PaperlayerView exact revision on arXiv

Source-linked AI summary

Disentangling Homophily and Rarity: Explaining Failure in Graph Neural Networks

Preben M. Ness, Fariz Ikhwantri, Dusica Marijan

arXiv:2608.14823v1cs.LG

TL;DR

The paper asks whether rare-homophily classification difficulty reflects general classification or the way GNNs process data. Through empirical evaluation and balanced retraining, it finds that heterophilic nodes are harder regardless of rarity, while representations often retain information recoverable by retraining the classifier.

  • Problem

    The paper investigates whether rare-homophily nodes are harder to classify because of rarity or because of how GNNs process data.

  • Method

    The study trains GNNs with empirical risk minimisation, then uses balanced GroupDRO retraining of the last layer, classification head, or full model.

  • Results

    Locally heterophilic nodes are harder to classify regardless of whether they are rare or common, while frozen representations often retain information needed for correct classification.

  • Takeaways & Limitations

    The findings challenge subgroup-generalisation framing and nuance claims that GNN aggregation destroys information needed to classify rare-homophily nodes.

  • Takeaways & Limitations

    The observed effects do not identify underlying mechanisms, and separating homophily from node difficulty, degree, class composition, and other confounders requires further experiments.

Abstract

from arXiv · show

Are heterophilic nodes in a graph harder to classify because they are heterophilic or because they are rare? Some existing work frames classification of such nodes as a subgroup generalisation problem, where a model performs well on the majority group at the expense of the rare group. Others explain this as a problem of neighbourhood aggregation in graph neural networks (GNNs). We assess these two viewpoints through a detailed evaluation of six GNNs on five datasets of varying homophily, and find that homophilic nodes tend to be easier to classify, even when they are rare---challenging the subgroup framing. However, our findings also nuance existing beliefs about how GNNs misrepresent heterophilic nodes. We demonstrate that the information needed to classify heterophilic nodes correctly is often recoverable by retraining the classification head of a model, or even just the final linear classification layer.

1 Introduction

The introduction frames rare-homophily classification as a choice between subgroup generalisation and failures in GNN representations. The paper investigates whether heterophilic nodes are intrinsically harder and whether their classification information remains recoverable through retraining.

  • Motivation: Existing work explains rare-homophily difficulty either as subgroup generalisation driven by spurious correlations or as a failure of GNN representations.The representation account attributes performance gaps to neighbourhood aggregation making nodes increasingly similar to their neighbours.
  • Motivation: Classification errors may reflect missing information in a node representation or a poorly drawn classification boundary.Prior work suggests rare-subgroup performance can often be recovered by cheaply retraining the final linear layer.
  • Research questions: The study asks whether rare heterophilic and rare homophilic nodes are harder to classify and whether their required information remains recoverable in latent representations.These questions distinguish a general classification problem from a phenomenon arising from how GNNs process data.
  • Methods: The experiments compare retraining the final affine layer, the complete graph-independent head, or the full model from a standard ERM model.The diagnostic preparations vary which components are trainable or frozen, their initialisation source, and the optimisation objective.
  • Contributions: Heterophilic nodes tend to be harder to classify even when most nodes are heterophilic, challenging the subgroup-generalisation framing.The paper reports this as a central empirical finding across its investigation of node classification under varying homophily.
  • Contributions: Rare-homophily node representations often contain the information needed for classification, and retraining the classification head or last layer can recover performance.This finding nuances the proposed representation-collapse explanation.

2 Related Work

Prior work links GNN performance to local homophily and studies heterophilic classification through subgroup generalisation, specialized architectures, and representation probing. However, these approaches generally do not disentangle homophily direction, structural rarity, class composition, and classifier effects.

  • Graph Homophily: Prior studies report that GNN performance varies with local homophily, but use differing definitions of relevant node groups.Examples include deviations from graph-wide homophily, common versus uncommon neighbourhood patterns, and fixed local-homophily intervals.
  • Subgroup Generalisation: Subgroup-generalisation work examines failures on node types poorly represented in training data, including accuracy declines with distance from training nodes in aggregated-feature space.Synthetic-graph results also associate more uniform representation of local-homophily patterns among labelled nodes with smaller disparities.
  • Heterophily-designed Architectures: Heterophily-designed architectures improve predictive performance by changing graph-information processing, including separate ego and multi-hop representations, learned propagation weights, adaptive filters, or no neighbourhood propagation.Examples include H2GCN, GPR-GNN, ACM-GCN, Node-MoE, and LINKX; Mowst routes nodes between feature-only and graph-dependent predictors.
  • Assessing Representations: Representation probing freezes a model’s representation and fits a new classifier to separate information available in the representation from the effects of the fitted classifier.Linear and non-linear probes provide this diagnostic with classifiers of different capacity.

