Localised Adaptive Spatial-Temporal Graph Neural Network
Spatial-temporal graph models are prevailing for abstracting and modelling
spatial and temporal dependencies. In this work, we ask the following question:
whether and to what extent can we localise spatial-temporal graph models? We
limit our scope to adaptive spatial-temporal graph neural networks (ASTGNNs),
the state-of-the-art model architecture. Our approach to localisation involves
sparsifying the spatial graph adjacency matrices. To this end, we propose
Adaptive Graph Sparsification (AGS), a graph sparsification algorithm which
successfully enables the localisation of ASTGNNs to an extreme extent (fully
localisation). We apply AGS to two distinct ASTGNN architectures and nine
spatial-temporal datasets. Intriguingly, we observe that spatial graphs in
ASTGNNs can be sparsified by over 99.5\% without any decline in test accuracy.
Furthermore, even when ASTGNNs are fully localised, becoming graph-less and
purely temporal, we record no drop in accuracy for the majority of tested
datasets, with only minor accuracy deterioration observed in the remaining
datasets. However, when the partially or fully localised ASTGNNs are
reinitialised and retrained on the same data, there is a considerable and
consistent drop in accuracy. Based on these observations, we reckon that
\textit{(i)} in the tested data, the information provided by the spatial
dependencies is primarily included in the information provided by the temporal
dependencies and, thus, can be essentially ignored for inference; and
\textit{(ii)} although the spatial dependencies provide redundant information,
it is vital for the effective training of ASTGNNs and thus cannot be ignored
during training. Furthermore, the localisation of ASTGNNs holds the potential
to reduce the heavy computation overhead required on large-scale
spatial-temporal data and further enable the distributed deployment of ASTGNNs.
Wenying Duan, Xiaoxi He, Zimu Zhou, Lothar Thiele, Hong Rao
# Localised Adaptive Spatial-Temporal Graph Neural Network

###### Abstract.

Spatial-temporal graph models are prevailing for abstracting and modelling spatial and temporal dependencies. In this work, we ask the following question: _whether and to what extent can we localise spatial-temporal graph models?_ We limit our scope to adaptive spatial-temporal graph neural networks (ASTGNNs), the state-of-the-art model architecture. Our approach to localisation involves sparsifying the spatial graph adjacency matrices. To this end, we propose Adaptive Graph Sparsification (AGS), a graph sparsification algorithm which successfully enables the localisation of ASTGNNs to an extreme extent (fully localisation). We apply AGS to two distinct ASTGNN architectures and nine spatial-temporal datasets. Intriguingly, we observe that spatial graphs in ASTGNNs can be sparsified by over 99.5% without any decline in test accuracy. Furthermore, even when ASTGNNs are fully localised, becoming gapless and purely temporal, we record no drop in accuracy for the majority of tested datasets, with only minor accuracy deterioration observed in the remaining datasets. However, when the partially or fully localised ASTGNNs are reinitialised and retrained on the same data, there is a considerable and consistent drop in accuracy. Based on these observations, we reckon that _(i)_ in the tested data, the information provided by the spatial dependencies is primarily included in the information provided by the temporal dependencies and, thus, can be essentially ignored for inference; and _(ii)_ although the spatial dependencies provide redundant information, it is vital for the effective training of ASTGNNs and thus cannot be ignored during training. Furthermore, the localisation of ASTGNNs holds the potential to reduce the heavy computation overhead required on large-scale spatial-temporal data and further enable the distributed deployment of ASTGNNs.

graph sparsification, spatial-temporal graph neural network, spatial-temporal data +
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeX Templates

+
Footnote †: journal: Acment of LaTeTe Templates

+
Footnote †: journal: Acment of LaTeTe Templates

+
Footnote †: journal: Acment of LaTeTe Templates

+
Footnote †: journal: Acment of LaTeTe Templates

+
Footnote †: journal: Acment of LaTeTe Templates

+
Footnote †: journal: Acment of LaTeTe Templates

+
Footnote †: journal: Acment of LaTe Templates

+
Footnote †: journal: Acment of LaTe Templates

+
Footnote †: journal: Acment of LaTe Templates

+
Footnote †: journal: Acment of LaTe Templates

+
Footnote †: journal: Acment of LaTe Templates

+
Footnote †: journal: Acment of LaTe Templates

+
Footnote †: journal: Acment of LaTe Templates

+
Footnote †: journal: Acment of LaTe Templates

+
Footnote †: journal: Acment of LaTe Templates

+
Footnote †: journal: Acment of LaTe Templates

+
Footnote †: journal: Acment of LaTeTe Templates

+
Footnote †: journal: Acment of LaTe Templates

+
Footnote †: journal: Acment of LaTe Templates
the localisation of an ASTGNN refers to the sparsification of only the adjacency matrices capturing the spatial dependencies. It is crucial not to be confused with sparsifying other weight matrices, such as those used in the temporal modules, often seen in GNN sparsification with pre-defined graph architectures [5, 29, 16, 27]. An initial clue which indicates that the localisation of ASTGNNs could be feasible, probably even to an extreme extent, is shown in Figure. 1). Here we show the distribution of the elements in the spatial graph's adjacency matrix from an ASTGNN trained on the PeMSD8 dataset [4]. It is obvious that most edges in the spatial graph have weights close to zero.

We are interested in the localisation of spatial-temporal graph models for the following reasons:

* _A deeper understanding of the spatial and temporal dependencies in the data._ Although it is commonly accepted that both spatial and temporal dependencies are vital for inference, it is unclear whether and to what extent the information provided by these dependencies overlaps. If the localisation induces a marginal accuracy drop, then the information provided by the spatial dependencies is already largely included in the information contained in the temporal dependencies and, thus, unnecessary for inference.
* _Resoruce-efficient ASTGNN designs._ ASTGNNs are notoriously computation heavy as the size of the spatial graph grows quadratically with the number of vertices, thus limiting their usage on large-scale data and applications. The localisation of ASTGNNs may significantly reduce the resource requirement of these spatial-temporal graph models and enable new spatial-temporal applications.
* _Distributed deployment of spatial-temporal graph models._ In many cases, the data to construct the spatial-temporal graph models are collected via distributed sensing systems _e.g._, sensor networks. However, making predictions of each vertex using these models requires the history of other vertices, thereby involving data exchange between sensor nodes. Localisation of spatial-temporal graph models may enable individual sensor nodes to make predictions autonomously without communicating with each other, which saves bandwidth and protects privacy in a distributed system.

We explore the localisation of ASTGNNs via Adaptive Graph Sparsification (AGS), a novel algorithm dedicated to the sparsification of adjacency matrices in ASTGNNs. The core of AGS is a differentiable approximation of the \(L_{0}\)-regularization of a mask matrix, which allows the back-propagation to go past the regularizer and thus enables a progressive sparsification while training. We apply AGS to two representative ASTGNN architectures and nine different spatial-temporal datasets. The experiment results are surprising. _(i)_ The spatial adjacency matrices can be sparsified to over 99.5% without deterioration in test accuracy on all datasets. _(ii)_ Even fully localised ASTGNNs, which effectively degenerate to purely temporal models, can still provide decent test accuracy (no deterioration on most tested datasets while only minor accuracy drops on the rest). _(iii)_ When we reinitialise the weights of the localised ASTGNNs and retrain them on the spatial-temporal datasets, we cannot reinstate the same inference accuracy. Figure. 2 summarises our experiments and observations.

Our empirical study implies two hypotheses. _(i)_ In the tested spatial-temporal datasets, the information provided by the spatial dependencies is primarily included in the information provided by the temporal dependencies. Therefore, **the spatial dependencies can be safely ignored for inference** without a noteworthy loss of accuracy. _(ii)_ Although the information contained in the spatial and temporal dependencies overlaps, such overlapping provides the vital redundancy necessary for properly training a spatial-temporal graph model. Thus, **the spatial dependencies cannot be ignored during training**.

Our main contributions are summarised as follows:

* To the best of our knowledge, this is the first study on the localisation of spatial-temporal graph models. We surprisingly observed that spatial dependencies could be largely ignored during inference without losing accuracy. Extensive experiments on common spatial-temporal datasets and representative ASTGNN architectures demonstrated that only a few edges (less than 0.5% on all tested datasets) are required to maintain the inference accuracy. More surprisingly, when the spatial dependencies are completely ignored, _i.e._, the ASTGNNs are fully localised, they can still maintain a decent inference accuracy (no deterioration on most tested datasets, minor drops on the rest).
* With further investigations, we suggest the hypothesis that, although spatial dependencies can be primarily ignored during inference, they can drastically improve training effectiveness. This is supported by the observation that, if we reinitialise all parameters in the sparsified ASTGNNs and retrain them with the same data, the retrained networks yield considerably and consistently worse accuracy.
* To enable the localisation of ASTGNNs, we propose Adaptive Graph Sparsification (AGS), a novel graph sparsification algorithm dedicated to ASTGNNs. The core of AGS is a differentiable approximation of the \(L_{0}\)-regularization of a mask matrix, which allows the back-propagation to go past the regularizer and thus enables a progressive sparsification while training.

Figure 1. Histogram of edge weights of the spatial graph from an ASTGNN trained on the PeMSD8 dataset.
## 2. Related Work

Our work is relevant to the following threads of research.

### Spatial-Temporal Graph Neural Networks

Spatial-temporal graph neural networks (STGNNs) play an essential role in spatial-temporal data analysis for their ability to learn hidden patterns of spatial irregular signals varying across time (Sutskever et al., 2017). These models often combine graph convolutional networks and recurrent neural networks. For example, Graph Convolutional Recurrent Network (GCRN) (Krizhevsky et al., 2014) combines an LSTM with ChebNet. Diffusion Convolutional Recurrent Neural Network (Krizhevsky et al., 2014) incorporates a proposed diffusion graph convolutional layer into GRU in an encoder-decoder manner to make multi-step predictions. Alternatively, CNN-based models can represent the temporal relations in spatial-temporal data in a non-recursive manner. For instance, GCCN (Ghezani et al., 2017) combines 1D convolutional layers with GCN layers. STG (Ghezani et al., 2017) composes a spatial-temporal model for skeleton-based action recognition using a 1D convolutional layer and a Partition Graph Convolution (PGC) layer. More recent proposals such as ASTGCN (Krizhevsky et al., 2014), STG2Seq (Bengio et al., 2015), and LSGCN (Krizhevsky et al., 2014) further employ attention mechanisms to model dynamic spatial dependencies and temporal dependencies. In addition, some researchers consider the out-of-distribution generalisation of STGNN, and propose a domain generalisation framework based on hypernetworks to solve this problem(Krizhevsky et al., 2014). However, these models adopt a predefined graph structure, which may not reflect the complete spatial dependency.

To capture the dynamics in graph structures of spatial-temporal data, an emerging trend is to utilize adaptive spatial-temporal graph neural networks (ASTGNNs). Graph WaveNet (Ghezani et al., 2017) proposes an AGCN layer to learn a normalized adaptive adjacency matrix without a pre-defined graph. ASTGAT introduces a network generator model that generates an adaptive discrete graph with the Gumbel-Softmax technique(Ghezani et al., 2017). The network generator can adaptively infer the hidden correlations from data. AGCRN (Bengio et al., 2015) designs a Node Adaptive Parameter Learning enhanced AGCN (NAPL-AGCN) to learn node-specific patterns. Due to its start-of-the-art performance, NAPL-AGCN has been integrated into various recent models such as Z-GCNETs (Chen et al., 2017), STG-NCDE (Chen et al., 2017), and TAMP-S2GCNets (Chen et al., 2017).

Despite the superior performance of ASTGNNs, they incur tremendous computation overhead, mainly because _(i)_ learning an adaptive adjacency matrix involves calculating the edge weight between each pair of nodes, and _(ii)_ the aggregation phase is computationally intensive. We aim at efficient ASTGNN inference, particularly for large graphs.

### Graph Sparsification for GNNs

With graphs rapidly growing, the training and inference cost of GNNs has become increasingly expensive. The prohibitive cost has motivated growing interest in graph sparsification. The purpose of graph sparsification is to extract a small sub-graph from the original large one. SGCN (Ghezani et al., 2017) is the first to investigate graph sparsification for GNNs, _i.e._, pruning input graph edges, and learned an extra DNN surrogate. NeuralSparse (Srivastava et al., 2015) prunes task-irrelevant edges from downstream supervision signals to learn robust graph representation. More recent works such as UGS (Chen et al., 2017) and GBET (Ghezani et al., 2017) explore graph sparsification from the perspective of the winning tickets hypothesis.

The aforementioned works only explore graph sparsification for vanilla GNNs and non-temporal data with pre-defined graphs. Our work differs by focusing on _spatial-temporal_ GNNs with _adaptive_ graph architectures.

## 3. Preliminaries

This section provides a quick review of the representative architectures of ASTGNNs.

Figure 2. An overview of our experiments and observations. We train ASTGNNs on spatial-temporal datasets, achieving baseline accuracies. Then we localise the ASTGNNs with the proposed algorithm AGS, achieving accuracies comparable to the dense graph baselines. Finally, we reinitialise the localised ASTGNNs and retrain them on the same datasets, resulting in considerably and consistently deteriorated accuracies.
### Spatial-Temporal Data as Graph Structure

Following the conventions in spatial-temporal graph neural network research (Beng et al., 2017; Chen et al., 2017; Chen et al., 2018; Chen et al., 2019; Chen et al., 2019; Chen et al., 2019; Chen et al., 2019; Chen et al., 2019; Chen et al., 2019; Chen et al., 2019; Chen et al., 2019), we represent the spatial-temporal data as a sequence of discrete frames \(\mathcal{X}\) with \(\mathcal{G}=\{\mathcal{V},\mathcal{E}\}\), where \(\mathcal{X}=\{\mathbf{X}_{1},\mathbf{X}_{2},\ldots,\mathbf{X}_{T}\}\). The graph \(\mathcal{G}\) is also known as the spatial network, which consists of a set of nodes \(\mathcal{V}\) and a set of edges \(\mathcal{E}\). Let \(|\mathcal{V}|=N\). Then the edges are presented with an adjacency matrix \(A_{t}\in\mathbb{R}^{N\times N}\), where \(\mathbf{X}_{t}\in\mathbb{R}^{N\times C}\) is the node feature matrix with dimension \(C\) at timestep \(t\), for \(t=1,\ldots,T\).

Given graphs \(\mathcal{G}\) and \(\mathcal{T}\) historical observations \(\mathcal{X}^{T}\)=\(\{\mathbf{X}_{t-\mathcal{T}},\ldots,\mathbf{X}_{t-1}\}\in\mathbb{R}^{T\times N\times C}\), we aim to learn a function \(\mathcal{F}\) which maps the historical observations into the future observations in the next \(\mathcal{H}\) timesteps:

\[\left\{\mathbf{X}_{t},\ldots,\mathbf{X}_{t+\mathcal{H}}\right\}=\mathcal{F}(\mathbf{X}_{ t-\mathcal{T}},\ldots,\mathbf{X}_{t-1};\theta,\mathcal{G}) \tag{1}\]

where \(\theta\) denotes all the learnable parameters.

### Modeling the Spatial Network \(\mathcal{G}\)

Since we focus on the role of spatial dependencies, we explain the state-of-the-art modelling of the spatial network in spatial-temporal graph neural networks (STGNNs).

The basic method to model the spatial network \(\mathcal{G}\) at timestep \(t\) with its node feature matrix \(\mathbf{X}_{t}\) in representative STGNNs (Beng et al., 2017; Chen et al., 2019; Chen et al., 2019) is Graph Convolution Networks (GCNs). A one-layer GCN can be defined as:

\[Z_{t}=\sigma\left(\tilde{D}^{-\frac{1}{2}}\tilde{A}_{t}\tilde{D}^{-\frac{1}{2 }}\mathbf{X}_{t}W\right) \tag{2}\]

where \(\tilde{A}=A+I_{N}\) is the adjacency matrix of the graph with added self-connections. \(I_{N}\) is the identity matrix. \(\tilde{D}\) is the degree matrix. \(W\in\mathbb{R}^{C\times F}\) is a trainable parameter matrix. \(\sigma(\cdot)\) is the activation function. \(Z_{t}\in\mathbb{R}^{N\times F}\) is the output. All information regarding the input \(\mathbf{X}_{t}\) at timestep \(t\) is aggregated in \(Z_{t}\).

A key improvement to model the spatial network is to adopt Adaptive Graph Convolution Networks (AGCNs) to capture the dynamics in the graph \(\mathcal{G}\), which leads to the adaptive spatial-temporal graph neural networks (ASTGNNs) (Chen et al., 2017; Chen et al., 2018; Chen et al., 2019; Chen et al., 2019; Chen et al., 2019). In the following, we briefly explain Adaptive Graph Convolutional Recurrent Network (AGCRN) (Chen et al., 2019) and the extension with transformers, denoted as AGFormer, two representative ASTGNN models.

* **AGCRN.** It enhances the GCN layer by combining the normalized self-adaptive adjacency matrix with a Node Adaptive Parameter Learning (NAPL), which is known as NAPL-AGCN. \[\mathbf{\Lambda}_{adp}=SoftMax\left(ReLU\left(\mathbf{E}\mathbf{E}^{T}\right)\right)\] (3) \[Z_{t}=\sigma\left(\mathbf{\Lambda}_{adp}\mathbf{X}_{t}\mathbf{E}W_{ \mathbf{\beta}}\right)\]

where \(W_{\mathbf{\beta}}\in\mathbb{R}^{d\times C\times F}\) and \(\mathbf{E}W_{\mathbf{\beta}}\in\mathbb{R}^{N\times C\times F}\). \(\mathbf{\Lambda}_{adp}\in\mathbb{R}^{N\times N}\) is the normalized self-adaptive adjacency matrix (Chen et al., 2019). \(d\) is the embedding dimension for \(d\ll N\). Each row of \(\mathbf{E}\) presents the embedding of the node. During training, \(\mathbf{E}\) is updated to learn the spatial dependencies among all nodes. Instead of directly learning \(W\) in (2) shared by all nodes, NAPL-AGCN uses \(EW_{\mathbf{\beta}}\) to learn node-specific parameters. From the view of one node (_e.g._, node \(i\)), \(\mathbf{E}_{i}W_{\mathbf{\beta}}\) are the corresponding node-specific parameters according to its node embedding \(\mathbf{E}_{i}\). Finally, to capture both spatial and temporal dependencies, AGCRN integrates NAPL-AGCN and Gated Recurrent Units (GRU) by replacing the MLP layers in GRU with NAPL-AGCN.
* **AGFormer.** It extends AGCRN by modelling the temporal dependencies with transformers (Kipf and Welling, 2017; Chen et al., 2019). A Transformer is a stack of transformer blocks. One block contains a multi-head self-attention mechanism and a fully connected feedforward network. We replace the MLP layers in the multi-head self-attention mechanism with NAPL-AGCN to construct a transformer-based ASTGNN model, which we call AGFormer.

Modelling the spatial network with NAPL-AGCN achieves state-of-the-art performances on multiple benchmarks, and it has been widely adopted in diverse ASTGNN variants (Chen et al., 2017; Chen et al., 2018; Chen et al., 2019; Chen et al., 2019). However, NAPL-AGCN is much more inefficient than GCNs, since \(\mathbf{\Lambda}_{adp}\) is a matrix without zeros, while the adjacency matrix of a pre-defined graph in GCNs is far more sparse than \(\mathbf{\Lambda}_{adp}\). This motivates us to explore the localisation of spatial-temporal graph models taking ASTGNNs as examples.

## 4. Adaptive Graph Sparsification

This section presents Adaptive Graph Sparsification (AGS), a new algorithm dedicated to the sparsification of adjacency matrices in ASTGNNs.

**Formulation.** The NAPL-AGCN-based ASTGNNs with normalized self-adaptive adjacency matrix \(\mathbf{\Lambda}_{adp}\) can be trained using the following objective:

\[\mathcal{L}(\theta,\mathbf{\Lambda}_{adp})=\frac{\sum_{r\in\mathcal{T}}\sum_{ \mathbf{\nu}\in\mathcal{V}}\left\|\mathbf{y}^{(r,\mathbf{\nu})}-\mathbf{\hat{y}}^{(r,\mathbf{ \nu})}\right\|_{1}}{|\mathcal{V}|\times|\Gamma|} \tag{4}\]

where \(\Gamma\) is a training set, \(\tau\) is a train sample, and \(\mathbf{y}^{(r,\mathbf{\nu})}\) is the ground-truth of node \(\mathbf{\nu}\) in \(\tau\).

Given a pre-trained model \(\mathcal{F}(\cdot;\theta,\mathbf{\Lambda}_{adp})\), we introduce a mask \(\mathbf{\mathbf{M}}_{\mathbf{\Lambda}}\) to prune the adjacency matrix \(\mathbf{\Lambda}_{adp}\). The shape of \(\mathbf{\mathbf{M}}_{\mathbf{\Lambda}}\) is identical to \(\mathbf{\Lambda}_{adp}\). Specifically, given \(\mathcal{F}(\cdot;\theta,\mathbf{\Lambda}_{adp})\), we obtain \(\mathbf{\mathbf{M}}_{\mathbf{\Lambda}}\) by optimizing the following objective:

\[\mathcal{L}_{AGS}=\mathcal{L}(\theta,\mathbf{\Lambda}_{adp}\odot\mathbf{ \mathbf{M}}_{\mathbf{\Lambda}})+\lambda\left\|\mathbf{\mathbf{M}}_{\mathbf{\Lambda}}\right\|_{ 0},\] \[\left\|\mathbf{\mathbf{M}}_{\mathbf{\Lambda}}\right\|_{0}=\sum_{i=1}^{N}\sum_ {j=1}^{N}m_{(i,j)},m_{(i,j)}\in\{0,1\} \tag{5}\]

where \(\odot\) is the element-wise product, \(m_{(i,j)}\) corresponds to binary "gate" that indicates whether an edge is pruned, and \(\lambda\) is a weighting factor for \(L_{0}\)-regularization of \(\mathbf{\mathbf{M}}_{\mathbf{\Lambda}}\).

**Sparsification Algorithm.** An intuitive way to get \(\mathbf{\mathbf{M}}_{\mathbf{\Lambda}}\) is to initialize a trainable weight matrix \(\mathbf{\mathbf{U}}\in\mathbb{R}^{N\times N}\) and map the entry \(u_{(i,j)}\in\mathbf{\mathbf{U}}\) into binary "gates" using a Bernoulli distribution: \(m_{(i,j)}=\mathcal{B}\left(u_{(i,j)}\right)\), where \(\mathcal{B}\) is a Bernoulli distribution. However, directly introducing \(\mathbf{\mathbf{U}}\) to model \(\mathcal{F}(\cdot;\theta,\mathbf{\Lambda}_{adp})\) has two problems.

* It may be unscalable for large-scale graphs.
* The \(L_{0}\) sparsity penalty is non-differentiable.

For the scalability issue, we adopt a node adaptive weight learning technique to reduce the computation cost by simply generating \(\mathbf{\mathbf{U}}\) with the node embedding \(\mathbf{\mathbf{E}}\):

\[\mathbf{\mathbf{U}}=\mathbf{\mathbf{E}}W_{\mathbf{\mathbf{E}}} \tag{6}\]
where \(W_{\mathbf{E}}\in\mathbb{R}^{d\times N}\) is a trainable matrix.

For the non-differentiable issue, we introduce the hard concrete distribution instead of the Bernoulli distribution (Berridge et al., 2016), which is a contiguous relaxation of a discrete distribution and can approximate binary values.

Accordingly, the computation of binary "gates" \(m_{(i,j)}\) can be formulated as:

\[\begin{split}& z\sim\mathcal{U}(0,1),s_{(i,j)}=Sig\left(\log z- \log(1-z)+\log\left(u_{(i,j)}\right)\right)/\beta\\ &\tilde{s}_{(i,j)}=s_{(i,j)}(\zeta-\gamma)+\gamma,m_{(i,j)}=\min \left(1,\max\left(0,\tilde{s}_{(i,j)}\right)\right)\end{split} \tag{7}\]

where \(z\) is a uniform distribution, \(Sig\) is a sigmoid function, \(\beta\) is a temperature value and \((\zeta-\gamma)\) is the interval with \(\zeta<0\) and \(\gamma>1\). We set \(\zeta=-0.1\) and \(\gamma=1.1\) in practice. Then, \(\mathbf{M}_{\mathbf{A}}\) is applied to prune the lowest-magnitude entries in \(\mathbf{A}_{adp}\), _w.r.t._ pre-defined ratios \(p_{g}\).

Alg. 1 outlines the procedure of AGS. The pruning begins after the network is pre-trained (Line 5). First, we sort edges in the adjacency matrix by magnitude in ascending order (Line 6). Then we perform pruning iteratively (Line 7). The top \(p_{g}\) of the edges are removed, and the rest are retained. We identify the remaining edge by setting its corresponding entry in \(\mathbf{M}_{\mathbf{A}}\) to \(1\) in each iteration (Line 8). The edges to be pruned are removed using Eq.(5) (Line 9).

```
1:\(\mathcal{X}\): input data, \(\mathcal{F}\left(\cdot;\theta,\mathbf{A}_{adp}\right)\): Spatial-temporal GNN with initialization self-adaptive adjacency matrix \(\mathbf{A}_{adp}\), \(\mathbf{N}_{1}\): number of pre-training iterations, \(\mathbf{N}_{2}\): number of sparsification iterations, \(s_{g}\): pre-defined sparsity level for graph.
2:\(\mathcal{F}\left(\cdot;\theta,\mathbf{A}_{adp}\odot\mathbf{M}_{\mathbf{A}}\right)\)
3:while iteration \(i<\mathbf{N}_{1}\)do
4: Forward to compute the loss in Eq.(4).
5: Back-propagate to update \(\theta\) and \(\mathbf{A}_{adp}\).
6:endwhile
7:Obtain pre-trained \(\mathcal{F}\left(\cdot;\theta,\mathbf{A}_{adp}\right)\).
8:Sort entries in \(\mathbf{A}_{adp}\) by magnitude in an ascending order then obtain list \(K=\left\{k_{i}\right\}_{i=1}^{N\times N}\).
9:while iteration \(i<\mathbf{N}_{2}\) and \(1-\frac{\left\|\mathbf{M}_{\mathbf{A}}\right\|_{0}}{\left\|\mathbf{A}_{adp} \right\|_{0}}<s_{g}\)do
10: set \(\mathbf{M}_{\mathbf{A}}^{(i,j)}=1\) if \(\mathbf{A}_{adp}^{(i,j)}\notin K_{N^{2}s_{g}}\).
11: Forward to compute the loss in Eq.(5).
12: Back-propagate to update \(\theta\) and \(\mathbf{A}_{adp}\odot\mathbf{M}_{\mathbf{A}}\).
13:endwhile
```

**Algorithm 1**Adaptive Graph Sparsification (AGS)

**Discussions.** We make two notes on our AGS algorithm.

* AGS differs from prior magnitude-based pruning methods designed for graphs (Zhu et al., 2017; Wang et al., 2018) in that (_i_) it sparsifies _adaptive graphs_ in spatial-temporal GNNs rather than vanilla GNNs and non-temporal data with pre-defined graphs; and (_ii_) it does not require iterative retraining on the pruned graphs to restore model accuracy.
* Pruning the adjacency matrix with AGS notably reduces the complexity of ASTGNNs for inference. The inference time complexity of unpruned NAPL-AGCN layers is \(\mathcal{O}(N^{2}d+\mathit{LNT}\mathcal{F}^{2}+\mathit{L7}\left\|A_{adp} \right\|_{0}F+\mathit{NdF})\). After sparsification, the inference time complexity of NAPL-AGCN layers is \(\mathcal{O}(N^{2}d+\mathit{LNT}\mathcal{F}^{2}+\mathit{L7}\left\|A_{adp} \odot\mathbf{M}_{\mathbf{A}}\right\|_{0}F+\mathit{NdF})\), where \(N^{2}d\) is the time complexity of computing adaptive adjacency matrix, \(d\) is the embedding dimension,\(N\) is the number of nodes, \(\left\|A_{adp}\odot M_{\mathbf{A}}\right\|_{0}\) is the number of remaining edges, \(F\) is the representation dimension of node features, \(\mathcal{T}\) is the length of input, \(L\) is the number of layers.

## 5. Experiments

To answer the question of whether and to what extent we can localise a spatial-temporal graph model, we conducted extensive experiments explained in this section.

### Neural Network Architecture

We evaluate the performance of AGS over two representative NAPL-AGCN-based ASTGNN architectures: **AGCRN**(Chen et al., 2017) and its extension **AGFormer**. AGCRN is a state-of-the-art ASTGNN architecture combining AGCN and RNN layers. AGCN layers are used to capture the spatial dependencies, while RNN layers are there to model the temporal dependencies. AGFormer, on the other hand, can be regarded as an alternative version of the AGCRN, in which the RNN layers are substituted by Transformer layers. We intentionally chose these two ASTGNN architectures sharing the same spatial module but using different temporal modules, to show that both the effectiveness of AGS and our observations on the learned spatial dependencies are orthogonal to the temporal modules involved.

### Datasets and Configurations

The localisation of ASTGNNs is evaluated on nine real-world spatial-temporal datasets from three application domains: transportation, blockchain and biosurveillance. Table 1 summarizes the specifications of the datasets used in our experiments. The detailed datasets and configurations are provided in Appendix A.1. The details on tuning hyperparameters are provided in Appendix A.2.

### Main Experimental Results

Our major experiments are illustrated in Figure. 2. We first train AGCRNs and AGFormers on the nine spatial-temporal datasets,

\begin{table}
\begin{tabular}{l c c} \hline \hline Datasets & \#Nodes & Range \\ \hline PeMSD3 & 358 & 09/01/2018 - 30/11/2018 \\ PeMSD4 & 307 & 01/01/2018 - 28/02/2018 \\ PeMSD7 & 883 & 01/07/2017 - 31/08/2017 \\ PeMSD8 & 170 & 01/07/2016 - 31/08/2016 \\ \hline Bytom & 100 & 27/07/2017 - 07/05/2018 \\ Decentral & 100 & 14/10/2017 - 07/05/2018 \\ Golem & 100 & 18/02/2017 - 07/05/2018 \\ \hline CA & 55 & 01/02/2020 - 31/12/2020 \\ TX & 251 & 01/02/2020 - 31/12/2020 \\ \hline \hline \end{tabular}
\end{table}
Table 1. Summary of datasets used in experiments.
achieving baseline accuracies. Then we conduct localisation of these well-trained AGCRNs and AGFormers using AGS. Finally, we reinitialise all weights in the localised AGCRNs and retrain them on the original datasets with the same training settings.

The experiment results are organised as follows:

* The test accuracies of the non-localised AGCRNs and AGFormers and those with localisation degrees until 99% are collected in Figure. 3 (on transportation datasets), Figure. 4 (on biosurveillance datasets) and Figure. 5 (blockchain datasets). These figures contain the test accuracies at graph sparsity of 0%, 30%, 50%, 80% and 99%.
* The test accuracies of AGCRNs with localisation degrees between 99.1% and 100% are illustrated in Figure. 6, shown in dotted green curves.
* The test accuracies of localised AGCRNs that are reinitialised and retrained are also collected in Figure. 6, shown in solid purple curves.

Error bars in these figures show the standard deviation of five runs. We made the following observations from these results:

* **The localisation of AGCRNs and AGFormers is possible.** Applying AGS on AGCRNs and AGFormers and localising them to a localisation degree of 99% incurs no performance degradation across all datasets. On the contrary, in many experiments, the test accuracy keeps improving until 99%-localisation. Further localisation of AGCRNs up to 99.5% still induces no accuracy drop against the non-localised baselines.
* **Full localisation of AGCRNs is still practical.** Even when we fully localise the AGCRNs, which in effect turn them into independent RNNs ignoring all spatial dependencies, they can still provide decent test accuracies. As shown in Figure. 6, on transportation datasets (PeMSD3, PeMSD4, PeMSD7 and PeMSD8), only minor drops are observed. On blockchain datasets (Bytom, Decentraland and Golem) and biosurveillance datasets (CA&TX), we can observe that the test accuracy is no worse at 100% sparsity compared with the non-localised baselines.
* **Localised AGCRNs cannot be relearned without the dense spatial graphs.** As shown in Figure. 6, when we reinitialise the partially or fully localised AGCRNs and then

Figure 3. Test accuracies of original and localised (up to 99%) AGCRNs and AGFormers, tested on transportation datasets (PeMSD3, PeMSD4, PeMSD7 and PeMSD8). Horizontal dash lines represent the baselines of non-localised AGCRNs and AGFormers.
retrain them on the nine datasets, we can observe a consistent and considerable drop in inference accuracy.

Upon these observations, we suggest the following hypotheses:

* In many spatial-temporal datasets, the information provided by the spatial dependencies is primarily included in the information provided by the temporal dependencies. Therefore, the spatial dependencies can be safely ignored for inference without a noteworthy loss of accuracy.
* Although the information contained in the spatial and temporal dependencies overlaps, such overlapping provides the vital redundancy necessary for properly training a spatial-temporal graph model. Thus, the spatial dependencies cannot be ignored during training.

## 6. Ablation Studies

### Impact on Resource Efficiency

