論文の概要: A Note on Graph-Based Nearest Neighbor Search

• arxiv url: http://arxiv.org/abs/2012.11083v1
• Date: Mon, 21 Dec 2020 02:18:05 GMT
• ステータス: 処理完了
• システム内更新日: 2021-04-27 06:27:55.605196
• Title: A Note on Graph-Based Nearest Neighbor Search
• Title（参考訳）: グラフに基づく最近傍探索に関する一考察
• Authors: Hongya Wang, Zhizheng Wang, Wei Wang, Yingyuan Xiao, Zeng Zhao, Kaixiang Yang
• Abstract要約: 高いクラスタリング係数は、グラフの最大強連結成分 (scc) に、q の k に近い近傍の大半を配置することを示している。 グラフに基づく探索アルゴリズムは,任意の地点を訪れると最大 SCC を横切ることが保証されている。
• 参考スコア（独自算出の注目度）: 4.38837720322254
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Nearest neighbor search has found numerous applications in machine learning, data mining and massive data processing systems. The past few years have witnessed the popularity of the graph-based nearest neighbor search paradigm because of its superiority over the space-partitioning algorithms. While a lot of empirical studies demonstrate the efficiency of graph-based algorithms, not much attention has been paid to a more fundamental question: why graph-based algorithms work so well in practice? And which data property affects the efficiency and how? In this paper, we try to answer these questions. Our insight is that "the probability that the neighbors of a point o tends to be neighbors in the KNN graph" is a crucial data property for query efficiency. For a given dataset, such a property can be qualitatively measured by clustering coefficient of the KNN graph. To show how clustering coefficient affects the performance, we identify that, instead of the global connectivity, the local connectivity around some given query q has more direct impact on recall. Specifically, we observed that high clustering coefficient makes most of the k nearest neighbors of q sit in a maximum strongly connected component (SCC) in the graph. From the algorithmic point of view, we show that the search procedure is actually composed of two phases - the one outside the maximum SCC and the other one in it, which is different from the widely accepted single or multiple paths search models. We proved that the commonly used graph-based search algorithm is guaranteed to traverse the maximum SCC once visiting any point in it. Our analysis reveals that high clustering coefficient leads to large size of the maximum SCC, and thus provides good answer quality with the help of the two-phase search procedure. Extensive empirical results over a comprehensive collection of datasets validate our findings.
• Abstract（参考訳）: 近隣の検索は、機械学習、データマイニング、大規模データ処理システムに多くの応用を見出している。 過去数年間、空間分割アルゴリズムよりも優れているため、グラフベースの近接探索パラダイムが人気を博してきた。 グラフベースのアルゴリズムの効率を実証する実証的研究は多いが、なぜグラフベースのアルゴリズムが実際にこれほどうまく機能するのかという根本的な疑問にはあまり注目されていない。 そして、どのデータプロパティが効率と方法に影響するのか? 本稿では,これらの疑問に答えようと試みる。 我々の洞察では、"ある点 o の隣人が KNN グラフの隣人となる確率" は、クエリ効率にとって重要なデータ特性である。 与えられたデータセットに対して、そのような性質はKNNグラフのクラスタリング係数によって定性的に測定することができる。 クラスタリング係数がパフォーマンスにどのように影響するかを示すために、グローバル接続の代わりに、あるクエリq周辺のローカル接続がリコールに直接影響を与えることを識別する。 具体的には、高いクラスタリング係数がq の k 近傍の大部分をグラフ内の最大連結成分 (SCC) に配置することを示した。 アルゴリズム的な観点からは、探索手続きは実際には最大scc外の2つのフェーズと、それに含まれるもう1つのフェーズで構成されており、これは広く受け入れられている単一の経路や複数の経路の探索モデルとは異なる。 グラフに基づく探索アルゴリズムは,任意の地点を訪れると最大 SCC を横切ることが保証されている。 解析の結果,クラスタリング係数が高いと最大sccのサイズが大きくなり,二相探索の助けを借りて回答品質が良好であることが判明した。 包括的なデータセットコレクションに対する広範な実験結果が、我々の発見を裏付ける。

関連論文リスト

• FINGER: Fast Inference for Graph-based Approximate Nearest Neighbor Search [20.928821121591493]
  効率的なグラフ探索を実現するための高速推論手法であるFINGERを提案する。 FINGERは、近傍の残差ベクトルと低ランク基底と分布マッチングとの角度を推定することで距離関数を近似する。 実証的に、FINGERによるHNSWと呼ばれるグラフベースの手法の高速化は、異なるベンチマークデータセット間で既存のグラフベースの手法を20%から60%上回っている。
  論文  参考訳（メタデータ） (2022-06-22T22:30:46Z)
• 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)
• Hierarchical Clustering: $O(1)$-Approximation for Well-Clustered Graphs [3.2901541059183432]
  階層クラスタリングのための2時間近似アルゴリズムを提案する。 本研究の意義は,合成データセットと実世界のデータセットの両方における経験的分析によって実証された。
  論文  参考訳（メタデータ） (2021-12-16T17:52:04Z)
• Graph-augmented Learning to Rank for Querying Large-scale Knowledge Graph [34.774049199809426]
  情報検索に基づく知識グラフ質問応答(KGQA)は,大規模知識グラフから回答を取得して回答することを目的としている。 まず,検索したKSGを,新しいサブグラフ分割アルゴリズムを用いて,より小さなKSGに分割する。 次に、ランク付けモデルから上位のKSGを選択するためのグラフ拡張学習を提案する。
  論文  参考訳（メタデータ） (2021-11-20T08:27:37Z)
• Effective and Efficient Graph Learning for Multi-view Clustering [173.8313827799077]
  マルチビュークラスタリングのための効率的かつ効率的なグラフ学習モデルを提案する。 本手法はテンソルシャッテンp-ノルムの最小化により異なるビューのグラフ間のビュー類似性を利用する。 提案アルゴリズムは時間経済であり,安定した結果を得るとともに,データサイズによく対応している。
  論文  参考訳（メタデータ） (2021-08-15T13:14:28Z)
• Spatial-Spectral Clustering with Anchor Graph for Hyperspectral Image [88.60285937702304]
  本稿では、HSIデータクラスタリングのための空間スペクトルクラスタリングとアンカーグラフ(SSCAG)という新しい非監視アプローチを提案する。 提案されたSSCAGは最先端のアプローチと競合する。
  論文  参考訳（メタデータ） (2021-04-24T08:09:27Z)
• Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
  クラスタリングのA*探索に基づく新しいアプローチを紹介します。 A*と新しいエンフォレリスデータ構造を組み合わせることで、禁止的に大きな検索空間を克服します。 実験により,本手法は粒子物理利用事例や他のクラスタリングベンチマークにおいて,ベースラインよりもかなり高品質な結果が得られることを示した。
  論文  参考訳（メタデータ） (2021-04-14T18:15:27Z)
• Towards Efficient Graph Convolutional Networks for Point Cloud Handling [181.59146413326056]
  ポイントクラウド上で学習するためのグラフ畳み込みネットワーク(GCN)の計算効率の向上を目指します。 一連の実験により、最適化されたネットワークは計算複雑性を減らし、メモリ消費を減らし、推論速度を加速した。
  論文  参考訳（メタデータ） (2021-04-12T17:59:16Z)
• Weighted Graph Nodes Clustering via Gumbel Softmax [0.0]
  重み付きグラフデータセットのクラスタリングのためのグラフクラスタリングアルゴリズムの研究成果について述べる。 アルゴリズムをGumbel Softmax(WGCGS)を介して重み付きグラフノードクラスタリングと呼びます。
  論文  参考訳（メタデータ） (2021-02-22T05:05:35Z)
• Deep Reinforcement Learning of Graph Matching [63.469961545293756]
  ノードとペアの制約下でのグラフマッチング(GM)は、最適化からコンピュータビジョンまでの領域におけるビルディングブロックである。 GMのための強化学習ソルバを提案する。 rgmはペアワイズグラフ間のノード対応を求める。 本手法は,フロントエンドの特徴抽出と親和性関数学習に焦点をあてるという意味において,従来のディープグラフマッチングモデルと異なる。
  論文  参考訳（メタデータ） (2020-12-16T13:48:48Z)

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

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