高斯混合模型的增强图神经网络泛化

Graph Neural Network Generalization with Gaussian Mixture Model Based Augmentation

基于高斯混合模型的增强图神经网络泛化

https://arxiv.org/pdf/2411.08638

摘要

图神经网络（GNN）在节点和图分类等任务中展现出巨大潜力，但其泛化能力常面临挑战，尤其是在处理未见数据或分布外（OOD）数据时。当训练数据的规模或多样性有限时，这些问题会进一步加剧。为解决上述问题，我们引入了一个基于拉德马赫复杂度的理论框架，用于计算泛化误差的遗憾界（regret bound），并刻画数据增强的影响。该框架指导了 GRATIN 算法的设计 —— 这是一种高效的图数据增强算法，其利用高斯混合模型（GMM）近似任意分布的能力。我们的方法不仅在泛化性能上超越了现有增强技术，还优化了时间复杂度，使其高度适用于实际应用场景。相关代码已开源，详见：https://github.com/abbahaddou/GRATIN。

1. 引言
   图是建模复杂关系与交互的基础且普适的结构。在生物学中，图被用于表示蛋白质相互作用的复杂网络，以及在药物发现中建模分子关系（Gaudelet 等，2021；Jagtap 等，2022）。同样，社交网络捕捉了关系和社区互动（Aboussalah 等，2023a；Zeng 等，2022；Malliaros & Vazirgiannis，2013；Newman 等，2002）。为应对图结构数据带来的独特挑战，图神经网络（GNN）作为一类专门设计用于直接处理图的神经网络应运而生。与针对图像或序列等网格状数据优化的传统神经网络不同，GNN 旨在处理和学习嵌入在图结构中的关系信息。GNN 已在节点和图分类等一系列图表示学习任务中展现出了最先进的性能，证明了其在各种实际应用中的有效性（Vignac 等，2023；Corso 等，2023；Duval 等，2023；Castro-Correa 等，2024；Chi 等，2022；Panagopoulos 等，2024；Aboussalah & Ed-dib，2025）。

尽管 GNN 具有令人印象深刻的能力，但它们在泛化方面面临重大挑战，尤其是在处理未见或分布外（OOD）数据时（Guo 等，2024；Li 等，2022）。OOD 图是指在图结构、节点特征或边类型方面与训练数据显著不同的图，这使得 GNN 难以适应并在此类数据上表现良好。当 GNN 在小数据集上训练时也会面临这一挑战，有限的数据多样性阻碍了模型有效泛化的能力。为应对这些挑战，学术界探索了各种策略来提高 GNN 的鲁棒性和泛化能力（Abbahaddou 等，2024；Yang 等，2023）。

GNN 的泛化界已使用各种理论工具推导得出，如 Vapnik-Chervonenkis（VC）维（Pfaff 等，2021；Garg 等，2020）和拉德马赫复杂度（Yin 等，2019；Esser 等，2021）。此外，Liao 等人（2021）是最早使用 PAC 贝叶斯方法为 GNN 建立泛化界的学者之一。神经正切核也被用于研究通过梯度下降训练的无限宽 GNN 的泛化特性（Jacot 等，2018；Du 等，2019；Huang 等，2024）。虽然现有研究大多集中在节点分类任务上，但提高图分类的泛化能力带来了独特的挑战。改善图分类泛化能力的技术可大致分为架构和基于数据集的策略（Tang & Liu，2023；Buffelli 等，2022）。在数据集方面，对抗训练和数据增强等技术发挥着重要作用。

更广泛地说，数据增强方法通过创建合成或修改的图实例来丰富训练集，减少过拟合并增强模型对不同图结构的适应性。数据增强已在图像（Krizhevsky 等，2012）和时间序列（Aboussalah 等，2023b）等不同类型的数据结构中显示出其优势。对于图数据结构，生成原始图的增强版本，如添加或删除节点和边，或扰动节点特征（Rong 等，2020；You 等，2020），可以创建更多样化的训练集。受计算机视觉中 Mixup 技术的成功启发（Rebuffi 等，2021；Dabouei 等，2021；Hong 等，2021），G-Mixup 和 GeoMix 等额外方法已被开发出来，将 Mixup 适应于图数据（Ling 等，2023；Han 等，2022）。这些技术通过组合不同的图来创建新的合成训练示例，进一步丰富了数据集并增强了 GNN 对新的未见图结构的泛化能力。

在这项工作中，我们介绍了 GRATIN—— 一种基于高斯混合模型（GMM）的图增强技术，其在最终隐藏表示层面上操作。具体来说，在理论结果的指导下，我们应用期望最大化（EM）算法在图表示上训练 GMM。然后，我们使用这个 GMM 通过采样生成新的增强图表示，从而提高训练数据的多样性。

