G2Pxy: Generative Open-Set Node Classification on Graphs with Proxy Unknowns

1 Introduction

Node classification is the task of assigning labels (categories) to unlabeled graph nodes. This task has many important applications such as traffic state prediction [Zheng et al., 2020], and completing user profiles in social networks [Wong et al., 2021]. Graph Neural Network (GNN) based methods [Zhu et al., 2022; Liu et al., 2021] achieve state-of-theart performance for this problem. However, they generally assume that the full set of labels (known classes) is available for training. Unfortunately, this assumption does not hold in many practical scenarios because of unforeseen factors. For instance, a trained GNN may be applied on samples from a research social network where researchers may have published in new conferences that were unseen in training. When facing samples of unknown classes, typical GNN methods [Kipf and Welling, 2017; Veliˇckovi´c et al., 2018; Hamilton et al., 2017] will incorrectly label nodes using known classes, which can considerably degrade performance. Hence, building models that can classify samples from known classes and reject samples from unknown classes is a key issue, which is known as the open set classification problem.

∗Corresponding author.

Recent techniques that have been designed to address the open-set node classification problem [Wu et al., 2021] presume that a model will be more confident in its predictions for closed-set samples than for open-set samples. Relying on this assumption, a threshold is applied on a model's confidence scores to separate unknown samples from known ones. Though this approach is intuitive [Hendrycks and Gimpel, 2017], it often fails because deep neural networks tend to be over-confident in input samples and may output high confidence scores even for an unknown input [Hein et al., 2019; Guo et al., 2017; Bendale and Boult, 2016; Scheirer et al., 2012]. Moreover, finding an optimal threshold to separate known from unknown classes is hard and timeconsuming [Perera et al., 2020; Ge et al., 2017].

Another critical challenge for open-set classification is the lack of open-set data. It is hard to collect open-set data due to the very large diversity. However, most of the prior solutions [Wu et al., 2020] follow a transductive learning approach, i.e., suppose that part or all of the features of the real unseen class samples can be observed and used to help with open-set learning. This setting is not suitable for most realworld applications. To alleviate this issue, several studies on image classification have attempted to estimate the distribution of unknown classes and calibrate a network's confidence. For example, G-OpenMax [Ge et al., 2017] utilizes a GAN to generate unknown samples for training an image classifier. Neal et al. [Neal et al., 2018] introduced a counterfactual image generation method to produce image samples lying between decision boundaries through GANs. Perera et al. [Perera et al., 2020] combined self-supervision and a generative model to enhance the optimal closed-set features and to effectively identify open-set samples. PROSER [Zhou et al., 2021] learns placeholders to prepare for unknown classes by allocating placeholders for both data and classifier, which yields high disparity.

Motivated by the above studies, we propose a novel Generative open-set node classification method on Graphs with Proxy unknowns (G 2Pxy for short). Under the constraints of not being able to obtain open-set data, G 2Pxy first generates pseudo unknown class nodes (unknown proxies) via mixup [Verma et al., 2019; Han et al., 2022], to mimic the distribution of unknown classes using only the closedset graph for learning. Two kinds of proxy unknown nodes, inter-class unknown proxies and external unknown proxies, are generated. Using the generated proxies, a closed-set classifier can be transformed into an open-set one, by augmenting it with an extra proxy classifier. The whole model is optimized under the supervision of cross entropy and tailored complement entropy loss [Chen et al., 2018] together, and can then adaptively perform class-specific classification and detection during testing. Moreover, G 2Pxy can be adopted by different kinds of GNNs and shows good generalizations. The contributions of this paper are summarized as follows:

• A novel method G 2Pxy for open-set node classification is proposed with efficient unknown proxy generation and open-set classifier learning, under the constraint of both cross entropy and complement entropy loss. To the best of our knowledge, G 2Pxy is the first generative method for open-set graph learning.
• No open-set data (samples of unknown classes or any side information of unknown classes) is required during training and validation. G 2Pxy has an explicit classifier for unknown and does not require tuning a threshold.
• G 2Pxy does not have specific requirement on the GNN architecture, and shows good generalizations. Using mixup as the generative method also ensures the efficiency, due to the acceptable extra computation cost.
• Experiments on benchmark graph datasets demonstrate the good performance of G 2Pxy.

2 ProblemDefinition &Preliminary

This paper focuses on the node classification problem for a graph. Consider a graph denoted as G = (V,E,X), where V = {vi|i = 1, . . . ,N} is a set of N nodes in the graph. E = {ei,j|i, j = 1, . . . ,N. i ̸= j} is a set of edges between pairs of nodes vi and vj. X ∈ RN×d denotes the feature matrix of nodes, and d is the dimension of node features. xi ∈ X indicates the feature vector associated with each node vi. The topological structure of G is represented as an adjacency matrix A ∈ RN×N , where Ai,j = 1 if the nodes vi and vj are connected, i.e., ∃ei,j ∈ E, otherwise Ai,j = 0. Y ∈ RN×C is the label matrix of G, where C is the already-known node classes. If node vi ∈ V is associated with a label c, yi,c = 1, otherwise, yi,c = 0.

For a typical closed-set node classification problem, a GNN encoder fθg takes node features X and adjacency matrix A as input, aggregates the neighborhood information and outputs representations. Then, a classifier fθc is used to classify the nodes into C already-known classes. The GNN encoder and the classifier are optimized to minimize the expected risk [Yu et al., 2017] in Eq. (1), with the assumption that test data Dte and train data Dtr share the same feature space and label space, i.e.,

where H is the hypothesis space, I(·) is the indicator function which outputs 1 if the expression holds and 0 otherwise. Generally, it can be optimized with cross-entropy to discriminate between known classes.

In open-set node classification problem, given a graph G = (V,E,X), Dtr = (X, Y ) denotes the train nodes. Dte = (Xte, Yte) is the test nodes, where Xte = S ∪ U, Yte = {1, . . . , C, C+1, . . .}. S is the set of nodes that belong to seen classes that already appeared in Dtr and U is the set of nodes that do not belong to any seen class (i.e., unknown class nodes). Open-set node classification aims to learn a (C + 1)- class classifier fθc that f(θg, θc;Xte,A) : {Xte,A} → Y, Y = {1, . . . , C, unknown}, with the minimization of the expected risk [Yu et al., 2017]:

where A is the adjacency matrix for Xte. The predicted class unknown ∈ Y contains a group of novel categories, which may contain more than one class. Thus, the overall risk aims to classify known classes while also detecting the samples from unseen categories as class unknown.

From close-set to open-set classifier, an intuitive way is thresholding [Hendrycks and Gimpel, 2017]. Taking the max output probability as confidence score, i.e., conf = maxc=1,...,Cfc(x,A), it assumes the model is more confident in closed-set instances than open-set ones. Then we can extend a closed-set classifier by

where τ is a threshold. However, due to the overconfidence phenomena of deep neural networks, the output confidence of known and unknown is both high [Bendale and Boult, 2016]. As a result, tuning a threshold that well separates known from unknown is hard and time-consuming.

Differently, the approach presented in this paper utilizes an additional proxy classifier to detect the unknown class nodes, with well-designed generated unknown proxies to facilitate the model training. There are advantages of adding a class instead of optimizing a threshold as in previous methods [Shu et al., 2017; Wu et al., 2020; Bendale and Boult, 2016], since it does not require real open-set samples in validation and also eliminates the difficulty of tuning the threshold.

3 Methodology

Facing the difficulty of closed-set classifier calibration, we need proxy unknown nodes to foresee the distribution of unknown classes and prepare the open-set model for novel classes.

The overall framework of G 2Pxy is introduced in Fig. 1. Specifically, a GNN encoder fθ1 takes node features X and adjacency matrix A as input, aggregates the neighborhood information and outputs representation hki for each node vi in its k-th layer, k = 1, . . . ,K. K is the total number of layers. Thus, in the k-th layer, for node vi, the GNN encoder aggregates neighbor information from the k-1 layer into a neighborhood representation:

where hki ∈ Rdk is the hidden representation at the k-th layer, Ni is the neighborhood of node vi and h0 = X.

Meanwhile, we mimic novel patterns by generating proxy unknown nodes through manifold mixup [Verma et al., 2019; Han et al., 2022]. Targeted node pairs are selected and mixed up at the middle layer of the GNN, and two kinds of proxies are created: inter-class unknown proxies that separate known classes from each other and external unknown proxies that separate known from unknown. Generated proxies and original known class nodes are input into the remaining layers together to learn discriminative representations. Then, a classifier fθ2 is learned to classify the nodes into C + 1 classes, achieving open-set node classification.

