A safe semi-supervised graph convolution network

1.   Introduction

In recent years, graph-based methods have attracted more and more attention from researchers. The reason is twofold. First, in the real-world problem, there exists a large amount of non-Euclidean data, such as recommender systems ^[1], proteins-proteins network ^[2,3,4], etc. Unlike the Euclidean data, non-Euclidean data have an irregular data structure, these data can be expressed by graph for the powerful ability of graph. Second, the geometric structure of data can be embedded by graph analysis methods, thereby helping the model to improve its recognition ability. In general, graph-based methods extend the application scenarios of existing machine learning methods to a certain extent.

Nowadays, graph neural networks (GNNs) have been widely used in machine learning for their convincing performance and high interpretability ^[5]. Due to the great success of CNNs in machine learning, a large number of researchers have tried to extend convolution operations from the image domain to the graph domain ^[6,7,8,9]. As for graph-based semi-supervised learning, Kipf & Welling ^[9] proposed graph convolution network (GCN). GCN used convolution on the graph to extract features and obtained both feature information and graph structure information of the nodes. However, it required the full graph Laplacian operator when training the model, which was very computationally intensive when computing large graphs. Moreover, the embedding of nodes in each layer of GCN was recursively computed by the embedding of all neighboring nodes in the previous layer. This made the receptive field of the nodes grow exponentially with the number of layers, which could be very time-consuming when computing the gradient. GraphSAGE ^[10] replaced the graph Laplacian function of GCN with a learnable aggregation function and used neighbor sampling to reduce the growth of the receptive domain, making it applicable to inductive learning. FastGCN ^[11] interpreted the graph convolution as an integral transform of the embedding function under probability measures and used important sampling to reduce the computational time while providing a comparable level of computational accuracy. Simple Graph Convolution (SGC) ^[12] reduced the additional complexity by successively removing the nonlinearity in the GCN layers and collapsing the resulting function into a linear transformation. The same computational speedup could be achieved without negatively affecting the classification accuracy. Different from GCN, Topology Adaptive Graph Convolutional Network (TAGCN) ^[13] used K graph convolution kernels at each layer to extract local features of different sizes, following the example of CNNs, to avoid the previous drawback of approximating the convolution kernels without extracting complete and sufficient graph information, and to improve the representational power of the model. Graph Attention Network (GAT) ^[14] made use of hidden self-attentive layers by stacking the nodes in each layer so that it can focus on the features of the neighborhood and assign different weights to different nodes in the neighborhood, making it possible to achieve advanced results without the need to know the graph structure in advance. It addressed the problem that GCN needs to have prior knowledge of unknown data and the usage scenarios are mostly in dealing with static graphs. SuperGAT ^[15] learned more appropriate attention weights when distinguishing misconnected neighbors by a self-supervised task. Moreover, GCN is widely used in other field tasks. For instance, Zhu et al. ^[16] introduced a graph convolutional network with conditional feature aggregation and proposed a common-centric localization (CCL) network for few-shot common-localization task. Many different improved versions have been proposed by researchers since then ^[17,18,19], and all have achieved promising results. Whereas, GCN and its variant models directly use the feature information of all unlabeled data during training without evaluating the risk. This makes the model perform poorly on datasets with noise unlabeled data.

On the other hand, GCN and its variant models are mostly built on a semi-supervised learning paradigm ^[20]. Semi-supervised learning used labeled data to train the model while using unlabeled data to better maintain the intrinsic structural information of the data, allowing the model to achieve promising results. And it is well adapted to problems that contain a small number of labeled data and a large number of unlabeled data. Nevertheless, it is known that there are risky unlabeled data in unlabeled dataset. Risky unlabeled data refers to noisy data that degrade model performance with incorrect information, such as outlier. These risky data can cause errors to propagate during the training of the model and degrade the performance of the model. In some cases, semi-supervised learning performs worse than the corresponding supervised learning, as has been verified in many works ^[21,22,23]. If the risk of unlabeled data cannot be reduced, this will make the model very limited for using in practical scenarios. Therefore, it is necessary to design a safe GCN.

