Abstract
Similarity graphs are an active research direction for the nearest neighborsearch (NNS) problem. New algorithms for similarity graph construction arecontinuously being proposed and analyzed by both theoreticians andpractitioners. However, existing construction algorithms are mostly based onheuristics and do not explicitly maximize the target performance measure, i.e.,search recall. Therefore, at the moment it is not clear whether the performanceof similarity graphs has plateaued or more effective graphs can be constructedwith more theoretically grounded methods. In this paper, we introduce a newprincipled algorithm, based on adjacency matrix optimization, which explicitlymaximizes search efficiency. Namely, we propose a probabilistic model of asimilarity graph defined in terms of its edge probabilities and show how tolearn these probabilities from data as a reinforcement learning task. Asconfirmed by experiments, the proposed construction method can be used torefine the state-of-the-art similarity graphs, achieving higher recall ratesfor the same number of distance computations. Furthermore, we analyze thelearned graphs and reveal the structural properties that are responsible formore efficient search.