ICML 2022 | TAM: Topology-Aware Margin Loss for Class-Imbalanced Node Classification
“文章信息
来源：Proceedings of the 39th International Conference on Machine Learning（ICML） 2022
”
标题：TAM: Topology-Aware Margin Loss for Class-Imbalanced Node Classification
作者：Jaeyun Song, Joonhyung Park, Eunho Yang
链接：https://proceedings.mlr.press/v162/song22a.html
内容简介
图神经网络 (GNN) 被广泛用于处理图结构数据，并在各个领域取得了显著成功。然而，由于自然图本身可能是类别不平衡的，因此GNN的处理结果容易偏向体量比较大的类别。在存在类别不平衡的情况下从这些图中学习会导致小体量的类别准确性低。
现有的解决方案大多是对小体量类别进行补偿，但是这会明显影响到某些节点对其他类别的性能。针对现有方案的不足，本文提出了拓扑感知边际(Topology-Aware Margin，TAM)，这是一种基于节点的logit调整方法，它在类对连通性和邻节点分布统计方面考虑了它们的局部拓扑。
该方案的关键原则如下：如果考虑到其局部拓扑，一个（次要）节点很可能与特定（主要）类混淆，应该减少这些（主要）类的边距，以便可以更加准确地训练GNN（通俗地说，当某个次要节点的主要邻节点特别多时，需要降低其权重）。为此，本文设计了异常连接感知边距（Anomalous Connectivity-aware Margin，ACM），如果该目标类的邻节点密度相对较高，则该节点的目标类边距会降低。同时，本文引入了异常分布感知边距（Anomalous Distribution-aware Margin，ADM），它根据目标类的平均邻节点统计量计算混淆程度，并额外调整目标类的边距。
本文的主要贡献如下：
本文假设并确认由于补偿次要节点导致的误报不会均匀地出现在图上，并且明显受到每个节点周围的邻节点标签分布的影响。具体来说，本文证明了在与主要节点具有较高连接性的次要节点周围出现了明显的高误报率。 本文针对这一假设提出了一个定制化解决方案，与类统计相比，可以通过基于节点拓扑单独调整补偿程度来有效减少过多的误报。 本文的方法可以与现有的类别不平衡处理方法相结合。当与本文的方法结合使用时，基线可以持续提高多个基准数据集的类别不平衡处理性能。
异常连通性分析
本文的主要研究假设是在基于数量的补偿过程中，偏离连接模式的次要节点会导致过多的误报。为了从经验上验证假设，本文研究了次要类上误报的拓扑位置。
实验设计
定义异常连接的节点集
计算比率，表示当主要节点与异常次要节点连接时误报的概率
结果分析
本文将计算的概率与比率 进行比较，得出误报的平均概率，如下图中的次要:
方案介绍
该研究设计了 TAM 的两个核心组件。
Anomalous Connectivity-Aware Margin，ACM
如果邻节点标签分布（NLD）中目标节点类的部分大于类平均连通性，则异常连通性边际 (ACM) 会降低目标节点（相邻节点之一）的类边际Anomalous Distribution-Aware Margin，ADM
异常分布感知边距（ADM）根据使用目标类平均 NLD 和自身类平均 NLD计算的相对距离调整边距。
Anomalous Connectivity-Aware Margin，ACM
为了抑制异常连接节点引起的误报，ACM通过校准（节点 的NLD）的偏差来修改每个类的边距（类 的连接模式）。类 上节点 的 ACM 导出为：
请注意，其自身类的余量通过上述等式被设置为0。
Anomalous Distribution-Aware Margin，ADM
尽管 ACM 可以识别偏离连接模式的节点，但不足以识别偏离的节点是与其他类混淆还是仅仅是离群节点。但是，确定一个节点可能无法区分的类对于显式调整混淆类的边距是必要的。因此，本文建议异常分布感知边距（ADM），它根据与目标类相比 NLD 空间中的自身类（给定节点的类）的相对接近度来补充调整目标类边距。由于两个类的 NLD 越接近，区分两个类就越困难，本文将 ADM 设计为对目标类和自身类之间的距离敏感。具体来说，定义自身类平均 NLD 和节点 NLD 之间的线段之间的角度，以及自身类平均 NLD 和目标类平均 NLD 之间的线段之间的角度为 。然后，根据余弦的最小值，我们可以计算给定节点 的 为：
是Jensen-Shannon散度，ADM表示为：
实验分析
本文的算法TAM和其他基线在三个类别不平衡节点分类基准数据集上的实验结果如下表，在三个典型的GNN结构上10次重复的平均平衡精确度和F1-score的标准误差。
为了验证本文方法的每个组成部分，在三个节点分类数据集上进行了消融研究。首先，本文将ACM与不使用类连通性矩阵的ACM进行比较，以证明利用类连通性统计的合理性。其次，我们还验证了我们的三个关键模块:ACM、ADM和分级温度。如下表所示，本文方案的每个组件都可以单独带来性能提升。
TAM还为次要类节点以外的节点（比如主要类节点）调整边距。这种设计的基本原理是：即使异常主要节点的影响要弱得多，它们仍然会对其邻节点产生假阳性。为了验证该原理，本文探索了TAM的性能，该TAM只调节CORA和Chameleon数据集上次要节点的边距。这些结果表明只调整次要节点显示次优性能，但与基线相比它仍然带来了相当大的改进。
总结
在类不平衡节点分类中，作者发现补偿偏离类连通模式的次节点容易导致次节点误报。根据这一观察，本文提出了TAM方案来根据与连通模式的偏离程度智能地调整类边距。实验表明，本文的算法通过简单地将TAM与各种GNN结构相结合，有效地改进了类别不平衡的处理方法
