Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits
Authors: Haya Diwan
Jinrui Gou
Cameron N Musco
Christopher Musco
Torsten Suel
Venue: NeurIPS 2024 poster (2024)
Keywords: vector databases
navigable graphs
near-neighbor search
Primary area: other
TL;DR: We prove tight upper and lower bounds for the average degree of navigable graphs for high-dimensional point sets.

Abstract: There has been significant recent interest in graph-based nearest neighbor search methods, many of which are centered on the construction of (approximately) "navigable" graphs over high-dimensional point sets. A graph is navigable if we can successfully move from any starting node to any target node using a greedy routing strategy where we always move to the neighbor that is closest to the destination according to the given distance function. The complete graph is obviously navigable for any point set, but the important question for applications is if sparser graphs can be constructed. While this question is fairly well understood in low-dimensions, we establish some of the first upper and lower bounds for high-dimensional point sets. First, we give a simple and efficient way to construct a navigable graph with average degree $O(\sqrt{n \log n })$ for any set of $n$ points, in any dimension, for any distance function. We compliment this result with a nearly matching lower bound: even under the Euclidean metric in $O(\log n)$ dimensions, a random point set has no navigable graph with average degree $O(n^{\alpha})$  for any $\alpha < 1/2$. Our lower bound relies on sharp anti-concentration bounds for binomial random variables, which we use to show that the {near-neighborhoods} of a set of random points do not overlap significantly, forcing any navigable graph to have many edges.

Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits
Haya Diwan New York University hd23718nyu.edi edu edu
Jinrui Gou New York University jg62260nyu. edu
Cameron Musco
UMass Amherst cmusco@cs, umass. edu
Christopher Musco New York University
Torsten Suel New York University torsten, suel@nyu. edu
cmusco@nyu. edu
Abstract
There has been recent interest graph-bused nearest neighbor search methods, many of which are centered the construction of (approximately) navigable graphs over high-dimensional point sets. graph is navigable if we can successfully move from any starting node to any target node using greedy routing strategy where we always move to the neighbor that is closest to the destination according to the given distance function. The complete graph is obviously navigable for any point set, but the important question for applications is if sparser graphs can be constructed. While this question is fairly well understood in low-din -iw-dimnsssons we establish some of the first upper and lower bounds for high- sighddimessiona point sets. First, we give simple and efficient way to construct navigable graph with average degree O O(vn n log vi) for any set of n points, in any dimension, for any distance function. We compliment this result with nearly matching lower bound: even under the Euclidean metric in O(log n) dimensions, a random point set has no navigable graph with average degree Onn") ) for any 1/2. Our lower bound relies on sharp anti-concentration bounds for binomial random variables, which we use show that the near-neighborhoods of set of random points do overlap significantly, forcing any navigable graph to have many edges.
Introduction
The concept of navigable graph has arisen repeatedly over the decades, perhaps most famously in Kleinberg's work on understanding Milgram's s "Small World" experiments from the 1960s [Kleinberg] 2000a b Milgram 1967]. Concretely, suppose we given n points Z1,.... In X in some input domain X, a distance function X' x X R20, and a directed graph G = (V, E), where each vertex in V {1...., } is associated with one of points. G is said to be navigable if the standard greedy routing algorithm successfully finds a path between any starting vertex E V and any target vertex i I In particular, letting (s)) denote the out-neigh of s, this algorithm first navigates to r E N (x) which minimizes D (Ir,, ...). At each subsequent step, we navigate to the out-neighbor of the current node that minimizes the distance to Fı, terminating once reach Tt, no neighbor has an associated point that closer to I2 than the current node.
It has been observed that many real-world networks (the internet, airport networks, social networks, etc.) are either navigable or almost navigable, where v; plays the role of, e.g., the physical coordinates of server individual and D is the standard Euclidean distance some other metric (Boguñá et al.)
G is further considered "soall-worldd if greedy routing always terminates in small number of steps.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

