We thank the reviewer for their review and for acknowledging the novelty of our theoretical analysis and the effectiveness of our proposed RS-Pool. We are indeed very grateful for the kind comments about our manuscript, and we hope that it can help increase the robustness of GNNs especially in critical applications as identified by the reviewer.

We additionally thank the reviewer for pointing out the Bit-flip attacks, which we were not aware of. It is indeed a nice direction of research for adversarial attacks, which is very relevant in the case of GNNs, and especially in the case of graph classification given the limited number of attacks focusing on this specific task. We will add a thorough discussion of this line of research in our related work section. We have additionally found an implementation of this specific attack in the context of GNNs, which takes into account the TU Dataset family, on which we base our experimental setup. We will accordingly try these experiments and provide them in the updated version of our manuscript.

Thanks a lot for the additional results! I think, though, they may have implications way beyond RS-Pool itself, as they suggest a potential relationship between BFAs and attacks using adversarial inputs.

Regarding your methodology, how exactly did you adapt the BFA from [1] to operate on floating point parameters? Did you allow bit flips along the whole floating point semantic (exponent, mantissa, sign) or did you implement any restrictions?

In any case, I think the relationship between pooling and BFA resilience is very important and interesting. This question is of course way beyond the scope of the current paper under review here, but I think it might even be possible to formally show different pooling methods will changes the formal bounds for GNN resilience to BFAs published in [2].

I will reach out to you for further discussions after double-blind review is over (i.e. either and the conference directly or once proceedings are published).

[1] Attacking Graph Neural Networks with Bit Flips: Weisfeiler and Leman Go Indifferent. - Kummer et al. SIGKDD. 2024.

[2] On the Relationship Between Robustness and Expressivity of Graph Neural Networks. - Kummer et al. AISTATS 2025

We appreciate the reviewer’s time and effort in reviewing our paper and for recognizing the significance of studying the effect of pooling in terms of adversarial robustness. In what follows, we try to address the raised questions and weakness:

Q1 - On the distance in the proof of Theorem 4.2 and the punctuation:

We apologize for the raised confusion in this part. Indeed, in Theorem 4.2, we consider feature-based adversarial attacks, which perturb only the node features, and therefore the topology remains unaltered. Hence, the distance (in terms of the norm) between $X$ and $X’$ is smaller than $\epsilon$. We will work on the writing clarity, fix the punctuation and more clearly distinguish matrix and vector norms accordingly.

---

Q2 - On the derived bound in Theorem 5.1:

As spotted by the reviewer, the bounds derived in Theorem 5.1 and Theorem 4.2 share several terms that depend on the weight norms, the message-passing framework and the effect of the structure (expressed in terms of the walks within the graph). The distinctive contribution and the main advantage of RS-Pool becomes more apparent in Corollary 5.2, where the bound is further refined to expose the influence of the hyperparameter $\tau$. This parameter, unique to RS-Pool, offers user control over the robustness-accuracy trade-off, allowing practitioners to directly control the upper bound on adversarial risk, and consequently the model’s underlying robustness. This is not possible with the classical flat pooling approaches considered in Theorem 4.2.

As highlighted in lines 286–287, a key insight is that RS-Pool functions as a robustness stabilizer, even when the preceding message-passing layers are not inherently robust. Unlike traditional pooling methods, which aggregate over potentially perturbed final node embeddings, our proposed pooling rather focuses on the dominant singular vector keeping therefore the dominant, low-frequency signal and attenuates high-frequency components, where adversarial perturbations typically arises [1]. This filtering contributes directly to the tightening of the bound and the improved empirical robustness demonstrated in our experiments. We will clarify this point further in the revised version of our manuscript.

[1] A Frequency Perspective of Adversarial Robustness. Maiya et al. arXiv. 2021.

---

Q3 - On the special case of singular value degeneracy: We thank the reviewer for pointing out this special case. We note that RS-Pool is applied to the final node embedding matrix produced by the message-passing scheme. At this stage, having a dominant singular value with high multiplicity is highly unlikely, even in symmetric graphs, because the learned embeddings do not depend just on the graph structure but also on initial node features and the GNN parameters, which typically break such dominant symmetries. Moreover, GNNs (and actually also Transformers) are known for their inherent smoothing tendencies, which lead to rank-reduction in the feature matrix and result in a non-trivial spectral gap in practice [1, 2, 3, 4, 5].

