Re-evaluating the Advancements of Heterophilic Graph Learning: A Three-Way Dataset Taxonomy and Quantitative Evaluation of Homophily Metrics
Synopsis
This work fine-tunes baseline models on 27 widely used benchmark datasets, categorizes heterophilic datasets into malignant, benign, and ambiguous groups based on whether graph-aware models underperform their coupled graph-agnostic counterparts, re-evaluates 11 SOTA heterophily-specific models, and conducts the first quantitative evaluation of 11 homophily metrics on synthetic graphs from three generation methods, finding that most SOTA models do not significantly outperform the best baselines and that classic metrics remain competitive.
Figure 1: Comparison of metrics on synthetic graphs with different generation methods. Note that Hnode overlaps with Hedge in Figure (e) and (f). In Figure (e), Hclass(G) overlaps with Hadj(G). KRL, KRNL and GNB overlaps in Figure (d).
· Page 8Interpretation
Proposes a new taxonomy of heterophilic datasets into malignant, benign, and ambiguous categories, identifying malignant and ambiguous heterophily as the truly challenging tasks. Prior work often judged dataset difficulty by homophily values alone; this work uses whether graph-aware models underperform their coupled graph-agnostic models as the criterion and is the first to propose such a taxonomy. Based on fine-tuned GCN, SGC-1 and their coupled MLP-2, MLP-1 across 27 benchmark datasets, with reported means and standard deviations.
Re-evaluates 11 SOTA heterophily-specific models with fine-tuned hyperparameters, finding that only ACM-GCN*, FSGNN, and GloGNN* have better overall average rankings than the best baselines. Prior literature often reported heterophily-specific models outperforming baselines; under unified fine-tuning and category-wise evaluation, this work reaches a different conclusion and notes that some models sacrifice performance on easy graphs to gain on difficult ones. Average ranking statistics of 11 models covering six method families across 27 datasets, with results worse than the best baselines and out-of-memory (OOM) cases marked.
Conducts the first quantitative evaluation of 11 homophily metrics on synthetic graphs from three generation methods (RG, PA, GenCat), using Pearson correlation and Fréchet distance to measure similarity between metric curves and GNN performance curves. Prior evaluation relied on observational comparison of curve shapes; this work introduces quantitative similarity measures and shows that conclusions depend heavily on the chosen similarity measure and synthetic graph type. Pearson correlation and Fréchet distance computed on RG, PA, and GenCat synthetic graphs with average rankings, reporting performance differences between classic and some new metrics across scenarios.
Shows that hyperparameter fine-tuning significantly affects baseline model performance, with 19 out of 28 cases showing significant improvement from tuning. This finding targets datasets claimed to be robust to hyperparameter values, indicating that reported results may be unreliable without sufficient tuning or a wide enough search range. Comparison of GCN, MLP-2, SGC-1, and MLP-1 with and without tuning on Squirrel-filtered, Chameleon-filtered, roman-empire, amazon-ratings, minesweeper, tolokers, and questions.
Perspective
This work targets model and metric evaluation for heterophilic graph node classification, applicable to researchers using these 27 benchmark datasets or similar synthetic graph generation methods; its taxonomy and evaluation pipeline can guide validation of new models and metrics and suggest drawing conclusions from all three synthetic graph types and multiple similarity measures.
The synergy between graph structure and model nonlinearity in ambiguous heterophilic datasets currently lacks theoretical explanation, which the authors also list as a future direction; moreover, metric rankings depend heavily on the chosen similarity measure and synthetic graph type, so readers should judge specific metric recommendations in light of their own scenarios.