Typology of phase transitions in Bayesian inference problems
arXiv:1806.11013 · doi:10.1103/PhysRevE.99.042109
Abstract
Many inference problems, notably the stochastic block model (SBM) that generates a random graph with a hidden community structure, undergo phase transitions as a function of the signal-to-noise ratio, and can exhibit hard phases in which optimal inference is information-theoretically possible but computationally challenging. In this paper we refine this description by emphasizing the existence of more generic phase diagrams with a hybrid-hard phase in which it is computationally easy to reach a non-trivial inference accuracy, but computationally hard to match the information theoretically optimal one. We support this discussion by quantitative expansions of the functional cavity equations that describe inference problems on sparse graphs. These expansions shed light on the existence of hybrid-hard phases, for a large class of planted constraint satisfaction problems, and on the question of the tightness of the Kesten-Stigum (KS) bound for the associated tree reconstruction problem. Our results show that the instability of the trivial fixed point is not a generic evidence for the Bayes-optimality of the message passing algorithms. We clarify in particular the status of the symmetric SBM with 4 communities and of the tree reconstruction of the associated Potts model: in the assortative (ferromagnetic) case the KS bound is always tight, whereas in the disassortative (antiferromagnetic) case we exhibit an explicit criterion involving the degree distribution that separates a large degree regime where the KS bound is tight and a low degree regime where it is not. We also investigate the SBM with 2 communities of different sizes, a.k.a. the asymmetric Ising model, and describe quantitatively its computational gap as a function of its asymmetry, and a version of the SBM with 2 groups of communities. We complement this study with numerical simulations of the Belief Propagation algorithm.
arXiv comment64 pages, 17 figures, v2 : minor modifications
References in corpus (29)
- Community detection in graphs
- Message Passing Algorithms for Compressed Sensing
- The Bethe lattice spin glass revisited
- The dynamics of message passing on dense graphs, with applications to compressed sensing
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Mean field theory of hard sphere glasses and jamming
- 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 transition in the detection of modules in sparse networks
- Reconstruction on trees and spin glass transition
- Maxwell Construction: The Hidden Bridge between Iterative and Maximum a Posteriori Decoding
- Hiding Quiet Solutions in Random Constraint Satisfaction Problems
- Tight bounds for LDPC and LDGM codes under MAP decoding
- Hiding solutions in random satisfiability problems: A statistical mechanics approach
- Information-theoretic thresholds from the cavity method
- Constrained Low-rank Matrix Estimation: Phase Transitions, Approximate Message Passing and Applications
- Finding One Community in a Sparse Graph
- Constraint satisfaction problems with isolated solutions are hard
- Robust reconstruction on trees is determined by the second eigenvalue
- Reconstruction of Random Colourings
- Community detection in networks with unequal groups
- Potts Glass on Random Graphs
- Belief propagation, robust reconstruction and optimal recovery of block models
- Quiet Planting in the Locked Constraint Satisfaction Problems
- Charting the replica symmetric phase
- Phase transitions in the -coloring of random hypergraphs
- The Tightness of the Kesten-Stigum Reconstruction Bound of Symmetric Model with Multiple Mutations
- Large Degree Asymptotics and the Reconstruction Threshold of the Asymmetric Binary Channels
Cited by in corpus (24)
- Phase transition in the recoverability of network history
- Community Detection in Bipartite Networks with Stochastic Blockmodels
- Disordered Systems Insights on Computational Hardness
- Marvels and Pitfalls of the Langevin Algorithm in Noisy High-dimensional Inference
- The Wishart planted ensemble: A tunably-rugged pairwise Ising model with a first-order phase transition
- Fundamental limits to learning closed-form mathematical models from data
- Limits and performances of algorithms based on simulated annealing in solving sparse hard inference problems
- Sampling with flows, diffusion and autoregressive neural networks: A spin-glass perspective
- Biased landscapes for random Constraint Satisfaction Problems
- Reducibility and Statistical-Computational Gaps from Secret Leakage
- Recovery thresholds in the sparse planted matching problem
- Average-Case Lower Bounds for Learning Sparse Mixtures, Robust Estimation and Semirandom Adversaries
- Generating Hard Ising Instances With Planted Solutions Using Post-Quantum Cryptographic Protocols
- Biased measures for random Constraint Satisfaction Problems: larger interaction range and asymptotic expansion
- Analytical solution to Heisenberg spin glass models on sparse random graphs and their de Almeida-Thouless line
- Efficient inference in stochastic block models with vertex labels
- Evidence of Replica Symmetry Breaking under the Nishimori conditions in epidemic inference on graphs
- The RL Perceptron: Generalisation Dynamics of Policy Learning in High Dimensions
- Generalized Approximate Survey Propagation for High-Dimensional Estimation
- Big Data Information Reconstruction on an Infinite Tree for a -state Asymmetric Model with Community Effects
- Mismatching as a tool to enhance algorithmic performances of Monte Carlo methods for the planted clique model
- Planted matching problems on random hypergraphs
- Interacting Copies of Random Constraint Satisfaction Problems
- The non-tightness of the reconstruction threshold of a 4 states symmetric model with different in-block and out-block mutations