Partition Function Expansion on Region-Graphs and Message-Passing Equations

Abstract

Disordered and frustrated graphical systems are ubiquitous in physics, biology, and information science. For models on complete graphs or random graphs, deep understanding has been achieved through the mean-field replica and cavity methods. But finite-dimensional `real' systems persist to be very challenging because of the abundance of short loops and strong local correlations. A statistical mechanics theory is constructed in this paper for finite-dimensional models based on the mathematical framework of partition function expansion and the concept of region-graphs. Rigorous expressions for the free energy and grand free energy are derived. Message-passing equations on the region-graph, such as belief-propagation and survey-propagation, are also derived rigorously.

10 pages including two figures. New theoretical and numerical results added. Will be published by JSTAT as a letter

References in corpus (5)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Loop series for discrete statistical models on graphs
• Nonequilibrium spin glass dynamics from picoseconds to 0.1 seconds
• Partition function loop series for a general graphical model: free energy corrections and message-passing equations
• Replica Cluster Variational Method

Cited by in corpus (7)

• Spin glass approach to the feedback vertex set problem
• 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
• New Understanding of the Bethe Approximation and the Replica Method
• Quantum Cluster Variational Method and Message Passing Algorithms Revisited
• CCCP Algorithms to Minimize the Bethe free energy of 3-SAT Problem