End-to-End Open-Set Semi-Supervised Node Classification with Out-of-Distribution Detection

1 Introdution

Graph Neural Networks (GNNs) present the state-of-theart learning algorithm for graph-structured data via message passing between graph nodes [Wu et al., 2020]. Recently, various GNNs have been proposed with promising performance, such as graph convolutional network (GCN) [Kipf and Welling, 2017], graph attention network (GAT) [Veliˇckovi´c et al., 2018], GraphSAGE [Hamilton et al., 2017], and many others [Defferrard et al., 2016; Wu et al., 2019; Klicpera et al., 2018; Kim and Oh, 2020; Chen et al., 2020]. Generally, these GNNs have been proposed for node classification under the closed-set assumption that the training and test data are assumed to be sampled from the same distribution. However, in the real world, it is difficult to know the complete set of labels for all nodes, and it is not guaranteed that all unlabeled nodes are sampled from the known classes especially on a large graph. Therefore, the learning algorithm dedicated for in-distribution scenarios cannot cover the situation above [Geisa et al., 2021]. Recently, the Out-Of-Distribution (OOD) detection has attracted increasing attention for computer vision applications [Hendrycks and Gimpel, 2016; Liang et al., 2018; Vernekar et al., 2019; Hsu et al., 2020] and graph-structured data [Zhao et al., 2020; Stadler et al., 2021]. However, to the best of our knowledge, no prior research on GNNs has considered both OOD detection and graph node classification in an end-to-end manner.

∗Corresponding author.

In this paper, we study a novel end-to-end Open-set SemiSupervised Node Classification (OSSNC) problem, where a graph consists of both in-distribution and OOD nodes. In real-world scenarios, a graph likely contains both labeled nodes belonging to known classes that can be regarded to be in-distribution, and unlabeled nodes belonging to known or unknown classes [Stadler et al., 2021], where the unknown classes are regarded to be OOD. The GNN may suffer from severe performance degradation due to acrossdistribution mixture [Bitterwolf et al., 2022], as shown in Fig. 1. We consider two situations on graphs: mixing to indistribution and mixing to OOD. 1) First, when the central node is in-distribution, aggregating the OOD node information in the neighbors will cause an across-distribution mixture. 2) When the central node is OOD, aggregating information from in-distribution nodes will smooth the node embedding, which increases the risk of misclassification. To avoid across-distribution mixture between nodes, the propagation and aggregation of GNNs should be well-designed. For OSSNC, while the attention-based GAT [Veliˇckovi´c et al., 2018] can cope with the first scenario where the central node is in-distribution to some extent by assigning a small attention value to OOD neighbors, it cannot deal with the second scenario since the attention coefficients on the neighbors are normalized which inevitably introduces the across-distribution mixture between them.

Thus, a crucial question remains to be addressed: How to train the GNN to perform OSSNC with OOD detection in endto-end manner? This problem faces the following challenges: 1) The lack of supervision on whether a node is in-distribution or OOD. 2) There exist graph edges between in-distribution and OOD nodes, promoting the information propagation between them and causing across-distribution mixture. 3) GNNs are also prone to over-fitting [Rong et al., 2019; Xiao et al., 2021], which could become more severe when we utilize an additional parameterized model to predict if each node is in-distribution or OOD.

To address these challenges, we adopt the principle of the probabilistic generative model and propose a novel algorithm called Learning to Mix Neighbors (LMN) in a variational inference framework. To handle challenge 1), we adopt variational inference, by introducing a latent variable to indicate in-distribution or OOD node to approximate the intractable true posterior distribution. To handle challenge 2), we design a parameterized predictor for OOD node detection, and instantiate it as a weight predictor which generates real-valued weights to softly mix neighboring nodes. Then, we adopt GCNII [Chen et al., 2020] as the backbone and take the learned weights to adjust the information from neighbors, which effectively mitigates across-distribution mixture. To handle challenge 3), a bi-level optimization algorithm is adopted to iteratively update the GNN parameters and the predictor parameters. To summarize, we list our contributions:

1. We study a novel end-to-end OSSNC problem for simultaneous node classification and OOD detection. To the best of our knowledge, we are the first to investigate this problem.
2. We propose an algorithm LMN in a variational inference framework, which learns to mix neighbors to mitigate the propagation to and from OOD nodes without needing any OOD labels. Furthermore, we employ a bi-level optimization to reduce over-fitting introduced by additional parameters.
3. We conduct extensive experiments on four graphs and the results demonstrate the effectiveness of our method.

2 RelatedWork

2.1 GNNs and Robust GNNs

Recently, GNNs have been proposed and they generally can be categorized into three categories, i.e., spectral-based methods [Defferrard et al., 2016; Kipf and Welling, 2017; Wu et al., 2019], spatial-based methods [Hamilton et al., 2017; Veliˇckovi´c et al., 2018] and deeper GNNs [Klicpera et al., 2018; Chen et al., 2020]. Next, we review methods about robust GNNs for alleviating the noise issue. For example, GAT [Veliˇckovi´c et al., 2018] aggregates neighboring nodes with weights from attention mechanism to prevent the robustness. And some methods (e.g., DropEdge [Rong et al., 2019])

based on graph sparsification and sampling to enable efficient computation, and improve robustness. Besides, the other related works are anomaly detection on graphs. The works on anomaly detection can be found in surveys [Pimentel et al., 2014; Ma et al., 2021]. The core of such work is how to find anomaly samples. However, OOD detection is usually addressed by modifying the model, which requires not only to effectively detect OOD samples, but also to ensure that the performance of the model is not affected. In this paper, we study the end-to-end OSSNC problem, and aim to train a GNN model with OOD detection in end-to-end manner, which is empowered to detect OOD nodes during inference, while we still take advantage of semi-supervised training for the original classification task.

2.2 Out-of-distribution Detection

Out-of-distribution detection task plays an important role in AI safety [Bitterwolf et al., 2022]. Recently, OOD detection has been investigated in computer vision for better robustness and prediction, including softmax-based methods [Hendrycks and Gimpel, 2016; Liang et al., 2018; Hsu et al., 2020], generative-model-based methods [Denouden et al., 2018; Lee et al., 2018], and uncertainty-based methods [DeVries and Taylor, 2018; Mukhoti et al., 2021]. For softmax-based models, they aim to distinguish between in-distribution and OOD samples by the softmax prediction probability. For example, ODIN [Liang et al., 2018] improved the baseline [Hendrycks and Gimpel, 2016] with two strategies, i.e., temperature scaling and input preprocessing, to further distinguish in-distribution and OOD data. For generative-modelbased models, [Lee et al., 2018] generates near-OOD samples to surround the manifold of the entire in-distribution data. And other work [Vernekar et al., 2019] generates these samples using a manifold learning network (e.g., variational autoencoder) and then trains an n+1 classifier for OOD detection. The uncertainty-based methods are to use the confidence of the model's prediction to measure whether a sample is OOD or not. For example, the work [DeVries and Taylor, 2018] augments with a confidence estimation branch to produce a confidence estimation. For graph-structural data, the previous works [Zhao et al., 2020; Stadler et al., 2021] expect to detect OOD nodes by uncertainty, and focus on OOD detection task, rather than consider both OOD detection and graph node classification in an end-to-end manner.

3 Preliminaries and Analysis

3.1 OSSNC

The OSSNC consists of semi-supervised node classification as a primary task with OOD detection as an auxiliary task. 1) Semi-Supervised Node Classification. Given a graph G = {V,E,X, YL}, where V indicates the node set, E indicates the edge set, X is the node feature and YL is the node label. And V = VL∪VU , where VL is labeled set and VU is unlabeled set. We also can use an adjacency matrix A ∈ RN×N to represent the graph G, where Av,u = 1 indicates that there exists an edge between nodes v and u; otherwise, Av,u = 0. For the semi-supervised node classification, the model takes a small amount of labeled nodes with a large amount of unlabeled nodes during training. Overall, the goal of the node classification is to predict the labels of unlabeled nodes. 2) OOD Detection. Let an input node x ∈ X and label y ∈ Y with the joint data distribution P (x, y|O=in) = P (y|x, O=in)P (x|O = in), where O indicates in-distribution or OOD node. We assume that a classifier Pθ(y|x) is trained using in-distribution nodes from P(x, y|O = in), where θ denotes the model parameter. However, the partial nodes during inference phase may come from out-of-distribution P (x|O = out). The OOD detection task is to determine whether the input node x is from P (O = in) or P (O = out). For each input node during inference, we measure some score based on the uncertainty of prediction (e.g., Entropy), and compare the score to a threshold γ. If the score is above γ, the node is considered as an OOD node; otherwise, in-distribution node.

3.2 Analysis on Across-distributionMixture

In this subsection, we first analyze the across-distribution mixture on graphs. According to [Bitterwolf et al., 2022]:

