  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.
