Searching the Space of Markov Equivalence Classes

21 concepts12 papers1 proposal

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.

Operating directly within the space of equivalence classes requires specialized search and optimization strategies across different learning paradigms.

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.

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.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 12 papers
  2. Version 1 · 2026-10-04 · 15 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_equivalence_class_search_1063064b,
  title = {equivalence class search},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/equivalence-class-search/rdr_1063064b28ba40918aeb10098e75f494},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_equivalence_class_search_1063064b_v2,
  title = {equivalence class search},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/equivalence-class-search/rdr_1063064b28ba40918aeb10098e75f494/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake