PaperlayerView exact revision on arXiv

Source-linked AI summary

Neural Sheaf Diffusion: A Topological Perspective on Heterophily and Oversmoothing in GNNs

Cristian Bodnar, Francesco Di Giovanni, Benjamin Paul Chamberlain, Pietro Liò, Michael M. Bronstein

arXiv:2202.04579v4cs.LGmath.AT

TL;DR

GNNs’ heterophily and oversmoothing problems are examined as consequences of assuming a trivial graph geometry, leaving open how richer geometries affect diffusion and asymptotic representations. The paper uses cellular sheaf theory to analyze increasingly general sheaf diffusions, prove greater asymptotic control for non-trivial sheaves, and learn sheaves from data. It connects graph representation learning with algebraic topology and reports competitive results in heterophilic settings.

  • Problem

    The paper asks how a graph’s underlying geometry relates to GNN performance on heterophilic graphs and to oversmoothing, problems associated with typical trivial-sheaf assumptions.

  • Method

    The paper applies cellular sheaf theory to sheaf-Laplacian diffusion, studies increasingly general sheaves and their harmonic spaces, and learns sheaves end-to-end for graph models.

  • Results

    The analysis shows that richer sheaves expand infinite-time linear-separation capability, while non-trivial sheaf diffusion has greater asymptotic control than GCNs and achieves competitive heterophilic results.

  • Takeaways & Limitations

    Graph models can evolve both node features and the graph’s underlying geometry, providing a topological framework for addressing heterophily and oversmoothing.

  • Takeaways & Limitations

    The theoretical analysis does not address the generalisation properties of sheaves.

Abstract

from arXiv · show

Cellular sheaves equip graphs with a "geometrical" structure by assigning vector spaces and linear maps to nodes and edges. Graph Neural Networks (GNNs) implicitly assume a graph with a trivial underlying sheaf. This choice is reflected in the structure of the graph Laplacian operator, the properties of the associated diffusion equation, and the characteristics of the convolutional models that discretise this equation. In this paper, we use cellular sheaf theory to show that the underlying geometry of the graph is deeply linked with the performance of GNNs in heterophilic settings and their oversmoothing behaviour. By considering a hierarchy of increasingly general sheaves, we study how the ability of the sheaf diffusion process to achieve linear separation of the classes in the infinite time limit expands. At the same time, we prove that when the sheaf is non-trivial, discretised parametric diffusion processes have greater control than GNNs over their asymptotic behaviour. On the practical side, we study how sheaves can be learned from data. The resulting sheaf diffusion models have many desirable properties that address the limitations of classical graph diffusion equations (and corresponding GNN models) and obtain competitive results in heterophilic settings. Overall, our work provides new connections between GNNs and algebraic topology and would be of interest to both fields.

1 Introduction

The paper links GNNs’ difficulties with heterophily and oversmoothing to the graph’s underlying geometry, formalized through cellular sheaf theory. It analyzes increasingly general sheaves, develops sheaf diffusion and convolutions, and applies learned sheaves to practical GNN models.

  • Motivation: GNNs often perform poorly on heterophilic graphs because many models assume neighboring nodes are similar.The paper also identifies oversmoothing in deeper GNNs, where node features become too smooth to remain useful.
  • Core perspective: The paper argues that heterophily and oversmoothing share a common cause: the graph’s underlying geometry is typically trivial.Cellular sheaves formalize this geometry by associating vector spaces with nodes and edges and linear maps with incident node-edge pairs.
  • Theoretical analysis: Increasingly general sheaves enable sheaf-Laplacian diffusion to solve increasingly complicated node-classification tasks in the infinite-time limit.The analysis uses the harmonic space of the sheaf Laplacian to characterize asymptotic diffusion behavior.
  • Modeling consequences: Non-trivial sheaves give discrete parametric diffusion greater control over asymptotic behavior than GCNs.The resulting Sheaf Convolutional Network generalizes Graph Convolutional Networks.
  • Practical application: The paper learns sheaves from data and uses them to design practical GNN models with competitive results in heterophilic settings.This connects the theoretical sheaf framework to end-to-end graph representation learning.

2 Background

The background introduces cellular sheaves as graph-associated vector spaces and restriction maps, then relates their Laplacians and diffusion equations to standard graph operators and GCNs. Harmonic cochains represent globally consistent edgewise opinions, while heat diffusion explains smoothing behavior.

  • Cellular Sheaves: A cellular sheaf assigns a vector space to every graph node and edge, plus a linear restriction map for each incident node-edge pair.These associated vector spaces are called stalks, and the maps are called restriction maps.
  • Cellular Sheaves: The 0-cochain space is the direct sum of node stalks, with each cochain assigning a vector to every node.A block-vector representation stacks the node vectors into one global object.
  • Cellular Sheaves: Global sections contain node assignments whose neighboring restrictions agree in the edge discourse space.This models private node opinions that manifest consistently along every edge.
  • Sheaf Laplacians: The normalized sheaf Laplacian is a bounded-spectrum block operator that generalizes the ordinary normalized graph Laplacian.When stalks are R and restriction maps are identities, it recovers the usual graph Laplacian with d = 1.
  • Sheaf Laplacians: Harmonic cochains lie in ker(LF) and are characterized by zero disagreements along all graph edges.The harmonic space is isomorphic to the space of global sections H0(G; F).
  • Cellular Sheaves: Orthogonal restriction maps define discrete O(d) bundles, giving sheaves a geometric interpretation as vector transport over the graph.These structures are discrete analogues of vector bundles from differential geometry.
  • Heat Diffusion and GCNs: Standard heat diffusion updates node features through the normalized graph Laplacian, and GCNs augment this process with learned weights and nonlinearities.Because heat diffusion increasingly smooths neighboring features, this perspective clarifies its connection to heterophily and oversmoothing.

3 The Expressive Power of Sheaf Diffusion

Sheaf diffusion’s infinite-time behavior is governed by the harmonic space of the sheaf Laplacian, whose structure determines whether classes can remain linearly separable. Increasing sheaf generality or stalk dimension expands separation power, including settings where conventional graph Laplacians fail.

  • Harmonic Space of Sheaf Laplacians: Each feature channel converges to a projection in ker(∆F), the signals compatible with the sheaf’s restriction maps.This makes diffusion a synchronization process whose asymptotic representations lie in the sheaf Laplacian’s harmonic space.
  • Harmonic Space of Sheaf Laplacians: For orthogonal sheaves, path-dependent transport is linked to the sheaf Laplacian’s spectral gap, while path-independent transport yields a non-trivial harmonic space.The harmonic-space dimension is at most d and equals d exactly when transport is path-independent.
  • Linear Separation Power: Different sheaf classes produce different diffusion behaviors and separation capabilities, and the paper concludes that node classification can be reduced to diffusion with an appropriate sheaf.The definition of separation power formalizes this criterion for labelled graph families and almost all initial conditions.
  • Linear Separation Power: The symmetric one-dimensional class includes standard positive-weight graph Laplacians but cannot separate the two classes of connected balanced bipartite graphs.Thus, this class retains a limitation under a heterophilic graph structure despite its ability to separate some binary tasks.
  • Linear Separation Power: Non-symmetric invertible one-dimensional sheaves can linearly separate two classes for almost all initial conditions by assigning opposite-signed restrictions across the classes.The resulting path-independent transport polarizes the two classes, providing a sheaf-theoretic explanation for negatively weighted edges in heterophilic settings.
  • Linear Separation Power: One-dimensional sheaves cannot separate three or more classes, whereas diagonal sheaves with d ≥ C and orthogonal sheaves with d ∈ {2, 4} have linear separation power.The results distinguish stalk dimension d from feature-channel count f: sufficient stalk width, rather than more channels alone, is needed for multiclass separation.

4 Expressive Power of Sheaf Convolutions

SCNs extend sheaf diffusion with learnable transformations, giving some non-trivial sheaves greater control over asymptotic representations than GCN-like diffusion. For suitable weighted-map families, convergence to the Laplacian kernel remains restrictive, whereas more general sheaves can escape it.

  • SCN construction: SCNs augment sheaf diffusion with left and right weight matrices plus a nonlinearity, generalising GCNs and recovering them for a trivial sheaf.The left matrix acts on stalk dimensions, while the right matrix adjusts feature channels.
  • Energy and asymptotics: Sheaf Dirichlet energy measures proximity to ker(∆F), with zero energy exactly characterising signals in that kernel.For multiple channels, EF(X) := trace(X⊤∆FX).
  • Energy and asymptotics: For sheaf Laplacians including weighted graph Laplacians, SCNs exponentially converge to ker(∆F) when λ∗∥W1∥2^2∥W⊤2∥2^2 < 1.If the input energy is already zero, the output remains in the kernel regardless of weight norms, limiting separation in the associated settings.
  • Beyond symmetric maps: More general SCNs can increase Dirichlet energy using an arbitrarily small linear transformation and thereby escape the Laplacian kernel.For any connected graph and ε > 0, a suitable W1 with ∥W1∥2 < ε can produce EF((I ⊗W1)x) > EF(x).
  • Beyond symmetric maps: SCNs are generally not constrained to decrease Dirichlet energy under low-norm weights, giving them greater control over asymptotic behaviour than GCNs.This is presented as an expressivity advantage of non-trivial sheaf models over heat-diffusion-based GCNs.

