Phase Transition for Stochastic Block Model with more than √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 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.