Diving into Unified Data-Model Sparsity for Class-Imbalanced Graph Representation Learning
Authors: Chunhui Zhang
Chao Huang
Yijun Tian
Qianlong Wen
Zhongyu Ouyang
Youhuan Li
Yanfang Ye
Chuxu Zhang
Venue: Submitted to ICLR 2023 (2023)
Keywords: Graph representation learning
Class-imbalanced data

Abstract: Even pruned by the state-of-the-art network compression methods, recent research shows that deep learning model training still suffers from the demand of massive data usage. In particular, Graph Neural Networks (GNNs) trained upon non-Euclidean graph data often encounter relatively higher time costs, due to its irregular and nasty density properties, compared with data in the regular Euclidean space (e.g., image or text). Another natural property accompanied with graphs is class-imbalance which cannot be alleviated even with massive data, therefore hinders GNNs’ ability in generalization. To fully tackle these unpleasant properties, (i) theoretically, we introduce a hypothesis about to what extent a subset of the training data can approximate the full dataset’s learning effectiveness. The effectiveness is further guaranteed and proved by the gradients’ distance between the subset and the full set; (ii) empirically, we discover that during the learning process of a GNN, some samples in the training dataset are informative in providing gradients to update model parameters. Moreover, the informative subset evolves dynamically during the training process, for samples that are informative in the current training epoch may not be so in the next one. We refer this observation as dynamic data sparsity. We also notice that sparse subnets pruned from a well-trained GNN sometimes forget the information provided by the informative subset, reflected in their poor performance upon the subset. Based on these findings, we develop a unified data-model dynamic sparsity framework named Graph Decantation (GraphDec) to address challenges brought by training upon a massive class-imbalanced graph dataset. The key idea of GraphDec is to identify the informative subset dynamically during the training process by adopting sparse graph contrastive learning. Extensive experiments on multiple benchmark datasets demonstrate that GraphDec outperforms state-of-the-art baselines for the class-imbalanced graph classification and class-imbalanced node classification tasks, with respect to classification accuracy and data usage efficiency.

Under review as a conference paper at ICLR 2023
UNIFYING DATA-MODEL SPARSITY FOR CLASS- IMBALANCED GRAPH REPRESENTATION LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
To relieve the massive computation cost in the field of deep learning, models with more compact architectures have been proposed for comparable performance. How- ever, it is not only the cumbersome model architectures but also the massiveness of the training data that adds up to the expensive computational burdens. This problem is particularly accentuated in the graph learning field: one hand, Graph Neural Networks (GNNs) trained upon non- -uelldcld graph data often encounter rela- tively higher time costs, due to their irregular density properties; on the other hand, the natural class-imbalance property accompanied by graphs cannot be alleviated by the massiveness of data, therefore hindering GNNs' ability in generalization. To fully tackle the above issues, (i) theoretically, we introduce a hypothesis on what extent a subset of the training data can approximate the full dataset's s learning effectiveness, which is further guaranteed by the gradients' distance between the subset and the full set; (ii) empirically, we discover that during the learning process of a GNN, some samples in the training dataset are informative in providing gradi- ents for model parameters update. Moreover, the informative subset evolves as the training process proceeds. We refer to this observation as dynamic data sparsity. We also notice that a pruned sparse contrastive GNN model sometimes "forgets" the information provided by the informative subset, reflected in their large loss magnitudes. Motivated by the above findings, we develop unified data-mode dynamic sparsity framework named Graph Decantation (GraphDec) to address the above challenges. The key idea of GraphDec is to identify the informative subset dynamically during the training process by adopting the sparse graph contrastive learning. Extensive experiments that GraphDec outperforms state-of-the baselines for the class-imbalanced graph/node classification tasks, with respect to classification accuracy and data usage efficiency.
multiple benchmark datasets demonstrate
INTRODUCTION
Graph representation learning (GRL) (Kipf & Welling, 2017) has shown remarkable power in dealing with non-Euclidean structure data (e.g., social networks, biochemical molecules, knowledge graphs). Graph neural networks (GNNs) (Kipf & Welling, 2017; Hamilton et al., 2017; Veličković et al., 2018), as the current state-of-the-ar of GRL, have become essential in various graph mining applications.
However, in many real-world scenarios, training on graph data often encounters two difficulties: class imbalance (Park al., 2022) and massive data usage (Thakoor et al., 2021; Hu al., 2020). Firstly, class imbalance naturally exists in datasets from diverse practical domains, such as bioinformaties and social networks. GNNs are sensitive to this property and can be biased toward the dominant classes. This bias may mislead GNNs' learning process, resulting in underfitting samples that are of real importance to the downstream tasks, and poor test performance at last. Secondly, massive data usage requires GNN to perform saasagg-passing over nodes of high degrees bringing about heavy computation burdens. Some calculations are redundant in that not all neighbors are informa- tive regarding learning task-related embeddings. Unlike regular data such images or texts, the connectivity of irregular graph data invokes random memory access, which further slows down the efficiency of data readout.

---

Under review as a conference paper at ICLR 2023
Accordingly, recent studies (Chen et al., 2021; Zhao et al., 2021; Park et al., 2022) arise to address the issues of class imbalance or massive data usage in graph data: (i) On one hand, to deal with the class imbalance issue in node classification
graphs. GraphSMOTE (Zhao et al., 2021) tries to generate new nodes for the minority classes to balance the training data. Improved upon GraphSMOTE. GraphENS (Park al., 2022) further proposes new augmentation method by constructing an ego network to learn the representations of the minority classes. (ūi) On the other hand, to alleviate the massive data usage, (Eden al., 2018; Chen et al., 2018) explore efficient data sampling policies to reduce the computational cost from the data perspective. From the model improvement perspective, some approaches design the quantization-ane aware training and low- low-precision inference method to reduce GNNs' operating costs on data. For example, GLT (Chen et al., 2021) applies the lottery ticket pruning technique (Frankle & Carbin, 2019) to simplify graph data and the GNN model concurrently,
Despite progress made so far, existing meth- ods fail to address the class imbalance and computational burden altogether. Dealing with one may even exacerbate the condi- tion of the other: when tackling the data imbalance, the newly synthetic nodes in GraphSMOTE and GraphENS bring along extra computational burdens for the next- coming training process. While a compact model reduces the computational burden to some extent, we interestingly found that the pruned model easily "forgets" the mi- norities in class-imbllanced data, reflected in its worse performance than the original model's. s. To investigate this observation, we study how each graph sample affects the GNN training by taking closer look at the gradients each of them exerts. Specifically, (i) in the early phases of training. we identify small subset that provides the most informative supervisory signals, as measured by the gradient norms' magnitudes (shown in later Figure 5); (ii) the informative subset evolves dynamically as the training process proceeds (as depicted in later Figure 3). Both the phenomenons prompt the hypothesize that the full training set's training effectiveness can be approximated, to some extent, by that of the dynamic subset. We further show that the effectiveness of the approximation is guaranteed by the distance between the gradients of the subsel and the full training set, as stated in Theorem 1.
Next
80-
Training Set
Loading
Graph Decantation
Snall Soon
Training
(this work)
Decantation
Raw Unlabeled Training Set
by Ranking
Samptes
Decantation Set
The principle of graph decantation. It decants data samples based on rankings of their gradient scores, and then uses them as the training set in the next epoch.
Figure I:
Based on the above, we propose a novel method called Graph Decantation (GraphDec) to guide dynamic sparsity training from both the model and data aspects. The principle behind GraphDec shown in Figure 1. Since the disadvantaged but informative samples tend to bring about higher gradient magnitudes, GraphDec relies on the gradients directed by dynamic sparse graph contrastive learning loss to identify the informative subsets that approximate the full set's training effectiveness. This mechanism not only does not require supervised labels, but also allows for the training of the primary GNN, and the pruning of the sparse one. Specifically, for each epoch, our proposed framework scores samples from the current training set and keep only k most informative samples for the next epoch. Additionally, the framework incorporates a data recycling process, which randomly recycles prior discarded samples (i.c., samples that considered unimportant in the previous training epochs) by re- invollviig them in the current training process. As a result, the dynamically updated subset (i) supports the sparse GNN to learn relatively unbiased representations and (ii) approximates the full training set through the lens of Theorem 1. To summarize, our contributions in this work are:
We develop a novel framework, Graph Decantation, which leverages dynamic sparse graph con- trastive learning on class-imbalanced graph data for efficient data usage. To our best knowledge, this is the first study to explore the dynamic sparsity property for class-imbalanced graphs.
We introduce cosine annealing to dynamically control the sizes of the sparse GNN model and the graph data subset to smooth the training process. Meanwhile, we introduce data recycling to refresh the current data subset and avoid overfitting.
Comprehensive experiments on multiple benchmark datasets demonstrate that Graph out- performs of-t-of-the--ee art methods for both the class-imbalanced graph classification and class- imbalanced node classification tasks. Additional results show that GraphDec dynamically finds an informative subset across the training epochs effectively.
2

---

