acceptodds
Under review as a conference paper at ICLR 2027

Understanding Hubness for Graph-Based Nearest Neighbor Search

Abstract

Graph-based approximate nearest neighbour search algorithms have gained significant attention recently due to their excellent empirical performance, though theoretical understanding of their behaviour remains limited. Empirical work has established the importance of ”hubs” during the greedy search. In this work, we offer some theoretical explanation for the ”hubness” phenomenon and its importance for nearest neighbour search. We develop a large-deviation framework for Gaussian data in the moderate high-dimensional regime . Through analysis of greedy nearest-neighbour search on data drawn from the Gaussian and uniform spherical distributions, we distinguish geometric hubs, characterized by high incoming degree, from navigation hubs, characterized by more frequent visitation during search. Together, these results connect graph geometry, hubness, and navigation guarantees, providing analytical tools for distribution-sensitive theories of graph-based nearest neighbour search.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Nearest Neighbour Graph, Approximate Nearest Neighbour Search, Hubness, High-Dimensional Data

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_NvriOpenReview ↗
Rating
3(+1)
Confidence
2(−1)
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies how hubness affects greedy search on nearest neighbour graphs. For Gaussian data, it relates a point's distance from the center to its incoming edges and its role in search. It derives conditions on the number of neighbors needed for search to succeed in a constant number of steps. The analysis also considers data sampled uniformly from a sphere. Numerical experiments compare the predicted graph properties with observed search behavior.

Critical strengths

(1) The analysis allows Gaussian points to have different distances from the center. This lets it study a source of unequal degrees that is absent when all points lie on a sphere. The result on the number of neighbors needed for successful greedy search is also a useful theoretical contribution.

(2) The paper distinguishes points with many incoming edges from points that are often visited during search. This is a useful distinction because a large number of incoming edges does not by itself explain how search uses a point. The numerical experiments help illustrate this relationship.

Critical weaknesses

(1) The meaning of αnav\alpha_{\mathrm{nav}} changes between the main text and the appendix. Section 4.2 uses it for the smallest norm among visited points, and Figure 1d is explained in the same way. Theorem 11 instead defines αnav=α+(1,2)\alpha_{\mathrm{nav}} = \alpha_{+}(1,2), which is the output from a typical starting point. These are different quantities. A typical output need not be the smallest possible output. This difference affects the paper's conclusion about which hubs are not visited.

(2) Theorem 11 includes a claim that is not established in its proof. It states that sup⁡Hnav<αh\sup \mathcal{H}_{\mathrm{nav}} < \alpha_h. This means that all values in Hnav\mathcal{H}_{\mathrm{nav}} stay below αh\alpha_h with a positive gap. The proof shows that a small interval near αmin\alpha_{\mathrm{min}} is excluded and that the typical output is below αh\alpha_h. These facts do not establish the same gap for the whole set. The claimed description of Hnav\mathcal{H}_{\mathrm{nav}} therefore needs an additional argument.

Questions for authors

(1) Does αnav\alpha_{\mathrm{nav}} mean the smallest norm among points that search can visit, or the norm produced from a typical starting point? Please distinguish these quantities and state which one appears in Figure 1d. Would this distinction change the interval of hubs that the paper says are not visited?

(2) Which step proves that sup⁡Hnav<αh\sup \mathcal{H}_{\mathrm{nav}} < \alpha_h? Please explain how the result follows for the whole set Hnav\mathcal{H}_{\mathrm{nav}}. The comparison αnav<αh\alpha_{\mathrm{nav}} < \alpha_h appears to concern only one typical value. It does not establish a positive gap below αh\alpha_h for the whole set.

Reviewer_LR9iOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies the role of hubness in graph-based approximate nearest-neighbor search using a large-deviation framework for high-dimensional Gaussian data. The authors introduce a source-dependent threshold graph and derive a sufficient degree exponent under which greedy search finds a cc-approximate nearest neighbor in O(1)O(1) steps with high probability.

