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 em Sequential Reweighted Message Passing (SRMP). Special cases include well-known techniques such as em Min-Sum Diffusion (MSD) and a faster em Sequential Tree-Reweighted Message Passing (TRW-S). Importantly, our derivation is simpler than the original derivation of TRW-S, and does not involve a decomposition into trees. This allows easy generalizations. We present such a generalization for the case of higher-order graphical models, and test it on several real-world problems with promising results.