MAP inference in MRFs (or energy minimization) is known to be NP-hard in general, and thus research has focussed on either finding efficiently solvable subclasses (eg trees via BP), or approximate inference algorithms (eg Loopy BP and Tree-reweighted message passing).
I will first present a unifying perspective of these approximate techniques – called “Decomposition Methods”. These are methods that decompose the given problem over a graph into tractable subproblems over subgraphs and then employ message passing over these subgraphs to get a global solution. This provides a new way of thinking about BP and TRW as successive steps in a hierarchy of decomposition methods. Using this framework, we take the first step towards extending this hierarchy beyond trees. We leverage a new class of graphs amenable to exact inference, called outer-planar graphs, and propose an approximate inference algorithm called Outer- Planar Decomposition (OPD). OPD is a strict generalization of BP and TRW, and contains both of them as special cases. Our experiments show that this extension beyond trees is indeed very powerful – OPD outperforms current state- of-art inference methods on hard non-submodular synthetic problems and is competitive on real vision applications.