Multivariate Time Series Forecasting By Graph Attention Networks With Theoretical Guarantees
Authors: Zhi Zhang
Weijian Li
Han Liu
Venue: Submitted to ICLR 2023 (2023)
Keywords: Multivariate Time Series Forecasting
Graph Attention Networks
Generalization Error Bound
Rademacher Complexity

Abstract: Multivariate time series forecasting (MTSF) aims to predict future values of multiple variables based on past values of multivariate time series, and has been applied in fields including traffic flow prediction, stock price forecasting, and anomaly detection. Capturing the inter-dependencies among variables poses one significant challenge to MTSF. Several methods that model the correlations between variables with an aim to improve the test prediction accuracy have been considered in recent works, however, none of them have theoretical guarantees. In this paper, we developed a new norm-bounded graph attention network (GAT) for MTSF by upper-bounding the Frobenius norm of weights in each layer of the GAT model to achieve optimal performance.  
Under optimal parameters, we theoretically show that our model can achieve a generalization error bound which is expressed as products of Frobenius norm of weight in each layer and the numbers of neighbors and attention heads, while the latter is represented as polynomial terms with the degree as the number of layers. Empirically, we investigate the impact of different components of GAT models on the performance of MTSF.  
Our experiment also verifies our theoretical findings. Empirically, we also observe that the generalization performance of our method is dependent on the number of attention heads, the number of neighbors, the scales (norms) of the weight matrices, the scale of the input features, and the number of layers.  
Our method provides novel perspectives for improving the generation performance for MTSF, and our theoretical guarantees give substantial implications for designing attention-based methods for MTSF.  


