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 wwoomas.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-inteeaaeeeeee 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-rootti--iiiee irottiinintteaattion 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 inbleddndeenneett 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)) (AA). 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 (==
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 & AUB, 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. "..: 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 Q(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 [" 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 ((x, 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 httpsaaaahahaaaaaaaaehaa

---

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.
Hans-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-Peled, 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): 1305-1177,, 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-eeedtarryy 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": "zpChSpzpaC4", "reviewer": "Reviewer_q1b7", "summary": "The paper considers the problem of actively learning the (binary) labels of the vertices of a graph, under abstract convexity assumptions. The main results are upper bounds and lower bounds on the number of label queries needed, expressed as a function of various graph-theoretical quantities.\n", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "POST-DISCUSSION EDIT: After taking the authors' response to the technical discussion into careful consideration, I am raising my score to 5. Should the paper be accepted, I trust the authors to fix all presentation issues as thoroughly as possible.\n\n==========\n\nTLDR: I believe the formal results are good, but the paper needs a thorough rewriting before being accepted at a conference such as NeurIPS.\n\n------------------\n\nRelevance: the problem is relevant to active learning and thus to the NeurIPS audience.\n\nOriginality: the results are mostly original. However, two of them (Proposition 2 and Theorem 11) already appeared in a recent workshop (MLG 2020). In fact, Proposition 2 is identical to the main result of that paper. If the authors are the same as that paper, then this can be considered as bad practice; otherwise, it is clearly plagiarism, in which case the paper should be rejected.\n\nQuality: questionable, not in the results themselves, but in how they are (not) presented and explained. Essentially all results and bounds are given without an intuition, a proof sketch, or a guiding example; one cannot understand where the paper is heading to, or what it wants to achieve. For these reasons I could not perform any sanity check of the claims and techniques. There are also some inaccuracies; for instance, the definition of query complexity (the main object of study here) is not formal at all, being described just as \"the least number of queries required to identify any halfspace separable labelling in the worst-case\".\n\nClarity: low. There is no introduction to the problem, its motivations, and the state of the art. The first two pages are an avalanche of technical terms and notation, spanning abstract convex spaces, hulls, rays, separation axioms, and so on, but without any direction or guideline, and with most terms used before having defined them. The main results are stated in formal terms, without an explanation of their meaning, significance, and limitations. What type of inputs (input classes) are captured by the proposed notions of convexity? Aren't they captured by existing definitions? Do the upper bounds developed in this paper improve on existing ones? By how much, and in which cases? What is the main idea behind the algorithms? How does it differ from previous ideas?\n\nSignificance: hard to assess.\n\n\nDETAILED COMMENTS\n\n1. The very first page of the work (i.e., Section 1 \"Introduction\") is mostly obscure to me, despite the fact that I have expertise in active learning. The first paragraph starts abruptly by talking of abstract convexity spaces, geodesic convexity, hull sets. There is no indication of the field or the topic at hand (active learning on graphs), and not even a definition or introduction to the problem. The second paragraph talks about some separation axioms for graphs, of which I do not have the slightest idea, culminating in an observation that these axioms (which we do not know) hold in all linear spaces. This section certainly needs a total rewriting from scratch.\n\n2. Section 2 is equally frustrating. It introduces dozens of definitions and concepts in just one page, accompanied by almost no intuition or anticipation of their use. Some of the concepts are used without a definition (e.g., the concept of nested union). After reading this section I was very confused, as I do not know what are the central points that I should keep in mind.\n\n3. The result given by Proposition 2 is a corollary of Theorem 1 in a paper appeared at the MLG workshop 2020 (http://www.mlgworkshop.org).\n\n4. The meaning of the bounds is not clear. In particular, Corollary 7 says that the query complexity of labelling G is at most  h(G) + log d(G) + 2 tw(G). The last two terms are just the diameter and the treewidth and that's fine. My perplexity is in the first term, h(G), which is defined as the size of the smallest subset of V(G) whose convex hull coincides with V(G). Howe large is this quantity? Isn't it at least the sum of the shortest path covers of the two classes? Is it in fact coinciding with that quantity? In this case, for instance, the bound is interesting because it gives an additive (and thus better) version of Proposition 2. Without an explanation it is very hard to grasp what's going on here.\n\n5. The rest of Section 3 lacks intuition and explanation. It just enumerates a series of upper bounds and lower bounds, involving several different quantities (the number of extremal vertices of G, the shortest path cover of G, and so on).\n\n6. Theorem 11 seems again to come from the paper that I mentioned above.\n\n\nTitle: Either \"Active Learning OF ...\" or \"Actively Learning ...\", but not \"Active Learning ...\".\nL13, L30: \"active\" -> \"actively\", since it is an adverb to \"learning\"\nL42: \"tuple\" is just a pair\nL23: what is a nested union? I can't even find it on Google.\nL93: what does \"iterative vertex queries\" mean? Perhaps \"active\" or \"adaptive\"?\nL114: what is a \"fully connected graph\"? what are \"edges independent of each other\"?\nL118: what does it mean for the labels of two paths to be \"independent\"? Just that the two paths are edge-disjoint?\nL119: first it is said \"with edge length l\", which means that every edge has weight l, and then \"paths with l vertices each\"; this is confusing.\nL121: why are 1+log(kl) queries sufficient? I would say something like k log(l), with one binary search along each dimension.\nCorollary 7: the statement invokes H but the bound does not use it (since you already use h(G)).\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations are not clearly addressed. There is no foreseeable societal impact.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "b8g32ADV5aj", "reviewer": "Reviewer_1KsL", "summary": "This paper presents novel bounds on the query complexity of learning halfspaces on graphs\nvia convex analysis.\nTwo general upper-bounds were derived along with a simple general lower bound based on\nextreme vertices. Based on these bounds, the authors developed two querying strategies\nbased on greedy and selective sampling approaches.\nOne interesting practical aspect of the proposed active learning algorithm is the evidence\nthat ground-truth communities in real-world graphs are typically convex.\nThe proposed bounds are compared to previous results based on the cut-size,\nwhich show that the halfspace assumption enables learning with large cuts, whereas previous\nbounds become less applicable.", "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": "The paper is original and significant in the sense that it provides novel bounds on the query complexity\nof learning halfspaces on graphs, an outstanding, challenging task. The proposed query\nstrategies are require a considerably smaller number of queries than previous active learning\nstrategies on halfspace separable datasets. However, the O(n^3) computational complexity\nis indeed prohibitive.  On this sense, it would be interesting if the authors could point\nout more detailed directions on how they intend to alleviate this issue. On another\nside, it was helpful to see that the authors generally discussed how to adapt their bounds\nto weakly convex sets.\n\nOn the predictive performance experiment (Figure 2), it would be beneficial to\nsee confidence bands around the accuracy measurements. More precisely, given that the authors\nbypass the greedy maximization step for each query (due to computational complexity issues),\nand their strategy picks a vertex uniformly at random (as mentioned in line 3 of Algorithm 1), then\nI would like to see the accuracy measurements over different choices of such initial vertex.\nIn addition, for the Moons dataset you could generate the dataset with different noise levels\nand compute the average accuracy (and confidence bands) over those levels.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors reasonably mention expectations on the usage of their technique in reducing the number of labelled datapoints in graph-based learning settings.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "b5KT3ui5kK1", "reviewer": "Reviewer_8BJz", "summary": "The authors study the problem of  learning geodesically convex halfspaces on graphs within an active learning setting. They propose a new algorithm and rigorously analyzed it by showing lower and upper bounds of the query complexity. They also carry out an experimental evaluation to validate their theoretical results. ", "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": "This is an interesting theoretical paper. However, in order to be accepted, the authors should modify part of its structure. More precisely, in Section 1, the motivations for focussing on this problem are not explained in detail, so that they are not very convincing. While reading the first three sections, I had the feeling that the problem studied is not motivated enough. The motivations described instead in the first part of Section 4 (\"Convexity in real-world datasets\"), make this work very significant. Hence, I firmly believe that the first part of Section 4 should be moved to Section 1. \n\nAnother modification concerns the other parts of Section 4. The details of the in-depth comparisons with the related work cannot be understood unless the reader is entirely familiar with the related literature. There is no enough space in the main body for providing the additional details necessary to understand such an in-depth comparison. Hence, the rest of Section 4 (starting from \"Relationships to Euclidean convexity\") should be briefly summarized in a \"Related work\" subsection and moved at the end of Section 1. The details of the in-depth comparison present in Section 4 should instead be moved to the Appendix. \n\nFinally, another essential point to improve the clarity and readability of the paper is the need for figures to help to understand some concepts, e.g., extreme vertices, A/B, ray a/b, Radon number (and possibly also weakly median graphs, which may be completely unknown to most readers). It would be unusual to publish a paper on these topics without any figure in the main body illustrating these concepts. If there is enough space in the main body, additional figures could also show to what extent, for some significant input labeled graphs, we have a good match between lower and upper bound. \n\nBesides these suggestions to improve the paper, I think the article is fairly well written. \nIn light of the motivations described in the first part of Section 4, I believe that the paper contributions are significant in the area of active learning on graphs and other researchers are likely to use these results or build on them. These contributions support its publication. \nFrom a theoretical viewpoint, the paper is very interesting. The experimental evaluation is not exhaustive, but it is sufficient for this kind of article. \n\nA weakness of this work is the computational complexity of the proposed algorithm. It would be great to understand if one can obtain an approximation result with a trade-off between accuracy and time complexity using a randomized version of the proposed algorithm. It would also be interesting to quantify the results of running the algorithm on inputs where the assumptions are only slightly violated. About real-world dataset convexity, it would be significant to define some meaningful function measuring to what extent an input network is convex, to provide more information about the real-world datasets considered in this paper. \n\n\n\nThere is a (minor) point that is not completely clear to me about the notion of rays for graphs (I guess I am missing something trivial here). Given an edge {a, b} in a weighted graph, we have that a/b = {v\\in V | d(b,v) = d(b,a)+d(a,v)}. Why for unweighted graphs do we have the condition d(a,v) < d(b,v) instead of d(b,v) = d(b,a)+d(a,v) = 1+d(a,v)?\n\nA minor comment concerns how the authors express the satisfaction of the four axioms. Personally, I would avoid writing \"A convexity space (X, C) **is** S_k\", where S_k is a (separation) axiom (with k\\in\\{1, 2, 3, 4\\}). I would instead prefer to rephrase such a sentence by writing, \"A convexity space (X, C) **satisfies** S_k.\" Furthermore, for these axioms, I would use another font type different from the one used to define sets., e.g., \\mathcal{S}_k. \n\n\nTypos: \n\n\"furture\" -> \"future\", \n\"additioanally\" -> \"additionally\", \n\"is always V/2\" -> \"is always |V|/2\"\n\n\n---AFTER REBUTTAL---\n\nI recommend acceptance on the condition that you also add the main content of the last two authors' answers to the camera-ready version.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": " The authors adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"ethical_concerns": "There are no ethical issues with this paper.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12"}, "extra_text": {}}, {"review_id": "BjQ0Jm3_JTV", "reviewer": "Reviewer_SPWf", "summary": "This paper considers the problem of learning labels on graphs, assuming the true separator is convex. It gives an algorithm for labeling the entire graph while attempting to minimize the number of queried vertices, and also gives lower-bounds which depend on graph properties.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "In convexity theory, a straightforward analogue to Euclidean convexity exists for graphs as well, and this analogue extends to the notions of convex hull and halfspaces. This paper considers exact active learning for halfspaces on graphs, and so it attempts to discover all graph labels under the assumption of halfspace separability. This extends the familiar notion of learning halfspaces to the settings of graphs. \n\nThe work suggests a couple of learning algorithms, which are algorithmically relatively straightforward. The first algorithm has dependence on the size of the shortest-paths cover and graph diameter, and can be implemented by a standard greedy algorithm. The second features dependence on the diameter, hull size and another term which can be bounded, for example, by the treewidh of the graph. The runtimes of these algorithms are particularly high, as one might expect for graph algorithms, though it would be nice if the authors are able to reduce these (in particular, the O(|V|^4 runtime of theorem 11).\n\nComplementing these algorithm are tight lower-bounds based on previously studied graph properties; these are related to the separation of induced geodesic convexity spaces of the graphs. Lower-bounds are expressed in terms of the Radon number, or the size of the hull or extremal point set of the graph.\n\nAlthough one could find faults with the paper (high running times, lower-bounds not exactly matching the algorithmic upper-bounds), I find that this paper is a good introduction to a new and natural learning problem.", "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": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The majority of reviewers argue that this paper should be accepted.  The main concerns were presentation issues as well as sufficient discussion of computational complexity wrt polynomial-time approximations of the algorithmic steps.  

Per the authors' comments in discussion it is suggested: that the presentation should be improved and the additional examples from discussion should be incorporated in the next  revision for NeuRIPS.  Non-exclusively this should include elaboration in Sections 1 & 2, illustrative figure(s) and examples.  Lastly a fuller discussion of graphs (realworld) classes (such as bounded treewidth graphs) for which the we have guarantees that can be achieved in poly-time and discussion how the approximation steps affect the guarantees.
Decision: Accept (Poster)