To conclude, the proposed G 2Pxy method consists of two main modules: 1) a proxy node generation module to create proxy unknown class nodes; 2) an open-set classifier learning module to guarantee the classification of known classes and the rejection of the unknown class. We introduce them in details.

3.1 Proxy Node Generation

As out-of-distribution nodes are unavailable during training, we propose an effective way of generating proxy unknown nodes, which are designed to be located at the boundaries between different classes. These nodes are utilized in the learning process to supervise and tell apart unknown nodes from known ones. Specifically, two different kinds of proxies are produced, inter-class unknown proxies and external unknown proxies. We adopt manifold mixup [Verma et al., 2019] as our generation method, due to its efficiency and good interpretability [Han et al., 2022].

Inter-Class Unknown Proxies

For a well-trained classifier, features of nodes that belong to the same categories are close to each other, while those from different classes are distant. Ideally, clear boundaries separate the different classes. Since nodes whose features are close to the boundaries are more likely to be less representative to their own classes, we decided to generate proxy unknowns using nodes near the boundary regions. Thus, samples that belong to different classes but are close to each other are ideal node pairs for proxy generation, i.e., node pairs where the two nodes are in different classes but have an edge between them. In details, given two connected nodes from different categories, i.e., {(xi, yi), (xj, yj)}, where yi ̸= yj and aij = 1, their embeddings in the k-th layer are hki and hkj , obtained by giving the graph to the network f 1∼k θ1 . The inter-class unknown proxy (˜xi, ˜ yi) are calculated by Eq. (5).

where α ∈ [0, 1] is randomly sampled from a Beta distribution and the value of α is around 0.5. ˜ yi = C + 1 is the category index of ˜xi, indicating it belongs to the unknown class. Two edges between (xi, ˜xi) and (xj, ˜xi) are also added into the graph. We denote the set of generated inter-class proxies samples as Xint. The purpose of Xint is to simulate the distribution of unknown class nodes that exist between known classes. The mixed hidden representation ˜xi is then passed to f k+1∼K θ1 to yield the final representation ˜hKi = f K θ1 (˜xi).

External Unknown Proxies

Besides the inter-class unknown proxies, external unknown proxies are further generated to mimic the unknown distributions at the periphery. We use the peripheral nodes from each known class and their corresponding class center to generate the external unknown proxies.

Specifically, the peripheral nodes are selected according to two rules. Rule 1 is to select the leaf nodes of known classes, i.e., xi ∈ Xtr, s.t. ∑j Ai,j = 1. Rule 2 is to collect the nodes with low classification confidence, i.e., the nodes which have the top T least confident scores are selected in each known class. In this way, both structure-based and semanticbased peripheral nodes are picked out. We record the set of peripheral nodes as Xper.

Moreover, the embedding of class centers in the k-th layer can be calculated according to the ground-truth annotations following Eq. (6):

where Xc denotes the nodes annotated with the class label c. Then, the manifold mixup is applied on peripheral nodes and their corresponding reversed class centers {(xi, yi), (x(yi), yi), xi ∈ Xper, yi ∈ {1, . . . , C}} to obtain the external unknown proxies in the k-th layer, i.e.,

where α > 0 is a hyperparameter to control the distance between the generated samples and the existing known class samples. Edges between (xi, ˜xi), xi ∈ Xper are also added into the graph. We denote the set of generated external unknown proxies as Xext.

3.2 Open-Set Classifier Learning

To handle the diverse compositions of known-unknown categories, it is necessary to extract invariant information from the known and unknown classes. Thus, the backbone GNN network fθ1 is shared by the C + 1 classes to learn class distributions and node representations.

Further, to calibrate closed-set (known classes) classifier to open-set classifier, an extra category is added to the last classification layer for unknown prediction. Suppose that the weights of the closed-set classifier is wclose ∈ RdK×C where dK is the dimension of the embeddings in the last layer of GNN, the open-set classifier is the combination of the closed-set classifier and the proxy classifier, i.e., θ2 = [wclose,wproxy] ∈ RdK×(C+1) , where wproxy ∈ RdK×1 is the weights w.r.t. the proxy classifier. Here, the bias term is omitted for simplicity. Then, the integrated classifier is trained with the original known class samples and the generated proxy samples, i.e., Dtr = Dtr ∪ (Xpxy, YC+1), Xpxy = Xint ∪Xext, with the cross entropy loss in Eq. (8):

