Lesser known but powerful probabilistic inference algorithms

There are many inference algorithms out there, especially approximate inference algorithms. As for exact inference algorithms, the variable (or bucket) elimination algorithms and jointree algorithms are the classical ones. There are also algorithms that are based on conditioning, such as cutset conditioning and recursive conditioning, which have their own advantages (e.g., time/space trade-offs).

There are also some more modern approaches, based on compiling probabilistic graphical models into Arithmetic Circuits (ACs), which can take advantage of determinism and local structure in your model. These approaches can handle models with high treewidth (and enough local structure), which are in general out of the scope of algorithms like variable elimination and jointree.

Adnan Darwiche's book on Modeling And Reasoning Bayesian Networks covers all of the above algorithms and approaches, which are intimately related, in a unified way.

Variable elimination and Junction Tree are exact but often too expensive for practical use (since their cost is exponential in the tree width). Belief Propagation can be applied to cyclic networks, but it is generally not guaranteed to converge, and the results are not necessarily accurate. The last decade saw the development of several approximate inference algorithms that are faster than Junction Tree, and still reliably convergent (unlike Belief Propagation). For instance, see Hazan and Shashu'a Norm-product BP, which is a family of inference algorithms, applicable to both maximum-a-posterior problems and to marginalization problems. The references from that article list several other convergent inference algorithms that preceded it.