Generate or Re-Weight? A Mutual-Guidance Method for Class-Imbalanced Graphs

1 Introduction

Graph Neural Networks (GNNs) have demonstrated impressive success across a range of graph analyzing tasks, including fraud detection, transportation analysis, disease diagnosis, and so on [Zhang et al., 2024; Rahmani et al., 2023; Sun et al., 2020]. Their remarkable performance is typically under the assumption of class balance, i.e., samples across various categories are unbiased in quantity [Ju et al., 2024]. However, the above assumption barely holds, as the class imbalance exists inherently in real-world scenarios [Dou et al., 2020; Liu et al., 2021]. It refers to a few classes holding enormous labeled nodes (i.e., majority class), while most classes contain limited labeled nodes (i.e., minority class). For instance, in fake account detection, the majority of users are benign, while only a few of them are bots. Analogously, in financial fraud detection, the quantity of compliant users far exceeds that of fraudsters. Once trapped in the problem of class imbalance, the GNN-based models over-fit the majority classes and under-represent the minority ones.

∗Corresponding Authors.

The studies tailored for the class-imbalanced graphs are categorized into generative and re-weighting methods. The former intends to synthesize new samples for minority classes, thereby balancing the distribution of samples across various categories. For example, GraphSMOTE first extends the existing over-sampling methods to graph-structured data [Zhao et al., 2021]. GraphSHA explores the subspace squeeze issue of minority classes and enlarges the decision boundaries of minority classes by synthesizing harder minority samples [Li et al., 2023]. The latter aims to fine-tune the weight of each sample, thus compelling the model to focus on minority ones. For instance, ReNode provides a unified perspective on analyzing the quantity and topology imbalance jointly by taking into account the node influence shift [Chen et al., 2021]. TAM adjusts margins node-wisely according to the extent of deviation from connectivity patterns [Song et al., 2022]. However, both generative and re-weighting methods only adhere to their standpoints and ignore potential collaboration. To this end, we revisit the generative and re-weighting methods to explore the underlying problems with an empirical study in Figure 1. It tells us two inspiring observations.

(1) Generative Perspective. The generative methods focus on synthesizing samples for each category until matching the majority. Thus, a question arises: Does the generated equal quantity balance the learning ability of the model for each category? To answer this question, we plot the mean loss of each category in Figure 1 (a). It can be observed that even if the number of samples in each category is balanced, the model still exhibits differences in its learning ability. This observation demonstrates that generative methods still lack the supervision to quantify the number of synthesized samples for each category.

(2) Re-weighting Perspective. The re-weighting methods are designed to increase the significance of minority samples, thereby compelling the model to allocate greater attention to these instances. In general, the authentic and generative samples are treated equally. Nevertheless, can the model learn them impartially? Analogously, we visualize the mean loss of authentic and generative samples for each category, respectively. The results are shown in Figure 1 (b). It can be seen that the model generalizes well on the authentic samples but struggles with the generative ones. This phenomenon indicates that it is essential to re-weight the authentic and generative samples to balance the concern of the model.

To this end, we propose a Mutual-Guidance method for the class-imbalanced graphs. To the best of our knowledge, it is the first try to incorporate the generative and re-weighting method into a unified framework. Specifically, we present an uncertainty-aware method to quantify the number of synthesized samples for each category. It first measures the mean loss of samples for each category to identify the uncertainty of the model. Then, it leverages the uncertainty to quantify the number of synthesized samples for each category adaptively. Furthermore, we devise a similarity-aware method to re-weight the importance of the authentic and generative samples. It summarizes the pacesetter feature by averaging the features of labeled samples belonging to the same category. Subsequently, it re-weights the generative samples by evaluating the similarity of their features and the corresponding pacesetter features. We conduct experiments under two imbalanced settings on five datasets. The experimental results demonstrate that our method outperforms ten competitive methods.

The main contributions of this work are as follows.

• We propose a mutual-guidance method for classimbalanced graphs. It is the first try to incorporate the generative and re-weighting method into a unified framework.
• We design an uncertainty-aware method to quantify the number of synthesized samples for each category.
• We devise a similarity-aware method to re-weight the importance of the authentic and generative samples.
• We conduct extensive experiments on five classimbalance datasets to verify the effectiveness of the proposed method.

2 RelatedWork

2.1 Graph Neural Networks

