Research map / Graph learning / Graph algorithms and clustering
Fast Convergence of Belief Propagation to Global Optima: Beyond Correlation Decay
Frederic Koehler
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Initialize mean-field iteration at the all-ones vector | Mean-field iteration for ferromagnetic Ising models · Arbitrary ferromagnetic Ising models | mean-field free-energy gap: 0 ≤ Φ_MF(x*) − Φ_MF(x_t) ≤ min{(||J||_1 + ||h||_1)/t, 2((||J||_1 + ||h||_1)/t)^(4/3)} | Improved |
| Initialize BP messages to all ones | Belief propagation for ferromagnetic Ising models · Arbitrary graphs with m edges | Bethe free-energy gap: 0 ≤ ΦBethe(P*) − Φ*Bethe(ν(t)) ≤ √(8mn(1 + ||J||∞)/t) | Improved |
| Use near-zero rather than all-ones initial messages (ablation) | Belief propagation · Ferromagnetic Ising models | convergence rate | Hurt |
Closest papers by meaning
- The Linearization of Belief Propagation on Pairwise Markov Random Fields (AAAI 2017 · similarity 0.85)
- Belief Propagation Converges to Gaussian Distributions in Sparsely-Connected Factor Graphs (ICML 2026 · similarity 0.84)
- Fixed Points of Belief Propagation—An Analysis via Polynomial Homotopy Continuation (TPAMI 2017 · similarity 0.84)
- Beyond Trees: Analysis and Convergence of Belief Propagation in Graphs with Multiple Cycles (AAAI 2020 · similarity 0.84)
- Self-Guided Belief Propagation – a Homotopy Continuation Method (TPAMI 2022 · similarity 0.83)
- Convergence Analysis of Distributed Inference with Vector-Valued Gaussian Belief Propagation (JMLR 2018 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
