GRAPHENS: NEIGHBOR-AWARE EGO NETWORK SYNTHESIS FOR CLASS-IMBALANCED NODE CLASSI-
Year: 2021

Abstract:
In many real-world node classification scenarios, nodes are highly classimbalanced, 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.

heading: 1 INTRODUCTION
text: Node classification for graphs has attracted significant attention as the importance of large-scale graphs analysis increases in various domains such as bioinformatics and commercial graphs to name a 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 is critical for improving the quality of recommendation systems (Perozzi et 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 et al., 2017; Kipf & Welling, 2017; Velickovic et al.). However, the nodes in many real-world graphs are sometimes class-imbalanced (Mohammadrezaei et al., 2018; Wang et al., 2020a), hence GNNs are prone to be biased toward major classes, as in general class-imbalance tasks. This bias forces networks to poorly classify the nodes of minor classes, resulting in destructive impacts and a large cost to their services.
While the peculiar characteristics of imbalanced node classification and specialized solutions suitable for it have hardly been investigated, applying generic imbalance handling methods (Chawla et al., 2002; Cui et al., 2019; Cao et 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 hypothesize that it is in fact more serious to overfitting to neighbors of minor nodes than to overfitting to the node feature itself. This ‘neighbor memorization’ is the critical obstacle to naively adopt the class-imbalance approaches of other domains such as re-weighting and re-sampling used in image classification. Specifically, 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 to minor nodes, hence there is no change in neighbor sets of minor nodes observed during training. 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 an oversampled node with all neighbors of original node will change the edges of neighbor nodes as well and hence significantly alters 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 neighbors 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.
In this paper, we propose GraphENS, a 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 in 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, we introduce a 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 ‘neighbor 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 baselines on multiple benchmark datasets including real-world imbalanced datasets. Even in highly imbalanced synthetic graphs, our method exhibits superior performance.

heading: 2 RELATED WORK AND PRELIMINARY

heading: 2.1 CLASS IMBALANCE PROBLEM
text: 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 a 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 et al., 2020; Wang et 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 et 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 to adjacent nodes. GraphSMOTE (Zhao et al., 2021) generates synthetic minor nodes by interpolating two minor class nodes and a (pretrained) edge predictor determines the connectivity of synthetized nodes between synthetized 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 an 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 is low in Section 5.3 (Table 4).

heading: 2.2 GRAPH NEURAL NETWORKS FOR NODE CLASSIFICATION
text: 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 ∈ R|V |×d be the node features whose the i-th row represents the d-dimensional feature of the i-th node. N (v) is the set of adjacent nodes that are directly connected to v: {u ∈ V |{u, v} ∈ E}. In node classification, each node in the graph corresponds to a class y ∈ {1, . . . , C} where C is the number of classes. In this paper, we consider several variants of GNNs that consists of three differentiable functions: 1) message function ml, 2) permutation invariant message aggregation function φl, and 3) node update function hl. Let x (l) v be the latent vector of node v at layer l. To simplify notations for the recursive definition of GNNs, we use x(0)v to denote the input node feature. At each GNN layer, node features are updated as x(l+1)v = hl(x (l) v , φl({ml(x(l)v , x(l)u , ev,u)|u ∈ N (v)}) to consider adjacent node embeddings. By passing these aggregated node features to a linear classifier as input, we obtain the prediction ŷ = f(xv) for node v where ŷc = P (y = c|xv). As a representative example, a layer of Graph Convolutional Network (GCN) (Kipf & Welling, 2017) is defined as x (l+1) v = Θ ∑ u∈N (v)∪{v}
ev,u√ d̂ud̂v x (l) u where d̂v = 1 +
∑ u∈N (v) ev,u with ev,u is the edge weight
of edge {u, v} ∈ 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.

heading: 3 NEIGHBOR MEMORIZATION PROBLEM
text: In this section, we define and investigate the neighbor memorization problem uniquely appearing in the node classification task of a class-imbalanced 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 vminor, but also overfitting to N (vminor) can be an issue. That is, the model is exposed to highly restricted neighboring structures for minor classes. Here, since GNN models are based on message passing that receives information from (a number of) neighboring nodes, we hypothesize that the overfitting and memorizing N (vminor) can be more serious than overfitting to vminor, and we experimentally verify that below.
Experimental setup We first conduct experiments to observe overfitting to minor classes on classimbalanced graphs. GNNs are trained with two widely used methods - re-weighting and oversampling on a node classification benchmark dataset, PubMed (Sen et al., 2008). We process the
PubMed dataset to follow a long-tailed 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 1 (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 train accuracy of the minor class is extremely high. This result implies that the existing approaches are prone to memorize minor class nodes. Note that we 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 are almost maintained until the last epoch for both methods. The learning curve for entire epochs is in Appendix A.2 (Figure 5). In the following paragraph, we investigate more specifically whether this overfitting is mainly due to memorizing node features or their neighbor structures.
Neighbor memorization problem To investigate which kinds of information GNN is prone to be more overfitting - 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 a seen minor node with an unseen minor node given a fixed seen neighbors (node-replacing experiment). Toward this, we randomly sample three nodes from the identical minor class: we sample vanchor (recipient), vseen (donator) from the training set and vunseen (donator) from the test set. We then replace the feature of vanchor with that of vunseen in the original graph, and evaluate the classification accuracy of replaced vanchor. 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 vseen 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 1(c), the blue and red bars represent the results of vanchor with seen node features and vanchor with unseen node features, respectively.
Now, we conduct a 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 selfnode feature (neighbor-replacing experiment). We sample vseen (donator) and vanchor (recipient) from the training set and vunseen (recipient) from the test set as before, but vanchor now has a different role compared to the node-replacing experiment: it serves as providing a seen neighbor set. Specifically, we replace the feature of vunseen with that of vseen, which represents the situation where a seen node is embedded into unseen neighbors. Then, we evaluate the classification accuracy of replaced vunseen. For a baseline, the node feature of vanchor is replaced by that of vseen and measures the accuracy of replaced vanchor; it is the case of seen node feature with a seen neighbor set. In Figure 1(d), the blue bar denotes the performance of seen node feature with seen neighbor set
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 B.
We demonstrate that conventional imbalance handling approaches severely suffer from a neighbor memorization problem in Figure 1(c) and (d)1. The performance drop of conventional algorithms in the neighbor-replacing experiment is almost two times 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 largely rely on the neighbor information compared to the node features. This neighbor memorization problem results in poor generalization performance on the minor class, so it must be appropriately addressed in class-imbalanced node classification. Recent work, GraphSMOTE (Zhao et al., 2021), connects a mixed node to neighbors of both the source node and target node in the same class, and then removes the unreliable edges by the feature similarity-based edge predictor. However, since GraphSMOTE only utilizes the neighbors of the 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.

heading: 4 GRAPHENS
text: We now describe our novel class-imbalance handling strategy for node classification, GraphENS that synthesizes an ego network for generated minor nodes considering the prediction similarity of the ego network instances, in order to alleviate the neighbor memorization described above. GraphENS is mainly composed of two core components. Both components exploit the features from two nodes: the minor class node vminor and the target node vtarget from entire classes2 to synthesize an ego network of minor class. The first component is to augment the neighbor set by combining neighbors of a minor node vminor with those of the target node vtarget. To prevent the generation of harmful ego networks, GraphENS regulates the combination ratio depending on the KL divergence between ego networks centered on vminor and vtarget, 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 vminor and vtarget 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-specific node features in the node feature mixing process to preserve the semantics of the minor class. The overall procedure of GraphENS is described in Figure 2. Our full algorithm is also provided in the Appendix C (Algorithm 1). We discuss the details of each component in the following subsections.
1To reduce the negative effect of oversampling on message-passing, we make the message passing work only on incoming edges to the oversampled nodes.
2Detailed explanation and justification for this strategy for target node selection are discussed in Section 5.2.

heading: 4.1 NEIGHBOR SAMPLING
text: Neighbor sampling is a method to determine which nodes to be connected to a new mixed node, vmixed (how to synthesize a 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 a mixed node from two ego networks of vminor and vtarget 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 (vtarget) more in constructing the adjacent node distribution when the ego network of vtarget is more similar to that of vminor. Note that the ego network Gv of node v consists of {Nv ∪ v} 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 distribution for vmixed by mixing adjacent node distributions of vminor and vtarget. Here, the adjacency node distribution for a real node v, p(u|v), is defined as p(u|v) = 1|N (v)| if u ∈ V, {u, v} ∈ E, and p(u|v) = 0 otherwise. To construct a ‘probable’ adjacent node distribution, the mixing ratio is determined based on the similarity between the ego networks of Gvminor and Gvtarget . Toward this, we utilize logits ov = f(G)v for a node v 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 at 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 aggregated logit of node v is computed as ôv = 1|N (v)|+1 ∑ u∈(N (v)∪v) ou. Then, we calculate the KL-divergence between ôminor and ôtarget to estimate the distance between Gvminor and Gvtarget : φ = KL (σ(ôminor)‖σ(ôtarget)) where σ is a softmax function. Now, the normalized distance is used as the mixing ratio for the minor adjacent node distribution, and it is calculated as φ̂ = 1
1+e−φ .
Finally, the adjacent node distribution for the synthesized vmixed is defined as
p(u|vmixed) = φ̂ p(u|vminor) + (1− φ̂) p(u|vtarget). (1) 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.
Sampling neighbors Given the adjacent node distribution p(u|vmixed) in Equation 1, we sample neighbors from this distribution without replacement. The number of neighbors is sampled from the degree distribution of a 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 vmixed since undirected edges affect message passing in the original graph.

heading: 4.2 SALIENCY-BASED NODE MIXING
text: We now describe how our method synthesizes new central node vmixed of Gvmixed by interpolating two nodes vminor and vtarget. Note that our method does not restrict the target node to be from minor classes to utilize the abundant class-generic 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 vmixed using minor node features and generic features of target node via convex combination.
Feature saliency Albeit GraphENS does not depend on specific ways of calculating the importance 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 as follows.
We first compute the gradient of classification loss L(G,y) with respect to the input node feature matrix ∂L∂X ∈ R |V |×d via backpropagation. Then, the saliency value of i-th feature s(v,i) is obtained
by the magnitude of the gradient regarding i-th attribute in node v as s(v,i) = ∣∣∣∣[∂L(G,y)∂X ]
(v,i)
∣∣∣∣ . The
feature saliency vector Sv = [s(v,1), ..., s(v,d)]T is derived without any modification to the GNN 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.
Node mixup We introduce our simple mixup-like augmentation to oversample the minor nodes without label mixing. Since we select target nodes vtarget from all classes unlike SMOTE (Chawla et al., 2002), filtering (or masking) out class-specific attributes of the target node is required to prevent the generation of noisy samples. To this end, we explicitly utilize the feature saliency information 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 vminor and vmajor, we adaptively assign K% proportional to normalized distance φ̂; K = kφ̂ where k is a hyperparameter. The intuition behind here is if target node vtarget is significantly differ from minor node vminor, we mask more salient features of vtarget. Specifically, given the feature saliency vector Svtarget , a binary mask MK ∈ Rd, which masks the K% of node attributes to 0, is sampled from multinomial distribution by applying softmax to Svtarget . Our final synthesized minor nodes vmixed can be formulated as follows given a random mixing ratio λ ∼ Beta(α, α):
vmixed = (1− ΛK) vminor + ΛK vtarget, where ΛK = λ ·MK . (2)
We also evaluate our method but without using saliency on multiple datasets in Section 5.4 (Table 3).

heading: 5 EXPERIMENT

heading: 5.1 EXPERIMENT SETUP
text: 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 a 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 at 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 imbanlance 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. In semi-supervised setting, we set the imbalance ratio as 10. The detailed setup is provided in Appendix D.5.
Baselines We test our methods over three architectures as GCN (Kipf & Welling, 2017), GAT (Velickovic et al.), and GraphSAGE (Hamilton et al., 2017). We adopt re-weight as costsensitive loss (Japkowicz & Stephen, 2002) inversely proportional to the number of class data. 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 original node when adding an oversampled node to the original graph. cRT (Kang et al., 2020) and PC Softmax (Hong et al., 2021) are recent effective baselines for decoupling and post-hoc correction 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 or continuous values. We adopt a 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 D.
Table 2: Results on AmazonPhoto and AmazonComputers in comparison to baselines. The experiment was repeated 5 times and standard errors are reported. Note that the Acc. is equal to bAcc. as the test sets are balanced.
Method AmazonPhoto AmazonComputers
(Imbalance ratio: 82) (Imbalance ratio: 244) Acc.(bAcc.) F1 Acc.(bAcc.) F1
G ra
ph SA
G E Vanilla 82.86 ±0.30 78.72 ±0.52 68.47 ±2.19 64.01 ±3.18 Re-Weight 92.94 ±0.13 92.95 ±0.13 90.04 ±0.29 90.11 ±0.28 Oversampling 92.46 ±0.47 92.47 ±0.48 89.79 ±0.16 89.85 ±0.17 cRT 91.24 ±0.28 91.17 ±0.29 86.02 ±0.55 86.00 ±0.56 PC Softmax 93.32 ±0.25 93.32 ±0.25 86.59 ±0.92 86.62 ±0.91 GraphSMOTE 92.65 ±0.31 92.61 ±0.32 89.31 ±0.34 89.39 ±0.35 GraphENS 93.82 ±0.13 93.81 ±0.12 91.94 ±0.17 91.94 ±0.17
Table 3: Ablation study. SM, NS, and PS denote saliency masking, neighbor sampling, and prediction similarity, respectively.
Method CiteSeer-semi AmazonPhoto (Imbalance ratio: 10) (Imbalance ratio: 82)
G ra
ph SA
G E
Acc bAcc. F1 Acc. bAcc. F1 GraphENS
(w/o SM,NS) 41.82 39.31 32.15 93.17 93.17 93.15 GraphENS (w/o SM) 49.24 48.77 45.85 93.54 93.54 93.53 GraphENS (w/o PS) 49.66 47.96 45.93 93.28 93.28 93.26 GraphENS 51.12 48.91 46.78 93.82 93.82 93.81
5.2 TARGET NODE SELECTION
bAcc. [%] F1-score [%]60
65
70
75 Cora-LT
bAcc. [%] F1-score [%]50
55
60
65 CiteSeer-LT Entire class Same class
Target Node vtarget Selection
Figure 3: Target node experiments (GAT).
Our method utilizes the target node vtarget from all classes, not only from the identical minor class of vminor. The intention of constructing the target node pool from entire classes is to guarantee sufficient diversity of synthesized ego networks. If the target nodes are restricted to a minor class at highly imbalanced scenarios, identical neighbor nodes would be redundantly duplicated. This issue makes it hard
to mitigate the neighbor memorization problem. To demonstrate this hypothesis, we conduct an experiment and compare our design choice (all classes) to selecting a target from the identical class as the minor node vminor. In the Figure 3, we confirm that exploiting entire classes for the target node 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-specific attributes using saliency) as 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 a target node, we sample a target class from the multinomial distribution with (logN1, logN2, . . . , logNC) where Ni is the number of the i-th class data and C is the number of classes. Then, we randomly select a target node from the training nodes of the sampled class.

heading: 5.3 MAIN RESULTS
text: Neighbor sampling mitigates neighbor memorization We investigate neighbor memorization over conventional algorithms in Section 3. We validate ours with respect to overfitting to minor classes, node memorization, and neighbor memorization. Although our training accuracy of the minor class is similar to re-weighting and oversampling, the test accuracy of our method is much higher than baselines, which indicates that our approach mitigates overfitting to minor classes in Figure 1 (a) and (b). Our method significantly decreases the performance degradation when seen neighbor set is replaced by an unseen neighbor set, implying that our approach can generalize well for unseen neighbor views compared to baselines (Figure 1 (d)). Neighbor sampling thus effectively alleviates the neighbor memorization by exposing minor nodes to diverse circumstances.
Supervised Learning We evaluate GraphENS on highly class-imbalanced situations as most realworld graphs. First, we test our method on three long-tailed citation networks: Cora-LT, CiteSeerLT, 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 imbalanced graphs, we also test GNNs trained with GraphENS on naturally class-imbalanced benchmark datasets without any modifications in graphs. Our method outperforms other contenders by significant margins in AmazonComputers (Table 2). Note that our method consistently exhibits higher accuracy and F1 score in other architectures (Table 5 in Appendix A.3).
Semi-supervised learning To validate our approaches when labeled nodes are extremely restricted, we conduct experiments in a semi-supervised setting on citation networks (Table 4). Our approach significantly outperforms baselines for all datasets. Ours also exhibits consistent superior performances in other GNN architectures (Table 6). Note that since GraphENS exploits entire classes to synthesize minor nodes, our method can avoid the generation of redundant nodes when the number of minor nodes is extremely low. Hence, our method significantly improves the performance against existing oversampling based approaches- GraphSMOTE, Oversampling. Ours brings further performance gain by utilizing unlabeled nodes to generate ego networks (Appendix A.4).

heading: 5.4 ABLATION STUDY
text: 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’ determines prediction similarity uniformly random, 2) ‘w/o SM’ mixes nodes without saliency masking (MK = 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 performance (Table 3). Thus, we believe each module effectively contributes to restrain the generation of harmful ego networks.

heading: 6 CONCLUSION
text: We investigated that existing imbalance handling algorithms suffer from neighbor memorization problem in class-imbalanced node classification. Thus, we proposed a novel augmentation method, GraphENS, to synthesize an ego network for minor classes with neighbor sampling and saliencybased 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.

heading: A ADDITIONAL EXPERIMENTAL RESULTS
text: In this section, we present experimental results which are not reported in the main paper due to space constraints.

heading: A.1 CLASS-WISE PERFORMANCE ANALYSIS
text: 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 is as follows: ( Minor 1: 72, Minor 2: 726, Major: 7260 ). The experiment settings are identical to Section 3.
In Figure 4 (a), while the training accuracies for minor classes (Minor 1, Minor 2) are highly similar over entire methods, GraphENS exhibits significantly superior test accuracies for minor classes (Figure 4 (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.

heading: A.2 LEARNING CURVE OF THE TRAINING PHASE
text: To show the early trend of the training process, we only show the learning curve for the first 200 epochs in our main paper. We observe that the gap between training and test accuracy is maintained over entire epochs in Table 5.

heading: A.3 THE RESULTS OF AMAZONPHOTO AND AMAZONCOMPUTERS
text: Due to space constraints, we only present the experiment table with GraphSAGE in the main paper, which exhibits the best vanilla performances, on two co-purchase graph datasets - AmazonPhoto, AmazonComputers. We also test our method with two different GNN architectures - GCN, GAT. As shown in Table 5, GraphENS shows the best performances over baselines in most cases. Detailed experimental settings are described in Section D.
Interestingly, we observe that cRT and PC Softmax show inferior performance than other algorithms on AmazonComputers (Table 5). We conjecture that these approaches fail to learn discriminative representations of minor classes due to message-passing in a highly imbalanced graph. Decoupling methods such as CRT and PC Softmax are proposed based on the observation that retraining a classifier with class-balanced sampling after training on imbalanced datasets show comparable performance 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 consistent with the observation that decoupling methods fail at the extremely high imbalance ratio (Ren et al., 2020).

heading: A.4 THE EXPERIMENTS IN SEMI-SUPERVISED LEARNING
text: In Section 5.3, we report the results of GCN on three citation networks - Cora, CiteSeer, PubMed. We additionally put the result table of two different GNN architectures - GAT, GraphSAGE. emphGraphENS outperforms baselines in most cases (Table 6).
To further improve the performance, we extend GraphENS to utilize unlabeled nodes and validate the extended model. First, we regard unlabeled data as theC+1-th class (C is the number of classes) and this class could be sampled when selecting a target node. Since the number of unlabeled data is large, the labeled class could be sampled less frequently if we utilize the number of unlabeled data in the multinomial distribution in Section 5.2. Thus, we treat the unlabeled class as the class having the same number of data with the least frequent class and sample a target class from the distribution with (logN1, logN2, . . . , logNC , logNC+1) where Ni 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, exploitation of saliency maps of source nodes is required.
In Table 6, the adoption of unlabeled data in GraphENS improves the performance significantly in many cases. We speculate that our approach could exploit rich information even in unlabeled nodes to produce safe and diverse ego networks.
A.5 VISUALIZATION OF THE HIDDEN REPRESENTATIONS
In this subsection, we shed light on why our 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 in 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 of the imbalance-handling 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.
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 we conduct experiments on Cora-LT with 2 layers of GraphSAGE. Compared to Re-weighting, we observe 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 of minor classes smoothly.

heading: A.6 OVERSAMPLING RATIO
text: We investigate the performance tendency according to 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) over 1.0. We conjecture that the induced bias of major classes is not sufficiently corrected at low oversampling scales (1). In the regime of (2), a 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 a preferable option and we adopted 1.0 as the scale in our main experiments, following conventional oversampling methods.
B ILLUSTRATIONS OF REPLACING EXPERIMENTS
To facilitate understanding of node/neighbor replacing experiments, we describe the experiments with intuitive illustrations. In Figure 8, to observe node memorization, we replace the node feature of vanchor with vseen in (a) and vanchor with vunseen in (b). The performance gap between vanchor in (a) and (b) is computed. Similar to node-replacing experiments, to see neighbor memorization, we replace the node feature of vseen with vanchor in (c) and vseen with vunseen in (d). The accuracy difference between vseen in (c) and vunseen in (d) is calculated. The results of replacing experiments are in Figure 1.

heading: C MAIN ALGORITHM
text: Algorithm 1 GraphENS 1: Input: Dataset (G(V,E), y), model fθ , class distribution pclass(C), class-conditional node distribution pnode(u|c), degree distribution pdegree(D), number of classes C, number of samples to be oversampled Nosc , feature masking hyperparameter k, learning rate η, temperature τ
2: Initialize: Model fθ . 3: for t = 1, 2, . . . , T do 4: Vnew, Enew ← V , E 5: for c = 1, 2, · · · , C do 6: for i = 1, 2, · · · , Nosc do 7: ctarget ∼ pclass(C) . Sampling target class 8: vtarget ∼ pnode(u|ctarget) 9: vminor ∼ pnode(u|c) 10: λ ∼ Beta(2, 2) 11: if t ≤ 10 then . Warmup 12: vmixed← (1− λ)vminor + λvtarget 13: vn1 , vn2 , · · · , vn|N(vminor)| ← Neighbors of vminor 14: Ênew ← {{vn1 , vmixed}, {vn2 , vmixed}, · · · , {vn|N(vminor)| , vmixed}} 15: else 16: φ←KL(ôt−1vminor‖ô t−1 vtarget) 17: φ̂← 1 1+e−φ 18: 19: . Saliency-based node mixing

heading: 20: K ← kφ̂
text: 21: Compute MK from multinomial distribution using St−1,K 22: ΛK ← λ ·MK 23: vmixed← (1− ΛK) vminor + ΛK vtarget 24: 25: . Neighbor sampling

heading: 26: p(u|vmixed)← φ̂p(u|vminor) + (1− φ̂)p(u|vtarget)
text: 27: r ∼ pdegree(D) 28: {vn1 , vn2 , · · · , vnr} ∼ p(u|vmixed) 29: Ênew ← {{vn1 , vmixed}, {vn2 , vmixed}, · · · , {vnr , vmixed}} 30: end if 31: Vnew ← Vnew ∪ {vmixed} 32: Enew ← Enew ∪ Ênew 33: end for 34: end for 35: o← fθ(Vnew, Enew) 36: Lnew ← CrossEntropy(o,y) 37: θ ← θ − η(∇θLnew) 38: for v ∈ V do 39: ôtv ← 1|N (v)|+1 ∑ u∈(N (v)∪v) Softmax(ou/τ) . Confidence aggregation 40: end for 41: St← Computing feature saliency with the gradient of Lnew (Equation. (2)) 42: end for 43: Output: fθ

heading: D DETAILED EXPERIMENT SETTINGS
text: In this section, we address all the details of experiments we conducted.

heading: D.1 DATA STATISTICS

heading: D.2 ARCHITECTURE
text: 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, we describe the detailed architecture of each GNN. For GCN, our model consists of l GCN layers with ReLU activation, followed by dropout Srivastava et al. (2014) with 0.5 dropping rate and a linear classifier. For GAT, our model comprises l GAT layers, which involves an ELU activation Clevert et al. (2016), followed by dropout with 0.5 dropping rate and a linear classifier. We also adopt multi-head attention with 8 heads and apply dropout with 0.6 dropping rate to its attention. GraphSAGE is composed of l SAGE layers with ReLU activation, followed by dropout with 0.5 dropping rate and a 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 l ∈ {1, 2, 3} and hidden dimension d ∈ {64, 128, 256}.

heading: D.3 EVALUATION PROTOCOL
text: 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 a scheduler as a learning rate is halved if there is no improvement on validation loss for 100 iterations. We choose weight decay to all convolutional layers except for a linear classifier with 0.0005. We select the best model using validation accuracy over the training phase.
D.4 IMPLEMENTATION DETAILS
In this subsection, we explain the hyperparameters of our experiments. For all datasets, we use Beta(2, 2) distribution to sample λ. Feature masking hyperparameter k and temperature τ are tuned among {1, 5, 10} and {1, 2}, respectively. We employ warmup since our approach utilizes model confidence, so models need to be trained to some extent. The number of epochs for warmup is tuned among {1, 5}.

heading: D.5 THE DETAILED SETUP FOR SEMI-SUPERVISED LEARNING
text: 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.

Review summaries:
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.

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.

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. The proposed method alleviates the neighbor memorization problem by synthesizing ego networks. Extensive experiments are conducted to evaluate the proposed method.