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

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.

Thank you for the detailed review. We provide responses to the specific questions below:

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

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

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

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

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

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

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

Q6: Thank you for the suggested references!

Q7: 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).

Thank you for the thoughtful comments. We address the two specific questions below.

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

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

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

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

Thank you for the feedback. We address a few of the points raised below:

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

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