Causal Discovery Algorithm

These algorithms use conditional independence tests to prune edges from a fully connected graph. The foundational PC algorithm systematically tests pairs of variables for independence given conditioning sets of increasing size. If X and Y are independent given some set Z, the edge between them is removed. The resulting skeleton is then oriented using collider detection rules (v-structures). Key assumptions include faithfulness—that all observed conditional independencies correspond to d-separations in the true causal graph—and causal sufficiency, meaning no unmeasured common causes exist. Constraint-based methods are asymptotically correct but sensitive to individual test errors, which can cascade through the orientation phase.

Score-based algorithms search over the space of possible Directed Acyclic Graphs (DAGs) and assign a numerical score to each candidate structure, selecting the one that optimizes the trade-off between fit and complexity. Common scoring functions include the Bayesian Information Criterion (BIC) and the Bayesian Dirichlet equivalence uniform (BDeu) score. The combinatorial explosion of possible DAGs—super-exponential in the number of variables—makes exhaustive search infeasible. Practical implementations use greedy hill-climbing, tabu search, or simulated annealing to navigate the space. The Greedy Equivalence Search (GES) algorithm operates on equivalence classes rather than individual DAGs, improving computational efficiency while maintaining asymptotic correctness under the same assumptions as constraint-based methods.

Functional causal models (FCMs) exploit asymmetries in the data-generating process to distinguish cause from effect, going beyond the Markov equivalence classes that constraint-based and score-based methods can identify. The Linear Non-Gaussian Acyclic Model (LiNGAM) assumes linear relationships with non-Gaussian noise terms. By leveraging Independent Component Analysis (ICA), LiNGAM uniquely identifies the full causal ordering and connection strengths without requiring conditional independence tests. Extensions include additive noise models (ANMs) for nonlinear relationships and post-nonlinear models that can handle sensor distortions. These methods can resolve the direction of two-variable causal relationships—something constraint-based methods cannot do without a third variable.

Hybrid algorithms combine constraint-based and score-based strategies to balance computational efficiency with statistical robustness. A typical pipeline first applies fast conditional independence tests to restrict the search space to a sparse skeleton, then uses score-based optimization to orient edges within that constrained space. The Max-Min Hill-Climbing (MMHC) algorithm exemplifies this approach: it uses the Max-Min Parents and Children (MMPC) constraint-based subroutine to identify candidate parent-child sets for each variable, then applies a greedy hill-climbing search restricted to those candidates. This decoupling dramatically reduces the number of score evaluations required, making causal discovery tractable on datasets with hundreds of variables while maintaining strong theoretical guarantees.

When data includes temporal ordering, algorithms exploit Granger causality principles and dynamic structural equation models to infer causal relationships from lagged dependencies. The Peter-Clark Momentary Conditional Independence (PCMCI) algorithm extends constraint-based methods to time series by combining a modified PC algorithm with momentary conditional independence tests that condition on the past of all variables. This addresses the autocorrelation and time-lagged confounding that plague naive applications of static causal discovery to temporal data. The output is a time-series graph with nodes representing variables at different time lags, distinguishing contemporaneous from lagged causal effects. Applications include climate teleconnection analysis and neural effective connectivity mapping.

Real-world datasets frequently violate the causal sufficiency assumption due to unmeasured confounders. Algorithms designed for latent variable scenarios produce Maximal Ancestral Graphs (MAGs) or Partial Ancestral Graphs (PAGs) instead of standard DAGs. The Fast Causal Inference (FCI) algorithm and its efficient variant RFCI (Really Fast Causal Inference) output PAGs that explicitly represent latent confounding with bidirected edges and selection bias with undirected edges. These graphs encode equivalence classes of MAGs, distinguishing between edges that are definitively present, definitively absent, and those whose orientation remains ambiguous given the latent structure. FCI-based methods are essential for genomic applications where unmeasured genetic or environmental factors are pervasive.

