The Bethe Partition Function of Log-supermodular Graphical Models
arXiv:1202.6035
Abstract
Sudderth, Wainwright, and Willsky have conjectured that the Bethe approximation corresponding to any fixed point of the belief propagation algorithm over an attractive, pairwise binary graphical model provides a lower bound on the true partition function. In this work, we resolve this conjecture in the affirmative by demonstrating that, for any graphical model with binary variables whose potential functions (not necessarily pairwise) are all log-supermodular, the Bethe partition function always lower bounds the true partition function. The proof of this result follows from a new variant of the "four functions" theorem that may be of independent interest.
Typo, bug fixes, and improved exposition
References in corpus (2)
Cited by in corpus (17)
- On the average size of independent sets in triangle-free graphs
- On Sampling from the Gibbs Distribution with Random Maximum A-Posteriori Perturbations
- Belief Propagation Neural Networks
- Extremes of the internal energy of the Potts model on cubic graphs
- Beyond Log-Supermodularity: Lower Bounds and the Bethe Partition Function
- Extremal regular graphs: the case of the infinite regular tree
- New Understanding of the Bethe Approximation and the Replica Method
- Bounding the Bethe and the Degree- Bethe Permanents
- Clamping Improves TRW and Mean Field Approximations
- Spectral Bounds for the Ising Ferromagnet on an Arbitrary Given Graph
- Sidorenko's conjecture, colorings and independent sets
- Concavity of reweighted Kikuchi approximation
- Fast Convergence of Belief Propagation to Global Optima: Beyond Correlation Decay
- The Bethe Free Energy Allows to Compute the Conditional Entropy of Graphical Code Instances. A Proof from the Polymer Expansion
- Lifted Hybrid Variational Inference
- Gauging Variational Inference
- On the free energy density of factor models on biregular graphs