Federico Ricci-Tersenghi

Guilhem Semerjian

Lenka Zdeborová

Typology of phase transitions in Bayesian inference problems

Keywords:

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 theoretically 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. In 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 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, 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 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. 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.

I. INTRODUCTION

Problems of statistical inference where a signal is observed via noisy measurements appear ubiquitously in situations involving data analysis. It is intuitive that as the signal-to-noise ratio decreases, the recovery of the signal becomes harder. Quantifying the optimal performance is one of the main theoretical tools to provide performance guarantees in practical situations. Numerous models of statistical inference bear formal analogies to models of disordered systems and thanks to this connection methods from statistical physics were applied to inference problems, for reviews see e.g. [START_REF] Nishimori | Statistical Physics of Spin Glasses and Information Processing: An Introduction[END_REF][START_REF] Mézard | Physics, Information, Computation[END_REF][START_REF] Zdeborová | Statistical physics of inference: thresholds and algorithms[END_REF][START_REF] Bandeira | Notes on computational-to-statistical gaps: predictions using statistical physics[END_REF]. Sharp changes in behaviour, known as phase transitions, appear in many situations in physical systems. Due to the above connection it does not come as a surprise that various types of phase transitions were also identified in inference problems. The statistical and computational implications of the presence of phase transitions recently attracted attention in several fields.

A number of works, including the present one, focus on inference models defined on sparse graphs or hypergraphs where the signal is related to a (hidden) labeling of the nodes, and the graph is generated via a rule that depends on these labels. A paradigmatic example of this class is the stochastic block model (SBM) where nodes belong to "communities" and the probability of observing an edge between a pair of nodes depends on the communities of the two nodes. There is a long history of studies of this model, see e.g. [START_REF] Zdeborová | Statistical physics of inference: thresholds and algorithms[END_REF][START_REF] Moore | The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness[END_REF][START_REF] Abbe | Community detection and stochastic block models: recent developments[END_REF] and references therein, particularly because of its relevance in the context of complex networks [START_REF] Fortunato | Community detection in graphs[END_REF]. In terms of phase transitions in the SBM, the work of [START_REF] Decelle | Phase transition in the detection of modules in sparse networks[END_REF][START_REF] Decelle | Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications[END_REF] was particularly influential as it identified three phases -undetectable, hard and easy -and located quantitatively transitions between them. In the undetectable phase inference better than random guessing is not possible, in the hard phase it is information-theoretically possible, but known algorithms are not able to perform better than random guesses (depending on parameters of the model, this phase is sometimes missing), in the easy phase known algorithms match the information-theoretically optimal performance that is in this case strictly better than random guesses. Another example of inference problems on sparse hyper-graphs are the planted constraint satisfaction problems with various types of constraints [START_REF] Krzakala | Hiding Quiet Solutions in Random Constraint Satisfaction Problems[END_REF][START_REF] Zdeborová | Quiet planting in the locked constraint satisfaction problems[END_REF][START_REF] Abbe | Conditional Random Fields, Planted Constraint Satisfaction and Entropy Concentration[END_REF][START_REF] Feldman | On the Complexity of Random Satisfiability Problems with Planted Solutions[END_REF]. Planted constraint satisfaction problems are instrumental in studies of average algorithmic complexity [START_REF] Feige | Relations Between Average Case Complexity and Approximation Complexity[END_REF], hardness of finding a solution [START_REF] Barthel | Hiding Solutions in Random Satisfiability Problems: A Statistical Mechanics Approach[END_REF] and refutation of satisfiability formulas. The same three phases explained above in the SBM example have also been found in planted constraint satisfaction problems, as well as in many other "dense" inference problems in which the signal is observed through all pairs of variables, not only the edges of a sparse graph (see [START_REF] Zdeborová | Statistical physics of inference: thresholds and algorithms[END_REF] for a review).

This paper provides a more detailed picture of these phase transitions. We emphasize indeed the existence of hybrid-hard phases, in which efficient inference better than random guessing is possible, however, matching the information-theoretically optimal performance is computationally hard. This type of phase was identified in dense inference problems, see e.g. [START_REF] Lesieur | Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications[END_REF], but was missed in some previous studies of sparse problems [START_REF] Zdeborová | Quiet planting in the locked constraint satisfaction problems[END_REF]. We revisit the latter by mean of the cavity method, that relates the analytic description (in particular the optimal errors, as defined below) of inference problems on sparse graphs and hyper-graphs to reconstruction problems on trees [START_REF] Mossel | Reconstruction on Trees: Beating the Second Eigenvalue[END_REF][START_REF] Janson | Robust reconstruction on trees is determined by the second eigenvalue[END_REF][START_REF] Mézard | Reconstruction on Trees and Spin Glass Transition[END_REF][START_REF] Borgs | The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels[END_REF][START_REF] Sly | Reconstruction of Random Colourings[END_REF][START_REF] Sly | Reconstruction for the Potts model[END_REF] (the local limit of the graphs in the large size limit). These tree problems are solved exactly by fixed point equations whose unknown (called order parameter) are functions (more precisely probability distributions), at variance with their dense counterparts where the order parameters are finite dimensional. We will focus on problems where the undetectable phase exists at small signal to noise ratio, which translates into the existence of a so-called non-informative (or trivial) fixed point of the corresponding cavity equations (in such cases there exists a close connection between the inference problems and the associated uniformly random models [START_REF] Krzakala | Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems[END_REF][START_REF] Coja-Oghlan | Information-theoretic thresholds from the cavity method[END_REF][START_REF] Coja-Oghlan | Charting the replica symmetric phase[END_REF] through the notion of quiet planting). Our main technical contribution in this paper is a systematic perturbative expansion of the cavity equations around the trivial fixed point, in the neighborhood of the so-called Kesten-Stigum transition where it looses its stability. Similar expansions can be found in [START_REF] Borgs | The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels[END_REF][START_REF] Sly | Reconstruction for the Potts model[END_REF][START_REF] Coja-Oghlan | Charting the replica symmetric phase[END_REF] but our results are either valid for more general models or pushed to an higher order in the perturbation series. This technical tool allows us to clarify several features of the phase diagrams of inference and tree reconstruction problems.

For the symmetric stochastic block model with q groups (or the tree reconstruction of the q state Potts model), it was known that the hard phase does not exist for 2 and 3 groups (in other words the Kesten-Stigum bound on reconstruction is tight), whereas it always exists for 5 and more groups [START_REF] Sly | Reconstruction for the Potts model[END_REF]. In the intermediate case of q = 4, whose status remained unclear up to now, we provide an explicit condition on the degree distribution and the ferromagnetic (or assortative) character of the model to distinguish these two qualitatively different behaviors.

We also study the asymmetric SBM with two groups of different sizes (but equal average degree) and derive conditions on the asymmetry that induces the appearance of the hard phase. We recover the critical fraction 1/2 -1/ √ 12 for the size of the smaller group below which the hard phase exists, that appeared in related studies in the dense regime [START_REF] Lesieur | Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications[END_REF][START_REF] Barbier | Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula[END_REF] or in the limit of large degrees [START_REF] Caltagirone | Recovering asymmetric communities in the stochastic block model[END_REF][START_REF] Lelarge | Fundamental limits of symmetric low-rank matrix estimation[END_REF]; quite strikingly this critical asymmetry does not depend on the degree distribution. This phenomenon was also studied in the tree reconstruction perspective under the name of asymmetric Ising model [START_REF] Mossel | Reconstruction on Trees: Beating the Second Eigenvalue[END_REF][START_REF] Borgs | The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels[END_REF].

Based on this expansion, we also conclude that the hybrid-hard phase always exists in a very generic class of sparse inference models where Boolean variables are observed through k-uplets, for any k, as long as they preserve a global symmetry between the two possible values of the variables. This class encompasses a large part of the Boolean occupation problems of [START_REF] Zdeborová | Quiet planting in the locked constraint satisfaction problems[END_REF]. More precisely, in that class of models we rule out the existence of a hard phase that would not be accompanied by the hybrid-hard phase.

Our analytical findings are confirmed by running Belief Propagation (BP) on large instances of the corresponding problems, thus providing a strong evidence that the analytical solution obtained in the thermodynamical limit is also of practical relevance for problems of large but finite size.

The two papers [START_REF] Liu | Reconstruction for the asymmetric Ising model on regular trees[END_REF][START_REF] Liu | The Tightness of the Kesten-Stigum Reconstruction Bound of Symmetric Model with Multiple Mutations[END_REF] that appeared while we were finishing the present work have some overlap with ours. The authors study indeed the reconstruction problem on regular d-ary trees and provide expansions around the Kesten-Stigum transition, for the asymmetric Ising model and a q-state Potts model whose symmetry is partially broken. While the results of [START_REF] Liu | Reconstruction for the asymmetric Ising model on regular trees[END_REF][START_REF] Liu | The Tightness of the Kesten-Stigum Reconstruction Bound of Symmetric Model with Multiple Mutations[END_REF] are rigorous our expansions are more generic, pushed to an higher order, and put to use in connection with the inference problems on graphs.

The rest of the paper is organized as follows. In Sec. II we present in generic terms the structure describing the performance of optimal and efficient estimators in inference problems, review the well-known phase diagrams that have been deduced from it, and explain the more complicated possible scenarios that can be observed. In Sec. III we define a family of inference problems on sparse (hyper)graphs, introduce the cavity equations that describe them and explain their link to the tree reconstruction problem; for the convenience of the reader we then summarize our main results in Sec. III D. The latter have been obtained by systematic moment expansions of the functional cavity equations, that are presented in Sec. IV for arbitrary discrete variables with pairwise interactions, and in Sec. V for boolean variables with k ≥ 2-wise interactions; the more technical parts of these computations are deferred to a series of Appendices. Sec. VI is then devoted to numerical experiments with Belief Propagation on finite size samples, and finally we draw some conclusions and perspectives in Sec. VII.

II. TYPOLOGY OF PHASE TRANSITIONS

This first Section is dedicated to the presentation of our qualitative results on the variety of possible phase diagrams in inference problems. We shall first briefly review the Bayesian perspective on inference and the way statistical mechanics handles it, staying at an abstract level of description (concrete examples will be introduced in Sec. III). The typology of phase transitions will then naturally follow from this discussion, as well as the quantitative computations that can be performed on concrete examples as first steps towards this classification (which will form the core of the rest of the paper).

A. Bayesian inference problems

In a statistical inference problem a ground-truth vector s * ∈ R N is to be inferred from some observations (or data) denoted G, that are correlated to s * . In the Bayesian setting s * is a random variable whose distribution is called "prior", and G is a random variable with a conditional law P (G|s * ), that correlates it to the ground-truth. An observer provided with a sample of G, and with the knowledge of the model that generated it (i.e. of the prior distribution and of P (G|s * )) must base her inference of s * on the posterior distribution that follows from Bayes' theorem

P (s|G) = 1 Z(G) P (G|s) N i=1 P 0 (s i ) , (1)
where we assumed for simplicity a prior distribution P 0 factorized on the components of the vector, and Z(G) is a normalizing constant. The observer uses an estimator s(G) that should ideally be "close" to s * . Which estimator is optimal depends on the definition of "closeness" between s(G) and the true value s * . To clarify this point let us denote the marginal probability distributions of the posterior as

µ i (s i ) = {sj } j =i P (s|G) . (2)
If the distance between s(G) and s * is measured in terms of the mean squared error MSE = i ( s is * i ) 2 /N , then the optimal estimator (that minimizes the MSE) is simply given by the means of the marginals

s i = si s i µ i (s i ) , (3)
and the error achieved by this estimator is called the minimum mean-squared error (MMSE). When the variables s i belong to a discrete set χ (as will be the case in this paper) another meaningful definition of similarity between s(G) and s * is the mean overlap MO = i δ ŝi,s * i /N . The estimator that maximizes the mean overlap is given by the value of s i for which the marginal is the largest, namely

s i = argmax µ i (s i ) . (4)
We are interested in this paper in phase transitions, i.e. qualitative changes of the behavior of such inference problems and non-analyticities in their optimal error. These can only occur in the so-called thermodynamic limit N → ∞; the dimensionality of G must be scaled appropriately for this limit to be non-trivial, in such a way that the signal-to-noise ratio (SNR) (whose precise definition depends on the specific problem considered) that measures the quantity of information on s * conveyed by G remains finite in the limit. We shall focus on a particularly interesting and challenging class of problems for which there exists a non-trivial low-SNR phase in which the inference problem cannot be solved more precisely than by using only the prior information; we shall call this phase undetectable, as the ground-truth s * has asymptotically no effect on the posterior distribution. We will call accuracy a ≥ 0 of an estimation procedure a measure of the additional information it exploits in the posterior distribution with respect to the prior, in such a way that a = 0 in the undetectable phase. The precise definition of the accuracy is a model-dependent problem, on which we shall come back in Sec. IV K, with rather subtle pitfalls (see for example [START_REF] Abbe | Community detection and stochastic block models: recent developments[END_REF] for a discussion of this point): for instance when the problem admits an exact symmetry the marginals of the posterior can be strictly equal to the prior distribution for arbitrary large SNR. This is for instance the case of the symmetric SBM, which is invariant under the permutation of the labels; in such a case the definition of the distance between s * and s(G) must be adapted to break explicitly the symmetry, by considering for instance the overlap modulo an arbitrary global permutation of the labels of the vertices.

B. Statistical mechanics description

Several Bayesian inference problems have recently been studied via statistical mechanics methods, and a good part of the predictions thus obtained have been confirmed rigorously; our goal here is not to review these results (see for instance [START_REF] Zdeborová | Statistical physics of inference: thresholds and algorithms[END_REF][START_REF] Bandeira | Notes on computational-to-statistical gaps: predictions using statistical physics[END_REF][START_REF] Moore | The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness[END_REF][START_REF] Abbe | Community detection and stochastic block models: recent developments[END_REF]) but to emphasize their common formal structure that is at the origin of the few possible universality classes of phase diagrams.

Consider, in this abstract perspective, an inference problem parametrized by a signal-to-noise ratio c. In the statistical mechanics approach the accuracy of the Bayes-optimal estimator is expressed as a variational problem: one derives (with the cavity or replica method) a so-called free-energy f , function of c and of an order parameter a (an object whose nature depends on the problem under study). This free-energy has to be minimized with respect to the order parameter, and the optimal accuracy is then a function of the location of this global minimum (the minimal free-energy yields instead the mutual information between the signal and the observations). In "dense models" (those in which there are much more than N measurements, each giving a weak information on the signal), see e.g. [START_REF] Lesieur | Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications[END_REF], the order parameter is a scalar (or a finite dimensional vector); in the sparse models studied later in this paper the order parameter is functional, yet the qualitative behavior is the same. To simplify this formal discussion let us stick to a scalar order parameter, and furthermore use the accuracy a ≥ 0 as the order parameter itself, with the minimal value a = 0 corresponding to the trivial, uninformative estimator (exploiting only the prior and not the observations). We shall write the free-energy as

f (a, c) = Φ(a, c) - a 2 2 , (5)
the motivation for the subtraction of the second term will be clarified below. The location of the global minimum of f with respect to a, denoted a * (c), is thus the prediction for the accuracy of the optimal estimator, irrespectively of its computational complexity. The cavity method also enlightens the computational complexity of the inference problems: as a matter of fact the derivation of the free-energy is tightly linked to the analysis of an efficient iterative algorithm (called Approximate Message Passing [START_REF] Donoho | Message-passing algorithms for compressed sensing[END_REF][START_REF] Bayati | The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing[END_REF] in the dense case, or Belief Propagation in the sparse regime [START_REF] Kschischang | Factor graphs and the sum-product algorithm[END_REF]), and provides a dynamical map that describes the discrete time evolution of the order parameter during the execution of the algorithm. In our abstract setting this yields an accuracy a (n) after n steps of the algorithm, that evolves according to a (n) = ϕ(a (n-1) , c) , [START_REF] Abbe | Community detection and stochastic block models: recent developments[END_REF] with the initial condition a (0) = ε, where ε > 0 is an infinitesimal positive constant: initially the algorithm only knows the prior on the signal, and at each time step uses the observation to iteratively update and improve the accuracy of its belief on the true value of the signal. We shall denote a alg (c) = lim a (n) as n → ∞ the accuracy ultimately reached by this algorithm.

The fundamental connection between the information-theoretically optimal accuracy and the description of the iterative algorithm is expressed mathematically in our setting by the relation ϕ(a, c) = Φ (a, c) , [START_REF] Fortunato | Community detection in graphs[END_REF] where here and in the following the primes denote derivatives with respect to the variable a. This equation implies indeed a tight connection between the static description in terms of the free-energy f (a, c) and the dynamical one in terms of the iteration function ϕ(a, c): the stationary points of the former correspond to the fixed points of the latter.

As mentioned previously we focus in this paper on problems which admit an undetectable phase; this translates in the abstract formalism employed here into the assumption that a = 0 is, for all values of the SNR c, a fixed point of the iteration [START_REF] Abbe | Community detection and stochastic block models: recent developments[END_REF], that we shall call the trivial or non-informative fixed point. Equivalently a = 0 is a stationary point of the free-energy f (a, c).

C. Possible phase diagrams

It should be clear at this point that the description of the phase transitions and the classification of the possible phase diagrams is nothing else than a bifurcation analysis. As the SNR c is varied the functions f (a, c) (resp. ϕ(a, c)) evolve in a smooth way; their stationary (resp. fixed) points also do, except at bifurcations where their number and nature can change in a singular way. The qualitative aspects of such a bifurcation diagram do not depend on the details of the function f (a, c), but only on its behavior close to the bifurcations (essentially the order and sign of the first non-vanishing derivatives), which explains the high level of universality among inference problems which can have very different origins.

Let us now describe in this perspective the phase transitions in inference problems, interpreted as bifurcations for the stationary points of f (a, c); among the possibly many stationary points two (which can coincide) will play a particular role: a * (c), the global minimum of f , that gives the information-theoretically best possible accuracy, and a alg (c), the fixed point reached by iterations starting infinitesimally close to the trivial one, as it corresponds to the accuracy reachable by an efficient algorithm.

As a = 0 is assumed here to be a fixed point for all values of c, and as the algorithm starts infinitesimally close to it, the local stability of a = 0 under the iterations (6) yields a crucial information on the accuracy a alg (c) reached by the algorithm: if a = 0 is stable the iterations will drive the algorithm to the trivial accuracy, then a alg (c) = 0, if not the dynamical system flows away from this fixed point and one reaches a alg (c) > 0. This stability can be determined very easily by expanding [START_REF] Abbe | Community detection and stochastic block models: recent developments[END_REF] at first order in a,

a (n) ≈ ϕ (0, c) a (n-1) , (8)
which shows that a = 0 is stable if and only if ϕ (0, c) < 1 (as a (n) ≥ 0 we can assume ϕ (0, c) ≥ 0). As c represents here a signal-to-noise ratio increasing values of c tends to destabilize the trivial fixed point. We shall thus define the so-called KS threshold (the abbreviation stands for Kesten-Stigum [START_REF] Kesten | Additional Limit Theorems for Indecomposable Multidimensional Galton-Watson Processes[END_REF] and is elucidated below) c KS as the largest signal-to-noise ratio c for which a = 0 is a stable fixed point; as mentioned above for c < c KS one has a alg (c) = 0, the algorithm will not be able to infer the underlying signal better than a random guess from the prior. On the other hand for c > c KS the iterative algorithm reaches a non-trivial accuracy a alg (c) > 0 and provides a strictly positive correlation between the ground truth signal and its estimator (but not necessarily as good as the optimal estimator, see the discussion below).

A moment of thought reveals that this change of stability of the trivial fixed point at c KS must be accompanied by a modification in the total number of fixed points, as the free-energy f (a, c) is smooth. Keeping in mind the restriction a ≥ 0, the two simplest global bifurcation diagrams that can arise are depicted in the lower panels of Fig. 1, where all the fixed points are represented as a function of the SNR c, with solid (resp. dashed) lines when they are stable (resp. unstable).

The bifurcation diagram presented in the left part of Fig. 1 corresponds to a so-called continuous (2nd order) phase transition. For all values of c there is a single stable fixed point, with a trivial accuracy when c < c KS and a non-trivial one for c > c KS . The optimal accuracy a * (c) and the algorithmic one a alg (c), depicted with red and blue lines in the upper panels of Fig. 1, coincide for all values of the SNR c. The transition at c KS thus separates an undetectable phase (for c < c KS no estimator can detect the signal as a * (c) = 0) from an easy phase (for c > c KS the iterative efficient algorithm matches the optimal performance as a alg (c) = a * (c) > 0).

The next possible bifurcation diagram, in the order of increasing complexity, is presented on the right of The "standard" scenarios in terms of the Bayes-optimal (a * , in blue) and algorithmic (a alg , in red) performance. Bottom: The "standard" scenarios in terms of the fixed points of eq. ( 6). Stable fixed points are in full line, unstable ones are dashed. In all panels the accuracy a is plotted as a function of the signal-to-noise ratio c. The thresholds csp, cIT, cKS and c alg , as defined in the text, are marked on the horizontal axes. ). One concludes in this case that the undetectable phase (for c < c IT ) and the easy phase (for c > c KS ) are separated by an hard phase (for c ∈ [c IT , c KS ]) in which a non-trivial accuracy is information theoretically possible (a * (c) > 0) yet the iterative algorithm does not provide any correlation with the signal (a alg (c) = 0). One can easily imagine more and more complicated bifurcation diagrams that will be exhibited by free-energies with more and more stationary points; we shall content ourselves with the next possibility, depicted in Fig. 2. As shown in its lower part the branch of the non-trivial stable fixed point that appears continuously for c > c KS undergoes a bifurcation at an algorithmic spinodal c alg > c KS , while the high accuracy branch disappears discontinuously at the spinodal c sp < c alg (the spinodal c sp can occur after or before c KS , as shown in the left and right part of Fig. 2). The algorithmic accuracy a alg (c) is in this case vanishing for c < c KS , growing continuously on the interval [c KS , c alg ], and jumping discontinuously at c alg . As we assumed here the existence of a single stable fixed point for c > c alg the algorithmic accuracy coincides then with a * (c) (i.e. the jump reaches the optimal value). To determine the information-theoretically optimal accuracy in the presence of two stable fixed points of the recursion one has to compare the values of the corresponding local minima of the free-energy f (a, c). Let us call c IT the informationtheoretic transition at which these two free-energies cross each other, inducing a discontinuity in the accuracy a * (c) of the global minimum of the free-energy. The left and right part of Fig. 2 distinguish further two different scenarios. On the left one has c IT > c KS , and the four regimes separated by the transitions c KS < c IT < c alg shall be called, for increasing values of c: undetectable, easy, hybrid-hard, easy; on the right c IT < c KS and the four phases separated by c IT < c KS < c alg are: undetectable, hard, hybrid-hard, easy. In this terminology we define an undetectable phase by The "new" scenarios in terms of the Bayes-optimal (a * , in blue) and algorithmic (a alg , in red) performance. Bottom: The "new" scenarios in terms of the fixed points of eq. ( 6). Stable fixed points are in full line, unstable one are dashed. In all panels the accuracy a is plotted as a function of the signal-to-noise ratio c. The thresholds csp, cIT, cKS and c alg , as defined in the text, are marked on the x-axes. The KS threshold cKS here is strictly smaller than the algorithmic one c alg . We note that the thresholds can also be ordered as csp < cKS < cIT < c alg .

the condition a * (c) = a alg (c) = 0, an easy phase by a * (c) = a alg (c) > 0, a hard phase by a * (c) > a alg (c) = 0, and an hybrid-hard phase by a * (c) > a alg (c) > 0. The hybrid character of this phase arises from the simultaneous easiness to beat the trivial accuracy of the uninformative estimator (a alg (c) > 0), and hardness of achieving the optimal accuracy (a * (c) > a alg (c)).

Let us make a few remarks on the classification of possible phase diagrams for inference problems we just presented:

• The scenarios described in this section and more generally in this paper are the simplest ones, and they do not by far cover all possibilities: one can always devise more complicated free-energies f (a, c) with more distinct stationary points and/or more bifurcations, yielding for instance several hard phases separated by easy regimes; we shall not discuss these more complicated situations as they did not arise in any of the cases we analyzed (see [START_REF] Measson | Maxwell Construction: The Hidden Bridge Between Iterative and Maximum a Posteriori Decoding[END_REF] for such examples in the related context of error-correcting codes).

• We defined the computational easiness or hardness of inference with respect to one specific efficient algorithm (Approximate Message Passing or Belief Propagation), as to this day there are no better efficient (i.e. running in polynomial time) algorithms known for the problems that are NP-hard from the worst case computational complexity point of view. It remains of course a very challenging open question to prove or disprove (under some computational complexity hypothesis) the existence of more accurate efficient algorithms than these message passing ones.

• The two simplest scenarios presented in Fig. 1 are well known in the context of inference on sparse random graphs; for instance the study of the symmetric stochastic block model in [START_REF] Decelle | Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications[END_REF] demonstrated a continuous (left panel) phase transition for q ≤ 3 communities, and a discontinuous one (right panel) for q ≥ 5. The more complicated phase diagrams of Fig. 2 were until now (as far as we know) only discussed in the context of dense inference problems (in particular for constrained low rank matrix estimation, see figure 3 and 6 in [START_REF] Lesieur | Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications[END_REF]). However, we shall see in the rest of the paper that they do also occur naturally in sparse problems, a fact that remained previously unobserved.

• It is known that for inference problems for which a = 0 is a fixed point of ( 6) there is a close relation between the inference (planted) model and the model with random uncorrelated disorder (see for instance [START_REF] Coja-Oghlan | Information-theoretic thresholds from the cavity method[END_REF]). In random optimization and constraint satisfaction problems some of the equilibrium phase transitions described in the literature correspond to phase transitions defined above. Notably, the dynamical phase transition [START_REF] Krzakala | Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems[END_REF], sometimes referred to as the mode-coupling theory transition [START_REF] Parisi | Mean-field theory of hard sphere glasses and jamming[END_REF] in the literature on the mean-field theory of structural glasses, and referred to as the reconstruction threshold [START_REF] Mézard | Reconstruction on Trees and Spin Glass Transition[END_REF] in the theory of reconstruction on tree, corresponds to c d = min(c KS , c sp ). This is indeed the smallest SNR for which a non-trivial fixed point does exist. The condensation phase transition from random constraint satisfaction problems [START_REF] Krzakala | Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems[END_REF], sometimes referred to as the Kauzmann ideal glass transition in the mean-field theory of structural glasses [START_REF] Parisi | Mean-field theory of hard sphere glasses and jamming[END_REF], correspond to c cond = min(c KS , c IT ). The KS phase transition would be referred to as the de Almeida-Thouless instability in the theory of spin glasses [START_REF] De Almeida | Stability of the Sherrington-Kirkpatrick Solution of a Spin-Glass Model[END_REF] and corresponds to the point starting from which iterative message passing algorithms such as belief propagation cease to converge on random instances of the corresponding problems. This correspondence between planted and random instances does not hold for all phase transitions: for instance the satisfiability [START_REF] Mézard | Analytic and Algorithmic Solution of Random Satisfiability Problems[END_REF] of random constraint satisfaction problems has no counterpart in the planted/inference setting, neither does the algorithmic spinodal c alg > c KS of inference problems in the random ensembles. This correspondence also breaks down for models where a = 0 is not a fixed point of ( 6), most notably satisfiability of random Boolean formulas.

D. Expansions around the trivial fixed point

The classification of the phase diagrams presented above relies on a global bifurcation analysis, which requires the identification of all fixed points of Eq. ( 6) and the study of their domain of existence as a function of the SNR parameter c. This is relatively easy to do when the order parameter is a scalar, or a finite-dimensional object, and when the recursion function ϕ can be studied explicitly. This global analysis becomes much more difficult for sparse inference models, because the order parameter is infinite-dimensional in this case. The main methodological contribution of the present paper is a generalization to the sparse case of a local bifurcation analysis of the trivial fixed point in the neighborhood of the Kesten-Stigum transition. For pedagogical reasons let us first explain here how this analysis is performed in the case of a scalar order parameter (as done for instance in section IV.C.3 of [START_REF] Lesieur | Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications[END_REF]), which will help to understand the strategy followed in the functional case.

