Hierarchical Cluster-based Open-World Graph Active Learning

Existing works in graph active learning (GAL) mostly assume a closed-world setting where all classes are known in advance, while in practice, we need to deal with the open-world setting where novel classes are encountered during learning. Apart from selecting informative nodes for refining the current classifier, the open-world GAL algorithms are also expected to discover novel classes. Motivated by the observation that identifying an informative region can be easier than finding the most informative example, we propose a novel hierarchical cluster-based algorithm for open-world GAL. Our algorithm performs clustering in the feature space to identify an informative region which either contains informative examples for known classes or novel classes, then performs a novel semi-supervised sub-clustering on the selected cluster to identify the most informative example. To facilitate the discovery of informative regions, we introduce a cluster-based self-distillation loss between ego and final embeddings to learn well-clustered node embeddings that are more likely to align with the classes. We also introduce a novel cluster informativeness score for the clusters, which measures not only how uncertain the cluster is (similar to standard active learning algorithms), but whether the cluster is likely to contain novel classes. Our semi-supervised sub-clustering algorithm partitions the selected cluster into subregions for known classes and an additional uncertain subregion, then we query the label for a representative node for the uncertain subregion. Extensive experiments on five benchmark datasets demonstrate the effectiveness of the proposed method with a more balanced improvement over novel classes. Ablation study shows that our cluster-based self-distillation loss, informativeness score, and the semi-supervised sub-clustering strategy are all beneficial. Empirical analysis also reveals how our informativeness score is effective for novel class discovery and identifying informative examples for refining the decision boundary.