Time-varying Signals Recovery via Graph Neural Networks
The recovery of time-varying graph signals is a fundamental problem with
numerous applications in sensor networks and forecasting in time series.
Effectively capturing the spatio-temporal information in these signals is
essential for the downstream tasks. Previous studies have used the smoothness
of the temporal differences of such graph signals as an initial assumption.
Nevertheless, this smoothness assumption could result in a degradation of
performance in the corresponding application when the prior does not hold. In
this work, we relax the requirement of this hypothesis by including a learning
module. We propose a Time Graph Neural Network (TimeGNN) for the recovery of
time-varying graph signals. Our algorithm uses an encoder-decoder architecture
with a specialized loss composed of a mean squared error function and a Sobolev
smoothness operator.TimeGNN shows competitive performance against previous
methods in real datasets.
Jhon A. Castro-Correa, Jhony H. Giraldo, Anindya Mondal, Mohsen Badiey, Thierry Bouwmans, Fragkiskos D. Malliaros
# Time-varying Signals Recovery via Graph Neural Networks

###### Abstract

The recovery of time-varying graph signals is a fundamental problem with numerous applications in sensor networks and forecasting in time series. Effectively capturing the spatio-temporal information in these signals is essential for the downstream tasks. Previous studies have used the smoothness of the temporal differences of such graph signals as an initial assumption. Nevertheless, this smoothness assumption could result in a degradation of performance in the corresponding application when the prior does not hold. In this work, we relax the requirement of this hypothesis by including a learning module. We propose a Time Graph Neural Network (TimeGNN) for the recovery of time-varying graph signals. Our algorithm uses an encoder-decoder architecture with a specialized loss composed of a mean squared error function and a Sobolev smoothness operator.TimeGNN shows competitive performance against previous methods in real datasets.

Graph neural networks graph signal processing time-varying graph signal recovery of signals

## 1 Introduction

Recent advances in information technology have led to an accumulation of large amounts of unstructured data. The representation and analysis of such irregular and complex data is a daunting task. Graph Signal Processing (GSP) and Graph Neural Networks (GNNs) are emerging research fields that have proved to be helpful for such tasks in recent years (Ortega et al. (2018), Defferrard et al. (2016), Kipf and Welling (2017), Ioannidis et al. (2019), Gama et al. (2019), Duval and Malliaros (2022)). In GSP and GNNs, the data is modeled as signals or vectors on a set of nodes of a graph, incorporating both the feature information and the underlying structure of the data. GSP and GNNs thus provide new perspectives on data handling, connecting machine learning and signal processing (Bronstein et al. (2017)), with profound impact in various fields like semi-supervised learning (Kipf and Welling (2017)), computer vision (Giraldo et al. (2022), Mondal et al. (2021)), and social media (Benamira et al. (2019)).

The sampling and reconstruction of graph signals are fundamental tasks that have recently attracted considerable attention from the signal processing and machine learning communities (Ortega et al. (2018), Marques et al. (2015), Romero et al. (2016), Ramirez et al. (2017), Parada-Mayorga et al. (2019), Guler et al. (2019), Girault et al. (2020), Hara et al. (2021), Giraldo et al. (2022)). Nevertheless, the problem of time-varying graph signal reconstruction1 has not been widely explored (Giraldo et al. (2022)). The reconstruction of time-varying graph signals has significant applications in data recovery in sensor networks, forecasting of time-series, and infectious disease prediction (Giraldo et al. (2022),
Girault (2015); Giraldo and Bouwmans (2020); Chen and Eldar (2021); Mondal et al. (2022)). Previous studies have extended the definition of smooth signals from static to time-varying graph signals (Qiu et al. (2017)). Similarly, other works have focused on the rate of convergence of the optimization methods used to solve the reconstruction problem (Giraldo et al. (2022); Giraldo and Bouwmans (2020)). However, the success of these optimization-based methods requires appropriate prior assumptions about the underlying time-varying graph signals, which could be inflexible for real-world applications.

In this work, we propose the Time Graph Neural Network (TimeGNN) model to recover time-varying graph signals. TimeGNN encodes the time series of each node in latent vectors. Therefore, these embedded representations are decoded to recover the original time-varying graph signal. Our architecture comprises: 1) a cascade of Chebyshev graph convolutions (Defferrard et al. (2016)) with increasing order and 2) linear combination layers. Our algorithm considers spatio-temporal information using: 1) graph convolutions (Defferrard et al. (2016)) and 2) a specialized loss function composed of a Mean Squared Error (MSE) term and a Sobolev smoothness operator (Giraldo et al. (2022)). TimeGNN shows competitive performance against previous methods in real-world datasets of time-varying graph signals.

The main contributions of our work are summarized as follows: 1) we exploit GNNs to recover time-varying graph signals from their samples, 2) we relax the strict prior assumption of previous methods by including some learnable modules in TimeGNN, and 3) we perform experimental evaluations on natural and artificial data, and compare TimeGNN to four methods of the literature. The rest of the paper is organized as follows. Section 2 introduces the proposed TimeGNN model. Section 3 presents the experimental framework and results. Finally, Section 4 shows the conclusions.

## 2 Time Graph Neural Network

### Preliminaries

We represent a graph with \(G=(\mathcal{V},\mathcal{E},\mathbf{A})\), where \(\mathcal{V}\) is the set of nodes with \(|\mathcal{V}|=N\), \(\mathcal{E}\subseteq\{(i,j)\mid i,j\in\mathcal{V}\text{ and }i\neq j\}\) is the set of edges, and \(\mathbf{A}\in\mathbb{R}^{N\times N}\) is the weighted adjacency matrix with \(\mathbf{A}(i,j)=a_{i,j}\in\mathbb{R}_{+}\) if \((i,j)\in\mathcal{E}\) and 0 otherwise. In this work, we consider connected, undirected, and weighted graphs. We also define the symmetrized Laplacian as \(\mathbf{L}=\mathbf{I}-\mathbf{D}^{-\frac{1}{2}}\mathbf{A}\mathbf{D}^{-\frac{1} {2}}\), where \(\mathbf{D}=\text{diag}(\mathbf{A}\mathbf{1})\) is the diagonal degree matrix of the graph. Finally, a node-indexed real-valued graph signal is a function \(x:\mathcal{V}\rightarrow\mathbb{R}\), so that we can represent a one-dimensional graph signal as \(\mathbf{x}\in\mathbb{R}^{N}\).

### Reconstruction of Time-varying Graph Signals

The sampling and recovery of graph signals are crucial tasks in GSP (Marques et al. (2015); Romero et al. (2016)). Several studies have used the smoothness assumption to address the sampling and recovery problems for static graph signals. The notion of global smoothness was formalized using the _discrete \(p\)-Dirichlet form_(Shuman et al. (2013)) given by:

\[S_{p}(\mathbf{x})=\frac{1}{p}\sum_{i\in\mathcal{V}}\left[\sum_{j\in\mathcal{ V}_{i}}\mathbf{A}(i,j)[\mathbf{x}(j)-\mathbf{x}(i)]^{2}\right]^{\frac{p}{2}}, \tag{1}\]

where \(\mathcal{N}_{i}\) is the set of neighbors of node \(i\). When \(p=2\), we have \(S_{2}(\mathbf{x})\) which is known as the graph Laplacian quadratic form \(S_{2}(\mathbf{x})=\sum_{(i,j)\in\mathcal{E}}\mathbf{A}(i,j)[\mathbf{x}(j)- \mathbf{x}(i)]^{2}=\mathbf{x}^{\mathsf{T}}\mathbf{L}\mathbf{x}\)(Shuman et al. (2013)).

