CVPR 2019 Linkage Based Face Clustering via Graph Convolution Network论文翻译

摘要

本文中，我们介绍了一个准确且scalable的方法来实现人脸聚类任务。我们的目的在于通过人脸潜在的identities实现人脸聚类。我们将这问题当做是连接预测问题：如果两个人脸是同一个人，则他们之间存在连接。关键思想是我们在一个实例（人脸）周围的特征空间中找到局部上下文，其中包含有关该实例与其邻居之间的连接关系的丰富信息。我们利用图卷积网络（GCN）进行推理并推断子图中各对之间链接的可能性，在每个实例上建立子图（描述了上下文）并作为输入数据。实验证明，balabala……。此外，我们证明了这个方法不需要预先知道类的数量，能够处理噪声和异常值，并可以扩展到多视图版本，以实现更准确的聚类精度。

1. 引言

本文，我们研究了根据人脸潜在的身份实现人脸聚类的问题。我们假设人脸表示或身份的数量的分布预先不知道。人脸聚类是人脸分析的基本的任务并且在先前的工作中得到了广泛的研究 [38, 27, 22, 29]。一些关键的应用包括：在桌面/在线相册中对面部进行分组和标记 [38]，组织大规模的面部图像/视频采集，以便在时间敏感的场景（如法医调查）中快速检索[19]，自动数据清理/标记以构建大规模数据集[26、12、34]。

传统的聚类方法有着复杂的人脸表征分布，因为它们对数据分布做出了不切实际的假设。例如，K-Means [24]要求簇为凸形，频谱聚类[28]需要在多个实例中平衡不同的聚类，DBSCAN [10]假设不同的簇具有相同的密度。相比之下，基于连接的聚类方法无需对数据分布进行假设即可获得更高的准确性。如图1(a)所示，基于连接的方法旨在预测两个节点（或者簇）是否应该连接（是同一个身份）。图1（b）显示了这个问题最初的解决方案，当它们的欧式距离小于某一阈值时就直接连接两个节点。这显然不是一个好的方法，因为簇的密度是不同的。因此，人们设计了更多复杂的指标来计算连接的可能性，例如Approximate Rank-Order Distance（图1（c））。

我们提出学习预测两个节点是否连接，而不是通过启发式指标计算连接的可能性。作为这项工作的关键思想，我们发现可以从节点的上下文中推断节点与其邻居之间的连接可能性。为了利用节点的上下文信息，我们基于GCN提出一个可学习的聚类方法，图1（d）是我们的主要思想。以下是我们对这个框架的总结。

首先，我们将聚类当做是连接预测问题。也就是说，当两个节点属于同一身份时，节点之间存在连接。第二，我们仅对一个实例和它最近的邻居预测连接。因此，我们对每一个实例（pivot）建立了IPS来描绘局部上下文，每个节点都模拟一个枢轴-邻居对（pivot-neighbor pair）。从IPS中，我们可以推断哪一个pivot-neighbor pair应当被连接，因而我们利用GCN学习这个任务。最后，GCN输出了一系列连接的可能性，然后我们合并连接的节点以获得聚类。

与state-of-art方法相比，我们提出的方法是准确的，并且在计算复杂度方面scalable。我们提出的方法能够学习自动生成连接的可能性，与其他利用启发式规则计算的连接方法（例如ARO[27]）相比，该方法具有更好的性能。此外，我们的方法能够了解噪声和离群值，不需要了解簇的个数，并且易于利用来自不同源的数据扩展成多视角版本。

2. 相关工作

人脸聚类：……

