GraphSMOTE

GraphSMOTE: Imbalanced Node Classification on Graphs with Graph Neural Networks

1. motivation: 样本不平衡是机器学习中常见的问题，有 合成少数过采样技术（SMOTE） 可以解决，但是将 SMOTE 存在两个问题：一是直接插值合成的新的节点需要与原图构造边相连，这可能破坏图结构；二是对于图结构数据而言，少数类样本的特征空间往往非常稀疏，直接在原始的特征空间执行 SMOTE 很容易产生域外样本（噪音），破坏图特征；因此作者希望将 SMOTE 技术应用到图上，同时解决上述两个问题

2. 主要数据增强方法: 通过特征提取的方法完善节点插入时的拓扑结构

   • feature extractor：这一步其实是node embedding的过程，作者认为原始特征高维稀疏难处理，因此先通过一个 GNN 进行node embdding的操作转为低维稠密的特征，使得后续合成节点时在域内的可信度提升

   • synthetic node generation：作者采用 SMOTE 对少数类样本及其最近邻域样本进行插值来合成新的样本（即**node insertion**）做法是找到取一个少样本类别的节点，在他领域内找另外一个标签一样的，然后进行embedding后的feature插值 \(\mathbf{h}_{v^\prime} = (1 - \delta)\cdot \mathbf{h}_v + \delta\cdot\mathbf{h}_{nn(v)}\)

   • edge generator：从原图（还没有插值前的）训练一个边预测器，输入为低维embedding；目标：\(\mathcal{L} = \parallel E - A\parallel\) 即预测的结果要和原图的结构尽可能相近；之后用该边预测器连接上一步插入的新节点

   • 最后输入到一个 GNNs 分类器

   • loss: \(\mathcal{L} = \mathcal{L}_{\text{node} } + \lambda \mathcal{L}_{\text{edge} }\) 前者是最后分类器的loss，后者是边预测器的loss

3. 方法评价：将SMOTE应用到图领域，缓解了样本不平衡的问题，通过对少样本类别插入新节点并重构图（可以看作data augmentation）来实现GNN 分类的效果提升，但是只使用了相同子类的节点进行新节点插入生成，对节点特征的多样性有影响；可以应用于样本不平衡的图数据，例如僵尸用户的检测等任务上。