# Phase Transition for Stochastic Block Model with more than √n Communities arXiv: https://arxiv.org/abs/2509.15822 · HTML: https://mlsanity.com/paper/2509.15822/ ## Key facts - Cited by 3 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 19 Sep 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, 3 of 3) - [Algorithmic Contiguity from Low-Degree Heuristic II: Predicting Detection-Recovery Gaps](https://mlsanity.com/paper/2604.17410/) (2026) - [Sharp Low-Degree Thresholds for Planted-vs-Planted Testing](https://mlsanity.com/paper/2606.05266/) (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) Predictions from statistical physics postulate that recovery of the communities in the Stochastic Block Model (SBM) with a fixed number K of communities is possible in polynomial time above, and only above, the Kesten-Stigum (KS) threshold. This conjecture has given rise to a rich literature, proving that non-trivial community recovery is indeed possible in SBM above the KS threshold. Failure of low-degree polynomials (LDP) below the KS threshold was also proven, as long as Kll √n, where n is the number of nodes in the observed graph. When K≥ √n, Chin et al.(2025) recently proved that, in a sparse regime, community recovery in polynomial time is possible below the KS threshold by counting non-backtracking paths. This breakthrough led them to postulate a new threshold for the many-communities regime K≥ √n. In this work, we provide evidence supporting their conjecture: 1- We prove that, for any graph density, LDP fail to recover communities below the threshold postulated by Chin et al.(2025) ; 2- We prove that community recovery is possible in polynomial time above the postulated threshold, not only in the sparse regime considered in Chin et al.~(2025), but also in moderately sparse regimes, by counting occurrences of some specific motifs inspired by the LDP analysis. In particular, counting self-avoiding paths of length log(n), which is closely related to spectral algorithms based on the Non-Backtracking operator, is optimal only in the sparse regime. More complex motifs based on the blow-up of a cycle must be considered in denser regimes.