Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs
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.
Code (1)
Similar Papers 제목 키워드 기반
Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs with Applications
Counting and sampling directed acyclic graphs 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…
Active LearningCounting Markov Equivalent Directed Acyclic Graphs Consistent with Background Knowledge
A polynomial-time exact algorithm for counting the number of directed acyclic graphs in a Markov equivalence class was recently given by Wien\"obst, Bannach, and Li\'skiewicz (AAAI 2021). In this paper, we consider the m…
Inference and Sampling of $K_{33}$-free Ising Models
We call an Ising model tractable when it is possible to compute its partition function value (statistical inference) in polynomial time. The tractability also implies an ability to sample configurations of this model in …
Counting and Sampling from Markov Equivalent DAGs Using Clique Trees
A directed acyclic graph (DAG) is the most common graphical model for representing causal relationships among a set of variables. When restricted to using only observational data, the structure of the ground truth DAG is…
Causal InferenceOn Exact Sampling in the Two-Variable Fragment of First-Order Logic
In this paper, we study the sampling problem for first-order logic proposed recently by Wang et al. -- how to efficiently sample a model of a given first-order sentence on a finite domain? We extend their result for the …
Sentence