Homophily, Heterophily and When Structure Helps

Two numbers from the same benchmark suite. On roman-empire, a residual MLP that never looks at an edge reaches 65.88 percent accuracy, and a graph attention network with separated self-features reaches 88.75 percent. On amazon-ratings, the same MLP reaches 45.90 percent and the best graph model 52.70 percent (Platonov et al., 2023, A critical look at the evaluation of GNNs under heterophily, ICLR, figures from the authors' results notebook). Twenty-three points of structure in one case, seven in the other. Before choosing an architecture, the question worth answering is which situation you are in.

The vocabulary for this question is homophily, and most of the trouble in the literature comes from treating one crude version of it as the answer.

Three measures, three different claims

Edge homophily is the fraction of edges joining two nodes with the same label:

Node homophily averages the same fraction per node instead of per edge, which reweights low-degree nodes upward (Pei et al., 2020, Geom-GCN, ICLR). Both are uncomparable across datasets, because both are inflated by class imbalance: a graph with 90 percent of nodes in one class scores high on edge homophily under random wiring. Adjusted homophily corrects for that by subtracting the value expected from the degree-weighted class distribution, so zero means "no better than chance" (Platonov et al., 2023, Characterizing Graph Datasets for Node Classification, NeurIPS).

The gap this opens is large. The questions dataset has edge homophily 0.84, which reads as strongly homophilous, and adjusted homophily 0.02, which reads as structurally uninformative about labels. minesweeper scores 0.68 and 0.01 on the same pair. Both numbers are correct; only the second is comparable.

The same paper adds label informativeness, which asks how many bits a neighbour's label carries about a node's label. It tracks measured GNN performance better than any homophily score does, which is the property you actually wanted from the measure.

Why heterophily is not the thing that hurts

The intuitive story is that message passing averages neighbours, averaging neighbours is a denoiser when they share your label, and under heterophily the average mixes classes and destroys the signal. The first two clauses are right and the third is too strong.

What a linear convolution needs is not label agreement but distinguishable and consistent neighbourhood distributions. If every node of class A has neighbours drawn 80 percent from class B, and every node of class B has neighbours drawn 80 percent from class C, aggregation separates A from B perfectly well while edge homophily sits near zero. This is the central result of Ma et al., 2022, Is Homophily a Necessity for Graph Neural Networks?, ICLR: a plain GCN beats several heterophily-specific designs on some of the standard heterophilous graphs, and the conditions under which it does are characterisable.

The theory on the generative side agrees. For a two-class Gaussian mixture whose nodes are wired by a stochastic block model, one round of graph convolution extends the regime in which the classes are linearly separable by roughly a factor \(1/\sqrt{D}\), where \(D\) is the expected degree, provided the graph is not too sparse and the ratio \((p-q)/(p+q)\) is bounded away from zero (Baranwal et al., 2021, Graph Convolution for Semi-Supervised Classification, ICML). What breaks the benefit in that model is not \(q > p\), it is \(p \approx q\): edges that carry no class information at all. Heterophily with structure is usable. Noise is not.

minesweeper is the clean illustration. The graph 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 hold mines, hidden for a random half of the nodes. Mines are placed independently, so adjusted homophily and label informativeness are both approximately zero. Yet the graph-agnostic baseline sits at 50.89 ROC-AUC, essentially chance, and a graph attention model reaches 93.91. The structure is indispensable and the labels of neighbours are irrelevant: what propagates usefully is neighbours' features. Label-based homophily measures cannot see that channel.

When it breaks

The canonical heterophilous benchmarks were leaking. In squirrel, 2,978 of 5,201 nodes are duplicates, and in chameleon, 1,387 of 2,277. GraphSAGE scores 51.69 on duplicated squirrel nodes against 34.67 on the rest, which is the signature of a model matching test neighbourhoods to training ones rather than learning (figures from the arXiv version of Platonov et al.; the earlier conference-review version reports slightly different counts). A decade of architectures was ranked on these splits.

Specialised designs mostly did not survive de-biased evaluation. Once standard models are given skip connections, layer normalisation and separate treatment of a node's own features, they "almost always outperform specialized models" on the newer benchmarks, in the authors' own summary. Treat any heterophily-specific architecture as needing to beat a well-tuned GAT with self-feature separation, not a plain two-layer GCN.

One number per dataset hides the variation inside it. Homophily is a global average, and real graphs mix neighbourhoods that are strongly homophilous with neighbourhoods that are not. Per-node measures are what justify node-adaptive designs such as the aggregation, diversification and identity channels of Luan et al., 2022, Revisiting Heterophily for Graph Neural Networks, NeurIPS.

The honest baseline is cheap and often omitted. Train the same MLP on node features with no edges, under the same tuning budget. The difference is your measurement of what the graph is worth, and sometimes it is close to zero.