圖神經(jīng)網(wǎng)絡(luò)拓?fù)涓兄狿AC-貝葉斯泛化分析

Topology-Aware PAC- Bayesian Generalization Analysis for Graph Neural Networks
圖神經(jīng)網(wǎng)絡(luò)的拓?fù)涓兄狿AC-貝葉斯泛化分析

https://arxiv.org/pdf/2604.10553

摘要

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

I. 引言

盡管圖神經(jīng)網(wǎng)絡(luò)在社交網(wǎng)絡(luò)、生物學(xué)和無線網(wǎng)絡(luò)等領(lǐng)域從關(guān)系型與結(jié)構(gòu)化數(shù)據(jù)中學(xué)習(xí)方面已被廣泛采用并展現(xiàn)出強大的實證性能，但關(guān)于這些模型如何以及為何能夠超越訓(xùn)練圖實現(xiàn)泛化的根本性問題，在很大程度上仍未得到充分探索。從統(tǒng)計學(xué)習(xí)的視角來看，圖數(shù)據(jù)自身的特性，加之權(quán)重共享與拓?fù)湟蕾嚨南鬟f機制，對傳統(tǒng)的泛化分析提出了根本性的挑戰(zhàn)。為應(yīng)對這些挑戰(zhàn)，針對圖神經(jīng)網(wǎng)絡(luò)已探索了多種理論框架，包括基于VC維的容量控制[1], [2]、數(shù)據(jù)依賴型度量（如Rademacher復(fù)雜度）[3], [4]、算法穩(wěn)定性[5], [6]，以及專為相關(guān)樣本與圖結(jié)構(gòu)定制的PAC-貝葉斯方法[7], [8]。在現(xiàn)有方法中，PAC-貝葉斯理論憑借其靈活性、數(shù)據(jù)依賴特性，以及在過參數(shù)化情形下仍能給出非平凡（non-vacuous）界的能力，已成為分析深度學(xué)習(xí)模型最具前景的工具之一。越來越多的研究已證實PAC-貝葉斯分析在神經(jīng)網(wǎng)絡(luò)（如[9]–[13]）乃至近期的圖結(jié)構(gòu)模型（如[8], [14]–[17]）中的有效性，這推動了開發(fā)一種拓?fù)涓兄腜AC-貝葉斯泛化框架，以顯式考量圖神經(jīng)網(wǎng)絡(luò)所獨有的架構(gòu)與譜特性。

A. 相關(guān)工作

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

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

B. 動機與貢獻(xiàn)動機

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

貢獻(xiàn)。 基于上述動機，本研究在面向圖神經(jīng)網(wǎng)絡(luò)的拓?fù)涓兄蚉AC-貝葉斯范數(shù)泛化理論方面做出了以下貢獻(xiàn)，尤其聚焦于用于圖分類任務(wù)的圖卷積網(wǎng)絡(luò)（GCNs）：

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

? 將圖結(jié)構(gòu)顯式整合至泛化分析。 本框架將圖結(jié)構(gòu)信息顯式地嵌入泛化界之中，從而能夠清晰地審視圖拓?fù)洹U散算子及其譜性質(zhì)如何影響泛化性能。通過分別刻畫空域聚合效應(yīng)與譜域濾波行為，所得泛化界為理解圖結(jié)構(gòu)在調(diào)控模型復(fù)雜度與魯棒性中的作用提供了新見解，并提供了一個獨特視角，使得圖神經(jīng)網(wǎng)絡(luò)的泛化行為得以從空域與譜域雙重視角進(jìn)行統(tǒng)一剖析。

本文結(jié)構(gòu)安排如下：第一節(jié)介紹了圖神經(jīng)網(wǎng)絡(luò)和基于PAC-貝葉斯邊際界（margin-based bounds）的一些預(yù)備知識，隨后是將統(tǒng)一框架擴展至圖設(shè)置的內(nèi)容。第四節(jié)詳細(xì)闡述了不同敏感性矩陣的具體設(shè)計，并最終得出了統(tǒng)一框架下的各種PAC-貝葉斯泛化界。第五節(jié)總結(jié)了全文，附錄給出了第三節(jié)中使用的關(guān)鍵結(jié)果的一些詳細(xì)證明。

II. 預(yù)備知識

A. 基于范數(shù)的界

GCN的PAC-貝葉斯界。 泛化誤差界可擴展至圖卷積網(wǎng)絡(luò)（GCN）[8], [15]，在計及圖結(jié)構(gòu)的情況下 2
，即，

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

B. 統(tǒng)一框架

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

III. PAC-貝葉斯泛化界

在下文中，我們將這一統(tǒng)一框架擴展至用于圖分類任務(wù)的圖神經(jīng)網(wǎng)絡(luò)，并通過采用計及圖結(jié)構(gòu)的空域與譜域敏感性矩陣設(shè)計，獲得了兩個泛化誤差界。

IV. 證明

為了證明定理 1 和定理 2，我們從雅可比矩陣的推導(dǎo)開始，利用統(tǒng)一框架中網(wǎng)絡(luò)輸出關(guān)于權(quán)重雅可比的一階泰勒展開。

V. 結(jié)論

W. 本文針對圖分類任務(wù)中的圖卷積網(wǎng)絡(luò)開展了PAC-貝葉斯泛化分析，在泛化界中顯式計及了圖結(jié)構(gòu)。通過將面向深度神經(jīng)網(wǎng)絡(luò)的統(tǒng)一PAC-貝葉斯框架擴展至圖結(jié)構(gòu)模型，我們提出了一種原則性方法，該方法能夠容納各向異性高斯后驗分布、對權(quán)重擾動的結(jié)構(gòu)化敏感性，并顯式整合圖拓?fù)浣Y(jié)構(gòu)。由此導(dǎo)出的拓?fù)涓兄夯缒軌蚩坍婫CN的空域或譜域特征，并將若干現(xiàn)有PAC-貝葉斯界作為特例予以還原，同時提供了較先前結(jié)果更為緊致的理論保證。除理論上的精確性（緊致性）之外，所提出的界通過闡明圖結(jié)構(gòu)與異質(zhì)性參數(shù)敏感性如何共同影響圖神經(jīng)網(wǎng)絡(luò)的泛化行為，進(jìn)一步提升了可解釋性。未來的工作將致力于把本框架擴展至其他類別的GNN（如消息傳遞神經(jīng)網(wǎng)絡(luò)、基于注意力的GNN以及采用自適應(yīng)或可學(xué)習(xí)圖算子的架構(gòu)），并進(jìn)一步引入對抗性設(shè)置，涵蓋節(jié)點/邊特征及/或圖結(jié)構(gòu)的對抗性擾動。

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