Some existing semi-supervised learning works have studied the idea of selecting high-confidence pseudo-label. Wu et al. ^[24] proposed the Exploit the Unknown Gradually (EUG) method, which iteratively obtains pseudo-label and updates the model. Unlike most works that use models to predict pseudo-label, EUG utilized the label of the nearest neighbor in the feature space to assign pseudo-label. And the Euclidean distance is used to measure the confidence of the pseudo-label. Wu et al. ^[25] used the same method in EUG to obtain pseudo-label, and proposed a joint learning method. These data not considered high-confidence are labeled by index and participate in the training of the model by Exclusive Loss. Similar Pseudo Label Exploitation (SimPLE) ^[26] utilized the label guessing technique, both labeled and unlabeled data are augmented with weak and strong augmentation. The pseudo-label is obtained by the mean of the class prediction distribution after augmented, and then the weak augmented unlabeled data are sharpened for the model prediction. The loss terms are optimized according to the augmentation data and pseudo-label. The above method only considers a single semi-supervised classifier, ignoring the pseudo-label information obtained by the supervised classifier, which is also important for pseudo-label. Multiple knowledge Representation (MKR) ^[32] proposed a framework that learned from different levels of abstraction, different sources, and different perspectives to improve model performance through multi-feature aggregation, but it did not evaluate the risk of unlabeled data.

Some recent works have used the self-training method ^{[27,28,29,30]} to select the unlabeled data and expanded the labeled dataset by the high-confidence unlabeled data, which somewhat alleviates the risk problem of unlabeled data. The main idea of Self-training is using the labeled data to train a classifier to label the unlabeled data ^[20,31], then select some high-confidence data to expand the labeled dataset. This process is carried out iteratively until convergence. How to design the Self-training method to select reasonable unlabeled data is an important challenge. Most works are only based on the highest soft-max output ^[28,29], which is always insufficient to measure the confidence of the data.

In this paper, we propose a safe GCN framework (Safe-GCN). The proposed model is implemented in three stages. First, S-GCN and GCN classifiers are trained to obtain the pseudo-label of unlabeled data. Second, the outputs of S-GCN and GCN are compared. The unlabeled data with high- confidence are selected by a confidence filtering condition. Then labeled dataset is expanded in a balanced way by high-confidence unlabeled data. Finally, the expanded labeled dataset is used to train the S-GCN. Hence, our proposed Safe-GCN makes better use of supervised and semi-supervised information, and has the opportunity to achieve model security by reducing the negative impact of risky unlabeled data. GCN and its variant models directly use the feature information of all unlabeled data during training without evaluating the risk. This makes models perform poorly on datasets with noisy unlabeled data. Compared with existing graph convolutional networks, our model enables GCN to be safely exploited on datasets with large amounts of unlabeled data. And Safe-GCN improves the noise immunity of GCN, which allows GCN to be applied in more real-world application scenarios.

We conducted experiments on three publicly available citation datasets. The results demonstrate that the classification performance of the proposed model outperforms most existing graph-based models. The main contributions and advantages of this paper compared to related works are summarized as follows:

● We proposed a safe semi-supervised graph convolution model that can effectively reduce the adverse effects of risky unlabeled samples. The model can safely utilize a large amount of unlabeled data.

● The proposed model utilizes only the information of the training data during training and does not need to know the graph structure and feature information of the test data. Therefore, the proposed model can be directly applicable to inductive learning.

The rest of the paper is organized as follows. Section 2 describes the background in this paper. Section 3 describes the proposed algorithm. The dataset, experimental configuration and results are described in Section 4. Section 5 gives the conclusion of this paper and discusses future directions.

2.   Background

Since GCN and its supervised version are used as classifiers in Safe-GCN, so we discuss the details of GCN in this section. Kipf & Welling ^[9] proposed a graph convolution network for semi-supervised learning. The main idea is to pass information from each node to its neighbors through information transfer between nodes, and iteratively aggregate the features of the nodes' neighbors through Laplace matrix and convolution on the graph, enabling it to deeply estimate the labels of unlabeled data. The model can be described as following:

where F$\in\mathbb{R}^{n\times d}$ denotes a label matrix that represents the output of the unlabeled data. X is the feature matrix of the dataset and A is the adjacency matrix associated with data.

