PaperlayerView exact revision on arXiv

Source-linked AI summary

The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness

Cristopher Moore

arXiv:1702.00467v3cs.CCcond-mat.stat-mechcs.SImath.PRphysics.soc-ph

TL;DR

Community detection asks whether hidden groups can be recovered from a graph, rather than merely finding a good partition. The paper connects this inference problem to statistical physics and analyzes its phase transitions, including regimes where information may suffice but efficient recovery remains conjecturally hard.

  • Problem

    The central question is when a graph contains enough signal to recover planted communities or distinguish them from random structure, especially when the graph is sparse or noisy.

    Source: §1 · p. 2, §3 · p. 10

  • Method

    The paper analyzes planted community detection through its Bayesian posterior and physics analogies, using direct computation of marginals to study phase transitions.

    Source: §3 · p. 8, §4 · p. 12

  • Results

    For q ≥ 5 groups, and disassortative q = 4, detection and weak reconstruction have an information-theoretic-to-computational gap where success is possible but believed to require exponential time.

    Source: §2 · p. 7

  • Takeaways & Limitations

    Community detection has distinct information and computation thresholds, so solvability from the graph does not necessarily imply an efficient algorithm is known.

    Source: §2 · p. 7

    Below the Kesten-Stigum threshold, the accurate fixed point is believed exponentially hard to find, with a free-energy barrier proposed as the explanation.

    Source: §9 · p. 30

Abstract

from arXiv · show

Community detection in graphs is the problem of finding groups of vertices which are more densely connected than they are to the rest of the graph. This problem has a long history, but it is undergoing a resurgence of interest due to the need to analyze social and biological networks. While there are many ways to formalize it, one of the most popular is as an inference problem, where there is a "ground truth" community structure built into the graph somehow. The task is then to recover the ground truth knowing only the graph. Recently it was discovered, first heuristically in physics and then rigorously in probability and computer science, that this problem has a phase transition at which it suddenly becomes impossible. Namely, if the graph is too sparse, or the probabilistic process that generates it is too noisy, then no algorithm can find a partition that is correlated with the planted one---or even tell if there are communities, i.e., distinguish the graph from a purely random one with high probability. Above this information-theoretic threshold, there is a second threshold beyond which polynomial-time algorithms are known to succeed; in between, there is a regime in which community detection is possible, but conjectured to require exponential time. For computer scientists, this field offers a wealth of new ideas and open questions, with connections to probability and combinatorics, message-passing algorithms, and random matrix theory. Perhaps more importantly, it provides a window into the cultures of statistical physics and statistical inference, and how those cultures think about distributions of instances, landscapes of solutions, and hardness.

1 Introduction

Community detection is framed as recovering hidden groups from a graph, but nearly equivalent partitions can disagree about who belongs where. The section contrasts minimizing a cut with inferring a trustworthy structure from uncertain data.

1 Introduction

  • The motivating task is to assign people to two hidden, equal-sized demographic groups using only their social links.The proposed groups are expected to link mostly within their own group, but their demographic labels are unavailable.Source: §1 · pp. 2–3
  • Min Bisection offers a computationally hard optimization framing, while researchers from statistics, combinatorics, machine learning, and physics bring different questions and tools.The discussion names Min Bisection as NP-hard and stages a clash among approaches including moment calculations, EM, MAP, and the planted Potts model.Source: §1 · pp. 2–3
  • The two nearly equal-cut partitions disagree about membership almost as often as a coin flip, leaving no clear indication of which reflects the hidden groups.They have 38 and 36 crossing edges, respectively, in a random 3-regular graph; such graphs typically have bisections with about 11% of edges crossing [79], see also [27].Source: §1 · p. 2, Figure 1 · p. 4
  • A slightly smaller cut suits a design objective, but uncertainty and small data errors can change which partition appears better.Min Bisection minimizes edges crossing between two equal groups; the section contrasts this with the sociologist’s goal of finding the truth.Source: §1 · p. 2

2 The Stochastic Block Model

The stochastic block model treats communities as planted labels that govern edge probabilities, turning community detection into reconstruction and testing problems. In the constant-degree regime, the section describes impossibility thresholds and, for specified group settings, a gap between information-theoretic possibility and known efficient algorithms.

