Adapting to Heterophilic Graph Data with Structure-Guided Neighbor Discovery
Victor M. Tenorio, Madeline Navarro, Samuel Rey, Santiago Segarra, and Antonio G. Marques · 2025
Read Adapting to Heterophilic Graph Data with Structure-Guided Neighbor Discovery by Victor M. Tenorio, Madeline Navarro, Samuel Rey, Santiago Segarra, and Antonio G. Marques (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-08871.txt.
Introduction
Victor Tenorio and co-authors rebuild the graph so that graph neural networks stop tripping over unlike neighbors, in this 2025 paper. Most graph learning assumes connected nodes resemble each other. Heterophilic data breaks that: linked nodes often differ. Standard message passing then averages in exactly the wrong signals. The authors instead link nodes that share structural roles, near or far.
Theory shows performance rises as wrong-class edges fall, and juggling several graph views raises the odds of finding a good one. The method discovers such alternative structures guided by node roles. Rather than forcing one given graph to behave, the work treats the graph itself as a design choice, a shift with uses far beyond the benchmarks shown.
Catalog record
| CREATOR | Victor M. Tenorio, Madeline Navarro, Samuel Rey, Santiago Segarra, and Antonio G. Marques |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 87 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-08871
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Adapting to Heterophilic Graph Data with Structure-Guided Neighbor Discovery Victor M. Tenorio, Madeline Navarro, Samuel Rey, Santiago Segarra, and Antonio G. Marques Abstract 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. To 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. I Introduction Graph 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 ] . Similarly, convolutional neural networks [ 3 ] can be viewed as a special case of GNNs operating on grid-like graphs, where the inherent smoothness of natural images (i.e., adjacent pixels often having similar values) aligns well with the local filtering operations of GNNs [ 2 , 4 ] . However, it is increasingly recognized that while the observed graph topology may contain valuable information, its edges may not directly indicate node similarity [ 5 , 6 ] . In such settings, directly employing the observed graph as input to a GNN can be suboptimal and may even hinder performance. A prominent example of this is heterophily, where connected nodes may be dissimilar or similar nodes may be distant [ 5 , 7 ] . Traditional GNNs typically rely on local, low-pass filters, hence struggling with such data [ 8 ] . To address this, several alternative methods have been proposed to incorporate non-local information. Some propose new architectures that are well suited for heterophilic data [ 9 , 10 , 11 , 12 ] , although these models may decrease interpretability due to their added complexity, and their performance may depend on the data being heterophilic, which may not be known beforehand [ 13 , 14 , 15 ] . Alternatively, GNNs that are not constrained to learn low-pass representations can adapt to both homophilic and heterophilic data. However, these models may resort to high powers of the adjacency matrix (leading to potential numerical instability) and require more parameters to allow for the necessary flexibility [ 16 , 17 ] , so while they are demonstrably effective at learning from heterophilic data, they may require a more careful optimization and be outperformed by simpler architectures on homophilic datasets [ 18 ] . This problem motivates neighbor discovery for node-level predictions [ 19 , 20 ] . Instead of altering GNN architectures, we may instead consider creating graphs more suited to the problem at hand. An alternative graph may have a more explicit relationship with node labels, allowing us to either leverage the inherent low-pass filtering of GNNs if node labels are homophilic on the new structure [ 21 ] or reduce complexity for GNNs designed to adapt to heterophilic data [ 16 ] . Deriving a new graph may involve using entirely new information or incorporating the original structure without directly using its potentially misleading edges. While heuristically altering the original graph can be effective, systematically exploiting known structural relationships offers a robust and convenient way to mitigate data dependencies and promote desired behaviors, independent of label noise. To this end, we propose a structure-based neighbor discovery approach to design alternative graph structures on which node labels exhibit greater homophily. Our methodology is inspired by the empirical observation that, in real-world graph data, nodes with similar structural attributes often share analogous labels. Thus, for a given node-level task, we construct new graphs based on sets of structural attributes computed for each node from the original graph. While our framework is flexible to various structural attributes, we exemplify its application using two primary categories: role-based attributes, which encode local connectivity patterns of nodes [ 22 , 23 ] , and global attributes, which relate a node to the entire graph structure [ 24 ] . Recognizing that the optimal graph choice is often unknown a priori and that both the original and newly derived graphs can be informative, we further introduce the Structure-Guided GNN (SG-GNN) . This architecture processes multiple graphs, including the original and the new structurally informed ones, and adaptively learns to emphasize the most relevant graphs for the task. This adaptive mechanism also enhances interpretability by revealing which graph structures contribute most to performance. In particular, we make the following contributions: • We introduce a structure-based neighbor discovery approach to construct new graphs from node-wise structural attributes of the original graph. This method is motivated by our empirical analysis of real-world graph data, which reveals that nodes possessing similar structural features often share the same labels. • We theoretically prove that GNN-based node classification can be improved by utilizing a graph with fewer edges connecting nodes of different classes. We further show that incorporating multiple graph views increases the likelihood of identifying such an improved graph. • Motivated by our theoretical findings, we propose SG-GNN. This model integrates the original graph with a set of structure-based graphs within a GNN layer, employing adaptively learned weights to aggregate their contributions and determine the most relevant graph structures. I-A Related Works The challenge of applying GNNs to heterophilic data has spurred significant research, primarily along two main avenues: designing GNN architectures suitable for non-homophilic data and modifying the input graph structure. GNN Architectures for Heterophily. Many efforts have focused on developing novel GNN architectures tailored for heterophily. Some propose architectures that specifically incorporate higher-order neighborhoods or signed messages, which may not generalize well when data is not explicitly either homophilic or heterophilic [ 15 , 14 , 13 ] . Other approaches aim for broader applicability by allowing nodes to adaptively incorporate information from neighbors near, far, and in between [ 5 , 9 , 10 , 12 , 11 , 18 , 16 , 17 ] . While powerful, these general-purpose models can become overly complex, increasing the risk of overfitting and often suffering from a lack of interpretability regarding how they adapt to different homophily levels. A subset of these methods implicitly or explicitly exploit structural information. For instance, some models incorporate centrality scores like PageRank into their aggregation schemes or attention mechanisms [ 15 ] . However, these often embed such structural cues within complex, end-to-end learned models, where the