Self-Guided Belief Propagation – a Homotopy Continuation Method

Research output: Contribution to journalArticlepeer-review


Belief propagation (BP) is a popular method for performing probabilistic inference on graphical models. In this work, we enhance BP and propose self-guided belief propagation (SBP) that incorporates the pairwise potentials only gradually. This homotopy continuation method converges to a unique solution and increases the accuracy without increasing the computational burden. We provide a formal analysis to demonstrate that SBP finds the global optimum of the Bethe approximation for attractive models where all variables favor the same state. Moreover, we apply SBP to various graphs with random potentials and empirically show that: (i) SBP is superior in terms of accuracy whenever BP converges, and (ii) SBP obtains a unique, stable, and accurate solution whenever BP does not converge.
Original languageEnglish
Pages (from-to)1-18
Number of pages18
JournalIEEE Transactions on Pattern Analysis and Machine Intelligence
Early online date2022
Publication statusE-pub ahead of print - 2022


  • Belief propagation
  • Computational modeling
  • Convergence
  • Couplings
  • graphical models
  • Graphical models
  • inference algorithms
  • partition function
  • probabilistic inference
  • Probabilistic logic
  • Random variables
  • sum-product algorithm

ASJC Scopus subject areas

  • Software
  • Artificial Intelligence
  • Applied Mathematics
  • Computer Vision and Pattern Recognition
  • Computational Theory and Mathematics

Fields of Expertise

  • Information, Communication & Computing


Dive into the research topics of 'Self-Guided Belief Propagation – a Homotopy Continuation Method'. Together they form a unique fingerprint.

Cite this