A Proof of the Block Model Threshold Conjecture

By Elchanan Mossel, Joe Neeman, Allan Sly. Combinatorica, 2013

356 citations recorded by the source corpus.

We study a random graph model called the “stochastic block model” in statistics and the “planted partition model” in theoretical computer science. In its simplest form, this is a random graph with two equal-sized classes of vertices, with a within-class edge probability of q and a between-class edge probability of q′. A striking conjecture of Decelle, Krzkala, Moore and Zdeborová [9], based on deep, non-rigorous ideas from statistical physics, gave a precise prediction for the algorithmic threshold of clustering in the sparse planted partition model. In particular, if q=a/n and q′=b/n, s=(a−b)/2 and d=(a+b)/2, then Decelle et al. conjectured that it is possible to efficiently cluster in a way correlated with the true partition if s2>d and impossible if s2Cdlnd for sufficiently large C. In a previous work, we proved that indeed it is information theoretically impossible to cluster if s2 ≤ d and moreover that it is information theoretically impossible to even estimate the model parameters from the graph when s2 < d. Here we prove the rest of the conjecture by providing an efficient algorithm for clustering in a way that is correlated with the true partition when s2>d. A different independent proof of the same result was recently obtained by Massoulié [20].

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/9e57a881c468bc6ff344a0904183733f43b47700

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Discrete Mathematics and Combinatorics

In Geometry and Topology

Citations in the corpus

A new proof of Friedman's second eigenvalue theorem and its extension to random lifts (2015, neutral): “Following [11, 8, 22, 7], we introduce a central definition.”
Supervised Community Detection with Line Graph Neural Networks (2017, background): “In the two community case, It was shown that exact recovery is possible on SBM(n, p = a lognn , q = b logn n ) if and only if a+b 2 ≥ 1 + √ ab (Mossel et al., 2014; Abbe et al., 2014).”
Consistency of spectral clustering in stochastic block models (2013, background): “…case, where the maximum degree is of order O (1), consistent community recovery is impossible and one can only hope to recover the communities up to a constant fraction (see Coja-Oghlan, 2010; Decelle et al., 2011; Mossel et al., 2012; Krzakala et al., 2013; Massoulie, 2013; Mossel et al., 2013).”
Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers (2017, neutral): “A result of Nesterov (1998) implies that this is true with κ = O(1) if ‖ · ‖∗ is any “quadratically convex” norm, which includes the `q-norms for q ∈ [2,∞].”
Structure and inference in annotated networks (2015, neutral): “that relies on network structure alone [22, 23].”
Statistical Inference on Random Dot Product Graphs: a Survey (2017, background): “In the study of stochastic blockmodels, there has been a recent push to understand the fundamental information-theoretic limits for community detection and graph partitioning [1, 2, 71, 72].”
Avoiding Imposters and Delinquents: Adversarial Crowdsourcing and Peer Prediction (2016, background): “Our setting corresponds to the sparse case where all nodes have constant degree, which has recently seen great interest (Decelle et al., 2011; Mossel et al., 2012; 2013b;a; Massoulié, 2014; Guédon and Vershynin, 2014; Mossel et al., 2015; Chin et al., 2015; Abbe and Sandon, 2015; Makarychev et al.,…”
Exact Recovery in the Stochastic Block Model (2014, methodology): “…≥ Ω( √ log(n)/n) [5] Bickel, Chen ’09 N-G modularity (p− q)/ √ p+ q = Ω(log(n)/ √ n) [32] Rohe, Chatterjee, Yu ’11 spectral method p− q = Ω(1) While these algorithmic developments are impressive, we next argue how they do not reveal the sharp behavioral transition that takes place in this model.”
Community Detection in General Stochastic Block models: Fundamental Limits and Efficient Algorithms for Recovery (2015, background): “Such phenomena are commonly used in coding theory for weak recovery [37], [38] and exact recovery [39], [40].”
Community Detection with Graph Neural Networks (2017, background): “There is no information-computation gap in this regime, so there are polynomial time algorithms when recovery is possible ((Abbe, 2017)(Mossel et al., 2014)).”
Nonbacktracking spectrum of random graphs: Community detection and nonregular Ramanujan graphs (2018, methodology): “Following [24], we say that a graph H is tanglefree (or -tangle-free to make the dependence in explicit) if every neighborhood”
Statistical physics of inference: thresholds and algorithms (2015, methodology): “The prediction and location of these phase transition in the stochastic block model from [59, 60] was followed by a remarkable mathematical development where the location of the threshold was made rigorous for q = 2 [158, 177, 178].”