Research map / Graph learning / Graph algorithms and clustering
Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows any point set admits a navigable graph with average degree O(sqrt(n log n)) for any distance function, and that random ±1 points in O(log n) Euclidean dimensions force average degree Omega(n^{1/2-δ}) for navigable graphs.
Problem
Constructing sparse navigable graphs for greedy nearest-neighbor routing over high-dimensional point sets, where the complete graph is trivially navigable but graph-based ANN search needs few edges.
Approach
Union of a near-neighbor graph (top m neighbors of each node, plus a greedy set cover of near-neighborhoods) gives navigability for any distance function with average degree O(sqrt(n log n)); a lower bound via sharp binomial anti-concentration shows near-neighborhoods of random points overlap little, forcing many edges under Euclidean distance.
Key results
- Any n-point set in any dimension admits a navigable graph with average degree at most 2 sqrt(n ln n), with greedy routing finishing in at most 2 steps.
- For random ±1 points in d >= (c/δ^2) log n Euclidean dimensions, any navigable graph needs average degree Omega(n^{1/2-δ}) w.h.p.
- There exist points in O(log n) dimensions where every navigable graph must have maximum out-degree n-1.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the randomized nearest-neighbor-plus-random-edges construction instead of the complete graph | Navigable graph construction · Arbitrary point set and distance function | average degree: n -> 2\sqrt{n\ln n} | Helped |
| Use the deterministic greedy set-cover construction | Navigable graph construction · Arbitrary point set and distance function | number of edges: 2n^{1.5}\sqrt{\ln n} | Helped |
Surprising findings
- Maximum degree of a navigable graph can be forced to n-1 even in O(log n) dimensions.
- Navigability holds for any distance function, even non-metric and asymmetric, with the average-degree upper bound.
Limitations
- Upper bound O(sqrt(n log n)) is not tight relative to the lower bound's n^{1/2}; the log factor gap remains.
- Navigability does not guarantee approximate nearest neighbor guarantees for queries outside the dataset.
- Lower bound applies only to random point sets and the analysis is for greedy search without beam search.
Experimental setup
Metrics: average degree maximum degree
Baselines: complete graph Delaunay graph sparse neighborhood graphs
Builds on: sparse neighborhood graphs DiskANN HNSW NSG
Closest papers by meaning
- Graph-Based Algorithms for Diverse Similarity Search (ICML 2025 · similarity 0.87)
- Sort Before You Prune: Improved Worst-Case Guarantees of the DiskANN Family of Graphs (ICML 2025 · similarity 0.86)
- Probabilistic Routing for Graph-Based Approximate Nearest Neighbor Search (ICML 2024 · similarity 0.86)
- Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search (NeurIPS 2025 · similarity 0.85)
- The Query Complexity of Local Search in Rounds on General Graphs (NeurIPS 2026 · similarity 0.85)
- CSPG: Crossing Sparse Proximity Graphs for Approximate Nearest Neighbor Search (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.