Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model

Abstract

We study the hard-core model defined on independent sets of an input graph where the independent sets are weighted by a parameter $\lambda >0$. For constant $\Delta$, previous work of Weitz (2006) established an FPTAS for the partition function for graphs of maximum degree $\Delta$ when $\lambda <{\lambda }_c(\Delta )$. The threshold ${\lambda }_c(\Delta )$ is the critical point for the phase transition for uniqueness/non-uniqueness on the infinite $\Delta$-regular trees. Sly (2010) showed that there is no FPRAS, unless NP=RP, when $\lambda >{\lambda }_c(\Delta )$. The running time of Weitz's algorithm is exponential in $\log (\Delta )$. Here we present an FPRAS for the partition function whose running time is $O^{\ast }(n^2)$. We analyze the simple single-site Glauber dynamics for sampling from the associated Gibbs distribution. We prove there exists a constant ${\Delta }_0$ such that for all graphs with maximum degree $\Delta \ge {\Delta }_0$ and girth $\ge 7$, the mixing time of the Glauber dynamics is $O(n\log (n))$ when $\lambda <{\lambda }_c(\Delta )$. Our work complements that of Weitz which applies for constant $\Delta$ whereas our work applies for all $\Delta \ge {\Delta }_0$. We utilize loopy BP (belief propagation), a widely-used inference algorithm. A novel aspect of our work is using the principal eigenvector for the BP operator to design a distance function which contracts in expectation for pairs of states that behave like the BP fixed point. We also prove that the Glauber dynamics behaves locally like loopy BP. As a byproduct we obtain that the Glauber dynamics converges, after a short burn-in period, close to the BP fixed point, and this implies that the fixed point of loopy BP is a close approximation to the Gibbs distribution. Using these connections we establish that loopy BP quickly converges to the Gibbs distribution when the girth $\ge 6$ and $\lambda <{\lambda }_c(\Delta )$.

References in corpus (4)

• Loopy Belief Propagation for Approximate Inference: An Empirical Study
• The computational hardness of counting in two-spin models on d-regular graphs
• Spatial mixing and approximation algorithms for graphs with bounded connective constant
• FPTAS for #BIS with Degree Bounds on One Side