They also distinguish geometric hubs, which have high incoming degrees, from navigable hubs, which are visited during greedy search, and claim that the highest-in-degree hubs are never visited. Finally, they compare the theoretical navigation guarantees for Gaussian and spherical-uniform data to investigate whether hubness improves search efficiency.

Critical strengths
  • The paper addresses an interesting theoretical question about the relationship between hubness and greedy navigation in graph-based nearest-neighbor search.

  • Extending existing theoretical analyses from spherical-uniform data to Gaussian data with source-dependent neighborhoods is a meaningful contribution.

  • The large-deviation framework and continuous optimization formulation provide a useful approach for analyzing greedy search in high dimensions.

  • The distinction between geometric and navigational hubness is an interesting direction that could improve our understanding of graph-based search.

Critical weaknesses

W1. The claimed minimum navigable norm αnav\alpha_{\mathrm{nav}} is not supported by the theoretical analysis.

Section 4.2 presents αnav\alpha_{\mathrm{nav}} as the minimum normalized squared norm of vertices visited during greedy search, and concludes that hubs with smaller norms are never visited. However, Appendix D.2 defines αnav=α+(1,2)\alpha_{\mathrm{nav}}=\alpha_+(1,2) as the unique minimizer of the navigation rate function InavI_{\mathrm{nav}}, meaning it represents the most typical one-step output norm, not the minimum possible output norm. The actual lower boundary of the region defined in the appendix is inf⁡Hnav\inf H_{\mathrm{nav}}, which is not shown to equal αnav\alpha_{\mathrm{nav}}. In fact, evaluating the authors' own equations with w=6.448w=6.448 and ρs=0.5\rho_s=0.5 gives α+(1,2)≈0.628583\alpha_+(1,2)\approx0.628583, while the feasible source state (α,θ)=(0.99,0)(\alpha,\theta)=(0.99,0) produces α+(0.99,1.99)≈0.627857\alpha_+(0.99,1.99)\approx0.627857. This source state has rate φ(0.99,0)≈2.52×10−5<1/w\varphi(0.99,0)\approx2.52\times10^{-5}<1/w, and the resulting output norm is within the geometric-hub region, so it also belongs to HnavH_{\mathrm{nav}} under Definition 8. Therefore, even the authors' continuous model contains navigable norms below αnav\alpha_{\mathrm{nav}}, contradicting its interpretation as a lower bound in Section 4.2 and Figure 1d. The unique-minimizer statement in Theorem 11 is not itself disproved, but the main text draws a stronger conclusion that does not follow.

W2. The one-step continuous analysis does not establish which vertices are actually visited during greedy search.

Appendix D.2 analyzes the norm of a continuous optimizer x+x_+ that minimizes the query distance under the large-deviation and neighborhood constraints. However, this optimizer is not necessarily an actual dataset vertex, and the authors do not establish that the norm of the selected neighbor in the finite graph concentrates around this optimizer uniformly over relevant source states. More importantly, the analysis considers source states drawn from the original Gaussian distribution, whereas the states encountered after one or more greedy steps follow a search-dependent distribution. The optimizer can also be defined for states in which it does not improve the query distance, in which case actual greedy search would stop rather than visit it. Consequently, this one-step analysis does not directly characterize vertices visited along complete greedy paths. The claim that the highest-in-degree hubs are never visited requires a stronger argument connecting the continuous optimizer to actual improving transitions and complete search trajectories.

W3. The formal definition of a navigable hub is inconsistent with the claimed result.

Definition 3 states that a geometric hub is navigable if there exists a starting vertex v′v' and a query qq such that the hub lies on the greedy path from v′v' to qq. As written, this definition does not exclude the starting vertex itself, which would make every geometric hub trivially navigable by choosing that vertex as the starting point. Even if the starting vertex is excluded, the definition quantifies over the existence of some query, whereas the theoretical analysis assumes a fixed query independent of the dataset. These are substantially different conditions, and results for an independent query do not establish that a hub can never be visited for any possible query. The definition and theorem statements should specify the intended quantifiers over queries and starting vertices.

W4. The proof of Theorem 11 contains incorrect equations and unsupported steps.

