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

Nicholas Ruozzi
Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, PMLR R11:618-627, 2013.

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 demon- strate 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR11-ruozzi13a, title = {Beyond Log-Supermodularity: Lower Bounds and the {B}ethe Partition Function}, author = {Ruozzi, Nicholas}, booktitle = {Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence}, pages = {618--627}, year = {2013}, editor = {Nicholson, Ann and Smyth, Padhraic}, volume = {R11}, series = {Proceedings of Machine Learning Research}, month = {12--14 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r11/main/assets/ruozzi13a/ruozzi13a.pdf}, url = {https://proceedings.mlr.press/r11/ruozzi13a.html}, 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 demon- strate 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.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Beyond Log-Supermodularity: Lower Bounds and the Bethe Partition Function %A Nicholas Ruozzi %B Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2013 %E Ann Nicholson %E Padhraic Smyth %F pmlr-vR11-ruozzi13a %I PMLR %P 618--627 %U https://proceedings.mlr.press/r11/ruozzi13a.html %V R11 %X A recent result has demonstrated that the Bethe partition function always lower bounds the true partition function of binary, log- supermodular graphical models. We demon- strate 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. %Z Reissued by PMLR on 04 October 2026.
APA
Ruozzi, N.. (2013). Beyond Log-Supermodularity: Lower Bounds and the Bethe Partition Function. Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R11:618-627 Available from https://proceedings.mlr.press/r11/ruozzi13a.html. Reissued by PMLR on 04 October 2026.

Related Material