Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits

Authors: haya  diwan
jinrui  gou
cameron  musco
christopher  musco
torsten  suel
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 19:14:05

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.

Main paper: 
 introduction: 
 The concept of a navigable graph has arisen repeatedly over the decades, perhaps most famously in Kleinberg's work on understanding Milgram's "Small World" experiments from the 1960s [Kleinberg, 2000a ,b, Milgram, 1967] . Concretely, suppose we are given n points x 1 , . . . , x n ∈ X in some input domain X , a distance function D : X × X → R ≥0 , and a directed graph G = (V, E), where each vertex in V = {1, . . . , n} is associated with one of our points. G is said to be navigable if the standard greedy routing algorithm successfully finds a path between any starting vertex s ∈ V and any target vertex t ∈ V . 1 In particular, letting N (s) denote the out-neighbors of s, this algorithm first navigates to r ∈ N (s) which minimizes D(x r , x t ). At each subsequent step, we navigate to the out-neighbor of the current node that minimizes the distance to x t , terminating once we reach x t , or if no neighbor has an associated point that is closer to x t 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 x i plays the role of, e.g., the physical coordinates of a server or individual and D is the standard Euclidean distance or some other metric [Boguñá et al., 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 ].More recently, significant work has studied the problem of constructing navigable or "approximately" navigable graphs given a point set x 1 , . . . , x n ∈ 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 graphbased approximate nearest neighbor search methods such as DiskANN [Subramanya et al., 2019] , the Hierarchical Navigable Small World (HNSW) method [Malkov and Yashunin, 2020, Malkov et al., 2014] , and the Navigating Spreading-out Graph (NSG) method [Fu et al., 2019] . 2 Such methods have shown remarkable empirical performance, outperforming state-of-the-art implementations of popular approximate nearest neighbor search algorithms such as product-quantization and locality-sensitive hashing [Johnson et al., 2021 , Jégou et al., 2011 , Indyk and Motwani, 1998 , Andoni et 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 R d 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 O(1) in dimension d = 2 (since it is planar) it can have average degree O(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 to be navigable for any point set in R d under the Euclidean distance and have average degree 2 O(d) . 4 While this results in a sparse navigable graph for small values of d, the degree bound is no better than that of the complete graph for d = Ω(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.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 1. For any input domain X , point set x 1 , . . . , x n ∈ X , and distance function D : X ×X → R ≥0 such that D(x i , x i ) = 0 for all i and D(x i , x j ) > 0 for x j ̸ = x i , it is possible to efficiently construct a directed navigable graph with average degree at most 2 √ n ln n. Moreover, the graph has the additional "small world" property: greedy routing always succeeds in at most 2 steps.Theorem 1 establishes that, even in arbitrarily high dimension, it is possible to beat the naive completegraph solution, which has O(n 2 ) edges (average degree n). The result is proven in Section 3. It is based on an simple construction, reminiscent of existing techniques for building nearest neighbor search graphs: we take the union of a O( √ n log n)-nearest neighbor graph, and a random graph with average degree O( √ n log n) [Malkov et al., 2014 , Kleinberg, 2000b , Subramanya et al., 2019] .Surprisingly, Theorem 1 holds for essentially any distance function, even if it is not a metric. Moreover, the construction is efficient: the navigable graph can be computed in O(n 2 (T + log n)) time, where T is a bound on the cost of computing D(x i , x j ) for any i, j. Given the generality of Theorem 1, we might expect that navigable graphs with even fewer edges could be constructed under additional assumptions -e.g., if we considered only the special case where the input domain is R d and D is the Euclidean distance. Our next result rules this out when d = Ω(log n). In particular, we show: Theorem 2. Let x 1 , . . . , x n ∈ R d be vectors with i.i.d. random ±1 entries, and let D(x i , x j ) = ∥x i -x j ∥ 2 be the Euclidean distance. For any parameter δ > 0, if d ≥ c δ 2 log n for a fixed constant c, then with high probability, any navigable graph for x 1 , . . . , x n requires average degree Ω(n 1/2-δ ).Theorem 2 is proven in Section 4. It is a corollary of our more general Theorem 4, which also implies a lower bound of Ω(n 1/2 / log n) average degree when d = Ω(log 3 n). The proof starts with a straight forward observation: in order for greedy routing to make progress towards a destination node x i , any node within the k-nearest neighbor set of x i , for any k, must include an edge to some other node in that set (possibly x i itself). Using sharp anti-concentration bounds for binomial random variables [Ahle, 2017 , Cramér, 2022] , we argue that, when k = O( √ n) and when x 1 , . . . , x n ∈ {-1, 1} d 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( √ n), and thus have expected overlap close to 1. This small overlap means that few edges can be 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 R d , it is possible to construct navigable graphs with 2 O(d) 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 = c log n for a small enough constant c.Together, Theorems 1 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 on 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 a 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 ∈ X converges on an α-approximate nearest neighbor x j satisfying D(q, x j ) ≤ α•min i D(q, x i ) for some α ≥ 1. This is the sort of guarantee that locality sensitive hashing and other methods can achieve with query time that is provably sublinear in n, i.e., without needing to directly compare q to all vectors x 1 , . . . , x n [Kleinberg, 1997 , Kushilevitz et al., 1998 , Indyk and Motwani, 1998 , Har-Peled, 2001] . Importantly, if regular greedy search is applied from an arbitrary starting node, navigability is a necessary condition for α-approximate nearest-neighbor search. In particular, for any finite α, if q ∈ {x 1 , . . . , x n }, min i D(q, x i ) = 0, so we must return q exactly. However, navigability is not a sufficient condition for greedy search to succeed, as it does not guarantee any level of approximation for queries q that are not in {x 1 , . . . , x n }. For some initial work on this more challenging problem, we refer to the reader to Laarhoven [2018] , Prokhorenkova and Shekhovtsov [2020] , and Indyk and Xu [2023] .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 in 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 as long as it is clear that these goals are not attained by the paper. 
preliminaries: 
 Notation. Throughout, we consider a set of n distinct points x 1 , . . . , x n ∈ X for some input domain X and a distance function D : X × X → R ≥0 . D(x i , x j ) denotes the distance from point j to point i. We assume only that D(x i , x i ) = 0 for all i and that D(x i , x j ) > 0 for x j ̸ = x i . 5 Our main upper bound, Theorem 1, does not require D to be a metric, or even to be symmetric. Our main lower bound, Theorem 2, holds against the standard Euclidean distance D(x i , x j ) = ∥x i -x j ∥ 2 .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, j), indicating that there is an edge from node i to node j. Throughout, we let ln n denote the natural base-e logarithm of n, and log n denote the base-2 logarithm of n.Algorithm 1 Greedy Search 1: Input: Graph G over nodes {1, . . . , n}, starting node s, query point x. 2: Output: A point x j that is ideally close to x with respect to distance function D. h ← argmin i∈N (j) D(x, x i ), where ties are broken to prefer nodes with the lowest id.6 9:if D(x, x h ) < D(x, x j ) then 10: j ← h.else if D(x, x h ) = D(x, x j ) and h < j then ▷ Tie-breaking on node id.12: j ← h. Distance-Based Permutations. We let N (i) denote the out-neighbors of node i in the graph; i.e., j ∈ N (i) if and only if (i, j) ∈ E. We use the notation N 1 (i), . . . , N n (i) to index the list of nodes in the graph ordered in non-decreasing order by their distances from i; i.e., for k < ℓ, D(x i , x N k (i) ) ≤ D(x i , x N ℓ (i) ). Ties are broken by node id. Specifically, whenever D(x i , x N k (i) ) = D(x i , x N ℓ (i) ) and k < ℓ, then N k (i) < N ℓ (i).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 x 1 , . . . , x n are distinct and that D(x i , x i ) = 0 for all i and D(x i , x j ) > 0 for all j ̸ = i, we always have that N 1 (i) = i.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 1. It can be checked that the algorithm always terminates in 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 is 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 1, we define navigability formally as follows:Definition 3 (Navigable Graph). A graph G is navigable for point set x 1 , . . . , x n under distance function D if, for all s, t ∈ {1, . . . , n}, when Algorithm 1 is run with starting node s and query x = x t , then the algorithm returns x t . I.e., when the query x 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 algorithm always terminates after at most S calls to the while loop.It will be useful to think about navigability as a property of the distance-based node permutations defined earlier. In particular, navigability is implied by the following property: For all t and all ℓ > 1, there is an edge from N ℓ (t) to N k (t) for at least one k < ℓ.(1)In particular, when given a query x t ∈ {x 1 , . . . , x n }, Algorithm 1 will only move from nodes N ℓ (t) to N k (t) for which k < ℓ. Moreover, as long as there is such a k in the out-neighborhood of N ℓ (t), then the algorithm will not terminate at N ℓ (t). It follows that, if (1) holds, the algorithm is guaranteed to terminate at N 1 (t) = t and return x t , as desired. We remark that, if all distances between nodes are distinct, ( 1) is equivalent to the navigability property of Definition 3, although we will not require this fact. To better illustrate the connection between (1) and Definition 3, we include an example of a navigable graph in Figure 1 and the corresponding list of distance-based permutations in Figure 2 .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 of our model and analysis to address such limitations.Guidelines:• The answer NA means that the paper has no 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 (e.g., independence assumptions, noiseless settings, model well-specification, 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 a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness. • 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 acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
upper bound: 
 We begin by proving our main positive result, which we restate below: Theorem 1. For any input domain X , point set x 1 , . . . , x n ∈ X , and distance function D : X ×X → R ≥0 such that D(x i , x i ) = 0 for all i and D(x i , x j ) > 0 for x j ̸ = x i , it is possible to efficiently construct a directed navigable graph with average degree at most 2 √ n ln n. Moreover, the graph has the additional "small world" property: greedy routing always succeeds in at most 2 steps.4 3 1 2 5 (a) Vertex Coordinates 1 (4, -2) 2 (6, -1) 3 (2, 1) 4 (0, 0) 5 (1, -2) (b)Figure 1 : Example of a navigable graph G = (V, E) on 5 nodes. A double arrow indicates that both (i, j) ∈ E and (j, i) ∈ E. We can check that G is navigable by referring to Figure 2 .1 2 5 3 4(a) Permutation for 1. (c) Permutation for 3. (1) = 1, N 2 (1) = 2, N 3 (1) = 5, N 4 (1) = 4, N 5 (1) = 3, we have N 1 (2) = 2, N 2 (2) = 1, N 3 (2) = 3, N 4 (2) = 5, N 5 (2) = 4, etc.For the permutations, we draw all edges in the graph G from Figure 1 that point "left" in the permutation. In particular, we show edges that connect any N ℓ (t) to N k (t) with k < ℓ. We can check that property (1) 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 is deterministic. Both require O(n 2 (T + 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 as follows:• For all i ∈ {1, . . . , n} and all 1 < ℓ ≤ m, add an edge fromN ℓ (i) to N 1 (i) = i.• For all i ∈ {1, . . . , n}, add an edge from i to ⌈ 3n ln n m ⌉ nodes chosen uniformly at random from {1, . . . , n} \ {i}.To prove that this construction leads to a navigable graph, we need to prove the (1) holds with high probability. To do so, consider the permutation N 1 (i), . . . , N n (i) for a fixed node i. The property trivially holds for all ℓ ≤ m since we connected N ℓ (i) to N 1 (i) in step one of the construction. So, we only have to consider ℓ > m.For any ℓ > m, the chance that any one random edge from the second step of the construction connects to some N k (i) for k ≤ m is m n . So, the chance that none of the random edges connect N ℓ (i)to some N k (i) for k ≤ m is at most 1 -m n ⌈ 3n ln n m ⌉ ≤ 1 e 3 ln n ≤ 1 n 3. By a union bound, it follows that with probability at least 1 -1 n , for all i and all ℓ > m, N ℓ (i) has an edge to some N k (i) with k ≤ m < ℓ. Thus property (1) holds, and we conclude that the graph we constructed is navigable.It is left to set m. The graph we constructed has at most (m -1)n + n • ⌈ 3n ln n m ⌉ ≤ mn + n • 3n ln n m edges. Balancing terms, if we choose m = √ 3n ln n, the graph has ≤ 2 √ 3n 1.5 √ ln n edges.Finally, we observe that constructing the graph requires computing and sorting all n distance-based permutations, which takes O(n 2 (T + log n)) time. Moreover, we can see that the constructed graph is small-world with parameter C = 2. In the first iteration of Algorithm 1, we are guaranteed to choose a node h that is one of the m closest neighbors of the input x = x i . Then, at the second iteration, h has an edge to i itself and so we terminate.Construction 2: Deterministic. Our randomized construction can be derandomized relatively directly. We construct the same n(m -1) edges from N ℓ (i) to N 1 (i) for all i and 1 < ℓ ≤ m. The goal in constructing random edges was to ensure that, for ℓ > m, N ℓ (i) always has an edge to some node in {N 1 (i), . . . , N m (i)}, which we will call i's "near-neighborhood", and denote by N m (i). We can instead ensure that each N ℓ (i) has an edge into N m (i) via a greedy set cover approach.In particular, we claim that there is a set of g ≤ 1 + n ln n m nodes k 1 , . . . , k g such that every nearneighborhood N m (i) contains at least one of k 1 , . . . , k g . To ensure property (1) for values of ℓ > m, we only have to connect all nodes in our graph to this set. We construct this set greedily. Let B 1 = {1, . . . , n} and, for i > 1, let B i denote the set of all i for which none of k 1 , . . . , k i-1 is in N m (i). We have that |B 1 | = n and our goal is to show that |B g+1 | < 1. By a counting argument, there must be at least one node that appears in N m (i) for at least m different values of i ∈ B 1 . Select this node to be k 1 , which ensures that:|B 2 | ≤ 1 - m n |B 1 | = 1 - m n n.Again by a counting argument, there must be one node that appears in N m (i) for at least |B2|•m n values of i ∈ B 1 . Select this node to be k 2 , which ensures that:|B 3 | ≤ |B 2 | - |B 2 | • m n = 1 - m n |B 2 | ≤ 1 - m n 2 n.Continuing in this way, we conclude that |B g+1 | ≤ 1 -m n g n, which is less than 1 as long as g > n ln n m . We conclude that, as long as we connect every node to k 1 , . . . , k g , ( 1) is satisfied for all N ℓ (i) where ℓ > m, so our constructed graph is navigable.In total, our deterministic graph has at most (m -1)n + n • n m ln n + 1 edges. Choosing m = √ n ln n we get a graph with at most 2n 1.5 √ ln n edges. Again, the cost of the algorithm is dominated by the O(n 2 (T + log n)) time required to compute and sort all n distance-based permutations.We remark that, while it may be possible to improve our upper bound from O( √ n log n) to O( √ n) 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 N m (i) to look like a uniformly random subset of {1, . . . , n}. If the neighborhoods were truly random, then existing results on random set cover problems imply that it is not possible to find k 1 , . . . , k g covering all near-neighborhoods unless g = Ω n ln n m [Vercellis, 1984 , Arpino et al., 2024] .Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Algorithms for the problem thus have societal impact, many positive, but possibly negative. However, since our work focuses on theoretical foundations of the nearest neighbor search problem, it is difficult to comment in a meaningful and concrete way on its potential for societal impact. We believe its main impact will be a better scientific understanding of existing methods based on search in navigable graphs. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness 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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 a 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 as 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 or 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
lower bounds: 
 In this section, we prove Theorem 2, which shows that even for a random point set in R d for d = O(log n) under the Euclidean metric, Theorem 1 cannot be improved significantly: with high probability, any navigable graph G must have average degree Ω(n 1/2-δ ) for any fixed constant δ. Theorem 2 is a corollary of our more general Theorem 4, which we state below: Theorem 4. Let x 1 , . . . , x n ∈ {-1, 1} d be distributed independently and uniformly in {-1, 1} d . With probability > 9 10 , any navigable graph for x 1 , . . . , x n under the Euclidean metric requires Ω(n 3/2-ϵ ) edges, for ϵ = max log log n log n , c log n d for a universal constant c.The Ω(n 3/2-δ ) lower bound of Theorem 2 follows immediately from Theorem 4 by taking d = c 2 δ 2 log n. Alternatively, if we take d = c 2 log 3 n we have a lower bound of Ω(n 3/2 / log n), which matches Theorem 1 up to a O(log 3/2 n) factor.We introduce a few intermediate results before giving the proof of Theorem 4. First, we observe that the point set of Theorem 4 does not have any duplicate points with high probability. Doing so simplifies our analysis as no "tie-breaking" will be needed when Algorithm 1 is run on an input x j .Claim 5 (No Repeated Points). Let x 1 , . . . , x n be distributed as in Theorem 4. As long as d ≥ c 1 log n for a universal constant c 1 , then with probability at least 99/100, all vectors in this set are distinct.The claim follows from a simple probability calculation and union bound -see Appendix A.We next define a notion of a neighborhood of a point, which includes all points within a certain radius. Definition 6 (Fixed Radius Near-Neighborhood). Consider the setting of Theorem 4. Let O j be the subset of vectors in x 1 , . . . , x n (includingx j itself) with ⟨x i , x j ⟩ ≥ c h √ d log n where c h ∈ [1/3, 1]is some value (that may depend on n) which we will specify later.Note that, for anyx i , x j ∈ {-1, 1} d , ∥x i -x j ∥ 2 2 = d -2⟨x i ,x j ⟩, so O j contains a set of nearest neighbors to j in the Euclidean distance. Importantly, however, the definition used in this section is different from the N m (j) notation used in the previous section, since O j is not of a fixed size.Using the distance-based permutation characterization of navigability given in (1), we can observe that, in order for greedy routing to make progress towards target x j , every node in the near-neighborhood O j needs an edge to another node in the near-neighborhood, closer to x j . Formally: Claim 7 (Required Connections Within Neighborhoods). Consider the setting of Theorem 4 and assume that x 1 , . . . ,x n ∈ {-1, 1} d are distinct. Any navigable graph G for x 1 , . . . , x n requires |O j | -1 edges in O j × O j for each j.Proof. For G to be navigable, for any i ∈ O j \ {j}, there must be an edge from i to some node that is closer j, and thus is also in O j . Thus, there are at least|O j | -1 edges in O j × O j .We next make two claims about the near neighborhoods of Definition 6 when x 1 , . . . , x n are random points in {-1, 1} d : that 1) 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 x 1 , . . . , x n requires a large number of edges, proving Theorem 4. We first formally state the claims and prove Theorem 4 using them. We then prove the claims in Section 4.2. Claim 8 (Neighborhoods are Large). Let x 1 , . . . , x n be as distributed as in Theorem 4 and let O j be as in Definition 6. As long as d ≥ c 1 log n for a universal constant c 1 , with probability at least 99/100, for all j, |O j | ≥ √ n/6. Claim 9 (Neighborhood Intersections are Small). Let x 1 , . . . , x n be distributed as in Theorem 4 and let O j be as in Definition 6. As long as d ≥ c 1 log n for a universal constant c 1 , with probability at least 99/100, for all i ̸ = j,|O i ∩ O j | ≤ 10 max log n, n c √ log n dfor some universal constant c.Claim 8 establishes that O j contains the Θ( √ n) nearest neighbors to x j , which is a consequence of our choice of radius in Def. 6. If each O j were just an independent random set of Θ( √ n) nodes, then we would expect that for any i ̸ = j, |O i ∩ O j | = Θ(1). I.e., our neighborhoods would have small overlap, which is the key property we need to prove a lower bound. An overlap of O(1) would imply that O(n 3/2 ) edges are needed to satisfy the requirements of Claim 7. Of course, each O j is not an independent random set in reality. Specifically, if x i and x j have large inner product, O i and O j will be correlated, so we expect that |O i ∩ O j | will be larger. Claim 9 shows that for large enough d, such strong correlations are unlikely to happen and thus we still expect |O i ∩ O j | to be fairly small.Proof of Theorem 4. First note that we can assume that d ≥ c 1 log n for some large constant c 1 , as otherwise we will have ϵ > 3/2 and the lower bound becomes vacuous. Accordingly, the conclusions of Claims 5, 8 and 9 all hold for x 1 , . . . , x n with probability > 9/10 by a union bound.We will use these claims to show that any navigable graph for x 1 , . . . , x n requires Ω(n 3/2-ϵ ) edges. Consider any navigable graph G = (V, E). For any edge (u, v) ∈ E, let w u,v = |{j : u, v ∈ O j }| be the number of near neighborhoods that u and v both belong to. I.e., w u,v is the number of nodes j for which (u, v) ∈ O j × O j . By Claims 7 and 8, we must haveEQUATIONwhere we use in the last step that n ≤ n 3/2 /12 for large enough n. Further, w u,v = |O u ∩ O v |√ log n/d ) = Ω(n 3/2-ϵ ),for ϵ = max( log log n log n , c log n/d). This proves the theorem.We now prove Claims 8 and 9. We will use a very sharp bound on the CDF of a binomial distribution, given by Ahle [2017] and attributed to Cramer [Cramér, 2022] . This is a quantitative version of the central limit theorem, saying that the binomial CDF is close to the normal CDF, up to some small error. It is 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 [Ahle, 2017] ). Let F t (•) be the CDF of a mean centered binomial random variable with t trials and success probability 1/2. There are universal constants c 1 , c 2 such that, for anyx satisfying c 1 ≤ x ≤ √ t/c 1 , 1 3x e -x 2 2 • 1+ c 2 x 2 t ≤ F t (-x • √ t/2) ≤ 1 x e -x 2 2 • 1- c 2 x 2 t .We will also use that, with high probability, no pair of our random vectors has too high of an inner product. This will be required to prove Claim 9, i.e., that all near neighborhoods have small overlap.The claim follows directly from a standard Chernoff bound and a union bound over all pairs i, j.Claim 11 (Vectors are Not Too Similar). Let x 1 , . . . , x n be distributed as in Theorem 4. As long as d ≥ c 1 log n for a universal constant c 1 , with probability at least 99/100, for all i ̸ = j, ⟨x i , x j ⟩ ≤ c u √ d log n for some fixed constant c u .Finally, we require the following technical claim, which we will use to set c h in Definition 6. Our goal is to ensure that the probability of a vector being in the near neighborhood of another is Θ(1/ √ n).Claim 12. For any large enough n, there is some value of c ∈ [1/3, 1] such that1 √ ln n • exp(-c 2 • ln n) = 1 √ n.Proof. Observe that if we set c = 1, then1 √ ln n • exp(-c 2 • ln n) = 1 n √ ln n < 1 √ n .Further, if we set c = 1/3, we have for large enough n,1 √ ln n • exp(-c 2 • ln n) = 1 √ ln n exp(-1/9 ln n) = 1 √ ln n • n 1/9 > 1 √ n .Thus, for some setting of c ∈ [1/3, 1] the claim holds.Proof of Claim 8. Fix some x j . Then for any i ̸ = j, the event that i ∈ O j is exactly the event that a binomial random variable Bin(d, 1/2) exceeds its mean by ≥ c h √ d ln n/2. I.e., letting F d (•) be the CDF of the mean centered binomial random variable, we haveEQUATIONPlugging in the lower bound of Fact 10, we have for some constant c 2 :Pr(x i ∈ O j ) ≥ 1 3 • c h √ ln n • exp - c 2 h 2 • ln n • 1 + c 2 c 2 h ln n d .Using that d ≥ c 1 ln n for some sufficiently large constant c 1 , 1 +c2c 2 h ln n d ∈ [1, 2].Then, by Claim 12, we can set c h to some value in [1/3, 1] to obtain:EQUATIONFrom ( 4), the claim follows by noting that the events i ∈ O j are independent and each happens with probability at least1 3 √ n , so E [|O j |] ≥√ n/3. Thus, by a Chernoff bound, with probability at least1 -2 Ω( √ n) , |O j | ≥ √ n/6. Taking a union bound over all j then gives that, for sufficiently large n, |O j | ≥ √ n/6 for all j with probability at least 99/100, giving claim.Proof of Claim 9. Fix i ̸ = j and consider some k which is not equal to either i or j. Let z be the number of positions in which x i and x j take the same value. Note that, assuming the event of Claim 11 holds,z ≤ d/2 + c u √ d log n/2. Denote d/2 + c u √ d log n/2 by µ.By Definition 6, to havex k ∈ O i ∩ O j we need min(⟨x k , x i ⟩, ⟨x k , x j ⟩) ≥ c h √ d log n.That is, we need x k to match each of x i and x j in at least d/2 + c h /2 • √ d log n positions. On the d -z positions where x i and x j differ, the best case scenario (i.e., the scenario maximizing min(⟨x k , x i ⟩, ⟨x k , x j ⟩)) is when x k matches exactly half of these positions for each of x i , x j (i.e., matches d-z 2 positions). Assuming this case, to have x k ∈ O i ∩ O j , on the z positions where x i and x j are identical, x k must match z/2 + c h /2 • √ d log n positions. The probability of this happening is equivalent to the probability that a binomial random variable with z trials exceeds its mean by ≥ c h /2 • √ d log n. Since z ≤ µ, we can upper bound this probability by the probability that a binomial random variable with µ trials exceeds its mean by c h /2 • √ d log n. We rewrite the upper bound as:c h /2 • d log n = c h /2 • d/µ • µ log n = c h √ 2 • 1 1 + c u log n d • µ log n,where we used/2 µ = 1 1+cu √ log n d. Via Fact 10, we now upper bound our probability of interest by:Pr(x k ∈ O i ∩ O j ) ≤ 1 + c u log n d √ 2c h √ log n • exp   - c 2 h log n 1 + c u log n d •   1 - 2c 2 c 2 h • log n (1 + c u log n d ) • µ     .Observe that since in the claim we require d ≥ c 1 log n for a large constant c 1 , we have that1 ≤ 1 + c u log n d ≤ 2.So, we can simplify the above to:Pr(x k ∈ O i ∩ O j ) ≤ √ 2 c h √ log n • exp   - c 2 h log n 1 + c u log n d • 1 - 2c 2 c 2 h • log n µ   = √ 2 c h √ log n • exp     -c 2 h log n • 1 + c 2 c 2 h log n d • 1 - 2c2c 2 h •log n µ 1 + c2c 2 h log n d • 1 + c u log n d     .Now, since we set d ≥ c 1 log n for a large constant c 1 , we can ensure that have that log n d ≤ c 3√ log √ dfor any small constant c 3 . Using this fact, along with the fact that µ ≥ d/2, we have:1 - 2c2c 2 h •log n µ 1 + c2c 2 h log n d • 1 + c u log n d ≥ 1 -.5c u log n d 1 + .5c u log n d • 1 + c u log n d ≥ 1 -2c u • log n d .For the second inequality, we used the fact that (1-.5x) (1+.5x)(1+x) ≥ 1 -2x for all x. Next, setting c h ∈ [1/3, 1] exactly as in (4) so that 1√ log n • exp - c 2 h 2 log n • 1 + c2c 2 h log n d = 1√ n , we have:Pr(x k ∈ O i ∩ O j ) ≤ √ 2 c h √ log n • exp -c 2 h log n • 1 + c 2 c 2 h log n d • 1 -2c u log n d ≤ √ 2 c h n • exp 2c 2 h c u log n • 1 + c 2 c 2 h log n d • log n d ≤ 4 √ 2 n • exp c log 3/2 n d = 4 √ 2 n • n c √ log n d ,for some constant c. Finally, observe that, conditioned on x i and x j sharing z entries, the event x k ∈ O i ∩ O j is independent for each x k . Thus, by a standard Chernoff bound, with probability atleast 1 -1/n c ′ , we have |O i ∩ O j | ≤ 10 max(log n, n c √ log n d) for some large constant c ′ . Union bounding over all O(n 2 ) pairs i ̸ = j then gives the claim.In Theorems 1 and 2, we focus on the average degree of navigable graphs. While a reasonable metric, we might also be interested in the maximum degree, which governs the worst-case complexity of a single step of the greedy algorithms. Here we give a simple argument showing that unfortunately, on 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 a set of points x 1 , . . . , x n ∈ R d for d = O(log n) such that any navigable graph for these points under the Euclidean metric has maximum out-degree d -1.Proof. First we prove the bound for a high dimensional point set. For all i < n, let x i be a standard basis vector with a 1 in position i. Let x n be the all zeros vector. As we can see, x n has Euclidean distance 1 from x 1 , . . . , x n-1 . On the other hand, for all i ̸ = j where i, j ̸ = n, ∥x i -x∥ 2 = √ 2. In other words, x n is the closest neighbor to each of x 1 , . . . , x n-1 . It follows that any navigable graph must contain an edge from x 1 to each of these points, resulting in maximum degree n.To extend the construction to low dimensions, we simply use the Johnson-Lindenstrauss Lemma to embed the point set above into c log n dimensions. As long as the constant c is sufficiently large, all distances will be preserved to within error, say, ±0.1. So, x n will still be the nearest neighbor of all other points, and we will still require it to have out-degree n -1.Below we gives the proofs of some simple technical claims required to prove our main lower bound, Theorem 4. First, we prove Claim 5, which establishes that, with high probability, the hard input distribution of Theorem 4 produces a set of distinct points.. Claim 5 (No Repeated Points). Let x 1 , . . . , x n be distributed as in Theorem 4. As long as d ≥ c 1 log n for a universal constant c 1 , then with probability at least 99/100, all vectors in this set are distinct.Proof. Consider two points x i , x j . The probability that these points are identical equals 1 2 d ≤ 1 n c 1 . Then by a union bound over all pairs i, j, we have that all points are distinct with probability at least 1 -1 n c 1 -2 , which is greater than 99/100 for sufficiently large c 1 .Next we give a short derivation of Fact 10, which gives a sharp bound on the CDF of a binomial distribution, and is used in proving Claims 8 and 9.Fact 10 (Binomial CDF Bound, 2.20 of [Ahle, 2017] ). Let F t (•) be the CDF of a mean centered binomial random variable with t trials and success probability 1/2. There are universal constants c 1 , c 2 such that, for anyx satisfying c 1 ≤ x ≤ √ t/c 1 , 1 3x e -x 2 2 • 1+ c 2 x 2 t ≤ F t (-x • √ t/2) ≤ 1 x e -x 2 2 • 1- c 2 x 2 t .Proof. Applying 2.20 of [Ahle, 2017] with p = q = 1/2 gives thatF t (-x • √ t/2) ∈ 1 √ 2πx exp -tD 1 2 - x 2 √ t 1 2 • 1 ± c 1 x 2 + x √ t ,for some constant c, where use the notation D(a∥b) def = a log(a/b) + (1 -a) 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 (2.13) of [Ahle, 2017] to claim that, for a constant c 2 ,D 1 2 - x 2 √ t 1 2 ∈ x 2 2t ± c 2 x 4 2t 2 ,Plugging back in, we have that for constants c and c 2 ,F t (-x • √ t/2) ∈ 1 √ 2πx exp - x 2 2 • 1 ± c 2 x 2 t • 1 ± c 1 x 2 + x √ t . If we assume c 1 ≤ x ≤ √ t/c 1 for large enough constant c 1 then 1 3x ≤ 1 √ 2πx • 1 -c 1 x 2 + x √ t and 1 √ 2πx • 1 + c 1 x 2 + x √ t ≤ 1x , which completes the proof. 
safeguards: 
 Question: Does the paper describe 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)? 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 a 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 a best faith effort. 12. Licenses for existing assets Question: 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? Answer: [NA] Justification: This paper does not use existing assets. Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a 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 of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.G is further considered "small-world" if greedy routing always terminates in a small number of steps.38th Conference on Neural Information Processing Systems (NeurIPS2024).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 on the graphs.The Delaunay graph connects i, j if xi and xj have adjacent cells in a Voronoi diagram for x1, . . . , xn.Such graphs are closely related to but not the same as "relative neighborhood graphs"[Toussaint, 1980].Even these assumptions are not needed, but they make our definition of "navigable" more natural. Otherwise, we must allow for greedy routing to navigate to any vertex xj ∈ argmin x 1 ,...,xn D(xj, xt) given target xt.Formally, h ← min {argmin i∈N (j) D(x, xi)} , where argmin t f (t) returns the set of minimizers of f . 
 
 Appendix:  


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

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: W1: The method proposed in the article is not generalizable to the construction methods used by current graph-based approaches.

W2: 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.
questions: 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?

Q2: 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: limitations: yes.
paper_summary: paper_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}$.
strength_weakness: strength_weakness: 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.
 

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

