PaperlayerView exact revision on arXiv

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

arXiv:2302.11640v2cs.LG

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.

    Source: §1 · p. 2, §3.1 · p. 4, §3.2 · p. 5

  • Method

    The authors identify benchmark defects, remove duplicate nodes from affected datasets, propose diverse heterophilous graphs, and evaluate standard and specialized GNNs.

    Source: §3.1 · p. 4, §4 · p. 6, §5.1 · p. 8

  • 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.

    Source: §3.1 · p. 4, §6 · p. 9, §5.2 · p. 9

  • Takeaways & Limitations

    Evaluation progress under heterophily may have been limited to flawed standard datasets, while separating ego- and neighbor-embeddings improves standard baselines.

    Source: §1 · p. 2, §3.1 · p. 4

    The proposed benchmark includes only graphs with 10K-50K nodes to balance statistical significance with the scalability of heterophily-specific models.

    Source: §4 · p. 6

Abstract

from arXiv · show

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.Source: §1 · p. 2
  • Heterophily-specific models have typically been evaluated on the same six graphs first used by Pei et al. (2020).Source: §1 · p. 2
  • The standard heterophilous datasets have low diversity, small size, extreme class imbalance, and duplicate nodes.Source: §1 · p. 2
  • The paper proposes diverse heterophilous graphs from different domains and evaluates both standard and specialized GNNs on them.Source: §1 · p. 2
  • Standard baselines almost always outperform heterophily-specific models, while separating ego- and neighbor-embeddings consistently improves baselines.Source: §1 · p. 2

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.Source: §2 · p. 2

Graph datasets

  • Early GNN studies predominantly used highly homophilous citation, coauthor, co-purchasing, and discussion-network datasets.Source: §2 · p. 2
  • Most heterophily studies use six benchmark graphs: squirrel, chameleon, actor, texas, cornell, and wisconsin.Source: §2 · p. 3

Specialized methods for learning under heterophily

  • Specialized heterophily methods include Geom-GCN, which defines convolution in a latent space formed from unsupervised node embeddings.Source: §2 · p. 3

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.Source: §2 · p. 3

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.Source: §3 · pp. 3–4

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.Source: §3.1 · p. 4
  • 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.Source: §3.1 · p. 4
  • Removing duplicates causes a significant performance drop for many models, especially on chameleon, and changes model rankings across filtered datasets.Source: §3.1 · p. 4
  • FSGNN ranks first on both original datasets but falls to 10th on filtered squirrel and 4th on filtered chameleon.Source: §3.1 · p. 5

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.Source: §3.2 · p. 5

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.Source: §4 · pp. 5–6
  • 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.Source: §4 · p. 6
  • 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.Source: §4 · p. 6
  • The benchmark contains five connected, undirected, simple heterophilous graphs without self-loops.Source: §4 · p. 6
  • 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.Source: §4 · pp. 6–8
  • The datasets cover varied application domains, including Wikipedia text, Amazon products, a synthetic Minesweeper grid, crowdsourcing workers, and question-answering users.Source: §4 · pp. 6–8

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.Source: §5.1 · pp. 8–9

Evaluation

  • Accuracy is reported for roman-empire and amazon-ratings, while ROC AUC is reported for minesweeper, tolokers, and questions.Source: Table 4 · p. 9
  • The comparison uses a wide range of heterophily-specific models and is described as the most extensive comparison of such models in the literature.Source: §5.1 · p. 9

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.Source: §5.2 · p. 9
  • 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.Source: §5.1 · p. 8, §5.2 · p. 9

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.Source: §6 · p. 9
  • 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.Source: §6 · p. 9
  • On the proposed datasets, standard GNNs generally outperform heterophily-specific models.Source: §6 · p. 9

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.

B ADDITIONAL DATASET STATISTICS

Additional statistics describe duplicate distributions in Squirrel and Chameleon and class distributions 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

Dataset domains

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

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.Source: D TWO VERSIONS OF THE SQUIRREL AND… · p. 15

Related papers

Loading 2302.11640v2…