Scalable Algorithms for Large Scale Causal Discovery

81 concepts80 papers1 proposal

Causal discovery—the process of inferring cause-and-effect relationships from observational data—is often described as the "holy grail" of data science. However, as Thuc Duy Le et al. note in the proceedings of the 2019 ACM SIGKDD Workshop, the transition from simple correlation to true causation introduces a massive computational burden. While identifying correlations is relatively straightforward, identifying the structure of a causal network typically involves navigating a combinatorial search space that grows exponentially with the number of variables.

The Combinatorial Explosion of Structure Learning

The fundamental difficulty in causal discovery lies in the search for a Directed Acyclic Graph (DAG) that best explains the data. For a system with only a few dozen variables, the number of possible graph structures is already astronomical. Yizuo Chen et al. highlight in Query-Specific Causal Graph Pruning Under Tiered Knowledge that learning a full causal structure typically scales exponentially, making it nearly impossible to apply to large-scale systems without significant pruning or background knowledge.

To bypass this "combinatorial nightmare," researchers have shifted toward continuous optimization. Xun Zheng et al. built upon the "NOTEARS" framework in Learning Sparse Nonparametric DAGs, transforming the discrete search for a graph into a smooth mathematical problem. Even so, they note that nonparametric methods often suffer from cubic complexity relative to the number of observations, creating a new bottleneck when dealing with "big data."

Statistical Bottlenecks and Kernel Methods

Beyond the search for graph structure, the statistical tests used to validate causal links are themselves expensive. Traditional methods for identifying causal direction, such as non-linear regression, do not scale well to massive datasets. Alexander Marx et al. addressed this in Telling Cause from Effect Using MDL-Based Local and Global Regression by introducing SLOPE, a linear-time algorithm that uses data compression (Minimum Description Length) to decide causal direction, breaking through the performance barriers of more complex regression techniques.

Similarly, in the realm of causal effect estimation, Kwangho Kim et al. argue in A kernel balancing approach that scales to big data that traditional weighting methods are too computationally intensive for massive datasets. By employing the Nyström approximation—a technique to approximate large matrices—they enable causal inference to scale to millions of observations.

Achieving Linear and Logarithmic Efficiency

The most recent frontier in this field involves bringing complex causal operations down to linear or even logarithmic time complexity. A notable milestone was achieved by Marcel Wienöbst et al. in Linear-Time Algorithms for Front-Door Adjustment in Causal Graphs, which transformed a high-polynomial task into a linear one, finally making the "Front-Door" adjustment practical for modern big data environments.

In the context of Reinforcement Learning, where agents must make decisions in real-time, even linear scaling can be too slow. Zhile Yang proposed Tree-based History Counterfactual Inference, which uses a coarse-to-fine search strategy to reduce the complexity of identifying causal drivers from linear to logarithmic. This allows agents to process long histories of observations without the prohibitive cost of testing every individual event.

Scaling to High-Dimensional Domains

As causal discovery moves into specialized fields, new domain-specific scaling challenges emerge:

  • Spatio-Temporal Data: Kun Wang et al. in NuwaDynamics highlight the overhead of intervening on "causal patches" in weather or urban sensing data, necessitating new pruning techniques.
  • Software Engineering: Andrei Paleyes et al. demonstrate in Dataflow graphs as complete causal graphs that while software dataflows naturally represent causal structures, scaling attribution algorithms to thousands of nodes in a production environment remains an open challenge.
  • Generative Modeling: Xiao Liu showed in Diffusion Models for Causal Discovery via Topological Ordering that neural score functions can decouple computational complexity from the total number of samples, allowing for discovery on datasets with 100,000+ samples that would crash traditional kernel-based systems.

Ultimately, the goal of this research direction is to move causal inference from a boutique statistical tool used on small, curated datasets to a robust engine capable of processing the high-volume, high-velocity data of the modern world. As Jean Kaddour et al. summarize in their survey of Causal Machine Learning, scaling these methods to handle larger, more complex graphs remains one of the most significant open problems in the field.

Key Foundational Work

Causal inference and causal explanation with background knowledge (1995) — contributed 1 concept elements to this direction.
Representation of Empirically Derived Causal Relationships (1983) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_computational_complexity_of_causal_disco_98355fb7,
  title = {computational complexity of causal discovery},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/computational-complexity-of-causal-discovery/rdr_98355fb7ec7b43878c0fcda112b7543e},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_computational_complexity_of_causal_disco_98355fb7_v1,
  title = {computational complexity of causal discovery},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/computational-complexity-of-causal-discovery/rdr_98355fb7ec7b43878c0fcda112b7543e/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake