In this paper, we present a novel method to significantly enhance the
computational efficiency of Adaptive Spatial-Temporal Graph Neural Networks
(ASTGNNs) by introducing the concept of the Graph Winning Ticket (GWT), derived
from the Lottery Ticket Hypothesis (LTH). By adopting a pre-determined star
topology as a GWT prior to training, we balance edge reduction with efficient
information propagation, reducing computational demands while maintaining high
model performance. Both the time and memory computational complexity of
generating adaptive spatial-temporal graphs is significantly reduced from
$\mathcal{O}(N^2)$ to $\mathcal{O}(N)$. Our approach streamlines the ASTGNN
deployment by eliminating the need for exhaustive training, pruning, and
retraining cycles, and demonstrates empirically across various datasets that it
is possible to achieve comparable performance to full models with substantially
lower computational costs. Specifically, our approach enables training ASTGNNs
on the largest scale spatial-temporal dataset using a single A6000 equipped
with 48 GB of memory, overcoming the out-of-memory issue encountered during
original training and even achieving state-of-the-art performance.
{Furthermore, we delve into the effectiveness of the GWT from the perspective
of spectral graph theory, providing substantial theoretical support.} This
advancement not only proves the existence of efficient sub-networks within
ASTGNNs but also broadens the applicability of the LTH in resource-constrained
settings, marking a significant step forward in the field of graph neural
networks. Code is available at this https URL

通过引入 “图中的中奖号码（GWT）” 的概念，我们提出了一种新颖的方法来显著提高自适应空间 - 时间图神经网络（ASTGNNs）的计算效率。通过采用预先确定的星形拓扑作为 GWT 来训练，我们在减少计算需求的同时，保持高性能的模型表现。我们的方法通过消除详尽的训练、修剪和重新训练周期，以及在各种数据集上的实证验证，可实现与完整模型相当的性能与大大降低的计算成本。此外，我们深入探讨了来自谱图理论角度的 GWT 的有效性，提供了实质性的理论支持。这一进展不仅证明了 ASTGNNs 中存在高效子网络的存在，而且扩大了资源受限环境中 LTH 的适用性，标志着图神经网络领域的重大进展。

自适应时空图神经网络中的图中优胜模型的预训练鉴定

Pre-Training Identification of Graph Winning Tickets in Adaptive  Spatial-Temporal Graph Neural Networks

Spatial-temporal graph models are prevailing for abstracting and modelling
spatial and temporal dependencies. In this work, we ask the following question:
\textit{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.

本研究针对自适应时空图神经网络 (ASTGNNs) 进行局部化，提出了一种名为自适应图稀疏化（AGS）的图稀疏化算法。实验表明，通过 AGS 进行稀疏化，ASTGNNs 的空间图可以被稀疏化超过 99.5％，而准确性不会有太大下降。因此，研究者得出以下结论：在测试的数据中，时空依赖性所提供的信息主要包含在时间依赖性所提供的信息中，因此在推理过程中可以忽略；尽管空间依赖性提供冗余信息，但对于 ASTGNNs 的有效训练至关重要，因此不能在训练过程中忽略它们。局地性的实现有可能减少在大规模时空数据上所需的计算的开销，从而进一步支持 ASTGNNs 的分布式部署。