  In this paper, we study the problem of inference in high-order structured
prediction tasks. In the context of Markov random fields, the goal of a
high-order inference task is to maximize a score function on the space of
labels, and the score function can be decomposed into sum of unary and
high-order potentials. We apply a generative model approach to study the
problem of high-order inference, and provide a two-stage convex optimization
algorithm for exact label recovery. We also provide a new class of hypergraph
structural properties related to hyperedge expansion that drives the success in
general high-order inference problems. Finally, we connect the performance of
our algorithm and the hyperedge expansion property using a novel hypergraph
Cheeger-type inequality.
