Temporal Graph Signal Decomposition
arXiv:2106.13517 · doi:10.1145/3447548.3467379
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.
arXiv comment9 Main Pages 2 Supplement to be published in the research track in Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 2021), August 14 through August 18, 2021,Virtual Event, Singapore
References in corpus (15)
- Semi-Supervised Classification with Graph Convolutional Networks
- The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
- The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-Rank Matrices
- A survey of sparse representation: algorithms and applications
- Dynamic Graph Convolutional Networks
- Learning graphs from data: A signal representation perspective
- BRITS: Bidirectional Recurrent Imputation for Time Series
- Network Lasso: Clustering and Optimization in Large Graphs
- Geometric Matrix Completion with Recurrent Multi-Graph Neural Networks
- Matrix Completion on Graphs
- A Review of Network Traffic Analysis and Prediction Techniques
- Finding GEMS: Multi-Scale Dictionaries for High-Dimensional Graph Signals
- A Distance Measure for the Analysis of Polar Opinion Dynamics in Social Networks
- Dynamic Graph Collaborative Filtering
- DSL: Discriminative Subgraph Learning via Sparse Self-Representation