连接预测：连接预测是社交网络分析的一个关键问题[21,1,20,25,36]。给定一个图形式的复杂网络，目标是预测两个成员节点连接的可能性。为了预测连接的可能性，一些先前的方法，例如PageRank[4]，SimRank[16]分析了整个网络，而其他方法，例如preferential attachment[3]，resource allocation[37]，仅从给定节点的邻居中计算了连接可能性。Zhang和Chen
[35，36]认为仅从节点对的本地邻居计算链接似然性就足够了，并且提出了一个Weisfeiler-Lehman Neural Machine[35]和一个图神经网络[36]从局部子图中学习大概的图结构特征。由于聚类任务可以简化为连接预测问题并且我们也利用了图神经网络学习子图，它与我们的工作有关。

图卷积网络：……根据在图数据上卷积的定义，GCN可以分为谱域的方法和空间的方法。基于谱域的GCN[5,8,18]利用图傅里叶变化产生卷积，而基于空间的GCN [31，13]直接在图节点及其邻居上执行手动定义的卷积。在应用方面，GCN可以处理传导设置[8，18]和归纳设置[13，31]中的问题。在转导设置中，训练数据和测试数据是固定图中的节点，而在归纳设置中，模型需要在不同图之间进行推断。本文我们提出使用基于空间的GCN来解决连接预测问题。设计的GCN在归纳设置中执行图形节点分类。

3. 提出的方法

3.1 概括

问题定义。假定我们有一些人脸图片的特征 $X=[x_1,...,x_n{]}^T\in {\mathbb{R}}^{N\times D}$，

其中N代表图片的数量，D代表特征的维度，人脸聚类的目标是分配一个虚拟的标签$y_i$，这样有着相同标签的就属于同一类。为了解决这一问题，我们基于连接的聚类方法，该方法的目的在于预测一对实例之间连接的可能性。因此，所有由连接的实例之间形成簇 (clusters)。
动机。本工作的动机是我们发现，我们只需要计算一个实例和它邻居之间连接的可能性，并且它已经足够得到一个良好的聚类结果。表一中，我们展示了不同的k值对于聚类性能上届(upper bound)的影响。为了得到这个上界，我们直接连接了每个实例和它的K个近邻，前提是该近邻和实例是同一个id。结果显示，在各种k值下，上界还是很高的。这表明，预测实例和它k个近邻之间的有效性，可以不用在在所有节点对上预测。这样的好处就是我们可以获得较高的聚类准确度而系统又很高效。
Pipeline。本文的工作专注于聚类的准确度和效率。于是我们采用了只在实例和它的K个近邻之间预测连接的思想。由于预测连接是基于上下文的，为了尽可能的准确预测，我们设计了一个局部的结构称为IPS。IPS是以中心实例p为中心的子图。IPS由节点p和它K个邻居以及p的更高级别的邻居节点组成。重要的是，我们从所有的节点中减去了p的特征，所以每个节点的特征都编码了中心-邻居之间的连接关系。我们从以下三步展现了我们提出方法的框架，见图三。

• 我们将每一个节点都当做pivot，并且为它建立一个IPS。3.2详细介绍了建图流程。
• PS作为输入数据，我们应用图卷积网络做推理，网络输出是每一个节点的score，也就是与相关中心节点连接的可能性。3.3介绍了GCN的工作机制。
• 以上的步骤输出一组加权后的边，权值代表连接的可能性。最终，根据链接的可能性，我们合并连接在一起的实例，构成cluster。3.4是细节
  

3.2 建立IPS

在一张图中，我们根据两张图片之间的上下文估计连接的可能性。在本文中，我们提出建立IPS作为上下文。IPS建立有三步：首先，我们定位IPS的所有节点。然后，我们通过减去中心节点的特征正则化节点的特征。最后，我们在节点间增加边。图2是建立IPS的过程。

