Source-linked AI summary
Causal Structure Learning
Christina Heinze-Deml, Marloes H. Maathuis, Nicolai Meinshausen
TL;DR
Causal structure learning seeks to recover causal graphs under assumptions that determine how well methods apply to data. The paper reviews several algorithms and their assumptions, then compares their empirical performance across settings where assumptions are met or violated. The comparison finds method clustering by algorithm class and identifies graph size and hidden-variable strength as especially important parameters.
Problem
Causal structure learning must recover causal graphs from data under assumptions about the data-generating process, motivating comparison across settings where those assumptions are met or violated.
Method
The paper reviews causal structure-learning algorithms and their assumptions, then compares them empirically in a simulation study across varied settings.
Results
The methods clustered into constraint-based, score-based, and other approaches, with graph size p and hidden-variable strength ρε being the most important parameters in the study setup.
Takeaways & Limitations
Algorithm performance depends on both the assumptions about the data-generating process and the specific implementation details of each algorithm.
Takeaways & Limitations
The study's conclusions are bounded by the assumptions made about the data-generating process and by the specific algorithm implementations evaluated.
Abstract
from arXiv · showhide
Graphical models can represent a multivariate distribution in a convenient and accessible form as a graph. Causal models can be viewed as a special class of graphical models that not only represent the distribution of the observed system but also the distributions under external interventions. They hence enable predictions under hypothetical interventions, which is important for decision making. The challenging task of learning causal models from data always relies on some underlying assumptions. We discuss several recently proposed structure learning algorithms and their assumptions, and compare their empirical performance under various scenarios.
1 INTRODUCTION
Causal graphical models extend graphical models by representing direct causal effects and supporting predictions under external interventions. The paper reviews causal structure-learning algorithms and compares them across settings where their assumptions hold or fail.
- Graphical models represent multivariate distributions with nodes for random variables and edges encoding allowed conditional dependencies.
- Causal graphical models interpret edges as direct causal effects, enabling predictions under arbitrary unseen interventions.
- Causal structure learning estimates a causal graph or aspects of one from data under explicit assumptions.
- The paper describes algorithms under different assumptions and compares their performance when those assumptions are met or violated.
- The paper proceeds from causal-model assumptions to target graphical objects, algorithms, simulations, results, and discussion.
2 THE MODEL
The paper formulates causality with structural equations whose mechanisms remain invariant under interventions, represents them as causal graphs, and studies assumptions including acyclicity, sufficiency, faithfulness, and noise structure.
- 2.1 Interventions: A linear structural equation model represents each variable as a weighted combination of other variables plus a noise contribution.
- 2.1 Interventions: Structural equations describe the generating mechanism, and autonomy assumes each equation remains invariant when other equations change.
- 2.1 Interventions: Do-interventions replace a structural equation with a forced value, whereas additive interventions add additional noise to that equation.
- 2.2 Graphical representation: The causal graph contains an edge when a coefficient is nonzero, so parents correspond to direct causes in the structural equations.
- 2.5 Assumptions: Acyclicity excludes feedback loops; cyclic models instead require conditions such as unique and stable equilibria.
- 2.5 Assumptions: Counterfactual joint noise distributions across interventions are unobservable and therefore unfalsifiable without additional assumptions.
- 2.5 Assumptions: Causal sufficiency excludes hidden variables, while faithfulness links d-separation relationships in the causal DAG to conditional independencies.
- 2.5 Assumptions: The paper considers Gaussian and t-distributed noise, homogeneous and heterogeneous settings, unknown shift-interventions, and known do-interventions.
3 METHODS
The paper compares causal structure-learning methods that target different graphical objects and operate under varied assumptions, data types, and levels of granularity. It evaluates five algorithm classes while focusing on ancestral relationships shared across output formats.
- Target graphical objects and comparison: Causal structure-learning methods differ in data requirements, assumptions about hidden variables and cycles, and the graphical objects they learn.These differences produce outputs ranging from directed graphs to partial ancestral graphs and determine the granularity of the learned causal structure.
- Target graphical objects and comparison: Under acyclicity, independent Gaussian errors, and observational data, the causal DAG is generally not identifiable; its Markov equivalence class can instead be represented by a CPDAG.With latent variables, methods may target MAGs or PAGs, which encode conditional independencies and ancestral information at coarser resolution.
- Target graphical objects and comparison: The comparison focuses on direct causes, represented by paG(j), and ancestors, represented by anG(j), for each variable Xj.Parents determine Xj's conditional distribution under interventions on other variables, while ancestors identify variables whose interventions can affect Xj.
- Algorithm classes and selection: The study includes constraint-based, score-based, hybrid, structural-equation, and invariance-based algorithms, selecting methods with R implementations.The selected methods include PC, rankPC, FCI, rankFCI, GES, rankGES, GIES, rankGIES, MMHC, LINGAM, and BACKSHIFT, while excluding time-series, mixed-data, and Bayesian methods.
- Constraint-based methods: PC learns a CPDAG through skeleton discovery, v-structure identification, and further edge orientations under acyclicity, causal faithfulness, and causal sufficiency.FCI modifies PC by dropping causal sufficiency, allowing arbitrarily many hidden variables and producing a PAG, but requires additional tests and orientation rules.
- Additional-restriction and invariance methods: LINGAM uses non-Gaussian linear acyclic models, whereas BACKSHIFT estimates causal structure through joint diagonalization and can accommodate latent confounding.BACKSHIFT's full identifiability depends on intervention settings that distinguish pairs of variables through noise-intervention variances.
4 EMPIRICAL EVALUATION
The study compares causal structure-learning methods across simulations that vary graph, noise, intervention, sample, and model-specification characteristics. Performance varies substantially: no method dominates globally, while method assumptions and simulation parameters shape which algorithms perform well.
- 4 EMPIRICAL EVALUATION: The comparison evaluates methods under model violations and seeks realistic boundaries in variables, sample size, and other parameters for reasonable graph reconstruction.Configurations and tuning options are varied before selecting the best configuration for each metric.
- 4.1 Data generation: The simulation varies observations, variables, graph density, noise, hidden-variable correlation, interventions, signal-to-noise ratio, cycles, and nonlinearities.Data are generated with at least one edge, and interventions assign each variable to one randomly selected setting.
- 4.3.1 Multi-dimensional scaling: Rank-based methods lie close to their non-rank counterparts, whereas LINGAM and BACKSHIFT are farthest from the other methods in the method-level MDS comparison.The simulation-setting MDS likewise separates regions where LINGAM or BACKSHIFT are optimal from regions favoring the other methods.
- 4.3.2 Pairwise comparisons: No globally dominant method appears across settings; related algorithms form performance blocks, while LINGAM and BACKSHIFT are substantially better or worse in many settings.Constraint-based methods form one block, score-based approaches another, and extensions or hybrid methods a third.
- 4.3.3 Which causal graphs can be estimated well?: Increasing p or hidden-variable correlation ρε is associated with higher equal-error-rates across methods; larger noise contributions and denser graphs show the same positive association.The correlation with intervention strength σZ is negative for every method except LINGAM, while strong interventions are expected to benefit BACKSHIFT.
- 4.3.4 Bounds on performance: NFP-ER is generally harder to keep low than NFN-ER, although LINGAM achieves very small NFP-ER values in some settings up to p ≈20.For isNoAncestor, the relative roles of NFN-ER and NFP-ER reverse because non-ancestral pairs are more abundant.
5 DISCUSSION
The paper provides an overview and empirical comparison of causal structure-learning methods, finding method-class clustering and strong effects from graph size and hidden-variable strength. It also identifies efficiency and methodological challenges that remain.
- The study surveys causal-model structure-learning methods available in R and conducts an extensive empirical comparison.
- Methods cluster into constraint-based, score-based, and other approaches, with methods from the same class behaving empirically similarly.
- Graph size p and hidden-variable strength ρε are the most important parameters in the simulation setup.
- Algorithmic success depends on assumptions about the data-generating process and on implementation details.
- More efficient algorithms and methods separating data-generation assumptions from implementation effects would be desirable.
6 APPENDIX
The appendix documents the software interfaces used to run the evaluated causal structure-learning methods and reports 842 unique simulation settings.
- Implementation: All methods were run through the CompareCausalNetworks package interface.The package calls the respective methods from their associated R packages.
- Implementation: BACKSHIFT used the backShift R package.
- Implementation: GES and rankGES used pcalg and CompareCausalNetworks, respectively.
- Implementation: GIES, rankGIES, FCI, rankFCI, MMHC, PC, and Rank PC used their listed pcalg, CompareCausalNetworks, or bnlearn implementations.
- Simulation settings: 842 unique simulation settings were generated across the study.The appendix tables count settings for each data-generation parameter value.
Edge density parameter
The simulation study varied the edge-density parameter across four specified values.
- Edge density parameter: The considered edge-density parameter values were 0.1, 0.2, 0.3, and 0.4.
Intervention type
The experiment distinguishes shift interventions from do-interventions and spans 417 and 425 settings.
- The intervention types are shift intervention and do-intervention.
- The experiment includes 417 and 425 settings.
Strength of the interventions
The experiment considers settings with and without model misspecification, with reported setting counts of 576, 266, 715, and 127.
- The reported setting counts include 576 and 266.
- The comparison distinguishes no model misspecification from model misspecification.
- The reported setting counts also include 715 and 127.