5 Neural Sheaf Diffusion and Sheaf Learning

Neural Sheaf Diffusion learns graph geometry from data and evolves the sheaf during diffusion, while retaining the expressive and theoretical properties of sheaf diffusion. Its parametrisations trade off efficiency, geometric flexibility, and numerical difficulty.

  • Model and learning: Neural Sheaf Diffusion learns the underlying sheaf from data end-to-end, allowing the model to select graph geometry for the task.The time-dependent sheaf is a learnable function of the graph and current features.
  • Model and learning: Setting the model weights to identity and the nonlinearity to identity or a suitable scaled ELU recovers the sheaf diffusion equation up to scaling.Thus the neural model is at least as expressive as the underlying sheaf diffusion process.
  • Model and learning: Unlike the earlier SCN, Neural Sheaf Diffusion learns the sheaf, supports stalk dimensions d ≥ 1 and higher-dimensional maps, and uses residual discretisation.These choices remove reliance on a hand-crafted one-dimensional sheaf built for a synthetic setting.
  • Sheaf parametrisations: Each restriction map is learned from locally available endpoint features through a parametric matrix-valued function Φ(xv, xu).The function must be non-symmetric to represent asymmetric transport maps; with sufficient capacity and diverse features, it can learn any sheaf.
  • Sheaf parametrisations: Diagonal maps reduce parameters and sparse-multiplication cost, orthogonal maps mix stalk dimensions while constraining overfitting, and general maps maximise flexibility but complicate normalisation.For equal representation size, diagonal maps have complexity O(nc^2 + mdc), while orthogonal or general maps have complexity O(n(c^2 + d^3) + m(cd^2 + d^3)).

6 Experiments

Synthetic and real-world experiments show that learned non-trivial sheaves can avoid the limitations of symmetric graph diffusion. Neural Sheaf Diffusion performs strongly across heterophilic and homophilic datasets, with O(d)-bundle diffusion best overall.

  • Synthetic experiments: On a bipartite synthetic task, symmetric-map diffusion cannot perfectly fit the data, whereas general sheaf diffusion improves as time increases toward the harmonic space.At zero diffusion time, a linear classifier cannot separate the classes.
  • Synthetic experiments: The learned scalar transport maps are negative on all edges, inverting the two classes' features and avoiding oversmoothing.The figure compares train and test accuracy over diffusion time with a histogram of learned transport maps.
  • Real-world experiments: Across six highly heterophilic benchmarks, the proposed models rank first on 5/6 and second on the remaining benchmark, Chameleon.The evaluation spans datasets with homophily coefficients from h = 0.11 to h = 0.81.
  • Real-world experiments: NSD remains within approximately 1% of the top model on homophilic graphs and ranks among the top three models on 8/9 datasets.The O(d)-bundle diffusion model performs best overall, while diagonal-map models also perform strongly.

7 Related Work, Discussion, and Conclusion

The paper connects GNN heterophily and oversmoothing to graph geometry through cellular sheaves, extending theoretical analysis and proposing learnable sheaf-based models. It concludes that jointly evolving features and graph geometry achieves competitive heterophilic performance, while generalisation remains unaddressed.

  • Sheaf Neural Networks & Sheaf Learning: The paper studies learning sheaves end-to-end, using a graph-size-independent parametrisation rather than directly minimising a regularised matrix-space energy.This distinguishes the approach from prior work that learns a sheaf Laplacian directly in matrix space.
  • Heterophily and Oversmoothing: Cellular sheaf theory provides a new language and mathematical toolkit for analysing heterophily and oversmoothing in GNNs.The paper contrasts its non-probabilistic diffusion-PDE analysis with prior analyses of linear SGCs on random attributed graphs.
  • Message Passing Neural Networks: Sheaf-based message-passing layers resemble GNN-FiLM and algorithmically resemble GAT while learning feature-conditioned linear transformations.These connections place the proposed layers among architectures studied for heterophilic graphs.
  • Limitations and societal impact: The theoretical analysis does not address the generalisation properties of sheaves, which the authors identify as a major limitation.The authors describe their setting as sufficient for insights into what sheaf types can and cannot do, but state that substantial work remains.
  • Conclusion: The proposed paradigm evolves both node features and the graph's underlying geometry, achieving competitive results in heterophilic settings.The conclusion frames this as a practical response to the connection between sheaf structure, heterophily, and oversmoothing.