Under review as a conference paper at ICLR 2023
2
RELATED WORK
Graph Contrastive Learning. Contrastive learning is first established for image tasks and then receives considerable attention in the field of graph representation learning (Chen et al., 2020). Contrastive learning is based on utilizing instance-level identity as supervision and maximizing agreement between positive pairs in hidden space by contrast mode (Velickovic et al., 2019; Hassani & Khasahmadi, 2020; You et al., 2020). Recent research in this area seeks to improve the efficacy of graph contrastive learning by uncovering more difficult views (Xu al., 2021; You et al., 2021). However, the majority of available approaches utilize a great deal of data. By identifying important subset from the entire dataset, our model avoids this issue.
Training deep model with sparsity. Parameter pruning aiming at decreasing computational cost has been a popular topic and many varameter-pruning strategies are proposed to balance the trade-off between model performance and learning efficiency (Deng et al., 2020; Liu et al., 2019). Some of them belong to the static pruning category and deep neural networks are pruned either by neurons (Han et al., 201 5b; 2016) architectures (layer and filter) (He et al., 2017; Dong et al., 2017). In contrast, recent works propose dynamic pruning strategies where different compact subnets will be dynamically activated at each training iteration (Mocanu et al., 2018; Mostafa & Wang, 2019; Raihan & Aamodt, 2020). The other line of computation cost reduction lies in the dataset sparsity (Karnin & Liberty, 2019; Mirzasoleiman al., 2020; Paul al., 2021). Recently, the property of sparsity is also used to improve model robustness (Chen et al., 2022; Fu et al., 2021). ). In this work, we attempt to accomplish dynamic sparsity from both the GNN model and the graph dataset simultaneously.
Mlass-imblaanee learning on graphs. Excepting conventional node re- balanced methods, like reweighting samples (Zhao et al., 2021; Park et al., 2022) and oversampling (Zhao et al., 2021; Park et al., 2022), an early work (Zhou et al., 2018) characterizes rare classes through a curriculum strategy, while other previous works (Shi al., 2020; Zhao al., 2021; Park et al., 2022) tackles the class-imbalanced issue by generating synthetic samples to re-balance the dataset. Compared to the node-level task, graph-level re-balancing under-explored. A recent work (Wang et al., 2021) proposes to utilize neighboring signals to alleviate graph-level glass-imbalance. To the best of our knowledge, our proposed GraphDec is the first work to solve the class-imbalanced for both the node-level and graph-level tasks.
METHODOLOGY
In this section, we first theoretically illustrate our graph sparse subset approximation hypothesis, which guides the design of GraphDec to continuously refine the compact training subset via the dynamic graph contrastive learning method. The presentation is organized by the importance ranking procedure of each sample, refine smoothing, and overfitting regularization. Relevant preliminaries of GNNs, graph contrastive learning, and network pruning are provided in Appendix B.
3.1 GRAPH SPARSE SUBSET APPROXIMATION HYPOTHESIS
We first introduce the key notations used in the method, Specifically, we denote the full graph dataset as Gr, the graph data subset used to train the model as Gs. the learning rate as a, and the graph learning model parameters as 0 (the optimal model parameters as 0*), Mcanwhile, we add a superscript represent the model's parameters and the graph data subset at epoch I, i.e., 000) and g
Besides, we use (gg)) to indicate the loss of model (()) over the graph dataset g( Thus, the
gradient error at the training epoch can be computed as (r) Voce
Logh) Lote Vai fer
The sparse graph subset approximation hypothesis states that the model effectiveness trained on can be approximated by the one trained on Gs. We introduce the hypothesis as follows:
Theorem Assume the model's 's parameters at epoch satisfies |@(0 2 < d?, where d is constant,
and the loss function L(-) is convex, can have the following guarantee:
If training loss LGg is Lipschitz continuous, VateL is upper-bounded by and oVT muin:Logg p00;
d then
Lax)
da T-1 (1)
The detailed proof of Theorem is provided in Appendix A. According to Theorem 1, is straight- forward that we can minimize the gap between the models trained on the full graph dataset and
3

---

Under review as a conference paper at ICLR 2023
(iii)
Recycle Bin
VgL
Giz
Throw
Sample
G
Gk:
cke+1
Gr
Prunc
CL
G3
Gs'
G
G2
Increase
G2
Top (1 - c)k
01
(iv)
Training Sct
Dynamic Sparse Pruner
(ii)
Rank by Gradients
The overall framework of GraphDec: (i) The dynamic sparse graph contrastive learning model computes gradients for graph/node samples; (ii) The input samples sorted according to their gradients; (iii) Part of the samples with the smallest gradients are thrown into the recycling bin; (iv) Part of the samples with the largest gradients in the current epoch and some sampled randomly from the recycling bin are jointly used as training input in the next epoch.
Figure 2:
graph data subset, i.e., Lgg;00 - Løx by reducing the distance between the gradients of the full
graph dataset and the graph subset, i.e., Err(") In other words, the optimized graph subset g is expected to approximate the gradients of the full graph dataset, and thereby exerts minimal affects on parameters' update. In contrast to GraphDec, data diet (Paul et al., 2021) is designed to identify the most influential data samples Gs (those with largest gradients during the training phase) only at the early training stage and have them involved in further training processes, while excluding samples from Gs Gr Gs with smaller gradients (i.e., Voco Lgg)), (001) V Vocc gio ggo, eternally.
This one-shot selection, however, capture the most important samples across all epochs during the training. Specifically, the rankings of elements within specific Gs might be relatively static, but those within the full graph dataset, i.e., g, are usually more dynamic, which implies the gradients of the one-shot subset Voce agght p000 is unable to constantly approximate that of the full graph dataset V gcs G during training.
will show in the experiments (Section 4.5), does not always
3.2 GRAPH DECANTATION
Inspired by Theorem and to solve the massive data usage in class-imbalance graphs, we propose GraphDec for achieving competitive performance as well as efficient data usage simultancously by dynamically filtering out the most influential data subset. The overall framework of GraphDec is illustrated in Figure 2. The training processes are summarized into four steps: (i) First, compute
the gradients of the samples in G with respect to the contrastive learning loss; (ii) Normalize the gradients and rank the corresponding graph/node samples descending order based on their gradient magnitudes; (iii) Decay the number of samples from | to (g(++)) with cosine annealing,
where we only keep the top (1 () samples
the exploration rate which controls the ratio of the randomly re-sampled samples from the recycle bin. The rest samples will hold in the recycle bin temporarily; (iv) Finally, randomly re-sample e ( samples from the recycled bin. The union of these samples and the ones selected in step (iii) will be used for model training in the (t + 1)-th
epoch. Each of the four steps is described in detail in the following content.
Compute gradients by dynamic sparse graph contrastive learning model. We adopt the mech- anism of dynamic sparse graph contrastive learning in computing the gradients. The reason is two-folded: (a) it scores the graph samples without the supervision of any label; (b) this pruning process is more sensitive in selecting informative samples, verified in Appendix D. We omit the superscript (1) for the dataset and model parameters for simplicity in the explanation of this step. Specifically, given a graph training set G = (G.) as input, for each training sample G,, we randomly generate two augmented graph views, G², and G", and feed them into the original GCN model fo).), and the sparse model f-) pruned dynamically by the dynamic sparse pruner, respec- tively. The gradients are computed based the outputs of the two GNN branches, directed by the contrastive learning loss signals. To obtain the pruned GNN model, the pruner only keeps neural connections with the top-k largest weight magnitudes. Specifically, the pruned parameters of 1-th
4

---

Under review as a conference paper at ICLR 2023
GNN layer (i.e., (') are selected following the formula below:
00 TopK(0', k); B(0) x 10%,
where (0' k) refers to the operation of selecting the top-k largest elements of 0', and /300) is the fraction of the remaining neural connections, controlled by the cosine annealing formulated as follows:
3(00 2
{
800
{ cos( Tt (T) ee [1,7],
(2)
where ((0) is initialized as I. addition, we refresh o every few epochs reactivate neurons based on their gradients, following the formula below:
lgg = argToppk V Ds k); k = B(0) x 10%,
(3)
where arg TopK returns the indices of the top-k largest elements Tøp of the corresponding neurons 0¹. To further elaborate, we refresh p every few epochs by 0f - B u 6y. as the updated pruned parameters to be involved in the next iteration. After we obtain the pruned model, gradients are computed based on the contrastive learning loss between fo(G') and fo, (G,), which are then saved for the further ranking process.
Rank graph samples according to their gradients' Le norms. In order to find the relative importance of the samples, we rank the samples based on the gradients each of them brings about, saved in the previous training epoch by the last step. Specifically, at each of the t-th training epoch, we score each sample by the L2 norm of its gradient:
g(G,) = Vo (fo(G)), fo,. (G))
where L is the popular InfoNCE (Van den Oord et al., 2018) loss in contrastive learning, taking the outputs of the two GNN branches as inputs. Therefore, the gradient is calculated as follows:
VoL(fo(G), (G. po (G"),
(5)
where po(C') and pa, (G"T) are the normalized model's predictions, i.e., p(-) S(S(-) and S(-) is the softmax function or sigmoid function. The samples are ranked based on the values calculated by Eq. 4.
Decay the size of Gs by cosine annealing. For decreasing the size of the subset, we use cosine annealing when the training process proceeds. As we will show in Figure 3 for the experiments, some graph samples showing low scores of importance at the early training stage may be highly-scored again if given more patience in the later training epochs. Therefore, chunking the size of the sparse subset radically in one shot deprives the chances of the potential samples informing the models at later stage. To tackle this issue, we employ cosine annealing to gradually decrease the size of the subset:
|
[ 1+ cos(
T(1) } tE LE [1.T].
G (0)
6
T
Note that this process not only automatically decreases the size of Gs smoothly, but also avoids the manual one-shot selection as the data diet (Paul et al., 2021).
Recycle removed graph samples for the next training epoch. We aim to update the elements in G(t) obtained in the last step. Since current low-scored samples may still have the potential be highly-scored in the later training epochs, we randomly recycle proportion of the removed samples and re-involve them in the training process again. Specifically, the exploration rate controls the proportion of data that substitutes a number of elg samples with the lowest scores with the same
amount of randomly selected samples in g ((++1) At the t-th epoch, the update rule is formulated as follows:
G To (1- ( UD Samplek (t-1) .elg
where SampleK (1-1) ( (lg(+++)))) returns randomly sampled elg(t+1) samples from Gg (t-1)
saved in the last epoch. We utilize the compact sparse subset g((-1) for the training purposes (t + 1)-th epoch, and repeat the previous pipelines until T epochs.
5

---

Under review as a conference paper at ICLR 2023
4 EXPERIMENTS
In this section, we conduct extensive experiments to validate the effectiveness of our proposed model for both the graph and node classification tasks under imbalanced datasets. We also conduct ablation study and informative subset evolution analysis to further prove the effectiveness. Due to space limit, more analysis validating GraphDec's 's properties and resource cost are provided in Appendix D and E.
4.1 EXPERIMENTAL SETUP
Datasets. We validate our model on various graph benchmark datasets for the two classification tasks under the class-imbalnced data scenario. For the class-imbalanced graph classification task, we choose the seven validation datasets in GNNNN paper (Wang et al., 2021), 1), i... MUTAG, PROTEINS, D&D, NCI1, PTC-MR, DHFR, and REDDIT-B in (Morris et al., 2020). For the class-imbalanced node classification task, we choose the five datasets in the GraphENS paper (Park et al., 2022), i.e., Cora-I.T, CiteSeer-LTT PubMed-LTT (Sen et al., 2008), Amazon-Photte and Amazon-Computers. Detailed descriptions of these datasets are provided the Appendix C.I.
Baselines. We compare our model with a variety of baselines methods with different rebalance methods. For class-imbalanced graph classification, we consider three rebalance methods, i.e., vanilla (without re-balancing when training), up-sampling ( (Wang et al., 2021), and re-weight (Wang et al., 2021). 1). For each rebalance method, we run three baseline methods including GIN (Xu et al., 2019), InfoGraph (Sun et al., 2019), and GraphCL (You et al., 2020). In addition, adopt two versions of G2GNN (i.e., remove-edge and mask-node) (Wang et al., 2021) for in-depth comparison. For class-imbalanced node classification, we consider nine baseline methods including vanilla, SynFlow (Tanaka et al., 2020), BGRL. (Thakoor et al., 2021), GRACE (Zhu et al., 2020), re- weight (Japkowicz Stephen, 2002), oversampling (Park et al., 2022), cRT (Kang et al., 2020), PC Softmax (Hong et al., 10.1). DR-GCN (Shi et al., 2020), GraphSMOTE (Zhao et al., 2021), and GraphENS (Park et al., 2022). We adopt Graph Convolutional Network (GCN) (Kipf Welling, 2017) as the default architecture for all rebalance methods. Further details about the baselines are illustrated Appendix C.2.
To evaluate model performance, we choose F1-micro (F1-mi.) and F1-macro (F1-ma.) scores as the metrics for the ianalannbla graph classification task, and accuracy (Acc.), balanced accuracy (bAcc.), and F1-macro (FI-ma.) score for the node classification task.
Evaluation Metries.
Experimental Settings. We adopt GCN (Kipf & Welling, 2017) as the GNN backbone of GraphDec for both the tasks. In particular, we concatenate two-layers GCN and one-layer fully-connected layer for node classification. and add one extra average pooling operator as the readout layer for graph classification. We follow (Wang et al., 2021) and (Park et al., 2022) varying the imbalance ratios for respectiveepet respectively. In addition, we take GraphCL (You et al., 2020) as graph and node classification tasks,
the graph contrastive learning framework, and cosine annealing to dynamically control the sparsity rate in the GNN model and the dataset. The target pruning ratio for the model is set to 0.75, and the one for the dataset is set 1.0. After the contrastive pre-training, we take the GCN output logits as the input to the Support Vector Machine for fine-tuning. GraphDec is implemented in PyTorch and trained on NVIDIA V100 GPU.
4.2 CLASS-IMBALANCEE GRAPHI CLASSIFICATION PERFORMANCE
The evaluated results for the graph classification task in Table 1, with the best performance and runner-ups bold and underlined, respectively. From the table. we find that GraphDec outperforms baseline methods on both the metrics across different datasets, while only uses an average of 50% data and 50% model weights per round. Although a slight Fi-micro difference has been detected on D&D when comparing GraphDec the best baseline GNN, it is understandable due to the fact that the graphs in D&D are significantly larger than those in other datasets, necessitating specialized designs for graph augmentations (e.g., the average graph size in terms of node number is 284.32 for D&D, but 39.02 and 17.93 for PROTEINS and MUTAG, respectively). However, in the same dataset, G2NNN only achieves 43.92 on FI-macro while GraphDec reaches to 44.01, which complements the 2% difference on F1-micro and further demonstrates GraphDec's 's ability to learn effectively even on large graph datasets. Specifically, models trained under the vanilla setting perform the worst due to the ignorance of the class-imbalance. Up-sampling strategy improves the performance, but it introduces additional unnecessary data usage by sampling the minorities multiple times. Similarly, re-weight strategy tries to address the class-
graph datasets are reported

---

Under review as a conference paper at ICLR 2023
Table 1: fass-imbalanced graph classification results. Numbers after each dataset name indicate imbalance ratios of minority to majority categories. Best/second-best results are in bold/underline.
Rebalance
MUTAG (5:45)
PROTEINS (30:270)
D&D (30:270)
NCII (100:900)
Spasitt (%)
Basis
Method
Fl-ma.
Fl-mi.
Fl-ma.
Fl-mi.
F1-ma.
Fl-mi.
Fl-mu.
Fl -m.
data
model
GIN
$2.50
56.77
25.33
26.50
11.88
18.24
18.94
100
100
vanilla
InfoCGraph
69.11
69. 68
35.91
36.81
21.41
27.68
33.09
34,03
100
100
GraphCT.
66.82
67.77
40.86
41.24
21.02
26.80
31.02
31.62
100
100
GIN
78.03
78.77
65.64
71.55
41.15
70.56
59.19
71.80
>100
100
up-sampling
InfoGraph
78.62
79.00
62.68
66.02
41.55
71.34
53.38
62:20
>100
100
GraphCL
80.06
80.45
64.21
65.76
38.96
64.23
49.92
58.29
>100
100
GIN
77.00
77.68
$4.54
55.77
28.49
40.79
36.84
39.19
100
100
re-weight
InfoGrraph
81.68
65.73
69.60
41.92
72.43
53.05
62.45
100
100
GraphCL
80.20
80.84
63.46
64.97
40.29
67.96
50.05
58.18
100
100
GPGNN
remove edge
80.37
81.25
67.70
73.10
43.25
77.03
63.60
72.97
100
100
mask node
83.01
83.59
67.39
73.30
43.93
79.03
64.78
74.91
100
100
GraphDec
dynamic sparsity
85.71
85.71
68.32
75.84
44,01
77.02
65.73
76.02
50
50
Rebalance
PTC-MN (9:81)
DHFR (12: 10:1
REDDIT-B (50:450)
Avg.
Rank
Spusity (9)
Basis
Method
Fl-ma.
Fl-mi.
Fl-ma.
Fl-mi.
Fl-ma.
Fl-mi.
Fl-ma.
Fl.mi.
data
model
GIN
17.74
20.30
35,96
49.46
33.19
36.02
12.00
12.00
100
100
vanilla
InfoGGraph
25.85
26.71
50.62
56.28
57.67
67.10
11.00
11.14
100
100
GraphCL
24.22
25.16
50,55
56,31
53.40
62.19
10.71
10.57
100
100
GIN
44.78
55.43
55,96
59.39
66.71
83.00
6.00
5.43
> =00
100
up-sampling
InfoGraph
44,29
48.91
59.49
61.62
67.01
78.68
6.00
6.00
>100
100
GraphCLL
45.12
53.50
60.29
61.71
62.01
75.84
6.29
6.43
>100
100
GIN
36.96
43.09
55.16
57.78
45.
51.92
9.86
9.86
100
100
ro-weight
InfoGraph
44.09
49.17
58.67
60.24
65.79
77.35
5,43
5.29
100
100
GraphCL
44.75
52.22
60.87
62.79
76.15
6.00
6.29
100
100
GPGNN
remove edge
46.40
56.61
61.63
63.61
68.39
86.35
2.71
2.86
100
100
mask node
46.61
56.70
59.72
61.27
67.52
85.43
2.71
2.71
100
100
GraphiDee
dynamic sparsity
47.07
58.15
62.25
69.70
87.00
1.00
1.14
50
50
imbalanced issue by assigning different weights to different samples. However, it requires the labels for weight calculation and thus may not generalize well when labels are missing. G the best baseline, obtains decent performance by considering the usage of rich supervisory signals from both globally and locally neighboring graphs. Finally, the proposed model, GraphDec, achieves the best performance due to its ability in capturing dynamic data sparsity on from both the model and data perspectives. In addition, we rank the performance of GraphDec with regard to baseline methods on each dataset. GraphDec ranks 1.00 and 14 on average, which further demonstrates the superiority of GraphDee. Notice that all existing methods utilize the entire datasets and the model weights while GraphDec only uses half of the data and weights to achieve superior performance.
4.3
NODE CLASSIFICATION PERFORMANCE
For the class-imbalanced node classification task, we first evaluate GraphDec on three long-tailed citation graphs (i.e., Cora-LT, CiteSeer-LT, PubMed-LT) and report the results on Table 2. We find that GraphDec obtains the best performance compared to baseline methods for different metrics. GraphSMOTE. and GraphENS achieve satisfactory performance by generating virtual nodes to enrich the involvement of the minorities. In comparison, GraphDec does not rely on synthetic virtual nodes to learn balanced representations, thereby avoiding the unnecessary computational costs. Similarly to the class-imbalanced graph classification task in Section 4.2, GraphDec leverages only half of the data and weights to achieve the best performance, whereas all baselines perform worse even with the full dataset and weights. To validate the efficacy of the proposed model the real-world data, we evaluate GraphDec on naturally classiimbllanced benchmark datasets (i.e., Amazon-Phott and Amazon Amazon-Computee Computers). We see that GraphDec has the best performance both datasets, which demonstrates our model's effectiveness with data sourced from different practical scenes.
4.4 ABLATION STUDY
Since GraphDec is a unified learning framework relying on multiple components (steps) to employ dynamic sparsity training from both the model and dataset perspectives, we conduct ablation study to
7

---

Under review as a conference paper at ICLR 2023
Table 2: class-imbalanced node classification results. Best/second results are in bold/underline.
Method
Cara-LT
CieSeer-LT LT
Pu
A.P. -82)
A.C.
-211)
Sparsity (%)
Asc.
bAoc.
Fi-ma.
Acc.
hAcc.
FI-ma.
bAcc.
Fl-ma.
(b)Apc.
(b)Acc.
Fi-ma.
vanilla
73.66
62.72
63.70
53.90
47.32
43.00
51.88
82.86
78.72
68.47
64.01
100
SynFlow
72.98
60.62
63.29
52.85
46.23
42.19
69.63
56.75
50.99
81.57
76.93
68.10
62.97
100
GRACE
74.72
63.95
65.26
54.94
50.87
46.90
72.37
63.22
58.18
83.57
83.61
73.02
64.52
100
100
BCRRI
73.81
64.95
64.87
56.84
50.83
47.04
74.17
62.21
59.07
83.49
82.37
75.88
63.15
100
100
Re-Weight
75.20
68.79
69.27
62.56
55.80
53.74
77.44
72.80
73.66
92.94
90.11
100
Oversampplig
77.44
00.73
72.40
62.78
56.01
53.99
69.50
92.46
92.47
89.79
89.85
>100
100
cKT
76.54
69.26
70.95
60.60
54.05
52.36
75.10
67.52
68.08
91.24
91.17
36.02
36.00
100
100
PC Sottmax
76.42
71.30
71.24
65.70
61.54
61.19
76.92
75.82
74.19
93.32
93.32
$6,59
$6.62
100
100
DR-GCN
75:90
64. 30
63.10
56,18
49.57
44.96
72.5
58, 58.86
53.05
N/A
NIA
N/A
N/A
100
100
GraphSmooe
76.76
69.31
70.21
62.58
55.94
$4.09
75
70.96
71.85
92.65
92.61
89.39
>-100
100
GraphENS
22.26
22.94
23.13
66.92
60.19
58.67
28.12
74.13
74.58
93.82
93.81
91.94
91.91
>-100
100
GraphDee
78.29
73.94
74.25
66.90
61.56
61.85
78.20
76.05
76.32
93.85
94,02
92.19
92.16
50
Table 3: Ablation study results for both tasks. Four rows of red represent removing four individual components from data sparsity perspective. Four rows of blue represent removing four individual components from model sparsity perspective. Best results are in bold.
Class-imballanced Graph Classifiiation (F1-ma.)
Class-imbalanced Node Classifiiation (Asc.)
Variant
MUTAG
PROTEINS
D&D
NCI1
PIC-MR
DHFR
REDDITEB
Corn-EI
ChtNeee-LT PubMed-EIT
Photos
Computer
GraphDee
85.71
68.32
44.01
65,73
47.07
62.25
69.70
78.29
66.90
78,20
93.85
92.19
GBS
80.10
63.42
36.61
48.57
61.40
60.33
56.22
73:22
67.
80.95
63.55
62.30
61.99
70.61
77.15
76.15
79.09
91.33
CAD
78.41
$7.99
40.23
60.61
44.96
50.00
67.15
74.87
62.62
75.35
90.71
83.23
w/o RS
83.21
59.32
41.65
60.51
35,21
60.99
67.61
73.27
61.32
72.02
87.11
90.38
44.37
40:42
32.14
43:75
54.58
70.16
79.01
65.38
wio SG
82.63
65.
42.50
69.10
35.19
61.42
69.16
77.54
67.43
72.43
91.25
90.05
wro CAG
83,50
54,04
40.21
51.82
34,20
62.41
64.14
75.78
63.43
73.07
92.77
87 $7,40
RW
79.25
56.33
38
61.53
65.36
75.54
89.10
w/o S.S.
80.07
63.90
39.77
57.22
38.60
62.30
65.67
74.82
65,28
74,00
86.14
86.40
prove the validity of each component. Specifically, GraphDec relies on four components address data sparsity and imbalance, including pruning samples by ranking gradients (GS), training with sparse dataset (SS), using cosine annealing reduce dataset size (CAD), and recycling removed samples (RS), and the other four to address model sparsity and data imbalance, including pruning weights by ranking magnitudes (RM), using sparse GNN (SG), using cosine annealing to progressively reduce sparse GNN's s size (CAG), and reactivate removed weights (RW). In addition, GraphDec employs self supervsuervii to calculate the gradient score. The details of model variants are provided in Appendix C.3. We analyze the contributions of different components by removing each of them independently. Experiments for both tasks are conducted comprehensively for effective inspection. The results are shown in Table 3.
From the table, we find that the performance drops after removing any component, demonstrating the effectiveness of each component. In general, both mechanisms for addressing data and model sparsity contribute significantly to the overall performance, demonstrating the necessity of these two mechanisms in solving sparsity problem. Self-supervision contributes similarly to the dynamic sparsity mechanisms, in that it enables the identification of informative data samples without label supervision. In the dataset dynamic sparsity mechanism, GS and CAD contribute the most as sparse GNN's s discriminability identifies hidden dynamic sparse subsets accurately and efficiently. Regarding the model dynamic sparsity mechanism, removing RM and SG leads to a sigmificant performance drop, which demonstrates that they are the key components in training the dynamic sparse GNN from the full GNN model. In particular, CAG enables the performance stability after the model pruning and helps capture informative samples during decantation by assigning greater gradient norms. Among these variants, the full model GraphDec achieves the best result in most cases. indicating the importance of the combination of the dynamic sparsity mechanisms from the two perspectives, and the supervisen strategy.
4.5 ANALYZING EVOLUTION OF SPARSE SUBSET BY SCORING ALL SAMPLES
To show GraphDec's capability in dynamically identifying informative samples, we show the visual- ization of sparse subset evolution of data diet and GraphDec on daas-imbalanceed NCII dataset in Figure 3. Specifically, we compute 1000 graph samples with their importance scores. These samples are then ranked according to their scores and marked with sample indexes. From the upper figures
8

---

Under review as a conference paper at ICLR 2023
Fpoch
Sparh
Fpoch
Fpoch 149
Fparh
Gradlent (109
Data Diet
5
Grackent 1307
130"
7.5
GrophDec
5.0
2.5
0.0
1000
1000
500
1000
Index
Data Index
Index
Deta Index
Data Index
Figure 3: Evolution of data samples' gradients computed by data diet (Paul et al., 2021) (upper figures) and our GraphDec (lower figures) on NC11 data.
in Figure 3, we find that data diet is unable to accurately identify the dynamic informative nodes. Once data sample has been removed from the training list due to the low score, the model forever disregards it. However, the fact that sample is currently unimportant does not imply that it will remain unimportant indefinitely, especially in the early training stage when the model cannot detect the true importance of each sample, resulting in premature elimination of vital nodes. Similarly, if a data sample considered important at early epochs (i.e., marked with higher sample index), cannot be removed during subsequent epochs. Therefore, we observe that data diet can only increase the scores of samples within the high index range (i.e., 500-1000), while ignoring samples within the low index range (i.e.. 500). However, GraphDec (Figure 3 (bottom)) can capture the dynamic importance of each sample regardless of the initial importance score. We see that samples with different indexes all have the opportunities to be considered important and therefore be included in the training list. Correspondingly. GraphDec takes into account a broader range of data samples when shrinking the training list, meanwhile maintaining flexibility towards the previous importance scores.
5 FINDING INFORMATIVE SAMPLES BY SPARSE GNN
Compared with the full GNN, our dynamic sparse GNN is more sen- sitive in recognizing informative data samples which can be empiri- cally verified by Figure 4. Our dy- namic pruned model assigns larger gradients to the minorities than the majorities during the contrastive training, while the full model gen- erally assigns relatively uniform gradients for both of them. Thus, the proposed dynamically pruned model demonstrates its discrimina- tory ability on the minority class.
Full Model
Pruned Model
6
Gradient (10*)
Gradient (103)
4-
2-
250
500
750
1000
0
250
500
750
1000
Figure 4: Results of data samples' gradients computed by full GNN model and our dynamic sparse GNN model on NCII data. Red dashed line: on the left side, points the x-axis [0, 900] are majority class; on the right side, points on the x-axis [900, 1000] are minority class.
This ability in our GraphDee framework is capable of resolving the class-imbalance issue.
CONCLUSION
In this paper. to take up the graph data imbalance challenge, we propose an efficient and effective method named Graph Decantation (GraphDec), by leveraging the dynamic sparse graph contrastive learning to dynamically identified a sparse-but-ing paarss--ut-ifformaiiee subset for model training, in which the sparse GNN encoder is dynamically sampled from a dense GNN, and its capability of identifying informative samples is used to rank and update the training data in each epoch. Extensive experiments demonstrate that GraphDec outperforms state-of-the-art baseline methods for both node classification and graph classification tasks in the iass-imbalanced scenario. The analysis of the sparse informative samples' evolution further explains the superiority of GraphDee in identifying the informative subset among the training periods effectively.
9

---

Under review as a conference paper at ICLR 2023
ETHICS STATEMENT
We do not find that this work is directly related to any ethical risks to society. In general, we would like that imbalanced learning algorithms (including this work) are able perform better
minority groups in real-world applications.
REPRODUCIBILITY STATEMENT
For the reproducibility this study, we provide the source code for GraphDec in the supplementary materials. The datasets and other baselines in our experiments are described in Appendix C. and C.2.
REFERENCES
Jie Chen, Tengfei Ma, and Cao Xiao. FastGCN: Fast learning with graph convolutional networks via importance sampling. In ICLR, 2018.
Tianlong Chen, Yongduo Sui, Xuxi Chen, Aston Zhang, and Zhangyang Wang. A unified lottery ticket hypothesis for graph neural networks. In ICML, 2021.
Tianlong Chen, Zhenyu Zhang, pengjun wang, Santosh Balachandra, Haoyu Ma. Zehao Wang, and Zhangyang Wang. Sparsity winning twice: Better robust generalization from more efficient training. In ICLR, 2022.
Ting Chen, Simon Korbllith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. ICML, 2020.
Lei Deng, Guoqi Li, Song Han, Luping Shi, and Yuan Xie. Model compression and hardware acceleration for neural networks: A comprehensive survey. In Proceedings of the IEEE. IEEE, 2020.
Xin Dong, Shangyu Chen, and Sinno Pan. Learning to prune deep neural networks via layer-wise optimal brain surgeon. NeurlPS, 30, 2017.
Talya Eden, Shweta Jain, Ali Pinar, Dana Ron, and C. Seshadhri. Provable and practical approxima- tions for the degree distribution using sublinear graph samples. In WWW, 2018.
Matthias Fey and Jan Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In ICLR, 2019.
Yonggan Fu, Qixuan Yu, Meng Li, Vikas Chandra, and Yingyan Lin. Double-win quant: Aggressively winning robustness of quantized deep neural networks via random precision training and inference. In ICML, 2021.
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning large graphs. In NIP,, 2017.
Song Han, Huizi Mao, and William J Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. arXiv preprint 11X1v:1510.00149, 201 5a.
Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural network. In NeurIPS, 2015b.
Song Han, Huizi Mao, and William J Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. In ICLR, 2016.
Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-view representation learning graphs. ICML, 2020.
Yihui He, Xiangyu Zhang, and Jian Sun. Channel pruning for accelerating very deep neural networks. In ICCV, 2017.
10

---

Under review as a conference paper at ICLR 2023
Youngkyu Hong, Seungju Han, Kwanghee Choi, Seokjun Seo, Beomsu Kim, and Buru Chang. Disentangling label distribution for long-tailed visual recognition. In CVPR, 2021.
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 0rXiv:2005.00687, 2020.
Nathalie Japkowiez and Shaju Stephen. The class imbalance problem: A systematic study. Intelligent Data Analysis, 2002.
Bingyi Kang, Saining Xie, Marcus Rohrbach, Zhicheng Yan, Albert Gordo, Jiashi Feng, and Yannis Kalantidis. Decoupling representation and classifier for long-tailed recognition. In ICLR, 2020.
Zohar Karnin and Edo Liberty. Discrepancy, coresets, and sketches in machine learning. In COLT, 2019.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang, and Trevor Darrell. Rethinking the value of network pruning. In ICLR, 2019.
Baharan Mirzasoleiman, Jeff Bilmes, and Jure Leskovec. Coresets for data-efficient training of machine learning models. In ICML, 2020.
Decebal Constantin Mocanu, Elena Mocanu, Peter Stone, Phuong H Nguyen, Madeleine Gibescu, and Antonio Liotta. Scalable training artificial neural networks with adaptive sparse connectivity inspired by network science. Nature Communications, 2018.
Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. In ICML Workshop on Graph Representation Learning and Beyond, 2020.
Hesham Mostafa and Xin Wang. Parameter efficient training of deep convolutional neural networks by dynamic sparse reparameterization. In ICML, 2019.
Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. arXiv preprint wrXiv:1807.03744 2018.
Joonhyung Park, Jaeyun Song, and Eunho Yang. GraphENS: Neighbor-aware ego network synthesis for class-imbalanced node classification. In ICLR, 2022.
Mansheej Paul, Surya Ganguli, and Gintare Karolina Dziugaite. Deep learning on data diet: Finding important examples early in training. In NeurlPS, 2021.
Md Aamir Raihan and Tor Aamodt. Sparse weight activation training. NeurIPS, 2020.
Prithviraj Sen, Galileo Namata. Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- -ad. Collective classification network data. Magazine, 2008
Min Shi, Yufei Tang, Xingguan Zhu, David Wilson, and Jianxun Liu. Multi-class imbalanced graph convolutional network learning. In IJCAI. 2020.
Fan-Yun Yun Sun, Jordan Hoffman, Vikas Verma, and Jian Tang. Infograph: Unsupervised and semi- supervised graph-level representation learning via mutual information maximization. In ICLR, 2019.
Hidenori Tanaka, Daniel Kunin, Daniel L Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. In NeurlPS, 2020.
Shantanu Thakoor. Corentin Tallec, Mohammad Gheshlaghi Azar, Mehdi Azabou, Eva L Dyer, Remi Munos, Petar Veličković, and Michal Valko. Large-scale representation learning on graphs via bootstrapping. In ICLR, 2021.
11

---

Under review as a conference paper at ICLR 2023
Aaron Van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. arXiv preprint arXiv:1807003748, 2018.
Petar Velickovic, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. In ICLR, 2019.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liö, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
Yu Wang, Yuying Zhao, Neil Shah, and Tyler Demr Imbalanced graph classification via graph-of-graphh neural networks. arXiv preprint 11X 2021.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey graph neural networks. TNNLS, 2020.
Dongkuan Xu, Wei Cheng, Dongsheng Luo, Haifeng Chen, and Xiang Zhang. Infogel: Information- aware graph contrastive learning. In NeurIPS, 2021.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? ICLR, 2019.
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. In NeurlPS, 2020.
Yuning You, Tianlong Chen, Yang Shen, and Zhangyang Wang. Graph contrastive learning automated. In ICML, 2021.
Tianxiang Zhao, Xiang Zhang, and Suhang Wang. Graphsmote: Imbalanced node classification on graphs with graph neural networks. WSDM, 2021.
Dawei Zhou, Jingrui He, Hongxia Yang, and Wei Fan. Spare: Self-paced network representation for few-shot rare category characterization. In KDD, 2018
Yanqiao Zhu, Yichen Xu, Feng Yu. Qiang Liu, Shu Wu, and Liang Wang. Deep Graph Contrastive Representation Learning. In ICML Workshop on Graph Representation Learning and Beyond, 2020.
12

---

Under review as a conference paper at ICLR 2023
A PROOF OF THEOREM
We denote the full graph dataset as Gr, the graph data subset used to train the model as 9s. the learning rate a, and the graph learning model parameters 0 (the optimal model parameters as 8*). Meanwhile, we add a superscript to represent the model's parameters and the graph data subset at epoch t, i..., g(t) and g Besides, we use Lggn jet) to indicate the loss of model g(t)
over the graph dataset G Thus, the gradient error at the training epoch can be computed as En = V git) L gggg gets - Bao Lagvates The sparse graph subset approximation hypothesis states that the model effectiveness trained on can be approximated by the one trained on Gs. We introduce the hypothesis as follows:
Theorem 1.
Assume the model's parameters at epoch t satisfies ||000 2 & d,, where is a constant,
and the loss function ((-) is convex, we can have the following guarantee:
If training loss Lgs is Lipschitz continuous, Lg is upper-bounded by and a d then oVT
mini(Cog).ooo Lo+) < de
TT- 4Erl().
VT
The gradients of training loss poghoos at epoch are supposed to be a-bounded by o. According to gradient descent, we huve:
Proof
VeL gooogroos (or 2 (0(0) - 0+)= a(1) (0()) - g((+1))" ( - -0*),
(0()))
1
(0(0))
(8)
V of o00 (0()) T (0(1) -+)) (x(1)) (100 (p00-o0c2D) ol(+1) + 10000 100000000 2 -loccta)- -0+1))-011 -oxl()
1
00|²
Since one update step 0(0) - ole+1) can be optimized by gradient multiplying with learning rate a Vo giis (0(+)) we have:
Vol gfth oin (o(t)) T (00+) yt) 20113
1
ogo o0s (00))) + -110c)) - 8¹| pmpp- - - 8+ 2)
(10)
Since Vol gg o003 (0(1)) T (0(0) - 0²) can be represented as follows:
Vul t0 2001 (0(1)) T (o()) - 0²) = VoL 00 o0co (010) (000) 0*)
(11)
ve of p0s)
T T(o(0) 0*) + V o ,00) T(o(t) - 0*),
then based the combination of the Equation equation 10 and Equation equation 11, we have:
Vol gg pu (0(1) (Q(()) ((()))((()) 0*) Vol og0 T(g(t)) 0*) + VoL aeo T T(((t)) 0+)
(lal E8 oc0 (otu))2 + 10000 - 001 - -|lo0tt2) - -
(12)
Volggheco p00) F(000) - 00) 2a(1)
1
(ao gg0 g0o (0:0)) + 11oc0 001² - -|lrc--)) -100c----000 00)²))
(vel 6 (ores (0(+))
V V Volgle (01))))))) )((o())
(0r(0 8+).
(13)
We assume learning rate (t)), 1. E [0, T 1] is a constant value, then we have:
VoL Voloy.oco F(olt) - 8*)
1
(0())
1- [0()) 0012
T-1 +
of
oo
(o(tt)]
/?
2x
2a
"(010) (000--99) 03))
(
5/00 s00r (0(1)) - Vol VoLogo,oco)
+
0
13

---

Under review as a conference paper at ICLR 2023
Since we assume [0() 0012² = 0. then we have:
T-
3 ,00) T(B())
(*)
=
2a
1
g(0)
2a
a
aVoL
og s00e)
(B(3))
(14)
T-1
(Vol
g0cc :000) (0(1)
VoL
VoLow-oro .010)
)((to)
T (0tD) 0t))
We assume loss L is convex and training loss aar is lipschitz continuous with parameter o. Then for convex function (()). we have Log Lox Voloy ,000 ²(0()) 0*). By combining this result with Equation 14, we get:
T-1 1 0100 0
1
loces (oco)/13
Lø*
V
nL
20x
2a
0/
t=0
(15)
T-1 +
VoL
0 locss (0(1))
Vo
"(ol0) -00) 00))
o
(011)
1=0
Since C Lag sato (0)] &0, a Vo
s00s saces (0(0))
E and we assume 110 - -8 a d, then we have:
d
Tao²
T-1
d V goo ,0cs (0(1)) - Vologrorol) 1);
C o000000 ,000 - Cg* &
+
(16)
2a
2
d
a
:00) Lo*
Vo 3 o00s (0
goligggrou (17)
20T
Since min (Cogr ,000 Lox) $ 4 21-
C
Logh,0oo Lox, based on Equation 17, we have:
d²
ao²
T-1 d Woooog0.ooo000 oc0 -
PoCogrooro) 1). (18)
min (C (000 Lox) $
2al +
2
We set learning rate a ovT and then have:
min (C g200000 Cox) do
Vo gio o0es (0(t)) Vol Tolggoooro) 1). (19)
B PRELIMINARIES: GNNS, GRAPH CONTRASTIVE LEARNING, NETWORK PRUNING
In this work, we denote graph as G = and X Rd represents the node (and edge) attributes of dimension d. In addition, we represent the neighbor set of node e E V as No.
where V is the set of nodes, E is the set edges,
Graph Neural Networks. GNNs (Wu et al., 2020) learn node representations from the graph structure and node attributes. This process can be formulated as:
h COMBINE() (A "(4"",,AGGGGATE"""
((n5"",Vue N.)))
(20)
where h denotes representation of node at 1-th GNN layer, AGGREGATE() and COMBINE(.)
are neighbor aggregation and combination functions, respectively; (1()) is initialized with node attribute X,. We obtain the output representation of each node after repeating the process in Equation
(20) for rounds. The representation the whole graph, denoted as lGg E Rd, can be obtained by using a READOUT function to combine the final node representations learned above:
hg READOUT
(1(2)) | v).
(21)
14

