Belief Propagation and Loop Series on Planar Graphs

Abstract

We discuss a generic model of Bayesian inference with binary variables defined on edges of a planar graph. The Loop Calculus approach of [1, 2] is used to evaluate the resulting series expansion for the partition function. We show that, for planar graphs, truncating the series at single-connected loops reduces, via a map reminiscent of the Fisher transformation [3], to evaluating the partition function of the dimer matching model on an auxiliary planar graph. Thus, the truncated series can be easily re-summed, using the Pfaffian formula of Kasteleyn [4]. This allows to identify a big class of computationally tractable planar models reducible to a dimer model via the Belief Propagation (gauge) transformation. The Pfaffian representation can also be extended to the full Loop Series, in which case the expansion becomes a sum of Pfaffian contributions, each associated with dimer matchings on an extension to a subgraph of the original graph. Algorithmic consequences of the Pfaffian representation, as well as relations to quantum and non-planar models, are discussed.

Accepted for publication in Journal of Statistical Mechanics: theory and experiment

References in corpus (12)

• Loop series for discrete statistical models on graphs
• Nishimori point in the 2D +/- J random-bond Ising model
• Loop Calculus in Statistical Physics and Information Science
• Conformal Invariance and SLE in Two-Dimensional Ising Spin Glasses
• Trading inverses for an irrep in the Solovay-Kitaev theorem
• Combinatorial and topological approach to the 3D Ising model
• Disordered Dirac Fermions: the Marriage of Three Different Approaches
• Loop Calculus Helps to Improve Belief Propagation and Linear Programming Decodings of Low-Density-Parity-Check Codes
• Exact Solution of the Ising Model on Group Lattices of Genus $g>1$
• Planar dimers and Harnack curves
• Integrability of graph combinatorics via random walks and heaps of dimers
• Pseudo-codeword Landscape

Cited by in corpus (6)

• Absdet-Pseudo-Codewords and Perm-Pseudo-Codewords: Definitions and Properties
• Message passing and Monte Carlo algorithms: connecting fixed points with metastable states
• Approximate inference on planar graphs using Loop Calculus and Belief Propagation
• Discrete geometric analysis of message passing algorithm on graphs
• Pairwise MRF Calibration by Perturbation of the Bethe Reference Point
• Gauging Variational Inference