論文の概要: Information-Theoretic Limits and Strong Consistency on Binary Non-uniform Hypergraph Stochastic Block Models

• arxiv url: http://arxiv.org/abs/2306.06845v2
• Date: Thu, 19 Dec 2024 08:23:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-20 13:27:05.467325
• Title: Information-Theoretic Limits and Strong Consistency on Binary Non-uniform Hypergraph Stochastic Block Models
• Title（参考訳）: 双対非一様ハイパーグラフ確率ブロックモデルにおける情報理論的限界と強い整合性
• Authors: Hai-Xiao Wang,
• Abstract要約: 非一様ハイパーグラフブロックモデル(HSBM)の下でのランダムハイパーグラフの教師なし分類問題 本稿では,クラスタリング精度と強い一貫性しきい値に対する情報理論の限界を確立する。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: Consider the unsupervised classification problem in random hypergraphs under the non-uniform Hypergraph Stochastic Block Model (HSBM) with two equal-sized communities, where each edge appears independently with some probability depending only on the labels of its vertices. In this paper, the information-theoretic limits on the clustering accuracy and the strong consistency threshold are established, expressed in terms of the generalized Hellinger distance. Below the threshold, it is impossible to assign all vertices to their own communities, and the lower bound of the expected mismatch ratio is derived. On the other hand, the problem space is (sometimes) divided into two disjoint subspaces when above the threshold. When only the contracted adjacency matrix is given, with high probability, one-stage spectral algorithms succeed in assigning every vertex correctly in the subspace far away from the threshold but fail in the other one. Two subsequent refinement algorithms are proposed to improve the clustering accuracy, which attain the lowest possible mismatch ratio, previously derived from the information-theoretical perspective. The failure of spectral algorithms in the second subspace arises from the loss of information induced by tensor contraction. The origin of this loss and possible solutions to minimize the impact are presented. Moreover, different from uniform hypergraphs, strong consistency is achievable by aggregating information from all uniform layers, even if it is impossible when each layer is considered alone.
• Abstract（参考訳）: 非一様ハイパーグラフ確率ブロックモデル(HSBM)に基づくランダムハイパーグラフの非教師なし分類問題を考える。 本稿では,クラスタリング精度と強い一貫性しきい値に関する情報理論上の限界を,一般化したヘリンジャー距離で表現する。 閾値以下では、全ての頂点を自身のコミュニティに割り当てることは不可能であり、予測ミスマッチ比の低い境界が導出される。 一方、問題空間はしきい値を超えるときに(時には)2つの非随伴部分空間に分割される。 収縮した隣接行列のみを与えると、高い確率で1段階のスペクトルアルゴリズムがしきい値から遠く離れた部分空間で全ての頂点を正しく割り当てることに成功したが、他方では失敗する。 その後の2つの改良アルゴリズムは、以前に情報理論の観点から導かれた最小のミスマッチ比が得られるクラスタリング精度を改善するために提案される。 2番目の部分空間におけるスペクトルアルゴリズムの失敗は、テンソルの収縮によって引き起こされる情報の喪失から生じる。 この損失の起源と影響を最小限に抑える可能な解決策が提示される。 さらに、均一なハイパーグラフとは異なり、各層を単独で考えると不可能であっても、全ての均一な層から情報を集約することで、強い一貫性が達成できる。

関連論文リスト

• 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)

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

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