Structure-Guided Input Graph for GNNs facing Heterophily
This addresses a domain-specific issue for researchers and practitioners working with heterophilic graph data, presenting an incremental improvement.
The paper tackles the problem of Graph Neural Networks (GNNs) performing poorly on heterophilic datasets by creating a new graph where nodes are connected based on shared structural features, leading to smoother labels and improved GNN performance.
Graph Neural Networks (GNNs) have emerged as a promising tool to handle data exhibiting an irregular structure. However, most GNN architectures perform well on homophilic datasets, where the labels of neighboring nodes are likely to be the same. In recent years, an increasing body of work has been devoted to the development of GNN architectures for heterophilic datasets, where labels do not exhibit this low-pass behavior. In this work, we create a new graph in which nodes are connected if they share structural characteristics, meaning a higher chance of sharing their labels, and then use this new graph in the GNN architecture. To do this, we compute the k-nearest neighbors graph according to distances between structural features, which are either (i) role-based, such as degree, or (ii) global, such as centrality measures. Experiments show that the labels are smoother in this newly defined graph and that the performance of GNN architectures improves when using this alternative structure.