Deep Attentive Belief Propagation: Integrating Reasoning and Learning for Solving Constraint Optimization Problems
This work addresses inefficiencies in tuning and exploration for Belief Propagation algorithms, which is important for researchers and practitioners in graphical models and optimization, though it is incremental as it builds on existing neural-based BP variants.
The paper tackles the limitations of static damping factors and uniform neighbor treatment in Belief Propagation for Constraint Optimization Problems by integrating GRUs and Graph Attention Networks to dynamically infer optimal weights and damping factors, achieving significant performance improvements over state-of-the-art baselines.
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.