2 The Stochastic Block Model

  • The model is motivated by noisy, random instances rather than worst-case guarantees, and its sparse setting has asymptotically Poisson degree distribution.The model’s edge probabilities depend on group membership; the classic Erdős-Rényi case occurs when c_in = c_out.Source: §2 · pp. 5–6
  • The model assigns each vertex a planted group and generates edges independently, with connection probabilities determined by whether endpoint groups match.The symmetric case uses the same within-group probability p_in and across-group probability p_out; p_in > p_out is assortative, while p_in < p_out is disassortative.Source: §2 · pp. 5–6
  • The paper asks whether one can recover planted labels up to group permutation, achieve correlation better than chance, or detect the model against an Erdős-Rényi graph of the same average degree.The reconstruction accuracy is measured after the best permutation of group labels; detection compares against G(n, c/n).Source: §2 · pp. 6–7
  • If groups are too weakly structured or the graph too sparse, no algorithm can reconstruct labels better than chance or distinguish the graph from a random one.These are the reconstruction and detection phase transitions emphasized for the constant-degree regime.Source: §2 · p. 7
  • For q ≥ 5, and in the disassortative case with q = 4, an information-theoretically possible but conjecturally exponential-time regime lies below the threshold where efficient algorithms are known.The computational threshold is where efficient algorithms are known to exist; below the information-theoretic threshold, the graph lacks enough information to solve the problem.Source: §2 · p. 7

3 Bayes and Ising

The section casts recovery of planted groups as Bayesian inference over assignments given the observed graph, then connects that posterior to statistical physics. This perspective distinguishes finding a single most likely assignment from understanding how much the full posterior reveals about the planted state.

3 Bayes and Ising

  • Bayesian recovery seeks the posterior distribution of group assignments given the graph, with its normalization summing graph probabilities over all assignments.Under the uniform prior, the prior probability is constant, leaving the posterior proportional to the graph likelihood.Source: §3 · pp. 7–8
  • With suitable interaction strength and temperature, the block-model posterior matches an Ising or Potts Boltzmann distribution; assortativity corresponds to ferromagnetic interactions and disassortativity to antiferromagnetic ones.Stronger community structure corresponds either to stronger interactions or lower noise.Source: §3 · p. 9
  • The highest-posterior, lowest-energy state is an exact-recovery target, possible when the planted assignment is the most likely state and average degree is sufficiently large relative to log n.The section identifies this state as MLE, or MAP when the prior is included.Source: §3 · p. 10
  • Because exact labeling every vertex is demanding, the section motivates weak reconstruction as labeling a constant fraction correctly above chance, analogous to magnetization.For q groups, the comparison is a fraction greater than 1/q.Source: §3 · p. 10

4 Temperature and Noise

The section uses the physics analogy between temperature and noise to explain why community recovery can lose its signal at a phase transition. It argues for estimating posterior marginals rather than relying on a single best assignment, and introduces direct marginal computation as a route to analyzing transitions and hard regimes.

4 Temperature and Noise

  • When community structure is too weak or the graph too sparse, the correctly labeled fraction is expected to approach chance, 1/q.The section relates this transition to an unmagnetized Ising system whose correlations decay with distance.Source: §4 · p. 10
  • Posterior marginals support assigning each vertex its most likely group, an estimator that maximizes expected correctly labeled fraction; uniform marginals make weak reconstruction impossible.The section notes that label-permutation symmetry can be broken by fixing a few vertex labels.Source: §4 · p. 11
  • A single best-fitting assignment can mislead when many local optima are unrelated, so Bayesian inference calls for considering the full posterior and its uncertainty.For sparse or uncertain data, averaging across likely fits is presented as preferable to relying on one best fit.Source: §4 · p. 12
  • Rather than estimate marginals by Monte Carlo sampling, the paper uses a direct method that can be efficient and accurate in some circumstances and can locate phase transitions analytically.The method also gives a hint why detection may be possible yet exponentially hard in some regimes.Source: §4 · p. 12

5 The Cavity Method and Belief Propagation

Belief propagation estimates community marginals by iteratively passing neighbor-excluding messages, an approach motivated by the cavity method and exact on trees. Its reliability on general graphs depends on local treelike structure, an assumption that can fail for real networks with short loops.

5 The Cavity Method and Belief Propagation

  • Belief propagation iteratively updates messages between neighboring vertices to estimate their marginals, excluding the recipient's message to avoid echoing information back.The cavity method is closely related to belief propagation and message-passing algorithms developed in AI, including Judea Pearl's work.Source: §5 · pp. 13, 15, Figure 3 · p. 14
  • Assuming neighbors are independent yields naive Bayes and a product-distribution posterior, while belief propagation instead conditions their independence on the vertex's own state.The latter approach models neighbors as correlated only through the vertex being updated.Source: §5 · p. 13
  • Belief propagation is exact on trees and can be asymptotically correct on locally treelike graphs when correlations decay rapidly with distance.Sparse block-model graphs are locally treelike with high probability.Source: §5 · p. 15
  • Stable message fixed points minimize the Bethe free energy, but the associated posterior approximation need not normalize on general graphs.The approximation is exact on trees, making its use on general graphs questionable.Source: §5 · p. 15
  • Belief propagation for the block model appeared in [39], and [25] used it to derive the detectability transition and conjecture a detectable-but-hard regime.Their analysis considered stable and unstable fixed points and how often random initial messages converge to them.Source: §5 · pp. 15–16

