Year: 2021

Abstract:
Graph Neural Networks (GNNs) have achieved outstanding success in a wide variety of domains and applications. However, they are still vulnerable to unnoticeable perturbations of graphs specially designed by attackers, causing significant performance drops. Developing algorithms to defend GNNs with robust graphs vaccinating from adversarial attacks still remains a challenging issue. Existing methods treat every edges individually or regularize them by specific robust properties, which ignores the structural relationships among edges or correlations among different properties. In this paper, we propose a tensor-based framework for GNNs to learn robust graphs from adversarial graphs by aggregating predefined robust graphs to enhance the robustness of GNNs via tensor approximation. All the predefined robust graphs are linearly compressed into and recovered from a lowrank space, which aggregates the robust graphs and the structural information in a balanced manner. Extensive experiments on real-world graph datasets show that the proposed framework effectively mitigates the adverse effects of adversarial attacks and outperforms state-of-the-art defense methods.

heading: 1 INTRODUCTION
text: In real-world applications, many complex structures from various domains can be represented by graph data, such as social networks, chemistry (molecular), biology (protein-protein interaction networks), knowledge databases, and recommender systems. Graph Neural Networks (GNNs) have achieved outstanding success for graph data in a wide range of application areas (Kipf & Welling, 2017; Battaglia et al., 2018; Wu et al., 2021; Zhou et al., 2020). GNNs are equipped with a messagepassing scheme (Gilmer et al., 2017), where the node representation is updated by transforming the aggregated representations propagated from its neighbor nodes via edges, and are optimized for performance on downstream tasks. In this fashion, GNNs can generate representations capturing both graph structural information and node feature information.
In this paper, we focus on the semi-supervised task of node classification (Kipf & Welling, 2017) by GNNs. GNNs have achieved promising performance in recent years, but have also shown to be vulnerable to adversarial attacks (Bojchevski & Günnemann, 2019; Dai et al., 2018; Jin et al., 2020a; Liu et al., 2019; Ma et al., 2019; Wu et al., 2019b; Zügner et al., 2018; Zügner & Günnemann, 2019b). Most of adversarial attack methods for GNNs focus on poisoning attacks, which deliberately rebuild the graph topology by changing an unnoticeable number of edges before the training process of GNNs. These unnoticeable perturbations can significantly degrade learned graph representations and confuse GNNs to catastrophically misclassify nodes. To defend the GNNs from adversarial edges, existing methods attempt to learn robust graphs, which are extracted from the perturbed graphs and perform solidly with GNNs. One way is to learn robust graph by reducing the attention weights of potentially malicious edges (Zhu et al., 2019; Tang et al., 2019; 2020; Zhang & Zitnik, 2020). Preprocessing the perturbed graphs to obtain robust graphs is another way to defend GNNs from adversarial edges (Wu et al., 2019b; Entezari et al., 2020). Most of the existing works only pay attention to a specific property of graph data (e.g., low-rank property (Entezari et al., 2020; Al-Sayouri et al., 2020), feature similarities (Wu et al., 2019b)). Pro-GNN (Jin et al., 2020b) regularizes the learned graph to fit a set of the corresponding graph properties and learns the weights for each node instead of the whole graph. These methods show improvements in defending GNNs from poisoning attacks but ignore the connection and balance between different graph properties or different nodes. The learned robust graph has every single edge with a weight close to the original graph and following the specific
graph properties, however, when looking through the point of view from the whole graph, it is either ignoring the original structure of the graph or not able to remove most of the perturbed edges.
To learn better robust graph from adversarial graphs, we propose a Tensor-based framework for Graph Neural Networks (TGNN), which can aggregate common information from the predefined robust graphs and the adversarial graphs and thus enhance the robustness of GNNs with improved classification performance. TGNN approximates the graph tensor, which consists of the attacked graph and several predefined robust graphs focusing on specific graph properties (e.g., low-rank, feature similarity properties), via low-rank approximation by applying tensor decomposition. By preserving the low-rank tensor representation, TGNN generates the robust graph and maintains the common core tensor space between the learned robust graph and predefined robust graphs. The learned robust graph is no longer calculated individually by each entry but aggregated with the common core tensors, balancing not only the different graph properties but also varied structural graph information. The learned robust graph is fed into GNNs and jointly leaned with GNN parameters. Extensive empirical results show that our proposed TGNN framework consistently improves the robustness of the learned graph and significantly boosts the performance of node classification task for GNNs against adversarial graphs.

heading: 2 RELATED WORKS

heading: 2.1 GRAPH NEURAL NETWORKS AND ADVERSARIAL ATTACKS ON GRAPHS
text: GNNs have achieved great success in solving machine learning problems on graph data in recent years. Existing GNNs can be divided into two categories: spectral-based methods where graph spectral theory (Bruna et al., 2014; Defferrard et al., 2016; Kipf & Welling, 2017; Wu et al., 2019a; Chen et al., 2018) was applied to learn node representations; and spatial-based GNNs based on local-dependence assumption of graph-structured data that graph convolution is defined in the spatial domain as aggregating and transforming local information (Gilmer et al., 2017; Hamilton et al., 2017; Velickovic et al., 2018; Atwood & Towsley, 2016).
Extensive studies have demonstrated that deep learning models are vulnerable to adversarial attacks (Goodfellow et al., 2015; Kurakin et al., 2017a;b; Rakhsha et al., 2020). Attackers add unnoticeable perturbations to the input for altering the output of the deep learning model. GNNs are also fragile to adversarial attacks (Bojchevski & Günnemann, 2019; Dai et al., 2018; Jin et al., 2020a; Liu et al., 2019; Ma et al., 2019; Wu et al., 2019b; Zügner et al., 2018; Zügner & Günnemann, 2019b). It is more challenging to investigate adversarial attack on graphs due to the discrete graph and dependent nodes compared with independent samples or grid data. Nettack (Zügner et al., 2018) preserves degree distribution and constrains feature co-occurrence to generate unnoticeable perturbations to poison GNNs in training time. Reinforcement learning was employed in RL-S2V (Dai et al., 2018) to generate adversarial attacks in testing-time. Both of the above two methods can only degrade the performance of GNN on target nodes. To attack the graph globally, metattack (Zügner & Günnemann, 2019b) is proposed to generate non-targeted poisoning attacks based on meta-learning.

heading: 2.2 DEFENSE ON GRAPHS
text: The studies for improving the robustness of GNNs have received increasing attention recently (Tang et al., 2019; Wu et al., 2019b; Zhu et al., 2019; Zügner & Günnemann, 2019a; Bojchevski et al., 2020; Geisler et al., 2020). In RGCN (Zhu et al., 2019), Gaussian distribution is adopted in hidden layers to absorb the effects of adversarial attacks into the variances. A meta-optimization way is proposed in PA-GNN (Tang et al., 2019) to learn attention scores for robust GNNs with the help of supervision knowledge from clean graphs. Transfer learning (Tang et al., 2020) is leveraged to improve the robustness of GNNs against poisoning attack with additional graph data from the similar domain during training. It is observed in Wu et al. (2019b) that attackers tend to connect to nodes with different features occurrence, GNN-Jaccard is proposed to remove the links between dissimilar nodes to identify the manipulated edges. GNN-SVD (Entezari et al., 2020) is proposed to preprocess the graph with its low-rank approximations to remove noisy information through an SVD decomposition. Pro-GNN (Jin et al., 2020b) proposes three different regularizers which correspondingly regularize the graph to be sparse, low-rank and smooth the features of connected nodes. In Zhang & Zitnik (2020), GNNGuard is proposed to quantify the relationship between the graph and node features,
and assigns less weight to suspicious edges, which mitigates negative effects of the adversarial perturbations.
Different from the aforementioned defense methods, we aim to aggregates predefined robust adversarial graphs to form a powerful regularization, which can be extended to different GNNs straightforwardly to enhance the robustness of GNNs.

