Macroscopic Models of Clique Tree Growth for Bayesian Networks

Abstract

In clique tree clustering, inference consists of propagation in a clique tree compiled from a Bayesian network. In this paper, we develop an analytical approach to characterizing clique tree growth as a function of increasing Bayesian net-work connectedness, specifically: (i) the expected number of moral edges in their moral graphs or (ii) the ratio of the num-ber of non-root nodes to the number of root nodes. In exper-iments, we systematically increase the connectivity of bipar-tite Bayesian networks, and find that clique tree size growth is well-approximated by Gompertz growth curves. This re-search improves the understanding of the scaling behavior of clique tree clustering, provides a foundation for benchmark-ing and developing improved BN inference algorithms, and presents an aid for analytical trade-off studies of tree cluster-ing using growth curves.