For time-varying graph signals, some studies assumed that the temporal differences of time-varying graph signals are smooth (Giraldo et al. (2022); Qiu et al. (2017)). Let \(\mathbf{X}=[\mathbf{x}_{1},\mathbf{x}_{2},\ldots,\mathbf{x}_{M}]\) be a time-varying graph signal, where \(\mathbf{x}_{s}\in\mathbb{R}^{N}\) is a graph signal in \(G\) at time \(s\). Qiu _et al._(Qiu et al. (2017) defined the smoothness of \(\mathbf{X}\) as:

\[S_{2}(\mathbf{X})=\sum_{s=1}^{M}\mathbf{x}_{s}^{\mathsf{T}}\mathbf{L} \mathbf{x}_{s}=\text{tr}(\mathbf{X}^{\mathsf{T}}\mathbf{L}\mathbf{X}). \tag{2}\]

\(S_{2}(\mathbf{X})\) only computes the summation of the individual smoothness of each graph signal \(\mathbf{x}_{s}\)\(\forall\)\(s\in\{1,2,\ldots,M\}\), so we do not consider any temporal information. To address this problem, we can define the temporal difference operator \(\mathbf{D}_{h}\) as follows (Qiu et al. (2017)):

\[\mathbf{D}_{h}=\begin{bmatrix}-1&&\\ 1&-1&&\\ &1&\ddots&\\ &&\ddots&-1\\ &&&1\end{bmatrix}\in\mathbb{R}^{M\times(M-1)}. \tag{3}\]
Therefore, we have that \(\mathbf{X}\mathbf{D}_{h}=[\mathbf{x}_{2}-\mathbf{x}_{1},\mathbf{x}_{3}-\mathbf{x}_{ 2},\ldots,\mathbf{x}_{M}-\mathbf{x}_{M-1}]\). Some studies (Giraldo et al. (2022b); Qiu et al. (2017) have found that \(S_{2}(\mathbf{X}\mathbf{D}_{h})\) shows better smoothness properties than \(S_{2}(\mathbf{X})\) in real-world time-varying data, _i.e._, \(\mathbf{x}_{s}-\mathbf{x}_{k-1}\) exhibits smoothness in the graph even if \(\mathbf{x}_{s}\) is not smooth across the graph. Qiu et al. (Qiu et al. (2017) used \(S_{2}(\mathbf{X}\mathbf{D}_{h})\) to present a Time-varying Graph Signal Reconstruction (TGSR) method as follows:

\[\min_{\tilde{\mathbf{X}}}\frac{1}{2}\|\mathbf{J}\circ\tilde{\mathbf{X}}- \mathbf{Y}\|_{F}^{2}+\frac{\upsilon}{2}\operatorname{tr}\left((\tilde{\mathbf{ X}}\mathbf{D}_{h})^{T}\mathbf{L}\tilde{\mathbf{X}}\mathbf{D}_{h}\right), \tag{4}\]

where \(\mathbf{J}\in\{0,1\}^{N\times M}\) is a sampling matrix, \(\circ\) is the Hadamard product between matrices, \(\upsilon\) is a regularization parameter, and \(\mathbf{Y}\in\mathbb{R}^{N\times M}\) is the matrix of observed values. The optimization problem in (4) has some limitations: 1) the solution of (4) could lose performance if the real-world dataset does not satisfy the smoothness prior assumption, and 2) (4) is solved with a conjugate gradient method in (Qiu et al. (2017)), which has a slow convergence rate because \(S_{2}(\tilde{\mathbf{X}}\mathbf{D}_{h})\) is ill-conditioned (Giraldo et al. (2022b)). Our algorithm relaxes the smoothness assumption by introducing a learnable module. Similarly, TimeGNN is fast once the GNN parameters are learned.

### Graph Neural Network Architecture

TimeGNN is based on the Chebyshev spectral graph convolutional operator defined by Defferrard et al. (Defferrard et al. (2016), whose propagation rule is given as follows:

\[\mathbf{X}^{\prime}=\sum_{k=1}^{K}\mathbf{Z}^{(k)}\mathbf{W}^{(k)}, \tag{5}\]

where \(\mathbf{W}^{(k)}\) is the \(k\)th matrix of trainable parameters, \(\mathbf{Z}^{(k)}\) is computed recursively as \(\mathbf{Z}^{(1)}=\mathbf{X}\), \(\mathbf{Z}^{(2)}=\hat{\mathbf{L}}\mathbf{X}\), \(\mathbf{Z}^{(k)}=2\hat{\mathbf{L}}\mathbf{Z}^{(k-1)}-\mathbf{Z}^{(k-2)}\), and \(\hat{\mathbf{L}}=\frac{2\mathbf{L}}{\alpha_{\text{max}}}-\mathbf{I}\). We use the filtering operation in (5) to propose a new convolutional layer composed of: 1) a cascade of Chebyshev graph filters, and 2) a linear combination layer as in Fig. 1. More precisely, we define the propagation rule of each layer of TimeGNN as follows:

