圖神經網絡拓撲感知PAC-貝葉斯泛化分析

Topology-Aware PAC- Bayesian Generalization Analysis for Graph Neural Networks
圖神經網絡的拓撲感知PAC-貝葉斯泛化分析

https://arxiv.org/pdf/2604.10553

摘要

圖神經網絡已在社交網絡、生物系統、推薦系統和無線通信等廣泛領域中展現出卓越的適用性。然而，對其泛化行為的嚴謹理論理解仍然有限，特別是在圖分類任務中，模型參數與圖結構之間的復雜交互起著關鍵作用。在現有的理論工具中，基于PAC-貝葉斯范數的泛化界提供了一種靈活且依賴于數據的框架；然而，當前針對圖神經網絡的研究結果往往限制了對圖結構的利用。在本工作中，我們針對圖卷積網絡（GCNs）提出了一種拓撲感知的基于PAC-貝葉斯范數的泛化框架，該框架將先前開發的框架擴展至圖結構模型。我們的方法將泛化界的推導重新表述為一個隨機優化問題，并引入了敏感性矩陣，用于衡量分類輸出對結構化權重擾動的響應程度。通過從空域與譜域視角對敏感性矩陣施加不同的結構約束，我們推導出一族顯式嵌入圖結構的泛化誤差界。此類泛化界可將現有結果作為特例予以還原，同時能夠得出比當前圖神經網絡最先進的PAC-貝葉斯界更緊的泛化界。值得注意的是，所提出的框架將圖結構特性顯式地整合到泛化分析之中，從而能夠從空間聚合與譜濾波的雙重視角，統一考察圖神經網絡的泛化行為。

I. 引言

盡管圖神經網絡在社交網絡、生物學和無線網絡等領域從關系型與結構化數據中學習方面已被廣泛采用并展現出強大的實證性能，但關于這些模型如何以及為何能夠超越訓練圖實現泛化的根本性問題，在很大程度上仍未得到充分探索。從統計學習的視角來看，圖數據自身的特性，加之權重共享與拓撲依賴的消息傳遞機制，對傳統的泛化分析提出了根本性的挑戰。為應對這些挑戰，針對圖神經網絡已探索了多種理論框架，包括基于VC維的容量控制[1], [2]、數據依賴型度量（如Rademacher復雜度）[3], [4]、算法穩定性[5], [6]，以及專為相關樣本與圖結構定制的PAC-貝葉斯方法[7], [8]。在現有方法中，PAC-貝葉斯理論憑借其靈活性、數據依賴特性，以及在過參數化情形下仍能給出非平凡（non-vacuous）界的能力，已成為分析深度學習模型最具前景的工具之一。越來越多的研究已證實PAC-貝葉斯分析在神經網絡（如[9]–[13]）乃至近期的圖結構模型（如[8], [14]–[17]）中的有效性，這推動了開發一種拓撲感知的PAC-貝葉斯泛化框架，以顯式考量圖神經網絡所獨有的架構與譜特性。

A. 相關工作

圖神經網絡泛化能力的理論分析已成為統計學習領域一個活躍的研究方向，這得益于圖神經網絡在節點級與圖級預測任務中的廣泛應用。早期試圖刻畫圖神經網絡泛化能力的研究依賴于經典的容量度量，如VC維（例如，[2]針對特定類別的圖神經網絡，[18]針對轉導設定下的節點分類），這類方法可直接界定泛化間隙，但其界限往往隨模型規模與圖規模的增大而呈現不利縮放。更為精細的分析則采用了Rademacher復雜度（例如，[4], [19]針對監督設定下的消息傳遞型圖神經網絡，[18]針對轉導設定下的節點分類，[20]針對半監督節點分類設定下的單層圖卷積網絡）與算法穩定性（例如，[6]針對轉導設定下的單層圖神經網絡，以及[21]中的多層擴展），以獲得能夠捕捉圖采樣與聚合動態的數據依賴型泛化界。此外還存在其他一些方法，如[22]考慮了基于神經正切核的無限寬多層圖神經網絡，以及一系列利用覆蓋數的工作[23]–[27]。關于圖神經網絡泛化性的綜述，請參閱[28]及其所引文獻。

與本研究尤為相關的是基于范數的PAC-貝葉斯框架，該框架已被成功擴展至圖分類任務中的圖神經網絡，以提供同時納入模型復雜度與學習參數不確定性的高概率泛化保證。近期研究表明，圖特有的因素（如最大節點度、特征分布以及擴散算子的譜性質）可顯著影響泛化行為。一個典型的例子是Liao等人[8]的工作，該工作推導了主要類別圖神經網絡（包括圖卷積網絡（GCNs）[29]與消息傳遞型圖神經網絡（MPGNNs）[30]）的PAC-貝葉斯泛化界。其結果揭示：最大節點度與權重矩陣的譜范數/Frobenius范數共同支配著泛化界。后續的PAC-貝葉斯分析進一步完善了這一視角，例如，[15]針對圖數據中對抗性擾動下的魯棒泛化問題進行了研究，同時在界的形式化表述中仍利用了譜性質。Ju等人[14]則提出了改進的PAC-貝葉斯泛化界，其縮放依賴關系基于圖特征擴散矩陣的最大奇異值，而非僅依賴于節點度。重要的是，圖算子與權重矩陣譜范數的使用，與圖級任務中泛化性能的實證觀察高度吻合，并為理解圖結構如何影響預測性能提供了更為銳利的洞察。最近，此類基于范數的PAC-貝葉斯框架已被擴展用于推導拓撲圖神經網絡[16]與超圖神經網絡[17]的泛化界。值得注意的是，這些結果關鍵依賴于將[11]中的擾動界擴展至具有矩陣譜范數集中性質的圖結構模型，這在一定程度上限制了對網絡架構影響的深入系統考察。

