A Caltech Library Service

Feedback Message Passing for Inference in Gaussian Graphical Models

Liu, Ying and Chandrasekaran, Venkat and Anandkumar, Animashree and Willsky, Alan S. (2010) Feedback Message Passing for Inference in Gaussian Graphical Models. In: 2010 IEEE International Symposium on Information Theory Proceedings (ISIT). IEEE , Piscataway, NJ, pp. 1683-1687. ISBN 978-1-4244-6960-4.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


For Gaussian graphical models with cycles, loopy belief propagation often performs reasonably well, but its convergence is not guaranteed and the computation of variances is generally incorrect. In this paper, we identify a set of special vertices called a feedback vertex set whose removal results in a cycle-free graph. We propose a feedback message passing algorithm in which non-feedback nodes send out one set of messages while the feedback nodes use a different message update scheme. Exact inference results can be obtained in O(k^2n), where k is the number of feedback nodes and n is the total number of nodes. For graphs with large feedback vertex sets, we describe a tractable approximate feedback message passing algorithm. Experimental results show that this procedure converges more often, faster, and provides better results than loopy belief propagation.

Item Type:Book Section
Related URLs:
URLURL TypeDescription ItemJournal Article
Additional Information:© 2010 IEEE. Date of Current Version: 23 July 2010. This work is supported in part by ARO under MURI Grant W911NF-06-1-0076, by AFOSR under Grant FA9550-08-1-1080 and MURI Grant FA9550-06-1-0324. We thank Professor Devavrat Shah and Justin Dauwels for many helpful discussions.
Funding AgencyGrant Number
Army Research Office (ARO)W911NF-06-1-0076
Air Force Office of Scientific Research (AFOSR)FA9550-08-1-1080
Air Force Office of Scientific Research (AFOSR)FA9550-06-1-0324
Subject Keywords:Gaussian graphical models, belief propagation, loopy graphs, feedback vertex set
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number11445908
Record Number:CaltechAUTHORS:20121004-153356182
Persistent URL:
Official Citation:Ying Liu; Chandrasekaran, V.; Anandkumar, A.; Willsky, A.S.; , "Feedback message passing for inference in gaussian graphical models," Information Theory Proceedings (ISIT), 2010 IEEE International Symposium on , vol., no., pp.1683-1687, 13-18 June 2010 doi: 10.1109/ISIT.2010.5513321 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:34688
Deposited By: Tony Diaz
Deposited On:04 Oct 2012 22:52
Last Modified:03 Oct 2019 04:21

Repository Staff Only: item control page