Unveiling Adversarially Robust Graph Lottery Tickets
Authors: Subhajit Dutta Chowdhury
Zhiyu Ni
Qingyuan Peng
Souvik Kundu
Pierluigi Nuzzo
Venue: Accepted by TMLR ()

Abstract: Graph lottery tickets (GLTs), comprising a sparse graph neural network (GNN) and a sparse input graph adjacency matrix, can significantly reduce the computing footprint of inference tasks compared to their dense counterparts. However, their performance against adversarial attacks remains to be fully explored. In this paper, we first investigate the resilience of GLTs against different {poisoning attacks based on structure perturbations} and observe that they are vulnerable and show a large drop in classification accuracy. We then present an \emph{adversarially robust graph sparsification (ARGS)} framework that prunes the adjacency matrix and the GNN weights by minimizing a novel loss function capturing the graph homophily property and information associated with the true labels of the train nodes and the pseudo labels of the test nodes. By iteratively applying ARGS to prune both the perturbed graph adjacency matrix and the GNN model weights, we can find graph lottery tickets that are highly sparse yet achieve competitive performance under different training-time (poisoning) structure-perturbation attacks. Evaluations conducted on various benchmarks, considering {attacks} such as PGD, MetaAttack, PR-BCD, GR-BCD, and adaptive attack, demonstrate that ARGS can significantly improve the robustness of the generated  GLTs, even when subjected to high levels of sparsity.

