Deep Attentive Belief Propagation: Integrating Reasoning and Learning
for Solving Constraint Optimization Problems
- URL: http://arxiv.org/abs/2209.12000v1
- Date: Sat, 24 Sep 2022 13:03:46 GMT
- Title: Deep Attentive Belief Propagation: Integrating Reasoning and Learning
for Solving Constraint Optimization Problems
- Authors: Yanchen Deng, Shufeng Kong, Caihua Liu, Bo An
- Abstract summary: Belief Propagation (BP) is an important message-passing algorithm for various reasoning tasks over graphical models.
We propose a novel self-supervised learning algorithm for DABP with a smoothed solution cost.
Our model significantly outperforms state-of-the-art baselines.
- Score: 24.63675651321079
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: 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.
Related papers
- Towards Interpretable Deep Local Learning with Successive Gradient Reconciliation [70.43845294145714]
Relieving the reliance of neural network training on a global back-propagation (BP) has emerged as a notable research topic.
We propose a local training strategy that successively regularizes the gradient reconciliation between neighboring modules.
Our method can be integrated into both local-BP and BP-free settings.
arXiv Detail & Related papers (2024-06-07T19:10:31Z) - DFA-GNN: Forward Learning of Graph Neural Networks by Direct Feedback Alignment [57.62885438406724]
Graph neural networks are recognized for their strong performance across various applications.
BP has limitations that challenge its biological plausibility and affect the efficiency, scalability and parallelism of training neural networks for graph-based tasks.
We propose DFA-GNN, a novel forward learning framework tailored for GNNs with a case study of semi-supervised learning.
arXiv Detail & Related papers (2024-06-04T07:24:51Z) - A Review of Barren Plateaus in Variational Quantum Computing [0.32360458646569984]
Variational quantum computing offers a flexible computational paradigm with applications in diverse areas.
A key obstacle to realizing their potential is the Barren Plateau (BP) phenomenon.
This article provides a comprehensive review of the current understanding of the BP phenomenon.
arXiv Detail & Related papers (2024-05-01T18:00:10Z) - Graph Neural Networks for Binary Programming [8.356266644802604]
This paper investigates a link between Graph Neural Networks (GNNs) and Binary Programming (BP) problems.
By analyzing the sensitivity of BP problems, we are able to frame the solution of BP problems as a heterophilic node classification task.
We then propose Binary-Programming GNN (BPGNN), an architecture that integrates graph representation learning techniques with BP-aware features to approximate BP solutions efficiently.
arXiv Detail & Related papers (2024-04-07T08:38:35Z) - Belief Propagation Decoding of Quantum LDPC Codes with Guided Decimation [55.8930142490617]
We propose a decoder for QLDPC codes based on BP guided decimation (BPGD)
BPGD significantly reduces the BP failure rate due to non-convergence.
arXiv Detail & Related papers (2023-12-18T05:58:07Z) - Predictive Coding Can Do Exact Backpropagation on Convolutional and
Recurrent Neural Networks [40.51949948934705]
Predictive coding networks (PCNs) are an influential model for information processing in the brain.
BP is commonly regarded to be the most successful learning method in modern machine learning.
We show that a biologically plausible algorithm is able to exactly replicate the accuracy of BP on complex architectures.
arXiv Detail & Related papers (2021-03-05T14:57:01Z) - Belief Propagation Neural Networks [103.97004780313105]
We introduce belief propagation neural networks (BPNNs)
BPNNs operate on factor graphs and generalize Belief propagation (BP)
We show that BPNNs converges 1.7x faster on Ising models while providing tighter bounds.
On challenging model counting problems, BPNNs compute estimates 100's of times faster than state-of-the-art handcrafted methods.
arXiv Detail & Related papers (2020-07-01T07:39:51Z) - A Theoretical Framework for Target Propagation [75.52598682467817]
We analyze target propagation (TP), a popular but not yet fully understood alternative to backpropagation (BP)
Our theory shows that TP is closely related to Gauss-Newton optimization and thus substantially differs from BP.
We provide a first solution to this problem through a novel reconstruction loss that improves feedback weight training.
arXiv Detail & Related papers (2020-06-25T12:07:06Z) - Belief Propagation Reloaded: Learning BP-Layers for Labeling Problems [83.98774574197613]
We take one of the simplest inference methods, a truncated max-product Belief propagation, and add what is necessary to make it a proper component of a deep learning model.
This BP-Layer can be used as the final or an intermediate block in convolutional neural networks (CNNs)
The model is applicable to a range of dense prediction problems, is well-trainable and provides parameter-efficient and robust solutions in stereo, optical flow and semantic segmentation.
arXiv Detail & Related papers (2020-03-13T13:11:35Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.