Source-linked AI summary
GraphSMOTE: Imbalanced Node Classification on Graphs with Graph Neural Networks
Tianxiang Zhao, Xiang Zhang, Suhang Wang
TL;DR
Imbalanced node classes create a gap for GNN-based node classification because existing methods under-represent minority samples and do not preserve graph relations during oversampling. GraphSMOTE synthesizes minority nodes in an embedding space and uses an edge generator to supply their relations; experiments on three datasets outperform all baselines by a large margin.
Problem
Imbalanced node classification is insufficiently addressed by existing GNNs and i.i.d. imbalance methods, which do not account for graph relations and minority under-representation.
Method
GraphSMOTE constructs an intermediate embedding space for oversampling and jointly trains an edge generator and GNN-based node classifier.
Results
GraphSMOTE outperforms all baselines with a large gap in experiments on three datasets.
Takeaways & Limitations
The framework extends synthetic minority oversampling to graph data by generating natural nodes together with relation information.
Takeaways & Limitations
Experiments mainly cover citation and social-media networks, leaving other application domains for future work.
Abstract
from arXiv · showhide
Node classification is an important research topic in graph learning. Graph neural networks (GNNs) have achieved state-of-the-art performance of node classification. However, existing GNNs address the problem where node samples for different classes are balanced; while for many real-world scenarios, some classes may have much fewer instances than others. Directly training a GNN classifier in this case would under-represent samples from those minority classes and result in sub-optimal performance. Therefore, it is very important to develop GNNs for imbalanced node classification. However, the work on this is rather limited. Hence, we seek to extend previous imbalanced learning techniques for i.i.d data to the imbalanced node classification task to facilitate GNN classifiers. In particular, we choose to adopt synthetic minority over-sampling algorithms, as they are found to be the most effective and stable. This task is non-trivial, as previous synthetic minority over-sampling algorithms fail to provide relation information for newly synthesized samples, which is vital for learning on graphs. Moreover, node attributes are high-dimensional. Directly over-sampling in the original input domain could generates out-of-domain samples, which may impair the accuracy of the classifier. We propose a novel framework, GraphSMOTE, in which an embedding space is constructed to encode the similarity among the nodes. New samples are synthesize in this space to assure genuineness. In addition, an edge generator is trained simultaneously to model the relation information, and provide it for those new samples. This framework is general and can be easily extended into different variations. The proposed framework is evaluated using three different datasets, and it outperforms all baselines with a large margin.
1 INTRODUCTION
GraphSMOTE addresses imbalanced node classification, where minority classes are under-represented and existing graph-independent oversampling methods fail to preserve graph relations. It generates minority samples in an embedding space and supplies relation information through an edge predictor.
- Imbalanced node classes can cause majority classes to dominate GNN loss, leading to over-classification of majority nodes and poor minority prediction.
- Existing imbalance methods are difficult to apply to graphs because they assume independent samples and neglect relational information affecting embeddings and neighborhood exchange.
- GraphSMOTE generates synthetic nodes in an intermediate GNN embedding space, where same-class samples are denser and interpolation is more likely to remain in-domain.
- An edge predictor learns genuine edge distributions to provide relation information between generated nodes and existing graph samples.
- GraphSMOTE extends oversampling to graph data, and experiments on three datasets report a large performance gap over all baselines.
2 RELATED WORK
Related work covers conventional class-imbalance methods and graph neural networks, highlighting why i.i.d. oversampling techniques such as SMOTE do not directly transfer to graph-structured data.
- Class-imbalance methods comprise data-level sampling, algorithm-level class penalties or priors, and hybrid combinations.
- SMOTE creates minority samples by interpolating between minority examples and their nearest neighbors, while extensions modify where or how interpolation occurs.
- Synthetic minority oversampling methods such as SMOTE are widely regarded as popular and effective for class imbalance in i.i.d. data.
- Existing oversampling methods cannot directly handle graphs because raw-feature synthesis ignores graph information and generated nodes lack graph links.
- GNNs model graph-structured data through message passing, while existing GNN work had not considered class imbalance despite its prevalence in applications.
3 PROBLEM DEFINITION
The paper formulates semi-supervised, transductive node classification on an attributed graph with imbalanced class sizes. The goal is a classifier that performs well for both majority and minority classes.
- The task uses one graph for training and testing, with only a subset of nodes labeled and class sizes distributed imbalancedly.
- An attributed network is represented as G = {V, A, F}, with nodes V, adjacency matrix A, and node-attribute matrix F.
- Only labels for the labeled node subset V_L are available during training, although the graph contains m classes.
- The imbalance ratio is defined using the smallest and largest class sizes, and it is small in the imbalanced setting.
- The objective is to learn a node classifier that works well for both majority and minority classes.
4 METHODOLOGY
GraphSMOTE balances imbalanced node classes by interpolating minority nodes in a GNN embedding space and predicting their missing graph relations. Its modular framework combines feature extraction, synthetic-node generation, edge generation, and GNN classification.
- Feature Extractor: GraphSMOTE uses a GNN-based feature extractor to learn node representations that preserve node properties and graph structure.The framework illustrates this pipeline in Figure 2 and can use different GNN architectures.
- Synthetic Node Generation: SMOTE interpolates minority nodes with same-class nearest neighbors in the learned embedding space to generate labeled synthetic nodes.The nearest neighbor is selected by Euclidean distance, and a uniform random interpolation variable controls each synthetic representation.
- Edge Generator: An edge generator learns relation information from real nodes and existing edges, then predicts links for synthetic nodes.Its weighted inner-product design is trained to reconstruct the observed adjacency structure before predicting relations involving generated nodes.
- Augmented Classification: GraphSMOTE inserts generated nodes and predicted edges into an augmented adjacency matrix that is supplied to the GNN classifier.The augmented graph balances class sizes, enabling classifier training on the oversampled structure.
- Edge Strategies: The framework supports thresholded binary edges or differentiable soft edges, allowing the edge generator to receive node-classification training signals.Soft edges enable gradients to propagate through the augmented adjacency matrix, whereas the first strategy uses edge reconstruction alone.
- Framework Properties: GraphSMOTE is general, combines interpolated embeddings with predicted edges, and can optimize its feature extractor using both classification and edge-prediction signals.The full framework is trained with multiple components and can incorporate different component structures or regularization terms.
5 EXPERIMENTS
The experiments evaluate GraphSMOTE and baselines for imbalanced node classification across datasets, variants, metrics, and sampling configurations. They assess effectiveness, sensitivity to over-sampling scale, and generalization across imbalance ratios and model settings.
- Experimental Questions: The experiments vary over-sampling scales, imbalance ratios, and base model structures to evaluate effectiveness and generalization.The study explicitly examines GraphSMOTE effectiveness, sampling-scale effects, and robustness to different imbalance ratios or backbone models.
- Datasets: Experiments use Cora, BlogCatalog, and Twitter, combining artificial and genuine class-imbalance settings.Cora is artificially imbalanced, while BlogCatalog has a genuine imbalanced distribution; Twitter is a fake-account detection dataset.
- Methods: The comparison includes over-sampling, Re-weight, SMOTE, Embed-SMOTE, and four GraphSMOTE implementations.The GraphSMOTE variants differ in edge-generator training and whether predicted edges are binary, continuous, or pre-trained.
- Configurations: All methods are implemented on the same GNN-based network for a fair comparison.The experiments use ADAM optimization and train models until convergence, with a maximum of 5000 epochs.
- Evaluation Metrics: Performance is measured with classification accuracy, mean AUC-ROC, and mean F-measure.AUC-ROC and F-measure are included because accuracy may underweight under-represented classes.
5.2 Imbalanced Classification Performance
GraphSMOTE consistently improves imbalanced node classification over the Origin setting and generally outperforms prior over-sampling baselines. Pre-trained variants perform more strongly, highlighting the role of the embedding space.
- Overall Performance: All four GraphSMOTE variants significantly improve imbalanced node classification over the Origin setting.The improvements are reported across the evaluated datasets and metrics.
- Overall Performance: GraphSMOTE outperforms almost all baselines across datasets and evaluation metrics.The reported comparisons support the effectiveness of the proposed framework against the evaluated alternatives.
- Baseline Comparisons: GraphSMOTE_T improves AUC-ROC over Over-sampling by 0.011, 0.003, and 0.021.The passage reports these three improvements for the evaluated settings.
- Baseline Comparisons: GraphSMOTE_T improves AUC-ROC over Embed-SMOTE by 0.016, 0.014, and 0.016.These values are reported as the corresponding comparison with Embed-SMOTE.
- Variant Analysis: Pre-trained GraphSMOTE variants perform more strongly than non-pre-trained variants.The authors connect this result to the importance of an embedding space that encodes sample similarities well.
5.3 Influence of Over-sampling Scale
On Cora with imbalance ratio 0.5, increasing the over-sampling scale generally helps below 0.8, while larger scales provide little benefit or can slightly reduce performance. Balancing class sizes is generally a good choice.
- Performance Trend: When over-sampling scale is below 0.8, generating more minority samples improves classifier performance.The synthetic nodes both balance the dataset and introduce additional supervision for training the GNN classifier.
- Performance Trend: Increasing over-sampling from 1.0 to 1.2 leaves performance similar or slightly degrades it.The authors attribute this to redundant or similar synthetic nodes that provide limited additional learning signal.
- Configuration Guidance: Setting the over-sampling scale to balance class sizes is generally a good choice.This recommendation is reported as consistent with existing synthetic minority over-sampling work.
5.4 Influence of Imbalance Ratio
On Cora, GraphSMOTE generalizes across the tested imbalance ratios and performs best across settings. Its advantage is larger under more extreme imbalance, while pre-training becomes especially important there.
- Robustness Across Imbalance Ratios: GraphSMOTE achieves the best performance across all tested imbalance-ratio settings.The experiments vary imbalance ratio over 0.1, 0.2, 0.4, and 0.6 with over-sampling scale fixed at 1.0.
- Effect of Imbalance Severity: GraphSMOTE's improvement is more significant when the imbalance is more extreme.For imbalance ratio 0.1, GraphSMOTE_preO exceeds Re-weight by 0.0326, while the gap is 0.0060 at ratio 0.6.
- Effect of Pre-training: Pre-training matters more at extreme imbalance ratios.At ratio 0.1, the reported gap is 0.0268; at ratio 0.6, it decreases to 0.0055.
5.5 Influence of Base Model
GraphSMOTE generalizes effectively when GCN replaces GraphSage as the base model, with all four variants achieving the best performance. Pre-training appears less necessary for GCN than for GraphSage.
- GraphSMOTE adapts well to GCN-based models across the evaluated variants.
- Pre-training is less necessary with GCN than with GraphSage.The paper attributes this difference to GCN having weaker representation ability and being easier to train than GraphSage.
5.6 Parameter Sensitivity Analysis
GraphSMOTE’s performance varies non-monotonically with λ: it improves initially, then declines, with smaller values generally performing better. Pre-training makes performance more stable across λ.
- Smaller λ values between 1e−6 and 4e−6 generally work better.
- Performance drops significantly when λ is too large.
- Pre-training makes GraphSMOTE more stable with respect to λ.
6 CONCLUSION AND FUTURE WORK
The paper addresses imbalanced node classification with GraphSMOTE, which combines embedding-space oversampling, edge generation, and a GNN classifier. Experiments show effectiveness against baselines, while future work targets broader tasks and domains.
- Conclusion: GraphSMOTE extends synthetic oversampling from i.i.d. data to imbalanced node classification on graphs.
- Conclusion: GraphSMOTE constructs an intermediate embedding space, then trains an edge generator and GNN-based node classifier on top of it.
- Conclusion: Experiments on one artificial and two real-world datasets show GraphSMOTE outperforming all other baselines with a large margin.
- Future Work: Future work extends GraphSMOTE to other imbalanced graph-learning tasks and application domains beyond citation and social-media networks.