  Maximum A posteriori Probability (MAP) inference in graphical models amounts
to solving a graph-structured combinatorial optimization problem. Popular
inference algorithms such as belief propagation (BP) and generalized belief
propagation (GBP) are intimately related to linear programming (LP) relaxation
within the Sherali-Adams hierarchy. Despite the popularity of these algorithms,
it is well understood that the Sum-of-Squares (SOS) hierarchy based on
semidefinite programming (SDP) can provide superior guarantees. Unfortunately,
SOS relaxations for a graph with $n$ vertices require solving an SDP with
$n^{\Theta(d)}$ variables where $d$ is the degree in the hierarchy. In
practice, for $d\ge 4$, this approach does not scale beyond a few tens of
variables. In this paper, we propose binary SDP relaxations for MAP inference
using the SOS hierarchy with two innovations focused on computational
efficiency. Firstly, in analogy to BP and its variants, we only introduce
decision variables corresponding to contiguous regions in the graphical model.
Secondly, we solve the resulting SDP using a non-convex Burer-Monteiro style
method, and develop a sequential rounding procedure. We demonstrate that the
resulting algorithm can solve problems with tens of thousands of variables
within minutes, and outperforms BP and GBP on practical problems such as image
denoising and Ising spin glasses. Finally, for specific graph types, we
establish a sufficient condition for the tightness of the proposed partial SOS
relaxation.
