Completed Partially Directed Acyclic Graph (CPDAG)

Recall that the true data generating Directed Acyclic Graph (DAG) \(G\) in a Bayesian Network (BN) can be seen as an encoding of Conditional Independence (CI) statements, where if \(X,Y\) are d-separated by \(Z\) in \(G\) then the random variables \(X,Y\) are conditionally independent given \(Z\).

However, there could be more graphs \(G_i\) which happen to encode the exact same CI statements. All of these graphs are said to belong to the same Markov Equivalence Class (MEC). An MEC can be represented by a graph called the Completed Partially Directed Acyclic Graph (CPDAG), also called the essential graph or maximally oriented graph, or even just the DAG pattern.

The CPDAG \(C\) of a DAG \(G\) is a Partially Directed Acylic Graph (PDAG) (i.e. a graph with directed and undirected edges but no directed edges) that has the same skeleton as \(G\), and an edge in \(C\) is directed iff it stays directed in every graph Markov Equivalent to \(G\).