我们的工作贡献如下：

• GNN 泛化的理论框架

  ：我们引入了一个理论框架，能够严格分析图数据增强如何影响 GNN 的泛化能力。该框架为通过增强提升性能的潜在机制提供了新见解。

• 基于 GMM 的高效图数据增强

  ：我们提出了 GRATIN—— 一种利用高斯混合模型（GMM）的快速高效图数据增强技术。该方法在保持计算简洁性的同时增强了训练数据的多样性，使其可扩展至大型图数据集。

• 使用影响函数的全面理论分析

  ：我们通过影响函数的视角对增强策略进行了深入理论分析，为该方法对泛化性能的影响提供了原理性理解。

• 实证验证

  ：通过在真实数据集上的实验，我们证实 GRATIN 在实际应用中是一种快速、高性能的图增强方案。

2. 背景与相关工作

其中，AGGREGATE(·)是一个排列不变函数，用于将节点v的邻域特征向量组合成一个聚合向量。这个聚合向量与之前的特征向量h(vₜ₋₁)一起被送入COMBINE(·)函数，该函数将这两个向量合并以生成节点v的更新特征向量。

在经过T次邻域聚合迭代后，图神经网络（GNN）通常通过首先应用一个排列不变的读出函数（例如求和操作符）来生成图级别的表示，对最终的节点嵌入进行聚合。然后，这个聚合输出会被传递到一个可训练的神经网络中，例如多层感知机（MLP），记作Ψ，称为后读出神经网络，以生成最终的图级别预测或表示。

数学上，这一过程可以表示为：

两种流行的 GNN 架构是图卷积网络（GCN）和图同构网络（GIN）（Kipf & Welling, 2017; Xu et al., 2019）。这些模型的具体表达式可在附录 D 中找到。

图数据增强。图数据增强已成为提升 GNN 性能和鲁棒性的关键技术。经典的图增强方法侧重于通过结构修改生成增强图，主要包括 DropEdge、DropNode 和子图采样（Rong et al., 2020; You et al., 2020）。例如，DropEdge 在训练过程中随机删除图中的部分边，从而提升模型对缺失或噪声连接的鲁棒性；DropNode 则删除特定节点及其连接，其假设是节点的缺失不会影响原始图的语义信息（即结构和关系信息）；而子图采样则通过随机游走从原始图中采样子图作为训练图。

除经典方法外，近年来的研究探索了更复杂的增强技术，重点在于操作图嵌入和利用图的几何性质。受计算机视觉中 Mixup 技术成功的启发（Rebuffi et al., 2021; Dabouei et al., 2021; Hong et al., 2021），多项研究提出了适用于图的 Mixup 变体。例如，Manifold-Mixup 模型在嵌入空间中对图分类任务执行 Mixup 操作，该技术在 READOUT 函数之后对图级嵌入进行插值，从而在嵌入空间中融合不同图（Wang et al., 2021）；类似地，G-Mixup（Han et al., 2022）使用图 on（graphon）对每个图类的拓扑结构进行建模，然后对不同类的图 on 进行插值，再通过从混合图 on 中采样生成合成图。需要注意的是，G-Mixup 基于一个重要假设：属于同一类的图可由单个图 on 生成。其他先进技术包括 S-Mixup 方法，该方法通过先确定一对图之间的节点级对应关系来对图进行插值（Ling et al., 2023），以及 FGW-Mixup，其采用融合 Gromov-Wasserstein 重心来计算混合图，但存在计算耗时的问题（Ma et al., 2024）。最后，GeoMix（Zeng et al., 2024）利用 Gromov-Wasserstein 测地线更高效地对图进行插值。通过利用这些结构增强技术，GNN 能够更好地泛化到未见的图结构。

3. GRATIN：用于图数据增强的高斯混合模型 在本节中，我们将介绍图数据增强的数学框架及其与 GNN 泛化性能的联系。随后，我们将提出基于高斯混合模型（GMM）的图增强方法 GRATIN。

3.1 图数据增强的形式化描述

定理 3.1 依赖于损失函数是利普希茨连续的假设。鉴于现实世界数据集中输入的节点特征和图结构通常是有限制的，这一假设是合理的，即节点特征通常被归一化或限制在一个固定的范围内，而图结构（通过邻接矩阵或其归一化形式表示）具有有界的谱性质，从而确保了受限的输入空间。此外，我们可以通过将任何标准分类损失与一个严格递增的函数组合，将值映射到区间 [0, 1]，从而确保损失函数的取值范围在 [0, 1] 内。我们在附录 A 中提供了该定理的证明。

