Abstract
The paper presents an iterative version of join-tree clustering that applies the message passing of join-tree clustering algorithm to join-graphs rather than to join-trees, iteratively. It is inspired by the success of Pearl's belief propagation algorithm (BP) as an iterative approximation scheme on one hand, and by a recently introduced mini-clustering (MC(i)) success as an anytime approximation method, on the other. The proposed Iterative Join-graph Propagation (IJGP) is both anytime and iterative. It belongs to the class of generalized belief propagation methods, recently proposed using analogy with algorithms in statistical physics. Empirical evaluation of this approach on a number of problem classes demonstrates that it is almost always superior to IBP and MC(i), and is sometimes more accurate by as much as several orders of magnitude.

PostScript