A message-passing algorithm with damping

Abstract

We propose a modified belief propagation algorithm, with over-relaxed dynamics. Such an algorithm turns out to be generally more stable and faster than ordinary belief propagation. We characterize the performance of the algorithm, employed as a tool for combinatorial optimization, on the random satisfiability problem. Moreover, we trace a connection with a recently proposed double-loop algorithm for minimizing Bethe and Kikuchi free energies.