Sheaf Neural Networks and Heterophily
Published:
The Heterophily Problem Revisited
Intuition First: On a heterophilic graph, running GCN is like trying to find your own position on a GPS by averaging all your neighbours’ GPS coordinates — if you live at the boundary between two neighbourhoods, you’ll always end up placed in the wrong one. The sheaf solution is to give each boundary edge a “flip” map, so that crossing the boundary transforms features rather than blending them. The result is like placing a mirror at each class boundary: you see the reflection of the other side, not a blend.
Recall: in a heterophilic graph, nodes tend to connect to nodes of different classes. GCN’s aggregation:
When N(v) contains mostly nodes of different classes, h_v becomes a mixture of other-class features. This is exactly wrong for node classification — h_v should be class-discriminative for v’s own class.
What Happens to Standard GCN on Heterophilic Graphs
- Initial features x_v are (roughly) class-discriminative
- After one GCN layer: h_v = mean of neighbour features = mean of different-class features → h_v moves toward the inter-class centroid
- After more layers: h_v converges further toward the global mean → all nodes become identical → accuracy near random
This is the catastrophic interaction between oversmoothing and heterophily.
The Sheaf Solution: Controlled Diffusion
With a learned sheaf F, the diffusion minimises:
The key degree of freedom: the learned maps F_{v→e} can be chosen such that for an edge between a class-A node v and a class-B node u, F_{v→e} x_v and F_{u→e} x_u are anti-aligned — they point in opposite directions.
In this case, the Sheaf Dirichlet energy is large at cross-class edges for the correct class-discriminative signal — the diffusion does not try to align them. Instead, it converges to the null space of Δ_F, which corresponds to signals that are globally consistent under the sheaf.
If the sheaf is learned optimally for a heterophilic graph, the null space of Δ_F contains class-discriminative signals — and diffusion converges to class separation, not class averaging.
Comparison with Other Heterophily Methods
| Method | Heterophily strategy | Principled? |
|---|---|---|
| GCN | Averaging (fails) | N/A |
| H2GCN | Separate ego/neighbour + multi-hop | Heuristic |
| GPRGNN | Learnable polynomial filter | Spectral |
| FAGCN | Low/high frequency attention | Heuristic |
| NSD (Sheaf) | Learned restriction maps + sheaf diffusion | Principled (topology) |
NSD is the only method with a rigorous mathematical explanation for why it works on heterophilic graphs — not just empirical evidence that it does.
Empirical Results
On standard heterophilic benchmarks (Chameleon, Squirrel, Cornell, Texas):
| Model | Chameleon | Squirrel |
|---|---|---|
| GCN | 59.8% | 53.4% |
| GAT | 60.3% | 54.6% |
| H2GCN | 57.1% | 36.4% |
| NSD (diag) | 71.6% | 56.7% |
| NSD (general) | 76.2% | 61.9% |
NSD with general restriction maps provides the largest improvements on heterophilic benchmarks.
Worked Example: Two-Class Bipartite Graph
Setup: complete bipartite graph K_{2,2} with nodes A₁, A₂ (class 0, features [1,0]) and B₁, B₂ (class 1, features [0,1]). Every edge connects a class-A node to a class-B node.
Standard GCN (2 layers):
- Layer 1: each A node averages its B neighbours → [0,1]; each B node averages its A neighbours → [1,0]
- Layer 2: each A node (now [0,1]) averages B neighbours (now [1,0]) → [0.5, 0.5]
- All nodes collapse to [0.5, 0.5] — classification impossible.
NSD with optimal maps: set F_{A→e} = I, F_{B→e} = [[0,1],[−1,0]] (90° rotation) for every edge.
- “Agreement” at edge (A,B): F_{A→e} x_A = x_A = [1,0]; F_{B→e} x_B = [0,1]·rotation → [1,0]. They agree!
- The global section satisfying all edge conditions is exactly the class-discriminative signal [1,0] for A, [0,1] for B (up to the frame rotation).
- Diffusion converges to this section — class structure is preserved at equilibrium.
Why Sheaves Beat Heuristic Fixes
H2GCN separates the ego node from its neighbours and concatenates multi-hop features. This helps on some heterophilic graphs but is a heuristic — no principled reason why it should work universally.
FAGCN uses signed attention (positive for same-class, negative for different-class). This is closer in spirit to sheaf GNNs, but the signs are a simplified version of the restriction maps (scalar ±1 vs full d×d matrix).
NSD provides a single principled framework that subsumes both: the restriction maps can represent identity (homophily), negation (anti-homophily), or any intermediate transformation.
Summary
Sheaf GNNs address heterophily by replacing the implicit assumption of standard message passing (“neighbours should be equal”) with an explicit learned relationship per edge. This allows the model to represent heterophilic structure — where neighbours should be different in a structured way — directly in the architecture, rather than fighting against an incorrect inductive bias.
References
- Bodnar, C., Giovanni, F. D., Chamberlain, B. P., Liò, P., & Bronstein, M. M. (2022). Neural Sheaf Diffusion: A Topological Perspective on Heterophily and Oversmoothing in GNNs. NeurIPS 2022 (NSD: theoretical analysis of the Sheaf Laplacian null space and why sheaf diffusion avoids the heterophily failure mode of standard GNNs).
- Zhu, M., Ghosh, B., Wang, X., Lu, H., Qiu, J., Cui, P., & Shi, C. (2020). Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs. NeurIPS 2020 (establishes heterophily benchmarks and surveys methods; baseline context for sheaf GNN comparisons).
- Lim, D., Li, X., Hohne, F., & Lim, S.-N. (2021). New Benchmarks for Learning on Non-Homophilous Graphs. arXiv 2021 (heterophily benchmark suite used to evaluate NSD and other heterophily-aware GNNs).