Theorem 3.1 Across-distributionMixture. It is assumed that the sample feature conforms to the Normal distribution with the mean µ and variance σ. The mixing feature of a sample comes from in-distribution and out-of-distribution:

On this basis, we can further analyze the acrossdistribution mixture on graphs, more complex due to the propagation and aggregation between nodes.

Lemma 3.1 Across-distribution Mixture on Graphs. Take one-layer aggregation of GNN as an example, the distribution mixture comes from the central node and its neighbors:

where i,jv ∈ {1, 2}, wv,u denotes weights between node u and v, and N(u) denotes neighbors of node u.

Visualization. To visualize the across-distribution mixture, we assign different weight wv,u for mixing to in-distribution (Fig. 2 (a) ∼ (c)) and mixing to OOD (Fig. 2 (d) ∼ (f)). The weight wv,u is set as 1 for all cases in (b) and (e) while close to 0 for all cases in (c) and (f). Consistent with intuition, (b) and (e) depicts a severe distribution mixture while (c) and (f) have a slight across-distribution mixture. From Fig. 2 (b) and (e), the OOD has a significant effect on distribution variation. It is necessary to accurately detect OOD samples.

3.3 ProblemDefinition

In this paper, we consider the input pair (x, y) with partial class y not belonging to any in-distribution class Cin, which is regarded as OOD nodes. Thus, the extended label set includes in-distribution classes Cin and OOD classes Cout, i.e., C=Cin ∪Cout. In traditional setting using the closed-set assumption, all nodes in the unlabeled set VU come from the same distribution encountered in VL. In our open-set scenarios, it is not necessary for unlabeled nodes VU coming from the same distribution as labeled nodes VL. In other words, unlabeled nodes VU may contain nodes of unseen classes, called OOD nodes. In summary, our goal is to learn a GNN with OOD detection in an end-to-end manner for avoiding the performance degradation on semi-supervised node classification.

4 Methodology

Given no supervision, a generative model is proposed for modeling the joint distribution of Y and O conditioned on features and graphs, P(Y, O|X, A), and formulate the Learning to Mix Neighbors (LMN) as a variational objective.

4.1 Unified Learning Framework

To avoid the across-distribution mixture as Fig. 2, we need to effectively distinguish data in terms of distribution. We expect that the primary classification task can be guided with the auxiliary OOD detection task in an end-to-end manner. Hence, we propose an unified learning framework for the OSSNC problem. The joint probability distribution of labels Y and O in the OSSNC task can be described as

where θ represents GNN parameter and the probability distribution of OOD detection can be described as P(O|X, A). From the Bayesian perspective, the learning process includes: i) Learning the GNN parameter by maximizing the likelihood

where Ok ∈ {in, out} indicates in-distribution or OOD case. ii) Inferring the following posterior of the latent variable O as

where j ∈ {in, out} also indicates in-distribution or OOD.

However, it is challenging to address such two learning problems. On one hand, we cannot directly learn the GNN parameter θ because it involves marginalizing the latent variable O, which is generally time-consuming and intractable [Kingma and Welling, 2013]. On the other hand, we lack of supervision for test nodes for inference.

Variational Inference. To solve the challenges, the variational inference principle is considered and the lower bound of the marginal log-likelihood in Eq. (4) produces the variational objective:

where Q(Ok) is the introduced variational distribution. Maximizing the evidence lower bound (ELBO) above is equivalent to simultaneously maximizing Eq. (4) and making the variational distributions Q(Ok) close to its intractable true posteriors. We consider an end-to-end iterative algorithm to minimize negative ELBO by introducing the parameterized posterior Qφ(O|X,A) with parameter φ, into Eq. (6) and directly optimize ELBO using reparameterization trick [Kingma and Welling, 2013].

Specifically, we introduce the variational distribution to minimize Kullback-Leibler (KL) divergence:

where P(Ok) follows Bernoulli distribution. Specifically, we minimize the following negative ELBO in Eq. (6) with the reparameterization trick

where the EQφ [logPθ(Y |X,A,O)] is the semi-supervised node classification loss. According to Eq. (7), minimizing Eq. (8) makes the variational distribution Qφ(O|X,A) close to its intractable true posterior distribution.

4.2 Learning toMix Neighbors

To learn the variational distribution Qφ(O|X,A), we introduce a novel method learning to mix neighbors. Recall our analysis for across-distribution mixture on graphs (Eq. (2)), our underlying intuition is that the central node should aggregate neighbor nodes discriminately. This gives us motivation to selectively mix our neighbors via learned weights.