where ˆ yi = softmax(fθ2 (fθ1 (xi))) is the output vector of the open-set classifier for the input node xi. lCrE denotes the cross entropy loss, i.e., lCrE(ˆ yi, yi) = -yi log ˆ yi .

Though the cross-entropy loss in Eq. (8) exploits mostly the information from the ground-truth class for maximizing data likelihood, the influence from complement classes (i.e., incorrect classes) has been largely ignored [Chen et al., 2018]. Thus, we further adopt complement entropy [Chen et al., 2018] to complement the softmax cross entropy by neutralizing the effects of complement classes.

The complement entropy loss LCoE is defined as the average of sample-wise entropies over complement classes, i.e.,

where ˆ yi,c denotes the predicted probability of node xi belonging to class c.

For the needs of the generative open-set classification method G 2Pxy, we further modify the above complement entropy according to the data distribution so that it better fits the task. Specifically, for generated unknown proxies, we minimize their original complement entropy, i.e., minimize the average of entropy over the C known classes, since the generated proxies could be adjacent to any of the known class. For the known class nodes, they are mostly adjacent to the generated proxies, i.e., the C + 1 class, thus we push the proxy classifier to output the second-largest probability for nodes from known classes. According to this consideration, we propose a tailored complement entropy loss for G 2Pxy as follows:

where ˆ yi/yi represents the prediction logits after removing the probability of its ground-truth label. The first term helps to reduce the misclassification of known class nodes for other known classes. It is believed that with the help of loss in Eq. (10), the open-world classifier fθ2 can classify nodes of known classes to their real categories, and use the proxy classifier to set an appropriate boundary to tell apart the known and the unknown. Finally, the total loss of G 2Pxy is a combination of cross entropy and the tailored complement entropy loss, i.e.,

where λ2 > 0 is the hyperparameter to balance these two losses.

In the test phase, the well learned open-set classifier will be applied to a test node xi ∈ Dte, and outputs C + 1 probabilities ˆ yi ∈ R(C+1)×1 . We choose the largest probability and give the related class label as prediction. Thus, xi will be detected as unknown class sample if the predicted label is C + 1.

4 Experiments

Experiments were conducted to validate the performance of G 2Pxy. These experiments include: open-set node classification comparison, ablation study, and use case. Codes are available online 1 .

Datasets. Experiments to evaluate the performance for open-set node classification were mainly carried out on four benchmark graph datasets [Wu et al., 2020; Zhu et al., 2022], namely Cora 2 , Citeseer 3 , DBLP 4 , PubMed 5 , which are widely used citation network datasets. Statistics are presented in Table 1.

1 https://github.com/ejfomxhue2o3239djnwkk/G2Pxy

2 https://graphsandnetworks.com/the-cora-dataset/

3 https://networkrepository.com/citeseer.php

4 https://dblp.uni-trier.de/xml/

5 https://pubmed.ncbi.nlm.nih.gov/download/

Metrics. Accuracy andMacro-F1 are used for performance evaluation.

Implementation Details. Generally, G 2Pxy adopts GCN [Kipf and Welling, 2017] as the backbone neural network for experimental evaluation unless otherwise specified. The GCN is configured with two hidden GCN layers in the dimensions of 512 and 128, followed by an additional multilayer perceptron layer of size 64. G 2Pxy is implemented with PyTorch and the networks are optimized using stochastic gradient descent with a learning rate of 1e-3 . The balance parameters λ1 and λ2 are chosen by a grid search in the interval from 10-2 to 102 with a step size of 101 .

The baseline methods are evaluated according to the instructions reported in the original papers with the same parameter configuration unless otherwise specified, and the best results are selected. For each experiment, the baselines and the proposed method were applied using the same training, validation, and testing datasets. The hyperparameters were tuned to get the best performance on the validation set.

All the experiments were conducted on a workstation equipped with an Intel(R) Xeon(R) Gold 6226R CPU and an Nvidia A100.

