Causal Discovery and Structure Learning

Causal Discovery and Structure Learning

Overview

Causal discovery (a.k.a. structure learning) learns the causal graph itself from observational and/or interventional data — the edges and their directions — rather than assuming the graph and estimating an effect. This is the upstream problem to causal inference.

• This skill (discovery): “What is the causal structure? Which variables cause which?” → output is a graph (DAG, CPDAG, or PAG).
• da-12 (inference): “Given this DAG, what is the effect of X on Y?” → DiD, RDD, IV, propensity scores, synthetic control, backdoor/frontdoor adjustment.

If the user already has/assumes a DAG and wants an effect estimate, defer to da-12-ab-testing-causal-inference. Use this skill only when the structure is the unknown.

The hard truth of discovery: from purely observational data you usually cannot recover a single DAG — only an equivalence class of DAGs (a CPDAG or PAG). Pinning down direction requires extra assumptions (non-Gaussianity, nonlinearity), interventions, or time order. Always communicate which edges are oriented vs. undetermined.

Core Concepts

1. Markov equivalence, CPDAGs, and what is identifiable

Two DAGs are Markov equivalent if they entail the same conditional independences — they have the same skeleton (undirected edges) and the same v-structures / colliders (A → C ← B with A, B not adjacent). Equivalent DAGs cannot be distinguished by observational independence tests alone (Verma & Pearl, 1990; Andersson, Madigan & Perlman, 1997).

• A CPDAG (Completed Partially Directed Acyclic Graph, a.k.a. essential graph) represents the whole Markov equivalence class: directed edges are oriented in every member, undirected edges flip across members.
• Constraint- and score-based methods return a CPDAG, not a DAG. Reporting a single oriented DAG from such output is a common, serious error.

2. Foundational assumptions (state them, always)

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

Methodology — algorithm families

A. Constraint-based (independence-test driven)

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

B. Score-based search

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

C. Permutation / ordering search

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

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

By assuming a functional form, these identify a unique DAG, not just a CPDAG.

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

E. Continuous-optimization / gradient methods

Reframe combinatorial DAG search as smooth optimization with a differentiable acyclicity constraint — scales and integrates with deep learning.

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

F. Time-series causal discovery

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

Tools / Frameworks

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

Practical Patterns

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

Anti-Patterns

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

Troubleshooting

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

References

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