Mitigating Emergent Robustness Degradation while Scaling Graph Learning

Dear Reviewer Fsb2:

Thanks for your insightful review. Below, we aim to provide clarifications. We have integrated all updates into the revision of our paper.

[W1. The module of DRAGON is not first proposed in the paper, which slightly limits the novelty of the proposed framework.]

• Novelty on DMGAN Although multiple graph masked auto-encoders [1, 2, 3] have been proposed, the intrinsic denoise ability of graph masked auto-encoder is first revealed by this paper. We are the first attempt to design a denoise graph masked auto-encoder and corresponding pretraining-recovery paradigm to denoise the attacked graph.

• Novelty on DPMoE Previous research on ensemble robustness [10, 11, 12] and MoE techniques [13, 14] only utilize the common components, and each of them is the same as others. We first assign DP noises with different magnitudes to each expert to counteract attacks at different intensities by gate routing. Furthermore, we provide the theoretical robustness guarantee for our DP-based MoE, which to the best of our knowledge has not been discussed in any ensemble robustness or MoE paper before.

• Novelty on motivation and setting Although DP, MoE, and MAE have been proposed in other domains, we identify their particular properties. Specifically, we find (i) masked graph auto-encoder in our design is able to recover clean graphs even under high-intensity attacks; (ii) matching DP noise magnitudes can help model better defense attacks with different intensities; (iii) MoE can select the most matching DP expert to handle the attack with specific intensity. Then, to solve this unique and realistic task (graph learning with anti-degradation robustness against increasing-intensity attacks), we deftly utilize these "particular properties" to design well-motivated new model architecture (DPMoE) and denoising paradigm (DMGAN). Under attacks with different intensities, DMGAN is always able to reconstruct clean graphs and DMGAN selects the most matching DP expert to defense attacks with different intensities.

Finally, our framework is the first to successfully address the phenomenon of severe robustness degradation under increasing intensity graph attacks:

Many existing defense methods, such as RGCN and GNN-SVD, effectively handle mild node injection attacks but experience an emergent decline in robustness as attack intensity increases. As shown in Figure 1, when attack intensity surpasses a threshold of 300 injected nodes, error rates for many models surge by more than 50%. (Quoted from Introduction Section in our submission)

We extensively test DRAGON on various graph datasets, where it not only outperforms popular baselines but also represents the first successful attempt to avoid severe robustness degradation phenomena (which are widespread in the real world, as discussed in Appendix I) while maintaining scalability.

[W2. It would be better if the presentation is more clear. For example, the notations in the lemma are not well introduced. The setting of the attack and defense is not included as well.]

We appreciate your feedback!

• Recognizing the need for better clarity, we have revised our manuscript to reintroduce and clearly define the notations at the start of the lemma, even if they have been previously mentioned.

• To further clarify the attack and defense settings, we have now included detailed descriptions in Appendix C.

We appreciate your concern regarding the training process of DMGAN and its adherence to the settings of the Graph Robustness Benchmark (GRB) and adversarial training. We assure that our framework (including the DMGAN module), strictly complies with these settings during both the training and evaluation phases. To clarify, here is a more detailed explanation of our process aligned with GRB guidelines:

• Training Stage: During training, DMGAN only has access to the clean training graph on the training set, as the model's input. This input is subsequently subjected to adversarial attacks (e.g., PGD attack) to generate adversarial training examples, following standard adversarial training practices.

• Evaluation Stage: In test evaluation, DMGAN operates only on the test graphs, which are also attacked (e.g., PGD attack). It does not have access to, nor does it recall, any clean test graph information. Hence, there is no test-set information leakage concerning the test nodes targeted for attack or the modifications/injections made to the edges/nodes.

Based on training data, DMGAN is trained to learn general patterns and representations that enable the reconstruction of a perturbed graph into a cleaner version, using only the data from the training set and instead of using data from the test set. During test evaluation, given only an attacked test graph from the test set as input, it attempts to recover a clean(er) graph without any prior information leakage about the clean information from the test graph set. Therefore, DMGAN adheres to the GRB's conditions, which prohibit access to the clean graph during evaluation and any information leakage/foreknowledge of attack modifications.

