Abstract
Reconstructing the interaction network of a system governed by Stochastic Differential Equations (SDEs) is a fundamental challenge in fields like systems biology and finance. This paper provides a rigorous theoretical framework for this "inverse problem" using $\ell_1$-regularized least squares. We demonstrate that sparse networks can be accurately recovered with a total observation time that scales only logarithmically with the number of variables, independent of sampling frequency, provided the sampling is sufficiently fast.
Introduction
Many complex systems, from protein-protein interactions to financial markets, are modeled as networks of variables evolving over time. These dynamics are often captured by linear Stochastic Differential Equations (SDEs), where the change in a variable depends on its neighbors and stochastic noise. Learning the underlying network structure from observed trajectories is difficult because data points are inherently correlated, violating the i.i.d. assumption of standard machine learning. This paper addresses the "time complexity" of network recovery—the total observation time $T$ required to reconstruct the graph with high probability.
Methodology
The study focuses on a linear SDE model: $$dx(t) = A^0 x(t) dt + db(t)$$ where $A^0$ is the interaction matrix and $b(t)$ is Brownian motion. The authors employ an $\ell_1$-regularized least squares estimator (Lasso) to recover $A^0$. By minimizing a likelihood function that compares observed rates of change to predicted linear interactions, and applying an $\ell_1$ penalty to promote sparsity, the algorithm identifies the most likely network structure. The analysis covers both discrete-time sampling and the continuous-time limit.
Key Insights: Time Complexity and Scalability
A central finding is that for a fixed observation window $T$, increasing the sampling frequency (decreasing the interval $\eta$) eventually yields diminishing returns. Once the sampling is "fast enough," the success of the recovery depends primarily on the total time $T$ rather than the number of samples $n$.
Furthermore, the required observation time $T$ scales logarithmically with the number of nodes $p$ in the network. This logarithmic scalability is a powerful result, implying that very large sparse networks can be learned efficiently.
Experimental Results
The theoretical bounds were validated using synthetic datasets, including random sparse networks and Laplacian graphs. Numerical simulations confirm that the probability of success converges as the total observation time $T$ increases.
The results show that for a fixed $p$, the success probability follows a characteristic S-curve relative to $T$. As $p$ increases, the curves shift to the right, but only slightly, consistent with the logarithmic dependence on $p$.
Conclusion and Future Work
This work establishes a solid foundation for learning the architecture of stochastic systems. It highlights the importance of the system's "relaxation time" and provides concrete guarantees for recovery in the linear regime. Future research may extend these results to non-linear dynamics or scenarios with latent variables, where not all nodes in the network are observable.
Summary updated