---

Under review as a conference paper at ICLR 2023
Table Original dataset details for imbalanced graph classification and imbalanced node classifica- tion tasks.
Task
Dataset
# Graphs
Nodes
# Edges
Features
Classes
MUTAG
188
17.93
19.79
2
PROTEINS
1,113
39.06
~2.82
D&D
1,178
284.32
771.66
2
Graph
NCI1
4,110
29.87
~32.30
2
PTC-MR
344
14.29
~ 14.69
2
DHER
756
42.43
444.54
2
REDDIT-B
2,000
429.63
497.75
2
Cora
2,485
5,069
1.433
Citeseer
2,110
3,668
3,703
6
Node
Pubmed
19,717
44,324
500
3
A-photo
7,650
238,162
745
8
A- A-computers
13,381
245,778
767
10
where the READOUT function can be any permutation invariant, like summation, averaging, etc. Graph Contrastive Learning. Given a graph dataset D = {G;); Graph Contrastive Learning (GCL) methods firstly implement proper transformations on each graph G; to generate two views G4 and G". The goal of GCL is to map samples within positive pairs closer in the hidden space, while those of the negative pairs are further. GCL methods are usually optimized by contrastive example, the contrastive loss is
loss. Taking the most popular InfoNCE loss (Oord et al., 2018) defined as:
exp (sim (Z.,1, 21,2))
LC G
log
(22)
11ر exp (sim (Zi,1, k5.2))
where Z, (C))
(G)). Zz,2 fo (G.),, and sim denotes the similarity function. Network Pruning. Given an over- over-parameterized deep neural network fe(-) with weights 0, the network pruning is usually performed layer-by-layer. The pruning process of the la layer in fo(-) can be formulated as follows:
g pruned TopK k), k: a x 10/0),
(23)
where glth the parameters in the Le layer of fe(-) and TopK(-, k) refers to the operation choose the top-k largest elements of glmn. We use a pre-defined sparse rate a to control the fraction of
parameters kept in the pruned network 8 Finally, only the top A: = |0/u)] largest weights will be kept in the pruned layer. The pruning process will be implemented iteratively to prune the parameters in each layer of deep neural network (Han al., 2015a).
C EXPERIMENTAL DETAILS
C.I DATASETS DETAILS
In this work, seven graph classification datasets and five node classification datasets are used to evaluate the effectiveness of our proposed model, we provided their detailed statistics in Table 4. For graph classification datasets, we follow the imbalance setting of (Wang al., 2021) to set the train- validation split as 25%/25% and change the imbalance ratio from 5:5 (balanced) to 1:9 (imbalanced). The rest of the dataset is used as the test set. The specified imbalance ratio of each dataset is clarified after its name in Table 5. For node classification datasets, we follow (Sen et al., 2008) to set the imbalance ratio of Cora, CiteSeer and PubMed as 10. Besides, the setting of Amazon-Phoo and Amazon Mmazzon-Computen are borrowed from (Park et al., 2022), where the imbalance ratio is set as 82 and 244, respectively.
C.2 BASELINE DETAILS
We compare model with variety of baseline methods using different rebalance methods:
15

