图神经网络拓扑感知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