Mutual information for the sparse stochastic block model

DOI10.1214/23-AOP1665arXiv2209.04513OpenAlexW4306835559MaRDI QIDQ6151948FDOQ6151948

Authors: Tomas Dominguez, J-C. Mourrat 

Publication date: 11 March 2024

Published in: The Annals of Probability (Search for Journal in Brave)

Abstract: We consider the problem of recovering the community structure in the stochastic block model with two communities. We aim to describe the mutual information between the observed network and the actual community structure in the sparse regime, where the total number of nodes diverges while the average degree of a given node remains bounded. Our main contributions are a conjecture for the limit of this quantity, which we express in terms of a Hamilton-Jacobi equation posed over a space of probability measures, and a proof that this conjectured limit provides a lower bound for the asymptotic mutual information. The well-posedness of the Hamilton-Jacobi equation is obtained in our companion paper. In the case when links across communities are more likely than links within communities, the asymptotic mutual information is known to be given by a variational formula. We also show that our conjectured limit coincides with this formula in this case.

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

Recommendations

• Asymptotic mutual information for the balanced binary stochastic block model
• Community detection and stochastic block models
• Application of the information-percolation method to reconstruction problems on graphs

zbMATH Keywords

stochastic block modelmutual informationfree energyHamilton-Jacobi equation

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Viscosity solutions to PDEs (35D40) Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics (82B44) PDEs on infinite-dimensional (e.g., function) spaces (= PDEs in infinitely many variables) (35R15)

Cites Work

• A proof of the block model threshold conjecture
• Mixed membership stochastic blockmodels
• Belief propagation, robust reconstruction and optimal recovery of block models
• Stochastic Blockmodels for Directed Graphs
• Concentration inequalities. A nonasymptotic theory of independence
• Reconstruction and estimation in the planted partition model
• Community detection thresholds and the weak Ramanujan property
• Exact Recovery in the Stochastic Block Model
• The phase transition in inhomogeneous random graphs
• Title not available (Why is that?)
• Random graph models of social networks
• Structure of 1-RSB asymptotic Gibbs measures in the diluted \(p\)-spin models
• Structure of finite-RSB asymptotic Gibbs measures in the diluted spin glass models
• Spin glass models from the point of view of spin distributions
• The Sherrington-Kirkpatrick model
• Efficient discovery of overlapping communities in massive networks
• The solution of some random NP-hard problems in polynomial expected time
• Statistical inference of finite-rank tensors
• Fundamental limits of symmetric low-rank matrix estimation
• On the replica symmetric solution of the \(K\)-sat model
• Hamilton-Jacobi equations for finite-rank matrix inference
• Hamilton-Jacobi equations for nonsymmetric matrix inference
• Stephen Fienberg: Superman of statistics
• Conditional random fields, planted constraint satisfaction, and entropy concentration
• Asymptotic mutual information for the balanced binary stochastic block model
• The adaptive interpolation method: a simple scheme to prove replica formulas in Bayesian inference
• Hamilton-Jacobi equations for mean-field disordered systems
• Mutual information for low-rank even-order symmetric tensor estimation
• Hamilton-Jacobi equations for inference of matrix tensor products
• Strong replica symmetry in high-dimensional optimal Bayesian inference
• Global and Local Information in Clustering Labeled Block Models
• Local algorithms for block models with side information
• Free energy of multi-layer generalized linear models

Cited In (4)

• Infinite-dimensional Hamilton-Jacobi equations for statistical inference on sparse graphs
• Fundamental limits of low-rank matrix estimation with diverging aspect ratios
• Breakdown of a concavity property of mutual information for non-Gaussian channels
• Information theoretic limits of learning a sparse rule

This page was built for publication: Mutual information for the sparse stochastic block model

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