Equivalence and Synthesis of Causal Models

article1990UAI1,534 citationsBest Paper Award

Establishes graphical criteria and efficient algorithms for determining when different causal directed acyclic graphs represent identical observational dependencies, providing the theoretical foundation for learning causal structures from empirical data.

Listen

In scientific research, decision analysis, and data-driven systems, practitioners frequently use graphical causal models to understand relationships between variables and estimate risks. A central challenge in this practice is non-uniqueness: multiple distinct causal structures often produce identical observational data and probability distributions, making them experimentally indistinguishable. This ambiguity complicates causal reasoning, especially when key factors are unobserved, creating spurious correlations that traditional directed graphs cannot adequately represent.

The article establishes formal graphical criteria and canonical representations to determine when two causal models are equivalent. It demonstrates how these canonical structures can be used to extract genuine causal relationships directly from statistical observational data, both for fully observed systems and for embedded systems containing unobserved variables.

To address this challenge, the authors conducted theoretical analyses of graphical models known as directed acyclic graphs and their extensions. They evaluated causal structures using directional separation—a formal criterion for mapping conditional independence—and introduced hybrid graphs that incorporate bidirectional links to account for hidden common causes. The analysis establishes necessary and sufficient graphical conditions for model equivalence and formulates a step-by-step recovery algorithm to infer these structures from observational data in polynomial time.

The findings provide three primary insights. First, two standard causal models are observationally equivalent if and only if they share identical node adjacencies and the same uncoupled head-to-head junctions. Second, this equivalence generalizes to embedded models containing hidden variables, where equivalent systems can be uniquely summarized into a canonical completed pattern in polynomial time, proving that any complex embedded structure is equivalent to a simple graph with fewer than the square of the number of observable variables. Third, the authors developed a systematic three-step recovery algorithm that uses conditional independence tests to reliably reconstruct the invariant directional and structural components of the underlying causal model.

These findings demonstrate that causal directionality can be inferred strictly from statistical data without relying on chronological time stamps. For decision-makers and analysts, this provides a rigorous mathematical framework to distinguish between direct causes, potential causes, and spurious associations. It ensures that analytical and policy models do not assume unjustified causal directions, reducing the risk of flawed operational decisions based merely on observational correlations.

Organizations should adopt these canonical pattern representations and recovery algorithms when building causal and predictive models from empirical datasets. For standard graphs, teams can improve computational efficiency by using undirected Markov network cliques to bound the search space for separating sets. When moving to empirical implementations, analysts should apply sample cross-entropy measures to prevent small sample sizes from corrupting the inference of independence conditions.

The primary limitations of this approach stem from the practical challenge of inferring independence relations from finite, sampled data, as sample size requirements grow exponentially with the number of conditioning variables. Additionally, the baseline framework assumes the probability distribution is graph-isomorphic and does not fully accommodate deterministic functional dependencies without specialized extensions. Nevertheless, the theoretical results provide high confidence for establishing structural equivalence and discovering causal links when sample sizes are adequate.

Cognitive Systems Laboratory University of California directed acyclic graphs efficient algorithm graphical representations causal models Bayesian networks influence diagrams

arXiv: 1304.1108

No sufficiently relevant recommendations were found.

Paper: Optimal Structure Identification With Greedy Search, David Maxwell Chickering (2002). Builds directly on the characterization of Markov equivalence and edge operations in DAGs to prove the Meek conjecture for optimal greedy search in causal discovery.
Paper: Learning Bayesian networks: The combination of knowledge and statistical data, David Heckerman et al. (1994). Extends the principles of Markov equivalence to Bayesian scoring and score-equivalent structural learning over equivalence classes of directed acyclic graphs.
Paper: A Bayesian method for the induction of probabilistic networks from data, Gregory F. Cooper et al. (1992). Develops the foundational K2 Bayesian scoring algorithm to induce causal and probabilistic network structures from observational database cases.
Paper: The max-min hill-climbing Bayesian network structure learning algorithm, Ioannis Tsamardinos et al. (2006). Combines constraint-based conditional independence tests with Bayesian score-based search to learn causal graphical models and orientation classes efficiently.
Paper: A Linear Non-Gaussian Acyclic Model for Causal Discovery, Shohei Shimizu et al. (2006). Advances causal discovery beyond standard Markov equivalence classes by showing that non-Gaussian disturbance terms enable full orientation of linear causal graphs.
Paper: Direct and Indirect Effects, Judea Pearl (2001). Extends the graphical and structural causal model framework to formally define and identify direct, indirect, and path-specific effects.
Paper: A Tutorial on Learning with Bayesian Networks, David Heckerman (1999). Provides an accessible pedagogical framework illustrating how causal structures and Markov equivalence classes are learned and inferred from data.
Paper: Learning Bayesian Networks with the bnlearn R Package, Marco Scutari (2009). Implements modern constraint-based and score-based causal network learning algorithms grounded in conditional independence and equivalence classes.
Paper: Identifying Weight-Variant Latent Causal Models, Yuhang Liu et al. (2026). Investigates identifiability and causal graph recovery up to Markov equivalence in complex latent causal models under varying generative weights.

