Survey Propagation as local equilibrium equations

Abstract

It has been shown experimentally that a decimation algorithm based on Survey Propagation (SP) equations allows to solve efficiently some combinatorial problems over random graphs. We show that these equations can be derived as sum-product equations for the computation of marginals in an extended space where the variables are allowed to take an additional value -- $\ast$ -- when they are not forced by the combinatorial constraints. An appropriate ``local equilibrium condition'' cost/energy function is introduced and its entropy is shown to coincide with the expected logarithm of the number of clusters of solutions as computed by SP. These results may help to clarify the geometrical notion of clusters assumed by SP for the random K-SAT or random graph coloring (where it is conjectured to be exact) and helps to explain which kind of clustering operation or approximation is enforced in general/small sized models in which it is known to be inexact.

13 pages, 3 figures

References in corpus (8)

• Broken Replica Symmetry Bounds in the Mean Field Spin Glass Model
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Survey propagation: an algorithm for satisfiability
• Rigorous decimation-based construction of ground pure states for spin glass models on random lattices
• On local equilibrium equations for clustering states
• Clustering analysis of the ground-state structure of the vertex-cover problem
• Constraint Satisfaction by Survey Propagation
• On the survey-propagation equations for the random K-satisfiability problem

Cited by in corpus (39)

• Critical phenomena in complex networks
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Phase Transitions in the Coloring of Random Graphs
• Sufficient conditions for convergence of the Sum-Product Algorithm
• Survey propagation: an algorithm for satisfiability
• Loop series for discrete statistical models on graphs
• Focused Local Search for Random 3-Satisfiability
• Generalization of the cavity method for adiabatic evolution of Gibbs states
• The asymptotic $k$-SAT threshold
• Belief-Propagation for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs with Integer Solutions
• Constraint satisfaction problems with isolated solutions are hard
• The backtracking survey propagation algorithm for solving random K-SAT problems
• On the exactness of the cavity method for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs
• Neural Enhanced Belief Propagation on Factor Graphs
• Relaxed Survey Propagation for The Weighted Maximum Satisfiability Problem
• The stochastic matching problem
• Comparing Beliefs, Surveys and Random Walks
• Biased landscapes for random Constraint Satisfaction Problems
• The large deviations of the whitening process in random constraint satisfaction problems
• From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy
• Stochastic optimization by message passing
• The theoretical capacity of the Parity Source Coder
• On the Atypical Solutions of the Symmetric Binary Perceptron
• A New Look at Survey Propagation and its Generalizations
• Spin glass phase transitions in the random feedback vertex set problem
• Clustering of solutions in hard satisfiability problems
• Biased measures for random Constraint Satisfaction Problems: larger interaction range and asymptotic expansion
• Convergence and Accuracy Analysis for A Distributed Static State Estimator based on Gaussian Belief Propagation
• Lower Bounds on the Rate-Distortion Function of Individual LDGM Codes
• The solution space structure of planted constraint satisfaction problems with growing domains
• Cutting-Plane Algorithms and Solution Whitening for the Vertex-Cover Problem
• Aspects of Statistical Physics in Computational Complexity
• Survey Propagation Revisited
• Perturbed Message Passing for Constraint Satisfaction Problems
• On the Solution-Space Geometry of Random Constraint Satisfaction Problems
• Revisiting Algebra and Complexity of Inference in Graphical Models
• Pruning Processes and a New Characterization of Convex Geometries
• On the Satisfiability Threshold and Clustering of Solutions of Random 3-SAT Formulas
• Equivariant Neural Network for Factor Graphs