heading: 3 METHODOLOGY
text: Before presenting the proposed method, we first introduce the problem statement for node classification with GNN, including some basic notations and concepts. Let G = (V, E ,X) be a graph, where V represents the set of N nodes {v1, v2, · · · , vN}, E represents the set of M edges {(i1, j1), (i2, j2), · · · , (iM , jM )}, and X ∈ RN×d denotes the node feature matrix composed of the feature vector xi of the node vi. The edges E describe the graph by the pair-wise relations between nodes, which can also be represented by an adjacency matrix A ∈ RN×N , one of the most popular representation for graph, where Aij = 1 ⇐⇒ (i, j) ∈ E (otherwise Aij = 0). In this work, we alternately use the concept of adjacency matrix and graph. Thus, a graph can also be denoted as G = (A,X). In this work, we focus on the common semi-supervised node classification setting for graph representation. Given a single (attributed) graph G = (A,X), the part of nodes VP = {v1, v2, · · · , vP } ⊆ V are associated with the corresponding labels YP = {y1, y2, · · · , yP }, where yi is the class label (e.g., the topic of a paper in a citation graph) of vi, the goal of node classification in GNN is to learn a neural network representing a function fθ : VP → YP which maps the nodes to the corresponding labels so that fθ can be generalized to predict the labels of unlabeled nodes (i.e., nodes not in VP ), where θ is the parameters of fθ. With LCE(·, ·) denoting the cross entropy loss, the objective function of node classification task in GNN can be formulated as:
min θ Lcls(θ,A,X,YP ) =
1
P P∑ i=1 LCE (yi, fθ(X,A)i) , (1)
where fθ(X,A)i is the prediction of node vi. Note that our proposed method can be extended to different GNNs straightforwardly, in this work, we focus on Graph Convolution Network (GCN) proposed in Kipf & Welling (2017) among numbers of different GNNs. Specifically, we adopt a two-layer GCN with layers (fθ1 , fθ2) and the corresponding parameters (θ1, θ2) = (W1,W2) can be denoted as:
fθ(X,A) = softmax(fθ2(fθ1(X,A),A)) = softmax(Âσ(ÂXW1)W2), (2)
where σ is the activation function and Â = D̂− 1 2 (A + I)D̂− 1 2 represents diagonal normalized
A + I. Here, self-loop I is added to A and D̂ is the diagonal degree matrix of A + I such that D̂ii = 1 + ∑ jAij .

heading: 3.1 THE PROPOSED FRAMEWORK
text: Although existing GNNs achieve the state of the art performance in node classification task, they are still vulnerable to edge perturbations generated by adversarial attacks. We refer to the attacked graph with carefully designed edge perturbations degrading GNNs performance as adversarial graphs and the graphs which are robust for GNNs to perform accurate node classification as robust graphs. Learning robust graphs from adversarial graphs can vaccinate the GNNs from the poisoned graph data for stable performance in node classification task. With the statements at the beginning of this section, the goal of learning robust graphs can be formally stated as:
Given G poisoned by adversarial graph Ã, the unperturbed feature X and partial node labels YP , we aim to learn GNN parameters θ and robust graph Ā replacing Ã to enhance robustness of GNNs and improve node classification performance for unlabeled nodes.
To generate robust graph, we propose a Tensor-based robust graph aggregation framework for Graph Neural Networks (TGNN) shown in Figure 1. TGNN aggregates K predefined robust adversarial
graphs Ar = {Ark|Kk=1} to learn the robust graph Ā from adversarial graph Ã. In particular, TGNN first calculates K predefined robust graphs Ar and combines them with the adversarial graph Ã to form a tensor structure, then decomposes the graph tensor into several core tensors C and reconstructs the tensor via low-rank approximation. By preserving the low-rank tensor representation for the graphs, TGNN generates the robust graph Ā and maintains the multi-linear relation between the learned robust graph Ā and predefined robust graphs Ar. Then the learned robust graph Ā will be fed into the GNN. TGNN simultaneously updates both the GNN parameters θ and Ā by updating learnable core tensors C during the training process. In this way, TGNN can achieve a more robust graph and better node classification performance. In the following sections, we will discuss how to aggregate robust graphs with TGNN, the predefined graphs, and the results of the generated robust graph of TGNN.

heading: 3.2 TENSOR-BASED AGGREGATION FOR ROBUST GRAPHS
text: A tensor, also called multi-dimensional array, is denoted by Euler script letter, e.g., T , where each dimension of the tensor is called a mode. In TGNN, we formulate a batch of adjacency matrices as a three-mode tensor. Specifically, given perturbed adjacency matrix Ã and K robust adjacency matrices Ar1, · · · ,ArK , we stack these adjacency matrices as a graph aggregation tensor T ∈ R(K+1)×N×N , where T (1, :, :) = Ã and T (k + 1, :, :) = Ark for 1 ≤ k ≤ K. To achieve a low-rank approximation of the graph aggregation tensor T , we perform tensor approximation by decomposing T into several smaller core tensors following specific formulations (Harshman et al., 1970; Tucker, 1966; Oseledets, 2011; Zhao et al., 2016), and then apply multilinear contraction operations on these core tensors to reconstruct approximated tensor T̄ . Low-rank approximation can discard high-rank noises in the graph to improve the performance of GNNs against adversarial graphs (Jin et al., 2020b; Entezari et al., 2020). Also, graphs in the real-world are often naturally lowrank because nodes within a community or the same class are apt to have similar neighbors or similar node features. Hence, low-rank approximation is a potential way to extract the robust graph from the adversarial graphs. Tensor decomposition is a powerful tool to compress the high-dimensional data into low-rank representation (Cichocki et al., 2015; Sidiropoulos et al., 2017). In this paper, we attempt to decompose the graph aggregation tensor T with Canonical Polyadic (CP) (Harshman et al., 1970), Tucker Tucker (1966) and Tensor-Train (Oseledets, 2011) formulations, respectively, the comparison results with three different decomposition methods are reported in Supplementary. To describe the process of learning robust graph, we use CP decomposition method as an example
which decomposes a three mode tensor T ∈ R(K+1)×N×N into:
T ≈ T̄ = ΣRt=1C0(t)C1(t, :) ◦C2(t, :) ◦C3(t, :), (3)
where C1 ∈ RR×(K+1), C2 ∈ RR×N , C3 ∈ RR×N and C0 ∈ RR are trainable core tensors (matrix/vectors, C0 is used as normalization vector). R represents the value of rank which is relatively small as compared to the node number N and ‘◦’ denotes outer product (i.e., T̄ (i, j, k) = ∑R t=1 C0(t)C1(t, i)C2(t, j)C3(t, k)). After the tensor graph approximation, TGNN takes the first slice of the first-mode in the approximated graph aggregation tensor, i.e., T̄ (1, :, :) as the learned robust graph Ā to be the input for GNNs. With C representing the sets of all core tensors, the objective function for TGNN can be defined as:
min θ,C L = Lcls(θ, Ā,X,YP ) + λ||T̄ − T ||2F , (4)
where Lcls is the classification loss from Eqn. (1) and λ is a hyper-parameter to balance the tensor approximation loss and the classification loss.
The decomposed representation of T in Eqn. (3) maps the graphs to a shared core tensor space in which different robust graphs are linearly connected to form common structure patterns by compressing and fusing the structure representations of each graphs. The learned common structure patterns are beneficial to TGNN to learn a more robust graph and we will show this in the next section.

