Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper proposes methods to construct 2-hop spanners to approximate similarity graph in extremely large data. The idea is to use  hashing functions to reduce the neighborhood searching load.  
strengths_and_weaknesses: I think the paper can be a significant contribution to the problem of similarity graph construction via using 2-hop spanners, which increase the sparsity of the graphs. 

I could not check the maths in detail to approve the analysis. 

What the paper's missing is to validate the benefit of 2-hop spanners compared to a similarity graphs as the two-hop spanners contain a similarity graph with higher threshold. 

The paper has typos in many places. 
questions: What is the benefit of 2-hop spanners compared to a similarity graph of: the same threshold (r_1), and larger threshold (somewhere between r_1 and r_2)? 
limitations: N/A
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This work proposes an algorithm for efficiently constructing similarity graphs for extremely large graphs. This work introduces the idea of using two-hop spanners (derived from concept of metric spanners), in which all points with similarity greater than some threshold are guaranteed to be less than or equal to 2 hops apart, and no edge with some small similarity level have an edge between them. With the relaxed goal of similar points being within two hops as opposed to one, the algorithm is able to make significant gains in overall efficiency. They give an algorithm for constructing the two-hop spanner threshold graph using Locality Sensitive Hashing (LSH) as well as an algorithm using Sorted LSH for approximating K-nearest neighbors. They give algorithms and theoretical guarantees that their algorithm approximates nearest neighbors using angle or jaccard similarity measures, as well as theoretical guarantees on efficiency. 

They confirm the theoretical results with experiments on a combination of real and synthetic datasets. The experiments include results on the number of comparisons made for various algorithms, how close the number of sketches hyperparameter affects approximation to KNN in terms of recall, as well as the coverage of the approximation. There is also an experiment showing the performance on clustering of various versions of the algorithm and the all-pairs baseline. 
strengths_and_weaknesses: Originality:

++ Somewhat original. Builds off techniques from previous similarity clustering algorithms as well as using techniques of locality sensitive hashing and two-hop spanners. 

-- Not clear to me how this compares to other approximate K nearest neighbor and similarity graph construction algorithms

e.g.

Eiras-Franco, Carlos et al. “Fast Distributed kNN Graph Construction Using Auto-tuned Locality-sensitive Hashing.” ACM Transactions on Intelligent Systems and Technology (TIST) 11 (2020): 1 - 18.

Zhang, Yanming et al. “Fast kNN Graph Construction with Locality Sensitive Hashing.” ECML/PKDD (2013).

Wang, G. et al. “Learning to Prune: General and Efficient Approximate Nearest Neighbor Search with Direction Navigating Graph.” 2022 the 5th International Conference on Data Storage and Data Engineering (2022): n. pag.

Quality:

++ This is a complete, high quality work. 

++ While I have not confirmed all the proofs in the appendix, the theorems seem to be soundly derived. 

++ The experiments show the effectiveness of the algorithm in terms of efficiency and approximation. 

-- It would be nice to have some more experiments showing the usefulness on downstream tasks. 

-- Also, no comparisons to similar works.

Clarity:

++ While math heavy, the paper remains clear. As a nice benefit, the paper would still read pretty clearly even for a light read as many readers might be doing. 

Significance:

++ It seems like this would be of interest to some readers. It seems certainly on the application side this would be of interest. 

-- It would be nice to have more examples of downstream use cases. The clustering experiment is helpful in that regard but not super clear-cut. It is 


Spelling/Gramar:

line 172: twp-hop -> two-hop
questions: 1) Can the related work be improved to show how does this method compares to the most similar other LSH-based/approximate KNN and similarity graph construction algorithms? 

2) Have you made any comparisons of theoretical guarantees and/or experimental results against other fast clustering/nearest neighbor algorithms?
limitations: Adequately done.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper studies the similarity graph construction problem which is useful for downstream tasks such as clustering and graph learning. It proposes a scheme named Stars to construct two-hop spanners as a relaxation of the similarity graph by selecting leader points and generate star-shape edges. It claims it is superior because it requires at most $O(n^{1+O(\epsilon)})$ complexity in construction and the output two-hop spanners are sparser than normal similarity graphs.
strengths_and_weaknesses: Strengths:

S1. This paper investigates a novel problem for graph construction on two-hop spanner graphs. It claims this type of graph has fewer edges and is hence more favorable for downstream tasks on large-scale data. It is of certain interest for the research in building sparse graphs from similarity representation, especially for large-scale data and distributed computation.