Cover for Equivalence and Synthesis of Causal Models

Abstract

Scientists often use directed acyclic graphs (days) to model the qualitative structure of causal theories, allowing the parameters to be estimated from observational data. Two causal models are equivalent if there is no experiment which could distinguish one from the other. A canonical representation for causal models is presented which yields an efficient graphical criterion for deciding equivalence, and provides a theoretical basis for extracting causal structures from empirical data. This representation is then extended to the more general case of an embedded causal model, that is, a dag in which only a subset of the variables are observable. The canonical representation presented here yields an efficient algorithm for determining when two embedded causal models reflect the same dependency information. This algorithm leads to a model theoretic definition of causation in terms of statistical dependencies.

Topics

directed acyclic graphs efficient algorithm graphical representations correlation analysis standard model stochastic processes directed graphs

Keywords

causal models Bayesian networks influence diagrams equivalence class equivalent DAGs unobserved variables hybrid graphs Markov network causal relationships canonical representations

1 Introduction
2 Patterns of Causal Models
3 Embedded Causal Models
4 Applications to the Synthesis of Causal Models
Recovery Algorithm
Acknowledgement
References

Knowls

Knowl 1 — Equivalence Criterion for Directed Acyclic Graphs
theoretical result
Two directed acyclic graphs (DAGs) $D_1$ and $D_2$ representing causal models over the same set of variables are statistically equivalent (meaning that every probability distribution parameterized over $D_1$ can be represented by $D_2$ , and vice versa, sharing the exact same set of d-separation independence assertions) if and only if they satisfy two conditions:
1. They possess the identical skeleton (the same set of undirected links/adjacencies).
2. They possess the same uncoupled head-to-head nodes (also known as v-structures or uncoupled colliders, where $a \rightarrow c \leftarrow b$ and $a$ is not adjacent to $b$ ).
Knowl 2 — Equivalence Criterion for Embedded Causal Models
theoretical result
Let an embedded causal model be a DAG $D$ defined over a set of variables $U_D$ , in which only a subset $U_O \subseteq U_D$ is observable and $U_D \setminus U_O$ represents latent/unobserved variables. Two embedded causal models are observationally equivalent over $U_O$ if and only if they have the exact same completed embedded pattern (hybrid graph).

