Year: 2021

Abstract:
Graph Neural Networks (GNNs) are powerful tools in representation learning for graphs. However, they are reported to be vulnerable to adversarial attacks, raising numerous concerns for applying it in some risk-sensitive domains. Therefore, it is essential to develop a robust GNN model to defend against adversarial attacks. Existing studies address this issue only considering cleaning perturbed graph structure, and almost none of them simultaneously consider denoising features. As the graph and features are interrelated and influence each other, we propose a General Unified Graph Neural Network (GUGNN) framework to jointly clean the graph and denoise features of data. On this basis, we further extend it by introducing two operations and develop a robust GNN model(R-GUGNN) to defend against adversarial attacks. One operation is reconstructing the graph with its intrinsic properties, including similarity of two adjacent nodes’ features, sparsity of real-world graphs and many slight noises having small eigenvalues in perturbed graphs. The other is the convolution operation for features to find the optimal solution adopting the Laplacian smoothness and the prior knowledge that nodes with many neighbors are difficult to attack. Experiments on four real-world datasets demonstrate that R-GUGNN has greatly improved the overall robustness over the state-of-the-art baselines.

heading: 1 INTRODUCTION
text: Graph Neural Networks(GNNs) have drawn great attention as graphs can represent complex relationships among nodes. Graphs are ubiquitous in different domains, which are usually applied in recommender systems(Ying et al., 2018a), chemistry(Duvenaud et al., 2015), social media(Qiu et al., 2018) and so on. Utilizing the strong representation capacity of graphs, we can enhance performance of down-stream tasks such as node classification(Kipf & Welling, 2017; Velickovic et al., 2018; Klicpera et al., 2019), link prediction(Grover & Leskovec, 2016; Bojchevski et al., 2018) and graph classification(Defferrard et al., 2016; Ying et al., 2018b). A GNN model often consists of several graph convolution layers. A common practice of convolution layers is utilizing a feed-forward network to transform features and then aggregating transformed features. A series of convolution layers have been proposed and achieved great success such as GCN(Kipf & Welling, 2017), GAT(Velickovic et al., 2018) and PPNP(Klicpera et al., 2019).
However, GNN models composed of these convolution layers are vulnerable to adversarial attacks. Attacks can be conducted on either node features or the graph structure, while most existing adversarial attacks on graph data focus on modifying the graph structure(Xu et al., 2020). They always try to add, delete, or rewire edges to change the graph structure. Although these perturbations are unnoticeable, they can easily degrade the performance of GNN models, which may cause bad consequences. For example, spammers may create virtual followers to increase the chance of false messages being recommended and spread. The lack of GNNs’ robustness raises increasing concerns for applying it in some risk-sensitive domains. Therefore, it is necessary to develop graph defense techniques. Many existing defense methods focus on cleaning perturbed graphs by detecting properties of clean graphs and effects of specific attacks on graphs(Entezari et al., 2020; Jin et al., 2020b). Prior knowledge according to these researches can help GNN models defend against adversarial attacks to a certain extent. The study(Jin et al., 2020b) has proved that adversarial attacks could lead perturbed graphs to violate some properties of real graphs. For example, the rank of attacked graph increases and adversarial attacks often connect nodes with large feature differences.
However, existing studies only focus on cleaning the perturbed graph structure, and almost none of them simultaneously consider denoising features.
As the graph and features are closely tied and contain perturbations and noises, in this paper, we propose a General Unified Graph Neural Network(GUGNN) framework to jointly clean the graph and denoise features. Based on the GUGNN framework, we further introduce two kinds of operations. One operation is reconstructing the graph with its properties that real-world graphs are sparse(Zhou et al., 2013), the features of two adjacent nodes tend to be similar(McPherson et al., 2001) and perturbed graphs have many slight noises with small eigenvalues. Nodes with more neighbors are hard to attack(Zügner et al., 2018). Though we cannot change the number of nodes’ first-order neighbors, we can adjust the size of nodes’ neighborhood to add some high-order neighbors to nodes. According to this principle, from the denoising perspective, we design the convolution operation for features to find the optimal solution. Utilizing the two kinds of operations above, we develop a robust model(R-GUGNN), which can be applied for defending against different adversarial attacks.
The contributions of this paper are summarized as follows:
• We propose GUGNN framework to jointly clean the graph and denoise features for perturbations and noises existing in the graph and features.
• We introduce two kinds of operations to clean attacked graphs and denoise features respectively based on the GUGNN framework.
• For defending against adversarial attacks, we develop a concrete model R-GUGNN to realize the goal of the GUGNN framework utilizing the two kinds of operations.
• Experiments show that R-GUGNN has a strong capacity for defending against different adversarial attacks and stably outperforms the state-of-the-art defense models.

heading: 2 RELATED WORK
text: This section has two parts, including graph neural networks, and adversarial attacks and defenses for GNNs.

heading: 2.1 GRAPH NEURAL NETWORKS
text: In this subsection, we review some famous graph neural network models, including GCN, GAT, PPNP, and a unified GNN framework UGNN. For more knowledge about GNNs, you can refer to some reviews(Wu et al., 2020; Zhang et al., 2020).
The convolution of GCN(Kipf & Welling, 2017) is defined in the graph spectral domain. Avoiding computing the full eigenvectors of the graph Laplacian matrix, based on Chebyshev polynomials, GCN only uses the first-order polynomial to simplify the graph convolution, which has been an accepted good graph convolution layer for its performance. The convolution of GAT(Velickovic et al., 2018) is defined in the spatial domain. The difference between GAT and GCN is that GAT learns different attention scores for neighbors when aggregating features. PPNP(Klicpera et al.,
2019) derives a propagation scheme based on personalized PageRank. It propagates information from a large and adjustable neighborhood instead of the first-order neighborhood directly. The neighborhood can be adjusted via a hyper-parameter.
UGNN(Ma et al., 2020) is a unified GNN framework available for different feature propagation processes from a denoising perspective. It proposes a denoising optimization problem with the Laplacian regularization term and tries to solve it in different ways utilizing the first derivative or the optimal solution. Original Laplacian matrix can be also replaced with different normalized forms. Different solutions to the optimization problem are corresponding to various convolution layers with different feature aggregation processes such as GCN, GAT, PPNP and so on.

heading: 2.2 ADVERSARIAL ATTACKS AND DEFENSES FOR GNNS
text: We recommend a repository DeepRobust(Li et al., 2020) for readers. It contains many adversarial attacks and defenses on the graph, which is quite useful for researchers. For more knowledge about adversarial attacks and defenses for GNNs, you can refer to the review(Jin et al., 2020a).
Some adversarial attack methods have been proposed to show the vulnerability of GNNs with some unnoticeable perturbations added to the graph structure or node attributes. In the field of node classification, the aim of adversarial attacks is fooling GNNs into classifying nodes incorrectly. Poisoning attacks change the graph structure before we train GNN models, which is one of the most common settings of adversarial attacks on graph data. Poisoning attacks have various types, including global attack, targeted attack and random attack. Based on the whole graph, the goal of global attack is to degrade the overall performance of GNNs. One of the state-of-the-art global attacks is metattack(Zügner & Günnemann, 2019), which generates the poisoning attacks based on metalearning. Targeted attack generates attacks on some specific nodes and aims to fool GNNs on these target nodes. The nettack(Zügner et al., 2018) is one of the state-of-the-art targeted attacks, which aims to change the graph structure and features of target nodes or nearby nodes with perturbations remaining unnoticeable. Random attack adds random noises to the clean graph whose concrete practice is adding, removing or flipping edges randomly.
Methods about preventing GNNs from adversarial attacks are also developed to improve the robustness of GNNs recently. To mitigate the effects of adversarial attacks on the graph, RGCN(Zhu et al., 2019) uses Gaussian distributions as hidden representations of nodes instead of plain vectors in other GNNs. Considering that nettack is a high-rank attack, GCN-SVD(Entezari et al., 2020) is proposed to reconstruct the perturbed graph with only the top-k largest singular components. Using such a low-rank approximation, GCN-SVD can reduce the effects of nettack. In fact, the practice of ensuring low-rank is removing noises with small singular values of the graph. Pro-GNN(Jin et al., 2020b) jointly optimizes a structural graph and a robust GNN model from the perturbed graph with some properties of clean graphs. Pro-GNN has big improvement over other defense models with these properties. However, like other defense models, Pro-GNN doesn’t take denoising features into account jointly.

heading: 3 THE PROPOSED FRAMEWORK
text: In this section, we first present GUGNN framework, and then we introduce a novel graph reconstruction operation. At last, we show the convolution operation for features and our concrete design of R-GUGNN model, which is used to realize the goal of GUGNN framework.

heading: 3.1 NOTIONS
text: We denote some notations here. Denote X ∈ RN×d as the feature matrix, where N, d represent the number of samples and the dimension of features respectively. Denote G = {V, E} as the graph, where V represents node sets and E represents edge sets. We also use the adjacency matrix A ∈ RN×N to represent G.
Algorithm 1: R-GUGNN Input: Adjacency matrix A, Feature matrix X, Labels y, Hyper-parameters m, c,β, λ, Learning rate η. Output: GNN parameters θ
1 Ã = A + I; Initialize S = Ã; 2 for i= 1 to m do 3 Calculating Z in formula(5); 4 S = S− c2Z; 5 S = prox∗β(S); 6 S = proxs(S); 7 Initialize F = X;Randomly initialize θ; 8 while Stopping condition is not met do 9 Forward propagation using two convolution layers:
10 Using feature transformation formula: F = FW, 11 and feature aggregation formula: F = (I + λL̂)−1F; 12 Getting output y′; 13 Calculating gradient g according to y and y′; 14 Backward propagation: θ = θ − ηg; 15 return θ;

heading: 3.2 THE GENERAL UNIFIED GNN FRAMEWORK
text: To discard perturbations and noises in the graph and features, considering the tight connection between them, we propose our general united graph neural network(GUGNN) framework to solve such problem, which is shown as follows:
argmin S,F
L = ‖S− A‖2F + γ‖F− X‖2F + c · tr(FTLF) + β · f(S) (1)
where S and F are the learned adjacency and feature matrix. L is the Laplacian matrix of S. L = D − S, where D is a diagonal matrix and Dii = ∑N j=1 Sij . L can be also replaced with different normalized forms. tr(FTLF) is Laplacian regularization term for both denoising features and cleaning the graph. f(S) is a flexible regularization term to enforce some prior over S. γ, c and β are hyper-parameters to balance different components.
From a united perspective, we view that both features and the graph contain noises and our goal is jointly optimizing F and S. tr(FTLF) can be rewritten as 12 ∑N i,j=1 Sij(fi − fj)2, where fi is the i-th row of F. This term represents that features of two adjacent nodes should be similar, which is the guidance for both learning F and S. Although X and A have some noises, they can represent the real features and the graph to a large extent. So, the learned F and S should be similar to X and A respectively, which are the meanings of ‖F − X‖2F and ‖S − A‖2F . In addition, we add some prior to the graph in f(S) to make it more accurate.

heading: 3.3 THE NOVEL GRAPH RECONSTRUCTION OPERATION
text: We focus on cleaning the perturbed graph supposing F=X. Formula(1) of GUGNN can be rewritten as follows:
argmin S
L = ‖S− A‖2F + c · tr(XTLX) + β · f(S) (2)
Considering that the graph contains noises, we rewrite formula(2) as follows:
argmin S
L = ‖S− Ã‖2F + c · tr(XT L̂X) + β‖S‖∗
= L1 + L2 + L3 (3)
The adjacency matrix with self-loop Ã and the normalized Laplacian matrix L̂ are adopted. L̂ = D− 1 2 LD−
1 2 . tr(XT L̂X) is equal to 12 ∑N i,j=1 Sij( xi√ Dii − xj√ Djj )2. Since degrees of the perturbed
graph are approximately equal to those of the real graph, for the convenience of calculation, we let Dii = ∑N j=1 Ãij . ‖S‖∗ = ∑rank(S) i σi, where σi is the i-th singular value of S.
To solve formula(3), we let ∂L1+L2∂S = 0 to get the closed form solution.
∂L1 + L2 ∂S = 2(S− Ã) + c
 ( x1√ D11 − x1√D11 ) 2 · · · ( x1√D11 − xN√ DNN )2 ... . . .
... ( xN√DNN − x1√D11 ) 2 · · · ( xN√DNN − xN√ DNN )2
 = 0 (4)
S = Ã− c 2
 ( x1√ D11 − x1√D11 ) 2 · · · ( x1√D11 − xN√ DNN )2 ... . . .
