Adapting to Heterophilic Graph Data with Structure-Guided Neighbor Discovery

• URL: http://arxiv.org/abs/2506.08871v1
• Date: Tue, 10 Jun 2025 15:03:23 GMT
• Title: Adapting to Heterophilic Graph Data with Structure-Guided Neighbor Discovery
• Authors: Victor M. Tenorio, Madeline Navarro, Samuel Rey, Santiago Segarra, Antonio G. Marques,
• Abstract summary: Graph Neural Networks (GNNs) often struggle with heterophilic data, where connected nodes may have dissimilar labels.<n>We propose creating alternative graph structures by linking nodes with similar structural attributes.<n>We introduce Structure-Guided GNN (SG-GNN), an architecture that processes the original graph alongside the newly created structural graphs.
• Score: 31.368672838207022
• License: http://creativecommons.org/licenses/by-sa/4.0/
• 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.

Related papers

• GLANCE: Graph Logic Attention Network with Cluster Enhancement for Heterophilous Graph Representation Learning [54.60090631330295]
  Graph Neural Networks (GNNs) have demonstrated significant success in learning from graph-structured data but often struggle on heterophilous graphs.<n>We propose GLANCE, a novel framework that integrates logic-guided reasoning, dynamic graph refinement, and adaptive clustering to enhance graph representation learning.
  arXiv  Detail & Related papers  (2025-07-24T15:45:26Z)
• Directed Homophily-Aware Graph Neural Network [7.539052660225002]
  We propose Directed Homophily-aware Graph Neural Network (DHGNN), a novel framework that incorporates homophily-aware and direction-sensitive components.<n>DHGNN employs a resettable gating mechanism to adaptively modulate message contributions based on homophily levels and informativeness.<n>Our analysis shows that the gating mechanism captures directional homophily gaps and fluctuating homophily across layers, providing deeper insights into message-passing behavior on complex graph structures.
  arXiv  Detail & Related papers  (2025-05-28T13:41:04Z)
• It Takes a Graph to Know a Graph: Rewiring for Homophily with a Reference Graph [19.222317334613162]
  Graph Neural Networks (GNNs) excel at analyzing graph-structured data but struggle on heterophilic graphs, where connected nodes often belong to different classes.<n>We provide theoretical foundations linking edge homophily, GNN embedding smoothness, and node classification performance.<n>We introduce a rewiring framework that increases graph homophily using a reference graph, with theoretical guarantees on the homophily of the rewired graph.
  arXiv  Detail & Related papers  (2025-05-18T13:28:56Z)
• Structure-Guided Input Graph for GNNs facing Heterophily [31.368672838207022]
  We create a new graph in which nodes are connected if they share structural characteristics, meaning a higher chance of sharing their labels.<n>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.
  arXiv  Detail & Related papers  (2024-12-02T17:52:33Z)
• Learn from Heterophily: Heterophilous Information-enhanced Graph Neural Network [4.078409998614025]
  Heterophily, nodes with different labels tend to be connected based on semantic meanings, Graph Neural Networks (GNNs) often exhibit suboptimal performance. We propose and demonstrate that the valuable semantic information inherent in heterophily can be utilized effectively in graph learning. We propose HiGNN, an innovative approach that constructs an additional new graph structure, that integrates heterophilous information by leveraging node distribution.
  arXiv  Detail & Related papers  (2024-03-26T03:29:42Z)
• DGNN: Decoupled Graph Neural Networks with Structural Consistency between Attribute and Graph Embedding Representations [62.04558318166396]
  Graph neural networks (GNNs) demonstrate a robust capability for representation learning on graphs with complex structures. A novel GNNs framework, dubbed Decoupled Graph Neural Networks (DGNN), is introduced to obtain a more comprehensive embedding representation of nodes. Experimental results conducted on several graph benchmark datasets verify DGNN's superiority in node classification task.
  arXiv  Detail & Related papers  (2024-01-28T06:43:13Z)
• Exploiting Neighbor Effect: Conv-Agnostic GNNs Framework for Graphs with Heterophily [58.76759997223951]
  We propose a new metric based on von Neumann entropy to re-examine the heterophily problem of GNNs. We also propose a Conv-Agnostic GNN framework (CAGNNs) to enhance the performance of most GNNs on heterophily datasets.
  arXiv  Detail & Related papers  (2022-03-19T14:26:43Z)
• Graph Neural Networks for Graphs with Heterophily: A Survey [98.45621222357397]
  We provide a comprehensive review of graph neural networks (GNNs) for heterophilic graphs. Specifically, we propose a systematic taxonomy that essentially governs existing heterophilic GNN models. We discuss the correlation between graph heterophily and various graph research domains, aiming to facilitate the development of more effective GNNs.
  arXiv  Detail & Related papers  (2022-02-14T23:07:47Z)
• Is Homophily a Necessity for Graph Neural Networks? [50.959340355849896]
  Graph neural networks (GNNs) have shown great prowess in learning representations suitable for numerous graph-based machine learning tasks. GNNs are widely believed to work well due to the homophily assumption ("like attracts like"), and fail to generalize to heterophilous graphs where dissimilar nodes connect. Recent works design new architectures to overcome such heterophily-related limitations, citing poor baseline performance and new architecture improvements on a few heterophilous graph benchmark datasets as evidence for this notion. In our experiments, we empirically find that standard graph convolutional networks (GCNs) can actually achieve better performance than
  arXiv  Detail & Related papers  (2021-06-11T02:44:00Z)
• Graph Attention Networks with Positional Embeddings [7.552100672006174]
  Graph Neural Networks (GNNs) are deep learning methods which provide the current state of the art performance in node classification tasks. We propose a framework, termed Graph Attentional Networks with Positional Embeddings (GAT-POS), to enhance GATs with positional embeddings. We show that GAT-POS reaches remarkable improvement compared to strong GNN baselines and recent structural embedding enhanced GNNs on non-homophilic graphs.
  arXiv  Detail & Related papers  (2021-05-09T22:13:46Z)
• Node Similarity Preserving Graph Convolutional Networks [51.520749924844054]
  Graph Neural Networks (GNNs) explore the graph structure and node features by aggregating and transforming information within node neighborhoods. We propose SimP-GCN that can effectively and efficiently preserve node similarity while exploiting graph structure. We validate the effectiveness of SimP-GCN on seven benchmark datasets including three assortative and four disassorative graphs.
  arXiv  Detail & Related papers  (2020-11-19T04:18:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.