Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Counting and Sampling from Markov Equivalent DAGs Using Clique Trees
 
conference paper

Counting and Sampling from Markov Equivalent DAGs Using Clique Trees

Ghassami, Amir Emad
•
Salehkaleybar, Saber
•
Kiyavash, Negar  
Show more
January 31, 2019
AAAI-19, IAAI-19, EAAI-20 Proceedings
Thirty-Third AAAI Conference on Artificial Intelligence - AAAI 2019

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 identifiable only up to Markov equivalence, based on conditional independence relations among the variables. Therefore, the number of DAGs equivalent to the ground truth DAG is an indicator of the causal complexity of the underlying structure–roughly speaking, it shows how many interventions or how much additional information is further needed to recover the underlying DAG. In this paper, we propose a new technique for counting the number of DAGs in a Markov equivalence class. Our approach is based on the clique tree representation of chordal graphs. We show that in the case of bounded degree graphs, the proposed algorithm is polynomial time. We further demonstrate that this technique can be utilized for uniform sampling from a Markov equivalence class, which provides a stochastic way to enumerate DAGs in the equivalence class and may be needed for finding the best DAG or for causal inference given the equivalence class as input.We also extend our counting and sampling method to the case where prior knowledge about the underlying DAG is available, and present applications of this extension in causal experiment design and estimating the causal effect of joint interventions.

  • Details
  • Metrics
Type
conference paper
DOI
10.1609/aaai.v33i01.33013664
Author(s)
Ghassami, Amir Emad
Salehkaleybar, Saber
Kiyavash, Negar  
Zhang, Kun
Date Issued

2019-01-31

Publisher

AAAI Press

Publisher place

Palo Alto, California, USA

Published in
AAAI-19, IAAI-19, EAAI-20 Proceedings
ISBN of the book

978-1-57735-809-1

Total of pages

8

Series title/Series vol.

Proceedings of the AAAI Conference on Artificial Intelligence; 33(1)

Volume

33

Start page

3664

End page

3671

Editorial or Peer reviewed

REVIEWED

Written at

OTHER

EPFL units
BAN  
Event nameEvent placeEvent date
Thirty-Third AAAI Conference on Artificial Intelligence - AAAI 2019

Honolulu, Hawaii, USA

January 27 - February 1, 2019

Available on Infoscience
April 27, 2020
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/168419
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés