Typology of phase transitions in Bayesian inference problems.

Many inference problems undergo phase transitions as a function of the signal-to-noise ratio, a prominent example of this phenomenon being found in the stochastic block model (SBM) that generates a random graph with a hidden community structure. Some of these phase transitions affect the information-theoretic optimal (but possibly computationally expensive) estimation procedure, others concern the behavior of efficient iterative algorithms. A computational gap opens when the phase transitions for these two aspects do not coincide, leading to a hard phase in which optimal inference is computationally challenging. In this paper we refine this description in two ways. From a qualitative perspective, we emphasize the existence of more generic phase diagrams with a hybrid-hard phase, in which it is computationally easy to reach a nontrivial inference accuracy but computationally hard to match the information-theoretic optimal one. We support this discussion by quantitative expansions of the functional cavity equations that describe inference problems on sparse graphs, around their trivial solution. 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 generic evidence for the Bayes optimality of the message-passing algorithms. We clarify in particular the status of the symmetric SBM with four 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 two communities of different sizes, also known as the asymmetric Ising model, and describe quantitatively its computational gap as a function of its asymmetry, as well as a version of the SBM with two groups of q_{1} and q_{2} communities. We complement this study with numerical simulations of the belief propagation iterative algorithm, confirming that its behavior on large samples is well described by the cavity method.