PaperlayerView exact revision on arXiv

Source-linked AI summary

D'ya like DAGs? A Survey on Structure Learning and Causal Discovery

Matthew J. Vowels, Necati Cihan Camgoz, Richard Bowden

arXiv:2103.02582v2cs.LGstat.MEstat.ML

TL;DR

Causal discovery seeks structure from data because experiments are often unavailable, yet observational structure does not automatically establish causality. This survey reviews background theory and structure-discovery methods, emphasizes continuous optimization, and discusses resources, scalability, and the assumptions behind interpreting structure causally.

  • Problem

    Experiments may be too costly, unethical, or impractical, creating a need for methods that discover causal structure from observational data.

  • Method

    The paper surveys background theory and structure-discovery methods, primarily emphasizing continuous optimization alongside combinatoric approaches and practical resources.

  • Results

    The survey synthesizes structure-discovery methods and discusses how observational, mixed, and interventional data relate to causal interpretation under assumptions.

  • Takeaways & Limitations

    Causal discovery can support exploratory candidate links and, with suitable data and assumptions, may help identify models corresponding to external cause-effect relationships.

  • Takeaways & Limitations

    Most continuous optimization approaches have been evaluated only on low-dimensional problems, partly because common acyclicity constraints require O(d^3) computations.

Abstract

from arXiv · show

Causal reasoning is a crucial part of science and human intelligence. In order to discover causal relationships from data, we need structure discovery methods. We provide a review of background theory and a survey of methods for structure discovery. We primarily focus on modern, continuous optimization methods, and provide reference to further resources such as benchmark datasets and software packages. Finally, we discuss the assumptive leap required to take us from structure to causality.

1 INTRODUCTION

Causal understanding matters across science and applications, but causal discovery often must rely on observational data when interventions are costly, unethical, or impractical. This survey reviews background theory and structure-discovery methods, emphasizing continuous optimization while stressing caution in moving from learned structure to causality.

  • Causal understanding is central to science, intelligence, and applications including policy, medicine, law, social science, and biology.
  • Interventions are often unavailable because experiments can be costly, ethically concerning, or impractical, leaving researchers dependent on observational data.
  • Observational data may omit relevant variables, creating hidden or latent-factor challenges for causal discovery.
  • The survey reviews background theory and structure-discovery methods using observational or mixed observational and experimental data.
  • It primarily expands coverage of continuous optimization approaches beyond shorter reviews focused on combinatoric methods, and points readers to datasets and software.
  • The survey closes by emphasizing skepticism and care when interpreting learned structure causally from observations.

2 BACKGROUND - DEFINITIONS AND ASSUMPTIONS

The background introduces graphical and structural representations for causal reasoning, together with assumptions governing conditional independence, identifiability, and hidden confounding. These frameworks can support causal questions from observational data only in principle and under strong assumptions.

  • The survey uses structured graphical representations and defines key concepts and assumptions for structure discovery.
  • 2.1 Causality and SCMs: Structural causal models represent causal effects through interventions that replace equations for variables in X with fixed values.
  • 2.1 Causality and SCMs: Graphical and structural frameworks can, under strong assumptions, use observational data to address how, why, and what-if questions.
  • 2.2 Graphical Models: A graph encodes variables as vertices and relationships as directed, undirected, bidirected, partially directed, or nondirected edges.
  • 2.2 Graphical Models: DAGs are fully directed graphs without cycles, although cyclic and feedback phenomena can occur in nature.
  • 2.3 The Markov Assumption, d-Separation, and d-Faithfulness: d-faithfulness requires graph-implied conditional independencies to appear in the joint distribution, but path cancellation can violate this assumption.
  • 2.4 Markov Equivalence Class (MEC) and CPDAGs: Conditional independencies may fail to identify one DAG uniquely, producing Markov equivalence classes represented by CPDAGs.
  • Unobserved confounding can substantially bias observational effect estimates, motivating graph representations with bidirected edges.

3 STRUCTURE DISCOVERY METHODS