A Harmonic Space Proofs

These proofs characterize harmonic spaces of discrete orthogonal bundles through transport along paths and cycles. They show how path dependence constrains harmonic dimension and relates transport deviation to the sheaf Laplacian's spectral gap.

  • Spectral gap: The sheaf spectral gap is related to how far transport maps deviate from path independence, as measured by the transport-disagreement parameter.The resulting Cheeger-like bound is described as theoretically informative but of limited practical use.
  • Transport and energy: Choosing a root node and transporting an arbitrary stalk vector along minimal paths constructs candidate signals whose energy is controlled by transport disagreement.Orthogonality preserves norms while the deviation between path transports determines the resulting bound.
  • Cycle constraints: Every harmonic section is transported consistently along paths, and its value at a node lies in the kernel of every based cycle's transport minus identity.Thus cycles impose fixed-point constraints on admissible harmonic signals.
  • Harmonic-space dimension: For a connected discrete O(d) bundle, harmonic-space dimension is at most d and reaches d exactly when transport is path-independent.Path-independent transport lets any basis at one stalk extend to a basis of global harmonic sections.

B Proofs for the Power of Sheaf Diffusion

These proofs establish how increasingly expressive sheaf classes expand infinite-time diffusion's ability to linearly separate node classes. Signed, diagonal, and orthogonal transports provide distinct separation capabilities and limitations.

  • Diffusion limit: Infinite-time sheaf diffusion converges to the orthogonal projection of initial features onto ker(∆F), so harmonic-space structure determines asymptotic representations.The subsequent separation results therefore reduce to characterizing ker(∆F) for selected sheaves.
  • One-dimensional sheaves: In one dimension, symmetric positive sheaf relations can separate certain binary tasks, but signed relations are necessary because positive asymmetric relations are insufficient.A two-node graph with different classes cannot be separated by the positive class, whose harmonic vector is constant.
  • Binary separation: Signed one-dimensional sheaves can separate two classes on any connected graph for almost all initial conditions.The harmonic vector has opposite signs on the two classes, yielding separated limiting features except for a nowhere-dense exceptional set of initial conditions.
  • Multiple classes: One-dimensional sheaves cannot linearly separate three or more classes for any initial conditions.The limiting feature of one class lies in the convex hull of features from other classes.
  • Higher-dimensional sheaves: Diagonal sheaves with stalk dimension d can separate graphs with C classes when d ≥ C, while orthogonal sheaves extend separation to C ≤ 2d classes for d ∈ {2, 4}.Diagonal maps yield independent one-dimensional processes; orthogonal constructions use rotations and higher-dimensional harmonic configurations.
  • Orthogonal constructions: In dimension four, selected orthogonal transports form an eight-matrix group and can linearly separate up to eight classes.The construction relies on matrix representations associated with Cayley-Dickson-type algebras, which exist here in dimensions two and four.

C Energy Flow Proofs

These proofs analyze energy behavior in sheaf convolutional processes and identify when oversmoothing preserves or destroys linear separability. They also show that small feature transformations can increase energy, while signed relations create a ReLU caveat.

  • Energy increase: For any connected graph, an appropriate sheaf and sufficiently small feature transformation can increase the energy of a feature vector.The construction uses a nontrivial sheaf outside the specified symmetric class and a weight matrix with norm below ε.
  • Energy bounds: For orthogonal sheaf transports, the energy analysis relies on transport orthogonality, ReLU Lipschitz continuity, and their combination across a diffusion layer.The proof assembles separate lemmas controlling the relevant terms.
  • Assumptions: The general energy-flow argument extends to weighted graphs, while non-normalised Laplacians require non-singular transports and incur conditioning-dependent bounds.Orthogonality is therefore a sufficient assumption for the stated bound, not the only possible setting.
  • Signed relations: For signed relations, ReLU can fail through counterexamples, although the corresponding result still holds in the deep linear case.The caveat is specific to the nonlinear activation setting rather than the linear architecture.
  • Oversmoothing consequences: If features oversmooth into ker(∆F), the resulting representations cannot linearly separate classes in the settings covered by the corollaries.This connects asymptotic energy collapse with the separation limits established for particular sheaf families.
  • Finite-depth corollaries: On the stated bipartite and multiclass graph families, finite-depth SCNs with zero input energy remain unable to produce linearly separable outputs.The corollaries transfer the infinite-time separation obstructions through the energy-preserving theorem.

