An improved Belief Propagation algorithm finds many Bethe states in the random field Ising model on random graphs

Abstract

We first present an empirical study of the Belief Propagation (BP) algorithm, when run on the random field Ising model defined on random regular graphs in the zero temperature limit. We introduce the notion of maximal solutions for the BP equations and we use them to fix a fraction of spins in their ground state configuration. At the phase transition point the fraction of unconstrained spins percolates and their number diverges with the system size. This in turn makes the associated optimization problem highly non trivial in the critical region. Using the bounds on the BP messages provided by the maximal solutions we design a new and very easy to implement BP scheme which is able to output a large number of stable fixed points. On one side this new algorithm is able to provide the minimum energy configuration with high probability in a competitive time. On the other side we found that the number of fixed points of the BP algorithm grows with the system size in the critical region. This unexpected feature poses new relevant questions on the physics of this class of models.

20 pages, 8 figures

References in corpus (11)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• On the optimality of tree-reweighted max-product message-passing
• The cavity method at zero temperature
• Absence of replica symmetry breaking in the random field Ising model
• Approximating the XY model on a random graph with a $q$-state clock model
• Exactness of Belief Propagation for Some Graphical Models with Loops
• No-passing Rule in the Ground State Evolution of the Random-Field Ising Model
• The T=0 random-field Ising model on a Bethe lattice with large coordination number: hysteresis and metastable states
• Stable, metastable and unstable states in the mean-field RFIM at T=0
• Random-field p-spin glass model on regular random graphs
• Anomalous finite size corrections in random field models

Cited by in corpus (1)

• The Ising spin glass on random graphs at zero temperature: not all spins are glassy in the glassy phase