mlsanityData to 14 Oct 2026

Near-Optimal Experiment Design in Linear non-Gaussian Cyclic Models

arXiv 2509.21423 ↗First posted 25 Sep 2025stat.ML cs.AI cs.LGcited by 4

Not on the map. Why?

Abstract (arXiv)

We study the problem of causal structure learning from a combination of observational and interventional data generated by a linear non-Gaussian structural equation model that might contain cycles. Recent results show that using mere observational data identifies the causal graph only up to a permutation-equivalence class. We obtain a combinatorial characterization of this class by showing that each graph in an equivalence class corresponds to a perfect matching in a bipartite graph. This bipartite representation allows us to analyze how interventions modify or constrain the matchings. Specifically, we show that each atomic intervention reveals one edge of the true matching and eliminates all incompatible causal graphs. Consequently, we formalize the optimal experiment design task as an adaptive stochastic optimization problem over the set of equivalence classes with a natural reward function that quantifies how many graphs are eliminated from the equivalence class by an intervention. We show that this reward function is adaptive submodular and provide a greedy policy with a provable near-optimal performance guarantee. A key technical challenge is to efficiently estimate the reward function without having to explicitly enumerate all the graphs in the equivalence class. We propose a sampling-based estimator using random matchings and analyze its bias and concentration behavior. Our simulation results show that performing a small number of interventions guided by our stochastic optimization framework recovers the true underlying causal structure.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 19 of its 38 references that are in the map. First posted on arXiv 25 Sep 2025.

Builds on

19 of 38 references.

References · 19

  1. 2019Variational Autoencoders and Nonlinear ICA: A Unifying Frameworkcited by 503
  2. 2016Foundations of Structural Causal Models with Cycles and Latent Variablescited by 134
  3. 2022Identifiability of deep generative models without auxiliary informationcited by 70
  4. 2015Learning Causal Graphs with Small Interventionscited by 63
  5. 2019ABCD-Strategy: Budgeted Experimental Design for Targeted Causal Structure Discoverycited by 52
  6. 2022Interventions, Where and How? Experimental Design for Causal Models at Scalecited by 49
  7. 2017Cost-Optimal Learning of Causal Graphscited by 44
  8. 2017Budgeted Experiment Design for Causal Structure Learningcited by 38
  9. 2020Active Structure Learning of Causal DAGs via Directed Clique Treecited by 38
  10. 2018Constraint-based Causal Discovery for Non-Linear Structural Causal Models with Cycles and Latent Confounderscited by 35
  11. 2013A Discovery Algorithm for Directed Cyclic Graphscited by 34
  12. 2020Constraint-Based Causal Discovery using Partial Ancestral Graphs in the presence of Cyclescited by 31
7 more
  1. 2020Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGscited by 14
  2. 2020LazyIter: A Fast Algorithm for Counting Markov Equivalent DAGs and Designing Experimentscited by 9
  3. 2022Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs with Applicationscited by 9
  4. 2018Counting and Sampling from Markov Equivalent DAGs Using Clique Treescited by 8
  5. 2019Interventional Experiment Design for Causal Structure Learningcited by 8
  6. 2013A Polynomial-Time Algorithm for Deciding Markov Equivalence of Directed Cyclic Graphical Modelscited by 7
  7. 2022A Unified Experiment Design Approach for Cyclic and Acyclic Causal Modelscited by 7

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 4.

4 papers.

  1. 2026Distributional Equivalence in Linear Non-Gaussian Latent-Variable Cyclic Causal Models: Characterization and Learningcited by 4
  2. 2026Coarsening Linear Non-Gaussian Causal Models with Cyclescited by 2
  3. 2026Causal Reasoning with Bipartite Graphical Causal Modelscited by 0
  4. 2026The Statistical Cost of Causal Discovery with Feedbackcited by 0