A computational transition for detecting correlated stochastic block models by low-degree polynomials

This paper establishes that low-degree polynomial tests can distinguish between correlated sparse stochastic block models and independent Erdős-Rényi graphs if and only if the subsampling probability exceeds the minimum of Otter's constant and the Kesten-Stigum threshold, thereby identifying a sharp computational transition for detection and partial recovery.

The Gist

Imagine you are a detective trying to solve a mystery involving two massive, messy social networks. Let's call them Network A and Network B.

The Mystery: Are They Related?

In the world of this paper, these networks are generated by a hidden "parent" network.

• The "Good" Scenario (Correlated): Imagine a parent network where people are grouped into secret clubs (Communities). Then, we create Network A and Network B by taking a random snapshot of this parent. Because they come from the same source, A and B share some hidden structure. If you look closely, you might see that the same "cliques" of friends appear in both, even if the names are shuffled.
• The "Bad" Scenario (Independent): Now imagine Network A and Network B were created completely separately, like two different parties thrown by different organizers with no overlap. They just happen to have the same number of people and roughly the same number of friendships, but there is no deep connection between them.

The Goal: Your job is to look at Network A and Network B and say, "These two are related!" or "These two are strangers!"

The Challenge: The "Low-Degree" Detective

The paper asks a very specific question: How smart does your detective tool need to be to solve this?

The authors focus on a specific type of tool called Low-Degree Polynomials.

• The Analogy: Think of a low-degree polynomial as a detective who can only look at small, simple patterns. They can count triangles (three friends all knowing each other), squares (four friends in a loop), or small trees. They are not allowed to look at the entire network at once or run a super-complex simulation that takes a million years. They are limited to "quick glances" at small groups.

The paper asks: Can these "quick-glance" detectives solve the mystery, or do they need a supercomputer (high-degree polynomials) to do it?

The Big Discovery: The "Tipping Point"

The authors found a precise tipping point (a threshold) that separates the "Easy" case from the "Impossible" case for these simple detectives.

There are two main factors that determine if the mystery is solvable:

1. The "Club" Strength ($\epsilon$): How clearly defined are the secret clubs? If the clubs are very distinct, it's easier to spot them.
2. The "Snapshot" Size ($s$): How much of the parent network did we keep? If we kept a huge chunk, the connection is obvious. If we only kept a tiny, sparse fragment, it's hard to see.

The paper proves that the simple detectives can solve the mystery if and only if the snapshot size ($s$) is larger than a specific number. This number is the smaller of two famous thresholds:

1. The "Tree" Threshold ($\sqrt{\alpha}$): This is related to how many trees grow in a forest. If the network is too sparse, the "trees" (connections) are too small to give clues. This constant is roughly 0.338.
2. The "Signal" Threshold ($1/\lambda\epsilon^2$): This is the famous Kesten-Stigum threshold. It's the point where the "signal" (the club structure) is strong enough to rise above the "noise" (random friendships).

The Verdict:

• If you are above the line: The simple detectives (low-degree polynomials) can easily count the small patterns (like trees) and shout, "Aha! These networks are related!"
• If you are below the line: The simple detectives are completely blind. No matter how many small patterns they count, they cannot tell the difference between the related networks and the random ones. The paper suggests that to solve it below this line, you would need a "super-detective" (an algorithm that takes exponential time, essentially forever).

Why is this hard? (The "Bad" Graphs)

Why is proving this so difficult? The authors had to deal with some tricky "glitches" in the math.

• The "Dense" Glitch: Sometimes, by pure chance, a small part of the network looks incredibly crowded (too many edges). This confuses the math, making it look like there's a signal when there isn't.
• The "Cycle" Glitch: Small loops (like a triangle of friends) can also mess up the calculations.

The authors had to invent a clever way to ignore these glitches. They essentially said, "Let's pretend these weird, crowded, or loop-heavy graphs don't exist." They proved that if you ignore these rare, weird cases, the math works perfectly. This is like a detective saying, "I will only solve the case if we ignore the one-in-a-million scenario where the suspect is a time traveler."

