FourierGNN: Rethinking Multivariate Time Series Forecasting from a Pure Graph Perspective
Authors: Kun Yi
Qi Zhang
Wei Fan
Hui He
Liang Hu
Pengyang Wang
Ning An
Longbing Cao
Zhendong Niu
Venue: NeurIPS 2023 poster (2023)
Keywords: multivariate time series forecasting
fourier space

Abstract: Multivariate time series (MTS) forecasting has shown great importance in numerous industries. Current state-of-the-art graph neural network (GNN)-based forecasting methods usually require both graph networks (e.g., GCN) and temporal networks (e.g., LSTM) to capture inter-series (spatial) dynamics and intra-series (temporal) dependencies, respectively. However, the uncertain compatibility of the two networks puts an extra burden on handcrafted model designs. Moreover, the separate spatial and temporal modeling naturally violates the unified spatiotemporal inter-dependencies in real world, which largely hinders the forecasting performance. To overcome these problems, we explore an interesting direction of directly applying graph networks and rethink MTS forecasting from a pure graph perspective. We first define a novel data structure, hypervariate graph, which regards each series value (regardless of variates or timestamps) as a graph node, and represents sliding windows as space-time fully-connected graphs. This perspective considers spatiotemporal dynamics unitedly and reformulates classic MTS forecasting into the predictions on hypervariate graphs.
 Then, we propose a novel architecture Fourier Graph Neural Network (FourierGNN) by stacking our proposed Fourier Graph Operator (FGO) to perform matrix multiplications in Fourier space. FourierGNN accommodates adequate expressiveness and achieves much lower complexity, which can effectively and efficiently accomplish {the forecasting}. Besides, our theoretical analysis reveals FGO's equivalence to graph convolutions in the time domain, which further verifies the validity of FourierGNN. Extensive experiments on seven datasets have demonstrated our superior performance with higher efficiency and fewer parameters compared with state-of-the-art methods. Code is available at this repository: https://github.com/aikunyi/FourierGNN.

