Bounding the Expected Robustness of Graph Neural Networks Subject to Node Feature Attacks
Authors: Yassine ABBAHADDOU
Sofiane ENNADIR
Johannes F. Lutzeyer
Michalis Vazirgiannis
Henrik Boström
Venue: ICLR 2024 poster (2024)
Keywords: Graph Neural Networks
Adversarial Robustness
Primary area: learning on graphs and other geometries & topologies
TL;DR: We define and upper-bound the expected adversarial robustness of Graph Neural Networks, which allows us to propose the more robust Graph Convolutional Orthonormal Robust Networks (GCORN).

Abstract: Graph Neural Networks (GNNs) have demonstrated state-of-the-art performance in various graph representation learning tasks. Recently, studies revealed their vulnerability to adversarial attacks. In this work, we theoretically define the concept of expected robustness in the context of attributed graphs and relate it to the classical definition of adversarial robustness in the graph representation learning literature. Our definition allows us to derive an upper bound of the expected robustness of Graph Convolutional Networks (GCNs) and Graph Isomorphism Networks subject to node feature attacks. Building on these findings, we connect the expected robustness of GNNs to the orthonormality of their weight matrices and consequently propose an attack-independent, more robust variant of the GCN, called the Graph Convolutional Orthonormal Robust Networks (GCORNs). We further introduce a probabilistic method to estimate the expected robustness, which allows us to evaluate the effectiveness of GCORN on several real-world datasets. Experimental experiments showed that GCORN outperforms available defense methods. Our code is publicly available at: https://github.com/Sennadir/GCORN .

Published as a conference paper at ICLR 2024
BOUNDING THE EXPECTED ROBUSTNESS OF GRAPH NEURAL NETWORKS SUBJECT TO NODE FEATURE ATTACKS
Yassine Abbahaddou LIX, Ecole Polytechnique IP Paris, France
Sofiane Ennadir* BECS, KTH Stockholm, Sweden
Johannes F. Lutzeyer LIX, Ecole Polytechnique IP Paris, France
Michalis Vazirgiannis
Henrik Boström BBCS, KTH Stockholm, Sweden
Ecole Polytechnique, IP Paris & KTH Stockholm, Sweden
ABSTRACT
Graph Neural Networks (GNNs) have demonstrated state-of-the-art performance in various graph representation learning tasks. Recently, studies revealed their vulnerability to adversarial attacks. In this work, we theoretically define the concept expected robustness in the context of attributed graphs and relate it to the classical definition of adversarial robustness in the graph representation learning literature. Our definition allows us to derive an upper bound of the expected robustness of Graph Convolutional Networks (GCNs) and Graph Isomorphism Networks subject to node feature attacks. Building on these findings, we connect the expected robustness of GNNs to the orthonormality of their weight matrices and consequently propose dttack-independe called the Graph Convolutional Orthonormal Robust Networks (GCORNs). We further introduce probabilistic method to estimate the expected robustness, which allows us to evaluate the effectiveness of GCORN on several real-world datasets. Experimental experiments showed that GCORN outperforms available defense methods. Our code is publicly available at: https//ggtuubcoommSSSsaaacCCCCC
more robust variant of the GCN,
INTRODUCTION
Graph-structured data is prevalent in a wide range of domains, motivating therefore the development of neural network models that can operate on graphs, known as Graph Neural Networks (GNNs).
GNNs have emerged as a powerful tool for learning node and graph representations. Many GNNs instances of Message Passing Neural Networks (MPNNs) (Gilmer al.. 2017) such as Graph Isomorphism Networks (Xu et al. 2019b) and Graph Convolutional Networks (GCN) & Welling 2017). These models have been successfully applied in real-worke applications such as molecular design (Kearnes et al., 2016). In parallel to their success, it has been shown, particularly in the field of computer vision, that deep learning architectures can susceptible to adversarial attacks (Goodfellow et al., 2015). These attacks, which are based on injecting small perturbations into the input, lead to unreliable predictions, limiting therefore the applicability these models to real-world problems. Similar to other deep learning architectures, GNNs also vulnerable to adversarial attacks. Recent studies (Dai et al.) 20188) Zügner et al.) 2018 Günnemann 2022) have shown that a GNN can be attacked by applying small structural perturbations to the input graphs. These attacks pose a threat to the reliability GNNs, particularly in crittyl applications such as finance and healthcare. Consequently, different attacks have been proposed explore the robustness of GNNs. Concurrently, several studies focus on developing methods to mitigate possible perturbation effects and improve the robustness of MPNNs. The proposed methods include augmenting training data with adversarial examples and retraining the model (Feng et al. 2019), pre-procssiing methods such as
"Equal contribution.
Contact:
yassi ne. abbahaddou@po ytechni que edu and
ennadi r@kth.

---

Published as a conference paper at ICLR 2024
edge pruning Zhang & Zitnik 2020), and more recently robustness certificates (Schuchardt et al. 2021). While the majonity of these proposed defenses focus on structural perturbations, only limited advances have been made for feature-basse based adversarial attacks graphs. Moreover, despite the large amount of research on the robustness of these methods through empirical exploration, there has been limited progress in understanding the theoretical robustness of GNNs.
In this work, we conduct a theoretical examination of the robustness of MPNNs subject to adversarial attacks. First, we formally define the concept of "Expected Adversarial Robustness" for structure and feature-basee perturbations in the context of graphs defined in a metric space. We further- more establish a formal relation between our introduced expected robustness and the conventional adversarial robustness formulation. Further, by analyzing the input sensitivity of the iterative message- passing schemes, we derive an upper bound on the robustness of these models for both structural and feature-based attacks. Motivated by our theoretical results, we propose a refined learning scheme, called Graph Convolutional Orthonormal Robust Network (GCORN), for the GCN, to improve its robustness to feature-based perturbations while maintaining its expressive power. In addition to our theoretical findings, we empirically evaluate the effectiveness of our GCORN in both node and graph classification commonly used real-world benchmark datasets and compare GCORN to existing methods to defend against nattre-bbssd adversarial attacks. Most empirical evaluations of the effectiveness of defense methods consider worst-case scenarios, hence not taking into account the variability of attacks and their likelihood of occurrence. To overcome this limitation, we propose a novel probabilistic method for evaluating the expected robustness of GNNs, which is based on our introduced robustness definition. The method is model-agnostic and can hence be applied to any architecture to estimate the local robustness. More realistic and comprehensive evaluation of the effectiveness of defense approaches can hence be conducted.
Our main contributions are: (i) We define and theoretically analyze the expected robustness of MPNNs. producing an upper- bound on their expected robustness, (ii) a novel approach (GCORN) for improving the expected robustness of GCNs to feature-based attacks while maintaining their performance in terms of accuracy, (iii) a theoretically well-founded, probabilistic and model-agnostic evaluation method, and (iv) an empirical evaluation of our GCORN on benchmark datasets, demonstrating its superior ability compared to existing methods to defend against feature-based attacks.
2 RELATED WORK
While most studies on attacking machine learning models focus on images (Goodfellow et al.) 2015), work on discrete spaces such as graphs has also emerged. Analogous to images, most existing graph-based attack methods frame the task as search/optimization problem. For instance, the targeted attack Nettack (Zügner et al. 2018) utilized greedy optimization scheme while Zügner & Günnemann (2019) formulate the problem as a bi-level optimization task and leverage meta- geea-ggradeets to solve it. Zhha & Pei ( expanded this work through a black-box gradient algorithm overcoming several limitations. Furthermore, Dai et al. (2018) proposed to use Reinforcement Learning to solve the search problem and generate adversarial attacks. Node injection attacks (Zou et al.) 2021 Tao jct al.] 2021 Chen et al.) 2022, Ju et al. 2023) have also proven effective, with attackers introducing malicious nodes instead of modifying existing nodes or edges, affecting therefore the model's s performance. In parallel, the field of defending against adversarial attacks on GNNs is still relatively under-explored compared that of image-based models. The majority of methods are primarily focused on heuristic strategies. Similar to computer vision, robust training (Zügner & Günnemann 2019) and noise injection (Ennadir et al.) 2024) have been used to improve the robustness of GNNs. Additionally, low-rank approximation with graph anomaly detection (Ma et al. 202T) has been used to defend against adversarial attacks. The GNN-Jaccard method (Wu et al. 2019) pre-processes the adjacency matrix to detect potential manipulation of edges. In the same context, GNN-SVD (Entezari jet al. (020) uses a low-rank approximation of the adjacency matrix to filter out noise. Other methods such as edge pruning (Zhang & Zitnik (220)) and transfer learning (Tang et al. (020) have also been proposed. Finally, Wang et al. (2020) proposed a low-pass adaptation of the message passing to enhance robustness while providing theoretical guarantees. Although these defense strategies have had some success, for the majority of them, their heuristic nature results in defenses against specific types of attacks without any guarantees the model's underlying robustness. As result, these defenses may be susceptible to being circumvented by future new advanced attacks. Consequently. the investigation of robustness certificates (Züggner & Günnemann, 2019 Bojchevski & Günnemann
2

---

Published as a conference paper at ICLR 2024
2019
Gosch et al. 2023) has gained attention by providing attack attack-independent guarantees the stability of the model's 's predictions such as randomized smoothing (Bojchevski et al., (020).
While the majority of the existing work on defense strategies for GNNs has focused structural perturbations, there is far less work on addressing feature- attacks. This represents a significant gap in the literature propose to add a node feature kernel to the message passing to enhance the robustness of GCNs. Additionally, RobustGCN (Zhu et al.) 2019) proposes use Gaussian distributions as the hidden representations. enabling the absorption of the impact of both structural and feature-based attacks. Finally, Liu et al., (2021a) edited the message passing module using adaptive residual connections and feature uggregation, which have been shown experimentally to enhance the model's 's robustness against abnormal node features. Robustness certificates have also been proposed for node feature- based attacks (Scholten et al. 2022 BBocchvski et al. 2020).
feature- based attacks on GNNs can be very effective. [Seddik et al. (2022)
3 EXPECTED ADVERSARIAL ROBUSTNESS
In this section we mathematically define the concept of the expected robustness for a graph-based function, such GNN. Let us consider three metric spaces with defined norms over the graph space (G, (l-llc). the feature space (X. I1-l(x) and the label space (), ll-lly). Let D be the underlying probability distribution defined on (G, ))) Given graph- based function f (G, X) + V/ and some input (G, X) E (g, X) with its corresponding label y E y where f(G = y. the goal of an adversarial attack is to produce a perturbed graph G and its corresponding features X which are "slightly' different from the original input (G, such that the predicted class of (G, X) ) is different from the predicted class of (G, X). The adversarial task is contingent on defining a similarity measure between the input graph and the adversarially generated graph. To this end, we introduce a distance over our input metric spaces, which takes both the graph and its corresponding features into account
& [), (J) = al|G Gllg + B|| - -X
In practice, a graph is represented by its adjacency matrix (or some other graph shift operator) and its feature matrix, we can therefore, without loss of generality, consider the distance
(IG, (IG, (G, Pen (alIA- PAP" 122 + B|| PXI12).
(I)
where II is the set of permutation matrices and ax, 33 are hyper-parametten graphs, the distance in ( aligns with the commonly used edit distance on graphs which is measure of similarity between two graphs quantifying the minimal number of edges that need to be edited to convert one graph into another while taking into account graph isomorphism. Based on this distance, we can mathematically formulate the adversarial task as finding a perturbed attributed graph (G, X) within a specified budget such that f(G X) = ÿ A with dm. d x1, X1) < c. Moreover, given that in practice the attacker does not have access to the ground-truth labels, we define an adversarial graph attack to be valid when f(,, X) A f(G, X). We can now define the expected vulnerability of a graph function as its likelihood to suffer from such attacks in the input's neighborhood defined by e. Upper bounding this vulnerability allows us to quantify the model's expected robustness, we start by formulating the expected vulnerability of a graph function f as
Note that for un-attributed
Ado [f] = =P(,, I(G, X) E Ba. (G, (G) d fG, f)) > a], (2)
with Ba.3 (G, X,e) = [(G. 8): : da.. X), [G, X1) < <e) for any budget e 2 0. Additionally, dy can be any defined distance in the output space y' a'and >> 0. Here, we focus on real-valued output mappings and consider the distance metric dy (f( X), X), formulation is applicable to both graph and node classification tasks. In node classification, the parameter determines the minimal number of nodes that need to be successfully attacked to consider the attack to be adversarially successful at the graph-level. This allows for flexibility in different scenarios, where in some cases, even single node's 's label flip may be considered threat, while in others, a limited number of changes can be tolerated. In graph classification, the parameter a acts as threshold to the continuous softmax output above which attack is considered effective. We can now introduce the concept of expected robustness of function defined on graphs, such as a GNN. Definition 3.1 (Expected Adversarial Robustness). Let d be graph distance on the spaces (G and dy be a distance on the space V. The graph function f (G) > ) is ((d0.) -),, (dy, 7)) robust if its vulnerability defined in (2) can be upper- upper-hounded by 7, i.e. e., Adv [S] 7.
X)) [ī, X)- f (GG.X)lly This
3

