Interventional Causal Discovery in a Mixture of DAGs
Not on the map. Why?
Abstract (arXiv)
Causal interactions among a group of variables are often modeled by a single causal graph. In some domains, however, these interactions are best described by multiple co-existing causal graphs, e.g., in dynamical systems or genomics. This paper addresses the hitherto unknown role of interventions in learning causal interactions among variables governed by a mixture of causal systems, each modeled by one directed acyclic graph (DAG). Causal discovery from mixtures is fundamentally more challenging than single-DAG causal discovery. Two major difficulties stem from (i)~an inherent uncertainty about the skeletons of the component DAGs that constitute the mixture and (ii)~possibly cyclic relationships across these component DAGs. This paper addresses these challenges and aims to identify edges that exist in at least one component DAG of the mixture, referred to as the true edges. First, it establishes matching necessary and sufficient conditions on the size of interventions required to identify the true edges. Next, guided by the necessity results, an adaptive algorithm is designed that learns all true edges using O(n2) interventions, where n is the number of nodes. Remarkably, the size of the interventions is optimal if the underlying mixture model does not contain cycles across its components. More generally, the gap between the intervention size used by the algorithm and the optimal size is quantified. It is shown to be bounded by the cyclic complexity number of the mixture model, defined as the size of the minimal intervention that can break the cycles in the mixture, which is upper bounded by the number of cycles among the ancestors of a node.
Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 22 of its 53 references that are in the map. First posted on arXiv 12 Jun 2024.
Builds on
22 of 53 references.
References · 22
- 2020Differentiable Causal Discovery from Interventional Datacited by 218
- 2019Causal Discovery from Heterogeneous/Nonstationary Data with Independent Changescited by 166
- 2018Characterizing and Learning Equivalence Classes of Causal DAGs under Interventionscited by 76
- 2019Permutation-Based Causal Structure Learning with Unknown Intervention Targetscited by 69
- 2015Learning Causal Graphs with Small Interventionscited by 63
- 2017Cost-Optimal Learning of Causal Graphscited by 44
- 2020Active Structure Learning of Causal DAGs via Directed Clique Treecited by 38
- 2020Constraint-Based Causal Discovery using Partial Ancestral Graphs in the presence of Cyclescited by 31
- 2013Directed Cyclic Graphical Representations of Feedback Modelscited by 27
- 2018Experimental Design for Cost-Aware Learning of Causal Graphscited by 25
- 2020Causal Structure Discovery from Distributions Arising from Mixtures of DAGscited by 24
- 2020Efficient Intervention Design for Causal Discovery with Latentscited by 22
10 more
- 2022Verification and search algorithms for causal DAGscited by 18
- 2013An Algorithm for Deciding if a Set of Observed Independencies Has a Causal Explanationcited by 17
- 2022Learning Mixtures of Linear Dynamical Systemscited by 15
- 2013Learning Mixtures of DAG Modelscited by 10
- 2021A Distance Covariance-based Kernel for Nonlinear Causal Clustering in Heterogeneous Populationscited by 10
- 2023Discovering Mixtures of Structural Causal Models from Time Series Datacited by 10
- 2020Intervention Efficient Algorithms for Approximate Learning of Causal Graphscited by 7
- 2022A Unified Experiment Design Approach for Cyclic and Acyclic Causal Modelscited by 7
- 2022Disentangling Mixtures of Unknown Causal Interventionscited by 6
- 2021CCSL: A Causal Structure Learning Method from Multiple Unknown Environmentscited by 2
Built on by
Citing papers per year: 2025: 2; 2026: 1.
3 papers.