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

Authors: guibin  zhang
haonan  dong
yuchen  zhang
zhixun  li
dingshuo  chen
kai  wang
tianlong  chen
yuxuan  liang
dawei  cheng
kun  wang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-04 17:48:32

Abstract: Training high-quality deep models necessitates vast amounts of data, resulting in overwhelming computational and memory demands. Recently, data pruning, distillation, and coreset selection have been developed to streamline data volume by \textit{retaining}, \textit{synthesizing}, or \textit{selecting} a small yet informative subset from the full set. Among these methods, data pruning incurs the least additional training cost and offers the most practical acceleration benefits. However, it is the most vulnerable, often suffering significant performance degradation with imbalanced or biased data schema, thus raising concerns about its accuracy and reliability in on-device deployment. Therefore, there is a looming need for a new data pruning paradigm that maintains the efficiency of previous practices while ensuring balance and robustness.
Unlike the fields of computer vision and natural language processing, where mature solutions have been developed to address these issues, graph neural networks (GNNs) continue to struggle with increasingly large-scale, imbalanced, and noisy datasets, lacking a unified dataset pruning solution. 
To achieve this, we introduce a novel dynamic soft-pruning method, \ourmethod, designed to update the training ``basket'' during the process using trainable prototypes. \ourmethod first constructs a well-modeled graph embedding hypersphere and then samples \textit{representative, balanced, and unbiased subsets} from this embedding space, which achieves the goal we called {\fontfamily{lmtt}\selectfont \textbf{Graph Training Debugging}}.
Extensive experiments on four datasets across three GNN backbones, demonstrate that \ourmethod (I) achieves or surpasses the performance of the full dataset with $30\%\sim50\%$ fewer training samples, (II) attains up to a $2.81\times$ lossless training speedup, and (III) outperforms state-of-the-art pruning methods in imbalanced training and noisy training scenarios by $0.3\%\sim4.3\%$ and $3.6\%\sim7.8\%$, respectively.

Main paper: 
 introduction: 
 Data-centric AI, though continuously providing high-quality data for upcoming artificial general intelligence [1, 2, 3, 4] , presents a significant hurdle for their on-device deployment during training and inference phases [5, 6, 7, 8] . To democratize existing state-of-the-art methods [9, 10, 9, 11, 12, 13, 14] , considerable efforts are directed toward identifying unbiased and core data within training datasets and conducting troubleshooting to deepen our solid understanding of the intrinsic property of data shcema [15, 16, 17, 18] . To date, data pruning [19, 20, 21, 22, 23] , distillation [24, 25, 26, 27, 28, 29, 30] and coreset selection [31, 32, 33, 16] aim to retain, synthesize or choose a small but informative dataset from original full set. While the sample size undergoes significant reshaping and reduction, methods like dataset distillation inevitably lead to additional training costs [23, 34, 35] . As a hardware-friendly candidate and accelerator for training and inference, data pruning serves as a promising candidate by mitigating the high computational burden. Recent advancements, however, have demonstrated that the efficiency of data pruning may come at a cost-utilizing only a portion of the data can potentially render the model more vulnerable to imbalance or malicious perturbation attacks [37] , which are commonly seen in real-world applications. As illustrated in Figure 1 , we evaluate the performance of the current state-of-the-art data pruning paradigm, In-foBatch [23] , with a pruning ratio of 50%, on MUTAG [38] +GCN [39] under both imbalance and biased scenarios. It can be observed that: ❶ InfoBatch exacerbates the imbalance of training samples during the training process; ❷ In-foBatch efficiently saves training costs in noisefree scenarios, even surpassing the original full dataset performance by 0.7%. However, it encounters significant performance degradation (5.7% ∼ 6.4% ↓) in biased scenarios.In this paper, we primarily focus on graph-level data pruning, aiming to enhance the model's robustness to data imbalance and noise while maintaining the efficiency inherited from traditional data pruning practices. This is because, unlike in computer vision (CV) and natural language processing (NLP) domains, where separate solutions already exist for addressing these issues [37, 23] , graph learning models continue to grapple with increasingly large-scale, imbalanced, and biased datasets [40, 36, 41] . To this end, we first introduce a novel direction in the realm of graph training, termed Graph Training Debugging (GTD), to (dynamically) identify representative, robust, and unbiased subsets for accelerating the training process without compromising performance.We achieve GTD goal by proposing a novel dynamical soft-pruning method, Graph De-Redundancy (GDeR), in which specifically designed to work efficiently and accurately on various GNN architectures. Concretely, GDeR draws inspiration from prototype learning [42, 43] practices, projecting training graph samples onto a hyperspherical embedding space. It utilizes a set of trainable prototypes to regularize the graph embedding distribution, essentially encouraging both inter-class separateness and intra-class compactness. Furthermore, on this well-regularized hypersphere, GDeR generates a sampling distribution that encourages the sampling of under-learned graphs, while excluding those with high outlier risk and belonging to majority clusters. Given a training budget (i.e., pruning ratio), GDeR dynamically maintains a sub-dataset at each epoch, efficiently combating the negative impact of imbalanced and noisy data on the model, simultaneously accelerating training significantly.Broader Impact. In this paper, we present a novel training philosophy GDeR to achieve our defined GTD goal. GDeR dynamically prunes irrelevant graph samples, providing a more comprehensive insight and achieving a triple-win of efficiency, balancing, and robustness. This approach can contribute to a wide range of graph-related applications, accelerating model training while demonstrating great potential in scenarios such as adversarial attacks [44, 45, 45] , imbalanced graph classification [40, 46] , and unsupervised pre-training [47, 48, 49] . We believe GDeR can serve as a benchmark for future research in this area, attracting significant attention and inspiring further exploration into understanding sparsity in other domains such as LLMs.Experimental Observation We validate the GDeR through a comprehensive series of graph-level tasks, across five datasets and three GNN backbones, showcasing that GDeR can: ❶ achieve lossless training performances with 30% ∼ 50% fewer training samples, ❷ achieve a 2.0× lossless speedup on OGBG-MOLHIV, and a 2.81× lossless speedup on pre-training ZINC. ❸ mitigate imbalance issues by achieving a 0.3 ∼ 4.3% ↑ in F1-macro on MUTAG and DHFR datasets, ❹ effectively help outlier-attacked GNNs improve accuracy by 3.5% ∼ 10.2% through data pruning.Limitations & Future Insight. GDeR, as a plug-in to graph training, not only improves efficiency but also ensures robustness and balance throughout the training. However, the applicability of its principles in fields such as CV remains unexplored, limiting the generalizability of data debugging. This represents a direction for future development in our work. 