在图的隐藏表示层面上进行操作，而不是直接在图输入空间中，提供了额外的优势。隐藏表示能够捕捉每个图的结构信息和节点特征，从而实现同时增强这两方面泛化能力的增强。此外，比较原始图和增强图时需要进行节点对齐，这在计算上是昂贵的。通过在隐藏表示上进行操作，节点对齐变得不再必要。此外，正如我们将在第3.4节中讨论的，增强数据的有效性取决于具体的图神经网络（GNN）架构。通过利用通过GNN学习到的图表示，我们确保增强过程保持架构特定性，与所选模型的归纳偏差保持一致。

3.2 提出的方法

3.3 时间复杂度

3.4 通过影响函数分析增强图的泛化能力

3.5 Fisher 指导的 GMM 增强

4. 实验结果

在本节中，我们展示结果与分析，实验设置详见附录 K。

GNN 的泛化性能

在表 1 和表 2 中，我们将数据增强策略的测试准确率与基线方法进行对比，更大数据集上的相同实验结果见附录 L。为确保公平比较，所有基线模型均使用相同的训练 / 验证 / 测试划分、GNN 架构和超参数。值得注意的是，基线方法的标准差较高，这是图分类任务的常见特征 —— 与节点分类不同，图分类的性能指标方差更大（Errica 等，2020；Duval & Malliaros，2022）。总体而言，我们的方法在大多数数据集上始终实现最佳或极具竞争力的性能。

此外，我们观察到基线方法的结果随 GNN 骨干网络的不同而变化，这促使我们使用影响函数进行深入研究。如定理 3.4 所示，梯度（更广义地说，模型架构）显著影响增强数据对测试集性能的作用。

结构损坏鲁棒性

除泛化性能外，我们遵循 Zeng 等人（2024）的方法评估数据增强策略的鲁棒性。具体而言，通过在训练集中随机删除或添加 10%/20% 的边，测试增强策略对图结构损坏的鲁棒性。仅损坏训练图会在训练与测试数据集间引入分布偏移，从而评估 GRATIN 对 OOD 测试图的泛化与预测能力。IMDB-BIN、IMDB-MUL、PROTEINS 和 DD 数据集的实验结果见表 3。可见，我们的数据增强策略在所有情况下均实现最高测试准确率，显著提升了模型对结构损坏的鲁棒性。

影响函数分析

图 2 展示了 GRATIN 采样的增强数据的平均影响密度分布，结果与表 1-2 的实证发现一致。在 MUTAG 和 PROTEINS 数据集上，GRATIN 增强对 GCN 和 GIN 模型均有正向影响；而在 DD 数据集上，GRATIN 对 GIN 无显著作用，但对 GCN 生成大量正影响分数的增强样本，从而提升其性能。这与基线结果一致 —— 当应用于 DD 数据集时，多数图增强策略对 GCN 测试准确率的提升显著高于 GIN。

该现象值得深入分析：在 DD 数据集上使用 GIN 模型推理时，我们观察到 Softmax 饱和现象（预测类别概率趋近于 0 或 1，见附录 M）。推测其原因是 DD 的平均节点数较多，且 GIN 未对节点表示进行归一化，导致图表示范数过大。饱和使模型预测置信度极高，最终导致损失函数对输入图的梯度收敛至 0，进而使影响分数可忽略（如 3.4 节所述）。

基于 Fisher 的过滤

图 3 展示了 Fisher 引导的 GMM 增强实验中，删除增强表示对测试准确率的影响（结果来自单次训练）。初始时，删除低影响或负影响的增强图可提升泛化能力；当移除大量低质量增强并保留高影响增强时，测试准确率达到峰值 —— 这表明精选的增强子集可优化模型性能。但随着增强图删除量增加，训练集多样性下降；当删除率达 100% 时，模型仅基于原始数据训练（参考案例），准确率显著下降，印证了数据增强对泛化的促进作用。

5. 结论

我们提出了 GRATIN—— 一种新的图数据增强方法，可同时提升 GNN 的泛化能力和鲁棒性。该方法受理论研究启发，在读出函数的输出层应用高斯混合模型（GMM）。利用 GMM 的通用近似特性，我们能够采样新的图表示，从而有效控制拉德马赫复杂度的上界，确保 GNN 泛化性能的提升。通过在广泛使用的数据集上进行大量实验，我们证明了该方法不仅具有强大的泛化能力，还能在结构扰动下保持鲁棒性。

我们的方法在时间复杂度方面也具有额外优势：与基线方法不同，GRATIN 无需为每个训练图或图对生成增强数据，而是一次性将 GMM 拟合到整个训练数据集，从而实现快速的图数据增强，且不会产生显著的额外反向传播时间。

https://arxiv.org/pdf/2411.08638