<p>Here's a <a href="http://web.mit.edu/devavrat/www/OR-BP-Preprint.pdf">paper</a> where the authors used BP to obtain a fully polynomial-time randomized approximation scheme for the the capacitated minimum-cost network ﬂow problem.</p>

CC BY-SA 3.0
2013-11-04T17:23:05.890Z
2013-11-04T17:23:05.890Z
Tianyang Li
<p>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. </p>

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

<p>[1] <a href="http://cs.nyu.edu/~dsontag/papers/sontag_phd_thesis.pdf">http://cs.nyu.edu/~dsontag/papers/sontag_phd_thesis.pdf</a> </p>

CC BY-SA 3.0
2013-11-04T16:51:15.577Z
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.
user834
CC BY-SA 3.0
2013-11-03T21:23:50.030Z
2013-11-03T21:23:50.030Z
Daniel
<p>Belief propagation has been shown to be a very powerful method through research in probabilistic graphical models.</p>

<p>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.</p>

<p>Could someone point me to some references?</p>

CC BY-SA 3.0
2013-11-02T07:18:22.683Z
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.
Yuval Filmus
CC BY-SA 3.0
2013-11-03T21:24:38.627Z
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?
Daniel
CC BY-SA 3.0
2013-11-04T17:24:12.990Z
@Daniel I was looking for solving problems using BP where they have good theoretical guarantees for running time.
Tianyang Li
CC BY-SA 3.0
2013-11-05T00:55:54.563Z
Then I guess you need to change the statement of your problem. I understood different thing.
Daniel
<cc.complexity-theory><reference-request><graph-algorithms><machine-learning><st.statistics>
Theoretical guarantees for running times of belief propagation methods?
Tianyang Li
# Theoretical guarantees for running times of belief propagation methods?

(Asked by: username_0 on 2013-10-30)

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?

**Tags:** cc.complexity-theory, reference-request, graph-algorithms, machine-learning, st.statistics
> **Comments:**
> **username_1**: 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.  
> **username_2**: 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?  
> **username_0**: @Daniel I was looking for solving problems using BP where they have good theoretical guarantees for running time.  
> **username_2**: Then I guess you need to change the statement of your problem. I understood different thing.  

---

## 2 answers

### Answer by username_0 on 2013-11-04. Score: 5 | Accepted answer

Here's a [paper](http://web.mit.edu/devavrat/www/OR-BP-Preprint.pdf) where the authors used BP to obtain a fully polynomial-time randomized approximation scheme for the the capacitated minimum-cost network ﬂow problem.


---

### Answer by username_2 on 2013-11-03. Score: 12

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>

> **Comments:**
> **username_3**: 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.  

---

