論文の概要: Empowering Graph-based Approximate Nearest Neighbor Search with Adaptive Awareness Capabilities
- arxiv url: http://arxiv.org/abs/2506.15986v1
- Date: Thu, 19 Jun 2025 03:07:12 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-23 19:00:04.922351
- Title: Empowering Graph-based Approximate Nearest Neighbor Search with Adaptive Awareness Capabilities
- Title（参考訳）: 適応的認識能力を有するグラフベース近似近傍探索
- Authors: Jiancheng Ruan, Tingyang Chen, Renchi Yang, Xiangyu Ke, Yunjun Gao,
- Abstract要約: 本稿では,Adaptive Topology とQuery AwarEness を用いた GATE, High-tier Near Graph を提案する。
Gateは、最先端のグラフベースのインデックスと比較して、クエリパフォーマンスの1.2-2.0倍の高速化を実現している。
- 参考スコア（独自算出の注目度）: 19.352675865525395
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Approximate Nearest Neighbor Search (ANNS) in high-dimensional spaces finds extensive applications in databases, information retrieval, recommender systems, etc. While graph-based methods have emerged as the leading solution for ANNS due to their superior query performance, they still face several challenges, such as struggling with local optima and redundant computations. These issues arise because existing methods (i) fail to fully exploit the topological information underlying the proximity graph G, and (ii) suffer from severe distribution mismatches between the base data and queries in practice. To this end, this paper proposes GATE, high-tier proximity Graph with Adaptive Topology and Query AwarEness, as a lightweight and adaptive module atop the graph-based indexes to accelerate ANNS. Specifically, GATE formulates the critical problem to identify an optimal entry point in the proximity graph for a given query, facilitating faster online search. By leveraging the inherent clusterability of high-dimensional data, GATE first extracts a small set of hub nodes V as candidate entry points. Then, resorting to a contrastive learning-based two-tower model, GATE encodes both the structural semantics underlying G and the query-relevant features into the latent representations of these hub nodes V. A navigation graph index on V is further constructed to minimize the model inference overhead. Extensive experiments demonstrate that GATE achieves a 1.2-2.0X speed-up in query performance compared to state-of-the-art graph-based indexes.
- Abstract（参考訳）: 高次元空間における近似Nearest Neighbor Search (ANNS) は、データベース、情報検索、レコメンダシステムなどにおいて広範囲に応用されている。
グラフベースの手法は、より優れたクエリ性能のためにANNSの主要なソリューションとして現れてきたが、ローカルな最適化や冗長な計算に苦しむなど、いくつかの課題に直面している。
これらの問題は既存の方法が原因で生じる
i) 近接グラフGの下の位相情報を十分に活用することができず、
(II) 実際には, ベースデータとクエリ間の分布ミスマッチに悩まされている。
そこで本稿では,ANNS を高速化するグラフベースインデックス上の軽量かつ適応的なモジュールとして,Adaptive Topology と Query AwarEness を備えた高層グラフ GATE を提案する。
特に、GATEは、与えられたクエリの近接グラフの最適なエントリポイントを特定するために重要な問題を定式化し、より高速なオンライン検索を容易にする。
高次元データの固有のクラスタビリティを活用することにより、GATEはまず、候補エントリポイントとして小さなハブノードVの集合を抽出する。
そして、対照的な学習に基づく2-towerモデルを用いて、Gの構造的セマンティクスとクエリ関連特徴の両方をこれらのハブノードの潜在表現にエンコードする。
GATEは最新のグラフベースインデックスと比較してクエリ性能が1.2-2.0倍に向上することを示した。
関連論文リスト
- Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search [23.208935102841103]
そこで本研究では,ビーム幅に基づくビームサーチのための距離に基づく新しい終端条件を提案する。
探索グラフがナビゲート可能である限り, 得られたアダプティブビームサーチ法は, ほぼ隣り合う問題を解くことが保証されている。
アダプティブビームサーチは、様々なリコール値、データセット、グラフ構造、および最も近い隣人のターゲット数において、標準ビームサーチより優れています。
論文 参考訳（メタデータ） (2025-05-21T15:18:53Z) - Theoretical and Empirical Analysis of Adaptive Entry Point Selection for
Graph-based Approximate Nearest Neighbor Search [14.832208701208414]
グラフベースニアニアニアサーチ(ANNS)における適応エントリーポイント選択の理論的および経験的分析を提案する。
btextit-monotonic path$と$Btextit-MSNETという新しい概念を紹介します。
適応的なエントリポイント選択は、以前の作業よりも一般的な条件下で、固定された中央エントリポイントよりも優れたパフォーマンスの上限を提供することを示す。
論文 参考訳（メタデータ） (2024-02-07T10:05:42Z) - On Exploring Node-feature and Graph-structure Diversities for Node Drop
Graph Pooling [86.65151066870739]
現在のノードドロッププーリング法は、ノードの特徴やグラフ構造の観点からグラフの多様性を無視し、結果としてグラフレベル以下の表現をもたらす。
そこで本稿では,textiti.fltextbfIpscore と textbfDropscore の2つの操作を持つ textbfMulti スコア空間からなる MID を新たに提案する。
具体的には、多次元スコア空間は、複数の基準を通してノードの重要さを描いており、フリップスコアは異種ノードの維持を奨励している。
論文 参考訳（メタデータ） (2023-06-22T08:02:01Z) - EGRC-Net: Embedding-induced Graph Refinement Clustering Network [66.44293190793294]
埋め込みによるグラフリファインメントクラスタリングネットワーク (EGRC-Net) という新しいグラフクラスタリングネットワークを提案する。
EGRC-Netは学習した埋め込みを利用して初期グラフを適応的に洗練し、クラスタリング性能を向上させる。
提案手法はいくつかの最先端手法より一貫して優れている。
論文 参考訳（メタデータ） (2022-11-19T09:08:43Z) - Subgraph Matching via Query-Conditioned Subgraph Matching Neural
Networks and Bi-Level Tree Search [33.9052190473029]
サブグラフマッチングは、グラフデータベース検索、バイオメディカル分析、ソーシャルグループ検索などにおける中核的な操作である。
本稿では,クエリと対象グラフのマッチング情報を動的に計算する,新しいエンコーダ・デコーダニューラルネットワークアーキテクチャを提案する。
5つの大きな実世界のターゲットグラフの実験により、N-BLSはサブグラフマッチング性能を大幅に改善できることが示された。
論文 参考訳（メタデータ） (2022-07-21T04:47:21Z) - Automatic Relation-aware Graph Network Proliferation [182.30735195376792]
GNNを効率的に検索するためのARGNP(Automatic Relation-Aware Graph Network Proliferation)を提案する。
これらの操作は階層的なノード/リレーショナル情報を抽出し、グラフ上のメッセージパッシングのための異方的ガイダンスを提供する。
4つのグラフ学習タスクのための6つのデータセットの実験により、我々の手法によって生成されたGNNは、現在最先端の手作りおよび検索に基づくGNNよりも優れていることが示された。
論文 参考訳（メタデータ） (2022-05-31T10:38:04Z) - Optimal Propagation for Graph Neural Networks [51.08426265813481]
最適グラフ構造を学習するための二段階最適化手法を提案する。
また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
論文 参考訳（メタデータ） (2022-05-06T03:37:00Z) - Reinforcement Learning Based Query Vertex Ordering Model for Subgraph
Matching [58.39970828272366]
グラフマッチングアルゴリズムは、クエリグラフの埋め込みをデータグラフGに列挙する。
マッチング順序は、これらのバックトラックに基づくサブグラフマッチングアルゴリズムの時間効率において重要な役割を果たす。
本稿では,Reinforcement Learning (RL) と Graph Neural Networks (GNN) 技術を適用して,グラフマッチングアルゴリズムの高品質なマッチング順序を生成する。
論文 参考訳（メタデータ） (2022-01-25T00:10:03Z) - Spatial-Spectral Clustering with Anchor Graph for Hyperspectral Image [88.60285937702304]
本稿では、HSIデータクラスタリングのための空間スペクトルクラスタリングとアンカーグラフ(SSCAG)という新しい非監視アプローチを提案する。
提案されたSSCAGは最先端のアプローチと競合する。
論文 参考訳（メタデータ） (2021-04-24T08:09:27Z) - GLSearch: Maximum Common Subgraph Detection via Learning to Search [33.9052190473029]
検索モデルに対するグラフニューラルネットワーク(GNN)に基づく学習手法であるGLSearchを提案する。
このモデルでは2つの入力グラフから1対のノードを選択して一度に拡張する。
我々のGLSearchは、グラフ上の制約で他の多くの問題を解決するために拡張できる可能性がある。
論文 参考訳（メタデータ） (2020-02-08T10:03:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。