NeurIPS 2021 | 图上不均衡表示学习新视野：基于拓扑结构的不均衡学习

论文标题：

Topology-Imbalance Learning for Semi-Supervised Node Classification

论文链接：

https://arxiv.org/abs/2110.04099

代码链接：

https://github.com/victorchen96/renode

稿件作者：

陈德里

论文作者：

陈德里，林衍凯，赵光香，任宣丞，李鹏，周杰，孙栩

论文机构：

微信AI & 北京大学

联系作者：

delichen@tencent.com

研究动机

类别不均衡（Class Imbalance）是真实场景中非常常见的问题，受到了学界和业界非常多的关注。一般在我们提及类别不均衡时，默认指的是数量不均衡：即不同类中训练样本数量的不一致带来的模型于不同类别学习能力的差异，由此引起的一个严重问题是模型的决策边界会主要由数量多的类来决定 [1] 。 

但是在图结构中，不同类别的训练样本不仅有在数量上的差异，也有在位置结构上的差异。这就使得图上的类别不均衡问题有了一个独特的来源：拓扑不均衡。而目前学界缺乏对于拓扑不均衡相关问题的研究。这个工作最主要的动机就是研究拓扑不均衡的特点，危害以及解决方法，希望能够引起社区对拓扑不均衡问题的重视。

▲ 图1 拓扑不均衡问题与ReNode方法

 

研究拓扑不均衡有哪些特点？为什么要研究它？

1. 拓扑不均衡广泛存在于节点分类中 

抽象于真实问题的图结构往往有着复杂的节点间连边关系，而不同类之间的拓扑结构往往是不对称的；而具体到节点分类任务中，标注（训练）节点在图上的分布也是不均匀的；这不对称且不均衡的特点使得不同类别的拓扑结构对于训练的影响是天然不同的，也使得拓扑不均衡问题天然存在于节点分类任务中。

2. 干拓扑不均衡扰图分类模型训练 

Message-Passing 是学习节点分类任务的最为重要而常见的方法，即标注节点沿着图中边将信息传递给无标注节点来进性节点表示学习。而 拓扑结构的不均匀就会导致信息传递中存在信息冲突（靠近类边界的节点）以及信息不足（远离信息源的节点）的问题，从而影响图模型训练（如图 1 左侧所示）。 

3. 缺少相关研究的解决方法 

拓扑不均衡是图结构中所特有的不均衡问题，而目前关于不均衡问题的研究集中在数量不均衡领域 [2][3][4] 。因此学如何深入认识拓扑不均衡问题以及设计相应的解决方法是亟待研究的课题。

拓扑不均衡与数量不均衡与哪些区别？

▲ 图2 图上不均衡问题的两个场景

拓扑不均衡问题独立于数量不均衡问题而存在：即使在数量均衡的设定中，非对称的拓扑结构也会造成模型学习的类别不均衡。也因为如此，数量不均衡的方法很难被迁移应用于解决拓扑不均衡的问题。

数量不均衡中，决策边界会主要由数量多的类别来决定；而在拓扑不均衡中，决策边界则主要由靠近图中类别边界的节点来决定。因此，数量不均衡的解决方法往往将同一个类的标注节点同等对待，并基于类别整体标注数量设计方法（例如 re-sampling 以及 re-weighting）。而拓扑不均衡问题中，我们更加关注每个标注节点在拓扑结构中独特的位置以及对模型训练产生的作用。

在图 2 中我们展示了图中两种不同的不均衡问题：1）左图是在随机采样的情况下，图中同时存在数量不均衡和拓扑不均衡的问题，模型的决策边界（黄线）向少数类偏移；2）右图是在类别数量均匀采样的情况下，图中依然存在拓扑不均衡的问题，此时模型的决策边界向多数类偏移。

怎么量化拓扑不均衡问题？

和数量不均衡问题存在类别标注数量这个直接的量化指标不同，虽然我们能确实感受到类别在其拓扑结构上的差异，但是如何对这一概念进行抽象和量化却是挺棘手的问题。

在这个工作中，我们分析指出拓扑不均衡的主要现象是靠近边界的类别节点引起的决策边界偏移，因此我们首先将拓扑不均衡问题抽象为标注节点到类边界的距离差异。之后我们设计了基于节点影响力冲突检测的拓扑不均衡量化指标 Totoro。其主要思想在于：如果标注节点 v 在其本身有着比较大影响力的子图上遇到了比较强的影响力冲突，我们认为节点 v 是更加靠近类别边界的节点。

▲ 图3 Totoro指标对Node-Level和Graph-Level的拓扑不均衡问题体现

在图 3（左）中，我们展示了 t-SNE 降维的图节点在二维上的分布（不同颜色代表不同的类别，五角星的颜色深浅代表其 Totoro 值的大小），可以看出越是远离边界的标注节点 Totoro 值越小，而越是靠近边界的标注节点的 Totoro 值越大。

在图 3（右）中，我们展示了标注集合整体的拓扑冲突水平和模型表现的关系，可以看出两者存在显著的相关关系。这说明了 Totoro 指标能有效的反映图上的拓扑不均衡程度。

怎么来解决拓扑不均衡问题？

