Does the Graph Help? Homophily, Heterophily, and the Baseline Nobody Runs

Five node-classification datasets, released together, evaluated under one protocol. On roman-empire, a residual MLP that never looks at an edge scores 65.88 percent and a graph attention network with separated self-features scores 88.75. On amazon-ratings, the same pair scores 45.90 and 52.70. On minesweeper, the MLP sits at 50.89 ROC-AUC, which is chance, and the graph model reaches 93.91 (Platonov et al., 2023, A critical look at the evaluation of GNNs under heterophily, ICLR; numbers from the authors' released results notebook).

Three datasets, three completely different answers to "how much is the graph worth". None of those answers is predicted by the statistic the literature spent five years optimising against. minesweeper has edge homophily 0.68 and gains 43 points from message passing. questions has edge homophily 0.84, higher, and gains 7.7. The number that was supposed to tell you whether message passing would work does not order these datasets correctly, and for a while nobody noticed because the benchmarks everyone used were leaking.

Why this matters: Choosing a graph architecture by whether the dataset is called homophilous or heterophilous selects for the wrong property. What predicts whether aggregation helps is how much information a neighbour carries about a node, measured against chance, plus whether that information arrives through labels or through features. Both are computable before you train anything, and the decisive comparison is against a graph-free baseline that most published tables omit.

TL;DR

• Raw edge homophily is not comparable across datasets. It is inflated by class imbalance, so a graph wired at random scores high when one class dominates. questions reads 0.84 by this measure and 0.02 once corrected for chance.
• Adjusted homophily subtracts the degree-weighted expectation, and label informativeness measures the bits a neighbour's label carries. The second tracks measured GNN performance better than any homophily score.
• Low label homophily does not break aggregation. What breaks it is neighbourhood label distributions that are identical across classes, or inconsistent within a class. Consistent heterophily is as learnable as homophily.
• Structure can be decisive while neighbours' labels are irrelevant: on minesweeper, label informativeness is approximately zero and message passing is still worth 43 ROC-AUC points, because the useful quantity lives in neighbours' features.
• The canonical heterophilous benchmarks leaked. In squirrel, 2,978 of 5,201 nodes are duplicates; in chameleon, 1,387 of 2,277. GraphSAGE scored 51.69 on duplicated squirrel nodes against 34.67 on the rest.
• Once standard models get skip connections, layer normalisation and separate treatment of a node's own features, they almost always beat the heterophily-specific architectures on de-biased benchmarks.
• Mean aggregation alone can leave the signal-to-noise ratio exactly where it started. Concatenating the self-feature rather than mixing it in adds a channel, which explains most of the gap between GAT and GAT-sep.
• The honest experiment is cheap: train the same features through an MLP under the same tuning budget. The difference is what your graph is worth, and sometimes it rounds to zero.

At a Glance

flowchart LR
    A[Node features X] --> M[Graph-free MLP]
    B[Edge set E] --> D{"Diagnose before training"}
    A --> D
    D --> D1["Adjusted homophily"]
    D --> D2["Label informativeness"]
    D --> D3["Feature-mediated signal"]
    D1 --> C[Choose aggregation]
    D2 --> C
    D3 --> C
    C --> G[Graph model]
    M --> V["Gap = what the edges are worth"]
    G --> V
    classDef blue fill:#1e40af,stroke:#3b82f6,stroke-width:1px,color:#fff
    classDef purple fill:#6d28d9,stroke:#a78bfa,stroke-width:1px,color:#fff
    classDef teal fill:#0e7490,stroke:#22d3ee,stroke-width:1px,color:#fff
    classDef amber fill:#b45309,stroke:#fbbf24,stroke-width:1px,color:#fff
    class A,B blue
    class D,D1,D2,D3,C purple
    class M,G teal
    class V amber

The diagnosis step is the part that usually gets skipped, and the comparison on the right is the part that usually gets skipped twice.

Before Heterophily Was a Research Area

[IMAGE: Mermaid-style side-by-side of two 12-node graphs with identical node features, one wired homophilously and one wired with consistent anti-correlation, each annotated with its edge homophily, adjusted homophily and label informativeness. Caption: "Three measures, two graphs, and only two of the six numbers are comparable across datasets."]

Graph convolution arrived as a semi-supervised method for citation networks, where papers cite papers on the same topic. A two-layer network propagating features over normalised adjacency, scaling linearly in edges, beat the available baselines on Cora, Citeseer and Pubmed (Kipf and Welling, 2017, Semi-Supervised Classification with Graph Convolutional Networks, ICLR). Nothing in that result was wrong, but the datasets shared a property nobody had to name yet: neighbours almost always agreed.

The name arrived with the first architecture designed for graphs where they do not. Geom-GCN defined a homophily index as the average fraction of a node's neighbours sharing its label, reported it for nine datasets, and introduced the WebKB and Wikipedia graphs that became the standard heterophilous suite (Pei et al., 2020, Geom-GCN, ICLR). Within months, H2GCN had isolated three designs that help when the index is low: separating a node's own representation from its neighbours' instead of mixing them, using higher-order neighbourhoods, and combining intermediate layer outputs rather than only the last (Zhu et al., 2020, Beyond Homophily in Graph Neural Networks, NeurIPS).

A subfield formed around that index. Dozens of architectures were proposed, each evaluated on the same six small graphs, each reporting improvements. Two papers from outside the subfield should have slowed it down. One showed that different train-test splits reorder GNN rankings outright, and that simpler architectures win when every model is tuned equally (Shchur et al., 2018, Pitfalls of Graph Neural Network Evaluation). The other re-ran five models on nine graph-classification benchmarks under one controlled protocol, more than 47,000 experiments, and found that on several datasets the models were not using graph structure at all (Errica et al., 2020, A Fair Comparison of Graph Neural Networks for Graph Classification, ICLR).

timeline
    title From assuming homophily to measuring it properly
    2016 : Kipf and Welling publish the GCN; citation networks where neighbours agree
    2019 : GIN fixes the expressivity ceiling at 1-WL with sum aggregation
         : Pitfalls of GNN Evaluation shows splits reorder model rankings
    2020 : Geom-GCN names the homophily index and ships the WebKB and Wikipedia suite
         : H2GCN isolates self-feature separation and higher-order neighbourhoods
    2021 : LINKX builds non-homophilous benchmarks up to 384 times larger
         : GPR-GNN learns propagation weights instead of assuming homophily
    2022 : Is Homophily a Necessity shows plain GCN beating specialised designs
         : ACM-GNN makes channel mixing node-adaptive rather than global
    2023 : Platonov et al. find duplicate-node leakage in squirrel and chameleon
         : Adjusted homophily and label informativeness replace the raw index
    2024 : Long-Range Graph Benchmark gaps close under baseline tuning

The correction came in two parts from the same group. First, the measures: the popular homophily indices cannot be compared across datasets, because they do not account for the number of classes or their sizes, and adjusted homophily does, along with a label informativeness measure that asks how much a neighbour's label actually tells you (Platonov et al., 2023, Characterizing Graph Datasets for Node Classification, NeurIPS). Second, the data: the two most-cited heterophilous datasets contain enough duplicate nodes to leak test labels into training, and five replacement datasets from different domains were released with the paper.

[IMAGE: Two-panel scatter plot. Left panel: measured GNN-minus-MLP accuracy gap on the y-axis against raw edge homophily on the x-axis for the five Platonov datasets, showing no monotone relationship. Right panel: the same gaps against label informativeness, with minesweeper circled as the outlier that neither measure explains. Caption: "The statistic the field optimised against does not order the datasets by how much the graph is worth."]

What Aggregation Actually Does to the Signal

Strip message passing down to one layer of mean aggregation and the question becomes arithmetic. Node \(i\) has a feature \(x_i = \mu_{y_i} + \varepsilon_i\), where \(\mu\) depends on the node's class and \(\varepsilon_i\) is independent noise with variance \(\sigma^2\). The layer replaces \(x_i\) with the mean over its \(D\) neighbours.

The denoiser view, and its exact price

Under homophily, every neighbour has mean \(\mu_{y_i}\), so the aggregate has the same expectation and its noise variance is \(\sigma^2/D\). The class means are untouched and the noise shrinks by the degree. That is the entire original argument for graph convolution, and it is a good one: a node with eight agreeing neighbours effectively gets nine samples of its own class.

Express it as a signal-to-noise ratio, separation squared over variance. Two classes at \(\pm 1\) with noise \(\sigma^2\) start at \(4/\sigma^2\); aggregating four perfectly homophilous neighbours keeps the separation and quarters the variance, giving \(16/\sigma^2\). Better by exactly the degree.

For a two-class Gaussian mixture wired by a stochastic block model, the same calculation done properly gives the field's cleanest theoretical statement: one graph convolution extends the regime in which the classes are linearly separable by a factor of roughly \(1/\sqrt{D}\), provided the graph is not too sparse and the edge noise ratio \((p-q)/(p+q)\) stays bounded away from zero (Baranwal et al., 2021, Graph Convolution for Semi-Supervised Classification, ICML). Read the condition carefully. What must be avoided is not \(q > p\). It is \(p \approx q\).

Heterophily flips the mean; noise destroys it

Suppose every node of class A draws three of its four neighbours from class B, and every node of class B draws three of four from class A. Aggregation maps class A to \(-0.5\) and class B to \(+0.5\). The ordering has flipped and the gap has halved, but the classes remain linearly separable and the layer above can learn the sign. Heterophily is a change of coordinates.

Now suppose instead that every node, whatever its class, draws two neighbours from each class. Aggregation maps every node to \(0\). A feature that was perfectly separable before the layer carries no information after it. Nothing about this case is "heterophilous" in the usual sense: edge homophily is exactly 0.5, higher than the first case. The difference that matters is whether the neighbourhood distribution varies with the class, which is precisely what adjusted homophily and label informativeness measure and what the raw index cannot see.

This is the formal content of the result that plain GCNs beat several purpose-built heterophilous architectures on some standard benchmarks: aggregation needs distinguishable neighbourhood distributions, not agreeing ones (Ma et al., 2022, Is Homophily a Necessity for Graph Neural Networks?, ICLR).

Three measures, and what each one is blind to

Edge homophily counts the fraction of edges joining same-label nodes:

Node homophily averages the same ratio per node, which reweights low-degree nodes upward. Neither is comparable across datasets, because both inherit the class distribution. Adjusted homophily fixes the baseline:

where \(\bar{d}_k\) is the share of all edge endpoints belonging to class \(k\). The subtraction is what makes zero mean "no better than random wiring" and allows negative values, which signal systematic anti-correlation. Label informativeness goes further and treats the endpoints of a random edge as random variables, reporting the mutual information between a neighbour's label and a node's, normalised by the label entropy. It agrees with measured GNN performance better than homophily does, which is the property you wanted all along.

The channel all three measures miss

Every measure above is a function of labels and edges. None of them looks at features, and that blind spot produces the most instructive row in the benchmark table.

minesweeper is a 100 by 100 grid with eight-neighbour connectivity and mines on 20 percent of cells. Node features one-hot encode how many neighbouring cells contain a mine, and those features are hidden for a random half of the nodes, with a flag marking which. Mines are placed independently, so a neighbour's label tells you nothing about yours: adjusted homophily is 0.01 and label informativeness is 0.00. By any label-based diagnosis, the graph is worthless. In fact a graph-agnostic model cannot beat chance, 50.89 ROC-AUC, while message passing reaches 93.91.

The mechanism is not subtle once stated. A hidden node's label is determined by information sitting in its neighbours' features, and aggregation is the only way to move that information to where the prediction is made. Structure can be essential through the feature channel while being uninformative through the label channel, and the measures the field standardised on see only the second.

[IMAGE: Diagram of a 3x3 patch of the minesweeper grid. Centre cell has its feature masked and label unknown; two diagonal neighbours show one-hot mine-count features. Arrows carry those counts inward, with a caption noting that no neighbour's label is used. Caption: "Label informativeness is zero here and message passing is worth 43 points. The signal travels through features, not labels."]

Seeing It in Motion

The protocol below is what a de-biased comparison looks like. The two steps that the heterophily literature's first wave skipped are the leakage audit and the equally-tuned graph-free baseline.

sequenceDiagram
    participant D as Dataset
    participant A as Leakage audit
    participant S as Split generator
    participant B as MLP baseline
    participant G as Graph model
    participant R as Report
    D->>A: nodes, edges, features, labels
    A->>A: find duplicate neighbourhoods
    A->>D: drop duplicates, rebuild splits
    D->>S: 10 random splits
    S->>B: same features, no edges
    S->>G: features plus edges
    Note over B,G: identical tuning budget, same seeds
    B->>R: accuracy, mean and std
    G->>R: accuracy, mean and std
    R->>R: gap = value of the structure

[IMAGE: Timeline strip showing the evaluation protocol as a pipeline with two highlighted steps, the leakage audit and the equally-tuned graph-free baseline, marked as "added after 2023". Caption: "The two steps the first wave of heterophily papers did not run."]

Architecturally, the designs that survived de-biased evaluation differ in one decision: what happens to a node's own representation.

flowchart TB
    subgraph Mixed["Self-feature mixed in"]
      M1[Node state] --> M2["Mean over neighbours including self"]
      M2 --> M3["One channel, halved separation"]
    end
    subgraph Separated["Self-feature separated"]
      S1[Node state] --> S2["Concat: self, neighbour aggregate"]
      S2 --> S3["Two channels, additive signal"]
    end
    subgraph Decoupled["Adjacency as its own input"]
      D1["MLP on features"] --> D3[Combine]
      D2["MLP on adjacency rows"] --> D3
      D3 --> D4["Works when either channel alone suffices"]
    end
    classDef rose fill:#be123c,stroke:#fb7185,stroke-width:1px,color:#fff
    classDef emerald fill:#047857,stroke:#34d399,stroke-width:1px,color:#fff
    classDef slate fill:#334155,stroke:#64748b,stroke-width:1px,color:#e2e8f0
    class M1,M2,M3 rose
    class S1,S2,S3 emerald
    class D1,D2,D3,D4 slate

The middle path is the one that shows up as GAT-sep and GT-sep in the results, and it is worth about eight accuracy points over plain GAT on roman-empire, 88.75 against 80.87. The right-hand path is the LINKX design, which embeds the adjacency matrix and the features through separate MLPs before combining them, built for graphs where propagation is the wrong prior entirely (Lim et al., 2021, Large Scale Learning on Non-Homophilous Graphs, NeurIPS).

Watch It Run

By the Numbers

The five replacement datasets, with the diagnostic measures from the authors' repository and the accuracy gap between a graph-agnostic residual network and the best standard graph model. Accuracy for roman-empire and amazon-ratings; ROC-AUC for minesweeper, tolokers and questions.

[IMAGE: Horizontal dumbbell chart, one row per dataset, with a dot for the graph-free ResNet score and a dot for the best standard GNN, connected by a line whose length is the gap, sorted by gap descending. Caption: "Sorted by what the edges are worth, the five datasets do not line up with any homophily ordering."]

Sources: dataset statistics and all model scores are from the heterophilous-graphs repository accompanying Platonov et al., 2023, means over the authors' ten splits with standard deviations between 0.30 and 1.39 in the original table. The leakage figures quoted elsewhere in this article (2,978 duplicates of 5,201 nodes in squirrel; 1,387 of 2,277 in chameleon; GraphSAGE at 51.69 against 34.67) are from the arXiv version of the same paper; the earlier conference-review version reports slightly different counts, so name your version if you cite them.

Two readings of this table are tempting and wrong. Edge homophily does not predict the gap, since the largest gap belongs to a dataset in the middle of the homophily range; adjusted homophily comes closer and minesweeper breaks it too. What survives is narrower and more useful. Near-zero adjusted homophily with near-zero label informativeness means neighbours' labels are uninformative, and the graph can still be essential if neighbours' features are not.

[IMAGE: Grouped bar chart with one group per dataset, bars for graph-free ResNet, GCN, SAGE and GAT-sep, annotated with the gap in points above each group. Caption: "The same architecture family spans a 7-to-43-point contribution depending on the dataset."]

A Concrete Example

Take eight nodes, two classes, one feature. Classes A and B have four nodes each. Every node has degree four. Each A node connects to three B nodes and one A node; each B node connects to three A nodes and one B node. The feature is \(x = +1\) for A and \(x = -1\) for B, plus independent noise of variance \(\sigma^2\).

Step 1: count the edges. Cross-class edges: four A nodes times three B neighbours gives 12, and the count from the B side agrees. Within-class: each A node has one A neighbour, so 2 A-A edges, and likewise 2 B-B edges. Total 16 edges, of which 4 are same-label.

Step 2: edge homophily. \(h_{\text{edge}} = 4/16 = 0.25\). By the standard reading, strongly heterophilous, the regime in which plain convolution is supposed to fail.

Step 3: adjust for chance. Every node has degree 4, so each class owns 16 of the 32 edge endpoints and \(\bar{d}_A = \bar{d}_B = 0.5\). Then \(\sum_k \bar{d}_k^2 = 0.25 + 0.25 = 0.5\), and

Negative, and large in magnitude. The edges are not uninformative, they are systematically anti-correlated with labels, which is a usable signal rather than an absent one.

Step 4: label informativeness. Treat the ordered endpoints of a uniformly random edge as \((y_u, y_v)\). The joint is \(p(A,B) = p(B,A) = 0.375\) and \(p(A,A) = p(B,B) = 0.125\), with marginals 0.5. In nats,

and dividing by \(H(y) = \ln 2 = 0.693\) gives \(\text{LI} \approx 0.19\). Nineteen percent of the label entropy is visible through one edge.

Step 5: aggregate. Each A node averages three \(-1\)s and one \(+1\): \((-3+1)/4 = -0.5\). Each B node averages three \(+1\)s and one \(-1\): \(+0.5\). The classes have swapped sides and the gap has shrunk from 2 to 1.

Step 6: price the aggregation honestly. Before: separation 2, variance \(\sigma^2\), so the ratio is \(4/\sigma^2\). After: separation 1, variance \(\sigma^2/4\) from averaging four independent noises, so the ratio is \(1/(\sigma^2/4) = 4/\sigma^2\). Identical. One round of mean aggregation on this graph has bought exactly nothing, which no homophily measure would have told you, because the measures describe the graph and this is a property of the graph and the aggregator.

Step 7: separate the self-feature instead of mixing it. Keep \(x_i\) and the neighbour mean as two coordinates. A node's own noise does not appear in its neighbours' mean, so the two channels are independent, and their ratios add: \(4/\sigma^2 + 4/\sigma^2 = 8/\sigma^2\). Double the discriminative power of either channel alone, from a concatenation rather than a sum.

Step 8: break it. Rewire so that every node, in either class, has two A neighbours and two B neighbours. Now \(h_{\text{edge}} = 0.5\), up from 0.25, and \(h_{\text{adj}} = (0.5-0.5)/(1-0.5) = 0\), and \(\text{LI} = 0\). Every node aggregates to \((1+1-1-1)/4 = 0\). The separable feature is gone, and a model that mixes self and neighbours has destroyed information its graph-free counterpart would have kept. This, not heterophily, is the configuration to fear.

Steps 6 and 7 together are the quantitative reason the -sep variants dominate the results table, and the reason H2GCN listed ego-neighbour separation first among its three designs five years ago.

[IMAGE: Eight-node graph drawn twice. Left: the consistent anti-correlated wiring, with aggregated values -0.5 and +0.5 labelled per node. Right: the 50-50 wiring, with every aggregated value 0. Caption: "Edge homophily rises from 0.25 to 0.50 between these graphs. Learnability goes to zero."]

Where It Breaks

Duplicate nodes made a benchmark suite unusable

The filtering rule that cleaned squirrel and chameleon removed nodes with no incoming edges for which another node had the same average monthly traffic and the same set of outgoing edges. More than half the nodes in each dataset met that description. When duplicates land in different splits, a model can answer a test node by matching its neighbourhood to a training node, and the accuracy gap between duplicated and non-duplicated nodes, 51.69 against 34.67 for GraphSAGE on squirrel, is the measurement of how much of the reported score was lookup. Any result ranked on the unfiltered versions needs re-reading, including results that reported improvements.

A global average cannot justify a global architecture

Homophily is reported per dataset and acted on per dataset, but neighbourhoods vary inside a graph. A social network has densely homophilous communities alongside bridge nodes whose neighbours are mostly unlike them. One aggregation rule for both is a compromise, which is the argument for node-adaptive designs that mix an aggregation channel, a diversification channel and an identity channel per node rather than globally (Luan et al., 2022, Revisiting Heterophily for Graph Neural Networks, NeurIPS).

Tuning asymmetry produces most published gaps

When one model is tuned hard and its baselines are inherited from an earlier paper, the comparison measures effort. The Long-Range Graph Benchmark is the cleanest demonstration: the reported advantage of graph transformers over message passing largely disappeared under basic hyperparameter optimisation of the baselines, and one of the benchmark's own metrics turned out to be implemented incorrectly (Tönshoff et al., 2024, Where Did the Gap Go?, TMLR). The same mechanism produced the heterophily subfield's apparent progress, and the same remedy applies: tune the thing you want to beat.

An under-trained MLP makes any graph look valuable

The graph-free baseline is only informative if it is a serious model. Platonov's version is a residual network with skip connections and normalisation, not a two-layer perceptron with default settings, and that matters: on questions it reaches 70.34 ROC-AUC against the best graph model's 78.05. A weaker baseline would have inflated the apparent contribution of the edges on every row of the table.

Transductive numbers do not transfer to inductive deployment

Node-classification benchmarks typically train on a graph that already contains the test nodes and their edges. Production systems usually score nodes that did not exist when the model was fit. The inductive setting is strictly harder, and the ratio between graph and graph-free performance can move substantially when you cross that line, so a transductive gap is not a forecast of the deployed gap.

Alternative Designs

The distillation row deserves a second look, because it reframes the article's question. If a graph-free student can be fitted to a graph-trained teacher and match it on 6 of 7 datasets while improving on a standalone MLP by 12.36 percent on average (Zhao et al., 2022, Graph-less Neural Networks, ICLR), then on those datasets the structure was useful as a training signal and unnecessary at inference. That is a different claim from "the graph does not help", and a much more actionable one for anyone with a latency budget.

How It Is Used in Practice

The five replacement benchmarks were each built from a production-shaped source, and the shapes recur. tolokers is a crowdsourcing platform's worker graph with average degree 88, the kind of dense interaction network fraud and abuse teams actually hold, where aggregation over a large neighbourhood smooths away the individual signal unless the self-feature is kept separate. amazon-ratings is a product co-purchase network, where a bought-together edge means complement as often as substitute. questions is a question-answering site's interaction graph with high raw homophily and near-zero adjusted homophily, which is exactly the trap an unaudited check walks into.

The takeaway is a sequence rather than an architecture. Compute adjusted homophily and label informativeness, one pass over the edges. Audit for duplicate neighbourhoods, a hash per node, which has now twice caught a benchmark that fooled a subfield. Train the graph-free model at the graph model's tuning budget. Then, if the gap justifies it, start from a standard architecture with separated self-features rather than a heterophily-specific design, and ask whether the deployed model needs the graph at inference or only needed it during training.

[IMAGE: Flow diagram of the four-step diagnostic sequence (measure, audit, baseline, choose), with the approximate compute cost annotated on each step and the architecture decision at the end. Caption: "Three of the four steps cost less than one training run."]

Insights Worth Remembering

1. Edge homophily is a baseline-free statistic, which makes it uncomparable. A graph wired at random scores high on it whenever one class dominates. Adjusted homophily subtracts the degree-weighted expectation, so zero means chance and negative means systematically anti-correlated. The gap between the two readings reached 0.82 on one of the five benchmark datasets.
2. Consistency, not agreement, is what aggregation needs. Neighbourhood label distributions that differ by class are learnable whatever their homophily. Distributions identical across classes are not, and that case is invisible to the raw index because it can occur at any homophily level.
3. Mean aggregation can be exactly signal-neutral. Halving the class separation while quartering the variance leaves the signal-to-noise ratio unchanged. The gain from a graph layer is not automatic, and the arithmetic takes two minutes on a specific graph.
4. Separating the self-feature adds a channel; mixing it in spends one. Concatenating a node's own state with its neighbour aggregate doubles the available discriminative power when the two are independent, which is why the -sep variants lead the de-biased results and why H2GCN put this design first.
5. Structure can be decisive while neighbours' labels are useless. minesweeper has label informativeness of 0.00 and a 43-point gap in favour of message passing, because the information the prediction needs lives in neighbours' features. Label-based diagnostics are necessary and not sufficient.
6. Over half the nodes in the two most-cited heterophilous datasets were duplicates. The architectures ranked on them were partly ranked on lookup. A duplicate-neighbourhood audit is a few lines of code and should run before any new benchmark is adopted, not after a hundred papers use it.
7. The decisive experiment is the one most papers omit. Same features, no edges, same tuning budget. If that model is within noise of your graph network, the interesting finding is not your architecture, and reporting it honestly is worth more than another two-tenths of a point.

Open Questions

Can a measure see the feature-mediated channel? Adjusted homophily and label informativeness are functions of labels and edges by construction, and minesweeper shows a second route from structure to prediction that they cannot observe. A measure combining neighbour features with labels would have to say which function of those features counts as informative, and no standard proposal has emerged.

Does the subfield contain a real architectural advance? On de-biased benchmarks, standard models with skip connections, normalisation and self-feature separation almost always outperform the specialised designs. Whether any heterophily-specific component survives equal tuning on datasets nobody has overfit yet is unresolved; what is measured so far is that most claimed gains were evaluation artefacts.

How much of the remaining gap is long-range dependence rather than heterophily? The two are confounded: graphs where neighbours disagree often need information from further away. Separating them needs tasks whose dependence radius is known by construction, and the one widely used attempt at that lost most of its reported effect under baseline tuning.

Does the distillation result generalise? Matching a graph teacher with a graph-free student on 6 of 7 datasets suggests the structure was a training signal rather than an inference-time requirement on those datasets. Whether that holds where the gap is 43 points rather than 8 is untested, and the mechanism that would predict it in advance is not known.

What should a practitioner do when the diagnostics disagree? Both failure directions occur: adjusted homophily near zero with a large measured gap, and clear homophily with none. No decision procedure exists beyond running the comparison, which says the diagnostics are descriptive rather than predictive.

Sources and Further Reading

1. Platonov, O., Kuznedelev, D., Diskin, M., Babenko, A., & Prokhorenkova, L. (2023). "A critical look at the evaluation of GNNs under heterophily: Are we really making progress?" ICLR 2023. arXiv:2302.11640. Datasets, statistics and all baseline scores: github.com/yandex-research/heterophilous-graphs
2. Platonov, O., Kuznedelev, D., Babenko, A., & Prokhorenkova, L. (2023). "Characterizing Graph Datasets for Node Classification: Homophily-Heterophily Dichotomy and Beyond." NeurIPS 2023. arXiv:2209.06177
3. Ma, Y., Liu, X., Shah, N., & Tang, J. (2022). "Is Homophily a Necessity for Graph Neural Networks?" ICLR 2022. arXiv:2106.06134
4. Zhu, J., Yan, Y., Zhao, L., Heimann, M., Akoglu, L., & Koutra, D. (2020). "Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs." NeurIPS 2020. arXiv:2006.11468
5. Pei, H., Wei, B., Chang, K. C.-C., Lei, Y., & Yang, B. (2020). "Geom-GCN: Geometric Graph Convolutional Networks." ICLR 2020. arXiv:2002.05287
6. Lim, D., Hohne, F., Li, X., Huang, S. L., Gupta, V., Bhalerao, O., & Lim, S.-N. (2021). "Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods." NeurIPS 2021. arXiv:2110.14446
7. Luan, S., Hua, C., Lu, Q., Zhu, J., Zhao, M., Zhang, S., Chang, X.-W., & Precup, D. (2022). "Revisiting Heterophily For Graph Neural Networks." NeurIPS 2022. arXiv:2210.07606
8. Chien, E., Peng, J., Li, P., & Milenkovic, O. (2021). "Adaptive Universal Generalized PageRank Graph Neural Network." ICLR 2021. arXiv:2006.07988
9. Baranwal, A., Fountoulakis, K., & Jagannath, A. (2021). "Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization." ICML 2021. arXiv:2102.06966
10. Kipf, T. N., & Welling, M. (2017). "Semi-Supervised Classification with Graph Convolutional Networks." ICLR 2017. arXiv:1609.02907
11. Hamilton, W. L., Ying, R., & Leskovec, J. (2017). "Inductive Representation Learning on Large Graphs." NeurIPS 2017. arXiv:1706.02216
12. Shchur, O., Mumme, M., Bojchevski, A., & Günnemann, S. (2018). "Pitfalls of Graph Neural Network Evaluation." arXiv:1811.05868
13. Errica, F., Podda, M., Bacciu, D., & Micheli, A. (2020). "A Fair Comparison of Graph Neural Networks for Graph Classification." ICLR 2020. arXiv:1912.09893
14. Tönshoff, J., Ritzert, M., Rosenbluth, E., & Grohe, M. (2024). "Where Did the Gap Go? Reassessing the Long-Range Graph Benchmark." TMLR. arXiv:2309.00367
15. Zhao, S., Liu, Y., Sun, Y., & Shah, N. (2022). "Graph-less Neural Networks: Teaching Old MLPs New Tricks via Distillation." ICLR 2022. arXiv:2110.08727
16. Xu, K., Hu, W., Leskovec, J., & Jegelka, S. (2019). "How Powerful are Graph Neural Networks?" ICLR 2019. arXiv:1810.00826
17. Rampášek, L., Galkin, M., Dwivedi, V. P., Luu, A. T., Wolf, G., & Beaini, D. (2022). "Recipe for a General, Powerful, Scalable Graph Transformer." NeurIPS 2022. arXiv:2205.12454

Free to read, no ads, no sign-up. If it was useful you can buy me a coffee.