logo

SCIENTIA SINICA Informationis, Volume 47, Issue 12: 1646-1661(2017) https://doi.org/10.1360/N112016-00248

Sufficient conditions for convergence of the survey propagation algorithm

More info
  • ReceivedOct 20, 2016
  • AcceptedDec 12, 2016
  • PublishedSep 5, 2017

Abstract

Message propagation algorithms are very effective at finding satisfying assignments for SAT instances, and hard regions of a random SAT have become narrower. However, message propagation algorithms do not always converge for some random SAT instances. Unfortunately, a rigorous theoretical proof of this phenomenon is still lacking. The survey propagation (SP) algorithm is very effective at solving SAT instances, and a theoretical analysis of SP is very important in designing other message passing algorithms. Through this study, we derived the sufficient conditions for convergence of SP with extending message [0,~1] to message $(-\infty,\infty)$. Finally, the experiment results show that the conditions for the convergence of SP are very effective in random 3-SAT instances.


Funded by

国家自然科学基金(61462001,61650206,61563001,61402017)

计算机应用技术自治区重点学科建设基金


References

[1] Martin D, Alan F, Michael M. A probabilistic analysis of randomly generated binary constraint satisfaction. Theory Comput Sci, 2003, 290: 1815--1828. Google Scholar

[2] Creignou N, Eaude H. The SAT-UNSAT transition for random constraint satisfaction problems. Discrete Math, 2009, 309: 2085--2099. Google Scholar

[3] Martin O C, Monasson R, Zecchina R. Statistical mechanics methods and phase transitions in optimization. Theory Comput Sci, 2001, 265: 3--67. Google Scholar

[4] Kirkpatrick S, Selman B. Critical behavior in the satisfiability of random Boolean formulae. Science, 1994, 264: 1297--1301. Google Scholar

[5] Mertens S, Mezard M, Zecchina R. Threshold values of random k-SAT from the cavity method. Random Structure Algorithms, 2006, 28: 340--373. Google Scholar

[6] Kaporis A, Kirousis L, Lalas E. The probabilistic analysis of a greedy satisfiability algorithm. Random Structures Algorithms, 2006, 28: 444--480. Google Scholar

[7] Dıaz J, Kirousis L, Mitsche D, et al. On the satisfiability threshold of formulas with three literals per clause. Theory Comput Sci, 2009, 410: 2920--2934. Google Scholar

[8] Moskewicz M W, Madigan C F, Zhao Y. Chaff: engineering an efficient SAT solver. In: Proceedings of the 38th Annual Design Automation Conference. New York: ACM, 2001. 530--535. Google Scholar

[9] Aurell E, Gordon U, Kirkkpatrick S. Comparing beliefs, surveys, and random walks. In: Proceedings of the 17th International Conference on Neural Information Processing Systems, Vancouver, 2004. 49--56. Google Scholar

[10] Braunstein A, Mezard M, Zecchina R. Survey propagation: an algorithm for satisfiability. Random Structures Algorithms, 2005, 27: 201--226. Google Scholar

[11] Maneva E, Mossel E, Wainwright M. A new look at survey propagation and its generalizations. J ACM, 2007, 54: 1089--1098. Google Scholar

[12] Yedidia J S, Freeman W T, Weiss Y. Understanding belief propagation and its generalizations. Artif Intell, 2003, 8: 239--269. Google Scholar

[13] Braunstein A, Zecchina R. Survey and belief propagation on random k-SAT. In: Theory and Applications of Satisfiability Testing. Berlin: Springer, 2004. 519--528. Google Scholar

[14] Xu K, Li W. Exact phase transitions in random constraint satisfaction problems. J Artif Intell Res, 2000, 12: 93--103. Google Scholar

[15] Xu K, Li W. Many hard examples in exact phase transitions. Theory Comput Sci, 2006, 355: 291--302. Google Scholar

[16] Xu K, Boussemart F, Hemery F, et al. Random constraint satisfaction: easy generation of hard instances. Artif Intell, 2007, 171: 514--534. Google Scholar