The location of the Kesten-Stigum transition c KS , defined by the condition ϕ (0, c KS ) = 1, was obtained through the linearization of [START_REF] Abbe | Community detection and stochastic block models: recent developments[END_REF]. In order to study the non-trivial fixed point in the neighborhood of this transition we shall expand the fixed-point equation a = ϕ(a, c) at the next order in a, to obtain

a = ϕ (0, c) a + 1 2 ϕ (0, c) a 2 + O(a 3 ) . (9)
In the neighborhood of c KS the derivative ϕ (0, c) is close to 1, we shall hence trade the SNR c for a parameter defined by ϕ (0, c) = 1+ , such that = 0 corresponds to the KS transition, > 0 (resp. < 0) to the high SNR (resp. low SNR) regime. If the second order derivative of ϕ does not vanish exactly at c KS we can rewrite this equation at lowest order as

a = a + a + v a 2 , (10)
where we defined v = ϕ (0, c KS )/2 = 0. The non-trivial solution of this equation is obviously a = -/v; at this point it is crucial to remember the positivity condition a ≥ 0 (without it the bifurcation diagrams would be qualitatively different). Indeed this requirement implies that if v < 0 the non-trivial perturbative fixed point exists for > 0, in the high SNR regime; this case corresponds both to the continuous transition (left panel of Fig. 1), and to the more complicated phase diagrams of Fig. 2. On the contrary if v > 0 it is in the low SNR regime ( < 0) that it exists, as in the first order transition case depicted in the right panel of Fig. 1.

Let us emphasize the limitations of such a local study: by definition it can only provide perturbative information on the phase diagram, in the neighborhood of the KS transition and for the branch of fixed point that coalesces with the trivial one; if this is enough to distinguish the first order transition scenario (Fig. 1 right) and exclude the three other ones when v > 0, in the opposite case one cannot decide between the second order transition (Fig. 1 right) and the scenarios of Fig. 2 solely from the condition v < 0, as non-perturbative (finite a) features further differentiate these cases.

We shall develop in the sparse case an expansion that goes one order further, corresponding to an equation of the form

a = a + a + v a 2 + w a 3 . ( 11
)
The motivations for continuing the expansion to this order are twofold. On the one hand, there are important inference problems for which v = 0 exactly (most notably the symmetric stochastic block model for q = 4 groups, both in the sparse [START_REF] Sly | Reconstruction for the Potts model[END_REF] and in the dense regime [START_REF] Lesieur | Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications[END_REF]). In that case the non-trivial solution is a = -/w and it is the sign of w (if w = 0) that allows to determine whether the perturbative non-trivial fixed point exist in the low or high SNR phase (the argument of the square root must be positive). On the other hand, some problems have, in addition to the SNR, another continuously varying parameter; this is in particular the case of the asymmetric 2 group stochastic block model (or asymmetric Ising model in the tree reconstruction language), where the asymmetry between the sizes of the two groups can be tuned independently of the SNR. Depending on this asymmetry parameter, that we shall denote m in the following, the type of transition changes from second to first order, which comes from a change of sign of v when m crosses a critical value m c . Having pushed the expansion to the third order will thus allow us to study the neighborhood of the "tri-critical" point ( , m) = (0, m c ) in parameter space, where the nature of the Kesten-Stigum transition changes. Taking simultaneously the limits → 0 and m → m c with well-chosen scalings the last three terms of [START_REF] Zdeborová | Quiet planting in the locked constraint satisfaction problems[END_REF] will indeed be of the same order (this will be further discussed in Sec. IV I).

III. CAVITY EQUATIONS AND MAIN RESULTS

In the previous Section we have discussed the classification of phase transitions and phase diagrams of Bayesian inference problems, relying on the bifurcation analysis for a scalar order parameter; dense inference problems can indeed be reduced to such a scalar (or more generically finite-dimensional) representation in the large-size limit. In the rest of the paper we shall turn instead to inference problems defined on sparse graphs, for which the corresponding order parameter becomes functional. In this Section we shall introduce two exemplary cases of these sparse inference problems, that cover the main applications of this paper, state in a rather generic way the cavity formalism that can be used to handle them, briefly explain its interpretation and finally present our main results, as obtained in the later Sections via an expansion of the cavity equations around their trivial solution.

A. Definitions of two exemplary inference problems on sparse (hyper)graphs

Stochastic Block Model

The Stochastic Block Model (SBM) is a random graph ensemble which generates networks with a community structure [START_REF] Fienberg | Categorical data analysis of single sociometric relations[END_REF][START_REF] Holland | Stochastic blockmodels: First steps[END_REF][START_REF] Bollobás | The phase transition in inhomogeneous random graphs[END_REF]. It is specified by the following parameters: N , the number of vertices (or nodes) of the graph G = (V, E), q the number of communities, η = (η 1 , . . . , η q ) a prior probability distribution on the communities, and c = {c στ } a q × q symmetric matrix (not to be confused with the SNR we also denoted c in Sec. II). A graph of this ensemble is generated by drawing for each vertex i ∈ V a label σ i ∈ {1, . . . , q}, independently at random with probability η σi ; this label represents the community of the vertex. Once the labels σ = (σ 1 , . . . , σ N ) are chosen, each of the N (N -1)/2 possible edges i, j between pairs of distinct vertices is included in the set of edges E of the graph with probability c σi,σj /N . The inference problem we shall consider is the determination of the labels σ (up to a potential symmetry between communities) from the mere observation of the graph G and from the knowledge of the parameters η and c.

We are in particular interested in the large-size limit N → ∞, taken for a fixed value of the affinity matrix c. In this limit the degree of a vertex labelled σ becomes a Poisson random variable with average d σ = σ c σσ η σ ; the finiteness of these degrees justifies the name "sparse" given to this type of inference problems. The phase transitions in the Bayes-optimal inference in the sparse stochastic block model were studied in detail in [START_REF] Decelle | Phase transition in the detection of modules in sparse networks[END_REF][START_REF] Decelle | Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications[END_REF]. Large part of these results were confirmed rigorously in subsequent works, see e.g. [START_REF] Abbe | Community detection and stochastic block models: recent developments[END_REF][START_REF] Mossel | A proof of the block model threshold conjecture[END_REF][START_REF] Massoulié | Community detection thresholds and the weak Ramanujan property[END_REF][START_REF] Mossel | Belief propagation, robust reconstruction and optimal recovery of block models[END_REF][START_REF] Abbe | Detection in the stochastic block model with multiple clusters: proof of the achievability conjectures, acyclic BP, and the information-computation gap[END_REF].

We shall assume in the following that d σ = d independently of σ, in such a way that the degree of a vertex is uninformative of its label. This is the condition for the existence of an undetectable phase at small d, in which case the SBM is asymptotically contiguous to a purely random Erdös-Rényi graph of the same average degree and the optimal estimation of the labels can only rely on the prior distribution η.

Planted occupation models

We consider now the family of Constraint Satisfaction Problems (CSP) in which N Boolean variables, denoted σ = (σ 1 , . . . , σ N ) ∈ {0, 1} N , are required to satisfy simultaneously M constraints of the following form: the a-th constraint bears on a subset of k variables, denoted ∂a ⊂ {1, . . . , N }, and is satisfied by σ if and only if i∈∂a σ i ∈ S, where S ⊂ {0, 1, 2, . . . , k} defines the type of problem. The interpretation of σ i = 1 (resp. 0) as a site occupied by a particle (resp. empty) justifies the name of occupation model, each constraint restricting the number of particles adjacent to it (in the bipartite graph on N + M vertices with an edge put between i and a iff i ∈ ∂a) to belong to S. This family of CSPs contains as special cases the bicoloring of hypergraphs (when S = {1, . . . , k -1}) and XORSAT problems (also known as parity checks, when S = {0, 2, 4, . . . , } or S = {1, 3, 5, . . . , }). Random ensembles of occupation problems, in which the neighborhoods ∂a are drawn uniformly at random among the N k possible ones, have been studied e.g. in [START_REF] Zdeborová | Constraint satisfaction problems with isolated solutions are hard[END_REF].

An inference problem can be associated to these occupation models if instead of this random ensemble of CSPs one considers its planted version, in which one first chooses a configuration σ, drawing independently each σ i with a prior probability distribution η σi (with η 0 + η 1 = 1), then draws the M neighborhoods ∂a uniformly among those that are satisfied by σ (i.e. such that i∈∂a σ i ∈ S). The inference problem is then to reconstruct the planted configuration σ solely from the observation of the bipartite graph linking variables to constraints and the knowledge of the subset S. Special cases of planted occupation problems and their corresponding phase transition have been studied previously in [START_REF] Zdeborová | Quiet planting in the locked constraint satisfaction problems[END_REF][START_REF] Angelini | Spectral detection on sparse hypergraphs[END_REF].

In this paper we shall focus on "symmetric" planted occupation models, in the sense that η 0 = η 1 = 1/2 and the set S of the number of allowed particles is invariant under the exchange of occupied and empty sites (i.e. we assume that n ∈ S if and only if kn ∈ S); this condition ensures the existence of an undetectable phase if the density of constraints α = M/N is small enough.

B. Cavity equations and free-entropy functional

We shall now present a formalism, known as the cavity method [START_REF] Mézard | Physics, Information, Computation[END_REF][START_REF] Mézard | The Bethe lattice spin glass revisited[END_REF], that allows to deal with inference problems on sparse random (hyper-)graphs. We will first state the approach in a formal way, with a level of generality that encompasses the two examples above, before discussing its interpretation and justification in the next subsection.

The cavity equations depend on the following list of parameters:

• χ, a discrete alphabet of spins of cardinality q, taken for concreteness to be χ = {1, . . . , q};

• a probability distribution η on χ, i.e. (η 1 , . . . , η q ) with η σ ≥ 0 and σ η σ = 1;

• a probability law p on non-negative integers representing the degree distribution of variables, and its size-biased version

p = ( + 1)p +1 E[ ] , (12)
where E[ ] = p is the average degree;

• an integer k ≥ 2;

• a joint probability law p j (σ 1 , . . . , σ k ) on χ k , that we assume to be invariant under all the permutations of its arguments, and to have η as marginal laws for a single argument:

p j (σ 1 , . . . , σ k ) = p j (σ π(1) , . . . , σ π(k) ) ∀π ∈ S k , σ2,...,σ k p j (σ 1 , . . . , σ k ) = η σ1 . (13)
We shall also need the conditional version of this probability law, to be denoted

p c (σ 1 , . . . , σ k-1 |σ) = p j (σ 1 , . . . , σ k-1 , σ) 1 η σ
. As a consequence of the hypothesis made on p j this conditional law is invariant under the permutations of its k -1 first arguments, and fulfils the reversibility property:

p c (σ 1 , . . . , σ k-1 |σ)η σ = p c (σ, σ 2 , . . . , σ k-1 |σ 1 )η σ1 . ( 14
)
We denote by η and ν probability distributions on χ (i.e. q-dimensional vectors of positive reals that sum to one). We shall call conditional version of the cavity equations associated to the parameters (q, η, p , k, p j ) the following recursive relations on the 2q distributions {P

(n) τ (η), P (n) τ (ν)} τ ∈χ : P (n+1) τ (η) = ∞ =0 p d P (n) τ (ν 1 ) . . . d P (n) τ (ν ) δ(η -f (ν 1 , . . . , ν )) , (15)
P (n) τ (ν) = τ1,...,τ k-1 p c (τ 1 , . . . , τ k-1 |τ ) dP (n) τ1 (η 1 ) . . . dP (n) τ k-1 (η k-1 ) δ(ν -f (η 1 , . . . , η k-1 )) , (16)
where here and in the following unspecified summation over spin indices σ or τ are understood to run over χ, and n should be thought of as a time index along the recursion (the initial condition for n = 0 will be discussed below).

The functions f and f appearing above are called Belief Propagations (BP) recursions and are defined as follows: η = f (ν 1 , . . . , ν ) means

η σ = 1 z(ν 1 , . . . , ν ) η σ i=1 ν i σ ν σ , (17)
where z enforces the normalization of η, and where we denoted ν the uniform distribution on χ (i.e. ν σ = 1 q ). The other recursion function ν = f (η 1 , . . . , η k-1 ) is spelled out as

ν σ = 1 z(η 1 , . . . , η k-1 ) ν σ η σ σ1,...,σ k-1 p j (σ, σ 1 , . . . , σ k-1 ) k-1 i=1 η i σi η σi , (18)
with again z a normalizing factor. One can check easily that the hypotheses (13) made on the joint probability law p j implies that f (ν, . . . , ν) = η and f (η, . . . , η) = ν, hence that P

(n) τ (η) = δ(η -η), P (n)
τ (ν) = δ(νν) is a stationary solution of the cavity equations [START_REF] Barthel | Hiding Solutions in Random Satisfiability Problems: A Statistical Mechanics Approach[END_REF][START_REF] Lesieur | Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications[END_REF], that will be called trivial fixed point in the following.

Let us also define what we shall call the unconditional version of the cavity equations associated to the parameters (q, η, p , k, p j ), that bear on the 2 sequences of distributions P (n) (η) and P (n) (ν):

P (n+1) (η) = ∞ =0 p d P (n) (ν 1 ) . . . d P (n) (ν ) δ(η -f (ν 1 , . . . , ν )) z(ν 1 , . . . , ν ) , (19)
P (n) (ν) = dP (n) (η 1 ) . . . dP (n) (η k-1 ) δ(ν -f (η 1 , . . . , η k-1 )) z(η 1 , . . . , η k-1 ) (20)
where the functions f , z, f and z have been defined in [START_REF] Mossel | Reconstruction on Trees: Beating the Second Eigenvalue[END_REF][START_REF] Janson | Robust reconstruction on trees is determined by the second eigenvalue[END_REF], and the distributions P (n) (η), P (n) (ν) are required to have mean η and ν respectively:

dP (n) (η) η = η , d P (n) (ν) ν = ν . (21)
With the choice of normalization made in [START_REF] Mossel | Reconstruction on Trees: Beating the Second Eigenvalue[END_REF][START_REF] Janson | Robust reconstruction on trees is determined by the second eigenvalue[END_REF] one has z(ν, . . . , ν) = z(η, . . . , η) = 1, hence the normalization of the distributions P (n) and P (n) , as well as the conditions (21) on their averages, are preserved by the recursions of Eqs. [START_REF] Mézard | Reconstruction on Trees and Spin Glass Transition[END_REF][START_REF] Borgs | The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels[END_REF]. Note that the conditional and unconditional versions of the cavity equations are actually equivalent: one can go from one form to the other according to the relations

P (n) (η) = τ η τ P (n) τ (η) , P (n) τ (η) = η τ η τ P (n) (η) , (22)
for all n, and similarly for P (n) ,

P (n) (ν) = τ ν τ P (n) τ (ν) , P (n) τ (ν) = ν τ ν τ P (n) (ν) . (23)
In particular the trivial fixed point, in the unconditional version of the cavity equations, corresponds to

P (n) (η) = δ(η -η), P (n) (ν) = δ(ν -ν).
Let us conclude this formal statement of the cavity formalism by the introduction of a functional, called free-entropy, that associates in its unconditional form a real value to a pair (P, P ) of distributions that satisfy [START_REF] Sly | Reconstruction of Random Colourings[END_REF] according to φ(P, P ) = -E[ ] dP (η)d P (ν) z e (η, ν) ln z e (η, ν)

+ E[ ] k dP (η 1 ) . . . dP (η k ) z c (η 1 , . . . , η k ) ln z c (η 1 , . . . , η k ) + ∞ =1 p d P (ν 1 ) . . . d P (ν ) z v (ν 1 , . . . , ν ) ln z v (ν 1 , . . . , ν ) , (24)
where

z e (η, ν) = σ η σ ν σ ν σ , (25)
z c (η 1 , . . . , η k ) = σ1,...,σ k p j (σ 1 , . . . , σ k ) k i=1 η i σi η σi , (26)
z v (ν 1 , . . . , ν ) = σ η σ i=1 ν i σ ν σ . ( 27
)
An equivalent form in the conditional formalism reads

φ({P σ , P σ } σ∈χ ) = -E[ ] σ η σ dP σ (η)d P σ (ν) ln z e (η, ν) + E[ ] k σ1,...,σ k p j (σ 1 , . . . , σ k ) dP σ1 (η 1 ) . . . dP σ k (η k ) ln z c (η 1 , . . . , η k ) + ∞ =1 p σ η σ d P σ (ν 1 ) . . . d P σ (ν ) ln z v (ν 1 , . . . , ν ) . ( 28
)
Note that these expressions of φ are variational, in the sense that their derivatives with respect to their arguments vanish when the latter are fixed point solutions of the cavity recursions (i.e. [START_REF] Barthel | Hiding Solutions in Random Satisfiability Problems: A Statistical Mechanics Approach[END_REF][START_REF] Lesieur | Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications[END_REF] in the conditional version, [START_REF] Mézard | Reconstruction on Trees and Spin Glass Transition[END_REF][START_REF] Borgs | The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels[END_REF] in the unconditional one). They are, however, well-defined even if their arguments are not solutions of the cavity equations (as long as the condition (21) is satisfied); this property has been recently exploited in [START_REF] Coja-Oghlan | Information-theoretic thresholds from the cavity method[END_REF][START_REF] Coja-Oghlan | Charting the replica symmetric phase[END_REF], we shall come back on this point in Sec. IV E. Let us also mention that our choices of normalization leads to φ = 0 on the trivial fixed point of the cavity equations.

C. Interpretation of the cavity equations

The cavity equations written above arise in the context of several slightly different and delicately intertwined problems, in particular in the study of graphical models on random structures, tree reconstruction problems, and inference on sparse graphs. We shall not attempt here an exhaustive discussion of these various interpretations and refer the reader to the literature [START_REF] Zdeborová | Statistical physics of inference: thresholds and algorithms[END_REF][START_REF] Abbe | Conditional Random Fields, Planted Constraint Satisfaction and Entropy Concentration[END_REF][START_REF] Mézard | Reconstruction on Trees and Spin Glass Transition[END_REF][START_REF] Krzakala | Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems[END_REF][START_REF] Coja-Oghlan | Information-theoretic thresholds from the cavity method[END_REF] for more details on these various perspectives and the connections between them, and instead give a brief description of two interpretations in order to clarify the meaning of our main results to be discussed below.

Reconstruction on trees

The first interpretation of the cavity equations we shall discuss concerns the tree reconstruction problem [START_REF] Mossel | Reconstruction on Trees: Beating the Second Eigenvalue[END_REF][START_REF] Janson | Robust reconstruction on trees is determined by the second eigenvalue[END_REF][START_REF] Mézard | Reconstruction on Trees and Spin Glass Transition[END_REF][START_REF] Borgs | The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels[END_REF][START_REF] Sly | Reconstruction of Random Colourings[END_REF][START_REF] Sly | Reconstruction for the Potts model[END_REF]. Consider a rooted bipartite tree, with two types of vertices, called variable nodes and interaction nodes, the latter being all of degree k, the root and the leaves being variable nodes. This tree is used as an information channel, in the following way: each variable node i bears a spin σ i ∈ χ, and an information is sent from the root to the leaves, by first drawing the spin of the root vertex with a prior probability η on χ, and then recursively assigning the values of the spins at distance n = 1, 2, . . . from the root. This last step is done independently for each interaction node a: denoting σ 1 , . . . , σ k-1 the k -1 variables adjacent to a that are at distance n + 1 from the root, and σ the variable at distance n (that has been assigned in the previous step of the induction), one draws the former conditional to the latter, with a law denoted p c (σ 1 , . . . , σ k-1 |σ). The tree reconstruction question is now: given the observation of the spins at distance n, is it possible to infer the value of the spin at the root that started this broadcast process? Thanks to the tree structure of the channel it is possible to compute easily the posterior probability η of the root given this observation; when the distance n becomes very large two possibilities can arise, depending on the level of noise in the channel: either η becomes very close to η, then all information on the root value is lost, or η keeps a trace of the correlation with the root, and an inference of its value with a better chance of success than the one allowed by the prior probability η is possible.

It is not too difficult to convince oneself that the distribution P (n) τ (η) that solves the cavity equations [START_REF] Barthel | Hiding Solutions in Random Satisfiability Problems: A Statistical Mechanics Approach[END_REF][START_REF] Lesieur | Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications[END_REF]) is precisely the one described above in this tree reconstruction problem (see e.g. [START_REF] Mézard | Reconstruction on Trees and Spin Glass Transition[END_REF] for a detailed derivation with similar notations), conditional to the root variable being τ in the broadcast process, and when the tree used as a channel is a random Galton-Watson tree with offspring degree probability p . In this light the unconditional version of the cavity equations [START_REF] Mézard | Reconstruction on Trees and Spin Glass Transition[END_REF][START_REF] Borgs | The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels[END_REF] is seen to describe the distribution of the marginal probability law of the root η, conditional to the observation of the leaves, when the law of the latter is not conditioned on the value of the root in the broadcast, and the relations [START_REF] Sly | Reconstruction for the Potts model[END_REF] are mere traductions of the Bayes theorem.

Following this interpretation the initial condition of the induction on n should be

P (n=0) τ (η) = δ(η -δ τ,• ) , (29)
with δ τ,• the probability law on χ supported solely on τ , which expresses the perfect knowledge of the variables observed at the leaves of the tree. As mentioned above the distribution δ(ηη) is a fixed point of the cavity recursions [START_REF] Barthel | Hiding Solutions in Random Satisfiability Problems: A Statistical Mechanics Approach[END_REF][START_REF] Lesieur | Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications[END_REF]: the tree reconstruction problem can thus be rephrased, in this setting, as determining whether the recursion bring, for n → ∞, the distributions P (n) τ towards this trivial fixed point, in which case all information on the root is lost, or towards a non-trivial fixed point that contains more information on the root than the prior probability η.

It is actually useful to consider a more generic initial condition, namely

P (n=0) τ (η) = ε δ(η -δ τ,• ) + (1 -ε) δ(η -η) , (30)
with ε ∈ [0, 1]. The iterations of [START_REF] Barthel | Hiding Solutions in Random Satisfiability Problems: A Statistical Mechanics Approach[END_REF][START_REF] Lesieur | Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications[END_REF], starting from this initial condition, describe now the inference problem of the tree where the spin value of each leaf is observed with probability ε, and kept hidden otherwise. The usual tree reconstruction problem is recovered for ε = 1; the variant known as the robust reconstruction problem [START_REF] Janson | Robust reconstruction on trees is determined by the second eigenvalue[END_REF] corresponds to the limit ε → 0, taken after the n → ∞ limit, and again asks whether the iterations of the cavity equation bring back the distributions

P (n) τ
to the trivial fixed point (corresponding to ε = 0) or lead it to a non-trivial one. Robust reconstruction is thus possible if an infinitesimal amount of information on a far away boundary is amplified in the reconstruction process and yields a non-vanishing information on the root. It was shown in [START_REF] Janson | Robust reconstruction on trees is determined by the second eigenvalue[END_REF] that the threshold for robust reconstruction corresponds to the Kesten-Stigum condition [START_REF] Kesten | Additional Limit Theorems for Indecomposable Multidimensional Galton-Watson Processes[END_REF], in other words the robust reconstruction problem is solvable if and only if the trivial fixed point is locally unstable. This provides a bound on the original reconstruction problem, which is certainly solvable whenever the robust variant is; the converse is not true in general, the tightness or not of the Kesten-Stigum bound depending on the channel will be a point that our main results will enlighten.

Link with inference problems on graphs

Let us now turn to the second interpretation of the cavity formalism, that corresponds to the inference problems on random graphs described in Sec. III A. For concreteness we concentrate on the Stochastic Block Model example, parametrized by the probability law η and the affinity matrix c, that verify the condition d σ = σ c σσ η σ = d independently of the label σ. Consider a graph G drawn from the SBM ensemble, along with its labels σ, and choose uniformly at random one of its vertices. One can then show (see for instance proposition 2 in [START_REF] Mossel | Reconstruction and estimation in the planted partition model[END_REF] for a formal statement) that its local neighborhood of fixed radius n converges in distribution, in the large size limit, to a Galton-Watson tree with an offspring distribution p that is a Poisson law of average d, decorated by labels σ i that have the law described above in the tree reconstruction perspective: the label of the root is drawn with probability η, and broadcasted along the edges of the tree with the conditional law

p c (σ |σ) = 1 d c σσ η σ , (31)
that verifies the reversibility property ( 14). This simple observation unveils a link between the inference problem on a graph and its tree counterpart; of course from a rigorous point of view the interplay between these two problems is subtler, in particular because there is no explicit observation of any label in the graph problem, contrary to the tree case. Another difference is the (weak) interaction between vertices that are not linked by an edge in the posterior probability law of the graph SBM problem, which is not explicitly present in the cavity formalism but can be traced to the condition [START_REF] Sly | Reconstruction of Random Colourings[END_REF]. The cavity method approach leads to the following conjectures:

(i) When the robust reconstruction tree problem is solvable, then the labels of the graph inference problem can be inferred with a better accuracy than using only the prior information η, via a polynomial time message-passing algorithm known as Belief-Propagation, whose accuracy is described in the large size limit by the fixed point of the cavity equations reached through the robust reconstruction initial condition (i.e. with ε → 0 after n → ∞ in [START_REF] Liu | The Tightness of the Kesten-Stigum Reconstruction Bound of Symmetric Model with Multiple Mutations[END_REF]).

(ii) The accuracy of the optimal estimator of the labels (that may require an exponential time to be computed) is described by the fixed point of the cavity equations [START_REF] Barthel | Hiding Solutions in Random Satisfiability Problems: A Statistical Mechanics Approach[END_REF][START_REF] Lesieur | Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications[END_REF] that yields the largest possible value of the freeentropy [START_REF] Lelarge | Fundamental limits of symmetric low-rank matrix estimation[END_REF], the latter being related to the mutual information between σ and G. In particular, if [START_REF] Barthel | Hiding Solutions in Random Satisfiability Problems: A Statistical Mechanics Approach[END_REF][START_REF] Lesieur | Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications[END_REF] only admit the trivial fixed point, then the hidden labels cannot be inferred better than with their prior distributions.

(iii) No polynomial time algorithm is able to beat the estimation accuracy of the Belief Propagation algorithm, hence the existence of the "hard" phase, where according to (ii) it is information-theoretically possible to infer the labels with a non-trivial accuracy, but this is not possible with Belief Propagation. We stress here that in problems where the hybrid-hard phase (with BP giving better estimate than random, but still being largely suboptimal) exists, the non-optimality of BP occurs for SNR above the Kesten-Stigum threshold.

Parts of points (i) and (ii) have been established rigorously, in particular for the stochastic block model as reviewed in [START_REF] Abbe | Community detection and stochastic block models: recent developments[END_REF]. The most detailed results have been obtained for the symmetric 2 groups SBM [START_REF] Mossel | A proof of the block model threshold conjecture[END_REF][START_REF] Massoulié | Community detection thresholds and the weak Ramanujan property[END_REF]. Point (ii) is established in [START_REF] Coja-Oghlan | Information-theoretic thresholds from the cavity method[END_REF][START_REF] Coja-Oghlan | Charting the replica symmetric phase[END_REF][START_REF] Coja-Oghlan | The replica symmetric phase of random constraint satisfaction problems[END_REF], for a large set of models; roughly speaking these works shows that the existence of probability distributions (P, P ) with φ(P, P ) > 0 implies the possibility of non-trivial inference of the labels in the graph problem (a similar variational principle for the tree reconstruction problem can be found in [START_REF] Mézard | Reconstruction on Trees and Spin Glass Transition[END_REF]). The optimality of Belief Propagation for large signal-to-noise ratio (above an unspecified constant multiplying the KS threshold) was established in [START_REF] Mossel | Belief propagation, robust reconstruction and optimal recovery of block models[END_REF], but remains an open problem in the low signal-to-noise ratio regime. Point (i) is very much related to theorem 2.12 in [START_REF] Mossel | Belief propagation, robust reconstruction and optimal recovery of block models[END_REF], where an auxiliary algorithm provides the initial condition of BP on a finite graph that emulates the observation of a few labels in the tree robust reconstruction problem.

D. Main results