Graph Neural Networks are deep learning models designed to learn and reason directly on graph-structured data [Wu et al., 2020]. They can be categorized into Spectral Graph Neural Networks and Spatial Graph Neural Networks based on their implementation manners. Spectral Graph Neural Networks aim to define the graph convolution through spectral graph theory and the convolution operation. Bruna et al. first formalized the definition of spectral graph convolution and emphasized its high computational complexity [Bruna et al., 2014]. To this end, Defferard et al. introduced the k-order Chebyshev polynomial to approximate the graph convolution kernel [Defferrard et al., 2016]. Kipf et al. advanced it by leveraging the limited 1-order Chebyshev polynomial and renormalization technique, giving rise to Graph Convolutional Networks (GCN) [Kipf and Welling, 2017]. Spatial Graph Neural Networks incorporate structural and node feature information by defining neighborhood aggregation functions. Gilmer et al. proposed the Message Passing Neural Network (MPNN), a general framework for spatial graph convolution [Gilmer et al., 2017]. Veliˇckovi´c et al. presented the Graph Attention Network (GAT), which defines the aggregation function using a learnable attention mechanism [Veliˇckovi´c et al., 2018]. Hamilton et al. introduced GraphSAGE, a model that leverages neighbor sampling and a variety of aggregation functions to explore the fusion of neighboring information [Hamilton et al., 2017]. Furthermore, researchers also investigated some interesting techniques for GNNs, such as graph transformer [Yun et al., 2019], graph diffusion [Li et al., 2024], graph foundation model [Mao et al., 2024], etc.

2.2 Class-Imbalance Problem

Class imbalance is a ubiquitous challenge in graph representation learning [Liu et al., 2023]. The existing countermeasures can be classified into generative and re-weighting methods. The former is devoted to synthesizing minority samples to balance the training set. For example, Zhao et al. extended the over-sampling methods for i.i.d data to the graph [Zhao et al., 2021]. They utilized the feature extractor to construct an intermediate embedding space, then proceeded to train an edge estimator and the GNN-based classifier on top of that. Park et al. proposed GraphENS to relieve the neighbor memorization problem encountered by existing generative methods [Park et al., 2021]. It synthesizes an ego network for minor classes with neighbor sampling and saliency-based node mixing. Li et al. explored the problem of squeezed minority [Li et al., 2023]. Hence, they presented GraphSHA, which synthesizes harder samples to avoid invading the spaces of neighbor classes. The re-weighting methods intend to tilt the training focus towards minority samples. For instance, Cui et al. leveraged the number of effective samples among each class to re-weight the classes[Cui et al., 2019]. Wang et al. introduced a class prototype-driven training paradigm to balance the loss between majority and minority classes [Wang et al., 2022]. Park et al. explored the decision boundary in classimbalance scenarios and presented a novel influence-balance loss to solve the overfitting problem of majority classes. Song et al. proposed a topology-aware loss to re-weight margins node-wisely according to the extent of deviation from connectivity patterns [Song et al., 2022]. In addition, researchers also explored contrastive-based methods to mitigate the class imbalance on graphs [Zeng et al., 2023].

3.2 Framework

In this section, we propose a mutual-guidance method for class-imbalanced graphs, as illustrated in Figure 2. It mainly consists of two modules: (i) Uncertainty-Aware Quantification and (ii) Similarity-Aware Re-Weighting. In particular, it first schemes the synthetic paradigm of generated samples. Then, it focuses on their quantitative and weighting problems. Specifically, it evaluates the loss distribution to assess the uncertainty of the model across various classes and adjusts the number of samples generated for each class accordingly. Furthermore, it summarizes the pacesetter features by averaging the features of labeled samples in the same category. Subsequently, it measures the similarity of synthesized sample features and their corresponding class-wise pacesetter features. Afterward, it fine-tunes the weights of each synthesized sample. Finally, the GNN-based models are trained on the graph balanced from the perspectives of generative and re-weighting. The implementation details are elaborated in the subsequent sections.

3.3 Synthetic Paradigm of Generative Sample

To synthesize a minority node, it first identifies an anchor node (i.e., vanc) and an auxiliary node (i.e., vaux). The anchor node is sampled from the minority class. Note that, to enlarge the decision boundary of the minority, it refers to the hardness-aware sampling strategy [Li et al., 2023]. Specifically, the hardness is measured in Eqn. (4).

where Hi is the hardness of node vi, Zi is the logits of vi, and τ is the temperature.

Then, it samples the minority anchor node vanc from the hardness-based multinomial distribution. In identifying the auxiliary node vaux, the category of vaux is sampled from the classification probability of the anchor node. Afterward,

3 ProposedMethod

3.1 Preliminaries

In this section, we first define the attributed graph and imbalance ratio. Then, we formulate the Graph Neural Networks. Finally, we clarify the task of node classification.

Definition 1. Attributed Graph. Suppose G = (V, E, X) is an attributed graph, where V = {v1, v2, ..., vn} is the set of nodes and E = {e1, e2, ..., em} is the set of edges. X ∈ R|V|×d is the feature matrix, where d represents the dimension of node features. A ∈ R|V|×|V| is the adjacency matrix, where Aij = 1 indicates that there is an edge between vi and vj , otherwise, Aij = 0.

Definition 2. Imbalance Ratio. Suppose the potential categories are in C = {c1, c2, ..., cl}, where the class with the most samples is denoted as cmax and the class with the least samples is abbreviated as cmin. Then, the imbalance ratio ρ is defined in Eqn. (1).

Definition 3. Graph Neural Networks. The messagepassing paradigm of GNNs can be summarized as aggregateupdate, which are specified in Eqn. (2) and Eqn. (3).

where ali is the aggregation of neighboring features at the l-th layer, Ni is the set of neighbors of vi, and hli is the embedding of vi at the l-th layer which is updated on hl-1 i and ali .

Problem. Node Classification. An attributed graph is denoted as G = (V, E,X). V L is the set of labeled nodes and V U is the set of unlabeled nodes, where |V L|<<|V U |. The goal of node classification is to train a model that takes feature matrix X and adjacency matrix A as input and predicts the labels of unlabeled nodes by learning and optimizing the function f (X, A) → ˆY.

within the nodes belonging to caux, the auxiliary node is sampled from the multinomial with their confidence in canc as the probability.

Let the feature of vanc and vaux be abbreviated as Xanc and Xaux, respectively. The feature of the synthesized node is mixed up according to Eqn (5).

where Xsyn is the feature of synthesized node and δ ∈ [0, 1] is the hyper-parameter that controls the relative importance of Xanc andXaux.

In modeling the topology of the synthesized node, it first identifies the degree of the synthesized node by sampling from the degree distribution of the entire graph as formulated in Eqn. (6) and Eqn. (7).

where PDg(k) is the probability of a node occupying degree k, I{·} is an indicator function, and ksyn is the degree of vsyn.

Then, it connects vsyn to the nodes within the 1-hop subgraph of vanc, as they tend to share the same label with vanc according to graph homophily. However, the 1-hop subgraph of vanc may contain fewer nodes than the sampled degree of vsyn. Furthermore, neighbor sampling from the unweighted graph ignores the topological information. Thus, it leverages graph diffusion to construct a normalized weighted graph as specified in Eqn. (8).

where ¯S ∈ R|V|×|V| is the normalized diffusion matrix, θr = α(1 - α)r , α is a hyper-parameter, T = AD-1 , and D is the diagonal matrix.

To reduce the computational cost, it only retains the top-K elements in each column of ¯S and sets the remaining elements to 0, sparsifying the normalized diffusion matrix. The sparsified diffusion matrix is denoted as ˜S. Finally, it leverages ˜Sanc to sample the neighbors of vsyn.

In summary, the synthesized node is defined in Eqn. (9).

where Xsyn, Nsyn, and Ysyn represent the feature, neighbor distribution, and class label of the synthesized sample, respectively.

3.4 Uncertainty-Aware Sample Quantification

The existing generative methods typically synthesize samples for each category until matching the majority. However, empirical studies have revealed that an equal number of training samples across various categories does not ensure balanced model learning. Hence, we propose an uncertaintyaware sample method to adaptively quantify the numbers of the synthesized samples for each category.

As we all know, the uncertainty of the model can be naturally reflected by training loss. Thus, it first measures the uncertainty for each category as specified in Eqn. (10) and Eqn. (11).

where V L is the set of labeled nodes, V S indicates the set of synthesized nodes, y is the ground truth label, ˆ y is the prediction, Lci represents the total loss of category ci, and Uci indicates the uncertainty of model for category ci.

Then, it schemes a flexible sample generation strategy. In contrast to existing methods that synthesize samples for each category until matching the majority, it exclusively focuses on synthesizing samples for categories whose sample count is less than the average one across all categories.

Specifically, it evaluates the class-wise average sample quantity by Eqn. (12).

where ¯Q is the class-wise average sample quantity and |C| indicates the number of categories.

Afterward, it quantifies the numbers of synthesized samples for each category by Eqn. (13) and Eqn. (14).

where U ′ci is the normalized uncertainty, Qci is the number of synthesized samples for category ci, β is the scale factor.

In summary, the uncertainty-aware quantification method adaptively identifies the numbers of the synthesized samples for each category from the perspective of the model, realizing the transition from "quantity balance" to "learning balance". Furthermore, it reduces the computational cost and avoids the noise introduced by excessive synthesized samples.

3.5 Similarity-Aware Sample Re-Weighting

The existing re-weighting methods aim to fine-tune the focus of the model on majority and minority. Nevertheless, the difference in learning difficulty between authentic and synthesized samples still troubles the model. Thus, we devise a similarity-aware method to re-weight the importance of synthesized samples.

As empirical studies have proven, the model generalizes well on the authentic samples but struggles with the synthesized ones. Therefore, it measures the difference between authentic and synthesized samples by similarity and emphasizes the focus of the model on the latter accordingly.

Specifically, it first evaluates the average feature of the labeled samples within the same class and denotes it as "pacesetter" in Eqn. (15).

where Xci pac is the pacesetter of class ci.

Subsequently, it identifies the weights by calculating the cosine similarity of the synthesized sample and its corresponding pacesetter as formulated in Eqn. (16).

where V S is the set of synthesized samples, Xci pac is the pacesetter for category ci, || · || is the Euclidean norm, γ is the gain factor, σ(·) is the sigmod function, and R(·) is the reciprocal operation.

To sum up, the similarity-aware re-weighting method finetunes the importance of each synthesized sample, achieving the switch of the re-weighting paradigm from "majorityminority" to "authentic-generative". Moreover, it improves the generalization ability of the model and relieves the risk of overfitting.

3.6 Optimization

The synthesized samples are inserted into the classimbalanced graph, steering the graph towards class balance. Finally, the GNNs are trained on the class-balance graph by optimizing the objective as formulated in Eqn. (17).

where L is the final optimization objective.

3.7 Algorithm and Complexity Analysis

The main procedures of our proposed GraphMuGu are summarized in Algorithm 1. The complexity of identifying the anchor and auxiliary nodes is O(|V L|2 ). For feature synthesis, the complexity is O(|V L|d). For topology modeling, the corresponding complexity is O( |V L | |V| |E|). For our proposed uncertainty-ware sample quantification, the time complexity of measuring the uncertainty is O(|V L| + |V S |). For our proposed similarity-aware sample re-weighting, the time complexity of evaluating the pacesetter is O(|V L|), and that of measuring weights is O(|V S |). In general, the additional complexity introduced by our method is O(2(|V L| + |V S |)), which enables its generalization to the large-scale graph.

4 Experiments

In this section, we conduct experiments to verify the effectiveness of our proposed method. We first introduce the datasets and baselines used in the experiments. Then, we elaborate on the implementation details. Finally, we conduct a comprehensive and in-depth analysis of the experimental results. We aim to answer the following four Research Questions.

Algorithm 1 The Proposed GraphMuGu Method

Input: Graph G = (V, E,X), adjacency matrix A, labeled node set V L with their labels Y L, unlabeled node set V U , potential categories C, GNN-based model fθ.

Output: fθ trained on the class-balance graph.

• 1: Calculate ˜S via graph diffusion and sparsification;
• 2: Calculate degree distribution PDg via Eqn. (6);
• 3: Calculate pacesetter Xpac according to Eqn. (15);
• 4: while not converge do
• 5: Calculate uncertainty Uci according to Eqn. (11);
• 6: Calculate uncertainty-aware synthesized sample quantification Qci via Eqn. (14);
• 7: Calculate node hardness according to Eqn. (4);
• 8: Sample anchor node vanc based on hardness;
• 9: Identify auxiliary node vaux based on classification probability of anchor node;
• 10: Mix feature of the synthesized node by Eqn. (5);
• 11: Model topology of synthesized node Nsyn ∼ ˜Sanc;
• 12: Calculate theweight of the synthesized node according to Eqn. (16);
• 13: Insert the synthesized nodes to G and train fθ on the class-balanced graph by optimizing Eqn. (17);
• 14: end while
• 15: return Optimized GNNmodel fθ.
• RQ1: How does the proposed method perform on longtailed and step imbalance issues?
• RQ2: How does each proposed module contribute to the performance?
• RQ3: How do the hyper-parameters take effect on the performance?
• RQ4: How does each proposed module work to benefit the model?

4.1 Datasets and Baselines

We evaluate the effectiveness of our proposed GraphMuGu on five widely-used datasets, including three citation datasets (Cora, Citeseer, and Pubmed) and two co-purchase datasets (Amazon-Photo and Amazon-Computers). The details of datasets are summarized in Table 1.

We compare the proposed GraphMuGu with ten competitive methods for class imbalance. They are classified into two categories, including loss modifying methods (Re-weight [Japkowicz and Stephen, 2002], PC Softmax [Hong et al., 2021], CB Loss [Cui et al., 2019], Focal Loss [Lin et al.,

2017], ReNode [Chen et al., 2021], and TAM [Song et al., 2022]) and generative methods (Upsample, GraphSMOTE [Zhao et al., 2021], GraphENS [Park et al., 2021], and GraphSHA [Li et al., 2023]).

4.2 Experimental Setup and Configurations

We leverage various GNNs (i.e., GCN [Kipf and Welling, 2017], GAT [Veliˇckovi´c et al., 2018], and GraphSAGE [Hamilton et al., 2017]) as the backbones. All of them are set to a 2-layer pattern. The number of multi-head is set to 8 for GAT. The dimension of the hidden layer is set to 64. Specifically, for our proposed GraphMuGu, α is set to 0.05 to measure the diffusion matrix, K is set to 128 to sparsify the diffusion matrix, and δ is sampled from β(1, 100). We perform the long-tailed class-imbalance experiments on the citation datasets and set the imbalance ratio ρ = 100. The step class-imbalance experiments are implemented on the copurchase datasets with an imbalance ratio ρ = 20. We refer to the reference [Li et al., 2023] to construct the class-imbalance datasets. For evaluation, we adopt Accuracy (Acc.), balanced Accuracy (bAcc.), and macro F1 score (F1) as the metrics.

4.3 Experimental Results and Analyses (RQ1)

The experimental results of long-tailed class-imbalance and step class-imbalance settings are shown in Table 2 and Table 3, respectively. The key observations are summarized as follows. 1) The proposed method achieves superior performance compared to the competitive methods (i.e., loss modifying methods and generative methods), demonstrating its effectiveness in addressing the class-imbalance issues among graph data. 2) The proposed GraphMuGu performs well on both the long-tailed and step class-imbalance settings, exhibiting the outstanding versatility of our method. 3) The proposed method yields a consistent improvement of performance across various datasets, proving the generalization ability of our proposed GraphMuGu.

4.4 Ablation Studies (RQ2)

In this section, we conduct ablation studies to verify the contribution of each component in the proposed GraphMuGu. We remove similarity-aware re-weighting and abbreviate the variant as GraphMuGu-UA. Analogously, we remove uncertainty-aware quantification and denote the variant as GraphMuGu-SA. We leverage GCN as the backbone and show the results in Figure 3. It can be observed that both uncertainty-aware quantification and similarity-aware re-weighting lead to significant improvement in performance. Furthermore, uncertainty-aware quantification performs well on datasets with more categories, and similarity-aware reweighting exhibits significant performance on datasets with more samples.

4.5 Hyper-Parameter Sensitivity Analysis (RQ3)

In this section, we investigate the performance of the method under various hyper-parameter settings. β controls total number of generated samples and γ controls the gain of weights. We leverage GCN as the backbone and exhibit the results in Figure 4. It can be seen that the model achieves the optimal results when β approximates the number of minority classes. The excessive value of β leads to the risk of noise, decreasing the performance of the model. In addition, the excessive value of γ results in insufficient learning of authentic samples, impairing the effectiveness of the model.

4.6 Visualization (RQ4)

In this section, we visualize the quantity of synthesized samples for each category and the weights of synthesized samples. We leverage GCN as the backbone and perform the experiments on Cora and Amazon-Photo datasets. The results are shown in Figure 5 and Figure 6. It can be seen that uncertainty-aware quantification and similarity-aware reweighting balance the model training by adaptively finetuning the number and importance of synthesized samples.

5 Conclusion

In this paper, we incorporate the generative and re-weighting methods into a unified framework to relieve the classimbalance problem on the graphs. It quantifies the uncertainty to identify the number of synthesized samples for each category. Furthermore, it measures similarity to re-weight the importance of the generative samples. Experimental results on five datasets demonstrate the effectiveness of our proposed method.

Acknowledgments

This research is supported by the National Key R&D Program of China (Grant No. 2022ZD0119501), the National Natural Science Foundation of China (Grant No. 62472263, 62072288, 52374221), the Taishan Scholar Program of Shandong Province, Shandong Youth Innovation Team, the Natural Science Foundation of Shandong Province (Grant No. ZR2024MF034, ZR2022MF268).