The proof of Theorem 11 in Appendix D.2 (page 41) contains several mathematical errors. First, it repeatedly uses s*(1; ρ_s) = m_flip² − m_flip, whereas the correct expression from the threshold definition is s*(1; ρ_s) = m_flip² + m_flip. Since 0 < m_flip < 1, the expression with the minus sign is negative and therefore cannot represent a normalized squared distance. Second, in the case λ_+ = 0, the proof states that α_(λ_+) = 0, although the definition of the interpolated center gives α_(λ=0) = 1. Finally, the theorem claims that sup H_nav < α_h, but the provided argument does not establish this strict inequality. These errors affect the proof relating the navigable and geometric hub regions. Although some may be fixable, the proof as written is not valid and requires revision.

W5. The geometric-hub analysis characterizes expected degrees rather than directly proving the claimed classification of vertices.

Definition 2 defines geometric hubs using their actual incoming and outgoing degrees. In Appendix D.1, however, Lemmas 21–25 characterize the expected incoming degree through a large-deviation exponent and compare it with the expected outgoing degree. These calculations explain why lower-norm vertices tend to have much larger incoming degrees, but a comparison of expectations alone does not prove that every vertex in the claimed norm region has incoming degree larger than outgoing degree. The main text presents the threshold αh\alpha_h as an if-and-only-if characterization of geometric hubs, which requires an additional concentration argument for realized degrees. Such an argument may be straightforward for norm levels separated from the threshold, but the behavior near αh\alpha_h also needs to be handled carefully.

W6. Some steps in the main Gaussian navigation proof require additional justification.

The overall argument for the constant-step navigation guarantee is promising, but several technical steps are not fully justified. In Lemma 7, the authors invoke Chebyshev's inequality to obtain a norm bound holding simultaneously for all n dataset points; this does not follow from the stated calculation when n grows exponentially with d, and an exponential tail bound is needed. The transfer from the threshold graph to the exact k-NN graph also relies on probability estimates that should be justified uniformly over the relevant source-norm interval, rather than only for each fixed norm. Furthermore, Theorem 10 uses the limiting nearest-neighbor distance sNN(1)s_{\mathrm{NN}}(1) to conclude a finite-sample c-ANN guarantee, which requires an additional argument using approximation slack and concentration of the actual nearest-neighbor distance. There are also smaller inaccuracies, such as the equality gG(x1)=rg_G(x_1)=r in Lemma 18, which does not hold throughout its stated Case 1. These issues appear more readily repairable than the problems with the navigable-hub theorem, but the proofs should be corrected.

W7. The comparison with spherical-uniform data does not establish that hubness accelerates greedy search.

Section 4.3 compares the sufficient graph-degree exponents required by the authors' analysis for Gaussian and spherical-uniform data. Although the derived comparison is interesting, a smaller sufficient exponent does not necessarily imply that the actual minimum degree required for successful search is smaller. The paper does not provide matching necessary bounds or otherwise establish that the derived thresholds are tight. Moreover, changing from spherical-uniform to Gaussian data changes several geometric properties simultaneously, so the comparison does not isolate hubness as the cause of any improvement. Therefore, the conclusion that hubs accelerate nearest-neighbor search is stronger than what the theoretical results establish. A more accurate interpretation would be that the analysis gives a more favorable sufficient degree bound for Gaussian data in certain parameter regimes.

W8. The constant-step guarantee should be distinguished from actual search complexity.

The main theorem guarantees that greedy search reaches an approximate nearest neighbor in O(1) steps, but each step examines k=nρs+o(1)k=n^{\rho_s+o(1)} outgoing neighbors. Thus, the number of distance evaluations can still be nρs+o(1)n^{\rho_s+o(1)}, which is substantial when the required degree exponent is large. For example, the paper's near-exact asymptotic analysis gives a limiting critical exponent approaching 8/98/9 as w increases. While the constant-step result is theoretically interesting, its implications for efficient ANN search should be discussed in terms of the total number of distance evaluations and graph storage, rather than the number of greedy steps alone.

W9. The experiments provide limited validation of the strongest theoretical claims.

