  Inference for probabilistic graphical models is still very much a practical
challenge in large domains. The commonly used and effective belief propagation
(BP) algorithm and its generalizations often do not converge when applied to
hard, real-life inference tasks. While it is widely recognized that the
scheduling of messages in these algorithms may have significant consequences,
this issue remains largely unexplored. In this work, we address the question of
how to schedule messages for asynchronous propagation so that a fixed point is
reached faster and more often. We first show that any reasonable asynchronous
BP converges to a unique fixed point under conditions similar to those that
guarantee convergence of synchronous BP. In addition, we show that the
convergence rate of a simple round-robin schedule is at least as good as that
of synchronous propagation. We then propose residual belief propagation (RBP),
a novel, easy-to-implement, asynchronous propagation algorithm that schedules
messages in an informed way, that pushes down a bound on the distance from the
fixed point. Finally, we demonstrate the superiority of RBP over
state-of-the-art methods for a variety of challenging synthetic and real-life
problems: RBP converges significantly more often than other methods; and it
significantly reduces running time until convergence, even when other methods
converge.