The main technical results of this paper, to be presented in the subsequent Sections, are expansions of the functional cavity equations [START_REF] Barthel | Hiding Solutions in Random Satisfiability Problems: A Statistical Mechanics Approach[END_REF][START_REF] Lesieur | Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications[END_REF] and free-entropy [START_REF] Lelarge | Fundamental limits of symmetric low-rank matrix estimation[END_REF] around their trivial fixed point (that exists because we consider models having an undetectable phase). These computations allow us to generalize the local bifurcation analysis sketched in Sec. II D for a finite-dimensional order parameter, to the functional infinite-dimensional case. When the parameters (η, p j , p ) of the models are varied in the neighborhood of the Kesten-Stigum transition, at which the trivial fixed point changes stability, a non-trivial fixed point bifurcates from it continuously. The local bifurcation analysis allows us to determine whether it bifurcates as an unstable fixed point in the direction of lower SNR, in which case the Kesten-Stigum threshold and the algorithmic threshold coincide (right panel of Fig. 1) and the hard phase must exist, or if the solution bifurcates as a stable fixed point in the direction of higher SNR (left panel of Fig. 1 or Fig. 2). To be able to further distinguish between the 3 scenarios in the latter case, we have also solved the fixed point cavity equations numerically using the population dynamics technique (a presentation of this numerical algorithm and of the subtleties in its implementation can be found in Appendix A). For the convenience of the reader we summarize here our main findings for the stochastic block model and the planted occupation models, and defer the detailed technical explanations to Sec. IV and V respectively. We also show the numerical confirmation that BP run on large single instances of the inference problem indeed follows the behaviour derived from the distributional cavity equations.

Symmetric SBM, the marginal case of 4 groups

The symmetric SBM is a special case of the model introduced in Sec. III A 1, where every community has the same size, i.e. η σ = 1/q, and the probability of an edge between two vertices of labels σ and σ only depends on whether σ = σ or not: c σσ = a, and c σσ = b for σ = σ . The average degree is then d = [a + (q -1)b]/q, and it is convenient to parametrize the difference between the intra-community and inter-communities connectivity by defining θ = (ab)/(a + (q -1)b). This parameter is positive in the assortative case (a > b), negative in the disassortative case (a < b). As explained in Sec. III C the study of this problem by the cavity method [START_REF] Decelle | Phase transition in the detection of modules in sparse networks[END_REF][START_REF] Decelle | Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications[END_REF] is tightly linked to the tree reconstruction problem for the symmetric Potts model [START_REF] Mézard | Reconstruction on Trees and Spin Glass Transition[END_REF][START_REF] Sly | Reconstruction for the Potts model[END_REF][START_REF] Bleher | On the purity of the limiting gibbs state for the Ising model on the Bethe lattice[END_REF][START_REF] Evans | Broadcasting on trees and the Ising model[END_REF], with an offspring distribution of the Galton-Watson tree p Poissonian of average d; in this context θ > 0 (resp. θ < 0) is called the ferromagnetic (resp. antiferromagnetic) case. The Kesten-Stigum transition is easily seen in the tree reconstruction perspective to occur when dθ 2 = 1, where d is the average of p , this combination of parameters can thus be regarded as a relevant signal-to-noise ratio (keeping in mind the sign of θ that disappears from this definition).

The results of our local bifurcation analysis, performed for an arbitrary distribution p , can be summarized as follows (the details can be found in Sec. IV H):

• for q ≤ 3, for both ferromagnetic and antiferromagnetic models and for any p , the Kesten-Stigum transition is continuous (2nd order, as in the left panel of Fig. 1).

• for q ≥ 5, for both ferromagnetic and antiferromagnetic models and for any p , the transition is discontinuous (1st order, cf. the right panel of Fig. 1).

• for q = 4 the order of the phase transition depends explicitly on the degree distribution and on the ferromagnetic/antiferromagnetic character of the model, through the sign of the following quantity

w = - 7 3 E[ ( -1)( -2)] E[ ] 3 + E[ ( -1)] E[ ] 2 2   5 E[ ] -1 - 12 sign(θ) E[ ] -1   , (32)
where E denotes the average with respect to the offspring degree distribution p . A 1st order phase transition is predicted to arise if w > 0, while the transition is continuous (2nd order) for w < 0. In the ferromagnetic/assortative case (sign(θ) = 1), one can check easily that w < 0 for all degree distributions, which yields a continuous transition (one has necessarily d = E[ ] > 1 for the problem to make sense). On the contrary in the antiferromagnetic/disassortative case the sign of w changes according to the degree distribution. For instance when p is a Poisson law with average d, as in the application to the graph SBM problem, there is a critical degree d c ≈ 22.2694 such that w > 0 for small degrees d < d c , leading to a 1st order phase transition, while for large degrees d > d c the coefficient w becomes negative and hence the transition is of 2nd order type.

This problem was extensively studied in the literature from various perspectives, notably tree reconstruction [START_REF] Mézard | Reconstruction on Trees and Spin Glass Transition[END_REF][START_REF] Sly | Reconstruction for the Potts model[END_REF][START_REF] Bleher | On the purity of the limiting gibbs state for the Ising model on the Bethe lattice[END_REF][START_REF] Evans | Broadcasting on trees and the Ising model[END_REF], stochastic block model [START_REF] Decelle | Phase transition in the detection of modules in sparse networks[END_REF][START_REF] Decelle | Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications[END_REF], Potts model on random graphs [START_REF] Krzakala | Potts Glass on Random Graphs[END_REF], and part of this characterization was already known (in particular the tightness of the transition for q = 2 was established in [START_REF] Bleher | On the purity of the limiting gibbs state for the Ising model on the Bethe lattice[END_REF][START_REF] Evans | Broadcasting on trees and the Ising model[END_REF], and [START_REF] Sly | Reconstruction for the Potts model[END_REF] proved the nontightness of the KS transition for q ≥ 5 for all degrees, and its tightness for q = 3 and large enough degrees). However, the situation of the q = 4 case remained rather obscure up to now (for instance Fig. 2 of [START_REF] Krzakala | Potts Glass on Random Graphs[END_REF] missed the crossover towards a continuous transition at large degrees), even if it could have been anticipated that the ferromagnetic and antiferromagnetic models must behave in the same way in the large degree limit (see for instance [START_REF] Sly | Reconstruction for the Potts model[END_REF][START_REF] Lesieur | MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel[END_REF] and the discussion in Sec. IV F). The explicit condition (32) that characterizes sharply the degree distributions for which the antiferromagnetic 4 groups Potts model (or disassortative symmetric SBM) has a gap between the informationtheoretical performance and the best known algorithmic one is thus one of our main original results.

In order to test this prediction we performed a numerical resolution of the cavity equations (see Appendix A for more details) for the q = 4 antiferromagnet on Poissonian Galton-Watson trees. In the left panel of Fig. 3 one sees clearly that for low average degrees the spinodal and information theoretic transition are below the Kesten-Stigum bound, and that they get closer to it as d grows. A simple scaling argument, to be explained in Sec. IV H, predicts that the signal-to-noise ratio dθ 2 of the spinodal and IT transitions reaches the Kesten-Stigum value 1 with a correction scaling as (d cd) 3 as d → d - c . In the right panel of Fig. 3 we thus plotted the same phase diagram in these reduced units. It is fair to say that our numerical data are compatible with our analytical prediction of d c , without bringing an independent confirmation of it. As a matter of fact, the largest degrees for which we could estimate reliably the location of the spinodal and IT transitions are still rather far from our prediction of d c ; it is indeed very difficult to distinguish numerically a continuous transition from a very weakly discontinuous one.

Asymmetric balanced two groups SBM

We have also dedicated a specific attention, detailed in section IV I, to the case of the q = 2 communities SBM with different communities sizes (η 1 = η 2 ), yet with an affinity matrix such that the average degree of the vertices in the two communities is the same (hence the degree of a vertex is uninformative of its label, and the model exhibits an undetectable phase at low degrees). We will parametrize this model by a "magnetization" parameter m ∈ [0, 1] such that the size of the smaller group is η 1 = 1-m 2 , the symmetric case being recovered for m = 0. With the condition of both groups having average degree d we are left with one more free parameter, we will call it θ and define it as θ = 1 -c12 d where c 12 = c 21 is N times the probability that two nodes in different groups are connected by an edge. The cavity method relates this model to a tree reconstruction problem known as the asymmetric Ising model [START_REF] Mossel | Reconstruction on Trees: Beating the Second Eigenvalue[END_REF][START_REF] Borgs | The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels[END_REF][START_REF] Liu | Reconstruction for the asymmetric Ising model on regular trees[END_REF], for which the KS transition occurs at dθ 2 = 1, with d = E[ ] the average offspring degree. Our expansions of the cavity equations around this point reveals a striking universality phenomenon: for all degree distributions, and for both ferromagnetic and antiferromagnetic models, the qualitative nature of the transition changes when the parameter m that quantifies the asymmetry of the model crosses the same value m c = 1/ √ 3. The transition is indeed second order (left panel of Fig. 1) for m < m c , and first order (right panel of 1 for their definitions) are plotted in terms of the signal-to-noise parameter dθ 2 , which equals 1 at the Kesten-Stigum transition (horizontal dashed line). On the right panel the same data is drawn in rescaled units to better appreciate the crossover from 1st to 2nd order transition as d increases; the vertical line marks our analytical prediction for dc ≈ 22.2694, the other line is only here as a guide to the eye.

was only known from [START_REF] Borgs | The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels[END_REF] that the Kesten-Stigum bound was tight (i.e. the transition second order) for small enough asymmetries, and that it was not tight for large enough asymmetries [START_REF] Mossel | Reconstruction on Trees: Beating the Second Eigenvalue[END_REF], but these papers did not estimate the critical asymmetry separating these two regimes. The value m c = 1/ √ 3 was deduced independently in [START_REF] Liu | Reconstruction for the asymmetric Ising model on regular trees[END_REF] which provide a rigorous proof of the non-tightness of the Kesten-Stigum bound for m > m c on regular trees, via moment expansions similar to ours. Our (non-rigorous) computations presented in Sec. IV I are more generic, as they encompass arbitrary offspring distributions p , but more importantly have been pushed to an higher order in the expansion. This allows us to predict not only the critical asymmetry m c above which the Kesten-Stigum bound is not tight, but also the leading order behavior of the spinodal (reconstruction) and IT transition lines in the regime m → m + c (which is not universal and depends on the degree distribution and on the ferromagnetic/antiferromagnetic character of the model). As an illustration we present in Fig. 4 the phase diagram for the ferromagnetic Ising model on a regular tree, obtained by a numerical resolution of the cavity equations. One sees indeed on the left panel that the spinodal and information theoretic transition occur before the KS threshold for asymmetries larger than m c , and that this discontinuity of the transition vanishes when m → m + c . In the right panel we present the same data in rescaled units, chosen such that the approach to m c is linear; the two straight lines of the plot are the results of our analytical predictions to be explained in Sec. IV I, and are in agreement with the numerical results within the accuracy we could reach.

Note that the independence of m c on the degree distribution explains why the same phenomenology, and the same critical asymmetry, was already obtained in the corresponding dense inference problems [START_REF] Lesieur | Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications[END_REF][START_REF] Barbier | Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula[END_REF], or in the large degree limit [START_REF] Caltagirone | Recovering asymmetric communities in the stochastic block model[END_REF][START_REF] Lelarge | Fundamental limits of symmetric low-rank matrix estimation[END_REF]. The community detection problem in networks with unequal groups was also recently investigated in [START_REF] Montanari | Finding One Community in a Sparse Graph[END_REF][START_REF] Zhang | Community detection in networks with unequal groups[END_REF], but these works treat the case where the degree of a vertex is correlated to its label; on the contrary in all the problems we treated in this paper the degree of a vertex is not informative of its label.

q1 + q2 SBM

As we have seen in the two cases above the qualitative properties of the phase diagram of the SBM strongly depends on the structure of the prior distribution η and of the affinity matrix c, in particular on their symmetry properties. It is of course impossible to investigate explicitly all the possible ways to break the full permutation symmetry between the q labels, for arbitrary q, and to determine the typology of the phase transitions of the associated models. We have studied a class of SBM that generalizes and encompasses both the symmetric SBM model for q arbitrary and the asymmetric q = 2 case, by dividing the q possible labels in two "super-groups" G 1 and G 2 of cardinality q 1 and q 2 (with q = q 1 + q 2 ) and keeping the permutation symmetry inside each of these two sets. This leads to a prior η σ that is constant inside G 1 and G 2 , and an affinity matrix c στ which depends only on the super-groups σ and τ belong to, and on the fact that σ = τ or not (see Fig. 5 for an illustration). One can view the graph generated in this way as a superposition of two symmetric SBMs on the vertices in the groups G 1 and G 2 , and an asymmetric Ising model that coarse-grain all the labels in a group G i as a single symbol. Once q 1 and q 2 is chosen the model is defined by 5 parameters: the average degree of a vertex (assumed to be independent of its label), the fraction of On the left panel the spinodal and IT transitions are plotted in terms of the signal-to-noise parameter dθ 2 , which equals 1 at the Kesten-Stigum transition (horizontal dashed line). Within our numerical accuracy we cannot distinguish the spinodal and IT points for m smaller than 0.8, we used a single symbol in this case. The two lines corresponds to the large degree limit, as computed for the dense models in [START_REF] Lesieur | Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications[END_REF][START_REF] Barbier | Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula[END_REF][START_REF] Caltagirone | Recovering asymmetric communities in the stochastic block model[END_REF]. On the right panel the same data is drawn in rescaled units to better appreciate the crossover from 1st to 2nd order transition as m reaches its critical value mc = 1/ √ 3 ≈ 0.577, marked as a vertical line. The two straight lines are the analytical predictions of Eqs. (131,134) for the leading order behavior of the spinodal and IT transitions as m → m + c , for the sparse case p = δ ,3 .

00 00 [START_REF] Zdeborová | Quiet planting in the locked constraint satisfaction problems[END_REF] vertices in the two super-groups, and the three SNR's quantifying the information provided by the edges of each SBM in the decomposition explained above. Depending on the choice of parameters the Kesten-Stigum transition can arise from any of these three subgraphs; in Section IV J we present a classification of the typology of the corresponding bifurcation. Moreover we will argue there that for well-chosen parameters the more complicated bifurcation depicted in Fig. 2 must occur in this model. Note that a special case of this problem (with an additional symmetry between the two sub-groups) was recently studied in [START_REF] Liu | The Tightness of the Kesten-Stigum Reconstruction Bound of Symmetric Model with Multiple Mutations[END_REF].

The hybrid-hard phase in the planted occupation models

In Sec. V we shall study in detail the cavity equations for Ising spin (q = 2) variables, denoting the spin alphabet χ = {-1, +1}, with k-wise interactions, for k ≥ 2 arbitrary. We concentrate on models that have a global spin-flip symmetry, i.e. such that η + = η -= 1/2 and p j (σ 1 , . . . , σ k ) = p j (-σ 1 , . . . , -σ k ) in the notations of Sec. III B. Quite strikingly we shall prove that all the problems fulfilling this symmetry property have, around their Kesten-Stigum threshold, a bifurcating non-trivial solution on the large signal-to-noise ratio side of the KS transition. In other words none of these models can exhibit a first order transition as in the right panel of Fig. 1; depending on the model the phase diagram is either of the second order type (cf. left panel of Fig. 1), or exhibits an hybrid-hard phase as in 6: Stable fixed points of the cavity equations in terms of their accuracies for the planted bicoloring of k-uniform hypergraphs, with k = 3, 4, 5 from left to right. The accuracy is defined here as the difference between the probability that a sample from the posterior marginal outputs the correct label and the same probability when only the prior is used, see Sec. IV K for more details. The vertical line marks the KS threshold. These curves have been obtained by a numerical resolution of the cavity equations [START_REF] Barthel | Hiding Solutions in Random Satisfiability Problems: A Statistical Mechanics Approach[END_REF][START_REF] Lesieur | Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications[END_REF], a inf corresponds to the fixed point reached from an informative initialization (corresponding to the reconstruction problem, ε = 1 in Eq. ( 30)), a alg was obtained from an uninformative initialization (corresponding to the robust reconstruction problem, ε → 0 in Eq. ( 30)). The parameter α controls the offspring degree distribution p , which is a Poisson law of average αk. The optimal accuracy a * coincides with a inf above the IT transition, whose location can be found in Table I. As an illustrating example we present in Fig. 6 the bifurcation diagrams for the planted k-uniform hypergraph bicoloring, as defined in Sec. III A 2, in which each hyperedge forbids the k variables around it to be all in the same state. The random version of this Constraint Satisfaction Problem has been studied in some details (see for instance [START_REF] Gabrié | Phase transitions in the q-coloring of random hypergraphs[END_REF] and references therein), but we are not aware of previous studies of its planted version for small values of k. The plots of Fig. 6 show that for k = 3 the transition is second order, while k = 4 and k = 5 realizes the two scenarios sketched in the left and right panel of Fig. 2, respectively, and whose interpretation was discussed in general terms in Sec. II C. In these latter two cases the hybrid-hard phase occupies a sizeable part of the phase diagram and can be easily identified numerically; we expect all k ≥ 5 to behave qualitatively in the same way, and checked this for k = 6. We report in Table I the corresponding values of the thresholds α KS for the Kesten-Stigum transition, α sp and α alg for the spinodals of the high and low accuracy branches, respectively, and α IT , corresponding to the crossings of the free-entropies of these two fixed-points (the corresponding numerical data will be shown in Sec. V).

k
As far as we know the hybrid-hard phase in which Belief Propagation is able to reach a non-trivial accuracy, yet cannot reach the optimal one, was never identified previously in sparse inference problems that have an undetectable phase. This can sound surprising in view of our statement above: hybrid-hard phases do appear as soon as the phase diagram is not a purely second order transition. The resolution of this apparent paradox is that the hybrid-hard phase is often very narrow: for instance the so-called 2-in-4 planted SAT problem was reported, wrongly, to have a first order transition in [START_REF] Zdeborová | Quiet planting in the locked constraint satisfaction problems[END_REF][START_REF] Angelini | Spectral detection on sparse hypergraphs[END_REF]. As we show in Sec. V the hybrid-hard phase does exist in this model, but its width is so tiny that it was easily missed in previous numerical studies.

Numerical experiments with Belief Propagation

Our main technical results are based on numerical resolutions and analytic expansion of the distributional cavity equations [START_REF] Mézard | Reconstruction on Trees and Spin Glass Transition[END_REF][START_REF] Borgs | The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels[END_REF]. These equations describe directly the tree reconstruction problem, but their interpretations in terms of the inference problems on graphs and hypergraphs relies on conjectured connections summarized in Sec. III C 2. We shall therefore devote Section VI to a numerical test of this connection, and show that the behavior of the BP algorithm on large but finite size samples is well described by the (infinite size) tree reconstruction problems. As a striking example let us anticipate that the curves of Fig. 6 shall be reproduced in Fig. 10 from the output of single sample experiments, including the coexistence of non-trivial branches in the hybrid-hard phases.

IV. MOMENT EXPANSIONS FOR PAIRWISE INTERACTING POTTS VARIABLES

This Section is devoted to the first of the two specializations of the formalism introduced in Sec. III: we shall only study here pairwise interacting models (i.e. k = 2), in other words we consider graphs instead of hypergraphs, but keep an arbitrary q-state variable alphabet (in Sec. V we shall instead turn to k-wise interactions with arbitrary k but restrict ourselves to Ising spin variables).

A. Cavity equations and free-entropy functional

Let us start by rewriting the cavity equations and free-entropy functional introduced in Sec. III in a simplified form, exploiting the pairwise character of the interactions considered here. Our problem is now defined in terms of a probability distribution η on χ = {1, . . . , q}, a q × q transition matrix M σσ = p c (σ |σ), and the degree distributions p and p related by the size-bias [START_REF] Abbe | Conditional Random Fields, Planted Constraint Satisfaction and Entropy Concentration[END_REF]. The two equations [START_REF] Barthel | Hiding Solutions in Random Satisfiability Problems: A Statistical Mechanics Approach[END_REF][START_REF] Lesieur | Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications[END_REF] can be joined into a single recursion on the conditional distribution:

P (n+1) τ (η) = ∞ =0 p τ1,...,τ M τ τ1 . . . M τ τ dP (n) τ1 (η 1 ) . . . dP (n) τ (η ) δ(η -f (η 1 , . . . , η )) , (33)
where the Belief Propagation recursion function f is obtained by concatenating ( 17) and [START_REF] Janson | Robust reconstruction on trees is determined by the second eigenvalue[END_REF]. In an explicit form, η = f (η 1 , . . . , η ) means that for all labels σ ∈ {1, . . . , q},

η σ = z σ (η 1 , . . . , η ) z(η 1 , . . . , η ) , z(η 1 , . . . , η ) = γ z γ (η 1 , . . . , η ) , z σ (η 1 , . . . , η ) = η σ i=1 σ M σσ η i σ , (34)
where we introduced the notation

M σσ = M σσ 1 η σ . (35)
An equivalent and more compact form of (33) can be written as an equality in distribution of random variables,

η (n+1,τ ) d = f (η (n,τ1) , . . . , η (n,τ ) ) , (36)
where all random variables are independent, has the distribution p , η (n,τ ) stands for a random draw from P (n) τ , and the τ i 's of the r.h.s. are generated with probability M τ τi .

From the equations [START_REF] Mézard | Reconstruction on Trees and Spin Glass Transition[END_REF][START_REF] Borgs | The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels[END_REF] one obtains the following recursion for the unconditional distribution,

P (n+1) (η) = ∞ =0 p dP (n) (η 1 ) . . . dP (n) (η ) δ(η -f (η 1 , . . . , η )) z(η 1 , . . . , η ) , ( 37
)
where z is the quantity defined in [START_REF] Kesten | Additional Limit Theorems for Indecomposable Multidimensional Galton-Watson Processes[END_REF]. We gave in Sec. III an expression of the free-entropy for generic random factor graph models. Specializing it to the case of pairwise interactions one obtains:

φ({P τ }) = ∞ =1 p τ η τ τ1,...,τ M τ τ1 . . . M τ τ dP τ1 (η 1 ) . . . dP τ (η ) ln z v (η 1 , . . . , η ) - 1 2 E[ ] τ1,τ2 η τ1 M τ1τ2 dP τ1 (η 1 ) dP τ2 (η 2 ) ln z e (η 1 , η 2 ) , (38)
where E[ ] = p is the average degree. The variable contribution z v reads exactly as z in [START_REF] Kesten | Additional Limit Theorems for Indecomposable Multidimensional Galton-Watson Processes[END_REF], while the edge contribution is

z e (η 1 , η 2 ) = σ1,σ2 η 1 σ1 M σ1σ2 η 2 σ2 . (39)
An equivalent form in terms of the unconditional distribution is

φ(P ) = ∞ =1 p dP (η 1 ) . . . dP (η ) z v (η 1 , . . . , η ) ln z v (η 1 , . . . , η ) - 1 2 E[ ] dP (η 1 ) dP (η 2 ) z e (η 1 , η 2 ) ln z e (η 1 , η 2 ) . (40)
B. Properties of the Markov matrix M

Let us review the properties of the transition matrix M σσ = p c (σ |σ) that follows from the hypothesis on p c made in Sec. III.

• The normalization of p c , that ensures the conservation of probabilities in the broadcast process, implies that M is a stochastic matrix, σ M σσ = 1 for all σ.

• The assumption ( 14) yields the reversibility of M with respect to η (the detailed balance condition in physics jargon),

η σ M σσ = η σ M σ σ .
• This reversibility is a sufficient condition for η to be stationary for the Markov chain with transition probability matrix M , i.e. σ η σ M σσ = η σ for all σ . Hence M has an eigenvalue θ 1 = 1, with right eigenvector (1, . . . , 1) and left eigenvector η.

Assuming that M is irreducible and aperiodic the Perron-Frobenius theorem ensures that all its other eigenvalues are strictly smaller in absolute value, we will order them as 1

> |θ 2 | ≥ • • • ≥ |θ q |.
The reversibility assumption simplifies the study of the eigen-decomposition of M : consider indeed the matrix

W σσ = η 1/2 σ M σσ η -1/2 σ
. It is easily seen that W is real and symmetric, hence diagonalizable in an orthonormal basis, and that M has the same eigenvalues as W . Let us write the eigen-decomposition of W as

W σσ = q j=1 θ j v (j) σ v (j) σ , (41)
where the vectors v of the orthonormal basis verify

σ v (j) σ v (k) σ = δ j,k , j v (j) σ v (j) σ = δ σ,σ , (42)
with here and in the following δ j,k the Kronecker symbol, equal to 1 if the two arguments are equal, 0 otherwise. The Perron eigenvector of W reads in this basis:

θ 1 = 1 , v (1) σ = η 1/2 σ . (43)
Transforming back from W to M we introduce the basis of the left and right eigenvectors of M ,

r (j) σ = η -1/2 σ v (j) σ , l (j) σ = η 1/2 σ v (j) σ , (44)
which obey the following relations:

σ l (j) σ r (k) σ = δ j,k , j l (j) σ r (j) σ = δ σ,σ , r (j) σ = 1 η σ l (j) σ , l (1) σ = η σ , r (1)
σ = 1 . (45)
The matrix M can thus be expressed as:

M σσ = q j=1 θ j r (j) σ l (j) σ = η σ + q j=2 θ j r (j) σ l (j) σ . (46)
The matrix M introduced in ( 35) is symmetric thanks to the reversibility condition, and it can be expressed in terms of the eigenvector decomposition as

M σσ = q j=1 θ j r (j) σ r (j) σ = 1 + q j=2 θ j r (j) σ r (j) σ . (47)

C. Symmetry properties

Let us recall that we stated in ( 22) some consequences of the Bayes theorem that bridge the conditional and unconditional distributions. These will play an important role in the following, hence we first spell out some consequences of these symmetry relations. We will denote E (n) τ and E (n) the averages with respect to P (n) τ and P (n) . One has E (n) [η] = η for all n. For any function g, the relationship between the densities of P (n) τ and P (n) given in [START_REF] Sly | Reconstruction for the Potts model[END_REF] yields:

η τ E (n) τ [g(η)] = E (n) [η τ g(η)] . (48)
Applying this identity with g(η) = 1 gives back the already mentioned property

E (n) [η] = η. If one uses instead g(η) = η σ , this yields η τ E (n) τ [η σ ] = E (n) [η τ η σ ] . (49)
Let us define a q-dimensional vector δ as the difference δ = ηη between a message and the stationary value. One has in this way E (n) [δ] = 0, and from ( 49) one obtains

η τ E (n) τ [δ σ ] = E (n) [η τ η σ ] -η τ η σ = E (n) [δ τ δ σ ] . (50)

D. Stability analysis of the trivial fixed-point via moment expansions

By construction the probability distribution η is a fixed point of the BP equation ( 34), i.e. f (η, . . . , η) = η, reflecting the stationarity of η under the Markov chain generated by M . This implies that P τ (η) = δ(ηη) is a fixed point of the cavity recursion (33) (and similarly P (η) = δ(ηη) is invariant under the recursion (37) for the unconditional distributions). We shall now study the stability of this trivial fixed point and determine perturbatively the non-trivial fixed points that arise in the neighborhood of the limit of stability. This bifurcation analysis will follow the steps explained in Sec. II D for scalar recursions. The additional complication due to the functional character of the recursions (33,37) will be dealt with by concentrating on the low order moments of the distributions P τ , thereby reducing the infinite-dimensional bifurcation analysis to a finite-dimensional one.

Linear analysis

We denote δ = ηη the (q-dimensional vector) difference between the BP message and the trivial fixed point. As both η and η are normalized one has σ δ σ = 0. The BP equation [START_REF] Kesten | Additional Limit Theorems for Indecomposable Multidimensional Galton-Watson Processes[END_REF] can be expressed as

δ σ = η σ i=1 (1 + δ i σ ) γ η γ i=1 (1 + δ i γ ) -η σ , (51)
where we defined

δ σ ≡ σ M σσ δ σ (52)
as a linearly transformed version of δ. The normalization condition becomes, under this transformation, σ η σ δ σ = 0. For this reason the denominator of ( 51) is equal to 1 up to quadratic corrections in δ, hence the linearization of the BP equation gives

δ σ ≈ η σ i=1 δ i σ . (53)
Taking averages according to Eq. ( 33) we thus obtain the evolution of the first moments of the distributions P (n) τ , within this linearized approximation, as

E (n+1) τ [δ σ ] = E[ ]η σ τ M τ τ E (n) τ [ δ σ ] , (54)
where E[ ] = p is the average offspring degree. To put this evolution equation under a more convenient form let us first exploit the moment identities to write