The "Otter's Constant" and the "Otter"

You might see a reference to Otter's constant ($\alpha \approx 0.338$).

• The Metaphor: Imagine a forest of trees (the network). There is a critical density where the trees start connecting to form a giant, continuous forest. Below this density, the trees are just isolated islands.
• The Otter: In the world of graph theory, this constant is named after a mathematician named Otter. It represents the point where the "forest" of connections becomes big enough to traverse. If your network is too sparse (below this constant), the "forest" is just a bunch of isolated bushes, and you can't walk from one side to the other to find the hidden pattern.

Summary in Plain English

This paper is about finding the limit of human (or simple computer) intuition when trying to find hidden connections in messy data.

1. The Setup: We have two social networks. Are they twins (related) or strangers (random)?
2. The Tool: We use simple tools that only look at small groups of friends (counting triangles, trees, etc.).
3. The Result: There is a sharp line.
   • Above the line: Simple tools work perfectly.
   • Below the line: Simple tools fail completely. You would need a super-computer that runs for billions of years to solve it.
4. The Takeaway: Sometimes, the information is there, but it's hidden so deeply in the noise that our best "efficient" methods just can't see it. The paper maps out exactly where that line is drawn for this specific type of network problem.

It's a bit like trying to hear a whisper in a hurricane. If the whisper is loud enough (above the threshold), you can hear it. If it's too quiet (below the threshold), no amount of simple listening will help; you'd need a super-sensitive microphone that takes forever to build.

Technical Summary

Here is a detailed technical summary of the paper "A computational transition for detecting correlated stochastic block models by low-degree polynomials" by Guanyi Chen, Jian Ding, Shuyang Gong, and Zhangsong Li.

1. Problem Statement

The paper addresses the fundamental statistical and computational problem of detecting correlation between a pair of random graphs. Specifically, the authors consider the Correlated Stochastic Block Model (CSBM) in the sparse regime (constant average degree).

• Model Definition:
  • A parent graph $G$ is sampled from a Stochastic Block Model (SBM) $S(n, \lambda/n; k, \epsilon)$ with $k$ symmetric communities, average degree $\lambda = O(1)$, and a divergence parameter $\epsilon$.
  • Two observed graphs, $A$ and $B$, are generated by subsampling $G$ with probability $s$ and applying a latent vertex permutation $\pi^*$ to $B$.
  • Hypothesis Testing: The goal is to distinguish between:
    • Null Hypothesis ($Q_n$): $A$ and $B$ are independent Erdős-Rényi graphs with edge density $\lambda s/n$.
    • Alternative Hypothesis ($P_n$): $A$ and $B$ are correlated CSBMs as defined above.
• Objective: Determine the computational threshold for this detection problem, specifically focusing on algorithms restricted to low-degree polynomials of the adjacency matrix entries. This class is widely accepted as a proxy for polynomial-time algorithms in high-dimensional inference.

2. Methodology

The authors employ the Low-Degree Polynomial (LDP) framework, which analyzes the power of algorithms based on polynomials of degree $D = o(\log n)$. The methodology involves two main components:

A. Algorithmic Upper Bound (Easy Regime)

To show detection is possible when $s$ is large, the authors construct a specific low-degree polynomial test based on counting trees.

• Statistic: They define a polynomial $f_T$ that counts the number of isomorphic copies of unlabeled trees in the "centered" adjacency matrices (subtracting the expected edge density).
• Analysis: They prove that under the planted model $P_n$, the expectation of this statistic is significantly higher than under the null model $Q_n$, while the variance remains controlled, provided $s$ exceeds a certain threshold.
• Key Insight: The test leverages the fact that in the correlated model, common tree structures appear more frequently due to the shared parent graph and the latent permutation.

B. Hardness Lower Bound (Hard Regime)

To prove that detection is computationally hard when $s$ is small, they use the Low-Degree Likelihood Ratio (LDLR) method.