3 Definitions and Research Questions

This section defines node-level homophily, dataset and tail terminology, and a controlled retraining framework. It formulates research questions about rare-tail performance, model aggregation, and where recoverable information is lost.

  • Definitions: Nodes are assigned to four equal-width h_v bins, merging bins below 1% of graph nodes; assignments depend only on the dataset and remain fixed across experiments.The resulting bins define the tails used throughout the evaluation.
  • Definitions: Datasets are homophilic when mean h_v > 0.5 and heterophilic otherwise; rare homophily nodes have uncommon h_v values, with the extreme bin defining the rare homophily tail.The tail is the lowest-h_v bin for homophilic datasets and the highest-h_v bin for heterophilic datasets.
  • Retraining procedures: Models are decomposed into a graph-dependent encoder h, nonlinear head g, and final linear classifier f, enabling retraining of the final layer, whole head, or full model.The procedures are A_l^ast, A_head, and A_full, respectively, using balanced GroupDRO over homophily bins after standard AERM training.
  • Research questions: The research questions test rare-tail performance gaps, within-class gaps, aggregation-model comparisons, and whether recoverable information is lost in f, f ◦g, or h.They compare homophilic and heterophilic datasets, aggregation models with an MLP, and heterophily-designed models with standard baselines.

4 Experimental Setup

The experiments evaluate six GNNs and an MLP across five datasets spanning homophilic and heterophilic settings, using repeated split-and-seed runs. Performance is assessed with bin-level macro-F1, tail-gap and class-composition adjustments, and bootstrap confidence intervals for uncertainty and significance.

  • Datasets: The study uses five datasets: two homophilic datasets, PubMed and ogbn-arxiv, and three heterophilic datasets, Roman-empire, Amazon-ratings, and arxiv-year.arxiv-year and ogbn-arxiv share the same graph but use different labels.
  • Models and training: Each model, dataset, and training procedure is evaluated over 30 runs combining dataset splits with random training seeds.The split and seed configurations vary by dataset, including Geom-GCN, Platonov, OGB time, and Lim et al. splits.
  • Models and training: The model set comprises six GNNs—GCN, GraphSAGE-mean, H2GCN-2, GPR-GNN, ACM-GCN, and LINKX—plus a graphless MLP baseline.The models include both standard and heterophily-designed aggregators, as well as the non-aggregation model LINKX.
  • Evaluation metrics: Individual homophily bins are typically evaluated with macro-F1, computed only over classes represented in a bin when some classes are absent.This treatment avoids arbitrary scores for absent classes and preserves a perfect-predictor score of 1.00.
  • Evaluation metrics: Tail gaps compare whole-test performance with tail-bin performance, while class-adjusted tail gaps account for differences in tail class composition.Metrics, gaps, and retraining differences are averaged over the 30 runs with 95% confidence intervals.
  • Uncertainty and statistical significance: Reported tail gaps and retraining gains use 1,000 bootstrap resamples of the 30 matched runs, with significance claimed when the 95% confidence interval excludes 0.The 30 dataset split/random seed runs are treated as independent resampling units, without multiplicity correction.

5 Results and Analysis

Results show that locally homophilic nodes are generally easier to classify, including when homophilic nodes are rare, while tail difficulty is partly dataset- and class-composition-dependent. MLPs often narrow tail gaps, and retraining classification components can recover substantial tail performance from frozen representations.

  • RQ1: Across four interpretable datasets, models generally achieve higher average macro-F1 on locally homophilic nodes.Roman-empire is noisy because its local-homophily distribution is skewed across bins.
  • RQ1a: Class adjustment leaves homophilic-dataset tail gaps essentially unchanged but reduces all Roman-empire and Amazon-ratings gaps, implicating difficult-class overrepresentation.Both homophilic datasets have positive tail gaps; Amazon-ratings has negative gaps for every model before adjustment.
  • RQ1: Rewiring edges to make nodes more homophilic increases GCN and GraphSAGE-mean performance, even when homophilic nodes are rare.The experiment preserves node degree while progressively moving local homophily toward the graph mean or changing edges randomly.
  • RQ1b: MLP has smaller tail gaps than aggregation models on both homophilic datasets and outperforms all other models on the tail bin.On heterophilic datasets, MLP tail gaps are small in magnitude, while other models’ gaps vary.
  • RQ1c: Heterophily-designed aggregators show slightly smaller tail gaps on homophilic datasets but no consistent advantage on heterophilic datasets.They also do not clearly outperform standard baseline models overall.
  • RQ2: Among 17 significant model/dataset cells, final-layer retraining exceeds 70% recovery in eight and head retraining in 13, with more consistent recovery on homophilic datasets.This indicates frozen representations often retain information needed for correct tail classification; DFR was sometimes competitive with GroupDRO, whereas FG-CCDB failed in all tested cases.

