Typology of phase transitions in Bayesian inference problems

Many inference problems undergo phase transitions as a function of the signal-to-noise ratio, a prominent example of this phenomenon being found in the stochastic block model (SBM) that generates a random graph with a hidden community structure. Some of these phase transitions affect the information-theoretic optimal (but possibly computationally expensive) estimation procedure, others concern the behavior of efficient iterative algorithms. A computational gap opens when the phase transitions for these two aspects do not coincide, leading to a hard phase in which optimal inference is computationally challenging. In this paper we refine this description in two ways. From a qualitative perspective, we emphasize the existence of more generic phase diagrams with a hybrid-hard phase, in which it is computationally easy to reach a nontrivial inference accuracy but computationally hard to match the information-theoretic optimal one. We support this discussion by quantitative expansions of the functional cavity equations that describe inference problems on sparse graphs, around their trivial solution. These expansions shed light on the existence of hybrid-hard phases, for a large class of planted constraint satisfaction problems, and on the question of the tightness of the Kesten-Stigum (KS) bound for the associated tree reconstruction problem. Our results show that the instability of the trivial fixed point is not generic evidence for the Bayes optimality of the message-passing algorithms. We clarify in particular the status of the symmetric SBM with four communities and of the tree reconstruction of the associated Potts model: In the assortative (ferromagnetic) case the KS bound is always tight, whereas in the disassortative (antiferromagnetic) case we exhibit an explicit criterion involving the degree distribution that separates a large-degree regime where the KS bound is tight and a low-degree regime where it is not. We also investigate the SBM with two communities of different sizes, also known as the asymmetric Ising model, and describe quantitatively its computational gap as a function of its asymmetry, as well as a version of the SBM with two groups of $q_1$ and $q_2$ communities. We complement this study with numerical simulations of the belief propagation iterative algorithm, confirming that its behavior on large samples is well described by the cavity method.

Figure 1

Two “standard” scenarios with either (a) and (c) a second-order (continuous) transition or (b) and (d) a first-order (discontinuous) transition for (a) and (b) the Bayes-optimal ($a^{*}$, in blue) and algorithmic ($a_{\mathrm{alg}}$, in red) performance and (c) and (d) the fixed points of Eq. (6), with solid (dashed) lines for stable (unstable) fixed points. In all panels the vertical axis is the accuracy $a$ and the horizontal axis is the signal-to-noise ratio $c$. The thresholds $c_{\mathrm{sp}}, c_{\mathrm{IT}}, c_{\mathrm{KS}}$, and $c_{\mathrm{alg}}$, as defined in the text, are marked on the horizontal axes.

Figure 2

Two “new” scenarios of phase transitions for inference problems, one in (a) and (c) and one in (b) and (d) for (as in Fig. 1) (a) and (b) the Bayes-optimal ($a^{*}$, in blue) and algorithmic ($a_{\mathrm{alg}}$, in red) performance and (c) and (d) the fixed points of Eq. (6), with solid (dashed) lines for stable (unstable) fixed points. In all panels the accuracy $a$ is plotted as a function of the signal-to-noise ratio $c$. The thresholds $c_{\mathrm{sp}}, c_{\mathrm{IT}}, c_{\mathrm{KS}}$, and $c_{\mathrm{alg}}$, as defined in the text, are marked on the $x$ axes. The KS threshold $c_{\mathrm{KS}}$ here is strictly smaller than the algorithmic one $c_{\mathrm{alg}}$. We note that the thresholds can also be ordered as $c_{\mathrm{sp}}<c_{\mathrm{KS}}<c_{\mathrm{IT}}<c_{\mathrm{alg}}$; in terms of $a^{*}$ and $a_{\mathrm{alg}}$ this still corresponds to the behavior shown in (a).

Figure 3