In summary, our experimental setup uses the training and test data provided by the GRB. We train DMGAN on the clean training-set graph and apply it to the attacked test-set graph. So our approach is fully compliant with the GRB rules: DMGAN does not have access to the clean test graph and lacks prior information about the specific edges/nodes that have been modified or injected.

In fact, DMGAN's strategy (i.e., firstly cleaning the input test data and then making robust test predicting easier for evasion defense) is also a widely used philosophy in robust vision/language processing for evasion defense, as evidenced by studies [5, 6, 7, 8]: For example, robust NLP methods referenced in [5, 6] similarly transform noisy or attacked test text into a cleaner state without access to the original clean information of test data as a first step (akin to our DMGAN approach), then simplifying the task of making robust predictions in an evasion defense context as a second step. Thus, they also do not break the rule, which is also consistent with the basic rules of adversarial robustness summarized by the Graph Robustness Benchmark.

We would also like to clarify that the poising attack is a different setting from our paper's evasion attack. As GRB's said:

Poisoning: Attackers generate corrupted graph data and assume that the targeted model is trained on these data to get a worse model (usually worse on clean test data).

Evasion: The target model has already been trained, and (during the test phase) attackers can generate corrupted test graph data to affect its inference.

Our design mainly concentrates on defending against evasion attacks provided by GRB, so defending against poisoning attacks is out of our scope. Since there is already a lot of research [2, 3, 4, 9] (only) focusing on attack-defense under graph evasion attack/defense setting, and evasion defense is also considered more realistic than poisoning setting in GRB [2], we would like to humbly clarify our targeted exploration of evasion attack/defense settings, while not encompassing poisoning attacks, doesn't harm the core contribution of our work.

References:

[1] Towards Deep Learning Models Resistant to Adversarial Attacks, ICLR 2018

[2] Graph Robustness Benchmark: Benchmarking the Adversarial Robustness of Graph Machine Learning, NeurIPS 2021

[3] Chasing All-Round Graph Representation Robustness: Model, training, and Optimization, ICLR 2023

[4] Understanding and Improving Graph Injection Attack by Promoting Unnoticeability, ICLR 2022

[5] Detecting Textual Adversarial Examples through Randomized Substitution and Vote, UAI 2022

[6] Combating Adversarial Misspellings with Robust Word Recognition, ACL 2019

[7] An Efficient Image Compression Model to Defend Adversarial Examples, CVPR 2019

[8] Deflecting Adversarial Attacks with Pixel Deflection, CVPR 2018

[9] Tdgia: Effective Injection Attacks on Graph Neural Networks, KDD 2021

Thanks for the authors' detailed review. Most of my concerns have been well addressed, but I'm still worried that "train the DMGAN on the clean training graph" is problematic.

To the best of my knowledge, although the defending model is trained on the clean graph during evaluation, it is not allowed for the defender to access or "remember" the clean graph in their model design. Using DMGAN to reconstruct the clean graph where it is trained seems to violate the rule. As it said in "Graph Robustness Benchmark": For defenders: (a) They have knowledge about the graph excluding the test nodes to be attacked. (b) They are allowed to use any method to increase the adversarial robustness, but do not have prior knowledge about the edges/nodes that are modified/injected.

If the clean graph is obtained by the defender, the edges/nodes modified/injected can be detected, which I think can not be called following the setting of the graph robustness benchmark. It would be better for the authors to clarify the problem setting or train DMGAN on the attacked graph.

And a follow-up weakness seems to be that DRAGON can not tackle poison attacks, where the whole model needs to be trained on the attacked graph.

[Q4. How DRAGON would perform when compiled with other basic GNNs like GCN? Is it still competitive?]

