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

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

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.

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?

Rating

7

Confidence

3

Soundness

4

Presentation

4

Contribution

3

Limitations

The authors fairly address the limitations of the work.

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.

Strengths

S1. The paper studies an important problem. S2. Several interesting theoretical results are given S3. The main ideas are easy to follow.

Weaknesses

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

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.

Rating

3

Confidence

4

Soundness

3

Presentation

2

Contribution

2

Limitations

Please refer to the weaknesses and questions.

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}$.

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

I do not have any questions in addition to the comments listed in the previous above.

Rating

5

Confidence

4

Soundness

3

Presentation

4

Contribution

3

Limitations

Limitations are discusses in the 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.

Strengths

S1: The article establishes both upper and lower bounds for navigable graphs and utilizes anti-concentration bounds for binomial random variables. S2: 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. S3: 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. 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

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.

Rating

5

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

yes.

Response to the author feedback

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,