Node Feature Forecasting in Temporal Graphs: an Interpretable Online Algorithm
Authors: Aniq Ur Rahman
Justin Coon
Venue: Accepted by TMLR ()

Abstract: In this paper, we propose an online algorithm mspace for forecasting node features in temporal graphs, which captures spatial cross-correlation among different nodes as well as the temporal auto-correlation within a node. The algorithm can be used for both probabilistic and deterministic multi-step forecasting, making it applicable for estimation and generation tasks. Evaluations against various baselines, including temporal graph neural network (TGNN) models and classical Kalman filters, demonstrate that mspace performs comparably to the state-of-the-art and even surpasses them on some datasets. Importantly, mspace demonstrates consistent performance across datasets with varying training sizes, a notable advantage over TGNN models that require abundant training samples to effectively learn the spatiotemporal trends in the data. Therefore, employing mspace is advantageous in scenarios where the training sample availability is limited. Additionally, we establish theoretical bounds on multi-step forecasting error of mspace and show that it scales linearly with the number of forecast steps $q$ as $\mathcal{O}(q)$. For an asymptotically large number of nodes $n$, and timesteps $T$, the computational complexity of mspace grows linearly with both \$n\$ and \$T\$, i.e., $\mathcal{O}(nT)$, while its space complexity remains constant $\mathcal{O}(1)$. We compare the performance of various mspace variants against ten recent TGNN baselines and two classical baselines, ARIMA and the Kalman filter, across ten real-world datasets. Lastly, we have investigated the interpretability of different mspace variants by analyzing model parameters alongside dataset characteristics to jointly derive model-centric and data-centric insights.

