{'fraction_non_alphanumeric': 0.029107551487414188, 'fraction_numerical': 0.00585812356979405, 'mean_word_length': 5.044536652835408, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Virtual Adversarial Training on Graph Convolutional Networks in Node Classification

The effectiveness of Graph Convolutional Networks (GCNs) has been demonstrated in a wide range of graph-based machine learning tasks. However, the update of parameters in GCNs is only from labeled nodes, lacking the utilization of unlabeled data. In this paper, we apply Virtual Adversarial Training (VAT), an adversarial regularization method based on both labeled and unlabeled data, on the supervised loss of GCN to enhance its generalization performance. By imposing virtually adversarial smoothness on the posterior distribution in semi-supervised learning, VAT yields improvement on the Symmetrical Laplacian Smoothness of GCNs. In addition, due to the difference of property in features, we perturb virtual adversarial perturbations on sparse and dense features, resulting in GCN Sparse VAT (GCNSVAT) and GCN Dense VAT (GCNDVAT) algorithms, respectively. Extensive experiments verify the effectiveness of our two methods across different training sizes. Our work paves the way towards better understanding the direction of improvement on GCNs in the future.


Introduction
Recently, research of analyzing graphs with machine learning has received more and more attention, mainly focusing on node classification [7], link prediction [16] and clustering tasks [4]. Graph convolutions, as the transformation of traditional convolutions from Euclidean domain to non-Euclidean domain, have been leveraged to design Graph Neural Networks to deal with a wide range of graph-based machine learning tasks.
Graph Convolutional Networks (GCNs) [7] generalize convolutional neural networks (CNNs) to graph structured data from the perspective of spectral theory based on prior works [1,3]. It has been demonstrated that GCN and its variants [6,14] significantly outperform traditional multi-layer perceptron (MLP) models and prior graph embedding approaches [13,11,5]. This is one oral paper published in PRCV 2019 and the first author is a student. arXiv:1902.11045v2 [cs.LG] 20 Feb 2020 However, there are still many deficits on GCNs, thus in this paper we propose to apply VAT on GCNs to tackle these drawbacks of GCNs. Particularly, we firstly highlight the importance of VAT on GCNs from the following aspects, which construct the motivation of our approaches.
Lacking the Leverage of Unlabeled Data for GCNs. The optimization of GCNs is solely based on the labeled nodes. Concretely speaking, GCNs directly distribute gradient information over the entire labeled set of nodes from the supervised loss. Due to the lack of loss on unlabeled data, the parameters that are not involved in the receptive field may not be updated [2], resulting in the inefficiency of information propagation of GCNs.
Effect of Regularization in Semi-Supervised Learning. Regularization plays a crucial role in semi-supervised learning including graph-based learning tasks. On the one hand, by introducing regularization, a model can make full use of unlabeled data, thus enhancing the performance in semi-supervised learning. On the other hand, regularization can also be regarded as prior knowledge that can smooth the posterior output. For GCN model, a good regularization can not only leverage the unlabeled data to refine its optimization, but only benefit the performance of GCNs, resulting in a improved generalization performance.
Virtual Adversarial Regularization on GCNs. Virtual Adversarial Training (VAT) [10] smartly performs adversarial training without label information to impose a local smoothness on the classifier, which is especially beneficial to semi-supervised learning. In particular, VAT endeavors to smooth the model anisotropically in the direction in which the model is the most sensitive, i.e., the adversarial direction, to improve the generalization performance of a model. In addition, the existence of robustness issue in GCNs has been explored in recent works [18,17], allowing VAT on graph-based learning task.
Due to the fact that VAT has been successfully applied on semi-supervised image classification [10,15] and text classification [9], a natural question could be asked: Can we utilize the efficacy of VAT to improve the performance of GCNs in semi-supervised node classification?
Following this motivation, in our paper, we formally introduce VAT regularization on the original supervised loss of GCNs in semi-supervised node classification task. Concretely speaking, firstly, a detailed analysis of GCNs focusing on the first-order approximation of local spectral convolutions is provided to demystify how GCNs work in semi-supervised learning. Moreover, based on the motivation described above, we elaborate the process of applying VAT on GCNs in a theoretical way by additionally imposing virtual adversarial loss on the basic loss of GCNs, resulting in GCNVAT algorithm framework. Next, due to the sparse property of node features, in the realization of our method, we actually add virtual adversarial perturbations on sparse and dense features, respectively, and attain the GCNSVAT and GCNDVAT algorithms. Finally, in the experimental part, we demonstrate the effectiveness of the two approaches under different training sizes and refine a theoretical analysis on the sensitivity to the hyperparameters on VAT, facilitating us to apply our approaches in real applications involving graph-based machine learning tasks. In summary, the contributions of the paper are listed below: -To the best of our knowledge, we are the first to focus on applying better regularization on original GCN to refine its generalization performance. -We are the first to successfully transfer the efficacy of Virtual Adversarial Training (VAT) to the semi-supervised node classification on graphs and point out the difference compared with image and text classification setting. -We refine the sensitivity analysis of hyper-parameters in GCNSVAT and GCND-VAT algorithms, facilitating the deployment of our methods in real scenarios.

GCNs with Virtual Adversarial Training
In this section, we will elaborate how GCNs work in semi-supervised learning and how to utilize the virtual adversarial training to smooth the posterior distribution of GCNs.

Semi-Supervised Classification with GCNs
Firstly, we denote a graph by G = (V, E), where V is the vertex set and E is the edge set. X and A are the features and adjacent matrix of the graph, respectively and First-Order Approximation. GCNs are based on the graph spectral theory. For efficient computation, [3] approximate the spectral filter g θ with Chebyshev polynomials up to K th order: where Λ is the eigenvalues matrix of normalized graph Laplacian L = I N −D − 1 2 AD − 1 2 . T k is the Chebyshev polynomials and θ k is a vector of Chebyshev coefficients. Further, [7] simplified this model by limiting K = 1 and then the first-order approximation of spectral graph convolution is defined as: where θ is the only Chebyshev coefficients left. Through the normalization trick, the final form of graph convolutional networks with two layers in GCNs [7] is: whereÂ =D − 1 2ÃD − 1 2 ,Ã = A + I.D is the degree matrix ofÃ. Z is the obtained embedding matrix from nodes, W (0) is the input-to-hidden weight matrix and W (1) is the hidden-to-output weight matrix. Optimization. Finally, the loss function is defined as the cross entropy error over all labeled nodes: where Y L is the set of node indices that have labels. In fact, the performance of GCNs heavily depends on the efficiency of this Laplacian Smoothing Convolutions, which has been demonstrated in [8,7]. Therefore, how to design a good regularization to smooth the posterior distribution of GCNs plays a crucial role for the improvement of performance for GCNs.

Virtual Adversarial Training in GCNs
Virtual Adversarial Training (VAT) [10] is a regularization method that trains the output distribution to be isotropically smooth around each input data point by selectively smoothing the model in its most anisotropic direction, namely adversarial direction. In this section, we apply VAT on GCNs to smooth the posterior distribution of GCNs.
Assumptions. Firstly, both VAT and GCNs mainly focus on semi-supervised setting, in which two assumptions should be implicitly met [15]: -Manifold Assumption. The observed data x presented in high dimensional space is with high probability concentrated in the vicinity of some underlying manifold with much lower dimensional space. -Smoothness Assumption. If two points x 1 , x 2 ∈ M are close in manifold distance, then the conditional probability p(y|x 1 ) and p(y|x 2 ) should be similar. In other words, the true classifier, or the true condition distribution p(y|x) varies smoothly along the underlying manifold M.
In the node classification task, GCNs, which involve the graph embedding process, also implicitly conform to these assumptions. There is underlying manifold in the process of graph embedding and the conditional distribution of embedding vectors are expected to vary smoothly along the underlying manifold. In this way, we are capable of utilizing VAT to smooth the embedding of nodes in the adversarial direction to improve the generalization of GCNs. Difference of VAT on Graph and Image, Text. Traditional VAT [10] is proposed on image classification while VAT on text classification [9] is applied on word embedding vectors of each word. For VAT on graphs, we simply apply VAT on the features of nodes for easy implementation. Additionally, another obvious difference lies in that the relation between each node is not independent for the node classification task compared with image and text classification. The classification result of each node not only depends on the feature itself but also the features of its neighbors, resulting in the Propagation Effect of perturbations on feature of each node. We use D l and D ul to denote dataset with labeled nodes and unlabeled nodes respectively. x represents features excluding feature x of current node. Adversarial Training in GCNs. Here we formally define the adversarial training in GCNs, where adversarial perturbations are solely added on features of labeled nodes: where D[q, p] measures the divergence between two distributions q and p. q(y|x l , X, A) is the true distribution of output labels, usually one hot vector h(y; y l ) and p(y|x l + r, x, A) = f (X, A) denotes the predicted distribution by GCNs. x l represents the feature of current labeled node and r represents the adversarial perturbation on the feature x l . When the true distribution is denoted by one hot vector h(y; y l ), the perturbation r adv in L 2 norm can be linearly approximated: Virtual Adversarial Loss. In order to utilize the unlabeled data, we are expected to evaluate the true conditional probability q(y|x l , x, A). Therefore, we use the current estimate p(y|x, x, A;θ) in place of q(y|x, x, A).
Then virtual adversarial regularization is constructed from inner max loss: The final regularization term we propose in this study is the average of R vadv (x, D l , D ul , θ) over all input nodes: Virtual Adversarial Training. The full objective function is thus given by: where L 0 is constructed from labeled nodes in GCNs, α denotes the regularization coefficient and VAT regularization is crafted from both labeled and unlabeled nodes.

Fast Approximation of VAT in GCNs
The key of VAT in GCNs is the approximation of r vadv where r vadv = arg max r, r ≤ D p(y|x, x, A;θ), p(y|x + r, x, A;θ) .
Second-Order Approximation. Just like the situation in traditional VAT, the evaluation of GCNs with VAT cannot be performed with the linear approximation since first-order approximation equals zero [9]. Therefore, a second-order approximation is needed: where H(x, x, A;θ) := ∇ 2 r D(r, x, x, A;θ)| r=0 . Then the evaluation of r vadv can be approximated by: where u(x, x, A;θ) is the first dominant eigenvector of H(x, x, A;θ) with magnitude 1.
Power Iteration and Finite Difference Approximation. After power interation and finite difference approximation mentioned in [9], the final approximation of r vadv is: 3 Algorithm In this section, we will elaborate our Graph Convolutional Networks with Virtual Adversarial Training (GCNVAT) Algorithm. Algorithm 1 summarizes the procedures of the computation of mini-batch SGD for GCNs with VAT algorithm.   Our GCNVAT Algorithm Framework is economical in computation since the derivative of the full objective function can be computed with at most three sets of propagation in total. Specifically speaking, firstly, by initializing the random unit vector d (i) in mini-batch and computing the gradient of divergence between predicted distribution of GCNs and that with the initial perturbation, we can evaluate the fast approximated r vadv , which is involved in the first set of back propagation. Secondly, after the computation of r vadv , we are able to compute the average virtual adversarial loss in the mini-batch and optimize this loss under fixed r vadv , which incorporates the second set of back propagation. Finally, the third back propagation is related to the original supervised loss based on labeled nodes in GCNs. All in all, by this GCNs with VAT algorithm including three sets of back propagation, we are capable of imposing the local adversarial regularization on the original supervised loss of GCNs through smoothing the posterior distribution of the model in the most adversarial direction, thereby improving the generalization of original GCNs. GCNSVAT and GCNDVAT In the real scenarios, there are usually sparse features for each node especially for a large graph, which are involved in the computation of sparse tensor. In this case, in the implementation of our GCNVAT algorithm framework, we customize two similar GCNVAT methods for different properties of node features. For GCN Sparse VAT (GCNSVAT), we only apply virtual adversarial perturbations on the specific sparse elements in feature of each node, which may save much computation time especially for high-dimensional feature vectors. For GCN Dense VAT (GCND-VAT), we actually perturb each element in feature by transforming the the sparse feature matrix to a dense one.

Experiments
In the experimental part, we conduct extensive experiments to demonstrate the effectiveness of our GCNSVAT and GCNDVAT algorithms. Firstly, we test the performance of both algorithms under different label rates compared with the original GCN. Then we make another comparison under the standard semi-supervised setting with other stateof-the-art approaches. Finally, a sensitivity analysis of hyper-parameters is provided for broad deployment of our method in real applications. Experimental Setup For the graph dataset, we select the three commonly used citation networks: CiteSeer, Cora and PubMed [12]. Dateset statistics are summarized in Table 1. For all methods involved in GCNs, we use the same hyper-parameters as in [7]: learning rate of 0.01, 0.5 dropout rate, 2 convolutional layers, and 16 hidden units without validation set for fair comparison. As for the hyper-parameters, we fix regularization coefficient α = 1.0 and only change the perturbation magnitude to control the regularization effect under different training sizes, which is further discussed later in the sensitivity analysis part. All the results are the mean accuracy of 10 runs to avoid stochastic effect.

Effect under Different Training Sizes
To verify the consistent effectiveness of our two methods on the improvement of generalization performance, we compare GCNSVAT and GCNDVAT algorithms with orig-  [7] under different training sizes across the three datasets and the results can be observed in Figure 1. As illustrated in Figure 1, GCNSVAT (the red line) and GCNDVAT (the blue line) outperform original GCN (the black line) consistently under all tested label rates. Actually, it is important to note that with the increasing of label rates, the regularization effect imposed by VAT on GCNs diminishes in both approaches since the improvement from regularization based on unlabeled data is decreasing. In other words, the superior performance of GCN with Virtual Adversarial Training are especially significant when there are few training sizes. Fortunately, in real scenarios, it is common to observe graphs with a small number of labeled nodes, thereby our algorithms are especially practical in these applications. Choice of GCNSVAT and GCNDVAT. GCNDVAT performs consistently better in comparison with GCNSVAT even though GCNDVAT requires extra computation cost related to perturbations in the entire feature space. As for the reason, we argue that continuous perturbations in features facilitate the effect of VAT than discrete perturbations in sparse features. However, in the scenarios where the graph are large-scaled and their features are sparse, it is more appropriate to utilize GCNSVAT from the perspective of economical computation.
More specifically, we list the detailed performances of GCNSVAT and GCNDVAT compared with original GCN under different label rates, which are exhibited in Ta-

CiteSeer
Rates 0.5% 1% 2% 3% 4% 5%  Table 3: Classification Accuracies on CiteSeer with different label rates. Numbers in bracket are the standard deviation of accuracies. bles 2, 3 and 4, respectively. We report the mean accuracy of 10 runs. The results in tables provide a more sufficient evidence for the effectiveness of our two methods.

Effect on Standard Semi-Supervised Learning
Apart from the experiments under different training sizes, we also test the performance of GCNSVAT and GCNDVAT algorithms in standard semi-supervised setting with standard label rates listed in Table 1. Particularly, we compare our methods with other state-of-the-art methods on the node classification task under standard label rate and the results of baselines are referred from [7].
From Table 5, it turns out that our GCNDVAT algorithm exhibits the state-of-the-art performance though the improvement are not apparent compared with that in few training sizes, while our GCNSVAT algorithm also shares a similar performance. Through the extensive experiments in semi-supervised learning, we demonstrate thoroughly that VAT suffices to improve the generalization performance of GCNs by additionally providing an adversarial regularization both in semi-supervised setting with few labeled nodes and standard semi-supervised setting.

Sensitivity Analysis of Hyper-parameters
One of the notable advantage of VAT in GCNs is that there are just two scalar-valued hyper-parameters: (1) the perturbation magnitude that constraints the norm of adversarial perturbation and (2) the regularization coefficient α that controls the balance between supervised loss L 0 and virtual adversarial loss E x∼D R vadv . We refine the analysis in original VAT [10] and theoretically demonstrate the total loss is more sensitive to rather than α in the regularization control of GCNs with VAT setting.
Consider the second approximation of virtual adversarial regularization: where λ 1 (x, x, A; θ) is the dominant eigenvalue of Hessian matrix H(x, x, A; θ) of D.
Substituting this into the objective function, we obtain Thus, the strength of regularization is approximately proportional to α and 2 . In consideration of the regularization term is more sensitive to the change of , in our experiments we just tune the perturbation to control the regularization by fixing α = 1 for both methods. Further, we present the tendency between the selected optimal and label rates. As for the different label rates, it is natural to expect that GCNs with VAT under lower label rate requires larger VAT regularization, yielding the urge for larger optimal . We empirically verify this conclusion in Figure 2.
From Figure 2, it is easy to observe that with the increasing of label rates, there is a descending trend of optimal for both GCNSVAT and GCNDVAT across three datasets. It meets our expectation since large VAT regularization are more expected for GCNs under lower label rates to obtain the optimal generalization of GCNs. In addition, the optimal parameter in GCNSVAT under the same label rate tends to be higher than that in GCNDVAT, especially when the label rate is lower. The reason is obvious because GCNSVAT only applies perturbations on specific elements of sparse feature for each node, thus requiring larger perturbations on those features to get similar regularization effect compared with GCNDVAT.

Discussions and Conclusion
GCNs with Virtual Adversarial Training is established on the adversarial training on GCNs, which in our paper is simply constrained in the adversarial perturbations on the features of nodes. However, there may exists a better form of adversarial training in GCNs by additionally considering the change of sensitive edges with respects to the output performance. Therefore, incorporating a better form of Virtual Adversarial Training into graphs allows better improvement of generalization of GCNs. Besides, how to combine VAT with other form Graph Neural Networks especially in inductive setting, is also worthwhile to explore in the future.
In our paper, we impose VAT regularization on the original supervised loss of GCN to enhance its generalization in semi-supervised learning, resulting in GCNSVAT and GCNDVAT, whose perturbations are added in sparse and dense features, respectively. Particularly, we apply VAT on GCNs in a theoretical way by additionally imposing virtual adversarial loss on the basic supervised loss of GCNs. Then we empirically demonstrate the improvement caused by the VAT regularization under different training sizes across three datasets. Our endeavour validates that smoothing anisotropic direction on the posterior distribution of GCNs suffices to improve the performance of original GCN model.