Variational message passing neural network for Maximum-A-Posteriori (MAP) inference

Zijun Cui, Hanjing Wang, Tian Gao, Kartik Talamadupula, Qiang JiUAI 2022 · OpenReview

Abstract

Maximum-A-Posteriori (MAP) inference is a fundamental task in probabilistic inference. While Belief Propagation (BP) is widely used, it struggles with loopy graphs and lacks guarantees. Existing neural approaches often require expensive ground-truth labels. We present the Variational Message Passing Neural Network (V-MPNN), which optimizes a neural-augmented free energy to perform MAP inference without supervised labels, achieving state-of-the-art results on complex graph topologies.

Introduction

MAP inference involves finding the most probable configuration of variables in a probabilistic graphical model (PGM). While exact for tree-structured graphs, standard algorithms like Belief Propagation (BP) often fail to converge or provide poor approximations on "loopy" graphs common in real-world applications like computer vision and biochemistry. Recent attempts to use deep learning for inference typically rely on supervised learning, requiring a large dataset of graphs paired with their exact MAP solutions—which are themselves NP-hard to compute.

The V-MPNN Framework

The Variational Message Passing Neural Network (V-MPNN) bridges the gap between classical variational inference and deep learning. It introduces a "neural-augmented free energy" where the traditional entropy term is replaced by a neural-parameterized function.

The V-MPNN architecture combines an MPNN for message passing with a neural-augmented free energy objective.

The framework uses a Message Passing Neural Network (MPNN) to minimize this free energy. Unlike standard BP, which uses fixed update rules, V-MPNN learns optimal message-passing strategies through a Multi-Layer Perceptron (MLP). A key theoretical contribution is the proof that this neural-augmented free energy is convex, ensuring stable optimization.

Label-Free Training

A standout feature of V-MPNN is its training strategy. Instead of matching ground-truth labels, the model is trained by minimizing the free energy itself. This "physics-inspired" loss allows the model to learn how to solve MAP problems on graphs where the ground truth is unknown or impossible to calculate. The training involves a minimax objective: minimizing free energy with respect to MPNN parameters while maximizing it with respect to entropy parameters to tighten error bounds.

Experimental Results

The researchers evaluated V-MPNN across 13 diverse graph structures, ranging from simple trees to highly complex loopy graphs like circular ladders and complete graphs.

Comparison of V-MPNN against traditional inference methods (BP, TRW-BP, MPLP) across various graph topologies.

As shown in the results, V-MPNN consistently outperforms traditional training-free methods. For instance, on the complex Circular Ladder graph ($N=15$), V-MPNN achieved 73% accuracy, significantly outperforming the next best traditional method (MPLP at 63%). Across all loopy graphs, V-MPNN maintained a higher mean accuracy compared to BP and its variants.

Furthermore, V-MPNN demonstrated superior generalization compared to supervised GNNs. On a Tree graph ($N=9$), V-MPNN reached 96% accuracy, significantly higher than the 77% achieved by a supervised Node-GNN. This suggests that the variational objective provides a stronger inductive bias for inference than simple supervision.

Conclusion

V-MPNN represents a significant step forward in probabilistic inference. By combining the theoretical foundations of variational methods with the representational power of neural networks, it enables accurate MAP inference on complex graphs without the need for labeled data. While it requires a "warm start" to ensure convergence and shows slight performance gaps on perfect trees compared to exact BP, its ability to handle loopy structures makes it a powerful tool for real-world PGMs.

Summary updated

Abstract

Maximum-A-Posteriori (MAP) inference is a fundamental task in probabilistic inference and belief propagation (BP) is a widely used algorithm for MAP inference. Though BP has been applied successful...
BibTeX
@inproceedings{cui2022variational,
  author = {Zijun Cui and Hanjing Wang and Tian Gao and Kartik Talamadupula and Qiang Ji},
  title = {{Variational message passing neural network for Maximum-A-Posteriori (MAP) inference}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2022},
  url = {https://openreview.net/forum?id=EHevFSalVS},
}
Figure