Understanding Hubness for Graph-Based Nearest Neighbor Search

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 $d=\Theta (\log (n))$. 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.