Bounding the Expected Robustness of Graph Neural Networks Subject to Node Feature Attacks

[Q8] Incorporating GCORN to other GNN backbones other than GCN: Although our primary focus is centered on the GCN model, we know that our approach can be extended to various GNN architectures and we have indeed outlined theoretical insights and guidelines in Appendix E aiming to generalize our theoretical investigation to diverse message-passing models. Moreover, in the original manuscript, we established the theoretical upper-bound for GIN (Theorem 4.3) and we additionally supplement this theoretical analysis with an experimental analysis that shows similar enhancement for the GIN as the one witness for the GCN model as shown by the following table. Note that we added this table to the revised manuscript (Table 8 - Appendix K). Table 3: Performance of our proposed method GIORN and GIN when using a GIN backbone when subject to both features adversarial attacks.

[Q9] Would GCORN work for large graphs? This is indeed an important point which we tried to address in Section 4.3 (“Complexity of our method”). We note that the complexity introduced by the modification we make in our method is independent of the input graph’s size since our method is mainly concerned with the weight projection into the orthogonal manifold, depending therefore on the size of the hidden dimension (which is very small for the majority of dataset - 16 for Cora for instance). Hence, the complexity of the GCORN and GCN grow equally as the graph size grows. This is not the case of the majority of available defense benchmarks where for instance the closely performant method to ours in structural perturbations which is GNNGuard has a complexity increasing with the input graph. Consequently, our method GCORN scales more gracefully to large graphs than available techniques. We note that we additionally provided complimentary time/complexity analysis in Appendix G.

[Q10] On the limited performance improvement over other baselines in certain cases. Firstly, we want to highlight that the primary strength of our paper lies in its theoretical analysis and guarantees, aspects notably absent in most of the benchmarks considered. These facets underscore the potential effectiveness of our approach against future, more sophisticated attacks. Our experimental evaluation shows that, in the majority of the cases, our method outperforms all benchmarks (which are considered state-of-the art defenses) across various scenarios—node features, structural, and mixed attacks. In the cases where one of the several high-performing benchmarks displays better results than our GCORN method, the two methods are often within the range of standard deviation of each other. Regarding Nettack in particular, it is crucial to note that Nettack is a targeted attack. Consequently, the evaluation focused on a limited number of nodes (40 in this instance, as per the original work). Therefore, we expect the observed enhancement gap not be substantial, which differs from other considered attacks that approach the attack aim from a global perspective attacking all the nodes (and in which the observed performance gap is important). Finally, using our robustness estimation (based on our robustness formulation) in Figure 1 (a) & (b), we can see the real robustness gap between our proposed GCORN and the other benchmarks, which is rather related to the method itself and not the considered attack (since we evaluate the whole input graph’s neighborhood).

[Q4] Regarding other robustness measure [3, 7]: We have added these references in our related work section. These two works are more interested in the structural aspect of the attacks where they consider the possible semantic content change in the adversarial graphs. While we agree that considering these evaluations is important, we also note that in addition to our proposed robustness evaluation we have considered the robustness evaluation provided by [1] (Figure 1.c) which allows us to consider both structural and node features based on robustness estimation.

[1] A. Bojchevski et Al. - Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and More, ICML 2020.

[Q5] Comparing GCORN to the provided baselines [8, 9, 10]: We thank the reviewer for pointing out these references, we have added experiments related to several of these models in the updated manuscript (Table 6 - Section J in the Appendix) and we list them also in this response. We note that the reference EvenNet work is very interesting and very relevant to our perspective, where it shows that actually ignoring some “odd-hop neighbors” improves the robustness. This is directly related to the second part of our computed bound (related to the normalized walks over the input graph). So while we have focused on the first part of the bound (related to the norm weights), this work seems to directly prove our second part of the bound. We finally would like to point out that our method is attack-agnostic since our theoretical design and analysis is considering the input graph’s whole neighborhood.

Table 2: Performance of GCORN, ElasticGNN and EvenNet when subject to node-features adversarial Attacks.

[Q6] On the difference between adopted baselines in Table 1 & 2: We apologize for any potential confusion. Table 1 focuses on node feature-based adversarial attacks (to validate the results of Theorem 4.1), whereas Table 2 addresses structural perturbations (related to Theorem 4.2). Consequently, our choice was to align each defense benchmark with the corresponding specific attack that it aims to defend. Using defense benchmarks with attack types beyond their original score resulted in poor performance and is therefore a penalization to these methods compromising the validity of our evaluation.

[Q7] On possible use of heuristic solution like weight decay: Based on the computed upper-bound (Theorem 4.1 & 4.2), weight decay which consists of adding a penalization term to regularize the weights can indeed be a solution to tighten the upper-bound resulting in an enhanced robustness. This is similar to what has been proposed by the benchmark Parseval Network (ParsevalR). While we have not explicitly considered weight decay, from the experimental results on ParsevalR and the use of some regularization techniques, we have seen that the related constraints to these methods usually deeply affects the model’s clean accuracy. And since apriori, we don’t know if the input graph is attacked or not, seeking a good balance between robustness and clean accuracy is crucial, hence the choice of our projection technique.

We thank the reviewer for his comments and question that helped improve the quality of our manuscript. In what follows, we address the raised questions and weaknesses point-by-point.

[Q1] On the limitation of the considered scope and application of node features attacks: We disagree with the reviewer on the fact that focussing on node features attacks is too limiting. We start by noting that while adversarial attacks may be deliberately crafted by a user, understanding and defending them also sheds light on how to interact with abnormal node features which are frequent in real-world datasets. Regarding the possible applications, we can consider social networks, in which a user can choose to edit/add their profile information (which for the more widely used social networks is easier than adding/deleting connections corresponding to the structural perturbation case) in order to get recommended to all the users (which is an edge-prediction task) or escape scam detection (which is a node classification task). Similarly, a company can enter/fake its product information in a marketplace such as to get shown to all the potential users using the underlying recommender system (which is an edge prediction task) or be listed in the wrong category (which is a node classification task). A more global and important perspective lies within the cybersecurity industry, where we often consider a network in which each node represents a computer/user with the edges representing the probability of observing the connection between the nodes. In order to enhance the modeling, additional node features are added such as the number of bytes exchanged, user credentials, number of connections with other users, which are externally controlled parameters. The goal in cyber-security is to estimate how rare these connections are, consequently ensuring the viability of the connection. In this context data poisoning attacks are common. In these attacks a user simply edits node features (where for instance a user will deliberately edit certain aspects of their credentials) to fool our security firewall/classifier.

[Q2] Regarding the general case of attacking the structure and node features: We apologize if we didn’t specify this enough in the original manuscript but we have actually provided a theoretical analysis on the general attack where the structure and node features are both attacked in parallel (Appendix F). We note that we have furthermore added some experiments (Table 3 - Appendix F) where our models outperforms the other benchmarks when dealing with both the attacks (Mettack & Random) in parallel. We thank the reviewer for pointing this out.

Table 1: Performance of GCORN and defense benchmarks when subject to both structural and node features adversarial attacks in parallel.

[Q3] Regarding graph injection attack techniques: We appreciate the reviewer's valuable input, and we have incorporated the references and the discussion into the related work section of the revised manuscript. The concept of "node injection attacks" indeed presents an intriguing perspective on adversarial techniques. Our current study predominantly explores "classical" attacks and our theoretical analysis is dependent on the introduced graph distance. In the context of node injection attacks, a new graph distance should be introduced/adapted to measure the similarity between graphs (with different number of nodes - giving the injection) and the concept of input’s neighborhood should also be revisited. This adaptation indeed is an exciting avenue for extending our work.

We thank the reviewer for their strong support recognizing the novelty and application of our work. We additionally are grateful for their comments and questions that we aim to address point-by-point in what follows.

[Q1 & W3] On the tightness of the provided and computed upper-bound: We agree that this was missing from our original manuscript. The focus of our work is to derive an upper-bound, which when tightened allows us to propose a model with enhanced inherent robustness. Regarding the tightness of the bound, we have experimentally studied this quantity by computing the theoretical upper-bound together with our estimation of the expected adversarial robustness for the Cora dataset. We provided the results in the updated manuscript in Figure 5 in Appendix M.3. While we observe the bound to not be tight, we see that it is relatively close to the empirically estimated robustness. The fact that the theoretical bound and the estimated expected robustness are meaningfully close, is further substantiated by the fact that reducing the upper-bound allowed us to improve model robustness in the experiments shown in Tables 1 and 2.

[Q2 & W1] Insights on the more general case of mixed attacks (combining Structural and node feature attacks): In fact in Appendix F of our original submission we provided a theoretical analysis (in form of a bound on the expected robustness) for the case in which both the structure and the node features are attacked concurrently ($\beta = (1,1)$). We additionally added experiments to compare the behavior of our proposed GCORN and other defense benchmarks when dealing with the mixed attacks (Mettack & Random) in parallel illustrating our theoretical analysis. Table 1 is providing these results and they have been also added to the revised manuscript (Table 3 - Appendix F). We thank the reviewer for pointing this out.

Table 1: Performance of GCORN and defense benchmarks when subject to both structural and node features adversarial attacks in parallel.

We thank the reviewer for their thoughtful comments, which have allowed us to improve the quality of our manuscript and to post a revised version. We are glad they identified the originality and applicability of our proposed approach. In what follows, we address the raised questions and weaknesses point-by-point.

