Not All Nodes Are Created Equal: Homophily-Aware Stratification for Stable GNN Evaluation
Naga Venkata Sai Jitin Jami, Thomas Altstidl, Sebastian Hoefler, Jonas Mueller, Dario Zanca, Bjoern Eskofier, Heike Leutheuser
cs.SI · cs.AI · cs.LG · stat.ML
Quick verdict
Proposes homophily-first k-fold stratification for GNNs; 15-dataset study shows variance cuts, but no significance tests and noisy k=4 std temper claims.
Summary
The paper tackles split-induced variance in transductive node-classification benchmarks. Because standard GNN accuracy depends on local neighborhood homophily, randomly drawn k-fold test sets differ systematically in relational composition, inflating cross-fold accuracy variance beyond genuine model differences. The authors propose HpStrat, which discretizes per-node homophily into ten equal-width bins and round-robin assigns nodes within each (bin, class) stratum, treating homophily as the primary stratification axis and class balance as a secondary consequence. Across 15 PyG datasets spanning mean homophily 0.05–0.92 and seven architectures (GCN, GAT, GraphSAGE, APPNP, MixHop, H2GCN, GPR-GNN) under fixed hyperparameters and 50/25/25 k=4 folds, HpStrat attains a mean stability rank of 1.49 versus 2.31 for random and 2.20 for class-stratified k-fold, ranking first on 13 of 15 datasets and first on fold-homophily balance (CHD) everywhere. Regressions over 200 folds per combination confirm fold homophily predicts accuracy (R² 0.021–0.289, p<0.05). Limitations: rank results lack significance tests; cross-fold standard deviation estimated from only four folds is noisy and main k=4 results appear single-seed; and mean accuracies shift under HpStrat (e.g., GCN/Squirrel 27.41→24.00), leaving the estimand question open. Code is public.
Review complete
Assessment at a glance
5
risk flags identified
● high 0
● medium 4
● low 1
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- Fold-level homophily composition is a statistically significant predictor of test-fold accuracy under random k-fold splits across model/dataset combinations (Appendix B, p<0.05, R² 0.021–0.289).
- HpStrat achieves the lowest cross-fold accuracy variance rank on 13 of 15 datasets, with overall mean stability rank 1.49 vs 2.31 (random) and 2.20 (class-stratified), ranking first for every architecture (Tables 3–4).
- Class-stratified k-fold does not control fold homophily (CHD 2.47 vs random 2.53) and therefore does not reliably stabilize GNN evaluation (Table 2).
- The choice of split strategy changes which architecture is reported best on 8 of 15 datasets (Appendix E).
- HpStrat degrades exactly when the homophily distribution is concentrated in few bins (Wisconsin, Actor, Cornell at k=5), a regime diagnosable from the homophily histogram before any training (§3.2, §5.3).
Strengths
Mechanism verified directly, not just asserted
Appendix B regresses fold-level test accuracy on test-fold homophily over 200 folds per combination across 9 model/dataset pairs, all significant (p<0.05); Table 2 then confirms the intervention works on the targeted metric (CHD rank 1.00 on all 15 datasets, vs 2.53 random / 2.47 class-stratified).
Broad, current benchmark coverage with robustness checks
15 PyG datasets spanning mean homophily 0.05 (Roman-Empire) to 0.92 (Physics), including leakage-corrected Chameleon/Squirrel (§4.1); 7 architectures from GCN to GPR-GNN; conclusions replicated at k=4, k=5, and 6-seed k=4 (Appendix C: overall ranks 1.49 / 1.63 / 1.53 vs random 2.31 / 2.11 / 2.34).
Honest, falsifiable failure-mode analysis
Practical consequence and adoption cost quantified
Clean drop-in design with guarded claims
Weaknesses
No statistical testing of the headline rank results
Primary metric is a noisy dispersion estimate
Estimand shift unexamined
Selection and strength of Appendix B evidence
Missing structural-stratification control and limited scope
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
This is an evaluation-methodology paper, not a modeling paper: its target quantity is the *variance of GNN performance measurement* in transductive node classification. The thesis is that random k-fold splits differ systematically in test-fold local homophily, and that this relational mismatch — not class imbalance — is a dominant, fixable source of cross-fold accuracy variance. Four claims carry the paper: (1) fold-level homophily significantly predicts fold accuracy under random splits (Appendix B: 9 combinations × 200 folds, all p<0.05, R² 0.021–0.289); (2) HpStrat, a homophily-primary/class-secondary stratification (Algorithm A.1), attains the lowest cross-fold std rank on 13/15 datasets with overall mean rank 1.49 vs 2.31 (random) and 2.20 (class-stratified), first for every architecture (Tables 3–4); (3) class stratification alone does not control homophily (Table 2: CHD rank 2.47 vs random's 2.53, while HpStrat is 1.00 everywhere); (4) split strategy flips the best-reported architecture on 8/15 datasets (Appendix E).
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 5 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What is HpStrat?
HpStrat (Homophily-Priority Stratification) is a k-fold split-construction method for transductive graph node classification. It bins each node's homophily (the fraction of its neighbors sharing its label) into ten equal-width bins, then distributes nodes round-robin within each bin-class group so that every fold mirrors the full graph's homophily distribution while class balance is preserved as a side effect. It is a drop-in replacement for random k-fold with negligible runtime.
Why doesn't class-stratified cross-validation fix GNN evaluation instability?
GNN accuracy depends not only on class composition but on neighborhood structure. The paper measures cross-fold homophily deviation (CHD) and shows class-stratified folds barely improve on random ones (mean CHD rank 2.47 vs 2.53), meaning folds can be class-balanced yet expose the model to systematically different relational conditions, so accuracy still varies across folds for reasons unrelated to the model.
When does HpStrat fail or not help?
When most nodes' homophily values fall into one or two bins (a skewed histogram), the method degenerates toward plain class-stratified k-fold. This happened on Wisconsin and Actor (and Cornell at k=5), the datasets with the most concentrated homophily distributions. The failure regime can be diagnosed from the homophily histogram before any model is trained, and density-adaptive binning is proposed as a future fix.
Is code and data available for this paper?
Yes. The splitting code is public at github.com/jitinjami/graph-strat, and all 15 benchmark datasets are standard public PyTorch Geometric datasets (with the corrected, leakage-free versions of Chameleon and Squirrel). Split construction runs in under 13 ms even on graphs of ~35,000 nodes.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- Figures 1, 2, B.1 and F.1 render as garbled glyph sequences in the extracted text; the review relies on the tables, which extracted completely.
- The seed count behind the main k=4 accuracy table (C.1) is not stated in the text; single-seed status is inferred from §4.3's description of the additional settings.
- The abstract in the provided metadata is truncated mid-sentence; the full embedded paper text was used for this review.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.