Timezone: »
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.
Author Information
Dmitry Baranchuk (Yandex)
Dmitry Persiyanov (Yandex)
Anton Sinitsin (HSE)
Artem Babenko (Yandex)
Related Events (a corresponding poster, oral, or spotlight)
-
2019 Poster: Learning to Route in Similarity Graphs »
Thu Jun 13th 01:30 -- 04:00 AM Room Pacific Ballroom
More from the Same Authors
-
2020 Poster: Unsupervised Discovery of Interpretable Directions in the GAN Latent Space »
Andrey Voynov · Artem Babenko