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

本文提出了一种新颖的方法，通过引入基于彩票票证假设（LTH）的图获胜票（GWT）的概念，显著提高自适应时空图神经网络（ASTGNNs）的计算效率。通过在训练之前采用预先确定的星形拓扑作为GWT，我们平衡了边缘减少和有效信息传播，减少了计算需求，同时保持了高模型性能。生成自适应时空图的时间和内存计算复杂度从$\mathcal{O}(N^2)$显著降低到$\mathcal{O}(N)$。我们的方法通过消除详尽的训练、修剪和重新训练周期，简化了ASTGNN的部署，并在各种数据集上经验证明，可以以大大降低的计算成本实现与完整模型相当的性能。具体而言，我们的方法使得使用配备48GB内存的单个A6000训练ASTGNNs成为可能，从而克服了原始训练期间遇到的内存不足问题，甚至实现了最先进的性能。此外，我们从谱图理论的角度探讨了GWT的有效性，提供了实质性的理论支持。这一进展不仅证明了ASTGNNs中存在高效的子网络，而且扩展了LTH在资源受限环境中的适用性，标志着图神经网络领域的重大进步。代码可在https://anonymous.4open.science/r/paper-1430上获得。

本论文旨在提出一种新的方法来显著提高自适应时空图神经网络（ASTGNNs）的计算效率，通过引入基于Lottery Ticket Hypothesis（LTH）的Graph Winning Ticket（GWT）的概念。是否是一个新问题？

该方法通过在训练之前采用预先确定的星形拓扑结构作为GWT，平衡边缘减少和有效信息传播，从而将生成自适应时空图的时间和内存计算复杂度显着降低从O（N^2）到O（N）。这种方法消除了对详尽的训练、修剪和重新训练周期的需求，证明了ASTGNNs中存在有效的子网络，同时扩展了LTH在资源受限环境中的适用性。

论文的亮点在于：1. 采用GWT的方法可以显著提高ASTGNN的计算效率；2. 实验结果表明，该方法可以在大规模时空数据集上训练ASTGNN，且性能与完整模型相当，计算成本大大降低；3. 从谱图理论的角度探讨了GWT的有效性，提供了实质性的理论支持；4. 提出的方法可以扩展到其他资源受限的环境中。

在这个领域中，最近的相关研究包括：1. Graph Neural Networks for Traffic Flow Forecasting: A Survey；2. Graph Neural Networks for Spatial-Temporal Prediction: A Survey；3. Learning Spatiotemporal Features with 3D Convolutional Networks for Action Recognition。