Published in Transactions on Machine Learning Research (05/2025)
Node Feature Forecasting in Temporal Graphs: an Interpretable Online Algorithm
Aniq Ur Rahman
anig. rediggrammaneeee Beng.onneennnrre ox.ac. uk justin. mustin.coon coon Meng.oangaa... or. ac.
Justin P. Coon
Deportment eepertment of Engineering Science, University of Ouford, U.K.
Reviewed on OpenReview: https: // openreview. net/ forun? id= TewIBlr2YJ
Abstract
In this paper, propose online algorithm mspace for forecasting node features in temporal graphs, which captures spatial cross-correlation among different nodes as well as the temporal auto-correlation within node. The algorithm can be used for both probabilistic and deterministic multi-step forecasting, making it applicable for estimation and generation tasks. Evaluations against various baselines, including temporal graph neural network (TGNN) models and classical Kalman filters, demonstrate that mapace performs comparably to the seate-of-theatt and even surpasses them on some datasets. Importantly, mspace demonstrates consistent performance across datasets with varying training sizes, notable advantage over TGNN models that require abundant training samples to effectively learn the spatiotemporal trends in the data. Therefore, employing mspace is advantageous in scenarios where the training sample availability is limited. Additionally, we establish theoretical bounds on multi-step forecasting error of mspace and show that scales lincarly with the number of forecast steps as Og)). For an asymptotically large number of nodes n, and timesteps T, the computational complexity of mspace grows linearly with both n, and T, i.e. OnTT), while its space complexity remains constant O(1). We compare the performance of various mspace variants against ten recent TGNN baselines and two classical baselines, ARIMA and the Kalman filter across ten real-world datasets. Lastly, we have investigated the interpretability of different mspace variants by analyzing model parameters alongside dataset characteristics to jointly derive model-centric and data-centric insights. Link to Code
1 Introduction
Temporal graphs are powerful tool for modelling real-world data that evolves over time. They are increasingly being used in diverse fields, such recommendation systems (Gao et al. 2022), social networks (Deng et al., 2019), and transportation systems (Yu et al., 2018). to name few. Temporal graph learning (TGL) can be viewed as the task of learning a sequence of graphs that form a time series. The changes in the graph can be of several types: changes to the number of nodes, the features of existing nodes, the configuration of edges, or the features of existing edges. Moreover, temporal graph can result from a single or a combination of these changes. The TGL methods can be applied to various tasks, such as regression, classification, and clustering, at three levels: node, edge, and graph (Longa et al. 2023).
In this work, we focus on node feature forecasting, also known as node regression, where the previous temporal states of a graph are used to predict its future node features. Forecasting is fundamental problem in various domains, such as weather, finance, and traffic, enabling informed decision-making (Petropoulos et al. 2022), and the problem still remains relevant today in light of the advances in machine learning. In the context of temporal graphs, node feature forecasting exploits the structure of the evolving network assuming that the future value of a node is influenced by its neighbours (Huang et al. 2023
In most temporal graph neural network (TGNN) models, the previous states are encoded into super-state dynamic graph embedding (Barros al. 2021 guided by the graph structure. This dynamic embedding

---

Published in Transactions on Machine Learning Research (05/2025)
is then used to forecast the future node features. Although TGNN models perform well, their interpretability is often overlooked, and their performance is not explained through the data. Furthermore, the relationship between the node features and the node or graph embeddings is not human-unddrssanddabll most embedding aggregation mechanisms impose a strong assumption that the neighbours influence a node
Furthermore,
in proportion to their edge weight (Wang el al. 2021.
TGNN methods (Li al. 2018 Micheli & Tortorella 2022 Wu al, 2019 Fang al, 2021 Liu al,,
2023 typically involve training phase where the model learns from training data and is then deployed test data without further training due to computational costs. If the test data distribution differs from the training data, an offline model cannot adapt (Wang et al. 2024). Therefore, when dealing with time-scries data, it is crucial to use a lightweight online algorithm that can adapt to changes in data distribution while also performing forecasts. Moreover, TGNN models are typically trained to forecast a predetermined number of future steps. we want to increase the number of forecast. steps, even by one, the model neods to be reinitialized and retrained. Alternativcly, the output can be fed back as input to the TGNN, extending the forecasting scale of the same model without additional training.
Inspired by the simplicity of Markov models, we define the state of a graph at given time in an interpretable manner and propose a lightweight model that can be deployed without any training. The algorithm is designed with a mechanism to prioritize recent. trends in the data over historical ones, allowing it to adapt to changes in data distribution.
Contributions
The contributions of our work are summarized as follows:
We have proposed online learning algorithm mspace for node feature forecasting in temporal graphs, which can sequentially predict the node features for q E N future timesteps after observing only two past node features.
The algorithum mspace can produce both probabilistic and deterministic forecasts, making it suitable for generative and predictive tasks.
The root mean square error (RMSE) of q-step iterative forecast scales linearly in the number of steps q, ie. RMSE(g) = Olg).
For asymptotically large number of nodes n, and timesteps T, the computational complexity of msapce grows linearly with both n, and T, ie.. O(TT), while the space complexity is constant O(1).
We have compared the performance of different variants of mspace against len recent TGNN baselines, and two classical baselines ARIMA, and Kalman filter.
We have evaluated mspace on four datasets for single-step forecasting and six datasets for multi-step forecasting.
In addition to the evaluation on ten rcal-world datascts, we have proposed a technique to generate synthetic datasets that can aid in a more thorough evaluation of node feature forecasting methods. The synthetic datasets have the potential to serve as benchmark for future research.
We have investigated the interpretability of different mspace variants by analyzing the model parameters along with the dataset characteristics to jointly derive model-centric and data-centric insights.
To facilitate the reproducibility of results, the code made available here
Notation We denote vectors with lowercase boldface æ, and matrices and lensors with uppercase boldface
X. Sets are written in calligraphic font such as V,U,S, C, with the exception of graphs G, and queues Q. The operator > used in two contexts: x > 0 is an element wise positivity check on the voctor æ, and A > 0 indicates that the matrix A is positive definite. I(-) is the indicator function, and [m] & (1.2...., .m for any N. We denote the distributions of continuous variables by p(-), and of discrete variables by P(.). The
2

---

Published in Transactions on Machine Learning Research (05/2025)
statement 2 p means that æ is sampled from p. The Hadamard product operator is denoted by C while the Kronecker product operator is denoted by 60. The trace of matrix A is written as tr(A).
We denote the neighbours of a node for an arbitrary number of hops as Up The neighbours of node up to K number of hops is defined as follows. Let N = =kEjK] A then U2 = {u No,a > 0, E V}. Since Au, 1, E Ug. We introduce the operator (-) to arrange the nodes in a set U in ascending numerical order of the node IDs. When another set or vector is super-scripted with (l)), the elements within that set or vector are filtered and arranged as per (24).
A Markov chain is represented using 3 with different subscripts for identification. The transition kernel of a Markov chain is denoled as P with Pa, representing the probability of transitioning from state a to b.
Organization In Scc. 2 we formulate the problem of node feature forccasting and also propose model to solve it. In Sec. 3 we expand upon the solution and present it as algorithm. We discuss the related works in Sec. | and present the results on single-step and multi-step node feature forecasting in Sec. 5 In Sec. G we discuss the interpretability of the proposed algorithm and then discuss the limitations in Sec. Finally, we conclude in Sec.
2 Methodology
Problem Formulation A discrete-time temporal graph is defined as (c. = (V) E [T]), where V= = in] is the set of nodes, 8 g x V is the set of edges, and X, E I@a the node feature matrix at time The set of odges & can alternatively be represented by the adjacency matrix denoted as A {0, 1)"xn. The node feature vector is denoted by (v( E Id such that X, [z) and refer to the first-order differencing (Shumway & Stoffer 2017 of a node feature vector as shock. For node E V we define the shock at time (v) = =z(1)) (v).
V
(v). The shock of the nodes in ordered set U at time t is denoted by E, E "R The shock at time t for an arbitrary set of nodes is Et. (4)
To address the problem, we make certain assumptions. The first a Markov assumption, stated as follows: Assumption 2.1. The shocks {E,, Eg, E3 E. is assumed to be sampled from a contimuous-state Markov chain defined on mnd for some m E [n], such that p (EE411 E,, E,, p st).
Although the Markov assumption can be extended to higher orders, this work, we consider only a first-order Markov chain, which limits the model's ability to capture long-range dependencies in the data. In theory, a continuous-state Markov chain has infinite nunber of states which makes it impossible to learn the transition kernel from limited samples without additional assumptions. To circumvent this, lineor dynamical systems and autoregressive models are used in the literature (Barber 2012 where the next state is determined through a function of the current state.
Let p(E' EE) denote the transition probability E - e' in a continuous-state Markov chain 30 defined over a set C. A discrete-state Markov chain 31 defined over finite set S with transition probability Ps,.' can be constructed from p(e' |e) through a mapping wr S as
[ [e)p(e) ()((((E))) 8') de de'
P Pe.s c
(1)
plE E))(E) (() s) de de! ce
For a contimuous-state Markov chain sample (2,, ET) we can estimate P directly from (M1()) (E2).. (Err) without the need of p(E' e). Now, consider a random function Ω S C, such that: (a) V(E)= 8, (b) V(e')= s', (c) e' = R(s), from which follows p(f(s)) p(E' s).
The approximate transition kernel P due to (V) can be written as:
T I p(E'l dE' = / (W())) = =8) d'dde'.
Pa.a' =
(2)
3

---

Published in Transactions on Machine Learning Research (05/2025)
$t-
SL
5t+1
(2(s)
V
V
Ω
V
Ω
V
Ω
S
6t-1
Et
EL+1
E1+2
C
C
Figure 1: (left) state and sampling functions visualized, (right) Markov approximation.
In Fig. 1 (left) we depict the functions mapping from continuous space in C a discrete space S. We also depict 92 mapping from S to C. In red patch we show the range of [(s), and in the green patch we show the domain of (s). In Fig. [ (right), visualize Assumption 2.1 wherein the shocks evolve as Markov chain through the functions V2
We refer to V as the state function, and Ω as the sampling function. The approximated Markov chain defined over S resulting from (V, is denoted as (( 22), with p(ě' E) = p(2 (e)). Ideally, the goal is to find the pair of functions (V, such that: (a) Pa.a' = =P.. V8, s' E (b) p(e'le) p(2 (e)) Ve e C. However, in practice this is quite ambitious as the state and sampling functions will induce some error in the encoding and decoding process. Therefore, we frame the problem follows.
The sequence of shocks drawn from the original Markov chain 30 is represented as {Er : E [T]} 30- Then, for each e, we generate sequence of q future shocks using the Markov chain ( 52) as
Êets = (1 (Ex), At [T - 11, E [g].
The problem is to design V such that [EEE Elts - 2 is minimized Ak E [g]. t E [T - 9], which can written alternatively as:
Problem 2.1 (g-step node feature forecasting). Design the state and sampling functions v such that
min EE(T -0 k<(al
Eæt - (1 o v
JE(M]
In a deep learning context, both V and Ω would typically be neural networks trained directly using the objective in Problem 2.1 In this work, however, we explicitly define W and Ω and learn their parameters through the same objective.
Proposed Model Instead of creating single model to approximate p (c e!""). we create model for each node E V to approximate p ( number of hops. We present this in the following assumption.
(Ut)) | E ((u.)) where U, denotes the neighbours of node within certain (Et+1
Assumption 2.2. The shock of node at time t + 1 can be estimated from the shock of its neighbouring nodes in Mp at time t.
While (w') for any node n' $ Uh may help in estimating (v)) we assume that enough information is already conveyed by the nodes in U, that the impact of considering node u' would be minimal. It must be noted that U, denotes the neighbours of node e up to an arbitrary number of hops, therefore if we consider U, to mean hops, then all the nodes that neighbours e with 1, 1,2, kk hops are all in U, and their impact
For example, C the Rm for some integer m, and S the set f1,-13m simply (1,2, , I.}. for some integer T..
4

---

Published in Transactions on Machine Learning Research (05/2025)
is considered. Assumption 2.2 is important to create scalable model, because in connected graph every node will be correlated with every other node which will make the state space prohibitively large.
We propose two variants of the state function, one which captures the characteristics of the shock Vs, and the other which is concerned with the timestamps vr and captures seasonality.
Vs Rlu (-1,1] Vs(e sign(e()))
Vr N - 10,1, 10,1, 1T, (r(() t mod To, where E N is the time period.
We also define two variants of the sampling function:
deterministic (2)(s) - u(s), Vs E.
probabilistic Qs((s) ~ NN(': E(s)), S.
In Vs, we binarize the shock values of a node and its neighbors, creating a vector that indicates whether each value has increased or decreased. This vector serves as the state on which the next shock value is conditioned. Similarly, in VT, we transform the timestamp into an integer based on predefined time period, then use this integer to condition the next shock value. A comprehensive explanation of the state functions provided The proposed model is presenled as online algorithm and discussed in detail in the following
in Sec. 6 section.
3 Algorithm
We name our algorithm mapace with suffix specifying the state and sampling functions. For example, mspace-SN represents the algorithm with state function Vs, and sampling function fly. For each node V, we approximate p(E (2.)) Va(e)(uu) ((a)) 8) as Gaussian distribution with mean vector (.(() E Rluldd and covariance matrix (s) gl4,jaxid,,dd indexed by the state 1j1, The parameters (e (s) are learnt through maximum likelihood estimation (MLE). For each node V, and state s we maintain a queue (s) of maximum size M in which the shocks succeeding a given state are collected. The MLE solution is calculated as (8) +- mean (Q.())) and Es(s) <- covariance( (x)).
state
(s)s)
MLE
(s))
shock
(s)
Normal sampling
S
S
S
past
future
Figure 2: Operation of a queue.
The use of a fixed-size queue (see Fig. 2 ensures that the model prioritises recent data over historical data, thereby allowing the system to adapt to prevailing trends.
As mapace is an online algorithm, we might encounter unobserved states for which the queue is empty, and therefore cannot employ MLE. To facilitate inductive inference, as state 8, is encountered, find the state s* E S, which is the closest to 8t, i.e., s* f- arg min.es. ||s sell, where S, is the set of states observed before time t.

---

Published in Transactions on Machine Learning Research (05/2025)
Algorithm 1 mspace-SN
Input - X), r E [0, 1), q, M Output éx(v), Vu V. 1 |r TJ.7]
Online learning (B)
13: for i ||r Tj: T
q] do
Et 2 21-1, Vt E [T]
14:
for v E V do
t vs (1,)
Offline training (A) do
15:
2: for L
16:
8" + arg min #ES.
8 - 8e|
for v N V do
8t - vs E (..)
17:
eL+1
(UL))
~ NN(:: (.)))
4:
18:
for k E [4] \ (1) do
5:
S. 5 S. U {
v ( ((00i)
(4.) 6: 2. (8:) t enqueue E E++1
19:
s + arg min
(((tk-1)
sES,
7: end for
20:
e
(e Ex(s"))
end for
21:
end for
22:
(l+H(V) t- (4k (v), Yk: E [g]
9: for v E V do
10: (s) f mean (e)n Vs E S,
23:
Update S., Qui (s)), E.(s), Vss E S.
11: (s) f covariance Vs E S.
24:
end for
25: end for
12: end for
Example For the purpose of explaining mspace-SN we consider an example with two nodes n = 2, and feature dimension d = 1. In Fig. 3 we first show the shock vector E, E R The state of shock Et, denoted by (E,) is marked have a
RR2
E1+1
e ((V(E)))
in S E (-1, 1)2. Corresponding to this state, Gaussian distribution N(E; (((()))) Σ (E)))) depicted ellipse. The next shock Ex+1 is sampled from this distribution. This distribution is updated as we gather more information over time. The volume of the Gaussian density in a quadrant is equal to the probability of the next shock's state being in that quadrant, i.e., the tran- sition kernel Pa.a' = S N (e; p(s), Es)) de. There- forc, mspace- -SAace-SWoaae can be viewed Markov chain whose transition function is multivariate Gaussian.
R²²
-1
(ei)
S
Figure 3: Shock Distribution.
4 Related Works
Correlated Time Series Forecasting A set of time series data denoted sx(v), Ve [m], / [T] is assumed to exhibit spatio-temporal correlation (Wu et al. 2021a Lai et al.) 2023 The correlations can then be discerned from the observations to perform forecasting, The correlated time series (CTS) data can be viewed as a temporal graph G = AX, with X, [z)(e))ee[n where the spotial correlation between (x) and (u) is quantified as the edge weight Au,er and A,,, significs the temporal correlation within a,, The architecture of existing CTS forecasting methods consist of spatial (S) and temporal (T) operators. The S-operator can be graph convolutional network (GCN) (Kipf & Welling 2017) or Transformer (Vaswani 2017 As for the T-operator, convolutional neural network (CNN), recurrent neural network (RNN)
et al. [Chung et al. 2014 or Transformer (Zeng et al. 2023) can be used.
Temporal Graph Neural Network A Graph Neural Network (GNN) is a type of neural network that operates on graph-structured data, such as social networks, citation networks, and molecular graphs. GNNs aim to learn node and graph representations by aggregating and transforming information from neighbouring nodes and edges (Wu et al. 2021b). GNNs have shown promising results in various applications, such node classification, link prediction, and graph classification.

---

Published in Transactions on Machine Learning Research (05/2025)
Temporal GNN (TGNN) Longa al. 2023 is extension of GNNss which operates temporal graphs 9. = (X,, Ad) where X, denotes the node features, and A, is the evolving adjacency matrix. The TGNN architecture can be viewed as a neural network encoder-decoder pair (fo. go) (see Fig. 4
A sequence of m past graph snapshots is first encoded into an embedding h4 [o(( 9.)), and then se- quence of future graph snapshots is estimated by the de- coder (9'+1.--
gt-m+1
9++1
fo
9
(h,). The parameters (6, Ø) are trained to minimize the difference between the true sequence (9t+1.-... ... G and the predicted sequence (9t+1, .. Ge-g)- In node feature forecasting, the objective is to minimize the difference between the node feature matrices .x
gt
h
Figure 4: TGNN architecture.
and { ('...... X while temporal link prediction, the goal is to minimize the difference between the graph structures (A.+1, ... Acto) and {A -. Astg).
There are two main approaches to implementing TGNNs: model evolution and embedding evolution. In model evolution, the paramcters of static GNN are updated over time capture the temporal dynamics of the graph, e.g., EvolveGCN (Pareja et al., 2020). In embedding evolution, the GNN parameters remain fixed,
and the node and edge embeddings
updated over time to learn the evolving graph structure and node
features (Li et al. 2018 Zhao et al.) 2019 Micheli & Tortorella 2022
Wu et al. 2019
Fang et al. 2021
Liu
ct al.
2023
The TGNN methods are described in Appendix D.3
Linear Dynamical System In a linear dynamical system (LDS) (Barber 2012). the observation is modelled as a linear function of the latent vector hes The transition model dictates the temporal evolution of the latent state h, A,h1-1 + Th, with ni ~ NN(n; hi, Σt), and the emission model defines the relation between the observation and the latent state y: B,h, + Sr, St N Vr, EY). The LDS describes a first-order Markov model p((3,, ho))=)) = p(h1)p(y1 h1) 11=22p(h p(h 1u-1)p((1 ht), where p(h; 1x-1)= (ht;; A + hr, E), and p(y - h₂) (yy B, + Dr. Ey). Therefore a LDS is defined by the paramcters (A,, E,, E, he Mt) and initial state h1 In simplified models the parameters can be considered time-invariant. Tn the literature, LDS is also referred to Kalman filter (Welch 1997),
Gaussian state space model (Eleftheriadis et al. 2017).
Gaussian Mixture Model A Gaussian mixture model (GMM) (McLachlan et al. 2019 is weighted sum of multiple Gaussian distribution components. An M-component GMM is defined as:
(xx) = - w/ N(x;; p. Ei), ΣiE[M u4 =.
(4)
where wi denotes the probability of the sample belonging to the 7th component. The parameters of the
GMM ((w, M4, Σ,) : Vi E [M] are learnt through
(EM) algorithm (Barber 2012
marimum a posteriori (MAP) estimation, or marimum likelihood estimation (MLE) [Barber 2012 Def. 8.30).
Network Vector Autoregression Network Vector Autoregression (NVAR) builds upon traditional vector autoregression models which capture the relationship among multiple time series by incorporating network structure (hhu et al. 2017). Developments, such as Graph VARMA (Isufi et al. 2019) and Graph GARCH (Hong ct al. 2023) further refined the NVAR framework by addressing issucs related to non-lincar dependencies and heteroskedastieity Although in this work, we have not compared our approach with NVAR methods, future work can be dedicated to comparing mspace with different variants of NVAR.

---

Published in Transactions on Machine Learning Research (05/2025)
5 Results
Baselines & Datasets We compare the performance of mapace with the following recent TGNN baselines: DCRNN (Li et al. 2018), TGCN (Zhao et al. 2019), EGCN-H [Pareja et al., 2020), EGCN-O Parrja et al.) 2020
DynGESN (Micheli & Tortorella 2022). GWNet (Wu et al.
2019), STGODE Fang et al. 2021 FOGS (Rao el al. 2023) Additionally, we also evaluate the performance
2022), CRAM-ODE (Liu al. 2023), LightCTS (Lai et al.
of classic autoregressive method ARIMA (Box Pierce 1970), and the famous LDS, the Kalman filter (Welchy
1997p. We introduce two variants of the Kalman filter: Kalman-z, which considers the node features observations, and Kalman-e, which operates on the shocks. For more details, please see Appendix D
Table 1: We use the datasets temnis, wikimath, pedalme, and cpox for single-step forecasting as they are relatively smaller in terms of number of nodes n and samples T. For multi-stpp forecasting traffic datasets PEMS03, PEMS04, PEMSO7, PEMS08, PEMSBAY, and METRLA. The datasets 00M1003/0407//// report traffic flow, while PEMSBAY, and METRLA report traffic speed.
the larger
tennis
wikimath
pedalme
cpox
PEMS03
PEMS04
PENS07
PEMS08
PEMSBAY
METRLA
1000
1068
15
20
358
307
883
170
325
207
120
731
26K
17K
28K
18K
52K
34K
Single-step Forecasting In Table 2 have single-step forecasting RMSE results for various models with training ratio 0.9. The best result is marked bold, and the second-best is underlined.
The models DCRNN, ECGN, and TGCN exhibit similar performance across all datasots, which may be at- tributed to their use of convolutional GNNs for spa- tial encoding. Kalman-e performs poorly across all datasets, indicating challenges in establishing a state- space relation for shocks. In contrast, Kalman-w: performs notably well, outperforming other meth- ods on tennis and pedalme datasets. We did not investigate why Kalman filters perform poorly when applied to shocks. However, it can be explored in future work.
Table 2: Single-step forecasting RMSE, (M
tennis
wikimath
pedalme
cpox
DynGESN
150.41
906.85
1.25
0.95
DCRNN
155.43
1108.87
1.21
1.05
EGON-H
155.44
1118.55
1.19
1.06
EGCN-O
155.43
1137.68
1.2
1.07
TGCN
155.43
1109.99
1.22
1.04
LightCTS
199.04
319.47
1.58
0.84
GRAM-ODE
206.50
484.90
0.99
0.98
STGODE
172.16
279.87
0.91
0.83
mapace-Sy1
105.32
563.69
0.86
1.58
mapace-SA
117.23
725.42
1.35
2.11
For wikimath and cpox, STGODE shows the best per- formance, followed by LightCTS and GRAM-ODE, po- tentially due to higher number of training samples. The light-weight methods such as Kalman-an a and mspace exploit the unavailability of cnough training samples and perform better on temnis and pedalme.
Kalman-we
73.01
792.6
0.66
1.42
Kalman-e
7.5K
64K
1.79
10.2
We notice that mspace-Sy achieves a balanced performance between TGNN models and Kalman-w across all datascts except for cpox. The subpar performance of mspace-S* on the cpox dataset may be attributod the seasonal trend, given that it represents the weekly count. of chickenpox cases.
Multi-step Forecasting For the TGNN models, use the 2: 2 train-validatiinntes chronological split in line with the experiments reported by the baselines. For mspace and Kalman, the train-test chronological split is 8 : 2, as they do not require a validation set. In Table 3 we report the multi-step 4 12 forecasting RMSE, and mean absolute error (MAE) on the test set. For mspace, the queue size M 20
Figure 5 shows the RMSE of the models, normalized the minimum RMSE for the dataset, plotted against the number of available training sample[A We observe that mspace-Ty performs competitively across all datasets with the exception of METRLA. Moreover, mяраcе-Tи demonstrates superior performance compared to mspace-Sıı across all the datasets which suggests that temporal auto-correlation dominate spatial cross-correlation among the nodes.
2g = 12 corresponds one hour in the traffic datasets used. Sa higher value of M might give better estimates at the of higher memory usage and lower adaptability. We refer to the number of training samples the training size.
8

---

Published in Transactions on Machine Learning Research (05/2025)
Table 3: Multi-step forecasting RMSE and MAE, 20)
PEMS03
PEMS04
PEMS07
PEMSO8
PEMSBAY
METRLA
RMSE
MAE
RMSE
MAE
RMSE
MAE
RMSE
MAE
RMSE
RMSE
MAE
GRAX-ODE
26.40
15.72
31.05
19.55
34.22
21.75
25.17
16.05
3.34
1.67
6.64
3.44
STGODE
27.84
16.50
32.82
20.84
37.54
22.99
25.97
16.81
4.89
2.30
7.37
3.75
DCRNN
30.31
18.18
38.12
24.70
38.58
25.30
27.83
17.86
4.74
2.07
7.60
3.60
ARIMA
47.59
33,51
48.80
33.73
59.27
38.17
44.32
31.09
6.50
3.38
13.23
6.90
GWNet
32.94
19.85
39.70
25.45
42.78
26.85
31.05
19.13
4.85
1.95
7.81
3.53
LightCTS
30.14
18.79
23.49
14.63
4.32
1.89
7.21
3.42
FOGS
24.09
15.06
31.33
19.35
33.96
20.62
24.09
14.92
mapace-Sji
36.51
26.43
18.85
13.25
54.39
38.83
14.61
10.36
4.27
2.17
10.24
6.56
mspace-Tμu
26.53
18.31
13.49
8.70
38.63
24.02
10.35
6.33
3.77
2.19
10.08
6.77
Kalman-w
45.38
33.21
33.75
15.26
64.95
48,01
27.40
12.40
5.71
3.87
13.97
10.7
Kalman-e
749
619
818
709
2313
1988
460
399
50.2
43.1
127.1
109
GRAM- ODE
LighCTS
4.0
STGODE
FOGS
PEMSO8
DCRNN
mspace-Sp mspace-TA -M
3.5
ARIMA
RMSE/min(RMSE)
GWNet
Kalman-xi
3.0
PEMS03
METRLA
PEMSBAY
PEMS07
2.5
2.0
PEMSO
1.5
1.0
10
3x 10
10
# samples
Figure Multi-step forecasting normalized RMSE.
TGNN models, being neural networks, rely heavily on the amount of training data available. With the relatively small number of training samples in PEMSO4 and PEMS08, these models underperform. In contrast, both variants of mspace significantly surpass the state-of-the-art (SoTA), demonstrating their effectiveness with smaller d Furthermore, mspace-Tpp ranks as the second-best model for the largest datasct, PEMSBAY. Therefore, we conclude that mspace oflers consistent performance across datasets with varying sample sized c and is particularly advantageous when training data is limited.
In Fig. we illustrate how the RMSE scales with the number of forecast steps q for different variants of mspace The scaling law for mspace-S* appears linear, while for mspace-T+, appears sublinear. We investigate this theoretically in Appendix A
The TGNN basclines perform forecasting for 9 = 12 future steps, relying on the node features from the preceding 12 time steps as input. In contrast, mspace requires only the node features from the two previous time steps. Additionally, mspace has the flcxibility to forecast for any E N, whereas TGNN models are limited to forecasting up to the specified number of steps they were trained on. Moreover, mspace offers both probabilistic (Qx) and deterministic (Ω2,) forecasts, a capability absent in the baselines. Finally, while TGNN baselines exploit the edge weights information for predictions, mspace achieves comparable results using only the graph structure.
singgl-sstep forecasting datasets have prohibitively low number of samples (< 800), likely limiting mspace's performance compared multi-step forecasting with 17k samples.
Another approach to study the impact of training size
fixed test and vary the training fraction given suggested by reviewer during the discussion and is worth mentioning.
dataset. While we did this experiment, We acknowledge that including error scaling for the haselines could have provided more comprehensive comparison.

---

Published in Transactions on Machine Learning Research (05/2025)
120
PEMS03
60
PEMS04
PEMS07
45
PEMS08
RMSE
80
RMSE
RMSE
RMSE
30
100
40
20
50
15
12
24
36
48
12
24
36
48
12
24
36
48
12
24
36
48
9
9
Figure 6: Scaling of error with the number of forecast steps q using different mspace variants: mspace-TA, mspace-Sμ, mapace-Tиı
mspace-SA,
6 Interpretability
In this section, we examine mspace in light of the following definition of Interprotability,
Definition 6.1. Consider data a E 'D which processed by a model Fø to produce the output ÿ E y, ie., ý = Fa( where denotes the model parameters. Moreover, consider true mapping / + y: Va where y is the ground truth associated with the input data æ. Then, an interpretable or explainable model Fo fulfils one or more of the following properties (Gilpin et al. 2018 Du et al., 2019
The internals of the model Fa can be explained in way that is understandable to humans.
The output ÿ can be explained in terms the properties the input æ, the input data distribution D, and the model parameters 0.
The failure of model on a given input data can be explained.
For a certain distance metric y x y Rt theoretical bounds on the expected error Ba Fo()))) can be established basod on the description of Fo, supported by the assumptions on the input data distribution D.
It can be identified whether the model Fg is susceptible to training bias, and to what extent.
6.1 Explaining s
In Fig. 7 we depict two consecutive snapshots of a subgraph, focused on node v. The dashed circle highlights the corresponding 1-hop neighbourhood Uy At any time f, draw green and red arrows next to the nodes to depict whether its node feature value increased or decreased, respectively.
Lky
Up
t=
Figure 7: Consecutive subgraph snapshots.
The design of Vs was inspired by the correlation dynamics of the stock market Caraiani 2014). where the inter-connecteddnss of various stocks exerts mutual influence on their respective prices. For instance, within the semiconductor sector, stocks such as NVDA, AMD, and TSMC often exhibit synchronised movements, with slight lead lag. Similarly, the performance of gold mining stocks can offer insights into the future value of physical gold and companies engaged in precious metal trade. This concept transcends individual industries and encompasses competition across multiple sectors.
10

---

Published in Transactions on Machine Learning Research (05/2025)
Let record the states at two consecutive time-steps St []
-1] and 8t,+1
[-1 -1 -1 1] At the state-level, iterate through the time-steps, and collect all the states succeeding = -1 1 -1]" If then draw random sample from this collection of succeeding stales, we can interested in pre-
predict whether the node feature value is more likely to increase decrease. However, dicting the amount of change. Therefore, at every time step when the state & matches = -1 -1] Rb) we collect the succeeding shock (ba) in a queue Qx(8), i.e, at time 2x(8) = [(1 8, 8, vl < with [2)( S M. The queue entries are then used to approximale distribution from which a random sample is drawn during forecast.
In Fig. we plot the normalized histogram of the trace tr(-) of the covariance matrix (s) of all the states Su, P [n]] for all the datasets used in multi-step forecasting. We notice that in both PEMS04 and PEMS08 the distribution of values is skewed to the left, with concentration of data points at values close to zero This explains the better-than-SoTA performance of mapace-Su on these datasets. In contrast, the histogram of METRLA is completely away from zero, while for PEMS03, and PEMS07 there are peaks near zero, but a major mass of the histogram skewed away from zero. This explains the poor performance mspace-Sy on these datascts.
0.002
PEMS03
0.003
PEMS04
0.001
0.001
0.000
0.000
500
1000
1500
2000
2500
500
1000
1500
2000
2500
0.0015
PEMS07
PEMSO8
0.0010
0,004
0.0005
0.002
0,0000
500
1000
1500
2000
2500
500
1000
1500
2000
2500
0.4
PEMSBAY
METRLA
0.02
0.2
0.01
0.00
0
2
8
10
20
40
60
80
100
Figure 8: Normalized histogram of (tr(E(s)) V8 E S,, Vo E [n]} for different datasets.
We represent data variance using the trace of the covariance matrix. Thus, if the variance histogram is close to zero, it indicates low variance. The error in estimating samples from distribution is lower if the variance of the distribution is lower, and vice versa.
6.2 Explaining Tr
Next, we discuss the rationale behind Vr, which is designed to identify periodic patterns. For instance, in many traffic networks, trends exhibit weekly cycles, with distinct patterns on weekdays compared to weekends. Moreover, on an annual basis, the influence of holidays on traffic can be discerned, as people engage in shopping and other Icisure activitics. In Fig. we have shown the traffic flow value of PEMS04 with weekly (a) and daily (b) periodicity. For the weekly periodic view (a), the trend is more pronounced with less deviation from the mean while for the daily view (b), a scattered trend is visible with high variance across states.
11

---

Published in Transactions on Machine Learning Research (05/2025)
600
500
400
400
300
300
200
200
100
100
1000 1250 1500 1750 Emod To
rmod To
(a) PEMSO4: Weekly
(b) PEMSO4: Daily
Figure 9: Periodic trends in the traffic dataset PEMS04; the black points represent the data-points, and the red line the mean estimate for each state mod Tp-
6.3 Error Bounds
We present the error bounds of mspace in the following theorem, detailed proof of which can be found in Appendix
Theorem 6.1. The RMSE of mspace for g-step node feature forecast is upper bounded as RMSE(1) s Vaq² + (3a + 3)q (2a + B), where a, 3 E R++ are conslants that depend on the dala, as well as the varianl of the mspace algorithm.
Corollary 6.1. In the asymptotic case of large q, the RMSE grows linearly with q: RMSE(() = O
6.4 Complexity Analysis
We denote the computational complezity operator as C(-), and the space complerity operator as M..), where the argument of each operator is an algorithm or a portion of an algorithm. The optional offline part of mspace is denoted by A, while the online part is denoted by B. In Table 4 we exhibit the computational and space complexities of the different mspace variants, where b max,e (m) [u is the maximum degree. For more details please refer to Appendix B
Table Computational and space complexity of different mspace variants. Vr
U/
C(A) (ndb (TT dbM min (ri,(rT2bbd)) 2bd))) C(B) o (11 r)Tnd212 (qdb M min
C(A) = o (nrT + d M
Ow
(1 25d
C(B) o ((1 r)TTnd (gd + MTo))
V7(AU B) o (d(M d)yo)
27(A B) = O (db(M M + db) min (T, 2/d))
((A) = O (ndb (rT + M min (ri, (ndd)))
((A) O (nrT + dMnr))
22
C(B) = O (11 - r)Tnbb(q M) min (220 2bd)
C(B) = O ((1 - -))nnlgg++++ M)
mI(A B) O (M min (T,2
MT B) 0 (Mdr0)
Theorem 6.2. For asymptotically large number of nodes n and timesteps T, the computational complezity of mspace is O(T)), and the space complerity is O(1) across all voriants.
The proof is detailed in Appendix
B.2
12

---

Published in Transactions on Machine Learning Research (05/2025)
7 Discussion
In this section discuss the limitations of mspace and how they be overcome. Firstly, mapace only considers binary edges, i.e. A E {0, 1jwxn instead of weighted adjacency matrix A E R This does not imply that we have used datasets with bimary edges, rather it means that we have used a binarized version of the adjacency matrix as input to mspace while the basclines exploited weighted edges. Secondly, we assume that the graph structure is fixed throughout, while for a truly dynamic graph, the graph structure should also be dynamic. Lastly, we have proposed two state functions: one that focuses on cross-correlation among the nodes, and the other that considers seasonality. Therefore, a state function which combines both can be studied in extension of our work in the future.
On creating a state function which combines Vs and Vr We can define sT R (-1,
10 To - 1} as VST (e(4), t) A (Tign(e(())T t mod To In essence, the queues (s)s), E S., Yo E [n] in mspace-ST would have lesser entries compared to mspace-S S which might lead to poor estimates and consequently make the algorithm data-intensive. Furthermore, in step where we find the closest state s the spatial and temporal parts can be assigned different weights: s" + -argging min.sss.. where y E I
[Laz
7]
8 (.))
On benchmarking using diverse datasets Experiments on more diverse datasets would help establish the performance of the proposed algorithm. In this work, we have used non-traffic datasets for single-step forecasting, and 6 traffic datasets for multi-step. The proposed algorithm mapace has general formulation, and is not designed specifically for traffic datascts; mspace (of any dimension) evolve with lime. We also proposed a synthetic temporal graph generation method in A Appendix C to alleviate the data scarcity issue in temporal graph learning.
be applued to any graph whose node features
8 Conclusion
In conclusion, our proposed algorithm, mspace, performs at par with the SoTA TGNN models across various spatio-temporal datasets. As an online learning algorithm, mspace is adaptive to changes data distribution and is suitable for deployment in scenarios where training samples are limited. The interpretability of mspace sets it apart from black-box deep learning models, allowing for clearer understanding of the underlying mechanisms driving predictions. This emphasis on interpretability represents a significant step forward in the field of temporal graph learning. In Sec. we discussed the potential limitations of mapace.
In addition to the algorithm, we also introduce a synthetic temporal graph generator (see Appendix C in
which the features of the nodes evolve with the influence of their neighbours a non-linear manner. These synthetic datasets can serve a valuable resource for benchmarking algorithms.
References
David Barber. Bayesion reasoning and machine learning. Cambridge University Press, 2012.
Claudio DT Barros, Matheus RF Mendonça, Alex B Vieira, and Artur Ziviani. A survey on embedding dynamic graphs. ACM Computing Surveys (CSUR), 55(1):1-33 37, 2021.
Ferenc Béres, Róbert Pálovics, Anna Olåh, and András A Benczúr. Temporal walk based centrality metric for graph streams. Applied network science, 3:1-26, 2018.
G. E. P. Box and David A. Pierce. Distribution of Residual Antocorrelations in Autoregressive-Inteenn Integratee Moving Average Time Series Models. Journal of the American Statistical Association, (133))):1500 15033)21:10-112 1526, December 1970. ISSN 0162-1459. doi: 111100//0122149917700000...0
Petre Caraiani. The predictive power of singular value decomposition entropy for stock market dynamics. Physica A: Statistical Mechanics and its Applications, 393:571-578 2014.
13

---

Published in Transactions on Machine Learning Research (05/2025)
Junyoung Chung, Caglar Gulcehre, KyungHyun Cho, and Yoshua Bengio. Empirical Evaluation of Gated Recurrent Neural Networks Sequence Modeling, December 2014. URL http://arxiv.orgg has//baa//a 1412 3555 arXiv:1412.3555 [es].
Songgaojun Deng, Huzefa Rangwala, and Yue Ning. Learning dynamic context graphs for predicting social events. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Dala Mining, pp- 1007-1016, 2019.
Mengnan Du, Ninghao Liu, and Xia Hu. Techniques for interpretable machine learning. Communications of the ACM, 63(1):68 77, 2019.
Stefanos Eleftheriadis, Tom Nicholson, Marc Deisenroth, and James Hensman. Identification gaussian process state space models. Advances neural information processing systems, 30, 2017.
Zheng Fang, Qingqing Long, Guojic Song, and Kunqing Xic. Spatial-Temporal Graph ODE Networks for Traffic Flow Forecasting. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 364 373, August 2021. doi: 00.1145/4447548.34674444 URL http://arxiv org/abs/ 2106. 12931 arXiv:2106.122: 12931 [cs].
Chen Gao, Xiang Wang, Xiangnan He, and Yong Li. Graph neural networks for recommender system. In Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining, pp. 1623-1622) 2022.
Leilani H Gilpin, David Bau, Ben Z Yuan, Ayesha Bajwa, Michael Specter, and Lalana Kagal. Explaining explanations: An overview of interpretability of machine learning. In 2018 IEEE 5th International Conference on data science and advanced analytics (DSAA), pp. 50-89. IEEE, 2018
Junping Hong, Yi Yan, Ercan Engin Kuruoglu, and Wai Kin Chan. Multivariate time series forecasting with garch models on graphs. IEEF Transactions Signal and Information Processing over Networks, 9: 557 568, 2023.
Shenyang Huang, Farimah Poursafaei, Jacob Danovitch, Matthias Fey, Weihua Hu, Emanuele Rossi, Jure Leskovee, Michael Bronstein, Guillaume Rabusseau, and Reihanch Rabbany. Temporal graph benchmark for machine learning on temporal graphs. Advances in Neurol Information Processing Systems, 36:2056 2073, 2023.
Elvin Isufi, Andreas Loukas, Nathanael Perraudin, and Geert Leus. Forccasting time series with varma recursions on graphs. IEEE Transactions on Signal Processing, 67(18):4870 4800:488888-85 2019.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017. URL https://openrevvie..nt htt.rrrrrreeeeeeeoo/mouiiiii
SJ
Zhichen Lai, Dalin Zhang, Huan Li, Christian S Jensen, Hua Lu, and Yan Zhao. LightCTS: A lightweight framework for correlated time series forecasting. Proceedings of the ACM on Management of Dala, 1(2): 1-26, 2023.
Yaguang Li, Rose Yu, Cyrus Shahabi, and Yan Liu. Diffusion convolutional recurrent neural network: Data-driven traffic forccasting. In International Conference on Learning Representations, 2018. URL https://openreview.. o
Zibo Liu, Parshin Shojaee, and Chandan K. Reddy. Graph-based multi-ODE neural networks for spatio- temporal traffic forecasting. Transactions on Machine Learning Research, 2023. ISSN 2835-8856. URL
Antonio Longa, Veronica Lachi, Gabriele Santin, Monica Bianchini, Bruno Lepri, Pictro Lio, Andrea Passcrini, al. Graph neural networks for temporal graphs: State of the art, open challenges, and opportunities. Transactions Machine Learning Research, 2023.
14

---

Published in Transactions on Machine Learning Research (05/2025)
Geoffrey J McLachlan, Sharon X Lee, and Suren I Rathnayake. Finite Mixture Models. 2019.
Alessio Micheli and Domenico Tortorella. Discreto-time dynamic graph echo state networks. Neurocomputing, 496:85 95, 2022. Publisher: Elsevier.
Aldo Pareja, Giacomo Domeniconi, Jie Chen, Tengfei Ma, Toyotaro Suzumura, Hirokí Kanezashi, Tim Kaler, Tao Schardl, and Charles Leiserson. Evolvegen: Evolving graph convolutional networks for dynamic graphs. Tn Proceedings of the AAAI conference artificial intelligence, volume 34, pp. 5363-5371 2020. Issue: 04.
Fotios Petropoulos, Daniele Apiletti, Vassilios Assimakopoulos, Mohamed Zied Babai, Devon Barrow, Souhaib Ben Taieb, Christoph Bergmeir, Ricardo Bessa, Jakub Bijak, John E Boylan, al. Forecasting: thoory and practice. International Journal of forecasting, 38(3):705-877 2022.
Xuan Rao, Hao Wang, Liang Zhang, Jing Li, Shuo Shang, and Peng Han. FOGS: First-Order Gradient Supervision with Learning-base based Graph for Traffic Flow Forecasting. In Proceedings of the Thirty-First
International Joinl Conference on Artificial Intelligence, pp. 3926 3926-3932, Vienna, Austria, July 2022. International Joint Conferences Artificial Intelligence Organization. ISBN 978-1-956792-00-- doi: 10.24963 1/24963/jjcai..2 20c2ii..022/45.. URL https://wwai ijcai wttg/prroceddnng////////555
Benedek Rozemberezki, Paul Scherer, Yixuan He, George Panagopoulos, Alexander Riedel, Maria Aste- fanoaei, Oliver Kiss, Ferenc Beres, Guzman Lopez, Nicolas Collignon, et al. Pytorch geometric temporal: Spatiolemporal signal processing with neural machine learning models. In Proceedings of the 30th ACM international conference on information & knowledge management, pp. 4564 4573, 2021a.
Benedek Rozemberezki, Paul Scherer, Oliver Kiss, Rik Sarkar, and Tamas Ferenci. Chickenpox cases in hungary: A benchmark dataset for spatiotemporal signal processing with graph neural networks. In Workshop on Graph Learning Benchmarks@ The WebConf 2021, 2021b.
Robert Н. Shumway and David S. Stoffer. Time Series Analysis and Its Applications: With R Exam- ples. Springer Texts in Statistics. Springer International Publishing, Cham, 2017. ISBN 978-3-319- 52451-1 978-3-319-52452- doi: 10.1007/978-3- 00000/998--311-5245555 978-3-319-52452-1
URL http:://ink..prrr trinkk.sprngger. c0m/10.10000
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is All you Need. Neural Information Processing Systems, 2017.
Liyuan Wang, Xingxing Zhang, Hang Su, and Jun Zhu, A comprehensive survey of continual learning: Theory, method and application. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024.
Yifei Wang, Yisen Wang, Jiansheng Yang, and Zhouchen Lin. Dissecting the diffusson process in linear graph convolutional networks. In NewrlPS, pp. 5758 5769, 2021. URL http:://proceetiigs.eees neurips abt. html
Greg Welch. An Introduction to the Kalman Filter. 1997.
Xinle Wu, Dalin Zhang, Chenjuan Guo, Chaoyang He, Bin Yang, and Christian Jensen. AutoCTS: Automated correlatod time scries forecasting. Proceedings of the VLDB Endowment, 15(4):971-983, 2021a.
Zonghan Wu, Shirui Pan, Guodong Long, Jing Jiang, and Chengqi Zhang. Graph wavenet for deep spatial- temporal graph modeling. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pp. 1907-1913, 2019.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A Comprehensive Survey on Graph Neural Networks. TEFE Trunsactions on Neural Networks and Learning Systems, 32(1):4 24, January 2021b. ISSN 2162-237X, 2162-2388. doi: 2000/NNNLSS.2000.22.2222 https://ieeexplore. ieee. wwtpeee.///ccceeee//eeee//e
URL
Bing Yu, Haoteng Yin, and Zhanxing Zhu. Spatio-temporal graph convolutional networks: a deep learning framework for traffic forecasting. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, pp. 3634 3640, 2018.
15

---

Published in Transactions on Machine Learning Research (05/2025)
Ailing Zeng, Muxi Chen, Lei Zhang, and Qiang Xu. Are transformers effective for time series forecasting? In Proceedings of the AAAT conference on Arlificial Intelligence, volume 37, pp. 11121-11128, 2023.
Ling Zhao, Yujiao Song, Chao Zhang, Yu Liu, Pu Wang, Tao Lin, Min Deng, and Haifeng Li. T-gen: A temporal graph convolutional network for traffic prediction. IEEE transactions on intelligent transportation syslems, 21 (1)988884 3858, 2019. Publisher: TEEE.
Xuening Zhu, Rui Pan, Guodong Li, Yuewen Liu, and Hansheng Wang. Network vector autoregression. 2017.
A Error Bounds
Upper Bound
We derive the upper bound on the RMSE for q-step iterative forecast below.
Proof of Theorem 6.1 For nodes in Up v E [n], the shock at time t is sampled from a Gaussian distribution,
the parameters of which depend on the previous shock e("A)) through the state function:
(lae) N (e:
Vs (((4)))
Us ( )))
E
(5)
We denote the shock estimated for node v at time & as:
év( E (240) (0) N (é: MAu (is (e(m)))
Ev
( (Mte)
(6)
The mean square for g-step iterative node feature forecasting is defined as:
MSE(2)=
E
Σ
Σ
Σ
(v+ Ex)((T)
ndq
vE(m)
k
jE(1
1 ΣE ndq
Σ
- Ec+s(()
VE(M)
JE
The shock difference between the true shock and predicted shock also follows Gaussian distribution:
Eltj(1) (u+ ~ N (E: (Us (e!(=:) (0t)(1),E) Ev Us ( (344)) ((44)11))
(8)
Since, the sum of Gaussian r.v.s is also Gaussian, we have:
Σ ()) (v) N E; Σ Hv jEli
Uss (e!(-))) E(ts(1), Σ E, Uss (e(4))
(9)
JEM
jE(1]
Morcover, for Gaussian r.v. x~ N(x; fe, E), E ||
= -1lee112 tr(E).
E
Σ (v4 (1))(()(())))
= ur Uss (s(4)--)) E(4s(U)
JE
Jel
Σ tr E Us
(10)
16

---

Published in Transactions on Machine Learning Research (05/2025)
Σ Mo Vss (e(t>-1) - Ec+s(v) jE(t)
Vs (e(tt)) (etts-1) Ec+ Er+s(1)
5
M4
Vs ((44)) ((it)11) E(+)(1)
S i max
p/
v (e(4--1) - Ec+
S
max KJeN
Mv
aa,11
(11)
Σ jE(1
tr
Us (1,))
(e())-)))
< i max tr ]c({]
E. (vs
(lh (Eits-1))) S 0x,2
(12)
E
Σ 1E
((+s(1) - E(+)(0)
S 5p.1 12 + 02. -2, 00,1, 02,2 RR
(13)
MSE(1)= S ndg
Σ Σ av,1 12 + 0v,2 1
vE[n] kElo)
E Enein 0w,1
Evelnl 0n,2 2nd
(a + 1)(g + 2) +
(g + 1).
(14)
6nd
Let a 2 15 End EuEje av,1; and 2 1 Eve(n) av,2, then
2nd
MSE(4) S au²² + (3a + 3)g + (2a + B).
(15)
By Jensen's inequality,
RMSE(2) S /MSE(q) S Vag² + (3a + 3)q + (2a + B).
(16)
The above proof is for mspace-SN SN and also applics to mspace-TN. For mspace-Spi and mspace- Tyu, B =
Lower Bound Similarly, we can find a lower bound on the MSE for q-step iterative forecast:
E
Σ (1) Elt(()) EE
En
U/' (e(4;-1))
SER
Σn Us (a( ( 1))
i min tr
i- -00.3
(17)
jEli
MSE(a) 2 ndg vE(N) kE(y)
Σ
0r,3
nd Σ av,3
-qq 1) 88 3'q+8 Br.
(18)
vE|m]
gr
17

---

Published in Transactions on Machine Learning Research (05/2025)
B Complexity Analysis
B.1
Computational Complexity
We denote the computational complexity operator as C(), the argument of which is an algorithm or part of an algorithm. The optional offline part of the algorithm is denoted as A while the online part is denoted as B.
Algorithm MMpace-SN
Input G = E,,E, X), TE 10, M
Output (v(v) Ve WEE,tE (I.-TT
1: Ev( + (1) xv)) V t, [T] Offline training (A):
2: for t 1 [[]] do
for V EE V do
8t (t)) V Et
Un)
EvED dlu
S. U-S.u u
8t
(M))
n
2. (Ma)
8t
enqueue E
P
end for end for
9: (s(ss) + mean (Q))s), E S,
B Evey SS
10: Ex(s) + covariance( (x)), vs E eEV
D
Online learning (B):
11: for E [[]r-T].
q) do
12:
for V E V do
13:
8, (1)) V E
(u))
Ever dll
14:
s" arg min seS.
8 (U6)
Σ EVEV dRHoolSsp
15:
(1a)) ~ N(e; (8 [x()))
4 Σ EvEy((uldd)
16:
for K E [2, q do
17:
(e(4k-1) )) elu))) ~ (.") Es(()))
+ arg min
b 1) x EvEr d/441(1 + (8o1)
sES
18:
b - 1) x (
19:
end for
20:
(x+x(U)= + (ll)) (v),
Vk [g]
21:
Update S,, Q.
>> 2n Evev + 1d(,.13))
22: Update (s), (s),,,
Vs S,
23:
end for
24:
end for
Computational complexity of offline training for aspace-SN can be written as:
C(A) - [rT]d] 1u +
[T dM Σ U.IIS.I+
&M
Σ u P1s
(19)
[5].
[4]
[9] (menn)
covarriac))
18

---

Published in Transactions on Machine Learning Research (05/2025)
Computational complexity of online learning for mspace-SA can be written as:
T-q
C(B) o
Σ
dq Σ Mul + dq
Σ s.l. d' Pa
Uo
+ +22
[TT]
[21]
[13]
[1/]//17]
[ssmplii(()))linngg
)
dM Σ U.l|sa + d Σ 14.11
(20)
[22] (meen))
(covaaiii)))
Lemma B.1.
The compulational complexity of mspace-SN is:
C(A) 0 [dbnr'I dd6222M Mn min (1T, 2hd).
C(B) o (a (1- (1-r)Tnddb qdb + M min
(1 +
T, 2nd 1))-
2
where = max [M).
Proof. We denote the maximum degree of a node as - max,e[m] [el < n which does not necessarily scale with n unless specified by the graph definition. Furthermore, the total number of states observed for node till time step e N cannot exceed t, i.e., S t. We also know the total number of states theoretically possible for node is 2|u,1d for Vs(-)) Therefore, the number of states observed till time t for node e is upper bounded as: [S.| min {t.2"d). Based on this, can simplify equation 19 and equation 20 as follows:
C(A) O (dbnr'I + 2nrT (dbM &) min((T2,24))
O AbmrT + d2t Mn min (in(rr.2bd))
T-4
C(B) o
Σ
qdbn + gd 2n - db(g + M)n min(t, 2 + Mn min 2bdg
Σ
nd (db(q + M) 62b mintl, 2
|=|r|]
0 (1 r)T qd db min (11 -2) 2nd - (1-r)T})
0 (1-r)Tn
r)n qdpt3 8b PM min
(1 (1+r) T, 2nd 1))
Lemma B.2. The computational complezity of mspace is:
C(A) o 0 (dlnrT [dbnrT+dbbll dbMM min (rT,
C(B) = (1- (1-r)Tndb(q + M) min
(1 + r) T. 2nd 1).
2
Proof. The sampling steps [15], and [18] in Algorithm are replaced with eQu. pu(s)) which has a computational complexity of Odd((.)) Moreover, Q,((.) does not require the covariance matrix, therefore
19

---

Published in Transactions on Machine Learning Research (05/2025)
do not need to compute it. We simplify the computational complexity expressions
C(A) 00
[rT] d Σ [4 + [rT]2n + dM Σ [uelsse]
0 dbbr'T + dbMn min(r1,20)) (1T22
T-9
((B)
0
Σ
dg
Mn + dg Σ 11 ||Sb] + dg Σ Mol
+n + dM Σ (4.11ss1) }
1= [+[
(sampling))
=0
2qdbn + 2n + db(q + M M)n minst, 2
0 (1 r TnTbbbl + M) min [1+
T, 2hdd }):
2
Lemma B.3. The computational complezity of mspace-TN is:
C(A) = O (nrT + dl MnTo),
C(B) o (11 (1-r)TTiie Tnd (M + qd)).
Proof. For the state function V7, the total number of states for any node is the period TO E E,, i.e., |S, S To- Moreover, the state calculation 8, < vr(()) has computational complexity of O(1). Most importantly, for VT, as it only focuses on the seasonal trends.
C(A) = 0 [rT] Σ 1 [rT]2n + dM Σ U0 + d M Σ Un 1m PIS
O (3nrT + dM d dnno O (nrT + dd (MM)))
T-q Σ (=[r1)
((B) = o
+ dg Σ R.11Sa1 + dd Σ 11 3 + 2n
[ [ol + d Σ 14 14. P|S (15.1} }
+ dM Σ
O (lg + dqto + qdd +2+ dM + d MTo} n(1 - r)
= (0((-r))m (M + +dd)
Lemma B.4. The compulational complerity of mspace-Ty. C(A) = 0 (nrT dT))
C(B) = 0(1 -rrrrrTnnn d(g + Myn)
20

---

Published in Transactions on Machine Learning Research (05/2025)
Proof. Based on the explanation provided for mspace-IN, simplify the computational complexity expres- sions for mspace-Tyu as:
((A) O [rT] Σ
[rT]2n dM Σ S
O (3nrTT ddNnT)) O (nrT + dMMFt).
C(B) o (
T-q
Σ
Σ 1+ 1+ dq Σ S + 2n dM Σ |So1
q
(=[r]]
0 10 doto + d n(1 r)rr 0 ( r)In d(g + M)
B.2 Space Complexity
We denote the space complexity operator as M).,), the argument of which is an algorithm or part of an algorithm. The variables offline training are re-used online learning B. Therefore, we can say that (B) 27(AU) UB).
In implementation of mspace where forecasting is sequentially performed for each node E [n], memory space can be efficiently reused, except for storing the outputs. This approach optimises memory usage, resulting in space complexity characterised by:
DT U B) = O
max d. Mddu + Id vE(n] EE(T]
+ =(dd
Sel + d(u
(21)
VeES,
(a VoES.
Va(s)
Lemma B.5. The space complerity of mspace-SN is ((AA = (ab + db) min (T,2k))
Proof. Simplifying equation 21
results in:
DT(AUB) 0
max (db + ccMd cdb + cd((3))8.,) + + vE(n], AE(T)
= (e((MMdb + edfti). max min (ab((M + db) min (T, 2
SE[T]
Lemma B.6. The space complerity of mspace-Sj. is M[ J B) o O(dbb min (T,
Proof. Some space is saved in mspace-SJı as we not need to store the covariance matrices.
27 (AU = O max (db cMdb + cdb) Sel + db -((Mbb min(T,29 2h))
of (E[T]
Lemma B.7. The space complerily of mspace-TN is AM(ABB) = od((M + dyro)
21

---

Published in Transactions on Machine Learning Research (05/2025)
Proof. As explained earlier, for the state function Wr. 1. Therefore, the queues only store the shock vectors for single node, and not the neighbours. The space complexity expression is simplified as:
max (d +d+ cMd + cd + edr))S.l - db =O(d(M + ddyo). vE(n).
(AUB)) =
[E[T]
Lemma B.8. The space complerity of mspace-Ty, is of (ddd)).
Proof. (I (B(AUB)- 0 maxxeln) (d cMd + + +d] =o(Mdro). TE[T]
Asymptotic Analysis Theorem 6.2 states that for asymptotically large number of nodes n and timesteps T the compulational complerity of mspace is OnTT), and the space complecity is O(1) across all variants.
Proof. We analyse the lemmas B. introduced in this section for the asymptotic case of very large n and T. For very large T, min (1+rT 2dd 2nd Similarly, min 2dd + 2nd Considering the terms r, d, M, 4, To, b as constants, the computational complexity for both offline and online parts of all the mspace variants becomes OnTT)) for asymptotically large n, T.
Furthermore, the space complexity terms lack n T for very large T, which allows us to conclude that the space complexity of all the variants of mspace is constant, i.c., O(1).
C Synthetic Datasets & Experiments
In traffic datasets, seasonality outweighs cross-nodal correlation, making it challenging to assess the efficacy of a TGL algorithms on node feature forecasting task. To address this gap, we propose a synthetic dataset. generation technique in line with the design idea of mspace which is described Algorithm
Algorithm Synthetic Data Generation
Input g == (V,E), d, Piing Pmax, Quino o2 ounax Mo: ob, T, Pr; o2.
1: 6o ~ Bernoulli"d 3
Fy ~ 1o
for t [T] do
81-1 + 1s(E,_1)
if 8. S then
6:
S S (s
1(81-1)~ ~ Uniform" nd (Pmins (max)
7:
Σ Uniform ndxnd mmiu m
E } (-++
10:
I(s-11) + $ 3 ( laxd)
11: end
12: E ~
(s)-1))
13: = -t- +
14: end for
15: if 0 then
16: y1 ~ NN
W [r] VI E [T]
17: Ft < + Dt. mod
18: end if
22

---

Published in Transactions on Machine Learning Research (05/2025)
In steps 8-10, construct covariance matrix adhering to Assumption 2.2 and in step 12, sample the shock from multivariate normal distribution. In steps 16-17, random signal y is tiled with period and added to the node features to introduce seasonality into the dataset.
The synthetic datasets can be utilized to analyze how various factors such as graph structure, periodicity, connectivity, sample size, and other parameters affect error metrics.
We generate datasets through Algorithm by supplying the parameters outlined in Table 5 For each dataset, create multiple random instances and report the mean and standard deviation of the metrics in the results.
Table 5:
Parameters for different synthetic datasel packages.
Dalaset
G ~
d
T
Mmin
Mmax
Umin
mmax
d
P4
OT
SYNO1
6 ER (20, 0.2)
1
10
200
200
40
50
X 10a
5000
100
100
20
SYNO2
ØER (20, 0.2)
1
10
-20
200
40
50
2 x 10
5000
0
SYNO3
PR (40, 0.5)
10
-400
400
30
40
10*
2000
0
SYN04
PE (40, 0.5)
10
-400
400
30
40
10
2000
0
24000
28000
22000
20000
kwm
24000
18000
16000
20000
14000
12000
16000
10000
1000
(a) SYNO1
(b) SYNO2
50000
40000
10000
30000
5000
X
10000
5000
Wmh
200
400
600
800
1000
2000
4000
6000
8000
10000
(c) SYNO3
(d) SYN04
Figure 10: Exemplary synthetic dataset samples shown for nodes.
C.1 Periodicity
The generator parameters for SYNO1 and SYN02 are same except for the periodic component added to SYNO1 which has period of 100 timesteps consisting of shocks sampled from (100, 20). An algorithm which can exploit the periodic influence in the signal should perform better on SYNO1 compared SYNO2. The models which perform worse periodic dataset marked red.
23

---

Published in Transactions on Machine Learning Research (05/2025)
Table 6: Impact of data periodicity on RMSE achieved by different models. % increase
SYNO1
SYNO2
std. dev.
std. dev.
89101
87001
mapace-Sju
299.18
+ 6.55
294.99
8.81
-0.63
mapace-SN
400.99
+ 3.74
395.33
+ 3.24
-1.52
STGODE
420.86
+ 103.29
420.25
- 52.17
-9.87
GRAM-ODE
921.94
+ 537.63
853.77
- 340.45
-18.18
LightCTS
419.43
+ 176.5
334.59
+ 79.01
-30.6
Kalman-w
781.94
+ 32.35
776.75
+ 30.38
-0.88
Kalman-s
393.76
+ 4.72
390.45
+ 3.54
-1.13
C.2 Training Samples
The generator parameters for SYN03 and SYN04 same except for the total number of samples being times more in SYN04. If model perform better SYN04 compared to SYN03, it would indicate that it is training intensive, requiring more samples to infer the trends. On the other hand, if the model performs worse on SYN04, it would indicate that there are scalability issues, or the training caused overfitting. An ideal model is expected to have similar performance on SYNO3 and SYN04. The models with ideal behaviour are marked teal, and the models susceptible to overfitting are marked red. Moreover, model(s) that require more training samples are marked violet.
Table 7: Impact of number of training samples on RMSE achieved by different models.
SYNO3
SYN04
% increase
mean
std. dev.
mean
std. dev.
SYN04 SYNO3 SYN03
mspace-Spi
793.41
+ 5.86
789.36
+ 3
0.86
mspace-SW
793.93
+ 5.73
792.61
+ 2.02
-0.63
STCODE
830.63
+ 127
931.33
+ 191.87
+17.29
GRAM-ODE
1382.48
+ 80.78
1423.93
+ 190.13
+10.31
LightCTS
769.34
+ 196.6
998.01
+ 319.72
336.2
Kalman-w
785.7
+ 8.95
721.88
+ 1.73
-8.44
Kalman-E
782.6
+ 6.5
783.36
+ 1.45
-055
D Evaluation
D.1
Metrics
The root mean squared error (RMSE) of consecutive predictions for all the nodes is:
RMSE(q) & E V ndg Evev Eiew Eser E(ts(1) Elts(o)
(22)
The mean absolute error (MAE) of consccutive predictions for all the nodes is:
MAE(g)
LE E E EiEW) EsEro E(ts(u) (
(23)
ndg
D.2 Datasets
In Table 3 we list the datasets commonly utilised in the literature for single and multi-step node feature forecasting.
24

---

Published in Transactions on Machine Learning Research (05/2025)
tennis (Béres et al., 2018)
represents discrete-time dynamic graph showing the hourly changes in the interaction work among Twitter users during the 2017 Roland-Garros (RG17) tennis match. The input features capture the structural attributes of the vertices, with each vertex symbolizing a different user and the edges indicating retweets or mentions within an hour
wikimath (Rozemberczki et al., 2021a) tracks daily visits to Wikipedia pages related to popular mathematical topics over a two-year period. Static edges denote hyperlinks between the pages
pedalme (Rozemberczki et al., 2021a) reports weekly bicycle package deliveries by Pedal Me in London throughout 2020 and 2021. The nodes different locations, and the edge weight encodes the physical proximity. The count of woekly bicycle deliverics in a location forms the node feature footnote TO
cpox (Rozemberczki et al., 2021b) tracks the weekly number of chickenpox cases for each county of Hungary between 2005 and 2015. Different counties form the nodes, and are connected if any two counties share a border 10.
The four datases are collected from four districts in California using the California Transportation Agencies (CalTrans) Performance Measurement System (PcMS) and aggregated into 5-minutes windows The spatial adjacency matrix for each dataset is constructed using the length of the roads. PEMS03 is collected from September 2018 to November 2018. PEMS04 is collected from San Francisco Bay area from July 2016 to August 2016. PEMS07 is from Los Angeles and Ventura counties between May 2017 and August 2017. PEMSO8 collected from San Bernardino area between July 2016 to August 2016.
TEMM00304/077/ (Rao al.) 2022)
Variables: The flow represents the number of vehicles that pass through the loop detector per time interval (5 minutes). The occupancy variable represents the proportion of time during the time interval that the detector occupied by vehicle. It is measured as percentage. Lastly, the speed variable represents the average speed of the vehicles passing through the loop detector during the time interval It is measured in miles per hour (mph).
PEMSBAY (Li et al. 2018 is traffic dataset collected by CalTrans PeMS. It is represented by network of 325 traffic sensors in the Bay Area with 6 months of traffic readings ranging from January 2017 to May 2017 in 5 minute interval
METRLA (Li et al., 2018 is traffic dataset based Los Angeles Mctropolitan traffic conditions. The traffic readings are collected from 207 loop detectors highways in Los Angeles County over 5 minute intervals between March 2012 to June T012TT
D.3 Baselines
DCRNN (Li et al.) 2018) The Diffusion Convolutional Recurrent Neural Network (DCRNN) models the node features as a diffusion process on a directed graph, capturing spatial dependencies through bidirectional random walks. Additionally, it addresses nonlinear temporal dynamics by employing an encoder-decoder architecture with scheduled sampling.
TGCN (Zhao et al.) 2019) Temporal Graph Convolutional Network (TGCN) combincs the graph convolu- tional network (GCN) with a gated recurrent unit (GRU), where the former learns the spatial patterns, and the latter learns the temporal.
hitpps: htttps://githhb.com com, fetrennbbrre//nniieeeeettte
wikimath dataset from Py Porch Geometric I Temporal
hittps:/ http://ttthhhhm/////. htt.://////oocccttccmmmmeee///// http::/mmbmrccci.oooooooooopproo datascts
https://gttubb.oo/ /gggghuubbommmggugm/////// htw.g/osomm100/m13 wttp:///w....mm/////////AAAA /tree/ /man/ data
PEMSBAY dataset
Py Torch Geometric l'emporal
METRLA datasel. from Py Pyrorr Geometric Temporal
25

---

Published in Transactions on Machine Learning Research (05/2025)
Table 8: Real world datasets for single and multi-step forecasting.
Name
time-step
T
tennis
1,000
# tweets
hour
120
wikimath
1,068
# visits
1 day
731
pedalme
15
deliveries # cases
1 week
35
сpox
20
week 520
PEMS03
358
flow
5 min 26,208
PEMS04
307
flow, occupancy, speed
min 16,992
PEMSO7
883
flow
5 min 28,224
PEMSO8
flow, occupancy, speed
min 17,856
PEMSBAY
325
speed
5 min 52,116
METRLA
207
speed
5 min 34,272
EGCN (Pareja et al., 2020) EvolveGCN (EGCN) adapts GCN model without using node embeddings. The evolution of the GCN parameters is learnt through an RNN. EGCN has two variants: ECGN-H which uses GRU, and ECGN-O which uses an LSTM.
DynGESN (iihhlli Tortorella, 2022) Dynamic Graph Echo State Networks (DynGESN) employ echo state networks (ESNs) a special type RNN in which the recurrent weights are conditionally initialized, while a memory-less readout layer is trained. The ESN evolves through state transitions wheere the states belong to compact space. For more details please refer to the original text.
GWNet (Wu et al., 2019) GraphWave Net (GWNet) consists of an adaptive dependency matrix which is learnt through node embeddings, which is capable of capturing the hidden spatial relations in the data. GWNet can handle long sequences owing to its one-dimensional convolutional component whose receptive field grows exponentially with the number of layers.
Spatial-temporal Graph Ordinary Differential Equation (STGODE) employs tensor-based ordinary differential equations (ODEs) model the temporal evolution of the node fcatures.
STGODE (Fang et al., 2021)
GRAM-ODE (Liu al., 2023 Graph-based Multi-ODE (GRAM-ODE) improves upon STGODE by con- necting multiple ODE-GNN modules to capture different views of the local and global spatiotemporal dynamics.
FOGS (Rao et al. 2022 FOGS utilises first-order gradients to train predictive model because the traffic data distribution is irregular.
LightCTS stacks temporal and spatial operators computationaaly--ffiiien manner, and uses lightweight. modules I-TCN and GT.-Former.
CightCTS (Lai et al.; 2023
ARIMA is multivariate time series forecasting technique that combines autoregressive, integrated, and moving average components. It models the relationship between observations and their lagged values, adjusts for non-stationarity in the data, and accounts for short-term fluctuations.
ARIMA (Box & Pierce. 1970)
Kalman Welch 1997)
Since mspace is state-space amgorithm, we also use the Kalman filter baseline. We introduce two variants of the Kalman filter: Kalman-æ, which considers the node features as observations, and Kalman-s, which operates on the shocks.
26

---

Published in Transactions on Machine Learning Research (05/2025)
E
Interpretability
The poor performance of mspace-Tya on the datascts PEMSBAY and METRLA is explained through Fig. 11 notice that there are many datapoints away from the mean, although the mean trend passed through the dense collection data points, i.e,, the variance in the data is high which leads to higher error values reported in Table 3
We
70
60
50
40
30
20
20
10
10
500
750
1500 1750 2000
250
750 1000 1250 1500 2000 Emod To
tmod To
(a) PEMSBAY: Weekly
(b) METRLA: Weekly
Figure 11: Periodic trends in the traffic dataset PEMSBAY and METRLA; the black points represent the data- points, and the red line is the mean estimate for each state mod To-
F Runtime
In Table we present the average execution time of different models. It must be noted that mspace was not optimized for GPUs.
Table 9: Average execution time per time-step (logı0 scale).
TRAIN
TEST
CPU
tennis
wikimath
pedalme
cpox
tennis
wikinath
pedalme
cpox
DynGESN
-3.73
-2.93
-4.02
-4.28
-3.33
-2.40
-3.68
-3.83
ECGN-H
-0.79
-0.56
-1.34
-1.32
-2.66
-2.00
-2.55
-293
ECCN-D
-0.85
-0.60
-1.56
-1.57
-2.66
-2.62
-3.22
-3.24
TGON
-0.57
-0.12
-1.18
-1.17
-2.40
-2.50
-2.81
-2.82
mapace-Sjı
-2.27
-1.54
-3.53
-3.59
-1.49
-0.30
-3.25
-3.07
mspace-SA
-2.24
-1.53
-3.53
-3.61
-1.15
-0.21
-2.63
-2.72
LightCTS
1.18
1.18
-0.91
-1.15
-1.21
-1.32
-3.24
-3.70
STGODE
0.46
0.51
-0.55
-0.68
-2.06
-2.02
-2.85
-3.22
GRAMODE
1.25
1.26
-0.64
-0.90
-0.87
-0.82
-2.44
-2.86
GPU
tennis
ei eikimath
pedalme
cpox
tennis
wikimath
pedalme
cpox
DynGESN
-3.99
-3.66
-2.61
-3.65
-3.52
-3.50
-3.63
-3.65
ECGN-H
-0.79
-0.78
-1.00
-1.00
-2.36
-2.34
-2.60
-2.59
ECGN-O
-1.22
-1.21
-1.28
-1.30
-2.11
-2.90
-2.92
-2.92
TGCH
-0.88
-0.81
-0.94
-0.92
-2.53
-2.48
-2.54
-2.53
LightCTS
0.11
0.13
-0.95
-1.41
-2.44
-2.40
-3.32
-3,98
STCODE
-0.37
-0.36
-0.62
-0.91
-2.76
-2.85
-2.53
-3.25
GRAMODE
0.26
0.29
-0.71
-1.17
-1.81
-1.79
-2.32
-2.94
27


Reviews:
[{"review_id": "RFjP1HsOBt", "reviewer": "Reviewer_96mB", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Simple approach for forecasting time series over a graph. The mspace-S version of the model, in particular, uses a very simple state function that is just the sign of the of the shocks of neighboring nodes at potentially multiple hops.\n- The mspace algorithm is scalable and adaptive to changes in the data distribution and does not need to be re-trained to forecast at different time steps into the future.\n\nWeaknesses:\n- No discussion of vector autoregressive (VAR) models. The authors should be comparing their approach to recent research on network vector autoregressive (NAR) models, beginning with Zhu et al. (2017). These NAR models, and later variants including graph VARMA and graph GARCH models (Hong et al., 2023), are ideally suited to the proposed task.\n- Novelty is unclear. Is the approach of mapping the continuous-state Markov chain into finite states using $\\\\Psi$ and $\\\\Omega$ itself novel? Or just the choices of the state and sampling functions?\n- Discussion of interpretability is unclear. The authors try to explain the failure of their approach using normalized histograms of $tr(\\\\Sigma(s))$, but there are some gaps in the reasoning.\n\nReferences:\n- Xuening Zhu. Rui Pan. Guodong Li. Yuewen Liu. Hansheng Wang. \"Network vector autoregression.\" Ann. Statist. 45 (3) 1096 - 1123, June 2017. https://doi.org/10.1214/16-AOS1476\n- J. Hong, Y. Yan, E. E. Kuruoglu and W. K. Chan, \"Multivariate Time Series Forecasting With GARCH Models on Graphs,\" in IEEE Transactions on Signal and Information Processing over Networks, vol. 9, pp. 557-568, 2023, doi: 10.1109/TSIPN.2023.3304142.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors propose the mspace algorithm for forecasting multiple time series that are connected by a static unweighted graph. The authors formulate the problem by modeling the shock (difference in time series values over consecutive time steps) using a continuous-state Markov chain. Then, they approximate the Markov chain using a state function $\\\\Psi$ and a sampling function $\\\\Omega$ to map to and from a finite set of states. They use fixed length queues to collect most recent shocks following a given state. They demonstrate competitive forecasting error compared to temporal graph neural network (TGNN) models and classical algorithms such as Kalman filters. They also provide some evidence of the interpretability of their approach.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Major issues:\n- A discussion and comparison against recent research on multivariate time series forecasting with graph structure, such as NAR models. If the authors believe that these models are not relevant, then I would expect a clear discussion of why.\n- Line 103 to the end of Section 2 contains no references, so it appears as if this entire portion is the contribution of the authors. If this is the case, then it should be stated. If not, then the authors should indicate which portions are novel and which portions are not.\n- Figure 8 and corresponding discussion on interpretability: Why does $tr(\\\\Sigma(s))$ being left skewed explain the strong performance of mspace? The discussion on interpretability should make it clear what the interpretation is and why.\n\nMinor issues:\n- Code repository at https://anonymous.4open.science/r/mspace-TMLR is expired so I could not review it.\n- The offline training portion is described as optional in Section 6.4. If this is not done, then how do you compute the MLEs for $\\\\mu_v(s)$ and $\\\\Sigma_v(s)$? Aren't the queues then empty for every single state?", "broader_impact_concerns": "No statement is present, and I don't believe that one is needed.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "nyP2iJfm2u", "reviewer": "Reviewer_UPbb", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n- the paper proposes an approach for node regression with controlled computational complexity. \n\n- The formulation of the method is simple and based on probabilistic approached.\n\n- The analysis on the interpretability of the method is helpful.\n\n\n## Weakness\n\n- the claim is not clear. It is not straightforward neither from abstract nor introduction what is the claim of the paper is. It seems overall the paper has a bag of contributions but it is not justified how they uniformly contribute to a primary particular significant contribution that would impact a particular problem. For instance it is not clear if the claim is that the proposed work is to have a node regression model for temporal graphs which has improved time and space complexity or to tackle the limited training data scenario.\n\n- the clarity of the narrative and arguments is not satisfied:\n    - The paper structure needs further restructuring. The abstract does not follow a standard composition in which problem is defined. It is extremely difficult to understand the paper. In a standard format, the abstract should decompose into the following structure: Why is it relevant? why is it hard? Indicate the significance of our work? How does it solved? What is the contribution? How do we verify we solved it? Is it empirical? What is the experimental setup? Elaborate on the empirical evidence supporting we solve it; main table, ablation studies, analysis.\n\n    - It is not clear by looking at the abstract and introduction why the problem is and why it is important to solve the problem. It is very weakly motivated on the significance of the research and the necessity of the solution. For instance, the introduction begins with a paragraph that introduce the temporal graphs and then in the second paragraph sudden the contribution is given. \n\n    - It is strange the related work section is between the methodology and results.\n\n    - The related work is very unusually formatted. It has introductory content and notations presented. There are material contamination from the background and problem formulation in the related work.\n\n- the evidence provided in the experimental setup is not convincing that the proposed method is on par with the baselines as claimed in the abstract. For instance in table 3, there case several cases the results of the proposed method falls behind the top ones. So it stronger to say the results are mixed rather than on par. Therefore, the evidence is not convincing enough. In Fig. 5, it is also depicted.\n\n- It is not clear how the interpretability of this method is different from the baselines. The evidence to support it is missing. \n\n- the computation complexity of this paper is not compared with the baselines hence missing evidence.\n\n- The experimental setup seems very simple and the scale of the datasets seems falling behind to accurately support the claims of the paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The summary of the contributions of the paper is as follows:\n\nThe paper introduces mspace, an online algorithm for forecasting node features in discrete-time temporal graphs that captures both spatial cross-correlation and temporal auto-correlation. It supports both probabilistic and deterministic multi-step forecasting and outperforms several baselines, including Temporal Graph Neural Networks (TGNNs) and Kalman filters, especially in scenarios with limited training data. The algorithm’s forecasting error scales linearly with the number of forecast steps, and its computational complexity grows linearly with nodes and time steps, while maintaining constant space complexity. Comparative experiments on ten real-world datasets show mspace’s strong performance, and its interpretability is analyzed.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Based on the aforementioned strengths and weaknesses, the requested changes are provided as follows:\n\n- Restructuring the entire paper specially the sections such as abstract and conclusion to help improve the language of the paper for the audience to understand the contribution of the paper. The ordering of the sections is very difficult to follow and it heavily impact the clarity of narration.\n\n- The introduction does not motivate and highlight the problem. It is very hard to understand what and why this paper is contributing to.\n\n- There are unsupported statements either needs references or proves to justify (e.g. line 39-48).\n\n- The comparison with the baseline across various q values is insightful.\n\n- The comparison with the baselines to show empirically the interpretability and efficiency improvement of the work is needed.", "broader_impact_concerns": "There are no \"Broader Impact Concerns\" for this paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "EVmvOQMUUa", "reviewer": "Reviewer_yvAf", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Clearly written paper, well structured and goes into details required for reproducibility\n- Lightweight, computationally efficient, yet adaptive to trends and distribution changes\n- Provides theoretical results like computational complexity analysis and error bounds\n\nWeaknesses:\n- For $\\Psi_{S}$ statespace can grow exponentially large the bigger the neighborhood of the node is considered\n- Its unclear and not much explored why Kalman Filter applied on shocks is performing so poorly", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a graph node value forecasting approach dubbed **mspace**. The approach is modeling the shocks as a Markov process, which is approximated using state functions, which can capture spatial and/or temporal aspects. \n\nOne contribution is that due to the model learning Gaussian distributions it can make predictions in both deterministic and probabilistic modes, by either using mean of the distribution or sampling from it - thus being applicable in generative as well as discriminative settings.\n\nAlso, method is online and its computation grows linearly in number of nodes and in the number of timesteps. Error in terms of RMSE is also growing linearly in the number of steps.\n\nInterpretability is highlighted as another beneficial aspect of the approach, as predictions can be explained by inputs and model parameters.\n\nFinally, an empirical study was conducted on multiple datasets against multiple competing approaches and the quantitative results are suggesting that proposed approach is typically among the top few performing approaches.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "In the introduction it was claimed that TGNN models are trained to forecast predetermined number of steps, and for any other number of steps they would need to be reinitialized and retrained. However, any forecasting model can be be applied recursively (aka iterative multistep) on arbitrary number of steps - without the necessity of retraining.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This version of the manuscript is significantly improved compared to the previous submission. Nevertheless, some concerns regarding the organization of the results and exposition, and the contributions themselves remain. I am recommending the paper to be accepted in order to reduce processing delays, but strongly advise the authors to take into account the final rounds of comments of the reviewers in order to further strengthen the exposition.
Decision: Accept (poster)