GraphENS: Neighbor-Aware Ego Network Synthesis for Class-Imbalanced Node Classification

Joonhyung Park, Jaeyun Song, Eunho YangICLR 2022 · OpenReview

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:

  1. 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.
  2. 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

Training/Test accuracy curves and replacing experiments demonstrating GraphENS reduces overfitting and handles unseen neighbors better than baselines.
  • 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

Abstract

In many real-world node classification scenarios, nodes are highly class-imbalanced, where graph neural networks (GNNs) can be readily biased to major class instances. Albeit existing class imbalance approaches in other domains can alleviate this issue to some extent, they do not consider the impact of message passing between nodes. In this paper, we hypothesize that overfitting to the neighbor sets of minor class due to message passing is a major challenge for class-imbalanced node classification. To tackle this issue, we propose GraphENS, a novel augmentation method that synthesizes the whole ego network for minor class (minor node and its one-hop neighbors) by combining two different ego networks based on their similarity. Additionally, we introduce a saliency-based node mixing method to exploit the abundant class-generic attributes of other nodes while blocking the injection of class-specific features. Our approach consistently outperforms the baselines over multiple node classification benchmark datasets and architectures.
BibTeX
@inproceedings{park2022graphens,
  author = {Joonhyung Park and Jaeyun Song and Eunho Yang},
  title = {{GraphENS: Neighbor-Aware Ego Network Synthesis for Class-Imbalanced Node Classification}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=718x8uUqMQx},
}
Figure