GDeR: Safeguarding Efficiency, Balancing, and Robustness via Prototypical Graph Pruning

We sincerely thank you for your careful comments and thorough understanding of our paper! Here we give point-by-point responses to your comments and describe the revisions we made to address them.

Weakness 1 & Question 1: Is the proposed method extendable to other data domains?

To address your concerns regarding the transferability of GDeR to other domains, we will first explain (1) how GDeR can be adapted with minor modifications to other data domains and (2) the performance of GDeR on CV datasets.

Minor Modification On Lines 146-148, we mention that in each epoch, any GNN encoder encodes a graph sample $\mathcal{G}\_i$ into an embedding $\mathbf{h}\_i\in\mathbb{R}^E$, which is then projected into hyperspherical space via the projector $g_\phi: \mathbb{R}^E \rightarrow \mathbb{R}^D$. If we apply this to other data scenarios, such as ResNet+ImageNet training, ResNet would map an image $\mathbf{x}_i$ from ImageNet into a one-dimensional vector $\mathcal{F}(x_i)\in\mathbb{R}^E$ after pooling. We then simply project this $\mathcal{F}(x_i)$ into hyperspherical space, enabling the use of GDeR for data soft pruning in the same manner. Therefore, you can see that GDeR can easily extend to classical backbones in other domains (e.g., ViT, Swin Transformer) and datasets (e.g., CIFAR, ImageNet, COCO).

Performance Evaluation We test GDeR's performance on two classic CV datasets, CIFAR-10 and ImageNet-1k, as shown in Tables A and B. As can be seen, even on the large-scale ImageNet, GDeR demonstrated consistent training speedup without performance loss.

Table A. Accuracy (%) comparison between Random, InfoBatch and GDeR on CIFAR-10+ResNet-18. Remaining ratio are set among {100%, 70%, 30%}.

Table B. Accuracy (%) and Time (hour) comparison between UCB, InfoBatch and GDeR on ImageNet-1k+ResNet-50. Remaining ratio are set as 60%. Our results are tested on eight NIVIDIA Tesla A100 (80GB GPU).

Weakness 2 & Question 2: The authors need to provide discussions both on complexity analysis and numerical comparisons to quantify the extra computational burden.

Following your suggestions, we provide (1) complexity analysis and (2) numerical comparisons to better evaluate the efficiency of GDeR.

Complexity Analysis Taking vanilla GCN as an example, its memory complexity is $\mathcal{O}\left(|\mathcal{D}|\times(L\times |\mathcal{N}|\times E + L\times |\mathbf{\Theta}|\times E^2)\right)$, where $|\mathcal{D}|$ denotes the graph sample count, $L$ denotes the GNN layer count, $|\mathcal{N}|$ denotes the (average) number of nodes, and $E$ represents the hidden dimension. GDeR utilizes an MLP-based projector that maps the graph-level embedding into hyperspherical space, introducing an additional $\mathcal{O}(|\mathcal{D}|\times D)$, where $D$ represents the hyperspherical embedding dimension. Furthermore, each sample needs to compute distances to prototypes, which introduces $\mathcal{O}(|\mathcal{D}|\times |\mathbf{P}|)$, where $|\mathbf{P}|$ denotes the number of prototypes. Overall, the additional complexity introduced by GDeR is $\mathcal{O}(|\mathcal{D}|\times (|\mathbf{P}|+D))$, which is significantly smaller than the complexity of GCN itself. Next, we empirically evaluate the extra burden caused by GDeR.

Numerical Comparisons We provide a comparison of wall-clock time for GDeR, random pruning, and InfoBatch under different pruning rates in the context of MUTAG+PNA, as well as wall-clock time on GraphGPS+Molhiv. It can be observed that although GDeR incurs additional computational overhead due to prototype-related calculations compared to random pruning, these costs are marginal and lead to significant performance improvements (2.8% on Molhiv).

Table C. Results on MUTAG+PNA.

Table D. Results on GraphGPS+Molhiv.

Weakness 3 & Question 3: The authors should report the results at extremely high sparsity levels (e.g. dropping 90% of the samples). Can your method still behaves fairly well?

To address your concerns, we compare GDeR with several best-performing baselines under extremely sparse scenarios.

Table E. Results on MUTAG+PNA.

Weakness 4 & Question 4: The authors should also compare their method with other techniques for data imbalance in Section 4.3.

Thank you for your insightful suggestions! Following your instructions, we have supplemented our experiments in imbalanced scenarios by comparing GDeR with two classic data-balancing plugins. As shown in Table 4, GDeR outperforms existing data balancing techniques across various imbalanced settings.

Table F. F1-Macro (%) comparison of GDeR, DynamicSample and Graph-level SMOTE on MUTAG+GCN. We fix the pruning ratio of GDeR to 20%.

[1] Dynamic sampling in convolutional neural networks for imbalanced data classification

[2] Imbalanced Graph Classification via Graph-of-Graph Neural Networks

We sincerely thank Reviewer RKXd for the thoughtful and constructive reviews of our manuscript! Based on your questions and recommendations, we give point-by-point responses to your comments and describe the revisions we made to address them.

Weakness 1: Though the authors claim that GDER can be extended to graph regression, more experiments are needed to validate their claim in Section 4.2.

Thank you for your insightful comment! We would like to respectfully point out that in Section 3.5 and Appendix D, we provide a detailed explanation of how to extend GDeR to the scenarios of graph regression or unsupervised learning. In Observation 3 of Section 4.2, we analyze the pruning performance and efficiency acceleration of GDeR on GraphMAE+ZINC. We hope this can help you better understand the versatility of GDeR.

Weakness 2: In robust GNN training, the baselines compared are outdated. There are stronger robust GNN baselines [1,2,3].

We admire your extensive knowledge! As the methods you cited [1,2] are limited to node classification, we supplemented the comparison with GraphDE [3] and the latest SOTA method MRGL [4] with our GDeR. Additionally, we employed a newer graph attack method GRABNEL [5] for perturbation attacks. As shown in Table A, GDeR outperforms GraphDE and MRGL in high noise scenarios through its unique soft pruning mechanism.

Table A. F1-Macro (%) comparison among GraphDE, MRGL and GDeR on DAGCN+MUTAG with GRABNEL. We set the pruning ratio of GDeR to 30%.

[3] Graphde: A generative framework for debiased learning and out-of-distribution detection on graphs, NeurIPS 2022

[4] Multi-View Robust Graph Representation Learning for Graph Classification, IJCAI 2023

[5] Adversarial Attacks on Graph Classification via Bayesian Optimisation， NeurIPS 2021

Weakness 3: The authors merely test GDER with poisoning attack on node features. Is GDER capable of addresing evasion attack? Also, the experiments can be stronger if the authors use more advanced GNN attack methods like Mettack [4] or Nettack [5].

Thank you for your feedback! Currently, GDeR only employs defense against adversarial poisoning attacks as it can dynamically identify and remove noisy samples during training. However, we would like to respectfully state this does not affect the comtribution of our work as we understand that most current robust GNN methods focus on solving poisoning attacks rather than evasion attacks.

In our manuscript, we only used noise perturbation on node features as the attack method. This is because there are currently few attack methods specifically designed for graph-level classification tasks, as noted in [1]. However, we have supplemented in our response to Weakness 2 with a performance comparison of different robust GNN methods against the newer graph-level attack GRABNEL, and we hope this will address your concerns.

[1] Adversarial Attacks on Graph Classification via Bayesian Optimisation

Minor

Thank you for your insightful suggestions! We promise to include Table 7 in the main text in the camera-ready version. Regarding Line 184/189, we did mistakenly write $\mathcal{X}_t$ as $\mathcal{D}^{(t)}$, and we appreciate your correction!

Question 1: Figure 1 shows the sample label ditrbution using Infobatch, right? If so, what is the distribution like with GDER?

Thank you for making our work even stronger! We tracked the training trajectory and sample distribution of GDeR on MUTAG+GCN. The visualizations are available at the Figure 1 of the global rebuttal PDF. As can be seen, unlike InfoBatch, which amplifies sample imbalance, our GDeR can effectively alleviate the problem of imbalance by allocating more samples from minority classes and achieving a stable distribution in the later stages of training.

Question 2: Can you give a case study of the graph samples pruned by GDER? For examples, how many of them are with noise? how many of them are from the majority class?

Thank you for your comment, which has further improved the quality of our article!

• Regarding pruning for noisy data, we tracked the training trajectory of GDeR and visualized how it balances the distribution of noisy and clean data in noisy scenarios. The visualizations are available at the Figure 2 of the global rebuttal PDF. It can be observed that as training progresses, GDeR gradually corrects the distribution of the training set, reducing the proportion of noisy/biased data in the maintained training set and thereby reducing the impact of biased samples on the model.
• Regarding pruning of imbalanced data, please refer to our response to Question 1.

Thank you immensely for your time and efforts, as well as the helpful and constructive feedback! Here, we give point-by-point responses to your comments.