FourierGNN: Rethinking Multivariate Time Series Forecasting from a Pure Graph Perspective
Kun Yi', Qi Zhang?, Wei Fan Hui He', Liang Hu?, Pengyang Wang' Ning An², Longbing Cao Zhendong Niu
Beijing Institute of Technology. "Tongji University, 'University of Oxford University of Macau, 'HeFei University of Technology. MMacquaiie University [yikun, hehui617, zniu] J @bit.edu.cn, zhangqi cs ees@toggj.edu weifan. oxford @ gmail.com railmilk @ gomil.com, pywang @ um.edu.mo, ning.g gnan @ acm.org, longbing cao @ mq.edu.au
Abstract
Multivariate time series (MTS) forecasting has shown great importance nu- merous industries. Current state-of-the-art graph neural network (GNN)-based forecasting methods usually require both graph networks (e.g.. GCN) and temporal networks (e.g., LSTM) to capture inter-series (spatial) dynamics and intra-series (temporal) dependencies, respectively. However, the uncertain compatibility of the networks puts an extra burden on handcrafted model designs. Moreover, the separate spatial and temporal modeling naturally violates the unified spatiotemporal inter-dependencies in real world, which largely hinders the forecasting performance. To overcome these problems, we explore interesting direction of directly apply- ing graph networks and rethink MTS forecasting from a pure graph perspective. We first define novel data structure, hypervariate graph, which regards each series value (regardless of variates or timestamps) as a graph node, and represents sliding windows as space-time fully-connected graphs. This perspective considers spa- tiotemporal dynamics unitedly and reformulates classic MTS forecasting into the predictions hypervariate graphs. Then, we propose a novel architecture Fourier Graph Neural Network (FourierGNN) by stacking our proposed Fourier Graph Operator (FGO) to perform matrix multiplications in Fourier space. FourierGNN accommodates adequate expressiveness and achieves much lower complexity, which can effectively and efficiently accomplish the forecasting. Besides, our thcoretical analysis reveals FGO's ' equivalence to graph convolutions in the time do- main, which further verifies the validity of FourierGNN. Extensive experiments seven datasets have demonstrated our superior performance with higher efficiency and fewer parameters compared with state-of-the-an methods. Code is available at this repository: https:// / thub, com/ aawaaai//uouuireeeaaar/r/r//
Introduction
Multivariate time series (MTS) forecasting plays important role in numerous real-world scenarios, such as traffic flow prediction in transportation systems [ 2], temperature estimation in weather forecasting 3 4 and electricity consumption planning in the energy market [5,0 [5,66, etc. In MTS forecasting, the core challenge to model intra-series (temporal) dependencies and simultaneously capture inter-series (spatial) correlations. Existing literature has primarily focused on the tempo- ral modeling and proposed several forecasting architectures, including Recurrent Neural Network (RNN)-based methods (e.g.. DeepAR (7),, Convolution Neural Network (CNN)) methods (e.g., Temporal Convolution Network and more recent Transformer-ban methods (e.g.. Informer
"Corresponding author
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

In addition, another branch of MTS forecasting methods has been developed to not only model temporal dependencies but also places emphasis on spatial correlations. The most representative methods are the emerging Graph Neural Network (GNN)-based approaches that have achieved mate-of-the-and performance in the MTS forecasting task.
and Autoformer [4].
I0] 2
Previous GNN-based forecasting methods (e.g., STGCN [12] and FAMP-S2GCNets (TI heavily rely on a pre-defined graph structure to specify the spatial correlations, which as a matter of fact cannot capture the spatial dynamics, i.e., the time-evolving spatial correlation patterns, Later advanced
2 can automatically learn inter-series correlations and accordingly model spatial dynamics without pre-defined priors, but almost all of them are designed by stacking graph networks (e.g.. GCN and GAT) to capture spatial dynamics and temporal networks (e.g., LSTM and GRU) to capture temporal dependencies. However, the uncertain compatibility of the graph networks and the temporal networks puts extra burden on handcrafted model designs, which hinders the forecasting performance. Moreover, the respective modeling for the two networks separately learn spatial/tempraa correlations, which naturally violate the real-world unified spatiotemporal inter-dependencies. In this paper, we explore opposite direction of directly applying graph networks for forecasting and investigate an interesting question: can pure graph networks capture spatial dynamics and temporal dependencies even without temporal networks?
approaches (e.g., StemGNN [TO], MTGNN [3), AGCRN
To answer this question, we rethink the MTS forecasting task from a pure graph perspective. We start with building new data structure, hypervariate graph, to represent time series with a united view of spatial/temporal dynamics. The core idea of the hypervariate graph is to construct a space-time time fully-connected structure. Specifically, given a multivariate time series window (say input window) X, E RNxT at timestamp 1, where N is the number of series (variates) and T is the length of input window, we construct corresponding hypervariate graph structure represented as G.T = (XT AT). which is initialized as a fully-connected graph of NT nodes with adjacency matrix A," E NIXNN
and node features X7 E NTx1 by regarding each value xx(") E .R. (variate at step 1) of input window as a distinct node of a hypervariate graph. Such a special structure design formulates both intra- and inter-series correlations of multivariate series pure node-node dependencies in the hypervariate graph. Different from classic formulations that make spatial-correlated graphs and learn dynamics in a two-stage (spatial and temporal) process [3, our perspective views spatiotemporal correlations as a whole. It abandons the uncertain compatibility of spatial/temporal modeling. constructs adaptive space-time dependeeen,,,,,,, and brings up higher-resolution fusion across multiple variates and timestamps in MTS forecasting.
Then, with such graph structure, the multivariate forecasting can be originally formulated into the predictions on the hypervariate graph. However, the node number of the hypervariate graph increase with the number of series (N) and the window length (7), leading to graph of large order and size. This could make classic graph networks (e.g., GCN [14], GAT (15) computationally expensive (usually with quadratic complexity) and suffer from optimization difficulty in obtaining accurate node representations [6]. To this end, we propose a novel architecture, Fourier Graph Neural Network (FourierGNN), for MTS forecasting from pure graph perspective. Specifically, FourierGNN is built upon our proposed Fourier Graph Operator (FGO), which as a replacement of classic graph operation units (c.g., convolutions), performs matrix multiplications in Fourier space of graphs By stacking FGO layers in Fourier space, FourierGNN can accommodate adequate learning expressiveness and in the mean time achieve much lower complexity (Log-linear complexity), which thus can effectively and efficiently accomplish MTS forecasting. Besides, we present theoretical analysis to demonstrate that the FGO is equivalent to graph convolutions in the time domain, which further explains the validity of FourierGNN.
Finally, we perform extensive experiments seven real-world benchmarks. Experimental results demonstrate that FourierGNN achieves an average of more than 10% improvement in accuracy compared with efficiency, which has about 14.6% less costs in training time and 20% less parameter volumes, compared with most lightweight GNN-based forecasting methods.
methods. In addition, FourierGNN achieves higher forecasting
2 Related Work
Graph Neural Networks for Multivariate Time Series Forecasting Multivariate time series (MTS) have embraced GNN due to their best capability of modeling structural dependencies between variates
[7
2
13
12
18 19]. Most of these models, such as STGCN [12), DCRNN (18),

---

and TAMP-S2GCNets [. require a pre-defined graph structure which is usually unknown in most cases. For this limitation, some studies enable to automatically learn the graphs by the inter-
series correlations, e.g., by node similarity [20 2 17 or self-attention mechanism [0] However,
these methods always adopt a graph network for spatial correlations and temporal network for temporal dependencies separately [20] 17 TO For example, AGCRN [2) use a GCN [14 and
GRU [21], GraphWaveNet [17 use a GCN and a TCN [8, etc. In this paper, we propose an unified spatiotemporal formulation with pure graph networks for MTS forecasting.
Multivariate Time Series Forecasting with Fourier Transform Recently, many MTS forecasting
models have integrated the Fourier theory into deep neural networks (22 23 For instance. SFM 224
decomposes the hidden state of LSTM into multiple frequencies by Discrete Fourier Transform (DFT). mWDN [25] decomposes the time series into multilevel sub-series by discrete wavelet decomposition (DWT) and feeds them to LSTM network. ATEN (66 proposes a Discrete Fourier Transform- based block to capture dynamic and complicated periodic patterns of time series data. FEDformer 277 proposes Discrete Fourier Transform-basee attention mechanism with low-rank approximation in frequency. While these models only capture temporal dependencies with Fourier Transform, StemGNN (TO) takes the advantages of both spatial correlations and temporal dependencies in the spectral domain by utilizing Graph Fourier Transform (GFT) to perform graph convolutions and Discrete Fourier Transform (DFT) to calculate the series relationships.
3 Problem Definition
Given the multivariate time series input, i.e., the lookback window X, = [ sy] E RX at timestamps with the number of series (variates) N and the lookback window size T, where Ie E IN denotes the multivariate values of series at timestamp t. Then, the multivariate time series forecasting task is to predict the next timestamps Y; [i+11 .... T[+r] E NN based on the historical T observations X, = [ 22... The forecasting process can be given by:
Y = (X.) =
where Y; are the predictions corresponding to the ground truth Y, The forecasting function is denoted as Fe parameterized by 0. In practice, many MTS forecasting models usually leverage a graph network (assume parameterized by 0g) to learn the spatial dynamics and temporal network (assume Thus, the parameterized by 0,) to learn the temporal dependencies, respectively [17 2 original definition of Equation ( can be rewritten to:
Y, = Fo (X.)) = Fe o, (I1-T+ æz.))
where original parameters are exposed to the parameters of the graph network 0g and the temporal network 0g to make prediction based on the learned spatial-temporal dependencies.
4 Methodology
In this section, we elaborate on our proposed framework: First, we start with our pure graph formulation with novel hypervariate graph structure for MTS forecasting in Section 4.1 Then, we illustrate the proposed neural architecture, Fourier Graph Neural Network (FourierGNN), for
this formulation in Section 4.2 Besides, theoretically analyze FourierGNN to demonstrate its architecture validity, and also conduct complexity analysis to show its efficiency. Finally, we introduce certain inductive bias to instantiate FourierGNN for MTS forecasting in Section 4.3
4.1 The Pure Graph Formulation
To overcome the uncertain compatibility of the graph network and the temporal network as afore- mentioned in Section [ and learn the united spatiotemporal dynamics, we propose pure graph formulation that refines Equation (2) by a novel data structure, hypervariate graph, for time series. Definition 1 (Hypervariate Graph). Given multivariate time series window as input X, E NXT of N variates at timestamp t, we construct hypervariate graph of NT nodes, G. = =xf Af), by regarding each element of X, one node of G, such that X E NTx1 stands for the node feature and AS E NT
NT is the adjacency matrix initialized make Gt a fully-connected graph.
3

---

Since the prior graph structure is usually unknown in most multivariate time series scenarios [T0 2 [3]. and the el- ements of X, are spatially or temporally correlated with each other because of time lag effect [28], we assume all nodes in the hypervariate graph G, are fully-connected. The hypervariate graph Gr contains NT nodes representing the values of each variate at each timestamp in Xx, which can learn a high-resolution representation across timestamps and variates (more explanations of the hypervariate graph can be seen in Appendix (.T). [.I). We present an example hy- pervariate graph of three time series in Figure | Thus, with such a data structure, we can reformulate the multivariate time series forecasting task into the predictions the hypervariate graphs, and accordingly rewrite Equation (2) into:
Input Window
Time
Hypervariate Graph
Figure 1: Illustration of hypervariate graph with three time series. Each value in the input window is considered as node of the graph.
Y, :- Fng (X9, A9)
where Og stands for the network parameters for hypervariate graphs. With such formulation, can view the spatial dynamics and the temporal dependencies from an united perspective, which benefits modeling the real- world spatiotemporal inter-dependencies.
4.2 FourierGNN
Though the pure graph formulation can enhance spatiotemporal modeling, the order and size of hypervariate graphs increase with the number of variates N and the size of window T, which makes classic graph networks (e.g., GCN [4] and GAT (15) computationally expensive (usually quadratic complexity) and suffer from optimization difficulty in obtaining accurate hidden node representations []]. In this regard, we propose an efficient and effective method, FourierGNN, for the pure graph formulation. The main architecture of FourierGNN is built upon our proposed Fourier Graph Operator (FGO), a learnable network layer in Fourier space, which is detailed as follows.
Definition 2 (Fourier Graph Operator). Given graph G = (X, A) with node features X E Rn and the adjacency matrix E 1 where n is the number of nodes and is the number of features, we introduce weight matrix W E gdxd to acquire tailored Green's 's kernel k [n]] [n]] - Bdxd
with k j] := Asj W and kli,.]] = j We define SA,W := F(R) E Cnxddd as a Fourier Graph Operator (FGO), where F denotes Discrete Fourier Trunsform (DFT).
According to the convolution theorem [29] (see Appendix B we can write the multiplication between F(X) and FGO SA, in Fourier space as:
F(X)F(s) = F((X b)(l = F XbI - 51) - F
Xiis(i,,). 1=1
Vi E [n]
j=1
where (X x]] denotes the convolution of X and K. As defined x[i.j] As W, it yields
Ej= Xljkk = - XDWW = AXW. Accordingly, we can get the convolution equation:
F(X)SAW F(AXW).
(5)
In particular, turning case of the fully-connected hypervariate graph, we adopt a n-invariant FGO S E Cdxd that has a computationally low cost compared to previous Xaxddd We provide more details and explanations in Appendix C.2
From Equation 5)) we can observe that performing the multiplication between F(X) and FGO S in Fourier space corresponds to graph shift operation (i.e., a graph convolution) in the time domain 20 Since the multiplications in Fourier space (O(n) have much lower complexity than the above shift operations (O(n²) in the time domain (See Complexity Analysis below), it motivates us to develop a highly efficient graph neural network in Fourier space.
To this end, we propose the Fourier Graph Neural Networks (FourierGNN) based on FGO. Specifi- cally, by stacking multiple layers of FGOs, we can define the K-layer Fourier graph neural networks given a graph G (X, A) with node features X E xxd and the adjacency matrix A E R"x* as:
K
FourierGNN =
(F())S + bz), Sux IIs, S.
(6)
k=
4

---

Herein, St is the FGO in the k-th layer, satisfying = the weights and Ag E R=*" corresponding to the k-th adjacency matrix sharing the same sparsity pattern of A, and by E Cd are the complex-valued biases parameters; F stands for Discrete Fourier Transform; a is the activation function. In particular, So. Wo. Ag are the identity matrix, and we adopt identical activation at k = O to obtain residual F(X). All operations in FourierGNN are performed in Fourier space. Thus, all parameters, i.c. {Sx, by 1K km= are complex numbers.
with W& E R being
The core operation of FourierGNN is the summation of recursive multiplications with nonlinear activation functions. Specifically, the recursive multiplications between F(X) and S, i.e., F(X))(x: are equivalent to the multi-order convolutions on the graph structure (see Theoretical Analysis below). Nonlinear activation functions are introduced address the capability limitations of modeling nonlinear information diffusion on graphs in the summation.
We theoretically analyze the effectiveness and interpretability of FourierGNN and verify the validity of its architecture. For convenience, we exclude the non-linear activation function a and learnable bias parameters from Equation (6). and focus on F(X)S
Theoretical Analysis
Proposition 1. Given a graph G (X, A) with node features X E Rnadd and adjacency matrix A E Rax", the recursive multiplication of FGOs in Fourier space is equivalent to multi-order convolutions in the time domain:
k (F())Su = X Su.k = II S. A km
0
k
II A. Work = II W 1=k
(7)
2m0
where Ao, Sa, Wo are the identity matrix, Ag E TR corresponds to the k-th diffussion step sharing the same sparsity pattern of A, W& RRdd is the k-th weight matrix, Sy Cd is the k-th FGO satisfying F(AxXW;, F(X)Sk, and F and F-2 denote DFT and its inverse, respectively.
In the time domain, operation X adopts different weights W₂ E Rdxd to weigh the information of different neighbors in different diffusion orders, beneficial to capture the extensive dependencies on graphs [20, 30 B1. This indicates FourierGNN is expressive in modeling the complex correlations among graph nodes, i.e., spatiotemporal dependencies in the hypervariate graph. The proof of Proposition [ and more explanations of FourierGNN are provided in Appendix C.3
Complexity Analysis The time complexity of F(X)S is lon + ndf), which includes the Discrete Fourier Transform (DFT), the Inverse Discrete Fourier Transform (IDFT), and the matrix multiplication in the Fourier space. Comparatively, the time complexity of the equivalent operations of F(X)S in the time domain, i.e., AXW, is O(n2d + nd*). Then, as a K Koorder summation of a recursive multiplication of F, FourierGNN, achieves the time complexity of O(dd n + Kndd), including DFT and IDFT, and the recursive multiplication of FGOs. Overall, the Log-linear O(n log n) complexity makes FourierGNN much more efficient.
FourierGNN vs Other Graph Networks We analyze the connection and difference between our FourierGNN with GCN [14] and GAT [15). From the complexity perspective, FourierGNN with lineli complexity shows much higher efficiency than GCN and GAT. Regarding the network architecture, we analyze them from two main perspectives:
(1) Domain. GAT implements operations in the time domain, while GCN and FourierGNN are in Fourier space. However, GCN achieves the transformation through the Graph Fourier Transform (GFT), whereas FourierGNN utilizes the Discrete Fourier Transform (DFT). (2) Information diffusion: GAT aggregates neighbor nodes with varying weights to via attention mechanisms. FourierGNN and GCN update node information via convoluting neighbor nodes. Different from GCN, FourierGNN assigns varying importance to neighbor nodes in different diffusion steps. We provide a detailed comparison in Appendix D
4.3 Multivariate Time Series Forecasting with FourierGNN
In this section, we instantiate FourierGNN for MTS forecasting. The overall architecture of our model is illustrated in Figure 2 Given the MTS input data X, RNT first construct a fully-connected hypervariate graph G. = (Xf AAA)) with X² E NTx] and A [1]mx>, Then, we project X into node embeddings X E R Xx by assigning d-dimension vector for each node using an
embedding matrix Es E I8 1xd i.c.. X² X² x Es.
5

---

Fourier G Graph Neural Network
4
Sg FGO
Sy. FGO
Output
FGO
14
6-- A
Hypervariste Graph
Time Domain
Fourler Space
Time Domaln
The network architecture of MTS forecasting with FourierGNN (blue characters denote complex values, such as X² S.). Given the hypervariate graph G (x . AA),, we I) embed nodes of g E RNTx1 to obtain node embeddings X NT'xx 2) feed embedded hypervariate graphs to FourierGNN: (i) transform X with DFT to X E CNxxx (ii) conduct recursive multiplications and make summation to output y (iii) transform y back to time domain by IDFT, resulting in Y E R NTNx 3) generate 7-step predictions Y, E R NxT via feeding Y to fully-connected layers.
Figure 2:
Subsequently, to capture the spatiotemporal dependencies simultaneously. we aim to feed multiple embeded hypervariate graphs with X to FourierGNN, First, we perform Discrete Fourier Transform (DFT) FF on each discrete spatio-temporal dimension of the embeddings X and obtain the frequency output X == F(X{) E CNTxd Then, we perform a recursive multiplication between X," and FGOs Sp:k in Fourier space and output the resulting representations y as:
y = (ourierGNN(X; AA)
Σ k=0
(F(( S + bx), So.k II S
(8)
i=0
Then D/ are transformed back to the time domain using Inverse Discrete Fourier Transform (IDFT) F-1, which yields Y == F= (F-1(19) E NTx.
Finally, according the FourierGNN output Y which encodes spatiotemporal anter-dependenciss we use two layer feed-forward networks (FFN) (see Appendix E.4 for more details) to project it onto future steps, resulting in Y, (Y)(Y?) e Nxx
5
Experiments
To evaluate the performance of FourierGNN, we conduct extensive experiments on seven real- world time series benchmarks to compare with state-of-the-art graph neural network-based methods.
5.1 Experimental Setup
Datasets. We evaluate our proposed method on seven representative datasets from various application scenarios, including traffic, energy, web traffic, clectrocardiogram, and COVID-19. All datasets are normalized using the min-max normalization. Except the COVID-19 dataset, we split the other datasets into training, validation, and test sets with the ratio of 7:2:1 in chronological order. For the COVID-19 dataset, the ratio 6:2:2. More detailed information about datasets are in Appendix E
Baselines. We conduct comprehensive comparison of the forecasting performance between our FourierGNN and several representative and tfate-of-theeart (SOTA) models on the seven datasets, including classic method VAR (32), deep learning based models such as SFM (24), LSTNet (3]
TCN 8,, DeepGI.O and CoST [36]. also compare FourierGNN against GNN-based models like Graph WaveNet 17 StemGNN 10) MTGNN 13 , and AGCRN 22] and two representative Transformer-Dasee models like Reformer [35] and Informer 9 as well as two frequency enhanced Transformer-based models including Autoformer 4 and FEDformer (2). In addition,
compare
FourierGNN with SOTA models such as AAMPsssGCNets M. DCRNN [8], and STGCN ( which require pre-defined graph structures. Please refer to Appendix for more implementation details of the adopted baselines.
Experimental Settings. All experiments are conducted in Python using Pytorch 1.8 [37] (except for SFM which uses Keras) and performed on single NVIDIA RTX 3080 10G GPU. Our model is trained using RMSProp with learning rate of 10-5 and MSE (Mean Squared Error) as the loss function. The best parameters for all comparative models are chosen through careful parameter tuning on the validation set. We use Mean Absolute Errors (MAE), Root Mean Squared Errors (RMSE), and

---

Table 1: Overall performance of forecasting models the six datasets.
Datasets
Solar RMSE
Wiki
Traffic
Models
MAE
MAPE(%)
MAE
RMSE
MAPE(%)
MAE
RMSE
MAPE(%)
VAR
0.184
0.234
$77.10
0.057
0.094
96.58
0.535
1.133
550.12
SFM 24
0.161
0.283
362.89
0.081
0.156
104.47
0.029
0.044
59.33
LSTNet
33
0.148
0.200
132.95
0.054
0.090
118.24
0.026
0.057
25.77
TCN
8
0.176
0.222
142.23
0.094
0.142
99.66
0.052
0.067
DeepGi.0
0.178
0.400
346.78
0.110
0.113
119.60
0.025
0.037
33.32
Reformer
35
0.234
0.292
128.58
0.048
0.085
73.61
0,029
0.042
112.58
Informer
9
0,151
0.199
128.45
0.051
0.086
80.50
0,020
0.033
59.34
Autoformer
0.150
0.193
103.79
0.069
0.103
121.90
0.029
0.043
100.02
FEDformer
27
0.139
0.182
100.92
0.068
0.098
123.10
0.025
0.038
85,12
GraphWaveNet
1i7
0.183
0,238
603
0.061
1.5
136.12
0.013
0.034
33.78
StemGNN 10
0.176
0.222
128.39
0.190
0,255
117.92
0.080
0.135
64.51
MTGNN
0.151
0.207
122.96
29.53
AGCRN 2
0.123
0.214
353.03
0.044
0.079
78.52
0.084
0.166
31.73
FourierGNN
0.120
0.162
116.48
0.041
0.076
64.50
0.011
0.023
28.71
Datasets
ECG
Electricity
COVID-19
Models
MAE
RMSE
MAPE(%)
MAE
RMSE
MAPE(%)
MAE
RMSE
MAPE(%)
VAR
0.120
0.170
22.56
0.163
43.11
0.226
191.95
SFM 24
0.095
0.135
24.20
0.086
0.129
33.71
0.205
0.308
76.08
LSTNet
35
0.079
0.115
18.68
0.075
0.138
29.95
0.248
0.305
89.04
TCN
8
0,078
0.107
17.59
0.057
0.083
26.64
0.317
0.354
151.78
DeepGi.0
0.110
0.163
43.90
0.090
0.131
29.40
0.169
0.253
75.19
Reformer
35
0.062
0.090
13.58
0.078
0.129
33.37
0.152
0.209
132.78
Informer
9
0.056
0.085
11.99
0.070
0.119
32.66
0,200
0.259
155.55
Autoformer
0.055
0.081
11.37
0.056
0.083
25.94
0.159
0.211
136.24
FEDformer
27
0.055
0.080
11.16
0.055
0.081
25.84
0.160
0.219
134.45
GraphWaveNet
117
0.093
0.142
40.19
0.094
0.140
37.01
0.201
0.255
100.83
StemGNN 10
0.100
0.130
29.62
0.070
0.101
0.421
0.508
141.01
MTGNN
13
0.139
29.77
0.394
88.13
AGCRN
2
0.055
0.080
11.75
0.074
0.116
26.08
0.254
0.309
83.37
FourierGNN
0.052
0.078
10.97
0.051
0.077
24.28
0.123
0.168
71.52
Table Performance comparison under different prediction lengths on the COVID-19 dataset.
Length
6
12
Metries
MAPE(S)
RMSE
MAPE(R)
GrspeiWaeeNe
77
0.092
0.129
53.00
0.133
0.179
65.11
0.171
0.225
80.91
0.201
0.255
100.83
StemGNN 10
0.247
0.318
99.98
0.344
0.429
125.81
0.359
0.442
131.14
0.421
0.508
141.01
AGCRN g
0.130
0.172
76.73
0.171
0.218
79.07
0.221
0.277
82.90
0.251
0.309
83.37
MIGNN [0]
0.276
TAMP-820C Nesss
0.140
50.01
0.200
0.170
71.78
0.180
0.230
CoST [6
0.122
0.216
68.74
0.157
0.318
72.84
0.183
0.364
77.04
0.202
0.377
80.81
FourierGNN(ours)
0,071
0,103
61,02
0.093
0.131
65.72
0,109
0.148
69.59
0.123
0,168
71.52
Mean Absolute Percentage Error (MAPE) to measure the performance. The evaluation details are in Appendix E.3 and more experimental settings are in Appendix E.4
5.2 Main Results
We present the evaluation results with an input length of 12 and prediction length in Table M Overall, FourierGNN achieves new state-of-the-ard all datasets. On average, FourierGNN makes an improvement of 9.4% in MAE and 10.9% RMSE compared to the best-performing across all datasets. Among these baselines, Reformer, Informer, Autoformer, and FEDformer Transformer- based models that demonstrate competitive performance on Electricity and COVID- 19 datasets, as they excel at capturing temporal dependencies. However, they have limitations in capturing the spatial dependencies explicitly. Graph NeteNe,, MTGNN, StemGNN, and AGCRN are GNN-based models that show promising results Wiki, Traffic, Solar, and ECG datasets, primarily due to their capability to handle spatial dependencies among variates. However, they are limited in their capacity to simultaneously capture spatiotemporal dependencies. FourierGNN outperforms the baseline models since it can learn comprehensive spatiotemporal dependencies simultancously and attends time-varying dependencies among variates.
Multi-Step Forecasting To further evaluate the performance in multi-step forecasting, we com- pare FourierGNN with other GNN-based MTS models (including StemGNN [10], AGCRN (2).
7

---

Graph WaveNet [7]] MTGNN [3]. and TAMP-S2GCNed. [T] and representation learning model (CoST (6) on COVID-19 19 dataset under different prediction lengths, and the results are shown in Table 2 It shows that FourierGNN achieves an average 30.1% 1% and 30.2% improvement on MAE we include more experiments and analysis under different prediction lengths, and further compare FourierGNN with models that require pre-defined graph structures.
and RMSE respectively over the best baseline. In Appendix [
5.3 Model Analysis
Efficiency Analysis We investigate the parameter volumes and training time costs of FourierGNN, StemGNN [TO), AGCRN (2). Graph [17], and MTGNN [33] on two representative datasets, including the Wiki dataset and the Traffic dataset. The results reported in Table 3 showing the comparison of parameter volumes and average time costs over five rounds of experiments. In terms of parameters, FourierGNN cxhibits the lowest volume of parameters among the comparative models. Specifically, it achieves a reduction of 32.2% and 9.5% in parameters compared to on Traffic and Wiki datasets, respectively. This reduction is mainly attributed that FourierGNN has shared scale-free parameters for each node. Regarding training time, FourierGNN runs much faster than all baseline models, and it demonstrates efficiency improvements of 5.8% and 23.3% over the fast baseline Graph WaveNet on Traffic and Wiki datasets, respectively. Considering variate number of Wiki dataset is about twice larger than that of Traffic dataset, FourierGNN exhibits larger efficiency superiority with the baselines. These findings highlight the high efficiency of FourierGNN in computing graph operations and its scalability large datasets with extensive graphs, which is important for the pure graph formulation due to the larger size of hypervariate graphs with NT nodes.
Table 3: Comparisons of parameter volumes and training time costs on datasets Traffic and Wiki.
Traffic
Wiki
Models
Parameters
Training (s/epoch)
Parameters
Training (s/epoch)
StemGNN
1, 1060 140
185.86-42.222
4, 102, 406
1..9
MTGNN
707, 516
169.34
1, 1,533, 436
28.69:+0.83
AGCRN
749, 940
113.46+1.91
755, 740
2..48=1.011
Graph WaveNet
280, 860
105.38.11.24
292, 460
21.23
FourierGNN
190, 564
99.25+
264, 804
16.28=00.48
Ablation Study We perform an ablation study on the METR-LA dataset to assess the individual contributions of different components FourierGNN. The results, presented in Table validate the effectiveness of each component. Specifically, w/o Embedding emphasizes the significance of performing node embedding improve model generalization. w/o Dynamic FGO using the same FGO verifies the effectiveness of applying different FGOs in capturing time-varying dependencies. In addition, w/o Residual represents FourierGNN without the K 0 layer, while w/o Summation adopts the last order (layer) output, i.e., X' as the output of FourierGNN. These results demon- strate the importance of high-order diffusion and the contribution of multi-order diffusion. More results and analysis of the ablation study are provided in Appendix G.3
Table 4: Ablation study on METR-LA dataset.
metrics
w/o Embedding
w/o Dynamic FGO
w/o Residual
w/o Summation
FourierGNN
MAE
0.053
0.055
0.054
0.054
0.050
RMSE
0.116
0.114
0.115
0.114
0.113
MAPE(%)
86.73
86.69
86.75
86.62
86.30
5.4 Visualization
To gain better understanding of the hypervariate graph and FourierGNN in spatiotemporal modeling for MTS forecasting, We conduct visualization experiments on the METR-LA and COVID-19 datasets. Please refer to Appendix E.5 for more information on the visualization techniques used.
Visualization of temporal representations learned by FourierGNN temporal dependencies learning capability of FourierGNN, we visualize the temporal adjacency matrix of different variates. Specifically, we randomly select counties from the COVID-19 dataset and calculate the relations of 12 consecutive time steps for each county. Then, we visualize the
order to showcase the
8

---

(a) N=7
(b) N=18
(c) N=24
(d) N=29
(c) N=38
(f) N=45
gg) N=46
(h) N=55
Figure 3: The temporal adjacency matrix of eight variates on COVID-19 dataset.
adjacency matrix by heatmap, and the results are illustrated in Figure 3 where N denotes the index of the country (variate). It shows that FourierGNN learns distinct temporal patterns for each county. indicating that the hypervariate graph can encode rich and discriminative temporal dependencies.
Visualization of spatial representations learned by FourierGNN To investigate the spatial corre- lations learning capability of FourierGNN, we visualize the generated adjacency matrix based on the representations learned FourierGNN on the METR-LA dataset. Specifically, randomly select 20 detectors and visualize their corresponding adjacency matrix via a heatmap, as depicted in Figure By examining the adjacency matrix in con- junction with the actual road map, we ob- serve: 1) the detectors (7, 9, 11, 13, 18) are very close w.r.t. the physical dis- tance, corresponding to the high values of their correlations with each other in the heatmap; 2) the detectors have small overall correlation values since they are far from other detectors; 3) how- ever, compared with detectors 14 and 16, detector has slightly higher correla- tion values to other detectors, e.g., 7, 8, which because although they are far apart, the detectors 4, 7, 8, are the same road. The results verify that the hypervariate graph structure can represent highly interpretative correlations.
14 and 16
Figure 4: The adjacency matrix (right) learned by Fouri- erGNN and the corresponding road map (left).
Moreover, to gain a understanding of how FGO works, we visualize the output of each layer of FourierGNN, and the visualization results demonstrate that FGO can adaptively and effectively capture important patterns while removing noises to learn discriminative model. Further details can found in Appendix H.T Additionally, investigate the ability of FourierGNN capture time-varying dependencies among variates, we further visualize the spatial correlations at different timestamps. The results illustrate that FourierGNN can effectively attend to the temporal variability in the data. For more information, please refer to Appendix H.2
Conclusion Remarks
In this paper, we explore an interesting direction of directly applying graph networks for MTS forecasting from pure graph perspective. To overcome the previous separate spatial and temporal modeling problem, we build hypervariate graph, regarding each series value graph node, which considers spatiotemporal dynamics unitedly. Then, we formulate time series forecasting on the hypervariate graph and propose FourierGNN by stacking Fourier Graph Operator (FGO) to perform matrix multiplications in Fourier space, which can accommodate adequate learning expressiveness with much lower complexity. Extensive experiments demonstrate that FourierGNN achieves state- of-the-art performances with higher efficiency and fewer parameters, and the hypervariate graph structure exhibits strong capabilities to encode spatiotemporal inter-dependencies.

---

Acknowledgments and Disclosure of Funding
The work was supported in part by the National Key Research and Development Program of China under Grant 2020AAA0104900 and 8019YFB1406300 and National Natural Science Foundation of China under Grant 62072039 and 62272048.
References
[1] Bing Yu, Haoteng Yin, and Zhanxing Zhu. Spatio-temports graph convolutional networks: A deep learning framework for traffic forecasting. In IJCAI, pages 3634-6640, 2018.
[2] Lei Bai, Lina Yao, Can Li, Xianzhi Wang, and Can Wang. Adaptive graph convolutional recurrent network for traffic forecasting. In NeurIPS, 2020.
[3] Yu Zheng, Xiuwen Yi, Ming Li, Ruiyuan Li, Zhangqing Shan, Eric Chang, and Tianrui Li. Forecasting fineggrained air quality based on big data. In KDD, pages 2267-22777 2015.
[4] Haixu Wu, Jiehui Xu, Jianmin Wang, and Mingsheng Long. Autoformer: Decomposition transformers with auto-correlation for long-term series forecasting. In NeurlPS, pages 22419- 22430, 2021.
[5] Hui He, Qi Zhang, Simeng Bai, Kun Yi, and Zhendong Niu. CATN: cross attentive tree-aware network for multivariate time series forecasting. In AAAI, pages 4030 4038. AAAI Press, 2022.
[6] Wei Fan, Shun Zheng, Xiaohan Yi, Wei Cao, Yanjie Fu, Jiang Bian, and Tic- Yan Liu. DEPTS: deep expansion learning for periodic time series forecasting. In ICLR. OpenReview.net, 2022.
[7] David Salinas, Valentin Flunkert, Jan Gasthaus, and Tim Januschowski. Deepar: Probabilistic forecasting with autoregressive recurrent networks. International Journal of Forecasting, 36(3):1181-1199) 2020.
[8] Shaojie Bai, J. Zico Kolter, and Vladlen Koltun. An empirical evaluation of generic convolu- tional and recurrent networks for sequence modeling. CoRR, abs/1803.01271, 2018.
(9] Haoyi Zhou, Shanghang Zhang, Jieqi Peng, Shuai Zhang, Jianxin Li, Hui Xiong, and Wancai Zhang. Informer: Beyond efficient transformer for long sequence time-series forecasting. In AAAI, pages 11106-11113 1111, 2021.
[10] Defu Cao, Yujing Wang, Juanyong Duan, Ce Zhang, Xia Zhu, Congrui Huang, Yunhai Tong, Bixiong Xu, Jing Bai, Jie Tong, and Qi Zhang. Spectral temporal graph neural network for multivariate time-series forecasting. In NeurlPS, 2020.
[11) Yuzhou Chen, Ignacio Dooooiuu, Baris Coskunuzer, and Yulia Gel. TAMP-s2GCNets: Coupling time-aware multipersistence knowledge representation with spatio-supra graph con- volutional networks for time-series forecasting. International Conference on Learning Representations, 2022.
[12] Bing Yu, Haoteng Yin, and Zhanxing Zhu. Spatio-temporal graph convolutional networks: deep learning framework for traffic forecasting. In ISCAI, pages
2018.
[13] Zonghan Wu, Shirui Pan, Guodong Long, Jing Jiang, Xiaojun Chang, and Chengqi Zhang, Connecting the dots: Multivariate time series forecasting with graph neural networks. In KDD, pages 753-763, 2020.
[14] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR (Poster). OpenReview.net, 2017.
[15] Petar Velickovie, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio. Graph attention networks. CoRR,
2017.
[16] Kate Smith-Miles and Leo Lopes. Measuring instance difficulty for combinatorial optimization problems. Comput. Oper. Res., 39(5):875-889 2012.
10

---

[17] Zonghan Wu, Shirui Pan, Guodong Long, Jing Jiang, and Chengqi Zhang. Graph wavenet for deep ppatial-tempora graph modeling. IJCAL, pages 1907-1913, 2019.
[18] Yaguang Li, Rose Yu, Cyrus Shahabi, and Yan Liu, Diffusion convolutional recurrent neural network: Data-driven traffic forecasting. In ICLR (Poster), 2018.
[19] Leyan Deng. Defu Lian, Zhenya Huang, and Enhong Chen. Graph convolutional adversarial networks for spatiotemporal anomaly detection. IEEE Transactions on Neural Networks and Learning Systems, 33(6):2416-243) 2022.
[20] Gonzalo Matcos, Santiago Segarra, Antonio G. Marques, and Alejandro Ribeiro. Connecting the dots: Identifying network structure via graph signal processing. IEEE Signal Process. Mag.. 36(3):16-33, 2019.
[21] Kyunghyun Cho, Bart van Merrienboer, Çaglar Gülçehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using RNN encoder- decoder for statistical machine translation. In EMNLP, pages 1724-1734. ACI., 2014.
[22] Kun Yi, Qi Zhang, Longbing Cao, Shoujin Wang, Guodong Long, Liang Hu, Hui He, Zhendong Niu, Wei Fan, and Hui Xiong. A survey on deep learning based time series analysis with frequency transformation. CoRR, abs/2302.02113,, 2023.
[23] Tian Zhou, Ziqing Ma, Xue Wang, Qingsong Wen, Liang Sun, Tao Yao. Wotao Yin, and Rong Jin. Film: Frequency improved legendre memory model for long-term time series forecasting. 2022.
[24] Liheng Zhang, Charu C. Aggarwal, and Guo-Jun Qi. Stock price prediction via discovering multi fuqquecy trading patterns. In KDD, pages 2141-2144 2017.
[25] Jingyuan Wang, Ze Wang, Jianfeng Li, and Junjie Wu. Multilevel wavelet decomposition network for interpretable time series analysis. In KDD, pages 2437-2446, 2018.
[26] Zhangjing Yang. Weiwu Yan, Xiaolin Huang, and Lin Mei. Adaptive temporal- network for time-series forecasting. IEEE Truns. Knowl. Data Eng. 3444): 2022.
[27] Tian Zhou, Ziqing Ma, Qingsong Wen, Xue Wang, Liang Sun, and Rong Jin. FEDformer: Frequency enhanced decomposed transformer for long-term series forecasting. In ICML, 2022.
[28] William W. S. Wei. Time series analysis univariate and multivariate methods. Addison-Wesley. 1989.
[29] Y. Katznelson. An introduction to harmonic analysis. Cambridge University Press., 1970.
[30] Santiago Segarra, Gonzalo Mateos, Antonio G. Marques, and Alejandro Ribeiro. Blind identifi- cation graph filters. IEEE Trans. Signal Process., 65(5):1 141441115 1159, 2017.
[31] Elvin Isufi, Fernando Gama, and Alejandro Ribeiro. Edgenets: Edge varying graph neural networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021.
[32] Mark W. Watson. Vector autoregressions and cointegration. Working Paper Series, Macroeco- nomic Issues, 4, 1993.
[33] Guokun Lai, Wei-Cheng Chang, Yiming Yang, and Hanxiao Liu. Modeling long- and short-term temporal patterns with deep neural networks, In SIGIR, pages 95-104, 2018
[34] Rajat Sen, Hsiang-Fu Yu, and Inderjit S. Dhillon. Think globally, act locally: A deep neural network approach to high dith-iiieniionll time series forecasting. In NeurlPS, pages 4838 4847, 2019.
[35] Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. In ICLR, 2020.
[36] Gerald Woo, Chenghao Liu, Doyen Sahoo, Akshat Kumar, and Steven C. H. Hoi. Cost: Contrastive learning of disentangled seasonal-trend representations for time series forecasting. In ICLR. OpenReview.net, 2022.
11

---

[37] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward 7. Yang. Zachary Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In NeurlPS, pages
2019.
[38] Hoang Anh Dau, Anthony J. Bagnall, Kaveh Kamgar, Chin-Chia Michael Yeh. Yan Zhu, Shaghayegh Gharghabi, Chotirat Ann Ratanamahatana, and Eamonn J. Keogh. The UCR time series archive. IEEE CAA J. Autom, Sinica, (66):129311333 1305, 2019.
12

---

A
Notation
Table Notations
X
multivariate time series input at timestamps 1, X E RN
the multivariate values of N series at timestamp 1, 22 R.V the next timestamps of multivariate time series, Y; E R
2t
Y
Y
the prediction values of multivariate time series for next timestamps, Ý, E RN the number of series
N
T
the lookback window size
the prediction length multivariate time series forecasting the hypervariate graph, G. {X?, A.) attributed to x² the nodes of the hypervariate graph, X² RNTx1
G
X
Ag
the adjacency matrix G., A RNNTNN
s
the Fourier Graph Operator
d
the embedding dimension the embedding of Xº. X E RTxxd
x
xg
the spectrum of x X E CN
y
the output of FourierGNN, y E CNTxd the parameters of the graph network
0g
0.
the parameters of the temporal network
0g
the network parameters for hypervariate graphs
E
the embedding matrix, Eg IR 1xd
the kernel function
W
the weight matrix
b
the complex bias weights
F
Discrete Fourier Transform
F-1
Inverse Discrete Fourier Transform
the forecasting model
B Convolution Theorem
The convolution theorem 29 is one of the most important properties of the Fourier transform. states the Fourier transform of a convolution of two signals equals the pointwise product of their Fourier transforms in the frequency domain. Given signal æ(n] and filter [1]1), the convolution theorem can be defined as follows:
F((x + h) = F(x)
where (x [m] = D h[m]z[(n m)N] denotes the convolution of x and h, (n m)) denotes (n - m) modulo N, and F(r) and F(h) denote discrete Fourier transform a(m) and h(m) respectively.
13

---

C Explanations and Proofs
C.1 The Explanations of the Hypervariate Graph Structure
Note that the time lag effect between time-series variables is common phenomenon in real-world multivariate time series scenarios, for example, the time lag influence between financial assets (e.g. dollar and gold) of a portfolio. It is beneficial but challenging to consider dependencies between different variables under different timestamps.
The hypervariate graph connecting any two variables at any two timestamps aims to encode high- resolution spatiotemporal dependencies. embodies only the intra-series temporal dependencies (node connections of each individual variable), inter-series spatial dependencies (node connections under each single time step), and also the time-varying spatiotemporal dependencies (node con- nections between different variables at different time steps). By leveraging the hypervariate graph structure, can effectively learn the spatial and temporal dependencies. This approach is distinct from previous methods that represent the spatial and temporal dependencies separately using two network structures.
C.2 The Interpretation of n-invariant FGO
Why F(k) E (Cxxxxd From Definition we know that the kernel k defined as a matrix- valued projection, i..., x [n] x [m] + gdxa Note that we assume к is in the special case of the Green's s kernel, i.e., tramslation-invartie
kernel k(i, xli j]. Accordingly, can be reduced: K [m] + Rddd where we can parameterize F(x) with complex-valued matrix Caxdxd
What is n-invariant FGO? Turning consider a special case of k, i.e., a space-invariant kernel x(i j] =<e] with e being a constant scalar. Accordingly, we can parameterize FGO with a n--ivvariant complex- valued matrix Cd
case of the fully-connected hypervariate graph, we
The interpretation of n-iivariant FGO. An n-invariant FGO is similar to shared-weight convo- lution kernel or filter of CNNs that slide along ([r] x [n)) input features, which effectively reduces parameter volumes and saves computation costs. Note that although we adopt the same transforma- tion (i.e., the n--ivariiat FGO) over NT frequency points, we embed the raw MTS inputs in d-dimension distributive space beforehand and then perform FourierGNN over MTS embeddings, which can be analogized as convolution kernels/filters in each convolutional layer in CNNs. This ensure FourierGNN is able to learn informative features/patterns improve its model capacity (See the following analysis of the effectiveness of n--ivaariant FGO).
The effectiveness of n-invariant FGO. In addition, the n--nvariant parameterized FGO is empirically proven effective to improve model generalization and achieve superior forecasting performance (See the ablation study in Section 5.3 for more details). Although parameterizing F(k) E C"xdxd (i.e., an n-variint FGO) may be more powerful and flexible than the n--invariant FGO in terms of forecasting performance, it introduces much more parameters and training time costs, especially in case of multi-layer FourierGNN, and may obtain inferior performance due to inadequate training overfitting. As indicated in Table 6 the FourierGNN with the n--nvariant FGO achieves slightly better performance than that with the n-variant FGO on ECG and COVID-19 respectively. Notably, the FourierGNN with the variiaatt FGO introduces much larger parameter volume proportional to n and requires significantly more training time. In contrast, n-invariant FGO is n-agnostic and lightweight, which is a more wise and efficient alternative. These results confirm our design and verify the effectiveness and applicability of n--invariant FGO.
Table Comparison between FourierGNN models with n-invariant FGO and n-variant FGO on the ECG and CO datasets.
Datasets
Models
Parameters (M)
Training (s/epoch)
MAE
RMSE
MAPE (%)
nt-invariant
0.18
12.45
0.052
0.078
10.97
ECG
n-variant
82.96
104.06
0.053
0.078
11.05
n-invariant
1.06
0.62
0.123
0.168
71.52
COVID-19
n-variant
130.99
7.46
0.129
0.174
72.12
14

---

C.3 Proof of Proposition 1 and Interpretation of FourierGNN
Proposition 1. Given a graph G (X, with node features R=nd and adjacency matrix A Rax", the recursive multiplication of FGOs in Fourier space is equivalent to multi-order convolutions in the time domain:
F (F(()sok))))) = Ak.o So.k = II S. Ak.0 2=
II A. Work s=
II W ==0
where Au, Su, Wo the identity matrix, As E <R corresponds the k-th diffusion step sharing the same sparsity pattern of A, We E Rddd is the k-th weight matrix, Sy. E Caxd is the k-th FGO satisfying F(AxXWa) S(.)Sk, and F and F-1 denote DFT and its inverse, respectively.
Proof. The proof aims to demonstrate the equivalence between the recursive multiplication of FGOs in Fourier space and multi-order convolutions the time domain. According to F(Ax-WW) F(X)S; we expand the multi-order convolutions Ao. X Wo.k in the time domain using set of FGOs in Fourier space:
F(AKAK-1 ... A WK-1WK) = F(AK-I...AXTII WK-1)SK
WK-1)Wk)
FF(AK- -AR Ag W 1
=((AK22.. An WK-2)SK-1SK
F(X)S0 SK-1SK = =F(X)SU:K
(10)
where it yields F (F(((SSS): AKoo. with Su.k I1 SK,AK: II A and
Wo.k = II W. Proved.
Thus, the FourierGNN be rewritten (for convenience, exclude the non-linear activation function a and learnable bias parameters b):
K
F(X)Suk) = A&XW, + A1AAx + XWo.
(11)
k=0
From the right part of the above equation, we can observe that it assigns different weights to weigh the information of different neighbors in each diffusion order. This property enable FourierGNN to capture the complex correlations (i.e., spatiotemporal dependencies) in the hypervariate graph, which empirically verified our visualization experiments.
D Compared with Other Graph Neural Networks
Graph Convolutional Networks. Graph convolutional networks (GCNs) depend the Laplacian eigenbasis to perform the multi-order graph convolutions over given graph structure. Compared with GCNs, FourierGNN as efficient alternative to multi-order graph convolutions has three main differences: 1) No eigendecompositions or similar costly matrix operations are required. FourierGNN transforms the input into Fourier domain by discrete Fourier transform (DFT) instead of graph Fourier transform (GFT); 2) Explicitly assigning various importance to nodes of the same neighborhood with different diffusion steps. FourierGNN adopts different Fourier Graph Operators S in different diffusion steps corresponding to different dependencies among nodes; 3) FourierGN'N is invariant to the discretization N. T. It parameterizes the graph convolution via Fourier Graph Operators which are invariant to the graph structure and graph scale.
Graph Attention Networks. Graph attention networks (GATs) are non-spectral attention-based graph neural networks. GAT's use node representations calculate the attention weights (i.e., edge weights) varying with different graph attention layers. Accordingly, both GATs and FourierGNN do
15

---

not depend on eigendecompositions and adopt varying edge weights with different diffusion steps (layers). However, FourierGNN can efficiently perform graph convolutions in Fourier space. For complete graph, the time complexity of the attention calculation of K layers is proportional to K' where the number of nodes, while a K-layer FourierGNN infers the graph structure in Fourier space with the time complexity proportional to n log In addition, compared with GAT's that implicitly achieve edge-varying weights with different layers, FourierGNN adopts different FGOs in different diffusion steps explicitly.
E
Experiment Details
E.1
Datasets
We use seven public multivariate benchmarks for multivariate time series forecasting and these benchmark datasets are summarized in Table
Table 7: Summary of datasets.
Datasets
Solar
Wiki
Traffic
ECG
Electricity
COVID-19
METR-LA
Samples
3650
803
10560
5000
140211
335
34272
Variables
592
2000
963
140
370
55
207
Granularity
Ihour
Iday
Ihour
15min
1day
5min
Start time
01/01/2006
01/07/2015
01/01/2015
01/01/2011
01/02/2020
01/03/2012
Solar This dataset about solar power collected by National Renewable Energy Laboratory. We choose the power plant data points in Florida as the data set which contains 593 points. The data is collected from 2006/01/01 2016/12/31 with the sampling interval of every hour.
Wiki [34]:
This dataset contains a number of daily views different Wikipedia articles and is collected from 2015/7/1 to 2016/12/31. It consists of approximately 145k time series and randomly choose 2k from them as our experimental data set.
Traffic (34]
This dataset contains hourly traffic data from 963 San Francisco freeway car lanes. The traffic data are collected since 2015/01/01 with the sampling interval of every hour.
ECG3L This dataset is about Flletrncardiggran(ECCCC from the UCR time-series classification archive contains 140 nodes and each node has length of 5000.
38
Electricity This dataset contains the electricity consumption of 370 clients and collected since 1/01/01 The data sampling interval is every 15 minutes.
COVID-195 This dataset is about COVID-19 hospitalization in the U.S. states of California (CA) from 01/02/2020 to 31/12/2020 provided by the Johns Hopkins University with the sampling interval of every one day.
METR-LA This dataset contains traffic information collected from loop detectors in the highway of Los Angeles County from 01/03/2012 30/06/2012, It contains 207 sensors and the data sampling interval is every minutes.
E.2 Baselines
In experiments, we conduct a comprehensive comparison of the forecasting performance between our FourierGNN and representative and state-of-the-un (SOTA) models as follows.
VAR 32] VAR is classic linear autoregressive model. We the Statsmodels library (https 7/www. statsmodelsss.....m......ss org) which is a Python package that provides statistical computations to realize the VAR.
16

---

DeepGLO models the relationships among variables by matrix factorization and employs a temporal convolution neural network to introduce non non-linear relationships. We download the source code from: https: gi thub. com/ jaaaaaatn9///eeepepep
DeepGLO [3
We follow the recommended configuration as our experimental settings for wiki, electricity, and traffic datasets. For covid datasets, the vertical and horizontal batch size is set to 64, the rank of the global model is set to 64, the number of channels is set to [32, 32, 32, 11, and the period is set to
LSTNet uses a CNN to capture inter-variable relationships and an RNN to discover long-term patterns. We download the source code from: htttps///github com/ / laiguokun/ LSTNet. In our experiment, we use the recommended configuration where the number of CNN hidden units is 100, the kernel size of the CNN layers is 4, the dropout is 0.2, the RNN hidden units is 100, the number of RNN hidden layers is 1, the learning rate is 0.001 and the optimizer is Adam.
LSTNet 33
TCN 8
TCN is causal convolution model for regression prediction. We download the source code We utilize the same configuration as the polyphonic music task exampled in the open source code where the dropout is 0.25, the kernel size is 5, the number of hidden units is 150, the number of levels is 4 and the optimizer is Adam.
from: https::/ :/gg thub.
Reformer [35] Reformer combines the modeling capacity of Transformer with architecture that can be executed efficiently on long sequences and with small memory use. We download the source code from: https: http///ggttt.tt/ www./ooommm///.mmm ormer We follow the recommended configuration as the experimental settings.
Informer 9:
Informer leverages an efficient self-attention mechanism to encode the dependen- cies among variables. We download the source code from: htttps///githbl com zhouhaoy1/ Informer 2020 We follow the recommended configuration as our experimental settings where the dropout is 0.05, the number of encoder layers is 2, the number decoder layers is 1, the learning rate is 0.0001, and the optimizer is Adam.
Autoformer 4 : Autoformer proposes decomposition architecture by embedding the series de- composition block as an inner operator, which can progressively aggregate the long-term trend part from intermediate prediction. We download the source code from: btttps:/ggithl/ . cwmm /thmm// Autoformer We follow the recommended configuration as our experimental settings with 2 encoder layers and decoder layer.
FEDformer proposes an attention mechanism with low-rank approximation in frequency and mixture of expert decomposition to control the distribution shifting. We download the source code from: https: //g::://tttttt /ggthtb........ com MMAii qing/ FEDf fomer We use FEB-f as the Frequency Enhanced Block and select the random mode with 64 as the experimental mode.
FEDformer 277
On the basis of the LSTM model, SFM introduces a series of different frequency compo- nents in the cell states. We download the source code from: httpp://tttiii /ggttttt..u.... com/ 2331565360/ State-Frequeeccy -emoryy-MeeM------ stock- prediction We follow the recommended settings where the sttrrr-sstto--pecttioo..
SFM 24:
learning rate is 0.01, the frequency dimension is 10, the hidden dimension is 10 and the optimizer is RMSProp.
StemGNN [10]: StemGNN leverages GFT and DFT to capture dependencies among variables in the frequency domain. We download the source code from: htttps///iithu. com mi crosoft/ StemGNN We use the recommended configuration of stemGNN as experiment setting where the optimizer RMSProp, the learning rate is 0.0001, the number of stacked layers 5, and the dropout rate is 0.5.
MTGNN 13: MTGNN proposes an effective method exploit the inherent dependency relation- ships among multiple time series. We download the source code from: https: thub. com/ mnzhan/MTCND) Because the experimental datasets have no static features, we set the parameter load_static feature to false. We construct the graph by the adaptive adjacency matrix and add the graph convolution layer. Regarding other parameters, we adopt the recommended settings.
Graph introduces an adaptive dependency matrix learning to cap- ture the hidden spatial dependency. We download the source code from: htttp:///itthu: com/ Brrchan/Graph... WaveNet) Since our datasets have no prior defined graph structures, we use only adaptive adjacent matrix. We add a graph convolution layer and randomly initialize the adjacent matrix. We adopt the recommended configuration as our experimental settings where the learning rate is 0.001, the dropout 0.3, the number of epochs is 50, and the optimizer is Adam.
WaveNt 17:
17

---

AGCRN proposes a data-adaptive graph generation module for discovering spatial correlations from data. We download the source code from: https://github com/LeiBALI AGCRN, We follow the recommended configuration our experimental settings where the embedding dimension is 10, the learning rate 0,003, and the optimizer Adam.
AGCRN 2:
TAMP-S2GCNets explores the utility of MP to enhance knowledge represen- tation mechanisms within the time-aware DL paradigm. We download the source code from: https com/ sh aaahnaaaaaa j (510tdeyy80) S2GCNets requires predefined graph topology and we use the California State topology provided by the source code as input. We adopt the recommended configuration our experimental settings on COVID-19.
TAMP-S2GCNets [II
/
TAMP-
DCRNN 18 : DCRNN uses bidirectional graph random walk to model spatial dependency and recurrent neural network capture the temporal dynamics. We download the source code from: https://gi thubb...tttu..... thub.
com/liyaguana /DCRNN We follow the recommended configuration as our experimental settings with the batch size is 64, the learning rate is 0.01, the input dimension 2 and the optimizer is Adam. DCRNN requires a pre-defined graph structure and we use the adjacency matrix as the pre-defined structure provided by the METR-LA dataset.
STGCN [] STGCN integrates graph convolution and gated temporal convolution through spatial-temporal convolutional blocks. We download the source code from/https://gii ParitasYin/SToon IJCAI-18 We use the recommended configuration as our experimental set- tings where the batch size is 50, the learning rate is 0.001 and the optimizer is Adam. STGCN requires a pre-defined graph structure and we leverage the adjacency matrix as the pre-defined structures provided by the METR-LA dataset.
com/
CoST 33 CoST separates the representation learning and downstream forecasting task and proposes contrastive learning framework that learns disentangled season-trend representations for time series forecasting tasks. We download the source code from: https: htt///gittubtt com/ sal sww.ssorceeee//////////ooooooeee CoST We set the representation dimension to 320, the learning rate 0.001, and the batch size 32. Inputs are man-max normalization, we perform a 70/20/10 train/validationttsst split for the METR-LA dataset and 60/20/20 for the COVID-19 dataset.
E.3 Evaluation Metrics
We use MAE (Mean Absolute Error), RMSE (Root Mean Square Error), and MAPE (Mean Absolute Percentage Error) as the evaluation metrics in the experiments.
Specifically, given the groudtruth at timestamps Y, [ ...y x E Rxxx and the predictions Y, [ $ttrl Nxr for future 7 steps at timestamp t, the metrics are defined follows:
N MAE
Taj R:sl
(12)
NN
RMSE
(xy - 221)
(13)
7N
1=1 j=1
Daj Taj
MAPE
x 100%
(14)
NN
Iij
1=1
with mi E Y, and Bay Yz.
E.4 Experimental Settings
We summarize the implementation details of the proposed FourierGNN as follows. Note that the details of the basclines are introduced in their corresponding descriptions (see Section E.2
18

---

Network details. The fully connected feed-forward network (FFN) consists of three linear transfor- mations with LeakyReLU activations in between. The FFN is formulated follows:
X Lea + +bi)
2 Le.,y W2 + bb)
(15)
Y X2W3+
where Wi E ((TT)xdd" W2 R4 xdf fm and W3 E Rdff"xr are the weights of the three layers respectively, and b E Idd"". b2 E R and b3 E R' are the biases of the three layers respectively. Here, of and df are the dimensions of the three layers. In addition, we adopt ReLU activation function in Equation
Training details. We carefully tune the hyperparameters, including the embedding size, batch size, df and df on the validation set and choose the settings with the best performance for FourierGNN on different datasets. Specifically, the embedding size and batch size are tuned over f32, 64, 128, 256, 512) and 4, 8, 16, 32, 64, 128} respectively. For the COVID-19 dataset, the embedding size is 256, and the batch size is set to 4. For the Traffic, Solar, and Wiki datasets, the embedding size is 128, and the batch size is set to 2. For the METR-LA, ECG, and Electricity datasets, the embedding size is 128, and the batch size is set 32.
To reduce the number of parameters, we adopt a linear transform to reshape the original time domain representation Y E NTxd to Y, E NxTxd and map Y, to a low-dimensional tensor Y, E Nxxx with < T. We then reshape Y, E IR (x(d) and feed to FFN. We perform grid search on the dimensions of FFN, i.e., df fn and de over {32, 64, 128, 256, 512] and tune the intermediate dimension / over {2, 6,8, 12). The settings of the three hyperparameters over all datasets are shown in Table g By default, we set the diffusion step (layers) K = 3 for all datasets.
Table 8: Dimension settings of FFN on different datasets. denotes that we feed the original time domain representation to FFN without the dimension reduction.
Datasets
Solar
Wiki
Traffic
ECG
Electricity
COVID-19
META-LR
1
6
*
8
d
64
64
64
256
dg
256
256
256
256
256
512
256
E,5 Details for Visualization Experiments
To verify the effectiveness of FourierGNN in learning the spatiotemporal dependencies the hypervariate graph, obtain the output of FourierGNN the node representation, denoted as Y IDFT(FourieGNNN((() NT'xd with Inverse Discrete Fourier Transform (IDFT). Then, visualize the adjacency matrix A calculated based the flatten node representation Y R NTx formulated A Y (Y E NTNTXN to show the variable correlations. Note that A is normalized via A/ max(AA A). Since is not feasible to directly visualize the huge adjacency matrix A of the hypervariate graph, we visualize its different subgraphs in Figures 4 and t0 better verify the learned spatiotemporal information on the hypervariate graph from different perspectives.
Figure We select 8 counties and visualize the correlations between 12 consecutive time steps for each selected county respectively. 3 the temporal correlations within each variable.
Figure 4 On the METR-LA dataset, we average its adjacency matrix A over the temporal dimension (i.c.. marginalizing 7') A' R.N'N, Then, we randomly select 20 detectors out of all N 207 detectors and obtain their corresponding sub adjacency matrix 20x200 from A' for visualization. We further compare the sub-adjacency with the real road map (generated by the Google map tool) to verify the learned dependencies between different detectors.
Figure Since adopt 3-layer FourierGNN, the spectrum input x2 of FourierGNN and the outputs of each layer in FourierGNN, Following the
calculate four adjacency matrices based on
19

---

way of visualization in Figure matrices for visualization. Figure shows the effects of each layer of FourierGNN in filtering or enhancing variable correlations.
we select 10 counties and two timestamps on the four adjaceney
Figure T0 On the COVID-19 dataset, randomly select 10 counties out of N 55 counties and obtain their four sub-adjacency matrices of four consecutive days for visualization. Each of the four sub adjacency matrices 100000 embodies the dependencies between counties in one day. Figure reflects the time-varying dependencies between counties (i.e., variables).
F
Additional Results
To further evaluate the performance of our model FourierGNN in multi-step forecasting, we conduct more experiments on the Wiki, METR-LA, and ECG datasets, respectively. We compare our model FourierGNN with five models (including StemGNN TO] AGCRN 2 GraphWaveNet [17], MTGNN [3]. and Informer [9]) on the Wiki dataset under different prediction lengths, and the results are shown in Table From the table, we observe that FourierGNN outperforms other models on MAE, RMSE, and MAPE metrics for all the prediction lengths. On average, FourierGNN improves MAE, RMSE, and MAPE by 7.4%, 3.5%, and 22.3%, respectively. Among these models, AGCRN shows promising performances since it captures the spatial and temporal correlations adaptively. However, fails to simultaneously capture spatiotemporal dependencies, limiting forecasting performance. In contrast, our model captures comprehensive spatiotemporal dependencies simultaneously hypervariate graph for multivariate time series forecasting.
Table 9: Accuracy comparison under different prediction lengths on the Wiki dataset.
Length Metries
3
6
9
12
MAE
MAPE(S)
RMSE
MAPE(%)
MAE
RMSE
MAPE/%)
RMSE
MAPE/%)
Groph WaveNet
17
0.061
0.105
138.60
0.061
0.108
135.32
0.061
0.105
132.52
0.061
0.104
136.12
StemKGNN 10
0.157
0.236
89.00
0.159
0.233
98.01
0.232
0.311
142,14
0.220
0.306
125.40
AGORN 2
0.043
0.077
01014
0.078
0.045
0.079
0.044
0.079
MTGNN [B]
0.102
0.141
123.15
0.091
0.133
91.75
0.074
0.120
85.14
0.101
0.140
122.96
Informer
0.053
0.089
85,31
0.054
0.090
$4.46
0.059
0.095
93,80
0.059
0.095
95.09
FourierGNN
0.040
0.075
0.041
0.075
0.076
0.041
0.076
Table 10: Accuracy comparison under different prediction lengths on the METR-LA dataset.
Honizon
3
6
12
Metries
RMSI:
MAPR(S)
RMSE:
MAPE(S5)
RMSE:
MAPE(S
MAE
RMSE
MAPR(S5)
DCRNN
18
0.160
0.204
80.00
0.191
0.243
83.15
0.216
0.269
85.72
0.241
0.291
$8.25
STGCN 1
0.058
0.133
59.02
0.080
0.177
60.67
0.102
0.209
62.08
0.128
0.238
63.81
WaveNe
17
0.180
0.366
21.90
0.184
0.375
22.95
0.196
0.382
23.61
0.202
0.386
24.14
MTGNN L3
0.135
0.294
17.99
0.141
0.307
18.82
0.149
0.328
19.38
0.153
0.316
19.92
StemKNNN
10
0.052
0.115
86.39
0.069
0.141
87.71
0.080
0.162
89.00
0.093
0.175
90.25
AGCRN
0.062
24.96
0.165
0.188
0.109
0.204
Informer
0.076
0.141
69.96
0.088
0.163
70.94
0.096
0.178
72.26
0.100
0.190
72.54
CoST [36
0.064
0.118
88.44
0.077
0.141
89.63
0.088
0.159
90.56
0.097
0.171
91,42
FourierGNN
0.050
0.113
86.30
0.066
0.140
87.97
0.076
0.159
$8.99
0.084
0.165
Furthermore, we compare our model FourierGNN with seven MTS models (including STGCN [. DCRNN [8], StemGNN [00, AGCRN (2) Graph WaveNee [7), MTGNN [33. Informer (9. and CoST (36)) on the METR-LA dataset which has a predefined graph topology in the data, and the results are shown in Table 10 On average, we improve 5.7% on MAE and 1.5% on RMSE. Among these models, StemGNN achieves competitive performance because it combines GFT to capture the spatial dependencies and DFT to capture the temporal dependencies. However, it is also limited to simultancously capturing spatiotemporal dependencies. CoST learns disentangled seasonal-tremt representations for time series forecasting via contrastive learning and obtains competitive results. But, our model still outperforms COST. Because, compared with CoST, our model not only can learn the dynamic temporal representations, but also capture the discriminative spatial representations. Besides, STGCN and DCRNN require pre-defined graph structures. But StemGNN and our model outperform them for all steps, and AGCRN outperforms them when the prediction lengths are 9 and 12. This also shows that novel adaptive graph learning can precisely capture the hidden spatial dependency. In addition, we compare FourierGNN with the baseline models under the different prediction lengths on the BCG dataset, as shown in Figure 5 It reports that FourierGNN achieves the best performances (MAE, RMSE, and MAPE) for all prediction lengths.
20

---

0.12
0.1b
50
0.10
1 0.12
0.08
0.10
20-
0.06
5
10
8
10
prodetio beaght
pold knngtt
PRCTAL or logglo
(a) MAE
(b) RMSE
(c) MAPE
Figure 5: Performance comparison in multi-step prediction on the ECG dataset.
G Further Analyses
G.1 Scalability Analysis
We further conduct experiments on the Wiki dataset to investigate the performance of FourierGNN under different graph sizes (N x T). The results are shown Figure where [ggure(((a) Figure 6(b)
and Figure(6(c) show MAF, RMSE, and MAPE at the different number of nodes, respectively. From these figures, we observe that FourierGNN keeps a leading edge over the other state-of-the- MTS
models as the number of nodes increases. The results demonstrate the superiority and scalability of FourierGNN on large-scale datasets.
0.50
180
Goad
160
4
0.15
N 0.20
120
0.10
0.15
80
300
350
150
500
300
400
450
350
400
500
Suantcr of Wode
Aumber of Media
humber Rooks
(a) MAE
(b) RMSE
(c) MAPE
Figure 6: Scalability analyses in terms of MAE, RMSE, and MAPE under different number of nodes on the Wiki dataset.
G.2 Parameter Analysis
We evaluate the forecasting performance of our model FourierGNN under different diffu- sion steps (layers) on the COVID-19 19 dataset, as illustrated in Table II The table shows that FourierGNN achieves increasingly bet- ter performance from K and achieves the best results when K = 3. With the further increase of K, FourierGNN obtains inferior performance. The results in- dicate that high-order diffusion information is beneficial for improving forecasting accuracy, but the diffusion information may gradually weaken the effect or even bring noises to forecasting with the increase of the order.
Table 11: Performance different diffusion steps (lay- ers) on the COVID-19 19 dataset.
K=1
K=2
K=3
K=4
K
MAE
0.136
0.133
0.123
0.132
RMSE MAPE(%)
0.181
0.177
0.168
0.176
72.30
71.80
71.52
72.59
In addition, we conduct additional experiments on the ECG dataset to analyze the effect of the input lookback window length T and the embedding dimension d, as shown in Figure 7 and Figure X respectively. Figure Z shows that the performance (including RMSE and MAPE) of FourierGNN gets better as the input lookback window length increases, indicating that FourierGNN can learn comprehensive hypervariate graph from long MTS inputs to capture the spatial and temporal dependencies. Moreover, Figure shows that the performance (RMSE and MAPE) first increases and then decreases with the increase of the embedding size, which is attributed that a large embedding
21

---

1902
0.755
42.30
0.0990
0.0077
11.000
0.785
0.0005
0.0700
13.00
0,0985
00375
0.008
10:30
10
25
20
25
25
Poxa: Jangth
Figure 7: Influence of input window.
Figure 8: Influence of embedding size.
size improves the fitting ability of FourierGNN but it may easily lead to the overfitting issue especially when the embedding size is too large.
G.3 Ablation Study
We provide more details about each variant used in this section and Section 5.3
w/o Embedding. variant of FourierGNN feeds the raw MTS input instead of its embed- dings into the graph convolution in Fourier space.
w/o Dynamic FGO. A variant of FourierGNN uses the same FGO for all diffusion steps instead of applying different FGOs in different diffusion steps. It corresponds to vanilla graph filter.
w/o Residual. A variant of FourierGNN does not have the K = 0 layer output, i.c., 2; in the summation.
w/o Summation. A variant of FourierGNN adopts the last order (layer) output the final frequency output of the FourierGNN.
We conduct another ablation study the COVID-19 dataset further investigate the effects of the different components of our FourierGNN. The results are shown in Table 12, which confirms the results in Table4anni and further verifies the effectiveness of each component in FourierGNN, Both Table 12 and T report that the embedding and dynamic FGOs in FourierGNN contribute more than the design of residual and summation the state-of-the-art performance of FourierGNN.
Table 12: Ablation studies on the COVID-19 dataset.
Metrie
w/o Embedding
w/o Dynamic FGO
w/o Residual
wlo Summation
FourierGNN
MAE
0.157
0.138
0.131
0.134
0.123
RMSE
0.203
0.180
0.174
0.177
0.168
MAPE(%)
76.91
74.01
72.25
72.57
71.52
H Visualizations
H.1 Visualization of the Diffusion Process in FourierGNN
To gain insight into the operation of the FGO, we visualize the frequency output of each layer in our FourierGNN. We select 10 counties from the COVID-19 dataset and visualize their adjacency matrices at two different timestamps, as shown in Figure 9 From left to right, the results correspond the original spectrum of the input, as well as the outputs of the first, second, and third layers of the FourierGNN. From the top, we can find that as the number of layers increases, some correlation values are reduced, indicating that some correlations are filtered out. contrast, bottom case illustrates some correlations are enhanced as the number of layers increases. These results show that FGO can adaptively and effectively capture important patterns while removing noises, enabling the learning of a discriminative model.
22

---

Figure 9: The diffusion process of FourierGNN at two timestamps (top and bottom) on COVID-19.
H.2 Visualization of Time-Varying Dependencies Learned by FourierGNN
Furthermore, we explore the capability of FourierGNN in capturing time-varying dependencies among variables, To investigate this, we perform additional experiments to visualize the adjacency matrix of 10 randomly-selected counties over four consecutive days on the COVID-19 dataset. The visualization results, displayed as a heatmap in Figure TO reveal clear spatial patterns that exhibit continuous evolution the temporal dimension. This is because FourierGNN can attend to the time-varying variability of the spatiotemporal dependencies. These results verify that our model enjoys the feasibility exploiting the time-varying dependencies among variables.
Based on the insights gained from these visualization results, we can conclude that the hypervariate graph structure exhibits strong capabilities encode spatiotemporal dependencies. By incorporating FGOs, FourierGNN can effectively attend to and exploit the time-varying dependencies among variates. The synergy between the hypervariate graph structure and FGOs empowers FourierGNN to capture and model intricate spatiotemporal relationships with remarkable effectiveness.
Figure 10: The adjacency matrix for four consecutive days on the COVID-19 dataset.
23


Reviews:
[{"review_id": "Rjj595CM7I", "reviewer": "Reviewer_G8af", "summary": "In this paper, the authors study a problem in GNN-based multivariate time series (MTS) forecasting, i.e. modeling spatial correlations and temporal dependencies in the same time. In particular, the authors do not follow previous works on regarding the input as T graphs and capturing temporal dependencies between graphs by temporal networks, but propose to formulate T graphs as a hypervariate graph(a pure fully-connected graph with NT nodes). Specifically, to deal with the huge node amount NT in a hypervariate graph, the authors propose the FourierGNN which utilize matrix multiplications in the Fourier space of graphs to decrease the quadratic computational complexity to quasi linear one. Empirical results on seven datasets show the effectiveness of this method.", "questions": "1.\tWhat’s the performance of FourierGNN on longer prediction lengths such as {24, 36, 48, 60} in FEDformer?\n2.\tWhat’s the meaning of “the same sparsity pattern” in line 196?\n3.\tHow to determine the value of A_i in equation (7), A_0 is identity and what about A_1, A_2?\n", "limitations": "Please check the weakness", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The authors provide a novel view of graph-based MTS forecasting called hypervariate graph.\n2. The authors propose Fourier Graph Operator and FourierGNN for efficient convolution on hypervariate graph.\n3. In the authors’ experiments, FourierGNN obtains superior performance.  \n", "weaknesses": "1.\tThe detail of the experiments is not clear. The authors run previous models on different datasets but do not show whether some hyperparameters, such as feature dim, change with the dataset.  \n2.\tThe authors claim that FourierGNN is efficient for hypervariate graph, but do not provide other networks’ performance such as GCN on hypervariate graph. \n3.\tThe models compared with Efficiency Analysis are too old.\n4.\tThe authors do not explain the reason for the Green kernel. The Green kernel is a strong assumpition. In line 161, k_{ij} = A_{ij} W and k_{ij} = k_{i-j} results A_{j+k}_{j} equals for any j, which strictly restricts the topology of the hypervariate graph. Besides, there is no visualization of A in each layer to check whether the green kernel assumption is satisfied during training.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your positive feedback and valuable suggestions. In the following, we provide a detailed response to address all of your concerns.\n\n**W1.**\n\nThanks for your suggestion. We provide more clear details to clarify the experimental settings of baselines in Appendix E.2. In the experiments, we 1) followed the parameter configuration recommended by the original authors of each baseline for the datasets used in both the baseline paper and our paper; and 2) tuned the recommended parameter settings on datasets not used in the baseline paper to guarantee that baselines achieve the best results. \n\nImportant reproduction details for all baselines are provided in Appendix E.2. For example, the parameter settings of DeepGLO, TAMP-S2GCNets, DCRNN, and STGCN vary with different datasets. \n\n**W2.**\n\nWe have conducted a thorough analysis of the time complexity of our proposed Fourier Graph Operator (FGO) in comparison with graph convolution, as presented in **Lines 203-209** of the paper.\n\nTo clarify more clearly, we summarize the time complexity and parameter volumes in **Table 5 in the attached PDF**.\n\nFurthermore, to address your concern, we conducted additional experiments on METR-LA and ECG datasets to compare the time complexity of FourierGNN with GCN. In the experiments, we replaced FourierGNN with GCN [1] and performed GCN on the hypervariate graph. We compare FourierGNN with two types of GCN: 1) GCN-N performs GCN on the graph of $N$ variable nodes; 2) GCN-NT performs GCN on the hypervariate graph with $NT$ nodes. Since GCN-N, as a typical GCN, requires a pre-defined graph topology, it can not be conducted on ECG dataset because the dataset has no pre-defined graph topology. For GCN-NT, we input the adjacency matrix with values all one as the graph topology. The corresponding results (average the results of five epoch times) in terms of training time costs on two datasets are reported in the following table:\n\n|    Models    | METR-LA (N=207, T=12)| ECG (N=140, T=12) | \n|:---|:---|:---|\n|  FourierGNN  | 99.76 $\\pm$ 2.74 s/epoch | 8.98 $\\pm$ 0.31 s/epoch |  \n|     GCN-N     | 213.64 $\\pm$ 1.21 s/epoch| --- |  \n| GCN-NT| 1976.33 $\\pm$ 6.24 s/epoch| 384.58 $\\pm$ 2.86 s/epoch |\n\nThe table reveals a notable efficiency advantage of FourierGNN, even showcasing superior performance compared to GCN with $N$ nodes. We will add this experiment to the appendix of our final version.\n\n[1]. Kipf & Welling, Semi-Supervised Classification with Graph Convolutional Networks, ICLR 2017\n\n**W3.**\n\nSince FourierGNN is a frequency-related GNN-based model, we previously chose the GNN-based baselines for efficiency analysis. We will add two **latest frequency-related** baselines, i.e., Autoformer (2021, NeurIPS) and FEDformer (2022, ICML), in the **Efficiency Analysis of Section 5.3**. The new results are presented in **Table 6 in the attached PDF**.\n\n**W4.**\n\nNote that the hypervariate graph $\\mathcal{G}\\_t$ is a **fully-connected graph** (i.e., $A=\\{1\\}^{n\\times n}$) as shown in **Definition 1**. Accordingly, we can easily prove the green kernel assumption on the hypervariate graph.\n\nRegarding the hypervariable graph: since the underlying topology structure of the $NT$ nodes is generally not known in advance, we initialize the hypervariate graph with a fully-connected graph and subsequently learn the edge weights (i.e., node correlations or spatiotemporal dependencies) on the graph (more explanation can be seen in **Appendix C**).\n\nIn addition, since the hypervariate graph is fully-connected, we have visualized the learned node correlations (edge weights) in each layer on the hypervariate graph in **Figure 9 in Appendix H.1**. Specifically, we have visualized the learned adjacency matrices corresponding to the original spectrum of the input, as well as the outputs of the first, second, and third layers of  FourierGNN in **Figure 9**.\nThese results show that our FGO can adaptively and effectively capture important spatiotemporal correlations while removing noises, enabling the learning of a discriminative model.\n\n**Q1.**\n\nTo address your concern, we performed additional experiments to compare the performance of FourierGNN and FEDformer on longer prediction lengths \\{12,24,36,48,60\\} with an input length of 24 on METR-LA dataset. The results are as below:\n\n|  Model| Metric|12 | 24 | 36 | 48 | 60 |\n|:----|:----|:----|:----|:----|:----|:---|\n|FEDformer|MAE| 0.108| 0.120| 0.137| 0.148| 0.163|\n| |RMSE|0.190 | 0.216| 0.231| 0.259| 0.278|\n|FourierGNN|MAE| 0.087| 0.115| 0.140| 0.155| 0.169|\n| |RMSE| 0.169| 0.207| 0.230| 0.265| 0.287|\n\nThe results demonstrate that FourierGNN achieves significantly better performance than FEDformer on lower prediction lengths, such as {12, 24}, but underperforms FEDformer on longer prediction lengths \\{36,48,60\\}. This is reasonable because FEDformer, being a Transformer-based baseline, is effective in capturing long-range temporal dependencies, while FourierGNN similar with GNN-based models is skilful in capturing local/short-term spatiotemporal dependencies.\n\n**Q2.**\n\nThe same sparsity pattern means that the positions of non-zero elements in two matrices are identical. The two matrices have the same structure of connections between elements, even though the actual values of the non-zero elements might be different.\n\n**Q3.**\n\nSince the underlying structure of the hypervariate graph is not given, we initialize the hypervariate graph as a fully-connected graph, i.e., $A=\\{1\\}^{n\\times n}$. All adjacency matrices $\\{A_i\\}_{i=1}^K$ in $K$-order FourierGNN sharing the same sparsity pattern with $A$ are fully-connected. But their edge weights are learned during training our FourierGNN on a specific dataset. This corresponds to learning the spatiotemporal dependencies between nodes.\n\nWe will clarify the above in the final version, and hope we have addressed all of your comments."}, {"review_id": "jilBXpkRco", "reviewer": "Reviewer_ndBv", "summary": "The paper addresses the time series forecasting problem.\nThe authors propose a model that represents each scalar\nobservation as a node in a (fully connected) graph,\nencodes the nodes and finally regresses the future\nobservations on all previous encoded observations\n(via a fully connected layer). As encoding they propose\na discrete fourier transform followed by several node-wise\nfully connected layers and finally an inverse fourier transform.\nIn experiments on 6 datasets they show improvements over\nseveral baselines.\n", "questions": "w1. a main aspect of the proposed model is not clear. \n- the authors describe the fourier graph layer as applying the discrete\n  fourier transform on the graph features X\\in\\R^{nd\\times 1} of a complete graph,\n  explicitly not the graph fourier transform. Which dimension is the time\n  dimension for this fourier transform? The node dimension of X contains\n  nd many entries, one for each time point and channel. While one can\n  compute a fourier transform also over this vector, what is it semantics?\n  How does it capture time varying information? And would this not crucially\n  depend on how on is ordering these nd many entries?\n\nw2. missed recent related work.\n- esp. PatchTST [Nie et al. 2023] and dlinear [Zeng et al. 2023] are well\n  known model outperforming your baselines by a good margin.\n\nw3. experimental protocol is unclear and deviates from the literature.  \n- what is the forecasting horizon \\tau you are using?\n- the experiments report only a single number per dataset and error measure,\n  while in the literature usually  results for a portfolio of forecasting horizons\n  are reported (e.g., 96, 192, 336, 720, e.g., the Fedformer). Why do you deviate\n  from this standard? This way it also is not possible to compare your results\n  with the results published in those papers.\n- usually results are also reported for further datasets such as ETTm2, Exchange,\n  Weather and ILI. How does your model compare to those published results?\n\nw4. for a key component of the proposed model, there is no ablation study\n  demonstrating its impact.\n- while there are many papers that simply operate on the fourier spectrum\n  of a time series, one key component of the model of the authors seems\n  to be that after these operations they move back into the time domain\n  by the inverse fourier transform. What is the impact of this back transformation?\n   \nreferences:\n- Nie, Yuqi, Nam H. Nguyen, Phanwadee Sinthong, and Jayant Kalagnanam. “A Time Series Is Worth 64 Words: Long-Term Forecasting with Transformers.” arXiv, March 5, 2023. https://doi.org/10.48550/arXiv.2211.14730.\n- Zeng, Ailing, Muxi Chen, Lei Zhang, and Qiang Xu. “Are Transformers Effective for Time Series Forecasting?” In AAAI, 2023.\n", "limitations": "n/a", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "s1. interesting problem: time series forecasting\ns2. interesting approach: parametrizing transformations in fourier space\ns3. results showing improvements over many baselines\n", "weaknesses": "w1. a main aspect of the proposed model is not clear. \nw2. missed recent related work.\nw3. experimental protocol is unclear and deviates from the literature.  \nw4. for a key component of the proposed model, there is no ablation study\n  demonstrating its impact.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your review. Hope our response can address the misunderstandings or concerns.\n\n**w1**\n\n1. The node features of the hypervariate graph are $X \\in \\mathbb{R}^{n \\times d}$, where $n=NT$ is the number of nodes, $d$ is the number of features, $N$ is the number of variables, and $T$ is the input length. In our proposed FourierGNN, we conduct DFT along the spatiotemporal dimension of $n$ (**see lines 227-228**).\n\n    Note that the Fourier transform allows us to transform data from the time domain to the frequency domain, revealing its frequency spectrum. However, the Fourier transform is not limited to the time domain alone; it can be applied to various types of data beyond time series, including images and other multidimensional data. Accordingly, the Fourier transform is not necessarily performed along the time dimension, for example, one can apply DFT on images to obtain the frequency spectrum features.\n\n2. According to the convolution theorem (see **Appendix B**), the Fourier transform of a convolution of two sequences equals the pointwise product of their Fourier transforms. Therefore, the multiplication between $\\mathcal{F}(X)$ and FGO $\\mathcal{S}$ can be written as $\\mathcal{F}(\\sum_{j=1}^n {{X}}[j]\\kappa[i-j])=\\mathcal{F}((X*\\kappa)[i])=\\mathcal{F}({X})\\mathcal{S}$, corresponding to a graph convolution on the hypervariate graph (see **Equations 4 and 5**). In other words, FGO is equivalent to the graph convolution, and FourierGNN is equivalent to multi-order convolutions on the hypervariate graph (**see Proposition 1**).\n\n    Mathematically, conducting DFT on the spatiotemporal dimension of $n$ is to purposefully transform the time-consuming graph convolutions on the hypervariable graph to the efficient pointwise multiplication in the Fourier space (**see Complexity Analysis in Section 4.2**). Intuitively, it obtains the global frequency spectrum of the node features of the hypervariate graph, corresponding to the values of all variables at each timestamp, facilitating learning a high-resolution spatiotemporal representation across timestamps and variables (**explanations can be seen in Appendix C.1**).\n\n    In addition, we have conducted visualization experiments to demonstrate that FourierGNN can learn both discriminative temporal dependencies and highly interpretative spatial dependencies (**Figures 3 and 4 in Section 5.4** and **Figures 9 and 10 in Appendix H Visualizations**).\n   \n3. Structure: According to **Definition 1**, the hypervariate graph connects any two variables at any two timestamps. It embodies not only the intra-series temporal dependencies (node connections of each individual variable), time-varying inter-series spatial dependencies (node connections over each single time step), and also the time-varying spatiotemporal dependencies (node connections between different variables at different time steps). More details can be seen in **Appendix C.1**.\n\n    Methodology: FourierGNN stacking multiple FGOs is equivalent to multi-order graph convolutions, enabling FourierGNN to adaptively capture the abovementioned high-resolution spatiotemporal dependencies, including the time-varying correlations.\n   \n    Empirically: In **Figure 10 in Appendix H.2**, we visualize the learned adjacency matrix of 10 randomly-selected counties over four consecutive days on the COVID-19 dataset. The results reveal clear spatial patterns that exhibit continuous evolution in the temporal dimension, verifying that FourierGNN enjoys the feasibility of exploiting the time-varying dependencies among variables.\n\n4. Our proposed FourierGNN **is not** influenced by the order of $n$ node features. Structurally, since the hypervariate graph is a fully-connected graph, the order of its $n$ nodes is trivial. Mathematically, given data $x[n]$ with $N$ datapoints, the DFT of $x$ is $\\mathcal{X}[k]=\\sum_{n=0}^{N-1} x[n]\\cdot e^{-\\frac{i2\\pi }{N} kn } $. The frequency spectrum $\\mathcal{X}[k]$ is regardless of the order of the datapoints $x[n]$.\n   \n    To verify the claim, we randomly shuffled the order of time series variables in the raw ECG data five times and evaluated our model on each shuffled set of data. The result is reported in **Table 3 in the attached PDF**, which shows that FourierGNN achieves consistent performance on raw data and randomly shuffled data.\n\n**w2**\n\nNote that FourierGNN represents a **GNN-based** model that incorporates **frequency analysis** and is tailored for short-term multivariate time series forecasting. Accordingly, we chose GNN-based models (AGCRN, StemGNN, MTGNN, GraphWaveNet, TAMP-S2GCNets, DCRNN, and STGCN), frequency-based models (SFM, FEDformer, Autoformer, and CoST), and short-term models (LSTNet, DeepGLO, and TCN), as well as one representative model (Informer) as our baselines.\n\nPatchTST (Transformer-based) and DLinear (MLP-based) are the latest representative work for long-term time series forecasting. Considering that they are neither short-term models nor GNN-based/frequency-based models, they were not included in the comparison. **Moreover, PatchTST and DLinear have not compared their performance with GNN-based models, and they have also not conducted experiments according to the short-term settings**.\n\nTo address your concern, we performed experiments to compare FourierGNN with PatchTST and DLinear on seven real-world datasets for short-term forecasting (the input length and the prediction length are 12). We reported the results in **Table 1 in the attached PDF**. From the results, we can find that FourierGNN outperforms PatchTST and DLinear on all datasets. The results are reasonable because, compared with FourierGNN, DLinear and PatchTST are more effective at handling gradually evolving trends/long-term temporal correlations but less effective at capturing complex/time-varying spatiotemporal dependencies.\n\nFor W3 and W4, due to space limit, we response them in general response and PDF file."}, {"review_id": "GxLch9lnMp", "reviewer": "Reviewer_ipTP", "summary": "This paper has studied a popular and important problem, i.e., modeling the intricate spatial and temporal dependencies among multivariate time series for accurate forecasting. To overcome the main limitation that existing works always separately model spatial and temporal, this work designs a new hypervariate graph structure to encode the spatiotemporal dynamics unitedly, and proposes a novel FourierGNN to learn the spatiotemporal dependencies. Extensive experiments on seven real-world datasets demonstrate FourierGNN achieves good performances in both accuracy and efficiency compared with state-of-the-art methods.", "questions": "1.Besides MTS forecasting, can FourierGNN be applied to other domains as well?\n2.How does the proposed model handle the redundant information in the hypervariate graph structure?", "limitations": "n/a", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "This paper presents a novel formulation from a pure graph perspective to model spatiotemporal dependencies for MTS forecasting. The work is interesting and original, which is different from previous GNN-based methods that typically model spatial and temporal dependencies with distinct graph and temporal networks. The novel pure graph modeling is straightforward yet quite meaningful for MTS forecasting, which brings up good inspiring insights.\n\nThis paper proposes a graph neural network, namely FourierGNN, to cooperate with the pure graph formulation and provides a theoretical guarantee of effectiveness. \n\nThis paper seems to have solid, extensive and diverse experiments, which are conducted on seven real-world different datasets. The extensive experimental results have clearly demonstrated the obvious performance improvement of FourierGNN in terms of accuracy and efficiency over state-of-the-art MTS forecasting models.", "weaknesses": "I have two concerns. \nMy first concern is about the hypervariate graph structure. Although the authors stated that all variables at all timestamps can encode high-resolution relationships, it also may introduce some redundant information or unwanted correlations, such as some variables that are far apart in time. How can this be properly handled? Besides, I find that the core operations of FourierGNN are conducted in the Fourier space, so I am curious whether transferring the hypervariate graph structure into the Fourier space help to learn dependencies. \n\nIn addition, another concern is whether FourierGNN can also be applied to other domains apart from the multivariate forecasting. Maybe it can be extended to other graph tasks.\n\nMinor typos: In the caption of Figure 2, Given the hypervariate graph $\\mathcal{G}=(X^\\mathcal{G}_t, A^\\mathcal{G}_t)$  should be $\\mathcal{G}_t=(X^\\mathcal{G}_t, A^\\mathcal{G}_t)$", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your positive comments. We would like to respond to your comments as follows.\n\n**Q1. How to properly handled redundant or unwanted correlations in the hypervariate graph?**\n\nAs stated in **Section 4.1 The Pure Graph Formulation**, we propose the hypervariate graph to connect all variables at all timestamps, where we view spatial dynamics and temporal dependencies from a united perspective. It benefits modeling the real-world spatiotemporal inter-dependencies. Specifically, since we do not have the pre-defined graph structure connecting any two variables at any two timestamps, we initialize the hypervariate graph as a fully-connected graph and learn edge weights (i.e., node spatiotemporal inter-dependencies) adaptively to training data. Accordingly, node correlations are adaptively learned by the supervision of MTS forecasting objectives. In other words, although we initially consider connections between all variables at all timestamps, significant/redundant node correlations are remained/reduced during training FourierGNN (i.e., the learning of spatiotemporal dependencies) via adaptively adjusting the correlation values.\n\nEmpirically, we have visualized the learned adjacency matrices from three different perspectives: \n1) temporal adjacency matrix of eight variates (see **Figure 3 in Section 5.4**); \n2) adjacency matrices of variables in different layers of FourierGNN (see **Figure 9 in Appendix H.2**); and \n3) final adjacency matrices of variables for four consecutive days (see **Figure 10 in Appendix H.2**).\n\nFrom these visualization results, we can obviously observe:\n1) FourierGNN learns distinct temporal patterns for each variable (county), indicating that the hypervariate graph can encode rich and discriminative temporal dependencies (corresponding to Figure 3); \n2) FGO can adaptively and effectively capture important patterns while removing noises, enabling the learning of a discriminative model (corresponding to Figure 9); and \n3) FourierGNN enjoys the feasibility of exploiting the time-varying dependencies among variables (corresponding to Figure 10). \n\nFurthermore, we have conducted a visualization analysis to evaluate the effectiveness of the learned correlations in accordance with the real-world road map on the METR-LA dataset. The results provide strong evidence that the learned hypervariate graph structure can represent highly interpretable correlations, confirming the ability of FourierGNN to capture meaningful and relevant relationships among nodes. Please refer to **Figure 4 in Section 5.4** for visual representation.\n\nThese empirical findings support the notion that FourierGNN is capable of effectively learning underlying node correlations and removing redundant correlations based on the hypervariate graph.\n\n**Q2. Whether transferring the hypervariate graph structure into the Fourier space help to learn dependencies.**\n\nYes, we transfer the hypervariate graph structure into the Fourier space, which helps learn spatiotemporal dependencies from two perspectives:\n1) **Effectiveness**: According to the convolution theorem (see **Appendix B**), the Fourier transform of a convolution of two sequences equals the pointwise product of their Fourier transforms. The theorem demonstrates that our proposed Fourier Graph Operator (FGO) is equivalent to the graph convolution operation in the time domain as shown in **Equations 4 and 5**, which provides a theoretical basis for FGO's ability to capture spatiotemporal dependencies on the hypervariate graph. See **Explanations and Proofs in Appendix C** for more details. In addition, Fourier transform offers a global view of the data, which may benefit capturing the global characteristics of the whole sequence [20]. The advantage helps FGO to effectively capture and model the global spatiotemporal dependencies in the hypervariate graph.\n2) **Efficiency**: As shown in **Definition 1**, the hypervariate graph $\\mathcal{G}\\_t$ as a fully-connected graph contains $NT$ nodes, and its corresponding adjacency matrix is ${A}^{\\mathcal{G}}\\_t \\in \\mathbb{R}^{NT \\times NT}$. It is extremely time-consuming to perform GCN or GAT on the hypervariate graph since the time complexity of the graph convolution and graph attention is quadratic to the number of nodes (i.e., $(NT)^2$) and proportional to the number of edges (i.e., $(NT)^2$), respectively. In contrast, the time complexity of our proposed FGO is proportional to $NT\\operatorname{log}(NT)$, where the Log-linear $\\mathcal{O}(n\\operatorname{log}n)$ complexity makes FourierGNN much more efficient. Please refer to **Complexity Analysis in Lines 203-209** for more details.\n\nIn summary, our proposed FourierGNN transfers the hypervariate graph into the Fourier space, facilitating efficiently learning effective spatiotemporal dependencies on the hypervariate graph.\n\n**Q3. \"Whether FourierGNN can also be applied to other domains ...\"**\n\nYes. In **Section 4.2 FourierGNN**, the paper presents the definition and formulation of the proposed FGO and FourierGNN, which are designed based on a graph. FGO, as well as FourierGNN, can be seen as a form of global convolution or multi-order convolutions, and they are not specifically limited to the time series domain. They can be applied to various other domains where graph-based learning models are applicable. When extending the application of FourierGNN to other domains, it is crucial to ensure that the underlying graph topology in those domains satisfies the conditions of the Green's kernel.\n\n**Q4. Minor typos**\n\nWe will carefully check thoroughly the paper and correct the typos in the final version.\n\n**Q5. \"... can FourierGNN be applied to other domains as well?\"**\n\nPlease refer to our response in Q3.\n\n**Q6. \"How does the proposed model handle the redundant information...?\"**\n\nPlease refer to our response in Q1.\n\nWe will clarify the above in the final version and hope that we have addressed all your concerns."}, {"review_id": "XmJXUCWMrG", "reviewer": "Reviewer_yaJh", "summary": "The paper presents FourierGNN for multivariate time series forecasting from a pure graph perspective, performing matrix multiplications in Fourier space, which has not been investigated so far. They design a new hypervariate graph structure to consider spatiotemporal dynamics unitedly and reformulate the graph operations on the hypervariate graph in Fourier space. Extensive experiments have demonstrated superior performance with higher efficiency and fewer parameters over state-of-the-art methods.", "questions": "FourierGNN demonstrates impressive performance across multiple datasets, with notable success observed on the COVID dataset. Could you explain the reasons that contribute to the superior performance of FourierGNN on the COVID dataset compared to other datasets?", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is overall well-written. I think the contribution and novelty of the proposed work are clearly presented.\n2. The idea of directly applying graph networks for multivariate time series forecasting seems novel and exciting. The hypervariate graph structure can encode spatiotemporal dependencies unitedly, and the visualizations in the experiments have also verified its advantages.\n3. The authors argue that performing the multiplication between the input and the proposed FGO in Fourier space is equivalent to a graph convolution in the time domain, while the multiplications in Fourier space have lower complexity. The argument is proved by the authors and seems very meaningful. I think this argument provides a new path for conducting graph operations in Fourier space.\n4. The effectiveness is validated through extensive experiments across seven real-world datasets. Sufficient analysis including efficiency analysis and ablation study is also provided.\n", "weaknesses": "1. In the efficiency analysis section, the authors assess the overall efficiency of the forecasting process. To specifically evaluate the efficiency of FourierGNN, it would be more appropriate to focus on comparing the number of parameters involved in the graph operations with those of the baselines.\n2. The MAPE (Mean Absolute Percentage Error) results on some datasets (e.g., Traffic, COVID-19) do not achieve state-of-the-art performance.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback and valuable suggestions. In the following, we provide a detailed response to address all of your concerns.\n\n**W1**\n\nSince it is difficult and unfair to analyze the time complexity and parameter volumes of comparative methods that have different architectures, we report the empirical training time and parameter volumes of FourierGNN and the GNN-based baselines in the efficiency analysis. Meanwhile, we provide theoretical efficiency analysis between FGO/FourierGNN and graph convolution/GCN (a commonly-used module) in the analysis of time complexity.\n\nThe efficiency analysis in **Model Analysis in Section 5.3** aims to investigate the parameter volumes and training time costs of FourierGNN and its comparative baselines. The comparison results show:\n1) FourierGNN exhibits the lowest volume of parameters among the comparative models; \n2) FourierGNN runs much faster than all baseline models. \n\nThese results demonstrate the efficiency of our proposed FourierGNN compared with state-of-the-art GNN-based models.\n\nRegarding the time complexity of the graph operators in FourierGNN, we have discussed and provided the time complexity of FGO in **Complexity Analysis (Lines 203-209)**. Specifically, the computational time complexity of FGO is $\\mathcal{O}(nd\\operatorname{log}n+nd^2)$, while the time complexity of the equivalent graph convolution in the time domain, i.e., $AXW$, is $\\mathcal{O}(n^2d+nd^2)$. This indicates the lower time complexity of FGO compared with the graph convolution. Accordingly, FourierGNN ($K$-order) has the time complexity of $\\mathcal{O}(nd\\operatorname{log}n+Knd^2)$, compared with the time complexity of $K$-layer GCNs $\\mathcal{O}(Kn^2d+Knd^2)$. In addition, the parameter volumes of FGO and FourierGNN are $\\mathcal{O}(d^2)$ and $\\mathcal{O}(Kd^2)$ respectively, which are the same as those of the graph convolution and GCNs. We summarize the parameter volumes and time complexity in **Table 5 in the attached PDF**.\n\n**W2.** \n\nWhile FourierGNN does not achieve the best MAPE results on all datasets, it consistently ranks within the top-3 among all 14 comparative methods and demonstrates comparable performance to state-of-the-art MAPE results.\n\nFurthermore, FourierGNN outperforms all the baselines in terms of MAE and RMSE, even though it may not achieve the best MAPE scores. This is an acceptable outcome because the best baseline on different datasets does not necessarily guarantee the best performance in terms of MAE, RMSE, and MAPE. These three metrics reflect the accuracy of forecasting from different perspectives. In addition, FourierGNN, along with most of the baseline methods, adopts MSE as the objective function. As a result, the comparative methods tend to prioritize improvements in terms of MSE or RMSE.\n\nIn summary, FourierGNN achieves the best MAE and RMSE scores while consistently ranks within the top-3 in terms of MAPE scores compared to state-of-the-art baselines. These results indicate the superiority of FourierGNN over other state-of-the-art models for MTS forecasting.\n\n**Q1.**\n\nTherefore, the outstanding performance of FourierGNN on the COVID-19 dataset can be attributed to its ability to effectively capture and model the complex spatiotemporal dependencies present in the data.\n\nThe superior performance of FourierGNN on the COVID-19 dataset is reasonable and can be attributed to the significant spatiotemporal dependencies in the dataset. As shown in **Section E.1 Datasets**, the dataset is about COVID-19 hospitalization in the U.S. states of California (CA) from 01/02/2020 to 31/12/2020 provided by the Johns Hopkins University. The COVID-19 dataset exhibits characteristics that align well with the principles of infectious disease transmission across different regions over time. Consequently, the variables in the dataset demonstrate high correlation with each other, and the datapoints within each variable and across different variables exhibit temporal correlation. These characteristics make the COVID-19 dataset particularly suitable for evaluating the effectiveness of our proposed FourierGNN in capturing spatiotemporal dependencies.\n\nTo interpret/verify the capability of FourierGNN in spatiotemporal modeling for MTS forecasting, we conducted visualizations of the learned adjacency matrix from different perspectives:\n1) Temporal Adjacency Matrix: In **Figure 3 of Appendix H.2**, we visualize the temporal adjacency matrix of eight variables. The results clearly demonstrate that FourierGNN learns distinct temporal patterns for each variable (county), indicating that the hypervariate graph can encode rich and discriminative temporal dependencies.\n\n2) Adjacency Matrices in Different Layers: In **Figure 9 of Appendix H.2**, we display the adjacency matrices of variables in different layers of FourierGNN. The visualization reveals that the Fourier Graph Operator (FGO) can adaptively and effectively capture important patterns while removing noise, thereby enabling the learning of a discriminative model.\n\n\n3) Final Adjacency Matrices for Consecutive Days: In **Figure 10 of Appendix H.2**, we present the final adjacency matrices of variables for four consecutive days. These matrices highlight the time-varying dependencies among variables and showcase the feasibility of FourierGNN in exploiting such dependencies.\n\nOverall, these visualization results provide strong support for the superior performance of FourierGNN on the COVID-19 dataset, indicating its effectiveness in learning underlying node correlations and removing redundant correlations on the hypervariate graph.\n\nWe'll update paper to address the above aspects and hope we have addressed your comments."}]

Author rebuttal:
Dear Reviewers, ACs, and the SAC:

We thank all reviewers for their valuable comments. We response to all comments of reviewers; in particular, after carefully considering ndBv's comments, we realize there might be some potential misunderstandings. We've tried our best to clarify these misunderstandings in the specific rebuttal.

**Short-term vs long-term forecasting presents significant differences**
  + Long-term forecasting focuses on a long historical context to efficiently capture long-range dependencies such as periodic patterns and trends. In contrast, short-term forecasting often involves dealing with rapidly changing and dynamic patterns.
  + In the literature, the benchmark datasets for short-term and long-term forecasting are different. Long-term forecasting involves most datasets containing a few variables, such as Exchange (8 variables), ETTh, ETTm, ILI (7 variables), and Weather (21 variables). In contrast, short-term forecasting datasets contain more variables, for example, the datasets in StemGNN have at least 140 variables except the COVID-19 dataset, and the two datasets in AGCRN have 307 and 170 variables, respectively.
  + In deep networks, SOTA long-term forecasting models are mainly Transformer-based and MLP-based, while SOTA short-term forecasting models are mainly GNN-based models. This is because GNN-based models are more effective at capturing spatial correlations among variables and require sufficient variables to guarantee an appropriately sized graph, while Transformer-based/MLP models are more efficient at processing very long inputs/predictions.

In summary, our FourierGNN aims to learn spatiotemporal dependencies and is designed specifically for short-term forecasting. The experiments are consistent with the literature on short-term forecasting, compared with SOTA GNN-based models, frequency-based models, and short-term models.

**W3**
   1. We follow the experimental settings in short-term forecasting baselines, like LSTNet and StemGNN, and the forecasting horizon $\tau$ in our experiment is set to 3, 6, 9, 12.
   2. Based on the above discussion of the differences between short-term and long-term forecasting, as shown in the literature, it would be generally unfair to compare long-term baselines with short-term baselines, or vice versa. The response to W2 verifies this conclusion that the long-term baselines underperform FourierGNN on short-term forecasting.
   To further address your concerns, we have evaluated FourierGNN's long-term forecasting performance compared with PatchTST and DLinear. The experimental results are shown in **Table 2 in the attached PDF**. From the results, we can find that FourierGNN performs not very well, which is attributed to the fact that FourierGNN focuses on learning the united spatiotemporal dependencies, while long-term forecasting often focuses on long-term periodic patterns and trends.
   3. As discussed above, ETTm2, Exchange, Weather, and ILI are generally used for evaluation in long-term forecasting.

**W4**
1. Actually, in the literature, it is quite prevalent to employ a combination of Fourier transform (FT) and inverse Fourier transform (IFT) operations, including StemGNN, FEDformer, Autoformer, CoST, FiLM [1], and FreDo [2]. They transform time series into the frequency domain via FT, then perform calculations in the frequency domain, and finally conduct IFT to transform back the results to the time domain for subsequent operations. 
   - This is because the frequency spectrum in the frequency domain is complex-valued (consisting of a real part and an imaginary part), while data in the time domain is real-valued. It is essential and necessary to perform inverse Fourier transform to transform complex-valued frequency values to real-valued time domain values, other complex-valued outputs can not feed into a traditional (real-valued) neural output layer for real-valued forecasts.
   - According to the convolution theorem, we obtain that the recursive multiplication of FGOs (containing a pair of FT and IFT) in Fourier space is equivalent to multi-order convolutions (see **Proposition 1**). In other words, multi-order convolutions in the time domain can be efficiently conducted by leveraging FT and IFT (see **Eq. 7**), which is the core idea of this work. 
   - FT and ITF are linear transforms, which do not add or discard any information. 
   
   As we know, some models, such as BTSF [3] and TF-C [4], incorporate frequency domain and time domain features into enhancing time series representations. Since the frequency features in the frequency domain are complex-valued, to combine them with time domain real-valued features, these models **discard** the phase information and only take the frequency magnitude spectrum as **features**. Since the magnitude spectrum is real-valued, there is no need to perform IFT. They leverage spectrum information as features for **data augmentations**, while in our model, we take advantage of the efficiency of Fourier transform. These are two different paradigms.
2. We further perform an ablation study on METR-LA and ECG datasets to compare FourierGNN with its variants that obtain either the real part or the imaginary part of the frequency spectrum in FourierGNN. In this case, the inverse Fourier transform is removed in FourierGNN's variants. The results are reported in **Table 4 in the attached PDF** which shows the real part is more important than the imaginary part for the performance, and both the real part and the imaginary part are indispensable for FourierGNN.

[1]. FiLM: Frequency improved Legendre Memory Model for Long-term Time Series Forecasting. NeurIPS 2022
[2]. FreDo: Frequency Domain-based Long-Term Time Series Forecasting. CoRR abs/2205.12301 (2022)
[3]. Unsupervised Time-Series Representation Learning with Iterative Bilinear Temporal-Spectral Fusion. ICML 2022.
[4]. Self-Supervised Contrastive Pre-Training For Time Series via Time-Frequency Consistency. NeurIPS 2022

Meta-review: The paper introduces a novel approach for multivariate time series forecasting using Graph Neural Networks (GNNs). In contrast to previous methods, this paper addresses spatial and temporal dependencies by representing data as a hypervariable graph. The proposed FourierGNN employs matrix multiplications in Fourier space to efficiently handle the complexity of hypervariate graphs, achieving higher accuracy and efficiency on multiple datasets.

Reviewers raise concerns about the experimental setting as well as the reproduction of SOTA baselines. However, the value of the contributions outweighs these concerns. Acceptance is recommended, and it is encouraged to integrate the reviewers' feedback during the preparation of the final version of the paper.
Decision: Accept (poster)