Multivariate Time-Series Forecasting with Temporal Polynomial Graph Neural Networks
Authors: Yijing Liu
Qinxian Liu
Jian-Wei Zhang
Haozhe Feng
Zhongwei Wang
Zihan Zhou
Wei Chen
Venue: NeurIPS 2022 Accept (2022)
Keywords: Graph Neural Networks
Multivariate Time-series Forecasting
Spatial-temporal Graph

Abstract: Modeling multivariate time series (MTS) is critical in modern intelligent systems. The accurate forecast of MTS data is still challenging due to the complicated latent variable correlation. Recent works apply the Graph Neural Networks (GNNs) to the task, with the basic idea of representing the correlation as a static graph. However, predicting with a static graph causes significant bias because the correlation is time-varying in the real-world MTS data. Besides, there is no gap analysis between the actual correlation and the learned one in their works to validate the effectiveness. This paper proposes a temporal polynomial graph neural network (TPGNN) for accurate MTS forecasting, which represents the dynamic variable correlation as a temporal matrix polynomial in two steps. First, we capture the overall correlation with a static matrix basis. Then, we use a set of time-varying coefficients and the matrix basis to construct a matrix polynomial for each time step. The constructed result empirically captures the precise dynamic correlation of six synthetic MTS datasets generated by a non-repeating random walk model. Moreover, the theoretical analysis shows that TPGNN can achieve perfect approximation under a commutative condition. We conduct extensive experiments on two traffic datasets with prior structure and four benchmark datasets. The results indicate that TPGNN achieves the state-of-the-art on both short-term and long-term MTS forecastings.

Multivariate Time-Series Forecasting with Temporal Polynomial Graph Neural Networks
Yijing Liu', Qinxian Liu', Haozhe Feng'. Zhongwei Wang!. State Key Lab of CAD&CG, Zhejiang University, Hangzhou, China (3150105531, 22021050, zjw w.w..ce cs. fenghz, wzw09, 12121109, chenvi (ieevvis)zzjueduu cn
Jian-We Wei Zhang'
Zihan Zhou', Wei Chen
Abstract
Modeling multivariate time series (MTS) is critical in modern intelligent systems. The accurate forecast of MTS data is still challenging due to the complicated latent variable correlation. Recent works apply the Graph Neural Networks (GNNs) to the task, with the basic idea of representing the correlation as a static graph. However, predicting with a static graph causes significant bias because the correlation tame-narying in the real-world MTS data. Besides, there is gap analysis between the actual correlation and the learned one in their works to validate the effectiveness. This paper proposes a temporal polynomial graph neural network (TPGNN) for accurate MTS forecasting, which represents the dynamic variable correlation as a temporal matrix polynomial in two steps. First, with a static matrix basis. Then, we use a set of time- evrriig coefficients and the matrix basis construct matrix polynomial for each time step. The constructed result empirically captures the precise dynamic correlation of six synthetic MTS datasets generated by non-repeating random walk model. Moreover, the the- oretical analysis shows that TPGNN can achieve perfect approximation under a commutative condition. We conduct extensive experiments on two traffic datasets with prior structure and four benchmark datasets. The results indicate that TPGNN achieves the state-of-the-ard on both short-term and long-term MTS forecastings.
capture the overall correlation
Introduction
The wide deployment of sensors in modern societies records tremendous time-series data, which boosts the application of energy dispatch, traffic control, etc. Commonly, there are numerous distributed sensors in monitoring system, e.g., the temperature control system of a computing center. Univariate time-series data recorded by these sensors formulate the multivariate time-series (MTS) recent years, as provides essential information for strategy formulation and resource schedule 52)
data. Forecasting over MTS data has been widely studied [ 21 41
One basic premise of modeling the MTS data is that the variables interact with each other, which is fulfilled in most cases. Therefore, capturing the variable correlation essential for MTS forecasting. Previous deep-learning-bass
works like FC-LSTM (36) and TPA-LSTM (34] model the correlation with an implicit recurrent process, which is inefficient in prediction and hard to optimize. The development of graph neural networks (GNNs) [17] brings an innovative way to capture the variable dependence. Recent works 442 regard the MTS data as series of graph signals and process them with GNNs, where the nodes are variables and the edge weight quantifies the dependence. Although GNNs-based methods achieve promising efficiency and accuracy in MTS forecasting,
*Corresponding author.
'Code is available at httpp://githubs http://wwwb.coeeappapane/t/////e
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

(3) Morning correlation
(b) Noon conrelation
(G) Evening conrllation
(d) Ground bush and prediction areor along the timeline
Figure 1: The sensor correlation and model prediction error in 24 hours. In (a)-(c), we apply the Pearson correlation coefficient to derive the sensor correlation of different periods, the results show time-varying patterns. We present the prediction error of three sttic-graph-based models in (d), the errors have steep increases between two periods, we mark them with red rectangles.
there are two notable challenges to the current approaches. 1) The MTS data have no prior variable dependence, which is required for determining the edge weight in graph construction. The existent methods compute the weight according to the physical distance among sensors [23 35 44) or utilize
parameter matrices to learn the weight from MTS data (27 41 42). As result, the edge weights are constant in their methods. However, according to the observations from the real-world dataset, the variable dependence changes with time. Therefore, using static-weight graphs in prediction causes significant bias. Figure iillsttrates the first challenge with traffic dataset (PEMS-D7), demonstrates that the correlation has distinct patterns different periods. Besides, three static- show error increases between two consecutive periods, which is caused by dependence variation. 2) Many researchers point out gap between the actual variable dependence and the constructed correlation [25 42 49), i.e., the edge weight does not accurately describe the variable correlation. Although they propose various methods to bridge the gap, there is no theoreticallempirical analysis of the gap. Therefore, the method's 's effectiveness is still unknown.
traph-based methods [
To address the above two challenges, propose Temporal Polynomial Graph Neural Network (TPGNN), a novel GNNs-based forecasting model for MTS data. TPGNN has an encoder-decoder structure, we encode historical MTS data with novel GNN module and make predictions by decoding the encoded results auto-regressively. The core of TPGNN is a temporal polynomial graph (TPG) module that learns the dynamic variable dependence end-to-end. The main idea is represent the correlation as a time-varying matrix polynomial. Firstly, we define an adjacency matrix basis A to capture the overall dependence for each variable pair. Then, we use a matrix polynomial of A to represent the correlation of each time step. where the coefficients are determined by time. To generate coefficients for MTS data of arbitrary length, we propose to use a set of cyclic timestamp embedding to index the time step. As a result, TPGNN captures the dynamic correlation with temporal matrix polynomial, which solves the first challenge effectively. For the second challenge, analyze the approximation error of the TPG module and provide theoretical bound on the error. Furthermore, we evaluate the existent dependence learning methods on six synthetic MTS datasets with ground-truth variable dependence. The main contributions of the work are follows:
We propose novel dependence learning module capture MTS data's dynamic correlation, which represents the variable dependence temporal matrix polynomial. The resultant model achieves state-of-the-ard forecasting performance on 5 of 6 benchmark datasets with significant improvements.
We investigate the dependence approximation gap on six synthetic datasets with different levels of dependence complexity. On average, the proposed TPGNN outperforms the best baseline by 23.41% % on the approximation error. theoretical result further demonstrates the dependence learning ability of TPGNN.

---

2
Related Works
MTS Forecasting There are two main categories of methods for MTS forecasting: implicit- dependence approaches and first category LSTNet [20]. it captures the variable dependence with convolution over variables. approaches represent the variable correlation as explicit graphs and pre-
approaches. One representative method of the
The sauuttuaal-ependeee dict with GNNs. Graph Wavenet [42] (GWN) attempts to learn the variable correlation with static node representations and captures the temporal pattern with convolution neural networks (CNNs). MTGNN [41] follows the idea of GWN to learn variable correlation statically and proposes a new graph convolution module for MTS forecasting. Although works like GMAN (50). SL.C (49 and StemGNN
4 model a dynamic correlation among variables with self-attention, the learned graph is sensitive the input, causing significant forecasting variance. Our construction is based on a set of time-variant coefficients, the result is independent of the input and robust in forecasting. Some works that focus learning time-narying graph structure [26] 33 45) However, these graph structures are not captured from the forecast task directly. They thus cause bias and increase the computation cost. but their methods do not thoroughly discuss the
There are some transformer-base works [43 46 48
issues.
GNNs and Polynomial Graph Filters (PGFs) GNNs are based on the message-passing mechanism. One representative work is GraphSAGE [14), which learns a sample-aggregation function to generate the node embedding. Michael et al. (6) generalize the convolutional neural networks (CNNs) the graph structure. Many filters of GNNs belong to PGFs, and Gama et al. [11] discussed the connections. In order incorporate the node feature of high-order neighbors, many works introduce PGFs their methods. APPNP (18) and SGC (40) adopt fixed-weight PGFs and use hyperparameters to define the coefficients. However, the constructed fixed-weight PGFs are biased because the coefficients are iisslirrelevant. GPR-GNN (5) constructs PGF from the graph dataset, where the coefficients are learnable. Besides, there are also some PGFs-based methods for MTS data learning [13] 15 16). Although these works are competitive in capturing graph structure, they fail in learning the dynamic correlation, we illustrate the point Section 5.4 Moreover, the missing/noixy/nncooplet adjacency matrix causes difficulties in applying these methods. Our approach introduces self eff-adaptive graph the PGFs construction, which improves the dependence capturing ability and the model versatility.
3
The Framework of TPGNN
Polynomial Coefficients Generating
3. TPGNN Framework
(1+748)
Predection
Decader
Attenion
Cyclic Timeskamp Eniaaking
Peluemial Cuelficions
Birbodding
g T)
Propugation K-urder Matrix Polynomial
Powers Adpconcy Mamix
TPG Module
Traperal Ararion
Hidder Fenurra
Embeliing
Resresentriios Generate by Mutippe Tranfommaion Matrices
X
X(44T-1]
Figure 2: Overview of the proposed TPGNN. (1) The TPG module generates a set of coefficients according the time steps. (2) We define a matrix polynomial with the coefficients to capture the dependence. (3) TPGNN has an encoder- decoder structure and predicts in an ruto-regressive manner.
In this section, we first define the MTS forecasting task the context of graph signal processing. We then introduce the TPG module and illustrate the inference pipeline of our framework.
3

