Bethe-ADMM for Tree Decomposition based Parallel MAP Inference

Qiang Fu, Huahua Wang, Arindam Banerjee

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:

  1. 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.
  2. 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.

Convergence analysis on synthetic 3D grids showing relative error and objective values.

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.

Performance comparison on protein design datasets 1jo8 and 1or7, showing dual values and integer solutions.

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

BibTeX
@inproceedings{fu2013bethe,
  author = {Qiang Fu and Huahua Wang and Arindam Banerjee},
  title = {{Bethe-ADMM for Tree Decomposition based Parallel MAP Inference}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2013},
}
Figure