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

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

## 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 (most cited first, 19 of 19)

- [Variational Autoencoders and Nonlinear ICA: A Unifying Framework](https://mlsanity.com/paper/1907.04809/) (2019)
- [Foundations of Structural Causal Models with Cycles and Latent Variables](https://mlsanity.com/paper/1611.06221/) (2016)
- [Identifiability of deep generative models without auxiliary information](https://mlsanity.com/paper/2206.10044/) (2022)
- [Learning Causal Graphs with Small Interventions](https://mlsanity.com/paper/1511.00041/) (2015)
- [ABCD-Strategy: Budgeted Experimental Design for Targeted Causal Structure Discovery](https://mlsanity.com/paper/1902.10347/) (2019)
- [Interventions, Where and How? Experimental Design for Causal Models at Scale](https://mlsanity.com/paper/2203.02016/) (2022)
- [Cost-Optimal Learning of Causal Graphs](https://mlsanity.com/paper/1703.02645/) (2017)
- [Budgeted Experiment Design for Causal Structure Learning](https://mlsanity.com/paper/1709.03625/) (2017)
- [Active Structure Learning of Causal DAGs via Directed Clique Tree](https://mlsanity.com/paper/2011.00641/) (2020)
- [Constraint-based Causal Discovery for Non-Linear Structural Causal Models with Cycles and Latent Confounders](https://mlsanity.com/paper/1807.03024/) (2018)
- [A Discovery Algorithm for Directed Cyclic Graphs](https://mlsanity.com/paper/1302.3599/) (2013)
- [Constraint-Based Causal Discovery using Partial Ancestral Graphs in the presence of Cycles](https://mlsanity.com/paper/2005.00610/) (2020)
- [Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs](https://mlsanity.com/paper/2012.09679/) (2020)
- [LazyIter: A Fast Algorithm for Counting Markov Equivalent DAGs and Designing Experiments](https://mlsanity.com/paper/2006.09670/) (2020)
- [Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs with Applications](https://mlsanity.com/paper/2205.02654/) (2022)
- [Counting and Sampling from Markov Equivalent DAGs Using Clique Trees](https://mlsanity.com/paper/1802.01239/) (2018)
- [Interventional Experiment Design for Causal Structure Learning](https://mlsanity.com/paper/1910.05651/) (2019)
- [A Polynomial-Time Algorithm for Deciding Markov Equivalence of Directed Cyclic Graphical Models](https://mlsanity.com/paper/1302.3600/) (2013)
- [A Unified Experiment Design Approach for Cyclic and Acyclic Causal Models](https://mlsanity.com/paper/2205.10083/) (2022)

## Built on by (most cited first, 4 of 4)

- [Distributional Equivalence in Linear Non-Gaussian Latent-Variable Cyclic Causal Models: Characterization and Learning](https://mlsanity.com/paper/2603.04780/) (2026)
- [Coarsening Linear Non-Gaussian Causal Models with Cycles](https://mlsanity.com/paper/2605.10163/) (2026)
- [Causal Reasoning with Bipartite Graphical Causal Models](https://mlsanity.com/paper/2608.19831/) (2026)
- [The Statistical Cost of Causal Discovery with Feedback](https://mlsanity.com/paper/2609.34050/) (2026)

## 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.