6 Conclusion · A Deviations from Preregistration

The conclusion finds that local heterophily, rather than rarity alone, explains classification difficulty in homophilic graphs, while frozen representations often retain recoverable information for rare-homophily nodes. It also emphasizes measurement, experimental, and causal limitations, alongside documented preregistration deviations.

  • 6 Conclusion: Locally heterophilic nodes are harder to classify in homophilic graphs, regardless of whether they are rare or common.The evidence does not clearly support the opposite-direction claim that locally homophilic nodes are difficult in heterophilic graphs.
  • 6 Conclusion: Balanced retraining of the classifier head, and often only the last linear layer, improves rare-homophily tail performance from frozen representations.The extent of improvement varies across models and datasets, indicating that required classification information is often retained.
  • 6 Conclusion: Homophily bins are oracle quantities because computing hv uses full-graph true labels, including held-out neighbour labels that can affect training-node bins.Future work could instead use estimated hv values without validation or test-set labels.
  • 6 Conclusion: Retraining tests whether information is usable in frozen representations, but failure cannot distinguish absent information from unsuccessful retraining.There is no single definite way to measure the information contained in a latent representation, making this assessment flexible but one-directional.
  • 6 Conclusion: The experiments trained seven models on five transductive benchmark datasets across 30 split–seed combinations, limiting generalisation beyond the tested settings.Broader evaluation across graphs, models, training settings, and sources of training variation is identified as future work.
  • 6 Conclusion: The reported effects remain descriptive, and disentangling homophily from node difficulty, degree, class composition, and other confounders requires further study.Exploratory edge interventions provide preliminary evidence that neighbourhood label composition contributes to tail-node performance.
  • A Deviations from Preregistration: The full analysis protocol, methodology, and experimental settings were registered on 10 July 2026, with all deviations recorded in Table 1.The deviations ledger covers departures from the preregistered analysis and experimental protocol.

B Details of Model Architectures and Training Settings

The models use a shared Platonov-style backbone where specified, while model-specific operations, source-release settings, and study-specific recovery choices determine the remaining architecture and training setup. Inputs are standardized as undirected graphs, and GroupDRO uses full-batch group losses with uniformly initialized, stepwise-updated weights and no generalisation adjustment.

  • Shared backbone: MLP, GCN, and GraphSAGE-mean use Platonov et al.’s five-block residual backbone with dropout 0.2 throughout.The backbone and optimiser settings follow Platonov et al.’s implementation.
  • Model-specific layers: Each model-specific operation is followed by an FFN whose first layer maps its output to width 512, with W2 mapping 512 →512.The FFN uses dropout and GELU between its two learned layers.
  • Training settings: Model-specific architectures and baseline settings follow the H2GCN, GPR-GNN, ACM-GCN, and LINKX source releases, while the shared head and recovery preparations are study-specific.LINKX uses the PyTorch Geometric implementation; uniform representation widths are also study-specific.
  • Graph preprocessing: All models receive the same simple undirected graph after directed edges are symmetrised and duplicate edges are collapsed before each model’s self-loop convention.Local homophily is calculated on this resulting undirected graph.
  • GroupDRO: GroupDRO uses full-batch group losses, starts group weights uniformly, updates them after each step, and optimises the weighted group-loss sum without generalisation adjustment.For group g, Lg denotes the mean training cross-entropy and the optimised loss is ∑g qgLg.

C Training Hardware and Computational Cost

Training used one CUDA GPU per run, with experiments conducted on NVIDIA A100 and RTX 3080 hardware. Reported GPU-hours measure optimisation-loop duration while excluding several ancillary processing stages.

  • Training hardware: All 4,200 main-panel runs used CUDA and one GPU per run on NVIDIA A100 or GeForce RTX 3080 hardware.The A100 had 80 GB memory and the RTX 3080 had 16 GB.
  • Computational cost: GPU-hours were calculated from the recorded optimisation-loop duration for each run.This defines the computational-cost measurement reported in Table 3.
  • Computational cost: The GPU-hour calculation excluded data loading, preprocessing, frozen-feature computation, final test evaluation, and serialisation.Frozen-feature computation was excluded for Alast and Ahead because it was a one-off step.

