論文の概要: Down with the Hierarchy: The 'H' in HNSW Stands for "Hubs"

• arxiv url: http://arxiv.org/abs/2412.01940v2
• Date: Sun, 02 Feb 2025 19:25:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-04 16:05:15.876894
• Title: Down with the Hierarchy: The 'H' in HNSW Stands for "Hubs"
• Title（参考訳）: HNSWの'H'は'Hubs'の略
• Authors: Blaise Munyampirwa, Vihan Lakshman, Benjamin Coleman,
• Abstract要約: 平坦なナビゲート可能な小世界グラフは、高次元データセットにおけるHNSWの利点をすべて保持していることを示す。 我々はさらに一歩進んで、HNSWの階層構造が高次元において何の利益も与えない理由について研究する。
• 参考スコア（独自算出の注目度）: 9.912508121466995
• License:
• Abstract: Driven by recent breakthrough advances in neural representation learning, approximate near-neighbor (ANN) search over vector embeddings has emerged as a critical computational workload. With the introduction of the seminal Hierarchical Navigable Small World (HNSW) algorithm, graph-based indexes have established themselves as the overwhelmingly dominant paradigm for efficient and scalable ANN search. As the name suggests, HNSW searches a layered hierarchical graph to quickly identify neighborhoods of similar points to a given query vector. But is this hierarchy even necessary? A rigorous experimental analysis to answer this question would provide valuable insights into the nature of algorithm design for ANN search and motivate directions for future work in this increasingly crucial domain. To that end, we conduct an extensive benchmarking study covering more large-scale datasets than prior investigations of this question. We ultimately find that a flat navigable small world graph graph retains all of the benefits of HNSW on high-dimensional datasets, with latency and recall performance essentially \emph{identical} to the original algorithm but with less memory overhead. Furthermore, we go a step further and study \emph{why} the hierarchy of HNSW provides no benefit in high dimensions, hypothesizing that navigable small world graphs contain a well-connected, frequently traversed ``highway" of hub nodes that maintain the same purported function as the hierarchical layers. We present compelling empirical evidence that the \emph{Hub Highway Hypothesis} holds for real datasets and investigate the mechanisms by which the highway forms. The implications of this hypothesis may also provide future research directions in developing enhancements to graph-based ANN search.
• Abstract（参考訳）: ニューラル表現学習の最近の進歩によって、ベクトル埋め込みに対する近似近傍探索(ANN)が重要な計算ワークロードとして登場した。 半階層的ナビゲート可能な小型世界(HNSW)アルゴリズムの導入により、グラフベースのインデックスは、効率的でスケーラブルなANN探索において圧倒的に支配的なパラダイムとして確立されてきた。 名前が示すように、HNSWは階層化された階層グラフを検索し、与えられたクエリベクトルに類似した点の近傍を素早く特定する。 しかし、この階層は必要か? この疑問に答えるための厳密な実験的分析は、ANN検索のためのアルゴリズム設計の性質に関する貴重な洞察を与え、このますます重要な領域における将来の研究の動機付けとなるだろう。 そこで本研究では,従来よりも大規模なデータセットを網羅した広範なベンチマーク研究を行っている。 フラットなナビゲート可能な小世界グラフは、高次元データセットにおけるHNSWの利点を全て保持しており、遅延とリコール性能は基本的に元のアルゴリズムでは「emph{identical}」であるが、メモリオーバーヘッドは少ない。 さらにさらに、HNSW の階層構造は高次元に利益を与えず、ナビゲート可能な小さな世界グラフは階層層と同じ関数を持つハブノードの「ハイウェイ」をよく連結していると仮定する。 本研究は, 実データに対して<emph{Hub Highway hypothesis} が成立し, ハイウェイ形成のメカニズムを解明する実証的証拠を提示する。 この仮説がもたらす意味は、グラフベースのANN探索の強化を開発する上での今後の研究の方向性にも繋がる可能性がある。

関連論文リスト

