Belief propagation by message passing in junction trees: Computing each message faster using GPU parallelization

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