2009]. Moreover, there has been interest in showing that natural generative models for networks produce navigable graphs with good probability [Kleinberg]
2000a Watts and Strogatz 1998
1.1 Constructing Sparse Navigable Graphs
More recently, significant work has studied the problem of constructing navigable or "approximately" navigable graphs given a point set . In E X' and distance function D. For any D and any point set, the complete graph is navigable, so more concretely, the goal is to construct a navigable graph that is as sparse as possible. At a high-level, this objective underlies many recently developed graph- based approximate nearest neighbor search methods such as DiskANN [Subramanya et al., 2019), the Hierarchical Navigable Small World (HNSW) method [Malkov and Yashunin [2200] Malkov et al.. 2014], and the Navigating Spreading-our Graph (NSG) method [Fu et al. [019 Such methods have shown remarkable empirical performance, outperforming state-of-the-arr implementations of popular approximate nearest neighbor search algorithms such as product-quantizate
and locality-sensitive hashing (Johnson al. 202T] Jégou et al. 2011 Indyk and Motwani [998] Andoni al., 2015] The computational efficiency of the graph- based methods is governed by the number of edges in the graph being searched, motivating the need for sparse navigable graphs.
Despite this recent interest, there has been relatively little theoretical work on the problem of constructing navigable graphs. When the input points lie in I2d and D is the Euclidean distance function, it is not hard to check that the Delaunay graph is navigable 3 While the Delaunay graph has average degree (11) in dimension d = 2 (since it is planar) it can have average degree (n) in dimension d = 3 or higher [Klee] 1980]. A better bound can be obtained via the so-called sparse neighborhood graphs of [Arya and Mount 1993], which are shown be navigable for any point set in Rd under the Euclidean distance and have average degree 20(4) 4 While this results in sparse navigable graph for small values of d, the degree bound is no better than that of the complete graph for d 2(log n).. Given that modern applications of nearest neighbor search often involve high dimensional data points, it is natural to ask if anything better can be done in high dimensions.
1.2 Our Results
The main contribution of this work is to provide tight upper and lower bounds on the sparsity required to construct navigable graphs for high-dimensional point sets. In particular, we prove two main results. The first is a strong upper bound that follows from a straight-forward graph construction:
Theorem For any imput domain X. point set T1....,. In E X, and distance function D X RZ20 such that D,), = 0 for all i and D(I,, > 0 for Ij + Ii, it is possible to efficiently construct directed navigable graph with average degree at most 2/n In n. Moreover, the graph has the additional "small world" property: greedy routing always succeeds in at most 2 steps.
Theorem | essabblishes that, even in arbitrarily high dimension, it is possible to beat the naive complete- graph solution, which has O(n²) edges (average degree n)) The result is proven in Section It is based simple construction, reminiscent of cxisting techniques for building nearest neighbor search graphs: we take the union of a O(yn h log n -nearest neighbor graph, and a random graph with average degree O(yn log Malkov et al. 2014 Kleinberg, 2000b Subramanya et al. 2019].
Surprisingly, Theorem I holds for essentially any distance function, even if it is not metric. Moreover, the construction is efficient: the navigable graph can be computed in Onn2 + n)) time, where is bound on the cost of computing D D(zi, xx)) for any i,j- Given the generality of Theorem [ we might expect that navigable graphs with even fewer edges could be constructed under additional assumptions - e.g., we considered only the special case where the input domain is I&d and is the Euclidean distance. Our next result rules this out when d Q(log n). In particular, we show:
Theorem 2.
Let I1,..., In E IRd be vectors with i.i.d. random 11 entries, and let D( = ||z, l2l be the Euclidean distance. For any parameter 8 > 0, if d 2 fo log foror a fixed constant c. then with high probability, any navigable graph for æ1,... In requires average degree Q(n
2 Note that none of these methods actually claim to construct sparse graphs that are navigable in the worst-case. They use heuristics to build graphs that are "approximately navigable", meaning that, empirically, greedy search tends to find good approximate nearest neighbors when run the graphs
'The Delaunay graph connects i, j if x; and xy have adjacent cells a Voronoi diagram for Ti,... Znn "uuh graphs are closely related to but not the same "relative neighborhood graphs" Toussaint 1980
2

---

Theorem 2 is proven in Section 4
is a corollary of our more general Theorem 4 which also implies a lower bound of (2 log n) average degree when d = (2 n). The proof starts with straight forward observation: in order for greedy routing to make progress towards destination node H;, any node within the k-nearest neighbor set of 2;, for any k, must include an edge to some other node in that set (possibly 2; itself). Using sharp coteeetncentatioon bounds for binomial random variables Ahle 2017 Cramér 2022). we argue that, when & = O(yn) and when 21. ........ In E ff-1, 1] are random for large enough d, the nearest neighbor sets for different destination nodes have very small pairwise intersections. Intuitively, they are nearly independent random sets of size O( and thus have expected overlap close to 1. This small overlap means that few edges can used to 'cover' the required connections within different nearest neighborhoods, giving a lower bound on the average degree of any navigable graph.
We remark that Theorem 2 cannot be improved significantly in its bound on the dimension d. As mentioned, for the Euclidean distance over IR, it is possible to construct navigable graphs with 20(4) edges for any d dimensional point set using the sparse neighborhood graphs of [Arya and Mount 1993]. This leads to average degree less than n 1/2 when d = clog n for a small enough constant c.
1.3 Outlook
Together, Theorems I and 2 help complete the picture of what level of sparsity is achievable when constructing navigable graphs in high-dimensions. However, these bounds are not the end of the story. For one, there are many variations simple greedy search that would lead to other notions of navigability, For example, in nearest neighbor search applications, a version of greedy search called beam search, which explores multiple greedy paths, is often preferred (Subramanya et al. 2019
Beyond the average degree, which we focus on in this work, the maximum degree of a navigable graph is also a natural metric, governing the maximum complexity of each iteration of greedy search. Unfortunately, for the navigability problem we study, we show in Section 4.3 that there are point sets for which every navigable graph must have maximum degree n. It would be interesting if relaxations of the problem or more flexible search method can avoid this limitation.
Finally, an important direction for future work is to prove end-to-end approximation guarantees for graph- based nearest neighbor search algorithms. Since finding exact nearest neighbors in high dimensions suffers from challenges related to the curse of dimensionality, a reasonable goal would be to prove that greedily routing towards any query q E X' converges on an a-approximate nearest neighbor 2j satisfying D(g. .25) S a a-min, D(q, [4; for some a 2 1. This is the sort of guarantee that locality sensitive hashing and other methods can achieve with query time that provably sublinear in n, i.e., without needing to directly compare g to all vectors Z1...., In [Kleinberg] 1997| Kushilevitz cet al., 1998. Indyk and Motwani 1998 Har-Peled 2001]. Importantly, if regular greedy search is applied from an arbitrary starting node, navigability is necessary condition for a-approximate neigest search. In particular, for any finite a, if q E (x, In min, D(q, x.)) = 0, so must return q exactly. However, navigability is not sufficient condition for greedy search to succeed, as it does not guarantee any level of approximation for queries that are not in (#1...... Fr }
For some initial work this more challenging problem, refer to the reader to Laarhoven 20188 Prokhorenkova and Shekhovtsov [2020). and Indyk and Xu 2023
2 Preliminaries
Notation. Throughout, consider set of distinct points ,1,..., J., E X' for some input domain X' and a distance function D :: X' x X' - R220 D(r,, 2.y) denotes the distance from point j to point i. We assume only that D(z,, x;) = 0 for all and that D(z;, xT) > 0 for xj # x, Our main upper bound, Theorem I does not require D to be metric, even to be symmetric. Our main lower bound, Theorem holds against the standard Fuclidean distance DI,, = | 22112-
We aim to construct a directed graph G = (V. E), where each vertex in V = {1...., n) is associated with one of our input points. Each edge E E is an ordered pair (i. indicating that there is an
EEven these assumptions are not needed, but they make our definition of "nvigabble" more natural, Otherwise, we must allow for greedy routing to navigate any vertex xz E argmin.,......r D(rr, 2x) given target Zt.
3

---

edge from node to node j. Throughout, we let in denote the natural base-e logarithm of n, and log n denote the base-2 logarithm of
Algorithm 1 Greedy Search
1: Input: Graph G over nodes (1, (1...., n), starting node 8, query point
2: Output: A point z that is ideally close to E with respect to distance function D.
3: j & 8, Done + False
4: while Done = False do
5:
if (() 0 then
6: Done t True.
7: else
8:
h + argmingeNG) ((E, 2,), where ties are broken to prefer nodes with the lowest id
9:
if D(E, (n) (TT, then
10:
j + h. else if D(T, D(2, and h < then j + h.
11:
Tie-breaking on node id.
12:
13:
else
14:
Done t True.
15:
Return Tyj
Distance-Based Permutations. We let ((t) denote the out-neighbors of node in the graph; i...
j e (i) if and only if (i,j) E E. We use the notation N₁ (i)..... (i) (i) index the list of nodes in the graph ordered in non-decreasing order by their distances from i; ie., for & < f, D(r,, (N) S D(x,, x N.))). Ties are broken by node id. Specifically, whenever D(x,, (N)) = D(z,, (t) and k < f, then (i) < Nz).). This choice is arbitrary, but a consistent way of breaking ties will simplify our exposition. For most applications, we will not have distances repeat exactly in the dataset, so tie breaking is never invoked. Note that since we assume T1,... ...,,,,, Tn are distinct and that D(r,, = 0 for all i and (r,,, O for all * i, we always have that N₁ (1) =
Greedy Search and Navigability. We study a notion of navigability that is tied to the standard greedy graph search algorithm for nearest neighbors, which is detailed in Algorithm I It can be checked that the algorithm always terminates at most n iterations since j can only be equal to every node in the graph at most once. Additionally, we note that Line 11 and 12 are unnecessary in the case when distances are assumed to be unique. When this not the case, these lines implement our arbitrary tie- breaking rule, which is to prefer nodes with lower id when distances are equal.
Given Algorithm [ we define navigability formally as follows:
Definition 3 (Navigable Graph). A graph G is navigable for point set Ti...., In under distance function D if. for all s,t {L...., n). when Algorithm is run with starting node and query = Iz, then the algorithm returns Zt. Le., when the query I exactly matches a point in the dataset, the algorithm finds that point. We further say that G is "small world" with parameter S if the algorithu always terminates after at most S calls to the while loop.
will be useful to think about navigability as a property of the distance- basedd node permutations defined earlier. In particular, navigability is implied by the following property:
For all and all i >>> 1, there is an edge from N2(() to Ng(() for at least one k < l.
In particular, when given a query x; E (.1,..., In), Algorithm| 1 will only move from nodes N1
to (t) for which & < f. Moreover, long there is such le in the out-neighborhood of (t).). then the algorithm will not terminate at (t) J. It follows that, if [I holds, the algorithm is guaranteed terminate at Ni (t) and return Tz, as desired. We remark that, if all distances between nodes are distinct, I is equivalent to the navigability property of Definition 3 although we will not require this fact. To better illustrate the connection between ( and Definition 3] we include an example of navigable graph in Figure and the corresponding list of distance- based permutations in Figure 2
Formally, h + min ((argminzeNt)) 2)). where argmin, f(t) returns the set of minimizers of f-

---

Upper Bound
We begin by proving our main positive result, which restate below:
Theorem [ For any imput domain X. point set 21. E X, and distance function D X X - I such that I2) = 0 for all and (z),, 0 for 2j # 24, possible to efficiently construct directed navigable graph with average degree at most 2//lur Moreover, the graph has the additional "small world" property: greedy routing always succeeds in al most 2 steps.
Vertex
Coordinates
(4, -2)
2
(6, -6.
3
(2,1) 1]
(0,0)
5
(1,
(a)
(b)
Figure I: Example of navigable graph (V, F.) on 5 nodes. A double arrow indicates that both
(i,j) E E' and (j.i) e) E E. We can check that is navigable by referring to Figure 2
(a) Permutation for 1.
(b) Permutation for 2.
3
(c) Permutation for 3.
(d) Permutation for 4.
(c) Permutation for 5.
Figure 2: Distance-based permutations for the data set in Figure
As an example, in the plot above,
we have (1) 1, (1) 2, N₃(1) 5, (1) 4, N1 3, we have (2 2, N₂ 1, (2) = 3, (2) = 5, (2) = 4, etc. For the permutations, we draw edges the graph G from Figure 1 that point "left" in the permutation. In particular, show edges that connect any Ne(t) to (t) with & < We can check that property (T) holds, so the graph is navigable.
Proof. We give two different constructions that establish the theorem. The first is randomized, and succeeds with high probability. The second deterministic. Both require (n log n)) time to construct, where T is the time to evaluate the distance function D for any two input points.
Construction 1: Randomized. Let m be an integer between 1 and n, to be chosen later. Our first
construction is follows:
For all i E {l,...,.) n and all < e S m, add an edge from (1) to N1 = i.
For all i {1,... n. add an edge from to 3n lun nodes chosen uniformly random from [I,...,n} {i).
To prove that this construction leads a navigable graph, we need to prove the I holds with high probability. To do so, consider the permutation N (i), (2) for a fixed node i. The property trivially holds for all é m since we connected Ne(i) to (1) step one of the construction. So, we only have to consider { > m.
For any m, the chance that any random edge from the second step of the construction connects to some (1) for le I m m. So, the chance that none of the random edges connect Ne(i)
to some (1) for l S is at most
+. By union bound, it follows
5

---

that with probability at least 1 - 1 for all i and all >> m, Neei)) has an edge to some N₂ (i) with k S m Thus property holds, and we conclude that the graph we constructed is navigable.
It is left to set The graph constructed has at most (m 1)n + n In S. mn + ln
edges. Balancing terms, if we choose m /3n In n, the graph has S 2/3n25// edges.
Finally, we observe that constructing the graph requires computing and sorting all n distance-based permutations, which takes On' logn)) time. Moreover, we can see that the constructed graph is small-world with parameter C' = 2. In the first iteration of Algorithm I we are guaranteed to choose node h that is one of the m closest neighbors of the input I;- Then, at the second iteration, h has an edge to i itself and so we terminate.
be derandomized relatively directly. We construct the same n - 1) edges from (i) to Ni( for all and 1 < < S m. The goal in constructing random edges was ensure that, for 8 m, Ne(i) always has an edge some node in {Ni (1). (i).... Nn { which we will call i"s "near-neighbortood"" and denote by (1). We can instead ensure that each Ne(i) has an edge into (i) via a greedy set cover approach.
Construction 2: Deterministic. Our randomized construction
In particular, claim that there is set of g 1 ulnn nodes ki...., by such that every near- neighborhood Nm (i) contains at least one of kj,..., kg. To ensure property (1) for values >> m, only have to connect all nodes in
graph to this set. We construct this set greedily. Let is in
B (1.....n] n) and, for > 1, let B, denote the set of all for which none of (1). We have that [1 n and our goal is show that By++1 1. By counting argument, there must be at least one node that appears in Nm (1) for at least m different values of E B1. Select this node to be kn, which ensures that:
Ba (1- B
n
Again by counting argument, there must be one node that appears in Nin for least Bal-m values of E B₁. Select this node to be h2, which ensures that:
B2 m (1 m
m71
[aal < B2
B2 <
n.
Continuing this way, we conclude that [By+1l I (1 - --) ) n, which is less than as long as g>> alnn We conclude that, long we connect every node to ki,..., kg. ① is satisfied for all (e)1) where > m, so our constructed graph is navigable.
In total, our deterministic graph has most (m 1)n + n ( Inn + 1) edges. Choosing vn in we get graph with at most 1.5 VIn edges. Again, the cost the algorithm is dominated by the O( + n)) time required to compute and sort all n distance-based permutations.
We remark that, while may be possible improve our upper bound from O Ovv log to ((vn) average degree, we do not believe our analysis can be directly tightened. For random points in high-dimensional space under the Euclidean metric, we roughly expect each near-neighborhood Nn ()) to look like uniformly random subset of (1....,n} .n). If the neighborhoods were truly random, then existing results on random set cover problems imply that it is not possible to find .j...., ...
covering all near-neighhorhoods unless = Ω (" (nlna
Vercellis 1984
Arpino al. 2024
4 Lower Bounds
In this section, we prove Theorem which shows that even for random point set in Rd for O(log n) under the Fuclidean metric, Theorem cannot be improved significantly: with high probability, any navigable graph G must have average degree 22(22/2-5) for any fixed constant Theorem is corollary of our more general Theorem 4 which we state below:
Theorem 4.
Let æ1,.... In E f-1,1 be distributed independently and uniformly in (-1,1] With probability > Io any navigable graph for II,...;Zo, under the Euclidean metric requires
(n13/2-9) edges. max
loglox log
.0V
log
for a universal constant c.

---

The 22(23/2-6) lower bound of Theorem 2 follows immediately from Theorem by taking d' = e 8t logn. n. Alternatively, if take c² log" n we have lower bound of f22 log which matches Theorem | up to Ollog)/
3/2 n) factor.
4.1 Average Degree Lower Bound
We introduce few intermediate results before giving the proof of Theorem 4 that the point set of Theorem doos not have any duplicate points with high probability. Doing so simplifies our analysis no "lie-breaking" will be needed when Algorithm is run on input zij.
First, we observe
Claim 5 (No Repeated Points). Let I1,,... ................................ ,r, be distributed as in Theorem As long d 2 e1 log for a universal constant C1 then with probability at least 99/ /000, all vectors in this set are distinct.
The claim follows from simple probability calculation and union bound see Appendix A
We next define notion of a neighborhood of point, which includes all points within a certain radius. Definition 6 (Fixed Radius Near- Hear-Neighborhoodd) Consider the setting of Theorrm Let Oj be the subset of vectors in 3 In (including 2j itself) with (1i, 2 Ca /og where en E [1/3,1] is some value (that may depend on n) which we will specify later.
Note that, for any Ji E [11, ||,, xy13 = d 2(x,, Byy), so Oj contains set of nearest neighbors to j in the Euclidean distance. Importantly, however, the definition used in this section is different from the Nm. (j) notation used in the previous section, since O2 is not of fixed size.
Using the distance-based permutation characterization of navigability given in (T). we can observe that, in order for greedy routing make progress towards target 2,,, every node in the neighboroddd Oj needs an edge to another node in the near nuuu-neighbohhoo, closer to Ij. Formally:
Claim (Required Connections Within Neighborhoods). Consider the setting of Theorem and assume that Zi...., Fn E {-1,1} are distinct. Any navigable graph G for ZI.... Zn requires |0,1 - 1 edges in Oj x O₂ for each j.
Proof. For G to be navigable, for any i E O, closer j. and thus is also in Oj. Thus, there are at least |O,| - edges in O, x O,,
\ (i). there must be edge from to some node that
We next make two claims about the near neighborhoods of Definition 6 when T1s.... In are random points in {-1, 11:; that I) they are large with high probability and 2) that they have low overlap with high probability. Together with Claim 7 these imply that any navigable graph G' for æ1. In requires large number edges, proving Theorem 4 We first formally state the claims and prove Theorem using them. We then prove the claims in Section 4.2]
Claim 8 (Neighborhoods are Large). Let 21...., be as Definition 6 As long as 2 Ci log n for a universal constant C₁ with probability at least 09/100, for all ,11 2 /n/6.
In be as distributed as in Theorem 4 Ann let Oj
In. be distributed as in Theorem Aand let O be as in Definition O As long as 2 Ci log n for universal constant C₁, with probability at least 99/100, 1000 for all i + j. 10, < 10 m0x (log n, v Jugm for some universal constant c.
Claim 9 (Neighborhood Intersections are Small). Let Z1....,
Claim 8 estaabishes that O, contains the O(v nearest neighbors to zy,, which a consequence of our choice of radius in Def. 6 If each O₂ were just an independent random set of O (vzz) nodes, then we would expect that for any i + j. JO, O (11). Lee., our neighborhoods would have small overlap, which is the key property we need to prove lower bound. An overlap of O(1) would imply that 3/2)) edges are needed to satisfy the requirements of Claim 7 Of course, each O₂ is not an independent random set in reality. Specifically, if x; and 2; have large inner product, O and O, will be correlated, so we expect that IO, n O5í will be larger. Claim 9 shows that for large enough d, such strong correlations are unlikely happen and thus we still expect JO, n n to be fairly small.
Proof of Theorem 4 First note that we can assume that d 2 ci log for some large constant C, as otherwise we will have e > 3/2 and the lower bound becomes vacuous. Accordingly, the conclusions of Claims 5 and 9 all hold for Ii, In with probability > 9/10 10 by union bound.
7

---

We will use these claims to show that any navigable graph for #1,.... requires 22(33/2-) edges.
Consider any navigable graph G EV. For any edge (u, u) E, let Wu,v = Ii u, v E 0, be the number of near neighborhoods that u and v both belong to. I.e., Wa, is the number of nodes
for which (u, e)) E Ø x Oj. By Claims 7 and 8
we must have
3/2
31/2
Σ (u,D)E
Wu.v
10,1-12 -
n2 2
(2)
6
12
3
where we use in the last step that I n22/2/12 for large enough n.
Further, W aO no since u and both lie O exactly when j lies in both O, and O,. Thus,
by Claim Wu,e I 10 max(log n, n noologg// n/d) for all u, v. Combined with (2 this gives:
n 1/22112
E
12n 2/(2))2-c)
10 max n, n v nog
for max(
log logn log
ev eellooooo log n/d).
This proves the theorem.
4.2 Probabilistic Claims about Near Neighborhoods
We now prove Claims 8 and We will use very sharp bound on the CDF of a binomial distribution, given by Ahle 2017 and attributed to Cramer [Cramér 2022). This a quantitative version of central limit theorem, saying that the binomial CDF is close to the normal CDF, up to some small error. tighter than more general bounds like the Berry-Esseen theorem. We give a proof of our exact statement of the bound in Appendix [A]
Fact 10 (Binomial CDF Bound, 2.20 of [Able 2017 Let F.(-) be the CDF of mean centered
binomial random variable with trials and success probability 1/2. There are universal constants C1 C2 such that, for any x satisfying 61 S x S Vt/e1.
1 3x
(14
1 - 1- m I F vt/2)
-e
We will also that, with high probability, pair of our random vectors has too high of inner product. This will be required to prove Claim / i.e. that all near neighborhoods have small overlap. The claim follows directly from standard Chernoff bound and union bound over all pairs i.j.
Claim 11 (Vectors are Not Too Similar). Let 21,-..; Fn be distributed as in Theorem 4 As long as 2 ei log n. for a universal constant C1, with probability at least 99/ 99/100, for all i + 3. (0,, S C₂ / log n for some fixed constant Cu-
Finally, we require the following technical claim, which we will use set C₁ Definition Our goal is to ensure that the probability of vector being in the near neighborhood of another is (11/vn)
Claim 12. For any large enough n, there is some value of c E [1/3, 1) such that
1
exp(-c² Inn) =
Vinn
Vn.
Proof. Observe that if we set c 1, then
exp(-
Inn)
Mnn
nvinn Vn
Further, we set c = 1/3, we have for large enough n,
exp( - Inn) Vinn exp( exp(-1/91n)) In
Vln 1/9 vn
Thus, for some setting of e [1/3, 1] the claim holds.

---

Proof of Claim 8 Fix some zj. Then for any i * j, the event that i Og is exactly the event that binomial random variable Bin(d, 1/2) exceeds its mean by 2 c V.ddln n/2. Le., letting Fa(-) be the CDF of the mean centered binomial random variable, we have
Pr(x; E O2) = Fal Fa(-ch v /
Plugging in the lower bound of Fact 10 we have for some constant co:
ch
(1+ C I Inn
Pr(x; E EO₂) 3 cp Vlnn
exp
lun
d
Using that 2 e1 In n for some sufficiently large constant C1 1 c2e lun 12 we can set to some value in [1/3, 1] to obtain:
E [1, 2]. Then, by Claim
Pr(z; e 00)) 3Ch
(4)
3/n
From (4) the claim follows by noting that the events i E O, are independent and each happens with probability at least 3/n so E. [|O,1] 2 vn/3. Thus, by Chernoff bound, with probability least
1- m 10 2 vn/6. Taking a union bound over all j then gives that, for sufficiently large n, 10,1 2 vn/6 for all with probability at least 99/100, giving the claim.
Proof of Claim 9
Fix i * j and consider some i which is not equal to either i or j. Let be the number of positions in which v; and z- take the same value. Note that, assuming the event Claim
11 holds, S d/2 + Cu cavd log n/22 Denote d/2 + Ca /d log//g//2 n by μ.
By Definition 6 to have I& E O nO we need min (Z&,, xz), (x (x), 2 Ch olg n. That is, we need z& to match each of x; and x, in at least d/2 cn/2 2- /d dog n positions. On the d- 2 positions where 2; and z, differ, the best case scenario (i.e.. the scenario maximizing min( (Ix, 24), (ax 2z))) when 24 matches exactly half of these positions for each of x; Fy (i.e., matches d-s positions).
Assuming this case, to have Is E O, no,, on the positions where x; and Ty are identical, a must match 2/2 + ca/2- Vd n positions. The probability of this happening is equivalent the probability that binomial random variable with trials exceeds its mean by 2 ch/2 Vdlogy Since S μ., we can upper bound this probability by the probability that a binomial random variable with y trials exceeds its mean by cn/2 Vdlog n. We rewrite the upper bound as:
cn/2 Vdlogn cn/2 vd/u Vulogn
Ch V2
log n,
1
log n
where we use
d/2 1
Via Fact 10
now upper bound our probability of interest by:
1tcu / loca
1 + Ca
logn
(1-
ch log
202eh log n2
Pr(xx &0,n0,)
exp
Veen Vlgn
cu V logn
(1 + Ca log
Observe that since in the claim require d log for large constant C1. we have that So, simplify the above to:
Jog 1 151 111+a Gu o
22
ci log
202c log
Pr(za E &0,OO,)
exp
Ch llgn
1 + Cu
logn
20ge llg 1
22
C2c logn
exp
logn
1
1
Chylogn
(1
czeh logn
(1 (1+ (+Cca/ ca
log

---

Now, since set d 2 61 log n for large constant 01, can ensure that have that log for any small constant 63. Using this fact, along with the fact that μ 2 d/2, we have:
d
S Cg
Vlog vd
(1 (1- 5c V
20grr, llog (1
log
log
[1 + cach log
(1+ Cu log
1 50
lorn d
logn 1 Cu
d
For the second inequality, we used the fact that
1x=5xx
2 1 2x for all x. Next, setting
(1+.62((422)
Ch [1/3, 1] exactly as so that Vlug
exp
2
logn n
(1+ ezc log )
vn
we have:
-ch logn.
(1 (1+
c2 log n Lokm)
(1- 20 V
log n
Pr(m E E0;)0,)
exp
Oh Ck Vloon
d
V2
(1+ c2 log d
log
<
exp
2c log
C/72
d
4v2
clog 3/2 n
4v2
n e
exp
d
for some constant c. Finally, observe that, conditioned on 2; and I; sharing x entries, the event , is independent for each rg- Thus, by a standard Chernoff bound, with probability at Jg E O, O,
for some large constant c' Union least - 1/n"', we have O, S 10 max(log n, no Ing.
bounding over all (nn²) pairs j then gives the claim.
4.3 Maximum Degree Lower Bound
In Theorems and 2 we focus on the average degree of navigable graphs. While reasonable metric, we might also be interested in the maximum degree, which governs the worst-case complexity of single step of the greedy algorithmss Here give simple argument showing that unfortunately, a worst-case input instance, it is not possible to achieve maximum degree better than the trivial n 1 given by the complete graph.
Theorem 13. There exists set of points Z1,..., In E Rd for d = O(log n) such that any navigable graph for these points under the Euclidean metric has maximum out out- degree
Proof. First prove the bound for high dimensional point set. For all < let æ, be a standard basis vector with a in position Let w, be the all zeros vector, As we can see, In has Euclidean distance from Ti, Fany.....nn111 -n
On the other hand, for all + j where i,j of n, || x1|2 = /2. In other words, Fn is the closest neighbor to each of æ1, ... Fn-1- It follows that any navigable graph must contain an edge from Ij to each of these points, resulting in maximum degree n.
To extend the construction to low dimensions, we simply use the Johnson-Lindenstrnn embed the point set above into elog n dimensions. As long as the constant is sufficiently large, all distances will be preserved to within error, say, 1..1. So, Zn will still be the nearest neighbor of all other points, and we will still require have out-degree n 1.
Lemma to
Acknowledgements
Christopher Musco was supported in part by NSF award IIS-2106888. Cameron Musco was supported in part by NSF award CCF-2046235 and an Adobe Research grant.
References
Thomas Ahle. Asymptotic tail bound and applications. tails pdf 2017.
https://thonasahle..com haomm/ppers////
10

---

Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, 1lya Razenshteyn, and Ludwig Schmidt. Practical and optimal LSH for angular distance. In Advances in Neural Information Processing Systems 28 (NeurIPS), 2015.
Gabriel Arpino, Daniil Dmitriev, and Nicolo Grometto. Greedy heuristics and linear relaxations for the random hitting set problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM)) 2024.
Sunil Arya and David M. Mount. Approximate nearest neighbor queries in fixed dimensions. In Proceedings of the Symposium Discrete Algorithms (SODA), 1993.
Marián Boguñá, Dmitri Krioukov, and K. C. Claffy. Navigability of complex networks. Nature Physics, 5(1):74 90, 2009.
Harald Cramér. On new limit theorem in probability theory (translation of 'sur nouveau théorème-limite de la théorie des probabilités'), arXiv:/802.05988 2022. Translated by Hugo Touchette.
Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. Fast approximate nearest neighbor search with the navigating spreading-out graph. Proceedings of the VLDB Endowment, 12(5):461-4744 2019.
Sariel Har-Peled. A replacement for voronoi diagrams of near linear size. In Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2001.
Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the ACM Symposium Theory of Computing (STOC), 1998.
Piotr Indyk and Haike Xu. Worst-case performance of popular approximate nearest neighbor search implementations: Guarantees and limitations. Advances in Neural Information Processing Systems 36 (NeurIPS), 2023.
Herve Jégou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neighbor search. IEEE Transactions Pattern Analysis and Machine Intelligence, 33(1):117-128, 2011.
Jeff Johnson, Matthijs Douze, and Hervé Jegou. Billion-scale similarity search with GPUs. IEEE Transactions Big Data, 7(03):535-55) 547, 2021.
Victor Klee. On the complexity of d-dimensional Voronoi diagrams. Archiv der Mathematik, 34(1): 75-80, 1980.
Jon Kleinberg. The small-world phenomenon: an algorithmic perspective. In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC), 2000a.
Jon M. Kleinberg. Two algorithms for nearest-neighhor search in high dimensions. Proceedings of the 29th Annual ACM Symposium Theory of Computing (STOC), 1997.
Jon M. Kleinberg. Navigation in a small world. Nature, 406(6798):845 845, 2000b.
Eyal Kushilevitz, Rafail Ostrovsky, and Yuval Rabani. Efficient search for approximate nearest neighbor in high dimensional spaces. In Proceedings of the 30th Annual ACM Symposium Theory of Computing (STOC), 1998.
Thijs Laarhoven. Graph-based time-space trade-offs for approximate near neighbors. In Proceedings of the 34th Annual Symposium Computational Geometry (SoCG), 2018.
Yu A. Malkov and Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 4244)8824 2020.
Yury Malkov, Alexander Ponomarenko, Andrey Logvinov, and Vladimir Krylov. Approximate nearest neighbor algorithm based on navigable small world graphs. Information Systems, 45:61-69 1-68, 2014.
Stanley Milgram. The small world problem. Psychology today, 2(1):60-67, 1967.

---

Liudmila Prokhorenkova and Aleksandr Shekhovtsov. Graph- practice theory. Proceedings of the 37th International Conference on Machine Learning (ICML), 2020.
Graph-based based nearest neighbor search: From
Suhas Jayaram Subramanya, Devvrit, Rohan Kadekodi, Ravishankar Krishaswamy, and Harsha Vard- han Simhadri. DiskANN: fast accurate billion-point nearest neighbor search on single node. In Advances in Neural Information Processing Systems 32 (NeurlPS), 2019.
Godfried T. Toussaint. The relative neighbourhood graph of a finite planar set. Pattern Recognition, 12(4):261-268, 1980.
Carlo Vercellis. A probabilistic analysis of the set covering problem. Annals of Operations Research, 133):255-27,, 1984.
Dunean Watts and Steven Strogatz. Collective dynamics of 'srall-world" networks. Nature, 493 1998.
12

---

A
Omitted Proofs
Below we gives the proof' of some simple technical claims required to prove our main lower bound, First, we prove Claim 5 which establishes that, with high probability, the hard input distribution of T'Thorem produces set of distinct points..
Theorem 4
Claim 5 (No Repeated Points). Let , Fn be distributed as in Theorem As long d 2 e log for a universal constant C1 then with probability at least 99/ 100, all vectors in this set are distinct.
Proof. Consider two points 2;, 2.- The probability that these points are identical equals 1- S n Then by union bound over all pairs i, j. we have that all points are distinct with probability at least which is greater than 99/100 for sufficiently large c1.
Next we give short derivation of Fact T0 which gives sharp bound on the CDF of a binomial distribution, and used in proving Claims and
Fact 10 (Binomial CDF Bound, 2.20 of [Ahle 2017). Let F+()) be the CDF of mean centered
binomial random variable with trials and success probability 1/2. There are universal constants C1, C2 such that, for any satisfying S S vt/c1.
(1+
1
1 - J S
I F v1/2)
3z
Proof. Applying 2.20 of Ahle 2017
with
1/2 gives that
F-(xx- Vi/2)
1
1 -ID
222
2 b
(1
1 52
exp
2
for some constant c. where use the notation (aallb) def log(a/b) + (1- log((1 a)/(1 b)). This is the KL divergence between two Bernoulli distributions with success probabilities a and b. We can then apply equation (3.13) of Ahle 2017 claim that, for a constant C22
x²
D
2vi 2
2t
C2 21
Plugging back in, we have that for constants e and e2.
1 exp
(-2 11 C227 2222)) )) 11
(- x²
(1) + vt)
1
x )
F((-x Vi/2)
V2Hx
If we assume C1 I S vi/e for large enough constant e1 then 32 S
(1 (1-6 c
( + v1)
vuzz
and
(1+c [/22 + 3x
)
- which completes the proof.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract states the main theoretical contributions of the paper accurately, as does the introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Limitations of our theoretical model are discussed concretely in Section 1.3. We suggest possible extensions our model and analysis to address such limitations.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
14

---

Answer: [Yes]
Justification: Each theoretical result in this paper is supported with a full set of assumptions and an associated proof citation.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
This paper does not include any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
15

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
This paper does not include experiments requiring code or data.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "pipsscc/puullc//uuu /otee//guudddeeeedSuuuubmiibii ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
16

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors Is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: There violations of the NeurIPS Code of Ethics in this paper.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: Nearest neighbor search is fundamental and long- studidd algorithmic problem. Algorithms for the problem thus have societal impact, many positive, but possibly negative. However, since work focuses on theoretical foundations of the nearest neighbor search problem, difficult to comment a meaningful and concrete way on its potential for societal impact. We believe its main impact will be better scientific understanding of existing methods based on search in navigable graphs.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
17

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This paper does not use existing assets.
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcone com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
18

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
19


Reviews:
[{"review_id": "Q32KlIZpxP", "reviewer": "Reviewer_Z5U8", "summary": "The paper provides a theoretical framework for understanding and constructing navigable graphs for high-dimensional nearest neighbor search, and the authors establish some of the first upper and lower bounds for high-dimensional point sets.", "questions": "Q1: Existing ANNS graph indexing algorithms do not necessarily need to ensure that the graph is fully navigable, as the query does not need to be considered a point in the graph. As long as the graph index can navigate to the vicinity of the given query vector, it largely meets the requirements. Therefore, the navigability of the graph is really important to ANNS?\n\nQ2: It is better to make the proof or explanation more clear and detailed. For instance, providing more examples or describing the proof process in more formal language. This could be more helpful for someone who is not familiar with the theoretical research.", "limitations": "yes.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "S1: The article establishes both upper and lower bounds for navigable graphs and utilizes anti-concentration bounds for binomial random variables.\n\nS2: The authors provide a foundational analysis that can influence the design and optimization of state-of-the-art ANNS methods, offering insights that could lead to more efficient graph-based solutions for high-dimensional data.\n\nS3: The article uses a distance-based permutation method to analyze the lower and upper bounds of the navigable graphs, which is a highlight of the article.", "weaknesses": "W1: The method proposed in the article is not generalizable to the construction methods used by current graph-based approaches.\n\nW2: The proposed graph construction algorithm has not been compared with existing graph construction algorithms. Such a method may only be useful for theoretical analysis rather than for building a practical application.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful comments. We address the two specific questions below.\n\nQ1: A desirable property of an ANNS algorithm is that, if the vector queried, $q$, is in the dataset, then the algorithm should return exactly that vector. This behavior is also required for any algorithm to give a multiplicative approximation guarantee, i.e., any algorithm that always returns a vector $y$ satisfying $d(y,q) \\leq \\alpha\\cdot \\min_{i\\in 1,\\ldots, n} d(x_i,q)$ for $\\alpha \\geq 1$. In particular, if there is a point $x_i$ such that $d(x_i,q) = 0$, then for any finite $\\alpha$, a multiplicative approximation algorithm must return that point. \n\nA major open research challenge is to prove strong multiplicative approximation guarantees for graph-based ANNS methods, similar to those available, e.g., for locality sensitive hashing. The argument above implies that navigability is *necessary* to achieve this goal. As the reviewer points out, it may also be reasonable to accept a weaker notion of approximation. However, we believe that the importance of multiplicative approximation in prior work on NNS supports the importance of navigability, and makes navigability a natural starting point to build on. \n\nMore broadly, while existing graph-based near neighbor search methods like HNSW *usually* work fairly well in practice, they do fail on a subset of queries. One reason to explore navigability is to better understand these failures, and ultimately to make existing algorithms more reliable.\n\nQ2: Thank you for the feedback. We will keep this in mind when editing the paper. Please let us know if there are any specific proofs that could benefit from editing, or any examples that you recommend would help the reader further understand our work.", "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": "", "extra_scores": {}}, {"review_id": "kFE1nIqBO1", "reviewer": "Reviewer_MezS", "summary": "This paper analyzes graph construction for greedy graph-based nearest neighbor search. First, the very general setup assuming an arbitrary similarity function is considered. In this case, it is shown that it is possible to construct a graph with an average degree at most $2 \\sqrt{n \\log n}$ which guarantees that the greedy search returns the nearest neighbor if the query coincides with an element of the dataset. Then, it is shown that the obtained average degree is close to the best possible since there are examples when the average degree cannot be better than $n^{\\frac{1}{2}-\\epsilon}$.", "questions": "I do not have any questions in addition to the comments listed in the previous above.", "limitations": "Limitations are discusses in the paper.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "NNS is an important problem. Graph-based algorithms are widely used for this task and yet there is not much theoretical analysis of their performance. This paper addresses this gap and considers a very general setup where the dimension is essentially not limited (in other words - an arbitrary similarity function is given). While the main theoretical results are relatively simple (not much can be done in such a general setup), I enjoyed reading the paper. All results are clearly stated and motivated, the proofs are easy to follow. The related work is well described. Importantly, limitations are clearly mentioned in the text: the results assume that the query coincides with an element of the dataset, which is a significant limitation, as stressed in line 105.", "weaknesses": "Theorem 1 limits the average degree but does not say anything about the complexity of the search, which also depends on node degrees. It is shown in the paper that there are cases when the maximum degree in a graph is of order $n$, which means that the worst-case performance can be of order $n$ for this general setup. This can be a limitation of the considered general setup and some additional requirements can be needed to show something more feasible and practically applicable.\n \n\nThe considered general setup (that does not require the triangle inequality and is essentially based only on the ranking of neighbors) is similar to the one proposed in [1]. I think discussing this relation would improve the presentation. Also, [1] uses a relaxed triangle inequality to obtain better bounds (but for relatively small dimensions only).\n\n[1] Goyal et al. \"Disorder inequality: a combinatorial approach to nearest neighbor search.\" WSDM 2008.\n\nMinor comments:\n- Theorem 1 repeats two times in the main text, this repetition can be avoided: e.g., in the introduction only an informal description can be given.\n- l263: \"gives\" should be \"give\"\n- l391: $x$ should probably be $x_j$ here", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the feedback. We address a few of the points raised below:\n\n-   We agree with the reviewer that an important next research direction is to look beyond the graph’s degree, and at more accurate proxies for the efficiency of near-neighbor search. For example, a natural metric might be the sum of degrees along any path taken by greedy search. It would be reasonable to study the average or worst case behavior of this metric for navigable graphs. We do feel that average degree serves as a good theoretical starting point, as it allows for direct comparison with prior work on low-dimensional data points, and is “simple”. We hope our progress on understanding average degree will lead to further theoretical progress on other graph metrics.\n\n-    Thanks very much for pointing out the Goyal et al.  reference, which we missed. Indeed, our general setup falls exactly into what they call “combinatorial near neighbor search”. We will add additional discussion to the final version of the paper.", "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": "", "extra_scores": {}}, {"review_id": "PdLwJfYt9L", "reviewer": "Reviewer_Jtod", "summary": "This paper studies the problem of constructing navigable graphs over high-dimensional point sets. Specifically, a randomized algorithm and a deterministic algorithm are given to construct such graphs within almost the same time complexity. Besides, theoretical results demonstrate that both algorithms can achieve the average degree is O(\\sqrt{nlogn}), which nearly matches the lower bound.", "questions": "Q1. Navigable graphs have several applications now, but different applications may have different requirements on the efficiency, effectiveness, or their trade-off. However, the (potential) application scope of the proposed algorithms is unclear. Are they designed for exact NNS or approximate NNS? Are they designed for NNS only, or can it be extended to k-NNS?   \n\nQ2. Section 1.1 claims that “the computational efficiency of the graph-based methods … motivating the need for sparse navigable graphs”, which explains the main motivation to study this work. However, I found it unconvincing. First, some methods (eg HNSW and its variants) have already been demonstrated to be very efficient, so it might be meaningless for them to use the proposed algorithms. Second, the meaning of computational efficiency is a little vague. Take  HNSW as an example, its efficiency include two aspects: time efficiency for construction and time efficiency for query. Which one do you indicate here? Third, as mentioned in this paragraph, quite a few graph-based methods are essentially approximate solutions, so there will usually be a consideration on the trade-off between efficiency and effectiveness. Due to the reasons, I think the motivation will be more convincing, if the authors can provide more motivation studies here.   \n\nQ3. Two algorithms are proposed to tackle the same problem: a randomized one and a deterministic one. Moreover, their time complexity are both O(n^2(T+logn)), so it becomes meaningful to provide more discussions on their strengths and weaknesses.   \n\nQ4. The paper has no experimental evaluation, so it is hard to tell whether their proposed techniques can be helpful in practice.   \n\nQ5. The theoretical analysis mainly concentrates on the average degree, indicating the sparsity of graphs. There are other options to represent the sparsity, eg the maximum degree. Then, why selects average degree instead of other potential metrics? Please give more explanations.   \n\nQ6. Since the paper is related to the area of high-dimensional nearest neighbor search, there should more comprehensive literature review of recent studies on this topic, such as    \n[R1] RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search. SIGMOD 2024.    \n[R2] LiteHST: A Tree Embedding based Method for Similarity Search. SIGMOD 2023.      \n[R3] Turbo Scan: Fast Sequential Nearest Neighbor Search in High Dimensions. SISAP 2023.   \n\nQ7. The structure of this paper can be improved by summarizing the conclusion and identifying the future direction.", "limitations": "Please refer to the weaknesses and questions.", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "S1. The paper studies an important problem.   \nS2. Several interesting theoretical results are given   \nS3. The main ideas are easy to follow.", "weaknesses": "W1. There is no experimental evaluation.   \nW2. More related work should be reviewed.   \nW3. Some technical details require clarifications.   \nW4. A section of conclusion and future direction is missing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the detailed review. We provide responses to the specific questions below:\n\nQ1: There has been little formal work on connecting the property of navigability to near neighbor search. Indeed, the standard definition of navigability (which we study in our paper) only ensures that greedy search returns an exact NN for a query *in the dataset*. Navigability does not ensure greedy search works well for approximate NNS, k-nearest neighbor search, or exact nearest neighbor search for points not in the dataset. This important caveat is discussed in Section 1.3 of our paper. \n\nNevertheless, we focus on navigability because it is often highlighted as a desirable feature in work on graph-based nearest neighbor search methods. For instance, navigability is essential for greedy search to obtain any bounded multiplicative approximation guarantee for approximate near-neighbor search (see our response to Reviewer Z5U8 for a detailed explanation of this fact). That said, we think an important research direction is to understand “generalized” notations of navigability that connect to the performance of approximate NN search, k-NN search, etc. For example, we are currently working on understanding notions of navigability that imply the convergence of the popular “beam search” method, a generalization of greedy search.\n\nQ2: We agree that graph-based methods have already been shown to be extremely efficient in practice. In fact, this is a major motivation for our work. Despite their empirical success, there is a lack of theoretical justification for this performance. Our paper aims to bridge this gap by enhancing the theoretical understanding of why graph-based methods are so effective, aligning with the goals of many related papers referenced in Section 1.3. We take a step in that direction by improving our theoretical understanding of navigability. We are not suggesting that our algorithms are ready to be used in practice in place of the effective graph-construction heuristics already used in methods like HNSW. \n\nIn terms of computational efficiency, we were specifically referring to computational efficiency of the search, although we agree that the efficiency of graph construction (and efficient maintenance under dynamic updates) is important as well. We will clarify this in the paper.\n\nQ3: We will add further discussion of this point. The deterministic algorithm is “better” in that it has no chance of failure, and obtains a slightly smaller constant on the average degree. However, we chose to include the randomized algorithm because we think it is conceptually easier to understand, and aligns with prior strategies for constructing navigable graphs: we simply union together a near-neighbor graph and a random graph. \n\nQ4: As mentioned in our response to Q1, we do not recommend applying our methods in practical settings. The primary goal of this paper is to enhance theoretical understanding, which we believe may in turn result in further improvements to the approaches currently used in practice.\n\nQ5: This point is discussed further in Section 1.3 of the paper and Appendix B. In short, we agree that addressing other measures of sparsity is a great direction for future research. Maximum degree itself is a difficult one to work with, as there is a lower bound of $n-1$ (proven in Appendix B).\n\nQ6: Thank you for the suggested references! \n\nQ7: We summarize our contributions and elaborate on future directions in our “Outlook” section (Section 1.3). This could be moved to later in the paper to serve as a conclusion (possibly with some additional discussion).", "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": "", "extra_scores": {}}, {"review_id": "WWikHiJMnn", "reviewer": "Reviewer_damy", "summary": "The article establishes upper and lower bounds for the average degree of navigable graphs in high-dimensional case. In particular, a method for constructing a navigable graph with average degree $\\mathcal{O}(\\sqrt{n \\log n})$ for any set of $n$ points is provided. In addition, they provide a random point set for which (with a high probability) it is not possible to build a navigable graph with average degree $\\mathcal{O}(n^\\alpha)$ for $\\alpha < 1/2$.", "questions": "If I understood correctly, you prove via a counterexample that it is not possible to build a navigable graph with an average degree smaller than $\\mathcal{O}(\\sqrt{n})$? for all possible sets of $n$ points? But this does not rule out that it would be possible to do it for a set of $n$ points for which certain additional assumptions holds?", "limitations": "The authors fairly address the limitations of the work.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "Theoretical limits of the navigable graphs is an important question, since they are widely applied in state-of-the-art approximate nearest neighbor algorithms. The article provides sharp bounds for the average degree of the navigable graphs. The technical level of the article is high.", "weaknesses": "The article is motivated by the observation that the state-of-the-art methods for approximate nearest neighbor search utilize navigable graphs. However, as the authors acknowledge, these graph are in practice only approximately navigable, and use beam search to retrieve approximate nearest neighbors instead of a simple greedy search. Thus, the bounds provided are not directly applicable to these algorithms, but consider simplified version of the algorithms.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review. Regarding your question, your understanding is exactly correct. Some point sets admit sparser navigable graphs. For example, if all points lie on a $d$-dimensional hyperplane, then the Arya, Mount  result discussed in Section 1.1 implies that we can find a navigable graph with degree $2^{O(d)}$, which can be less than $O(\\sqrt{n\\log n})$ for small values of $d$. That said, our lower bound does not require an “adversarial” set of points: it holds with high-probability for a set of random $\\pm 1$ vectors in $O(\\log n)$ dimensions. Of course, “real data” often does not look random. An interesting question for future work might be to understand if there are natural measures of complexity of a point set that dictate the minimum degree of a navigable graph for that set.", "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": "", "extra_scores": {}}]

Author rebuttal:
We would like to thank all of the reviewers for their thoughtful reviews and feedback. We address all specific questions in our individual responses below.

In general, we want to emphasize that our work can be viewed as a meaningful starting point to obtaining a better theoretical understanding of graph-based near neighbor search. Up until now, there has been very limited theoretical work on navigable graphs for high-dimensional data ($d > O(\log n)$). By making a first theoretical step on this topic, we hope to build a foundation for further theoretical work that can address many of the questions raised by the reviewers. For example, we plan to explore (and hope others will explore) different metrics of graph sparsity, the approximate search problem, generalizations of greedy search like beam search, and more.

Meta-review: This paper aims to bridge our gap in theoretical understanding of very practical graph-based nearest neighbor search (NNS) methods in high dimensions. It provides a very clean theoretical view of the problem and proves almost matching lower and upper bounds on the size (average degree) of so-called navigable graphs for high-dimensional point sets.

There is no consensus among reviewers in the assessment of this paper. The main strengths they highlight are:
– Important problem.
– Tight bounds.
– Interesting techniques.
– Well written paper, easy to read.
The main weak points mentioned are:
– It is still quite far from explaining what the methods actually used in practice do.
– No impact on developing new practical solutions, no experimental evaluation.
– Bounds in terms of average degree and not max degree.
– Some related work not discussed.
– Some parts are hard to follow.

Based on the rebuttal, I believe the authors will discuss the missing related work in the next version of the paper. I also put little weight on the argument regarding experiments – I view this paper as a pure theory paper, whose goal is to increase our understanding of a certain phenomenon, and not to directly develop new practical algorithms.

The paper propose a very natural model to analyse graph-based NNS, and gives (almost) tight bounds in this model. It may seem somewhat disappointing and unimpressive that these bounds are far from what we observe in practice, but this only shows that this natural model is too simplistic, and we need to look for more elaborate ways to model the problem. It is an important first step that had to be made on our way to build our theoretical understanding of the power of graph-based NNS (in high dimension). Therefore I recommend to accept the paper. I believe it is going to inspire further notable work on this topic.
Decision: Accept (poster)