... ( xN√DNN − x1√D11 ) 2 · · · ( xN√DNN − xN√ DNN )2  (5) We denote formula(5) as S = Ã − c2Z for convenience. A proximal operator of nuclear norm is adopted to remove noises and reserve main properties(Entezari et al., 2020).
prox∗β(S) = Udiag(max{σi − β, 0})iVT (6)
where S = Udiag(σ1 . . . σN )VT is the singular value decomposition of S. Let S = prox∗β(S) to represent this step. For the constraint Sij ∈ [0, 1], we let S = S + I to enhance self-loop, and set Sij<0 to 0 and Sij>1 to 1. We denote this step as S = proxs(S), which can make the graph sparse at the same time.

heading: 3.4 THE CONVOLUTION OPERATION FOR FEATURES
text: After getting the cleaned graph through several graph reconstruction operations above, we fix it and focus on denoising features, formula(1) of GUGNN can be rewritten as follows:
argmin F
L = ‖F− X‖2F + λ · tr(FTLF) (7)
where λ = cγ . In this case, formula(7) is equal to that of UGNN(Ma et al., 2020). We use the normalized Laplacian matrix L̂ and let ∂L∂F = 0 to find the optimal solution. ∂L ∂F = 2(F− X) + 2λL̂F = 0 (8)
F = (I + λL̂)−1X (9) Formula(9) is the process of feature aggregation. Before it, we let X = XW to transform features, where W is the parameter of a single GNN convolution layer. This is our convolution operation for features, which is proved(Ma et al., 2020) equal to PPNP(Klicpera et al., 2019). So, our convolution operation for features can also adjust nodes’ neighborhood to enhance the model’s robustness.

heading: 3.5 THE DESIGN OF R-GUGNN MODEL
text: Utilizing the two kinds of operations, we design R-GUGNN model and show it in Figure 1, where m is the number of graph reconstruction operations we can set. In step À, we fix features and clean the graph with m graph reconstruction operations. In step Á, we fix the cleaned graph and denoise features with two graph convolution layers. We train GNN parameters θ using the two graph convolution layers and classify nodes finally. Concrete steps of R-GUGNN are shown in Algorithm 1.

heading: 4 EXPERIMENTS
text: In this section, we evaluate the effectiveness of R-GUGNN model compared with the state-of-theart GNN models against different attacks. We first introduce the experimental settings and then present results of a series of experiments. At last, we conduct the ablation study and analyze hyperparameters of R-GUGNN.

heading: 4.1 EXPERIMENTAL SETTINGS

heading: 4.1.1 DATASETS
text: We compare different models on four benchmark datasets, including three citation graphs, i.e., Cora(McCallum et al., 2000), Citeseer(Giles et al., 1998) and Cora-ML(Bojchevski & Günnemann, 2017), and one blog graph, i.e., Polblogs(Jin et al., 2020b). Cora-ML is the subset of machine learning papers from Cora dataset, which is also a well-known dataset in GNN field. Since Polblogs dataset has no node features, a N × N identity matrix is used to act as the feature matrix. We only consider the largest connected component(LCC) in each dataset(Jin et al., 2020b; Zügner et al., 2018). Table 1 contains detailed information about the dataset.

heading: 4.1.2 BASELINES
text: R-GUGNN model are compared with the state-of-the-art GNN and defense models in repository DeepRobust(Li et al., 2020), i.e., GCN(Kipf & Welling, 2017), GAT(Velickovic et al., 2018), RGCN(Zhu et al., 2019), GCN-SVD(Entezari et al., 2020) and Pro-GNN(Jin et al., 2020b). We adopt the default parameter settings in GCN and GAT. The number of hidden units of RGCN are tuned from {16, 32, 64, 128}. The reduced rank of the perturbed graph in GCN-SVD is tuned from {5, 10, 15, 50, 100, 200}. For Pro-GNN, we use the tuned hyper-parameters the author gives online.