Under review as a conference paper at ICLR 2023
MULTIVARIATE TIME SERIES FORECASTING BY GRAPH ATTENTION NETWORKS WITH THEORETICAL GUARANTEES
Anonymous authors Paper under double-blind review
ABSTRACT
Multivariate time series forecasting (MTSF) aims to predict future values of multi- ple variables based on past values of multivariate time series, and has been applied in fields including traffic flow prediction, stock price forecasting, and anomaly detection. Capturing the inter-dependencies among variables poses one significant challenge to MTSF. Several methods that model the correlations between vari- ables with an aim to improve the test prediction accuracy have been considered recent works, however, none of them have theoretical guarantees. In this paper, we developed a new norm-bounded graph attention network (GAT) for MTSF by upper-bounding the Frobenius norm of weights in each layer of the GAT model to achieve optimal performance. Under optimal parameters, we theoretically show that our model can achieve a generalization error bound which is expressed as products of Frobenius norm of weight in each layer and the numbers of neighbors and attention heads, while the latter is represented as polynomial terms with the degree as the number of layers. Empirically, we investigate the impact of different components of GAT models on the performance of MTSF. Our experiment also verifies our theoretical findings. Empirically, we also observe that the generaliza- tion performance of our method is dependent on the number of attention heads, the number of neighbors, the scales (norms) of the weight matrices, the scale of the input features, and the number of layers. Our method provides novel perspectives for improving the generation performance for MTSF, and our theoretical guarantees give substantial implications for designing attention-based methods for MTSF.
INTRODUCTION AND BACKGROUNDS
Substantial time series data generated in the real world make multivariate time series forcasting (MTSF) a crucial topic in various scenarios, such as traffic forecasting, sensor signal anomaly detection in the Internet of things, demand and supply prediction in the supply chain management, and stock market price prediction in financial investment (Cao et al., 2020). Traditional methods simply deploy time series models, c.g., auto-regressive (AR) (Mills & Mills, 1990), auto-regressive integrated moving average (ARIMA) (Box et al., 2015) and vector auto-regression (VAR)(Box et al., 2015; Hamilton, 2020; Lütkepohl, 2005) for forecasting. Specifically, ARIMA, though one of the classic forecasting methods in univariate situations, fails to accommodate multivariate issues due to high computational complexity. VAR, as an extension of AR model in multivariate situations, is widely used in MTSF tasks due to its simplicity, however, it cannot handle the nonlinear relationships among variables, leading to reduced forecasting accuracy. In addition to traditional statistical methods, deep learning methods have been applied in MTSF problems and demonstrated potentials to solve these problems (Tokgöz & Ünal, 2018).
The long short term memory (LSTM)) (Graves, 2012), gated recurrent units (GRU) (Cho et al., 201 4), ( gated linear units (GLU) (Dauphin et al., 2017), temporal convolution networks (TCN) (Bai et al.. 2018), state frequency memory (SFM) network (Zhang et al., 2017) have found success in practical time series tasks. However, another important issue in time series data, complex inter-dependency (i.e., the correlations among multiple correlated time series), is still unaddressed in these methods, restricting forecasting accuracy (Bai al., 2020; Cao et al., 2020). For example, in the traffic forecasting task, adjacent roads naturally interplay with each other. Another example is stock price prediction, in which it is casier to predict a stock price based on the historical information of the stocks in similar categories, while information on stocks from other sectors can be relatively useless.
Graph is a special form of data that describes the relationships between different entities. Recently, graph neural networks (Scarelia et al., 2008) have achieved great success in handling graph data with development in
local connectivity, and compositionality. In general,

---

Under review as a conference paper at ICLR 2023
GNNs assume that the state of a node is influenced by the states of its neighbors. By disseminating information through structures, GNNs allow each node in a graph be aware of its neighborhood context. MTSF can be viewed naturally from a graph perspective. Variables from multivariate time series can be considered as nodes in a graph where they are interlinked each other through hidden dependency relationships. It follows that modeling multivariate time series data using GNNs can be a promising way to preserve their temporal trajectory while exploiting the inter-dependency among time series. In the meantime, due to the popularity of convolutional neural networks (CNNs), considerable studies attempt to generalize convolutions to graph-structured data, leading to the creation of graph convolutional networks (GCNs) (Duvenaud et al., 2015; Atwood & Towsley, 2016; Monti et al., 2018; Niepert et al., 2016; Kipf & Welling, 2017). GCNs model a node's feature representation by aggregating the representations of its one-step neighbors. Many studies have shown that GNN- and GCN-based methods outperform prior methods in time series forecasting tasks (Yu et al., 2017; Wu al., 2019; Chen et al., 2020). The graph attention network (GAT) (Veličković et al., 2017), one of the most popular GNN architec- tures, is considered a state-of-the- art neural architecture to process graph-structured data. Building on the aggregating approach of GCNs, in GATs, every node computes the importance of its neighboring nodes, and then utilizes the importance as weights to update its representations of the features during the aggregation. Compared to the well-known GCNs, GAT's have demonstrated equivalent, if not improved, performance across well-established benchmarks of node multiclass classification. Within the GAT framework, Guo et al. (2019); Deng & Hooi (2021) use adjust the correlations among multiple time series, showing better performance in accuracy over GNNs and GCNs.
models to adaptively
The numeric and experimental successes of GATs for MTSF notwithstanding, theoretical under- standings of the underlying mechanisms of GATs for MTSF are still limited: none of them has theoretical guarantees with respect to generalization error bounds, the most commonly used method to theoretically evaluate the prediction model.
The generalization error bound provides a standard approach to evaluate neural networks as it characterizes the predictive performance of a class of learning models for unseen data (Golowich et al., 2018). Therefore, understanding the generalization error bound of GAT's for MTSF will shed light on the relationship between the architecture of the GATs and their generalization performance for MTSF, advancing understandings of underlying mechanisms.
Studies show that deriving generalization error bound for neural network classes requires constraints on the size of weights. Bartlett (1998) first gave a generalization error bound for neural networks by bounding the size of the cover of neural network function classes, suggesting that the bound depends on the number of training samples and the size of weights, rather than the number of weights. In the following studies, the empirical Rademacher complexity (ERC) was shown as an essential component of generalization error bound for neural network classes. Bartlett & Mendelson (2002) introduced the generalization error bounds using the Rademacher complexity of the function classes that include neural networks with constraints on the magnitudes of weights for binary classification. Bartlett et al. (2017) then presented a margin-based generalization error bound using the Rademacher complexity of neural network function classes with the spectral norms of weight matrices being controlled for multiclass classification. Neyshabur et al. (2015) used the Rademacher complexity bounds showing that the generalization error of deep neural networks can be upper bounded by a bound in terms of the Frobenius norms of weights. Golowich et al. (2018) further demonstrated that the generalization error bound for deep neural network classes with bounded Frobenius norm of weights can be independent of the number of layers and the width of each layer if employing proper techniques. These methods are also extended graph-based neural networks. Garg al. (2020) derived the generalization error bounds for GNNs using Rademacher complexity for binary classification. Lv (2021) provided the generalization error bound for GCNs via Rademacher complexity for binary classification.
Contributions. In this study, to capture the inter-dependencies among variables of MTSF, develop GAT-based method for MTSF; to secure the generalization error bound, we require the norm of weight matrix in our model to be bounded; to evaluate the performance of our method, we compare our method with two SOTA methods and show our method outperforms over these prior methods. We also provide the theoretical generalization error bound for our method, aiming to develop models with desired generalization error for MTSF.
Specifically, we derive the generalization error bounds of two-layer GAT models for multi-step MTSF task. We also extend our generalization error bounds deep GAT models with more than two layers. Generalization error bounds derived in this study are based on the bound of ERC of GAT models with the weight matrix norm being controlled. This approach is characterized by controlling Frobenius norm of the hidden layer weight matrix, a common method to derive the norm- based generalization error bounds for DNNs CNNs, and GNNs. In particular, we show that ERC derived for GAT models for MTSF has a polynomial dependence on the number of neighbors considered
2

---

Under review as a conference paper at ICLR 2023
in attention representation and the number of attention heads being used. The aforementioned ERC is also dependent on the product of norms of weight matrices of each layer, the L2-norm of the input feature vector, and the Lipschitz constant of loss and activation functions. To further understand the effectiveness of GAT's for MTSF, in addition to theoretical analysis of the relationships between components of the GAT model and this bound. we also investigate the influence of different components of GATs models on the performance of MTSF using experiments with complex stock price data. Our experimental results consistent with theoretical findings. To our best knowledge, we develop the first GAT -bssed method for MTSF with theoretical guarantees.
PRELIMINARIES
2.1 PROBLEM FORMULATION
In this paper, we focus on the task of MTSF, considering multivariate situation that con- tains N correlated univariate time series represented as (.1..... EN], where use X, (x, x.......) to denote a sequence of time series from time step to infinity. Based on sequence of historical T time steps of values prior to current time t, our goal is to predict the multi-step-away value of ..I.....YYN
using an appropriate prediction model f. where each y: = (y . y.,+c) } has values from C timestamps. In addition, the historical inputs can be representative of multiple aspects if complemented with auxiliary features, so our problem can be characterized as .. YN [[((x....... X1,t-T+1 ....., (XN....... -N. }). To accu- rately capture the inter-dependency. the problem is formulated the graph structure introduced below.
2.2 THE GRAPH STRUCTURE
Now consider undirected graph 9 = (N, N= (n1....,NN), W N. is set of node labels representing the sources of N time series. & C x is the set of edges representing the connection between series. We let x; E X, E [N] be a random variable representing the input feature vector of node n, for time series For node i, its random input feature x; E X C RDD is a multi-dimensional vector, which contains all the historical values from 7 time steps, in other words, we x; = (Xitt...., X1,+-++1 be the concatenation of time steps; true label y; E C R the vector for the C-step-away values. During the learning period, some nodes, which will be treated as the training set, know the C-step-away true values y. We denote the set of indices of those nodes as M C N such that M = [M] < N. And for each node in the M. we order them based on their node labels nı and re-index them based on their order number, j E [M]. Here the random input and labels are S = {(11, V1), )
(XM, (M)) } over M. In the following paragraphs, will introduce the GATs for our problem.
2.3 GATS MODEL
We consider the GATs defined by Veličković et al. (2017), given the random feature matrix X L-layers GAT model f. and the final output Z()).
[x1, , x.
(c))= = [f(x)] f(x.)
= P(L) ok a (P(L-1) ... 0 (P of a PPa.,)WW.. W ((2)) ...Wa-)) Way
In GAT with more than two layers, the output of the hidden layer /
Z o (1,)) (Lx) W (a,s)),
(1)
Here we use subscript (1) or (1 1) to indicate which layer the variable belongs to. We have I 21....... 1}, and Zo= X.
Here, W ((.,) Di is - 1-to-l weight matrix for hidden layer with Dj feature maps. Here a is the activation function.
And we let ( denote the concatenation for the attention heads. This definition is specific to the GATs, with its detailed description found in Veličković al. (2017). And we have total K such matrices in layer I with each matrix W (I.A) corresponding to one attention head. ((I,)), P(2) and P (I.-1) are the attention matrix introduced by us, and further function as an operator to incorporate the attention. We will justify its equivalence to the original GAT models (Veličković et al., 2017) in later paragraphs.
3

---

Under review as a conference paper at ICLR 2023
Even though analysis covers GATs with more than two layers, will give a focus two-layers GATs model, which is also implemented by Veličković al. (2017), with the following simple form:
(2) =
= P() $k=1 a (P(.)) ((2)-
The first layer consists of K attention heads computing Dj features each (a total of K x Dj features), followed by an activation function o. Here, (1.A) E 1 P1 is an for hidden layer with D1 feature maps, and we have K such matrices.
hidden weight matrix
The second layer is used for prediction: a single attention head that predicts the y. For C-step-away forecasting, we have D₂ C. The W (2) E &RKDiXC is hidden-to-output weight matrix.
Attention Model We now give more explanation about the attention introduced the GAT model. In section 2 of the original GAT paper. Veličković et al. (2017) mentioned the learnable linear transformation to transform the input features into higher-level features with sufficient expressive power. In their process, they first apply shared linear transformation, parameterized by the weight matrix, W E P to every node. Then they perform self-attention on the node: a shared attentional mechanism a Di x P1 + R computes attention coefficients Eij = a(x; W x W). indicate the importance of node j's features to node i. They also inject the graph structure into the mechanism by performing masked attention: they compute Ezy for nodes j E NN (t). the neighhors of node i, which might include node itself. Then they normalize the coefficients to make them easily
comparable across different nodes using the softmax function to obtain p
ex,
p o(e,,,,, 2i,2,...))
ZkN((i exp Ei,b
Then the output features from the first layer for each node will be: a( a(EjeN(0) p W). They also propose the K-head attention. The K independent attention mechanisms execute the afore- mentioned transformation, and then their output are concatenated, resulting the following feature representation: , (EjeN() P(K)
W (K))).
To make the above process more integrated, here in the GAT models, we introduce the attention matrix P that contains the normalized attention coefficients used to compute a linear combination of the neighborhood features. yielding the new feature representation for every node. This matrix contains individual node's importance weights with every other node in its neighborhood.
E LL 1]. is the matrix of the graph attention ma- trix defined by the attention coefficients 1 We use No I N as the fixed num- ber of neighbors for each node. And let ((n) be the of neighbors for node
Let Pi E NNN,
Pūt E [0, is the coefficients of node attributed from node Each row sum of the Pay is equal to I, Here
ae
P/D (0)
Lk (())
P())
Pū)
(()
(i.km)
NN(I)
which EcEN(()) P(j) P(La) (row n of P P(.,)) denotes node n's 's all coefficients, which are com- puted by
P())
P(n)
P())
N.g
Pi)
N.j
0
(3)
(N.J)=
(4) where is softmax function, used calculate the importance weight from other nodes. The Na..) IR Dex1 is convolutional filter with filter size equal to 1 x 1 and output channel size equal to 1. The un is the n's entry of ((1-1) W (t.K) (1.,)NN N(.a)- And M is a mask matrix with M,,e = 1 for E [N] and e E (n),,, and 0 otherwise, and is the element-wist product, IN is the size N vector with all entries equal to 1. In the paper by Veličković et al. (2017), )) the proposed attention mechanism consists of the following steps: firstly apply another convolutional filter N to the W, secondly get the attention coefficients Gij x WN x WN. We integrate the result of this whole process into attention matrix P (t). which functions exactly as the attention mechanism in the original architecture introduced by Veličković et al. (2017). Since the sum of row elements of the P equals one, we have the following property hold for P(n: (P S N, i... the Forbunis norm of P (1) is bounded by the total number of nodes.
P(i,) = o (M- Z(--1 W(.s (a. ((.A) un 1N] 12) ER
sum up these representations
In the final layer, we have P(L)) E TR M since obtain output for the nodes in M.
4

---

Under review as a conference paper at ICLR 2023
2.4 THE EMPIRICAL RISK FRAMEWORK FOR MTSF
We first introduce function spaces of GATs for MTSF. Let the X' and y be the feature and true label spaces, respectively, and Q unknown distribution over X' x y. Let F C V be the hypothesis class for predictions, where V is another space that might be different from V. In our paper, the function space F be the space our GAT classes that contains the GAT functions f. We defer the detailed definitions of F in later sections, i.e. terms of Weights- bounded GATs for the MTSF problem, see the definition 15.
let
Given F, X, and V we let V x - [0, B] be the loss function defined over F. We assume that g is bounded, i.c., the range loss is [0, BJ. Additionally, we require = 1 (if not, we can scale the loss function) without loss of generality.
We also introduce the function class gF C [0, B] Xxy by composing the functions JF with g(+,)) +).
i.c., 9F = y(x,)) 7 y) FE.
For any risk function g defined over F, given the training set S (i). (XM. which includes M i.i.d samples from X' x y according to distribution Q, the expected/populatioon risk E(f) and the empirical risk function E(f) defined as:
E(J)
E lol(()))))) (x.y)~ (xc.)~a
(5)
E(f)
1 M
Σ I g((())))))) j=1
(6)
predictor f F can be generalized if for any > O, lim s
E(ʃ) B(J)
A predictor with generalization guarantee is closely related to the complexity of its hypothesis space. In that sense, the generalization error bound for F is characterized by the condition where E(f) is bounded by the summation of E(f). the ERC that generally the dominating term, and an error function associated with the confidence the bound and the sample size M.
2.5 THE RADEMACHER COMPLEXITY
(f:x>> f(x)} is model space. We define the ERC R(F)ann Rademacher complexity R.((F) as
Suppose F
Rs(F)
E R(F),
R(F)
sup M fEF
Σ {x[(x,) , XN
SnQ
(8)
where (c ) are i.i.d. Rademacher variables satisfying P P(g = 1)= P (cj = 1) = 1/2.
3 GENERALIZATION BOUND FOR THE GAT MODEL.
3.1 NOTATION
We use bold-faced letters to denote vectors and capital letters to denote matrices or fixed parameters (which should be clear from the context). Given vector w E E., /|w|] refers the Euclidean norm,
2/p
and for 2 1, ||wllp (E /w:/P)
refers to the Lp norm. For a matrix W. | Pr refers to
the Frobenius norm, ||W] |F E. |wis function f R + Rm is L-Lipschitz, L 2 if [[)( f(b)]l < L L|aa- bll for all a, E R", We use standard big-O notation, with [2()), e(-), and O(-) hiding constants.
3.2 FUNCTION CLASS GATS
Given the inputs = .x.,..., xN) ) as multiple time series with each x, as input feature for node n, the class of 2-layer GATs for MTSF if maps x to the output fxx) that represents C-step-away prediction expressed in equation 2. And We consider subset of such class requiring each / with bounded weight norm, expressed as
F x f(x,) RC; W S M1. w s M2.j j [M].
(9)
5

