ICLR 2022 | GraphENS：用于类别不平衡节点分类的邻居感知自我网络生成

©作者 |  陈景岩

单位 |  南京大学

研究方向 |  图神经网络

论文标题：

GraphENS: Neighbor-Aware Ego Network Synthesis for Class-Imbalanced Node Classification 

论文链接：

https://openreview.net/forum?id=MXEl7i-iru

这是一篇针对类别不平衡问题的数据生成文章。

Abstract

在不平衡分类任务中，由于 GNN 中的消息传递，相比于过拟合少类节点而言，GNN 会对少类节点的邻居过拟合更加严重（本文的新观点）。

针对上述问题作者提出了一种数据生成的方法 GraphENS，其基本步骤是选择一个少类节点 ，和一个其他类的节点 ，根据这两个节点生成一个 节点。同时，根据两个母节点的 ego network 之间的相似性为 节点设计一种邻居采样方法。

本文的主要贡献有：

• 展示并说明了 GNN 会对少类节点的邻居出现严重的过拟合，这种现象称为 neighbor memorization。少类节点越少，这种现象就越严重。

• 根据两个母节点的 ego network 为新节点生成邻居，缓解了 neighbor memorization。此外在 的生成过程中，根据节点特征的显著性防止了有害的特征注入到 中。
• 在不平衡的数据集上做实验，效果超过了许多 baselines。

Neighbor Memorization

本节作者展示了 Neighbor Memorization，通过实验说明了 GNN 对邻居的过拟合要比对少类节点本身的过拟合更严重。

1.1 Overfitting to minor classes

作者首先研究了对少类节点本身的过拟合问题，在数据集 PubMed 上构造了不平衡率为 100 的数据（多类/少类 = 100），采用两层 256-dim 的 GraphSAGE 训练了 2000 个 epoch，得到了以下结果：

实线是少类样本的 Acc，虚线是整体的 Acc。对比 Train 和 Test 可以看出，现有针对不平衡的方法对少样本有严重的过拟合问题，而 GraphENS 对此有缓解。

下一节作者将验证这到底是因为 GNN 对少类节点本身的特征过拟合，还是对其邻居结点过拟合。

1.2 Neighbor memorization problem

作者在此采用了两组置换实验对比验证。

1.2.1 Node replacing experiment

▲ Seen节点来自训练集，Unseen节点来自测试集

作者首先在训练集中选择一个替换节点 ，再分别在训练集和测试集中采样节点 、 、 作为提供特征的节点。将二者的特征分别换给 ，并统计其分类准确度。 提供的特征作为对照组。

这个实验相当于把不同的特征换到相同的邻居环境下，看看在邻居结构不变的情况下，改变中心节点的特征对分类效果的影响。

1.2.2 Node replacing experiment

这里的采样和 1 中类似，但这里是把一个节点分别换到了两个邻居结构中，再统计节点的分类效果。换到 的邻居中作为对照组。

这个实验相当于把一个节点换到不同的邻居环境下，看在节点本身特征不变的情况下，改变邻居环境对分类效果的影响。

上述两个实验结果为：

▲ RW:re-weight，OS：over sampling

对比两张图相同位置下的红色柱可以发现，更换邻居环境后，分类效果比更换节点特征差很多。由此作者论证了 neighbor memorization 对分类效果的影响。

GraphENS

GraohENS 包括两部分：

• 选择两个母节点 、 ，用于后续的节点 的生成和邻居选择；
• 根据两个母节点的 ego network 相似性，为 生成邻居采样概率，并进行邻居采样；
• 根据节点的特征显著性，为 进行特征生成。

2.1 Neighbor Sampling

这一步是从两个母节点的邻居中，根据 ego network 的相似性为邻居结点生成一个采样概率，并通过采样确定 的邻居节点。ego network 就是指节点和一阶邻居组成的小网络。

首先，构造两个母节点的 Logits：

随后，根据两个节点的 KL 散度衡量两个 ego network 的相似度：

最后为每个节点生成一个采样概率：

这里的   注意到 ，因此 。也就是 的邻居节点不会太靠近 。 同时 随 KL 散度增大而增大，也就是如果 和 的邻居差距越大，采样的邻居越靠近 。

邻居节点的采样数量由图中节点度数的分布决定（比如统计均值），以保证节点度数的稳定。

2.2 Saliency-based Node Mixing

本节作者构建了一个基于特征显著性的节点混合策略，用于生成 。

Feature Saliency

在此，作者通过损失函数的反向传播确定特征的显著性，具体而言对于节点 v，其第 i 维特征的显著性为：

一个直观的解释是，损失对 X 的偏导刻画了变量的轻微变化对损失的影响大小，因此如果数值越大，则认为该特征越具有显著性。节点 v 的显著性向量为： 。

Node mixup

其中 ，是一个超参数。 ，是一个 mask vector，用于抹去 里 K% 的特征（设置为 0）。其中 k 是超参数：

哪些位置被抹去，由一个概率分布 决定。按照这个概率采样，将 K% 的位置抹去为 0。

注意这里，节点混合的出发点是，我们想生成靠近少样本的数据点（解决不平衡），同时添加适当的噪音。因此 如果 和 差距较大，应该多保留 的特征。同时对于 里较为显著的特征（较强的噪音），也应该抹去（越显著，其被采样的概率越大）。

Experiments

• w/o PS：把邻居相似度用随机值代替
• w/o SM：去掉节点特征显著性，置  
• w/o SM,NS：去掉节点特征显著性，同时把 的邻居置为和 相同

接下来作者对比了 来自于所有类，以及只来自于一类的实验效果：

实验表明从所有类中随机选择更有利于模型效果。

类别的选择依据概率分布 ，选择一类后，等概率从类别中随机选择一个节点作为 。

Whole Algorithm

更多阅读

#投 稿 通 道#

 让你的文字被更多人看到 

如何才能让更多的优质内容以更短路径到达读者群体，缩短读者寻找优质内容的成本呢？答案就是：你不认识的人。

总有一些你不认识的人，知道你想知道的东西。PaperWeekly 或许可以成为一座桥梁，促使不同背景、不同方向的学者和学术灵感相互碰撞，迸发出更多的可能性。 

PaperWeekly 鼓励高校实验室或个人，在我们的平台上分享各类优质内容，可以是最新论文解读，也可以是学术热点剖析、科研心得或竞赛经验讲解等。我们的目的只有一个，让知识真正流动起来。

📝 稿件基本要求：

• 文章确系个人原创作品，未曾在公开渠道发表，如为其他平台已发表或待发表的文章，请明确标注 

• 稿件建议以 markdown 格式撰写，文中配图以附件形式发送，要求图片清晰，无版权问题

• PaperWeekly 尊重原作者署名权，并将为每篇被采纳的原创首发稿件，提供业内具有竞争力稿酬，具体依据文章阅读量和文章质量阶梯制结算

📬 投稿通道：

• 投稿邮箱：hr@paperweekly.site 

• 来稿请备注即时联系方式（微信），以便我们在稿件选用的第一时间联系作者

• 您也可以直接添加小编微信（pwbot02）快速投稿，备注：姓名-投稿

△长按添加PaperWeekly小编

🔍

现在，在「知乎」也能找到我们了

进入知乎首页搜索「PaperWeekly」

点击「关注」订阅我们的专栏吧

·

·