論文の概要: Stochastic Parallelizable Eigengap Dilation for Large Graph Clustering

• arxiv url: http://arxiv.org/abs/2207.14589v1
• Date: Fri, 29 Jul 2022 10:13:07 GMT
• ステータス: 処理完了
• システム内更新日: 2022-08-01 12:26:51.179560
• Title: Stochastic Parallelizable Eigengap Dilation for Large Graph Clustering
• Title（参考訳）: 大規模グラフクラスタリングのための確率的並列化固有ギャップ拡張
• Authors: Elise van der Pol, Ian Gemp, Yoram Bachrach, Richard Everett
• Abstract要約: 私たちは、ほとんどのエッジがクラスタ内に落ち、わずかにエッジがクラスタ間に落ちているノードのクラスタを特定することを目的としています。 スペクトルクラスタリングのコアステップは、対応するグラフラプラシア行列の固有分解を行う。 本稿では,SVDソルバを高速化し,スペクトルクラスタリングを行うために,スペクトルを並列化可能なアプローチを提案する。
• 参考スコア（独自算出の注目度）: 12.544602297450533
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Large graphs commonly appear in social networks, knowledge graphs, recommender systems, life sciences, and decision making problems. Summarizing large graphs by their high level properties is helpful in solving problems in these settings. In spectral clustering, we aim to identify clusters of nodes where most edges fall within clusters and only few edges fall between clusters. This task is important for many downstream applications and exploratory analysis. A core step of spectral clustering is performing an eigendecomposition of the corresponding graph Laplacian matrix (or equivalently, a singular value decomposition, SVD, of the incidence matrix). The convergence of iterative singular value decomposition approaches depends on the eigengaps of the spectrum of the given matrix, i.e., the difference between consecutive eigenvalues. For a graph Laplacian corresponding to a well-clustered graph, the eigenvalues will be non-negative but very small (much less than $1$) slowing convergence. This paper introduces a parallelizable approach to dilating the spectrum in order to accelerate SVD solvers and in turn, spectral clustering. This is accomplished via polynomial approximations to matrix operations that favorably transform the spectrum of a matrix without changing its eigenvectors. Experiments demonstrate that this approach significantly accelerates convergence, and we explain how this transformation can be parallelized and stochastically approximated to scale with available compute.
• Abstract（参考訳）: 大きなグラフは一般的にソーシャルネットワーク、知識グラフ、推薦システム、生命科学、意思決定問題に現れる。 グラフを高レベルな性質で要約することは、これらの設定における問題の解決に有用である。 スペクトルクラスタリングでは、ほとんどのエッジがクラスタ内にあり、クラスタ間のエッジがほとんどないノードのクラスタを識別することを目的としています。 このタスクは多くの下流アプリケーションや探索分析で重要です。 スペクトルクラスタリングのコアステップは、対応するグラフラプラシア行列の固有分解を行う(または、同値、入射行列の特異値分解、SVD)。 反復特異値分解アプローチの収束は、与えられた行列のスペクトルの固有ギャップ、すなわち連続した固有値の差に依存する。 十分にクラスタ化されたグラフに対応するグラフラプラシアンは、固有値は非負であるが非常に小さい(1ドル以下)収束が遅くなる。 本稿では,SVDソルバの高速化とスペクトルクラスタリングのために,スペクトルの並列化を行う手法を提案する。 これは行列のスペクトルを固有ベクトルを変更することなく好ましく変換する行列演算への多項式近似によって達成される。 実験により、このアプローチが収束を著しく加速することを示し、この変換がどのように並列化され、利用可能な計算でスケールするために確率的に近似できるかを説明する。

関連論文リスト

• Learning Sparse High-Dimensional Matrix-Valued Graphical Models From Dependent Data [12.94486861344922]
  スパース,高次元,定常行列-ガウス時系列の条件独立グラフ(CIG)を推定する問題を考察する。 我々は、Kronecker分解性パワースペクトル密度(PSD)による問題をスパースベースで定式化することを考える。 合成データと実データの両方を利用した数値例を用いて,本手法について述べる。
  論文  参考訳（メタデータ） (2024-04-29T19:32:50Z)
• Graph Generation via Spectral Diffusion [51.60814773299899]
  本稿では,1)グラフラプラシア行列のスペクトル分解と2)拡散過程に基づく新しいグラフ生成モデルGRASPを提案する。 具体的には、固有ベクトルと固有値のサンプリングにデノナイジングモデルを用い、グラフラプラシアン行列と隣接行列を再構成する。 我々の置換不変モデルは各ノードの固有ベクトルに連結することでノードの特徴を扱える。
  論文  参考訳（メタデータ） (2024-02-29T09:26:46Z)
• A Distributed Block Chebyshev-Davidson Algorithm for Parallel Spectral Clustering [7.632758664232665]
  スペクトルクラスタリングにおけるスペクトル解析のための大規模先行固有値問題の解法として,分散Block Chebyshev-Davidsonアルゴリズムを開発した。 チェビシェフ・ダビッドソンアルゴリズムの効率は、推定にコストがかかる固有値スペクトルの事前の知識に依存している。 分散バージョンと並列バージョンは、魅力的なスケーラビリティで開発されている。
  論文  参考訳（メタデータ） (2022-12-08T18:06:13Z)
• Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
  本稿では,低ランク構造制約下でのグラフ学習のためのフレキシブルなアルゴリズムフレームワークを提案する。 この問題は楕円分布のペナルティ化された最大推定値として表される。 楕円モデルによく適合する正定行列と定ランクの正半定行列のジオメトリを利用する。
  論文  参考訳（メタデータ） (2022-10-21T13:19:45Z)
• Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
  本稿では,初期監視情報を同時に拡張し,識別親和性行列を構築することのできる,新しい半教師付きサブスペースクラスタリング手法を提案する。 6つの一般的なベンチマークデータセットの総合的な実験結果から,本手法が最先端手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-05-21T01:47:17Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。 そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-30T19:17:35Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。 次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
  論文  参考訳（メタデータ） (2021-05-03T16:36:27Z)
• Average Sensitivity of Spectral Clustering [31.283432482502278]
  入力グラフにおけるエッジ摂動に対するスペクトルクラスタリングの安定性について検討する。 その結果,入力グラフにクラスタ構造が存在する場合,スペクトルクラスタリングはエッジ摂動に対して安定であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-07T09:14:44Z)
• Spectral Learning on Matrices and Tensors [74.88243719463053]
  テンソル分解は行列法で欠落する潜伏効果を拾うことができることを示す。 また,効率的なテンソル分解法を設計するための計算手法についても概説する。
  論文  参考訳（メタデータ） (2020-04-16T22:53:00Z)
• Approximate Graph Spectral Decomposition with the Variational Quantum Eigensolver [1.0152838128195465]
  スペクトルグラフ理論はラプラシア行列と隣接行列とその関連するグラフの固有ベクトルと固有値の関係を研究する。 ハイブリッド量子/古典的アルゴリズムとして変分量子固有解法 (VQE) アルゴリズムが提案された。 本稿では、VQEアルゴリズムを拡張し、有向グラフと無向グラフのスペクトルを解析する。
  論文  参考訳（メタデータ） (2019-12-27T23:27:38Z)

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

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