Stars: Tera-Scale Graph Building for Clustering and Learning
Authors: CJ Carey
Jonathan Halcrow
Rajesh Jayaram
Vahab Mirrokni
Warren Schudy
Peilin Zhong
Venue: NeurIPS 2022 Accept (2022)
Keywords: Graph Building
Clustering
Nearest Neighbor Search
Locality Sensitive Hashing

Abstract: A fundamental procedure in the analysis of massive datasets is the construction of similarity graphs. Such graphs play a key role for many downstream tasks, including clustering, classification, graph learning, and nearest neighbor search. For these tasks, it is critical to build graphs which are sparse yet still representative of the underlying data. The benefits of sparsity are twofold: firstly, constructing dense graphs is infeasible in practice for large datasets, and secondly, the runtime of downstream tasks is directly influenced by the sparsity of the similarity graph. In this work, we present Stars: a highly scalable method for building extremely sparse graphs via two-hop spanners, which are graphs where similar points are connected by a path of length at most two. Stars can construct two-hop spanners with significantly fewer similarity comparisons, which are a major bottleneck for learning based models where comparisons are expensive to evaluate. Theoretically, we demonstrate that Stars builds a graph in nearly-linear time, where approximate nearest neighbors are contained within two-hop neighborhoods. In practice, we have deployed Stars for multiple data sets allowing for graph building at the Tera-Scale, i.e., for graphs with hundreds of billions of nodes and tens of trillions of edges. We evaluate the performance of Stars for clustering and graph learning, and demonstrate 10~1000-fold improvements in pairwise similarity comparisons and significant running time speedups with negligible quality loss. 

Stars: Tera-Scale Graph Building for Clustering and Graph Learning
CJ Carey Google Research cj jjaaey@google.comm com
Jonathan Halerow Google Research halcrow@google.co com
Rajesh Jayaram Google Research rkj ayaram@google..om com
Vahab Mirrokni
Warren Schudy Google Research
Peilin Zhong Google Research pei peilinz@google.com com
Google Research
mirrokni@google.comm com
wachudy@google.com com
Abstract
A fundamental procedure in the analysis of massive datasets is the construction of similarity graphs. Such graphs play a key role for many downstream tasks, including clustering, classification, graph learning, and nearest neighbor search. For these tasks, it is critical to build graphs which are sparse yet still representative of the underlying data. The benefits of sparsity are twofold: firstly, constructing dense graphs is infeasible in practice for large datasets, and secondly, the runtime downstream tasks directly influenced by the sparsity of the similarity graph. In this work, we present Stars: highly scalable method for building extremely sparse graphs via two-hop spanners, which are graphs where similar points are connected by a path of length most two. Stars can construct two-hop spanners with significantly fewer similarity comparisons, which are a major bottleneck for learning based models where comparisons we demonstrate that Stars builds a graph in nearly- time, where approximate nearest neighbors are contained within two-hop neighborhoods. In practice, have deployed Stars for multiple data sets allowing for graph building at the Tera- Scale, i.e., for graphs with tens of trillions of edges. We evaluate the performance of Stars for clustering and graph learning, and demonstrate 10- 10-0000-fold improve- ments in pairwise similarity comparisons compared different baselines, and 2- 10-fold improvement in running time without quality loss.
expensive evaluate. Theoretically,
Introduction
Given a collection of unlabeled data, a critical technique in many data mining and machine learning pipelines is the construction of similarity graph over the data. Similarity graphs provide sparse representation of the underlying structure of a dataset by creating edges between the most similar data points. This allows downstream analytic procedures by restricting comparisons to edges the graph. In particular, many such procedures, such as Hierarchical Agglomerative Clustering (HAC) and variants [17, 5, 1], can be run in time nearly-linear in the number edges.
run more efficiently over the data
In order to be useful part of a larger pipeline, graph building itself must be an extremely efficient procedure. Namely, the time required to construct the graph exceeds the size of the graph itself, then graph building may become the primary bottleneck of the pipeline. To avoid this scenario, graph building algorithms must circumvent all-pairs comparisons by employing selective filtering methods, such locality sensitive hashing (LSH). However, with the extraordinary scale of modemn datasets, LSH alone is often no longer sufficient to ensure efficiency. Such methods still require an all all-pairs
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

