Beyond the Known: Novel Class Discovery for Open-world Graph Learning

Applying a clustering algorithm with polynomial time complexity on the small prototype graph $(\mathcal{C},\mathcal{E}^{p})$ instead of the whole graph can substantially ease the computational burden, where $\mathcal{E}^{p}=\{(\mathbf{c}_{i},\mathbf{c}_{j},{s}_{ij})\}$. Given the groups $\mathcal{C}^{g}=\{\mathcal{C}_{1}^{g},\cdots,\mathcal{C}_{N_{clu}}^{g}\}$ discovered by clustering on prototypes, the assignment probability of a node $v_{i}$ to a group $\mathcal{C}_{k}^{g}$ can be approximated according to their relationship scores with prototypes,

Despite prototype-based clustering can improve efficiency significantly, the labeling granularity which decides the class (cluster) number is still unknown. However, overly fine-grained clustering can cluster nodes of the same class into different clusters, while overly coarse-grained clustering can cluster nodes of different classes into the same cluster. Both cases lead to drops in clustering accuracy. Therefore, we search for the optimal clustering granularity by maximizing the accuracy on the labeled known class nodes. The clustering accuracy is calculated as,

where $\mathds{1}$ is the indicator function and $\hat{y}_{i}$ is the predicted group ID. Considering the potential misalignment between between class and groups IDs, we find the alignment function from the set of all permutations $\mathcal{P}(\mathcal{Y}^{L})$ by solving the maximization problem through the Hungarian algorithm [16]. Groups do not match with any known class are regarded as discovered novel classes.

Besides local attribute information on nodes, the neighborhood information on graphs has also been shown to be important for node classification [2, 12, 13, 15, 23]. However, due to the existence of edges between known class nodes and novel class ones, aggregating all neighborhood information with existing graph convolution layers can make different classes indistinguishable in the representation space. Despite graph attention networks can assign different weights to different neighbors, which are not guaranteed to contain knowledge about how to distinguish each novel class from others.

To learn compact representations for novel class discovery, we propose the group-aware attention mechanism. Group assignments predicted by semi-supervised prototypical learning are approximations of the ground-truth labels, which can be utilized to eliminate correlations between novel and known classes during neighborhood aggregation. The group-aware attention mechanism calculates the attention scores for neighbors according to the group assignment similarities $e_{ik}=\cos{(\mathbf{p}_{i},\mathbf{p}_{k})}$, where $\mathbf{p}_{i}=[p_{i1},\ldots,p_{iN_{clu}}]$,

The low group assignment similarities between novel and known class nodes lead to low attention weights, while the attention weights between nodes from the same class are high. Consequently, aggregating information according to the group assignments can eliminate correlations between classes due to the low attention weights on inter-class edges, obtaining compact representations,

where $\sigma$ is the relu activation function. By stacking multiple prototypical attention networks, ORAL further predicts over the representation $\mathbf{h}_{i}^{*}$ obtained after selectively aggregating neighborhood information. Consequently, we get access to a list of predictions as well as node representations, $\{(\mathbf{p}^{(1)},\mathbf{h}^{(1)}),...,(\mathbf{p}^{(L)},\mathbf{h}^{(L)})\}$, calculated at different scales using different hops of neighborhood information, where $L$ is the number of layers, $(\mathbf{p}^{(i)},\mathbf{h}^{(i)})$ is the group assignments and representations generated by the $i$-th prototypical attention network. The prototypical attention networks are trained by the cross-entropy loss layer by layer,

where $y_{i}$ is the label of node $v_{i}$ and $p^{(l)}_{iy_{i}}$ is the predicted probability of node $i$ belonging to the $y_{i}$-th group (class) in the $l$-th layer.

ORAL introduces the pseudo-label generator to mitigate the lack of novel class labeling information. To fully leverage the rich information captured at different scales, ORAL ensembles prediction results estimated by multiple stacked prototypical attention networks. However, ensembling multiple group assignment results is non-trivial. Due to the unsupervised nature of novel class discovery, groups from different layers are not aligned, even the number of groups varies from layer to layer.

We overcome these challenges through the proposed padding, aligning and suppressing operation. Given the set of predictions $\{\mathbf{p}^{(1)},...,\mathbf{p}^{(L)}\}$, we first pad them with zero vectors such that they have the same number of prototype groups. Then we align and ensemble predictions from different layers by the Hungarian algorithm [16],

where $j_{k}$ denotes the prototype group ID in the k-th layer that corresponds to the j-th group in the initial layer. $\hat{p}_{ij}$ is the probability of assigning node $i$ to group $j$ obtained from ensemble inference. Groups which only exist in a certain layer or associates with almost no nodes can be regarded as detection noise. We suppress neurons responding to these noisy groups by masking over the prediction results,