DRAGON serves as a plug-and-play framework with the flexibility to be integrated with different GNN backbones, i.e., the motivation of DRAGON is the generality of helping the defense model/backbone. We plug DRAGON into the basic GAT on most datasets and only with GATGuard (w.o. AT) on small datasets. Here we plug DRAGON into GCN on several datasets with different scales in Tables F and G, which also show the competitive performance and scalability of our method. Although DRAGON with GCN backbone performs less robustly on CiteSeer, DRAGON+AT still leads in robustness.

Table F. The robustness performance of our method with GCN backbone under FGSM attacks on the Citeseer (small-scale) dataset.

Table G. The robustness performance of our method with GCN backbone under FGSM attacks on Flickr (medium-scale) and Reddit (large-scale) datasets. The improvement denotes the improvement of our method compared to the best performance among all baselines.

[Q5. Why the baselines like GATGuard and EvenNet not coupled with AT?]

As shown in Table H, training GATGuard and Evennet with AT hurts their robustness. Therefore, we don't combine GATGuard and Evennet with AT since they are stronger baselines without AT for fair comparisons.

Table H. The performance of baselines under FGSM attack on the Cora dataset.

It is worth noting that not all defense methods can improve the robustness via adversarial training. Previous benchmark research [4] also has shown that GATGuard+AT has less robustness compared with GATGuard. This phenomenon can be explained by the special architecture designed against modification attacks, and introducing adversarial samples via max-min adversarial training often instigates a shift in data distribution compared to real-world adversarial samples, a phenomenon discussed at length in [5].

References:

[1] GraphMAE: self-supervised masked graph autoencoders, KDD 2022

[2] Heterogeneous graph masked autoencoders, AAAI 2022

[3] S2GAE: self-supervised graph autoencoders are generalizable learners with graph masking, WSDM 2023

[4] Graph robustness benchmark: Benchmarking the adversarial robustness of graph machine learning, NeurIPS 2021

[5] Adversarial examples improve image recognition, CVPR 2020

[6] Masked autoencoders are scalable vision learners, CVPR 2022

[7] Switch transformers: scaling to trillion parameter models with simple and efficient sparsity, JMLR 2022.

[8] Detecting Textual Adversarial Examples through Randomized Substitution and Vote, UAI 2022

[9] Combating Adversarial Misspellings with Robust Word Recognition, ACL 2019

[10] TRS: Transferability reduced ensemble via promoting gradient diversity and model smoothness, NeurIPS 2021

[11] Building robust ensembles via margin boosting, ICML 2022

[12] Diversifying vulnerabilities for enhanced robust generation of ensembles, NeurIPS 2020

[13] Outrageously large neural networks: The sparsely-gated Mixture-of-Experts layer, ICLR 2017

[14] Switch transformers: Scaling to trillion parameter models with simple and efficient sparsity, JMLR 2022

[15] An efficient image compression model to defend adversarial examples, CVPR 2019

[16] Deflecting adversarial attacks with pixel deflection, CVPR 2018

[Q2. What the results would be if the denoising module is compiled with other defense models? For example, GATGuard + DMGAN. It looks like the two modules of DRAGON can be decoupled.]

DMGAN can also be combined with other defense models and improve the robustness performance: in Table D below, GATGuard + DMGAN has better robustness performance than GATGuard. We also combine DMGAN with another competitive baseline, GAME, and show the results in Table E, where GAME+DMGAN also has better robustness than GAME.

Table D. The robustness performance of GATGuard and GATGuard + DMGAN under FGSM attack on the Cora dataset.

Table E. The robustness performance of GAME and GAME + DMGAN under FGSM attack on the Cora dataset.

As shown in the previous Table D and Table E, for the most competitive baselines, GATGuard + DMGAN still suffers from out-of-memory on GPU and GAME + DMGAN suffers from severe robustness degradation. These results again reflect the scalability and robustness against degradation of DPMoE.

[Q3. Does the reported time in Table 18 include the training time of DMGAN?]