\[\mathbf{H}^{(l+1)}=\sum_{\rho=1}^{\alpha}\mathbf{\mu}_{\rho}^{(l)}\sum_{k=1}^{ \rho}\mathbf{Z}^{(k)}\mathbf{W}_{l,\rho}^{(k)}, \tag{6}\]

where \(\mathbf{H}^{(l+1)}\) is the output of layer \(l+1\), \(\alpha\) is a hyperparameter, \(\mathbf{\mu}_{\rho}^{(l)}\) is a learnable parameter, \(\mathbf{Z}^{(k)}\) is recursively computed as in (5), and \(\mathbf{W}_{l,\rho}^{(k)}\) is the \(k\)th learnable matrix in the layer \(l\) for the branch \(\rho\). The architecture of TimeGNN is

Figure 1: Cascade of Chebyshev graph convolutions.

Figure 2: Pipeline of our Time Graph Neural Network (TimeGNN) for the recovery of time-varying graph signals.
given by stacking \(n\) cascade layers as in (6), where the input is \((\mathbf{J}\circ\mathbf{X})\mathbf{D}_{h}\). Finally, our loss function is such that:

\[\mathcal{L} =\frac{1}{|\mathcal{S}|}\sum_{(i,j)\in\mathcal{S}}(\mathbf{X}(i,j)- \mathbf{\hat{X}}(i,j))^{2}\] \[\quad+\lambda\text{ tr}\big{(}(\mathbf{\hat{X}}\mathbf{D}_{h})^{ \mathsf{T}}(\mathbf{L}+\epsilon\mathbf{I})\mathbf{\hat{X}}\mathbf{D}_{h}\big{)}, \tag{7}\]

where \(\mathbf{\hat{X}}\) is the reconstructed graph signal, \(\mathcal{S}\) is the training set, with \(\mathcal{S}\) a subset of the spatio-temporal sampled indexes given by \(\mathbf{J}\), and \(\epsilon\in\mathbb{R}^{+}\) is a hyperparameter. The term \(\text{tr}\big{(}(\mathbf{\hat{X}}\mathbf{D}_{h})^{\mathsf{T}}(\mathbf{L}+ \epsilon\mathbf{I})\mathbf{\hat{X}}\mathbf{D}_{h}\big{)}\) is the Sobolev smoothness (Giraldo et al. (2022b)).

We can think of TimeGNN as an encoder-decoder network with a loss function given by an MSE term plus a Sobolev smoothness regularization. The first layers of TimeGNN encode the term \((\mathbf{J}\circ\mathbf{X})\mathbf{D}_{h}\) to an \(H\)-dimensional latent vector that is then decoded with the final layer. As a result, we capture the spatio-temporal information using the GNN, the temporal encoding-decoding structure, and the regularization term \(\text{tr}\left((\mathbf{\hat{X}}\mathbf{D}_{h})^{\mathsf{T}}(\mathbf{L}+ \epsilon\mathbf{I})\mathbf{\hat{X}}\mathbf{D}_{h}\right)\) where we use the temporal operator \(\mathbf{D}_{h}\). The parameter \(\lambda\) in (7) weighs the importance of the regularization term against the MSE loss. Figure 2 shows the pipeline of our TimeGNN applied to a graph of the sea surface temperature in the Pacific Ocean.

## 3 Experiments and Results

We compare TimeGNN with Graph Convolutional Networks (GCN) (Kipf and Welling (2017)), Natural Neighbor Interpolation (NNI) (Kiani and Saleem (2017)), TGSR (Qiu et al. (2017)), and Time-varying Graph signal Reconstruction via Sobolev Smoothness (GraphTRSS) (Giraldo et al. (2022b)).

### Implementation Details

