Research map / Probabilistic and scientific modeling / Causal discovery
Near-Optimal Experiment Design in Linear non-Gaussian Cyclic Models
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Characterizes linear non-Gaussian cyclic SCM equivalence classes as perfect matchings in a bipartite graph, shows single-variable interventions reveal a matching edge, and proves the expected-elimination reward is adaptive submodular, giving a greedy (1-1/e) policy with a sampling-based reward estimator.
Problem
Optimal experiment design for causal structure learning in linear non-Gaussian structural causal models that may contain cycles, where observational data identifies the graph only up to a permutation-equivalence class.
Approach
Represent each graph in the observational equivalence class as a perfect matching in a bipartite graph built from the ICA-recovered matrix; each single-node intervention reveals one matching edge, so the reward (number of eliminated graphs) is adaptive submodular and a greedy adaptive policy is near-optimal. Reward is estimated by sampling matchings rather than enumerating them.
Key results
- With an ideal ICA oracle, the adaptive policy consistently needs fewer interventions than Random and Max Degree baselines and stays close to the exact feedback vertex set lower bound.
- The sampling-based estimator of the marginal benefit has error O(sqrt(log M / M)) with probability at least 1 - 1/M.
- With finite-sample FastICA plus adaptive thresholding and safe matching, the method achieves high-fidelity recovery of W in the vast majority of runs.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use adaptive intervention selection instead of Random or Max Degree | Adaptive experiment design with ideal ICA · Synthetic Erdős–Rényi cyclic graphs | average number of interventions | Helped |
| Use adaptive intervention selection instead of Random or Max Degree | Adaptive experiment design with finite-sample FastICA · Synthetic Erdős–Rényi cyclic graphs | average number of interventions | Helped |
| Use adaptive intervention selection | Adaptive experiment design with ideal ICA · Synthetic Erdős–Rényi cyclic graphs | average number of interventions relative to FVS lower bound | Mixed |
| Use adaptive intervention selection with robustness modifications | Adaptive experiment design with finite-sample FastICA · Synthetic Erdős–Rényi cyclic graphs | average number of interventions relative to FVS lower bound | Mixed |
Limitations
- Assumes perfect single-variable interventions and linear non-Gaussian noise with at most one Gaussian component.
- Theoretical sampler assumes a uniform (FPRAS-based) matching sampler, while the practical sampler is a non-uniform greedy heuristic.
- Finite-sample experiments rely on added heuristics (adaptive thresholding, safe matching) on top of FastICA.
Experimental setup
Datasets: synthetic Erdős–Rényi linear non-Gaussian directed graphs
Benchmarks: synthetic Erdős–Rényi graphs
Metrics: average number of interventions to full identification relative Frobenius error of recovered W
Baselines: Random Max Degree feedback vertex set lower bound
Builds on: LiNGAM adaptive stochastic optimization (Golovin and Krause) FastICA
Closest papers by meaning
- Coarsening Linear Non-Gaussian Causal Models with Cycles (NeurIPS 2026 · similarity 0.88)
- Adaptive Online Experimental Design for Causal Discovery (ICML 2024 · similarity 0.88)
- Partial Structure Discovery is Sufficient for No-regret Learning in Causal Bandits (NeurIPS 2024 · similarity 0.87)
- Sample Efficient Bayesian Learning of Causal Graphs from Interventions (NeurIPS 2024 · similarity 0.87)
- QWO: Speeding Up Permutation-Based Causal Discovery in LiGAMs (NeurIPS 2024 · similarity 0.87)
- Learning Mixtures of Unknown Causal Interventions (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.