[W1] Regarding the computational cost: As discussed in Section 5, Appendix H and I, the computational cost of estimating a GNN’s expected robustness equals the time of firstly, sampling perturbed attributed graphs and secondly, running inference of the studied GNN on the perturbed graphs (potentially in parallel or in batches). Firstly, we sample perturbed attributed graphs by sampling from uniform distributions, which has a complexity of O(1). Secondly, the complexity of performing inference of a GNN on several graphs depends on the chosen GNN, for the GCN for example the inference complexity is linear in the number of edges in the perturbed graphs.

With regards to step 1 of our evaluation procedure, existing evaluation approaches often evaluate model accuracy by injecting Gaussian noise [5], the generation of which is of, e.g., $O((nK)^3)$ for $n$ $K$-dimensional samples drawn when using the method relying on the Cholesky decomposition [1]. Now concerning step 2 of our evaluation procedure, using the GNN for inference several times is required for the large majority of traditional robustness evaluations, e.g. in the Project Gradient Descent (PGD) algorithm [2], we have to perform an inference at each iteration of the algorithm. Furthermore, each iteration involves computing the gradient and updating the input. The number of iterations needed for convergence in the PGD method can be high, leading to increased computational cost [3,4]. Consequently, our proposed expected robustness metric has a lower computational cost than the PGD metric.

We therefore reckon the computational cost of our estimation procedure to be limited and certainly lower than most existing robustness evaluation approaches.

[1] T. Muschinski, G. Mayr, T. Simon, N. Umlauf & A. Zeileis - Cholesky-based multivariate Gaussian regression, Econometrics and Statistics 2022.

[2] K. Xu, H. Chen & Al. - Topology attack and defense for graph neural networks: An optimization perspective, IJCAI 2019.

[3] J. Tian, Y. Liu, J. Smith, Z. Kira - Fast Trainable Projection for Robust Fine-Tuning, NeurIPS 2023

[4] J. Tian, X. Dai, C. Ma, Z. He, Y. Liu Z. Kira - Trainable Projected Gradient Method for Robust Fine-tuning, CVPR 2023.

[5] B. Li, C. Chen, W. Wang, L. Carin - Certified Adversarial Robustness with Additive Noise - NeurIPS 2019

[Q1 & W2] On the effect of number of samples on the robustness estimation: We agree with the reviewer that analyzing the effect of the number of samples on the variance of our robustness estimation is interesting. In response, we have conducted both theoretical and empirical work to answer your question.

Firstly, we theoretically studied the minimum number of samples that could allow us to converge to a reliable estimate. We hence considered the concept of discrepancy of volumes and its known link with the quality of estimation [1, 2]. We provided a complete analysis in the updated manuscript in Appendix M.2 where we derive the following inequality:

$\hspace{8cm} L_{max} \geq \frac{log(\alpha) }{log\left ( 1 - \left ( \frac{ r}{ \epsilon} \right )^K \right )}.$

Recall, that $L_{max}$ denotes the number of sampling per graph, $r$ the radius, $K$ the feature dimensions, $\epsilon$ the attack budget (also defining the input graph’s neighborhood), and $\alpha$ is a discrepancy-confidence level. This bound demonstrates that there exists a required minimum number of samples in order to reach a low discrepancy of volumes, which corresponds to a lower estimation error. The functional form of the bound confirms the intuition that with a small $\epsilon$, we need fewer samples to estimate the robustness of the underlying model.

We furthermore empirically studied the number of samples required for an acceptably low variance of the robustness estimate. Figure 4 in Appendix M.2 displays the results of this study for the Cora dataset. We find that the estimate is already reasonably accurate for small sample sizes, even for 10 samples only, and for the standard deviation to meaningfully decrease within the first 40 considered samples. Thus, with only a small number of samples, we can accurately estimate the expected robustness in practice.

[1] H. Niederreiter - Random number generation and quasi-Monte Carlo methods, SIAM 1992.

[2] S. Tezuka - Uniform random numbers: Theory and practice, Springer Science & Business Media 2012.

We would like to thank the reviewer for their positive and encouraging review. We are pleased that they liked the novelty and applicability of our proposed approach. We additionally are grateful to the reviewer for spotting these typos. Indeed, in the inner loop of Algorithm 1, the features vector $X$ should be replaced by $X_i$ as we may have different graphs in the dataset, e.g. in the graph classification task. The quantity $Z$ is resampled at each iteration of the inner loop in Step 2 and hence, the algorithm is correctly stated without subscripting $Z.$ However, to avoid any confusion, we have chosen to replace $Z$ by $Z_l,$ where $l$ is the iteration counter of the inner loop, in Steps 2 and 3 of Algorithm 1. We have made the necessary adaptations in our revised manuscript.