# On Performance Discrepancies Across Local Homophily Levels in Graph Neural Networks

arXiv: https://arxiv.org/abs/2306.05557 · HTML: https://mlsanity.com/paper/2306.05557/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 39 of its 56 references that are in the map.
- First posted on arXiv 8 Jun 2023.

## Builds on (most cited first, 30 of 39)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [A Survey on Bias and Fairness in Machine Learning](https://mlsanity.com/paper/1908.09635/) (2019)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [LightGCN: Simplifying and Powering Graph Convolution Network for Recommendation](https://mlsanity.com/paper/2002.02126/) (2020)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [Counterfactual Fairness](https://mlsanity.com/paper/1703.06856/) (2017)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Connecting the Dots: Multivariate Time Series Forecasting with Graph Neural Networks](https://mlsanity.com/paper/2005.11650/) (2020)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [Composition-based Multi-Relational Graph Convolutional Networks](https://mlsanity.com/paper/1911.03082/) (2019)
- [Fairness in Machine Learning: A Survey](https://mlsanity.com/paper/2010.04053/) (2020)
- [Beyond Low-frequency Information in Graph Convolutional Networks](https://mlsanity.com/paper/2101.00797/) (2021)
- [A critical look at the evaluation of GNNs under heterophily: Are we really making progress?](https://mlsanity.com/paper/2302.11640/) (2023)
- [Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Ranking](https://mlsanity.com/paper/1707.03815/) (2017)
- [Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods](https://mlsanity.com/paper/2110.14446/) (2021)
- [Graph Neural Networks with Heterophily](https://mlsanity.com/paper/2009.13566/) (2020)
- [Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks](https://mlsanity.com/paper/2102.06462/) (2021)
- [Is Homophily a Necessity for Graph Neural Networks?](https://mlsanity.com/paper/2106.06134/) (2021)
- [Towards a Unified Framework for Fair and Stable Graph Representation Learning](https://mlsanity.com/paper/2102.13186/) (2021)
- [Adaptive Graph Encoder for Attributed Graph Embedding](https://mlsanity.com/paper/2007.01594/) (2020)
- [GBK-GNN: Gated Bi-Kernel Graph Neural Networks for Modeling Both Homophily and Heterophily](https://mlsanity.com/paper/2110.15777/) (2021)
- [Is Heterophily A Real Nightmare For Graph Neural Networks To Do Node Classification?](https://mlsanity.com/paper/2109.05641/) (2021)
- [Fairness in Graph Mining: A Survey](https://mlsanity.com/paper/2204.09888/) (2022)
- [Subgroup Generalization and Fairness of Graph Neural Networks](https://mlsanity.com/paper/2106.15535/) (2021)

## Built on by (most cited first, 13 of 13)

- [Can LLMs Effectively Leverage Graph Structural Information through Prompts, and Why?](https://mlsanity.com/paper/2309.16595/) (2023)
- [Unveiling the Impact of Local Homophily on GNN Fairness: In-Depth Analysis and New Benchmarks](https://mlsanity.com/paper/2410.04287/) (2024)
- [Learning Laplacian Positional Encodings for Heterophilous Graphs](https://mlsanity.com/paper/2504.20430/) (2025)
- [Edge-Splitting MLP: Node Classification on Homophilic and Heterophilic Graphs without Message Passing](https://mlsanity.com/paper/2412.08310/) (2024)
- [Understanding GNNs and Homophily in Dynamic Node Classification](https://mlsanity.com/paper/2504.20421/) (2025)
- [A Neuro-Symbolic Approach for Probabilistic Reasoning on Graph Data](https://mlsanity.com/paper/2507.21873/) (2025)
- [Glance for Context: Learning When to Leverage LLMs for Node-Aware GNN-LLM Fusion](https://mlsanity.com/paper/2510.10849/) (2025)
- [Mixture of Scope Experts at Test: Generalizing Deeper Graph Neural Networks with Shallow Variants](https://mlsanity.com/paper/2409.06998/) (2024)
- [Gumbel-MPNN: Graph Rewiring with Gumbel-Softmax](https://mlsanity.com/paper/2508.17531/) (2025)
- [Are Heterogeneous Graph Neural Networks Truly Effective for Node Classification? A Causal Perspective](https://mlsanity.com/paper/2510.05750/) (2025)
- [Disentangling Homophily and Rarity: Explaining Failure in Graph Neural Networks](https://mlsanity.com/paper/2608.14823/) (2026)
- [Not All Nodes Are Created Equal: Homophily-Aware Stratification for Stable GNN Evaluation](https://mlsanity.com/paper/2609.19210/) (2026)
- [HoTS: Homophily-Aware Temperature Scaling for Graph Neural Network Calibration](https://mlsanity.com/paper/2609.32426/) (2026)

## Abstract (arXiv)

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.