6 Stability and Non-Backtracking Walks

The section derives the Kesten-Stigum threshold by analyzing the stability of belief propagation's uniform fixed point through non-backtracking walks. Above the threshold, informative eigenvectors emerge from the spectral bulk, supporting weak reconstruction by non-backtracking spectral methods.

6 Stability and Non-Backtracking Walks

  • Weak reconstruction is possible and feasible above the Kesten-Stigum threshold, where belief-propagation variants and efficient algorithms are known to succeed.For q = 2, efficient algorithms were given in [52] [61]; for q > 2, a belief-propagation variant achieves weak reconstruction.Source: §6 · p. 16
  • The non-backtracking matrix B encodes directed-edge walks that cannot immediately reverse, and its combination with T governs linearized message updates.The derivative matrix M is formed by replacing each 1 in B with a copy of T.Source: §6 · pp. 17–18
  • The Kesten-Stigum threshold occurs when the uniform belief-propagation fixed point becomes unstable, yielding condition (16).This instability is determined by the relevant eigenvalue of M = B ⊗ T.Source: §6 · pp. 16, 20
  • Above the threshold, community-correlated non-backtracking eigenvectors emerge from the bulk, enabling spectral clustering that beats chance but is less accurate than belief propagation.The non-backtracking spectral algorithm was proposed in and proved to work in [18].Source: Figure 4 · p. 19, §6 · p. 20
  • Standard adjacency-matrix and graph-Laplacian spectral clustering fail in the constant-degree regime because high-degree vertices localize their eigenvectors.When average degree grows moderately with n, the semicircle law offers another route to deriving the Kesten-Stigum threshold [66].Source: §6 · p. 20
  • Using incorrect block-model parameters can separate the instability and spectral thresholds, producing a spin-glass phase in which belief propagation fails to converge.In that phase the non-backtracking matrix does not reveal the ground truth.Source: §6 · pp. 20–21

7 Reconstruction on Trees

Reconstruction on trees asks whether distant descendants retain information about the root’s color. Its threshold provides an information-theoretic lower bound for weak reconstruction in the block model, while the number of groups affects whether information and computational thresholds coincide.

7 Reconstruction on Trees

  • Faithful descendants have expected count c^ℓλ^ℓ; majority succeeds when their signal exceeds the typical imbalance among randomly colored descendants.Below the threshold, faithful descendants are exponentially fewer than that imbalance.Source: §7 · pp. 21, 23
  • Above cλ² = 1, the population majority matches the root with high probability; below it, correlation with the root decays exponentially in generations.For q = 2, the tree condition is necessary and sufficient for reconstruction and is also the threshold for robust reconstruction [43].Source: Figure 5 · p. 22, §7 · p. 23
  • The tree reconstruction threshold lower-bounds the block model’s information-theoretic threshold, and for q = 2 it matches the Kesten-Stigum threshold.The comparison gives the true labels of vertices ℓ steps away and asks how much information they provide about an interior vertex.Source: §7 · p. 23
  • For q ≥ 4, the Kesten-Stigum threshold is not tight and the information-theoretic and computational thresholds are distinct; for q = 3, tightness remains unproved.For q ≥ 4, reconstruction is described as information-theoretically possible but conjectured computationally hard in the intervening regime.Source: §7 · p. 23

8 Detection and Contiguity

Detection asks whether a graph came from a block model or an Erdős-Rényi null model, and contiguity formalizes when these distributions cannot be distinguished with high probability. The section develops second-moment lower bounds and contrasts them with exhaustive-search upper bounds, including regimes where the information-theoretic and Kesten-Stigum thresholds differ.

