Counting and Sampling Markov Equivalent Directed Acyclic Graphs

Show full item record



Permalink

http://hdl.handle.net/10138/306070

Citation

Talvitie , T & Koivisto , M 2019 , Counting and Sampling Markov Equivalent Directed Acyclic Graphs . in THIRTY-THIRD AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE / THIRTY-FIRST INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE CONFERENCE / NINTH AAAI SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE . AAAI Press , Palo Alto, CA , pp. 7984-7991 , 33rd AAAI Conference on Artificial Intelligence , Honolulu , United States , 27/01/2019 . < https://aaai.org/ojs/index.php/AAAI/article/view/4799/4677 >

Title: Counting and Sampling Markov Equivalent Directed Acyclic Graphs
Author: Talvitie, Topi; Koivisto, Mikko
Contributor: University of Helsinki, Department of Computer Science
University of Helsinki, Department of Computer Science
Publisher: AAAI Press
Date: 2019
Language: eng
Number of pages: 8
Belongs to series: THIRTY-THIRD AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE / THIRTY-FIRST INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE CONFERENCE / NINTH AAAI SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE
ISBN: 978-1-57735-809-1
URI: http://hdl.handle.net/10138/306070
Abstract: Exploring directed acyclic graphs (DAGs) in a Markov equivalence class is pivotal to infer causal effects or to discover the causal DAG via appropriate interventional data. We consider counting and uniform sampling of DAGs that are Markov equivalent to a given DAG. These problems efficiently reduce to counting the moral acyclic orientations of a given undirected connected chordal graph on n vertices, for which we give two algorithms. Our first algorithm requires O(2(n)n(4)) arithmetic operations, improving a previous super-exponential upper bound. The second requires O (k! 2(k) k(2)n) operations, where k is the size of the largest clique in the graph; for bounded-degree graphs this bound is linear in n. After a single run, both algorithms enable uniform sampling from the equivalence class at a computational cost linear in the graph size. Empirical results indicate that our algorithms are superior to previously presented algorithms over a range of inputs; graphs with hundreds of vertices and thousands of edges are processed in a second on a desktop computer.
Subject: ENUMERATION
NUMBER
113 Computer and information sciences
Rights:


Files in this item

Total number of downloads: Loading...

Files Size Format View
4799_Article_Text_7838_1_10_20190708.pdf 804.2Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record