第一步：发现节点。 给定pivot节点p，我们把p的邻居（直到h级别）作为IPS的节点。对于每一个级别的节点，选择的节点数可以不一样。我们用$k_i$作为第$i$级别的最近节点数。例如，设P为中心节点，$h=3,k_1=8,k_2=4,k_3=2$，也就是，p的最近邻居有8个，每个p的一级邻居有4个最近邻居，p的每个二级节点有2个最近邻居。值得注意的是，p不算在IPS的节点集中。当我们这么做时，高级别的邻居能够提供中心节点和邻居之间上下文的局部结构的辅助信息。例如，对于p和它的邻居之一q，如果q的k个近邻与p离得比较远，那么p和q之间的连接可能性就比较小。
第二步：节点特征正则化。 现在，我们有中心实例p，节点集$V_p$和他们的节点特征$x_p$和$x_q$。为了将中心节点的信息编码进IPS中的节点特征，我们通过减去$x_p$正则化特征，$$F_p=[...,x_q?x_p,..{]}^T,q\in V_p$$
我们用$F_p\in {\mathbb{R}}^{|V_p|\times D}$代表正则化的节点特征。
第三步：在节点中增加边。 最后一步是在节点之间增加边。对于一个节点q（属于Vp），我们首先在初始的所有节点集中找到最近的u个邻居。如果uNN中的一个节点r出现在Vp中，我们就连接（q，r），并加入边集Ep。这个过程保证了节点度不会相差太多。最后，我们利用了一个邻接矩阵$A_p\in {\mathbb{R}}^{|V_p|\times |V_p|}$和节点特征矩阵$F_p$代表IPS的拓扑结构。

3.3 IPS上的卷积

IPS中的包含的上下文信息（节点边）对于确定节点是positive（与中心节点连接）还是negative（与中心节点不连接）是非常有用的。为了利用它，我们将图卷积网络稍加修改应用在了IPS上。一个图卷积网络将特征矩阵X和邻接矩阵A作为输入，输出一个转换的特征矩阵Y。在第一层，输入的节点特征矩阵是原始的节点特征节点，X=F。形式上，我们图卷积网络有以下表达式

$$Y=\sigma ([X||GX]W)$$
$X\in {\mathbb{R}}^{N\times d_{in}}$,$Y\in {\mathbb{R}}^{N\times d_{out}}$，N是节点数，$d_{in}$和d_{out}是输入/输出节点矩阵的维度。$G=g(X,A)$是$N\times N$的聚合矩阵，每一行的和是1，而g(·)是X和A的函数。运算符||表示沿特征维度拼接矩阵。W是图卷积网络的权重矩阵，大小为$2d_{in}\times d_{out}$，最外层的是非线性激活函数。

图卷积操作可以分成两个部分。第一步，通过G左乘X，聚集节点邻居的潜在信息。然后，输入的节点特征矩阵X就与聚集信息GX拼起来了。在第二步中，通过一组线性滤波器对连接后的特征进行变换，学习参数W。我们研究了用于聚合的g(·)的三种操作。

• 均值聚合。聚集矩阵$G={\Lambda }^{?1/2}A{\Lambda }^{?1/2}$,$A$是邻接矩阵，$\Lambda$是对角矩阵且${\Lambda }_{ii}={\sum }_j{A}_{ij}$，这个均值聚集在邻居之间执行平均池化。
• 加权聚合。们将A中的非零元素替换成相应的余弦相似度，并且利用softmax函数正则化这些非零元素… …
• 注意力聚合。

本文使用的GCN由4个图卷积层组成，激活函数是ReLU，我们在softmax之后使用了交叉熵。实际上我们只反向传播了一级邻居的梯度，因为我们仅仅考虑中心节点和一级邻居之间的邻居。这种策略能够极大加快速度，而且能够得到较好的准确率。原因是高级别的节点大多数是negative，因此，一跳邻居中的正样本和负样本比所有邻居中的样本更加均衡。为了测试，我们也仅在一跳节点上分类。
为了描述图卷积的工作机制，我们设计了一个简单的例子，输入是2D的输入节点特征，并且有两层图卷积网络。每一层的输出维度$d_1,d_2$都设为2，方便可视化。在图4中，我们显示了每一层的输出是如何随着迭代次数变化的。每一层图卷积层之后，positive（红色）节点更聚拢，negative节点（绿色和蓝色）形成了另一个集群。这是因为在聚合阶段邻居的信息都传送到节点上，并且来自邻居的节点能够将连接的节点聚在一起。与此同时，监督信号将positive和negative分开。最终，系统达到了它的平衡点，positive和negative彼此距离得很远并且同一类的节点距离得很近。

