論文の概要: Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model
- arxiv url: http://arxiv.org/abs/2112.11671v3
- Date: Wed, 24 Apr 2024 21:55:34 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-27 00:45:56.917147
- Title: Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model
- Title（参考訳）: 非一様超グラフ確率ブロックモデルにおける部分回復と弱い整合性
- Authors: Ioana Dumitriu, Haixiao Wang, Yizhe Zhu,
- Abstract要約: 非一様ハイパーグラフブロックモデル(HSBM)に基づくランダムハイパーグラフにおけるコミュニティ検出問題の検討
我々は,少なくとも$gamma$分の頂点を正しく分類した分割を出力するスペクトルアルゴリズムを提案し,$gammainはモデルの信号-雑音比(SNR)に依存する。
このアルゴリズムの理論的解析は、非一様ランダムハイパーグラフに対する隣接行列の濃度と正規化に依存しており、これは独立な関心を持つことができる。
- 参考スコア（独自算出の注目度）: 6.681901523019242
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the community detection problem in sparse random hypergraphs under the non-uniform hypergraph stochastic block model (HSBM), a general model of random networks with community structure and higher-order interactions. When the random hypergraph has bounded expected degrees, we provide a spectral algorithm that outputs a partition with at least a $\gamma$ fraction of the vertices classified correctly, where $\gamma\in (0.5,1)$ depends on the signal-to-noise ratio (SNR) of the model. When the SNR grows slowly as the number of vertices goes to infinity, our algorithm achieves weak consistency, which improves the previous results in Ghoshdastidar and Dukkipati (2017) for non-uniform HSBMs. Our spectral algorithm consists of three major steps: (1) Hyperedge selection: select hyperedges of certain sizes to provide the maximal signal-to-noise ratio for the induced sub-hypergraph; (2) Spectral partition: construct a regularized adjacency matrix and obtain an approximate partition based on singular vectors; (3) Correction and merging: incorporate the hyperedge information from adjacency tensors to upgrade the error rate guarantee. The theoretical analysis of our algorithm relies on the concentration and regularization of the adjacency matrix for sparse non-uniform random hypergraphs, which can be of independent interest.
- Abstract（参考訳）: 本研究では,非一様ハイパーグラフ確率ブロックモデル(HSBM)に基づくスパース・ランダム・ハイパーグラフにおけるコミュニティ検出問題について考察する。
ランダムハイパーグラフが有界次数を持つ場合、少なくとも$\gamma$区切りを正しく分類した頂点を出力するスペクトルアルゴリズムを提供し、$\gamma\in (0.5,1)$はモデルの信号-雑音比(SNR)に依存する。
頂点数が無限に近づくにつれてSNRが緩やかに増加すると、我々のアルゴリズムは弱い一貫性を達成し、非一様HSBMに対するGhoshdastidar と Dukkipati (2017) の以前の結果を改善する。
スペクトルアルゴリズムは,(1) ハイパーエッジ選択: 誘導されたサブハイパーグラフに対して最大信号-雑音比を提供するために,特定のサイズのハイパーエッジを選択する; (2) スペクトル分割: 正規化された隣接行列を構築し,特異ベクトルに基づいて近似的な分割を得る; (3) 補正とマージ: 隣接テンソルからのハイパーエッジ情報を組み込んでエラー率保証をアップグレードする。
本アルゴリズムの理論的解析は,非一様非一様ハイパーグラフに対する隣接行列の濃度と正則化に依存する。
関連論文リスト
- 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) - Optimal and exact recovery on general non-uniform Hypergraph Stochastic Block Model [0.0]
非一様ハイパーグラフ化ブロックモデル(HSBM)に基づくランダムハイパーグラフにおけるコミュニティ検出問題の検討
文献ではじめて、この一様でないケース下での正確な回復のための鋭いしきい値が、小さな制約の下で確立された。
しきい値を超えると正確な回復を達成でき、正確な回復が不可能な場合には最小の確率で達成できる2つの効率的なアルゴリズムを提供する。
論文 参考訳（メタデータ） (2023-04-25T20:30:33Z) - 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) - Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector
Problems [98.34292831923335]
オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。
我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
論文 参考訳（メタデータ） (2021-12-29T18:46:52Z) - Balanced Coarsening for Multilevel Hypergraph Partitioning via
Wasserstein Discrepancy [40.93626211612559]
マルチレベルハイパーグラフのためのバランスの取れた粗大化方式を提案する。
初期分割アルゴリズムはk-wayハイパーグラフの品質を向上させるために設計されている。
論文 参考訳（メタデータ） (2021-06-14T15:30:34Z) - 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) - ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。
有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
論文 参考訳（メタデータ） (2020-08-28T14:46:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。