# Cost-Optimal Learning of Causal Graphs

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

## Key facts

- Cited by 44 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Mar 2017.

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

- [Interventions, Where and How? Experimental Design for Causal Models at Scale](https://mlsanity.com/paper/2203.02016/) (2022)
- [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)
- [Causal Bandits with Unknown Graph Structure](https://mlsanity.com/paper/2106.02988/) (2021)
- [Evaluation Methods and Measures for Causal Learning Algorithms](https://mlsanity.com/paper/2202.02896/) (2022)
- [Adaptively Exploiting d-Separators with Causal Bandits](https://mlsanity.com/paper/2202.05100/) (2022)
- [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)
- [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)
- [Subset verification and search algorithms for causal DAGs](https://mlsanity.com/paper/2301.03180/) (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)
- [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)
- [Gene Regulatory Network Inference in the Presence of Selection Bias and Latent Confounders](https://mlsanity.com/paper/2501.10124/) (2025)
- [Adaptive Online Experimental Design for Causal Discovery](https://mlsanity.com/paper/2405.11548/) (2024)
- [Confounded Budgeted Causal Bandits](https://mlsanity.com/paper/2401.07578/) (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)
- [Interventional Causal Discovery in a Mixture of DAGs](https://mlsanity.com/paper/2406.08666/) (2024)
- [Universal Lower Bound for Learning Causal DAGs with Atomic Interventions](https://mlsanity.com/paper/2111.05070/) (2021)
- [Causal Discovery under Off-Target Interventions](https://mlsanity.com/paper/2402.08229/) (2024)
- [Goal-Oriented Sequential Bayesian Experimental Design for Causal Learning](https://mlsanity.com/paper/2507.07359/) (2025)

## Abstract (arXiv)

We consider the problem of learning a causal graph over a set of variables with interventions. We study the cost-optimal causal graph learning problem: For a given skeleton (undirected version of the causal graph), design the set of interventions with minimum total cost, that can uniquely identify any causal graph with the given skeleton. We show that this problem is solvable in polynomial time. Later, we consider the case when the number of interventions is limited. For this case, we provide polynomial time algorithms when the skeleton is a tree or a clique tree. For a general chordal skeleton, we develop an efficient greedy algorithm, which can be improved when the causal graph skeleton is an interval graph.