Mitigating Emergent Robustness Degradation while Scaling Graph Learning
Authors: Xiangchi Yuan
Chunhui Zhang
Yijun Tian
Yanfang Ye
Chuxu Zhang
Venue: ICLR 2024 poster (2024)
Keywords: Graph neural network
Primary area: learning on graphs and other geometries & topologies
TL;DR: When scaling up graph learning, we are the first to observe and then mitigate the emergent robustness degradation.

Abstract: Although graph neural networks have exhibited remarkable performance in various graph tasks, a significant concern is their vulnerability to adversarial attacks. Consequently, many defense methods have been proposed to alleviate the deleterious effects of adversarial attacks and learn robust graph representations. However, most of them are difficult to *simultaneously* avoid two major limitations: (i) an emergent and severe degradation in robustness when exposed to very intense attacks, and (ii) heavy computation complexity hinders them from scaling to large graphs. In response to these challenges, we introduce an innovative graph defense method for unpredictable real-world scenarios by *designing a graph robust learning framework that is resistant to robustness degradation* and *refraining from unscalable designs with heavy computation*: specifically, our method employs a denoising module, which eliminates edges that are associated with attacked nodes to reconstruct a cleaner graph; Then, it applies Mixture-of-Experts to select differentially private noises with varying magnitudes to counteract the hidden features attacked at different intensities toward robust predictions; Moreover, our overall design avoids the reliance on heavy adjacency matrix computations, such as SVD, thus facilitating its applicability even on large graphs. Comprehensive experiments have been conducted to demonstrate the anti-degraded robustness and scalability of our method, as compared to popular graph adversarial learning methods, under diverse attack intensities and various datasets of different sizes.

Published as a conference paper at ICLR 2024
MITIGATING EMERGENT ROBUSTNESS DEGRADATION WHILE SCALING GRAPH LEARNING
Xiangchi Yuan Chunhui Zhang? Yijum Tian Yanfang Ye
Chuxu Zhang'
Brandeis University, (xiangchiy yuan, Shuxuzhang)@brar inerrandeis.. .ddu 2 Dartmouth College, { (chunhui, zhang gr)@dartmouth. edu 3 University of Notre Dame, {yi jun. t tian, yye7]end.
ABSTRACT
While graph neural networks have exhibited remarkable performance in various graph tasks, a significant concern their vulnerability to adversarial attacks. Con- sequently, many defense methods have been proposed to alleviate the deleterious effects of adversarial attacks and learn robust graph representations. However, most of them are difficult to simultaneously avoid two major limitations: 1) an emergent and severe degradation in robustness when exposed to very intense attacks, and 2) heavy computation complexity hinders them from scaling to large graphs. In response to these challenges, we introduce an innovative graph defense method for unpredictable real-world scenarios by designing a graph robust learning frame- work that is resistant robustness degradation and refraining from the unscalable designs with heavy computation: specifically, our method employs a denoising module, which eliminates edges that are associated with attacked nodes to recon- struct a cleaner graph; Then, it applies Mixture-ot of- of-Experts to select differentially private noises with varying magnitudes counteract the hidden features attacked at different intensities toward robust predictions: Moreover, our overall design avoids the reliance on heavy adjacency matrix computations, such as SVD, thus facilitating its applicability even on large graphs. Comprehensive experiments have been conducted to demonstrate the anti-degraded robustness and scalability of our method, compared to popular graph adversarial learning methods, under diverse attack intensities and various datasets of different sizes.
INTRODUCTION
Graph Neural Networks (GNNs) are potent tools for learning relational data, excelling in tasks like node and graph classification (Kipf & Welling, 2017; Veličković al., 2018; Hamilton al., 2017; Ying et al., 2018; You et al., 2020; Guo et al., 2023b). They employ message- message-passing to iteratively update node representations by aggregating neighbor information. GNNs find widespread use, such as social media (Wu et al., 2022; Zhang al., 2022; Qian et al., 2022; Wen et al., 2022b; Li et al., 2023a), recommender systems (Huang et al., 2021; Tian et al., 2022; Fan et al., 2019; Ouyang et al., 2024, 2023), and molecular prediction (Jin et al., 2018; Guo et al., 2023a; Wang et al., 2023).
While GNNs have excelled in various tasks, they are vulnerable to adversarial attacks (Zügner & Günnemann, 2019; Zheng et al., 2021; Tian et al., 2023b; Zügner et al., 2018) that manipulate their performance through tactics like edge modifications (Geisler et al., 2021). node perturbations (Zügner & Günnemann, 2019; Sun al., 2020), or malicious node injections (Zou al., 2021). To address these vulnerabilities, several defense mechanisms have emerged, but they often face two significant challenges: 1) severe robustness degradation: many existing defense methods, such as RGCN (Zhu et al., 2019) and GNN-SVD (Entezari et al., 2020), effectively handle mild node injection attacks but experience an emergent decline in robustness as attack intensity increases. As shown in Figure when attack intensity surpasses a threshold of 300 injected nodes, error rates for many models surge by more than 50%. This limits their suitability for real-world scenarios (Goodfellow et al., 2015; Zheng et al., 2021; Madry et al., 2018; Zou et al., 2021). 2) limited scalability; scalability is notable concern, particularly for widely used methods like GNN-SVD (Entezari et al., 2020) and
Xiangchi is mentored by Chunhui; both contributed equally and are listed alphabetically by last name.

---

