Linkage Based Face Clustering via Graph Convolution Network
Zhongdao Wang Liang Zheng Yali Li Shengjin Wang


































Linkage Based Face Clustering via Graph Convolution Network
    


Zhongdao Wang^1, Liang Zheng^2, Yali Li^1, Shengjin Wang^1Corresponding author

^1Department of Electronic Engineering, Tsinghua University

^2Australian Centre for Robotic Vision, Australian National University

 
 




    December 30, 2023
===================================================================================================================================================================================================================================






In this paper, we present an accurate and scalable approach 
to the face clustering task. We aim at grouping a set of faces by their potential identities. 
We formulate this task as a link prediction problem: a link exists between two faces if they are of the same identity.
The key idea is that we find the local context in the feature space around an instance (face) contains rich information about the linkage relationship between this instance and its neighbors. 

By constructing sub-graphs around each instance as input data, which depict the local context, we utilize the graph convolution network (GCN) to perform reasoning and infer the likelihood of linkage between pairs in the sub-graphs.

Experiments show that our method is more robust to the complex distribution of faces than conventional methods, yielding favorably comparable results to state-of-the-art methods on standard face clustering benchmarks, and is scalable to large datasets.
Furthermore, we show that the proposed method does not need the number of clusters as prior, is aware of noises and outliers, and can be extended to a multi-view version for more accurate clustering accuracy. [Code available at <https://github.com/Zhongdao/gcn_clustering/>.]





§ INTRODUCTION



In this paper, we study the problem of clustering faces according to their underlying identities. We assume no prior of the distribution of face representations or the number of identities. 
Face clustering is a fundamental task in face analysis and has been extensively studied in previous works <cit.>.
Some key applications include: grouping and tagging faces in desktop / online photo albums for photo management <cit.>, organizing large scale face image / video collections for fast retrieval in time-sensitive scenarios like forensic investigations <cit.>, and automatically data cleaning / labeling for constructing large-scale datasets <cit.>. 




Conventional clustering methods suffer from the complex distribution of face representations, because they make impractical assumptions on data distribution. 
For instance,  K-Means <cit.> requires the clusters to be convex-shaped, Spectral Clustering <cit.> needs different clusters to be balanced in the number of instances, and DBSCAN <cit.> assumes different clusters to be in the same density.
In contrast, a family of linkage-based clustering methods make no assumption on data distribution and achieve higher accuracy. 
As shown in Fig.<ref> (a), linkage-based methods aim at predicting whether two nodes (or clusters) should be linked (are of the same identity).
Fig.<ref> (b) presents a naive solution to this problem by directly linking node pairs whose l_2 distance is under a certain threshold. 
This is apparently not a good solution since the densities of clusters vary a lot.
Therefore, more sophisticated metrics are designed to compute the linkage likelihood, such as the Approximate Rank-Order Distance (see Fig.<ref> (c)). 


Instead of computing the linkage likelihood by heuristic metrics, we propose to learn to predict if two nodes should be linked.



As the key idea of this work, we find that the linkage likelihood between a node and its neighbors can be inferred from its context.

































In order to leverage the valuable information in the context of nodes, we propose a learnable clustering method based on the graph convolution network (GCN), and the main idea is shown in Fig.<ref> (d).   
The framework of the proposed method can be summarized as follow.

Firstly, we formulate clustering as a link prediction problem <cit.>. That is, a link exists between two nodes when their identity labels are identical. 
Secondly, we only predict linkages between an instance and its nearest neighbors.
Accordingly, we construct an Instance Pivot Subgraph around each instance (pivot), to depict the local context, with each node modeling a pivot-neighbor pair.

From IPS, we can perform reasoning to infer which pivot-neighbor pair should be linked and we adopt GCN to learn this task.
Finally,  GCN outputs a set of linkage likelihood, and we transitively merge linked nodes to obtain the clusters.

We show that the proposed method is accurate when compared with the state-of-the-art methods and is scalable in terms of computational complexity.

The proposed method learns to generate linkage likelihood automatically, and results in superior performance to other linkage-based  methods like ARO <cit.> in which the linkage likelihood is computed by heuristic rules.
In addition, our approach is aware of noises and outliers, does not need the number of clusters as input, and is easy to be extended to  a multi-view version for utilizing data from different sources.























The  remainder  of  this  paper  is  organized  as  follows. First,  we briefly  review  the  related  works in  Section  <ref>. Then,  Section <ref> introduces the proposed clustering algorithm. The experimental results are presented in Section <ref> and conclusions are given in Section <ref>.





§ RELATED WORK



Face Clustering. Due to large variations in pose, occlusion, illumination and number of instances, face clusters vary significantly in size, shape and density. 
The complex distribution of face representations makes it unsuitable to apply classic clustering algorithms like K-Means <cit.> and spectral clustering <cit.>, because these methods have rigid assumptions on data distribution.
Several papers develop clustering algorithms based on Agglomerative Hierarchical Clustering (AHC) <cit.>, which is robust in grouping data with complex distribution. Lin  <cit.> propose the proximity-aware hierarchical clustering (PAHC) which exploits a linear SVM to classify local positive instances and local negative instances. Zhu  <cit.> propose a cluster-level affinity named Rank-Order distance to replace the original l_1/l_2 distance, and demonstrate its ability in filtering out noise / outliers. Lin  <cit.> also design a density-aware cluster-level affinity using SVDD <cit.> to deal with density-unbalanced data.
All the above methods yield good performance on unconstrained face clustering, but their computation complexity remains a problem, limiting their application in large-scale clustering.

Fortunately, the Approximate Rank-Order Clustering (ARO) <cit.> provides an efficient framework for large-scale clustering. ARO aims at predicting whether a node should be linked to its k Nearest Neighbors (kNN), and transitively merges all linked pairs. Therefore, the computational complexity of ARO is only O(kn). The kNN search process can be also accelerated by the Approximate Nearest Neighbor (ANN) search algorithm. Accordingly, the overall complexity is O(nlog n) or O(n^2), depending on whether we set k as a constant or let it increase with n. ARO is much more efficient than AHC based algorithms. Shi  <cit.> also adopt ANN to expand their ConPac algorithm to a scalable version. In this work, since the proposed method is based on kNN, it is suitable to exploit this framework as well.

Link Prediction is a key problem in social network analysis <cit.>.
Given a complex network which is organized as a graph, the goal is to predict the likelihood of link between two member nodes. 

To estimate the likelihood of links, some previous works like PageRank <cit.> and SimRank <cit.> analyze the entire graph, while others, such as preferential attachment <cit.> and resource allocation <cit.>, calculate the link likelihood of the given nodes only from their neighbors. 
Zhang and Chen <cit.> argue that it is sufficient to compute link likelihood only from the local neighbor of a node pair, and propose a Weisfeiler-Lehman Neural Machine <cit.> and a graph neural network <cit.> to learn general graph structure features from local sub-graphs. 
It is closely related to our work, since the clustering task can be reduced to a link prediction problem, and we also exploit graph neural networks to learn from local graphs.


Graph convolutional network (GCN). In many machine learning problems, the input can be organized as graphs. 
Considerable research effort <cit.> has been devoted to designing the convolutional neural network for graph-structured data. 
According to the definition of convolution on graph data, GCNs can be categorized into spectral methods and spatial methods.
Spectral based GCNs <cit.> generalize convolution based on Graph Fourier Transform, while spatial based GCNs <cit.> directly perform manually-defined convolution on graph nodes and their neighbors.
In terms of applications, GCNs can handle problems in both the transductive setting <cit.> and the inductive setting <cit.>. 
In the transductive setting, training data and testing data are nodes in a same fixed graph, while in the inductive setting, the model needs to inference across different graphs.

In this work, we propose a spatial-based GCN to solve  link prediction problem. The designed GCN performs graph node classification in the inductive setting. 


§ PROPOSED APPROACH




 §.§ Overview




Problem definition. Assume that we have the features of a collection of face images X = [x_1, ..., x_N]^T∈ℝ^N× D, where N is the number of images and D the dimension of the features, the goal of face clustering is to assign a pseudo label y_i to each 
i ∈{1,2,...,N} so that instances with the same pseudo label form a cluster.
To resolve this problem, we follow the link-based clustering paradigm, which aims at predicting the likelihood of linkage between pairs of instances. 
Accordingly, clusters are formed among all the instances connected by linked pairs. 




Motivation. 
The motivation behind this work is that we find we only need to compute the linkage likelihood between an instance and its k nearest neighbors, and it suffices to produce decent clustering results.
In Table <ref>, we show an upper bound of clustering performance with different values of k. 
To obtain the upper bound, we directly connect each instance with its kNN if the neighbor is of the same identity with this instance. 
The results show that the upper bound is quite high under various values of k.
This indicates the potential effectiveness of predicting linkages between an instance and its kNN, rather than among all potential pairs.
The advantage of adopting such a strategy is that we could obtain reasonably high clustering accuracy while the system has the benefit of being efficient. 













Pipeline. This work focuses on the efficiency and accuracy of a face clustering system. So we adopt the idea of predicting linkages between an instance and its kNNs. 

Because predicting a linkage is based on its context, to make linkage prediction possibly accurate, we design a local structure named Instance Pivot Subgraphs (IPS). 


An IPS is a subgraph centered at a pivot instance p. IPS is comprised of nodes including the kNNs of p and the high-order neighbors up to h-hop of p. 
Importantly, we subtract the feature of pivot p from all these nodes, so that each resulting node feature encodes the linkage relationship between a pivot-neighbor pair.
We present the framework of the proposed approach in the following three steps, and an illustration is shown in Fig. <ref>:


  * We use every instance as a pivot, and construct an Instance Pivot Subgraph (IPS) for it. 
The construction of IPS is described in detail in Section <ref>.

  * Given an IPS as input data, we apply graph convolution networks (GCNs) for reasoning on it and the network outputs a score for every node, , linkage likelihood between the corresponding pivot-neighbor pair. 
The mechanism of GCN is presented in Section <ref>.

  * The above steps output a set of weighted edges among the entire graph, where the weights are the linkage likelihood. 
Finally we transitively merge linked instances into clusters,  according to the linkage likelihood. Details are presented in Section <ref>.














 §.§ Construction of Instance Pivot Subgraph




We estimate the linkage likelihood between two face images (nodes) based on their context in a graph. 

In this paper, we propose to construct the Instance Pivot Subgraph (IPS) as context. IPS is generated by three steps.  

First, we locate all the nodes of IPS. 
Then, we normalize the node features by subtracting the feature of the pivot.
Finally, we add edges among nodes. 
An illustration of Instance Pivot Subgraph generation is presented in Fig. <ref>.




Step 1: Node discovery.
Given a pivot p, we use its neighbors up to h-hop as nodes for IPS. 

For each hop, the  number of picked nearest neighbors may vary.
We denote the number of nearest neighbors in the i-th hop as k_i, i=1,2,...,h. 
For example, let p be the pivot, the node set V_p of the IPS G_p(V_p,E_p) with h=3 and k_1=8, k_2=4, k_3=2 consists of 8 nearest neighbors of p, 4 nearest neighbors of each 1-hop neighbors, and 2 nearest neighbors of each two-hop neighbors. Note that the pivot p itself is excluded from  V_p.
When we do so, the high-order neighbors provide auxiliary information of the local structure of the context between a pivot and its neighbor. 
For instance, for p and one of its neighbors q, if the 
kNN of q are consistently far away from p, then the linkage likelihood between p and q is expected be small.

Step 2: Node feature normalization.
Now we have the pivot instance p, the node set V_p and their node features x_p and {x_q| q∈ V_p}.
In order to encode the pivot information into the node features of IPS, we normalize the node features by subtracting x_p,

    ℱ_p = 
        [, x_q -x_p, ]^T
        
        
        
        
        
        , for all q ∈ V_p,

where we use ℱ_p∈ℝ^|V_p|× D to represent the normalized node features. A node feature in IPS is the residual vector between the feature of the pivot p and the feature of the corresponding neighbor q.

Step 3: Adding edges among nodes.
The last step is to add edges among the nodes. 
For a node q∈ V_p, we first find the top u nearest neighbors among all instances in the original entire collection.
If a node r of the uNNs appears in V_p, we add an edge (q,r) into the edge set E_p. 
This procedure ensures the degree of nodes does not vary too much. 
Finally we represent the topological structure of IPS by an adjacency matrix A_p∈ℝ^|V_p|× |V_p| and the node feature matrix ℱ_p.  We neglect the subscript p 
hereafter.





 §.§ Graph Convolutions on IPS


The context  contained in IPS (edges among the nodes) is highly valuable for determining if a node is is positive (should link to the pivot) or negative (should not link to the pivot).  
To leverage it, we apply the graph convolution networks (GCN) <cit.> with slight modifications to perform reasoning on IPS.

A graph convolution layer takes as input a node feature matrix X together with an adjacency matrix A and outputs a transformed node feature matrix Y.
In the first layer, the input node feature matrix is the original node feature matrix, X=ℱ.
Formally, a graph convolution layer in our case has the following formulation,

    Y = σ([XGX]W),

where X∈ℝ^N× d_in, Y∈ℝ^N× d_out, N is the number of nodes, and d_in, d_out are the dimension of input / output node features.

G = g(X,A) is an aggregation matrix of size N × N and each row is summed up to 1, and g(·) is a function of X and A. 
Operator  represents matrix concatenation along the feature dimension.
W is the learnable weight matrix of the graph convolution layer of size 2d_in× d_out, and
σ(·) is the non-linear activation function.

The graph convolution operation can be broken down into two steps. In the first step,
by left multiplying X by G, the underlying information of nodes' neighbors is aggregated.
Then, the input node features X are concatenated with the aggregated information GX along the feature dimension.
In the second step, the concatenated features are transformed by a set of linear filters, whose parameter W is to be learned.
The following three strategies g(·) for the aggregation operation is explored.

    
  * Mean Aggregation. The aggregation matrix G=Λ^-1/2AΛ^-1/2, where A is the adjacency matrix and Λ is a diagonal matrix with Λ_ii=∑_j A_ij. 
    The mean aggregation performs average pooling among neighbors.
    

    
  * Weighted Aggregation.
    We replace each non-zero element in A with the corresponding cosine similarity, and use softmax function to normalize these non-zero values along each row. 
    The weighted aggregation performs weighted average pooling among neighbors.
    

    
  * Attention Aggregation. Similar to the graph attention network <cit.>, we attempt to learn the aggregation weights of neighbors. That is, the elements in G are generated by a two-layer MLP using the features of a pair of pivot-neighbor nodes as input. The MLP is trained end-to-end. The attention aggregation performs weighted average pooling among neighbors, where the weights are learned automatically.


The GCN used in this paper is the stack of four graph convolution layers activated by the ReLU function. 
We then use the cross-entropy loss after the softmax activation as the objective function for optimization.

In practice, we only backpropagate the gradient for the nodes of the 1-hop neighbors, because we only consider the linkage between a pivot and its 1-hop neighbors. 
This strategy not only leads to considerable acceleration compared with the fully supervised case, but  also brings about accuracy gain. The reason is that the high-order neighbors are mostly negative, so the positive and negative samples are more balanced in 1-hop neighbors than in all the neighbors.
For testing, we only perform node classification on the 1-hop nodes as well.

To demonstrate the working mechanism of graph convolutions, we design a toy example with 2-D input node feature and two graph convolution layers.
The output dimension of each layer, d_1 and d_2, is set to 2 for visualization purpose.

In Fig. <ref>, we show how the output embeddings in each layer vary with training iterations. 

After each graph convolution layer, positive nodes (red) are grouped closer, and the negative nodes (blue and green) form another group. This is because messages of neighbors are passed to nodes in the aggregation step, and the message from neighbors acts as a smoothness for the embedding that pulls linked nodes together, like these nodes are connected by springs. Meanwhile, the supervision signal pushes away the group of positive nodes and the group of negative nodes. 
Finally, the system reaches its equilibrium point, where positive and negative groups are far from each other and nodes in the same category are close.





 §.§ Link Merging


To apply clustering on a collection of face data, we loop over all the instances, construct an IPS with each instance as the pivot, and predict the likelihood of linkage (the softmax probability output by the node classifier) between the involved instances and the pivot.
As a result, we have a set of edges weighted by the linkage likelihood. 
To acquire clusters, a simple approach is to cut all the edges whose weight is below some threshold and use Breath First Search (BFS) to propagate pseudo labels, as shown in Fig. <ref>. 
However, the performance can be sensitively affected by the threshold value. We accordingly adopt the pseudo label propagation strategy proposed in <cit.>. 
In each iteration, the algorithm cuts edges below some threshold and maintain connected clusters whose size are larger than a pre-defined maximum size in a queue to be processed in the next iteration.
In the next iteration, the threshold for cutting edges is increased. This process is iterated until the queue is empty, which means all the instances are labeled with pseudo labels.



§ EXPERIMENT





 §.§ Evaluation Metrics and Datasets



To evaluate the performance of the proposed clustering algorithm, we adopt two mainstream evaluation metrics: normalized mutual information (NMI) and BCubed F-measure <cit.>. 
Given Ω the ground truth cluster set, C the predicted cluster set, NMI is defined as, 

    NMI(Ω, C) = I(Ω, C)/√(H(Ω)H(C)),

where H(Ω) and H(C) represent the entropies for Ω and C, and I(Ω,C) is the mutual information. 

BCubed F-measure <cit.> is a more practical measurement which takes both precision and recall into consideration. 

Let us denote L(i) and C(i) as the ground truth label and cluster label, respectively, we first define the pairwise correctness as, 

    Correct(i,j) = 
        {[                         1, if L(i)=L(j) and C(i)=C(j);                         0,                  otherwise ].
        .

The BCubed Precision P and BCubed Recall R  are respectively defined as,

    P = 𝔼_i[𝔼_j:C(j)=C(i)[Correct(i,j)]],


    R = 𝔼_i[𝔼_j:L(j)=L(i)[Correct(i,j)]],

and the BCubed F-measure is defined as F = 2PR/P+R.


We use separate datasets for training and testing. First,  we use   ArcFace <cit.>[https://github.com/deepinsight/insightfacehttps://github.com/deepinsight/insightface] as the face representations. This model is trained on the union set of MS-Celeb-1M <cit.>  and VGGFace2 <cit.> dataset. Second, for GCN training, we use a random subset of the CASIA dataset <cit.> which contains  5k identities and 200k samples. Third, for testing, we adopt the IJB-B dataset <cit.> because it contains a clustering protocol. The protocol consists of seven subtasks varying in the number of ground truth identities. 
We evaluate our algorithm on three largest subtasks. In the three subtasks, the numbers of identities are 512, 1,024 and 1,845, and the numbers of samples are 18,171, 36,575 and 68,195, respectively. 
















 §.§ Parameter Selection


There are three hyperparameters for IPS construction: the number of hops h, the number of picked nearest neighbors in each hop {k_i}, i=1,2,...,h, and the number of linked nearest neighbors u for picking edges. 
We first experiment with different values of h and find that h≥3 does not bring performance gain, so we set h=2 in the following experiment.
Accordingly, we explore the impact of different values k_i, k_2 and u.
We discuss both the training phase and the testing phase.

In the training phase, we expect more supervision signals to be back-propagated.
Since supervision is only added to 1-hop nodes, we select a large  k_1=200.
In order to avoid IPS being too large, we set a small value k_2=10. 
We also set u=10 to ensure every 2-hop node has at least one edge.

In the testing phase, it is not necessary to keep the same configuration with the training phase. To investigate how  k_1, k_2 and u influence the performance, we conduct two group of experiments and the the results are shown in Fig. <ref>. 
First, we keep u constant, vary k_1, k_2, and show how F-measure changes on 1JB-B-512. 


We observe in Fig. <ref> (a) that the F-measure increases with larger k_1 and k_2.
Larger k_1 brings more candidate links to be predicted, thus yields higher recall.
Larger k_2 involves more 2-hop neighbors, depicting the local structure of 1-hop neighbors more precisely, so the prediction is more accurate.
However, the performance reaches saturation when k_1 and k_2 are large enough.
For the parameter u, , the linked number of neighbors, we observe in <ref> (b) that the performance is not sensitive to the value of u.

Taking efficiency into consideration, the values of k_1 and k_2 cannot be too large. 
We find that k_1=80, k_2=5, u=5 yield a good trade-off between efficiency and performance and use this setting in the following experiment. 



 §.§ Evaluation

The proposed approach is compared to the following methods: K-means <cit.>, Spectral Clustering <cit.>, Agglomerative Hierarchical Clustering (AHC) <cit.>, Affinity Propagation (AP) <cit.>, Density-Based Spatial Clustering of Applications with Noise (DBSCAN) <cit.>, Proximity-Aware Hierarchical Clustering (PAHC) <cit.>, Deep Density Clustering (DDC) <cit.>, Conditional Pair-wise Clustering (ConPaC) <cit.>, and Approximate Rank-Order Clustering (ARO) <cit.>.
For all the methods, we tune the hyperparameters , σ in Spectral Clustering and ϵ, n in DBSCAN , 
and report the best results.
For non-deterministic algorithms like K-means we select the best result from 100 runs. 

Comparing different aggregation methods. 
We first compare the aggregation strategies described in Section <ref>. 
In Table <ref>, GCN-M refers to Mean Aggregation, GCN-W refers to Weighted Aggregation, and GCN-A refers to Attention Aggregation. 
The Attention Aggregation learns the aggregation weights of neighbors automatically in an end-to-end manner, yielding marginally better performance than Mean Aggregation and Weighted Aggregation. 
Considering the computation cost, the improvement is not significant, so we use Mean Aggregation in the following experiment.

Comparison with baseline methods. 
The top part of Table <ref> showcases results of several widely used clustering algorithms. 
The results suggest algorithms that make less restrictive assumptions on  data distribution usually achieve higher performance. 
For instance, there is no assumptions on data distribution in AHC and the performance is the best.
DBSCAN requires the data to have similar density and the performance is inferior to AHC. 
K-means needs the data to be convex-shaped, and Spectral Clustering is not good at handling unbalanced data, thus both yield unsatisfactory results. 
Same as AHC, our approach does not make any assumptions on the data distribution, and the clustering rule is learned by a parametric model, therefore it is not surprising the performance is superior to the strong AHC baseline.
This is  not a trivial result, since the performance of AHC is sensitive to the threshold, while ours is not sensitive to parameter selection and consistently outperforms AHC.




Comparison with state-of-the-art. 
In the second part of Table <ref> we compare our method with four state-of-the-art face clustering algorithms, , ARO <cit.>, PAHC <cit.>, ConPaC <cit.> and DDC <cit.>. 


The proposed method consistently outperforms other method on the three subtasks in term of both F-measure and NMI score. 
Note that the results of PAHC and ConPac may not be compared directly since different face representations are employed. However, we find that both of them underperform the corresponding AHC baseline (with the same face representation), while our method surpass the AHC baseline. 

This shows the accuracy of our mehtod is favorably comparable to the state-of-the-art face clustering algorithms.


Different face representation.  To validate that the benefit is indeed from the algorithm rather than the strong ArcFace feature, we train a face recognition model using ResNet-50 <cit.> + Softmax Loss on the MS1M dataset <cit.>, and test clustering methods with such representation. Method comparison under Res-50 representation is shown
in Table. <ref>. Combined with Table. <ref>, the results show that:

(1) When stronger representation is adopted (Arcface),
our method yields better performance. This indicates our
method is able to benefit from better representation.

(2) When using the same representation, our method outperforms state-of-the-art methods. This indicates our method
has superior performance to prior arts.




Singleton Clusters.








In practice, we find our approach produces many singleton clusters, , clusters that contain only a single sample.
The proportion of the generated singleton clusters among the whole collection varies with the hyperparameters in the merging step. 
We examine singleton samples and find that most of the them are extreme hard samples, ,  profile faces, low-resolution faces or blurred faces,
also non-face images due to the failure of face detection, and mis-labeled faces.
We filtered all the singleton clusters and re-test the F-measure and NMI score on IJB-B-512.
For a fair comparison, we also report the performance of other three linkage based clustering methods after removing singleton clustering. 
We manually tune the hyperparameters in each algorithm to let  the proportion of singleton instances vary, then remove singleton clusters and compute  F-measure and NMI score.

Finally We plot the curves of the two metrics as the proportion of singleton clusters varies in Fig. <ref>.
ARO, DBSCAN and our method present ascending cureves, which means these methods are able to filter out noise and outliers. 
By tuning hyperparameters to be stricter, these methods generate more singleton clusters, and the remained non-singleton clusters are more accurate. 
In contrast, AHC presents a plain curve, so the accuracy of generated clusters is not controllable by tuning hyperparameters.
With the same proportion of singleton clusters, our method consistently outperforms other algorithms. 
Furthermore, clusters generated by our method are in pretty high purity, with a moderate sacrifice in instance number (say 0.943 F-measure with 15.2% instances discarded).

This is a valuable property in applications like automatically data labeling, where the purity is important.




Scalability and Efficiency. 
The proposed method only operate on local IPS, hence the runtime of link prediction process grows linearly with the number of data. 
The IPS construction has an O(n^2) complexity if we search nearest neighbor by brute force, and can be reduced to O(nlog n) by Approximate Nearest Neighbor (ANN) search.
In general, the overall complexity of our method is O(nlog n), which means it is efficient and scalable.
Here we perform a large-scale experiment by introducing 1 million distractors to the IJB-B-1845 dataset, to investigate the efficiency of our method. 
We use the whole Megaface <cit.> dataset as distractors, which comprises of 1 million irrelevant face images. 
F-measure and NMI score are then computed by simply ignoring the distractors.
As shown in Table <ref>,  the runtime and performance is influenced by k_1, and we can tune the k_1 for accuracy-time trade-off. All the experiment are performed on a single Titan Xp GPU, and one can use more for acceleration since our algorithm is suitable for parallelism.



 §.§ Multi-View Extension

In many real-world applications, data may come from multiple sources and contain complementary information, known as "multi-view data". 
Multi-View clustering aims at exploiting such data to generate better clusters. 
In this section, we show our clustering method is easily extended to a multi-view version, and also adaptive to different base features.

We apply the proposed clustering method to video face clustering task, where two views of data, namely face features and audio features, can be extracted to depict a person. 

The face features and the audio features are extracted by two CNNs and then simply concatenated as a joint representation, accordingly the training and inference procedures of the GCN are the same as described above. 

We adopt VoxCeleb2 <cit.> dataset for training the GCN and evaluating the clustering results. 
The VoxCeleb2 dataset comprises of 145K videos of 5,994 different identities, and we split it into a test set consisting of 2,048 identities and a disjoint training set.
We propose two clustering protocols which consist of 22,568 instances of 512 identities and 83,265 instances of 2,048 identities, respectively. 
Several clustering methods are compared with three different base features, namely face, audio and face+audio, and the results are presented in Table <ref> and Table <ref>.



The distribution of the concatenated face+audio features are more complex than the single face / audio features, therefore some heuristic clustering methods fail to leverage the complementary information (face features outperform face+audio features). 
In contrast, the proposed method learn the clustering rule by a parametric model, thus is able to handle such data distribution, and brings about performance gain from multi-view data.








This series of experiment show 
our clustering method can be 1) easily extend to a multi-view version, only if training data is provided, and 
also 2) adaptive to different base features.







§ CONCLUSION


In this paper, we propose a linkage based  method for face clustering. 
We emphasize the importance of context in face clutering and propose to construct instance pivot subgraphs (IPS) that depict the context of given nodes. On IPS, We use the graph convolution network to reason the linkage likelihood between a given node and its neighbors.
Extensive experiment indicates the proposed method is more robust to the complex distribution of faces than conventional methods. We report favorably comparable results to state-of-the-art methods on standard face clustering benchmarks and show our method is scalable to large datasets. Finally, we demonstrate the strength of our method in visual-audio face clustering. 



§ ACKNOWLEDGEMENT

This work was supported by the state key development program in 13th Five-Year under Grant No. 2016YFB0801301 and the National Natural Science Foundation of China under Grant Nos. 61771288、61701277.

ieee



