Belief Propagation Neural Networks
This work provides a learned alternative to hand-crafted solvers for counting problems in combinatorial optimization, offering significant speed improvements.
The paper tackles the problem of solving general counting variants of combinatorial optimization problems, which are typically addressed with hand-crafted solvers, by introducing belief propagation neural networks (BPNNs) that generalize Belief Propagation. The result shows that BPNNs converge 1.7x faster on Ising models and compute estimates 100's of times faster than state-of-the-art handcrafted methods while maintaining comparable quality.
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.