Robust Graph Neural Networks via Unbiased Aggregation
Authors: Zhichao Hou
Ruiqi Feng
Tyler Derr
Xiaorui Liu
Venue: NeurIPS 2024 poster (2024)
Keywords: Adversarial Robustness
Graph Neural Networks
Robust Estimation
Primary area: graph_neural_networks

Abstract: The adversarial robustness of Graph Neural Networks (GNNs) has been questioned due to the false sense of security uncovered by strong adaptive attacks despite the existence of numerous defenses.
In this work, we delve into the robustness analysis of representative robust GNNs and provide a unified robust estimation point of view to
understand their robustness and limitations.
Our novel analysis of estimation bias motivates the design of a 
robust and unbiased graph signal estimator. 
We then develop an efficient Quasi-Newton Iterative Reweighted Least Squares algorithm to solve the estimation problem, which is unfolded as robust unbiased aggregation layers in GNNs with theoretical guarantees.
Our comprehensive experiments confirm the strong robustness of our proposed model under various scenarios, and the ablation study provides a deep understanding of its advantages.

Robust Graph Neural Networks via Unbiased A Aggregation
Zhichao Hou
Ruiqi Feng
Tyler Derr²
Xiaorui Liu
North Carolina State University, Vanderbilt University
( xliu96] Cncsu. edu ruiqifeng- 20240gmai1 com tyler dllerrderrSvandebbiltt.cc
saigifeng.20240gmai
Abstract
The adversarial robustness of Graph Neural Networks (GNNs) has been questioned due to the false sense security uncovered by strong adaptive attacks despite the existence of numerous defenses. In this work, we delve into the robustness analysis of representative robust GNNs and provide a unified robust estimation point of view to understand their robustness and limitations. Our novel analysis of estimation bias motivates the design of a robust and unbiased graph signal estimator: We then develop efficient Quasi-Newton Iterative Reweighted Least Squares algorithm to solve the estimation problem, which unfolded as robust unbiased aggregation layers in GNNs with theoretical guarantees. Our comprehensive experiments confirm the strong robustness of our proposed model under various scenarios, and the ablation study provides deep understanding of its advantages. Our code is available
Introduction
Graph neural networks (GNNs) have gained tremendous popularity in recent years due to their ability capture topological relationships in graph-structured structured data [ However, most GNNs are vulnerable
to adversarial attacks, which can lead to a substantial decline in predictive performance [2] 3 4
Despite the numerous defense strategies proposed robustify GNNs. a recent study has revealed that most of these defenses are not as robust initially claimed (5) Specifically, under adaptive attacks, they easily underperform the multi-layer perceptrons (MLPs) which do not utilize the graph topology information at all [5) Therefore, it is imperative to thoroughly investigate the limitations of existing defenses and develop innovative robust GNNs to securely harness the topology information in graphs.
Existing defenses attempt to bolster the resilience of GNNs using diverse approaches. For instance, Jaccard-GCN 6 and SVD-GCN 7 aim denoise the graph by removing potential adversarial learns the clean graph structure during
edges during the pre- preppeccsssnng procedure, while ProGNN (3]
the training process. GRAND g and robust training 99 10 also improve the training procedure reinforce their GNN architectures by heuristically reweighting edges in the graph. Additionally, there emerge some ODFssinspired architectures including the GraphCON [12] and HANG [13 that demonstrate decent robustness. Although most of these defenses exhibit decent robustness against transfer attacks, i.e., the attack generated through surrogate models, they encounter catastrophic performance drops when confronted with adaptive adversarial attacks that directly attack the victim model 5
through data augmentation. GNNGuard 2 and RGCN [1]
38th Conference on Neural Information Processing Systems (NeurIPS 2024).
"Equal contribution.
1 Correspondiig author.

---

Concerned by the false sense of security, we provide a comprehensive study on existing defenses under adaptive attacks. Our preliminary study Section Lindicates that SoftMedian 4. TWIRLS [4]. and FlasticGNN IS exhibit closely aligned performance and notably outperform other defenses despite their apparent architectural differences. However, as attack budgets increase, these defenses still experience a severe performance decrease and underperform the graph-agnostic MLPs. These observations are intriguing, but the underlying reasons are still unclear.
To unravel the aligned robustness and performance degradation of SoftMedian, TWIRLS, and ElasticGNN, we delve into their theoretical understanding and unveil their inherent connections and limitations in the underlying principles. Specifically, their improved robustness can be understood from unified view of f1 f1-based robust graph smoothing. Moreover, we unearth the problematic estimation bias of f bi-based graph smoothing that allows the adversarial impact to accumulate as the attack budget escalates, which provides plausible explanation of their declining robustness. Motivated by these understandings, we propose robust and unbiased graph signal estimator to reduce the estimation bias GNNs. We design an efficient Quasi-Newton IRLS algorithm that unrolls as robust unbiased aggregation layers to safeguard GNNs against adversarial attacks. Our contributions can be summarized as follows:
We provide a unified view of -baaed robust graph signal smoothing to justify the improved and closely aligned robustness of representative robust GNNs. Moreover, we reveal their estimation bias, which explains their severe performance degradation as the attack budgets increase.
We propose a robust and unbiased graph signal estimator to mitigate the estimation bias in é based graph signal smoothing and design an efficient Quasi-Newton IRLS algorithm to solve the non-smooth and non-convex estimation problem with theoretical guarantees.
The proposed algorithm can be readily unfolded as feature aggregation building blocks in GNNs, which not only provides clear interpretability but also covers many classic GNNs as special cases.
Comprehensive experiments demonstrate that our proposed GNN significantly improves the robustness while maintaining clean accuracy. We also provide comprehensive ablation studies to validate its working mechanism.
2 Estimation Bias Analysis of Robust GNNs
In Section 2. we conduct preliminary study to evaluate the robustness of several representative robust GNNs. Section 2.2] we establish a unified view as -based models to uncover the inherent connections of three werl-performing GNNs, including SoftMedian, TWIRLS and ElasticGNN. In Section 2.3, we leverage the bias of b--baded estimation to explain the catastrophic performance degradation in the preliminary experiments.
Notation. Let G {V,E} be graph with node V {UI,.... d and edge set & {ei...., em }. The adjacency matrix of G is denoted as A E 10.1)=xm and the graph Lapla- cian matrix L D A. D diag(d1.... ... d,) is the degree matrix where d: (N(ii) and Aii) is the neighborhood set of v4- The node feature matrix is denoted as F = [f f.] Rxa and (()) (FF()) denotes the node feature vector (matrix) before graph smoothing decoupled GNN models. Let A E {-1, 0, 1m be the incidence matrix whose 1-th row denotes the I-th edge = (i.5) such that Au -1, = 1, Ai = 0 Vk & {i.j}. Â is its normalized version A. Auj/ /dj. For vector & E IRd, we use based gragh smoothing penalty to denote either ||||| E, a or ||l122 = v E, .... Note that we use based gragh smoothing penalty to denote
|
2.1 Robustness Analysis
To test the robustness of existing GNNs without the false sense of security, we perform a preliminary evaluation of existing robust GNNs against adaptive attacks. We choose various baselines including the undefended MLP, GCN [16), some of the most representative defenses in (5), and two additional robust models TWIRLS 14] and ElasticGNN 15 We execute adaptive local evasion topological attacks and test the node classification accuracy on the Cora MI. and Citeseer datasets. The detailed
settings follow Section 4.1 From Figure I it can be observed that:

---

MLP
GNNGuard
GRAND TWIRLS
RGCN
GCN
SoftMedias
ElasticGNN
Cora
Citeseer
80
Accuracy (%)
60
40
20
20
50
100
150
200
100 150
200
Budget (%)
Budget (%)
Figure 1: Robustness analysis under adaptive local attack. The perturbation budget (z-axis) is the number of edges allowed be perturbed relative the target node's degree. SoftMedian, TWIRLS, and ElasticGNN (blue curves) exhibit similarly aligned competitive robustness among all the selected robust GNNs, but all models experience catastrophic performance degradation as the attack budget increases.
Among the selected robust GNNs, only SoftMedian, TWIRLS, and ElasticGNN exhibit notable and closely aligned improvements in robustness whereas other GNNs do not show obvious improvement over undefended GCN.
SoftMedian, TWIRLS, and ElasticGNN encounter a similar catastrophic performance degradation the attack budget scales up. Their accuracy easily drops below that of the graph-unware MLP, indicating their failure in safely exploiting the topology the data.
2.2 A Unified View of Robust Estimation
Our preliminary study provides intriguing observations in Section 2.1 but the underlying reasons be- hind these phenomena remain obscure. This motivates us to delve into their theoretical understanding and explanation. In this section, will compare the architectures of three well-performing GNNs, aiming to reveal their intrinsic connections.
SoftMedian [ substitutes the GCN aggregation for enhanced robustness with the dimension-wise median m, id for all neighbors of each node i E However, computing the median in- volves operations like ranking and selection, which is not compatible with the back-propagation training GNNs. Therefore, the median approximated as a differentiable weighted sum m = EjeN() w(f,, m,).f. Vi E V, where m; is the exact einddifferentiable dimension-win median, f, is the feature vector the j-th neighbor, w(x y) = e - -81i--llle Ull2, and Z Σn w (fk. my) normalization factor. In this way, the aggregation assigns the largest weights the neighbors closest to the actual median.
TWIRLS 14] utilizes the iteratively reweighted least squares (IRLS) algorithm to optimize the objective with parameter and p(y) = y is the default:
2A Σ (L.))E
p(l.f f(12))
Σ iEV
lff
f(o)
12 (1 -
(1)
ElasticGNN 15 proposes the elastic message passing which unfolds the proximal alternating predictor-correttn (PAPC) algorithm to minimize the objective with parameter \(1,2);
Σ - 1 + 1EV
Σ
f Vd
f Vd,
A2
f Vd
f,
where p E (1,2).
dd
(3.))E
A Unified View of Robust Estimation. While these three approaches have seemingly different architectures, we provide a unified view of robust estimation illuminate their inherent connections. First, the objective of TWIRLS in Eq. (I) can be considered particular case of ElasticGNN

---

with X2 0 and 2 when neglecting the difference in the node degree normalization. However, TWIRLS and ElasticGNN leverage different optimization solvers, i.e., IRLS and PAPC, which leads to vastly different GNN layers. Second, SoftMedian approximates the computation of medians in a soft way of weighted sums, which can be regarded as approximately solving the dimension-we median estimation problem [17] arg min ))EN(()) Ilf. - fşll Therefore, SoftMedian can be regarded the ElasticGNN with X2 0 and p = 1. We also note that the SoftMedoid [8] approach also resembles ElasticGNN with X2 = 0 and p = 2, and the Total Variation GNN [9] also utilizes an l estimator in spectral clustering.
The above analyses suggest that SoftMedian, TWIRLS, and ElasticGNN share the same under- lying design principle of fi-based robust graph signal estimation, i.e. similar graph smoothing objective with edge difference penalties || fill or Ilf: f5l12- However, they adopt different approximation solutions that result in distinct architecture designs. This unified view of robust estimation clearly explains their closely aligned performance. Besides, the superiority & bbased models over the b-base models such GCN [16), whose graph smoothing objective is essentially Eones f| V f3/ / 2 (20), can be explained since l bb-ased graph smoothing mitigates the impact of the outliers 15
2.3 Bias Analysis and Performance Degradation
The unified view of f-based graph smoothing we established in Section 2.2 not only explains their aligned robustness improvement but also provides perspective understand their failure attack budgets scale up through an estimation bias analysis.
Clean sample
Outlier
True mean
I
l
I l-b
Ours
10
10
10
Feature dimension
Feature dimension
Feature dimension 1
5
5
2
0
0-
-2
-2
15%
outliers
30% outliers
45% % outliers
-4
-4
-4
-4
-2
10
-4
-2
2
10
-4
-2
0
2
10
Feature dimension
Feature dimension
Feature dimension 2
Figure 2: Different mean estimators in the presence of outliers. The clean samples are the majority of data points following the Gaussian distribution AV((,, 0), 1- 1). while the outliers are data points that deviate significantly from the main data pattern, following (V( 8), 0.5 /). fz-estimator deviates far from the mean, while the -based estimator is more resistant outliers. However, as the ratio of outliers escalates, the ba-aae estimator encounters a greater shift from the true mean, but our estimator still maintains a position close the ground truth
Bias of based Estimation. In the literature of nigh-dimensiooal statistics, it has been well understood that the ε regularization will induce an estimation bias. In the context of denoising (21] or variable selection [22]. small coefficients 3 are undesirable. To exclude small 3 in the estimation, a toftthhresholding operator can be derived as (3) = sign(8) max(]3] - X, 0). As a result, large 8 are also shrunk by constant, the & estimation is biased towards zero.
similar bias effect also occurs in graph signal estimation the presence of adversarial attacks. For example, in TWIRLS (Eq. (T), after the graph aggregation f(l++1) = ΣjeN(a) Wiys (k) where Wi = f - fy ||- the edge difference f. f, will shrink towards zero. Consequently, every adversarial edge the attacker adds will induce bias that can be accumulated and amplified when the attack budget scales up.
Numerical Simulation. To provide a more intuitive illustration of the estimation bias of 6 based models, we simulate a mean estimation problem on synthetic data since most message passing schemes in GNNs essentially estimate the mean of neighboring node features. The results in Figure]

