Source-linked AI summary
DYNOTEARS: Structure Learning from Time-Series Data
Roxana Pamfil, Nisara Sriwattanaworachai, Shaan Desai, Philip Pilgerstorfer, Paul Beaumont, Konstantinos Georgatzis, Bryon Aragam
TL;DR
The paper addresses learning both contemporaneous and time-lagged structure in dynamic Bayesian networks. It proposes DYNOTEARS, a score-based method using penalized loss and a smooth acyclicity constraint, and reports strong simulated-data performance, including high-dimensional settings, plus applications to finance and molecular biology. The authors conclude that it is simple, scalable, and accurate on real data.
Problem
Learning graphical structure from temporally fluctuating data requires modeling dynamic Bayesian networks rather than only static relationships.
Method
DYNOTEARS jointly estimates intra-slice and inter-slice dependencies by minimizing a penalized score-based objective with a differentiable acyclicity constraint.
Results
DYNOTEARS achieves F1 scores close to 1 for n = 500 and performs best when d = 100 exceeds the number of samples in the reported simulations.
Takeaways & Limitations
The method supports DBN learning on high-dimensional data and applications with approximately 100 variables in finance and molecular biology.
Takeaways & Limitations
The assumed DBN structure is fixed through time and identical across time series, while nonstationarity, confounders, and changing structure remain future-work topics.
Abstract
from arXiv · showhide
We revisit the structure learning problem for dynamic Bayesian networks and propose a method that simultaneously estimates contemporaneous (intra-slice) and time-lagged (inter-slice) relationships between variables in a time-series. Our approach is score-based, and revolves around minimizing a penalized loss subject to an acyclicity constraint. To solve this problem, we leverage a recent algebraic result characterizing the acyclicity constraint as a smooth equality constraint. The resulting algorithm, which we call DYNOTEARS, outperforms other methods on simulated data, especially in high-dimensions as the number of variables increases. We also apply this algorithm on real datasets from two different domains, finance and molecular biology, and analyze the resulting output. Compared to state-of-the-art methods for learning dynamic Bayesian networks, our method is both scalable and accurate on real data. The simple formulation and competitive performance of our method make it suitable for a variety of problems where one seeks to learn connections between variables across time.
1 Introduction
Dynamic structure learning extends graphical-model structure learning to temporal dependencies, while DYNOTEARS jointly estimates contemporaneous and time-lagged relationships through scalable score-based optimization.
- Dynamic models explicitly represent temporal dependencies, unlike static models designed for independent and identically distributed data.
- DYNOTEARS is a score-based method for learning DBNs of arbitrary order without bounded in-degree or treewidth assumptions.It uses standard optimization routines and is based on a differentiable acyclicity characterization.
- DYNOTEARS simultaneously estimates intra-slice and inter-slice dependencies rather than estimating them successively.
- The method targets accuracy on high-dimensional data, robustness to complex graph topologies, and a simple plug-and-play optimization algorithm.The paper applies it to stock returns with d = 97 and DREAM4 molecular-biology data with d = 100.
- Existing DBN methods variously omit contemporaneous dependencies, estimate relationship types independently, or use two-step procedures.Related methods include constraint-based, score-based, and hybrid approaches.
2 Dynamic Structure Learning
The paper formulates DBN learning as a penalized structural-equation problem with contemporaneous and lagged weighted graphs, then replaces acyclicity with a smooth equality constraint for optimization.
- 2.1 Formulation: The model assumes stationary time series whose variables have both contemporaneous intra-slice and time-lagged inter-slice influences.The network structure is assumed constant across time.
- 2.1 Formulation: Weighted adjacency matrix W represents intra-slice edges, while A1 through Ap represent inter-slice edges across p lags.Lagged data can include selected noncontiguous time points, such as seasonally relevant slices.
- 2.1 Formulation: Identifiability is established in two cases: non-Gaussian errors or standard Gaussian errors combined with acyclicity of W.
- 2.2 Optimization problem: The objective minimizes least-squares reconstruction loss with ℓ1 penalties on W and A, subject to W being acyclic.Regularization is especially useful when n ≪ d.
- 2.2 Optimization problem: Acyclicity is enforced through h(W) = tr e^(W◦W) − d = 0, an equivalent smooth equality constraint optimized with an augmented Lagrangian.
- 2.3 Alternative formulations: The alternative two-stage formulation fits a reduced-form VAR, applies static NOTEARS to residuals for W, and then recovers lagged matrices.Its errors can make sparsity enforcement difficult and propagate into later estimates.
3 Experiments
DYNOTEARS is evaluated through simulations with known ground truth across noise models, sample sizes, graph structures, and dimensions. It generally performs best, including when variables outnumber samples.
- Experimental setup: The simulations generate weighted intra-slice and inter-slice graphs, compatible data matrices, and benchmark metrics against three alternative algorithms.The alternatives are NOTEARS + Lasso, LiNGAM, and tsGFCI.
- Illustrative recovery: In a Gaussian example with n = 500, d = 5, and p = 3, DYNOTEARS estimates W and A close to their true weights.Only one significant omission appears: an entry in the third row and third column of A2.
- Benchmark design: Figure 3 varies Gaussian and Exponential noise, n ∈{50, 500}, five graph dimensions, and separate intra-slice and inter-slice F1 scores.Each marker averages performance across five runs on different simulated datasets.
- Benchmark results: F1 scores are close to 1 for n = 500, and DYNOTEARS remains best-performing when d = 100 exceeds the number of samples.This high-dimensional setting is identified as especially difficult; NOTEARS + Lasso underperforms because Lasso falsely assigns some intra-slice edges to inter-slice structure.
4 Applications
The applications examine whether contemporaneous or time-lagged relationships dominate in financial and molecular-biology data. DYNOTEARS finds sector-structured stock relationships, no inter-slice stock edges, and competitive DREAM4 performance among DBN methods.
- Application scope: The applications use DYNOTEARS to assess whether contemporaneous or time-lagged relationships are more meaningful in different datasets.The paper discusses examples in which each interaction type is dominant.
- Financial data: The S&P 100 dataset contains 1,257 daily observations and 97 stock variables after log-return transformation and normalization.DYNOTEARS is applied with p = 1, λW = 0.1, and λA = 0.1, while the final 400 observations are held out for validation.
- Financial results: The estimated stock network is approximately block-diagonal by industry sector, with same-sector stocks more likely to influence each other.The sector-community agreement has normalized mutual information of approximately 0.79.
- Molecular-biology results: On DREAM4, DYNOTEARS averages AUROC 0.664 and AUPR 0.173, ranking first and second among six DBN methods for AUPR and AUROC, respectively.Across all compared methods, it ranks fourth in AUPR and eighth in AUROC.
5 Discussion
DYNOTEARS learns intra-slice and inter-slice dependencies simultaneously and performs well across simulated settings and larger real datasets. The discussion identifies fixed-structure, sampling-rate, and linearity assumptions as limitations or extension opportunities.
- DYNOTEARS simultaneously estimates intra-slice and inter-slice dependencies instead of estimating them in succession.
- DYNOTEARS performs well on simulated data across a wide range of data-generation parameter choices.
- The method was applied to finance and molecular-biology datasets, both with d ≈100, larger than datasets considered in most prior DBN work.
- Assumptions: The assumed DBN structure is fixed through time and identical across all time series.
- Undersampling: DYNOTEARS assumes the sampling rate is at least as high as fluctuations in the underlying causal process, and it was not designed for undersampled data.
- Nonlinear dependence: The linear model is adopted for simplicity, while nonlinear dependence modeling is left as a possible extension.
A Comparison of one-stage and two-stage algorithms
The one-stage and two-stage formulations produce nearly identical results when samples substantially exceed variables, but their behavior diverges in undersampled settings. The two-stage method is faster with sufficient data, whereas simultaneous estimation is preferred to avoid error propagation.
- With n ≫ dp, one-stage and two-stage algorithms give nearly identical results, while the two-stage version runs somewhat faster.
- When n < dp, reduced-form VAR estimation is underdetermined, producing zero residuals and no meaningful estimate of W.
- In undersampled settings, Ai is typically denser than Bi, so the two-stage formulation requires stronger regularization.
- Estimating W and A simultaneously via the combined loss is preferred because it prevents error propagation.
B Numerical experiments
The numerical experiments compare DYNOTEARS with independent estimation, SVAR/LiNGAM, and tsGFCI-based alternatives. The comparison also documents favorable handling of tsGFCI ambiguities and the hyperparameter settings used for simulated benchmarks.
- Alternative algorithms: Independent learning of W and A uses static NOTEARS for W and Lasso regression for A.
- Alternative algorithms: SVAR/LiNGAM first estimates a reduced-form VAR and then applies LiNGAM to residuals, with identifiability under non-Gaussian errors.
- Alternative algorithms: tsGFCI combines conditional-independence tests with local graph changes that incrementally improve the BIC score and returns a PAG.
- Evaluation caveat: Ambiguous tsGFCI outputs are resolved in its favor against the ground-truth DAG, slightly overstating its simulated performance.
- Hyperparameters: For n = 500, the simulations use λW = λA = 0.05; for n = 50, regularization increases to λW = λA = 0.2.
B.4 Data generation process
The numerical experiments generate weighted intra-slice and inter-slice graphs using ER, BA, and block-model constructions, then simulate time-series data with controllable lag-dependent weights. The autoregressive order can be diagnosed from objective plateaus and negligible higher-lag weights.
- Intra-slice model: Intra-slice graphs are generated with Erdős–Rényi or Barabási–Albert models at a target mean degree k.
- Intra-slice model: The Barabási–Albert construction produces DAGs with power-law degree distributions and randomized node ordering.
- Inter-slice model: Inter-slice graphs use directed ER or a two-block SBM, with same-block edges more likely than cross-block edges.
- Inter-slice model: Inter-slice edge weights decay with lag through α = 1/η^(p−1), reducing the influence of variables farther back in time when η > 1.
- Data generation: Data matrices X of size n × d are generated from W and A using a structural equation model with i.i.d. noise.
- Choosing p: For simulated data with ptrue = 5, the objective plateaus for p > ptrue and estimated Ap weights become close to zero.
- Choosing p: When p is unknown, one diagnostic is to increase p until the entries of Ap become negligible.
B.6 Running times
DYNOTEARS has running times that vary with graph properties and regularization, yet remains practical for datasets with around 100 variables.
- DYNOTEARS and NOTEARS + LiNGAM become faster with larger regularization parameters.Running times also depend on graph density and edge-weight distributions.
- CPU times are comparable across Gaussian and exponential noise and between n = 500 and n = 50 simulations.
- A typical laptop processes the S&P100 dataset with DYNOTEARS in a few minutes.The dataset contains approximately 100 variables.
B.7 Additional results
Additional experiments examine graph-density sensitivity, multiple performance metrics, parameter selection, and behavior across noise distributions and sample sizes.
- Graph-density sensitivity: tsGFCI is especially sensitive to graph density, with a notable F1-score drop when the intra-slice graph is ER4.
- Parameter selection: For DREAM4, CPU times are approximately 0.1, 1.5, and 60 minutes as λW decreases from 0.1 to 0.001 with λA = 0.01.
- Performance metrics: The additional metrics are TPR, FDR, SHD, and the Frobenius norm of weighted-matrix differences.The Frobenius norm does not apply to tsGFCI because it returns only unweighted edges.
- Performance metrics: DYNOTEARS generally outperforms other algorithms for n = 500 under both Gaussian and exponential noise.Exceptions occur when d ∈{5, 10, 20}.
- Performance metrics: For n = 50, NOTEARS + Lasso and LiNGAM produce dense graphs with high TPRs but many false positives.Their overall performance is therefore not competitive.
- Parameter selection: The S&P100 validation analysis selects λW = 0.1 and λA = 0.1 from a fairly smooth Frobenius-norm loss surface.
- Parameter selection: DREAM4 uses 10-fold cross-validation and RMSE to select λW and λA, with separate parameter selection for each dataset.The selected parameters are then used to compute average AUPR and AUROC.
D.2 Comparison to other methods
DYNOTEARS is compared with other structure-learning algorithms on DREAM4 gene-expression data using AUROC and AUPR, while combining its fast- and slow-acting influence matrices.
- Method comparison: DYNOTEARS returns W and A matrices representing fast-acting and slow-acting influences, respectively.The matrices are combined by element-wise summation into a final weight matrix.
- Evaluation: Heatmaps show cross-validation RMSE across λA and λW for the five DREAM4 datasets.
- Evaluation: DREAM4 comparisons report AUROC scores for 18 algorithms and AUPR scores for 23 algorithms.Values for methods other than DYNOTEARS come from Lu et al. (2019).