---

Under review as a conference paper at ICLR 2023
1. For imbalanced graph classification (Wang et al., 2021), four models included baselines in our work, we list these baselines as follow:
(I) GIN (Xu et al., 2019), popular supervised GNN backbone for graph tasks due to its powerful expressiveness on graph structure;
(2) InfoGraph (Sun al., 2019), unsupervised graph learning framework by maximizing the mutual information between the whole graph and its local topology of different levels;
(3) GraphCL (You et al., 2020), learning unsupervised graph representations via maximizing the mutual information between the original graph and corresponding augmented views;
(4) GNN (Wang al., 2021), re-balanced GNN proposed utilize additional supervisory signals from both neighboring graphs and graphs themselves to alleviate the imbalance issue of graph.
IL For imbalanced node classification, consider nine baseline methods in our work, including
(I) vanilla, denoting that we train GCN normally without any extra rebalancing tricks;
(2) re-weight (Japkowicz & Stephen, 2002), denoting penalty of nodes in different classes;
cost-sensitive loss and re-weight the
(3) oversampling (Park et al., 2022), denoting that sample nodes of each class make the data's number each class reach the maximum number of corresponding class's s data;
(4) cRT (Kang al., 2020), a post-hoc correction method for decoupling output representations:
(5) PC Softmax (Hong et al., 2021), a post-hoc correction method for decoupling output representa- tions, too;
(6) DR-GCN (Shi et al., 2020), building virtual minority nodes and forces their features to be close to the neighbors of source minority node;
(7) GraphSMOTE (Zhao et al., 2021), a pre- pre-processing method that focuses on the input data and investigates the possibility of re-creating new nodes with minority features balance the training data.
(8) GraphENS (Park et al., 2022), proposing augmentation method to construct ego network from all nodes for learning minority representation.
(9) SynFlow (Tanaka et al., 2020), one-shot model pruning method with less reliance data.
(10) BGRL (Thakoor et al., 2021), a graph contrastive learning method using only simple augmen- tations and avoids the requirements for contrasting with negative examples, and thus makes itself scalable.
(11) GRACE (Zhu al., 2020). graph contrastive learning method generating two views by corrupting a graph and learning node embeddings by minimizing the distance of node embeddings in these two views.
We use Graph Convolutional Network (GCN) (Kipf & Welling, 2017) as the default architecture for all rebalance methods.
C.3 DETAILS OF GRAPHDEC VARIANTS
The details of model variants provided as follows:
I. Specifically, GraphDec contains four components to address data sparsity and imbalance: (1) GS is sampling informative subset data according to ranking gradients; (2) SS is training model with the sparse dataset, correspondingly; (3) CAD is using cosine annealing to reduce dataset size; (4) RS is recycling removed samples, correspondingly. To investigate their corresponding effectiveness, remove them correspondingly as:
(1) w/o GS is that we randomly sample subset from the full set;
(2) w/o SS is that we train GNN with the full set:
(3) w/o CAD is that directly reduce dataset size target dataset size and it is same data diet;
16

