Overcoming Class Imbalance: Unified GNN Learning with Structural and Semantic Connectivity Representations

Class-imbalanced learning methods generally fall into three categories: re-sampling, re-weighting, and data augmentation. Re-sampling involves adjusting the original imbalanced data distribution to a class-balanced one by either up-sampling minority class data or down-sampling majority class data (Wallace et al., 2011; Mahajan et al., 2018). Re-weighting methods assign smaller weights to majority instances and larger weights to minority instances, either in the loss function or at the logits level (Ren et al., 2020; Menon et al., 2021). Data augmentation methods either transfer knowledge from head classes to augment tail classes or apply augmentation techniques to generate additional data for minority classes (Chawla et al., 2002; Kim et al., 2020; Zhong et al., 2021; Ahn et al., 2023). Traditional oversampling methods do not consider the graph structure when generating synthesized samples, making them unsuitable for graph data. Self-training methods for semi-supervised class imbalanced learning address class imbalance by supplementing the labeled set with unlabeled nodes predicted to belong to the minority class (Wei et al., 2021). However, GNNs’ bias towards majority classes can introduce noise in pseudo-labels, necessitating the development of new methods to mitigate the bias under class imbalance.

Traditional class imbalance methods assume independently distributed labeled instances, a condition not met in graph data where nodes influence each other through the graph structure. Existing class imbalanced graph learning can be categorized into three groups: re-weighting, over-sampling, and ensemble methods. Re-weighting methods assign importance weights to labeled nodes based on their class labels while considering the graph structure. Topology-Aware Margin (TAM) adjusts node logits by incorporating local connectivity (Song et al., 2022). However, re-weighting methods have limitations in addressing the under-reaching or neighborhood memorization problems (Park et al., 2021; Sun et al., 2022). Graph over-sampling methods generate new nodes and connect them to the existing graph. GraphSMOTE uses SMOTE to synthesize minority nodes in the learned embedding space and connects them using an edge generator module (Zhao et al., 2021). ImGAGN employs a generative adversarial approach to balance the input graph by generating synthetic nodes with semantic and topological features (Qu et al., 2021). GraphENS generates new nodes by mixing minority class nodes with others in the graph, using saliency-based node mixing for features and KL divergence for structure information (Park et al., 2021). However, these methods increase the graph size, leading to higher computational costs. Long-Tail Experts for Graphs (LTE4G) is an ensemble method that divides training nodes based on class and degree into subsets, trains expert teacher models, and uses knowledge distillation to obtain student models (Yun et al., 2022). It however comes with a computational cost due to training multiple models.

The Unified GNN Learning (Uni-GNN) framework comprises three crucial components: the structural node encoder, the semantic node encoder and the balanced node classifier. The structural node encoder is dedicated to constructing a graph adjacency matrix founded on structural connectivity, facilitating the propagation of node embeddings beyond the immediate structural neighbors of nodes. Concurrently, the semantic node encoder generates adjacency matrices based on semantic connectivity where it connects nodes to their semantically similar neighboring nodes, transcending structural distances. This facilitates the linking of nodes that are spatially distant in the graph but are from the same class, and enables message propagation between distantly located yet similar nodes, enriching the encoding process with learned node embeddings. At every layer in both the structural and semantic encoders, we propagate the integrated structural and semantic embeddings of the nodes along the corresponding connectivity, alleviating bias induced by each single type of connectivity. Ultimately, a balanced node classifier utilizes the acquired node embeddings from both the structural and semantic encoders for node classification. The overall framework of Uni-GNN is illustrated in Figure 1.

To leverage the unlabeled nodes in the graph, a balanced pseudo-label generation mechanism is proposed. The objective is to increase the number of available labeled nodes in the graph while considering the class imbalance in the set of labeled nodes. The goal is to generate more pseudo-labels from minority classes and fewer pseudo-labels from majority classes, thus balancing the class label distribution of the training data. In particular, for each class $c$, the number of nodes to pseudo-label, denoted as $\hat{N}_{c}$, is set as the difference between the largest labeled class size and the size of class $c$, aiming to balance the class label distribution over the union of labeled nodes and pseudo-labeled nodes:

