Neural Sheaf Diffusion: A Topological Perspective on Heterophily and
  Oversmoothing in GNNs
  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
state-of-the-art results in heterophilic settings. Overall, our work provides
new connections between GNNs and algebraic topology and would be of interest to
both fields.
