图神经网络(二十三) Data Augmentation for Graph Neural Networks，AAAI2021

本文的研究者来自美国圣母大学。
数据增强技术已被普遍应用于提高机器学习模型的通用性。然而，在图数据增强方面的工作研究相对较少。这种现象主要归因于图的复杂性和非欧几里得结构限制了可能的操作手段。本文系统探讨了图数据增强的实践、理论动机以及相关考虑因素和策略。研究表明，在A-style edge中发现了一种有效的编码机制来促进内部类边并降级类间边的能力。随后提出了GAUG（Graph Augmentation Framework），该框架能够显著提升基于图神经网络（GNN）架构的数据集性能。

Introduction

本文总结了现有三种图数据增强策略。
其中一种策略是DropEdge方法，在预测高置信度且具有相同标签的节点之间删除边；另一种策略是ADARdge方法，在预测高置信度但不同标签的节点之间添加边。
第三种策略是BGCN方法。该方法通过利用去噪后的图数据训练Assortative Mixed Membership Stochastic Block Model（AMEM），并集成多个GCN模型的结果。
本文探讨了如何通过去除噪声边以及补充原始图中缺失的关键连接来优化消息传播路径。
此外，该研究还分析了这种增强机制如何促进不同类群之间的信息交互。
实验结果表明，在不同网络拓扑结构下增加或删减关键连接能够显著提升模型性能。

具体而言，
黑色线条代表原始图的连通性特征；
纯蓝色线条对应新增的边；
虚线蓝色线条则标识删除的边。
（a）展示GCN在原始图上的性能；
（b）通过随机删除和添加边的方式导致性能下降；
采用GAUG增强方法©取得了显著的相对性能提升。
这里需要澄清的是，
"omniscient"一词的意思是指所有标签已知，
因此类内部通过添加边的方式形成了一个连通分量，
并通过尽可能减少类间无用边的数量，
从而实现了最高的准确率。
本文提出了两种不同的增强策略：
GAUG-M 和 GAUG-O。
其中，
GAUG-M 通过边缘预测器修改输入结构，
并使用修改后的结构进行训练；
而 GAUG-O 则是在输入数据的基础上添加可能的数据增强的操作，
并通过应用多个变换仅使用原始图来进行推理。
上图中的 M 和 O 分别代表了两种不同的架构设计。

Graph Data Augmentation via Edge Manipulation

本节将阐述图数据增强的基本原理及其相关理论基础。其主要目标是生成一个理想化的图结构G_i，在该图中添加必要的（原本缺失）连接的同时删除那些不相关或不必要的（原本存在的）连接。通过策略性地在同一个类别（类内）中的节点之间增加边，并相应地在不同类别（类间）之间的节点之间移除边，这种方法显著提升了该方法在节点分类测试中的性能。即使每个类别仅使用单个训练样本的情况下也能实现这一目标换句话说，在相同标签节点构成的一个连通分量内部具有高度的一致性这使得GCN卷积能够生成一致且独特的表示向量并与连通分量外部（它类）中的结点进行有效区分比较

该定理验证了本文所提出的理论框架。进一步阐述了在任意连通分量内部任意选取的两个节点i,j通过GNN模型处理后将拥有相同的特征表示。进一步阐述了来自不同连通分量的节点在权重矩阵W非零的情况下将无法实现特征的一致性。这一结论易于理解：由于不同连通分量内部的节点特征之间缺乏信息交互机制，在权重矩阵W非零的情况下也无法实现特征的一致性。

Proposed GAUG Framework

基于上述理论分析可知，在图数据增强过程中其核心概念在于基于图中固有的信息推断缺失边的可能性 同时通过识别和去除那些不符合合理性的边来优化模型

GAUG-M for Modified-Graph Setting

对于GAUG-M而言，在本研究中我们采用了边上概率预测机制来计算图G中存在的所有潜在边的概率值。基于这些预测得到的边概率值作为依据，在实际操作中我们可靠地增删新的（已存在的）边以生成修正后的子图G_m作为节点分类任务的输入。在本研究中我们采用图自动编码器（Graph Auto-Encoder, GAE）对原始图进行处理，并生成修正后的子图G_m。其中包含了两层GCN编码器以及内积解码器：

用符号|E|代表图中的总边数，在该算法中我们会引入不在原图中但其得分最高的前i|E|条具有最高概率的新边，并去除原图中得分最低、共计j|E|条已存在的旧边。

观察结果显示，在移除较少节点的情况下会使分类精度有所提升（c），而移除较多节点则会降低分类精度，在移除约20%节点时达到最佳效果。增加边的数量也会提高分类精度。相较于随机方法而言，在学习概率的基础上进行边的增删操作能够使类内边界变得更加分明（ac项），同时使类间边界增长较为平缓；另一方面，则会使类内边界下降低幅度（bd项），同时使类间边界下降更为剧烈。

GAUG-O for Original-Graph Setting

GAUG-O由三部分构成：首先是一个可微化的边缘预测器用于生成边缘概率估计；其第二部分是一个插值与采样的步骤负责生成稀疏图变量；此外是一个图神经网络（GNN）通过这些变量来学习节点嵌入并用于节点分类；整个模型采用端到端训练策略，并结合了节点分类损失和边缘预测损失

其中，在融合预测结果与原始图数据的基础上生成邻接矩阵P；遵循Gumbel分布形式的τ可视为该分布的一个温度调节参数；基于以下联合损失函数计算得到：

其中BCE/CE 表示 standard (binary) cross-entropy loss。

Evaluation

通过不同数据集的热力图分析可以看出，在所有数据集中添加边都是可行且具有正面效果的；相反地，在许多情况下不具备这种正面效果。最突出的例子是来自Flicker的数据集，在该集合中Red Temperature（RT）的效果最佳，在去除25%的数据后表现尤为突出。

并且如前所述（a）所示，在学习过程中边缘预测器增强了类内的边缘强度并减少了类间边缘。此外在损失函数方面表现出显著效果的是实验中采用的自监督学习框架。具体而言在训练初期阶段 L_{nc} 逐渐减小这有助于减少类别之间的相似度从而提高了验证集上的F1值同时观察到尽管 L_{ep} 有所上升但这种变化能够较好地平衡来自 L_{nc} 的影响最终实验结果表明即使是在标记样本很少的情况下该方法依然能够很好地平衡类别内部和外部的关系表现出了良好的泛化能力