Fugu-MT 論文翻訳(概要): Probabilistic Routing for Graph-Based Approximate Nearest Neighbor Search

論文の概要: Probabilistic Routing for Graph-Based Approximate Nearest Neighbor Search

arxiv url: http://arxiv.org/abs/2402.11354v2
Date: Wed, 10 Jul 2024 17:05:43 GMT
ステータス: 処理完了
システム内更新日: 2024-07-11 21:49:49.272584
Title: Probabilistic Routing for Graph-Based Approximate Nearest Neighbor Search
Title（参考訳）: グラフに基づく近似近傍探索のための確率的ルーティング
Authors: Kejing Lu, Chuan Xiao, Yoshiharu Ishikawa,
Abstract要約: 高次元空間における近似近接探索(ANNS)は、機械学習分野における重要な課題である。本稿では,グラフ内のノードの近傍を探索する際の確率的保証を提供する手法を提案する。次に,グラフ内のどの近傍が正確な距離計算を行うべきかを効率的に同定する新しい手法PEOを紹介する。
参考スコア（独自算出の注目度）: 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.
Abstract（参考訳）: 高次元空間における近似近接探索(ANNS)は、機械学習分野における重要な課題である。近年、ANNSの優れたアプローチとしてグラフベースの手法が登場し、新しい最先端技術が確立されている。グラフベースのANNSの様々な最適化が導入されたが、それらは主に公式な理論的裏付けを持たないヒューリスティックな手法に依存している。本稿では,グラフ内のノードの近傍を探索する際の確率的保証を提供する手法を導入することにより,グラフベースのANNS内のルーティングを強化することを目的とする。確率的ルーティングとして問題を定式化し、局所性に敏感な手法を取り入れた2つのベースライン戦略を開発する。次に,グラフ内のどの近傍が正確な距離計算を行うべきかを効率的に同定し,実際の効率を大幅に向上させるPEOを紹介した。実験により, PEOの装備により, 一般的に利用されるグラフインデックス(HNSW, NSSG)のスループットが1.6～2.5倍に向上し, その効率は1.1～1.4倍に向上することを示した。

関連論文リスト

Ensemble Quadratic Assignment Network for Graph Matching [52.20001802006391]
グラフマッチングはコンピュータビジョンやパターン認識において一般的に用いられる技法である。最近のデータ駆動型アプローチは、グラフマッチングの精度を著しく改善した。データ駆動手法と従来の手法の利点を組み合わせたグラフニューラルネットワーク(GNN)に基づくアプローチを提案する。
論文参考訳（メタデータ） (2024-03-11T06:34:05Z)
Efficient Heterogeneous Graph Learning via Random Projection [58.4138636866903]
不均一グラフニューラルネットワーク(HGNN)は、異種グラフを深層学習するための強力なツールである。最近のプリ計算ベースのHGNNは、一時間メッセージパッシングを使用して不均一グラフを正規形テンソルに変換する。我々はRandom Projection Heterogeneous Graph Neural Network (RpHGNN) というハイブリッド計算前HGNNを提案する。
論文参考訳（メタデータ） (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]
本研究では,市販のグラフベースインデックスの性能をチューニングする手法を提案する。我々はブラックボックス最適化アルゴリズムを用いて、必要なリコールレベルと待ち時間(QPS)を満たす統合チューニングを行う。 SISAP 2023 Indexing Challengeの10万トラックと3000万トラックで2位になった。
論文参考訳（メタデータ） (2023-09-01T14:11:19Z)
A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph [51.880164098926166]
グラフベースのアルゴリズムは、近隣探索(NN-Search)問題において最先端の性能を示す。グラフベースのNN-Searchアルゴリズムには実践と理論のギャップがある。低次元および高密度ベクトルに対する ANN-Graph 上の欲求探索による NN-Search の解法を理論的に保証する。
論文参考訳（メタデータ） (2023-03-10T21:18:34Z)
SCARA: Scalable Graph Neural Networks with Feature-Oriented Optimization [23.609017952951454]
グラフ計算のための特徴指向最適化を備えたスケーラブルグラフニューラルネットワーク(GNN)であるSCARAを提案する。 SCARAはノードの特徴からグラフの埋め込みを効率的に計算し、機能の結果を選択して再利用することでオーバーヘッドを減らします。利用可能な最大10億のGNNデータセットであるPapers100M(1110万ノード、1.6Bエッジ)を100秒でプリ計算するのが効率的である。
論文参考訳（メタデータ） (2022-07-19T10:32:11Z)
FINGER: Fast Inference for Graph-based Approximate Nearest Neighbor Search [20.928821121591493]
効率的なグラフ探索を実現するための高速推論手法であるFINGERを提案する。 FINGERは、近傍の残差ベクトルと低ランク基底と分布マッチングとの角度を推定することで距離関数を近似する。実証的に、FINGERによるHNSWと呼ばれるグラフベースの手法の高速化は、異なるベンチマークデータセット間で既存のグラフベースの手法を20%から60%上回っている。
論文参考訳（メタデータ） (2022-06-22T22:30:46Z)
Benchmarking Node Outlier Detection on Graphs [90.29966986023403]
グラフの外れ値検出は、多くのアプリケーションにおいて、新しいが重要な機械学習タスクである。 UNODと呼ばれるグラフに対して、最初の包括的教師なしノード外乱検出ベンチマークを示す。
論文参考訳（メタデータ） (2022-06-21T01:46:38Z)
Distributed Graph Neural Network Training with Periodic Historical Embedding Synchronization [9.503080586294406]
グラフニューラルネットワーク(GNN)は、ソーシャルネットワーク、レコメンダシステム、ナレッジグラフなどの様々なアプリケーションで広く使われている。従来のサンプリングベースの手法は、エッジとノードをドロップすることでGNNを加速し、グラフの整合性とモデル性能を損なう。本稿では,新しい分散GNNトレーニングフレームワークであるDIstributed Graph Embedding SynchronizaTion (DIGEST)を提案する。
論文参考訳（メタデータ） (2022-05-31T18:44:53Z)
Optimal Propagation for Graph Neural Networks [51.08426265813481]
最適グラフ構造を学習するための二段階最適化手法を提案する。また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
論文参考訳（メタデータ） (2022-05-06T03:37:00Z)
Neighbor2vec: an efficient and effective method for Graph Embedding [0.0]
Neighbor2vecは、ノードとその隣人の特徴伝搬によって構造情報を収集するフレームワークである。ネットワークのノード分類とリンク予測タスクについて実験を行った。 Neighbor2vecの表現は、競合する手法よりも平均6.8%高いスコアを提供する。
論文参考訳（メタデータ） (2022-01-07T16:08:26Z)
Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。本稿では,非自明なERGに対する近似フレームワークを提案する。我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文参考訳（メタデータ） (2020-02-14T11:42:16Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。