# Deep Attentive Belief Propagation: Integrating Reasoning and Learning for Solving Constraint Optimization Problems

arXiv: https://arxiv.org/abs/2209.12000 · HTML: https://mlsanity.com/paper/2209.12000/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 60 references that are in the map.
- First posted on arXiv 24 Sep 2022.

## Builds on (most cited first, 15 of 15)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation](https://mlsanity.com/paper/1406.1078/) (2014)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Solving Mixed Integer Programs Using Neural Networks](https://mlsanity.com/paper/2012.13349/) (2020)
- [Neural Enhanced Belief Propagation on Factor Graphs](https://mlsanity.com/paper/2003.01998/) (2020)
- [Belief Propagation Neural Networks](https://mlsanity.com/paper/2007.00295/) (2020)
- [Gaussian Mixture Variational Autoencoder with Contrastive Learning for Multi-Label Classification](https://mlsanity.com/paper/2112.00976/) (2021)
- [Bucket Elimination: A Unifying Framework for Several Probabilistic Inference](https://mlsanity.com/paper/1302.3572/) (2013)
- [Multiagent Simple Temporal Problem: The Arc-Consistency Approach](https://mlsanity.com/paper/1711.08151/) (2017)
- [Pretrained Cost Model for Distributed Constraint Optimization Problems](https://mlsanity.com/paper/2112.04187/) (2021)

## Built on by (most cited first, 1 of 1)

- [Learning Lagrangian Multipliers for the Travelling Salesman Problem](https://mlsanity.com/paper/2312.14836/) (2023)

## Abstract (arXiv)

Belief Propagation (BP) is an important message-passing algorithm for various reasoning tasks over graphical models, including solving the Constraint Optimization Problems (COPs). It has been shown that BP can achieve state-of-the-art performance on various benchmarks by mixing old and new messages before sending the new one, i.e., damping. However, existing methods of tuning a static damping factor for BP not only are laborious but also harm their performance. Moreover, existing BP algorithms treat each variable node's neighbors equally when composing a new message, which also limits their exploration ability. To address these issues, we seamlessly integrate BP, Gated Recurrent Units (GRUs), and Graph Attention Networks (GATs) within the message-passing framework to reason about dynamic weights and damping factors for composing new BP messages. Our model, Deep Attentive Belief Propagation (DABP), takes the factor graph and the BP messages in each iteration as the input and infers the optimal weights and damping factors through GRUs and GATs, followed by a multi-head attention layer. Furthermore, unlike existing neural-based BP variants, we propose a novel self-supervised learning algorithm for DABP with a smoothed solution cost, which does not require expensive training labels and also avoids the common out-of-distribution issue through efficient online learning. Extensive experiments show that our model significantly outperforms state-of-the-art baselines.