Source-linked AI summary
A critical look at the evaluation of GNNs under heterophily: Are we really making progress?
Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, Liudmila Prokhorenkova
TL;DR
The paper asks whether specialized GNNs are genuinely needed for heterophilous graphs, given weaknesses in the benchmarks used to evaluate them. It identifies duplicate-node leakage, constructs a more diverse benchmark, and finds that standard GNNs generally outperform specialized models on it.
Problem
The paper examines the belief that standard GNNs perform poorly under heterophily and the reliability of the standard datasets used to support specialized models.
Method
The authors identify benchmark defects, remove duplicate nodes from affected datasets, propose diverse heterophilous graphs, and evaluate standard and specialized GNNs.
Results
Standard GNNs generally outperform specialized models on the proposed benchmark, while removing duplicate nodes strongly changes performance and model rankings on squirrel and chameleon.
Takeaways & Limitations
Evaluation progress under heterophily may have been limited to flawed standard datasets, while separating ego- and neighbor-embeddings improves standard baselines.
Takeaways & Limitations
The proposed benchmark includes only graphs with 10K-50K nodes to balance statistical significance with the scalability of heterophily-specific models.
Abstract
from arXiv · showhide
Node classification is a classical graph machine learning task on which Graph Neural Networks (GNNs) have recently achieved strong results. However, it is often believed that standard GNNs only work well for homophilous graphs, i.e., graphs where edges tend to connect nodes of the same class. Graphs without this property are called heterophilous, and it is typically assumed that specialized methods are required to achieve strong performance on such graphs. In this work, we challenge this assumption. First, we show that the standard datasets used for evaluating heterophily-specific models have serious drawbacks, making results obtained by using them unreliable. The most significant of these drawbacks is the presence of a large number of duplicate nodes in the datasets Squirrel and Chameleon, which leads to train-test data leakage. We show that removing duplicate nodes strongly affects GNN performance on these datasets. Then, we propose a set of heterophilous graphs of varying properties that we believe can serve as a better benchmark for evaluating the performance of GNNs under heterophily. We show that standard GNNs achieve strong results on these heterophilous graphs, almost always outperforming specialized models. Our datasets and the code for reproducing our experiments are available at https://github.com/yandex-research/heterophilous-graphs
1 INTRODUCTION
The paper challenges the assumption that heterophily requires specialized GNNs by questioning standard evaluations and testing diverse benchmarks. It reports that standard baselines almost always outperform heterophily-specific models on the proposed datasets.
- Standard GNNs are widely considered unsuitable for heterophilous graphs because earlier evaluations focused mainly on homophilous graphs.
- Heterophily-specific models have typically been evaluated on the same six graphs first used by Pei et al. (2020).
- The standard heterophilous datasets have low diversity, small size, extreme class imbalance, and duplicate nodes.
- The paper proposes diverse heterophilous graphs from different domains and evaluates both standard and specialized GNNs on them.
- Standard baselines almost always outperform heterophily-specific models, while separating ego- and neighbor-embeddings consistently improves baselines.
2 RELATED WORK
Related work distinguishes homophily measures, established graph benchmarks, and specialized approaches for heterophily. It also documents emerging evidence that standard GNNs can perform strongly on some heterophilous graphs.
- Measuring homophily: Edge homophily is the fraction of edges connecting nodes with the same class, whereas node homophily averages each node’s proportion of same-class neighbors.
- Graph datasets: Early GNN studies predominantly used highly homophilous citation, coauthor, co-purchasing, and discussion-network datasets.
- Graph datasets: Most heterophily studies use six benchmark graphs: squirrel, chameleon, actor, texas, cornell, and wisconsin.
- Specialized methods for learning under heterophily: Specialized heterophily methods include Geom-GCN, which defines convolution in a latent space formed from unsupervised node embeddings.
- Performance of standard GNNs under heterophily: Recent work reports strong standard-GNN results on some heterophilous graphs, but primarily on synthetic or semi-synthetic datasets.
3 ISSUES WITH POPULAR HETEROPHILOUS DATASETS
The popular heterophily benchmark has limited source diversity, duplicated Wikipedia nodes that leak labels across splits, and small, imbalanced WebKB datasets. Filtering duplicates substantially changes model performance and rankings.
- Benchmark coverage: The six popular datasets come from only three sources and therefore do not cover the diversity of heterophilous patterns in real data.
- Squirrel and Chameleon: Squirrel and chameleon contain groups of nodes with identical regression targets and neighborhoods, creating train-test leakage when duplicates span data splits.Squirrel includes a group of 48 such nodes, while chameleon includes a group of 92.
- Squirrel and Chameleon: The duplicate structure is unusual because duplicate nodes may differ in features, have outgoing edges only, and often correspond to one node with additional incoming edges.
- Squirrel and Chameleon: Removing duplicates causes a significant performance drop for many models, especially on chameleon, and changes model rankings across filtered datasets.
- Squirrel and Chameleon: FSGNN ranks first on both original datasets but falls to 10th on filtered squirrel and 4th on filtered chameleon.
- Cornell, Texas, Wisconsin: Cornell, texas, and wisconsin contain only 183-251 nodes and 295-499 edges, with high variance and severe class imbalance.Texas has a class containing only one node, making that class unsuitable for meaningful training and evaluation.
4 NEW HETEROPHILOUS DATASETS
The paper constructs five diverse heterophilous datasets and reports graph statistics to support their use as benchmarks. The datasets span different domains and structural properties, with adjusted homophily emphasized for evaluating heterophily.
- The datasets are designed to be heterophilous, structurally diverse, graph-informative, and large enough for statistically significant evaluation.
- Adjusted homophily is emphasized because edge homophily is not meaningful for datasets with unbalanced classes.Adjusted homophily supports comparisons across datasets with different class counts and class-size balance.
- Label informativeness measures how much a neighbor’s label gives information about the node’s label and is reported alongside homophily.The measure is defined using mutual information between labels at the endpoints of a uniformly sampled edge, normalized by label entropy.
- The benchmark contains five connected, undirected, simple heterophilous graphs without self-loops.
- The five datasets vary substantially in graph structure: Tolokers is densest, Roman-empire is sparsest and most chainlike, and Questions has the smallest clustering coefficients.Tolokers has average degree 88.28; Roman-empire has average degree 2.9, diameter 6824, and adjusted homophily −0.05; Questions has 48.9K nodes, average degree 6.28, and adjusted homophily 0.02.
- The datasets cover varied application domains, including Wikipedia text, Amazon products, a synthetic Minesweeper grid, crowdsourcing workers, and question-answering users.
5 BENCHMARKING EXISTING ALGORITHMS
The benchmark compares graph-agnostic, standard GNN, and heterophily-specific models on proposed datasets, finding that standard baselines generally perform best. Separating ego- and neighbor-embeddings is especially helpful among standard GNNs.
- Baselines: The benchmark includes graph-agnostic ResNet variants, classic GCN and GraphSAGE, attention-based GAT and Graph Transformer models, and ego-neighbor separation variants.The study also evaluates eight heterophily-specific models using their official implementations.
- Evaluation: Accuracy is reported for roman-empire and amazon-ratings, while ROC AUC is reported for minesweeper, tolokers, and questions.
- Evaluation: The comparison uses a wide range of heterophily-specific models and is described as the most extensive comparison of such models in the literature.
- Results: Among 15 top-3 performances across five datasets, 13 belong to standard GNNs, which almost always outperform heterophily-specific models.Some specialized models perform worse than the graph-agnostic ResNet baseline; FSGNN is the only specialized model consistently achieving strong performance.
- Results: The best standard-GNN results almost always come from models separating ego- and neighbor-embeddings, including GraphSAGE, GAT-sep, and GT-sep.GAT-sep and GT-sep typically outperform their versions without embedding separation.
6 CONCLUSION
The paper identifies serious problems in commonly used heterophily benchmarks, especially duplicate nodes causing train-test leakage in Squirrel and Chameleon. It proposes diverse replacement datasets and finds that standard GNNs generally outperform specialized models.
- Duplicate nodes in Squirrel and Chameleon create train-test data leakage, and removing them drastically changes the relative performance of different models.
- The proposed benchmark contains heterophilous datasets with different natures and diverse structural properties.The datasets are intended to form a better benchmark for evaluating models under heterophily.
- On the proposed datasets, standard GNNs generally outperform heterophily-specific models.
A TRAINING DETAILS AND HYPERPARAMETERS SELECTION
Training uses repeated splits tailored to existing and proposed datasets, with mean performance and standard deviation reported across runs. Baselines receive architectural augmentations, while specialized models undergo model-specific hyperparameter searches.
- Squirrel and Chameleon use 10 existing train/validation/test splits, while filtered versions reuse those splits after duplicate removal.
- Each proposed dataset uses 10 random 50%/25%/25% train/validation/test splits, with each model trained once per split.Mean performance and standard deviation are reported.
- Squirrel and Chameleon are treated as directed, whereas all proposed benchmark graphs are undirected.
- Baseline GNNs add two-layer MLPs, skip connections, and layer normalization after neighborhood aggregation layers.The authors found these additions important for strong baseline performance and robustness to hyperparameter selection.
- Heterophily-specific models use official author code and model-specific hyperparameter grids because learning rate and weight decay substantially affect performance.Optimal hyperparameter ranges differ drastically across models.
B ADDITIONAL DATASET STATISTICS
Additional statistics describe duplicate distributions in Squirrel and Chameleon and class distributions in the Texas, Cornell, and Wisconsin datasets.
- Squirrel and Chameleon contain many duplicate nodes across all classes, but duplicate distributions are uneven between classes.
- Table 6 reports how nodes are distributed across classes in the Texas, Cornell, and Wisconsin datasets.
C COMPARISON TO THE BENCHMARK PROPOSED IN LIM ET AL. (2021)
The proposed benchmark differs from Lim et al. (2021) in graph size and dataset domains. Its smaller, diverse graphs enable comparison with many heterophily-specific GNNs while complementing Lim et al.’s large-scale benchmark.
- Graph size: Lim et al. (2021) collect large heterophilous graphs to evaluate scalable graph methods, whereas the proposed benchmark uses graphs with fewer than 50K nodes.The smaller size permits comparisons with compute- and memory-intensive heterophily-specific GNNs.
- Dataset domains: The proposed benchmark covers domains different from Lim et al. (2021), whose datasets include social, citation, and web graphs.The authors present their datasets as complementary because comprehensive graph benchmarks should span varied domains.
- Dataset domains: The proposed datasets are diverse heterophilous graphs collected from different domains and structural settings.This diversity is the stated motivation for using them as a better benchmark.
D TWO VERSIONS OF THE SQUIRREL AND CHAMELEON DATASETS
Squirrel and chameleon exist in two dataset versions with different edge sets, while their regression targets are the same up to a logarithmic transform. The paper’s duplicate-edge observations apply only to the SNAP version used by Pei et al. (2020).
- Dataset versions: Squirrel and chameleon have an authors’ version and a SNAP Datasets version, which differ in their edge sets.Pei et al. (2020) used the SNAP version, which became standard in the literature.
- Dataset versions: The paper’s observations about edges of duplicate nodes apply only to the SNAP version.This scope follows from the version used in the paper’s experiments.
- Regression targets: Regression targets are the same in both versions up to a logarithmic transform, so duplicated targets occur in both.The edge-set difference does not remove the duplicated-target issue.