Phase diagram of the four-group disassortative symmetric SBM (equivalently the reconstruction of the antiferromagnetic $q=4$ Potts model on Poissonian Galton-Watson trees), as a function of the average degree $d$. (a) The spinodal and IT transitions (see the text and Fig. 1 for their definitions) are plotted in terms of the signal-to-noise parameter $d{\theta }^2$, which equals 1 at the Kesten-Stigum transition (horizontal dashed line). (b) Same data as in (a) drawn with a change of variable on the vertical axis to better appreciate the crossover from the first- to the second-order transition as $d$ reaches $d_{\mathrm{c}}$; as explained in the text and with more details in Sec. 4h, we expect the curves in (b) to vanish linearly when $d\to d_{\mathrm{c}}^{-}$. The vertical line marks our analytical prediction for $d_{\mathrm{c}}\approx 22.2694$; the other line is only a guide to the eye.

Figure 4

Phase diagram of the ferromagnetic ($\theta >0$) asymmetric Ising model on a regular tree with offspring degree distribution ${\tilde{p}}_{\ell }={\delta }_{\ell ,d}, d=3$. The magnetization parameter $\overline{m}$ encodes the size of the smaller community, in the SBM interpretation, as $(1-\overline{m})/2$. (a) The spinodal and IT transitions are plotted in terms of the signal-to-noise parameter $d{\theta }^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 $\overline{m}$ smaller than 0.8; we use a single symbol in this case. The two lines correspond to the large-degree limit, as computed for the dense models in Refs. [16, 26, 27]. (b) Same data as in (a) drawn in rescaled units to better appreciate the crossover from the first- to the second-order transition as $\overline{m}$ reaches its critical value ${\overline{m}}_{\mathrm{c}}=1/\sqrt{3}\approx 0.577$, marked as a vertical line. The two straight lines are the analytical predictions of Eqs. (130) and (133) for the leading-order behavior of the spinodal and IT transitions as $\overline{m}\to {\overline{m}}_{\mathrm{c}}^{+}$, for the sparse case ${\tilde{p}}_{\ell }={\delta }_{\ell ,3}$.

Figure 5

Shape of the connectivity matrix in the $q_1+q_2$ Potts model. Matrix elements filled with the same pattern are equal.

Figure 6

Stable fixed points of the cavity equations in terms of their accuracies for the planted bicoloring of $k$-uniform hypergraphs for (a) $k=3$, (b) $k=4$, and (c) $k=5$. 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. 4k for more details). The vertical line marks the KS threshold. These curves have been obtained by a numerical resolution of the cavity equations (15) and (16), $a_{\inf }$ corresponds to the fixed point reached from an informative initialization [corresponding to the reconstruction problem, $\varepsilon =1$ in Eq. (30)], and $a_{\mathrm{alg}}$ was obtained from an uninformative initialization [corresponding to the robust reconstruction problem, $\varepsilon \to 0$ in Eq. (30)]. The parameter $\alpha$ controls the offspring degree distribution ${\tilde{p}}_{\ell }$, which is a Poisson law of average $\alpha k$. The optimal accuracy $a^{*}$ coincides with $a_{\inf }$ above the IT transition, whose location can be found in Table 1.

Figure 7

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 ($\theta >0$) asymmetric Ising model. We used a regular degree distribution ${\tilde{p}}_{\ell }={\delta }_{\ell ,d}$ with $d=3$, each point corresponding to a different value of $\theta >0$. The two sets of symbols correspond to $\overline{m}=0.4<{\overline{m}}_{\mathrm{c}}$ and $\overline{m}=0.7>{\overline{m}}_{\mathrm{c}}$. The vertical dashed line indicates the location of the Kesten-Stigum transition, while the inclined line is our analytical prediction from (115) for $\overline{m}=0.4$.

Figure 8

Study of the scaling regime in the neighborhood of the point $({\theta }_{\mathrm{KS}},{\overline{m}}_{\mathrm{c}})$ for the ferromagnetic asymmetric Ising model with degree distribution ${\tilde{p}}_{\ell }={\delta }_{\ell ,d}, d=3$. The rescaled signal-to-noise ratio parameter is $t=(d{\theta }^2-1)/{(\overline{m}-{\overline{m}}_{\mathrm{c}})}^2$; the Kesten-Stigum transition thus corresponds to $t=0$. (a) Rescaled accuracy $\tilde{a}=a/(\overline{m}-{\overline{m}}_{\mathrm{c}})$ 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. (127) and the symbols are numerical results that approach the analytic line when $\overline{m}\to {\overline{m}}_{\mathrm{c}}^{+}$. (b) Rescaled free entropy $\tilde{\varphi }=\varphi /{(\overline{m}-{\overline{m}}_{\mathrm{c}})}^4$ as a function of $t$. The analytic lines have been obtained by inserting in Eq. (131) the two branches of $\tilde{a}$ from (127); the threshold $t_{\mathrm{IT}}$ corresponds to the crossing with the horizontal line $\tilde{\varphi }=0$.

