Learning Time-Varying Graphs from Online Data

Alberto Natali*, Elvin Isufi, Mario Coutino, Geert Leus

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

1 Citation (Scopus)
30 Downloads (Pure)

Abstract

This work proposes an algorithmic framework to learn time-varying graphs from online data. The generality offered by the framework renders it model-independent, i.e., it can be theoretically analyzed in its abstract formulation and then instantiated under a variety of model-dependent graph learning problems. This is possible by phrasing (time-varying) graph learning as a composite optimization problem, where different functions regulate different desiderata, e.g., data fidelity, sparsity or smoothness. Instrumental for the findings is recognizing that the dependence of the majority (if not all) data-driven graph learning algorithms on the data is exerted through the empirical covariance matrix, representing a sufficient statistic for the estimation problem. Its user-defined recursive update enables the framework to work in non-stationary environments, while iterative algorithms building on novel time-varying optimization tools explicitly take into account the temporal dynamics, speeding up convergence and implicitly including a temporal-regularization of the solution. We specialize the framework to three well-known graph learning models, namely, the Gaussian graphical model (GGM), the structural equation model (SEM), and the smoothness-based model (SBM), where we also introduce ad-hoc vectorization schemes for structured matrices (symmetric, hollows, etc.) which are crucial to perform correct gradient computations, other than enabling to work in low-dimensional vector spaces and hence easing storage requirements. After discussing the theoretical guarantees of the proposed framework, we corroborate it with extensive numerical tests in synthetic and real data.

Original languageEnglish
Article number9785716
Pages (from-to)212 - 228
Number of pages17
JournalIEEE Open Journal of Signal Processing
Volume3
DOIs
Publication statusPublished - 2022

Keywords

  • Graph topology identification
  • dynamic graph learning
  • network topology inference
  • graph signal processing

Fingerprint

Dive into the research topics of 'Learning Time-Varying Graphs from Online Data'. Together they form a unique fingerprint.

Cite this