Towards Counting Markov Equivalence Classes with Logical Constraints
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910457515737088 |
|---|---|
| author | Bizzaro, Davide Serafini, Luciano Malhotra, Sagar |
| author_facet | Bizzaro, Davide Serafini, Luciano Malhotra, Sagar |
| contents | We initiate the study of counting Markov Equivalence Classes (MEC) under logical constraints. MECs are equivalence classes of Directed Acyclic Graphs (DAGs) that encode the same conditional independence structure among the random variables of a DAG model. Observational data can only allow to infer a DAG model up to Markov Equivalence. However, Markov equivalent DAGs can represent different causal structures, potentially super-exponentially many. Hence, understanding MECs combinatorially is critical to understanding the complexity of causal inference. In this paper, we focus on analysing MECs of size one, with logical constraints on the graph topology. We provide a polynomial-time algorithm (w.r.t. the number of nodes) for enumerating essential DAGs (the only members of an MEC of size one) with arbitrary logical constraints expressed in first-order logic with two variables and counting quantifiers (C^2). Our work brings together recent developments in tractable first-order model counting and combinatorics of MECs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_13736 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Towards Counting Markov Equivalence Classes with Logical Constraints Bizzaro, Davide Serafini, Luciano Malhotra, Sagar Logic in Computer Science We initiate the study of counting Markov Equivalence Classes (MEC) under logical constraints. MECs are equivalence classes of Directed Acyclic Graphs (DAGs) that encode the same conditional independence structure among the random variables of a DAG model. Observational data can only allow to infer a DAG model up to Markov Equivalence. However, Markov equivalent DAGs can represent different causal structures, potentially super-exponentially many. Hence, understanding MECs combinatorially is critical to understanding the complexity of causal inference. In this paper, we focus on analysing MECs of size one, with logical constraints on the graph topology. We provide a polynomial-time algorithm (w.r.t. the number of nodes) for enumerating essential DAGs (the only members of an MEC of size one) with arbitrary logical constraints expressed in first-order logic with two variables and counting quantifiers (C^2). Our work brings together recent developments in tractable first-order model counting and combinatorics of MECs. |
| title | Towards Counting Markov Equivalence Classes with Logical Constraints |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2405.13736 |