A new look at reweighted message passing

We propose a new family of message passing techniques for MAP estimation in graphical models which we call Sequen-tial Reweighted Message Passing (SRMP). Special cases include well-known techniques such as Min-Sum Diffusion (MSD) and a faster Sequential Tree-Reweighted Message Passing (TRW-S). Importantly, our derivation is simpler than the original derivation of TRW-S, and does not in-volve a decomposition into trees. This allows easy gener-alizations. The new family of algorithms can be viewed as a generalization of TRW-S from pairwise to higher-order graphical models. We test SRMP on several real-world problems with promising results.