📊 statistics

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

This paper provides evidence for a new phase transition threshold in the Stochastic Block Model with $K \geq \sqrt{n}$ communities by proving that low-degree polynomials fail below this threshold while polynomial-time recovery is achievable above it through counting specific graph motifs, extending previous results from sparse to moderately sparse regimes.

Original authors: Alexandra Carpentier, Christophe Giraud, Nicolas Verzelen

Published 2026-06-19

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Alexandra Carpentier, Christophe Giraud, Nicolas Verzelen

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a massive, chaotic party with thousands of guests. You can only see who is talking to whom (the "edges" of the graph), but you don't know who belongs to which friend group (the "communities"). Your goal is to figure out the friend groups just by looking at the conversation map.

This is the Stochastic Block Model (SBM) problem. For a long time, scientists believed there was a specific "magic line" (called the Kesten-Stigum threshold) that you had to cross to solve this puzzle quickly. If the connections between people were too weak or the groups too small, they thought it was impossible to find the groups without taking forever.

However, this paper tackles a specific, tricky scenario: What happens when there are huge numbers of friend groups? Specifically, when the number of groups is larger than the square root of the total number of people.

Here is what the authors discovered, explained simply:

1. The Old Map Was Wrong for Big Crowds

Previously, researchers thought that if you had too many groups, you needed a very strong signal (lots of conversations within groups) to find them. They believed that if the signal was just below a certain "magic line," no computer algorithm could solve the puzzle quickly.

But a recent discovery suggested that when there are many groups, you might actually be able to solve the puzzle even if the signal is weaker than that old "magic line." This paper confirms that suspicion.

2. The "Low-Degree" Limit (The Simple Calculator)

To prove that a problem is hard, mathematicians often test it against "Low-Degree Polynomials." Think of these as simple calculators that can only perform basic, short calculations. They can't do complex, deep thinking.

The authors proved that these "simple calculators" fail to find the groups if the signal is below a new, lower threshold. This suggests that the problem is indeed computationally hard for simple methods, but it doesn't mean all methods fail. It sets a new "floor" for how hard the problem is.

3. The New Solution: Counting Specific Shapes

The paper's biggest breakthrough is showing that you can solve this puzzle quickly (in polynomial time) if you use a smarter strategy than just counting simple conversations.

Instead of just looking at who talked to whom, the authors propose counting specific shapes (called "motifs") in the conversation map.

In a sparse party (few conversations): The best shape to look for is a long, winding path where no one repeats a person they've already met (a "self-avoiding path"). This is like tracing a long, non-repeating line of introductions.
In a denser party (more conversations): Long paths aren't enough. You need to look for complex, blown-up shapes. The authors invented a new shape they call a "Cycle Blow-up with Fasteners."

The "Cycle Blow-up" Analogy:
Imagine a bicycle wheel (a cycle). Now, imagine you replace every single spoke with a whole cluster of spokes (a "blow-up"). Then, you attach two special "fastener" pins to specific points on this giant wheel.

If the two people you are investigating belong to the same group, this giant, fastened wheel shape will appear in the conversation map many, many times.
If they are in different groups, this shape will almost never appear.

By counting how many of these specific, complex shapes exist, the algorithm can tell the groups apart, even when the signal is too weak for simple methods.

4. The "Phase Transition"

The paper identifies a precise "tipping point" (a phase transition).

Below the line: Even the smartest quick algorithms (and simple calculators) fail. The groups are too mixed up to separate quickly.
Above the line: By counting these specific shapes (paths for sparse parties, blown-up wheels for denser ones), you can separate the groups efficiently.

Summary

This paper proves that when you have a massive number of groups, the rules change. You don't need the signal to be as strong as previously thought. However, to find the groups, you can't just use simple math; you have to look for complex, specific patterns (like the "blown-up wheel") hidden in the network. If you count these patterns correctly, you can solve the puzzle quickly, even in conditions where it was previously thought to be impossible.

Key Takeaway: The "magic line" for solving these puzzles has moved lower for large groups, but to cross it, you need to stop looking for simple connections and start counting complex, specific shapes.

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

1. Problem Statement

The paper addresses the computational limits of community recovery in the Stochastic Block Model (SBM) when the number of communities $K$ grows with the number of nodes $n$ , specifically in the regime where $K \ge \sqrt{n}$ .

In the standard SBM, nodes are partitioned into $K$ communities, with edges generated independently based on whether nodes share a community (probability $p$ ) or not (probability $q$ ). The central task is to recover the latent community assignments from a single observed graph.

Historically, for a fixed $K$ , statistical physics conjectured a "computational barrier" known as the Kesten-Stigum (KS) threshold. Below this threshold, non-trivial recovery is information-theoretically possible but conjectured to be impossible in polynomial time. Recent work by Chin et al. (2025) challenged this view for the regime $K \gg \sqrt{n}$ in sparse graphs (where connection probabilities scale as $1/n$ ). They demonstrated that polynomial-time recovery is possible below the KS threshold by counting non-backtracking paths, proposing a new phase transition threshold:
$\lambda \gtrsim_{\log} \left( \frac{q + \lambda}{K} \right)^{1 - \log_n(K)}$
where $\lambda = p - q$ .

This paper investigates two open questions regarding this regime:

Q1: Does this new threshold hold in the sparse regime ( $q \sim 1/n$ ) for $K \ge \sqrt{n}$ ?
Q2: Where does the phase transition occur in denser regimes ( $q \gg 1/n$ ), and what algorithms are optimal there?