在设计拓扑不均衡方法之前，我们首先在思考拓扑不均衡的解决方法应该满足什么要求？考虑到拓扑不均衡问题的普遍性，以及现有的 GNN 模型缺乏对其的特殊设计和考虑，解决方案应该尽可能的兼容众多已有的 GNN 结构。同时针对于拓扑不均衡的方法应该尽可能和已有的数量不均衡方法兼容，从而更加全面完整的解决图上不均衡问题。此外，所设计的方法给模型训练带来的额外开销应该尽可能小，并能够适用于几百万节点的超大规模图结构。

基于这些考虑，我们提出了用于解决拓扑不均衡问题的 ReNode 框架（如图 1 所示）。整个框架包括两个步骤： 

1. 标注节点的拓扑定位： 计算节点到类边界的远近（Totoro 指标）； 

2. 标注节点训练权重 Re-Weight： 减少靠近类边界节点的训练权重，增加靠近类中心节点的训练权重。

ReNode 是基于每个标注节点到其类边界的距离的远近进行 instance-level 的重新加权。通过 ReNode 方法，靠近类别边界位置的、容易引起决策边界偏移的训练节点的权重被减少，而靠近类别中心位置的训练节点权重增大。这就使得节点的影响力边界和真实的类别边界更加重合，减少了因为拓扑结构不均衡引起的决策边界偏移问题。

我们的方法效果如何？

对应于上一节中我们关于拓扑不均衡的解决方法应该满足什么要求的思考，我们在三个不同的场景中验证了 ReNode 方法的有效性：

1. 拓扑不均衡，数量均衡

 

▲ 表1 拓扑不均衡-数量均衡设定下实验结果

这里选用了 GCN, GAT, PPNP, GRAPHSAGE, Cheb GCN, SGC 等六个常用的图神经网络作为 backbone 模型，对比了是否使用 ReNode 方法情况下模型训练效果；在 CORA 等 5 个 benchmark 数据集上，ReNode 方法能够有效地缓解拓扑不均衡问题并提升模型的训练效果。

2. 拓扑不均衡，数量不均衡

▲ 表2 拓扑不均衡，数量不均衡下的实验结果

这个实验设定标注结合同时为拓扑不均衡和数量不均衡（imbalance ratio=5/10）。实验结果表明，我们的方法能够很好地和数量不均衡的方法结合（Re-weight, Focal Loss, Class-Balanced Loss），从而更加全面地解决图上拓扑不均衡的问题。

3. 超大图场景

▲ 图4 超大图上的实验结果

在两个大规模的图数据中展开实验：社交网络 Reddit 以及引用网络 MAG-Scholar（千万节点），这里我们同样设定了只有拓扑不均衡的场景，已经拓扑不均衡和数量不均衡的综合场景。结果验证了我们的方法对于超大图上的拓扑不均衡问题的解决能力。

关于拓扑不均衡有哪些亟待研究的问题？

在做这个工作的过程中，我越发认识到了拓扑不均衡给图结构相关任务带来的威胁以及问题本身的复杂性，还有许许多多工作要做来更进一步地认识和解决这一问题。 

这里我整理了一些未来可以考虑做的问题和方向，可能有不成熟之处，就当抛砖引玉，希望大家能有更好的想法。 

1. 设计更有效的解决节点分类中拓扑不均衡的方法 

ReNode 方法在标注比例低和图连通性差的场景中效果不明显，克服这些问题能够更好地解决拓扑不均衡这一问题。 

2. 考虑特殊领域中拓扑不均衡问题的特点和解法 

在分子医药，交通运输等特殊应用场景中考虑拓扑不均衡问题有哪些不同的特点，并设计相应的解决方法。 

3. 在更一般的前提下考虑拓扑不均衡问题  

这篇工作的部分结论只在同质连边的图中成立，未来工作可以考虑更一般的场景：例如从同质连边到异质连边，从同构图到异构图等等。 

4. 研究其他图结构相关任务中的拓扑不均衡问题  

虽然这篇工作基于图节点分类展开，但是拓扑结构不平衡问题广泛存在于图相关的任务中并值得关注。例如和节点分类紧密相关的链接预测任务，拓扑不均衡直接影响着节点表示学习的质量从而影响链接预测的准确性，因此也可以从解决拓扑不均衡出发也是提升连接预测任务的效果。

再如主动学习（active learning），我们的 ReNode 方法是在给定了标注节点后去在学习中缓解拓扑不均衡带来的影响。而换个思路，从主动学习的角度出发，我们是否能够在标注节点学习阶段通过主动学习的方法来获取一个拓扑相对均衡的标注数据集呢？ 

总结来看，关于拓扑不均衡还有很多有趣的可以研究的方向，欢迎大家就相关研究问题进行讨论！

路漫漫而修远兮，与诸君共勉~

参考文献

[1] Rethinking the Value of Labels for Improving Class-Imbalanced Learning 

[2] RA-GCN: Graph Convolutional Network for Disease Prediction Problems with Imbalanced Data 

[3] Multi-Class Imbalanced Graph Convolutional Network Learning 

[4] GraphSMOTE: Imbalanced Node Classifi- cation on Graphs with Graph Neural Networks