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.
To guarantee convergence, TCBO enforces two primary conditions during each update:
- Reparameterization: Local beliefs are updated such that they continue to represent the original global energy function, effectively redistributing weights without altering the total score.
- 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.
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