Sparse-Matrix Belief Propagation

Reid Bixler, Bert Huang
Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, PMLR R16:610-619, 2018.

Abstract

We propose sparse-matrix belief propagation, which executes loopy belief propagation in pairwise Markov random fields by replacing indexing over graph neighborhoods with sparse-matrix operations. This abstraction allows for seamless integration with optimized sparse linear algebra libraries, including those that per-form matrix and tensor operations on modern hardware such as graphical processing units (GPUs). The sparse-matrix abstraction allows the implementation of belief propagation in a high-level language (e.g., Python) that is also able to leverage the power of GPU parallelization. We demonstrate sparse-matrix belief propagation by implementing it in a modern deep learning framework (PyTorch), measuring the resulting massive improvement in running time, and facilitating future integration into deep learning models.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR16-bixler18a, title = {Sparse-Matrix Belief Propagation}, author = {Bixler, Reid and Huang, Bert}, booktitle = {Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence}, pages = {610--619}, year = {2018}, editor = {Globerson, Amir and Silva, Ricardo}, volume = {R16}, series = {Proceedings of Machine Learning Research}, month = {06--10 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r16/main/assets/bixler18a/bixler18a.pdf}, url = {https://proceedings.mlr.press/r16/bixler18a.html}, abstract = {We propose sparse-matrix belief propagation, which executes loopy belief propagation in pairwise Markov random fields by replacing indexing over graph neighborhoods with sparse-matrix operations. This abstraction allows for seamless integration with optimized sparse linear algebra libraries, including those that per-form matrix and tensor operations on modern hardware such as graphical processing units (GPUs). The sparse-matrix abstraction allows the implementation of belief propagation in a high-level language (e.g., Python) that is also able to leverage the power of GPU parallelization. We demonstrate sparse-matrix belief propagation by implementing it in a modern deep learning framework (PyTorch), measuring the resulting massive improvement in running time, and facilitating future integration into deep learning models.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Sparse-Matrix Belief Propagation %A Reid Bixler %A Bert Huang %B Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2018 %E Amir Globerson %E Ricardo Silva %F pmlr-vR16-bixler18a %I PMLR %P 610--619 %U https://proceedings.mlr.press/r16/bixler18a.html %V R16 %X We propose sparse-matrix belief propagation, which executes loopy belief propagation in pairwise Markov random fields by replacing indexing over graph neighborhoods with sparse-matrix operations. This abstraction allows for seamless integration with optimized sparse linear algebra libraries, including those that per-form matrix and tensor operations on modern hardware such as graphical processing units (GPUs). The sparse-matrix abstraction allows the implementation of belief propagation in a high-level language (e.g., Python) that is also able to leverage the power of GPU parallelization. We demonstrate sparse-matrix belief propagation by implementing it in a modern deep learning framework (PyTorch), measuring the resulting massive improvement in running time, and facilitating future integration into deep learning models. %Z Reissued by PMLR on 04 October 2026.
APA
Bixler, R. & Huang, B.. (2018). Sparse-Matrix Belief Propagation. Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R16:610-619 Available from https://proceedings.mlr.press/r16/bixler18a.html. Reissued by PMLR on 04 October 2026.

Related Material