Active Learning of Convex Halfspaces on Graphs
Authors: Maximilian Thiessen
Thomas Gärtner
Venue: NeurIPS 2021 Poster (2021)
Keywords: active learning
learning theory
semi-supervised learning
transduction
vertex classification
graphs
convexity theory
geodesic convexity
shortest paths
halfspaces
query complexity

Abstract: 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.

Active Learning of Convex Halfspaces on Graphs
Maximilian Thiessen
Thomas Gärtner
Research Unit of Machine Learning TU Wien, Vienna, Austria maximilian, twwessen@tuwiennncommm ac.at
Research Unit of Machine Learning TU Wien, Vienna, Austria thomas wloomas.gerrnerrtuuee gwwrtner@twwienn ac. ac.at
Abstract
We systematically study the query complexity of learning geodesically convex halfspaces on graphs. Geodesic convexity is natural generalisation of Euclidean convexity and allows the definition of convex sets and halfspaces on graphs. We prove upper bound on the query complexity which is 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.
Introduction
We systematically characterise active learning of geodesically convex halfspaces on graphs. While unlabelled graphs such social networks are readily accessible, obtaining many labels is tedious and labour intensive, Active learning reduces the labelling effort by iteratively selecting informative data points be labelled. Graph-bases based active learning, in particular, has been successfully applied on communication [Regol et al., 2020] and protein-protein wwwpeio-inteeraeeeeee interaction networks [Vazquez et al., 2003, Xiong et al.. 2014]. While most previous approaches assume that the number of edges with differently labelled vertices, the cul size, is small [Afshani et al., 2007, Guillory and Bilmes, 2009, Dasarathy et al., 2015], we take a different approach and instead assume geodesic convexity: For every pair of vertices with the same label it holds that every vertex on every shortest path between them also has that label. This assumption is used, for example, by biologists on gene similarity networks [Zhou al., 2002] and cancer-related protein-proteii cetttt-rooteiiiiiiee irottiinintteaaction networks [Li et al., 2012, 2013]. It also typically holds for connected subgraphs of collaboration networks [Mare and Šubelj. 2018, Šubelj et al., 2019] and our preliminary experiments confirmed that many communities in community detection datasets are convex. We derive bounds on the number of queries required determine all labels, that is, the query complexity. using concepts from convexity theory and geodesic convexity spaces, which naturally generalise the regular Euclidean convexity. While learning convex sets and halfspaces in Euclidean spaces has been intensively investigated in the machine learning community for over half a century, geodesic convexity on graphs understudied. For a concise presentation of our theoretical results in this paper, concentrate on active learning of halfspaces on graphs, that is, the vertex set partitioned into two classes which are both geodesically convex.
After introducing the concepts of graph and abstract convexity theory in Section 2, we derive general iebleddndeenneett upper and lower bounds on the query complexity. We discuss that such general bounds can be loose on specific graphs and derive tighter lower bounds along the separation axioms of abstract convexity theory in Section This allows us to substantially reduce the gap between our upper and lower bounds. Note that Euclidean spaces cannot be structured in a similar way: while the separation axioms partition the space of all graphs into non-empty sets, all separation axioms
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

