論文の概要: Fundamental Limits of Community Detection in Contextual Multi-Layer Stochastic Block Models

• arxiv url: http://arxiv.org/abs/2602.08173v1
• Date: Mon, 09 Feb 2026 00:27:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-10 20:26:25.013044
• Title: Fundamental Limits of Community Detection in Contextual Multi-Layer Stochastic Block Models
• Title（参考訳）: 文脈的マルチ階層確率ブロックモデルにおけるコミュニティ検出の基礎的限界
• Authors: Shuyang Gong, Dong Huang, Zhangsong Li,
• Abstract要約: 高次元共変量行列と$L$スパースネットワークの合同観測からコミュニティ検出の問題を考える。 ネットワークの平均等級が一定であり,特徴数$p$が$n$に比例して増加するスパース体制では,対象ラベルの検出と推定が可能なシャープしきい値が導出される。 以上の結果から,この設定には統計的・計算的ギャップが存在しないことが示唆された。
• 参考スコア（独自算出の注目度）: 4.312207944236305
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of community detection from the joint observation of a high-dimensional covariate matrix and $L$ sparse networks, all encoding noisy, partial information about the latent community labels of $n$ subjects. In the asymptotic regime where the networks have constant average degree and the number of features $p$ grows proportionally with $n$, we derive a sharp threshold under which detecting and estimating the subject labels is possible. Our results extend the work of \cite{MN23} to the constant-degree regime with noisy measurements, and also resolve a conjecture in \cite{YLS24+} when the number of networks is a constant. Our information-theoretic lower bound is obtained via a novel comparison inequality between Bernoulli and Gaussian moments, as well as a statistical variant of the ``recovery to chi-square divergence reduction'' argument inspired by \cite{DHSS25}. On the algorithmic side, we design efficient algorithms based on counting decorated cycles and decorated paths and prove that they achieve the sharp threshold for both detection and weak recovery. In particular, our results show that there is no statistical-computational gap in this setting.
• Abstract（参考訳）: 我々は,高次元共変量行列と$L$スパースネットワークの合同観測からコミュニティ検出の問題を考える。 ネットワークの平均等級が一定であり,特徴数$p$が$n$に比例して増加する漸近的状態においては,対象ラベルの検出と推定が可能なシャープしきい値が導出される。 この結果から, ネットワーク数が定数である場合, 共振器内の予想を解くことができる。 我々の情報理論の下限は、ベルヌーイとガウスモーメントの新たな比較不等式、および \cite{DHSS25} に着想を得た ''' の統計変種によって得られる。 アルゴリズム側では、装飾された周期と装飾された経路を数えた上で効率的なアルゴリズムを設計し、検出と弱い回復の両方において鋭いしきい値を達成することを証明した。 特に,本研究の結果は,この設定に統計的・計算的ギャップがないことを示している。

関連論文リスト

• Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
  本稿では,誤差確率の指数的減衰を保証し,最適な腕識別のための新しいアルゴリズムを提案する。 我々は,複雑性のレベルが異なる様々な問題インスタンスに対する包括的経験的評価を通じて,アルゴリズムの有効性を検証する。
  論文  参考訳（メタデータ） (2025-06-03T02:56:26Z)
• Robust Graph-Based Semi-Supervised Learning via $p$-Conductances [49.0776396776252]
  本研究では,データラベルが不足している,あるいは破損しているような状況下でのグラフに対する半教師付き学習の課題について検討する。 我々は、$p$-laplace と Poisson の学習方法を一般化した $p$-conductance learning という手法を提案する。 コンピュータビジョンと引用データセットの実証実験結果から,本手法が低ラベルレート, 劣化ラベル, 部分ラベルレジームにおける最先端の精度を実現することを示す。
  論文  参考訳（メタデータ） (2025-02-13T01:11:25Z)
• Information-Theoretic Thresholds for Planted Dense Cycles [52.076657911275525]
  本研究では,社会科学や生物科学においてユビキタスな小世界ネットワークのランダムグラフモデルについて検討する。 植え込み高密度サイクルの検出と回復の両面において、情報理論の閾値を$n$, $tau$、エッジワイド信号対雑音比$lambda$で特徴づける。
  論文  参考訳（メタデータ） (2024-02-01T03:39:01Z)
• Semi-Supervised Clustering of Sparse Graphs: Crossing the Information-Theoretic Threshold [3.6052935394000234]
  ブロックモデルは、ネットワーク構造データのクラスタリングとコミュニティ検出のための標準ランダムグラフモデルである。 ネットワークトポロジに基づく推定器は、モデルパラメータが一定の閾値以下である場合、スパースグラフの確率よりも大幅に向上する。 パラメータ領域全体でラベルの任意の部分で実現可能であることを示す。
  論文  参考訳（メタデータ） (2022-05-24T00:03:25Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  クラスタリングは教師なし学習における基本的なプリミティブである。 最近の研究は、低次手法のクラスに対する低い境界を確立している。 意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
  論文  参考訳（メタデータ） (2021-12-07T18:50:17Z)
• A Unifying Theory of Thompson Sampling for Continuous Risk-Averse Bandits [91.3755431537592]
  本稿では,多腕バンディット問題に対するリスク-逆トンプソンサンプリングアルゴリズムの解析を統一する。 大規模偏差理論における収縮原理を用いることで、連続リスク汎関数に対する新しい濃度境界が証明される。 リスク関数の幅広いクラスと「ニセ」関数が連続性条件を満たすことを示す。
  論文  参考訳（メタデータ） (2021-08-25T17:09:01Z)
• Quantitative Propagation of Chaos for SGD in Wide Neural Networks [39.35545193410871]
  本稿では,SGD(Gradient Descent)の連続時間動作の制限挙動について検討する。 本研究では, この連続時間力学によって定義される粒子系に対して, 異なるシナリオ下での「カオスの伝播」を示す。 最小化問題の暗黙的な正則化版に対応する2つの平均場限界を求める。
  論文  参考訳（メタデータ） (2020-07-13T12:55:21Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)

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

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