A characterization of Markov equivalence classes for acyclic digraphs. (English) Zbl 0876.60095

Summary: Undirected graphs and acyclic digraphs (ADG’s), as well as their mutual extension to chain graphs, are widely used to describe dependencies among variables in multivariate distributions. In particular, the likelihood functions of ADG models admit convenient recursive factorizations that often allow explicit maximum likelihood estimates and that are well suited to building Bayesian networks for expert systems. Whereas the undirected graph associated with a dependence model is uniquely determined, there may be many ADG’s that determine the same dependence (i.e., Markov) model. Thus, the family of all ADG’s with a given set of vertices is naturally partitioned into Markov-equivalence classes, each class being associated with a unique statistical model. Statistical procedures, such as model selection or model averaging, that fail to take into account these equivalence classes may incur substantial computational or other inefficiencies. Here it is shown that each Markov-equivalence class is uniquely determined by a single chain graph, the essential graph, that is itself simultaneously Markov equivalent to all ADG’s in the equivalence class. Essential graphs are characterized, a polynomial-time algorithm for their construction is given, and their applications to model selection and other statistical questions are described.


60K99 Special processes
62H05 Characterization and structure theory for multivariate probability distributions; copulas
62M99 Inference from stochastic processes
68R10 Graph theory (including graph drawing) in computer science
68T30 Knowledge representation
94C15 Applications of graph theory to circuits and networks
Full Text: DOI


