Research map / Probabilistic and scientific modeling / Causal discovery
DCILP: A Distributed Approach for Large-Scale Causal Structure Learning
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.
Proposes DCILP, a divide-and-conquer causal structure learner that learns local causal graphs over Markov blankets in parallel (Phase-2 via DAGMA or GES) and reconciles them globally with an integer linear program solved by Gurobi.
Problem
Causal graph learning from observational data does not scale to thousands of variables; existing divide-and-conquer fusion steps are mostly rule-based and hard to apply in large settings.
Approach
Identify Markov blankets per variable, learn local causal subgraphs in parallel, and reconcile conflicting local edges via an ILP with binary variables for causal, spouse and v-structure relations plus consistency constraints, maximizing agreement with the naive merged graph.
Key results
- On MUNIN, DCILP-dagma gives about 270x speed-up over DAGMA with SHD on par, and DCILP-ges gives about 25x speed-up over GES with better SHD.
- On SF3 with d=800 (n/d=20), DCILP-dagma reaches TPR 0.923 and FDR 0.250 at 3406 s versus DAGMA's TPR 0.999, FDR 0.003 at 22953 s.
- For d=1600 on ER2 data, DCILP-ges achieves more than 5x speed-up over GES.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace GES with DCILP-ges | causal structure learning · ER1 (d=1000, n/d=10) | SHD: 1521.8 {$\pm$ 51.3} -> 79 {$\pm$ 5.86} | Helped |
| replace GES with DCILP-ges | causal structure learning · ER1 (d=1000, n/d=10) | time (sec): 629.30 -> 328.00 | Helped |
| replace DAGMA with DCILP-dagma | causal structure learning · ER1 (d=1000, n/d=10) | time (sec): 8554.24 -> 272.67 | Helped |
| replace DAGMA with DCILP-dagma | causal structure learning · ER1 (d=1000, n/d=10) | SHD: 3.40 {$\pm$ 2.88} -> 46 {$\pm$ 23.59} | Hurt |
| use ground-truth Markov blankets instead of estimated blankets (ablation) | DCILP-dagma · SF3 (d=400, n/d=20) | SHD: 322 { $\pm$ 68.83} -> 208 { $\pm$ 24.43} | Helped |
| use ground-truth Markov blankets instead of estimated blankets (ablation) | DCILP-dagma · SF3 (d=800, n/d=20) | SHD: 914 { $\pm$ 191.78} -> 879 { $\pm$ 234.64} | Helped |
| apply ILP reconciliation instead of naive merging of local causal graphs (ablation) | DCILP · ER2 and SF3 synthetic graphs | FDR | Helped |
| apply ILP reconciliation instead of naive merging of local causal graphs (ablation) | DCILP · ER2 and SF3 synthetic graphs | TPR | Hurt |
Surprising findings
- On SF3 and ER1 data, DCILP-dagma trades a noticeable accuracy loss (SHD 322 vs DAGMA's 3 at d=400) for speed, and DAGMA is near-exact on these graphs.
- The ILP output is not guaranteed to be a DAG; only 2-cycles are excluded by constraints.
Limitations
- Errors in Markov blanket estimation (Phase-1) propagate to Phase-2 and Phase-3, and Phase-1 is restricted to linear Gaussian SEMs.
- The ILP solution is not guaranteed to be acyclic; only 2-cycles are ruled out by the constraints.
- Accuracy loss relative to DAGMA on synthetic graphs (e.g., TPR about 0.92 vs 0.999) and ILP cost grows with Markov blanket size.
Experimental setup
Datasets: synthetic linear SEM data (ER1, ER2, SF3) MUNIN Bayesian network data
Benchmarks: MUNIN ER1 synthetic graphs ER2 synthetic graphs SF3 synthetic graphs
Metrics: TPR FDR FPR SHD running time
Baselines: GES DAGMA GOLEM DAS PEF
Builds on: GES DAGMA NOTEARS PC algorithm LocalLearn
Closest papers by meaning
- A Recursive Decomposition Framework for Causal Structure Learning in the Presence of Latent Variables (ICML 2026 · similarity 0.89)
- Characterization and Learning of Causal Graphs with Small Conditioning Sets (NeurIPS 2023 · similarity 0.89)
- A Fixed-Point Approach for Causal Generative Modeling (ICML 2024 · similarity 0.88)
- A Recipe for Causal Graph Regression: Confounding Effects Revisited (ICML 2025 · similarity 0.87)
- Quantifying Distributional Invariance in Causal Subgraph for IRM-Free Graph Generalization (NeurIPS 2025 · similarity 0.87)
- Graph Contrastive Invariant Learning from the Causal Perspective (AAAI 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.