A new look at survey propagation and its generalizations

By Elitza N. Maneva, Elchanan Mossel, Martin J. Wainwright. 2004

166 citations recorded by the source corpus.

We study the survey propagation algorithm [19, 5, 4], which is an iterative technique that appears to be very effective in solving random k-SAT problems even with densities close to threshold. We first describe how any SAT formula can be associated with a novel family of Markov random fields (MRFs), parameterized by a real number ρ. We then show that applying belief propagation---a well-known "message-passing technique---to this family of MRFs recovers various algorithms, ranging from pure survey propagation at one extreme (ρ = 1) to standard belief propagation on the uniform distribution over SAT assignments at the other extreme (ρ = 0). Configurations in these MRFs have a natural interpretation as generalized satisfiability assignments, on which a partial order can be defined. We isolate cores as minimal elements in this partial ordering, and prove that any core is a fixed point of survey propagation. We investigate the associated lattice structure, and prove a weight-preserving identity that shows how any MRF with p > 0 can be viewed as a "smoothed" version of the naive factor graph representation of the k-SAT problem (p = 0). Our experimental results show that message-passing on our family of MRFs is most effective for values of ρ ≠ 1 (i.e., distinct from survey propagation); moreover, they suggest that random formulas may not typically possess non-trivial cores. Finally, we isolate properties of Gibbs sampling and message-passing algorithms that are typical for an ensemble of k-SAT problems. We prove that the space of cores for random formulas is highly disconnected, and show that for values of p sufficiently close to one, either the associated MRF is highly concentrated around the all-star assignment, or it has exponentially small conductance. Similarly, we prove that for p sufficiently close to one, the all-star assignment is attractive for message-passing when analyzed in the density-evolution setting.

Subfields: Artificial Intelligence, Computer Networks and Communications, Molecular Biology

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Molecular Biology

Citations in the corpus

Graphical Models, Exponential Families, and Variational Inference (2008, methodology): “Survey propagation turns out to be an instance of the sum-product or belief propagation algorithm, but as applied to an alternative graphical model for satisfiability problems [38, 159].”