論文の概要: Achieving the Kesten-Stigum bound in the non-uniform hypergraph stochastic block model

• arxiv url: http://arxiv.org/abs/2604.20907v1
• Date: Tue, 21 Apr 2026 20:43:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-24 14:40:06.08423
• Title: Achieving the Kesten-Stigum bound in the non-uniform hypergraph stochastic block model
• Title（参考訳）: 非一様超グラフ確率ブロックモデルにおけるケステン・スティグム境界の達成
• Authors: Manuel Fernandez, Ludovic Stephan, Yizhe Zhu,
• Abstract要約: 非一様ハイパーグラフブロックモデルにおけるコミュニティ検出問題について検討する。 検出しきい値以下で複数の均一なハイパーグラフ層を組み合わせれば、弱い回復が可能か? 均一なハイパーグラフ層にまたがる信号-雑音比の和が1を超えると、弱い回復が可能であることを示す。
• 参考スコア（独自算出の注目度）: 8.513101411060898
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the community detection problem in the non-uniform hypergraph stochastic block model (HSBM), where hyperedges of varying sizes coexist. This setting captures higher-order and multi-view interactions and raises a fundamental question: can multiple uniform hypergraph layers below the detection threshold be combined to enable weak recovery? We answer this question by establishing a Kesten--Stigum-type bound for weak recovery in a general class of non-uniform HSBMs with $r$ blocks, generated according to multiple symmetric probability tensors. In the case $r=2$, we show that weak recovery is possible whenever the sum of the signal-to-noise ratios across all uniform hypergraph layers exceeds one, thereby confirming the positive part of a conjecture in (Chodrow et al., 2023). Moreover, we provide a polynomial-time spectral algorithm that achieves this threshold via an optimally weighted non-backtracking operator. For the unweighted non-backtracking matrix, our spectral method attains a different algorithmic threshold, also conjectured in (Chodrow et al., 2023). Our approach develops a spectral theory for weighted non-backtracking operators on non-uniform hypergraphs, including a precise characterization of outlier eigenvalues and eigenvector overlaps. We introduce a novel Ihara--Bass formula tailored to weighted non-uniform hypergraphs, which yields an efficient low-dimensional representation and leads to a provable spectral reconstruction algorithm. Taken together, these results provide a principled and computationally efficient approach to clustering in non-uniform hypergraphs, and highlight the role of optimal weighting in aggregating heterogeneous higher-order interactions.
• Abstract（参考訳）: 非一様ハイパーグラフ確率ブロックモデル(HSBM)におけるコミュニティ検出問題について検討した。 この設定は、高階と多面的な相互作用を捉え、基本的な疑問を提起する: 検出しきい値以下の複数の均一なハイパーグラフ層を組み合わせて、弱い回復を可能にすることができるか? 複数の対称確率テンソルに基づいて生成された$r$ブロックを持つ非一様HSBMの一般クラスにおいて、弱い回復のためのケステン-スティグム型境界を確立することで、この問題に答える。 r=2$の場合、すべての均一ハイパーグラフ層における信号-雑音比の和が 1 を超えると弱回復が可能であることを示す(Chodrow et al , 2023)。 さらに、最適重み付けされた非バックトラック演算子を用いて、このしきい値を達成する多項式時間スペクトルアルゴリズムを提案する。 非重みのない非追跡行列の場合、スペクトル法はアルゴリズムのしきい値が異なる(Chodrow et al , 2023)。 提案手法は,非一様ハイパーグラフ上での重み付き非追従作用素のスペクトル理論を開発し,外乱固有値と固有ベクトル重なりの正確な評価を含む。 重み付けされた非一様ハイパーグラフに合わせた新しいIhara-Bass式を導入し,高効率な低次元表現を実現し,証明可能なスペクトル再構成アルゴリズムを提案する。 これらの結果は、非一様ハイパーグラフにおけるクラスタリングに対する原理的かつ計算学的に効率的なアプローチを提供し、不均一な高次相互作用の集約における最適な重み付けの役割を強調している。

関連論文リスト

• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  一般的な嗜好を伴う文脈的オンラインRLHFの問題を考える。 一般化された双線形選好モデルを用いて、低ランクなスキュー対称行列による選好を捉える。 グリーディポリシーの双対ギャップは推定誤差の正方形によって有界であることを示す。
  論文  参考訳（メタデータ） (2026-02-26T15:27:53Z)
• Almost Asymptotically Optimal Active Clustering Through Pairwise Observations [59.20614082241528]
  そこで本研究では, ノイズと能動的に収集された応答を用いて, M$アイテムを未知数の$K$個別グループにクラスタリングするための新しい分析フレームワークを提案する。 クラスタリングの精度に対する望ましい信頼性を達成するのに必要なクエリ数の基本的下位境界を確立する。 我々は、一般化された同値比統計の計算可能な変種を開発し、その下限に対する性能ギャップを正確に推定できることを実証的に示す。
  論文  参考訳（メタデータ） (2026-02-05T14:16:47Z)
• Graph-based Clustering Revisited: A Relaxation of Kernel $k$-Means Perspective [73.18641268511318]
  本稿では,クラスタリング結果を導出するための正規制約のみを緩和するグラフベースのクラスタリングアルゴリズムを提案する。 二重制約を勾配に変換するために、非負の制約をクラス確率パラメータに変換する。
  論文  参考訳（メタデータ） (2025-09-23T09:14:39Z)
• Information-Theoretic Limits and Strong Consistency on Binary Non-uniform Hypergraph Stochastic Block Models [0.0]
  非一様ハイパーグラフブロックモデル(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)
• 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)

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

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