Structure discovery uses constraint tests, graph scores, structural asymmetries, and interventions, but causal direction generally requires additional assumptions or experimental information. The survey emphasizes how these approaches identify or narrow graph structures under different conditions.

  • Constraint-based approaches: Constraint-based methods test conditional independencies, often returning a graph representing a Markov equivalence class rather than a unique DAG.Their independence tests require large samples to be reliable.
  • Score-based approaches: Score-based methods evaluate candidate graphs with scoring functions such as BIC, MDL, BGe, BDe, and BDeu.The objective scores a candidate graph against empirical data.
  • Structural asymmetries: Observational data alone cannot always distinguish opposite structural directions, but functional or parametric assumptions can expose asymmetries useful for identification.Examples include linear relationships with non-Gaussian errors and nonlinear additive-noise models.
  • Structural asymmetries: Information-geometric identification assumes deterministic, sufficiently nonlinear mechanisms and may be undermined by adaptation between cause and effect.The approach uses dependence between the effect distribution and the inverse mechanism.
  • Interventions: Interventions narrow a Markov equivalence class by changing or removing relationships according to whether the intervened variable is a cause or effect.Hard interventions can orient an otherwise undirected edge by comparing the resulting distributions.
  • Causality over time and evaluation: Granger causality tends to fail with contemporaneous effects because of identifiability difficulties, and requires separability that is rarely satisfied in dynamic systems.Structural Interventional Distance instead counts intervention effects that would be incorrect under an estimated graph.

4 COMBINATORIC/SEARCH BASED APPROACHES

Combinatoric and search-based methods address structure discovery through discrete graph exploration, but their scalability is constrained by the super-exponential number of possible DAGs. The survey organizes these methods by approach, assumptions, interventions, and graph output.

  • Search complexity: The number of possible DAGs grows super-exponentially, exceeding 4 × 10^18 for 10 variables and making graph search NP-hard.This complexity motivates continuous optimization approaches.
  • Approach categories: The survey’s non-continuous methods include constraint-based, score-based, asymmetry-based, hybrid, and sampling-based approaches.Sampling-based methods measure belief in graph structures by sampling from a posterior.
  • Assumptions and outputs: The comparison table records assumptions about sufficiency, faithfulness, and acyclicity, along with intervention use and outputs such as CPDAGs or PAGs.A DAG output does not necessarily mean that the true DAG has been identified.

5 CONTINUOUS OPTIMIZATION BASED APPROACHES

Continuous optimization methods recast discrete DAG search as an equality-constrained optimization problem, connecting structure discovery with gradient-based deep learning. The survey reviews their motivation, scope, and representative methods.

  • Continuous formulation: Continuous approaches optimize an adjacency matrix under a differentiable acyclicity constraint instead of searching directly over valid DAGs.The survey formulates both traditional graph search and its continuous equality-constrained counterpart.
  • Motivation: The approach is motivated by increased computational capacity and the use of structured representations for causal reasoning, transfer learning, robustness, and interpretability.Hybrid models aim to learn semantic representations and structured relations together.
  • Survey scope: The survey reviews the recent evolution of continuous optimization methods and summarizes them in a non-exhaustive table.The methods span structure-learning approaches developed after the shift from combinatoric search.
  • Representative methods: CMS uses radial basis function neural networks to compare mapping errors between time-delayed embeddings and infer causal directionality.The method is demonstrated for univariate input variables.
  • Representative methods: DAGs with NO TEARS enforces acyclicity with h(A) = tr(e^(A⊙A)) − d = 0 and combines least-squares loss with an l1 sparsity penalty.Its optimization uses an Augmented Lagrangian method with L-BFGS.

5.4 Graphite (2019)

Graphite is a generative neural network model that infers latent graph structure using a graph neural network encoder and black-box variational inference. The surrounding survey contrasts this approach with neural and variational methods that learn directed structure under explicit assumptions.

  • Graphite: Graphite encodes graphical data with a graph neural network and infers a posterior latent distribution using black-box variational inference.It reconstructs graphs parameterized by symmetric, weighted adjacency matrices.
  • Related neural methods: CGNN learns structural-equation functions with neural networks while selecting variables through greedy search, avoiding prior restrictions on functional form.Its search and distribution-matching components contribute to scalability limitations addressed by SAM.
  • Related neural methods: SAM replaces CGNN’s greedy-search and quadratic MMD calculation with adversarial training and end-to-end DAG optimization.Its score uses log-likelihood together with model-complexity regularization.
  • Structural parameterization: SAM’s structural gate acts as an adjacency matrix, masking each variable’s inputs before neural-network transformations model its structural equation.The gate marks an edge Xi → Xj when the corresponding binary entry is one.
  • Structural parameterization: SAM’s theoretical analysis separates a structural component seeking the CPDAG from a functional component exploiting asymmetries, under faithfulness and sufficiency assumptions.It is evaluated on low- to medium-dimensional datasets, including one with approximately 6000 dimensions.
  • DAG-GNN: DAG-GNN extends NO TEARS with neural functions and variational inference, using an ELBO score and an acyclicity constraint optimized with an Augmented Lagrangian.It generalizes the linear SEM and is evaluated on low-dimensional data.

5.7 Graph AutoEncoder (GAE, 2019)

