Temporal Graph Signal Decomposition
Maxwell J. McNeil, Lin Zhang, Petko Bogdanov
Abstract
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.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
2 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
Cited by top-tier papers2
Related papers
- Graph-Guided Network for Irregularly Sampled Multivariate Time SeriesXiang Zhang, Marko Zeman, Theodoros Tsiligkaridis, Marinka ZitnikICLR 2022 · 166 citations
- TIME-FS: Joint Learning of Tensorial Incomplete Multi-View Unsupervised Feature Selection and Missing-View ImputationYanyong Huang, Minghui Lu, Wei Huang, Xiuwen Yi et al.AAAI 2025 · 22 citations
- Efficient Graph Embedding Generation and Update for Large-Scale Temporal GraphYifan Song, Xiaolong Chen, Wenqing Lin, Jia Li et al.VLDB 2025 · 2 citations
- TeMP: Temporal Message Passing for Temporal Knowledge Graph CompletionJiapeng Wu, Meng Cao, Jackie Chi Kit Cheung, William L. HamiltonEMNLP 2020 · 137 citations
- Towards Dynamic Spatial-Temporal Graph Learning: A Decoupled PerspectiveBinwu Wang, Pengkun Wang, Yudong Zhang, Xu Wang et al.AAAI 2024 · 34 citations
