# Understanding Heterophily for Graph Neural Networks

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 44 references that are in the map.
- First posted on arXiv 17 Jan 2024.

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

- [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)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (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)
- [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)
- [Finding Global Homophily in Graph Neural Networks When Meeting Heterophily](https://mlsanity.com/paper/2205.07308/) (2022)
- [Revisiting Heterophily For Graph Neural Networks](https://mlsanity.com/paper/2210.07606/) (2022)
- [Contextual Stochastic Block Models](https://mlsanity.com/paper/1807.09596/) (2018)
- [Breaking the Limit of Graph Neural Networks by Improving the Assortativity of Graphs with Local Mixing Patterns](https://mlsanity.com/paper/2106.06586/) (2021)
- [Non-Local Graph Neural Networks](https://mlsanity.com/paper/2005.14612/) (2020)
- [New Benchmarks for Learning on Non-Homophilous Graphs](https://mlsanity.com/paper/2104.01404/) (2021)
- [Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization](https://mlsanity.com/paper/2102.06966/) (2021)
- [Ordered GNN: Ordering Message Passing to Deal with Heterophily and Over-smoothing](https://mlsanity.com/paper/2302.01524/) (2023)
- [A Non-Asymptotic Analysis of Oversmoothing in Graph Neural Networks](https://mlsanity.com/paper/2212.10701/) (2022)
- [Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?](https://mlsanity.com/paper/2306.01323/) (2023)
- [Block Modeling-Guided Graph Convolutional Neural Networks](https://mlsanity.com/paper/2112.13507/) (2021)
- [Bi-GCN: Binary Graph Convolutional Network](https://mlsanity.com/paper/2010.07565/) (2020)
- [Graph Pointer Neural Networks](https://mlsanity.com/paper/2110.00973/) (2021)
- [On the Universality of Graph Neural Networks on Large Random Graphs](https://mlsanity.com/paper/2105.13099/) (2021)
- [Finding the Missing-half: Graph Complementary Learning for Homophily-prone and Heterophily-prone Graphs](https://mlsanity.com/paper/2306.07608/) (2023)
- [Effects of Graph Convolutions in Multi-layer Networks](https://mlsanity.com/paper/2204.09297/) (2022)

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

- [Position: Graph Foundation Models are Already Here](https://mlsanity.com/paper/2402.02216/) (2024)
- [Oversmoothing, Oversquashing, Heterophily, Long-Range, and more: Demystifying Common Beliefs in Graph Machine Learning](https://mlsanity.com/paper/2505.15547/) (2025)
- [Feature Distribution on Graph Topology Mediates the Effect of Graph Convolution: Homophily Perspective](https://mlsanity.com/paper/2402.04621/) (2024)
- [What Is Missing In Homophily? Disentangling Graph Homophily For Graph Neural Networks](https://mlsanity.com/paper/2406.18854/) (2024)
- [GraphTOP: Graph Topology-Oriented Prompting for Graph Neural Networks](https://mlsanity.com/paper/2510.22451/) (2025)
- [On the Necessity of Learnable Sheaf Laplacians](https://mlsanity.com/paper/2603.05395/) (2026)
- [Theoretical and Empirical Insights into the Origins of Degree Bias in Graph Neural Networks](https://mlsanity.com/paper/2404.03139/) (2024)
- [Aggregation Buffer: Revisiting DropEdge with a New Parameter Block](https://mlsanity.com/paper/2505.20840/) (2025)
- [Graph Attention is Not Always Beneficial: A Theoretical Analysis of Graph Attention Mechanisms via Contextual Stochastic Block Models](https://mlsanity.com/paper/2412.15496/) (2024)
- [Deep Graph Learning will stall without Network Science](https://mlsanity.com/paper/2502.01177/) (2025)
- [Full-Spectrum Graph Neural Networks: Expressive and Scalable](https://mlsanity.com/paper/2605.05759/) (2026)
- [Towards Anomaly-Aware Pre-Training and Fine-Tuning for Graph Anomaly Detection](https://mlsanity.com/paper/2504.14250/) (2025)
- [How do Probabilistic Graphical Models and Graph Neural Networks Look at Network Data?](https://mlsanity.com/paper/2506.11869/) (2025)
- [NK-GAD: Neighbor Knowledge-Enhanced Unsupervised Graph Anomaly Detection](https://mlsanity.com/paper/2604.15668/) (2026)
- [Hierarchical Multi-Scale Graph Neural Networks: Scalable Heterophilous Learning with Oversmoothing and Oversquashing Mitigation](https://mlsanity.com/paper/2605.10975/) (2026)

## Abstract (arXiv)

Graphs with heterophily have been regarded as challenging scenarios for Graph Neural Networks (GNNs), where nodes are connected with dissimilar neighbors through various patterns. In this paper, we present theoretical understandings of the impacts of different heterophily patterns for GNNs by incorporating the graph convolution (GC) operations into fully connected networks via the proposed Heterophilous Stochastic Block Models (HSBM), a general random graph model that can accommodate diverse heterophily patterns. Firstly, we show that by applying a GC operation, the separability gains are determined by two factors, i.e., the Euclidean distance of the neighborhood distributions and √mathbbEleft[operatornamedegright], where mathbbEleft[operatornamedegright] is the averaged node degree. It reveals that the impact of heterophily on classification needs to be evaluated alongside the averaged node degree. Secondly, we show that the topological noise has a detrimental impact on separability, which is equivalent to degrading mathbbEleft[operatornamedegright]. Finally, when applying multiple GC operations, we show that the separability gains are determined by the normalized distance of the l-powered neighborhood distributions. It indicates that the nodes still possess separability as l goes to infinity in a wide range of regimes. Extensive experiments on both synthetic and real-world data verify the effectiveness of our theory.