Pure node selection for imbalanced graph node classification

Fanlong Zeng, Wensheng Gan, Jiayang Wu, Philip S. Yu

TL;DR

Researchers have identified the Randomness Anomalous Connectivity Problem (RACP), where graph neural networks (GNNs) trained on imbalanced data become highly sensitive to random seeds during data augmentation. To fix this, they proposed Pure Node Sampling (PNS), a plug-and-play module that filters out "confusing" nodes to ensure synthetic data actually helps—rather than hinders—the model.

What Problem Does This Paper Address?

In the real world, graph data is rarely balanced. Think of a social network where "fraudulent" users are a tiny minority compared to "legitimate" ones. Standard GNNs struggle here because they are designed assuming classes are roughly equal.

To solve this, researchers often use node synthesis—creating "fake" minority nodes to balance the scales. However, the authors of this paper discovered a hidden trap: RACP. They found that if a random seed causes a model to pick a "confusing" node (a minority node that is mostly surrounded by majority-class neighbors) as a template for synthesis, the resulting synthetic nodes are "noisy." This noise propagates through the GNN's message-passing layers, leading to a massive drop in accuracy simply because the researcher got "unlucky" with their random seed.

Methods

The authors introduce Pure Node Sampling (PNS), a straightforward but powerful filtering mechanism designed to be used during the node synthesis stage.

  1. Node Purity Recognition: For every node in the training set, PNS calculates its "purity"—the ratio of its neighbors that share its same label.
  2. Filtering "Confusion Nodes": If a node’s purity falls below a user-defined threshold (the confusion rate $r$), it is labeled a "confusion node."
  3. Pure Synthesis: When the model needs to synthesize new minority nodes (using methods like GraphENS), it is restricted to sampling only from the "pure" nodes.

By narrowing the sampling boundary to nodes that truly represent their class's topological neighborhood, PNS decouples the model's performance from the randomness of the initial seed.

Datasets

The authors evaluated PNS across several standard and large-scale benchmarks:

  • Citation Networks: Cora-LT, CiteSeer-LT, and PubMed-LT (modified for Long-Tailed imbalance).
  • Amazon Purchase Networks: Photo-ST, Computer-ST, and Coauthor-CS (modified for Step imbalance).
  • Large-Scale Graph: The OGB-Arxiv dataset, which features a natural imbalance ratio of 942.

Key Insights and Ideas

  • The "Unlucky Seed" is Real: The paper quantifies how much a bad random seed can hurt. In some experiments, a "worse seed" dropped accuracy by nearly 5% compared to a "normal" one.
  • Topology > Quantity: Simply adding more minority nodes isn't enough. If those nodes are placed in "noisy" parts of the graph (high anomalous connectivity), they actually make the classification task harder for the GNN.
  • Purity as a Proxy for Quality: Using the label distribution of one-hop neighbors is a computationally efficient way to identify which nodes are "safe" templates for data augmentation.
  • Plug-and-Play Stability: PNS isn't a new GNN architecture; it’s a filter that can be added to existing state-of-the-art imbalance methods like GraphENS or BAT to make them more robust.

Key Results

PNS consistently outperformed baselines across GCN, GAT, and GraphSAGE backbones:

  • Accuracy Boost: On the PubMed-LT dataset using a GCN backbone, PNS + GraphENS achieved 79.94% accuracy, significantly higher than the vanilla GCN (69.48%) and the original GraphENS (76.90%).
  • Large-Scale Success: On the massive OGB-Arxiv dataset, 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 much more stable training curves and reproducible results.

Limitations and Future Work

The authors acknowledge a few key limitations:

  • Data Scarcity: If a minority class is already extremely small, filtering out "impure" nodes might leave the model with too few samples to perform effective synthesis, potentially leading to overfitting (homogenization).
  • Manual Tuning: The "confusion rate" $r$ is a hyperparameter that currently needs to be tuned for each dataset.
  • Neighborhood Complexity: Purity is currently measured as a simple 1D ratio. Future work could involve more complex, multi-dimensional measures of a node's neighborhood to better capture graph heterogeneity.

The authors suggest that future research should focus on automated confusion rate selection to make PNS even easier to deploy in production environments.

Summary updated

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. Data and code are available at https://github.com/flzeng1/PNS.
BibTeX
@article{zeng2026pure,
  author = {Fanlong Zeng and Wensheng Gan and Jiayang Wu and Philip S. Yu},
  title = {{Pure node selection for imbalanced graph node classification}},
  journal = {Neural Networks},
  year = {2026},
  doi = {10.1016/j.neunet.2025.108315},
}

Loading related content...

Figure