Phase Transition for Stochastic Block Model with more than $\sqrt{n}$ Communities

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 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 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.