# Temporal Graph Signal Decomposition

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 56 references that are in the map.
- First posted on arXiv 25 Jun 2021.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Spatial Temporal Graph Convolutional Networks for Skeleton-Based Action Recognition](https://mlsanity.com/paper/1801.07455/) (2018)
- [Spatio-Temporal Graph Convolutional Networks: A Deep Learning Framework for Traffic Forecasting](https://mlsanity.com/paper/1709.04875/) (2017)
- [Graph Signal Processing: Overview, Challenges and Applications](https://mlsanity.com/paper/1712.00468/) (2017)
- [Graph Convolutional Networks for Text Classification](https://mlsanity.com/paper/1809.05679/) (2018)
- [BRITS: Bidirectional Recurrent Imputation for Time Series](https://mlsanity.com/paper/1805.10572/) (2018)
- [Graph-based Anomaly Detection and Description: A Survey](https://mlsanity.com/paper/1404.4679/) (2014)
- [Learning graphs from data: A signal representation perspective](https://mlsanity.com/paper/1806.00848/) (2018)
- [Geometric Matrix Completion with Recurrent Multi-Graph Neural Networks](https://mlsanity.com/paper/1704.06803/) (2017)
- [Dynamic Graph Convolutional Networks](https://mlsanity.com/paper/1704.06199/) (2017)
- [A survey of sparse representation: algorithms and applications](https://mlsanity.com/paper/1602.07017/) (2016)
- [Network Lasso: Clustering and Optimization in Large Graphs](https://mlsanity.com/paper/1507.00280/) (2015)
- [Low-Rank Matrix Completion: A Contemporary Survey](https://mlsanity.com/paper/1907.11705/) (2019)
- [Dynamic Graph Collaborative Filtering](https://mlsanity.com/paper/2101.02844/) (2021)
- [Matrix Completion on Graphs](https://mlsanity.com/paper/1408.1717/) (2014)
- [Sampling and Recovery of Graph Signals](https://mlsanity.com/paper/1712.09310/) (2017)
- [A Review of Network Traffic Analysis and Prediction Techniques](https://mlsanity.com/paper/1507.05722/) (2015)
- [Spectral Algorithms for Temporal Graph Cuts](https://mlsanity.com/paper/1702.04746/) (2017)
- [A Distance Measure for the Analysis of Polar Opinion Dynamics in Social Networks](https://mlsanity.com/paper/1510.05058/) (2015)
- [Finding GEMS: Multi-Scale Dictionaries for High-Dimensional Graph Signals](https://mlsanity.com/paper/1806.05356/) (2018)
- [DSL: Discriminative Subgraph Learning via Sparse Self-Representation](https://mlsanity.com/paper/1904.00791/) (2019)

## Built on by (most cited first, 8 of 8)

- [EasyDGL: Encode, Train and Interpret for Continuous-time Dynamic Graph Learning](https://mlsanity.com/paper/2303.12341/) (2023)
- [Time-Vertex Machine Learning for Optimal Sensor Placement in Temporal Graph Signals: Applications in Structural Health Monitoring](https://mlsanity.com/paper/2512.19309/) (2025)
- [Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution](https://mlsanity.com/paper/2302.03933/) (2023)
- [Multi-Dictionary Tensor Decomposition](https://mlsanity.com/paper/2309.09717/) (2023)
- [Low Rank Multi-Dictionary Selection at Scale](https://mlsanity.com/paper/2406.06960/) (2024)
- [Unsupervised Instance and Subnetwork Selection for Network Data](https://mlsanity.com/paper/2212.12771/) (2022)
- [Functional-Edged Network Modeling](https://mlsanity.com/paper/2404.00218/) (2024)
- [Multi-Dictionary Learning for Low Rank Sparse Coding](https://mlsanity.com/paper/2509.10033/) (2025)

## Abstract (arXiv)

Temporal graph signals are multivariate time series with individual components associated with nodes of a fixed graph structure. Data of this kind arises in many domains including activity of social network users, sensor network readings over time, and time course gene expression within the interaction network of a model organism. Traditional matrix decomposition methods applied to such data fall short of exploiting structural regularities encoded in the underlying graph and also in the temporal patterns of the signal. How can we take into account such structure to obtain a succinct and interpretable representation of temporal graph signals? We propose a general, dictionary-based framework for temporal graph signal decomposition (TGSD). The key idea is to learn a low-rank, joint encoding of the data via a combination of graph and time dictionaries. We propose a highly scalable decomposition algorithm for both complete and incomplete data, and demonstrate its advantage for matrix decomposition, imputation of missing values, temporal interpolation, clustering, period estimation, and rank estimation in synthetic and real-world data ranging from traffic patterns to social media activity. Our framework achieves 28% reduction in RMSE compared to baselines for temporal interpolation when as many as 75% of the observations are missing. It scales best among baselines taking under 20 seconds on 3.5 million data points and produces the most parsimonious models. To the best of our knowledge, TGSD is the first framework to jointly model graph signals by temporal and graph dictionaries.