A graphical representation of causal assumptions where nodes represent variables and directed edges represent direct causal effects. The acyclic constraint prohibits feedback loops, ensuring no variable can cause itself. Causal discovery algorithms output a DAG or an equivalence class of DAGs. Key properties include:

• d-separation: A graphical criterion for reading conditional independencies from the DAG structure
• Markov equivalence: Two DAGs are Markov equivalent if they encode the same set of conditional independencies
• Faithfulness assumption: The joint probability distribution contains no conditional independencies beyond those implied by the DAG structure

A constraint-based causal discovery algorithm named after its creators, Peter Spirtes and Clark Glymour. It learns a partial ancestral graph by systematically testing conditional independence relationships. The algorithm proceeds in three phases:

• Skeleton identification: Start with a fully connected undirected graph and remove edges where variables are unconditionally independent
• V-structure orientation: Identify collider patterns (X → Z ← Y) where X and Y are independent unconditionally but dependent conditional on Z
• Meek rules propagation: Apply orientation rules to maximize the number of directed edges without creating cycles or additional v-structures

The PC algorithm assumes causal sufficiency (no unobserved confounders) and faithfulness.

Causal discovery algorithms fall into two broad methodological categories:

• Constraint-based methods (e.g., PC, FCI): Use statistical tests of conditional independence to prune edges and orient causal directions. They rely on the faithfulness assumption and are sensitive to individual test errors
• Score-based methods (e.g., GES, NOTEARS): Search over the space of possible DAGs to optimize a goodness-of-fit score, such as the Bayesian Information Criterion (BIC) or Minimum Description Length (MDL). These methods treat causal discovery as a combinatorial optimization problem
• Hybrid methods (e.g., MMHC): Combine constraint-based skeleton learning with score-based edge orientation for computational efficiency Score-based methods are often more robust to small sample sizes but can be computationally prohibitive in high-dimensional settings.

The Fast Causal Inference (FCI) algorithm extends constraint-based discovery to settings with latent confounders and selection bias. Unlike the PC algorithm, FCI does not assume causal sufficiency. It outputs a Partial Ancestral Graph (PAG) that represents an equivalence class of Maximal Ancestral Graphs (MAGs). Key innovations include:

• Possible-D-SEP sets: Larger conditioning sets that account for paths through unobserved variables
• Bidirectional edges (↔): Indicate the presence of an unmeasured confounder between two variables
• Circle endpoints (∘): Represent uncertainty about edge orientation FCI is essential for biomedical applications where unmeasured genetic or environmental confounders are ubiquitous.

A formal mathematical framework developed by Judea Pearl for reasoning about interventions from observational data. The do-operator—denoted do(X = x)—represents an external intervention that sets variable X to value x, severing its incoming causal edges. Do-calculus provides three rules for transforming expressions involving interventions into estimable quantities:

• Rule 1 (Insertion/deletion of observations): Allows adding or removing conditioning on variables irrelevant to the intervention
• Rule 2 (Action/observation exchange): Permits replacing an intervention with conditioning when they have the same effect
• Rule 3 (Insertion/deletion of actions): Allows removing interventions on variables that do not affect the outcome Do-calculus provides the theoretical foundation for determining whether a causal effect is identifiable from observational data given a causal graph.

The statistical engine underlying constraint-based causal discovery. A conditional independence test evaluates whether two variables X and Y are independent given a conditioning set Z. Common tests include:

• Partial correlation test: For linear Gaussian data, tests whether the partial correlation coefficient ρ(X,Y|Z) is zero
• Kernel-based conditional independence (KCI): A non-parametric test using reproducing kernel Hilbert spaces for non-linear dependencies
• Conditional mutual information (CMI): Estimates information-theoretic dependence; zero CMI implies conditional independence
• G-squared test: A likelihood ratio test for discrete variables The choice of test dramatically impacts algorithm performance. False positive errors (incorrectly removing edges) propagate through orientation steps, while false negatives (failing to remove edges) produce dense, uninformative graphs.