  We propose an approach for approximating the partition function which is
based on two steps: (1) computing the partition function of a simplified model
which is obtained by deleting model edges, and (2) rectifying the result by
applying an edge-by-edge correction. The approach leads to an intuitive
framework in which one can trade-off the quality of an approximation with the
complexity of computing it. It also includes the Bethe free energy
approximation as a degenerate case. We develop the approach theoretically in
this paper and provide a number of empirical results that reveal its practical
utility.
