Belief-propagation-guided Monte-Carlo sampling

A Monte-Carlo algorithm for discrete statistical models that combines the full power of the belief-propagation algorithm with the advantages of a heat-bath approach fulfilling the detailed balance is presented. First we extract randomly a subtree inside the interaction graph of the system. Second, given the boundary conditions, belief propagation is used as a perfect sampler to generate a configuration on the tree, and finally, the procedure is iterated. This approach is best adapted for locally treelike graphs and we therefore tested it on random graphs for hard models such as spin glasses, demonstrating its state-of-the art status in those cases.

Figure 1

A schematic illustration of the BP-guided MCMC on the coloring problem. Left: Starting from a random node $s_{\mathrm{INIT}}$ we create a random tree by adding the neighbors of each node in the tree progressively (but without creating a loop). The (plain) links in gray have been cut on the picture to emphasis the constructed tree structure. Middle: The tree nodes have been reset and marked by a red X on the figure. We illustrate by arrows how the BP messages propagate to compute the partial marginals until the central spin is reached. For the latter we can then compute the complete marginal. Right: The central node has been put in one state according its marginal $p^{\mathrm{central}}$. Propagating this information backward on the tree, this allows us to compute the complete marginal for each variable and to sample a new configuration for all the variables on the tree.

Figure 2

Energy density after a quench (using $e_{\mathrm{REF}}=c/2$ for the ferromagnet and $e_{\mathrm{REF}}=0$ for the antiferromagnet) starting from a random initial configuration for an Ising model on a large $(N={10}^6)$ regular random graph with connectivity $c=3$ at temperature $T=0.1$. Top panel: The convergence of the energy is shown versus the iteration time in the ferromagnetic case using different thresholds for the largest possible tree-cluster move on each curve. While standard Metropolis (1 spin) gets trapped in configurations with large energy for infinitely long time, increasing the size of the trees systematically increases the efficiency of the algorithm. With large enough trees, one equilibrates the system in less than 20 iterations. Bottom panel: A similar study for an antiferromagnet that behaves as a spin glass model due to the frustration. Similar performances to those in the ferromagnetic case are observed. Note that while the Wolff cluster approach is able to perfectly sample the ferromagnet, it fails in the spin glass case where the best performances are obtained by the BP-guided algorithm.

Figure 3

Autocorrelation $m\left(t\right)=C_{\mathrm{eq}}\left(t\right)$ for the $p$ spin on regular graph with $N={10}^5$ and $c=3$ starting from equilibrium. The temperatures go from $0.7\to 0.525$ and the dynamic glass transition arises at $T_d=0.510$ [24]. In the inset the melting time diverges as a power law. The BP-guided MCMC method is more than 10 times faster than the traditional one.

Figure 4

Simulated annealing starting from an equilibrated configuration at $T=0.12$ in a 4-coloring problem on a large $N={10}^5$ 9-regular random graph. The annealing is performed by decreasing the temperature by $\Delta T={10}^{-7}$ every ten time steps. While the traditional Metropolis approach is stuck at finite energy, our BP-guided algorithm shows no sign of such blocking and actually reaches the ground state.