Timezone: »
We systematically study the query complexity of learning geodesically convex halfspaces on graphs. Geodesic convexity is a natural generalisation of Euclidean convexity and allows the definition of convex sets and halfspaces on graphs. We prove an upper bound on the query complexity linear in the treewidth and the minimum hull set size but only logarithmic in the diameter. We show tight lower bounds along well-established separation axioms and identify the Radon number as a central parameter of the query complexity and the VC dimension. While previous bounds typically depend on the cut size of the labelling, all parameters in our bounds can be computed from the unlabelled graph. We provide evidence that ground-truth communities in real-world graphs are often convex and empirically compare our proposed approach with other active learning algorithms.
Author Information
Maximilian Thiessen (TU Wien)
Thomas Gaertner (Fraunhofer IAIS)
More from the Same Authors
-
2021 : Controllable Network Data Balancing With GANs »
Fares Meghdouri · Thomas Schmied · Thomas Gaertner · Tanja Zseby -
2021 : Controllable Network Data Balancing With GANs »
Fares Meghdouri · Thomas Schmied · Thomas Gaertner · Tanja Zseby -
2022 : Generalized Laplacian Positional Encoding for Graph Representation Learning »
Sohir Maskey · Ali Parviz · Maximilian Thiessen · Hannes Stärk · Ylli Sadikaj · Haggai Maron -
2022 : Expectation Complete Graph Representations using Graph Homomorphisms »
Maximilian Thiessen · Pascal Welke · Thomas Gärtner -
2022 Poster: Active Learning of Classifiers with Label and Seed Queries »
Marco Bressan · Nicolò Cesa-Bianchi · Silvio Lattanzi · Andrea Paudice · Maximilian Thiessen