Causal Graph Discovery

The foundational representation in causal discovery where nodes represent variables and directed edges encode direct causal influence. The acyclic constraint ensures no feedback loops, meaning a variable cannot be its own cause. DAGs are the output of constraint-based algorithms like the PC algorithm and score-based methods like GES (Greedy Equivalence Search). Each DAG implies a set of conditional independence relationships that can be tested against observational data to validate or refute the proposed causal structure.

Multiple DAGs can encode the exact same set of conditional independence statements, forming a Markov equivalence class. This means observational data alone often cannot distinguish between certain causal structures. These classes are represented by Completed Partially Directed Acyclic Graphs (CPDAGs) or Partial Ancestral Graphs (PAGs) when latent confounders are present. Understanding equivalence classes is critical because it defines the fundamental limits of what can be learned from purely observational data without experimental intervention.

Algorithms that use statistical conditional independence tests to prune edges and orient causal directions. The classic PC algorithm (named after Peter Spirtes and Clark Glymour) works by:

• Starting with a fully connected undirected graph
• Removing edges between variables found to be conditionally independent given any subset of other variables
• Orienting v-structures (colliders) where two non-adjacent nodes both cause a common effect
• Applying orientation propagation rules to infer remaining edge directions

These algorithms search over the space of possible DAGs to find the structure that optimizes a goodness-of-fit score penalized by model complexity. Common scores include the Bayesian Information Criterion (BIC) and the Bayesian Dirichlet equivalence score (BDeu). Greedy Equivalence Search (GES) operates in two phases: a forward phase that greedily adds edges to improve the score, and a backward phase that removes edges. Score-based methods typically scale better to high-dimensional problems than constraint-based approaches.

A framework that assumes each variable is generated as a deterministic function of its direct causes plus independent noise. Unlike constraint and score-based methods that rely on conditional independence, FCMs exploit asymmetries in the joint distribution to distinguish cause from effect. Key algorithms include:

• LiNGAM (Linear Non-Gaussian Acyclic Model): Uses independent component analysis on non-Gaussian data
• ANM (Additive Noise Model): Tests whether the residual is independent of the hypothesized cause
• PNL (Post-Nonlinear Model): Handles nonlinear sensor distortions after causal mixing

The do-operator, formalized by Judea Pearl, represents an external intervention that sets a variable to a specific value, severing its incoming causal edges. Do-calculus provides three rules for transforming expressions involving interventions into expressions computable from observational data alone. This enables:

• Identifying causal effects from observational and mixed experimental data
• Determining which variables must be measured to estimate a target causal effect
• Deriving identifiability conditions for causal queries in the presence of unobserved confounders

The formal mathematical framework for representing causal relationships as a set of structural equations. An SCM defines a directed acyclic graph (DAG) where each node's value is a function of its direct causes and an independent noise term.

• Encodes intervention distributions via the do-operator
• Enables generation of counterfactual explanations for GNN predictions
• Foundation for the Causal Hierarchy: association, intervention, and counterfactuals
• Distinct from purely statistical graphical models like Bayesian networks

A class of algorithms that infer causal structure by testing for conditional independencies in observational data. The PC algorithm (named after Peter and Clark) and FCI (Fast Causal Inference) are canonical examples.

• PC algorithm: Assumes causal sufficiency (no unobserved confounders)
• FCI algorithm: Handles latent confounders and selection bias
• Uses statistical tests like partial correlation or mutual information
• Outputs a Markov equivalence class of possible DAGs

Techniques that search over the space of possible DAGs to find the structure that optimizes a goodness-of-fit score penalized by model complexity. Greedy Equivalence Search (GES) and NOTEARS are prominent approaches.

• GES: Performs a greedy search over Markov equivalence classes
• NOTEARS: Reformulates the DAG constraint as a continuous optimization problem using a differentiable acyclicity penalty
• Scores include BIC, BDeu, and minimum description length
• Scales to high-dimensional settings with sparsity priors

A framework that leverages asymmetries in the data-generating process to identify causal direction. Unlike constraint-based methods, FCMs can distinguish between causally equivalent DAGs by modeling the functional form of relationships.

• LiNGAM: Assumes linear, non-Gaussian relationships; uses independent component analysis
• ANM (Additive Noise Model): Identifies direction by testing independence between residuals and hypothesized causes
• PNL (Post-Nonlinear Model): Handles sensor distortions via a nonlinearity applied after additive noise
• Exploits the principle that cause and mechanism are independent

The formal machinery for reasoning about controlled experiments and their effects. The do-operator, denoted do(X=x), represents an external intervention that sets a variable to a specific value, severing its incoming causal edges.

• Do-calculus: Three rules for transforming expressions with interventions into estimable quantities from observational data
• Enables identifiability analysis: determining if a causal effect can be estimated without a randomized trial
• Critical for evaluating causal graph discovery outputs against interventional data
• Underpins Pearl's back-door and front-door adjustment criteria

A statistical hypothesis test for determining whether one time series is useful in forecasting another. While not true causality in the Pearlian sense, it is widely used for temporal causal discovery in dynamic graphs.

• Tests if past values of X provide statistically significant information about future values of Y beyond Y's own history
• Extended to multivariate and nonlinear settings via vector autoregressive models and kernel methods
• Granger-Graph: A directed graph where edges represent Granger-causal relationships
• Applied in neural dynamics, fMRI analysis, and financial contagion modeling