D Sheaf Learning Proof

With unique endpoint-feature pairs, an MLP with sufficient capacity can learn any sheaf by representing restriction maps as a smooth function of concatenated node features.

  • An MLP with sufficient capacity can learn any sheaf when every oriented edge has a unique pair of endpoint features.The learned function maps each pair (xv, xu) to its corresponding restriction map.
  • The proof forms a finite set of concatenated endpoint features for all oriented edges.Uniqueness makes the mapping from endpoint-feature pairs to restriction matrices well-defined.
  • Smooth bump functions extend the finite restriction-map assignment to a smooth function over the full feature space.The construction isolates each observed endpoint-feature pair with a neighborhood-specific bump function.

E Additional model details and hyperparameters

The additional model details describe hybrid transport choices, feature-magnitude adjustment, Laplacian normalization, training procedures, and computational costs for diagonal and non-diagonal sheaves.

  • Model design: Hybrid transport maps append fixed low-pass and high-pass components to learned maps as an additional hyperparameter.The fixed diagonal parts contain 1 and −1 entries and are combined with learned transport.
  • Model design: Learning a vector ε ∈[−1, 1]d lets discrete models adjust feature magnitudes across stalk dimensions.This parameter is used across all discrete-model experiments.
  • Normalization: Augmented normalization uses (D + I_nd)^−1/2 to improve numerical stability, especially for SVD when learning general sheaves.This parallels augmented-degree normalization in GCN.
  • Training: Models use fixed maximum epochs, validation-based early stopping, and Weights and Biases hyperparameter optimization.Reported results use the best validation-scoring model configuration and epoch.
  • Complexity: Message passing costs O(mc) for diagonal restriction maps and O(mdc) for non-diagonal maps.The difference follows from elementwise multiplication versus matrix-vector multiplication for each block.
  • Complexity: Learning restriction maps costs O(md^2f) = O(mcd) for diagonal maps under the stated parameterization.The passage contrasts this with the higher-dimensional non-diagonal case.
  • Synthetic comparison: The bundle model has better training and test-time performance than the one-dimensional sheaf in the two-dimensional synthetic experiment.The comparison uses learned sheaves with one-dimensional versus two-dimensional stalks.
  • Complexity: The final complexity is O(nc^2 + mcd) for diagonal maps and O(n(c^2 + d^3) + m(cd^2 + d^3)) for non-diagonal maps.With constant hidden size in the MLP, learning costs reduce to O(nc^2 + mc) and O(n(c^2 + d^3) + m(c + d^3)), respectively.

F Additional Experiments

Additional experiments compare learned sheaf models across synthetic, continuous-model, positional-encoding, and diffusion-visualization settings, including class-separation limits beyond four classes.

  • Synthetic experiments: In the two-dimensional synthetic experiment, the discrete vector bundle outperforms the one-dimensional counterpart but neither matches the ideal sheaf.The graph has three classes, two-dimensional features, and edge homophily 0.2.
  • Continuous models: Continuous sheaf models generally outperform other state-of-the-art continuous PDE-based models, though they underperform the discrete versions overall.The passage attributes the continuous-model constraint to shared weights across integration time and no dropout.
  • Benchmark results: Table 3 reports node-classification results sorted by homophily level, with the top three models ranked and NSD models marked.The table is the comparison source for the continuous-model results.
  • Positional encoding ablation: Positional encodings improve the performance of the continuous models in the ablation study.The analysis links this improvement to making nodes more distinguishable.
  • Diffusion visualization: The diffusion visualizations show class configurations becoming linearly separable in the limit for graphs with three and four classes.The classes are rotated apart by 2π/C in the limiting configuration.
  • Diffusion visualization: Beyond C = 4, linear separability in 2D is not guaranteed, although the classes remain well separated.The paper illustrates the broader case with a ten-class example.
Loading 2202.04579v4…