Learning to Route in Similarity Graphs

Dmitry Baranchuk, Dmitry Persiyanov, Anton Sinitsin, Artem Babenko
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:475-484, 2019.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v97-baranchuk19a, title = {Learning to Route in Similarity Graphs}, author = {Baranchuk, Dmitry and Persiyanov, Dmitry and Sinitsin, Anton and Babenko, Artem}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, pages = {475--484}, year = {2019}, editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan}, volume = {97}, series = {Proceedings of Machine Learning Research}, month = {09--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v97/baranchuk19a/baranchuk19a.pdf}, url = {https://proceedings.mlr.press/v97/baranchuk19a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Learning to Route in Similarity Graphs %A Dmitry Baranchuk %A Dmitry Persiyanov %A Anton Sinitsin %A Artem Babenko %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-baranchuk19a %I PMLR %P 475--484 %U https://proceedings.mlr.press/v97/baranchuk19a.html %V 97 %X 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.
APA
Baranchuk, D., Persiyanov, D., Sinitsin, A. & Babenko, A.. (2019). Learning to Route in Similarity Graphs. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:475-484 Available from https://proceedings.mlr.press/v97/baranchuk19a.html.

Related Material