Counting Markov equivalence classes for DAG models on trees
© 2018 Elsevier B.V. DAG models are statistical models satisfying a collection of conditional independence relations encoded by the nonedges of a directed acyclic graph (DAG) G. Such models are used to model complex cause–effect systems across a variety of research fields. From observational data al...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier BV
2021
|
| Online Access: | https://hdl.handle.net/1721.1/134952 |
| _version_ | 1826210698636558336 |
|---|---|
| author | Radhakrishnan, Adityanarayanan Solus, Liam Uhler, Caroline |
| author_facet | Radhakrishnan, Adityanarayanan Solus, Liam Uhler, Caroline |
| author_sort | Radhakrishnan, Adityanarayanan |
| collection | MIT |
| description | © 2018 Elsevier B.V. DAG models are statistical models satisfying a collection of conditional independence relations encoded by the nonedges of a directed acyclic graph (DAG) G. Such models are used to model complex cause–effect systems across a variety of research fields. From observational data alone, a DAG model G is only recoverable up to Markov equivalence. Combinatorially, two DAGs are Markov equivalent if and only if they have the same underlying undirected graph (i.e., skeleton) and the same set of the induced subDAGs i→j←k, known as immoralities. Hence it is of interest to study the number and size of Markov equivalence classes (MECs). In a recent paper, we introduced a pair of generating functions that enumerate the number of MECs on a fixed skeleton by number of immoralities and by class size, and we studied the complexity of computing these functions. In this paper, we lay the foundation for studying these generating functions by analyzing their structure for trees and other closely related graphs. We describe these polynomials for some well-studied families of graphs including paths, stars, cycles, spider graphs, caterpillars, and balanced binary trees. In doing so, we recover connections to independence polynomials, and extend some classical identities that hold for Fibonacci numbers. We also provide tight lower and upper bounds for the number and size of MECs on any tree. Finally, we use computational methods to show that the number and distribution of high degree nodes in a triangle-free graph dictate the number and size of MECs. |
| first_indexed | 2024-09-23T14:54:03Z |
| format | Article |
| id | mit-1721.1/134952 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T14:54:03Z |
| publishDate | 2021 |
| publisher | Elsevier BV |
| record_format | dspace |
| spelling | mit-1721.1/1349522022-04-01T16:18:08Z Counting Markov equivalence classes for DAG models on trees Radhakrishnan, Adityanarayanan Solus, Liam Uhler, Caroline © 2018 Elsevier B.V. DAG models are statistical models satisfying a collection of conditional independence relations encoded by the nonedges of a directed acyclic graph (DAG) G. Such models are used to model complex cause–effect systems across a variety of research fields. From observational data alone, a DAG model G is only recoverable up to Markov equivalence. Combinatorially, two DAGs are Markov equivalent if and only if they have the same underlying undirected graph (i.e., skeleton) and the same set of the induced subDAGs i→j←k, known as immoralities. Hence it is of interest to study the number and size of Markov equivalence classes (MECs). In a recent paper, we introduced a pair of generating functions that enumerate the number of MECs on a fixed skeleton by number of immoralities and by class size, and we studied the complexity of computing these functions. In this paper, we lay the foundation for studying these generating functions by analyzing their structure for trees and other closely related graphs. We describe these polynomials for some well-studied families of graphs including paths, stars, cycles, spider graphs, caterpillars, and balanced binary trees. In doing so, we recover connections to independence polynomials, and extend some classical identities that hold for Fibonacci numbers. We also provide tight lower and upper bounds for the number and size of MECs on any tree. Finally, we use computational methods to show that the number and distribution of high degree nodes in a triangle-free graph dictate the number and size of MECs. 2021-10-27T20:10:01Z 2021-10-27T20:10:01Z 2018 2019-07-09T17:43:30Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/134952 en 10.1016/J.DAM.2018.03.015 Discrete Applied Mathematics Creative Commons Attribution-NonCommercial-NoDerivs License http://creativecommons.org/licenses/by-nc-nd/4.0/ application/pdf Elsevier BV arXiv |
| spellingShingle | Radhakrishnan, Adityanarayanan Solus, Liam Uhler, Caroline Counting Markov equivalence classes for DAG models on trees |
| title | Counting Markov equivalence classes for DAG models on trees |
| title_full | Counting Markov equivalence classes for DAG models on trees |
| title_fullStr | Counting Markov equivalence classes for DAG models on trees |
| title_full_unstemmed | Counting Markov equivalence classes for DAG models on trees |
| title_short | Counting Markov equivalence classes for DAG models on trees |
| title_sort | counting markov equivalence classes for dag models on trees |
| url | https://hdl.handle.net/1721.1/134952 |
| work_keys_str_mv | AT radhakrishnanadityanarayanan countingmarkovequivalenceclassesfordagmodelsontrees AT solusliam countingmarkovequivalenceclassesfordagmodelsontrees AT uhlercaroline countingmarkovequivalenceclassesfordagmodelsontrees |