Scalable causal discovery methods improved for larger data sets
Mapping and Advancing the Scalability-Accuracy Frontier of Nonlinear Causal Discovery
Machine LearningArtificial Intelligence
Summary
Finding cause-and-effect relationships in complex data is challenging when there are many variables. The authors studied four main ways to discover these relationships and found each has different strengths and weaknesses. They created a new technique called SPADE that speeds up a reliable method by reusing calculations, making it practical to analyze much bigger problems quickly. This work helps push the limits of how accurately and quickly we can find causes in large data sets.
What this means in practice
- •For data engineering teams: Analyze large complex datasets to uncover cause-effect relationships more efficiently and accurately than before.
- •For financial risk analysts: Improve modeling of nonlinear causal effects in markets with many factors to inform risk management decisions.
Authors
Hendrik Suhr, Sascha Xu, Jilles Vreeken
Abstract
Scalable nonlinear causal discovery requires methods that combine flexible mechanism estimators with efficient search over large graph spaces. Several algorithmic families have been proposed to address this challenge, yet their accuracy-runtime trade-offs remain poorly understood. We empirically compare the four major approaches: differentiable structure learning, amortized structure learning, score-matching, and combinatorial search. Our results reveal complementary bottlenecks: differentiable and amortized methods scale well but exhibit an accuracy gap, score-matching methods can be accurate in low dimensions but degrade quickly for increasing feature sizes, and combinatorial methods remain accurate but are slowed by repeated and redundant local scoring. Motivated by this bottleneck, we develop SPADE, a spline-based score-evaluation scheme that compiles sufficient statistics once and reuses them throughout combinatorial search. Under bounded indegree, its Gaussian variant reduces algorithmic complexity from O(nd^3) to O(nd^2+d^3). Empirically, SPADE shifts the observed scalability-accuracy frontier by orders of magnitude: it solves 100-variable problems with 160K samples in seconds and 1600-variable problems with 2.5K samples in minutes, while retaining high structural accuracy across synthetic and real-world benchmarks. These results reveal a substantial shift in the practical scale of combinatorial search and highlight the importance of evaluating scalable causal-discovery methods along the full accuracy-runtime frontier.