2022-03-25

GCN-Based Linkage Prediction for Face Clustering on Imbalanced Datasets: An Empirical Study

近年来，得益于图卷积网络（GCNs）的表达能力，人脸聚类取得了重大突破。然而，很少有人关注基于 GCN 的不平衡数据聚类。尽管不平衡问题已经被广泛研究，但不平衡数据对基于 GCN 的链接预测任务的影响是完全不同的，这会导致两个方面的问题：不平衡的链接标签和有偏差的图表示。链接标签不平衡的问题类似于图像分类任务中的问题，但后者是通过链接预测进行基于 GCN 的聚类中的一个特殊问题。训练中显着偏差的图表示可能导致 GCN 模型的灾难性过拟合。为了解决这些问题，我们通过大量实验评估了现有方法在图上解决不平衡图像分类问题的可行性，并提出了一种新方法来缓解不平衡标签并使用反向不平衡增强图表示加权抽样 (RIWS) 策略，随后是富有洞察力的分析和讨论。从 MS-Celeb-1M 和 DeepFashion 合成的代码和一系列不平衡基准数据集可在不平衡数据集上的 https://github.com/espectre/GCNs 上获得。

1 简介

人脸聚类被广泛应用于人脸检索、人脸标注和相册分类等许多应用中。它旨在以无人监督的方式将来自某个人的面部图像组合在一起。传统的聚类方法通常假设过度简化的数据分布 [Wang et al., 2019b] 与现实世界中大规模人脸图像的分布有很大差异，因此很难获得令人满意的性能。

近年来，得益于图卷积网络 (GCN) 的表达能力，基于 GCN 的解决方案在 MS-Celeb-1M [Guo et al., 2016] 等大规模人脸聚类基准测试中获得了更好的性能，其中GCN 用于图形、节点或边缘识别任务以及特征嵌入。 L-GCN [Wang et al., 2019b] 使用 GCN 来预测“枢轴”节点与其 1 跳邻居之间是否存在链接。 [Yang et al., 2019] 中使用了两个 GCN 来检测和分割集群提案。 [Yang et al., 2020] 还使用两个 GCN 来完成人脸聚类：一个用于估计顶点的置信度，另一个用于测量顶点之间的连通性。 DA-Net [Guo et al., 2020] 利用本地和非本地信息来获得更好的特征嵌入。

尽管上述方法取得了显着进步，但在面对真实场景中不平衡的数据时（即不同人的面部样本数量大范围变化且分布不平衡），它们的性能往往会受到很大影响。为了帮助减少这种性能折衷，本文特别研究了基于 GCN 的链接预测任务（以 L-GCN 方法作为示例基线）中的不平衡问题，该任务很少受到关注。在过去的几年里，图像分类中的不平衡问题，其本质在于正样本和负样本的数量不平衡（即标签的不平衡），已经被广泛研究 [Cui et al., 2019;康等人，2019；周等人。，2020]。在L-GCN中，相同的性质存在于阳性和负环节的形式。然而，除了标签中的不平衡问题之外，不平衡数据还可以在L-GCN中引起偏置图形表示，其特别是与GCN相关的。具体地，从不平衡训练集中产生的图表容易出现具有IM平衡的结构（具有相同类别和不同类节点的不平衡数量，也不是边缘），这对于模型泛化不利（即，获取模型可以发出任何图形结构）。

因此，我们研究了两个方面的基于GCN的联系预测任务中的不平衡问题：不平衡标签和偏置图形表示。首先采用了一些典型的图像分类的不平衡问题来解决标签中的不平衡问题，其中一些人展示了他们的有效性。为了解决不平衡标签和偏置图表代理的问题，在本文中提出了一种反向不平衡的加权采样（RIWS）策略，通过提供更多样化的结构来增加图表代表，但在训练样本上保持平衡的整体分布。

图。图1示出了由RIW构造的典型的子图结构（主要是忽略其边缘的1跳节点，其中覆盖了平衡和IMBAL-截止结构。相比之下，由原始L-GCN构造的子图往往是极其易用的（图1（a）），而通过正常再采样方法产生的子图均易于具有绝对的结构结构（图。如图1（b）所示，两者都被偏置，差不平或平衡。在脸部聚类（MS-CELEB-1M）和衣物聚类（Deepfashion）中证明了RIWS策略的有效性，其中获得了稳定的性能增益。

总之，本文具有以下三项主要贡献：

第一次研究了基于GCN的链接预测任务中的不平衡问题，设计了具有不平衡数据集的基准。

图像分类中不平衡问题的典型重新采样和重新加权方法是转换的，以解决基于GCN的连杆预测任务中的标签不平衡问题，评估其有效性和富有洞察分析;

提出了一种名为RIWS的新颖策略来解决通过增加图形结构的多样性而在训练样本上保持平衡的整体分布的图形结构的多样性来解决不平衡标签和偏置图表表示的问题。

相关工作

基于GCN的面部聚类。

面部聚类对于利用未标记的面部数据至关重要，并且已广泛使用在许多情况下。传统方法，例如K-Means [Lloyd，1982]，DBSCAN [Ester等，1996]和HAC [SIB-SON，1973]，首先应用于脸部聚类任务。有史以来，由于一些天真的假设（例如，所有集群的密度或凸形相同），这些方法不能在现实世界中处理大规模的面部数据[Wang等人，2019b]。在终年中，图表卷积网络（GCNS）正在成为群化越来越强大的聚类技术，并实现了显着的性能改进。 GCN的图表性质使其优于解决非欧几里德数据相关任务。最近，已经致力于使用GCNS解决面部聚类的大量研究工作，因为它可以捕捉不同面部之间的复杂关系。

L-GCN [Wang等人，2019B]将面部聚类配制为连杆预测问题。如果预计两个面部被链接，则它们将它们聚集在一起。在[杨等人，2019]中，利用两个GCN模块，即GCN-D（检测）和GCN-S（检测），用于集群面。它是一种两阶段的过程，其中使用GCN-D来选择高质量的集群提案，而GCN-S用于去除提案中的噪声。类似于[杨等人，2019]，[杨等人，2020]也是两级解决方案。在第一阶段，GCN-V（顶点）估计所有顶点的置信度，并且仅选择具有更高置信度的顶点以构建下一个阶段的子图。 GCN-E（边缘）用作连接估计器，类似于链接[Wang等人，2019b]，它输出子图中每个节点的分数，这表示它与枢轴节点相同的标识。

在大多数基于GCN脸聚类方法，GCN主要是利用当地的信息，以提高人脸特征，不考虑全球信息考虑在内。 DA-净[Guo等人，2020]利用通过集团和链本地和非本地信息，以获得更好的功能嵌入。

类不平衡学习。大多数公共数据集（例如，Ima-遗传学[Deng等人，2009]，CIFAR [Krizhevsky等人，2009]和MS-名人-1M [Guo等人，2016]）通常artifi- cially平衡，这手段EV-ERY类实例的数量没有太大的区别。然而，在现实世界中，数据更可能是不均衡分配，从而导致巨大的挑战。由于大多数情况下的是─长一些头类，因此，头班称霸训练阶段，而以较少的样本的类表现显著恶化。

目前已经有大量的研究集中在imbal- ANCE问题，我们将它们分为三个系列：再抽样方法，重新加权的方法，并传递学到，荷兰国际集团为基础的方法。重新采样策略[Zhou等，2020; Wang等，2019a。 Kang等人，2019]主要由过采样的少数样品和欠采样的马jority样本构建均衡的数据分布。用最上端的样品的比例，重新加权甲 -  ODS [Chou等，2020; Cao等，2019; Cui等，2019;贾马尔等人，2020]分配适当的设计 - 通过ING重新加权的权重损失来平衡数据分布，其核心思想在于在直觉尾类别应具有较大的损失重量。通过转移学到，ING，一些文献启发[Xiang等，2020;刘等人，2019；刘等人，2020年]，尝试从头班尾班传授知识得到改善拖尾类的多样性。

在这项工作中，我们主要专注于基于GCN联动预测任务的不平衡问题。据我们所知，这是基于GCN联动预测任务相关的不平衡问题的第一项工作。基于GCN的任务在于对双方的不平衡prob- LEMS，除了为每个类的节点数量，子结构的多样性也不平衡。如在图1（a）所示，如果一个节点是由具有相同标识的节点太多包围，子图构建了基于k最近neigh-博斯（KNN）极为不平衡。虽然传统的重采样方法可以减少不平衡标签的问题，它是无效的偏置图形表示的问题。幸运的是，RIWS策略，本文提出可以通过建立不同的子图与均衡分布缓解的问题。

3问题制剂

在基于GCN联动预测的任务，不平衡的数据集可能会导致两个关键问题：不平衡联动标签和偏置图表示。前者是类似于用于图像分类，即，阳性和阴性样品之间的不平衡的不平衡问题。后者是基于GCN任务一个独特的问题。直接构造为L-GCN的子图倾向于训练集，这是容易发生过度拟合的分布被偏压。

在这项工作中，我们旨在解决基于 GCN 的链接预测任务的不平衡问题。为了方便解释，我们用 G = {V, E} 来表示特征图，其中 V = {v1,v2,...,vN} 是特征空间 R 中的一组节点。假设每个人脸的身份由 Yi 表示，N 张人脸图像可以分为 C 个身份 {Y1 , Y2 , ..., YC }。在真实场景中，正负样本的比例极不平衡，对人脸聚类问题提出了很大的挑战。我们将此任务表述为其中 Y 是预测结果。 X' 和 A' 表示子图的特征和采样邻居的邻接矩阵。 g(·) 是平均聚合操作，θ 是学习权重。

4 种方法

本文主要研究基于 GCN 的链接预测任务中的不平衡问题。已经有许多研究人员关注正样本和负样本之间的不平衡问题。我们选择了一些具有代表性的方法并评估它们在基于 GCN 的链接预测任务中的有效性。然而，现有的方法只处理不平衡标签问题，没有考虑到有偏差的图表示问题。因此，我们提出了一种反向不平衡加权采样（RIWS）策略，可以有效缓解这些问题。

4.1 不平衡连锁标签的方法

目前主流的方法主要有重加权法和重采样法。选择类平衡损失和焦点损失来评估重加权方法的影响，而过采样和欠采样方法用于评估重采样方法的性能。

类余额损失。在人脸聚类的边缘分类阶段，我们需要预测枢轴与其一跳邻居之间是否存在联系，这是一个二元分类问题。如果模型是在不平衡的数据集上训练的，则枢轴的 KNN 可能由大多数正样本或负样本支配。以图1（a）为例，pivot'KNN以正样本为主，导致子图不平衡，进而严重影响模型的学习。

为了避免正样本或负样本支配子图，我们引入类平衡损失来平衡每个子图中正样本和负样本的权重。具体来说，我们首先分别计算正负样本的平均损失值，然后取两个损失值的平均值作为最终损失值。

其中zP和zN分别是正样本和负样本的logit。 αP 和 αN 是根据出现频率计算的权重，它们满足 α = 1 ,α = 1 。 （N和N分别是正样本和负样本的个数）

焦点损失。 Focal loss 最早是在 [Lin et al., 2017] 中提出的，用于目标检测，它是专门为处理困难的训练样本而设计的。在我们的方法中，我们想要确定枢轴与其一跳节点之间是否存在边。如果我们将 1 跳节点的输出概率定义为 P = [pP, pN]，其中 pP 表示存在边的概率。然后链接预测的焦点损失可以表示为

其中 y 是真实标签，如果存在边，则 y = 1。超参数α（αP + αN = 1）用于平衡正负样本的影响，γ用于挖掘困难样本。

重新取样。随机过采样或欠采样是最直接和最具代表性的方法。随机过采样复制少数类中的随机样本，而随机欠采样随机删除多数类中的样本。尽管简单，但这些方法可以实现良好的性能。

4.2 不平衡标签和有偏图表示的方法

RIWS。目前解决不平衡问题的方法主要关注正负样本的比例，例如重新加权权重，过采样少数和欠采样多数。然而，在基于 GCN 的链接预测任务中，如果像传统的重采样方法一样强制所有子图构建平衡结构，则容易出现过拟合。在推理阶段，模型在面对不同比例的子图结构时往往表现不佳。这个由从多样性不足的图结构中学习引起的问题被定义为有偏差的图表示。

