通過噪聲遮掩實現可擴展的深度圖神經網絡

Yuxuan Liang, Wentao Zhang, Zeang Sheng, Ling Yang, Quanqing Xu, Jiawei Jiang, Yunhai Tong, Bin Cui

論文鏈接：https://arxiv.org/abs/2412.14602

背景和挑戰：

圖神經網絡 (GNN) 在圖表示學習方面取得了巨大成功。但由于訓練期間重復特征傳播的計算和存儲成本很高，因此將其擴展到大型圖具有挑戰性。

為了解決可擴展性問題，模型簡化GNN作為可擴展性能的一個有前途的方向，最近引起了人們的極大興趣。最具代表性的工作是SGC，并以此衍生一系列模型簡化GNN比如SIGN，S2GC, GBP, GAMLP等。

盡管現有的模型簡化 GNN 具有較好的可擴展性和預測性能，但它們仍然面臨以下兩個限制：（1）帶有噪聲信息的傳播；（2）具有高預處理開銷的傳播。這兩個限制阻礙了模型簡化 GNN進一步加深。

研究動機：

在本節中，我們將深入分析模型簡化 GNN 中存在的兩個局限性，然后提供我們的見解來幫助我們設計 RMask 的架構。

圖1. 實驗觀察和見解

（1）帶有噪聲信息的傳播：

我們在Cora數據集上隨機選擇 10 個節點，并通過 L2 歸一化P傳播觀察每跳的平均權重。

如圖1a所示，權重較高的節點經常在較低的跳數內被捕獲，而有價值信息的較高跳數的節點表現出相當低的權重。這種現象阻礙了對高跳信息的捕獲。

為了進一步解釋，我們從目標節點開始進行 2 跳傳播。如圖1c所示，2跳捕獲的信息不僅包括當前跳，還包括2跳冗余信息，由于這些信息在1跳內已經可以捕獲，我們將其稱為噪聲信息。隨著傳播深度的增加，高跳捕獲的節點包含大量低跳噪聲信息，難以區分高跳和低跳信息，加劇了過平滑問題。為了進一步研究噪聲信息對過平滑的影響，我們增加跳數，并使用SIGN模型測量噪聲信息和圖平滑度GSL的比例。如圖1b所示，隨著跳數的增加，GSL呈爆炸式增長，噪聲信息也不斷增長。7跳后捕獲的信息完全是冗余的。

基于此，我們重新實現了帶噪聲掩蔽的SIGN。如圖1d所示，節點不僅可以捕獲高跳的有效信息，還可以消除過度平滑問題，如圖1e所示。隨著跳數的增加，準確率和平滑度趨于平穩。

(2) 具有高預處理開銷的傳播:

此外，這種傳播方法會導致顯著的預處理開銷。圖1f 的上部說明了當前模型簡化 GNN 采用的統一預處理過程。首先，預處理的時間復雜度與邊的數量線性相關。每一跳都會從所有先前的跳數中捕獲大量的圖結構信息，從而產生高密集計算開銷。其次，這種方法依賴于不同跳躍之間信息的相互依賴性，只能串行執行。與昂貴的預處理開銷相比，模型簡化 GNN 通常使用簡單的模型進行快速訓練。由于上述原因，預處理開銷構成了端到端訓練時間的大部分。如圖1f下半部分所示，為了減少預處理的高開銷，我們需要一種稀疏和并行的方法來有效地捕獲每一跳的重要信息。

方法：

圖2. Rmask架構

RMask執行流程：

給定指定的跳躍數和圖結構，我們首先根據圖結構對每個節點執行帶有屏蔽機制的隨機游走。然后聚合捕獲的圖結構信息和特征以獲得不同跳躍的結果。

此外，通過這種方式得到的特征傳播結果可以直接替代其他模型簡化GNN（如 S2GC、GBP、SIGN、GAMLP 等）中的P操作。同時，我們保留了現有模型簡化 GNN 在特征組合和模型選擇方面的優勢。

