Information-theoretic thresholds from the cavity method

Abstract

Vindicating a sophisticated but non-rigorous physics approach called the cavity method, we establish a formula for the mutual information in statistical inference problems induced by random graphs and we show that the mutual information holds the key to understanding certain important phase transitions in random graph models. We work out several concrete applications of these general results. For instance, we pinpoint the exact condensation phase transition in the Potts antiferromagnet on the random graph, thereby improving prior approximate results [Contucci et al.: Communications in Mathematical Physics 2013]. Further, we prove the conjecture from [Krzakala et al.: PNAS 2007] about the condensation phase transition in the random graph coloring problem for any number $q\ge 3$ of colors. Moreover, we prove the conjecture on the information-theoretic threshold in the disassortative stochastic block model [Decelle et al.: Phys. Rev. E 2011]. Additionally, our general result implies the conjectured formula for the mutual information in Low-Density Generator Matrix codes [Montanari: IEEE Transactions on Information Theory 2005].

References in corpus (28)

• The Bethe lattice spin glass revisited
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Broken Replica Symmetry Bounds in the Mean Field Spin Glass Model
• The phase transition in inhomogeneous random graphs
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Statistical physics of inference: Thresholds and algorithms
• Phase Transitions in the Coloring of Random Graphs
• An Extended Variational Principle for the SK Spin-Glass Model
• Optimisation problems and replica symmetry breaking in finite connectivity spin-glasses
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• Maxwell Construction: The Hidden Bridge between Iterative and Maximum a Posteriori Decoding
• Tight bounds for LDPC and LDGM codes under MAP decoding
• Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
• The asymptotic $k$-SAT threshold
• Mutual Information in Rank-One Matrix Estimation
• Spin glass models from the point of view of spin distributions
• Factor models on locally tree-like graphs
• The cavity method at zero temperature
• Information-theoretic thresholds for community detection in sparse networks
• Asymptotic Mutual Information for the Two-Groups Stochastic Block Model
• The condensation phase transition in random graph coloring
• Replica bounds for optimization problems and diluted spin systems
• Harnessing the Bethe free energy
• Limits of discrete distributions and Gibbs measures on random graphs
• Antiferromagnetic Potts model on the Erdos-Renyi random graph
• Planting colourings silently
• Gibbs Measures and Phase Transitions on Sparse Random Graphs
• The number of solutions for random regular NAE-SAT

Cited by in corpus (29)

• Machine learning and the physical sciences
• Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models
• Supervised Community Detection with Line Graph Neural Networks
• The adaptive interpolation method for proving replica formulas. Applications to the Curie-Weiss and Wigner spike models
• Typology of phase transitions in Bayesian inference problems
• Storage capacity in symmetric binary perceptrons
• Fundamental limits of low-rank matrix estimation: the non-symmetric case
• Charting the replica symmetric phase
• Information-theoretic and algorithmic thresholds for group testing
• Phase transitions in the $q$-coloring of random hypergraphs
• Spin systems on Bethe lattices
• The random 2-SAT partition function
• Metastability of the Potts ferromagnet on random regular graphs
• The replica symmetric phase of random constraint satisfaction problems
• Phase transitions in the mini-batch size for sparse and dense two-layer neural networks
• Estimating rank-one matrices with mismatched prior and noise: universality and large deviations
• Strong replica symmetry for high-dimensional disordered log-concave Gibbs measures
• An Information-Percolation Bound for Spin Synchronization on General Graphs
• Concentration of multi-overlaps for random ferromagnetic spin models
• Mutual Information for the Stochastic Block Model by the Adaptive Interpolation Method
• The rank of random matrices over finite fields
• Noisy group testing via spatial coupling
• Breaking of 1RSB in random MAX-NAE-SAT
• Satisfiability Thresholds for Regular Occupation Problems
• Non-linear Log-Sobolev inequalities for the Potts semigroup and applications to reconstruction problems
• Counting colorings of triangle-free graphs
• Frozen $1$-RSB structure of the symmetric Ising perceptron
• Mutual Information in Community Detection with Covariate Information and Correlated Networks
• Inference in Spreading Processes with Neural-Network Priors