Published as a conference paper at ICLR 2024
GNNGuard (Zhang & Zitnik, 2020), which require dense adjacency matrix computations. This can result in substantial computational overhead, as shown in the experiment section, leading to oft-of-memory problems when applied to larger datasets like Flick, Reddit, and AMiner, especially when using a 32 GB GPU. These challenges necessitate innovative solutions to enhance the robustness and scalability of GNNs against adversarial attacks.
Therefore, we propose a novel framework called DRAGON (i.e., Differentially Private Masked Graph Auto-Encoder for Anti-degraded Robustness): To ad- dress (i) the emergent robustness degradation under increasing-in -nnrasing-intenstty graph attacks, DRAGON utilizes a denoise masked auto-encoder to reconstruct the given attacked graph towards cleaner node connec- tions, and further uses Mixture-of- off-Exsrtt Liu et (2023); Zhang et al. (2023c), which is specifically differential privacy-based, to eliminate the impact of injected nodes hidden in an attacked graph. For dealing with (ii) the limited scalability issue on large graph datasets, DRAGON avoids the heavy computa- tion of large adjacency matrices, which is achieved by making all designs not require large-scale adjacency matrices like GNNSVD (Entezari et al., 2020) and GNNGuard (Zhang& Zitnik, 2020), thereby we pre- vent out-of ment-ofmmooryy from occurring in our framework while scaling our framework to large graph datasets.
90
50
70
60
AccuracyP55
30
40
GNT
RGON
GUNSVD
IIGUNAI
DRAGON (Dun))
1001
200
500
4100
500
500
700
Attack Intersity on grb-cora injected nodes)
Figure 1: when FGSM attack intensity grb-Cora in- creasing, DRAGON outperforms other robust base- lines with negligible robustness degradation even under extreme-intensie attack.
The performance of different methods
The above effects are delivered in two steps: First,
given an attack graph as input, a masked graph auto-encoder applied to eliminate malicious edges connected to injected nodes, resulting in (nearly) clean graph with very few injected nodes connected to clean nodes; Second, we ensemble the differential privacy (DP) mechanism in each GNN layer, which introduces random noises into the graph features while counteracting the attacked node features and constraining the change of the model's output, thus against attack perturbations in injected nodes. Additionally, the Mixture-of offteer-of--xperts (MoEs) technique is used manipulate multiple DP expert networks, each holding Gaussian DP noise of different magnitudes. These expert networks are then assigned to injected node features attacked at different intensities, providing an appropriate level of noise to improve robustness. Our major contributions are summarized as follows:
Our solution, DRAGON framework, addresses both severe robustness degradation and scalability constraints in adversarial graph learning, Existing techniques often struggle with GNN scalability on large datasets and maintaining robustness against various attack intensities.
Our framework comprises two key components: denoise auto-encoder for cleaning attacked graphs by removing malicious edges connected to injected nodes and a differentially- private MoE that adapts the level of differential privacy noise counteract attacks of different intensities.
We extensively test DRAGON on diverse graph datasets and outperforms popular baselines, ensuring robustness in unpredictable real-world scenarios while preventing emergent phenomena severe robustness degradation.
attacks, where it
2 RELATED WORK
Graph Neural Networks. GNNs distinguish in various graph mining tasks (Hamilton al., 2017; Battaglia et al., 2018; Xu et al., 2019; Zhang et al., 2023b,a; Jia et al., 2024) due to their prowess in learning Eu--Fuulid data, Early GNN variants like GCN (Kipf & Welling, 2017; Gao et al., 2018; Wu et al., 2019a) introduced convolutional concepts to graph data. Subsequently, graph attention networks( networks(Veličkovic Veličkoviv et al., 2018; Wang et al., 2019) incorporated attention mechanisms. Moreover,
masked autoencoders (He al., 2022) found application in the graph domain (Li et al., 2023b; Tian et al., 2023a), inspiring our work in constructing clean graphs from attacked ones.
Adversarial Learning Graphs. Graph attacks disrupt structural semantic graph properties via connection manipulation (Du et al., 2017: Chen et al., 2018; Wanick et al., 2018), node feature perturbation (Zügnnr et al., 2018; Zügner & Günnemann, 2019; Sun et al., 2020; Zhang al., 2023c;
2

---

Published as a conference paper at ICLR 2024
Jia et al., 2023), malicious node insertion (Wang al., 2020; Zou et al., 2021). In response to these attacks, researchers have proposed a range of defense methods for GNNs. These include learning robust GNNs (Zhu al., 2019; Feng et al., 2020: Jin et al., 2020), adversarial training (Yue et al., 2022; Wen et al., 2022a; Zhang et al., 2023c), and removing attacked inputs during preprocessing (Entezari al., 2020; Zhang & Zitnik, 2020). However, two critical challenges persist: severe robustness degradation under intense attacks and limited scalability on large graph datasets. These inspire us to design the DRAGON framework to uniquely address both challenges.
PRELIMINARIES
Sparse Mixture-of-Experte The Mixture-of of of-EExerts (MoE) combines multiple models to make predictions by partitioning the input space and assigning experts to these partitions. Each expert specializes in a specific input subset, and their predictions are weighted and assembled using a gating mechanism. Given input space h and an MoE layer with N experts E = {E,())= the MoE output is: y Σi=1 (h),, where E, is an expert model, p.(h) is the expert's weight, typically determined by gating network.
N
Node Injection Attacks. In node injection attacks, malicious nodes are inserted into undirected attributed graph 9 = E X)) As GRB benchmark (Zheng et al., 2021) formally defined, the goal maximize the number of error predictions without modifying existing edges node features:
max arg max f(g") * arg max f(G)).
(I)
where g' = -V', "",""" and V includes malicious nodes. Constraints on E and X" limit edge changes and node feature modifications too.
Differential Privacy. Differential Privacy (DP) protects individual data during computations by adding randomness. It ensures that the output of function f(-) on neighboring datasets indis-
tinguishable. Formally, mechanism M is (e, d)diffferrnttially private if, for neighboring datasets D ~ D' and events in the output space O:
Pr[M (D) E O (M 6 5,
22)
with parameters and 5 controlling privacy strength and budget. For any a. 5 E (0, 1), the deviation of the classical Gaussian DP mechanism has the form / In( 1n 1.25/88/ (Dwork al., 2006; Balle & Wang, 2018; Dwork et al.. 2014). DP introduces noise to the function output, maintaining output consistency despite input perturbations, aligning with adversarial robustmess in deep learning.
METHODOLOGY
We introduce DRAGON for enhancing GNN robustness. Figure 2 depicts the framework's two key components: first, DMGAN serves an attacked graph preprocessing module, removing malicious edges linked to injected nodes, thus restoring a cleaner graph for the defender GNN; second, the framework combines the DP mechanism with GConv to form DP-GConv layer, enhancing the defense module. Given unpredictable attack intensities, we partition DP-GConv into multiple experts, each with varying DP noise magnitudes, enabling defense against attacks of varying strengths.
4.1 DENOISE MASKED GRAPH AUTO-ENCODER
Denoise Masked Graph Auto-Encoder (DMGAN) eliminates the negative influence of injected nodes by removing the malicious edges associated with the injected nodes. And its pipeline can be divided into three steps: masking the input (attacked) graph, encoding and decoding, and self-supervising.
Mask the Input Graph. Given an input graph G, we first adopt the widely used random walk (Perozzi et al., 2014) as path-masking strategy to mask the graph. We denote the masked subgraph as 9.. = (Vm. Em, ), and the visible subgraph as G. = (Vr. Ey, EY, where they complement each other, i.e., Gm J G.- G. To illustrate, the path masking strategy selects and masks multiple adjacent edges via random walk. This process is formulated as follows: &m ~ Random Walk() Vr, now Jw)) where V, C V is the set of root nodes, no and by represent the number of walks per node and the walk
3

---

Published as a conference paper at ICLR 2024
Overall Framework
injocted node
MLP Decnder
Defender DAN
CND
clean edge
injected odge
keep edge
remove odge
Attacked graph
Denoise MGAN (1)
Denoised graph
DP-MoE GNN (2)
Class A, B, o...
node representation:
Node classification
Denoise MGAN
Encoder
MLP Decnder
odge discrintinate: positive sepasivet
Cate
GNN
Dis.
Attacked graph
Encoded node representations
nond regredios 3,
Casa
Denoised graph
Learning objectives
(2) DP-MoE GNN
ZP Fopwort
OP Pxpsrr
Gote
Expert
Export
1-th Expert
Expert
Expert
TALL A
70)
nele
Spår
nith
Denoised graph
Splitted DPP MolE Layer
Figure 2: Our framework. First, (1) in Denoise MGAN, cleaner graph is recovered by removing the edges connected injected nodes, preventing their message- message-passing interactions with clean nodes. Second, the cleaner graph classified using (2) DPMoE GNN, which consists into multiple DP expert networks with adjustable noise coefficients to handle attacks different intensities.
graph convolutional layer split
lengths, respectively. By disrupting edges between sequence of adjacent nodes, the path masking strategy encourages the model to capture structured dependencies and high-order node proximities. This enables the model to subsequently reconstruct cleaner graph from the attacked one.
Generate the Clean Graph via Auto-Encoder. To construct a scalable DMGAN, we adopt GCN as the encoder and multilayer perceptrons (MLP) as the decoder. The decoder has dual purpose: reconstructing the graph structures and predicting node degrees.
demonstrate, we first obtain the encoded representations H obtained from the encoder for nodes V... Then, the decoder leverages the representations of pair of nodes as link representations to reconstruct the connections of the original graph. We use MLP to reconstruct the graph structure, and define the structure decoder as Dec,, with weight parameters w as follows: Dec., h4, h2) S (MLP(h, (h, o hyy ))) where denotes the element-wist product, h4 H and hy H are the representations of node and node j. respectively. Subsequently, to predict node degrees in the masked graph, we employ another MLP-based decoder for degree regression. We denote this Dec,, with weight parameters 6: Dec, (h,) MLP(h.). Here, h, corresponds to the representation of the target node E V., obtained through the previous encoder. This approach allows the DMGAN module learn the connection patterns of nodes in the original clean graph, aiding in the detection of malicious edges linked to injected nodes when the DMGAN module operates on the attacked graph.
Self-Supervised Loss for Denoise Auto-Encoder. The loss function for the decoder, responsible for both graph structure reconstruction and node degree regression, consists of two terms. First, a binary cross-entropy loss term is used to predict the edge for graph structure decoding:
L. =
log(Decw (hw, hv)) +
Σ (a','')E..
log(1 - Dec, (hwe, (hw,))r))
(3)
Eml
Eal
(u.
where h the node representation output from the encoder, En is a set of nonexistent negative edges sampled from training graph G. Second, regression loss term is applied measure how accurately the node degree prediction matches the original in the masked graph:
La
Σ BEV...
[Deec(hh)) deg(v))13
Pm
4

---

Published as a conference paper at ICLR 2024
where deg(-) and Vm denote the masked node degree and the masked nodes in the graph, respectively. The overall objective to be minimized during training is the combination of La and L.. After using the loss L to train the auto auto-encoder DMGAN, during attack evaluation, attacked graph g' = =V', E X') is perturbed from & and used as an input. Then decode the reconstructed edges of G' i.e.,& Ey. We use & to index the reconstructed subgraph G, from g, and then use G. for downstream tasks.
the trained DMGAN to
4.2 DEFENDER TO ATTACKS OF DIFFERENT INTENSITIES: DP-BASED MIXTURE OF EXPERTS
After cleaning the attacked graph with DMGAN, if any injected nodes remain in G. and negatively affect predictions, we deploy the DP mechanism in the Defender GNN for robust predictions on Gp. This involves introducing the DP mechanism into the GNN layer to create DP-GConv, which is further divided into DPMoE with different DP experts to handle various attack intensities.
Differentially-Priiaaet Private Graph Convolution. For tackling attacked graph outputs from DMGAN, introduce Differentially-Privee Private Graph Convolution DD-GGCnv). DP-GConv updates the representa- tion of target node, he (l-1), output by the (1 - 1)-th layer, in three steps:
First, a Gaussian differentially-private noise module M(.) computes Gaussian noise N, added he ( + nNV where μ is the scaling coefficient, and N follows /2 ln(1.25/6) Second,
to he (111), M(h
Gaussian distribution with mean zero and standard deviation M(n!-1) is multiplied by a learnable weight matrix W performed by the DPLinear(-)) module: DPLinear ( ( w()) M(hh-1)). This transformation is applied all neighboring nodes linked with the current target node. Third, after aggregating the features of all transformed neighbor- ing nodes, DP-G DP-GConv combines the feature of the target node and neighboring nodes, updating the target node representation from h (11 to (!)
h "COM(
(P AGG (DPLinear"(h!! Vu No))))
(5)
where A-G(.) and COM(-) represent neighbor aggregation and combination functions, respectively. No is the set of all neighboring nodes of node v.
In our implementation, the Gaussian DP noise module M(-) can be placed in front of DP-GConv's weight matrix, randomizing attack node features and constraining output results closer to predictions based on the original clean input, effectively neutralizing the influence of injected nodes.
To enhance the robustness of the defender GNN against node injection attacks of varying intensities, we introduce a novel approach known as Splitted Differentially-Privaae Private Mfxture-of-Expers (DPMoF).. This design divides each DP-GConv layer, denoted as DPLinear(.), into multiple expert networks. Each of these expert networks is equipped with a specific magnitude of Gaussian DP module, allowing the defender GNN effectively handle node injection attacks of differing strengths. The DPMoE module, which is split from DPLinear()). is formulated as follows:
Splitted Differentially-Priis Private Mixture-of-
DPMoF(()) = --Ee pc DPL,neer,
SET
where T represents the set of activated top-k expert indices. DPMoE(() combines the outputs of multiple DP expert networks, each with a different scaling coefficient 14 for the Gaussian DP noise N' at various magnitudes. Y4 increases linearly as the index of the expert increases. The top-k activated expert indices are determined by the gate values p: (h), which can be obtained using a softmax function as described below:
exp(t(h); +,,)
(h
ΣN Am exp(t(h,)x + +x))*
where ((-) denotes linear transformation, and N is the total number of experts. The activated expert indices in the DPMoE module are determined by gate values p. (h), which compute the activation probability of each expert. Logits are weighted by the i-th value t(h); of the linear transformation, and a random noise term E; is added to ensure randomness in the expert activation procedure. Typically, e is sampled from Gaussian distribution.
5

---

Published as a conference paper at ICLR 2024
To update the features of target node, the DPMcE layer combines feature transformation and aggregation operations. First, it transforms the features of the target node and its neighboring nodes using (PMoE( and then aggregates the transformed features of the neighboring nodes using AGG(.). The final representation of the target node is obtained by combining the transformed characteristic of the target node and the aggregated characteristic of its neighboring nodes:
k =COM (DPMoE (n!-")) AGG ((DPMoE")) O (M!-")) Vu E No xaa))
(8)
In comparison to the previous DP-GConv formulation in Equation (5), the proposed DPMoE layer employs a gating mechanism to control multiple experts, each equipped with multi-scale DP Gaussian noises. This allows it to effectively handle node injection attacks of varying intensities while maintaining higher anti-degraded robustness.
Theoretical Analysis of DPMoE Robustness. Let's denote is E KC the ground-truth class label for node ut 6, as two differential privacy parameters Gaussian DP mechanism; hi as the feature of node in layer / after aggregating from the injection nodes. When Equation (9) in Proposition is satisfied, we can theoretically ensure the robustness of the model.
Proposition 1. Robustness Guarantee for DPMoE. For GNN f(-) containing DPMoE which utilizes Gaussian DP. assume this mechanism lets the model output satisfy (a, (D.P If the expected value B of the model output satisfies the following property:
((fx(h
max B(fs(h.)) + +1+ Aie
(9)
then the label probability output vector p p(h! = (E(fi (,., satisfies the robustness: (ho 2 4 B(f((h)))) (1)
(hx))))) of f() for node v
This proposition sheds light on how upholding DP can bolster the model's robustness against adversarial perturbations. By adhering to the (c, 6)D constraints, the model's vulnerability to perturbations induced by adversarial injections is significantly reduced. The complete proof is in Appendix A.
In a brief proof sketch, we begin by confirming the (c, 5)DD) of a GNN model that solely consists of DP-GConv. Utilizing previous propositions and equations, the proof establishes bounds the model's expected outputs. These bounds are instrumental in deriving inequalities, which compare the expected output of the genuine class & to that of any other class under adversarial perturbations. By examining these inequalities, we uncover the necessary conditions for the model to maintain robustness speciiicils that the expected output for class significantly surpasses that of any other class. The proof then extends these findings to models incorporating DPMoE, demonstrating that if a DPMoE model meets the specified conditions, its robustness is established.
EXPERIMENTS
5.1 SETTINGS
Datasets. We evaluate the robustness and scalability of our proposed DRAGON framework using the Graph Robustness Benchmark (GRB) dataset (Zheng et al., 2021), which includes graphs of varying scales, such as grb-cora (small-scale), grb-citeseer (small-scale), grb-flickr (medium-scale)) grb-reddit (large-scale), and grb-aminer (large-scale). The statistics of the datasets are in Appendix C.
Baselines Methods. We evaluate the robustness of DRAGON against several baseline methods from two perspectives: First, for baselines that have been applied on robustness against injection attacks, we consider GCN-SVD (Entezari et al., 2020), GNNGuard (Zhang & Zitnik, 2020), RGCN (Zhu et al., 2019), EvenNet (Lei et al., 2022). Second, we compare against general GNN models (i.e., GCN (Kipf & Welling, 2017), GAT (Veličković et al., 2018)), RGCN (Zhu et al., 2019) and GAME (Zhang et al., 2023c) that are integrated with a generic defense approach, Adversarial Training (AT) (Madry et al., 2018). Configurations of all methods are included in Appendix C. In addition, many other graph robust learning methods such as Jaccard GCN (Wu et al., 2019b), SoftMedian (Geisler et al., 2021) and GARNET (Deng al., 2022) only effective for specific attacks with ad hoc designs, making the results less generalizable and practical, thus we do not include them as our primary baselines and compare them with DR DRAG in Appendix G.

---

Published as a conference paper at ICLR 2024
Table I: Overall assessments of all methods among five GRB datasets with different- inntensitiitetsttiy FGSM attacks. The best result is bolded and the runner-up is underlined. Inten. denotes Attack Intensity and OOM represents Mut-oo- MTt means integrating the method with adversarial training.
Inten.
GCN
GAT
RGCN
GCNSVD
GATGuard
EvenNet GCN-AT GAT+AT RGCN-AT GAME-AT
Ours
Qurs+AT
nulla
84.2
83.620..5
84.020.7
64.5+100
81.741.0
82.4
33.540.1
79.620.9
85.440.5
N5.5
14.1
81,640.77
65.623.2
58.9:4.2
5
44.1204
80.6+1.1
67.7=2.2
82.5+1.1
8
79.1+2.1
81.750.
84.2+0.6
82,0H0.2
Cora
II
$7.3+3.0
38.923.7
23.020.7
42.032.0
80.721.
53.3a2.1
79.610.8
79.2
72.824.6
80.120.7
84.140.3
81.64144
(smalt)
III
33.623.0
24.324.3
13.620.3
37,542.9
80.7+1.0
39.611.7
71.4+4.7
79.5=0.8
49.747.2
79.1
84.0:0.5
81.740.5
IV
17.9=0.8
1-2.5
12.0=0.1
3
1..+11.
28.9+088
47.9+3.9
78. 18.1
25.0+2.6
78, 18.3+022
84.0+0.3
81.009
V
12.4+0.1
14.3=1.6
11.9+0.1
33,040.
1..4+1.5
23.8+0.2
35.6+4.4
79.3=0.6
24.7+8.9
77.3+0.6
83.3+0.3
80,4+0.8
71.6+0.8
72.0=0.6
73.7+0.7
68.241.2
72,8+0,3
69.0+0.5
73.8+0.6
69.6
73,9+0,3
76.1+1.3
75.940.6
+0.1
37.926.5 19.4200.
62.4+2.
23.4
72.5.0.6
$7.3+2.3
59.742.9
69.2.0.7
71.
72.4
75.620.2
70.6
Citeseer
II
33.328.4
212.
45.925.
22.640.6
72.440.6
49.023.0
68.8:0.7
64.4114
69.310.9
74.7+0.3
70.420.7
(owal!)
III
1..8
19.743.8
35.1=39
21.7+2.0
72.540.6
36.843.1
27. 27.5
68.7=0.3
58.743.6
66.7+1.2
75.9.0.5
10.7
IV
16.2s1.0
19.615.6
31.455.1
19.411.8
72.440.6
28.611.9
63.64
68.720.3
51,942.8
64.640.3
75.610.5
70.3+1.0
21.024.0
13.5+4.7
32.7=2.4
14.6+1.0
72.5:0.6
24.0:3.3
26.7
68. 80.8
47.3
62. 62.8
70.6+1.1 75.3+0..3
mulla
47.1 50.0&1.2
50.820.7
OOM
OOM
49.020.6
45. 450.3
44.2+1.8
43.1
52.2+0.9
52.740.1
+0,1
39.6+0.9
47.8+2.6
48.2+1.0
O0M
M0O
48.240.7
340.8
44.1=2.1
40,3+4.6
6...1111
52.0+0.2
51 11.000.1
Flickr
II
30.620.1
44.1=3.9
43.7=2.
COM
O0M
45.1 44.3+1.2
44.0=2.4
40.0a2.8
43.0+1.4
51.8
50,3+0.0
(modiuu))
13.521.0
18.9225
NOM
MOO
37.2 27.147.6
43.113.1
45,923.6
41.111.1
51.2+1.5
TO 820.0
IV
9.62:0.3
24.529.6
12.6213
COM
O0M
29.5#3.4
15.242.7
42.8:3.5
43.5=112
40.8+0.9
50.3+1.8
78.7
9.120.1
24.929.8
15.7a4.5
0OM
OOM
26.9a3.8
14.445.6
42.424.1
43.8&1..5
38.4
48.8
47.540.1
mulla
95.6+0.0
95.8+0.0
95.5+0.1
OOM
OOO
95.1+0.0
95, 65.60
95.4=0.0
95.740.0
96. 96.1+0.0
96.2+0.0
95.7+0.0
95.6 =0.1
95.4
93.0=0.1
COM
WOO
OOO
95,0=0.1
4+0.1
95.4
93.240.D
95.3
96.10..0
95.640.1
Reddit
II
94.720.0
95.220.2
851
O0M
MOO
94.920.2
95. 110.0 45.420.1
85.0g0.3
95.120.1
16.0
95.640..
(lorge)
III
93.6+0.1
94.2=0.1
75.4+14
COM
O0M
93.8+0.2
94, 4+0.2
95.3=0.0
72.0+0.1
94,8+0.0
96.02..0
95.5+0.0
91.720.3
93
59.1=10
OOM
MOO
93.720.1
93, 23.3. 95.2.001
51.540.1
95.910.1
55.5
V
88.620.1
120.5
49.6213
OOM
0OM
93.2+0.1
88. 910.2
95.2=0.0
42.840.0
93.0+0.1
95.8 25.8
95.5+0.1
63.4s0.1
66.8=0.7
63.6=0.2
OOM
OOM
62.7+0.0
1+0.0 63.9=0.0
64.4+0.2
64 64.540.2
64.340.8
64.340.0
61.0=0.5
59.3=0.3
51.2+0.6
OOM
00M
61 61.0=0.2
62. 7+0.0
63.8=002
61.0+1.0
63.0H0.1
61.7+0.5
64.1
AMiner
II
51.2+0.3
46.9=1.0
32.6+0.3
OOM
OOM
52.3+0.1 57.4+0.0
63.4=0.1
50.642.22
62.1
56.140.2
63.7+0.1
(large)
III
39.320.1
35.6210.8
21 920.3
OOM
0OM
42.720.0 48.640.0
62.7.0.0
38.3+1.2
60.8
090.00..4
63.1+9.1
IV
32.2s1.2
30.2=2.5
16.51=12
OOM
0OM
32.2a0.1 41.340.0
62.1=0.1
31.020.7
38.610.2
42.540.3
62.620.3
24.5
23.8=2.3
13.0=0.9
0OM
00M
26.3a0.2
32.4+0.0
61.1.0.3
22.0+2.3
56.7a0.3
49.7a0.2
62.0+0.5
Attack Strategies. In this section, we examine five effective and distinct graph injection attack methods, including FGSM (Goodfellow et al., 2015), SPEIT (Zheng et al., 2020), PGD (Madry et al., 2018), TDGIA (Zou et al., 2021), HAO (Chen et al., 2022), that can degrade the performance of victim GNNs, including our proposed DRAGON framework and other baselines. Note that we focus primarily injection attacks, which have received considerable attention due to their ease of deployment and cost-effecttvennes compared to modifying the original graph input.
In configuring attack strategies, we maintain consistency with the default GRB configuration, varying attack intensities by multiplying the number of injected nodes to create five intensities from to 5 as detailed in Appendix C.I, while keeping hyperparameters consistent with GRB for generating attacks and surrogate models, with additional specifics in Appendix C.2. The code can be accessed through https: / thub. com/ chmmmmihuniiiiii zng/ / ewwegeetteteeeeeeeeeeeeeeeeee degpeeentddgrdddaaiioiooo
5.2 OVERALL ROBUSTNESS AND SCALABILITY ON GRB
We first assess DRAGON's 's robustness and scalability, comparing it against state-of-the-as (SOTA) baseline methods. Results are summarized in Table Table reveals DRAGON's comprehensive superiority over other baselines in terms of robust accuracy across five distinct attack intensities (ranging from I to V). Additionally, DRAGON achieves these results without encountering out-of- memory issues while handling five graph datasets of varying scales on the same hardware platform.
Specifically. with regards to anti-degraded robustness, DRAGON demonstrates consistent and im- pressive robust accuracy under five different attack intensities among various datasets, while other baseline methods, including robust GNNs, adversarial trained GNNs, and general GNNs, experience severe degradation in robustness as the attack intensity increases. For instance, on the scall-scale grb-citeseer dataset, DRAGON outperforms the most competitive baseline GAME+AT by 3.2% when the attack intensity is I and by 12.5% when the attack intensity increases to V: On the medium grb-flickr dataset, compared to the most competitive baseline GAME+AT, DRAGON outperforms this baseline by 6.4% when the attack intensity is I and by 10.4% when the attack intensity increases to V; On the large grb-reddit dataset, DRAGON outperforms the most competitive bascline, GAT+AT, by 0.7% when the attack intensity is / and by 0.6% when the attack intensity increases to V; In addition,
7

---

Published as a conference paper at ICLR 2024
DRAGON also demonstrates strong representation ability on clean graphs and outperforms other baselines in the nulla (i.e., without attack) setting. Moreover, some baseline methods, such as GCNSVD and GATGuard, struggle with GPU memory limitations due to their reliance on heavy computation complexity and run into out-of-memory problems on medium and large datasets, unlike DRAGON, which shows reliable scalability. We note that DRAGON exhibits relatively lower robustness on the AMiner dataset and we provide the explanation in Appendix B.
5.3 ABLATION STUDY
We examine the contributions of DRAGON'S individual components, namely the denoising preprocessing component (DMGAN) and the defender component (DPMoE), we perform ablation experiments. We systematically re- move each component to observe its impact on DRAGON's performance. The ablated models are denoted as: (a) without denoise, (b) without DPMGE, and (c) the GNN backbone, represent- ing the base model without both denoise and DPMoF, shown in Table 2 (a fine-grained ablation study on DMGAN is in Appendix D).
Table 2: Ablation studies for DRAGON on graphs of varying scales and under FGSM attack of varying inten- sities. Base model denotes backbone w.o. DRAGON.
Int.
Base model w.o. denoise w.o. DPMcE DRAGON
nulla
83,1
84,2+0,2
83,9=0.6
10,1
81 81.644.2
84.1+1.3
81.8+1.4
84,2+0.4
Cora (smalf)
80.713.7
83.911.9
80.910.8
84.1:1.6
III
79.7+4.3
83,9+3.7
80.1
84.0=2.0
IV
76.4+2.5
83.5+1.3
77.0+1.6
84.0=1.3
V
75.241.6
83.012.1
76.112.3
83.3+2.9
nulla
74.1
76.0+0.5
75.8+0.3
75.920.5
73.4+0.6
75.5+3.1
73.5+1.1
75.6+1.88
Our experiments reveal that removing any ponent from DRAGON leads to decreased per- formance in node injection attacks, particularly as the attack intensity increases. This empha- sizes the critical role each component plays in enhancing the model's robustness and providing anti anti-degraded robustness:
Citeseer II
72.7+2.5
75.6+0..7
72.9+2.0
74.7=2.1
(amall)
III
71.31:3.8
75.743.5
71.711.2
15.9
IV
70.5+5.6
75.4+2.5
70.8+2.7
75.6+0.7
69.6+4.7
75.0+2.4
71.1+3.2
75.3+2.4
nulla
66.810.1
66.340.1
64.840.0
64.3
59.3+0.5
61.7+0.4
60.9+0.8
61.7=0.5
AMiner II
46.910.3
52.410.7
51,910.2
56.120.2
(large)
III
35.6+4..1
42,4+1.7
40,9+0.4
49.020.4
IV
30.1=1.2
34.0+0.5
34.6+0.3
42.5+0.3
V
23.840.7
26.542.2
28.140.9
39.720.2
For (a) w.o. denoise, eliminating the DMGAN component significantly impairs DRAGON'S ability to recover clean graph information from an attacked graph input. For instance, on the small grb-cora dataset, the model experiences a 0. 1% loss in accuracy at attack intensity of I and 0.3% loss at intensity of V. This illustrates that a cleaner graph reconstructed by DMGAN is easier for defense. For (b) w.o. DPMoE, disabling the DPMoE component entirely hinders DRAGS''s capacity to manipulate Gaussian DP noises of varying magnitudes to counteract attacks of different intensities. On the grb-citeseer, the removal of this component results in 2.1% % loss in accuracy an attack intensity of I and 4.2% loss intensity of V. This demonstrates that DPMoE enhances the robustness of GNNs against adversarial node injections of varying strengths by providing diverse yet effective Gaussian DP noises. Finally, for (c) w.o. denoise and DPMOE, removing both components reduces DRAGON to a vanilla GAT model. On the larger grb-aminer, this leads 2.5% increase in accuracy at an attack intensity of and 15.9% loss at an intensity of V.
Above results highlight the effectiveness of DRAGON in denoising and enhancing a base model's capacity to learn robust representations against attacks of different intensities.
5.4 WHAT WINS ANTI-DEGRADED ROBUSTNESS?
We investigate the denoising module (DGMGAN) in recovering attacked graphs and the capability of the defender component (DPMoH) in manipulating the magnitude of the Gaussian Differential Privacy mechanisms and analyze how they improve DRAGON's amti-degradation robustness.
Denoising Injected Nodes by DMGAN. To gauge the effectiveness of DMGAN in DRAGON, we visually compare the attacked graph input with the denoised version produced by DMGAN in Figure 3, and specific statistics for this edge denoising process are listed in Appendix D. The results illustrate that as the attack intensity increases, DMGAN continues to efficiently remove numerous malicious edges associated with injected nodes. This reduction in the negative impact of the attack showcases DMGAN's robustness against node injection attacks of varying intensities.
8

---

Published as a conference paper at ICLR 2024
Before delving into the DPMcE design, it is crucial to acknowledge that relying solely the DP mechanism within standard GNN backbone, without MoE, poses challenges strik- ing balance between performance in attack and non-attack scenarios. As shown in Fig- ure 4, models with higher DP scaling coefficients display flatter performance curves, indicat- ing robustness in high-intensity attack scenarios but reduced accuracy in non-attack scenarios.
Effectiveness of DPMoE. To attain a more fa- vorable trade-off between non-attack and attack scenarios of varying intensity. DPMoE intro- duced to dynamically balance these scenarios. This is achieved by employing multiple experts that integrate DP scaling coefficients of varying magnitudes. Such an approach allows the activa- tion of the appropriate expert network with the corresponding DP scaling coefficient, yielding an (more) optimal solution for both non-attack and varying- iittgnittnssty attack scenarios: (i) in non-attack scenarios, DPMoE activates the pert with minimal DP noise; (ii) as attack inten- sity increases, it activates the expert with larger DP noise magnitudes. This adaptive adjustment of the DP scaling coefficient by DPMoE for non-attack and terying-intensiee attack inputs results impressive performance under varying- intensity attack evaluations and non-attack eval-
A graphh
Denoised graph
Attack Intensity
Attack Intensity V
The visualization of sampled Cora graph at attack intensity and V and their DMGAN-denoid version. The black edges denote normal edges and the red edges represent malicious edges.
Figure 3:
uations.
In addition to the above experi- ments, we present more comprehen- sive findings and clarifications, in-
90
84
80
82-
cluding evaluations against SPEIT, PGD, TDGIA, and HAO attacks,
70
60
Accuracy
80
in Appendix B. Appendix eluci- dates all dataset and attack strategy settings. Further insight into the trade-offs within the denoise mod- ule is offered in Appendix D. Ad- ditionally, Appendix and delve into discussions about GNNs under modification and adaptive attacks, although these discussions slightly extend beyond the scope of this pa-
50
ratc-0.1
78
rate-0.2
rate-0
OF ratemo.4
DP ratenD.3
DP ratemo.s
DP r0ta
DR-MoE
OR-MGE
10 100 200 300 400 s00 Attack Intensity (# injected nodes)
600
700
72
100 200 300 400 s00 600 700
Attack Intensity injected nodes)
Figure 4: Different DP rates (scaling coefficients) on DRAGON w. single DP rate and multiple DP rates via DPMoE using standard training (left) and adversarial training (right) Cora dataset.
per, explained in the appendix. Detailed analyses demonstrating method's linear time and memory complexities, contributing to its scalability and efficiency, can be found Appendix H. Furthermore, the realistic importance of considering high-intensity graph attacks in the real world is discussed in Appendix
CONCLUSION
We begin by identifying two practical issues: severe robustness degradation and limited scalability in current adversarial graph learning. Then address them simultaneously, propose novel framework named DRAGON by utilizing denoising masked graph auto-encoder and differential privacy mechanism. Our experimental results show the effectiveness of DRAGON in denoising malicious edges, counteracting the injected attack node features through differential privacy, and navigating graph data of varying scales and attacks of different intensities. Overall, DRAGON is robust and scalable solution for avoiding GNN's emergent robustness degradation in unpredictable real-world applications.

---

Published as a conference paper at ICLR 2024
ETHICS STATEMENTS
We emphasize the critical importance of considering high-intensity graph attacks and the emergent severe robustness degradation, which is bitter lesson from unpredictable real-world scenarios. We discuss this in detail in Appendix I. Therefore, we improve the robustness of GNNs with respect to severe robustness degradation, ensuring their effectiveness against adversarial attacks even in high-intensity scenarios and with large graph datasets.
Furthermore, advances in graph adversarial learning may lead to potential vulnerabilities in GNNs. Therefore, it is imperative to develop robust graph defense methods and advocate for responsible GNN deployment and management. Our novel defense framework, DRAGON, paves the way for future research on trustworthy graph learning. We emphasize the need for comprehensive strategies to address possible implications and threats in future research and applications.
ACKNOWLEDGMENTS
This work was partially supported by Dartmouth, the NSF under grants IIS IIS-2321 2341 IIS 1I3-233,,9,, IIS- 2203262, IIS-2217239, CNS-2203261, IIS-2340346, and CMMI-214600 Any opinions, findings, conclusions, or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the sponsors.
REFERENCES
Borja Balle and Yu-Xiang Wang. Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. In ICML., 2018.
Peter W Battaglia, Jessica B Hamrick, Vietor Bapst, Alvaro Sanchez-Gonzaler Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint meo::000600000 2018.
Jinyin Chen, Yangyang Wu, Xuanheng Xu, Yixian Chen, Haibin Zheng, and Qi Xuan. Fast gradient attack on network embedding. arXiv preprint arXiv:1809.022 2018.
Yongqiang Chen, Han Yang, Yonggang Zhang, Kaili Ma, Tongliang Liu, Bo Han, and James Cheng. Understanding and improving graph injection attack by promoting unnoticeability. In ICLR, 2022.
Chenhui Deng, Xiuyu Li, Zhuo Feng, and Zhiru Zhang. Garnet: Reduced-rank topology learning for robust and scalable graph neural networks. In LoG, 2022.
Jian Du, Shanghang Zhang, Guanhang Wu, José MF Moura, and Soummya Kar. Topology adaptive graph convolutional networks. arXiv preprint arXiv: 10370, 2017.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryplography Conference, 2006.
Cynthia Dwork, Aaron Roth, al. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 2014.
Negin Entezari, Saba A Al-Sayouri, Amirali Darvishzadeh, and Evangelos E Papalexakis. All you need low (rank) defending against adversarial attacks graphs. In WSDM, 2020.
Wenqi Fan, Yao Ma, Qing Li, Yuan Hc, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In The Web Conference, 2019.
Wenzheng Feng, Jie Zhang, Yuxiao Dong, Yu Han, Huanbo Luan, Qian Xu, Qiang Yang, Evgeny Kharlamov, and Jie Tang. Graph random neural networks for cemi-supervised learning on graphs. In NewrlPS, 2020.
Hongyang Gao, Zhengyang Wang, and Shuiwang Ji. Large-scale learnable graph convolutional networks. In KDD, 2018.
10

---

Published as a conference paper at ICLR 2024
Simon Geisler, Tobias Schmidt, Hakan Sirin, Daniel Zügner, Aleksandar Bojchevski, and Stephan Günnemann. Robustness of graph neural networks at scale. In NeurIPS, 2021.
lan Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In ICLR, 2015.
Zhichun Guo, Kehan Guo, Bozhao Nan, Yijun Tian, Roshni G Tyer, Yihong Ma, Olaf Wiest, Xian- gliang Zhang, Wei Wang, Chuxu Zhang, et al. Graph-based molecular representation learning. In IJCAI, 2023a.
Zhichun Guo, Chunhui Zhang, Yujie Fan, Yijun Tian, Chuxu Zhang, and Nitesh V. Chawla. Boosting graph neural networks via adaptive knowledge distillation. In AAAI, 2023b.
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NeurIPS, 2017.
Kaiming He, Xinlei Chen, Saining Xie, Yanghao Li, Piotr Dollár, and Ross Girshick. Masked autoencoders are scalable vision learners. In CVPR, 2022.
Tinglin Huang, Yuxiao Dong, Ming Ding, Zhen Yang, Wenzheng Feng, Xinyu Wang, and Jie Tang. Mixgef: An improved training method for graph neural network-based recommender systems. In KDD, 2021.
Yaning Jia, Dongmian Zou, Hongfei Wang, and Hai Jin. Enhancing node-level adversarial defenses by lipschitz regularization of graph neural networks. SIGKDD, 2023.
Yaning Jia, Chunhui Zhang, and Soroush Vosoughi. Aligning relational learning with lipschitz fairness. In ICLR, 2024.
Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. In KDD, 2020.
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. In ICMI,, 2018.
Thomas N. Kipf and Max Welling. Semi-super classification with graph convolutional networks. In ICLR, 2017.
Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness adversarial examples with differential privacy. In IEEE Symposium on Security and Privacy, 2019.
Runlin Lei, WANG Zhen, Yaliang Li, Bolin Ding, and Zhewei Wei. Evennet: Ignoring odd-hop neighbors improves robustness of graph neural networks. In NeurIPS, 2022.
Jiazheng Li, Chunhui Zhang, and Chuxu Zhang. Heterogeneous temporal graph neural network
explainer. In CIKM, 2023a.
Jintang Li, Ruofan Wu, Wangbin Sun, Liang Chen, Sheng Tian, Liang Zhu, Changhua Meng, Zibin Zheng, and Weiqiang Wang. What's behind the mask: Understanding masked graph modeling for graph autoencoders. In KDD, 2023b.
Yixin Liu, Zhao Li, Shirui Pan, Chen Gong, Chuan Zhou, and George Karypis. Anomaly detection on attributed networks via contrastive self-supervised learning. IEEE Transuctions on Neural Networks and Learning Systems, 2021.
Zheyuan Liu, Chunhui Zhang, Yijun Tian, Erchi Zhang, Chao Huang, Yanfang Ye, and Chuxu Zhang, Fair graph representation learning via diverse mixture-of-experts. In The Web Conference, 2023.
Zheyuan Liu, Guangyao Dou, Yijun Tian, Chunhui Zhang, Eli Chien, and Ziwei Zhu. Breaking the trilemma of privacy, utility, and efficiency via controllable machine unlearning. In The Web Conference, 2024.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant adversarial attacks. In ICLR, 2018.
11

---

Published as a conference paper at ICLR 2024
Felix Mujkanovic, Simon Geisler, Stephan Günnemann, and Aleksandar Bojchevski. Are defenses for graph neural networks robust? In Neur!PS, 2022.
Zhongyu Ouyang, Shifu Hou, Shang Ma, Chaoran Chen, Chunhui Zhang, Toby Li, Xusheng Xiao, Chuxu Zhang, and Yanfang Ye. Prompt learning unlocked for app promotion in the wild. In NeurlPS 2023 Workshop: New Frontiers in Graph Learning, 2023.
Zhongyu Ouyang, Chunhui Zhang, Shifu Hou, Chuxu Zhang, and Yanfang Ye. How to improve representation alignment and uniformity in graph-based collaborative filtering? In International AAAI Conference on Web and Social Media, 2024.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representa- tions. In KDD, 2014.
Yiyue Qian, Chunhui Zhang, Yiming Zhang, Qianlong Wen, Yanfang Ye, and Chuxu Zhang. Co- modality graph contrastive learning for imbalanced node classification. NeurlPS, 2022.
Yiwei Sun, Suhang Wang. Xianfeng Tang, Tsung-Yo Yu Hsich, and Vasant Honavar. Adversarial attacks on graph neural networks via node injections: A hierarchical reinforcement learning approach. In The Web Conference, 2020.
Shuchang Tao, Qi Cao, Huawei Shen, Junjie Huang, Yunfan Wu, and Xueqi Cheng. Single node injection attack against graph neural networks. In CIKM, 2021.
Yijun Tian, Chuxu Zhang, Zhichun Guo, Chao Huang, Ronald Metoyer, and Nitesh V. Chawla. Reciperec: heterogeneous graph learning model for recipe recommendation. In ICCI,, 2022.
Yijun Tian, Kaiwen Dong, Chunhui Zhang, Chuxu Zhang, and Nitesh V Chawla. Heterogeneous graph masked autoencoders. In AAAI, 2023a.
Yijun Tian, Chuxu Zhang, Zhichun Guo, Xiangliang Zhang, and Nitesh V Chawla. Learning mips on graphs: A unified view effectiveness, robustness, and efficiency. In ICLR, 2023b.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
Soroush Vosoughi, Prashanth Vijayaraghavan, and Deb Roy. Tweet2vec: Learning tweet embeddings using character-level cnn-lstm encoder-decoder. In ACM SIGIR, 2016.
Soroush Vosoughi, Mostafa 'Neo' Mohsenvand, and Deb Roy. Rumor gauge: Predicting the veracity of rumors on twitter. ACM Transactions on Knowledge Discovery from Data, 2017.
Soroush Vosoughi, Deb Roy, and Sinan Aral. The spread of true and false news online. Science, 2018.
Jihong Wang, Minnan Luo, Fnu Suya, Jundong Li, Zijiang Yang, and Qinghua Zheng. Scalable attack graph data by injecting vicious nodes. Data Mining and Knowledge Discovery, 2020.
Wenjie Wang, Pengfei Tang, Jian Lou, and Li Xiong. Certified robustness to word substitution attack with differential privacy. In NAACI, 2021.
Xiang Wang, Xiangnan He, Yixin Cao, Meng Liu, and Tat-Seng Chua. Kgat: Knowledge graph attention network for recommendation. In KDD, 2019.
Yifei Wang, Shiyang Chen, Guobin Chen, Ethan Shurberg, Hang Liu, and Pengyu Hong. Motif-based graph representation learning with application to chemical molecules. In Informatics, 2023.
Marcin Waniek, Tomasz P Michalak, Michael J Wooldridge, and Talal Rahwan. Hiding individuals and communities in a social network. Nature Human Behaviour, 2018.
Qianlong Wen, Zhongyu Ouyang, Chunhui Zhang, Yiyue Qian, Yanfang Ye, and Chuxu Zhang. Graph contrastive learning with cross-view reconstruction. In NeurIPS 2022 Workshop: New Frontiers in Graph Learning, 2022a.
12

---

Published as a conference paper at ICLR 2024
Qianlong Wen, Zhongyu Ouyang, Jianfei Zhang, Yiyue Qian, Yanfang Ye, and Chuxu Zhang. Disentangled dynamic heterogencous graph learning for opioid overdose prediction. In SIGKDD, 2022b.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplify- ing graph convolutional networks. In ICML, 2019a.
Huijun Wu, Chen Wang, Yuriy Tyshetskiy, Andrew Docherty, Kai Lu, and Liming Zhu. Adversarial examples on graph data: Deep insights into attack and defense. In IJCAI, 2019b.
Jiele Wu, Chunhui Zhang, Zheyuan Liu, Erchi Zhang, Steven Wilson, and Chuxu Zhang. Graphbert: Bridging graph and text for malicious behavior detection social media. In ICDM, 2022.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? In ICLR, 2019.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. NeurIPS, 2018.
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. In NeurlPS, 2020.
Han Yue, Chunhui Zhang, Chuxu Zhang, and Hongfu Liu. Label-invariant augmentation for semi- supervised graph classification. In NeurlPS, 2022.
Chunhui Zhang, Chao Huang, Youbuan Li, Xiangliang Zhang, Yanfang Ye, and Chuxu Zhang. Look twice as much as you say: Scene graph contrastive learning for self-supervised image caption generation. In CIKM, 2022.
Chunhui Zhang, Chao Huang. Yijun Tian, Qianlong Wen, Zhongyu Ouyang, Youhuan Li, Yanfang Yc, and Chuxu Zhang. When sparsity meets contrastive models: Less graph data can bring better Alass-balancedd representations. In ICML., 2023a.
Chunhui Zhang, Hongfu Liu, Jundong Li, Yanfang Ye, and Chuxu Zhang. Mind the gap: Mitigating the distribution gap in graph few-shot learning. Transactions on Machine Learning Research, 2023b.
Chunhui Zhang, Yijun Tian, Mingxuan Ju, Zheyuan Liu, Yanfang Ye, Nitesh Chawla, and Chuxu Zhang. Chasing all-round graph representation robustness: Model, training, and optimization. In ICLR, 2023c.
Xiang Zhang and Marinka Zitikk. Gnnguard: Defending graph neural networks against adversarial attacks. In NeurIPS, 2020.
Qinkai Zheng, Yixiao Fei, Yanhao Li, Minhao Hu Qingmin Liu, and Qibo Sun. KDD CUP 2020 ML Track Adversarial Attacks and Defense on Academic Graph 1st Place Solution, 2020.
Qinkai Zheng, Xu Zou, Yuxiao Dong, Yukuo Cen, Da Yin, Jiarong Xu, Yang Yang, and Jie Tang. Graph robustness benchmark: Benchmarking the adversarial robustness of graph machine learning. In NewrIPS on Datasets and Benchmarks, 2021.
Dingyuan Zhu, Ziwei Zhang, Peng Cui, and Wenwu Zhu. Robust graph convolutional networks against adversarial attacks. In KDD, 2019.
Xu Zou, Qinkai Zheng, Yuxiao Dong, Xinyu Guan, Evgeny Kharlamov, Jialiang Lu, and Jie Tang. Tdgia: Effective injection attacks on graph neural networks. In 2021
Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks on neural networks for graph data. In KDD, 2018.
Daniel Zügner and Stephan Günnemann. Adversarial attacks on graph neural networks via meta learning. ICLR, 2019.
13

---

Published as a conference paper at ICLR 2024
A
PROOF
This section provides a rigorous proof and analysis to clucidate the robustness of the DPMoE module. The proof of Lemma 1 is adapted from Lemma in the research (Lecuyer al., 2019), aligning the notations and the scope of this paper.
We first assume the composition model f(.) with classical Gaussian mechanism satisfies (c. 6)-DP property. This assumption follows precedents in NLP (Wang et al., 2021) and CV (Lecuyer et al., 2019), where language/vision models composed of the DP module be assumed to satisfy (e, ()-D.. The (c, 8)-DP can be justified through its use of the classical Gaussian DP output perturbation (this mechanism is inherently (c, -DP) due the post-processing invariance of differential privacy (i.e.. any computation on the output of the DP mechanism remains DP).
Given (r) representing a p-norm ball with radius r, defined as:
By(r) (Ah!) e R. | rr).
(10)
where A represents the noise affecting h layer / after message passing for node v. Suppose node classification model f()) is robust to this perturbation if, for all An E Bp(r).
fa(h' max f((h' 0 Bifk
(11)
Lemma 1. (Expected Output Bound) Let f(-) be GNN incorporating DP-GCon and having bounded output f f(h that satisfies (c, DD... Then, the expected output (h has the following property:
b)
[ S e ( +66 66, vAh E Bp(b).
(12)
Proof. For A E (b) that modifies 11 to ((()) the expected output f(-) is
B((()))] J Pr(s()))) > f)dt.
(13)
Using the post-processing property of (c, 5)D algorithms and applying this to f(.), we deduce:
[[f(h()) s et (1." Pr(F(()9)) > t)dt + b5
(14)
=EE( +
Assuming f()) incorporating DP-GConv satisfies (cP and f(h (F1()))) fK
(x (11
where (x (1) [0, 1). applying Lemma I with b = 1, we have
B( S B(JAAN +8, Vk, VAN E B,(1).
(15)
Proposition 1. Robustness Guarantee for DPMoE. For GNN f(-) containing DPMcE which utilizes Gaussian DP, assume this mechanism lets the model output satisfy (o,6)-DP. the expected value B. of the model output satisfies the following property:
2c max ((f.(h()) + +1+
(16)
siif
then the label probability output vector p(h! = (E(fi (1) ")
(he))) of f() node
satisfies the robustness: (f (he" max ((fs(ho)) ))
Proof. We first consider GNN, f(-), containing only DP-GConv. By Equation (15), derived from
Lemma 1, we have:
E(fa(h()) 5 {EE((F( 8,
(17)
) S SETEAA +
(18)
14

---

Published as a conference paper at ICLR 2024
Given the lower-bound on ((f by Equation (17) and the upper-bound on max, ((f by Equation (18), we deduce:
equation 17 E(fa(ho)) -
6²
max B(f((h))) ( + 611+
(19)
e" max B(f +
((f((h".))) )), tafk
max
aligning with Equation (20), implying robustness of the model f(-) containing DP-GConv.
To further prove the robustness of f(-) containing DPMoE, we simplify Equation (8) ((+1)
Update(he)) ()) and substitute it into Equation (16), to yield:
[[Updatee(f((b e²t max maxx((Updatee((((h"))) + e
(20)
Thus, when f(.) containing DPMoE satisfies Equation (20), satisfies robustness. Note that we set N4 to obtain more concise proof.
Proposition explicates the interrelation between the model's robustness and the perturbations in the features. This interrelation enables the identification of maximum solution, denoted as Ah (!)
D[max)'
ensuring the model's robustness. Post injection attacks, let's denote h as:
h i C (DPMOF.ON[")) AGG (DPPMRR" (n- (21)
where Yu E N₂ A u E G, and Vi E N Aw G' Aw $ G. Denote the attack method as Att(-) and the altered graph as:
G' AU(AE,AN,C)
(22)
where AE and AN represent the budget of edges per injected node and the budget of injected nodes, respectively, and G is the input graph.
According to Proposition 1, there exists a maximum solution Ah A e(max) that certifies the robustness of the model, provided Equation (16) holds true, and the 8)D in DP-GConv is maintained. Here, AA (1) (mmax Equation (8) Equation (21). By solving Equations (16) and (21) along with AA, (4) "(max)* a maximum AN can also be found to guarantee model robustness with a fixed A E. Importantly, there is necessity inversely solve for the explicit maximum AN.
B ADDITIONAL PERFORMANCE COMPARISONS
We also test the robustness of DRAGON under the PGD attack and the SPEIT attack. The results are shown in Figure 6, 7 and 5. The figures show our method outperforms all baselines under representative attacks scalable and robust framework for GNNs.
15

---

Published as a conference paper at ICLR 2024
Cora
Citeseer
Flickr
90
80
60
75
GAME
60
Accuracy
%0
RGON
RGEN
GAME-AT
GAME-AT
65
50
GATCuaid
30
RCCN
40
RGCNA
GAT
RGCN
30
50
200
600
800
2000
4000
intensity (# (finjected nodes]
Attack Intensity (e injected nodes)
Attack Intersity (Minjected nodes)
Reddit
AMiner
100
30-
Accuracy(55)
50
80
CAMEA
40
RGCN-AI Al
Eventie
CAT
EAT-AT
30
DAME-4T AT
GCN AT
ECN-T
20
DAT-AT
Durs
10-
Ours
DUPUAT
DurVAT
50
9c
Re
9k
12c
15k
4K
12k
15k
20k
Attack Intensity (dinjected nodes)
Attack Intensity (8 (iijeccted nodes)
Figure 5: The performance of top-5 baselines and our method under the SPEIT Attack.
Citeseer
Flickr
80
55
85
70
Accuracyeis
800
GAME-AT
60
RGDN
Accuracy/55
RIEN
75
GATGuerS
50
GAME-AT
GAME-AT
70
GATAT
GEN-AT
40
GATAT
GATCLard
CAT-AT
Evarthet
RECN-T
30
RGGNAT
REENAAT
OurE-A"
20
Oun-AT
Durs
DursAT
55
100 300
10c
200
400
600
800
2000
4000
Attack intensity (#injected nodes]
Attack Intensity (Rinjected nodes)
Attack Intensity (#injected nodes)
Reddit
AMiner
Accuracy(50
GCM
ROCK
RGON AT
30
GON-AT
GAME-AT
CAME
20
GAT
AT
OurS
10-
Ours
Ours
3K
GK
9K
12x
15k
4k
8k
12k
15k
20k
Altack Intensity (#injected nodes)
Atlack Intensity (4 (Winjected nodes)
Figure The performance of top-5 baselines and our method under the PGD Attack.
Citeseer
Flickr
Accuracy(%)
70
Accuraty
75
GAME-AT CATGueed
60
RAME-AT
RGON
Accuracy
40
GAME-AT
RGEN
GCN AT
GATCuard
EvenNet
55
GTT
50
GAT AT
Di W
CAT
60-
RCCN AT
RGCN AT
RGCN AT
40
Ours
AT
Ou
DU
50
100 200 300 400
30
200
400
600
500
1000 2000 3000 4000 5000
Attack Intensity ( dfijecteed nodes)
Attack Intensity injected nodes)
Attack Intersity (finjected nodes)
Reddit
AMiner
1.00
70
60
(cciracy(5))
80
GCN
ROCN
70-
30
GCN
GAVE-AT
GAMEAAT
20
GATATT
Ours
10
Outs
DursAT
DunwAT
Be
9k
12c
15c
4k
8k
12k
15k
20k
Attack intensity (finjected nodes)
Attack Intensity (Finjected nodes)
Figure 7: The performance of top-5 baselines and our method under the TDGIA Attack.
16

---

Published as a conference paper at ICLR 2024
Cora
Citeseer
Flickr
90
80
60
75
GAME
60
GAME AT
45
RGCN
GATGuord
GON-AT
GAME-AT
65
50
GATCuard
60
Evantkit
RCCN
40
GAT
35
ROCN
30
50
200
600
800
2000
4000
Attack intensity (# deinjected nodes)
Attack Intersity (e injected nodes)
Intersity (Minjected nodes)
Reddit
AMiner
100
Accuracy(50
50
70
ROCK
CCN
40
NGCN- AT
GCM
60-
GAME-AT
CAT
30
DAME-41 AT
GCN AT
EAT AT
20
DATTAT
Durs
10-
Ours
DUPUAT
Re
9k
12c
15k
4K
12k
1Sk
20k
Attack Intensity (dinjected nodes)
Attack intensity 1e (iijeccted nodes)
Figure 8: The performance of top-5 baselines and our method under the HAO Attack.
We note that DRAGON exhibits relatively lower robustness on the AMiner dataset compared to others. This outcome can be attributed the distinctive characteristics of our DPMoE module. By incorporating DP noise into the feature space, our approach effectively mitigates the adverse effects stemming from the malicious aggregation of injected node features. This mechanism enhances robustness, especially on datasets with larger feature dimensions, as evidenced by our empirical findings. Notably, the AMiner dataset has a modest feature dimension (#Feat 100). In contrast, datasets like Citeseer (#Feat 768) and Reddit (#Feat 602), characterized by richer feature dimensions, show minimal performance degradation. This highlights the strength of our method in handling datasets with more extensive feature information common scenario in real-world data.
C IMPLEMENTATION DETAILS
C.I REPRODUCIBILIIY SETTINGS
Training and Evaluation Configuration. In our experiments, we maintain consistency with the default hyperparameters of the GRB benchmark for the baseline methods. To ensure reliable results, we conduct 5 runs for each experimental result and report the mean value and standard deviation. Additionally, we adhere to the GRB benchmark's 's data splitting protocol, with 60% of the graph data as the training set, 10% as the validation set, and 30% as the test set for each benchmark dataset. Statistics of GRB data covering small to large graphs are listed in Table 4. All experiments performed on an NVIDIA V100 GPU with 32 GB of memory.
To ensure reproducibility,
follow the hyperparameter settings of baselines used in GRB (Zheng et al., 2021) and other original papers (Chen et al., 2022; Zhang et al., 2023c). The hyperparameters of DPMoE are given in Table including hyperparameters of adversarial training listed in Table Specifically, for Cora, we set the total number of experts to N = 10 and the number of activated experts to k 2. For other datasets, by default, we set the total number of experts N and the number of activated experts to k 1. Note that the DP scaling coefficient μ4 for each individual expert is linearly increased via multiplying the minimum coefficient by as the index i of that expert increases. The number of experts is determined by evaluating the performance of the validation set. The experiment results on the Cora dataset in Table assess the DPMoE module's performance with varying numbers of experts. We find that when the number of experts (num) is set to 10, the accuracy of the validation set approaches a marginal effect. However, when the number of experts exceeds 10, uncertainty increases, potentially leading to instability in optimizing a larger number of expert models. Therefore, we set the number of expert models to 10, which allows us to achieve acceptable differential privacy rates.
Additionally, hyperparameters of DMGAN are shown in Table 10. The mask rate is 0.7, the walks per node is 1, and the walk length is 3.
17

---

Published as a conference paper at ICLR 2024
Table 3: Hyperparameters for adversarial training. The settings follow the GRB benchmark.
Datasets
Cora
Cheseer
Flickr
Reddiz
AMiner
Injections
Edges
20
20
100
200
100
size
0.01
0.01
0.01
Iteration
10
Attack
FGSM
RGSM
RGSM
RGSM
FGSM
Table 4: Statistics of GRB data covering small to large graphs.
GRB
Feat, Range
Scale
Nodes
Edges
Feat.
Classes
Datasets
(normalized)
Coru
Small
2,680
5,148
[-0.94, 0.94]
Citeseer
Small
3,191
4,172
768
[-0.96, 0.89]
Flickr
Medium
89,250
449,878
500
[-0.47, 1.00]
Reddit
Large
232,965
11,606,919
602
41
[-0.98, 0.99]
AMiner
Large
659,574
2,878,577
100
18
[-0.93, 0.93|
Table Hyperparameters the DPMoE defender GNN.
Datasets
Layer num.
Hidden size
Heads
Dropout
LR
Backbone layer
Minimal DP rate
w.O.
AT
w.O. AT
w.
w.o.
w.
Cora
3
128
0.5
0,001
GATGuard
GAT
0.3
0.1
Citeseer
3
0.5
0.001
GATGuard
GAT
0.3
0.1
Flickr
3
64
8
0.5
0.0001
0,0001
GAT
GAT
0.3
0.1
Reddit
2
64
0.5
0.01
0.01
GAT
GAT
0.1
0.1
AMiner
3
0.5
0.01
GAT
0.1
0.1
Table The results of DPMoE module with different numbers of experts on Cora dataset under FGSM attack
num, of experts
5
10
75
150
Accuracy
0.825
0.841
0.842
0.841
0.839
C.2 MORE DETAILS ABOUT ATTACK STRATEGIES
We examine three effective and diverse graph attack methods that can impair the performance of vietim GNNs, including our proposed DRAGON framework and other baselines. The details of these attack strategies are listed as follows:
The Fast Gradient Sign Method (FGSM) (Goodfellow et al., 2015) computes the optimal max-norm constrained perturbation attacks by linearizing the loss function around the current value of the parameters.
FGSM:
SPEIT: SPEIT (Zheng et al., 2020) emerges as the first-place winner in the KDD-CUP 2020 Graph Adversarial Attack & Defense competition. It generates perturbed adjacent matrix and feature gradient attacks for global black-box node injection attack.
PGD: The Projected Gradient Descent (PGD) (Madry et al., 2018) is an adversary method that leverages local first-order gradient information about the network generate the strongest attack inputs.
TDGIA: Topological Defective Graph Injection Attack (Zou et al., 2021) introduces the topological defective edge selection strategy and the smooth feature optimization objective to generate the features for the injected nodes.
HAO: Harmonious Adversarial Objective (HAO) (Chen et al., 2022) introduces homophily unno- ticeability that enforces graph injection attack to preserve the homophily, thereby enabling stronger attacks.
18

---

Published as a conference paper at ICLR 2024
In order to generate gradient- gradient-based attacks, we follow previous research (Zheng et al., 2021) and use GCN as the surrogate model. To enhance the strength, stability, and transferability of the attacks, we also add layer normalization (LN) layers provided by the GRB benchmark to the GCN surrogate model. The hyperparameters of the surrogate model are presented Table 7. The step size is 0.01 and iteration is 1000 when attacks are generated. In addition, We provide details of node injection attack intensities from nulla to V in Table 8.
Regarding attacks, in our setting, integrating other single-node injection attacks such as SNI (Tao et al., 2021) as a baseline proves challenging due to limited edge scope, which differs significantly from other baselines that involve injected nodes with multiple edges. Furthermore, Table shows that these baselines exhibit stronger attacks than Tao et al. (2021)'s I''s method. Notably, our method's robustness is demonstrated against the latest and most advanced injection attacks Appendix B.
Table Hyperparameters the surrogate model (the settings follow the GRB benchmark).
Datasets
Cona
Citsserr
Fbikr
Reddiz
AMiner
Hilden Size
64
64
128
128
128
Layer Number
3
3
3
3
Learning Rate
0.01
0.01
0.01
0,01
0.01
Dropout
0.5
0.5
0.5
0.5
0.5
Table The configurations about attacks of five intensities and without attacks: node represents the number of injected nodes, # edge/n. represent the max number of edges per injected node, and nulla represents without any attack injections into the graph input.
Attack Intensity
Dataset
Injection
nulla
I
II
III
IV
V
node edge/n.
0
1+135
2*135
3*135
4*135
5*135
Cora
20
20
20
20
20
Citeseer node edge/n.
0
1+160
1*160
1*160
1*160
1*160
0
20
20
20
20
20
Flickr node edge/n.
0
|$1000
2
3
491000
$*1000
0
100
100
100
100
100
node edge/n.
0
|#3000
30000
3*3000
4*3000
5*3000
Reddit
0
200
200
200
200
200
node
0
1*4000
2*4000
3*4000
4*4000
5*4000
AMiner
edge/n.
0
100
100
100
100
100
Table 9: DRAGON's performance under attacks at Intensity V. Other methods exhibit stronger attacks than Single Node Injection Attack (SNI) (Tao et al., 2021).
SNI
FGSM
SPEIT
PGD
TDGIA
HAO
Ours
52.5
48.8
51.2
51.3
48.7
48.1
D TRADE-OFFS OF DMGAN
According to Figure 9, the trade-off associated with using DMGAN as a denoising module needs be considered: there risk of removing the original edges along with the malicious edges, which may affect the performance of the model when it is used in a non-attack setting. After careful study, we find that reconstruction rate of 0.3 provides good balance between these trade-offs. For example, compared with DRAGON integrated with vanilla graph autoencoder, our DRAGON integrated with DMGAN sacrifices only little accuracy under non non-attack settings, but shows larger accuracy improvement when the graph is under attack. The improvement of our DRAGON increases as the attack intensity increases, demonstrating the robustness of our DPMoE design from several perspectives.
To further explore the denoise ability of DMGAN, we conduct the experiment and report the results in Table 11, Let's denote TPR-N1 (FNR-N1) as TPR (FNR) for link prediction between normal/original
19

---

Published as a conference paper at ICLR 2024
nodes; and TPR-At (FNR-Af) as TPR (FNR) for link prediction between original nodes and injection/attack nodes. FNR-N (less than 7.4%) indicates how many edges between original nodes wrongly removed by DMGAN. According the previous research (Jin et al., 2018). the edge noise of this level between original nodes only causes a small robustness degradation (less than 3%) on GNNs. FNR-A (more than 25.1 %) indicates how many more harmful malicious edges of attack nodes are removed by DMGAN.
In order explore the sensitivity of hyperparameters DMGAN and how each loss term contributes to denoising on the attacked graph, we present sensitivity analysis in Table 12, Figure 10 and fine-griined ablation study in Table 13.
Table 10: Hyperparameters DMGAN. We use a simple graph auto-encoder model design to ensure scalability.
Auto-encoder
Model
Layers Num.
Hidden Size
LR
Dropout
Encoder
GCN
128
0.01
0.8
Decoder
MLP
2
64
0.01
0.2
Table 11: TPRs and FNRs of DMGAN under FGSM attack on Cora dataset.
nulla
11
111
IV
TPR-N1
0.954
0.941
0.935
0.931
0.929
0.926
FNR-N
0.046
0.059
0.065
0.069
0.071
0.074
TPR-A
N.A.
0.638
0.674
0.691
0.724
0.749
FNR-A
N.A.
0.362
0.326
0.309
0.276
0.251
90
70-
Accuracy(95)
60-
Accuracy(59)
60
40-
DMGAN
W.b DNGAN
DMGAN-00.25 0.22
DMGMN-0011
DMGAN-0.30
40
DMG
10-
DMGAN
0 100 200 300 400 500
600
700
20
200 300 400 500 600 700 Attack Intensity (# injected nodes)
100
Attack Intensity (# injected nodes)
Figure 9: The effect of DMGAN with different reconstruction rates on the performance of GAT (left) and DPMoE (right) defender GNNs in the Cora dataset under the FGSM attack (the DPMoE module uses the GAT layer the backbone layer of each expert network).
Table 12: Sensitivity analysis for hyperparameter of DMGAN loss of L La + abe.
0.000
0.005
0.010
0,015
0.020
DMGAN
48.31
48.63
48.56
48.48
48.41
DRAGON
$1.63
52.02
51.90
51.88
51.87
50.0
47.5
50
Accuracy(R)
45.0
Accuracy/s5)
42.5
35
40.0
37.5
25
35.0
32.5
30.0
Walk Length
Number of Walks
Figure 10: The effect of DMGAN with different walk lengths and number of walks under FGSM attack Flickr datasets, J-V represents attack intensities.
20

---

Published as a conference paper at ICLR 2024
Table 13: Fine-grate tinengr Ablation studies under FGSM attack of varying intensities on Flickr dataset. DM-
GAN(Link) denotes only using link prediction loss in DMGAN and DMGAN(Link + Degree) denotes incorpo- rating both link prediction loss and degree regression loss.
Models
Vanilla GAT
50.0
47.8
44,1
34.2
24.5
24.9
DPMoE
52.9
51.6
49.
49.1
48.5
47.7
-DMGAN(Liik)
DMGANO Degree)
50.2
48.6
41.2
33.3
52.2
51,6
51.2
50.4
49.5
47.6
+DMME DWG.DDMMNN--DDDOCCCo Degree))
52.7
52,0
318
51.2
50.3
48.8
E DEFENSE AGAINST GRAPH MODIFICATION ATTACKS
In the main section of the paper, we mainly present the performance of DRAGON under graph injec- tion attacks. To evaluate the effectiveness of DRAGON under graph modification attacks, we apply GR-BCD and BR-BCD attacks (Geisler et al., 2021) on our method and baselines, including SOTAs Mii-MMMddd//So--Meeeeee GDCs (Geisler et al., 2021) and GAME). The results are summarized below in Table 14.
Table 14: The robust accuracy of Soft-Median GDC and Soft-Medoid GDC without or with our GAME
framework on the Cora dataset with the global attacks (GR- BCDDB & PR-BCD, = 0.1) proposed by Soft- Soft-Medoid
GDC. We set the number of experts 10 and the hidden units of each expert 32. We run them three random splits and report the mean and standard error results.
GR BR-BCD
PR PR-BCD
GCN
0.622 0.003
0.645 0.002
GDC
0.677 a 0.005
0.674 1: 0.004
PPRGo
0.726 0.002
0.700 : 0.002
SVD GCN
0.755 0.006
0.724 0.006
Jaccard GCN
0.664 = 0.001
0.667 : 0.003
RGCN
0.005
0.664 + 0.004
Soft Median GDC
0.765 0.001
0.752 4 0.002
Soft-Medoid GDC
0.775 1 0.003
0.761 4 0.003
Moft-nedian GDC (+GAME)
0.772 0.005
0.759 0.005
Soft-Medoid GDC (+GAMB)
0,780 0.007
0.772 + 0.006
DRAGON
0.788 + 0.012
0.784 * 0.007
F DEFENSE AGAINST GRAPH ADAPTIVE ATTACK
In our paper, primarily focus more advanced and scalable injection attacks involving malicious node features and edges. On the other hand, adaptive attacks LowBlow (Entezari et al., 2020) and the method from Mujkanovic et al. (2022) primarily focus structure (edge) perturbations and usually limited to small graphs due to their cubic complexity in computing the full set of adjacency eigenpairs. Consequently, adaptive attacks fail scale to medium- sizedd graph datasets like Flickr and large graph datasets like Reddit. Additionally, they cannot be easily scaled with higher intensity, which is essential for our investigation into the emergence of robustness degradation. Moreover, our DMGAN module is non- non-differentiable during graph reconstruction, making adaptive attacks difficult to optimize specific loss function on our model. Table 15 provides a referential comparison when models are attacked by adaptive attacks.
Table 15: The robust performance of our method under adaptive attacks on the Cora dataset.
Model
Vanilla
SVD
ProGNN
GNNGuard
GARNET
Soft-Median-DDC
Ours
Entezari
74.77
26.03 2.76
77.62
Mujkanovic et al. (2022) 75.32 0.71
20.11 3.32
74.87 2.02
72.53 4 0.25
75.27 0.74
0.74
77.15 0.55
79.92 2 1.35
21

---

Published as a conference paper at ICLR 2024
G EXPLORATION OF ALTERNATIVE GRAPH ROBUST LEARNING METHODS (SLIGHTLY OUTSIDE THE SCOPE OF OUR PAPER)
In Appendix E and Appendix F, we have assessed several of these baselines under different types of attacks, furmishing comprehensive discussion along with experimental results. Therefore, here, we aim elucidate the rationale behind not selecting some recent methods our primary basclines.
Many methods are only effective for specific attacks with ad hoc designs, making the results less generalizable and practical. SoftMedian (Geisler et al., 2021) and GARNET (Deng al., 2022) are only designed to defend against structure (edge) perturbations between original nodes by cleaning the structure, and GCN-Jaccart (Wu et al., 2019b) uses structure-based preprocessing. Although structure- based solutions handle structure perturbations well and can scale to large graphs by considering only structure, they fail to defend against advanced node injection attacks with both malicious features and edges. Table 16 shows that the performances of these structure-based methods are less robust than GAT with adversarial training and even close to vanilla GAT under node injection attacks. This structure- based weakness has been discussed in the benchmark (Zheng al., 2021), which also avoids them as baselines.
Current graph anomaly detection methods still face the accuracy problem when used to remove malicious nodes, i.e., they falsely identify too many original nodes as anomaly nodes. The recent method CoLA (Liu et al., 2021) provides detection performance of 0.751 the Flickr dataset, which means that when using it to remove attacks, it may introduce even more extra node noise (0.249) than the highest intensity attacks (0.056). Table 16 shows that anomaly detection cannot be easily generalized to our scenario, i.e., the emergence of robustness degradation.
Table 16:
The performance of DRAGON and other methods under FGSM attack of varying intensities the Flickr dataset. GAD is representative graph anomaly defection method and Struc. represents methods are only designed for graph structure attacks or only defend structural ways.
Methods
nulla
I
III
IV
V
Vanilla GAT
50.0
47.8
44.1
34,2
24.5
24.9
CoLA (GAD Anamaly Detection)
38.2
25.7
19.8
17.6
14,5
15.2
GCN-Jaccare (Struc.)
47.3
41.2
33.6
18.3
14,8
15.4
SoftMedian (Struc.)
$1.0
48.3
46.2
39.8
27.2
28.7
GARNET (Struc.)
51.8
49.9
42.1
35.6
29.2
30.1
GAT
44.2
44.3
44.0
43.1
42.8
42.4
Ours
52.7
52.0
51.8
51.2
50.3
48.8
H COMPLEXITIES
Here analyze the time and memory complexities of our method. Let N be the number of nodes, N' be the number of nodes after masking, E be the number of edges, E' be the number of edges after masking, d be the size of the hidden channels (we assume it is of the same order as the size of the input features), l be the number of encoder layers in the DMGAN, l2 be the number of MLP layers in the DMGAN decoder, 13 be the number of DPMoE layers, & be the number of experts, our comprehensive complexity analysis is structured as follows:
DMGAN Module. DMGAN encoder part obtains encoded representations with time complexity d(Idd2N') and memory complexity dldd) The DMGAN MLP decoder part decodes the degree regression with time complexity (lzd? N²) and memory complexity OIIdNN Izd?). MLP also predicts whether edges exist or not by decoding 2F' times node feature element-wise product, with (222ad3 F') time and (22 + 1zd)) memory complexity. The total time complexity of the DMGAN module is Oll N' + (22d2(N' +2dE")) and the memory complexity is Olld(NN' d) + 12d(N' 2E + 2d)).
DPMoE Module. In one layer DPMOE, N/k nodes are distributed into each expert, resulting in ((PN/K) time and (d + dN/k) memory complexity. For all experts, the total time complexity is N) and memory complexity is O(kd dN)- Gating network is trained with O(dNN) time complexity and constant (dk) memory complexity for gating in one layer. Overall time complexity of DPMoE module is O(IdNN dd k:)) and memory complexity is OlId((N N kd + k)).
22

---

Published as a conference paper at ICLR 2024
DRAGON (Complete Model). Overall time complexity of DRAGON is O + INd 2dE') + (Igd k), and memory complexity is (l1((N' + d) + (N' + 2E" +2d) + 13d(NN+ kd + k)).
Given these additions and clarifications, when constants are stripped away (i.c., mask rate), the complexities for methodology remain linear (i.e., O(N+ matching earlier simplified analysis and empirical outcomes. Empirical assessments, as presented in Table I, underscore that most baselines with ((N)) complexities (e.g., GCNSVD and GNNGuard) find scalability challenging, especially with medium to large graphs. This contrasts with our linear complexity method which demonstrates better scalability. For brevity, the comparison between some representative baselines and our method is listed in Table 17. In addition, comparing the standard training time, DRAGON shows better performance and less training time compared to GNNGuard and GCNSVD since they have significantly higher time complexity of O(N2). The details of training time are listed in Table 18.
Table 17: Time and Memory Complexity of representative graph robust learning methods.
Complexity
RGCN
GAME
EvenNet
GCNSVD
GNNGuurd
Ours
Time Memory
O O
O(N E)
O(E)
O(N E)
O(E) O(N")
ONN O(N
O(N)
O(N E)
O(N")
Table 18: The training times for models on the Cora dataset.
Model Name
RGCN
GAT
EvenNet
GAME
DRAGON
GNNGuard
GCNSVD
Training Time (s)
00:03
00:04
00:11
00:18
00:23
01:03
05:28
I A BITTER LESSON FROM THE REAL WORLD: MASSIVE NODE INJECTION ATTACK Is POSSIBLE
Learning from the highly corrupted graph is important. In representation learning, the ability to derive effective representations from highly corrupted data has been subject of great interest. This pursuit is evident in various domains, including computer vision, where the goal is recover original images from heavily noisy pictures, and natural language processing, where the challenge is to learn useful language representations from low-quality Internet corpora. Similarly, in the context of graphs, the significance of learning effective representations from highly corrupted data cannot be overstated. Therefore, the ability to learn high-quality representations from highly noisy Internet social graphs is of immense practical importance.
Massive node injection on the graph is possible. The notion of "unnoticeability" or "imperceptibil- ity" is indeed critical in general adversarial attacks, which constrains the attack intensity. However, transposing this concept directly from computer vision to graph scenarios brings about its own set of challenges, which allows strong attack intensity to be realistic on graphs:
(i) Ill-efinition in Graph Scenarios: As highlighted by research on adversarial learning on non- Fuclidean data, specifically on graphs (Zheng et al., 2021):
"However, this assumption is controversial: If defenders have the original graph, they can simply train the model on that one; If defenders do not have the original graph (the general case for data poisoning where defenders can not tell whether the data are benign or not), then it does not make sense to keep unnoticeability. This is different from the case of images, where unnoticeability can be easily judged by humans even without ground-truth images."
"The attackers may perturb the graph structure attributes within the scope of unnoticeability defined by themselves, while defenders have to depend on their own observations to discover. However, even defenders notice that the degree distribution different, is still hard to identify specific malicious nodes or edges from the entire graph."
"Thus, we do not add too many constraints and we insist that the notion like "umnoticeability" will be refined during the arms race between attackers and defenders. For example, if an advanced
23

---

Published as a conference paper at ICLR 2024
defense proposes measure to identify malicious nodes with high probability, then the attackers can decide by themselves to refine the constraints based on this measure."
(ii) Dynamics of Real-world Graphs: Networks like those on the internet undergo constant mod- ifications, often through the addition of new nodes. This continual change provides conducive environment for malicious node insertions, often without the constraints of "unnoticeability", Identify- ing these alterations, especially the specific malicious nodes and edges, is challenging, as highlighted Global-Ree Response Section 3.
(iii) High-Intensity Attacks in Reality; Contrary to the notion of limited attack budgets, real-world scenarios, especially on Internet social platforms, have demonstrated intense attacks. For instance, media outlets have reported massive bot influxes on platforms like Twitter. These bots, operating at high intensities, spread disinformation on an unprecedented scale, and interact with other users without being detected (same with injection attacks). One real-world report' have shown that bots present on these platforms at high intensities (20%). In such scenarios, where attacks are noticeable, classifying new nodes on attacked graphs remains crucial challenge. The societal concerns derived from social media are always at the forefront of machine learning research (Vosoughi et al., 2016, 2017, 2018; Liu et al., 2024).
In conclusion, our work primarily emphasizes high-intensity attack scenarios, given their growing relevance in real-world graph contexts. These scenarios differ significantly from traditional attack situations in vision or language domains. Our approach, designed to address the emergence of severe robustness degradation, gains notable importance in these graph-related contexts.
Twitter Bots Poised Spread Disinformation Before Election, The New York Times, October 29, 2020.
24


Reviews:
[{"review_id": "ljMej4qOSo", "reviewer": "Reviewer_kprb", "summary": "The paper develops a novel graph learning model that can handle very intense attacks and avoid heavy computation complexity. The model involves designing a new graph neural network (GNN) architecture the mixture of experts associated with differential noise. Extensive experiments are conducted to demonstrate that the proposed model can outperform many baseline methods against different attacks. Sufficient theoretical analysis is also provided.", "questions": "Please see the weaknesses.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "+ It is new that the paper introduced the problem of performance degradation against intense attacks of existing models. Solving the problem is very important, especially for the data of high-risk applications. It is also interesting to consider improving computation efficiency. \n\n+ The paper developed a new model that leverages a mixture of experts to design a new graph neural network architecture, which is novel and interesting. The theoretical analysis of the proposed method is sufficient and solid. \n\n+ The authors have conducted sufficient experiments over multiple datasets with different intensity attacks. The proposed model outperforms many baseline methods. The improvements are significant.", "weaknesses": "- It seems that the current manuscript mainly focused on the node attacks. How is the performance of the proposed method against other attacks? That is, more results and discussion regarding different attacks are suggested. \n\n- Besides a mixture of experts, there are other choices for improving GNN from an ensemble perspective. It is necessary to discuss the comparison between different methods and why the current design, i.e., MoE with differential private noise, is selected.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "Foibsdd4PC", "reviewer": "Reviewer_owAp", "summary": "The authors propose a graph neural network resilient to adversarial attacks. This approach incorporates a denoising step and a novel message passing scheme that leverages a mixture of experts (trained for varying levels of noises). The superiority of the proposed method over baseline approaches is demonstrated across diverse adversarial attack scenarios.", "questions": "Q1. Please address W1\n\nQ2. Please address W2\n\nQ3. Could you provide details on how E_{r} is derived from the trained auto-encoder? Can it include new edges, or does it solely filter out some existing ones?\n\nQ4. The results in Table 11 are not easy to understand. Can you please provide more specific details, including the numbers of TPs, TNs, FPs, and FNs?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "S1. The paper is easy to follow well structured.\n\nS2. The inclusion of a mixture of experts, each tailed for distinct noise levels, seems to be a novel and logical approach.", "weaknesses": "W1. The argument regarding the poor scalability of the existing method is not sufficiently convincing. For example, many extremely fast SVD algorithms have been developed for sparse graphs. It is essential for the authors to discern whether the scalability issue (e.g., O(N^2) complexity) is simply an implementation issue or it stems from fundamental limitations. \n\nW2. It appears that the considered baselines were not specifically designed to address the attack scenarios under consideration (i.e., the injection of nodes). For instance, EvenNet is specifically designed for generalization to graphs with different degrees of homophily. Consequently, claiming superiority over them may not strongly support the effectiveness of the proposed method. The authors should consider evaluating their approach against state-of-the-art methods better aligned with the specified attack scenarios.\n\nW3. The denoising performance of the proposed auto-encoder module is not compared with any baseline approach (e.g., Jaccard, SVD, etc).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "euVTlAkchM", "reviewer": "Reviewer_qpZP", "summary": "This paper focuses on defending node injection attacks on graphs. The authors propose a pipeline called DRAGON to reconstruct a clean graph via combining denoise auto-encoder and DP-based mixture of experts. Extensive experiments are conducted to illustrate the advantage of the proposed method.", "questions": "1. Why the deviation is in this form: $σ =\\sqrt{p2ln(1.25/δ)/ε}$ in DPGC in section 4.2?\n2. In Table 1 why adversarial training can hurt the robustness of DRAGON for most cases?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The problem is well motivated and important. The organization is clear, and the performance of the proposed method is promising.", "weaknesses": "1. Illustrations in some sections are not clear and easy to follow. For example in Section 4.2, the notations are not clearly introduced. Besides, the motivation of DPMoE is not well introduced. The authors should provide some intuitions/insights for leveraging Mixture-of-Experts, which I think is an important novelty of this work. But from this section, I do not get why MoE is useful though the authors empirically illustrate that in the experimental part.\n2. Lemma 1 is very confusing. It is hard to understand what the authors are trying to state in this lemma and how it supports the method. The most confusing thing is that \"Suppose a GNN f(·) containing DPMoE satisfies (ε,δ)-DP\", how can this be supposed? I thought Lemma 1 was to prove that adding a DPMoE module to the model would make it DP, but the authors directly assume that. Besides, what does this mean \"node v is robust to the features $h_v^{(l)}$\"? This statement is too informal and the authors should characterize robustness in rigorous mathematical expressions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "vqsylILzV9", "reviewer": "Reviewer_Fsb2", "summary": "This paper proposes a framework DRAGON that is robust against Graph Injection Attack. \nThe framework first adopts an edge denoising module implemented by an auto-encoder.\nThen, a Differentially-Private Mixture-of-Experts (DPMOE) layer is used as a robust Graph Convolution layer.\nExtensive experiements verify the effectiveness and efficiency of DRAGON.", "questions": "1. How is the auto-encoder trained? Is it trained on the clean graph or trained on the attacked graph? \nIf the denoising module is trained on the attacked graph, why auto-encoder enjoys such a good performance in recovering clean graph structrue?\nIncluding more discussion about the intuition why the denosing part is effective would be better. \n2. What the reuslts would be if the denoising module is compiled with other defense model?  For example, GATGuard + DMGAN. \nIt looks like the two modules of DRAGON can be decoupled. \n3. It is amazing that DRAGON is so efficient. Dose the reported time in Table 18 include the training time of DMGAN?\n4. DRAGON adopts other defense model as backbone, which could seems a little unfair. I wonder how DRAGON would perform when compiled with other basic GNNs like GCN? Is it sill competitive?\n5. Why the baselines like GATGuard and EvenNet not coupled with AT?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The proposed framework holds siginificant perfromance superiority over defense baselines against various types of attacks.\n2. The proposed framework is scalable to large graphs, like AMiner with more than 600,000 nodes.", "weaknesses": "1. The module of DRAGON is not first proposed in the paper, which slightly limits the novelty of the proposed framework.\n2. It would be better if the presentation is more clear. For example, the notations in the lemma are not well introduced. The setting of the attack and defense is not included as well. \n3. The whole framework is quite complex and not in an end-to-end manner.\nIt includes quite a few hyperparameters, and choosing a propoer GNN backbone seems to matter, which would be a concern when applied to real-world scenarios.\n\nOther concerns are listed in Questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)