A Survey of Imbalanced Learning on Graphs: Problems, Techniques, and Future Directions
A Survey of Imbalanced Learning on Graphs: Problems, Techniques, and Future Directions
图上不平衡学习综述
摘要
图 表示在真实世界中普遍存在的相互关联的结构。有效的图分析 ，例如图学习方法，使用户能够从图数据中获得深刻的见解，支持各种任务，包括节点分类node classification、链接预测link prediction。然而，这些方法往往存在数据不平衡问题data imbalance ，这是图数据中一个常见的问题，即某些部分拥有丰富的数据，而另一些部分则缺乏数据，从而导致有偏差的学习结果。这就需要新兴领域：即图上的不平衡学习，目的是纠正这些数据分布偏差，以获得更准确和更具代表性的学习结果。在这项调查中，我们着手对图上的不平衡学习的文献进行了全面的回顾。我们首先提供对概念和相关术语的明确理解，为读者建立牢固的基础理解。在此基础上，我们提出了两种综合分类法 ：(1)问题分类法，它描述了我们考虑的不平衡形式、相关任务和潜在解决方案;(2)技术分类，详细说明了解决这些不平衡的关键策略，并为读者在方法选择过程中提供帮助。最后，我们提出了图上不平衡学习领域的问题和技术的未来发展方向，促进了这一关键领域的进一步创新。
Index Terms: Imbalanced learning on graphs, graph reprsentation learning, class imbalance, structure imbalance
1 介绍
图或者网络，指的是在现实世界场景中常见的相互连接的结构，其中实体经常相互作用。图在各个领域都无处不在，比如Facebook平台上的社交网络，DBLP上的引文网络，亚马逊上的电子商务网络等。图结构的流行引起了人们对图分析的极大兴趣，图分析旨在利用图中的固有信息进行下游任务，如节点分类、链接预测和图分类。
图分析的早期研究通常依赖于传统的技术 ，如特征工程[1]-[3]，这可能是计算昂贵的，需要大量的努力。然而，随着图表示学习graph representation learning[4]，[5]的出现，图分析出现了新的机会。图表示学习旨在将图的结构(如节点、边或图)嵌入到低维空间中，同时保留其结构信息。先前的图嵌入方法[4]，如Deepwalk [6]， LINE[7]和node2vec[8]，依赖于节点之间的上下文连接来捕获节点表示学习的接近度。最近，更多的注意力转移到图神经网络(gnn)[9] -[12]，这是一种利用邻域聚集的图表示学习方法。它们进行邻域聚合，以端到端的方式沿边缘递归地传递和接收消息，从而有效地对图结构进行编码。因此，GNNs也在许多下游任务中达到了SOTA。
失衡现象Imbalance phenomenon ：虽然这些图表示学习方法可能是有效的，但像许多机器学习模型一样，它们通常需要大量标记数据进行训练。然而，现实世界的数据经常显示不平衡的分布，其中一些段具有丰富的数据，而其他段则没有。例如，在分类任务中，标记数据(如图像或文档)的分布可能向某些类倾斜，从而导致标签分布不平衡。这种数据不平衡会显著影响训练过程。具体来说，该模型往往在拥有充足数据的高资源组上训练良好，而在数据有限的低资源组上表现不佳，导致不明确的类边界[13]-[15]。因此，在高资源组中，模型性能通常令人满意，但在低资源组[16]-[18]中，模型性能会下降。因此，不平衡学习 的严峻挑战在文献中引起了极大的关注，解决这些挑战至关重要[17]，[19]- [22]。
图上的不平衡学习imbalanced learning on graphs ：为了解决这种不平衡问题，人们在视觉和语言领域提出了各种方法，然而，图数据与他们的不同在于样本是非独立同分布的，并且是multifarous，具有不同的结构方面（节点度数）。直接应用这些方法来解决图上的不平衡问题可能是不可行的。因此，图学习面临着新的不平衡类型的挑战，而不是在这些设置中发现的。
不平衡问题对基于图的任务性能的巨大影响最近引起了重要的研究兴趣[28]- [30]，如图1所示。这些研究努力致力于解决各种现实世界的应用[18]，[26]，[31]-[34]，形式化成几个不同的研究问题。每一个问题都有其独特的特点，要求开发专门的技术，以有效地解决每一种情况所特有的不平衡问题。然而，问题和技术的多样性导致了图上不平衡学习的分散景观，缺乏一个全面的框架来识别它们的共性和差异。
因此，在本调查中，我们将重点放在图上的不平衡学习(ILoGs)上 ，通过回顾和总结解决图上不平衡问题的问题和技术来弥合这一差距。ILoGs的本质在于观察到输入不平衡的图学习模型通常在不同图资源丰度[18]，[32]，[34]-[36]的组中表现出不同的性能。更准确地说，如图图所示，给定输入图，图数据往往被划分为多个段，造成图资源分布不平衡。这种现象可以在各种任务中观察到，如不平衡节点分类[25]，[37]和不同程度的节点表示学习[18]，[27]，如图2(b)所示。这种不平衡的分布往往会导致不平衡的结果:图模型通常在高资源部分表现良好，而在低资源部分被边缘化，最终导致各部分之间的性能差异，如图图©所示。
然而，图上不平衡学习的多面性在其研究中表现出相当大的复杂性。一方面，图形结构产生了一系列以各种形式的不平衡为特征的问题，任务和解决办法。这种多样性给统一这些元素带来了挑战。因此，创建一个有组织的分类法 来对图上的这些不平衡学习问题进行分类是一项重要的任务。此外，详细的分类将有利于未来的研究，通过确定未开发的领域。另一方面，图上的许多不平衡问题产生了不同的解决方案，有些任务由于其独特的属性而需要特定的技术。这创造了一个复杂的解决方案，使该领域的研究具有挑战性。因此，从技术角度对文献进行分类 是至关重要的。此外，这种分类还可以帮助读者选择适当的技术来处理他们特定的图形不平衡问题。
为了解决这一复杂性，我们从问题和技术的角度对文献进行了分类，以提供一个全面的概述。首先，对于问题的分类，我们根据类别失衡和结构失衡对文献进行分类，两者都源于输入不平衡。我们进一步将其提炼为更具体的类别:节点级、边缘级和图级失衡，提供对图级失衡的全面理解，如图图所示。此外，为了更清楚地了解这些不平衡问题，我们在表1中通过详细描述和对比它们的类型、设置和信息丰度来进行更深入的研究。此外，对于技术分类，我们根据失衡类型和缓解失衡的相关策略对文献进行分类，如图所示。这是因为，特定类型的不平衡可能需要特定的技术来有效地解决相关的问题，并且所采用的技术可能因不同的不平衡类型而异。
使用这些分类法，我们可以捕捉到不平衡图学习过程中的共性和差异。在问题和技术分类的基础上，我们进一步描绘了图上不平衡学习领域未来研究的有希望的方向。具体而言，在考虑未来问题的方向时，我们通过阶级不平衡和结构不平衡的视角来剖析潜在的研究挑战。至于未来的技术方向，我们考虑创新的解决方案，可以推动这一领域的发展。
请注意，考虑到研究这个复杂问题的论文数量庞大，我们的调查并没有深入研究每项研究的细微差别。相反，我们的主要目标是根据已建立的分类法给出一个整体的、结构化的概述。这种方法确保我们提供了一个广阔的视角，并聚焦在图上不平衡学习的新兴前沿。
Relationship with existing surveys：在过去的十年中，不平衡学习已经成为几项研究的主题，涵盖了从一般的不平衡分类general imbalanced classification[19]，[20]，[38]到更具体的任务 ，例如异常检测anomaly detection[39]-[41]，少量样本学习few-shot learning[42]，[43]，长尾分布[17]等各个领域。然而，这些调查主要集中在一般情况下或特定任务中的不平衡学习，而缺乏对图上不平衡学习的全面覆盖。在与图相关的任务领域，有一些研究关注图上的特定任务，如类不平衡学习[44]、异常检测[28]、[45]-[47]、少量样本学习分类[29]、[30]和公平学习[48]。尽管他们的相关性，这些调查集中在个人任务和缺乏全面的概述不平衡的学习图。
我们的调查填补了这一空白，提供了不平衡学习的整体视图，涵盖了不同的任务，重点关注阶级不平衡和结构不平衡。与之前的调查[28]-[30]，[45]-[48]相比，我们的工作阐明了这些任务的共同特征和独特特征，为它们的共性提供了新的见解。基于两种分类的图上不平衡学习范围内的差异。此外，我们还将图上的公平学习(参见7.1节了解更多细节)作为一种特定类型的不平衡学习。与其他形式的不平衡学习不同，公平学习侧重于减轻模型预测中可能存在的潜在偏见和歧视，而不仅仅是提高在不平衡数据上的表现。
2 基础
2.1 Graphs and Graph Representation Learning
2.1.1 Graph Formalization
节点和边类型的多样性导致了图的不同形式。同质图homogeneous graph 是不考虑节点和边类型的图。由于它的简单性，它一直是图分析中大多数研究的主题。异构图heterogeneous graph ，也成为异构信息网络(Heterogeneous Information Network,HIN)，是具有不同节点或边缘类型的图，并且由于节点和边缘类型的存在，保留了不同的语义。特别是，基于异质性的多样性，异构图可以进一步分为几类。二部图bipartite graph 要求只存在两种类型的节点，它们的边连接着不同类型的节点，在推荐系统[50]中，通过将用户-项目交互形式化为图格式，对二部图进行了广泛的研究.另外，**知识图谱(KG)[**51]是由节点之间的各种类型的边组成的图，这些边分别被称为关系和实体。
2.1.2 图表示学习
4.1.2 Node-Level Anomaly Detection
节点级异常检测作为不平衡节点分类的具体表现，一般以正常节点和异常节点的二值分类为中心 。该任务在许多应用中起着至关重要的作用，例如异常值检测[72]，[73]，欺诈用户检测[74]-[77]，以及社交垃圾邮件发送者检测[78]-[80]。考虑到图的多样性(例如，同构图，异构图或动态图)，已经开发了一系列技术来解决这个问题，例如传统的图算法(GA)，图嵌入方法(GE)和图神经网络方法(GNN)。表3对它们进行了分类，其中还包括边缘和图级异常检测方法。虽然我们概述了该领域的最新文献，但要进行深入分析，我们建议读者参阅综合调查[28] 。
Homogeneous graphs：在同构图上的节点级异常检测是其中感兴趣的焦点。传统的图算法(GA)通过各种手工度量捕获结构异常来处理异常检测，例如对属性应用残差分析[82]，[85]，或以交互方式利用人类反馈[87]。在此之后，基于图嵌入(GE)的方法被开发出来，旨在分别嵌入异常和正常节点以捕获其特定模式[93]，[95]，或者生成可以在类之间形成清晰边界的表示[96]等。
近年来，gnn被广泛用于图的异常检测。这些方法通常与不同的学习目标相结合，以获得可区分的节点嵌入。我们在下面概述了一些流行的技术。对比学习 方法通常在模型预训练期间利用目标节点与其上下文之间的相似性。对于包含可疑节点的图数据(这些节点经常试图伪装自己)，识别它们与上下文的不相似性(即异质性)对它们的检测是有益的[107]，[111]。像gan这样的生成模型 也被用于在训练过程中创建合成节点，因此模型可以学习正态节点的不同分布以及分布外的异常节点[102]，[110]。此外，自编码器 也用于重建图结构或节点特征，其中难以重建的样本通常被识别为异常[102]，[106]。
summary：由于图结构的复杂性和异常的罕见性，对图的节点级异常检测具有固有的挑战性。在这个领域中流行的技术主要集中在建立正常和异常节点之间的明确界限。这可以通过特征工程(GA)、判别节点表示(GE)或结构编码的邻域聚合(GNN)来实现。为了更全面地了解最先进的比较，读者可以参考[186]等基准或访问排行榜1。为了进一步推动这一领域的进展，采用创新的方法至关重要。例如，复杂的生成学习模型，如扩散[71]，可以用来支持合成实例生成，从而增强异常节点的可辨别性 。此外，创新的基础模型[187]有望丰富对图结构的理解，从而可能促进更有效的异常检测。