Walk-Sums and Belief Propagation in Gaussian Graphical Models

TLDR

The authors introduce a walk‑based framework for analysis and inference in Gaussian graphical models. They decompose pairwise correlations into sums over all walks, weighting each by the product of edgewise partial correlations, and apply this to walk‑summable Gaussian models, interpreting Gaussian belief propagation on trees and loopy BP on cyclic graphs. They characterize walk‑summable models, relate them to diagonally dominant, attractive, non‑frustrated, and pairwise‑normalizable classes, and show that the walk‑sum view yields deeper insight into Gaussian belief propagation and provably stronger convergence guarantees in loopy graphs.

Abstract

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.