[1] ANDERSSON, S. A., MADIGAN, D. and PERLMAN, M. D. 1996. On the Markov equivalence of chain graphs, undirected graphs, and acy clic digraphs. Scand. J. Statist. To appear. Z.
[2] ANDERSSON, S. A., MADIGAN, D., PERLMAN, M. D. and TRIGGS, C. M. 1995. On the relation between conditional independence models determined by finite distributive lattices and by directed acy clic graphs. J. Statist. Plann. Inference 48 25 46. Z. · Zbl 0839.62063
[3] ANDERSSON, S. A., MADIGAN, D., PERLMAN, M. D. and TRIGGS, C. M. 1996. A graphical characterization of lattice conditional independence models. Ann. Math. and Artificial Intelligence. To appear. Z. · Zbl 0888.68090
[4] ANDERSSON, S. A. and PERLMAN, M. D. 1996. Normal linear regression models with recursive graphical Markov structure. Unpublished manuscript. Z. · Zbl 1127.62377
[5] ASMUSSEN, S. and EDWARDS, D. 1983. Collapsibility and response variables in contingency tables. Biometrika 70 567 578. Z. JSTOR: · Zbl 0549.62041
[6] BERNARDO, J. M. and SMITH, A. F. M. 1994. Bayesian Theory. Wiley, Chichester. Z. · Zbl 0796.62002
[7] BLAIR, J. R. S. and PEy TON, B. 1993. An introduction to chordal graphs and clique trees. In Z Graph Theory and Sparse Matrix Computation A. George, J. R. Gilbert and J. W. H.. Liu, eds. 1 29. Springer, New York. Z. · Zbl 0803.68081
[8] BUNTINE, W. 1994. Operations for learning with graphical models. Journal of Artificial Intelligence Research 2 159 225. Z.
[9] CHICKERING, D. M. 1995. A transformational characterization of equivalent Bayesian network structures. In Proceedings of the Eleventh Annual Conference on Uncertainty in Z. Artificial Intelligence P. Besnard and S. Hanks, eds. 87 98. Morgan Kaufmann, San Mateo, CA. Z.
[10] COOPER, G. F. and HERSKOVITS, E. 1992. A Bayesian method for the induction of probabilistic networks from data. Machine Learning 9 309 347. Z. Z · Zbl 0766.68109
[11] COX, D. R. and WERMUTH, N. 1993. Linear dependencies represented by chain graphs with. discussion. Statist. Sci. 8 204 218, 247 277. Z. · Zbl 0955.62593
[12] COX, D. R. and WERMUTH, N. 1996. Multivariate Dependencies: Models, Analy sis, and Interpretation. Chapman and Hall, London. Z. · Zbl 0880.62124
[13] DAWID, A. P. and LAURITZEN, S. L. 1993. Hy per Markov laws in the statistical analysis of decomposable graphical models. Ann. Statist. 21 1272 1317. Z. · Zbl 0815.62038
[14] DARROCH, J. N., LAURITZEN, S. L. and SPEED, T. P. 1980. Markov fields and log-linear interaction models for contingency tables. Ann. Statist. 8 522 539. Z. · Zbl 0444.62064
[15] FRy DENBERG, M. 1990. The chain graph Markov property. Scand. J. Statist. 17 333 353. Z.
[16] FRy DENBERG, M. and LAURITZEN, S. L. 1989. Decomposition of maximum likelihood in mixed graphical interaction models. Biometrika 76 539 555. Z. JSTOR: · Zbl 0677.62053
[17] GEIGER, D. and HECKERMAN, D. 1995. A characterization of the Dirichlet distribution through local and global independence. In Proceedings of the Eleventh Annual Conference on Z. Uncertainty in Artificial Intelligence P. Besnard and S. Hanks, eds. 196 207. Morgan Kaufmann, San Mateo, CA. Z.
[18] GEORGE, E. and MCCULLOGH, R. 1993. Variable selection via Gibbs sampling. J. Amer. Statist. Assoc. 88 881 889. Z.
[19] GOODMAN, L. 1973. The analysis of multidimensional contingency tables when some variables are posterior to others: a modified path analysis approach. Biometrika 60 179 192. Z. JSTOR: · Zbl 0253.62029
[20] HECKERMAN, D., GEIGER, D. and CHICKERING, D. M. 1994. Learning Bayesian networks: the combination of knowledge and statistical data. In Uncertainty in Artificial IntelliZ. gence, Proceedings of the Tenth Conference B. Lopez de Mantaras and D. Poole, eds. 293 301. Morgan Kaufmann, San Mateo, CA. Z.
[21] HECKERMAN, D., HORVITZ, E. and NATHWANI, B. 1992. Toward normative expert sy stems. I: the PATHFINDER project. Methods of Information in Medicine 31 90 105. Z.
[22] KIIVERI, H., SPEED, T. P. and CARLIN, J. B. 1984. Recursive causal models. J. Austral. Math. Soc. Ser. A 36 30 52. · Zbl 0551.62021
[23] LAURITZEN, S. L. 1996. Graphical Models. Oxford Univ. Press. Z. · Zbl 0907.62001
[24] LAURITZEN, S. L., DAWID, A. P., LARSEN, B. N. and LEIMER, H.-G. 1990. Independence properties of directed Markov fields. Networks 20 491 505. Z. · Zbl 0743.05065
[25] LAURITZEN, S. L. and SPIEGELHALTER, D. J. 1988. Local computations with probabilities on Z. graphical structures and their application to expert sy stems with discussion. J. Roy. Statist. Soc. Ser. B 50 157 224. Z. JSTOR: · Zbl 0684.68106
[26] LAURITZEN, S. L. and WERMUTH, N. 1989. Graphical models for association between variables, some of which are qualitative and some quantitative. Ann. Statist. 17 31 57. Z. · Zbl 0669.62045
[27] MADIGAN, D., ANDERSSON, S. A., PERLMAN, M. D. and VOLINSKY, C. 1996. Bayesian model averaging and model selection for Markov equivalence classes of acy clic digraphs. Comm. Statist. Theory Methods. To appear. Z. · Zbl 0894.62032
[28] MADIGAN, D. and RAFTERY, A. E. 1994. Model selection and accounting for model uncertainty in graphical models using Occam’s window. J. Amer. Statist. Assoc. 89 1535 1546. Z. · Zbl 0814.62030
[29] MADIGAN, D. and YORK, J. 1995. Bayesian graphical models for discrete data. Internat. Statist. Rev. 63 215 232. Z. · Zbl 0834.62003
[30] MEEK, C. 1995. Causal inference and causal explanation with background knowledge. In Proceedings of the Eleventh Annual Conference on Uncertainty in Artificial Intelligence Z. P. Besnard and S. Hanks, eds. 403 410. Morgan Kaufmann, San Mateo, CA. Z.
[31] NEAPOLITAN, R. E. 1990. Probabilistic Reasoning in Expert Sy stems. Wiley, New York. Z.
[32] PEARL, J. 1988. Probabilistic Reasoning in Intelligent Sy stems: Networks of Plausible Inference. Morgan Kaufmann, San Mateo, CA. Z. · Zbl 0746.68089
[33] ROBINSON, R. W. 1977. Counting unlabeled acy clic digraphs. In Proceedings of the Fifth Z. Australian Conference on Combinatorial Mathematics C. H. C. Little, ed. 28 43. Springer-Verlag, Berlin. Z. · Zbl 0376.05031
[34] SPIEGELHALTER, D. J., DAWID, A. P., LAURITZEN, S. L. and COWELL, R. G. 1993. Bayesian Z. analysis in expert sy stems with discussion. Statist. Sci. 8 219 283. Z. · Zbl 0955.62523
[35] SPIEGELHALTER, D. J. and LAURITZEN, S. L. 1990. Sequential updating of conditional probabilities on directed graphical structures. Networks 20 579 605. Z. · Zbl 0697.90045
[36] VERMA, T. and PEARL, J. 1990. Equivalence and sy nthesis of causal models. In Uncertainty in Z Artificial Intelligence: Proceedings of the Sixth Conference M. Henrion, R. Shachter,. L. Kanal and J. Lemmer, eds. 220 227. Morgan Kaufman, San Francisco. Z.
[37] VERMA, T. and PEARL, J. 1992. An algorithm for deciding if a set of observed independencies has a causal explanation. In Uncertainty in Artificial Intelligence: Proceedings of the Z. Eighth Conference D. Dubois, M. P. Wellman, B. D’Ambrosio and P. Smets, eds. 323 330. Morgan Kaufman, San Francisco. Z.
[38] WERMUTH, N. and LAURITZEN, S. L. 1990. On substantive research hy potheses, conditional Z. independence graphs and graphical chain models with discussion. J. Roy. Statist. Soc. Ser. B 52 21 72. Z. JSTOR: · Zbl 0749.62004
[39] WHITTAKER, J. L. 1990. Graphical Models in Applied Multivariate Statistics. Wiley, New York. Z. · Zbl 0732.62056
[40] WRIGHT, S. 1921. Correlation and causation. J. Agricultural Research 20 557 585. Z.
[41] YORK, J., MADIGAN, D., HEUCH, I. and LIE, R. T. 1995. Estimating a proportion of birth defects by double sampling: a Bayesian approach incorporating covariates and model uncertainty. J. Roy. Statist. Soc. Ser. C 44 227 242. · Zbl 0821.62092
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.