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?

  • 2
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Nov 2 '13 at 7:18
  • 2
    $\begingroup$ 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? $\endgroup$ – Daniel Nov 3 '13 at 21:24
  • $\begingroup$ @Daniel I was looking for solving problems using BP where they have good theoretical guarantees for running time. $\endgroup$ – Tianyang Li Nov 4 '13 at 17:24
  • $\begingroup$ Then I guess you need to change the statement of your problem. I understood different thing. $\endgroup$ – Daniel Nov 5 '13 at 0:55

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, Lovasz-Schrijver, and Lasserre Hierarchies.

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

[1] http://cs.nyu.edu/~dsontag/papers/sontag_phd_thesis.pdf

  • 3
    $\begingroup$ 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. $\endgroup$ – user834 Nov 4 '13 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 flow problem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.