• Challenge: In standard SBM settings, the second moment of the likelihood ratio often diverges due to "bad" events (e.g., graphs with atypically high density or small cycles). In the CSBM setting, this is exacerbated by the latent permutation and community structure.
• Conditional Low-Degree Argument:
  1. Truncation: The authors define a "good event" $E$ where the parent graph $G$ contains no "bad" subgraphs (atypically dense subgraphs) and no small cycles (length $\le N$). They show $P(E) > 0$.
  2. Modified Measure: They construct a new probability measure $P'$ that is statistically indistinguishable from the conditional measure $P(\cdot | E)$ but simplifies the analysis. This involves removing edges from "bad" subgraphs in the parent graph.
  3. Admissible Polynomials: They restrict the analysis to "admissible polynomials" (those corresponding to admissible graphs) and show that the low-degree likelihood ratio under $P'$ is bounded.
  4. Cancellation: A crucial technical innovation is handling the conditional expectation involving the latent permutation $\pi^*$. They utilize sophisticated combinatorial cancellations and the independence of edges in the conditioned model to bound the moments.

3. Key Contributions

1. Sharp Computational Threshold: The paper establishes a sharp transition for low-degree polynomial tests. Detection is possible if and only if:
   $$s > \min\left\{ \sqrt{\alpha}, \frac{1}{\lambda \epsilon^2} \right\}$$
   where:
   • $\alpha \approx 0.338$ is Otter's constant (related to the number of unlabeled trees).
   • $\frac{1}{\lambda \epsilon^2}$ is the Kesten-Stigum (KS) threshold (the information-theoretic threshold for community detection in a single SBM).
2. Novel Conditional Argument: The authors develop a refined conditional low-degree argument that handles the simultaneous presence of community structure (SBM) and graph matching (permutation). Unlike previous works that conditioned on events with probability $1-o(1)$, this work conditions on an event with positive probability (ruling out small cycles), which is necessary because small cycles occur with non-negligible probability in the sparse regime and cause the likelihood ratio to blow up.
3. Tightness of Bounds: The result suggests that the computational barrier for detecting correlation in CSBMs is strictly determined by the interplay between the difficulty of recovering the community labels (KS threshold) and the difficulty of matching the graphs (Otter's threshold).

4. Main Results

• Theorem 1.3 (Computational Detection Threshold):
  • Easy Regime ($s > \min\{\sqrt{\alpha}, (\lambda \epsilon^2)^{-1}\}$): There exists a polynomial-time algorithm (based on degree-$D$ polynomials with $D = o(\log n)$) that successfully distinguishes $P_n$ from $Q_n$ with vanishing error.
  • Hard Regime ($s < \min\{\sqrt{\alpha}, (\lambda \epsilon^2)^{-1}\}$): No algorithm based on low-degree polynomials (degree $n^{o(1)}$) can distinguish the models. By the low-degree conjecture, this implies that no polynomial-time algorithm exists for this regime.
• Implications for Partial Recovery: Combining their hardness result with a reduction from [57], the authors show that partial recovery of the latent matching $\pi^*$ and community labels $\sigma^*$ is also computationally impossible in the hard regime.

5. Significance

• Bridging SBM and Graph Matching: This work unifies two major areas of random graph theory: Community Detection (SBM) and Graph Matching. It demonstrates that side information (correlation) does not always lower the computational threshold; in the sparse regime, the threshold is the minimum of the thresholds for the individual problems.
• Methodological Advancement: The paper provides a robust framework for analyzing low-degree hardness in models with complex dependencies (permutations + community labels). The technique of conditioning on the absence of small cycles and constructing a statistically indistinguishable measure $P'$ is a significant technical contribution that overcomes the divergence issues inherent in sparse correlated models.
• Open Questions: The authors note that while the low-degree threshold is established, the exact information-theoretic threshold remains an open question. It is conjectured that the information-theoretic threshold might be lower than the computational one, suggesting a statistical-computational gap in this setting.

In summary, this paper rigorously characterizes the limits of efficient algorithms for detecting correlations in sparse stochastic block models, identifying a precise phase transition governed by Otter's constant and the Kesten-Stigum threshold.