• The Impacts of Data, Ordering, and Intrinsic Dimensionality on Recall in Hierarchical Navigable Small Worlds [0.09208007322096533]
  調査は、HNSWがデータセットのスペクトルにわたって有効であることに焦点を当てている。 我々は、KN(K Nearest Neighbours)探索と比較して、近似HNSW探索のリコールが、ベクトル空間の固有次元と結びついていることを発見した。 一般的なベンチマークデータセットをKNNの代わりにHNSWで実行することで、いくつかのモデルではランキングを最大3ポジションシフトすることができる。
  論文  参考訳（メタデータ） (2024-05-28T04:16:43Z)
• Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
  本稿では,属性付きグラフデータに対する新しいDeep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE)を提案する。 提案手法は,最先端のベースラインアルゴリズムを,一般的なデータセット間でのダウンストリームタスクの差を大きく越える。
  論文  参考訳（メタデータ） (2024-01-12T17:57:07Z)
• 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)
• ReVoLT: Relational Reasoning and Voronoi Local Graph Planning for Target-driven Navigation [1.0896567381206714]
  Embodied AIは、知的な実体と現実世界の相互作用を強調する必然的なトレンドである。 グラフニューラルネットワーク(GNN)によるレイアウト関係の活用に関する研究 このタスクを分離し、階層的なフレームワークであるReVoLTを提案する。
  論文  参考訳（メタデータ） (2023-01-06T05:19:56Z)
• A Comprehensive Study on Large-Scale Graph Training: Benchmarking and Rethinking [124.21408098724551]
  グラフニューラルネットワーク(GNN)の大規模グラフトレーニングは、非常に難しい問題である 本稿では,既存の問題に対処するため,EnGCNという新たなアンサンブルトレーニング手法を提案する。 提案手法は,大規模データセット上でのSOTA(State-of-the-art)の性能向上を実現している。
  論文  参考訳（メタデータ） (2022-10-14T03:43:05Z)
• Subgraph Matching via Query-Conditioned Subgraph Matching Neural Networks and Bi-Level Tree Search [33.9052190473029]
  サブグラフマッチングは、グラフデータベース検索、バイオメディカル分析、ソーシャルグループ検索などにおける中核的な操作である。 本稿では,クエリと対象グラフのマッチング情報を動的に計算する,新しいエンコーダ・デコーダニューラルネットワークアーキテクチャを提案する。 5つの大きな実世界のターゲットグラフの実験により、N-BLSはサブグラフマッチング性能を大幅に改善できることが示された。
  論文  参考訳（メタデータ） (2022-07-21T04:47:21Z)
• Sublinear Algorithms for Hierarchical Clustering [14.124026862687941]
  本稿では,3つの線形計算モデルに基づく大規模グラフの階層クラスタリングについて検討する。 すべてのモデルにおいて階層クラスタリングのためのサブ線形アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2022-06-15T16:25:27Z)
• 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)
• Arch-Graph: Acyclic Architecture Relation Predictor for Task-Transferable Neural Architecture Search [96.31315520244605]
  Arch-Graphはタスク固有の最適アーキテクチャを予測するトランスファー可能なNASメソッドである。 Arch-Graphの転送性と,多数のタスクにわたる高いサンプル効率を示す。 わずか50モデルの予算の下で、2つの検索スペースで平均して0.16%と0.29%のアーキテクチャを見つけることができる。
  論文  参考訳（メタデータ） (2022-04-12T16:46:06Z)
• Edge-featured Graph Neural Architecture Search [131.4361207769865]
  最適GNNアーキテクチャを見つけるために,エッジ機能付きグラフニューラルアーキテクチャ探索を提案する。 具体的には、高次表現を学習するためにリッチなエンティティとエッジの更新操作を設計する。 EGNASは、現在最先端の人間設計および検索されたGNNよりも高い性能で、より優れたGNNを検索できることを示す。
  論文  参考訳（メタデータ） (2021-09-03T07:53:18Z)
• Neural Architecture Search in Graph Neural Networks [1.2881413375147996]
  本稿では,グラフニューラルネットワーク(GNN)の最適化のための2つのNAS手法を比較する。 その結果、2つの探索空間上の7つのデータセットについて検討し、どちらの手法もランダムな探索に類似した精度が得られることを示した。
  論文  参考訳（メタデータ） (2020-07-31T21:04:24Z)

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

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