# Phase Transition for Stochastic Block Model with more than √n Communities (II) arXiv: https://arxiv.org/abs/2511.21526 · HTML: https://mlsanity.com/paper/2511.21526/ ## Key facts - Cited by 4 papers in the map (data through 14 Oct 2026). - Builds on 24 of its 35 references that are in the map. - First posted on arXiv 26 Nov 2025. ## Builds on (most cited first, 24 of 24) - [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017) - [Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio](https://mlsanity.com/paper/1907.11636/) (2019) - [Spectral redemption: clustering sparse networks](https://mlsanity.com/paper/1306.5550/) (2013) - [The power of sum-of-squares for detecting hidden structures](https://mlsanity.com/paper/1710.05017/) (2017) - [Reducibility and Statistical-Computational Gaps from Secret Leakage](https://mlsanity.com/paper/2005.08099/) (2020) - [Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent](https://mlsanity.com/paper/2009.06107/) (2020) - [Community detection thresholds and the weak Ramanujan property](https://mlsanity.com/paper/1311.3085/) (2013) - [Subexponential-Time Algorithms for Sparse PCA](https://mlsanity.com/paper/1907.11635/) (2019) - [Computational Barriers to Estimation from Low-Degree Polynomials](https://mlsanity.com/paper/2008.02269/) (2020) - [A Proof Of The Block Model Threshold Conjecture](https://mlsanity.com/paper/1311.4115/) (2013) - [Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure](https://mlsanity.com/paper/1806.07508/) (2018) - [Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices](https://mlsanity.com/paper/1402.1267/) (2014) - [Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs](https://mlsanity.com/paper/1501.06087/) (2015) - [The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness](https://mlsanity.com/paper/1702.00467/) (2017) - [Computational Complexity of Statistics: New Insights from Low-Degree Polynomials](https://mlsanity.com/paper/2506.10748/) (2025) - [Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs](https://mlsanity.com/paper/2008.12237/) (2020) - [Low-degree lower bounds via almost orthonormal bases](https://mlsanity.com/paper/2509.09353/) (2025) - [Sharp Phase Transitions in Estimation with Low-Degree Polynomials](https://mlsanity.com/paper/2502.14407/) (2025) - [Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials](https://mlsanity.com/paper/2308.15728/) (2023) - [Stochastic block models with many communities and the Kesten--Stigum bound](https://mlsanity.com/paper/2503.03047/) (2025) - [Computational lower bounds in latent models: clustering, sparse-clustering, biclustering](https://mlsanity.com/paper/2506.13647/) (2025) - [Community detection with the Bethe-Hessian](https://mlsanity.com/paper/2411.02835/) (2024) - [Low coordinate degree algorithms II: Categorical signals and generalized stochastic block models](https://mlsanity.com/paper/2412.21155/) (2024) - [Low degree conjecture implies sharp computational thresholds in stochastic block model](https://mlsanity.com/paper/2502.15024/) (2025) ## Built on by (most cited first, 4 of 4) - [Statistical-computational gap in multiple Gaussian graph alignment](https://mlsanity.com/paper/2512.00610/) (2025) - [Graph energy as a measure of community detectability in networks](https://mlsanity.com/paper/2601.05065/) (2026) - [Low-degree Lower bounds for clustering in moderate dimension](https://mlsanity.com/paper/2602.23023/) (2026) - [Slow Beats Fast at the Kesten-Stigum Threshold: Minimax, Fisher-Information and Belief-Propagation Characterizations of the Information-Computation Gap in Sparse Stochastic Block Models](https://mlsanity.com/paper/2610.08872/) (2026) ## Abstract (arXiv) A fundamental theoretical question in network analysis is to determine under which conditions community recovery is possible in polynomial time in the Stochastic Block Model (SBM). When the number K of communities remains smaller than √n --where n denotes the number of nodes--, non-trivial community recovery is possible in polynomial time above, and only above, the Kesten--Stigum (KS) threshold, originally postulated using arguments from statistical physics. When K ≥ √n, Chin, Mossel, Sohn, and Wein recently proved that, in the sparse regime, community recovery in polynomial time is achievable below the KS threshold by counting non-backtracking paths. This finding led them to postulate a new threshold for the many-communities regime K ≥ √n. Subsequently, Carpentier, Giraud, and Verzelen established the failure of low-degree polynomials below this new threshold across all density regimes, and demonstrated successful recovery above the threshold in certain moderately sparse settings. While these results provide strong evidence that, in the many community setting, the computational barrier lies at the threshold proposed in~Chin et al., the question of achieving recovery above this threshold still remains open in most density regimes. The present work is a follow-up to~Carpentier et al., in which we prove Conjecture~1.4 stated therein by: 1- Constructing a family of motifs satisfying specific structural properties; and 2- Proving that community recovery is possible above the proposed threshold by counting such motifs. Our results complete the picture of the computational barrier for community recovery in the SBM with K ≥ √n communities. They also indicate that, in moderately sparse regimes, the optimal algorithms appear to be fundamentally different from spectral methods.