Markov Equivalence Classes (MECs)

Given 2 Directed Acyclic Graphs (DAGs) \(G_1 = (\mathbf{V},\mathbf{E}_1), G_2=(\mathbf{V},\mathbf{E}_2)\), we say they are Markov Equivalent, or that they belong to the same Markov Equivalence Class (MEC) if they have the same d-separations, i.e. for each mutually exclusive subsets of nodes \(\mathbf{X},\mathbf{Y},\mathbf{Z} \subset \mathbf{V}\), \(\mathbb{I}_{G_1}(\mathbf{X},\mathbf{Y}|\mathbf{Z}) \iff \mathbb{I}_{G_2}(\mathbf{X},\mathbf{Y}|\mathbf{Z})\). In the context of Bayesian Networks (BNs) this means that being in the same MEC amounts to have the same Conditional Independence (CI) relations, and thus we cannot distinguish between BNs whose DAGs are in the same MEC based on information from conditional independence testing alone.

Another characterization of Markov Equivalence is as follows (Theorem 1 (Verma and Pearl 1990)). Two DAGs \(G_1,G_2\) are Markov Equivalent if they:

This latter characterization is the basis of causal discovery (also called causal structure learning) algorithms such as the PC Algorithm.

Thoughts

Author: Nazaal

Created: 2022-04-04 Mon 23:39

Validate