  Tree-reweighted max-product (TRW) message passing 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.
