mlsanityData to 14 Oct 2026

Active Structure Learning of Causal DAGs via Directed Clique Tree

arXiv 2011.00641 ↗First posted 1 Nov 2020stat.ME cs.LG stat.MLcited by 38

Not on the map. Why?

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

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 7; 2022: 6; 2023: 7; 2024: 6; 2025: 5; 2026: 7.

38 papers.

Sort:

  1. 2022Interventions, Where and How? Experimental Design for Causal Models at Scalecited by 49
  2. 2022Causal Structure Learning: a Combinatorial Perspectivecited by 46
  3. 2021Learning Neural Causal Models with Active Interventionscited by 40
  4. 2021Causal Bandits with Unknown Graph Structurecited by 37
  5. 2022Verification and search algorithms for causal DAGscited by 18
  6. 2021Matching a Desired Causal State via Shift Interventionscited by 16
  7. 2024Causal Discovery with Fewer Conditional Independence Testscited by 13
  8. 2023Subset verification and search algorithms for causal DAGscited by 12
  9. 2021Efficient Online Estimation of Causal Effects by Deciding What to Observecited by 11
  10. 2023Causal Bandits without Graph Learningcited by 10
  11. 2023Active causal structure learning with advicecited by 10
  12. 2022Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs with Applicationscited by 9
26 more
  1. 2022A Unified Experiment Design Approach for Cyclic and Acyclic Causal Modelscited by 7
  2. 2023Adaptivity Complexity for Causal Graph Discoverycited by 7
  3. 2022Trust Your nabla: Gradient-based Intervention Targeting for Causal Discoverycited by 5
  4. 2024Adaptive Online Experimental Design for Causal Discoverycited by 5
  5. 2021Active Structure Learning of Bayesian Networks in an Observational Settingcited by 4
  6. 2024Sample Efficient Bayesian Learning of Causal Graphs from Interventionscited by 4
  7. 2025Near-Optimal Experiment Design in Linear non-Gaussian Cyclic Modelscited by 4
  8. 2023New metrics and search algorithms for weighted causal DAGscited by 3
  9. 2023Meek Separators and Their Applications in Targeted Causal Discoverycited by 3
  10. 2024Interventional Causal Discovery in a Mixture of DAGscited by 3
  11. 2024Improving Finite Sample Performance of Causal Discovery by Exploiting Temporal Structurecited by 3
  12. 2021Universal Lower Bound for Learning Causal DAGs with Atomic Interventionscited by 2
  13. 2024Causal Discovery under Off-Target Interventionscited by 2
  14. 2023Practical Algorithms for Orientations of Partially Directed Graphical Modelscited by 1
  15. 2021Active-LATHE: An Active Learning Algorithm for Boosting the Error Exponent for Learning Homogeneous Ising Treescited by 0
  16. 2025Sample Complexity of Nonparametric Closeness Testing for Continuous Distributions and Its Application to Causal Discovery with Hidden Confoundingcited by 0
  17. 2025Design of Experiment for Discovering Directed Mixed Graphcited by 0
  18. 2025Graph Distance Based on Cause-Effect Estimands with Latentscited by 0
  19. 2025Theoretical Guarantees for Causal Discovery on Large Random Graphscited by 0
  20. 2026Efficient Causal Structure Learning via Modular Subgraph Integrationcited by 0
  21. 2026Partial Causal Structure Learning for Valid Selective Conformal Inference under Interventionscited by 0
  22. 2026Iterative Identification Closure: Amplifying Causal Identifiability in Linear SEMscited by 0
  23. 2026Causal Learning with the Invariance Principlecited by 0
  24. 2026Information-Directed Sampling for Causal Banditscited by 0
  25. 2026FOCUS: Fixed-Confidence Online Causal Learning Using Sequential Adaptive Interventionscited by 0
  26. 2026Certifying Interventional Agreement Among Observationally Equivalent Causal Modelscited by 0