Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs

Marcel Wienöbst, Max Bannach, Maciej Liskiewicz

AAAI 2021 pp. 12198-12206

doi:10.1609/AAAI.V35I13.17448 /aaai/2021/wienobst2021aaai-polynomial/

Abstract

Counting and uniform sampling of directed acyclic graphs (DAGs) from a Markov equivalence class are fundamental tasks in graphical causal analysis. In this paper, we show that these tasks can be performed in polynomial time, solving a long-standing open problem in this area. Our algorithms are effective and easily implementable. Experimental results show that the algorithms significantly outperform state-of-the-art methods.

PDF AAAI Semantic Scholar

Cite

Text

Wienöbst et al. "Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs." AAAI Conference on Artificial Intelligence, 2021. doi:10.1609/AAAI.V35I13.17448

Markdown

[Wienöbst et al. "Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs." AAAI Conference on Artificial Intelligence, 2021.](https://mlanthology.org/aaai/2021/wienobst2021aaai-polynomial/) doi:10.1609/AAAI.V35I13.17448

BibTeX

@inproceedings{wienobst2021aaai-polynomial,
  title     = {{Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs}},
  author    = {Wienöbst, Marcel and Bannach, Max and Liskiewicz, Maciej},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2021},
  pages     = {12198-12206},
  doi       = {10.1609/AAAI.V35I13.17448},
  url       = {https://mlanthology.org/aaai/2021/wienobst2021aaai-polynomial/}
}