# Active Structure Learning of Causal DAGs via Directed Clique Tree

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

## Key facts

- Cited by 38 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Nov 2020.

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

- [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)
- [Verification and search algorithms for causal DAGs](https://mlsanity.com/paper/2206.15374/) (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)
- [Efficient Online Estimation of Causal Effects by Deciding What to Observe](https://mlsanity.com/paper/2108.09265/) (2021)
- [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)
- [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)
- [Adaptivity Complexity for Causal Graph Discovery](https://mlsanity.com/paper/2306.05781/) (2023)
- [Trust Your nabla: Gradient-based Intervention Targeting for Causal Discovery](https://mlsanity.com/paper/2211.13715/) (2022)
- [Adaptive Online Experimental Design for Causal Discovery](https://mlsanity.com/paper/2405.11548/) (2024)
- [Active Structure Learning of Bayesian Networks in an Observational Setting](https://mlsanity.com/paper/2103.13796/) (2021)
- [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)
- [Improving Finite Sample Performance of Causal Discovery by Exploiting Temporal Structure](https://mlsanity.com/paper/2406.19503/) (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)
- [Practical Algorithms for Orientations of Partially Directed Graphical Models](https://mlsanity.com/paper/2302.14386/) (2023)
- [Active-LATHE: An Active Learning Algorithm for Boosting the Error Exponent for Learning Homogeneous Ising Trees](https://mlsanity.com/paper/2110.14341/) (2021)
- [Sample Complexity of Nonparametric Closeness Testing for Continuous Distributions and Its Application to Causal Discovery with Hidden Confounding](https://mlsanity.com/paper/2503.07475/) (2025)
- [Design of Experiment for Discovering Directed Mixed Graph](https://mlsanity.com/paper/2509.01887/) (2025)
- [Graph Distance Based on Cause-Effect Estimands with Latents](https://mlsanity.com/paper/2510.25037/) (2025)

## Abstract (arXiv)

A growing body of work has begun to study intervention design for efficient structure learning of causal directed acyclic graphs (DAGs). A typical setting is a causally sufficient setting, i.e. a system with no latent confounders, selection bias, or feedback, when the essential graph of the observational equivalence class (EC) is given as an input and interventions are assumed to be noiseless. Most existing works focus on worst-case or average-case lower bounds for the number of interventions required to orient a DAG. These worst-case lower bounds only establish that the largest clique in the essential graph could make it difficult to learn the true DAG. In this work, we develop a universal lower bound for single-node interventions that establishes that the largest clique is always a fundamental impediment to structure learning. Specifically, we present a decomposition of a DAG into independently orientable components through directed clique trees and use it to prove that the number of single-node interventions necessary to orient any DAG in an EC is at least the sum of half the size of the largest cliques in each chain component of the essential graph. Moreover, we present a two-phase intervention design algorithm that, under certain conditions on the chordal skeleton, matches the optimal number of interventions up to a multiplicative logarithmic factor in the number of maximal cliques. We show via synthetic experiments that our algorithm can scale to much larger graphs than most of the related work and achieves better worst-case performance than other scalable approaches. A code base to recreate these results can be found at https://github.com/csquires/dct-policy