Size of interventional Markov equivalence classes in random DAG models
© 2019 by the author(s). Directed acyclic graph (DAG) models are popular for capturing causal relationships. From observational and interventional data, a DAG model can only be determined up to its interventional Markov equivalence class (I-MEC). We investigate the size of MECs for random DAG models...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137203 |
| _version_ | 1826192791520149504 |
|---|---|
| author | Uhler, Caroline Squires, Chandler |
| author_facet | Uhler, Caroline Squires, Chandler |
| author_sort | Uhler, Caroline |
| collection | MIT |
| description | © 2019 by the author(s). Directed acyclic graph (DAG) models are popular for capturing causal relationships. From observational and interventional data, a DAG model can only be determined up to its interventional Markov equivalence class (I-MEC). We investigate the size of MECs for random DAG models generated by uniformly sampling and ordering an Erdős-Rényi graph. For constant density, we show that the expected log observational MEC size asymptotically (in the number of vertices) approaches a constant. We characterize I-MEC size in a similar fashion in the above settings with high precision. We show that the asymptotic expected number of interventions required to fully identify a DAG is a constant. These results are obtained by exploiting Meek rules and coupling arguments to provide sharp upper and lower bounds on the asymptotic quantities, which are then calculated numerically up to high precision. Our results have important consequences for experimental design of interventions and the development of algorithms for causal inference. |
| first_indexed | 2024-09-23T09:28:55Z |
| format | Article |
| id | mit-1721.1/137203 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T09:28:55Z |
| publishDate | 2021 |
| record_format | dspace |
| spelling | mit-1721.1/1372032021-11-04T03:36:41Z Size of interventional Markov equivalence classes in random DAG models Uhler, Caroline Squires, Chandler © 2019 by the author(s). Directed acyclic graph (DAG) models are popular for capturing causal relationships. From observational and interventional data, a DAG model can only be determined up to its interventional Markov equivalence class (I-MEC). We investigate the size of MECs for random DAG models generated by uniformly sampling and ordering an Erdős-Rényi graph. For constant density, we show that the expected log observational MEC size asymptotically (in the number of vertices) approaches a constant. We characterize I-MEC size in a similar fashion in the above settings with high precision. We show that the asymptotic expected number of interventions required to fully identify a DAG is a constant. These results are obtained by exploiting Meek rules and coupling arguments to provide sharp upper and lower bounds on the asymptotic quantities, which are then calculated numerically up to high precision. Our results have important consequences for experimental design of interventions and the development of algorithms for causal inference. 2021-11-03T14:40:14Z 2021-11-03T14:40:14Z 2019 2021-04-05T13:32:40Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/137203 Uhler, Caroline and Squires, Chandler. 2019. "Size of interventional Markov equivalence classes in random DAG models." AISTATS 2019 - 22nd International Conference on Artificial Intelligence and Statistics, 89. en http://proceedings.mlr.press/v89/katz19a.html AISTATS 2019 - 22nd International Conference on Artificial Intelligence and Statistics Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Proceedings of Machine Learning Research |
| spellingShingle | Uhler, Caroline Squires, Chandler Size of interventional Markov equivalence classes in random DAG models |
| title | Size of interventional Markov equivalence classes in random DAG models |
| title_full | Size of interventional Markov equivalence classes in random DAG models |
| title_fullStr | Size of interventional Markov equivalence classes in random DAG models |
| title_full_unstemmed | Size of interventional Markov equivalence classes in random DAG models |
| title_short | Size of interventional Markov equivalence classes in random DAG models |
| title_sort | size of interventional markov equivalence classes in random dag models |
| url | https://hdl.handle.net/1721.1/137203 |
| work_keys_str_mv | AT uhlercaroline sizeofinterventionalmarkovequivalenceclassesinrandomdagmodels AT squireschandler sizeofinterventionalmarkovequivalenceclassesinrandomdagmodels |