# Belief Propagation Neural Networks

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

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jul 2020.

## Built on by (most cited first, 30 of 33)

- [Understanding Non-linearity in Graph Neural Networks from the Bayesian-Inference Perspective](https://mlsanity.com/paper/2207.11311/) (2022)
- [NSNet: A General Neural Probabilistic Framework for Satisfiability Problems](https://mlsanity.com/paper/2211.03880/) (2022)
- [A visual introduction to Gaussian Belief Propagation](https://mlsanity.com/paper/2107.02308/) (2021)
- [Deep learning via message passing algorithms based on belief propagation](https://mlsanity.com/paper/2110.14583/) (2021)
- [Joint Entity and Relation Extraction with Span Pruning and Hypergraph Neural Networks](https://mlsanity.com/paper/2310.17238/) (2023)
- [Partition Function Estimation: A Quantitative Study](https://mlsanity.com/paper/2105.11132/) (2021)
- [Neural Belief Propagation for Scene Graph Generation](https://mlsanity.com/paper/2112.05727/) (2021)
- [Relational Reasoning Networks](https://mlsanity.com/paper/2106.00393/) (2021)
- [Learning to Solve the Constrained Most Probable Explanation Task in Probabilistic Graphical Models](https://mlsanity.com/paper/2404.11606/) (2024)
- [Understanding GNNs for Boolean Satisfiability through Approximation Algorithms](https://mlsanity.com/paper/2408.15418/) (2024)
- [Mitigating Attention Localization in Small Scale: Self-Attention Refinement via One-step Belief Propagation](https://mlsanity.com/paper/2509.07324/) (2025)
- [Graph Belief Propagation Networks](https://mlsanity.com/paper/2106.03033/) (2021)
- [Vejde: A Framework for Inductive Deep Reinforcement Learning Based on Factor Graph Color Refinement](https://mlsanity.com/paper/2509.09219/) (2025)
- [Equivariant Neural Network for Factor Graphs](https://mlsanity.com/paper/2109.14218/) (2021)
- [Robust Deep Learning from Crowds with Belief Propagation](https://mlsanity.com/paper/2111.00734/) (2021)
- [Adversarial Neural Networks for Error Correcting Codes](https://mlsanity.com/paper/2112.11491/) (2021)
- [IBIA: Bayesian Inference via Incremental Build-Infer-Approximate operations on Clique Trees](https://mlsanity.com/paper/2202.12003/) (2022)
- [Graph Neural Networks for Propositional Model Counting](https://mlsanity.com/paper/2205.04423/) (2022)
- [Deep Attentive Belief Propagation: Integrating Reasoning and Learning for Solving Constraint Optimization Problems](https://mlsanity.com/paper/2209.12000/) (2022)
- [Physics Informed Constrained Learning of Dynamics from Static Data](https://mlsanity.com/paper/2504.12675/) (2025)
- [Transformer-Based Decoding in Concatenated Coding Schemes Under Synchronization Errors](https://mlsanity.com/paper/2511.00999/) (2025)
- [Unifying AI Algorithms with Probabilistic Programming using Implicitly Defined Representations](https://mlsanity.com/paper/2110.02325/) (2021)
- [Neural Bayesian Network Understudy](https://mlsanity.com/paper/2211.08243/) (2022)
- [Local Message Passing on Frustrated Systems](https://mlsanity.com/paper/2306.01494/) (2023)
- [Classification-Aided Robust Multiple Target Tracking Using Neural Enhanced Message Passing](https://mlsanity.com/paper/2310.12407/) (2023)
- [Circular Belief Propagation for Approximate Probabilistic Inference](https://mlsanity.com/paper/2403.12106/) (2024)
- [ReMAP: Lossless Residual Neural Lifting for Scalable MAP Inference in Arbitrary-Order Markov Random Fields](https://mlsanity.com/paper/2411.18954/) (2024)
- [The Role of Recurrency in Image Segmentation for Noisy and Limited Sample Settings](https://mlsanity.com/paper/2412.15734/) (2024)
- [Attn-JGNN: Attention Enhanced Join-Graph Neural Networks](https://mlsanity.com/paper/2510.15583/) (2025)
- [In-Context Graphical Inference](https://mlsanity.com/paper/2606.05042/) (2026)

## Abstract (arXiv)

Learned neural solvers have successfully been used to solve combinatorial optimization and decision problems. More general counting variants of these problems, however, are still largely solved with hand-crafted solvers. To bridge this gap, we introduce belief propagation neural networks (BPNNs), a class of parameterized operators that operate on factor graphs and generalize Belief Propagation (BP). In its strictest form, a BPNN layer (BPNN-D) is a learned iterative operator that provably maintains many of the desirable properties of BP for any choice of the parameters. Empirically, we show that by training BPNN-D learns to perform the task better than the original BP: it 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, while returning an estimate of comparable quality.