# Theoretical guarantees for running times of belief propagation methods?

Belief propagation has been shown to be a very powerful method through research in probabilistic graphical models.

However, I don't know anything about BP that's comparable to MCMC methods where we can have fully polynomial randomized approximation schemes (FPRAS) for #P-complete problems.

Could someone point me to some references?

• Versions of belief propagation appear in expander codes and in Alon & Kahale's A spectral technique for coloring random 3-colorable graphs (as well as numerous later papers exploiting their ideas). While that answers your title to some extent, it doesn't answer the body of your question. Commented Nov 2, 2013 at 7:18
• BTW, I didn't get your last sentence. What do you mean by this? "MCMC methods where we can have fully polynomial randomized approximation schemes (FPRAS) for #P-complete problems." Any pointers? Commented Nov 3, 2013 at 21:24
• @Daniel I was looking for solving problems using BP where they have good theoretical guarantees for running time. Commented Nov 4, 2013 at 17:24
• Then I guess you need to change the statement of your problem. I understood different thing. Commented Nov 5, 2013 at 0:55

## 2 Answers

BP and most of its variants are proved to converge on graphs without cycles. When you have cycles they show very strange behavior sometimes. For these cases people have tried different approximations schemes, for example Sherali-Adams, Lovasz-Schrijver, and Lasserre Hierarchies.

See [1] for a comprehensive review of these approximations. Also (Wainwright and Jordan, 2008) includes other class of approximations.

• This is also why survey propagation (a cousin of belief propagation) works so well on solving large random 3-SAT problems. For random factor graphs, locally, the graph looks like it's a tree and so survey propagation can make progress. Commented Nov 4, 2013 at 16:51

Here's a paper where the authors used BP to obtain a fully polynomial-time randomized approximation scheme for the the capacitated minimum-cost network ﬂow problem.