---

3.1 Problem Defintion
At time step I, the MTS data is signal set g = (V. x(0), WOO.. The node set V (01 N) contains N variables of MTS data, g()) is the edge set, X(0 E RN records the signal of N variables, and w N is weighted adjacency matrix. If variables and j are dependent, then an edge connects the two nodes, and entry w indicates their correlation. Otherwise, w if
ij equals to zero. Given I observations of the signal sets, our problem is to find a function F' that can forecast the variable state of the subsequent T' signals:
(g (0g.((+))..... ..... "
G((+T-1)) F x(++), ((+++1) X(+T+T'--)
The setting regards the graph structure as a latent feature of MTS data, and the forecast target the same the standard setting. Prevailing works [25 42 regard ((() time-invariant matrix, while in our work, W(0 changes with the time.
3.2 Represent the Correlation as a Temporal Matrix Polynomial
To capture & and W for MTS data, we construct series of matrix polynomials that share matrix basis. The TPG module controls the influence of cach polynomial term temporally with a set of adaptive coefficients. As result, we can approximate wide range of dynamic graph structures.
Counstructing the adjacency matrix basis. We firstly define an initial adjacency matrix A RNNN following the self-adaptive graph proposed by Wu et al. [42). They learn variable embeddings E IR Nxe (c is the embedding dimension) from MTS data and define the variable dependence with embedding similarity. Besides, they further remove weak connections with R.L.(()) and normalize the result with (.f)
A = Softtaax(eL(((EE))
(2)
For MTS data that have a prior structure, e.g., the physical distance among sensors, denote the corresponding adjacency matrix as W R To incorporate W into the encoding process, we first calculate its symmetric normalized Laplacian 17 L = D- + W)D- (I is the identity matrix and D is the degree matrix), then combine the two results define the initial adjacency matrix:
A = SoftMax(ReLL((EE)) + L
Generating the temporal polynomial coefficients. At time step t. we represent the variable depen- dence as a K-order matrix polynomial of A:
( K (0) A R
Due to the polynomial coefficients being learning coefficients for every time step impractical because the sequence length grows infinitely. Fortunately, the periodicity property is common in MTS data (8 [8].). Therefore, propose to use a set of cyclic timestamp embeddings to index the time step. Firstly, we define T, timestamp embeddings (e(2)
W(i shows dynamic behavior. However,
c(T)) E DRD,, where Tμ is the cycle and D. is the embedding dimension. ....,,, ...., Following a cyclic order, we then assign the (t%T,,))t embedding to time step t, where % is the
remainder operator. Finally, we generate the coefficients for time step by the e (*%Tp) As shown in Figure (1), Given T historical graph signals start from time step f, we calculate the coefficients for each graph signal with a coefficient matrix W. E IR (1)
a E R
(a
(t+ (t+T-1)) = (ets
(1%T,)
(1+T-1%T, WW
(5)
According to Equation 4 each (t) defines -ordder matrix polynomial of A. representing variable dependence of time step t. Instead of predicting with T' different matrix polynomials, we use an average result to improve the prediction efficiency and robustness. Due the linearity of the polynomial, the average polynomial is equivalent to the polynomial with average coefficients. We calculate the final coefficients with another parameter matrix W. E Tx1 (average matrix).
(āo, @1...., ......),))).. ēx) (a
(+T (+T-1)) W.
(6)

---

In Figure (2), we illusrate the TPG module's propagation process with a. Let X E RNXD, denote the matrix signal embedding. W RD. = 0. .... K denote the model parameter matrices, -|- ||x denote the Frobenius norm of matrix, we derive the hidden feature Z E Nx as follows:
WR
z DK R=
W
TPG module follows the diffusion graph convolution layer 23 to introduce (K + 1) parameter matrices for enhancing representation diversity. Besides, we decouple the parameter matrix norm and coefficient by normalizing W with a factor of ? since W with a large norm increases the k-th term's 's contribution. As result, à completely controls the contribution of each term.
3.3 Inference Pipeline
In Figure 2 (3), TPGNN has an encoder-decoder structure. First, we derive the historical data embedding with linear transformation, then feed the results into the encoder. The encoder generates data encoding Z (1)++T-1) E Txx De for time step Ê to t + T temporal attention layer. The temporal attention layer follows the design of Transformer (37), which uses self- atffetttenion to capture intra-series patterns for each variable. Finally, the decoder forecasts with the data encoding and temporal attention layer. For the first prediction of time step + T, the decoder queries the data encoding with learnable beginning of sentence (BOS) token Enos E RRNxD, The query result represents the first prediction, denoted as E(-T)) NDDx, We a prediction matrix W pred E IR P to get the forecasting result X (++ E R NX1
with the TPG module and
E Decoder(EEoo)
Z (1+TT1))
(8)
X =Bx (t+
W pred,
After generating the subsequent & query results (EX (t+T) E((TT++-)),, the decoder derives the (k: + 1)-th result x (++ by querying (t:++T11) with the latest Lmaz query results. The forecast
basically follows auto-regressive (AR) mechanism, where Lmaa is the maximum query length.
E (++++)) = Decoder( (4T+k-lmm
E ( 1) Z),
(1+T++) -Ex -EQ
(++T+))
W
pred-
The above process continues until getting the subsequent 7" forecasts, such AR mechanism helps TPGNN to capture long-term intra-series dependence with informative context.
Theoretical Properties of TPGNN
To explore the dependence learning capability of TPGNN, focus analyzing the theoretical gap between the optimal graph structure and the TPG module's approximation in this section.
TPGNN is able to achieve perfect approximation. Unlike the real function, the approximation of graph structure largely depends on the topology property the target graph, where the lower bound of the approximation eиrоr is nonzero in many cases. However, TPGNN mitigates the gap for wide range of dynamic graph structures with a small group of parameters, which leads to a robust and accurate forecasting result. The approximation capability of TPGNN is concluded as the following result, we show the detailed statement and proofs in Appendix A.9 due to the space limitation.
Theorem 1. Let G..)...., G(T) E NNN be the symmetric normalized Laplacian of the optimal ..... graph structure for time step 1 to T. A E N is the initial adjacency matrix of TPGNN. We model these Laplacians with Equation 4 and the corresponding approximation error (1:T)) + (O() - IB, where the || |[ is the Frobenius norm of the matrix. Suppose all the matrices are symmetric (undirected graph), G.G, = G,G., Vi,j, A has N different singular values, and the polynomial's order is large enough. Then have the following estimation for (1:2T)
Amau L,, ( < (1:T) < (1- Amin | |
(10)
5

---

where E, | = - || is the average norm of the Laplacians, Amin, Amaz E [0. the minimum and maximum eigenvalues of a constant matrix. If A is commutative with G then Amar Amin = 1, i.e., we achieve a uniform perfect approximation. Although the zero error depends on the commutative condition, A is learnable with Equation 2 which relaxes the restriction. Moreover, TPGNN empirically achieves the best approximation compared with other methods.
5 Experiments
Table I: Dataset statistics.
Datasets
Samples
# Nodes
Sample Rate
Input Length
Output Length
Traffic
17,544
862
hour
168
Enlegy
52.560
137
10 minutes
168
Electricity
26304
321
I hour
168
Exchange-Ran Rate
7,588
8
day
168
1
PEMS-D7
12672
228
5 minutes
12
12
PEMS-Ba Bay
52116
325
5 minutes
12
12
5.1 Experimental Setup
We validate the performance of TPGNN on two tasks: single-step and multi-step MTS forecasting, In Table [ we present the statistics of six benchmark datasets. The first four benchmark datasets [9] aim to predict a single future step: the last two datasets [33 44 record distance matrix among sensors, where the goal is to forecast multiple future steps. More details about the datasets are given in the AppendixA..3] For single-step prediction, the baselines are VAR-MLP (47). GP (3I. RNN-GRU [4T), LSTNet 200.. TPA-LSTM (34), and MTGNN (41). MTGNN firstly introduces GNNs to general MTS data and achieves state-of-the-art (SOTA) performance; other baselines are representative
Table 2: We forecast 3, 6, 12, and 24 horizons for the first four real-world datasets, and models with high CORR and low RSE are preferred. TPGNN outperforms other models on three of the first four datasets. For the remaining two datasets, we predict the next 15, 30, and 60 minutes based on one-hour observation, and the three metrics represent the prediction error. The results show that TPGNN achieves state-of-the-art performance on both short-term and long-term predictions.
Dunset
Solar Beeray
Traff Hacizon
Electiiity Hinians
Exchange Rate
Hocioon
Borians
VARMEP
RSE
0.1922
0.2670
0.4244
(1654)
0.5582
B18579
0.6023
0.6166
0.1892
0.1600
0.1557
0.1274
0.0263
0.0394
D.9407
0.0678
VARMLP
CORR
0.9829
0.9655
0.9058
0.7149
0.8245
0.7915
0.7929
0.789]
0.8738
0.8389
0.8192
0.3679
0.8099
0,8725
0.8200
0,7675
0.3156
0.5200
0.797
0.082
0.7722
0.6406
0.3955
0.1500
0.1621
0.0299
0.0222
0.050
DORR
09731
0,918
0.5518
0.591
0,8811
02405
0.9671
0.7999
0.567
03334
0.8394
0.8818
08913
03193
0.22%
RNN-GRU
RSR
01912
0.268
0.463
0.483
0.535
0.522
0.5562
0.563
0.100
0.114
0.118
0.1285
00091
0.0064
00408
0/0636
RNN-GRU
0.5111
0.6355
LSTNa
RSE
0.1443
0.255)
0.3254
0.4643
0,477
0.4893
0,450
0.4055
0.864
0.0931
0.1007
0.1007
0.0256
0,0250
R.0556
0.0449
LSTNet
CORR
09943
0.9090
0,9457
0.850
0.8721
0,800
0.5614
0.555
0,9233
0.9155
0,9077
0.919
0.933
0
0.9511
0.9354
0,4487
0.4641
00074
0.8341
IRA-LTM
DORR
09850
0.97
0.9487
(1961
0.3812
08717
0.5717
0.8679
0.949
08337
0,9150
0.913
(979)
0.929
0L9564
6.9011
MIGNN
RSB
0.87%
0.2345
0.3109
014270
0.4163
B.4744
0.4461
0.4535
0.0745
0.6675
0.0916
0.2953
0.0944
0,6259
B.044
0.0456
MTGNN
0.9708
0.955]
0.9372
TPGNN
RSE
0.130
0.2412
0.3059
0.3495
0,305M
0.4715
0.4476
0.4095
8.0627
0.0885
0,0699
0,8936
0.0174
0,0250
100550
0.0458
TPGNN
DORR
0.540
0.9716
0.9529
09719
0.9233
0.945
0,9028
0.8858
0,4177
0.933
8,9235
0.9295
0.793
0.9637
019599
0.9966
PEMS BAY (Horizon 3/6/12)
PEMS D7 (Horizon 3//12)
Model
MAR
MAPE(%)
RMSH
MAE
MAPE(S)
RMSE
ARIMA
1.6//2.3/3.38
3.50/5.40/8.30
3.30/4.76/6.66
12.92/13.9448 94/15.20
1.0999.13/9.8
FC-LSTM
2.05/2.20V..37
4.80/5.21V5.70
4.19/4.55/4.96
3.57/3.92/4.16
8.609.55/10. 10
6.20/7.0377.
STGON
1.39/1.84/2 3.00/4.22/5.55
199//4.12/..33
2.25/3.03/4.02
5.26/7.33/9.88 85
4.04/5.70/7 7.64
DCRNN
1.38/1.74/2.07
1.9003.90/499
2.95/3.97/4.77
2.25/2.98/3.83
5.30/7.39/9.88
4.04/5.58/7 58/7.11
StemGNN
1.52/1.94/2.45
3.38/4.58/6.03
3.06/4.07/5.00
0./4
2.94/3.66/4.66
7.63/9.66/122
5.05/6.35/8.0 000000
Graph WaveNet
1.30/166//.95
2.73/3.67/4.65
2.74/3.70/4.52
2.18/2.95/3.88
5,02/7 22/10.03
4.18/5. 82/8822777. ,16
Informer
1.30/2.40/2.55
5.02/5.32/5.73
4.24/4.49/4.85
3.64/3.77/4.09
8.66/9.07/9.87
8.02/6.3416
MIGNN
1.32/1.65/1994
2.77/3.69/4.53
2.79/3.74/4.49
2.17/2.89/4.02
5.03/6.93/9.95
4.01/5. 84/8.78
TPGNN
1.26/1.65/2.05
2.56/3.47/4.40
2.64/3.65/4.58
2.12/2.72/3.22
5.0016.738.22
45/6/6.4

---

non-GNNs-basse methods. For multi-step prediction, the baselines are ARIMA [23) FC-LSTM [3]. DCRNN [22]. STGCN (44), StemGNN (4), Graph WaveNet, Informer (ST), and MTGNN;; all the baselines are GNN-based except ARIMA, FC-LSTM and Informer. These GNNs-based baselines are representative methods for MTS data with a prior structure. Besides, the Informer is novel Transformer-baat baased model that achieves SOTA performance on long-term forecasting. We list the paramter scale of each model in Appendix A.4 to show our method is light-weight. We use five evaluation metrics [41]: Mean Absolute Error (MAE), Mean Absolute Percentage Error (MAPE), Root Mean Squared Error (RMSE), Root Relative Squared Error (RRSE), and Empirical Correlation Coefficient (CORR). For CORR, higher values are better. For the other metrics, lower values are better. We tune the hyperparameters on the validation dataset, the results are presented in the Appendix A.. We divide the dataset into three parts for training, validation, and testing with ratio of 7:1:2. More details about the baselines, metrics, and experiment settings are in Appendix AA4 A.6
5.2 Main Results
Table 2 summarizes the experimental results of TPGNN. Generally, TPGNN achieves the state- of-the-art most of the datasets. Our framework has an un-par performance for the single-step forecasting task with the SOTA methods like MTGNN and TPA-LSTM. Moreover, TPGNN makes a significant improvement on Traffic and Electricity datasets. On the Solar-Energy, TPGNN lowers RSE by 1.61% %, 18.08% and increases CORR by 1.47%, 6.93% over the horizons of 12, 24. Our method improves the CORR by 2.21% average over the four horizons of the Traffic. Moreover, we lower the RSE by 15.82% on average over the four horizons of Electricity. Our method fails to achieve SOTA performance on the exchange-rate data. We think the main reason is the small sample size, which causes difficulties in capturing the dynamic variable dependence. The second row of Table[[concuute the results of the multi-step forecasting task, which demonstrates that TPGNN achieves SOTA performance on the two datasets with prior structure. On the PEMS-BAL BAY, TPGNN lowers the MAPE by 5.47% on average over the three horizons. Besides, The RMSE is reduced by 4.30% 2.41% over the horizons of 3 and 6. TPGNN reduces the MAE/MAPE by 8 8.04% /4.6%6..%% on average over the three horizons on the PEMS-D7 dataset. The RMSE is lowered by 2.33%, 4.23% over the horizon of 6 and 12. Although the prior structure is provided to each baseline, the results on the last two traffic datasets demonstrate that TPGNN can capture more precise variable dependence and setresseries patterns than other GNNs-based methods.
5.3 Ablation Experiments
Table 3: Long-term prediction results for ablation study on the PEMS-D7 D7 dataset.
Metries
TPGNN
w/o TPG
w/o dynomic
overview
normalize
w/o K-matricos
MAE
3.215:0.014
3.701
3.48020.047 8.873+0.014
3.330:2.031
3.261:20035
3 3.294:0:036
MAPR(S))
8.221+00.035
9.553+0.106
8.
8.347+0.061
8.406+0.244 245
RMSE
6.559-10023
7.47310.033
6. 6.806100098 6.989110084
6.67110.033
6.701
The PEMS-D7 includes a prior structure and has complex inter-series and intra-series dependence, we conduct ablation experiments on the PEMS-D7 to evaluate the effectiveness of each design in our method. Due to the importance and complexity of the long-term prediction, we set the horizon as 12. More results of other horizons can be found in Appendix A.8 There are five experiments in total, we repeat each experiment& 5 times and report the average and standard deviation (std). w/o TPG: TPGNN without the TPG module. We replace the graph constructed by TPG with the prior structure of PEMS-D7. w/o dynamic: TPGNN without the time-varying coefficients. We adopt set of learnable static coefficients construct the graph. w/o overview: TPGNN does not use average coefficients in Equation 6 We predict with I graphs defined by Equation 5
w/o normalize: TPGNN without the normalization factor in Equation 7 w/o K-matrices: TPGNN without multiple parameter matrices in Equation 7 We use an identical normalized matrix to derive the hidden feature. Table summarrzzs the experimental results, which indicates that all the designs are indispensable. The result of w/o TPG illustrates the TPG module's 's critical contribution to our method. Although we replace the graph constructed by the TPG module with the prior structure given by PEMS-D7, the performance has a steep decline by 13. 13%, 13.94%, 12. 23% on the three metrics. w/o dynamic follows the strategy of GPR-GNN (5) that uses static coefficients to capture graph structure from data. However, the results indicate the importance of introducing varr-vtriant coefficients, which
7

---

NDoX
MIGNN
NIGX
Grneh Utreet
Lox MAG
Goyb Revset
RA BD
Varoot
Valce
(a) The upproxiiaation and prediction erver of different methods.
TRANNAI
IPLAN Ac
IPUNKA
Loc.
The Value
The Value cf N
The Value of
The approximation under the different settings of
Figure 3: The approximation error and prediction error of different graph approximation methods. (a) compares TPGNN with other basclines, the results indicate TPGNN significantly reduces the approximation error and achieves the highest prediction accuracy. (b) investigates the effect of polynomial order to the dependence approximation error. The high-order polynomials impairs the precision and robustness of the dependence learning.
significantly improve the long-tern terg prediction accuracy by 7.04% on average. w/o overview and w/o K K-matrices show large variance compared with other results, indicating the two modules are essential for improving model robustness. Besides, the w/o overview's performance close to the w/o dynamic, demonstrating the necessity of using the average coefficients. w/o normalize has comparable performance to the TPGNN, possibly due to the weight decay causing similar norms. Nevertheless, it demonstrates that the normalization helps TPGNN capture the variable dependence.
Table 4: Average results on six synthetic datasets configured with different N
Method
TPGNN
Graph Wavener
MTGGNN
GPR-GNN
Self-artemtio
0.176-7..05x100
0.207-3.476x00-+
0.098+199811 -10
0.1653+1449x
MAE
442 142x 10
10.00 10
0.06914429xx00
1.020881..888 10
0.01026_128xx0000
RMSE
189x:11
0.01632=2.27x:0000
0.1141134410
10556113.537x100
0.01993-205x
5.4 Study of the Graph Structure Approximation Gap
Synthetic data. To investigate the empirical gap between the optimal graph structure and the approximation result, we propose to generate MTS data with ground-truth dynamic dependence using non-repeating random walk (NRW) model [7], which is widely adopted in time-series data generation [ 32). At time step I, we synthesize the matrix signal ( E R with dynamic weighted adjacency matrix ((!) by (t) (t-l( (t-1), .), where .(.:.)) is the normal distribution, a E RR controls the variance, and X is sampled from discrete uniform distribution. We define ( by traversing No, constant matrices (G) ,.... G(Mw)) in cyclic order, where each G Laplacian of sparsified random adjacency matrix. Given a period of Tр Tp 2 N.. we partition the period into N., even intervals of length T., and each interval shares one of the matrices, ie., ( G (((TTT))/T)) where [:] is the rounding function. We point out that N... controls the complexity of dynamic dependence, and N, = corresponds to static-dependence case. To increase the data diversity, we randomly initialize the (() for every Tp step. We set T 120, a = 0.001 in our evaluation and generate six MTS data of length 2400 with N... 1, ...., 6. Besides, each

---

(93, 218) (61), 218)
00 The plasiel locaions of 218, 95, and
(30 dytanik depeodasse learted TPGNN o9 2183 and (00,
Figure 4: Three nodes are highly correlated in the TPG's learned result but independent in the prior structure. We find they on the same road and have different dynamic correlation trends.
synthetic dataset is divided into three parts for training, validation, and testing with a ratio of 7:1:2. More details about the synthetic algorithm, configuration, and synthetic results are in Appendix [A.3]
Predicting with different graph approximation methods. We evaluate the dependence capturing ability of different methods the six synthetic datasets, where the task is the next-step prediction
based current variable states. Suppose that W(() E I V i 0, ...... T is the learned adjacency matrix series, we measure the approximation gap with a Mean Frobenius Error (MFE) metric, defined by MFE = TN= - - Wr Besides, we use MAE/RMSE to measure the forecasting accuracy. The baselines Self-attention. The first three methods are saatic-dependence-baseee
Graph Wavenet (GWN), MTGNN, GPR-GNN, and
Self-attention constructs a dynamic graph, which is adopted in many works like GMAN (50) and StemGNN (4) We follow the implementation of StemGNN to learn the graph structure with GRU module and self-attention operator in the evaluation. The polynomial order K is fixed as 2 in the evaluation, we repeat each experiment times and report the average/std. more details about the settings are in Appenedix A.6 The main results are summarized in Figure (a) and Table 4 demonstrating that TPGNN outperforms other baselines on the six synthetic datasets. In Table 4 TPGNN reduces the graph approximation error by 23. 23.41% 1% on average over the six datasets. The first chart of Figure (a) also illustrates the improvement, we consistently achieve the best approximation under different No. Moreover, the MFE of TPGNN has a descending trend with the increase of N,, while other methods' approximation eтrors are increasing. We think the TPG module overfits on datasets with small Nw. since their behavior tends to have static dependence. TPGNN achieves the lowest prediction error on average, the improvement in the accuracy is slight compared with MFE because the task is a simple next-step prediction. Furthermore, we observe that the ranking on MFE is identical to the MAE/RMSE, which demonstrates the importance of capturing precise variable dependence for MTS forecasting.
The effect of polynomial order. We further investigate the relation between approximation error and the polynomial order K, where the K ranges from to 4, and K = 1 corresponds to a linear approximation. The first two charts of Figure 3 (b) present the average MFE and corresponding std, respectively. The results show that the approximation variance increases significantly with K; especially when K- = Moreover, TPGNN- K4 has a large MFE on the six datasets compared with other configurations. Therefore, we think high-order matrix polynomial impairs both the precision and robustness of the dependence capturing ability of TPGNN. We point out that the observation non-trivial since GPR-GNY achieves good results with a large K (K 2 10) on normal graph datasets, possibly due to the difference between MTS forecasting and node classification. The third chart shows the prediction error, it also validates that model with low MFE has a low prediction error.
Case study on the real-world dataset. Due to the absence of ground-truth dependence, we illustrate the correlation modeling ability of TPGNN on real-world datasets with an example of PEMS-D7 -D.. We find three highly correlated nodes in the learned result but independent in the prior structure, where the node IDs are 60, 93, and 218. In Figure 3 (a), we mark the physical location of the three nodes according to PEMS 3. The three nodes are on the same road, which illustrates that TPGNN can learn reliable dependence from data. In Figure (b), we show the learned correlation of pairs (60, 218) and (93, 218). We observe that (93, 218) has stable dependence and (60, 218)'s 's correlation increases in the evening, the difference possibly caused by the branch road between 218 and 60.

---

Conclusion
We proposes novel GNNs-based method for MTS forecasting. TPGNN, which represents the vari- able dependence as a temporal polynomial matrix. The results on six real-world datasets illustrate the outstanding forecasting performance of TPGNN. Besides, extensive experiments on synthetic datasets demonstrate that our method achieves the best dependence approximation than other baselines.
Limitations and future works Although TPGNN achieves outstanding performance MTS forecasting and dependence capturing, our methods have limitations. First, the dependence captured unreliable and decrease
by TPGNN is not strict causal structure. Therefore, some correlations the model's robustness. Second, MT'S forecasting in the real world is affected by rare events like weather disasters, which may significantly impair prediction accuracy. The future works focus on MTS data to solve the above limitations.
causal learning and transfer learning 24 28 38
Acknowledgment
The work of the authors was supported by the National Natural Science Foundation of China (No. 62132017).
References
[1] ADHIKARI, R., AND AGRAWAL, R. K. A combination of artificial neural network and random walk models for financial time series forecasting. Neural Computing and Applications 24 (2013), 1441-1449.
[2] ASUNCION, A., AND NEWMAN, D. J. Uei machine learning repository. [EB/OL], 2007.
http://www. ics uci http://wwlaanm//eopssiotooos html
[3]
CA.Gov. Pems. [EB/OL], 2010. https://pems: dot. ca. gov/
[4] CAO, D., WANG, Y., DUAN, J., ZHANG, C.,, ZHU, X., HUANG, C., TONG, Y., XU, B., BAI, J., TONG, J., ET AL. Spectral temporal graph neural network for multivariate time-series forecasting. arXiv preprint
(2021).
[5] CHIEN, E., PENG, J., LI, P., AND MILENKOVIC, O. Adaptive universal generalized pagerank graph neural network. arXiv: Learning (2021).
[6] DEFFERRARD, M., BRESSON, X., AND VANDERGHEYNST, P. Convolutional neural networks on graphs with fast localized spectral filtering. In NIPS (2016).
[7] DENTON, A. M. Kernel-density- based based clustering of time series subsequences using continuous random-walk noise model. Fifth IEEE International Conference on Data Mining (ICDM '05) (2005), pp.-.
[8] DI.TTO,, P., QIU, W., AND RUDKIN, S. Cyclicality, periodicity and the topology of time series. ArXiv abs/1905. /2/ 18 (2019).
[9] FENG, H., You, Z., CHEN, M.. ZHANG, T., ZHU, M., WU. F., WU, C., AND CHEN, W. KD3A: unsupervised multi-source decentralized domain adaptation via knowledge distillation. In Proceedings of the 38th International Conference on Machine Learning, ICMI. ICMI,2021, 18-24 July 2021, Virtual Event (2021), M. Meila and T. Zhang, Eds., vol. 139 of Proceedings of Machine Learning Research, PMLR, pp. 3274-3283.
[10] FRIGOLA, R. Bayesian time series learning with Gaussian processes. PhD thesis, University of Cambridge, 2015.
[11] GAMA, F., ISUFI, E., LEUS, G., AND RIBEIRO, A. Graphs, convolutions, and neural networks: From graph filters to graph neural networks. IEEE Signal Processing Magazine 37 (2020), 128-138.
[12] Guo, S., LIN, Y., FENG, N., SONG, C., AND WAN, H. Attention based spatial-temports graph convolutional networks for traffic flow forecasting, In Proceedings of the AAAI Conference on Artificial Intelligence (2019), vol. 33, pp. 922-929.
[13] HADOU, S., KANATSOULIS,, C. I., AND RIBEIRO, A. Space-time graph neural networks. ArXiv
(2021).
10

---

[14] HAMILTON, W. L., YING, R., AND LESKOVEC, J. Inductive representation learning on large graphs. arXiv preprint arXiv:1706.02216 (2017).
[15] ISUFI, E., LOUKAS, A., PERRAUDIN, N., AND LEUS, G. Forecasting time series with varma recursions on graphs. IEEE Transactions on Signal Processing 67 (2019),
[16] ISUFI, E., AND MAZZOLA, G. Graph-time convolutional neural networks. 2021 IEEE Data Science and Learning Workshop (DSLW) (2021), 1-6.
[17] KIPF, T. N., AND WELLING, M. Semi-supervvied classification with graph convolutional networks. arXiv preprint 160vv:1600009900 (2016).
[18] KLICPERA, J., BOJCHEVSKI, A., AND GÜNNEMANN, S. Predict then propagate: Graph neural
networks meet personalized pagerank. In ICLR (2019).
[19] LAI, G., CHANG, W.-C., YANG, Y., AND LIU, H. Modeling long- and short-term temporal patterns with deep neural networks. The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval (2018).
[20] LAI, G., CHANG, W.-C., YANG, Y., AND LIU, H. Modeling long-and and short-term temporal patterns with deep neural networks. The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval (2018), pp. 95-104.
[21] LEE, W. K. Partial correlation- based attention for multivariate time series forecasting. In Proceedings of the AAAI Conference on Artificial Intelligence (2020), vol. 34, pp. 13720-13721.
[22] LI, Y., YU, R., SHAHABI, C., AND LIU, Y. Diffusion convolutional recurrent neural network: Data-driven traffic forecasting. arXiv preprint 77770: (2017).
[23] LI, Y., YU, R., SHAHABI, C., AND LIU, Y. Diffusion convolutional recurrent neural network: Data-driven traffic forecasting. arXiv: Learning (2018).
[24] LIANG, X. S. Normalized multivariate time series causality analysis and causal graph recon- struction. Entropy 23 (2021).
[25] MENGZHANG, L.., AND ZHANXING, Z. Spatial-temporal fusion graph neural networks for traffic flow forecasting. arXiv preprint arXiv:20/2.0966 2.0964 (2020).
[26] NATALI, A., ISUFI, E., COUTIÑO, M., AND LEUS, G. Learning time-varying graphs from online data. IEEE Open Journal of Signal Processing 3 (2022), 212-228.
[27] ORESHKIN, B. N., AMINI, A., COYLE, L.,, AND COATES, M. J. Fe-gaga: Fully connected gated graph architecture for spatio-temporal traffic forecasting. ArXiv abs/2007.15533 1553/ (2021).
[28] PAN, J., AND YANG, Q. A survey on transfer learning. IEEE Transactions on Knowledge and Data Engineering 22 (2010), 1345-1359.
[29] PUECh, T., BOUSSARD, M., D' AMATO, A., AND MILLERAND, G. A fully automated periodicity detection in time series. In AALTD PKDD/ECMII (2019).
[30] QING, L., YONGQIN, T., YONG-GUO, H., AND QINGMING, Z. The forecast and the optimiza- tion control of the complex traffic flow based on the hybrid immune intelligent algorithm. The Open Electrical & Electronic Engineering Journal 8 (2014), 245-251.
[31] ROBERTS, S., OSBORNF, M., EBDEN, M., REECE, S., GIBSON, N., AND AIGRAIN, S. Gaussian processes for time-series modelling. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences 371, 1984 (2013), 201 10550.
[32] SARIA, S., DUCHI, A., AND KOLLER, D. Discovering deformable motifs in continuous time series data. In IJCAI (2011).
[33] SHAFIPOUR, R., SEGARRA, S., MARQUES, A. G., AND MATEOS, G. Identifying the topology of undirected networks from diffused non-stationary graph signals. IEEE Open Journal of Signal Processing 2 (2021), 171-189.
[34] SHIH, S.-Y., SUN, F.-K., AND LEF, H.-Y. Temporal pattern attention for multivariate time series forecasting. Machine Learning 108, 8 (2019), 1421-1441.
[35] SONG, C.,, LIN, Y., GUO, S., AND WAN, H. Spatial-temporal synchronous graph convolutional networks: A new framework for spatial-temporal network data forecasting. In Proceedings of the AAAI Conference on Artificial Intelligence (2020), vol. 34, pp. 914-921.
[36] SUTSKEVER, I., VINYALS, O., AND LF, Q. V. Sequence to sequence learning with neural networks. arXiv preprint arXiv:1409.3215 (2014).

---

[37] VASWANI, A., SHAZEER, N., PARMAR, N., USZKOREIT, J., JONES, L., GOMEZ, A. N., KAISER, L., AND POLOSUKHIN, I. Attention all you need. arXiv preprint arXiv:706.003722 (2017).
[38] WEN, T., AND KEYES, R. Time series anomaly detection using convolutional neural networks and transfer learning. ArXiv abs/1905. 13628 (2019).
[39] WU, C.-H., Ho, J.-M., AND LEE, D.-T. Travel-time prediction with support vector regression.
IEEE transactions on intelligent transportation systems 5, (2004), 276-281.
[40] WU, F., ZHANG, T., DE SOUZA, A. H., FIFTY, C., Yu, T., AND WEINBERGER, K. Q. Simplifying graph convolutional networks. ArXiv abs/1902.07153 (2019).
[41] WU, Z., PAN, S., LONG, G., JIANG, J., CHANG, X., AND ZHANG, C. Connecting the dots: Multivariate time series forecasting with graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (2020),
pp. 753-763.
[42] WU, Z., PAN, S., LONG, G., JIANG, J., AND ZHANG, C. Graph wavenet for deep spatial- temporal graph modeling. arXiv preprint arXiv:/906.000
(2019).
[43] Xu, M., DAI, W., LIU, C., GAO, X., LIN, W., QI, G.-J., AND XIONG, H. Spatial-temporiy transformer networks for traffic flow forecasting. ArXiv abs/2001 1.0908 (2020).
[44] YU, B., YIN, H., AND ZHU, 7. Spatio-temporal graph convolutional networks: A deep learning framework for traffic forecasting. arXiv preprint arrXiv:/799.000 04875 (2017).
[45] ZAMAN, B., RAMOS, L. M. L.,, ROMERO, D., AND BRFERUIII-LLZAAN B. Online topology identification from vector autoregressive time series. IEEE Transactions on Signal Processing 69 (2021), 210-225.
[46] ZERVEAS, G., JAYARAMAN, S., PATEL, D., BHAMIDIPATY, A., AND EICKHOFF, C. A transformer-base framework for multivariate time series representation learning. Proceedings the 27th ACM SIGKDD Conference Knowledge Discovery & Data Mining (2021).
[47] ZHANG, G. P. Time series forecasting using a hybrid arima and neural network model. Neurocomputing 50 (2003), 159-175.
[48] ZHANG, J.-W., SUN, Y., YANG, Y., AND CHEN, W. Feature-Proxy Transformer for Few-Shot Segmentation. In NeurlPS (2022).
[49] ZHANG, Q., CHANG, J., MENG, G., XIANG, S., AND PAN, C. Spatio-temporal graph structure
learning for traffic forecasting. In Proceedings of the AAAI Conference on Artificial Intelligence (2020), vol. 34, pp. 1177-1185.
[50] ZHENG, C., FAN, X., WANG, C., AND QI, J. Gman: A graph multi-attention network for traffic prediction. In Proceedings of the AAAI Conference Artificial Intelligence (2020), vol. 34, pp. 1234-1241.
[51] ZHOU, H., ZHANG, S., PENG, J., ZHANG, S., LI, J., XIONG, H., AND ZHANG, W. Informer: Beyond efficient transformer for long sequence time-series forecasting. In AAAI (2021).
[52] ZIOO,, X., YAN, H., ZIIANG, H., AND PENG, C. Model predictive control with feedback correction for optimal energy dispatch of networked microgrid. Transactions of the Institute of Measurement and Control 41 (2019), 1540 1552.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] see Section
(c) Did you discuss any potential negative societal impacts of your work? [Yes] see
Appendix(A.1
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
12

---

(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proof' of all theoretical results? [Yes] see Appendix A.9
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material as URL.)? [Yes] see Ap- pendix A.6
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] see Appendix A.6
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] 5.3 5.335.444mm
Appendix AA
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] see Appendix[A.6)
4. If you are using existing assets (c.g., code, data, models) or curating/relcasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes] see Appendix A.3
(c) Did you include any new assets either in the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [Yes] see Appendix [A.3]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [Yes] see Appendix A.3
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A] not applicable
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A] not applicable
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A] not applicable
13


Reviews:
[{"review_id": "re7MRekgf5O", "reviewer": "Reviewer_ppp4", "summary": "The paper proposes TPGNN, a novel graph model for multivariate time-series forecasting. The most significant improvement of TPGNN is the ability to learn dynamic correlations between nodes. TPGNN models a dynamic graph with a novel component, TPG, based on matrix polynomials. The paper demonstrates how the proposed model can learn actual correlations in a simulated setting and provide theoretical guarantees for the approximation. TPGNN achieves SoTA performance on 6 benchmark datasets, on both single-step and multi-step settings.", "questions": "- Many recent studies (such as Informer, Autoformer, FEDFormer, and N-HiTS, among others) use the Electricity, Traffic, and Exchange datasets for the long-horizon multi-step forecasting setting. Why didn't the authors consider these datasets as benchmarks for this task?\n- How does the choice of T_p affects the performance? Would it be beneficial to match the cycle to known seasonalities of the data?\n- Adding simpler univariate baselines to the experiments (classic models such as ARIMA, SeasonalNaive, and DL methods such as N-BEATS) will help better measure the complexity/accuracy tradeoff of TPGNN.", "limitations": "Limitations are discussed, and I do not identify potential negative social impacts.", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper proposes a novel module, TPG, to model dynamic correlations between time series.\n- Authors provide theoretical approximation guarantees and empirical results on simulated data.\n- Ablation studies demonstrate the gains in performance of each component.\n- TPGNN achieved SoTA performance on 6 benchmark datasets, on both single-step and multi-step settings. \n- The paper is well written and clear.\n\nWeaknesses:\n- The model can only learn periodic correlations, as the coefficients of the polynomials are fixed between cycles. This potentially limits the model's advantages to settings with distinct periodic patterns. This might explain why TPGNN performs worst in Exchange, a dataset without clear seasonalities. \n- To produce multi-step forecasts, TPGNN uses an auto-regressive strategy. This strategy performance is worst than other methods (such as the direct strategy) on long-horizon forecasting, as 1. errors accumulate over time, leading to worse performance, and 2. longer inference times.\n- The paper claims the model achieves SoTA performance on the long-horizon setting; however, the horizons considered in the paper are far lower than most recent studies. For example, the Informer paper (and a whole body of literature) considers a multi-step forecast of 720 timestamps.\n- The paper does not present any time complexity analysis.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "X4oAlc_pgbp", "reviewer": "Reviewer_3dhS", "summary": "This paper introduces a Temporal Polynomial Graph Neural Network (TPGNN) for multivariate time series forecasting. TPGNN first models the overall correlation with a static matrix basis, and then constructs a matrix polynomial for each time step by a set of learnable time-varying coefficients and the matrix basis. The experimental results on several benchmark datasets show that TPGNN could outperform the baseline methods.", "questions": "1. Self-attention might be the simplest way to learn dynamic graph structures. How does it perform compared to TPGNN?\n2. What's the time complexity of TPGNN?\n", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The experimental results on PEMS datasets show that the proposed TPGNN could achieve state-of-the-art performance. \n2. The experimental results on the synthetic dataset show that TPGNN could approximate the underlying graph structure.\n3. The paper is clear and easy to follow.\n\n\nWeakness:\n1. The novelty of using matrix polynomial to approximate graph structure is limited, as it is quite similar to [1]. \n2. The experimental results on the single future step forecasting task show that the improvements are not significant for many metrics.\n3. Other weaknesses: please refer to the questions.\n\n[1] Chien, Eli, et al. \"Adaptive universal generalized pagerank graph neural network.\" arXiv preprint arXiv:2006.07988 (2020).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "HgnMuTsdWp1", "reviewer": "Reviewer_gX4A", "summary": "This paper focuses on multivariate time series forecasting based on correlation graphs between such data. The main motivation is that dynamic correlation can avoid the bias in the solution that approaches focusing on the static correlation graph operate. Leveraging this dynamic correlation graph, a GNN-based model is leveraged to find higher-order representations of the data. One key aspect of the paper is that is uses time-varying coefficients (later, I argue that it is not explicitly the case). Some theoretical comparisons on the graph-based component of the paper are given. Numerical result on several datasets show a good performance and a thorough abolition study supports the role of the different components.", "questions": "1- All work is based on correlation graphs to support forecasting. But in real multivariate time series, causation is often more important than correlation, especially in traffic networks. And since the correlation does not imply causation, the model presents a limitation in this regard. The authors should discuss this aspect int he paper and provide guidelines about it.\n\n2- Regarding the challenges of related works in the introduction. Point 1) about no variable dependence and using physical distance graphs. This is one approach to build the graph as the physical graph may provide additional information to aid the forecasting. But those methods could apply to any graph, even a similarity (KNN graph, correlation) and the likes. However, working with correlation graphs (or in general data-graphs) may not necessarily be beneficial. This is because both the graph and the model parameters are estimated from the same data, hence there is redundancy in the model. In this regard, the graph structure does not bring any additional information that is not present in the data themselves (as a road network would do) but it rather acts as bias (the type of graph) we choose to model the data. In this regard, the scientific challenge of current approaches are not well positioned.\n\n3- Following the above point, the fact that temporal data may be better represented by time-varying graphs is of more importance. The paper should however acknowledge and contrast the contribution also with alternatives coming from non-GNN but graph-based methods such as [R1, R2, R3] and references therein. Also there are also works on GNNs over dynamic graphs, e.g., [R4] and following works that refer to it. The same remark applies here as well. \n\n4-Wrt works [36, 35, 4] it is claimed that those models also work with a dynamic correlation among variables. And it is also claimed that their issues is that the learned graph is sensitive to the observation. Can you elaborate more on this, why it is the case. And also why in the proposed model does not suffer from it as the graph is also build from the observation. In my view, this is needed as the proposed approach is related to these works and this may entail the key contribution.\n\t4a) In general, it I given the impression in the introduction that one of the key novelties of this paper is to work with time varying graphs. But as acknowledged here and in comment 2 other works have already proposed this. In this regard, the paper introduction does not give merit to existing literature and does not detail entirely the key contribution of the paper wrt those alternatives.\n\n5- Related works on GNNs and PGFs. \n\t5a) The division of GNNs into spectral and spatial methods is misleading. While there is a track of record within the CS community to do so, recent works have indeed realised that all GNN approaches are spatial—maybe the only spectral one is the early work in [R5]. In fact, the GCN mentioned as a spectral method is actually spatial. It can be seen as a particular case of GraphSage or message passing where the aggregation is dictated by multiplying nodal features with the graph Laplacian.\n\t5b) The GCN is a particular case of [R6] that claimed to use Chebyshev polynomials but as realised recently they often learn coefficients not respecting the coefficient rules in the Chebyshev polynomials [R8]. In turn, since the GCN is just an order one polynomial, and a particular case of [R6], it is more appropriate to give as an example [R6].\n\t5c) Polynomial graph filters have been initially formalised in the field of graph signal processing [R9, R10]. Also GCN [12] and ChebNet [R6, R8] use polynomial graph filters in the form of Chebyshev polynomials [R11]. The work in [30] instead is a very particular case of polynomial filtering. The link between polynomial filtering and GNNs has been discussed in [R12] including the expression of GCNs and SGCs as such polynomials. Another broader category casting the aforementioned GNNs are particular instances of graph filtering can be found in [R13] and their use for spatiotemporal learning has been discussed in [R14, R15, R16].\n\t5d) Some encoder decoder structure for GNN-based learning in multivariate time series have been discussed in [R17, R18]. The paper should highlight the contribution wrt these works as they also focus on dynamic graphs within the encoder-decoder solution.\n\nWhile some of this discussion may not be central to the developed method, I feel it is propagating misleading information about the GNN architecture. The authors are in this regard requested to reorganise this part and highlight the differences in using PGFs wrt to alternatives that have used them for multi-variate time series forecasting.\n\n6- Method\n\n6a) Learning matrices E in (2) has a number of parameters Nc. Isn’t this too much and suffering the curse of dimensionality?\n\n6b) The graph filter with time-varying coefficients has been discussed for forecasting in [R14, R16]. Here the difference stems mainly on using a (partially) learnable matrix A as well. Please highlight the differences.\n\n6c) After (5): the use of “average result” yields a smoothing (or low pass filtering) of the spatiotemporal data; hence, while it can play a role in robustness it also affects performance. Limitations of this choice should be discussed. \n\n6d) From eq. (7), it is shown that the average coefficients are used. So the final model in the end is not strictly a time varying model. This comes as a surprise as up to this point is has been build up towards a method that was time varying. It is therefore needed to highlight this properly not only in the introduction but also when contrasting with related works. The model is basically some engineered form of a PGF applied per time stamp, where the coefficients are the same (they only differ in the embedding). This to some extent contradicts the motivation and the theme of the paper in the earlier parts, which should be re-organised to make this part explicit.\n\n6e) Why the decoder is not made graph-based? Can one then attribute the benefits to the graph-based solution proposed in the paper or to this non graph-based decoder? The motivation behind such a choice and role of the different components is unclear.\n\n7- Theoretical properties - Thm1 is not about the TPGNN but it is rather the ability of a graph filter wrt the adjacency matrix A to approximate a user-defined operator. Similar results have been already discussed in the field of graph signal processing; see e.g., [R9, R19]. This result instead is applied to every operator (G^t) and errors are summed. The polynomial order in fact does not have to be large enough, but should satisfy the Cayley-Hamilton theorem (see [R19]).\n\nWhile we could argue this result differs so some extend form that in the aforementioned works, I feel it is tangential to the method (TPGNN) as it does not account for several aspects of the method, e.g., (7) and the diffusion convolutional layer where these are embedded. Consequently, it is unclear if the TPGNN can indeed achieve perfect approximation and the provided theoretical properties reported do not support it.\n\n8- In Sec. 5.5. the definition of the normal distribution, \\sigma be a covariance matrix. Also it is said that the matrix signal X^(t) but the dimensions are those of a vector. I’m a bit confused here. In the same sentence it is also said that X^(t) depends on W^(t) but in the normal distribution it appears W^{(t-1)}. Are all these typos? If not considering the entries of X^(t) independent  and identically distributed seems like a bit limitation to me. Can the authors elaborate why it makes sense considering this way of generating the data?\n\nMinor comments\n- Sec. 3.1: The MTS data is a graph signal \\mathcal{G}… is a wrong statement as the symbol represents a set (i.e., the graph), while the graph signal is defined as the data on this graph [R9-R10]-R14-R16-R11.\n- Sec. 3.1.-If W^t is time varying, shouldn’t also \\mathcal{E} be a time varying set of edges? Or do you mean a set of fixed edges exist and only their weights changes?\n- “not independent“ -> dependent\n- Is any link between the embedding vectors e_ts in the paragraph after (4) and the embedding matrix E in (3)? Either way, please make this explicit.\n- In 3.2, Laplacians are indicated with bold L; in Thm.1 with bold G;\n- There is a typo in the body of Lemma 2: “mathbfG” \n- Are there enough data in the test set to have a significant fourth decimal digit (e.g., Tab2)\n\n\n[R1] Natali, Alberto, et al. \"Learning Time-Varying Graphs from Online Data.\" arXiv preprint arXiv:2110.11017 (2021).\n\n[R2] Shafipour, Rasoul, et al. \"Identifying the topology of undirected networks from diffused non-stationary graph signals.\" IEEE Open Journal of Signal Processing 2 (2021): 171-189.\n\n[R3] \t.\tB.Zaman,L.M.L.Ramos,D.Romero,andB.Beferull-Lozano,“Online  topology identification from vector autoregressive time series,” IEEE Transactions on Signal Processing, vol. 69, pp. 210–225, 2021. \n\n[R4] Rossi, E., Chamberlain, B., Frasca, F., Eynard, D., Monti, F., & Bronstein, M. (2020). Temporal graph networks for deep learning on dynamic graphs. arXiv preprint arXiv:2006.10637.\n\n[R5] Bruna, J., Zaremba, W., Szlam, A., & LeCun, Y. (2013). Spectral networks and locally connected networks on graphs. arXiv preprint arXiv:1312.6203.\n\n[R6] Defferrard, Michaël, Xavier Bresson, and Pierre Vandergheynst. \"Convolutional neural networks on graphs with fast localized spectral filtering.\" Advances in neural information processing systems 29 (2016).\n\n[R8] He, Mingguo, Zhewei Wei, and Ji-Rong Wen. \"Convolutional Neural Networks on Graphs with Chebyshev Approximation, Revisited.\" arXiv preprint arXiv:2202.03580 (2022).\n\n[R9] Sandryhaila, Aliaksei, and José MF Moura. \"Discrete signal processing on graphs.\" IEEE transactions on signal processing 61.7 (2013): 1644-1656.\n\n[R10] Shuman, David I., et al. \"The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains.\" IEEE signal processing magazine 30.3 (2013): 83-98.\n\n[R11] Shuman, David I., et al. \"Distributed signal processing via Chebyshev polynomial approximation.\" IEEE Transactions on Signal and Information Processing over Networks 4.4 (2018): 736-751.\n\n[R12] Gama, Fernando, et al. \"Graphs, convolutions, and neural networks: From graph filters to graph neural networks.\" IEEE Signal Processing Magazine 37.6 (2020): 128-138.\n\n[R13] Isufi, Elvin, Fernando Gama, and Alejandro Ribeiro. \"EdgeNets: Edge varying graph neural networks.\" IEEE Transactions on Pattern Analysis and Machine Intelligence (2021).\n\n[R14] Isufi, Elvin, and Gabriele Mazzola. \"Graph-time convolutional neural networks.\" 2021 IEEE Data Science and Learning Workshop (DSLW). IEEE, 2021.\n\n[R15] Hadou, Samar, Charilaos I. Kanatsoulis, and Alejandro Ribeiro. \"Space-time graph neural networks.\" arXiv preprint arXiv:2110.02880 (2021).\n\n[R16] Isufi, Elvin, et al. \"Forecasting time series with varma recursions on graphs.\" IEEE Transactions on Signal Processing 67.18 (2019): 4870-4885.\n\n[R17] Sanchez-Gonzalez, Alvaro, et al. \"Learning to simulate complex physics with graph networks.\" International Conference on Machine Learning. PMLR, 2020.\n\n[R18] Pfaff, Tobias, et al. \"Learning mesh-based simulation with graph networks.\" arXiv preprint arXiv:2010.03409 (2020).\n\n[R19] Segarra, Santiago, Antonio G. Marques, and Alejandro Ribeiro. \"Optimal graph-filter design and applications to distributed linear network operators.\" IEEE Transactions on Signal Processing 65.15 (2017): 4117-4131.", "limitations": "see above in the questions", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n+ Works on dynamic graphs for forecasting rather than static, which is a less exposed area;\n+ Establishes links between;\n+ Numerical results are quite strong and support the method;\n+ Some theoretical results about the role of the graph filter (not of all the method) are given;\n\nWeaknesses\n- The paper over claims its contribution as proposing learning solutions over time varying graphs; while later on discusses that there exist prior work on learning over time-varying graphs;\n- Related work are rather limited and discusses mainly some baseline methods in GNN but misses several recent works on polynomial filtering for MTS; hence, the specific contribution of the paper is unclear and not well positioned, consequently, its novelty is lower than claimed.\n- The paper focuses entirely on correlation as the main argument to aid forecasting, bypassing any discussion related to causation; hence, limitations of the approach are not thoroughly discussed;\n- The provided theoretical result are tangential to the method developed and rather focused on the graph filter but not of the overall solution; \n- It is unclear if the benefits comes from the graph-based encoder with all the dynamics or from the non-graph based decoder.\n\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "3d3Spev6GfS", "reviewer": "Reviewer_U7ug", "summary": "The paper presents a novel framework for multivariate time series forecasting in the context of Graph Neural Networks (GNN). The aim of the work is to take into account the variable dependence which can evolve temporally.   To tackle the issue, the authors propose to use a dynamic adjacency matrix inside the GNN process. This matrix corresponds to a polynom of an initial adjacency matrix where the coefficients are learned from the data and depend on the timestamp.  The initial adjacency matrix is computed from the data following previous works and can integrate previous knowledge. A hypothesis of periodicity is considered in order to obtain a finite number of polynomial coefficients. The computed dynamic adjacency matrix is then used in a Graph Convolutional network to obtain the encoding module. The decoder uses a self-attention mechanism to forecast in a auto-regressive way the future of the time series. The authors propose a theorem to prove the correctness of the estimation of the adjacency matrix.  An extensive experimental part compares the proposed approach to several SOTA baselines and presents a complete ablation study. Finally, experiments on artificial (and real) data show the effectiveness of the proposed module to learn the graph correlation structure. \n\n", "questions": "From what I understand, the initial adjacency matrix is computed from embeddings that are not related to the learning process. It is correct? Do think it is possible to learn it in an end-to-end way?", "limitations": "NA", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* The paper is well written, the SOTA is clearly stated and the work is well positioned wrt to previous works. \n* The model is clearly presented and illustrated\n* The experimental part is very well designed, with exhaustive experiments (comparison to SOTA models, ablation study wrt all the aspects of the model,  analysis of the captured correlation,..).\n\nWeaknesses :\n* The novelty is not great (but sufficient in my opinion)\n* The experimental section is quite overfilled, maybe some results can be put to the appendix to give more space to introduce the datasets for instances.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept