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)和無(wú)線(xiàn)通信等廣泛領(lǐng)域中展現(xiàn)出卓越的適用性。然而，對(duì)其泛化行為的嚴(yán)謹(jǐn)理論理解仍然有限，特別是在圖分類(lèi)任務(wù)中，模型參數(shù)與圖結(jié)構(gòu)之間的復(fù)雜交互起著關(guān)鍵作用。在現(xiàn)有的理論工具中，基于PAC-貝葉斯范數(shù)的泛化界提供了一種靈活且依賴(lài)于數(shù)據(jù)的框架；然而，當(dāng)前針對(duì)圖神經(jīng)網(wǎng)絡(luò)的研究結(jié)果往往限制了對(duì)圖結(jié)構(gòu)的利用。在本工作中，我們針對(duì)圖卷積網(wǎng)絡(luò)（GCNs）提出了一種拓?fù)涓兄幕赑AC-貝葉斯范數(shù)的泛化框架，該框架將先前開(kāi)發(fā)的框架擴(kuò)展至圖結(jié)構(gòu)模型。我們的方法將泛化界的推導(dǎo)重新表述為一個(gè)隨機(jī)優(yōu)化問(wèn)題，并引入了敏感性矩陣，用于衡量分類(lèi)輸出對(duì)結(jié)構(gòu)化權(quán)重?cái)_動(dòng)的響應(yīng)程度。通過(guò)從空域與譜域視角對(duì)敏感性矩陣施加不同的結(jié)構(gòu)約束，我們推導(dǎo)出一族顯式嵌入圖結(jié)構(gòu)的泛化誤差界。此類(lèi)泛化界可將現(xiàn)有結(jié)果作為特例予以還原，同時(shí)能夠得出比當(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ú)線(xiàn)網(wǎng)絡(luò)等領(lǐng)域從關(guān)系型與結(jié)構(gòu)化數(shù)據(jù)中學(xué)習(xí)方面已被廣泛采用并展現(xiàn)出強(qiáng)大的實(shí)證性能，但關(guān)于這些模型如何以及為何能夠超越訓(xùn)練圖實(shí)現(xiàn)泛化的根本性問(wèn)題，在很大程度上仍未得到充分探索。從統(tǒng)計(jì)學(xué)習(xí)的視角來(lái)看，圖數(shù)據(jù)自身的特性，加之權(quán)重共享與拓?fù)湟蕾?lài)的消息傳遞機(jī)制，對(duì)傳統(tǒng)的泛化分析提出了根本性的挑戰(zhàn)。為應(yīng)對(duì)這些挑戰(zhàn)，針對(duì)圖神經(jīng)網(wǎng)絡(luò)已探索了多種理論框架，包括基于VC維的容量控制[1], [2]、數(shù)據(jù)依賴(lài)型度量（如Rademacher復(fù)雜度）[3], [4]、算法穩(wěn)定性[5], [6]，以及專(zhuān)為相關(guān)樣本與圖結(jié)構(gòu)定制的PAC-貝葉斯方法[7], [8]。在現(xiàn)有方法中，PAC-貝葉斯理論憑借其靈活性、數(shù)據(jù)依賴(lài)特性，以及在過(guò)參數(shù)化情形下仍能給出非平凡（non-vacuous）界的能力，已成為分析深度學(xué)習(xí)模型最具前景的工具之一。越來(lái)越多的研究已證實(shí)PAC-貝葉斯分析在神經(jīng)網(wǎng)絡(luò)（如[9]–[13]）乃至近期的圖結(jié)構(gòu)模型（如[8], [14]–[17]）中的有效性，這推動(dòng)了開(kāi)發(fā)一種拓?fù)涓兄腜AC-貝葉斯泛化框架，以顯式考量圖神經(jīng)網(wǎng)絡(luò)所獨(dú)有的架構(gòu)與譜特性。

A. 相關(guān)工作

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

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

B. 動(dòng)機(jī)與貢獻(xiàn)動(dòng)機(jī)

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

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

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

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

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

II. 預(yù)備知識(shí)

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

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

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

B. 統(tǒng)一框架

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

III. PAC-貝葉斯泛化界

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

IV. 證明

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

V. 結(jié)論

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

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