Belief Propagation Neural Networks

Abstract

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.

References in corpus (6)

• Fast Graph Representation Learning with PyTorch Geometric
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Taming the Curse of Dimensionality: Discrete Integration by Hashing and Optimization
• The Bethe Partition Function of Log-supermodular Graphical Models
• Learning Neural PDE Solvers with Convergence Guarantees
• New Understanding of the Bethe Approximation and the Replica Method

Cited by in corpus (2)

• Deep learning via message passing algorithms based on belief propagation
• Unifying AI Algorithms with Probabilistic Programming using Implicitly Defined Representations