Belief-Propagation Guided Monte-Carlo Sampling

Abstract

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.

5 pages, 4 figures

References in corpus (5)

• Phase transition in the detection of modules in sparse networks
• Rigorous Inequalities between Length and Time Scales in Glassy Systems
• Generalization of the cavity method for adiabatic evolution of Gibbs states
• Behavior of Ising Spin Glasses in a Magnetic Field
• Glassy dynamics as a melting process (On melting dynamics and the glass transition, Part II)

Cited by in corpus (6)

• Efficient partition of integer optimization problems with one-hot encoding
• Efficient subgraph-based sampling of Ising-type models with frustration
• Message passing and Monte Carlo algorithms: connecting fixed points with metastable states
• A Generalization of Spatial Monte Carlo Integration
• Spatial Monte Carlo Integration with Annealed Importance Sampling
• Solving Spin Glasses with Optimized Trees of Clustered Spins