Nonetheless, as pointed out by the reviewer, we agree that the provided upper-bound doesn’t take into account this specific case, but an extension of Theorem 5.1 to the case where $\sigma_1 = \sigma_2$ is immediate. Specifically, as previously discussed in Wedin’s Theorem, which is the main basis of our proof, extending to the case where the dominant singular value is of multiplicity $r$ shall result in an additional scalar $\sqrt{r}$ (rather than $\sqrt{2}$) in the derived upper-bound $\gamma$ and the considered spectral gap is $\sigma_r - \sigma_{r+1}$. While such a special case is unlikely to arise in practice, we will provide the details of this derivation in the revised manuscript for completeness.

[1] Anisotropy Is Inherent to Self-Attention in Transformers.- Godey et al. - EACL 2024.

[2] How do vision transformers work? - Park N. & Kim S. - ICLR 2022.

[3] Anti-oversmoothing in deep vision transformers via the fourier domain analysis: From theory to practice. - Wang et al. - ICLR 2022.

[4] Attention is not all you need: Pure attention loses rank doubly exponentially with depth. - Dong et al. - ICML 2021.

[5] How expressive are transformers in spectral domain for graphs? - Bastos et al. - TMLR 2022.

We thank the reviewer for their constructive feedback.

W1 - On the “average” versus “worst-case” robustness: Indeed, as pointed out by the reviewer, we rather approach the subject from what we define as the “expected adversarial risk”, which differs from the more commonly used adversarial robustness definition. In this perspective, rather than considering only the worst-case adversarial examples, we consider the whole input’s neighborhood. We believe that our quantity is of complementary value to the typically considered “worst-case” robustness, since in certain settings it is preferable to be robust to “average” attacks rather than to the “worst-case” scenarios [1]. To clarify this ambiguity we will replace the term “adversarial robustness” by “expected adversarial robustness” throughout our revised manuscript. We further note that in our proof, we place no assumption on the sampling distribution of the perturbed graphs within the considered neighborhood defined by the budget $\epsilon$. Hence, the upper-bound $\gamma$ applies to any point within the considered neighborhood $\mathcal{N}\_{\epsilon}$ (refer to the equation following Line 553 in Appendix A). Therefore, with a suitable choice of the sampling distribution of the perturbed graphs, the derived bounds also applies to the worst case (as defined by different attack schemes) since by definition the set of worst-case perturbations are also part of the neighborhood ($\mathcal{S}\_{\epsilon}(A, X) \subseteq \mathcal{N}_{\epsilon}(A, X)$). Hence, while we have focused on the expected adversarial case, our proofs and the derived bounds can be easily adapted to take into account the worst-case adversarial robustness by adapting the definition of the expected adversarial risk. We will make sure to revise the manuscript accordingly to make clear such ambiguity and clarify that the provided bound can also be adapted to the worst-case (by adapting the definition in Eq. 1). We thank the reviewer for pointing this out.

[1] Robustness between the worst and average case. Rice, Bair, Zhang & Kolter. - NeurIPS 2021

Q2 & W2 - Regarding feature-based attacks:

Our empirical results, focused on structural perturbations, as structural attacks and defenses are well-implemented, documented and more commonly studied. Nonetheless, we agree with the reviewer that extending our experiments to feature based adversarial attacks allows us to show a direct connection between our theoretical and practical results, and we thank the reviewer for this suggestion.

We ran the requested experiments by considering two main attacks: The first is random attack (which consists of adding random sampled noise in the node features), and the second is the PGD attack (which uses the gradients). Table 1 provides the mean accuracy (and the standard deviation) of the different considered pooling methods. These new results show that our proposed RS-Pool also outperforms all the other pooling strategies for feature based attacks. We will revise the manuscript accordingly and add these results.

Table 1: Results on feature-based attacks.

