Graph Zeta Function in the Bethe Free Energy and Loopy Belief Propagation

Abstract

We propose a new approach to the analysis of Loopy Belief Propagation (LBP) by establishing a formula that connects the Hessian of the Bethe free energy with the edge zeta function. The formula has a number of theoretical implications on LBP. It is applied to give a sufficient condition that the Hessian of the Bethe free energy is positive definite, which shows non-convexity for graphs with multiple cycles. The formula clarifies the relation between the local stability of a fixed point of LBP and local minima of the Bethe free energy. We also propose a new approach to the uniqueness of LBP fixed point, and show various conditions of uniqueness.

19 pages, Annual Conference on Neural Information Processing Systems (NIPS 2009), together with the supplementary material

References in corpus (1)

• Loopy Belief Propagation for Approximate Inference: An Empirical Study

Cited by in corpus (4)

• Nishimori meets Bethe: a spectral method for node classification in sparse weighted graphs
• Extreme singular values of inhomogeneous sparse random rectangular matrices
• Norm of matrix-valued polynomials in random unitaries and permutations
• Local stability of Belief Propagation algorithm with multiple fixed points