Consequently, the completed embedded pattern serves as a canonical and unique characteristic representation for the entire observational equivalence class of any embedded DAG.
Knowl 3 — Inducing Paths and Adjacency in Embedded Causal Models
theoretical result
Let $D$ be a directed acyclic graph over variables $U_D$ with observable subset $U_O \subseteq U_D$ . Let $A_{ab}$ denote the union of ancestors of $a$ and $b$ in $D$ excluding the pair $\{a, b\}$ . An inducing path between two observable nodes $a, b \in U_O$ is any path $p$ in $D$ between $a$ and $b$ satisfying:
1. Every observable node on $p$ is a head-to-head node (collider) on $p$ .
2. Every head-to-head node on $p$ is in $A_{ab}$ .
For any two observable variables $a, b \in U_O$ and the pattern $P$ of $D$ restricted to $U_O$ , the following four conditions are equivalent:
1. $a$ and $b$ are adjacent in $P$ .
2. $a$ and $b$ are unseparable in $D$ over $U_O$ (no subset $S \subseteq U_O \setminus \{a,b\}$ d-separates $a$ and $b$ ).
3. $a$ and $b$ are not d-separated by $A_{ab} \cap U_O$ in $D$ .
4. $a$ and $b$ are connected by an inducing path in $D$ .
Knowl 4 — Constraint-Based Causal Model Recovery Algorithm
algorithm
Under the assumption that the observed probability distribution is DAG-isomorphic (faithful to a DAG causal structure), the underlying causal pattern can be reconstructed from conditional independence relationships using the following procedure:
Input: Set of observable variables $U_O$ , conditional independence oracle $I(\cdot, \cdot, \cdot)$
Output: Completed pattern graph $P$
for each pair of variables $a, b \in U_O$ do
    Search for a separating subset $S_{ab} \subseteq U_O \setminus \{a, b\}$ such that $I(a, S_{ab}, b)$ holds
    if no such $S_{ab}$ exists then
        Add an undirected edge between $a$ and $b$ in $P$
    end if
end for
for each pair of non-adjacent variables $a, b \in U_O$ with a common neighbor $c \in U_O$ ( $a - c - b$ ) do
    if $I(a, S_{ab} \cup \{c\}, b)$ is false then
        Add arrowheads pointing at $c$ , orienting the chain as $a \rightarrow c \leftarrow b$
    end if
end for
Complete $P$ by directing undirected edges without creating new uncoupled head-to-head nodes or strictly directed cycles
return $P$
For DAG models without latent variables, the search space for separating sets $S_{ab}$ can be restricted to cliques in the Markov network (the undirected graph linking variables dependent given all remaining variables) containing $a$ or $b$ , bounding the computational complexity by the size of the largest clique in the Markov network.
Knowl 5 — Model-Theoretic Definitions of Genuine and Potential Causes
definition
Let $\mathcal{P}$ denote the set of all patterns that are minimal I-maps consistent with an observed probability distribution.
- An observable variable $c$ is a genuine cause of an observable variable $e$ if $c$ causes $e$ in every consistent model; that is, every pattern in $\mathcal{P}$ contains the directed arrow $c \rightarrow e$ .
- An observable variable $c$ is a potential cause of an observable variable $e$ if $c$ causes $e$ in some consistent model (at least one pattern in $\mathcal{P}$ contains $c \rightarrow e$ ) and $e$ never causes $c$ in any consistent model (no pattern in $\mathcal{P}$ contains $e \rightarrow c$ ).
This non-temporal definition determines causal directionality directly from statistical dependencies and distinguishes genuine direct causal influence from unobserved common confounding.
Knowl 6 — Independence Characterization of Head-to-Head Junctions
theoretical result
In a directed acyclic graph $D$ , let the nodes $a, c, b$ form an uncoupled chain (meaning $a$ is adjacent to $c$ , $c$ is adjacent to $b$ , and $a$ is not adjacent to $b$ ). Then $c$ is a head-to-head node (collider) between $a$ and $b$ ( $a \rightarrow c \leftarrow b$ ) if and only if $a$ and $b$ are not d-separated by any conditioning set containing $c$ :

$a \rightarrow c \leftarrow b \in D \iff \neg I_D(a, S \cup \{c\}, b) \quad \forall S \subseteq U_D \setminus \{a, b, c\}$