τ M τ τ E (n) τ [ δ σ ] = τ M τ τ η τ E (n) τ [ δ σ ] = τ M τ τ E (n) [ δ σ η τ ] , (55)
where in the first step we used the definition (47) of M and in the second one we exploited the relation ( 48) between conditional and unconditional averages. Noting that τ M τ τ η τ = 1 and that E (n) [ δ σ ] = 0 we obtain the identity:

τ M τ τ E (n) τ [ δ σ ] = E (n) [ δ σ δ τ ] , (56)
Multiplying the linearized evolution equation ( 54) by η τ and using [START_REF] Coja-Oghlan | The replica symmetric phase of random constraint satisfaction problems[END_REF] to transform the left hand side and (56) to treat the right hand side we obtain, without making further approximations,

E (n+1) [δ σ δ τ ] = E[ ]η σ η τ E (n) [ δ σ δ τ ] . (57)
We shall call

A (n) στ = E (n) [δ σ δ τ ]
; it can be viewed as a matrix A (n) of size q×q, which is symmetric positive semi-definite with vanishing row sums. We also denote

A (n) στ = E (n) [ δ σ δ τ ] = σ ,τ M σσ M τ τ A (n) σ τ , (58)
which defines a matrix A, symmetric positive semi-definite with σ η σ A

(n) στ = 0. With these notations the linearized recursion (57) becomes

A (n+1) στ = E[ ]η σ η τ A (n) στ , (59)
which, considering now A as a q 2 -dimensional vector, can be viewed as a matrix multiplication:

A (n+1) = N A (n) , N στ,σ τ = E[ ]η σ η τ M σσ M τ τ = E[ ]η σ M σσ 1 η σ η τ M τ τ 1 η τ . (60)
In this equation N is a q 2 × q 2 symmetric matrix; its eigenvalues are easily computed, exploiting its tensor product form, and seen to be { E[ ]θ i θ j } i,j=1,...,q , where the θ's are the eigenvalues of M (see Sec. IV B). As A (n) must obey the normalization condition σ A

(n) στ = 0 the relevant eigenvalues of N are only those with i, j ≥ 2. The stability of A = 0 under its multiplication by N is equivalent to the largest absolute value among the (relevant) eigenvalues of N being smaller than 1: we have thus recovered, as expected, the well-known Kesten-Stigum [START_REF] Kesten | Additional Limit Theorems for Indecomposable Multidimensional Galton-Watson Processes[END_REF] condition E[ ]θ 2 2 < 1 for the trivial fixed point P (η) = δ(ηη) to be stable under small perturbations.

Second order expansion

Our goal now is to characterize the non-trivial fixed points of the functional recursions [START_REF] Kschischang | Factor graphs and the sum-product algorithm[END_REF][START_REF] De Almeida | Stability of the Sherrington-Kirkpatrick Solution of a Spin-Glass Model[END_REF] that bifurcate continuously from the trivial one at the Kesten-Stigum transition; we shall hence drop the iteration index n in the following, and denote E τ [•] and E[•] as the averages with respect to P τ and P fixed-point solutions of ( 33) and ( 37) respectively. It is rather intuitive, and can be easily seen in the scalar case treated in Sec. II D, that this task will rely on an expansion of (51) beyond the linear order. However, the functional character of the fixed point equation complicates the determination of the relevant non-linear terms in this expansion. In other words one has to specify in which precise sense the sought-for fixed point is "close" to the trivial one. Let us consider the unconditional distribution P (η) and discuss the relative scaling of its centered moments. By definition the first one E[δ σ ] must vanish; the second one, A στ = E[δ σ δ τ ] must be non-zero for the distribution to be non-trivial, and we assume that it is small, of the order of some parameter κ 1. We shall make the following ansatz for the higher-order moments,

B στ γ = E[δ σ δ τ δ γ ] = O(κ 2 ) , C στ γβ = E[δ σ δ τ δ γ δ β ] = O(κ 2 ) , . . . E[δ σ1 . . . δ σp ] = O(κ p/2 ) . (61)
This ansatz was inspired by the numerical resolution of the functional equations, and we refer the reader to the Appendix B for a proof of its self-consistency.

We shall now proceed with these assumptions, and compute the leading behavior of A στ by considering the following truncated expansion of (51):

δ σ = η σ i=1 δ i σ + η σ 1≤i<j≤   δ i σ δ j σ - γ η γ δ i γ δ j γ - γ η γ ( δ i σ + δ j σ ) δ i γ δ j γ - γ η γ δ i σ δ i γ δ j σ δ j γ + γ,β η γ η β δ i γ δ i β δ j γ δ j β   ; (62)
we have included non-linear terms that are of order 2,3 and 4 in terms of δ, but that will all be of order κ 2 once averaged, according to the ansatz (61). Taking averages with respects to the fixed point conditional distributions yields, without further approximations,

E τ [δ σ ] = E[ ]η σ τ M τ τ E τ [ δ σ ] + 1 2 E[ ( -1)]η σ τ ,τ M τ τ M τ τ E τ [ δ σ ]E τ [ δ σ ] - γ η γ E τ [ δ γ ]E τ [ δ γ ] -2 γ η γ E τ [ δ σ δ γ ]E τ [ δ γ ] - γ η γ E τ [ δ σ δ γ ]E τ [ δ σ δ γ ] + γ,β η γ η β E τ [ δ γ δ β ]E τ [ δ γ δ β ]   . (63)
In order to simplify this equation we first state an identity similar to [START_REF] Zhang | Community detection in networks with unequal groups[END_REF]:

τ M τ τ E τ [ δ σ δ γ ] = τ M τ τ E[ δ σ δ γ η τ ] = E[ δ σ δ γ ] + E[ δ σ δ γ δ τ ] ; (64)
note that according to our ansatz the second term is negligible with respect to the first one (it is of order κ 2 κ). We shall now multiply (63) by η τ , in such a way that its left hand side becomes A στ ; the right hand side can be simplified by using the identities [START_REF] Zhang | Community detection in networks with unequal groups[END_REF]64). Keeping only the terms of order κ and κ 2 yields

A στ = E[ ]η σ η τ A στ + 1 2 E[ ( -1)]η σ η τ   ( A στ ) 2 - γ η γ ( A σγ + A γτ ) 2 + γβ η γ η β ( A γβ ) 2   , (65)
A στ = σ ,τ M σσ M τ τ A σ τ , (66)
where we recalled the equation linking A and A in the second line.

An equivalent form of these equations, which will turn out to be more convenient in some cases, can be given in the basis that diagonalizes the matrix M defined in Sec. IV B. Using the eigenvectors defined in [START_REF] Mossel | Belief propagation, robust reconstruction and optimal recovery of block models[END_REF] we can trade the matrix A for a matrix A , now indexed by these basis vectors, in an invertible way:

A στ = jk l (j) σ l (k) τ A jk ↔ A jk = στ r (j) σ r (k) τ A στ . (67)
The normalization condition that implied the vanishing of the row and column sums of A shows up now as A jk = 0 whenever j = 1 or k = 1. The transformation from A to A, i.e. the matrix multiplication by M for each of the two indices, becomes for A a simple multiplication by the eigenvalues θ j of the matrix M . The equation (65) thus becomes in this basis:

A jk = E[ ]θ j θ k A jk + 1 2 E[ ( -1)]   j1j2k1k2 f jj1j2 f kk1k2 θ j1 θ j2 θ k1 θ k2 A j1k1 A j2k2 -2θ j θ k l A jl A lk θ 2 l   , (68)
where we defined

f j1j2j3 = σ η σ r (j1) σ r (j2) σ r (j3) σ . ( 69
)
We have achieved here our first technical goal: this quadratic equation (65) on the matrix A (or equivalently (68) on the matrix A ) constitutes the equivalent of [START_REF] Krzakala | Hiding Quiet Solutions in Random Constraint Satisfaction Problems[END_REF] for the scalar bifurcation analysis, but now for a generic model with pairwise interaction between Potts variables in the sparse regime. In particular imposing the positive definiteness of A will allow us to discriminate between different bifurcation scenarios, as explained in Sec. II D in the simpler scalar case. We shall see in the following various applications of this formula, for different choices of the matrix M and stationary distribution η.

Third order expansion

Before turning to these applications let us first state the results of this moment expansion at the next order (which in some cases will be crucial to discriminate between different bifurcation scenarios). According to our ansatz (61) we have now to determine the centered moments of P (η) up to the fourth moment, we thus define

A στ = E[δ σ δ τ ] , B στ γ = E[δ σ δ τ δ γ ] , C στ γβ = E[δ σ δ τ δ γ δ β ] . (70)
Generalizing the derivation of (65) above by including higher order terms we have obtained the following set of equations on A, B and C (see Appendix B for a justification through a formal expansion at all orders):

A στ = E[ ]η σ η τ A στ + 1 2 E[ ( -1)]η σ η τ   ( A στ ) 2 - γ η γ ( A σγ + A γτ ) 2 + γβ η γ η β ( A γβ ) 2   (71) + E[ ( -1)]η σ η τ   - γ η γ B στ γ ( A σγ + A τ γ ) + γβ η γ η β ( B σγβ + B τ γβ ) A γβ + γβ η γ η β C στ γβ A γβ   + E[ ( -1)( -2)]η σ η τ   1 6 ( A στ ) 3 - 1 6 γ η γ ( A σγ + A τ γ ) 3 - 1 2 A στ γ η γ ( A σγ + A τ γ ) 2 + 1 6 γβ η γ η β ( A γβ ) 3 + 1 2 γβ η γ η β ( A γβ ) 2 ( A στ + A σγ + A τ γ + A σβ + A τ β ) + γβ η γ η β A γβ ( A σγ + A τ γ )( A σβ + A τ β ) - γβα η γ η β η α A γβ A βα A αγ   B στ γ = E[ ]η σ η τ η γ B στ γ (72) + E[ ( -1)]η σ η τ η γ   A στ A τ γ + A σγ A γτ + A τ σ A σγ - β η β ( A σβ A βγ + A σβ A βτ + A τ β A βγ )   C στ γβ = E[ ]η σ η τ η γ η β C στ γβ + E[ ( -1)]η σ η τ η γ η β ( A στ A γβ + A σγ A τ β + A σβ A τ γ ) (73)
A στ = σ τ M σσ M τ τ A σ τ , (74)
B στ γ = σ τ γ M σσ M τ τ M γγ B σ τ γ , (75)
C στ γβ = σ τ γ β M σσ M τ τ M γγ M ββ C σ τ γ β . (76)

E. Expansion of the free-entropy

Let us now focus on the second fundamental object introduced besides the cavity equation recursions, namely the free-entropy functional, in particular the expressions [START_REF] Mézard | Analytic and Algorithmic Solution of Random Satisfiability Problems[END_REF][START_REF] Holland | Stochastic blockmodels: First steps[END_REF] for the case of pairwise interacting Potts variables. With the conventions we used the value of φ for the trivial fixed point P triv (η) = δ(ηη) is φ(P triv ) = 0. We have computed an expansion of φ(P ) when P is close to P triv , i.e. when the centered moments of P are small (imposing the condition dP (η) η = η). Denoting again A, B and C the tensors encoding these centered moments of P of order 2, 3 and 4

(as defined in (70)), and A, B and C their transformed versions according to (74-76), we have found (see Appendix C for the details of the derivation):

1

E[ ] φ(P ) = - 1 4 στ A στ A στ + 1 12 στ γ B στ γ B στ γ - 1 24 στ γβ C στ γβ C στ γβ (77) + 1 4 E[ ] στ η σ η τ ( A στ ) 2 - 1 12 E[ ] στ γ η σ η τ η γ ( B στ γ ) 2 + 1 24 E[ ] στ γβ η σ η τ η γ η β ( C στ γβ ) 2 + 1 12 E[ ( -1)] στ η σ η τ ( A στ ) 3 -2 στ γ η σ η τ η γ A στ A τ γ A γσ - 1 2 E[ ( -1)] στ γ η σ η τ η γ B στ γ A στ A σγ + 1 4 E[ ( -1)] στ γβ η σ η τ η γ η β C στ γβ A στ A γβ + 1 48 E[ ( -1)( -2)] στ η σ η τ ( A στ ) 4 -6 στ γ η σ η τ η γ ( A στ ) 2 ( A σγ ) 2 -12 στ γ η σ η τ η γ ( A στ ) 2 A σγ A τ γ +3 στ η σ η τ ( A στ ) 2 2 + 12 στ γβ η σ η τ η γ η β A στ A τ γ A γβ A βσ   ,
where of course this expression is a truncation of an infinite series involving moments of all orders. Let us make a few comments on this result:

• One can rewrite this expansion in the eigenbasis of M (i.e. in terms of the quantities A jk instead of A στ , as defined in (67)), the corresponding expression is given in Appendix C.

• The expression [START_REF] Holland | Stochastic blockmodels: First steps[END_REF] of the free-entropy φ(P ) is variational, in the sense that its variation with respect to P vanishes when P is a fixed point solution of the recursion equation [START_REF] De Almeida | Stability of the Sherrington-Kirkpatrick Solution of a Spin-Glass Model[END_REF]. Accordingly, the derivatives of the truncated expansion (77) with respect to A, B and C vanish when the latter are solutions of the moment equations (71-76).

• If the centered moments of P verify the scaling ansatz (61) that we argued was the correct one for fixed points of the cavity recursion, then the expansion (77) contains all the terms of order κ 2 , κ 3 and κ 4 .

• However, the free-entropy functional φ(P ) of equation ( 40) is well-defined even if P is not a fixed point of the recursion equation [START_REF] De Almeida | Stability of the Sherrington-Kirkpatrick Solution of a Spin-Glass Model[END_REF] (as long as it satisfies dP (η) η = η), and accordingly the expansion (77) can be used even if A, B and C do not satisfy (71-76). As a matter of fact, such an expansion was performed in [START_REF] Coja-Oghlan | Charting the replica symmetric phase[END_REF], let us briefly mention the similarities and differences with respect to ours. In the context of the models studied in this Section, one of the results of [START_REF] Coja-Oghlan | Charting the replica symmetric phase[END_REF] (i.e. their theorem 2.3) can be rephrased as: above the Kesten-Stigum transition, i.e. whenever E[ ]θ 2 2 > 1 in such a way that the trivial fixed point is unstable under the cavity recursions, there exists a distribution P with φ(P ) > 0, hence the Kesten-Stigum transition is an upperbound for the information-theoretic transition (or condensation transition in the associated non-planted random ensemle). Let us recover this statement from our computations, defining the probability distributions P λ by

P λ (η) = 1 2 δ(η -(η + λ l (2) )) + 1 2 δ(η -(η -λ l (2) )) , (78)
where l (2) is the left eigenvector of M associated to the eigenvalue θ 2 , and λ > 0 should be sufficiently small for η ± λ l (2) to remain inside the polytope of probability distributions. The average of P λ is η for all λ, and the first centered moments of P λ are easily seen to be

A στ = λ 2 l (2) σ l (2) τ , B στ γ = 0 , C στ γβ = λ 4 l (2) σ l (2) τ l (2) γ l (2)
β .

(79)

More generically the odd centered moments vanish and the 2p-th one is λ 2p times the 2p-th tensor power of l (2) .

Computing the corresponding value of A στ and inserting in (77) one obtains 1

E[ ] φ(P λ ) = 1 4 θ 2 2 ( E[ ]θ 2 2 -1)λ 4 + O(λ 6 ) , (80)
which can indeed be made strictly positive as soon as E[ ]θ 2 2 > 1 by taking a sufficiently small λ. Note that the centered moments of P λ do not satisfy our ansatz (61), which is not contradictory as P λ has no reason to be a fixed point of the cavity recursion (incidentally, there might be no perturbative non-trivial fixed point in such a situation, see the right panel of Fig. 1). Only two terms of (77) contribute to φ(P λ ) at order λ 4 (the first ones in the first and second line), hence our expansion is more detailed than the one in [START_REF] Coja-Oghlan | Charting the replica symmetric phase[END_REF], which on the other hand deals with a much more general and complicated setting (k-wise interaction of Potts variables with quenched disorder) and is performed in a mathematically rigorous way.

F. Large degree limit

We have underlined in the introduction of this paper the existence of two families of inference problems, the dense ones which can be described by a finite-dimensional order parameter, and the sparse ones that require the use of a distributional, infinite-dimensional, description. The focus of this paper is on the latter family, but it is important to realize that the two types of problems are not completely disjoint: as a matter of fact the sparse models reduce effectively to the simpler dense ones if one takes the limit of large degrees, after the thermodynamic limit. This is a well-known fact that has been derived rigorously in several papers (see for instance [START_REF] Sly | Reconstruction for the Potts model[END_REF][START_REF] Caltagirone | Recovering asymmetric communities in the stochastic block model[END_REF][START_REF] Lelarge | Fundamental limits of symmetric low-rank matrix estimation[END_REF]), for the sake of self-containedness and to be able to contrast the behavior of the sparse and dense models we reproduce here this derivation.

We shall consider the recursion for the unconditional distribution [START_REF] De Almeida | Stability of the Sherrington-Kirkpatrick Solution of a Spin-Glass Model[END_REF] and simplify it in the large degree limit

E[ ] → ∞.
We will show that in this limit the evolution of the distribution P (n) can be tracked exactly by following a finite-dimensional object, namely the covariance matrix

A (n) στ = E (n) [δ σ δ τ ]
, that obeys a recursion equation of the form

A (n+1) = F (A (n) ).
The main idea of the derivation is to exploit a central limit theorem, we shall thus rewrite [START_REF] De Almeida | Stability of the Sherrington-Kirkpatrick Solution of a Spin-Glass Model[END_REF] in a way that makes apparent a sum of a large number of random variables. To reach this goal we will define two functions ψ(L) and z(L) whose arguments are q-dimensional real vectors L = (L 1 , . . . , L q ), that are mapped by ψ and z to normalized probability distributions and positive reals, respectively, according to

ψ(L) σ = e Lσ z(L) , z(L) = q γ=1 e Lγ . (81)
One can translate the unconditional recursion relation [START_REF] De Almeida | Stability of the Sherrington-Kirkpatrick Solution of a Spin-Glass Model[END_REF] as

E (n+1) [g(η)] = E (n) [g(ψ(L)) z(L)] , (82)
for an arbitrary function g, where in the right hand side the vector L has the distribution:

(L) σ=1,...,q d = (ln z σ (η 1 , . . . , η )) σ=1,...,q ,

with drawn from p and the η i 's drawn from P (n) . From the expression of z σ given in [START_REF] Kesten | Additional Limit Theorems for Indecomposable Multidimensional Galton-Watson Processes[END_REF] one realizes that

L σ = ln η σ + i=1 ln σ M σσ η i σ . (84)
We now recall that if Y d = n i=1 X i is a sum of i.i.d. random vectors, the number of summands n being also random, the two first moments of the sum are given by

(E[Y ]) σ = E[n]E[X σ ] , ( 85
) (Cov [Y ]) στ = E[n]E[X σ X τ ] + (Var [n] -E[n])E[X σ ]E[X τ ] . (86)
Moreover, the large degree limit E[ ] → ∞ yields a non-trivial result only if the non-trivial eigenvalues of M , θ 2 , . . . , θ q vanish in the limit. More precisely, they have to be of the form θ i = θ i / E[ ] with θ i finite. We thus have

X σ = ln σ M σσ η σ = ln   1 + 1 E[ ] q j=2 θ j r (j) σ σ r (j) σ δ σ   (87) = 1 E[ ] q j=2 θ j r (j) σ σ r (j) σ δ σ - 1 2 1 E[ ]   q j=2 θ j r (j) σ σ r (j) σ δ σ   2 + o 1 E[ ] . ( 88
)
Combining these various observations, and assuming that the offspring degree distribution is sufficiently well-behaved for the second term in (86) to be negligible (it vanishes exactly for a Poisson distribution), we find that in the large degree limit the promised recursion A (n+1) = F (A (n) ) can be decomposed in two steps:

• from A (n) compute A (n) with A (n) στ = lim E[ ] σ τ M σσ M τ τ A (n) σ τ = q j,k=2 θ j θ k r (j) σ r (k) τ σ τ r (j) σ r (k) τ A (n) σ τ . (89)
• then compute the new covariance matrix A (n+1) from

A (n+1) στ = E [(ψ(L) σ -η σ )(ψ(L) τ -η τ ) z(L)] = E (e Lσ -η σ z(L))(e Lτ -η τ z(L)) z(L) , (90)
with L a Gaussian vector characterized by its first two moments

(E[L]) σ = ln η σ - 1 2 A (n) σσ , (Cov [L]) στ = A (n) στ . (91)
As emphasized before this finite-dimensional recursion

A (n+1) = F (A (n)
) is an exact description of the functional recursion on P (n) in the large degree limit. The trivial covariance A = 0 is a fixed point of F , that reproduces the stationarity of P (η) = δ(ηη) under the functional recursion. It is instructive to expand the equation A = F (A) around A = 0, in order to compare this expansion with the one we performed previously on the full functional equation. Exploiting the properties of Gaussian random variables it is relatively easy to obtain from (90):

A στ = η σ η τ A στ + 1 2 η σ η τ   ( A στ ) 2 - γ η γ ( A σγ + A γτ ) 2 + γβ η γ η β ( A γβ ) 2   (92) + η σ η τ   1 6 ( A στ ) 3 - 1 6 γ η γ ( A σγ + A τ γ ) 3 - 1 2 A στ γ η γ ( A σγ + A τ γ ) 2 + 1 6 γβ η γ η β ( A γβ ) 3 + 1 2 γβ η γ η β ( A γβ ) 2 ( A στ + A σγ + A τ γ + A σβ + A τ β ) + γβ η γ η β A γβ ( A σγ + A τ γ )( A σβ + A τ β ) - γβα η γ η β η α A γβ A βα A αγ   + O(A 4 ) . (93)
This is, at it should, consistent with the expansion performed in the sparse case and presented in Eq. ( 71). Of course the equations in the sparse regime are richer, the effects of the third and fourth order moments B and C being washed out in the large degree limit by the Gaussian character of the distribution.

For completeness let us also state the large degree limit for the free-entropy, that becomes a function of a covariance matrix A,

φ(A) = E[ z(L) ln z(L)] - 1 4 στ A στ A στ , ( 94
)
where A is obtained from A according to (89), and in the first term L is a Gaussian vector with the two first moments indicated in (91).

In the remaining of this Section we shall investigate the consequences of our expansions, that were performed for an arbitrary choice of q, η and M , in several specific cases. In particular we have to analyze the bifurcation of the quadratic equation (65) on the covariance matrix A in the neighborhood of the Kesten-Stigum transition, and use it to discriminate between the possible scenarios depicted in Fig. 1 and 2 by imposing the positive definiteness of A.

G. Application 1: the non-degenerate case

Let us first consider the case of a simple second eigenvalue of M at the Kesten-Stigum transition. More explicitly, we consider that the various parameters of the model (degree distribution, η, M ) are functions of a single control parameter , defined in such a way that E[ ]θ 2 2 = 1 + , with = 0 at the Kesten-Stigum transition, and we assume that E[ ]θ 2 j are bounded away from 1 for j = 3, . . . , q in a neighborhood of = 0. Consider now the set of quadratic equations (68) on A , the covariance matrix expressed in the basis of eigenvectors of M . With the assumption of simplicity of θ 2 the only coefficient of the linear terms in the right hand side that crosses 1 at the Kesten-Stigum transition corresponds to j = k = 2; the bifurcating solution will thus have |A 22 | |A jk | for (j, k) = (2, 2) in the neighborhood of = 0. We can thus close the equation on this leading term as

A 22 = E[ ]θ 2 2 A 22 + 1 2 E[ ( -1)]θ 4 2 (A 22 ) 2 ((f 222 ) 2 -2) , (95)
where the expression of f 222 is given in (69). At the leading order in we have

0 = + 1 2 E[ ( -1)]θ 4 2 ((f 222 ) 2 -2)A 22 , (96)
hence A 22 varies linearly with around = 0, the other matrix elements of A being at least of order 2 . The crucial point is now to remember that A , as a covariance matrix, must be positive definite, and as a consequence A 22 must be a positive real. Depending on the sign of (f 222 ) 2 -2 this happens for > 0 (resp. < 0), corresponding for instance to the scenario sketched on the left (resp. right) of Fig. 1. Spelling out the definition of f 222 in terms of the eigenvectors of M , we have obtained that the first case occurs when

σ η σ (r (2) σ ) 3 2 < 2 . ( 97
)
Let us underline the striking similarity between this criterion and the one obtained in [START_REF] Lesieur | Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications[END_REF] in the context of matrix factorization. This is a dense inference problem with continuous variables, for which the condition of existence of a bifurcating solution above the Kesten-Stigum transition was found to be x 3 0 2 < 2 x 2 0 3 , the average being here on the prior distribution of a real valued variable x 0 (see equation ( 205) in [START_REF] Lesieur | Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications[END_REF]). Using the properties of the eigenvalue decomposition of M explained in Sec. IV B one can rewrite (97) as

σ η σ (r (2) σ ) 3 2 < 2 σ η σ (r (2) σ ) 2 3 , (98)
a formally equivalent expression with η σ replacing the prior distribution and the eigenvector r

(2) σ the continuous variable x 0 .

H. Application 2: the symmetric q state case

We turn now to a case which can be viewed as the opposite of the previous one, with a maximal degeneracy of the second eigenvalue of M . Consider indeed the symmetric q state Potts model, with a stationary distribution η σ = 1 q for all σ, and a matrix M which is invariant under all permutations of its rows and columns. As M is stochastic it must be of the form

M στ = 1 q + θ K στ , with K στ = δ σ,τ - 1 q ; ( 99
)
θ is the non-trivial eigenvalue of M , with a degeneracy q -1. The matrix elements of M must be non-negative, the authorized range of θ is thus -1 q-1 , 1 . The model is said assortative (or ferromagnetic) if θ > 0 and disassortative (or antiferromagnetic) if θ < 0. The matrix elements of M are M στ = 1 + qθK στ .

The recursion equation [START_REF] De Almeida | Stability of the Sherrington-Kirkpatrick Solution of a Spin-Glass Model[END_REF], for this choice of η and M , will respect the permutation symmetry between the q values of σ. If the initial condition is symmetric this will also be the case for P (n) , for all n. In particular the covariance matrix A (n) will be invariant under all row and column permutations; as its row sums must also vanish it is necessarily of the form A (n) = a (n) K, with a (n) a real number and K the matrix defined in (99). The eigenvalues of K being 0 and 1, the positivity constraint on A (n) thus translates into a (n) ≥ 0. One finds easily that with this form of A and M that A (n) = (qθ) 2 a (n) K. Plugging these forms of A and A in the linearized evolution equation (59) yields a (n+1) = E[ ]θ 2 a (n) , hence the Kesten-Stigum condition E[ ]θ 2 = 1 for the limit of stability of the trivial solution a = 0, as expected.

Looking for a fixed point solution of the form A στ = aK στ in the neighborhood of the Kesten-Stigum transition, we obtain from (65) after a brief computation:

a = E[ ]θ 2 a + E[ ( -1)]θ 4 1 2 q(q -4)a 2 . ( 100
)
Denoting E[ ]θ 2 = 1 + , and keeping in mind the crucial positivity condition a ≥ 0, one realizes that for q < 4 the non-trivial perturbative fixed point exists for > 0, whereas if q > 4 it exists for < 0, which implies that the Kesten-Stigum bound is not tight for the tree reconstruction problem in the latter case. This fact was proven rigorously in [START_REF] Sly | Reconstruction for the Potts model[END_REF], the above equation corresponding to (1.1) in [START_REF] Sly | Reconstruction for the Potts model[END_REF] (with a linear change of variable between our a (n) and x n of [START_REF] Sly | Reconstruction for the Potts model[END_REF]). Let us emphasize the necessity of imposing the permutation symmetry of A in order to reach this conclusion; the bifurcation equations (65) admit indeed, besides the symmetric solution studied above, non-symmetric spurious solutions A even when η and M are invariant under permutations.

We have thus justified the statements made in Sec. III D 1 in the cases q ≤ 3 and q ≥ 5. When q = 4 the coefficient of a 2 in the bifurcation equation vanishes exactly and one cannot conclude from this lowest-order expansion on the type of transition encountered at the Kesten-Stigum threshold. Thanks to the next order expansion presented in Sec. IV D 3 we shall now be able to elucidate this case, and justify the efforts put in this generalization of the expansion. In order to solve the equations (71-76) on A, B and C, we first note that B and C vanish when summed over any of their indices; from the expression of M in the case under study we can thus conclude that B στ γ = (qθ) 3 B στ γ and C στ γβ = (qθ) 4 C στ γβ . Inserting these expressions in (72,73) yields an explicit solution for B and C in terms of A,

