Fundamental Limits of Community Detection in Contextual Multi-Layer Stochastic Block Models
This work addresses fundamental limits in community detection for multi-layer data, extending prior results to more realistic noisy and sparse settings, which is incremental but important for network analysis applications.
The paper tackles the problem of community detection from noisy, high-dimensional covariates and sparse networks, deriving a sharp threshold for detection and estimation in the constant-degree regime and showing that efficient algorithms achieve this threshold without a statistical-computational gap.
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.