Maximal Prime Subgraph Decomposition of Bayesian Networks

Kristian G. Olesen, Aalborg University, Denmark; Anders L. Madsen, Hugin Expert A/S, Denmark

In this paper we present a method for decomposition of Bayesian networks into their maximal prime subgraphs. The correctness of the method is proven and results relating the maximal prime subgraph decomposition to the maximal complete subgraphs of the moral graph of the original Bayesian network are presented. The maximal prime subgraphs of a Bayesian network can be organized as a tree which can be used as the computational structure for lazy propagation. We also identify a number of tasks performed on Bayesian networks that can benefit from maximal prime subgraph decomposition. These tasks are: divide and conquer triangulation, hybrid propagation algorithms combining exact and approximative inference techniques, and incremental construction of junction trees. We briefly compare the proposed algorithm with standard algorithms for decomposition of undirected graphs into their maximal prime subgraphs. The discussion shows that the proposed algorithm is simpler, more easy to comprehend, and it has the same complexity as the standard algorithms.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.