# Causal Structure Learning: a Combinatorial Perspective

arXiv: https://arxiv.org/abs/2206.01152 · HTML: https://mlsanity.com/paper/2206.01152/

## Key facts

- Cited by 46 papers in the map (data through 14 Oct 2026).
- Builds on 85 of its 204 references that are in the map.
- First posted on arXiv 2 Jun 2022.

## Builds on (most cited first, 30 of 85)

- [DAGs with NO TEARS: Continuous Optimization for Structure Learning](https://mlsanity.com/paper/1803.01422/) (2018)
- [DAG-GNN: DAG Structure Learning with Graph Neural Networks](https://mlsanity.com/paper/1904.10098/) (2019)
- [Gradient-Based Neural DAG Learning](https://mlsanity.com/paper/1906.02226/) (2019)
- [Differentiable Causal Discovery from Interventional Data](https://mlsanity.com/paper/2007.01754/) (2020)
- [CAM: Causal additive models, high-dimensional order search and penalized regression](https://mlsanity.com/paper/1310.1533/) (2013)
- [Causal Inference and Causal Explanation with Background Knowledge](https://mlsanity.com/paper/1302.4972/) (2013)
- [Causal Inference in the Presence of Latent Variables and Selection Bias](https://mlsanity.com/paper/1302.4983/) (2013)
- [Invariant Causal Prediction for Nonlinear Models](https://mlsanity.com/paper/1706.08576/) (2017)
- [Foundations of Structural Causal Models with Cycles and Latent Variables](https://mlsanity.com/paper/1611.06221/) (2016)
- [Semiparametric doubly robust targeted double machine learning: a review](https://mlsanity.com/paper/2203.06469/) (2022)
- [Learning Neural Causal Models from Unknown Interventions](https://mlsanity.com/paper/1910.01075/) (2019)
- [DiBS: Differentiable Bayesian Structure Learning](https://mlsanity.com/paper/2105.11839/) (2021)
- [Causal Bandits: Learning Good Interventions via Causal Inference](https://mlsanity.com/paper/1606.03203/) (2016)
- [D-VAE: A Variational Autoencoder for Directed Acyclic Graphs](https://mlsanity.com/paper/1904.11088/) (2019)
- [Causal Structure Learning](https://mlsanity.com/paper/1706.09141/) (2017)
- [Permutation-based Causal Inference Algorithms with Interventions](https://mlsanity.com/paper/1705.10220/) (2017)
- [Approximate Kernel-based Conditional Independence Tests for Fast Non-Parametric Causal Discovery](https://mlsanity.com/paper/1702.03877/) (2017)
- [Characterizing and Learning Equivalence Classes of Causal DAGs under Interventions](https://mlsanity.com/paper/1802.06310/) (2018)
- [Permutation-Based Causal Structure Learning with Unknown Intervention Targets](https://mlsanity.com/paper/1910.09007/) (2019)
- [Causal Networks: Semantics and Expressiveness](https://mlsanity.com/paper/1304.2379/) (2013)
- [Structure Learning in Graphical Modeling](https://mlsanity.com/paper/1606.02359/) (2016)
- [Differentiable Causal Discovery Under Unmeasured Confounding](https://mlsanity.com/paper/2010.06978/) (2020)
- [Learning latent causal graphs via mixture oracles](https://mlsanity.com/paper/2106.15563/) (2021)
- [Causal Discovery from Changes](https://mlsanity.com/paper/1301.2312/) (2013)
- [ABCD-Strategy: Budgeted Experimental Design for Targeted Causal Structure Discovery](https://mlsanity.com/paper/1902.10347/) (2019)
- [Learning Sparse Causal Models is not NP-hard](https://mlsanity.com/paper/1309.6824/) (2013)
- [Interventions, Where and How? Experimental Design for Causal Models at Scale](https://mlsanity.com/paper/2203.02016/) (2022)
- [Constraint-based Causal Discovery from Multiple Interventions over Overlapping Variable Sets](https://mlsanity.com/paper/1403.2150/) (2014)
- [High-dimensional consistency in score-based and hybrid structure learning](https://mlsanity.com/paper/1507.02608/) (2015)
- [Cost-Optimal Learning of Causal Graphs](https://mlsanity.com/paper/1703.02645/) (2017)

## Built on by (most cited first, 30 of 46)

- [Nonparametric Identifiability of Causal Representations from Unknown Interventions](https://mlsanity.com/paper/2306.00542/) (2023)
- [Learning Linear Causal Representations from Interventions under General Nonlinear Mixing](https://mlsanity.com/paper/2306.02235/) (2023)
- [Linear Causal Disentanglement via Interventions](https://mlsanity.com/paper/2211.16467/) (2022)
- [Identifiability Guarantees for Causal Disentanglement from Soft Interventions](https://mlsanity.com/paper/2307.06250/) (2023)
- [On the Origins of Linear Representations in Large Language Models](https://mlsanity.com/paper/2403.03867/) (2024)
- [Causal Discovery from Temporal Data: An Overview and New Perspectives](https://mlsanity.com/paper/2303.10112/) (2023)
- [Learning Interpretable Concepts: Unifying Causal Representation Learning and Foundation Models](https://mlsanity.com/paper/2402.09236/) (2024)
- [Causal Abstraction with Soft Interventions](https://mlsanity.com/paper/2211.12270/) (2022)
- [Counterfactual (Non-)identifiability of Learned Structural Causal Models](https://mlsanity.com/paper/2301.09031/) (2023)
- [Standardizing Structural Causal Models](https://mlsanity.com/paper/2406.11601/) (2024)
- [Causal Discovery with Fewer Conditional Independence Tests](https://mlsanity.com/paper/2406.01823/) (2024)
- [Local Causal Discovery for Estimating Causal Effects](https://mlsanity.com/paper/2302.08070/) (2023)
- [An Interventional Perspective on Identifiability in Gaussian LTI Systems with Independent Component Analysis](https://mlsanity.com/paper/2311.18048/) (2023)
- [C2P: Featuring Large Language Models with Causal Reasoning](https://mlsanity.com/paper/2407.18069/) (2024)
- [Heteroscedastic Causal Structure Learning](https://mlsanity.com/paper/2307.07973/) (2023)
- [Effective Bayesian Causal Inference via Structural Marginalisation and Autoregressive Orders](https://mlsanity.com/paper/2402.14781/) (2024)
- [Overcoming Fairness Trade-offs via Pre-processing: A Causal Perspective](https://mlsanity.com/paper/2501.14710/) (2025)
- [Causal Discovery in Mixtures of Populations](https://mlsanity.com/paper/2311.07454/) (2023)
- [Investigating potential causes of Sepsis with Bayesian network structure learning](https://mlsanity.com/paper/2406.09207/) (2024)
- [Measure-Theoretic Anti-Causal Representation Learning](https://mlsanity.com/paper/2510.18052/) (2025)
- [dotears: Scalable, consistent DAG estimation using observational and interventional data](https://mlsanity.com/paper/2305.19215/) (2023)
- [Differentiable Bayesian Structure Learning with Acyclicity Assurance](https://mlsanity.com/paper/2309.01392/) (2023)
- [Meek Separators and Their Applications in Targeted Causal Discovery](https://mlsanity.com/paper/2310.20075/) (2023)
- [Learned Causal Method Prediction](https://mlsanity.com/paper/2311.03989/) (2023)
- [Optimal estimation of Gaussian (poly)trees](https://mlsanity.com/paper/2402.06380/) (2024)
- [Causal Imputation for Counterfactual SCMs: Bridging Graphs and Latent Factor Models](https://mlsanity.com/paper/2402.14777/) (2024)
- [Greedy equivalence search for nonparametric graphical models](https://mlsanity.com/paper/2406.17228/) (2024)
- [Score-matching-based Structure Learning for Temporal Data on Networks](https://mlsanity.com/paper/2412.07469/) (2024)
- [DAG DECORation: Continuous Optimization for Structure Learning under Hidden Confounding](https://mlsanity.com/paper/2510.02117/) (2025)
- [Working Paper: Active Causal Structure Learning with Latent Variables: Towards Learning to Detour in Autonomous Robots](https://mlsanity.com/paper/2410.20894/) (2024)

## Abstract (arXiv)

In this review, we discuss approaches for learning causal structure from data, also called causal discovery. In particular, we focus on approaches for learning directed acyclic graphs (DAGs) and various generalizations which allow for some variables to be unobserved in the available data. We devote special attention to two fundamental combinatorial aspects of causal structure learning. First, we discuss the structure of the search space over causal graphs. Second, we discuss the structure of equivalence classes over causal graphs, i.e., sets of graphs which represent what can be learned from observational data alone, and how these equivalence classes can be refined by adding interventional data.