論文の概要: 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) が失敗しても、全ての頂点を収縮した隣接行列のみを与えられた場合、高い確率で正しく割り当てる。 さらに、各層を単独で考えることは不可能であっても、すべての均一層から情報を集約することで、強固な一貫性を実現することができる。 我々の結論は理論解析と数値実験の両方で支持されている。

関連論文リスト

• One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering [56.81492360414741]
  両部グラフの1ステップ正規化カットを、特に線形時間複雑性で実施する方法を示す。 本稿では、まず、正規化制約付き一段階二分グラフカット基準を特徴付けるとともに、そのトレース問題に対する等価性を理論的に証明する。 このカット基準を、適応アンカー学習、二部グラフ学習、一段階正規化二部グラフ分割を同時にモデル化するスケーラブルなサブスペースクラスタリングアプローチに拡張する。
  論文  参考訳（メタデータ） (2023-05-12T11:27:20Z)
• Optimal and exact recovery on general non-uniform Hypergraph Stochastic Block Model [0.0]
  非一様ハイパーグラフ化ブロックモデル(HSBM)に基づくランダムハイパーグラフにおけるコミュニティ検出問題の検討 文献ではじめて、この一様でないケース下での正確な回復のための鋭いしきい値が、小さな制約の下で確立された。 しきい値を超えると正確な回復を達成でき、正確な回復が不可能な場合には最小の確率で達成できる2つの効率的なアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2023-04-25T20:30:33Z)
• Semi-Supervised Clustering of Sparse Graphs: Crossing the Information-Theoretic Threshold [3.6052935394000234]
  ブロックモデルは、ネットワーク構造データのクラスタリングとコミュニティ検出のための標準ランダムグラフモデルである。 ネットワークトポロジに基づく推定器は、モデルパラメータが一定の閾値以下である場合、スパースグラフの確率よりも大幅に向上する。 パラメータ領域全体でラベルの任意の部分で実現可能であることを示す。
  論文  参考訳（メタデータ） (2022-05-24T00:03:25Z)
• Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
  本稿では,初期監視情報を同時に拡張し,識別親和性行列を構築することのできる,新しい半教師付きサブスペースクラスタリング手法を提案する。 6つの一般的なベンチマークデータセットの総合的な実験結果から,本手法が最先端手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-05-21T01:47:17Z)
• Geometric Graph Representation Learning via Maximizing Rate Reduction [73.6044873825311]
  学習ノード表現は、コミュニティ検出やノード分類などのグラフ解析において、さまざまな下流タスクの恩恵を受ける。 教師なしの方法でノード表現を学習するための幾何学グラフ表現学習(G2R)を提案する。 G2R は異なるグループ内のノードを異なる部分空間にマッピングし、各部分空間はコンパクトで異なる部分空間が分散される。
  論文  参考訳（メタデータ） (2022-02-13T07:46:24Z)
• Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model [6.681901523019242]
  非一様ハイパーグラフブロックモデル(HSBM)に基づくランダムハイパーグラフにおけるコミュニティ検出問題の検討 我々は,少なくとも$gamma$分の頂点を正しく分類した分割を出力するスペクトルアルゴリズムを提案し,$gammainはモデルの信号-雑音比(SNR)に依存する。 このアルゴリズムの理論的解析は、非一様ランダムハイパーグラフに対する隣接行列の濃度と正規化に依存しており、これは独立な関心を持つことができる。
  論文  参考訳（メタデータ） (2021-12-22T05:38:33Z)
• 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)
• Agnostic Learning of Halfspaces with Gradient Descent via Soft Margins [92.7662890047311]
  勾配降下は、分類誤差$tilde O(mathsfOPT1/2) + varepsilon$ in $mathrmpoly(d,1/varepsilon)$ time and sample complexity.
  論文  参考訳（メタデータ） (2020-10-01T16:48:33Z)

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

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