[17] Zhao C Y, Zheng Z M. A belief-propagation algorithm based on variable entropy for constraint satisfaction problems. Sci Sin Inform, 2012, 42: 1170--1180. Google Scholar

[18] Yin M H, Zhou J P, Sun J G, et al. Heuristic survey propagation algorithm for solving QBF problem. J Softw, 2011, 22: 1538--1550. Google Scholar

[19] Ravanbakhsh S, Greiner R. Perturbed message passing for constraint satisfaction problems,. arXiv Google Scholar

[20] Chieu H L, Lee W S. Relaxed survey propagation for the weighted maximum satisfiability problem. J Artif Intell Res, 2009, 36: 229--266. Google Scholar

[21] Bayati M, Shah D, Sharma M. Max product for maximum weight matching: convergence, correctness, and LP duality. IEEE Trans Inf Theory, 2007, 54: 1241--1251. Google Scholar

[22] Coja-Oghlan A, Mossel E, Vilenchik D. A spectral approach to analyzing belief propagation for 3-colouring. Comb Probab Comput, 2009, 18: 881--912. Google Scholar

[23] Gamarnik D, Shah D, Wei Y. Belief propagation for min-cost network flow: convergence and correctness. Oper Res, 2012, 60: 410--428. Google Scholar

[24] Sanghavi S, Malioutov D M, Willsky A S. Belief propagation and LP relaxation for weighted matching in general graphs. IEEE Trans Inf Theory, 2011, 57: 2203--2212. Google Scholar

[25] Sanghavi S, Shah D, Willsky A S. Message passing for maximum weight independent set. IEEE Trans Inf Theory, 2009, 55: 4822--4834. Google Scholar

[26] Kschischang F, Frey B, Loeliger H. Factor graph and the sum-product algorithm. Inform Theory, 2001, 47: 498--519. Google Scholar

[27] Weiss Y. Correctness of local probability propagation in graphical models with loops. Neural Comput, 2000, 12: 1--41. Google Scholar

[28] Weiss Y, Freeman W T. Correctness of belief propagation in Gaussian graphical models of arbitrary topology. Neural Comput, 2001, 13: 2173--2200. Google Scholar

[29] Tatikonda S C, Jordan M I. Loopy belief propagation and Gibbs measure. In: Proceedings of the 18th Annual Conference on Uncertainty in Artificial Intelligence, Alberta, 2002. 493--500. Google Scholar

[30] Heskes T. On the uniqueness of loopy belief propagation fixed points. Neural Comput, 2004, 16: 2379--2413. Google Scholar

[31] Ihler A T. Loopy belief propagation: convergence and effects of message errors. Mach Learn Res, 2005, 6: 905--936. Google Scholar

[32] Mooij J M, Kappen H J. Sufficient conditions for convergence of the sum-product algorithm. IEEE Trans Inf Theory, 2007, 53: 4422--4437. Google Scholar

[33] Shi X Q, Schonfeld D, Tuninetti D. Message error analysis of loopy belief propagation for the sum-product algorithm. Comput Inf Sci, 2010, 1009: 1--30. Google Scholar

[34] Brunsch T, Cornelissen K, Manthey B, et al. Smoothed analysis of BP for minimum cost flow and matching. J Graph Algorithms Appl, 2013, 17: 647--670. Google Scholar

[35] Norshams N, Wainwright M J. Stochastic belief propagation: a low complexity alternative to the sum product algorithm. IEEE Trans Inf Theory, 2013, 59: 1981--2000. Google Scholar

[36] Feige U, Mossel E, Vilenchik D. Complete convergence of message passing algorithms for some satisfiability problems. Theory Comput, 2013, 9: 617--651. Google Scholar

[37] Wang X F, Xu D Y, Wei L. Convergence of warning propagation algorithms for random satisfiable instances. J Softw, 2013, 24: 1--11. Google Scholar

[38] Wang X F, Xu D Y. Sufficient conditions for convergence of the warning propagation algorithm. J Softw, 2016, 27: 3003--3013. Google Scholar