---

shows that & b1-based estimator is more resistant than & b2-based estimator. However, as the ratio of outliers escalates, the bassed estimator encounters greater shift from the true mean due the accumulated bias caused by outliers. This observation explains why &1-based graph smoothing models suffer from catastrophic degradation under large attack budgets. The detailed simulation settings and results are available in Appendix A.
3 Robust GNNs with Unbiased Aggregation
In this section, we first design a robust unbiased estimator to reduce the bias in graph signal estimation in Section 3.1 and propose efficient second-order IRLS algorithm compute the robust estimator with theoretical convergence guarantees Section 3.2 Finally, we unroll the proposed algorithm as the robust unbiased feature aggregation layers in GNNs in Section 3.3
3.1 Robust and Unbiased Graph Signal Estimator
Our study and analysis Section 2 have shown that while 4 -base methods outperform fg-based methods in robustness, they still suffer from the accumulated estimation bias, leading to severe performance degradation under large perturbation budgets. This motivates us to design robust and unbiased graph signal estimator that derives unbiased robust aggregation for GNNs with stronger resilience to attacks.
Theoretically, the estimation bias in Lasso regression has been discovered and analyzed in high- dimensional statistics (23]. Statisticians have proposed adaptive Lasso [2 and many non-convex penalties such as Smoothly Clipped Absolute Deviation (SCAD) 24 and Minimax Concave Penalty (MCP) (25) to alleviate this bias. Motivated by these advancements, we propose Robust and Unbiased Graph signal Estimator (RUGE) as follows:
arg min H((F) = E
Eall
S:
1+
f:
(0))
(3)
Vd.
Vd,
(5)EE
LEV
where P.y (y) denotes the function that penalizes the feature differences on edges by MCP:
y 24
if
P+
i
As shown in Figure 3 MCP closely approximates the E norm when y² is negligible, and it becomes y is small since the quadratic term 27
MCP
constant value when y is large. This transition be adjusted by the thresholding parameter y. When approaches infinity, the penalty (1) reduces the ε norm. Conversely, when 7 is very small, the "valley" of P.y near zero is exceptionally sharp, so (x( approaches the tn norm and becomes constant for slightly larger This enables RUGE to suppress smoothing on edges whose node differences exceeding the threshold y. This not only mitigates the estimation bias against outliers but also maintains the estimation accuracy the absence of outliers, The simulation in Figure ? verifies that our proposed estimator (1)(x) p.y (yy[|< (||=||2)) can recover the true mean despite the increasing outlier ratio when the outlier ratio is below the theoretical optimal breakdown point.
ply
0
1
2(v)
y
Figure 3: Penalties.
3.2 Quasi-Newton IRLS
Despite the advantages discussed above, the proposed RUGE Eq. (3) is non-smooth and non-convex, which results in challenges for deriving efficient numerical solutions that can be readily unfolded as neural network layers. the literature, researchers have developed optimization algorithms for MCP-related problems, such as the Alternating Direction Multiplier Method (ADMM) and Newton- type algorithms 24 25 26). However, due to their excessive computation and memory requirements well as the incompatibility with back propagatpon training, these algorithms are not well-suited
5

---

for the construction of feature aggregation layers in GNNs. To solve these challenges, we propose an efficient Quasi-Newton Iteratively Reweighted Least Squares algorithm (QN-IRLS) to solve the estimation problem in Eq.
IRLS. Before stepping into our QN-IRLS, we first introduce the main idea of iteratively reweighted least squares (IRLS) (27) and analyze its weakness in convergence. IRLS aims to circumvent the non-smooth F() in Eq. (3 by computing its quadratic upper bound H. based on F in each
iteration & and optimizing H(F)::
P((F) = Σ
w
f. Vd.
2 Vd,
f3
+ + +
f - f: -1
(5)
12
(i,)EE
iEV
(M) - |s, /Vd, 515// /V and p-(() is the where Vig MCP function. For the detailed proof of the upper bound, please refer to Lemma in Appendix B Then, each iterative step of IRLS can be formulated as the first-order gradient descent for H(F))
where w((h) if 1 Kijj
4p.(ues)
dai; Moo W
0k
((++1)= (()) (F())
(b))
(1)()) (W ()F(M) 22F()).
(6)
where 17 is the step size, Q(K) 2 2(diag(( (1**)) ) +1), and qm
(ag
(A:)
wi(k) mj Ams/ Its convergence
condition is given in Theorem [ with proof in Appendix B
Theorem If F(k) follows the update rule in Eq. (6) where p defining W satisfies that doly) is non-decreasing Vy E (0, oc), then sufficient condition for H (F(++1)) S H(F(k)) is that the step size o7 satisfies 1) S |diag(a (
w() À + AlIlo
Quasi-Newton IRLS. Theorem | suggests the difficulty in the proper selection of stepsize for (first-order) IRLS due to its non-trivial dependency on the graph (A) and the dynamic terms (x) and ( The dilemma is that small stepsize will lead to slow convergence but a large step easily causes divergence and instability as verified by our experiments in Section 4.3 (Figrue 5 which reveals its critical shortcoming for the construction of GNN layers.
To overcome this limitation, we aim to propose a second-order Newton method, F(++1) ((K) - (F")("")))~
to achieve faster convergence and stepsize-free hyperparam- eter tuning by better capturing the geometry of the optimization landscape. However, obtaining the analytic expression for the inverse Hessian matrix (F((((()))) E R="x is intractable, and the numerical solution requires expensive computation for large graphs. Therefore, we pro- pose novel Quasi-Newton IRLS algorithm (QN-IRLS) that approximates the Hessian matrix (²H(((())) 2(diag( (g(*)) (k) @ Á + Af) by the diagonal matrix Q(k) 2(diag(a(*)) AT)
such that the inverse is trivial. The proposed QN-IRLS works as follows:
p(++1) (() (Q - (diag(g +X) (IW o ()F()) + XE (7)
where (Q (x))) automatically adjusts the per-coordinate stepsize according to the local geometry of the optimization landscape, (*)) and (A) are defined as in Eq. (5) and (6). In this way. QN-IRLS provides faster convergence without needing to select a stepsize. The convergence is guaranteed by Theorem with the proof Appendix B
Theorem If F(++1) follows update rule in Eq. 7 where satisfies that dp(y) is non-decreasing dy²
vy E (0, oo), it is guaranteed that H ((F(++)) < H(F(M))
3.3 GNN with Robust Unbiased Aggregation
'Wi is defined dely) dy* yy (k) so that the quadratic upper bound A is tight (P()) according to Lemma
The diagonal terms of W are set to zero to avoid undefined derivative of de(s) as discussed in Remark 2 dy
'A related work [14 adopts IRI.S algorithm optimize the problem Eq. A preconditioned version
proposed to handle the unnormalized graph Laplacian, but its step size needs to satisfy 1) S |A T (()) A+ shown in Lemma 3.3 of [14) which expensive estimate.

---

The proposed QN-IRLS provides an efficient algorithm to optimize the RUGE in Eq. ( with a theoretical convergence guarantee. Instantiated with / Pr. each iteration in QN-IRLS in Eq. 7 can be used as one layer in GNNs, which yields the Robust Unbiased Aggregation (RUNG):
RUGE
3
2
W.
F((+1) (diag(q + (WW()) A) + > (8)
0
where (1) = Ej wilh)
Amj/dm. as in Eq. my
6
((())
0
1
21y)
1 Lizy m0 J + and Vij
1
Figure 4: do(y).
Vdd
vd,
dy
Interpretability. The proposed RUNG can be interpreted intuitively with edge reweighting. In
Eq. (8) the normalized adjacency matrix Á is reweighted by W(k), where w do(u)
dy
(4) y=
shown in Figure 4 that Wiy becomes zero for any edge e (i, with a node difference Vij 2 % thus pruning suspicious edges. This implies RUNG's strong robustness under large-budget adversarial attacks. With the inclusion of the skip connection F (hag(q()) + AI can be seen as a normalizer of the layer output.
(k)
Relations with Existing GNNs. RUNG can adopt different p that Theorem aallows, thus covering many classic GNNs as special cases. When p(y) y², RUNG in Eq. (8) exactly reduces to (F(++1)
APPNP 28
1 (F()) + A F()) and GCN (F(++1) AF()) if chosing À = 0. 1
When ply) = y, the objective of RUGE is equivalent to ElasticGNN with p 2, which is analogous to SoftMedian and TWIRLS due to their inherent connections as fi-based graph smoothing.
Complexity analysis. RUNG is scalable with time complexity of (() and space complexity O(m + nd), where m is the number of edges, d is the number of features, n is the number nodes, and & is the number of GNN layers. Therefore, the complexity of our RUNG is comparable normal GCN (with a constant difference) and it is feasible to implement. The detailed discussions about computation efficiency can be found in Appendix C
Experiment
In this section, we perform comprehensive experiments to validate the robustness of the proposed RUNG. Besides, ablation studies show its convergence and defense mechanism.
4.1 Experiment Setting
Datasets. We test our RUNG with the node classification task on two widely used real- world citation networks, Cora ML and Citeseer [29]. as well as a large-scale networks Ogbn-Arxiv [30]. We adopt the data split of 10% training, 10% validation, and 80% testing, and report the classification accuracy of the attacked nodes following [ Each experiment is averaged over 5 different random splits.
Baselines. To evaluate the performance of RUNG, we compare it to lg other representative baselines. Among them, MLP, GCN (16), APPNP (28), and GAT 31 are undefended vanilla models. GNN- Jaccard-GCN (). SVD-GCN (7), EvenNet (32),
Guard (2). RGCN (1I. GRAND (8) ProGNN
3
R4 are representative robust GNNs. Besides, Soft- Median and TWIRLS are representative methods with & bbased graph smoothing Fl We also evaluate a variant of TWIRLS with thresholding attention (TWIRLS-T), For RUNG, we test two variants: default RUNG (Eq. (8) and RUNG-L, with &1 penalty (p(y) v).
HANG 13), NoisyGNN [R]] and GARNET
The model hyperparameters including learning rate, weight decay, and dropout rate are tuned as in [5]. Other hyperparameters follow the settings in the original papers. RUNG uses an MLP connected 10 graph aggregation layers following the decoupled GNN architecture of APPNP. Ā = I#X is tuned in (0.7. 0.8, 0.9), and tuned in {0.5, 1, 2, 5). We chose the
Hyperparameters.
We do not include ElasticGNN because it is still unclear how to attack it adaptively due to its special incident matrix formulation [15.. In the preliminary study (Section 2.1. we evaluate the robustness of ElasticGNN following the unit test setting proposed in [5].
7

---

hyperparameter setting that yields the best robustness without notable impact (smaller than 1%) on the clean accuracy following [35]
Attack setting. We use the PGD attack 36 to execute the adaptive evasion and poisoning topology attack since it delivers the strongest attack in most settings [5]. The adaptive attack setting provided in Appendix F The adversarial attacks aim to misclassify specific target nodes (local attack) or the entire set of test nodes (global attack). To avoid false sense of robustness, our adaptive attacks directly target the victim model instead of the surrogate model. Additionally, we include the transfer attacks with 2-layer GCN as the surrogate model. We also include graph injection attack following the setting in TDGIA 37
4.2
Adversarial Robustness
Table 1: Adaptive local attack Cora ML.
The best and second marked.
Model
0% (Clcan)
20%
50%
100%
150%
200%
MLP
72.6 + 6.4
72.6
72.6 + 6.4
72.6 + 6.4
72.6 6.4
72.6 6.4
GCN
82.7
10.2
12.0 6.2
2.7
0.0
0.0 0.0
APPNP
84.7 6.8
50.0 13.0
27.3
14.0+ 5.3
3.3
0.7
GAT
80.7 10.0
30.7 + 16.1
16.0 12.2
11.345
1.6
2.0 = 1.6
GNNGuard
44.0 6.7
30.6
6.80
5.3
2.0 2.7
RGCN
84.6
9.3
8.1
6.0
0.0
0.0
GRAND
84.0
1.0
18.7
7.3
1.
0.0
ProGNN
6.2
10.4
21.3
2.0
0.0
0.0
Jaccard-GCN
8.0
6.8
1.9
1.7
0.7
0.3
GARNET
8.8
7.5
7.9
42.7
11643.
9.6
HANG
8.41
7.2
6.3
39.5
9.4
5.6 2.3
NoisyGNN
8.6
5.7
4.2
36.1+445
5.8
4.1 1.2
EvenNet
8.1
6.9
5..1
2.3
3.1
1.1 1.3
GraphCON
8.1
7.3
54.7
4.2
4.1
2.3 1.2 1.2
SoftMedian
80.0
13.7
12.7
41.
8.0
8.7
TWIRLS
83.3
8.6
60.7
3..0
20.7
12.0 6.9
TWIRLS-T
4.5
4.4
7.
6.27
44.0
40.7 = 11.8
RUNG-E, (Our))
84.0
7.17
11.2
53.3
22.0
14.0 + 7.4
RUNG (Ours)
84.0 5.3
75.3 6.9
7.5
70.7 1 10.6
69.3 9.8
69.3 9.0
Table 2: Adaptive global attack on Cora ML.
The best and second are marked.
Model
0% (Clcan)
5%
10%
20%
30%
40%
MLP
65.0 + 1.0
65.0 = 1.0
65.0 +: 1.0
65.0 + 1.0
65.0 + 1.0
65.0 + 1.0
GCN
85.0 0.4
75.3
0.5
69.6 + 0.5
60.9 1: 0.7
51.2 0.6
48.4 0.5
APPNP
86.3
75.8
69.7 0.7
60.3 0.9
53.8 1.2
49.0 1.6
GAT
83.5 0.5
75.8 = 0.8
71.2 1.2
65.0 0.9
60.5
56.7 0.9
GNNGuard
0.7 85.7
74.6 0.7
70.2
63.1
57.5
51.0
RGCN
75.0 0.8
69.1
5.78
46.1 0.7
GRAND
8.71
76.2 0.8
0.7
6.7
56.7
51.9 0.9
ProGNN
85.6
76.5
0.5
6.70
56.8 0.7
51.3+
Jaccard-GCN
83.7
73.9 0.5
0.7
1.1
54.0
49.1
GARNET
0.5
76.5 0.4
7.11
0.7
6..
58.7 1.5
HANG
8.22
75.7 1 0.6
74.21
6.4
6..9
58.4 0.1
NoIsyGNN
0.5
76.7 0.1
72.1
6.7
58.0
53.3 0.6
EvenNet
8.9
75.8 0.9
70.7
0.5
0.7
54.7 0.8
GraphCON
0.6
75.8
7.
0.7
62.2
56.6
SoftMedian
8.70
78.6=0.3
0.9
0.55
0.8
58.1 0.7
TWIRLS
8.22
0.8
0.3
66.920.2
58.7 0.64
TWIRLS-T
8.5
76.8
7..2
6.47
0.2
60.8+033
RUNG-& (Ours)
85.8 0.5
78.4 0.4
74.3
68.1
63.5 0.7
59.8 + 0.8
RUNG (Ours)
84.6 0.5
0..
75.7
6.3 0.4
6..1+112

---

ON-IRLS
IRLS 7
1e7
n=
IRLS, 0.6
Densiyy function a.u.
1o4
-X-
0.6
f
16-
0.4
RUNG
2
0.2
1.0
0.0
10
Layer
Dudget 1%
Feature difference
Figure 5: Convergence of our
Figure 6: Bias induced by
Figure 7: Distribution of feature difference on attacked edges.
QN-IRLS compared to IRLS.
different attack budgets.
Here we evaluate the the performance of RUNG against the baselines under different settings. The results of local and global adaptive attacks on Cora ML are presented in Table I Jnnd Table 2, while those on Citeseer are presented in Table 3 and Table 4 in Appendix E due to space limits. We summarize the following analysis from Cora MI., noting that the same observations apply to Citeseer.
Under adaptive attacks, many existing defenses are not significantly more robust than undefended models. The f--aee models such TWIRLS, SoftMedian, and RUNG-&, demonstrate consider- able and closely aligned robustness under both local and global attacks, which supports our unified b-aaed robust view analysis in Section 2.2]
RUNG exhibits sigmificant improvements over all baselines across various budgets under both global and local attacks. Local attacks stronger than global attacks since local attacks concentrate targeted nodes. The robustness improvement of RUNG appears to be more remarkable in local attacks.
When there no attack, RUNG largely preserves an excellent clean performance. RUNG also achieves state-of-the-an tfrttr-rrt performance under small attack budgets.
4.3 Ablation study
Convergence. To verify the advantage of our QN-IRLS method in Eq 7 over the first-order IRLS in Eq (6). we show the objective H on each layer in Figure It can be observed that our stepsize-frre QN-IRLS demonstrates the best convergence discussed in Section
Estimation bias. The bias effect in basedd GNNs and the unbiasedness of our RUNG can be empirically verified. We quantify the bias with Eiey ll 1l. where f. and f. denote the aggregated feature on the clean graph and attacked graph, respectively. As shown in in/Fur 6 when the budget scales up, & GNNs exhibit notable bias, whereas RUNG has nearly zero bias. We provide comprehensive discussion of unbiasedness of RUNG in Appendix D
Defense Mechanism To further investigate how our defense takes effect, we analyze the edges added under adaptive attacks. The distribution of the node feature differences f/ / f// Vd of attacked edges is shown in Figure for different graph signal estimators. It can be observed that our RUNG forces the attacker to focus on the edges with a small feature difference, indicating that RUNG improve robustness by doig-weighting pruning some malicious edges that connect distinct nodes. Therefore, the attacks become less influential, which explains why RUNG demonstrates outstanding robustness.
Transfer Attacks. In addition to the adaptive attack, we also conduct a set of transfer attacks that take every baseline GNN the surrogate model to comprehensively test the robustness of RUNG, following the unit test attack protocol proposed [5]. We summarize the results on Cora ML and Citeseer in Figure 9 and Figure 10 Appendix E due to space limits. All transfer attacks are weaker than the adaptive attack in Section 4.2 indicating the necessity to evaluate the strongest adaptive attack to avoid the false sense of security emphasized in this paper. Note that the attack transferred from RUNG model is slightly weaker than the adaptive attack since the surrogate and victim RUNG models have different model parameters in the transfer attack setting.
Hyperparameters. Due to the space limit, we provide the additional ablation studies on hyperparameters (including and À in MCP as well the number of layers) of RUNG in Appendix

---

The results offer an overview strategy for the choice of optimal hyperparameters. We can observe that y in MCP has significant impact on the performance of RUNG. Specifically. larger y makes RUNG closer to an f1-based model, while smaller encourages more edges to be pruned. This pruning helps RUNG to remove more malicious edges and improve robustness, although a small ? may slightly reduce clean performance.
Robustness under various scenarios. Besides the evaluation under strong adaptive attacks, we also validate the consistent effectiivnness of our proposed RUNG under various scenarios, including Trans- fer attacks (Appendix E.2 Poisoning attacks (Appendix E.3). Large scale datasets (Appendix E.4 Adversarial training (Appendix E.5), Graph injection attacks (Appendix E.6).
5 Related Work
To the best our knowledge, although there are works unifying existing GNNs from a graph signal denoising perspective (20), no work has been dedicated to uniformly understand the robustness and limitations of robust GNNs such as SoftMedian [4) SoftMedoid [18]. TWIRLS [1). Elas- ticGNN [15), and TVGNN [19] from the & robust statistics and bias analysis perspectives. To mitigate the estimation bias, MCP penalty is promising since it is well known for its near unbiased- ness property (25 and has been applied to the graph trend filtering problem (26] to promote piecewise signal modeling, but their robustness is unexplored. Nevertheless, other robust GNNs have utilized alternative penalties that might alleviate the bias effect. For example, GNNGuard 2 prunes the edges whose cosine similarity is too small. Another example is that TWIRLS [4] with a thresholding penalty can also exclude edges using graph attention. However, the design of their edge weighting or graph attention is heuristic-based and exhibits suboptimal performance compared to the RUNG proposed in this work.
6 Conclusion & Limitation
In this work, we propose unified view of & robust graph smoothing to uniformly understand the robustness and limitations of representative robust GNNs. The established view not only justifies their improved and closely aligned robustness but also explains their severe performance degradation under large attack budgets by novel estimation bias analysis. To mitigate the estimation bias, we propose robust and unbiased graph signal estimator. To solve this non-trivial estimation problem, we design a novel and efficient Quasi-Newton IRLS algorithm that can better capture the landscape of the optimization problem and converge stably with theoretical guarantee. This algorithm can be unfolded and used as a building block for constructing robust GNNs with Robust Unbiased Aggregation (RUNG). As verified by experiments, RUNG provides the best performance under strong adaptive attacks among all the baselines. Furthermore, RUNG also covers many classic GNNs special cases. Most importantly, this work provides deeper understanding of existing approaches and reveals principled direction for designing robust GNNs.
Regarding the limitations, first, the improvement of RUNG is more significant under large budgets compared to the robust baselines. Second, we primarily include experiments on homophilic graphs generalize the proposed robust aggregation to heterophilic graphs in
in the main paper, but future work. Third, although our Quasi-Newton IRLS algorithm has exhibited excellent convergence compared to the vanilla IRLS, the efficiency of RUNG could be further improved.
Acknowledgment
Zhichao Hou and Dr. Xiaorui Liu are supported by the National Science Foundation (NSF) National AI Research Resource Pilot Award, Amazon Research Award, NCSU Data Science Academy Seed Grant Award, and NCSU Faculty Research and Professional Development Award.
10

---

References
[1] Yao Ma and Jiliang Tang. Deep learning on graphs. Cambridge University Press, 2021.
[2] Xiang Zhang and Marinka Zitnik. Gunguard: Defending graph neural networks against adversarial attacks. Advances in neural information processing systems, 33:9263-9275, 2020.
[3] Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining. pages 66-74, 2020.
[4] Simon Geisler, Tobias Schmidt, Hakan Sirin, Daniel Zügner, Aleksandar Bojchevski, and Stephan Günnemann, Robustness of graph neural networks at scale. In M. Ranzato, A. Beygelz- imer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 7637-7649. Curran Associates, Inc., 2021.
[5] Felix Mujkanovic, Simon Geisler, Stephan Günnnemann, and Aleksandar Bojchevski. Are defenses for graph neural networks robust? In Neural Information Processing Systems, NeurIPS, 2022.
[6] Huijun Wu, Chen Wang, Yuriy Tyshetskiy, Andrew Docherty, Kai Lu, and Liming Zhu. Ad- versarial examples on graph data: Deep insights into attack and defense. arXiv preprint 1rXiv:1933.01610, 2019.
[7] Negin Entezari. Saba A Al-Sayouri, Amirali Darvishzadeh, and Evangelos E Papalexakis. All you need is low (rank) defending against adversarial attacks on graphs. In Proceedings of the 1 3th International Conference on Web Search and Data Mining, pages 169-177, 2020.
[8] Wenzheng Feng, Jie Zhang, Yuxiao Dong, Yu Han, Huanbo Luan, Qian Xu, Qiang Yang, Evgeny Kharlamov, and Jie Tang. Graph random neural networks for semi-supervised learning on graphs. Advances neural information processing systems, 33:22092-22111 2020.
[9] Zhijie Deng, Yinpeng Dong, and Jun Zhu. Batch virtual adversarial training for graph convolu- tional networks. Al Open, 2023.
[10] Jinyin Chen, Xiang Lin, Hui Xiong, Yangyang Wu, Haibin Zheng, and Qi Xuan. Smoothing adversarial training for gnn. IEEE Transactions on Computational Social Systems, 8(3):688-66) 8-699, 2020.
[11] Dingyuan Zhu, Ziwei Zhang, Peng Cui, and Wenwu Zhu Robust graph convolutional networks against adversarial attacks. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pages 1399-1401, 1407, 2019.
[12] Konstantin Rusch, Ben Chamberlain, James Rowbottom, Siddhartha Mishra, and Michael Bronstein. Graph-coupled oscillator networks. In International Conference on Machine Learning, pages 18989. PMLR, 2022.
[13] Kai Zhao, Qiyu Kang, Yang Song, Rui She, Sijie Wang, and Wee Peng Tay. Adversarial robustness in graph neural networks: A hamiltonian approach. Advances in Neural Information Processing Systems, 36, 2024.
[14] Yongyi Yang, Tang Liu, Yangkun Wang, Jinjing Zhou, Quan Gan, Zhewei Wei, Zheng Zhang, Zengfeng Huang, and David Wipf. Graph neural networks inspired by classical iterative algorithms. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 11773-11783, PMLR, 18-24 Jul 2021.
[15] Xiaorui Liu, Wei Jin, Yao Ma, Yaxin Li. Hua Liu, Yiqi Wang, Ming Yan, and Jiliang Tang. Elastic graph neural networks. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 6837-6849. PMLR, 18 28-24JJ Jul 2021.
[16) Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv: 12Xv:16609.0997,, 2016.

---

[17] Peter Huber. Robust statistics, volume 523. John Wiley & Sons, 2004.
[18] Simon Geisler, Daniel Zügner, and Stephan Günnemann. Reliable graph neural networks via robust aggregation. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS'20, Red Hook, NY, USA, 2020. Curran Associates Inc.
[19] Jonas Berg Hansen and Filippo Maria Bianchi. Total variation graph neural networks. In Proceedings of the 40th international conference Machine learning. ACM, 2023.
[20] Yao Ma, Xiaorui Liu, Tong Zhao, Yozen Liu, Jiliang Tang, and Neil Shah. A unified view on graph neural networks graph signal denoising. In Proceedings of the 30th ACM International Conference on Information Knowledge Management, CIKM '21, page 222-12111 New York, NY, USA, 2021. Association for Computing Machinery.
[21] David L Donoho. De-noising by soft-thresholding IEEE transactions on information theory, 41(3):613-627, 1995.
[22] Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society. Series B (Methodological), 58(1):267-288, 1996.
[23] Hui Zou. The adaptive lasso and its oracle properties. Journal of the American Statistical Association, 101(476):14181422) 2006.
[24] Jianqing Fan and Runze Li. Variable selection via nonconcave penalized likelihood and its oracle properties. Journal of the American Statistical Association, (144566::348-1366 2001.
[25] Cun-Hui Zhang. Nearly unbiased variable selection under minimax concave penalty, The Annals of Statistics, 38(2):894 942, 942,2010, 2010.
[26] Rohan Varma, Harlin Lee, Jelena Kovačević, and Yuejie Chi. Vector-valued graph trend filtering with non-convex penalties. IEEE transactions on signal and information processing over networks, 6:48 62, 2019.
[27] Paul W Holland and Roy Welsch. Robust regression using iteratively reweighted least-squares. Communications in Statistics-theory and Methods, 6(9): 1-8877,, 1977.
[28] Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv:/8/0.059977 2018.
[29] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al magazine, 29(3):93-92 2008.
[30] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:22118 18-22133, 2020.
[31] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, Yoshua Bengio, et al. Graph attention networks. star, 1050((0): 48-585 2017.
[32] Runlin Lei, Zhen Wang, Yaliang Li, Bolin Ding, and Zhewei Wei. Evennet: Ignoring odd-hop neighbors improves robustness of graph neural networks. Advances in Neural Information Processing Systems. 35:4694-4706, 2022.
[33] Sofiane Ennadir, Yassine Abbahaddou, Johannes F Lutzeyer, Michalis Vazirgiannis, and Henrik Boström. A simple and yet fairly effective defense for graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 21063-21071, 2024
[34] Chenhui Deng, Xiuyu Li, Zhuo Feng, and Zhiru Zhang. Garnet: Reduced-rank topology learning for robust and scalable graph neural networks. In Learning on Graphs Conference, pages 3-1. PMLR, 2022.
[35] Aleksandar Bojehevski and Stephan Günnemann. Certifiable robustness to graph perturbations. In Neural Information Processing Systems, 2019.
12

---

[36] Kaidi Xu, Hongge Chen, Sijia Liu, Pin- Yu Chen, Tsui- Tsu Weng, Mingyi Hong, and Xue Lin. Topology attack and defense for graph neural networks: an optimization perspective. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pages 3961-3967, 2019.
[37] Xu Zou, Qinkai Zheng, Yuxiao Dong, Xinyu Guan, Evgeny Kharlamov, Jialiang Lu, and Jie Tang. Tdgia: Effective injection attacks on graph neural networks. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 2461-2471, 2021.
[38] Emmanuel J. Candès, Michael B. Wakin, and Stephen P. Boyd. Enhancing sparsity by reweighted li minimization. Journal of Fourier Analysis and Applications, 14(5-6):877-95, Dec 2008. Funding by NSF.
[39] Amir Beck and Shoham Sabach. Weiszfeld's method: Old and new results. Journal of Optimization Theory and Applications, 164(1):1-44) 2015.
[40] Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society Series B: Statistical Methodology, 58(1):267-288, 1996.
[41] Cun-Hui Zhang. Nearly unbiased variable selection under minimax concave penalty. 2010.
[42] Simon Geisler, Tobias Schmidt, Hakan Şirin, Daniel Züggerr, Aleksandar Bojchevski, and Stephan Günnemann. Robustness of graph neural networks at scale. Advances in Neural Information Processing Systems, 34:7637-7649, 2021.
13

---

A Bias Accumulation of & Models
A.1 Details of the Numerical Simulation Settings
To provide a more intuitive illustration of the estimation biases of different models, we simulate mean estimation problem on synthetic data since most message passing schemes in GNNs essentially estimate the mean of neighboring node features. In the context of mean estimation, the bias is measured as the distances between different mean estimators and the true mean. We firstly generated clean samples { (blue dots) and the outlier samples {æ; J (red dots) from 2-dimensional Gaussian distributions, (VO,, 0), 1) and (V(8, 8), 0.5), respectively. We calculate the mean of clean samples n
1 Σi= 3; as the ground truth of the mean estimator. Then we estimate the mean of all the
samples by solving arg min Di=1 17(2 xx;) using the Weiszfeld method
38 39 where 17(-) can
take different norms such as Eg norm || 112 and & norm 112-
The mean estimators are formulated as minimization operators
= arg min
Σ
n1 - -x;),
(9)
where n is the number clean samples and m the number of adversarial samples.
& estimator. The & estimator (n(y) == |1vl))), essentially is the geometric median. We adopted the Weiszfeld method iteratively reweight z to minimize the objective, following
E; w a7
(k+1)
(10)
Σ, w (b)
where w(th) [|=(1) This can be seen as gradient descent step of (k++) (k)
-4)- aVz Σ, || we 22 (k-1)) Ex [ - Taking
Σ. ! instantly yields Eq. 10
MCP-based estimator. We therefore adopt similar approach for the MCP-based estimator ("Ours" Fig. Figure 2). where 77(3) == (y)
(k+1) (k) - av Σ Pr (|( 2rel12)
(11)
= (k) Σ max(O, ||((]] 201112 7
1
1 (z xz). (12)
Denoting max(0, (1z
0z 10il221
4) as wi and then a E.w. yields a similar reweighting
iteration z (1++) E. (1))
E. (0(
l estimator. It is worth noting that the same technique can be applied to the l estimator with p(z) = || The iteration becomes
(1++1) (R) -V Σ x. 11
(13)
= =((k) (k) -xa),
(14)
and a = 1 iteration.
n+m yields z (k+1)
1+m E, Di, which gives the mean of all samples in one single
Similarities between this mean estimation scenario and our QN-IRLS in graph smoothing can be observed, both of which involve iterative reweighting estimate similar objectives. The approximated Hessian in our QN-IRLS resembles the Weiszfeld method, canceling the 2(k) by tuning the stepsize.
In Figure we visualize the generated clean samples and outliers, as well as the ground truth means and the mean estimators with 17(-) || 112 or - l]a under different outlier ratios (15%,
14

---

30%, 45%). The results show that the E2-based estimator deviates far from the true mean, while the bbased estimator is more resistant outliers, which explains why éb-bsed methods exhibit stronger robustness. However, as the ratio of outliers escalates, the -baased estimator encounters greater shift from the true mean due to the accumulated bias caused by outliers. This observation explains why f1-based graph smoothing models suffer from catastrophic degradation under large attack budgets. Our estimator keeps much closer to the ground truth than other estimators with the existence of outliers.
A.2 Additional Simulation Results and Discussions
Here, we complement Figure 2 with the settings of higher attack budgets. As the outlier ratio exceeds the breakdown point 50%, observe that our MCP- based mean estimator can correctly recover the majority the samples, i.e. converge to the center of "outliers".
trajectory
Clean sample
Inttial
dimension
0-
-2-
10% outliers
25% outliers
40% outliers
10
Feature dimennsin 2
5-
2-
-2
60% outliers
75% outliers
90% outliers
-4
-4
-2
10
-4 -2
10
-4
10
dimension
Feature dimension
dimension
Figure 8: The trajectory of our MCP-based mean estimator.
B Convergence Analysis
To begin with, we will provide overview of our proof, followed by detailed presentation of the formal proof for the convergence analysis.
Overview of proof. First, for both IRLS and QN-IRLS, construct, for F(k) in every iteration k quadratic upper bound H that satisfies H C H where the equality is reached F()), Then we can minimize H. to guarantee the iterative descent H. since H(F(++1) H(F((+1)) C' s Ai ((()))) + C H(F(())
To find the (k-1) such that ((F((+))) < (((()))) IRLS simply adopts the plain gradient descent [(++1) = (h) - (FV((((()) whose convergence condition can analyzed with the 3-smoothness of the quadratic 7l TTheorem 1.. To address the problems of IRLS as motivated in Section 3.2 our Quasi-Newton IRLS utilizes the diagonal approximate Hessian Q to scale the update step size in different dimensions respectively ((k+1) = (k) Q (-(()(F())) Thereafter, by bounding the
Hessian with 2Q, the descent condition of 7 is simplified Theorem 2
15

---

Lemma For any ply) satisfying doly) is non-increasing, denote Vij dy²
ft
f1
then
Va.
vag
H(F) E(o.)e,,ss p(yis) +
EiEv IIfe 5:0 has the following upper bound:
H(F) S SH(F) +C
E
W vi
+
Σ II: 8 12 C
(15)
(KJ)EEEiss
where w (k)
80(z)
ān²² 1y
(2) and
Vig
g(h) va,
vd
{1th)
and C = )(((()) - is constant.
The equality in Eq. (15 is achieved when F F(k).
Proof. Let u = y² and define ((v) = ply) = plVo). Then vp is concave since de(e) dply) is du
dy"
non-increasing. According the concavity property, have rb(v) v/(v)) v (v(()] 1= Substitute e = y² Uo = Vū, we obtain:
v0)
2 Op(y)
pp(ly)
p(v) S y Oy²
30
0y² y= p(y0)
(16)
y=
= 1² 3p(y)
+ +(vo)
(17)
Oy²
y=ya
where the inequality is reached when y Vo- Next, substitute y = Miy and yo = vij can get
(k)
p(yn)) S w yiy + Cly,,) (k)) which takes the equality at Usy Vij Finally, by summing up both sides and add regularization term, we can prove the Eq. 15
(k)
Remark 1. It can be seen that the definition of H depends on F(0), which ensures that the bound is tight when F = Fk)) This tight bound condition is essential in the magorizaatinnmmiiiiiaaatt minimization algorithm as seen in Theorem
Lemma 2. For H EiiseeE Woy Eiev IIf: 1.00
12g the gradient and Hessian w.r.l.
F satisfy
V Pm A((F= - (ddiag(()) W O À A+ -XF() -
(18)
mm
and
V Fmn V VF, H(F) = ((((F)))(ddd884)))) - W A+
(19)
where qm = E, W Amj/mm/dn and A.j =
Av is the symmetrically normalized adjacency v Vd,dz
matrix.
'Here are some explanations on tensor 'Hessian' H.H. Since F(FF) is dependent on a matrix, there are some difficulties in defining the Hessian. However, as can he observed in Eq. (27) and Eq. (32) the feature dimension can be accounted for by the following. Initially, we treat the feature dimension as an irrelevant dimension that is excluded from the matrix operations. E.g., FV"HF En, F,, Nyss Fki where the feature dimensions j and remain free indices while the node indices i and & are eliminated as dummy indices. Finally, take the trace of the resulting #feature #feature matrix to get the desired value.
16

---

Proof. Follow A AT and define
4
1
then the first-order gradient of
ddz
Eisiee W WasVey will be
V F Fm
E
Wwstey
(20)
(i
Outy
E
Wis FFmn
(21)
(1
Oymn
E
W
mi Wmi
(22)
(m.J)EE
2
Fmn dd
Fin
ddz
Σ (m.J)EE
W
Wmj
(23)
a Fmn
Fm
Fin
Σ (EN(m)
2W
mj
dm
V dmddy d
(24)
Ami
Ami
W my
Fun
Fjn)
(25)
dm
dmddj
Σ3 Wing Amjj
-2(
F 2((W 2 F)F) mn
(26)
dm
(2(diag(q) - W 3 A)F)
(27)
mn
and the second-orde order hessian will be:
Vi Fenn Flr
Σ
Wishhy
(28)
(KJ)
Oy
Σ
Wij
(29)
F
(15)EEE
Amj
Ami
-2 OFF
Σ Wmy!
Fmn
p(n)
(30)
dm
Amj
=2m
Σ Wms
(31)
Ddmd
-2(diag(q) W A)mkku
(32)
Remark 2. From Eq. (1 to Eq. (4). one can assume m. & (m)), and thus W...- However, as we know, self-loop is often added to A to facilitate stability by avoiding zero-degree nodes that cannot be normalized. This is not as problematic as seems, though. Because E(s.)EE $41 intrinsically excludes the diagonal terms, we can simply assign zero to the diagonal terms of W so that the term of j = m is still zero in Eq. 24 as defined in Eq. 55)
To minimize H. the gradient descent update rule takes the form of Eq. (6). One may assume that when 17 is chosen to be small enough, 7 ((((((++)) < (F(F()). For a formal justification, we have Theorem I to determine the convergence condition of n.
Theorem 1. If F(k) follows the update rule in Eq. (6) where the p satisfies that dply) is non-
dy" decreasing for y E (0, oo), then sufficient condition for ((F(++1) S H(((()) is that the step size
n satisfies 0 < 17 < [[diag((()) (k) @ A X1
17

---

Proof. The descent of (F) can ensure the descent of ((FF) since H(F((+1)) - H((((tt))) s
H(((()) H(F(k)). Therefore, we only need to prove H (F - H(F(()).
Noting that H is quadratic function and F(++1)
F(k)
- (())) then H ((F(+))) and
((((()) can be connected using Taylor expansion where VH and 42 is given in Lemma 2
*((((++1)) He (F(())
(33)
=tr (V((()())) (Fo( ( _F(k))
(34)
((E(tt)))F())) ((t)) (F ( p(()))
(35)
2
=tr (
(36)
+ tr VH((F()) T V (K) ( (A(()())
(37)
2
Insert (=)(((())) (d) w(k) @ À AI) from Lemma
into the above equation and we
can find a sufficient condition for #((F((+1)) v 7 F (k))
to be
1y ||dia(())
w (k) A + ÅI 22 00
(38)
or
S diag (q) ( C A + A
(39)
Now prove that when taking the MIasi-Newton-IRLS step in Eq. 7 the objective 7 is guaranteed to descend. Since the features in different dimensions are irrelevant, we simplify our notations if feature dimension was 1. One may easily recover the general scenario by taking the trace.
Lemma 3Q-V"H(1 positive semi-definite, where H E(LDEE Wistfy+ + E f! (0)
Q 2(diag (q) + XI), and qm E, Wmj Ami/ hmm/dm-
Proof. In Lemma 2 we have v²H((y) = 2(diag( (2) + AI W @ A), then
2Q v²H((y) 2((iag ( AI W @ Á).
(40)
Recall how we derived Eq.
27 from Eq.
15 where proved that
ft Vd,
f,
Σ
Will
l1 tr (F (diag q) W 3 A)F),
(41)
Vd,
(1
which holds for all F. Similarly, the equation still holds after flipping the sign before f,/ / dj and @ A. We then have this inequality: VF,
A 0 0
0 Σ
W
f
f, Vdz
f
tr(F F (diag(q) + W W A)F)
(42)
Vd
Str(F" (diag( ④ + W 3 Ā AT)F).
(43)
Thus, (diag(q) W À AT) 0. and thus 2Q (2H(()) 2 0.
Using Lemma 1 and Lemma 3 we can prove Theorem
Note that we continue assume #feature
for simplicity but without loss of generality 0
Theorem 2. If ((++)) follows update rule Eq. 7 where p satisfies that dply) Vy E (0, oo), it is guaranteed that H. H((((++1) I H(F())).
non-decreasing
dg
18

---

Following the discussions in Theorem the quadratic H. we have:
Proof.
we only need to prove R((F((+1)) & (((F(()))
H(x) = Fl(y) + vH(y)) (( - y) 1 (x---))
y---y) v) ( (>)((()) - v).
(44)
We can define Q(y) (2( in Lemma 3 such that Q(y) (²) ž 0. then
Vz, = 2(y)= 2 (²H(y)z
(45)
Then an upper bound of (a) can be found by inserting Eq. 45 into Eq. (4
1(xx) - Rg) + Vil (a y) x y) Qyy) y).
(46)
Then, insert Q = 2Q into Eq. (46). Note that Q = 2(diag(q) + AI), so Q = and QT =
Q
Thereafter, the update rule æ
1-1 in Eq. 7 gives
H((r) H(y)
(47)
<Vi(l)) (x y) / [(y))( y)
(48)
-VA(y) y) +2 (0 v)) (Q) - v)
(49)
-2V villy) -VV--- (Q T) )v)l())
(50)
=0.
(51)
Therefore, our QN-IRLS Eq. is guaranteed descend.
L
C Computation Efficiency
Our RUNG model preserves udvantagcous efficiency even adopting the quasi-Newton IRLS algorithm.
C.1 Time Complexity Analysis
Each RUNG layer involves computing W, and the subsequent aggregations. We elaborate on them one by one. We denote the number of feature dimensions d, the number of nodes n, and the number of edges which are assumed to satisfy m >> 1, n > 1 and d > 1. The number of layers denoted as k. The asymptotic computation complexity denoted as ((.).
Computation of W @ A and W @ Å. W == 1izj
(p-( dyf,
is the edge weighting matrix dependent
on the node feature matrix F. The computation of yij = f
fo 12 is (d)) and that of (p.) ded (1). Wij only needs computing when (i.j) E E, because V(i.j) $ E, Way will be masked out by A or A anyways. Each element of W involves computation time of (dd) and m elements are needed. In total, W costs (md)) and W @ A and W c Á cost Omd + m) = ((d)).
Computation of @- Q= 1/2 (diag(q + XT) is the inverse Hessian in our quasi-Newton IRLS. Because Q designed to be diagonal matrix, its inverse can be evaluated as element-wise reciprocal which is efficient. As for = E, w evaluation in the summation. Therefore, this computation costs (()). Thus, Q-1 costs ((m) in total.
(k) Amj/ /m. only existing edges (i..) E & need mj
Computation of aggregation. An RUNG layer follows
F(++1) = 2Q- ((W(k)) @ () + XF()).
(52)
which combines the quantities calculated above. An extra graph aggregation realized by the matrix multiplication between W @ A and F is required, costing O(md). The subsequent addition to (()) and the multiplication to the diagonal Q-1 both cost ((nd).
19

---

Stacking layers. RUNG unrolls the QN-IRLS optimization procedure, which has multiple iterations. Therefore, the convergence increase that QN-IRLS introduces allows RUNG with fewer layers and increases the overall complexity. is worth noting that the QN-IRLS utilizes a diagonal approximated Hessian, and thus the computation per iteration is also kept efficient as discussed above.
Summing up all the costs, we have the total computational complexity of our RUNG, O(mm + n))d). Our RUNG thus scales well larger graph datasets such as ogbn-arxiv.
Space Complexity Analysis The only notable extra storage cost is W whose sparse layout takes up (m)) This is the same order of size the adjacency matrix itself, thus not impacting the total asymptotic complexity.
C.2 Alternative Perspective
In fact, the above analysis can be simplified when look the local aggregation behavior of RUNG. For node i, it's updated via aggregation f. @.. T ((E)EN(() Woffi + >f! The summation over neighbors' fj will give ((m) in the total time complexity in each feature dimension, and W;; involves (dd) computations for each neighbor. This sums up to (mmd) well. Essentially, the high efficiency of RUNG originates from that every edge weighting in our model involves only the nodes on this edge.
D Comprehensive Bias Analysis
In this section, we provide multiple evidence from various perspectives to reveal the estimation bias of b--baeed estimation follows.
(1) From the theoretical perspective, the extensive literature on figh-dimensional statistics 40 has proved that & regularization induces estimation bias.
(2) From the algorithm perspective, in Section 2.3 we provide the explanation on the é based estimation problem solver. Specifically, the soft-thresholding operator (0) == sign(f) max
X, 0) induced by the l regularized problem causes a constant shrinkage for & larger than X, enforcing the estimator to be biased towards zero with the magnitude X.
(3) From the numerical simulation in Section 2.3 we provide an example of mean estimation to verify this estimation bias. As shown in Figure 2 the & estimator (green) deviates further from the true mean the ratio of outliers escalates. This can be clearly explained the effect of the accumulation of estimation bias. In other words, each outlier results in constant bias, and the bias accumulates with more outliers.
(4) From the performance perspective, fi-based GNNs such as SoftMedian, TWIRLS, and RUNG-4 (the & variant of our model) suffer from significant performance degradation when the attack budget increases.
(5) From our ablation study in Figure 6, we quantify the estimation bias of the aggregated feature f on the attacked graph from the feature fs on the clean graph: Evey [|/ - 1 The results demonstrate that & -base GNN produces biased estimation under adversarial attacks and the bias indeed scales up with the attack budget. However, our proposed RUNG method exhibits a nearly zero estimation bias under the same attacking budgets.
All of this evidence can convincingly support our claim that based robust estimator suffers from the estimation bias, which validates the motivation of our new algorithm design.
20

---

E
Additional experiment results
In this section, we present the experiment results that are not shown in the main paper due to space limits.
E.1
Adaptive Attacks
Table
and
Table 4 are the results of adaptive local and global attacks on Citeseer, referred to in
Section
Table 3: Adaptive local attack on Citeseer.
The best and second are marked.
Model
20%
50%
100%
150%
200%
MLP
69.3 + 2.5
69.3 + 2.5
69.3 + 2.5
69.3 + 2.5
69.3
2.5
69.3 2.5
GCN
79.3 3.3
44.7 + 8.8
27.3 + 7.7
6.7 6.7 3.7
0.7 1.3
0.0 0.0
APPNP
80.7 4.4
50.0 6.7
39.3
16.7 = 12.3
16.0 8.0
0.0
GAT
74.7 + 5.0
15.3 17.5
13.3 13.5
12.0 11.3
12.7 6.5
9.3 5.3
GNNGuard
74.7
46.0 10.4
11.0
18.0
6.0 3.9
4.0
RGCN
2..0
46.7
8.87
1.2
0.7 1.3
0.7
GRAND
2.5
5.2
3.9
16.7
0.7
0.0
ProGNN
2..0
4.77
26.0
10.0
0.7
0.0
Jaccard GCN
3.4
4.3
2.5
6.7
0.7
0.0
SoftMedian
78.7
69.3
7.1
56.0
8.7 6.9
3.3 3.0
TWIRLS
2.5
+.3
1.67
2.5
36.7
4.7
2.7
TWIRLS-T
3.3
70.7 2.5
2.77
3.4
52.7
5.3
47.3 - 8.3
RUNG-É, (ours)
80.0 3.7
75.3 +: 4.5
73.3 1 3.0
67.3 + 3.3
36.0
9.3
26.0 + 8.3
RUNG (ours)
77.3 + 1.3
70.7 + 5.7
69.3 6.8
67.3 + 7.1
64.0 5.7
61.3 5.8
Table Adaptive global attack on Citeseer. The best and second are marked.
Model
Clean 5%
10%
20%
30%
40%
MLP
0.3
67.7 + 0.3
67.7 0.3
67.7 + 0.3
67.7
0.3
67.7 +
GCN
74.8 + 1.2
66.1 + 1.0
60.9 + 0.8
53.0
47.0 - 0.8
41.2 11.2:10 1.1
APPNP
75.3 = 1.1
05.8 0.9
60.7 + 1.6
52.3 1.6
2.2
GAT
1.2
6..4
60.+1.
5..6
4.12
4..2
GNNGuard
1.1
65.6+0..9
6.48
1..6
1.3
4.3
RGCN
1.0
6.80
6.9
52.5 0.8
4..1
4
GRAND
0.6
6.7
0.7
5.1
4.2
4.22
ProGNN
1.3
6.16
1.1
5.
4..2
4..8
Jaccard-GCN
1.2
6.2
1.2
5.9
4.9
41.1
EvenNet
0..6
0.5
0.6
5..9
51.1
47.4
GARNET
1.3
0.9
61.
58.2
53.9
51.0 0.9
SoftMedian
7.76
0.70
6.94
59.3
2..
51.9 2.1
TWIRLS
74.2+
0.8
6.74
6..6
58.1
51.8 + 1.5
TWIRL S-T
7.1
1.2
1.
1.5
6..
57.4 1.5
RUNG-E, (ours)
75.5 1.1 0.7
69.3 1.2
65.9
61.111
57.2
53.9 + 1.3
RUNG (ours)
714410
69.8
67.6 1.2
66.5 - 1.3
65.3 1.5
E.2
Transfer Attacks
Table 5
and Table a/a the results of transfer global attacks Cora ML and Citeseer. Figure 9 and Figure 10 are the experiment results of our RUNG attacked by transfer attacks generated on different
surrogate models mentioned in Section 4.3
Figure I shows results global evasion transfer attacks between different models on Cora ML. Our observations summarized below:
The attacks generated by RUNG are stronger when applied to more robust models like SoftMedian, while are not strong against undefended weakly defended models.
21

---

Table 5: Transfer global evasion attack on Cora ML.
Model
Clean
5%
10%
20%
30%
40%
MLP
65.0 1.0
65.0 1.0
65.0 1.0
65.0 +: 1.0
65.0 1.0
65.0 65.0 1.0
GCN
85.0 0.4
76.0 0.7
70.6
0.9
62.1 1.0
55.4 15.41.00 1.0
49.8 + 1.1
APPNP
86.3 = 0.4
78.0
72.7
1.2
144118
57.7 : 1.5
53.0 1.2
GAT
83.5
0.7
75.1
6.7
6.8
61.4
GNNGuard
83.1 0.7
7.7
0.7
7.9
11
RGCN
85.7
0.67
0.8
6..4
0.8
52.6 1.0
GRAND
8.71
8.7
1..4
1.3
61.6
60.1 1.1
ProGNN
0.5
0.7
0.9
6418
1.3
53.2 1.3
Jaccard-GCN
8.7
0.7
71.1
6..1
1.6
59.3 1.4
ElasticGNN
0.5
0.9
1.0
13
1.
63.6 1.5
SoftMedian
8.70
8.4
0.6
1.
66.3
60.4 + 2.4
TWIRLS
8.
8.7
0.6
76.8
74.3
72.8 + 0.9
RUNG-E, (ours)
85.8 0.5
82.3 0.8
0.6
75.1 0.8
70.5 - 0.8
67.1 1 0.9
RUNG (ours)
84.6 0.5
83.7 0.6
8.9
81.3 1.3
79.2 1.6
77.9 2.0
Table 6: Transfer global evasion attack on Citeseer.
Model
Clean
5%
10%
20%
30%
40%
MLP
67.7 + 0.3
67.7
0.3
67.7 0.3
67.7 0.3
67.7 0.3
GCN
74,8 1.2
66.7
62.1
54.5 1.7
4.8
43.4
APPNP
75.3 1.1
67.7
1.0
1.0
1.0
1.6
GAT
73.4 1.2
1.3
1.
58.2
5.1
4.7
GNNGuard
4.1
1.2
69.1
6..1
65.4
6.9
RGCN
4.0
6.08
6.3
1.5
+..
46.1
GRAND
0.6
6..
6.9
1.3
1..
51.2
ProGNN
1.3
1.0
62.3+100
5.10
1.0
4.3
Jaccard-GCN
74.8
1.1
65.1
59.0
1.9
51.1
ElasticGNN
1.2
1.4
6..7
2.5
5.2
5.0
SoftMedian
0.7
0.7
6.9
1.1
2.0
51.9
TWIRLS
1.8
1.0
0.9
68.4144
1.6
66.4 1.8
RUNG-E1 (ours)
75.5 4: 1.1
1.3
1.4
65.1
15.1118 1.8
58.7 2.4
RUNG (ours)
4: 0.7
74.2
74.2 1.0
74.3
1.0
74.2
74.1
84.1
5%
83.7
83.7 84.1
83.7
82.6
10%
82.9
82.9
83.0
83.8
83.2
82.6
83.0 82.7
80.2
80.1
80.5
81.1
76.7
Budget
Accuracy
81.4
81.3
81.3
83.1
81.7
81.7
81.7
80.8
76.5
76.6
76.3
77.6
72.5
30%
79.7
79.2
79.8
82.2
80.1
78.6
80.1
78.9
73.5
73.2
72.5
74.2
68.5
40%
77.5
77.9
77.7
81.3
79.0
76.5
78.4
77.3
70.7
70.2
68.6
70.5
66.0
APPNP
GCN
GAT
GNNGuard
RGCN
GRAND
Jaccard Jaccard-GGN GCN
ProGNN
SoftMedian
TWIRLS
TWIRLS-T
RUNG-fi
RUNG
Transfer
Figure 9: Transfer global attack from different surrogate models to our RUNG on Cora ML.
For & GNNs, the attacks are the strongest when transferred from & GNNs. This supports again our unified view on & GNNs. An exception TWIRLS because only has one attention layer and does not always converge to the actual & objective.
22

---

74.3
5%
74.2
74.2
74.1
74.1
74.2
74.2
74.2
74.2
73.7
73.3
73.4
73.9
72.6
72.9
10%
74.2
74.2
74.0
74.2
74.2
74.2
74.3
74.2
73.7
73.2
73.3
73.8
71.8
Budget
Accuracy
20%
74.1
74.3
73.9
74.2
74.1
74.2
74.2
74.2
73.5
72.6
72.6
73.5
70.4
71.5
30%
74.1
74.2 73.9 74.1 74.2 74.1 74.1 74.2 73.4
72.6 72.2
73.4
69.5
70.1
40%
74.0
74.1
73.7 74.0 74.1 74.1 74.1 74.2 73.2
72.3
71.9
73.2
68.6
68.6
APPNP
GCN
GAT
GNNGuard
RGCH
GRAND
Jaccard GCN
ProGNN
MoftMedian
TWIRLS
TWIRLS.T
RUNG-1
RUNG
Transfer
Figure 10: Transfer global attack from different surrogate models RUNG Citeseer.
Budget: 0.050
Budget: 0.100
6CN
76.0
78.0
27.7
50.2
79.9
82.3
81.5
81.8
63.7
91.9
70.6
72.7
72.7
76.4
78.1
79.7
78.7
79.0
82.9
79.0
AРРMР
77.6
76.5
78.9
70.5
80.4
82
81.7
82.0
R3.
87.0
71.5
70.4
74.1
77.2
78.9
82.0
80.0
79.1
17.9
392
80G2
765
77.8
75.8
79.6
80.4
81.9
81.9
82.0
83.9
91.4
71.2
72.2
70.0
75.3
762
79.2
75.9
79.4
83.2
78.5
GRAND
79.4
78.7
79.2
78.3
81.1
$2.8
82.3
75.4
75.1
14.6
72.7
79.5
79.0
82.6
79.3
Tanceer
78.5
80.2
80.1
76.1
75.9
76.2
TWRUSS4
SoftMeeie
51.6
81.8
82.3
78.6
78.4
79.3
RUNG
81.8
81.8
02.3
79.2
75.8
79.4
79.3
Budget: 0,200
Budget: 0.400
GCN
52.1
64.4
64.4
70.0
74.8
75.1
76.5
75.0
81.3
75.5
40.5
$3.0
52.5
65.1
69.9
67.1
72.8
50.4
77.9
63.6
APPEP
57.0
61.9
68.0
71.3
76.0
75.7
77.4
72.7
61.4
73.8
50.3
50.7
57
58.8
707
65.5
72.4
61.7
77.5
63.4
52.5
63.1
60.8
68.2
74.8
74.0
77.5
73.2
81,7
72.0
48.7
51.9
46.0
50.5
70.6
66.5
73.9
52.0
78.1
62.5
55.0
57.6
04.6
Thancher
67.5
66.4
TWRRS4
68.6
58.7
SolMedion
14.0
75.3
75.4
71.3
75.8
b0.F
60.5
61.3
83.9
69.8
10.
52A
RURGG
74.6
74.3
74.9
75.2
76.7
75.1
76.4
73.1
72.5
74.2
67.9
67.1
08.3
68.3
72.7
68.0
71.1
85.9
06.0
872
004
APPNP
RGGH
ORwGGadd
RUNG-1
THARLSH
SobMettan
RUNN
Blamic GRG
GCN
APPR
THmELS
SahMeddin Kinion
RUNG
Blatic DRN
Tanser
Fonsfer
Figure 11: Transfer global attack between different model pairs on Cora.
E.3 Poisoning Attacks
provide the experiment results under poisoning attacks on Cora MI. and Citeseer in Table and Table g respectively.
23

---

Table 7: Poisoning Attacks on Cora ML.
Budget
5%
10%
20%
30%
40%
GCN
74.9 + 0.4
69.7
+. 0.7
60.7 0.7
54.0 + 1.0
48.7 + 1.0
APPNP
76.3 1 0.9
71.1 + 1.2
63.0 1.3
57.1
0.6
53.2 1.1
SoftMedian
79.2
75.6
67.8
62.9 + 1.0
58.6
RUNG-& (ours)
79.7
6..1 0.6
63.8
0.5
60.1
RUNG (ours)
78.5 0.5
75.5
71.5
67.1 + 1.6
64.6 + 1.3
Table 8: Poisoning Attacks on Citeseer.
Budget
5%
10%
20%
30%
40%
GCN
65.5 + 1.1
59.8 + 1.0
51.0 1.0
44.0 1.2
37.9 + 1.0
APPNP
64.2 1.8
2.6
2.5
40.6 2.3
SoftMedian
67.1 1.0
1.0
5.1
51.2 1..
RUNG-É1 (ours)
68.9 $9.9110 1.0
6.19
61.0
57.2
53.9 1.3
RUNG (ours)
72.4 0.9
72.1133
1.
70.8 10.8133
69.7
E.4 Large Scale Ogbn-Arxiv
In the large scale datasets, we can not directly apply the vanilla PGD attack [36 on them due to excessive requirement of memory and computation dense matrix. Alternatively, the PRBCD 42 to scale the PGD attack instead of manipulating on the dense adjacency matrix. large scale Ogbn-Arxiv and the results in Table 9 verified the superior
leverage
We conduct experiments robustness of our RUNG model. RUNG's robustness outperforms its & variant which delivers similar performance as SoftMedian and Elastic GNN due their shared & graph smoothing.
Table 9: Global PGD Attacks on Ogbn-Arxiv.
Model
Clean
1%
5%
10%
GCN
71.9 + 0.5
63.1
= 0.4
48.9
3.2
41.8 = 0.5
APPNP
71.7 0.3
64.2 + 0.4
50.1
2.3
42.2
1.3
SoftMedian
71.2 0.5
65.1
+ 0.3
54.1
50.1
2.6
RUNG-&, (ours)
7 0.6
65.5
+ 0.4
5.10
49.6
1.1
RUNG (ours)
70.2 2.1
65.2 + 0.2
6..0
61.2
0.7
E.5
Adversarial Training
We conduct the adversarial training following (36 and present the results in Table 10 From the results, observe that with adversarial training, the robustness of RUNG can be further improved.
Table 10: Adversarial Training vs Normal Training on RUNG.
Budget
Clean
5%
10%
20%
30%
40%
Normal Training
84.6 + 0.5 84.3 1.2
78.9
75.7 + 0.2
71.8 0.4
67.8 1.3
65.1 1.2
Adversarial Training
81.8 0.7
79.9 + 0.3
77.3 1.1
72.8 + 0.6
69.1 + 0.9
E.6
Graph Injection Attack
The injection attack was conducted following the settings in (37 to evaluate the robustness of different methods. We set up the budget on the number of injected nodes as 100 and the budget on degree as 200. The results in Table IT show that RUNG significantly outperforms the baseline models.
24

---

Table 11: Graph Injection Attack on Citescer.
Model
Clean
Attacked
GCN
75.40
28.14 14
APPNP
75.84
25.24
GNNGuard
73.47
34.73
SoftMedian
74.82
38,91
RUNG-11
75.01
39.22
RUNG-MCP (ours)
75.65
51.13
F Adaptive Attack Settings
For the adaptive PGD attack we adpoted in the experiments, majorly followed the algorithm in [5] in the adaptive evasion attack. For the sake of completeness, we describe it below:
In summary, consider the topology attack setting where the adjacency matrix A is perturbed by 8A whose element 8Ai E {0, 1]. The budget B is defined as B 2 || The PGD attack
involves first relaxing A from binary continuous that gradient ascent attack be conducted on the relaxed graph.
During the attack, the minimization problem below is solved:
8A. arg min Lattack (Grn/iiiNi (GNN, A (I 2A)) @ 88, F), Marrett):
(53)
AA
where L is carefully designed attack loss function 4 55 A, F and Mtarget are respectively the graph, node feature matrix and ground truth labels the dataset, 0 the parameters of the GNN under attack which are not altered in the evasion attack setting. (I 2 @ 8A is the calculated perturbation that "flips" the adjacency matrix between 0 and when is perturbed. The gradient of 6 and utilized to update the perturbation matrix S.A.
is computed
After the optimization problem is solved, 5A is projected back to the feasible domain of 8Aij {1}. The adjacency matrix serves as probability matrix allowing Bernoulli sampling of the binary adjacency matrix A'. The sampling is executed repeatedly so that an A' producing the strongest perturbation is finally generated.
G Additional Ablation Study of RUNG
G.1
Hyperparameters
The choice of the hyperparameters y and is crucial the performance of RUNG, We therefore experimented with their different combinations and conducted adaptive attacks on Cora as shown in Fig. 12
Recall the formulation of RUNG in Eq. S):
F(++1) = (diag q (k)) + 21)-1 ((W()) o () + (
(54)
where qm
(k) W ((()) Amj/dm. w Lizs m0
(k)
20
) and Vij
(k)
Vd:
Va,
2
In the formulation, À controls the intensity of the regularization in the graph smoothing. In our experiments, we tune = I which is normalized into (0, 1). In Figure 12 the optimal value of Å can be found almost always near 0.9 regardless of the attack budget. This indicates that our penalty function p, is decoupled from y which makes the tuning easier, contrary the commonly used formulation of MCP (25]
On the other hand, 7 has the smaller y is, the more edges get pruned, which leads to higher robustness and a lower clean accuracy. We begin discussion in three cases:
intricate impact on the performance of RUNG. Generally speaking,
Small attack budget (0%, 5%, 10%). The performance largely dependent on clean accuracy. Besides, when + oc, RUNG becomes a state-of-the-ant robust & model. Therefore, small
25

---

likely introduces more harm to the clean performance than robustness increments over & models. The optimal y thus least recovers the performance of models.
Large attack budget (20%, 30%, 40%). In these cases, + 0o is no longer a good choice because l models beginning suffer from the accumulated bias effect. The optimal thus smaller (near 0.5). However, for fairness, we chose the same under different budgets in our experiments, so the reported RUNG fixes 7 3. In reality, however, when know the possible attack budgets in advance, we can tune for an even better performance.
Very large attack budget (50%, 60%). We did not include these scenarios because almost all GNNs perform poorly in this region. However, we believe can provide some insights into robust graph learning. Under these budgets, more than half of the edges perturbed. In the context of robust statistics (e.g. mean estimation), the estimator will definitely break down. However, our problem of graph estimation, the input node features offer extra information allowing us exploit the graph information even beyond the breakdown point. In the "peak" near (0.9, 0.5). RUNG achieves > 70% accuracy which is higher than MLP. This indicates that the edge weighting of RUNG is capable of securely harnessing the graph information even in the existence of strong adversarial attacks.
The "ridge" near a = 0.2, on the other hand, emerges because of MLP. When the regularization dominates, À + co, and + 0. A small À is then connected to larger emphasis on the input node feature prior. Under large attack budgets, MLP delivers relatively good estimation, small is beneficial.
Budget:
Budget:
Budget: 10
Budget:
0.8558
0.7989
0.7705
0,7421
Budget: 30
Budget: 40
Budget: 50
Budget:
0.7137
0.6568
5
0.6284
0.6000
0-
Figure 12: The performance dependence of RUNG with different hyperparameters y and The performance is evaluated under different attack budgets. The attack setting is the global evasion attack and the dataset is Cora. Note the x-axis = I+X instead of A.
G.2 GNN Layers
In RUNG, QN-IRLS is unrolled into GNN layers. We would naturally expect RUNG to have enough number layers so that estimator converges as desired. conducted an ablation study on performance (clean and adversarial) of RUNG with different layer numbers and the results are shown in Fig. Figure 13
We make the following observations:
As the layer number increases, RUNG exhibits better performance. This verifies the effectiveness our proposed RUGE, as well as the stably converging QN-IRLS.
The performance of RUNG can achieve reasonably good level even with small layer number (3-5 layers) with accelerated convergence powered by QN-IRLS. This can further reduce the computation complexity of RUNG.
26

---

0.80
0.75
Accuracy
0.70
0.65
budget: 5%
budget: 10%
0.60
budget: 20%
budget: 40%
5
10
15
20
Propagation steps
Figure 13: The performance dependence of RUNG on the number of aggregation layers.
H Robustness of GCN and APPNP
In addition to the formulation in Section 3 the main text, we can simply apply our edge reweighting technique the GCN architecture. Essentially the aggregation operation in GCN can be viewed as an APPNP layer with Å = 0. The GCN version layer in our model can then be formulated as (k++1 ReLU((((M)) 3 ( M (K)),
(55)
where M is the learned weight matrix in GCN.
GCN-based defenses are less robust than APPNP-based defenses GCN consists of layers in which both feature transformation and message passing are included. This graph convolution operation will weaken defense methods that rely on edge weighting, such GNNGuard, models using 4 penalty as well as our method using MCP penalty.
Consider an edge that is added by the attacker A successful defense should detect the attack on this edge by the large difference of nodes connected by this edge, and then assign a zero weight or at least smaller weight to this edge. However in GCN, even if this edge is detected in the first layer's message passing, the subsequent feature transformation makes the node difference less likely to be preserved until the second layer. This is where the attack can evade the defense and is thus a vulnerability allowing adaptive attacks through. According to our experiments, using different defense parameters in different layers of GCN, unfortunately, does not help much either.
On the other hand, in APPNP node features also altered along the message-passing layers, but the node distance change is more regulated than in GCN since MLP is decoupled from the graph smoothing layers. In the latter submodule, node differences simply decrease, which allows our defense based on node differences.
Experiments can be seen from Figure 14 that the correlation of node feature differences in different layers of GCN is about 4 times less than in APPNP, which means that an attack detected in the first layer less likely to continue be detected in the second layer than in APPNP. This property of GCN makes the many defense methods using GCN architecture as backbone less robust, as shown the experiment results in Table 12 and Table 13, Nevertheless, our model outperforms the SOTA models using 1 methods.
MCP
Almost all attacks add new edges shown by experiments, this is almost always the
27

---

30
30
cor: 0.077
cor: 0.252
cor: 0.319
after first layer of GCN
after last layer of APPNP
25
25
20
layer of
20
10
10
5
10
before first layer of GCN
before first layer of APPNP
before first layer of L21
Figure 14: The distances I|fs fill2 between connected nodes in different layers are shown. The
linear transform operation in aggregation layers of GCN reduces the correlation between the node distance at different propagation layers.
Model
Clean
5%
10%
20%
30%
40%
RUNG-
85.8 + 0.5
78.4 0.4
74.3 + 0.3
68.1 + 0.6
63.5
1..5:00 0.7
59.8 = 0.8
RUNG
84.6 0.5
78.9 = 0.4
75.7 + 0.2
71.8
67.8 1.3
65.1 1.2
RUNG-L1-GCN
84.0 0.4
74.7 0.6
69.7
0.7
0.6
0.6
53.5 0.8
RUNG-GCN
82.6 0.6
76.1 = 0.7
0.9
6.1
59.9 - 0.8
56.5 1.1
Table 12: Comparison between APPNP-based and GCN-based QN-IRLS on Cora.
Model
Clean 5%
10%
20%
30%
40%
RUNG-
75.5 + 1.1
69.3 = 1.2
65.9 + 1.2
61.1 + 1.1
57.2 1.4
53.9 + 1.3
RUNG
74.3 = 0.7
71.4 = 1.0
69.8 - 1.3
6.2
1.3
65.3 + 1.5
RUNG-L1-GGE
73.8 = 1.2
66.1
1.1
61.91.0
5..0
47.7 0.6 0.8
RUNG-GCN
73.0=0..
68.2 = 0.8
64.3
5.04
55.7
1.4
53.1 + 1.6
Table 13: Comparison between APPNP- and GCN-based QN-IRLS on Citeseer.
28

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Our abstract and introduction (Section] closely follow the contribution (at the end of Section in the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contribu- tions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations of the work in the Section 6
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results to vi- olations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specifficttio, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by review- ers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't t acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each thcoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
29

---

Justification:
We provide the theory in Section 3.2 and the detailed proof in the Appendix B
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs the paper should numbered and cross-referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main experi- mental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification:
We provide the detailed experimental setting in Section 4.1
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access a hosted model (e.g., in the of large language model), releasing of model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results way reproduce the model (c.g., with an open-soure dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
Open access data and code
Question: Does the paper provide open access the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification:
We will organize the data and code after the submission.
Guidelines:
30

---

The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (tttps::/nips..c//pbb))
Tuutess/ooeeSubbiissioooo..
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed reproduce the results. See the NeurlPS code and data submission guidelines (https:// nips.
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide the detailed experimental setting in Section 4.1
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report еπтоr bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: Error bars are not reported because it would be too computationally expensive
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" the results are accompanied by error bars, confidence intervals, statistical significance tests, least for the experiments that support the main claims the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show tables or figures symmetric error bars that would yield results that out of range (c.g, negative error rates).
31

---

If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory. time of execution) needed reproduce the experi- ments?
Answer: [No]
Justification:
We include the theoretical computation analysis in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experi- mental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Does the research conducted in the paper conform, every respect, with the NeurIPS Code of Ethics
Question:
Answer:
[Yes]
Justification:
The paper closely follows NeurlPS Code of Ethies
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consideration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no societal impact of the work performed.
Guidelines:
The answer NA means that there is no socictal impact of the work performed.
If the authors answer NA or No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess considerations (c.g., deploy- ment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
32

---

If there are negative societal impacts, the authors could also discuss possible mitigation strategies (c.g. gated release of models, providing defenses addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g.. pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification:
Our paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions access the model implementing safety filters.
Datasets that have been scraped from Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.
12. Licenses for existing assets
Question: Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: Our paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include a URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use the package should be provided. For popular datasets, paperswi thcode. com datasttssss has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged reach out to the asset's creators.
13. New Assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [NA]
Justification:
Our paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets. Researchers should communicate the details of the dataset/codemmodel part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
33

---

At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects Question:
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Sub- jects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
34


Reviews:
[{"review_id": "mgyV8B5EDq", "reviewer": "Reviewer_7kcB", "summary": "The authors point out that some of the successful defenses for GNNs are related to l1-based graph smoothing. Motivated by the bias of l1-based estimators, the authors develop an unbiased variant (RUGE), rooted in high-dimensional statistics. To optimize under such a non-smooth objective, the authors devise a Quasi-Newton Iterative Reweighted Least Squares algorithm. In the empirical evaluation, the authors compare with a rich set of baseline GNNs and defenses on graphs of varying sizes. The authors report the performance on both non-adaptive and adaptive attacks. Moreover, the authors study the influence of hyperparameters and further complement their method with adversarial training.", "questions": "1. How does RUGE perform on heterophilic graphs?", "limitations": "The limitations are sufficiently addressed.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. The authors provide a unified view of some of the important defenses in the GNN domain\n1. The proposed method is well-motivated and empirically successful\n1. The empirical evaluation is extensive and convincing", "weaknesses": "1. The paper only studies homophilic datasets\n1. The adversarial training is performed in the biased transductive evasion setting of Xu et al [A]. It is better to follow an inductive evasion setting as in [B]. The authors should at least note that the studied setting has limitations.\n1. Minor: The references in some cases do not mention the respective venue/journal (e.g., [36])\n\n[A] Xu et al. \"Topology Attack and Defense for Graph Neural Networks: An Optimization Perspective\" NeurIPS 2019.\n[B] Gosch et al. \"Adversarial Training for Graph Neural Networks: Pitfalls, Solutions, and New Directions\" NeurIPS 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your recognition of the novelty and effectiveness of our method. We are glad to solve\nyour concerns and answer your questions with the following illustrations.\n\n**W1: The paper only studies heterophilic datasets**\n\n**Answer:** We want to point out that our RUNG (Robust Unbiased Aggregation) is a robust aggregation built-in block that can be readily incorporated into various GNN backbones. In this paper, we comprehensively evaluate the robustness on homophilic graphs with the APPNP backbone, but our RUNG can be generalized to heterophilic graphs by incorporating it into heterophilic GNNs. We include the experimental results and validate the effectiveness of RUNG on heterophilic datasets in global response.\n\n**W2: The adversarial training is performed in the biased transductive evasion setting of Xu et al [A]. It is better to follow an inductive evasion setting as in [B]. The authors should at least note that the studied setting has limitations.**\n\n[A] Xu et al. \"Topology Attack and Defense for Graph Neural Networks: An Optimization Perspective\" NeurIPS 2019.  \n\n[B] Gosch et al. \"Adversarial Training for Graph Neural Networks: Pitfalls, Solutions, and New Directions\" NeurIPS 2023.\n\n**Answer:** We evaluate RUNG under inductive evasion setting in the following table. The results show that the robustness of RUNG can be also be further improved with adversarial training under inductive setting. We will mention this setting difference in the revision following your suggestion and provide these additional results as ablation study.\n\n### Table 7: Adversarial Training vs Normal Training on RUNG in the inductive evasion setting.\n\n| Budget            | Clean            | 5%              | 10%              | 20%              |\n|-------------------|------------------|-----------------|------------------|------------------|\n| Normal Training   | 83.2 ± 0.2       | 73.4 ± 0.3      | 69.8 ± 0.5       | 65.5 ± 0.3       |\n| Adversarial Training | 82.4 ± 0.9   | 76.3 ± 0.2      | 74.3 ± 0.4       | 71.4 ± 0.6       |\n\n**W3: Minor: The references in some cases do not mention the respective venue/journal (e.g., [36])**\n\n**Answer:** We initially cited the most referenced version of the paper, but we will update it to the respective venue/journal in the revised version for proper citation format.\n\n**Q1: How does RUGE perform on heterophilic graphs?**\n\n**Answer:** Please refer to W1.", "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": "jSiL7I6oqB", "reviewer": "Reviewer_E1WB", "summary": "This paper uncovers that while $\\ell_1$-based models exhibit robustness against moderate adaptive attacks, their performance significantly degrades under strong adaptive attacks. The authors investigate the root cause of this phenomenon, identifying estimation bias as the culprit. To address this, they propose a robust and unbiased graph signal estimator. Extensive experiments and ablation studies confirm that their method significantly enhances GNN robustness without compromising clean accuracy.", "questions": "See the Weaknesses", "limitations": "The authors addressed the limitations.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper provides compelling motivating experiments, observations, and insights. Furthermore, the authors rigorously analyze the root cause of their findings, offering a persuasive and logical explanation.\n- Based on these discoveries, the authors propose a simple yet effective method, well-supported both theoretically and empirically.\n- Extensive experiments offer thorough analysis to demonstrate the effectiveness of the proposed method.\n- The proposed method significantly outperforms other baselines under both local and global adaptive attacks.", "weaknesses": "- The datasets considered by the authors are limited to only three citation networks. While I acknowledge that implementing adaptive attacks on new datasets and baselines is significantly cumbersome and requires considerable effort, demonstrating that the proposed methods work well on datasets from other domains would greatly enhance the applicability and recognition of this work.\n\n- There is no available source code for the reproduction,", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your recognition of the novelty and effectiveness of our method. We are glad to solve\nyour concerns and answer your questions with the following illustrations.\n\n**W1:** The datasets considered by the authors are limited to only three citation networks. While I acknowledge that implementing adaptive attacks on new datasets and baselines is significantly cumbersome and requires considerable effort, demonstrating that the proposed methods work well on datasets from other domains would greatly enhance the applicability and recognition of this work.\n\n**Answer:** To further validate the effectiveness, we include 2 heterophilic datasets and multiple datasets from various domains in global response.\n\n**W2:** There is no available source code for the reproduction.\n\n**Answer:** We have sent the anonymized link to the AC in a separate comment.", "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": "KwIRUi0duY", "reviewer": "Reviewer_Vusx", "summary": "The paper addresses the adversarial robustness of Graph Neural Networks (GNNs) against adaptive attacks. The authors propose a unified framework for robust estimation in GNNs to understand and improve their robustness. Specifically, \n\n1. The paper provides a unified view of $\\ell_1$-based robust graph signal smoothing, and tries to reveal the estimation bias leading to performance degradation under attacks.\n\n2. The authors propose a robust and unbiased graph signal estimator (RUGE) to mitigate the estimation bias.\n\n3. They develop an efficient Quasi-Newton Iterative Reweighted Least Squares (IRLS) algorithm to solve the non-smooth and non-convex estimation problem, as well as theoretical guarantees.", "questions": "It would be great if the authors could respond to concerns mentioned in the *Weaknesses*.", "limitations": "The authors addressed the limitations.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The topic of the paper, robust GNN, is of interest, and a way to alleviate the bias is proposed.\n\n2. A unified perspective on existing robust GNN works is built.\n\n3. A new optimization algorithm, QN-IRLS, is proposed, as well as the corresponding complexity analysis.", "weaknesses": "1. The manuscript is difficult to follow due to poor **writing**. Specifically,\n\n  1a. The phrase “without the false sense of security” in Sections 1 and 2 is unclear. What does it mean, and why is it significant in this context?\n\n  1b. The figures are hard to understand without additional details (either in captions or main text). For instance, in Figure 1, what does the x-axis represent, and how is 200% defined? How is an attack conducted? \nIn Figure 2, how are “clean sample” and “outliers” defined? Similar issues to Figures 5 and 7.\n\n  1c. Some of the equations are unclear. For example, in Equation (1), \\tilde{f} should be formatted similarly to Equation (2).\n\n2. The **contribution** is unclear.\n\n2a. Regarding the unified perspective: it seems inconsistent with the experimental results in Figures 1 and 2. As shown in Figure 2, the $\\ell_2$ estimator deviates further from the true mean, while in Figure 1, SoftMedian performs the worst, which is a special case of ElasticGNN with  p=1  ($\\ell_1$).\n2b. Regarding the optimization: the distinction and connection between QN-IRLS and other standard QN methods is missing.\n\n3.\tThe **experiments** can be further improved.\n\n3a. Only two datasets, Cora and CiteSeer, are included.\n\n3b. While it is understood that space constraints may limit the inclusion of all interesting details in the main text, lines 304-317 occupy significant space without providing primary conclusions or insights.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your recognition of the novelty and effectiveness of our method. We are glad to solve\nyour concerns and answer your questions with the following illustrations.\n\n**W1a**: The phrase \"without the false sense of security\" in Sections 1 and 2 is unclear. What does it mean, and why is it significant in this context?\n\n  **Answer**: We would like to clarify that the \"false sense of security\" is a common phenomenon in adversarial robustness [1][2]. This means that the robustness can be overestimated if the adversarial attacker is weak due to various reasons such as not directly targeting the victim model. For example, in this paper, \"transfer attacks\" are denoted as first attacking the surrogate GCN model and then transferring the perturbations to the specific victim model, which might be much weaker.\nTherefore, we need to evaluate the models under \"adaptive attacks\" that directly target the victim model to avoid a \"false sense of security\".\n\nRef:\n\n[1] Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples. (ICML, 2018)\n\n[2] Mujkanovic, Felix, et al. \"Are defenses for graph neural networks robust?.\" (NeurIPS, 2022 )\n\n**W1b**: Lack of detailed caption in Figures. \n\n**Answer**: Let me make them clear as follows:\n- **Fig 1**: The x-axis represents the attack budget, which means the portion of edges allowed to be perturbed. We conduct adaptive local attack in Figure 1, where \"200%\" means the number of perturbed edge is up to 200% of target node’s degree. For example, if the target node has 5 neighbors, the budget 200% means the attacker can change up to 5*200%=10 edges.\n- **Fig 2**: We mention in the main paper that we put the detailed settings including how we construct clean sample and outliers in Appendix A. In Figure 2, we define \"clean sample\" as the major data points following the Gaussian distribution $N((0,0), I)$, while \"outliers\" is the data points far away from major data pattern following $N((8,8), 0.5 \\cdot I)$.\n- **Fig 5**: The x-axis represents the layer/iteration number of the algorithm, y-axis represents the objective value. This figure aims to validate the fast convergence of our QN-IRLS algorithm.\n- **Fig 7**: This figure aims to find the reasons for better performance of RUNG, by getting insight into the distribution of node feature differences of attacked edges for different models. A smaller difference (our RUNG) means the attacker tends to perturb the edges connecting two more similar nodes, indicating that our RUNG can improve robustness by down-weighting or pruning some malicious edges that connect distinct nodes.\n\n**W1c**: Some of the equations are unclear. For example, in Equation (1), $ \\hat{f} $ should be formatted similarly to Equation (2).\n\n**Answer**: We have given the detailed and clear definition of $ \\hat{f} := (1 + \\lambda_i)^{-\\frac{1}{2}} f_i $. Please kindly let us know if there are any further confusions.\n\n**W2a**: Regarding the unified perspective: it seems inconsistent with the experimental results in Figures 1 and 2. As shown in Figure 2, the estimator deviates further from the true mean, while in Figure 1, SoftMedian performs the worst, which is a special case of ElasticGNN with $ p=1 $.\n\n**Answer**: Actually, Figure 1 and Figure 2 provide the results of different experiments: Figure 1 gives the empirical robustness results on real graph datasets, while Figure 2 offers the simulation experiments on synthetic Gaussian data. For the inconsistent results of SoftMedian and ElasticGNN, although these two models share common underlying characteristics, their detailed architecture designs such as different numerical solvers are different, which may cause difference in the empirical results as reported.\n\n**W2b**: Regarding the optimization: the distinction and connection between QN-IRLS and other standard QN methods is missing.\n\n**Answer**: The proposed QN-IRLS differs with standard QN methods in two perspectives. First, QN-IRLS iteratively constructs smooth quadratic upper bounds of the objective function so that it can deal with non-smooth objectives such as the robust penalties. Second, the proposed Quasi-Newton algorithm approximates the Hessain matrix of the quadratic upper bounds with a specifically chosen diagonal matrix, which makes the implementation and memory cost much lower than standard QN methods such as BFGS and L-BFGS that do not consider the specific structure of the problems.\n\n**W3a**: Only two datasets, Cora and CiteSeer, are included.\n\n**Answer**: To further validate the effectiveness, we include 2 heterophilic datasets and multiple datasets from various domains in global response.\n\n**W3b**: While it is understood that space constraints may limit the inclusion of all interesting details in the main text, lines 304-317 occupy significant space without providing primary conclusions or insights.\n\n**Answer**: \nFor the experiments presented in lines 304-317, let me elaborate the primary conclusions and insights as follows:\n- **For \"Transfer Attack\"**, we can observe that all the transfer attacks from various surrogate models are weaker than the adaptive attacks. That indicates the necessity to evaluate the strongest adaptive attack to avoid the false sense of security emphasized in this paper.\n- **For \"Hyperparameters\"**, we observe that the γ in MCP has an intricate impact on the performance of RUNG. Specifically, larger γ makes RUNG closer to ℓ1-based model. While smaller γ encourages more edges to be pruned, which help RUNG to remove more malicious edges and improve the robustness, but small γ may sacrifice the clean performance a little bit.\n- **For \"Robustness under various scenarios\"**, we try to include more datasets or attacks further validate the consistent effectiveness of our proposed RUNG.\n\n**We believe we have fully addressed all the concerns. Please kindly let us know if there are any remaining concerns, and we are happy to further clarify.**", "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:
Thank you to all the reviewers for recognizing the novelty and effectiveness of our method. Since all reviewers share concerns about the effectiveness of RUNG on heterophilic graphs and other domain-specific datasets, we will include the experimental results for several datasets in our global response as follows.

# Heterophilic dataset

To evaluate the robustness on heterophilic datasets, we conduct experiments following the settings in [1]. We build our model by replacing the message passing aggregation block with RUN G in FSGNN [2] which is designed for heterophilic graph. The results summarized below showcase the advantage of our RUN G among all the compared models.

### Table:  Robustness on  heterophilic datasets.
| Method & Dataset | Chameleon         | Squirrel          |
|------------------|-------------------|-------------------|
| MLP              | 48.84 ± 1.66      | 30.31 ± 1.25      |
| GCN              | 49.93 ± 0.70      | 31.16 ± 2.19      |
| EGCNGuard        | 45.34 ± 2.80      | 27.34 ± 0.90      |
| H2GCN            | 51.42 ± 1.31      | 28.41 ± 1.08      |
| FAGCN            | 49.98 ± 1.27      | 33.64 ± 1.10      |
| GPRGNN           | 50.42 ± 0.83      | 32.47 ± 1.36      |
| EvenNet          | 52.87 ± 1.88      | 33.21 ± 0.96      |
| FSGNN            | 53.64 ± 8.39      | 34.86 ± 4.48      |
| RUNG (Ours)            | 58.47 ± 7.85      | 42.07 ± 2.94      |

References:

[1] Runlin Lei, Zhen Wang, Yaliang Li, Bolin Ding, and Zhewei Wei. Evennet: Ignoring odd-hop neighbors improves robustness of graph neural networks. Advances in Neural Information Processing Systems, 35:4694–4706, 2022.

[2] Maurya, Sunil Kumar, Xin Liu, and Tsuyoshi Murata. "Improving graph neural networks with simple architecture design." arXiv preprint arXiv:2105.07634 (2022).

# Additional datasets

To further validate the effectiveness of our RUNG, we evaluate the robustness under adaptive global attack in additional datasets including 2 blog networks (BlogCatalog and PolBlogs), 1 photo sharing network (Flickr) and 2 citation networks (ACM and DBLP). The following results demonstrate the consistent and significant advantage of our RUNG over other models. We include the tables in the attached pdf.

Meta-review: The paper examines the adversarial robustness of Graph Neural Networks (GNNs) against adaptive attacks and proposes a unified framework for robust estimation. It finds that l1-based models, while resilient to moderate attacks, degrade under strong attacks due to estimation bias. To address this, the authors introduce an unbiased graph signal estimator and connect their work to existing defenses, creating an unbiased variant based on high-dimensional statistics. The proposed approach is both well-justified and empirically successful. The reviewers were satisfied with the responses provided during the rebuttal and found the paper interesting. The authors are encouraged to incorporate the comments and feedback received to strengthen their work.
Decision: Accept (poster)