Source-linked AI summary
Unrolled Time-Varying Graph Signal Restoration under Spatiotemporal Smoothness Priors
Hayate Kojima, Hikari Noguchi, Koki Yamada, Yuichi Tanaka
TL;DR
Noisy, incomplete time-varying graph signals require restoration that accounts for both spatial structure and temporal relationships. GLASS unrolls an optimization method with learned spatiotemporal regularization in batch, online, and unsupervised settings. Supervised batch achieves the lowest RMSEs in almost all cases, while online and unsupervised batch outperform methods in their own settings and are often competitive with existing batch methods.
Problem
Static restoration applied independently over time ignores temporal relationships, while fixed low-order priors may not capture longer-term dependencies.
Source: §I · p. 1, A. Restoration of Static Graph Signals · p. 4, B. Restoration of Time-varying Graph… · p. 4Method
GLASS unrolls an optimization problem combining a Sobolev spatial operator and multi-tap FIR temporal filter, learning their parameters for supervised batch, supervised online, and unsupervised batch restoration.
Source: §I · p. 2, §VI · pp. 9, 12Results
The supervised batch method achieves the lowest RMSEs in almost all cases; supervised online and unsupervised batch outperform existing methods in their own settings and are often competitive with existing batch methods.
Source: §I · p. 2, §VI · p. 12Takeaways & Limitations
The spatiotemporal regularizer is effective across the three settings, including online restoration and unsupervised restoration without target ground truth.
Source: D. Restoration Results · p. 9
Abstract
from arXiv · showhide
In this paper, we propose restoration methods for time-varying graph signals using deep algorithm unrolling (DAU). Time-varying graph signals, such as signals obtained from sensor networks, are nonuniformly distributed in space and observed as time series. Since these observed signals often contain noise and missing values, their restoration needs to consider both spatial and temporal relationships. Our approach is based on an optimization problem that models signal properties using a spatiotemporal regularizer that combines a Sobolev operator for spatial smoothness and a multi-tap FIR filter for temporal smoothness. We then unroll the iterative conjugate gradient method to solve this problem and learn the regularization parameters and filter coefficients in each iteration. Our method can be applied to supervised batch, supervised online, and unsupervised batch settings to learn these parameters. Experiments on several synthetic and real-world datasets show that the supervised batch method achieves the lowest RMSEs in almost all cases. The supervised online and the unsupervised batch methods outperform the existing methods of their own settings, and are often competitive with the existing batch methods.
I. INTRODUCTION
Time-varying graph restoration must account for irregular spatial structure and temporal dependencies, yet existing priors and methods leave long-term temporal structure difficult to learn interpretably. GLASS uses deep algorithm unrolling to learn spatiotemporal regularization across three training settings, with results favoring supervised batch restoration.
I. INTRODUCTION
- Sensors in applications such as wireless networks, traffic monitoring, and environmental sensing are irregularly distributed, limiting classical methods designed for regular, equispaced domains.Hybrid methods combine model-based optimization with data-driven components; DAU learns iterative-algorithm parameters from training data.Source: §I · pp. 1–2
- Static restoration methods applied independently at each time step ignore temporal dependencies, which may degrade restoration quality.This motivates methods that jointly exploit graph structure and temporal dynamics.Source: §I · p. 1
- Existing time-varying restoration often uses fixed, simple temporal priors that may miss long-term dependencies, while learning temporal structure interpretably remains an open challenge.Model-based methods also rely on handcrafted priors and hyperparameter tuning; data-driven methods can require large datasets and offer limited interpretability.Source: §I · p. 2
- GLASS combines a Sobolev operator for spatial smoothness with a multi-tap FIR filter for temporal smoothness, learning regularization parameters and filter coefficients from data.The framework is based on an optimization problem solved through deep algorithm unrolling.Source: §I · p. 2
- The three settings are supervised batch, supervised online, and unsupervised batch restoration.Batch methods process all T time steps; online restoration uses the current observation and L previously restored signals; unsupervised batch learns from the target observation alone.Source: §I · p. 2
- The supervised batch method achieves the lowest RMSEs in almost all cases; online and unsupervised batch outperform methods in their own settings and are often competitive with batch methods.Experiments span synthetic and real-world datasets.Source: §I · p. 2
II. BASIS OF GRAPH SIGNAL PROCESSING
Graph signal processing represents data on graph nodes and quantifies spatial smoothness through graph structure. A time-varying graph signal stacks these node signals across consecutive time instances.
A. Time-varying Graph Signals
- The paper models the graph as weighted and undirected, with nodes V, edges E, and a weighted adjacency matrix W.An edge weight is positive for connected nodes and zero otherwise; the graph Laplacian is formed from W and the degree matrix.Source: A. Time-varying Graph Signals · p. 3
- A graph signal assigns a value to each graph node, and its smoothness is quantified by the Laplacian quadratic form.Smaller S2(x) indicates slower variation across the graph and therefore a smoother signal.Source: A. Time-varying Graph Signals · p. 3
- A time-varying graph signal stacks graph signals at T consecutive time instances as the columns of X.Each column x_t is the graph signal at time t.Source: A. Time-varying Graph Signals · p. 3
III. RELATED WORK
Static graph restoration uses spatial-smoothness priors in an optimization objective, but applying static methods independently over time leaves temporal relationships unused. The section introduces these foundations and their limitation for time-varying signals.
A. Restoration of Static Graph Signals
- Static restoration methods require the observed-node locations to be known, represented by a measurement vector marking observed entries.The observation model includes an unknown original signal and noise; the measurement indicator is 1 for observed nodes and 0 otherwise.Source: A. Restoration of Static Graph Signals · p. 3
- Tikhonov regularization restores a static graph signal by minimizing an objective that balances data fidelity with a spatial-smoothness penalty.The regularization operator is commonly a graph high-pass filter; Laplacian regularization is a special case.Source: A. Restoration of Static Graph Signals · pp. 3–4
- Applying static methods independently at each time step cannot exploit relationships between consecutive signals and may degrade restoration performance.This is the motivation for methods that jointly use spatial graph structure and temporal dynamics.Source: A. Restoration of Static Graph Signals · p. 4
B. Restoration of Time-varying Graph Signals
Time-varying graph restoration combines spatial and temporal smoothness priors, but earlier formulations use low-order operators and a fixed two-tap temporal difference. A Sobolev operator can reshape the spatial response, while the temporal filter in that formulation remains fixed.
B. Restoration of Time-varying Graph Signals
- The observation model represents the time-varying signal as Y = [y0, . . . , yT−1], with a measurement matrix J assumed known beforehand.J indicates which signal values are observed, and the observation model includes noise and an unknown original signal.Source: B. Restoration of Time-varying Graph… · p. 4
- The spatiotemporal regularizer applies a graph Laplacian quadratic form to consecutive-frame differences, penalizing signals that are non-smooth in both spatial and temporal domains.Its Laplacian captures one-hop spatial relationships, while the fixed two-tap filter captures only differences between consecutive time instances.Source: B. Restoration of Time-varying Graph… · p. 4
- A Sobolev operator replaces the Laplacian in the spatial term, reshaping its spectral response through ϵ and β while retaining the temporal two-tap difference.A larger β penalizes high graph frequencies more strongly; β = 0 penalizes all graph frequencies equally.Source: B. Restoration of Time-varying Graph… · p. 4
IV. GLASS
GLASS restores time-varying graph signals by unrolling an iterative solver for a spatiotemporal smoothness objective. Its baseline uses a Sobolev operator and a causal multi-tap FIR filter.
IV. GLASS
- GLASS presents the baseline method alongside a proposed unrolled network, with its three settings sharing that network but differing in input, output, and loss.The online setting uses a window of past restored frames and the current observation, then takes the network's last output column as the restored frame.Source: §IV · p. 4, Figure 2 · p. 5
A. Baseline Problem
- GLASS formulates restoration with data fidelity and a spatiotemporal smoothness term applying a Sobolev operator to a temporally filtered signal.The filter replaces the fixed two-tap difference with an (L + 1)-tap filter, measuring smoothness across multiple past frames; L = 1 recovers the earlier formulation.Source: A. Baseline Problem · p. 5
- Conjugate gradient can solve the baseline objective iteratively, producing the restored signal when α, ϵ, β, and the FIR filter are fixed.The objective's parameters must be fitted to data characteristics, noise level, and missing ratio, but their appropriate values are difficult to determine in advance.Source: A. Baseline Problem · p. 5
B. Proposed Restoration with DAU
GLASS replaces difficult-to-select restoration parameters with trainable parameters in an unrolled conjugate-gradient network. It supports supervised batch and online restoration settings.
B. Proposed Restoration with DAU
- The restoration quality depends on α, ϵ, β, and the FIR filter, whose suitable values are difficult to determine in advance for differing data characteristics, noise, and missing ratios.Source: B. Proposed Restoration with DAU · p. 5
- GLASS unrolls conjugate-gradient iterations into network layers and trains layer-specific regularization parameters and FIR coefficients to produce the restored signal.The network takes the observed signal, measurement matrix, and graph Laplacian; each layer performs one CG iteration.Source: B. Proposed Restoration with DAU · pp. 5–6
C. Supervised Restoration
- The supervised batch method reconstructs the full observed signal at once, whereas the supervised online method uses the current observation and previously restored frames.Source: C. Supervised Restoration · p. 6
1) Supervised Batch Method:
The paper describes supervised batch and causal online training, an unsupervised batch option for target data without ground truth, and differentiability of the unrolled algorithm and losses.
1) Supervised Batch Method:
- The supervised batch method restores the whole observed signal and trains parameters using a dataset with ground-truth outputs and an MSE loss.The loss compares the restoration output with the ground-truth signal.Source: 1) Supervised Batch Method · p. 6
2) Supervised Online Method:
- The supervised online method restores each frame causally from the current observation and L previously restored frames, using the window's last output column.When t < L, unavailable past frames are set to zero and treated as unobserved; the recursion is trained with supervised learning.Source: 2) Supervised Online Method · p. 6
D. Unsupervised Batch Restoration
- Unsupervised batch restoration is designed for target data without ground truth and trains using observed entries only.Its loss compares the restored signal with observations only where entries are observed.Source: D. Unsupervised Batch Restoration · p. 6
E. Differentiability of the Algorithm
- The iterative algorithm and loss are differentiable with respect to trainable parameters, supporting gradient-based training of GLASS.The argument checks differentiability of the parameter-dependent terms and notes that the losses are quadratic in the restored signal.Source: E. Differentiability of the Algorithm · p. 6
V. EXPERIMENTS
The experiments compare the proposed supervised batch, supervised online, and unsupervised batch methods with existing restoration approaches. The comparison spans learning settings and includes model-based, static, and graph-neural-network methods.
V. EXPERIMENTS
- The methods and comparison approaches are evaluated across supervised batch, supervised online, and unsupervised batch settings.The section introduces comparisons with existing methods.Source: §V · p. 6, A. Comparison Methods · p. 7
A. Comparison Methods
- The comparison covers batch methods OGTR, TRSS, and Tikhonov, plus static LR, GCN, and ChebNet.These methods form the batch and static comparison groups.Source: A. Comparison Methods · p. 7
- Online GLASS is compared with OGTR, while unsupervised GLASS is compared with Inpainting DAU.Inpainting DAU learns filters in the spatiotemporal domain.Source: A. Comparison Methods · p. 7
- Model-based methods are tuned by Bayesian optimization; other trained methods use Adam, while unsupervised methods fit parameters to test observations without training data.Batch training uses 100 epochs and online training uses 50; unsupervised methods train on the test observation for 100 epochs.Source: A. Comparison Methods · p. 7
B. Setup
The setup evaluates restoration across sampling ratios under controlled noise and describes how the synthetic graph signals are generated. The synthetic results table reports RMSE across sampling ratios for batch, static, online, and unsupervised methods.
B. Setup
- Observations are simulated by masking noisy ground-truth signals; supervised methods are trained across sampling ratios 0.1–0.9 and noise levels 0.02–0.10.Noise is white Gaussian, scaled by the ground-truth signal standard deviation.Source: B. Setup · p. 7
- Evaluation fixes the noise level at 0.1, varies the sampling ratio, uses L=8 learnable FIR taps, and measures RMSE against the ground truth.The number of taps is selected in Section V-E.Source: B. Setup · p. 7
1) Synthetic Dataset:
- The synthetic graph has 100 randomly placed nodes linked by a 5-nearest-neighbor graph, with edge weights based on inverse squared distance.The weights are normalized by the maximum edge weight.Source: 1) Synthetic Dataset · p. 7
- Synthetic signals use a low-pass-filtered initial graph signal and recursively generated temporal variations; 15 signals are split into 10 training and 5 test examples.The graph filter preserves the lowest 10% of graph frequencies and attenuates the others.Source: 1) Synthetic Dataset · p. 7
- The synthetic results table reports RMSE for varying sampling ratios, with separate batch, static, online, and unsupervised method groups.Bold and underlining identify the best and second-best within each group; colors identify the best and second-best across methods.Source: Table III · p. 8
2) Japan COVID-19 Number of Infected Patient Dataset:
Across the evaluated settings, the batch method is most accurate when the whole signal is available, while the online and unsupervised methods remain effective under their respective constraints. The section also describes the Japan and New York datasets and the accuracy–computation trade-off used to choose the FIR tap count.
2) Japan COVID-19 Number of Infected Patient Dataset:
- The Japan COVID-19 dataset contains daily new infections for 47 prefectures from January 2020 to May 2023, with separate 350-day training and test periods.The graph connects prefectures using a 5-nearest-neighbor construction based on their coordinates.Source: 2) Japan COVID-19 Number of Infected… · p. 8
3) New York Subway Ridership Dataset:
- The New York subway dataset aggregates station ridership into weekday daily counts; experiments use 420 stations and separate 400-day training and test periods.Twelve missing values in those periods are linearly interpolated along time at each station.Source: 3) New York Subway Ridership Dataset · p. 8
E. Selection of Hyperparameter L
- L=1 cannot learn the temporal filter; accuracy drops sharply at L=3 and improves further at low sampling ratios, while L=8 balances accuracy against online computation.Larger L uses more past frames but lengthens the online window and raises computation per frame.Source: Figure 3 · p. 9, E. Selection of Hyperparameter L · p. 9
D. Restoration Results
- GLASS (online) beats OGTR (online) at every sampling ratio on all three datasets and is competitive with several batch methods.It has lower RMSE than OGTR (batch) on the synthetic dataset at every ratio, with further dataset-specific wins over batch baselines.Source: D. Restoration Results · p. 9
- GLASS (unsupervised) has lower RMSE than Inpainting DAU at every sampling ratio on all three datasets and is competitive with batch methods when observations are sparse.At sampling ratio 0.1, it beats TRSS and Tikhonov on the synthetic dataset and TRSS on the New York subway dataset.Source: D. Restoration Results · p. 9
- GLASS (batch) is the most accurate when the whole signal is available; GLASS (online) retains most of that accuracy, and GLASS (unsupervised) stays close without target ground truth.The paper concludes that the spatiotemporal regularizer is effective under the constraints of the three settings.Source: D. Restoration Results · p. 9
F. Discussion of Trained Parameters
GLASS’s learned temporal coefficients and spatial spectral response show both shared and dataset-specific structure. Across the visualized datasets, its three training settings produce accurate restorations, with the supervised batch method achieving the lowest RMSEs in almost all cases.
F. Discussion of Trained Parameters
- GLASS’s FIR coefficients spread weight across past frames in shallow layers, then concentrate on the most recent frame in deeper layers; α also decreases in later layers on both real-world datasets.The temporal coefficients show a similar tendency across the three datasets, while the decreasing α weakens regularization near the network’s end.Source: F. Discussion of Trained Parameters · p. 9, Figure 4 · p. 10
- The learned spatial response exceeds the graph-Laplacian response in most layers, but its largest increase occurs in deeper Japan COVID-19 layers and shallower New York subway layers.This dataset- and depth-dependent pattern contrasts with the similar FIR-coefficient tendency across datasets.Source: F. Discussion of Trained Parameters · p. 9, Figure 4 · p. 10
G. Visualization of Restored Signals
- On the synthetic dataset, GLASS methods keep errors small across the graph; on Japan COVID-19, larger errors occur at prefectures containing large cities, while Inpainting DAU errors are larger across the map.The synthetic visualization reports no GLASS unsupervised node with error above 5, whereas a third of Inpainting DAU nodes exceed 5.Source: G. Visualization of Restored Signals · p. 9, Figure 5 · p. 10, Figure 6 · p. 11
- On the New York subway dataset, errors concentrate at stations with large dynamic ranges, but GLASS keeps errors smaller than existing methods at those stations.The figure visualizes absolute error through node color and size.Source: G. Visualization of Restored Signals · p. 9, Figure 7 · p. 11
VI. CONCLUSION
- The supervised batch method achieves the lowest RMSEs in almost all cases, while online and unsupervised methods outperform their counterparts and often rival batch methods.The restoration figures show representative outputs for the synthetic, Japan COVID-19, and New York subway datasets.Source: Figure 5 · p. 10, Figure 6 · p. 11, Figure 7 · p. 11