Causal discovery aims to uncover the directed graph that governs a system's underlying mechanisms. However, a fundamental limitation arises when we rely purely on observational data: many distinct directed acyclic graphs (DAGs) imply the exact same set of conditional independence relationships.
For example, the structures $A \rightarrow B \rightarrow C$ and $A \leftarrow B \leftarrow C$ both encode the same constraint—that $A$ and $C$ are independent given $B$. Because observational data cannot distinguish between these two configurations, they belong to the same Markov Equivalence Class (MEC).
If a structure learning algorithm searches through the space of individual DAGs, it will spend massive computational resources evaluating, scoring, and moving between graphs that are statistically identical. Shifting the search paradigm from individual graphs to the space of equivalence classes eliminates this redundancy, transforming an intractable combinatorial explosion into a highly optimized, parsimonious search problem.
The Cost of Graph-Based Redundancy
To understand why searching the space of equivalence classes works, we must first look at the sheer scale of redundancy in graph spaces. As Deleu et al. and Darwiche et al. point out, treating observationally identical graph permutations as distinct entities introduces severe computational overhead.
How much smaller is the space of equivalence classes? Gillispie et al. explicitly enumerated DAGs and MECs for up to 10 variables, demonstrating empirically that the number of distinct equivalence classes is significantly smaller than the total number of possible DAGs. By collapsing thousands or millions of equivalent graphs into a single representative class, algorithms can avoid wasting time scoring structurally distinct but statistically identical candidates.
Individual DAG Space:
[A → B → C] [A ← B ← C] [A ← B → C] <-- Distinct graphs, same dependencies
\ | /
\ | /
Collapsed Equivalence Class Space:
[A — B — C] (CPDAG) <-- Single search node
To navigate this compressed space, algorithms utilize abstract graphical representations that capture an entire class at once. The most common representation is a Completed Partially Directed Acyclic Graph (CPDAG), or essential graph, where directed edges represent invariant causal directions (identifiable from data) and undirected edges represent reversible relationships. As noted by Pelckmans et al., targeting these unique sets of independence assumptions directly allows algorithms to bypass individual graph instances entirely.
This abstraction also simplifies downstream causal tasks. For instance, when estimating a causal effect, one must find a valid "adjustment set" of variables to control for confounding. van der Zander et al. demonstrated that by using restricted chain graphs to represent MECs, valid adjustment sets can be identified across an entire class of equivalent models in polynomial time, completely bypassing the need to exhaustively enumerate individual DAGs.
Algorithmic Frameworks for Equivalence Search
Operating directly within the space of equivalence classes requires specialized search and optimization strategies across different learning paradigms.
Score-Based Greedy Search
Traditional greedy algorithms like Greedy Equivalence Search (GES) move step-by-step through the space of CPDAGs. This strategy has been extended to handle complex real-world conditions like unmeasured variables and feedback loops. Claassen et al. developed Greedy PAG Search (GPS), which efficiently handles latent confounders by searching over equivalence classes in linear time for sparse graphs, preventing repeated scoring of equivalent structures. Similarly, Améndola et al. proved that simple cyclic graphs share a distributional equivalence rule with acyclic graphs, allowing score-based greedy searches to target equivalence classes even when systems contain feedback loops.
Exact Enumeration and Top-K Selection
In many applications, finding a single best graph is insufficient; we want the top $k$ highest-scoring structures. If we perform this search in the DAG space, the top results will be dominated by trivial edge reversals of the same underlying model. Chen et al. resolved this by canonizing the search space into an "EC Tree" and using A* search to navigate equivalence classes directly, representing millions of equivalent graphs as a single search node and achieving orders-of-magnitude speedups.
Bayesian Model Averaging
To account for structural uncertainty, Bayesian Model Averaging (BMA) computes the posterior probability of a causal feature by averaging over the model space. Tian et al. showed that searching for the top $k$ equivalence classes rather than individual DAGs captures a vastly larger portion of the cumulative posterior probability mass. This prevents the search from being dominated by minor, unidentifiable edge variations and yields much more accurate causal inferences under a fixed memory budget.
Amortized Generative Search
Modern deep learning approaches, such as Generative Flow Networks (GFlowNets), have also adopted this paradigm. While early implementations sampled individual DAGs sequentially, Liu et al. shifted the generation process to operate directly on CPDAGs. This focuses the generative model's capacity entirely on identifiable causal relationships rather than wasting probability mass on redundant graph permutations.
Beyond Standard Markov Equivalence
The core philosophy of equivalence class search—reducing search space complexity by grouping observationally identical models—extends beyond standard conditional independence.
Algebraic Equivalence
In linear Structural Equation Models (SEMs), models may share the same conditional independencies but differ in non-independence equality constraints. van Ommen et al. introduced the concept of algebraic equivalence classes by leveraging the "half-trek criterion." This approach collapses thousands of structurally distinct graphs containing complex latent confounders into a small set of algebraically distinct candidates, simplifying the fitting process and avoiding the convergence difficulties common to complex latent variable models.
Maximal Graphs for Hidden Variables
When a system contains arbitrary hidden variables, the space of possible graphs becomes infinitely large. To make search tractable, Evans characterized the conditions under which variables can be simplified based on the nested Markov property. This work proved that the search space can be restricted to a specific class of "maximal arid graphs" that uniquely capture all possible distributional constraints, simplifying causal discovery without sacrificing any representational power.
Key Foundational Work
Margin based Transductive Graph Cuts using Linear Programming (2007) — contributed 3 concept elements to this direction.
Enumerating Markov Equivalence Classes of Acyclic Digraph Models (2001) — contributed 1 concept elements to this direction.