Bethe Bounds and Approximating the Global Optimum
  Inference in general Markov random fields (MRFs) is NP-hard, though
identifying the maximum a posteriori (MAP) configuration of pairwise MRFs with
submodular cost functions is efficiently solvable using graph cuts. Marginal
inference, however, even for this restricted class, is in #P. We prove new
formulations of derivatives of the Bethe free energy, provide bounds on the
derivatives and bracket the locations of stationary points, introducing a new
technique called Bethe bound propagation. Several results apply to pairwise
models whether associative or not. Applying these to discretized
pseudo-marginals in the associative case we present a polynomial time
approximation scheme for global optimization provided the maximum degree is
$O(\log n)$, and discuss several extensions.
