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

作者：Wenying Duan, Tianxiang Fang, Hong Rao, Xiaoxi He

機構：南昌大學，澳門大學

arXiv網址：https://arxiv.org/abs/2406.08287

Cool Paper：https://papers.cool/arxiv/2406.08287
Code: https://anonymous.4open.science/r/paper-1430

關鍵詞：：自適應時空圖神經網絡，彩票假設，圖中獎票，計算效率。

TL; DR:本文提出了一種新方法，通過預訓練識別圖神經網絡中的高效子網絡（圖中獎票），顯著提高了自適應時空圖神經網絡的計算效率，同時保持了模型性能。

12 Pages 1 Preliminaries 1.5 Methodology 3.75 Experiments 1 Appendix

該研究團隊在KDD23也有一篇對ASTGNNs（自適應時空圖神經網絡）的研究：

2023 [KDD] Localised Adaptive Spatial-Temporal Graph Neural Network

TL;DR: 對于自適應時空圖神經網絡（ASTGNN）在測試（推理）階段圖結構的空間信息是冗余的，訓練是必要的。

🌟【緊跟前沿】“時空探索之旅”與你一起探索時空奧秘！🚀
歡迎大家關注時空探索之旅

摘要

在本文中，提出了一種新方法，通過引入源自彩票假設 (Lottery Ticket Hypothesis，LTH) 的圖中獎彩票 (Graph Winning Ticket，GWT) 概念，顯著提高自適應時空圖神經網絡 (ASTGNN) 的計算效率。通過在訓練之前采用預先確定的星型拓撲作為 GWT，本文在邊緣減少和高效信息傳播之間取得平衡，在保持高模型性能的同時降低了計算需求。生成自適應時空圖的時間和空間計算復雜度都從$$O(N^2)$$ 顯著降低到 $$O(N)$$。本文的方法簡化了 ASTGNN 部署，消除了對詳盡訓練、剪枝和再訓練周期的需求，并在各種數據集上通過實證證明，有可能以低得多的計算成本實現與完整模型相當的性能。具體來說，本文的方法能夠使用配備 48 GB 顯存的單張 A6000 在最大規模時空數據集上訓練 ASTGNN，克服了原始訓練中遇到的內存不足問題，甚至達到了最先進的性能。此外，本文從譜圖理論的角度深入研究了 GWT 的有效性，提供了大量的理論支持。這一進步不僅證明了 ASTGNN 中存在高效子網絡，而且拓寬了 LTH 在資源受限環境中的適用性，標志著圖神經網絡領域的重大進步。

Q: 這篇論文試圖解決什么問題？

A: 這篇論文提出了一種新的方法，旨在顯著提高自適應時空圖神經網絡（Adaptive Spatial-Temporal Graph Neural Networks，簡稱ASTGNNs）的計算效率。具體來說，論文通過引入基于彩票假設（Lottery Ticket Hypothesis，簡稱LTH）的圖中獎票（Graph Winning Ticket，簡稱GWT）的概念，以期在減少計算需求的同時保持模型性能。

ASTGNNs在處理大規模時空數據時面臨顯著的計算開銷挑戰，這主要是因為它們需要學習完整的圖上的自適應鄰接矩陣，并且聚合階段計算密集。論文的主要貢獻包括：

1. 提出了一種在訓練前確定GWT的方法，通過采用預定的星型拓撲作為GWT，平衡了邊的減少和有效信息傳播之間的關系，從而在降低計算需求的同時保持了高性能。
2. 通過實驗驗證了這種方法在多個數據集上與完整模型相比具有可比性，甚至在某些情況下性能更優，同時顯著降低了訓練和推理的計算成本。
3. 從譜圖理論的角度深入探討了GWT的有效性，為LTH在資源受限環境中的適用性提供了理論支持。

這種方法不僅證明了ASTGNNs內存在高效的子網絡，而且擴展了LTH在資源受限設置中的適用性，是圖神經網絡領域的重要進展。

Q: 有哪些相關研究？

