What are the lesser-known but powerful probabilistic inference algorithms?
Most references about probabilistic graphical models describe popular inference methods like Variable Elimination and Junction Tree. However, I think that there are a huge number of other important probabilistic inference algorithms out there. Every once in a while I would stumble upon a paper that describes a method that I didn't hear about before, take for example The Factored Frontier Algorithm for Approximate Inference in DBNs.
Please try to add one algorithm per answer, with a brief description or points to related papers.