  We consider the problem of deleting edges from a Bayesian network for the
purpose of simplifying models in probabilistic inference. In particular, we
propose a new method for deleting network edges, which is based on the evidence
at hand. We provide some interesting bounds on the KL-divergence between
original and approximate networks, which highlight the impact of given evidence
on the quality of approximation and shed some light on good and bad candidates
for edge deletion. We finally demonstrate empirically the promise of the
proposed edge deletion technique as a basis for approximate inference.