---

Under review as a conference paper at ICLR 2023
here use fx,) mean the output of f corresponding node j, where [M,, and know the true label yj this node.
Furthermore, we also provide model space F C R with single dimensional output that corresponds to the c-th component of model output from f(x) for the c-th time step, expressed
F = fx
f(x)), [Walll f(x)) S Mi.
w s
M2, c e [C], [M]
(10)
3.3 AN UPPER BOUND OF RADEMACHER COMPLEXITY OF GAT CLASS
Here we first provide an upper bound of ERC of GAT class J for single dimensional output of MTSF.
Theorem (Upper Bound of ERC of GAT class F MTSF), Let the activation function (.) be Tip-hicch continuous, and also satisfy (0) 0 and o(az) (x) for all 2 O. Assume
the Le-norm of the feature vector x comes from a bounded domain X = {x: ||x]] <. B}. Assume the Frobenius norm of every weight matrix in the first layer of the GAT' class is bounded, namely,
| (W.lll S M1 with some constant M1 > 0 for every Also, the norm of the weight vector of
the second layer of the GATs is also bounded, [wiel] S M2,, where e E [C], with some constant M2 > Let N; denote the neighborhood of node i (including i), let the number of neighbors of each node is equal to each other, namely. for some common constant N N+, assume N := | for consider the most general formulation, which allows every node to
all node E N, furthermore, attend on every other node, i.e., No- N. Then let R(F)) be the ERC defined in the definition 7 for GAT class F in the definition 17, given the M sized input set {x1,.... XM }, then we have
R(F) ( BK (K))1/ 1/2 1/2 M2).
We that this bound has polynomial dependence on the N. the total number of nodes. The N appears here due the fact that we consider all the nodes neighbors, which can be replaced by the No. the number of neighbors. small No N can result potentially smaller bound. The proof details can found in SA.
3.4 GENERALIZATION ERROR BOUND OF THE GAT CLASS FOR MTSF
In this section, we will give the final generalization error bound of the GAT class for MTSF. The formal result is in the following theorem and the proof is in $B.
Theorem 2. Define the hypothesis class F the definition 15. We suppose g is Lipschitz with constant Log. Then for any (0, 1), with probability least 5, all J E we have
(2/2/8)
E(f) < ((f)+ + +3
2M
where we have R(F)) OL,,
from Theorem
4 EXTENSION TO GAT CLASS WITH LAYERS L >
Now we extend the analysis to GATs with more than two layers for MTSF and provide corresponding generalization error bounds. Here, the proof is done by simple induction argument using the "peeling-off" technique employed for Rademacher complexity bounds for neural networks. The output of L-layer GATs represents multi-step-ad step-away prediction shown in expression 1.
We define the function class over M, according to the definition of the GATs network, with
(11) Furthermore, we require that the Frobenius norm of every weight matrix every layer of the GAT class is bounded, namely, for any 7 E [7], [Wa.)) (aa.))l || & M2 with some constant M, for every k.
F- f(x,) E E : < M.....,
wiol < Mr, [C].j e [M]

---

Under review as a conference paper at ICLR 2023
Also, we have single dimensional GAT function space defined
F' fx f(x;)) F [C].j E [M]]
(12)
Also, the output up to layer 1, E [ 10-1, 11. has the format as,
[ ..... f((...((xx))))) [((xx))
= 0k P(
Ka
(
o Ki k1= a (Pa.a) W )..)..
...Wo))
e ER.
(13)
Thus, we define layer-wised class of functions
= (si x Ji(x;) E IR,;, ((a,)) Ip S MI..... || (a.alll < MGj E [M]-
(14)
We provide an upper bound of ERC of GAT class J with L layers with proof details in &C Theorem 3 (Upper Bound of ERC of GAT class F with L layers). Let all the assumptions from Theorem be fulfilled. Furthermore, let the Frobenius norm of every weight matrix the first L- layers of the GATs be bounded, namely, || [| (1,) ll S M1 with some constant Mi ffoor every k.
Also, the norm of the weight vector of the last layer is also bounded, with some constant Mr > Let R(F)) be the ERC defined in Equation 7 for GAT class F in the definition 12, given the M sized imput set (XI,...XMM}} then we have
Wirs| S ML, where e E (C),
= (OF)) II M((NN 1/2
Based on the theorem 3, we provide the generalization error bounds for the GAT class with more than two layers in the following theorem.
Theorem 4 (Generalization Error Bounds for the GAT Class with More than Two Layers). Given any real E (0, 1), with probability at least 1 5, for any J E defined the definition 11, which contains L-layer GATs, and given the M sized training data set S ((x1,1))....... Y we
have the generalization error for MTSF is upper bounded as
In(2/8)
B(f) & B( + +222CI,R(FF) + +3/
2M
where R(F*) is calculated in theorem 3.
To give the generalization ERC, we apply the layer-peeling strategy that the ERC of L-layer networks expressed by factor multiplied by the ERC of I-layer networks. Specifically, we consider this factor as the matrix Frobenius norm, and our current bounds scale with the product of these norms as the layer size increases. However, the number of attention heads and the number of attention neighbors appear as the polynomial terms with order roughly equal to the number of layers L. The bound has an exponential dependence on the network depth.
bound of deep GAT, we firstly derive its ERC. To bound the
The generalization eтгог bound Theorem implies that the following attempts can be taken to reduce the generalization error: i) increase the training samples, ii) minimize the empirical loss, and iii) design the neural network carefully to achieve a proper hypothesis class. Increasing the complexity of the hypothesis class can decrease the approximation error but also increase the estimation error due to a large ERC, which leads undesired test performance in practical task. In the next section, we will empirically show how structural components of GATs related complexity could affect the test performance for a MTSF task, providing empirical support for our thcoretical findings.
EXPERIMENT DETAILS
Our goal is to show the relationship between the upper bound of the generalization error of the GAT model and variables the ERC, including the number of attention heads, the number of neighbors, the Frobenius norm of model weights, the number number of labeled nodes. We use the daily stock price data from Nasdaq and NYSE. The multivariate time series have about 1500 stocks. For each stock, the meek historical data is used to predict future returns. For every stock, we assume that every feature is i.i.d. per day. By default, we use three-layer (input layer, hidden layer, and output layer) GAT to do single-step forecasting on the
model layers, the norm of inputs, and the
7

---

Under review as a conference paper at ICLR 2023
returns of each stock. For each variable, we try its various values with all other variables's values fixed. We repeat the experiment 20 times and report the loss on the out-of-sample test dataset to represent its generalization error. We use minimum square enror (MSE) as evaluation metrics". 2.
EXPERIMENT RESULTS
10
Olzt 1),b
y- 0je )
8-
Cimeraliationio
Gesernizzation
6-
2-
2-
0-
111
20
30
Number of utteation heads
Numberr of neighhors
Upper baurd of weightt norm
(a)
(b)
(c)
012%)
O(z)
O1a-1133
10
Gemesttzation Dees
Generalizaoon
2-
1-
4-
10
1.5
20
25
0.2
0.8
Number hidden layers
Upper bound Inputs
Number of labeled uodes
(d)
(e)
(f)
Figure 1: Experiment results six variables in the ERC. We run the experiment 20 times and obtain a standard deviation of the generalization error. (a) relationship between test loss and the number of attention heads. (b) relationship between test loss and the number of neighbors. (c) relationship
between test loss and the upper bound of weight norm. (d) relationship between test loss and the number of (hidden) layers. (e) relationship between test loss and the upper bound of input norm. (f) relationship between test loss and the number of labeled nodes. The red line is possible thcoretical upper bound. The plots show that all test losses generally conform the big O of the theoretical upper bound.
Number of Attention Heads K. For three-layer GAT', Theorem 3 indicates that with the increasing number of attention heads in the attention layer, the upper bound of ERC is y = O(K)). The experiment results in Figure shows test error beginning to increase quadratically after some values of K. This is consistent with our theoretical results on the generalization error bound.
Number of Neighbors Ne. For three-layer GATs, Theorem 3 indicates that with the increas- ing number of neighbors considered for the attention operation, the upper bound of ERC is y = ON 1-/2
Figure 1 demonstrates that as the N, increases, the test error conforms to this theoretical error bound. But it is noteworthy that when the number is too small, the loss is also high. It is possible that at certain range, the influence of the information loss due to the limited number of neighbors is dominant.
Norm of Weight Matrix Mj. We also have an empirical evaluation on the relationship between the generalization error bound and the Frobenius norm of GAT models' weights. Theorem indicates that with the increasing bound of the Frobenius norm, the upper bound of ERC increases polynomially. The experiment results in Figure corroborate the conclusion. When the weight norm increases, the
IIt known MSE loss not Lipschitz continuous over y. however, since we consider finite hypothesis class satisfying bounded input and weights conditions, the output GATs bounded, thus, the MSE locally Lipschitz continuous function.
8

