# Towards Similarity Graphs Constructed by Deep Reinforcement Learning

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

## Key facts

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

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

- [A Survey on Deep Reinforcement Learning for Data Processing and Analytics](https://mlsanity.com/paper/2108.04526/) (2021)
- [LEANN: A Low-Storage Vector Index](https://mlsanity.com/paper/2506.08276/) (2025)

## Abstract (arXiv)

Similarity graphs are an active research direction for the nearest neighbor search (NNS) problem. New algorithms for similarity graph construction are continuously being proposed and analyzed by both theoreticians and practitioners. However, existing construction algorithms are mostly based on heuristics and do not explicitly maximize the target performance measure, i.e., search recall. Therefore, at the moment it is not clear whether the performance of similarity graphs has plateaued or more effective graphs can be constructed with more theoretically grounded methods. In this paper, we introduce a new principled algorithm, based on adjacency matrix optimization, which explicitly maximizes search efficiency. Namely, we propose a probabilistic model of a similarity graph defined in terms of its edge probabilities and show how to learn these probabilities from data as a reinforcement learning task. As confirmed by experiments, the proposed construction method can be used to refine the state-of-the-art similarity graphs, achieving higher recall rates for the same number of distance computations. Furthermore, we analyze the learned graphs and reveal the structural properties that are responsible for more efficient search.