論文の概要: PASCO (PArallel Structured COarsening): an overlay to speed up graph clustering algorithms
- arxiv url: http://arxiv.org/abs/2412.13592v1
- Date: Wed, 18 Dec 2024 08:15:55 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-19 16:49:13.601560
- Title: PASCO (PArallel Structured COarsening): an overlay to speed up graph clustering algorithms
- Title（参考訳）: PASCO(Parallel Structured COarsening):グラフクラスタリングアルゴリズムのオーバーレイ
- Authors: Etienne Lasalle, Rémi Vaudaine, Titouan Vayer, Pierre Borgnat, Rémi Gribonval, Paulo Gonçalves, Màrton Karsai,
- Abstract要約: グラフのクラスタリングノードは、グラフ解析の土台である。
いくつかの一般的な方法は、非常に大きなグラフには適さない。
この研究は、クラスタリングアルゴリズムを高速化するオーバーレイであるPASCOを導入している。
- 参考スコア（独自算出の注目度）: 14.601622103700516
- License:
- Abstract: Clustering the nodes of a graph is a cornerstone of graph analysis and has been extensively studied. However, some popular methods are not suitable for very large graphs: e.g., spectral clustering requires the computation of the spectral decomposition of the Laplacian matrix, which is not applicable for large graphs with a large number of communities. This work introduces PASCO, an overlay that accelerates clustering algorithms. Our method consists of three steps: 1-We compute several independent small graphs representing the input graph by applying an efficient and structure-preserving coarsening algorithm. 2-A clustering algorithm is run in parallel onto each small graph and provides several partitions of the initial graph. 3-These partitions are aligned and combined with an optimal transport method to output the final partition. The PASCO framework is based on two key contributions: a novel global algorithm structure designed to enable parallelization and a fast, empirically validated graph coarsening algorithm that preserves structural properties. We demonstrate the strong performance of 1 PASCO in terms of computational efficiency, structural preservation, and output partition quality, evaluated on both synthetic and real-world graph datasets.
- Abstract（参考訳）: グラフのノードをクラスタリングすることは、グラフ解析の基盤であり、広く研究されている。
スペクトルクラスタリングは、多数のコミュニティを持つ大きなグラフには適用できないラプラシア行列のスペクトル分解の計算を必要とする。
この研究は、クラスタリングアルゴリズムを高速化するオーバーレイであるPASCOを導入している。
1-We compute several independent small graphs representation the input graph by applied an efficient and structure-serving coarsening algorithm。
2-A クラスタリングアルゴリズムは各小さなグラフに対して並列に実行され、初期グラフのいくつかのパーティションを提供する。
これらのパーティションはアライメントされ、最終パーティションを出力する最適なトランスポートメソッドと結合されます。
PASCOフレームワークは、並列化を可能にするために設計された新しいグローバルアルゴリズム構造と、構造特性を保存する高速で実証済みのグラフ粗大化アルゴリズムである。
本研究では, 計算効率, 構造保存, 出力分割品質の観点から, 1 PASCO の強い性能を示し, 合成および実世界のグラフデータセットを用いて評価した。
関連論文リスト
- Differentiable Proximal Graph Matching [40.41380102260085]
微分可能近位グラフマッチング(DPGM)と呼ばれる近位演算子に基づくグラフマッチングアルゴリズムを提案する。
アルゴリズム全体をグラフ親和性行列からノード対応の予測への微分可能な写像とみなすことができる。
数値実験により、PGMは様々なデータセット上で既存のグラフマッチングアルゴリズムより優れていることが示された。
論文 参考訳（メタデータ） (2024-05-26T08:17:13Z) - A Differentially Private Clustering Algorithm for Well-Clustered Graphs [6.523602840064548]
このようなグラフに特化された効率的な(epsilon,$delta$)-DPアルゴリズムを提供する。
我々のアルゴリズムは、ほぼバランスの取れたクラスタに対して$k$のグラフを扱う。
論文 参考訳（メタデータ） (2024-03-21T11:57:16Z) - Latent Random Steps as Relaxations of Max-Cut, Min-Cut, and More [30.919536115917726]
クラスタリングと単純化を統一する非負行列分解に基づく確率モデルを提案する。
ハードクラスタリングをソフトクラスタリングに緩和することにより、ハードクラスタリングの潜在的な問題をトラクタブルクラスタに緩和する。
論文 参考訳（メタデータ） (2023-08-12T02:47:57Z) - One-step Bipartite Graph Cut: A Normalized Formulation and Its
Application to Scalable Subspace Clustering [56.81492360414741]
両部グラフの1ステップ正規化カットを、特に線形時間複雑性で実施する方法を示す。
本稿では、まず、正規化制約付き一段階二分グラフカット基準を特徴付けるとともに、そのトレース問題に対する等価性を理論的に証明する。
このカット基準を、適応アンカー学習、二部グラフ学習、一段階正規化二部グラフ分割を同時にモデル化するスケーラブルなサブスペースクラスタリングアプローチに拡張する。
論文 参考訳（メタデータ） (2023-05-12T11:27:20Z) - Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
点雲を符号化するグラフ上での効率的な場積分のためのアルゴリズムを2種類提案する。
第1のクラスであるSeparatorFactorization(SF)は、ポイントメッシュグラフの有界属を利用するが、第2のクラスであるRFDiffusion(RFD)は、ポイントクラウドの一般的なepsilon-nearest-neighborグラフ表現を使用する。
論文 参考訳（メタデータ） (2023-02-02T08:33:36Z) - Hierarchical Clustering: $O(1)$-Approximation for Well-Clustered Graphs [3.2901541059183432]
階層クラスタリングのための2時間近似アルゴリズムを提案する。
本研究の意義は,合成データセットと実世界のデータセットの両方における経験的分析によって実証された。
論文 参考訳（メタデータ） (2021-12-16T17:52:04Z) - 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) - Sparse Partial Least Squares for Coarse Noisy Graph Alignment [10.172041234280865]
グラフ信号処理(GSP)は、様々な領域で発生する信号を分析する強力なフレームワークを提供する。
本稿では,観測されたグラフ構造を組み込んで,その基盤となるブロックコミュニティ構造を反映させる,新しい正則化部分最小二乗法を提案する。
論文 参考訳（メタデータ） (2021-04-06T21:52:15Z) - MC2G: An Efficient Algorithm for Matrix Completion with Social and Item
Similarity Graphs [85.89744949820376]
MC2Gは、ソーシャルグラフとアイテム類似性グラフの存在下で行列補完を行うアルゴリズムである。
スペクトルクラスタリングと局所的な精細化のステップに基づいている。
我々は、MC2Gが他の最先端行列補完アルゴリズムより優れている合成データセットと実データセットの両方に関する広範な実験を通して示す。
論文 参考訳（メタデータ） (2020-06-08T06:11:37Z) - Wasserstein-based Graph Alignment [56.84964475441094]
我々は,より小さいグラフのノードと大きなグラフのノードをマッチングすることを目的とした,1対多のグラフアライメント問題に対する新しい定式化を行った。
提案手法は,各タスクに対する最先端のアルゴリズムに対して,大幅な改善をもたらすことを示す。
論文 参考訳（メタデータ） (2020-03-12T22:31:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。