On Performance Discrepancies Across Local Homophily Levels in Graph Neural Networks

• URL: http://arxiv.org/abs/2306.05557v4
• Date: Mon, 20 Nov 2023 21:46:58 GMT
• Title: On Performance Discrepancies Across Local Homophily Levels in Graph Neural Networks
• Authors: Donald Loveland, Jiong Zhu, Mark Heimann, Benjamin Fish, Michael T. Schaub, Danai Koutra
• Abstract summary: Graph Neural Network (GNN) research has highlighted a relationship between high homophily and strong predictive performance in node classification. We study the performance of GNNs when the local homophily level of a node deviates from the global homophily level. We show that GNNs designed for globally heterophilous graphs can alleviate performance discrepancy by improving performance across local homophily levels.
• Score: 17.9878305101678
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph Neural Network (GNN) research has highlighted a relationship between high homophily (i.e., the tendency of nodes of the same class to connect) and strong predictive performance in node classification. However, recent work has found the relationship to be more nuanced, demonstrating that simple GNNs can learn in certain heterophilous settings. To resolve these conflicting findings and align closer to real-world datasets, we go beyond the assumption of a global graph homophily level and study the performance of GNNs when the local homophily level of a node deviates from the global homophily level. Through theoretical and empirical analysis, we systematically demonstrate how shifts in local homophily can introduce performance degradation, leading to performance discrepancies across local homophily levels. We ground the practical implications of this work through granular analysis on five real-world datasets with varying global homophily levels, demonstrating that (a) GNNs can fail to generalize to test nodes that deviate from the global homophily of a graph, and (b) high local homophily does not necessarily confer high performance for a node. We further show that GNNs designed for globally heterophilous graphs can alleviate performance discrepancy by improving performance across local homophily levels, offering a new perspective on how these GNNs achieve stronger global performance.

Related papers

• FedHERO: A Federated Learning Approach for Node Classification Task on Heterophilic Graphs [55.51300642911766]
  Federated Graph Learning (FGL) empowers clients to collaboratively train Graph neural networks (GNNs) in a distributed manner. FGL methods usually require that the graph data owned by all clients is homophilic to ensure similar neighbor distribution patterns of nodes. We propose FedHERO, an FGL framework designed to harness and share insights from heterophilic graphs effectively.
  arXiv  Detail & Related papers  (2025-04-29T22:23:35Z)
• Unveiling the Impact of Local Homophily on GNN Fairness: In-Depth Analysis and New Benchmarks [12.077386474432124]
  Graph Neural Networks (GNNs) often struggle to generalize when graphs exhibit both homophily (same-class connections) and heterophily (different-class connections) This issue poses a risk in user-centric applications where underrepresented homophily levels are present. We move beyond global homophily and explore how local homophily levels can lead to unfair predictions.
  arXiv  Detail & Related papers  (2024-10-05T21:21:40Z)
• 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)
• Breaking the Entanglement of Homophily and Heterophily in Semi-supervised Node Classification [25.831508778029097]
  We introduce AMUD, which quantifies the relationship between node profiles and topology from a statistical perspective. We also propose ADPA as a new directed graph learning paradigm for AMUD.
  arXiv  Detail & Related papers  (2023-12-07T07:54:11Z)
• Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All? [61.35457647107439]
  Most real-world homophilic and heterophilic graphs are comprised of a mixture of nodes in both homophilic and heterophilic structural patterns. We provide evidence that Graph Neural Networks(GNNs) on node classification typically perform admirably on homophilic nodes. We then propose a rigorous, non-i.i.d PAC-Bayesian generalization bound for GNNs, revealing reasons for the performance disparity.
  arXiv  Detail & Related papers  (2023-06-02T07:46:20Z)
• LSGNN: Towards General Graph Neural Network in Node Classification by Local Similarity [59.41119013018377]
  We propose to use the local similarity (LocalSim) to learn node-level weighted fusion, which can also serve as a plug-and-play module. For better fusion, we propose a novel and efficient Initial Residual Difference Connection (IRDC) to extract more informative multi-hop information. Our proposed method, namely Local Similarity Graph Neural Network (LSGNN), can offer comparable or superior state-of-the-art performance on both homophilic and heterophilic graphs.
  arXiv  Detail & Related papers  (2023-05-07T09:06:11Z)
• When Do Graph Neural Networks Help with Node Classification? Investigating the Impact of Homophily Principle on Node Distinguishability [92.8279562472538]
  Homophily principle has been believed to be the main reason for the performance superiority of Graph Networks (GNNs) over Neural Networks on node classification tasks. Recent research suggests that, even in the absence of homophily, the advantage of GNNs still exists as long as nodes from the same class share similar neighborhood patterns.
  arXiv  Detail & Related papers  (2023-04-25T09:40:47Z)
• 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 Neural Networks with Heterophily [40.23690407583509]
  We propose a novel framework called CPGNN that generalizes GNNs for graphs with either homophily or heterophily. We show that replacing the compatibility matrix in our framework with the identity (which represents pure homophily) reduces to GCN.
  arXiv  Detail & Related papers  (2020-09-28T18:29:36Z)

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.