On the Effectiveness of Graph Reordering for Accelerating Approximate Nearest Neighbor Search on GPU

• URL: http://arxiv.org/abs/2508.15436v1
• Date: Thu, 21 Aug 2025 10:50:49 GMT
• Title: On the Effectiveness of Graph Reordering for Accelerating Approximate Nearest Neighbor Search on GPU
• Authors: Yutaro Oguri, Mai Nishimura, Yusuke Matsui,
• Abstract summary: Graph-based Approximate Nearest Neighbor Search (ANNS) has become the dominant paradigm for modern AI applications.<n>We present the first systematic investigation of graph reordering effects for graph-based ANNS on a GPU.
• Score: 14.338954144116759
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present the first systematic investigation of graph reordering effects for graph-based Approximate Nearest Neighbor Search (ANNS) on a GPU. While graph-based ANNS has become the dominant paradigm for modern AI applications, recent approaches focus on algorithmic innovations while neglecting memory layout considerations that significantly affect execution time. Our unified evaluation framework enables comprehensive evaluation of diverse reordering strategies across different graph indices through a graph adapter that converts arbitrary graph topologies into a common representation and a GPU-optimized graph traversal engine. We conduct a comprehensive analysis across diverse datasets and state-of-the-art graph indices, introducing analysis metrics that quantify the relationship between structural properties and memory layout effectiveness. Our GPU-targeted reordering achieves up to 15$\%$ QPS improvements while preserving search accuracy, demonstrating that memory layout optimization operates orthogonally to existing algorithmic innovations. We will release all code upon publication to facilitate reproducibility and foster further research.

Related papers

• GPU-Accelerated Algorithms for Graph Vector Search: Taxonomy, Empirical Study, and Research Directions [54.570944939061555]
  We present a comprehensive study of GPU-accelerated graph-based vector search algorithms.<n>We establish a detailed taxonomy of GPU optimization strategies and clarify the mapping between algorithmic tasks and hardware execution units.<n>Our findings offer clear guidelines for designing scalable and robust GPU-powered approximate nearest neighbor search systems.
  arXiv  Detail & Related papers  (2026-02-10T16:18:04Z)
• Global optimization of graph acquisition functions for neural architecture search [6.266977090949175]
  Graph Bayesian optimization has shown potential as a powerful and data-efficient tool for neural architecture search (NAS)<n>This paper presents explicit optimization formulations for graph input space including properties such as reachability and shortest paths.<n>We theoretically prove that the proposed encoding is an equivalent representation of the graph space and provide restrictions for the NAS domain with either node or edge labels.
  arXiv  Detail & Related papers  (2025-05-29T16:46:29Z)
• Amplify Graph Learning for Recommendation via Sparsity Completion [16.32861024767423]
  Graph learning models have been widely deployed in collaborative filtering (CF) based recommendation systems. Due to the issue of data sparsity, the graph structure of the original input lacks potential positive preference edges. We propose an Amplify Graph Learning framework based on Sparsity Completion (called AGL-SC)
  arXiv  Detail & Related papers  (2024-06-27T08:26:20Z)
• Differentiable Proximal Graph Matching [40.41380102260085]
  We introduce an algorithm for graph matching based on the proximal operator, referred to as differentiable proximal graph matching (DPGM) The whole algorithm can be considered as a differentiable map from the graph affinity matrix to the prediction of node correspondence. Numerical experiments show that PGM outperforms existing graph matching algorithms on diverse datasets.
  arXiv  Detail & Related papers  (2024-05-26T08:17:13Z)
• Hierarchical Attention and Graph Neural Networks: Toward Drift-Free Pose Estimation [1.745925556687899]
  The most commonly used method for addressing 3D geometric registration is the iterative closet-point algorithm. We propose a framework that replaces traditional geometric registration and pose graph optimization with a learned model utilizing hierarchical attention mechanisms and graph neural networks.
  arXiv  Detail & Related papers  (2023-09-18T16:51:56Z)
• 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)
• Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
  We propose a unified graph signal sampling framework which enjoys the benefits of graph signal analysis and processing. The key idea is to transform each user's ratings on the items to a function (signal) on the vertices of an item-item graph. For the online setting, we develop a Bayesian extension, i.e., BGS-IMC which considers continuous random Gaussian noise in the graph Fourier domain.
  arXiv  Detail & Related papers  (2023-02-08T08:17:43Z)
• EGRC-Net: Embedding-induced Graph Refinement Clustering Network [66.44293190793294]
  We propose a novel graph clustering network called Embedding-Induced Graph Refinement Clustering Network (EGRC-Net) EGRC-Net effectively utilizes the learned embedding to adaptively refine the initial graph and enhance the clustering performance. Our proposed methods consistently outperform several state-of-the-art approaches.
  arXiv  Detail & Related papers  (2022-11-19T09:08:43Z)
• 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)
• 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)
• GraphCoCo: Graph Complementary Contrastive Learning [65.89743197355722]
  Graph Contrastive Learning (GCL) has shown promising performance in graph representation learning (GRL) without the supervision of manual annotations. This paper proposes an effective graph complementary contrastive learning approach named GraphCoCo to tackle the above issue.
  arXiv  Detail & Related papers  (2022-03-24T02:58:36Z)
• Enhancing Balanced Graph Edge Partition with Effective Local Search [41.4257628524592]
  Graph partition is a key component to achieve workload balance and reduce job completion time in parallel graph processing systems. In this paper, we study local search algorithms for this problem to further improve the partition results from existing methods.
  arXiv  Detail & Related papers  (2020-12-17T08:58:06Z)

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.