Causal Discovery and Structure Learning

Parent: data analysis · researched 2026-05-30T22:36:31.172Z· 23 sources · 12 concepts · skill da-32-causal-discovery

Causal discovery (a.k.a. structure learning) learns the causal graph itself

Overview

Causal discovery (a.k.a. structure learning) learns the causal graph itself [source]
from observational and/or interventional data - the edges and their directions — [source]
rather than assuming the graph and estimating an effect. This is the upstream [source]
problem to causal inference. [source]
This skill (discovery): "What is the causal structure? Which variables [source]
cause which?" → output is a graph (DAG, CPDAG, or PAG). [source]
da-12 (inference): "Given this DAG, what is the effect of X on Y?" → DiD, [source]
RDD, IV, propensity scores, synthetic control, backdoor/frontdoor adjustment. [source]
If the user already has/assumes a DAG and wants an effect estimate, defer to [source]
da-12-ab-testing-causal-inference. Use this skill only when the structure [source]
The hard truth of discovery: from purely observational data you usually cannot [source]
recover a single DAG - only an equivalence class of DAGs (a CPDAG or PAG). [source]
Pinning down direction requires extra assumptions (non-Gaussianity, nonlinearity), [source]
interventions, or time order. Always communicate which edges are oriented vs. [source]

1. Markov equivalence, CPDAGs, and what is identifiable

Two DAGs are Markov equivalent if they entail the same conditional [source]
independences - they have the same skeleton (undirected edges) and the same [source]
v-structures / colliders (A → C ← B with A, B not adjacent). Equivalent DAGs [source]
cannot be distinguished by observational independence tests alone (Verma & Pearl, [source]
1990; Andersson, Madigan & Perlman, 1997). [source]
A CPDAG (Completed Partially Directed Acyclic Graph, a.k.a. essential [source]
graph) represents the whole Markov equivalence class: directed edges are [source]
oriented in every member, undirected edges flip across members. [source]
Constraint- and score-based methods return a CPDAG, not a DAG. Reporting a [source]
single oriented DAG from such output is a common, serious error. [source]

2. Foundational assumptions (state them, always)

Causal Markov condition: each variable is independent of its [source]
non-descendants given its parents. [source]
Faithfulness: every conditional independence in the distribution is [source]
implied by the graph structure (no exact cancellations). Near-violations cause [source]
unstable orientation in finite samples (Spirtes, Glymour & Scheines, 2000). [source]
Causal sufficiency: no unmeasured common causes (latent confounders). PC [source]
and GES assume this; FCI does not. [source]
Acyclicity: most methods assume a DAG (no feedback loops). [source]
Identifiability hinges on these. Be explicit which the chosen method needs. [source]

A. Constraint-based (independence-test driven)

PC algorithm (Peter–Clark; Spirtes, Glymour & Scheines, 2000): start from a [source]
complete undirected graph, remove edges via conditional-independence (CI) tests, [source]
then orient colliders and propagate (Meek rules). Output: CPDAG. Assumes [source]
causal sufficiency + faithfulness. Order-dependence fixed by PC-stable [source]
(Colombo & Maathuis, 2014). CI tests: Fisher-Z (linear-Gaussian), G²/χ² [source]
(discrete), KCI (kernel, nonlinear). [source]
FCI (Fast Causal Inference) and RFCI: drop causal sufficiency - handle [source]
latent confounders and selection bias. Output: a PAG (Partial Ancestral [source]
Graph) over a MAG, with edge marks ○ (unknown), → (ancestor), ↔ (latent [source]
common cause) (Spirtes et al., 2000; Zhang, 2008). [source]

B. Score-based search

GES (Greedy Equivalence Search; Chickering, 2002): searches over CPDAG space [source]
with a two-phase forward (edge-add) / backward (edge-delete) greedy search, [source]
scoring with a decomposable, consistent score - BIC (continuous) or [source]
BDeu (discrete). Asymptotically returns the true equivalence class. fGES [source]
is the fast/parallel variant (TETRAD). [source]
GIES (Hauser & Bühlmann, 2012): GES extended to interventional data — [source]
searches over interventional Markov equivalence classes, exploiting experiments [source]
to orient more edges. [source]

C. Permutation / ordering search

GRaSP and BOSS (Lam, Andrews & Ramsey, 2022): search over variable [source]
orderings; more accurate and scalable than GES on many benchmarks, available [source]
in causal-learn and TETRAD. [source]

