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.

arXiv comment20 pages, 8 figures

References in corpus (25)

• The Bethe lattice spin glass revisited
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Statistical physics of inference: Thresholds and algorithms
• Zero-temperature Hysteresis in Random-field Ising Model on a Bethe Lattice
• On the optimality of tree-reweighted max-product message-passing
• Elusive Glassy Phase in the Random Field Ising Model
• The cavity method at zero temperature
• Exact Expressions for Minor Hysteresis Loops in the Random Field Ising Model on a Bethe Lattice at Zero Temperature
• Absence of replica symmetry breaking in the random field Ising model
• Finite size corrections to disordered Ising models on Random Regular Graphs
• Approximating the XY model on a random graph with a $q$-state clock model
• Finite size corrections to disordered systems on Erdös-Rényi random graphs
• Metastable states and T=0 hysteresis in the random-field Ising model on random graphs
• Exactness of Belief Propagation for Some Graphical Models with Loops
• No-passing Rule in the Ground State Evolution of the Random-Field Ising Model
• A universal form of slow dynamics in zero-temperature random-field Ising model
• The T=0 random-field Ising model on a Bethe lattice with large coordination number: hysteresis and metastable states
• Large Deviations of Correlation Functions in Random Magnets
• Zero Temperature Hysteresis in Random Field Ising Model on Bethe Lattices: approach to mean field behavior with increasing coordination number z
• Stable, metastable and unstable states in the mean-field RFIM at T=0
• Random-field p-spin glass model on regular random graphs
• Aging in the three-dimensional Random Field Ising Model
• Low-energy excitations in the three-dimensional random-field Ising model
• Exact spin-spin correlation function for the zero-temperature random-field Ising model
• Anomalous finite size corrections in random field models

Cited by in corpus (4)

• Two critical localization lengths in the Anderson transition on random graphs
• The random field XY model on sparse random graphs shows replica symmetry breaking and marginally stable ferromagnetism
• New loop expansion for the Random Magnetic Field Ising Ferromagnets at zero temperature
• The Ising spin glass on random graphs at zero temperature: not all spins are glassy in the glassy phase