Yes. Our design is efficient for two reasons: (i) according to the analysis in Appendix H, the time complexity is linear: O(N+E), which indicates training time is linearly increasing with the number of node N and the number of edge E; (ii) although DPMoE is complex and consists of multiple experts, it dispatches nodes to experts without repeat training on the same data. This efficient property has been analyzed in previous research [7].

[W3. The whole framework is quite complex and not in an end-to-end manner. It includes quite a few hyperparameters, and choosing a proper GNN backbone seems to matter, which would be a concern when applied to real-world scenarios.]

We appreciate your comment and would like to clarify the following points:

• Our framework adopts a two-stage design (denoising -> prediction). While this may seem complex in concept, it does not translate into complexity during real implementation or inference. In particular, our experimental results show that the training and inference processes remain efficient (not overly complex compared to baselines). Moreover, the two-stage approach is a proven strategy/philosophy in the domains of vision/language processing for stable learning in the real world, as evidenced by studies [8, 9, 15, 16].

• DRAGON with different GNN backbones has different performance, but DRAGON uniformly improves backbone robustness a lot. We further provide the performance of DRAGON with GCN backbone in Table F and Table G. Although DRAGON with GCN backbone is slightly less robust than DRAGON with GAT backbone in the paper, it still outperforms other baselines.

• We analyze the sensitivity of 5 key hyperparameters (3 for DMGAN, 2 for DPMoE) in Tables 6, 12, Figures 9, and 10, respectively. According to the analysis of tables and figures, these hyperparameters are not very sensitive to downstream performance and they are also easy to tune according to the observed regular pattern from different scales' experiments, then reduce the tuning complexity in real-world datasets.

[Q1. How is the auto-encoder trained and is it trained on the clean graph or trained on the attacked graph? If the denoising module is trained on the attacked graph, why auto-encoder enjoy such a good performance in recovering clean graph structure? Including more discussion about the intuition why the denoising part is effective would be better.]

• We train the DMGAN on the clean training graph, which follows the settings (dataset configurations, evaluation configurations, etc.) of the graph robustness benchmark [4].

• The path masking strategy disrupts the edges between consecutive nodes, prompting the model to grasp the structured dependency and higher-order proximity inherent in node relationships from 'mask noise'. This, in turn, enables the model to reconstruct a clean graph from the initially attacked one.

• The initial intuition of this design is inspired by vision representation research [6], where researchers observed a phenomenon: reconstructed examples, although distinct from the ground truth, remained semantically plausible. Therefore, we propose DMGAN to effectively remove edges that lack semantic plausibility and deviate from the normative distribution of structural characteristics.

[Q2. In Table 1 why adversarial training can hurt the robustness of DRAGON for most cases?]

The principle behind adversarial training (AT) is to enhance model resilience against adversarial attacks. Yet, the introduction of AT does not guarantee uniform success across all contexts (which will not hurt the overall usefulness of AT across all contexts, too). Here we delve deeper into two facets:

• Potential Distribution Shift during AT: Introducing adversarial samples via max-min adversarial training often instigates a shift in data distribution compared to real-world adversarial samples, a phenomenon discussed at length in [3]. In our findings, under non-attacked conditions or when model performance mirrors that of a non-adversarial state, the data sample distribution during AT does not align with that of the non-attacked samples. This divergence in distribution gives rise to a marginal performance dip when integrating AT with DRAGON, which mirrors observations made in previous studies [3].

• Trade-offs between Robustness and Performance: As paper [4] illustrated, while trade-offs between robustness and performance are common in normal trained models, the trade-offs between robustness and performance on AT-trained models become more apparent when AT training is employed. In our experiments, DRAGON, when trained with AT, frequently delivers performance close to that of its non-AT-trained counterpart, sometimes even matching or outperforming it.

Despite the noted trade-off, DRAGON's robustness--both with and without AT--is impressive, particularly when benchmarked against prevailing baseline methodologies. In summation, while integrating AT into DRAGON presents certain challenges, the overarching robustness and performance exhibited by our method remain noteworthy (e.g., the ability to resist the emergence of severe robustness degradation), reiterating its value in severe adversarial contexts.