The propagation law of the layers in GCN is given by:

where $\widetilde{A} = A+I$ denotes the A matrix with added self-connections, I denotes the identity matrix, and $\widetilde{D}$ denotes the degree matrix of the $\widetilde{A}$ matrix. $W^{(i)}$ denotes the weight matrix corresponding to the ith layer of the network. $\sigma(\cdot)$ denotes the activation function, it is given by the ReLU. $H^{(0)}$ is X.

Since the GCN model can achieve advanced results with 2–3 layers, a two-layer GCN model has the following form:

where $\breve{A} = D^{-\frac{1}{2}}\widetilde{A}D^{-\frac{1}{2}}$ denotes the regularized Laplace matrix, $W^{(0)}$ is the input-hidden weight matrix, and $W^{(1)}$ is the hidden-output weight matrix.

The softmax activation function converts the output matrix into a probability distribution for each data corresponding to each category by row, i.e., the probability of each data corresponding to all categories sums to 1. Deep neural networks is learned by making the predicted label as close as possible to the ground-truth label. This is achieved by minimizing the cross-entropy loss function that is typically used for classification problems. The cross-entropy function is used as the loss function in the GCN.

3.   Our algorithm

As stated in Section 1, the GCN and its variants models use unlabeled data to enhance the performance of the model and achieve promising results. However, mistakes in risky unlabeled data can spread during the training of the model and may degrade the performance of the model, which makes the use of unlabeled data very risky. Considering the safe use of unlabeled data, we propose an enhanced safe GCN model, which is based on the self-training framework. The method to select high-confidence data in the proposed model is illustrated in Figure 1. The model is divided into three stages as shown below:

$(1)$ Pseudo label acquisition: the first stage computes the information encoded in the embedding by S-GCN and GCN to make better use of labeled and unlabeled data. The classification results and model outputs of S-GCN and GCN for unlabeled data are obtained in this stage.

$(2)$ Labeled dataset expansion: the second stage evaluates the unlabeled data and performed data expansion. Most self-training methods use high-confidence unlabeled data to expand the labeled dataset, and they rely on the maximum softmax scores to assess the risk level of unlabeled data ^[29,30], which is always not accurate enough. Therefore, we propose a new confidence-based data filtering condition. Meanwhile, the same number of unlabeled data with high confidence for each class is added to the labeled dataset to ensure a balanced distribution of labels. The first and second stages of learning are iteratively performed until the stopping condition is satisfied (i.e., there are no data meeting filtering condition in the unlabeled dataset).

$(3)$S-GCN classification: Supervised GCN learning is performed using the final expanded dataset to predict the test data and obtain the final results.

3.1.   Pseudo-label acquisition

This stage is the fundamental module that obtained pseudo label of unlabeled data by S-GCN and GCN.

The feature matrix of the dataset is defined as $X = \left[x_1, \ldots, x_l, \ldots, x_n\right], X\in\mathbb{R}^{n\times d}$, $n$ is the number of data, $d$ is the number of feature dimensions of the data. $l$ denotes the total number of initially labeled data. The number of labeled data increases with the iterations, and the details are given in the following sections. The feature matrix of the initial labeled data is defined as: $X^{l\left(0\right)} = \left[x_1, \ldots, x_l\right]$ with the corresponding initial label set $Y^{l\left(0\right)} = \left[y_1, ...\, \ y_l\right]^T$, each labeled data $x_p$ will have a label $y_p\ \in\ \left\{1, \ \ldots\, \ c\right\}$ with the number of classes $c$. And the labeled dataset after the $kth$ iteration is $X^{l\left(k\right)}$,

The network structure of S-GCN is the same as the GCN, with the difference: 1) the adjacency matrix and degree matrix are constructed using labeled data. 2) only labeled data are involved in model training. The model output of the $kth$ iteration is expressed as follow:

$A^{\prime\left(k\right)}\in\mathbb{R}^{l\times l}$ denotes the adjacency matrix of the S-GCN after the $kth$ iteration. The model output of the $kth$ iteration of the GCN is given by:

