論文の概要: Scaling Graph Clustering with Distributed Sketches
- arxiv url: http://arxiv.org/abs/2007.12669v1
- Date: Fri, 24 Jul 2020 17:38:04 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-07 06:15:04.420240
- Title: Scaling Graph Clustering with Distributed Sketches
- Title(参考訳): 分散スケッチによるグラフクラスタリングのスケーリング
- Authors: Benjamin W. Priest, Alec Dunton, Geoffrey Sanders
- Abstract要約: スペクトルクラスタリングにインスパイアされた手法として,ランダムな次元還元プロジェクションから得られた行列スケッチを用いる。
提案手法は,完全に動的なブロックモデルストリームが与えられた場合,性能の高いクラスタリング結果が得られる埋め込みを生成する。
また、ブロックモデルパラメータがその後の埋め込みの必要次元に与える影響についても検討し、ランダムなプロジェクションが分散メモリにおけるグラフクラスタリングの性能を大幅に改善できることを示す。
- 参考スコア(独自算出の注目度): 1.1011268090482575
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The unsupervised learning of community structure, in particular the
partitioning vertices into clusters or communities, is a canonical and
well-studied problem in exploratory graph analysis. However, like most graph
analyses the introduction of immense scale presents challenges to traditional
methods. Spectral clustering in distributed memory, for example, requires
hundreds of expensive bulk-synchronous communication rounds to compute an
embedding of vertices to a few eigenvectors of a graph associated matrix.
Furthermore, the whole computation may need to be repeated if the underlying
graph changes some low percentage of edge updates. We present a method inspired
by spectral clustering where we instead use matrix sketches derived from random
dimension-reducing projections. We show that our method produces embeddings
that yield performant clustering results given a fully-dynamic stochastic block
model stream using both the fast Johnson-Lindenstrauss and CountSketch
transforms. We also discuss the effects of stochastic block model parameters
upon the required dimensionality of the subsequent embeddings, and show how
random projections could significantly improve the performance of graph
clustering in distributed memory.
- Abstract(参考訳): コミュニティ構造の教師なし学習、特にクラスタやコミュニティへの分割頂点は、探索グラフ解析における標準的かつよく研究された問題である。
しかし、ほとんどのグラフ分析と同様に、膨大なスケールの導入は従来の方法に困難をもたらす。
例えば、分散メモリにおけるスペクトルクラスタリングは、グラフ関連行列のいくつかの固有ベクトルへの頂点の埋め込みを計算するために数百の高価なバルク同期通信ラウンドを必要とする。
さらに、基礎となるグラフがエッジ更新の低い割合を変更する場合、計算全体を繰り返す必要がある。
スペクトルクラスタリングにインスパイアされた手法として,ランダムな次元還元プロジェクションから得られた行列スケッチを用いる。
高速なジョンソン-リンデンシュトラウス変換とカウントスケッチ変換の両方を用いて, 完全に動的確率的ブロックモデルストリームを与えられた性能的クラスタリング結果を得る埋め込みを生成する。
また,確率的ブロックモデルパラメータがその後の埋め込みの必要次元に与える影響についても論じ,ランダムなプロジェクションが分散メモリにおけるグラフクラスタリングの性能を著しく改善することを示す。
関連論文リスト
- Interpretable Multi-View Clustering Based on Anchor Graph Tensor Factorization [64.00146569922028]
アンカーグラフの分解に基づくマルチビュークラスタリング法では,分解行列に対する適切なクラスタ解釈性が欠如している。
複数のビューからアンカーグラフを合成するアンカーグラフテンソルを分解するために、非負のテンソル因子分解を用いることにより、この制限に対処する。
論文 参考訳(メタデータ) (2024-04-01T03:23:55Z) - MeanCut: A Greedy-Optimized Graph Clustering via Path-based Similarity
and Degree Descent Criterion [0.6906005491572401]
スペクトルクラスタリングは、優れたパフォーマンス、簡単な実装、強力な適応性のために人気があり、魅力的です。
我々は,MeanCutを目的関数として提案し,非破壊グラフ分割の次数降下順で厳密に最適化する。
本アルゴリズムの有効性は,実世界のベンチマークによる検証と顔認識の適用によって実証される。
論文 参考訳(メタデータ) (2023-12-07T06:19:39Z) - Latent Random Steps as Relaxations of Max-Cut, Min-Cut, and More [30.919536115917726]
クラスタリングと単純化を統一する非負行列分解に基づく確率モデルを提案する。
ハードクラスタリングをソフトクラスタリングに緩和することにより、ハードクラスタリングの潜在的な問題をトラクタブルクラスタに緩和する。
論文 参考訳(メタデータ) (2023-08-12T02:47:57Z) - GrannGAN: Graph annotation generative adversarial networks [72.66289932625742]
本稿では,高次元分布をモデル化し,グラフスケルトンと整合した複雑な関係特徴構造を持つデータの新しい例を生成することの問題点を考察する。
提案するモデルは,タスクを2つのフェーズに分割することで,各データポイントのグラフ構造に制約されたデータ特徴を生成する問題に対処する。
第一に、与えられたグラフのノードに関連する機能の分布をモデル化し、第二に、ノードのフィーチャに条件付きでエッジ機能を補完する。
論文 参考訳(メタデータ) (2022-12-01T11:49:07Z) - Nonbacktracking spectral clustering of nonuniform hypergraphs [2.408714894793063]
非一様ハイパーグラフに対するスペクトルクラスタリングをハイパーグラフ非追跡演算子を用いて検討する。
本稿では,線形化された信念伝達を用いたハイパーグラフブロックモデルにおける推論の交互化アルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-04-27T01:14:06Z) - Effective and Efficient Graph Learning for Multi-view Clustering [173.8313827799077]
マルチビュークラスタリングのための効率的かつ効率的なグラフ学習モデルを提案する。
本手法はテンソルシャッテンp-ノルムの最小化により異なるビューのグラフ間のビュー類似性を利用する。
提案アルゴリズムは時間経済であり,安定した結果を得るとともに,データサイズによく対応している。
論文 参考訳(メタデータ) (2021-08-15T13:14:28Z) - T-LoHo: A Bayesian Regularization Model for Structured Sparsity and
Smoothness on Graphs [0.0]
グラフ構造化データでは、構造化されたスパーシリティと滑らかさが団結する傾向にある。
グラフィカルな関係を持つ高次元パラメータに先立って提案する。
構造された空間と滑らかさを同時に検出するために使用します。
論文 参考訳(メタデータ) (2021-07-06T10:10:03Z) - Spectral-Spatial Global Graph Reasoning for Hyperspectral Image
Classification [50.899576891296235]
畳み込みニューラルネットワークは、ハイパースペクトル画像分類に広く応用されている。
近年の手法は空間トポロジのグラフ畳み込みによってこの問題に対処しようとしている。
論文 参考訳(メタデータ) (2021-06-26T06:24:51Z) - Regularization of Mixture Models for Robust Principal Graph Learning [0.0]
D$次元データポイントの分布から主グラフを学習するために,Mixture Modelsの正規化バージョンを提案する。
モデルのパラメータは期待最大化手順によって反復的に推定される。
論文 参考訳(メタデータ) (2021-06-16T18:00:02Z) - Multilayer Clustered Graph Learning [66.94201299553336]
我々は、観測された層を代表グラフに適切に集約するために、データ忠実度用語として対照的な損失を用いる。
実験により,本手法がクラスタクラスタw.r.tに繋がることが示された。
クラスタリング問題を解くためのクラスタリングアルゴリズムを学習する。
論文 参考訳(メタデータ) (2020-10-29T09:58:02Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳(メタデータ) (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。