The Library
A spectral approach to analysing belief propagation for 3-colouring
Tools
Tools
Tools
Coja-Oghlan, Amin, Mossel, Elchanan and Vilenchik, Dan (2009) A spectral approach to analysing belief propagation for 3-colouring. Combinatorics, Probability and Computing, Vol.18 (No.6). pp. 881-912. doi:10.1017/S096354830900981X ISSN 0963-5483.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1017/S096354830900981X
Abstract
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 ‘far’ from being a tree. However, the theoretical understanding of BP (and its new relative survey propagation) when applied to CSPs is poor.
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 ‘planted’ 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.
| Item Type: | Journal Article | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
| Journal or Publication Title: | Combinatorics, Probability and Computing | ||||
| Publisher: | Cambridge University Press | ||||
| ISSN: | 0963-5483 | ||||
| Official Date: | 2009 | ||||
| Dates: |
|
||||
| Volume: | Vol.18 | ||||
| Number: | No.6 | ||||
| Page Range: | pp. 881-912 | ||||
| DOI: | 10.1017/S096354830900981X | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
