MARKOV EQUIVALENCE FOR ANCESTRAL GRAPHS

By R. Ali, Thomas S. Richardson, Peter Spirtes. 2009

117 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence

View Paper: https://www.semanticscholar.org/paper/eae2bc0e5745434ab5c38d6fe0eb75253ae75d34

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Parameter and Structure Learning in Nested Markov Models (2012, methodology): “Previous work [4] has given a discrete parameterization and ML fitting algorithms, as well as a characterization of model equivalence for mixed graph models representing conditional independences [1].”
EIGHT MYTHS ABOUT CAUSALITY AND STRUCTURAL EQUATION MODELS (2013, unknown): “Recent advances in graphical models have resulted in a complete systematization of conditional independence tests, to the point where they can be used to test nonparametric models which include latent variables (see Verma and Pearl 1990; Spirtes et al. 2000; Ali et al. 2009).”
3. The Foundations of Causal Inference (2010, methodology): “…(Shpitser and Pearl 2008) may be deduced from some semi-Markovian models, i.e., graphs with correlated errors (Verma and Pearl 1990). and Pearl 1990; Ali et al. 2009) that are mathematically proven and should therefore supercede the heuristic (and occasionally false) rules prevailing in social…”
Causal Structure Learning (2017, background): “Such MAGs form a Markov equivalence class, which can be represented by a partial ancestral graph (PAG) (Richardson and Spirtes, 2002; Ali et al., 2009).”
Joint Causal Inference from Multiple Contexts (2016, methodology): “In the case of purely observational data, the PAG output by FCI provides a complete description of the Markov equivalence class (Zhang, 2008a; Ali et al., 2009).”
Algebraic problems in structural equation modeling (2016, background): “ d-separation relations. The latter comparison can be accomplished in polynomial time. We state the result for acyclic digraphs [35, 69]. A generalization for ancestral graphs was given more recently [1]; see also [74]. Theorem 10.2. Let G and G′ be two acyclic digraphs. Then MG = MG′ if and only if”
Structure Learning in Graphical Modeling (2016, background): “PAGs can be learned by a generalization of the PC algorithm, called the FCI algorithm (Spirtes et al., 1999; Richardson & Spirtes, 2002).”
Causal Learning for Partially Observed Stochastic Dynamical Systems (2018, methodology): “…class of MAGs (Maximal Ancestral Graphs), one can exploit the fact that Markov equivalent graphs have the same adjacencies, so the learning algorithm can ﬁrst ﬁnd this so-called skeleton of the graph and then orient the edges by applying a ﬁnite set of rules (Zhang, 2008; Ali et al., 2009).”
Markov equivalence of marginalized local independence graphs (2018, background): “In the case of MAGs, a key result is that every element in a Markov equivalence class has the same skeleton , that is, the same adjacencies [5].”
Discrete chain graph models (2009, background): “Results for chain graphs of type IV follow as special cases from the work in [1, 36] that considers the more general setting of ancestral graphs.”
TRYGVE HAAVELMO AND THE EMERGENCE OF CAUSAL CALCULUS (2014, unknown): “Modern developments in graphical modeling have devised visual and algorithmic tools for detecting, displaying, and enumerating these equivalent models (Verma and Pearl, 1990; Kyono, 2010; Ali et al., 2009).”
Learning high-dimensional directed acyclic graphs with latent and selection variables (2011, background): “Several MAGs can describe exactly the same conditional independence relationships; see [2].”
Order-independent constraint-based causal structure learning (2012, background): “04 l l l l l l l l l l l l l l l l (b) Estimation performance of RFCI(-stable), CRFCI(-stable), and MRFCI(-stable) for the PAGs in terms of SHD edge marks.”
The Causal Foundations of Structural Equation Modeling (2012, methodology): “2 Equivalent Models D-separation also defines conditions for model equivalence that are easily ascertained in the Markovian models (Verma and Pearl, 1990) as well a semi-Markovian models (Ali et al., 2009).”
Constraint-based causal discovery from multiple interventions over overlapping variable sets (2014, background): “Discriminating paths, their properties and their connection to Markov equivalence is discussed in detail in Ali et al. (2009). Unfortunately, two Markov equivalent MAGs may not share the same discriminating paths.”
Nested Markov Properties for Acyclic Directed Mixed Graphs (2012, background): “Much previous work (Ali et al., 2009; Evans and Richardson, 2010; Richardson and Spirtes, 2002; Sadeghi and Lauritzen, 2014; Wermuth, 2011; Wermuth et al., 1994) has defined Markov models for mixed graphs via independence constraints implied by hidden variable DAGs on the observed margin.”
D’ya Like DAGs? A Survey on Structure Learning and Causal Discovery (2021, background): “MAGs satisfy the following three properties [2, 203, 204]: (1) there are no directed cycles (acyclicity); (2) if an edge Xi ↔ X j exists (which implies Xi is the spouse of X j ) then there are no directed paths between Xi and X j ; (3) if an edge Xi Ð X j exists (which implies Xi is the neighbour X ”