Characterizing and Improving Generalized Belief Propagation Algorithms on the 2D Edwards-Anderson Model

Abstract

We study the performance of different message passing algorithms in the two dimensional Edwards Anderson model. We show that the standard Belief Propagation (BP) algorithm converges only at high temperature to a paramagnetic solution. Then, we test a Generalized Belief Propagation (GBP) algorithm, derived from a Cluster Variational Method (CVM) at the plaquette level. We compare its performance with BP and with other algorithms derived under the same approximation: Double Loop (DL) and a two-ways message passing algorithm (HAK). The plaquette-CVM approximation improves BP in at least three ways: the quality of the paramagnetic solution at high temperatures, a better estimate (lower) for the critical temperature, and the fact that the GBP message passing algorithm converges also to non paramagnetic solutions. The lack of convergence of the standard GBP message passing algorithm at low temperatures seems to be related to the implementation details and not to the appearance of long range order. In fact, we prove that a gauge invariance of the constrained CVM free energy can be exploited to derive a new message passing algorithm which converges at even lower temperatures. In all its region of convergence this new algorithm is faster than HAK and DL by some orders of magnitude.

19 pages, 13 figures

References in corpus (4)

• Identification of direct residue contacts in protein-protein interaction by message passing
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• Exact Algorithm for Sampling the 2D Ising Spin Glass

Cited by in corpus (12)

• The Bethe approximation for solving the inverse Ising problem: a comparison with other inference methods
• Region graph partition function expansion and approximate free energy landscapes: Theory and some numerical results
• Replica Cluster Variational Method: the Replica Symmetric solution for the 2D random bond Ising model
• Message passing and Monte Carlo algorithms: connecting fixed points with metastable states
• The Quantum Cluster Variational Method and the Phase Diagram of the quantum ferromagnetic $J_1$-$J_2$ model
• Simplifying Generalized Belief Propagation on Redundant Region Graphs
• Cycle-based Cluster Variational Method for Direct and Inverse Inference
• Quantum Cluster Variational Method and Message Passing Algorithms Revisited
• Statistical physics of loopy interactions: Independent-loop approximation and beyond
• On one-step replica symmetry breaking in the Edwards-Anderson spin glass model
• Improving variational methods via pairwise linear response identities
• Gauge-free cluster variational method by maximal messages and moment matching