Towards Similarity Graphs Constructed by Deep Reinforcement Learning
  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.
