New Benchmarks for Learning on Non-Homophilous Graphs

1 INTRODUCTION

• Homophilous graphs have connected nodes that are much more likely to share a class label than edges independent of labels would predict.In non-homophilous graphs, connected nodes may be no more likely—or may be less likely—to share labels.Source: §1 · p. 1
• Existing non-homophilous datasets are small, narrow in application area, and use synthetic classes, limiting evaluation of methods in these settings.The paper proposes larger datasets spanning wider application areas and complex label-topology relationships.Source: §1 · p. 1
• The paper introduces non-homophilous datasets and a measure of homophily, then benchmarks simple methods, general GNNs, and non-homophilous GNNs.It also reintroduces strong simple graph-learning methods that had been overlooked in recent non-homophilous GNN work.Source: §1 · p. 1

2.1 Graph Representation Learning

• Many GNNs aggregate neighboring features, smoothing representations and predictions across adjacent nodes; common benchmarks’ homophily has also encouraged homophily-based methods.Such smoothing can be a poor fit for non-homophilous graphs [41] [53], while homophily-based methods can perform strongly on homophilic datasets [24] [53].Source: §2.1 · p. 2

2.2 Non-Homophilous Methods

• Low-homophily methods use geometric aggregation (Geom-GCN [44]), mixed adjacency powers (MixHop [2]), signed propagation (GPR-GNN [11]), or separated ego and higher-order information (H2GCN [60]).Recurring design choices include higher-order neighborhoods, separating ego from neighbor information, and combining graph information at multiple scales; topology-based methods also use label propagation or supervised learning [43].Source: §2.2 · p. 2

2.3 Real-world Datasets

• Most node-classification datasets in the Open Graph Benchmark are homophilous, while the widely used non-homophilous datasets from [44] are small.Cornell, Texas, and Wisconsin have 180–250 nodes, and the largest dataset has 7,600; these datasets also show high variance across splits and limit scalability experiments [48] [60]. The paper draws on Peel [43] but adds node features to Pokec and Facebook networks and introduces citation-year tasks.Source: §2.3 · p. 2

2.4 Synthetic Data

• Synthetic non-homophilous data can support controlled model investigations, but this paper focuses on real-world benchmarks with diverse, complex structure.Prior synthetic approaches control homophily through graph-generation modifications [6] [15].Source: §2.4 · p. 2

3.1 Measuring Homophily

• The proposed scalar measure mitigates sensitivity to class count and class imbalance by aggregating positive class-wise deviations from expected homophily.It captures the presence of homophily, but does not distinguish among different non-homophilous relationships.Source: §3.1 · pp. 2–3
• The measure ranks Chameleon above Squirrel and Squirrel above Actor, matching reported model-performance ordering, though other factors may confound this relationship.Edge homophily is approximately the same across these datasets; Figure 1 also illustrates cases where edge homophily depends on class count or imbalance but the proposed measure does not.Source: §3.1 · p. 3, Figure 1 · p. 3

3.2 Proposed Datasets

• Some datasets modify existing data by changing labels or adding features; examples cover explicit-language classification, fraudulent-review labels, 112 binary protein tasks, publication-year labels, and patent grant-time prediction.Source: §3.2 · pp. 3–4

3.3 General Non-homophilous Settings

• The datasets represent non-homophilous relationships found in gender networks, biological structures, web connections, fraud networks, and citation networks.The paper notes that not all examples from these contexts are non-homophilous.Source: §3.3 · p. 4

4.1 Experimental Setup

• The benchmark includes graph-agnostic and node-feature-agnostic baselines, simple methods, general GNNs, and three methods proposed for non-homophilous settings, using five random 50/25/25 train/val/test splits except ogbn-proteins.Classification accuracy is used for other datasets; ROC-AUC is used for Twitch-DE, YelpChi, and ogbn-proteins, which uses the original Open Graph Benchmark splits.Source: §4.1 · pp. 4–5

4.2 Experimental Results

• Feature-only and topology-only methods beat random, performance is more stable than on Pei et al. datasets [44], and non-homophilous GNNs usually do well, though not everywhere.Table 2 reports test accuracy for most datasets and ROC-AUC for Twitch-DE, YelpChi, and ogbn-proteins.Source: Table 2 · p. 5, §4.2 · p. 5
• Two-hop modifications often improve low-homophily performance, LINK performs well without node features, and 1-hop label propagation's ogbn-proteins result may reflect implementation nuance.Source: §4.2 · p. 5
• Larger datasets make the tradeoff between scalability and learning performance starker, with some methods facing memory issues.This matters because many scalable graph-learning methods rely on homophily assumptions and can face issues in non-homophilous settings.Source: §4.2 · p. 5

