Lune

KDD2021Top-tier venue

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.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers2

  1. Low Rank Multi-Dictionary Selection at ScaleBoya Ma, Maxwell McNeil, Abram Magner, Petko BogdanovKDD 2024 · 1 citation
  2. Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form SolutionChao Chen, Haoyu Geng, Gang Zeng, Zhaobing Han et al.ICLR 2023

Related papers

  1. Graph-Guided Network for Irregularly Sampled Multivariate Time SeriesXiang Zhang, Marko Zeman, Theodoros Tsiligkaridis, Marinka ZitnikICLR 2022 · 166 citations
  2. 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
  3. Efficient Graph Embedding Generation and Update for Large-Scale Temporal GraphYifan Song, Xiaolong Chen, Wenqing Lin, Jia Li et al.VLDB 2025 · 2 citations
  4. TeMP: Temporal Message Passing for Temporal Knowledge Graph CompletionJiapeng Wu, Meng Cao, Jackie Chi Kit Cheung, William L. HamiltonEMNLP 2020 · 137 citations
  5. Towards Dynamic Spatial-Temporal Graph Learning: A Decoupled PerspectiveBinwu Wang, Pengkun Wang, Yudong Zhang, Xu Wang et al.AAAI 2024 · 34 citations
Dusk over the sea between two cliffs drawn in fine vertical lines