D. Functional causal models (FCMs) — orient beyond the equivalence class

By assuming a functional form, these identify a unique DAG, not just a CPDAG. [source]
LiNGAM - Linear, Non-Gaussian, Acyclic Model (Shimizu, Hoyer, Hyvärinen & [source]
Kerminen, 2006, JMLR 7:2003–2030): linear SEM with non-Gaussian noise → full [source]
causal order is identifiable. ICA-LiNGAM uses ICA; DirectLiNGAM [source]
(Shimizu et al., 2011) is regression-based and avoids ICA local optima. [source]
ANM - Additive Noise Models (Hoyer, Janzing, Mooij, Peters & Schölkopf, [source]
2008/2009): Y = f(X) + N with N ⟂ X. Nonlinear f breaks the X↔Y symmetry → [source]
cause/effect direction identifiable. [source]
Post-Nonlinear (PNL) model (Zhang & Hyvärinen, 2009): Y = g(f(X) + N) - most [source]
general identifiable FCM. In causal-learn. [source]

E. Continuous-optimization / gradient methods

Reframe combinatorial DAG search as smooth optimization with a differentiable [source]
acyclicity constraint - scales and integrates with deep learning. [source]
NOTEARS (Zheng, Aragam, Ravikumar & Xing, NeurIPS 2018): the acyclicity [source]
breakthrough - h(W) = tr(e^{W∘W}) − d = 0 is a smooth, exact characterization [source]
of acyclicity, solved via augmented Lagrangian. Originally linear; NOTEARS-MLP [source]
extends to nonlinear. [source]
GOLEM (Ng, Ghassami & Zhang, NeurIPS 2020): likelihood-based score with soft [source]
acyclicity - faster and more accurate than NOTEARS in the linear-Gaussian/EV [source]
DAG-GNN (Yu et al., ICML 2019): VAE/GNN variant for nonlinear and discrete [source]
Caveat: Reisach, Seiler & Weichwein (NeurIPS 2021, "Beware of the Simulated [source]
DAG") showed continuous-optimization methods can exploit varsortability — [source]
marginal-variance artifacts of synthetic data scaling. Standardize data and [source]
don't trust synthetic-benchmark wins blindly. [source]

F. Time-series causal discovery

Granger causality: X Granger-causes Y if past X improves prediction of Y [source]
beyond Y's own past. Predictive, not structural; fails with latent confounders / [source]
instantaneous effects / nonlinearity. Use only as a baseline. [source]
PCMCI / PCMCI+ (Runge et al., Science Advances 2019; PCMCI+ in UAI 2020): [source]
two-stage - a PC-style condition-selection step, then **Momentary Conditional [source]
Independence (MCI)** tests controlling for autocorrelation and indirect links. [source]
PCMCI+ adds contemporaneous links. Implemented in Tigramite; pairs with any [source]
CI test (ParCorr, GPDC, CMI). LPCMCI handles latent confounders. [source]
VAR-LiNGAM (Hyvärinen et al., 2010): combines a VAR model with LiNGAM to [source]
recover both lagged and instantaneous causal effects. [source]

Tools / Frameworks

causal-learn (py-why, Python; Zheng et al., 2024; docs [source]
https://causal-learn.readthedocs.io/): the reference Python toolkit - PC, FCI, [source]
GES, GRaSP, BOSS, LiNGAM family, ANM, PNL, CD-NOD, plus CI tests and graph [source]
utilities. Default first choice for general discovery. [source]
gCastle (Huawei Noah's Ark Lab; Zhang et al., 2021): gradient-based focus [source]
(NOTEARS, GOLEM, DAG-GNN, GraN-DAG, ...), PyTorch + GPU, data simulators, and a [source]
built-in metrics module (SHD, FDR, TPR, F1, NNZ). [source]
Tigramite (Runge; https://github.com/jakobrunge/tigramite): the standard for [source]
time-series discovery (PCMCI, PCMCI+, LPCMCI, RPCMCI). [source]
pcalg (R; Kalisch et al., JSS 2012): mature PC/FCI/RFCI/GES with IDA effect [source]
DoWhy (py-why; https://www.pywhy.org/dowhy/): primarily inference, but its [source]
GCM module and dowhy.causal_discovery wrap discovery; good for the [source]
discover-then-refute workflow. [source]
CausalNex (QuantumBlack): NOTEARS-based structure learning + Bayesian-network [source]
reasoning, with expert-knowledge constraints (tabu edges, required edges). [source]
TETRAD / py-tetrad: large library of search algorithms and the [source]
knowledge/background-constraint framework. [source]

Practical Patterns

Always inject background knowledge. Forbidden edges, required edges, and [source]
tiered time order (a cause can't follow its effect) dramatically reduce the [source]
equivalence class. Every major tool supports knowledge/tabu constraints - use [source]
Match method to assumptions and data type: [source]
Possible latent confounders → FCI / RFCI (get a PAG), not PC/GES. [source]
Linear + non-Gaussian noise → DirectLiNGAM (gets a full DAG). [source]
Nonlinear, continuous → ANM / PNL, or NOTEARS-MLP / DAG-GNN. [source]
Discrete/categorical → score-based with BDeu, or G²-test PC. [source]
High-dim time series → PCMCI+. [source]
Have interventions/experiments → GIES or interventional NOTEARS. [source]
Standardize/scale continuous variables before continuous-optimization [source]
methods to avoid varsortability artifacts. [source]
Bootstrap for edge stability. Resample, re-run discovery, and report [source]
edge-presence and orientation frequencies rather than one point graph. [source]
Discover → refute → estimate. Use discovery to propose a graph, validate [source]
with domain experts and refutation/sensitivity checks, then hand the validated [source]
DAG to da-12 for effect estimation. Discovery output is a hypothesis, not [source]
Evaluate with the right metric: [source]
SHD (Structural Hamming Distance): count of edge insert/delete/reverse [source]
ops to match the truth - lower is better; compare against the CPDAG, not a [source]
DAG, when methods return equivalence classes. [source]
SID (Structural Intervention Distance; Peters & Bühlmann, 2015): counts [source]
intervention-distribution errors - closer to what matters for downstream [source]
effect estimation than SHD. [source]
Also F1 / precision / recall on the skeleton, FDR, TPR. [source]

Anti-Patterns

Reporting a single DAG when the method returns a CPDAG/PAG. Undirected / [source]
circle-marked edges are genuinely undetermined; orienting them implies [source]
assumptions you didn't make. [source]
Treating Granger causality as structural causality. It's lagged prediction; [source]
silent on confounders and contemporaneous effects. [source]
Trusting synthetic-benchmark performance of NOTEARS-family methods without [source]
standardizing data (varsortability - Reisach et al., 2021). [source]
Ignoring latent confounders. Running PC/GES when unmeasured common causes are [source]
plausible yields confident but wrong edges. Use FCI or sensitivity analysis. [source]
Skipping faithfulness/sufficiency disclosure. Stakeholders must know the [source]
result is conditional on assumptions that can't be verified from data alone. [source]
Using discovery output directly for policy. Discovery proposes; it does not [source]
prove. Validate before acting. [source]
Doing effect estimation here. Backdoor adjustment, IV, DiD, propensity [source]
scores, synthetic control → da-12-ab-testing-causal-inference. [source]

Troubleshooting

Too many undirected edges in the CPDAG: expected with observational-only [source]
data. Add background knowledge, use an FCM method (LiNGAM/ANM) if assumptions [source]
hold, or collect interventional data. [source]
Unstable edges across runs/bootstraps: likely faithfulness near-violations, [source]
small n, or wrong CI test. Increase data, switch CI test (e.g., KCI for [source]
nonlinearity), use PC-stable. [source]
PC gives different graphs depending on variable order: use PC-stable [source]
(Colombo & Maathuis, 2014). [source]
Dense, implausible graph from NOTEARS: increase the L1 sparsity penalty, [source]
standardize data, threshold small weights; consider GOLEM. [source]
Nonlinear relationships missed: linear methods (Fisher-Z PC, linear NOTEARS, [source]
LiNGAM) can't see them - use KCI tests, ANM/PNL, NOTEARS-MLP, or DAG-GNN. [source]
Time-series links look confounded by autocorrelation: that's exactly what [source]
PCMCI (MCI step) controls for; plain Granger does not. [source]

References

Spirtes, Glymour & Scheines, Causation, Prediction, and Search, 2nd ed., 2000 - PC, FCI foundations. [source]
Andersson, Madigan & Perlman (1997) - characterization of Markov equivalence / CPDAGs. [source]
Chickering (2002) - Greedy Equivalence Search (GES). https://jmlr.org/papers/v3/chickering02b.html [source]
Hauser & Bühlmann (2012) - GIES (interventional GES). https://jmlr.org/papers/v13/hauser12a.html [source]
Shimizu, Hoyer, Hyvärinen & Kerminen (2006) - LiNGAM, JMLR. https://www.jmlr.org/papers/v7/shimizu06a.html [source]
Shimizu et al. (2011) - DirectLiNGAM, JMLR. https://jmlr.org/papers/volume12/shimizu11a/shimizu11a.pdf [source]
Hoyer et al. (2008/2009) - nonlinear additive noise models (ANM), NeurIPS. [source]
Zhang & Hyvärinen (2009) - Post-Nonlinear (PNL) model. https://arxiv.org/abs/1205.2599 [source]
Zheng, Aragam, Ravikumar & Xing (2018) - NOTEARS, NeurIPS. https://arxiv.org/abs/1803.01422 [source]
Ng, Ghassami & Zhang (2020) - GOLEM, NeurIPS. https://arxiv.org/abs/2006.10201 [source]
Yu et al. (2019) - DAG-GNN, ICML. https://arxiv.org/abs/1904.10098 [source]
Reisach, Seiler & Weichwein (2021) - "Beware of the Simulated DAG", NeurIPS. https://arxiv.org/abs/2102.13647 [source]
Colombo & Maathuis (2014) - order-independent PC-stable, JMLR. https://jmlr.org/papers/v15/colombo14a.html [source]
Lam, Andrews & Ramsey (2022) - GRaSP / BOSS. https://proceedings.mlr.press/v180/lam22a.html [source]
Zhang (2008) - augmented FCI orientation rules for PAGs, AIJ. [source]
Runge et al. (2019) - PCMCI, Science Advances. https://www.science.org/doi/10.1126/sciadv.aau4996 [source]
Runge (2020) - PCMCI+, UAI. https://proceedings.mlr.press/v124/runge20a.html [source]
Hyvärinen et al. (2010) - VAR-LiNGAM, JMLR. https://jmlr.org/papers/v11/hyvarinen10a.html [source]
Peters & Bühlmann (2015) - Structural Intervention Distance (SID). https://arxiv.org/abs/1306.1043 [source]
Zheng et al. (2024) - causal-learn, JMLR; docs https://causal-learn.readthedocs.io/ [source]
Zhang et al. (2021) - gCastle toolbox. https://arxiv.org/abs/2111.15155 [source]
Kalisch et al. (2012) - pcalg, JSS. https://www.jstatsoft.org/article/view/v047i11 [source]
Tigramite - https://github.com/jakobrunge/tigramite ; DoWhy - https://www.pywhy.org/dowhy/ ; CausalNex docs. [source]

Children

Constraint-based methods (PC, FCI) (frontier)
Score-based search (GES, GIES) (frontier)
Functional causal models (LiNGAM, ANM, PNL) (frontier)
Continuous-optimization methods (NOTEARS, GOLEM, DAG-GNN) (frontier)
Permutation search (GRaSP, BOSS) (frontier)
Markov equivalence classes and CPDAGs (frontier)
Faithfulness and causal sufficiency assumptions (frontier)
Latent confounders (FCI, PAGs/MAGs) (frontier)
Time-series causal discovery (Granger, PCMCI, VAR-LiNGAM) (frontier)
Interventional data (frontier)
Evaluation metrics (SHD, SID) (frontier)
Causal discovery tooling (causal-learn, gCastle, Tigramite, pcalg) (frontier)

Frontier under this node: Causal discovery tooling (causal-learn, gCastle, Tigramite, pcalg), Constraint-based methods (PC, FCI), Continuous-optimization methods (NOTEARS, GOLEM, DAG-GNN), Evaluation metrics (SHD, SID), Faithfulness and causal sufficiency assumptions, Functional causal models (LiNGAM, ANM, PNL), Interventional data, Latent confounders (FCI, PAGs/MAGs), Markov equivalence classes and CPDAGs, Permutation search (GRaSP, BOSS), Score-based search (GES, GIES), Time-series causal discovery (Granger, PCMCI, VAR-LiNGAM)

← the whole tree · 3D view· how to read this page