Formulas for counting acyclic digraph Markov equivalence classes. (English) Zbl 1088.05036
Summary: Multivariate Markov dependencies between different variables often can be represented graphically using acyclic digraphs (ADGs). In certain cases, though, different ADGs represent the same statistical model, thus leading to a set of equivalence classes of ADGs that constitute the true universe of available graphical models. Building upon the previously known formulas for counting the number of acyclic digraphs and the number of equivalence classes of size 1, formulas are developed to count ADG equivalence classes of arbitrary size, based on the chordal graph configurations that produce a class of that size. Theorems to validate the formulas as well as to aid in determining the appropriate chordal graphs to use for a given class size are included.
MSC:
| 05C30 | Enumeration in graph theory |
| 62M99 | Inference from stochastic processes |
| 68R05 | Combinatorics in computer science |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68T30 | Knowledge representation |
Keywords:
ADG; Bayesian network; chordal graph; count; dag; essential graph; GMM; graphical Markov modelReferences:
| [1] | Andersson, S. A.; Madigan, D.; Perlman, M. D., A characterization of Markov equivalence classes for acyclic digraphs, Ann. Statist., 25, 505-541 (1997) · Zbl 0876.60095 |
| [2] | Blair, J. R.S.; Peyton, B., An introduction to chordal graphs and clique trees, (George, A.; Gilbert, J. R.; Liu, J. W.H., Graph Theory and Sparse Matrix Computation (1993), Springer: Springer New York) · Zbl 0803.68081 |
| [3] | Cayley, A., A theorem on trees, Quart. J. Math., 23, 376-378 (1889), (Citations from Moon, J.W., 1970. Counting Labelled Trees. Prentice-Hall, Englewood Cliffs, NJ) · JFM 21.0687.01 |
| [4] | Chickering, D.M., 1995. A transformational characterization of equivalent Bayesian network structures. In: Uncertainty in Artificial Intelligence: Proceedings of the Eleventh Conference. Morgan Kaufmann, San Francisco, pp. 87-98.; Chickering, D.M., 1995. A transformational characterization of equivalent Bayesian network structures. In: Uncertainty in Artificial Intelligence: Proceedings of the Eleventh Conference. Morgan Kaufmann, San Francisco, pp. 87-98. |
| [5] | Chickering, D. M., Learning equivalence classes of Bayesian-network structures, J. Mach. Learn. Res., 2, 445-498 (2002) · Zbl 1007.68179 |
| [6] | Dirac, G. A., On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg, 25, 71-76 (1961) · Zbl 0098.14703 |
| [7] | Gillispie, S., Perlman, M., 2001. Enumerating markov equivalence classes of acyclic digraph models. In: Uncertainty in Artificial Intelligence: Proceedings of the Seventeenth Conference. Morgan Kaufmann, San Francisco, pp. 171-177.; Gillispie, S., Perlman, M., 2001. Enumerating markov equivalence classes of acyclic digraph models. In: Uncertainty in Artificial Intelligence: Proceedings of the Seventeenth Conference. Morgan Kaufmann, San Francisco, pp. 171-177. |
| [8] | Gillispie, S. B.; Perlman, M. D., The size distribution for Markov equivalence classes of acyclic digraph models, Artif. Intell., 141, 137-155 (2002) · Zbl 1043.68096 |
| [9] | Golumbic, M.C., 1980. Algorithmic Theory and Perfect Graphs. Academic Press, New York, p. 83.; Golumbic, M.C., 1980. Algorithmic Theory and Perfect Graphs. Academic Press, New York, p. 83. · Zbl 0541.05054 |
| [10] | Heckerman, D., Geiger, D., Chickering, D.M., 1994. Learning Bayesian networks: the combination of knowledge and statistical data. In: Uncertainty in Artificial Intelligence: Proceedings of the Tenth Conference. Morgan Kaufmann, San Francisco, pp. 293-301.; Heckerman, D., Geiger, D., Chickering, D.M., 1994. Learning Bayesian networks: the combination of knowledge and statistical data. In: Uncertainty in Artificial Intelligence: Proceedings of the Tenth Conference. Morgan Kaufmann, San Francisco, pp. 293-301. · Zbl 0831.68096 |
| [11] | Kočka, T. (Aalborg University, Denmark), Personal communications.; Kočka, T. (Aalborg University, Denmark), Personal communications. |
| [12] | Moon, J. W., Counting labelled Trees (1970), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0214.23204 |
| [13] | Roberts, F.S., 1984. Applied combinatorics, Prentice-Hall, Englewood Cliffs, NJ, p. 254.; Roberts, F.S., 1984. Applied combinatorics, Prentice-Hall, Englewood Cliffs, NJ, p. 254. · Zbl 0547.05001 |
| [14] | Robinson, R.W., 1973. Counting labeled acyclic digraphs. In: Harary, F. (Ed.), New Directions in the Theory of Graphs: Proceedings of the Third Ann Arbor Conference on Graph Theory, 1971. Academic Press, New York, pp. 239-273.; Robinson, R.W., 1973. Counting labeled acyclic digraphs. In: Harary, F. (Ed.), New Directions in the Theory of Graphs: Proceedings of the Third Ann Arbor Conference on Graph Theory, 1971. Academic Press, New York, pp. 239-273. · Zbl 0259.05116 |
| [15] | Robinson, R.W., 1977. Counting unlabeled acyclic digraphs. In: Little, C.H.C. (Ed.), Proceedings of the Fifth Australian Conference on Combinatorial Mathematics. Springer, Berlin, pp. 28-43.; Robinson, R.W., 1977. Counting unlabeled acyclic digraphs. In: Little, C.H.C. (Ed.), Proceedings of the Fifth Australian Conference on Combinatorial Mathematics. Springer, Berlin, pp. 28-43. · Zbl 0376.05031 |
| [16] | Steinsky, B., Enumeration of labeled chain graphs and labeled essential directed acyclic graphs, Discrete Math., 270, 267-278 (2003) · Zbl 1060.05047 |
| [17] | Verma, T., Pearl, J., 1990. Equivalence and synthesis of causal models. In: Uncertainty in Artificial Intelligence: Proceedings of the Sixth Conference. Morgan Kaufmann, San Francisco, pp. 220-227.; Verma, T., Pearl, J., 1990. Equivalence and synthesis of causal models. In: Uncertainty in Artificial Intelligence: Proceedings of the Sixth Conference. Morgan Kaufmann, San Francisco, pp. 220-227. |
| [18] | Verma, T., 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 Eighth Conference. Morgan Kaufmann, San Francisco, pp. 323-330.; Verma, T., 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 Eighth Conference. Morgan Kaufmann, San Francisco, pp. 323-330. |
| [19] | Volf, M.; Studený, M., A graphical characterization of the largest chain graphs, Intl. J. Approx. Reason., 20, 209-236 (1999) · Zbl 0935.62063 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
