Deep Attentive Belief Propagation: Integrating Reasoning and Learning for Solving Constraint Optimization Problems
Nov 28, 2022
Speakers
Yanchen Deng
Speaker · 0 followers
Shufeng Kong
Speaker · 0 followers
Caihua Liu
Speaker · 0 followers
About
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 on tuning a static damping factor for BP not only is laborious but also harms 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 massage-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.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 on tuning a static damping factor for BP not only is laborious but also harms their performance. Moreover, existing BP algorithms t…
Organizer
NeurIPS 2022
Account · 952 followers
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
Structural Causal Model for Molecular Dynamics Simulation
Watch later
Qi Liu, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Contrasting Drugs from Decoys
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Addressing Resource Scarcity across Sign Languages with Multilingual Pretraining and Unified-Vocabulary Datasets
Watch later
Gokul NC, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Open High-Resolution Satellite Imagery: The WorldStrat Dataset -- With Application to Super-Resolution
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Towards dynamical stability analysis of sustainable power grids using Graph Neural Networks
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Peptide-MHC Structure Prediction With Mixed Residue and Atom Graph Neural Network
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%