GAE extends continuous DAG structure learning with a graph autoencoder that supports nonlinear structural relationships and vector-valued variables. The survey reports stronger performance than NO TEARS and DAG-GNN as graph size increases, with shorter training time.

  • GAE extends NO TEARS and DAG-GNN into a graph autoencoder model for nonlinear structural relationships and vector-valued variables.
  • The model uses multilayer perceptrons and the augmented Lagrangian method with Adam for constrained optimization.
  • GAE performs significantly better than NO TEARS and DAG-GNN, particularly as the number of vertices increases.
  • GAE training time is much shorter than for the compared NO TEARS and DAG-GNN methods.
  • DEAR is not strictly a causal discovery method because it assumes the super-graph is given and learns weights and parameters with label supervision.
  • CAN learns a graph from dataset labels and generates images conditioned on user-specified interventional distributions.
  • CAN is evaluated on CelebA, CHILD, and Alarm, with performance competitive with the state of the art.

5.12 DAGs with NO FEARS

NO FEARS analyzes weaknesses in existing acyclicity constraints and replaces dependence on A ⊙ A with a differentiable absolute-value formulation linked to sparsity. Related continuous methods extend this optimization framework to soft likelihood-based constraints, latent confounding, temporal structure, and unknown interventions.

  • NO FEARS shows that augmented-Lagrangian optimization of the NO TEARS constraint is not guaranteed to converge to a feasible solution.
  • NO FEARS proposes an acyclicity constraint based on |A|, connecting it to the l1 penalty and sparsity after making the absolute-value function differentiable.
  • NO FEARS improves all baselines, including combinatoric approaches, according to the survey.
  • GOLEM uses a likelihood-based score with soft sparsity and soft acyclicity penalties, reducing optimization complexity relative to a hard constraint.
  • ABIC extends continuous optimization to ancestral, arid, and bow-free ADMGs that represent unmeasured confounding using a second adjacency matrix.
  • DYNOTEARS learns contemporaneous and time-lagged structure through intra-slice and inter-slice adjacency matrices, constraining only the intra-slice matrix.
  • SDI assumes discrete categorical variables without missingness, sparse single-variable interventions, and no compounding interventions.
  • SDI alternates functional, structural, and REINFORCE-based updates while predicting unknown intervention targets from log-likelihood reductions.

5.17 AutoEncoder Complexity (AEQ, 2020)

AEQ uses autoencoder reconstruction error to infer causal direction in vector-valued cause-effect pairs and constructs multivariate surrogates for univariate variables. Related reinforcement-learning and time-series methods use learned graphs for discovery, prediction, or hidden-confounding settings.

  • AEQ scores cause-effect direction using autoencoder reconstruction error for vector-valued pairs.
  • AEQ argues that Y = g(f(X), U) holds in only one direction when X and Y are vectors and g and f are neural networks.
  • For univariate variables, AEQ creates multivariate surrogates from sorted concatenated slices and treats the higher reconstruction loss as evidence of the cause.
  • For multivariate variables, AEQ uses adversarial conditional independence to distinguish joint distributions from products of marginals.
  • RL-BIC generates directed graphs with an encoder-decoder actor, BIC rewards, and a critic that updates graphs and neural-network parameters.
  • RL-BIC enforces acyclicity with a hard indicator penalty and evaluates relatively small graphs of at most 30 nodes.
  • ACD infers latent posterior graphs for nonlinear Granger-causal time series and performs well under hidden confounding.
  • ACD uses an encoder to infer a sample-specific graph and a decoder to predict future observations from that graph and part of the past.

5.21 Causal Discovery from Video (V-CDN, 2020)

V-CDN builds causal representations of detected video keypoints by combining unsupervised key-point detection, latent graph inference, and a dynamics module for future prediction. The surrounding survey discusses neural DAG learning, supervised causal representations, and intervention-oriented latent models.

  • V-CDN uses unsupervised key-point detection on video to construct causal representations of the detected points.
  • V-CDN applies black-box variational inference and deep neural networks to infer a latent graph explaining keypoint relationships.
  • V-CDN integrates a dynamics module to facilitate future prediction from the learned representation.
  • CASTLE makes causal discovery an auxiliary task within a supervised predictive model to regularize learning and reduce reliance on potential confounders.
  • GranDAG models nonlinear additive-noise mechanisms with fully connected neural networks and derives a weighted adjacency matrix from their connectivity patterns.
  • GranDAG uses augmented-Lagrangian learning with a log-likelihood score and reports better performance than PC, NO TEARS, and DAG-GNN.
  • MaskedNN uses a binary adjacency matrix in an augmented SEM and applies thresholding plus CAM-based pruning to remove spurious edges under mild conditions.
  • CausalVAE transforms exogenous latent factors into endogenous factors with a causal layer and uses semantic-label supervision to force identifiability.

