# Low-rank Updates in Slowly Time-varying Graphs for Spatial-Temporal Signal Interpolation

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

## Key facts

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

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Spatio-Temporal Graph Convolutional Networks: A Deep Learning Framework for Traffic Forecasting](https://mlsanity.com/paper/1709.04875/) (2017)
- [GMAN: A Graph Multi-Attention Network for Traffic Prediction](https://mlsanity.com/paper/1911.08415/) (2019)
- [Graph Signal Processing: Overview, Challenges and Applications](https://mlsanity.com/paper/1712.00468/) (2017)
- [T-GCN: A Temporal Graph ConvolutionalNetwork for Traffic Prediction](https://mlsanity.com/paper/1811.05320/) (2018)
- [Learning graphs from data: A signal representation perspective](https://mlsanity.com/paper/1806.00848/) (2018)
- [DynGEM: Deep Embedding Method for Dynamic Graphs](https://mlsanity.com/paper/1805.11273/) (2018)
- [Dynamic Graph Convolutional Networks](https://mlsanity.com/paper/1704.06199/) (2017)
- [Predicting Path Failure In Time-Evolving Graphs](https://mlsanity.com/paper/1905.03994/) (2019)
- [Graph Spectral Image Processing](https://mlsanity.com/paper/1801.04749/) (2018)
- [Attributed Network Embedding for Learning in a Dynamic Environment](https://mlsanity.com/paper/1706.01860/) (2017)
- [Lifelong Graph Learning](https://mlsanity.com/paper/2009.00647/) (2020)
- [Graph-Based Blind Image Deblurring From a Single Photograph](https://mlsanity.com/paper/1802.07929/) (2018)
- [Signed Graph Metric Learning via Gershgorin Disc Perfect Alignment](https://mlsanity.com/paper/2006.08816/) (2020)
- [Deep Graph Laplacian Regularization for Robust Denoising of Real Images](https://mlsanity.com/paper/1807.11637/) (2018)
- [Graph Signal Restoration Using Nested Deep Algorithm Unrolling](https://mlsanity.com/paper/2106.15910/) (2021)
- [Random Walk Graph Laplacian based Smoothness Prior for Soft Decoding of JPEG Images](https://mlsanity.com/paper/1607.01895/) (2016)
- [Unrolling of Deep Graph Total Variation for Image Denoising](https://mlsanity.com/paper/2010.11290/) (2020)
- [Learning Time-Varying Graphs from Online Data](https://mlsanity.com/paper/2110.11017/) (2021)
- [Interpretable Lightweight Transformer via Unrolling of Learned Graph Smoothness Priors](https://mlsanity.com/paper/2406.04090/) (2024)
- [Manifold Graph Signal Restoration using Gradient Graph Laplacian Regularizer](https://mlsanity.com/paper/2206.04245/) (2022)
- [Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect Alignment](https://mlsanity.com/paper/2208.08726/) (2022)
- [Network Topology Inference with Sparsity and Laplacian Constraints](https://mlsanity.com/paper/2309.00960/) (2023)
- [Fast DCT+: A Family of Fast Transforms Based on Rank-One Updates of the Path Graph](https://mlsanity.com/paper/2409.08970/) (2024)

## Abstract (arXiv)

A crucial assumption in graph signal processing (GSP) is the existence of an underlying graph that captures the pairwise similarities between nodes, allowing filters to be designed based on this graph for tasks such as denoising. For spatial-temporal data in which node-to-node similarities evolve over time, a static spatial graph is insufficient. In this paper, to represent slowly time-varying pairwise relationships, we model the graph changes in two consecutive adjacency matrices P = W(2) - W(1) across time as a low-rank matrix. % Specifically, given an initial adjacency matrix W(1) at time t=1, we jointly interpolate a signal x2 and estimate W(2) at t=2 using both a graph signal smoothness prior for x2 and a low-rank prior on P. We alternate optimization steps. With W(2) fixed, x2 is interpolated by solving a linear system. Alternatively, holding x2 fixed, W(2) is updated via proximal gradient descent (PGD). The proximal mapping of the rank term Gamma(W(2) - W(1)) is approximated in linear time using a fast orthogonal matching pursuit (OMP) algorithm that selects a sparse combination of atoms from a dictionary cR formed by the outer products of W(1)'s eigenvectors. We unroll iterations of our algorithm into layers to build a lightweight neural network for limited data-driven parameter tuning. Experiments show that our joint optimization achieves better signal interpolation compared to existing time-varying graph models.