論文の概要: Stars: Tera-Scale Graph Building for Clustering and Graph Learning
- arxiv url: http://arxiv.org/abs/2212.02635v1
- Date: Mon, 5 Dec 2022 22:43:26 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-07 17:52:20.903402
- Title: Stars: Tera-Scale Graph Building for Clustering and Graph Learning
- Title（参考訳）: Stars: クラスタリングとグラフ学習のためのテラスケールグラフ構築
- Authors: CJ Carey, Jonathan Halcrow, Rajesh Jayaram, Vahab Mirrokni, Warren
Schudy, Peilin Zhong
- Abstract要約: $textitStars$は、2ホップスパンナーを介して非常にスパースなグラフを構築するための非常にスケーラブルな方法です。
私たちはスターズがほぼ直線時間でグラフを構築することを実証した。
- 参考スコア（独自算出の注目度）: 14.265732346610534
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A fundamental procedure in the analysis of massive datasets is the
construction of similarity graphs. Such graphs play a key role for many
downstream tasks, including clustering, classification, graph learning, and
nearest neighbor search. For these tasks, it is critical to build graphs which
are sparse yet still representative of the underlying data. The benefits of
sparsity are twofold: firstly, constructing dense graphs is infeasible in
practice for large datasets, and secondly, the runtime of downstream tasks is
directly influenced by the sparsity of the similarity graph. In this work, we
present $\textit{Stars}$: a highly scalable method for building extremely
sparse graphs via two-hop spanners, which are graphs where similar points are
connected by a path of length at most two. Stars can construct two-hop spanners
with significantly fewer similarity comparisons, which are a major bottleneck
for learning based models where comparisons are expensive to evaluate.
Theoretically, we demonstrate that Stars builds a graph in nearly-linear time,
where approximate nearest neighbors are contained within two-hop neighborhoods.
In practice, we have deployed Stars for multiple data sets allowing for graph
building at the $\textit{Tera-Scale}$, i.e., for graphs with tens of trillions
of edges. We evaluate the performance of Stars for clustering and graph
learning, and demonstrate 10~1000-fold improvements in pairwise similarity
comparisons compared to different baselines, and 2~10-fold improvement in
running time without quality loss.
- Abstract（参考訳）: 大規模データセットの分析における基本的な手順は、類似性グラフの構築である。
このようなグラフは、クラスタリング、分類、グラフ学習、近接探索など、多くの下流タスクにおいて重要な役割を果たす。
これらのタスクでは、基礎となるデータを表しながらスパースであるグラフを構築することが重要です。
第一に、高密度グラフの構築は、大規模なデータセットでは実現不可能であり、第二に、ダウンストリームタスクのランタイムは、類似グラフのスパース性によって直接影響を受ける。
この論文では、$\textit{stars}$という、2つのホップスパンナーを通して非常にスパースなグラフを構築するための非常にスケーラブルな方法を紹介します。
恒星は相似性比較が著しく少ない2ホップスパンナーを構成できるが、これは比較評価が高価である学習ベースのモデルにとって大きなボトルネックである。
理論的には、恒星がほぼ線形な時間にグラフを構築し、近接する近傍が2つのホップ近傍に含まれることを実証する。
実際、私たちは複数のデータセットに対してStarsをデプロイし、例えば数十兆のエッジを持つグラフに対して$\textit{Tera-Scale}$でグラフ構築を可能にしました。
クラスタリングとグラフ学習におけるStarsの性能を評価し,異なるベースラインとペアの類似性比較で10～1000倍,品質損失のないランニング時間で2～10倍に改善したことを示す。
関連論文リスト
- Robust Graph Structure Learning under Heterophily [12.557639223778722]
本稿では、下流タスクのための異種データから高品質なグラフを実現するための、新しい頑健なグラフ構造学習法を提案する。
まず,そのノードの特徴に構造情報をエンコードすることで,各ノードが近隣ノードとより区別されるようにハイパスフィルタを適用する。
そして、異なるレベルのノイズを特徴付ける適応ノルムを持つ頑健なグラフを学習する。
論文 参考訳（メタデータ） (2024-03-06T12:29:13Z) - Exploiting Edge Features in Graphs with Fused Network Gromov-Wasserstein
Distance [18.522233517515975]
ノードとエッジが特徴を持つグラフを比較するために,Gromov-Wasserstein距離の拡張を導入する。
入力空間または出力空間でグラフが発生する学習タスクにおいて、新しい距離の有効性を実証的に示す。
論文 参考訳（メタデータ） (2023-09-28T17:05:03Z) - CGMN: A Contrastive Graph Matching Network for Self-Supervised Graph
Similarity Learning [65.1042892570989]
自己教師付きグラフ類似性学習のためのコントラストグラフマッチングネットワーク(CGMN)を提案する。
我々は,効率的なノード表現学習のために,クロスビューインタラクションとクロスグラフインタラクションという2つの戦略を用いる。
我々はノード表現をグラフ類似性計算のためのプール演算によりグラフレベル表現に変換する。
論文 参考訳（メタデータ） (2022-05-30T13:20:26Z) - Edge but not Least: Cross-View Graph Pooling [76.71497833616024]
本稿では,重要なグラフ構造情報を活用するために,クロスビューグラフプーリング(Co-Pooling)手法を提案する。
クロスビュー相互作用、エッジビュープーリング、ノードビュープーリングにより、相互にシームレスに強化され、より情報的なグラフレベルの表現が学習される。
論文 参考訳（メタデータ） (2021-09-24T08:01:23Z) - Joint Graph Learning and Matching for Semantic Feature Correspondence [69.71998282148762]
本稿では,グラフマッチングを向上するための信頼度の高いグラフ構造を探索するために,GLAMという共用電子グラフ学習とマッチングネットワークを提案する。
提案手法は,3つの人気ビジュアルマッチングベンチマーク (Pascal VOC, Willow Object, SPair-71k) で評価される。
すべてのベンチマークにおいて、従来の最先端のグラフマッチング手法よりも大きなマージンを達成している。
論文 参考訳（メタデータ） (2021-09-01T08:24:02Z) - Effective and Efficient Graph Learning for Multi-view Clustering [173.8313827799077]
マルチビュークラスタリングのための効率的かつ効率的なグラフ学習モデルを提案する。
本手法はテンソルシャッテンp-ノルムの最小化により異なるビューのグラフ間のビュー類似性を利用する。
提案アルゴリズムは時間経済であり,安定した結果を得るとともに,データサイズによく対応している。
論文 参考訳（メタデータ） (2021-08-15T13:14:28Z) - Grale: Designing Networks for Graph Learning [68.23038997141381]
我々は,数十億のノードを持つグラフのグラフ設計問題に対処するために,スケーラブルなGraleを提案する。
グレールは、(潜在的に弱い)類似性の異なる測度を融合して、そのノード間の高いタスク固有のホモフィリーを示すグラフを作成する。
Googleでは、数千億のノードを持つデータセットや、数十兆の潜在的なエッジを含む、20以上の異なる産業環境にGraleをデプロイしています。
論文 参考訳（メタデータ） (2020-07-23T13:25:36Z) - Graph topology inference benchmarks for machine learning [16.857405938139525]
本稿では,グラフ推論手法の相対的メリットと限界を明らかにするために,いくつかのベンチマークを導入する。
我々はまた、文学において最も顕著な技法のいくつかを対比している。
論文 参考訳（メタデータ） (2020-07-16T09:40:32Z) - Multilevel Graph Matching Networks for Deep Graph Similarity Learning [79.3213351477689]
グラフ構造オブジェクト間のグラフ類似性を計算するためのマルチレベルグラフマッチングネットワーク(MGMN)フレームワークを提案する。
標準ベンチマークデータセットの欠如を補うため、グラフグラフ分類とグラフグラフ回帰タスクの両方のためのデータセットセットを作成し、収集した。
総合的な実験により、MGMNはグラフグラフ分類とグラフグラフ回帰タスクの両方において、最先端のベースラインモデルより一貫して優れていることが示された。
論文 参考訳（メタデータ） (2020-07-08T19:48:19Z) - Wasserstein Embedding for Graph Learning [33.90471037116372]
Wasserstein Embedding for Graph Learning (WEGL)は、グラフ全体をベクトル空間に埋め込むフレームワークである。
グラフ間の類似性をノード埋め込み分布間の類似性の関数として定義する上で,新たな知見を活用する。
各種ベンチマークグラフ固有性予測タスクにおける新しいグラフ埋め込み手法の評価を行った。
論文 参考訳（メタデータ） (2020-06-16T18:23:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。