  In recent years, benefiting from the expressive power of Graph Convolutional
Networks (GCNs), significant breakthroughs have been made in face clustering
area. However, rare attention has been paid to GCN-based clustering on
imbalanced data. Although imbalance problem has been extensively studied, the
impact of imbalanced data on GCN- based linkage prediction task is quite
different, which would cause problems in two aspects: imbalanced linkage labels
and biased graph representations. The former is similar to that in classic
image classification task, but the latter is a particular problem in GCN-based
clustering via linkage prediction. Significantly biased graph representations
in training can cause catastrophic over-fitting of a GCN model. To tackle these
challenges, we propose a linkage-based doubly imbalanced graph learning
framework for face clustering. In this framework, we evaluate the feasibility
of those existing methods for imbalanced image classification problem on GCNs,
and present a new method to alleviate the imbalanced labels and also augment
graph representations using a Reverse-Imbalance Weighted Sampling (RIWS)
strategy. With the RIWS strategy, probability-based class balancing weights
could ensure the overall distribution of positive and negative samples; in
addition, weighted random sampling provides diverse subgraph structures, which
effectively alleviates the over-fitting problem and improves the representation
ability of GCNs. Extensive experiments on series of imbalanced benchmark
datasets synthesized from MS-Celeb-1M and DeepFashion demonstrate the
effectiveness and generality of our proposed method. Our implementation and the
synthesized datasets will be openly available on
https://github.com/espectre/GCNs_on_imbalanced_datasets.
