Adapting to Heterophilic Graph Data with Structure-Guided Neighbor Discovery

--Graph Neural Networks (GNNs) often struggle with heterophilic data, where connected nodes may have dissimilar labels, as they typically assume homophily and rely on local message passing. T o address this, we propose creating alternative graph structures by linking nodes with similar structural attributes (e.g., role-based or global), thereby fostering higher label homophily on these new graphs. We theoretically prove that GNN performance can be improved by utilizing graphs with fewer false positive edges (connections between nodes of different classes) and that considering multiple graph views increases the likelihood of finding such beneficial structures. Building on these insights, we introduce Structure-Guided GNN (SG-GNN), an architecture that processes the original graph alongside the newly created structural graphs, adaptively learning to weigh their contributions. Extensive experiments on various benchmark datasets, particularly those with heterophilic characteristics, demonstrate that our SG-GNN achieves state-of-the-art or highly competitive performance, highlighting the efficacy of exploiting structural information to guide GNNs. RAPH neural networks (GNNs) have demonstrated remarkable performance in processing graph-structured data by leveraging local neighborhood information [1], [2]. For node classification or regression, the graph structure is traditionally assumed to indicate which nodes should share similar representations or be treated similarly by a GNN. This holds true in many real-world scenarios; for example, temperature readings on a graph discretizing a geographical region often exhibit smoothness, where nearby sensors record similar temperatures [2]. M. Tenorio, S. Rey, and A. G. Marques are with the Department of Signal Theory and Communications, King Juan Carlos University, Madrid, Spain.