technical background: 
 Notations Consider an undirected graph G = (V, E), where V represents the node set and E signifies the edges. The feature matrix for the graph is designated as X ∈ R |V|×F . Each node v i ∈ V is associated with a feature vector of F dimensions. The adjacency matrix A ∈ {0, 1} N ×N represents the connectivity between nodes, where A[i, j] = 1 suggests the presence of an edge e ij ∈ E, and 0 indicates no edge. In graph-level training tasks, specifically for graph classification, given a set ofN graphs {G} = {G 1 , G 2 , . . . , G N }, where each graph G i = (V i , E i) is as defined above, and their corresponding labels Y ∈ R N ×C with C being the total number of classes, we aim to learn graph representations H ∈ R N ×d ′ with H[i, :] for each G i ∈ G that effectively predict Y i . Graph Neural Networks (GNNs). GNNs [50, 51] have become pivotal for learning graph representations, achieving benchmark performances in various graph tasks at node-level [52] , edge-level [53] , and graph-level [54] . The success of GNN mainly stems from message-passing mechanism: hEQUATIONHere, L represents the number of GNN layers, where h(0) i = x i , and h (l)i (1 ≤ l ≤ L) denotes the node embedding of v i at the l-th layer. N (v i ) denotes the 1-hop neighbors of v i , and AGGR(•) and COMB(•) are used for aggregating neighborhood information and combining ego/neighborrepresentations, respectively. Finally, a sum/mean pooling operation is commonly used for READOUT function to obtain the graph-level embedding. While promising, the increasing volume of graph samples [55, 19, 56] poses significant computational challenges for both training and pre-training of GNNs. Efficiently accelerating graph-level training remains an unresolved issue. Data Pruning Current data pruning methods can be categorized as static or dynamic [23] . Static data pruning involves heuristic-based metrics or limited training to assess sample importance and perform pruning before formal training, like EL2N [18] and Influence-score [57] . On the other hand, dynamic data pruning dynamically selects different training samples during training [58, 23, 59] , often achieving better results than static pruning. In the graph domain, attempts related to data pruning include edge-level sampling techniques like GraphSAGE [60] and GraphSAINT [61] . However, to the best of our knowledge, there is currently no method specially designed for graph-level data pruning, let alone one that can simultaneously improve the balance and robustness of GNNs. Imbalance in GNNs Deep imbalanced learning has been one of the significant challenges in deep learning [62] . The current mainstream research can be broadly categorized into three approaches:(1) re-sampling [63, 64, 65] , which balances the number of samples from different classes; (2) re-balancing [66, 67, 68] , which adjusts the loss values for samples from different classes; and (3) post-hoc processing [69] , which shifts the model logits based on label frequencies. In the domain of graph learning, most efforts to address the imbalance issue focus on node-level classification imbalances [70, 71, 72] , yet solutions targeting graph-level imbalance are relatively limited. Despite a preliminary attempt [40] , which requires complex up-sampling and regrouping operations, there is still a need for a straightforward yet effective solution to graph imbalance issue. Robustness in GNNs As for robustness learning, many studies showcase graph classification is vulnerable to adversarial attacks [73, 74] . Given a set of training or test graphs, an attacker could perturb the graph structure [75] and/or node features to deceive a graph classifier into making incorrect predictions for the perturbed testing graph. Traditional empirical and certified defenses [76, 77, 78, 79] often involve complex designs and additional components. In this paper, we propose subtle adjustments during training, leveraging prototypes to enhance the robustness of graph training. 
