Index: Causal Discovery

Causal Discovery

Routing Summary

This folder covers causal structure learning / discovery — learning the structure of directed acyclic graphs (DAGs / Bayesian networks) from data. The NOTEARS notes (Zheng et al., 2018) cover the continuous-optimization approach; the Constraint and Score-Based Discovery sub-topic covers the classical PC/FCI/GES/FCM families (Glymour, Zhang & Spirtes 2019).

• Want the NOTEARS paper in one page? → NOTEARS - Overview
• Need the problem setup (SEM, score functions, NP-hardness)? → DAG Structure Learning Problem
• Need the key theorem ($h(W)=\mathrm{tr}{e}^{W\circ W}-d$, acyclicity)? → Smooth Characterization of Acyclicity
• Need the optimization (augmented Lagrangian, L-BFGS, thresholding, Algorithm 1)? → NOTEARS Algorithm
• Need empirical results (vs FGS, SHD/FDR, Sachs data)? → NOTEARS Experiments
• Need the PC algorithm, FCI, GES, or LiNGAM/ANM (constraint- & score-based discovery)? → Constraint and Score-Based Discovery

Sub-topics

Sub-topic	Notes	Covers
Constraint and Score-Based Discovery	5	Markov & faithfulness assumptions / CPDAG, the PC algorithm & FCI (constraint-based), GES (score-based), functional causal models (LiNGAM, ANM) — Glymour, Zhang & Spirtes (2019)

Concept Map

Concept	Note	Type	Depends On	Key Result
Continuous reformulation of DAG learning	NOTEARS - Overview	overview	DAG Structure Learning Problem	Combinatorial → continuous program
Linear SEM + LS score	DAG Structure Learning Problem	concept	Confirmatory Factor Analysis and SEM	$F(W)=\frac{1}{2n}\Vert X-XW{\Vert }_F^2+\lambda \Vert W{\Vert }_1$
Matrix-exponential acyclicity	Smooth Characterization of Acyclicity	theorem	DAG Structure Learning Problem	$h(W)=\mathrm{tr}{e}^{W\circ W}-d=0⟺$ DAG
Acyclicity gradient	Smooth Characterization of Acyclicity	theorem	—	$\nabla h(W)=(e^{W\circ W}{)}^T\circ 2W$
Augmented-Lagrangian ECP	NOTEARS Algorithm	concept	Smooth Characterization of Acyclicity	${\min }_{W}F(W)$ s.t. $h(W)=0$; <10 dual steps
Hard thresholding	NOTEARS Algorithm	concept	Smooth Characterization of Acyclicity	Round $
Structure-recovery benchmarks	NOTEARS Experiments	example	NOTEARS Algorithm	Beats FGS on dense/large graphs; ≈ global optimum

Notes

• NOTEARS - Overview — CONTAINS: research question, the 4 contributions, NOTEARS acronym, undirected-GM analogy, lineage.
• DAG Structure Learning Problem — CONTAINS: Defs (data/SEM, induced graph $\mathsf{G}(W)$, linear SEM, LS score $F$), Programs (3) & (4), NP-hardness, landscape table of prior methods (exact / local / order / constraint / hybrid).
• Smooth Characterization of Acyclicity — CONTAINS: desiderata (a)–(d), Prop. 1 (infinite series $\mathrm{tr}(I-B{)}^{-1}=d$), Prop. 2 (matrix exp $\mathrm{tr}{e}^B=d$), Theorem 1 ($h(W)=\mathrm{tr}{e}^{W\circ W}-d$ + gradient), sign-cancellation example, proofs.
• NOTEARS Algorithm — CONTAINS: ECP (9), augmented Lagrangian $L^{\rho }$, dual ascent + Prop. 3 (linear convergence), L-BFGS / proximal quasi-Newton subproblem solve with soft-threshold closed form, thresholding, Algorithm 1 full pseudocode.
• NOTEARS Experiments — CONTAINS: ER/SF + Gauss/Exp/Gumbel design, SHD/FDR vs FGS (Fig. 3), Table 1 global-optimum comparison, Sachs real-data result, limitations & future work.

Cross-Cutting Concepts

• Linear SEM / weighted adjacency matrix $W$: the object of estimation; appears in DAG Structure Learning Problem (definition) and threads through every note.
• Matrix exponential $e^{W\circ W}$: the engine of both the constraint (Smooth Characterization of Acyclicity) and its $O(d^3)$ cost (NOTEARS Algorithm, NOTEARS Experiments).
• Nonconvexity / stationary points: introduced in Smooth Characterization of Acyclicity, handled in NOTEARS Algorithm, empirically assessed in NOTEARS Experiments.

Sources

• 1803.01422-NOTEARS.pdf — Zheng, Aragam, Ravikumar & Xing, DAGs with NO TEARS: Continuous Optimization for Structure Learning, NeurIPS 2018 (arXiv:1803.01422). Code: https://github.com/xunzheng/notears.

See Also

• Confirmatory Factor Analysis and SEM — structural equation models in the Bayesian setting
• Spurious Association and Confounds — DAG semantics for causal inference
• Nonparametric Causal Inference — related causal-modeling material