Tree-reweighted max-product (TRW) message
passing [9] is a modified form of the ordinary
max-product algorithm for attempting to find minimal energy
configurations in Markov random field with cycles. For a TRW fixed
point satisfying the strong tree agreement condition, the algorithm
outputs a configuration that is provably optimal. In this paper, we
focus on the case of binary variables with pairwise couplings, and
establish stronger properties of TRW fixed points that satisfy only
the milder condition of weak tree agreement (WTA). First, we
demonstrate how it is possible to identify part of the optimal
solution---i.e., a provably optimal solution for a subset of nodes---
without knowing a complete solution. Second, we show that for
submodular functions, a WTA fixed point always yields a globally
optimal solution. We establish that for binary variables, any WTA
fixed point always achieves the global maximum of the linear
programming relaxation underlying the TRW method.