# Characterizing Graph Datasets for Node Classification: Homophily-Heterophily Dichotomy and Beyond

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

## Key facts

- Cited by 60 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 52 references that are in the map.
- First posted on arXiv 13 Sep 2022.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [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)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Gaussian Error Linear Units (GELUs)](https://mlsanity.com/paper/1606.08415/) (2016)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (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)
- [GraphSAINT: Graph Sampling Based Inductive Learning Method](https://mlsanity.com/paper/1907.04931/) (2019)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classification](https://mlsanity.com/paper/2009.03509/) (2020)
- [MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing](https://mlsanity.com/paper/1905.00067/) (2019)
- [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)
- [Is Homophily a Necessity for Graph Neural Networks?](https://mlsanity.com/paper/2106.06134/) (2021)
- [Characteristic Functions on Graphs: Birds of a Feather, from Statistical Descriptors to Parametric Models](https://mlsanity.com/paper/2005.07959/) (2020)
- [Breaking the Limit of Graph Neural Networks by Improving the Assortativity of Graphs with Local Mixing Patterns](https://mlsanity.com/paper/2106.06586/) (2021)
- [Is Heterophily A Real Nightmare For Graph Neural Networks To Do Node Classification?](https://mlsanity.com/paper/2109.05641/) (2021)
- [Twitch Gamers: a Dataset for Evaluating Proximity Preserving and Structural Role-based Node Embeddings](https://mlsanity.com/paper/2101.03091/) (2021)
- [Expertise and Dynamics within Crowdsourced Musical Knowledge Curation: A Case Study of the Genius Platform](https://mlsanity.com/paper/2006.08108/) (2020)
- [Taxonomy of Benchmarks in Graph Representation Learning](https://mlsanity.com/paper/2206.07729/) (2022)
- [Good Classification Measures and How to Find Them](https://mlsanity.com/paper/2201.09044/) (2022)
- [Community Detection through Likelihood Optimization: In Search of a Sound Model](https://mlsanity.com/paper/1802.04472/) (2018)

## Built on by (most cited first, 30 of 60)

- [A critical look at the evaluation of GNNs under heterophily: Are we really making progress?](https://mlsanity.com/paper/2302.11640/) (2023)
- [Turning Tabular Foundation Models into Graph Foundation Models](https://mlsanity.com/paper/2508.20906/) (2025)
- [A Label-Free Heterophily-Guided Approach for Unsupervised Graph Fraud Detection](https://mlsanity.com/paper/2502.13308/) (2025)
- [GraphPFN: A Prior-Data Fitted Graph Foundation Model](https://mlsanity.com/paper/2509.21489/) (2025)
- [GraphLand: Evaluating Graph Machine Learning Models on Diverse Industrial Data](https://mlsanity.com/paper/2409.14500/) (2024)
- [Oversmoothing, Oversquashing, Heterophily, Long-Range, and more: Demystifying Common Beliefs in Graph Machine Learning](https://mlsanity.com/paper/2505.15547/) (2025)
- [Node-wise Filtering in Graph Neural Networks: A Mixture of Experts Approach](https://mlsanity.com/paper/2406.03464/) (2024)
- [No Metric to Rule Them All: Toward Principled Evaluations of Graph-Learning Datasets](https://mlsanity.com/paper/2502.02379/) (2025)
- [GNNs Getting ComFy: Community and Feature Similarity Guided Rewiring](https://mlsanity.com/paper/2502.04891/) (2025)
- [Towards Mechanistic Interpretability of Graph Transformers via Attention Graphs](https://mlsanity.com/paper/2502.12352/) (2025)
- [Mitigating Oversmoothing Through Reverse Process of GNNs for Heterophilic Graphs](https://mlsanity.com/paper/2403.10543/) (2024)
- [On the Impact of Feature Heterophily on Link Prediction with Graph Neural Networks](https://mlsanity.com/paper/2409.17475/) (2024)
- [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)
- [Joint Diffusion Processes as an Inductive Bias in Sheaf Neural Networks](https://mlsanity.com/paper/2407.20597/) (2024)
- [AGS-GNN: Attribute-guided Sampling for Graph Neural Networks](https://mlsanity.com/paper/2405.15218/) (2024)
- [When Heterophily Meets Heterogeneity: Challenges and a New Large-Scale Graph Benchmark](https://mlsanity.com/paper/2407.10916/) (2024)
- [Semantic Refinement with LLMs for Graph Representations](https://mlsanity.com/paper/2512.21106/) (2025)
- [Rethinking Graph Contrastive Learning through Relative Similarity Preservation](https://mlsanity.com/paper/2505.05533/) (2025)
- [Rethinking Spectral Graph Neural Networks with Spatially Adaptive Filtering](https://mlsanity.com/paper/2401.09071/) (2024)
- [Mixture of Experts for Node Classification](https://mlsanity.com/paper/2412.00418/) (2024)
- [Revisiting Graph Homophily Measures](https://mlsanity.com/paper/2412.09663/) (2024)
- [Homophily Heterogeneity Matters in Graph Federated Learning: A Spectrum Sharing and Complementing Perspective](https://mlsanity.com/paper/2502.13732/) (2025)
- [Fixed Aggregation Features Can Rival GNNs](https://mlsanity.com/paper/2601.19449/) (2026)
- [OpenRFM: Dissecting Relational In-Context Learning](https://mlsanity.com/paper/2606.04320/) (2026)
- [A Fair Evaluation of Graph Foundation Models for Node Property Prediction](https://mlsanity.com/paper/2606.24509/) (2026)
- [Contextualized Messages Boost Graph Representations](https://mlsanity.com/paper/2403.12529/) (2024)
- [Unraveling the Impact of Heterophilic Structures on Graph Positive-Unlabeled Learning](https://mlsanity.com/paper/2405.19919/) (2024)
- [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)

## Abstract (arXiv)

Homophily is a graph property describing the tendency of edges to connect similar nodes; the opposite is called heterophily. It is often believed that heterophilous graphs are challenging for standard message-passing graph neural networks (GNNs), and much effort has been put into developing efficient methods for this setting. However, there is no universally agreed-upon measure of homophily in the literature. In this work, we show that commonly used homophily measures have critical drawbacks preventing the comparison of homophily levels across different datasets. For this, we formalize desirable properties for a proper homophily measure and verify which measures satisfy which properties. In particular, we show that a measure that we call adjusted homophily satisfies more desirable properties than other popular homophily measures while being rarely used in graph machine learning literature. Then, we go beyond the homophily-heterophily dichotomy and propose a new characteristic that allows one to further distinguish different sorts of heterophily. The proposed label informativeness (LI) characterizes how much information a neighbor's label provides about a node's label. We prove that this measure satisfies important desirable properties. We also observe empirically that LI better agrees with GNN performance compared to homophily measures, which confirms that it is a useful characteristic of the graph structure.