3.4 合并连接

为了在人脸上应用聚类，我们在整体实例上循环，将每一个实例当做中心节点建立IPS，并且预测中心节点和相关节点连接的可能性（通过节点分类器输出的softmax可能性）。因此，我们得到了一组由链接可能性加权的边。为了获得集群，一个简单的方法是将权值小于某阈值的边删除并且利用BFS（广度优先搜索）传播伪标签，如图3所示。然而，性能会被阈值影响。因此我们采用了文献[34]中的伪标签传播方法。在每次迭代中，该算法都会删除权值低于某一阈值的边，并且维持连接的簇，这些簇的大小大于在下一次迭代中待处理的预定义队列的最大值。在下一次迭代中，删除边的阈值增大。迭代直到队列为空时停止，也就意味着所有的实例都分配到了伪标签。

4. 实验

4.1 评估指标和数据集

为了评估这个聚类方法的性能，我们采用了两个主流的评估指标：NMI和B立方度量[2]。给定ground truth簇$\Omega$，预测簇C，NMI定义为

$$NMI(\Omega ,C)=\frac{I(\Omega ,C)}{\sqrt{H(\Omega )H(C)}}$$
$H(\Omega )$和$H(C)$代表$\Omega$和C的熵，$I(\Omega ,C)$是公共信息。

B立方度量是一个更加实际的方法，它考虑了预测和召回率。用L(i)和C(i)分别代表真实标签和标签，我们首先定义正确性为

B立方预测P和B立方召回率R定义为

并且B立方度量定义为$F=\frac{2RP}{R+P}$

我们利用了单独的数据集测试与训练。首先，我们利用ArcFace[9]作为人脸表示。这个模型在MS-Celeb-1M和VGGFace2上训练。第二，为了训练GCN网络，我们利用了CASIA数据集[33]的子集，包括了5k个人和200k的例子。第三，为了测试，我们采用IJB-B数据集因为它包含了一个聚类的protocol。protocol包括七个子任务，每个子任务的ground truth均不同。我们在最大的子任务上评估了算法。在三个子任务中，身份的个数为512,1024，和1845，并且样本的数量为18171,36575和68195.

4.2 参数选择

IPS建立有3个超参数：跳数h，对于每一跳选择的最近邻数$k_i,i=1,2,...h$,以及，选择连接的近邻数。我们首先对不同的h做了实验，并且发现h>=3并不会增加性能，于是在接下来的实验中我们设置h=2。之后，我们探索了k1,k2和u。我们讨论了训练阶段以及测试阶段。

训练阶段，k1=100，k2=10，u=10.

考虑到效率，k1和k2不能太大，我们发现k1=80，k2=5，u=5可以取得不错的效果，接下来的实验中，我们都这么用。

4.3 评估

时间复杂度以及效率。所提出的方法仅在局部IPS上进行，因此连接预测过程的运行时间随数据数量线性增长。如果使用暴力搜索建立IPS的复杂度为O(n^2)，如果用ANN搜索可以降至O(nlogn)。总体来说，大致的复杂度是O(nlogn)，也就是说它是有效且scalable。

5. 总结

本文中，我们提出了一个基于连接的人脸聚类方法。我们强调了人脸聚类中上下文的重要性，并且提出了建立IPS包括上下文。在IPS上，我们利用了图卷积网络预测了给定节点和它的邻居之间连接的可能性。大量的实验表明，我们提出的问题相比传统方法更具鲁棒性。最后，我们证明了我们的方法在视听人脸聚类中的优势。