Introduction
GraphENS is a novel data augmentation framework designed to solve class imbalance in graph neural networks (GNNs). By synthesizing entire "ego networks" (a central node and its immediate neighbors) rather than just individual nodes, it prevents GNNs from overfitting to the sparse local structures of minority classes—a phenomenon the authors term "neighbor memorization."
The Challenge: Neighbor Memorization
In many real-world graphs, such as those used for fraud detection or rare disease bioinformatics, some classes have thousands of examples while others have only a handful. Standard GNNs are notoriously biased toward these majority classes.
While "imbalance-handling" techniques from the image processing world—like re-weighting loss or oversampling—exist, they often fail on graphs. This is because GNNs do not just evaluate a node's features; they aggregate information from its neighbors. The authors identify a specific hurdle: Neighbor Memorization. When a minority class has very few nodes, the GNN memorizes the specific, limited set of neighbors it has rather than learning generalizable features. This makes the model brittle and unable to accurately classify minority nodes that possess different neighborhood structures.
The GraphENS Solution
To combat this, the authors propose GraphENS (Neighbor-Aware Ego Network Synthesis), which generates new, synthetic training data for minority classes. It consists of two main components:
- Neighbor Sampling (The "Where"): Instead of merely duplicating a minority node, GraphENS synthesizes an entirely new neighborhood. It selects a "minority node" and a "target node" (which can belong to any class). It then creates a new neighborhood distribution by mixing the two. To ensure the new neighborhood is realistic, it uses the KL-divergence between the model's predictions for both nodes. If the nodes appear similar to the model, it allows more influence from the target node's neighbors.
- Saliency-based Node Mixing (The "What"): To create the features for the new synthetic central node, the authors use a "mixup" approach. To avoid accidentally injecting majority-class-specific features into a minority node, they employ gradient-based saliency. This identifies which features are most important for the target node's classification and masks them out, allowing only "class-generic" attributes to be mixed into the new minority node.
Key Insights and Results
- The "Aha!" Moment on Memorization: The authors proved via "replacing experiments" that GNNs are more sensitive to changes in neighbors than changes in node features for minority classes. This confirms that the graph structure itself is the primary source of overfitting in imbalanced settings.
- Diversity via Cross-Class Mixing: Unlike previous methods (like GraphSMOTE) that only mix nodes within the same class, GraphENS mixes minority nodes with nodes from any class. This significantly increases the diversity of the synthetic data, provided the saliency masking prevents "label-leaking" features from crossing over.
- State-of-the-Art Performance: GraphENS consistently outperformed baselines like SMOTE, Re-weighting, and GraphSMOTE across multiple datasets (including Cora, CiteSeer, PubMed, AmazonPhoto, and AmazonComputers) and architectures (GCN, GAT, GraphSAGE). In the highly imbalanced "Cora-LT" dataset, GraphENS achieved a balanced accuracy of 72.94%, compared to the Vanilla GCN's 62.72%.
Limitations and Future Work
While highly effective, GraphENS introduces some computational overhead. Synthesizing ego networks for every minority instance adds complexity compared to simple loss-weighting, though the authors note saliency can be calculated using gradients from the previous training iteration to save time. Additionally, the method introduces new hyperparameters (like the masking ratio and temperature) that require tuning. Finally, GraphENS currently focuses on synthesizing one-hop neighborhoods; extending this to multi-hop synthesis for deeper GNNs remains an open challenge for future research.
Summary updated