Belief-Propagation Guided Monte-Carlo Sampling

Understand

A Monte-Carlo algorithm for discrete statistical models that combines the full power of the Belief Propagation algorithm with the advantages of a detailed-balanced heat bath approach is presented.

• A sub-tree inside the factor graph is first extracted randomly; Belief Propagation is then used as a perfect sampler to generate a configuration on the tree given the boundary conditions and the procedure is iterated.
• This appoach is best adapted for locally tree like graphs, it is therefore tested on the hard cases of spin-glass models for random graphs demonstrating its state-of-the art status in those cases.