GraphSR: A Data Augmentation Algorithm for Imbalanced Node Classification

Mengting Zhou, Zhiguo GongAAAI 2023 · DOI

GraphSR, presented at AAAI-23, is a novel data augmentation algorithm designed to address the class imbalance problem in graph neural networks (GNNs). By mining unlabeled nodes instead of generating synthetic ones, GraphSR provides a more robust and natural way to balance training sets for node classification tasks.

The Problem: Bias in Imbalanced Graphs

In many real-world graph datasets—such as social networks containing rare fraudulent accounts or medical databases with infrequent disease cases—the distribution of labels is heavily skewed. Standard GNNs are naturally biased toward majority classes because they have more labeled examples to learn from, leading to poor performance on minority classes.

Existing solutions generally fall into two categories:

  1. Re-sampling/Re-weighting: These methods repeat minority samples or increase their loss function weight, which often leads to severe overfitting.
  2. Synthetic Augmentation: Methods like GraphSMOTE create "fake" nodes by interpolating between existing minority nodes. However, these synthetic nodes often fail to capture the true underlying distribution of the data, leading to poor generalization.
Comparison of GraphSR with synthetic augmentation methods like GraphSMOTE and GraphENS.

GraphSR asks a fundamental question: Why invent fake nodes when the graph already contains a massive amount of unlabeled real nodes? The challenge lies in identifying which unlabeled nodes belong to the minority classes and are reliable enough to assist the model.

The GraphSR Framework

GraphSR utilizes a self-training framework that operates in two main stages to "recruit" unlabeled nodes into the minority training sets.

Overview of the GraphSR framework, illustrating (a) Similarity-based Selection and (b) RL-based Selection.

1. Similarity-Based Selection

First, a baseline GNN is trained on the imbalanced data to generate embeddings and pseudo-labels for all unlabeled nodes. To filter out noise, the algorithm calculates the "center" of each minority class in the embedding space. It then identifies a candidate set of unlabeled nodes that are both predicted to be in the minority class and physically close to the class center in the embedding space.

2. RL-Based Selection

To account for potential errors in pseudo-labels, GraphSR employs Reinforcement Learning (RL) to refine the selection:

  • The Agent: A multi-layer perceptron (MLP) selector that decides whether to "Keep" or "Discard" a candidate node.
  • The Environment: The GNN training process.
  • The Reward: A positive reward is given if adding a node improves the GNN’s performance on a small, balanced validation set.

This RL step allows the model to adaptively determine the sampling scale, learning exactly how many nodes are needed to achieve the best balance without requiring a human-defined fixed ratio.

Key Insights and Results

Real Data vs. Synthetic Data

The core innovation of GraphSR is that unlabeled nodes provide more natural diversity than synthetic nodes. While synthetic nodes are restricted to the space between existing points, unlabeled nodes can extend class boundaries into authentic, previously unseen parts of the graph.

Experimental Performance

The authors evaluated GraphSR on standard citation benchmarks (Cora, CiteSeer, PubMed) with varying imbalance ratios ($\rho$).

  • Accuracy Gains: On the Cora dataset ($\rho = 0.3$), GraphSR achieved 78.78% accuracy, significantly outperforming Vanilla GNNs (75.67%) and GraphENS (76.84%).
  • Robustness: The performance gap was most pronounced under extreme imbalance ($\rho = 0.1$), where GraphSR’s ability to find reliable real nodes provided a critical boost that synthetic methods could not match.
  • Adaptive Scaling: Visualization showed that the RL agent successfully chose different amounts of supplemental nodes for different classes, proving that a "one-size-fits-all" sampling ratio is suboptimal.

Conclusion

GraphSR demonstrates that leveraging the inherent information in unlabeled nodes is a powerful alternative to synthetic data generation for imbalanced graph learning. By combining similarity-based filtering with an adaptive RL selector, it effectively mitigates the "pseudo-label trap" and improves the generalization of GNNs in data-starved scenarios.

Summary updated

BibTeX
@inproceedings{zhou2023graphsr,
  author = {Mengting Zhou and Zhiguo Gong},
  title = {{GraphSR: A Data Augmentation Algorithm for Imbalanced Node Classification}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i4.25622},
}
Figure