論文の概要: 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の業績に触発され、彼は独立なエントリを持つ対称行列の固有ベクトルのエントリワイズ境界を開発した。
類似度行列の複雑な依存性構造にもかかわらず、類似のエントリワイズ保証が証明される。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。