8 Detection and Contiguity

  • Above the Kesten-Stigum threshold, cycle counts become less overlapping as cycle length increases; triangle counts also differ between the block and Erdős-Rényi models for λ > 0.The triangle-count distributions remain overlapping, despite being noticeably different.Source: §8 · p. 24
  • If the block-model and Erdős-Rényi distributions are contiguous, any event rare under the null is also rare under the block model, preventing reliable detection.The section defines detection as distinguishing the models with probability 1 − o(1).Source: §8 · p. 24
  • A bounded second moment of the likelihood ratio under the null is sufficient for one-way contiguity; proving the reverse direction requires refinement by conditioning on short-cycle counts.The likelihood ratio is the block-model probability of a graph divided by its null-model probability [69].Source: §8 · p. 25
  • The second-moment sum pits entropy, favoring uncorrelated assignment pairs, against energy, favoring correlated pairs; Laplace’s method yields a constant bound when λ is small enough.For q > 2, the optimization is over doubly stochastic matrices.Source: §8 · pp. 26–27
  • Second-moment calculations and their short-cycle refinement established contiguity below Kesten-Stigum for q = 2, and a lower bound on general-q detectability; reconstruction is also impossible in the stated range.The passage does not specify the general-q range in the supplied text.Source: §8 · p. 27
  • Exhaustive search gives upper bounds: a sufficiently good partition supports detection and reconstruction, q-colorability places the information threshold below Kesten-Stigum for q ≥ 5, and typical partitions show this gap for some λ < 0 when q ≥ 4.For q ≥ 4 in the disassortative case, this proves the conjectured separation [25]; whether the thresholds coincide for q = 3 remains open.Source: §8 · p. 27

9 The Hard Regime

For q = 5 planted coloring, the hard regime lies between the clustering transition at c = 12.8 and the information-theoretic transition at c = 13.2. Belief propagation with random initialization usually misses the accurate fixed point there, while the free-energy comparison identifies when accurate inference becomes favored.

9 The Hard Regime

  • For c > 16, belief propagation leaves the unstable uniform fixed point for the accurate one, whereas below c = 12.8 the accurate fixed point disappears.The threshold c = 16 is the Kesten–Stigum value for q = 5.Source: §9 · p. 28, Figure 6 · p. 29
  • Between c = 12.8 and c = 16, both fixed points are locally stable, but random initialization reaches the accurate one with only exponentially small probability.The accurate fixed point has a narrow basin of attraction; it was found numerically by initializing messages with the ground truth.Source: §9 · p. 28, Figure 6 · p. 29
  • At c = 13.2 the Bethe free energies cross, marking the information-theoretic threshold; the accurate fixed point first appears at c = 12.8.Between these transitions it exists but has higher Bethe free energy than the uniform fixed point, so Bayesian inference favors the uniform one.Source: §9 · pp. 28, 30, Figure 6 · p. 29
  • The authors believe the accurate fixed point is exponentially hard to find below the Kesten–Stigum threshold because a free-energy barrier separates it from the uniform state.They describe possible proofs for specific algorithm classes, such as exponential mixing for Markov chains or convergence of belief propagation to the uniform fixed point.Source: §9 · p. 30
  • Between c = 12.8 and c = 13.2, exponentially many separated clusters of good-looking partitions also occur in random graphs, making focus on any one cluster vulnerable to overfitting.These transitions have analogues in random constraint satisfaction problems; the information-theoretic threshold is the condensation transition and the appearance of the accurate fixed point is the clustering transition.Source: §9 · p. 30
  • Recent work makes the Bethe free energy asymptotically correct in some planted models, including the disassortative block model, and rigorously identifies the information-theoretic threshold with condensation.This supports locating the threshold through calculations that are not fully explicit and justifies numerical cavity-method approaches.Source: §9 · pp. 30–31

10 Open Questions

The open questions concern how thresholds and computational hardness behave across block-model settings and extensions. They also point toward related inference problems with phase transitions and hard regions.

10 Open Questions

  • Whether information-theoretic and computational thresholds coincide remains open for q = 3 and q = 4 in the assortative case, including whether the regular-tree Kesten–Stigum result extends to Poisson Galton–Watson trees.For regular trees, the Kesten–Stigum bound is tight for q = 3 at sufficiently large degree.Source: §10 · p. 31
  • The hard regime motivates proving exponential difficulty for specific algorithms, including Glauber dynamics mixing and belief propagation with random initial messages.These are posed as open proof questions, not established hardness results.Source: §10 · p. 31
  • The phase transitions induced by side information remain open as a function of community structure and the amount or accuracy of revealed labels.Providing true labels for some vertices can push an algorithm toward the accurate fixed point; this setting is also called semisupervised learning or side information, [65].Source: §10 · p. 31
  • For mixedmembership block models, an open question is whether phase transitions depend on network density and the extent of community overlap.Vertices carry q-dimensional membership vectors, and some versions can be viewed as low-rank matrix factorization with Poisson noise,.Source: §10 · p. 31
  • The article situates these questions within a broader class of inference problems that can have information-theoretic phase transitions and hard regions where known polynomial-time methods fail.Examples named include matrix factorization and sparse recovery; PCA is cited as one such failing method [13].Source: §10 · p. 33
Loading 1702.00467v3…