B. 動機與貢獻動機

盡管針對圖神經網絡的PAC-貝葉斯泛化結果日益豐富，但現有分析仍存在若干局限性，這構成了本研究的動機。首先，大多數已有工作假設所有參數具有同質不確定性的各向同性高斯后驗分布，這與圖神經網絡的實際情況尤為不符；在實踐中，權重共享、依賴于深度的聚合機制以及由圖結構誘導的相關性，會導致高度各向異性且具有層特異性的敏感性模式。其次，現有針對圖神經網絡的PAC-貝葉斯界往往高度依賴于對權重擾動與圖傳播算子譜范數的控制，而相應的譜范數集中不等式在面對深層、寬網絡或特定結構化架構時已知較為脆弱，從而限制了所得泛化保證的緊致性。第三，現有方法通常僅通過最大節點度或全局譜半徑等粗粒度指標來引入圖結構，極少考慮不同圖組成部分的異質性影響，亦鮮少顧及損失曲面相對于單個權重與網絡層的多樣化敏感性。這些局限性共同表明，亟需構建一種面向圖神經網絡的拓撲感知型PAC-貝葉斯范數泛化框架——該框架需允許各向異性后驗分布、支持超越全局譜范數的精細化擾動控制，并顯式整合圖結構與逐參數敏感性——這對于建立圖神經網絡泛化行為更具理論根基的理解至關重要。

貢獻。 基于上述動機，本研究在面向圖神經網絡的拓撲感知型PAC-貝葉斯范數泛化理論方面做出了以下貢獻，尤其聚焦于用于圖分類任務的圖卷積網絡（GCNs）：

? 統一框架下的拓撲感知泛化界。 我們證明了文獻[31]中先前提出的面向深度神經網絡的統一PAC-貝葉斯范數泛化框架可自然擴展至圖結構模型，顯式計及圖卷積網絡固有的消息傳遞與聚合機制。通過引入敏感性矩陣以刻畫圖分類輸出對GCN權重擾動的響應差異，我們在不同的結構假設下推導出一族PAC-貝葉斯泛化界。具體而言，從空域（節點與鄰域級聚合）與譜域（圖傅里葉變換與算子范數）雙重視角出發，對這些矩陣施加對角、低秩或圖對齊結構約束，可導出一系列泛化誤差界。這些泛化界可將現有針對圖神經網絡的PAC-貝葉斯結果作為特例予以還原，并被證明緊于當前依賴各向同性擾動或全局譜范數控制的最先進泛化界。

? 將圖結構顯式整合至泛化分析。 本框架將圖結構信息顯式地嵌入泛化界之中，從而能夠清晰地審視圖拓撲、擴散算子及其譜性質如何影響泛化性能。通過分別刻畫空域聚合效應與譜域濾波行為，所得泛化界為理解圖結構在調控模型復雜度與魯棒性中的作用提供了新見解，并提供了一個獨特視角，使得圖神經網絡的泛化行為得以從空域與譜域雙重視角進行統一剖析。

本文結構安排如下：第一節介紹了圖神經網絡和基于PAC-貝葉斯邊際界（margin-based bounds）的一些預備知識，隨后是將統一框架擴展至圖設置的內容。第四節詳細闡述了不同敏感性矩陣的具體設計，并最終得出了統一框架下的各種PAC-貝葉斯泛化界。第五節總結了全文，附錄給出了第三節中使用的關鍵結果的一些詳細證明。

II. 預備知識

A. 基于范數的界

GCN的PAC-貝葉斯界。 泛化誤差界可擴展至圖卷積網絡（GCN）[8], [15]，在計及圖結構的情況下 2
，即，

泛化界公式(8)建立在[8, 引理3.1]與[15, 引理4.3]中關于GCN擾動界的關鍵引理之上，其中由權重擾動引起的輸出變化上界為：

B. 統一框架

這種統一框架允許我們通過靈活設計敏感性矩陣來探究當前神經網絡的敏感性，從而使得泛化界能夠衡量特定網絡架構對泛化性能的敏感程度。這為我們提供了一個靈活且強大的工具，用于檢驗深度神經網絡（DNN）的泛化能力。

III. PAC-貝葉斯泛化界

在下文中，我們將這一統一框架擴展至用于圖分類任務的圖神經網絡，并通過采用計及圖結構的空域與譜域敏感性矩陣設計，獲得了兩個泛化誤差界。

IV. 證明

為了證明定理 1 和定理 2，我們從雅可比矩陣的推導開始，利用統一框架中網絡輸出關于權重雅可比的一階泰勒展開。

V. 結論

W. 本文針對圖分類任務中的圖卷積網絡開展了PAC-貝葉斯泛化分析，在泛化界中顯式計及了圖結構。通過將面向深度神經網絡的統一PAC-貝葉斯框架擴展至圖結構模型，我們提出了一種原則性方法，該方法能夠容納各向異性高斯后驗分布、對權重擾動的結構化敏感性，并顯式整合圖拓撲結構。由此導出的拓撲感知泛化界能夠刻畫GCN的空域或譜域特征，并將若干現有PAC-貝葉斯界作為特例予以還原，同時提供了較先前結果更為緊致的理論保證。除理論上的精確性（緊致性）之外，所提出的界通過闡明圖結構與異質性參數敏感性如何共同影響圖神經網絡的泛化行為，進一步提升了可解釋性。未來的工作將致力于把本框架擴展至其他類別的GNN（如消息傳遞神經網絡、基于注意力的GNN以及采用自適應或可學習圖算子的架構），并進一步引入對抗性設置，涵蓋節點/邊特征及/或圖結構的對抗性擾動。

原文鏈接： https://arxiv.org/pdf/2604.10553