論文の概要: Community Detection in the Hypergraph SBM: Exact Recovery Given the
Similarity Matrix
- arxiv url: http://arxiv.org/abs/2208.12227v3
- Date: Sat, 14 Oct 2023 18:07:48 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-18 06:59:59.007626
- Title: Community Detection in the Hypergraph SBM: Exact Recovery Given the
Similarity Matrix
- Title（参考訳）: ハイパーグラフSBMにおけるコミュニティ検出 : 類似行列を用いたエクササイズリカバリ
- Authors: Julia Gaudio, Nirmit Joshi
- Abstract要約: 我々は$similarity$matrix$W$で動作するアルゴリズムの性能を調査し、$W_ij$は$i$と$j$の両方を含むハイパーエッジの数を報告する。
ほぼ線形な実行時間を持つ単純かつ高効率なスペクトルアルゴリズムを設計し,min-bisectionしきい値を達成することを示す。
- 参考スコア（独自算出の注目度）: 1.74048653626208
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: Community detection is a fundamental problem in network science. In this
paper, we consider community detection in hypergraphs drawn from the
$hypergraph$ $stochastic$ $block$ $model$ (HSBM), with a focus on exact
community recovery. We study the performance of polynomial-time algorithms
which operate on the $similarity$ $matrix$ $W$, where $W_{ij}$ reports the
number of hyperedges containing both $i$ and $j$. Under this information model,
while the precise information-theoretic limit is unknown, Kim, Bandeira, and
Goemans derived a sharp threshold up to which the natural min-bisection
estimator on $W$ succeeds. As min-bisection is NP-hard in the worst case, they
additionally proposed a semidefinite programming (SDP) relaxation and
conjectured that it achieves the same recovery threshold as the min-bisection
estimator.
In this paper, we confirm this conjecture. We also design a simple and highly
efficient spectral algorithm with nearly linear runtime and show that it
achieves the min-bisection threshold. Moreover, the spectral algorithm also
succeeds in denser regimes and is considerably more efficient than previous
approaches, establishing it as the method of choice. Our analysis of the
spectral algorithm crucially relies on strong $entrywise$ bounds on the
eigenvectors of $W$. Our bounds are inspired by the work of Abbe, Fan, Wang,
and Zhong, who developed entrywise bounds for eigenvectors of symmetric
matrices with independent entries. Despite the complex dependency structure in
similarity matrices, we prove similar entrywise guarantees.
- Abstract（参考訳）: コミュニティ検出はネットワーク科学における根本的な問題である。
本稿では,hypergraph$$$stochastic$ $block$$model$ (hsbm) を用いたハイパーグラフにおけるコミュニティ検出について考察する。
我々は$similarity$$matrix$$W$で動作する多項式時間アルゴリズムの性能を調査し、$W_{ij}$は$i$と$j$の両方を含むハイパーエッジの数を報告する。
この情報モデルの下では、正確な情報理論の限界は分かっていないが、Kim, Bandeira, Goemans は、W$の自然な分節推定器が成功するまでの鋭い閾値を導出した。
最悪の場合、min-bisectionはNP-hardであるため、半定値プログラミング(SDP)緩和も提案し、min-bisection 推定器と同じ回復しきい値に達すると推測した。
本稿では,この予想を確認する。
また、ほぼ線形な実行時間を持つ単純かつ高効率なスペクトルアルゴリズムを設計し、min-bisection閾値を達成することを示す。
さらに、スペクトルアルゴリズムはより高密度な状態でも成功し、従来の手法よりもかなり効率的であり、選択方法として確立されている。
スペクトルアルゴリズムの解析は、$W$の固有ベクトルの強い$entrywise$境界に決定的に依存する。
我々の境界は、abbe、fan、wang、zhongの業績に触発され、彼は独立なエントリを持つ対称行列の固有ベクトルのエントリワイズ境界を開発した。
類似度行列の複雑な依存性構造にもかかわらず、類似のエントリワイズ保証が証明される。
関連論文リスト
- Sum-of-squares lower bounds for Non-Gaussian Component Analysis [33.80749804695003]
非ガウス成分分析(Non-Gaussian Component Analysis、NGCA)は、高次元データセットにおいて非ガウス方向を求める統計的タスクである。
本稿では Sum-of-Squares フレームワークにおける NGCA の複雑さについて考察する。
論文 参考訳（メタデータ） (2024-10-28T18:19:13Z) - Exact Community Recovery (under Side Information): Optimality of Spectral Algorithms [1.4732811715354452]
一般の2つのコミュニティブロックモデルにおいて,コミュニティの正確な回復の問題について検討する。
正確な回復の情報理論的限界に対する側情報の影響を統一的に分析する。
論文 参考訳（メタデータ） (2024-06-18T21:48:59Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。
我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文 参考訳（メタデータ） (2022-06-07T16:49:54Z) - Sparse random hypergraphs: Non-backtracking spectra and community
detection [10.503525445174464]
我々は、ハイパーグラフの非追跡演算子に基づくスペクトル法が、アンジェリーニらによって予想される一般化ケステン・スティグム検出しきい値まで高い確率で作用することを証明した。
これは、一般的な対称確率テンソルに従って$r$ブロックを生成するHSBMの予測しきい値を達成する最初の証明可能かつ効率的なアルゴリズムである。
論文 参考訳（メタデータ） (2022-03-14T17:45:03Z) - Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。
O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。
さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
論文 参考訳（メタデータ） (2021-10-15T00:54:04Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - An Online Riemannian PCA for Stochastic Canonical Correlation Analysis [37.8212762083567]
投影行列の再パラメータ化を用いた正準相関解析(CCA)のための効率的なアルゴリズム(RSG+)を提案する。
本論文は,その特性の定式化と技術的解析に主眼を置いているが,本実験により,一般的なデータセットに対する経験的挙動が極めて有望であることが確認された。
論文 参考訳（メタデータ） (2021-06-08T23:38:29Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。