[1] Goyal et al. "Disorder inequality: a combinatorial approach to nearest neighbor search." WSDM 2008.

Minor comments:
- 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.
- l263: "gives" should be "give"
- l391: $x$ should probably be $x_j$ here
questions: questions: I do not have any questions in addition to the comments listed in the previous above.
limitations: limitations: Limitations are discusses in the paper.
paper_summary: paper_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.
strength_weakness: strength_weakness: W1. There is no experimental evaluation.   
W2. More related work should be reviewed.   
W3. Some technical details require clarifications.   
W4. A section of conclusion and future direction is missing.
questions: 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?   

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

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

Q4. The paper has no experimental evaluation, so it is hard to tell whether their proposed techniques can be helpful in practice.   

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

Q6. 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    
[R1] RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search. SIGMOD 2024.    
[R2] LiteHST: A Tree Embedding based Method for Similarity Search. SIGMOD 2023.      
[R3] Turbo Scan: Fast Sequential Nearest Neighbor Search in High Dimensions. SISAP 2023.   

Q7. The structure of this paper can be improved by summarizing the conclusion and identifying the future direction.
limitations: limitations: Please refer to the weaknesses and questions.
paper_summary: paper_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$.
strength_weakness: strength_weakness: 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.
questions: 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: limitations: The authors fairly address the limitations of the work.

Comments: title: Response to the author feedback
comment: I acknowledge that I have read the rebuttal. Currently, Q2 has not been addressed clearly.
Dear authors,

I have read the rebuttal, and thank you for considering my suggestions. I will carefully consider the rebuttal when making the final decision.

Best regards,
Thank you for the reply!

While the results are relatively simple, it is a nice work that, I think, is above the acceptance threshold since it addresses an important problem (there is a gap between theory and practice in this field), provides new theoretical results and clearly states the limitations.
I acknowledge that I have read the rebuttal, and thank the authors for carefully answering my question.