A characterization of Markov equivalence for directed cyclic graphs

DOI10.1016/S0888-613X(97)00020-0MaRDI QIDQ1809370zbMATH OpenFDO

Authors Yanyan Li

Publication date 20 December 1999

Published in International Journal of Approximate Reasoning (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1302.3600

zbMATH Keywords

\(d\)-separationacyclic directed graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Artificial intelligence (68T99)

Abstract: Although the concept of d-separation was originally defined for directed acyclic graphs (see Pearl 1988), there is a natural extension of he concept to directed cyclic graphs. When exactly the same set of d-separation relations hold in two directed graphs, no matter whether respectively cyclic or acyclic, we say that they are Markov equivalent. In other words, when two directed cyclic graphs are Markov equivalent, the set of distributions that satisfy a natural extension of the Global Directed Markov condition (Lauritzen et al. 1990) is exactly the same for each graph. There is an obvious exponential (in the number of vertices) time algorithm for deciding Markov equivalence of two directed cyclic graphs; simply chech all of the d-separation relations in each graph. In this paper I state a theorem that gives necessary and sufficient conditions for the Markov equivalence of two directed cyclic graphs, where each of the conditions can be checked in polynomial time. Hence, the theorem can be easily adapted into a polynomial time algorithm for deciding the Markov equivalence of two directed cyclic graphs. Although space prohibits inclusion of correctness proofs, they are fully described in Richardson (1994b).

Recommendations

• A characterization of Markov equivalence classes for acyclic digraphs
• Markov equivalence for ancestral graphs
• On the Markov Equivalence of Chain Graphs, Undirected Graphs, and Acyclic Digraphs
• Separation and completeness properties for AMP chain graph Markov models.
• Markov equivalence in Bayesian networks

Cites work

• A Note on the Statistical Testability of 'Explicit Causal Chains' Against the Class of 'Interdependent' Models
• Causation, prediction, and search
• scientific article; zbMATH DE number 4174001 (Why is no real title available?)
• scientific article; zbMATH DE number 4211299 (Why is no real title available?)
• scientific article; zbMATH DE number 45532 (Why is no real title available?)
• scientific article; zbMATH DE number 3449757 (Why is no real title available?)
• Independence properties of directed markov fields
• Markov properties of nonrecursive causal models
• The Statistical Implications of a System of Simultaneous Equations

Cited in

(8)

• Inferring large graphs using \(\ell_1\)-penalized likelihood
• Computation of maximum likelihood estimates in cyclic structural equation models
• Graphical modeling of stochastic processes driven by correlated noise
• On the Markov Equivalence of Chain Graphs, Undirected Graphs, and Acyclic Digraphs
• Markov Properties for Acyclic Directed Mixed Graphs
• scientific article; zbMATH DE number 1448979 (Why is no real title available?)
• Totally ordered conditional independence models
• Weak equivalence of local independence graphs

Describes a project that uses

Uses Software

• TETRAD

This page was built for publication: A characterization of Markov equivalence for directed cyclic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1809370)