The set of unlabeled nodes that can be confidently pseudo-labeled to class $c$ can be determined as:

where $\epsilon$ is a hyperparameter determining the confidence prediction threshold. Balanced sampling is then performed on each set $\hat{V}_{u}^{c}$ by selecting the top $\hat{N}_{c}$ nodes, denoted as $\text{Top}_{\hat{N}_{c}}(\hat{V}_{u}^{c})$, with the most confident pseudo-labels based on the predicted probability $P_{i}[c]$. This results in a total set of pseudo-labeled nodes, denoted as $\hat{V}_{u}$, from all classes:

The Unified GNN Learning framework is trained to minimize the following node classification loss over this set of pseudo-labeled nodes $\hat{V}_{u}$:

where $\ell_{\text{ce}}$ again is the standard cross-entropy loss function, $P_{i}$ is the predicted class probability vector with classifier $\phi$, and $\boldsymbol{1}_{\text{argmax}(P_{i})}$ is a one-hot pseudo-label vector with a single 1 at the predicted class entry $\text{argmax}(P_{i})$. This pseudo-labeling mechanism aims to augment the labeled node set, particularly focusing on addressing class imbalances by generating more pseudo-labels for minority classes.

We evaluate the performance of Uni-GNN framework on the semi-supervised node classification task under class imbalance. Across the three datasets, we explore four distinct evaluation setups by manipulating the number of minority classes and the imbalance ratio ($\rho$). Additionally, we explore the long-tail class label distribution setting for Cora and CiteSeer with an imbalance ratio of $\rho=1\%$. We assess the performance of Uni-GNN using balanced Accuracy (bAcc), Macro-F1, and Geometric Means (G-Means), reporting the mean and standard deviation of each metric over 3 runs. Table 1 summarizes the results for different numbers of minority classes and imbalance ratios on all three datasets, while Table 2 showcases the results under long-tail class label distribution on Cora and CiteSeer.

Table 1 illustrates that the performance of all methods diminishes with decreasing imbalance ratio ($\rho$) and increasing numbers of minority classes. Our proposed framework consistently outperforms the underlying GCN baseline and all other methods across all three datasets and various evaluation setups. The performance gains over the GCN baseline are substantial, exceeding 10% in most cases for Cora and CiteSeer datasets and 13% for most instances of the PubMed dataset. Moreover, Uni-GNN consistently demonstrates superior performance compared to all other comparison methods, achieving notable improvements over the second-best method (LTE4G) by around 3%, 5%, and 11% on Cora, CiteSeer with 3 minority classes and $\rho=10\%$, and PubMed with 1 minority class and $\rho=10\%$, respectively. Similarly, Table 2 highlights that Uni-GNN consistently enhances the performance of the underlying GCN baseline, achieving performance gains exceeding 8% and 12% on Cora-LT and CiteSeer-LT datasets, respectively. Furthermore, Uni-GNN demonstrates remarkable performance gains over all other class imbalance methods, surpassing 3% and 6% on Cora-LT and CiteSeer-LT, respectively. These results underscore the superior performance of our framework over existing state-of-the-art class-imbalanced GNN methods across numerous challenging class imbalance scenarios.

We conducted an ablation study to discern the individual contributions of each component in our proposed framework. In addition to the underlying GCN baseline, eight variants were considered: (1) Independent Node Encoders (Ind. Enc.): each node encoder exclusively propagates its own node embeddings, instead of propagating the concatenated semantic and structural embeddings. Specifically, $f^{\ell}_{\text{sem}}$ solely propagates ${H}_{\text{sem}}^{\ell-1}$ while $f^{\ell}_{\text{struct}}$ solely propagates ${H}_{\text{struct}}^{\ell-1}$. (2) Drop $\mathcal{L}_{\text{ps}}$: excluding the balanced pseudo-label generation. (3) $A_{\text{struct}}=A$: structural connectivity considers only immediate neighbors of nodes ($\alpha=1$). (4) Semantic Encoder only (Semantic Enc.): it discards the structural encoder. (5) Structural Encoder only (Structural Enc.): it discards the semantic encoder. (6) Imbalanced Pseudo-Labeling: it generates pseudo-labels for all unlabeled nodes with confident predictions without considering class imbalance. (7) Fixed $\{A^{\ell}_{\text{sem}}\}_{\ell=2}^{L}$: it does not update the semantic connectivity during training. (8) $\omega_{c_{i}}=1,\forall i\in V_{l}$: it assigns equal weights to all labeled nodes in the training set. Evaluation was performed on Cora and CiteSeer datasets, each with 3 minority classes and imbalance ratio ($\rho$) of 10%, and with long-tail class label distribution and imbalance ratio ($\rho$) of 1%. The results are reported in Table 3.

Table 3 illustrates performance degradation in all variants compared to the full proposed framework. The observed performance decline in the Independent Node Encoders (Ind. Enc.) variant underscores the importance of simultaneously propagating semantic and structural embeddings across both the semantic and structural connectivity. This emphasizes the need for incorporating both aspects to effectively learn more discriminative node embeddings. The performance drop observed in the Semantic Enc. and Structural Enc. variants underscores the significance and individual contribution of each connectivity type to the proposed Uni-GNN framework. This highlights the critical role that each type of connectivity plays in the overall performance of the proposed framework. The $A_{\text{struct}}=A$ variant’s performance drop emphasizes the importance of connecting nodes beyond their immediate structural neighbors, enabling the propagation of messages across a larger portion of the graph and learning more discriminative embeddings. The performance degradation in Drop $\mathcal{L}_{\text{ps}}$ and Imbalanced Pseudo-Labeling variants validates the substantial contribution of our balanced pseudo-label generation mechanism. The $\omega_{c_{i}}=1,\forall i\in V_{l}$ variant underscores the importance of assigning weights to each node in the labeled training set based on their class frequency. The consistent performance drops across both datasets for all variants affirm the essential contribution of each corresponding component in the proposed framework.

To investigate the impact of the hyper-parameters in Uni-GNN framework, we present the results of several sensitivity analyses on the Cora dataset with 3 minority classes and an imbalance ratio of 10% in Figure 2. Figures 2(a), 2(b), 2(c), and 2(d) depict the accuracy of Uni-GNN as we independently vary the max SPD distance in $A_{\text{struct}}$ ($\alpha$), the number of clusters ($K$), the pseudo-label confidence threshold ($\epsilon$) and the rate of updating $\{A^{\ell}_{\text{sem}}\}_{\ell=2}^{L}$ ($\beta$), respectively. Larger values for $\alpha$ result in performance degradation due to over-smoothing as the graph becomes more densely connected. Optimal performance is achieved with $\alpha=2$. Uni-GNN exhibits robustness to variations in the hyperparameters $K$, $\epsilon$, and $\beta$ within a broad range. It consistently outperforms state-of-the-art methods across diverse settings of these hyperparameters, as depicted by the corresponding results presented in Table 1. Small $K$ values lead to noisy clusters with mixed-class nodes, while large $K$ values result in over-segmented clusters with sparse semantic connectivity. Optimal performance is achieved when $K$ falls within the range of $5C$ to $15C$. Inadequately small values for $\epsilon$ result in the utilization of noisy pseudo-label predictions in the training process, while excessively large values exclude reasonably confident pseudo-labeled nodes from selection. The optimal range for $\epsilon$ lies between 0.4 and 0.7. Extremely small values for $\beta$ lead to frequent updates of the semantic connectivity, preventing Uni-GNN from learning stable discriminative embeddings. Values around 100 training epochs yield the best results.