Source-linked AI summary
A Survey on Causal Discovery: Theory and Practice
Alessio Zanga, Elif Ozkirimli, Fabio Stella
TL;DR
Causal discovery addresses how to recover causal graphs and quantify causal effects when relationships cannot be established from correlation alone. This survey synthesizes theory and practice across algorithms and settings, including observational and interventional data, tools, evaluation resources, and applications. It also identifies unresolved challenges involving missing and heterogeneous data.
Problem
Causal discovery must recover unknown causal graphs across a fragmented landscape of assumptions, problems, and solutions so causal effects can be identified and estimated.
Method
The paper provides a unified theoretical and practical survey of causal-discovery concepts, algorithms, intervention settings, evaluation resources, software, and applications.
Results
The survey organizes existing causal-discovery methods across observational and interventional settings and reports their assumptions, computational properties, tools, data, and applications.
Takeaways & Limitations
The survey helps readers compare causal-discovery algorithms and assess their results across differing assumptions, settings, evaluation resources, and practical tools.
Takeaways & Limitations
Causal discovery for heterogeneous data remains unresolved because pooling sources across distribution shifts can produce poor performance.
Abstract
from arXiv · showhide
Understanding the laws that govern a phenomenon is the core of scientific progress. This is especially true when the goal is to model the interplay between different aspects in a causal fashion. Indeed, causal inference itself is specifically designed to quantify the underlying relationships that connect a cause to its effect. Causal discovery is a branch of the broader field of causality in which causal graphs are recovered from data (whenever possible), enabling the identification and estimation of causal effects. In this paper, we explore recent advancements in causal discovery in a unified manner, provide a consistent overview of existing algorithms developed under different settings, report useful tools and data, present real-world applications to understand why and how these methods can be fruitfully exploited.
1. Introduction
Causal discovery recovers causal graph structures from data and prior knowledge to support causal-effect analysis. This survey organizes a fragmented literature across theories, algorithms, settings, and practical resources.
- Causal inference seeks to quantify the impact of causes on outcomes rather than merely measure correlation.
- Causal discovery learns graphical structures with causal interpretations when the underlying causal graph is unknown.
- The survey unifies causal-discovery algorithms that differ in assumptions, problems, and solutions while pursuing the same goal.
- The paper covers common concepts, observational algorithms, approaches that relax acyclicity, and experimental settings.
- Earlier surveys generally covered theoretical foundations, but few reported evaluation datasets, metrics, or software tools.
Software Packages
The survey addresses practical gaps in prior causal-discovery surveys by covering evaluation resources, tuning, software, and applications. It frames these materials as part of a broader comparison of methods and their use.
- Prior surveys rarely provided evaluation datasets, metrics, and software resources for causal-discovery methods.
- The survey discusses machine-learning, deep-learning, reinforcement-learning, time-series, high-level, and specialized causal-discovery approaches.
- The survey guides readers through algorithm comparisons by describing evaluation datasets and metrics, hyperparameter tuning, software packages, and practical applications.
2. Definitions and Notation
This section introduces graph notation, causal graphs, structural causal models, and the causal discovery problem. It also explains how algorithms recover graphs under observational or interventional data, with guarantees limited by assumptions and unobserved variables.
- Graph notation: Graphs represent variables as vertices and relationships as edges, which may be undirected or directed; directed paths, cycles, and DAGs specify further structure.A DAG is a directed graph without cycles.
- Causal models: Causal graphs encode cause-effect relationships, distinguishing causal edge directions from merely probabilistic relationships in Bayesian networks.A directed edge X →Y denotes that X causes Y, while reversing a causal edge changes the interpretation of the data-generating mechanism.
- Causal models: Structural causal models combine endogenous and exogenous variables, functions, and an exogenous distribution to represent both causal mechanisms and uncertainty.The model is defined as M = (V, U, F, P), with V observable, U unobservable, F functional, and P a joint distribution over exogenous variables.
- The causal discovery problem: Causal discovery seeks to recover the unknown graph generating a dataset, using observational or interventional distributions and often assuming a specific function class.An algorithm solves the problem when it converges to the true graph as sample size increases.
- The causal discovery problem: Soundness, completeness, consistency, and identifiability describe whether an algorithm recovers the true graph, the most informative graph, a data-consistent graph, or edge directions.Some methods identify only an equivalence class because remaining edge orientations cannot be determined without additional assumptions.
- Sufficiency and insufficiency: Causal sufficiency requires all causes of the observed variables to be observed; latent causes violate this condition and may require augmented graphs or methods such as FCI.In causally insufficient settings, observed variables can share unobserved parents, creating common latent causes.
3. Causal Discovery
Causal discovery algorithms recover causal structures from observational data using constraint-based, score-based, hybrid, and specialized approaches under different assumptions. Their guarantees, computational costs, handling of latent confounding, and empirical performance vary substantially across settings.
- Constraint-based Algorithms: Constraint-based algorithms infer graph structure from conditional independence tests, translating probabilistic independence into graphical separation under faithfulness.They can incorporate prior knowledge and accommodate different data types when the assumptions of the selected conditional independence test hold.
- Constraint-based Algorithms: 2^|V\{X,Y}| conditioning sets may be required for one variable pair in the worst case, producing exponential growth in constraint-based search.The limitation arises from the size of possible conditioning sets.
- Constraint-based Algorithms: PC builds a complete undirected graph, removes edges using conditional independence tests, and orients remaining edges from v-structures and acyclicity, returning a CPDAG.Undirected CPDAG edges remain reversible for the observational distribution.
- Constraint-based Algorithms: FCI extends PC to latent confounding and selection bias, using discriminating paths and new orientation rules for causally insufficient observational settings.A discriminating path requires specific adjacency, collider, and parent relationships in an ancestral graph.
- Hybrid Algorithms: ARGES addresses consistency weaknesses in hybrid GES by restricting moves to admissible edges, while GFCI combines score-based and constraint-based search for causal insufficiency.GFCI is described as asymptotically correct with unmeasured confounders; ARGES's forward phase is consistent under admissible moves.
- Specialized Algorithms: LiNGAM consistently estimates its connection matrix, whereas NOTEARS uses continuous optimization with O(n^3) matrix-exponential evaluation but may recover acyclic rather than causal graphs.LiNGAM targets non-Gaussian noise and causally insufficient datasets; NOTEARS thresholds small coefficients and can perform well when in-degree and sample size are large.
4. Causal Discovery with Cycles
Causal discovery methods for cyclic systems extend graphical criteria and algorithms beyond acyclic DAGs, while confronting equivalence, identifiability, and computational limits. The section surveys constraint-, ICA-, optimization-, and exact-search approaches for these settings.
- Cyclic causal models: Cyclic structural causal models contain feedback loops, so their conditional independencies may not be representable by any DAG.Despite this, cyclic models are used for feedback systems in sociology, economics, and biology.
- Graphical criteria: σ-separation generalizes d-separation to directed mixed graphs with cycles and latent variables, and reduces to d-separation for DAGs.It blocks paths using conditions involving strongly connected components, ancestors, and colliders.
- Constraint-based discovery: CCD was historically the only provably sound algorithm for general directed graphs, but its incomplete output PAG may omit features shared across an equivalence class.CCD is d-separation complete, meaning its PAG can represent an equivalence class with a single graph, but it is not complete in the broader sense.
- ICA-based discovery: LiNG adapts LiNGAM to cycles by recovering simple graphs without requiring acyclicity, but cyclic variants can admit multiple causal graphs.The missing acyclicity assumption removes the row permutation that would otherwise identify the best-fitting assignment; approximate or sparse ICA can reduce computational cost.
- Optimization-based discovery: σ-connection-graph discovery formulates causal discovery as a constrained optimization problem whose solutions may represent members of the same causal equivalence class.Conditional-independence statements receive confidence weights, and multiple optimal solutions can arise because invariant undirected edges are retained.
- Search complexity: Exact search is generally infeasible because causal discovery is inherently exponential, motivating branch-and-bound and constraint-pruning strategies.One reviewed method incrementally updates constraints and rules out incompatible extensions, while assuming acyclicity lowers execution time.
5. Causal Discovery with Interventions
Interventional causal discovery distinguishes observational, experimental, and counterfactual information, using do-calculus and intervention graphs to represent and exploit interventions. The section also defines intervention targets, equivalence, and factorized interventional distributions.
- Layers of causation: Observational, interventional, and counterfactual data form three nested layers of causation associated with progressively broader classes of queries.The interventional layer includes the observational setting as the special case with no intervention, while counterfactual reasoning adds hypothetical actions.
- Do-calculus: do-calculus formally represents interventions and identifies causal effects when a finite sequence of its rules yields a do-free expression.The do operator represents setting intervention variables to specified values, such as do(X = x).
- Intervention types: Perfect interventions remove incoming causal edges into their targets, whereas imperfect interventions alter the functions governing those causal dependencies.Perfect interventions are described as a special case of imperfect interventions, in which affected parameters are effectively set to zero.
- Intervention targets: An intervention target contains exactly the variables subjected to an intervention, and an intervention family is a set of such targets.The empty target represents the observational case; a conservative family leaves every variable untreated in at least one target.
- Intervention graphs: An intervention graph is obtained by removing every directed edge pointing to a vertex in the intervention target.This construction agrees with the graph surgery associated with do-interventions.
- Interventional distributions: Interventional distributions can be represented through a factorization that uses intervention-specific mechanisms for targeted variables and observational factors for variables outside the target.For variables not included in the intervention target, P(∅) supplies the observational distribution; perfect interventions can additionally be written with do-notation.
- Interventional equivalence: I-contradictory edges differ across interventional equivalence classes, making them useful for consistent causal discovery from intervention data.Their distinction reflects violations of the I-Markov property.
5.4. Learning with Interventions
Interventional causal discovery extends structural learning beyond observational data, addressing intervention targets that may be single, multiple, or unknown. The survey reviews score-, permutation-, constraint-, and differentiable approaches, along with their accuracy and scalability trade-offs.
- Intervention design: Single-variable interventions require n −1 experiments to identify the causal graph, whereas multi-variable interventions need only ⌊log(n)⌋+ 1 in the worst case.With randomized multi-variable interventions, O(log log(n)) can be achieved as a lower bound with high probability.
- Intervention design: Unknown intervention targets add complexity because the affected variables are not precisely identified.The survey treats unknown targets as a distinct structural-learning setting.
- Score-based methods: GIES adapts the two-phase GES search to interventional data by exploiting similarities between observational and interventional causal graphs.It traverses the search space through forward and backward phases until reaching a local score maximum.
- Permutation-based methods: IGSP restricts permutation search to intervention-coherent neighbors, prioritizing I-covered edges that are also I-contradictory and may improve the score.UT-IGSP extends this strategy to partially unknown intervention targets.
- Comparative performance: IGSP and UT-IGSP outperform GIES when dimensionality is below 10 vertices, while GIES is more efficient at pooling interventional datasets in higher-dimensional spaces.The survey notes that GIES is not consistent in general.
- Broader settings: Interventional methods also cover context pooling, latent variables, nonlinear cyclic models, and unknown targets, but their strengths differ in accuracy, assumptions, and scalability.FCI-JCI is faster under all three assumptions, backShift outperforms LiNG with O(|I| · n2 · m) complexity, and DCDI scales through O(n3) matrix-exponential computation.
6. Evaluation and Tuning
The survey presents datasets, graph- and intervention-oriented metrics, tuning strategies, and software resources for evaluating causal discovery methods. These components span real-world and synthetic data, structural recovery, causal statements, stability, complexity, and predictive performance.
- Evaluation datasets: Evaluation resources include real-world and synthetic datasets containing observational, interventional, or mixed data.Examples include biological, robotic, bivariate, and synthetic gene-expression benchmarks.
- Evaluation metrics: Adjacency precision and recall evaluate correctly predicted neighboring vertices using TP/(TP+FP) and TP/(TP+FN), respectively.These metrics assess the recovered graph skeleton rather than edge orientation.
- Evaluation metrics: Arrowhead precision and recall evaluate correctly predicted arrowheads, making them useful when graphical marks encode distinct causal statements.Their confusion-matrix entries are computed over arrowheads rather than merely edge presence.
- Evaluation metrics: Structural Hamming Distance counts the edge additions, deletions, and reversals needed to transform one graph into another.It measures graphical-model differences directly in terms of edge operations.
- Evaluation metrics: Structural Intervention Distance counts wrongly inferred interventional distributions and is related to adjustment sets and SHD.SID is defined over interventional distributions rather than only graph structure.
- Tuning and software: Tuning strategies select configurations using graph complexity, perturbation stability, or out-of-sample predictive performance.The survey discusses AIC/BIC, StARS with an instability threshold β, and OCT without parametric distributional assumptions.
- Tuning and software: Stable and reliable software implementations are presented as necessary for reproducible experimental results.The survey includes software packages alongside datasets, metrics, and tuning practices.
7. Practical Applications
The survey illustrates causal discovery in environmental economics, medicine, and psychology. These applications use recovered structures to study nonlinear dependencies, latent variables, background knowledge, longitudinal effects, and causal symptom pathways.
- Emissions, production, and energy use: A multivariate time-series application linked CO2 emissions, energy use, and economic production through nonlinear dependencies at global and regional levels.The analysis suggested that rapid energy-sector net-zero transitions may hinder global economic growth and supported coordinated regional policies.
- Causal discovery in medicine: FCI and FGES were compared with a literature-derived graph to study Alzheimer’s biological mechanisms under causal sufficiency and insufficiency assumptions.Differences between recovered structures helped assess the possible influence of unmeasured external variables and competing hypotheses.
- Causal discovery in medicine: In Alzheimer’s analysis, adding background knowledge significantly improved discovery, while longitudinal data revealed more edges and removed incorrect ones.The constraint-based approach performed lower and less stably across bootstrap samples than the score-based approach.
- Causal discovery in medicine: In schizophrenia data, estimated effects connected social and occupational functioning with socio-affective capacity and motivation, while longitudinal analysis revealed causal cycles over six months.The study used GFCI at baseline and after six months.
- Causal discovery in psychology: In alcohol-use and anxiety research, drinking craving was the main causal influence of drinking and was itself influenced by drinking to cope.Ambiguity in depression’s associations with social anxiety and stress suggested possible latent variables.
8. Conclusions and Discussion
The survey unifies causal discovery methods, evaluation criteria, software, tuning strategies, and datasets across theoretical and practical scenarios. It also identifies unresolved challenges involving time series, missing and heterogeneous data, and other real-world settings.
- The survey covers algorithms, evaluation criteria, software tools, tuning strategies, and public datasets across diverse causal-discovery scenarios.It considers unobserved variables, cyclical dependencies, nonlinear relationships, and unknown interventions.
- Time-series causal discovery remains outside the survey’s scope because temporal causal dependencies differ from static representations.The paper treats this as a separate topic requiring additional discussion, especially alongside the survey’s other topics.
- Missing-data causal discovery remains underexplored, with nonrandom missingness making imputation suboptimal through bias; recent advances are restricted to constraint-based approaches.
- Pooling heterogeneous data sources can produce poor performance under distribution shifts, leaving causal representation learning across multiple contexts unresolved.The shifts can arise when context variables differ substantially, including environmental changes.
- Current limitations also include non-identical overlapping variable sets, streaming data, and federated learning.
Funding
The paper acknowledges Ph.D. scholarship support from F. Hoffmann-La Roche Ltd.
- Alessio Zanga was granted a Ph.D. scholarship by F. Hoffmann-La Roche Ltd.