References:

[1] Improving the Gaussian mechanism for differential Privacy: Analytical calibration and optimal denoising, ICML 2018

[2] Calibrating noise to sensitivity in private data analysis, Theory of Cryptography 2006

[3] Adversarial examples improve image recognition, CVPR 2020

[4] Ensemble adversarial training: Attacks and defenses, ICLR 2018

[5] Towards understanding the Mixture-of-Experts layer in deep learning, NeurIPS 2022

[6] A Mixture of Experts classifier with learning based on both labelled and unlabelled data, NeurIPS 1996

[7] Certified robustness to word substitution attack with differential privacy, NAACL 2021

[8] Certified robustness to adversarial examples with differential privacy, IEEE Symposium on Security and Privacy (S&P) 2019

[9] The algorithmic foundations of differential privacy, Foundations and Trends in Theoretical Computer Science 2014

[W2. Confusion about Lemma 1: "Suppose a GNN $f(·)$ containing DPMoE satisfies $(\sigma, \delta)$-DP", how can this be supposed? I thought Lemma 1 was to prove that adding a DPMoE module to the model would make it DP, but the authors directly assume that. Besides, what does this mean "node $v$ is robust to the features"? This statement is too informal and the authors should characterize robustness in rigorous mathematical expressions.]

• Clarifying Lemma 1's purpose: We appreciate the opportunity to elucidate Lemma 1's role. The lemma does not aim to demonstrate that the DPMoE module confers $(\epsilon, \delta)$-DP of the composition model $f(·)$; instead, it assumes $(\epsilon, \delta)$-DP property of the composition model $f(·)$ to establish an extended robustness guarantee. This assumption follows precedents in NLP (e.g., [7] on NAACL 2021) and CV (e.g., [8] on IEEE-S&P 2019), where language/vision models composed of the DP module can be assumed to satisfy $(\epsilon, \delta)$-DP, and then contribute to stability. The $(\epsilon, \delta)$-DP property in DPMoE is justified through its use of the classical Gaussian DP output perturbation (this mechanism is inherently $(\epsilon, \delta)$-DP [1, 2, 9]), due to the post-processing invariance of differential privacy(i.e., any computation on the output of the DP mechanism remains DP). Consequently, the output of DPMoE adheres to this differential privacy standard. For better clarity, we replace 'Suppose a GNN $f(·)$ containing DPMoE satisfies $(\sigma, \delta)$-DP' with 'For a GNN $f(\cdot)$ containing DPMoE which utilizes Gaussian DP, assume this mechanism lets the model output satisfy $(\sigma, \delta)$-DP.

• Theoretical Basis for Robustness: As discussed in Section 4.2, Lemma 1 provides theoretical backing for the robustness of DPMoE (proof in Appendix A). This underpins our integration of DP into MoE:

By examining these inequalities, we uncover the necessary conditions for the model to maintain robustness—specifically, that the expected output for class k significantly surpasses that of any other class. The proof then extends these findings to models incorporating DPMoE, demonstrating that if a DPMoE model meets the specified conditions, its robustness is established.

