  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.
