Abstract:
Variational methods, such as mean-field (MF) and tree-reweighted (TRW), provide computationally efficient approximations of the log-partition function for generic graphical models but their approximation ratio is generally not quantified.
%
As the primary contribution of this work, we provide an approach to quantify their approximation ratio for any discrete pairwise graphical model with non-negative potentials through a property of the underlying graph structure $G$.
%
Specifically, we argue that (a variant of) TRW produces an estimate within factor $1/\sqrt{\kappa(G)}$ where $\kappa(G) \in (0,1]$
captures how far $G$ is from tree structure.
%
As a consequence, the approximation ratio is $1$ for trees, $\sqrt{(d+1)/2}$ for graphs with maximum average degree $d$ and $1+1/(2\beta)+o_{\beta\to \infty}(1/\beta)$ for graphs with girth at least $\beta \log N$.
%
The quantity $\kappa(G)$ is the solution of a min-max problem associated with the spanning tree polytope of $G$ that can be evaluated in polynomial time for any graph.
%
We provide a near linear-time variant that achieves an approximation ratio depending on the minimal (across edges) effective resistance of the graph. We connect our results to the graph partition approximation method and thus provide a unified perspective.
