T. Kocka, R. R. Bouckaert, M. Studeny: On characterizing inclusion of Bayesian networks. In Uncertainty in Artificial Intelligence. Proceedings of the 17th Conference (J. Breese, D. Koller eds.), Morgan Kaufmann, San Francisco 2001, pp. 261-268.

The inclusion problem deals with how to characterize (in graphical terms) whether all independence statements in the model induced by a DAG K are in the model induced by the second DAG L. Meek (1997) had a conjecture that this inclusion holds iff there exists a sequence of DAGs from L to K such that only certain 'legal' arrow reversal and 'legal' arrow addition operations are performed to get the next graph in the sequence. In this paper, we give several characterizations of inclusion of DAG models and verify Meek's conjecture in the case that the DAGs K and L differ in at most one adjacency. As a warming up a rigourous proof of graphical characterizations of equivalence of DAGs is given.

AMS classification 68T30

Bayesian network
dependence complex
equivalence of DAGs
inclusion problem
Meek's conjecture

A scanned pdf copy (1012kB) is available.

The paper builds on the following works: