Thiessen, M., & Gärtner, T. (2020). Active Learning on Graphs with Geodesically Convex Classes. In Proceedings of 16th International Workshop on Mining and Learning with Graphs (MLG’20). 16th International Workshop on Mining and Learning with Graphs, Austria. https://doi.org/10.34726/3467
We study the problem of actively learning the vertex labels of a graph, assuming the classes form geodesically convex subgraphs, which is related to linear separability in the Euclidean setting. The main result of this paper is a novel query-efficient active learning algorithm with label-independent upper bounds on the number of queries needed to learn all labels. For that, we use shortest path covers and provide a logarithmic approximation for the sub-problem of computing a shortest path cover of minimum size. We extend the approach to arbitrarily labeled graphs using a convexity-based selection criterion. Finally, we discuss whether the convexity assumption holds on real-world data and give some first preliminary results on citation and image benchmark datasets.
CC BY 4.0
