https://arxiv.org/pdf/2006.06830

https://github.com/zhao-tong/GAug

Data Augmentation for Graph Neural Networks ，2021，AAAI

总结：和CV、NLP中的数据增强不同，通过Edge Manipulation进行图数据增强，提出了GAUG框架。具体来说删去图中可能是噪声的边，增加图中可能丢失的边（对模型有益），其实可以看做是一个降噪和补全的过程（不知道其他图数据增强技术是不是有其他增强方法）。另外GAUG的动机和本质是：增加同类别节点之间的边，去掉不同类别节点之间的边，这在异构图中是不成立的，因此无法用于异构图学习。不过可以考虑是否可以将数据增强方法用于小样本图学习中。

1. 简介

1.1 摘要

Data augmentation has been widely used to improve gener-alizability of machine learning models. However, compara-tively little work studies data augmentation for graphs. Thisis largely due to the complex, non-Euclidean structure ofgraphs, which limits possible manipulation operations. Aug-mentation operations commonly used in vision and languagehave no analogs for graphs. Our work studies graph dataaugmentation for graph neural networks (GNNs) in the con-text of improving semi-supervised node-classification. Wediscuss practical and theoretical motivations, considerationsand strategies for graph data augmentation. Our work showsthat neural edge predictors can effectively encode class-homophilic structure to promote intra-class edges and de-mote inter-class edges in given graph structure, and our maincontribution introduces the GAUGgraph data augmentationframework, which leverages these insights to improve per-formance in GNN-based node classification via edge predic-tion. Extensive experiments on multiple benchmarks showthat augmentation via GAUGimproves performance acrossGNN architectures and datasets.

数据增强已经被广泛用于给中机器学习模型，但是在图学习领域很少有关于数据增强的研究。因为在图这种非欧式结构数据十分复杂，不能直接将CV和NLP中的数据增强技术迁移到图中。本文我们研究图数据增强技术，用于GNNs中来提高半监督节点分类的性能。我们从理论和实际两个方面分析了我们的动机和策略。我们的工作表明神经边预测器能够有效编码class-homophilic结构，增加intra-class边，减少inter-class边。本文我们主要的贡献是提出了GAUG图数据增强框架，通过预测边，提高GNN-based模型的节点分类性能。多个数据集上的大量实验表明，通过GAUG进行数据增强可以提高GNN的性能。

1.2 本文工作

数据增强技术被广泛用于CV和NLP领域，可以增加模型泛化能力，更加关注信号本身而非噪声。但是在图学习领域，很少有工作将GNNs和数据增强结合到一起，因为图的结构很复杂，难以将CV和NLP中的数据增强技术迁移过来。

在图中作数据增强，显然只能添加或删除节点或者边，但是在节点分类任务中添加或删除节点显然是不现实的，因此只能增删一些边。

本文作者采取的数据增强策略为：利用消息传播（GNNs），删除“noisy”边，增加“missing”边。

上图展示了使用作者提出的数据增强方法后，模型分类性能得到了显著提高。其中a图为未使用数据增强，b图为随机增减边，c图为使用作者提出的GAUG方法，d表示上帝视角。图中的M和O分别表示GAUG的两种模式，下文中会介绍。

1.3 动机

实际：

现实世界中的图很容易受到noise影响，这回导致我们得到的图和ideal graph存在gap。上面图1展示了，通过增加同类别节点之间的边（intra-class），删减不同类别节点之间的边(inter-class)可以有效提高模型性能。直觉上来说，这种操作鼓励同类别节点之间的嵌入更加平滑（趋同），并区别与其他类节点嵌入，提高区别性（因为GNNs本质是消息传播，同类别节点之间边增多，不同类别节点之间边减少，会导致同类别节点之间学习到的嵌入更加平滑，可以参考热传播模型）。

理论：

考虑理想状态下，图中只有同类别节点之间存在边，假设有节点类型有k个，那么图天然的就被分成了k份，GNNs准确完成节点分类。因为，此时对于相同类型节点，GNNs学到的节点嵌入是完全相同的，不同类型节点GNNs学习到的嵌入一定是不同的（文章中有关于该定理的证明）。

2. 方法

CV中的数据增强方法通常分成两个步骤：（1）transformation，$\mathcal{f:S\rightarrow T}$，生成输入图像$\mathcal{S}$的变体$\mathcal T$；（2）用$\mathcal {S\cup T}$训练模型。但是图数据的增强有所不同，因为CV中图像数量$|S|>>1$，而图数据中$|S|=1$。

本文作者提出两种策略GAUG-M和GAUG-O：

• GAUG-M：通过图转换操作$\mathcal {f:\mathcal G\rightarrow G_m}$生成新图$\mathcal G_m$，$\mathcal G$在training和inference阶段都用$\mathcal G_m$替代。
• GAUG-O：执行多个transformation $f_i:\mathcal{G\rightarrow G_m^i}, i=1...N$，$\mathcal{G\cup\{G_m^i\}_{i=1}^N}$用于训练，$\mathcal G$用于inference。