Learning Weights. Instead of binary dropping of edges [Rong et al., 2019; Luo et al., 2021], we adopt a predictor fφ, which generates the weights w to mix neighbors and gives a single scalar between 0 and 1 (parametrized as a sigmoid):

where W is a trainable parameter of predictor fφ, Hv and Hu are the representation of node v and u, and wv,u represents the weight to aggregate the neighbor nodes. The learned weight is generated by taking the concatenate or elementwise multiplication features as input of the predictor fφ.

Then, the latent variable wv,u ∈ [0, 1] is treated as an aggregating weight from node v to u. For our model, the graph convolution based on message passing can be described as

where fθ(l) is GNN with parameter θ at layer l, H(0) = X.

Objective Function for Learning. By substituting Eq. (9) into (8), and (8) into (7), the objective becomes

where Qφ(wv,u|X,A) is the output of predictor fφ. Consequently, minimizing Eq. (11) allows each node to learn effective weights for the OSSNC task.

Framework. In Section 4.1, we present a unified learning framework, where Qφ in Eq. (7) denotes a general formula and can be used for various considerations (such as nodes, edges). However, in Eq. (9), Qφ is a dedicated probability distribution for edges in our specific LMN method (in Section 4.2). The architecture of LMN in our implementation is shown in Fig. 3, which likely consists of a multi-layer GNN and achieves good performance on both node classification and OOD detection tasks in an end-to-end manner.

4.3 Bi-level Optimization

For the optimization, we calculate the optimal MLP-based predictor φ as well as the GNN with OOD detection classifier θ = {θg, θc}, which is formulated by using two nested loops of optimization, i.e., an outer loop for the predictor φ and an inner loop for the GNN θ. Thus, the objective is given as

where Ltrain and Lval are consistent with the objective of semi-supervised node classification task with the variational inference, i.e., Eq. (11), where Ltrain samples from training sets and Lval samples from validation sets. We employ an alternating optimization strategy to iteratively update the GNN θ and the predictor φ. However, the nested optimization results in a huge computational complexity and a heavy GPU memory occupation. To alleviate these issues, we adopt an approximate alternating optimization via the first-order approximation trick same as [Xiao et al., 2021].

Updating inner level θg and θc. This updating is different from calculating the optimal parameters θ∗ g and θ∗ c at each iteration, we only perform a hyper-parameter T steps stochastic gradient descent [Dai et al., 2021].

where αg and αc are the learning rate of GNN and classifier. Updating outer level φ. We use the parameters after updating inner level θT g and θT c to approximate the optimal parameters θ∗ g and θ∗ c . Then, the convergence of the updating via first-order approximation is proved in [Xiao et al., 2021].

where αφ is the learning rate of the predictor.

5 Experiments

In the section, we aim to answer the following questions:

(RQ1) How does our proposed LMN perform compared with the baselines in term of node classification?

(RQ2) How is our LMN performed compared with the baselines in term of OOD detection?

(RQ3) Could the bi-level optimization alleviate the overfitting issue?

(RQ4) How does our method perform with different mixing neighbor strategies?

5.1 Experiment Settings

Datasets. For semi-supervised node classification, we employ four widely used benchmark datasets: 1) Cora; 2) Citeseer; 3) Pubmed; and 4) ogbn-arXiv [Hu et al., 2020]. The statistics of datasets are presented in the Table 1. For the split of OOD classes, we strictly follow the standard OOD detection benchmark on graphs [Stadler et al., 2021].

Baselines. In this paper, we implement 10 representative GNN models covering Spectral-based, Spatial-based, Deeper and Robust GNNs, which are GCN [Kipf and Welling, 2017], ChebNet [Defferrard et al., 2016], GraphSAGE [Hamilton et al., 2017], GAT [Veliˇckovi´c et al., 2018], SGC [Wu et al., 2019], JKNet [Xu et al., 2018], APPNP [Klicpera et al., 2018], SuperGAT [Kim and Oh, 2020], GCNII [Chen et al., 2020], and DropEdge [Rong et al., 2019]. We implement all baselines and our proposed models in PyTorch and PyTorch-Geometric.

