Phase Transition for Stochastic Block Model with more than $\sqrtn$ Communities

Alexandra Carpentier, Christophe Giraud, Nicolas Verzelen
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:938-1000, 2026.

Abstract

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 $K\ll \sqrt{n}$, where $n$ is the number of nodes in the observed graph. When $K\geq \sqrt{n}$, Chin et al. (2025) recently proved that, in a \emph{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\geq \sqrt{n}$. In this work, we provide evidence supporting their conjecture: 1- We prove that, for \emph{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 \emph{sparse regime} considered in Chin et al. (2025), but also in \emph{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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-carpentier26a, title = {Phase Transition for Stochastic Block Model with more than $\sqrt{n}$ Communities}, author = {Carpentier, Alexandra and Giraud, Christophe and Verzelen, Nicolas}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {938--1000}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/carpentier26a/carpentier26a.pdf}, url = {https://proceedings.mlr.press/v336/carpentier26a.html}, abstract = {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 $K\ll \sqrt{n}$, where $n$ is the number of nodes in the observed graph. When $K\geq \sqrt{n}$, Chin et al. (2025) recently proved that, in a \emph{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\geq \sqrt{n}$. In this work, we provide evidence supporting their conjecture: 1- We prove that, for \emph{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 \emph{sparse regime} considered in Chin et al. (2025), but also in \emph{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. } }
Endnote
%0 Conference Paper %T Phase Transition for Stochastic Block Model with more than $\sqrtn$ Communities %A Alexandra Carpentier %A Christophe Giraud %A Nicolas Verzelen %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-carpentier26a %I PMLR %P 938--1000 %U https://proceedings.mlr.press/v336/carpentier26a.html %V 336 %X 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 $K\ll \sqrt{n}$, where $n$ is the number of nodes in the observed graph. When $K\geq \sqrt{n}$, Chin et al. (2025) recently proved that, in a \emph{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\geq \sqrt{n}$. In this work, we provide evidence supporting their conjecture: 1- We prove that, for \emph{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 \emph{sparse regime} considered in Chin et al. (2025), but also in \emph{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.
APA
Carpentier, A., Giraud, C. & Verzelen, N.. (2026). Phase Transition for Stochastic Block Model with more than $\sqrtn$ Communities. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:938-1000 Available from https://proceedings.mlr.press/v336/carpentier26a.html.

Related Material