在训练和测试阶段图不改变的情况下可以采用GAUG-M策略，但是在测试阶段图会发生改变的情况下只能用GAUG-O策略。在实际应用中，这两种策略其实是和transductive、inductive相对应的。

2.1 GAUG-M

GAUG-M包含两个步骤：

• 使用edge predictor，计算所有节点之间存在边的概率
• 利用第一步得到的概率，对原有图中的边进行增加和删减，生成修改后的图$\mathcal G_m$

所以，整个方法的关键其实就是edge predictor $f_ep:A,X\rightarrow M$的定义。以原始图为输入，输出概率矩阵$M$，$M_{uv}$表示节点u和v之间存在边的概率。

本文作者采用GAE作为edge predictor，它包含两个GCN层（encoder）和一个内积层（decoder）：

$\mathbf{M}=\sigma\left(\mathbf{Z} \mathbf{Z}^{T}\right), \text { where } \mathbf{Z}=f_{G C L}^{(1)}\left(\mathbf{A}, f_{G C L}^{(0)}(\mathbf{A}, \mathbf{X})\right)\tag 2$

其中$\mathbf Z$表示编码后的hidden embedding，$\mathbf M$表示输出的概率矩阵，$\sigma(·)$表示element-wise激活函数。

上图展示了使用GAUG-M进行数据增强后，图中inter-class和intra-class边数量的变化情况。可以看到使用GAUG-M后，intra-class边的数量增加的快，减少的慢，而inter-class边的数量增加的慢，减少的快。对比图右边随机增减边，模型性能有显著提高。

2.2 GAUG-O

GAUG-O不需要单独训练edge predictor，可以end-to-end训练。下图展示了GAUG-O的运行过程：

这里作者同样采用GAE作为edge predictor。

（1） 首先利用GAE对原始图$\mathcal G$进行调整得到$\mathcal G_m$；

（2） 然后将调整后的邻接矩阵和原始邻接矩阵采用加权的方式合并到一起；

（3） 再进行伯努利边稀疏化得到最终的邻接矩阵$A'$；

（4） 最后通过GNN节点分类器进行节点分类。

具体计算公式如下：

$\begin{array}{l} \mathbf{A}_{i j}^{\prime}=\left\lfloor\frac{1}{1+e^{-\left(\log \mathbf{P}_{i j}+G\right) / \tau}}+\frac{1}{2}\right\rfloor \\ \text { where } \mathbf{P}_{i j}=\alpha \mathbf{M}_{i j}+(1-\alpha) \mathbf{A}_{i j} \end{array}\tag 3$

其中$A'$为最终采样后的邻接矩阵，$\tau$为Gumbel-softmax分布的temperature，$G\sim Gumbel(0,1)$为Gumbel随机变量，$\alpha$为超参。得到$A'$后，再结合节点特征$X$，利用节点分类器进行分类，分类损失为：

$\begin{aligned} & \mathcal{L}=\mathcal{L}_{n c}+\beta \mathcal{L}_{c p}, \\ \text { where } & \mathcal{L}_{n c}=C E(\hat{\mathbf{y}}, \mathbf{y}) \\ \text { and } & \mathcal{L}_{e p}=B C E\left(\sigma\left(f_{e p}(\mathbf{A}, \mathbf{X})\right), \mathbf{A}\right) \end{aligned}$

前者$L_{nc}$为分类损失，后者$L_{cp}$为边预测损失，$\sigma(·)$为element-wise sigmoid，$CE$和$BCE$为交叉熵损失。

3. 实验

采用的六个数据集如下表所示：

baseline采用：ADAEDGE，BGCN，DROPEDGE

一、对比实验

经过GAUG-M和GAUG-O数据增强后，四种GNN模型性能得到显著提高。

二、增删比例

上图展示了不同增删比率下模型性能，横轴表示增加比例，纵轴表示删除比例，red-white-blue点分别表示outperformance，at-par和underperformance。

三、训练过程

图5a中展示了GAUG-O让增加了图中intra-class边的比例，降低了inter-class边的比例。图5b中展示了训练过程中两种损失的变化情况，可以发现在刚开始几个epoch，$\mathcal L_{nc}$逐渐降低，$F1$逐渐增大，但是$\mathcal L_{ep}$逐渐增大，调和了$\mathcal L_{nc}$的监督效果。之后$L_{nc}$继续减小，intra-class边比率还在增加，出现过拟合。

四、监督程度敏感性

上图展示了不同数目节点用于训练情况下各个模型性能。可以看到在弱监督情况下，GAUG可以显著提高GNNs模型性能。

原文附录中还提供了了非常多的补充实验，感兴趣可以参见原文附录。