Research map / Graph learning / Graph algorithms and clustering
Scalable and Flexible Causal Discovery with an Efficient Test for Adjacency
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 the Differentiable Adjacency Test (DAT), which replaces exponentially many conditional independence tests with a differentiable search over soft noised separating representations, and builds DAT-Graph for scalable causal graph learning with and without interventions.
Problem
Learning causal graphs over many variables requires either a huge discrete model search or exponentially many conditional independence tests to decide whether two variables are adjacent, which does not scale and is unreliable under near violations of faithfulness.
Approach
Relax the discrete separating-set search into a differentiable search over soft masks ψ that mix each variable with thick-tailed noise, scored by a neural-network estimate of variance explained; combine with Markov-blanket (moral graph) pruning and test each adjacency twice for reliability.
Key results
- DAT-Graph learns 1000-variable graphs in roughly 4.5 hours vs 25 minutes for SDCD, and is more accurate than SDCD at large N.
- At N=30 with s=3 DAT-Graph reaches skeleton SHD 8±1 vs 25±4 for SDCD and 99±85 for GES.
- On RNA-seq, the DAT-Graph+SDCD hybrid achieves learned mutual information of 26.7 (control) vs 5.2 for SDCD.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the DAT-Graph skeleton and SDCD to orient edges instead of SDCD alone | Hybrid graph learner · N=30, s=3 | directed graph SHD: 26±4 -> 11± 3 | Helped |
| Restrict SDCD graph search to edges in the DAT-Graph skeleton | SDCD · RNA sequencing, control | learned mutual information: 5.2 -> 26.7 | Helped |
| Restrict SDCD graph search to edges in the DAT-Graph skeleton | SDCD · RNA sequencing, IFN | learned mutual information: 12.7 -> 28.3 | Helped |
| Restrict SDCD graph search to edges in the DAT-Graph skeleton | SDCD · RNA sequencing, Co-culture | learned mutual information: 4.3 -> 20.6 | Helped |
| Use the DAT-Graph intervention-aware procedure rather than Naive JCI | DAT-Graph · N=200, 50% intervened | skeleton SHD: 69±9 -> 51±9 | Helped |
| Replace the soft-subset representation with a neural network representation (ablation) | DAT-Graph · N=200, 800 edges | skeleton SHD: 81±9 -> 173±11 | Hurt |
| Replace thick-tailed noise distributions with Gaussian noise (ablation) | DAT-Graph · N=200, 800 edges | skeleton SHD: 81±9 -> 98±12 | Hurt |
| Test each pair using only one of the two Markov-blanket search spaces (ablation) | DAT-Graph · N=200, 800 edges | skeleton SHD: 81±9 -> 177±16 | Hurt |
| Fix ψ=0 and test marginal independence instead of optimizing ψ (ablation) | DAT-Graph · N=200, 800 edges | skeleton SHD: 81±9 -> 125±19 | Hurt |
| Fix ψ=1 and test conditional independence instead of optimizing ψ (ablation) | DAT-Graph · N=200, 800 edges | skeleton SHD: 81±9 -> 308±14 | Hurt |
| Use a graph inferred by SDCD rather than DAT-Graph to restrict SDCD (ablation) | SDCD hybrid · RNA sequencing, control | learned mutual information: 5.2 -> 5.4 | No clear effect |
Surprising findings
- Classical testing-based methods in the paper (GES, CAM, NoGAM) perform worse than a trivial empty-graph baseline on the small-N benchmark.
- SDCD makes worse-than-trivial predictions on the RNA-seq data under its default variance setting.
Limitations
- DAT-Graph is less accurate than model-selection methods on dense graphs.
- Assumes all variables observed and no cycles; does not handle confounding or latent variables.
- Separating set selection is NP-hard, so the relaxed search may fail in some cases; many hyperparameters (four thresholds and network settings).
Experimental setup
Datasets: synthetic Erdos-Renyi and scale-free graphs with neural/linear relations single-cell RNA-seq immunotherapy-resistant cancer CRISPR perturbation dataset
Benchmarks: synthetic graphs N up to 1000 (SHD) RNA-seq intervention prediction (mutual information)
Metrics: structural Hamming distance AUC wall time mean log-likelihood / learned mutual information
Baselines: SDCD DCDFG PC GES CAM NoGAM RCoT GCIT CCIT CMIT
Builds on: SDCD PC algorithm Invariant Risk Minimization NoGAM RCoT
Closest papers by meaning
- Differentiable Cyclic Causal Discovery Under Unmeasured Confounders (NeurIPS 2025 · similarity 0.89)
- Causal Discovery with Fewer Conditional Independence Tests (ICML 2024 · similarity 0.88)
- Interventional Causal Discovery in a Mixture of DAGs (NeurIPS 2024 · similarity 0.88)
- Identifying biological perturbation targets through causal differential networks (ICML 2025 · similarity 0.88)
- Stable Differentiable Causal Discovery (ICML 2024 · similarity 0.88)
- THE ROBUSTNESS OF DIFFERENTIABLE CAUSAL DISCOVERY IN MISSPECIFIED SCENARIOS (ICLR 2025 · similarity 0.88)
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.