D Local-Homophily Bins … F.1 Within-class accuracy.

The paper defines local-homophily bins with an under-threshold merge rule, then evaluates tail performance using macro-F1, accuracy, and within-class accuracy gaps. These analyses compare whole-test or non-tail outcomes against performance in rare homophily tails.

  • D Local-Homophily Bins: Nodes are assigned to four base local-homophily bins, with bins below 1% of nodes repeatedly merged into an adjacent bin.Ties are resolved toward lower local homophily, then toward the larger adjacent bin, dataset mean, and lower local homophily.
  • D Local-Homophily Bins: The merge rule triggers only once across five datasets: Roman-empire’s 81 nodes in [0.75, 1] merge with [0.5, 0.75).
  • E RQ1 Appendix: Figure 7 reports average test accuracy across 12 equal-width local-homophily bins and marks each dataset’s rare homophily tail.Roman-empire accuracy is omitted when a bin lacks test nodes in at least one split.
  • E.1 Macro-F1 Tail Gap: The ERM signed tail gap is defined as whole-test macro-F1 minus tail macro-F1, with positive values indicating lower tail performance.Values summarize mean paired differences over 30 matched split–seed runs with 95% percentile-bootstrap intervals; grey cells contain zero.
  • E.2 Whole-Test and Tail Accuracy: The ERM accuracy gap is defined as whole-test accuracy minus tail accuracy, with positive values indicating lower tail accuracy.Values summarize mean paired differences over 30 matched split–seed runs with 95% percentile-bootstrap intervals; grey cells contain zero.
  • F RQ1a: Within-Class Analyses and Class-Composition Adjustment: The within-class analysis adjusts for class composition by comparing tail and non-tail accuracy separately for each true class represented in both subsets.It subtracts tail accuracy from non-tail accuracy within each class and averages class-wise differences equally.
  • F.1 Within-class accuracy.: Table 7 reports per-class non-tail accuracy minus tail accuracy, averaged equally over classes across 30 runs.Each cell includes a 95% percentile-bootstrap interval, and grey cells denote intervals containing zero.

F.2 Class-adjusted RQ1 gaps. … I.1 RQ2: Sensitivity to Retraining Approach

The paper standardises tail-gap comparisons for class composition before evaluating aggregation models, heterophily-designed models, and retraining procedures. These analyses distinguish composition effects from prediction patterns and test how much tail performance can be recovered by refitting different parts of the model.

  • F.2 Class-adjusted RQ1 gaps.: The class-adjusted comparison restricts whole-test evaluation to classes represented in each tail, then reweights tail predictions to match their whole-test proportions.Predictions outside the tail’s class set remain errors, while classes absent from the tail are excluded from both evaluations.
  • F.2 Class-adjusted RQ1 gaps.: Adjusted accuracy and macro-F1 gaps retain within-class tail prediction patterns while standardising class composition, so they can differ from unadjusted gaps.The adjusted gap may also change when the tail omits classes; “adjusted” denotes statistical standardisation, not a causal interpretation.
  • G RQ1b Tail Gaps of Aggregation models vs MLP: The study compares aggregation-based GNN tail gaps with the graphless MLP across five datasets using macro-F1 differences, including class-composition-adjusted differences.Each plotted estimate averages 30 matched split–seed differences with 95% bootstrap intervals.
  • G RQ1b Tail Gaps of Aggregation models vs MLP: For RQ1b, a positive tail gap means worse performance on the rare homophily tail, and a larger gap means a larger tail-versus-test performance disparity.The adjusted analysis repeats this comparison after standardising class composition.
  • H RQ1c: Heterophily-Designed Versus Standard Aggregation Models: RQ1c compares each heterophily-designed model with each standard aggregation baseline using differences between their macro-F1 tail gaps.Negative values indicate a smaller tail gap for the heterophily-designed model, while intervals containing zero are not statistically significant.
  • H RQ1c: Heterophily-Designed Versus Standard Aggregation Models: The class-composition-standardised RQ1c analysis reweights tail scores to whole-test proportions for represented true classes and uses the same class set for whole-test scores.Figure 10 orders models within each dataset as MLP, GCN, GraphSAGE-mean, H2GCN-2, GPR-GNN, ACM-GCN, and LINKX.
  • I RQ2: Tail and Non-Tail Performance Across Retraining Procedures: RQ2 measures tail macro-F1 changes after last-layer, head, or full-model retraining relative to AERM, and reports recovered shares for last-layer and head refitting.The corresponding tables provide means with 95% percentile-bootstrap intervals; grey cells contain zero or fail the stated recovery criteria.
  • I.1 RQ2: Sensitivity to Retraining Approach: Sensitivity ablations replace GroupDRO balanced retraining with DFR-style Final-Layer retraining and FG-CCDB balanced training.These ablations test whether RQ2 findings depend on the retraining approach.

