# Learning Causal Graphs with Small Interventions

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

## Key facts

- Cited by 63 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Oct 2015.

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

- [Causal Confusion in Imitation Learning](https://mlsanity.com/paper/1905.11979/) (2019)
- [Causal Discovery in Heterogeneous Environments Under the Sparse Mechanism Shift Hypothesis](https://mlsanity.com/paper/2206.02013/) (2022)
- [Interventions, Where and How? Experimental Design for Causal Models at Scale](https://mlsanity.com/paper/2203.02016/) (2022)
- [Learning Neural Causal Models with Active Interventions](https://mlsanity.com/paper/2109.02429/) (2021)
- [Causal Bandits with Unknown Graph Structure](https://mlsanity.com/paper/2106.02988/) (2021)
- [Active Bayesian Causal Inference](https://mlsanity.com/paper/2206.02063/) (2022)
- [Active Learning for Optimal Intervention Design in Causal Models](https://mlsanity.com/paper/2209.04744/) (2022)
- [Evaluation Methods and Measures for Causal Learning Algorithms](https://mlsanity.com/paper/2202.02896/) (2022)
- [Interventional Sum-Product Networks: Causal Inference with Tractable Probabilistic Models](https://mlsanity.com/paper/2102.10440/) (2021)
- [Verification and search algorithms for causal DAGs](https://mlsanity.com/paper/2206.15374/) (2022)
- [Identifying Linearly-Mixed Causal Representations from Multi-Node Interventions](https://mlsanity.com/paper/2311.02695/) (2023)
- [Near-Optimal Multi-Perturbation Experimental Design for Causal Structure Learning](https://mlsanity.com/paper/2105.14024/) (2021)
- [Membership Inference Attacks and Generalization: A Causal Perspective](https://mlsanity.com/paper/2209.08615/) (2022)
- [Matching a Desired Causal State via Shift Interventions](https://mlsanity.com/paper/2107.01850/) (2021)
- [Causal Discovery with Fewer Conditional Independence Tests](https://mlsanity.com/paper/2406.01823/) (2024)
- [Subset verification and search algorithms for causal DAGs](https://mlsanity.com/paper/2301.03180/) (2023)
- [Causal Bandits without Graph Learning](https://mlsanity.com/paper/2301.11401/) (2023)
- [Active causal structure learning with advice](https://mlsanity.com/paper/2305.19588/) (2023)
- [When Selection Meets Intervention: Additional Complexities in Causal Discovery](https://mlsanity.com/paper/2503.07302/) (2025)
- [Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs with Applications](https://mlsanity.com/paper/2205.02654/) (2022)
- [DAG Learning on the Permutahedron](https://mlsanity.com/paper/2301.11898/) (2023)
- [A Unified Experiment Design Approach for Cyclic and Acyclic Causal Models](https://mlsanity.com/paper/2205.10083/) (2022)
- [Sample Constrained Treatment Effect Estimation](https://mlsanity.com/paper/2210.06594/) (2022)
- [Adaptivity Complexity for Causal Graph Discovery](https://mlsanity.com/paper/2306.05781/) (2023)
- [CORE: Towards Scalable and Efficient Causal Discovery with Reinforcement Learning](https://mlsanity.com/paper/2401.16974/) (2024)
- [Collaborative Causal Discovery with Atomic Interventions](https://mlsanity.com/paper/2106.03028/) (2021)
- [Towards the Reusability and Compositionality of Causal Representations](https://mlsanity.com/paper/2403.09830/) (2024)
- [Adaptive Online Experimental Design for Causal Discovery](https://mlsanity.com/paper/2405.11548/) (2024)
- [Deriving Causal Order from Single-Variable Interventions: Guarantees & Algorithm](https://mlsanity.com/paper/2405.18314/) (2024)
- [Partial Structure Discovery is Sufficient for No-regret Learning in Causal Bandits](https://mlsanity.com/paper/2411.04054/) (2024)

## Abstract (arXiv)

We consider the problem of learning causal networks with interventions, when each intervention is limited in size under Pearl's Structural Equation Model with independent errors (SEM-IE). The objective is to minimize the number of experiments to discover the causal directions of all the edges in a causal graph. Previous work has focused on the use of separating systems for complete graphs for this task. We prove that any deterministic adaptive algorithm needs to be a separating system in order to learn complete graphs in the worst case. In addition, we present a novel separating system construction, whose size is close to optimal and is arguably simpler than previous work in combinatorics. We also develop a novel information theoretic lower bound on the number of interventions that applies in full generality, including for randomized adaptive learning algorithms. For general chordal graphs, we derive worst case lower bounds on the number of interventions. Building on observations about induced trees, we give a new deterministic adaptive algorithm to learn directions on any chordal skeleton completely. In the worst case, our achievable scheme is an α-approximation algorithm where α is the independence number of the graph. We also show that there exist graph classes for which the sufficient number of experiments is close to the lower bound. In the other extreme, there are graph classes for which the required number of experiments is multiplicatively α away from our lower bound. In simulations, our algorithm almost always performs very close to the lower bound, while the approach based on separating systems for complete graphs is significantly worse for random chordal graphs.