where $A^{\prime\prime}\in\mathbb{R}^{(l+u)\times(l+u)}$ denotes the adjacency matrix of the GCN.

Formally the training dataset can be represented by a labeling function with the goal of learning the labeling functions $L(F^{\prime\left(k\right)}), L(F^{\prime\prime\left(k\right)})$ in S-GCN and GCN.

3.2.   Labeled dataset expansion

Once the data have been processed by the softmax layer, we are interested in the largest value in $\mathbf{F}_\mathbf{i}^{\prime\left(k\right)}$, $\mathbf{F}_\mathbf{i}^{\prime\prime\left(k\right)}$ that is associated with the most likely class. Therefore, we consider a function $m(\cdot)$ that returns the largest element in the vector. The function can be defined as: $m(\cdot) = max(\cdot)$, $m(\mathbf{F}_\mathbf{i}^{\prime\left(k\right)})$ returns the largest element in $\mathbf{F}_\mathbf{i}^{\prime\left(k\right)}$. $\mathbf{F}_\mathbf{i}^{\prime\left(k\right)}$, $\mathbf{F}_\mathbf{i}^{\prime\prime\left(k\right)}$ denotes the output vector of the ith data in S-GCN and GCN, respectively, both being c-dimensional vector.

However, the maximum value of the output vector of the softmax layer is not sufficient to determine the security of data. To this end, we propose a confidence-based filtering condition for unlabeled data: (1) the prediction results of S-GCN and GCN for the unlabeled data are the same. (2) the maximum value of the output vector of GCN is greater than or equal to the S-GCN and greater than the confidence threshold $\alpha$. We treat data that satisfy the filtering condition as high confidence ones.

Labels of data that meet the conditions form a candidate label set. The histogram is used to count the alternative label set. In order to balance the distribution of label set, the number of data per class is counted in a histogram. Formally, a function $hgram(\cdot)$ is defined to statistically the classes in the label set and the number of labels in each class. $s^{(k)}$ denotes the number of labels of the least labeled classes in the candidate label set for the $kth$ iteration. If there is a class that is not present in the candidate label set, the class label is not updated.

3.3.   Supervised GCN classification

GCN using a semi-supervised learning framework for training has achieved promising results. The proposed model is based on the self-training learning framework, and we improve the performance of the model by utilizing the pseudo-label information of unlabeled data. Moreover, traditional GCN is mainly used for semi-supervised learning but can also be used for supervised learning. Supervised GCN is implemented by training the model using only the features and graph structure of the labeled data. We select high-confidence unlabeled data, and the remaining unlabeled data are considered as risky data. Utilizing risky unlabeled data can degrade the performance of the model. Therefore, we use supervised GCN for classification.

The first and second stages are iteratively applied until there are no more unlabeled data satisfying the filtering condition. The labeled dataset after the completion of the iteration is the final labeled dataset. The third stage uses S-GCN model to learn the expanded dataset and obtain the final classification result, i.e., the classification result of Safe-GCN.

The three stages of the proposed method are detailed and formally defined in the following subsections. An overview of the proposed method is given in Algorithm 1. Lines 1 and 2 of the algorithm table train a GCN and an S-GCN, respectively, and lines 3 to 9 select high-confidence data by filtering conditions. Lines 10 to 15 add the high-confidence data to the labeled dataset in a balanced way.

4.   Experimental evaluation

4.1.   Citation dataset

The predictive power of the model is evaluated on three citation network datasets: Cora, Citeseer and Pubmed ^[33]. These datasets have been utilized in many graph-based semi-supervised classification tasks. The division of datasets are shown in Table 1, and a brief introduction of datasets are as follows:

Cora  The Cora dataset consists of 2708 scientific publications, each publication is described by a 1433-dimensional word vector with values of 0 and 1, respectively, representing whether corresponding word appears in the paper. Publications of Cora are divided into 7 classes. The division of Cora is following the GCN. The difference is that we use the union of the train set and the validation set as our train set.

Citeseer  The Citeseer dataset employs a similar representation to Cora, but the publications are divided into 6 classes and the data are described by a 3703-dimensional word vector. The division of Citeseer is also following the GCN.