problem formulation: 
 In the classic scenario of graph-level training (not limited to specific tasks like graph classification, regression, or pre-training), given a graph datasetD = {z i } |D| i=1 = {(G i , Y i )} |D| i=1, a GNN encoder is employed to extract graph-level embeddings H = {h i } |D| i=1 for each graph sample, which are then utilized for downstream tasks. The goal of GDeR is to find an oracle function that changes with time (epochs) and can determine the current most representative, balanced, and denoised core subset X t :EQUATIONwhere F t-1 is the selection function at the (t -1)-th epoch. Given a preset sparsity ratio s%, the subset's volume is fixed as The overview of our proposed GDeR. GDeR comprises hypersphere projection, embedding space modeling, sampling distribution formatting, and the final dynamic sampling. We present the dynamic sample selection process of GDeR within one epoch.|X t | = (1 -s)% × |D|.As shown in Figure 2 , given an arbitrary GNN, GDeR selects a training sample set X t within a specified budget for each epoch. At the t-th epoch, after the GNN f θ : X → R E outputs graph embeddings h ∈ R E from the input graph G i with h = f θ (G i ), these are projected into a hyperspherical embedding space via a projector g ϕ : R E → R D . GDeR allocates a set of M trainable prototypesP c = {p c k } K k=1for each class c, with associated losses used to shape the embedding space, ensuring inter-class separation and intra-class compactness. In this regularized space, GDeR formulates a sampling distribution by focusing on samples unfamiliar to the model, excluding those from the majority prototype cluster and with high outlier risk, thereby providing a subset of samples S t+1 for the next epoch. Through this balanced and robust dynamic pruning mechanism, GDeR achieves unbiased graph representations at a significantly lower training cost than the full dataset.At the t-th epoch, GDeR maintains a subset X t with a given budget, where s% = |X t |/|D| is a constant, representing the dataset pruning ratio. Given the feature representations H ∈ R |Xt|×E output by f θ , we first project these features into a hyperspherical embedding space, denoted as z ′ = g ϕ (h), z = z ′ /||z ′ || 2 . This projection has been shown to be beneficial for compactly embedding samples of the same class [80, 81, 82] . The projected embeddings z ∈ R D , which lie on the unit sphere (||z|| 2 = 1), can naturally be modeled using the von Mises-Fisher (vMF) distribution [80, 81] . Here, we first consider the graph classification scenario 1 , in which we allocate K prototypes P c = {p c k } K k=1 for each class c (1 ≤ c ≤ C). Following conventional practices in hyperspherical space modeling [83] , we model a vMF distribution as the combination of a center prototype representation p k and the concentration parameter κ:EQUATIONwhere κ ≥ 0 denotes the tightness around the mean, Z D (κ) represents a normalization factor [83] , exp κp ⊤ k z is called the angular distance and I v is the modified Bessel function of the first kind with order v. In our multi-prototype settings, we model the probability density of a graph embedding z i in class c as follows:EQUATIONFurther, the embedding z i is assigned to class c with the normalized probability as shown above:EQUATION)where τ is a temperature coefficient. Given that we have now allocated a corresponding class for each graph embedding, we aim to further encourage: ❶ allocation correctness, meaning that the allocation should be consistent with the ground truth label; ❷ intra-class compactness, meaning that graph embeddings should be close to the appropriate prototypes belonging to their own class; and ❸ inter-class separateness, meaning that graph embeddings should be distant from prototypes of other classes. To achieve ❶ and ❷ , we have designed the compactness loss below:EQUATIONwhere y i represents the class index for z i . Equation ( 6) is the maximum likelihood estimation ofmax θ,ϕ Π |Xt| i=1 p(y i = c|z i , {{p c k , κ} K k=1 } C j=1 ), which not only boosts the allocation correctness but also enforces graph embeddings to compactly surround the appropriate prototypes. Furthermore, to achieve ❸, namely encouraging inter-class separateness, we design the separation loss, optimizing large angular distances among different class prototypes:EQUATIONwhere 1(•) is an indicator function. Through the above regularization, we obtain C prototype clusters{χ c } C c=1 , each composed of K prototype centers {p k } K k=1and surrounding sample sets {z (C) }. After modeling this hypersphere, we proceed with sample selection on the current subset D (t) .Traditional dynamic dataset pruning methods typically rely on loss-based metrics to select informative subsets [58, 23] , which, however, can make the model more vulnerable to imbalance and malicious perturbation (as discussed in Section 1). In this subsection, while selecting a representative subset D (t) , we also intend to further ensure it is balanced and noise-free. Our first step is to locate samples that are at risk of being outliers in the embedding space. We propose using a prototype-based Mahalanobis distance to estimate the outlier risk of each graph sample:EQUATIONwhere Σ k ∈ R K×K is the sample covariance of all the prototypes in class c. Equation ( 8) calculates the maximum distance of z i to all prototypes within its class, which serves as a robust outlier detection metric [84] . Furthermore, we intend to evaluate the effectiveness of each sample. Given that the distance of an embedding from its cluster center has been shown to be a good indicator of the model's familiarity with it [85] , we compute the distance of each graph sample to its class-specific prototypes as a familiarity metric:EQUATIONwhich suggests that if a graph sample is significantly closer to its own prototypes and farther from those of other classes, the model is more familiar with it. We implement the distance function using the angular distance in Equation (3). When considering the data balancing issue, we formulate the balancing score for each sample z i as follows:EQUATIONwhere ϕ zi (p k ) denotes the closest prototype to z i , and ϕ zi (χ) denotes the prototype cluster that z i currently belongs to. Equation (10) evaluates whether the graph sample z i belongs to a minority from a prototype-cluster perspective. Finally, we assign sampling probabilities to all samples in D (t) :EQUATIONwhere (•) σ represents the Sigmoid transformation. Equation ( 11) is designed to sample with higher probability those samples that the model is less familiar with, have a lower outlier risk, and belong to a minority group. Now, at the t-th epoch, we obtain the final sampling probability distributionP (t) (z) : z∈Xt ω(z)z ω(z) dz dz. Recall that we have (1 -s)% of samples pruned in the t-th epoch, i.e., Xt = D \ X t . For Xt , we use the probability distribution P (t-1) (z) from the (t -1)-th epoch 2 . Specifically, we formulate GDeR's coreset sampling function F t in Equation ( 2) as follows:EQUATIONwhere F t outputs the selected samples X t+1 for the next epoch's training, S(X , P, N ) is a sampling operator that samples N samples from X with probability distribution P, and Ψ(t) ( Ψ(t)) is the scheduler function (with implementation placed in Appendix B.5) that control the number of samples drawn from X t ( Xt ), respectively, subject to the given budgetΨ(t) + Ψ(t) = |D| × s% = |X t |.Optimization Aside from the original task-specific loss of GNN training denoted as L task , GDeR has additionally introduced L comp and L sepa . The overall training objective of GDeR is formulated as:EQUATIONwhere λ 1 and λ 2 are co-efficient adjusting the relative importance of two losses. We conclude the algorithm workflow table of GDeR in Appendix C.Extension Finally, we advocate that GDeR is not limited to graph classification but can also be seamlessly adapted to tasks such as graph regression and graph pre-training. The key distinction between these tasks and graph classification is that each graph sample does not have a ground truth class index, which makes ground truth class-based calculations, such as those in Equations ( 6) and ( 7), infeasible. One straightforward approach is to manually set M virtual classes, using the class assigned by Equation ( 5) as the graph sample's current class. However, this may result in prototypes and hyperspherical embeddings that do not accurately reflect the underlying clustering distribution [86] .To address this, we leverage ProtNCELoss [43] as a self-supervised signal, providing a more reliable reflection of the data's structure. Detailed implementation can be found in Appendix D. 
