Computational Properties of Two Exact Algorithms for Bayesian Networks

This paper studies computational properties of two exact inference algorithms for Bayesian networks, namely the clique tree propagation algorithm (CTP)¹ and the variable elimination algorithm (VE). VE permits pruning of nodes irrelevant to a query while CTP facilitates sharing of computations among different queries. Experiments have been conducted to empirically compare VE and CTP. We found that, contrary to common beliefs, VE is often more efficient than CTP, especially in complex networks.