S2. This paper proposes a simple yet effective scheme Stars which can efficiently generate two-hop spanners based on similarity measures, i.e. Locality Sensitive Hash (LSH) Families. It provides theoretical analysis to show that Stars can construct approximate near neighbor (ANN) graphs under given error guarantees, and gives the time complexity bound.

Weaknesses:

W1. Given that two-hop spanner is a generalized type of similarity graphs, it is natural that algorithms designed on this graph type have better complexity than baselines. So whether the performance improvement comes from the Stars algorithm itself or is the merit of the graph relaxation is unclear. It is also not presented in the paper whether the difference in similarity graphs will result in performance drop in downstream tasks such as clustering (see Q1).

W2. As $\epsilon$ ranges from 0 to 1, I doubt whether the $O(n^{1+O(\epsilon)})$ complexity can be described as "nearly-linear". In the paper, it claims that the empirical time is significantly better than the theoretical bound, but this is not well explained (see Q3).

W3. For both theoretical and experimental evaluations, there are insufficient baselines included in this paper.

W3.1. For theoretical complexity analysis, it only presents the complexity of Stars without comparison to other approaches.

W3.2. For the graph construction experiment, it only compares brute force (all-pairs) and a non-Stars algorithm. What exactly is the "non-Stars algorithm" is unknown. Similar works like [21] or [R1] are also not evaluated.

W3.3. For the clustering experiment, there should be even more available baselines. I think it is even necessary to compare with non-LSH-based and non-similarity-based approaches.

W4. The experiment designs are still too simple beside the baseline issue. Sec 5 Empirical Study lacks critical information and is poorly written.

W4.1. It mainly evaluates the algorithm by changing the parameter $R$ of number of sketches. However, only having three points R = 25, 100, 400 is not enough. It is hard to observe the relation between complexity (num comparisons, num edges) and sketches.

W4.2. As complexity improvement is an important contribution in the paper, there should be experiments and analyses explicitly studying that. The evaluation of complexity on different scales of data is expected, rather than solely on two points of 1B and 10B data.

W4.3. Section 5 lacks necessary analysis and conclusion for experiments. For example in Fig 2, what is the meaning of the "recall" metric? Why the performance of "LSH exact" is different from others on MNIST? In Fig 4 Amazon2m, why "lsh+stars-learn" and "sortinglsh+stars-learn" seem to have lower performance than non-Stars methods?

Minor issues:
I1. Line 125 sentitive -> sensitive.

I2. Line 297-305, whether Random1B/Random10B dataset names are capitalized needs to be aligned.

I3. The log y axes in some figures (e.g. Fig 1 wikipedia, Fig 3 MNIST) are too rough to assess the results. Some data points (Fig 1 allpair, Fig 2 LSH+Stars exact, Fig 3 lsh+stars-relaxed) are hard to observe.

[R1] Zhang, Yan-Ming, et al. "Fast kNN graph construction with locality sensitive hashing." Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer, Berlin, Heidelberg, 2013.

questions: Q1. In two-hop spanners, similar points are two-hop neighbors, is that true reversely? That in Definition 2.4, for every $p \in N_2(q)$, is it guaranteed $\mu(p,q) \lq r_2$? If not, what is the impact on downstream tasks of introducing additional neighbors that are not similar?

Q2. What are the requirements (theoretical assumptions) for the LSH family $H$ in Theorem 3.4, especially for the sorting LSH technique? When migrating from the (r1 , r2 , rho)-sensitive families to (r1 , r2 , p1 , p2 )-sensitive families, are there any differences in theoretical and empirical performance?

Q3. Line 67 says Stars "construct significantly fewer than the O(n^1.99)-edges suggested by our theoretical guarantees." How is this presented in the experiments? Additionally, is this statement true for all scales of graphs, for example, small-scale graphs?

Q4. In Sec 5 "Sketching parameters" and "Clustering" tasks, how to determine which similarity / LSH is used for each dataset? Is there a general criterion for choosing similarity / LSH?

