Introduction
In the field of graphical models, Maximum A Posteriori (MAP) inference is a fundamental task that involves finding the most likely configuration of states for a set of discrete variables. While critical for applications ranging from computer vision to bioinformatics, MAP inference is NP-hard for graphs containing cycles. To address this, researchers typically employ Linear Programming (LP) relaxations to approximate the solution.
The Alternating Direction Method of Multipliers (ADMM) has emerged as a powerful framework for solving these LPs in parallel. However, existing ADMM-based approaches often face a "trade-off trap": decomposing a graph into individual edges simplifies subproblems but introduces a massive number of constraints that slow convergence. Conversely, using larger sub-structures reduces constraints but makes the subproblems computationally expensive to solve. This paper introduces Bethe-ADMM, a novel algorithm that breaks this trade-off by combining tree decomposition with a specialized proximal function.
The Bethe-ADMM Framework
Bethe-ADMM introduces two primary innovations to the standard ADMM framework:
- Tree Decomposition: Instead of edge-based decomposition, the algorithm decomposes the complex graph into overlapping trees. Trees are mathematically advantageous because inference on them can be solved exactly in linear time using the sum-product algorithm.
- Bethe-Divergence Proximal Function: Standard ADMM uses a quadratic penalty term to enforce consensus. Bethe-ADMM replaces this with a Bregman divergence induced by Bethe entropy (Bethe-divergence).
This technical shift is the algorithm's "Aha!" moment. By using Bethe-divergence, the ADMM subproblem for each tree becomes equivalent to a standard tree-inference problem. This allows the algorithm to solve each subproblem exactly and efficiently without expensive inner loops, enabling high-performance parallel execution.
Experimental Evaluation
The researchers evaluated Bethe-ADMM across three distinct domains: synthetic 3D grids, real-world protein design tasks, and a massive climate dataset.
Convergence and Efficiency
On synthetic 3D grids (Potts model), Bethe-ADMM demonstrated superior convergence characteristics. As shown in the figure below, it reaches lower relative error significantly faster than other primal LP methods like Proximal or Exact ADMM.
Real-World Complexity: Protein Design
The algorithm was tested on the 1jo8 and 1or7 protein design datasets, which feature hundreds of variables and a complex state space (up to 100 states per variable). In these tests, Bethe-ADMM proved to be highly competitive with state-of-the-art dual methods like MPLP.
As illustrated in the results for 1jo8 and 1or7, Bethe-ADMM consistently provides high-quality integer solutions. While coordinate descent methods like MPLP can sometimes stall at suboptimal points, Bethe-ADMM’s global convergence properties ensure it continues to progress toward the global optimum of the LP relaxation.
Massive-Scale Scalability
To test the limits of the algorithm, the authors applied it to the Climate Research Unit (CRU) dataset, which involves a 3D grid with over 7.1 million nodes. Using an Open MPI implementation, Bethe-ADMM achieved near-linear speedup as the number of processor cores increased, demonstrating its readiness for massive, distributed datasets.
Conclusion
Bethe-ADMM represents a significant advancement in parallel MAP inference. By leveraging the mathematical properties of trees and the Bethe-divergence proximal function, it offers a solution that is both theoretically robust—with a proven $O(1/T)$ convergence rate—and practically efficient. Its ability to scale linearly on multi-core systems while maintaining high accuracy on complex real-world problems makes it a versatile tool for large-scale graphical model inference.
Summary updated