PaperlayerView exact revision on arXiv

Source-linked AI summary

Network Inference via the Time-Varying Graphical Lasso

David Hallac, Youngsuk Park, Stephen Boyd, Jure Leskovec

arXiv:1703.01958v2cs.LGcs.SImath.OC

TL;DR

The paper addresses how to infer interpretable relationships among entities from multivariate time series when those relationships change over time. It introduces TVGL, a sparse inverse-covariance formulation with flexible temporal penalties and an ADMM solver. TVGL improves accuracy by up to 92% over two state-of-the-art baselines and scales to 5 million unknown variables in under 12 minutes.

  • Problem

    Inferring dynamic networks requires learning both network structure and its diverse temporal changes from multivariate timestamped observations.

  • Method

    TVGL estimates sparse inverse covariance matrices over time using coupled graphical-lasso objectives, evolutionary penalties, and an ADMM-based scalable solver.

  • Results

    TVGL improves accuracy by up to 92% over two state-of-the-art baselines and solves 5 million unknown variables in under 12 minutes.

  • Takeaways & Limitations

    TVGL supports interpretable dynamic-network inference across different evolutionary patterns and real-world sensor and financial data.

  • Takeaways & Limitations

    The current algorithm assumes a zero-mean distribution and is suited to simultaneously related entities rather than correlations across different timestamps.

Abstract

from arXiv · show

Many important problems can be modeled as a system of interconnected entities, where each entity is recording time-dependent observations or measurements. In order to spot trends, detect anomalies, and interpret the temporal dynamics of such data, it is essential to understand the relationships between the different entities and how these relationships evolve over time. In this paper, we introduce the time-varying graphical lasso (TVGL), a method of inferring time-varying networks from raw time series data. We cast the problem in terms of estimating a sparse time-varying inverse covariance matrix, which reveals a dynamic network of interdependencies between the entities. Since dynamic network inference is a computationally expensive task, we derive a scalable message-passing algorithm based on the Alternating Direction Method of Multipliers (ADMM) to solve this problem in an efficient way. We also discuss several extensions, including a streaming algorithm to update the model and incorporate new observations in real time. Finally, we evaluate our TVGL algorithm on both real and synthetic datasets, obtaining interpretable results and outperforming state-of-the-art baselines in terms of both accuracy and scalability.

1 INTRODUCTION

The paper introduces TVGL for inferring sparse networks whose dependencies evolve over time, addressing the difficulty of learning both network structure and temporal changes. It combines flexible evolutionary penalties with a scalable ADMM-based solver and evaluates the approach on synthetic and real data.

  • 1 INTRODUCTION: Dynamic network inference must accommodate changes ranging from one or two edges changing to an entire network restructuring.This variety makes simultaneous estimation of network structure and its evolution challenging.
  • 1 INTRODUCTION: TVGL infers time-varying inverse covariance matrices to reveal dependencies between entities and when those dependencies change.The inverse covariance representation supports dynamic undirected networks from multivariate observations.
  • 1 INTRODUCTION: TVGL uses five evolutionary penalties to model different temporal patterns, including smooth variation, edge rewiring, node changes, and broader restructuring.Selecting the appropriate penalty is important for accurate results because prior dynamic methods support fewer temporal patterns.
  • 1 INTRODUCTION: The ADMM-based implementation solves 5 million unknown variables in under 12 minutes, while other solvers require several hours for 50 thousand unknowns.The method is designed to address the computational cost of dynamic network inference.
  • 1 INTRODUCTION: On synthetic data, TVGL improves accuracy by up to 92% over two state-of-the-art baselines and is evaluated further on financial and automobile sensor data.The real-world case studies demonstrate meaningful structure and different evolutionary patterns in time series data.
  • 1 INTRODUCTION: Unlike Kalman filters, which typically predict unknown values from previous data, TVGL learns the underlying dynamic graphical structure.The paper also distinguishes TVGL from cascade-based inference, which assumes viral spreading and uses infection times.