---

Published as a conference paper at ICLR 2024
In Appendix A (Proposition A.1 we show how, via the equivalence of metrics, expected robustness in given metric implies expected robustmess in several other metrics.
Relating Expected Adversarial Robustness to Worst-Case Adversarial Robustness. Our in- troduced formulation represents a broader perspective of the classical "worst-case" adversarial robustness, where the attacker aims identify a single adversarial attack representing "worst-case" losses within a predefined budget and neighborhood. Our Expected Adversarial Robustness focuses on understanding the overall behavior of the underlying graph-based function within the specified input neighborhood. This approach offers a more comprehensive assessment of the model's robust- ness. Nevertheless, we note that our formulation encompasses the adversarial robustness as a special case since by definition these examples are included in our considered neighborhood. In fact, by adjusting the hyper-parameter a, we can isolate these worst-case examples. Lemma 3.2 directly relates Definition 3.1 to the classical "worst-case" adversarial robustness.
Lemma 3.2. Let da.9 be defined graph metric on the metric spaces 9, X. Let f () + y be a graph-based function, we have the following result: If f is ((da.) ,e), (dy, (dl,)))) rrobuus, then f is also ((d e). (dy: "))))"))osss"ooo"
robust.
The proof of Lemma 3.2 is provided in Appendix As a result, our forthcoming theoretical analysis, which considers the general case, is equally applicable to worst-case adversarial examples, which will be also validated experimentally in Section 6
We finally note that the advantages and pitfalls of the generalization of "worst-case" to average robustness have also been studied by Rice et al. (202I)
4 THE EXPECTED ROBUSTNESS OF MESSAGE PASSING NEURAL NETWORKS
We now use our Expected Adversarial Robustness Definition 3.1 to derive an upper bound on the expected robustness of the GCN, based which we introduce our more robust GCN adaptation.
4.1 ON THE EXPECTED ROBUSTNESS OF GRAPH CONVOLUTIONAL NETWORKS
Our work primarily focuses on the theoretical analysis of GCNs within the broader context of MPNNs. The computations of one GCN layer composed of the aggregation of node hidden states over neighborhoods in the graph and subsequent node-wise updates of the hidden states via a weight matrix and non-linear activation function. The updated hidden states are then passed to the next layer for further aggregation and updates. An iteration of this process can be expressed as follows
(C) = (1() (6))
where h,(0) represents the hidden state in the ε-th GCN layer and (0) is the initial node features X E TR W(() E Rxxe is the weight matrix in the L-th layer, e the embedding dimension and (1 a I-Lipschitz continuous non- linear activation function. Moreover, À e Rax=, with being the number the nodes, denotes the normalized adjacency matrix -= AD 1/22
Determining the exact expected adversarial robustness of graph-based function, as outlined in Section 3] poses a significant challenge. To overcome this, we provide an upper bound, referred to as in Definition 3.1 Our definition of adversarial attacks is closely related to the concept of sensitivity analysis. In both cases, the goal is to understand how small input changes can affect the model's 's output. We hence tackled the adversarial task by adopting input perturbation perspective. Similar approaches based on sensitivity analysis have had some success for deep neural networks (DNNs). While extending to other domains such Convolutional Neural Networks is direct, generalizing to graphs presents new challenges. Notably, model dynamics differ due to the Message Passing process involving the adjacency and node features, complicating the task of providing an bound. Since, the architecture itself involves the adjacency matrix, any perturbation on the input produces different dynamic in the model itself, unlike the classical DNNs architecture, which remains static when subject to perturbations. Consequently, the theoretical analysis and results have to reflect the underlying propagation architecture, i.e., the graph structure. Theorem 4.1 provides theoretical insight into the expected robustness of GCNs by establishing an upper bound on the amount of perturbation that GCN can tolerate before its predictions become unreliable.
Theorem 4.1. Let f (9,X) + y denote a graph-based function composed of L GCN layers, with ( denoting the weight matrix of the i-th layer. Further, let d be a feature distance. For attacks targeting node features of the input graph, with a budget e, with respect Definition 3.1
4

---

Published as a conference paper at ICLR 2024
f is ((d ,c), ()): with yy - [ie( ueyy Wu)/o, with w. denoting the sum of normalized walks of length (I. 1) starting from node and V is the node set.
. f ((d"))e)) (d)):))) rrobuutt with y II i= | 1oo with üg = max Uy.
aEV
As previously mentioned, the provided upper-bound in Theorem 4.1 is directly dependent on both the graph structure (in terms walks from the graph's 's nodes) and the propagation scheme (where the length of the considered walks depends the number of message-passingg iterations). The derived upper-bound bound is intuitive: effectively using feature- based attacks is increasingly difficult with increasing graph sparsity; conversely, in dense graphs node feature attacks can have greater effect since the message passing scheme propagates them along a greater number of walks. To make this precise, the expected sum of normalized walks in sparser graph tends to be lower than in denser one, resulting in a reduced bound, indicating more robust model within the considered neighborhood. We finally note that this bound applies to both targeted and untargeted feature modifications, whether limited to specific subset or all the nodes. While our main focus is on node feature- based attacks, our analysis provided in Theorem 4.1 can be extended to structural attacks; Theorem sheds light on this latter case.
Theorem 4.2. Let f (g) - y denote a graph function composed of I. GCN layers, where W denotes the weight matrix of the i-th layer. Further, let d=-0 be a graph distance. For structural attacks with budget the function f is ((d2.) e), (d2, -rorbbustt with
L [ X 2e + L III | [ 122//
-II
(4)
We observe the upper bound in 4 to functionally depend on the size of the graph via |X [2, yielding the intuitive result that larger graphs have more potential targets to attack and thereby give rise less robust models. The proofs of Theorems and 4.2 are provided in Appendix
4.2 ON THE GENERALIZATION TO OTHER GRAPH NEURAL NETWORKS
While our work focuses on GCNs, our analysis can be extended to any GNN, Our theoretical analysis contingent on assuming the input node feature space to be bounded, which is realistic assumption for real word data. For illustration, Theorem 4.3 derives the upper-bound the specific case of GINs.
Theorem 4.3. Let f (G, + y be composed of GIN-layers (with parameter Ç 0, that usually denoted by e in the literature) and (()) denote the weight matrix of the i-th MLP layer. We consider the input node feature space to be bounded, i.e., ||X 222 < B for some B E E, and graphs of maximum degree Dg. For node feature- attacks, with a budget e, the function is (( {), (doo, 7)) 7))--rbusst with
( 1c0 (B
Theorem is proved in Appendix D In addition, following the same assumption, it is possible to derive an upper bound on the GCN's s robustness when subject to both structural and feature-based attacks simultaneously. The complete study and additional information are provided in Appendix
4.3 ENHANCING THE ROBUSTNESS OF GRAPH CONVOLUTIONAL NETWORKS
Leveraging the established upper-bound on the expected robustness in Theorem 4.1 we now introduce novel approach, called Graph Convolutional Orthonormal Robust Networks (GCORNs), which enhances the robustness of a GCN to node feature perturbations while maintaining its ability to learn accurate node and graph representations. To this end, aim design GCN architecture for which the upper bound y as stated in Theorem 4. is low. As this quantity is dependent on the norm of the weight matrices in each layer of the GCN, we propose control the norms of these matrices.
Enhancing the robustness through enforcing matrix norm constraints during training has previously been studied in the context of DNNs through methods such as Parseval regularization (Cisse et al.
5

---

Published as a conference paper at ICLR 2024
2017) or optimizing over the orthogonal manifold (Ablin & Peyré 2022). our experiments, the added constraints of these methods can negatively impact the performance of the graph function and additionally the hyper-paramette tuning can be tricky especially when dealing with large datasets. In our work, we choose to tackle the task by modifying the mathematical formulation of the GCN in (3) encourage the orthonormality of the weights. We have therefore chosen to use an iterative algorithm (Björck & Bowie 1971), that mainly was used in the literature for studying Lipschitz approximation (Amil al. 2019), ensure a f'air trade-off between clean and attacked accuracy. We note that, based on the introduced Theorem 4.1 any orthonormalization method can theoretically enhance the underlying model's robustness. Given our weight matrix W, the iterative process which is computed using Taylor expansion, consists of finding the closest orthonormal matrix W to our weight matrix W. By considering Wo W, recursively compute Wq from
However, observed in
W++1 Wr [ +-1 "
with A 2 O, Q+ = WTW, and p 1 is the chosen order. A key advantage of this orthonormal- ization approach is its differentiabilityy hence its compatibility with the pack-propagation process of training GNNs. By incorporating this projection into each forward pass during the model's training, we encourage the orthonormality of the weights, consequently enhancing its expected robustness.
Training and Convergence of Our Approach. Encouraging the orthonormality of the weight matrices for each layer in our framework mitigates the problems of vanishing and exploding gradients. Our proposed method preserves the gradient norm, leading to enhanced convergence and improved learning (Guo et al., (022). It is important to note that the training of our framework relies on the convergence of the iterative orthonormalization process. From the original work (Björck Bowie 1971) which examined this aspect, convergence is contingent on the condition [WTW - - being satisfied, which can be guaranteed by applying a scaling factor, based on the spectral norm, to the weight matrices before the iterative process. We noticed that this approach not only guarantees that the weight matrices satisfy the necessary condition for convergence but also helps to speed up the convergence and the training process analyzed by previous work (Salimans & Kingma| (201)).
Complexity of Our Approach. Equation (5) entails a trade-off between convergence speed and the approximation's precision. A higher order p yields closer projections in each iteration, resulting in an increased computational complexity. This trade-off must be carefully considered to strike a balance between complexity and approximation accuracy. The main complexity of the method results from the matrix products which are Oee²) where represents the embedding dimension. Our experiments indicate that a low order and small number of iterations often yield a satisfactory approximation in practice. We note that our method's 's complexity does not increase with growing input graph size, distinguishing it from other defenses such as GNNGuard which has a complexity of O(e |E)). where FF| represents the number of edges or GNN-SVD which computes a low-rank approximation through SVD with corresponding complexity of O(n²), with n being the number of nodes. We point out that we conducted an ablation study (reported in Appendix G on the effect of changing the order p and number of iterations & on both the precision of the orthonormal projection (represented by both the clean accuracy and the adversarial accuracy) and the time complexity.
5 ESTIMATION OF OUR ROBUSTNESS MEASURE
Based on our introduced definition of expected robustness in Section 3 we introduce an algorithm to empirically estimate the quantity Adoa,()) [f], serving therefore as new metric to evaluate GNN robustness. While most defense methods on graphs are evaluated using the worst-case accuracy of a
GNN when exposed to specific attack schemes (Bojchevski et al. 2020 Xu et al. 2019a| Zügner & Günneeaan 2019), Adog.9 [J] is an attack-independen and model-agnostic robustness metric based on uniform sampling. It can therefore be used as security checkpoint, addition to existing robustness metrics, to evaluate the GNN robustness against unknown attack distributions.
Numerous model-agnostic robustness metrics (Weng et al. 2018 Cheng et al. [22 have emerged primarily in computer vision. These metrics mainly assess robustness through measuring the distortion between input and output manifolds. While these methods can be extended to the graph classification task with appropriate distortion definitions, their application in the node classification context proves challenging. To our knowledge, there exists no specific or analogous adaptation within the context of graph representation learning. Thus, our proposed evaluation aims to address this gap.
6

---

Published as a conference paper at ICLR 2024
Given that the expected value of indicator random variable for an event E is the probability of that
event, i.e., [[]{E]] = P(E), we use (6) as an equivalent formulation of Ado [f] in (2)
Adog [ = E
(G.X) (G.X)EB (GG.)),)
[dx(((C ( (G, x)) >))
(6)
From the law of large numbers (Bernoulli] 1713), the mean sampling is an unbiased estimator of the vulnerability quantity Adv. [.]. Consequently, we estimate GNN's expected robustness by generating multiple graph pairs ([,, XJ). where each input graph [G, Xx] is sampled from the underlying distribution Dg.x and [G, X] is uniformly sampled from the ball of radius c centered around [G. e.. d' d', X), [G, ([G
X]) I e. This approach can be used for both structural and feature attacks. Since we focus on the latter, we propose sampling strategy based on the distance
max du. GG, XI) = ||X x|x== sE......
| 1.
(7)
where I-lpp is the Lp norm (p > 0) and X,, X, are the i-th rows of the matrices X, X R Since the original dataset consists of samples [G, X] from the underlying distribution Dg.xx we only need to sample uniformly graphs [G, from the neighborhood of the dataset graphs [G,X] such that || - S and G = G. Sampling such X is equivalent to first sample 7 E Rank from B. {z E B=*K | e} and then set X X + Z. Sampling from the ball B, could be performed by partitioning the ball with respect to the possible values of /Z
S, = (Z E B 11 r}.
B. U.
Vr S, 0.
We therefore propose to use the following Stratified Sampling approach, which is based on two main steps: (i) Sample a distance r from [0, c] using the distribution P. defined in Lemma 5. (ii) Sample Z from S,.. Additional details the prior distribution and the sampling from S, are Appendix
Lemma 5.1. Let R be the real finite dimensiimenii space and a positive real number. If R(a) is the random variable indicating the maximum of the Ly norm's 's values inside the ball of radius i.e.
B. = {Z E RRaX mmax;e()....n)) S c}. Then, for every p > 0, the density distribution of R(P) does not depends on p and is defined as follows, (r(r) = K c (5) ( 1,0 Sc....
The proof is available in Appendix [ We note that the proposed framework a practical and theory- based robustness evaluation approach applicable to any GNN, since no assumption has been made on the underlying architecture. Algorithm in Appendix [Hooffers summary of the approach.
EMPIRICAL INVESTIGATION
This section examines the practical impact of our theoretical findings on real-world datasets where we aim to investigate the robustness of GCORN in comparison to other defense benchmarks.
6.1 EXPERIMENTAL SETUP
The necessary code to reproduce all our experiments is available on github In this section, we focus on node classification while we report results on graph classification (Morris et al. 2020) in Appendix ! We use the citations networks Cora, CiteSeer, and PubMed (Sen et al., 2008), the Co-author network CS (Shchur et al. 2018). 8) and the citation network between Computer Science arXiv papers OGBN-Arxiv (Hu ctt al. 2020 Further information about the datasets and implementation details are provided in repeated each experiment 10 times and used Appendix L To reduce the impact of initialization,
https://gttuu..oom./ Sttpa/bbbooomSeeaannnCrree
splits provided with the datasets and for the CS dataset, we followed the framework of Yang et al. (2016). We note that for the node feature-based attacks, normalized the input features to work in continuous space allowing more flexibility in terms of available attacks.
the prain/validations
Attacks. We two evasion and poisoning feature- based attacks: (i) The baseline random attack injecting Gaussian noise ( I) to the features with a scaling parameter controlling the attack budget; (ii) The white-box Proximal Gradient Descent (Xu et al. 2019a), which is sadient--baedd
7

---

Published as a conference paper at ICLR 2024
Table I: Attacked classification accuracy (# standard deviation) of the models on different benchmark node classification dataset after the feature attacks.
Atlack
Dataset
GCN
GCN-k
AirGNN
RGCN
ParsevalR
GCORN
Cora
68.4 + 1.9
69.2 + 2.6
73.5 + 1.9
71.6 = 0.3
72.9 + 0.9
77.1 + 1.8
CiteSecr
57.8 + 1.5
62.3 + 1.2
64.6
+ 1.6
63.7 = 0.6
65.1
+ 0.8
67.8 + 144
Random
PubMed
68.3 + 1.2
71.2 + 111
70,9
+ 1.3
71.4 0.5
71.8 + 0.8
73.1 + 1.1
(1) 0.5)
CS
85.3 85.3
86.7 1.1
87.5
+ 1.6
88.2 = 0,9
87.6 0.6
89.8 1.2
OGBN-Arxiv
68.2
0.5
66.5
1.3
63.8 = 1.9
68.3 1.9
69.1 1.8
Cora
2.1
2.8
$3.7
52.
55.3 1.2
57.6 1.9
CiteSeer
38,2
45
49.8 4988
43.7 2
51.2
57.3
Random ( 1.0)
62.3
62
61.9
61.3
CS
69.9
0.9
76.7
76.2
78.7
81.3 1.6
OGBN-Arxiv
66.4
0.6
6.77
63.0
66.1 1.7
67.3
Cora
2..1
58.3
68.2 1.8
62.5
68.6
71.1 1.4
CiteSeer
52.3 1.1
1.
2.1
619 I.
62.1
65.6 1.4
PGD
PubMed
66.1..2.1
1.3
70.8 1.7
69.5
68.9
72.3 1 1.3
CS
71.3
7.8
7.13
76.6122
0.
79.6 + 1.2
OGBN-Arxiv
67.5
49.9
55.7 + 0.9
03,6=00
67.6 1.2
68.1 + 1.1
Cora
64.2 1 5.2
66.7 3.8
63.4 3.8
67.5 2.3
68.3 + 1.4
CiteSeer
55.8 1.4
67.5
70.8 = 3,8
69.2
0.24300 3.8
77.5 + 2.5
Nettack
PubMed
60.0
65.8
1. 2.9
69.2
1 1.4
71.7 1 3.8
68.3 1.4 1.4
70.8 1 1.4
CS
55.8 1
71.6 + 1.4
76.7
+ 1.4
71.7
= 2.9
75.8 + 288
78.3 + 1.4
OGBN-Arxiv
49.2 9.2:229 2.9
53.3
1.4
56.7
+ 1.4
52.6 = 2.5
55.8 + 1.4
55.8 + 1.4
[b]
(4)
9.8
12
02
02
ra (dotted). ra (solid)
Figure 1: (a) and (b) display Adv for Cora and OGBN-Arxiv. (c) Robustness guarantees on Cora, where Tas Fd are respectively the maximum number of adversarial additions and deletions.
approach to the adversarial optimization task. We set the perturbation rate to 15%. While this attack has limited success for structural perturbations due to the discrete space, is known to be powerful in continuous spaces, such as the node feature space; (iii) The argeted-attack Nettack (Zügner et al.) 2018), where similar the original study, selected 40 correctly classified target nodes, comprising 10 with the largest classification margin, 20 randomly chosen, and 10 with the smallest margin.
Baseline Models. Currently, presented in Section 2 there only few methods for defending against feature-bases adversarial perturbations. We compare against (i) GCN-k (Seddik et al.) (022) :
(ii) RobustGCN (RGCN) (Zhu et al., 2019); (iii) AIRGNN (Liu et al., 202 la) and (iv) finally compared to the Parseval Regularization (ParsevalR) (Cisse et al.) 2017). another orthonormalization method, with great success the computer vision. The aim mainly motivate the merits of our proposed orthonormalization method based on the iterative weight projection.
6.2 EXPERIMENTAL RESULTS
Empirical Estimation of Our Expected Robustness. We start by investigating the robustness of the different considered benchmarks through the empirical estimation Ado as introduced in Section 5 (see Appendix M L. [ and (b) report the estimated values of the vulnerability Adu f for our GCORN and the considered defense benchmarks for the Cora and OGBN-Aree datasets, respectively. Additional results further datasets provided in Appendix [] The figures show that our GCORN yields the lowest adversarial vulnerability indicating therefore that our proposed approach is exhibiting greater expected robustness within the considered neighborhood.
8

---

Published as a conference paper at ICLR 2024
Table 2: Attacked classification accuracy (# standard deviation) of the models on different benchmark node classification datasets after the structural attacks.
Attack
Dataset
GCN
GCN-Jaccard
RGCN
GNN-SVD
GNN-Guard
ParsevalR
GCORN
Cora
73.0 0.7
75.4 1.8
69.2 + 0.3
73.6=0,9
74.4 0.8
71.9 + 0.7
77.3 0.5
CiteSeer
63.2
69.5
68.9
65.8 6
68.8 155
08.3...3
73.7 0.3
Mettack
PubMed
60.7 0.7
62.9
65.1 65.1:044
82.1 0.8
84.8 0.3
69.5
71.8
CoraML
73.1 0.6
7.44
1.1
71.3 1.0
76.5 0.7
76.9 1.3
79.2 0.6
Cora
76.7 7.9
7.
72.0
71.6
7.
78.4 1.2
79.9 0.4
CiteSeer
0.8
70.9
62.2
60.3 2.4
2.2
70.6
73.1
PGD
PubMcd
1.6
81,9 7.
0.4
77.4 0.7
CoraML
1.2
2.40
73.1 0.3
0.8
81.3
84.1 + 0.2
Cora
0.8
7.9
79.6 0.3
72.2 1.4
75.6
79.7 + 0.8
78.9 0.4
CiteSeer 6.5
6..0
68.7 0.5
62.6 1.2
1.11111
68.9 08.9004 0.4
DICE
PuhMcd
0.4
0.2
79.8 0.4
76.6 0.5
77.8
79.2 0.3
78.1
CoraML
0.6
0.3
80.1 0.4
58.7
0.4
77.5 0.2
80.5 1.3
81.1 + 0.8
Worst-Cass Adversarial Evaluation. Table the attacked node classification accuracies for our GCORN and the other considered benchmarks. The results show that, when subject to features- based adversarial attacks with varying budget, the performance GCN is severely impacted. Instead, the proposed GCORN demonstrates a significant improvement in defending against these attacks comparison to other methods. For instance, GCORN outperforming the GCN-k by an average of ~ 12% in accuracy. In certain situations, GCORN demonstrates the ability to recover the GCN's performance to a level equivalent to no adversarial attack. Furthermore, the baselines are not as effective in defending against gradient-based attacks. In contrast, GCORN, which is based on an attack-agnostic upper bound (Theorem 4.1.. demonstrates its ability to defend against grudient- based attacks. We. additionally study the trade-off between robustness and input sensitivity in Appendix
Certified Robustness. In addition to our probabilistic and empirical evaluations, we assessed the certified robustness of a GCN and our proposed GCORN on the Cora dataset using the sparse randomized smoothing approach (Bojchevski et al., 2020). Specifically, we plotted their certified accuracy (r.,, ra) for varying addition ra and deletion ra radii. Figure showcases theoretical robustness; GCORN improves the certified accuracy with respect to feature perturbations for all radii.
Structural Perturbations. Although focus is node feature-based adversarial attacks, also provided a theoretical analysis for structural perturbations (Theorem 4.2). To evaluate the effectiveness of our approach handling structural attacks, we conducted an empirical comparison to five bascline defense methods that focus on structural perturbations, GNN-Jaccard (Wu et al. 2019). RobustGCN (Zhu al., 2019). GNN-SVD (Entezari al.] 2020), GNNGuard (Zhang & Zimik 2020) and the Parseval Regularization (ParsevvlllP (Cisse et al. 2017) We considered three structural adversarial attacks with a perturbation budget 0.1[8]: "Mettack" (with the 'Meta-Self' strategy) (Zügner& & Günnemann] (211)), "Dice" (Zügner & Günnemann 2019) and "PGD" (Xu) jet al. 2019a). The average node classification accuracies of the considered models under attack presented in Table Our GCORN shows remarkable defense capabilities against these attacks, outperforming other methods of 12 experiments. This result highlights the effectiveness of our proposed defense mechanism in enhancing the robustness of the underlying GCNs against structural perturbations while providing theoretical guarantees which are absent for the considered baselines.
7 CONCLUSION
We have proposed GCORN, an adaptation the GCN, which robust against feature- adversar- ial attacks. The approach utilizes the orthonormalization of weight matrices control the robustness of GCNs via an upper bound we derived. Additionally, we have proposed a probabilistic evaluation method for the robustness of GNNs based on the introduced definition of "Expected Adversarial Robustness". Experimental results comparing our GCORN model to the standard GCN and existing defense methods show the superior performance of GCORN on different real-world datasets.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
This work was partially supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation. The computation (on GPUs) was enabled by resources provided by the National Academic Infrastructure for Supercomputing in Sweden (NAISS) at Alvis partially funded by the Swedish Research Council through grant agreement no. "2022-06725". This work was granted access to the HPC resources of IDRIS under the allocation "2023-AD01061 1440RI 3340RR"" made by GENCL Y.A. supported by the French National research agency via the AML-HELAS (ANR-19-CHIA 11-CC19--00O0 (0200 project. We furthermore want to thank Dr. Henrique Helfer Hoeltgebaum for a very helpful discussion on cybersecurity during the rebuttal period.
REFERENCES
Pierre Ablin and Gabriel Peyré. Fast and accurate optimization on the orthogonal manifold without retraction. In International Conference on Artificial Intelligence and Statistics, pp. 5636-5657, PMLR, 2022.
Cem Anil, James Lucas, and Roger Grosse. Sorting lipschitz function approximation. In International Conference on Machine Learning. pp. 291-301. PMLR, 2019.
Jakob Bernoulii. Ars conjectandi: opus posthumum: accedit Tractatus de seriebus infinitis; et Epistola gallice scripta de ludo pilae reticularis. Impensis Thurnssiorum, 1713.
Å. Björck and C. Bowie An iterative algorithm for computing the best estimate of an orthogonal matrix. SIAM Journal Numerical Analysis, pp. 358-364, 1971.
Aleksandar Bojchevski and Stephan Günnemann. Certifiable robustness to graph perturbations.
Advances in Neural Information Processing Systems, 32, 2019.
Aleksandar Bojchevski, Johannes Gasteiger, and Stephan Günnemann. Efficient robustness certifi- cates for discrete data: Sparsity-aware randomized smoothing for graphs, images and more. In International Conference on Machine Learning. pp. 1003-1013, PMLR, 2020.
Yongqiang Chen, Han Yang, Yonggang Zhang, Kaili Ma, Tongliang Liu, Bo Han, and James Cheng. Understanding and improving graph injection attack by promoting unnoticeability. International Conference of Learning Representations, 2022.
Wuxinlin Cheng, Chenhui Deng, Zhiqiang Zhao, Yaohui Cai, Zhiru Zhang, and Zhuo Feng. Spade: A spectral method for black-box adversarial robustness evaluation. In International Conference Machine Learning, pp. 1824-1824. PMLR, 2021.
Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usunier. Parseval networks: Improving robustness adversarial examples. In International Conference on Machine Learning, pp. 853-863. PMLR, 2017.
Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song. Adversarial Attack on Graph Structured Data. In Proceedings of the 35th International Conference Machine Learning, pp. 1115-1 124, 2018.
Sofiane Ennadir, Yassine Abbahaddou, Johannes F. Lutzeyer, Michalis Vazirgiannis, and Henrik Boström. A simple and yet fairly effective defense for graph neural networks, 2024.
Negin Entezari, Saba A. Al-Sayouri, Amirali Darvishzadeh, and Evangelos E. Papalexakis. All you need is low (rank): Defending against adversarial attacks on graphs. In Proceedings of the 13th International Conference Web Search and Data Mining, pp. 169-177, 2020.
Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. A Fair Comparison of Graph Neural Networks for Graph Classification. In 8th International Conference on Learning Represen- fations, 2020.
Fuli Feng, Xiangnan He, Jie Tang, and Tat-Seng Chua. Graph adversarial training: Dynamically regularizing based on graph structure. IEEE Transactions on Knowledge and Data Engineering, 33(6):2493-2504 2019. 2019.
10

---

Published as a conference paper at ICLR 2024
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning, pp. 1263-1272. PMLR, 2017.
lan Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In International Conference on Learning Representations (ICLR), 2015.
Lukas Gosch, Daniel Sturm, Simon Geisler, and Stephan Günnemann. Revisiting robustness in graph machine learning. International Conference of Learning Representations, 2023.
Stephan Günnemann. Graph neural networks: Adversarial robustness. In Graph Neural Networks: Foundations, Frontiers, and Applications, pp. 149-176. Springer, 2022.
Kai Guo, Kaixiong Zhou, Xia Hu, Yu Li, Yi Chang, and Xin Wang. Orthogonal graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 3996-4004, 2022.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong. Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benehmark: Datasets for machine learning on graphs. Advances in Neural Information Processing Systems, 33:221 18 22133, 2020.
Mingxuan Ju. Yujie Fan, Chuxu Zhang, and Yanfang Ye. Let graph be the go board: gradient-free node injection attack for graph neural networks via reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 4383-4390, 2023.
Steven Kearnes, Kevin McCloskey, Mare Berndl, Vijay Pande, and Patrick Riley. Molecular graph convolutions: moving beyond fingerprints. Journal of Computer-Aided Molecular Design, 30(8): 595-608, 2016.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015.
Thomas N. Kipf and Max Welling. Semi-Supervised Classification with Graph Convolutional Networks. International Conference on Learning Representations (ICLR), 2017.
Runlin Lei, Zhen Wang, Yaliang Li, Bolin Ding, and Zhewei Wei. Evennet: Ignoring odd-hop neigh- bors improves robustness of graph neural networks. Advances in Neural Information Processing Systems, 35:4694 4706, 2022.
Xiaorui Liu, Jiayuan Ding, Wei Jin, Han Xu, Yao Ma. Zitao Liu, and Jiliang Tang. Graph neural networks with adaptive residual. Advances in Neural Information Processing Systems, 34:9720- 9733, 2021a.
Xiaorui Liu, Wei Jin, Yao Ma, Yaxin Li, Hua Liu, Yiqi Wang, Ming Yan, and Jiliang Tang. Elastic graph neural networks. In International Conference on Machine Learning, pp. 6837-6849, 2021b.
Xiaoxiao Ma, Jia Wu, Shan Xue, Jian Yang, Chuan Zhou, Quan Z Sheng, Hui Xiong, and Le- man Akoglu. A comprehensive survey graph anomaly detection with deep learning. IEEE Transactions on Knowledge and Data Engineering, 2021.
Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. TUDataset: A collection of benchmark datasets for learning with graphs. Graph Representation Learning and Beyond (GRL+), ICML Workshop, 2020.
Masaru Nagisa. The p-norm of some matrices. arXiv preprint arXiv:2209.0855. 2022.
Harald Niederreiter. Random number generation and quasi-Monte Carlo methods. SIAM, 1992.
Mustapha Raissouli and Iqbal H Jebril. Various proofs for the decrease monotonicity of the schatten's power norm, various families r n- norms and some open problems. Int. Open Problems Compt. Math, 3(2):164-174, 2010.
11

---

Published as a conference paper at ICLR 2024
Leslie Rice, Anna Bair, Huan Zhang, and J Zico Kolter. Robustness between the worst and average case. Advances in Neural Information Processing Systems, 01778440-7751,,222 2021.
Tim Salimans and Durk P Kingma. Weight normalization: A simple reparameterization to accelerate training of deep neural networks. Advances in Neural Information Processing Systems, 29, 2016.
Yan Scholten, Jan Schuchardt, Simon Geisler, Aleksandar Bojchevski, and Stephan Günnemann. Randomized caassggeinterception smoothing: Gray-box certificates for graph neural networks. Advances in Neural Information Processing Systems, 35:33146 44-33158,, 2022.
Jan Schuchardt, Aleksandar Bojchevski, Johannes Gasteiger, and Stephan Günnemann. Collective robustness certificates: Exploiting interdependence in graph neural networks. In International Conference on Learning Representations, 2021.
Mohamed El Amine Seddik, Changmin Wu, Johannes Lutzeyer, and Michalis Vazirgiannis. Node feature kernels increase graph convolutional network robustness. In International Conference Artificial Intelligence and Statistics. pp. 6225 6241. PMLR, 2022.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad Collective classification in network data. Al magazine, 29(3):93 93, 2008
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günneemann. Pitfalls of graph neural network evaluation. Relational Representation Learning Workshop (R2L 2018), NeurlPS, 2018.
Xianfeng Tang, Yandong Li, Yiwei Sun, Huaxiu Yao, Prasenjit Mitra, and Suhang Wang. Transfer- ring robustness for graph neural network against poisoning attacks. In Proceedings of the 13th international Conference Web Search and Data Mining, pp. 600-608. 2020.
Shuchang Tao, Qi Cao, Huawei Shen, Junjie Huang. Yunfan Wu, and Xueqi Cheng. Single node injection attack against graph neural networks. In Proceedings of the 30th ACM International Conference on Information& Knowledge Management. ACM, 2021.
Shu Tezuka. Uniform random numbers: Theory and practice, volume 315. Springer Science & Business Media, 2012.
Yiwei Wang, Shenghua Liu, Minji Yoon, Hemank Lamba, Wei Wang, Christos Faloutsos, and Bryan Hooi. Provably robust node classification via low-pass message passing. In 2020 IEEE International Conference on Data Mining (ICDM), pp. 621-630. IEEE, 2020.
Tsui- Wei Weng, Huan Zhang, Pin- Yu Chen, Jinfeng Yi, Dong Su, Yupeng Gao, Cho-Jui Hsieh, and Luca Daniel. Evaluating the robustness of neural networks: An extreme value theory approach. In International Conference Learning Representations (ICLR), 2018.
Huijun Wu, Chen Wang, Yuriy Tyshetskiy, Andrew Docherty, Kai Lu, and Liming Zhu. Adversarial examples for graph data: Deep insights into attack and defense. In Proceedings of the Twenty- Eighth International Joint Conference on Artificial Intelligence, IJCAI-19, pp. 4816-4823, 2019.
Kaidi Xu, Hongge Chen, Sijia Liu, Pin- Yu Chen, Tsui- Weng, Mingyi Hong, and Xue Lin. Topology attack and defense for graph neural networks: An optimization perspective. Proceedings of the Eventy-Eights International Joint Conference on Artificial Intelligence (IJCAI-19, 2019a.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How Powerful are Graph Neural Networks? In 7th International Conference on Learning Representations, 2019b.
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International Conference on Machine Learning, pp. 40-48. PMLR, 2016.
Haoxi Zhan and Xiaobing Pei. Black-box Gradient Attack on Graph Neural Networks: Deeper Insights in Graph- Attack and Defense. arXiv preprint arXiv.2104.15061, 2021.
Xiang Zhang and Marinka Zitnik. Gunguard: Defending graph neural networks against adversarial attacks. Advances in Neural Information Processing Systems, 33:9263-9275, 2020.
12

---

Published as a conference paper at ICLR 2024
Xin Zhao, Zeru Zhang, Zijie Zhang, Lingfei Wu, Jiayin Jin, Yang Zhou, Ruoming Jin, Dejing Dou, and Da Yan. Expressive 1-lipschitz neural networks for robust multiple graph learning against adversarial attacks. In International Conference Machine Learning, pp. 12719-12735. PMLR, 2021.
Dingyuan Zhu, Ziwei Zhang, Peng Cui, and Wenwu Zhu. Robust graph convolutional networks against adversarial attacks. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 1399-1407, 2019.
Xu Zou, Qinkai Zheng, Yuxiao Dong, Xinyu Guan, Evgeny Kharlamov, Jialiang Lu, and Jie Tang. Tdgia: Effective injection attacks on graph neural networks. Proceedings of the 27th ACM SIGKDD Conference Knowledge Discovery & Data Mining, KDD '21, 2021.
Daniel Zügner and Stephan Günnemann. Adversarial attacks on graph neural networks via meta learning. In 7th International Conference on Learning Representations, 2019.
Daniel Zügner and Stephan Günnemann. Certifiable robustness and robust training for graph convolutional networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. ACM, 2019.
Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks neural networks for graph data, In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2018
13

---

Published as a conference paper at ICLR 2024
Appendix: Bounding the Expected Robustness of Graph Neural Networks Subject to Node Feature Attacks
A PROOF OF PROPOSITION I.I A.I
Proposition A.1. Let f (9, () + y be a graph-based classifier subject to feature-based attacks and X' be of dimension D. Let d.1 be the graph distance corresponding to the spectral norm, df corre- sponding the L1 norm and d corresponding to the Lp norm with p 2. If is ((d2 ,c), (dy, robust, then f is also ((d)), DD-1/2c) (dy, (1),:))))mm -robutt and ((d)), D-2c), (dy, VD+))
Proof. Let IR the real finite dimen-oimealional space. The set of standard considered norms of P for x (Z1,...,,ID E R is
1/v
Vp 0, |0111- - Σ l
| |0
max |20g] I8i5n
As for any x R.,, the mapping p + |I>||p is monotone decreasing (Raissouli & Jebril, 2010 meaning that
q > p 2 |
||rl|--
Using Holder's 's inequality with s = q/p > 1, we have
D
(1|=11))* =
x
t=1
D
Σ
i=1
1-!
D
Σ
(1x;
Σ
1
D
1-2
Σ
(Lo: (3
Σ1
D p/4 (1|=118)p
Thus,
9> p21 |
11/1- 1//1-1//1/olll
(8)
We additionally have that
1/9
|
Σ
12:19
1/9
Σ
| 118
< D //
||
D
14

---

Published as a conference paper at ICLR 2024
From 8 and
9
deduce that
DJ $ $1|||||5 |واا
D |11l|
Consequently, for any matrix N E RD
D we have the following
D : N || Nolll:
p> p>q21= Vz +
D >||>||5> | D
|
D D ||
D
||
Vx
D " S |
D
Va 0, D ||Nxll1
||
| lpp
I D
|
||=||p
= D $ N| _ || D* ||
In partieular, for p have
Ag > 2, AN E REXD
1 VDIN
(10)
Similar for q = 2 and p = 1, we have
E ROND
|N DI
(11)
The Inequalities (T) and 11] stay valid for the distance related the norm T.p e.,
R
.p 2,
Xx) - VD),(X,X).
dx(X,X) < (X))..
Finally, for every input graph X, we have
Vp > 2, ((G',)) (1, X1,
VD [(' [d2([G, <c),
1
[(G',x')
< 1 c ((G | x1, (G, <c).
1
Therefore, the ((c)) , )) (dy: r)--buusttss of graph
function
implies the
((d)), D-1/22), (dy, 7)) robustness and (ld"))D-'c) (dy, - robusttess.
B PROOF OF LEMMA 3.2
Lemma. Let da.8 be a defined graph metric on the metric spaces G, Let / (9, + + graph-based function, we have the following result: If f is ((d%,) (),, (dy, rrbbust then is also (( .e), (dy, (()b,,)))"wowl "woss-ortt- robust.
(G, < <} be the set of "worst-case" adversarial attacks within the attack budget We denote the expected vulnerability of graph function f on the set of worst-case adversarial examples as Adva. fflwwa..
Proof. Let , = {(A
"ffl
By definition, we have Wa. c (G, Consequently, we have that was X),
Ad [[]lwa " F(G.X)DDax
(12)
{((G. (G, 8) E (G, (G
(13)
< Lf
(14)
Let the graph function f be (daa.0, ,)) (dy, ()) robust, then Adv.. [ 7. From 114. we have
15

---

Published as a conference paper at ICLR 2024
W - Ado Adu2.Pffl s.
We therefore, can conclude that if f is ((da.), c), (dy, 7)) - then f is ((da.), .c), (dy,))) "worst-case" robust.
C PROOF OF THEOREM 4.1 AND 4.2
funciioon composed of L GCN layers, with W denoting the weight matrix of the i-th layer. Further, let d be a feature distance. For attacks targeting node features of the input graph, with a budget G, with respect Definition 3.1
Theorem. Let f: (9,X) - Y denote a graph-based function
I is ((d01, e), rr)obus with = =I[ the sum of normalized walks of length (I. - 1) starting from node u and V is the node set.
wu)/o, with wn, denoting
f is is ((d0), ,e), (d) robbutt with 7 = II || 1lo0 with dg = max Uy.
WEV
Proof. Let's consider a graph-function f that is based on L layers of GCN. The GCN message- message-passing passing propagation can be written for a node as
W(0 (F-1)
(0 = (8)
(15)
VEN( U(w) V(1 d,.((1 d.))
where W(E) E Red ixde is the learnable weight matrix with de being the embedding dimension of layer and g(4) is the activation function of é-th layer. We recall that (0)) = -X E gaxd is set to the initial node features.
Let X the original node features and denote by X' the perturbed adversarial features. Let's consider node u E V, denote by h. its representation in the clean graph and hi, its representation in the attacked graph, only consider node feature based adversarial attacks, then by definition the original node u and its corresponding node in the corrupted graph have the same neighborhood, can therefore write
note that the activation functions (o()))<<< are nonexpensive. Since
[ -1((10 11 ( 11(0
W (6-1)
E w(0/p(--1 d'EN())U()) v(1 dh) d..) )|
=1oo(0
= vEN(w) /(1 dh) dr)
-(00
(e-11)
11((-1)
<||W
Σ
4''
VEN(H)U(M) ((1 + dw))(1 de)
d'E (1+ dl )1 + dhe
h 11-1) (6-1)
< <|
Σ
VEN(u)
/11 dry) de)
Σ W((-1))(e-2)
1
=|
Σ
(EN(MUU() /(1 d1 +d)
JEN())U(M) ((1
W((-1))
((-1))
JEN(o)
(1+ do) +dg)
h (e-1) (((-1))
|W ((-D))
Σ UE)( /(1 de d. JEN(UUU)) 41+ d.)
Σ
By iteration on the same process, we get the following result:
16

---

Published as a conference paper at ICLR 2024
[ I s
Σ VEN(w) UMN
1=1
X2 X VEN(UiU d.) d .,)... /
with th being the sum of normalized walks of length (Z. 1) starting from node u.
Let's now consider the final output of the model which represents the case of node classification the individual output of each node.
- -(4,
||
((L)
||
Based on the previous formulation, we have the following results:
1 Σ
DEV
II(AA, X) - -(A,
((
lcc
max V.
WEV
Therefore, we computed the Lipschitz constant of our considered model f. To link this constant to our robustness definition in Equation 2
we use the Markov inequality as follows
Ado [f] P(G.Xi~Do.x ((, Ba,s(G,XX,) s.. (.I d
8),
1 E (G.X)~Do.x.
XI X(Al
0 (G', (G.
[
1ppp
e max wEV
th
Thus, the classifier ʃ is ((ra11 e), (doo, robust robust with
II
W (
max w..oo. wEV
And we also have that the classifier is ((a011 .c), (d), robust with
|e( Σ ww)/o.
Theorem. Let f (G. - y denote a graph function composed of L GCN layers, where W())
denotes the weight matrix of the i-th layer. Further, let d=.u be a graph distance. For structural attacks with budget the function J is ((d2.) .), (d2, 7)) robbust with
L
x (11
(0) 1)/a.
17

---

Published as a conference paper at ICLR 2024
Proof. Following the same analogy, let's consider the case of structural perturbations. We only consider that the activation functions (ax()) ( are nonexpensive. In this setting, the graph shift operator (the normalized adjacency matrix in our work) is the one to he edited and the input features are shared between the two graphs. Let À the clean adjacency and (0) its hidden represented
i-th layer and A', (1) with the attacked/perturbed one.
Let's first consider the following
| = 11 (Agh 11-11 (00001100))) wl0
< || (nn
By recursion, we have: || = II [
From another side, we have the following
[ (An(" (()) ( (A'h') 1l) = w A
(0
| |1 A 11
10) Ah 112
I [1I 11(0)) 10 (Ā (Ā- A)ll
[(]II()) -100 11+1|| (I1(A= (1)(A))))12)
[I - -
By recursion, we get the following (By considering Vi 1: | 2 1)
(A,, $(A,, X)112 - w X||e + T 1
xIIe |
||||| + L I]
1=1
Similarly to the previous proof, we deduce that the classifier f is ((d2.0, e), (d2, 7))-uobust where
== II. - ||
x
|((l
LII IWW/)//
D PROOF OF THEOREM 4.3
Theorem. Let f (G + y be composed of L GIN-layers (with parameter Ç 0, that is usually denoted by in the literature) and W denote the weight matrix of the i-th MLP layer. We consider the input node feature space be bounded, i.e.. || < B for some B E IR and graphs of maximum degree Aç. For node feature-batt based attacks, with a budget e, the function f is (1.),1 ,e), (dos, (d) -robuutt with
W l (B Ao +c/o.
18

---

Published as a conference paper at ICLR 2024
Proof. Let's now consider graph-function f that is based on L GIN-layers (with parameter Ç 0, that is usually denoted by e in the literature). The GIN message- passsng propagation process can be written for node u
+C) ((+22) 7(1 (1++
E 4 VEN
where T denotes a Neural Networks (a MLP) for example and Ç denotes the parameter of the GIN. We recall that A (0) X Rgxd is set to the initial node features.
Let X the original node features and X the perturbed features. Let's consider node E V, denote by hy its representation in the clean graph and N2 its representation in the attacked graph note that consider the activation functions be nonexpensive. Since only consider node feature based adversarial attacks, then by definition the original node u and its corresponding corrupted node have the same neighborhood, we therefore write
( - (1(51 |1700 (1+ + 116-1)) (T(0 + C) +
vEN(u)
vEN(u)
(1 1(l--)))+ (n - -1((-1)))
vEN(u)
We assume that the input feature space Hu bounded, thus each hidden space Hi of the iterative process of message passing is bounded and let B max be its global maximum bound. From the previous result, we have
PST.
IN: 11 || + ()(1))1)) - ((((-1)) + B x deg(u))l
By iteration over the previous process, and by considering vi> 1: | 2 1, we can write
L.
L I
1 +
( -1((1)) || < B x deg(u) x
(1+
(1 1 - 10
1=1
1=1
1=1
< B deg(u)
I(+
(11
E=1
1=1
1=1
L
[ deg(u)
E (1+C) + (1+
Since we consider the GIN GIN-parameter ( x 0, we can deduce from the previous result that
[M(C-1) - H (e+ s
[[ L x deg(u) + c)
Let's consider the final output of the model which represents in the case of node classification the individual output of each node.
((A, || ( (L))
Based the previous formulation, have the following results
19

---

Published as a conference paper at ICLR 2024
II lB L max deg(u))
wEV
Similar to the previous proof of Theorem we connect the Lipschitz constant of our considered model f to the robustness definition in Equation through Markov inequality and we get the following
max deg(u) + e|/o. wEV
E GENERALIZING TO ANY GRAPH NEURAL NETWORK
While this work focuses GCNs, it can be easily extended to other GNN architecture. Given the iterative nature of GNNs, they can be viewed as a composition of multiple continuously differentiable functions, fi H, H,+1. where H. represents the input space of the i th function. The Lipschitz constant, as shown in Zhao et al. (021 is given by C = II, V fall. The functions ife hv can be grouped into two categories (i) The set L of functions fa that linear with corresponding parameter W. (ii) The set of functions that are not linear. We can hence decompose C' according
the nature of the function follows
C' C'= (II (IIWa)) S:ECC
fEEC
We can assume the input feature space Ho be bounded; this a realistic assumption. Thus, each hidden space Hi is also bounded, and since (Vfi),,e are continuous functions on bounded spaces, there exists an upper bound C; for fill. Therefore, there exists C 0, such that,
C' C's ISCIII WWll.
DEEC
We return the previous case by simply taking e' = eC/C". Furthermore, following the assumption on the input feature space being bounded, it is possible to derive an upper bound on the GNN's ro- bustness when subject both structural and feature-based attacks simultaneously (See Appendix F.
F VULNERABILITY UPPER-BOUND WHEN DEALING WITH BOTH STRUCTURAL AND NODE FEATURES ATTACKS
In this section, we derive the upper-bound for GCN's vulnerability Adva, when dealing with both structural and feature-based attacks simultancously.
3. < - (G.
[I)(A), - (G..X))BBa.o(GGi...)))
< -
E
[I](A), - ((AI, (2), [(A2,
(G..X))EBa
<
E
(G..I)~DDo..
[]](A), X1) - S(A,, (21,; X2) 1(12, X2)
< EE (G.,N))DDO..
[I] X1) - X2)lee+
((G
[II(AA,))) ( X2)
(G.
(G..)))eBB.alGGG....)
20

---

Published as a conference paper at ICLR 2024
Table 3: Attacked classification accuracy (# standard deviation) of the models on different benchmark node classification datasets after both structural attacks and node feature attacks application.
Dataset
GCN
GCN-Jaccard
RGCN
GNN-SVD
GNNGuard
ParsevalR
GCORN
Cora
76.7 1.2
76.7 + 0.4
78.1 + 0.6
65.9 4.0
61.0
77.6
79.8 0.7
CiteSeer
68.7 = 0.3
71.5 11.50.33
68.9 0.8
0.8
6.5
65.0
70.9 0.6
74.2 = 0.3
PubMed
47.0 100=0..
49.4
51.2 0.4
4.5
40.3
49.7 1.1
53,9 0.8
CoraML
63.3
32.2
59.7
53.8 0.8
1.5
63.4
We already established upper-bound in Appendix C for each term of the previous inequality. Therefore, we can have a new upper-bound bound for Ad
[[ W
L IIc Σ WEV
[I [ + IIw
Ad σ
wal) c+
Following the assumption on the input feature space being bounded, i.e. 3B Vx |||| S B. the inquality become
Ad
1
[[wwo]]
E NEV
w.,)²
B(1 + I
Thus, the classifier is d robust where
7= = (Iwon)
Σ NEV
ui.)² B(1
([ c/0.
F.1 EXPERIMENTAL VALIDATION
We assessed the efficacy of our proposed method against both Structural and Node-feature- baaedd adversarial attacks simultaneously. This evaluation involved combined evasion attack approach, wherein two attacks were integrated. Initially, we generated the perturbed adjacency matrix by employing surrogate GCN model along with the "Mettack" (utilizing the 'Meta-Self" strategy) (Zügner& & Günnemann 2019). Subsequently, we perturbed the node features using a random attack strategy involving the injection of Gaussian noise (O0 I) into the features. This perturbation was controlled by scaling parameter y,, which we identified as effective in prior experiments. For the structural perturbations, we set the perturbation budget 0.1E, while for the node features, was set to 5.0. We compared our method to the same considered defense benchmarks that were used in Section
G TIME AND COMPLEXITY ANALYSIS
Drawing from the original paper Björck Bowie 1971), it has been established that the Bjorck orthonormalization method will always converge, provided that the condition |WT T||2 1 met. In this section, we will begin by examining the connection between the selected order, the number of iterations and the resulting performance and then present empirical time analysis of the proposed GCORN on various datasets.
G.1 ON THE EFFECT OF ORDER/ITERATIONS
As per the projection equation 5 it appears that a higher order/iteration generally results in a more precise projection of the weight matrix. In our study, gauge the accuracy of the approximation by assessing the model's performance in the absence of adversarial attacks, as well as under attack. Although our experiments demonstrate that employing the first order with restricted number of
21

---

Published as a conference paper at ICLR 2024
iterations produce satisfactory outcomes, we believe that hyper-parameter analysis should be conducted. Consequently. we evaluate the influence of modifying the order (while maintaining constant number of iterations) the resulting accuracy in Table 4
Table 4: Performance of GCN and our proposed GCORN model, for different used approximation orders, the Cora dataset.
GCN
GCORN(1 ORD)
GCORN(2 ORD)
GCORN(3 ORD)
TRAINING TIME (IN S) ACCURACY W/O ATTACK
0.01
0.07
8.7 +: 0.07
10.9 0.08
79.2 + 1.6
78.8 + 1.3
79.8 + 0.9
80.8 - 1.1
ACCURACY W. ATTACK
68.4 1.9
77.1 2.1
78.3 + 1.1
78.6 = 0.4
Table 4 shows both clean and attacked accuracy of the GCN and proposed GCORN and the corre- sponding standard deviations for different orders. We observe that using higher order approximations generally leads enhanced accuracy and robustness, albeit at the expense of increased running time. Therefore, the choice of order hyperparameter employed in the approximation must be carefully tuned for each application find the best trade-off between bbbustness,accuraac and training time. In our experiments, we found that an approximation of order yielded adequate and satisfactory results.
G.2 ON TRAINING TIME
In line with the above, also investigate the training time of model compared to that of standard GCN. To conduct this experiment, we held the order and number of iterations constant and utilized identical architectures and hyperparameters for both models (see Appendix D
Table 5: Mean training time analysis (in s) of our GCORN in comparison to the other benchmarks.
DATASET
GCN
GCN-K
AIRGNN
RGCN
GCORN
CORA
2.8
1.8
2.6
3.2
4.8
CITESEER
2.4
5.8
2.9
2.4
4.6
PUBMED
5.9
8.9
7.4
14.5
7.3
CS OGBN-ARXIV
6.1
12.1
12.4
13.8
15.5
77.8
185.8
68.1
161.6
78.4
The mean training time presented in Table [5] indicating trade-off between the improved robustness provided by the GCORN model and its slightly longer training time compared to the GCN model and other available methods.
H MORE DETAILS ABOUT THE ESTIMATION OF OUR ROBUSTNESS MEASURE
We begin by providing the pseudocode of the algorithm used to estimate our robustness measure.
Algorithm 1: Estimation of Adu [f].
Inputs: Sphere Radius: e 0, Number of Samples Timas: Number of Input Graphs [D]; Initialize Adv 0; foreach [G, E D
Initialize Ado; 0:
foreach | 1, Lmaz do
1. Sample distance E [0, from the prior distribution (sec Appendix []
2. Uniformly sample Zi E Ba* from S, (see Appendix
3. Choose X = X, Ze:
4. Update
Ado; < Adv; + (ddy( (I, > a);
end foreach
Adv; Advs/ Adu:/Lmmai Limar' Adv Adv + Adv;;
end foreach
Return \d)
22

---

Published as a conference paper at ICLR 2024
We now detail how to uniformly sample from the set S, defined by,
2z D
max
12i1p== r)
18
where c). The set S, can also be defined in the following way,
Z E Sr 3 max
1
1siSn
Big E {I....,.)
n}
1p T 7 1
vi n
Since the position of io within {1, (I...., . n do matter in the previous equivalence, we can uniformly sample ig E . m). such that Tio 2 1p r and that the other index i E {I,..., nn \ { should satisfy r; = || r, r, i.e. Zi E B* (r) = { E ||| S r). We will use another time
Stratified Sampling where we start by sampling f within [0, r). Using the Lemma 5.1 directly sample (rsto from the probability distribution
we can
mu \ (oo), p(r:) K (#) K-1
vi (I.....,n)
Once we know the values of (rihis the problem boils down to sampling n vectors Isinnn from R.K. such that
Vi E ni,.
|| || ri.
(16)
For that, we have consider the cases p < oo and p oo
H.1 CASE WHERE 0o
In this case, Equation 16 can be written follows
Vi E (1.....m), | Vi (I....,,n)
Σ
Zi.j 1'
P.
[Z
P
+ aViE (1..,,...
n},
1.
(17)
J=1
To satisfy Equation 117.. , we randomly uniformly partition the 00, 1] into K parts. To do so, for each
i E {I,.... ..... n2. we randomly sample D 1 element from uniform distribution 2/(0, 1]; Let's denote
(8) (p) ....., P the sorted list of sampled elements. We directly choose
1
P
j = K
Olj
P)
if j= otherwise..
Pj
P
The matrix
satisfy
Vi E (1,
(1......))
n)
Σ
11
Figure gives insight into the previously introduced concept randomly partitioning in the case of the set (0, into K 4.
23

---

Published as a conference paper at ICLR 2024
P4
O4
Figure A toy example on how randomly partition the [0, 1] into 4 parts such as the sum
of the parts lengths is 1. We first uniformly sample 3 elements from [0, 1] and reorder them [Pt, P2, Ps]. And subsequently, we consider O [0. pı]. O₂ [p4. O₂ Ps]. O2 = [1,P4]
Based on the previous elements, we can choose Z such that
J.
OOg + Vi Z, = x 0
(18)
Equation 18 is invariant with respect to the sign of Zij hence, we use the following
Vi, Zi = Wijj r; 1/1pp
where Ms, is sampled from the discrete uniform distribution U1 11-1,1).
We recall that for p 1, the distance dd ([, (G, X max |[; X,Ilp defined in Equation| matches with the infinity matrix distance dx BA, + Σx X
|AX- BX as shown
in Nagisa 2022). Therefore, from the Theorem 4.1 the upper-bound the expected vulnerability Adu [f] is = I ( (000
H.2 CASE WHERE D0
In this case, Equation 16 can be written follows
Vi E (1....,nn n}. 1 + vi {1, .l........ n).
[z,
ISJSK 3j0 {1,....
K}
Zz.jo Ti. Zz.jo
+ Wi (I........ n]
(19)
Vj
K}
I ri.
For each (1....,n) n). we randomly select jo (l,.... K} to satisfy [Zr.jal = rs. For the other j * jo. uniformly sample the value of Zn,l from Uar These equations are invariant with respect to the sign of Zz,j, therefore, we choose,
Vi.j, Z unj [Zi
where Ui.y is sampled from the discrete uniform distribution M(-1,1).
PROOF OF LEMMA 5.1
Lemma. Let KR be the real funite-dimensional space and a positive real number. If (RP)) is the random variable indicating the maximum of the Ly norms values inside the ball of radius e, i.e. B. = {Z E Raak mmaxg((1.....) 1/ c} Then, for every p > O, the density distribution of R(P) does not depends p and is defined as follows,
(r(r) = K (5) 1 1005rsd.
Proof. Using the following equivalence
32 E R max Isiin
| 3T E
|
We deduce that the density Pe do not depend on n, and therefore set 1 for this proof. Therefore,
B, Zz E R |イ
24

---

Published as a conference paper at ICLR 2024
We start by calculating the volume of the K K-sphere of radius for any real miite-dimensional space RK where K > 2 an integer.
8 S*((r = for RR [ r..
Let's denote the volume of (*((r) Using Fubini Theorem, we have
(r) by (r).
[" yk- -1=1)>))))100) dx
(k)
VK-1 (r(1 - -1011) dr
p - (11 /sp)))/P)) de
Kk [ Dk-1 (1-1z|)))/1) de
(20)
Thus, the surface L ball in R of radius r is
sk(r)) dv* (r)
(21)
dr Kr (1).
(22)
Consequently the density distribution of (()) could be written as
(r(r) = (x(rr (c)
110 Se
(rk 1 110 S sc)
(c) dr
K-1
105rset
(23)
We note that the previous quantity doesn" 't depend on p.
J ADDITIONAL RESULTS
J.1 NODE CLASSIFICATION
To further understand the relationship between robustness and input sensitivity, from which we derived the upper bound for GNNs and specifically GCNs, we empirically validate the trade-off between robustness and input perturbation. We hence compare the difference in the output of each model when subjected to random perturbations with varying attack budgets. The results of this study are presented in Figure 3 The figure displays the results for both Cora and CiteSeer datasets in both absolute (left figure) and log-scale (right figure) format. The results demonstrate that the GCN is highly sensitive to perturbations in comparison to the proposed approach in terms of the difference in output. These findings provide validation for the stability of GCORN against input perturbations, and by extension, adversarial attacks.
We additionally considered two defense techniques benchmarks: (1) ElasticGNN (Liu et al. 202 which proposes novel and general message passing scheme into GNNs to enhance the local smoothness adaptivity of GNNs via baased graph smoothing and (2) EvenNet (Lei et al. 2022) which proposes spectral GNN corresponding to even polynomial graph filter with the main idea being that ignoring odd-hop neighbors improves the underlying robustness. For this additional evaluation, consider similar attacks techniques as the one from Table
25

---

Published as a conference paper at ICLR 2024
Results on Cora
GCM ccoRs
OCt
1 XI -(A..x+
Lopccale 14A
66
14
64 Perturbation scale
Perturbation
Results on CiteSear
OCN ocoms
COOMN
[dlA.x) XI xl)
100
Lopccale (8AAX)
15
Perturbation scale
Perturbation scale
Figure 3: Difference (in average and standard deviation) in output for the GCN and our GCORN when subject to random perturbations with different attack budgets for both (a) Cora and (b) CiteSeer. The right-hand side plots are on the log-scale.
Table 6: Attacked classification accuracy (# standard deviation) of the models different benchmark node classification dataset after the attack application.
Attack
Dataset
ElasticGNN
EvenNet
GCORN
Cora
72.5 + 2.4
69.7 + 1.8
77.1 1.8
Random
CiteSeer
58.9 + 2.3
48.6 + 1.6
67.8 1.4
(*) 0.5)
PubMed
70.5 0.6
68.8 = 1.6
73.1
Cora
5..4
57.6 2.1
Random (v) 0.5)
CiteSeer
43.8
39.7
57.3 1.7
PubMed
56.8 2.1
58.5
65.8 + 1.4
Cora
64.7 1.6
57.6
71.1
PGD
CiteSeer
50.8 3.2
37.1 3.3
65.6 1.4
PubMed
64.6 1.5
61.0 4.1
72.3 + 1.3
J.2 GRAPH CLASSIFICATION
In this section, we present the result of our GCORN the graph classification task using both empirical and our proposed probabilistic evaluation. Details about the experimental setting for this task provided in Appendix L Note that for the random attack, used 0.5 and for the gradient- based, we used a budget 0.2. Trepors the average accuracy and the corresponding standard deviation for both clean and attacked accuracy.
26

---

Published as a conference paper at ICLR 2024
Table Classification accuracy (# standard deviation) of the models on different benchmark graph classification dataset before (clean) and after the attack. The higher the accuracy (in %) the better.
PROTEINS
D&D
NCI1
Attack
GCN
GCORN
GCN
GCORN
GCN
GCORN
Clean
73.4 + 2.8
74.1 1.9
3.6
7..4
15.7
74.8 + 1.7
Random
66.7 + 2.5
7..7
7.29
7..1
6..1
2.1
PGD
56.7 + 2.8
6.14
61.8 4.1
68.6
62.4 5.
K
EXPERIMENTAL RESULTS ON GIN
To showcase our method's versatility beyond the considered GCN framework and confirm the GIN- related results outlined in Theorem 4.3 we conducted similar experiments to those presented in Table I However, this time, we employed GIN as the pressage-passingg scheme. In this perspective, we used the same previously considered node features attacks, notably: (i) The baseline random attack injecting Gaussian noise (0, I) to the features with scaling parameter controlling the attack budget; (ii) The white-box Proximal Gradient Descent (Xu et al. 2019a), which is gradient-bases approach to the adversarial optimization task with a chosen attack budget of 15%.
Table 8: Attacked classification accuracy (# standard deviation) of the models on different benchmark node classification dataset using Graph Isomorphism Network after the attack application.
Model
Cora
CiteSeer
PubMed
GIN
67.8 + 1.3
50.1
+ 0.3
72.8 + 0.4
Random (+) = 0.5)
GIORN
71.8 0.8
60.8 0.5
74.3 + 0.7
GIN
54.5 = 0.9
45.1 + 0.4
67.3 = 0.6
Random (v) = 1.0)
GIORN
66.7 = 1.2
54.4 + 0.8
68.9 = 1.1
GIN
61.4 1.4
44.1 14.100.5
70.6 = 0.4
PGD
GIORN
69.5 = 0.6
58.3 + 0.6
73.1 = 1.6
L DATASETS AND IMPLEMENTATION DETAILS
For all the used models, the same number of layers, hyperparameters, and activation functions were used. The models were trained using the cross-entropy loss function with the Adam optimizer, the number of epochs and learning rate were kept similar for the different approaches across all experiments.
L.1 NODE CLASSIFICATION
Characteristics and information about the datasets utilized the node classification part of the study are presented in Table I0 As outlined in the main paper, we conduct experiments on set of citation networks, including Cora, CiteSeer, and PubMed (Sen et al. 20088), as well as the Amazon Co-author network of authors from the Computer Science (CS) domain (Shchur et al. 2018). For Cora, SiteSeer, and PubMed, we adhere to the hiii//alid/test splits provided by the datasets. For the CS dataset, we adopt the same methodology as used in Yang et al. (2016). by randomly selecting 20 nodes from each class to form the training set and 500/1 0000 nodes from the remaining for the validation and test sets.
In all of the experiments, the models employed a 2-layer convolutional architecture (consisting of two iterations of message passing and updating) stacked with Multi-Layer Perception (MLP) as a readout. The intent was to compare the models in an iso-architectural setting, to ensure a fair evaluation of their robustness. All experiments were conducted using the Adam optimizer (Kingma Ba 2015) and the same hyperparameters, including a learning rate le-2, 300 epochs, and a hidden feature dimension of 16. For the OGB dataset, used 512 hidden feature dimension. To account for the impact of random initialization, each experiment was repeated 10 times, and the mean and standard deviation of the results were reported. We finally note that for the AIRGNN,
27

---

Published as a conference paper at ICLR 2024
Table 9: Statistics of the node classification datasets used in our experiments.
DATASET
#FEATURES
#NoDES
#EDGES
#CLASSES
CORA
1433
2708
5208
CITESEER
3703
3327
4552
PUBMED
500
19717
44338
CS
6805
18333
81894
15
OGBN-ARNE ARXIV
128
31971
71669
Table 10: Statistics of the graph classification datasets used our experiments.
DATASET
#GRAPHS
#NODES
#EDGES
#CLASSES
1178
284.32
715.66
NCTI
4110
29.87
32.30
PROTEINS
1113
39.06
72.82
2
set = 2 so as to have the same number propagation as the other benchmarks. For our proposed GCORN, tuned the iteration numbers for the different datasets and this was also done for the Parseval Regularization (ParselR) to find the best regularization parameter.
L.2 GRAPH CLASSIFICATION
We additionally emperically evaluated our proposed method GCORN using both probabilistic eval- uation and the classical experimental evaluation. We used benchmark datasets derived from bioin- formatics and chemoinformatics (PROTEINS, NCT1, D&D) (Morris et al.) 2020). The framework proposed by |Errica al. (2020) used to evaluate the performance of the models this task. We therefore performed a 10-fold cross-validation using the same folds as provided by the paper to obtain an estimate of the generalization performance of each method.
Similar to node classification, we employed a 2-layer convolutional architecture (consisting of two iterations of message passing and updating) stacked with a Multi-Layer Perception (MLP) as readout using the Adam Optimizer.
L.3 IMPLEMENTATION DETAILS
Our implementation is available in the supplementary materials (and will be publicly available afterwards). built using the open-source library PyTorch Geometric (PyG) under the MIT license (Fey & Lenssen| 2019). We leveraged the publicly available implementation of the different benchmarks from their available repositories From GCN-k for AIRGNN ? for GNNGuard and for RGCN we used the implementation from the DeepRobust package. Note that we additionally utilized the PyTorch ReepRobust packagd" to implement the adversarial attacks used in this study. The experiments have been both NVIDIA A100 GPU and RTX A6000 GPU.
L.4 IMPLEMENTATION DETAILS OF OUR EMPIRICAL ROBUSTNESS ESTIMATION
We considered the input distance defined in Equation with p 2, we fixed the radius 10 and the number of sampling per graph at Lmaa = 100. For each graph G, the output distance dy has been re-scaled the interval [0, by normalization using factor of 2 /Ng where Ne the number of nodes in the graph G (See Appendix M)
"http:://githubb.. http:///gghttttooooo/////o/////a
"https//github..c hhtpss//gitub..oo/miinse http://hwww.cccmmmmmmmm/a/a////a hhapss//gghhb..ooDDDsss/////e//p
28

---

Published as a conference paper at ICLR 2024
M RESULTS OF THE EMPIRICAL ESTIMATION OF OUR ROBUSTNESS MEASURE
M.I NORMALIZATION OF THE OUTPUT DISTANCE dy
The distance dy is defined as follows,
= =1(((, f(G,
Let's put Q = (Qi,)o = - - -(G, X), where Na is the number of nodes in the OSiSC
graph and C the number of classes, i.e. output dimension. Since, the last layer of f is a Sigmoid function, all the element of the matrix f(G.X) and f(G, are bounded between and thus, Vi [Qa,1 S IIS II1G, x)lls 2, i.e. [l S Therefore, we have
||$||2
|| S
sup x=
||0||2
2) 1/2
Σ No
Σ
(Er- Qis
sup
|
1/2
No
[ 2 Tzj)
Li=1
< o|
||01|2
2
5 j=
B3
= ||Q1
No sup ax$0
| |x|12
| |
||Q1l / NG sup 2/0
11Qlloo < 2 2/ No.
Thus,
0 2/NG &IG $
M.2 THE EFFECT OF SAMPLING ON THE EMPIRICAL ESTIMATION OF Ad)
The provided robustness evaluation is based estimation related to sampling strategy. Con- sequently, the quality of our evaluation is dependent on the number of generated samples. In what follows we aim shed light on the effect of the chosen number of samples on our estimation.
Previous work (Niederreiter) 1992 Tezuka 2012) has proven the intricate link between the discrep- ancy of samples and the estimation errors. Discrepancy, particularly in the context of quasi-Monte Carlo methods, assesses how effectively a set of points covers a given space. A high discrepancy signifies the presence of volumes with varying point densities-som some with high density and others with low density. Conversely, low discrepancy indicates a more uniform distribution of points, resulting in smaller estimation errors for Ado [f]
We use this concept to understand the possible variation of our estimation within our considered input this perspective, we measure the discrepancy by computing the probability to find ball of radius <<<<< e, included in B, = { E R ||] | < e). which does not contain any of the Lmoz samples [Z,.... ,4....,ZZmea. Zimar.. We denote by B, the set of balls of radius r, i.c. we have:
graph's 's neighborhood.
B B, RRE B Z E R 2 T4p e).
29

---

Published as a conference paper at ICLR 2024
For any B B, such that B C Be, the probability that none of the Lmar samples belongs to B is
Umaz
P(Vi fl..... Lmar). J. Z, B)
II P(Z, $ B})
= 1 & B
(1 P(Zz E B)) Timax
VK (x(r)
Lmax
VR (E)
T.max
To reach a low discrepancy, we need to reduce the aforementioned probability, i.e. upper-bounding the probability P(Vi E (man..,Lmma, } Zi $ B) with a small within J0, 1], e.g. a 0.05.
P(vi f1....; Imar]; }, Z B) sa (1 (1-
(2) K
Lmax
Sa
(24)
Lmaalog (1
(2)
S log(a)
(25)
log(a)
+ Lima
(26)
log 11-(2 K
Therefore, to reach low discrepancy and hence reduce the estimation error, Equation 26 provides theoretical guarantee for the minimum required number of samples. The given lower-bound is an increasing function respect to e, thus, we may need fewer samples if we consider a smaller input graph's neighborhood.
We also empirically investigate how the robustness measure Adv varies due to sampling. To do for fixed number of samples, empirically estimate Adva. 10 different times using the Algorithm We report the mean and the standard deviation of Adu [f] for each fixed number of samples. As noticed for the dataset Cora, have consistent estimation of Ado [f] with different number of samples. Morcover, the variance becomes almost constant with only 40 samples. Thus, with only few number of samples, can statistically significant estimation of Adug. [
Cora
60
G2ORP
25-
Adv(f) (In
15-
30
20
40
80
103
123
340
Number of Samples
Figure 4: The Values of Ad [f] for the dataset Cora. The dotted line and the shaded region represent respectively the mean value and the standard deviation Adv
M.3 EMPIRICAL. VALIDATION OF THE TIGHTNESS OF THE COMPUTED THEORETICAL. UPPER-BOUND
In this section, we study the tightness of the theoretical upper-bound y IT = |[(]] -o cua/o of Theorem 4.1 For that, we use empirical estimation of Adu using Algorithm [
We calculated both its theoretical upper-bound and the estimated robustness evaluation for different values of a. The results provided in Figure As shown in Appendix M.I the maximum
30

---

Published as a conference paper at ICLR 2024
possible value of a is 2/Nc. thus, plot the values of [f] and the upper-bound " function of a (22NGa) Notably, these experimental findings affirm the tightness of the theoretically computed bound. This tightness explains our considered link between reducing the upper-bound and the robustness enhancement experimentally seen in Table 1 and 2
Cora
AdX11
Prooecical Bound
0.
0.6
Values in
0.2
Figure 5: The Values of [f and the theoretical upper-bound y (c.f. Theorem 4.1 for the dataset Cora using different values of a. For this experiment, we used the values e 0.1 and Timaz 100.
M.4 ADDITIONAL RESULTS OF THE EMPIRICAL ESTIMATION FOR THE NODES CLASSIFICATION TASK
In Figure we report the values of Adv of our GCORN and the baselines for the datasets CiteSeer, Pub\eed and CS. We used the same setting previously described in Section For the dataset CiteSeer and PubMed, we notice that GCORN method yielded the lowest Adversarial Robustness value, indicating that GCORN exhibits greater robustness against adversarial examples.
CiteSeer
PubMed
10
GCORW
8R21
1,5
GCN
ARRW
GCN-K
Advif]
0.6
Adv[[]
0.5
02
0.2
SCORY
RGOH AIRIGIN
SCV
0.0
0.1
02
CS
1.0
OCORN
0.5
Adv(f)
6.0
0.0
Figure 6: The Values of ( for the dataset CiteSeer, PubMed and CS.
31

---

Published as a conference paper at ICLR 2024
M.5 ADDITIONAL RESULTS OF THE EMPIRICAL ESTIMATION FOR THE GRAPHS CLASSIFICATION TASK
In Figures 7 report the values of Adv for the datasets DD, NCI and Proteins. We observe that GCORN and the two other baselines exhibit nearly identical values of Ad Adv [.].
DD
NC11
SCORY
-
1.2
GCORN
GCN
GCV
GCV
0.8
Adv(f]
Adv[f]
0.2
2.0
0.2
0.5
0.6
0.0
0.1
02
5.3
0.4
3.5
PROTEINS
1.0
6ONM GCI
Adv(f]
0.6
0.2
0.0
Figure 7: The Values of ( for the dataset CiteSeer, PubMed and CS.
32


Reviews:
[{"review_id": "7ozD7CfagG", "reviewer": "Reviewer_gkkc", "summary": "In this paper, authors have provided theoretical as well as empirical study of vulnerability of GNNs to adversarial attacks. The concept of \"Expected Adversarial Robustness\" for GNNs is introduced and studied in relation to conventional adversarial robustness. An upper bound of this robustness concept is derived and proved for the networks which is independent of the model or attack. Based on these results, GCORN is introduced which is a training method to improve robustness of graph networks by controlling the norm of weight matrices, encouraging their orthonormality. Empirical analysis is conducted to illustrate the effectiveness of GCORN in comparison to other defense baselines.", "questions": "see weaknesses", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "**Originality**: This work introduces and studies the concept of expected robustness of graph networks and sounds very novel. Not only strong theoretical foundation is provided, methods are proposed to empirically calculate the robustness. Furthermore based on findings, a novel method to improve robustness is introduced. The theoretical and empirical claims speak to the novelty of the work.\n\n**Quality**: The paper is characterized by its rigorous theoretical exploration and empirical analysis, which collectively elevate its overall quality. The experimental results strongly support the theoretical claims.\n\n**Clarity**: The concepts in the paper are clear and well organized. The narrative flow keeps the reader engaging and this clarity in presentation makes the complex subject matter accessible and comprehensible.\n\n**Significance**: I think this work provides significant insights to the robustness of GNNs and will be useful for the research community. The GCORN method is effective, has good theoretical foundation and adds a new benchmark for training robust GNNs.", "weaknesses": "A few typos:\nSection 4.3 encourages -> encourage\nAlgorithm 1: Second for loop line# 3 $X +Z$ should be $X_i + Z_i$?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GBDUvwuBmA", "reviewer": "Reviewer_dcsE", "summary": "In this paper ,the authors theoretically define the concept of expected robustness to evaluate the robustness of GNNs, extending beyond the traditional \"worst-case\" adversarial robustness, and derive an upper bound of the expected robustness of GCNs and GINs. They propose a modification to the GCN architecture called the Graph Convolutional Orthogonal Robust Network (GCORN) that aims to improve robustness against node feature perturbations by promoting the orthogonality of weight matrices, effectively controlling the norm of these matrices to mitigate the impact of such attacks. The authors employ an iterative orthogonalization process that also benefits learning convergence by mitigating vanishing and exploding gradients. They ensure that the complexity of their approach remains manageable and does not excessively increase with larger graph sizes. Furthermore, they develop a probabilistic and model-agnostic method for empirical evaluation of GNN robustness. Unlike existing metrics, this proposed method applies to a variety of attack types and does not require the knowledge of specific attack schemes. They present experimental results to demonstrate the superior robustness of GCORN compared to baseline models, using various real-world datasets. The findings suggest that GCORN is a promising modification to enhance GNNs' robustness to adversarial feature perturbations without significant trade-offs in performance.", "questions": "1. How to determine the number of samples required to obtain an accurate empirical estimation of the robustness? Is there a theoretical guarantee (such as a bound on the estimation error with high probability) that the estimated value is close enough to the true expected robustness?\n2. A comparison between the theoretical upper bound of the expected robustness and its empirical estimates should be provided in order to show how closely the empirical results align with the theoretical bound and the effectiveness of the theoretical bound.\n3. It is encouraged to include experiments with more sophisticated adversarial models and comparisons with other defense methods.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Originality: The paper introduces a new theoretical framework for defining and quantifying the concept of \"Expected Adversarial Robustness\" for GNNs, which is a deviation from the traditional worst-case scenario evaluation that dominates the field. Their GCORN model demonstrates an innovative approach to mitigating the impact of adversarial attacks on GNNs by leveraging the orthogonality of weight matrices, a concept that has not been extensively explored in the context of GNNs. The development of a model-agnostic, probabilistic method for evaluating GNN robustness is a creative combination of existing ideas that significantly enhances the security assessment of graph models against a wider range of adversarial strategies.\nQuality: The quality of the paper is high as it thoroughly examines the proposed concepts from both theoretical and empirical perspectives. It provides a rigorous mathematical formulation of the problem and strong theoretical foundations for the methods proposed.\nClarity: The paper is well-written and organized in a manner that strategically guides the reader through both the theoretical and practical aspects of the work. Definitions and theoretical findings are clearly presented and sufficiently detailed, making them accessible to readers with a foundational understanding of the domain. \nSignificance: The Expected Adversarial Robustness framework gives practitioners a more nuanced understanding of model vulnerability in realistic scenarios beyond the worst-case adversarial examples.\nIn summary, the paper showcases original conceptual developments, high-quality theoretical work, clarity in its exposition, and significant contributions to the field of graph representation learning, particularly addressing adversarial robustness in GNNs.", "weaknesses": "While the paper presents significant contributions to the stability and robustness of GNNs against feature-based adversarial attacks, there are certain areas where it could potentially be improved to reinforce its claims and widen its applicability:\n1. Computational Cost: The estimation of a GNN’s expected robustness involves a sampling-based approach, which indeed can be computationally intensive as it requires generating and evaluating numerous perturbed versions of the input graph, especially when it comes to large datasets.\n2. The robustness measure might vary significantly with each estimation due to sampling, leading to inconsistency and making it difficult to compare with other models.\n3. The paper lacks the comparison between the theoretical upper bound of the expected robustness and its empirical estimates. The authors have provided a theoretical upper bound for the expected adversarial robustness of GNNs and introduced an empirical method to estimate this robustness; however, the paper does not explicitly show how closely the empirical results align with the theoretical bound.\n4. Attack Models and Benchmarks: It appears that the attack models used to evaluate robustness are largely selected from existing and potentially well-known strategies. Exploration of the effectiveness of GCORN against emerging or more sophisticated adversarial models could further substantiate the claimed robustness. Furthermore, including newer or well developed defense mechanisms would be advantageous for our understanding of GCORN’s effectiveness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vDZgu0Ilf5", "reviewer": "Reviewer_B7fh", "summary": "The paper proposes a new formalization of the notion of expected robustness for GNN and introduce some theoretical guarantees on this quantity. It also uses the insights coming from the bound in the case of GCN to propose a robust alterntive under the form of GCORN. The paper also validates the relevance of their approach empirically.", "questions": "* Do you have some table summarizing the tightness of the bound in the experiments you ran ?\n* You focus mainly on the cases where alpha, beta=(0,1) or (1,0). Do you have some insights on the more general case of mixed attacks (structural and feature based) ? Are some results holding in that case ? (combination of 4.1 and 4.2 ?)", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "* The paper is well structured and easy to read\n* The paper proposes a clear and general framework for adversarial robustness on graphs\n* The paper derives some theoretical bounds for expected adversarial robustness and leverage this formulation to propose some simple but efficient improvement based on orthonormalisation with the GCORN model\n* In the case of MPNN, the paper provides both bounds for node features attacks and structural attack\n* It also validates that his approach work in practice", "weaknesses": "* The paper considers only a few attacks to validate his approach. Even if these attacks makes sense (PGD / Nettack are good standards for this type of tests), it would have been interesting to try additional ones.\n* The gain of robustness of GCORN over GCN is interesting but it's not clear how it compares to other defense methods (for instance is GCORN w adversarial training still better than GCN with adversarial training)\n* It is unclear to me how tight is the bound from theorem 4.1/4.2 ; this part could be stated more clearly in the experiment section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BLdtULE5SS", "reviewer": "Reviewer_nkA1", "summary": "This paper studies the robustness of GNNs under adversarial attacks to node features in attributed graphs. The authors establish the upper bound for the expected robustness of GCNs under the node feature perturbations, and generalize to GIN as well as structural attacks. The bound also motivates a solution called Graph Convolutional Orthogonal Robust Networks (GCORNS), that adopts  orthogonal projections of the weight matrices of GNNs to reduce the upper bound (and to improve the robustness). Moreover, the authors also propose an estimation method of the proposed robustness measure. Then they conduct experiments to demonstrate the improved robustness of GCORN method.", "questions": "1. The scope seems to be too limited:\na. If the scope is as claimed as focusing on adversarial attacks on node features, what are the practical scenarios? Are there any realistic cases for the studied attack?\n\nb. As already been shown by the authors, there is a natural connection between structural attacks and the attribute attacks, why not study the more general attacks? \n\nc. The work also neglects a rich literature in the line of graph injection attack, where the adversary will inject new nodes and optimize the injected nodes’ features to perform the attack [1,2,3,4]. It is also worth discussing the connections of the proposed robustness measure with respect to injection attacks, as well as the recently emerging backdoor attacks [5,6].\n\n2. There are already multiple new robustness measures proposed [3,7] which have not been discussed in the paper.\n\n3. Some baselines have not been compared with, including [8,9,10]. Can GCORNS outperform them? \n\nb. Besides, why table 1 and table 2 adopt different baselines? \n\nc. Can a heuristic solution like weight decay achieve the same functionality as GCORNS?\n\nd. Can GCORNS be incorporated to more GNN backbones other than GCN?\n\ne. Would GCORNS work for large graphs?\n\n4. The improvements seem to be limited when with slightly more powerful attacks. For example, in Table 1, with Nettack, GCORN underperform AirGNN in ogbg-arxiv, and RGCN in PubMed. In Table 2, with structural attacks, GCORN underperform previous methods in even more cases.\n\n\n**References**\n\n[1] TDGIA: Effective Injection Attacks on Graph Neural Networks, KDD’21.\n\n[2] Single Node Injection Attack against Graph Neural Networks, CIKM’21.\n\n[3] Understanding and Improving Graph Injection Attack by Promoting Unnoticeability, ICLR’22.\n\n[4] Let Graph be the Go Board: Gradient-free Node Injection Attack for Graph Neural Networks via Reinforcement Learning, AAAI’23.\n\n[5] Unnoticeable Backdoor Attacks on Graph Neural Networks, WWW’23.\n\n[6] On Strengthening and Defending Graph Reconstruction Attack with Markov Chain Approximation, ICML’23.\n\n[7] Revisiting Robustness in Graph Machine Learning, NeurIPS’22.\n\n[8] Graph Structure Learning for Robust Graph Neural Networks, KDD’20.\n\n[9] Elastic graph neural networks, ICML’21. \n\n[10] EvenNet: Ignoring Odd-Hop Neighbors Improves Robustness of Graph Neural Networks, NeurIPS’22.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The proposed robustness measure is new;\n\n- The proposed method is somehow interesting;\n\n- The presentation and organization are clear;", "weaknesses": "(-) The scope seems to be limited;\n\n(-) Some baselines have not been compared with.\n\n(-) The improvements seem to be incremental and limited;", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)