---

Under review as a conference paper at ICLR 2023
generalization error first decreases, then increases. The reason for the initial decrease is because the bound on the norms is so small that it severely prevents the weights from having enough amount of updates. Thus, the scales (norms) of the weight matrices should be neither too large (induces large generalization error) nor too small (harms weights' updates) and choosing proper scales is important in practice as the current work has shown Li ct al. (2018).
Number of Layers (Model Depth)- - I. Theorem 3 and Theorem 1 indicate that the upper bound
of ERC increases exponentially with an increasing number of layers. suggesting that the number of layers has negative impact on the test performance of GATs for MTSF. However, Sun et al. (2016) reported that deeper nets which have larger representation power are able to fit training data better and achieve smaller empirical error. This observation indicates a positive impact of the number of layers' positive on the test performance for MTSF. Our empirical results are consistent with the above discussions about the double-edged edged impacts. The experiment results are shown in Figure and indicate that as the number of layers increases, the test ertor first decreases, and then increases. This observation indicates that if the ERC increases quickly, the representation power cannot compensate for the negative impact of the increased number of layers.
Norm of Inputs - B. The experiment results in Figure show that when the input norm is greater than certain values, the generalization loss the GAT has a linear relationship with the upper bound of the input norm. This empirical observation aligns with Theorem 3.
Number of Labeled Nodes M. Theorem also indicates that when the number of labeled nodes increases, the generalization loss of the GAT decreases and the upper bound of the generalization loss is y = O 1/2). The empirical results in Figure 1 confirm this relationship.
We include the details about how we control the above six variables in D.2. In addition, we conduct experiments on two-layer GAT's to show that empirical results are also consistent with error bounds in Theorem 1. Results and discussions are in $E.
It is noteworthy that Figure also shows that the test error decreases initially, then starts to increase as Theorem 3 suggests. The inconsistency at the beginning could be brought about by other factors that affect the test error. As seen in the Theorem 4, in addition to the ERC, the training error also contributes to the upper bound. Nevertheless, the ERC becomes dominant by increasing the number of attention heads, the number of neighbors, the upper bound of weights norm, and the number of hidden layers, indicating the importance of a proper design of neural networks for MTSF to guarantee smaller test error. Among all the above factors that affect the generalization error, since the order of the upper bound of the weights norm is the highest, properly controlling the upper bound of the weights norm is especially significant.
As reported in the previous literature (Wu et al., 2021), in- creasing the complexity hypothesis class in terms of larger weight matrices bounds could decrease the approximation error, but may also increase the estimation error, which corresponds to the second term of RHS in Theorem 4.
1.8
1.6
Geveralization loes
Therefore, in practical training process, we generally start with a simple neural network and gradually increase its complexity in terms of larger weight matrix bounds to improve the test performance, and the bound can be tuning parameter in our model. We call it weight control.
1.4
1.2
To show the meanings of weight control, we further de- veloped an improved version of the GAT called Weights- bounded GAT. And we conduct an additional experiment to demonstrate its improvement over the vanilla GAT. As the name suggests, the weight Frobenius norm of each layer is bounded by a hyperparameter. We compare the Weights-boundeer GAT with the vanilla GAT using test loss on the above stock return forecasting task. We repeat the same train-test pipeline 20 times and collect 20 test losses for each model. As Figure 2 shows, the Weights- bounded GAT performs much better than the vanilla GAT. While the neural network training process can only minimize the training error and has no guarantee on generalization error. this generalization error bound analyzed in this study is more useful in the sense that it provides solid guideline on GAT structure design to improve the models generalization performance for MTSF.
Weightsshnnnddd GAT
Vanilla
Test loss of two types of GATs. The train-test pipeline runs 20 times over 20 random seeds. The Weights- Weights-bounded GAT has better test loss than the vanilla GAT regarding the minimum, maximum, first quantile, third quantile and the me- dian of the test loss.
Figure 2:

---

Under review as a conference paper at ICLR 2023
7 ETHICS STATEMENT
We have read the code ethics carefully and ensured that our paper conforms them.
8 REPRODUCIBILITY STATEMENT
We make our best effort to ensure the reproducibility of the paper's experiments and provide clear guidelines. More specifically, we include detailed experiment setup information in D.I. Besides, we give detailed description on the architecture of the neural network we use and we explain how control and adjust different variables in D.2. We list all the important hyperparameters' and their default values in D.3. We give the website link for the dataset we use D.4. There is no extra data processing steps to be conducted. All the work is done in the code an end-to-end manner. We also give the link to the source code in D.5.
We explain all assumptions of our theorems (Theorem 1, 2, 3, 4) clearly, and provide the complete proof of the theorems in the appendix $,, SB, and $C.
10

---

Under review as a conference paper at ICLR 2023
REFERENCES
James Atwood and Don Towsley. Diffusion-coonvllutionall neural networks. Advances neural information processing systems, 29, 2016.
Dzmitry Bahdanau, Dmitriy Serdyuk, Philemon Brakel, Nan Rosemary Ke, Jan Chorowski, Aaron Courville, and Yoshua Bengio. Task loss estimation for sequence prediction. arXiv preprint arXiv:1511.06455 2015.
Lei Bai, Lina Yao, Can Li, Xianzhi Wang, and Can Wang. Adaptive graph convolutional recurrent net- work for traffic forecasting. Advances in neural information processing systems, 33:17804-1788 2020.
Shaojie Bai, J Zico Kolter, and Vladlen Koltun. An empirical evaluation of generic convolutional and recurrent networks for sequence modeling. arXiv preprint arXiv:1803.01271, 2018.
Peter L.. Bartlett. The sample complexity of pattern classification with neural networks: The size of the weights is more important than the size of the network. IEEE Trans. Inf. Theory, 44 (2):525-536, 1998. URL http:/ /dblp. uni-trier. http://c/c////ooo///as/saaaa html #Ba 98
Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463-482 2002.
Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally-normaaizee normalized margin bounds for neural networks. Advances in neural information processing systems, 30, 2017.
George EP Box, Gwilym M Jenkins, Gregory Reinsel, and Greta M Ljung. Time series analysis: forecasting and control. John Wiley & Sons, 2015.
Defu Cao, Yujing Wang, Juanyong Duan, Ce Zhang, Xia Zhu, Congrui Huang, Yunhai Tong, Bixiong Xu, Jing Bai, Jie Tong, et al. Spectral temporal graph neural network for multivariate time-series forecasting. Advances in neural information processing systems, 33: 33:17766-17778 2020.
Weiqi Chen, Ling Chen, Yu Xic, Wei Cao, Yusong Gao, and Xiaojie Feng. Multi-range attentive bicomponent graph convolutional network for traffic forecasting. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pp. 3529-3536, 2020.
Jianpeng Cheng, Li Dong, and Mirella Lapata. Long short-term memory-networks for machine reading. arXiv preprint vrXiv:1601.067333 2016.
Kyunghyun Cho, Bart Van Merriënboer, Dzmitry Bahdanau, and Yoshua Bengio. On the properties of neural machine translation: dncoder-decoder approaches. arXiv preprint arXiv: 1409.129, 2014.
Djork-Aréé Clevert, Thomas Unterthiner, and Sepp Hochreiter. Fast and accurate deep network learning by exponential linear units (elus). arXiv preprint arXiv:1511.07289, 2015.
Yann N Dauphin, Angela Fan, Michael Auli, and David Grangier. Language modeling with gated convolutional networks. In International conference machine learning, pp. 933 941. PMLR, 2017.
Ailin Deng and Bryan Hooi. Graph neural network- based anomaly detection in multivariate time series. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 4027-4034 2021.
Simon Du, Kangcheng Hou, Russ R Salakhurdinov, Barnabas Poczos, Ruosong Wang, and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels, Advances in neural information processing systems, 32, 2019.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams. Convolutional networks on graphs for learning molecular fingerprints. Advances in neural information processing systems, 28, 2015.
Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. In International Conference Machine Learning, pp. 3419-3430. PMLR, 2020.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. In Conference On Learning Theory, pp. 297-299. PMLR, 2018.
11

---

