A Spectral Approach to Analyzing Belief Propagation for 3-Coloring

Abstract

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 coloring 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 color classes.

References in corpus (1)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems

Cited by in corpus (9)

• Influence maximization in complex networks through optimal percolation
• Spectral redemption: clustering sparse networks
• Statistical physics of inference: Thresholds and algorithms
• Quiet Planting in the Locked Constraint Satisfaction Problems
• Spectral Detection on Sparse Hypergraphs
• On belief propagation guided decimation for random k-SAT
• Decoding from Pooled Data: Sharp Information-Theoretic Bounds
• Spectral partitioning in equitable graphs
• The solution space structure of planted constraint satisfaction problems with growing domains