論文の概要: Sparse random hypergraphs: Non-backtracking spectra and community detection

• arxiv url: http://arxiv.org/abs/2203.07346v1
• Date: Mon, 14 Mar 2022 17:45:03 GMT
• ステータス: 処理完了
• システム内更新日: 2022-03-15 17:15:49.836516
• Title: Sparse random hypergraphs: Non-backtracking spectra and community detection
• Title（参考訳）: スパースランダムハイパーグラフ:非バックトラッキングスペクトルとコミュニティ検出
• Authors: Ludovic Stephan and Yizhe Zhu
• Abstract要約: 我々は、ハイパーグラフの非追跡演算子に基づくスペクトル法が、アンジェリーニらによって予想される一般化ケステン・スティグム検出しきい値まで高い確率で作用することを証明した。 これは、一般的な対称確率に応じて$k$ブロックが生成されるHSBMの予測しきい値を達成する最初の証明可能かつ効率的なスペクトルアルゴリズムである。
• 参考スコア（独自算出の注目度）: 15.175954792120173
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the community detection problem in a sparse $q$-uniform hypergraph $G$, assuming that $G$ is generated according to the so-called Hypergraph Stochastic Block Model (HSBM). We prove that a spectral method based on the non-backtracking operator for hypergraphs works with high probability down to the generalized Kesten-Stigum detection threshold conjectured by Angelini et al. We characterize the spectrum of the non-backtracking operator for the sparse HSBM, and provide an efficient dimension reduction procedure using the Ihara-Bass formula for hypergraphs. As a result, community detection for the sparse HSBM on $n$ vertices can be reduced to an eigenvector problem of a $2n\times 2n$ non-normal matrix constructed from the adjacency matrix and the degree matrix of the hypergraph. To the best of our knowledge, this is the first provable and efficient spectral algorithm that achieves the conjectured threshold for HSBMs with $k$ blocks generated according to a general symmetric probability tensor.
• Abstract（参考訳）: 我々は,いわゆるHypergraph Stochastic Block Model (HSBM) に基づいて,$G$が生成されることを前提として,スパース$q$-uniform hypergraph $G$のコミュニティ検出問題を考察した。 ハイパーグラフの非追跡演算子に基づくスペクトル法は、アンジェリーニらによって予想される一般化ケステン・スティグム検出しきい値まで高い確率で作用することを示す。 我々は、スパースHSBMの非バックトラック演算子のスペクトルを特徴付け、ハイパーグラフのIhara-Bass式を用いた効率的な次元削減手順を提供する。 その結果,超グラフの隣接行列と次数行列から構築した2n\times 2n$非正規行列の固有ベクトル問題に,n$頂点上のスパースHSBMのコミュニティ検出を還元することができる。 我々の知る限り、このアルゴリズムは一般的な対称確率テンソルに基づいて$k$ブロックを生成するHSBMの予測しきい値を達成する最初の証明可能かつ効率的なスペクトルアルゴリズムである。

関連論文リスト

• Community detection with the Bethe-Hessian [8.890988784292926]
  スパースブロックモデル(SBM)におけるベーテ・ヘッセン分光法の最初の厳密な分析法を提供する。 ベーテ・ヘッセン行列の負の外れ値の数は、ケステン・スティグムしきい値より上のブロックの数を一貫して推定できることが示される。 また、その外周負固有値の位置の濃度を定め、ベーテ・ヘッセン行列に基づくスペクトル法により、弱い整合性を実現することができる。
  論文  参考訳（メタデータ） (2024-11-05T06:18:37Z)
• Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
  一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。 既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。 G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
  論文  参考訳（メタデータ） (2024-01-14T14:14:19Z)
• Strong consistency and optimality of spectral clustering in symmetric binary non-uniform Hypergraph Stochastic Block Model [0.0]
  非一様EmphHypergraph Block Model(HSBM)に基づくランダムハイパーグラフの教師なし分類問題について検討する。 すべての均一層から情報を集約することで,各層を単独で考えるのが不可能であっても,強い一貫性が達成できることがわかった。
  論文  参考訳（メタデータ） (2023-06-12T03:38:25Z)
• Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
  ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。 我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。 平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
  論文  参考訳（メタデータ） (2023-04-17T10:38:08Z)
• Community Detection in the Hypergraph SBM: Exact Recovery Given the Similarity Matrix [1.74048653626208]
  我々は$similarity$matrix$W$で動作するアルゴリズムの性能を調査し、$W_ij$は$i$と$j$の両方を含むハイパーエッジの数を報告する。 ほぼ線形な実行時間を持つ単純かつ高効率なスペクトルアルゴリズムを設計し,min-bisectionしきい値を達成することを示す。
  論文  参考訳（メタデータ） (2022-08-23T15:22:05Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• Nonbacktracking spectral clustering of nonuniform hypergraphs [2.408714894793063]
  非一様ハイパーグラフに対するスペクトルクラスタリングをハイパーグラフ非追跡演算子を用いて検討する。 本稿では,線形化された信念伝達を用いたハイパーグラフブロックモデルにおける推論の交互化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-04-27T01:14:06Z)
• Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model [6.681901523019242]
  非一様ハイパーグラフブロックモデル(HSBM)に基づくランダムハイパーグラフにおけるコミュニティ検出問題の検討 我々は,少なくとも$gamma$分の頂点を正しく分類した分割を出力するスペクトルアルゴリズムを提案し,$gammainはモデルの信号-雑音比(SNR)に依存する。 このアルゴリズムの理論的解析は、非一様ランダムハイパーグラフに対する隣接行列の濃度と正規化に依存しており、これは独立な関心を持つことができる。
  論文  参考訳（メタデータ） (2021-12-22T05:38:33Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。 我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。 MRP のサブクラスに対する minimax の下位境界を証明する。
  論文  参考訳（メタデータ） (2021-09-24T14:48:20Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。 次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
  論文  参考訳（メタデータ） (2021-05-03T16:36:27Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。 本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-12T16:29:45Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。