  Variational approximation, such as mean-field (MF) and tree-reweighted (TRW),
provide a computationally efficient approximation of the log-partition function
for a generic graphical model. TRW provably provides an upper bound, but the
approximation ratio is generally not quantified.
  As the primary contribution of this work, we provide an approach to quantify
the approximation ratio through the property of the underlying graph structure.
Specifically, we argue that (a variant of) TRW produces an estimate that is
within factor $\frac{1}{\sqrt{\kappa(G)}}$ of the true log-partition function
for any discrete pairwise graphical model over graph $G$, where $\kappa(G) \in
(0,1]$ captures how far $G$ is from tree structure with $\kappa(G) = 1$ for
trees and $2/N$ for the complete graph over $N$ vertices. As a consequence, the
approximation ratio is $1$ for trees, $\sqrt{(d+1)/2}$ for any graph with
maximum average degree $d$, and $\stackrel{\beta\to\infty}{\approx}
1+1/(2\beta)$ for graphs with girth (shortest cycle) at least $\beta \log N$.
In general, $\kappa(G)$ is the solution of a max-min problem associated with
$G$ that can be evaluated in polynomial time for any graph.
  Using samples from the uniform distribution over the spanning trees of G, we
provide a near linear-time variant that achieves an approximation ratio equal
to the inverse of square-root of minimal (across edges) effective resistance of
the graph. We connect our results to the graph partition-based approximation
method and thus provide a unified perspective.
  Keywords: variational inference, log-partition function, spanning tree
polytope, minimum effective resistance, min-max spanning tree, local inference
