A proof of the block model threshold conjecture

DOI10.1007/S00493-016-3238-8MaRDI QIDQ1715062zbMATH OpenOpenAlexWikidataFDO

Authors Elchanan Mossel, Joe Neeman, Allan Sly

Publication date 1 February 2019

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1311.4115

zbMATH Keywords

planted partition modelrandom graphstochastic block model

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05)

Abstract: We study a random graph model named the "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 clusters, with a between-class edge probability of $q$ and a within-class edge probability of $p$. A striking conjecture of Decelle, Krzkala, Moore and Zdeborov'a 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 $p=a/n$ and $q=b/n$, $s=(a-b)/2$ and $p=(a+b)/2$ then Decelle et al. conjectured that it is possible to efficiently cluster in a way correlated with the true partition if $s^2>p$ and impossible if $s^2<p$. By comparison, the best-known rigorous result is that of Coja-Oghlan, who showed that clustering is possible if $s^2>Cplnp$ for some sufficiently large $C$. In a previous work, we proved that indeed it is information theoretically impossible to to cluster if $s^2<p$ and furthermore it is information theoretically impossible to even estimate the model parameters from the graph when $s^2<p$. Here we complete the proof of the conjecture by providing an efficient algorithm for clustering in a way that is correlated with the true partition when $s^2>p$. A different independent proof of the same result was recently obtained by Laurent Massoulie.

Review text

The paper under review considers the so-called stochastic block model of random graphs, where each vertex $v\in \{1,2,\ldots n\}$ is assigned (independently and uniformly at random) a label $\sigma_{v}\in \{-1,1\}$ and then $u$ and $v$ are adjacent with probability $q$ if they have the same label and probability $q'$ if they have different labels, again all edges being, conditional on the labelling, independent of each other. For $q=q'$ we recover the Erdős-Rényi random graph model. We focus on the sparse case $q=a/n$, $q'=b/n$ and introduce two parameters $d=(a+b)/2$ and $s=(a-b)/2$. Based on deep but non-rigorous ideas from statistical physics, it was conjectured in [\textit{A. Decelle} et al., ``Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications, Phys. Rev. E (3) 84, Article ID 066106, 19 p. (2011; \url{doi:10.1103/PhysRevE.84.066106})] that provided $s^2>d$ one can solve the problem, in the sense that one can a.a.s. find a bisection of the graph -- i.e., partition its vertex set -- in a way whose correlation with the ``planted bisection, i.e., the partition given by the labelling is bounded away from zero. In [Probab. Theory Relat. Fields 162, No. 3--4, 431--461 (2015; Zbl 1320.05113)], the authors of the paper under review had shown that if $s^{2}\leq d$ then the problem cannot be solved in the above sense. Their substantial contribution in this paper is, building on earlier partial results of Coja-Oghlan, to indeed prove the conjecture. Indeed their method is computationally effective and can be implemented in time $O(n\log^{2}(n))$. The result has also been shown independently by \textit{L. Massoulié} [in: Proceedings of the 46th annual ACM symposium on theory of computing, STOC 2014. New York, NY: Association for Computing Machinery (ACM). 694--703 (2014; Zbl 1315.68210)] whose algorithm is spectral but slower than that in the paper under review.

Recommendations

• Proof of the achievability conjectures for the general stochastic block model
• The complexity of the Approximate Multiple Pattern Matching Problem for random strings
• Publication:3033152
• An impossibility result for reconstruction in the degree-corrected stochastic block model
• On the chromatic number in the stochastic block model
• An exact threshold theorem for random graphs and the node-packing problem
• scientific article; zbMATH DE number 1789844
• The Maximum Block Size of Critical Random Graphs
• Blocks in constrained random graphs with fixed average degree
• Further evidence for conjectures in block theory.

Cited in

(91)