• The paper introduces a homophily measure, proposes non-homophilous graph datasets, and benchmarks simple baselines and representative graph-learning methods across them.Source: §5 · p. 5
• The authors hope these contributions will provide better tools for testing non-homophilous graph-learning models and evaluating new techniques.Source: §5 · p. 5
• The benchmark covers transductive node classification; the datasets could be adapted to link prediction, clustering, and some inductive node-classification tasks.The paper also identifies reformulating homophily for other settings and broadening application coverage as future directions.Source: §5 · p. 5

• Each compatibility-matrix entry measures the proportion of edges from one node class that connect to another, capturing label-topology detail beyond a scalar metric.Source: A COMPATIBILITY MATRICES AND STATISTICS · p. 7
• arXiv-year and snap-patents have mostly lower-triangular matrices, consistent with citations primarily pointing to past work.Source: A COMPATIBILITY MATRICES AND STATISTICS · p. 7
• Penn94 is mostly uniform, while Twitch-DE and Pokec show distinct class-connection preferences despite overall non-homophilous structure.In Twitch-DE, both explicit-content and non-explicit-content streamers often connect to explicit-content streamers; in Pokec, one gender shows some preference for friends of another gender.Source: A COMPATIBILITY MATRICES AND STATISTICS · p. 7

• Table 3 reports statistics for homophilic graph datasets, with #C denoting the number of node classes.Source: Table 3 · p. 7
• Cora, CiteSeer, PubMed, ogbn-arxiv, and ogbn-products are highly homophilous, with diagonally dominant compatibility matrices and high edge homophily and h-hat.Source: §A.1 · p. 7
• The OEIS graph remains homophilous across different numbers of time-period classes, unlike the temporal citation patterns of academic papers and patents.Related sequence entries are often posted rapidly and cite one another.Source: §A.1 · p. 7

• The six datasets from Pei et al. [44] are commonly used to evaluate graph representation learning methods in non-homophilous regimes.Their basic statistics are listed in Table 4, with compatibility matrices in Figure 5.Source: §A.2 · p. 7
• The proposed collection includes many more datasets, including 100 Facebook100 graphs, with up to orders of magnitude more nodes and edges across a wider range of contexts.Source: §A.2 · p. 7
• Class imbalance in these datasets may make edge homophily misleading; the proposed measure can help distinguish Chameleon, Actor, and Squirrel despite similar edge homophily.Source: §A.2 · p. 7

• The experiment generates label-independent Erdős-Rényi graphs with two classes, 100 nodes, and edge probability .25, using 100 samples.Source: §A.3 · p. 7
• Figure 2 displays compatibility matrices for two of the 112 ogbn-proteins tasks among datasets with varied non-homophilous structures.Source: Figure 2 · p. 8
• As the majority class grows, the proposed measure stays near zero while edge homophily increases.Source: §A.3 · p. 8

• The default optimizer is AdamW with weight decay .001 and learning rate .01, using full-batch gradient descent; most methods use grid-search tuning.Source: B EXPERIMENTAL DETAILS · p. 8
• Graphs are treated as undirected except arXiv-year and snap-patents, though label propagation and C&S use undirected graphs for those datasets.Source: B EXPERIMENTAL DETAILS · p. 8
• Simple methods ran on an Nvidia 2080 Ti with 11 GB memory, with some experiments moved to a Titan RTX with 24 GB when needed.Table 2 marks cases where memory remained insufficient.Source: B EXPERIMENTAL DETAILS · pp. 8–9
• On class-imbalanced random graphs with label-independent edges, the proposed measure is mostly constant as edge homophily increases.Figure 3 shades three standard deviations.Source: Figure 3 · p. 9

B.1 Hyperparameters

• Hyperparameters were selected for highest validation performance, using grids intended to cover reasonable regimes rather than guarantee optimal performance.The default GNN setup uses dropout .5 and BatchNorm in each layer unless otherwise stated.Source: §B.1 · p. 9
• The grids vary architecture and propagation settings across methods, including GCN/GAT dimensions and heads, APPNP propagation depth, and MixHop adjacency powers.The GCN and GAT grids also cover learning rates; H2GCN varies depth and dropout.Source: §B.1 · p. 9

VERSION NOTES

• The July 2021 version added batch normalization to the APPNP and GPR-GNN grids because it sometimes affects performance, especially on larger graphs.Source: VERSION NOTES · p. 9
• The compatibility-matrix captions identify diagonal dominance in homophilic datasets and note that Cornell class 1 has no outgoing edges; “film” is also called “Actor.”Source: Figure 4 · p. 10, Figure 5 · p. 10