Abstract
The problem of class imbalance refers to an uneven distribution of quantity among classes in a dataset, where some classes are significantly underrepresented compared to others. Class imbalance is also prevalent in graph-structured data. Graph neural networks (GNNs) are typically based on the assumption of class balance, often overlooking the issue of class imbalance. In our investigation, we identified a problem, which we term the Randomness Anomalous Connectivity Problem (RACP), where certain off-the-shelf models are affected by random seeds, leading to a significant performance degradation. To eliminate the influence of random factors in algorithms, we proposed PNS (Pure Node Sampling) to address the RACP in the node synthesis stage. Unlike existing approaches that design specialized algorithms to handle either quantity imbalance or topological imbalance, PNS is a novel plug-and-play module that operates directly during node synthesis to mitigate RACP. Moreover, PNS also alleviates performance degradation caused by abnormal distribution of node neighbors. We conduct a series of experiments to identify what factors are influenced by random seeds. Experimental results demonstrate the effectiveness and stability of our method, which not only eliminates the effect of unfavorable random seeds but also outperforms the baseline across various benchmark datasets with different GNN backbones.
Introduction: The Randomness Anomalous Connectivity Problem (RACP)
In real-world graph data, such as social networks or financial transaction graphs, classes are rarely balanced. While researchers often use node synthesis (creating synthetic minority nodes) to address this, we have identified a critical vulnerability: the Randomness Anomalous Connectivity Problem (RACP).
Standard GNNs trained on imbalanced data exhibit high sensitivity to random seeds. If a random seed selects a "confusing" node—a minority node primarily surrounded by majority-class neighbors—as a template for synthesis, the resulting noise propagates through the network's message-passing layers. This leads to substantial performance drops purely due to stochastic factors.
Methodology: Pure Node Selection (PNS)
To mitigate RACP, we propose Pure Node Selection (PNS), a plug-and-play filtering mechanism that ensures synthetic data enhances rather than degrades model performance. PNS operates in three primary stages:
- Node Purity Recognition: For every node in the training set, PNS calculates its "purity"—the ratio of neighbors that share its label.
- Filtering Confusion Nodes: Nodes with purity below a defined threshold (the confusion rate $r$) are flagged as "confusion nodes."
- Pure Synthesis: During data augmentation (e.g., using GraphENS), the model is restricted to sampling only from "pure" nodes, avoiding the propagation of topological noise.
By narrowing the sampling boundary to nodes that truly represent their class's topological neighborhood, PNS decouples model performance from the randomness of the initial seed.
Experimental Evaluation
We evaluated PNS across several standard and large-scale benchmarks, including citation networks (Cora-LT, CiteSeer-LT, PubMed-LT) and Amazon purchase networks (Photo-ST, Computer-ST).
Key Results
- Accuracy and Stability: PNS consistently outperformed baselines across GCN, GAT, and GraphSAGE backbones. For instance, on PubMed-LT with a GCN backbone, PNS + GraphENS achieved 79.94% accuracy, compared to 76.90% for vanilla GraphENS.
- Large-Scale Performance: On the OGB-Arxiv dataset (imbalance ratio of 942), PNS achieved a test accuracy of 72.31%, outperforming complex reweighting and upsampling baselines.
- Variance Reduction: The most significant qualitative result was the elimination of performance dips caused by random seeds, providing stable training curves and reproducible results.
Conclusion
PNS demonstrates that topology is often more critical than quantity in imbalanced graph learning. Simply adding minority nodes is insufficient if they are placed in "noisy" parts of the graph. By using purity as a proxy for quality, PNS provides a computationally efficient way to stabilize GNNs. Future work will focus on automating the selection of the confusion rate $r$ to further simplify deployment.
Summary updated