Can Graph Neural Networks Tackle Heterophily? Yes, With a Label-Guided Graph Rewiring Approach!

Area of Science:

• Artificial Intelligence
• Machine Learning
• Graph Theory

Background:

• Graph Neural Networks (GNNs) excel on homophilic graphs but struggle with heterophilic ones.
• Heterophilic graphs have edges connecting nodes of different classes, challenging standard GNN performance.
• Existing GNNs often fail to capture complex relationships in heterophilic graph data.

Purpose of the Study:

• To present a versatile preprocessing framework to enhance GNN performance on heterophilic graphs.
• To develop a method that effectively addresses the challenges posed by graph heterophily.
• To improve the accuracy and robustness of GNN models in diverse graph settings.

Main Methods:

• A three-stage preprocessing framework: class probability prediction, autoencoder-based class embedding reweighting, and a two-stage graph rewiring process (node deletion/insertion).
• Integration of class embeddings with original node features to enrich representations.
• Utilizing updated node features and the rewired graph structure for GNN message passing.

Main Results:

• Consistent performance improvements across established baseline GNN methods on standard datasets.
• Demonstrated effectiveness of the framework on both homophilic and heterophilic graph characteristics.
• Enhanced GNN accuracy through improved neighborhood information and feature representation.

Conclusions:

• The proposed framework effectively mitigates performance degradation of GNNs on heterophilic graphs.
• The method offers a versatile solution adaptable to various GNN architectures.
• This approach significantly advances the application of GNNs to real-world heterophilic graph data.