---

Under review as a conference paper at ICLR 2023
Table 5: Imbalanced graph classification results. The numbers after each dataset name indicate the imbalance ratios of minority to majority categories. We report the macro F1-score and micro Fl Fs-rc with the standard errors as Results are reported as mean std for 3 repetitions on each dataset. We bold the best performance.
Rehelanee Xithod
(3:45)
PROTEINS (30.270)
(20,200)
NCI (100:500)
Flana.
Fl-m
Fl-za
Fi-mi
Flora.
Fl-ms.
Fl-ra.
Fi-mi
Dis al, 2014))
18-70
16.77 2. 18.14
25:31
2-53
25.10 5.50
0.00 1. 7:41
11.08-3 9..9
18:21
15:04 7-12
GraphClL (1i al., 2000)
06.82
11:36
9.76
00.85
41.28
0.55
21.02
5.05
90.
33.02 1, 2.00
31.
3.00
GIN Diu et al, 2019)
75.08 7.02
29.77
7.67
06.44 + 2.67
71.56
9.10
41.35 8.74
70,56 10.29
09.15 + 4.90
71 80 7.02
up samplin
IndoCrath ot di.,
29.06
6.50
8.19 68:02
62
-281
GraphCI,
2000)
GIN DJu et al, 2019)
72.00 9: 0.60
12.06
9.30
50.64 1 4.23
55.75 0: 7.11
26.09 0.50
00.79 1: 11.89
36.54 0: 8:06
20.15 1000
woigg
InloCingth (Sun oi.. 20199
96.b 7:15
31.08
1.85
06.133-1
3.60
09.00
5.69
41.02
2.28
12.45
13:00 1:
1.81
GraghTT
63.00
50:00 6
GPONN (Wing et 2011)
resove slge
ausk mode
+..0
81.25 6.57
23.70
7:34
2.070
07:20 2.95
-..00-4.00
73.50
1..00-410
8.45 41.90
48.20 8.01
1903 + 10.79
17.00-00 - 9.98
03.50 + 1.67
94.75 + 2.56
74.01 -214
72.00 = 1.51
sparsity
6931-4435
44,01-
65.33-47
Robalance
Basis
PTC (9:81)
DHIR (12:108)
REDDITT i8 (50:450)
Method
F1-ma.
F1-mi.
P1-ma.
F1-mi.
F1-ma.
F1-ma.
(Xa et al., 2019)
17.74 + 6.49
20.30
0000=-.0000 6.06
25.96 + 8.87
49.46 + 4.50
50.19 + 14.26
36.012 + 17,38
vamilla
InfoCIngph (Sun et al., 2019)
25.85 6.14
26.71 101:6633 6.50
50.62 2: 9.53
56.95
2: 4.58
57.67
1: 3.80
67. 10 4.91
GraphCL (You et al. 2020)
24.22 1 6:21
26.16 5.25
50.55 10.01
56.31
8 6.12
53,40 :: 4.06
62.19 1: 5,68
GIN (Xi al., 2019)
44.78 2 8.01
65.43 = 14.25
55.96
10.05
50.30 6.55
66:71 = 3.92
83:00 5.18
up sampling
InfoGruph (Sun
2019)
$4.29 1 4.69
48,91
7.49
59.49 5.20
61:62 1.118
67.01 3.34
18.68 3.71
GraphCL, et 20100)
45.32 7.53
9.04
61.71
3.97
3,98
(Xa al., 2019)
14.08
43.09
20.01
05.16 9:47
57.7%
6.60
45.17
61,92 12:29
re-weight
IntoGraph (Sun ol., 20199
44.002+ 5.02
49.17 8.78
08.07 + 5,82
00:24:1
4.50
60.79
77.45 3.95
GraphCT. et al., 20200
44.75-1 7.62
62.22 = 13.24
00.87 2: 6.33
61.00:23 3: 5.15
62.70 2: 6.93
76.15 9.15
GNNNN (Wing et al. 202))
remove edge
46.40 7:73
56.61 13.72
61.63 10.02
63.61 1. 6.05
68.30 :1 2.97
80.35 2.27
mask sode
36.61 8:27
56.711 = 14.81
59.72 4: 0.85
01.27 +: 5.40
07.02 2 2.00
W5.43 4: 1,50
GraphDee
dynomic spaevity
47.07:8.222
58.15-10.33 10.24
62.25_99.54
63.61:7.10
69.70:27.20
97.60
Table 6: Imbalanced node classification results. We report the accuracy, balanced accuracy, and macro Fl-score with the standard errors as mean t std for 3 repetitions on each dataset (Due to time limitation, we will update GRACE, BGRL, and SynFlow's 's results with standard deviations in next manuscript). We bold the best performance.
Metted
Cladies
AC (2-244))
ABc
Fl
Age
B1 du
AM
Fl re)
F1 PM
Brfice
Fi He
66666 24
$100-677
+3.3388:1
(1:3::300
57.5 S5
51586843
33.8 3)
76.123351
10-Tg2111
9001-311
Suaflar Madker 3020
13:48
10.35
04.53
$175
5054
26.0
5191
$3.51
1502
walt millooe d. 2011
00.33
7558
75
55 55.829
5355g
6341g115
69.5533
the eeg (Pok 2007)
77 8s22 94
4.10.3331 15
114421 17
18-022311
01.123
Sakeec clkeg mil. m00r
19 472n
71 3333
65485 65
11 01201
181928235
51.122225
GapiSarr etal,
0931--077
3021-594
14:9--177
89-116044
(6901021
11:5-00
03333311
033:4333
0191-017
(4) w/o RS is not recyeling any removed samples.
II. Another four components to address model sparsity and data imbalance: (1) RM samples model weights according to ranking magnitudes; (2) SG is using sparse GNN, correspondingly: (3) CAG is using cosine annealing to progressively reduce sparse GNN's size; (4) RW is reactivating removed weights. To investigate their effectiveness, we remove them correspondingly as:
(1) w/o RM is that we randomly sample activated weights from full GNN model;
(2) w/o SG is that we train full GNN during forward and backward;
(3) w/o CAG is that we directly reduce the model size to target sparsity rate;
w/o RW is not reactivating any removed weights during sparse training.
C.4 FULL RESULTS WITH ERROR BARS
We provide the F1-macro and F1-micro scores along with their standard deviation for our model and other baselines across both graph classification and node classification tasks in Table and Table 6. We report their results as mean + sid for 3 repetitions on each metric for each dataset.
17

---

Under review as a conference paper at ICLR 2023
Full Model
Pruned Model
Gradient (10*)
Gradient (10²)
250
500
750
1000
250 500 750
1000
Figure 5: Results of data samples' gradients computed by full GNN model and our dynamic sparse GNN model on NCI1 data. Red dashed line: on the left side, points on the x-axis [0, 900] are majority class; on the right side, points on the x-axis [900, 1000] are minority class.
D FINDING INFORMATIVE SAMPLES BY SPARSE GNN
Compared with the full GNN model, our dynamic sparse GNN model more sensitive in recognizing informative data samples which can be empirically verified by Figure 5, As we can see in the figure, our dynamic pruned model assigns larger gradients to the minorities than the majorities during the contrastive training, while the full model generally assigns relatively uniform gradients for both of them. Thus, the proposed dynamically pruned model demonstrates its discriminatory ability on the minority class.
E RESOURCE COST
To evaluate the proposed GraphDec's computational cost on wide range of datasets, results in Table 7 that include three different class-imbalanced node classification datasets (PubMed-LT, Cora- LT. CiteSeer-LT) three different class-imbalanced graph classification datasets (MUTAG, PROTEINS. PTC.MR), and four baselines (vanilla GCN, re-weight, re(/over)-sample, GraphCL), We run 200 epochs for each method measure their computational time (second) for training. On NVIDIA GeForce RTX 3090 GPU device, we obtain the running time as reported in Table 7. All models are implemented in Py PyTorch Geometric (Fey & Lenssen, 2019).
Table 7: Computational time comparisons.
Model Method
PubMed-LT LT Cora-LT CiteSeer-Li LT
PROTEINS PTC_MR MUTAG
vanilla
2.436
2.154
2.129
12.798
4.295
2.989
re- re-weight
2,330
2.282
2.150
12,903
4.410
3.125
GCN
sample
3.241
2.860
2.794
15.996
5.734
4.022
GraphCL
3.747
3,412
3.399
14.981
5.049
3.215
GraphDec
2.243
1.995
1.952
10.614
4.212
2.090
According to the results, our GraphDec encounters less computation cost than prior methods. The following explains why augmentation doubles the input graph without increasing overall computation costs: (i) The augmentations we adopt (e.g. node dropping and edge dropping) reduce the size of input graphs (i.e., node number decreases 25%, edge number decreases 25-35%); (ii) During each epoch, our GraphDec prunes datasets so that approximately only 50% of the training data is used. (ii) GraphDec prunes the model weights, resulting lighter model requiring less computational resources. (iv) Despite the fact that augmentation doubles the number of input graphs, the additional new views only consume forward computational resources without requiring a backward weight update step, thereby only marginally increases the computation.
18


Reviews:
[{"review_id": "m0gp00mnz17", "reviewer": "Reviewer_ta4g", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper argues that current Graph Neural Networks (GNNs) suffer from high time cost when trained on massive data, and class-imbalance issue. The authors then propose GraphDec to address the problems by pruning both GNN and the training data.", "summary_of_the_review": "I vote for a reject. As pointed out in Weakness, the motivation of the paper is unclear, the proposed methods along with the theory seems to be irrelevant to the problems (the massiveness and class-imbalance in graphs) that the authors try to address, making the main methodology is full of tricks and the paper too technical.", "strength_and_weaknesses": "## Strength\n(+) The authors provide plentiful empirical results to show the effectiveness of GraphDec.\n\n## Weakness\n(-) Motivation is unclear. \n- Does the imbalance class problem really exist when massive training data is available? \n- Why do the authors choose self-supervised graph contrastive learning? If the model is learned in a self-supervised fashion, does it suffer from class-imbalance?\n\n(-) Key theoretical results seem to be irrelevant with GNNs, graph contrastive learning. Furthermore, I can not see the connections between the proposed methods and the theorem. \n\n(-) Moreover, class-imbalance issue seems not to be considered in method design, making the readers confusing about the improvements in experiments. \n\n(-) The main method seems not to consider any characteristics of graphs and GNNs, but a bag of tricks when applying Data Diet to graph contrastive learning.\n\n(-) The main method also introduces additional computation and memory overheads, which makes readers confusing about its advantages compared to existing graph contrastive learning, sparsity and class-imbalanced learning methods. Besides, the authors did not provide any efficiency checks such as complexity or the running time cost in experiments.\n\n(-) The authors did not compare other pruning methods and the state-of-the-art graph contrastive learning methods. The node classification experiments did not include graph contrastive learning methods either.\n\n(-) There are too many hyperparameters are introduced, but the authors did not test the sensitivity to these hyperparameters.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "gvQofgv_NzA", "reviewer": "Reviewer_9iT6", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper addresses the class-imbalance problem in graph learning. The authors propose Graph Decantation (GraphDec) framework for learning balanced graph representation in a self-supervised manner. The key procedure of GraphDec is to select some informative samples from unbalanced node data or graph data during training based on the gradient norm. The idea is interesting and novel, and the method is generally applicable to either node-level or graph-level class-imbalance situations.", "summary_of_the_review": "This is a technically sound paper with novel ideas on dynamic graph learning model and data sparsity, and its impact on the community is not restricted to the graph area. I believe that the experimental evaluation results are encouraging and sufficient. I would like to accept this novel and solid work. \n", "strength_and_weaknesses": "Strength:\n1. The idea of unifying dynamic informative subset selection and subnetwork selection during training is a first exploration and compelling. In addition, as a rebalancing method in this paper, data and model co-pruning do not require additional learnable weights or human-crafts hyperparameters. It can be used as a plug-and-play tool for other GNN models.\n\n2. The model design is well-driven by an intriguing hypothesis. It theoretically examines the extent to which a subset of the training data can approximate the learning efficiency of the entire dataset. Based on the hypothesis, the methods and experiments also demonstrate the rebalanced subset's gradients can effectively approximate the entire imbalanced dataset. \n\n3. The authors suggest Graph Decantation (GraphDec) as a solution to the difficulties posed by training on huge class-imbalanced graph data. Utilizing the self-pruned contrastive framework's sensitivity on informative samples to gradually refine a more balanced subset is an innovative approach. Consequently, this subset can reduce learning computation and train the model contributing more balanced predictions for classifying graph data.\n\n4. The experiments are sufficient and the improvement of GraphDec is significant. Particularly, the experiments studying the \"Evolution of Sparse Subset by Scoring All Samples\" are interesting, which supports the paper's motivation and inspires readers.\n\n\nWeakness:\n1. Does the idea of dynamically mining informative samples be applicable to some supervised frameworks? It will be nice to discuss the effect of applying the self-supervised learning (SSL) framework since the motivation for using SSL needs to be strengthened. Also, I think the problem of imbalance classification on the graph is very general among supervised and self-supervised settings. It is better to analyze the generality of GraphDec.\n\n2. When I see the GraphDec sorting neural weights and data samples for pruning, I am expecting the exact computation consumption of this model-data joint optimization can be clearly shown. I am not sure whether the method can actually trim down the computational cost.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "MKlf3E-baSw", "reviewer": "Reviewer_ZWS9", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper aims to solve both graph data imbalance and unnecessary model-level computation burden in a unified framework. Specifically, the authors first examine the challenges from theoretical and empirical perspectives. Then, the authors propose GraphDec, a novel data-model dynamic sparsity framework to address the challenges. Extensive experiments on multiple benchmark datasets demonstrate that GraphDec outperforms state-of-the-art methods.", "summary_of_the_review": "The paper address two significant challenges of imbalanced graph learning by designing a novel and effective model. The technical contribution is solid. The empirical explanations are interesting, and the experimental results are remarkable. ", "strength_and_weaknesses": "+This work is solid and insightful. The proposed framework investigates a new perspective in which sparsification can be utilized in both graph datasets and graph neural networks, which possess many advantages for real-world applications. For example, this work can be leveraged to detect important data points and conserve computational time.\n\n+The authors conduct comprehensive ablation studies to evaluate each model components, which clearly show the contributions of every module and the impact of rebalancing strategies.\nThe introduced components such as dynamically downsampling important subsets, and pruning contrastive model are empirically proven to contribute distinct positive impacts to the full framework. Despite employing a subset of the data, the proposed method achieves similar or better performance compared to the methods that utilize the entire dataset. \n\n+ The overall structure is based on an intriguing hypothesis with proof. The authors provide a hypothesis to explain why downsample a subset can estimate the entire graph dataset; they infer that the subset with the gradient closest to the gradient of the entire dataset is the most important. They then apply this inspiration to develop GraphDec. In addition, the inspiration provided by this hypothesis is also relevant for tasks in other domains (e.g., computer vision, natural language processing).\n\nWeakness/questions:\n-What is the purpose of training the contrastive learning system? Does this method exclude other learning schemes and supervised loss? The paper can be improved by highlighting the unique effect, such as a concise summary of the motivation and empirical ablation experiments.\n\n-Certain technical descriptions lack clarity for readers unfamiliar with coresets. In the experiment section, for instance, the word \"prune\" is sometimes used in a rather ambiguous manner. In the previous method section, it refers to the network, whereas in the experiment section, prune appears to be the \"sampling\" step of the dataset. The authors should provide additional information to explain the definitions of prune and sample on data and model or clarify that the terms are used in different sentences.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject