Region graph partition function expansion and approximate free energy landscapes: Theory and some numerical results

Abstract

Graphical models for finite-dimensional spin glasses and real-world combinatorial optimization and satisfaction problems usually have an abundant number of short loops. The cluster variation method and its extension, the region graph method, are theoretical approaches for treating the complicated short-loop-induced local correlations. For graphical models represented by non-redundant or redundant region graphs, approximate free energy landscapes are constructed in this paper through the mathematical framework of region graph partition function expansion. Several free energy functionals are obtained, each of which use a set of probability distribution functions or functionals as order parameters. These probability distribution function/functionals are required to satisfy the region graph belief-propagation equation or the region graph survey-propagation equation to ensure vanishing correction contributions of region subgraphs with dangling edges. As a simple application of the general theory, we perform region graph belief-propagation simulations on the square-lattice ferromagnetic Ising model and the Edwards-Anderson model. Considerable improvements over the conventional Bethe-Peierls approximation are achieved. Collective domains of different sizes in the disordered and frustrated square lattice are identified by the message-passing procedure. Such collective domains and the frustrations among them are responsible for the low-temperature glass-like dynamical behaviors of the system.

30 pages, 11 figures. More discussion on redundant region graphs. To be published by Journal of Statistical Physics

References in corpus (9)

• Identification of direct residue contacts in protein-protein interaction by message passing
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Loop series for discrete statistical models on graphs
• Mean Field Theory For Non-Equilibrium Network Reconstruction
• Zero and low temperature behavior of the two-dimensional $\pm J$ Ising spin glass
• Replica Cluster Variational Method: the Replica Symmetric solution for the 2D random bond Ising model
• Dynamics and Performance of Susceptibility Propagation on Synthetic Data
• On Cavity Approximations for Graphical Models
• Boltzmann distribution of free energies in a finite-connectivity spin-glass system and the cavity approach

Cited by in corpus (25)

• Spin glass approach to the feedback vertex set problem
• Statistical Mechanics of the Minimum Dominating Set Problem
• A Cavity Master Equation for the continuous time dynamics of discrete spins models
• The Directed Dominating Set Problem: Generalized Leaf Removal and Belief Propagation
• A mean field method with correlations determined by linear response
• Block belief propagation algorithm for two-dimensional tensor networks
• Statistical physics of hard combinatorial optimization: The vertex cover problem
• Off-Diagonal Series Expansion for Quantum Partition Functions
• Message passing and Monte Carlo algorithms: connecting fixed points with metastable states
• Simulating quantum dynamics in two-dimensional lattices with tensor network influence functional belief propagation
• Minimal Dominating Set problem studied by simulated annealing and cavity method: Analytics and population dynamics
• Optimal segmentation of directed graph and the minimum number of feedback arcs
• Kinked Entropy and Discontinuous Microcanonical Spontaneous Symmetry Breaking
• Generalized minimum dominating set and application in automatic text summarization
• Simplifying Generalized Belief Propagation on Redundant Region Graphs
• A spin glass approach to the directed feedback vertex set problem
• Loop-corrected belief propagation for lattice spin models
• Correcting beliefs in the mean-field and Bethe approximations using linear response
• Gauge-free cluster variational method by maximal messages and moment matching
• On one-step replica symmetry breaking in the Edwards-Anderson spin glass model
• Witness of unsatisfiability for a random 3-satisfiability formula
• Two-distance minimal dominating set problem studied by statistical mechanics and simulated annealing
• The Directed Dominating Set problem studied by cavity method: Warning propagation and population dynamics
• CCCP Algorithms to Minimize the Bethe free energy of 3-SAT Problem
• Statistical Mechanics of the L-Distance Minimal Dominating Set problem