Pubmed  The dataset includes 19,717 scientific publications on diabetes from the Pubmed database. Publications are divided into three classes and described by a TF/IDF-weighted word vector in a dictionary of 500 unique words.

The adjacency matrix is very important for the performance of graph-based algorithms. Many graph-based algorithms construct the adjacency matrix from the similarity matrix of nodes. The citation network dataset used in this paper constructs the adjacency matrix by whether two nodes (i.e., papers) are cited to each other.

In many practical applications of machine learning, the information of the test data during the training of the model is unknown. Therefore, the three citation datasets are divided differently from those in GCN, the model is trained without using feature information and node information from the test dataset. Since Safe-GCN only uses the training data to train the model, and the test dataset as a new graph structure to compute classification accuracy, our model is directly applicable to inductive learning. For a fair comparison, the methods used for comparison also use the same form of data division (i.e., feature and node information from the test dataset is not used). The initial labeled data is trained using 20 labels per class. The specific division is shown in Table 1.

4.2.   Experimental setup

We compare the proposed model Safe-GCN with some traditional machine learning methods and some state-of-the-art graph-based methods. These methods belong to two categories: (1) traditional machine learning algorithms. (2) graph-based convolution networks.

The traditional machine learning algorithms include multilayer perceptron (MLP) and support vector machine (SVM). The graph-based models include representative semi-supervised graph convolution networks (GCN) ^[9], Graph Attention Network (GAT) ^[14], Topology Adaptive Convolutional Network (TAGCN) ^[13], Predict then Propagate: Graph Neural Networks meet Personalized PageRank ^[34] and Attention-based Graph Neural Network for Semi-supervised Learning ^[35].

The implementation of the proposed Safe-GCN and the above methods were made upon the Pytorch framework. The graph-based methods were implemented via Pytorch Geometric (PYG), an extension library for geometric learning based on the Pytorch framework, and the traditional machine learning methods were implemented via the Scikit-learn package.

Adam was used to training all the above graph-based models as optimizers. During the training phase, each model's hyperparameters and network configuration were followed the default benchmark provided in PYG. The learning rate of the models was set to 0.01 and the dropout parameter was defined as 0.5, except for GAT which was 0.6. For a fair comparison, the number of epochs of all models was limited to 200. MLP and SVM followed the default setups in Scikit-learn, the maximum number of iterations were defined as 1000 for MLP to ensure full convergence.

4.3.   Method comparison

Table 2 illustrates the classification rate using different traditional machine learning and graph-based methods for Cora, Citeseer, and Pubmed datasets (following the split in ^[9]). Table 3 illustrates the average classification rate (together with its standard deviation over the ten random splits). For each table, there are three columns that correspond to three citation datasets.

4.4.   Ablation experiment

In safe-gcn, two classifiers are used to obtain high confidence pseudo-label. To verify that combining two classifiers improves the quality of pseudo-label, we conducted ablation experiments using only a single classifier under the same experimental setup. The results are shown in Table 4.

4.5.   The effect of the iterative process on model performance

The self-training learning framework uses an iterative approach to expand the labeled samples. To investigate how Safe-GCN improves the performance over the iterations, we recorded the unlabeled data expanded in the first 10 iterations of the model and the performance of Safe-GCN for each iteration in Table 5.

4.6.   The effect of the number of labeled data

Since the number of labeled data has an effect on the accuracy of the model, it is interesting to study the performance of the model with different numbers of labeled data. The number is increased or decreased from the original labeled dataset. In this section, we adjust the number of initially labeled data to study the performance of the proposed model from different dataset. The basic labeled dataset of Cora, Citeseer, and Pubmed are respectively 140,120, 60, accounting for 0.2, 0.16, and 0.02% of the total training data, respectively. In Figure 2, the horizontal coordinate indicates the proportion of labeled data to the overall training data, and the vertical coordinate indicates the classification accuracy of the model.

4.7.   The effect of confidence thresholds

