  LP relaxation-based message passing algorithms provide an effective tool for
MAP inference over Probabilistic Graphical Models. However, different LP
relaxations often have different objective functions and variables of differing
dimensions, which presents a barrier to effective comparison and analysis. In
addition, the computational complexity of LP relaxation-based methods grows
quickly with the number of constraints. Reducing the number of constraints
without sacrificing the quality of the solutions is thus desirable.
  We propose a unified formulation under which existing MAP LP relaxations may
be compared and analysed. Furthermore, we propose a new tool called Marginal
Polytope Diagrams. Some properties of Marginal Polytope Diagrams are exploited
such as node redundancy and edge equivalence. We show that using Marginal
Polytope Diagrams allows the number of constraints to be reduced without
loosening the LP relaxations. Then, using Marginal Polytope Diagrams and
constraint reduction, we develop three novel message passing algorithms, and
demonstrate that two of these show a significant improvement in speed over
state-of-art algorithms while delivering a competitive, and sometimes higher,
quality of solution.
