Spotlight
Graph Zeta Function in the Bethe Free Energy and Loopy Belief Propagation
Yusuke Watanabe · Kenji Fukumizu

Tue Dec 8th 03:33 -- 03:34 PM @ None

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.

Author Information

Yusuke Watanabe (The Institute of Statistical Mathematics)
Kenji Fukumizu (Institute of Statistical Mathematics / Preferred Networks / RIKEN AIP)

More from the Same Authors