  Graphical models with High Order Potentials (HOPs) have received considerable
interest in recent years. While there are a variety of approaches to inference
in these models, nearly all of them amount to solving a linear program (LP)
relaxation with unary consistency constraints between the HOP and the
individual variables. In many cases, the resulting relaxations are loose, and
in these cases the results of inference can be poor. It is thus desirable to
look for more accurate ways of performing inference in these models. In this
work, we study the LP relaxations that result from enforcing additional
consistency constraints between the HOP and the rest of the model. We address
theoretical questions about the strength of the resulting relaxations compared
to the relaxations that arise in standard approaches, and we develop practical
and efficient message passing algorithms for optimizing the LPs. Empirically,
we show that the LPs with additional consistency constraints lead to more
accurate inference on some challenging problems that include a combination of
low order and high order terms.
