論文の概要: Strong consistency and optimality of spectral clustering in symmetric binary non-uniform Hypergraph Stochastic Block Model

• arxiv url: http://arxiv.org/abs/2306.06845v1
• Date: Mon, 12 Jun 2023 03:38:25 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-13 16:05:53.435748
• Title: Strong consistency and optimality of spectral clustering in symmetric binary non-uniform Hypergraph Stochastic Block Model
• Title（参考訳）: 対称二項非一様ハイパーグラフ確率ブロックモデルにおけるスペクトルクラスタリングの強い一貫性と最適性
• Authors: Haixiao Wang
• Abstract要約: 非一様EmphHypergraph Block Model(HSBM)に基づくランダムハイパーグラフの教師なし分類問題について検討する。 すべての均一層から情報を集約することで,各層を単独で考えるのが不可能であっても,強い一貫性が達成できることがわかった。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Consider the unsupervised classification problem in random hypergraphs under the non-uniform \emph{Hypergraph Stochastic Block Model} (HSBM) with two equal-sized communities ($n/2$), where each edge appears independently with some probability depending only on the labels of its vertices. In this paper, an \emph{information-theoretical} threshold for strong consistency is established. Below the threshold, every algorithm would misclassify at least two vertices with high probability, and the expected \emph{mismatch ratio} of the eigenvector estimator is upper bounded by $n$ to the power of minus the threshold. On the other hand, when above the threshold, despite the information loss induced by tensor contraction, one-stage spectral algorithms assign every vertex correctly with high probability when only given the contracted adjacency matrix, even if \emph{semidefinite programming} (SDP) fails in some scenarios. Moreover, strong consistency is achievable by aggregating information from all uniform layers, even if it is impossible when each layer is considered alone. Our conclusions are supported by both theoretical analysis and numerical experiments.
• Abstract（参考訳）: 非一様 \emph{Hypergraph Stochastic Block Model (HSBM) におけるランダムハイパーグラフの非教師なし分類問題を考える(n/2$)。 本稿では,強い整合性を示す<emph{information-theoretical>しきい値を確立する。 しきい値以下では、全てのアルゴリズムは、高い確率で少なくとも2つの頂点を誤分類し、固有ベクトル推定器の期待値である 'emph{mismatch ratio} は閾値を下げる力に$n$で上限づけられる。 一方、しきい値を超えると、テンソルの収縮によって引き起こされる情報損失にもかかわらず、一段階のスペクトルアルゴリズムは、あるシナリオにおいて \emph{semidefinite programming} (SDP) が失敗しても、全ての頂点を収縮した隣接行列のみを与えられた場合、高い確率で正しく割り当てる。 さらに、各層を単独で考えることは不可能であっても、すべての均一層から情報を集約することで、強固な一貫性を実現することができる。 我々の結論は理論解析と数値実験の両方で支持されている。

関連論文リスト

• Optimal and exact recovery on general non-uniform Hypergraph Stochastic Block Model [0.0]
  非一様ハイパーグラフ化ブロックモデル(HSBM)に基づくランダムハイパーグラフにおけるコミュニティ検出問題の検討 文献ではじめて、この一様でないケース下での正確な回復のための鋭いしきい値が、小さな制約の下で確立された。 しきい値を超えると正確な回復を達成でき、正確な回復が不可能な場合には最小の確率で達成できる2つの効率的なアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2023-04-25T20:30:33Z)
• Multilayer hypergraph clustering using the aggregate similarity matrix [0.7373617024876725]
  ハイパーグラフブロックモデル(HSBM)の多層版におけるコミュニティリカバリ問題について考察する。 本研究では、半定値プログラミング(SDP)アプローチを調査し、正確な回復を保証するモデルパラメータに関する情報理論条件を求める。
  論文  参考訳（メタデータ） (2023-01-27T11:15:46Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。 漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2022-06-17T06:10:20Z)
• Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
  本稿では,初期監視情報を同時に拡張し,識別親和性行列を構築することのできる,新しい半教師付きサブスペースクラスタリング手法を提案する。 6つの一般的なベンチマークデータセットの総合的な実験結果から,本手法が最先端手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-05-21T01:47:17Z)
• Sparse random hypergraphs: Non-backtracking spectra and community detection [10.503525445174464]
  我々は、ハイパーグラフの非追跡演算子に基づくスペクトル法が、アンジェリーニらによって予想される一般化ケステン・スティグム検出しきい値まで高い確率で作用することを証明した。 これは、一般的な対称確率テンソルに従って$r$ブロックを生成するHSBMの予測しきい値を達成する最初の証明可能かつ効率的なアルゴリズムである。
  論文  参考訳（メタデータ） (2022-03-14T17:45:03Z)
• Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model [6.681901523019242]
  非一様ハイパーグラフブロックモデル(HSBM)に基づくランダムハイパーグラフにおけるコミュニティ検出問題の検討 我々は,少なくとも$gamma$分の頂点を正しく分類した分割を出力するスペクトルアルゴリズムを提案し,$gammainはモデルの信号-雑音比(SNR)に依存する。 このアルゴリズムの理論的解析は、非一様ランダムハイパーグラフに対する隣接行列の濃度と正規化に依存しており、これは独立な関心を持つことができる。
  論文  参考訳（メタデータ） (2021-12-22T05:38:33Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  クラスタリングは教師なし学習における基本的なプリミティブである。 最近の研究は、低次手法のクラスに対する低い境界を確立している。 意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
  論文  参考訳（メタデータ） (2021-12-07T18:50:17Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Exact Recovery in the General Hypergraph Stochastic Block Model [92.28929858529679]
  本稿では,d-uniform hypergraph block model(d-HSBM)の正確な回復の基本的な限界について検討する。 精度の高いしきい値が存在し、正確な回復がしきい値の上に達成でき、その下には不可能であることを示す。
  論文  参考訳（メタデータ） (2021-05-11T03:39:08Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。 次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
  論文  参考訳（メタデータ） (2021-05-03T16:36:27Z)

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

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