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

2026-06-19 · Source: stat.ML updates on arXiv.org · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Data Science & Analytics, Mathematics & Computational Sciences · Depth: Expert, extended

Summary

This research investigates the phase transition for community recovery in the Stochastic Block Model (SBM) when the number of communities, K, is greater than or equal to the square root of the number of nodes, √n. It provides strong evidence confirming a new threshold conjectured by Chin et al. (2025). Specifically, the authors prove that low-degree polynomials fail to recover communities below this new threshold, λ ≲ᴼₚₚ(ĭ + λ/K)^(1-log_n(K)), across all graph densities. Conversely, they demonstrate that polynomial-time community recovery is possible above this threshold in certain moderately sparse regimes, specifically when the inter-community connection probability ĭ scales as n^(-2/(m+1)) for m ∈ {3,4,5,…}. This recovery is achieved using an algorithm based on m-clique counting combined with a Median-of-Means layer.

Key takeaway

For research scientists developing community detection algorithms for large-scale networks, this work highlights a critical shift in computational feasibility when the number of communities K exceeds √n. You should investigate clique-counting methods, particularly for moderately sparse regimes where ĭ ≈ n^(-2/(m+1)), as they offer polynomial-time recovery above the new theoretical threshold. This suggests moving beyond traditional low-degree polynomial approaches in such "many communities" scenarios.

Key insights

A new phase transition threshold governs SBM community recovery when K ≥ √n, confirmed by low-degree hardness and clique-counting success.

Principles

• Computational hardness for SBM community recovery shifts significantly when K ≥ √n.
• Low-degree polynomials fail to recover communities below the Chin et al. (2025) threshold.
• Clique counting enables polynomial-time recovery above this threshold in specific sparse regimes.

Method

Community recovery is achieved by counting m-cliques in a modified graph, combined with a Median-of-Means layer for robust estimation of node co-community probabilities.

In practice

• Consider clique-counting algorithms for SBM community recovery when K ≥ √n.
• Optimal algorithms depend on graph density, e.g., m-cliques for ĭ ≈ n^(-2/(m+1)).

Topics

• Stochastic Block Model
• Community Detection
• Phase Transitions
• Computational Hardness
• Clique Counting
• Low-Degree Polynomials

Best for: AI Scientist, Research Scientist

Related on AIssential

• Achieving the Kesten-Stigum bound in the non-uniform hypergraph stochastic block model — Combining subcritical hypergraph layers can enable weak recovery if their aggregate signal-to-noise ratio surpasses a Kesten–Stigum-type bound.
• Alcmean's: Unsupervised community detection using local Laplacian, automatic detection of the number of centers — ALCMeans automatically detects communities in complex networks by combining Laplacian energy with DeepWalk embeddings, outperforming traditional methods.
• A Topological Characterization of Graph Neural Networks via Stochastic Block Model Embeddings on the n-Sphere — A topological framework characterizes GNNs via SBM embeddings on an n-sphere, creating low-dimensional "fingerprints" for model comparison and transfer learning.
• Two-way Node Popularity Model for Directed and Bipartite Networks — TNPM enhances community detection in complex networks by integrating node popularity and diverse edge distributions.
• Finite-Time Queue Peak Laws in Stochastic Networks: Logarithmic Scaling After Geometric Thresholds — Queue peaks in stochastic networks exhibit logarithmic growth after a geometric threshold, driven by self-normalization.
• A Parameter-free Adaptive Resonance Theory-based Topological Clustering Algorithm Capable of Continual Learning — A new ART-based clustering algorithm autonomously estimates critical parameters for superior, adaptive performance.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by stat.ML updates on arXiv.org.