# Adaptivity Complexity for Causal Graph Discovery

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 68 references that are in the map.
- First posted on arXiv 9 Jun 2023.

## Builds on (most cited first, 11 of 11)

- [Causal Inference and Causal Explanation with Background Knowledge](https://mlsanity.com/paper/1302.4972/) (2013)
- [Learning Causal Graphs with Small Interventions](https://mlsanity.com/paper/1511.00041/) (2015)
- [Cost-Optimal Learning of Causal Graphs](https://mlsanity.com/paper/1703.02645/) (2017)
- [Active Structure Learning of Causal DAGs via Directed Clique Tree](https://mlsanity.com/paper/2011.00641/) (2020)
- [Verification and search algorithms for causal DAGs](https://mlsanity.com/paper/2206.15374/) (2022)
- [Subset verification and search algorithms for causal DAGs](https://mlsanity.com/paper/2301.03180/) (2023)
- [Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions](https://mlsanity.com/paper/1608.00673/) (2016)
- [Parallel Algorithms for Select and Partition with Noisy Comparisons](https://mlsanity.com/paper/1603.04941/) (2016)
- [Welfare Maximization with Limited Interaction](https://mlsanity.com/paper/1504.01780/) (2015)
- [An Adaptivity Hierarchy Theorem for Property Testing](https://mlsanity.com/paper/1702.05678/) (2017)
- [The Query Complexity of Local Search and Brouwer in Rounds](https://mlsanity.com/paper/2101.00061/) (2020)

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

- [Amortized Active Causal Induction with Deep Reinforcement Learning](https://mlsanity.com/paper/2405.16718/) (2024)
- [Adaptive Online Experimental Design for Causal Discovery](https://mlsanity.com/paper/2405.11548/) (2024)
- [Sample Efficient Bayesian Learning of Causal Graphs from Interventions](https://mlsanity.com/paper/2410.20089/) (2024)
- [Probably approximately correct high-dimensional causal effect estimation given a valid adjustment set](https://mlsanity.com/paper/2411.08141/) (2024)
- [Causal Discovery by Interventions via Integer Programming](https://mlsanity.com/paper/2412.01674/) (2024)
- [Design of Experiment for Discovering Directed Mixed Graph](https://mlsanity.com/paper/2509.01887/) (2025)
- [FOCUS: Fixed-Confidence Online Causal Learning Using Sequential Adaptive Interventions](https://mlsanity.com/paper/2609.32165/) (2026)

## Abstract (arXiv)

Causal discovery from interventional data is an important problem, where the task is to design an interventional strategy that learns the hidden ground truth causal graph G(V,E) on |V| = n nodes while minimizing the number of performed interventions. Most prior interventional strategies broadly fall into two categories: non-adaptive and adaptive. Non-adaptive strategies decide on a single fixed set of interventions to be performed while adaptive strategies can decide on which nodes to intervene on sequentially based on past interventions. While adaptive algorithms may use exponentially fewer interventions than their non-adaptive counterparts, there are practical concerns that constrain the amount of adaptivity allowed. Motivated by this trade-off, we study the problem of r-adaptivity, where the algorithm designer recovers the causal graph under a total of r sequential rounds whilst trying to minimize the total number of interventions. For this problem, we provide a r-adaptive algorithm that achieves O(minr,log n · n^1/minr,log n) approximation with respect to the verification number, a well-known lower bound for adaptive algorithms. Furthermore, for every r, we show that our approximation is tight. Our definition of r-adaptivity interpolates nicely between the non-adaptive (r=1) and fully adaptive (r=n) settings where our approximation simplifies to O(n) and O(log n) respectively, matching the best-known approximation guarantees for both extremes. Our results also extend naturally to the bounded size interventions.