HpStrat - Homophily-Aware Stratification

Building cross-validation folds for graph neural networks that balance node homophily, not just class labels, for more stable GNN evaluation.

GNN accuracy on node classification can shift substantially from one random train/test split to another, which makes comparisons between architectures unreliable. Stratifying by class, the usual remedy, is not enough on graphs: nodes are connected, and folds that differ in their mix of local neighbourhood homophily expose the model to systematically different conditions for message passing.

We propose HpStrat, a stratification procedure that uses node homophily as the primary axis and class label as the secondary one. Across 15 node-classification datasets spanning the full homophily spectrum and 7 GNN architectures, it reaches a mean stability rank of 1.49, against 2.31 for random k-fold, and is the most stable method on 13 of the 15 datasets, while keeping class balance close to class-stratified splits.

Random, class-stratified and HpStrat splits of the same graph
The same graph split three ways. Random and class-stratified splits leave folds with different homophily; HpStrat balances both homophily and classes.

This extends our earlier work on stratification for image segmentation to graphs.

Accepted at the Learning on Graphs Conference (LoG) 2026. arXiv · Code