Probabilistic Routing for Graph-Based Approximate Nearest Neighbor Search

• URL: http://arxiv.org/abs/2402.11354v2
• Date: Wed, 10 Jul 2024 17:05:43 GMT
• Title: Probabilistic Routing for Graph-Based Approximate Nearest Neighbor Search
• Authors: Kejing Lu, Chuan Xiao, Yoshiharu Ishikawa,
• Abstract summary: Approximate nearest neighbor search (ANNS) in high-dimensional spaces is a pivotal challenge in the field of machine learning. This paper introduces a method that offers a probabilistic guarantee when exploring a node's neighbors in the graph. We then introduce PEOs, a novel approach that efficiently identifies which neighbors in the graph should be considered for exact distance calculation.
• Score: 3.934351369702082
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Approximate nearest neighbor search (ANNS) in high-dimensional spaces is a pivotal challenge in the field of machine learning. In recent years, graph-based methods have emerged as the superior approach to ANNS, establishing a new state of the art. Although various optimizations for graph-based ANNS have been introduced, they predominantly rely on heuristic methods that lack formal theoretical backing. This paper aims to enhance routing within graph-based ANNS by introducing a method that offers a probabilistic guarantee when exploring a node's neighbors in the graph. We formulate the problem as probabilistic routing and develop two baseline strategies by incorporating locality-sensitive techniques. Subsequently, we introduce PEOs, a novel approach that efficiently identifies which neighbors in the graph should be considered for exact distance calculation, thus significantly improving efficiency in practice. Our experiments demonstrate that equipping PEOs can increase throughput on commonly utilized graph indexes (HNSW and NSSG) by a factor of 1.6 to 2.5, and its efficiency consistently outperforms the leading-edge routing technique by 1.1 to 1.4 times.

Related papers

• 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)
• Fast Geometric Embedding for Node Influence Maximization [49.84018914962972]
  We introduce an efficient force layout algorithm that embeds a graph into a low-dimensional space, where the radial distance from the origin serves as a proxy for centrality measures.<n>As an application, it turns out that the proposed embedding allows to find high-influence nodes in a network, and provides a fast and scalable alternative to the standard greedy algorithm.
  arXiv  Detail & Related papers  (2025-06-09T05:21:56Z)
• Ensemble Quadratic Assignment Network for Graph Matching [52.20001802006391]
  Graph matching is a commonly used technique in computer vision and pattern recognition. Recent data-driven approaches have improved the graph matching accuracy remarkably. We propose a graph neural network (GNN) based approach to combine the advantages of data-driven and traditional methods.
  arXiv  Detail & Related papers  (2024-03-11T06:34:05Z)
• Efficient Heterogeneous Graph Learning via Random Projection [58.4138636866903]
  Heterogeneous Graph Neural Networks (HGNNs) are powerful tools for deep learning on heterogeneous graphs. Recent pre-computation-based HGNNs use one-time message passing to transform a heterogeneous graph into regular-shaped tensors. We propose a hybrid pre-computation-based HGNN, named Random Projection Heterogeneous Graph Neural Network (RpHGNN)
  arXiv  Detail & Related papers  (2023-10-23T01:25:44Z)
• General and Practical Tuning Method for Off-the-Shelf Graph-Based Index: SISAP Indexing Challenge Report by Team UTokyo [14.832208701208414]
  This study introduces a method to tune the performance of off-the-shelf graph-based indexes. We utilize a black-box optimization algorithm to perform integrated tuning to meet the required levels of recall and Queries Per Second (QPS) We got second place in the 10M and 30M tracks of SISAP 2023 Indexing Challenge.
  arXiv  Detail & Related papers  (2023-09-01T14:11:19Z)
• 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)
• SCARA: Scalable Graph Neural Networks with Feature-Oriented Optimization [23.609017952951454]
  We propose SCARA, a scalable Graph Neural Network (GNN) with feature-oriented optimization for graph computation. SCARA efficiently computes graph embedding from node features, and further selects and reuses feature results to reduce overhead. It is efficient to process precomputation on the largest available billion-scale GNN dataset Papers100M (111M nodes, 1.6B edges) in 100 seconds.
  arXiv  Detail & Related papers  (2022-07-19T10:32:11Z)
• 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)
• Benchmarking Node Outlier Detection on Graphs [90.29966986023403]
  Graph outlier detection is an emerging but crucial machine learning task with numerous applications. We present the first comprehensive unsupervised node outlier detection benchmark for graphs called UNOD.
  arXiv  Detail & Related papers  (2022-06-21T01:46:38Z)
• Distributed Graph Neural Network Training with Periodic Historical Embedding Synchronization [9.503080586294406]
  Graph Neural Networks (GNNs) are prevalent in various applications such as social network, recommender systems, and knowledge graphs. Traditional sampling-based methods accelerate GNN by dropping edges and nodes, which impairs the graph integrity and model performance. This paper proposes DIstributed Graph Embedding SynchronizaTion (DIGEST), a novel distributed GNN training framework.
  arXiv  Detail & Related papers  (2022-05-31T18:44:53Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  We propose a bi-level optimization approach for learning the optimal graph structure. We also explore a low-rank approximation model for further reducing the time complexity.
  arXiv  Detail & Related papers  (2022-05-06T03:37:00Z)
• Neighbor2vec: an efficient and effective method for Graph Embedding [0.0]
  Neighbor2vec is a framework to gather structure information by feature propagation between the node and its neighbors. We conduct experiments on several node classification and link prediction tasks for networks. Neighbor2vec's representations provide an average accuracy scores up to 6.8 percent higher than competing methods.
  arXiv  Detail & Related papers  (2022-01-07T16:08:26Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)

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.