# Learning to Route in Similarity Graphs

arXiv: https://arxiv.org/abs/1905.10987 · HTML: https://mlsanity.com/paper/1905.10987/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 May 2019.

## Built on by (most cited first, 9 of 9)

- [RoarGraph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2408.08933/) (2024)
- [Navigable Proximity Graph-Driven Native Hybrid Queries with Structured and Unstructured Constraints](https://mlsanity.com/paper/2203.13601/) (2022)
- [Composite Code Sparse Autoencoders for first stage retrieval](https://mlsanity.com/paper/2204.07023/) (2022)
- [CANDY: A Benchmark for Continuous Approximate Nearest Neighbor Search with Dynamic Data Ingestion](https://mlsanity.com/paper/2406.19651/) (2024)
- [Probabilistic Routing for Graph-Based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2402.11354/) (2024)
- [Probabilistic Kernel Function for Fast Angle Testing](https://mlsanity.com/paper/2505.20274/) (2025)
- [ARM 4-BIT PQ: SIMD-based Acceleration for Approximate Nearest Neighbor Search on ARM](https://mlsanity.com/paper/2203.02505/) (2022)
- [Dual-Branch HNSW Approach with Skip Bridges and LID-Driven Optimization](https://mlsanity.com/paper/2501.13992/) (2025)
- [The Virtuous Cycle: AI-Powered Vector Search and Vector Search-Augmented AI](https://mlsanity.com/paper/2603.09347/) (2026)

## Abstract (arXiv)

Recently similarity graphs became the leading paradigm for efficient nearest neighbor search, outperforming traditional tree-based and LSH-based methods. Similarity graphs perform the search via greedy routing: a query traverses the graph and in each vertex moves to the adjacent vertex that is the closest to this query. In practice, similarity graphs are often susceptible to local minima, when queries do not reach its nearest neighbors, getting stuck in suboptimal vertices. In this paper we propose to learn the routing function that overcomes local minima via incorporating information about the graph global structure. In particular, we augment the vertices of a given graph with additional representations that are learned to provide the optimal routing from the start vertex to the query nearest neighbor. By thorough experiments, we demonstrate that the proposed learnable routing successfully diminishes the local minima problem and significantly improves the overall search performance.