  Markov Chain Monte Carlo (MCMC) and Belief Propagation (BP) are the most
popular algorithms for computational inference in Graphical Models (GM). In
principle, MCMC is an exact probabilistic method which, however, often suffers
from exponentially slow mixing. In contrast, BP is a deterministic method,
which is typically fast, empirically very successful, however in general
lacking control of accuracy over loopy graphs. In this paper, we introduce MCMC
algorithms correcting the approximation error of BP, i.e., we provide a way to
compensate for BP errors via a consecutive BP-aware MCMC. Our framework is
based on the Loop Calculus (LC) approach which allows expressing the BP error
as a sum of weighted generalized loops. Although the full series is
computationally intractable, it is known that a truncated series, summing up
all 2-regular loops, is computable in polynomial-time for planar pair-wise
binary GMs and it also provides a highly accurate approximation empirically.
Motivated by this, we first propose a polynomial-time approximation MCMC scheme
for the truncated series of general (non-planar) pair-wise binary models. Our
main idea here is to use the Worm algorithm, known to provide fast mixing in
other (related) problems, and then design an appropriate rejection scheme to
sample 2-regular loops. Furthermore, we also design an efficient rejection-free
MCMC scheme for approximating the full series. The main novelty underlying our
design is in utilizing the concept of cycle basis, which provides an efficient
decomposition of the generalized loops. In essence, the proposed MCMC schemes
run on transformed GM built upon the non-trivial BP solution, and our
experiments show that this synthesis of BP and MCMC outperforms both direct
MCMC and bare BP schemes.