As mentioned in Sec. 1, one of the reasons that we are particularly interested in the localisation of ASTGNNs is its resource efficiency. Non-localised ASTGNNs usually learn spatial graphs that are complete. Therefore, the number of edges and consequently the computation overhead grows quadratically with the number of vertices. Localisation of ASTGNNs is equivalent to pruning edges in the learned spatial graph, which could dramatically reduce the computation overhead associated with the spatial dependencies and thus improve resource efficiency. To this end, we calculated the amount of computation during inference of 99%-localised AGCRNs and AGFormers, measured in FLOPs, and summarised the results in Table 2. We can see that the localisation of AGCRNs and AGFormers effectively reduces the amount of computation required for inference. The acceleration is more prominent on AGCRNs against AGFormers because a larger portion of the total computation required by AGFormers is used on their temporal module (transformer layers), whereas AGCRNs use much lighter temporal modules (RNN layers).

### Localised AGCRNs vs. Other Non-Localised ASTGNNs

In Figure. 3, Figure. 4 and Figure. 5, we can clearly see that the localisation up to 99% is able to improve the test accuracy slightly. For example, 99%-localised AGCRNs outperform non-localised AGCRNs by decreasing the RMSE/MAE/MAPE by 3.6%/3.7%/2.0% on PeMSD3. Such improvement is consistently observed across both AGCRNs and AGFormers and all tested datasets. We reckon that this improvement is caused by the regularisation effect of sparsifying the spatial graph, which may suggest that the non-localised AGCRNs and AGFormers all suffer from overfitting to a certain degree.

Recent works on ASTGNNs proposed improved architectures of AGCRN, including Z-GCNETs (Zhou et al., 2017), STG-NCDE (Chen et al., 2018), and TAMP-S2GCNets (Chen et al., 2018) for different applications. We are therefore curious about how our localised AGCRNs compare to these variations. Hence we compare the test accuracy of 99%-localised AGCRNs with these architectures. Results are shown in Table 3, Table 4 and Table 5. We can see that our localised AGCRNs can generally provide competitive inference performance even against those delivered by state-of-the-art architectures. This observation also agrees with our first hypothesis mentioned in Sec. 5.3: in many spatial-temporal datasets, the information provided by the spatial dependencies are primarily included in the information provided by the temporal dependencies. Therefore, different spatial modules, given that the temporal modules are properly trained, may not make a significant difference in inference performance.

### Localisation of Non-temporal Graphs

To further investigate spatial dependencies and indirectly test our hypotheses, we conduct additional experiments and extend AGS to non-temporal graphs. We attempt to sparsify the spatial graph pre-given by non-temporal datasets, including Cora, CiteSeer, and Pubmed (Pubmed, 2018). On these datasets, we train two non-temporal graph neural network architectures, GCN(Wang et al., 2019) and GAT(Wang et al., 2019). On GCN and GAT, as they don't own node embeddings E, we can use the representation H learned by pre-trained GCN and GAT to replace E in (6), then prune the edges as in Alg. 1, where the weighting factor \(\lambda\) takes control of graph sparsity.

Table 6 shows the accuracy of localised GCN and GAT non-temporal datasets. The pre-defined graphs of Cora, CiteSeer, and PubMed are sparsified to 30%, 50%, 80% and 100%, respectively. We can observe a significant drop in the test accuracy among all

Figure 4. Test accuracies of original and localised (up to 99%) AGCRNs and AGFormers, tested on biosurveillance datasets (CA and TX). Horizontal dash lines represent the baselines of non-localised AGCRNs and AGFormers.
localised non-temporal graph models. This indicates that, in the absence of temporal dependencies, the information provided by spatial dependencies plays a major role during inference and thus can not be ignored via localisation.

Figure 5. Test accuracies of original and localised (up to 99%) AGCRNs and AGFormers, tested on blockchain datasets (Bytom, Decentraland and Golem). Horizontal dash lines represent the baselines of non-localised AGCRNs and AGFormers.

Figure 6. Test accuracies of localised (99.1% to 100%) AGCRNs and their reinitialised&retrained counterparts, tested on all datasets. Horizontal dash lines represent the baselines of non-localised AGCRNs.
## 7. Conclusion

In this paper, we ask the following question: whether and to what extent can we localise spatial-temporal graph models? To facilitate our investigation, we propose AGS, a novel algorithm dedicated to the sparsification of adjacency matrices in ASTGNNs. We use AGS to localise two ASTGNN architectures: AGCRN and AGFormer, and conduct extensive experiments on nine different spatial-temporal datasets. Primary experiment results showed that The spatial adjacency matrices could be sparsified to over 99.5% without deterioration in test accuracy on all datasets. Furthermore, when the ASTGNNs are fully localised, we still observe no accuracy drop on the majority of the tested datasets, while only minor accuracy deterioration happened on the rest datasets. Based on these observations, we suggest two hypotheses regarding spatial and temporal dependencies: _(i)_ in the tested data, the information provided by the spatial dependencies is primarily included in the information provided by the temporal dependencies and, thus, can be essentially ignored for inference; and _(ii)_ although the spatial dependencies provide redundant information, it is vital for effective training of ASTGNNs and thus cannot be ignored during training. Last but not least, we conduct additional ablation studies to show the practical impact of ASTGNN's localisation on resource efficiency and to verify our hypotheses from different angles further.

## 8. Acknowledgement

The authors are grateful to the KDD anonymous reviewers for many insightful suggestions and engaging discussion which improved the quality of the manuscript.

\begin{table}
\begin{tabular}{l|c c c c c} \hline \hline \multirow{2}{*}{Sparsity(\%)} & Cora & \multicolumn{2}{c}{Citeseer} & \multicolumn{2}{c}{PubMed} \\ \cline{2-7}  & GCN & GAT & GCN & GAT & GCN & GAT \\ \hline
0\% & 80.20 & 82.10 & 69.40 & 72.52 & 78.90 & 79.00 \\
30\% & 80.35 & 83.17 & 69.23 & 72.31 & 79.14 & 79.23 \\
50\% & 72.73 & 75.40 & 69.37 & 72.70 & 78.82 & 79.31 \\
80\% & 65.19 & 70.81 & 58.47 & 63.18 & 68.37 & 77.03 \\
100\% & 56.22 & 63.29 & 53.13 & 57.50 & 61.02 & 64.25 \\ \hline \hline \end{tabular}
\end{table}
Table 6. Classification accuracy (%) of localised GCN and GAT on citation graph datasets.