heading: 4.1.3 PARAMETER SETTINGS
text: Just as(Jin et al., 2020b), for each dataset, we choose 10% of nodes for training, 10% of nodes for validation and the remaining 80% of nodes for testing. The average performance of 10 runs is reported for all experiments below. The hyper-parameters of all the models are tuned based on the loss and accuracy on the validation set. Note that the same hyper-parameters are used under the same attack for the same dataset no matter what perturbation rate is. If there are no special instructions, all models adopt two graph convolution layers with 16 hidden units. Learning rate of Adam optimizer η is fixed as 0.01 and negative log likelihood loss is adopted for a fair comparison(RGCN has its own loss function).

heading: 4.2 PERFORMANCE AGAINST DIFFERENT ATTACKS
text: The node classification performance of R-GUGNN is evaluated against three types of poisoning attacks, i.e., global attack, targeted attack and random attack. Since Ploblogs dataset has no real node features, hyper-parameter c of R-GUGNN is set to 0 on Ploblogs dataset.

heading: 4.2.1 AGAINST GLOBAL ATTACK
text: The famous metattack(Zügner & Günnemann, 2019) is used as the global attack to conduct experiments and all the default parameter settings in the authors’ original implementation are adopted. Concretely, the strongest variant Meta-Self is applied for all datasets. The perturbation rate of metattack on the graph is from 0% to 25% with a step of 5%, since too heavy attacks are noticeable and make no sense. We report the average accuracy of node classification with standard deviation on test set and highlight the optimal results in bold. Concrete results are shown in Table 2 and we draw some conclusions:
• R-GUGNN has great improvement compared to others on four datasets. The average improvement of accuracy under different perturbation rates over GCN on four datasets is about 16%, 10%, 19% and 21% respectively. When the graph is heavily perturbed, the improvement is larger. For example, when the perturbation rate is 20%, the improvement over GCN is about 23%, 16%, 25% and 25% on four datasets respectively. When compared with different second best models, improvement can reach 10%, 6%, 19% and 7% on four datasets. These results prove that R-GUGNN can defend against metattack very well.
• Accuracy of R-GUGNN is stably high under different perturbation rates on all datasets. The gap between accuracy of R-GUGNN on clean and perturbed graphs is small. For example, gaps of the accuracy of R-GUGNN under 25% and 0% metattack on Cora and Citeseer datasets are only about 7% and 2%. Besides, the overall standard deviations of R-GUGNN are small. However, the lack of real node features on Polblogs dataset causes big standard deviations when the graph is heavily attacked.

heading: 4.2.2 AGAINST TARGETED ATTACK
text: The typical netttack(Zügner et al., 2018) is employed as the targeted attack to conduct experiments and all the default parameter settings in the authors’ original implementation are adopted. We select nodes with degree >10 as targeted nodes from the test set. The number of perturbations of the graph on each targeted node is from 0 to 5 with a step of 1. We report accuracy of these targeted nodes as results, which are shown in Figure 2. R-GUGNN suffers less effects of nettack and also performs greatly and stably. For example, compared to the second best method Pro-GNN, R-GUGNN achieves 10% and 5% improvement on Citeseer and Cora-ML datasets. These results prove that R-GUGNN can defend against netttack very well.

heading: 4.2.3 AGAINST RANDOM ATTACK
text: Performance of R-GUGNN under random attack is evaluated here. We add random perturbations on the graph from 0% to 100% with a step of 20%. Concrete results are shown in Figure 3. R-GUGNN outperforms other models again and the improvement is distinct. For example, compared to different second best models, R-GUGNN achieves a 2.5% and 3.5% improvement on Citeseer and Cora-ML datasets. These results prove that R-GUGNN can defend against random attack very well.
From the overall performance, we observe that the advantage of R-GUGNN is obvious compared with others and its performance is stably great. In conclusion, R-GUGNN is robust enough to defend against different attacks.

heading: 4.3 ABLATION STUDY
text: R-GUGNN contains m graph reconstruction operations. If we discard these operations and only use two convolution layers for features, R-GUGNN is equal to PPNP(Klicpera et al., 2019). So, in this
subsection, we compare PPNP with GCN and R-GUGNN on Cora dataset under random attack as an example to illustrate. In addition, we set β and c to 0 to understand the impact of each component in the graph reconstruction operation. Furthermore, we observe standard deviations of R-GUGNN when c=0.
In Figure(4)(a), we can see that performance of R-GUGNN is better than PPNP and performance of GCN is the worst. It shows graph reconstruction operations are significant(R-GUGNN vs PPNP), and adjusting neighborhood is beneficial to defending against attacks(PPNP vs GCN). PPNP curve and the no-β curve overlap very well, which indicates that removing noises with small singular values plays a quite important role in cleaning the graph. What’s more, if c=0, not only model’s performance is poor, but also the standard deviation rises a lot especially when the graph is heavily attacked in Figure(4)(b). It shows the Laplacian regularization term is significant in improving stability of R-GUGNN, which explains why the standard deviation is big on Polblogs dataset under heavy attack.