where $I_D(X, Z, Y)$ denotes that $X$ and $Y$ are d-separated given $Z$ in $D$ , and $U_D$ is the set of all variables in $D$ .
Knowl 7 — Adjacency and Unseparability in Directed Acyclic Graphs
theoretical result
Let $a$ and $b$ be two distinct nodes in a directed acyclic graph $D$ . Let $A_{ab}$ denote the union of the ancestor sets of $a$ and $b$ (excluding $\{a, b\}$ ), and let $P_{ab}$ denote the union of the parent sets of $a$ and $b$ (excluding $\{a, b\}$ ). The following four statements are equivalent:
1. $a$ and $b$ are adjacent in $D$ (there is a directed link $a \rightarrow b$ or $b \rightarrow a$ ).
2. $a$ and $b$ are unseparable in $D$ (no set $S \subseteq U_D \setminus \{a, b\}$ d-separates $a$ and $b$ ).
3. $a$ and $b$ are not d-separated by $A_{ab}$ in $D$ .
4. $a$ and $b$ are not d-separated by $P_{ab}$ in $D$ .
Knowl 8 — Size Bound and DAG Representability of Embedded Causal Models
theoretical result
For any set of observable variables $U_O$ :
1. There are strictly fewer than $5^{|U_O|^2}$ distinct observational equivalence classes of embedded causal models over $U_O$ .
2. Every embedded causal model over $U_O$ is statistically equivalent to a simple DAG containing strictly fewer than $|U_O|^2$ total variables (including both observable and latent variables).
This follows because any pattern over $U_O$ has at most four edge types per pair ( $a - b$ , $a \rightarrow b$ , $a \leftarrow b$ , $a \leftrightarrow b$ ) or no edge, and each bidirectional link $a \leftrightarrow b$ can be realized by introducing a single hidden common parent $\alpha$ with links $\alpha \rightarrow a$ and $\alpha \rightarrow b$ .
Knowl 9 — Embedded Pattern Representation and Arrowhead Induction
model/method
Given a DAG $D$ over variables $U_D$ with observable subset $U_O \subseteq U_D$ , the rudimentary embedded pattern $P$ is a hybrid graph over $U_O$ containing undirected ( $-$ ), directed ( $\rightarrow$ ), and bidirectional ( $\leftrightarrow$ ) edges satisfying:
1. $a$ and $b$ are adjacent in $P$ if and only if $a$ and $b$ are not d-separated by any $S \subseteq U_O \setminus \{a, b\}$ in $D$ .
2. An arrowhead pointing at $b$ on the link between $a$ and $b$ (denoted $a \mathrel{\overline{\rightarrow}} b$ , covering $a \rightarrow b$ and $a \leftrightarrow b$ ) is placed if and only if there exists some $c \in U_O$ adjacent to $b$ but not adjacent to $a$ in $P$ such that both links $ab$ and $bc$ were induced by paths in $D$ that ended pointing at $b$ .
The completed embedded pattern is obtained by adding orientations to undirected links in $P$ subject to the constraints that no added arrowhead may (1) create a new uncoupled head-to-head node, or (2) create a strictly directed cycle (a directed cycle consisting solely of singly directed arrows).
Knowl 10 — Reliable Conditional Independence via Sample Cross-Entropy
equation
To prevent sample size degradation when testing conditional independence assertions $I(a, S, b)$ from empirical data, the independence relation is quantified via the sample conditional cross-entropy:

$\hat{H}(a, b \mid S) = \sum_{a, b, S} \hat{P}(a, b, S) \log \frac{\hat{P}(a, b \mid S)}{\hat{P}(a \mid S)\hat{P}(b \mid S)}$

where $\hat{P}$ denotes empirical sample frequency and the sum ranges over all valid instantiations of variables $a$ , $b$ , and conditioning set $S$ . Terms involving low cell counts (small $\hat{P}(a, b, S)$ ) are automatically discounted relative to better-sampled configurations.

Coverage note — Deterministic variable refinements of d-separation were omitted as they are cited as external prior work/deferred to future work.

References