heading: 3.3 PREDEFINED ROBUST GRAPHS
text: Here we briefly introduce three simple methods to generate robust graphs from adversarial graphs which will be adopted as predefined robust graphs by our proposed robust graph aggregation method:
• PRUNE: Adversarial graphs tend to add edges to unconnected nodes with dissimilar features (Wu et al., 2019b; Jin et al., 2020b). It is natural to prune the graph to get robust graph by eliminating edges that connect nodes with less similarity of features. Specifically, the pruned adjacency matrix can be represented by:
ArPRUNE(i, j) = { 1 if Ã(i, j) = 1 and s(xi,xj) > τ, 0 otherwise.
(5)
Here s(·, ·) denotes similarity function that calculates the feature similarity of two nodes (can be Jaccard similarity for binary features or cosine similarity for real-valued features), and τ is a threshold parameter.
• KNN: Since the edges are perturbed and we are not able fully determine which edge is perturbed, we can completely ignore the edge information and construct the graph only based on the node features. Similar to PRUNE, we can build robust graph by calculating the k-nearest neighbors based on feature similarities between nodes:
ArKNN (i, j) = { 1 if j ∈ top(i, k), 0 otherwise.
(6)
Here top(i, k) denotes set of the top k-th nodes that have large feature similarity to node i. • SVD: Existing works (Jin et al., 2020b; Entezari et al., 2020) found that adversarial perturbations
tend to add edges that connect nodes of different communities to fool GNNs, which enlarge the singular values of the adjacency matrix. Hence, with ui, σi, and vi to be the i-th singular value/vectors of Ã, we can generate robust graph by calculating low-rank approximations of the adjacency matrix:
ArSV D = Σ r i=1uiσivi. (7)
All the aforementioned methods are preprocessing methods that cost little time to run but still efficient to generate robust graphs to defend against adversarial edges. However, these methods are designed for single graph property so that they may fail to counteract complex global attacks. In Figure 2, we visualize the adjacency matrix of different predefined robust graphs and those learned by TGNN. As we can see from the figure, ArSV D preserve the graph with more graph spectral information that some of the perturbed edges are reduced, but a large number of original edges are also weakened.
ArKNN link the nodes with similar features, which contains many additional edges (green dots), and almost removes all the perturbed edges but also drops most of the original edges. For ArPRUNE , it eliminates some perturbed edges with low feature similarity but also a small number of original edges. For the robust graph Ā learned from TGNN, at the beginning of the training process, similar to ArSV D, the low-rank presentation makes the learned graph Ā pay more attention to spectral information, while gradually, it considers more about the feature similarities and reconstructs the input graph. Then during the training, the learned graph Ā is fuzzier and more edges that are not in the original input graph are added. Then at the rest of the training process, Ā is sparser and closer to the original graph. Compared with ArPRUNE , Ā drops more perturbed edges. In Figure 2, we also visualize the core tensor C1 defined in Eqn. (3) which reveals the relationship between the learned graph and the predefined graphs. Here we choose the rank as 32 so that C1 ∈ R32×4 and show the heatmap of values in C1. From the top to the bottom rows, the vectors are representing the weights for the learned graph Ā, ArKNN , A r SV D and A r PRUNE . Correlations are calculated by the cosine similarity between different weights, e.g., the correlation between Ā and ArKNN is calculated by the cosine similarity between C1(:, 1) and C1(:, 2). From the results, we can see that the correlation between Ā and ArSV D is initially high in the training process, degrades in the middle stage and grows back slightly at the end of the training. For ArKNN and A r PRUNE , the correlations are low at the beginning, then grow quickly during the training, and finally at a high level. These results also reveal how TGNN aggregates the predefined robust graphs and learn Ā.
Also, these predefined methods may suffer from the simple two-stage preprocessing without end-toend training. Combined with our proposed tensor-based robust graph aggregation method, we can aggregate the properties of these robust graphs and jointly learn the robust graph and the GNN. In Section 4.3, we will discuss the performance of our proposed TGNN compared with these predefined robust graphs for node classification performance. In Appendix A.6, we visualize the graph for nettack and random attack. In Appendix A.5, we compare the graph visualization between TGNN and a state-of-the-art method Pro-GNN.

heading: 4 EXPERIMENTS

heading: 4.1 EXPERIMENTAL SETTING
text: Datasets Following Zügner et al. (2018); Zügner & Günnemann (2019b); Jin et al. (2020b), we conduct experiment on four benchmark datasets,including three citation graphs, i.e., Cora (McCallum et al., 2000), Citeseer (Giles et al., 1998; Sen et al., 2008) and Pubmed (Sen et al., 2008), and one blog graph Polblogs (Adamic & Glance, 2005). We summarize the statistics of the datasets in Appendix A.2.
Baselines Following the adversarial attack repository DeepRobust (Li et al., 2020), we report the results of the state-of-the-art GNN and defense models for comparison. GCN (Kipf & Welling, 2017) and GAT (Velickovic et al., 2018) are adopted as baselines of GNNs, while RGCN (Zhu et al., 2019), GCN-Jaccard (Wu et al., 2019b), GCN-SVD (Entezari et al., 2020), Pro-GNN (Jin et al., 2020b), and GNNGuard (Zhang & Zitnik, 2020) are chosen as baselines of defense models. Please note that GCN-Jaccard and GCN-SVD are using the same approaches as PRUNE and SVD in Section 3.3. Specific description to these baselines can be found in Appendix A.3.
Parameter Settings For each graph, all nodes are randomly split into 10% of training nodes, 10% of validation nodes, and 80% of testing nodes. We report the average performance of ten runs for each experiment. The hyper-parameters of all the models are tuned by observing the loss and accuracy on validation set. We use Adam (Kingma & Ba, 2015) optimizer with learning rate as 0.01. λ is 100 in Eqn. (4). We use PyTorch (Paszke et al., 2019) (TensorLy (Kossaifi et al., 2019) for the tensor decomposition parts) to implement TGNN. We choose to use CP decomposition and the rank is selected based on cross validation. In Appendix A.7, we will discuss how different formats of tensor decomposition affect TGNN. All the results from the state-of-the-art methods are reported with the best parameter settings.

heading: 4.2 DEFENSE PERFORMANCE
text: To evaluate the effectiveness of TGNN, we conduct node classification experiments under three types of adversarial attacks, i.e., non-targeted attack, targeted attack and random attack. Targeted attack aims to fool GNNs with generated attacks on specific nodes, and we adopt the state-of-the-art targeted attack nettack (Zügner et al., 2018) in this paper. Different from targeted attack, non-targeted attack can degrade the overall performance of GNNs on the whole graph and we choose metattack (Zügner
& Günnemann, 2019b) for the non-targeted attack evaluation. Random attack randomly adds noise to the original graph by injecting fake edges into the graph.
Against Non-Targeted Adversarial Attacks: Firstly, we evaluate the node classification performance of different methods against non-targeted adversarial attack. We adopt metattack Zügner & Günnemann (2019b) and implement it with its default parameter settings in original paper. We apply the most destructive attack variant of metattack, Meta-Self, to Cora, Citeseer and Polblogs. For Pubmed, A-Meta-Self as the approximate version of 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%. The average accuracy with standard deviation is reported in Table 1, in which the best performance is highlighted in bold. From the table, we can see that TGNN achieves the highest node classification accuracy under different perturbation rates, which demonstrates that TGNN can generate robust graph against non-targeted adversarial attack. For instance, TGNN improves GCN over 20.7% at 5% perturbation rate on Polblogs. Under the 25% perturbation rate, vanilla GCN performs very poorly and TGNN improves GCN by 27% (resp., 16%, 23% and 11%) on the dataset Cora (resp., Citeseer, Polblogs, and Pubmed), which indicates TGNN outperforms other baselines by a larger margin even under large perturbation. In addition, TGNN may also perform better when the graph is not attacked (i.e., perturbation rate is 0). That is because there may be a small amount of noise edges in the original graph which are mitigated by TGNN. For the other defense methods, although GCN-SVD also employs SVD to get low-rank approximation of the graph, the performance of GCN-SVD drops rapidly. Similarly, GCN-Jaccard does not perform as well as Pro-GNN under different perturbation rates. This is because simply pruning the perturbed graph by feature similarities once cannot extract the robust graph from the carefully-crafted adversarial noises. TGNN also outperforms Pro-GNN that applies regularization based on low-rank, sparse and feature similarity properties to learn robust graph, which shows the regularization is not able to perfectly balance different graph properties to enhance robustness. On the contrary, TGNN adopts tensor-based aggregation method to update the graph and GNNs simultaneously to learn better graph and more robust GNNs.
Against Targeted Adversarial Attack: For the targeted-attack method nettack (Zügner et al., 2018), we use the default parameter settings in the original implementation. Following Zhu et al. (2019), the number of perturbations added on every targeted node is varied from 1 to 5 with a step size of 1. Nodes with degree larger than 10 as target nodes are selected as the test set. 10% of target nodes are sampled on Pubmed dataset to save running time, while all the target nodes are used on other datasets. The node classification accuracy on target nodes is shown in Figure 3 (a)-(d), in which we can observe that TGNN achieves better performance than other baselines with the increase of the number of perturbation in most cases. For instance, at 5 perturbation per targeted node, TGNN improves vanilla GCN by 16% (resp., 29%, 6%, 6%) on Cora (resp., Citeseer, Polblogs, Pubmed) dataset. It demonstrates that TGNN can also resist the targeted adversarial attack.
Against Random Attack: By varying the ratios of random noises from 0% to 100% with a step size of 20%, we compare the performance of TGNN with baselines and state-of-the-art methods. Node classification accuracy results are reported in Figure 3 (e)-(h). It can be observed that TGNN is able to resist random attack and outperforms all other baselines under random attack.

heading: 4.3 ABLATION STUDIES
text: We design different ablated methods to demonstrate the effectiveness of TGNN defending against metattack attack and report classification performance on Cora (McCallum et al., 2000) dataset in Table 2, in which our full method is named as “TGNN-ALL”. Please note that the setting “No A” means running GCN without graph information, i.e., remove Â in Eqn. (2). We list it here as a reference. Both “No A” and “KNN” are not using the graph, which means their results are unchanged with the perturbation rate, so we omit the results and put them in the caption of Table 2. We also put the baseline results of “GCN” for the sake of comparison.
Variations of Predefined Robust Graphs: Firstly we report the results of three predefined adversarial graphs in Section 3.3, which are referred to as “PRUNE”, “KNN”, and “SVD” in Table 2. Then, we use TGNN to aggregate a predefined adversarial graph “PRUNE” (resp., “KNN”, “SVD”), which is referred to as “TGNN-P” (resp., TGNN-K, TGNN-S). From the comparison result between “PRUNE” (resp., “SVD”) and “TGNN-P” (resp., “TGNN-S”), we can see that each predefined adversarial graph with the help of our TGNN can consistently improve classification performance. We also remove all predefined adversarial graphs from our method, which is named as “TGNN-N” in Table 2. We find that the performance is comparable with predefined adversarial graphs “PRUNE” and “SVD”, which demonstrates the rationality of TGNN.
Compared to Ensembles: To evaluate the effectiveness of the tensor decomposition in TGNN, we simply ensemble predefined adversarial graphs, which is referred to as “Ensemble”, the result is better than “PRUNE” and “SVD”, which indicates that assembling predefined adversarial graphs by learning a GNN for each one and summing them up is one way to improve the robustness of GNNs. However, the performance is worse than our full method “TGNN-ALL”, which demonstrates the effectiveness of the designed aggregation strategy of TGNN.
End-to-End Training: Corroborate the superiority of end-to-end training strategy, we design a two-stage variant of TGNN where the robust graph is firstly obtained, and then using it to train a GNN, which is recorded as “Two-Stage” in Table 2. It can be seen that the performance is worse than our full method “TGNN-ALL”, which demonstrates the advantage of the jointly learning strategy.

heading: 5 CONCLUSION
text: In this paper, we introduce TGNN, a framework for defending GNN against poisoning attacks. TGNN combines predefined robust graph structures and formulates them with the adversarial graph structure as a graph structure tensor, then applies low-rank tensor approximation to generate a more robust graph structure. The low-rank representation of the robust graph structures preserve the common patterns of robust structures, balance different graph properties, and enhance the robustness of the generated graph structure. Experiments on four datasets show that TGNN outperforms existing GNN defense algorithms, especially when the perturbation rate is high.

heading: 6 ETHICS STATEMENT
text: TGNN is a framework for defending GNN against poisoning attacks, combining predefined robust graphs and the adversarial graph as a graph tensor, then applying low-rank tensor approximation to generate a more robust graph. We have shown that TGNN outperforms existing GNN defense methods, especially when the perturbation rate is high. TGNN can be used in a wide range of applications integrated with GNNs, e.g., recommendation system, drug discovery, and social/financial networks. Positive impacts of TGNN include helping users avoid potential losses caused by malicious attacks, predict false diagnoses for knowledge systems, and improve fairness and explainability of GNNs. One potentially negative impact is to design a more powerful attacking algorithm based on TGNN. TGNN aggregates predefined robust graph methods, we have shown that TGNN can always improve the classification accuracy based on the provided predefined methods. Hence, attackers may develop more powerful attacking algorithms based on TGNN (i.e., adaptive attacks).
In this paper, all the datasets are downloaded from public academic resources (please refer to Appendix A.2).

heading: 7 REPRODUCIBILITY STATEMENT
text: We provide the source code in the supplementary materials to reproduce the results. We also provide extensive analyses for the settings and hyperparameters of TGNN, which can be found in Appendix.

heading: A APPENDIX
text: In this section, we provide more details of our experiments settings, visualization of TGNN compared with state-of-the-art methods, visualization of TGNN under other types of attacks, analyses of tensor decomposition formations and ranks, and hyperparameter effects. We also provide the code and data in the supplementary materials for reproducing the results we reported.

heading: A.1 FURTHER IMPLEMENTATION DETAILS
text: We use PyTorch Paszke et al. (2019) (BSD Style License) to implement TGNN and TensorLy Kossaifi et al. (2019) (BSD 3-Clause License) for the tensor decomposition parts. For each graph, all nodes are randomly split into 10% of training nodes, 10% of validation nodes, and 80% of testing nodes. The best learned robust graph and GNN parameters are chosen based on the validation set for each graph. All the results are averaged based on 10 runs. We are using two different Adam Kingma & Ba (2015) optimizers for learning GNNs and the tensor cores in Eqn. (3, 4). The learning rate is 0.01. The weight decay for learning tensor cores and GNNs are 0.3 and 0. ReLU activation is applied after the first layer of the GCN. We train TGNN with 1000 epochs for each graph.
The goal of TGNN is to learn low-rank aggregation of the robust graphs, and the decomposition of TGNN is learned end-to-end. The diagnose is objective-oriented, which means to be based on the validation performance. We are focusing on the semi-supervised task of node classification that for each graph, so all the models are selected based on the best validation performance (accuracy). We found that the results for validation sets and the results for test sets show similar trends for different hyper-parameters.
The experiments are run on NVidia Tesla V100 GPU, Intel(R) Xeon(R) Silver 4116 CPU 2.10GHz, 192G RAM. It takes 83 seconds to train the full-fledged TGNN (GCN takes 39 seconds on the same device) which is estimated to emit 3.92g CO2 (estimators were conducted in ML CO2 impact calculator Lacoste et al. (2019)).
We analyze different hyperparameters and settings for TGNN on Cora dataset in Section A.7, A.8 and A.9. For the full implementation details, please refer to the code provided with supplementary material.

heading: A.2 DATASETS STATISTICS
text: Following Zügner et al. (2018); Zügner & Günnemann (2019b); Jin et al. (2020b), we conduct experiments on four public benchmark datasets, including three citation graphs, i.e., Cora McCallum et al. (2000), Citeseer Giles et al. (1998); Sen et al. (2008) and Pubmed Sen et al. (2008), and one blog graph Polblogs Adamic & Glance (2005). We were unable to find the license for the datasets we used. All the data (including perturbed graphs) was downloaded from DeepRobust Li et al. (2020) (an open library for attack and defense methods on images and graphs, with MIT License) and attached in the supplementary material. Note that we set the attribute matrix to N ×N identity matrix and use the adjacency matrix to compute node similarities in the Polblogs graph since node features in this dataset are not available. Further detailed statistics of the four chosen datasets are summarized In Table 3. For predefined methods PRUNE and KNN, we use jaccard similarity for Cora, Citeseer and Polblogs, and cosine similarity for Pubmed.

heading: A.3 BASELINE SETTINGS
text: • GCN (Kipf & Welling, 2017): Among a number of different Graph Convolutional Networks (GCN) models, we choose the most popular one Kipf & Welling (2017) as a baseline and the default parameter setting in the official implementation is adopted.
• GAT (Velickovic et al., 2018): Graph Attention Network (GAT) leverages attention layers to learn different weights for different nodes in the neighborhood. GAT is often used as a baseline Jin et al. (2020b); Zhang & Zitnik (2020) to defend against adversarial attacks. Similar to GCN, the default parameter setting in the official implementation is adopted for GAT.
• RGCN (Zhu et al., 2019): For RGCN models, Gaussian distributions are applied to model node representations for mitigating effects of adversarial attacks. The nodes with high variance are penalized by the attention mechanism. For RGCN, the number of hidden units are tuned from {16, 32, 64, 128} and the best choice is selected for each dataset.
• GCN-Jaccard (Wu et al., 2019b): GCN-Jaccard is a preprocessing method that eliminates edges connecting nodes with feature similarities less than a given threshold. This is the same approach to PRUNE described in Section 3.3. Jaccard similarity is used for datasets with binary feature type, while for continuous features cosine similarity is adopted. For Polblogs dataset where adjacency matrix is used as node feature, we are also using jaccard similarity. The threshold of similarity for pruning dissimilar edges are chosen from {0.01, 0.02, 0.03, 0.04, 0.05, 0.1}.
• GCN-SVD (Entezari et al., 2020): GCN-SVD preprocesses the network by vaccinating GCN with the low-rank approximation (implemented by SVD decomposition) of the perturbed graph. This is the exact approach to SVD described in Section 3.3. The rank of GCN-SVD is selected from {5, 10, 15, 50, 100, 200}.
• Pro-GNN (Jin et al., 2020b): Pro-GNN is a method that regularizes learned robust graph with three different graph properties: sparse, low-rank and feature smoothing. There are two settings (one with feature smoothing and one without) reported in the original paper. In Table 1, the numbers of these two settings are merged with the best results.
• GNNGuard (Zhang & Zitnik, 2020): GNN-Guard quantifies the relationship between the graph and node features by assigning less weights to suspicious edges to absorb malicious edges. We re-run the officially released code of GNN-Guard under ours setting and the results are reported in Table 1.

heading: A.4 COMPLEXITY ANALYSES
text: Following the notation in Section 3, we use N /M to represent the number of nodes/edges. We will report the complexity of all the mentioned attack methods and defend methods. The time and space complexity are the same for most reported methods.
Let’s first look at the complexity of attack methods.
• Random: O(M × Perturbation Rate) • Nettack: O(|Target Nodes| ×N) • Metattack: O(N2)
Metattack (Zügner & Günnemann, 2019b) and Nettack (Zügner et al., 2018) are considering both deleting existing edges and wiring the node pairs in the graph. Metattack is a global poisoning attack method and is much more powerful than Nettack or Random attack.
• Defend methods in O(M) complexity: RGCN, Jaccard, GNNGuard • Defend methods in O(N2) complexity: SVD, KNN, Pro-GNN, TGNN
The exact time/space complexity of TGNN is O((NK +N2)Rd)/O((N +K)R+N2), where R is the rank, andK is the number of predefined graphs. The number of feature/embedding dimensionality d, rank R, and the number of predefined graphs K are relatively low-dimensional compared to N or M . The complexity of TGNN is in the same order as that of Metattack.
Please note we are doing truncated SVD for the SVD method, which only needs the top-k singular values/vectors for the adjacency matrix. The name SVD is only used to differ from PRUNE and
KNN. We are doing Truncated SVD via scipy.sparse.linalg.svds. We adopt the default option from scipy, which uses ARPACK (Lehoucq et al., 1998). Computing SVD of a matrix is done by eigendecomposition of a square symmetric matrix. ARPACK is an iterative algorithm used to quickly find a few eigenvalues/eigenvectors of large sparse matrices. The complexity of calculating truncated SVD by ARPACK is O(kN2). There is another work (Halko et al., 2011) pointing out that with randomized techniques, finding the k dominant components of the SVD is of O(log(k)N2). Since k is relatively minor to N , the predefined SVD algorithm has the complexity of the order O(N2).
It also should be noted that the complexity of KNN (All-k-Nearest-Neighbors Problem) is proved to be of the order O(NlogN) (Ma & Li, 2019). Here we store the dense representation of the KNN map, so the space complexity of KNN is O(N2).
For the proposed TGNN, we first apply random initialization to the core tensors, then apply the alternating least squares (ALS) approach for 100 iterations. After that, the core tensors are learned endto-end with the whole model. Since how to learn tensor decomposition is not the main contribution of this submission, and we are using the code from TensorLy (Kossaifi et al., 2019) to produce the core tensors, we omit the detail of tensor decompositions. For CP decomposition as an example, the ALS approach chooses one core tensor and fixes the other tensors to solve the chosen core tensor. Since each core tensor represents a specific mode, the process of solving the chosen core tensor can be solved by matrix least square approximation. The approach is proposed in Harshman et al. (1970) and Carroll & Chang (1970), while detailed numerical complexity analyses can be found in Comon et al. (2009). Overall, each iteration for ALS and end-to-end core tensor training is of the order O(N2) complexity.
Intuitively, when the graph is severely perturbed, it is necessary to check each node pair from the global view in the graph to verify whether the edge is removed or added. Methods with O(M) complexity only consider the edges that appear in the perturbed graph. They are not considering rewiring the edges deleted by the attack methods, which implies they are not able to defend against attacks that remove existing edges. As shown in Table 1 and Figure 3, TGNN outperforms all the methods with O(M) complexity. Hence, we argue that O(N2) is a more reasonable complexity level than O(M) to effectively defend the poisoning attack methods. When compared to the methods with the same level of O(N2) computational complexity, Pro-GNN and SVD, TGNN performs substantially better. TGNN takes 83s to be trained on Cora while GCN takes 39s , GNNGuard takes 94s and Pro-GNN takes 890s on the same machine. TGNN does not consume too much extra time to run.

heading: A.5 COMPARISON BETWEEN TGNN AND PRO-GNN
text: Like TGNN, Pro-GNN Jin et al. (2020b) is also a method that defends adversarial attacks combining different graph properties (sparse, low-rank and feature smoothing). Different from TGNN that balances different graph properties with tensor-based aggregation, Pro-GNN regularizes learned robust graph with objective functions directly satisfying these graph properties, which may cause imbalance among the properties and the original graph information. In Figure 4, we visualize the learned adjacency matrix from TGNN and Pro-GNN. The input graph is the same as that in Figure 2, which is from Cora dataset and attacked by metattack with 25% perturbation rate.
As we can see in the figure, when the attack is severe, Pro-GNN is apt to learn robust graph by overfitting strong sparse and low-rank property with many original edges removed, which is harmful because the original edges are useful for GNNs to provide robust classification performance. The learned robust graph from TGNN covers most of the original edges but is also sparse and with low-rank structure. For the point of view from each edge entry, the edge weight satisfies every graph properties. But looking from the whole graph, the original graph structure is destroyed. Combined with the quantitative results in Table 1, TGNN balances different graph properties and the original graph information better, and outperforms Pro-GNN when the perturbation is severe.
A.6 VISUALIZATION OF TGNN AGAINST NETTACK AND RANDOM ATTACK
In Figure 2, we visualize the learned graph from TGNN and predefined methods to show how TGNN aggregate and learn robust graphs. Here we also visualize the results for the other two types of
adversarial attacks: nettack Zügner et al. (2018) and random attack in Figure 5 and Figure 6. Similar to Figure 2, the graphs in Figure 5 and Figure 6 are also perturbed in the most severe situation.
In Figure 5, we can see that nettack perturbs the graph with fewer edges compared with metattack, which is due to the targeted attacking mechanism. ArSV D and A r KNN ignore too much information from the original graph. TGNN generates robust graph similar to the one from ArPRUNE while still pays attention to spectral structures.
While for random attack, more adversarial edges are added so that ArPRUNE is not able to remove most of the perturbed edges. In this situation, TGNN generates robust graph which is more likely to the one from ArSV D, while still keeps the low-rank structure of the perturbed graph, but with less weights for the perturbed edges.

heading: A.7 ANALYSES FOR TENSOR DECOMPOSITION METHODS AND RANKS
text: In this section, we compare different tensor decomposition methods for TGNN and discuss how different choices of tensor decomposition methods and ranks affect TGNN performance. In Figure 7, we illustrate the formation of different tensor decomposition method.
CP Decomposition (Harshman et al., 1970; Carroll & Chang, 1970): The formation of CP decomposition can be found in Eqn. (3). Here we rewrite the equation into element-wise formation:
T̄ (i, j, k) = R∑ r=1 C0(r)C1(r, i)C2(r, j)C3(r, k), (8)
where C1 ∈ RR×(K+1), C2 ∈ RR×N , C3 ∈ RR×N and C0 ∈ RR. There are R × (2N + K + 2) parameters in total. We select rank R from {8, 16, 32, 64, 128} and plot the corresponding classification performance in Figure 8. All the results are on Cora dataset with metattack perturbations, which are under the same setting of Table 2 “TGNN-ALL”.
We can see from the figure that when R is too small (i.e., R = 8), the low-rank property is too strong that the learned graph is not able to obtain enough information for GNNs for accurate classification. For R ≥ 16, when R goes larger, performance for graphs with low perturbation rates is better, which means the low-rank property is not strong and the learned robust graph can reconstruct the original
graph well. But this may degrade the robustness of GNNs when the graph is heavily perturbed. Among all the choices of rank, we find that R = 32 is the best considering all the perturbation rates.
Tucker Decomposition (Tucker, 1966): Similar to CP decomposition, Tucker decomposition can be formulated as:
T̄ (i, j, k) = ∑
t1,t2,t3
C0(t1, t2, t3)C1(i, t1)C2(j, t2)C3(k, t3), (9)
where C1 ∈ R(K+1)×(K+1), C2 ∈ RR×N , C3 ∈ RR×N and C0 ∈ R(K+1)×R×R. There are R× (R× (K + 1) + 2N) + (K + 1)× (K + 1) parameters in total.
In Figure 9, we also plot the classification performance for different ranks of Tucker decomposition. Similar to CP decomposition, R = 32 is also the best choice considering all the perturbation rates.
Tensor-Train (TT) (Oseledets, 2011) Decomposition: TT decomposition can be formulated as:
T̄ (i, j, k) = ∑ t1,t2 C1(i, t1)C2(t1, j, t2)C3(t2, k), (10)
where C1 ∈ R(K+1)×(K+1), C2 ∈ R(K+1)×N×R, C3 ∈ RR×N . There are R× (N × (K + 1) +N) + (K + 1)× (K + 1) parameters in total.
In Figure 10, we plot the classification performance for different ranks of TT decomposition that R = 32 is the best choice considering all the perturbation rates. Please note there is another way to apply TT decomposition by swapping the first two modes of T̄ . We omit this formation in this paper because it is very similar to the formation of Tucker decomposition.
Comparing Different Tensor Decomposition Methods: Combining all the tensor decomposition methods, we find that CP decomposition , which costs the less amount of parameters under the same rank, is the best one for TGNN. Here we plot the results of CP, Tucker and TT decomposition when R = 32.
Please note it may be unfair to compare different decomposition methods with the same rank because the meanings of rank for these decomposition methods are different. We show the results to provide evidence for why we are using CP decomposition for our implementation.

heading: A.8 ANALYSES FOR HYPERPARAMETERS IN PREDEFINED METHODS
text: In this section, we analyze how hyperparameters affect the predefined methods and TGNN performance.
SVD: To investigate the impact of rank r in Eqn.(7) for SVD, we select rank r from {5, 10, 15, 50, 100, 200} to conduct experiments with the setting of “SVD” and “TGNN-S” in Table 2. The results can be found in Figure 12.
For the predefined method “SVD” shown in Figure 12 (a) , the results are not promising when rank r is too small, which means the low-rank property is too strong for the method to carry enough information of the graph. When r grows, performance for the graphs with low perturbation rates becomes better, while the performance of the graphs with high perturbation rates is poorer. Similarly, in Figure 12 (b), “TGNN-S” also has this phenomenon but always performs better than “SVD” with the same ranks. We also plot the comparison results of “SVD” and “TGNN-S” with rank {5, 50, 200} in Figure 12 (c) in which the gap between these two methods demonstrates the effectiveness of TGNN.
PRUNE: We tune the threshold τ in Eqn.(5) from {0.01, 0.02, 0.03, 0.04, 0.05, 0.1} for “PRUNE” and “TGNN-P” in Table 2, the corresponding results are summarized in Figure 13. Please note the results for τ = 0.01 and τ = 0.02 are too close due to the node feature similarity distribution (i.e., few node similarities are in the range of [0.01, 0.02]), so we omit the results for τ = 0.02 in this figure.
For the predefined method “PRUNE” in Figure 13 (a) , when τ grows, more edges (can be both perturbed edges and the original edges) are pruned, resulting in the poorer performance of the graphs with low perturbation rates, while the graphs with high perturbation rates achieve better results. Comparing Figure 13 (a) and Figure 13 (b), it can be seen that “TGNN-P” always performs better than “PRUNE” under the same perturbation rate. From the comparison results of “PRUNE” and “TGNN-P” with thresholds {0.01, 0.04, 0.1} in Figure 13 (c), the gap between these two methods also demonstrates the effectiveness of aggregation strategy in TGNN.
KNN: The k in Eqn.(6) is chosen from {8, 16, 32, 64, 128}. We plot the results for “KNN” and “TGNN-K” in Table 2 and the results can be found in Figure 14. Since the results for “KNN” are not changing with perturbation rates, we plot them with horizontal lines in this figure. The results for “KNN” and “TGNN-K” with the same k are in the same color.
From the figure, we can see that “TGNN-K” always outperform predefined method “KNN”.

heading: A.9 ANALYSES FOR OTHER HYPERPARAMETERS
text: In this section, we analyze the other hyperparameters used in the proposed TGNN method, including λ in Eqn. (4) and the weight decay for learning tensor cores.
λ in Eqn. (4): The λ in Eqn. (4) is a hyperparameter balancing the classification loss and the low-rank approximation loss. Here we choose different λ from {1, 10, 100, 1000, 10000} to verify
the performance of TGNN. The results are still from Cora dataset attacked with metattack and depicted in Figure 15. Please note the results for λ = 1000 and λ = 10000 are very close hence we omit the results for λ = 10000.
From the figure, we can see that λ = 100 is the best choice for TGNN to perform robustly against adversarial attacks.
Weight Decay for Learning Tensor Cores: In our TGNN, optimizer with weight decay 0.3 is adopted to learn the core tensors. To investigate the effects of weight decay, we choose it from {0, 0.01, 0.03, 0.1, 0.3, 1} to tune TGNN and report the results in Figure 16.
From the results, we can see that weight decay has minor effects on the performance of TGNN.

heading: A.10 LIMITATIONS
text: One of the limitations for TGNN is scalability. All the existing methods use the same choice of datasets or others with similar scales. There are no existing defense methods evaluated on datasets on a scale of about or above 100000 nodes. It is also tough to evaluate attack methods like Metattack and Nettack on that scale because attack methods can wire any of the N2 −M edges not included in the graph, where N denotes the number of nodes and M denotes the number of edges. We argue that O(N2) is more reasonable than O(M) for defense methods when considering to rewire the potential N2 −M deleted edges by the attacks. Our method has the same scalability as two competing methods (GCN-SVD and Pro-GNN), and is reasonable compared to the other three methods (GNNGuard, GCN-Jaccard and RGCN), while our method can beat all competing methods in terms of robustness to different attacks.
Here, we provide a potential solution for TGNN to handle large-scale graphs. The core idea is not to calculate the whole adjacency matrix explicitly. Sampling based algorithms have been used previously for scalable tensor decomposition (Larsen & Kolda, 2020; Cheng et al., 2016; Bhojanapalli & Sanghavi, 2015). In Cheng et al. (2016), statistical leverage scores (i.e., sampling weights or
importance) are adaptively estimated by exploiting the tensor/matrix product structure of the designed tensors in least square problems. We can utilize this technique to reduce the complexity of the tensor approximation process of TGNN to O(NR3) for each iteration by reducing the size of least square problems in ALS. As we have analyzed in Section A.4, ignoring SVD and without explicitly constructing the whole predefined matrices, the complexity for KNN and PRUNE are O(NlogN) andO(M) respectively. We can also approximate the normalized graph Â directly to avoid estimating the diagonal degree matrix. Hence, the complexity of tensor approximation (calculating the core tensors) can be reduced to the order O(M + NlogN). With the calculated core tensors, we can replace the calculation of each GCN layer in Eqn 2 by:
fθk(X,C0,C1,C2,C3) = R∑ r=1 C0(r)C1(r, 1)C2(r, :) T (C3(r, :)XWk) . (11)
Since C1 ∈ RR×(K+1), C2 ∈ RR×N , C3 ∈ RR×N and C0 ∈ RR, the computational complexity of each GCN layer in the above equation is of the order O(NRD). Overall, ignoring the minor terms R and D, the complexity for this whole alternative algorithm is O(M +NlogN).
Attack/defense algorithms for GNNs with high scalability would be interesting, and we will consider designing them and learn how they perform with TGNN as future works.

heading: A.11 TRANSFERABILITY OF THE LEARNED ROBUST GRAPH Ā
text: In this section, we evaluate the transferability of the learned robust graph Ā from TGNN. A robust graph is transferable if it can consistently defend different GNN models effectively. Since TGNN is trained with GCN, we evaluate the performance of Ā transferring to GAT and another state-of-the-art GNN: APPNP (Klicpera et al., 2019). Evaluation is based on Metattack on Cora dataset and the results are in Figure 17.
From Figure 17, we can see that APPNP also suffers from adversarial attacks (accuracy on clean graph: 84.80%, under 25% perturbation rate: 53.42%). Suppose we replace the perturbed graph Ã with the robust graph Ā learned from TGNN by GCN for GAT and APPNP. In that case, we can significantly improve the classification performance for GAT and APPNP (under 25% perturbation rate, GAT: from 54.78% to 71.23%, APPNP: from 53.42% to 76.16%), which proves that the learned robust graph from TGNN can be transferred to different GNNs.

heading: A.12 RESULTS AGAINST ATTACKS WITH FEATURES
text: In this section, we conduct experiments to verify whether TGNN is able to defend GNNs against adversarial attacks perturbing both structure and feature. We apply Metattack on Cora datasets changing both adjacency matrix and feature maps and evaluate state-of-the-art methods and the proposed TGNN. The feature matrix in Cora dataset is binary, so the attacks for feature can be applied in the same way as for structure. There are two different settings for this combined attacks: the first one is called Combined, following Zügner & Günnemann (2019b) that the attacks for feature matrix X and adjacency matrix A share the same budget (a.k.a., maximum number of perturbations)
∆, i.e., ||A− Ã||0 + ||X− X̃||0 ≤ ∆; the second setting is called Separate that the attacks for X and A have their own budget that ||A − Ã||0 ≤ ∆A and ||X − X̃||0 ≤ ∆X . For Combined, we use the same perturbation rates as used for structure-only attacks in Table 1, where ∆ = p× ||A||0 and p ∈ {5%, 10%, 15%, 20%, 25%}. For Separate, the same set of perturbation rates are applied separately for feature and structure respectively that ∆X = p× ||X||0 and ∆A = p× ||A||0. The results are shown in Figure 18.
Under Combined setting, TGNN outperforms all the other methods, and it can also be observed that the impact of features for Metattack is slightly lower than the structures to GNNs (under 25% perturbation rate comparing TGNN and the best sota method, structure-only attack: TGNN 74.14% vs Pro-GNN 69.72%, Combined: TGNN 77.73% vs Pro-GNN 70.85%). In Zügner & Günnemann (2019b), similar observations are shown. We attribute this to two reasons: (1) Unbalanced density between feature matrix and adjacency matrix: The budgets assigned for feature and structure are the same for Combined; however, the density of feature and structure might be imbalanced. The average value of A for Cora is 0.0016, while the average value of the X is 0.0128. The adjacency matrix is sparser than the feature matrix, so it may cost more perturbations for attacking features to achieve the same degradation level as the attacks for structures. (2) Structure and feature have different roles in GCN: Based on the formulation of GCN (Eqn. (2), fθ(X,A) = softmax(fθ2(fθ1(X,A),A))), the feature matrix X is only used in the first layer, while the adjacency matrix A appears in every layer. This can make it easier to perturb A than X for degrading the performance of GCN.
Under Separate setting, TGNN still outperforms all the other methods (under 25% perturbation rate comparing TGNN and the best sota method, TGNN 73.30% vs GCN-Jaccard 59.74%). The results show that TGNN is also robust against attacks with features. It might be a concern that attacks for features can mislead KNN and fool TGNN easily. However, KNN performs very consistently: only 362 out of 39720 entries (less than 1%) are changed for KNN predefined graph from the clean graph data to 25% perturbation rate under Separate setting.
We find that features are very robust to adversarial perturbation for GNNs. We think it is because of the different roles of feature and structure in GCN, as we have mentioned before. But unfortunately, if we only use features to classify the nodes, the performance is very poor (on clean graph, “No A” in Table 2: 62.12%, KNN: 71.94%, GCN: 83.50%). How to effectively attack GNNs with features would be a very interesting topic, and we will address it in future works.

heading: A.13 RESULTS ON AMAZON DATASET
text: We add an experiment to show the effectiveness of TGNN defending GNNs on product co-purchase graphs. Amazon (Shchur et al., 2018) dataset is based on the Amazon co-purchase graph, where nodes represent goods, edges indicate that two goods are frequently bought together, node features are bag-of-words encoded product reviews, and class labels are given by the product category. It contains
two sub-datasets: Computers which contains 13752 nodes, 491722 edges, 767 binary features and 10 classes; and Photos which contains 7650 nodes, 238162 edges, 745 binary features and 8 classes.
We evaluate TGNN and the state-of-the-art methods mentioned in Table 1 on Computers/Photos dataset against Metattack. The results can be found in Figure 19. We can see from the results that TGNN is the best method defending GNNs on product co-purchase graphs (under 25% perturbation rate comparing TGNN and the best sota method, Computers: TGNN 75.44% vs GCN-SVD 72.31%, Photos: TGNN 80.87% vs GAT 76.81%).

heading: A.14 RESULTS AGAINST EVASION ATTACKS
text: In this section, we evaluate the proposed TGNN on another type of attacks: evasion attacks. Evasion attacks are also called as test-time attacks. Victim models are trained with clean data and tested with perturbed data. The goal of defending evasion attacks can be formally stated as:
Given fixed GNN parameters θ trained with the unperturbed adjacency matrix A, feature X and partial node labels YP , the GNN is evaluated with adversarial graph Ã. We aim to learn robust graph Ā replacing Ã to improve node classification performance for unlabeled nodes.
We mentioned that we are focusing on poisoning attacks in this work, and we argue that poisoning attacks for node classification are more reasonable due to the semi-supervised setting. Poisoning attacks are train-time attacks that perturb the graph data before the training process of the victim models. For reasons why the poisoning attack is more interesting and realistic in GNN, on the one hand, in evasion attack settings, GNN models are trained on the clean graph and evaluated on the perturbed graph generated by evasion attack methods. The graph information can be memorized by GNN models during the training process and be utilized to test to defend against evasion attacks. On the other hand, GNN models require the entire graph to classify every node, which means evasion
attacks provide the entire perturbed graph in the testing phase. Based on the given entire graph, we are able to retrain GNN models to defend against evasion attacks. Hence, poisoning attacks are more realistic than evasion attacks. In (Zügner et al., 2018), similar argumentation is made.
We choose two evasion attacks: PGD and Min-Max, proposed in Xu et al. (2019) to evaluate all the defense methods. The defense performance results of TGNN and state-of-the-art methods can be found in Figure 20. For GCN-Jaccard, GCN-SVD, Pro-GNN and TGNN, the surrogate GCN is firstly trained with clean graph. During the test-time, the surrogate GCN is fixed and used to learn the robust graph. From Figure 20, we can see that TGNN also shows more promising performance against evasion attacks than all state-of-the-art methods (under 25% perturbation rate comparing TGNN and the best sota method, PGD: TGNN 75.35% vs GCN-Jaccard 74.33%, Min-Max: TGNN 79.88% vs Pro-GNN 77.67%).

Review summaries:
The paper presents a tensor-based framework to improve robustness of GNNs by denoising the adversarial graphs. By leveraging the low-rank and feature similarity properties of graph data, the authors use three predefined robust graphs with the adversarial graph to form a graph tensor, and then apply tensor decomposition methods to learn a robust graph. The experimental results show that the framework outperforms baselines under different adversarial attacks. 

The paper proposes a tensor-based defense strategy against adversarial perturbations to graph neural networks. Specifically, the authors propose to aggregate several "robust" adjacency matrices obtained from previously proposed methods into a tensor, which is then decomposed. Based on this decomposition, we can then obtain a new robust graph, with the idea of combining the strengths of the different robust approaches.

This paper studies the problem of defending against adversarial attacks for graph neural networks. It first defines some robust adversarial graphs and aggregates the predefined graphs to form a powerful regularization. Then low-rank tensor approximation is applied to generate a more robust graph structure while jointly learning the GNN parameters. graph structure. Extensive experiments demonstrated the effectiveness of the proposed method.