where the mask $\mathbf{m}$ is calculated by comparing the group popularity with a pre-defined threshold $\eta$, $m_{i}=\mathds{1}(\frac{1}{|\mathcal{V}|}\sum_{i}\hat{p}_{i,j}>\eta)$. The symbol $\odot$ stands for the element-wise product. For each known class and discovered novel class, we select reliable pseudo labels as the labeling information on confident node subset, which is the top $\gamma$ percentage of unlabeled nodes with the highest prediction probability (confidence) of belonging to this label.

Reliable pseudo-labels information is incorporated into the input graph data for guiding open-world learning. Specifically, we recover intra-class edges to increase similarities between nodes of the same pseudo-label, while eliminating inter-class edges to decrease inter-class similarities. Structure refining according to pseudo-labeling makes it easier to distinguish novel classes from others.

Recovering intra-class edges according to pseudo-labels can introduce information from unconnected nodes in the original graph for open-world learning. However, excessive edge recovery can result in over-smoothing. We select the top $\mu$ percent of intra-class node pairs with the lowest similarities as recovered edges $\mathcal{E}_{+}$, where the similarity is calculated according to their relationship scores to prototypes in Eq. 1,

where $\mathbf{r}^{(l)}_{i}$ is the relationship between nodes and prototypes in the l-th layer. Consequently, edges between intra-class nodes associated to different prototypes are recovered, which increases similarities between prototypes related to the same class and facilitates more accurate semi-supervised prototypical clustering for novel class discovery.

ORAL further eliminate inter-class edges $\mathcal{E}_{-}$ according to pseudo-labeling. Since ensemble pseudo-labeling incorporates knowledge from different layers, taking the refined structure as input for each prototypical attention layer can transfer knowledge to eliminate unwanted correlations between classes among layers. The final refined structure can be formulated as,

To make ORAL robust to the noise introduced during the structure refining process, we introduce the permutation-consistent training loss, which augments the structure information with the adaptive augmentation technique [36] and regularizes the prediction consistency between different views,

where $\bar{\mathbf{p}}_{i}^{(l)}$ is the prediction over the augmented graph. The overall training loss can be calculated as,

The final predictions on unlabeled nodes can be obtained based on Eq. (LABEL:Eq_ensemble). The training process is summarized in Algorithm 1.

We test our method on three commonly used datasets: (1) Cora [32] is the citation network where classes are subjects of scientific publications. (2) AmazonPhoto [25] is the co-purchase network with categories of goods as node labels. (3) BlogCatlog [19] is the blog network where node labels are topics of blogs. The dataset statistics is shown in Table 1. For each dataset, we sample 80 percent of classes for which we have labels during training, the remaining ones are novel classes emerged in the test set. We further sub-sample 70 percent and 15 percent of the nodes from known classes to constitute the labelled training set and validation set. The remaining nodes from known classes, along with all instances from novel classes, constitute the unlabeled test node set $V_{U}$.

Following the novel class discovery literature [18, 27] in the CV domain, we conduct experiments in scenarios where the number of classes is known as well as in scenarios where it is unknown. The model performance is measured with clustering accuracy, since the label IDs of ground-truth labeling and predictions may not be aligned. Similar to Equation 4, the clustering accuracy on test nodes can be calculated as,

Besides the main metric indicating the classification performance over all testing nodes, we further report values for both known class subset (nodes in $\mathcal{V}_{U}$ belonging to classes in $\mathcal{Y}^{L}$) and novel classes subset (nodes in $\mathcal{V}_{U}$ belonging to classes in $\mathcal{Y}^{U}\setminus\mathcal{Y}^{L}$).

We choose the following methods as baselines, which can be classified into the three families. (1) Semi-supervised Approach. GCN [15] is a popular graph convolution network for semi-supervised node classification, which is unable to discover novel classes and will mistakenly classify novel class nodes into known classes.(2) Unsupervised Approach. VGAE [14] is an unsupervised method to learn graph embeddings. We extend this method for open-world graph learning by combining VGAE with the non-parametric kmeans classifier, where the number of classes is assumed to be a known prior. (3) Open-world Semi-supervised Approaches. GCD [27] is the most popular method for discovering novel categories in the CV domain, which estimates the number of novel classes by maximizing the clustering accuracy on labeled instances. OpenNCD [18] is the state-of-the-art method for open-world semi-supervised learning. Considering the performance decrease caused by non-parametric classifier in GCD, OpenNCD replaces the kmeans classifier with learnable prototypes and trains the network with a novel progressive bi-level contrastive learning method. We abbreviate OpenNCD as OCD in this article. We extend these methods to open-world graph learning by replacing the encoding module with graph convolution layers [15]. When the number of novel classes is known as a prior, both open-world semi-supervised baselines and ORAL search for the clustering granularity where the number of clusters (classes) matches with the prior knowledge.