以前的工作没有考虑基于 GCN 的链接预测任务中的偏差图表示问题。在本文中，基于基本的重采样方法，提出了RIWS来构建子图。与 L-GCN [Wang et al., 2019b] 类似，我们以数据集中的每个实例为中心（称为“枢轴”），并基于枢轴的 KNN 构建子图。之后，GCN 模型聚合子图的特征，然后分类器预测枢轴与其每个 1 跳邻居之间是否存在链接。

与初始子图构造方法相比，我们增加了一个膨胀系数γ。有了这个系数，1-hop 节点的选择间隔从 k 增加到 k*γ，定义为扩展的 k 最近邻（eKNN），然后选择 eKNN 中的 k 个节点作为 1-hop 邻居，用于一定程度上控制了正负样本的分布。

图 1 展示了通过不同方法选择的一些子图示例的 1 跳节点。假设k=10，γ=1.5，在每个子图中，绿色实心圆圈包围的节点为pivot样本，1-hop候选节点由pivot在特征空间的15-NN组成。图1（a）表示使用L-GCN选择的k个邻居，其中选择了在特征空间中最接近枢轴的10个节点，没有考虑样本的不平衡问题。采用常规重采样策略时，选择的 1 跳邻居如图 1（b）所示，其中随机选择 5 个正样本（蓝点）（欠采样），选择 5 个负样本.如果负样本数量不足，则需要通过重复进行过采样。

如图2所示，RIWS流程如下。首先，对于每个pivot，将其eKNN中的节点作为其子图的候选节点，根据正负样本的个数计算每个候选样本的权重

其中 wij 是第 i 个样本的 eKNN 中第 j 个邻居节点的权重（即，第 j 个邻居节点被选为以第 i 个样本节点为轴的子图中的节点的概率）。然后，根据这些权重从每个 eKNN 中选择 k 个节点来构建其子图。这样子图的平衡性和多样性都可以得到保证。一方面，这个平衡权重可以保证1-hop邻居中正负样本的整体分布是平衡的；另一方面，加权随机抽样过程提供了多种结构（包括图1（a，b，c，d）所示的所有结构）。这两个属性共同有助于解决标签不平衡和图表示有偏差的问题。

5个实验

在本节中，我们构建不平衡数据集并进行广泛的实验，以评估传统不平衡分类问题的方法在扩展到基于 GCN 的链接预测任务时是否仍然有效，并验证我们提出的 RIWS 方法的性能。

5.1 设置

不平衡的数据集构建。为了评估每种方法在不平衡数据集上的性能，参考 [Liu et al., 2020]，我们基于两个公共数据集构建了一系列不平衡数据集：MS-Celeb-1M [Guo et al., 2016] 和 DeepFashion [刘等人，2016]。以 MS-Celeb-1M 为例，不平衡数据集的构建过程如下。

基于清理后的 MS-Celeb-1M [Yang et al., 2020] 的第 0 部分，我们根据两个超参数合成了 8 个不平衡的训练集：多数身份计数 m 和少数身份大小 n。具体来说，身份按其样本数排序，并选择前 m 个身份作为多数类。对于其余部分，从每个身份中随机抽取 n 个样本。如果身份大小小于 n，则将抽取所有样本。 m 采用 200、500、1000、2000，n 采用 3、5。这样就可以构造出8个不平衡的数据集，分别记为(H200, S3)、(H200, S5)等。我们在 8 个不平衡数据集上训练模型，然后分别在清理后的 MS-Celeb-1M 的第 1 部分上对其进行测试。

与 MS-Celeb-1M 类似，我们也构建了 2 个基于 DeepFashion 的不平衡训练集。

评估指标。我们将边缘分类模块和聚类的链接合并阶段解耦，以消除链接合并阶段的影响。在边缘分类阶段，选择AP（Average Precision）作为评价指标，在聚类阶段，选择Bcubed F score。

5.2 每种方法和组合的人脸聚类比较实验。

为了消除合并阶段超参数的影响，我们选择边缘分类AP作为基本度量来展示每种方法及其组合的性能。

表 1 的上半部分显示了边缘分类 AP

基于 MS-Celeb-1M 构建的 8 个数据集上的 L-GCN 和其他方法。在这些方法中，CB 代表类平衡损失，FL 代表焦点损失，RS 代表传统的重采样方法。

除个别情况外，每种方法对不平衡问题的表现都明显优于基线方法。在多数身份计数较小的子数据集中，例如子数据集（H200，S3），focal loss 取得了更好的结果，为 0.9694。可能正负样本之间的不平衡比例在这种配置中更为严重，因此焦点损失可以通过其对困难示例的学习能力和降低众多简单负例的能力来缓解不平衡问题，而基于采样的方法执行由于缺乏足够的样本进行采样，因此效果不佳。在多数同一性计数较大的子数据集中，有偏差的图表示的影响逐渐显现。本文提出的RIWS方法取得了比其他方法更好的结果，在子数据集（H2000，S5）中达到了0.9867的高AP。

这四种方法可以分为两类：重采样方法和重新加权方法。前一种方法主要用于子图构建阶段，而后一种方法用于分类器的训练。

为了进一步展示每种方法的性能，我们将两类方法结合起来，实验结果如表1底部所示。所有结果均显着高于baseline的实验结果。结合RIWS的类平衡损失明显高于使用常规重采样方法的类平衡损失，并且除了（H200，S3）子数据集外，RIWS的focal loss远远超过结合重采样方法的focal loss，说明该方法本文提出的方法不仅在单独使用时比重采样方法表现出更好的效果，而且在与重加权方法结合使用时也有更好的效果。

超参数灵敏度的比较。在本文中，我们引入了一个新参数 γ，它控制每个子图的候选节点和选定邻居的比率。当 γ = 1 时，我们的子图构建方法等效于 L-GCN 基线。常规重采样和 RIWS 方法在不同 γ 值下的性能如图 3 所示。点划线、虚线和实线分别表示基线、重采样和RIWS方法。并且每种方法都基于基线缓解了不平衡问题。

随着γ的增大，重采样方法的性能先增大后下降，在γ=1.2时达到最大值，而RIWS随着γ的增大继续增大，在γ处增长速度开始急剧放缓=2.0。在我们的实验中，我们为重采样方法选择 γ=1.2，为了不增加过多的计算开销，RIWS 方法选择了 2.0。在这种配置中，重采样和 RIWS 方法分别在 8 个不平衡子数据集上获得平均 AP 值 0.9739 和 0.9783，均远远超过基线 0.9688。我们提出的 RIWS 方法在每个子数据集中明显优于常规重采样方法。

5.3 时尚聚类实验

为了验证方法对不平衡问题的泛化能力，我们在 DeepFashion 的两个子数据集（H200，S3）和（H500，S3）上进行了实验。如表2所示，除focal loss外的所有方法都超过了L-GCN基线，而结合RIWS的类平衡损失达到了最佳性能。

5.4 部分/完整数据集的实验

表 3 展示了不平衡方法的最佳组合与基线之间的比较。请注意，我们的组合是在不平衡的子数据集上训练的，而基线是在完整数据集上训练的。标有星号的结果来自 [Yang et al., 2020]。尽管在分布不平衡的较少数据上进行了训练，但我们的方法获得了与在完整 MS-Celeb-1M 或 DeepFashion 数据集上训练的基线相当的结果，这有力地验证了我们方法的有效性。

6 结论与讨论

本文首次从不平衡标签和有偏图表示两个方面研究了基于 GCN 的链接预测任务中的不平衡问题。进行了广泛的实验来评估四种典型的图像分类不平衡问题方法在解决基于 GCN 的任务中不平衡标签问题的有效性，表明它们都可以带来一定程度的性能提升，并且它们的一些组合可以进一步扩展改进。本文提出了一种反向不平衡加权采样（RIWS）策略，作为解决标签不平衡和有偏图表示问题的试验，其有效性在 MS-Celeb-1M 和 DeepFashion 上的大量实验中得到证明数据集。

这些结果为选择和设计解决基于 GCN 的节点和边缘分类任务（不仅是 L-GCN）中的不平衡问题的方法提供了一些参考，其中不平衡的数据会导致上述两个方面的问题：不平衡的标签和有偏差的图表示。 RIWS 策略是尝试设计同时解决这两个问题的方法，但不一定是最佳方法。需要和欢迎更多的研究来为各种场景提供更好的解决方案。从 MS-Celeb-1M 和 DeepFashion 合成的代码和基准测试不平衡数据集可在 https://github.com/espectre/GCNs 上的不平衡数据集上获得。