Towards Similarity Graphs Constructed by Deep Reinforcement Learning
This addresses the need for more efficient nearest neighbor search in applications like information retrieval and machine learning, representing an incremental improvement over existing heuristic-based methods.
The paper tackles the problem of constructing similarity graphs for nearest neighbor search by introducing a new algorithm based on adjacency matrix optimization and reinforcement learning to explicitly maximize search recall, achieving higher recall rates for the same number of distance computations compared to state-of-the-art graphs.
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.