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?
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