Models for Graph Decomposition
Adnan Y. Darwiche · Cambridge University Press eBooks · 2009
We consider in this chapter three models of graph decomposition: elimination orders, jointrees and dtrees, which underly the key inference algorithms we discussed thus far. We present formal definitions of these models, provide polytime, width-preserving transformations between them, and show how the optimal construction of each of these models corresponds in a precise sense to the process of optimally triangulating a graph. Introduction We presented three inference algorithms in previous chapters whose complexity can be exponential only in the network treewidth: variable elimination, factor elimination (jointree), and recursive conditioning. Each one of these algorithms can be viewed as decomposing the Bayesian network in a systematic manner, allowing us to reduce a query with respect to some network into a query with respect to a smaller network. In particular, variable elimination removes variables one at a time from the network, while factor elimination removes factors one at a time and recursive conditioning partitions the network into smaller pieces. We also saw how the decompositional choices made by these algorithms can be formalized using elimination orders, elimination trees (jointrees), and dtrees, respectively. In fact, the time and space complexity of each of these algorithms was characterized using the width of its corresponding decomposition model, which is lower-bounded by the treewidth. We provide a more comprehensive treatment of decomposition models in this chapter including polytime, width-preserving transformations between them. These transformations allow us to convert any method for constructing low-width models of one type into low-width models of other types.