論文の概要: The kernel of graph indices for vector search

• arxiv url: http://arxiv.org/abs/2506.20584v1
• Date: Wed, 25 Jun 2025 16:24:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-26 21:00:42.842862
• Title: The kernel of graph indices for vector search
• Title（参考訳）: ベクトル探索のためのグラフ指標の核
• Authors: Mariano Tepper, Ted Willke,
• Abstract要約: 機械学習を用いて,距離空間および非距離ベクトル空間におけるベクトル探索のためのグラフインデックスを構築することができることを示す。 本稿では,距離空間と非距離ベクトル空間で有効となる公式なナビゲート性を保証するグラフインデックスであるSupport Vector Graph(SVG)を紹介する。
• 参考スコア（独自算出の注目度）: 0.9821874476902968
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The most popular graph indices for vector search use principles from computational geometry to build the graph. Hence, their formal graph navigability guarantees are only valid in Euclidean space. In this work, we show that machine learning can be used to build graph indices for vector search in metric and non-metric vector spaces (e.g., for inner product similarity). From this novel perspective, we introduce the Support Vector Graph (SVG), a new type of graph index that leverages kernel methods to establish the graph connectivity and that comes with formal navigability guarantees valid in metric and non-metric vector spaces. In addition, we interpret the most popular graph indices, including HNSW and DiskANN, as particular specializations of SVG and show that new indices can be derived from the principles behind this specialization. Finally, we propose SVG-L0 that incorporates an $\ell_0$ sparsity constraint into the SVG kernel method to build graphs with a bounded out-degree. This yields a principled way of implementing this practical requirement, in contrast to the traditional heuristic of simply truncating the out edges of each node. Additionally, we show that SVG-L0 has a self-tuning property that avoids the heuristic of using a set of candidates to find the out-edges of each node and that keeps its computational complexity in check.
• Abstract（参考訳）: ベクトル探索における最も一般的なグラフ指標は、計算幾何学からグラフを構築するための原理である。 したがって、それらの公式グラフナビビビリティ保証はユークリッド空間でのみ有効である。 本研究では,距離空間と非計量ベクトル空間(例えば内積類似性)におけるベクトル探索のためのグラフインデックスを構築するために,機械学習が利用できることを示す。 この新たな視点から、我々は、グラフ接続を確立するためにカーネルメソッドを活用する新しいタイプのグラフインデックスであるSupport Vector Graph (SVG)を導入する。 さらに,HNSW や DiskANN などのグラフ指標を SVG の特殊化として解釈し,この特殊化の背景にある原理から新たな指標を導出できることを示す。 最後に,SVGカーネル法に$\ell_0$スペーサ性制約を組み込んだSVG-L0を提案する。 これは、各ノードのアウトエッジを単に切り刻むという従来のヒューリスティックとは対照的に、この実践的な要件を実装する原則的な方法をもたらす。 さらに,SVG-L0の自己調整特性は,各ノードのアウトエッジを見つけるために一連の候補を用いることのヒューリスティックさを回避し,計算複雑性をチェックできることを示す。

関連論文リスト

• Discrete Graph Auto-Encoder [52.50288418639075]
  離散グラフオートエンコーダ(DGAE)という新しいフレームワークを導入する。 まず、置換同変オートエンコーダを用いてグラフを離散潜在ノード表現の集合に変換する。 2番目のステップでは、離散潜在表現の集合をソートし、特別に設計された自己回帰モデルを用いてそれらの分布を学習する。
  論文  参考訳（メタデータ） (2023-06-13T12:40:39Z)
• Seq-HGNN: Learning Sequential Node Representation on Heterogeneous Graph [57.2953563124339]
  本稿では,シーケンシャルノード表現,すなわちSeq-HGNNを用いた新しい異種グラフニューラルネットワークを提案する。 Heterogeneous Graph Benchmark (HGB) と Open Graph Benchmark (OGB) の4つの広く使われているデータセットについて広範な実験を行った。
  論文  参考訳（メタデータ） (2023-05-18T07:27:18Z)
