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

Summary

This paper introduces a novel training debugging concept aimed at enhancing efficiency, robustness, and balance during the graph training process. It employs trainable prototypes to dynamically select appropriate samples for each training iteration. The concept is innovative and intriguing. However, the experiments are confined to the graph domain, which raises questions about its generalizability. The authors might need to further elaborate on this issue in the text to address potential limitations.

Strengths

1. Topic of large importance in the community given the direction of the field. The authors proposed training debugging, namely robust and unbiased soft pruning, is indeed novel and significant, especially in the context of research on large models where data collection is increasingly extensive. This approach addresses critical challenges in ensuring that these large-scale models train effectively and efficiently, mitigating issues that might otherwise go unnoticed due to the complexity and size of the data involved. 2. The article is well written and engaging, particularly excelling in the clarity of its experimental tables and diagrams. These elements contribute to a structure that quickly aids readers in understanding the contributions of the paper.

Weaknesses

1. One of my main concerns is whether this concept is only applicable to graph training. If it is limited solely to graphs, the overall contribution of this work may not reach a particularly high standard. Especially relevant is whether its methodology can be transferred to datasets for CV or NLP. 2. Intuitively, the introduction of prototypes may potentially decrease the training speed of the original GNN backbone. Considering there are $K$ prototypes and $|D|$ training samples, each epoch would require the computation of similarity scores between samples and prototypes at $\mathcal{O}(K \times |D|)$ space complexity. This is bound to introduce additional overhead during backpropagation. The authors need to provide discussions both on complexity analysis and numerical comparisons to quantify the extra computational burden. 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? 4. The authors should also compare their method with other techniques for data imbalance in Section 4.3. Data imbalance/long-tail distribution is a long-standing issue with many established solutions in CV. To name a few, focal Loss [1] and Dynamic Sampling [2]. [1] Focal loss for dense object detection [2] Dynamic sampling in convolutional neural networks for imbalanced data classification

Questions

1. Is the proposed method extendable to other data domains? 2. How does the trainable prototypes effect the training speed? 3. Can GDeR remain its performance even pruning a great propotion of training samples? 4. Can you compare GDeR with other data imbalance baselines?

Rating

8

Confidence

4

Soundness

3

Presentation

4

Contribution

3

Limitations

Yes

Summary

This paper presents a novel method for graph neural network training called Graph De-Redundancy. This method aims to enhance the efficiency, balance, and robustness of GNN training. It constructs a hyperspherical embedding space using trainable prototypes to maintain a balanced subset of the training data, addressing the computational and performance challenges posed by large-scale, imbalanced, and noisy datasets. The experiments demonstrate that GDeR can achieve or surpass the performance of full datasets with significantly fewer samples, achieving up to a 2.81× speedup and outperforming existing pruning methods in various scenarios. Overall, this approach achieves an effective, balancing, and robust pruning method for graph datasets, showing the potential for efficient training of graph datasets and even general datasets.

Strengths

1. The study gives a powerful solution that meets the multifaceted needs of balance, stability and efficiency, and has great potential for application especially on large-scale and unbalanced graph datasets. 2. Using a hyperspherical embedding space and trainable prototypes for dataset pruning in graph learning is quite novel. In addition, the authors give sound explanations and theoretical support for these methods. 3. The paper is fluently written, with clear explanations of the problem, methodology and results. Especially the graphs and visualisations in the paper are impressive.

Weaknesses

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? 2. Does changing the weights of different losses such as $\lambda_1$ in Eq.(13) have an impact on the model output? 3. As shown in Eq. (14), at the beginning of training,$\Psi(t)$ 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? 4. There appears to be some typos in line 245. $\lambda$ misses a subscript.

Questions

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?

Rating

6

Confidence

3

Soundness

2

Presentation

3

Contribution

3

Limitations

The authors have adequately discussed the limitations.

Summary

This paper addresses the computational and memory challenges posed by large datasets in the training of graph neural networks (GNNs). The authors propose GDeR, a dynamic soft-pruning method that leverages trainable prototypes to regularize the graph embedding distribution. This approach aims to maintain a balanced and unbiased subset of the data during training, thereby enhancing the efficiency and robustness of the learning process.

Strengths

(1) Soft dataset pruning for graph data remains underexplored for the past years, and GDER makes the first attempt. (2) The paper reads very well, with straightforward motivation and well-organized methodology. I appreciate its visual aids (Fiure 2,3). (3) The experimental results (particularly on GraphMAE+ZINC) are encouraging. It is demonstrated that GDER can save over 60% of the training wall-clock time without performance decay. I believe GDER has the potential to become a general acceleration operator/plugin for the graph learning community.

Weaknesses

(1) The methodology is primarily organized around graph classification. Though the authors claim that GDER can be extended to graph regression, more experiments are needed to validate their claim in Section 4.2. (2) In robust GNN training, the baselines compared are outdated. There are stronger robust GNN baselines [1,2,3]. (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]. Minor: I recommend the authors to move Table 7 to the main text. Pretraining GNNs present more computational burden, so its accelerating is more meaningful. Besides, On Lines 184 and 189, does $D^{t}$ refers to $X_t$? [1] Adversarial robustness in graph neural networks: A Hamiltonian approach, NeurIPS 2023. [2] A Simple and Yet Fairly Effective Defense for Graph Neural Networks, AAAI 2024 [3] Graphde: A generative framework for debiased learning and out-of-distribution detection on graphs, NeurIPS 2022 [4] Adversarial attacks on node embeddings via graph poisoning, ICML 2019 [5] Adversarial attacks on neural networks for graph data, KDD 2018

Questions

(1) Figure 1 shows the sample label ditrbution using Infobatch, right? If so, what is the distribution like with GDER? (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?

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

The limiations are discussed in the paper.

Response

I read the replies, which addressed most of my concerns. I would like to raise my score.