GNN 2021(六) GraphSMOTE: Imbalanced Node Classification on Graphs with Graph Neural Networks，WSDM

在面对样本不均衡的问题时, 通过有目的地增加少数类别的数量或生成新的合成实例来平衡各类别的代表性. 然而,MOTE算法无法为新增实例提供与原有数据相关联的关系信息, 这对于图神经网络的学习至关重要. 此外, 节点属性通常表现为高维特征向量. 将过采样操作直接施加于原始数据空间可能导致测试集与训练集之间存在分布偏移. 为此我们提出了一个新的框架GraphSMOTE, 在其中构造一个嵌入空间用于捕捉节点间的相似性. 这一过程确保了新增实例的真实性. 同时, 我们还训练了一个边生成器来建模节点间的关系, 并赋予新增实例相应的连接信息. 这种通用的设计方案能够轻易扩展到多种变体形式.

INTRODUCTION

在机器学习领域，传统的类不平衡问题引起了学术界的广泛关注。研究算法可归纳为三类:数据级策略通常采用过采样或下采样的方法来平衡类别分布；其中一种是算法级方法；另一种是基于模型的方法；还有一种则是混合策略结合了前两者的优势。

这是因为图数据中的关系信息对于提升嵌入质量至关重要；此外，少数样本的信息不足以支持有效的知识传播过程

• 针对图上学习中的节点级不平衡现象提出了新方法。
• 我们的创新性解决方案不仅扩展了传统的过采样算法，在图数据处理方面也展现出显著优势。
• 通过系统性的实验研究，在多个公开可用的数据集上进行了全面评估。
• 结果显示GraphSMOTE在多个数据集上展现出显著优势。
• 进一步深入探讨了其具体运作机制及其适用范围。

METHODOLOGY

首先需要明确一个定义：imbalance ratio ：

该指标用于评估类别间的不平衡程度。其中|C_i|代表某一类别的样本数量。然而在原论文中提到的相关公式可能存在表述不当的情况。其中不平衡度应为各类别中最小的训练样本数量与最大节点数之比。

GraphSMOTE由四个关键模块构成：(i)一种基于图神经网络（GNN）的特征提取模块（编码器），该模块负责从原始数据中学习有效的节点表示，并同时保留原始数据中各节点属性及其全局拓扑关系；(ii)一种用于在潜在空间中生成少量合成样本的新样本生成模块；(iii)一种边预测模块，在此过程中建立新的样本与扩展后的平衡类别数据集之间的关联；(iv)一种基于GNN的设计分类模型，在经过人工强化后的数据集上完成对各个样本类别归属性的判定任务。进一步说明每个模块的工作原理

Feature Extractor

对于单纯的SMOTE方法而言，在实际应用中存在两大问题：其一是在高维稀疏特征空间中难以获取具有相同属性且相近邻接关系的节点用于插值；其二是忽略了图数据特有的结构性信息而导致生成效果欠佳。基于此，在分析现有技术时发现现有改进方法往往难以有效平衡多个关键指标之间的制约关系。针对该研究目标我们选择GNN模型作为核心算法框架并设计了一种基于双重损失函数的新方法以期达到预期性能提升效果

在获得特征提取器构建的嵌入场域中每个节点的表示后，在此基础之上我们能够实施过采样操作以生成来自少数类的新样本的理想表示

Synthetic Node Generation

SMOTE算法的基本思想是通过在目标少数类样本之间构建插值关系，并在此基础上寻找与其所属类别中的其他样本相邻的空间位置。该方法特别适用于处理类别不平衡问题，在嵌入空间中实现数据分布的均衡化处理。

h_v^1代表少样本节点的特征；
该算法通过寻找与节点v同一类中的最近标记节点；
通过插值方法结合这两个节点的特征来生成新的样本。

Edge Generator

该模型被训练于真实存在的节点及其连接上，并用于推断合成节点所拥有的邻居信息。新增加的节点及其连接将被整合进初始邻接矩阵A中，并作为基于图神经网络构建的数据输入。

E_{v,u}就是边的预测器了，S是一个参数矩阵。预测器需要优化一个损失函数：

借助边生成器这一工具技术手段，我们实施了两项策略方案，并将其预测连接关系嵌入到扩展邻接矩阵中。其中一项采用二进制表示法。

