Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs
Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs
复制标题
DOI：
10.1609/aaai.v35i13.17448
复制
发表时间：
2020-12
期刊：
影响因子：
--
通讯作者：
Marcel Wienöbst;Max Bannach;M. Liskiewicz
中科院分区：
文献类型：
--
作者：
Marcel Wienöbst;Max Bannach;M. Liskiewicz
对来自马尔可夫等价类的有向无环图 (DAG) 进行计数和均匀采样是图形因果分析中的基本任务。在本文中，我们证明这些任务可以在多项式时间内执行，解决了该领域长期存在的开放问题。我们的算法有效且易于实施。实验结果表明，该算法明显优于最先进的方法。
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.