GraphENS: Neighbor-Aware Ego Network Synthesis for Class-Imbalanced Node Classification
Authors: Joonhyung Park
Jaeyun Song
Eunho Yang
Venue: ICLR 2022 Poster (2022)
Keywords: Deep learning
Node classification
Class imbalance
Data Augmentation

Abstract: In many real-world node classification scenarios, nodes are highly class-imbalanced, where graph neural networks (GNNs) can be readily biased to major class instances. Albeit existing class imbalance approaches in other domains can alleviate this issue to some extent, they do not consider the impact of message passing between nodes. In this paper, we hypothesize that overfitting to the neighbor sets of minor class due to message passing is a major challenge for class-imbalanced node classification. To tackle this issue, we propose GraphENS, a novel augmentation method that synthesizes the whole ego network for minor class (minor node and its one-hop neighbors) by combining two different ego networks based on their similarity. Additionally, we introduce a saliency-based node mixing method to exploit the abundant class-generic attributes of other nodes while blocking the injection of class-specific features. Our approach consistently outperforms the baselines over multiple node classification benchmark datasets and architectures.

Published as a conference paper at ICLR 2022
GRAPHENS:NEIGHBOR-AAWE EGO NETWORK SYN- THESIS FOR CLASS-IMBALANCED NODE CLASSIFICA- TION
Joonhyung Parkln, Jaeyun Song'", Eunho Yang!.
Korea Advanced Institute of Science and Technology (KAIST)), AITRICS (deepjoon, mercery, eunhoy (aahoy)kkakn sraboyy@kaist.ac.k.
ABSTRACT
In many real-world node classification scenarios, nodes are highly class- imbalanced, where graph neural networks (GNNs) can be readily biased to ma- jor class instances. Albeit existing class imbalance approaches in other domains can alleviate this issue to some extent, they do not consider the impact of mes- sage passing between nodes. In this paper, we hypothesize that overfitting the neighbor sets of minor class due to message passing is a major challenge for class-imbalanced node classification. To tackle this issue, we propose GraphENS, a novel augmentation method that synthesizes the whole ego network for minor class (minor node and its one-hop neighbors) by combining two different ego networks based on their similarity. Additionally, we introduce a saliency- saliency-based node mixing method exploit the abundant glass-generic attributes of other nodes while blocking the injection of class-specific features. Our approach consistently outperforms baselines over multiple node classification benchmark datasets.
INTRODUCTION
Node classification graphs has attracted significant attention the importance of large-scale graphs analysis increases various domains such as bioinformatics and commercial graphs to name few (Perozzi et al., 2016; Hamilton et al., 2017; Ying et al., 2018; Mohammadrezaei et al., 2018). For example, in retail services, acquiring the qualitative node representations for items or customers critical for improving the quality of recommendation systems (Perozzi al., 2016; Ying et al., 2018). Detecting abnormal users in social networks, as another example, is also closely related to classifying the property of each node (Mohammadrezaei et al., 2018). Recently, Graph Neural Networks (GNNs) have demonstrated their effectiveness on learning node representations (Hamilton al., 2017; Kipf& & Welling, 2017; Velickovic et al.). However, the nodes in many real-world graphs inherently class-imbalanced (Mohammadrezaei et al., 2018; Wang et al., 2020a), hence GNNs are prone to be biased toward major classes, as general class-imbalance tasks. This bias forces networks to poorly classify the nodes of minor classes, resulting in destructive impacts and large cost to their services.
While the peculiar characteristics of imbalanced node classification and specialized solutions suit- able for it have hardly been investigated, applying generic imbalance handling methods (Chawla al., 2002; Cui et al., 2019; Cao al., 2019; Kang et al., 2020; Menon et al., 2021) directly to the graph domain has several non-trivial challenges. One of the distinct natures of graph data is that adjacent nodes are involved in constructing the representation of each node, which makes the model more confused to learn the unbiased representation of minor class nodes. Here, we hypoth- esize that is in fact more serious overfitting to neighbors of minor nodes than overfitting to the node feature itself. This 'neighbor memorization' is the critical obstacle to naively adopt the class-imbalance approaches of other domains such re-weighting and re-sampling used in image classification. Specifically, re- re-weighting approaches (Cui et al., 2019; Tan et al., 2020; Cao et al., 2019; Menon et al., 2021; Hong et al., 2021), applying penalties according to the number of data, simply assign large weight minor nodes, hence there is no change in neighbor sets of minor nodes
Equal contribution.

---

Published as a conference paper at ICLR 2022
observed during training. Re- Re-sampling methods (Chawla et al., 2002; Kang et al., 2020; Zhang et al., 2021: Wang et al., 2021), sampling data to balance the number of data for each class, are also vulner- able to overfit on minor nodes with their neighbors. Another challenge of the re-sampling method, especially for oversampling variants, is determining how to connect the newly sampled nodes to the original graph. For example, simply connecting the original node will change the edges of neighbor nodes as well and hence significantly alter the message passing to the neighbors, which might impair their class semantics. To mitigate this issue, GraphSMOTE (Zhao et al., 2021) exploits edge predictor to decide the connectivity with the neigh- bors of two minor nodes used in oversampling. Nevertheless, GNNs trained with GraphSMOTE still suffer from neighbor memorization when the number of minor nodes is limited.
oversampled node with all neighbors of
In this paper, we propose GraphENS, novel augmentation approach that synthesizes the whole ego network for minor class (minor node and its one-hop neighbors) by interpolating two different ego networks in the data; to enlarge the limited neighbor views of minor instances the data, our method combines the ego network of anchoring minor node with that of randomly selected node from all classes, where it interpolates ego networks based on KL-divergence between model predictions of ego networks in order to keep the semantics of minor classes. Synthesized ego networks are attached to the original graph to construct a class-balanced graph, and GNNs are trained with the enlarged graph. GraphENS enables the model to learn the minor class nodes with feasible neighbors by generating the virtual ego networks.
To further prevent the synthesis of deleterious ego networks, introduce saliency-based node mixing approach to generate the central node of ego network. Our method separates class-generic node features from class-specific node features by using saliency information of each feature and exploits only class-generic attributes to combine with node feature of anchoring minor node. We validate our method on various benchmark datasets including citation networks (Sen et al., 2008), and Amazon product co-purchasing networks (Shchur et al., 2018) with diverse architectures such as GCN (Kipf & Welling, 2017), GAT (Velickovic et al.), and GraphSAGE (Hamilton et al., 2017), and confirm that our approach consistently outperforms baseline methods over various settings.
In summary, our contribution is threefold:
We demonstrate that in class-imbalanced node classification, GNNs severely overfit to neighbor sets of minor class nodes, rather than to minor nodes themselves. This 'neigh- bor memorization' problem becomes severe when the number of minor nodes is extremely small.
Our method effectively alleviates the neighbor memorization problem in class-imbalanced graphs by synthesizing feasible ego networks based on the similarity between source ego networks. We also block the injection of harmful features in generating the mixed nodes using node feature saliency.
Through extensive experiments, we show that our approach consistently outperforms base- lines multiple benchmark datasets including real-world imbalanced datasets. Even in highly imbalanced synthetic graphs, our method exhibits superior performance.
2 RELATED WORK AND PRELIMINARY
2.1 CLASS IMBALANCE PROBLEM
The goal of class-imbalance handling in classification is to construct an unbiased classifier to the label distribution of the training set. There are three main streams: loss modification, post-hoc correction, and re-sampling approaches. Loss modification methods alter the objective function to assign more weights (Japkowicz& & Stephen, 2002; Cui et al., 2019) or margins (Tan et al., 2020; Cao et al., 2019; Menon et al., 2021) on minor classes. Post-hoc correction strategies (Kang et al., 2020; Tian et al., 2020; Menon et al., 2021; Hong et al., 2021) remedy logits to compensate minor classes in the inference. Re-sampling approaches augment minor class data by sampling strategies (Kang et al., 2020; Liu et al., 2020; Ren et al., 2020) or generation (Chawla et al., 2002; Kim et al., 2020a; Chu et al., 2020: Zhang et al., 2021; Wang et al., 2021). Among minor class generation approaches, SMOTE (Chawla et al., 2002) is widely used method to mix minor data with the nearest data of the identical class. Synthesizing minor class data from data of other classes (Kim et al., 2020a; Chu
2

---

Published as a conference paper at ICLR 2022
et al., 2020; Wang al., 2021) is introduced to exploit the rich information of other classes. Kim et al. (2020a) produces new minor class data by taking gradient steps to translate major class data into minor class data. Wang et al. (2021) synthesizes minor class data by combining features of minor class data with feature displacements of other data. To extend these approaches to the graph domain, structural aspects of graph have to be considered when generating minor instances.
In node classification, imbalance handling works (Zhou et al., 2018; Wang et al., 2020b; Shi et al., 2020; Zhao al., 2021; Qu et al., 2021) are proposed to exploit structural information in graphs. DR-GCN (Shi et al., 2020) produces the virtual minor nodes generated by additional conditional GAN and regularizes the features of virtual nodes close adjacent nodes. GraphSMOTE (Zhao et al., 2021) generates synthetic minor nodes by interpolating two minor class nodes and (pre- trained) edge predictor determines the connectivity of synthesized nodes between synthesized nodes and neighbors of two source minor nodes. ImGAGN (Qu et al., 2021) synthesizes minor nodes by interpolating features among whole minor nodes with the generated weight matrix. Then the synthesized nodes are connected to the original minor nodes if weights in the matrix are larger than a fixed threshold. As GraphSMOTE and ImGAGN only utilize nodes of the identical minor class to generate minor nodes, the sample diversity of synthesized nodes would be significantly constrained. Moreover, ImGAGN mainly targets binary classification and its extension to multi-class classification is non-trivial since independent generator is required per each class. Compared to these approaches, our GraphENS utilizes whole nodes to synthesize minor nodes, thus our method outperforms baselines when the number of minor classes low in Section 5.3 (Table 4).
2.2 GRAPH NEURAL NETWORKS FOR NODE CLASSIFICATION
We briefly introduce GNNs for node classification tasks. Let us first define graph G(V, E) where V is the set of nodes and E is the set of edges between two nodes. Let X E [ be the node features whose the i-th row represents the d-dimensional feature of the i-th node. ((v) is the set of adjacent nodes that are directly connected to v: {u E VH,, v} E}. In node classification, each node in the graph corresponds to a class y E {l....,C, ... where C is the number of classes. In this paper, consider several variants of GNNs that consists of three differentiable functions: 1) message function mi, 2) permutation invariant message aggregation function 61, and 3) node update function h4. Let (1) be the latent vector of node at layer l. To simplify notations for the recursive definition of GNNs, we use ( to denote the input node feature. At each GNN layer,
node features are updated as xb (!+1) = hu(x"" der (b(((ma(=))) (1) .,((), eu E (N()))) to consider adjacent node embeddings. By passing these aggregated node features to a linear classifier as input, we obtain the prediction ÿ = fxx)) for node v where de = P(y = clr,). As representative example, a layer of Graph Convolutional Network (GCN) (Kipf & Welling, 2017) is defined as te (1+1) = + (wEN(())))r)) Vä,d,
11 6v.. Tu where d, = 11 EnEN((()) En,a with e,,, is the edge weight
of edge (u, E E and θ is a filter parameters. There are several variants depending on how these key components are designed, but they are beyond scope of our work.
3 NEIGHBOR MEMORIZATION PROBLEM
In this section, we define and investigate the neighbor memorization problem uniquely appear- ing in the node classification task of a ilas--ibbllnnced graph. Conventional imbalance handling approaches such as re-weighting and oversampling enable the model to train in a class-balanced manner. However, these methods are vulnerable to overfit toward minor classes (Zhou et al., 2020) since they solely assign large weights on limited minor instances in the training phase. In the node classification task, the unique characteristics of this task, which have not been considered until now, should be considered: not only overfitting to the minor node feature Uminar, but also overfitting to N (Uminnr) can be an issue. That is, the model exposed to highly restricted neighboring structures for minor classes. Here, since GNN models are based on message passing that receives informa- tion from (a number of) neighboring nodes, we hypothesize that the overfitting and memorizing A (Uminor) can be more serious than overfitting to Uninor, and we experimentally verify that below.
Experimental setup We first conduct experiments to observe overfitting to minor classes on class- imbalanced graphs. GNNs are trained with two widely used methods- re-weighting and over-
3

---

Published as a conference paper at ICLR 2022
200
Seen
unseen
Accuracy (%)
0.5
Accuracy
70
Re-we weighiinggg
02
Oversampling
0.2
GraphENS
0.0
Epach
0.
Epach
150
RW
05
Ours
RW
G5
Ours
(a) Train ACc Curve
(b) Test Acc Curve
(c) Node- dede-Repp
(d) Neighbor-Repllainn
Figure 1: The results for overfitting to minor classes, node memorization, and neighbor memorization. Dash lines are learning curves including all classes and solid lines are learning curves for the minor class in (a) and (b). In (c). the blue/red bars indicate the accuracy of seen/unseen nodes with seen neighbors in the node- replacing experiments. In (d), bluefred bars denote the accuracy of seen nodes with seen/unseen neighbors in the weighbor-replacing experiments. Note that RW and OS represent re- re-weighting and oversampling.
sampling on a node classification benchmark dataset, PubMed (Sen et al., 2008). We process the PubMed dataset follow a long-taile distribution by well-known construction rule in the vision domain (Cui et al., 2019). The imbalance ratio between the numbers of the most frequent class and the least frequent class is set as 100. We fix architecture as the 2-layer GraphSAGE having 256 hidden dimension and train models for 2000 epochs. We select the model by the validation accuracy.
Overfitting to minor classes The learning curves of imbalance handling approaches are presented in Figure (a) and (b). The solid lines and the dash lines are the curves of minor class accuracy and overall accuracy, respectively. We observe that the test accuracy of the minor class is much lower than the overall accuracy while the training accuracy of the minor class is extremely high. This result implies that the existing approaches are prone memorize minor class nodes. Note that only present the learning curves for the first 200 epochs to show the tendency of the early phase more clearly. We confirm the test accuracy differences between minor classes and all classes almost maintained until the last epoch for both methods. The learning curve for entire epochs is in Appendix A.2 (Figure 4). In the following paragraph, investigate more specifically whether this overfitting is mainly due to memorizing node features or their neighbor structures.
Neighbor memorization problem To investigate how seriously GNN is prone to be overfitting to self node features or aggregated features from neighbors, we design two 'replacing' experiments. In the first replacing experiment, we scrutinize 'node memorization' where GNNs memorize seen minor node features excessively. We intentionally replace seen minor node with an unseen minor node given fixed seen neighbors (node-replacing experiment). Toward this, we randomly sample three nodes from the identical minor class: we sample Vanchor (recipient), Useen (donator) from the training set and Vunseen (donator) from the test set. We then replace the feature of fanchor with that of Tunseen in the original graph and evaluate the classification accuracy of replaced Vonchor. That is, the replaced feature of Vanchor is not exposed during training, but its neighbor view does. For comparison, we replace the feature of Vanchor with of Useen as a baseline; it is the case of seen node features and neighbors but it has the artifact of grafting. We measure the accuracy for all minor test nodes and experiments are repeated 50 times, In Figure (cc), the blue and red bars represent the results of Canchor with seen node features and Vanchor with unseen node features, respectively.
Now, we conduct similar experiment for 'neighbor memorization'. We would like to estimate how much GNN relies on seen topological structures. To this end, we measure the performance degradation when the seen neighbor set is replaced by an unseen neighbor set given a fixed seen self- node feature (neighbor-replacing experiment). We sample Useen (donator) and Vanchor (recipient) from the training set and Vanseen (recipient) from the test set as before, but Vanchor now has different role compared to the node-replacing experiment: it serves as providing a seen neighbor set. Specifically, we replace the feature of Vanseen with that of Useen, which represents the situation where a seen node embedded into unseen neighbors. Then, we evaluate the classification accuracy of replaced Vunseen- For baseline. the node feature of Vanckor is replaced by that of Useen and measures the accuracy of replaced V it is the case of seen node feature with a seen neighbor set. In Figure (d)) the blue bar denotes the performance of seen node feature with seen neighbor set
4

---

Published as a conference paper at ICLR 2022
Pinnor
Minor Network
Pmixed
(b) Saliency-based Node Mixing
Attach
Neighbor Sampling
Vtargel
Target Ego Network
Synthesized Ego
(a) Neighbor Sampling
Saliency based Node
Combination
Lul.
Pitixed
0 p(u(Painee)
divergence
Sample
Masking Salient
0 p(u(Pnargue)
Vtarget
Masitd Ptarget
Figure 2: Overall pipeline of GraphENS. Uminor is node sampled from minor class to augmented
(oversampled). Ubarget is a node sampled from the entire class and exploited to synthesize the ego network.
and the red bar represents the performance of seen node feature with an unseen neighbor set. The overall procedure is described by Figure 8 in Appendix D.
We demonstrate that conventional imbalance handling approaches severely suffer from neighbor memorization problem in Figure I(c) and (d) The performance drop of conventional algorithms in the neighbor-replacing experiment steeper than in the node-replacing setting. These results imply that the neighbor memorization problem is a critical obstacle in properly handling the class- imbalanced problem in node classification tasks.
From the learning curves and replacing experiments, we find that conventional approaches to handle imbalanced data largely rely on neighbor information. This neighbor memorization problem results the minor class, it must be appropriately addressed in
in poor generalization performance class-imbalanced node classification. Recent work, GraphSMOTE (Zhao et al., 2021), connects mixed node to neighbors of both the source node and target node in the same class, and then removes the unreliable edges by the fcature similarity- only utilizes the neighbors of the seed nodes in the identical class, it still prone to memorize the neighbors of minor classes when the number of minor class nodes is extremely limited.
edge predictor. However, since GraphSMOTE
GRAPHENS
We now describe our novel class- insss-iibbllnce handling strategy for node classification, GraphENS that synthesizes an ego network for generated minor nodes considering the prediction similarity of the ego network instances, order to alleviate the neighbor memorization described above. GraphENS mainly composed of two core components. Both components exploit the features from two nodes: the minor class node Uminor and the target node Utarget from entire classes' to synthesize an ego network of minor class. The first component is to augment the neighbor set by combining neighbors of a minor node Uminor with those the target node Utarget. To prevent the generation of harmful ego networks, GraphENS regulates the combination ratio depending the KL divergence between ego networks centered on Uminor and Utarget: respectively (Section 4.1). The second component of GraphENS defines the node feature saliency for GNNs that represents the importance of each node feature in classifying the node property. Equipped with this node feature saliency, GraphENS mixes Uminar and Utarget to generate a central node and combine with the ego network synthesized above (Section 4.2). This feature saliency information is utilized to filter out the class-specind node features in the node feature mixing process to preserve the semantics the minor class. The overall procedure of GraphENS is described in Figure 2. Our full algorithm is also provided in the Appendix E (Algorithm 1). We discuss the details of each component in the following subsections.
To reduce the negative effect of oversampling on passaggepassing. we make the message passing work only on incoming edges to the oversampled nodes. Detailed explamation and justification for this strategy for target node selection are discussed in Section 5.2.

---

Published as a conference paper at ICLR 2022
4.1 NEIGHBOR SAMPLING
Neighbor sampling is a method to determine which nodes to be connected to a new mixed node, Umiaed (how synthesize mixed node is described in Section 4.2). The goal of neighbor sampling is to expose minor nodes to various environments to mitigate neighbor memorization problem while preventing the generation of harmful connections. To provide diverse neighbor sets, we construct 'adjacent node distribution' for mixed node from two ego networks of Uminor and Utarget and stochastically sample the neighbors from this distribution. At the same time, regarding the avoidance of detrimental connectivity, we devise a scheme that reflects N (Vtargett) more in constructing the adjacent node distribution when the ego network of Utarget is more similar to that of Uminor. Note that the ego network G, of node consists of (Nr Uv} nodes and edges directly connected to the central node v. The overall scheme of neighbor sampling is in Figure 2 (a).
Constructing adjacent node distribution Now, we build the similarity aware adjacent node dis- tribution for Umized by mixing adjacent node distributions of Uminor and Utarget- Here, the adja- cency node distribution for a real node v, p(u/e), is defined as p(ulu) = [o) and p(ule) 0 otherwise. To construct 'probable" adjacent node distribution, the mixing ratio is determined based on the similarity between the ego networks of Geminor and Gueargu Toward this, we utilize logits O2 f(G), for node given the full graph G as input of GNN f since GNN aggregates neighbor information with self node feature. It is worth noting that the logits can be obtained without additional cost (we can bring the model confidences the previous epoch). To further reflect the neighbor information explicitly and avoid the overconfidence problem, we aggregate adjacent logits and utilize these logits to compute the similarity. Specifically, the ag- gregated logit of node is computed as ô, = WHl EnE(M(()un) On. Then, we calculate the KL-divergence between Ôminor and Ötarger to estimate the distance between Granveer and G Grarrati where a is a softmax function. Now, the normalized distance is 1
1 if E V, {u, v} E E,
é = K L (a (lor used as the mixing ratio for the minor adjacent node distribution, and it is calculated as & 1 Finally, the adjacent node distribution for the synthesized Umized is defined as
p(u ((u(umized) = p( [u] Uminor) + (1 ②) p(u) Vtartttrr)))) Note here that the mixing ratio of the target node decreases as the distance from the minor node increases and the mixing ratio of anchoring minor node is guaranteed to be at least 0.5.
(1)
Sampling neighbors Given the adjacent node distribution p(u Umized) in Equation 1, we sample neighbors from this distribution without replacement. The number of neighbors is sampled from the degree distribution of given graph to keep degree statistics with the original graph. Not only that, we make the message passing work only on the incoming edges to Umized since undirected edges affect message passing in the original graph.
4.2 SALIENCY-BASED NODE MIXING
We now describe how our method synthesizes new central node Umized of Gemazed by interpolating two nodes Unzinor and Utarget- Note that our method does not restrict the target node to be from mi- nor classes to utilize the abundant class-generie information of other classes. To extract only generic attributes independent of class, we first define the node feature saliency to identify the importance of each node feature. Armed with this node feature saliency, GraphENS synthesizes new minor node Umined using minor node features and generic features of target node via convex combination.
Feature saliency Albeit GraphENS does not depend specific ways of calculating the impor- tance of each node attribute, we simply adopt an approach that evaluates the importance of node features based on gradients. In particular, motivated by the works using the gradient of the loss function with respect to input features in image classifications (Simonyan et al., 2013; Shrikumar et al., 2017), we define the feature saliency follows.
We first compute the gradient of classification loss L(G with respect to the input node feature matrix dc
ax E RlVlxd via backpropagation. Then, the saliency value of i-th feature ((,.) is obtained
(c((G.))
by the magnitude of the gradient regarding i-th attribute in node e as 8(u,)) =
.The
0x
(v.1)

---

Published as a conference paper at ICLR 2022
feature saliency vector S, architecture. Our gradient- based feature saliency can be derived without additional backpropagation as we simply exploit the gradient values computed from the previous training iteration.
(v. 1). (...))).....))))). ((r,))) 1 is derived without any modification to the GNN
Node mixup We introduce our simple mixup-like augmentation to oversample the minor nodes without label mixing. Since we select target nodes Utarget from all classes unlike SMOTE (Chawla et al., 2002), filtering (or masking) out class-specific attributes of the target node required to prevent the generation of noisy samples. To this end, we explicitly utilize the feature saliency infor- mation of the target node.
First, we determine the masking ratio K% using a normalized distance é (from Section 4.1). As é implies the distance between two ego networks centralized by Uminor and Umajor. we adaptively assign K% proportional to normalized distance Φ; K kō where l is hyperparameter. The intuition behind here is if target node Utarget is significantly differ from minor node Uminors we mask more salient features of Utarget- Specifically, given the feature saliency vector S Stargges binary mask MM E Rd which masks the K% of node attributes 0, is sampled from multinomial distribution by applying softmax to Spmrege Our final synthesized minor nodes Umired can be formulated as follows given a random mixing ratio Beta(a, a):
Uymiandd = (1 Ax) C Uminor + A @ Starget, where AK = X MM-
(2)
We also evaluate our method but without using saliency on multiple datasets in Section 5.4 (Table 3).
5 EXPERIMENT
5.1 EXPERIMENT SETUP
Datasets We validate GraphENS on five benchmark datasets: Cora, CiteSeer, PubMed for citation networks (Sen et al., 2008), AmazonPhoto and AmazonComputers for co-purchase graphs (Shchur et al., 2018). For citation networks, we follow splits in Yang et al. (2016). In supervised learning setting, we construct long-tailed citation networks following Cui et al. (2019) to validate models at high imbalance ratio, which denotes the ratio between the most frequent class and the least frequent class. Nodes are removed until the class distribution follows a long-tailed distribution with keeping the connection in graphs most. We sort the classes from major class to minor class and then remove nodes for each class started from major classes. When eliminating nodes, we remove nodes having low degrees and the corresponding edges of those nodes. We also evaluate imbalance handling methods on natural imbalanced datasets such as AmazonPhoto and AmazonComputers. To make validation/test sets balanced, we sample the same number of nodes from each class for validation/test sets. Then, the remaining nodes are assigned to the training set. We fix the least number of train nodes for all classes as 20. semi-supervised setting, we set the imbalance ratio as 10. The detailed setup is provided in Appendix F.5.
Baselines We test our methods over three architectures GCN (Kipf & Welling, 2017), GAT (Velickovic et al.), and GraphSAGE (Hamilton et al., 2017). We adopt re-weight as cost- sensitive loss (Japkowicz & Stephen, 2002) inversely proportional Oversampling is the approach that samples each class node until the number of each class data reaches the maximum number of class data. For oversampling, we duplicate the edges of the orig- inal node when adding an oversampled node to the original graph. cRT (Kang et al., 2020) and PC Softmax (Hong al., 2021) are recent effective baselines for decoupling and post-hoc correc- tion approaches, respectively. DR-GCN generates virtual minor nodes and forces virtual nodes to be similar to the neighbors of a source node. Although DR-GCN has an additional component to exploit entire unlabeled nodes for semi-supervised learning, we do not consider this component for a fair comparison. GraphSMOTE (Zhao et al., 2021) has two versions, depending on whether the predicted edges are discrete continuous values. We adopt discrete version of GraphSMOTE since it exhibits superior performance on multiple benchmark datasets. Implementation details of ours and description of evaluation protocol are deferred to Appendix F.
the number of class data.
7

---

Published as a conference paper at ICLR 2022
Table 1: Comparison of our method GraphENS with other baselines in extremely class-imbalanced settings (Imbalance vatio:/00), We report the averaged accuracy, balanced accuracy, and Fi-score with the standard errors for 5 repetitions on three benchmark datasets for node classification tasks.
Method
Con--777'
CiteSeerJ.TT
PuhMedd-/7
Acc.
bAce.
Fi
Acc.
bAcc.
Fi
Acc.
bAcc.
Fi
Vanilla
73,66
62.72 20:30
63,70
20.43
53.90
47.32 as
43.00
70.76 29.74
$7.56 20.39
51.88
Re: Weight
75,20 20.13
68.79 so.1s
69.27
50.25
62.56 00.52
55.80 so.2e
53.74
10.20
77.44 so.21
72.80 sn.35
73.66
=0.27
Ovenampling
77.44 20.00
70.73 20.10
72.40 :0.11
62.78
+0.37
56.00 2x..s
53.99
20.3T
76.70
20.45
68.49
=0:25
69.50
=0:35
cRT
76.54
69.26
70.95
60.60
54.05
52.36
75.10
29:25
67.52
68.08
Softmax
50.34
71.30 sp.43
71.24 =0.52
+0.42
so.40
+0.40
76.92 20.25
75.82
n9.23
74.19 =0.23
DR- DR-GON
73.90 20.23
64.30 20:30
63.10 29.57
56.18 $1.30
19:57 s2.00
44.98 #1.20
72.38 20.19
58.86 20.15
$3.05 =0.13
GrapISMOTE
76.76 20:33
69.31 20:37
70.21 20:01
62 62.58 20.30
55 94 an.s4
$4.09
75.98
29:23
70.96
71,85 20.02
GraphENS
77.76
72.94
73.15
66.92
58.67
78.12
74.13
74.58
Vanilla
73.60 20.45
62.75 20.37
63.53
29.35
56.76 19.39
50.15 10:34
46.59
20.45
71,26
20.27
58.86 :0.55
51,91
23.12
Re Weight
77,26
71.97
71.37
63 54
56
98
$5.30
78.14
75.80
20:34
76.07
Oversampling
77.50 10.12
71.16 2p.14
72.58 so.19
+0.20
+0.22
s0.37
76.96 00.24
70.71
a9.23
72.29
=0.20
GNT
cKT
76.74 20:30
69.19 20.52
70.60 =9.57
60.50 25.55
51.18 +0.50
52.33 20.70
73.76 20.25
65.69 21:25
66.40 =0.27
PC Softmax
76.62 20.15
73.14 20.19
72.6
10.19
62 20
59.49
axt 40
59.51 2:.33
7K.70 20.50
75:40
75.96
20
DR-GON
74.42
64.17
64
o7
56
50.02
45,82
71.52
59.18
54.879
GraphSMOTE
76.92 20.33
70.03 29.51
70:17 29.55
57.33 +0.39
55.43 $0.49
77.12 29.40
73.59 #1.15
74.40
=0.72
GrapheNS
78.10 10
73.45 19
73.48
go 19
66.90 gn
60.30
gm1.0 so
58, 70
am 20
78.24
20
74.27 go:as
74.68 g0
Vanilla
72,08
61.97
61.90 97
50 50.76
44.5 56
40.43
64.54
$3.07
80.
CrapSSAGE
Ovenampling
Reigeigh
74,88 20.44
74.38 20.40
66.20
68.24 20.55
21
66. 36 #1:11
69.28 $0.96
59 19.79
58 64 11:17
51.76 $1.17
$2.73 20.01
49:42 2:.40
50.12
$1.01
69.36 29:13
69.78 20.35
62.15 20:3
67.06 #1.79
62.46
65.69 20.66
20.74
oRT
73.52
63.65
29:77
64.65
51 10
45.04 20.30
42.02
67.50
20
56.76
54,04
PC Softmax
20:73
=0.72
20.28
20.36
$0.46
74.96 29.35
74,28
21:33
73.32 =0.41
DR-GON
23.28 20.45
63.32 20.05
62.95 12
50.80 1:n
44.51 20:41
39.02
20.55
64.90 20.03
$2.84 20.42
47.56 20:41
GrapSSMOTE
24.34 20.0
64.76
20:09
65
50
58 98 1:0
52.11 1..38
50.27
70.02 20:01
63.04
2007
63,43
GraphENS
77.26
70017
70.25
63.98
57.33
55.23
79.60
74,90
75.83
Table 2: Results on AmazonPhoto and AmazonComputers in Table 3: Ablation study. SM. NS, and comparison to baselines. The experiment was repeated 5 times and PS denote saliency masking, neighbor sam- standard errors reported. Note that the Acc. equal bAcc. pling, and prediction similarity, respectively. as the test sets are balanced.
CiteSeer semi
AmazonPhoto (lubalance natle:
AmazomPaoto (Imbalance rati::
AmuzzonCanpuute
Method
Unbbaionce ratio:
Method
82)
Umbalaace ranio: 244)
Acc bAce.
F1
Ace. bAve.
Fl
Aec.bbAcc))
Acc. (bAcc.))
F1
GaspPENS
Vanilla
82,86 20.30
78.72 20052
68.47 12.19
64.01
13.18
Owl SM.
41,82
39.31
32,15
93.17
93.17 93.15
GraplSAGE
"Ri-Weighit
92.04 1o.13
99.95
13.13
96.04 10.29
90.11
1:0.6
GraphENS
Ovensampling
92.46 20.47
92.47
20046
89.79
10.16
89.85
10
(wio SM)
49.24 48.77 45.85
93.54 93.54
93.53
cRT
91.24 10.28
91.17
1:0.2
86,02
10.55
86.00
1.0.6
GosphENS
GraphSMOTE
93.32 +0.25
92.65 20.31
92.61 #0.32
4:0.25
$6.59
89.31 #0.34
+00.2
89.39
86.62
+0035
+-0.91
(wdo PS)
47.96
93.28
93.28
93.26
GraphENS
93.82 +0.13
#0.12
91,94 #0.17
91.94 100.17
GraphKN8 51.12
48.91 46.78
93.82
93.83
93.81
5.2
TARGET NODE SELECTION
Cora LT
CiteSeor LT
Our method utilizes the target node Utarget from all classes, not only from the identical minor class Uminor. The inten-
tion of constructing the target node pool from entire classes
is to guarantee sufficient diversity of synthesized ego net- works. If the target nodes restricted to minor class
at highly imbalanced scenarios, identical neighhor nodes
Lokce [4] PL--Cow [S] DACC [S] Flacore [X]
Target Node Yhag Selection
would be redundantly duplicated. This issue makes it hard Figure 3: Target node experiments (GAT).
to mitigate the neighbor memorization problem. To demonstrate this hypothesis, we conduct an
experiment and compare our design choice (all classes) to select a target from the identical class as the minor node Uminor. In the Figure 3, we confirm that exploiting entire classes for the target node suppe
achieves superior performances. From this design choice of the target node, our method can utilize
the manifold assumption that "similar predictions of neural networks indicate the close proximity in the manifold', which are commonly utilized in semi-supervised learning (Van Engelen & Hoos, 2020). We aim to enlarge and smooth the decision boundary of the minor class by interpolating the minor nodes and the target node of the entire classes (but excluding target-specifie attributes using saliency) investigated in Verma et al. (2019). Moreover, our method considers the prediction of the ego network (not a single node) to reflect the structural aspects of graph.
To select target node, (logNN, log. logNe) where N, is the number of the i-th class data and C. is the number of classes. Then, we randomly select target node from the training nodes of the sampled class.
sample target class from the multinomial distribution with
8

---

Published as a conference paper at ICLR 2022
Table 4: Comparison of our method GraphENS with other baselines in semi-supervised learning settings. We
report the averaged accuracy, balanced accuracy, and Fl-score with the standard crrors for 5 repetitions.
Method
Cora-
CiteSeer Somi
Acc:
bAce:
Acc:
bAoc:
F1
Acc.
bAoc:
F1
Vanilla
68.38
62,04
60.92
39 32
18
34,5
59.52
63.
58,
"Ro- "Ro-Weighi"
Y1.00 1.:1a
68.00 21:45
65.09 11
10
21:41
50.88
21:1
33.13
68.10
25:47
669.02 19.00
67:70
23:00
Oversampling
65.20 11.15
60.61 20.55
59.57 11.71
43.56 23.02
42.27
23.0
36.68 14.81
64.94 23:24
68.48 #2.35
63. $3.05
cRT
68.99 1::00
62.65
61.74 21:45
41.42
42.17
20:44
36.38 10:00
58.38
63.10
57.95
Sofmmx
#1.33
$1.09
20.85
+0.81
#1.08
DR-GCN
66.84 2:102
59.94 #2.77
58.21 1:1.0
42.52
=1:00
41.16 21:40
35.89 $1.00
59.64 #2:13
64.32 22.37
59.09 =1:2:
GimphSMore:
69 69.20 2:
63.43 22:13
62.35
20.50
44.76 17:17
43.50 27:45
38.
36
62.94 2:0.0
67.29 2:17%
62 02.08
23 7M
GraphENS
20.45
$0.04
52.20 #2.7
1:3.28
72.06 21.33
5.3 MAIN RESULTS
Neighbor sampling mitigates neighbor memorization We investigate neighbor memorization over conventional algorithms in Section We validate ours with respect to overfitting to minor classes, node memorization, and neighbor memorization. Although minor class similar to re-weighting and oversampling, the test accuracy of our method is much higher than baselines, which indicates that our approach mitigates overfitting minor classes in Figure (a) and (b). Our method significantly decreases the performance degradation when a seen neighbor set is replaced by unseen neighbor set, implying that our approach can generalize well for unseen neighbor views compared to baselines (Figure I (d)). Neighbor sampling thus effectively alleviates the neighbor memorization by exposing minor nodes diverse circumstances.
training accuracy of the
Supervised Learning We evaluate GraphENS on highly class-imbalanced situations as most real- world graphs. First, we test our method on three long-tailed citation networks: Cora-LT, CiteSeer- LT, and PubMed-LT. In Table 1, our method brings better imbalance handling performance in most cases compared to other baselines. To verify the effectiveness of our method on real-world imbal- anced graphs, we also test GNNs trained with GraphENS naturally dass-imballnced benchmark datasets without any modifications graphs. Our method outperforms other contenders by signif- icant margins in AmazonComputer (Table 2). Note that method consistently exhibits higher accuracy and Fl score in other architectures (Table in Appendix B.1).
Semi-supervised learning To validate approaches when labeled nodes are extremely stricted, we conduct experiments a semi-supervised setting on citation networks (Table 4). Our approach significantly outperforms baselines for all datasets. Ours also exhibits consistent supe- rior performances in other GNN architectures (Table 7). Note that since GraphENS exploits entire classes synthesize minor nodes, method avoid the generation of redundant nodes when the number of minor nodes is extremely low. Hence, our method significantly improves the perfor- approaches- GraphSMOTE, Oversampling. Ours brings further performance gain by utilizing unlabeled nodes to generate ego networks (Appendix B.2).
mance against existing oversampling-base
5.4 ABLATION STUDY
We verify two key components of our method: 'prediction similarity' on neighbor sampling and 'saliency masking' on node mixing. To this end, we introduce baselines: 1) 'GraphENS w/o PS* de- termines prediction similarity uniformly random, 2) 'w/o SM' mixes nodes without saliency mask- ing (Mx = 1), and 3) "w/o SM,NS' generates mixed minor nodes without masking and connecting to neighbors of the target. We find that removing each module drops accuracy (Table 3). Thus, we believe each module effectively contributes to restraining the generation of harmful ego networks.
6 CONCLUSION
We investigated that existing imbalance handling algorithms suffer from neighbor memorization problem in class-imbalanced node classification. Thus, we proposed novel augmentation method, GraphENS, to synthesize an ego network for minor classes with neighbor sampling and saliency- based node mixing. We verified that our method effectively mitigates neighbor memorization by synthesizing diverse but probable minor ego networks. GraphENS demonstrated its effectiveness in that it outperforms baselines over multiple benchmark datasets with various GNN architectures.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENT
This work was supported by Institute of Information & Communications Technology Planning & Evaluation (ITP)) grant (No.2019-0-00075, Artificial Intelligence Graduate School Program (KAIST), No.2001-0-01371, Development of brain- inspired Al with human-like intelligence, No.2021-0-02068. Artificial Intelligence Innovation Hub) and the National Research Foundation of Korea (NRF) grants (No.20180) ASAA059921)) funded by the Korea govermment (MSIT). This
work was also supported by Samsung Electronics Co., Ltd NN..12201214-08133-0011
REFERENCES
Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Aréchiga, and Tengyu Ma. Learning imbalanced datasets with label-distrbuttion-awee margin loss. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019,
December 8-14, 2019, Vancouver, BC, Canada, pp. 1565-1576, 2019.
Nitesh V. Chawla, Kevin W. Bowyer, Lawrence O. Hall, and W. Philip Kegelmeyer. SMOTE: synthetic minority over-sampling technique. Artif. Intell. Res., 16:321-357, 2002.
Peng Chu, Xiao Bian, Shaopeng Liu, and Haibin Ling. Feature space augmentation for long-tailed data. In Computer Vision ECCV 2020 - 16th European Conference, Glasgow, UK, August 23- 28, 2020, Proceedings, Part XXIX, volume 12374 of Lecture Notes in Computer Science, pp. 694-710. Springer, 2020.
Arné Clevert, Thomas Unterthiner, and Sepp Hochreiter. Fast and accurate deep network learning by exponential linear units (elus). In 4th International Conference on Learning Repre- sentations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016.
Yin Cui, Menglin Jia, Tsung- Yi Lin, Yang Song, and Serge J. Belongie. Class-balanced loss based on effective number of samples. In IEEE Conference on Computer Vision and Pattern Recog- nition, CVPR 2019, Long Beach, CA, USA, June 16-20, 2019, pp. 9268-9277 9277. Computer Vision Foundation IEEE, 2019.
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 1024 1034, 2017.
Youngkyu Hong. Seungju Han, Kwanghee Choi, Seokjun Seo, Beomsu Kim, and Buru Chang, Dis- entangling label distribution for long-tailed visual recognition. In IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2021, virtual, June 19-25, 2021, pp. 6626 6636. Computer Vision Foundation / IEEE, 2021.
Ahmet Iscen, Giorgos Tolias, Yannis Avrithis, and Ondrej Chum. Label propagation for deep semi- supervised learning. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 5070-5079 2019.
Nathalie Japkowicz and Shaju Stephen. The class imbalance problem: A systematic study. Intell. Data Anal., 6(5):429-449, 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 8th Interna- tional Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
Jachyung Kim, Jongheon Jeong, and Jinwoo Shin. M2m: Imbalanced classification via major-to- minor translation. In 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2020, Seattle, WA, USA, June 13-19, 2020, pp. 13893-13902. IEEE, 2020a.
Jachyung Kim, Jongheon Jeong, and Jinwoo Shin. M2m: Imbalanced classification via major-to- minor translation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 13896-13880 13905, 2020b.
10

---

Published as a conference paper at ICLR 2022
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In 3rd Interna- tional Conference on Learning Representations, ICLR 2015, 2015.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. 5th International Conference on Leurning Representations, ICLR 2017, Toulon, Frunce, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
Zhining Liu, Pengfei Wei, Jing Jiang, Wei Cao, Jiang Bian, and Yi Chang. MESA: boost ensemble imbalanced learning with meta-sampler. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, Decem- ber 6-12, 2020, virtual, 2020.
Aditya Krishna Menon, Sadeep Jayasumana, Ankit Singh Rawat, Himanshu Jain, Andreas Veit, and Sanjiv Kumar. Long-tail learning via logit adjustment. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
Mohammadreza Mohammadrezaei, Mohammad Ebrahim Shiri, and Amir Masoud Rahmani. Iden- tifying fake accounts on social networks based on graph analysis and classification algorithms. Secur: Commun. Networks, 1111::992315:11592333
2018.
Bryan Perozzi, Michael Schueppert, Jack Saalweachter, and Mayur Thakur. When recommendation goes wrong: Anomalous link discovery in recommendation networks. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, August 17, 2016, pp. 569-578. ACM, 2016.
Liang Qu, Huaisheng Zhu, Ruiqi Zheng. Yuhui Shi, and Hongzhi Yin. Imgagn: Imbalanced network embedding via generative adversarial graph networks. KDD '21: The 27th ACM SIGKDD Conference Knowledge Discovery and Data Mining, Virtual Event, Singapore, August 14-18, 2021, pp. 1390-1398. ACM, 2021.
Jiawei Ren, Cunjun Yu, Shunan Sheng, Xiao Ma, Haiyu Zhao, Shuai Yi, and Hongsheng Li. Balanced meta-softmax for long-tailed visual recognition. Advances Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Gallagher, and Tina Cliassi-Rad. Collective classification network data. AI Mag., 29(3):93-106, 2008
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski. and Stephan Günneemann. Pitfalls of graph neural network evaluation. CoRR, abs/181 1.1..1111000 1.05868, 2018. URL http://arxiv. org/ /bs//bb//// / 1811. 05868.
abs/
Min Shi, Yufei Tang, Xingquan Zhu, David Wilson, and Jianxun Liu. Multi-class imbalanced graph convolutional network learning. In Proceedings of the Twenty-Ninth International Joint Confer- ence on Artificial Intelligence (IJCAI-20), 2020.
Avanti Shrikumar, Peyton Greenside, and Anshul Kundaje. Learning important features through propagating activation differences. In International Conference on Machine Learning, pp. 3145- 3153. PMLR, 2017.
Karen Simonyan, Andrea Vedaldi, and Andrew Zisserman. Deep inside convolutional networks: Vi- sualising image classification models and saliency maps. arXiv preprint arXiv:1312.6034 2013.
Nitish Srivastava, Geoffrey E. Hinton, Alex Krizhevsky. Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. J. Mach. Learn. Res., 15(1): 1929-1958. 2014.
Jingru Tan, Changbao Wang. Buyu Li, Quanquan Li, Wanli Ouyang, Changqing Yin, and Junjie Yan. Equalization loss for long-tailed object recognition. In 2020 IEEE/CVF Conference Computer Vision and Pattern Recognition, CVPR 2020, Seattle, WA, USA, June 13-19, 2020, pp- 11659-11668 11668. IEFF, 2020.
11

---

Published as a conference paper at ICLR 2022
Junjiao Tian, Yen-Cheng Liu, Nathaniel Glaser, Yen- Yen-Chang Hsu, and Zsolt Kira. Posterior calibration for imbalanced datasets. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan- -ienn Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
Jesper Van Engelen and Holger H Hoos. A survey on semi-supervised learning. Machine Learn- ing. 109(():373-444 4400, 2020.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings.
Vikas Verma, Alex Lamb, Christopher Beckham, Amir Najafi, Ioannis Mitliagkas, David Lopez- Paz, and Yoshua Bengio. Manifold mixup: Better representations by interpolating hidden states. In International Conference on Machine Learning, pp. 6438-6447, PMLR, 2019.
Jianfeng Wang, Thomas Lukasiewicz, Xiaolin Hu, Jianfei Cai, and Zhenghua Xu. RSG: A simple but effective module for learning imbalanced datasets. In IEEE Conference on Computer Vi- sion and Puttern Recognition, CVPR 2021, virtual, June 19-25, 2021, pp. 3784-3793. Computer Vision Foundation / IEEE, 2021.
Zheng Wang, Qiao Wang, Tanjie Zhu, and Xiaojun Ye. Extending LINE for network embedding with completely imbalanced labels. Int. Data Warehous. Min., 16(3):00-36, 2020a.
Zheng Wang, Xiaojun Ye, Chaokun Wang, Jian Cui, and Philip Yu. Network embedding with completely-imbalaneee labels. IEEE Transactions on Knowledge and Data Engineering, 2020b.
Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. In Proceedings of the 33nd International Conference on Machine Learn- ing. ICML 2016, New York City, NY, USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pp. 40-48. JMLR.org. 2016.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William I.. Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Pro- ceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2018, London, UK, August 19-23, 2018, pp. 974-983, ACM, 2018.
Yongshun Zhang, Xiu-Shen Wei, Boyan Zhou, and Jianxin Wu. Bag of tricks for long-tailed visual recognition with deep convolutional neural networks. Proceedings of the AAAI Conference on Artificial Intelligence, 35(4):3447-3455 May 2021.
Tianxiang Zhao, Xiang Zhang. and Suhang Wang. Graphsmote: Imbalanced node classification on graphs with graph neural networks. In WSDM 21, The Fourteenth ACM International Conference Web Search and Data Mining, Virtual Event, Israel, March 8-12, 2021, pp. 333-841. ACM, 2021.
Boyan Zhou, Quan Cui, Xiu-Shen Wei, and Zhao-Min Chen. BBN: caaterallbranch network with cumulative learning for long-tailed visual recognition. In 2020 IEEE/CVF Conference on Com- puter Vision and Pattern Recognition, CVPR 2020, Seattle, WA, USA, June 13-19, 2020, pp- 9725-9725. Computer Vision Foundation IEEE, 2020.
Dawei Zhou, Jingrui He, Hongxia Yang, and Wei Fan. SPARC: self-paced network representation for sho- rare category characterization. In Proceedings of the 24th ACM SIGKDD Interna- tional Conference on Knowledge Discovery & Data Mining, KDD 2018, London, UK, August 19-23, 2018, pp. 2807-2816. ACM, 2018
12

---

Published as a conference paper at ICLR 2022
A AUXILIARY RESULTS FOR NEIGHBOR MEMORIZATION PROBLEM
In this section, we present experimental results which are not reported in the Section due to the space constraints.
A.1 FURTHER INVESTIGATION FOR NEIGHBOR MEMORIZATION
In Section 3, we verify our hypothesis easy to overfit to neighbor structures on the hasis of the most simple imbalance handling approaches. To further strengthen our claim, we intensively exam- ine the neighbor memorization problem with other recent baselines over five benchmark datasets. As can be seen from Table 5, we observe that baselines consistently suffer from neighbor memorization approach shows significantly superior generalization perfor-
issues in most cases. In addition, mance than baselines on both node and neighbor replacing experiments except for node-replacing experiments PubMed-L.T.
Table 5: The results of node replacing (node memorization) and neighbor replacing (neighbor memorization) experiments on five benchmark datasets. We report the averaged accuracy repetitions.
Methad
Crer
PrnMed-UT
AmszenPPten
Acc.
Auc
(Seen/ Unseen)
Node
Neighbee
Node
Neighbor
Node
Neigher
Node
Neishooe
Node
Neiglber
89.74
1880/900 99.71
Ownramping
86.44/79.58
36.44 1444766.44
89017
54.05
00.77/9077
70.19
06 88-26888-15
96.23 21.28555.000 99
94.19/95.4
94. 79..
96 96.2878594
96 94 73.43
00.60/ 96.64
00.60 86.
66-66-10
96.66 0s
GrsphENN
02.44/9948
97.34 77.34/91.8
91.44781.5
9K.679923 99299
96.477
07 0771779
791.30
01.11/91.38
99.457991D
96-45 98.48
We conducted experiments with 2-layer GCN having 256 hidden dimensions and adopted PC Soft- max and GraphSMOTE as recent algorithms since PC Softmax and GraphSMOTE outperform cRT and DR-GCN in the main experiments, respectively. Note that for these experiments we group classes with less than 100 training nodes as minor classes.
A.2 LEARNING CURVE OF THE TRAINING PHASE
To show the early trend of the training process, only show the learning curve for the first 200 epochs in our main paper. We observe that the gap between training and test accuracy almost maintained entire epochs in Table
1.0
0.8
0.8
Train Acc
Test Acc
0.6
0.6
Re-weighting
0.2
Oversampling
0.2
GraphENS
0.0
0.0
2000
Epoch
Epoch
(a) Train Acc Curve
(b) Test Acc Curve
Figure 4: The learning curves over the training phase.
13

---

Published as a conference paper at ICLR 2022
B ADDITIONAL EXPERIMENTS ON MULTIPLE SETTINGS
B.I RESULTS OF AMAZONPHOTO AND AMAZONCOMPUTERS
Due space constraints, we only present the experiment with GraphSAGE in the main paper, which exhibits the best vanilla performances, AmazonComputers. We also test our method with two different GNN architectures GCN, GAT. As shown in Table GraphENS shows the best performances over baselines in most cases. Detailed experimental settings are described in Section F.
two co-purchase graph datasets AmazonPhoto,
Interestingly. we observe that cRT and PC Softmax show inferior performance than other algorithms on AmazonComputers (Table 6). We conjecture that these approaches fail to learn discriminative representations of minor classes due message-passian methods such as cRT and PC Softmax are proposed based on the observation that retraining the classifier with class-balanced sampling after training on imbalanced datasets show comparable per- formance with baselines (Kang et al., 2020). In other words, learning distinctive representation is not significantly affected by class imbalance. However, oversmoothing caused by message passing impedes learning distinctive representation of minor classes in highly imbalanced datasets. It is con- sistent with the observation that decoupling methods fail at the extremely high imbalance ratio (Ren et al., 2020).
in a highly imbalanced graph. Decoupling
Table 6: Accuracy/F1-see -score on AmazonPhoto and Amazon benchmark datascts in comparison to other baselines. The experiment was performed five times and the averaged accuracy and Fl-score with standard error are reported. Note that the accuracy equal to balance accuracy since the test are balanced.
AmazonPhoto
AmazonComputcrs
Method
(ldholnny rain: 82)
(Imbolooce vate: 244)
(bc.c)Acc.)
F1
Acc.
F1
Vanilla
81,91 20.25
77.50
=9.28
58.42
10.29
51.21
=0.39
Re- Re-Weight
92.73 #0.12
92.72
#0.13
90.65
#0.26
90.70
=0.23
Oversampling
92.62 +0.2a
92.61 +0.25
90.60
+0.26
90.67
+0.26
cRT
10:16
90.20 29.21
78.06
30
77.60
=1.35
PC Softmax
91.05
91.09 #0.18
75.89
74.87
GraphSMOTE
92.58
92.58 +0.11
91,00 +0.21
91.05 +0.21
GraphENS
93.67
93.67 #0.17
91,28 +0.18
91.28
#0.17
Vanilla
81.41 #0.40
76.76
+0.48
60.19 +4.26
54.60
=53.15
"Re-Weight
92.80 10.07
92.80
20.07
90.80
1::18
90.85
20.00
Oversampling
92.69
92.68
90.54
90.56
GAT
cRT
89,92 10.21
89.69 20.25
81,56 42.77
81.57 22206
PC Softmax
90.48 #0.11
90.49 #0.12
79.41 +:3.1
78.
#:4.28
GraphSMOTE
92.63 +0.11
92.63 #0.11
90.77 +0.17
90.80 #0.19
GraphENS
93.10 10.10
93.10
2:020
91.11
10.28
91.07
20.25
B.2 RESULTS OF SEMI-SUPERVISED LEARNING
In Section 5.3, we report the results of GCN on three citation networks Cora, CiteSeer, PubMed. We here additionally offer the result table of two different GNN architectures GAT, GraphSAGE. GraphENS outperforms baselines in most cases (Table 7).
To ensure that method brings improvement for any data split (other than public split), we GraphENS on randomly selected train nodes while keeping the public split of validation/test nodes unmodified (Table 8). We confirm that the improvements of our method is not depending on particular data split. We also attempt to extend GraphENS to utilize unlabeled nodes and validate this extended method. First, we regard unlabeled data as the (C + 1)-th class (C' is the number of classes) and this class could be sampled when selecting target node. Since the number of unlabeled data is large, the labeled class could be sampled less frequently we utilize the number of unlabeled data in the multinomial distribution in Section 5.2. Thus, treat the unlabeled class as the class having the same number data with the least frequent class and sample a target class from the distribution with (LogNN1, log.N...... .o..,.oo.N Nc. logNo+1) where N, is the number of the i-th class data. Note that we utilize model prediction on unlabeled nodes for neighbor sampling and saliency maps of source nodes for saliency masking. To keep class-specific information of source nodes,
14

---

Published as a conference paper at ICLR 2022
Table 7: Comparison of our method GraphENS with other baselines in semi-supervised learning settings (public splif). We report the averaged accuracy, halanced accuracy, and F1-score with the standard errors for repetitions on three benchmark datascts for node classification tasks.
Method
Cara-Sroul
ChteSoer-Sowi
PubMed-SSemi
Acc.
bAcc.
Asc.
bAcc.
Vanilla
69.56
63.57 $1:77
63.27
42.86
43.28
g1:13
39.30
66.78
70.80
66.46
Re-Weight
73.24 27:67
67.68 49
67.36 21:75
52.58 g::10
51.92
20:09
50.22 10:15
67.28 2::71
70.63 11.01
67.07 11
Oversaplling
65.92 g:
59.33 29:5
58.44 12.11
43.48
22.03
42,39
1::09
38.12 29.05
64,22 33.00
66.50 13:30
63.24 2400
GNT
cRT
69.68
63.44
62.96
46.40
45.87
43.71
65.72
69.82
65.26
PC Softmax
71.06 a1
65.89 11
65.35 11:91
g1:81
52.66 11:10
41:45
68.88 19:18
71:65 11:40
68.7 2200
DR-GCN
68.84 g0.71
62.87 10.36
62.20 11:35
46.06
53.00
46.26 13:07
42,05
19.05
65.48 10.76
09:31 10.10
65.03 gA:
Srap&SMOTE
70.20
64.99
64.39
46.42
46.63
41,92
66.42
68 86 $2:00
65
GraphKNS
74.38 go.e>
69.64 g0.36
30.75
56,60
go.00
55.07
20.07
$4.80
30.45
70.48 g1:70
72.08 g::00
70.32 g1
Vanilla
61.68 20.03
$7.62 20.44
56.35 #1.22
40.56
e2.51
41.42
21.00
35.17
22.15
61.30
22.50
65.37
sq.ur
60 60,99
Reight
66.00
60.70
60.18
46
46.000
21.60
66.40
00 16
63385
GropSAAGE
Ovensampling
62.04 53.15
53.66 $1.43
50.55 +:3.3
38.14 #1.51
38.00
=0.75
31.57 #1.04
64.74 +3.35
67.71 #2:45
61.72 =5.02
cRT
65.28 20:87
58.33 :1:24
56,71 11.00
42.90 51.26
43.41
=0.00
38.17
$3.40
60.98
#1.08
65.36 #1.64
59.95 =2.3
PC Softmax
66.84
60.76
60.05
46.76
46.69
41,31
63.84
67.36
63,57
GCN
65.74 20:95
58.96 11.30
=2:30
46.75 =1:77
#5.42
#2.04
66.91 +:228
=3:2:
GrRpSMOTE
62.34 23.34
55.07 $1:08
$2,80 3:3.3M
36.76 21.07
37:21 $1.04
26.33 12.04
63.46 #2.53
67.47 $3.40
62.78 =2:05
GraphENS
71.18
66.50
66.56
53.48
52.57
50.56
69.44
70.67
69.59
exploitation of saliency maps of source nodes is required. In Table 8, the adoption of unlabeled data in GraphENS improves the performance significantly in most cases. We believe that our approach could exploit rich information even in unlabeled nodes to produce safe and diverse ego networks.
Table 8: Evaluation of GraphENS with other baselines in supe-supe learning settings (random split). We report the averaged accuracy. balanced accuracy, and Fl-score with the standard errors for 5 repetitions on three benchmark datasets for node classification tasks. f denotes the results when utilizing unlabeled nodes.
Method
Cora-Semi
ChicSer-
Pub Semi
Acc.
bAcc.
F1
Acc:
hAce.
F1
Asc.
hAcc:
P1
Vanilla
63.98
58 28
55.97
40 76
40 54
35,11
57.48
62. 35
Re "eeWeiighi
87.56 21:32
6330
61.43
42.00
23.07
41122
23.06
33.35
14.15
66.98
10.36
66.34
66:35
23:00
Ovensompling
61,86 21.04
56.52 20:05
53.41 11:21
36.34
2:100
35.93 11:07
27.75 15.10
63.76 21:00
68-45 21.00
62.37 23:35
cRT
63.94
57.16
54.45
41.16 22.93
41.78 23:36
36,088 19.34
57.34 29.98
62:21 12.10
55,39
23.0
GCN
PC Softmax
69.20
64.68
63.80
45.24
44.34
40.38
64.78
66.89
64.82
CPGNN
65.30 24
58. 20
$4.79 10.80
41.38 22:30
21.73
34,85 19.45
62.18 21.40
68:41 1::00
60.56 13:10
DR-GCN
64.22 a1
58.28 21 a0
$5.93 17:6
35,80 51:0
36.51 29:00
27.62 29.16
61.78 2a
66.13 22:40
59.67 21
GrIpSMMTE
64.70
58.71
56.31
39.74
38.27
31,45
64.00
67.90
63,44 s3.8)
GraphiNN
69.78 m
65.01 17
64.09 11:40
52.42 10:00
49.55 21:18
$4:54 46.27
68.54 11:18
70.68 19:90
69.9 g00
GraphENS'
70.76
66.78
66,20
53.58
51.69
49,42 33.73
69,54
70.38
69.00
Vanilla
21.99
64.08
43,42
42.3
#2.02
66, #1.78
70.37 $1.36
65
Re- Weight
69.40 #1.42
65.14 1144
63,90 12.45
50.56 61.72
47.83
#1107
45,28 #2.45
68.94 +2.04
71.57 +1.33
68. 68.78 =1.84
Ovensumpling
65.36
59,72
57,51
10.58
38.23
=3:25
31.47
61,.22
67.
63.18
GAT
cRT
67.56 61:63
62.10 22.27
12.61
$3.60
43.45
02:05
12.30
19.54
13.17
65 23002
PC Softmax
69.30 51.17
66.05 11.47
65.06 11:51
50.08 02.13
48.61
#2.15
47.19 $2.00
68.42 #1.36
71.83 00.66
68 68.28 =1.00
DR- GCN
66.76 21.77
61.47 22:45
59.95 15..07
11.28
23:14
10.71
=2.97
33.96
66.96 #1.50
69:02 #1.82
66.11 =2
GraphSMOTE
68.23
63.67
62.50
45.26
43.42
39,46
65.16
69.32
64.39
GraphENS
69.62 20.91
65.27 $1.35
61.16 11.57
$3.90 53.25
51.74 s0.81
19.17 #1.57
70.24 $1.40
71.00 $1.15
69.93 =1.2:
GraphENS'
69.02
64.66
63.74
$6.32
$3.69
$1,76
70.18
70.52
69.42
Vanilla
62.50 80.99
56.24 11.05
13.47 "AAK
40.16
20.00
62.30 pa.sa
66.57 83.15
"KeWeiigh
6252 g0:05
10.46
41.10
50..6
68.50
69.29
13:40
68:30
GippSAGEE
Oversampling
61.40
$2.99
39.04
38.
52,17
59,26
63.59
58.05
cRT
63.20 21:17
57.21 11 d9
54.71 19.59
40.34 20:00
40.59 20:44
36.18 20
62.90 29:36
67.13 1:
PC Softmax
65.32 1:
60.52 11:59
58.91 1.1.0c
44.02 23:40
44.34 11:05
38.99 39.35
63.18 3a:c
66.94 13.51
61 61.19 24:41
DR-GCN
61,82
55,
51,93
42,86
41.72
37.49
62.50
65.65 1::20
61.73
GrIASMOTE
60.84
28 52.00
39.27
1::14
6607
GraphENSS
65.84 20.74
62.29 $1:09
61.52 21.79
51.12 53.M
48.91 2::94
46.78 3:2022
67.62 $1.77
68.27 23.20
67.37 21.00
GraphKNN'
67.72
64.18 21:31
11.47
17.13
.9.94
68.04 10.10
20000
15

---

Published as a conference paper at ICLR 2022
C IN-DEPTH ANALYSIS
C.I CLASS-WISE PERFORMANCE ANALYSIS
To clearly present alleviation of overfitting to minor classes, we provide the test accuracy curves for each class. Note that PubMed-LT has three classes and the number of nodes for each class as follows: Minor 11: 72, Minor_2 2: 726, Major: 7260). ). The experiment settings are identical to Section 3.
In Figure 5 (a), while the training accuracies for minor classes (Minor_1, Minor_2) highly similar over entire methods, GraphENS exhibits significantly superior test accuracies for minor classes (Fig- 5 (b.c)). Albeit our method slightly sacrifices the test accuracy of the major class, we confirmed that our approach substantially mitigates overfitting to the minor classes.
10
1.0
08
0.3
Test Acc.
206
0.60
Test
F04
Re-weighting
Oversampling
ENS
Epoch
Epach
Epoch
Epoch
(a) Train Acc. Curve
(b) Test Acc. of Minor 1 class
(c) Test Acc. of Minor 2 class
(d) Test Acc. of Major class
Figure 5: The train accuracy curves for all methods and test accuracy curves for each class on PubMed-LT dataset. Solid lines represents Minor_ class, dashed lines are Minor 2, and finely-dotted lines are Major class, respectively.
C.2 VISUALIZATION OF THE HIDDEN REPRESENTATIONS
In this subsection, shed light on why algorithm works. Our method aims to enlarge and smooth the decision boundary of the minor class. First, to extend the boundary of the minor class, GraphENS utilizes the manifold assumption that "similar predictions of neural networks indicate the close proximity the manifold" (Van Engelen & Hoos, 2020; Iscen et al., 2019) as a key inductive bias. By synthesizing the minor ego network using the target node of the entire class, our method widens the decision boundary effectively in that we interpolate the ego networks based on prediction similarity. In the vision domain, M2m (Kim et al., 2020b), one the imbalance-hande handdinnnn methods, also translates major class data into minor class to prevent overfitting on minor classes exploiting our assumption implicitly. This extrapolation scheme for the minor class becomes more significant when the number of data is highly scarce.
[most trequent class)
L2
***
class)
(a) Re-weighting
(b) GraphENS
Figure 6: The decision boundaries of Re-weighting and our method are visualized by using 2D hidden repre- sentations of GNN.
16

---

Published as a conference paper at ICLR 2022
Another advantage of our method for node classification is that the generalization performance of GNNs can be improved by smoothing the decision boundary. As investigated in Verma et al. (2019), convex combinations of node features encourage the smoothness of the boundary. To verify the smoothness and enlargement of minor classes, we visualize the decision boundaries of Re-weighting and our method by using 2D bottleneck hidden representations of GNN in Figure 6. Note that conduct experiments on Cora-LT with 2 layers of GraphSAGE. Compared to Re-weighting, we ob- serve that our boundaries are smoother and the fewest class occupies more region with significantly large margin. Therefore, along with the main results, this result implies that our method could improve generalization performance by enlarging the decision boundary minor classes smoothly.
C.3 OVERSAMPLING RATIO
We investigate the performance tendency according oversampling scale, which determines the number of generated minor nodes. Specifically, the number of oversampled nodes is computed as oversampling ratio (the number of nodes in the largest class the number of nodes in the minor class)). In Figure 7, we observe that the performance decreases as the scale is (1) under 0.6 or (2) 1.0. We conjecture that the induced bias of major classes is not sufficiently corrected low oversampling scales (1). In the regime of (2), high oversampling scale impedes the learning of major class representations, resulting in performance degradation. Thus, the oversampling scale between 0.8 and 1.0 is preferable option and we adopted 1.0 as the scale in our main experiments, following conventional oversampling methods.
94.0
93.5
F1-score (%)
92.5
92.0
91.5
GraphENS
91.0
GraphSMOTE Oversampling
90.0
0.2
0.4
0.6
0.8
1.0
1.2
Oversampling ratio
Figure 7: Performance analysis according the oversampling ratio with AmazonPhoto dataset with Graph- SAGE.
17

---

Published as a conference paper at ICLR 2022
D ILLUSTRATIONS OF REPLACING EXPERIMENTS
To facilitate understanding of node/neighbor replacing experiments, we describe the experiments with illustrations. In Figure observe node memorization, replace the node feature Vanchor with Useen in (a) and Vanchor with Uunseen in (b). The performance gap between Vanchor in (a) and (b) is computed. Similar node-replacing experiments. the node feature of Useen with fanchor in (c) and Useen with Vanseen in (d). The accuracy difference between Useen in (c) and Vanseon (d) calculated. The results of replacing experiments are in Figure 1.
see neighbor memorization, we replace
Veee
anchor
D amnhbar
V Vanchor
Node-Replacing: Seen Nodes with Seen Neighbors
(B) Node Replacing: Unseen Nodes Seen Neighbors
1
2 Vanchor
I uuseen
Vmnseen
Useen
U seen
Neighbon-Rappe Ruplacing:
Sean Naighbars
Neighhar-RRplacinng
Neighbors
Figure 8: Overall pipeline of node-replacing and neighbor-replacing experiments.
18

---