2 PROBLEM DEFINITION

TVGL formulates dynamic network inference as a convex optimization problem over sparse inverse covariance matrices coupled across time. Its likelihood, sparsity, and temporal penalties support interpretable estimates and multiple patterns of network evolution.

  • 2 PROBLEM DEFINITION: The method estimates one sparse inverse covariance matrix Θ_i = Σ(t_i)^−1 for each timestamp from Gaussian multivariate observations.The estimates use local empirical observations and coupling constraints with neighboring timestamps.
  • 2 PROBLEM DEFINITION: TVGL couples a sequence of graphical-lasso problems in a chain to penalize deviations between neighboring network estimates.Each chain element solves for a network slice at one timestamp.
  • 2 PROBLEM DEFINITION: When the empirical covariance is rank deficient, neighboring estimates borrow strength through structural similarity.This supports estimation in high-dimensional settings where the number of dimensions exceeds the number of observations.
  • 2 PROBLEM DEFINITION: The optimization balances empirical fit, element-wise sparsity, and temporal consistency through likelihood, λ, and β-dependent penalties.Sparsity improves interpretability, while temporal consistency encourages similar estimates at adjacent timestamps.
  • 2 PROBLEM DEFINITION: An element-wise ℓ1 temporal penalty is suited to only a handful of edges changing at a time.It encourages the rest of neighboring graphs to remain exactly the same.
  • 2 PROBLEM DEFINITION: A Laplacian penalty produces smoothly varying estimates, whereas ℓ∞ and row-column overlap penalties target block restructuring and perturbed-node behavior.The penalty should match the expected temporal evolution of the network.

3 EXTENSIONS

TVGL is extended to handle asynchronous, intermediate-time, and streaming observations. The streaming approximation updates only recent network estimates while fixing an older estimate to provide predictable computation.

  • Extensions: The extensions support asynchronous observations, intermediate-time network estimates, and streaming real-time updates.They address irregular sampling, unobserved times, and continually arriving data.
  • Asynchronous Observations: For irregularly spaced samples, temporal consistency is weakened as the interval between consecutive observations grows.Convexity motivates evenly distributing changes across intermediate time steps.
  • Inferring Intermediate Networks: Intermediate networks can be inferred at unobserved times by inserting a dummy node between neighboring observations.For common penalties, the resulting estimate has a closed-form solution and supports covariance upsampling.
  • Streaming Algorithm: Warm-start ADMM may take increasingly long to incorporate later observations because new information can propagate across the entire time series.The 1000th reading may therefore take longer to incorporate than the 100th.
  • Streaming Algorithm: The streaming approximation fixes Θi−m to its previous value and re-solves only the m most recent nodes after a new observation arrives.The window size m can be selected using memory limits, previous breakpoints, or domain expertise.

4 PROPOSED ALGORITHM

The proposed algorithm solves TVGL through ADMM by splitting the optimization into separable subproblems. Consensus variables and proximal updates enable parallel computation, closed-form updates for several penalties, and global convergence.

  • ADMM Solution: TVGL uses ADMM to split a large convex optimization problem into message-passing subproblems that converge to the globally optimal solution.The approach targets examples where solving the full problem with standard interior-point methods is infeasible.
  • ADMM Solution: Consensus variables separate per-time inverse covariance terms from temporal penalty terms while preserving equivalent constraints.The split introduces Z0, Z1, and Z2 blocks connected to the Θ variables.
  • ADMM Updates: The Θ-step updates each Θi independently and in parallel, while the Z-update handles sparsity and temporal-consistency components.The sparsity term uses an ℓod,1 penalty, and the temporal term operates on paired neighboring variables.
  • Θ-Update: The computationally expensive matrix decomposition in each Θ-update has O(p3) runtime for a p × p matrix.This decomposition is the dominant computational task identified for the algorithm.
  • Z-Update: Proximal operators provide closed-form or efficiently solvable updates for element-wise ℓ1, group-lasso ℓ2, Laplacian, ℓ∞, and perturbed-node penalties.The ℓ1 update uses element-wise soft thresholding, while the group-lasso ℓ2 update uses block-wise soft thresholding; perturbed-node penalties require nested ADMM.

