# Learning Time-Varying Graphs from Incomplete Graph Signals

arXiv: https://arxiv.org/abs/2510.17903 · HTML: https://mlsanity.com/paper/2510.17903/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 25 of its 67 references that are in the map.
- First posted on arXiv 19 Oct 2025.

## Builds on (most cited first, 25 of 25)

- [How to learn a graph from smooth signals](https://mlsanity.com/paper/1601.02513/) (2016)
- [Handling Missing Data with Graph Representation Learning](https://mlsanity.com/paper/2010.16418/) (2020)
- [Network Inference via the Time-Varying Graphical Lasso](https://mlsanity.com/paper/1703.01958/) (2017)
- [Missing Data Imputation with Adversarially-trained Graph Convolutional Networks](https://mlsanity.com/paper/1905.01907/) (2019)
- [Graph Signal Processing: History, Development, Impact, and Outlook](https://mlsanity.com/paper/2303.12211/) (2023)
- [Learning Graphs from Smooth and Graph-Stationary Signals with Hidden Variables](https://mlsanity.com/paper/2111.05588/) (2021)
- [Joint Network Topology Inference in the Presence of Hidden Nodes](https://mlsanity.com/paper/2306.17364/) (2023)
- [Kernel-based Graph Learning from Smooth Signals: A Functional Viewpoint](https://mlsanity.com/paper/2008.10065/) (2020)
- [Gegenbauer Graph Neural Networks for Time-varying Signal Reconstruction](https://mlsanity.com/paper/2403.19800/) (2024)
- [Dynamic Spatiotemporal Graph Convolutional Neural Networks for Traffic Data Imputation with Complex Missing Patterns](https://mlsanity.com/paper/2109.08357/) (2021)
- [Higher-order Spatio-temporal Physics-incorporated Graph Neural Network for Multivariate Time Series Imputation](https://mlsanity.com/paper/2405.10995/) (2024)
- [A Computational Framework for Modeling Complex Sensor Network Data Using Graph Signal Processing and Graph Neural Networks in Structural Health Monitoring](https://mlsanity.com/paper/2105.05316/) (2021)
- [Sparse Graph Learning Under Laplacian-Related Constraints](https://mlsanity.com/paper/2111.08161/) (2021)
- [Distributionally Robust Graph Learning from Smooth Signals under Moment Uncertainty](https://mlsanity.com/paper/2105.05458/) (2021)
- [Learning Sparse Graphs via Majorization-Minimization for Smooth Node Signals](https://mlsanity.com/paper/2202.02815/) (2022)
- [Robust Time-Varying Graph Signal Recovery for Dynamic Physical Sensor Network Data](https://mlsanity.com/paper/2202.06432/) (2022)
- [Inferring Network Structure with Unobservable Nodes from Time Series Data](https://mlsanity.com/paper/2202.10144/) (2022)
- [Gradients of Connectivity as Graph Fourier Bases of Brain Activity](https://mlsanity.com/paper/2009.12567/) (2020)
- [Joint Signal Recovery and Graph Learning from Incomplete Time-Series](https://mlsanity.com/paper/2312.16940/) (2023)
- [Graph Signal Reconstruction Techniques for IoT Air Pollution Monitoring Platforms](https://mlsanity.com/paper/2201.00378/) (2022)
- [Spatial-temporal traffic modeling with a fusion graph reconstructed by tensor decomposition](https://mlsanity.com/paper/2212.05653/) (2022)
- [Network Topology Inference from Smooth Signals Under Partial Observability](https://mlsanity.com/paper/2410.05707/) (2024)
- [Time-Varying Graph Learning for Data with Heavy-Tailed Distribution](https://mlsanity.com/paper/2501.00606/) (2024)
- [Bayesian Spillover Graphs for Dynamic Networks](https://mlsanity.com/paper/2203.01912/) (2022)
- [Estimating and Analyzing Neural Information Flow Using Signal Processing on Graphs](https://mlsanity.com/paper/2205.13719/) (2022)

## Abstract (arXiv)

This paper tackles the challenging problem of jointly inferring time-varying network topologies and imputing missing data from partially observed graph signals. We propose a unified non-convex optimization framework to simultaneously recover a sequence of graph Laplacian matrices while reconstructing the unobserved signal entries. Unlike conventional decoupled methods, our integrated approach facilitates a bidirectional flow of information between the graph and signal domains, yielding superior robustness, particularly in high missing-data regimes. To capture realistic network dynamics, we introduce a fused-lasso type regularizer on the sequence of Laplacians. This penalty promotes temporal smoothness by penalizing large successive changes, thereby preventing spurious variations induced by noise while still permitting gradual topological evolution. For solving the joint optimization problem, we develop an efficient Proximal Alternating Direction Method of Multipliers (PADMM) algorithm, which leverages the problem's structure to yield closed-form solutions for both the graph and signal subproblems. This design ensures scalability to large-scale networks and long time horizons. On the theoretical front, despite the inherent non-convexity, we establish a convergence guarantee, proving that the proposed PADMM scheme converges to a stationary point. Furthermore, we derive non-asymptotic statistical guarantees, providing high-probability error bounds for the graph estimator as a function of sample size, signal smoothness, and the intrinsic temporal variability of the graph. Extensive numerical experiments validate the approach, demonstrating that it significantly outperforms state-of-the-art baselines in both convergence speed and the joint accuracy of graph learning and signal recovery.