# Budgeted Experiment Design for Causal Structure Learning

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

## Key facts

- Cited by 38 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Sep 2017.

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

- [Causal Structure Learning: a Combinatorial Perspective](https://mlsanity.com/paper/2206.01152/) (2022)
- [Learning Neural Causal Models with Active Interventions](https://mlsanity.com/paper/2109.02429/) (2021)
- [Active Bayesian Causal Inference](https://mlsanity.com/paper/2206.02063/) (2022)
- [GeneDisco: A Benchmark for Experimental Design in Drug Discovery](https://mlsanity.com/paper/2110.11875/) (2021)
- [Verification and search algorithms for causal DAGs](https://mlsanity.com/paper/2206.15374/) (2022)
- [Near-Optimal Multi-Perturbation Experimental Design for Causal Structure Learning](https://mlsanity.com/paper/2105.14024/) (2021)
- [Matching a Desired Causal State via Shift Interventions](https://mlsanity.com/paper/2107.01850/) (2021)
- [Differentiable Multi-Target Causal Bayesian Experimental Design](https://mlsanity.com/paper/2302.10607/) (2023)
- [Causal Entropy Optimization](https://mlsanity.com/paper/2208.10981/) (2022)
- [Provably Efficient Causal Model-Based Reinforcement Learning for Systematic Generalization](https://mlsanity.com/paper/2202.06545/) (2022)
- [Subset verification and search algorithms for causal DAGs](https://mlsanity.com/paper/2301.03180/) (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)
- [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)
- [Neural Design for Genetic Perturbation Experiments](https://mlsanity.com/paper/2207.12805/) (2022)
- [Collaborative Causal Discovery with Atomic Interventions](https://mlsanity.com/paper/2106.03028/) (2021)
- [Trust Your nabla: Gradient-based Intervention Targeting for Causal Discovery](https://mlsanity.com/paper/2211.13715/) (2022)
- [Causality from Bottom to Top: A Survey](https://mlsanity.com/paper/2403.11219/) (2024)
- [Sample Efficient Bayesian Learning of Causal Graphs from Interventions](https://mlsanity.com/paper/2410.20089/) (2024)
- [Near-Optimal Experiment Design in Linear non-Gaussian Cyclic Models](https://mlsanity.com/paper/2509.21423/) (2025)
- [New metrics and search algorithms for weighted causal DAGs](https://mlsanity.com/paper/2305.04445/) (2023)
- [Meek Separators and Their Applications in Targeted Causal Discovery](https://mlsanity.com/paper/2310.20075/) (2023)
- [Universal Lower Bound for Learning Causal DAGs with Atomic Interventions](https://mlsanity.com/paper/2111.05070/) (2021)
- [Experimental Design for Causal Effect Identification](https://mlsanity.com/paper/2205.02232/) (2022)
- [Causal Discovery under Off-Target Interventions](https://mlsanity.com/paper/2402.08229/) (2024)
- [Characterization and Learning of Causal Graphs from Hard Interventions](https://mlsanity.com/paper/2505.01037/) (2025)
- [Goal-Oriented Sequential Bayesian Experimental Design for Causal Learning](https://mlsanity.com/paper/2507.07359/) (2025)
- [Disentangling Observed Causal Effects from Latent Confounders using Method of Moments](https://mlsanity.com/paper/2101.06614/) (2021)
- [Graph Agnostic Causal Bayesian Optimisation](https://mlsanity.com/paper/2411.03028/) (2024)

## Abstract (arXiv)

We study the problem of causal structure learning when the experimenter is limited to perform at most k non-adaptive experiments of size 1. We formulate the problem of finding the best intervention target set as an optimization problem, which aims to maximize the average number of edges whose directions are resolved. We prove that the corresponding objective function is submodular and a greedy algorithm suffices to achieve (1-frac1e)-approximation of the optimal value. We further present an accelerated variant of the greedy algorithm, which can lead to orders of magnitude performance speedup. We validate our proposed approach on synthetic and real graphs. The results show that compared to the purely observational setting, our algorithm orients the majority of the edges through a considerably small number of interventions.