Loopy belief propagation

Loopy belief propagation is the application of belief propagation to graphs that contain cycles. Standard belief propagation is exact on tree-structured graphs, where messages pass from leaves to root and back. On loopy graphs — the graphs that describe real-world systems, from social networks to protein interactions to electrical grids — the algorithm becomes iterative: messages circulate until (hopefully) they converge.

Convergence is not guaranteed. On graphs with strong correlations or tight loops, loopy belief propagation can oscillate indefinitely or converge to incorrect marginals. Yet in practice, it often works surprisingly well, producing accurate approximations even where theory predicts failure. The algorithm\'s empirical success on loopy graphs remains one of the unexplained phenomena of approximate inference.