B στ γ = E[ ( -1)] 1 -E[ ]θ 3 1 q 3   A στ A τ γ + A σγ A γτ + A τ σ A σγ - 1 q β ( A σβ A βγ + A σβ A βτ + A τ β A βγ )   , (101)
C στ γβ = E[ ( -1)] 1 -E[ ]θ 4 1 q 4 ( A στ A γβ + A σγ A τ β + A σβ A τ γ ) . (102)
Furthermore we have argued above by symmetry arguments that A = aK and A = a(qθ) 2 K, we can thus determine completely B and C modulo the still unknown real a. Plugging these expressions in (71) gives, after some combinatorial evaluations, the following equation on a that generalizes (100):

a = E[ ]θ 2 a + E[ ( -1)]θ 4 1 2 q(q -4)a 2 + w a 3 , (103)
where the coefficient w reads

w = 1 6 q 2 (q 2 -18q + 42) E[ ( -1)( -2)]θ 6 - 6q 2 (q -2) E[ ( -1)] 2 θ 9 1 -E[ ]θ 3 + q 2 (q + 1) E[ ( -1)] 2 θ 10 1 -E[ ]θ 4 . (104)
In the most interesting case q = 4 where the coefficient of a 2 vanishes, one finds for w (substituting θ = sign(θ)/ E[ ] at lowest order around the Kesten-Stigum transition):

w = 16   - 7 3 E[ ( -1)( -2)] E[ ] 3 + E[ ( -1)] E[ ] 2 2   5 E[ ] -1 - 12 sign(θ) E[ ] -1     , (105)
which justifies the expression (32) announced in Sec. III D 1 (the factor 16 between ( 32) and ( 105) is irrelevant for the study of the sign of w). Depending on the degree distribution p and on the sign of θ this coefficient can be positive or negative; as the equation on a reduces here to 0 = + w a 2 , with = E[ ]θ 2 -1, the sign of w controls the sign of for which a non-trivial solution of the cavity equations exists in a neighborhood of the trivial one, hence the type of bifurcation scenario as sketched in Fig. 1. As mentioned in Sec. III D 1 one has w < 0 in the ferromagnetic case for all degree distributions, which yields a second order transition; it is indeed easy to check numerically that

5 d -1 - 12 √ d -1 < 0 (106)
for all average offspring degrees d = E[ ] > 1.

In the antiferromagnetic case the sign of w depends on the degree distribution. For instance when p is a Poisson law of parameter d the expression of w above can be simplified to

w = 16 - 7 3 + 5 d -1 + 12 √ d + 1 . (107)
A numerical study of this function reveals the existence of a critical degree d c ≈ 22.2694 such that w > 0 for d ∈ (1, d c ), hence a discontinuous bifurcation scenario similar to the case q > 4, while for d > d c one has w < 0, yielding the scenario of q < 4. We have also evaluated the sign of w in the regular case, i.e. for an offspring degree distribution p = δ ,d . Similarly to the Poisson case one finds (for the antiferromagnetic model) that w < 0 for d ≤ 24 and w > 0 for d ≥ 25.

Note that for large enough degrees ferromagnetic and antiferromagnetic models behave in the same way; this could be anticipated from the study of the large degree limit recalled in Sec. IV F, as in this limit the degree distribution and θ only appear in the combination E[ ]θ 2 , which is clearly independent of the sign of θ. Actually an expansion to the same order than in (103) can be found in equation (4.9) of [START_REF] Sly | Reconstruction for the Potts model[END_REF], but in the large degree limit and not in the sparse regime, which did not allow to deduce the modification of the type of phase transition according to the degree distribution.

Let us finally justify the scaling exponent we used in the plot presented in the right panel of Fig. 3. If we had included in the expansion of the cavity equations around the trivial fixed point one more term, one would have found, for q = 4, an equation on a of the form

0 = + w( p) a 2 + x a 3 , (108)
where a priori x = 0, and we emphasized the dependency of w on the degree distribution. Let us consider for concreteness p to be Poissonian with average d, in such a way that w(d) is given explicitly by (107). In the neighborhood of the critical degree d c where w changes sign we have w(d) ≈ w (dd c ), with w some constant. Inserting this form in the equation above gives

0 = + w (d -d c ) a 2 + x a 3 ; (109)
the scaling of θ sp , which corresponds to the limit of existence of a solution of this equation, must be such that the three terms in (109) are of the same order. This is easily seen to imply that is of the order of (dd c ) 3 , which is the reason of our choice of exponent in the right panel of Fig. 3: the spinodal and IT curves should, in this rescaled units, behave linearly in the neighborhood of d c .

I. Application 3: the asymmetric Ising (q = 2) case

We consider now the case of binary variables (q = 2), that for convenience we denote as Ising spins or sign variables, σ ∈ {-1, 1} = {-, +}. We parametrize the stationary probability distribution η as η σ = 1+σm 2 , with m ∈ [-1, 1]. This bias parameter can be interpreted as a magnetization in the perspective of a physical Ising model [START_REF] Borgs | The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels[END_REF], or in the context of the SBM as controlling the relative size of the two communities of vertices which are η + = 1+m 2 and η -= 1-m 2 . The symmetric case, as studied in Sec. IV H, is recovered for m = 0. We write the matrix M as

M = M ++ M +- M -+ M -- = 1 2 1 + m 1 -m 1 + m 1 -m + θ 1 2 1 -m -1 + m -1 -m 1 + m , i.e. M στ = 1 + τ m 2 + στ θ 1 -σm 2 . ( 110
)
This is indeed the only Markov matrix reversible with respect to η with second eigenvalue θ. To connect with the definition of the SBM in section III A 1 the parameter θ is defined as θ = 1c -+ /d where c -+ = c +-is N times the probability that nodes in different groups are connected, and d is the average degree. Given the group sizes η ± , the condition of equal average degree in the two groups then implies uniquely the parameters c --and c ++ . In the context of the SBM the degree distributions p and p are Poissonian with average d, we shall, however, consider generic degree distributions, as they are relevant in the tree reconstruction perspective. The range of allowed values of the parameters (m, θ) is a subset of [-1, 1] 2 : imposing the non-negativity of the matrix elements of M implies indeed that

θ ≥ - 1 -|m| 1 + |m| , (111)
which is always fulfilled for θ ≥ 0 but restrict the range of allowed biases m when θ < 0.

The transformed version M of M defined in [START_REF] Angelini | Spectral detection on sparse hypergraphs[END_REF] reads thus:

M στ = M στ 1 η τ = 1 + θστ 1 -σm 1 + τ m . ( 112
)
Thanks to the binary nature of the variables the probability laws η can be parametrized by a single real, and the recursion equation ( 34) can be rewritten in a simpler form with this parametrization. This expression, along with some more technical details on the numerical resolution of the cavity equations, can be found in Appendix A.

The critical asymmetry

Let us now apply the generic results of the moment expansions presented in Sec. IV D to this specific case. Because of the normalization condition δ + + δ -= 0 the deviation δ σ = η ση σ is equal to σ multiplied by a scalar random variable. We can thus write the matrix A

(n) στ = E (n) [δ σ δ τ ] as A (n) στ = a (n) 1
2 στ , where a (n) is a scalar; the factor 1/2 is chosen in such a way that 1 2 στ coincides with the matrix K στ of (99), in the case q = 2. Once again we have a positivity requirement on this covariance, a (n) ≥ 0. From the expression of M given in (112) one sees that σσ

M σσ σ = θ 1 η σ σ , (113)
hence with the relation (58) one obtains

A (n) στ = θ 2 a (n) 1 η σ η τ 1 2 στ . (114)
The linear evolution of (59) thus becomes

a (n+1) 1 2 στ = E[ ]θ 2 a (n) 1 2 στ , i.e. a (n+1) = E[ ]θ 2 a (n) , (115)
which reproduces the expected Kesten-Stigum threshold at E[ ]θ 2 = 1.

We now look for a fixed-point solution in the neighborhood of the Kesten-Stigum transition, by injecting the above forms of A and A in equation (65). This yields after a short computation

a = E[ ]θ 2 a + E[ ( -1)]θ 4 2(3m 2 -1) (1 -m 2 ) 2 a 2 . (116)
A simple consistency check is provided by the coincidence of (100) and (116) when q = 2 and m = 0. Moreover when q = 2 the non-trivial eigenvalue of M is unique, hence certainly non-degenerate; one can check that (116) is also a consequence of the equation (95) derived in Sec. IV G under this non-degeneracy assumption, for all m.

The crucial property of (116) we would like to emphasize is the change of sign of the coefficient of a 2 depending on whether |m| is larger or smaller than m c = 1/ √ 3. Because of the condition a ≥ 0 this implies that the nontrivial perturbative solution exists when E[ ]θ 2 > 1 at small asymmetry (|m| < m c ), and when E[ ]θ 2 < 1 at large asymmetry (m > m c ). In the latter case one has, in the tree reconstruction language, a reconstructible phase below the Kesten-Stigum threshold, which is not tight in this case. Quite strikingly the critical asymmetry m c does not depend on the degree distribution; this explains why this value 1/ √ 3 was also obtained previously in the large degree limit [START_REF] Caltagirone | Recovering asymmetric communities in the stochastic block model[END_REF][START_REF] Lelarge | Fundamental limits of symmetric low-rank matrix estimation[END_REF] and in related dense inference problems [START_REF] Lesieur | Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications[END_REF][START_REF] Barbier | Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula[END_REF]. Very recently this critical asymmetry was also discovered for the reconstruction of the Ising model on regular trees [START_REF] Liu | Reconstruction for the asymmetric Ising model on regular trees[END_REF]; this paper proved rigorously the non-tightness of the Kesten-Stigum bound for m > m c , and its tightness for m < m c at large enough degrees.

As an illustration of this phenomenon we present in Fig. 7 the results of a numerical resolution of the cavity equations, for two asymmetries below and above m c . One clearly sees that in the latter case reconstruction is possible below the Kesten-Stigum threshold, and that in the former case our analytical prediction (116) is in agreement with the numerical results.

Further expansions around the critical asymmetry

Let us now further describe the phase diagram of the problem in the (θ, m) plane (for simplicity of the discussion we assume the degree distribution to be held fixed), see Fig. 4 for an example. In the low asymmetry (|m| < m c ) situation there are only two phases, the tree reconstruction being possible if and only E[ ]θ 2 > 1. This tightness of the Kesten-Stigum bound at small non-zero asymmetry was proven in [START_REF] Borgs | The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels[END_REF], but this paper did not estimate the value of m c . In terms of the SBM inference problem the Kesten-Stigum transition separates an easy phase from an information theoretically impossible phase; this was proven in the symmetric (m = 0) case in [START_REF] Mossel | A proof of the block model threshold conjecture[END_REF][START_REF] Massoulié | Community detection thresholds and the weak Ramanujan property[END_REF].

The large asymmetry (|m| > m c ) part of the phase diagram is richer. In terms of the tree reconstruction problem there will be two lines of transition θ sp,± (m) such that reconstruction is possible for θ < θ sp,-(m) < 0 and θ > θ sp,+ (m) > 0, with E[ ]θ sp,± (m) 2 < 1; the subscript ± indicates the ferromagnetic (θ > 0) or antiferromagnetic (θ < 0) part of the phase diagram. Note that the average offspring degree E[ ] has to be larger than (2+ √ 3)/(2-√ 3) ≈ 13.928 for the large asymmetry antiferromagnetic part of the phase diagram to be non-empty, because of the condition (111). This discontinuous transition of the tree reconstruction problem, depicted in the bottom right part of Fig. 1, is not directly relevant for the SBM graph inference problem. The latter has an easy phase for E[ ]θ 2 > 1, an hard phase for θ < θ IT,-(m) < 0 and θ > θ IT,+ (m) > 0, with

E[ ]θ IT,± (m) 2 ∈ [ E[ ]θ sp,± (m) 2 , 1]
, while the inference is information theoretically (IT) impossible for θ ∈ [θ IT,-(m), θ IT,+ (m)]. This "IT" line is defined by the vanishing of the free-entropy computed in the non-trivial solution of the cavity equations.

In the remaining of this Section we shall describe more precisely the neighborhood of the (ferromagnetic and antiferromagnetic when it exists) points (θ, m) = (θ KS , m c ) of the phase diagram, and in particular present an analytic description of the lines θ sp,± (m) and θ IT,± (m) when |m| → m + c . To reach this goal we shall exploit the next order in our generic moment expansions, as summarized in (71-76). We first note that for symmetry reasons the tensors B and C depends on their spin indices as B στ γ = b στ γ and C στ γβ = c στ γβ, with b and c two reals. The form of the matrix M given in (112) leads to

B στ γ = θ 3 b 1 η σ η τ η γ στ γ , C στ γβ = θ 4 c 1 η σ η τ η γ η β στ γβ . ( 117
)
Plugging these expressions into (71-73) leads after a short computation to a set of equations on a, b and c, namely:

a = E[ ]θ 2 a + E[ ( -1)] 2(3m 2 -1) (1 -m 2 ) 2 θ 4 a 2 + E[ ( -1)] 32m (1 -m 2 ) 2 θ 5 ab + E[ ( -1)] 16 (1 -m 2 ) 2 θ 6 ac + E[ ( -1)( -2)] 4 3 5 -42m 2 + 45m 4 (1 -m 2 ) 4 θ 6 a 3 , (118) b = E[ ]θ 3 b -E[ ( -1)] 3m 1 -m 2 θ 4 a 2 ,
(119)

c = E[ ]θ 4 c + E[ ( -1)] 3 4 θ 4 a 2 . ( 120
)
Alternatively these equations can be obtained via the computation of the free-entropy (77), which is found to be 1

E[ ] φ(a, b, c) = E[ ]θ 2 -1 (1 -m 2 ) 2 θ 2 a 2 - 16 3 E[ ]θ 3 -1 (1 -m 2 ) 3 θ 3 b 2 + 32 3 E[ ]θ 4 -1 (1 -m 2 ) 4 θ 4 c 2 (121) + E[ ( -1)] 4 3 3m 2 -1 (1 -m 2 ) 4 θ 6 a 3 + E[ ( -1)] 32m (1 -m 2 ) 4 θ 7 a 2 b + E[ ( -1)] 16 (1 -m 2 ) 4 θ 8 a 2 c + E[ ( -1)( -2)] 2 3 5 -42m 2 + 45m 4 (1 -m 2 ) 6 θ 8 a 4 ;
its derivatives with respect to a, b and c do indeed vanish when the equations (118-120) are fulfilled.

The equations ( 119) and ( 120) can be immediately solved to obtain b and c as a function of a; re-injecting these results in (118) one obtains a quadratic equation on a:

0 = u + v a + w a 2 , with (122)
u(θ) = E[ ]θ 2 -1 , (123)
v(θ, m) = E[ ( -1)] 2(3m 2 -1) (1 -m 2 ) 2 θ 4 , (124)
w(θ, m) = E[ ( -1)( -2)] 4 3 5 -42m 2 + 45m 4 (1 -m 2 ) 4 θ 6 (125) + E[ ( -1)] 2 12θ 9 (1 -m 2 ) 2 - 8m 2 1 -m 2 1 1 -E[ ]θ 3 + θ 1 -E[ ]θ 4 . ( 126
)
We want to study this equation in the neighborhood of the point (θ KS , m c ), taking simultaneously the limits θ → θ KS and m → m c ; we denote as before = E[ ]θ 2 -1. The coefficients u = and v will thus be both small in this regime, while w = w(θ KS , m c ) = 0. In order to have the three terms in (122) of the same order, one realizes that the two simultaneous limits must be taken with = t(mm c ) 2 , where t is finite and constitutes the relevant control parameter in this scaling regime. Then, denoting v(θ

KS , m) = v(m -m c ) + O((m -m c ) 2
), we reduce (122) at lowest order to

0 = t (m -m c ) 2 + v (m -m c ) a + w a 2 . ( 127
)
Defining a reduced unknown a = a (m-mc) , which will be finite in the limit, we obtain finally

0 = t + v a + w a 2 hence a = - v 2 w ± 1 2 w v 2 -4 wt . ( 128
)
The coefficients v and w only depend on the degree distribution; to determine them at dominating order one replaces θ by its value at the Kesten-Stigum transition, i.e. sign(θ)/ E[ ], and obtain:

v = 9 √ 3 E[ ( -1)] E[ ] 2 , ( 129
) w = -27 E[ ( -1)( -2)] E[ ] 3 -27 E[ ( -1)] E[ ] 2 2   4 sign(θ) E[ ] -1 - 1 E[ ] -1   . ( 130
)
It is rather easy to check that w < 0 in the ferromagnetic case (sign(θ) > 0) for all degree distributions with E( ) > 1 (a necessary condition for the Galton-Watson tree to be infinite with positive probability, and for the Kesten-Stigum transition to exists); we believe that w < 0 also in the antiferromagnetic case whenever the point (-1/ E[ ], m c ) belongs to the authorized domain of parameters according to the condition (111) for all offspring degree distributions, but could only check it explicitly in the regular and Poisson cases. Note that in the large degree limit both coefficients v and w remains finite, namely v → 9 √ 3 and w → -27. As a consequence of w < 0 the real solutions of (128) exist for t ≥ t sp = v 2 /(4 w). This is precisely the condition that defines the line θ sp ; translating back from rescaled units yields the lowest order expansion of θ sp (m) in the limit m → m + c :

θ sp (m) = θ KS 1 - v 2 8| w| (m -m c ) 2 + o((m -m c ) 2 ) ; (131)
note that w depends on sign(θ), giving two distinct expansions for the ferromagnetic and antiferromagnetic lines θ sp,+ and θ sp,-.

Using the expression (121) of φ one can also expand the IT line θ IT around (θ, m) = (θ KS , m c ). Indeed in the scaling regime described above one finds that

φ = 9 2 E[ ] E[ ] (m -m c ) 4 1 2 t a 2 + 1 3 v a 3 + 1 4 w a 4 . ( 132
)
The IT line corresponds to φ = 0 (this is the value on the trivial fixed point), hence the IT threshold corresponds to the solution of

0 = t + v a + w a 2 0 = 1 2 t + 1 3 v a + 1 4 w a 2 ⇒ a = - 2 v 3 w , t = 2 v 2 9 w . ( 133
)
The IT threshold t IT = 2 v 2 9 w is thus distinct at this order from the spinodal one t sp = v 2 4 w (even though the difference in the coefficient is small). Translating back in terms of the parameters (θ, m) gives

θ IT (m) = θ KS 1 - v 2 9| w| (m -m c ) 2 + o((m -m c ) 2 ) , (134)
with again two different expressions for the ferromagnetic and antiferromagnetic transitions. These two expansions (131,134) on the behavior the spinodal and IT lines in the neighborhood of the critical asymmetry where the transition crosses over from second to first order constitute our main new results for the asymmetric Ising model. We have shown in the right panel of Fig. 4 that they are in agreement with our numerical data, within the accuracy we could reach. As a further illustration we show in Fig. 8 the numerical determination of a and φ in the scaling regime and compare it to our analytical formulae.

J. Application 4: the q1 + q2 case

We shall now turn our attention to the model introduced in Sec. III D 3, that breaks the symmetry between q labels in a minimal way, generalizing the two previous cases (i.e. q symbols with maximal symmetry studied in Sec. IV H and q = 2 without any symmetry in Sec. IV I).

Let us consider indeed an alphabet of q labels, χ = {1, . . . , q}, divided into two "super-groups" (or "supercommunities") G 1 and G 2 containing respectively q 1 and q 2 symbols (in such a way that q = q 1 + q 2 ), namely G 1 = {1, . . . , q 1 } and G 2 = {q 1 + 1, . . . , q}. We break the symmetry among the q labels in a minimal way, according to this sub-division in two groups, by taking η σ constant in G 1 and G 2 :

η σ = η 1 if σ ∈ G 1 and η σ = η q if σ ∈ G 2 ,
with the normalization condition q 1 η 1 + q 2 η q = 1. We parametrize the fraction of vertices in G 1 and G 2 by m ∈ [-1, 1], according to

η σ = 1 q1 1+m 2 if σ ∈ G 1 1 q2 1-m 2 if σ ∈ G 2 ; ( 135
)
this notation is reminiscent of the asymmetric Ising case, which would be obtained by coarse-graining the labels σ ∈ G 1 (resp. σ ∈ G 2 ) as σ = + (resp. σ = -). We also perform this minimal symmetry breaking on the matrix M , The rescaled signal-to-noise ratio parameter is t = (dθ 2 -1)/(m -mc) 2 , the Kesten-Stigum transition thus corresponds to t = 0. Left panel: the rescaled accuracy a = a/(m -mc) as a function of t; the lines are the analytic predictions for the stable (solid) and unstable (dashed) branches of fixed-points obtained in Eq. ( 128), the symbols are numerical results that approach the analytic line when m → m + c . Right panel: the rescaled free-entropy φ = φ/(m -mc) 4 as a function of t; the analytic lines have been obtained by inserting in (132) the two branches of a from (128), the threshold tIT corresponds to the crossing with the horizontal line φ = 0.

assuming that its matrix elements M στ only depend on the group of appartenance of σ and τ , and on whether σ = τ or not (the shape of the associated connectivity matrix in the SBM interpretation is sketched in Fig. 5).

Imposing in addition the reversibility of the stochastic matrix M with respect to η (this condition corresponds to the equality of the average degrees in G 1 and G 2 in the SBM interpretation) one realizes that such a matrix M is necessarily of the form:

M στ = 1 + m 2q 1 I(τ ∈ G 1 ) + 1 -m 2q 2 I(τ ∈ G 2 ) + µ 1 I(σ, τ ∈ G 1 ) δ σ,τ - 1 q 1 + µ 2 I(σ, τ ∈ G 2 ) δ σ,τ - 1 q 2 + µ 0 1 -m 2 I(σ ∈ G 1 ) - 1 + m 2 I(σ ∈ G 2 ) 1 q 1 I(τ ∈ G 1 ) - 1 q 2 I(τ ∈ G 2 ) . ( 136
)
One can check that M admits 1 as an eigenvalue, with eigenvectors η on the left and constant vector on the right; the parameters µ 0 , µ 1 and µ 2 introduced in (136) correspond to the non-trivial eigenvalues of M . There are q 1 -1 (resp. q 2 -1) degenerate eigenvalues µ 1 (resp. µ 2 ) with eigenvectors supported on G 1 (resp. G 2 ) and a simple eigenvalue µ 0 whose eigenvector is constant inside each of the two groups. For a given choice of m ∈ [-1, 1] the requirement of positivity of the matrix elements of M restricts the allowed domain of the parameters (µ 0 , µ 1 , µ 2 ) to the subset of

-1-|m| 1+|m| , 1 × -1 q1-1 , 1 × -1 q2-1 , 1 that fulfils the condition µ 0 ≥ max 2µ 1 -1 -m 1 -m , -2(q 1 -1)µ 1 -1 -m 1 -m , 2µ 2 -1 + m 1 + m , -2(q 2 -1)µ 2 -1 + m 1 + m . ( 137
)
One sees that the relevant eigenvalue for the Kesten-Stigum transition, i.e. the maximal one in absolute value, can be either µ 1 , µ 2 or µ 0 depending on the choice of the parameters. In other words the signal on the labels transmitted through the edges of the SBM can be stronger inside G 1 , inside G 2 or in the difference of behavior between G 1 and G 2 .

We shall now specialize the equations of Sec. IV D to this particular case. We have first to describe the matrices

A στ = E[δ σ δ τ ].
Because of the permutation invariance inside each of the two groups of labels the matrix element A στ should only depend on whether σ = τ or not and on the group of the two communities σ and τ . In addition the matrix A has to be symmetric and the sum of every row or column has to vanish. A moment of thought reveals that the vector space of such matrices is 3 dimensional, and is spanned by the three matrices K 1 , K 2 and K 0 defined as

(K 1 ) στ = I(σ, τ ∈ G 1 ) δ σ,τ - 1 q 1 , (K 2 ) στ = I(σ, τ ∈ G 2 ) δ σ,τ - 1 q 2 , ( 138
) (K 0 ) στ = 1 qq 1 q 2 (q 2 I(σ ∈ G 1 ) -q 1 I(σ ∈ G 2 )) (q 2 I(τ ∈ G 1 ) -q 1 I(τ ∈ G 2 )) . ( 139
)
These matrices, which are defined similarly to the matrix K of the symmetric Potts model introduced in (99), are linearly independent and obey in addition the simple algebra

K 2 1 = K 1 , K 2 2 = K 2 , K 2 0 = K 0 , K i K j = 0 if i = j . ( 140
)
We can thus parametrize A (n) as a n) are then found to be a