experiments: 
 In this section, we conduct extensive experiments to answer the following research questions: (RQ1) Can GDeR effectively boost GNN efficiency (under both supervised and unsupervised settings)? (RQ2) Does GDeR genuinely accelerate the GNN training? (RQ3) Can GDeR help alleviate graph imbalance? (RQ4) Can GDeR aid in robust GNN training?We test GDeR on two widely-used datasets, MUTAG [38] and DHFR [87] ; two OGB large-scale datasets, OGBG-MOLHIV and OGBG-MOLPBCA [88] ; one large-scale chemical compound dataset ZINC [89] . Following [40] , we adopt a 25%/25%/50% train/validation/test random split for the MUTAG and DHFR under imbalanced scenarios and 80%/10%/10% under normal and biased scenarios, both reporting results across 20 data splits. For OGBG-MOLHIV and OGBG-MOLPBCA, we use the official splits provided by [88] . For ZINC, we follow the splits specified in [90] . We choose three representative GNNs, including GCN [91] , PNA [92] and GraphGPS [90] . Detailed dataset and backbone settings are in Appendices B.1 and B.2.The hyperparameters in GDeR include the temperature coefficient τ , prototype count K, loss-specific coefficient λ 1 and λ 2 . Practically, we uniformly set K = 2, and tune the other three by grid searching: τ ∈ {1e-3, 1e-4, 1e-5}, λ ∈ {1e-1, 5e-1},λ ∈ {1e-1, 1e-5}. Detailed ablation study on hyperparameters is placed in Section 4.5. Obs.❶ GDeR achieves maximum graph pruning with performance guarantees. As shown in Tables 1 and 2 , GDeR consistently outperforms both static or dynamic baselines under various pruning ratios. For instance, on OGBG-MOLHIV+PNA, GDeR experiences only a 0.5% performance decay even with 80% pruning, surpassing the current state-of-the-art method In-foBatch, which suffers a 1.7% decay. When pruning 50% and 30% of the data, GDeR even achieves performance improvements of 0.1% and 0.5%, respectively.Obs.❷ The degree of redundancy varies across different datasets. We observe that OGBG-MOLPCBA is more sensitive to pruning than OGBG-MOLHIV, which suggests the degree of redundancy varies between datasets. For example, when pruning 80% of the data, GraphGPS on OGBG-MOLPCBA exhibits a performance decay ranging between 3.5% ∼ 13.9%, significantly higher than the 2.5% ∼ 11.5% decay observed on OGBG-MOLHIV. However, as the remaining ratio increases, GDeR quickly recovers and surpasses the full dataset performance by 0.2% at the 50% pruning level. To answer RQ3, we tested GDeR in extremely imbalanced scenarios and compared its performance with other dynamic pruning methods. Following [40] , we randomly set 25%/25% graphs as training/validation sets and within each of them, we designate one class as the minority class and reduce the number of graphs for this class in the training set (while increasing the others) until the imbalance ratio reached 1:9, which creates an extremely imbalanced scenario. The reported metrics are the average of 50 different data splits to avoid bias from data splitting. We observe from Figure 4 that: Obs. ❹ GDeR can effectively mitigate imbalance issues. As observed in Figure 4 , baseline pruning methods struggle to outperform "no-pruning" GCN, resulting in substantial losses in speedup efficacy. In contrast, GDeR offers a more meaningful pruning approach. For instance, on DHFR, pruning 50% of the data results in a 4.3%improvement in F1-Macro. This demonstrates that GDeR not only saves computational resources but also effectively mitigates data imbalance issues.DHFR DHFR MUTAG MUTAGTest Accuracy (%)10% NoisePruning Settings (%) Noise Settings (%) We divide RQ4 into two sub-questions: (1) Is GDeR more robust to outlier perturbation compared to previous data pruning methods? (2) Can GDeR compete with mainstream methods designed to enhance GNN robustness? In practice, following [36] , we introduce perturbations to k% of the graph samples in the training set by adding Gaussian noise to the node features of the selected graphs. We compare GDeR against both data pruning baselines and GNN robustness enhancement baselines. The experimental results are presented in Figure 5 , and we observe:Obs. ❺ GDeR is a resource-saving GNN robustness booster. From Figure 5 (Left), we observe that GDeR effectively counters noise perturbation, outperforming the GNN under outlier attacks at both 30% and 50% pruning rates. Notably, InfoBatch, which performed competitively in RQ1, suffers a significant performance drop (2.0% ∼ 6.1% ↓) in this biased training scenario, which is likely due to its loss magnitude-based sample selection mechanism, inadvertently amplifying the negative impact of high-loss outlier samples on the model. From Figure 5 (Right), we conclude that GDeR performs as well as or better than current robust GNN plugins, and it shows the most significant improvement in accuracy, with increases of 3.6% and 7.8% at noise ratios of 5% and 30%, respectively. 11), with the other two variants defined similarly. We observe from Table 3 that ❶ removing any component leads to a performance drop for GDeR, while removing ω b in the imbalance scenario or ω r in the biased scenario results in the most significant impact; ❷ GDeR w/o ω e consistently underperforms across all scenarios, indicating that selecting highly representative samples is fundamental to the success of dynamic pruning methods. We investigate the impact of K, on the performance and efficiency of GDeR. Specifically, we vary K ∈ {1, 2, 4} on OGBG-MOLHIV+GraphGPS and observe changes in performance and per-epoch time. We observe from Table 4 that K = 1 leads to an under-learning of the hypersphere, resulting in consistently lower performance. While K = 4 shows a marginal performance gain compared to K = 2, for efficiency considerations, we opt for K = 2 across all experiments. Additionally, we observe that data pruning significantly saves per-epoch time, with s = 20 resulting in per-epoch times being 40% ∼ 60% of those achieved with s = 70. 