heading: 4.4 PARAMETER ANALYSIS
text: In this subsection, we show performance of R-GUGNN with different values of hyper-parameters i.e., m, c, β, and λ. We use Cora-ML dataset under 15% metattack as an example to illustrate. The value range of m is from 1 to 5 with the step of 1. The value of c is selected in {10−5, 10−4, 10−3, 10−2, 10−1}. We select β from 1 to 3.5 and λ from 0.5 to 3 with the step of 0.5. In the process of tuning one hyper-parameter, other hyper-parameters are fixed as the optimal. Figure 5 shows effects of different values of hyper-parameters.
m is the number of graph reconstruction operations. Our novel operations of R-GUGNN are important for defending against attacks, and even one such operation improves model’s robustness(76.87% accuracy). However, proper m can boost the accuracy and too many such operations cannot benefit R-GUGNN. β is also a key affecting the performance of R-GUGNN, which controls how many noises with small singular values to remove. When β is too small, noises cannot be removed entirely. While when β is too big, the main properties of the graph can be hurt. λ is used to adjust the size of nodes’ neighborhood when propagating features and choosing proper λ is also important. c is used to control the Laplacian smoothness of the graph. We find the big value of c hurts the performance of R-GUGNN, but when c is small, accuracy doesn’t decrease a lot. From a whole performance, all hyper-parameters have an interval of values where the performance of R-GUGNN is stably great.

heading: 5 CONCLUSION
text: In this paper, we propose GUGNN, a novel general unified framework to effectively enhance the robustness of GNNs against adversarial attacks by jointly cleaning the perturbed graph and denoising the features of data. Furthermore, we extend this framework by reconstructing the graph and making convolution operations of features with intrinsic properties, and propose a robust GNN model RGUGNN. Experiment results show that R-GUGNN stably outperforms the state-of-the-art baselines under different adversarial attacks. In the future, we aim to extend this framework to other models on graphs, even more complicated graph structures for mining the rich value underlying graph data of various domains.

Review summaries:
This paper focuses on developing a robust GNN model to defend against adversarial attacks on both graph structures and node features. More specifically, a general unified graph neural network is proposed to learn a graph structure and node features to correct the adversarial attacks. This a two-step approach. First, one operation is applied to reconstruct the graph with the node features. Then, the node features are updated by another operation with the learned graph structure. Experiments are conducted on four small datasets for evaluation.

The authors propose a General Unified Graph Neural Network (GUGNN) framework to address graph and feature denoising. They use this framework to design a graph neural network (R-GUGNN) which is Robust against poison adversarial attacks in a semi-supervised node classification setting. The authors demonstrate on four common datasets (Cora, Citeseer, Cora-ML & Polblogs) that their method is generally more robust against perturbation compared to commonly used graph neural networks (GCN, GAT) and models which are designed to be robust in the same setting (RGCN, GCN-SVD, Pro-GNN).

Considering the problem of adversarial manipulations of graphs, the authors propose a framework for "cleaning" the graph structure and its features to obtain more robust predictions. The core contribution, compared to existing works, is the additional considering of the feature cleaning. Technically, the authors first perform the graph cleaning (phrased as some kind of sparse, trace minimization problem) followed by some feature cleaning (phrased as some kind of feature diffusion/propagation). Experiments on standard (small) benchmark datasets shows some improvements.

The paper proposes a robust model for graph neural networks (GNNs) to defend against adversarial attacks. While most of the defense mechanisms in previous work focus on identifying and fixing the perturbed structure of the underlying graph, this paper proposes to jointly fix the perturbed structure as well as the node features. The proposed objective function captures these components along with weighting by some hyper-parameters. The experiments include several baselines and show results on different attack models: targeted attack, untargeted or global attack, and random attack. The experiments also have results on ablation study as well as hyper-parameters.