Hyperparameters are very important in machine learning, which can directly affect the performance of the model. In this paper, $\alpha$ as a hyperparameter denotes the confidence threshold used to determine the data security. Therefore, in order to study the effect of $\alpha$ on the model, we give a set of values to adjust it. The $\alpha$ of Cora, Citeseer were chosen from ${[0.2, 0.3, ...\, 0.9]}$ and Pubmed were chosen from ${[0.4, \ 0.5, ...\, 0.9]}$, respectively. The classification accuracy of the model for each of the three citation datasets at different $\alpha$ is illustrated in Figure 3.

4.8.   The effect of $s^{(k)}$

In this section, we study the effect of $s^{(k)}$ on the model performance. $s^{(k)}$ as a hyperparameter that determines the number of expanded high-confidence data per class in the $kth$ iteration. Figure 4 illustrates the classification accuracy of the model at different ranges of $s^{(k)}$.

4.9.   Experimental analysis

From the results of all previous tables and pictures, we can conclude the following:

$(1)$ From Tables 2 and 3, we can see that our model outperforms the other methods on all three citation datasets. In particular, it can improve more than 3% on all three datasets compared to GCN. We also have different degrees of advancement compared to other methods. This indicates that high confidence data can enhance the predictive power of the model.

$(2)$ The superiority of the proposed model in the case of small labeled data size is obvious as presented in Figure 2, which indicates that the proposed model is applicable to the problem of few labels and can safely utilize a large number of unlabeled data to satisfy many real-world application scenarios. The advantages of the proposed model are not evident in the case of a large amount of labeled data, which is attributed to the fact that a large amount of labeled data can already describe the distribution of the data adequately.

$(3)$ Figure 3 illustrates that in the Cora and Citeseer, the proposed model is insensitive in the ranges ${[0.2, 0.3, ...\, 0.9]}$, ${[0.4, \ 0.5, ...\, 0.9]}$ for parameter $\alpha$, respectively. In Pubmed, the proposed model is insensitive to the parameter $\alpha$ and even to the proportion of labeled data in the training data.

$(4)$ The results of the ablation experiments demonstrate that combining two networks can improve the quality of pseudo-label and achieve better classification performance than using only a single network.

$(5)$ Table 5 illustrates how the iterative process improves the predictions. Cora and Citeseer show that the large number of accurate pseudo-labels added at each iteration enhances the performance classifier at each iteration, allowing it to classify unlabeled data more accurately. In contrast, Pubmed adds a large number of accurate pseudo-label at the first iteration, therefore, the performance improvement over the iterations is slow, but the overall classification performance is improving.

$(6)$ Figure 4 shows the classification accuracy of the model for Safe-GCN at different proportions of $s^{(k)}$ settings. The results demonstrate that the model is insensitive to the parameter $s^{(k)}$.

5.   Conclusions

We propose a safe GCN framework. The model is based on the self-training framework, which utilizes embedding information of unlabeled data by learning S-GCN classifiers and GCN classifiers. Then obtains high-confidence unlabeled data using a confidence threshold-based data filtering condition, which is balanced to expand the labeled data and reduce the negative impact of risky unlabeled data. At the same time, the model combines supervised and semi-supervised information of data, which improves the security of unlabeled data than using only supervised or semi-supervised information. Therefore, our model can effectively reduce the risk of unlabeled data and safely use a large number of unlabeled data. In addition, our model is applicable to inductive learning, which extends the applicability of the model to some extent.

In the future work, we will focus on the following directions: (1) more detailed risk classification of unlabeled data, and different risk levels of unlabeled data may have different effects on the model. (2) The quality of the model also affects the performance of the model, and methods to assess the quality of the model will be explored. (3) Reducing the time complexity of the model is of importance in realistic application scenarios.

Acknowledgments

The work was supported by Open Funding Project of the State Key Laboratory of Biocatalysis and Enzyme Engineering under grant No. SKLBEE2020020 and SKLBEE2021020, the High-level Talents Fund of Hubei University of Technology under grant No. GCRC2020016, Key Laboratory of Brain Machine Collaborative Intelligence of Zhejiang Province under grant No. 2020E10010-02, and Natural Science Foundation of Hubei Province under grant No. 2021CFB282.

Conflict of interest

The authors declare there is no conflict of interest.