Exact inference on Gaussian graphical models of arbitrary topology using path-sums

Journal article

We present the path-sum formulation for exact statistical inference of marginals on Gaussian graphical models of arbitrary topology. The path-sum formulation gives the covariance between each pair of variables as a branched continued fraction of finite depth and breadth. Our method originates from the closed-form resummation of infinite families of terms of the walk-sum representation of the covariance matrix. We prove that the path-sum formulation always exists for models whose covariance matrix is positive definite: i.e. it is valid for both walk-summable and non-walk-summable graphical models of arbitrary topology. We show that for graphical models on trees the path-sum formulation is equivalent to Gaussian belief propagation. We also recover, as a corollary, an existing result that uses determinants to calculate the covariance matrix. We show that the path-sum formulation formulation is valid for arbitrary partitions of the inverse covariance matrix. We give detailed examples demonstrating our results.

Authors: Giscard, P; Choo, Z; Thwaite, S; Jaksch, D

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Journal of Machine Learning Research
• Journal: Journal of Machine Learning Research
• Volume: 17
• Issue: 71
• Pages: 1-19
• Publication date: 2016-04-01
• Acceptance date: 2015-11-12
• EISSN: 1533-7928
• ISSN: 1532-4435
• Keywords: walk-sum; Gaussian graphical models; belief propagation; path-sum; block matrices; graphs of arbitrary topology