Research map / Probabilistic and scientific modeling / Causal discovery
QWO: Speeding Up Permutation-Based Causal Discovery in LiGAMs
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 QWO, a whitening-plus-orthogonal-matrix method that computes the permutation-constrained DAG G^pi for LiGAMs in O(n^3) initially and O(n^2 d) per update, independent of sample size, and plugs it into GRaSP and hill-climbing search.
Problem
Permutation-based causal discovery in linear Gaussian acyclic models requires repeatedly computing the permutation-constrained DAG G^pi, and existing BIC/BDeu/CV-based computations are too expensive for scaling to many variables.
Approach
Characterize all LiGMs generating the data as B = I - QW with W a whitening matrix and Q orthogonal; for a permutation, construct Q by Gram-Schmidt on whitened columns in reverse permutation order, so G^pi = G(I - QW) is obtained without score optimization, and updates reuse the unchanged part of Q.
Key results
- QWO achieves comparable skeleton F1 to BIC with GRaSP on small graphs (e.g., 0.87 vs 1.0 on ASIA, 0.88 vs 0.93 on SACHS) while running in milliseconds versus tens of milliseconds for BIC.
- Theoretical complexity is O(n^3) initially and O(n^2 d) per update, versus O(n^5) and O(n^4 d) for BIC, a claimed O(n^2) speed-up.
- On 10,000-sample high-dimensional experiments QWO shows significant speedup over BIC with both GRaSP and hill-climbing while maintaining accuracy.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use QWO instead of BIC for graph construction with GRaSP | GRaSP on CANCER · CANCER | Time (s): 0.06 -> 0.003 | Helped |
| Use QWO instead of BIC for graph construction with GRaSP | GRaSP on SURVEY · SURVEY | Time (s): 0.07 -> 0.004 | Helped |
| Use QWO instead of BIC for graph construction with GRaSP | GRaSP on ASIA · ASIA | Time (s): 0.08 -> 0.01 | Helped |
| Use QWO instead of BIC for graph construction with GRaSP | GRaSP on SACHS · SACHS | Time (s): 0.39 -> 0.04 | Helped |
| Use QWO instead of BIC for graph construction with GRaSP | GRaSP on ER2 · ER2 | Time (s): 0.02 -> 0.002 | Helped |
| Use QWO instead of BIC for graph construction with GRaSP | GRaSP on CANCER · CANCER | SKF1: 1 -> 1 | No clear effect |
| Use QWO instead of BIC for graph construction with GRaSP | GRaSP on SURVEY · SURVEY | SKF1: 1 -> 1 | No clear effect |
| Use QWO instead of BIC for graph construction with GRaSP | GRaSP on ASIA · ASIA | SKF1: 1 -> 0.87 | Hurt |
| Use QWO instead of BIC for graph construction with GRaSP | GRaSP on SACHS · SACHS | SKF1: 0.93 -> 0.88 | Hurt |
| Use QWO instead of BIC for graph construction with GRaSP | GRaSP on ER2 · ER2 | SKF1: 1 -> 0.85 | Hurt |
| Use QWO instead of BIC for graph construction with GRaSP | GRaSP on ASIA · ASIA | PSHD: 0 -> 0.87 | Hurt |
| Use QWO instead of BIC for graph construction with GRaSP | GRaSP on SACHS · SACHS | PSHD: 0.81 -> 0.63 | Hurt |
Surprising findings
- QWO's skeleton F1 on some small graphs is lower than BIC with GRaSP (e.g., 0.85 vs 1.0 on CANCER-like ER2 setting and 0.57 on SURVEY for CV General, though QWO is lower on ASIA), indicating errors come mainly from covariance estimation rather than the module.
Limitations
- Assumes LiGAM: linear, Gaussian (or near-Gaussian) noise, and acyclic structure.
- Accuracy bottleneck is covariance estimation error; with oracle inverse covariance accuracy is much higher.
- Generalization to cyclic LiGMs requires solving a non-convex orthogonal optimization problem that is not yet solved.
Experimental setup
Datasets: ASIA CANCER SACHS SURVEY synthetic Erdos-Renyi LiGAM data
Benchmarks: ASIA CANCER SACHS SURVEY ER2/ER3/ER4 synthetic graphs
Metrics: Skeleton F1 Complete PDAG SHD runtime (s)
Baselines: BIC BDeu CV General
Builds on: GRaSP sparsest permutation sparsest Markov representation BIC score
Closest papers by meaning
- Coarsening Linear Non-Gaussian Causal Models with Cycles (NeurIPS 2026 · similarity 0.90)
- PACER: Acyclic Causal Discovery from Large-scale Interventional Data (ICML 2026 · similarity 0.88)
- Interventional Causal Discovery in a Mixture of DAGs (NeurIPS 2024 · similarity 0.88)
- Near-Optimal Experiment Design in Linear non-Gaussian Cyclic Models (NeurIPS 2025 · similarity 0.87)
- Causal Discovery with Fewer Conditional Independence Tests (ICML 2024 · similarity 0.87)
- Hybrid Top-Down Global Causal Discovery with Local Search for Linear and Nonlinear Additive Noise Models (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.