# Fundamental Limits of Community Detection in Contextual Multi-Layer Stochastic Block Models

arXiv: https://arxiv.org/abs/2602.08173 · HTML: https://mlsanity.com/paper/2602.08173/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 44 references that are in the map.
- First posted on arXiv 9 Feb 2026.

## Builds on (most cited first, 20 of 20)

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Contextual Stochastic Block Models](https://mlsanity.com/paper/1807.09596/) (2018)
- [Spectral redemption: clustering sparse networks](https://mlsanity.com/paper/1306.5550/) (2013)
- [Community detection thresholds and the weak Ramanujan property](https://mlsanity.com/paper/1311.3085/) (2013)
- [A Proof Of The Block Model Threshold Conjecture](https://mlsanity.com/paper/1311.4115/) (2013)
- [Achieving Optimal Misclassification Proportion in Stochastic Block Model](https://mlsanity.com/paper/1505.03772/) (2015)
- [Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models](https://mlsanity.com/paper/1807.00891/) (2018)
- [Spectral and matrix factorization methods for consistent community detection in multi-layer networks](https://mlsanity.com/paper/1704.07353/) (2017)
- [Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs](https://mlsanity.com/paper/1501.06087/) (2015)
- [Testing for high-dimensional geometry in random graphs](https://mlsanity.com/paper/1411.5713/) (2014)
- [Minimax Rates of Community Detection in Stochastic Block Models](https://mlsanity.com/paper/1507.05313/) (2015)
- [Contextual Stochastic Block Model: Sharp Thresholds and Contiguity](https://mlsanity.com/paper/2011.09841/) (2020)
- [Testing network correlation efficiently via counting trees](https://mlsanity.com/paper/2110.11816/) (2021)
- [Optimal hypothesis testing for stochastic block models with growing degrees](https://mlsanity.com/paper/1705.05305/) (2017)
- [Global and Individualized Community Detection in Inhomogeneous Multilayer Networks](https://mlsanity.com/paper/2012.00933/) (2020)
- [General Community Detection with Optimal Recovery Conditions for Multi-relational Sparse Networks with Dependent Layers](https://mlsanity.com/paper/2004.03480/) (2020)
- [Fundamental limits of community detection from multi-view data: multi-layer, dynamic and partially labeled block models](https://mlsanity.com/paper/2401.08167/) (2024)
- [Exact Phase Transitions for Stochastic Block Models and Reconstruction on Trees](https://mlsanity.com/paper/2212.03362/) (2022)
- [Weak recovery, hypothesis testing, and mutual information in stochastic block models and planted factor graphs](https://mlsanity.com/paper/2406.15957/) (2024)
- [The Algorithmic Phase Transition in Correlated Spiked Models](https://mlsanity.com/paper/2511.06040/) (2025)

## Built on by (most cited first, 2 of 2)

- [Algorithmic Contiguity from Low-Degree Heuristic II: Predicting Detection-Recovery Gaps](https://mlsanity.com/paper/2604.17410/) (2026)
- [Achieving the Kesten-Stigum bound in the non-uniform hypergraph stochastic block model](https://mlsanity.com/paper/2604.20907/) (2026)

## Abstract (arXiv)

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 citeMN23 to the constant-degree regime with noisy measurements, and also resolve a conjecture in citeYLS24+ 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 citeDHSS25. 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.