hold in all real vector spaces including the Euclidean spaces. We discuss related topics like previous active learning bounds that depend on the cut size between the classes, active learning of halfspaces in Euclidean spaces, non-active learning of geodesically convex halfspaces, and other related learning theoretic concepts in Section 4. Notably, we provide a bound on the VC dimension of geodesically convex halfspaces given by the Radon number. After presenting an empirical validation of our assumptions and approach in Section 5, we conclude with a discussion of future work.
2 Convexity spaces
In this section, we introduce the required concepts of convexity theory. For more thorough introduction on convexity theory we refer the reader to van de Vel [1993] and Pelayo [2013].
For set X and family C C 2 of subsets, the pair (X,C) is convexity space if (i) 0, X C. (ii) C is closed under intersection, and (iii C is closed under unions of sets totally ordered by inclusion. For finite set systems, property (ili) always holds. Any set in C is called convex. If set C and its complement X ) C are convex, both are called halfspaces. Two disjoint sets A, B are halfspace separable if there exists a halfspacce C' such that A C C and B S X CC A mapping Ø : 2 + 2* is a convex hull (or closure) operator if for all A, B C X with A S B (i) (0) = 0, (ii) (AA) C (B)) ((A). Any convexity space (X,C) induces a convex hull
(iii) A S a (A), and (iv) (A))) operator by (A) = Nic A C C C}. A set A S X is convex, that is A E C, if and only if is equal its convex hull, A= (A)).
A set C X is a hull set if its convex hull is the whole space, (H) For A, S X, the set A/B {ir X An (B U (=]]) * 0} is the extension of A away from B. For a, b X, the extension {a} / [b} is also called a ray a a/b. Two disjoint sets A1, A2 form a partition of A C X if # 0. The Radon number is the minimum number such that any subset of X of size r has a Radon partition.
A U A2 A. The partition 11 A2 of A is Radon partition if a (A1) n (a
A particular type of convexity is an interval convexity. Apart from the convex hull (-) it has an inter- val mapping I xx + 2x such that for all x. y E X. (i) x. y E [(x. y) and (ii I(x. y) = [(y x). [2x y) is the interval between x and y. We denote I (A4 = Uo,EE [a, b). A set C in an interval convexity space is convex and only if C = I(C)). The convex hull is given by (A) = U (A). where I' (.) = I(.) and fa+1(1 (.) = (+)), A well-known instance of interval convexity spaces are metric spaces (X. There, the interval contains all the points for which the triangle inequality holds with equality: Ia(x, y) = {a E X d(z y) = d(x, + d(2, y)}. In Euclidean space this corresponds to all points on line segment and leads the classical notion of convex sets.
We study metric spaces induced by graphs. The geodesic convexity (or shortest path convexity) of a connected graph G = (V, E') is given by the interval mapping Ta. where d : V22 + R is the shortest path distance in G. Let x, y E V. For unweighted graphs d(x: 3) is the minimum number of edges on any z-y-path and for graphs with edge weights,
E' + R it is the minimum total edge weight of any z-y-path. A set of vertices C C V is, thus, (geodesically) convex if and only if C contains every vertex every shortest path joining vertices in C, corresponding again to the Euclidean case.
We denote by (GG the vertex set of graph G, the Radon number of the induced geodesic convexity space of graph as r(G), and the size of the minimum hull set as hGG). Rays a b in graphs can be defined using the shortest path distance d: In unweighted graphs a/b = {u E V d(a, v) < d(bb, v)
and in weighted graphs a/b (u E V d(b, r) d(b, a) + dda, A vertex v is extreme if {v) forms halfspace, that is, V V [w) is convex. We denote the set of extreme vertices of as Ext((G (G). In unweighted graphs, is extreme if and only if its neighbours form clique. The diameter d d(G) of a weighted or unweighted graph G is the maximum number of edges in any shortest path in G.
3 Active learning halfspaces on graphs
Having introduced the necessary concepts from convexity theory, we now present the main theoretical results of the paper. In active node classification, a graph G = (V, E) with unknown vertex labels V - {0, 1} is given and the goal is to accurately predict all labels using as few as possible vertex queries. Edges can be weighted or unweighted. The learner queries the vertices one by one: iteratively selects vertices v E V and receives their label A(e). In this paper, we consider active learning on an undirected connected graph where the vertices with same label form geodesically

---

convex sets. The classes are, thus, halfspaccs and we call the labelling halfspace separable. Our results in this section are upper and lower bounds on the number of queries required to deduce all labels X of the graph. We denote the number of queries required to identify any halfspace separable labelling in the worst-case, the query complexity, by go(G). We derive two general upper bounds (Proposition 1, Theorem 5) and one lower bound (Theorem 7) on qe(G)) that hold for any halfspace separable labelling. To reduce the gap between the upper and lower bounds (Proposition 8), we derive increasingly tighter lower bounds along separation axioms (Theorem 10), In this section, we consider only undirected and connected graphs. Full proof' and a discussion of the multiclass, directed, and disconnected setting are in the supplementary material.
3.1 Upper bounds on the query complexity
To derive simple upper bound, we note that one immediate consequence of the halfspace assumption is that any shortest path P' can have at most one cut edge, that is, an edge with differently labelled endpoints. To deduce all labels of P. we first query its endpoints. If they have the same label, we know that all vertices on P have this label. Otherwise, we find the cut edge by binary search with at most [log d(G) queries, as the length of P is at most the diameter [V()) 1 S d(G). Here, log is the base 2 logarithm. We can generalise this approach to the whole graph using shortest path covers [Thiessen and Gärtner. 2020]. which a set S of shortest paths whose vertices cover the graph: UPES V(P) = VG).. Performing binary search on each path in S gives our first upper bound. Proposition 1. For any weighted graph G with minimum shortest path cover S" the query complexity can be bounded as qe(G) S | [2 + [log (())))
By considering a complete graph with edge weights such that the position of the cut edges all shortest path in the minimum shortest path cover can be chosen independently of each other, we can show that this bound is tight:
Proposition 2. For any l,s 8 E N. there exists a weighted graph G with diameter d(G) = l and minimum shortest path cover S of size s such that qe(G) 2 |S* log d(G)..
However, the graph in Proposition 2 is artificial worst-case example. For most graphs, we can do much better as the labels of vertices on different paths in the cover can typically not be chosen independently of each other. Consider a cubic hypergrid graph G, that is, the Cartesian product of k paths with f vertices each. More than (V( + 1 2 jkk shortest paths are needed to cover G but 2 + (ke] queries suffice to identify all labels, fixing one cut edge determines all others.
Our main idea to improve the bound and derive a better algorithm for active learning of geodesically convex halfspaces is to deduce additional labels using convex hulls and extensions after each query. Algorithm realises this idea. It first queries the vertices of a hull set (line 1). all labels in the hull set are the same, we conclude that all vertices in the graph have the same label (line 2-3). Otherwise, it performs binary search on a shortest path between two vertices with different labels to identify cut edge {a, b) (line 4-5). Finally, Algorithm 1 queries the remaining vertices. It initialises the sets A and B with the convex hull of the rays a/b and b/a, respectively, corresponding to vertices with already known labels (line 6). In each iteration of the main loop, the algorithm queries a vertex in the set W ab V(G) \ (a(a/) U Uo(b/a)), consisting of all vertices whose labels we cannot directly deduce through convex hulls and extensions, and updates the sets A and B using the new vertex (line 7-12). The number of queries spend in the first five lines are summarised in Lemma Lemma 3. Let G be a weighted graph with halfspace separable labels. Using hGG) + [log d(G)] queries, we can either find a cul edge or determine that all vertices of the graph have the same label.
Proof. The convex hull of any minimum hull set is the whole graph. If all vertices in a hull set have the same label, then all vertices in the graph have this label. If not, we can take two vertices with different labels and find a cut edge on a shortest path between them with [log diG)) queries. L
Lemma 4 shows that the initialisation and updates of A and B in Algorithm are indeed valid. Lemma 4. Let G be a weighted graph with halfspace separable labels given by a halfspace and let A C C and B C V(G) C. It holds that of (A/B) CC
Proof sketch. A/ B C as
as A A (x)) C CV 0 for all x E V(G) N.C. This
implies o (A/ B) = [(C' A/B C C², C' convex] S by definition.
O
3

---

Algorithm 1: Ray-based Active Halfspace Learning on Graphs
Input: graph G, oracle access labels X
Output: halfspaces corresponding to both classes
Compute hull set H and query its vertices
2 if I', h' E H A(h) = A(h') then
L return (0, V(G))
Choose h, E H such that A(h)) X(h'
5 Perform binary search queries on any shortest h-h' -path to find a cut edge {a, b}
A (a/bb, B (b/aa
7 while AU B VG)) do
query any vertex V(G) (AUB)
if A(v) A(a) then
L A ((Au (o))BB)
B (==(BB(AUU()))
10
else
12
A (B=
B B (o))/A)
13
return B)
We can bound the remaining number of vertices queried by Algorithm using the following set W (v E W=ab Aw Waab (v) such that E (w/a) (w/b))
as it is enough to know the labels of the vertices in W to deduce all labels of W=ab- Theorem 5 shows that Algorithm correct and summarises our main upper bound.
Theorem 5. Ler G be weighted graph. For the query complexity it holds that:
qc(G) S h(G)) + [log d(G)] +
max (a.))EE(G)
|W
Proof sketch. By Lemma 3, we can use h(G) + [log d(G)] queries to find the first cut edge (a,b). b). Every time Algorithm queries a vertex e E W= \ W there is a E W -ab by definition such that e E (w/a) n (w/b). .). It holds that w & AAB, B, as otherwise E (w/a) n (w/b) A AUB, which contradicts line 8 of Algorithm 1, E V(G) \ (AU B). Thus, in each iteration at least one new vertex from W aab will be added to or B. This bounds the number of iterations by -Waal--
O
Comparing our two upper bounds, we see that Theorem 5 is preferable to Proposition 1, as long as [W is small. To see this, note that the endpoints of paths a minimum shortest path cover S* form a hull set, implying (G) < 2 St If I =abl is small, the bound of Theorem 5 is additive in the dominating terms h(G) + [log d(G) < 2
[log d(G)). not multiplicative as in Proposition
To state the bound for the unweighted case in more common parameters, we relate !W to the well-studied freewidth tw (G) [Bodlaender, 1996), which measures the tree-likeness' of graph. It is known, that the largest & E N. such that the complete bipartite graph K2, is minor of graph G, is most twice the treewidth [Bodlaender et al., 1997]: k < tw(G). This bounds the size WWa < 2 tw( (G) for any edge {a, 6}, as the vertices {a, 6} U U =ab form a minor K2. "..l Consequently, graphs with small treewidth like molecules [Horváth and Ramon, 2010] and infrastructure-based networks [Maniu et al., 2019] have small W Corollary 6 summarises this result.
Corollary Let G be an unweighted graph. For the query complexity holds that go(G) S MGG)) + flog d(G) 2 (G).
3.2 Lower bounds under separation axioms
Having discussed our upper bounds on the query complexity, based on the extreme vertices Ext(G) of the graph, recall each of them is halfspace by definition.
turn simple lower bound
Theorem 7. For any weighted graph G, it holds that qe(G) > Ext(G))
Considering graph containing paths that all coincide only in the same two endpoints, we can show that this bound is tight and that the gap between it and our upper bound can be arbitrarily large.

---

Table 1: Tight bounds for common unweighted graph families.
graph family
sep. axiom
bound on qo(G)
remark
trees
S1
(log d + (x)(
(x) are exactly the leaves
K2.3 minor-free free
S4
(log d(G) + h(G))
including outerplanar graphs
partial cubes
S3
(log d(G) + h(G))
O() holds for all bipartite graphs
weakly median
S4
@llo d(G) + h(G) +r(
O() holds for meshed graphs
Proposition 8. For any l, s, k. E N, there exists unweighted graph G with d(G) 2 E, minimum shortest path cover S of size at least s, h(G) 2 k Ext(G) = c, and qc(G) I max e2, e}.
This shows that this lower bound is best possible in general, even if d(G), h(G), and 8 are large. One main insight of our work is that we achieve increasingly tighter lower bounds by structuring the set of all graphs along separation axioms, which characterise the ability of a convexity space to separate sets via halfspaces. This follows a related notion in topological spaces.
Definition (Separation axioms [van de Vel, 1993]) A convexity space (X,C) is:
S1 if and only if each singleton X is convex.
S2 if and only if each pair of distinct elements x, y E X is halfspace separable.
Sy if and only if each convex set C and elements x E X XXC. C are halfspace separable.
S4 if and only if any two disjoint convex sets are hulfspace separable.
If S1 holds, which is the case for the geodesic graph convexity, the remaining axioms are increasingly stronger, that is, S2 + S3 < S4. We call a graph S,, for 1, .,,..,44 4, if the induced geodesic convexity space satisfies the respective separation axiom. While real vector spaces such as the Euclidean space satisfy all four separation axioms [Kakutani, 1937], there are graphs that are S; but not S for 1, 2, 3 [Bandelt, 1989], see supplementary material for some examples. Structuring all graphs along these separation axioms gives us increasingly stronger lower bounds.
Theorem 10. For every weighted graph G the following holds for the query complexity qc(G))
if G is S2, then qc(G) Z max{log (G)
if G is Sz, then qc(G) > max{log ((G), and
G is S4, then qe(G) max/log
Each bound is tight in the respective family and stronger axioms lead to tighter bounds.
Proof sketch.. In S2 graphs, any edge a fixed but arbitrary shortest path with size of the diameter can be bisected with a halfspace. Thus, log d(G) queries are required find the chosen edge. In S3 graphs, any point h E H1 can be separated from the remainder of a minimum hull set H" thus the whole hull set H must be queried in the worst-case. In S4 graphs, any set that has Radon partition can be labelled arbitrarily. To see that the bounds are increasingly tighter, notice that all extreme vertices are by definition contained in any hull set and hence Ext(G) S h(G). As there are graphs with hGG) = k and rG)) = for any k. t E N with k, 2 4, both parameter can be dominating.
Theorems 5 and 10 imply tight bounds (Table 1) for graph families in metric graph theory [Bandelt and Chepoi, 2008], convexity theory [Chepoi, 1994], and machine learning [Seiffarth et al., 2019].
3.3 Computational aspects
Above, we derived lower and upper bounds on the query complexity of learning halfspaces on graphs G (V,E), We now discuss computational aspects of our algorithms and bounds.
5

---

bound To achieve the bound of Proposition 1, we need to compute a minimum shortest path cover of the given graph, which is an open problem [Manuel, 2021]. We show that greedily covering the graph with longest shortest paths gives logarithmic approximation:
Theorem 11. For a given weighted graph G, we can compute an (1 + In(d(G) + 1)) approximatin for the minimum shortest path cover S in time ((VV)*).
Thus, using this approximation we achieve the query complexity bound qc(G) I |S
[log d( in polynomial time. To evaluate this bound, we also need to compute the diame- ter d(G), which can be achieved by a generalised Dijkstra algorithm, see supplementary material.
Hull-set-based bound The main computational bottleneck of Algorithm 1 is the computation of a minimum hull set. Computing the minimum hull set size h(G) is APX-hard [Coelho al., 2015]. For many graph families however, such as distance-hereditay [Kanté and Nourine, 2016], interval, and cographs [Dourado et al., 2009] the problem is solvable in polynomial time. Moreover, the problem can be solved in polynomial time if any of the following parameters is bounded by a constant: the treewidth [Kanté et al., 2019]. the vertex cover size, the neighbourhood diversity [Araujo et al., 2013b], and the number of induced paths in bounded vertex subsets [Araujo et al., 2013a]. The remaining runtime of Algorithm I is dominated by the computation of convex hulls and extensions. A single convex hull computations can be performed in time O ()) by first computing the full distance matrix and then evaluating the triangle inequality for each triplet of vertices. Extensions can be computed through [ convex hull evaluations. Algorithm I achieves, thus, the bound of Theorem in polynomial time, as long as we can efficiently compute a minimum hull set. On unweighted graphs we additionally achieve the bound in Corollary 6 efficiently in this case. Alternatielly, we can compute any. possibly non-optimal, hull set H in polynomial time to achieve the bound H + [log d(G)] (G.)
[Waabl-
Lower bounds To evaluate our lower bounds in Theorem 10, we also need to compute Ext(G) and rGG). Computing the set of extreme vertices Gx) possible in time ((V]] by evaluating the neighbourhood of each vertex. Computing the Radon number of graph is even hard to approximate within any factor sublinear in [V] [Coelho et al., 2015]. However, Duchet and Meyniel [1983] bounded the Radon number in terms of the size of the largest clique minor, that is, the Hadwiger number, which in turn can be upper bounded by the treewidth.
Proposition 12. For any weighted graph G, it holds that r(G) (G) +
Thus r(G) is computable in polynomial time for bounded treewidth graphs. To decide which lower bound applies for given graph, we need to check if the graph is S, for 1..... 4. For the cases 8= 1, 2, 3, it is unclear whether this is possible in polynomial time. Only for S₂ an algorithm with runtime (IVV ((V(())))) is known [Seiffarth et al., 2019]. Just deciding whether graph has a proper halfspace, which is neither empty nor the full graph, is NP-hard [Artigas et al., 20112 1]. Both problems are efficiently decidable on planar and bipartite graphs [Glantz and Meyerhenke, 2017].
4 Discussion
In this section, we discuss our assumptions as well as results related to our learning problem.
Convexity in real-world datasets In some applications convexity -ased assumptions are already implicitly or explicitly used, For example, it is well-known that shortest paths in gene similarity networks largely preserve functional relationships [Zhou et al., 2002]. Similarly on protein-protein- interaction networks, shortest paths between cancer-related genes are used to identify a candidate set of novel genes, which are likely to be cancer-related, as well [Li et al., 2012, 2013]. Aside from biological networks, Marc and Šubelj [2018] and Šubelj et al. [2019] recently found that connected subgraphs of certain real-world graphs like collaboration networks are often convex. To provide further evidence for convexity in real-world graphs, we performed preliminary experiments on different networks with ground truth communities. Table 2 shows the number of convex communities in six datasets from SNAP [Leskovec and Krevl, 2014]. We found that on the DBLP scientific collaboration dataset more than 85% of the 5000 communities are convex, supporting the results of Subelj et al. [2019]. On the Amazon product network we have similar results with roughly 80%. On the Youtube network we found that roughly 60% of the communities are convex. On the remaining

---

Table 2: Number of convex communities.
dataset
convex communities
dataset
convex communities
DBLP
4308/5000 2990//5000
Amazon
3999/5000 1649/5000
Youtube
LiveJournal
Orkut
363/5000
Eu-core
7/42
three datasets, however, less than a third of the communities are convex. Clearly, convexity on graphs is application dependent and further study with real-world networks is necessary.
Relationships to Euclidean convexity Learning halfspaces in Euclidean space one of the oldest learning problems initiating algorithms like the perceptron [Rosenblatt, 1958, Novikoff, 1962] and support vector machines [Boser et al., 1992. Cortes and Vapnik, 1995], and is still an active research area [Daniely, 2016, Diakonikolas et al., 2019, Hopkins et al., 2020]. A simple lower bound for the number queries required to learn the labels of a finite set X S IR' labelled accordingly to a halfspace is (m log XI) [Hopkins et al., 2020]. However, for worst-case instances such as points on the circle, already ((X)) queries are required to identify all labels [Dasgupta, 2005], corresponding to our hull set lower bound. The query complexity can be improved through membership query synthesis [Angluin, 1988], which allows the learner to query additionally any point in R"' XX Using
them, Hopkins et al. [2020] showed that in expectation Om log" (m) (m) log [X]] + m ++((1) queries enough to infer all labels, essentially matching the lower bound. There is no direct equivalent of membership queries in the transductive graph setting. It is in general not possible to embed a graph into RT or the other way around while preserving halfspaces. An example can be seen in Figure Ic and further discussion can be found in the supplementary material. Together with the fact that Euclidean convexity spaces are always S4 while graphs do not have to be, there is immediate way to transform general bounds on the query complexity from one setting to the other.
Previous cut-based bounds Most previous bounds for active learning on graphs are linear in the number of cut edges C or cut vertices oC, which are the vertices incident to the cut edges. Therefore, these bounds can become vacuous when the cut is large, independent of halfspace separable labels. We will illustrate the bounds on the unweighted 2 x k grid, that is, the Cartesian product of a path with l vertices and path with 2 vertices. On the one hand, our upper bound of Theorem 5 yields query complexity of 2 + log(k + 1). On the other hand, the bounds of Afshani et al. [2007] and Dasarathy et al. [2015] result in at least |aC| queries even under additional balancedness assumptions on the labels. Thus, the bounds are at least [V] for the halfspace corresponding to the 1 x k grid. The bound of Guillory and Bilmes [2009] is for the non-iterative active setting, where a set L S V of vertices is queried all at once. Let 8(T) denote the set of edgs with exactly one endpoint in T S V. They bound the error by (L) using the min-cut- based prediction strategy [Blum and Chawla, 2001], where (L) ming I/TT) As long as |L| < |V//8, we will have (L) I 4/8 and for the previously mentioned halfspace |C"l = k. Thus, the error bound will be at least 2k = [V.. This shows that the three discussed previous bounds can be vacuous and exponentially worse than our achieved bound. All three are particularly sensible to large cut sizes. The sole cut is thus not sufficient measure the complexity inherent in the labelling.
Margin-based bounds Bressan et al. [2021] study the query complexity of identifying convex clusters in the e-nearest-neighbourr of semi-metric space (X,d). Even though they rely additional assumptions, like a large margin, their upper bound is very similar to our main result. However, they only provide lower bounds on the query complexity on specific worst-case instances, while our lower bounds hold in general under the different separation axioms. They use same-cluster queries, which are binary queries on a pair of vertices to test whether they belong to the same cluster. Same-cluster queries and regular vertex queries are equivalent in terms of the query complexity up to a multiplicative factor given by the number of classes. To derive a bound they use restrictions beyond our halfspace assumption. In particular, Bressan et al. [2021] assume that the weight of any cut edge is > Be for a B (0, 1] and use an interval I (7,,, y) with margin 7 E (0, 1]. which consists of all vertices that lie on path at most (1 + 7) as long as the shortest --y--pah, to define convex sets. The regular geodesic convexity corresponds to 7 = They also require a constant number of
so-called seed queries that take a class label and set U C X as input and return a vertex from U
7

---

with the specified label or certify that U does not contain such a vertex. Under these assumptions they derive an O log [X] + (%/2- dene(X)) upper bound on the query complexity, where dens is the density dimension of the space [Gottlieb and Krauthgamer, 2013]. Even though Bressan et al. [2021] consider a more restricted hypothesis space, there exist graph families where our bound in Theorem 5 is exponentially better. For example, on the 2 x k grid, the halfspace corresponding the 1 x k grid enforces margin of y < 2/k: This results in bound of at least log(2k) + (3k) (3k))dns(() with dens(X) X) 2 1 while our bound (Theorem 5) predicts that 2 + log(k + 1) queries are enough. Even with a large Y our bound remains better on this example.
Alternatives to hull sets As computing minimum hull sets is APX-hard in general [Coelho et al., 2015], we discuss two alternatives to perform the first step in Algorithm that is, finding two vertices with different labels. For that, Afshani et al. [2007] and Dasarathy et al. [2015] assume that the labels are balanced, that is, the relative size 3 of the smallest labelled class is close to 1/2. This assumption is in their case required to find two vertices with different labels query-effiiietly use any
with high probability 1 a, for (0, 1). We do not require this assumption as hull set to achieve the same deterministically. However, if [3 is known, we can state an alternative
log(Ao) probabilistic upper bound. Instead of spending (G) queries we can sample a set of size
[og[1-0]
uniformly at random from V(G) find two differently labelled vertices with probability 1 ar [Dasartthy et al., 2015]. This means that with probability 1 the query complexity is bounded [log di (G) + maX(a.))EB(C)) W The other alternative using the mentioned seed queries of Bressan et al. [2021]. Spending only two seed queries to find two vertices with different labels and [log d(G)) + max (a. E F(G) |W label queries using Algorithm from line 5 on is enough. We note that both bounds can be achieved algorithmically in polynomial time.
by qe(G) S
log(8o)
[=g(1-83
Non-active learning of convex sets and halfssaace Non-active learning of halfspaces on graphs was studied by Seiffarth et al. [2019, 2020] and de Araūjo et al. [2019]. Seiffarth et al. [2019] rely on the separation axiom S4 to bound the number of convex hull evaluations needed to construct a halfspace. Anthony and Ratsaby [2018] study the problem of learning large-margin halfspaces set equipped with an arbitrary dissimilarity measure d. which generalises shortest path distances of graphs. However, their notion of halfspace, {a d(æ, p²) S d(zr,p") based on the dissimilarity to two prototypes p+, p is in general not convex. Stadtländer et al. [2021] investigate the problem of learning weakly conver sets in a metric space (X, dd) Here, weakly convex sets with parameter 0 2 0 are given by the interval mapping (a, b) = {z X d(a, +d(xxx regular geodesic convexity corresponds 0 Z max,, b d(a. b). Gärtner and Garriga [2007] and Missura and Gärtner [201] 1] studied monotone classes in directed acyclic graphs, which corresponds to an interval mapping containing the vertices on all directed paths instead of just shortest paths. Moran and Yehudayoff [2019] established that the VC dimension of halfspaces of any convexity space smaller than the Radon number of the space. Building on that, we can show that VC dimension is exactly determined by the Radon number in S4 convexity spaces. This corresponds to the classical result that in TM the VC dimension of halfspaces is m + and the Radon number is m + 2.
d(a, b) < 0) bj. The
Proposition 13. The VC dimension of the hypothesis class of halfspaces of an S^ convexity space is exactly one less than the Radon number of the space.
For S4 graphs, r(G) determines the VC dimension and gives lower bound on the query complexity (Theorem 10), establishing the Radon number as a central parameter for learning geodesically convex halfspaces. Proposition 12 together with the above bound of Moran and Yehudayoff [2019] gives:
Proposition 14. The VC dimension of halfspaces in a weighted graph G is at most 2 tw(G) + 1.
5 Experiments
Having discussed our bounds on the query complexity and the conceptual benefits of the halfspace assumption in terms of theoretical upper bounds, we want to see whether we also get empirical benefits on data, as well. We propose two practical versions of Algorithm 1: greedy and selective sampling. The greedy strategy tries to maximise the number of known vertex labels with each query. For that, it queries the vertex e that would maximise the minimum number of known labels after the update of A and B. More precisely, after the update with vertex we will know the labels
8

---

(a) Two moons NN-graph.
(b) Iris dataset NN-graph.
(c) Not separable in R??
Figure 1: Halfspace separations on different graphs.
of the set ((AU) (B)( or the set U U ( The greedy strategy thus selects the vertex that maximises the size of the smaller one of these two sets. As performing the described greedy maximisation for each query rather computationally expensive, we propose simpler strategy based on selective sampling [Cohn al., 1994] that picks a vertex uniformly at random from V(G) \ (AU B) in line 8 of Algorithm 1.
To find the first cut edge, Algorithm I requires hull set in the first step. As discussed, computing a minimum hull set is in general not tractable. Therefore, we propose to use the selection strategy (greedy or selective sampling) also to iteratively construct hull set until two vertices with different labels are found. For that we start with A B and query a vertex v from V(G) \ A: by maximising |a U [v}) (greedy). Afterwards we update := (A U {u}) and repeat until e has a different label than the previous vertices. Implicitly this process will construct (typically
either uniformly random (selective sampling)
mon-minimum) hull set H. That way the query complexity bound in Theorem 5 still holds, as it is independent of the specific selection strategy used; only the (G)) is replaced with the size of the heuristically computed H. We compare these two strategies with the state-of-the--n graph-based active learning algorithm S [Dasarathy et al., 2015], the classical active label propagation of Zhu et al. [2003b], and baseline non-active random sampling.
As datasets, we use e-nearest- e-ncarest-neighbous neighbour graphs of two moons' and Iris?, see Figures la and lb. The parameter selected such that the graph is connected and the labels are halfspace separable. Additionally, we use a 20 x 20 grid and a 20 hypercube labelled with a random halfspace. We implemented all approaches in python? and ran the experiments on Ubuntu 21.04 laptop with 32GB main memory. More details and in-depth experiments are in the supplementary material.
5.1 Query evaluation
Dasarathy et al. [2015] proposed to count the number of found cut vertices after each query measure to compare querying algorithms without relying on any classification method. A query- efficient graph-based active learner should detect these as fast as possible. The results for 20 iterative queries in the upper half of Figure show that our approaches identify the cut vertices more efficiently than 5², active label propagation, and random sampling by deducing many labels after each query. Our greedy approach requires at most 6 queries to deduce all vertex labels on all four datasets emphasising the strength of convexity-based assumptions. The selective sampling approach is only slightly worse using 2-8 queries more. S², active label propagation, and random sampling can find most one cut vertex per query as they do not rely on these assumptions. As can be seen on the grid dataset, S2 performs better than active label propagation and random sampling finding a cut vertex on any new query, which is not by coincidence was specifically designed for this task.
5.2 Predictive performance
We also evaluated the predictive performance of the chosen queries. Our two approaches predict the labels of the computed hulls and default to the majority of known labels when they do not know vertex's ' label. The other three approaches perform label propagation [Zhu et al., 2003a] with the default Gaussian similarity and length-scus scale whole graph after each query of the 20 queries. In the lower half of Figure 2, we can confirm that
1 for prediction. We check the accuracy on the
1g 0.14, faake_moons_eee (noise=0.1 1, random_ random_state=0) in scikit-learn [Pedregosa et al., 2011]
2g = 0.3, first class vs the other two [Fisher, 1936] htttps:/ www//matthieeeee//tttteeeeeeeeee httpsaaaahahaaaahaaaehaa

---

greedy
selective sampling
S
aclive
random
% found cut vertices
1.0
0.5
0.0
1.0
accuracy
0.5
0.0
5
10
15
20
5
10
15
20
5
10 grid
15
20
5
10
15
20
hypercube
Figure Found cut vertices and accuracy plotted against number of queries.
greedy identifies the vertex labels of the whole graph on all datasets within 6 queries. The predictive behaviour of the three baselines worse, even unstable. The main reason is that label propagation favours small cuts (weighted by the similarity), and thus fails to predict halfspaces, especially on the grid and hypercube. 5² mitigates this problems to some extent, even though it predicts the labels also with label propagation, by removing any found cut edge from the graph. Still, it has difficulties to find the correct halfspace and then stick to these prediction, as can be seen, for example, on the grid.
6 Conclusion and Future Work
In this paper, we introduced active learning of halfspaces on graphs and derived tight bounds on the query complexity for this problem using concepts from convexity theory. On the one hand, we derived two general upper bounds: one based on shortest path covers and the other based on the diameter, hull sets, and the quantity (aX E(G) W aabl We showed that the latter treewidth of the graph in the unweighted case. On the other hand, we derived general lower bound based on extreme vertices and increasingly tighter lower bounds for graph families induced by the separation axioms. For the strongest separation axiom S4. we achieved nearly tight lower and upper bounds with only the gap between the Radon number rG') and (aX)EEEEEE( W remaining.
is at most twice the
We compared our bounds to previous cut-based bounds and showed that the halfspace assumption makes learning with large cuts possible while previous bounds are vacuous in this case. We dis- cussed that there are inherent differences between Euclidean and graph convexity spaces such that the respective query complexity bounds do not carry over the other setting. With preliminary experiments we confirmed that communities in real-world networks such as collaboration and product networks are often convex. Based on our algorithm, we proposed two practical variants greedy and selective -sapplmmllll ing. We empirically compared them with active label propagation [Zhu et al., 2003b] and 52 [Dasarathy al., 2015] on datasets with halfspace separable classes and found that our algorithms require considerably less queries to correctly identify the halfspaces. The main bottleneck of our variants is the cubic runtime to compute convex hulls. To scale our methods to large datasets we will investigate efficient approximations of convex hulls [Blum et al., 2019) 9] and distances using the Nyström [Williams and Seeger, 2001] or other landmark based methods [Potamias et al., 2009].
To make our results more broadly applicable, we propose to relax our notion of halfspaces and use the weak convexity of Stadtländer et [2021]. They define weak convexity with respect a parameter 0 2 O and show that weakly convex sets can be decomposed into weakly convex blocks that are least distance of apart. The number of these blocks may serve as a parameter to adapt our bounds to weakly convex classes. Another promising future research direction is to develop querying and prediction strategies for general interval convexity spaces by combining our ideas with those of Seiffarth et al. [2019], Stadtländer al. [2021], and Bressan et al. [2021]. A promising first step is to consider geometric interval spaces using base-point orders [van de Vel, 1993]. Finally, we propose to also investigate regret bounds for online learning of convex sets graphs.
10

---

Broader impact statement As this is an early theoretical and algorithmic work, we do not see any specific immediate societal impact. neither positive nor negative. In the long run the developed theoretical results might help reduce the required number of labelled data points in graph-based learning settings and help with data annotation general.
Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers for helpful comments and Marco Bressan for fruitful discussions.
References
Peyman Afshani. Ehsan Chiniforooshan, Reza Dorrigiv, Arash Farzan, Mehdi Mirzazadeh, Narges Simjour, and Hamid Zarrabi-Zadeh. On the complexity of finding unknown via vertex queries. In International Computing and Combinatorics Conference, 2007.
Dana Angluin. Queries and concept learning. Machine learning, 2(4):319-344 342, 1988.
Martin Anthony and Joel Ratsaby. Large-widtt width bounds for learning half-spaces on distance spaces. Discrete Applied Mathematics, 243:73-89, 2018.
Julio Araujo, Victor Campos, Frédéric Giroire, Nicolas Nisse, Leonardo Sampaio, and Ronan Soares. On the hull number of some graph classes. Theoretical Computer Science, 475:1-12, 2013a.
Julio Araujo, Gregory Morel, Leonardo Sampaio, Ronan Soares, and Valentin Weber. Hull number: P5-free graphs and reduction rules. Electronic Notes in Discrete Mathematics, 44:67-73, 2013b.
Danilo Artigas, Simone Dantas, Mitre C. Dourado, and Jayme I.. Szwarefiter. Partitioning graph into convex sets. Discrete Mathematics, 311((7))1168-199)) 19777 2011.
Hans-Jürgen Bandelt. Graphs with intrinsic s3 convexities. Journal of graph theory, 13(2):215-228. 1989.
Häng-Jürgen Bandelt and Victor Chepoi. Metric graph theory and geometry: survey. Contemporary Mathematics, 453:49-86, 86, 2008.
Avrim Blum and Shuchi Chawla. Learning from labeled and unlabeled data using graph mincuts. In ICML, 2001.
Avrim Blum, Sariel Har- and Benjamin Raichel. Sparse approximation via generating point sets. Transactions on Algorithms, 15(3):1-16, 2019.
Hans L. Bodlaender. linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on computing, 25(6)) 1996.
Hans L. Bodlaender, Jan van Leeuwen, Richard Tan, and Dimitrios M. Thilikos. On interval routing schemes and treewidth. Information and computation, 139(1):92-109, 1997.
Bernhard E. Boser, Isabelle M. Guyon, and Vladimir Vapnik. A training algorithm for optimal margin classifiers. In COLT, 1992.
Marco Bressan, Nicolò Cesa-Biai Bianchi, Silvio Lattanzi, and Andrea Paudice. Exact recovery of clusters in finite metric spaces using oracle queries. In COLT, 2021.
Victor Chepoi. Separation of two convex sets in convexity structures. Journal of Geometry, 50(1-2); 30-51, 1994.
Erika M. M. Coelho, Mitre C. Dourado, and Rudini M. Sampaio. Inapproximability results for graph convexity parameters. Theoretical Computer Science, 600:49-58. 2015.
David Cohn, Les Atlas, and Richard Ladner. Improving generalization with active learning. Machine learning, 1522):201-221, 1994.
Corinna Cortes and Vladimir Vapnik. Support-vector networks. Machine learning, 20(3):273-277, 1995.

---

Amit Daniely. Complexity theoretic limitations on learning halfspaces. In STOC, 2016.
Gautam Dasarathy, Robert Nowak, and Xiaojin Zhu. S2: An efficient graph based active learning algorithm with application to nonparametric classification. COLT, 2015.
Sanjoy Dasgupta. Coarse sample complexity bounds for active learning. In NIPS, 2005.
Paulo H.M. de Araújo, Manoel Campêlo, Ricardo C. Corréa, and Martine Labbé. The geodesic classification problem on graphs. Electronic Notes in Theoretical Computer Science, 346:65-76. 2019.
Ilias Diakonikolas, Themis Gouleakis, and Christos Tzamos. Distribution-indeeenddn PAC learning of halfspaces with Massart noise. NeurIPS, 2019.
Mitre C. Dourado, John G. Gimbel, Jan Kratochvíl, Fábio Protti, and Jayme L Szwarcfiter, On the computation of the hull number of graph. Discrete Mathematics, 309(18):5668-50) 2009.
Pierre Duchet and Henry Meyniel. Ensemble convexes dans les graphes i: Théorèmes de Helly de
Radon pour graphes et surfaces. European Journal of Combinatorics, 4(2): 1983.
Ronald A. Fisher. The use of multiple measurements in taxonomic problems. Annals of eugenics, 7 (2):179-188, 1936.
Thomas Gärtner and Gemma C. Garriga. The cost learning directed cuts. ECMLPKDD, 2007.
Roland Glantz and Henning Meyerhenke. On finding convex cuts in general, bipartite and plane graphs. Theoretical Computer Science, 695:54-733 73, 2017.
Lee-Ad Gottlieb and Robert Krauthgamer. Proximity algorithms for nearly doubling spaces, Journal on Discrete Mathematics, 1759:177,,, 2013.
Andrew Guillory and Jeff Bilmes. Label selection graphs. In NIPS, 2009.
Max Hopkins, Daniel M. Kane, Shachar Lovett, and Gaurav Mahajan. Point location and active learning: Learning halfspaces almost optimally. FOCS, 2020.
Tamás Horváth and Jan Ramon. Efficient frequent connected subgraph mining in graphs of bounded tree-width. Theoretical Computer Science, 41 (1166-33):2784-2799 2010.
Shizuo Kakutani. Ein Beweis des Satzes von M. Eidelheit über konvexe Mengen. Proceedings of the Imperial Academy, 13(4):93-99) 94, 1937.
Mamadou Moustapha Kanté and Lhouari Nourine. Polynomial time algorithms for computing min- imum hull set in distance- aaeaancce-eeeetarry and chordal graphs. SIAM Journal on Discrete Mathematics, 2016.
Mamadou Moustapha Kanté, Thiago Marcilon, and Rudini Sampaio. On the parameterized comple complexity of the geodesic hull number. Theoretical Computer Science, 1:1-18, 2019.
Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http: //snap. stanford odu/dataa June 2014.
Bi-Qing Li, Tao Huang, Lei Liu, Yu-Dong Cai, and Kuo-Chen Chou. Identification of colorectal cancer related genes with mrmr and shortest path in protein-protein interaction network. PLoS one, 7(4):3333,3, 2012.
Bi-Qing Li, Jin You, Lei Chen, Jian Zhang, Ning Zhang, Hai-Peng Li, Tao Huang, Xiang- Yin Kong, and Yu-Dong Cai. Identification of Lung-cancer-relatee genes with the shortest path approach in protein-protein interaction network. BioMed research international, 2013.
Silviu Maniu, Pierre Senellart, and Suraj Jog. An experimental study of the treewidth of real-world graph data. International Conference on Database Theory, 2019.
Paul Manuel. On the isometric path partition problem. Discussiones Mathematicae Graph Theory, 1079 202..
12

---

Tilen Mare and Lovro Subelj. Convexity in complex networks. Network Science, 6(2):176-25) 2018.
Olana Missura and Thomas Gärtner. Predicting dynamic difficulty, In NIPS, 2011.
Shay Moran and Amir Ychudayoff. On weak epsilon nets and the Radon number. In Symposium on Computational Geometry, 2019.
Albert B. Novikoff. On convergence proofs on perceptrons. In Symposium the Mathernttiaal Theory of Automata, 1962.
Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, Jake Vanderplas, Alexandre Passos, and David Cournapeau. Scikit-leam: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2834 2011.
Ignacio M. Pelayo. Geodesic convexity in graphs. Springer, 2013.
Michalis Potamias, Francesco Bonchi, Carlos Castillo, and Aristides Gionis. Fast shortest path distance estimation in large networks. In Conference Information and knowledge management,
2009.
Florence Regol, Soumyasundar Pal, Yingxue Zhang, and Mark Coates. Active learning on attributed graphs via graph cognizant logistic regression and preemptive query generation. In ICML., 2020.
Frank Rosenblatt The Perceptron: probabilistic model for information storage and organization in the brain. Psychological review, 65(6))386, 1958.
Florian Seiffarth, Tamás Horváth, and Stefan Wrobel. Maximal closed set and half-space separations in finite closure systems. In ECMLPKDD, 2019.
Florian Seiffarth, Tamás Horváth, and Stefan Wrobel. Maximum margin separations in finite closure systems. In ECMLPKDD, 2020.
Eike Stadtländer, Tamás Horváth, and Stefan Wrobel. Learning weakly convex sets in metric spaces. In ECMLPKDD, 2021.
Lovro Subelj, Dalibor Fiala, Tadej Ciglarič, and Luka Kronegger. Convexity in scientific collaboration networks. Journal of Informetrics, 13(1):10-31, 2019.
Maximilian Thiessen and Thomas Gärtner. Active learning on graphs with geodesically convex classes. In KDD workshop on Mining and Learning with Graphs, 2020.
Marcel L.J. van de Vel. Theory of convex structures. Elsevier, 1993.
Alexei Vazquez, Alessandro Flammini, Amos Maritan, and Alessandro Vespignani. Global protein function prediction from protein-proteli interaction networks. Nature biotechnology. (6))6667 700, 2003.
Christopher KI Williams and Matthias Seeger. Using the Nyström method to speed up kernel machines. In NIPS, 2001.
Wei Xiong, Luyu Xie, Shuigeng Zhou, and Jihong Guan. Active learning for protein function prediction in protein interaction networks. Neurocomputing, 145:44-52, 2014.
Xianghong Zhou, Ming-Chih J Kao, and Wing Hung Wong. Transitive functional annotation by shortest-path analysis of gene expression data. Proceedings of the National Academy of Sciences, 99(20): 2002.
Xiaojin Zhu, Zoubin Ghahramani, and John Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. In ICML, 2003a.
Xiaojin Zhu, John Lafferty, and Zoubin Ghahramani. Combining active learning and semi- supervisd learning using gaussian fields and harmonic functions. ICML workshop on the continuum from labeled to unlabeled data in machine learning and data mining, 2003b.
13


Reviews:
[{"review_id": "sYcJXfdVPJ", "reviewer": "Reviewer_sgyY", "summary": "The paper studies the problem of active learning on graphs to identify two classes. The main assumption is that the vertices of the same class form a geodesically convex set, and the two classes are halfspace separable. \nThe authors propose a simple halfspace querying algorithm, and analyzes the upper and lower bounds on the number of queries required to deduce all labels of the graph for binary classification on connected undirected graphs. In particular this number of queries is related to the graph properties and the separation condition between two classes. Furthermore the VC dimension of the hypothesis class is related to the aforementioned properties.  ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n\nThe problem discussed in the paper is interesting and novel. If my understanding is correct, the whole assumption at the beginning of Section 3 can be viewed as a generalization of convex and lienar separable clusters in the Euclidean space. \n\nI am not sure how relevent the results are to the NeurIPS community since it is more on the theoretical CS side, but I like the insights about graph properties (treewidth / diameter / hull set) -- upper bound, and separation condition S1, S2, S3, S4 -- lower bound. The latter is in particular interesting, as one does not have the differences in simple spaces.\n\nThe paper is well written and organized for most of the time. I did not check the proofs though. \n\n\n\nWeakness:\n\nOne could potentially argue that the assumption of two classes being geodesically convex and perfectly separable is a very strong condition. Basically this is equivalent to saying that the observed communities are noiseless. \n\nSurprisingly, the paper shows that there exists a large number of convex communities in real world networks as in Table 2. Could the authors comment on how separable (maybe in terms of S1 - S4) the communities are in these real world networks?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "n/a\nThis is a theoretic work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "gyHugvnf0P8", "reviewer": "Reviewer_G7Y8", "summary": "This paper considers learning of geodesically convex halfspaces and present upper and lower bounds on the query complexity.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "While it seems natural to consider a more general concept class, it is not clear to me the significance of geodesical convexity. What is the main application of the approach?\n\nThe technical novelty also appears vague.\n\nSince the paper claims the generality, do the current results recover the best known results of learning halfpsaces in the literature?\n\nIf I understand correctly, the results only apply to noise-free learning which is a strong restriction.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "f70HerDwm4Q", "reviewer": "Reviewer_KdHb", "summary": "This work studies the query complexity of active learning geodesically convex halfspaces on graphs (that is given a graph $G=(V,E)$, the class of subsets $S \\subseteq V$ such that $S$ and $V \\setminus S$ are both convex). While most prior works gave hypothesis-dependent upper bounds, here the authors give two novel worst-case bounds based on natural graph parameters: the first on the smallest shortest path cover, the second on the hull size, diameter, and tree-width. While neither algorithm is computationally efficient in its original form, the former can be efficiently approximated to within a (multiplicative) logarithmic factor in the diameter, and the latter can be computed efficiently on graphs with bounded tree-width.\n\nThe authors also prove a complementary series of lower bounds. The first show both bounds are tight in a weak sense for general graphs in the sense that there exist examples matching the upper bound. They then provide a series of lower bounds based on four (successively stronger) standard convexity properties of the underlying graph $G$. Their final (and tightest) bound holds for graphs on which every two disjoint convex sets are halfspace separable. In this case the only gap between the upper and lower bounds is that between the Radon number and Tree-width of the graph. The authors also provide a number of reasonably natural classes on which their bounds are exactly tight, including trees, $K_{2,3}$ minor-free graphs, partial cubes, and weakly median graphs. \n\nFinally, the authors provide some experimental motivation for their setting, along with a number of heuristic implementations of their algorithm. They compare performance to two non-trivial baseline algorithms, the label propagation algorithm of Zhu et al. (2003), and the $S^2$ algorithm of Dasarathy et al. (2015), and show preliminary experimental evidence that their algorithm outperforms both.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Learning halfspaces is one of the most well-studied problems in machine learning theory. Learning halfspaces on graphs is an understudied variant of this problem, to which this work makes important theoretical contributions in the regime of worst-case analysis. Since learning on graphs is a common problem in practice, this work should be of broad interest both to theoreticians and practitioners. While the techniques themselves used in this work are fairly elementary, the observations are nonetheless novel, and draw interesting connections between standard characterizations of convexity, standard graph complexity parameters, and resulting query complexity lower bounds.\n\nOverall, the paper is well-written and seems technically sound, but could be improved with some discussion of the proofs outside of the appendix (perhaps replacing one of the many discussion sections, or some of the lengthy experimental discussion?). It would also be nice to see more motivation for the study of convex communities in real world graphs, since, while clearly at least related to the topic of study, these don’t seem to obviously lead to halfspace separable learning problems. \n\nA few minor notes for the authors:\n\n1. typos: propsed, conceptional\n\n2. “Same-cluster queries, which are binary queries on a pair of points to test whether they are in the same cluster, instead of vertex label queries” is not a full sentence.\n\nEdit: I thank the authors for their response and my review remains unchanged.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "bV4_zfxN37P", "reviewer": "Reviewer_mSJZ", "summary": "This paper studies the query complexity of learning geodesically convex halfspaces on graphs.  In the present context, a geodesically convex set of a graph $G = (V,E)$ is a subset $C$ of $V$ such that each shortest path containing any two vertices of $C$ is contained in $C$, and a halfspace of $G$ is any convex set of $G$ whose complement is also convex.  The main contributions are upper and lower bounds for the query complexity of a class of halfspaces on a weighted graph in terms of various graph parameters.  One upper and almost matching lower bound is given in terms of the size of the minimum shortest cover and the graph diameter.  Another upper bound is given in terms of the minimum size of a hull set, the graph diameter and the maximum size of a set $W_{=ab}^*$ of vertices over all pairs $(a,b)$ of vertices, where $W_{=ab}^*$ is defined to be the set of all points that avoid the intersection of rays from $a$ (resp. $b$) to any point neither in the convex hull of $a/b$ nor in that of $b/a$ and are themselves not in these convex hulls.  The size of the set $W_{=ab}^*$ can also be bounded in terms of the treewidth.  It is shown, moreover, that increasingly tighter lower bounds can be obtained as more stringent separation axioms are assumed.        \n", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I checked the proofs in the Supplementary up to and including Theorem 10; I think they are correct.  The remaining proofs also look convincing enough.  Overall, I think the results in the paper are correct. \n\nHowever, I am not familiar with the area so I cannot assess how novel the proof methods/conceptual ideas are.  It seems from the writing that the paper does not introduce any new proof techniques, so the focus seems to be mainly on the application of known results in metric graph theory and general convex structures to the problem of learning graph labels under a new assumption, namely that each class of labels forms a halfspace.  \n\nComments/suggestions:\n\n- Page 3, Lemma 4 and Supplementary, page 2, Lemma 4: I suggest phrasing Lemma 4 in the main text as well as the Supplementary as follows: Using $h(G) + \\lceil log d(G) \\rceil$ queries, we can either find a cut edge or determine that all vertices of the graph have the same label. \n\n\nMinor comments/suggestions:\n\n- Supplementary, page 1, line 19: change -> changes \n\n- Supplementary, page 4, line 103: $d$ -> $d(G)$\n\nEdit: I raised my score to 7 after reading the author(s)' explanations on the novelty of this work.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, I think so.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "16"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is an original work which proposes and explores a natural and elegant abstraction of convexity. The reviewers unanimously agreed to accept this paper.
Decision: Accept (Poster)