• Embedding Graphs on Grassmann Manifold [31.42901131602713]
  本稿では,グラスマン多様体に近似した2階グラフ特性を組み込んだ新しいグラフ表現学習手法EGGを提案する。 EGGの有効性はノードレベルとグラフレベルでのクラスタリングと分類タスクの両方を用いて示される。
  論文  参考訳（メタデータ） (2022-05-30T12:56:24Z)
• Node Feature Extraction by Self-Supervised Multi-scale Neighborhood Prediction [123.20238648121445]
  我々は、新しい自己教師型学習フレームワーク、グラフ情報支援ノード機能exTraction (GIANT)を提案する。 GIANT は eXtreme Multi-label Classification (XMC) 形式を利用しており、これはグラフ情報に基づいた言語モデルの微調整に不可欠である。 我々は,Open Graph Benchmarkデータセット上での標準GNNパイプラインよりもGIANTの方が優れた性能を示す。
  論文  参考訳（メタデータ） (2021-10-29T19:55:12Z)
• Online Graph Dictionary Learning [10.394615068526505]
  本論文では,Gromov Wassersteinの発散をデータフィッティング用語として用いるオンライングラフ辞書学習手法を提案する。 私たちの研究では、グラフはノードの対関係を通じてエンコードされ、グラフ原子の凸結合としてモデル化されます。 私たちのアプローチはラベル付きグラフに自然に拡張され、埋め込み空間におけるGromov Wassersteinの高速近似として使用できる新しい上界によって完了されます。
  論文  参考訳（メタデータ） (2021-02-12T14:39:28Z)
• COLOGNE: Coordinated Local Graph Neighborhood Sampling [1.6498361958317633]
  グラフノードのような個別の未順序オブジェクトを実数値ベクトルで置き換えることは、グラフデータから学ぶための多くのアプローチの中心である。 ノードベクトル表現の座標がグラフノードであるような離散ノード埋め込みを学習する問題に対処する。 これにより、ノードにもともと存在するすべての属性が保存されているため、グラフの解釈可能な機械学習アルゴリズムを設計する扉が開く。
  論文  参考訳（メタデータ） (2021-02-09T11:39:06Z)
• Learning Sparse Graph Laplacian with K Eigenvector Prior via Iterative GLASSO and Projection [58.5350491065936]
  グラフ Laplacian 行列 $L$ 上の構造的仮定を考える。 最初の$K$ eigenvectors of $L$は、例えばドメイン固有の基準に基づいて事前選択される。 本稿では,H_u+$$$$barC$で最も適切なグラフラプラシアン行列$L*を計算するために,効率的なハイブリッドグラフラッソ/投影アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-10-25T18:12:50Z)
• Dirichlet Graph Variational Autoencoder [65.94744123832338]
  本稿では,グラフクラスタメンバシップを潜在因子とするDGVAE(Dirichlet Graph Variational Autoencoder)を提案する。 バランスグラフカットにおける低パス特性により、入力グラフをクラスタメンバシップにエンコードする、Heattsと呼ばれるGNNの新しい変種を提案する。
  論文  参考訳（メタデータ） (2020-10-09T07:35:26Z)
• Pseudoinverse Graph Convolutional Networks: Fast Filters Tailored for Large Eigengaps of Dense Graphs and Hypergraphs [0.0]
  Graph Convolutional Networks (GCNs) は、グラフベースのデータセットで半教師付き分類を行うツールとして成功している。 本稿では,三部フィルタ空間が高密度グラフを対象とする新しいGCN変種を提案する。
  論文  参考訳（メタデータ） (2020-08-03T08:48:41Z)
• Wasserstein Embedding for Graph Learning [33.90471037116372]
  Wasserstein Embedding for Graph Learning (WEGL)は、グラフ全体をベクトル空間に埋め込むフレームワークである。 グラフ間の類似性をノード埋め込み分布間の類似性の関数として定義する上で,新たな知見を活用する。 各種ベンチマークグラフ固有性予測タスクにおける新しいグラフ埋め込み手法の評価を行った。
  論文  参考訳（メタデータ） (2020-06-16T18:23:00Z)

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

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