Learning Time-Varying Graphs form Online Data

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.