(n) 1 K 1 + a (n) 2 K 2 + a (n) 0 K 0 ; the non-zero eigenvalues of A (
(n) 1 , a (n) 2
and a (n) 0 . These three reals must thus be non-negative for A (n) to be semi-positive definite. The matrix M defined in [START_REF] Angelini | Spectral detection on sparse hypergraphs[END_REF] can then be expressed as

M στ = 1 + µ 1 1 η 1 (K 1 ) στ + µ 2 1 η q (K 2 ) στ + µ 0 qη 1 η q 1 η σ (K 0 ) στ 1 η τ , (141)
and a simple computation based on the algebraic properties stated above reveals that

η σ η τ A (n) στ = (µ 2 1 a (n) 1 K 1 + µ 2 2 a (n) 2 K 2 + µ 2 0 a (n) 0 K 0 ) στ . ( 142
)
Hence the linearized evolution equation ( 59) yields

a (n+1) i = E[ ]µ 2 i a (n) i for i = 0, 1, 2 . ( 143
)
The trivial fixed point a 1 = a 2 = a 0 = 0 becomes unstable as soon as one of the three coefficients a i grows under these iterations, hence we recover the Kesten-Stigum criterion E[ ] max(µ 2 1 , µ 2 2 , µ 2 0 ) = 1 at the limit of stability of the trivial fixed point, the parameters µ i being the non-trivial eigenvalues of M .

Following our usual program we incorporate the next order correction and look for a perturbative non-trivial fixed point around the Kesten-Stigum transition. Inserting the form given above for the matrices A and A into the generic equation ( 65) yields, after some computations, the following system of quadratic equations for a 0 , a 1 and a 2 :

a 1 = E[ ]µ 2 1 a 1 + E[ ( -1)] 2q 1 (1 + m) 2 (q 1 -3 -m)µ 4 1 a 2 1 + 2q 2 q µ 2 0 µ 2 1 a 0 a 1 , (144)
a 2 = E[ ]µ 2 2 a 2 + E[ ( -1)] 2q 2 (1 -m) 2 (q 2 -3 + m)µ 4 2 a 2 2 + 2q 1 q µ 2 0 µ 2 2 a 0 a 2 , (145)
a 0 = E[ ]µ 2 0 a 0 (146) + E[ ( -1)] 4q 1 q 2 q 3m 2 -1 (1 -m 2 ) 2 µ 4 0 a 2 0 + qq 1 (q 1 -1) 2q 2 (1 -m) 2 (1 + m) 2 µ 4 1 a 2 1 + qq 2 (q 2 -1) 2q 1 (1 + m) 2 (1 -m) 2 µ 4 2 a 2 2
From this system of equations one can recover, as a consistency check, the equations (100) of the symmetric q-state model and (116) of the asymmetric Ising case. The latter is indeed obtained with q 1 = q 2 = 1, in which case K 1 = K 2 = 0, the only parameter is a 0 which obeys indeed (116) with the identification µ 0 = θ. To recover the former case one takes µ 1 = µ 2 = µ 0 = θ, a 1 = a 2 = a 0 and m = (q 1q 2 )/2; then the three equations (144-146) reduces to (100). Note also that these equations coincide, in the special case q 1 = q 2 , µ 1 = µ 2 , m = 0, for which a 1 = a 2 , to the moment recursions derived in [START_REF] Liu | The Tightness of the Kesten-Stigum Reconstruction Bound of Symmetric Model with Multiple Mutations[END_REF].

Let us now come back to an arbitrary choice of parameters in (144-146), and discuss the bifurcation of the nontrivial solution of this system of equations at the Kesten-Stigum transition. This discussion must be divided according to which eigenvalue µ i causes the transition by fulfilling the condition E[ ]µ 2 i = 1 (we shall assume for simplicity that only one among µ 1 , µ 2 and µ 0 becomes critical).

Bifurcation driven by µ0

Let us first consider the case where the bifurcation is driven by µ 0 , i.e. where E[ ]µ 2 0 = 1 + with small, while

E[ ]µ 2 1 < 1 and E[ ]µ 2 2 < 1.
The dominant direction of the bifurcation being a 0 one can simplify the system (144-146) at lowest order into a single equation on a 0 :

0 = + E[ ( -1)] 4q 1 q 2 q 3m 2 -1 (1 -m 2 ) 2 µ 4 0 a 0 . ( 147
)
Remembering the positivity condition a 0 ≥ 0, one realizes that the bifurcating solution exists above the Kesten-Stigum transition (i.e. for > 0) if and only if the asymmetry between the two groups of labels is small enough, namely if m < m c = 1/ √ 3, as in the asymmetric Ising case. As in the right hand sides of (144-145) there are no terms proportional to a power of a 0 (without further multiplication by a 1 or a 2 ), the non-bifurcating unknowns a 1 and a 2 remain strictly equal to 0 in this solution.

Bifurcation driven by µ1

Suppose now that µ 1 is the critical eigenvalue (the case where µ 2 becomes critical can be deduced from this one by exchanging the two groups), i.e. that E[ ]µ 2 1 = 1 + with small, while E[ ]µ 2 2 < 1 and E[ ]µ 2 0 < 1. The lowest order equation on the bifurcating direction a 1 thus becomes

0 = + E[ ( -1)] 2q 1 (1 + m) 2 (q 1 -3 -m)µ 4 1 a 1 , (148)
with the sub-dominant coefficient a 0 being of order O(a 2 1 ) = O( 2 ), while a 2 remains strictly zero (within the system (144-146)). The sign of for which the non-trivial solution satisfies the constraint a 1 ≥ 0 is thus the one of -(q 1 -3-m).

To analyze the sign of this quantity we can exclude the cases where m = ±1, as these reduce to purely symmetric models with either q 1 or q 2 labels. The type of bifurcation thus depends on the (integer) value of q 1 as follows:

• if q 1 ≥ 4, for any value of m, the bifurcating solution exists for < 0, leading to the non-tightness of the Kesten-Stigum bound for the reconstruction. This is the conclusion reached in [START_REF] Liu | The Tightness of the Kesten-Stigum Reconstruction Bound of Symmetric Model with Multiple Mutations[END_REF], in the special case q 1 = q 2 and m = 0.

• if q 1 ∈ {1, 2}, for any value of m, the continuous solution is present above the Kesten-Stigum transition (for > 0).

• if q 1 = 3 the scenario depends on the asymmetry parameter m: for m < 0 the bifurcating solution exists for < 0, yielding a 1st order transition with the non-tightness of the Kesten-Stigum bound. On the other hand if m > 0 the non-trivial solution appears continuously in the large SNR regime, above the Kesten-Stigum transition.

Note that this classification is independent of the number q 2 of labels in the group which does not become critical at the Kesten-Stigum transition.

Higher-order terms and the existence of algorithmic spinodals

We have computed the next order in the expansion of (144-146), computing the coefficients of the terms that are cubic in the a i 's, by specializing the generic equations (71-73) to the symmetry pattern of the q 1 + q 2 model. This requires in particular the determination of the most generic symmetric tensors with 3 and 4 indices, B στ γ and C στ γβ , that are invariant under permutations of the labels inside G 1 and G 2 ; the resulting equations are rather long, we shall hence not write them completely but concentrate on the additional predictions they led us to.

As long as the coefficient of the quadratic term in the equation for the bifurcating a i is non-zero in the right hand side of (144-146), these higher order terms can only affect the solution quantitatively, but not qualitatively. Suppose first that the bifurcation is driven by µ 0 , and that m = m c = 1/ √ 3, in such a way that the first non-linear term in a 0 vanishes. In this case a 0 is solution of a quadratic equation of the form 0 = + w a 2 0 ; our computation yields explicitly the value of this coefficient w, which turns out to be proportional (with a positive constant depending only on q 1 and q 2 ) to the corresponding expression found in the asymmetric Ising case and written in (130), with µ 1 playing the role of θ. We argued this coefficient to be always negative for all degree distributions and sign of µ 1 , this case thus brings no novelty with respect to the situations investigated previously.

Suppose now that the bifurcation is driven by µ 1 , and that q 1 = 3, and m = 0, in such a way that the coefficient of a 2 1 in (144) vanishes. In this much more interesting case the leading order bifurcation equation becomes 0 = + w a 2 1 , with the following expression for the coefficient w (with E[ ]µ 2 1 = 1 at lowest order):

w = 36   -3 E[ ( -1)( -2)] E[ ] 3 + E[ ( -1)] E[ ] 2 2   4 E[ ] -1 - 12 sign(µ 1 ) E[ ] -1 - 2µ 0 1 -µ 0 + E[ ]µ 2 0 1 -E[ ]µ 2 0     (149)
The crucial point we want to emphasize is that w can be made positive for well-chosen values of the parameters of the model, in particular when |µ 0 | is close to |µ 1 | (but still strictly smaller for the bifurcation to be driven by µ 1 ). In such a case the non-trivial solution a 1 of the equation exists for < 0, hence the Kesten-Stigum bound is not tight. Let us now argue that the situation depicted in Fig. 2 must occur in some part of the phase diagram of the q 1 + q 2 model; for simplicity let us consider that the degree distribution is Poissonian with average c, that we take as the SNR. Suppose that q 1 = 3 and fix the values of the µ i 's in such a way that w > 0 in the expression of (149). For m = 0 the analysis above shows the existence of reconstruction down to c sp (m = 0) < c KS , while c alg (m = 0) = c KS as the bifurcating solution exists only for < 0. Suppose now that m is slightly increased to a small positive value; from (148) we conclude that a non-trivial perturbative solution exists for some range of c > c KS , but by continuity with the situation for m = 0 must undergo a bifurcation at some c alg (m) > c KS . Also by continuity the spinodal of the high-accuracy branch c sp (m) must persist for small enough m > 0, hence the existence of a bifurcation diagram as in Fig. 2. When m is further increased the two spinodals c sp (m) and c alg (m) collides and for even larger values of m the bifurcation diagram becomes the one of the left panel of Fig. 1. Indeed when m → 1 the model reduces to a symmetric SBM with q 1 = 3 communities. Preliminary numerical results obtained by a resolution of the cavity equations via the population dynamics algorithm suggest a rather narrow domain of parameters for which this phenomenon of coexistence of two non-trivial stable solutions is observable, for this reason we do not present numerical data to illustrate this model.

K. On the definition of accuracy and the maximal overlap estimator

The covariance matrix A στ = E[δ σ δ t ] appeared naturally in our expansions as a measure of the deviation between the fixed point distribution P (η) solution of the cavity equations and the trivial fixed point δ(ηη). Let us now briefly comment on its interpretation as the accuracy of an estimation procedure, and its connection with the maximal overlap estimator.

Consider the tree reconstruction problem explained in Sec. III C 1, and assume that the root had value τ in the broadcast process; an observer, which has no direct knowledge of τ , computes its posterior probability distribution η given the values of spins on far away vertices of the tree. If the observer proposes as an estimator of τ a random spin value chosen with probability η, the probability of success of the reconstruction is, on average with respect to the broadcast, the estimation and the tree, E τ [η τ ]. The probability of success if one had discarded all the observations, i.e. if one draws the estimator with the prior probability η, is η τ ; the accuracy, defined as the difference of these two probabilities, is thus E τ [δ τ ]. Averaging finally over the value τ of the unknown spin, we obtain the accuracy

a = τ η τ E τ [δ τ ] = τ A τ τ = Tr A , (150)
where we used the identity (50) between conditional and unconditional distributions. For binary spins σ = ±1 there is an affine mapping between the MMSE and the accuracy. Consider now the maximal overlap estimator defined in Sec. II A, for which the observer estimates the value of the root as argmax σ η σ . The probability of correct estimation can be expressed in different forms involving the conditional or unconditional distributions of η, namely

P corr = τ η τ E τ [I(argmax σ η σ = τ )] = E τ η τ I(argmax σ η σ = τ ) = E[max σ η σ ] , (151)
the first step resulting from the general change of density between condition and unconditional distributions expressed in [START_REF] Mézard | The Bethe lattice spin glass revisited[END_REF]. This quantity can easily be evaluated numerically from the resolution of the cavity equations by the population dynamics algorithm, it is however much more difficult to characterize it analytically than the accuracy (150). If we could indeed determine systematically A στ as a perturbative expansion in the small parameter κ in the neighborhood of the Kesten-Stigum transition, a similar determination is not possible for P corr . The scaling ansatz (61) means that around the KS transition, the dominant behavior of δ under P is described by δ/ √ κ d → X (where X has a symmetric distribution). We can thus conclude that P corr should behave as max σ η σ + C √ κ, but with a prefactor C that involves the whole distribution of the rescaled random vector X, and thus cannot be computed from a finite number of moments. An explicit determination of P corr can be achieved in the large degree limit, thanks to the Gaussian simplifications explained in Sec. IV F. One finds indeed in this limit

P corr = E e max σ Lσ , (152)
where the expectation is over a Gaussian vector L defined by its moments in Eq. (91). For instance in the symmetric Ising case (q = 2, m = 0), denoting λ = lim( E[ ]θ 2 ) the SNR, a short computation yields

P corr = 1 2 + √ 2λa 0 dt √ 2π e -1 2 t 2 , (153)
where a = a(λ) is the solution of

a = e -λa E e 2 √ 2λaZ e √ 2λaZ + e - √ 2λaZ - 1 2 , (154)
with Z a standard Gaussian random variable (of zero mean and unit variance). Expanding now these expressions around the Kesten-Stigum transition, i.e. setting λ = 1 + with → 0 + , one obtains the leading behavior a ∼ /2, while P corr ∼ (1/2) + /2π.

V. MOMENT EXPANSIONS FOR k-WISE INTERACTING ISING VARIABLES

We turn now to the second specialization of the formalism of Sec. III: we will consider generic k-wise interactions, but we restrict now to binary variables (q = 2), that for convenience we will represent as Ising spins, χ = {-1, 1}. As most of the reasonings are similar to the ones presented in Sec. IV we shall give less details on the computations and underline the main differences with the case of pairwise interacting Potts variables.

A. Fourier transforms of Boolean functions

The main ingredient defining the models under study here is a joint probability p j (σ 1 , . . . , σ k ) over {-1, +1} k , invariant under all permutations of its arguments. This symmetry implies that p j is a function of (σ 1 + • • • + σ k ) only, and can thus be specified by k real numbers (taking into account the normalization condition). The occupation models of [START_REF] Zdeborová | Constraint satisfaction problems with isolated solutions are hard[END_REF], whose definition was recalled in Sec. III, correspond to the special case of a p j vanishing for some values of (σ 1 + • • • + σ k ), and constant otherwise. A convenient way to specify a generic permutation invariant p j is via the following representation,

p j (σ 1 , . . . , σ k ) = 1 2 k   1 + γ 1 k i=1 σ i + γ 2 i<j σ i σ j + • • • + γ k σ 1 . . . σ k   , (155)
where the γ n are the Fourier coefficients of p j . They can be expressed as

γ n = E[τ 1 . . . τ n ] (156)
where the average is over a configuration (τ 1 , . . . , τ k ) drawn with probability p j (τ 1 , . . . , τ k ). Let us describe in these terms the conditional distribution p c (τ 1 , . . . , τ k-1 |τ ) obtained from p j . Because of its invariance under the permutations of its k-1 first arguments, it is fully described by the averages of products of n spins. These values are easily expressed in terms of the Fourier coefficients of p j , as

E[τ 1 . . . τ n |τ ] = γ n + τ γ n+1 1 + τ γ 1 for n = 1, . . . , k -1 . (157)
In what follows we will assume that the stationary probability distribution η is unbiased, i.e. η + = η -= 1 2 . For the reversibility assumption of Sec. III to hold in this case one needs the marginal probability of a single variable drawn from p j to be also unbiased. In terms of the Fourier coefficient representation this is equivalent to γ 1 = 0 (see Eq. ( 156)). We will actually make a stronger hypothesis on p j , namely that it is invariant under a global spin reversal: p j (σ 1 , . . . , σ k ) = p j (-σ 1 , . . . , -σ k ). This implies that not only γ 1 but all the Fourier coefficients γ p with p odd vanish. With this assumption (157) can be simplified into:

E[τ 1 . . . τ 2p-1 |τ ] = τ γ 2p , E[τ 1 . . . τ 2p |τ ] = γ 2p . (158)

B. Cavity equations and free-entropy functional

We have stated in Sec. III recursive equations obeyed by the distributions

P (n) τ (η), P (n)
τ (ν), and their unconditional versions P (n) (η), P (n) (ν), see [START_REF] Barthel | Hiding Solutions in Random Satisfiability Problems: A Statistical Mechanics Approach[END_REF][START_REF] Lesieur | Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications[END_REF][START_REF] Mossel | Reconstruction on Trees: Beating the Second Eigenvalue[END_REF][START_REF] Janson | Robust reconstruction on trees is determined by the second eigenvalue[END_REF][START_REF] Mézard | Reconstruction on Trees and Spin Glass Transition[END_REF][START_REF] Borgs | The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels[END_REF]. As we are dealing now with Ising variables we can use a more succinct notation, a probability distribution over a Boolean variable being parametrized by a single real. We shall use the following notations,

η σ = 1 + m σ 2 , ν σ = 1 + u σ 2 , (159)
with m and u in [-1, 1], and hence denote P

(n) τ (m), P (n) (m), P (n)
τ (u) and P (n) (u) for the above distributions expressed with this parametrization. The Belief Propagation equation [START_REF] Mossel | Reconstruction on Trees: Beating the Second Eigenvalue[END_REF] can then be reformulated as

m = f (u 1 , . . . , u ) = i=1 (1 + u i ) - i=1 (1 -u i ) i=1 (1 + u i ) + i=1 (1 -u i ) = tanh i=1 atanh (u i ) , (160)
with the normalization factor

z(u 1 , . . . , u ) = 1 2 i=1 (1 + u i ) + 1 2 i=1 (1 -u i ) . (161)
The other BP equation [START_REF] Janson | Robust reconstruction on trees is determined by the second eigenvalue[END_REF] reads in this notation:

u = f (m 1 , . . . , m k-1 ) = γ 1 + γ 2 k-1 i=1 m i + γ 3 i<j m i m j + • • • + γ k m 1 . . . m k-1 1 + γ 1 k-1 i=1 m i + γ 2 i<j m i m j + • • • + γ k-1 m 1 . . . m k-1 . ( 162
)
With the assumption of invariance of p j under global spin reversal the odd Fourier coefficients vanish and one can simplify this equation into

u = f (m 1 , . . . , m k-1 ) = 1 z(m 1 , . . . , m k-1 ) γ 2 k-1 i=1 m i + γ 4 i1<i2<i3 m i1 m i2 m i3 + . . . , z(m 1 , . . . , m k-1 ) = 1 + γ 2 i<j m i m j + γ 4 i1<i2<i3<i4 m i1 m i2 m i3 m i4 + . . . . (163)
Let us now discuss the symmetry properties of the distributions P (n) τ (m) and P (n) (m), and the relationships between them. The consequences of the Bayes theorem stated in [START_REF] Sly | Reconstruction for the Potts model[END_REF] become, for an unbiased stationary distribution η,

P (n) (m) = 1 2 P (n) + (m) + 1 2 P (n) -(m) , P (n) τ (m) = (1 + τ m)P (n) (m) , dP (n) (m) m = 0 . (164)
Actually the assumption of invariance under global spin reversal has further consequences: not only P (n) has zero average, but it is also symmetric. Hence one has

P (n) (m) = P (n) (-m) , P (n)
+ (m) = P (n) -(-m) . (165)
Combining these two set of properties yields particularly simple identities between moments of these distributions. The change of densities between P (n) τ

and

P (n) means indeed that E (n) + [f (m)] = E (n) [(1 + m)f (m)] for any function f (m). Applying this identity with f (m) = m 2p and f (m) = m 2p-1 yields E (n) + [m 2p ] = E (n) [m 2p ] + E (n) [m 2p+1 ] = E (n) [m 2p ] , E (n) + [m 2p-1 ] = E (n) [m 2p-1 ] + E (n) [m 2p ] = E (n) [m 2p ] , (166)
where we exploited the symmetry of P (n) that makes its odd moments vanish. These identities are well-known in the context of Low Density Parity Check Codes, see for instance lemma 3 in [START_REF] Montanari | Tight Bounds for LDPC and LDGM Codes Under MAP Decoding[END_REF]. Spelling out these identities for the lowest order moments we obtain

E (n) + [m] = E (n) + [m 2 ] = E (n) [m 2 ] , E (n)
+ [m 3 ] = E (n) + [m 4 ] = E (n) [m 4 ] . (167)
The distributions P (n) τ and P (n) have exactly the same symmetry properties as P (n) τ and P (n) , hence the random variables u enjoy the same identities as the m's.

The identity m) that follows from the invariance under global spin-flip allows to close the equations [START_REF] Barthel | Hiding Solutions in Random Satisfiability Problems: A Statistical Mechanics Approach[END_REF][START_REF] Lesieur | Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications[END_REF] on the two distributions P (n) + (m) and P (n) + (u), that are found to evolve with n according to

