在高维特征与多层网络中，首次证明社区检测无统计-计算鸿沟。
Fundamental Limits of Community Detection in Contextual Multi-Layer Stochastic Block Models
- 结合高维特征与多层稀疏网络，设计基于装饰环与路径计数的算法。
- 在常数平均度下，给出可检测性的精确阈值，且算法达到该极限。
- 解决一关键猜想，适用于需融合多源异构数据的场景。
我们研究从高维协变量矩阵和 $L$ 个稀疏网络的联合观测中进行社区检测的问题，这些数据均以噪声和不完整的方式编码 $n$ 个主体的潜在社区标签。在平均度恒定、特征数 $p$ 与 $n$ 同阶的渐近条件下，我们推导出可实现标签检测与估计的精确阈值。结果拓展了 extcite{MN23} 在常数度情形下的工作，并在 $L$ 为常数时解决了 extcite{YLS24+} 的一个猜想。信息论下界通过伯努利与高斯矩的新比较不等式，以及受 extcite{DHSS25} 启发的统计版“恢复到卡方散度缩减”论证获得。算法方面，我们设计基于装饰环与装饰路径计数的高效算法，并证明其在检测与弱恢复上均达到尖锐阈值，表明此设定下不存在统计-计算鸿沟。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。