We implement TimeGNN and GCN using PyTorch and PyG (Fey and Lenssen (2019). We define the space search for the hyperparameters tuning of TimeGNN as follows: 1) number of layers \(\{1,2,3\}\), 2) hidden units \(\{2,3,\ldots,10\}\), 3) learning rate \([0.005,0.05]\), 4) weight decay \([1e-5,1e-3]\), 5) \(\lambda\in[1e-6,1e-3]\), 6) \(\alpha\in\{2,3,4\}\). Similarly, we set the following hyperparameters: 1) \(\epsilon=0.05\), and 2) the number of epochs to \(5,000\). The graphs are constructed based on the coordinate locations of the nodes in each dataset with a \(k\)-Nearest Neighbors (\(k\)-NN) algorithm as in (Giraldo et al. (2022b)). NNI, TGRS, and GraphTRSS are implemented using the code in (Giraldo et al. (2022b)) in MATLAB(r) 2022b. The hyperparameters of the baseline methods are optimized following the same strategy as with TimeGNN.

### Datasets

**Synthetic Graph and Signals:** We use the synthetic graph dataset developed in (Qiu et al. (2017). The graph contains 100 nodes randomly generated from a uniform distribution in a \(100\times 100\) square area using \(k\)-NN. The graph signals

\begin{table}
\begin{tabular}{l|c c c c|c c c|c c c|c c c} \hline \hline Method & \multicolumn{2}{c|}{Synthetic Graph Signals} & \multicolumn{2}{c|}{PM2.5 Concentration} & \multicolumn{2}{c|}{Sea-surface Temperature} & \multicolumn{2}{c}{Intel Lab Data} \\  & RMSE & MAE & MAPE & RMSE & MAE & MAPE & RMSE & MAE & MAPE & RMSE & MAE & MAPE & RMSE & MAE & MAPE \\ \hline GCN (Kipf and Welling (2017)) & 11.296 & 8.446 & 1.123 & 4.657 & 2.959 & 0.550 & 3.766 & 2.922 & 0.548 & 2.998 & 2.327 & 0.120 \\ NNI (Kiani et al. (Kiani and Saleem 2017)) & 0.775 & 0.436 & 0.255 & 4.944 & 2.956 & 0.593 & 0.772 & 0.561 & 0.067 & 0.661 & 0.291 & 0.015 \\ GraphTRSS (Giraldo et al. (Giraldo et al. (2022b))) & **0.260** & **0.256** & **0.178** & **3.824** & **2.264** & **0.377** & **0.357** & **0.260** & **0.022** & **0.056** & **0.023** & **0.001** \\ TGSR (Qiu et al. (Qiu et al. (2017))) & **0.263** & **0.193** & **0.144** & 3.898 & 2.279 & 0.394 & 0.360 & 0.263 & 0.030 & _0.069_ & _0.037_ & _0.002_ \\ \hline TimeGNN (ours) & 0.452 & 0.323 & 0.226 & **3.809** & **2.172** & **0.362** & **0.275** & **0.203** & **0.023** & 0.156 & 0.095 & 0.005 \\ \hline \hline \end{tabular}

* The best and second-best performing methods on each dataset are shown in **red** and **blue**, respectively.

\end{table}
Table 1: Quantitative comparison of TimeGNN with the baselines in all datasets using the average error metrics.

Figure 3: Comparison of TimeGNN to baseline methods in one synthetic and three real-world datasets (RMSE).
are generated with the recursive function \(\mathbf{x}_{t}=\mathbf{x}_{t-1}+\mathbf{L}^{-1/2}\mathbf{f}_{t}\), where \(\mathbf{x}_{1}\) is a low frequency graph signal with energy \(10^{4}\), \(\mathbf{L}^{-1/2}=\mathbf{U}\lambda^{-1/2}\mathbf{U}^{\top}\), where \(\mathbf{U}\) is the matrix of eigenvectors, \(\lambda=\operatorname{diag}(\lambda_{1},\lambda_{2},\ldots,\lambda_{N})\) is the matrix of eigenvalues, \(\lambda^{-1/2}=\operatorname{diag}(0,\lambda_{2}^{-1/2},\ldots,\lambda_{N}^{- 1/2})\), and \(\mathbf{f}_{t}\) is an i.i.d. Gaussian signal.

**PM 2.5 Concentration:** We use the daily mean concentration of PM 2.5 in the air in California, USA4. Data were collected from 93 sensors over 220 days in 2015.

Footnote 4: [https://www.epa.gov/outdoor-air-quality-data](https://www.epa.gov/outdoor-air-quality-data)

**Sea-surface Temperature:** We use the sea-surface temperature data, which are measured monthly and released by the NOAA PSL5. We use a sample of 100 locations in the Pacific Ocean over a duration of 600 months.

Footnote 5: [https://psl.noaa.gov](https://psl.noaa.gov)

**Intel Lab Data:** We use the data captured by the 54 sensors deployed at the Intel Berkeley Research Laboratory 6. The data consists of temperature readings between February 28th and April 5th, 2004.

Footnote 6: [http://db.csail.mit.edu/labdata/labdata.html](http://db.csail.mit.edu/labdata/labdata.html)

### Evaluation Metrics

We use the Root Mean Square Error (RMSE), Mean Absolute Error (MAE), and Mean Absolute Percentage Error (MAPE) metrics, as defined in (Giraldo et al. (2022b)), to evaluate our algorithm.

### Experiments

We construct the graphs using \(k\)-NN with the coordinate locations of the nodes in each dataset with a Gaussian kernel as in (Giraldo et al. (2022b). We follow a random sampling strategy in all experiments. Therefore, we compute the reconstruction error metrics on the non-sampled vertices for a set of sampling densities. We evaluate all the methods with a Monte Carlo cross-validation with 50 repetitions for each sampling density. For the synthetic data, \(k=5\) in the \(k\)-NN, and the sampling densities are given by \(\{0.1,0.2,\ldots,0.9\}\). For PM2.5 concentration, \(k=5\) and the sampling densities are \(\{0.1,0.15,0.2,\ldots,0.45\}\). For the sea-surface temperature, we keep \(k=5\) and the sampling densities are set to \(\{0.1,0.2,\ldots,0.9\}\). For Intel Lab data, we set \(k=3\) and the sampling densities at \(\{0.1,0.3,0.5,0.7\}\).

### Results and Discussion

Figure 3 shows the performance of TimeGNN against the previous methods for all datasets using RMSE. Furthermore, Table 1 shows the quantitative comparisons using the averages of all metrics along the set of sampling densities. We do not plot the performance of GCN in Fig. 3 because this network performs considerably worse than the other methods, as shown in Table 1. GCN was implemented using the same input and loss function as in TimeGNN. Our algorithm outperforms previous methods for several metrics in PM2.5 concentration and sea-surface temperature datasets. The synthetic data were created to satisfy the conditions of smoothly evolving graph signals (Definition 1 in (Qiu et al. (2017)), while here, we relaxed that prior assumption by adding a trainable GNN module. Therefore, TGRS and GraphTRSS are better suited for that artificial dataset, as shown in Fig. 3 and Table 1. Similarly, the Intel Lab dataset is highly smooth. Some of the reasons behind our model's success in real-world datasets are: 1) its ability to capture spatio-temporal information, 2) its encoding-decoding structure, and 3) its powerful learning module given by a cascade of Chebyshev graph convolutions.

## 4 Conclusions

In this paper, we introduced a GNN architecture named TimeGNN for the recovery of time-varying graph signals from their samples. Similarly, we proposed a new convolutional layer composed of a cascade of Chebyshev graph filters. TimeGNN includes a learning module that relaxes the requirement of strict smoothness assumptions. We found that our framework shows competitive performance against several approaches in the literature for reconstructing graph signals, delivering better performance in real datasets. Our algorithm could help solve problems like recovering missing data from sensor networks, forecasting weather conditions, intelligent transportation systems, and many others.

For future work, we plan to extend our framework to other graph filters like transformers (Yun et al. (2019)), and alternative compact operators as introduced in (Ji and Tay (2019). Similarly, we will explore TimeGNN in highly dynamic 4D real datasets (Badiey et al. (2013), Castro-Correa et al. (2022)).
**Acknowledgments:** This work was supported by DATAIA institute as part of the "Programme d'Investissement d'Avenir", (ANR-17-CONV-0003) operated by CentraleSupelec, by ANR (French National Research Agency) under the JCJC project GraphIA (ANR-20-CE23-0009-01), and by the Office of Naval Research, ONR (Grant No. N00014-21-1-2760).
