Research map / Graph learning / Graph algorithms and clustering
Toward Falsifying Causal Graphs Using a Permutation-Based Test
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 a node-permutation baseline for judging whether a user-given causal DAG is significantly better than random at satisfying its implied conditional independences, yielding a p-value (p_LMC) and a Markov-equivalence falsifiability measure (p_TPa).
Problem
Existing metrics for checking how consistent a given causal DAG is with observational data report raw counts of conditional independence violations, which are hard to interpret without a baseline and are distorted by unknown CI-test type I error rates.
Approach
Build a null distribution by randomly permuting the nodes of the given DAG (which preserves the number of implied CIs, their conditioning-set sizes, and semi-graphoid closure), then compare the LMC violation count of the given graph to that of the permuted graphs to get a valid p-value; a second test measures how many Markov-equivalent DAGs lie in the permutation orbit to assess falsifiability.
Key results
- On synthetic data with the true DAG, p_LMC < 0.005 was never observed to falsify the true graph at alpha=1% (true graph not falsified); graphs from domain experts with |K|/|V| <= 0.6 or SHD/|E| >= 1.5 are falsified at alpha=1%.
- On real data, the consensus graphs for Sachs (p=0.031), Auto MPG (p=0.03) and APM (p=0.00) are not falsified at alpha=5%, despite LMC violation fractions of 0.08, 0.50 and 0.22 respectively.
- Runtime for ER graphs with 200 nodes and 100 permutations was about 3,386 s (under 1 hour).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use node permutations as the baseline for evaluating the true graph | Permutation test · Synthetic nonlinear data | p_LMC: p_LMC < 0.005 | Helped |
| Increase node-domain-expert knowledge | Permutation test · Synthetic data | p_LMC | Helped |
| Reduce edge-domain-expert SHD from the true graph | Permutation test · Real-world datasets | p_LMC | Helped |
| Use the raw LMC violation fraction instead of the permutation baseline | True consensus graphs · Sachs, Auto MPG, and APM | LMC violation fraction: 0.08; 0.50; 0.22 | Hurt |
| Evaluate NOTEARS and CAM graphs with the permutation test | Causal discovery graphs · Protein signaling network | p_LMC: 0.548 \pm 0.237; 0.0724 \pm 0.0866; 0.0362 \pm 0.129 | Mixed |
| Increase the number of observations from 10 to 100 or more (ablation) | Permutation test on true ER-10 synthetic graphs · ER-10-1, N column | p_LMC: 0.1045; 0.0084; 0.0028; 0.002 | Helped |
| Increase the number of observations from 10 to 100 or more (ablation) | Permutation test on true ER-10 synthetic graphs · ER-10-2, N column | p_LMC: 0.08496; 0.00036; 2e-05; 0 | Helped |
| Increase the number of observations from 10 to 100 or more (ablation) | Permutation test on true ER-20 synthetic graphs · ER-20-1, N column | p_LMC: 0.00724; 2e-05; 0; 0 | Helped |
| Increase the number of sampled permutations (ablation) | Permutation test on true ER synthetic graphs · ER-10-1, T column | p_LMC: 0.006; 0.0094; 0.00936; 0.008902 | No clear effect |
| Increase the number of sampled permutations (ablation) | Permutation test on true ER-10-2 synthetic graphs · ER-10-2, T column | p_LMC: 0; 0; 0; 2.2e-05 | No clear effect |
Surprising findings
- The fraction of LMC violations for the true graph exceeds the nominal 5% type I error rate on all real datasets, so using raw violation fractions would falsely reject the true graph.
- Graphs from NOTEARS and CAM on the Sachs data are not significantly better than random, while LiNGAM graphs are not falsified.
Limitations
- Node-permutation baseline may be a low bar; 'better than random' is a weak reference point and other baselines could be considered.
- Metric results depend on the CI test chosen, and nonparametric CI tests with unknown type I error affect the violation counts.
- Applying the test to causal-discovery outputs is limited because CIs used by the algorithm are not available as evidence.
Experimental setup
Datasets: Sachs protein signaling network Auto MPG APM cloud microservice traces (PetAdoptions) synthetic ER graphs with linear and nonlinear mechanisms
Benchmarks: Sachs protein signaling network Auto MPG APM cloud monitoring dataset synthetic ER graphs
Metrics: p_LMC p-value fraction of LMC violations SHD SID p_TPa
Baselines: NOTEARS CAM LiNGAM dagitty Structural Intervention Distance
Builds on: Parental Markov condition d-separation Generalized Covariance Measure Structural Hamming Distance
Closest papers by meaning
- Graph Distance Based on Cause-Effect Estimands with Latents (NeurIPS 2026 · similarity 0.89)
- Characterization and Learning of Causal Graphs from Hard Interventions (NeurIPS 2025 · similarity 0.88)
- Causal Discovery with Fewer Conditional Independence Tests (ICML 2024 · similarity 0.87)
- Foundations of Testing for Finite-Sample Causal Discovery (ICML 2024 · similarity 0.87)
- Scalable and Flexible Causal Discovery with an Efficient Test for Adjacency (ICML 2024 · similarity 0.86)
- Identifying Macro Conditional Independencies and Macro Total Effects in Summary Causal Graphs with Latent Confounding (AAAI 2025 · 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.