Graph Structure Learning for Robust Graph Neural Networks

Graph Neural Networks (GNNs) are powerful tools in representation learning for graphs. However, recent studies show that GNNs are vulnerable to carefully-crafted perturbations, called adversarial attacks. Adversarial attacks can easily fool GNNs in making predictions for downstream tasks. The vulnerability to adversarial attacks has raised increasing concerns for applying GNNs in safety-critical applications. Therefore, developing robust algorithms to defend adversarial attacks is of great significance. A natural idea to defend adversarial attacks is to clean the perturbed graph. It is evident that real-world graphs share some intrinsic properties. For example, many real-world graphs are low-rank and sparse, and the features of two adjacent nodes tend to be similar. In fact, we find that adversarial attacks are likely to violate these graph properties. Therefore, in this paper, we explore these properties to defend adversarial attacks on graphs. In particular, we propose a general framework Pro-GNN, which can jointly learn a structural graph and a robust graph neural network model from the perturbed graph guided by these properties. Extensive experiments on real-world graphs demonstrate that the proposed framework achieves significantly better performance compared with the state-of-the-art defense methods, even when the graph is heavily perturbed. We release the implementation of Pro-GNN to our DeepRobust repository for adversarial attacks and defenses (footnote: https://github.com/DSE-MSU/DeepRobust). The specific experimental settings to reproduce our results can be found in https://github.com/ChandlerBang/Pro-GNN.

(the Facebook friend network). With their prevalence, it is particularly important to learn effective representations of graphs and then apply them to solve downstream tasks. Recent years have witnessed great success from Graph Neural Networks (GNNs) [15,17,21,29] in representation learning of graphs. GNNs follow a message-passing scheme [14], where the node embedding is obtained by aggregating and transforming the embeddings of its neighbors. Due to the good performance, GNNs have been applied to various analytical tasks including node classification [17], link prediction [18], and recommender systems [34].
Although promising results have been achieved, recent studies have shown that GNNs are vulnerable to adversarial attacks [10,16,31,38,39]. In other words, the performance of GNNs can greatly degrade under an unnoticeable perturbation in graphs. The lack of robustness of these models can lead to severe consequences for critical applications pertaining to the safety and privacy. For example, in credit card fraud detection, fraudsters can create several transactions with only a few high-credit users to disguise themselves, thus escaping from the detection based on GNNs. Hence, developing robust GNN models to resist adversarial attacks is of significant importance. Modifying graph data can perturb either node features or graph structures. However, given the complexity of structural information, the majority of existing adversarial attacks on graph data have focused on modifying graph structure especially adding/deleting/rewiring edges [33]. Thus, in this work, we aim to defend against the most common setting of adversarial attacks on graph data, i.e., poisoning adversarial attacks on graph structure. Under this setting, the graph structure has already been perturbed by modifying edges before training GNNs while node features are not changed.
One perspective to design an effective defense algorithm is to clean the perturbed graph such as removing the adversarial edges and restoring the deleted edges [27,37]. The key challenge from this perspective is what criteria we should follow to clean the perturbed graph. It is well known that real-world graphs often share certain properties. First, many real-world clean graphs are low-rank and sparse [36]. For instance, in a social network, most individuals are connected with only a small number of neighbors and there are only a few factors influencing the connections among users [13,36]. Second, connected nodes in a clean graph are likely to share similar features or attributes (or feature smoothness) [24]. For example, in a citation network, two connected publications often share similar topics [17]. Figure 1 demonstrates these properties of clean and poisoned graphs. Specifically, we apply the state-of-the-art graph poisoning attack, metattack [39], to perturb the graph data and visualize the graph properties before and after mettack. As shown in Figure 1a, metattack enlarges the singular values of the adjacency matrix and Figure 1b illustrates that metattack quickly increases the rank of adjacency matrix. Moreover, when we remove the adversarial and normal edges from the perturbed graph respectively, we observe that removing adversarial edges reduces the rank faster than removing normal edges as demonstrated in Figure 1c. In addition, we depict the density distribution of feature difference of connected nodes of the attacked graph in Figure 1d. It is observed that metattack tends to connect nodes with large feature difference. Observations from Figure 1 indicate that adversarial attacks could violate these properties. Thus, these properties have the potential to serve as the guidance to clean the perturbed graph. However, work of exploring these properties to build robust graph neural networks is rather limited.
In this paper, we target on exploring graph properties of sparsity, low rank and feature smoothness to design robust graph neural networks. Note that there could be more properties to be explored and we would like to leave it as future work. In essence, we are faced with two challenges: (i) how to learn clean graph structure from poisoned graph data guided by these properties; and (ii) how to jointly learn parameters for robust graph neural network and the clean structure. To solve these two challenges, we propose a general framework Property GNN (Pro-GNN) to simultaneously learn the clean graph structure from perturbed graph and GNN parameters to defend against adversarial attacks. Extensive experiments on a variety of real-world graphs demonstrate that our proposed model can effectively defend against different types of adversarial attacks and outperforms the state-of-the-art defense methods.
The rest of the paper is organized as follows. In Section 2, we review some of the related work. In Section 3, we introduce notations and formally define the problem. We explain our proposed framework in Section 4 and report our experimental results in Section 5. Finally, we conclude the work with future directions in Section 6.

RELATED WORK
In line with the focus of our work, we briefly describe related work on GNNs, and adversarial attacks and defense for graph data.

Graph Neural Networks
Over the past few years, graph neural networks have achieved great success in solving machine learning problems on graph data. To learn effective representation of graph data, two main families of GNNs have been proposed, i.e., spectral methods and spatial methods. The first family learns node representation based on graph spectral theory [6,11,17]. Bruna et al. [6] generalize the convolution operation from Euclidean data to non-Euclidean data by using the Fourier basis of a given graph. To simplify spectral GNNs, Defferrard et al. [11] propose ChebNet and utilize Chebyshev polynomials as the convolution filter. Kipf et al. [17] propose GCN and simplify ChebNet by using its first-order approximation. Further, Simple Graph Convolution (SGC) [30] reduces the graph convolution to a linear model but still achieves competitive performance. The second family of models define graph convolutions in the spatial domain as aggregating and transforming local information [14,15,29]. For instance, DCNN [2] treats graph convolutions as a diffusion process and assigns a certain transition probability for information transferred from one node to the adjacent node. Hamilton et al. [15] propose to learn aggregators by sampling and aggregating neighbor information. Veličković et al. [29] propose graph attention network (GAT) to learn different attention scores for neighbors when aggregating information. To further improve the training efficiency, FastGCN [8] interprets graph convolutions as integral transforms of embedding functions under probability measures and performs importance sampling to sample a fixed number of nodes for each layer. For a thorough review, we please refer the reader to recent surveys [3,32,35].

Adversarial Attacks and Defense for GNNs
Extensive studies have demonstrated that deep learning models are vulnerable to adversarial attacks. In other words, slight or unnoticeable perturbations to the input can fool a neural network to output a wrong prediction. GNNs also suffer this problem [5,10,16,22,23,31,38,39]. Different from image data, the graph structure is discrete and the nodes are dependent of each other, thus making it far more challenging. The nettack [38] generates unnoticeable perturbations by preserving degree distribution and imposing constraints on feature co-occurrence. RL-S2V [10] employs reinforcement learning to generate adversarial attacks. However, both of the two methods are designed for targeted attack and can only degrade the performance of GNN on target nodes. To perturb the graph globally, metattack [39] is proposed to generate poisoning attacks based on meta-learning. Although increasing efforts have been devoted to developing adversarial attacks on graph data, the research about improving the robustness of GNNs has just started recently [27,31,37,40]. One way to solve the problem is to learn a robust network by penalizing the attention scores of adversarial edges. RGCN [37] is to model Gaussian distributions as hidden layers to absorb the effects of adversarial attacks in the variances. PA-GNN [27] leverages supervision knowledge from clean graphs and applies a meta-optimization way to learn attention scores for robust graph neural networks. However, it requires additional graph data from similar domain. The other way is to preprocess the perturbed graphs to get clean graphs and train GNNs on the clean ones. Wu et. al [31] have found that attackers tend to connect to nodes with different features and they propose to remove the links between dissimilar nodes. Entezari et al. [12] have observed that nettack results in changes in high-rank spectrum of the graph and propose to preprocess the graph with its low-rank approximations. However, due to the simplicity of two-stage preprocessing methods, they may fail to counteract complex global attacks.
Different from the aforementioned defense methods, we aim to explore important graph properties to recover the clean graph while learning the GNN parameters simultaneously, which enables the proposed model to extract intrinsic structure from perturbed graph under different attacks.

PROBLEM STATEMENT
Before we present the problem statement, we first introduce some notations and basic concepts. The Frobenius norm of a matrix S is defined by ||S|| 2 F = Σ i j S 2 i j . The ℓ 1 norm of a matrix S is given by ||S|| 1 = Σ i j |S i j | and the nuclear norm of a matrix S is defined (S) + denotes the element-wise positive part of matrix S where S i j = max{S i j , 0} and sдn(S) indicates the sign matrix of S where sдn(S) i j = 1, 0, or −1 if S i j >0, =0, or <0, respectively. We use ⊙ to denote Hadamard product of matrices. Finally, we use tr (S) to indicate the trace of matrix S, i.e., tr (S) = i S ii .
Let G = (V, E) be a graph, where V is the set of N nodes {v 1 , v 2 , ..., v N } and E is the set of edges. The edges describe the relations between nodes and can also be represented by an adjacency matrix A ∈ R N ×N where A i j denotes the relation between nodes v i and v j . Furthermore, we use X = [x 1 , x 2 , . . . , x N ] ∈ R N ×d to denote the node feature matrix where x i is the feature vector of the node v i . Thus a graph can also be denoted as G = (A, X). Following the common node classification setting, only a part of nodes V L = {v 1 , v 2 , ..., v l } are associated with corresponding labels Y L = {y 1 , y 2 , ..., y l } where y i denotes the label of v i .
Given a graph G = (A, X) and the partial labels Y L , the goal of node classification for GNN is to learn a function f θ : V L → Y L that maps the nodes to the set of labels so that f θ can predict labels of unlabeled nodes. The objective function can be formulated as where θ is the parameters of f θ , f θ (X, A) i is the prediction of node v i and ℓ(·, ·) is to measure the difference between prediction and true label such as cross entropy. Though there exist a number of different GNN methods, in this work, we focus on Graph Convolution Network (GCN) in [17]. Note that it is straightforward to extend the proposed framework to other GNN models. Specifically, a two-layer GCN with θ = (W 1 , W 2 ) implements f θ as Update GNN Parameters "#$ = " − ∇ *+ ℒ -.. whereÂ

Low-rank and
σ is the activation function such as ReLU.
With aforementioned notations and definitions, the problem we aim to study in this work can be formally stated as: Given G = {A, X} and partial node label V L with A being poisoned by adversarial edges and feature matrix X unperturbed, simultaneously learn a clean graph structure with the graph adjacency matrix S ∈ S = [0, 1] N ×N and the GNN parameters θ to improve node classification performance for unlabeled nodes.

THE PROPOSED FRAMEWORK
Adversarial attacks generate carefully-crafted perturbation on graph data. We refer to the carefully-crafted perturbation as adversarial structure. Adversarial structure can cause the performance of GNNs to drop rapidly. Thus, to defend adversarial attacks, one natural strategy is to eliminate the crafted adversarial structure, while maintaining the intrinsic graph structure. In this work, we aim to achieve the goal by exploring graph structure properties of low rank, sparsity and feature smoothness. The illustration of the framework is shown in Figure 2, where edges in black are normal edges and edges in red are adversarial edges introduced by an attacker to reduce the node classification performance. To defend against the attacks, Pro-GNN iteratively reconstructs the clean graph by preserving the low rank, sparsity, and feature smoothness properties of a graph so as to reduce the negative effects of adversarial structure. Meanwhile, to make sure that the reconstructed graph can help node classification, Pro-GNN simultaneously updates the GNN parameters on the reconstructed graph by solving the optimization problem in an alternating schema. In the following subsections, we will give the details of the proposed framework.

Exploring Low rank and Sparsity Properties
Many real-world graphs are naturally low-rank and sparse as the entities usually tend to form communities and would only be connected with a small number of neighbors [36]. Adversarial attacks on GCNs tend to add adversarial edges that link nodes of different communities as this is more efficient to reduce node classification performance of GCN. Introducing links connecting nodes of different communities in a sparse graph can significantly increase the rank of the adjacency matrix and enlarge the singular values, thus damaging the low rank and sparsity properties of graphs, which is verified in Figure 1a and Figure 1b. Thus, to recover the clean graph structure from the noisy and perturbed graph, one potential way is to learn a clean adjacency matrix S close to the adjacency matrix of the poisoned graph by enforcing the new adjacency matrix with the properties of low rank and sparsity. As demonstrated in Figure1c, the rank decreases much faster by removing adversarial edges than by removing normal edges. This implies that the low rank and sparsity constraint can remove the adversarial edges instead of normal edges. Given the adjacency matrix A of a poisoned graph, we can formulate the above process as follows: arg min Since adversarial attacks target on performing unnoticeable perturbations to graphs, the first term ∥A − S∥ 2 F ensures that the new adjacency matrix S should be close to A. As we assume that the graph are undirected, the new adjacency matrix should be symmetric, i.e., S = S ⊤ . R(S) denotes the constraints on S to enforce the properties of low rank and sparsity. According to [7,19,26], minimizing the ℓ 1 norm and the nuclear norm of a matrix can force the matrix to be sparse and low-rank, respectively. Hence, to ensure a sparse and low-rank graph, we want to minimize the ℓ 1 norm and the nuclear norm of S. Eq. (3) can be rewritten as: where α and β are predefined parameters that control the contributions of the properties of sparsity and low rank, respectively. One important benefit to minimize the nuclear norm ∥S∥ * is that we can reduce every singular value, thus alleviating the impact of enlarging singular values from adversarial attacks.

Exploring Feature Smoothness
It is evident that connected nodes in a graph are likely to share similar features. In fact, this observation has been made on graphs from numerous domains. For example, two connected users in a social graph are likely to share similar attributes [24], two linked web pages in the webpage graph tend to have similar contents [28] and two connected papers in the citation network usually have similar topics [17]. Meanwhile, recently it is demonstrated that adversarial attacks on graphs tend to connect nodes with distinct features [31]. Thus, we aim to ensure the feature smoothness in the learned graph. The feature smoothness can be captured by the following term L s : where S is the new adjacency matrix, S i j indicates the connection of v i and v j in the learned graph and (x i − x j ) 2 measures the feature difference between v i and v j . L s can be rewritten as: where L = D − S is the graph Laplacian matrix of S and D is the diagonal matrix of S. In this work, we use normalized Laplacian matrixL = D −1/2 LD −1/2 instead of L to make feature smoothness independent on the degrees of the graph nodes [1], i.e., where d i denotes the degree of v i in the learned graph. In the learned graph, if v i and v j are connected (i.e., S i j 0), we expect that the feature difference (x i −x j ) 2 should be small. In other words, if the features between two connected node are quite different, L s would be very large. Therefore, the smaller L s is, the smoother features X are on the graph S. Thus, to fulfill the feature smoothness in the learned graph, we should minimize L s . Therefore, we can add the feature smoothness term to the objective function of Eq. (4) to penalize rapid changes in features between adjacent nodes as: where λ is a predefined parameter to control the contribution from feature smoothness.

Objective Function of Pro-GNN
Intuitively, we can follow the preprocessing strategy [12,31] to defend against adversarial attacks -we first learn a graph from the poisoned graph via Eq. (8) and then train a GNN model based on the learned graph. However, with such a two-stage strategy, the learned graph may be suboptimal for the GNN model on the given task. Thus, we propose a better strategy to jointly learn the graph structure and the GNN model for a specific downstream task. We empirically show that jointly learning GNN model and the adjacency matrix is better than two stage one in Sec 5.4.2. The final objective function of Pro-GNN is given as arg min where L G N N is a loss function for the GNN model that is controlled by a predefined parameter γ . Another benefit of this formulation is that the information from L G N N can also guide the graph learning process to defend against adversarial attacks since the goal of graph adversarial attacks is to maximize L G N N .

An Optimization Algorithm
Jointly optimizing θ and S in Eq.(9) is challenging. The constraints on S further exacerbate the difficulty. Thus, in this work, we use an alternating optimization schema to iteratively update θ and S.
Update θ . To update θ , we fix S and remove terms that are irrelevant to θ , then the objective function in Eq.(9) reduces to: which is a typical GNN optimization problem and we can learn θ via stochastic gradient descent.
Update S. Similarly, to update S, we fix θ and arrive at where L(S, A) is defined as Note that both ℓ 1 norm and nuclear norm are non-differentiable. For optimization problem with only one non-diffiential regularizer Algorithm 1: Pro-GNN Data: Adjacency matrix A, Attribute matrix X, Labels Y L , Hyper-parameters α, β, γ , λ, τ , Learning rate η, η ′ Result: Learned adjacency S, GNN parameters θ 1 Initialize S ← A 2 Randomly initialize θ 3 while Stopping condition is not met do Return S, θ R(S), we can use Forward-Backward splitting methods [9]. The idea is to alternate a gradient descent step and a proximal step as: where η is the learning rate, prox R is the proximal operator as: In particular, the proximal operator of ℓ 1 norm and nuclear norm can be represented as [4,26], where Z = U diaд(σ 1 , ..., σ n )V ⊤ is the singular value decomposition of Z. To optimize objective function with two non-differentiable regularizers, Richard et al. [25] introduce the Incremental Proximal Descent method based on the introduced proximal operators. By iterating the updating process in a cyclic manner, we can update S as follows, After we learn a relaxed S, we project S to satisfy the constraints. For the symmetric constraint, we let S = S+S ⊤ 2 . For the constraint S i j ∈ [0, 1], we project S i j < 0 to 0 and S i j > 1 to 1. We denote these projection operations as P S (S).
Training Algorithm. With these updating and projection rules, the optimization algorithm is shown in Algorithm 1. In line 1, we first initialize the estimated graph S as the poisoned graph A. In line 2, we randomly initialize the GNN parameters. From lines 3 to 10, we update S and the GNN parameters θ alternatively and iteratively. Specifically, we train the GNN parameters in each iteration while training the graph reconstruction model every τ iterations.

EXPERIMENTS
In this section, we evaluate the effectiveness of Pro-GNN against different graph adversarial attacks. In particular, we aim to answer the following questions: • RQ1 How does Pro-GNN perform compared to the state-of-theart defense methods under different adversarial attacks? • RQ2 Does the learned graph work as expected?
• RQ3 How do different properties affect performance of Pro-GNN.
Before presenting our experimental results and observations, we first introduce the experimental settings.

Experimental settings
5.1.1 Datasets. Following [38,39], we validate the proposed approach on four benchmark datasets, including three citation graphs, i.e., Cora, Citeseer and Pubmed, and one blog graph, i.e., Polblogs. The statistics of the datasets are shown in Table 1. Note that in the Polblogs graph, node features are not available. In this case, we set the attribute matrix to N × N identity matrix.

Baselines.
To evaluate the effectiveness of Pro-GNN, we compare it with the state-of-the-art GNN and defense models by using the adversarial attack repository DeepRobust [20]: • GCN [17]: while there exist a number of different Graph Convolutional Networks (GCN) models, we focus on the most representative one [17]. • GAT [29]: Graph Attention Netowork (GAT) is composed of attention layers which can learn different weights to different nodes in the neighborhood. It is often used as a baseline to defend against adversarial attacks. • RGCN [37]: RGCN models node representations as gaussian distributions to absorb effects of adversarial attacks. It also employs attention mechanism to penalize nodes with high variance. • GCN-Jaccard [31]: Since attackers tend to connect nodes with dissimilar features or different labels, GCN-Jaccard preprocesses the network by eliminating edges that connect nodes with jaccard similarity of features smaller than threshold τ . Note that this method only works when node features are available. • GCN-SVD [12]: This is another preprocessing method to resist adversarial attacks. It is noted that nettack is a high-rank attack, thus GCN-SVD proposes to vaccinate GCN with the low-rank approximation of the perturbed graph. Note that it originally targets at defending against nettack, however, it is straightforward to extend it to non-targeted and random attacks.
In addition to representative baselines, we also include one variant of the proposed framework, Pro-GNN-fs, which is the variant by eliminating the feature smoothness term (or setting λ = 0).

Defense Performance
To answer the first question, we evaluate the node classification performance of Pro-GNN against three types of attacks, i.e., nontargeted attack, targeted attack and random attack: • Targeted Attack: Targeted attack generates attacks on specific nodes and aims to fool GNNs on these target nodes. We adopt nettack [38] for the targeted attack method, which is the stateof-the-art targeted attack on graph data. • Non-targeted Attack: Different from targeted attack, the goal of non-targeted attack is to degrade the overall performance of GNNs on the whole graph. We adopt one representative nontargeted attack, metattack [39] . • Random Attack: It randomly injects fake edges into the graph.
It can also be viewed as adding random noise to the clean graph.
We first use the attack method to poison the graph. We then train Pro-GNN and baselines on the poisoned graph and evaluate the node classification performance achieved by these methods.

Against Non-targeted Adversarial Attacks.
We first evaluate the node classification accuracy of different methods against nontargeted adversarial attack. Specifically, we adopt metattack and keep all the default parameter settings in the authors' original implementation. The metattack has several variants. For Cora, Citeseer and Polblogs datasets, we apply Meta-Self since it is the most destructive attack variant; while for Pubmed, the approximate version of Meta-Self, A-Meta-Self is applied to save memory and time. We vary the perturbation rate, i.e., the ratio of changed edges, from 0 to 25% with a step of 5%. As mentioned before, all the experiments are conducted 10 times and we report the average accuracy with standard deviation in Table 2. The best performance is highlighted in bold. From the table, we make the following observations: • Our method consistently outperforms other methods under different perturbation rates. For instance, on Polblogs dataset our model improves GCN over 20% at 5% perturbation rate. Even under large perturbation, our method outperforms other baselines by a larger margin. Specifically, under the 25% perturbation rate on the three datasets, vanilla GCN performs very poorly and our model improves GCN by 22%, 12% and 14%, respectively. • Although GCN-SVD also employs SVD to get low-rank approximation of the graph, the performance of GCN-SVD drops rapidly. This is because GCN-SVD is designed for targeted attack, it cannot adapt well to the non-targeted adversarial attack. Similarly, GCN-Jaccard does not perform as well as Pro-GNN under different perturbation rates. This is because simply preprocessing the perturbed graph once cannot recover the complex intrinsic graph structure from the carefully-crafted adversarial noises. On the contrary, simultaneously updating the graph structure and GNN parameters with the low rank, sparsity and feature smoothness constraints helps recover better graph structure and learn robust GNN parameters. • Pro-GNN achieves higher accuracy than Pro-GNN-fs especially when the perturbation rate is large, which demonstrates the effectiveness of feature smoothing in removing adversarial edges.

Against Targeted Adversarial Attack.
In this experiment, nettack is adopted as the targeted-attack method and we use the default parameter settings in the authors' original implementation. Following [37], we vary the number of perturbations made on every targeted node from 1 to 5 with a step size of 1. The nodes in test set with degree larger than 10 are set as target nodes. For Pubmed dataset, we only sample 10% of them to reduce the running time of nettack while in other datasets we use all the target nodes. The node classification accuracy on target nodes is shown in Figure 3. From the figure, we can observe that when the number of perturbation increases, the performance of our method is better than other methods on the attacked target nodes in most cases. For instance, on Citeseer dataset at 5 perturbation per targeted node, our model improves vanilla GCN by 23% and outperforms other defense methods by 11%. It demonstrates that our method can also resist the targeted adversarial attack.

Against Random Attack.
In this subsection, we evaluate how Pro-GNN behaves under different ratios of random noises from 0% to 100% with a step size of 20%. The results are reported in Figure 4. The figure shows that Pro-GNN consistently outperforms all other baselines and successfully resists random attack. Together with observations from Sections 5.2.1 and 5.2.2, we can conclude that Pro-GNN is able to defend various types of adversarial attacks. This is a desired property in practice since attackers can adopt any kinds of attacks to fool the system.

Importance of Graph Structure Learning
In the previous subsection, we have demonstrated the effectiveness of the proposed framework. In this section, we aim to understand the graph we learned and answer the second question.

Normal Edges Against Adversarial Edges.
Based on the fact that adversary tends to add edges over delete edges [31,39], if the model tends to learn a clean graph structure, the impact of the adversarial edges should be mitigated from the poisoned graph. Thus, we investigate the weights of normal and adversarial edges in the learned adjacency matrix S. We visualize the weight density distribution of normal and perturbed edges of S in Figure 5. Due to the limit of space, we only show results on Pubmed and Polblogs under metattack. As we can see in the figure, in both datasets, the weights of adversarial edges are much smaller than those of normal edges, which shows that Pro-GNN can alleviate the effect of adversarial edges and thus learn robust GNN parameters. In this subsection, we study the performance when the graph is heavily poisoned. In particular, we poison the graph with 25% perturbation by metattack . If a graph is heavily poisoned, the performance of GCN will degrade a lot. One straightforward solution is to remove the poisoned graph structure. Specifically, when removing the graph structure, the adjacency matrix will be all zeros and GCN normalizes the zero matrix into identity matrix and then makes prediction totally by node features. Under this circumstance, GCN actually becomes a feed-forward neural network. We denote it as GCN-NoGraph. We report the performance of GCN, GCN-NoGraph and Pro-GNN when the graph is heavily poisoned in Table 3.
From the table, we first observe that when the graph structure is heavily poisoned, by removing the graph structure, GCN-NoGraph outperforms GCN. This observation suggests the necessity to defend poisoning attacks on graphs because the poisoned graph structure are useless or even hurt the prediction performance. We also note that Pro-GNN obtains much better results than GCN-NoGraph. This observation suggests that Pro-GNN can learn useful graph structural information even when the graph is heavily poisoned.

Ablation Study
To get a better understanding of how different components help our model defend against adversarial attacks, we conduct ablation studies and answer the third question in this subsection.

Regularizers.
There are four key predefined parameters, i.e., α, β, γ and λ, which control the contributions for sparsity, low rank, GNN loss and feature smoothness, respectively. To understand the impact of each component, we vary the values of one parameter and set other parameters to zero, and then check how the performance changes. Correspondingly, four model variants are created: Pro-GNN-α, Pro-GNN-β, Pro-GNN-γ and Pro-GNN-λ. For example, Pro-GNN-α denotes that we vary the values of α while setting β, γ and λ to zero. We only report results on Cora and Citeseer, since similar patterns are observed in other cases, shown in Figure 6.
From the figure we can see Pro-GNN-α does not boost the model's performance too much with small perturbations. But when the perturbation becomes large, Pro-GNN-α outperforms vanilla GCN because it can learn a graph structure better than a heavily poisoned adjacency graph as shown in Section 5.3.2. Also, Pro-GNN-β and Pro-GNN-λ perform much better than vanilla GCN. It is worth noting that, Pro-GNN-β outperforms all other variants except Pro-GNN, indicating that nuclear norm is of great significance in reducing the impact of adversarial attacks. It is in line with our observation that adversarial attacks increase the rank of the graph and enlarge the singular values. Another observation from the figure is that, Pro-GNN-γ works better under small perturbation and when the perturbation rate increases, its performance degrades. From the above observations, different components play different roles in defending adversarial attacks. By incorporating these components, Pro-GNN can explore the graph properties and thus consistently outperform state-of-the-art baselines.

Two-Stage vs One-Stage.
To study the contribution of jointly learning structure and GNN parameters, we conduct experiments with the variant Pro-GNN-two under metattack . Pro-GNN-two is the two stage variant of Pro-GNN where we first obtain the clean graph and then train a GNN model based on it. We only show the results on Cora in Table 4 due to the page limitation. We can observe from the results that although Pro-GNN-two can achieve good performance under large perturbation, it fails to defend the attacks when the perturbation rate is relatively low. The results demonstrate that jointly learning structure and GNN parameters can actually help defend attacks.

Parameter Analysis
In this subsection, we explore the sensitivity of hyper-parameters α, β, γ and λ for Pro-GNN. In the experiments, we alter the value of α, β, γ and λ to see how they affect the performance of our model. More specifically, we vary α from 0.00025 to 0.064 in a log scale of base 2, β from 0 to 5, γ from 0.0625 to 16 in a log scale of base 2 and λ from 1.25 to 320 in a log scale of base 2. We only report the results on Cora dataset with the perturbation rate of 10% by metattack since similar observations are made in other settings. The performance change of Pro-GNN is illustrated in Figure 7. As we can see, the accuracy of Pro-GNN can be boosted when choosing appropriate values for all the hyper-parameters. Different from γ , appropriate values of α and λ can boost the performance but large values will greatly hurt the performance. This is because focusing on sparsity and feature smoothness will result in inaccurate estimation on the graph structure. For example, if we set α and λ to +∞, we will get a trivial solution of the new adjacency matrix, i.e, S = 0. It is worth noting that, appropriate value of β can greatly increase the model's performance (more than 10%) compared with the variant without β, while too large or too small value of β will hurt the performance. This is also consistent with our observation in Section 5.4.1 that the low rank property plays an important role in defending adversarial attacks.

CONCLUSION
Graph neural networks can be easily fooled by graph adversarial attacks. To defend against different types of graph adversarial  Figure 7: Results of parameter analysis on Cora dataset attacks, we introduced a novel defense approach Pro-GNN that learns the graph structure and the GNN parameters simultaneously. Our experiments show that our model consistently outperforms state-of-the-art baselines and improves the overall robustness under various adversarial attacks. In the future, we aim to explore more properties to further improve the robustness of GNNs.