Typology of phase transitions in Bayesian inference problems

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.

64 pages, 17 figures, v2 : minor modifications

References in corpus (11)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Phase transition in the detection of modules in sparse networks
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• Constrained Low-rank Matrix Estimation: Phase Transitions, Approximate Message Passing and Applications
• Constraint satisfaction problems with isolated solutions are hard
• Reconstruction of Random Colourings
• Potts Glass on Random Graphs
• Charting the replica symmetric phase
• Phase transitions in the $q$-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 $4\times 4$-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