# Intervention Efficient Algorithms for Approximate Learning of Causal Graphs

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Dec 2020.

## Built on by (most cited first, 7 of 7)

- [Sample Constrained Treatment Effect Estimation](https://mlsanity.com/paper/2210.06594/) (2022)
- [Collaborative Causal Discovery with Atomic Interventions](https://mlsanity.com/paper/2106.03028/) (2021)
- [Identifiability Matters: Revealing the Hidden Recoverable Condition in Unbiased Learning to Rank](https://mlsanity.com/paper/2309.15560/) (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)
- [Experimental Design for Causal Effect Identification](https://mlsanity.com/paper/2205.02232/) (2022)
- [Characterization and Learning of Causal Graphs from Hard Interventions](https://mlsanity.com/paper/2505.01037/) (2025)

## Abstract (arXiv)

We study the problem of learning the causal relationships between a set of observed variables in the presence of latents, while minimizing the cost of interventions on the observed variables. We assume access to an undirected graph G on the observed variables whose edges represent either all direct causal relationships or, less restrictively, a superset of causal relationships (identified, e.g., via conditional independence tests or a domain expert). Our goal is to recover the directions of all causal or ancestral relations in G, via a minimum cost set of interventions. It is known that constructing an exact minimum cost intervention set for an arbitrary graph G is NP-hard. We further argue that, conditioned on the hardness of approximate graph coloring, no polynomial time algorithm can achieve an approximation factor better than Theta(log n), where n is the number of observed variables in G. To overcome this limitation, we introduce a bi-criteria approximation goal that lets us recover the directions of all but ε n2 edges in G, for some specified error parameter ε > 0. Under this relaxed goal, we give polynomial time algorithms that achieve intervention cost within a small constant factor of the optimal. Our algorithms combine work on efficient intervention design and the design of low-cost separating set systems, with ideas from the literature on graph property testing.