Learning to Route in Similarity Graphs (arxiv)

The paper improves Similarity Graphs for large-scale Nearest Neighbor Search by training an agent to efficiently navigate the graph with deep imitation learning. Put simply, these guys train the search engine to better navigate the graph of all images so as to find the nearest neighbours. Basically Deep Imitation Learning meets Graph Convolutional Networks meets Web/Image Search and other fancy large-scale applications.

Toy example. Each node represents one data point (e.g. image). Given the query “q”, the algorithm navigates the graph from “start” vertex to find the nearest neighbour “gt” for the query. The yellow path follows the oririginal search procedure, the orange path corresponds to the learned agent.

​

Read the paper (arxiv) , browse the code (github) or talk to authors at ICML right about now if you’re attending 🙂

(source: saw the paper at icml, acquainted with the authors)