P (n) + (m) = P (n) -(-
P (n+1) + (m) = ∞ =0 p d P (n) + (u 1 ) . . . d P (n) + (u ) δ(m -f (u 1 , . . . , u )) , (168)
P (n) + (u) = τ1,...,τ k-1 p c (τ 1 , . . . , τ k-1 |+) dP (n) + (m 1 ) . . . dP (n) + (m k-1 ) δ(u -f (τ 1 m 1 , . . . , τ k-1 m k-1 )) , (169)
where the function f and f are given in ( 160) and ( 163) respectively. This form is very convenient for a numerical resolution by the population dynamics algorithm (see Appendix A for more details on this point).

Equivalently the unconditional version of the cavity equations read

P (n+1) (m) = ∞ =0 p d P (n) (u 1 ) . . . d P (n) (u ) δ(m -f (u 1 , . . . , u )) z(u 1 , . . . , u ) , (170)
P (n) (u) = dP (n) (m 1 ) . . . dP (n) (m k-1 ) δ(u -f (m 1 , . . . , m k-1 )) z(m 1 , . . . , m k-1 ) . (171)
The free-entropy functional can be expressed in these two versions of the cavity formalism from (24,28) as

φ(P, P ) = -E[ ] dP (m)d P (u) z e (m, u) ln z e (m, u) + E[ ] k dP (m 1 ) . . . dP (m k ) z c (m 1 , . . . , m k ) ln z c (m 1 , . . . , m k ) + ∞ =1 p d P (u 1 ) . . . d P (u ) z v (u 1 , . . . , u ) ln z v (u 1 , . . . , u ) , (172) φ(P
where

z e (m, u) = 1 + mu , (174)
z c (m 1 , . . . , m k ) = 1 + γ 2 i<j m i m j + γ 4 i1<i2<i3<i4 m i1 m i2 m i3 m i4 + . . . , (175)
z v (u 1 , . . . , u ) = 1 2 i=1 (1 + u i ) + 1 2 i=1 (1 -u i ) . (176)
C. Stability analysis of the trivial fixed-point via moment expansions

The functions f ({u i }) and f ({m i }) defined in the equations (160,163) vanish when all their arguments are equal to 0, which traduces the stationarity of the unbiased distribution η. As a consequence the distributions P (n) (m) = δ(m), P (n) (u) = δ(u) form a fixed point of the cavity equations. Following the same strategy as in Sec. IV D we shall now investigate its stability, by first locating the Kesten-Stigum transition where the trivial fixed point go from stable to unstable, and then looking for a bifurcating non-trivial fixed point in a neighborhood of the transition.

Linear analysis

Linearizing for small arguments the functions f ({u i }) and f ({m i }) defined in (160,163) and inserting this expansion in the conditional distribution recursions (168,169) yields very easily

E (n+1) + [m] = E[ ]E (n) + [u] , E (n) + [u] = (k -1)γ 2 E[τ 1 |+]E (n) + [m] , (177)
with E[τ 1 |+] = γ 2 as proven before in (158). Putting these two equations together, and expressing the conditional first moments in terms of the unconditional second moments according to (167) gives

E (n+1) [m 2 ] = E[ ](k -1)γ 2 2 E (n) [m 2 ] . (178)
This implies that the Kesten-Stigum transition occurs when

E[ ](k -1)γ 2 2 = 1 ; (179)
in the following we shall assume that the second Fourier coefficient does not vanish, γ 2 = 0, for this bifurcation to occur at a finite value of E[ ] (this excludes notably the case of a XORSAT constraint for p j whenever k ≥ 3).

Second order expansion: the continuity of the Kesten-Stigum transition

We look now for a fixed point distribution P (m) in the neighborhood of the Kesten-Stigum transition; we need to make an ansatz on the behavior of its moments in order to reduce the functional bifurcation problem to a finitedimensional one, as already explained for the case of Potts variables in Sec. IV D. Thanks to the spin reversal symmetry we known that for all odd moments E[m 2p+1 ] = E[u 2p+1 ] = 0; we assume the existence of a small parameter κ such that the even moments scale as E[m 2p ] = O(κ p ), E[u 2p ] = O(κ p ). Pushing the expansion of f ({u i }) and f ({m i }) to the order needed to obtain the first correction to the variances of u and m yields after a short computation:

E[m 2 ] = E[ ]E[u 2 ] -E[ ( -1)](E[u 2 ]) 2 + O(κ 3 ) , (180)
E[u 2 ] = (k -1)γ 2 2 E[m 2 ] -(k -1)(k -2)γ 3 2 (E[m 2 ]) 2 + O(κ 3 ) . (181)
Eliminating the variance of u gives us a single equation on E[m 2 ]; we shall denote a = E[m 2 ]/2 in such a way that this quantity corresponds to the one of Sec. IV D, which obeys

a = E[ ](k -1)γ 2 2 a -2 E[ ](k -1)(k -2)γ 3 2 a 2 -2 E[ ( - 1
= -2 (k -2)γ 2 + E[ ( -1)] E[ ] 2 a . (183)
We shall show now that the expression in the square bracket is non-negative for all the models encompassed by the study of this Section, hence that the bifurcating solution (which must certainly obey the positivity condition a = E[m 2 ] > 0) always exists for > 0, i.e. in the regime of parameters where the trivial fixed point is unstable. To prove our claim we first notice that the Fourier coefficient γ 2 lies necessarily in the interval -1 k-1 , 1 . Indeed, from the interpretation of these coefficients as spin averages given in (156) we obtain

E[(τ 1 + • • • + τ k ) 2 ] = E[kτ 2 1 + k(k -1)τ 1 τ 2 ] = k(1 + (k -1)γ 2 ) ≥ 0 ⇒ γ 2 ≥ - 1 k -1 , (184)
where we have merely exploited the permutation invariance and the fact that Ising spins square to 1. Moreover the upper-bound γ 2 = E[τ 1 τ 2 ] ≤ 1 is obvious. Then we rewrite the square bracket of (183) as

E[ 2 ] -E[ ] 2 E[ ] 2 + 1 - 1 E[ ] + (k -2)γ 2 = E[ 2 ] -E[ ] 2 E[ ] 2 + (1 -(k -1)γ 2 2 + (k -2)γ 2 ) , (185)
where we used the Kesten-Stigum condition E[ ](k -1)γ 2 2 = 1. The first term above is proportional to the variance of the offspring distribution, hence non-negative; as 1 -(k -1)x 2 + (k -2)x ≥ 0 for x ∈ [-1/(k -1), 1], the authorized interval of variation of γ 2 , the second term in (185) is also non-negative.

Third order expansion

We have also pushed the expansion in moments to the next order; compared to the Potts case the computations are much easier, thanks on the one hand to the binary nature of the variable (hence the moments to be determined are scalar quantities that do not bear any spin index), and on the other hand to the spin-flip symmetry (which cancels the moments of odd order). Let us introduce for convenience some more compact notations, that are reminiscent of the ones used in Sec. IV:

a = 1 2 E[m 2 ] , b = E[m 4 ] , a = 1 2 E[u 2 ] , b = E[u 4 ] . (186)
These quantities obey the following set of equations:

a = E[ ] a -2 E[ ( -1)] a 2 + E[ ( -1)] a b + 20 3 E[ ( -1)( -2)] a 3 , (187)
b = E[ ] b + 12 E[ ( -1)] a 2 , a = (k -1)γ 2 2 a -2(k -1)(k -2)γ 3 2 a 2 + (k -1)(k -2)γ 4 2 a b + 4(k -1)(k -2)(k -3) γ 2 4 6 -γ 2 2 γ 4 + 5γ 4 2 2 a 3 , b = (k -1)γ 4 2 b + 12 (k -1)(k -2)γ 4 2 a 2 ,
where in a and a (resp. in b and b) we neglected terms of order κ 4 (resp. κ 3 ).

The expansion of the free-entropy to the corresponding order yields

φ(a, b, a, b) = (k -1)γ 2 2 a 2 - 4 3 (k -1)(k -2)γ 3 2 a 3 + 1 24 (k -1)γ 4 2 b 2 + (k -1)(k -2)γ 4 2 a 2 b (188) +2(k -1)(k -2)(k -3) γ 2 4 6 -γ 2 2 γ 4 + 5γ 4 2 2 a 4 + E[ ] a 2 - 4 3 E[ ( -1)] a 3 + 1 24 E[ ] b 2 + E[ ( -1)] a 2 b + 10 3 E[ ( -1)( -2)] a 4 -2 a a - 1 12 b b ;
one can check that the derivatives of this expression vanish when the cavity equations (187) are fulfilled, a property which arises from the variational character of the free-entropy. Another short computation also reveals that the free-entropy, computed on the non-trivial perturbative fixed-point which here always exists for > 0, behaves as 3 (with a positive prefactor) when → 0 + .

D. Numerical results for two examples

In order to confirm our analytical expansions, and to complement them with a global bifurcation analysis, we have solved numerically the cavity equations for two cases of occupation models, as we shall now detail.

Bicoloring

We considered first the bicoloring problem, for which the joint probability

p j (σ 1 , . . . , σ k ) is 0 if σ 1 = • • • = σ k = ±1, 1/(2 k -2)
otherwise. This constraint forbids monochromatic hyperedges, and give an equal weight to all configurations with at least one positive and at least one negative variable around it. One easily finds the corresponding value of the Fourier coefficients,

γ n = - 1 2 k-1 -1 (189)
for all even n between 2 and k (the odd coefficients vanish due to the up-down symmetry). We used for the degree distributions p = p Poisson laws of average αk, that corresponds to a random hypergraph with M = αN constraints. The criterion (179) shows then that the Kesten-Stigum transition happens at As discussed there our analytical prediction on the existence of a bifurcating solution above the Kesten-Stigum transition is confirmed by this numerical results, and for k = 3, 4, 5 we find explicit realizations of the bifurcation diagrams presented in the left panel of Fig. 1 and in both panels of Fig. 2. On Fig. 9 we plot the complexity (i.e. minus the free-entropy) of these fixed-points; the location of the discontinuity in the derivative of the solution that minimizes the complexity defines the threshold α IT reported in Table I. We chose here to plot the opposite of the free-entropy as it is a more familiar quantity in the context of random, instead of planted, constraint satisfaction problems. The interpretation of this coexistence of solutions in this context has been discussed, also on the example of the bicoloring, in [START_REF] Gabrié | Phase transitions in the q-coloring of random hypergraphs[END_REF].

α KS = (2 k-1 -1) 2 k(k -1) . (190)

2-in-4 satisfiability

We have also considered the so-called 2-in-4 satisfiability model in the nomenclature of [START_REF] Zdeborová | Constraint satisfaction problems with isolated solutions are hard[END_REF], defined by k = 4 and p j (σ 1 , σ 2 , σ 3 , σ 4 ) = I(σ 1 + σ 2 + σ 3 + σ 4 = 0)/6: the constraint imposes that among the four variables exactly two are positive and two negative. The corresponding Fourier coefficients are

γ 1 = γ 3 = 0 , γ 2 = - 1 3 , γ 4 = 1 ; (191)
note that this case saturates the lower-bound on γ 2 .

In our numerical investigation we have used truncated Poisson distributions for p and p , namely

p = 1 e c -1 -c c ! I( ≥ 2) , p = 1 e c -1 c ! I( ≥ 1) . (192)
The averages of these distribution are

E[ ] = c 1 -e -c 1 -(c + 1)e -c , E[ ] = c 1 -e -c . (193)
In terms of this parameter c the Kesten-Stigum transition is thus found to happen at c KS ≈ 2.82144. Note that this is a locked model in the sense of [START_REF] Zdeborová | Constraint satisfaction problems with isolated solutions are hard[END_REF], as the minimal degree of a variable is 2 and no pair of configurations allowed by p j differ from one single spin flip: the typical solutions of such a Constraint Satisfaction Problem on a locally tree-like factor graph are separated by an Hamming distance that diverges with the graph size. Nevertheless this property does not have any effect on the existence of a continuously bifurcating solution above the Kesten-Stigum transition. In some sense the locked property is a "high-frequency condition" on p j , whereas we have shown that the criterion (185) only depends on the low frequency Fourier coefficient γ 2 .

Indeed our numerical resolution of the cavity equations showed that a continuously growing solution exists right above the Kesten-Stigum transition, and disappears at c alg ≈ 2.84. Note that the interval [c KS , c alg ] is very small, which explains why it remained unnoticed in [START_REF] Zdeborová | Quiet planting in the locked constraint satisfaction problems[END_REF]. This model thus falls in the scenario sketched on the right panel of Fig. 2, with the other thresholds c sp ≈ 1.256 and c IT ≈ 1.853 correctly determined in [START_REF] Zdeborová | Quiet planting in the locked constraint satisfaction problems[END_REF]. Actually for locked models the high-accuracy fixed point is perfectly informative, as it corresponds to P τ (m) = δ(mτ ); the transition at c sp corresponds to a change of stability of this perfectly informative fixed point, that can be tested by taking ε → 1 after n → ∞ in [START_REF] Liu | The Tightness of the Kesten-Stigum Reconstruction Bound of Symmetric Model with Multiple Mutations[END_REF], a procedure termed small noise reconstruction in [START_REF] Zdeborová | Constraint satisfaction problems with isolated solutions are hard[END_REF].

VI. NUMERICAL EXPERIMENTS ON SINGLE SAMPLES

This Section is devoted to a study of the behaviour of the Belief Propagation (BP) algorithm run on given instances of two inference problems defined and studied analytically in the previous Sections, namely the planted hypergraph bicoloring and the asymmetric SBM with two groups. As a matter of fact, most of the analytical results presented in the rest of the paper directly apply to (infinite) tree reconstruction problems, their interpretation in terms of inference on (large but) finite size graphs relying on delicate conjectures of the cavity method, as briefly discussed in Sec. III C 2. The experiments reported in this Section will allow us to test this connection, and to confront quantitatively the predictions of the tree reconstruction problem, studied numerically via the population dynamics algorithm, and the results of BP on single large instances. Because of the local convergence of the graph problems towards trees it is quite simple to see that a finite number of iterations of BP can be described analytically, in the thermodynamic limit, by a finite number of the tree distributional iterations [START_REF] Barthel | Hiding Solutions in Random Satisfiability Problems: A Statistical Mechanics Approach[END_REF][START_REF] Lesieur | Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications[END_REF]. There are, however, two aspects that make the graph-tree connection much less trivial and justify these numerical tests: (i) on finite graphs BP can be run until convergence to a fixed point (FP), i.e. for a number of iterations much larger than the girth of the graph, this regime cannot a priori be described in terms of tree-like local properties and could be sensitive to the long cycles of the graph; (ii) in the graph problems there is initially no observation of the labels on the vertices, the infinitesimal information of the tree robust reconstruction problem must thus arise from the amplification of noise in the initial condition of BP.

A. Generation of planted problems, BP equations and observables

The models that we study numerically, namely random hypergraph bicoloring and asymmetric SBM with 2 groups, have been already defined in detail in Sec. III A. Here we just give additional informations about the generation of the instances with a planted solution, and about the BP equations and the way we solve them, for the convenience of the reader who would like to repeat our numerical tests. Both models have Ising (i.e. binary) variables σ i ∈ {-1, 1}, and thus the marginals can be written in terms of a single scalar variable.

Random hypergraph bicoloring

The random ensemble of hypergraph bicoloring problems has three parameters: the number of variables N , the number of constraints M = αN , and the degree of the factor nodes k (i.e. the number of variables per constraint). The N variables are divided in 2 groups of equal size and the planted configuration is defined as σ * i = 1 in the first group and σ * i = -1 in the second one. For each of the M constraints we extract k variables uniformly at random, conditional on the k variables not belonging all to the same group (we implemented this condition by a rejection method). The random graph thus obtained can be described by the set E of edges (ia) connecting variables nodes and factor nodes (1 ≤ i ≤ N , 1 ≤ a ≤ M and |E| = KM ).

One can write the posterior distribution of σ given the observation of the graph and treat this probability measure with the BP algorithm, that can be put after some simplifications under the form of messages η i→a and ηa→i passed between variables and interactions obeying the following equations:

η (t) i→a = b∈∂i\a η(t-1) b→i b∈∂i\a η(t-1) b→i + b∈∂i\a (1 - η(t-1) b→i ) , (194)
η(t) a→i = γ η(t-1) a→i + (1 -γ) 1 -j∈∂a\i η (t) j→a 2 -j∈∂a\i η (t) j→a -j∈∂a\i (1 -η (t) j→a ) , (195)
where ∂i = {a : (ia) ∈ E} and ∂a = {i : (ia) ∈ E} are the local neighborhoods of variable and factor nodes respectively, and γ is a damping factor set to 0.5 in most of our numerical simulations. The BP messages η i→a and ηa→i represent the probability that variable i belongs to a given group (say the first group) in a modified graph where some of the edges have been removed: in particular η i→a considers the graph where constraint a has been removed, while ηa→i considers the graph where constraints in ∂i \ a have been removed. BP messages are initialized in the following way: with probability q 0 we set η(0) a→i = η (0) i→a = I[σ * i = 1] and with probability 1q 0 we set η(0) a→i = 0.5 and η (0)

i→a ∈ [0.45, 0.55] uniformly at random. The parameter q 0 (the q 0 and q of this Section should not be confused with the number of states of the Potts model of the rest of the paper) thus controls the amount of direct information on the planted configuration we use in this initial condition. Of course only q 0 = 0 should be considered if we want to study BP as an inference algorithm that does not use any information on the hidden labels. It is, however, useful to allow arbitrary values of q 0 as a tool to investigate the connections between the tree and graph problems. The choice of distributing the messages in the interval [0.45, 0.55] for the non-informed vertices is made to avoid the trivial fixed point with all messages η = η = 0.5.

BP messages are not updated all in parallel, as the time indices in Eqs. (194,195) may suggest. In each step of BP we visit all the variables once in a random order: for each variable i we compute all the outgoing messages η i→a according to Eq. ( 194) and immediately we update all the BP messages leaving neighbouring factor nodes according to Eq. (195). By these tricks (and the use of damping) we avoid any undesirable oscillation and improve convergence to fixed points. Convergence is declared achieved if, in a given step of BP, all messages change by less than a pre-fixed threshold, i.e. |η

m i = a∈∂i η a→i -a∈∂i (1 -η a→i ) a∈∂i η a→i + a∈∂i (1 -η a→i ) . ( 196
)
Because of the global spin-flip symmetry of the model the mean magnetization m = i m i /N is zero, while detection of the planted solution is signalled by the following order parameters: the staggered magnetization m s (i.e. the absolute value of the mean overlap with the planted configuration), the magnetization variance m 2 (recall that m = 0 here), that equals the mean overlap between two real replicas, and the maximum overlap q with the planted configuration, defined as

m s = 1 N i m i s * i , m 2 = 1 N i (m i ) 2 , q = 1 N i sign(m i )s * i . (197)
The Bethe (replica symmetric) entropy is given by the following expression

S = 1 N i log a∈∂i η a→i + a∈∂i (1 -η a→i ) + 1 N a log 1 - i∈∂a η i→a - i∈∂a (1 -η i→a ) - 1 N (ia) log [η a→i η i→a + (1 -η a→i )(1 -η i→a )] , (198)
that reduces to S para = log(2) + α log(1 -2 1-k ) on the paramagnetic (trivial) BP fixed point, where all messages are non-informative η a→i = η i→a = 1/2.

Asymmetric two groups SBM

An instance of the asymmetric SBM with 2 groups is generated using the following 4 parameters: the number of variables N , the mean degree d, the asymmetry m and the parameter θ related to the SNR. The N variables are divided in 2 groups of sizes N 1 = 1+m 2 N and N 2 = 1-m 2 N , such that the planted configuration is σ * i = 1 in the first group and σ * i = -1 in the second group. Then the edge set E of the interaction graph between the variable nodes is generated by selecting uniformly at random M 11 =

c στ = d(1 + θ (σ-m)(τ -m) 1-m 2 ). It is easy to check that M11 N1 + M12 2N1 = M22 N2 + M12 2N2 = d 2 ,
i.e. the mean degree in each group is the same. It is worth noticing that these rules define a "microcanonical" ensemble of random graphs having a fixed number of edges. In the "canonical" ensemble of random graphs, each possible edge is chosen independently with a given probability and thus the number of edges is a random variable. The difference between the two ensemble vanishes in the large N limit, and produces fluctuations of order O(1/ √ N ) in intensive observables measured in finite graphs. The BP equations for the posterior measure of the SBM were written in the general case in [START_REF] Decelle | Phase transition in the detection of modules in sparse networks[END_REF][START_REF] Decelle | Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications[END_REF], we reproduce here this derivation for the asymmetric two group model.

We shall rewrite the posterior probability as the Gibbs measure of an Ising model q 0 =0 q 0 =1 pop dyn FIG. 10: The order parameter ms detecting the planted configuration for k = 3 (left), k = 4 (center) and k = 5 (right), obtained by running BP on three samples of size N = 10 6 for each value α. The lines are the predictions obtained by solving the cavity equations for the reconstruction problem on a tree, and plotted also in Fig. 6, with the correspondence ms = 2a explained in the text.

P[σ] ∝ exp i H i σ i + i<j J ij σ i σ j , (199)
In Figure 10 we show the order parameter m s that detects the planted configuration. Red filled points correspond to the BP fixed point reached starting with the q 0 = 0 initial condition (i.e. with no direct information on the planted configuration), while blue open points correspond to the BP fixed point reached from the q 0 = 1 initial condition (complete information on the planted configuration). For comparison we also draw with lines the results obtained solving via population dynamics the cavity equations: red (resp. blue) line corresponds to results obtained with an initial condition (30) having ε = 10 -3 (resp. ε = 1), while green line is the result that is obtained with both initial condition (i.e. it is independent on the initial condition). These cavity equations results were already plotted in Fig. 6 in slightly different units, namely a = m s /2. Let us explain the reasoning behind this conversion. A technical statement of the tree-graph connection hypothesis of the cavity method is that the empirical distribution of the magnetizations m i computed at a BP fixed point of a large finite graph, conditional on σ * i = τ , should be well approximated by the distribution P τ (m) (on the infinite tree), in formula

i g(m i )δ σ * i ,τ i δ σ * i ,τ ≈ E τ [g(m)] , (220)
for any function g. Applying this identity with g(m) = m, and recalling that for models with a global spin-flip symmetry

E + [m] = -E -[m] = E[m 2 ] = 2a yields the identification m s = 2a.
For each α value we run BP on three different samples and we report in the plots only the data corresponding to cases where the convergence criterion was met within 10 4 BP steps (Fig. 11 shows that this happens most of the time). Zooming in the plots one should be able to see three data points very nearby; if one fails to see three different points it is because the data from different samples perfectly coincide or because BP on some samples did not reach convergence (the last case happen especially at α KS and very close to it).

We notice that for all the cases where BP reaches a fixed point, the latter is very well described by the cavity equations derived in the thermodynamic limit for the tree reconstruction problem. When different initial conditions of BP lead to different fixed points one observes, as expected, that the one reached with q 0 = 0 is associated to the robust reconstruction version of the tree problem (ε → 0), while q 0 = 1 reproduces the reconstruction one (ε = 1). Sample-to-sample fluctuations can be appreciated only slightly on the right of α KS and close to the spinodal points at α sp and α alg .

We observe that for α > α KS BP with q 0 = 0, i.e. the version of the algorithm that does not use any direct information on the planted configuration, can actually detect it in all the samples we have studied, although for α < α alg the detection is sub-optimal (hybrid-hard phase). For α < α alg BP can achieve the optimal detection only if initialized with a q 0 value large enough (we shall discuss this point later, when searching for the unstable fixed point, separating the two stable fixed points already found).

In Figure 11 we show the convergence times of BP for k = 3 (left) and k = 5 (right). For each system size (N = 10 5 , 10 6 ) and initial condition (q 0 = 0, 1) we study 3 samples.

For k = 3 we observe that convergence times strongly increase around the KS threshold, where also strong sampleto-sample fluctuations arise and the size dependence can be appreciated (consider that at α KS BP did not reach a fixed point for any of the N = 10 6 samples). Away from α KS convergence times are size-independent, and only weakly dependent on the initial condition for α < α KS .

K=3

α KS convergence time α q 0 =1 N=10 5 q 0 =1 N=10 6 q 0 =0 N=10 5 q 0 =0 N=10 6

K=5

α sp α KS α alg convergence time α q 0 =1 N=10 5 q 0 =1 N=10 6 q 0 =0 N=10 5 q 0 =0 N=10 6 FIG. 11: Times to meet the BP convergence criterion (i.e. any marginal must change by less than 10 -8 ) for k = 3 (left) and k = 5 (right), 2 system sizes (N = 10 5 , 10 6 ) and 2 different initial conditions (q0 = 0, 1). A data point with a time 10 4 means BP did not reach convergence.

For k = 5 convergence times increase not only at α KS , but also at the spinodal points α sp and α alg . The behavior of BP strongly depends on the initial condition (recall that in the region α sp < α < α alg BP reaches two different fixed points depending on the value of q 0 , see right panel in Figure 10). The dependence on the system size between N = 10 5 and N = 10 6 is not evident and sample-to-sample fluctuations for N = 10 5 are definitely larger. In Figure 12 we show several order parameters that can detect the planted configuration: m s , m 2 and q. In order to make the plot cleaner we have averaged over the samples where BP reached a fixed point.

We notice that the Nishimori equality m s = m 2 is very well satisfied in all the BP fixed points we reached. This is expected from the fact that the planted configuration is a typical configuration of the posterior distribution, the mean overlap with the planted configuration m s should be equal to the mean overlap between two replicas m 2 . One can also derive this property from the correspondence (220) with the tree computation, and the consequence of the Bayes theorem stated as moment identities in Sec. V.

As expected, the maximum overlap q is the largest order parameter (larger than m s ). According to Sec. IV K q should have a square root singularity at α KS ; this is not visible from the data of because of strong fluctuations in the neighborhood of α KS .

We investigated further the properties of the BP fixed points, by computing their Bethe entropy given in Eq. ( 198), the results being displayed in Figure 13. In the top panels we also show the paramagnetic entropy (the one of the trivial fixed point) with a green straight line. The comparison with the results of the cavity equations is made with the correspondence S = S para + φ, with φ the free-entropy of Eq. (173), to compensate for a different choice of normalization. The dominating fixed point, that is the fixed point providing the right entropy of the posterior probability distribution, is the one with with the largest entropy at each value of α. The case k = 5 clearly shows that, while on some branches the entropy can be negative, the dominating one is always positive (as it should be by definition of the entropy of a probability measure over a discrete set). FIG. 13: Bethe RS entropy computed at the BP fixed points. The lower panels show the difference with respect to the paramagnetic entropy in order to show better the difference which is tiny in some cases. For k = 5 the difference is too small to be estimated reliably via population dynamics and so we report only data obtained via BP.

The lower panels in Figure 13 serve to highlight the way the entropy departs from the paramagnetic curve at α KS . In particular for k = 4 it is possible to appreciate the crossing of the entropies obtained with the two different initial conditions (q 0 = 0 and q 0 = 1) taking place at α IT , that is hardly visible in the corresponding upper panel. Note that for k = 5 the difference S -S para is extremely small, hence we did not manage to estimate it from the population dynamics algorithm. Nonetheless the entropy computed on the BP fixed point clearly shows a stable increase with respect to the paramagnetic value, with quite strong sample-to-sample fluctuations (given by the spread of the three points in the figure).

We have shown evidence that for k ≥ 4, in the range α sp ≤ α ≤ α alg there exist at least two different fixed points of BP (along with their symmetric partners under the global spin-flip symmetry). At α IT the entropies of these two BP fixed point cross and this corresponds, in the thermodynamic limit, to a first order transition between two different thermodynamic states. Running BP without information on the planted configuration (q 0 = 0), the drastic change in the posterior distribution taking place at α IT is not visible: the algorithm remains confined to the low-informative branch until α alg . By analogy with the bifurcation theory of fixed-point systems of equations (even if α is not here a parameter modifying smoothly a set of equations of constant dimension) we expect a branch of unstable fixed points of BP to exist in the range of parameters α sp ≤ α ≤ α alg , and to connect these two branches as in the scalar toy model sketched in Fig. 2. However, getting evidence of the existence of this unstable fixed point is very difficult, because it is repulsive by its very nature.

We report in Figure 14 the evidence we have gathered in favour of this hypothesis. On its left panel we show the evolution of the order parameter m s as a function of the number of iterations of the BP updates, for different values of the initialization parameter q 0 . During the evolution all variables are updated; in order words q 0 is not the fraction of variables pinned to the value of the planted configuration. So any fixed point we find is a fixed point of the standard BP algorithm. The initial condition is just used to aim the algorithm to different fixed points, but then the BP algorithm is unconstrained. The evolution of BP at α = 4.68 with different values of q 0 reported in the left panel of Figure 14 clearly shows that for q 0 large enough BP converges to the same high-information fixed point reached for q 0 = 1, while for q 0 small enough only the low-information fixed point can be reached. Note that it is very hard to precisely define a separatrix value q * 0 that separates the two regimes, because BP is a stochastic algorithm, so its behaviour is not deterministically fixed by the initial condition, but also by the random numbers used during the evolution to choose the order of update of the BP messages. This means that, for the same q 0 ≈ q * 0 , it may happen that two evolutions converge to different fixed points. Nevertheless the left panel of Figure 14 show evidence that some evolutions of BP (those with q 0 = 0.266 and q 0 = 0.268 in the present figure) remain for a long time on a stationary regime which is neither of the two stable fixed points already found: we define this regime as the unstable fixed point of BP. Although the precise value of q 0 is not significant for the argument we just made, the value of m s on the unstable fixed point can be measured with a reasonable uncertainty. We repeated the above procedure for several α values in the range [α sp , α alg ] and we report in the right panel of Figure 14 the summary of the results for k = 4, with open blue symbols showing the unstable branch in addition to the results already presented in Fig. 10.

C. Results for the asymmetric stochastic block model with two groups

As discussed in Sec. IV I the asymmetric SBM with two groups undergoes different kinds of phase transitions depending on the level of the asymmetry: for |m| < m c = 1/ √ 3 the transition is continuous, while for |m| > m c the transition is discontinuous. We focused our analysis on 2 values of m, namely m = 0.4 belonging to the former case and m = 0.8 belonging to the latter case. We shall present results for a rather small average degree d = 4, for which the Kesten-Stigum transition occurs at θ KS = 0.5, but we have checked that the same conclusions apply to the case d = 8. We run BP only on problems of a very large size (N = 10 7 ) in order to reduce as much as possible the finite size effects. We show in Figure 15 a comparison of the properties of the fixed-point reached by BP on single samples with the results of the population dynamics study of the tree problem, concentrating on values of θ close to the Kesten-Stigum transition, where fluctuations become more significant. In the left panel we show data for m = 0.4 where the transition is continuous: we report both the values of m s and m 2 at the fixed point in order to show how well the Nishimori condition is satisfied on a given sample. For each sample (we run BP on 3 different samples for each θ value) both the runs with q 0 = 0 and q 0 = 1 converge to exactly the same fixed point or did not converge within the maximum number of iterations t max = 10 4 (the latter happened for all the 3 samples at θ = 0.5 and for one sample at θ = 0.502). We conclude that the main effects of being close to the critical point are the lack of convergence and some visible sample-to-sample fluctuations (remember we run BP on samples of size N = 10 7 ). Nevertheless the prediction coming from population dynamics is accurate even in the vicinity of θ KS .

In the right panel of Figure 15 we show data for the overlap with the planted configuration m s measured in 3 samples of size N = 10 7 and asymmetry m = 0.8 > m c . Starting from an non-informative initial condition (q 0 = 0) the planted configuration can be detected only for θ ≥ θ KS , while with an informative initial condition (q 0 = 1) the planted configuration can be detected for θ ≥ θ sp . The Nishimori condition m 2 = m s is verified with such a good accuracy that we do not plot the data for m 2 , the points being almost perfectly superimposed. The prediction of the population dynamics is faithful, although sample-to-sample fluctuations are still clearly visible, even for such large sizes. The quantity that mostly changes from sample to sample is the location of the spinodal point θ sp , where the informative fixed point first appears: given θ sp , the rest of the curve is pretty well conserved and sample-independent.

One may wonder how we can 'follow' a sample varying θ (see right panel in Figure 15) given that at different θ values the graph has a different number of links within and between the communities. The construction of the graph for each value of θ is a random process and we identify the sample with the random seed used by the algorithm. The stochastic algorithm that builds the graph is such that when it is run with the same seed (and so with the same sequence of pseudo-random numbers) and two not too different θ values most of the links are in common between the two graphs. This is the reason why we can 'follow' a sample in θ. The very good agreement between the BP results and the population dynamics shown in Fig. 15 actually hides a subtle point that we shall now explain in the case m = 0.4, for which the transition at θ KS is continuous. We have indeed observed that, with the non-informative initial condition (q 0 = 0), different runs of BP on the same sample converge to two different fixed points when θ > θ KS , with comparable probability (as soon as q 0 > 0 this issue disappears, but as an inference algorithm BP should not use any information on the planted configuration). The properties of these two fixed points are displayed in Fig. 16 (for θ ≤ θ KS the trivial fixed point is unique and has m s = m 2 = m 2 and m = q = m). We report with red full points the data corresponding to the dominating fixed point, i.e. the one having the largest value of log(Z), and with blue empty points the data corresponding to the sub-dominant fixed point. Comparing the first two panels in Figure 16 we see that the dominating FP satisfies the Nishimori condition m s = m 2 , while the sub-dominant one does not. Also the condition m = m is satisfied by the dominant FP (within finite size fluctuations), while the sub-dominant FP typically violates such a condition. For all these reasons we consider the dominant fixed-point as the correct one, that is why we reported in Fig. 15 only the data corresponding to this one.

The existence of 2 FPs beyond the KS threshold can be justified by the following reasoning. Consider first the symmetric case m = 0, which enjoys an exact global spin-flip symmetry (corresponding to the exchange of the two communities in the SBM interpretation). As a consequence of this symmetry there must be (at least) two non-trivial FP that arise at the Kesten-Stigum transition from the bifurcation of the trivial one, these two FPs having opposite values of the local magnetizations. Consider now a slight increase of m; by continuity one expects the two FPs to persist, even if they are not anymore symmetric one of the other, and in particular they do not have the same value for their free-entropy log(Z). What is somehow unexpected is the observation that BP reaches both FPs with similar probabilities. The only difference is in the time BP takes to reach these 2 FPs: this is shown in the sixth panel in Figure 16 where it is evident that reaching the dominating FP requires a smaller number of iterations (the interpolating power law fit has an exponent ≈ -2/3). It seems that the small difference in log(Z) between the 2 FPs does not influence enough the BP evolution at the very beginning, when the choice of the basin of attraction is made; the only effect is to speed up the evolution in case the basin of attraction of the dominating FP is eventually chosen.

From the data shown in Figure 16 it is clear the dominating FP is the one we would like BP to reach, since it is the one better correlated with the planted configuration satisfying the right conditions. However, when running BP from a non-informative initial condition we may likely end up in the sub-dominating FP. The simplest solution is to run BP several times, until both FPs are found and the one with largest Z is then chosen. Actually this procedure may be slow, and so we have found a more efficient way to reach both FPs in just one run of BP.

At θ KS the bifurcation of the trivial FP produces 2 FPs which are on opposite sides, that is the unstable FP stays more or less on the midpoint of the line joining the 2 stable FPs. This property remains approximately true also for θ > θ KS and we can exploit it in order to 'jump' from one FP to the other one. Once BP reaches a FP with messages {u i→j } we can produce an initial condition for a second BP run with the transformation

u (0) i→j = 2K -u i→j (221)
(remember the non-informative FP has all messages equal to K). We have checked this initial condition always brings BP to the other FP. And so we can find both FPs with just 2 runs (the second being very fast, thanks to the initial condition which is pretty close to the FP).

The BP initial condition for the first run, u (0) i→j = Lτ 0 i with L = 100 and τ 0 i distributed according to Eq. ( 216), is quite 'drastic' (i.e. has very strong messages) in order to be far from the non-informative FP. For θ > θ KS this is actually not necessary, given that the non-informative FP is locally unstable. So, in order to check that all what we have described above does not depend on such a drastic first initial condition, we have repeated the numerical experiments in the regime θ > θ KS by using a different initial condition, which is much closer to the non-informative FP u (0)

i→j = K(1 + ετ 0 i ) (222)
with ε = 10 -3 and τ 0 i again distributed according to Eq. ( 216). The results are identical to those with the drastic first initial condition.

For the sake of completeness let us also mention that for θ > θ KS and m large enough (e.g. at θ = 0.6 in the range m 0.46) we observed a divergence of the BP convergence time to the subdominant FP. Increasing further m some runs of BP converge to the dominant FP, others keep on wandering in a region of the message space that is far from the dominant FP, but that does not contain anymore a strict FP. This phenomenon could be interpreted as a spontaneous replica symmetry breaking of the sub-dominant FP. To fix the algorithm in such a way that it always converges to the dominant FP we adopted the following rule: stop BP after t max iterations and apply the tranformation in (221) to the current BP messages. Even if the BP messages did not corresponds to a true FP their transformation is actually close enough to the other FP to make the second BP run converge to the dominant FP with high probability (this trick worked for all the hundreds of samples we tried).

Finally we present in Fig. 17 a study of the unstable branch of fixed points of BP for the discontinuous case, m > m c , in the range θ sp < θ < θ KS . Similarly to what we did for the hypergraph bicoloring (cf. Fig. 14), well q 0 =1 q 0 =0.27 q 0 =0.268 q 0 =0.266 q 0 =0.264 q 0 =0.262 q 0 =0.26 q 0 =0.25 q 0 =0 q 0 =0 q 0 =q 0,c q 0 =1 FIG. 17: The left panel illustrates the way we estimate the value of ms for the unstable fixed point of BP (here θ = 0.492), that plays the role of separatrix for the BP dynamics. The right panel reports these values obtained in the coexistence region θsp < θ < θKS (here m = 0.8).

chosen parameters q 0 for the initial condition allow to identify the value of m s that plays the role of separatrix for the BP evolution (this value with its uncertainty is marked by a cyan strip in the inset). In the right panel of Figure 17 we report the data of the first sample already shown in the right panel of Figure 15 together with the values of m s measured at the unstable FP in the coexistence region θ sp < θ < θ KS .

VII. CONCLUSIONS

We have discussed in this paper the typology of phase transitions in inference problems, emphasizing in particular the possible existence of hybrid-hard phases; our main technical contribution is a rather generic expansion of the functional cavity equations for sparse models around their trivial fixed point. Let us briefly sketch some possible directions for future work. Some of our results could probably be proven rigorously without too much effort, in particular the techniques of [START_REF] Sly | Reconstruction for the Potts model[END_REF] combined with the higher order expansions we obtained should yield the non-tightness of the Kesten-Stigum bound for the reconstruction of the q = 4 anti-ferromagnetic Potts model on a tree with low enough degree (more directly than using the bound on the information theoretic threshold of [START_REF] Abbe | Detection in the stochastic block model with multiple clusters: proof of the achievability conjectures, acyclic BP, and the information-computation gap[END_REF]).

We performed our expansions assuming either pairwise interactions between arbitrary discrete spins, or k-wise interactions between binary valued variables; one could relax this assumption and consider k-wise interactions between q-valued variables, as was done in [START_REF] Coja-Oghlan | Charting the replica symmetric phase[END_REF] (but truncating the expansion to a low order).

We believe the q 1 + q 2 SBM we introduced would deserve a further investigation; we argued that its phase diagram must contain some hybrid-hard phases, but probably in a narrow range of parameters. As a first step the large degree limit of this model could be studied, the corresponding dense model also exhibits this hybrid-hard phenomenon while being much easier to study, with evolution equations bearing on covariance matrices of Gaussian random variables instead of probability distributions.

Let us consider a fixed point solution P (η) of the recursion equation [START_REF] De Almeida | Stability of the Sherrington-Kirkpatrick Solution of a Spin-Glass Model[END_REF], and look for a hierarchy of equations between its centered moments. As in the main text we denote δ σ = η ση σ the centered random variable with distribution P , and δ σ = σ M σσ δ σ a linearly transformed version of δ. Denoting E[•] the average with respect to P we have by definition E[δ σ ] = 0, and we assume E[δ σ δ σ ] to be non-zero but small, of an order denoted κ. From the self-consistent equation [START_REF] De Almeida | Stability of the Sherrington-Kirkpatrick Solution of a Spin-Glass Model[END_REF] on P and the expression (51) of the function f we can write the p-th centered moment of P (p ≥ 2 is understood below) as:

E[δ σ1 . . . δ σp ] = E z σ1 z -η σ1 • • • z σp z -η σp z , (B1)
where on the right hand side z σ = η σ i=1 (1 + δ i σ ), z = γ z γ , is drawn from p and for i = 1, . . . , the δ i are linearly transformed (according to [START_REF] Evans | Broadcasting on trees and the Ising model[END_REF]) versions of η i 's i.i.d. samples drawn from P (η). To simplify this expression we introduce the notation ε σ = i=1 (1 + δ i σ ) -1, in such a way that z σ = η σ (1 + ε σ ) and z = 1 + γ η γ ε γ . The previous equation thus becomes

FIG. 1 :

 1 FIG.1: Top: The "standard" scenarios in terms of the Bayes-optimal (a * , in blue) and algorithmic (a alg , in red) performance. Bottom: The "standard" scenarios in terms of the fixed points of eq. (6). Stable fixed points are in full line, unstable ones are dashed. In all panels the accuracy a is plotted as a function of the signal-to-noise ratio c. The thresholds csp, cIT, cKS and c alg , as defined in the text, are marked on the horizontal axes.

  is now the disappearance of an unstable non-trivial fixed point (instead of the appearance of a stable non-trivial fixed point for a continuous phase transition). There thus exists an interval of SNR, c ∈ [c sp , c KS ], where two stable fixed points coexist (the trivial one a = 0 and a non-trivial one). A bifurcation occurs at the spinodal transition c sp , where the high-accuracy branch appears discontinuously. The consequences of this bifurcation diagram on the optimal and algorithmic accuracies a * (c) and a alg (c) are presented in the upper right panel of Fig.1; the latter is only affected by the change of stability of the trivial fixed point at c KS , above which it jumps to the only stable fixed point which must thus coincide with the optimal accuracy a * (c). In the interval c ∈ [c sp , c KS ] the two stable fixed points correspond to two local minima of the free-energy f (a, c); their values cross each other at the information-theoretic phase transition c IT ∈ [c sp , c KS ], the trivial (resp. non-trivial) fixed point being the global minimum for c ∈ [c sp , c IT ] (resp. for c ∈ [c IT , c KS ]

FIG. 2 :

 2 FIG. 2: Top:The "new" scenarios in terms of the Bayes-optimal (a * , in blue) and algorithmic (a alg , in red) performance. Bottom: The "new" scenarios in terms of the fixed points of eq. (6). Stable fixed points are in full line, unstable one are dashed. In all panels the accuracy a is plotted as a function of the signal-to-noise ratio c. The thresholds csp, cIT, cKS and c alg , as defined in the text, are marked on the x-axes. The KS threshold cKS here is strictly smaller than the algorithmic one c alg . We note that the thresholds can also be ordered as csp < cKS < cIT < c alg .

Fig. 1 )FIG. 3 :

 13 FIG.3:The phase diagram of the 4 groups disassortative symmetric SBM (equivalently the reconstruction of antiferromagnetic q = 4 Potts model on Poissonian Galton-Watson trees), as a function of the average degree d. On the left panel the spinodal and IT transitions (see the text and Fig.1for their definitions) are plotted in terms of the signal-to-noise parameter dθ 2 , which equals 1 at the Kesten-Stigum transition (horizontal dashed line). On the right panel the same data is drawn in rescaled units to better appreciate the crossover from 1st to 2nd order transition as d increases; the vertical line marks our analytical prediction for dc ≈ 22.2694, the other line is only here as a guide to the eye.

FIG. 4 :

 4 FIG.4:The phase diagram of the ferromagnetic (θ > 0) asymmetric Ising model on a regular tree with offspring degree distribution p = δ ,d , d = 3. The magnetization parameter m encodes the size of the smaller community, in the SBM interpretation, as (1 -m)/2. On the left panel the spinodal and IT transitions are plotted in terms of the signal-to-noise parameter dθ 2 , which equals 1 at the Kesten-Stigum transition (horizontal dashed line). Within our numerical accuracy we cannot distinguish the spinodal and IT points for m smaller than 0.8, we used a single symbol in this case. The two lines corresponds to the large degree limit, as computed for the dense models in[START_REF] Lesieur | Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications[END_REF][START_REF] Barbier | Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula[END_REF][START_REF] Caltagirone | Recovering asymmetric communities in the stochastic block model[END_REF]. On the right panel the same data is drawn in rescaled units to better appreciate the crossover from 1st to 2nd order transition as m reaches its critical value mc = 1/ √ 3 ≈ 0.577, marked as a vertical line. The two straight lines are the analytical predictions of Eqs. (131,134) for the leading order behavior of the spinodal and IT transitions as m → m + c , for the sparse case p = δ ,3 .

  FIG.6: Stable fixed points of the cavity equations in terms of their accuracies for the planted bicoloring of k-uniform hypergraphs, with k = 3, 4, 5 from left to right. The accuracy is defined here as the difference between the probability that a sample from the posterior marginal outputs the correct label and the same probability when only the prior is used, see Sec. IV K for more details. The vertical line marks the KS threshold. These curves have been obtained by a numerical resolution of the cavity equations[START_REF] Barthel | Hiding Solutions in Random Satisfiability Problems: A Statistical Mechanics Approach[END_REF][START_REF] Lesieur | Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications[END_REF], a inf corresponds to the fixed point reached from an informative initialization (corresponding to the reconstruction problem, ε = 1 in Eq. (30)), a alg was obtained from an uninformative initialization (corresponding to the robust reconstruction problem, ε → 0 in Eq. (30)). The parameter α controls the offspring degree distribution p , which is a Poisson law of average αk. The optimal accuracy a * coincides with a inf above the IT transition, whose location can be found in TableI.

Fig. 2 .

 2 Fig. 2.As an illustrating example we present in Fig.6the bifurcation diagrams for the planted k-uniform hypergraph bicoloring, as defined in Sec. III A 2, in which each hyperedge forbids the k variables around it to be all in the same state. The random version of this Constraint Satisfaction Problem has been studied in some details (see for instance[START_REF] Gabrié | Phase transitions in the q-coloring of random hypergraphs[END_REF] and references therein), but we are not aware of previous studies of its planted version for small values of k. The plots of Fig.6show that for k = 3 the transition is second order, while k = 4 and k = 5 realizes the two scenarios sketched in the left and right panel of Fig.2, respectively, and whose interpretation was discussed in general terms in Sec. II C. In these latter two cases the hybrid-hard phase occupies a sizeable part of the phase diagram and can be easily identified numerically; we expect all k ≥ 5 to behave qualitatively in the same way, and checked this for k = 6. We report in TableIthe corresponding values of the thresholds α KS for the Kesten-Stigum transition, α sp and α alg for the spinodals of the high and low accuracy branches, respectively, and α IT , corresponding to the crossings of the free-entropies of these two fixed-points (the corresponding numerical data will be shown in Sec. V).As far as we know the hybrid-hard phase in which Belief Propagation is able to reach a non-trivial accuracy, yet cannot reach the optimal one, was never identified previously in sparse inference problems that have an undetectable phase. This can sound surprising in view of our statement above: hybrid-hard phases do appear as soon as the phase diagram is not a purely second order transition. The resolution of this apparent paradox is that the hybrid-hard phase is often very narrow: for instance the so-called 2-in-4 planted SAT problem was reported, wrongly, to have a first order transition in[START_REF] Zdeborová | Quiet planting in the locked constraint satisfaction problems[END_REF][START_REF] Angelini | Spectral detection on sparse hypergraphs[END_REF]. As we show in Sec. V the hybrid-hard phase does exist in this model, but its width is so tiny that it was easily missed in previous numerical studies.

FIG. 7 :

 7 FIG. 7: The value of a in the fixed-point solution of the cavity equations reached from an informative initial condition, as a function of the signal-to-noise ratio, for the ferromagnetic (θ > 0) asymmetric Ising model. We used a regular degree distribution, p = δ ,d with d = 3, each point correspond to a different value of θ > 0. The two set of symbols correspond to m = 0.4 < mc and m = 0.7 > mc. The vertical dashed line indicates the location of the Kesten-Stigum transition, while the inclined line is our analytical prediction from (116) for m = 0.4.

FIG. 8 :

 8 FIG.8: Study of the scaling regime in the neighborhood of the point (θKS, mc) for the ferromagnetic asymmetric Ising model with degree distribution p = δ ,d , d = 3. The rescaled signal-to-noise ratio parameter is t = (dθ 2 -1)/(m -mc) 2 , the Kesten-Stigum transition thus corresponds to t = 0. Left panel: the rescaled accuracy a = a/(m -mc) as a function of t; the lines are the analytic predictions for the stable (solid) and unstable (dashed) branches of fixed-points obtained in Eq. (128), the symbols are numerical results that approach the analytic line when m → m + c . Right panel: the rescaled free-entropy φ = φ/(m -mc) 4 as a function of t; the analytic lines have been obtained by inserting in (132) the two branches of a from (128), the threshold tIT corresponds to the crossing with the horizontal line φ = 0.

  + , P + ) = -E[ ] dP + (m)d P + (u) ln z e (m, u) + E[ ] k σ1,...,σ k p j (σ 1 , . . . , σ k ) dP + (m 1 ) . . . dP + (m k ) ln z c (σ 1 m 1 , . . . , σ k m k ) + ∞ =1 p d P + (u 1 ) . . . d P + (u ) ln z v (u 1 , . . . , u ) ,

  )]((k -1)γ 2 2 a) 2 + O(κ 3 ) (182) Denoting E[ ](k -1)γ 2 2 = 1 + , with parametrizing the distance to the Kesten-Stigum transition, dividing the equation by a, and taking = 0 in the correction term gives 0

2 FIG. 9 :

 29 FIG.9:The complexity Σ = -φ for the fixed point solutions of the cavity equations for the hypergraph bicoloring problem, for k = 3, 4, 5 from left to right; the symbols are the same as in Fig.6, crosses correspond to an informative initial condition, circles to an uninformative one.

  i→a | < 10 -8 . At a fixed point {η i→a , η a→i } of the BP equations, the local magnetizations are given by

N

  edges among variables in the first group, M 22 = edges among variables in the second group and M 12 = N 1 N 2 c+-N edges joining variables in different groups, where

FIG. 12 :

 12 FIG.12: Comparison between different order parameters detecting the planted configuration. Data have been averaged over the samples where BP reached a fixed point. As in Figure10, filled (resp. empty) points correspond to q0 = 0 (resp. q0 = 1).

FIG. 15 :

 15 FIG. 15: Comparison between BP and population dynamics in detecting the planted configuration in the asymmetric SBM with d = 4. For each θ value we have simulated 3 samples of size N = 10 7 . The asymmetry is m = 0.4 < mc in the left panel and m = 0.8 > mc in the right panel. In both cases the planted configuration can be detected purely from the graph (q0 = 0) for θ > θKS. Despite visible sample-to-sample fluctuations the prediction by population dynamics is always very faithful.

FIG. 16 :

 16 FIG.16: Different fixed points reached by BP run with a non-informative initial condition on samples of the asymmetric SBM (d = 4, m = 0.4, N = 10 7 ). Red full points refer to the dominating fixed point having the largest log(Z), while blue empty points refer to the sub-dominating fixed point.

E(- 1 )(- 1 )(- 1 )

 111 [δ σ1 . . . δ σp ] = η σ1 . . . η σp E[(ε σ1 -γ1 η γ1 ε γ1 ) . . . (ε σpγp η γp ε γp )(1 + γ η γ ε γ ) 1-p ] (B2) = η σ1 . . . η σp ∞ m=0 1p m γ1,...,γp+m (δ σ1,γ1η γ1 ) . . . (δ σp,γpη γp )η γp+1 . . . η γp+m E[ε γ1 . . . ε γp+m ] ,where the binomial coefficient with negative argument takes its conventional value 1-p m = (-1) m p-2+m m . In order to close these equations we should now express the average of products of ε's in terms of centered moments of P . As an intermediate step let us further defineµ σ = ε σ + 1 = i=1 (1 + δ i σ ); exploiting the independence of the random variables η i for distinct i one can easily compute the average of products of µ's,E[µ σ1 . . . µ σp ] =where S is summed over subsets of {1, . . . , p} of cardinality |S| ≥ 2 (because of the property E[ δ σ ] = 0). Expanding the last power we rewrite this as E[µ σ1 . . . µ σp ] = 1 + S satisfy the same properties as above, and the average denoted E is over drawn with probability p , the requirement ≥ r being kept understood. We can now come back to the computation of the average of products of ε's, noting thatE[ε σ1 . . . ε σp ] = E[(µ σ1 -1) . . . (µ σp -1)] = T (-1) p-|T | Ewhere T runs over all subsets of {1, . . . , p}. Before proceeding let us recall the following version of the inclusionexclusion principle: if E is an arbitrary finite set, T runs over all the subsets of E, and F is a subset of E, thenT ⊂E |E|-|T | I(F ⊂ T ) = (1 -1) |E|-|F | = I(F = E) ,(B6)which can be easily proven by enumerating the number of subsets T that contains F and that are contained in E.Consider now an arbitrary function g(S) of the subsets of E, and an integer r; as a consequence of the above identity we have T ⊂E |E|-|T | S1⊂T,...,Sr⊂T g(S 1 ) . . . g(S r ) = S1⊂E,...,Sr⊂E g(S 1 ) . . . g(S r ) T ⊂E |E|-|T | I(S 1 ⊂ T ) . . . I(S r ⊂ T ) = S1⊂E,...,Sr⊂E g(S 1 ) . . . g(S r )I(S 1 ∪ • • • ∪ S r = E) . (B7)

TABLE I :

 I Thresholds for the bicoloring on Poissonian random hyper-graphs, see the text and Fig.2for their definitions.

	αKS αsp	αIT α alg
	3 1.5	-	-	-
	4 4.083 4.64 4.673 4.71
	5 11.25 9.46 10.296 12.44
	6 32.03 18.08 21.425 34.5

  Search for the unstable fixed point of BP in the range [αsp, α alg ]. In the left panel, lowermost (resp. uppermost) curves have been obtained with q0 = 0 (resp. q0 = 1); the rest of the curves for α = 4.68 have been obtained varying q0 by ∆q0 = 0.01 in the range [0.2, 0.29] and by ∆q0 = 0.002 in the range [0.26, 0.27].

		1		α=4.72 α=4.68 α=4.64		0.9 0.8 0.7		stable FP unstable FP		K=4
		0.8				0.6		pop dyn
	m s	0.6			m s	0.4 0.5
		0.4				0.3
		0.2	q 0			0.2	α KS					α sp	α alg
						0.1
		0				0
		1	10	100	1000		4.1	4.2	4.3	4.4	4.5	4.6	4.7	4.8	4.9	5
			t								α
	FIG. 14:

Acknowledgment

We would like to thank Andrea Montanari for discussions about the asymmetric SBM with 2 communities, Amin Coja-Oghlan for useful discussions, in particular about [25], and Florent Krzakala for discussions about bifurcation phase diagrams.

LZ acknowledges funding from the European Research Council (ERC) under the European Unions Horizon 2020 research and innovation programme (grant agreement No 714608 -SMiLe). GS is part of the PAIL grant of the French Agence Nationale de la Recherche, ANR-17-CE23-0023-01.

where here and in the following ∝ denotes proportionality up to a constant independent of the spin variables. Indeed the prior is given by

while the likelihood is proportional to

where c is the affinity matrix with which the edges have been generated. We have approximated the product over the non-edges (i.e. pairs of vertices not connected by an edge) with a sum over all pairs of variables, the difference being a correction of order O(1/N ) in the large N limit. The following algebraic relation that holds for σ, τ ∈ {-1, 1}

∝ e Jστ -K(σ+τ ) with (202)

allows to rewrite the first term of the likelihood in exponential form exp

The second term of the likelihood (the one given by all the edges, including those absent from the graph) provides a term proportional to exp

So the posterior distribution that we have to study is given by the following expression

that corresponds to an Ising model with local fields and couplings given by

The corresponding BP equations are very well known

Unfortunately these BP equations involve N (N -1) messages u i→j with i = j (we assume u i→i = 0) and we need to simplify the if we want BP to run in a time linear in the system size. The main observation to achieve such a simplification is that BP messages running along the non-edges, i.e. sent between vertices not connected in E, are O(1/N ) and thus very small. The following equations hold up to terms of order O(1/N ) if (ij) / ∈ E:

where the first equality comes from J ij being O(1/N ), while the second one from ignoring u j→i ∼ O(1/N ) in the definition of local magnetization

Eliminating BP messages on non-edges via the substitution u i→j = -dθm i /((1m 2 )N ) we end up working only with the O(N ) BP messages running on the edges in E. These are updated according to the following iterative equations

where ∂i = {j : (ij) ∈ E} and we have redefined the local fields including also the effect of the non-edges

The local magnetizations are defined via

We solve equations (213) starting from a set of BP messages strongly biased towards a configuration τ 0 , that is u

i , where L is a large number (we fix L = 100 in our simulations, but the results are independent on L). Again we call q 0 the similarity between the starting configuration and the planted one, that is the components of τ 0 are independent random variables distributed according to

BP messages are updated in a random order and convergence is determined by the condition

At the BP fixed point, the local magnetizations are given by

The parameters m s , m 2 and q defined in Eq. (197) signal again the detection of the planted configuration (for m = 0 the absolute value in the definition of m s is not strictly required, but keeping it is not an error). It is worth noticing that in this case the non-informative fixed point is characterized by the BP messages u i→j = K and by the order parameters m s = m 2 = m 2 and m 2 = m, due to the asymmetry in the model. With a little bit of algebra, the Bethe RS free-entropy can be simplified to the following form,

B. Results for random hypergraph bicoloring

We present results for k = 3, 4, 5 and system size N = 10 6 (some samples of size N = 10 5 are shown just for the scaling of the convergence time). Every time we present three plots in a row, the left one refers to k = 3, the central one to k = 4 and the right one to k = 5.

Appendix A: Numerical resolution of the cavity equations

Population dynamics algorithm

We shall give in this appendix some details on the numerical procedure we used to solve the cavity equations and produce the curves presented in the main part of the text. It has become customary to solve recursive distributional equations like [START_REF] Kschischang | Factor graphs and the sum-product algorithm[END_REF] by a population dynamics method [START_REF] Mézard | The Bethe lattice spin glass revisited[END_REF][START_REF] Abou-Chacra | A selfconsistent theory of localization[END_REF]. The main idea of this method is to a approximate a probability distribution, for instance P (n) τ , by the empirical distribution of a large number N 1 of representants of P (n) τ , namely

where the η (n,τ,i) are i.i.d. samples from P

(n)

τ . The iterative equation ( 33) is then translated into a rule to generate the representative elements (i.e. the population) at iteration n + 1 from the one at iteration n, as follows. For each of the τ and independently for i = 1, . . . , N :

Average values over the conditional distributions P (n) τ or over the unconditional distribution P (n) are then evaluated as empirical averages over the population: for an arbitrary function f one computes

This approach is very natural, simple to implement, and becomes exact in the limit N → ∞. Unfortunately it suffers in many cases from an instability problem at finite N that requires additional care. In order to explain the origin of this difficulty we recall that the unconditional distribution must obey, for all iterations n, the condition E (n) [η] = η. A consequence of this identity and of the Bayes theorem as stated in [START_REF] Sly | Reconstruction for the Potts model[END_REF] is that, for all τ , the conditional distributions should obey

The elements of the population at iteration n + 1 should thus be such that

If the condition E (n) [η] = η is verified exactly then it will also be the case at iteration n + 1; however, when N is finite there are necessarily some small fluctuations around this value, that turn out to be amplified under the iteration whenever E[ ]|θ 2 | > 1 (as in the expression of the KS transition, but without the square on the eigenvalue). In that case the implementation presented above is bound to fail because of this instability. Depending on the model there are different ways to treat this problem. If the problem has an explicit symmetry, like the permutation invariance for the symmetric q-state Potts model, or the up-down symmetry for the Ising models studied in Sec. V, this can be exploited to tame the instability (see below for more details on the practical implementation).

The most difficult cases arise when there is no explicit symmetry to use, for instance for the asymmetric Ising model studied in Sec. IV I with m = 0. In such a case one needs to compute, at each iteration, the left hand side of (A4) from the newly generated elements, and if this average is not equal to 1 apply some transformation rules on the population samples in order to bring it closer to this target value. There are still many ways to implement this idea, we will be more explicit below for the asymmetric Ising case.

Symmetric problems

As mentioned above the population dynamics algorithm can be simplified and stabilized when the problem to solve exhibit some additional symmetries. Consider for instance the symmetric Potts model with q states, as defined in Sec. IV H. The invariance under any permutation π of the q states imply that P (n) (η) = P (n) (η • π), where (η • π) σ = η π(σ) is the probability measure on χ obtained from η by the reshuffling π of the q states. This observation allows to express all conditional distributions P τ in terms of a single one, for instance τ = 1, and close the iteration equation on P 1 as

where the π's are permutations on q colors, ρ is a probability distribution on them, such that with probability 1 q + θ 1 -1 q the permutation π is uniform under the condition π(1) = 1, otherwise it is uniform under the condition π(1) = 1. This equation is much simpler than the generic one, as it involves only one population instead of q, and also much more stable numerically.

Even simpler is the treatment of Ising spin models (q = 2) which are symmetric under the spin reversal operation, as for instance those studied in Sec. V. In that case the probability laws on χ are encoded by a single real m, the magnetization, and the conditional and unconditional distributions verify the identities m). This allows to close the cavity equation on a single population P (n) + (m), see in particular equations (168,169).

