Spectral Approximate Inference
  Given a graphical model (GM), computing its partition function is the most
essential inference task, but it is computationally intractable in general. To
address the issue, iterative approximation algorithms exploring certain local
structure/consistency of GM have been investigated as popular choices in
practice. However, due to their local/iterative nature, they often output poor
approximations or even do not converge, e.g., in low-temperature regimes (hard
instances of large parameters). To overcome the limitation, we propose a novel
approach utilizing the global spectral feature of GM. Our contribution is
two-fold: (a) we first propose a fully polynomial-time approximation scheme
(FPTAS) for approximating the partition function of GM associating with a
low-rank coupling matrix; (b) for general high-rank GMs, we design a spectral
mean-field scheme utilizing (a) as a subroutine, where it approximates a
high-rank GM into a product of rank-1 GMs for an efficient approximation of the
partition function. The proposed algorithm is more robust in its running time
and accuracy than prior methods, i.e., neither suffers from the convergence
issue nor depends on hard local structures, as demonstrated in our experiments.
