Home Page




Editorial Board


Open Source Software




Frequently Asked Questions

Contact Us

RSS Feed

Walk-Sums and Belief Propagation in Gaussian Graphical Models

Dmitry M. Malioutov, Jason K. Johnson, Alan S. Willsky; 7(73):2031−2064, 2006.


We present a new framework based on walks in a graph for analysis and inference in Gaussian graphical models. The key idea is to decompose the correlation between each pair of variables as a sum over all walks between those variables in the graph. The weight of each walk is given by a product of edgewise partial correlation coefficients. This representation holds for a large class of Gaussian graphical models which we call walk-summable. We give a precise characterization of this class of models, and relate it to other classes including diagonally dominant, attractive, non-frustrated, and pairwise-normalizable. We provide a walk-sum interpretation of Gaussian belief propagation in trees and of the approximate method of loopy belief propagation in graphs with cycles. The walk-sum perspective leads to a better understanding of Gaussian belief propagation and to stronger results for its convergence in loopy graphs.

© JMLR 2006. (edit, beta)