噪聲掩碼機制：

噪聲掩碼機制由兩個部分組成：噪聲信息識別和鄰居節點重要性分配。

第一個組件識別每一跳中的噪聲信息，并使用隨機游走有效地捕獲非冗余的圖結構信息。第二個組件為每個鄰居節點分配重要性權重，以幫助隨機游走捕獲更重要的信息。

（1）噪聲信息識別:

考慮到噪聲的影響，高跳數通常包含來自低跳數的冗余信息。因此，我們需要遍歷整個圖來識別每一跳的噪聲信息。基于對高hop噪聲信息的觀察，我們使用去噪矩陣來記錄噪聲信息：

采用去噪矩陣使我們能夠在確保低過平滑度級別的同時，從每一跳中提取有用信息。然后，對于每一跳，我們使用隨機游走函數（RW）來捕獲當前跳的圖結構信息，然后結合去噪矩陣從每一跳中提取有用的信息：

其中T是隨機游走的次數。通過控制T，我們在準確性和效率之間取得了良好的平衡，使其可以支持大規模圖的處理。

（2）鄰居節點重要性分配:

為了進一步提升預測精度，我們采用基于相鄰節點重要性的偏置隨機游走。使用PageRank來獲取相鄰節點重要性：

其中S是重要性矩陣。通過為圖中的每個邊分配重要性權重，可以引導隨機游動的方向，從而捕獲更重要的去噪信息。具體算法如表1所示：

表1. Rmask算法概述

實驗效果：

實驗主要包含以下四個方面：(1)與最先進的模型簡化方法進行端到端比較 ；(2)分析更深層架構的能力 ；(3)分析效率和準確性之間的權衡 ；(4)分析效率。

（1）與最先進的模型簡化方法進行端到端比較：如表2所示，集成RMask 后，SIGN、S2GC、GBP 和 GAMLP 在所有六個數據集上均實現了比其各自原始版本更好的性能。

表2. 節點分類預測任務的實驗結果

（2）更深層架構的能力：如圖3所示，集成Rmask的模型簡化方法可以更有效地利用深層信息，從而提高準確性。

圖3. 隨著跳數增加，性能變化的趨勢

（3）分析效率和準確性之間的權衡：如圖4（a）所示，使用 RMaska 插件模塊可以在效率和準確性之間進行良好的權衡。

（4）效率實驗：如圖4（b）(c)所示，在所有數據集中，我們的方法成功地減少了端到端訓練中預處理開銷的比例，并且獲得了2.9X以上的提速。

圖4. （a）ogbn-product上效率和準確性之間的權衡。（b）時間開銷分析。（c）加速分析。

總結：

本文介紹了 RMask，這是一個即插即用的模塊，旨在增強現有的模型簡化 GNN 在更高速度下探索更深層次的圖形結構的能力。作為插件方法， RMask可以與大多數模型簡化GNN無縫集成。實驗結果表明，RMask有效地提高了模型簡化GNN的準確性和效率。

實驗室簡介

北京大學數據與智能實驗室（Data And Intelligence Research Lab at Peking Univeristy，PKU-DAIR實驗室）由北京大學計算機學院崔斌教授領導，長期從事數據庫系統、大數據管理與分析、人工智能等領域的前沿研究，在理論和技術創新以及系統研發上取得多項成果，已在國際頂級學術會議和期刊發表學術論文100余篇，發布多個開源項目。課題組同學曾數十次獲得包括CCF優博、ACM中國優博、北大優博、微軟學者、蘋果獎學金、谷歌獎學金等榮譽。PKU-DAIR實驗室持續與工業界展開卓有成效的合作，與騰訊、阿里巴巴、蘋果、微軟、百度、快手、中興通訊等多家知名企業開展項目合作和前沿探索，解決實際問題，進行科研成果的轉化落地。