論文の概要: Community Detection in the Hypergraph SBM: Optimal Recovery Given the
Similarity Matrix
- arxiv url: http://arxiv.org/abs/2208.12227v1
- Date: Tue, 23 Aug 2022 15:22:05 GMT
- ステータス: 処理完了
- システム内更新日: 2022-08-26 14:04:58.117219
- Title: Community Detection in the Hypergraph SBM: Optimal Recovery Given the
Similarity Matrix
- Title（参考訳）: ハイパーグラフSBMにおけるコミュニティ検出:類似行列を考慮した最適回復
- Authors: Julia Gaudio, Nirmit Joshi
- Abstract要約: コミュニティ検出はネットワーク科学における根本的な問題である。
単純で高効率なスペクトルアルゴリズムが最適であることを示す。
私たちの限界は、Abe、Fan、Wang、Zhongの業績にインスパイアされています。
- 参考スコア（独自算出の注目度）: 2.28438857884398
- License: http://creativecommons.org/licenses/by/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 for
community detection in a case where the full hypergraph is unknown. Instead, we
are provided a $similarity$ $matrix$ $W$, where $W_{ij}$ reports the number of
hyperedges containing both $i$ and $j$. Under this information model, Kim,
Bandeira, and Goemans [KBG18] determined the information-theoretic threshold
for exact recovery, and proposed a semidefinite programming relaxation which
they conjectured to be optimal. In this paper, we confirm this conjecture. We
also show that a simple, highly efficient spectral algorithm is optimal,
establishing the spectral algorithm 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 [AFWZ20], 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, and Goemans [KBG18] は、正確な回復のための情報理論しきい値を決定し、最適な半定値プログラミング緩和を提案した。
本稿では,この予想を確認する。
また,単純で高効率なスペクトルアルゴリズムが最適であることを示し,スペクトルアルゴリズムを選択法として確立した。
スペクトルアルゴリズムの解析は、$W$の固有ベクトルの強い$entrywise$境界に決定的に依存する。
我々の境界は、Abe, Fan, Wang, Zhong [AFWZ20] の業績に触発され、彼は独立なエントリを持つ対称行列の固有ベクトルのエントリーワイド境界を開発した。
類似度行列の複雑な依存性構造にもかかわらず、類似のエントリワイズ保証が証明される。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。