# Not All Nodes Are Created Equal: Homophily-Aware Stratification for Stable GNN Evaluation

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 26 of its 38 references that are in the map.
- First posted on arXiv 16 Sep 2026.

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

- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (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)
- [Geometric deep learning on graphs and manifolds using mixture model CNNs](https://mlsanity.com/paper/1611.08402/) (2016)
- [MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing](https://mlsanity.com/paper/1905.00067/) (2019)
- [A critical look at the evaluation of GNNs under heterophily: Are we really making progress?](https://mlsanity.com/paper/2302.11640/) (2023)
- [Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods](https://mlsanity.com/paper/2110.14446/) (2021)
- [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)
- [Classic GNNs are Strong Baselines: Reassessing GNNs for Node Classification](https://mlsanity.com/paper/2406.08993/) (2024)
- [Characterizing Graph Datasets for Node Classification: Homophily-Heterophily Dichotomy and Beyond](https://mlsanity.com/paper/2209.06177/) (2022)
- [Position: Graph Learning Will Lose Relevance Due To Poor Benchmarks](https://mlsanity.com/paper/2502.14546/) (2025)
- [A Network Perspective on Stratification of Multi-Label Data](https://mlsanity.com/paper/1704.08756/) (2017)
- [On Performance Discrepancies Across Local Homophily Levels in Graph Neural Networks](https://mlsanity.com/paper/2306.05557/) (2023)
- [Feature Distribution on Graph Topology Mediates the Effect of Graph Convolution: Homophily Perspective](https://mlsanity.com/paper/2402.04621/) (2024)
- [Stratified Sampling for Extreme Multi-Label Data](https://mlsanity.com/paper/2103.03494/) (2021)
- [EvoSplit: An evolutionary approach to split a multi-label data set into disjoint subsets](https://mlsanity.com/paper/2102.06154/) (2021)
- [Novel split quality measures for stratified multilabel Cross Validation with application to large and sparse gene ontology datasets](https://mlsanity.com/paper/2109.01425/) (2021)
- [Stratify or Die: Rethinking Data Splits in Image Segmentation](https://mlsanity.com/paper/2509.21056/) (2025)

## Abstract (arXiv)

Graph neural networks are widely used for transductive node classification, with accuracy typically measured on randomly drawn train/validation/test splits. Reported accuracy has been shown to shift substantially across different random splits of the same dataset, making published comparisons between architectures unreliable. The classical remedy in non-graph settings is stratified k-fold cross-validation, which ensures each test fold reflects the full class distribution of the dataset. We argue that class stratification alone is insufficient for graphs: nodes are not isolated but connected, and folds that differ in their distribution of local neighbourhood homophily expose the model to systematically different relational conditions that directly affect message-passing behaviour. The resulting cross-fold variation reflects the homophily composition of each split, inflating reported variance beyond what model behaviour alone would produce. To address this, we propose hp, a topology-aware stratification procedure that treats node homophily as the primary stratification axis, aligning folds with respect to local relational consistency alongside the class marginal that standard stratification already controls. Stratifying on homophily alone does not guarantee class balance, so hp incorporates class label as a secondary axis, preserving class representativeness as a natural consequence of the procedure. We evaluate hp on a broad benchmark suite comprising 15 node-classification datasets spanning the full homophily spectrum and 7 GNN architectures. hp achieves a mean stability rank of 1.49 compared to 2.31 for random k-fold, achieving the lowest mean stability rank on 13 of 15 datasets while preserving class balance close to class-stratified splits and substantially better than random. We argue that homophily-aware split construction merits broader adoption for GNN evaluation.