Sudderth–Wainwright–Willsky conjecture on the Bethe partition function

Let $G=(V,\mathcal{A})$ be a factor graph and let $f:\mathbb{\{0,1\}}^n\to\mathbb{R}_{\geq 0}$ admit a pairwise, log-supermodular factorization over $G$. Let $Z(G)=\sum_x f(x)$ be the true partition function, and let $Z_\mathrm{B}(G)$ denote the maximum Bethe approximation over the local marginal polytope.

Sudderth–Wainwright–Willsky conjecture. If $f$ admits a pairwise, log-supermodular factorization over $G$, then

$$Z_\mathrm{B}(G)\leq Z(G).$$

This conjecture asserts that the Bethe partition function is a lower bound on the true partition function for attractive pairwise binary graphical models. The paper studies this conjecture and proves the bound under the stated log-supermodularity assumptions.