Loop series for discrete statistical models on graphs

Abstract

In this paper we present derivation details, logic, and motivation for the loop calculus introduced in \cite{06CCa}. Generating functions for three inter-related discrete statistical models are each expressed in terms of a finite series. The first term in the series corresponds to the Bethe-Peierls (Belief Propagation)-BP contribution, the other terms are labeled by loops on the factor graph. All loop contributions are simple rational functions of spin correlation functions calculated within the BP approach. We discuss two alternative derivations of the loop series. One approach implements a set of local auxiliary integrations over continuous fields with the BP contribution corresponding to an integrand saddle-point value. The integrals are replaced by sums in the complimentary approach, briefly explained in \cite{06CCa}. A local gauge symmetry transformation that clarifies an important invariant feature of the BP solution, is revealed in both approaches. The partition function remains invariant while individual terms change under the gauge transformation. The requirement for all individual terms to be non-zero only for closed loops in the factor graph (as opposed to paths with loose ends) is equivalent to fixing the first term in the series to be exactly equal to the BP contribution. Further applications of the loop calculus to problems in statistical physics, computer and information sciences are discussed.

20 pages, 3 figures

References in corpus (8)

• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Multifractal Detrended Fluctuation Analysis of Sunspot Time Series
• Radiative corrections to K_{l3} decays
• Survey Propagation as local equilibrium equations
• The glassy phase of Gallager codes
• Loop Calculus in Statistical Physics and Information Science
• How to Compute Loop Corrections to Bethe Approximation
• Loop expansion around the Bethe-Peierls approximation for lattice models

Cited by in corpus (81)

• Critical phenomena in complex networks
• Inverse statistical problems: from the inverse Ising problem to data science
• Complexity of Inference in Graphical Models
• Belief-propagation algorithm and the Ising model on networks with arbitrary distributions of motifs
• The Bethe Permanent of a Non-Negative Matrix
• Normal Factor Graphs and Holographic Transformations
• The Bethe Partition Function of Log-supermodular Graphical Models
• Counting in Graph Covers: A Combinatorial Characterization of the Bethe Entropy Function
• Convergence Analysis of Distributed Inference with Vector-Valued Gaussian Belief Propagation
• Loop Calculus Helps to Improve Belief Propagation and Linear Programming Decodings of Low-Density-Parity-Check Codes
• Region graph partition function expansion and approximate free energy landscapes: Theory and some numerical results
• Tensor Networks contraction and the Belief Propagation algorithm
• Partition function loop series for a general graphical model: free energy corrections and message-passing equations
• Mathematical Programming Decoding of Binary Linear Codes: Theory and Algorithms
• Spectral density of random graphs with topological constraints
• Finite size corrections to disordered Ising models on Random Regular Graphs
• Loop expansion around the Bethe approximation through the $M$-layer construction
• Stability analysis on the finite-temperature replica-symmetric and first-step replica-symmetry-broken cavity solutions of the random vertex cover problem
• Phase diagram of an Ising model with competitive interactions on a Husimi tree and its disordered counterpart
• Belief Propagation and Loop Calculus for the Permanent of a Non-Negative Matrix
• Approximating the Permanent with Fractional Belief Propagation
• Join-Graph Propagation Algorithms
• From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy
• Exactness of Belief Propagation for Some Graphical Models with Loops
• Belief Propagation and Beyond for Particle Tracking
• Belief Propagation and Loop Series on Planar Graphs
• Replica Cluster Variational Method: the Replica Symmetric solution for the 2D random bond Ising model
• Stochastic optimization by message passing
• Block belief propagation algorithm for two-dimensional tensor networks
• Communication and correlation among communities
• Large Deviations of Correlation Functions in Random Magnets
• Perturbative Corrections for Approximate Inference in Gaussian Latent Variable Models
• Zero temperature solutions of the Edwards-Anderson model in random Husimi Lattices
• Partition Function Expansion on Region-Graphs and Message-Passing Equations
• Improving convergence of Belief Propagation decoding
• "Clumpiness" Mixing in Complex Networks
• Discrete geometric analysis of message passing algorithm on graphs
• Approximate inference on planar graphs using Loop Calculus and Belief Propagation
• Message-passing algorithm of quantum annealing with nonstoquastic Hamiltonian
• Loop Series Expansions for Tensor Networks
• Perturbative large deviation analysis of non-equilibrium dynamics
• New Understanding of the Bethe Approximation and the Replica Method
• Fermions and Loops on Graphs. I. Loop Calculus for Determinant
• Belief propagation with multipoint correlations and its application to Inverse problem
• Boltzmann distribution of free energies in a finite-connectivity spin-glass system and the cavity approach
• Long-range frustration in T=0 first-step replica-symmetry-broken solutions of finite-connectivity spin glasses
• Sums over geometries and improvements on the mean field approximation
• A spin glass approach to the directed feedback vertex set problem
• Pairwise MRF Calibration by Perturbation of the Bethe Reference Point
• Ising spin glass models versus Ising models: an effective mapping at high temperature III. Rigorous formulation and detailed proof for general graphs
• Planar Graphical Models which are Easy
• State Estimation of Power Flows for Smart Grids via Belief Propagation
• Loop corrections for approximate inference
• Fermions and Loops on Graphs. II. Monomer-Dimer Model as Series of Determinants
• Loop corrections in spin models through density consistency
• Computing loop corrections by message passing
• Cycle-based Cluster Variational Method for Direct and Inverse Inference
• Norm-Product Belief Propagation: Primal-Dual Message-Passing for Approximate Inference
• Quantum Cluster Variational Method and Message Passing Algorithms Revisited
• Random cluster model on regular graphs
• Spectral Bounds for the Ising Ferromagnet on an Arbitrary Given Graph
• A Cluster-Cumulant Expansion at the Fixed Points of Belief Propagation
• Beyond the Bethe Free Energy of LDPC Codes via Polymer Expansions
• Holographic Transformation, Belief Propagation and Loop Calculus for Generalized Probabilistic Theories
• Clamping Improves TRW and Mean Field Approximations
• Statistical physics of loopy interactions: Independent-loop approximation and beyond
• Loop-corrected belief propagation for lattice spin models
• Codes on Graphs: Observability, Controllability and Local Reducibility
• Graph polynomials and approximation of partition functions with Loopy Belief Propagation
• On one-step replica symmetry breaking in the Edwards-Anderson spin glass model
• New graph polynomials from the Bethe approximation of the Ising partition function
• Truncating the loop series expansion for Belief Propagation
• Reducing the Error Floor
• The Bethe Free Energy Allows to Compute the Conditional Entropy of Graphical Code Instances. A Proof from the Polymer Expansion
• Tensor Network Loop Cluster Expansions for Quantum Many-Body Problems
• Decay of Correlations for Sparse Graph Error Correcting Codes
• Bethe Free Energy Approach to LDPC Decoding on Memory Channels
• Orbit-Product Representation and Correction of Gaussian Belief Propagation
• Gauging Variational Inference
• Searching for low weight pseudo-codewords
• Forest expansion of two-body partition functions for sparse interaction graphs