  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.
