Understanding the Scalability of Bayesian Network Inference Using Clique Tree Growth Curves

Date Added: May 2010
Format: PDF

One of the main approaches to performing computation in Bayesian Networks (BNs) is clique tree clustering and propagation. The clique tree approach consists of propagation in a clique tree compiled from a BN, and while it was introduced in the 1980s, there is still a lack of understanding of how clique tree computation time depends on variations in BN size and structure. This paper improves this understanding by developing an approach to characterizing clique tree growth as a function of parameters that can be computed in polynomial time from BNs.