論文の概要: Community Detection in the Hypergraph SBM: Optimal Recovery Given the
Similarity Matrix
- arxiv url: http://arxiv.org/abs/2208.12227v2
- Date: Sat, 1 Jul 2023 04:54:27 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-04 15:48:33.420443
- Title: Community Detection in the Hypergraph SBM: Optimal Recovery Given the
Similarity Matrix
- Title（参考訳）: ハイパーグラフSBMにおけるコミュニティ検出:類似行列を考慮した最適回復
- Authors: Julia Gaudio, Nirmit Joshi
- Abstract要約: 我々は、$hypergraph$ $stochastic$ $block$ $model$ regimeから引き出されたハイパーグラフにおけるコミュニティ検出について検討する。
ほぼ線形な実行時間を持つ単純かつ高効率なスペクトルアルゴリズムを設計し、情報理論しきい値を達成することを示す。
- 参考スコア（独自算出の注目度）: 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
which operate on the $similarity$ $matrix$ $W$, where $W_{ij}$ reports the
number of hyperedges containing both $i$ and $j$. Under this information model,
Kim, Bandeira, and Goemans determined the information-theoretic threshold for
exact recovery in the logarithmic degree regime, and proposed a semidefinite
programming relaxation which they conjectured to be optimal. 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
information-theoretic 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$の固有ベクトルの強い$entrywise$境界に決定的に依存する。
我々の境界は、abbe、fan、wang、zhongの業績に触発され、彼は独立なエントリを持つ対称行列の固有ベクトルのエントリワイズ境界を開発した。
類似度行列の複雑な依存性構造にもかかわらず、類似のエントリワイズ保証が証明される。
関連論文リスト
- Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。
また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。
我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
論文 参考訳（メタデータ） (2025-02-07T15:57:56Z) - Entangled Mean Estimation in High-Dimensions [36.97113089188035]
信号のサブセットモデルにおける高次元エンタングルド平均推定の課題について検討する。
最適誤差(polylogarithmic factor)は$f(alpha,N) + sqrtD/(alpha N)$であり、$f(alpha,N)$は1次元問題の誤差であり、第二項は準ガウス誤差率である。
論文 参考訳（メタデータ） (2025-01-09T18:31:35Z) - SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More [37.208622097149714]
我々は、最大$|M u|$で境界を証明できる新しいアップタイムアルゴリズムの族を与える。
我々の認証アルゴリズムは, Sum-of-Squares階層を必須に活用する。
論文 参考訳（メタデータ） (2024-12-30T18:59:46Z) - 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) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。