Research map / Probabilistic and scientific modeling / Causal discovery
Causal Discovery by Interventions via Integer Programming
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.
Formulates minimal intervention-set design for causal discovery as an integer program (set-cover style) covering UPC, OPC, and CC identifiability conditions, with extensions for costs, size limits, and secondary objectives.
Problem
Designing the minimum number of multi-variable interventions needed to make a DAG's causal structure identifiable, given observational MEC and an independence oracle, with optional cost and intervention-size constraints.
Approach
Casts interventional causal discovery design as a binary integer program over all candidate intervention sets of size up to floor(|V|/2), with constraints encoding forward/backward/null pair conditions (UPC, OPC, CC), solved exactly by branch-and-bound and extended via objective changes for cost and secondary criteria.
Key results
- For N=9 variables with k_max=1, the IP finds 8 interventions; with k_max=2 it finds 6 and with k_max=3 or 4 it finds 4 (solved in under 2 seconds).
- For N=16 and N=17 with k_max=2 or more, the full identifiability IP exceeded the 10-minute cap, so solutions may be suboptimal.
- Under the CC-only model, a single null-plus-interventions design suffices for all tested N, which is trivial since the null experiment is a feasible solution.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Allow intervening on up to 2 rather than 1 variable simultaneously | IP identifiability model · Identifiability, N=9 | number of interventions: 8 -> 6 | Helped |
| Allow intervening on up to 3 rather than 1 variable simultaneously | IP identifiability model · Identifiability, N=9 | number of interventions: 8 -> 4 | Helped |
| Increase the maximum intervention size from 3 to 4 | IP identifiability model · Identifiability, N=9 | number of interventions: 4 -> 4 | No clear effect |
| Allow intervening on up to 2 rather than 1 variable simultaneously | IP UPC model · UPC, N=9 | number of interventions: 8 -> 6 | Helped |
| Allow intervening on up to 3 rather than 1 variable simultaneously | IP OPC model · OPC, N=9 | number of interventions: 9 -> 6 | Helped |
Surprising findings
- The covariance condition alone is trivially satisfied by the null experiment, so CC-only designs need just one experiment.
Limitations
- Exact IP becomes intractable beyond about 16 variables when multi-variable interventions are allowed, with a 10-minute solver cap.
- Assumes causal sufficiency, acyclicity, faithfulness and an independence oracle.
- Cost and secondary objectives are illustrated on small examples only.
Experimental setup
Metrics: minimum number of interventions solver time in seconds intervention-size configurations
Builds on: separating systems cut-coverings OPTINTER
Closest papers by meaning
- On Causal Discovery in the Presence of Deterministic Relations (NeurIPS 2024 · similarity 0.89)
- Adaptive Online Experimental Design for Causal Discovery (ICML 2024 · similarity 0.87)
- Differentiable Constraint-Based Causal Discovery (NeurIPS 2025 · similarity 0.87)
- Causal Discovery with Fewer Conditional Independence Tests (ICML 2024 · similarity 0.87)
- Strong and Weak Identifiability of Optimization-based Causal Discovery in Non-linear Additive Noise Models (ICML 2025 · similarity 0.87)
- CausalTab: Pretraining Across Causal Environments for Tabular Causal Discovery (NeurIPS 2026 · similarity 0.86)
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.