• MAX \(\kappa\)-cut and the inhomogeneous Potts spin Glass
• A note on probably certifiably correct algorithms
• Notes on computational-to-statistical gaps: predictions using statistical physics
• Bethe states of random factor graphs
• On semidefinite relaxations for the block model
• Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs
• Contiguity and non-reconstruction results for planted partition models: the dense case
• Charting the replica symmetric phase
• Random Laplacian matrices and convex relaxations
• Convex relaxation methods for community detection
• Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing
• Detecting a planted community in an inhomogeneous random graph
• The structure of Gaussian minimal bubbles
• On the computational tractability of statistical estimation on amenable graphs
• Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
• Global and individualized community detection in inhomogeneous multilayer networks
• Testing community structure for hypergraphs
• Iterative algorithm for discrete structure recovery
• Sparse and smooth: improved guarantees for spectral clustering in the dynamic stochastic block model
• Powerful multiple testing of paired null hypotheses using a latent graph model
• Application of the information-percolation method to reconstruction problems on graphs
• Optimal rates for community estimation in the weighted stochastic block model
• Entrywise eigenvector analysis of random matrices with low expected rank
• Step-by-step community detection in volume-regular graphs
• Information reconstruction on an infinite tree for a \(4\times 4\)-state asymmetric model with community effects
• Exact recovery in the hypergraph stochastic block model: a spectral algorithm
• Exact recovery in the Ising blockmodel
• Large degree asymptotics and the reconstruction threshold of the asymmetric binary channels
• Exact recovery of community detection in k-partite graph models with applications to learning electric potentials in electric networks
• Global and local information in clustering labeled block models
• Disentangling group and link persistence in dynamic stochastic block models
• Belief propagation, robust reconstruction and optimal recovery of block models
• Statistical inference on random dot product graphs: a survey
• Proof of the achievability conjectures for the general stochastic block model
• On the complexity of random satisfiability problems with planted solutions
• Matched bipartite block model with covariates
• Non-backtracking spectrum of degree-corrected stochastic block models
• Universal latent space model fitting for large networks with edge covariates
• Weighted message passing and minimum energy flow for heterogeneous stochastic block models with side information
• Phase transition of the reconstructability of a general model with different in-community and out-community mutations on an infinite tree
• Strong consistency, graph Laplacians, and the stochastic block model
• The Lovász theta function for random regular graphs and community detection in the hard regime
• Charting the replica symmetric phase
• Average whenever you meet: opportunistic protocols for community detection
• Eigenvalues of the non-backtracking operator detached from the bulk
• Graph powering and spectral robustness
• Compressive sensing for cut improvement and local clustering
• Exact Recovery and Sharp Thresholds of Stochastic Ising Block Model
• Community Detection in Sparse Networks Using the Symmetrized Laplacian Inverse Matrix (SLIM)
• Iterative Collaborative Filtering for Sparse Matrix Estimation
• Joint community detection and rotational synchronization via semidefinite programming
• Find Your Place: Simple Distributed Algorithms for Community Detection
• Optimal couplings between sparse block models
• scientific article; zbMATH DE number 7307464 (Why is no real title available?)
• Statistical guarantees for local graph clustering
• The Lovász theta function for random regular graphs and community detection in the hard regime
• Community detection thresholds and the weak Ramanujan property
• The Ising Antiferromagnet and Max Cut on Random Regular Graphs
• Outliers in spectrum of sparse Wigner matrices
• Non-linear log-Sobolev inequalities for the Potts semigroup and applications to reconstruction problems
• Community detection in the sparse hypergraph stochastic block model
• The planted matching problem: sharp threshold and infinite-order phase transition
• Nonbacktracking Spectral Clustering of Nonuniform Hypergraphs
• Combinatorial statistics and the sciences
• Bias-Adjusted Spectral Clustering in Multi-Layer Stochastic Block Models
• Mutual information for the sparse stochastic block model
• A compressed sensing based least squares approach to semi-supervised local cluster extraction
• A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization
• Learning sparse graphons and the generalized Kesten-Stigum threshold
• Community Detection in Censored Hypergraph
• Inference in balanced community modulated recursive trees
• Limiting empirical spectral distribution for the non-backtracking matrix of an Erdős-Rényi random graph
• Bad local minima exist in the stochastic block model
• Pair-matching: link prediction with adaptive queries
• Computational lower bounds for graphon estimation via low-degree polynomials
• Searching for (sharp) thresholds in random structures: where are we now?
• Sparse random hypergraphs: non-backtracking spectra and community detection
• A computational transition for detecting correlated stochastic block models by low-degree polynomials
• Matching algorithms in the sparse stochastic block model
• Fundamental limits of community detection from multi-view data: multi-layer, dynamic and partially labeled block models
• Partial recovery and weak consistency in the non-uniform hypergraph stochastic block model
• Exact recovery of community detection in k-community Gaussian mixture models
• Semi-supervised clustering of sparse graphs: crossing the information-theoretic threshold
• Exact phase transitions for stochastic block models and reconstruction on trees
• Reconstructing ultrametric trees from noisy experiments
• Large deviation principles for graphon sampling
• Consistency of Lloyd's algorithm under perturbations
• A goodness-of-fit test for sparse networks
• Community detection in sparse networks via Grothendieck's inequality
• Finding one community in a sparse graph
• Estimating the number of communities by spectral methods

This page was built for publication: A proof of the block model threshold conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1715062)