Theoretical guarantees for running times of belief propagation methods?
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