論文の概要: Community detection with the Bethe-Hessian
- arxiv url: http://arxiv.org/abs/2411.02835v1
- Date: Tue, 05 Nov 2024 06:18:37 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-06 14:58:53.975672
- Title: Community detection with the Bethe-Hessian
- Title（参考訳）: Bethe-Hessianによるコミュニティ検出
- Authors: Ludovic Stephan, Yizhe Zhu,
- Abstract要約: スパースブロックモデル(SBM)におけるベーテ・ヘッセン分光法の最初の厳密な分析法を提供する。
ベーテ・ヘッセン行列の負の外れ値の数は、ケステン・スティグムしきい値より上のブロックの数を一貫して推定できることが示される。
また、その外周負固有値の位置の濃度を定め、ベーテ・ヘッセン行列に基づくスペクトル法により、弱い整合性を実現することができる。
- 参考スコア（独自算出の注目度）: 8.890988784292926
- License:
- Abstract: The Bethe-Hessian matrix, introduced by Saade, Krzakala, and Zdeborov\'a (2014), is a Hermitian matrix designed for applying spectral clustering algorithms to sparse networks. Rather than employing a non-symmetric and high-dimensional non-backtracking operator, a spectral method based on the Bethe-Hessian matrix is conjectured to also reach the Kesten-Stigum detection threshold in the sparse stochastic block model (SBM). We provide the first rigorous analysis of the Bethe-Hessian spectral method in the SBM under both the bounded expected degree and the growing degree regimes. Specifically, we demonstrate that: (i) When the expected degree $d\geq 2$, the number of negative outliers of the Bethe-Hessian matrix can consistently estimate the number of blocks above the Kesten-Stigum threshold, thus confirming a conjecture from Saade, Krzakala, and Zdeborov\'a (2014) for $d\geq 2$. (ii) For sufficiently large $d$, its eigenvectors can be used to achieve weak recovery. (iii) As $d\to\infty$, we establish the concentration of the locations of its negative outlier eigenvalues, and weak consistency can be achieved via a spectral method based on the Bethe-Hessian matrix.
- Abstract（参考訳）: Saade, Krzakala, Zdeborov\'a (2014) によって導入されたベーテ・ヘシアン行列 (Bethe-Hessian matrix) は、スペクトルクラスタリングアルゴリズムをスパースネットワークに適用するために設計されたエルミート行列である。
非対称かつ高次元の非追跡演算子を用いるのではなく、ベーテ・ヘッセン行列に基づくスペクトル法がスパース確率ブロックモデル(SBM)のケステン・スティグム検出しきい値に達することを予想する。
本研究では,SBMにおけるBethe-Hessスペクトル法を,有界次数と成長次数の両方で厳密に解析した。
特に、私たちはこう示しています。
i) 予想次数 $d\geq 2$ のとき、ベーテ・ヘッセン行列の負の外れ値の数は、一貫してケステン・スティグムしきい値より上のブロックの数を推定できるので、$d\geq 2$ に対して Saade, Krzakala, Zdeborov\'a (2014) からの予想を確認することができる。
(ii)十分に大きな$d$の場合、その固有ベクトルは弱い回復を達成するために使用できる。
(iii)$d\to\infty$として、負のアウトリート固有値の位置の濃度を確立し、ベーテ・ヘッセン行列に基づくスペクトル法により弱一貫性を達成することができる。
関連論文リスト
- Low-rank Bayesian matrix completion via geodesic Hamiltonian Monte Carlo on Stiefel manifolds [0.18416014644193066]
低ランクベイズ行列の効率的な計算を可能にするための新しいサンプリングベース手法を提案する。
提案手法は, 標準ギブスサンプリング器で発生するサンプリング困難を, 行列完備化に使用される一般的な2つの行列因子化のために解決することを示す。
数値的な例は、より優れた混合と定常分布への高速収束を含む優れたサンプリング性能を示す。
論文 参考訳（メタデータ） (2024-10-27T03:12:53Z) - Provable Benefit of Annealed Langevin Monte Carlo for Non-log-concave Sampling [28.931489333515618]
簡単なアニール型Langevin Monte Carloアルゴリズムに対して$widetildeOleft(fracdbeta2cal A2varepsilon6right)のオラクル複雑性を確立する。
例えば、$cal A$ は対象分布 $pi$ と容易にサンプリング可能な分布を補間する確率測度の曲線の作用を表す。
論文 参考訳（メタデータ） (2024-07-24T02:15:48Z) - Sparse PCA with Oracle Property [115.72363972222622]
新規な正規化を伴うスパースPCAの半定緩和に基づく推定器群を提案する。
我々は、家族内の別の推定器が、スパースPCAの標準半定緩和よりも、より急激な収束率を達成することを証明した。
論文 参考訳（メタデータ） (2023-12-28T02:52:54Z) - A Family of Bipartite Separability Criteria Based on Bloch
Representation of Density Matrices [7.6857251828091595]
密度行列のブロッホ表現に基づく任意の次元における二部量子系の分離性について検討する。
我々は、Bloch表現の相関テンソルから構築された行列$T_alphabeta(rho)$と$W_ab,alphabeta(rho)$の2つの分離性基準を示す。
論文 参考訳（メタデータ） (2023-04-30T12:11:51Z) - Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
本稿では,初期監視情報を同時に拡張し,識別親和性行列を構築することのできる,新しい半教師付きサブスペースクラスタリング手法を提案する。
6つの一般的なベンチマークデータセットの総合的な実験結果から,本手法が最先端手法よりも優れていることを示す。
論文 参考訳（メタデータ） (2022-05-21T01:47:17Z) - Sparse random hypergraphs: Non-backtracking spectra and community
detection [10.503525445174464]
我々は、ハイパーグラフの非追跡演算子に基づくスペクトル法が、アンジェリーニらによって予想される一般化ケステン・スティグム検出しきい値まで高い確率で作用することを証明した。
これは、一般的な対称確率テンソルに従って$r$ブロックを生成するHSBMの予測しきい値を達成する最初の証明可能かつ効率的なアルゴリズムである。
論文 参考訳（メタデータ） (2022-03-14T17:45:03Z) - Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。
我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。
MRP のサブクラスに対する minimax の下位境界を証明する。
論文 参考訳（メタデータ） (2021-09-24T14:48:20Z) - Exact Recovery in the General Hypergraph Stochastic Block Model [92.28929858529679]
本稿では,d-uniform hypergraph block model(d-HSBM)の正確な回復の基本的な限界について検討する。
精度の高いしきい値が存在し、正確な回復がしきい値の上に達成でき、その下には不可能であることを示す。
論文 参考訳（メタデータ） (2021-05-11T03:39:08Z) - Spectral clustering under degree heterogeneity: a case for the random
walk Laplacian [83.79286663107845]
本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。
次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
論文 参考訳（メタデータ） (2021-05-03T16:36:27Z) - Searching for exceptional points and inspecting non-contractivity of
trace distance in (anti-)$\mathcal{PT}\!-$symmetric systems [0.0]
パリティ時間(mathcalPT$)対称性と反$mathcalPT$対称性を持つ非エルミート系は例外点(EP)をもたらす
発展密度行列の対角化を必要としないHSS(Hilbert-Schmidt speed)に基づく,強力で計算が容易なツールを提案する。
2つの任意の量子状態の区別可能性の尺度であるトレース距離は、系の非エルミート進化の下では非収縮的である可能性がある。
論文 参考訳（メタデータ） (2021-01-12T18:42:52Z) - Relative Error Bound Analysis for Nuclear Norm Regularized Matrix Completion [101.83262280224729]
我々は、原子核ノルム正規化行列補完に対する相対誤差を開発する。
未知行列の最適低ランク近似を回復するための相対上界を導出する。
論文 参考訳（メタデータ） (2015-04-26T13:12:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。