文脈付きマルチレイヤー確率ブロックモデルにおけるコミュニティ検出の根本的な限界

arXiv:2602.08173v1 告知タイプ: cross 要約：高次元共変行列と $L$ つの疎ネットワークの同時観察からコミュニティ検出の問題を検討する。これらは、$n$ 人の被験者の潜在コミュニティラベルに関する noisy な部分的な情報を符号化する。ネットワークの平均度数が一定である漸近的な制約において、特徴量の数 $p$ が $n$ に比例して増加する場合、被験者ラベルを検出・推定可能なためのシャープな閾値を導出した。当社の結果は、 extcite{MN23} の作業を一定度数の制約下、ノイズ測定を含むケースに拡張し、またネットワークの数が一定である場合において extcite{YLS24+} の仮説も解決した。 当社の情報理論的下限は、ベルヌーイ分布とガウス分布のモーメント間の新しい比較不等式、および extcite{DHSS25} へのインスピレーションに基づく「回復からカイ二乗偏差の減少への」引数の統計的バリエーションを用いて得られた。アルゴリズムの側面では、装飾付きサイクルと装飾付きパスに基づく効率の良いアルゴリズムを設計し、検出および弱い回復の両方においてシャープな閾値を達成することが証明された。特には、当社の結果はこの設定において統計的・計算論的なギャップが存在しないことを示している。

arXiv:2602.08173v1 Announce Type: cross 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.