Sokolov, G., Thiessen, M., Akhmejanova, M., Vitale, F., & Orabona, F. (2025). Self-Directed Node Classification on Graphs. In G. Kamath & P.-L. Loh (Eds.), PMLR Proceedings of Machine Learning Research (pp. 1–31).
We study the problem of classifying the nodes of a given graph in the self-directed learning setup.
This learning setting is a variant of online learning, where rather than an adversary determining
the sequence in which nodes are presented, the learner autonomously and adaptively selects them.
While self-directed learning of Euclidean halfspaces, linear functions, and general multiclass hy-
po...
We study the problem of classifying the nodes of a given graph in the self-directed learning setup.
This learning setting is a variant of online learning, where rather than an adversary determining
the sequence in which nodes are presented, the learner autonomously and adaptively selects them.
While self-directed learning of Euclidean halfspaces, linear functions, and general multiclass hy-
pothesis classes was recently considered, no results previously existed specifically for self-directed
node classification on graphs. In this paper, we address this problem developing efficient algo-
rithms for it. More specifically, we focus on the case of (geodesically) convex clusters, i.e., for
every two nodes sharing the same label, all nodes on every shortest path between them also share
the same label. In particular, we devise an algorithm with runtime polynomial in n that makes
only 3(h(G) + 1)4 ln n mistakes on graphs with two convex clusters, where n is the total number
of nodes and h(G) is the Hadwiger number, i.e., the size of the largest clique minor of the graph
G. We also show that our algorithm is robust to the case that clusters are slightly non-convex, still
achieving a mistake bound logarithmic in n. Finally, we devise a simple and efficient algorithm for
homophilic clusters, where strongly connected nodes tend to belong to the same class.
Keywords: self-directed learning, online learning, node classification, graphs, time complexity