Evaluation Metrics. For semi-supervised node classification task, we evaluate the performance of the node classification in terms of the in-distribution by using the accuracy metric. For OOD detection task, we implement a unified OOD detection method based on the uncertainty of prediction (e.g., Entropy) [Mukhoti et al., 2021]. And we use Area Under the Receiver Operating Characteristic curve (AUROC) as the evaluation metric, which is a threshold-independent performance evaluation. The average results and standard deviations of five runs are reported on all datasets.

5.2 Node Classification Task (RQ1)

Following semi-supervised node classification setting [Rong et al., 2019], we apply the standard fixed training/validation/testing split, where 20 labeled nodes per class are for training, 500 nodes are for validation, and the remaining nodes are for testing. We report the average accuracy of baselines and LMN in Table 2. From this table, we have the following observations: 1) Attention-based models like GAT and SuperGAT generally outperform other shallow GNNs including GCN, ChebNet and SGC. It implies the attention mechanism is helpful to focus on the self- or neighborinformation and beneficial to node classification. 2) The deeper GNNs achieve higher performance than shallow GNN, which indicates that deeper GNNs can improve the performance of model. 3) The DropEdge outperforms its backbone GCNII and other baselines, which indicates that DropEdge can improve the robustness of model even if it adopts a random way to drop edges. 4) Our proposed LMN outperforms all baselines because LMN can effectively identify data to be in-distribution or OOD and thus alleviate across-distribution mixture.

5.3 OODDetection Task (RQ2)

To comprehensively evaluate the OOD detection performance, we adopt AUROC as the evaluation metric. The AUROC is a threshold-independent performance evaluation metric. The results of AUROC are reported in Table 3. From this table, we have following observations: 1) Attentionbased models like GAT and SuperGAT get better results than weighted average models since the attention weighted aggregation is helpful to OOD detection. 2) The DropEdge outperforms its backbone GCNII except Pubmed; however, it adopts a random dropping leading to a lack of interpretability. 3) Our proposed LMN achieves the best performance, which indicates once again that LMN alleviates the across-distribution mixture between in-distribution and OOD samples.

5.4 The Effect of Bi-level Optimization (RQ3)

To demonstrate the effectiveness of bi-level optimization for over-fitting issue, we analyze the model loss of vanilla training (we simultaneously optimize φ and θ on training data without validation) as well as the loss of the bi-level optimization with validation. Fig. 4 shows the learning curves of training loss and validation loss on the Cora dataset. From such figure, we can find that the over-fitting issue leads to a low training loss in (a) but a high validation loss in (b). And the bi-level optimization has a lower validation loss than vanilla training, which indicates that the bi-level optimization with validation can effectively alleviate the over-fitting issue.

5.5 Mixing Strategies (RQ4)

We further consider five OOD models for comparison, RandomMask (RM), TruthMask (TM), RandomDrop (RD), TruthDrop (TD), and ATtention (AT). Specifically, 1) RM masks neighbor nodes randomly with different masking proportions. 2) TM masks neighbor nodes by using OOD ground truth. 3) RD removes edges randomly. 4) RD drops edges by OOD ground truth. 5) AT adopts attention mechanism. For RM and RD, we report the best result on dropping proportions {0.1, 0.2, 0.3, 0.4, 0.5}. To make a fair comparison, a stateof-the-art graph neural network architecture GCNII [Chen et al., 2020] is adopted as backbone.

Results. We report the results on Cora and Citeseer datasets for page limitation but the observation is consistent for all datasets. From Fig. 5, we observe that: 1) TM and TD outperform AT, indicating that AT cannot avoid across-distribution mixture well. 2) Both TM and TD surpass RM and RD. It shows that the randomly discarding on nodes and edges cannot obtain satisfactory results. 3) LMN outperforms RM, RD, TD, and AT consistently, indicating that LMN alleviates across-distribution mixture effectively.

5.6 Ablation Study

Table 4 shows the results for brief ablation study on two datsets. Our LMN uses GCNII with OOD detection while GCNII has no OOD detection module. LMN outperforming GCNII demonstrates the effectiveness of our detection scheme.

6 Conclusions

Current efforts on promoting GNNs mostly focus on classification accuracy on closed-set assumption. In this paper, we study a novel problem of end-to-end open-set semisupervised node classification. The novel method LMN in a variational inference framework has been proposed for simultaneous node classification and OOD detection in an end-toend manner. Extensive experiments on four various datasets demonstrate the effectiveness of our proposed method.

Acknowledgements

Authors would like to thank funding support from NSFC General Program (No.62176215). Dr. Yuan Fang's work in this research is supported by the Lee Kong Chian Fellowship awarded by Singapore Management University.