• Formalizing 'Robustness to Features': To address the ambiguity around the phrase 'node $v$ is robust to the features', we provide a rigorous definition in Appendix A, Equation 19: $\mathrm{E}(f_k(h_{v}^{'(l)})) \geq \max_{i : i \neq k} \mathrm{E}(f_i(h_{v}^{'(l)}))$. This inequality rigorously quantifies the robustness in a mathematical expression, indicating that the expected output for the correct class $k$ remains the highest even after a node injection attack. We use $h_{v}^{'(l)}$ to express node $v$ is attacked after aggregating injection node features.

Further, we provide a thorough proof of how robustness, as stated in Lemma 1, is achieved given the precondition outlined in Equation 9. This is detailed in Appendix A of our manuscript, offering both a formal treatment and intuitive insight into the model's robustness against feature perturbations.

[Q1. Why the deviation is in this form:$\sigma = \sqrt{2\ln(1.25/\delta)}/\epsilon$ in DPGC in section 4.2?]

We follow the conclusion of $\sigma = \sqrt{2\ln(1.25/\delta)}/\epsilon$ from the classical Gaussian differential privacy mechanism [1, 2, 9]. Thank you for the reminder and we will add the clarification in the preliminary as follows:

For any $\sigma, \delta \in (0, 1)$ be two privacy parameters, the classical Gaussian differential privacy mechanism has the form $\sigma = \sqrt{2\ln(1.25/\delta)}/\epsilon$ [1, 2, 9].

Dear Reviewer qpZP:

We sincerely appreciate your constructive suggestions for our work. We also take your suggestions into account and address them below.

[W1. Illustrations in some sections are not clear and easy to follow. For example, in Section 4.2, the notations are not clearly introduced. Besides, the motivation of DPMoE is not well introduced. The authors should provide some intuitions/insights for leveraging Mixture-of-Experts, which I think is an important novelty of this work. But from this section, I do not get why MoE is useful though the authors empirically illustrate that in the experimental part.]

Thank you for bringing this to our attention!

First, to further clarify the illustrations, we have now revised our manuscript to have clearer descriptions of notations, especially for Section 4.2 and Lemma 1.

Second, the motivation for our model's DPMoE is discussed in Section 4.2 of our manuscript：

In comparison to the previous DP-GConv formulation in Equation (5), the proposed DPMoE layer employs a gating mechanism to control multiple experts, each equipped with multi-scale DP Gaussian noises. This allows it to effectively handle node injection attacks of varying intensities while maintaining higher anti-degraded robustness.

More specifically, matching DP noise magnitudes can help model better defense attacks with different intensities, and MoE can route the node feature to the most matching DP expert to handle specific intensity attacks. The effectiveness of this design to support our motivation is empirically illustrated in the experimental part.

Regarding why MoE is useful, previous research [6] has demonstrated that MoE architectures can adeptly manage data noise, implying an inherent potential for handling perturbations in our graph adversarial scenarios. Moreover, insights from a theoretical study [5] on MoE strengthen our methodology too:

Each expert is good on one cluster and the router only distributes the example to a good expert. (In Section 4 of research [5])

The mixture of non-linear experts can correctly recover the (underlying) cluster structure and diversify. (In Section 6.1 of research [5])

These results do not only explain our empirical findings but also justify our intuition. That is, the MoE mechanism can recover the underlying noisy cluster structure and distribute the node to the right robust expert with matching DP noise against different attack intensities.

Your feedback is greatly appreciated. We are encouraged that our response addressed your main concerns. Thank Reviewer qpZP again for taking the time to evaluate our paper!

References:

[1] EvenNet: Ignoring odd-hop neighbors improves robustness of graph neural networks, NeurIPS22

[2] Chasing all-round graph representation robustness: Model, training, and optimization, ICLR23

[3] Gnnguard: Defending graph neural networks against adversarial attacks, NeurIPS 2020

[4] Adversarial robustness in graph neural networks: A hamiltonian approach, NeurIPS 2023

[5] Graph robustness benchmark: Benchmarking the adversarial robustness of graph machine learning, NeurIPS 2021

[6] Robustness of Graph Neural Networks at Scale, NeurIPS 2021

[7] GARNET: Reduced-rank topology learning for robust and scalable graph neural Networks, Learning on Graphs Conference 2022

[8] Graph structure learning for robust graph neural networks, KDD 2020

[W3. The denoising performance of the proposed auto-encoder module is not compared to baselines such as Jaccard, SVD, etc.]

We have provided the performance of Jaccard, SVD, and proposed ablated DMGAN in the original paper. Table 16 in our Appendix G shows that the performance of Jaccard is less robust than GAT with AT and even close to vanilla GAT under node injection attacks. This structure-based weakness has been discussed in the benchmark [5], which avoids Jaccard as a baseline. In our manuscript, Table 1 shows that the SVD method only has close robustness to GCN with AT on Cora and is even less robust than vanilla GCN on CiteSeer. In contrast, ablated DMGAN module in Table 2 and Table 13 have better performance than these baselines (e.g., Jaccard, SVD).

To further compare DMGAN with Jaccard and SVD, we conduct the experiment on them with unified backbone GCN and report the results in Table B.

Table B. The robustness performance of different methods under FGSM attack on the CiteSeer dataset.

According to our experiments, Jaccard and SVD cannot defend injection attacks well like DMGAN. They are only designed and effective to defend against structure (edge) perturbations between original nodes by cleaning the structure with ad hoc designs, making them less generalizable and practical to defend against advanced node injection attacks with both malicious features and edges. Furthermore, SVD can't scale to medium/large graphs (such as Flickr, Reddit, and AMiner datasets) since it suffers from out-of-memory on a 32GB Nvidia V100 GPU.

[Q3. Details on how $E_{r}$ is derived from the trained auto-encoder. Can it include new edges, or does it solely filter out some existing ones?]

The DMGAN, once trained, reconstructs edges by predicting their existence based on the node features within the attacked graph. This prediction aligns with link prediction methodologies. While it is true that the DMGAN may inadvertently eliminate some existing edges, the robustness of the DPMoE ensures that such occasional omissions do not adversely affect the downstream classification performance. Even at the highest level of attack intensity $V$, the proportion of existing edges mistakenly removed remains below 7.4%. We refer to the subsequent answer, which includes Table C detailing these comprehensive results.

[Q4. The results in Table 11 are not easy to understand. Can you please provide more specific details, including the numbers of TPs, TNs, FPs, and FNs?]

Thanks for bringing this to our attention. Let's denote TPR-N↑ (FNR-N↑) as TPR (FNR) for link prediction between normal/original nodes; and TPR-A↑ (FNR-A↑) as TPR (FNR) for link prediction between original nodes and injection/attack nodes. Since DMGAN doesn't need to predict non-existent edges on the attacked graph, we don't have FPRs and TNRs. The results in Table 11 are actually statistics of FNR-N and TPR-A. Here in Table C, we rewrite Table 11 in the following form according to your suggestion.

Table C. TPRs and FNRs of DMGAN under FGSM attack on the Cora dataset.

FNR-N (less than 7.4%) indicates the ratios of edges between original nodes are wrongly removed by DMGAN. Combine with the ablation study in Table 2 and Table 13, we find that such extra wrong removal introduced by DMGAN can only lead to

(i) 0.1% performance decrease on Cora and CiteeSeer datasets of DRAGON;

(ii) 0.2% and 2.0% performance decrease on Flickr and AMiner datasets of DRAGON.

Similarly, the previous research [8] also has the same observation that the wrong removal of this level between original nodes only causes a small robustness degradation (less than 3%) on GNNs. FNR-A (more than 25.1%) indicates the ratios of harmful malicious edges associated with attack nodes are removed by DMGAN, which is a large proportion of the total malicious edges.

The above indicates that the wrong removal of true edges between original nodes by DMGAN is not a big problem to harm downstream performance, and in fact, the removal of malicious edges between original nodes and attack nodes is the key to improving the robustness of DRAGON.

Dear Reviewer owAp:

Thank you for your constructive questions and helpful comments. Here we address your concerns as follows. We also integrate all updates into our revised manuscript.

[W1&Q1. The argument regarding the poor scalability of existing methods needs to be further investigated.]

The scalability issue for the existing graph defenses has been well-discussed in previous research [1, 5, 6, 7]. We follow the discussion in previous research [5, 6, 7] on SVD to take the scalability issue as a fundamental limitation. Research [5, 7] further explains why the SVD defense method has a fundamental limitation on scalability and is hard to implement efficiently:

Concretely, as previous TSVD-based methods produce a dense (low-rank) adjacency matrix $A$, they involve dense matrices during GNN training, which has quadratic time/space complexity and thus cannot scale to large graphs. However, naïvely selecting the largest elements of each row in $A$ requires forming/storing $A$ first, which still has quadratic time/space complexity. (Appendix R in research paper [7])

GNN-SVD utilizes a low-rank approximation of the graph, that uses only the top singular components for its reconstruction... GNN-SVD and GNNGuard are not scalable to large-scale graphs due to the calculation of large dense matrices. (Appendix A.4.3 in research paper [5])

Therefore, the SVD defense has a fundamental limitation: it produces a dense (low-rank) matrix (even for sparse graphs), and it is difficult to scale to medium/large graphs (out-of-memory on 32GB Nvidia V100 GPU) with quadratic complexity (as shown in Table 1, Flickr, Reddit, and AMiner datasets) using trivial implementation techniques.

[W2&Q2. It appears that the considered baselines were not specifically designed to address the attack scenarios under consideration (i.e., the injection of nodes). For instance, EvenNet is specifically designed for generalization to graphs with different degrees of homophily. Consequently, claiming superiority over them may not strongly support the effectiveness of the proposed method. The authors should consider evaluating their approach against state-of-the-art methods better aligned with the specified attack scenarios.]

• The baseline GAME [2] (on ICLR 2023) we used is designed to address node injection attacks. In addition, we have included recent defense methods that are widely competed under node attack scenarios, such as methods [1, 2, 3], and other competitive baselines in graph robustness benchmark (GRB) [5]. Note that GRB is a specialized, large-scale benchmark for defending against injection attacks, and we follow this benchmark to introduce several competitive baselines.
• While we notice EvenNet [1] suffers from severe robustness degradation, we include EvenNet as baselines since its authors claim that EvenNet is still competitive against strong graph injection attacks (GIAs) in Appendix F of its original paper [1]:

Notwithstanding GIAs are somehow out of the scope of EvenNet, we can see that EvenNet is still competitive against strong spatial baselines in Table F, which verifies the ability of EvenNet under homophily change.

• To further address your concern, we provide the performance of HANG/HANG-quad [4] (on NeurIPS 2023) and other competitive and new baselines (e.g., GAME on ICLR 2023 [2]) that are already included in our paper in Table A. In particular, HANG/HANG-quad (published 1 month after ICLR 2024 submission) is the most recent graph robust learning method against injection attacks. However, HANG suffers from scalability limitations (out-of-memory issues on large graph datasets such as Reddit and AMiner) and is less robust than DRAGON and other included baselines [2, 3].

Table A. The robustness performance when defenses are under FGSM attack on the Cora dataset.

Dear Reviewer kprb:

We sincerely appreciate your professional and insightful suggestions for our work. We have taken your suggestions into account and addressed them below:

[How is the performance of the proposed method against other attacks?]

We have also provided the analysis and the performances of our method against other graph injection attacks, graph modification attacks and graph adaptive attacks in Appendix B, E and F. In these graph attack settings, our method outperformed other popular baselines.

[There are other choices for improving GNN from an ensemble perspective. It is necessary to discuss the comparison.]

Besides MoE, other related ensemble methods [2, 3, 4] have been verified to improve model stability. However, recent research [1] finds simple ensemble methods face adversarial risks and have an upper bound of robustness. First, our DPMoE avoids these adversarial risks and no worst-case performance guarantees by employing the MoE with a gate network. Second, different from common ensemble methods, our method spontaneously selects the most appropriate DP expert with suitable DP noise magnitude to effectively counteract adversarial attacks at different attack intensities.

References:

[1] On the robustness of randomized ensembles to adversarial perturbations, ICML 2023

[2] TRS: Transferability reduced ensemble via promoting gradient diversity and model smoothness, NeurIPS 2021

[3] Building robust ensembles via margin boosting, ICML 2022

[4] Diversifying vulnerabilities for enhanced robust generation of ensembles, NeurIPS 2020