Test Settings. Compared to existing studies focusing on open-set classification [Wu et al., 2021; Tang et al., 2021; Wang et al., 2020], the evaluation framework is extended. Two kinds of open-set classification evaluations were conducted to consider short or long distances between known classes and unknown classes, i.e., near open-set classification and far open-set classification. Besides, a discussion is provided of different settings in terms of the availability of side information of unknown class samples during training and validation, i.e., the inductive learning setting and the transductive learning setting.

Specifically, in the near open-set classification experiment, for each dataset, the data of several classes were held out as the unknown classes for testing and the remaining classes were considered as the known classes. 70% of the known class nodes were sampled for training, 10% for validation and 20% for testing. In the far open-set classification experiment, nodes from other datasets were used as unknown class samples for testing, instead of the nodes from the same dataset used in training. In experiments with inductive learning setting, there is not any information about the real unknown class (such as the features xi or side information of unknown classes) used during training or evaluation, while under the transductive learning setting, the whole graph (including unlabeled real unknown class nodes) are input during model training or validation.

Baselines. The following methods are used as the baselines for the open-set classification comparison.

• GCN soft: GCN [Kipf and Welling, 2017] is adopted for graph learning, where a softmax layer is used as the final output layer. It has no capability of recognizing the unknown classes.
• GCN sig: This baseline replaces the softmax layer of GCN with multiple 1-vs-rest of sigmoids as the final out-

put layer, which still does not have the capability of rejecting the unknown classes.

• GCN soft τ: Based on GCN soft, a probability threshold chosen in {0.1, 0.2, . . . , 0.9} is used for the classification of each class .
• GCN sig τ: Similar to GCN soft τ, a threshold is combined to GCN sig.
• GCN Opmax: Openmax [Bendale and Boult, 2016] is an open-set recognition model based on "activation vectors". Extreme value distribution is used to calibrate softmax scores to Openmax scores, which are then used for open-set classification.
• GCN DOC: DOC [Shu et al., 2017] is an open-world classification method for text classification. It uses multiple 1-vs-rest of sigmoids as the final output layer and defines an automatic threshold setting mechanism. GCN is combined with DOC to allow comparison with the proposed model.
• GCN PROSER: PROSER [Zhou et al., 2021] is a novel and highly effective open-set recognition method used in the field of image processing. We paired it with GCN for graph-based comparison.
• OpenWGL: OpenWGL [Wu et al., 2020] employs an uncertainty loss in the form of graph reconstruction loss on unlabeled data and using an adaptive threshold to detect the unknown class samples.

4.1 Open-Set Node Classification Comparison

Since real-world scenarios are complex, where seen and unseen differs in diverse tasks, we evaluate our model from two aspects: near open-set classification, and far open-set classification.

Near Open-Set Classification

Table 2 and 3 list the accuracy and macro-F1 scores of the methods for the near open-set node classification task, where the last class of each dataset is set as the unknown class (i.e. u=1) and the remaining classes are used to train the model. The results in Table 2 were obtained under the inductive learning setting, where there is no side information about the real unknown class samples available during training or validation. The results in Table 3 are obtained under the transductive learning setting, i.e., the features of unknown class nodes are used to facilitate the model training or validation.

It is observed from these results that G 2Pxy outperforms the baselines on the datasets under both the inductive learning and transductive learning settings. This shows that G 2Pxy can better differentiate between a known class and an unknown class, though they are similar to each other. Specifically, G 2Pxy achieves an average of 3.70% improvement over the second-best method (GCN PROSER) in terms of accuracy, and an average of 9.60% improvement in terms of F1 score on the four datasets, under the inductive learning setting. Also, G 2Pxy achieves 5.01% and 11.25% improvements on average in terms of accuracy and F1 on the four datasets under the transductive learning setting, respectively. Furthermore, by comparing Table 2 and Table 3, it is observed that the involving of real unknown class information during training or validation benefits the model, which is reasonable.