Under review as a conference paper at ICLR 2023
Marco Gori, Gabriele Monfardini, and Franco Scarselli. A new model for learning in graph domains. In Proceedings. 2005 IEEE international joint conference on neural networks, volume 2, pp. 729-734, 2005.
Alex Graves. Long short-term memory. Supervised sequence labelling with recurrent neural nelworks, pp. 37-45, 2012.
Shengnan Guo, Youfang Lin, Ning Feng, Chao Song, and Huaiyu Wan. Attention based spatial- temporal graph convolutional networks for traffic flow forecasting. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pp. 922 22-929, 2019.
James Douglas Hamilton. Time series analysis. Princeton university press, 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-777 2016.
Simon Jégou, Michal Drozdzal, David Vazquez, Adriana Romero, and Yoshua Bengio. The one hundred layers tiramisu: Fully convolutional densenets for semantic segmentation. In Proceedings of the IEEE conference on computer vision and pattern recognition workshops, pp. 11-19, 2017.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 1ef2..4412.9960 2014.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks 2017. ArXiv fbs/1609.02907, 2017.
Vladimir Koltchinskii and Dmitry Panchenko. Empirical margin distributions and bounding the
generalization error of combined classifiers. The Annals of Statistics, 30(1):1-50, 2002.
Sulabh Kumra and Christopher Kanan. Robotic grasp detection using deep convolutional neural networks. In 2017 JEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 769-776. IEEE, 2017.
Xingguo Li, Junwei Lu, Zhaoran Wang, Jarvis Haupt, and Tuo Zhao. On tighter generalization bound for deep neural networks: Cnns, resnets, and beyond. arXiv preprint arXiv: /806. 05159, 2018.
Renjie Liao, Raquel Urtasun, and Richard Zemel. A pac- bayesaa approach generalization bounds for graph neural networks. arXiv preprini urXiv:20/2.0702 2.07690, 2020.
Helmut Lütkepohl. New introduction to multiple time series analysis. Springer Science & Business Media, 2005.
Shaogao Lv. Generalization bounds for graph convolutional neural networks via rademacher com- plexity. arXiv preprint arXiv:2102.1022. 2021.
Andreas Maurer.
vector-comtraatioon inequality for rademacher complexities. In International Conference on Algorithmic Learning Theory, pp. 3-17. Springer, 2016.
Terence C Mills and Terence C Mills. Time series techniques for economists. Cambridge University Press, 1990.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar, Foundations of machine learning. MIT press, 2018
Federico Monti, Karl Otness, and Michael M Bronstein. Motifnet: a motif-based graph convolutional network for directed graphs. In 2018 IEEE Data Science Workshop (DSW), pp. 225-228. IEEE, 2018.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Conference on Learning Theory, pp. 1376-1401. PMLL 2015.
Mathias Niepert, Mohamed Ahmed. and Konstantin Kutzkov. Learning convolutional neural networks for graphs. In International conference on machine learning, pp. 2014-2023, PMLR, 2016.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabricle Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):11-80 2008.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. The journal of machine learning research, 191911929-1955 2014.
12

---

Under review as a conference paper at ICLR 2023
Shizhao Sun, Wei Chen, Liwei Wang, Xiaoguang Liu, and Tie- Yan Liu. On the depth of deep neural networks: A theoretical view. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
Alper Tokgöz and Gözde Ünal. A ran based time series approach for forecasting turkish electricity load. In 2018 26th Signal Processing and Communications Applications Conference (SIU), pp- 1-4. IEEE, 2018.
Gal Vardi, Ohad Shamir, and Nathan Srebro. The sample complexity of one-hidden-layer neural networks. arXiv preprint arXiv:2202.06233, 2022.
Ashish Vaswani, Samy Bengio, Eugene Brevdo, Francois Chollet, Aidan N Gomez, Stephan Gouws, Llion Jones, Lukasz Kaiser, Nal Kalchbrenner, Niki Parmar, al. Tensor2tensor for neural machine translation. arXiv preprint 1803.0740 2018.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua 2017.
Bengio. Graph attention networks. arXiv preprint
Saurabh Verma and Zhi-Li Zhang. Stability and generalization of graph convolutional neural networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1539-1548, 2019.
Zhe Wu, David Rincon, Quanquan Gu, and Panagiotis D Christofides. Statistical machine learning in model predictive control of nonlinear processes. Mathematics, 9(16),991,, 2021.
Zonghan Wu, Shirui Pan, Guodong Long, Jing Jiang, and Chengqi Zhang. Graph wavenet for deep spatial-temporal graph modeling. arXiv preprint arXiv: 00121, 2019.
Bing Yu, Haoteng Yin, and Zhanxing Zhu. Spatio-temporal graph convolutional networks: A deep learning framework for traffic forecasting. arXiv preprint arXiv:1709.04885, 2017.
Liheng Zhang, Charu Aggarwal, and Guo-Jun Qi. Stock price prediction via discovering multi- frequency trading patterns. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pp. 2141-2149, 2017.
Shuai Zhang, Meng Wang, Sijia Liu, Pin-Yu Chen, and Jinjun Xiong. Fast learning of graph neural networks with guaranteed generalizability: mee-hidden-layee case. In International Conference on Machine Learning, pp. 1 1268 11277. PMLR, 2020.
13

---

Under review as a conference paper at ICLR 2023
APPENDICES To MULTIVARIATE TIME SERIES FORECASTING BY GRAPH ATTENTION NETWORKS WITH THEORETICAL GUARANTEES
A PROOF OF THEOREM
Here we will derive the upper bound of ERC of two-layer GAT's with on-dimensional output for the single-time prediction.
As mentioned in section 2.3, our GATs model's second layer ((2) uses Z(1) E RRN as input, and outputs ((2) E RxC The input to the first layer ((1) is a set of node features
X
XN),
where each X; E RD, is the number of features in each node. The first layer produces Z(1) with each ((()) E RRD,, The Z is composed by concatenation of K outputs from the K identically structured attention layers (1.8), with each output denoted as
H (1,a) (1,,) (W(,)))
Now we write the output vector of GATs for all classes node j. E [M] as,
KD
N
der w
(1,A) E Ephiaaerua
(2)
kr=1
because we already have indexes & E [K] and r E [Dr]. And it is easy to show that above output can be easily written in vector format:
Here we use index notation kr E [KD) D2]
KD:
N
K
N Σ Eehiss (WaL)))))
(2)
kr=1
where ((LA)) represents the column r of W(1,)), ((2) represents the row kr of W (2), and w(2)
represents the column of W (22)- Then the class of functions defined over the subset of the node set M, |M| = M, will be
KD; Σ
Σ P(),)) ( (Maa)))))) ERC;
F ((x))
P
(2)
o
(15)
k=1
S Ma..j mM]
| S Mi,
w(es)
(16)
Furthermore, we also provide model space with single dimensional output that corresponds c-th component of model output from f(x) for the c-th time step. Now we write the output of node n of time-step of ((2) as
KD. kr.C (2)
N
K
F
N
je (()
Tut
de (1.k)
li
((2
kym1
1=1
dm
and its vector format is
K
j.c (2)
kr.
n.t
Σ
Eptias of ((in))((rn))))))
P(2)
kr=l
Now let hypothesis class F C F. be set of functions on x E X. Specifically, we have such single dimensional GAT function space defined as
KD Σ
N
K
N ( (WiLA)>xi)
F
x + 1(x;)
Σ i=
2. P(1,)))
(2)
kr=1
1=1
k=
(17)
W (1.,)) l1.
< M1, w
< M2, [C],1 [[M]
14

---

Under review as a conference paper at ICLR 2023
We have the first layer's matrix to be
(1,)) (wa.))...., w. waio
The output of first layer 4 is
Z 1T (1,8)) (I.A)..... ((16))
NTT
ERNXKD.
We then further write the output of attention head & of first layer (11)
H (1,)) = 1 20. ... (L
E ERD
By the concatenation relationship, we have the row of ((1) to be
<(1> [b (12.0))......................1 ................................ ..1..))))) RRKD
(18)
And define each h (,,)))
Dr T ERD,
(1..0)) = Mau
(2.k1))
with each (1,..) R defined
((.,..)) = a Σ Piicas ( (WiLA)))))
Then the output of node j of class can be re-written as
jo Ento ( (Ki))W))) (2)
where w represents column e of W W(2). (2)
According to the definition of F definition 17, and ERC, we have
R(F))
E
1
sup
Σ
of(xx))
=
E
1
sup
Σ C
Σ p
(ch)
mia
M
fe
M
W
[wf SM2
M
N
jtt
w
M
|| |wsss/ SM²
sup
SM,
1=1
t=1
(2)
(1)
M
M
N
Σ
M
sup [|
2
SMi
t=1
The inequality comes from the Cauchy-Schward inequality. We further unfold the expectation, we have
M
E sup
((1)
(19)
K
M
N
N
= E
sup
(2)
Σ
((),)) (WLL)))
(
||
k=1
1=1
1=1
15

---

Under review as a conference paper at ICLR 2023
The equality is due to the following derivation:
Σ
22)
(1)
2
KD:
M
N
M
N
(2)
(1.K.t)
Σ
fj
jat
h (1.0)))
t=1
k=
1=1
K
D
M
N
N
(w (ware))))) (w)))))))))))
Σ
(2)
0
P(.,)
f=1
[=1
For fixed k-th attention head, we let the then, by positive homogeneity o, we have
w (a.e) w "..))..... w D:
be the the columns of W (1,)))
(1,b)
K
D
M
N
N
(M(LA))))) x
Σ
t. (())))
(
((2
km
1=1
2
N
w (1.
W
Σ Ej
P1
Σ
P(iin)
x;
The supremum of this quantity over ((1, wi wi w Dr
(1.k) under the constraint that (awlll & M² = EP w will 122 S M2 attained when (1,6)) = M1 for some r
and wh (1,8) = 0 for all other r' # r. In the end, only the r terms remain. For simplicity of notation, we use W(1,)) mean that r's column ((),
Therefore, we have
M
N
Σ E
ht
sup
(2)
((1)
SW
1=1
1=1
K
M
N
N
sup
Σ
1/20 0
Σ (2,A)
W(I.), X:
[[] MM1 k=1
j=1
1=1
(20)
(4)
K
M
N Σ P(),)) ((.,))x)))))
sup
E
((2
|[a] = M1
k=1
j=1
M
N
Σ
Σ Li
Eii (W(LL)))))) xi)
sup
fj
1(22
a
[|
M1
The inequality (a) is because sup(E, x.) & E, sup(xx).
16

---

Under review as a conference paper at ICLR 2023
For the inequality (b) above, we have
M
sup [|W(Lx)]||
C
Σ P(iia)
( W
((1,)) xx
=M
j=1
sup
Σ 9
((2) a
Σ
(1))))
Σ
pSj
Σ Eniiss
[|
(b)
M
N
IM
sup
Σ
(2)
0
Σ P(1,6)
(W.,,)),
/=1
1=1
M Σ
N
+ E
sup
Ej
Sit
Σ
Ci ((1,))
((L.A).2))
||W(L,))] Mi
1=1
1=1
N Σ
=2
sup
of P(I.)) W(LA))
[|
M1
t=1
N Σ P(i.)) W(LA);
E
sup
jit a
[|
M1
j=1
(0)
M
N
N
=2
sup
(2)
((1,)) W(L xi
[|
M
J=1
t=1
(21)
where the equality (a) above is due |x|| (x) + (x) and the inequality (b) is due to sup A+ I sup + sup n- and the equality (c) comes from the symmetry in the distribution of the e; random vari- ables. The equality (d) is due to sup, A, = (sup +) The equality (c) is because the supremum is non-
negative, as when W(Lk) = O, can get the ΣØ e Em 1/
(EmiP ( (Wo.k).x)) O.
We then rewrite
N
N Epais (MaAs))))))))) 1=1
N M
Σ> t=1==1
Σ tid
Eptiss (MLLA)
(22
0
1=1
By the same argument in sup(E, x;) S E, sup(z;), we have
M
N (MELA).x))
E
sup
{j
P
Σ
(())))
|
MM1 j=1
1=1
i=1
(22)
N
M
N
E
sup
Σ c
Σ
P(),)) (7..)))))))
1=1
|=
1=1
17

