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

Cited by in corpus (19)

• Critical phenomena in complex networks
• Loop Calculus Helps to Improve Belief Propagation and Linear Programming Decodings of Low-Density-Parity-Check Codes
• Phase diagram of an Ising model with competitive interactions on a Husimi tree and its disordered counterpart
• Belief Propagation and Beyond for Particle Tracking
• 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 Loop Series on Planar Graphs
• Communication and correlation among communities
• Zero temperature solutions of the Edwards-Anderson model in random Husimi Lattices
• Improving convergence of Belief Propagation decoding
• Approximate inference on planar graphs using Loop Calculus and Belief Propagation
• "Clumpiness" Mixing in Complex Networks
• 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
• Reducing the Error Floor
• Bethe Free Energy Approach to LDPC Decoding on Memory Channels
• Decay of Correlations for Sparse Graph Error Correcting Codes
• Searching for low weight pseudo-codewords
• Orbit-Product Representation and Correction of Gaussian Belief Propagation