Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search

• URL: http://arxiv.org/abs/2505.15636v1
• Date: Wed, 21 May 2025 15:18:53 GMT
• Title: Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search
• Authors: Yousef Al-Jazzazi, Haya Diwan, Jinrui Gou, Cameron Musco, Christopher Musco, Torsten Suel,
• Abstract summary: We propose a new distance-based termination condition for beam search to replace the commonly used condition based on beam width.<n>We prove that, as long as the search graph is navigable, our resulting Adaptive Beam Search method is guaranteed to approximately solve the nearest-neighbor problem.<n>We find that Adaptive Beam Search outperforms standard beam search over a range of recall values, data sets, graph constructions, and target number of nearest neighbors.
• Score: 23.208935102841103
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Nearest neighbor search is central in machine learning, information retrieval, and databases. For high-dimensional datasets, graph-based methods such as HNSW, DiskANN, and NSG have become popular thanks to their empirical accuracy and efficiency. These methods construct a directed graph over the dataset and perform beam search on the graph to find nodes close to a given query. While significant work has focused on practical refinements and theoretical understanding of graph-based methods, many questions remain. We propose a new distance-based termination condition for beam search to replace the commonly used condition based on beam width. We prove that, as long as the search graph is navigable, our resulting Adaptive Beam Search method is guaranteed to approximately solve the nearest-neighbor problem, establishing a connection between navigability and the performance of graph-based search. We also provide extensive experiments on our new termination condition for both navigable graphs and approximately navigable graphs used in practice, such as HNSW and Vamana graphs. We find that Adaptive Beam Search outperforms standard beam search over a range of recall values, data sets, graph constructions, and target number of nearest neighbors. It thus provides a simple and practical way to improve the performance of popular methods.

Related papers

• Skeleton-Guided Learning for Shortest Path Search [31.51778160288742]
  Shortest path search is a core operation in graph-based applications.<n>We propose a versatile learning-based framework for shortest path search on generic graphs.
  arXiv  Detail & Related papers  (2025-08-04T10:21:52Z)
• Empowering Graph-based Approximate Nearest Neighbor Search with Adaptive Awareness Capabilities [19.352675865525395]
  This paper proposes GATE, high-tier proximity Graph with Adaptive Topology and Query AwarEness.<n>Gate achieves a 1.2-2.0X speed-up in query performance compared to state-of-the-art graph-based indexes.
  arXiv  Detail & Related papers  (2025-06-19T03:07:12Z)
• Theoretical and Empirical Analysis of Adaptive Entry Point Selection for Graph-based Approximate Nearest Neighbor Search [14.832208701208414]
  We present a theoretical and empirical analysis of the adaptive entry point selection for graph-based approximate nearest neighbor search (ANNS) We introduce novel concepts: $btextit-monotonic path$ and $Btextit-MSNET. We prove that adaptive entry point selection offers better performance upper bound than the fixed central entry point under more general conditions than previous work.
  arXiv  Detail & Related papers  (2024-02-07T10:05:42Z)
• ProvG-Searcher: A Graph Representation Learning Approach for Efficient Provenance Graph Search [13.627536649679577]
  We present ProvG-Searcher, a novel approach for detecting known APT behaviors within system security logs. We formulate the task of searching provenance graphs as a subgraph matching problem and employ a graph representation learning method. Experimental results on standard datasets demonstrate that ProvG-Searcher achieves superior performance, with an accuracy exceeding 99% in detecting query behaviors.
  arXiv  Detail & Related papers  (2023-09-07T11:29:01Z)
• Learnable Graph Matching: A Practical Paradigm for Data Association [74.28753343714858]
  We propose a general learnable graph matching method to address these issues. Our method achieves state-of-the-art performance on several MOT datasets. For image matching, our method outperforms state-of-the-art methods on a popular indoor dataset, ScanNet.
  arXiv  Detail & Related papers  (2023-03-27T17:39:00Z)
• A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph [51.880164098926166]
  Graph-based algorithms have demonstrated state-of-the-art performance in the nearest neighbor search (NN-Search) problem. There exists a practice-to-theory gap in the graph-based NN-Search algorithms. We present theoretical guarantees of solving NN-Search via greedy search on ANN-Graph for low dimensional and dense vectors.
  arXiv  Detail & Related papers  (2023-03-10T21:18:34Z)
• Subgraph Matching via Query-Conditioned Subgraph Matching Neural Networks and Bi-Level Tree Search [33.9052190473029]
  Subgraph Matching is a core operation in graph database search, biomedical analysis, social group finding, etc. In this paper, we propose a novel encoder-decoder neural network architecture to dynamically compute the matching information between the query and the target graphs. Experiments on five large real-world target graphs show that N-BLS can significantly improve the subgraph matching performance.
  arXiv  Detail & Related papers  (2022-07-21T04:47:21Z)
• FINGER: Fast Inference for Graph-based Approximate Nearest Neighbor Search [20.928821121591493]
  We propose FINGER, a fast inference method to achieve efficient graph search. FINGER approximates the distance function by estimating angles between neighboring residual vectors with low-rank bases and distribution matching. Empirically, accelerating a popular graph-based method named HNSW by FINGER is shown to outperform existing graph-based methods by 20%-60% across different benchmark datasets.
  arXiv  Detail & Related papers  (2022-06-22T22:30:46Z)
• Automatic Relation-aware Graph Network Proliferation [182.30735195376792]
  We propose Automatic Relation-aware Graph Network Proliferation (ARGNP) for efficiently searching GNNs. These operations can extract hierarchical node/relational information and provide anisotropic guidance for message passing on a graph. Experiments on six datasets for four graph learning tasks demonstrate that GNNs produced by our method are superior to the current state-of-the-art hand-crafted and search-based GNNs.
  arXiv  Detail & Related papers  (2022-05-31T10:38:04Z)
• Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching [58.39970828272366]
  Subgraph matching algorithms enumerate all is embeddings of a query graph in a data graph G. matching order plays a critical role in time efficiency of these backtracking based subgraph matching algorithms. In this paper, for the first time we apply the Reinforcement Learning (RL) and Graph Neural Networks (GNNs) techniques to generate the high-quality matching order for subgraph matching algorithms.
  arXiv  Detail & Related papers  (2022-01-25T00:10:03Z)
• Learnable Graph Matching: Incorporating Graph Partitioning with Deep Feature Learning for Multiple Object Tracking [58.30147362745852]
  Data association across frames is at the core of Multiple Object Tracking (MOT) task. Existing methods mostly ignore the context information among tracklets and intra-frame detections. We propose a novel learnable graph matching method to address these issues.
  arXiv  Detail & Related papers  (2021-03-30T08:58:45Z)
• Line Graph Neural Networks for Link Prediction [71.00689542259052]
  We consider the graph link prediction task, which is a classic graph analytical problem with many real-world applications. In this formalism, a link prediction problem is converted to a graph classification task. We propose to seek a radically different and novel path by making use of the line graphs in graph theory. In particular, each node in a line graph corresponds to a unique edge in the original graph. Therefore, link prediction problems in the original graph can be equivalently solved as a node classification problem in its corresponding line graph, instead of a graph classification task.
  arXiv  Detail & Related papers  (2020-10-20T05:54:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.