Abstract
According to physics predictions, the free energy of random factor graph
models that satisfy a certain “static replica symmetry” condition can be
calculated via the Belief Propagation message passing scheme [Krzakala
et al., PNAS 2007]. Here we prove this conjecture for two general classes of
random factor graph models, namely Poisson random factor graphs and
random regular factor graphs. Specifically, we show that the messages
constructed just as in the case of acyclic factor graphs asymptotically satisfy
the Belief Propagation equations and that the free energy density is
given by the Bethe free energy formula.
models that satisfy a certain “static replica symmetry” condition can be
calculated via the Belief Propagation message passing scheme [Krzakala
et al., PNAS 2007]. Here we prove this conjecture for two general classes of
random factor graph models, namely Poisson random factor graphs and
random regular factor graphs. Specifically, we show that the messages
constructed just as in the case of acyclic factor graphs asymptotically satisfy
the Belief Propagation equations and that the free energy density is
given by the Bethe free energy formula.
| Original language | English |
|---|---|
| Journal | Annales de L'Institut Henri Poincare (D) |
| Early online date | 9 May 2017 |
| Publication status | E-pub ahead of print - 9 May 2017 |