Published in Transactions on Machine Learning Research (September/202) 2204)
Unveiling Adversarially Robust Graph Lottery Tickets
Subhajit Dutta Chowdhury'
Multacho@uusc.oo
Deportment of Electricol and Computer Engineering University of Southern California, Los Angeles
Zhiyu NI
shiyuni@usc.co edu
Department Electricol and Computer Engineering University of Southern California, Los Angeles
Qingyuan Peng
pengging@usc.ect
Deportment of Electricol and Computer Engineering University of Southern California, Los Angeles
Souvik Kundu
sowvikkuuusc.. edu
Intel Labs, Sun Diego
Pierluigi Nuzzo
muzzodeecs. Buezoooeess.erreeeee... berkeley. edu
Deportment of Electrical Engineering and Computer Sciences, University of California, Berkeley Department of Electrical and Computer Engineering, University of Southern Californéa, Angeles
Reviewed on OpenReview: https: openreview. net/ forum? id= PX06pUVs11
Abstract
Graph lottery lickets (GLTs), comprising a sparse graph neural network (GNN) and a sparse input graph adjacency matrix, can significantly reduce the computing footprint. of inference tasks compared to their dense counterparts. However, their performance against adversarial attacks remains to be fully explored. In this paper, we first investigate the resilience of GLTs against different poisoning attacks based structure perturbations and observe that they are vulnerable and show large drop in classification accuracy. We then present adversarially robust graph sparsification (ARGS) framework that prunes the adjacency matrix and the GNN weights by minimizing novel loss function capturing the graph homophily property and information associated with the true labels of the train nodes and the pseudo labels of the test nodes. By iteratively applying ARGS to prune both the perturbed graph adjacency matrix and the GNN model weights, we can find graph lottery tickets that are highly sparse yet achieve competitive performance under different training-tine (poisoning) pnauttureperturbattionn attacks. Evaluations conducted on various benchmarks, considering attacks such as PGD, Atlakk PR-BCD, GR-BCD, and adaplive allack, demonstrate that ARGS can significantly improve the robustness of the generated GLTs, even when subjected to high levels of sparsity.
1
Introduction
Graph neural networks (GNNs)
Hamilton al,
2017
Kipf & Welling 2017 Veličković al. 2018 Zhou
ct al.
2020 Zhang al. 2020) achieve statc-of-tho-art
performance various graph-based tasks like semi-
supervised node classification (iipf & Welling
2017
Hamilton et al. 2017 Velicković et al. 2018 Chowdhury
et al.
2021 link prediction (Zhang & Chen 2018
Chowdhury et al. 2023b), and graph classífication (Ying) 2018 The success of GNNs attributed to the neural message paaggggpppsnnggggee scheme in which each node
et al.
updates its feature by recursively aggregating and transforming the features of its neighbors. However, the
"Equal contributions.

---

Published in Transactions on Machine Learning Research (September/2022 /2024)
effectiveness of GNNs, when scaled up to large and densely connected graphs, is impacted by the high training and inference cost and substantial memory consumption. Unified graph sparsification (UGS) (Chen et al. 2021] addresses this concern by sinultaneously pruning the input graph adjacency matrix and the GNN to find a graph lottery ticket (GLT), a pair of sparse graph adjacency matrix and GNN model, which can substantially reduce inference cost. without compromising model performance.
Recent studies reveal that GNNs are vulnerable to adversarial attacks (Dai al. 2018 Wu et al. 2019
Zügner& & Günnemann 2019 Mujkanovic et al, 2022. Jin al. 2021 In the transductive setting, the labels of a few nodes are given, and the goal is to predict the labels of the remaining nodes in the graph. An adversarial attack on the graph structure introduces unnoticeable perturbations by inserting, deleting, or rewiring edges in the graph. These perturbations increase the distribution shift between the train nodes, i.e. the nodes in the train set, and the test nodes in the test set, fooling the GNN to misclassify nodes (Li et al. 2023b) in the transductive node classification task. Many defense techniques have been developed to counter these attacks. Some techniques improve the node classification accuracy of GNNs by cleaning the perturbed graph structure (Wu et. al., 2019 Entezari et al., 2020 Jin al. 2020 Deng et al. 2022 Zhu et al.
2021b:: others improve the accuracy by modifying the GNN architecture (Zhang & Zitnik 2020: Geisler
ct al. 2021 Zhu et al. 2019 Although GLTs demonstrate strong performance on original benign graph data, their performance in the presence of adversarial structure perturbations remains largely unexplored. Achieving adversarially robust GLTS (ARGLTs) can enable efficient GNN inference under adversarial threats.
We pursue this objective by first investigating empirically the resilience of GLTs identified by UGS against different structure-pertarbation attacks [uügner& & Günnemann) 2019
PGD Attack
Liu et al. 2019; Mujkanovic et al.j 2022 Chowdhury et al.
Accuracy (GCN cora)
70
Perturbation rate 5%
2024 2023a) and showing that they are vulnerable. We then
present ARGS (Adversarially Robust Graph Sparsification), an optimization framework that, given an adversarially per- turbed graph, iteratively prunes the graph adjacency matrix and the GNN model weights to generate an adversarially robust graph lottery ticket (ARGLT) which achieves com- petitive node classification accuracy while exhibiting high levels of sparsity.
56-
ARGS
UGS
28-
Random Pruning
Baseline (STRG)
ARGLT
5
60
Graph Sparsity (%)
Adversarial attacks like the projected gradient descent (PGD)
attack (Wu et al.] 2019), the meta-learning- based graph attack (Meta (Zügner & Günnemann 2019h, h, the projected randomized block coordinate descent (PR-BCD) attack (Geislerr et al.) 2021), and the greedy randomized block coordinate descent (GR-BCD) attack (Geisler et al. 2021), poison the graph structure by adding new edges or deleting existing edges, resulting in changes in the properties of the graph. In the case of homophilic graphs, connected nodes generally have similar features and often belong to the same class, while for heterophilic graphs, linked nodes have dissimilar features and different classes. Our analysis shows that the PGD attack and the MetaAttack introduce most edge modifications around the train nodes [Li et al., 2023b) while the local structure of the test. nodes is less affected. Moreover, for homophilic graphs, adversarial edges are often introduced between nodes with dissimilar features. In contrast, for heterophilic graphs, adversarial edges are introduced between nodes with dissimilar neighborhood structures. We leverage this information to formulate a new loss function that better guides the pruming of the adversarial edges in the graph and the GNN weights. Additionally, we use self-learning Amini et al. (2022) to train the pruned GNNs on sparse graph structures, which improves the classification accuracy of the GLTs To the best of our knowledge, this is the first study on the adversarial robustness of GLTs.
Figure 1: Comparison of different graph sparsifi- cation techniques in accuracy vs. graph sparsity, ARGS achieves similar accuracy (see red star) with 35% more sparsity for the Cora dataset. under the PGD attack.
Our proposal is evaluated across various GNN architectures both homophilic (Cora, citescer, PubMed, OGBN-ArXiv,
and heterophilic (Chameleon, Squirrel) graphs attacked by the PGD attack, the MetaAttack, the PR-BCD attack [Geisler et al. 2021), and the GR-BCD attack, for the node classification task. We also evaluate the proposed technique for an adaptive attack, ie.. a stronger form of attack specifically
2

---

Published in Transactions on Machine Learning Research (teptember/202/
designed to target our technique. By iteratively applying ARGS, ARGLTs can be broadly located across the 7 graph datasets with substantially reduced inference costs, up to 98% multiply-andacccmmlatt (MAC) savings, and little to no accuracy drop. Figure shows that, for node classification on Cora attacked by the PGD attack, our ARGLT achieves similar accuracy to that of the full models and graphs even with high graph and model sparsity of 48.68% and 94.53%, respectively. Compared to the GLTs identified by UGS, our ARGLTs on average achieve the same accuracy with 2.4x higher graph sparsity and 2.3x higher model sparsity.
2
Related Work
We provide an overview of the graph lottery ticket hypothesis, adversarial attacks on graphs, and the existing defenses against such attacks.
2.1 Graph Lottery Ticket Hypothesis
The lottery ticket hypothesis (LTTH) (Frankle & Carbin 2019) conjectures that there exist small sub-networks, dubbed as lottery tickets (LTs), within a dense randomly initialized neural network, that can be trained in isolation to achieve comparable accuracy to that of their dense counterparts. Unified graph sparsificatio (UGS) made it possible to extend the LTH to GNNs (Chen et al., 2021), showing the existence of GLTTs that can make GNN inference efficient. A GNN sub-network along with a sparse input graph defined a GLT if the sub-network with the original initialization, trained on the sparsified graph, has a test. accuracy that matches the one of the original, umpruned GNN trained the full graph. Specifically, during training, UGS applics two differentiable binary mask tensors to the adjacency matrix and the GNN model weights, respectively. After training, the lowest-magnitude elements are removed and the corresponding mask location is updated to O, eliminating the low-scored edges and weights from the adjacency matrix and the GNN, respectively. The sparse GNN weight parameters are then rewound to their original initialization. To identify the GLTs, the UGS algorithm is applicd in an iterative fashion until pre-defined graph and weight sparsity levels are reached. Experimental results show that UGS can significantly trim down the inference computational cost without compromising predictive accuracy. In this work, we aim to find GLTs for datasets that have been adversarially perturbed. When we apply the UGS algorithm directly to the perturbed graphs, the accuracy performance of the GLTs is substantially lower than the one of their clean counterparts, calling for new methods to find adversarially robust GLTTs
2.2 Adversarial Attacks on Graphs
Adversarial attacks on graphs can be classified as poisoning attacks, perturbing the graph at train time, and evusion allacks, perturbing the graph at test. lime. Both poisoning and evasion allacks can be targeled or global attacks [Liu et al. 2019). A targeted attack deceives the model misclassify a specific node (Zügner et al., 2018 Bojchevski & Günnemann 2019 A global attack degrades the overall performance of the model (Zügner
& Günnemann 2019 Wu et al. 2019 Depending on the amount of information available, the existing attacks can further be categorized into white-bor attacks, gray-boz attacks, and black-bor attacks (Zügner ltt al.] 2018 Chang et al.) 2020). Finally, an attacker can modify the node features, the discrete graph structure, or both. Different attacks show that structure perturbation is often more effective when compared to modifying the node features (Zhu et al. 2021ab.
Examples of global poisoning attacks include the MetaAttack Zügner & Günnemann, 2019 PGD attack WW et al. 2019), PR-BCD attack (Geisler et al., 2021), and GR-BCD attack (Geisler et al. 2021 Gradient- based attacks like PGD and MetaAttack treat the adjacency matrix a parameter tensor and modify it via scaled gradient-based perturbations that aim to maximize the loss, thus resulting in degradation of the GNN prediction accuracy. PR-BCD and GR-BCD (Geisler et al. 2021) are more scalable, first-order optimization- based attacks that can scale up to large datasets like OGBN-ArXiv and OGBN-Produets (Hul ct al. (020), respectively. Global poisoning attacks are highly effective in reducing the classification accuracy of multiple GNN models and are typically more challenging to counter since they modify the graph structure before training (Zhu et al. 2021a). In this work, we consider global graph-structure poisoning attacks.
3

---

Published in Transactions on Machine Learning Research (tttemmber/20244
2.3 Defenses on Graphs
Several approaches have been developed to combat adversarial attacks on graphs (Tang et al. 2020 Entezari
et al.] 2020 Zhu et al.] 2019 Jin a 2020 Zhang & Zitnik 2020 Wu et al, 2019 Deng et al. 2022
Zhou et al. 2023 Many of these techniques try to improve the classification accuracy by preprocessing
the graph structure, i.e., they detect the potential adversarial edges and assign lower weights to these odges, or even remove them. Jaccard-GCN (Wu et al. 2019) removes all the edges between nodes whose features exhibit a Jaccard similarity below a certain threshold. SVD-GCN (Entezari et al. 2020) replaces the adjacency matrix with a low-rank approximation since many real-world graphs are low-rank and attacks tend to disproportionately affect the high-frequency spectrum of the adjacency matrix. ProGNN (Jin et al.) 2020) leverages low-rank, sparsity, and feature smoothness properties of graphs to clean the perturbed adjacency matrix. GARNET (Deng et. al., 2022) combines spectral graph embedding with probabilistic graphical models to recover the original graph topology from the perturbed graph. GNNGuard (Zhang & Zitnik 2020
learns weights for the edges in cach message passing aggregation step via cosine similarity and penalizes the adversarial edges either by filtering them out or by assigning less weight to them. STABLE (Li et al.] 2022 preprocesses the graph structure by leveraging unsupervised learning. Instead of using the node features like the above mentioned techniques, STABLE leverages contrastive learning to learn new node representations, which are then used to refine the graph structure. Other techniques try to improve the GNN performance
by enhancing model training through data augmentation (Li et al. 2022 Feng et al.] 2020), adveraarial training (Wu et al., 2019), self-learning (Li et al., 2023b), robust aggregate functions (Geisler et al. 2021 Li
et al. 2022). or by developing novel GNN layers Zhu et al. 2019).
Differently from the approaches above, GCN-LFR (Chang et al. 2021), a spectral-based method, leverages the fact that some low-frequency components in the graph spectrum are more robust to edge perturbations and regularizes the training process of given GCN with robust information from an auxiliary regularization ion network to improve its adversarial performance. Overall, graph preprocessing tends to remove only a small fraction of edges from the adjacency matrix. Additionally, none of these defenses roduces the number of parameters in the GNN model, which results in unchanged computational footprints. We instead aim to improve the robustness of sparse GNNs with sparse adjacency matrices to achieve computation efficiency. As robustness generally requires more non-zero parameters, yielding parameter-efficien robust GLTss remains a challenge.
3 Preliminaries
Notation. Let 9 = (V, & represent an undirected graph with [V] nodes and [E] edges. The topology of the graph can be represented with an adjacency matrix A E RR x|V| where A., = there is an edge ei,j E E between nodes u, and Uj while A.j = otherwise. Each node U; E V has an attribute feature vector æ; E R where F is the number of node features. Let X E R|P|xF and Y E R denote the feature matrix and the labels of all nodes in the graph, respectively, where C' is the number of classes in the dataset. With a slight abuse of notation, in this paper, we will also represent a graph as a pair X), We call the nodes in the train set as Irain nodes, whereas those within the test set are denoted as lest nodes. In the case of message- message-passing GNN, the representation of a node v, is iteratively updated by aggregating and transforming the representations of its neighbors. As an example, a two-layer GCN Kipf & Welling 2017) can be specified as
z = 1(1, 0) = ((Ao
(1)
where Z is the prediction, θ = (Wo, Wi) are the weights, (.) is the activation function, e.g., rectified linear unit (ReLU), S(.) is the softmax function, Å = P + D- is the normalized adjaceney matrix with self-loops, and D is the degree matrix of A + I. We consider the transductive semi-supervised node classification (SSNC) task for which the cross-entropy (CE) loss over the train nodes is given by
(o(f((,,)),)))
- Σ Σ Yú, log (Z)))
(2)
lEVTL.
4

---

Published in Transactions on Machine Learning Research (rntembbe//2024]
PGD Attark
MetaAttark
PGD Attack
MetaAttack
60
80
80
80
Accuracy (Citesear)
Accuracy (Cora)
70
72
-2
72
60
64
04
64
50
56
-6
56
Perturbation rate 5%
Perturbation rate 5%
Perturbation ate 55%
Perturbation rate 5%
Perturbation rate 20%
48
Perturbation rate 20%
Perturbation rate 20%
46
Perturbation rate 20%
Baseline
Baseline
Baseline
Baseline
30
5 P p
3.....-----555 61 4 &
& Dop--ip-- ( Graph Sparsity (56
Graph Sparsty (96)
Graph Sparsity (56)
Graph Sparsity (96)
Figure/ 2: Classification accuracy of GLTs generated using UGS for Cora and Citeseer datasets attacked by the PGD attack and the MetaAttack. The baseline refers to accuracy the clean graph.
where Vrr is the set of train node indices, C' is the total number of classes, and Y is the one-hot encoded label of node up In the transductive SSNC task, for a given graph, the labels of the train nodes are known and the goal to predict the labels of the remaining one, i.c., the test nodes.
Graph Lottery Tickets. A GLT consists of a sparsified graph, obtained by pruning some edges 9, and a GNN sub-network, with the original initialization, that can be trained to achieve comparable performance to the original GNN trained on the full graph, where performance is measured in terms of test accuracy. Given GNN O) and graph G = X), the associated GNN sub-network and the sparsified graph can be represented as f(,, mg O ①) and G, = {mg @ X), respectively, where my and mg are dabeerentiable masks applied to the adjacency matrix A and the model weights θ respectively, and @ is the element-wise product. UGS (Cen et al. 2021 finds the two masks my and mg by minimizing the loss function Luos = (o(m(mm @ A,
AXJmma mg C ))) + +hl | + /b2l/molli such that the GNN sub-network f(,, mg @ θ) along with the sparsified graph G, can be trained to similar accuracy as f(, () on G, where 1/1, 1/2 are the l--mrmm sparsity regularizers of mg: ma-
Poisoning Attack on Graphs. In this work, we primarily investigate the robustness of GLTSs under global poisoning attacks that modify the structure of the graph. In the case of a poisoning attack, GNNs are trained on a graph that has been maliciously modified by the attacker. The aim of the attacker is to find an optimal perturbed A' that fools the GNN into making incorrect predictions. This can be formulated as a bi-level optimization problem ZZigner et al. 2018 Zügner & Güinnemann 2019
arg max Latk (f(A'', x), +*)) ('E
(3)
s.t. = arg mig min (o(f(t'',x,.00
A ||A'- < A, Lark is the attack loss function, A is the perturbation rate, and O' is the optimal parameter of the surrogate GNN model used to perform the attack. ||. llo is the Lo norm, counting the number of non-zero elements. We provide details about the different poisoning attacks in Appendix A.2
where (AA) is the set of adjacency matrices that fit the constraint
4 Graph Sparsification Under Adversarial Attacks
We perform the MetaAttack Zügner & Günnemann 2019 and the PGD attack (wu et al. 2019) the Cora and Citeseer datasets with different perturbation rates. We use the same setup as Xu et al. 2019 Zhang & Zitnik (0200), and Mujkanovic et al. (2022) for performing the poisoning attacks on the datasets. Then, we apply UGS on these perturbed graphs to find the GLTs, As shown in Figure 2 the classification accuracy of the GLTs identified by UGS is lower than the clean graph accuracy. The difference increases substantially when the perturbation rate increases. For example, the PGD attack, when the graph sparsity is 30%, at 5% perturbation, the accuracy drop is 6%. This drop increases to 25% when the perturbation rate is 20%. Moreover, for 20% perturbation rate, even with 0% sparsity, the accuracy of the GNN is around 20%
5

---

Published in Transactions on Machine Learning Research Hrptember/2022/
Citeseer
Chameleon
Chameleon
Nortal udges Adversartsl edges
Normal edgus Advensrttal edges
0.0
Normal edgis
Dendity Distribution
Density Distribution
2.02
Density Distributtoo
0.15
Adveen nal edges
2,03
0.2
2.04
0.09
6.44
6.2
2.00
2.00
0.00
Attibute Feature Difference Beimeen Cornected Nodus
Atir bute Feature Difference Butweon Cornected Nodes
Positional Feature Differncce Between Connected Nodus
(a)
(b)
(c)
Figure 3: Impact of adversarial attacks graph properties. (a), (b) Density distribution of attribute feature differences connected nodes in perturbed homophilic (Citeseer) and heterophilic (Chameleon) graphs. (c) Density distribution of positional feature differences of connected nodes in perturbed heterophilic graphs.
lower than that of the clean graph accuracy. While UGS removes edges from the perturbed adjacency matrix, as shown in Figure [ it may not effectively remove the adversarially perturbed edges. naive application of UGS may not be sufficient to improve the adversarial robustness of the GLTs. Consequently, there is a need for adversarially robust UGS technique that efficiently remove the edges affected via adversarial perturbations while pruning the adjacency matrix and the associated GNN, along with improved adversarial training, allowing the dual benefits of improved robustness and inference efficiency.
Analyzing the Impact of Adversarial Attacks on Graph Properties. Adversarial attacks like the MetaAttack, PGD, PR-BCD, and GR-BCD poison the graph structure by either introducing new edges or deleting existing edges, resulting in changes in the original graph properties. We analyze the difference in the attribute features of the nodes that are connected by the clean and adversarial edges. Figure 3h and b depict the density distribution of the attribute feature difference between connected nodes in homophilic and heterophilic graph datasets attacked by the PGD attack. In homophilic graphs, the attack tends to connect nodes with large attribute feature differences. defense technique can potentially leverage this information to differentiate between the benign and adversarial edges in the graph(Chen et al. 2022). However, this is not the case for heterophilic graphs (Zhu et al. (202)). For heterophilic graphs, we resort, instead, to the positional features of the nodes, using positional encoding techniques like DeepWalk (Perozzi et al. 2014). As observe from Figure b in heterophilic graphs, attacks tend to connect nodes with large positional fcature differences. ARGS uses these graph properties to iteratively prune the adversarial edges from homophilic and heterophilic graphs.
5 Adversarially Robust Graph Sparsification
We present ARGS, sparsification technique that simultaneously reduces edges in G and GNN parameters in @ under adversarial attack conditions to effectively accelorate GNN inference yet maintain robust classification accuracy. ARGS reformulates the loss function to include (a) a CE loss term on the train nodes, (b) a CE loss term on a set of test nodes, and (c) a square loss term on all edges. Pruning the edges based on this combined loss function results in the removal of adversarial well as less-important non-adversarial edges from the graph.
Removing Edges Around the Train Nodes. Poisoning attacks like the MetaAttack and the PGD attack lend to modily more the local structure around the train nodes than that around the test nodes (Li et al. 2023b). Specifically, a large portion of the modifications introduced to the edges connecting a train node to test node or train node to another train node. We include a CE loss term associated with the train nodes, as defined equation 2 in our objective function to account for the edges surrounding the train nodes. These edges include both adversarial and non-adversarial edges.

---

Published in Transactions on Machine Learning Research (September/202)) 22024)
Removing Adversarial Edges. In numerous application domains, including social graphs, web page graphs, and citation graphs, connected nodes in homophilic graph exhibit similar attribute features, while they still keep similar positional features in heterophilic graphs (Li et al., 2022; McPherson et al.) 2001 Kipf & Welling 2017 J. On the other hand, as shown in Figure g adversarial attacks tend to connect nodes with distinct attribute features in homophilic graphs and distinct positional features in heterophilic graphs. Therefore, we help remove adversarial edges and encourage feature smoothness by including the following loss to our objective function for homophilic graphs:
( x)
Σ Aly(w; - wzz)² 2,j=1
2
where A' is the perturbed adjacency matrix and (ar; 1 22)² measures the attribute feature difference. For heterophilic graphs, we introduce instead the following loss term:
(A') Σ Aly yÿ)
(5)
s,==1
where yr y E R.P are the positional features of nodes i, obtained by running the DeepWalk algorithm Per-
ozzi et al. 2014 on the input graph G, is the number of node positional features, and (y: - -2,)² measures
the positional feature distance.
Removing Edges Around the Test Nodes. Removal of edges tends to be random in later iterations of UGS (Hui et al. 2023) since only a fraction of edges in G is related to the train nodes and directly impacts the corresponding CE loss. To better guide the edge removal around the test nodes, we also introduce a CE loss term for these nodes. However, the labels of the test nodes are unknown. We can then leverage the fact that structure poisoning allacks only modify the structure surrounding the train nodes, while their features and labels remain "clean." " Therefore, we first train simple multi-layer perceptron (MLP) with layers on the train nodes. MLPs only use the node features for training. We then use the trained MLP to predict the labels for the test nodes. We call these labels pseudo-labels. Finally, we use the test nodes for which the MLP has high prediction confidence for computing the test node CE loss term. Let Vrr be the set of test nodes for which the MLP prediction confidence is above threshold and Ymup be the prediction by the MLP. The CE loss is given by
C,U[(A',,)))))
Σ EXmimy Yminy log( Zz
(6)
1E)rr.j=l
In summary, the complete loss function that ARGS minimizes is
LARGS = aLolf(Im, @ A), me @ +)) + BC 3 A' tffi(f((m 3 A', x), mg @ θ)) + A mylli + dellmellı.
(7)
where B, År, and X2 are hyperparameters and the value of a
and y is set to 1. d and Ag are the 4-norrm regularizers of my and me, respectively. After the training is complete, the elements with the smallest values in my and ma, representing the lowest percentages Py and Pa, are set to O. Then, the updated masks are applied to prune A and θ, and the weights of the GNN are rewound to their original initialization value to generate the ARGIT. We apply these steps iteratively until we reach the desired sparsity 8n and sg. Algorithm I illustrates our iterative pruning process. As shown in Figure 4 most of the adversarial perturbation edges are between train and test nodes (Li ct al., 2023bb. Morcover, our proposed sparsification technique successfully removes many of the adversarial edges. In particular, after applying our technique for 20 iterations, where each iteration removes 5% of the graph odges, the number of train- tainn train-test, and test-test adversarial edges reduces by 13%, 47.3%, and 14.3%, respectively.
No. Adversriial Edges
14.0
Train-Test Train Train Test-Test
1200
1000
800-
6:0
430
2:00
Pruning Iterati ons
Figure 4: Evolution of adversarial edges in Cora dataset (attacked by PGD, 20% pertur- bation) as we apply ARGS prune the graph. Train-Traie edges connect two nodes from the train set. Train-Test edges connect node from the train set with one from the test set. Test- Test edges connect two nodes from the test set.
7

---

Published in Transactions on Machine Learning Research (September/2024) 2202))
Algorithm 1 Adversarially Robust Graph Sparsilication
Input: Graph 9 = {A, X), GNN f(g, O") with initialization 0", Sparsity levels sg for graph and sa for GNN, Initial masks My = A, me = 1/
Output: Final masks may me
while
mollo || lo
8g and mmmello 89 do |ello
2:
m mg. m ms. O (W W
3: for
t= 0, T
do
4:
Input G = {m) C A. } to f(.,m) @ O¹) to compute the loss LARGS in equation equation
5:
@*+1 + O -V VV LARGS
6:
m² + mgg wi V mg CARGS
7:
[41 < my We V m LARGS m2
8:
my mm-- ma mi m
9:
Set percentage Pg the lowest-scored values in mg to 0 and set others to
10: Set percentage po of the lowest-scored values in my to 0 and set others
Training Sparse ARGLTs. Structure poisoning attacks do not modify the labels of the nodes. In the case of attacks like PGD and MetaAttack, the locality structure of the test nodes is less contaminated (Li et al. 2023b). implying that. the train node labels and the local strueture of the test. nodes contain relatively clean information. We leverage this insight and train the GNN sub-network using both train nodes and test nodes. We use a CE loss term for both the train (Lu) and test (41) nodes. Since the true labels of the test nodes are not available, we train an MLP on the train nodes and then use it to predict the labels for the test nodes [Li et al. 2018 2023b). To compute the CE loss, we use only those test nodes for which the MLP has high prediction confidence. The loss function used for training the sparse GNN on the sparse adjacency matrix generated by ARGS is
min n)Co[(((m @ A', ma @ θ)) + (C X', mg (O),
where my and my are the masks evaluated by ARGS that are kept fixed throughout training, and 1y is set to 1. In the early pruning iterations, when graph sparsity is low, the test nodes are more useful in improving the model's adversarial performance because the train nodes' localities are adversarially perturbed and there exist distribution shifts between the train and test nodes. However, as the graph sparsity increases, adversarial edges associated with the train nodes are gradually removed by ARGS, thus reducing the distribution shift. and making the contribution of the train nodes more important in the adversarial training.
6 Evaluation
We evaluate the effectiveness of ARGS and assess the existence of ARGLI's across diverse datasets and GNN models under different adversarial attacks and perturbation rates. In particular, evaluate sparsification method on both homophilic and heterophilic graph datasets which are attacked by two structure poisoning attacks, namely, PGD (Wu et al. 2019) and Attakk (Zügner & Günnemann) 2019) We consider three
GNN models, namely, graph convolution networks (GCNs) (Kipf & Welling] [211]) graph isomorphism
networks (GINs) (Xu et al. 2019), and graph attention networks (Veličković et al.J 2018). We also evaluate
ARGS on larger datasets, namely, OGBN-ArXiv and DGBN-Produce (Hu et al. 2020). attacked by the PR-BCD and GR-BCD attacks, respectively, for the DecperGCN model. Finally, we evaluate the robustnoss of ARGS against adaptive atlacks (Mujkanovic et al. 2022).
We use DeepRobust, adversarial attack library Li et al. 2020 to perform the PGD attack and the MetaAttack and generate the perturbed graph adjacency matrix A'. When performing these attacks, we use surrogale models which have the same type and architecture of the GNN models being attacked. For example, when attacking ARGS on a 2-layer GCN, the surrogate model is also a 2-layer GCN. We use Pytorch-Geometii (Fey & Lenssen 2019h to perform the PR-BCD and GR-BCD attacks on the OGBN- ArXiv and OGBN-Products datasets, respectively. We compare our method with UGS (Chen et al. 2021 random pruning, and other stale-of-the-art adversarial defense methods, namely, STRG (Li et al.
2023b
8

---

Published in Transactions on Machine Learning Research (tttembbe/220244
ECN Cora
GAT Cora
GIN Cora
GCN Clteserr
GAT Cleeseer
GI Citeseer
PGD Attack Rbb rate: 20.0%
PGD Attack PtD rate: 20.0%
PGD Attack Rbb rate: 20.0%
Metakltack PLb rate: 20.0%
Metakitack rate: 0%
MetaAtaack Pib rate: 20.0%
870
60
65
50
60
55
40
60
30
30
20
70
30
9
@
40
@
89 39 40
4
@
20
8
49
@
10
30
10
30
50
Graph Spersity
80
40
30
20
1880
1.00
12000
20000
2000
2000
2500
1500
1009
3000
201000
2000
30000
2300
2000
2500
1000
Inference MACs (M)
ARGS
Random Fruning
Baseline (STRG)
Figure 5: Node classification performance versus graph sparsity levels and inference MACs for the GCN, CIN, and GAT architectures on Cora and Citeseer datasets attacked by PGD and MetaAttack, respectively. Red stars indicate the ARGLTs. Dash black lines represent the performance of STRG, an adversarial defense technique.
Table 1: Performance comparison between ARGS and other defense techniques in terms of accuracy and inference MAC count.
Cora (PGD) attack)
Citesorr (MetaAttack) Perturbation Rate 20%
Perturbation Rate 20%
Model
Accuracy (%)
Inference MACs (M)
Accuracy (%)
Inference MACs (M)
GON-ProGNN
63. 03.13
1832.14 14
61.02 #0.11
4006. 91
GCN-ARGS
77.53
68.97
43.78
GON-GNNGuard
73.1920.72
1948.32
71.62+1.01
4188.33
GCN-ARGS
7..5
78.78
71.78:00.88
211.77
GON-GARNET
G6. 1.110
1681.9 78.78
72.97+1.20
3898. 21
GON-ARGS
1.153
19.19:0.78
425.81
GNNGuard Zhang & Zitnik 2020), ProGNN (Jin et al. 2021 and Soft Only UGS and random pruning techniques prune both the graph adjacency matrix and the GNN model parameters - no other existing defense techniques prune the GNN model parameters. We set Pg = 5%, Pa 20%, similarly to the parameters used by UGS. More details on the dalaset. statistics, model configurations, and hyperparameters in ARGS can be found in Appendix A.I
GARNET
Deng et al. 2022
Median (Geisler et al. 2021
6.1 Defense Homophilic Graphs
We first evaluate the performance of ARGS on homophilic graphs against PGD and MetaAttack. Due to space limitations, show the results for 20% perturbation rate for the Cora and Citescer datasets. Results for PubMed and other perturbation rates are shown in Appendix A.4
Figure 5 shows the results for the GCN, GIN, and GAT architectures on the Cora and Citeseer datasets attacked by PGD and MetaAttack, respectively, where the average accuracy of the ARGLTs reported across 5 runs. ARGLTs at a range graph sparsity from 30% to 60% with similar performance as the STRG bascline can be identified across the different GNN backbones. The ARGITs significantly reduce the MAC operation count for GCN, GIN, and GAT by ~95%, 997% and ~83, respectively, for the Cora dataset. For the Citeseer dataset, the inference MAC's reduce by ~98% for all the backbone GNNs.
Comparison with Other Defense Techniques. We compare the performance of ARGS with the one of GNNGuard, GARNET, and ProGNN, which are all defense methods. Differently from ARGS, none of these methods prunes the weights of the GNN model. We compare these methods in terms of accuracy and inference MAC and we consider GCN as the backbone. For the different basclines, the GLT which has similar accuracy as the baseline with maximum graph and model sparsity identified as the ARGLT by ARGS and reported in Table [ For the Cora dataset, the ARGLT identified by ARGS for the PGD attack
9

---

Published in Transactions on Machine Learning Research (eptembbr/2024
Accuracy (Chameleon)
MetaAttack
MetaAttack Ptb rate 20.0%
PGD
rate
50
55
45
50
Accuracy (Squirrel)
35
40
35
40
330
30-
35
40
25
25
35
25
20
20
30
100
15
2
60
100
15
4
6
80
100
15
100
Weight Sparsity (%)
Weight Sparsity (9)
Weight Sparsity (%)
Weight Sparsity (%)
ARGS
UGS
Baseline (GARNET)
Figure 6: Node classification performance versus weight sparsity levels for GPRGNN on Chameleon and Squirrel dataset attacked by the PGD Attack and MetaAttack. * indicate the ARGLTs.
(20% perturbation rate) with maximun sparsity levels (model sparsity: 98.9%, graph sparsity: 64.1%) has classification accuracy of 77.53%. The three different defense techniques, namely, ProGNN, GNNGuard, and GARNET have classification accuracy of 63.43%, 73.19%, and 66.66%, respectively, which are all less than the classification accuracy of the ARGLT identified by ARGS. For the Citesoer dataset attacked by MetaAttack with a 20% perturbation rate, the most sparse ARGLT has a classification accuracy of 70.2%. The defense technique ProGNN has a classification accuracy 61.02%, which is less than the classification accuracy of the most sparse ARGLT. The defense techniques GNNGuard and GARNET have a classification accuracy of 71.62% and 72.97%, respectively. In these cases, the GLT with the same classification accuracy the defense technique is reported in Table
6.2 Defense on Heterophilic Graphs
We report the classification accuracy of ARGS on heterophilic graphs in Figure 6 We use GPRGNN (Chien et al. 2020) as the GNN model for the heterophilic graph datasets Chameleon and Squirrel (McCallum et al. 2000). GPRGNN performs better than GCN, GIN, and GAT for heterophilic graphs (Deng et al.) 2022). We use GARNET as the baseline since achieves state-of-the-art adversarial classification accuracy compared to other defense techniques for heterophilic graphs. As shown in Figure G ARGS is able identify GLTs that achieve similar classification accuracy GARNET for the Chameleon and Squirrel datasets allacked by PGD and MetaAttack with 85% to 97% weight sparsity, resulting in substantial reduction in inference MACs.
6.3 Defense on Larger Graphs
Perturbation Rate: 10.0%
Perturbation Rate: 15.0%
70-
70-
We evaluate the robustness of ARGS on the large-scale datasots OGBN-ArXiv and OGBN-Products. OGBN-ArXiv has 170,000
Accuracy (%6)
60
60
nodes and 1.16 million edges while OGBN-Products has 2.5 million nodes and 61 million edges. We use the PR-BCD attack for perturbing the OGBN-ArXiv dataset. Attempting the PR-BCD attack on the OGBN-Products dataset resulted in out-of-memory errors. We then conducted a more scalable GR-BCD attack (Geisler et al., 2021 on the OGBN-Products dataset, employing a perturbation rate of 50%. The reference GNN model Deeper-GCN (Li et al. 2023a) For both the PR- BCD and GR-BCD attacks, the adversarial edges are uniformly distributed among the train and test nodes. Hence, we set the value of ( to be 0. The PGD attack or MetaAttack faces timeout due to memory for these large graphs. Figure 7 shows that ARGS with 28-layer DeeperGCN can identify ARGLTs that have higher model and graph sparsity compared to UGS. We take GARNET as the bascline since it achieves better adversarial robustness than other defense techniques for the OGBN-ArXiv dataset. GARNET uses 28-leyer DeeperGCN as the backbone
55
35
80
50
49
<0
10
+7
6
45
4
40
8
&
Graph Sparsity (%)
Graph Sparsity (36
Accuracy (%)
58100
$2000
20000
M000
58000
Inference MACs (M)
Inference MACs (M)
Figure 7: Node classification performance ver- sus graph sparsity levels and inference MACs for Deeper-GCN OGBN-ArXiv dataset attacked by PR-BCD. * indicate the ARGLTs.
10

---

Published in Transactions on Machine Learning Research (September/202) 20024
Table 2: Comparison between ARGLTs identified by ARGS and GLTs identified by UGS in terms of Graph
sparsity, Model sparsity, and Inference MACs across different basclines for the OGBN-Products dataset.
Baseline
Accuracy (%)
Graph Sparsity(%)
Model Sparsity
Inference MACs(M)
UGS
ARGS
UGS
ARGS
UGS
ARGS
Modian GDC
59.23
87.89
75721.5
75727.8
GCN
62.71
83.32
87.84
83.36
87.89
104076.4
75727.8
GNNGuard GARNET
03.22
83.32
87.84
83.30
87.89
104076.4
75727.8
74.97
19.00
40.95
19.01
40.98
506511.0
369089.2
Table 3: ARGS and UGS performance comparison for the PGD attack and adaptive attack for the Cora, Citeseer, and PubMed dataset. GCN is used as the GNN model.
Classification Accuracy at
Classification Accuracy at
Perturbation Rate 5%
Perturbation Rate 10%
Graph Sparsity
Graph Sparsity 43.16% Model Sparsity 91. 70%
Graph Sparsity
Graph Spansity 43.16% Model Sparsity
Dataset
Technique
Attack
22.64%
22.64% Model Sparsity
Model Sparsity 67.60%
67.60%
91.70%
Cora
ARGS
PGD Attack
82.041:1 .09
80.68-0.85
82.8
80.18:1.13
Adaptive Attack
80.33+1.33
1.87
79.68+1.38
77.16=0.98
Citeseer
ARGS
PGD Attack
75.32:10.88
74.17-0.55
74.7=10.88
73.53:11.00
Adaptive Attack
7..11#1.76
73.10:0.887
1..93+1.87
71189:1.01
PubMed
ARGS
Attack
85.57-10.07
85.41
82.72:0000
$3.36:10.10
Adaptive Attack
83.09#0.06
$3.76:00.09
80.78+0.
83.04=0.09
GNN. The model sparsity and graph sparsity of the ARGLT are 94.50% and 48.67%, respectively, for the 10% perturbed dataset, and 94.50% and 48.70%, respectively, for the 15% perturbed dataset. Results on the OGBN-Products dataset are reported in Table Our baselines include GCN, GARNET, GNNGuard, and Soft Median GDC. For the different baselines, the GLT which has similar accuracy as the baseline with maximum graph and model sparsity identified as the ARGLT by ARGS and reported in Table 2 As evident from Table ARGS can identify lottery tickets with higher graph and model sparsity than UGS.
6.4 Defense Against Adaptive Attacks
Recently, adaptive attacks (Mujkanovic et al. 2022 have been developed, which are stronger attacks since they are specifically tailored for a given defense technique. Because all the components in the loss function of ARGS are differentiable, ARGS can be directly attacked by an adaptive attack. Specifically, we evaluate ARGS on a gradient-based adaptive attack, called Meta-PGD (Mujkanovic et al., 2022) which iteratively perturbs the adjacency matrix. Table compares the performance of ARGS against the PGD atlack and the adaptive attack, with GCN as the GNN backbone for Cora and CiteSeer. For 5% perturbation rate, the accuracy of the ARGIT identified by ARGS reduces by only ~1.7% for Cora while for CiteSeer it reduces by only ~1.5% For 10% perturbation rate, the reduction in classification accuracy is 2.99 for the Cora dataset and ~2.5% for the Citeseer dataset, showing that the performance degradation of ARGS from adaptive attacks is minimal. We also perform the adaptive attack on OGBN-ArXiv and the results are highlighted in Table
Table 4: ARGS and UGS performance comparison for the PRBCD attack and adaptive attack for the OGBN-ArXiv dataset. DeeperGCN is used the GNN model.
Classification Accuracy
Classification Accuracy
Perturbation Rate 10%
Perturbation Rate 15%
Graph
Sparsity
Graph Sparsity 26.5% Model 73.8%
Graph Sparsity
Graph Sparsity 26.5%
Dataset
Technique
Attack
5.0%
5.0%
Model 20.0%
Spansity
Spansity
Model Sparsity 20.0%
Model Sparsity 73.8%
OGBN-ArXIv
ARGS
PRBCD Attack
68.70
68.28 67.83
69.19 67.06
67.64
Adaptive Attack
68.30
66.38
11

---

Published in Transactions on Machine Learning Research (ttemmber/20244
GCk Cleader
DDN Dara
SCN Cleweer
GCN Cara
GCN Claseer
GCN Cara
70
Accurncy (S3)
70
65
55
50
4 9 9
80
19
19
19
60
59
8
50
99
8
4
59 +P
60
-9
-9
40
50
69
4 59 50
89 8 69 8
80
Graph Sparsity
(%)
Graph Spariiyy 0%)
Graph Sparsity (5)
8
Accurnay
8
8
50
Inference MACS
Inference MACS (M)
MACS (H)
ARGS
UGS
Baseline (STRC)
Figure Node classification performance over achieved graph sparsity levels for a GCN model on Cora and Citescer datasets attacked by a version of the MetaAttack that modifics both graph structure and node features. The perturbation rales are 5%, 10,, and 15%. Red stars indicate the ARGLTs. STRG is used as the baseline. indicate the ARGLTs.
6.5 Analysis Under Structure and Node Feature Attacks
In addition to structural attacks, also evaluate the performance of ARGS against attack that modifics both the graph structure and the node features simultancously. Mettack (Zügner & Günnemann 2019 be modified for this purpose. For a given perturbation budget, this attack performs a structure perturbation and a feature perturbation at each iteration, and between the two perturbations, it chooses the one that results in a higher attack loss. This iterative process is repeated until the perturbation budget is exhausted. We attack the Cora and Citeseer clttasets with 5%, 10,, and 15% perturbation rates, and use the STRG defense technique as the bascline. ARGS can find highly sparse GLTs that achieve similar classification accuracy as the baseline for different graph datasets perturbed with different perturbation rates using this attack. For example, for 5% perturbation rate, ARGS finds GLTs that have 53.75% graph sparsity and 96.55% model sparsity for the Cora. dataset and 58.31% % graph sparsity and 97.92% model sparsity for the Citeseer dataset. We also include the performance of UGS for comparison. Figure S shows that, for the same sparsity levels, GLTs identified by ARGS achieve much higher classification accuracy when compared to GLTs identified by UGS. We observe that the attacked graph contains more edge perturbations than feature perturbations since modifying the graph structure results in higher attack loss than modifying the node features. This result shows that ARGS can find highly sparse GLTs for graphs allacked by both structure and node feature perturbations.
6.6 Ablation Study
We evaluate the effectiveness of each component of the proposed loss function for the sparsification algorithm by performing an ablation study, as shown in Table 5 We consider the Cora dataset under the PGD attack with 10% and 20% perturbation rates. Configuration 1 corresponds to ARGS with all the loss components in Configuration 2 does not use the feature smoothness component in (4) while configuration 3 skips the CE loss associated with the predicted test nodes in (6). Configuration 4 skips both the smoothness and CE loss on predicted test nodes. Table 5 shows that both configurations 2 and 3 improve the final performance when compared to that of configuration 4, highlighting the importance of the losses introduced in 4 and (6). More importantly, both high and low target sparsity, we yield the best classification performance with configuration 1, showcasing the importance of the unified loss function provided in Appendix A.6
(7). Further ablation studies are
12

---

Published in Transactions on Machine Learning Research (September/2022 20024)
Table 5; Ablation study.
Classification Accuracy at
Classification Accuracy at
GCN, Cora, PGD Attack
Perturbation Rate 10%
Perturbation
20%
Graph
Sparsity
Graph Sparsity 64.4% Model 98.9%
Graph
Sparsity
Graph Sparsity
Configuration
B
9.8% Model Spansity
9.8%
64.5% Model Sparsity 98.9%
Sparsity
Model
Sparsity
36.1%
/
/
/
83.25
76.10
80.63
75.60
82.01
70.57
78.92
64.84
24
72.84
78.97
52.92
x
80.58
62.42
75.7
54.18
7 Conclusion
In this paper, we first empirically observed that the performance of GLTSs collapses against structure- perturbation poisoning attacks. To address this issue, we presented a new adversarially robust graph sparsification technique, ARGS, that prunes the perturbed adjacency matrix and the GNN weights by minimizing novel loss function. By iteratively applying ARGS, we found ARGLTs that are highly sparse yet achieve competitive performance under different structure poisoning attacks. Our evaluation showed the superiority of our method over UGS at both high and low sparsity regimes.
7.1 Broader Impact
Graphs are universally used to capture the structure of real-world complex systems. Empowering deep learning for reasoning and making predictions over graph-structured data of broad interest in a wide range of applications, such as recommendation systems, neural architecture search, and drug discovery. However, scaling up GNNs to large datasets is often difficult due the computational costs. Besides, GNNs are highly vulnerable to adversarial attacks. This work aims to find GNN models that reduce the computational footprint yet maintain adversarial robustness. Such robust models will enable efficient and reliable deployment of GNNs.
7.2 Acknowledgments
This research was supported part by the National Science Foundation under Awards 1846524 and 2139982, the Office of Naval Research under Award N00014-00-1-2258, the Okawa Research Grant, and the USC Center for Autonomy and Artificial Intelligence.
References
Massih-Reza Amini, Vasilii Feofanov, Loic Pauletto, Lies Hadjadj, Emilie Devijver, and Yury Maximov. Self-training: A survey, arXiv preprint orXiv:2202.12440 2022.
Aleksandar Bojchevski and Stephan Günnemann. Adversarial attacks on node embeddings via graph poisoning. In International Conference on Machine Learning, pp. 695-704 PMLR, 2019.
Heng Chang, Yu Rong, Tingyang Xu, Wenbing Huang, Honglei Zhang, Peng Cui, Wenwu Zhu, and Junzhou Huang. A restricted black-box box adversarial framework towards attacking graph embedding models. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 3389-3396, 2020.
Heng Chang, Yu Rong, Tingyang Xu, Yatao Bian, Shiji Zhou, Xin Wang, Junzhon Huang, and Wenwu Zhu. Not all low-pass filters are robust in graph convolutional networks. Adoances in Neural Information Processing Systems, 34:25058 25071, 2021.
Tianlong Chen, Yongduo Sui, Xuxi Chen, Aston Zhang, and Zhangyang Wang. A unified lottery ticket hypothesis for graph neural networks. In International Conference on Machine Learning, pp. 1695-1706. PMLR, 2021.
13

---

Published in Transactions on Machine Learning Research (September/202)
Yongqiang Chen, Han Yang, Yonggang Zhang, MA KAILI, Tongliang Liu, Bo Han, and James Cheng. Understanding and improving graph injection attack by promoting unnoticeability. In International Conference on Learning Representations, 2022.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. Xiv preprint arx:::0006. 079888 2020.
Subhajit Dutta Chowdhury, Kaixin Yang, and Pierluigi Nuzzo. ReIGNN: State register identification using graph neural networks for circuit reverse engineering. In 2021 IEEE/ACM Internalional Conference On Computer Aided Design (ICCAD), pp. 1-9. IEEE, 2021.
Subhajit Dutta Chowdhury, Zhiyu Ni, Qingyuan Peng, Souvik Kundu, and Pierluigi Nuzzo. Sparse but strong: Crafting adversarially robust graph lottery tickets. arXiv preprint ar 06568, 2023a.
Subhajit Dutta Chowdhury, Kaixin Yang, and Picrluigi Nuzzo. Simll: Similarity-based logic locking against machine learning attacks. In 2023 60th ACM/IEEE Design Automation Conference (DAC), pp. 1 6. IEEE, 2023b.
Subhajit Dutta Chowdhury, Zhiyu Ni, Qingyuan Peng, Souvik Kundu, and Pierluigi Nuzso Analyzing adversarial vulnerabilities of graph lottery tickets. In ICASSP 2024-2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 7830 7834. IEEE, 2024.
Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song. Adversarial attack on graph structured data. In International conference on machine learning, pp. 1115-1124. PMLR, 2018.
Chenhui Deng, Xiuyu Li, Zhuo Feng, and Zhiru Zhang, GARNET: Reduced-rank topology learning for robust and scalable graph neural networks. In Learning on Graphs Conference, pp. 3-1. PMLR, 2022.
Negin Entezari, Saba A Al-Sayouri, Amirali Darvishzadeh, and Evangelos E Papalexakis. All you need is low (rank) defending against adversarial attacks on graphs. In Proceedings of the 13th International Conference on Web Search and Dala Mining, pp. 169 177, 2020.
Wenzheng Feng, Jie Zhang, Yuxiao Dong, Yu Han, Huanbo Luan, Qian Xu, Qiang Yang, Evgeny Kharlamov, and Jie Tang. Graph random neural works for semi-supervised learning on graphs. Advances in neural information processing systems, 33:22092 22103, 2020.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In TCLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference on Learning Representations, 2019.
Simon Geisler, Tobias Schmidt, Hakan Sirin, Daniel Zügner, Aleksandar Bojchevski, and Stephan Günnemann. Robustness of graph neural networks at scale. Advances in Newral Information. Processing Systems, 34: 7637 7637-76499, 2021.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ron, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in newral information processing systems, 33:22118 22-12333, 2020.
Bo Hui, Da Yan, Xiaolong Ma, and Wei-Shinn Ku. Rethinking graph lottery tickets: Graph sparsity matters. In The Eleventh International Conference on Learning Representations, 2023.
Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 66-74, 2020.
14

---

Published in Transactions on Machine Learning Research (September/2022 2202)
Wei Jin, Yaxing Li, Han Xu, Yiqi Wang, Shuiwang Ji, Charu Aggarwal, and Jiliang Tang. Adversarial attacks and defenses on graphs: A review and empirical study. SIGKDD Explor. Newsl., 22(2):19-3k) 34, jan 2021. ISSN 1931-0145.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
Guohao Li, Chenxin Xiong, Guocheng Qian, Ali Thabet, and Bernard Ghanem. DeeperGCN; Training deeper GCNs with generalized aggregation functions. IEFE Transactions on Pattern Analysis and Machine Intelligence, 45(1)):13024 13034, 2023a. doi: 10.1109 /T00//TPP2..222233600000
Kuan Li, Yang Liu, Xiang Ao, Jianfeng Chi, Jinghua Feng, Hao Yang, and Qing Hc. Reliable representations make a stronger defender: Unsupervised structure refinement for robust gun. In Proceedings of the 28th ACM SIGKDD conference on knowledge discovery and data mining, pp- 925-939--- 2022.
Kuan Li, Yang Liu, Xiang Ao, and Qing He. Revisiting graph adversarial attack and defense from a data distribution perspective. In The Eleventh International Conference on Learning Representations, 2023b.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi- supervised learning. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
Yaxin Li, Wei Jin, Han Xu, and Jiliang Tang. DeepRobust: A pytorch library for adversarial attacks and defenses. arxiv preprint ar 2rxi::2005.061 06149, 2020.
Xuanqing Liu, Si Si, Jerry Zhu, Yang Li, and Cho-Jui Hsich. A unified framework for data poisoning attack to graph-based semi-supervised learning. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 3:127 163, 2000.
Miller McPherson, Lynn Smith-Lovin, and James M Cook. Birds of a feather: Homophily in social networks. Annual review of sociology, 27(1):415 14415-4444-11 2001.
Felix Mujkanovic, Simon Geisler, Stephan Günnemann, and Aleksandar Bojchevski. Are defenses for graph neural networks robust? Advances in Neural Information Processing Systems 35 (NeurIPS 2022), 2022.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. DeepWalk: Online learning of social representations, In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and dala mining, pp. 701-710, 2014.
Xianfeng Tang, Yandong Li, Yiwei Sun, Huaxiu Yao, Prasenjit Mitra, and Suhang Wang. Transferring robustness for graph neural network against poisoning attacks. In Proceedings of the 13th international conference on web search and data mining, pp. 600-608, 2020.
Pelar Veličković, Guillem Cucurull, Aranixa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Huijun Wu, Chen Wang, Yuriy Tyshetskiy, Andrew Docherty, Kai Lu, and Liming Zhu. Adversarial examples for graph data: Deep insights into attack and defense. In Proceedings of the Tweety--ighhd International Joint Conference on Arlificial Intelligence, IJCAI-19, pp. 0816-4823, 2019.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? Tn International Conference on Learning Representations, 2019.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hicrarchical graph representation learning with differentiable pooling. Advances in neural information processing systems, 31, 2018.
15

---

Published in Transactions on Machine Learning Research (September/2022 22024
Muhan Zhang and Yixin Chen. Link prediction based graph neural networks. Advances in newral informalion processing systems, 31, 2018.
Xiang Zhang and Marinka Zitnik. GNNGuard: Defending graph neural networks against adversarial allacks. Advances in neural information processing systems, 33:9263 9275, 2020.
Ziwei Zhang, Peng Cui, and Wenwu Zhu. Deep learning on graphs: survey. IEEE Transuctions on Knowledge and Data Engineering, 34(1):249 270, 2020.
Bingxin Zhou, Yuanhong Jiang, Yuguang Wang, Jingwei Liang, Junbin Gao, Shirui Pan, and Xiaoqun Zhang. Robust graph representation learning for local corruption recovery. In Proceedings of the ACM Web Conference 2023, pp. 438-448, 2023.
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications. AI open, 1:57-81, 2020.
Dingyuan Zhu, Ziwei Zhang, Peng Cui, and Wenwu Zhu. Robust graph convolutional networks against adversarial attacks. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 1399 1407, 2019.
Jiong Zhu, Junchen Jin, Michael T Schaub, and Danai Koutra. Improving robustness of graph neural networks with heterophily-inspiree designs. arXiv preprint arXiv:2106.07767, 3, 2021a.
Jiong Zhu, Junchen Jin, Donald Loveland, Michael T Schaub, and Danai Koutra. How does hetcrophily impact the robust ness of graph neural networks? theoretical connections and practical implications. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 2637-2647, 2022.
Yanqiao Zhu, Weizhi Xu, Jinghao Zhang, Qiang Liu, Shu Wu, and Liang Wang. Deep graph structure learning for robust representations: A survey. arXiv preprint arXim:2003.0300 14, 2021b.
Daniel Zügner and Stephan Günnemann. Adversarial attacks on graph neural networks via meta learning. The seventh International Conference Learning Representations, 2019.
Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks on neural networks for graph data. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & dala mining, pp. 2847 2856, 2018.
A Appendix
In this section, provide details about the datasets, different attacks considered, and additional results.
A.1 Dataset Details
We seven benchmark datascts, namely, Cora, Citescer, PubMed, OGBN-arXiv, OGBN-Produts, Chameleon, and Squirrel, to evaluate the efficacy of ARGS. Details about the datasets are summarized in Table 6, In the case of Cora, Citeseer, and PubMed, 10% of the data constitutes the train set, 10% of the data constitutes the validation set, while the test set is the remaining 80%. For Chameleon and Squirrel, we keep the same data split settings as Chien et al. 20200) For OGBN-ArXiv and OGEN-Products we follow the data split setting of the Open Graph Benchmark (OGB) (Hu et al. 2020).
A.2 Poisoning Attacks on GNNs
This section gives further details about the poisoning attacks introduced the paper. We consider different structure poisoning attacks to perturb the input graph. We recall the attacker's objective to find an optimal perturbed A' which results in degradation in the performance of the GNN model on the test data. Poisoning attacks be formulated bi-level optimization problems, shown in ( The Meta tackles the
16

---

Published in Transactions on Machine Learning Research (September/2022 20024
Table 6: Details on the datasets.
Datasets
Type
# #Nodss
#Edges
Classes
Features
Cora
Homophilic
2485
5069
1433
Citeseer
Homophilic
2110
3668
6
3703
PubMed
Homophilic
19717
44338
3
500
OGBN-ArXiv
Homophilic
169,343
1,166,243
40
128
CCGNN-Pooducss
Homophilic
2,449,029
61, 31,859,140 140
47
100
Chameleon
Heterophilic
2277
62792
2325
Squirrel
Heterophilic
5201
396846
2089
bi-level problem using meta-gradients (Bojchevski & Günnemann 2019 It treats the graph adjacency matrix a hyperparameter which is to be optimized such that Latk increases. The PGD attack (Xu et al. 2019) relaxes the discrete adjacency matrix A to continuous matrix in (0, 10,1 during the gradient-based optimization and optimizes its entries. The resulting adjustments to the matrix entries reflect the probability of an edge getting flipped. After each gradient update, the entries in the adjacency matrix are projected back such that the perturbations ions are within A. Out of the different perturbed adjacency matrices in ((A), the one which results in maximum Latk is chosen as the perturbed graph A'. Attacks like PGD and MetaAttack face scalability issues when extended to large graph datasets like OGBN-ArXiv and OGBN-Products. Inspired by the randomized block coordinate descent (RBCD), more scalable attacks have recently been developed, namely, the PR-BCD and GR-BCD attacks Geisler et al. (2021), where only subset of variables is optimized at time, and only the gradients of those variables are computed, resulting in lower memory requirements.
A.3 ARGS Implementation Details
We follow the setup used by UGS as our default setting (Chen et al. 2021 for ARGS, For Cora, Citeseer, and PubMed, we conduct all our experiments on two-layer GCN, GIN, and GAT networks with 512 hidden units. The graph sparsity Pg and model sparsity Po are 5% and 20% unless otherwise stated. The value of 3 is chosen from {0.01,0.1, 1, 10} while the value of a, Y, 7/, and Ç is 1 by default. We use the Adam optimizer for training the GNNs. In each pruning round, the number of epochs to update the masks is by default 200, using early stopping. The 2-layer MLP used for predicting the pseudo-labels of the test nodes has by default hidden dimension of 1024 unless otherwise mentioned. We use DeepRobust, an adversarial attack library (Li et al., 2020), to implement the PGD attack and the MetaAttack on the different datasets. We use Entorch-Geomettre (Fey & Lenssen 2019) to perform the PR-BCD and GR-BCD attacks on the OGBN-ArXiv and OGBN-Products datasets, respectively. All the experiments are conducted on an NVIDIA Tesla A100 (80-GB GPU).
For GCN, the values of X and A2 are both 10-2 for Cora and Citeseer, while for PubMed they are 10-6 and 10-3, respectively. The value of the learning rate is 8 x 10-3 3 and that of the weight decay is x 10-5 for the Cora dataset. For Citesecr and PubMed, the learning rate is 10-2 and the weight decay is 5 x 10 For the different datasets, we use a dropout of 0.5.
In the case of GIN, for the Cora dataset, the learning rate is 8 x 10-3, the weight decay is 8 x 10-5, \ is 10-3, 3 and A2 is 10-3, 3, For Citeseer, the learning rate is 10-2, the weight decay is 5 x 10-4, A is 10-5, and Ag is 10-5, For GAT, the case of the Cora dataset, the learning rate x 10-3, the weight decay is x 10-5, A is 10-3, A2 is 10-3, 3, and dropout is 0.6. Finally, for the Citescer datasct, the learning rate 10-2, the weight decay is 5 10-4, 4, A is 10-5, A2 is 10-3, and the dropout is 0.6.
We use DeeperGCN models for the OGBN-ArXiv and OGBN-Products datasets. In the case of ArXiv we use a 28-layer DeeperGCN model; for OGEN-Products, we use 14-layer DeeperGCN model. For OGBN-ArXiv, the learning rate is 10-2, X is 10-6, and X2 is 10-6, For OGBN-Produels, the learning rate is 10-3, >1 is 10 10-4, and Ag is 10-6, Droput is 0.5 for both the datasets. In the case of heterophilic graphs, we use GPRGNN as the backbone GNN. For the Chamelcon datasot, the learning rate
10-2 2 > is 10-3 3, > is 10-3, and dropout 0.4. For the Squirrel dataset, the learning rate is 5 x 10 2 A is 10 10-2, and dropout is 0.4.
Ag is
17

---

Published in Transactions on Machine Learning Research (September/2024)
84
Perturbation rate 5%%
Perturt at on rate 10%
52
Perburbation rate 15%
Accuracy coral
Mela/ttack
54
54
54
ABGS
ARGS
UGS
UGS
UGS
28
Basslnn (STRG)
26
Basdinc
26
fruring 6
9 cP 6
Graph Sparsity (95)
Graph Sparsity (9))
Graph (9)
Perturbation 5%
Perturbation rate 10%
Perturbation rate 15%
86
REcuracy (GON cora)
70
70
70
PGD Attack
56
56
56
42
42
ARGS
42
ARGS
28
28
(STRG)
Basatinc (STRG)
(STRG)
ARGLT
ARGIT
9 Graph Sparsity
Graph Sparsity
Graph Sparsity
Figure 9: Node classification performance over achieved graph sparsity levels for GCN on the Cora dataset attacked
by the PGD attack and MetaAttack. The perturbation rates are 5%, 10%, and 15%. Red stars * indicate the ARGLI' which achieve similar performance with high sparsity, STRG is used as the baseline.
Perturbation rate 5%
70
Perturb at on rate 10%
Perturbation rate 15%
Accurary (GCN chosoor)
1.4
06
54
Metahttack
52
54
52
40
ARGS
42
A8GS
40
ARGS
Ug5
JG5
USS
28
Bandom Pruring
30
Random Pruning
Random maning
Sassline (STRG)
Basoline (STR:)
Sasoline (STRG)
ARGIT
ARGIT
ARGLT
28
18
16
Graph Sparsity (%)
Graph Sparsity (5)
Graph Sparsity (%)
76
Perturbation rate 5%
76
Perturbation rate 10%
76
Portutation rate 15%
Accuracy citeseer)
66
64
PGD Attack
54
46
52-
42
ARGS
34-
ARGS
ARG5
US5
U9S
UGS
30
Random Pruning
20
Random Pruning
28
Randam Pruning
Banebin (STRC)
Beseins (STRC)
Bawiin (STRC))
ARGET
ARGLT
ARCLT
Graph Sparsity (9))
Graph Sparsity (%)
Graph Sparsity (%)
Figure 10: Node classification performance over achieved graph sparsity levels for GCN on the Citeseer dataset. attacked by the PGD attack and the MetaAttack. The perturbation rates are 5%, 10,, and 15%. Red stars indicate the ARGLTs which achieve similar performance as that of the baseline with high sparsity. STRG is used as the baseline.
A.4 Performance Evaluation of ARGS: Additional Results
We evaluate the performance of ARGS on homophilic graphs perturbed by the PGD atlack and MetaAUlack. We show the results for a 5%, 10%, and 15% perturbation rate for the Cora and Citeseer datasets in Figures g and I0 Figures 11 and show the performance of ARGS on the Cora and Citescer datascts with GIN as the backbone GNN. Finally, Figure 13 shows the performance of ARGS on Citesoer with GAT as the backbone GNN. Finally, we evaluate the performance of ARGS the PubMed dataset, shown in Figure 14
18

---

Published in Transactions on Machine Learning Research (September/2024)
Perturbation rate 5%
Perturbation rate 10%
Perturbation rate 15%
MetaArtack
(GIN
65
68
ARGS UGS
ARGS
ARGS
Random Pruning
Random Pruning
Random Pruning
Base (STRG)
Baseline (STRG)
Baseline (STRG)
48
50
2 8 6
Graph Sparsity (%)
Graph Sparsity (%)
Graph Sparsity (96
Perturbation
Perturbation rate 10%
Porturbation 15%
(GIN cora)
74
74
74
PGD Artack
68
67
67
ARGS
ARGS
ARGS
UGS
56
Random Pruning
Random Pruning
53
Random Pruning
Baseline (STRG)
Baseline (STAG)
ARGIT
ARGLT
ARGIT
50
46
46
99 2 2 2 6 6 Graph Sparsity (%)
Graph Sparsity (%)
Graph Sparsity (%)
Figure 11: Node classification performance over achieved graph sparsity levels for GIN on the Cora dataset attacked by the PGD attack and MetaAttack. The perturbation rates are 5%, 10,, and 15%. Red stars indicate the ARGLTs which achieve similar performance with high sparsity. STRG is used the baseline.
Perturbation
Perturbation rate
Perturbation rate
Accuracy (GIN citesee))
70
70
70
MetaAttack
ARGS
UGS
UGS
UGS
55
Random Pruning
55
Random Pruning (STRG)
55
Random Pruning (STRG)
Daseline (STRG)
ARGLT
ARGLT
ARGLT
Graph Sparsity (%)
Graph Sparsity
Graph Sparsity (%)
Perturbation rate 5%
Perturbation rate 10%
Perturbation rate 15%
77
75
75
(GIN citeseer)
PGD Attack
ARGS
60
ARGS
60
ARGS
UGS
UGS
UGS
57
Random Pruning
55
Random Pruning
55
Random Pruning
Baseline [STRG!
Baseline (STRG)
Daseline (STRG)
ARGLT
ARGUT
ARGLT
Graph Sparsity (%)
Graph Sparsity (%)
Graph Sparsity (%)
Figure 12: Node classifiatiio performance over achieved graph sparsity levels for GIN on the Citeseer dataset attacked by the PGD attack and the MetaAttack. The perturbation rates are 5%, 10%, and 15%. Red stars indicate the ARGLT's which achieve similar performance with high sparsity. STRG used as the baseline.
19

---

Published in Transactions on Machine Learning Research (September/202)
75
Perturtation rate 5%
75
Perturbation rate 10%
Perturbation rate 15%
citeseer)
01
61
58-
Meta/
Aocurac
MGS
ARS5
ARGS
47
Random Fruning
47
Random
42
Randam
9. 2
Graph Sparsity (9)
Graph Sparsit
Graph Sparstty
Perfurbation rate 5%
Perfurbation rate 10%
Perturbation 15%
Accuracy (GAT ctesser)
70
66
PGD Altack
15
54
30
44
Pruning (STRG)
Random Pruning
Random Pruning
Baselin (S
Baseine (TRG))
ARGIT
APOIT
ARGLT
38
32
22
Graph Sparsity (1)
Graph Sporsity (9)
Graph Sparsity (9)
Figure 13: Node classification performance over achieved graph sparsity levels for GAT the Citeseer dataset. attacked by the PGD attack and the MetaAttack. The perturbation rates are 5%, 10,, and 15%. Red stars * indicate the ARGLT's which achieve similar performance with high sparsity, STRG is used as the baseline.
GCN
Perturbation rate 5%
84
Perturbation rate 10%
86
Perturbation rate 15%
86
Perturbation rate 20%
Accuraty (pubmed)
75
77
75
PGD Atlack
ARGS
UGS
USS
UGS
UGS Baseline (STRG) ARGET
[STRG)
Baseline (STRG)
Baseline (STRC)
ARGUT
ARGUT
ARGUT
61
41
31
+
@
R
Graph Sparsity (%)
Graph Sparsity
(9)
Graph Sparsity (%)
Graph Sparsity (%)
Accuracy (putmed)
MetaAttack
67
58
58
43
ARGS
57-
ARGS
43
ARGS
43
ARGS
UGS
USS
UGS
UGS
Baswine [STRG)
Baselin (STRG)
Baveline (STRG)
28
Baneiin IS STRGI
ARGUT
ARGIT
ARGET
50
30
50
9
+
6
Graph Sparsity
Graph Sparsity
Graph Sparsity
Graph Sparsily (%)
Figure 14: Node classification performance over achieved graph sparsity levels for GCN on the PubMed dataset attacked by the PGD atlack and the MetaAktack. The perturbation rates are 5%, 10%, 15%, and 20%. Red stars x indicate the ARGLTs which achieve similar performance with high sparsity. STRG is used as the baseline.
A.5 Comparing the Impact of Node Attribute Features and Positional Features on ARGLTs for Homophilic Graphs
For homophilic graphs, we considered node attribute features for removing the adversarial edges, while node positional features were considered for heterophilic graphs. We then perform a set of experiments, where we instead consider positional features of the nodes in homophilic graphs. We observe that the overlap between the density distribution of positional feature differences for clean edges and that for adversarial edges higher when compared to the overlap between the density distributions of attribute features. However, the two density distributions of positional feature differences are still separable. The results reported in Table 7
20

---

Published in Transactions on Machine Learning Research (September/202) 20044)
Table ARGS performance comparison when positional and attribute features are considered the loss function for homophilic graphs in the Cora and Citeseer dalasets three different GNN models.
GCN
GIN
GAT
Dataset
Attack
Perturbation
Feature Type
Graph Spansity
Model Sparsity
Graph Spansity
Model Sparsity
Graph
Model
Sparsity
Spansity
Cora
PGD
5%
Attribute
49.2%
94.8%
58.3%
97.2%
64.2%
98.9%
Positional
46.0%
93.3%
58.3%
97.2%
64.2%
98.9%
10%
Attribute
48.3%
94.2%
46.0%
93.5%
64.3%
98.9%
Positional
37.2%
87.1%
40.1%
89.8%
64.3%
98.9%
15%
Attribute
49.1%
94.8%
53.7%
96.7%
64.2%
98.9%
Positional
37.2%
87.1%
18.5%
59.2%
64.3%
98.9%
Citeseer
Mettack
5%
Attribute
31.2%
79.4%
33.6%
83.6%
64.2%
98.9%
Positional
25.8%
74.2%
26.5%
74.2%
64.2%
98.9%
10%
Attrihute
33.6%
83.6%
64.2%
98.8%
64.2%
98.8%
Positional
33. 33.6%
83.6%
64.2%
98.8%
64.2%
98.8%
15%
Attribute
48.7%
94.8%
64.2%
98.8%
64.3%
98.8%
Positional
43.1%
91.9%
64.2%
98.8%
64.3%
98.8%
When positional features are considered, ARGS still able to find highly sparse GLTs, but the sparsity levels of the GLTs in some cases are lower than those obtained when attribute features are considered.
A.6 Further Ablation Study
We perform an ablation study verify the effectiveness of each component of the proposed loss function used for the sparsification algorithm. Part of this study is already included in the main sections of the paper We report the rost of the results in Table 8 In particular, present the analysis performed the Cora dataset for all the 3 different attacks with all the perturbation rales. We recall that configuration 1 corresponds to ARGS with all the loss components. As shown in Table g at both high and low target sparsity, we yield the best classification performance with configuration 1, showcasing the importance of all the components of the proposed loss function.
Table 8: Ablation study.
GCN, Cora, PGD Attack
Classification Accuracy at 5%
Classification Accuracy at Perturbation
Perturbation
Graph
Sparsity
Graph Sparsity 60.4% Model
Graph
Sparsity
Graph Spansity
Configuration
<
22.7% Model Sparsity
22.7% Model
60.4% Model 98.2%
Sparsity
Sparsity
Sparsity
67.7%
/
82.04
74.75
80.23
73.99
81.84
73. 64
79.98
68 81
81.69
74.45
76.86
72.89
79.28
71.33
74.70
63 63.48
Classlfication Accuracy Perturbation Rate 5%
Classification Accuracy Perturbation Rate 10%
GCN, Cora, Mettack Attack
Graph 22.7%
Sparsity
Graph Sparsity 62.3% Model Sparsity 98.6%
Graph
Sparsity
Graph Sparsity
Configuration
Ø
<
22.6% Model 67.5%
64.2% Model Sparsity 98.9%
Model 67.6%
Sparsity
Spareity
x
80.89
69. 91
78.17
70.98
79.58
71.33
75.40
66. 81
78.89
69.03
75.40
60.97
Classification Accuracy at Perturbation Hate 15%
Claesification Accuracy at
CCN, Cora, Mottack Attark
Perturbation
Graph 22.7% Model 67.6%
Sparsity
Graph Sparsity 60.4% Model
Graph
Sparsity
Graph Sparsity 60.3% Model Sparsity 98.2%
Configuration
B
22.6%
Sparsity
Sparsity
Model 67.5%.
Sparsity
/
/
/
80.73
75.91
79.38
70.37
73.60
77.97
72.74
75.50
69.16
x
78.42
72.08
74.09
68.86
21

---

Published in Transactions on Machine Learning Research (September/2024) 22024)
Table 9: Comparison between the performance ARGS and UGS with GCN, GIN, and GAT as backbone architectures on the clean Cora and Citescer datasets.
Dataset
Technique
Accuracy
Graph Sparsity
Model Sparsity
GCN
Cora
UGS
80%
26.52%
74.20%
ARGS
80%
40. 40.17%
89.48%
Citesecr
UGS
70%
64.56%
98.93%
ARGS
70%
64.27%
98.88%
GIN
UGS
79%
26.82%
73.93%
ARGS
79%
33.73%
83.33%
Citeseer
UGS
68%
66.05%
98.86%
ARGS
68%
64.27%
98. 88.8
GAT
UGS
80%
65.35%
98.91
ARGS
80%
64.32%
98.93%
Citeseer
UGS 70%
67.61%
98.86%
ARGS
70%
64. 64.24%
98.86%
A.7 Performance Evaluation of ARGS on Clean Graphs
We finally evaluate the performance of ARGS on clean graphs. shown Table g ARGS can still find highly sparse GLTs in clean graphs. The lottery tickets found by ARGS achieve similar model and graph sparsity level when compared to UGS for the same classification accuracy Cora and Citescer datasets across three different GNN models. We assume the accuracy of UGS at 0% graph and 0% model sparsity the baseline accuracy.
22


Reviews:
[{"review_id": "yh1QOhO7dT", "reviewer": "Reviewer_i6qx", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The paper provides a thorough analysis of the vulnerabilities of GLTs under various adversarial attacks, highlighting the need for improved robustness in graph neural networks.\n2. The proposed ARGS framework is a novel approach that effectively combines graph and model pruning to enhance adversarial robustness, making it a significant contribution to the field.\n\nWeakness:\n1. The ARGS framework involves a complex optimization process, which may impedes its application.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper investigates the resilience of Graph Lottery Tickets (GLTs) against adversarial attacks and proposes the Adversarially Robust Graph Sparsification (ARGS) framework to enhance their robustness. The paper first evaluates the vulnerability of GLTs identified by Unified Graph Sparsification (UGS) against various adversarial attacks. The results demonstrate that GLTs show a significant drop in classification accuracy under such attacks. The authors propose the ARGS framework, which prunes the graph adjacency matrix and GNN weights by optimizing a novel loss function that captures the graph homophily property and information from both true and pseudo labels. This framework iteratively refines the graph and model to achieve adversarial robustness. The paper compares the performance of ARGS with other state-of-the-art adversarial defense techniques like GNNGuard, GARNET, and ProGNN. The results indicate that ARGS achieves better accuracy and efficiency in terms of inference MACs, demonstrating its effectiveness in identifying highly sparse yet robust GLTs.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Provide efficiency analysis of the pruning method and compare with the baselines.", "broader_impact_concerns": "No broader impact concern.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "l4zSfCLqZC", "reviewer": "Reviewer_6wEC", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths.**\n\nThe paper appears to be the first to study the adversarial robustness of GLTs, finding that the standard sparsification algorithm (UGS) does not yield models that are inherently more robust to adversarial examples. The proposed approach (ARGS) appears to effectively present a way to find adversarially-robust GLTs (ARGLTs).\n\n**Weaknesses.**\n\nThe paper is fairly hard to follow for readers not 100% familiar with the literature of adversarial robustness of GNNs. It would be fairly important to carefully introduce the technical details behind the baselines (UGS, first of all, but also the working mechanisms behind the attacks employed in the experimental evaluation).\n\nOn the methodological side, the design of ARGS appears to be mostly inspired by analysing the behaviour of some poisoning attacks on a couple of datasets (Figure 3), and then taking steps to heuristically counter their effect. How can the authors make sure that such techniques and observations generalize to further datasets and further attacks? The fact some algorithm components (equations (4) and (5)) change depending on the type of the dataset is not a good sign in this regard.\n\nOn a related note, the empirical evaluations seem to be mostly carried out on attacks and datasets similar to those employed for the analysis of Figure 3. On some plots, such as Figure 6, the baseline appears to be fairly weak, as it is outperformed also by UGS (not an adversarial defense) for many sparsity levels. Perhaps this is linked to the fact that the attacks used for these plots are not adaptive (section 4.4), and hence do not attack the proposed defense directly. It would be very important to see plots such as Figure 6 or 8 against stronger/adaptive attacks.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors present a technique to find Graph Lottery Tickets (GLT, pairs of sparsified input graphs and GNN models performing as well as the original input-model pair, yet with significantly reduced inference time) that are adversarially robust to structural poisoning attacks.\nThe proposed approach (ARGS) is a heuristic defense, based on a series of terms encouraging the removal of adversarial structural modifications from the graph. \nExperiments showing that ARGS improves robustness to such attacks in practice on a series of benchmarks.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- More emphasis should be put on the fact that the proposed approach is designed for *poisoning* attacks, or experiments onto *evasion* attacks should be provided.\n- More technical details about the baselines (UGS, defenses, attacks) should be provided.\n- I missed how the perturbed A' (equation (7)) employed at training time is computed. These details should be clarified or given more prominence.\n- What is the difference between UGS, ARGS, and the employed baseline for sparsity=0? Why do both UGS and ARGS outperform the baseline even when sparsity=0? Is this linked to the use of pseudo-labels?\n- Adaptive and stronger attacks should be employed throughout the experimental evaluation.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "fVMo9djSoY", "reviewer": "Reviewer_a5P8", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "(+) The studied problem is new and seems to be interesting;\n\n(-) Most of the findings seem to be well-studied in the literature;\n\n(-) The presentation is confusing;\n\n(-) The experiments may not be sufficient;", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the adversarial robustness of graph lottery tickets. The authors investigate the resilience of GLTs against different structure perturbation attacks and observe that they are vulnerable and show a large drop in classification accuracy. Then they propose an adversarially robust graph sparsification (ARGS) framework that prunes the adjacency matrix and the GNN weights by optimizing a novel loss function capturing the graph homophily property and information associated with both the true labels of the train nodes and the pseudo labels of the test nodes. With extensive experiments, they verify that ARGS can find adversarially robust graph lottery tickets that are highly sparse yet achieve competitive performance under different training-time structure attacks.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. What is the surrogate model used to generate adversarial perturbations? \n\n2. What is the difference between the GLT setting and graph structure learning? For example [1].\n\n3. The derived findings from the experiments are already found in the existing literature, including [2,3,4]. The discussion of related works should properly differentiate the similarities and dissimilarities with existing works.\n\n4. What are the performances of the proposed method on clean graphs? \n\n5. The experiments of \n- Perturbation rates;\n- Scale of datasets;\n- GNN backbones;\n- Up-to-date graph lottery ticket methods;\n\nare all limited, making the generality of the conclusions suspected.\n\n**References**\n\n[1] Reliable Representations Make A Stronger Defender: Unsupervised Structure Refinement for Robust GNN, KDD'22.\n\n[2] How does Heterophily Impact the Robustness of Graph Neural Networks? Theoretical Connections and Practical Implications. KDD'22.\n\n[3] Understanding and Improving Graph Injection Attack by Promoting Unnoticeability, ICLR'22.\n\n[4] Revisiting graph adversarial attack and defense from a data distribution perspective. ICLR'23.", "broader_impact_concerns": "Could find any discussion of broader impacts.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: My understanding of the key contribution of this work is that it demonstrates the existence of adversarially robust graph lottery tickets and proposes a technique to identify such tickets. There is a consensus among the reviewers that this could be an interesting contribution. However, since the study proves this existence "empirically," the paper's evaluation needs to be comprehensive and extensive.

In this regard, one reviewer has expressed concern about the lack of evaluation of the proposed method against strong defense baselines. While I don't believe this work needs to be evaluated against the "strongest possible defenses," the reviewer's concern seems to be more about the evaluation configuration, which may have led to an unfair comparison.

I believe the reviewer's point is fair, and I believe it should be addressed during the minor revision process. Other than that, I could not foresee any other problems.
Decision: Accept (poster)