mlsanityData to 7 Oct 2026

Understanding Heterophily for Graph Neural Networks

arXiv 2401.09125 ↗First posted 17 Jan 2024cs.LG stat.MLcited by 15

Not on the map. Why?

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.

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

Builds on

34 of 44 references.

References · 34

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2017Graph Attention Networkscited by 8,854
  3. 2017Inductive Representation Learning on Large Graphscited by 6,284
  4. 2018How Powerful are Graph Neural Networks?cited by 4,355
  5. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  6. 2019Simplifying Graph Convolutional Networkscited by 1,470
  7. 2018Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learningcited by 1,099
  8. 2016Revisiting Semi-Supervised Learning with Graph Embeddingscited by 970
  9. 2020Geom-GCN: Geometric Graph Convolutional Networkscited by 821
  10. 2020Adaptive Universal Generalized PageRank Graph Neural Networkcited by 592
  11. 2021Beyond Low-frequency Information in Graph Convolutional Networkscited by 361
  12. 2023A critical look at the evaluation of GNNs under heterophily: Are we really making progress?cited by 332
22 more
  1. 2021Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networkscited by 182
  2. 2021Is Homophily a Necessity for Graph Neural Networks?cited by 182
  3. 2022Finding Global Homophily in Graph Neural Networks When Meeting Heterophilycited by 179
  4. 2022Revisiting Heterophily For Graph Neural Networkscited by 169
  5. 2018Contextual Stochastic Block Modelscited by 134
  6. 2021Breaking the Limit of Graph Neural Networks by Improving the Assortativity of Graphs with Local Mixing Patternscited by 95
  7. 2020Non-Local Graph Neural Networkscited by 91
  8. 2021New Benchmarks for Learning on Non-Homophilous Graphscited by 81
  9. 2021Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalizationcited by 70
  10. 2023Ordered GNN: Ordering Message Passing to Deal with Heterophily and Over-smoothingcited by 67
  11. 2022A Non-Asymptotic Analysis of Oversmoothing in Graph Neural Networkscited by 49
  12. 2023Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?cited by 41
  13. 2021Block Modeling-Guided Graph Convolutional Neural Networkscited by 32
  14. 2020Bi-GCN: Binary Graph Convolutional Networkcited by 27
  15. 2021Graph Pointer Neural Networkscited by 27
  16. 2021On the Universality of Graph Neural Networks on Large Random Graphscited by 26
  17. 2023Finding the Missing-half: Graph Complementary Learning for Homophily-prone and Heterophily-prone Graphscited by 25
  18. 2022Effects of Graph Convolutions in Multi-layer Networkscited by 24
  19. 2022Understanding Non-linearity in Graph Neural Networks from the Bayesian-Inference Perspectivecited by 19
  20. 2022Meta-Weight Graph Neural Network: Push the Limits Beyond Global Homophilycited by 14
  21. 2022Learnable Graph Convolutional Attention Networkscited by 8
  22. 2023Heterophily-Aware Graph Attention Networkcited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 5; 2025: 6; 2026: 4.

15 papers.

Sort:

  1. 2024Position: Graph Foundation Models are Already Herecited by 84
  2. 2025Oversmoothing, Oversquashing, Heterophily, Long-Range, and more: Demystifying Common Beliefs in Graph Machine Learningcited by 18
  3. 2024Feature Distribution on Graph Topology Mediates the Effect of Graph Convolution: Homophily Perspectivecited by 9
  4. 2024What Is Missing In Homophily? Disentangling Graph Homophily For Graph Neural Networkscited by 9
  5. 2025GraphTOP: Graph Topology-Oriented Prompting for Graph Neural Networkscited by 5
  6. 2026On the Necessity of Learnable Sheaf Laplacianscited by 5
  7. 2024Theoretical and Empirical Insights into the Origins of Degree Bias in Graph Neural Networkscited by 4
  8. 2025Aggregation Buffer: Revisiting DropEdge with a New Parameter Blockcited by 3
  9. 2024Graph Attention is Not Always Beneficial: A Theoretical Analysis of Graph Attention Mechanisms via Contextual Stochastic Block Modelscited by 2
  10. 2025Deep Graph Learning will stall without Network Sciencecited by 1
  11. 2025Towards Anomaly-Aware Pre-Training and Fine-Tuning for Graph Anomaly Detectioncited by 0
  12. 2025How do Probabilistic Graphical Models and Graph Neural Networks Look at Network Data?cited by 0
3 more
  1. 2026NK-GAD: Neighbor Knowledge-Enhanced Unsupervised Graph Anomaly Detectioncited by 0
  2. 2026Full-Spectrum Graph Neural Networks: Expressive and Scalablecited by 0
  3. 2026Hierarchical Multi-Scale Graph Neural Networks: Scalable Heterophilous Learning with Oversmoothing and Oversquashing Mitigationcited by 0