1.H.M. Blalock, Causal Models in The Social Sciences. Macmillian, London, 1971.
2.O.D. Duncan, Introduction to Structural Equation Models. Academic Press, New York, 1975.
3.D. Geiger and J. Pearl, Logical and Algorithmic Properties of Independence and Their Application to Bayesian Networks, UCLA Cognitive Systems Laboratory, Technical Report CSD-890035 (R-123), February 1989. To appear in Annals of Mathematics and AI, Special Issue on Statistics and AI.
4.D. Geiger, T.S. Verma and J. Pearl, d-Separation: From Theorems to Algorithms, Proceedings, 5th Workshop on Uncertainty in AI, Windsor, Ontario, Canada, August 1989, pp. 118-124.
5.D. Geiger and T.S. Verma, Identifying Independence in Bayesian Networks, UCLA Cognitive Systems Laboratory, Technical Report CSD-890028 (R-116), To appear in Networks, John Wiley and Sons, Sussex, England, 1990.
6.C. Glymour, R. Scheines, P. Spirtes and K. Kelly. Discovering causal structure. Academic Press, New York, 1987.
7.R.A. Howard and J.E. Matheson, Influence Diagrams, chapter 8, in The Principles and Applications of Decision Analysis, Vol. II, Strategic Decisions Group, Menlo Park, California, 1981.
8.S.M. Olmsted, On Representing and Solving Decision Problems, Ph.D. Thesis, Engineering-Economic Systems Dept., Stanford University, Stanford California, 1984.
9.J. Pearl, D. Geiger and T.S. Verma, The Logic of Influence Diagrams, in R.M. Oliver and J.Q. Smith (Eds), Influence Diagrams, Belief Networks and Decision Analysis, John Wiley and Sons, Ltd., Sussex, England 1990. A shorter version, in Kybernetica, Vol. 25:2, 1989, pp. 33-44.
10.J. Pearl, Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann Publishers, Inc, San Mateo, California, 1988.
11.J. Pearl and T.S. Verma, The Logic of Representing Dependencies by Directed Graphs, Proceedings, AAAI Conference, Seattle, WA. July, 1987, pp. 374-379.
12.R.D. Shachter, Evaluating Influence Diagrams, in A.P. Basu (Eds), Reliability and Quality Control, Elsevier, 1985, pp. 321-344.
13.P. Spirtes, C. Glymour and R. Scheines, Causality from Probability, in G. McKee, ed., Evolving Knowledge in Natural and Artificial Intelligence, Pitman, 1990.
14.J .Q. Smith, Influence Diagrams for Statistical Modeling, The Annals of Statistics, Vol. 17(2):654-672, 1989.
15.T.S. Verma, Invariant Properties of Causal Models. In preparation.
16.T.S. Verma and J. Pearl, Causal Networks: Semantics and Expressiveness, UCLA Cognitive Systems Laboratory, Technical Report 870032 (R-65), June 1986. Also in Uncertainty in AI 4, R. Shachter, T.S. Levitt and L.N. Kanal (eds), Elsevier Science Publishers, 1990.
17.S. Wright, The Method of Path Coefficients. Ann. Math. Statistics 5:161-215, 1934.

Citation

MLA

Verma, T. S., and J. Pearl. “On the Equivalence of Causal Models”. arXiv, 2013, http://arxiv.org/abs/1304.1108v1.

APA

Verma, T. S., & Pearl, J. (2013). On the Equivalence of Causal Models. arXiv. http://arxiv.org/abs/1304.1108v1

Chicago

Verma, T. S., and J. Pearl. 2013. “On the Equivalence of Causal Models”. arXiv. http://arxiv.org/abs/1304.1108v1.

Harvard

Verma, T.S. and Pearl, J. (2013) “On the Equivalence of Causal Models”, arXiv [Preprint]. Available at: http://arxiv.org/abs/1304.1108v1.

Vancouver

1. Verma TS, Pearl J (2013) On the Equivalence of Causal Models. arXiv

BibTeX

@article{verma2013the,
  title = {On the Equivalence of Causal Models},
  author = {Verma, Tom S. and Pearl, Judea},
  year = {2013},
  journal = {arXiv},
  url = {http://arxiv.org/abs/1304.1108v1},
  eprint = {1304.1108}
}

Metadata:arXiv

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

Equivalence and Synthesis of Causal Models

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Equivalence Criterion for Directed Acyclic Graphs

Knowl 2 — Equivalence Criterion for Embedded Causal Models

Knowl 3 — Inducing Paths and Adjacency in Embedded Causal Models

Knowl 4 — Constraint-Based Causal Model Recovery Algorithm

Knowl 5 — Model-Theoretic Definitions of Genuine and Potential Causes

Knowl 6 — Independence Characterization of Head-to-Head Junctions

Knowl 7 — Adjacency and Unseparability in Directed Acyclic Graphs

Knowl 8 — Size Bound and DAG Representability of Embedded Causal Models

Knowl 9 — Embedded Pattern Representation and Arrowhead Induction

Knowl 10 — Reliable Conditional Independence via Sample Cross-Entropy

References

Citation

BibTeX

Access the Paper