Figure 9

Complexity $\mathrm{\Sigma }=-\varphi$ for the fixed-point solutions of the cavity equations for the hypergraph bicoloring problem for (a) $k=3$, (b) $k=4$, and (c) $k=5$. The symbols are the same as in Fig. 6; pluses correspond to an informative initial condition and circles to an uninformative one.

Figure 10

Order parameter $m_s$ detecting the planted configuration for (a) $k=3$, (b) $k=4$, and (c) $k=5$, obtained by running BP on three samples of size $N={10}^6$ for each value of $\alpha$. The lines are the predictions obtained by solving the cavity equations for the reconstruction problem on a tree (plotted also in Fig. 6), with the correspondence $m_s=2a$ explained in the text.

Figure 11

Times to meet the BP convergence criterion (i.e., any marginal must change by less than ${10}^{-8}$) for (a) $k=3$ and (b) $k=5$, two system sizes ($N={10}^5,{10}^6$), and two different initial conditions ($q_0=0,1$). A data point with a time ${10}^4$ means BP did not reach convergence.

Figure 12

Comparison between different order parameters detecting the planted configuration for (a) $k=3$, (b) $k=4$, and (c) $k=5$. Data have been averaged over the samples where BP reached a fixed point. As in Fig. 10, closed (open) points correspond to $q_0=0$ ($q_0=1$).

Figure 13

Bethe RS entropy computed at the BP fixed points for (a) $k=3$, (b) $k=4$, and (c) $k=5$. (d)–(f) The difference with respect to the paramagnetic entropy is shown 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.

Figure 14

Search for the unstable fixed point of BP in the range $[{\alpha }_{\mathrm{sp}},{\alpha }_{\mathrm{alg}}]$. In (a) the lowermost (uppermost) curves have been obtained with $q_0=0$ ($q_0=1$); the rest of the curves for $\alpha =4.68$ have been obtained varying $q_0$ by $\mathrm{\Delta }{q}_0=0.01$ in the range [0.2,0.29] and by $\mathrm{\Delta }{q}_0=0.002$ in the range [0.26,0.27]. (b) The value of $m_s$ at the various fixed points as a function of $\alpha$.

Figure 15

Comparison between BP and population dynamics in detecting the planted configuration in the asymmetric SBM with $d=4$. For each $\theta$ value we have simulated three samples of size $N={10}^7$. The asymmetry is (a) $\overline{m}=0.4<{\overline{m}}_{\mathrm{c}}$ and (b) $\overline{m}=0.8>{\overline{m}}_{\mathrm{c}}$. In both cases the planted configuration can be detected purely from the graph ($q_0=0$) for $\theta >{\theta }_{\mathrm{KS}}$. Despite visible sample-to-sample fluctuations, the prediction by population dynamics is always very faithful.

Figure 16

Different fixed points reached by BP run with an uninformative initial condition on samples of the asymmetric SBM ($d=4, \overline{m}=0.4$, and $N={10}^7$). Red closed circles represent the dominating fixed point having the largest $ln\left(Z\right)$, while blue open circles represent the subdominating fixed point. (a)–(f) Several observables, indicated on the axis, are displayed for the two fixed points as a function of $\theta$.

Figure 17

(a) Illustration of the way we estimate the value of $m_s$ for the unstable fixed point of BP (here $\theta =0.492$), which plays the role of separatrix for the BP dynamics. (b) This value of $m_s$ obtained in the coexistence region ${\theta }_{\mathrm{sp}}<\theta <{\theta }_{\mathrm{KS}}$ (here $\overline{m}=0.8$).