Enhancing Heterophilic Graph Neural Network Performance Through Label Propagation in K-Nearest Neighbor Graphs

How can we exploit Label Propagation (LP) to improve the performance of GNN models on heterophilic graphs? Graph Neural Network (GNN) models have received a lot of attention as a powerful deep learning technology that uses graph structure and features, and has achieved an archived state-of-the-art performance for graph-related tasks. LP has been applied in various studies to improve performance of GNN models. However, LP does not perform well on heterophilic graphs, where nodes of different types are linked with each other, since LP assumes that the graphs inherently exhibits homophily, where similar nodes tend to be linked. Such heterophilic graphs are increasing common nowadays. In this paper, we propose LPkG (Label Propagation on k-Nearest Neighbor Graphs of Graph Autoencoder), a simple but effective method to engage LP to improve the performance of GNN models even on heterophilic graphs. LPkG constructs a supplementary homophilic graph, peforms LP on this graph, and uses the results together with the results of GNN models. The supplementary graph is a k-Nearest Neighbor (k-NN) graph genereated from a latent space computed by Graph Autoencoder (GAE). Experimental results demonstrate that LPkG consistently achieves performance improvement on various heterophilic graph datasets: 2.75% on the Wisconsin dataset, 2.23% on the Texas dataset, and 2.55% on the Cornell dataset.