The asymmetric Ising model

Let us finally turn to the case of the asymmetric Ising model, defined in Sec. IV I. The general BP equation of Eq. ( 34) for η σ can be written as a scalar recursion by parametrizing η σ = 1+σm 2 . The BP equation reads in this parametrization m = f (m 1 , . . . , m ), with

One sees immediately that z σ (m, . . . , m) = 1+σm 2 , hence z(m, . . . , m) = 1 and m = f (m, . . . , m) is a fixed point, as it should.

The "naive" implementation of the population dynamics algorithm explained above corresponds to a representation of P (n) + (m) (resp. P (n) + (m)) by N reals m (n,+,i) (resp. m (n,-,i) ). In order to cure the instability and to enforce the condition (A4) at each iteration we have proceeded as follows: once the 2N magnetizations m (σ,i) have been generated according to the standard procedure (we remove the iteration index to lighten the notation) we compute

and replace the elements of the population by

One can check that this procedure strictly enforces the identity (A4), the coefficients β measuring the deviation of the naively generated population elements from the symmetry respecting probability distributions.

Appendix B: Moment expansion for pairwise interacting Potts variables

The goal of this appendix is to justify some of the statements made in Sec. IV D, in particular the ansatz (61) for the scaling of the centered moments of the perturbative non-trivial fixed point, and the third order expansion given in (71-73).

Inserting (B4) in (B5) and using this last form of the inclusion-exclusion principle yields finally

where we treated the term r = 1 separately as it is simpler than the general terms for r ≥ 2. In the latter the summation is over S 1 , . . . , S r subsets of {1, . . . , p} of cardinality |S i | ≥ 2 whose union must cover {1, . . . , p} (but they do not need to be disjoint). Each term in this sum can be associated to a diagram, i.e. an hypergraph on p vertices with r hyperedges that connect at least 2 vertices, in such a way that no vertex remains isolated. Furthermore, in (B2) some of the ε σ appears multiplied by η σ and summed over σ; in that case the only diagrams that contribute are those in which the corresponding vertex has degree at least 2, because of the property σ η σ δ σ = 0. The two expressions (B2) and (B8) form an infinite hierarchy of equations that, formally, determine all the centered moments of the possible distributions P (η) fixed point solutions of (37); as η is bounded these moments are enough to characterize P itself. The results presented in Sec. IV D have been obtained by truncating this hierarchy under the hypothesis that

where κ is a small parameter controlling the distance between the studied fixed point P (η) and the trivial one δ(η -η).

The self-consistency of this ansatz can be checked on (B2,B8); using the hypothesis on E[ε σ1 . . . ε σp ] in the right hand side of (B2) leads to a compatible scaling for E[δ σ1 . . . δ σp ], the dominant contribution coming from the term m = 0 if p is even, and from m = 0 and m = 1 if p is odd. Similarly one can insert the hypothesis on E[δ σ1 . . . δ σp ] in the right hand side of (B8); the first term corresponding to r = 1 is obviously compatible with the ansatz. The order in κ of the generic term with r ≥ 2 is

as the sets S 1 , . . . , S r have to cover {1, . . . , p}, hence these terms are not strictly dominant with respect to the case r = 1, which concludes our verification of the consistency of the ansatz. From (B2,B8) it is relatively easy to obtain the third order expansion stated in the main text in Eqs. (71-73), exploiting the ansatz to truncate the hierarchy of equations at the desired order in κ, and the diagrammatic representation of the terms in (B8) to organize their bookkeeping.

Appendix C: Expansion of the free-entropy for pairwise interacting Potts variables

We provide in this Appendix some details on the derivation of the expansion (77) for the free-entropy of pairwise interacting models. Let us start from the expression (40) that we rewrite in a more compact notation,

where the expressions of z v and z e are given in [START_REF] Kesten | Additional Limit Theorems for Indecomposable Multidimensional Galton-Watson Processes[END_REF] and ( 39) respectively.

To deal with the second term of φ we write z e = 1 + σ δ 1 σ δ 2 σ , where δ 1 σ = η 1 ση σ and δ 2 σ = σ M σσ (η 2 ση σ ) with η 1 and η 2 two independent samples from P (η). Using the power series expansion of (1 + x) ln(1 + x) around x = 0 gives

Neglecting the terms with p ≥ 5 yields the first line in (77).

In the first term we write z v = 1 + σ η σ ε σ , where the notation ε σ = i=1 (1 + δ i σ ) -1 is the same as in Appendix B, the only difference being that is now drawn from the distribution p instead of p . This yields

where the expression of E[ε σ1 . . . ε σp ] can be read off from (B8) with the modification p → p . Enumerating the various terms that contribute up to order κ 4 using the diagrammatic representation explained in Appendix B yields the remaining terms of (77). We factored out in these terms a common factor E[ ], using the identity E[ ( -1) . . . (r + 1)] = E[ ] E[ ( -1) . . . (r + 2)] (C4) that follows from the size bias between p and p expressed in [START_REF] Abbe | Conditional Random Fields, Planted Constraint Satisfaction and Entropy Concentration[END_REF]. Finally let us write down an expression that is equivalent to the expansion (77) but where the centered moments are expressed in the basis of eigenvectors of M :

A j1k1 A j2k2 A j3k3 A j4k4 θ j1 θ k1 θ j2 θ k2 θ j3 θ k3 θ j4 θ k4 h j1j2j3j4 k1k2k3k4 with the definitions of the tensors that encode the structure of the eigenvectors of M :

h j1j2j3j4 k1k2k3k4 = g j1j2j3j4 g k1k2k3k4 -6g j1j2j3j4 δ k1k2 δ k3k4 -12f j1j2j3 f k1k2j4 δ k3k4 + 3δ j1j2 δ k1k2 δ j3j4 δ k3k4 + 12δ k4j1 δ k1j2 δ k2j3 δ k3j4 (C8)