Causal Discovery – PC Algorithm, LiNGAM, NOTEARS and Learning DAGs from Observational Data

The most important question in data science is not “what predicts Y?” but “what causes Y, and what happens to Y if we intervene on X?” Answering the second question requires a causal graph — a directed acyclic graph (DAG) encoding which variables directly causally influence which others. In most real-world settings, this graph is not known: researchers disagree, domain knowledge is incomplete, and the literature contains contradictory claims. Causal discovery algorithms address this problem directly: given a dataset of observational measurements, recover the causal graph (or the set of graphs consistent with the data) automatically. This guide covers the PC algorithm and constraint-based discovery, LiNGAM for fully identifiable linear discovery, NOTEARS and continuous optimisation-based methods, the FCI algorithm for settings with latent confounders, and the practical workflow for applying causal discovery to real tabular datasets using Python.

Constraint-Based Discovery — PC and FCI Algorithms

Constraint-based causal discovery exploits the Causal Markov Condition: in the true causal DAG G, every variable is conditionally independent of its non-descendants given its direct parents. The PC algorithm recovers the causal graph by testing all conditional independence relationships implied by this condition and removing edges that are contradicted by the data. Phase 1 (skeleton learning): start with a complete undirected graph; for each pair of adjacent variables (X, Y), test whether they are conditionally independent given any subset S of their common neighbours, removing the edge X—Y if any separating set S is found and recording S as sep(X,Y). Phase 2 (orientation): orient edges by identifying v-structures X → Z ← Y (where X and Y are not adjacent but both adjacent to Z, and Z ∉ sep(X,Y)), then propagate orientations using Meek rules to avoid new v-structures or directed cycles. The connection to our causal inference guide is foundational: causal inference methods (do-calculus, backdoor adjustment, IV estimation) assume the causal graph is known; causal discovery provides the graph that those methods require. The connection to our hypothesis testing guide is direct: the conditional independence tests at the heart of PC (partial correlation tests for Gaussian data, kernel HSIC for nonlinear data) are statistical hypothesis tests with their own Type I and Type II error rates, and the PC algorithm’s reliability degrades as the number of tests grows with the number of variables.

FCI (Fast Causal Inference) extends PC to settings with latent common causes (unmeasured confounders). In the presence of latent variables, the observed marginal distribution may encode conditional dependencies that cannot be explained by direct causal links between observed variables — instead, bidirected edges X ↔ Y in the PAG (Partial Ancestral Graph) represent latent common causes. FCI outputs a PAG rather than a CPDAG, representing all MAGs (Maximal Ancestral Graphs) consistent with the observed data. FCI is the appropriate algorithm for biomedical and social science datasets where unmeasured confounders are virtually guaranteed. The practical cost is that PAGs are harder to interpret and less actionable than DAGs: the presence of a bidirected edge X ↔ Y indicates a latent common cause but does not identify it, and many causal effect identification results require a DAG rather than a PAG.

LiNGAM — Full DAG Identifiability from Non-Gaussian Data

LiNGAM (Shimizu et al., 2006) achieves a remarkable result: in a linear structural equation model X = BX + ε where B is the adjacency matrix and the noise terms ε are mutually independent and non-Gaussian, the full DAG is uniquely identifiable from the observational distribution — not just the Markov equivalence class. The key insight: Gaussian noise is the unique exception where the causal direction X → Y is statistically indistinguishable from Y → X. For any non-Gaussian noise distribution, the asymmetry between cause and effect is detectable via higher-order statistics (kurtosis, mutual information). ICA-LiNGAM applies ICA (Independent Component Analysis) to estimate the unmixing matrix W = B⁻¹, then recovers the causal order from the zero-pattern of W. DirectLiNGAM avoids ICA’s local optima by regressing each variable on the remaining variables and identifying the causal root (the variable whose residuals are independent of all other variables) iteratively. The connection to our linear algebra guide is direct: the B matrix factorisation and the ICA unmixing problem are fundamentally linear algebra problems involving permutation matrices and triangular decompositions. For time series causal discovery, VARLiNGAM combines a VAR (Vector AutoRegression) model with LiNGAM to identify both lagged (V_t-1 → V_t) and instantaneous (V_t → W_t) causal effects — connecting to our time series analysis guide.

NOTEARS, Continuous Optimisation and Practical Workflow

NOTEARS (Zheng et al., 2018) transforms DAG learning into a smooth optimisation problem. The key contribution is the acyclicity characterisation: a real matrix W ∈ ℝ^{d×d} is the adjacency matrix of a DAG if and only if tr(e^{W ⊙ W}) − d = 0, where e^{W ⊙ W} is the matrix exponential of the elementwise square. This constraint is differentiable everywhere, enabling the DAG learning problem to be solved as a penalised regression: min_W (1/2n)||X − XW^T||²_F + λ||W||₁ subject to h(W) = 0, where ||W||₁ is an L1 sparsity penalty and h(W) = 0 enforces the DAG structure. The augmented Lagrangian method solves this efficiently, producing a sparse weighted adjacency matrix where W_ij ≠ 0 indicates a direct causal edge X_i → X_j. NOTEARS scales to hundreds of variables — far beyond PC or FCI — making it the practical choice for genomics (eQTL networks with hundreds of genes) and financial networks with many interacting variables. DAG-GNN (Yu et al., 2019) and GRAN-DAG replace the linear structural equation with a neural network, recovering nonlinear causal graphs at the cost of increased computational complexity and identifiability challenges. For a practical causal discovery session, causal-learn (Python) provides PC, FCI, and LiNGAM in a unified scikit-learn-style API, and causalnex provides NOTEARS with Bayesian network inference for the learned graph structure. The connection to our Bayesian statistics guide is direct: after running causal discovery to learn the graph skeleton, Bayesian network parameter learning (estimating conditional probability tables or conditional Gaussian parameters) combines the discovered structure with the data to enable probabilistic inference — the full pipeline from graph learning to probabilistic prediction.

✦ SUMMARIZE THIS ARTICLE WITH AI

ChatGPT Perplexity Claude Grok

Causal inference (estimating effects given a known graph) is in our Causal Inference guide. Uplift modelling and CATE estimation that use causal graphs are in our Uplift Modelling guide. Bayesian statistics and Bayesian networks for parameter estimation on discovered graphs are in our Bayesian Statistics guide. Hypothesis testing for conditional independence tests (PC algorithm) is in our Hypothesis Testing guide. Time series causal discovery (VARLiNGAM, DYNOTEARS) connects to our Time Series Analysis guide. A/B testing as the gold-standard alternative (interventional data) is in our A/B Testing guide.