[39] Wang X F, Xu D Y. Convergence of the belief propagation algorithm for RB model instances. J Softw, 2016, 27: 2712--2724. Google Scholar

[40] Dieudonne J. Foundations of Modern Analysis. New York: Academic Press, 1960. Google Scholar

  • Figure 1

    Factor graph

  • Figure 2

    Part of factor graph

  • Figure 3

    Properties change of random 3-SAT instance with parameter $\alpha~=\frac{m}{n}$. (a) The phase transition of satisfaction; (b) the hardness of solving random 3-SAT instance

  • Figure 4

    (Color online) Properties change of convergence (a) and time (b) of SP with parameter $\alpha~=\frac{m}{n}$.

  • Figure 5

    (Color online) The change of spectral radius $\rho$ with parameter $\alpha~=\frac{m}{n}$

  •   

    Algorithm 1 SP algorithm

    Require:the factor graph of formula $F$; a maximal number of iterations $t_{\rm~max}$; a requested precision $\varepsilon$.

    Output:unconvergence if SP has not converged after $t_{\rm~max}$ sweeps. If it has converged: the messages $\eta^*~_{a~\to~i}$.

    At time $t=0$: For every edge $a~\to~i$ of the factor graph, randomly initialize the messages $\eta~_{a~\to~i}(t=0)\in~[0,1]$;

    For $t=0$ to $t=t_{\rm~max}$:2.1. Sweep the set of edges in a random order, and update sequentially the warning on all the edges of the graph, generating the values $\eta~_{a~\to~i}(t)$, using subroutine SP-UPDATE;2.2. If $|\eta~_{a~\to~i}(t)-\eta~_{a~\to~i}(t-1)|<\varepsilon$ on all the edges, the iteration has converged and generated $\eta^*~_{a~\to~i}=\eta~_{a~\to~i}(t)$: go to 3;

    If $t==t_{\rm~max}$ return UN-CONVERGENCE. If $t<t_{\rm~max}$ return the set of fixed point survey $\eta^*~~_{a~\to~i}=\eta~_{a~\to~i}(t)$.

  •   

    Algorithm 2 Subroutine SP-UPDATE ($\eta~_{a~\to~i}$)

    Require:set of all messages arriving onto each variable node $j~\in~V(a)\backslash~i$.

    Output:new value for the message $\eta~_{a~\to~i}$.

    For every $j\in~V(a)\verb|\|i$, compute the three numbers $\Pi^u_{j~\to~a}$, $\Pi^s_{j~\to~a}$, $\Pi^0_{j~\to~a}$; If a set like $V^{s}_{a}(j)$ is empty, the corresponding product takes value 1 by definition;

    Using these numbers, compute and return the new survey $\eta~_{a~\to~i}$.

  •   

    Algorithm 3 SID algorithm

    Require:the factor graph of formula $F$; a maximal number of iterations $t_{\rm~max}$; a requested precision $\varepsilon$.

    Output:one assignment which satisfies all clauses, or SP UN-CONVERGENCE, or probably UNSAT.

    Random initial condition for the surveys;

    Run SP. If SP does not converge, return SP UN-CONVERGENCE and stop. If SP converges, use the fixed-point surveys $\eta^*_{a~\to~i}$ in order to:

    Decimate: 3.1. If non-trivial surveys $(\eta~\ne~0)$ are found, then(a) Evaluate, for each variable node $i$, the three `biases $\{W^+_{i},W^-_{i},W^0_{i}\}$;(b) Fix the variable with the largest $|W^+_{i}-W^-_{i}|$ to the value $x_{i}=1$ if $|W^+_{i}>W^-_{i}|$, to the value $x_{i}=0$ if$|W^+_{i}<W^-_{i}|$. Clean the graph;3.2. If all surveys are trivial $(\eta~=~0)$, then output the simplified sub-formula and run on it a local search process (e.g., WALKSAT);

    If the problem is solved completely by unit clause propagation, then output SAT and stop. If no contradiction is found then continue the decimation process on the smaller problem, go to 1, else stop.

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1       京公网安备11010102003388号