Abstract
The introduction of the NOTEARS algorithm resulted in a wave of research on differentiable Directed Acyclic Graph (DAG) learning. Differentiable DAG learning transforms the combinatorial problem of identifying the DAG underlying a Structural Causal Model (SCM) into a constrained continuous optimization problem. Being differentiable, these problems can be solved using gradient-based tools which allow integration into other differentiable objectives. However, in contrast to classical constrained-based algorithms, the identifiability properties of differentiable algorithms are poorly understood. We illustrate that even in the well-known Linear Non-Gaussian Additive Model (LiNGAM), the current state-of-the-art methods do not identify the true underlying DAG. To address the issue, we propose NOTIME (Non-combinatorial Optimization of Trace exponential and Independence MEasures), the first differentiable DAG learning algorithm with provable identifiability guarantees under the LiNGAM by building on a measure of (joint) independence. With its identifiability guarantees, NOTIME remains invariant to normalization of the data on a population level, a property lacking in existing methods. NOTIME compares favourably against NOTEARS and other (scale-invariant) differentiable DAG learners, across different noise distributions and normalization procedures. Introducing the first identifiability guarantees to general LiNGAM is an important step towards practical adoption of differentiable DAG learners.
Breaking the "Equal Variance" Trap
Causal discovery—the art of inferring "what causes what" from raw data—has undergone a revolution recently. The field has moved from slow, combinatorial searches to "differentiable" methods that treat graph learning like a standard deep learning optimization problem. However, a significant limitation has persisted: most of these modern tools only function correctly if data follows specific, often unrealistic, scaling rules.
Researchers from the University of Cambridge, University of Antwerp, and KU Leuven have introduced NOTIME, a framework that brings provable identifiability to differentiable causal discovery. NOTIME is the first differentiable algorithm that guarantees finding the true graph in Linear Non-Gaussian Additive Models (LiNGAM) regardless of data scaling.
The Problem: Identifiability in Differentiable Learning
In 2018, the NOTEARS algorithm transformed the discrete problem of finding a Directed Acyclic Graph (DAG) into a continuous optimization task using an "acyclicity constraint." Despite this breakthrough, NOTEARS and its successors (like DAGMA or GOLEM) typically rely on Mean Squared Error (MSE) as their objective function.
MSE-based methods are only guaranteed to find the correct graph if all "noise" variables in the system have the exact same variance. In real-world scenarios, this is rarely true. Standard data preprocessing—such as normalizing variables to a variance of 1—actually breaks these algorithms. If units are changed (e.g., from meters to millimeters), a standard differentiable learner might incorrectly reverse the causal direction.
Methodology: The NOTIME Framework
NOTIME (Non-combinatorial Optimization of Trace exponential and Independence MEasures) addresses these identifiability issues by making two major changes to the standard differentiable pipeline:
- Independence as the Objective: Instead of minimizing prediction error (MSE), NOTIME minimizes the d-dimensional Hilbert Schmidt Independence Criterion (dHSIC). In a causal model, the residuals should be jointly independent if the graph is correct. dHSIC is a kernel-based method that detects complex dependencies between multiple variables simultaneously.
- Scale-Invariant Sparsity: The authors introduce a modified $\ell_1$ penalty incorporating a "de-standardization" matrix. This ensures that the pressure for graph sparsity remains consistent even if the scale of input variables changes.
By combining these with the standard "trace exponential" constraint to ensure acyclicity, NOTIME creates a learner that is mathematically scale-invariant.
Key Results and Empirical Performance
The researchers evaluated NOTIME against synthetic simulations (Erdős-Rényi graphs with 10 to 100 variables), scaling stress tests, and real-world data (NASA Airfoil Self-Noise dataset).
- Robustness to Scaling: In experiments where data was "reversely scaled" to confuse learners, NOTIME maintained a low Average Structural Hamming Distance (ASHD). In contrast, competitors like NOTEARS and DAGMA saw error rates spike by an order of magnitude.
- Superior Accuracy: On exponential and $t_3$ noise, NOTIME consistently outperformed other differentiable methods. As shown in the performance plots, NOTIME's error converges toward zero as sample sizes increase, while traditional methods like GES and NOTEARS plateau at significantly higher error levels.
- Real-World Application: On the Airfoil dataset, NOTIME produced a sparser and more accurate graph than NOTEARS, which tended to produce dense graphs with false-positive edges and cycles.
Limitations and Future Work
While a major step forward, NOTIME faces several challenges. Calculating dHSIC and its gradients is computationally more expensive than MSE, with a complexity of roughly $O(nd^4)$. Additionally, causal identifiability through independence is "sample hungry," requiring more data than variance-based methods to reliably recover structure in high-dimensional graphs. Finally, while NOTIME is currently built for linear models, extending the framework to non-linear additive noise models remains a task for future research.
Summary updated