Markov equivalence
Markov equivalence is a relation between probabilistic graphical models that encode the same collection of conditional independence statements. For directed acyclic graphs (DAGs), two graphs are Markov equivalent when their graphical structures imply identical conditional independences under the d-separation criterion. The relation is central to the interpretation of Bayesian networks, because observational data can generally identify an equivalence class of graph structures rather than a unique orientation of every edge.
The graphical characterization of equivalence separates structural information recoverable from conditional independence relations from orientations that remain observationally indeterminate. Two DAGs belong to the same Markov equivalence class exactly when they have the same underlying undirected graph and the same unshielded collider configurations. This criterion permits equivalence to be established without enumerating all d-separation statements implied by either graph.
Formal definition
Let (G=(V,E)) be a DAG on a finite vertex set (V). Its independence model is
[ \mathcal I(G)
\left{ (X,Y\mid Z): X \mathrel{\perp_d} Y\mid Z \text{ in }G \right}, ]
where (X), (Y), and (Z) are pairwise disjoint subsets of (V), and (\perp_d) denotes d-separation. Two DAGs (G_1) and (G_2) are Markov equivalent when
[ \mathcal I(G_1)=\mathcal I(G_2). ]
Equivalently, they determine the same family of distributions satisfying the global Markov property, provided that the comparison concerns the conditional independence constraints encoded by the graphs rather than additional parametric restrictions. A linear Gaussian model, for example, may contain coefficient-specific constraints that are not consequences of the graph alone and therefore do not define ordinary DAG Markov equivalence.
Markov equivalence is an equivalence relation. Reflexivity follows because every graph has the same independence model as itself. Symmetry follows from equality of independence models, while transitivity follows when two successive pairs encode equal models. The resulting equivalence classes partition the set of DAGs on (V).
Graphical characterization
The skeleton of a DAG is obtained by replacing every directed edge with an undirected edge. An unshielded collider, also called a v-structure or immorality, is an induced configuration
[ A\rightarrow B\leftarrow C ]
in which (A) and (C) are not adjacent. The absence of an edge between the outer vertices distinguishes an unshielded collider from a collider embedded in a triangle, since the latter does not have the same identifiable effect on the graph's conditional independence model.
The Verma–Pearl characterization states that two DAGs are Markov equivalent if and only if they have identical skeletons and identical sets of unshielded colliders. The skeleton determines which pairs of vertices can be directly connected, while the collider set records those orientations that alter d-separation in a manner detectable from the independence model.
Consider the three DAGs
[ A\rightarrow B\rightarrow C, \qquad A\leftarrow B\rightarrow C, \qquad A\leftarrow B\leftarrow C. ]
They have the same path skeleton and contain no unshielded collider. Each graph entails (A\perp C\mid B), so all three are Markov equivalent. By contrast,
[ A\rightarrow B\leftarrow C ]
has the same skeleton but contains an unshielded collider. It entails the marginal independence (A\perp C) while generally rendering the outer variables dependent after conditioning on (B), and it therefore belongs to a different equivalence class.
Shielded colliders do not independently characterize an equivalence class. If (A) and (C) are adjacent, changing the orientation at (B) may preserve all d-separation relations because the additional adjacency prevents the local configuration from producing the separation pattern associated with an unshielded collider.
Development
The modern treatment of Markov equivalence emerged from work on graphical representations of multivariate dependence during the late twentieth century. Judea Pearl and Thomas Verma established the skeleton-and-collider characterization in their analysis of equivalence and synthesis for causal models. Morten Frydenberg developed closely related results in the broader setting of graphical Markov models, including structures containing both directed and undirected components.
During the early 1990s, You Watanabe formulated the DAG criterion directly as an equality between d-separation models and skeleton-plus-collider descriptions. This formulation connected the local graphical characterization with the global conditional independence semantics and was used in subsequent analyses of equivalence-class representations.
David Chickering later supplied a transformational characterization based on covered edge reversals. A directed edge (A\rightarrow B) is covered when the parent set of (B) is obtained by adjoining (A) to the parent set of (A):
[ \operatorname{Pa}(B)=\operatorname{Pa}(A)\cup{A}. ]
Reversing a covered edge preserves acyclicity and Markov equivalence. Moreover, any two Markov-equivalent DAGs can be connected by a finite sequence of such reversals, with every intermediate graph remaining in the same equivalence class. This result relates the static skeleton-and-collider criterion to local transformations of graph orientation.
Steen Andersson, David Madigan, and Michael Perlman developed a systematic representation of equivalence classes through essential graphs. Their treatment clarified how an entire class of DAGs can be represented without selecting an arbitrary member as its canonical structure.
Essential graphs
A Markov equivalence class can be represented by a completed partially directed acyclic graph (CPDAG), also known as an essential graph. The CPDAG has the common skeleton of the class. An edge is directed when every DAG in the class assigns it the same orientation, and it is undirected when both orientations occur among class members.
An orientation shared by every member is described as compelled. An orientation that differs across members is reversible, although reversibility concerns membership in the complete equivalence class rather than an unrestricted reversal inside one chosen graph. Directly reversing an edge can create a directed cycle or a new unshielded collider, so a reversible edge need not be independently reversible while all other orientations remain fixed.
The directed part of a CPDAG records the information determined by the conditional independence model. Its undirected chain components are chordal graphs, which permits their edges to be oriented through suitable elimination orderings without introducing additional unshielded colliders. Every admissible orientation of these components that respects the directed structure corresponds to a DAG in the represented equivalence class.
A class containing only one DAG has a fully directed CPDAG. Such a graph is identifiable from its complete d-separation model. More commonly, the CPDAG retains undirected edges because observational conditional independences do not determine all directions.
Relation to causal interpretation
In a causal Bayesian network, directed edges receive a causal interpretation in addition to their probabilistic role. Markov-equivalent DAGs can then represent different causal hypotheses even though they entail the same observational conditional independences. Observational equivalence consequently does not imply equality of intervention distributions.
The distinction is visible in the Markov-equivalent structures
[ A\rightarrow B\rightarrow C \quad\text{and}\quad A\leftarrow B\rightarrow C. ]
Both encode (A\perp C\mid B), but an intervention on (A) can affect (C) in the first graph and has no directed causal path to (C) in the second. Interventional data may therefore orient edges that remain undirected in an observational CPDAG, producing a smaller interventional equivalence class.
Causal discovery methods based on conditional independence commonly return a CPDAG rather than a single DAG. Under causal sufficiency, the causal Markov condition, and faithfulness, the population independence model determines the correct Markov equivalence class. Faithfulness excludes distributions in which distinct active paths cancel numerically and create conditional independences not implied by d-separation.
When latent variables are permitted, DAG equivalence over the observed variables is no longer an adequate representation. Maximal ancestral graphs and partial ancestral graphs describe observational equivalence in settings involving latent confounding or selection effects. Their equivalence criteria require graphical information beyond the skeleton and ordinary unshielded colliders.
Statistical significance
Markov equivalence defines the structural resolution available from an ideal conditional independence model. Even exact knowledge of every observational independence relation cannot distinguish DAGs within the same class. Finite-sample uncertainty adds a separate statistical problem because estimated independences may differ from the population model.
Score-based structure learning reflects the same equivalence through score equivalence. A score-equivalent criterion assigns equal values to Markov-equivalent DAGs when they represent the same statistical model under corresponding parameter assumptions. The Bayesian information criterion can possess this property for standard discrete or Gaussian Bayesian-network parametrizations, while Bayesian scores require compatible parameter priors to produce equivalent marginal likelihoods.
Search can consequently be conducted over equivalence classes rather than individual DAGs. In this formulation, the state space consists of CPDAGs, and transitions modify features that alter the represented independence model. The interpretation of a result remains class-level: compelled orientations are common to all represented DAGs, whereas undirected edges retain unresolved directional variation.