Counting and Sampling Markov Equivalent Directed Acyclic Graphs

Show simple item record

dc.contributor.author Talvitie, Topi
dc.contributor.author Koivisto, Mikko
dc.date.accessioned 2019-10-16T12:19:01Z
dc.date.available 2019-10-16T12:19:01Z
dc.date.issued 2019
dc.identifier.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 , Hawaii , United States , 27/01/2019 . < https://aaai.org/ojs/index.php/AAAI/article/view/4799/4677 >
dc.identifier.citation conference
dc.identifier.other PURE: 126265129
dc.identifier.other PURE UUID: 512e2c57-66ad-40ab-aff2-4ba8454cbbf8
dc.identifier.other WOS: 000486572502063
dc.identifier.other ORCID: /0000-0001-9662-3605/work/63349842
dc.identifier.uri http://hdl.handle.net/10138/306070
dc.description.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. en
dc.format.extent 8
dc.language.iso eng
dc.publisher AAAI Press
dc.relation.ispartof THIRTY-THIRD AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE / THIRTY-FIRST INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE CONFERENCE / NINTH AAAI SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE
dc.relation.isversionof 978-1-57735-809-1
dc.rights unspecified
dc.rights.uri info:eu-repo/semantics/openAccess
dc.subject ENUMERATION
dc.subject NUMBER
dc.subject 113 Computer and information sciences
dc.title Counting and Sampling Markov Equivalent Directed Acyclic Graphs en
dc.type Conference contribution
dc.contributor.organization Department of Computer Science
dc.description.reviewstatus Peer reviewed
dc.rights.accesslevel openAccess
dc.type.version publishedVersion
dc.identifier.url https://aaai.org/ojs/index.php/AAAI/article/view/4799/4677

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 simple item record