5.26 Causal AutoRegressive Flows (CAREFL, 2020)

The survey describes CAREFL as combining causal discovery with normalizing flows, while also covering related continuous-optimization methods and missing-data structure discovery.

  • CAREFL: CAREFL combines causal discovery with normalizing flows to model complex densities through invertible transformations.The framework uses exact log-likelihood computation via the change-of-variables formula and inverse log Jacobian determinant.
  • CAREFL: CAREFL assumes a causal ordering in which parents precede their children and represents each variable with an additive-noise structural equation.Its formulation writes X_j as a function of variables preceding it in the causal order plus noise.
  • Related methods: NODAG learns a linear SEM and corresponding DAG using proximal-gradient optimization without an acyclicity constraint.The method frames structure learning as sparse matrix factorization and is reported as effective and efficient.
  • Related methods: NO TEARS+ extends the acyclicity constraint to nonparametric models by representing dependencies through partial derivatives rather than an adjacency matrix.The framework includes multilayer perceptrons and derives graph weights from l2 norms of partial derivatives.
  • Related methods: ICL addresses missing-data structure discovery by jointly imputing incomplete data with GANs while using VAEs.The passage introduces MAR, MCAR, and MNAR missingness settings.
  • Resources: Table 3 lists Python and R packages for causal inference and structure discovery, including command-line interfaces.The survey presents the table as a resource for undertaking causal inference and structure discovery.

5.30 Scalable Learning for Bayesian Networks (LEAST, 2020)

LEAST replaces the computationally expensive NO TEARS acyclicity treatment with a more scalable constraint based on an upper bound of the spectral radius.

  • Motivation: LEAST proposes a new acyclicity constraint intended to improve on the O(d^3) cost of NO TEARS.The method targets the computational burden associated with the matrix-exponential formulation.
  • Constraint: The method motivates its constraint by noting that both matrix-exponential approaches and NO BEARS’ spectral-radius computation require O(d^3) computation.LEAST instead derives an upper bound on the spectral radius.
  • Constraint: LEAST combines a computable spectral-radius upper bound with least squares and l1 regularization.The resulting objective is reported as nearer to O(d), while edge thresholding remains necessary.
  • Results: 5 to 15 times faster than NO TEARS, LEAST trains on small graphs and graphs with as many as 160,000 vertices.The survey reports this speedup alongside evaluation across substantially larger graph sizes.
  • Evaluation resources: Table 4 lists datasets used for testing structure discovery methods.The survey notes that not all listed datasets are readily available.

6 SUMMARY AND DISCUSSION

The survey reviews structure-discovery methods and resources while emphasizing scalability limits and the strong assumptions required to interpret learned structure causally. It concludes that these methods remain useful for exploratory work when researchers treat the causal interpretation cautiously.

  • Summary: The survey covers background, definitions, assumptions, discovery approaches, evaluation metrics, combinatoric methods, continuous optimization, software, datasets, and further references.It provides a detailed review of continuous optimization methods and lists additional resources.
  • Opportunities and Future Directions: Combinatoric approaches can provide guarantees for identifying the true graph or equivalence class but are limited to low-dimensional problems by the super-exponential search space.The number of possible DAGs drives this limitation.
  • Opportunities and Future Directions: Most continuous optimization approaches have been evaluated only on low-dimensional problems, partly because the common NO TEARS constraint requires O(d^3) computation.More efficient constraints such as LEAST are motivated by this limitation, while lower-dimensional representations offer another strategy.
  • Opportunities and Future Directions: Few continuous optimization methods learn structured semantic representations from non-semantic, high-dimensional data such as video or images.The survey identifies this as an opportunity for future work.
  • Opportunities and Future Directions: Few continuous optimization approaches handle unobserved confounding or cyclicity, despite the complexity and time variation of real-world phenomena.The survey calls for methods operating across a broader class of scenarios.
  • The Causal Leap: Interpreting learned graphical or structural models causally requires assumptions such as the Causal Markov Condition, whose causal implications are not guaranteed in complete generality.The survey distinguishes structural association from causal association and discusses identifiability concerns.
  • The Causal Leap: Structural equations are more specific than graphical models alone, but interpreting them as structural causal models still requires strong, often untestable assumptions.The survey therefore warns against treating formal structure as automatically equivalent to causal reality.
  • The Causal Leap: Graphical models may represent complex social constructs inadequately, making careful attention to variable meaning and intervention semantics necessary.The survey notes that understanding a variable’s ontology and epistemology may be difficult or impossible.
Loading 2103.02582v2…