\begin{table}
\begin{tabular}{l c c c c c c c c c c c c} \hline \hline \multirow{2}{*}{Methods} & Datasets & PenMSD3 & \multicolumn{3}{c}{PenMSD4} & \multicolumn{3}{c}{PenMSD7} & \multicolumn{3}{c}{PenMSD8} & \multicolumn{3}{c}{Average} \\ \cline{2-13}  & Metrics & MAE & RMSE & MAPE & MAE & RMSE & MAPE & MAE & RMSE & MAPE & MAE & RMSE & MAPE \\ \hline AGCRN & 15.98 & 28.25 & 15.23\% & 19.83 & 32.30 & 12.97\% & 22.37 & 36.55 & 9.12\% & 15.95 & 25.22 & 10.09\% & 18.53 & 30.58 & 11.85\% \\ Z-GCNETS & 16.64 & 28.15 & 16.39\% & 19.50 & 31.61 & 12.78\% & 21.77 & 35.17 & 9.25\% & 15.76 & 25.11 & 10.01\% & 18.42 & 30.01 & 12.11\% \\ STG-NCDE & 15.57 & **27.09** & 15.06\% & **19.21** & **31.09** & 12.76\% & **20.53** & **33.84** & 8.80\% & **15.45** & 24.81 & 9.92\% & **17.69** & **29.21** & 11.64\% \\ TAMP-S2GCNets & 16.03 & 28.28 & 15.37\% & 19.58 & 31.64 & 13.22\% & 22.16 & 36.24 & 9.20\% & 16.17 & 25.75 & 10.18\% & 18.49 & 30.48 & 11.99\% \\ \hline
**Localised AGCRN** & **15.41** & 27.21 & **14.93**\% & 19.55 & 31.88 & **12.70**\% & 21.03 & 34.56 & **8.53**\% & 15.63 & **24.78** & **9.78**\% & 17.91 & 29.61 & **11.49\%** \\ \hline \hline \end{tabular}
\end{table}
Table 4. Performance of 99%-localised AGCRNs compared with other non-localised ASTGNN architectures on biosurveillance datasets.

\begin{table}
\begin{tabular}{l c c c c c c c c c c c} \hline \hline \multirow{2}{*}{Methods} & Datasets & \multicolumn{3}{c}{PenMSD3} & \multicolumn{3}{c}{PenMSD4} & \multicolumn{3}{c}{PenMSD7} & \multicolumn{3}{c}{PenMSD8} & \multicolumn{3}{c}{Average} \\ \cline{2-13}  & Metrics & MAE & RMSE & MAPE & MAE & RMSE & MAPE & MAE & RMSE & MAPE & MAE & RMSE & MAPE \\ \hline AGCRN & 15.98 & 28.25 & 15.23\% & 19.83 & 32.30 & 12.97\% & 22.37 & 36.55 & 9.12\% & 15.95 & 25.22 & 10.09\% & 18.53 & 30.58 & 11.85\% \\ Z-GCNETS & 16.64 & 28.15 & 16.39\% & 19.50 & 31.61 & 12.78\% & 21.77 & 35.17 & 9.25\% & 15.76 & 25.11 & 10.01\% & 18.42 & 30.01 & 12.11\% \\ STG-NCDE & 15.57 & **27.09** & 15.06\% & **19.21** & **31.09** & 12.76\% & **20.53** & **33.84** & 8.80\% & **15.45** & 24.81 & 9.92\% & **17.69** & **29.21** & 11.64\% \\ TAMP-S2GCNets & 16.03 & 28.28 & 15.37\% & 19.58 & 31.64 & 13.22\% & 22.16 & 36.24 & 9.20\% & 16.17 & 25.75 & 10.18\% & 18.49 & 30.48 & 11.99\% \\ \hline
**Localised AGCRN** & **15.41** & 27.21 & **14.93**\% & 19.55 & 31.88 & **12.70\%** & 21.03 & 34.56 & **8.53\%** & 15.63 & **24.78** & **9.78**\% & 17.91 & 29.61 & **11.49\%** \\ \hline \hline \end{tabular}
\end{table}
Table 3. Performance of 99%-localised AGCRNs compared with other non-localised ASTGNN architectures on transportation datasets.

\begin{table}
\begin{tabular}{l|c c c c c} \hline \hline \multirow{2}{*}{Sparsity(\%)} & Cora & \multicolumn{2}{c}{Citeseer} & \multicolumn{2}{c}{PubMed} \\ \cline{2-5}  & GCN & GAT & GCN & GAT & GCN & GAT & GCN & GAT \\ \hline
0\% & 80.20 & 82.10 & 69.40 & 72.52 & 78.90 & 79.00 \\
30\% & 80.35 & 83.17 & 69.23 & 72.31 & 79.14 & 79.23 \\
50\% & 72.73 & 75.40 & 69.37 & 72.70 & 78.82 & 79.31 \\
80\% & 65.19 & 70.81 & 58.47 & 63.18 & 68.37 & 77.03 \\
100\% & 56.22 & 63.29 & 53.13 & 57.50 & 61.02 & 64.25 \\ \hline \hline \end{tabular}
\end{table}
Table 2. Computation cost during inference on original and 99%-localised AGCRNs and AGformers. The amount of computation is measured in MFLOPs, and acceleration factors are calculated in the round brackets.