Spectral Approximate Inference

Sejun Park, Eunho Yang, Se-Young Yun, Jinwoo Shin

In probabilistic machine learning, Graphical Models (GMs) are foundational tools used to represent complex joint distributions. However, the most critical task in using GMs—computing the partition function ($Z$)—is notoriously difficult. The partition function acts as the normalizing constant that translates raw model scores into valid probabilities, but computing it is generally #P-hard.

Existing heuristic approaches, such as Variational Inference (e.g., Belief Propagation) or Markov Chain Monte Carlo (e.g., Gibbs sampling), rely heavily on local, iterative updates. While effective in many scenarios, these methods frequently fail to converge or produce highly inaccurate results in "low-temperature" regimes—situations where the interactions (couplings) between variables are exceptionally strong. In these hard instances, local structures fail to capture the full picture, causing traditional algorithms to get stuck.

To overcome this, researchers from KAIST and AITRICS have developed a novel spectral approach to approximate the partition function. By shifting the focus from local message-passing to global spectral features (eigenvalues and eigenvectors), they provide a provable polynomial-time approximation for low-rank models and a robust "spectral mean-field" scheme for more complex scenarios.

The Spectral Strategy

The authors propose a two-step strategy based on the spectral properties of the GM's coupling matrix $A$:

1. Fully Polynomial-Time Approximation Scheme for Low-Rank GMs

For models where the coupling matrix has a low rank, the authors reformulate the partition function using its eigenvalues ($\lambda$) and eigenvectors ($v$). By quantizing the values of the projections of the state vector onto these eigenvectors, they transform the intractable exponential summation into a manageable dynamic programming problem. This yields a Fully Polynomial-Time Approximation Scheme (FPTAS), provided the rank of the matrix remains small.

2. Spectral Mean-Field for High-Rank GMs

Because most real-world matrices are high-rank, the authors introduce a Spectral Mean-Field approach. They decompose the high-rank partition function into a product of rank-1 partition functions.

Overview of the Spectral Mean-Field approach

To minimize the approximation error, they employ a clever "diagonal trick." Changing the diagonal of the coupling matrix $A$ only alters the partition function by a known constant factor. The authors exploit this mathematical freedom by using Semi-Definite Programming (SDP) to optimize the diagonal matrix $D$. This optimization shifts the eigenvalues to make the subsequent mean-field approximation as accurate as possible. Interestingly, the SDP used here is mathematically equivalent to the famous relaxation used for the Max-Cut problem, bridging probabilistic inference and classical combinatorial optimization.

Key Results and Performance

The authors evaluated their approach on synthetic GMs (Erdős-Rényi, complete, bipartite, and grid graphs) and real-world benchmark datasets from the UAI 2014 Inference Competition.

Performance and scaling of the spectral approach
  • Robustness in Low-Temperature Regimes: In high-coupling regimes where Belief Propagation (BP) and Mean-Field (MF) approximations exhibit high variance or fail completely, the Spectral approach maintains remarkable accuracy and stability.
  • Near-Exact for Rank-1: For rank-1 models, the proposed dynamic programming algorithm is nearly exact. In contrast, traditional methods like BP and Mini-Bucket Elimination (MBE) output very poor approximations, particularly in anti-ferromagnetic (negative eigenvalue) cases.
  • Competitive Scaling: Despite the theoretical complexity of spectral decomposition and SDP, the algorithm scales practically. Empirically, the SDP solver runs in $O(n^2)$ to $O(n^3)$ time, making it viable for models with thousands of variables.

Limitations and Future Directions

While powerful, the approach has limitations. The FPTAS is only "fully polynomial" if the rank $r$ is constant; as rank increases, complexity grows exponentially, necessitating the mean-field approximation for general models. Additionally, the current framework focuses on pairwise binary GMs (Ising-like models).

Future work aims to extend this spectral framework to higher-order interactions beyond pairwise couplings, adapt it for continuous variable models, and apply it to the estimation of marginal distributions rather than solely the partition function.

Summary updated

Abstract

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 ...
BibTeX
@inproceedings{park2019spectral,
  author = {Sejun Park and Eunho Yang and Se-Young Yun and Jinwoo Shin},
  title = {{Spectral Approximate Inference}},
  booktitle = {International Conference on Machine Learning},
  year = {2019},
  url = {https://openreview.net/forum?id=BJ-uSsW_WB},
}
Figure