Markov equivalence for ancestral graphs

Abstract

Ancestral graphs can encode conditional independence relations that arise in directed acyclic graph (DAG) models with latent and selection variables. However, for any ancestral graph, there may be several other graphs to which it is Markov equivalent. We state and prove conditions under which two maximal ancestral graphs are Markov equivalent to each other, thereby extending analogous results for DAGs given by other authors. These conditions lead to an algorithm for determining Markov equivalence that runs in time that is polynomial in the number of vertices in the graph.

Published in at http://dx.doi.org/10.1214/08-AOS626 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (4)

• Causal Inference and Causal Explanation with Background Knowledge
• Markov equivalence for ancestral graphs
• Enumerating Markov Equivalence Classes of Acyclic Digraph Models
• Supplementary material for Markov equivalence for ancestral graphs

Cited by in corpus (29)

• Learning high-dimensional directed acyclic graphs with latent and selection variables
• Constraint-based Causal Discovery from Multiple Interventions over Overlapping Variable Sets
• Markov equivalence for ancestral graphs
• A generalized back-door criterion
• Nested Markov Properties for Acyclic Directed Mixed Graphs
• Computing maximum likelihood estimates in recursive linear models with correlated errors
• Searching Multiregression Dynamic Models of Resting-State fMRI Networks Using Integer Programming
• A Complete Generalized Adjustment Criterion
• Complete Graphical Characterization and Construction of Adjustment Sets in Markov Equivalence Classes of Ancestral Graphs
• Markov equivalence of marginalized local independence graphs
• Parameter and Structure Learning in Nested Markov Models
• Graphical modeling of stochastic processes driven by correlated errors
• Semiparametric Inference For Causal Effects In Graphical Models With Hidden Variables
• Causal Discovery with Unobserved Confounding and non-Gaussian Data
• Constraint-Based Causal Discovery using Partial Ancestral Graphs in the presence of Cycles
• Algebraic Problems in Structural Equation Modeling
• Towards Characterizing Markov Equivalence Classes for Directed Acyclic Graphs with Latent Variables
• Markov Equivalences for Subclasses of Loopless Mixed Graphs
• Faithfulness of Probability Distributions and Graphs
• Nonparametric causal structure learning in high dimensions
• A Transformational Characterization of Markov Equivalence for Directed Acyclic Graphs with Latent Variables
• Causal Structural Learning Via Local Graphs
• Learning AMP Chain Graphs and some Marginal Models Thereof under Faithfulness: Extended Version
• Faster algorithms for Markov equivalence
• Distributional Invariances and Interventional Markov Equivalence for Mixed Graph Models
• Towards unique and unbiased causal effect estimation from data with hidden variables
• Generating Markov Equivalent Maximal Ancestral Graphs by Single Edge Replacement
• A General Framework on Conditions for Constraint-based Causal Learning
• Conditions and Assumptions for Constraint-based Causal Structure Learning