Convergent message passing algorithms - a unifying view

Talya Meltzer, Amir Globerson, Yair Weiss

Abstract

Message-passing algorithms are essential tools for approximate inference in graphical models, yet many popular variants lack convergence guarantees. This paper introduces Tree-Consistency Bound Optimization (TCBO), a unifying framework that ensures monotonic convergence for both Maximum A Posteriori (MAP) and marginal inference. By framing inference as the optimization of variational bounds, TCBO demonstrates that convergence can often be achieved simply by refining the update schedule of existing algorithms. This framework unifies several disparate algorithms, including TRW-S, MPLP, and Heskes' algorithm, while providing a systematic method for deriving new convergent variants.

Introduction

In probabilistic graphical models, exact inference—such as calculating marginal probabilities or solving the MAP problem—is often computationally intractable. Variational message-passing algorithms like Belief Propagation (BP) offer a scalable alternative. However, these algorithms are notorious for failing to converge, often oscillating indefinitely. While specific convergent algorithms like TRW-S or MPLP have been developed, they were previously viewed as isolated solutions. The lack of a unifying theory has hindered the systematic design of convergent message-passing techniques. This work addresses that gap by presenting TCBO as a general umbrella for convergent inference.

The TCBO Framework

The TCBO framework treats approximate inference as an optimization problem: minimizing an upper bound on the log-partition function (for marginals) or the Linear Programming (LP) relaxation (for MAP). The algorithm operates on a region graph, iteratively updating tree-structured subgraphs.

Region graph representation for the TRW-S algorithm.

To guarantee convergence, TCBO enforces two primary conditions during each update:

  1. Reparameterization: Local beliefs are updated such that they continue to represent the original global energy function, effectively redistributing weights without altering the total score.
  2. Tree-consistency: Beliefs must agree on overlapping regions, enforcing sum-consistency for marginals or max-consistency for MAP.

The authors prove that satisfying these conditions on tree structures is equivalent to performing block coordinate descent on the variational bound, which mathematically guarantees a monotonic decrease toward a local or global optimum.

The Power of Update Schedules and Duality

A key insight of this research is that the convergence of an algorithm is often a property of its update schedule rather than its core logic. For example, Wainwright’s standard tree-reweighted (TRW) sum-product algorithm is generally non-convergent. However, by adopting Kolmogorov’s TRW-S schedule—passing messages sequentially along monotonic chains—the algorithm becomes an instance of TCBO and gains a convergence guarantee.

Furthermore, the framework highlights a "sum/max duality." Because MAP and marginal inference are unified under a single temperature parameter, any convergent max-product algorithm can be transformed into a novel convergent sum-product algorithm (and vice versa) simply by swapping the mathematical operators.

Empirical Results

The theoretical strengths of TCBO were validated using a 10x10 "spin glass" grid model with random pairwise potentials. The experiments focused on comparing the newly derived sum-product TRW-S against standard non-convergent methods.

Convergence comparison between sum-TRW-S and sum-TRBP.

As shown in Figure 6, the sum-TRW-S algorithm (derived via TCBO) monotonically decreases the log-partition bound at every iteration. In contrast, the standard sum-TRBP algorithm oscillates and fails to reach a stable solution. Similar results were observed for MAP inference, where MPLP, MSD, and the max-product version of Heskes' algorithm all converged to identical bound values.

Conclusion and Future Work

TCBO provides a powerful unifying view of convergent message passing, proving that many existing algorithms are specific instances of a broader optimization principle. While the framework is limited to region graphs with non-negative counting numbers and does not yet encompass all known convergent methods, it opens the door to discovering convergent schedules for a wider class of graphical models. Future work will investigate more complex tree updates and the potential for automated discovery of convergent update orders.

Summary updated

Abstract

Message-passing algorithms have emerged as powerful techniques for approximate inference in graphical models. When these algorithms converge, they can be shown to find local (or sometimes even global) optima of variational formulations to the inference problem. But many of the most popular algorithms are not guaranteed to converge. This has lead to recent interest in convergent message-passing algorithms. In this paper, we present a unified view of convergent message-passing algorithms. We present a simple derivation of an abstract algorithm, tree-consistency bound optimization (TCBO) that is provably convergent in both its sum and max product forms. We then show that many of the existing convergent algorithms are instances of our TCBO algorithm, and obtain novel convergent algorithms "for free" by exchanging maximizations and summations in existing algorithms. In particular, we show that Wainwright's non-convergent sum-product algorithm for tree based variational bounds, is actually convergent with the right update order for the case where trees are monotonic chains.
BibTeX
@inproceedings{meltzer2009convergent,
  author = {Talya Meltzer and Amir Globerson and Yair Weiss},
  title = {{Convergent message passing algorithms - a unifying view}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2009},
  url = {https://openreview.net/forum?id=BdeWumbT8Dm},
}
Figure