Causal discovery aims to uncover the hidden web of cause-and-effect relationships driving a complex system, representing them as a Directed Acyclic Graph (DAG). Historically, finding the optimal DAG was treated as a discrete, combinatorial search problem—a notorious "combinatorial nightmare" because the number of possible graphs scales super-exponentially with the number of variables.
A major breakthrough occurred when researchers reframed this discrete search as a continuous optimization problem. In papers like Gradient-Based Neural DAG Learning by Lachapelle et al., the discrete graph search was replaced by gradient descent over continuous neural network weights. By enforcing a smooth, mathematical penalty that vanishes only when the graph is acyclic, standard deep learning hardware could suddenly be used to learn causal structures directly from data.
However, this continuous revolution hit a massive wall: scalability. The mathematical functions used to enforce acyclicity globally across the graph scale cubically ($O(d^3)$) with the number of variables $d$. This cubic bottleneck makes it computationally impossible to apply gradient-based causal discovery to high-dimensional systems like whole-genome regulatory networks or large-scale sensor arrays.
A vibrant thread of recent research focuses on bypassing this $O(d^3)$ bottleneck. To understand how these new methods work, we must first understand why cycle detection is so computationally expensive in the first place.
The Root of the Cubic Bottleneck
Why does ensuring a graph has no loops require $O(d^3)$ overhead?
Consider an adjacency matrix $A$, where $A_{ij}$ represents the strength of the edge from node $i$ to node $j$. A cycle exists if you can start at a node and follow directed edges back to itself. In matrix algebra, the number of paths of length $k$ between nodes is given by the matrix power $A^k$. Therefore, to guarantee that a graph has no cycles of any length, you must ensure that the diagonal elements of $A^k$ are zero for all path lengths $k$ from 2 up to the total number of nodes $d$.
To check all path lengths simultaneously within a differentiable framework, standard continuous causal discovery relies on global matrix functions, most notably the matrix exponential:
$$\text{Tr}(\exp(A \odot A)) = d$$
Computing a matrix exponential or performing the matrix fractional operations required for these constraints inherently involves operations like matrix multiplication, inversion, or eigendecomposition. Each of these operations scales cubically ($O(d^3)$) relative to the number of nodes.
As highlighted by Brouillard et al. in Differentiable Causal Discovery from Interventional Data and Martins et al. in Differentiable Causal Discovery Under Latent Interventions, evaluating this constraint at every single gradient step creates an insurmountable computational barrier when moving from toy problems to real-world datasets containing thousands of variables.
[Standard Continuous Discovery]
Graph Matrix (A) ──> Matrix Exponential / Inversion ──> Global Acyclicity Check [O(d³)]
│
Gradient Update <────────────────────────────────────────────────┘
To scale causal discovery to high-dimensional domains, researchers have developed three primary strategies to avoid evaluating these expensive global matrix functions.
Strategy 1: Constraint-Free Smooth Orientations
If enforcing an acyclicity constraint on a general matrix is too expensive, why not parameterize the graph so that it is physically impossible to form a cycle in the first place?
A graph is guaranteed to be a DAG if its nodes follow a strict topological ordering (i.e., an edge can only exist from node $i$ to node $j$ if $i$ precedes $j$ in the ordering). If the ordering is fixed, the adjacency matrix can be represented as a simple upper-triangular matrix, which is inherently acyclic. However, searching through discrete permutations of node orderings is non-differentiable.
To solve this, Massidda et al. introduced COSMO in Constraint-Free Structure Learning with Smooth Acyclic Orientations. Instead of a hard sorting operation, the authors parameterize the graph using continuous node "priorities." They construct a smooth orientation matrix where the probability or weight of an edge existing between two nodes is smoothly scaled by the difference in their continuous priority scores.
Because this parameterization naturally suppresses edges that violate the continuous ordering, the optimization space is restricted entirely to valid DAGs. This eliminates the need for any matrix exponentials, dropping the computational complexity per step from cubic $O(d^3)$ to quadratic $O(d^2)$.
[Smooth Orientation (COSMO)]
Continuous Node Priorities ──> Smooth Orientation Matrix ──> Inherently Acyclic Graph [O(d²)]
This approach scales exceptionally well to dynamic systems. For instance, Michelis et al. developed SVARCOSMO in Large-Scale Continuous Structure Learning from Time-Series Data, applying constraint-free smooth parameterizations to high-dimensional time-series data, bypassing the heavy matrix calculations that traditionally cripple large-scale temporal causal modeling.
Strategy 2: Decoupling Optimization via Graph Projections
A second strategy asks: why force the graph to be acyclic during the intermediate steps of gradient descent?
Methods like ProxiMAS and OptiMAS, proposed by Gillot et al. in Learning Large DAGs by Combining Continuous Optimization and Feedback Arc Set Heuristics, completely decouple the data-fitting process from the structural acyclicity constraint. During the continuous optimization phase, the algorithm is allowed to learn a cyclic, unconstrained graph structure that best explains the statistical dependencies in the data.
Once an unconstrained graph is learned, the algorithm uses fast, discrete graph-theoretic heuristics—specifically solving the Feedback Arc Set (FAS) problem—to identify and remove the minimal set of edges causing loops. By projecting the cyclic graph back into a valid DAG space outside of the gradient loop, these methods can scale to datasets with over 20,000 variables.
[Decoupled Projection]
Continuous Optimization (Data Fit Only) ──> Cyclic Graph ──> Feedback Arc Set / Projection ──> Final DAG
This concept of projection is also powerful in probabilistic settings. In ProDAG: Projected Variational Inference for Directed Acyclic Graphs, Thompson et al. designed a Bayesian framework that projects continuous distributions directly onto the space of sparse, acyclic matrices using the implicit function theorem, maintaining rigorous uncertainty quantification without the cubic overhead of standard matrix constraints.
Strategy 3: Low-Rank and Alternative Matrix Decompositions
When global structural constraints cannot be avoided entirely, the cubic bottleneck can still be mitigated by changing the underlying algebraic representation of the matrix or the data.
In Large-Scale Differentiable Causal Discovery of Factor Graphs, Lopez et al. addressed the scaling problem in biological systems by introducing DCD-FG. They observed that while a system might contain thousands of individual variables (such as genes), their interactions are often coordinated by a much smaller set of latent biological factors. By enforcing a low-rank factorization on the graph's weight matrices, they compressed the dimensionality of the space over which acyclicity must be verified, allowing differentiable causal discovery to scale to massive single-cell RNA sequencing datasets.
Alternatively, the matrix exponential itself can be replaced with more efficient matrix decompositions. For example, Liang et al. developed MgCSL (Multi-Granularity Causal Structure Learning), which utilizes a high-efficiency acyclicity constraint based on Schur decomposition rather than matrix exponentials, achieving up to a ten-fold speedup in graph discovery.
Why This Matters: Broad Applications
Bypassing the cubic bottleneck is not just a theoretical victory; it unlocks the practical application of causal AI across several complex domains:
- Anomaly Detection in Sensor Networks: In systems like power grids or traffic networks containing thousands of sensors, models like GANF (Dai et al. in Graph-Augmented Normalizing Flows for Anomaly Detection of Multiple Time Series) use scalable DAG learning alongside normalizing flows to isolate anomalies by understanding how downstream sensors are causally affected by upstream failures.
- Irregularly Sampled Systems: In clinical health records or physical simulations where variables are observed at irregular intervals, frameworks like GNeuralFlow (Mercatali et al. in Graph Neural Flows for Unveiling Systemic Interactions Among Irregularly Sampled Time Series) integrate efficient graph learning directly into continuous-time trajectory predictors.
- Causally-Consistent Data Imputation: Methods like MIRACLE (Kyono et al. in MIRACLE: Causally-Aware Imputation via Learning Missing Data Mechanisms) rely on scalable causal discovery to prevent the generation of physically impossible or structurally contradictory values during missing data imputation.
By shifting away from computationally heavy global matrix exponentials toward smooth priority parameterizations, decoupled graph projections, and low-rank decompositions, modern causal discovery has successfully broken through the $O(d^3)$ barrier—moving the field closer to discovering the true causal architectures of massive, real-world systems.
Key Foundational Work
Bayesian Network Learning via Topological Order (2017) — contributed 1 concept elements to this direction.
Inferning with High Girth Graphical Models (2014) — contributed 1 concept elements to this direction.