論文の概要: Multi-Community Spectral Clustering for Geometric Graphs
- arxiv url: http://arxiv.org/abs/2508.00893v1
- Date: Sun, 27 Jul 2025 14:09:00 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-08-05 20:32:48.667397
- Title: Multi-Community Spectral Clustering for Geometric Graphs
- Title（参考訳）: 幾何グラフのためのマルチコミュニティスペクトルクラスタリング
- Authors: Luiz Emilio Allem, Konstantin Avrachenkov, Carlos Hoppen, Hariprasad Manjunath, Lucas Siviero Sibemberg,
- Abstract要約: このモデルにより生成されたグラフ上で,コミュニティ回復のためのスペクトルクラスタリングアルゴリズムを提案する。
弱い整合性を証明し、単純な局所的な精細化ステップが強い整合性を保証することを示す。
鍵となる要素は、非標準バージョンのデイビス=カハンの定理を、固有値が単純でないときに固有空間を制御するための応用である。
- 参考スコア（独自算出の注目度）: 0.0699049312989311
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we consider the soft geometric block model (SGBM) with a fixed number $k \geq 2$ of homogeneous communities in the dense regime, and we introduce a spectral clustering algorithm for community recovery on graphs generated by this model. Given such a graph, the algorithm produces an embedding into $\mathbb{R}^{k-1}$ using the eigenvectors associated with the $k-1$ eigenvalues of the adjacency matrix of the graph that are closest to a value determined by the parameters of the model. It then applies $k$-means clustering to the embedding. We prove weak consistency and show that a simple local refinement step ensures strong consistency. A key ingredient is an application of a non-standard version of Davis-Kahan theorem to control eigenspace perturbations when eigenvalues are not simple. We also analyze the limiting spectrum of the adjacency matrix, using a combination of combinatorial and matrix techniques.
- Abstract（参考訳）: 本稿では,高密度政権における同質コミュニティの固定数$k \geq 2$のソフトな幾何ブロックモデル(SGBM)について考察し,このモデルにより生成されたグラフのスペクトルクラスタリングアルゴリズムを提案する。
そのようなグラフが与えられたとき、アルゴリズムは、モデルのパラメータによって決定される値に最も近いグラフの隣接行列の$k-1$固有値に付随する固有ベクトルを用いて、$\mathbb{R}^{k-1}$への埋め込みを生成する。
次に、埋め込みに$k$-meansクラスタリングを適用する。
弱い整合性を証明し、単純な局所的な精細化ステップが強い整合性を保証することを示す。
鍵となる要素は、固有値が単純でないときに固有空間摂動を制御するために、デービス=カハンの定理の非標準版を適用することである。
また,組合せ行列法と行列法の組み合わせを用いて,隣接行列の制限スペクトルを解析した。
関連論文リスト
- Learnable Similarity and Dissimilarity Guided Symmetric Non-Negative Matrix Factorization [18.53944578996308]
学習可能な重み付き$k$-NNグラフを構築し、各$k$-th NNの信頼性を反映する。
識別的類似度行列を得るために,類似度行列の二重構造を持つ相似性行列を導入する。
提案したモデルを解決するために,効率的な代替最適化アルゴリズムを設計する。
論文 参考訳（メタデータ） (2024-12-05T11:32:53Z) - Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
本稿では,低ランク構造制約下でのグラフ学習のためのフレキシブルなアルゴリズムフレームワークを提案する。
この問題は楕円分布のペナルティ化された最大推定値として表される。
楕円モデルによく適合する正定行列と定ランクの正半定行列のジオメトリを利用する。
論文 参考訳（メタデータ） (2022-10-21T13:19:45Z) - Graph Polynomial Convolution Models for Node Classification of
Non-Homophilous Graphs [52.52570805621925]
本研究では,高階グラフ畳み込みからの効率的な学習と,ノード分類のための隣接行列から直接学習する。
得られたモデルが新しいグラフと残留スケーリングパラメータをもたらすことを示す。
提案手法は,非親和性パラメータのノード分類における精度の向上を実証する。
論文 参考訳（メタデータ） (2022-09-12T04:46:55Z) - Community Detection in the Hypergraph SBM: Exact Recovery Given the
Similarity Matrix [1.74048653626208]
我々は$similarity$matrix$W$で動作するアルゴリズムの性能を調査し、$W_ij$は$i$と$j$の両方を含むハイパーエッジの数を報告する。
ほぼ線形な実行時間を持つ単純かつ高効率なスペクトルアルゴリズムを設計し,min-bisectionしきい値を達成することを示す。
論文 参考訳（メタデータ） (2022-08-23T15:22:05Z) - Stochastic Parallelizable Eigengap Dilation for Large Graph Clustering [12.544602297450533]
私たちは、ほとんどのエッジがクラスタ内に落ち、わずかにエッジがクラスタ間に落ちているノードのクラスタを特定することを目的としています。
スペクトルクラスタリングのコアステップは、対応するグラフラプラシア行列の固有分解を行う。
本稿では,SVDソルバを高速化し,スペクトルクラスタリングを行うために,スペクトルを並列化可能なアプローチを提案する。
論文 参考訳（メタデータ） (2022-07-29T10:13:07Z) - 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) - Self-supervised Symmetric Nonnegative Matrix Factorization [82.59905231819685]
シンメトリー非負係数行列(SNMF)は、データクラスタリングの強力な方法であることを示した。
より良いクラスタリング結果を求めるアンサンブルクラスタリングにインスパイアされた,自己監視型SNMF(S$3$NMF)を提案する。
SNMFのコード特性に対する感度を、追加情報に頼らずに活用しています。
論文 参考訳（メタデータ） (2021-03-02T12:47:40Z) - A simpler spectral approach for clustering in directed networks [1.52292571922932]
隣接行列の固有値/固有ベクトル分解は、すべての一般的な方法よりも単純であることを示す。
広く使われているk平均アルゴリズムよりもガウス混合クラスタリングの方が優れていることを示す数値的な証拠を提供する。
論文 参考訳（メタデータ） (2021-02-05T14:16:45Z) - Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
ktimes k$, rank-r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ sample。
我々は、$cal O(frackrepsilon2log2fracepsilon)$ sample, a number linear in the high dimension, and almost linear in the matrices, usually low, rank proofs.というアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-09-30T19:10:32Z) - Higher-Order Spectral Clustering for Geometric Graphs [0.17188280334580194]
我々は、高階スペクトルクラスタリングと呼ばれる効果的な一般化を提案する。
概念的には古典的なスペクトルクラスタリング法に似ているが、高次固有値に付随する固有ベクトルを分割するために用いられる。
本手法は, 極小グラフにおいても, 数値実験に有効であることを示す。
論文 参考訳（メタデータ） (2020-09-23T19:51:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。