Towards Similarity Graphs Constructed By Deep Reinforcement Learning
2019 · Dmitry Baranchuk, Artem Babenko
Abstract
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 st
Authors
(none)
Tags
Stats
Related papers
- Deep Graph Similarity Learning: A Survey (2019)13.97
- Similarity Search On Neighbor's Graphs With Automatic Pareto Optimal Performance And Minimum Expected Quality Setups Based On Hyperparameter Optimization (2022)0.00
- Graph-based Nearest Neighbor Search: From Practice To Theory (2019)0.00
- Understanding And Generalizing Monotonic Proximity Graphs For Approximate Nearest Neighbor Search (2021)0.00
- Simgnn: A Neural Network Approach To Fast Graph Similarity Computation (2018)0.00
- S\(^3\)GND: An Effective Learning-based Approach For Subgraph Similarity Search Under Generalized Neighbor Difference Semantics (technical Report) (2026)0.00
- A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph (2023)0.00
- Fast Approximate Nearest Neighbor Search With A Dynamic Exploration Graph Using Continuous Refinement (2023)0.00