Graph-based nearest neighbor search

Graph-based NNS.png

Graph-based approaches

NNS example.gif
Example of graph-based greedy search


Discovering graph structures and search algorithms

imitation learning icml.png
Imitation learning for graph-based search. The agent walks over the graph (black arrows). The expert (BFS) provides the correct choices at each step (red arrows). Finally, the agent is updated in a supervised manner.
RL graph construction.png
RL scheme for graph construction. Left: the environment is a similarity graph equipped with a search algorithm. Right: the agent obtains the state and uses policy network to predict which outgoing edges to preserve.

Theoretical guarantees

Euclidean space

Hyperbolic space



  1. Muja M., Lowe D. G. “Fast approximate nearest neighbors with automatic algorithm configuration.” VISSAPP 2009.
  2. Dasgupta S., Sinha K. “Randomized partition trees for exact nearest neighbor search.” COLT 2013.
  3. Jégou H., Douze M., Schmid C. “Product quantization for nearest neighbor search.” TPAMI 2011.
  4. Babenko, A., Lempitsky, V. S. “The inverted multi-index.” CVPR 2012.
  5. Andoni A., Indyk P., Laarhoven T., Razenshteyn I., Schmidt L. “Practical and optimal LSH for angular distance.” NeuriPS 2015.
  6. Malkov Y. A., Yashunin D. A. “Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs.” TPAMI 2018.
  7. Fu C., Xiang C., Wang C., Cai D. “Fast approximate nearest neighbor search with the navigating spreading-out graph.” VLDB 2019.
  8. Iwasaki M., Miyazaki D. “Optimization of indexing based on k-nearest neighbor graph for proximity.” 2018.
  9. Morozov S., Babenko A. “Non-metric similarity graphs for maximum inner product search.” NeurIPS 2018.
  10. Prokhorenkova L., Baranchuk D., Bogachev N., Demidovich Y., Kolpakov A. “Graph-based nearest neighbor search in hyperbolic spaces.” ICLR 2022.
  11. Morozov S. and Babenko A. “Relevance proximity graphs for fast relevance retrieval.” 2019.
  12. Baranchuk D., Babenko A., Malkov Y. “Revisiting the inverted indices for billion-scale approximate nearest neighbors.” ECCV 2018.
  13. Baranchuk D., Persiyanov D., Sinitsin A., Babenko A. “Learning to route in similarity graphs.” ICML 2019.
  14. Baranchuk D., Babenko A. "Towards similarity graphs constructed by deep reinforcement learning.” 2019.
  15. Prokhorenkova L., Shekhovtsov A. “Graph-based nearest neighbor search: From practice to theory.” ICML 2020.