Structural Markov graph laws for Bayesian model uncertainty. (English) Zbl 1317.62046

Summary: This paper considers the problem of defining distributions over graphical structures. We propose an extension of the hyper Markov properties of A. P. Dawid and S. L. Lauritzen [Ann. Stat. 21, No. 3, 1272–1317 (1993; Zbl 0815.62038)], which we term structural Markov properties, for both undirected decomposable and directed acyclic graphs, which requires that the structure of distinct components of the graph be conditionally independent given the existence of a separating component. This allows the analysis and comparison of multiple graphical structures, while being able to take advantage of the common conditional independence constraints. Moreover, we show that these properties characterise exponential families, which form conjugate priors under sampling from compatible Markov distributions.


62H05 Characterization and structure theory for multivariate probability distributions; copulas
05C80 Random graphs (graph-theoretic aspects)
05C90 Applications of graph theory
68T30 Knowledge representation


Zbl 0815.62038


HdBCS; Separoids
Full Text: DOI arXiv Euclid


[1] Andersson, S. A., Madigan, D. and Perlman, M. D. (1997a). A characterization of Markov equivalence classes for acyclic digraphs. Ann. Statist. 25 505-541. · Zbl 0876.60095
[2] Andersson, S. A., Madigan, D. and Perlman, M. D. (1997b). On the Markov equivalence of chain graphs, undirected graphs, and acyclic digraphs. Scand. J. Stat. 24 81-102. · Zbl 0918.60050
[3] Armstrong, H., Carter, C. K., Wong, K. F. K. and Kohn, R. (2009). Bayesian covariance matrix estimation using a mixture of decomposable graphical models. Stat. Comput. 19 303-316.
[4] Asmussen, S. and Edwards, D. (1983). Collapsibility and response variables in contingency tables. Biometrika 70 567-578. · Zbl 0549.62041
[5] Auvray, V. and Wehenkel, L. (2002). On the construction of the inclusion boundary neighbourhood for Markov equivalence classes of Bayesian network structures. In Proceedings of the Eighteenth Annual Conference on Uncertainty in Artificial Intelligence (A. Darwiche and N. Friedman, eds.) 26-35. Morgan Kaufmann, San Francisco, CA.
[6] Bornn, L. and Caron, F. (2011). Bayesian clustering in decomposable graphs. Bayesian Anal. 6 829-845. · Zbl 1330.62244
[7] Brooks, S. P., Giudici, P. and Roberts, G. O. (2003). Efficient construction of reversible jump Markov chain Monte Carlo proposal distributions. J. R. Stat. Soc. Ser. B. Stat. Methodol. 65 3-55. · Zbl 1063.62120
[8] Castelo, R. and Kočka, T. (2004). On inclusion-driven learning of Bayesian networks. J. Mach. Learn. Res. 4 527-574. · Zbl 1102.68536
[9] Chickering, D. M. (1995). A transformational characterization of equivalent Bayesian network structures. In Proceedings of the Eleventh Annual Conference on Uncertainty in Artificial Intelligence ( Montreal , PQ , 1995) (P. Besnard and S. Hanks, eds.) 87-98. Morgan Kaufmann, San Francisco, CA.
[10] Chickering, D. M. (2003). Optimal structure identification with greedy search. J. Mach. Learn. Res. 3 507-554. · Zbl 1084.68519
[11] Cowell, R. G., Dawid, A. P., Lauritzen, S. L. and Spiegelhalter, D. J. (2007). Probabilistic Networks and Expert Systems . Springer, New York. · Zbl 1120.68444
[12] Dawid, A. P. (1979). Conditional independence in statistical theory. J. R. Stat. Soc. Ser. B. Stat. Methodol. 41 1-31. · Zbl 0408.62004
[13] Dawid, A. P. (1981). Some matrix-variate distribution theory: Notational considerations and a Bayesian application. Biometrika 68 265-274. · Zbl 0464.62039
[14] Dawid, A. P. (2001a). Separoids: A mathematical framework for conditional independence and irrelevance. Ann. Math. Artif. Intell. 32 335-372. · Zbl 1314.68308
[15] Dawid, A. P. (2001b). Some variations on variation independence. In Artificial Intelligence and Statistics 2001 (T. Jaakkola and T. Richardson, eds.) 187-191. Morgan Kaufmann, San Francisco, CA.
[16] Dawid, A. P. and Lauritzen, S. L. (1993). Hyper-Markov laws in the statistical analysis of decomposable graphical models. Ann. Statist. 21 1272-1317. · Zbl 0815.62038
[17] Frydenberg, M. (1990). The chain graph Markov property. Scand. J. Stat. 17 333-353. · Zbl 0713.60013
[18] Frydenberg, M. and Lauritzen, S. L. (1989). Decomposition of maximum likelihood in mixed graphical interaction models. Biometrika 76 539-555. · Zbl 0677.62053
[19] Giudici, P. and Green, P. J. (1999). Decomposable graphical Gaussian model determination. Biometrika 86 785-801. · Zbl 0940.62019
[20] Green, P. J. and Thomas, A. (2013). Sampling decomposable graphs using a Markov chain on junction trees. Biometrika 100 91-110. · Zbl 1284.62172
[21] He, Y., Jia, J. and Yu, B. (2013). Reversible MCMC on Markov equivalence classes of sparse directed acyclic graphs. Ann. Statist. 41 1742-1779. · Zbl 1360.62369
[22] Heckerman, D., Geiger, D. and Chickering, D. M. (1995). Learning Bayesian networks: The combination of knowledge and statistical data. Mach. Learn. 20 197-243. · Zbl 0831.68096
[23] Hemmecke, R., Lindner, S. and Studený, M. (2012). Characteristic imsets for learning Bayesian network structure. Internat. J. Approx. Reason. 53 1336-1349. · Zbl 1281.68183
[24] Jones, B., Carvalho, C., Dobra, A., Hans, C., Carter, C. and West, M. (2005). Experiments in stochastic computation for high-dimensional graphical models. Statist. Sci. 20 388-400. · Zbl 1130.62408
[25] Kijima, S., Kiyomi, M., Okamoto, Y. and Uno, T. (2008). On listing, sampling, and counting the chordal graphs with edge constraints. In Computing and Combinatorics. Lecture Notes in Computer Science 5092 458-467. Springer, Berlin. · Zbl 1148.68419
[26] Lauritzen, S. L. (1996). Graphical Models. Oxford Statistical Science Series 17 . Oxford Univ. Press, New York. · Zbl 0907.62001
[27] Lauritzen, S. L., Speed, T. P. and Vijayan, K. (1984). Decomposable graphs and hypergraphs. Austral. Math. Soc. Lect. Ser. 36 12-29. · Zbl 0533.05046
[28] Letac, G. and Massam, H. (2007). Wishart distributions for decomposable graphs. Ann. Statist. 35 1278-1323. · Zbl 1194.62078
[29] 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. · Zbl 0814.62030
[30] Mukherjee, S. and Speed, T. P. (2008). Network inference using informative priors. Proc. Natl. Acad. Sci. USA 105 14313-14318.
[31] Studený, M. (2005a). Characterization of inclusion neighbourhood in terms of the essential graph. Internat. J. Approx. Reason. 38 283-309. · Zbl 1134.68515
[32] Studený, M. (2005b). Probabilistic Conditional Independence Structures . Springer, London. · Zbl 1070.62001
[33] Studený, M. and Vomlel, J. (2009). A reconstruction algorithm for the essential graph. Internat. J. Approx. Reason. 50 385-413. · Zbl 1191.68534
[34] Verma, T. and Pearl, J. (1990). Equivalence and synthesis of causal models. In Proceedings of the Sixth Annual Conference on Uncertainty in Artificial Intelligence (P. Bonissone, M. Henrion, L. Kanal and J. Lemmer, eds.) 220-227. Elsevier Science, New York, NY.
[35] Wormald, N. C. (1985). Counting labelled chordal graphs. Graphs Combin. 1 193-200. · Zbl 0572.05035
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.