Abstract
The paper investigates the behavior of iterative belief propagation algorithm (IBP) in Bayesian networks with loops. In multiply connected network, IBP is only guaranteed to converge in linear time to the correct posterior marginals when evidence nodes form a loop-cutset. We propose an e-cutset criteria that IBP will converge and compute posterior marginals close to correct when a single value in the domain of each loop-cutset node receives very strong support compared to other values thus producing an effect similar to the observed loop-cutset. We investigate the support for this criteria analytically and empirically and show thatit is consistent with previous observations of IBP performance in multiply connected networks.