Besides, we show the detailed classification accuracy in terms of known classes (i.e. in-distribution classification, ind for short) and unknown classes (i.e. out-of-distribution classification, ood for short) respectively, in Table 4. The experiment was conducted under the same setting of Table 2. It shows that in order to gain the ability of unknown class detection, there is a slight decrease in the performance of known class classification, i.e. from 86.9% to 82.5% on average, comparing G 2Pxy to closed-set classification method GCN soft. However, the unknown class detection accuracy is improved from 0% to 73.3% on average, which is remarkable. Compared to other open-set classification methods, such as the globally second best method GCN PROSER, the average performance of unknown-class node detection is improved from 71.7% to 73.3% while the performance of the knownclass classification still gain a certain increase from 78.0% to 82.5% on average.

Far Open-Set Classification

Following the protocol defined in [Perera et al., 2020], the models are trained and validated by all training and validation instances of the original dataset (in-distribution data, IND data). While for testing, instances from another dataset are augmented to the original test set as open-set classes (Outof-distribution data, OOD data). Specifically, three experiments were designed: Cora Citeseer(i.e., Core as IND data and Citeseer as OOD data); Citeseer DBLP (Citeseer as IND, DBLP as OOD), and DBLP Pubmed (DBLP as IND, Pubmed as OOD), to evaluate the performance of the methods for the far open-set classification task. The known-unknown ratio is 1:1 by setting the number of test examples from the OOD dataset to the same number as in the IND dataset.

The results for far open-set classification are shown in Table 5. It is found that G 2Pxy can handle far outof-distribution classes from diverse inputs and achieve a large performance improvement over state-of-the-art method GCN PROSER. Surprisingly, the simple thresholding approach of GCN soft τ achieves comparable performance with G 2Pxy. This inspires us to combine the generative methods with discriminative methods for far open-set classification in future work.

4.2 Ablation Study

We compare variants of G 2Pxy with respect to the generative strategy to demonstrate its effect. The following G 2Pxy variants are designed for comparison.

• G 2Pxy τ: In this variant, generative strategies are removed, so the proxy unknown class is not involved in training. Instead, a threshold τ is set to separate the known and the unknown, which is chosen in {0.1, 0.2, . . . , 0.9}.
• G 2Pxy int: A variant of G 2Pxy with only inter-class unknown proxies.
• G 2Pxy ext: A variant of G 2Pxy with only external unknown proxies.
• G 2Pxy¬CoE: A variant of G 2Pxy that the complement entropy loss (Eq. (10)) is removed.

Table 6 illustrates the results of these four variants and the proposed method. It can be seen that both the generated inter-class unknown proxies and the external unknown proxies matter. The proposed G 2Pxy method achieves significant improvements over G 2Pxy τ without unknown proxies, and also outperforms variants that only use a single type of unknown proxies. Meanwhile, the comparison between G 2Pxy and G 2Pxy¬CoE illustrates that the complement entropy loss is also indispensable.

4.3 Use Case

The proposed model does not have specific requirement on the GNN architecture for classification. Hence, when unknown classes are expected in testing, the proposed proxy node generation mechanism can be integrated and jointly optimized with convergence guarantee. The generated proxies can help find potential unknown class distributions and facilitate the rejection of unknown class samples.

Table 7 compares the performance of the proposed G 2Pxy with other open-set classification baselines, with different GNN architectures, including GCN, GAT and GraphSage. The results confirm the effectiveness and generalization ability of G 2Pxy for open-set node classification.

5 Conclusion

This paper introduced a novel generative method for openset node classification, named G 2Pxy. Unlike prior methods, it does not require side-information about unknown classes for model training and validation. Two kinds of proxy unknown nodes, inter-class unknown proxies and external unknown proxies are generated to foresee the distributions of unknown classes. Under constraint of both cross entropy loss and complement entropy loss, G 2Pxy achieves superior effectiveness for unknown class detection and known class classification, which is validated by experiments on benchmark graph datasets. Moreover, G 2Pxy also has good generalization since it has no specific requirement on the GNN architecture. In future work, we will try to find an effective combination of the generative model and discriminative model for near and far open-set node classification.

Acknowledgments

This research was supported by National Key R&D Program of China(2021YFB3301500), National Natural Science Foundation of China (62206179, 92270122), Guangdong Provincial Natural Science Foundation (2022A1515010129, 2023A1515012584), University stability support program of Shenzhen (20220811121315001), Shenzhen Research Foundation for Basic Research, China(JCYJ20210324093000002).