Published as a conference paper at ICLR 2022
E MAIN ALGORITHM
Algorithm GraphENS
1: Input: Dataset (G(V, E), model fo. class distribution PClase(C), class-conditional node distribution
Prode (u)c), degree distribution Pdegree number classes C, number samples to oversampled No feature masking hyperparameter k, learning rate temperature T
2: Initialize: Model fe.
3: for t= 1, . do Vnew. Enew for c 1, ... do 6: for i = 1, 1,2,... N do
7:
Ctarget Pelass (C)
Sampling target class
8:
Vtarget Prode Prode(ul Ctarget) Uminor ~ Prodd (ule
10:
~ Beta(2,2)
11:
ift < 10 then Emized (1 A) Ammmno + Attarget
D Warmup
12:
13:
Unj Ung:" (V
Neighbors of Uninor
14:
Bnew - {f Umixed h {Unzr Umixed), .** ; Wimmorl)) Umized]
15:
else
16:
Φ t KL ((oorrgge))
17:
1+c-#
18:
19:
Saliency-based node mixing
20:
21:
Compute Mr from multinomial distribut in using S St-1 K AK X MR
22:
23:
Umized (1 Ax) Uninoo Ag Utarget
24:
25:
D. Neighbor sampling p(u (miszed) x- óp(ulemminon (1 d)p(u (b)p(u/Vaagget)
26:
27:
r ~ Pdegree (D)
28:
Uniy Unz1" Unr (luuzed))de)
29:
Enew t ({Un) Umisaed; ) { (Ung. Umisedd::.. :.. {Uar, Umizedt)
30:
end if
31:
Vnew f- Vnew U (Umized)
32:
Enew t- Enew U Enew
33:
end for end for
34:
35:
fo(Vnem Fnew)
36:
Enew &- CrossEntropyyo.r)
37:
O x- 0 (VaCne))
38:
for do
39:
No) EnE(N(OUO)) Softmar(o./T)
Confidence aggregation
40:
end for
41: St --ooputting feature saliency with the gradient of Lnew (Equation. (2))
42: end for
43: Output: fo
19

---

Published as a conference paper at ICLR 2022
F DETAILED EXPERIMENT SETTINGS
this section, we address all the details of experiments we conducted.
F.1 DATA STATISTICS
Table 9: Data summary Label distribution of training datasets [%)
Dataset
Domain
Lo
L
L2
Lg
L4
L
Lg
L7
Ls
Lg
Cora-Semi
23.26
23.26
23.26
23.26
2.33
2.33
2.33
Citation Network
Cora-LT
54.04
25.04
11.57
5.39
2.38
1.11
0.48
CiteSeer-Sene
30.30
30.30
30.30
3.03
3.03
3.03
Citation Network
CiteSeer-Le LT
60.72
24.06
9.49
3.76
1.47
0.49
PubMed-
83.33 8.33
8.33
Citation Network
PubMed- LT
90.10 9.01
0.89
AmazonPhoto
Co- Co-Purchase Graph
31.58
26.64
11.70
11.06
9.92
7.59
1.12
0.39
AmazonComputers
Co-Purchasc Graph
44.26
17.07
16.94
10.35
4.95
2.45
1.96 1.49 0.34 0.18
F.2 ARCHITECTURE
We evaluate our method with three representative GNN architectures GCN (Kipf & Welling, 2017), GAT (Velickovic et al.), and GraphSAGE (Hamilton et al., 2017). In this section, describe the detailed architecture of each GNN. For GCN, our model consists of GCN layers with ReLU activation, followed by dropout Srivastava al. (2014) with 0.5 dropping rate and linear classifier. For GAT, our model comprises I GAT layers, which involves an ELU activation Clevert et al. (2016), followed by dropout with 0.5 dropping rate and linear classifier. We also adopt multi-head attention with 8 heads and apply dropout with 0.6 dropping rate to its attention. GraphS AGE is composed of SAGE layers with ReLU activation, followed by dropout with 0.5 dropping rate and linear classifier. We search the architecture to maximize the validation accuracy for all algorithms. The search spaces of reported results are the number of layers 7 (1,2,3) and hidden dimension d (64, 128, 256].
F.3 EVALUATIONN PROTOCOT.
We adopt Adam (Kingma & Ba, 2015) optimizer with the initial learning rate as 0.01 and train GNNs for 2000 epochs. The best models are selected with validation accuracy. We design scheduler as a learning rate is halved if there is no improvement on validation loss for 100 iterations. We choose weight decay all convolutional layers except for linear classifier with 0.0005. We select the best model using validation accuracy over the training phase.
F.4 IMPLEMENTATION DETAILS
In this subsection, we explain the hyperparameters our experiments. For all datasets, we use Beta(2, 2) distribution to sample X. Feature masking hyperparameter & and temperature are tuned among {1, 5, 10} and {1, 2}, respectively. We employ warmup since our approach utilizes model confidence, models need to be trained to some extent. The number of epochs for warmup is tuned among 51.
F.5 THE DETAILED SETUP FOR SEMI-SUPERVISED LEARNING
We validate imbalance handling approaches on the citation networks such as Cora, CiteSeer, and PubMed. We follow the split in Yang et al. (2016) and set the imbalance ratio as 10. Specifically, for Cora and CiteSeer, three classes have only two labeled nodes while other classes have 20 labeled nodes since the number of labeled nodes in each class is 20 in Yang et al. (2016). For PubMed, only two classes have two labeled nodes as PubMed consists of three classes.
20


Reviews:
[{"review_id": "qgNhf_f9s5F", "reviewer": "Reviewer_ACEE", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "Strong points:\n\n1. The proposed model is intuitive and technically sound. Neighbour sampling is important in graphs given the neighborhood memorization problem.\n\n2. I like the preliminary analysis on the importance of neighbour sampling, putting the neighbor memorization problem in a quantitative manner (i.e. section 3)\n\n3. Experiments are extensive with strong empirical results.\n\nI only have one main concern:\n\nThe target node is picked from a distribution based on the log of the number of nodes in the class, but not much rationale is offered on why this particular distribution is chosen. Is there any guiding principle? Would the model benefit from more elaborately designed distributions?\n\n", "summary_of_the_paper": "The paper proposes an imbalanced classification strategy for GNNs. Unlike traditional imbalanced classification, nodes on a graph are dependent on its neighbors, and simply over-sampling/re-weighting the minor class instances would not work. In particular, the authors recognize and analyze the severity of the \"neighbor memorization\" problem, which is identified as the key cause of overfitting in GNNs.\nThe proposed method alleviates the neighbor memorization problem by synthesizing ego networks. Extensive experiments are conducted to evaluate the proposed method.", "summary_of_the_review": "The paper is well written and technical sound, with strong results. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made 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": {}}, {"review_id": "nWV0scUHPpK", "reviewer": "Reviewer_KQwg", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Representation learning for node classification usually has class-imbalance issue. Some labels might cover a few number nodes. This work empirically indicates out that the learned node representations will be influenced by the neighbor label distribution. In particular, those nodes with minor class can have the neighbor memorization problem, that is, the target node's embedding might mainly represent the neighbor nodes but not itself. Empirical analysis in this work supports this claim clearly. Then a data augmentation method based on this observation is proposed. Experiments with class-imbalance setting are conducted to demonstrate the superiority of the proposed augmentation method.\n\nConcerns:\n 1. The notations in this work are not easy to follow. Authors use many kinds of symbols like minor, target, seen, or unseen to represent the types of nodes. However, it's very difficult to tell their difference in the manuscript. Could you please explain what's the target node and its difference to the nodes with class? Should the minor nodes be the target nodes? Please check the manuscript again and consider to present the types of nodes in alternative way.\n\n2. It's difficult to draw connection between the proposed method and the solution to address the neighbor memorization problem. We can only see an augmented data by mixing up the node feature and neighbor nodes. Could please explain how to created virtual label for the synthesized node, and why the augmentation method can solve the neighbor memorization problem?\n\n3. Could you please consider baselines which can deal with heterophily network [1]? The neighbor memorization seems to be similar with the definition of heterophily, where the target usually has different labels from the neighbors.\n\nReferences:\n[1] Jiong Zhu et al., Graph neural networks with heterophily, AAAI 2021.\n \n\n", "summary_of_the_paper": "This paper exploring neighborhood memorization problem and proposes a neighbor-aware data augmentation method for node classification task.", "summary_of_the_review": "This work studies an interesting problem, but the presentation is not clear expressing the motivation.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "QOvrQElej-L", "reviewer": "Reviewer_DE1Z", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "However, there are several major concerns in the paper.\n\n1. A case study is conducted to prove the hypothesis that \"we hypothesize that it is in fact more serious to overfitting to neighbors of minor nodes than to overfitting to the node feature itself\". And this study fundamentally lays the foundation for the following part of this paper. However, there are several issues in this case study.\n\n- (1.1) A benchmark dataset Pubmed is employed to conduct the case study. However, on different datasets, node representations calculated by GNNs may be influenced differently by the node-self features and the neighboring information, due to the distinct characteristics of datasets. Therefore, only employing one dataset here cannot demonstrate the existence of this phenomenon on different datasets with different distributions.\n\n- (1.2) Two traditional baselines are utilized, namely re-weighting and oversampling approaches. However, many advanced approaches are proposed recently to deal with this problem. Only comparing with the most conventional approaches is less convincing to prove this hypothesis. \n\n- (1.3) In the section of \"Overfitting to minor classes\", based on Figure 1, a claim is provided that \"This result implies that the existing approaches are prone to memorize minor class nodes\". However, this conclusion is not quite reasonable. Firstly, the case study only resorts to two conventional approaches, and they cannot represent all the existing approaches (for this problem). Secondly, from Figure 1, we can only observe that \"the existing approaches are prone to overfit on minor classes, and the performance (on test) of them on minor classes is not good compared to the proposed GraphENS\". Thus, the conclusion is over-claimed to some extent.\n\n- (1.4) In summary of the case study, we can achieve a conclusion that: for a minor node, its neighboring information might provide a larger influence on the performance than its own features. However, it is hard to say: the neighboring information is the key factor to impair the performance of minor nodes. \nTherefore, it seems that the case study cannot comprehensively provide the fundamental basis for the proposed model.\n\n\n2. In the Introduction, a claim is presented that \"Nevertheless, GNNs trained with GraphSMOTE still suffer from neighbor memorization when the number of minor nodes is limited\". Why it still suffers from neighbor memorization? More details should be given.\n\n\n3. The proposed model GraphENS contains two key components, namely neighbors sampling and saliency masking on features. From the main contribution of this paper, we can see that \"the neighboring information is the key reason that impairs the performance of minor nodes\". However, from the ablation study (Sect 5.4), we can see that, these two components generally have a comparable influence on the performance. The authors should give more explanations.\n\n\n4. The illustration of Sect 4.1 is a bit confusing, especially the utilized notations. For example, is v_{minor} (or v_{target}) an example node or a group of nodes? \n\n\n5. In the Experiments, in order to generate the imbalanced settings on the citation networks, for the minor classes, only two labeled nodes are available for training. The extreme scarcity of minor classes is not a reasonable setting and might import high bias or uncertainty into the experiments, which may damage the persuasiveness of the experiments accordingly, and even the case study.", "summary_of_the_paper": "This paper investigates the problem of class-imbalanced node classification on graph. To address this, the authors first conduct a case study on a dataset to analyze the underlying reason for inferior performance on minor class nodes. Then a model named GraphENS, which consists of two key components, is proposed to deal with the imbalance issue. Experiments on several datasets show that the proposed model can outperform the baselines.", "summary_of_the_review": "1. The case study is not convincing enough to lay the foundation for the model.\n2. More details should be given for some confusing points.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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": "E7-Ywb_qAKU", "reviewer": "Reviewer_6ykZ", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "The paper has multiple strong points and few weak points.\n\nStrong points:\n\n1. The paper motivates the problem very well. The experiments in Section 3 show the gap that existing / conventional approaches for class imbalance problem fail to address for graphs. Thus, it shows very well why graph-specific solutions for class imbalance problem are needed.\n\n2. The related work and baselines used for experiments are quite exhaustive to the best of my knowledge.\n\n3. Experimental results are quite promising. They clearly show the merit of the algorithm and its components for imbalanced node classification.\n\n4. The source code is attached (I have not run it though).\n\n\nWeak Points / Need Clarifications:\n\n1. Though I appreciated the motivation and problem formulation of the paper, the proposed algorithm GraphENS is very heuristic in nature. Different steps of the algorithm, i.e., Neighbor Smapling and Node Mixing do not have a strong objective. I agree that these steps are simple and also intuitive. But what (and how) advantage it is gaining for node classification objective is not clear. It would have been great if some objective / cost function can be formulated and these steps could have been deduced by solving that. At least, authors should give more justification on their need for node classification.\n\n2. Table 1 shows improvement on the manually imbalanced citation datasets. I am curious to see the performance of GraphENS on the original citation datasets. It would be great if authors can compare the performance using GCN, GAT and GraphSAGE with / without GraphENS.\n\n3. What is the training, validation and test size for supervised and semi-supervised learning setup? I also think that \"Supervised Learning\" task is also a semi-supervised one as it is a GNN based node-level task on a graph. Can authors please clarify that?\n\n4. Figure 1b shows that the gap of performance between all classes and the minor class (around epoch 200) is almost the same for all the algorithms. The training accuracy is also very similar for all classes and the minor class from Figure 1a. Does it mean that overfitting to minor classes is not resolved in graphENS? On a similar note, the gap between blue bar and red bar is almost the same for all the algorithms in Figure 1c. However, GraphENS is doing really well to minimize the gap between blue bar and red bar for the neighbor-replacing experiment in Figure 1d. Can authors comment on this and throw some light on the actual reason for the superior performance of graphENS.", "summary_of_the_paper": "This paper addresses the class imbalance problem for node classification in a graph and points out some issues faced by existing GNNs and  methods to address the same. It nicely depicts the problem of overfitting to minor classes and neighborhood memorization problem for class imbalance through experiments. It proposes n approach GraphENS which can work with any message passing GNN to resolve the problem of class imbalance for node classification. Experimental results show the merit of the proposed algorithm working with multiple GNNs (GCN, GraphSAGE and GAT) on both synthetically imbalanced dataset and real-world imbalanced dataset for node classification.", "summary_of_the_review": "I am still voting for acceptance since the problem motivation and formulation is done very nicely and experimental section is also strong. The proposed algorithm is simple and intuitive, but not that rigorous.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made 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": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Although reviews were initially a little polarized, they trend toward accepting the paper after rebuttal and discussion.

The most negative review raised issues of datasets, baselines, and experiments, and various details that they find confusing. These concerns were not shared by the other reviewers for the most part. Following a detailed rebuttal the most negative reviewer ended up siding with the more positive reviewers.
Decision: Accept (Poster)