mlsanityData to 14 Oct 2026

Learning Causal Graphs with Small Interventions

arXiv 1511.00041 ↗First posted 30 Oct 2015cs.AI cs.IT cs.LGcited by 63

Not on the map. Why?

Abstract (arXiv)

We consider the problem of learning causal networks with interventions, when each intervention is limited in size under Pearl's Structural Equation Model with independent errors (SEM-IE). The objective is to minimize the number of experiments to discover the causal directions of all the edges in a causal graph. Previous work has focused on the use of separating systems for complete graphs for this task. We prove that any deterministic adaptive algorithm needs to be a separating system in order to learn complete graphs in the worst case. In addition, we present a novel separating system construction, whose size is close to optimal and is arguably simpler than previous work in combinatorics. We also develop a novel information theoretic lower bound on the number of interventions that applies in full generality, including for randomized adaptive learning algorithms. For general chordal graphs, we derive worst case lower bounds on the number of interventions. Building on observations about induced trees, we give a new deterministic adaptive algorithm to learn directions on any chordal skeleton completely. In the worst case, our achievable scheme is an α-approximation algorithm where α is the independence number of the graph. We also show that there exist graph classes for which the sufficient number of experiments is close to the lower bound. In the other extreme, there are graph classes for which the required number of experiments is multiplicatively α away from our lower bound. In simulations, our algorithm almost always performs very close to the lower bound, while the approach based on separating systems for complete graphs is significantly worse for random chordal graphs.

Key facts. Cited by 63 papers in the map (data through 14 Oct 2026). First posted on arXiv 30 Oct 2015.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2019: 1; 2020: 0; 2021: 8; 2022: 11; 2023: 9; 2024: 11; 2025: 13; 2026: 10.

63 papers.

Sort:

By area:

  1. 2019Causal Confusion in Imitation Learningcited by 288
  2. 2022Causal Discovery in Heterogeneous Environments Under the Sparse Mechanism Shift Hypothesiscited by 55
  3. 2022Interventions, Where and How? Experimental Design for Causal Models at Scalecited by 49
  4. 2021Learning Neural Causal Models with Active Interventionscited by 40
  5. 2021Causal Bandits with Unknown Graph Structurecited by 37
  6. 2022Active Bayesian Causal Inferencecited by 35
  7. 2022Active Learning for Optimal Intervention Design in Causal Modelscited by 31
  8. 2022Evaluation Methods and Measures for Causal Learning Algorithmscited by 23
  9. 2021Interventional Sum-Product Networks: Causal Inference with Tractable Probabilistic Modelscited by 22
  10. 2022Verification and search algorithms for causal DAGscited by 18
  11. 2023Identifying Linearly-Mixed Causal Representations from Multi-Node Interventionscited by 18
  12. 2021Near-Optimal Multi-Perturbation Experimental Design for Causal Structure Learningcited by 17
38 more
  1. 2022Membership Inference Attacks and Generalization: A Causal Perspectivecited by 17
  2. 2021Matching a Desired Causal State via Shift Interventionscited by 16
  3. 2024Causal Discovery with Fewer Conditional Independence Testscited by 13
  4. 2023Subset verification and search algorithms for causal DAGscited by 12
  5. 2023Causal Bandits without Graph Learningcited by 10
  6. 2023Active causal structure learning with advicecited by 10
  7. 2025When Selection Meets Intervention: Additional Complexities in Causal Discoverycited by 10
  8. 2022Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs with Applicationscited by 9
  9. 2023DAG Learning on the Permutahedroncited by 9
  10. 2022A Unified Experiment Design Approach for Cyclic and Acyclic Causal Modelscited by 7
  11. 2022Sample Constrained Treatment Effect Estimationcited by 7
  12. 2023Adaptivity Complexity for Causal Graph Discoverycited by 7
  13. 2024CORE: Towards Scalable and Efficient Causal Discovery with Reinforcement Learningcited by 6
  14. 2021Collaborative Causal Discovery with Atomic Interventionscited by 5
  15. 2024Towards the Reusability and Compositionality of Causal Representationscited by 5
  16. 2024Adaptive Online Experimental Design for Causal Discoverycited by 5
  17. 2024Deriving Causal Order from Single-Variable Interventions: Guarantees & Algorithmcited by 5
  18. 2024Partial Structure Discovery is Sufficient for No-regret Learning in Causal Banditscited by 5
  19. 2024Sample Efficient Bayesian Learning of Causal Graphs from Interventionscited by 4
  20. 2025Near-Optimal Experiment Design in Linear non-Gaussian Cyclic Modelscited by 4
  21. 2023New metrics and search algorithms for weighted causal DAGscited by 3
  22. 2023Meek Separators and Their Applications in Targeted Causal Discoverycited by 3
  23. 2024Interventional Causal Discovery in a Mixture of DAGscited by 3
  24. 2024Detecting and Measuring Confounding Using Causal Mechanism Shiftscited by 3
  25. 2021Universal Lower Bound for Learning Causal DAGs with Atomic Interventionscited by 2
  26. 2024Causal Discovery under Off-Target Interventionscited by 2
  27. 2025Characterization and Learning of Causal Graphs from Hard Interventionscited by 2
  28. 2025Counterfactual Inference for Eliminating Sentiment Bias in Recommender Systemscited by 2
  29. 2025Assimilative Causal Inferencecited by 2
  30. 2021Intervention Efficient Algorithm for Two-Stage Causal MDPscited by 1
  31. 2023Practical Algorithms for Orientations of Partially Directed Graphical Modelscited by 1
  32. 2024Causal Contextual Bandits with Adaptive Contextcited by 1
  33. 2025DODO: Causal Structure Learning with Budgeted Interventionscited by 1
  34. 2025Bridging Prediction and Attribution: Identifying Forward and Backward Causal Influence Ranges Using Assimilative Causal Inferencecited by 1
  35. 2026Causal Neighbourhood Learning for Invariant Graph Representationscited by 1
  36. 2022Fast Causal Orientation Learning in Directed Acyclic Graphscited by 0
  37. 2025Sample Complexity of Nonparametric Closeness Testing for Continuous Distributions and Its Application to Causal Discovery with Hidden Confoundingcited by 0
  38. 2025From Observation to Orientation: an Adaptive Integer Programming Approach to Intervention Designcited by 0

50 most cited of 63 All 63 (JSON)