Weakness 1: How are the prototypes initialized? I didn't see a note about it from the Algo. 1. Does the initialization of prototypes have an impact on the regulariaztion of hyperspherical space?

Thank you for your insightful inquiry! GDeR follows classic prototype learning practices like [1], randomly initializing prototype embeddings for each cluster. Although different random initializations may affect the subsequent regularization of the hypersphere, we respectfully note that this impact is minimal. As shown in Table 4, even when the number of prototypes per cluster $K=1$, the performance variance of GDeR is around $1-2\%$; as $K$ increases, the performance variance tends to decrease.

[1] Attribute prototype network for zero-shot learning

Weakness 2: Does changing the weights of different losses such as $\lambda_1$ in Eq.(13) have an impact on the model output?

We are happy to answer your question, and conduct a sensitivity on $\lambda_1$ and $\lambda_2$ on MUTAG+PNA, as shown in Table A. We can conclude that (1) too small $\lambda_1$ or $\lambda_2$ can lead to under-fitting of hypersphere and less reliable data pruning; (2) GDeR pruning performs best when $\lambda_1$ and $\lambda_2$ are kept within a similar magnitude. Overall, GDeR is not sensitive to these two parameters, and practitioners can achieve desirable training speedup without extensive parameter tuning.

Table A. Sensitivity analyis of $\lambda_1$ and $\lambda_2$ on MUTAG+PNA. The pruning ratio is set to 50%.

Weakness 3: As shown in Eq. (14), $\Psi(t)$ at the beginning of training, will be relatively large tend to retain the graph retained in the last iteration, as the training proceeds $\Psi(t)$ will tend to be close to 0, resulting in a greater tendency to completely replace the graph retained in the last iteration, making the graph retained in each iteration varies greatly in the last few epochs, can you explain this phenomenon?

We apologize for any confusion caused! In Eq. (14), $\Psi(t)$ and $\widetilde{\Psi(t)}$ should be swapped, such that as the training proceeds $\Psi(t)$ will tend to be close to 1, indicating that we should retain the sample set more in the last few epochs. This is because, at the early stages of GNN training, the randomly selected sub-dataset is likely to be highly noisy, necessitating more frequent swapping. By the end of the training, GDeR has progressively filtered out truly representative, unbiased, and balanced sub-datasets, thus reducing the need for sample swapping.

Weakness 4: There appears to be some typos in line 245. $\lambda$ misses a subscript.

Thank you for your detailed comments! On Line 245, we conducted a grid search for $\lambda_1$ and $\lambda_2$, both ranging in {$1e-1, 5e-1$}.

Question 1: This work looks like it could seamlessly migrate to the CV domain as the authors state in Section 3.5, have you done any extension experiments accordingly?

To address your concerns regarding the transferability of GDeR to other domains, we will first explain (1) how GDeR can be adapted with minor modifications to other data domains and (2) the performance of GDeR on CV datasets.

Minor Modification On Lines 146-148, we mention that in each epoch, any GNN encoder encodes a graph sample $\mathcal{G}\_i$ into an embedding $\mathbf{h}\_i \in \mathbb{R}^{E}$, which is then projected into hyperspherical space via the projector $g_\phi: \mathbb{R}^E \rightarrow \mathbb{R}^D$. If we apply this to other data scenarios, such as ResNet+ImageNet training, ResNet would map an image $\mathbf{x}_i$ from ImageNet into a one-dimensional vector $\mathcal{F}(x_i)\in\mathbb{R}^E$ after pooling. We then simply project this $\mathcal{F}(x_i)$ into hyperspherical space, enabling the use of GDeR for data soft pruning in the same manner. Therefore, you can see that GDeR can easily extend to classical backbones in other domains (e.g., ViT, Swin Transformer) and datasets (e.g., CIFAR, ImageNet, COCO).

Performance Evaluation We test GDeR's performance on two classic CV datasets, CIFAR-10 and ImageNet-1k, as shown in Tables B and C. As can be seen, even on the large-scale ImageNet, GDeR demonstrated consistent training speedup without performance loss.

Table 1. Accuracy (%) comparison between Random, InfoBatch and GDeR on CIFAR-10+ResNet-18. Remaining ratio are set among {100%, 70%, 30%}. Our results are tested on one NIVIDIA Tesla A100 (80GB GPU).

Table 2. Accuracy (%) and Time (h) comparison between UCB, InfoBatch and GDeR on ImageNet-1k+ResNet-50. Remaining ratio are set as 60%. Our results are tested on eight NIVIDIA Tesla A100 (80GB GPU).