5 IMPLEMENTATION

The implementation provides a Python TVGL solver that accepts observations, regularization parameters, and penalty types, returning a time-varying network.

  • Implementation: The custom TVGL Python solver runs on SnapVX and accepts observations, regularization parameters, and five penalty types.Supported penalties are ℓ1, ℓ2, Laplacian, ℓ∞, and perturbed node.
  • Implementation: Although TVGL can distribute computation across machines, the implementation distributes it across multiple cores of one large-memory machine.

6 EXPERIMENTS

Experiments evaluate TVGL on synthetic networks with known ground truth, comparing accuracy under different temporal shifts and penalties, then benchmark scalability against alternative solvers.

  • 6.1 Accuracy on Synthetic Data: Synthetic experiments test global and local network shifts in R10 over 100 timestamps, with each shift occurring at t = 50 and 10 samples per timestamp.
  • 6.1 Accuracy on Synthetic Data: Accuracy is evaluated using F1 score for edge recovery and the temporal deviation ratio for identifying the true shift timestamp.
  • 6.1 Accuracy on Synthetic Data: TVGL’s F1 score is up to 38.4% higher than the kernel method and 91.9% higher than the static graphical lasso.
  • 6.1 Accuracy on Synthetic Data: TVGL’s temporal deviation ratio is at least 9.7 times larger than either baseline, with its largest peak correctly occurring at t = 50.

7 CASE STUDIES

The case studies apply TVGL to financial and automobile sensor data, identifying localized and market-wide network changes and interpretable sensor relationships.

  • Financial data: TVGL identifies a late-January local shift in the stock network and attributes the affected node to Apple.Only Apple’s edges changed at the detected shift, coinciding with Apple’s January 27 iPad introduction.
  • Financial data: The post-announcement financial network links Apple, Google, Amazon, and Intel closely, while FedEx and Boeing connect only to Amazon.The model predicts FedEx and Boeing are conditionally independent given Amazon across the dataset.
  • Financial data: TVGL detects a market-wide shift during the week of May 6, 2010, coinciding with the Flash Crash’s 9% market drop.The results indicate lasting effects on the S&P 500 correlation network despite the recovery in stock prices.
  • Automobile sensors: The automobile case study tracks eight sensors sampled every 0.1 seconds before, during, and after a standard right turn.A Laplacian penalty enforces a smoothly varying network because sudden shifts are not expected.
  • Automobile sensors: During the turn, steering-wheel angle explains much of the variation in other sensors, whereas it lies on the network periphery on straightaways.The changing network position illustrates how sensor relationships reflect driving behavior.

8 CONCLUSION AND FUTURE WORK

The paper presents TVGL as a general, scalable framework for inferring dynamic networks from timestamped observations. Future work includes richer temporal penalties, time-varying means and covariances, and cross-time correlations.

  • Conclusion: TVGL is a general method for inferring dynamic networks from timestamped observational data with scalable support for varied temporal dependencies.The framework is intended for large-scale sensor deployments.
  • Future work: Future work includes penalty functions for additional network-evolution behaviors and corresponding closed-form proximal-operator solutions.The paper also notes extensions beyond those discussed in its main framework.
  • Future work: The current model assumes a zero-mean underlying distribution and does not jointly estimate time-varying means and covariances.A proposed extension models x ∼ N(µ(t), Σ(t)) while estimating both quantities over time.
  • Future work: The current algorithm captures simultaneous relationships but not correlations across different timestamps.The paper gives delayed neural responses as an example motivating cross-time correlation modeling.
Loading 1703.01958v2…