comparison within each hash bucket, which is infeasible for the bucket sizes produced by LSH on large datasets. This not deficit of LSH specifically, but is rather an intrinsic dilemma of scale: even ground truth similarity graphs, such as threshold graphs and k-nearest neighbor graphs, would have too many edges to construct efficiently. Instead, graph building at scale requires expanding our conceptions of similarity graphs.
In this work we go beyond the standard model of similarity graph, introducing Stars, a novel graph building framework for constructing extremely sparse yet high-quality similarity graphs, based on the construction of two-hop spanners. Unlike a classical similarity graph, two-hop spanners relax the constraint that similar points should be connected by an edge, instead requiring that such points be connected by path of length at most two. This allows for considerable improvements in sparsity, scaling up to tens of trillions of edges, with negligible loss in quality for downstream applications.
Stars employs specialized locality sensitive hashing technique bucket points, and then constructs a collection of star graphs within each bucket. By creating star graphs, we significantly reduce the number of pairwise comparisons required to process bucket from quadratic nearly-linear in the bucket size. In practice, this results in significant (e.g. 10-20 fold) reduction in the number of comparisons made when compared to LSH alone. This reduction yields tremendous speedups for graph construction, especially for similarity measures derived from learned models, such as pre-trained deep neural networks, which are expensive evaluate. For such learning- cearning-based models, similarity computations constitute a majority of the overall runtime, therefore reducing the number of comparisons has enormous performance benefits.
We formally introduce Stars in Section 3, and prove theoretical guarantees on its performance for similarity measures such as cosine and Jaccard similarity. For these measures, we prove that Stars can construct two-hop spanners which capture the 1/e-approximate k-nearest neighbors, for any value of k, in time at most O(n!+(())) for any approximation factor (1/e) 2 1. Additionally, we demonstrate a variant of Stars which, given a threshold r. constructs a two-hop spanner such that all points with similarity larger than r are connected by path of length at most 2, and no edge connects two points with similarity less than er. We demonstrate that such two-hop spanners also approximately preserve connected components, allowing for a 2-approximation of single-linkage clustering (Theorem 2.5).
We discuss implementation and design details in Section 4. We then provide an empirical evaluation of Stars in Section 5, where we demonstrate that Stars performs significantly better in practice than even the theoretical bounds suggest. Specifically, in our experiments we set e = .99, and demonstrate that Stars recovers -aprooxiie nearest neighbors, as well as yields to threshold similarity graphs, all while constructing significantly fewer than the O(n! Pin!-99-eddes (especially for large datasets) suggested by our theoretical guarantees. In particular, Stars yields 10-20 fold and 2-10 fold improvements in number of comparisons and runtime respectively, e.g., from 120 trillion to trillion comparisons, when compared to baseline LSH.. The improvement is certainly much larger (at least 1000-fold) compared to the bruteforce (all-pairs) algorithm. Importantly, these runtime improvements do not negatively impact on the quality of downstream tasks, such as hierarchical clustering. The speedups become even more significant as we employ more sophisticated similarity learning models; moreover, better similarity learning models further improve the quality of the graph.
1.1 Related Work
Graph Building and Nearest Neighbor Search. The construction of similarity graphs, such as the k-nearest neighbor graph, is a key step for many established machine learning and data mining methods [10, 40, 11]. To efficiently compute approximate nearest neighbors, Locality Sensitive Hashing (LSH) based methods [22] and their data-dependent counterparts [4, 29, 3] have proven tremendously successful. In addition to LSH, other techniques such tree-based data structures [32, 31, 8). quantization approaches [24], and learning based methods [19], have also been utilized.
However, the majority of these methods were designed for quickly answering nearest neighbor search queries with a large dataset and a (generally) smaller number of queries, whereas in graph building the query set and the dataset are the same. This scenario allows for an additional set of techniques and optimizations to be employed, such as local search [18], and the construction of two-hop spanners (as in this work). Perhaps the most similar work to ours is [25], which builds large-scale graphs over

---

learned similarity models. In fact, our current results demonstrate that graphs with quality comparable to those [25] can be constructed with substantially fewer edges via two-hop spanners.
Large Scale Graph Clustering Other than nearest neighbor search, one of the primary downstream analytic tasks run on similarity graphs is clustering. One of the best studied class of such algorithms is hierarchical agglomerative clustering (HAC), which has been analyzed extensively from both theoretical and practical perspective [16, 33, 23, 38]. For graph-based HAC, it was recently shown that an approximate clustering can be obtained for average linkage in nearly linear time [17]. Previously, this was also shown for Euclidean space using Ward's s linkage [1]. Several works also give sub-quadee -uaddrudatiic HAC algorithms, but sacrifice theoretical guarantees (such as approximation ratio) [15]. Finally, related hierarchical clustering algorithm the MST-based clustering algorithm Affinity [5], a highly-scalabe method which we also use for evaluating our two-hop spanners.
Two-Hop Spanners. The concept of a two-hop spanner stems from the literature on metric spanners (see the surveys [21, 41, 2I). which are sparsifications of a graph with the property that distances in specifier well approximate distances in the original graph. Note that a two-hop spanner itself satisfies this property. The first usage of two-hop spanners can be attributed to [27]. who demonstrated the existence of sparse two-hop spanners for Euclidean space with the & metric. Two-hop spanners have also been implicitly studied in the context of min-size clustering in the MPC model [20].
2 Preliminaries
Let P be any set of points, and let μu p2 - be either a similarity or a distance measure over P. For the remainder, we choose to focus only on similarity measures for clarity of presentation. However, we remark that the techniques we present generalize naturally to distance measures by employing the appropriate locality sensitive hash functions for those measures (see definitions below).
We consider several types of similarity measures in the paper, including the dot-product similarity ju(,, y) = (xr y) between points x, y E Rdd, and the cosine similarity p( y) = cos(O2.g). where Oz, the angle between the vectors x, y. Additionally, we consider the Jaccard similarity between sets: p(A, B3 = A U / A B), where A, B C U for some universe 24, and the weighted Jaccard similarity between non -egaatiee vectors x, y. given by by μ(z,)) y) = min(s...:))
E, max( Finally, we use learned similarity measures μ which are computed by pre-trained model, such as deep neural network, and may be expensive to evaluate.
j-Nearest Neighbors. Given (P, μ1) where n = PP. for any p E we define the nearest neighbor ordering Tp in] + P as any bijection which satisfies u(p, TTp()) 2 ,u(,, (p()) > up, Tp (n)). We write (p) = p(p, (i)) to denote the similarity to the i-th nearest neighbor, and we denote the set of č-nearest neighbors via (p) (1p(1,, ... (i)))
Locality Sensitive Hash Families. We now introduce the notion of locality sensitive hash (LSH) family H. for similarity measures. Given a similarity measure μ over point set P, an LSH fam- ily H is a family of hash functions h P - U, for some universe U, with the property that Pr (h(p)= = h(q)] is larger when the points p, q are more similar, namely when p(p. 9) is large. For ease of presentation, we use a simplified parameterization of LSH families, as opposed to the more standard parameterization of (r1, P1, P2) pse-senstt families (see, e.g. [26]).
Definition 2.1 ((11, F2, p)-seniitive Family) Fix any parameters P1 < E and p E [0, 1]. Let P be any point set with similarity measure μ _2 > R, and fix a universe of buckets U. Then a family H. of hash functions h : P + U is said to be (ri, -e-ssitiveee locality sensitive hash family for (P, p) if the following holds: for any E P, vfp 4) > r2, then Pri- (h(p) = h((4) 2 nTp, and if p(p,g) q) < Tı then Pra-H (h(p) h(g)) <n-
Graph Building and Similarity Graphs. In this work, we consider two distinct notions of similarity graphs, which are appropriate in different contexts based on the application. The first notion is that of an r-threshold graph, which uniformly connects points with similarity above given threshold.
Definition 2.2 (r-threshold graph) Given a point set P, similarity measure μb, and a threshold r, the r-threshold graph for (P,
(P, u) is the graph G EP,E) where E [(z,8) P u(x, y) 2 r).
3

---

The r-threshold graph for (p) is useful similarity graph when downstream tasks impose a uniform threshold on when points should be connected. For instance. clustering with the constraint that pairs of points within a cluster have similarity above a threshold r. On the other hand, from the perspective of nearest neighbor search, one would like edges to be created non- con-uniformly, where a point p is connected to its k closest neighbors. Formally:
Definition 2.3 (k-near neighbor graph (k-NN graph)) Given a set of n points P and similarity measure μ.. let Tp PP + [n] be a nearest neighbor ordering over P. Then the k-nearest neighbor graph (P. is the graph G = (P, E) where E = uper(p) 9) q E (p()))-
Two-Hop Spanners. A two-hop spanner is similarity graph which relaxes the guarantees of the prior two notions of similarity graphs, where similar points are only required to be connected by path of length 2, rather than by a direct edge. The advantage of such spanners is that they can be considerably sparser than the associated similarity graph, and still produce high-quality results for downstream tasks (such as clustering). For any graph G (V, E), V E V, and integer k 2 1, we write (p) to denote the k-hop neighborhood of p. namely, the set of vertices E V which are at (unweighted) shortest-path distance most & from in G. The following definition captures the generalization of r-threshold graphs from one-hop to two-hop neighborhoods.
Definition 2.4 (Threshold Two-Hop Spanners) Given a point set P and similarity measure μt, a (T1, -twohhp spanner is graph G EP, such that: (1) for every edge (p.q) E. we have p(p.9) q) 2 TI, and (2) for every pair p. g E P with u(p, q) 2 T2, we have E N2(9)-
The above notion of two hop-spanners provide good (two-hop) approximation of the r-threshold graph for a point set. The approximation is controlled by the gap between 71, 12. In Section 3.1, we give provable guarantees for Stars, by demonstrating that it constructs two-hop spanners where this gap is small. In Section 3.2, we define an analogous notion of two-hop spanners for approximation the k-nearest neighbor graph, and prove that Stars efficiently constructs such approximation for k-nearest neighbors as well.
Two-hop spanners can be used powerful approximation of the underlying similarity structure of dataset. For instance, we demonstrate that two-hop spanners can be utilized to obtain an approximation to the optimal k-single linkage clustering solution, which is to partition P into & clusters Ci...., ......,C,, Ck so as to minimize max;şj maxpeC1.9EC; ()
Theorem 2.5 Let
1 and r <. OPTs/c, where OPTs is optimal cost of k-single-linkage clustering on (P,p). Then any (r/c.r)-2-hop spanner G has at least k connected components. Furthermore, for any two connected components C, C" of G, min p(x,)) v) 2 r. Thus, by
constructing log maxx p(s.y) distinct (r-hop)-2-hop spanner for geometrically increasing r.
miizz.er ((a.y)
one obtains a 2-approximattin to k-singleelinkage clustering.
3 Graph Building via Two-Hop Spanners
In this section, we theoretically analyze the performance of the Stars algorithm, by demonstrating that it efficiently constructs highly-sparse two-hop spanners. We describe two variants of Stars, in Sections 3.1 and 3.2 respectively. The first can be used to approximate the r-threshold similarity graph, and the second can be used to approximate the k-nearest neighbor graph.
3.1 Two-Hop Spanners via Locality Sensitive Hashing
We first describe the Stars algorithm for constructing two-hop spanner for approximating r-similarity threshold graph for point set P and similarity measure μ. Specifically, given a locality sensitive hash family H for (P, μ). Stars proceeds by bucketing points via a randomly drawn hash function H. Within each bucket, Stars samples a random "leader" p, and then connects together all points in the bucket to which are sufficiently similar to p, effectively creating a star graph centered at p. The process is repeated with R independent sketches, to ensure that all sufficiently similar points land in the same bucket at least once. The formal algorithm is given in the algorithm Stars 1.
Theorem 3.1 Let P be a point set equipped with a similarity measure μ. and fix any Ii <r2 E TR. Let H. P U be (F1,T2,P p) family of hash functions, such that each h E H can be evaluated

---

Stars 1: Constructing Approximate Threshold Graphs
Input: Point set P, similarity measure μı, and (r1, p)) hash family H.
Repeat: the following procedure R = ci log times, for sufficiently large constant c1
1. Evaluate h(p) for each p E P, and construct the buckets B, {p E P h(p) u).
2. For each bucket Bu, where u E U:
Sample a uniformly random leader x ~ Ba.
For all E B, \. fx), if p(z, v) > r1, then create an edge (x, y) with weight u(a,y).
in time at most Ti) Let (P, be the graph produced by the algorithm Stars 1, using the LSH family H. Then with probability 1 -.). G is a (rı, T2)-two-hop spanner for (P, p.). Moreover, the number of edges produced is at most [F(G] O( and the runtime of the algorithm is bounded by ((n++0(p) Timee(H)).
In the Appendix, we demonstrate that for parameters a, 0, there exist (1- (()))) sensitive hash families for both cosine and Jaccard similarity measures.
3.2 Two-Hop Spanners via SortingLSH
We now describe variant of the Stars algorithm for the construction of two-hop spanners which approximate that k-nearest neighbor graph (k-NN graph, Definition 2.3). While the k-NN Graph itself is sparse for small k, for large & this is no longer the case, and directly approximating the k-NN graph becomes infeasible. Instead, by employing two-hop spanners, we show how one can construct extremely sparse graphs, with almost-linear number of edges, such that the approximate k-nearest neighbors of every point p are contained in the two-hop neighborhood of p. To do so, we will need to utilize a technique known as SortingL
SortingLSH. Since the similarities (p) between points p and their is nearest neighbors may vary significantly across the dataset, we cannot apply single level of bucketing based on hash family chosen with a fixed set of parameters, as doing so would result in points being split around uniform threshold. Instead, we utilize a technique known as SortingLSH, which originates from the work
[6]. SortingLSH evaluates a sequence of hash functions Hpp) = (hu (p), hp(p)) for each point p E P. and interprets the resulting string of buckets as an key for p. One then sorts the keys H (p) lexicographically. and breaks the sorted sequence into contiguous chunks of given window size W. We then apply the two-hop spanner technique on each chunk, by sampling s leaders within that bucket, and comparing each leader to the rest of the chunk.
The key advantage of SortingLSH is that points living in dense regions of the similarity space (P, p1) (i.e., the similarity (p) is large) will share a longer prefix of hashes with their k-nearest neighbors, and therefore be more likely to be placed in the same window as them. At the same time, points whose kenearest neighbors are not as similar will still be equally likely to share (shorter) prefix with their neighbors, and therefore also placed in the same window.
In order describe our results, we first introduce notion of k-approximate nearest neighbors (k-ANN), defined with respect to a family of hash functions H. In what follows, recall that given any p E P and e [n]] we write T. to denote the i-th nearest neighbor to p with respects to p.
Definition 3.2 (ANN with respects to an LSH Family) Fix a point set P equipped with a similarity measure μ1, and let = (h P UJ be a family of hash functions. Fix any p E [0, 1). We say that collection of sets A = (AphpEP is an (ks P)NNNN family with respect to H if for every p P:
Ap is a prefix of the sequence (1), (2). .., (p(n) (Tp)) with size A 2 k.
There exists an integer =((p) such that for all E [k], we have:
Pr (e(( (b ((,, (x((( n
5

---

and such that for all x &f Ap we have
Pr [h)((p)...... ..... he(p)) = (a), .e(x),))e(()))) S n
If A has the property that p(p) S M for all p E P. then we say that A is M M-bounded (p, M)-ANN family (hereafter a (k, p. -NNN family).
Definition 3.2, while at first somewhat unwieldy, is fairly straightforward to unpack. Specifically, given a base hash family H. and let H. denote the family of f-wise concatenations of h E H. Then if, for every p E P. there exists a smaller threshold rp S Tx((p) and a sketch length {()) such that the family 7 (P) is a (Tp: Thk (p), p) -esssiiiveee hash family (Definition 2.1), then the family A = <ApppEr where Ap {q P g( 2 rp), is (k, p)-ANN family. Note that the gap between rpp and (p) will depend on the properties of the family H. Lastly, the condition of being M-bounded simply ensures that one can reach the appropriate splitting point {(p) with a limited number of hash functions. Thus, for points p with extremely large Thk (p) (e.g.., near-duplicate neighbors), in order to ensure that A is M-bounded, one may need to limit E(p) M which would result in value of rp that is smaller than what would otherwise be possible with a larger sketch length {pp).
We now prove explicit bounds for the above notion of k-ANNs for the case of angular (cosine) similarity, and the Jaccard similarity measure. The bounds utilize the well-known SimHash family [14] for cosine similarity, and MinHash [12] for Jaccard similarity. For the case of weighted Jaccard similarity, we remark that there is a straightforward reduction (i.e. similarity preserving mapping) from the (integer) weighted unweighted case by simply duplicating coordinates, therefore the following bounds also apply to the weighted variant. For weighted Jaccard distance over general non-integer vectors, one instead use the variant of min-hash for probability distributions of [34].
Proposition 3.3 (Approximate Nearest Neighbors for Angular and Jaccard Similarity) Let P be a subset of either gd or 2d for some universe U. In the first case, let μ. be the Angular Similarity p(z,y) = 1 Oz where Oz.9 is the angle between I, E P (normalized so that Oz.g [0, 1)), and in the second case we set μ to be the Jaccard similarity p(A, B) = LAUB
| between sets A, B U.
For any E P, let (v(v) = 11 The (p).). Then for any E 10, and M 2 1, there exists a hush family H. for (P, (u) such the family A {Ap)rEP, where
Ap = {a E P u(p, 2 min (1 -1- 1 1 111M}}
a (k. O(e), 4M log n) -ANN family with respect to H.
Since both the angular and Jaccard similarity are bounded by 1, the value sy sx)) in the Proposition 3.3 can be interpreted as a natural dissimilarity measure d(p. q) = 1- p(p q). Therefore, Proposition 3.3 demonstrates that away than the k-th nearest neighbor to p, namely p(p, q) ddpp, (p)).
take Ap to be the set of points q which are at most 1/c factor farther
We now state the main result of this section, which demonstrates that Stars provably recovers nearly distinct
k-nearest neighbors in the two-hop neighborhood of p. Formally, for each point p P. we guarantee that there is a two-hop path from p to nearly k points q E Ap. Moreover, we guarantee that this path utilizes only edges between other approximate nearest neighbors u E Ap
Theorem 3.4 Let P be a point set equipped with a similarity measure μ,, and fix any ó E (0, 1). Let H: P + U be a family of hash functions, such that each h E H can be evaluated in time at most (i) Let G = (P, F) be the graph produced by the algorithm Stars 2. Let A = (Apler be (ks, p. M)-NNN family with respects to H. For any p E P, let Go denote the subgraph of G induced by the set Ap U {p). Then with probability - 1/poby(n), for every p E P, we have: I (p) Z (1 8)k. Moreover, we have |E() = Ô (o-22(+000) and the runtime of the algorithm is Ö(8-' (00(p) M Timme()))-
Theorem 3.4 demonstrates that, even for extremely large values of k, for instance k- = Vn. one can construct a two-hop spanner with a nearly-linear number of edges, such that each point p is connected with at least (1 - 5)k of its k-approximate nearest neighbors, via path containing only k-approximate nearest neighbors of p. Notably, the runtime and the size of the graph produced are independent of k.

---

Stars 2: Constructing Approximate Nearest Neighbor Graphs
Input: Point set P, a hash family H. ANN parameters kt M >> 0, recall parameter 5 E (0, 1).
Repeat: the following procedure R = ci log times, for sufficiently large constant c1.
1. Let (h1,/2;.. ,hM) be sequence of independent draws from H.
2. Sort the points x lexicographically according to the hash values (h1 (2)).......A hM Let #1...., .n be this ordering. Set the window size to be W 16k
3. Pick a random shift
[W/2...., W). and split ....... into consecutive blocks
B1, B,,..., Be, each of size at most W,, such that B1 = { Jr
4. If: l > n22
(a) For each block By, sample 8 = c2p-1n2 log² uniformly random leaders 0z wi...., 3/ ~ Bj. where 02 is a sufficiently large constant depending only on e₁. (b) Create an edge (z, uf) with weight μ(x, u²) for every x E Bj and leader yf E Bj
5. Else if: k S nt
(a) For each block By. create an edge (x, y) with weight p(x, v) for every pair
I. y E By.
4 System Implementation and Design
We have implemented Stars as part of the Grale [25] graph building system using Flume a C++ counterpart to FlumeJava [13]. which is based on the Adaptive Massively Parallel Computation (AMPC) model [7]. Each logical unit of computation is automatically distributed across a number of worker machines, with the experiments in this paper scaling thousands of individual workers.
Our implementation has two primary phases: generating LSH tables using LSH or Sorting then scoring pairs of points that share sketch using all-pain or Stars. For efficiency we generate LSH tables containing only the identifier of each point, excluding the associated point features, as the same point is sketched R >>> times to aid in edge recall. To compute pairwise similarity we thus require an additional round of communication join point features with the LSH tables. We implement this in one of two ways: a MapReduce-stye style distributed shuffle sort, via lookups in distributed hash table (DHT). These two options trade off CPU time and disk usage for memory.
In the shuffle case, we require (Rn) additional disk storage and Of R' log( (Rn)) time to materialize the joined table. For problem settings with billions of points and large feature vectors, this extra storage requirement can be prohibitive. The DHT caches the entire input dataset in memory across multiple machines, requiring ((n) RAM but no additional on-disk storage. This enables online feature lookup we process each bucket, eliminating the need for shuffle and costly disk I/O.
An additional important implementation detail is the limit we impose on LSH bucket sizes. In the worst case, naive LSH implementation could have the same or worse running time than a brute-force all pairs comparison, because poorly chosen LSH function could hash the entire dataset single value, up to R times. To ensure robustness to sub-optimal LSH settings, we randomly partition large buckets into cize-constrained sub-buckets prior pairwise scoring. This reduces the overall number of edges eligible for comparison, potentially impacting edge recall, but also capping the worst case running time for the scoring phase of graph construction. Due to its nearly-linear runtime complexity, the Stars algorithm enables us to relax the sub-bucket size limitation significantly.
See Appendix for further implementation details.
5 Empirical Study
We evaluate the performance and quality of Stars on both real and synthetic datasets of varying scales. We compare the StH+Stars, SortingLSH+Stars, SortingLSH, and bruteforce (AllPair) algorithms.
7

---

num comparisens
synthetic
wikipedia
amazon2m
mnist
2014
1042
sortinglsh
1043
10a4
10t
10"
Ish
sortingish+sstars
10
104
I stars
randomib
random10b
100
400
25
400
100
allpair
dataset
num sketches
num sketches
num sketches
Figure I: Number of comparisons of each algorithm on each dataset. For Random IB and Random IOB, we only run algorithms with number of sketches R = 25, and the AllPair algorithm does not finish in 3 days.
wikipedia
amazon2m
mnist
1.0
LSH exact
recall
LtH+Stars exact
+ approx
0.5
25
100
400
25
100
400
100
400
num sketches
num sketches
num sketches
wikipedia
amazon2m
mnist
1.0
SortingLSH exact
SortingLSH approx
SortingLSH+ Stars exact
0.5
SortingLSH+ Stars approx
25
100
400
25 100
400
25
100
400
sketches
num sketches
num sketches
Figure 2: The recall of found near(est) neighbors of each algorithm.
Datasets. We run experiments on three real public datasets: MNIST [30], Amazon2m [9] (also known OGBN-Products [28]), and Wikipedia [39], and two synthetic datasets: random and random10B. MNIST contains 60k data points, each of which has a feature a 784-dimensional float vector. Wikipedia contains 3,650.339 data points, where each point is represented by set of strings with positive weights. Amazon2m contains 2,449 ,,99 data points, each of which has a feature of a 100-dimensional float vector and set of strings. Random 1B and random 10B generated from Gaussian mixture model with 100 modes, where each data point has 100 dimensions. Random IB contains 109 data points and Random contains 10 data points. We refer readers to Appendix D for further details regarding the datasets.
Sketching parameters. For each similarity measure studied, we use a corresponding LSH function to build the graph. In particular, for MNIST, Random B and Random 10B datasets, we study the cosine similarity between float vector features, and thus we employ SimHash for them. For the Wikipedia dataset, we study the weighted Jaccard similarity between two sets of strings with weights, and therefore we use the weighted Minhash LSH to build the graph. For the Amazon2m dataset, study two different similarity measures: (1) a mixture of cosine similarity and Jaccard similarity, and (2) neural network where the training set of candidate pairs are generated by SimHash over float vector features and MinHash over sets of strings [25]. In summary, in both cases, we use a mixture of SimHash and MinHash for graph building. See Appendix D for more detailed sketching setups.
Number of comparisons. Figure 1, we illustrate the number of pairwise similarity comparisons of each algorithm each dataset. In all cases, Stars yields at least 10-fold improvement in number of comparisons over the other algorithms. The number of comparisons used by Stars can be further reduced by choosing smaller number of leaders (see Appendix D).
Coverage of Near(est) Neighbors. We evaluate the number of (approximate) near(est) neighbors which can be found for each point in the dataset, and by each algorithm. We run the bruteforce (AllPair) algorithm for MNIST, Wikipedia and Amazon2m (using mixture similarity) datasets to find all ground truth 1e0-nearest neighbors and all ground truth near neighbor points with similarity above 0.5 for each point. For the non-Stars LSH based algorithm, we compute the fraction of points with similarity at least 0.5 that are direct neighbors for each point. For LSH+Stars, we compute two ratios, the first is the fraction of points with similarity least 0.5 that can be found two hops where each edge has similarity also at least 0.5, and the second is the same except that the two hop edges
8

---

10"
Ish-exact
num edges
10
I Iih stars--rrrde
10a
allpair-exact
108
10a
100
400
100
num sketches
num sketches
num sketches
Wikipedia
Amazon2m
MNIST
Figure 3: The number of edges with similarity at least 0.5 (0.495 for relaxed threshold) built by each algorithm.
0.8
Vilesoure
0.4
sorting shettrsttrtt
thesttrs--co caam
loam
sortinglhhesten
50hmix
Shrstorsma
VMozzur
ish
ish-stars
sorting sh-lemm
sorting-hhmm
0.5
sortinglsh-
0.2
aipat-emdd S-iamn
alpainemm...
sortingish
alpan- 100mm-mm. mix
alppair-sm0..5
allpair 100nn
affinity
affinity rounds
Amazon2m
MNIST
Figure 4: The VMeasure scores of clusterings. The allpair-100mn indicates the ground truth 100-nearest neighbor graph. The allpair-sim0.5 indicates the ground truth near neighbor graph induced by edges with similarity at least 0.5. The suffix learn indicates the similarity learned by neural network. The suffix mix indicates the mixture similarity of cosine similarity and Jaccard similarity.
have similarity least 0.495 (this aligns with the 001-approximation mentioned in Section 3.2). For SortingLSH based algorithms, we consider the fraction of exact 100-nearest neighbors can be found in one hop and two hops for non-Stars and Stars respectively in the graph introduced by the 100-nearest neighbors. We also consider the relaxation of finding 1.01-approximate 100-nearest neighbors (i.e. 1/c = 1.01). Note that if we find more than 100 approximate 100-nearest neighbors, we regard the ratio as 1. In Figure 2, we report the average of each ratio over all data points. The graphs built using Stars are able to find more near(est) neighbors in 2 hops, with fewer edges overall. Note that the graphs built by SortingLSH-benn since we only keep the 250 closest points for each node (even for SortingLSH+Starss) The sparsity of graphs built by LSH-based algorithms is presented in Figure 3. In Figure 2, we show good recall of finding -01-appro near(est) neighbors
algorithms have the same sparsity
hops by our Stars algorithms. In the meanwhile, the number of edges shown in Figure 3 is much less than n 1.99 which is suggested by our theoretical guarantees. This phenomenon is observed all datasets used in Figure 2,3.
Clustering. The points from MNIST are drawn from 10 classes, and the points from Amazon2m are drawn from 47 classes. To cluster the graphs, we run average Affinity clustering [5] on the graphs built by each algorithm. In particular, for graphs built by LSH-based algorithms, we only keep the edges with similarity at least 0.5, and for graphs built by SortingLSH-base the closest direct 100 nodes for each point. For Amazon2m, we consider both mixture similarity and learning similarity, i.e., we built graphs for each similarity and apply clustering on these graphs. For all algorithms, we use the number of sketches R 400. We measure the clustering quality via VMeasure score [37] which is the harmonic mean between homogeneity score and completeness score of a clustering. The VMeasure score is in (0, 1). The higher the VMeasure score, the higher the quality of the clusters. We report VMessrre scores in Figure 4.
algorithms, we only keep
Effect of the similarity function. As shown in Figure 4, using a similarity function learned by a neural network the graph building stage indeed helps other downstream tasks such as clustering on the built graphs. However, a sophisticated similarity function increases the running time of computing the similarity between two points. In fact, all of our algorithms become 5x 10x (ín terms of the total running time over all workers) slower when using neural network similarity instead of using the mixture of cosine and Jaceard similarity to build the graph for Amazon2m dataset. Fortunately, the Stars graph building algorithms use significantly fewer comparisons. and are 10x faster than non-Stars versions (in terms of total running time over workers). addition, they lose only negligible quality for downstream tasks. Thus, given the same computational resources, switching to a Stars-based graph building strategy enables us employ wider range of similarity functions, and affords us the potential to significantly improve the quality of downstream tasks.

---

Experiments on Random10B dataset. Since we set the degree threshold to be 250, each algorithm outputs exactly 2.5 trillion edges for the Random dataset. However, since the non-Stars- -tarsss---aee algorithms make ~ 1044 comparisons, more than 95% of these comparisons are redundant. In contrast, the number of comparisons made by Stars-based algorithms only 2-3x the number of edges obtained. Overall, the total running time of non-Stars LSH based algorithm is 100x the total running time of LSH+Stars. Similarly, the total running time of non-Stars SortingLSH algorithm is 10x the total running time of WortingLSH+Strn The actual runtime of all Stars-based algorithms finish hours, whereas the non-Stars SortingLSH algorithm finishes in 4 hours, and the non-Stars LSH algorithm finishes in 23 hours.
References
[1] A. Abboud, V. Cohen-Addad, and H. Houdrougé. Subquadratic high-dimennionall hierarchical clustering. Advances in Neural Information Processing Systems, 32, 2019.
[2] R. Ahmed, G. Bodwin, F. D. Sahnch, K. Hamm, M. J. L. Jebelli, S. Kobourov, and R. Spence. Graph spanners: tutorial review. Computer Science Review, 37:100253, 2020.
[3] A. Andoni, A. Naor, A. Nikolov, I. Razenshteyn, and E. Waingarten. Data-dependent hashing via nonlinear spectral gaps. In Proceedings of the 50th Annual ACM SIGACT Symposium Theory of Computing, pages 787-800, 2018.
[4] A. Andoni and Razenshteyn. Optimal data-dependent hashing for approximate near neighbors. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 793-801, 2015.
[5] M. Bateni, S. Behnezhad, M. Derakhshan, M. Hajiaghayi, R. Kiveris, Lattanzi, and V. Mir- rokni. Affinity clustering: Hierarchical clustering at scale. In NIPS 20/7, pages 6867-6877, 2017.
[6] M. Bawa, T. Condie, and P. Ganesan. Lsh forest: self-tuning indexes for similarity search. In Proceedings of the 14th international conference on World Wide Web, pages 651-660, 2005.
[7] S. Behnezhad, L. Dhulipala, H. Esfandiari, J. Lącki, V. Mirrokni, and W. Schudy. Massively parallel computation via remote memory access, In The 31st ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '19, page 59-68, New York, NY, USA, 2019. Association for Computing Machinery.
[8] A. Beygelzimer, S. Kakade, and J. Langford. Cover trees for nearest neighbor. In Proceedings of the 23rd international conference on Machine learning, pages 97-104, 2006.
[9] K. Bhatia, K. Dahiya, H. Jain, P. Kar, A. Mittal, Y. Prabhu, and M. Varma. The extreme classification repository: Multi-label datasets and code, 2016.
[10] O. Boiman, E. Shechtman, and M. Irani. In defense of nearest- based image classifica- tion. In 2008 IEEE conference on computer vision and pattern recognition, pages 1-8. IEEE, 2008.
[11] M. R. Brito, E. L. Chávez, A. J. Quiroz, and J. E. Yukich. Connectivity of the mutual k-nearest- neighbor graph in clustering and outlier detection. Statistics & Probability Letters, 35(1):33 42, 1997.
[12] A. Z. Broder. On the resemblance and containment of documents. pages 21-29, 1997.
[13] C. Chambers, A. Raniwala, F. Perry, S. Adams, R. Henry, R. Bradshaw, and Nathan. Flumejava: Easy, efficient data- parallel pipelines. In ACM SIGPLAN Conference Programming Language Design and Implementation (PLDI), pages 363-375, 2 Penn Plaza, Suite 701 New York, NY 10121-0701, 2010.
[14] M. Charikar. Similarity estimation techniques from rounding algorithms. pages 380-388, 2002.
[15] M. Cochez and H. Mou. Twister tries: Approximate hierarchical agglomerative clustering for average distance in linear time. Proceedings of the 2015 ACM SIGMOD international conference on Management of data, pages 505-517, 2015.
10

---

[16] S. D.Daguptt. A cost function for similarity based hierarchical clustering. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 118 118-127, 2016.
[17] L. Dhulipala, D. Eisenstat, J. Lącki, Mirrokni, and J. Shi. Hierarchical agglomerative graph clustering in nearly-linear time. In International Conference Machine Learning, pages 2686.2686. PMLR, 2021.
[18] W. Dong, C. Moses, and K. Li. Efficient k-nearest neighbor graph construction for generic similarity measures. In Proceedings of the 20th international conference on World wide web, pages 577-586, 2011.
[19] Y. Dong, P. Indyk, I. Razenshteyn, and T. Wagner. Learning space partitions for nearest neighbor 2019.
search. arXiv preprint
[20] A. Epasto, M. Mahdian, V. Mirrokni, and P. Zhong. Massively parallel and dynamic algorithms for minimum size clustering. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1613-1660. SIAM, 2022.
[21] D. Eppstein. Spanning trees and spanners.. 2000.
[22] A. Gionis, P. Indyk, R. Motwani, et al. Similarity search in high dimensions via hashing. In Vidb, volume 99, pages 518-529, 1999.
[23] S. Guha, R. Rastogi, and K. Shim. Rock: A robust clustering algorithm for categorical attributes. Information systems, 2555)3345-36, 2000.
[24] R. Guo, S. Kumar, Choromanski, and D. Simeha. Quantization based fast inner product search. In Artificial intelligence and statistics, pages 482-490. PMLR, 2016.
(25] J. Halcrow, A. Mosoi, S. Ruth, and B. Perozzi. Grale: Designing networks for graph learning. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery 2020.
& Data Mining, pages
[26] Har-Peled, P. Indyk, and R. Motwani. Approximate nearest neighbor: Towards removing the curse of dimensionality. Theory of computing, 8(1):321-350 2012.
[27] S. Har-Peled, P. Indyk, and A. Sidiropoulos. Euclidean spanners in high dimensions. In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, pages 804-809. SIAM, 2013.
(28) W. Hu, M. Fey, M. Zitnik, Y. Dong, H. Ren, B. Liu, M. Catasta, and J. Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 62, 2020, virtual, 2020.
[29] Indyk, I. Razenshteyn, and T. Wagner. Practical data-dependent metric compression with provable guarantees. Advances in Neural Information Processing Systems, 30, 2017.
[30] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied document recognition. Proceedings of the IEEE, 86(1 36(11):2278-2324, 1998.
[31] T. Liu, A. Moore, K. Yang, and A. Gray. An investigation of practical approximate nearest neighbor algorithms. Advances in neural information processing systems, 17, 2004.
[32] A. Moore. The anchors hierachy: Using the triangle inequality to survive high dimensional data. arXiv preprint 1301.387. 2013.
[33] B. Moseley and Wang. Approximation bounds for hierarchical clustering: Average linkage, bisecting k-means, and local search. Advances in neural information processing systems, 30, 2017.
[34] R. Moulton and Y. Jiang. Maximally consistent sampling and the jaccard index of probability distributions. arXiv preprint
2018. 2018.

---

[35] V. Nair and G. E. Hinton. Rectified linear units improve restricted boltzmann machines. In ICML, 2010.
[36] O. O' O'malley. Terabyte sort on apache hadoop. Yahoo, available online at: http://sorbbenchmark org/Yahoo-Hladopp. pdf.(May), pages 1-3, 2008.
[37] A. Rosenberg and Hirschberg. V-measure: A conditional entropy-basee external cluster evaluation measure. In Proceedings of the 2007 joint conference on empirical methods in natural language processing and computational natural language learning (EMNLP-CoNLL), pages 410-420, 2007.
[38] A. Roy and S. Pokutta. Hierarchical clustering via spreading metrics. Advances in Neural Information Processing Systems, 29, 2016.
[39] Wikipedia, Wikipedia.
[40] Yan, D. Xu, B. Zhang, H.-J Zhang, Q. Yang, and Lin. Graph embedding and extensions: A general framework for dimensionality reduction. IEEE transactions pattern analysis and machine intelligence, 29(1):40-33 2006.
[41] U. Zwick. Exact and approximate distances in graphs a survey. In European Symposium on Algorithms, pages 33-48. Springer, 2001.
12


Reviews:
[{"review_id": "cY-6V0go9cm", "reviewer": "Reviewer_Gvmm", "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. \n\nThey 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. ", "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? \n\n2) Have you made any comparisons of theoretical guarantees and/or experimental results against other fast clustering/nearest neighbor algorithms?", "limitations": "Adequately done. ", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality:\n\n++ Somewhat original. Builds off techniques from previous similarity clustering algorithms as well as using techniques of locality sensitive hashing and two-hop spanners. \n\n-- Not clear to me how this compares to other approximate K nearest neighbor and similarity graph construction algorithms\n\ne.g.\n\nEiras-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.\n\nZhang, Yanming et al. “Fast kNN Graph Construction with Locality Sensitive Hashing.” ECML/PKDD (2013).\n\nWang, 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.\n\nQuality:\n\n++ This is a complete, high quality work. \n\n++ While I have not confirmed all the proofs in the appendix, the theorems seem to be soundly derived. \n\n++ The experiments show the effectiveness of the algorithm in terms of efficiency and approximation. \n\n-- It would be nice to have some more experiments showing the usefulness on downstream tasks. \n\n-- Also, no comparisons to similar works.\n\nClarity:\n\n++ 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. \n\nSignificance:\n\n++ It seems like this would be of interest to some readers. It seems certainly on the application side this would be of interest. \n\n-- 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 \n\n\nSpelling/Gramar:\n\nline 172: twp-hop -> two-hop", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "bnf8g_MUqa", "reviewer": "Reviewer_DHNc", "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.  ", "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", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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. \n\nI could not check the maths in detail to approve the analysis. \n\nWhat 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. \n\nThe paper has typos in many places. ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "RnTTl-KVXOW", "reviewer": "Reviewer_kY9Y", "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.\n\nThis 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.\n\nThis 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).\n\n", "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.\n\nAnother 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.\n", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nThe 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:\n- tau_k(p) not explicitly defined (is line 199 supposed to be implicitly defining it as the similarity to the kth most similar point?)\n- Incompatible neighborhood notation between lines 149 and 261\n- 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)\n\nand 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.\n\nSmall corrections:\n1. missing subscripts on the pi's in line 220\n2. Did you mean d(p,q) instead of mu(p,q) on line 251", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "N00xQwFrGdu", "reviewer": "Reviewer_MbNY", "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.", "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?\n\nQ2. 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?\n\nQ3. 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?\n\nQ4. 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?\n\nQ5. As stated in W4.3.", "limitations": "See W1 to W4.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nS1. 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.\n\nS2. 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.\n\nWeaknesses:\n\nW1. 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).\n\nW2. 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).\n\nW3. For both theoretical and experimental evaluations, there are insufficient baselines included in this paper.\n\nW3.1. For theoretical complexity analysis, it only presents the complexity of Stars without comparison to other approaches.\n\nW3.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.\n\nW3.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.\n\nW4. The experiment designs are still too simple beside the baseline issue. Sec 5 Empirical Study lacks critical information and is poorly written.\n\nW4.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.\n\nW4.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.\n\nW4.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?\n\nMinor issues:\nI1. Line 125 sentitive -> sensitive.\n\nI2. Line 297-305, whether Random1B/Random10B dataset names are capitalized needs to be aligned.\n\nI3. 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.\n\n[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.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept