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)). Two DAGs \(G_1,G_2\) are Markov Equivalent if they:

• Have the same skeleton, i.e. same underlying undirected graph.
• Same v-structures (also called immoralities), which are triples of nodes \(X,Y,Z \in \mathbf{V}\) such that \(X \rightarrow Z \leftarrow Y\).

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