也就是说，在给定的预测器中设置一个阈值η。当预测的概率超过该阈值时保留生成的边；反之则舍弃。第二种方法则是针对合成节点v'而言，在其中使用软边来代替传统的二进制边。

GNN Classifier

对于已经生成节点和边的新的图，使用GNN进行分类，其过程概述为：

其中\tilde A, \tilde H分别是增广的邻接矩阵和特征，损失函数定义为：

softmax之后输出预测值：

最终的损失函数为联合损失：

算法总体的流程如下：

EXPERIMENTS

Experimental Settings

因为和以往的节点分类任务稍微有所不同，所以介绍一下设置。

Cora系统中采用了一种借鉴真实网络拓扑特性的无标度网络生成模型，并在此基础上构建了其扩展版本Corrastd系统。通过在Corrastd系统中引入异构信息增强机制和多层注意力机制来提升系统的性能表现。
在实验部分中：

• 对于Cora数据集而言，在分类任务中涉及的14个小规模类别和8个大规模类别。
• 在BlogCatalog数据集上，则采用了更加激进的不平衡分布设定：共有27个小规模类别（每个小规模类别的样本数量均不超过50）以及69个大规模类别（每个大规模类别的样本数量均超过50）。
• 通过Deepwalk算法提取节点嵌入特征，并附加节点度特征以增强模型表现能力。
• 该研究系统被用于二进制分类任务中的过采样问题研究，在实验过程中分别采用了四种不同的过采样策略。

• GraphSMOTE_T。仅基于边缘预测任务中的损失对边缘生成器进行训练，并将预测出的边设定为带阈值的二值化结果后传递至图神经网络分类器。
• GraphSMOTE_O。通过将预测边设定为连续值以确保梯度能够从图神经网络分类器中有效计算与传播，并主要依赖于两个分支任务（即边生成与节点分类）联合优化的方法。
• GraphSMOTE_preT。在图链接预测任务下对特征提取器与边缘生成器实施预训练步骤，并在后续节点分类等下游应用中采用L_{edges}损失函数进行微调优化。
• GraphSMOTE_preO。类似地，在上述基础上针对损失函数优化方法展开进一步改进与扩展。

Results

大多数GraphSMOTE变体展现出更优的效果。在不同版本的GraphSMOTE方法中，经过训练后的模型在性能上优于未经训练版本。这一发现表明，在构建有效的嵌入空间时，样本间的相似性得到充分地捕捉和利用。

Influence of Over-sampling Scale

研究了多种算法在不同过采样比例下的性能变化情况。基于Cora数据集，在将不平衡率设定为固定值0.5的情况下，分析了不同的过采样策略及其对模型的影响。研究采用了{[over_sampling_ratio]: 0.2, 0.4, 6/1o=}, 1/2}这一系列设置，并确保每个设置均重复运行3次以获得稳定的统计结果。通过对比实验发现：当设置的过采样比例低于等于0．8时，在保持少数类样本数量的同时增加其数量有助于提升模型预测能力；而随着设置的过采样比例增大（如超过等于1．O），虽然偶尔仍能观察到微小的提升效果（如表2所示），但进一步提高可能会导致效果逆转。这种现象的主要原因在于，在生成大量合成节点的过程中可能出现了一些冗余信息（即合成节点之间存在高度相似性），这些信息无法有效补充现有知识以进一步优化模型表现

Influence of Imbalance Ratio

当数据集的不平衡程度达到一定程度时，GraphSMOTE算法在性能上表现出更强的优势；当数据集严重失衡至极限水平时，预训练的作用变得尤为突出。

Influence of Base Model

在GCN上使用本模型，之前都是基于GraphSAGE的。

通常情况下, GraphSMOTE算法能够有效支持基于GCN的模型应用。该算法的四种变体均表现出色,并在表3中取得了最优性能。相较于基于GraphSage的方法, 该算法的主要区别在于无需额外重视其预训练需求。我们推测其原因可能在于GCN在表征能力上相对不及GraphSage. 比较而言, GraphSage更具灵活性, 具备对更为复杂的关联关系进行建模的能力. 因此, 提前建立一个性能优良的嵌入空间将有助于提升该算法的整体效能.

Parameter Sensitivity Analysis of \lambda

随着λ的增加, 模型呈现出先上升后下降的趋势, 当λ过大时, 则会导致显著的性能下降。经过预训练过程, GraphSMOTE算法表现得更加稳定可靠。