Convergence analysis of a survey propagation algorithm
Pages 9239 - 9252
Abstract
The survey propagation algorithm is the most effective information propagation algorithm for solving the 3-SAT problem. It can effectively solve the satisfiability problem when it converges. However, when the factor graph structure is complex, the algorithm often does not converge and the solution fails. In order to give a theoretical explanation to this phenomenon and to analyze the convergence of the survey propagation algorithm effectively, a connected treewidth model of the propositional formula was constructed by using the connected tree decomposition method, and the connected treewidth of the factor graph was calculated. The relationship between the connected treewidth and the convergence of the survey propagation algorithm is established, and the convergence judgment condition of the survey propagation algorithm based on the connected tree width is given. Through experimental analysis, the results show that the method is effective, which is of great significance for analyzing the convergence analysis of other information propagation algorithms.
References
[1]
Freuder E.C. and Mackworth A.K., Constraint satisfaction: An emerging paradigm[M]//Foundations of Artificial Intelligence, Elsevier 2 (2006), 13–27.
[2]
Kaporis A.C., Kirousis L.M. and Lalas E.G., The probabilistic analysis of a greedy satisfiability algorithm[J], Random Structures & Algorithms 28(4) (2006), 444–480.
[3]
Díaz J., Kirousis L., Mitsche D. et al. On the satisfiability threshold of formulas with three literals per clause[J], Theoretical Computer Science 410(30–32) (2009), 2920–2934.
[4]
Moskewicz M.W., Madigan C.F., Zhao Y. et al. Chaff: Engineering an efficient SAT solver[C]//Proceedings of the 38th annual Design Automation Conference, (2001), 530–535.
[5]
Aurell E., Gordon U. and Kirkpatrick S., Comparing beliefs, surveys, and random walks[J], Advances in Neural Information Processing Systems (2004), 17.
[6]
Marino R., Parisi G. and Ricci-Tersenghi F., The backtracking survey propagation algorithm for solving random K-SAT problems[J], Nature Communications 7(1) (2016), 1–8.
[7]
Maneva E., Mossel E. and Wainwright M.J., A new look at survey propagation and its generalizations[J], Journal of the ACM (JACM) 54(4) (2007) 17–es.
[8]
Fu Wang, Yunren Zhou and Li Ye, Ant Colony Algorithm Combined with Survey Propagation for Satisfiability Problem[J], Computer Science 39(04) (2012), 227–231.
[9]
Battaglia D., Kolář M. and Zecchina R., Minimizing energybelow the glass thresholds[J], Physical Review E 70(3) (2004), 036107.
[10]
Chieu W.S., Lee, Relaxed Survey Propagation for The Weighted Maximum Satisfiability Problem[J], Jair Org 36 (2009), 229–266.
[11]
Marino R., Learning from Survey Propagation: a Neural Network for MAX-E-3-SAT[J], Machine Learning: Science and Technology 2021.
[12]
Meng X. and Chen T., Event based agreement protocols for multi-agent networks [J], Automatica 49(7) (2013), 2125–2132.
[13]
Shao Ming, Li Guanghui and Li Xiaowei, Survey propagation algorithm for SAT and its performance dominated by step length[J], Chinese Journal of Computers 2005(05) (2005), 849–855.
[14]
Wang Xiaofeng, Xu Daoyun, Jiang Jiulei, et al. Sufficient conditions for convergence of the survey propagation algorithm[J], Scientia Sinica Informationis 47(12) (2017), 1646–1661.
[15]
Liang Chen, Wang Xiaofeng, Liu Zilin, Lu Lei, et al. Convergence analysis of survey propagation algorithm based on K-dimensional structure entropy [J], Application Research of Computers 39(05) (2022), 1432–1436.
[16]
Freuder Eugene C., A sufficient condition for backtrack-free search, J. ACM 29(1) (1982), 24–32.
[17]
Robertson N., Seymour P.D. and Graph X., Minors, Obstructions to tree-decomposition[J], Journal of Combinatorial Theory, Series B 52 (1991), 153–190.
[18]
Chen H., Quantified constraint satisfaction and bounded treewidth[C]//ECAI, 16 (2004), 161.
[19]
Krishnamurthy S. and Sahoo S., Balanced k-satisfiability and biased random k-satisfiability on trees[J], Physical Review E 87(4) (2013), 042130.
[20]
Lei Ying and Xu Daoyun, Algorithm of Graph and Its Application[J], Computer Science 47(05) (2020), 51–58.
[21]
Jégou P., Ndiaye S.N. and Terrioux C., Computing and exploiting tree-decompositions for solving constraint networks[C]//International Conference on Principles and Practice of Constraint Programming, Springer, Berlin, Heidelberg (2005), 777–781.
[22]
Jégou P. and Terrioux C., Bag-Connected Tree-Width: A New Parameter for Graph Decomposition[C]//ISAIM, 2014.
[23]
Jégou P. and Terrioux C., Tree-decompositions with connected clusters for solving constraint networks[C]//International Conference on Principles and Practice of Constraint Programming. Springer, Cham (2014), 407–423.
[24]
Bodlaender H.L., A linear-time algorithm for finding tree-decompositions of small treewidth[J], SIAM Journal on Computing 25(6) (1996), 1305–1317.
[25]
Stefan A., Derek G.C., Andrzej P. et al. Complexity of finding embeddings in a k-tree[J], SIAM Journal on Algebraic Discrete Methods 8(2) (1987), 277–284.
[26]
Weiss Y., Correctness of local probability propagation in graphical models with loops[J], Neural Computation 12(1) (2000), 1–41.
[27]
Diestel R. and Müller M., Connected tree-width[J], Combinatorica 38(2) (2018), 381–398.
[28]
Mescoff G., Paul C. and Thilikos D.M., A polynomial time algorithm to compute the connected treewidth of a series– parallel graph[J], Discrete Applied Mathematics 312 (2022), 72–85.
[29]
Braunstein A., Mezard M. and Zecchina R., Survey propagation: an algorithm for satisfiability, Random Structures Algorithms 27 (2005), 201–226.
Recommendations
Semismooth Karush-Kuhn-Tucker Equations and Convergence Analysis of Newton and Quasi-Newton Methods for Solving these Equations
There are several forms of systems of nonsmooth equations which are equivalent to the Karush-Kuhn-Tucker KKT system of a nonlinearly constrained optimization problem NLP. If the NLP is twice continuously differentiable and the Hessian functions of its ...
On the convergence of descent methods for monotone variational inequalities
Recently, Zhu and Marcotte (1993) established the convergence of a modified descent algorithm for monotone variational inequalities. Using algorithmic equivalence results due to Patriksson (1993) and Larsson and Patriksson (1994), we show that this ...
Convergence Analysis of Finite Volume Scheme for Nonlinear Tensor Anisotropic Diffusion in Image Processing
In this article we design the semiimplicit finite volume scheme for coherence enhancing diffusion in image processing and prove its convergence to the weak solution of the problem. The finite volume methods are natural tools for image processing ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© 2023 – IOS Press. All rights reserved.
Publisher
IOS Press
Netherlands
Publication History
Published: 01 January 2023
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 09 Feb 2025