Belief Propagation by Message Passing in Junction Trees: Computing Each Message Faster Using GPU Parallelization

Lu Zheng, Ole Mengshoel, Jike Chong
Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, PMLR R9:903-911, 2011.

Abstract

Compiling Bayesian networks (BNs) to junction trees and performing belief propagation over them is among the most prominent approaches to computing posteriors in BNs. However, belief propagation over junction tree is known to be computationally intensive in the general case. Its complexity may increase dramatically with the connectivity and state space cardinality of Bayesian network nodes. In this paper, we address this computational challenge using GPU parallelization. We develop data structures and algorithms that extend existing junction tree techniques, and specifically develop a novel approach to computing each belief propagation message in parallel. We implement our approach on an NVIDIA GPU and test it using BNs from several applications. Experimentally, we study how junction tree parameters affect parallelization opportunities and hence the performance of our algorithm. We achieve speedups ranging from 0.68 to 9.18 for the BNs studied.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR9-zheng11a, title = {Belief Propagation by Message Passing in Junction Trees: Computing Each Message Faster Using {GPU} Parallelization}, author = {Zheng, Lu and Mengshoel, Ole and Chong, Jike}, booktitle = {Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence}, pages = {903--911}, year = {2011}, editor = {Cozman, Fabio and Pfeffer, Avi}, volume = {R9}, series = {Proceedings of Machine Learning Research}, month = {14--17 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r9/main/assets/zheng11a/zheng11a.pdf}, url = {https://proceedings.mlr.press/r9/zheng11a.html}, abstract = {Compiling Bayesian networks (BNs) to junction trees and performing belief propagation over them is among the most prominent approaches to computing posteriors in BNs. However, belief propagation over junction tree is known to be computationally intensive in the general case. Its complexity may increase dramatically with the connectivity and state space cardinality of Bayesian network nodes. In this paper, we address this computational challenge using GPU parallelization. We develop data structures and algorithms that extend existing junction tree techniques, and specifically develop a novel approach to computing each belief propagation message in parallel. We implement our approach on an NVIDIA GPU and test it using BNs from several applications. Experimentally, we study how junction tree parameters affect parallelization opportunities and hence the performance of our algorithm. We achieve speedups ranging from 0.68 to 9.18 for the BNs studied.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Belief Propagation by Message Passing in Junction Trees: Computing Each Message Faster Using GPU Parallelization %A Lu Zheng %A Ole Mengshoel %A Jike Chong %B Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2011 %E Fabio Cozman %E Avi Pfeffer %F pmlr-vR9-zheng11a %I PMLR %P 903--911 %U https://proceedings.mlr.press/r9/zheng11a.html %V R9 %X Compiling Bayesian networks (BNs) to junction trees and performing belief propagation over them is among the most prominent approaches to computing posteriors in BNs. However, belief propagation over junction tree is known to be computationally intensive in the general case. Its complexity may increase dramatically with the connectivity and state space cardinality of Bayesian network nodes. In this paper, we address this computational challenge using GPU parallelization. We develop data structures and algorithms that extend existing junction tree techniques, and specifically develop a novel approach to computing each belief propagation message in parallel. We implement our approach on an NVIDIA GPU and test it using BNs from several applications. Experimentally, we study how junction tree parameters affect parallelization opportunities and hence the performance of our algorithm. We achieve speedups ranging from 0.68 to 9.18 for the BNs studied. %Z Reissued by PMLR on 04 October 2026.
APA
Zheng, L., Mengshoel, O. & Chong, J.. (2011). Belief Propagation by Message Passing in Junction Trees: Computing Each Message Faster Using GPU Parallelization. Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R9:903-911 Available from https://proceedings.mlr.press/r9/zheng11a.html. Reissued by PMLR on 04 October 2026.

Related Material