Fast Sparse $\alpha$-Navigable Graph Construction with Improved Resource Augmentation

Abstract

Graph-based nearest neighbor search methods, which run greedy search on a directed graph over the data points, have surged in popularity in recent years. A common goal is to construct a search graph with the $\alpha$-navigability property, which ensures that greedy search returns provably good approximate nearest neighbors and converges in few iterations. Increasing $\alpha \ge 1$ improves accuracy and convergence rate, but requires more edges, which increases both space and search time. This tradeoff has motivated the study of algorithms for constructing a sparsest $\alpha$-navigable graph for a given set of points. For any point set and any distance function, we show how to compute an $\alpha$-navigable graph with at most $O(\log n)$ times as many edges as the sparsest $(1+\epsilon )\alpha$-navigable graph, in $O(n^{\omega }\log (\Delta )/\epsilon )$ time, where $\omega <2.372$ is the matrix multiplication exponent and $\Delta$ is the aspect ratio of the input. This improves on Khanna, Padaki, and Waingarten (SODA 2026), who achieve the same runtime but are only competitive with the sparsest $2(1+\epsilon )\alpha$-navigable graph. Since sparsity often increases rapidly with $\alpha$ (typically $\alpha \le 1.1$), their bound can be significantly weaker. Previously, the best algorithm competing with the sparsest $(1+\epsilon )\alpha$-navigable graph required $\tilde{O}(n^{2.5})$ time. Our techniques also extend to constructing sparse $\tau$-monotonic graphs, another popular target in nearest neighbor search. Finally, we give a fine-grained complexity analysis suggesting that improving the $O(n^{\omega })$ running time is unlikely, or would require a very different approach. It is based on hardness results for problems related to verifying whether a graph is navigable, a topic of independent interest.

arXiv comment26 pages. To appear in SODA 2027