Asymptotic Mutual Information for the Two-Groups Stochastic Block Model

Abstract

We develop an information-theoretic view of the stochastic block model, a popular statistical model for the large-scale structure of complex networks. A graph $G$ from such a model is generated by first assigning vertex labels at random from a finite alphabet, and then connecting vertices with edge probabilities depending on the labels of the endpoints. In the case of the symmetric two-group model, we establish an explicit `single-letter' characterization of the per-vertex mutual information between the vertex labels and the graph. The explicit expression of the mutual information is intimately related to estimation-theoretic quantities, and --in particular-- reveals a phase transition at the critical point for community detection. Below the critical point the per-vertex mutual information is asymptotically the same as if edges were independent. Correspondingly, no algorithm can estimate the partition better than random guessing. Conversely, above the threshold, the per-vertex mutual information is strictly smaller than the independent-edges upper bound. In this regime there exists a procedure that estimates the vertex labels better than random guessing.

41 pages, 3 pdf figures

References in corpus (7)

• MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel
• Community Detection in the Labelled Stochastic Block Model
• Finding One Community in a Sparse Graph
• Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms
• Accurate Community Detection in the Stochastic Block Model via Spectral Algorithms
• Stochastic Block Model and Community Detection in the Sparse Graphs: A spectral algorithm with optimal rate of recovery
• Tight Error Bounds for Structured Prediction

Cited by in corpus (20)

• Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula
• Phase Transitions in Semidefinite Relaxations
• MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel
• Information-theoretic thresholds from the cavity method
• Mutual Information in Rank-One Matrix Estimation
• Entrywise Eigenvector Analysis of Random Matrices with Low Expected Rank
• Solving SDPs for synchronization and MaxCut problems via the Grothendieck inequality
• Information-theoretic bounds for exact recovery in weighted stochastic block models using the Renyi divergence
• Density Evolution in the Degree-correlated Stochastic Block Model
• Reducibility and Statistical-Computational Gaps from Secret Leakage
• Inference via Message Passing on Partially Labeled Stochastic Block Models
• False Discoveries Occur Early on the Lasso Path
• Optimal Cluster Recovery in the Labeled Stochastic Block Model
• Rank-one matrix estimation: analysis of algorithmic and information theoretic limits by the spatial coupling method
• Universality of Computational Lower Bounds for Submatrix Detection
• Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization
• An Information-Percolation Bound for Spin Synchronization on General Graphs
• Application of information-percolation method to reconstruction problems on graphs
• Minimum ${\ell }_1$-norm interpolators: Precise asymptotics and multiple descent
• Mismatched Estimation of rank-one symmetric matrices under Gaussian noise