Q5. As stated in W4.3.
limitations: See W1 to W4.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: Given a set of points X endowed with a measure of pairwise similarity, a similarity graph G(X,E) on X is supposed, loosely speaking, to draw edges between similar points and avoid edges between dissimilar points. Common variants define that a pair of points x,y should be neighbors if their similarity is above a fixed threshold, or if y is among the k most similar points to y for some fixed k. These graphs are commonly used in many applications. The computational challenges they pose are (a) that constructing them can be very costly, especially for very large datasets where exact construction is infeasible, and (b) that they need to be reasonably sparse since this affects their usability in the downstreams applications they are constructed for.

This paper advocates constructing these graphs such that similar points are not necessarily connected by an edge, but with a path of length 2. This addresses challenge (b) since this relaxed requirement allows the graph to be more sparse, and addresses challenge (a) since it lends itself to a very simple construction: bucketing the points in a way that roughly preserves similarity (there is a vast literature on efficiently generating such bucketing for large high-dimensional point sets, notably, by LSH), and then choosing a representative point from each bucket, and drawing an edge between the representative and the other point in the bucket (i.e., putting a star graph on the bucket). The algorithms in this paper repeat this with several random partitions to generate the similarity graph.

This approach to constructing similarity-preserving graphs has been suggested and studied before, but this paper applies it more specifically in the context of near-neighbor preserving graph construction, shows it can be implemented in practice on a very large scale, and includes an empirical evaluation. This adds a different angle to the existing literature (previous work that I am aware of has been strictly theoretical and focused on other flavors of similarity preserving graph).


strengths_and_weaknesses: This is a good quality paper that seems to me like a solid contribution to the literature on large-scale NNS graph construction, is written well and clearly (up to some technical points noted below), and to me clears the bar for acceptance. The analytic novelty is perhaps not on the higher side, as the analysis directly utilizes classical and existing LSH techniques. However, the application to similarity graphs -- especially in practice and in demonstrably large scale -- is interesting and significant, and well-executed in this paper. This may advance the way we use LSH in large-scale settings and impact the way we construct large-scale similarity graphs. There is perhaps some room for more discussion and exploration of the usability and limitations of this approach, see "questions" below.

The technical writing could be more careful, with some undefined (on not clearly defined) notation and some lax writing in parts of the proofs (though there is no concern about correctness). These glitches can be corrected from context or if one is already familiar with the background literature, but may still impede readability for newcomers, which is a bit unfortunate since the paper is otherwise very well written. For example:
- tau_k(p) not explicitly defined (is line 199 supposed to be implicitly defining it as the similarity to the kth most similar point?)
- Incompatible neighborhood notation between lines 149 and 261
- The proof of proposition 3.3 makes use of properties of Simhash and Minhash that are never stated or referenced (the connection between the collision probability to the similarity)

and some more. I cannot list all of these but making the technical parts clearer and self-contained would likely help make the paper accessible to a wider audience.

Small corrections:
1. missing subscripts on the pi's in line 220
2. Did you mean d(p,q) instead of mu(p,q) on line 251
questions: The paper is perhaps missing some discussion on what we lose when we allow similar points to be connected by a 2-hop path instead of an edge. What downstreams tasks is it suitable for, and are there downsteams tasks for which it is less suitable, or perhaps requires possibly costly modifications to those tasks (for example, replacing the greedy traversal used in graph-based NNS with 2-hop lookahead traversal). These questions come up naturally from the approach suggested in the paper, though I am generally content with largely leaving them for future work.

Another question is about guarantees for dissimilar points. The constructions in the paper ensure that each point is likely to have sufficiently many similar points in its 2-hop neighborhood, and the first construction also ensures that adjacent points (i.e., 1-hop away) are at least somewhat similar, but in neither construction I am not sure if there is a guarantee that dissimilar points are mostly disincluded in the 2-hop neighborhood. There is a sparsity guarantee on the total number of edges, which means that things are okay on average, but there could still be particular points where the 2-hop neighborhood contains many irrelevant point along with the near neighbors, which could cause latency issues (long runtime for specific queries) if these nodes participate in the downstream query (for example if they are visited in a traversal), if I am understanding this correctly.

limitations: N/A
review_title: null

Meta-review: metareview: All reviews for this paper were positive, albeit with a varying level of enthusiasm. Reviewers found the problem (large scale similarity search) to be important, and the authors contribution to it (faster search using 2-hops search graph constructed via  LSH) significant. There were some concerns about the baselines in experimental evaluation, and some (relatively minor) presentation issues. Ultimately, the positives significantly outweighed the negatives.
confidence: Certain
Decision: Accept