{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,22]],"date-time":"2025-11-22T16:51:48Z","timestamp":1763830308721},"reference-count":20,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2009,3,24]],"date-time":"2009-03-24T00:00:00Z","timestamp":1237852800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2009,11]]},"abstract":"<jats:p>Belief propagation (BP) is a message-passing algorithm that computes the exact marginal distributions at every vertex of a graphical model without cycles. While BP is designed to work correctly on trees, it is routinely applied to general graphical models that may contain cycles, in which case neither convergence, nor correctness in the case of convergence is guaranteed. Nonetheless, BP has gained popularity as it seems to remain effective in many cases of interest, even when the underlying graph is \u2018far\u2019 from being a tree. However, the theoretical understanding of BP (and its new relative survey propagation) when applied to CSPs is poor.<\/jats:p><jats:p>Contributing to the rigorous understanding of BP, in this paper we relate the convergence of BP to spectral properties of the graph. This encompasses a result for random graphs with a \u2018planted\u2019 solution; thus, we obtain the first rigorous result on BP for graph colouring in the case of a complex graphical structure (as opposed to trees). In particular, the analysis shows how belief propagation breaks the symmetry between the 3! possible permutations of the colour classes.<\/jats:p>","DOI":"10.1017\/s096354830900981x","type":"journal-article","created":{"date-parts":[[2009,3,24]],"date-time":"2009-03-24T10:23:16Z","timestamp":1237890196000},"page":"881-912","source":"Crossref","is-referenced-by-count":18,"title":["A Spectral Approach to Analysing Belief Propagation for 3-Colouring"],"prefix":"10.1017","volume":"18","author":[{"given":"AMIN","family":"COJA-OGHLAN","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ELCHANAN","family":"MOSSEL","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"DAN","family":"VILENCHIK","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2009,3,24]]},"reference":[{"key":"S096354830900981X_ref2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794270248"},{"key":"S096354830900981X_ref1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(1999010)14:1<63::AID-RSA3>3.0.CO;2-7"},{"key":"S096354830900981X_ref20","unstructured":"[20] Yamamoto M. and Watanabe O. (2007) Belief propagation and spectral methods. Report C\u2013248, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology."},{"key":"S096354830900981X_ref13","unstructured":"[13] Luby M. , Mitzenmacher M. , Shokrollahi M. A. and Spielman D. (1998) Analysis of low density parity check codes and improved designs using irregular graphs. In Proc. 30th ACM Symposium on the Theory of Computing, pp. 249\u2013258."},{"key":"S096354830900981X_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-7152(02)00054-8"},{"key":"S096354830900981X_ref7","unstructured":"[7] Brightwell G. R. and Winkler P. (2002) Random colorings of a Cayley tree. In Contemporary Combinatorics, Vol. 10 of Bolyai Society Mathematical Studies, J\u00e1nos Bolyai Math. Soc., pp. 247\u2013276."},{"key":"S096354830900981X_ref19","doi-asserted-by":"crossref","unstructured":"[19] Weitz D. (2006) Counting independent sets up to the tree threshold. In Proc. 38th Annual ACM Symposium on the Theory of Computing, pp. 140\u2013149.","DOI":"10.1145\/1132516.1132538"},{"key":"S096354830900981X_ref10","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"S096354830900981X_ref17","doi-asserted-by":"publisher","DOI":"10.1109\/18.910578"},{"key":"S096354830900981X_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/s004930200010"},{"key":"S096354830900981X_ref18","unstructured":"[18] Tatikonda S. and Jordan M. I. (2002) Loopy belief propagation and Gibbs measures. In Uncertainty in Artificial Intelligence (UAI): Proc. 18th Conference."},{"key":"S096354830900981X_ref4","volume-title":"Computational Complexity and Statistical Physics","author":"Braunstein","year":"2005"},{"key":"S096354830900981X_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-006-0029-7"},{"key":"S096354830900981X_ref5","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20057"},{"key":"S096354830900981X_ref15","unstructured":"[15] Maneva E. , Mossel E. and Wainwright M. (2005) A new look at survey propagation and its generalizations. In Proc. 16th ACM\u2013SIAM Symposium on Discrete Algorithms, pp. 1089\u20131098."},{"key":"S096354830900981X_ref9","doi-asserted-by":"crossref","unstructured":"[9] Feige U. , Mossel E. and Vilenchik D. (2006) Complete convergence of message passing algorithms for some satisfiability problems. In Random 2006, Vol. 4110 of Lecture Notes in Computer Science, pp. 339\u2013350.","DOI":"10.1007\/11830924_32"},{"key":"S096354830900981X_ref6","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.68.036702"},{"key":"S096354830900981X_ref16","volume-title":"Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference","author":"Pearl","year":"1988"},{"key":"S096354830900981X_ref12","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0703685104"},{"key":"S096354830900981X_ref14","doi-asserted-by":"publisher","DOI":"10.1109\/18.910575"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S096354830900981X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,30]],"date-time":"2019-04-30T09:31:26Z","timestamp":1556616686000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S096354830900981X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,3,24]]},"references-count":20,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2009,11]]}},"alternative-id":["S096354830900981X"],"URL":"https:\/\/doi.org\/10.1017\/s096354830900981x","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,3,24]]}}}