Beyond Log-Supermodularity: Lower Bounds and the Bethe Partition Function

Abstract

A recent result has demonstrated that the Bethe partition function always lower bounds the true partition function of binary, log-supermodular graphical models. We demonstrate that these results can be extended to other interesting classes of graphical models that are not necessarily binary or log-supermodular: the ferromagnetic Potts model with a uniform external field and its generalizations and special classes of weighted graph homomorphism problems.

Appears in Proceedings of the Twenty-Ninth Conference on Uncertainty in Artificial Intelligence (UAI2013)

References in corpus (2)

• Approximating the partition function of the ferromagnetic Potts model
• The Bethe Partition Function of Log-supermodular Graphical Models

Cited by in corpus (3)

• Extremes of the internal energy of the Potts model on cubic graphs
• Extremal regular graphs: the case of the infinite regular tree
• Structure Learning Using Forced Pruning