TL;DR
Graph Neural Networks (GNNs) struggle with imbalanced datasets, leading to poor performance on minority classes. This paper introduces the Label Difference Index (LDI), a novel node-level metric to quantify misclassification risk due to imbalance. Based on LDI, they propose new loss functions and methods that significantly improve GNN performance on imbalanced graph data.
What Problem Does This Paper Address?
Graph Neural Networks (GNNs) are powerful tools for analyzing graph-structured data, leveraging the connections between nodes to learn representations. However, real-world graph datasets often suffer from class imbalance, meaning some categories have far fewer samples than others. This imbalance poses a significant challenge for GNNs, as they tend to optimize for the majority classes, leading to misclassification of minority class nodes and a degradation of overall performance. Unlike traditional machine learning, GNNs face an additional challenge: information exchange between neighboring nodes can exacerbate the problem, as minority nodes are more likely to be connected to majority nodes, further confusing the model. Existing methods for handling imbalance in non-graph data don't fully address these unique GNN challenges.
Methods
The core contribution of this paper is the Label Difference Index (LDI), a new node-level metric designed to quantify a node's susceptibility to misclassification due to class imbalance. LDI measures the difference between a node's own category distribution and the category distribution of its immediate neighbors. A higher LDI suggests a node is more likely to be misclassified.
Based on LDI, the authors propose:
- Improved Focal Loss (iFL): A modification of the standard focal loss, adapted for GNNs to better handle class imbalance by automatically adjusting weights based on category-level performance.
- Graph Re-sampling (GRS) and Graph Re-weighting (GRW): These methods adjust the training process by either oversampling minority classes or assigning higher weights to them. They introduce three weighting strategies: label-based, LDI-based, and a combination of both.
- Graph Metric Learning (GML): This approach aims to learn a feature space where similar nodes are closer and dissimilar nodes are further apart, using a triplet loss. However, the authors note this method was less effective for GNNs due to the inherent edge connections.
- Graph Bilateral-branch Network (GBBN): This architecture features two branches: a conventional GNN branch for standard learning and a re-balancing branch that uses LDI to prioritize minority classes and nodes with higher misclassification risk. It employs a cumulative learning strategy to balance the focus between the two branches during training.
Datasets
The authors evaluated their methods on five benchmark graph datasets:
- Cora
- Citeseer
- Pubmed
- CoauthorCS (CS)
- Flickr
These datasets are noted to exhibit imbalanced or highly-skewed category distributions.
Key Insights and Ideas
- LDI as a Misclassification Predictor: The LDI is a powerful indicator of a node's likelihood of being misclassified. Nodes with higher LDIs consistently show lower accuracies, and this trend holds across different GNN architectures and settings.
- Heterophily's Role: The LDI is influenced by heterophily (nodes connecting to different classes). Nodes in minority classes are more prone to being surrounded by heterophily nodes, thus increasing their LDI and misclassification risk.
- GNNs are Particularly Vulnerable: The paper argues that imbalance has a more severe impact on GNNs than on non-graph data models due to the direct information exchange between neighboring nodes, which can propagate misclassifications.
- LDI-based Weighting is Effective: The combination of label and LDI for weighting (W3) in GRS and GRW consistently yielded better results, highlighting the value of node-level imbalance information.
- Metric Learning Challenges: Standard metric learning approaches, while effective for image data, struggle with graph data due to the inherent edge connections that can interfere with learning distinct class separations.
Key Results
- Improved Performance: The proposed methods (GRS, GRW, and GBBN) generally outperformed the baseline DR-GCN and original GNN models (GCN, GAT, SGC) across various datasets and settings.
- GBBN Leads: The GBBN, particularly when combined with iFL and LDI-based weighting, achieved the best performance in many inductive and transductive settings.
- LDI's Practicality: The LDI can be applied to existing GNNs to improve their performance, demonstrating its versatility.
- Transductive vs. Inductive: The paper shows that LDI-based weighting strategies are particularly beneficial in the inductive setting, where the model needs to generalize to unseen nodes.
Limitations and Future Work
- Neighborhood Size: The current LDI calculation considers only the 1-neighborhood. The authors suggest exploring larger neighborhood sizes for potentially richer information.
- Metric Learning for GNNs: The paper identifies metric learning as a promising area for future research, specifically for developing methods tailored to the unique characteristics of graph data.
- Scalability: While not explicitly detailed as a limitation, the use of graph sampling strategies for larger datasets (like Reddit, Amazon-Computer, Amazon-Photo) is mentioned as future work, implying current methods might face scalability challenges on massive graphs.
Summary updated