conclusion & future work: 
 In this work, we propose the graph training debugging concept and explore soft dataset pruning in the graph learning area for the first time. Particularly, we present a prototype-guided soft pruning method, termed GDeR, which initially establishes a well-modeled graph embedding hypersphere and subsequently samples representative, balanced, and noise-free subsets from this embedding space, debugging and troubleshooting graph processing. In the future, we plan to extend this concept to the CV realm, aiming to expedite the process of image training and provide efficient insights for the development of high-quality visual large-scale models.[115] Junnan Li, Pan Zhou, Caiming Xiong, and Steven Hoi. Prototypical contrastive learning of unsupervised representations. In International Conference on Learning Representations, 2021. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes]Justification: we have specified all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results (See Appendix B).Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes] Justification: In this paper, we have reported the standard deviation of the experiments (See Experiments).Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. Justification: In this paper, we provide detailed information about the experimental resources, including GPU configurations used in our studies (See Appendix).Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes]Justification: We have provided the societal impacts of the work (See Introduction).Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: This paper does not address issues related to this aspect.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: All creators and original owners of the assets used in our paper, such as code, data, and models, have been properly credited. We have explicitly mentioned the licenses and terms of use for each asset and have ensured full compliance with these terms throughout our research.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [NA] Justification: The research presented in this paper is not concerned with new assets.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA] Justification: This paper does not involve experiments or research related to human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA] Justification: This paper does not address potential risks incurred by study participants.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: We conclude the commonly used notations throughout the manuscript in Table 5 .Table 5 : The notations that are commonly used in the manuscript.Notation DefinitionG = {V, E} = {A, X} Input graph A Input adjacency matrix X Node features D = {zi} |D| i=1 = {(Gi, Yi)} |D| i=1Graph embedding for Gi f θ GNN encoder g ϕ Feature projector The graph dataset details are summarized in Table 6 . P c = {p c k } K k=1 Total KWe choose three representative GNNs, including one classic message-passing network GCN [91] , one classical graph classification backbone PNA [92] and a graph transformer backbone GraphGPS [90] .For GCN, we simply set layer_num = 3 and hidden_dim = 128. For PNA, we set layer_num = 4, and hidden_dim = 64, edge_dim = 16. The rest configurations are the same as provided by [92] (https://github.com/lukecavabarrett/pna/blob/master/ models/pytorch_geometric/example.py). For GraphGPS, we uniformly set hidden_dim = 64, pe_dim = 8 and utilize random walk encoding, performer [101] , and GINE [102] as the positional encoding, attention module and the local convolutional module, respectively. The rest configurations are the same as provided by the PyTorch library (https://github.com/pyg-team/pytorch_ geometric/blob/master/examples/graph_gps.py). All the experiments are conducted on NVIDIA Tesla V100 (32GB GPU), using PyTorch and PyTorch Geometric framework.As for static pruning methods, we first introduce Hard Random, which conducts a random sample selection before training. Influence [57] and EL2N [18] are two classical static pruning methods that prune samples based on Influence-score and EL2N-score, respectively. DP [100] conducts pruning with consideration of generalization. Following the methodology of [23] , we introduce a total of 13 static data pruning methods. These methods select a core set of data via predefined score functions or heuristic knowledge. Additionally, we introduce three dynamic pruning methods, including ϵ-greedy [58] , UCB [58] , and InfoBatch [23] . Following [58, 23] , we also introduce the dynamic pruning baseline, termed Soft Random, which conducts random selection in each epoch.For MUTAG and DHFR, the metrics used vary across different scenarios. In the normal (Section 4.2) and biased (Section 4.4) scenarios, we use accuracy. However, in the imbalanced scenario (Section 4.3), accuracy does not faithfully reflect the performance for the minority group. Following previous works in imbalanced classification [71] , we choose to use F1-macro, which computes the accuracy independently for each class and then takes the average, treating different classes equally. For OGBG-MOLHIV and OGBG-MOLPCBA, we use ROC-AUC and Average Precision (AP), following [88] .Ψ(t) and Ψ(t) are scheduler functions that determine the proportions of samples in X t+1 originating from X t and Xt , respectively. For simplicity, we adopt the Inverse Power function [103] :EQUATIONwhere ς denotes the initial ratio and κ is the decay factor controlling the rate at which the ratio decreases over intervals. In practice, we uniformly set ς = 0.7 and κ = 2.The algorithm framework is presented in Algo. 1.In this section, we will explain how to extend GDeR beyond traditional graph classification tasks to more complex scenarios like graph regression and graph pre-training. As noted in Section 3.5, tasks such as graph pre-training do not have ground truth class indices, making direct application of GDeR, which relies on true class labels in Equations ( 6) and ( 7), infeasible.A straightforward approach is to assign C virtual classes, each with K prototypes P c = {p c k } K k=1 . During prototype allocation, we use the probability distribution provided by Equation ( 5) to determine Algorithm 1: Algorithm workflow of GDeRInput :Graph datasets D = {z i } |D| i=1 = {(G i , Y i )} |D| i=1 , the number of epochs T , GNN encoder f θ , feature projector g ϕ , Initialized M prototypes {p (C) k } M i=1 for class C for epoch t ← 1 to T do /* Extract graph-level embedding and Projection */ X t ← current training set. for sample index i ← 1 to |X t | do Compute graph embedding h i ← g θ (G i ).Project graph embedding onto hypersphere byz i = z ′ /||z ′ || 2 , z ′ = g θ (h i ). end Determine which prototype cluster χ c each graph sample z i corresponds to;▷ Eq. 5 /* Formatting sampling distribution */ Calculate the outlier score ω r (z i ) by prototype-based Mahalanobis distance;▷ Eq. 8 Calculate the familiarity score ω e (z i ) based on prorotype-sample distance;▷ Eq. 9 Calculate the balancing distribution ω b based on cluster volume;▷ Eq. 10Formulate sampling distribution ω(z i ) = ω σ e (zi) (ω σ r (zi)+ϵ)•(ω σ b (zi)+ϵ) ;▷ Eq. 11 /* Dataset sampling */ Initialize the sample set for the (t + 1)-th epoch X t+1 ← ∅ /* Sample from currently remained set */ X t+1 ← X t+1 + S X t , P (t-1) (z), Ψ(t) /* Sample from currently pruned set */X t+1 ← X t+1 + S Xt , P (t-1) (z), Ψ(t) /* Standard GNN training */ Compute loss L GDeR = L task + λ 1 • L comp + λ 2 • L sepa ;▷ Eq. 13 Backpropagate to update the GNN model f θ , projector g ϕ , and prototypes. end the class of each graph sample:EQUATIONWe then substitute ỹi for y i in Equations ( 6) and ( 7), essentially emphasizing that the sample z i should cluster tightly around its assigned prototype cluster χ ỹi and remain distant from other clusters. However, this approach is prone to error accumulation: if a sample is initially misclassified, L comp and L sepa will erroneously encourage it to continue moving in the wrong direction. To address this issue, we draw inspiration from previous practices in prototypical contrastive learning and leverage the prototypical contrastive loss [43] :EQUATIONwhere ϕ calculates the concentration level of the feature distribution around a prototype as defined in [43] . Equation ( 16) has been shown to learn cluster distributions with high mutual information with ground truth labels in unsupervised settings. It encourages samples to migrate between clusters by measuring a concentration-weighted contrastive signal, rather than accumulating current errors. Thus, the overall objective of GDeR becomes:EQUATIONWe applied this setting when extending GDeR to pre-training with GraphMAE on the ZINC dataset, with the experimental results in Table 7 .Table 7 : Graph pre-training performance of GDeR on GraphMAE [47] +ZINC15 [104] . Following [47] , the model is first pre-trained in 2 million unlabeled molecules sampled from the ZINC15, and then finetuned in 3 classification benchmark datasets contained in MoleculeNet [105] . We place additional results about MUTAG and DHFR in Table 8 , and the GraphMAE+ZINC pre-training results in Table 7 .Constrastive Learning and Prototypical learning Contrastive representation learning methods consider each sample as a unique class, aligning multiple views of the same input while distancing other samples. This significantly improves the discriminative power of the learned representations, allowing these methods to excel in learning robust feature representations across unsupervised [106, 107, 108, 109, 110] , semi-supervised [111] , and supervised settings [81] . The foundational properties and effectiveness of contrastive loss within hyperspherical space have been extensively studied [80, 112] . Other approaches focus on learning feature representations by modeling the relationships between samples and cluster centroids [113] or prototypes [114] . Building on contrastive learning, [115] incorporates prototypical learning, adding a contrastive mechanism between samples and prototypes obtained through offline clustering. PALM [82] utilizes prorotypical learning for out-of-distribution (OOD) identification, which automatically identifies and dynamically updates prototypes, and assigns each sample to a subset of prototypes via reciprocal neighbor soft assignment weights. However, all these methods are not conducive to a more lightweight training burden, and our method is the first attempt at leveraging prototype learning for soft data pruning.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes] Justification: For the datasets disclosed in the article, we have provided information regarding their sources and origins (See Appendix).Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.Justification: The study presented in this paper conforms to the NeurIPS Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).The extension of GDeR to broader scenarios will be detailed in Section 3.5For the first epoch, we set P (t-1) (z) as uniform distribution. 


Decision: Despite the fact that there has been a good number of data pruning techniques aiming at saving the neural network training computation costs, it seems that no one has explored the application of data pruning techniques for graph-level data in graph neural network training.

This paper, for the first time, systematically evaluated quite a few data pruning techniques that have been previously used for computer vision or NLP tasks on pruning graph-level datasets, specifically focusing on accelerating neural network training, mitigating the dataset (class) imbalance issue, and improving neural network robustness in the presence of adversarial attacks. The paper found that all the existing methods being tested in the paper display issues in training efficiency, imbalanced learning, and robustness learning. Based on these findings, the paper proposed a new data pruning method "Graph De-Redundancy" (GDeR) and demonstrated superior performance in all the three aspects than the other baseline methods. Specifically, GDeR adds additional modules to GNN to project the intermediate data sample feature representation vector to hyperspherical embedding space with learnable center prototype representations for each class in the dataset and encourages intra-class compactness and inter-class separations. Using the learned hyperspherical embeddings, a data sampling method that considers sample anomaly, familiarity, and balance was proposed for soft-pruning (sampling) dataset to accelerate training. The GDeR method has set up a good baseline for future data pruning techniques that primarily focus on graph-level data pruning.

While the paper has conducted systematic evaluations and set up a good baseline for this specific direction for the first time, there are a few items that might worth taking into consideration for further improvements.

1. There are typos or unannotated symbols in the equations. Even if the reader might be able to guess what they are, we have to ensure the correctness and clarity of the paper anyway. For example, what is $k$ and $\mathcal{N}$ in the Equation 1? What is $I$ and $d$ in the Equation 3? Please proof reading all the mathematical equations and their annotations in the paper, ensuring there is no error.
2. The novelty of the proposed GDeR method has not been described in detail in the paper. GDeR works on feature embeddings after all. It has been inspired by many other previous works on representation learning and data coreset selection. The paper should provide references to the equations related to the previous work. For example, even though I cannot fully remember where the source is, I am pretty sure I have seen previous representation learning works that encourage intra-class compactness and inter-class separations for learned embeddings of different classes. Of course, the paper should also highlight the key technical distinctions and innovations in GDeR comparing to the previous works.
3. The paper has done a tremendous amount of work evaluating the previous data pruning methods on graph-level data pruning, for the first time. These work should be mentioned and emphasized in the key locations of the paper, including the abstract, to motivate the proposal of the new GDeR method.
4. Need to clarify or fix "there is currently no method for graph-level data pruning" in line 119. This is a very strong statement and shall not confuse the readers. All the methods presented in this paper can be used for graph-level data pruning, it's just never been systematically tested for it.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: (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: 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?
limitations: limitations: The limiations are discussed in the paper.
paper_summary: paper_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.
strength_weakness: strength_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?
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: 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?
limitations: limitations: The authors have adequately discussed the limitations.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: 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?
limitations: limitations: Yes

Comments: title: Response
comment: We are glad that our rebuttal has effectively addressed you concerns! We are still open to any further questions you may have :)
I read the replies, which addressed most of my concerns. I would like to raise my score.
We extend our heartfelt thanks to Reviewer zhEK for their increased support and recognition of our paper! We are pleased that our revisions and rebuttal have addressed the concerns!
Thank you for your response. Introducing ImageNet experiments and complexity analysis is persuasive and effectively showcases GDeR's adaptability. Personally, I appreciate the contribution of this work, and with its proper packaging and open-sourcing, it can become a widely applicable training acceleration technique. Therefore, I have adjusted my rating accordingly.