We show that the influential algorithm of iterative
belief propagation can be understood in terms of exact inference on
a polytree, which results from deleting enough edges from the
original network.  We show that deleting edges implies adding new
parameters into a network, and that the iterations of belief
propagation are searching for values of these new parameters which
satisfy intuitive conditions that we characterize.  The new
semantics lead to the following question: Can one improve the
quality of approximations computed by belief propagation by
recovering some of the deleted edges, while keeping the network easy
enough for exact inference?  We show that the answer
is yes, leading to another question: How do we choose which edges to
recover?  To answer, we propose a specific method based on mutual
information which is motivated by the edge deletion semantics.
Empirically, we provide experimental results showing that the
quality of approximations can be improved without incurring much
additional computational cost. We also show that recovering certain
edges with low mutual information may not be worthwhile as they
increase the computational complexity, without necessarily improving
the quality of approximations.