Efficiently Constructing Sparse Navigable Graphs

Alex Conway, Laxman Dhulipala, Martin Farach-Colton, Rob Johnson, Ben Landrum, Christopher Musco, Yarin Shechter, Torsten Suel, Richard Wen · 2025

Read Efficiently Constructing Sparse Navigable Graphs by Alex Conway, Laxman Dhulipala, Martin Farach-Colton, Rob Johnson, Ben Landrum, Christopher Musco, Yarin Shechter, Torsten Suel, Richard Wen (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-13296.txt.

Introduction

Alex Conway and co-authors give in 2025 the first fast algorithm with proven guarantees for building sparse navigable graphs, the structures behind top graph based nearest neighbor search. Building such a graph by hand tuned rules is costly, and no method had proof behind it. Framing the job as many linked set cover problems yields a slow greedy method whose graph is near optimal in sparseness.

By exploiting the links between those problems and borrowing streaming tricks, the team cuts the run time to near the square of the data size. Their graph stays within a small factor of the sparsest possible, for any distance rule. A hardness result shows the speed is near best possible. Code level preprocessing adds more gains.

Catalog record

CREATORAlex Conway, Laxman Dhulipala, Martin Farach-Colton, Rob Johnson, Ben Landrum, Christopher Musco, Yarin Shechter, Torsten Suel, Richard Wen
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE142 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-13296

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Efficiently Constructing Sparse Navigable Graphs Alex Conway, Laxman Dhulipala, Martin Farach-Colton, Rob Johnson, Ben Landrum, Christopher Musco, Yarin Shechter, Torsten Suel, Richard Wen Abstract Graph-based nearest neighbor search methods have seen a surge of popularity in recent years, offering state-of-the-art performance across a wide variety of applications. Central to these methods is the task of constructing a sparse navigable search graph for a given dataset endowed with a distance function. Unfortunately, doing so is computationally expensive, so heuristics are universally used in practice. In this work, we initiate the study of fast algorithms with provable guarantees for search graph construction. For a dataset with n n data points, the problem of constructing an optimally sparse navigable graph can be framed as n n separate but highly correlated minimum set cover instances. This yields a naive O ⁡ ( n 3 ) O(n^{3}) time greedy algorithm that returns a navigable graph whose sparsity is at most O ⁡ ( log ⁡ n ) O(\log n) higher than optimal. We improve significantly on this baseline, taking advantage of correlation between the set cover instances to leverage techniques from streaming and sublinear-time set cover algorithms. Combined with problem-specific pre-processing techniques, we present an O ~ ​ ( n 2 ) \tilde{O}(n^{2}) time algorithm for constructing an O ⁡ ( log ⁡ n ) O(\log n) -approximate sparsest navigable graph under any distance function. The runtime of our method is optimal up to logarithmic factors under the Strong Exponential Time Hypothesis via a reduction from the Monochromatic Closest Pair problem. Moreover, we prove that, as with general set cover, obtaining better than an O ⁡ ( log ⁡ n ) O(\log n) -approximation is NP-hard, despite the significant additional structure present in the navigable graph problem. Finally, we show that our techniques can also beat cubic time for the closely related and practically important problems of constructing α \alpha -shortcut reachable and τ \tau -monotonic graphs, which are also used for nearest neighbor search. For such graphs, we obtain O ~ ​ ( n 2.5 ) \tilde{O}(n^{2.5}) time or better algorithms. 1 Introduction Nearest neighbor search has been central in computer science and data science for decades [ 28 , 34 , 39 , 11 , 7 , 2 , 31 , 4 , 6 ] . Current interest in the problem is driven by its central role in modern AI systems: search over machine-learned semantic embeddings is the key technology behind AI-driven web search, retrieval-augmented generation in LLMs, and more [ 40 , 33 , 53 , 41 , 9 ] . Formally, the nearest neighbor search problem is defined as follows: Given a point set P=\{p_{1},\ldots,p_{n}\} and a distance function d , 1 1 1 Our work only requires that d(p_{i},p_{i})=0 for all i and d(p_{i},p_{j})=d(p_{i},p_{j})>0 for i\neq j (i.e., we assume no repeated data points in the dataset). These conditions are satisfied by any metric, but are much weaker. construct a data structure to efficiently find \argmin_{i\in\{1,\ldots,n\}}d(p_{i},q) for any given query point q , or an approximate minimizer. A naive O(n) time method is to brute-force search over the entire dataset, so “efficiently” here means finding the nearest neighbor in o(n) time. The nearest neighbor search problem has been studied extensively both in theory and in practice. A classical solution is locality-sensitive hashing (LSH) [ 28 , 3 ] , which provides theoretical guarantees on the approximation ratio, construction time, and query time. However, LSH has proven too inefficient for large high-dimensional datasets [ 44 ] . For these applications graph-based nearest neighbor search heuristics like the Hierarchical Navigable Small World (HNSW) method [ 43 ] , Vamana/DiskANN [ 49 , 38 ] , Navigating Spreading-out Graphs (NSG) [ 21 ] , and more [ 42 , 20 , 25 , 47 , 44 , 6 , 48 ] have become much more popular. While these graph-based heuristics substantially outperform other (potentially more theoretically sound) techniques in practice, there is surprisingly little underlying theory about their performance. Although the details differ, the core idea behind all of these graph-based search methods is the same, dating back to decades old work on Milgram’s “small world phenomenon” and greedy routing in networks [ 45 , 52 , 36 , 35 ] . The basic approach is to preprocess the input set by constructing a directed search graph G=\left(P,E\right) , with a node corresponding to each point in our data set. To answer a query q , greedy search , or some variant 2 2 2 Beam-search, a natural “conservative” version of greedy search is currently the method of choice in practice. , is employed: traverse a path through the graph, starting at an arbitrary node, until a local minimum condition is met. To extend a path at node p , move to p ’s neighbor closest to q ; the local minimum is achieved (and the path is terminated) when the current p has no neighbors that are closer to q than p is. We then return p . The main computation cost at each step is finding p ’s closest neighbor to q , which requires a number of distance computations proportional to p ’s degree. A key question in graph-based nearest neighbor search is how to choose G , subject to the following competing constraints: • Can we construct a graph G whose greedy traversal will yield a nearest neighbor, or good approximate nearest neighbor, of the query point? • Can we construct G to be sparse so that memory overhead is minimized and traversing it is fast? We note that these two constraints are indeed in tension: if G were a clique, it would certainly always return the nearest neighbor of a query, but traversing it would take O(n) time for every query. If, on the other hand, G were a constant-degree spanner, greedily traversing G would require just O(1) time per step and the graph would require just O(n) space, but might not return a very good answer to most queries. Our work studies the fundamental question of how to efficiently construct graphs that satisfy the competing constraints. We explain the notions required to make this statement precise in the next section. 1.1 Navigable Search Graphs As discussed above, our goal is to construct a search graph G where greedy search is effective in finding (approximate) nearest neighbors in a point set P . Towards this goal, many different graphs properties have been considered (see [ 47 ] for an overview). The most popular such property is navigability . Since convergence to a nearest-neighbor for all possible queries is difficult to guarantee 3 3 3 Despite their practical effectiveness, most graph-based methods do not enjoy worst-case theoretical accuracy guarantees as strong as, for example, methods based on LSH [ 2 ] . , navigability demands that, at least if the query q is in P (i.e., it has as a nearest neighbor with distance 0 ), then greedy search on G should return q itself, no matter where the search begins. A standard equivalent definition for navigability is as follows [ 1 ] : Definition 1 (Navigable Graph) . Given point set P and distance function d:P\times P\to\mathbb{R}^{+} ,

Read the complete text