  Node classification on graphs is of great importance in many applications.
Due to the limited labeling capability and evolution in real-world open
scenarios, novel classes can emerge on unlabeled testing nodes. However, little
attention has been paid to novel class discovery on graphs. Discovering novel
classes is challenging as novel and known class nodes are correlated by edges,
which makes their representations indistinguishable when applying message
passing GNNs. Furthermore, the novel classes lack labeling information to guide
the learning process. In this paper, we propose a novel method Open-world gRAph
neuraL network (ORAL) to tackle these challenges. ORAL first detects
correlations between classes through semi-supervised prototypical learning.
Inter-class correlations are subsequently eliminated by the prototypical
attention network, leading to distinctive representations for different
classes. Furthermore, to fully explore multi-scale graph features for
alleviating label deficiencies, ORAL generates pseudo-labels by aligning and
ensembling label estimations from multiple stacked prototypical attention
networks. Extensive experiments on several benchmark datasets show the
effectiveness of our proposed method.
