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 2024 poster (2024)
Keywords: data pruning
graph pruning
graph neural networks
Primary area: graph_neural_networks

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.

GDeR: Safeguarding Efficiency, Balancing, and Robustness via Prototypical Graph Pruning
Guibin Zhang 112 Haonan Dong"), Yuchen Zhang", Zhixun Li", Dingshuo Chen', Kai Wang", Tianlong Chen'. Yuxuan Liang', Dawei Cheng" Kun Wang
TToggii Univerity, "Shanghai AI Laboratory, "CUHK, *UCAS,
NUS, UNC-Chapel Hill, "HKUST (Guangzhou) NNUU Equal Contribution, Corresponding author dcheng@tongjii.o .dd. en, vk620559ujh@gmaill.
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 retaining, synthesizing, 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, 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 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 novel dynamic soft-pruning method, GDeR, designed to update the training "basket" during the process using trainable prototypes. GDeR first constructs well- medeeed graph embedding hypersphere and then samples representative, balanced, and unbiased subsets from this embedding space, which achieves the goal we called Graph Training Debugging. Extensive experiments on five datasets across three GNN backbones, demonstrate that GDeR (I) achieves surpasses the performance of the full dataset with 30% 50% fewer training samples, (II) attains up to a 2.81 x lossless training speedup, and (III) outperforms state-of-the-art pruning methods in imbalanced training and noisy training scenarios by 0.3% ~ 4.3% and 3.6% ~ 7.8%, respectively. The source code is available https: // github...... com/ www.mssnnnm/maaammmmm
1 Introduction
Data-centric AI, though continuously providing high-quality data for upcoming artificial general
intelligence [1, 2, 4], presents significant hurdle for their on-device deployment during training and inference phases [5, 6, 7, 8J. To democratize existing state-of-the-an methods [9, 10, 1, 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 sheema [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 promising candidate by mitigating the high computational burden.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Recent advancements, however, have demon- strated that the efficiency of data pruning may come at a cost- cost-utilizing only a portion of the data can potentially render the model more vulnerable to imbalance or malicious perturba- tion attacks [37]. which are commonly seen in real-world applications. As illustrated in Fig- ure I, we evaluate the performance of the cur- rent -fate-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: O InfoBatch exacerbates the imbalance of train- ing samples during the training process; @ In- foBatch efficiently saves training costs in noise- free scenarios, even surpassing the original full dataset performance by 0.7%. However, it en- counters significant performance degradation (5.7% 6.4% L) in biased scenarios.
(a) Imbalanced Scenario
(2:1
J.A.
10.0%
Original
Epoch 100
Epoch 200
Epoch 300
(b) Biased Scenario
96.3
GOX
(Oang)
j0
+GaloBanch
74.5
Noddon 800
Roton 50%
Figure I: (a) We report the label distribution of the training set retained by InfoBatch at pruning ratios of 50% in the {0, 100, 200,300) 300}-th epochs. The gray, light blue and dark blue represent pruned, mi- nority, and majority samples, respectively. (b) Per- formance comparison between InfoBatch and our GDeR when introducing outliers (following [36]) into (0%, 10%, 20%} of the training set.
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 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), (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 Re-Redundancy (GDeR), in which specifically designed to work efficiently and accurately on various GNN archi- tectures. Concretely, GDeR draws inspiration from prototype learning [42, 43] practices, projecting training graph samples onto a hyperspherical embedding space. It utilizes 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 lnder-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 novel training philosophy GDeR to achieve our defined GTD goal. GDeR dynamically prunes irrelevant graph samples, providing a more comprehensive insight and achieving triple-win of efficiency, balancing, and robusiness. 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- 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: 1 achieve lossless training performances with 30% ~ 50% fewer training samples, @ achieve 2.0x lossless speedup on OGBG-MOLHIV, and a 2.81 x lossless speedup on pre-training ZINC. @ mitigate imbalance issues by achieving a 0.3 ~ 4.3% 1 in F1-macro on MUTAG and DHFR datasets, O 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 direction for future development in our work.

---

2 Technical Background
Notations Consider an undirected graph 9 = (V,E), where V represents the node set and E signifies the edges. The feature matrix for the graph is designated as X E RiV xF, Each node v; E V is associated with a feature vector of F dimensions. The adjacency matrix A E {0, 1 represents the connectivity between nodes, where A
suggests the presence of edge 6ij E E, and O indicates no edge. In graph-level training tasks, specifically for graph classification, given a set of N graphs {9} (2,,9,.... ....... Gr., where each graph G. = (V* E+ is as defined above, and their corresponding labels Y E RRNCC with C' being the total number of classes, we aim to learn graph representations H E Nxd' with :[i for each G E G that effectively predict Y,
Graph Neural Networks (GNNs). GNNs [50, 51] have become pivotal for learning graph represen- tations, 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 ceassage-passingg mechanism:
h (1) COMB h (1-1), (h) (1 (1-1), my E((a))) 0 OSISI.
(1)
Here, L. represents the number of GNN layers, where h.o) Xs, and (1 PISIS SIS de- notes the node embedding of v, at the 1-th layer. ((ss) denotes the 1-hop neighbors of Us and AGGR(.) and COMB(.) are used for aggregating neighborhood information and combining ego/neighbor- representations, respectively. Finally, 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 metries 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 method specially designed for graph-level data pruning. let alone one that can simultancously 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-sumpling [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, 721, 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 need for straightforward yet effective solution to graph imbalance issue.
Robustness in GNNs As for robustness learning, many studies showcase graph classification vulnerable to adversarial attacks [73, 74]. Given 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.
3 Methodology
3.1 Problem Formulation
In the classic scenario of graph-level training (not limited to specific tasks like graph elassification, regression, or pre-training), given a graph dataset D = { = (G., Y.) a GNN encoder is employed to extract graph-level embeddings H (hh
[ 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 X4
Ne = F [D, (b. (2( 1.1))
(2)
where Fi-1 is the selection function at the (1- 1) epoch. Given a preset sparsity ratio 8%, the subset's 's volume is fixed as | = (1 3)% x [D]
3

---

Inter-class
Outher assessment
Belanced Sampling
Clustering
Protofype
Robuninss
(ppoda 21
U.X,
bER
Rygengheical
Projector.
Visualization
Outller Assessment
Dienrbaation 2%)o
Efficiency
IL
Luroa
Graph Neural
Regalario
Balanced Weighting
Sumple
Sacpk-b 10 993
Network
Embodiings
9pd
|1||
LL
c++1
Famillarity Futeeing
Mathodology Target
Robust
Pi
Efficient
Dynamic Pruning
Class-cnndtsoned Prototypes
Figure 2: 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.
3.2 Overview of the Proposed Method
As shown Figure given arbitrary GNN, GDeR selects training sample set X, within a specified budget for each epoch. At the (-th epoch, after the GNN fo X - R outputs graph embeddings E from the input graph G3 with h (G.). these are projected into a hyperspherical embedding space via projector 96 RR + R.. GDeR allocates a set of M trainable prototypes P === { for each class with associated losses used to shape the embedding space, ensuring inter-class separation and intra-class compactness. In this regularized space, GDeR formulates sampling distribution by focusing on samples unfamiliar to the model, excluding those from the majority prototype cluster and with high outlier risk, thereby providing subset of samples S for the next epoch. Through this balanced and robust dynamic pruning mechanism, GDeR achieves unbiased graph representations a significantly lower training cost than the full dataset.
3.3 Projection onto Hyperspherical Embedding Space
At the t-th epoch, GDeR maintains a subset & with a given budget, where s% = /x/l/|Di is a constant, representing the dataset pruning ratio. Given the feature representations H E R |x output by fo. first project these features into hyperspherical embedding space, denoted as z ga (h), z' 2/||z'|| 2. This projection has been shown to be beneficial for compactly embedding samples of the same class [80, 81, 82]. The projected embeddings R which lie the unit sphere (||z|| 1), can naturally be modeled using the von Mises-Fisher (vMF) distribution [80, 81]. Here, we first consider the graph classification scenario in which allocate K prototypes P = {p for each class e (1 S < C). Following conventional practices in hyperspherical space modeling [83], we model a vMF distribution as the combination center prototype representation p and the concentration parameter N:
pn P&, x) (n)))exp))))) (spTz), ZD(k) K
D/2-1
D/2 1
where K 2. 0 denotes the tightness around the mean, (D( represents normalization factor [83], exp (wpp z) called the angular distance and I, is the modified Bessel function of the first kind with order In multi-prototype settings, we model the probability density of graph embedding 2; in class e as follows:
K Plz;:P R) Σ (x()) exp(xpf 2z),
(4)
'The extension of GDeR broader scenarios will be detailed in Section 3.5

---

Further, the embedding is assigned to class e with the normalized probability as shown above:
Ex ZD (D(K) ex 2i/T)
ply e 25 ()))) Σj 2 exp(p).- z,/T)
(5)
where 7 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 O inter-class separateness, meaning that graph embeddings should be distant from prototypes of other classes. To achieve 1 and @ have designed the compactness loss below:
2
K (D( exp(p) Z1/T)
Comp
log
(6)
X
E (K') exp(p zz/T)
where represents the class index for z, Equation (6) is the maximum likelihood estimation of Xt maxe, の pl clz,, {(p K ( 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:
C Σ log C 1m
Lueaa C
c-12
1
exp(p/2:/T)
k=1
where (-) is an indicator function. Through the above regularization, we obtain C' prototype clusters fxele-1 1, each composed of K prototype centers {px k== | and surrounding sample sets (z(C)) }. After modeling this hypersphere, we proceed with sample selection on the current subset D(())
3.4 Efficient, Balanced and Robust Graph Debugging
Traditional dynamic dataset pruning methods typically rely on loss-based metrics to select informative subsets [58, 233. which, however, can make the model more vulnerable to imbalance and malicious perturbation (as discussed in Section 1). In this subsection, while selecting representative subset D(O), 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:
wx(2:) = min - Ly max [iz, - Pi) Σx (z, - -P0) I
(8)
where Σg E IR K is the sample covariance of all the prototypes in class c. Equation (8) calculates the maximum distance of z, to all prototypes within its class, which serves a robust outlier detection metric [84]. Furthermore, we intend to evaluate the effectiveness of each sample. Given that the distance of embedding from its cluster center has been shown be good indicator of the model's familiarity with it [85], we compute the distance of each graph sample to its class-specific prototypes as familiarity metric:
K k= dist(p) -h 2;)
We (z:)
Σ Lezy, dist(p
which 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, as follows:
(b,),) = z: min (ost (px). 2.)) / (x))1.
{
(10)
where dz, (Px) denotes the closest prototype to 2,, and de, (x) denotes the prototype cluster that z; currently belongs to. Equation (10) evaluates whether the graph sample 2; belongs minority from prototype-cluster perspective. Finally, we assign sampling probabilities all samples in D(t);
5

---

we (wp (z:) + +)) (ug (zi) + +))
w(z:)
(11)
where (.)0 represents the Sigmoid transformation. Equation (11) is designed to sample with higher probability those samples that the model is less familiar with, have lower outlier risk, and belong to minority group. Now, at the (-th epoch, we obtain the final sampling probability distribution
(z) SREX, [ dz. Recall that we have (1 (1-s)8 3)% of samples pruned in the t-th epoch,
w(2)
i.., & = -D \ Xy. For L, we use the probability distribution (z) from the (t - 1)-th epoch ? Specifically, we formulate GDeR's coreset sampling function Fr in Equation (2) follows:
Fi = S (4,
v(1) Us ((t (z), (())
(12)
where Ft outputs the selected samples X441 for the epoch's 's training, S(X, P,N) is sampling operator that samples N samples from X' with probability distribution P. and (() (t)) is the scheduler function (with implementation placed in Appendix B.5) that control the number of samples
drawn from Xe (Z;), respectively, subject to the given budget (f) + (t) [D] x s% = (&)..
3.5 Optimization and Extension
Optimization Aside from the original task-specific loss of GNN training denoted as Lunks GDeR has additionally introduced Leomp and Liuepa The overall training objective of GDeR is formulated as:
CEDER
Lusk + A1 Coomp + X2- Csepa:
(13)
where d and x2 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 '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 Loss [43] as self-supervised signal, providing a more reliable reflection of the data's structure. Detailed implementation can be found in Appendix D.
4 Experiments
In this section, we conduct extensive experiments 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?
4.1 Experiment Setup
Datasets and Backbones We test GDeR on two widely-used datasets, MUTAG [38] and DHFR [87]; two OGB large-scale datasets, OGBI-MOLHIV and OGBG-MOLPBCA [88]; one large-scale chemical compound dataset ZINC [89]. Following [40], we adopt a 25% 25%/25%/50g train/validation/tesl random split for the MUTAG and DHER under imbalanced scenarios and 80%//0%%/10% under normal and biased scenarios, both reporting results across 20 data splits. For OGBG-MOLHIV and OGBG- MOLPBCA, 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. and B.2.
Parameter Configurations The hyperparameters in CDeR include the temperature coefficient т, prototype count K, loss-specific coefficient X; and Ag- Practically, we uniformly set K 2, and tune the other three by grid searching: 7 E (le-3, 3, le-4, 4, le 5). A E [1e-1,5e-11] E (1e-1,le-5} Detailed ablation study on hyperparameters placed in Section 4.5.
For the first epoch, we set ((t-1)(z) uniform distribution.

---

Table I: Performance comparison to state-of-the-an dataset pruning methods when remaining {20%, 30%, 50%, 70%) of the full set. All methods are trained using PNA, and the reported metrics represent the average of five runs.
Dataset
OGRG-MOLHIV (ROC-AUC1)
OGBG-MOLPCBA (AP f)
Remaining Ratio %
20
30
50
70
20
30
50
70
Hard Random
72.1
72.4
73.5
75.6.0.7
20.5 JT.6
22.9.5.a
24.7.s.4
28.0
CD [93]
71.9
72.6.3.7
73.8 12.5
15.9.0.4
19.8 18.3
22.6_5.5
23.7
27.8
Herding [94]
63.0
64.9
66.8
75.2
12.4
14.0
15.5
21.8
K-Means [95]
61.5_14.8
65.9.10.4
69.5
74.7
18.5_o.6
23.4
23.2.4.9
27.6.0.5
Least Confidence [96]
72.1
12.4.0.9
75.6.0.7
75.9.0.4
21.0.7.1
23.4_4.7
25.0.a.1
27.8
Margin [96]
72.9
71.3
75.1
76.0.o.a
20.2
23.3,4.8
25.0.a.1
28.3r0.2
Statie
Forgetting [33]
72.6.a.7
73.0ga.a
J3.9
75.7.0.6
20.7
23.1_a.0
24.1.4.0
27.9.0.2
GraNd-4 [18]
68.5
J2.7
73.8
75.7.0.6
20.2.7.9
22.9
25.0.a.1
28.0.o.1
GraNd-20 [18]
74.7.1.6
74.0
g4.9
J5.9.0.4
21.2.6.9
23.8
24.9.3.2
27.8
DeepFool [97]
41.9.4.4
72.5
73.0g3.3
75.6.0.7
19.3
22.7.6.4
24.0.4.1
27.7.0.4
Craig [98]
71.8.4.5
72.3
73.5
76.0
20.5
23.1_s.0
24.7.a.4
27.8
Glister [99]
73.3 j3.0
14.4
75.0
J6.2.0.1
20.6
23.4 .3.4
25.0.a.1
27.9 L0.2
Influence [57]
71.5
42.7
g3.5
75.2.1.1
19.7
22.3 _2.3
23.9
27.2.0.9
EL2N-2 [33]
73.0
74.5
75.0
76.1
20.9 L7.2
23.5 4..6
24.3 J9.8
27.6 600.6
DP [100]
72.1
73.5
74.7
76.0go.s
20.0
22.7
24.6
27.7 20.4
Dynamic
Soft Random
74.3
73.9
76.1
76.2.o.a
22.7 22.7.5.4
24.8
27.0.1.1
27.8,0.3
e-greedy [58]
73.8
73.612.7
75.610.7
76.2.o.a
24.0.4.1
27.1 25.3.2.6
27.6.0.5
UCB [58]
73.8 j3.8
73.7 J2.6
75.0
75.8
23.9
25.8
26.6.1.6
28. 18.00
InfoBatch [23]
74. j2.1
74.0
76.3
76.3
24. g4.1
24.8
27.3
28.3
GDeR
75.8 1o.5
76.0 1o.3
76.4
76.8
24.8 (33
26.0 2.1
28.0
28.5
Whole Dataset
76.
28. 2..3
4.2
GDeR makes GNN training way faster
To answer RQI and RQ2, we comprehensively compare GDeR with fourteen widely-used static pruning methods and three dynamic pruning methods, as outlined in Table with more detailed explanations in Appendix B.3. Following [23], we add hard random and soft random pruning as baselines for a more comprehensive comparison. Specifically,
set the dataset remaining ratio (1 - ()=8)% E (20%, 30,, 50%, 70%)- The performance results are shown in Tables 1, 2 and 7 and the efficiency comparisons are in Figure Our observations (Obs.) are as summarized follows:
Obs. 1 GDeR achieves maximum graph prun- ing with performance guarantees. As shown in Tables 1 and 2, GDeR consistently outper- forms 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, sur- passing the current state-of of-te-of-thh-arr method In- foBatch, which suffers a 1.7% decay. When
75
Accuracy (%)
pruning 50% and 30% of the data, GDeR even achieves performance improvements of 0.1% and 0.5%, respectively.
Vanilla
z3-
H-Random
Margin
Obs.e The degree of redundancy varies across different datasets. We observe that OGRG-MOLPCE, more sensitive to pruning than OGBG-MOLHIV, which suggests the de- gree of redundancy varies between datasets. For example, when pruning 80% of the data, GraphGPS on OGBG-MOLPCBA exhibits a per- formance decay ranging between 3.5% 13.9%, significantly higher than the 2.5% ~ 11.5% decay observed on OGBG-MOLHIV. However, the remaining ratio increases, GDeR quickly recovers and surpasses the full dataset performance by 0.2% at the 50% pruning level.
72
DP
S-Random
UCB
InfoBatch
(Ours)
100%
90%
70%
80%
40%
30%
Per Epoch Time (ogbn-molhiv)
Figure 3: The trade-off between per epoch time and ROC-AUC (%) of data pruning methods. Specifically, we report the test performance when pruning methods achieve per epoch times of (90%, 70%, 50%,40% 40%, 30%) of the full dataset training time. "Vanilla" denotes the original GNN backbone without any data pruning.
7

---

Table 2: Performance comparison to state-of-the dataset pruning methods. All methods are trained using GraphGPS, and the reported metrics represent the average of five runs.
Dataset
MOLHIY (ROC-AUC 1)
OGBG-MOLPCBA (AP f)
Remaining Ratio %
20
30
50
70
20
30
Random
19.3
72.7.6.0
73.4_n.a
75.6,a.1
19.4,7.8
11.7
23.9
26.3
CD [93]
72.6,6.1
73.0.n.7
75.3
16.7
18.0
20.7
21.7
26.4.o.s
Herding [94]
69,5
73.3.6.4
74.5
15.
13.3 113.9
14.0
17.8
23.0,4.2
K-Center [95]
67.2
70.8_
72.6.a.1
73.9 LA.8
16.9 10.3
19.4.7.8
22.8
26.1
Least Confidence [96]
73.9 14.8
74.2.4.6
75.8
77.3
19.4
21.9 15.3
23.5 13.7
26.0,1.2
Margin [96]
74.0 p4.7
74.4_4.8
75.8.2.9
77.5 11:2
18.8 18.4
21.5 15.7
23.9
27.0,0.2
Forgetting [33]
74.2 14.5
74.8_ _9.9
75.6.a.1
76.9 11.8
18.3 19.9
21.915.3 15.3
23.3|3.9
26.8
Static
GraNd-4 [18]
73.8 14.9
74.2.4.5
_5.3
77.5 11:2
19.0
21.3,5.9 15.9
23.6,3.6
26.9 1o.3
DeepFool [97]
16.5
_3.3_5.4
74.9.0.8
75.5
17.6
21.9.5.3 15.3
23.2
26.5 j0.7
Craig [98]
13.5
74.4.4.8
76.0.2.7
77.9 1o.8
(0.9
18.7 18.7 18.5
14.5
24.5j2.7
27.1
Glister [99]
73.615.1
74.0.4.7
75.8.2.9
18.0
19.9
22.5 14.7
24.8
27.0g0.2
Influence [57]
72.9 15.8
73.7.8.0
74.8
17.4
17.7
21.9 15.3
23.5
26.6.0.6
EI.2N-20 [33]
74.0,4.7
75.5_a.2
76.9.1.
77.7 11.0
19.1 19.1
22.9 14.3
24.0
26.0
DP [100]
72.0 16.7
74.1
76.0_2.7
76.9.1.8
19.6
21.5g5.7
24.942.8
26.4.0.8
Dynamic
Soft Random
|4.0
74.4 74.1
78.1
21.5 16.7
22.4
26.0
27.1
6-greedy [58]
14.7
76.6.2. 74.9_a.8
78.6 (0.1
22.8 (4.4
23.1
26.3
27.0.0:2
UCB [58]
15.5
76.3 74.9.a.8
23.7 j8.0
24.1
26.5
27.2
InfoBatch [23]
75.0
75.6
g7.
18.5
23.5
24.6
26.7.o.o
27.2
GDeR
76.5
76.9,1.
78.7
79.1
|3.4
g4.5
27.4
27.6704
Whole Datasct
78.7
27.2.002
Obs. @ GDeR can significantly accelerate GNN training. Figure illustrates the per-epoch time and corresponding performance of each pruning method compared to full dataset training OGBG- NOLHIV+GraphGPS. is evident that GDeR can achieve 2.0x speedup without any performance loss (corresponding to 50% per-epoch time). Even with a significant 3.3x speedup, GDeR only experiences a moderate drop of 0.9%, which is superior to baselines including InfoBatch by a margin of 1.1% ~ 4.2%. Additionally, we observe from Table 7 that pretraining ZINC with only 30% of the data leads to a 1.53% ROC-AUC improvement, with 2.81 x training time acceleration.
4.3 GDeR Mitigates Graph Imbalance
To answer RQ3, we tested GDeR in extremely imbalanced scenarios and compared its performance with other dynamic pruning methods. Following [40], randomly set 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 avoid bias from data splitting. We observe from Figure 4 that:
DHFR
MUTAO
To Peanttnn Hagis Siluddrs oce Glub (Dum
NUTRO
No Pranttt
Hugis
F1 Macro 10
FioMocro
Fl Macaoo
Macro
Glih (Dam
Ho RoPoniag
Iroaigg Worple
Kandees
lakibarch
Gbock (Dunt)
Imbbalane Railo (Prune 80%)
Imbaltnne Baño (Prusc 80%)
Imbrllancc Retso (Prune 80%)
Imbalkaice Ratio (Prune 20%)
Figure 4: Performance comparison of different pruning methods across various imbalance ratios. We utilize MUTAG and DHFR datasets with GCN, and reported the metrics when adjusting the imbalance ratios among [1:9, 3:7, 5:5, 7:3, 9:1). "No Pruning" denotes training GCN without dataset pruning.
Obs. 4 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 more meaningful pruning approach. For instance, on DHIR, pruning 50% of the data results in a 4.3% impr in F1-Macro. This demonstrates that GDeR not only saves computational resources but also effectively mitigates data imbalance issues.
8

---

4.4
GDeR Aids in GNN Robustness
28
H-Random
S-Random
InfoBatch
83
Origital DrepEdge
GRAND
CDaR-305
Craig
GDelt
0000
GDeB-10%
Test Accuracy (%)
79-
10% Noise
22
15
69
63
30%
Pruze
5% Noian
10% 20% Nossn
30%
Pruning Settings (%)
Noise Settings (%)
Figure 5: (Left) We report the performance of several top-performing pruning methods when perturbation noise is added to 10% of the training set of MUTAG. The black dashed line represents the original GNN performance without pruning. (Right) We compare GDeR with DropEdge and GRAND under different noise settings, utilizing GDeR with pruning ratios of 10% and 30%.
We divide RQ4 into two sub-questions: (1) 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 1% 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. 6 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 both 30% and 50% pruning rates. Notably, InfoBatch, which performed competitively in RQ1, suffers significant performance drop (2.0% ~ 6. 6.1% 4) in this biased training scenario, which is likely due to its loss magnitude-basee 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 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.
4.5 Ablation & Sensitivity Study
Ablation Study To evaluate the effectiveness of the different modules in GDeR, we propose three variants: (1) GDeR w/o We, (2) GDeR w/o wy, and (3) GDeR w/o wb. GDeR w/o we represents removing We from Equation (11), with the other two variants defined similarly. We observe from Table that removing any component leads to a performance drop for GDeR, while removing W; in the imbalance scenario or w, in the biased scenario results in the most significant impact; @ GDeR w/o we consistently underperforms across all scenarios, indicating that selecting highly representative samples is fundamental to the success of dynamic pruning methods.
Setting
Normal
Imbalance
Raised
Ratio (s%)
Metric
K =
K =
K =
CDeR
24.21
76
27.84
Perf.
75.811.5
76.5
76.110.9
GDeR wlo wie
79.77
73.784299
75.60
20%
Time
15.32
16.44
17.16
CDeR
way
81.0113.09
46.2113-2
77.9613.18
Porf.
78.2+1.4
78.7+1.3
78.9+0.29
GDeR wio
83.4612.50
52
75.0212.05
50%
Time
19.97
20.18
22,08
Table 3: Ablation study on GDeR and its three variants. "Imbalance" refers to setting the imbal- ance ratio be {1 9), and "Noisy" refers adding 5% noise to the training set. All metrics are reported under 30% pruning ratio.
70%
Perf.
81.1942.0
79.1+1.0
79.2 79.2+2.2
Time 26.19
31.30
39.55
Table 4: Sensitivity analysis on K. We report the ROCAUC (%) and per-epoch time (s) on OCRG-MMOLHHVAAGrpIiGPSS
Sensitivity and Efficiency Analysis We investigate the impact of K, on the performance and and observe
efficiency of GDeR. Specifically, we vary K (1, 4) on OCBG-MOLIIV-GraphcPS changes in performance and per-epoch time. We observe from Table 4 that K = 1 leads to an under-learning of the hypersphere, resulting consistently lower performance. While K = 4 shows 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 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, present prototype-guided soft pruning method, termed GDeR, which initially establishes 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 expedite the process of image training and provide efficient insights for the development of high-quality visual large-scale models.
Acknowledgement
Dawei Cheng is supported by the National Natural Science Foundation of China (Grant No. 62102287). Yuxuan Liang is supported by the National Natural Science Foundation of China (No. 62402414), Guangzhou Municipal Science and Technology Project (No. 2023A03J001I) and Guangdong Provincial Key Lab of Integrated Communication, Sensing and Computation for Ubiquitous Internet of Things (No. 2023B1212010007,
References
[1] Mohammad Motamedi, Nikolay Sakharnykh, and Tim Kaldewey, A data-centric approach for training deep neural networks with less data. arXiv preprint arXiv:2110.03613. 2021.
[2] Daochen Zha, Zaid Pervaiz Bhat, Kwei-Herng Lai, Fan Yang, Zhimeng Jiang. Shaochen Zhong, and Xia Hu. Data-centric artificial intelligence: A survey. arXiv preprint arXiv:2303. 10158, 2023.
[3] Luciano Floridi and Massimo Chiriatti. Gpt-3: Its nature, scope, limits, and consequences. Minds and Machines, 30:681 1-94, 2020.
[4] Guohao Li, Hasan Hammoud, Hani Itani, Dmitrii Khizbullin, and Bernard Ghanem. Camel: Communicative agents for" mind" exploration of large language model society, Advances in Neural Information Processing Systems, 36, 2024.
[5] Elias Frantar and Dan Alistarh. Sparsegpt: Massive language models can be accurately pruned in one-shot. In International Conference on Machine Learning, pages 10323-10337 PMLR. 2023.
[6] Salch Ashkboos, Maximilian L Croci, Marcelo Gennari do Nascimento, Torsten Hoefler, and James Hensman. Slicegpt: Compress large language models by deleting rows and columns. arXiv preprint 2.kiv:2401.15024 2024.
[7] Mingjie Sun, Zhuang Liu, Anna Bair, and J Zico Kolter. A simple and effective pruning approach for large language models. arXiv preprint arXiv:2306. 1695, 2023.
[8] Victor Sanh, Thomas Wolf, and Alexander Rush. Movement pruning: Adaptive sparsity by fine-tuning, Advances in neural information processing systems, 33:20378-20389 2020.
[9] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint 2300::2307.09288, 2023.
[10] Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, al. Gpt-4 technical report. arXiv preprini urXiv:2303. 087774 2023.
[11] Junke Wang, Dongdong Chen, Chong Luo, Xiyang Dai, Lu Yuan, Zuxuan Wu, and Yu-Gang Jiang. Chatvideo: A tracklet-centric multimodal and versatile video understanding system, 2023.
10

---

[12] Jun Chen, Deyao Zhu, Xiaoqian Shen, Xiang Li, Zechu Liu, Pengchuan Zhang, Raghuraman Krishnamoorthi, Vikas Chandra, Yunyang Xiong, and Mohamed Elhossein.. Minigpt-v2. large language model as unified interface for vision-language multi-task learning. arXiv preprint arXiv:211009477. 2023.
[13] Deyao Zhu, Jun Chen, Xiaoqian Shen, Xiang Li, and Mohamed Elhoseiny. Minigpt-4: Enhancing vision-language understanding with advanced large language models. arXiv preprint arXiv:2304. 10592, 2023.
[14] Sihan Chen, Handong Li, Qunbo Wang, Zijia Zhao, Mingzhen Sun, Xinxin Zhu, and Jing Liu. Vast: A vision-audio-subbitle--- omni-modality foundation model and dataset, 2023.
[15] Bojan Karlak, David Dao, Matteo Interlandi, Bo Li, Sebastian Schelter, Wentao Wu, and Ce Zhang. Data debugging with shapley importance over end-to-end machine learning pipelines, 2022.
[16] Jae-hun Shim, Kyeongho Kong, and Suk-Ju Kang. Core-set sampling for efficient neural architecture search. arXiv preprint (cXiv:2107006866 2021.
[17] Murad Tukan, Alaa Maalouf, and Dan Feldman. Coresets for near-convex functions. Advances Neural Information Processing Systems, 33:997-1009, 2020.
[18] Mansheej Paul, Surya Ganguli, and Gintare Karolina Dziugaite. Deep learning on data diet: Finding important examples early in training. Advances in Neural Information Processing Systems, 34:20596-20677, 2021.
[19] Guibin Zhang, Kun Wang, Wei Huang, Yanwei Yue, Yang Wang, Roger Zimmermann, Aojun Zhou, Dawei Cheng, Jin Zeng, and Yuxuan Liang. Graph lottery ticket automated. In The Twelfth International Conference on Learning Representations, 2024.
[20] Kun Wang, Yuxuan Liang. Xinglin Li, Guohao Li, Bernard Ghanem, Roger Zimmermann, Huahui Yi, Yudong Zhang, Yang Wang, et al. Brave the wind and the waves: Discovering robust and generalizable graph lottery tickets. IEEE Transactions on Pattern Analysis and Muchine Intelligence, 2023.
[21] Guibin Zhang, Yanwei Yue, Kun Wang, Junfeng Fang. Yongduo Sui, Kai Wang, Yuxuan Liang, Dawei Cheng, Shirui Pan, and Tianlong Chen. Two heads are better than one: Boosting graph sparse training via semantic and topological awareness, 2024.
[22] Ravi S Raju, Kyle Daruwalla, and Mikko Lipasti. Accelerating deep learning with dynamic data pruning. arXiv preprint S.Ni::211..162.1 2021.
[23] Ziheng Qin, Kai Wang, Zangwei Zheng, Jianyang Gu, Xiangyu Peng, Zhaopan Xu, Daquan Zhou, Lei Shang, Baigui Sun, Xuansong Xie, et al. Infobatch: Lossless training speed up by unbiased dynamic data pruning. arXiv preprint arXiv:2303. 04947, 2023.
[24] Bo Zhao and Hakan Bilen. Dataset condensation with distribution matching. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pages 6514-6523, 2023.
[25] Kai Wang, Bo Zhao, Xiangyu Peng, Zheng Zhu, Shuo Yang, Shuo Wang, Guan Huang, Hakan Bilen, Xinchao Wang, and Yang You. Cafe: Learning to condense dataset by aligning features. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 12196-12205, 2022.
[26] George Cazenavette, Tongzhou Wang, Antonio Torralba, Alexei A Efros, and Jun-Yan Zhu. Dataset distillation by matching training trajectories. In Proceedings of the IEFF/CVF Confer- ence on Computer Vision and Puttern Recognition, pages 4750 4759, 2022.
[27] Timothy Nguyen, Roman Novak, Lechao Xiao, and Jaehoon Lee. Dataset distillation with infinitely wide convolutional networks. Advances in Neural Information Processing Systems, 14:5186-5199 1021.
11

---

[28] Xinglin Li, Kun Wang, Hanhui Deng, Yuxuan Liang, and Di Wu. Attend who is weak: Enhanc- ing graph condensation via cross-free adversarial training, arXiv preprint arXiv:2311.1577.. 2023.
[29] Yuchen Zhang, Tianle Zhang, Kai Wang, Ziyao Guo, Yuxuan Liang, Xavier Bresson, Wei Jin, and Yang You. Navigating complexity: Toward lossless graph condensation via expanding window matching. In Forty-first International Conference on Machine Learning, 2024.
[30] Tianle Zhang, Yuchen Zhang, Kun Wang, Kai Wang, Beining Yang. Kaipeng Zhang, Wenqi Shao. Ping Liu, Joey Tianyi Zhou, and Yang You. Two trades is not baffled: Condense graph via crafting rational gradient matching. arXiv preprint arXiv:2402.04P4 044444440444 2024.
[31] Sariel Har-Peled and Soham Mazumdar. On coresets for k-means and k-median clustering. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pages 291-300, 2004.
[32] Ke Chen. On coresets for k-median and k-means clustering in metric and euclidean spaces and their applications. SIAM Journal on Computing, 39(3):22-9947, 2009.
[33] Mariya Toneva, Alessandro Sordoni, Remi Tachet des Combes, Adam Trischler, Yoshua Bengio, and Geoffrey J Gordon. An empirical study of example forgetting during deep neural network learning, arXiv preprint
2018.
[34] Bo Zhao, Konda Reddy Mopuri, and Hakan Bilen. Dataset condensation with gradient matching. arXiv preprint arXiv:2006.08 05929, 2020.
[35] Yao Lu, Xuguang Chen, Yuchen Zhang, Jianyang Gu, Tianle Zhang, Yifan Zhang, Xiaoniu Yang, Qi Xuan, Kai Wang, and Yang You. Can pre-trained models assist in dataset distillation? arXiv preprint arXiv:2310.03225,, 2023.
[36] Zenan Li, Qitian Wu, Fan Nie, and Junchi Yan. Graphde: A generative framework for debiased learning and out-of-distributtin detection on graphs. Advances in Neural Information Processing Systems, 35:30277-30290, 2022.
[37] Dongmin Park, Scola Choi, Doyoung Kim, Hwanjun Song, and Jae-Gil Lee. Robust data pruning under label noise via maximizing re-labeling accuracy, Advances in Neural Information Processing Systems, 36, 2024.
[38] Asim Kumar Debnath, Rosa L Lopez de Compadre, Gargi Debnath, Alan J Shusterman, and Corwin Hansch. Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. J. Med.
Chem., 34(2):78623)) 79777, 1991.
[39] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks, 2016.
[40] Yu Wang, Yuying Zhao, Neil Shah, and Tyler Derr. Imbalanced graph classification via graph-of-graph neural networks. In Proceedings the 31 ACM International Conference on Information & Knowledge Management, pages 2067-2076, 2022.
[41] Zhixun Li, Yushun Dong, Qiang Liu, and Jeffrey Xu Yu. Rethinking fair graph neural networks from re-balancing. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 1736-1745, 2024.
[42] Sercan O Arik and Tomas Pfister. Protoattend: Attention-based prototypical learning. Journal of Machine Learning Research, 21(210):1-35, 2020.
[43] Junnan Li, Pan Zhou, Caiming Xiong, and Steven CH Hoi. Prototypical contrastive learning of unsupervised representations. arXiv preprint arXiv:2005.0m 04966006666 2020.
[44] Judy Hoffman, Eric Tzeng, Taesung Park, Jun-Yan Zhu, Phillip Isola, Kate Saenko, Alexei Efros, and Trevor Darrell. Cycada: Cycle-consistent adversarial domain adaptation. In International conference machine learning, pages 1989-1998. Pmlr, 2018.
12

---

[45] Yi-Hsuan Tsai, Wei-Chih Hung, Samuel Schulter, Kihyuk Sohn, Ming Ming-Hsuan Yang, and Manmohan Chandraker. Learning to adapt structured output space for semantic segmentation. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 7472-7481, 2018.
[46] Shirui Pan and Xingquan Zhu. Graph classification with imbalanced class distributions and noise. In IJCAI, pages 1586-1592, 2013.
[47] Zhenyu Hou, Xiao Liu, Yukuo Cen, Yuxiao Dong, Hongxia Yang. Chunjie Wang, and Tang. Graphmae: Self-supervised masked graph autoencoders. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 594-604, 2022.
[48] Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. Advances in neural information processing systems, 33:5812-5888 2020.
[49] Yuning You, Tianlong Chen, Yang Shen, and Zhangyang Wang. Graph contrastive learning automated. In International Conference on Machine Learning, pages 12121-12132. PMLR, 2021.
[50] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE transactions neural networks and learning systems, 32(1):4-22 2020.
[51] Jie Zhou, Ganqu Cui, Shengding Hu. Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications. Al open, 1:57-811 81,-8,122 2020.
[52] Shunxin Xiao, Shiping Wang, Yuanfei Dai, and Wenzhong Guo. Graph neural networks in node classification: survey and evaluation. Machine Vision and Applications, 33(1):4, 2022.
[53] Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. In Proceedings of NIPS, 2018.
[54] Chuang Liu, Yibing Zhan, Jia Wu, Chang Li, Bo Du, Wenbin Hu, Tongliang Liu, and Dacheng Tao. Graph pooling for graph neural networks: Progress, challenges, and opportunities. arXiv preprint arXiv:2204.0733 2022.
[55] Kun Wang, Yuxuan Liang, Pengkun Wang. Xu Wang, Pengfei Gu, Junfeng Fang. and Yang Wang. Searching lottery tickets in graph neural networks: A dual perspective. In The Eleventh International Conference on Learning Representations, 2022.
[56] Dingshuo Chen, Yanqiao Zhu, Jieyu Zhang, Yuanqi Du, Zhixun Li, Qiang Liu, Shu Wu, and Liang Wang. Uncovering neural scaling laws in molecular representation learning. Advances Neural Information Processing Systems, 36, 2024.
[57] Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In Proceedings of the 34th International Conference on Machine Learning-Volume Volume 70, pages 1885-1894. JMLR. org, 2017.
[58] Ravi S Raju, Kyle Daruwalla, and Mikko Lipasti. Accelerating deep learning with dynamic data pruning, 2021.
[59] Dingshuo Chen, Zhixun Li, Yuyan Ni, Guibin Zhang, Ding Wang, Qiang Liu, Shu Wu, Jeffrey Xu Yu, and Liang Wang. Beyond efficiency: Molecular data pruning for enhanced generalization. arXiv preprint arXiv:2409.0I1 2024.
[60] Yongduo Sui, Xiang Wang, Tianlong Chen, Xiangnan He, and Tat-Seng Chua. Inductive lottery ticket learning for graph neural networks. 2021.
[61] Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graphsaint: Graph sampling based inductive learning method. arXiv preprint arXiv:1907.049311 2019.
13

---

[62] Yifan Zhang, Bingyi Kang. Bryan Hooi, Shuicheng Yan. and Jiashi Feng. Deep long-tailed learning: A survey. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2023.
[63] Haibo He and Edwardo A Garcia. Learning from imbalanced data. IEEE Transactions on knowledge and data engineering, 21(9):1233-1284 2009.
[64] Nitesh Chawla, Kevin W Bowyer, Lawrence Hall, and W Philip Kegelmeyer. Smote: synthetic minority over-sampling technique. Journal of artificial intelligence research, 16:321- 357, 2002.
[65] Bingyi Kang, Saining Xie, Marcus Rohrbach, Zhicheng Yan, Albert Gordo, Jiashi Feng, and Yannis Kalantidis. Decoupling representation and classifier for long-tailed recognition. arXiv preprint arXiv: 1910.0927. 2019.
[66] Tsung-Yo Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár. Focal loss for dense object detection. In Proceedings of the IEEE international conference on computer vision, pages 2980-2988, 2017.
[67] Yin Cui, Menglin Jia, Tsung-Yi Yi Lin, Yang Song, and Serge Belongie. Class-balanced loss based on effective number of samples. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 9268-9277, 2019.
[68] Jingru Tan. Changbao Wang. Buyu Li, Quanquan Li, Wanli Ouyang, Changging Yin, and Junjie Yan. Equalization loss for long-tailed object recognition. In Proceedings of the IEEE/CVF conference computer vision and pattern recognition, pages 11662-11671, 2020.
[69] Aditya Krishna Menon, Sadeep Jayasumana, Ankit Singh Rawat, Himanshu Jain, Andreas Veit, and Sanjiv Kumar. Long-tail learning via logit adjustment. arXiv preprint arXiv:2007.07314 2020.
[70] Min Shi, Yufei Tang, Xingquan Zhu, David Wilson, and Jianxun Liu. Multi-class imbalanced graph convolutional network learning. In I/CAI, 2020.
[71] Tianxiang Zhao, Xiang Zhang, and Suhang Wang. Graphsmote: Imbalanced node classification on graphs with graph neural networks. In WSDM, 2021.
[72] Liang Qu, Huaisheng Zhu, Ruiqi Zheng, Yuhui Shi, and Hongzhi Yin. Imgagn: Imbalanced network embedding via generative adversarial graph networks. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 1390-1398, 2021.
[73] Jiaqi Ma, Shuangrui Ding, and Qiaozhu Mei. Towards more practical adversarial attacks on graph neural networks. Advances in neural information processing systems, 33:4756-4766, 2020.
[74] Dingyuan Zhu, Ziwei Zhang, Peng Cui, and Wenwu Zhu. Robust graph convolutional networks against adversarial attacks. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pages 1399-1407, 2019.
[75] Zhixun Li, Xin Sun, Yifan Luo, Yanqiao Zhu, Dingshuo Chen, Yingtao Luo, Xiangxin Zhou, Qiang Liu, Shu Wu, Liang Wang, et al. Gslb: The graph structure learning benchmark. Advances in Neural Information Processing Systems, 36, 2024.
[76] Yizheng Chen, Yacin Nadji, Athanasios Kountouras, Fabian Monrose, Roberto Perdisci, Manos Antonakakis, and Nikolaos Vasiloglou. Practical attacks against graph- clustering. In Proceedings of the 2017 ACM SIGSAC conference computer and communications security, pages 1125-1142, 2017.
[77] Binghui Wang, Meng Pang, and Yun Dong. Turning strengths into weaknesses: A certified robustness inspired attack framework against graph neural networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 16394-16403, 2023.
[78] Han Yang, Binghui Wang, Jinyuan Jia, et al. Graphguard: Provably robust graph classi- fication against adversarial attacks. In The Twelfth International Conference on Learning Representations, 2023.
14

---

[79] Zaixi Zhang, Jinyuan Jia, Binghui Wang, and Neil Zhenqiang Gong, Backdoor attacks to graph neural networks. In Proceedings of the 26th ACM Symposium on Access Control Models and Technologies, pages 15-26, 2021.
[80] Tongzhou Wang and Phillip Isola. Understanding contrastive representation learning through alignment and uniformity on the hypersphere. In Proceedings of ICML, 2020.
[81] Prannay Khosla, Piotr Teterwak, Chen Wang, Aaron Sarna, Yonglong Tian, Phillip Isola, Aaron Maschinot, Ce Liu, and Dilip Krishnan. Supervised contrastive learning. Advances in neural information processing systems, 33: 8661-18673, 2020.
[82] Haodong Lu, Dong Gong, Shuo Wang, Jason Xue, Lina Yao, and Kristen Moore. Learning with mixture prototypes for 2024.
detection. arXiv preprint arXiv:2402.02633,
[83] Xuefeng Du, Gabriel Gozum, Yifei Ming, and Yixuan Li. Siren: Shaping representations for detecting out-of-distribttion objects. Advances Neural Information Processing Systems, 35:20434-20449, 2022.
[84] Vikash Sehwag, Mung Chiang, and Prateek Mittal. Ssd: A unified framework for self- supervised outlier detection. arXiv preprint arXiv:2103, 12051, 2021.
[85] Amro Abbas, Evgenia Rusak, Kushal Tirumala, Wieland Brendel, Kamalika Chaudhuri, and Ari S Morcos. Effective pruning of web-scale datasets based on complexity of concept clusters. arXiv preprint arXiv:2401.0453 04578, 2024.
[86] Hichem Frigui and Olfa Nasraoui. Unsupervised learning of prototypes and attribute weights. Pattern recognition, 3763)5677-81, 2004.
[87] Jeffrey Sutherland, Lee A O' O'brien, and Donald F Weaver. Spline-fitting fittinn with a genetic algorithm: A method for developing classification structure- activity relationships. J Chem Inform Comput Sci, 43(6), 2003.
[88] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.006 00687, 2020.
[89] John J Irwin, Teague Sterling, Michael M Mysinger, Erin S Bolstad, and Ryan G Coleman. ZINC: free tool to discover chemistry for biology. Journal of Chemical Information and Modeling, 52(7): 1757-178,, 2012.
[90] Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for a general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems,
2022.
[91] Thomas N. Kipf and Max Welling. Semi-Supervised Classification with Graph Convolutional Networks. In Proceedings of the 5th International Conference on Learning Representations, 2017.
[92] Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. Advances in Neural Information Processing Systems, 33: 13660-11-3,,,, 2020.
[93] Sharat Agarwal, Himanshu Arora, Saket Anand, and Chetan Arora. Contextual diversity for active learning. In ECCV, pages 137-153. Springer, 2020.
[94] Max Welling. Herding dynamical weights learn. In ICMLg, pages 1121-1128, 2009.
[95] Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: core-set approach. In ICLR, 2018
[96] Cody Coleman, Christopher Yeh, Stephen Mussmann, Baharan Mirzasoleiman, Peter Bailis, Percy Liang, Jure Leskovee, and Matei Zaharia. Selection via proxy: Efficient data selection for deep learning. In ICLR, 2019.
15

---

[97] Melanie Ducoffe and Frederic Precioso. Adversarial active learning for deep networks: margin based approach. arXiv preprint vrxiv:1802.09844/ 2018.
[98] Baharan Mirzasoleiman, Jeff Bilmes, and Jure Leskovec. Coresets for data-efficient training of machine learning models. In ICML. PMLR, 2020.
[99] Krishnateja Killamsetty, Durga Sivasubramanian, Ganesh Ramakrishnan, and Rishabh Iyer. Glister: Generalization based data subset selection for efficient and robust learning, In Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
[100] Shuo Yang, Zeke Xie, Hanyu Peng, Min Xu, Mingming Sun, and Ping Li. Dataset pruning: Reducing training data by examining generalization influence. In The Eleventh International Conference on Learning Representations, 2023.
[101] Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, et al. Rethinking attention with performers. arXiv preprint arXiv:2009. 14794, 2020.
[102] Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. arXiv preprint arXiv: 1tt.ii995..222.... 2019.
[103] Michael Zhu and Suyog Gupta. To prune, or not to prune: exploring the efficacy of pruning for model compression. arXiv preprint arXiv:1710.01878, 2017.
[104] Teague Sterling and John J Irwin. Zinc 15-ligand discovery for everyone. Journal of Chemical Information and Modeling, 55(1 1):2324-2337, 2015.
[105] Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh Pappu, Karl Leswing, and Vijay Pande. MoleculeNet: A benchmark for molecular machine learning. Chemical Science, 9()):113-530) 2018
[106] Zhirong Wu, Yuanjun Xiong, Stella X Yu, and Dahua Lin. Unsupervised feature learning via non- non-parametric instance discrimination. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3733-3742, 2018.
[107] Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. arXiv preprint arXiv:
2018.
[108] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In Proceedings of CVPR, 2020.
[109] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. International conference on machine learning, pages 1725-1735. PMLR, 2020.
[110] Joshua David Robinson, Ching Yao Chuang, Suvrit Sra, and Stefanie Jegelka. Contrastive learning with hard negative samples. In International Conference on Learning Representations, 2021.
[111] Mahmoud Assran, Mathilde Caron, Ishan Misra, Piotr Bojanowski, Armand Joulin, Nicolas Ballas, and Michael Rabbat, Semi-supervised learning of visual features by paraametttrr predicting view assignments with support samples. In Proceedings of the IEEE/CVF Interna- tional Conference on Computer Vision, pages 8443-8452, 2021.
[112] Feng Wang and Huaping Liu, Understanding the behaviour of contrastive loss. In Proceedings of the IEEE/CVF conference computer vision and pattern recognition, pages 2495-2504, 2021.
[113] Mathilde Caron, Piotr Bojanowski, Armand Joulin, and Matthijs Douze. Deep clustering for unsupervised learning of visual features. In Proceedings of the European conference computer vision (ECCV), pages 132-149, 2018
[114] Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few-shot learning. Advances in neural information processing systems, 30, 2017.
16

---

[115] Junnan Li, Pan Zhou, Caiming Xiong, and Steven Hoi. Prototypical contrastive learning of unsupervised representations. In International Conference on Learning Representations, 2021.
Appendices
Notations
We conclude the commonly used notations throughout the manuseript in Table 5.
Table 5: The notations that are commonly used in the manuseript.
Notation
Definition
9 (V,8) {A
Input graph
A
Input adjacency matrix
X
Node features
D
(2: 1
(99, Y.)
Graph datasets
h
Graph embedding for
fo
GNN encoder
Do
Feature projector
p {
Total K Prototypes for class
X
Remained training set the t-th epoch
&
Pruned training the f-th epoch
2, E RDD
Projected embedding G:
w+(2))
Outlier risk assessment metric
(2:)
Sample familiarity matric Sample balancing score Sampling probability for Scheduler function that controls how many samples choose from N Scheduler function that controls how many samples to choose from X'+1
(2:)
(2x.
(1)
(t)
B Experimental Details
B.1 Dataset Details
The graph dataset details are summarized in Table 6.
Table 6: Graph datasets statistics.
Dataset
#Graph
#Node
# #Edge
# #Classes
Metric
MUTAG
188
17.93
19.79
2
Accuracy/F1-macro
DIIR
756
42.43
44.54
2
Accuracy/Fl-macro
OGBG-MOLHIV
41,127
25.5
27.5
40
ROC-AUC
OGBG-MOLPCBA
437,929
26.0
28.1
2
Average Precision
ZINC15
70,100
50.5
564.5
10
Accuracy
17

---

B.2 Backbone Settings
We choose three representative GNNs, including one classic passage-passinng network GCN [91], one classical graph classification backbone PNA [92] and a graph transformer backbone GraphGPS [90]. For GCN, we simply set layer layer_num num = and hidden_din layer_noe
128. For PNA, we set 4, and hidden dim = 64, edge_din = 16. The rest configurations are the same as provided by [92] (https://s) thub. models/pytore wwwtorrchgemeeteeeeeeeeeee gww.etricicciooo eemmmerraeeaeeeeeeeeeeeeee py). For GraphGPS, we uniformly set bidden_diin = 64, pe_dimm 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: //gi com/ coom/pyg-teen teeam pytooch_ geometric/ httbb/lbb///s//eeeeee /ww./r/s/ee//////eaa////e/aeeeee / examples, esm graph__ps .py). All the experiments are conducted on NVIDIA Tesla V100 (32GB GPU), using Py PyTorch and PyTorch Geometric framework.
B.3 Pruning Baselines
As for static pruning methods, we first introduce Hard Random, which conducts random sample selection before training. Influence [57] and EL.2N [18] are two classical static pruning methods that prune samples based on Influence-scon and EL22-score, respectively. DP [100] conducts pruning with consideration
generalization. Following the methodology of [23], we introduce total of 13 static data pruning methods. These methods select core set of data via predefined score functions or heuristic knowledge. Additionally, we introduce three dynamic pruning methods, including e-gredyy [58], UCB [58], and InfoBatch [23]. Following [58, 23]. also introduce the dynamic pruning baseline, termed Soft Random, which conducts random selection in each epoch.
B.4 Metries
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, the imbalanced scenario (Sec- tion 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-MGOR MOLHIV and OGBG-MOLPCBA, we use ROC-AUC and Average Precision (AP), following [88].
B.5 Scheduler Function
(t) and (t) are scheduler functions that determine the proportions of samples in X'++1 originating from Xr and X2, respectively. For simplicity, we adopt the Inverse Power function [103]:
(t) 1.21- (1-
t
(
| (t)
(14)
where s 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 x = 2.
C Algorithm Workflow
The algorithm framework is presented in Algo. 1.
D Extension of GDeR
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- pre-training do not have ground truth class indices, making direct application of GDeR, which relies true class labels in Equations (6) and (7), infeasible.
straightforward approach to assign C virtual classes, each with K prototypes P { During prototype allocation, use the probability distribution provided by Equation (5) to determine
18

---

Algorithm 1: Algorithm workflow of GDeR
Input
GGraph datasets D 12 {(9,, Y.) the number of epochs T, GNN encoder
fa, feature projector 9
Initialized M prototypes (P(()) J for class for epoch ( to 7 do
/* Extract graph-level embedding and Projection
X2 current training set.
for sample index +- to [e] do
Compute graph embedding h, + go (G.).
Project graph embedding onto hypersphere by 2; z'/1|z'112 z' go (h.).
end
Determine which prototype cluster Xe each graph sample 2; corresponds to;
Eq.
/* Formatting sampling distribution
*/
Calculate the outlier score wr(z;) by prototype-based Mahalanobis distance;
Eq. 8
Calculate the familiarity score we (2,) based on prorotype-sampi distance; Calculate the balancing distribution wb based on cluster volume;
Eq.
& Eq. 10
Formulate sampling distribution wz.))
we (x.)
Eq 11
(a)) (2.())) (c.)+e)
/* Dataset sampling
/
Initialize the sample set for the (1 + 1)-th epoch X4+1 <
/* Sample from currently remained set
*/
1 X S p(t))) vi)))
/* Sample from currently pruned set
*/
X,+1 X+11 S &g p(t-1) (1))
/* Standard GNN training
*/
Compute loss CoDeR = Lask + A1 Loomp + X2 Cxepai
D Eq. 13
Backpropagate to update the GNN model for projector Is. and prototypes.
end
the class of each graph sample:
J = argmaa. p(y: = c/a;; (P* x3 x=)==))
(15)
We then substitute D. for in Equations (6) and (7), essentially emphasizing that the sample z; should cluster tightly around its assigned prototype cluster Xý, and remain distant from other clusters. However, this approach is prone to error accumulation: if a sample is initially misclassified, Ccomp and Sep will erroneously encourage issue, we draw inspiration from previous practices in prototypical contrastive learning and leverage prototypical contrastive loss [43]:
continue moving the wrong direction. To address this
exp(z, P(/(S) log Ex= exp(z, p)/05)
Leontrs
(16)
where & caleulates 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 amncentration-weighte contrastive signal, rather than accumulating current enrors. Thus, overall objective of GDeR becomes:
CaDER Lrast + d Ceump + X2 Lyepu + Ag Lcontra
(17)
We applied this setting when extending GDeR to pre-training with GraphMAF on the ZINC dataset, with the experimental results in Table 7.
19

---

Table 7: Graph pre-training performance of GDeR on GraphMAE [47]+ZINCI5 [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].
Remaining Ratio %
30%
50%
70%
Dataset
BBBP
ToxCast
BACE
BBBP ToxCast
BACE
BBBP
ToxCast
BACE
Original +GDeR
72.04 73.57
65.77
81.96
72.04
65.77
81.96 82.29
72.04 73.87
65.77
81.96
63.55
78.42
73.99
64.16
65.68
82.70
Time consumption
1.70
2.58 h
3.78
Training Speedup
2.81x
1.86x
1.26x
The original pre-trainn training time 4.8 h.
Table 8: Performance comparison to state-of-the-art dataset pruning methods. All methods are trained using PNA, and the reported metries represent the average of twenty random runs and different dataset splits.
Dataset
MUTA (Accuracy 1)
DHFR (Accuracy
Remaining Ratio %
20
30
50
70
20
30
50
Random
85.3
85.6
86.7 ...7
88.3
72.3
72.6.a1
73.7
75.8
CD [93]
85.1
85.8
87.0.2.4
88.1
72.1 14.4
72.8
74.0
76.
Herding [94]
77.7
79.6.9.8
81.5
87.9.1.6
65.8
67.6.8.9
69.6.a.9
73.612.9
K-Center [95]
7..2
80.6,8.8
84.2.5.a
88.4.1.0
64.2
68.2.8.3
70.6
72.8
Least Confidence [96]
85.3
85.6
87.8
88.3
72.3
72.6.9.9
74.8
76.1
Margin [96]
g..2
84.5
87.3
88.4
70.2
71.5_5.0
74.6
75.6
Forgetting [33]
85.8
86.2.13.2
87.1
88.4
72.8
73.2.s.8
[4.1
76.0
Statie
GraNd-4 [18]
81.7
85,9
87.0
88.2
68.7
72.9
74.0
75.6
DeepFool [97]
85.1 14.3
85.6
86.7 L2.7
88.1 88.1
72.1 14:4
72.7_s.8
73.2
75.8 jo.7
Craig [98]
85.0
85.4.4.0
86.3
88.2
72.0
72.5
73.7
76.2
Glister [99]
86.3
86.8
87.2,2.2
88.4
72.9
73.3
75.2
76.4
Influence [57]
84.714.7
85.9
86.7
88.1
71.7.4.8
72.9.a.6
73.7
75.4
EL2N-2 [33]
p..2
87. 12.a
87.7
88.2 88.2
72.2
73.9.2.6
74.6.1.
75.0
EL2N-20 [33]
8..3
87.1
87.9.1.a
88.3
72.4.4.1
73.0
74.6.1.
76.2.poa
DP [100]
85.3
86.2.aa2
87.4
87.9
71.3
72.6.a.9
74.0
75.610.9
Dynamic
Random*
87.0
86.6
88.8.o.. jo.6
88.9.0.s
73.4
73.9.2.6
74.8.1.7
76.4
e-greedy [58]
L6.5
86.3
88.3
88.9 88.9.0.6
73.1 13.4
73.4_a.1
14.1
76.4
UCB [58]
L6.5
86.4
87.7
88.5.g..
73.1 13.4
73.5_a.0
74.0,2.5
75.9
InfoBatch [23]
86.8
86.7
89.0.o.4 .0.4
89.3
73.3
73.7 12.8
75.0
76.3 jo.2
GDeR
88.2
88.5
89.3
89.9 10.5
75.7 jos
75.9 Jo.
76.
77.1 10.6
Whole Dataset
09.4+
76.5
E Additional Experimental Results
We place additional results about MUTAG and DHFR in Table 8, and the GraphMAF+ZINC pre-training results in Table 7.
Supplementary Related Work
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], cumissueeveieed [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 contrastive learning, [115] incorporates prototypical learning, adding a contrastive mechanism between samples and prototypes obtained through offline clustering. PALM [82] utilizes prorotypical learning for
20

---

suttof-ddistibuttion (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 more lightweight training burden, and our method is the first attempt at leveraging prototype learning for soft data pruning.
21

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: this paper, we introduce a novel soft pruning strategy and we claim the con- tributions and scope in the abstract and introduction sections (See Abstract and Introduction Section).
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: this work, we systematically discuss the limitations of our research and outline directions for future work (See Introduction Section).
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
22

---

Answer:
[NA]
Justification:
This paper does not include experimental results related to theoretical aspects.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We provide the code necessary for replicating the studies described in this paper via an anonymous link, and we detail the experimental setup for the replication in the article itself (See Appendix).
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
23

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions 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.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to rum to reproduce the results. See the NeurIPS code and data submission guidelines (https: / /nips. cc/public//eeecccccccccccccc wwwolicgguides////eeeeeeoo /Coo//eoeeeeeeeee cobbbmisssinn womiissssoopoooyoooo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code permitted.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
we have specified all the training and test details (e.g., data splits, hyperpa- rameters, how they were chosen, type of optimizer, etc.) necessary to understand the results (See Appendix B).
Justification:
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 appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, or as supplemental material.
7. 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 emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
24

---

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 the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
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 include experiments.
The paper should indicate 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 (c.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https /:tn:///neeuppe httpp///ccccccccccccccteeeeeeee.
Answer: [Yes]
Justification:
The study presented in this paper conforms to the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. if there special consid- eration due to laws or regulations in their jurisdiction..
10. 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.
25

---

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), faimess 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 tied to particular applications, let alone deployments. However, if there is 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 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 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 attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have 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 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 best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (c.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]
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 research.
Justification:
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 dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
26

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
If assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. cww datasets has curated licenses for some datasets. Their licensing guide can help determine the license of 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 s creators.
13. 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/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent 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.
14. 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 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 contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS 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.
15. 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 crowdsoureing nor research with human subjects.
27

---

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.
28


Reviews:
[{"review_id": "Dl2tQGoPXJ", "reviewer": "Reviewer_RKXd", "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.", "questions": "(1) Figure 1 shows the sample label ditrbution using Infobatch, right? If so, what is the distribution like with GDER?\n(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": "The limiations are discussed in the paper.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(1) Soft dataset pruning for graph data remains underexplored for the past years, and GDER makes the first attempt.\n(2) The paper reads very well, with straightforward motivation and well-organized methodology. I appreciate its visual aids (Fiure 2,3).\n(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.\n(2) In robust GNN training, the baselines compared are outdated. There are stronger robust GNN baselines [1,2,3].\n(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].\n\n\nMinor:\n\nI 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$?\n\n\n[1] Adversarial robustness in graph neural networks: A Hamiltonian approach, NeurIPS 2023.\n[2] A Simple and Yet Fairly Effective Defense for Graph Neural Networks, AAAI 2024\n[3] Graphde: A generative framework for debiased learning and out-of-distribution detection on graphs, NeurIPS 2022\n[4] Adversarial attacks on node embeddings via graph poisoning, ICML 2019\n[5] Adversarial attacks on neural networks for graph data, KDD 2018", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n---\n> **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.\n\nThank 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.\n\n---\n> **Weakness 2**:  In robust GNN training, the baselines compared are outdated. There are stronger robust GNN baselines [1,2,3].\n\nWe 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.\n\n*Table A. F1-Macro (%) comparison among GraphDE, MRGL and GDeR on DAGCN+MUTAG with GRABNEL. We set the pruning ratio of GDeR to 30%.*\n|Noise ratio|0%|5%|10%|20%|\n|-|-|-|-|-|\n|GraphDE|85.12|82.99|81.45|79.16|\n|MRGL|85.12|**84.66**|82.07|78.59|\n|GDeR|85.12|83.08|**83.46**|**80.14**|\n\n[3] Graphde: A generative framework for debiased learning and out-of-distribution detection on graphs, NeurIPS 2022\n\n[4] Multi-View Robust Graph Representation Learning for Graph Classification, IJCAI 2023\n\n[5] Adversarial Attacks on Graph Classification via Bayesian Optimisation， NeurIPS 2021\n\n---\n> **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].\n\nThank 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.\n\nIn 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.\n\n[1] Adversarial Attacks on Graph Classification via Bayesian Optimisation\n\n---\n> **Minor** \n\nThank 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!\n\n---\n> **Question 1**: Figure 1 shows the sample label ditrbution using Infobatch, right? If so, what is the distribution like with GDER?\n\nThank 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.\n\n---\n> **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?\n\nThank you for your comment, which has further improved the quality of our article!\n\n- 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.\n- Regarding **pruning of imbalanced data**, please refer to our response to Question 1.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qNe9wsGXgw", "reviewer": "Reviewer_kNzQ", "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.", "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": "The authors have adequately discussed the limitations.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "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.\n2. 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.\n3. 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?\n2. Does changing the weights of different losses such as $\\lambda_1$ in Eq.(13) have an impact on the model output?\n3. 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?\n4. There appears to be some typos in line 245. $\\lambda$ misses a subscript.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n---\n> **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?\n\nThank 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.\n\n[1] Attribute prototype network for zero-shot learning\n\n---\n> **Weakness 2**: Does changing the weights of different losses such as $\\lambda_1$ in Eq.(13) have an impact on the model output?\n\nWe 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.\n\n*Table A. Sensitivity analyis of $\\lambda_1$ and $\\lambda_2$ on MUTAG+PNA. The pruning ratio is set to 50%.*\n|$\\lambda_1$\\ $\\lambda_2$|5e-2|1e-1|5e-1|1e-0|\n|-|-|-|-|-|\n|5e-2|88.72|88.54|88.66|88.38|\n|1e-1|89.11|89.37|89.21|88.56|\n|5e-1|88.80|88.24|89.17|89.15|\n|1e-0|88.03|88.79|89.07|89.12|\n\n---\n> **Weakness 3**: As shown in Eq. (14), $\\Psi(t)$ at the beginning of training,\n 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?\n\nWe 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.\n\n---\n> **Weakness 4**: There appears to be some typos in line 245. $\\lambda$ misses a subscript.\n\nThank 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$}.\n\n---\n> **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?\n\nTo 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.\n\n**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).\n\n**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.\n\n*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).*\n|Remaining ratio|100|70|30|\n|-|-|-|-|\n|Random|95.69|94.88|90.2|\n|InfoBatch|95.69|95.36|94.92|\n|GDeR|95.69|**95.74**|**95.12**|\n\n\n*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).*\n|Remaining ratio|100||60||\n|-|-|-|-|-|\n|Metric|Acc|Time|Acc|Time|\n|InfoBatch|76.43|6.2h|76.49|3.74h|\n|GDeR|76.43|6.2h|**76.52**|3.89h|", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bWZg474MnO", "reviewer": "Reviewer_zhEK", "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.", "questions": "1. Is the proposed method extendable to other data domains?\n2. How does the trainable prototypes effect the training speed?\n3. Can GDeR remain its performance even pruning a great propotion of training samples?\n4. Can you compare GDeR with other data imbalance baselines?", "limitations": "Yes", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "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.\n\n2. 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. \n\n2. 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.\n\n3. 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?\n\n4. 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].\n\n[1] Focal loss for dense object detection\n[2] Dynamic sampling in convolutional neural networks for imbalanced data classification", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n---\n> **Weakness 1 & Question 1**: Is the proposed method extendable to other data domains?\n\nTo 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.\n\n**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).\n\n**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.\n\n*Table A. Accuracy (%) comparison between Random, InfoBatch and GDeR on CIFAR-10+ResNet-18. Remaining ratio are set among {100%, 70%, 30%}.*\n|Remaining ratio|100|70|30|\n|-|-|-|-|\n|Random|95.69|94.88|90.2|\n|InfoBatch|95.69|95.36|94.92|\n|GDeR|95.69|**95.74**|**95.12**|\n\n\n*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).*\n|Remaining ratio|100||60||\n|-|-|-|-|-|\n|Metric|Acc|Wall-clock Time|Acc|Wall-clock Time|\n|InfoBatch|76.43|6.2h|76.49|3.74h|\n|GDeR|76.43|6.2h|**76.52**|3.89h|\n\n\n---\n> **Weakness 2 & Question 2**: The authors need to provide discussions both on complexity analysis and numerical comparisons to quantify the extra computational burden.\n\nFollowing your suggestions, we provide (1) complexity analysis and (2) numerical comparisons to better evaluate the efficiency of GDeR.\n\n**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.\n\n**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).\n\n*Table C. Results on MUTAG+PNA.*\n|  Sparsity     | 0.2      | 0.3      | 0.5      | 0.7      |\n|-|-|-|- | -- |\n| Ours | 115.9506 | 118.4320 | 195.7631 | 241.3048 |\n| Random | 100.6895 | 100.0426 | 183.6579 | 227.6009 |\n| InfoBatch | 102.5114 | 114.5953  | 185.8063 | 231.3231 |\n\n*Table D. Results on  GraphGPS+Molhiv.*\n|  (prune 70%)| Wall-clock time| Performance|\n|-|-|-|\n|Random| 1607.29| 74.1|\n|InfoBatch| 1694.55| 75.6|\n|GDeR| 1844.56|**76.9**|\n\n---\n> **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?\n\nTo address your concerns, we compare GDeR with several best-performing baselines under extremely sparse scenarios.\n\n*Table E. Results on MUTAG+PNA.*\n|Remaining Ratio (%)|10|15|20|\n|-|-|-|-|\n|Random|82.71±1.29|85.92±0.94|87.60±0.52|\n|UCB|83.11±0.87|85.70±0.81|86.52±0.60|\n|InfoBatch|83.42±0.93|86.33±0.42|86.8±0.83|\n|GDeR|**83.59**±1.03|**87.15**±0.59|**88.24**±0.72|\n\n---\n> **Weakness 4 & Question 4**: The authors should also compare their method with other techniques for data imbalance in Section 4.3.\n\nThank 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.\n\n*Table F. F1-Macro (%) comparison of GDeR, DynamicSample and Graph-level SMOTE on MUTAG+GCN. We fix the pruning ratio of GDeR to 20%.*\n|Imbalance Ratio|1:9|3:7|7:3|9:1|\n|-|-|-|-|-|\n|Original|58.07|76.52|51.99|50.75|\n|DynamicSample[1]|63.12|75.41|73.07|69.20|\n|Graph SMOTE[2]|65.26|77.87|77.68|73.48|\n|GDeR|71.81|79.10|77.96|75.70|\n\n[1] Dynamic sampling in convolutional neural networks for imbalanced data classification\n\n[2] Imbalanced Graph Classification via Graph-of-Graph Neural Networks", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Dear Reviewers,

We extend our sincere gratitude for your dedication to the review process. We are truly encouraged by the reviewers' recognition of several positive aspects of our paper, including **a novel and significant data pruning method** (Reviewer `RKXd`,  `kNzQ`, `zhEK`), **high-quality presentation** (Reviewers  `RKXd`,  `kNzQ`, `zhEK`), and **encouraging experimental rsults** (Reviewers `RKXd`). Additionally, we have diligently addressed and responded to each concern raised by every reviewer. Here, we summarize several key points as follows:

1. **Transferability to other data domains** (Reviewer `kNzQ`, `zhEK`)
To demonstrate the transferability of GDeR to other data domains, we present its performance on CIFAR-10 and ImageNet datasets (in Tables 1 and 2 of the gloabl rebuttal PDF).

2. **Updated baselines** (Reviewer `RKXd`, `zhEK`)
We compare GDeR with more advanced robust GNN and long-tail techniques (in Tables 3 and 4).

3. **Complexity and efficiency** (Reviewer `zhEK`)
We supplement the complexity analysis of GDeR and provide corresponding wall-clock time evaluation (in Tables 5 and 6).

4. **Case Study** (Reviewer `RKXd`)
We have supplemented a case study, demonstrating how GDeR dynamically removes noisy data and alleviates long-tail distribution in practical training processes (in Figures 1 and 2).

Thanks again to all the reviewers, and your expertise significantly helps us strengthen our manuscript – this might be the most helpful review we received in years! We are willing to address any further concerns or questions you may have.

Warm regards,

Authors

Meta-review: 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.
Decision: Accept (poster)