I.1.1 DFR-style Last layer Retraining · I.1.2 RQ2: FG-CCDB Retraining

Sensitivity analyses show that DFR-style last-layer retraining remains competitive while preserving the main GroupDRO conclusions, whereas FG-CCDB retraining underperforms GroupDRO across all tested models and procedures.

  • I.1.1 DFR-style Last layer Retraining: DFR-style retraining froze ERM features, standardised them, and fitted an L1-regularised multinomial logistic regression to balanced samples across class and fixed local-homophily bins.The analysis used 30 matched split–seed runs per model on PubMed.
  • I.1.1 DFR-style Last layer Retraining: Table 16 reports PubMed tail macro-F1 for ERM, three registered retraining procedures, and the DFR-style frozen-representation refit over 30 runs with 95% percentile-bootstrap intervals.The table compares the retraining variants using tail macro-F1.
  • I.1.1 DFR-style Last layer Retraining: ADFR improves on the ERM baseline AERM for ACM-GCN, GCN, and GraphSAGE-mean but is not clearly better than the GroupDRO retraining procedures.ADFR exceeds Alast for ACM-GCN and GCN, but not GraphSAGE-mean.
  • I.1.1 DFR-style Last layer Retraining: ADFR scores worse than full model retraining Afull for all three models, yet remains a competitive and computationally cheaper alternative without qualitatively changing the GroupDRO results.This conclusion is based on the limited post-registration sensitivity test.
  • I.1.2 RQ2: FG-CCDB Retraining: FG-CCDB was adapted by treating fixed local-homophily bins as a discrete nuisance variable and assigning sampling weights to eligible training nodes by bin and class.The reweighted cross-entropy batches target the product of the bin and class marginals.
  • I.1.2 RQ2: FG-CCDB Retraining: Across GraphSAGE-mean, GCN, and ACM-GCN, FG-CCDB retraining performs worse than GroupDRO for Alast, Ahead, and Afull.The comparison repeated 30 training runs on PubMed, and the authors conclude FG-CCDB is not a useful alternative to GroupDRO.
  • I.1.2 RQ2: FG-CCDB Retraining: Table 17 compares PubMed tail macro-F1 gains relative to AERM under FG-CCDB and GroupDRO using means over 30 matched split–seed runs.FG-CCDB entries include 95% percentile-bootstrap intervals, with grey intervals containing zero.

J The Effect of Edge Perturbation · K GenAI Usage Statement

The edge-perturbation experiment tests whether changing rare-tail homophily affects classification while preserving node degree, finding that increased homophily improves performance and decreased homophily harms it. The paper also documents AI assistance, author review, and author responsibility for final decisions.

  • J The Effect of Edge Perturbation: The intervention changed rare-tail nodes’ local homophily toward the graph mean while preserving every node’s degree.It used PubMed, ogbn-arxiv, and arxiv-year with ERM checkpoints for GCN and GraphSAGE-mean.
  • J The Effect of Edge Perturbation: Treatment rewiring was compared with matched control rewiring that performed the same number of operations without changing selected nodes’ local homophily.Model parameters and node features remained fixed, and evaluation used test splits from the rare-homophily tail.
  • J The Effect of Edge Perturbation: The experiment evaluated tail macro-F1 across increasing percentages of the rare homophily tail using five graph replicates and 30 fixed ERM checkpoints per model.Shaded bands represent one standard deviation across graph-replicate means.
  • J The Effect of Edge Perturbation: Treatment–control differences were positive when rewiring increased local homophily on PubMed and ogbn-arxiv, but negative when it decreased homophily on arxiv-year.These effects occurred at every non-zero percentage tested.
  • J The Effect of Edge Perturbation: Making the tail more homophilic improved performance, whereas making a homophilic tail more heterophilic harmed performance.The result challenges the notion that rare-homophily nodes are difficult because they are rare in the graph.
  • K GenAI Usage Statement: OpenAI Codex with ChatGPT 5.5 and 5.6 assisted with research critique, code development and review, literature summaries, and manuscript revision.The assistance covered experimental, analysis, and plotting code as well as research questions and protocol.
  • K GenAI Usage Statement: The authors reviewed all AI-assisted material, tested code, checked results and figures against saved outputs, and verified methodological statements against code and cited sources.They made all final methodological and interpretive decisions and accepted full responsibility for the paper and artefacts.
Loading 2608.14823v1…