A: 論文中提到了多個與時空圖神經網絡（STGNNs）和彩票假設（LTH）相關的研究領域和具體工作。以下是一些主要的相關研究：

1. 時空圖神經網絡（STGNNs）: 這類網絡專注于分析時空數據，特別是動態信號在不同空間域之間的相互作用。STGNNs能夠建模節點之間的空間依賴性，并且通過學習鄰接矩陣來有效捕捉數據的潛在模式。
2. 預定義和自學習方法: STGNNs可以根據構建鄰接矩陣的方法分為預定義方法和自學習方法。預定義方法使用領域知識來構建圖，例如ASTGNN和STGCN利用道路網絡結構。自學習方法則通過時間變化的輸入動態構建圖，如PDFormer和DG。
3. 彩票假設（LTH）: LTH提出了在大型神經網絡中存在較小的子網絡（稱為“中獎彩票”），這些子網絡可以在隔離訓練時達到與原始網絡相似的性能。這個概念已經被擴展到ASTGNNs的領域，即在可學習的時空圖中識別這樣的子網絡，即GWTs。
4. 圖彩票假設（Graph Lottery Ticket Hypothesis）: 這是LTH在圖神經網絡（GNNs）中的擴展，研究者通過迭代應用UGS來識別圖彩票。
5. ASTGNN模型: 如Graph WaveNet和AGCRN，這些模型通過隨機初始化的可學習節點嵌入來促進自適應圖的生成。
6. 譜圖理論: 論文還深入探討了譜圖理論，為GWT的有效性提供了理論支持。
7. 其他STGNNs: 論文中還提到了其他幾種STGNNs，包括DGCRN、MegaCRN、STGODE、D2STGNN和DSTAGNN，這些模型代表了該領域的最新趨勢。
8. 圖結構的稀疏化: 論文中提到了AGS方法，這是一種通過稀疏化空間圖來提高ASTGNNs推理效率的先前工作。

這些相關研究為理解論文提出的GWT方法提供了背景，并展示了該方法在現有研究基礎上的創新和改進。

Q: 論文如何解決這個問題？

A: 論文通過以下幾個關鍵步驟解決了提高ASTGNNs計算效率的問題：

1. 引入圖中獎票（GWT）概念：基于彩票假設（LTH），論文提出了圖中獎票的概念，這是一種存在于ASTGNNs可學習空間圖中的高效子網絡，可以在減少計算成本的同時保持模型性能。
2. 預確定星型拓撲：論文提出使用星型拓撲作為GWT，這種拓撲結構在減少邊數的同時，仍然保持了有效的信息傳播能力。星型拓撲的直徑為2，可以在兩層AGCN中實現全局空間依賴性的建模。
3. 降低計算復雜度：通過使用星型拓撲，論文將生成自適應時空圖的時間和內存計算復雜度從O(𝑁^2)顯著降低到O(𝑁)。
4. 簡化訓練過程：論文的方法避免了傳統訓練過程中的迭代訓練、剪枝和重訓練的需要，從而簡化了ASTGNNs的部署。
5. 理論和實證分析：論文從譜圖理論的角度提供了對GWT有效性的深入分析，并在多個數據集上通過實驗驗證了星型拓撲作為GWT的性能。
6. 提出GWT-AGCN層：為了進一步提高效率和硬件兼容性，論文提出了一種新的GWT-AGCN層，該層使用矩陣乘法和標準激活函數，與傳統AGCN層相比，具有更低的計算復雜度和更好的硬件兼容性。
7. 中心節點選擇和初始化：論文討論了中心節點選擇的重要性，并提出了一種平均初始化方法，以確保中心節點嵌入向量位于節點嵌入空間的物理中心，從而提高模型的預測精度。

通過這些方法，論文不僅提高了ASTGNNs的計算效率，還保持了模型性能，甚至在某些情況下達到了最先進的性能水平。

Q: 論文做了哪些實驗？

A: 論文中進行了一系列實驗來驗證所提出方法的有效性，實驗主要包括以下幾個方面：