---

Under review as a conference paper at ICLR 2023
For any fixed t, we have
M
Σ Pil (wLL)))( (MCLA))):))
N
E
sup
Σ
M1
1=1
(a)
M
N ( (WALR))Z)))
2
max
P(2)
itt
EB
sup
Σ coo 1=1
Σ 1=1
P(2,))
(23)
(w
(b)
N Σ (iiiess j=1
M
2E IE
sup
Σ coo
||
The inequality (a) due to the contraction property of ERC. The inequality (b) due the definition of graph attention matrix P, i... the maximum value of entries each row is equal to Put (19), (20), (22), (23) together, we get
M
E
sup W W
E
(1)
(24)
Σ
Σ P(ii
(W(LM)) xi
sup |
EjO
/=1
Then use the fact that is Lo Lipschitz continuous and the contraction property of ERC. We further derive that
M Σ 3o
E
sup
Σ P(i,))
(W(LA)))))
1=1
P(i,,) Xx, w((LE))
<4La
E
sup
||
1/27
<4La
E
sup
Σ Cj
P ti
||<cLaoll2
||W
A= 1=1
(25)
1/2
K
N
M
N
S4L. M
E
(1,b))x
1=1
1/2
(9)
K
N
Mi
Σ
Σ
P(),))x X
1/2
[
-4,
XP XPL
Where the inequality (a) is by Cauchy-Schwartz, and the inequality (b) is by Jensen's inequality. And the equality (c) follows the i.i.d. condition of Rademacher sequences with zero-mean.
18

---

Under review as a conference paper at ICLR 2023
Next, continue to bound the rest,
1/2
K
N
M
K
4h M
X
1
S ALL.
(1xIl2 P(LA
k= im
k= 2m
[|lll2 P(1..0 1.)
S4L, M
AL.
(1x)
k= i=1
k i=1
1/2
( X;, w m)) ())
SAIGMMVM
sup
|Xw|22
S4I.M
sup [|
Σ
[|wll2=1
k=1
1/2
K
N
ΣΣ
Σ
X;
S BKAM
k=
where the first inequality is by ||Ax|, 2| S || 1xx122
Combined with the earlier result, get
R(F) S AL.
B POOF OF THEOREM 2
We now turn to prove the Theorem 2. Our proof strategy will be the following, We first provide classic theorem that used to bound the expected loss based on the empirical loss and the upper bound of ERC loss functions associated with GAT's for the multi-time-ster step situation F, then we derive this upper bound of ERC of loss functions of F by extending the upper bound of ERC of GATs with dieemmimnioonll output for the single-time prediction Fe, based on the existing theorem in literature.
Proof. From Theorem Mohri al. (2018), we have the following holds for all f
(2(2/))
E(f < B(f) + 2R(g)) + 3/
2M
where E(f), R(g=), and E(f) are defined in section 2.4.
In order to extend to multi-dimensionn vector-valued functions for MTSF, we will use the contraction inequality for the hypothesis class F of vector valued functions f E CRC.
Lemma 5 (Corollary 4 in Maurer (2016)). let F be class of vector-valued functions f (f1...., E R with each fc E F C Rx, and let {xI,...,XX,, XM.), KyI....yMM be data set with each xj E X and y; E E.. Let )b(--)) be frtiscchtz,functiin mapping V x y to R, and associated to F, where F C CVX. Then we have
M sup FEF j=1c=1
sup Σ ()((F()))))))))) FEF
S SVZE
Gefe(xx)
(26)
where tgj is the e, j-th entry of x M matrix of indeperulent Rademacher variables.
However, the RHS of equation 26 has supremum over all f F which is hard to compute and we can reduce it to scalar classes, and derive the following bound (Maurer, 2016):
M sup JEF
E JEF
(x))
<<
E
of(x)) j=1
(27)
c=l
Then we can derive the following upper bound for the loss function g(f(x) ((f(x).)) with f(x) being vector-valued functions based on equation and 27, where the RHS of equation is related to R(F)):
R(gr) S (2CR(FF)
(28)
n
19

---

Under review as a conference paper at ICLR 2023
C PROOF THEOREM 3 AND THEOREM 4
Proof. For = L, by the definition of network output and the Rademacher complexity, we have
M Σ
R(F))
E
sup M JEF ==1
{
M
sup M
Ej
P(L)
f(--1) EFL
j=1
| SNV
Mr.
M N
sup
Σ j=1
jj
(L))
2 (--1)
M
[W SMz f(z 21-
t=1
so we get
M
M
N
M₂
R(F) SE
|| 1. | SM
sup
Ej
(1.
(1-1)
j=1
Jic 2) 2
We denote the RHS as R(L). We further unfold the expectation, we have
N
E
sup
Σ
2
L-
(L- 1,63 -M
[=1
110-2))FL--
K
M
N
Σ 6j0 j=1
Σ
Ppu P(
(W(L
sup || -
k=
1=1
Ju- 2) EF
This follows the same reason with equation 24. Now for any / [T. - 1). have
20

---

Under review as a conference paper at ICLR 2023
M
E
sup
Σ cjo
Σ
((.b)
t.d
((LL))) ((LLA))-i-1))
Iwo,wlll EA--1
M
N
<11 E
sup
(1,k)
2 1
|w( |= 11-1)
==1
1=1
N
<lg E
sup
(1,b)
1-1
|
[[ | 1
j=1
i=1
Lo. M1
E
sup I Loll -
Σ
E
2
i=1
FL-2
Then we get the induction equation, which says
M
E
sup
Σ
((11))
(00
W S.:
1=1
F
2
K
N
M
<4L, M
ΣΣ
E
sup
Σ
C
R
[ SMc fa 2) Fi=
1=1
i=1
R(1 + 1) S 4L, Mi
R())
By induction, we get
L-1
R(++1) (AL,KN) 4-1
(4LKK)(ALKKN)"
II
MIR(1
1/2
T- II 1=1
M
N
$ KNL
Mi
Σ
(1,
x,
L-1
< (AL,
II
Mi
B(N
1=1
Combining with the previous result, we get
R(F9) S (4T.
II Mi
BNL-1/2M-11? 1/2
21

---

Under review as a conference paper at ICLR 2023
D EXPERIMENT AND DATA
D.1 EXPERIMENT SETUP
The model is trained by the Adam optimizer (Kingma & Ba, 2014). The learning rate is 1e-4. The number of training epochs is 30. The batch size set to We split the dataset into three parts for training, validation and testing with a ratio of 0.6 : 0.2 0.2. All the deep learning models, are implemented in Python with Pytorch and executed on server with 8 NVIDIA GeForce GTX 2080Ti GPUs. The Nvidía river version is 470. 770.141.0. 1.003 and the CUDA version is 11.4.
Table I; Experiment environment. The list only includes major packages. All the packages are installed using Anaconda and Pip.
Package
Version
python 3.9.13
matplotlib
3.5.2
numpy
1.23.1
pandas
1.4.4
pytorch
1.12.1
torch-geometric
2.1.0.postl
torch-scatter
2.0.9
torch-sparse
0.6.15
D.2 NEURAL NETWORK ARCHITECTURE
We implement our neural network as a three-layer Graph Attention Neural network. This includes the input layer, one hidden layer, and the output layer. Each layer is GATConv layer from the Pytorch-Geometre package We use ELU activation (Clevert et al., 2015) and Dropout (Srivastava et al., 2014) after both the input layer and the hidden layer.
For the number of heads variable, we change the number of attention heads of each layer and all layers the same number of attention heads. For the number of neighbors variable, we adjust the dropout rate inside each layer's s attention mechanism (different from the dropout layer) so that only a pereentage of the nodes are considered when using the attention to aggregate information from a node's neighbors. For the weight norm variable, we adjust the bound of the Frobenius norm of the weight matrix inside each layer by using weight clipping. Each element of the weight matrix is clipped to the threshold make sure the Frobenius norm of the matrix is less than equal to the bound. For the number of layers variable, we adjust the number of hidden layers ranging from For the input norm variable, we make sure each node's feature vector's L1 norm less than or equal to bound ranging from to 28. For the number of labeled nodes variable, we use a ratio to adjust the size of the training dataset.
D.3 MODEL HYPERPARAMETERS
Table 2: Default hyperparameters. When we study the impact of different values of a variable such as the number of heads, we keep all other variables fixed to the set of same values.
Hyperparameter
Value
Comment
num-hid-layers
Number of hidden GATConv layers
num-heads
Number of attention heads; Same for all layers
num-neighbors
0.1
Neighbors to obtain attentions; Percentage all nodes
num-labeled-notde
None
Ratio of training set if not None
train-ratio
0.6
Ratio of training dataset
inputs-norm
1.0
Bound of the norm of the inputs
weights-bound
None
Bound of the norm of the model weights if None
hidden-size
32
Out-channels of the input layer and hidden layer Learning rate
le-4
dropout
0.1
Dropout rate after input layer and hidden layer
hhttps://pytorrchhgeoeerrr
ess html
22

---

Under review as a conference paper at ICLR 2023
D.4 DATA
We use the US daily stock market prices dataset from Kaggle 4
D.5
SOURCE CODE
The source code is shared via Dropbox 5. Please refer to the included README file for detailed exccution guide.
E SUPPLEMENTAL EXPERIMENTS
y- O(2 1)
20-
Y-
0
L-2
30
Genernization
Generalzation
15-
20
10-
10
30
0
0-
14
30
12
Number of sitication hezals
Number neighhoes
Upper bound of weights norm
(a)
(b)
(c)
Figure 3: Additional experiment results using a two-layer GAT on three variables in the ERC whose generalization error is related to the number of layers. We run the experiment 20 times and obtain standard deviation of the generalization error. (a) relationship between test loss and the number of attention heads. (b) relationship between test loss and the number of neighbors. (c) relationship between test loss and the upper bound of weight norm. The red line is possible theoretical upper bound. The plots show that when L equals to 2, all test losses still generally conform to the big O of the theoretical upper bound.
In the experiment section, for all experiments, where the number of layers, I., needs to be fixed for studying the relationship of the generalization error with different GAT components that impact the ERC, including the number of attention heads, the number of neighbors, the upper bound of weights norm, we use a three-layer GAT to demonstrate Theorem However, the upper bound input norm and the number of labeled nodes affecting the ERC do not depend on the number of layers, thus, in our supplemental experiment for two-layer GATs, we only consider the three variables (the number of attention heads, the number of neighbors, and the upper bound of weights norm) that impact ERC and depend on the number of layers. Notably, Theorem for generalization error bound of two-layer GATs is just special case Theorem for deep GATs: when we let L equal in Theorem the generalization error bound is identical to the bound in Theorem multiplied with some constants. We now give empirical results on two-layer GAT's to see if it is consistent with Theorem and Theorem 3,
In this appendix section, we include more experiment results from a two-layer GAT on three variables in the ERC. As Figure 3 shows, when the number of attention heads increases, the generalization error also increases at a linear rate after certain values. When the number of neighbors increases. generalization error initially decreases when the number of neighbors is small, then starts increasing following the trend of a polynomial function. As for the upper bound of weight norm, the generalization error increases quadratically with the increment of the norm. The empirical results well
for all three variables generally conforms to the theoretical bound suggests by Theorem as Theorem 3. For some inconsistency between the results and the reference red line theoretical results at the the beginning, the reason, as we have discussed, can be due to the trade-off between approximation error and estimation error, since when the complexity of hypothesis class increases, the former decreases and the latter increases. In the long run, the estimation error or the ERC dominate the bound.
Thus, the results for L 2 along with the three-layer experiments provide evidence for our theoretical findings (Theorem 1 and Theorem 3).
ptttps://ww.keee
com htt.://ww.....aaaaaa.aa...eeae/a
hhttps:/wwwe http://wwww.owboox.o/oo dropbox. com/ http:://wo...aaa.o.oooooooaaaaaa d1=0
23

---

which allows every node to attend on every Under review as a conference paper at ICLR 2023
F SUPPLEMENT RESULTS
F.1 MTSF UNDER
SETTING INSTEAD OF SEMI- SEMI-SUPERVISED SETTING
We consider an undirected graph G = EW, N -M1...... nN), IV = -N, is a set of node labels representing the sources of N time series. & C.C X the set of edges representing the connection between series. We let x; E X, i [N] be random variable representing the input feature vector of node n, for time series i. For node i, its random input feature x; E X C RR is a multi-dimensional vector, which contains all the historical values from T time steps, in other words, we let x; = (Xi,t>...., Xi,+-++1 be the concatenation of T time steps; its true label y; E E C RC is the vector for the --step-away values. We sample n training data over G. where n = N x V for some V N+. In other words, we have V batches of samples over graph G. For any risk function g defined over F, given the training set S = {(x). V1 Vi...... (x,. which includes n samples from X' x y according distribution Q, the expelted/popplaaiion risk E(f) and the empirical risk function E(f are defined as:
V Ñ ΣΣ ,(( V N
B(f)= E vl. (29) (x.Y)
E(O)
1
(30)
We introduce 1 S Ñ S N the effective size of data because the data among nodes corresponding to different time series are not independent. If Ñ 1, all of the time series are fully dependent. If Ñ N, they are mutually independent. So the N characterizes the strength of the independence among different time series. Then we use ñ as the effective sample size of data which are i.i.d, where V S ń < NV = n. So the training set will contain ñ data.
Given the inputs X= = -X;,..., .......,x)))))) as multiple time series with each x, as input feature for node ny the class of 2-layer GATs for MTSF f maps x to the output f(x) that represents C-step-away prediction expressed in equation 2. We consider subset of such class requiring each f with bounded weights norm, expressed as
x= f f(x) W(Lmll S M1, w S M2).
F
(31)
Furthermore, we also provide model space F c R with single dimensional output that corresponds to the c-th component of model output from f(x) for the e-th time step, expressed
F
f
f(x) W s M1,
M2, [
(32)
Here we first provide an upper bound of ERC of GAT class Fe for single dimensional output of MTSF.
Theorem 6 (Upper Bound of ERC of GAT class F for MTSF). Let the activation funcctioon,uuccionn o(:) be Lo Lipschiiiz continuous, and also satisfy (0) = and o(az) (va (z) for all a 2 Assume that the To-norm of the feature vector x comes from bounded domain X === {x ||x|| < B). Assume that the Frobenius norm of every weights matrix in the first layer of the GAT class is bounded, namely, [ S M1 with some constant M1 > 0frrr every k. Also, the norm of the weights vector of the second layer of the GAT's is bounded, ((()) I M2, where E [C], with some constant M2 0. Let N₂ denote the neighborhood of node i (including i), let the number of neighbors of each node be identical, namely, for some common constant N. E N++ assume Ne := |Wi for all node E N, furthermore, we consider the most general formulation, g other node, i.e., No = N.
Then let R(F)) be the ERC defined in the definition 7 for GAT class F in the definition 32, given the ñ sized input set {x1,..., Xx ). then we have
R(F)) BLL.
Similar proof details can be found in SA.
Theorem 7. Define the hypothesis class F as the definition 15. We suppose g is Lipschitz with constant Tag. Then for any 5 E (0, 1), with probability at least 5, for all f E F, we have
24

---

Under review as a conference paper at ICLR 2023
In(2/6)
E(J) E()) + +222CL,((FF + 31
2n.
where we have R(FF) OLL, from Theorem 6.
F.2 RESULTS UNDER SUPERVISED SETTING
In this section, we provide the results of experiments under the fully-supervised setting. The multivariate time series have about 1500 stocks, and these stocks are used for training and testing.
We ensure that the training and testing data do not have any overlap. The results for the relationship between the upper bound of the generalization error of the model and variables in the ERC are shown in the Figure 4.
3
0(25)
- Ole
Gensrlizztion
1
0.0
0.5
0.2
10
30
15
20
25
30
attenii lazal
Number neighhoes
Upper bound weights
(a)
(b)
(c)
10-
V. O(x)
O(am213)
0.6
1.5
0.0
Generalication
Gesealiiaaiin
0.4
0.6
0
3.5
11.
0.7
Number of brdden layers
Upper bound of ingurs norm
Liffective sample size
(c)
(f)
Figure 4: Experiment results on six variables in the ERC. We run the experiment 20 times and obtain a standard deviation of the generalization error. (a) relationship between test loss and the number of attention heads. (b) relationship between test loss and the number of neighbors. (c) relationship
between test loss and the upper bound of weight norm. (d) relationship between test loss and the
number of (hidden) layers. (e) relationship between test loss and the upper bound of input norm. (f) relationship between test loss and the training data set size. The red line a possible theoretical upper bound. The plots show that all test losses generally conform to the big O of the theoretical upper bound.
From Figure 4 in Figure 1. For the last variable, we use the size the training data set instead of the number the labeled nodes. Our Theorem 6 reports that the ERC has polynomial O 1/2)'s dependence on Oññ-1/2)3s the effective sample size. we can see from Figure 4f, the generalization loss decreases when the training data set size increases. The red curve based on the theoretical value matches the pattern of the yellow curve based on our experiments, though slightly lower than the yellow curve after certain values of training data set size. This is because we need more samples in the experiment to satisfy the effective samples in terms of the generalization enror.
that the overall pattern for different variables still consistent with those
25

---

Under review as a conference paper at ICLR 2023
Table 3: Comparison of Weight-bounded GAT with Baselines ASTGCN, GDN
Metrics (10 3)
MSE
MAE
STD(MSE)
STD(MAE)
Weight-bounded GAT ASTGCN
2.04
30.61
0.9
10.55
7.14
36.77
6,61
17.41
Guo al. (2019)
GDN
8.11
46.31
3.62
24.21
Deng & Hooi (2021)
F.3 COMPARISON WITH OTHER BASELINES
So far, two current works (Guo et al., 2019; Deng & Hooi, 2021) use GAT-based models to model multiple time series data, showing better performance in accuracy over other traditional linear methods (e.g., VAR), neural-network based methods (e.g., L.STM), and graph-networ GNNs and GCNs). Both works differ from ours as they do not consider any control model variables (e.g., the weight matrix norm) and they lack theoretical guarantees in terms of the generalization error. GDN is proposed by Deng & Hooi (2021) and is used for anomaly detection in multivariate time series. ASTGCN is developed by Guo et al. (2019) for multiple traffic flow forecasting. We use GDN and ASTGCN baselines compare with Weight-bounded GAT. To adapt them into our settings, we modify the output layer of We also keep other test error and standard deviation from 20 runs. We use two evaluation metrics, the MSE and MAE. Additionally, also use figure 5 show their generalization loss difference.
based methods (e.g..
to perform the regression instead of classification task. the same across three methods. Table 3 reports their average
As Table and Figure 5 show. the Weight-bounded GAT performs better than the GDN and ASTGCN. Apart from using graph attention mechanism, GDN also learns a di- rected graph to model the causal-effect relationship be- tween different nodes, which can capture the asymmetric dependency patterns. Learning graph structure bet- ter dynamically capture the relationship between nodes, but also increase the learning time and model complexity. In the meantime, while using attention between nodes, ASTGCN also considers the attention along the time axis.
.007
ISSE
Geseralitation loss (MSE, MAE)
IMME
Our method does consider attention along the time the features every time step has already embedded the historical information. Compared the weight-bounded control in our method plays an impor- tant role in controlling the generalization eтror, which is also verified in our theoretical analysis. This result further corroborated the outperformance of our method the GAT- based SOTA methods for MTSF.
GDN and ASTGCN,
Weight-bounded GAT
Figure 5: Test loss of three methods. The train-test pipeline runs 20 times over 20 random seeds. The Weight-bounde GAT has a better test loss than the GDN and ASTGCN regarding first quan- tile, third quantile and the mean of the test loss.
F.4 MODEL ARCHITECTURE
26

---

Under review as a conference paper at ICLR 2023
Dropout
Dropout
GATConv
GATConv
GATConv
Input
Weights bounded)
(Weights bounded)
(Wiigtt bounded)
Output
Input Layer
Hidden Layer
Output Layer
Three-layer weights- bouuned GAT
Figure 6: The demonstration of the lhyee-layer Weight-bounded GAT model we The input layer and the hidden layer both followed by an ELU activation and dropout. Each GAT layer is implemented using Pytorch-Geometri Geometric GATCony layer.
27


Reviews:
[{"review_id": "pECDRv1m0C", "reviewer": "Reviewer_Hkz8", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper presents a multivariate time-series forecasting framework that combines GAT with a forecasting framework. The paper provides detail about the GAT framework. The way they integrate it seems to have been inspired by Wu et al. IJCAI 19 but differs in the choice of the specific GAT parameterization. The second half is about their theoretical analysis based on their empirical risk minimization framework.", "summary_of_the_review": "This might be a potentially solid work from a theoretical perspective, but the overall impression is that it was submitted prematurely before careful proof reading.", "strength_and_weaknesses": "Strength\n\n- Novel incorporation of GAT into a multi-variate time-series forecasting framework.\n\n- Conducted a theoretical analysis of the GAT parameter under the Frobenius-norm-based loss.\n \n\nWeakness\n \n- Despite that the authors claim that incorporation of GNN/GCN will improve the prediction performance, the authors do not provide a clear-cut description of the forecasting model itself. \n\n- Similarly, it seems the authors did not evaluate the forecasting performance if I understand correctly. This gives the impression that the first half and the second half are disconnected and do not deliver a coherent message. \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "iMcn6xbEqd", "reviewer": "Reviewer_yXLj", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work proves generalization error bounds of multivariate time series forecasting by graph attention network, under the assumption that every node in the graph has the same degree. The theoretical analyses are based on upper bounding empirical Rademacher complexity of the class of functions represented by the graph attention network. The derived generalization bounds depend on the norm of weight matrices, the number of neighbors, the number of attention heads, and the number of layers. The theoretical claims are further validated by empirical results.", "summary_of_the_review": "The paper provides a solid theoretical analysis on the generalization error of graph attention network for multivariate time series forecasting. However, I have some concerns about the relevance of the problem setting in this paper to multivariate time series forecasting.", "strength_and_weaknesses": "The paper attempts to provide a theoretical foundation to an important problem: the use of graph attention networks for multivariate time series forecasting. Using graphical information to capture correlations among variables in multivariate time series forecasting has gained a lot of interests recently. Although various GNN-based methods have been proposed and are shown to deliver state-of-the-art empirical performance, there is few rigorous study on the generalization error of these methods. Therefore the subject studied in this paper is very interesting. In addition, the paper is nicely written. The overall presentation is clear and easy to follow. The authors also carry out empirical experiments to validate all theoretical claims.\n\nHowever, on the other side, I have a few concerns/questions regarding the practical relevance of the theoretical setting in this work to multivariate time series forecasting.\n\n- Typically in multivariate time series forecasting, we do not have access to future C-step-away values of any series. This comes from the fact that in forecasting we never know what is going to happen in the future. However, in this paper, the authors assume that we are given the true future C-step-away values for a subset of time series. This assumption seems to be counter-intuitive and not very realistic. Can the authors comment on the assumption?\n\n- The authors assume that each node in the graph has the same degree. Moreover, in Theorem 1 the authors claim that \"we consider the most general formulation, which allows every node to attend on every other node\". I think that requiring each node to have the same degree, e.g., requiring that every node to attend to every other node, is in fact a limitation rather than being general. The general setting should be without assuming anything about the structure of the graph, or at least without assuming that the graph is degree-regular or complete. I think the authors should make it clear in the text about the limitations imposed by the assumptions.\n\n- In general, I feel like the setting in this paper, i.e, problem formulation in section 2.1 and the graph structure in section 2.2, is not really the typical setting for time series forecasting. It feels more like graph-based semi-supervised regression. For example, I couldn't find any characteristics in the problem setting that are special to time series forecasting. Moreover, I think that, in general, semi-supervised setting in more typical for classification rater than forecasting. Please correct me if I am wrong.\n\n- Because of the above points, I think that there is a gap between what the paper claims to solve and what the paper actually solves. It might be more appropriate if the paper has been framed as providing generalization bound for graph attention network on semi-supervised regression tasks.\n\nFinally, a minor question about the experiments: How did you construct the graph for the stock pricing dataset when you vary the node degrees? Is it kNN graph?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "OtMipa0JkCt", "reviewer": "Reviewer_7dJx", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a norm-bounded graph attention network (GAT) for multivariate time series forecasting. The norm of the weight matrix in the proposed model is bounded to ensure the generalization error bound, the paper proves this theoretically. The experimental section in the paper shows that the generalization performance depends on the number of attention heads, the number of neighbors at each given node, the upper bound of weights norm, the number of hidden layers, the upper bound of inputs norm, and the number of labeled nodes. Their empirical results match the theoretical expectations (this is shown in figure 1).\n", "summary_of_the_review": "The main weakness of the paper is that it has no empirical experiments comparing the performance of GAT to other networks. While I appreciate the theoretical guarantees multivariate time series forecasting is a very practical topic and convincing the AI community to use a method must come with some strong empirical results. Proving error bounds is great but it is not enough, unfortunately. If the authors would like to provide this paper as a purely theoretical paper the title and area should have been different so more theoretical reviewers could have been assigned.\nIf the paper had strong empirical results I would have happily accepted the paper.", "strength_and_weaknesses": "Strength:\nThe paper provides theoretical guarantees on graph attention by bounding weight matrix for multivariate time series forecasting.\nThe paper is clearly written and easy to follow.\nThe paper shows empirically that test losses conform to the big O of the theoretical upper bound.\n\nWeakness:\n\nThe title of the paper is \"MULTIVARIATE TIME SERIES FORECASTING BY GRAPH ATTENTION NETWORKS WITH THEORETICAL GUARANTEES\" and the area chosen by the authors where the paper falls is application. So one would expect to see the performance of the proposed method on multivariate time series and compare the performance to other methods. Yet the paper has no empirical experiments showing the performance of forecasting tasks. This makes me question the capabilities of the proposed GAT when compared to other neural methods for practical forecasting applications.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject