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

Graph neural networks (GNNs) witness impressive performances on homophilic graphs characterized by a higher number of edges connecting nodes of similar class labels. A decline in the performance of GNNs can be experienced when applied to heterophilic graphs where most of the edges connect nodes with different class labels. This study presents a novel and versatile preprocessing framework comprising three fundamental stages. This framework can be seamlessly integrated with various GNN architectures to address heterophily within graphs effectively. In the initial stage, we predict class probabilities for nodes through a dense network. It is widely acknowledged that conventional feature-based similarity measures, such as cosine similarity, might not always accurately capture the correspondence between node pairs. Moving to the second stage, we introduce a reweighting strategy guided by class embeddings generated from autoencoders to counter this limitation. In the final stage, we utilize the reweighted similarity coefficients in a two-stage graph rewiring process. This process involves node deletion and subsequent insertion to generate a more homophily-oriented neighborhood. We reuse class embeddings by fusing them with the original node features to enrich the node features with class-level information. The updated node features and the rewired graph structure are ultimately fed into the GNN model. This facilitates effective message passing (MP) across neighborhoods. We extensively evaluate our approach on various standard graph datasets encompassing homophilic and heterophilic characteristics. Across these datasets, our framework consistently improves the performance of the established baseline methods.