A new look at survey propagation and its generalizations

ABSTRACT

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.

REFERENCES

• 1: D. Achiloptas and Y. Peres. The threshold for random k-SAT is 2k 2 log 2 -- o(k). In Proceedings of FOCS, pages 223--231, 2003.
• 2: E. Aurell, U. Gordon, and S. Kirkpatrick. Comparing beliefs, surveys, and random walks. Technical report, 2004. URL:http://lanl.arXiv.org/cond-mat/0406217.
• 3: N. Berger, C. Kenyon, E. Mossel, and Y. Peres. Glauber dynamics on trees and hyperbolic graphs. To appear, 2004.
• 4: A. Braunstein, M. Mezard, M. Weigt, and R. Zecchina. Constraint satisfaction by survey propagation. Technical report, 2003. Preprint at URL:http://lanl.arXiv.org/cond-mat/0212451.
• 5: A. Braunstein, M. Mézard, and R. Zecchina. Survey propagation: an algorithm for satisfiability. Technical report, 2003. Preprint at URL:http://lanl.arXiv.org/cs.CC/0212002.
• 6: A. Braunstein and R. Zecchina. Survey propagation as local equilibrium equations. Technical report, 2004. Preprint at URL:http://lanl.arXiv.org/condmat/0312483.
• 7: V. Chvatal and B. Reed. Mick gets some (the odds are on his side). In Proceedings of 33rd FOCS, Pittsburgh Pennsylvania, 1992.
• 8: Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
• 9: W. F. de la Vega. On random 2-sat. Unpublushed manuscript., 1992.
• 10: Olivier Dubois , Yacine Boufkhad , Jacques Mandler, Typical random 3-SAT formulae and the satisfiability threshold, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.126-127, January 09-11, 2000, San Francisco, California, United States
• 11: S. Franz and M. Leone. Replica bounds for optimization problems and diluted spin systems. J. Stat. Phys., 111:535, 2003. URL:http://lanl.arXiv.org/condmat/0208280.
• 12: E. Friedgut. Neccesary and sufficient conditions for sharp threhsolds of graph properties and the k-problem. J. Amer. Math. Soc., 12:1017--1054, 1999.
• 13: A. Goerdt. A remark on random 2-sat. J. Computer System and Sciences, 53:469--486, 1996.
• 14: Alexis C. Kaporis , Lefteris M. Kirousis , Efthimios G. Lalas, The Probabilistic Analysis of a Greedy Satisfiability Algorithm, Proceedings of the 10th Annual European Symposium on Algorithms, p.574-585, September 17-21, 2002
• 15: S. Kirkpatrick. On survey propagation. Personal communication, 2004.
• 16: E. Maneva, E. Mossel, and M. J. Wainwright. A new look at survey propagation and its generalizations. Technical report, Department of Statistics, UC Berkeley, September 2004. URL: https://lanl.arXiv.org/abs/cs.CC/0409012.
• 17: F. Martinelli. Lectures on Glauber dynamics for discrete spin models. In Lectures on probability theory and statistics (Saint-Flour, 1997), volume 1717 of Lecture Notes in Math., pages 93--191. Springer, Berlin, 1999.
• 18: M. Mezard, G. Parisi, and R. Zecchina. Analytic and algorithmic solution of random satisfiability problems. Science, 297, 812, 2002. (Scienceexpress published online 27-June-2002; 10.1126/science.1073287).
• 19: M. Mezard and R. Zecchina. Random k-satisfiability: from an analytic solution to an efficient algorithm. Phys. Rev. E, 66, 2002.
• 20: R. Monasson and R. Zecchina. Statistical mechanics of the random k-satisfiability model. Phys. Rev. E., 3:1357--1370, 1997.
• 21: D. Panchenko and M. Talagrand. Bounds for diluted mean field spin glass models. 2004. Preprint at URL:http://lanl.arXiv.org/math.PR/0405357.
• 22: T. Richardson and R. Urbanke. The capacity of low-density parity check codes under message-passing decoding. IEEE Trans. Info. Theory, 47:599--618, February 2001.
• 23: J. Rosenthal, J. Plotkin, and J. Franco. The probability of pure literals. Journal of Computational Logic, 9:501--513, 1999.
• 24: P. Svenson and M. G. Nordahl. Relaxation in graph coloring and satisfiability problems. Phys. Rev. E., 59:3983--3999, 1999.
• 25: S. Tatikonda and M. I. Jordan. Loopy belief propagation and Gibbs measures. In Uncertainty in Artificial Intelligence (UAI), Proceedings of the Eighteenth Conference, 2002.
• 26: M. J. Wainwright and M. I. Jordan. Graphical models, exponential families, and variational methods. Technical report, UC Berkeley, Department of Statistics, No. 649, 2003. Preprint at URL:http://www.stat.berkeley.edu/techreports/index.html.
• 27: Jonathan S. Yedidia , William T. Freeman , Yair Weiss, Understanding belief propagation and its generalizations, Exploring artificial intelligence in the new millennium, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003