The experiments are restricted to synthetic Gaussian and spherical-uniform datasets, and the paper provides limited details about the exact graph construction, number of queries, and evaluation protocol. The empirical degree comparisons use a 90% success threshold with uniformly sampled starting vertices, whereas the main theorem provides a high-probability asymptotic guarantee simultaneously for every starting vertex. These are different guarantees, and the experiments do not directly evaluate the stronger condition. Similarly, Figure 1d compares visited norms with the proposed αnav\alpha_{\mathrm{nav}}, but does not distinguish the typical visited norm from the minimum visited norm or separately validate one-step and multi-step behavior. Given the central role of the navigable-hub claim, more direct experiments examining the full distribution of visited norms and the predicted lower boundary would be valuable. As a minor numerical point, evaluating the displayed near-exact degree formulas gives a Gaussian/spherical crossover near w=6.472w=6.472, rather than the approximately 6.448 stated in Figure 1c.

Questions for authors

Q1. Is αnav\alpha_{\mathrm{nav}} intended to represent the most typical one-step output norm or the minimum possible visited norm? Appendix D.2 establishes the former, while Section 4.2 and Figure 1d use it as the latter. Can the authors clarify this distinction and provide a proof of the claimed lower bound?

Q2. How does the analysis of the continuous one-step optimizer establish which vertices are visited during actual greedy search? In particular, can the authors justify the connection to finite-graph neighbor selection and explain how the analysis extends to later search steps, where source vertices are no longer distributed as independent Gaussian samples?

Q3. Can the authors clarify Definition 3? Does a starting vertex count as being visited, and is navigability defined with respect to a fixed independent query or the existence of an arbitrary query? How do the theoretical guarantees correspond to the revised definition?

Q4. Can the authors provide a corrected proof of Theorem 11, particularly the relationships among αnav\alpha_{\mathrm{nav}}, αflip\alpha_{\mathrm{flip}}, and αh\alpha_h, and the claimed strict upper boundary of HnavH_{\mathrm{nav}}? The current proof contains incorrect expressions for the neighborhood threshold and the interpolated-center norm.

Q5. Can the authors provide concentration arguments connecting the expected in-degree analysis to the actual geometric-hub classification? Similarly, can they clarify the uniform probability estimates, the norm bound in Lemma 7, and the finite-sample approximation guarantee used in the main navigation theorem?

Q6. Does the comparison of sufficient degree exponents between Gaussian and spherical-uniform data establish an actual search advantage, or only an advantage in the derived sufficient bounds? Can the authors provide evidence that the bounds are tight or that hubness itself is responsible for the observed difference?

Q7. Can the authors provide more details about the experiments and directly test the lower boundary of the visited-norm distribution, including the difference between first-step and later-step visits? It would also be helpful to report the number of distance evaluations and clarify the discrepancy in the reported Gaussian/spherical crossover value.

Reviewer_UMW4OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The authors consider the study of hubs in the KNN graphs on randomly generated data (Gaussian and uniform). They show that greedy search on such KNN graphs converges to a good approximate solution in constant steps.

I generally like the results but am concerned about the motivation behind this theory work. I am willing to increase my score if the questions raised are addressed.

Critical strengths

Understanding of hubs and also the analysis of greedy search on the KNN graphs for randomly generated data sounds quite interesting to me.

Critical weaknesses
  1. The authors analyze the KNN graphs, but the introduction talks about HNSW, NSG and DiskANN none of which are remotely close to being KNN graphs. Would authors please clearly state why the results presented here are of any practical importance? In particular, do you see any possible path for any of these ideas or intuition developed here to be used in practical graph based algorithms?

  2. I would encourage authors to please list intuitive important properties of \rho_{crit} in the introduction.

  3. How did you get the RHS in Equation 3.

  4. The paper is a little heard to read and is very dense. In particular, section 3.2 needs to be polished. Also, why is is there a pho_{s} in the argument of G_{\tau} in Definition 1, it might be that k=n^{\rho_{s}} is assumed in this definition. Please state this explicitly in the definition itself.

Questions for authors

See weaknesses.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.