Convergence of belief propagation algorithms on binary pairwise Gibbs random fields

Abstract

In this paper, we study the convergence of belief propagation algorithms (BPAs) on binary pairwise Gibbs random fields (BP-GRFs). Exploiting the equivalence of BPA on the graph associated with BP-GRF and the corresponding computation tree, we first express each BPA message from a node to its parent (on the computation tree) as a function of the messages from its descendants (on the computation tree) at a certain distance. Then, we introduce the notion of a message range by restricting message functions to appropriate domains that correspond to arbitrary initialization of the BPA. We show that message ranges contract at each BPA iteration and characterize the asymptotic behavior of BPA messages on BP-GRF graphs. For a special but important class of BP-GRFs, we are able to derive necessary and sufficient conditions for the BPAs to converge. This should be contrasted with existing methods which typically provide sufficient conditions for convergence (but may not impose any restrictions on the BP-GRFs). We have experimentally shown that these necessary and sufficient conditions can be checked with low computational complexity and, hence, can be applied to large graphs. © 2011 IFAC.