1. 實驗設置：
   • 使用了兩種典型的ASTGNN架構：AGCRN和Graph WaveNet (GWNET)。
   • 在五個大型時空數據集上進行實驗，包括PEMS07、SD、GBA、GLA和CA。
2. 性能評估：
   • 使用了三個標準的預測準確度指標：平均絕對誤差（MAE）、均方根誤差（RMSE）和平均絕對百分比誤差（MAPE）。
3. 效率評估：
   • 評估了模型訓練和推理的墻鐘時間。
   • 報告了訓練過程中的批量大小，以反映模型處理大規模數據集的能力。
4. 主要結果：
   • 展示了AGCRN和GWNET在不同數據集上的性能和效率比較。
   • 證明了在所有數據集上，使用GWT的ASTGNNs（AGCRN★和GWNET★）與原始模型相比具有可比或更優的性能。
5. 收斂性分析：
   • 展示了原始AGCRN和AGCRN★在PEMS07和SD數據集上的損失和測試MAE曲線，證明了預確定的GWT確保了與完整圖模型同樣一致、快速和穩定的收斂性。
6. 與最新技術比較：
   • 將AGCRN和GWNET與當前最先進的STGNNs進行了比較，包括DGCRN、MegaCRN、STGODE、D2STGNN和DSTAGNN。
7. 節點嵌入初始化的影響分析：
   • 對AGCRN★進行了消融研究，比較了平均初始化和隨機初始化對模型預測精度的影響。
8. 與AGS方法的比較：
   • 將所提出的方法與現有的AGS方法進行了比較，證明了所提出方法的優越性。
9. T★的魯棒性分析：
   • 通過引入T★的擾動過程，研究了T★的連通性對ASTGNN建模全局空間依賴性的重要性。

這些實驗全面評估了所提出方法在不同方面的表現，包括預測準確性、計算效率、收斂速度、魯棒性等，從而為論文的主張提供了有力的實證支持。

Q: 總結一下論文的主要內容

A: 這篇論文的主要內容可以概括為以下幾個要點：

1. 問題提出：論文針對自適應時空圖神經網絡（ASTGNNs）在大規模時空數據上的訓練和推理階段存在的高計算開銷問題，提出了一種新的方法來提高計算效率。
2. 方法介紹：引入了基于彩票假設（LTH）的圖中獎票（GWT）概念，通過預訓練前確定星型拓撲結構作為GWT，以減少邊數同時保持有效信息傳播，從而降低計算復雜度。
3. 理論支持：利用譜圖理論為星型拓撲的有效性提供了理論分析和證明，證明了星型拓撲是完整圖的一個良好近似，能夠學習到空間時間依賴性。
4. 實驗驗證：在多個大型時空數據集上進行了實驗，驗證了使用GWT的ASTGNNs在保持或甚至超越完整模型性能的同時，顯著降低了計算成本。
5. 效率和性能：論文的方法不僅減少了模型的計算需求，還展示了在不同數據集上與現有模型相比的可比性或優越性。
6. 簡化訓練過程：通過預確定GWT，避免了傳統訓練過程中的迭代訓練、剪枝和重訓練的需要，簡化了ASTGNNs的部署。
7. GWT-AGCN層：提出了GWT-AGCN層，提高了模型的硬件兼容性和計算效率。
8. 中心節點選擇：討論了中心節點選擇的重要性，并提出了平均初始化方法來提高模型的預測精度。
9. 未來工作：論文最后提出了一些可能的研究方向，包括長期預測、不同拓撲結構的GWT、跨領域適用性等。

出了GWT-AGCN層，提高了模型的硬件兼容性和計算效率。
8. 中心節點選擇：討論了中心節點選擇的重要性，并提出了平均初始化方法來提高模型的預測精度。
9. 未來工作：論文最后提出了一些可能的研究方向，包括長期預測、不同拓撲結構的GWT、跨領域適用性等。

總的來說，這篇論文在理論和實踐層面都為ASTGNNs的效率和實用性提供了顯著的改進，并通過實驗驗證了其有效性。