Phase Transition for Stochastic Block Model with more than $\sqrt{n}$ Communities
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912692709621760 |
|---|---|
| author | Carpentier, Alexandra Giraud, Christophe Verzelen, Nicolas |
| author_facet | Carpentier, Alexandra Giraud, Christophe Verzelen, Nicolas |
| contents | Predictions from statistical physics postulate that recovery of the communities in Stochastic Block Model (SBM) 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, as long as the number $K$ of communities remains smaller than $\sqrt{n}$, where $n$ is the number of nodes in the observed graph. Failure of low-degree polynomials below the KS threshold was also proven when $K=o(\sqrt{n})$.
When $K\geq \sqrt{n}$, Chin et al.(2025) recently prove that, in a sparse regime, community recovery in polynomial time is possible below the KS threshold by counting non-backtracking paths. This breakthrough result lead them to postulate a new threshold for the many communities regime $K\geq \sqrt{n}$. In this work, we provide evidences that confirm their conjecture for $K\geq \sqrt{n}$:
1- We prove that, for any density of the graph, low-degree polynomials 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 of~Chin et al., but also in some (but not all) moderately sparse regimes by essentially by counting occurrences of cliques or self-avoiding paths of suitable size in the observed graph.
In addition, we propose a detailed conjecture regarding the structure of motifs that are optimal in sparsity regimes not covered by cliques or self-avoiding paths counting. 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. Other motif counts--unrelated to spectral properties--should be considered in denser regimes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_15822 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Phase Transition for Stochastic Block Model with more than $\sqrt{n}$ Communities Carpentier, Alexandra Giraud, Christophe Verzelen, Nicolas Machine Learning Probability Statistics Theory Predictions from statistical physics postulate that recovery of the communities in Stochastic Block Model (SBM) 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, as long as the number $K$ of communities remains smaller than $\sqrt{n}$, where $n$ is the number of nodes in the observed graph. Failure of low-degree polynomials below the KS threshold was also proven when $K=o(\sqrt{n})$. When $K\geq \sqrt{n}$, Chin et al.(2025) recently prove that, in a sparse regime, community recovery in polynomial time is possible below the KS threshold by counting non-backtracking paths. This breakthrough result lead them to postulate a new threshold for the many communities regime $K\geq \sqrt{n}$. In this work, we provide evidences that confirm their conjecture for $K\geq \sqrt{n}$: 1- We prove that, for any density of the graph, low-degree polynomials 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 of~Chin et al., but also in some (but not all) moderately sparse regimes by essentially by counting occurrences of cliques or self-avoiding paths of suitable size in the observed graph. In addition, we propose a detailed conjecture regarding the structure of motifs that are optimal in sparsity regimes not covered by cliques or self-avoiding paths counting. 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. Other motif counts--unrelated to spectral properties--should be considered in denser regimes. |
| title | Phase Transition for Stochastic Block Model with more than $\sqrt{n}$ Communities |
| topic | Machine Learning Probability Statistics Theory |
| url | https://arxiv.org/abs/2509.15822 |