Q1 - Is the PGD attack adaptive ?

As pointed out by the reviewer, for each pooling method (including RS-Pool), we differentiate through the pooling, making the attack adaptive. We will add an algorithm describing the attack framework in the appendix of our revised manuscript (note that our implementation is available in the supplementary materials).

Q3 & W4-Linking to the existing bounds:

We thank the reviewer for the different provided references, we agree that citing them and discussing them in detail is important and we will edit the manuscript accordingly. We note that the (adversarial) generalization bounds provide understanding and quantify the difference in terms of the loss from the training to unseen (either perturbed or non-perturbed) test graphs. In our work, we rather consider the specific perturbation effect of the pooling layer choices at inference time. We hence consider a set of flat pooling methods to theoretically study their effect and accordingly we propose a new pooling RS-Pool, which we show theoretically and empirically to have some benefits in enhancing the overall robustness of the model. We believe that studying the generalization bounds of the pooling layer (also our RS-Pool) can be a great way to combine both directions in future work.

W3 - On the considered attack budgets:

We agree with the reviewer that extending to other budgets is indeed very useful to further showcase the value of our proposed method. We therefore have extended the results to 10% and 20% attack budgets in the case of the PGD attack (the most performant attack in Table 1 of our paper). We will additionally extend this study to the other considered attacks and models and update the appendix accordingly. Table 2 reports the mean and standard deviation of the resulting attacked classification accuracy. We see that our RS-Pool is still out-performing the other pooling methods in smaller budgets. We furthermore want to point out that for the binary adjacency matrices we consider, the $L_0$ and $L_2$ norms are equivalent and hence, there is no discrepancy between the norm considered by the threat model and the number of perturbed edges.

Table 2: Results for different attack budgets.

Q4 - On the effect of $\alpha$ and extending the study to other datasets:

We note that $\alpha$ is a hyper-parameter controlling the trade-off between clean and attacked accuracy (based on Corollary 5.2, recall that $\tau = \sigma_1(X)/\alpha$). Typically, depending on the use-case and the user’s need to sacrifice clean accuracy for better robustness, this parameter should be tuned. While we have focused on the PROTEINS dataset in Figure 1 (e), the insights translate to other datasets. In response to your question, we considered 3 additional datasets and higher values of $\alpha$. We will add the required figures in the appendix (which will be based on the table below).

On the trick: We want to warmly thank the reviewer for the proposed “trick”, indeed such an adaptation can reduce the training time of our method, we will edit the code accordingly and provide more details on this implementation in the revised manuscript.

We thank the reviewer for their thoughtful comments and constructive feedback. We especially appreciate their recognition of the novelty and value of our proposed theoretical study and the proposed pooling method. Please find our responses to the raised concerns below:

Q1 - On the semantic meaning of the dominant singular vector:

We thank the reviewer for raising this very interesting question. We first want to recall that our RS-Pool method relies on the dominant singular vector of the node embedding matrix that is produced by several iteratively applied GNN message passing layers. In general, in a GNN, we learn a function that maps from the graph space (often represented via the adjacency matrix) and node feature space (node feature matrix) to the label space as accurately as possible. Consequently, semantic properties of the considered dominant singular vector are highly dependent on the label structure that we attempt to map to and we cannot provide any general semantic interpretation for this vector without regard for the learning task and dataset.

As you rightly point out we have nice semantic interpretations for the singular vectors obtained from the node feature and graph structural space. For the node feature matrix the singular vectors can be interpreted via the long-standing theory on principal components to provide the directions that capture maximal variance of the node features. And like you mention there is a rich theory on the spectral properties of adjacency and Laplacian matrices. These singular vectors (equal to the eigenvectors for symmetric matrices) have indeed been shown to encode community structure [1] and in some instances hubs [2]. Now, our pooling strategy also works with the principal singular vector that captures the direction in which our learned embeddings vary maximally. However, what kind of semantic information is placed in this vector by the trainable GNN layers is entirely dependent on the labels that the GNN is trained to predict. This flexibility to some degree marks the strength of GNNs, as is visible by the strong empirical performance of RS-Pool that we observe in Table 1.

In general, we agree that the semantic analysis of the dominant singular vector in the context of specific learning tasks and dataset is of interest and is a promising direction for future research on the interpretability of GNNs. We will make sure to mention this direction in the revised manuscript.

[1] A tutorial on spectral clustering. U. von Luxburg. Statistics and Computing. 2007.

[2] Authoritative Sources in a Hyperlinked Environment. J. Kleinberg. Journal of the ACM (JACM). 1999

---

Q2 - What kind of information is lost when considering only the dominant singular vector:

While it is correct that focusing on the dominant singular vector discards certain information, particularly high-frequency, node-local variations, we emphasize that in practice, this loss has limited impact on standard graph classification tasks. Empirically, as shown in Table 1 (GCN) and Table 2 (GIN), RS-Pool achieves clean accuracy comparable to that of sum pooling, which retains the full spectrum of signals. This suggests that the fine-grained information encoded in the subdominant singular vectors is rarely essential for achieving high classification performance on clean (non-attacked) graphs.

On the other hand, our motivation centers on robustness. Recent findings [3] indicate that adversarial perturbations tend to manifest in high-frequency components, precisely the directions discarded by RS-Pool. Thus, although the loss of high-frequency information is existent, it is their removal that enables RS-Pool to enhance adversarial robustness. In this sense, our method intentionally trades off a marginal amount of discriminative capacity (which is not always needed for graph classification tasks) for a significant gain in robustness. We thank the reviewer for raising this question, and we shall clarify this trade-off in the manuscript.

[3] A Frequency Perspective of Adversarial Robustness. Maiya et al. arXiv. 2021.

---

Q3 - On the effect of depth and over-smoothing: We appreciate the reviewer’s suggestion to investigate the role of depth in our framework. Traditionally, the adversarial robustness literature does not emphasize depth or other model’s hyperparameters, as models under attack are typically assumed to be well-trained and performant.

Nonetheless, we agree that in the context of GNNs, over-smoothing is an important subject to take into consideration. However, we would like to clarify that over-smoothing is primarily a concern in node classification tasks, where discriminative power between node embeddings is critical. In contrast, in graph classification, the focus of our work, the effect of over-smoothing is less pronounced and can even be regarded as positive [4] since the collapse of the node embeddings is only problematic if the collapsed state is not label-informative.

In the regime of oversmoothing, node embeddings across the graph tend to become similar, effectively collapsing the rank of the node representation matrix $H$ to 1. This leads to the information being concentrated within the dominant singular vector and consequently $\sigma_1$ becomes dominant and subsequent singular values tend to vanish. Therefore, instead of shrinking the spectral gap $\sigma_1 - \sigma_2$ will increase, resulting in better robustness guarantee of RS‑Pool as derived in Theorem 5.1, where the bound is inversely proportional to this gap.

To further illustrate our discussion, we conducted an ablation by increasing the depth of the GCN encoder and evaluated the impact on accuracy for both RS‑Pool and Sum Pooling. We pushed the number of layers until 10, which is the average graph diameter in the considered TUDataset, where at this point, most nodes have already aggregated information from the entire graph. Table 1 provides the mean and standard deviation of the accuracy, where we see that depth has not much effect on the resulting clean accuracy. We will update the manuscript accordingly.

Table 1: Performance of a GCN on different graph classification dataset for different number of layers (depth) for RS-Pool and Sum Pooling.

---

[4] Understanding Virtual Nodes: Oversquashing and Node Heterogeneity. Southern et al. ICLR. 2025.

Dear Reviewer kMFs,

This is a friendly reminder that the reviewer–author discussion phase is approaching its end, and we notice you have not yet responded in the discussion thread. Please take a moment to engage with the authors' rebuttal by sharing your thoughts or follow-up questions. If your concerns have been addressed, kindly acknowledge that in the discussion thread. Before submitting the “Mandatory Acknowledgement,” please ensure that you have engaged in actual communication with the authors. Simply clicking the button without participating in the discussion is not permitted. Thank you again for your time and efforts.

Regards,

AC