2. Methodology

The authors employ a dual approach combining Low-Degree Polynomial (LDP) lower bounds and constructive algorithmic upper bounds based on motif counting.

2.1. Low-Degree Polynomial Lower Bounds

To establish computational hardness, the authors analyze the performance of estimators restricted to polynomials of degree $D = O(\log n)$ . The LDP conjecture posits that if degree- $O(\log n)$ polynomials fail to solve a problem, no polynomial-time algorithm can succeed.

Objective: Instead of directly outputting a partition (a combinatorial task), the authors focus on estimating the centered membership matrix entries $x_{ij} = \mathbb{1}\{z_i = z_j\} - 1/K$ .
Technique: They construct an almost-orthonormal basis for permutation-invariant polynomials. Unlike previous works that used simple proxies for normalization, this paper introduces a refined normalization strategy based on the exact second moments of the polynomials.
Key Insight: By analyzing the correlation between basis elements (motifs), they derive a precise condition under which the correlation between any degree- $D$ polynomial and the target $x_{ij}$ vanishes. This condition defines a critical value $\lambda_c$ .

2.2. Algorithmic Upper Bounds via Motif Counting

To prove that recovery is possible above the derived threshold, the authors design algorithms based on counting specific graph motifs (subgraphs) attached to a pair of nodes $(i, j)$ .

Strategy: The algorithm counts occurrences of a specific motif $G$ involving nodes $i$ and $j$ . If $i$ and $j$ are in the same community, the count is significantly higher than if they are in different communities.
Motif Selection: The optimal motif depends on the density regime $q \sim n^{-\alpha}$ $q \sim n^{- α}$ .
- For specific rational densities, simple motifs like cliques or self-avoiding paths suffice.
- For general rational densities, the authors construct complex motifs called "cycle blow-ups with fasteners." These are formed by taking a cycle, "blowing up" each node into a layer of vertices, and connecting the target nodes $i$ and $j$ to these layers via "fastener" edges.
Post-Processing: To ensure concentration and polynomial-time complexity, the authors employ a Median-of-Means (MoM) procedure. They partition the graph into disjoint subsets, compute the motif count on each subset, and take the median of these counts to estimate the community relationship.

3. Key Contributions and Results

Contribution 1: A Tight LDP Lower Bound

The authors prove that for any graph density, low-degree polynomials fail to recover communities below the threshold $\lambda_c$ defined by:
$\sup_{r \ge 1} \frac{n \lambda_c^{2r}}{K \lambda_c^r + K^2 \bar{q}^r} = 1$
where $\bar{q} = q(1-q)$ .

Regime $K \le \sqrt{n}$ : The maximum is achieved at $r=1$ , recovering the standard Kesten-Stigum threshold.
Regime $K \ge \sqrt{n}$ : The maximum is achieved at $r > 1$ . In the sparse regime ( $q \sim 1/n$ ), this threshold matches the one conjectured by Chin et al. (2025) up to poly-logarithmic factors. In denser regimes, it provides a new lower bound for polynomial-time recovery.

Contribution 2: Successful Recovery via Motif Counts

The authors prove that community recovery is possible in polynomial time above the threshold $\lambda_c$ by counting specific motifs.

Sparse Regime ( $q \sim 1/n$ ): Recovery is achieved by counting non-backtracking paths (or self-avoiding paths of length $\log n$ ), confirming the results of Chin et al. (2025).
Moderately Sparse/Dense Regimes ( $q \sim n^{-\alpha}$ ):
- If $q \sim n^{-2/(m+1)}$ , recovery is possible by counting $m$ -cliques.
- If $q \sim n^{-(m-2)/(m-1)}$ , recovery is possible by counting self-avoiding paths of length $m-1$ .
- For general rational exponents, the cycle blow-up with fasteners motif is optimal.
Result: For $q \sim n^{-\alpha}$ with $\alpha \in (0, 1] \cap \mathbb{Q}$ , the phase transition for weak recovery in polynomial time occurs at the level $\lambda_c$ (up to poly-log factors).

4. Significance and Claims

The paper claims to provide strong evidence supporting the conjecture by Chin et al. (2025) regarding the phase transition in the many-communities regime ( $K \ge \sqrt{n}$ ).

Unification of Regimes: The work unifies the understanding of computational barriers across different density regimes. It demonstrates that while non-backtracking paths are optimal in the sparse regime, more complex motifs (like cliques or cycle blow-ups) become necessary and optimal as the graph becomes denser.
Optimality of Motifs: The paper establishes a direct link between the density parameter $\alpha$ and the geometry of the optimal motif. It shows that the "shape" of the optimal algorithm changes with the sparsity of the graph.
Limitations and Open Questions:
- The authors acknowledge that their bounds involve poly-logarithmic factors that do not match exactly (the upper and lower bounds are not sharp in terms of constants).
- They note that for irrational density exponents, the recovery is possible via polynomials of degree $O(\log n / \log \log n)$ , but it remains an open question whether such polynomials can be computed in strict polynomial time.
- The exact location of the phase transition (sharp vs. coarse) and the existence of algorithms with sharp constants remain open questions.

In summary, the paper rigorously characterizes the computational threshold for community recovery when $K \ge \sqrt{n}$ , proving that the barrier is determined by the interplay between the number of communities, the graph density, and the complexity of the motifs required to detect them.