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.

I. Introduction

How can we leverage Label Propagation (LP) to improve the performance of Graph Neural Network (GNN) models on heterophilic graphs? The myriad of information surrounding us is often represented as heterophilic graphs; a graph is considered heterophilic if different kinds of nodes are typically connected to each other by edges. Fig. 1b is an example of a heterophilic graph. For example, in an online transaction network, fraudsters may have more connections to regular customers than other fraudsters [1]; in a dating network, individuals may prefer connections with individuals of the opposite gender [2]; in a protein-protein interaction network, different types of amino acids are connected [3].