Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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.
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. 

The 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).

Complementing 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.

Although 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.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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. 
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. 

Another 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. 

Finally, 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. 

Besides these suggestions to improve the paper, I think the article is fairly well written. 
In 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. 
From a theoretical viewpoint, the paper is very interesting. The experimental evaluation is not exhaustive, but it is sufficient for this kind of article. 

A 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. 



There 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)?

A 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. 


Typos: 

"furture" -> "future", 
"additioanally" -> "additionally", 
"is always V/2" -> "is always |V|/2"


---AFTER REBUTTAL---

I recommend acceptance on the condition that you also add the main content of the last two authors' answers to the camera-ready version.


limitations_and_societal_impact:  The authors adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper presents novel bounds on the query complexity of learning halfspaces on graphs
via convex analysis.
Two general upper-bounds were derived along with a simple general lower bound based on
extreme vertices. Based on these bounds, the authors developed two querying strategies
based on greedy and selective sampling approaches.
One interesting practical aspect of the proposed active learning algorithm is the evidence
that ground-truth communities in real-world graphs are typically convex.
The proposed bounds are compared to previous results based on the cut-size,
which show that the halfspace assumption enables learning with large cuts, whereas previous
bounds become less applicable.
main_review: The paper is original and significant in the sense that it provides novel bounds on the query complexity
of learning halfspaces on graphs, an outstanding, challenging task. The proposed query
strategies are require a considerably smaller number of queries than previous active learning
strategies on halfspace separable datasets. However, the O(n^3) computational complexity
is indeed prohibitive.  On this sense, it would be interesting if the authors could point
out more detailed directions on how they intend to alleviate this issue. On another
side, it was helpful to see that the authors generally discussed how to adapt their bounds
to weakly convex sets.

On the predictive performance experiment (Figure 2), it would be beneficial to
see confidence bands around the accuracy measurements. More precisely, given that the authors
bypass the greedy maximization step for each query (due to computational complexity issues),
and their strategy picks a vertex uniformly at random (as mentioned in line 3 of Algorithm 1), then
I would like to see the accuracy measurements over different choices of such initial vertex.
In addition, for the Moons dataset you could generate the dataset with different noise levels
and compute the average accuracy (and confidence bands) over those levels.
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_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.

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.

==========

TLDR: I believe the formal results are good, but the paper needs a thorough rewriting before being accepted at a conference such as NeurIPS.

------------------

Relevance: the problem is relevant to active learning and thus to the NeurIPS audience.

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

Quality: 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".

Clarity: 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?

Significance: hard to assess.


DETAILED COMMENTS

1. 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.

2. 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.

3. 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).

4. 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.

5. 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).

6. Theorem 11 seems again to come from the paper that I mentioned above.


Title: Either "Active Learning OF ..." or "Actively Learning ...", but not "Active Learning ...".
L13, L30: "active" -> "actively", since it is an adverb to "learning"
L42: "tuple" is just a pair
L23: what is a nested union? I can't even find it on Google.
L93: what does "iterative vertex queries" mean? Perhaps "active" or "adaptive"?
L114: what is a "fully connected graph"? what are "edges independent of each other"?
L118: what does it mean for the labels of two paths to be "independent"? Just that the two paths are edge-disjoint?
L119: 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.
L121: why are 1+log(kl) queries sufficient? I would say something like k log(l), with one binary search along each dimension.
Corollary 7: the statement invokes H but the bound does not use it (since you already use h(G)).


limitations_and_societal_impact: The limitations are not clearly addressed. There is no foreseeable societal impact.
review_title: null

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)