Survey Propagation beyond Constraint Satisfaction Problems

Christopher Srinivasa, Siamak Ravanbakhsh, Brendan J. FreyAISTATS 2016 · OpenReview

Abstract

Survey propagation (SP) is a message passing procedure that attempts to model all the fixed points of Belief Propagation (BP), thereby improving BP’s approximation in loopy graphs where BP’s assumptions fail. This paper extends SP to general probabilistic inference in binary pairwise graphical models by using a clever approximation scheme involving Fast Fourier Transforms (FFTs), making it computationally efficient and superior to standard BP in complex, loopy settings.

Introduction

In probabilistic graphical models, marginalization is a fundamental task often addressed by Belief Propagation (BP). While exact on trees, BP frequently struggles on loopy graphs, failing to converge or becoming trapped in suboptimal fixed points. Survey Propagation (SP) was developed to "survey" the landscape of these BP fixed points. However, its application has been largely restricted to Constraint Satisfaction Problems (CSPs) where messages are discrete. In general models like the Ising model, SP messages become continuous and intractable. This work bridges this gap, extending SP to general binary pairwise graphical models.

Methodology

The authors propose an efficient approximation for SP in binary pairwise models, specifically the Ising model, through three technical innovations:

  1. Logarithmic Quantization: Continuous distributions are quantized into $K$ discrete bins based on the log-ratio of BP messages.
  2. FFT-based Convolution: Variable node updates, which typically have exponential complexity $O(K^D)$, are computed as multiplications in the frequency domain using Fast Fourier Transforms (FFTs). This reduces complexity to $O(DK \log(DK))$.
  3. Variable-Factor Subroutines: Specific algorithms manage message passing between variable and factor nodes to track locally consistent BP fixed points.
Comparison of the factor graph structures for Belief Propagation (BP) and Survey Propagation (SP).

Experimental Results

The method was evaluated on various Ising model topologies, including fully connected, bipartite, and grid graphs, with varying coupling strengths (attractive, repulsive, and mixed).

Capturing Multiple Fixed Points

A key insight is SP's ability to capture the "dynamical phase" where the probability space breaks into clusters. While BP typically selects a single cluster, SP models the distribution across all clusters. This is particularly evident as coupling strength $J$ increases, where the belief distribution in SP spreads to reflect multiple potential solutions.

Belief distributions for BP and SP across different coupling strengths J. As J increases, SP captures a wider distribution of beliefs, reflecting multiple BP fixed points.

Performance and Convergence

SP achieved significantly lower Mean Absolute Error (MAE) than BP in high-coupling (non-trivial) settings. Furthermore, SP demonstrated robust convergence in cases where Loopy BP oscillated. The accuracy of SP closely matched Gibbs Sampling but with significantly lower computational cost. Increasing the number of bins ($K$) consistently improved accuracy, showing the stability of the approximation.

Conclusion and Future Work

This work demonstrates that FFT-based SP is a viable and efficient tool for general machine learning tasks beyond CSPs. Future research includes extending the framework to multi-valued variables and applying it to Maximum A Posteriori (MAP) inference and the training of Boltzmann Machines, which currently rely on slower MCMC methods.

Summary updated

Abstract

Survey propagation (SP) is a message passing procedure that attempts to model all the fixed points of Belief Propagation (BP), thereby improving BP’s approximation in loopy graphs where BP’s assump...
BibTeX
@inproceedings{srinivasa2016survey,
  author = {Christopher Srinivasa and Siamak Ravanbakhsh and Brendan J. Frey},
  title = {{Survey Propagation beyond Constraint Satisfaction Problems}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2016},
  url = {https://openreview.net/forum?id=JdIYbVsC5MR},
}
Figure