Abstract
Structural learning, which aims to learn directed acyclic graphs (DAGs) from observational data, is foundational to causal reasoning and scientific discovery. Recent advancements formulate structural learning into a continuous optimization problem; however, DAG learning remains a highly non-convex problem, and there has not been much work on leveraging well-developed convex optimization techniques for causal structural learning. We fill this gap by proposing a data-adaptive linear approach for causal structural learning from time series data, which can be conveniently cast into a convex optimization problem using a recently developed monotone operator variational inequality (VI) formulation. Furthermore, we establish non-asymptotic recovery guarantee of the VI-based approach and show the superior performance of our proposed method on structure recovery over existing methods via extensive numerical experiments.
Introduction
Causal discovery—the process of identifying "who causes what" in a complex system—is a cornerstone of scientific inquiry. In the context of time series data, this involves learning a Directed Acyclic Graph (DAG) that represents how variables interact across time. Despite its importance, learning these structures is notoriously difficult due to two primary hurdles: the combinatorial complexity of the acyclicity constraint (ensuring no loops like A → B → A exist) and the non-convexity of modern continuous optimization approaches. While recent gradient-based methods have improved the field, they often get trapped in local optima and lack the strong theoretical guarantees associated with convex optimization.
This research introduces a novel framework that transforms DAG learning from time series into a convex optimization problem. By utilizing monotone operator variational inequalities (VI), the authors provide a more efficient and theoretically grounded method for recovering causal relationships.
Methodology
The proposed approach models time series data using a Generalized Linear Model (GLM) based on a discrete-time Bernoulli process. The framework is built upon two innovative pillars:
1. Data-Adaptive Linear Regularization
Traditional methods often use complex, non-convex functions to enforce acyclicity. In contrast, this paper introduces a "cycle elimination" penalty that targets potential cycles of lengths 1, 2, and 3 in an initial estimate. By applying a linear penalty to shrink the "least important" edges within these identified cycles, the authors maintain a convex optimization landscape. This adaptive strategy effectively induces a DAG structure without the computational burden of non-convex constraints.
2. Variational Inequality (VI) Formulation
The authors cast parameter estimation as a monotone operator variational inequality. This mathematical framework allows for the decoupling of inference for each node, enabling parallel computation. Furthermore, it supports a wide range of non-linear "link functions" (such as sigmoid or exponential) to describe how past events trigger future ones, providing a path to joint estimation with the DAG penalty.
Key Insights
- The Power of Convexity: By relaxing the hard DAG constraint into a data-adaptive linear penalty, the problem enters the realm of convex optimization. This ensures that the solution found is globally optimal and allows for the use of highly efficient, well-developed solvers.
- Short Cycle Targeting: While the penalty explicitly addresses cycles of length $\leq 3$, experiments demonstrate that this is often sufficient to induce a full DAG structure in practice, especially when paired with the authors' hyperparameter selection strategy.
- Monitoring "DAG-ness": The researchers utilize a metric, $h(A)$ (the trace of the matrix exponential), to monitor the graph's proximity to a DAG. They observed that optimal structural recovery occurs precisely when this measure converges to zero, offering a practical tuning mechanism.
Experimental Results
The method was evaluated using synthetic datasets simulating various scenarios, scaling from 10 to 30 nodes ($d_1$) and time horizons ($T$) from 500 to 1500. The proposed method consistently outperformed benchmarks such as standard DAG regularization (NOTEARS-style), $\ell_1$ regularization (Lasso), and Adaptive $\ell_1$ in terms of Structural Hamming Distance (SHD).
- Accuracy: In 10-node trials, the proposed method achieved an SHD of 7, significantly better than standard DAG regularization (21) and Lasso (25).
- Scalability: As dimensions increased to 30 nodes, the performance gap widened. The proposed method maintained a relatively low SHD (around 73), while standard DAG regularization errors spiked to approximately 300.
- Theoretical Foundations: Beyond empirical success, the authors established a non-asymptotic recovery guarantee, providing a mathematical upper bound on estimation error—a significant contribution to the field of non-linear causal discovery.
Conclusion and Future Work
This work demonstrates that causal structural learning can be effectively handled through convex optimization. While the current implementation focuses on cycles of length $\leq 3$ and has been validated primarily on synthetic data, it opens new avenues for efficient causal discovery. Future research will aim to provide formal theoretical guarantees for the data-adaptive regularizer itself and extend the application of this framework to real-world datasets in fields such as finance and biology.
Summary updated