Neural Sheaf Diffusion: A Topological Perspective on Heterophily and Oversmoothing in GNNs
Authors: Cristian Bodnar
Francesco Di Giovanni
Benjamin Paul Chamberlain
Pietro Lio
Michael M. Bronstein
Venue: NeurIPS 2022 Accept (2022)
Keywords: sheaf
graph
neural network
diffusion
heterophily
oversmoothing
algebraic topology

Abstract: 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.

Neural Sheaf Diffusion: A Topological Perspective on Heterophily and Oversmoothing in GNNs
Cristian Bodnar" University of Cambridge cristian, bodnar@cl. cam ac
Francesco Di Giovannit Twitter inlgiivaani@twittton com
Benjamin P. Chamberlain
Pietro Liò University of Cambridge
Michael Bronstein University of Oxford & Twitter
Twitter
Abstract
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 graph with 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 dis- cellular sheaf theory to show that
cretise this equation. In this paper, the underlying geometry of the graph is deeply linked with the performance 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 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 asymp- totic 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 heterophilic settings. Overall, our work provides new connections between GNNs and algebraic topology and would of interest to both fields.
Flu)
F(c)
F(u)
FT
F.
Row
F Usie
Tude
4x X
FK Xi)
Fist
U.
10
Figure 1: A sheaf (G,F) F) shown for a single edge of the graph. The stalks are isomorphic to Ig The restriction maps Fude, Fase and their adjoints move the vector features between these spaces. In practice, we learn the sheaf (i.e. the restrictions maps) from data via parametric function T.
Figure Analogy between parallel trans- port on sphere and transport on a discrete vector bundle (cellular sheaf). A tangent vec- tor is moved from F(w) F(w) F(u) and back. Because the vector returns in a different position, the transport is not path- independent.
'Wokk done research intern Twitter. Proved the results in Section 3.1. Our code is available at https: htte::///ttttt
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Introduction
Graph Neural Networks (GNNs) [12, 20, 27-29, 39, 58, 64] have recently become very popular in the ML community as model of choice to deal with relational and interaction data due to their multiple successful applications in domains ranging from social science and particle physics to structural biology and drug design. In this work, we focus on two main problems often observed in GNNs: their poor performance in heterophilic graphs [75] and their oversmoothing behaviour [48, 50]. The former arises from the fact that many GNNs are built on the strong assumption of homophily, i.c., that nodes tend to connect to other similar nodes. The latter refers to a phenomenon of some deeper GNNs producing features that are too smooth to be useful.
Contributions. We show that these two fundamental problems are linked by a common cause: the underlying "geometry" of the graph (used here very loose sense). When this geometry trivial, as is typically the case, the two phenomena described above emerge. We make these statements precise through the lens of (cellular) sheaf theory [10, 18, 26, 44, 56, 62), a subfield of algebraic topology and geometry. Intuitively, cellular sheaf associates vector space to each node and edge of a graph, and a linear map between these spaces for each incident node-edge pair (Figure 1).
In Section 3, we analyse how by considering a hierarchy of increasingly general sheaves, starting from trivial one, diffusion equation based on the sheaf Laplacian [34] can solve increasingly more complicated pode-classificatio tasks in the infinite time limit. In this regime, we show that oversmoothing and problems due to heterophily can be avoided by equipping the graph with the right sheaf structure for the task. In Section 4, we study the behaviour of a non-linear, parametric, and discrete version of this process. This results in a Sheaf Convolutional Network [32] that generalises Graph Convolutional Networks [39]. We prove that this discrete diffusion process is more flexible and has greater control over its asymptotic behaviour than GCNs [13, 51J. All these results are based on the properties of the harmonic space of the sheaf Laplacian, which we study from spectral perspective in Section 3.1. We provide new Cheeger-type incquality for the spectral gap of the sheaf Laplacian and note that these results might be of independent interest for spectral sheaf theory [34]. Finally, in Section 5, we apply our theory to designing simple and practical GNN models. We describe how to construct Sheaf Neural Networks by learning sheaves from data, thus making these types of models applicable beyond the toy experimental setting where they were originally introduced [32]. The resulting models obtain competitive results both in heterophilic and homophilic graphs.
2 Background
Cellular Sheaves. A cellular sheaf [18, 62] over a graph (Figure 1) is a mathematical object associating vector space to each node and edge in the graph and a map between these spaces for each incident node-edge pair. We define this formally below:
Definition 1. A cellular sheaf FG,F) on an undirected graph G = (V,E) consists of:
A vector space F(u) for each E V.
vector space F(e) for each e E F..
linear map Fuge: F(v) F(e))fff for each incident u 9 node-edge pair.
The vector spaces of the nodes and edges are called stalks, while the linear maps are referred to as restriction maps. The space formed by all the spaces associated with the nodes of the graph is called the space of O-cochains C.Dl (G; == θ vEV F(v), where Q denotes the direct sum of vector spaces. For a O-cochain x E (G; we use x. to refer to the vector in F(U) of node e. Hansen and Ghrist [35] have constructed a convenient mental model for these objects based on opinion dynamics. In this context, x,, is the 'private opinion' of node u, while FoseX, expresses how that opinion manifests publicly in a *discourse space' formed by F(e). A particularly important subspace of (G; is the space of global sections (G; == = (" F): Fesex,, Fu containing those private opinions x for which all neighbours (v, u) agree with each other in the discourse space. Given a cellular sheaf FG, we can define sheaf Laplacian operator [34] measuring the aggregated "disagreement of opinions' at each node:
Definition 2. The sheaf Laplacian of a sheaf (G.F) F) is a linear map L5 (G, (G, defined node-wise as Lz(x), := En Figel (Foge F FuseXu).
2

---

u
W
2
F Fustuna) (estiaa)Fastua Fas(ua))
d
X, E F(e)
Fostoar veleoal
gret
x, E F(u)
X E F(w)
W
W
x, J(z)
G = (V. F)
D
X
Figure 3: graph (left), the Laplacian matrix of sheaf with d-dimensional stalks over the graph (middle). and a O-cochain x represented as block-vector stacking the vectors of all nodes (right).
The sheaf Laplacian is a positive semi-definite block matrix (Figure 3). The diagonal blocks are LFve Euse F Filge Fuger while the non-diagonal blocks LF -F FF Denoting by D For
the block-diagonal of L,, the normalised sheaf Laplacian is given by Ay simplicity, we assume that all the stalks have a fixed dimension In that case, the sheaf Laplacian nd x nd real matrix, where is the number of nodes of G. When the vector spaces are set to IR (i.e., d = 1) ) and the linear maps to the identity map over IR, the underlying sheaf is trivial and one recovers the well-known
graph Laplacian matrix and its normalised version Ao. In general, AF is preferred to LF for most practical purposes due to its bounded spectrum and, therefore, we focus on the former. A cochain x is called harmonic if L 0 or, equivalently, if x ker (Lr(.)). This means harmonic cochains are characterised by zero disagreements along all the edges of the graph, and it is not difficult to that, in fact, spaces [35].
and ker(LF) are isomorphic as vector
The sheaves with orthogonal maps (i.e. Foste E (d) the Lie group of d x d orthogonal matrices) provide more geometric interpretation of sheaves and play an important role our analysis. Such sheaves are called discrete (d) bundles and can be seen as discrete version of vector bundles [24, 60, 73] from differential geometry [67]. Intuitively, these objects describe vector spaces attached to the points of manifold. In our discrete case, the role of the manifold is played by the graph, and the sheaf Laplacian describes how the elements rotations in another neighbouring vector space similarly to how tangent vectors moved across manifold via parallel transport (connection; see Figure 2). Due to this analogy, the sheaf Laplacian on (dd bundles is also referred to connection Laplacian [63].
vector space are transported via
Heat Diffusion and GCNs. Consider graph with adjacency matrix A, diagonal degree matrix D. normalised graph Laplacian Ao := I D-11//2 AD- 1-/2 and an n x f feature matrix X. We can define the heat diffusion equation and its Euler discretisation with unit step as follows:
1/2
(1) = (() ~ X( = (() (1) = (I - Ao)
Comparing this with the Graph Convolutional Network [39] model, we observe that GCN is an augmented heat diffusion process with additional weight matrix W and nonlinearity a:
GCN(X, A) = aD 1/2 AD 1/2 xw) a(11 Ao)
From this perspective, it is perhaps not surprising that GCN is particularly affected by heterophily and oversmoothing since heat diffusion makes the features of neighbouring nodes increasingly smooth. In what follows, consider much more general and powerful family of (sheaf) diffusion processes leading to more expressive sheaf convolutions.
3 The Expressive Power of Sheaf Diffusion
Preliminaries. Let now assume G to be graph with d-dimensional node feature vectors X, E F(e). The features of all nodes are represented the individual d-dimensional vectors (Figure 3). Additionally, if we allow for f feature channels, everything can be represented as a matrix X E [R(nd)x f, whose columns are vectors in (); F). We are interested in the spatially discretised sheaf diffusion process governed by the following PDE:
single vector (o; F) stacking all
X(O) = X, X(t) (t)(
3
3

---

It can be shown that in the time limit, each feature channel is projected into ker (Ax) [34]. As described above (up to a D-1/2 normalisation), this space contains the signals that agree with the re- striction maps of the sheaf along all the edges. Thus, sheaf diffusion can be seen as 'synchronisation" process over the graph, where all the private opinions converge towards global agreement.
In this section, we investigate the expressive power of this process within the infinite time limit. Because the asymptotic behaviour of sheaf diffusion is determined by the properties of ker( (A)), in Section 3. investigate when this subspace non-trivial (i.e. it contains more than just the zero vector). In Section 3.2, we use this characterisation of the harmonic space to study what sort of sheaf diffusion processes will asymptotically produce projections into ker A that can linearly separate the classes for various kinds of graphs and initial conditions. Since diffusion converges exponentially fast, the following results are also relevant for models with finite integration time or layers.
3.1 Harmonic Space of Sheaf Laplacians
A major role in the analysis below is played by discrete vector bundles, and we concentrate on this case. We note though that our results below generalise to the general linear group Fudee E GL(d). the Lie group of d x d invertible matrices, provided we can also control the norm of the restriction maps from below. Given a discrete ((d)-bundle, F.g..ooge = La and the block diagonal of Ly has diagonal structure since Live d, where dy is the degree of node v. Accordingly, if a signal X E ker(L then the signal x v + Vd, E ker(Az) and similarly for the inverse transformation.
Key to our analysis is studying transport operators induced by the restriction maps of the sheaf. Given nodes v, u E V and a path Yo-u = (u, Ul...., Ug, u) from to u, we consider notion of transport from the stalk F(u) to the stalk F(u), constructed by composing restriction maps (and their transposes) along the edges:
P7 カIト == (Fugee
(F., (FugeeFuge)) : F(u) - F(u).
For general sheaf structures, the graph transport is path dependent, meaning that how the vectors are transported across two nodes depends on the path between them (see Figure 2). In fact, we show that this property characterises the spectral gap of a sheaf Laplacian, i.c. the smallest eigenvalue of Ar.
Proposition 3. If F max ||? - Pa'sall then we have No S 2r2/2
discrete O(d) bundle over connected graph and
consequence of this result is that there is always a non-trivial harmonic space (i.e. Xo if the transport maps generated by an orthogonal sheaf are path-independent (i.c. r = 0). Next, we address the opposite direction.
Proposition 4. If F is a discrete (d) bundle over a connected graph and x E (G, F), then for any cycle 7 based E we have Xy (Pe I).
This proposition highlights the interplay between the graph and the sheaf structure. A simple consequence of this result is that for any cycle-free subset S C V, have that any sheaf (or connection-) Laplacian restricted to S always admits a non-trivial harmonic space. A natural question connected to the previous result is whether Cheeger-like inequality holds in the other direction. This turns out to be the case:
Proposition 5. Let F. be discrete (dd) bundle over a connected graph G with nodes and let [I(P),, _-. - T)x,1l 2 <||x,|]] for all cycles Tv-su- Then Xo 2 ((diiam (G)m d
While the bound above is of little use in practice, it shows how the spectral gap of sheaf Laplacian indeed related to the deviation of the transport maps from being aath-independent, as measured by We note that the Cheeger-lik- like inequality presented here is not unique, and other types of bounds on X have been derived [2]. We conclude this section by further analysing the dimensionality the harmonic space of discrete O(d)-bundle)
Lemma 6. Let F be discrete O(d) bundle over a connected graph G. Then dim (H²) S d and dim(H = d if and only if the transport is path-indeeendent.

---

Diffusion time 0.O
Diftusion time 0.5
Diflusinn time 1.
Difusion time
Difustoon time 3.5
Diflusion time 4.5
Diftusion time 5.5
Diftusion time
Figure 4: Diffusion process on O(2)-bundles progressively separates the classes of the graph.
3.2 The Linear Separation Power of Sheaf Diffusion
In what follows, use the results above to analyse the ability of certain classes of sheaves to linearly separate the features in the limit of the diffusion processes they induce. We utilise this as a proxy for the capacity of certain diffusion processes avoid oversmoothing.
Definition 7. A hypothesis class of sheaves with d-dimensional stalks Hd has linear separation power over a family of graphs G if for any labelled graph G = (V, E) E G, there is a sheaf (F, G) E Hd that can linearly separate the classes of G in the time limit of Equation 3 for almost all initial conditions.
Note that the restriction to almost all initial conditions is necessary because, in the limit, diffusion behaves like projection in the harmonic space and there will always be degenerate initial conditions (e.g. the zero matrix) that will yield a zero projection. We will now show how the choice of the sheaf impacts the behaviour of the diffusion process. For this purpose, we will consider a hierarchy of increasingly general classes of sheaves.
Symmetric invertible. HSy := ((F.G) Fuge = Fase: det(Fuge) + 0}. We note that for d d= 1. the sheaf Laplacians induced by this class of sheaves coincides with the set of the well- known weighted graph Laplacians with strietly positive weights, which also includes the usual graph Laplacian (see proof in Appendix B). Therefore, this hypothesis class is of particular interest since it includes those graph Laplacians typically used by graph convolutional models such as GCN [39] and ChebNet [20]. We first show that this class of sheaf Laplacians can linearly separate the classes in binary classification settings under certain homophily assumptions:
Proposition 8. Let be the set of connected graphs G E) with two classes A, B C V such that for each v E A, there exists u E A and an edge (u. u) E E. Then Haym has linear separation power over G.
In contrast, under certain heterophilic conditions, this hypothesis class is not powerful enough to linearly separate the two classes no matter what the initial conditions are:
Proposition 9. Let G be the set of connected bipartite graphs G = (A, B, E), with partitions A, B forming two classes and |A| |B) Then Haym cannot linearly separate the classes of any graph in G for any initial conditions (0) E Raxf_
Non-symmetric invertible. Hd := ((F.)) : det(FFge) * 0}. This larger hypothesis class addresses the above limitation by allowing symmetreet relations:
Proposition 10. Let 9 contain all the connected graphs G = (V.E) with two classes A Consider a sheaf (F; G) E H' with Fuse -ae if v E A and Fuge aie if u E B with ae 0 for all e E E. Then the diffusion induced by (F:G) can linearly separate the classes of G for almost all initial conditions, and H. has linear separation power over G.
Since FTSeF = =o. the type of sheaf above can be interpreted as discrete -bnndbll over a weighted graph with edge weights af and transport maps Fuse -1 for the inter-class edges and +1 for the intra-class edges. Intuitively, this type of transport, which is path-independent, polarises the features of the two classes and forces them to take opposite signs in the infinite limit. This provides a sheaf-theoreti explanation for why negatively-weighted edges have been widely adopted in heterophilic settings [7, 17, 72].
So far we have only studied the effects of changing the type of sheaves in dimension one. We now consider the effects of adjusting the dimension of the stalks and begin by stating a fundamental limitation of (sheaf) diffusion when d = L.
Proposition 11. Let be a connected graph with C classes. Then, Hi cannot linearly separate the classes of G for any initial conditions X(0) E R
5

---

This is essentially a consequence of dim (ker( (a)r < 1 in this case, by virtue of Lemma 6. From GNN perspective, this means that in the infinite depth setting, sufficient stalk width (i.e., dimension d) is needed in order to solve tasks involving more than two classes. Note that d is different from the classical notion of feature channels f. As the result above shows, the latter has no effect on the linear separability of the classes in d = 1. Next, we will see that the former does.
Diagonal invertible. Htt { diagonal Fuse: det(Fooge) * 0}. The sheaves in this class be seen as d independent sheaves from H encoded in the d-dimensional diagonals of their restriction maps. This perspective allows us to generalise Proposition 10 to multi-class setting:
Proposition 12. Let 9 be the set of connected graphs with nodes belonging to C 2 classes. Then for d 2 C. diag has linear separation power over G.
This result illustrates the benefits of using higher-dimensional stalks while maintaining a simple and computationally convenient class of diagonal restriction maps. Next, with more complex restriction maps, we can show that presence of even more classes.
stalks can be used to achieve linear separation in the
Orthogonal. Ho == [(F G): Fust E O(d) is the class of (dd)-bundles. Orthogonal maps are able to make more efficient use of the space available to them than diagonal restriction maps:
Proposition 13. Let G be the class of connected graphs with C < 2d classes. Then, for all {2, 4). H has linear separation power over G.
Figure includes an example diffusion process over an 0(2)- bundde.
Summary: Different sheaf classes give rise to different behaviours of the diffusion process and, consequently, different separation capabilities. Taken together, these results show that solving any node classification task can be reduced to performing diffusion with the right sheaf.
4 Expressive Power of Sheaf Convolutions
Analogously to how GCN augments heat diffusion, we can construct Sheaf Convolutional Network (SCN) augmenting the sheaf diffusion process. In this section, we analyse the capacity of SCNs to change, if necessary, their asymptotic behaviour compared to the base diffusion process. Since the sheaf structure will be ultimately learned from data, this is particularly important for the common setting when the learned sheaf is different from the "ground truth" sheaf for the task to be solved.
The continous diffusion process from Equation 3 has the Euler discretisation with unit step-size X(I 1)) = x() - (t) = (Ind Ax (t), Assuming X E &Rndxfr /t, we can equip the right side with weight matrices W1 E Rdddd Wa E x and -on-linear a to arrive at the following model originally proposed by Hansen and Gebhart [32]:
Y AI) @ W))XW;) E nd
(4)
where S2 are the number of input and output feature channels, and @ denotes the Kronecker product. Here, W, multiplies from the left the vector feature of all the nodes in all channels (i.e. Wix', for all v and channels i), while We multiplies the features from the right and can adjust the number of feature channels, just like in GCNs. As one would expect, when using trivial sheaf,
AF= == Ao. W1 becomes a scalar and one recovers the GCN of Kipf and Welling [39]. To see how SCNs behave compared to their base diffusion process, we investigate how SCN layers affect the sheaf Dirichlet energy Ex(x),, which sheaf diffusion is known to minimise over time.
Definition 14. Ex(x) == = Ee=(v.a)
F D.
1/2 X.
Fuse D.. 1/2 x,113
Similarly, for multiple channels the energy is Es close a signal x is to (er(Ar) and it is easy to see that x E ker (Ar) + E = O. We begin by studying the sheaves for which the energy decreases and representations end up asymptotically in ker( (A)). Let X, == max - 1)2 < and denote by H. : ((F G) Furgo > 0}.
trace X X). This is a measure of how
Theorem 15. For (F,G) H., and being ReLU,,) Ex X. | W E

---

This generalises existent results for GCNs [13, 51] and proves that SCNs using this family of Laplacians, which includes all weighted graph Laplacians, exponentially converge ker( (Ax)
O, then (Y) 0 and the representations remain trapped inside the kernel no matter what the norm of the weights is. Therefore, in settings as those described by Propositions 9 and 11, the linear separation capabilities of this class of models are severely limited (see Corollaries 36, 37 in Appendix B).
>= >=I W 1 <. 1. In particular, if (x)
Finally, the Theorem also extends to bundles with symmetric maps, H orth, H HHyymi
Theorem 16. If (F, G) E Hid
oythhssm and o = (Leaky)ReLU, Ex & X, W. 2 2 (X).
In some sense, this is not surprising because, for this class, ker (b) contains the same information as the kernel of the classical normalised graph Laplacian (see Proposition 29 in Appendix C).
More generally, SCNs with sheaves outside Hyym are much more flexible and can easily increase the Dirichlet energy using an arbitrarily small linear transformation Wi:
Proposition 17. For any connected graph G and ε > there exist a sheaf (G, $ Hoym W1 with [/Wlll ll2 < & and feature vector x such that E & Wi)x) > Ex
Importantly, this proves that this family of SCNs can, if necessary, escape the kernel of the Laplacian.
Summary: Not only that sheaf diffusion is more expressive than heat diffusion as shown in Section 3.2, but SCNs are also more expressive than GCNs in the sense that they are generally not constrained to decrease the Dirichlet energy when using low-norm weights. This provides them with greater control than GCNs over their asymptotic behaviour.
5 Neural Sheaf Diffusion and Sheaf Learning
In the previous sections, we discussed the various advantages provided by sheaf diffusion and sheaf convolutions. However, in general, the ground truth sheaf is unknown or unspecified. Therefore, we aim learn the underlying sheaf from data end-to-end, thus allowing the model pick the right geometry for solving the task.
Neural Sheaf Diffusion. We propose the diffusion-type model from Equation 5. We note that by setting W,, I, W₂ to identity and (x) = ELU(xx)/e with e >> small enough or simply o = id, we recover (up to scaling) the sheaf diffusion equation. Therefore, the model is at least as expressive as sheaf diffusion and benefits from all the positive properties outlined in Section 3.2.
X(t) = - & (1))(
(5)
Crucially, the sheaf Laplacian AF(1) is that of a sheaf (G, that evolves over time. More specifically, the evolution of the sheaf structure is described by a learnable function of the data (G, = g(G, X(t): 8). This allows the model to use the latest available features to manipulate the underlying geometry of the graph and, implicitly, the behaviour of the diffusion process. Additionally, We use an MLP followed by a reshaping to map the raw features of the dataset to a matrix X(0) of shape nd x f and a final linear layer to perform the node classification.
In our experiments, we focus on the time-discretised version of this model from Equation 6, which allows us to use a new set of weights at each layer i while maintaining the nice theoretical properties of the model above.
5+1=X, X, - (I @ Wi)X,W')
-
(6)
We note that this model is different from the SCN model from Equation 4 in two major ways. First, Hansen and Gebhart [32] used a hand-crafted sheaf with d' = 1, constructed in a synthetic setting with full knowledge of the data-generating process. In contrast, we learn a sheaf, which makes model applicable to any real-world graph dataset, even in the absence of a sheaf structure. Additionally, motivated by our theoretical results, use the full generality of sheaves by using stalks with d' > 1 and nigher-dimensiona. maps. Second, our model uses a residual parametrisation of the discretised diffusion process, which empirically improves its performance.
Sheaf Learning. The restriction maps are learned using locally available information. Each d x d matrix Fuse is learned via a parametric matrix- matrix-valued function L. with (use:=(o.)) 2(xx,, x.).
7

---

Crepk
Hasopill Mya Brauh
Heroogan of th haimed costpport maga
1.0
14
manng
585
thoa E be 200
0.00
Weipedd
14
Steal sont)
Figure 5: (Left) Train and (Middle) test accuracy as a function of diffusion time. (Right) Histogram of the learned scalar transport maps. The performance of the sheaf diffusion model is superior to that of seighted-graphe diffusion and correctly learns to invert the features of the two classes.
This function must be non-symmetric to be able to learn asymmetric transport maps along each edge. In practice, we set (xx,, x,) = of (V[x,, |x,]) followed by a reshaping of the output, where V is a weight matrix. For simplicity, the equations above use a single feature channel, but in practice, all channels are supplied as input. More generally, we can show that if the function has enough capacity and the features are diverse enough, we can learn any sheaf over a graph.
Proposition 18. Let G = (V, E) be a finite graph with features X. Then, if (Xx, Xu) + (Xu, ffr any (v. u) + (w, 2) E E and & is an MLP with sufficient capacity, 4 can learn any sheaf (F; G).
First, this result formally motivates learning sheaf at each layer since the model can learn to distinguish more nodes after each aggregation step. Second, this suggests that more expressive models (in the Weisfeiler-Lehhmn sense [8, 9, 46, 71 could learn more general family of sheaves. We leave a deeper investigation of these aspects for future work. In what follows, we distinguish between several types of functions & depending on the type of matrix they learn.
Diagonal. The main advantage of this parametrisation is that fewer parameters need to be learned per edge, and the sheaf Laplacian ends up being matrix with diagonal blocks, which also results in fewer operations in sparse matrix multiplications. The main disadvantage is that the d dimensions of the stalks interact only via the left W, multiplication.
Orthogonal. In this case, the model effectively learns a discrete vector bundle. Orthogonal matrices provide several advantages: (1) they can mix the various dimension of the stalks, (2) the orthogonality constraint prevents overfitting while reducing the number of parameters, (3) they have better understood theoretical properties, and (4) the resulting Laplacians are casier to normalise numerically since the diagonal entries correspond to the degrees of the nodes. In our model, we build orthogonal matrices from composition of Houscholder reflections [45].
General. Finally, we consider the most general option of learning arbitrary matrices. The maximal flexibility these maps provide can be useful, but it also comes with the danger of overfitting. At the same time, the sheaf Laplacian is more challenging to normalise numerically since one has to compute D-1/2 for a positive semi-definite matrix D. To perform this at scale, one has to rely on SVD, whose gradients can be infinite if D has repeated eigenvalues. Therefore, this model is more challenging train.
Computational Complexity. The GCN from Equation 2 has complexity Onne² + mc), where e is the number of channels and m the number of edges. Assume sheaf diffusion model with stalk e (i.e. same representation size). Then, when the model uses diagonal maps, the complexity is O(ne2 + mdc). When using orthogonal general matrices, the complexity becomes O(n(c² + dd) + m(cd + dd)) (see Appendix F. 1.1 for detailed derivations). In practice, we 1 < d < 5, which effectively results in constant overhead compared to GCN.
dimension d and f channels such that d x
Experiments
Synthetic experiments. We consider a simple setup given by a connected bipartite graph with equally sized partitions. We sample the features from two overlapping isotropic Gaussian distributions to make the classes linearly non-separable at initialisation time. From Proposition 9, we know that diffusion models using symmetric restriction maps cannot separate the classes in the limit, while a diffusion process using negative transport maps can. Therefore, we use two vanilla sheaf diffusion processes by setting d = 1, W
Ia. W2 1 and id in Equation 5. In both models, we learn
8

---

Table I: Results on node classification datasets sorted by their homophily level. Top three models coloured by First, Second, Third. Our models are marked NSD.
Texas
Wisconsin
Film
Squirrel
Chameleon
Cornell
Citeseer
Pubmed
Cora
Hom lovel
0.11
0.21
0.22
0.22
0.23
0.30
0.74
0,80
0.81
#Nodes
251
7,600
5,201
2,277
183
3,327
18.717
2.708
#Edges
295
466
26.752
198,493 5
31,421 5
280
4,676
44,327 3
5,278
#Classes
5
Diug-NSD
a5.67
88,
63.77
37.70
54.78
68 68..77
77.14 86.49:7.35
80 89.42a0.4a
87.14
Oid)-NSD
85, 45.9525.31
89. 690.41:14
37 81 11:15
56.3441133
68 68.0441.54
84 86
76.70g 57
89 49
86.901111
Gen-NSD
52.97.5.13
89.2113384
37 1:11
53.17.1.31
67.90.1.55
85 88.68
76.32.1.05 1.05
80.53..0.3
87.30
GGCN
84. 4.55
86,86 1:.22.
37. 77.544::.0 .s
55. 00.1771..
71. 71.14
85 68
77.14
80. 80.155
87 17.95:1..0
H2GCN
87.65
35-70
46.48_114
10.11
82.70
87 87
GPRGNN
78. 38
82, 21
31 683e 22
31. 31.61=1124
1.75
80 00.277+8..1 11
77. 77.13=110 1.77
87.51++0. sa
87 15115
FAGUN
82.43
82.94
34.87
42.59 79
56. 05.22:33.19
79: 19
N/A
N/A
N/A
MixHop
77.84=7.75
75.88=4.50
32. 22
13.80=1446
60.50)=2.58
73.51+66.4
76.26 L8
87 83.
GCNII
77.57
20.33
37. 37.44
38. 18.47:11.50
63.86.2..44
77 77.86:13.79
77.33:1.48
90. 15
88. 15.37::1
Geon-GCN
76:76:2:72
61.51=3.50
31 19
38.15=9092
60.001+2.55
78.02#1.16
89 95:0.4
85, 15.35
PairNorm
60.27..434
48.47.16.14
27.40
50.44_.2044
62.74.11..a
18.92133:1
73.50 AT
87.50..0.4 s4
65.7911.0
GraphSAGE
82 82.43::6:14
81.18:5.00 56
34 14.23330..00 09
41.6120074
08.73:11.8
75. 10.96::3.00 o
76.04::1.00 30
88, 18.44aa0 to
86 66.900110 04
GCN
55.14_.-15
51.76.3.06
27.3213:00
53.43
64.82,1..1
76.50.1.1 60.5411..99
89.42 18.42.10.5
86.9811.37
GAT
62.16:66.0
49.41=4.00
27.4466.89 89
40.722:1550 56
00.26:22.00 50
61 89..3
76.65 28
87.30+ 10
86, 86.333e0
MLP
80.81=4.75
83,299s.31
36.53e0070
28.77:1.50
46,21=22.0
61.899666.0 40
71.02=1.00
$7.16is0.57
75. 75.69:2200
a sheaf at t 0 function of X(0), and we keep the sheaf constant over time. For the first model, we learn a sheaf with general maps Fr E R. For the second model, we use a similar layer but constraint Fuste
Fuge, obtaining a weighted graph Laplacian.
Figure presents the results across five seeds. As expected, for diffusion time zero (i.e. no diffusion). we see that a linear classifier cannot separate the classes, At later times, the diffusion process using symmetric maps cannot perfectly fit the data, In contrast, with the more general sheaf diffusion, as time increases and the signal approaches the harmonic space, the model gets better and the features become linearly separable. In the last subfigure, we take closer look at the sheaf that the model learns in the time limit by plotting histogram of all the transport (scalar) maps FuseFuse In accordance with Proposition 10, the model learns a negative transport map for all edges. This shows that the model manages to avoid oversmoothing (see Appendix F for an experiment with d >>> 1).
Real-world experiments. We test our models on multiple real-world datasets with an edge homophily coefficient h ranging from h = 0.11 (very heterophilic) to h = 0.81 (very homophilic). Therefore, they offer a view of how model performs over this entire spectrum. We evaluate our models on the 10 fixed splits provided by Pei et al. [53] and report the mean accuracy and standard deviation. Each split contains 20%%%22222// 920% of nodes per class for training, validation and testing, respectively. As baselines, we use an ample set of GNN models that can be placed in three
61, 66)
categories: (1) classical: GCN [39], GAT [68]. GraphSAGE [31]; (2) models specifically designed for heterophilic settings: GGCN [72], Geom-GCN [53], H2GCN [75]. GPRGNN [17], FAGCN [7],
MixHop [1]: (3) models addressing oversmoothing: GCNII [16]. PairNorm [74]. All the results
taken from Yan et al. [72], except for FAGCN and MixHop, which come from Lingam et al. [41]
and Zhu al. [75], respectively. All of these were evaluated on the same set of splits ours. In
Appendix F we also include experiments with continuous GNN models.
we see that our models are first in 5/6 benchmarks with high heterophily (h < 0.3) and second-ranked on the remaining one (i.e. Chameleon). At the same time, NSD also shows strong performance on the homophilic graphs by being within approximately 1% of the top model. Overall, NSD models diffusion model performs best overall confirming the intuition that it can better avoid overfitting, while also transforming the vectors in sufficiently complex ways. We also remark on the strong performance of the model learning diagonals maps, despite the simpler functional form of the Laplacian.
Results. From Table
among the top three models on 8/9 datasets. The bundde
7 Related Work, Discussion, and Conclusion
Sheaf Neural Networks & Sheaf Learning. Sheaf Neural Networks [32] with a hand-crafted sheaf Laplacian were originally introduced in a toy experimental setting. Since then, they have remained completely unexplored, and we hope this paper will fill this lacuna. contrast to [32), we provide an ample theoretical analysis justifying the use of sheaves in Graph MI. and study for the first time how sheaves can be learned from data using neural networks. Furthermore, we present the first successful application of Sheaf Neural Networks real-world datasets. Hansen and Ghrist [33]

---

have also considered learning sheaf Laplacian by minimising directly in matrix space a regularised Dirichlet energy metric. Different from their approach, we learn the sheaf as part of an end-to-end model and use an efficient parametrisation that is independent of the size of the graph.
Follow-up works have also experimented with inferring a connection Laplacian directly from data pre-processing time [3], combining sheaves with attention [4], and designing models based on the wave equation on sheaves [65]. Besides the sheaf Laplacians employed in all these works and ours, one can also use higher-order sheaf (connection) Laplacians that operate on higher-order tensors. These were shown to encode important information about the underlying symmetries in the data [55], which hints at the powerful data properties that Sheaf Neural Networks could potentially extract from these operators.
Heterophily and Oversmoothing. While good empirical designs jointly addressing these two problems have been proposed before [17, 72], Yan et al. [72] is the only other work connecting the two theoretically. Their analysis [72] is very different in terms of methods and assumptions and, therefore, their results are completely orthogonal. Concretely, the authors analyse the performance of linear SGCs [69] (i.e. GCN without nonlinearities) on random attributed graphs. In contrast, our analysis is not probabilistic, focuses on diffusion PDEs and also extends to GCNs in the non-linear regime. Furthermore, we employ a new set of mathematical tools from cellular sheaf theory, which brings a new language and new tools to analyse these problems. Perhaps the only commonality is that both works find evidence for the benefits of negatively signed edges in GNNs, although with different mathematical motivations. At the same time, other recent works [21, 42] have shown that GCNs with finite layers (typically one) can perform well in heterophilic graphs (including bipartite). This is in no contradiction with our results, which consider an infinite time/layer regime (i.e. not finite) and perfect linear separation (i.e. a model that cannot fit the data can still achieve high accuracy).
Category Theory and GNNs. From the perspective of category theory [43], cellular sheaves are a functor from category describing the incidence structure of the graph to category describing the data living on top of the graph. Informally, this says that the vertices and edges are mapped to some type of data (e.g. vector spaces) and the incidence relations between vertices and edges mapped to some type of relation between the assigned data (e.g. linear maps between the vector spaces). The generality provided by this perspective could be used extend the models described in this work to more exotic types of data such as lattices and their associated sheaf Laplacians [25]. At the same time, our work echoes other recent efforts to place GNNs a categorical foundation [19, 22].
Message Passing Neural Networks. The layer from Equation 6 can be seen as a form of GNN- FiLM layer [11, 54], where each node learns linear message function conditioned on the features of the neighbours. Such models have been recently shown to perform well empirically in heterophilic settings [52]. At the same time, the model bares an algorithmic resemblance to GAT [68]. For central node v and neighbouring node GAT learns an attention coefficient aeu. while our model learns a matrix given by the block (v, u) of Az.. Finally, a pesssage-passing procedure based on parallel transport has also been proposed by Haan et al. [30] in the context of geometric graphs (meshes). In the absence of a natural geometric structure on arbitrary graphs, in our case, the transport structure is learned from data end-to-end.
Limitations and societal impact. One of the main limitations of our theoretical analysis is that does not address the generalisation properties of sheaves, but this remains a major impediment for the entire field of deep learning. Nonetheless, our setting was sufficient to produce many valuable insights about heterophily and oversmoothing and a basic understanding of what various types of sheaves can and cannot do. Much more work remains to be done in this direction, and we expect to see further cross-fertilization between ML and algebraic topology in the future. Finally, due to the theoretical nature of this work, we do not foresee any immediate negative socictal impacts.
Conclusion. In this work, we used cellular sheaf theory to provide novel topological perspective on heterophily and oversmoothing in GNNs. We showed that the underlying sheaf structure of the graph is intimately connected with both of these important factors affecting the performance of GNNs. To mitigate this, we proposed a new paradigm for graph representation learning where models not only evolve the features at each layer but also the underlying geometry of the graph. In practice, we demonstrated that this framework achieves competitive results in heterophilic settings.
10

---

Acknowledgments and Disclosure of Funding
We are grateful to Iulia Duta, Dobrik Georgiev and Jacob Deasy for valuable comments on an earlier version of this manuscript. CB would also like thank the Twitter Cortex team for making the research internship a fantastic experience. This research was supported in part by ERC Consolidator grant No. 724228 (LEMAN).
References
[1] Sami El--aaaaa Bryan Perozzi, Amol Kapoor, Hrayr Harutyunyan, Nazanin Alipourfard, Kristina Lerman, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convo- lutional architectures via sparsified neighborhood mixing. In The Thirty-sixth International Conference Machine Learning (ICML), 2019. URL http::tttpp/ceeee httt:://prrceeedngss mlr. aalr.pret press/ -97/aabueel-haijaala/a -aaieell-aaaaaaa jaaiiaaala.pp... a1f....f.........
[2] Afonso Bandeira, Amit Singer, and Daniel A Spielman. Cheeger inequality for the graph connection laplacian. SIAM Journal on Matrix Analysis and Applications, 34(4):1611-1630 2013.
[3] Federico Barbero, Cristian Bodnar, Haitz Sáez Ocáriz Borde, Michael Bronstein, Petar Veličković, and Pietro Liò. Sheaf neural networks with connection laplacians. In ICML 2022 Workshop on Topology, Algebra, and Geometry in Machine Learning. 2022.
[4] Federico Barbero, Cristian Bodnar, Haitz. Sáez de Ocáriz Borde, and Pietro Lio. Sheaf attention networks. NeurlPS 2022 Workshop on Symmetry and Geometry Neural Representations, 2022.
[5] Lukas Biewald. Experiment tracking with weights and biases, 2020. URL https://wwe wandb.com com/. Software available from wandb.com.
[6] Christopher M. Bishop. Pattern Recognition and Machine Learning (Information Science and Statistics), Springer-Verlag, Berlin, Heidelberg, 2006. ISBN 0387310738.
[7] Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. Beyond low-frequency information in graph convolutional networks. In AAAI. AAAI Press, 2021.
[8] Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yu Guang Wang, Pietro Liò, Guido Montúfar, and Michael Bronstein. Weisfeiler and Lehman Go Cellular: CW Networks. In NeurIPS, 2021.
[9] Cristian Bodnar, Fabrizio Frasca, Yuguang Wang, Nina Otter, Guido F Montufar, Pietro Lió, and Michael Bronstein. Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks. In ICML., 2021.
[10] Glen E Bredon. Sheaf theory, volume 170. Springer Science & Business Media, 2012.
[11] Mare Brockschmidt. Gnn-film: Graph neural networks with feature-wise linear modulation. In International Conference on Machine Learning, pages 1144-1152, PMLR, 2020.
[12] Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. In ICLR, 2014.
[13] Chen Cai and Yusu Wang. arXiv:2006. 13318, 2020.
note on over-smoothing for graph neural networks.
[14] Benjamin Paul Chamberlain, James Rowbottom, Davide Eynard, Francesco Di Giovanni, Dong Xiaowen, and Michael M Bronstein. Beltrami flow and neural diffusion on graphs. In NeurIPS. 2021.
[15] Benjamin Paul Chamberlain, James Rowbottom, Maria Goronova, Stefan Webb, Emanuele Rossi, and Michael M Bronstein. Grand: Graph neural diffusion. In ICML, 2021.

---

[16] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In Hal Daumé III and Aarti Singh. editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 1725-1735. PMLR, 13-18 Jul 2020. JRR.https://proceediig /ttp//v119///// 19/ chen20v. html.
mlr. prwspreeeveeee caaiss/vvii
[17] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. In International Conference on Learning Representations, 2021. URL https: /ttee:///ppeeeieeeeeeeeee httpp/p/nrrra.....eeeemaraaaaaaa
[18] Justin Michael Curry. Sheaves, cosheaves and applications. University of Pennsylvania, 2014.
[19] Pim de Haan, Taco Cohen, and Max Welling. Natural graph networks. In NeurIPS, 2020.
[20] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In NIPS, 2016.
[21] Lun Du, Xiaozhou Shi, Qiang Fu, Xiaojun Ma, Hengyu Liu, Shi Han, and Dongmei Zhang. Gbk-gnn: Gated bi-kemel graph neural networks for modeling both homophily and heterophily. In Proceedings of the ACM Web Conference 2022, pages 1550-1558, 2022.
[22] Andrew Dudzik and Petar Veličković. Graph neural networks are dynamic programmers. arXiv preprint arXiv:2203. 15544, 2022.
[23] Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. (xXiv:2003.0098: 2020.
[24] Tingran Gao, Jacek Brodzki, and Sayan Mukherjee. The geometry of synchronization problems and learning group actions. Discrete Computational Geometry, 65(1):150-21 2021
[25] Robert Ghrist and Hans Riess. Cellular sheaves of lattices and the tarski laplacian. arXiv:2007.04099 2020.
[26] Robert W Ghrist. Elementary applied topology, volume Createspace Seattle, 2014.
[27] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In JCML, 2017.
[28] Christoph Goller and Andreas Kuchler. Learning desedeepnddntt distributed representations by backpropagation through structure. In ICNN, 1996.
[29] Marco Gori, Gabriele Monfardini, and Franco Scarselli. A new model for learning in graph domains. IJCNN, 2005.
[30] Pim De Haan, Maurice Weiler, Taco Cohen, and Max Welling. Gauge equivariant mesh CNNs: Anisotropic convolutions on geometric graphs In International Conference on Learning Representations, 2021. URL https:// http://wwww.....eeeeeerererrreee wtdfoorrmmmddddppppppp Jnsppp- oIZE.
[31] William L Hamilton, Rex Ying, and Jure Leskovec. Representation learning on graphs: Methods and applications. IEEE Data Engineering Bulletin, 2017.
[32] Jakoh Hansen and Thomas Gebhart. Sheaf neural networks. In NeurlPS 2020 Workshop on Topological Data Analysis and Beyond, 2020.
[33] Jakob Hansen and Robert Ghrist. Learning sheaf laplacians from smooth signals. In ICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 5446-5450. IEEE, 2019.
[34] Jakob Hansen and Robert Ghrist. Toward a spectral theory of cellular sheaves. Journal of Applied and Computational Topology, 3(4):315 2019.
[35] Jakob Hansen and Robert Ghrist. Opinion dynamics on discourse sheaves. SIAM Journal on Applied Mathematics, 81(5):2033-2060, 2021.
12

---

[36] Kurt Hornik. Approximation capabilities of multilayer feedforward networks. Neural networks, 4(2):251-257, 1991.
[37] Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural networks, 2(5):359-36,, 1989.
[38] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR, 2015.
[39] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
[40] Hyun Deok Lee. On some matrix inequalities. Korean Journal of Mathematics, 16(4):565-571, 2008.
[41] Vijay Lingam, Rahul Ragesh, Arun lyer, and Sundararajan Sellamanickam. Simple truncated svd based model for node classification heterophilic graphs. arXiv preprint 1xXiv:2006.12807,, 2021.
[42] Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao-War Chang, and Doina Precup. Is heterophily real nightmare for graph neural networks to do node classification? arXiv preprint arXiv: 109.522109.05641, 2021.
[43] Saunders Mac Lane. Categories for the working mathematician, volume 5. Springer Science & Business Media, 2013.
[44] Saunders MacLane and Ieke Moerdijk. Sheaves geometry and logic: first introduction to topos theory. Springer Science & Business Media, 2012.
[45] Zakaria Mhammedi, Andrew Hellicar, Ashfaqur Rahman, and James Bailey. Efficient orthogonal parametrisation of recurrent neural networks using householder reflections. In International Conference on Machine Learning, pages 2401 2409. PMLR, 2017.
[46] Christopher Morris, Martin Ritzert, Matthias Fey, William I. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and Leman go neural: Higher-order graph neural networks. In AAAI, 2019.
[47] Galileo Namata, Ben London, Lise Getoor, Bert Huang, and U Edu. Query-driven active surveying for collective classification. In 10th International Workshop on Mining and Learning with Graphs, volume 8, page 1, 2012.
[48] H Nt and T Machara. Revisiting graph neural networks: all we have is low pass filters. arXiv preprint arXiv:18122.0844VV 2019.
[49] Anton Obukhov. Efficient householder transformation in pytorch, 2021. URL www. github. Version: 1.0.1, DOI: 10.5281/2emodo.506697
[50] K Oono and T Suzuki. Graph neural networks exponentially lose expressive power for node classification. In International Conference on Learning Representations, 2020.
[51] Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. arXiv:1905.10%4 2019.
[52] John Palowitch, Anton Tsitsulin, Brandon Mayer, and Bryan Perozzi. Graphworld: Fake graphs bring real insights for gnns. arXiv preprint arXiv:2203.000 12, 2022.
[53] Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. arXiv preprint arXiv:2002.05287, 2020.
[54] Ethan Perez, Florian Strub, Harm De Vries, Vincent Dumoulin, and Aaron Courville. Film: Visual reasoning with general conditioning layer. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018
[55] David Pfau, Irina Higgins, Alex Botev, and Sébastien Racanière, Disentangling by subspace diffusion. Advances in Neural Information Processing Systems, 33:17403-17415 2020.
13

---

[56] Daniel Rosiak. Sheaf theory through examples. MIT Press, 2022.
[57]
Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 9())cnabb01, 2021.
[58] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Trans. Neural Networks, 20(1):61-80, 2008.
[59] Richard D Schafer. An introduction to nonassociative algebras. Courier Dover Publications, 2017.
[60] Luis Scoccola and Jose A Perea. Approximate and discrete euclidean vector bundles. arXiv preprint /0X.v:2/04.07563, 2021.
[61] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al magazine, 29(3):93 93,9999932200 2008.
[62] Allen Dudley Shepard. cellular description of the derived category of a stratified space. PhD thesis, Brown University, 1985.
[63] Amit Singer and H-T Wu. Vector diffusion maps and the connection laplacian. Commumications on pure and applied mathematics, 6568):1067-1144, 2012.
[64]
Alessandro Sperduti. Encoding labeled graphs by labeling RAAM. In NIPS, 1994.
[65] Julian Suk, Lorenzo Giusti, Tamir Hemo, Miguel Lopez, Konstantinos Barmpas, and Cristian Bodnar. Surfing the neural sheaf. In NeurlPS 2022 Workshop Symmetry and Geometry in Neural Representations, 2022.
[66] Jie Tang, Jimeng Sun, Chi Wang, and Zi Yang. Social influence analysis in large- scale networks. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. pages 807-816, 2009.
[67] Loring W Tu. Manifolds. In An Introduction Manifolds, pages 47-83. Springer, 2011.
[68] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
[69] Felix Wu, Tianyi Zhang, Amauri Holanda de Souza Jr, Christopher Fifty, Tao Yu, and Kilian Q Weinberger. Simplifying graph convolutional networks. ICMI., 2019.
[70] Louis-Pascal Xhonneux, Meng Qu, and Jian Tang. Continuous graph neural networks. In ICML, 2020.
[71] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In ICLR, 2019.
[72] Yujun Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, and Danai Koutra. Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks. arXiv:2102.06442. 2021.
[73] Fouad El Zein and Jawad Snoussi. Local systems and constructible sheaves. In Arrangements, local systems and singularities, pages 1 111-53.. Springer, 2009.
[74] Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gnns. In International Conference on Learning Representations, 2020. URL httpa:///penrrvview wtwperrwwwwweeeeeffrrtrea net/forum? id=rkecl1rtwB.
[75] Jiong Zhu, Yujun Yan. Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Be- yond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33, 2020.
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Proofs are included in the appendix
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes] Our code is avail- sheaf diffusi ion. (b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Section 6 and Appendix E
able at attpps://githnn con.//atttteeeeeeeeerrdlllll research/neuree
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] Appendix E
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes] Appendix F
(c) Did you include any new assets either the supplemental material or as URL? [Yes] The code of our submission.
(d) Did you discuss whether and how consent obtained from people whose data you're
using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
15


Reviews:
[{"review_id": "w3YZP6jB5Lr", "reviewer": "Reviewer_s77q", "summary": "This paper uses cellular sheaf theory to study the oversmoothing behavior of GCNs and their limitations in heterophilic graphs. Additionally, it proposes a novel deep convolutional model, the SCN, and extension of Kipf and Welling's GCN where one simultaneously learns the sheaf and the convolution weights.", "questions": "- Per the theorem statement, Theorem 18 only holds for the Leaky ReLU and ReLU nonlinearities. Would other nonlinearities (e.g., the sigmoid or the tanh) significantly change its result?\n- To improve the readability of the paper, a minor suggestion is to make the conclusions in lines 239-242 (that GCNs cannot linearly separate heterophilic bipartite graphs and graphs with more than two classes respectively) corollaries, or to highlight them somehow.", "limitations": "The main limitation of the paper is that its analysis only holds for the asymptotic case where $L\\to\\infty$ ($L$ is the number of layers). In well-connected graphs, using many message-passing layers leads to redundancy, so it is not hard to see how a deep architecture might exhibit oversmoothing. The authors should discuss this limitation more thoroughly (both in Section 8 and in the introduction), especially considering the fact that, in practice, many of the GCN architectures that exhibit good performance are not very deep.", "rating": 9, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The paper is clear, well-written, and easy to understand (especially given the complexity of the topic).\n\n- The technical contributions are timely and significant: Proposition 10 and Theorem 18 provide a possible explanation for why GCNs do poorly in node classification problems on heterophilic graphs, and Proposition 12 and Theorem 18 for why they do poorly in problems with more than two classes. In contrast, Proposition 13 and Theorem 16 show that general SCNs do not have these limitations because neural sheaf diffusion can achieve linear class separation, and that this separation can be achieved exponentially fast. At the same time, Proposition 17 shows that in SCNs the Dirichlet energy is not constrained to decrease (unlike in GCNs).\n\nWeaknesses:\n\n- The paper (specifically, Sections 4 and 5) lacks a more precise link between the specific theoretical results (propositions, theorems) and the specific problems (limitations associated with heterophily, oversmoothing) that they help explain. In particular, the link between the Dirichlet energy and oversmoothing can be made clearer. Another suggestion is to indicate, in the introduction or in the gray inserts, which theorems/propositions explain the heterophily and oversmoothing problems respectively.\n\n- The numerical experiments are convincing but limited.\n\n     - Synthetic experiments: in the main body of the paper, it would be more interesting to see results for $d>1$. The benefits of \n       asymmetric Laplacians and negative weights have been previously observed in the literature. Moreover, considering $d>1$ would \n       provide a better illustration of the generality of the model, as SCNs with $d>1$ cannot be reduced to GCNs. One suggestion is to \n       compare the ability of SCNs and GCNs to perform node classification on graphs with more than two classes.\n\n     - Real-world experiments: the gains in performance (w.r.t. to other GNN models) in Table 1 are not very significant, but the results are \n       competitive and the main contribution of the paper are its theoretical results.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "oobYeSSuvg5", "reviewer": "Reviewer_QFM1", "summary": "The paper proposes a new topological perspective of GNN. In the first part of the paper, the authors introduce the concept of “cellular sheaf” and “sheaf Laplacian” which allows defining a diffusive process over the graph. Interestingly, the ability of the diffusive process to correctly classify the nodes in the input labelled graph is strictly related to the class of the sheaves considered to define the process itself.\n\nThe continuous sheaf diffusion can be discretised using the Euler method to solve PDE, obtaining the sheaf convolution. The properties of the sheaf convolution are studied by observing how it affects the Dirichlet energy of the process.\n\nIn practice, the convolution sheaf operator is not known and should be learned from data. To this end, the authors propose three different convolution models that can learn the sheaf operator. In particular, the three alternatives are diagonal sheaf operators, orthogonal sheaf operators and general sheaf operators.\n\nThe experimental results show competitive performances against standard GNN models.\n", "questions": "1) Why are we interested in studying the Dirichlet energy of the sheaf convolutional network?\n2) From my understanding, it seems that we prefer sheaf convolutional networks that do not converge fast to the equilibrium (the zero-energy point). On the contrary, the property of the sheaf diffusion process is studied in the time infinite limit (that should be the equilibrium). Why is there this difference?\n3) How X(0) is computed? From my understanding, the node features are stored in a matrix N x F. Nevertheless, X(0) should be ND x F. Is an MLP used for this goal? Is the same MLP for all input features?\n4) How is the parametric matrix-valued function \\phi used? Is it used to build the sheaf Laplacian explicitly? Is the cost of evaluating \\phi considered in the computational complexity (I think it should be O(d^2) in the diagonal case)?\n5) The \\phi defined in the paper allows building only symmetric sheaf operators. While this allows to speed up the computation, it reduces the separation power. Are there any other options that could be considered to find a trade-off between complexity and power?\n\nMinors:\n1) In proposition 1, maybe W should have subscript 1.\n2) I suggest another capital letter (W is already used) to denote the parameter of the MLP which learns the sheaf operator.\n", "limitations": "Yes, the authors discuss the limitations of their work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is interesting since it applies topological concepts in the context of graph learning. To the best of my knowledge, the application of the sheaf theory in this context is novel. I believe that the most interesting result is the connection between the sheaf structure and the classification ability of the diffusion process associated with that structure.\n\nThe paper is well written and easy to follow. The only part that I found not clear is Section 5 (see questions). Also, I believe that more words could be spent explaining the experimental setting (see questions). \n\nFinally, it is hard to conclude that the proposed models outperform the baseline models due to the variance of the results. I do not believe that this reduces the impact of the paper, but I would change sentences such as “the models achieve state-of-the-art results” and similar ones.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "IjxzwXDucq3", "reviewer": "Reviewer_dwBG", "summary": "This paper investigates the heterophily and oversmoothing problems in graph neural networks through the lens of cellular sheaf theory, and reveals that these problems can be avoided by building a proper sheaf model upon graph that is suitable for the task. It also proposes NSD model based on the theory, which is latter verified effective in heterophilic graphs.", "questions": "See above.", "limitations": "I don’t think this paper has any negative societal impact. ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "In general, the idea of building a connection of sheaf theory and graph neural networks is somehow intriguing, and perhaps also fruitful in the sense that it provides a new perspective to understand heterophily and oversmoothing problems. The corresponding theoretical results about how a proper choice of the sheaf structure can help to solve these problems may greatly benefit our community. The mathematical analysis seem extensive and sound though I didn’t check the proof in the supplementary material. Experimental results also show that the proposed NSD model performs better especially in heterophilic graphs, which is in alignment with the theoretical findings. \n\nI think the downside of this paper is the readability. Since it is very likely that most of the interested readers from the graph learning community are not familiar with sheaf theory (or differential geometry and algebraic topology), the readability of this paper would improve greatly to add more intuitive explanations on abstract theoretical results, e.g., regarding why change of sheaf structure can affect model’s separation power. In addition, it appears that the theoretical results in Section 3 about the properties of harmonic space are only of analysis interest and their connection with rest of the paper is somehow loose. I suggest the authors to move some of the details to appendix or explain more about their connections if they are indeed crucial. \n\nI also have some concerns or questions regarding the implementation and experiments. \n1. The computation complexity seems to be large, which scales with the stalk dimension as O(d^3). Though one can use batched GPU computations for training as the authors pointed out, the scalability problem may still remain when in comes to making predictions in the inference stage.\n2. The paper seems to be missing a baseline, i.e., SheafNN [1], the predecessor of the proposed NSD. The authors also claimed that the proposed NSD is more powerful than SheafNN, so to what extent can NSD empirically outperform SheafNN?\n3. The authors claimed in Section 4 that higher stalk dimension and more complex restriction maps indicate better separation power. But does better separation power necessarily translate into better ability to handle heterophily? If this is the case, how does the performance of NSD change with increasing d and restriction map complexity?\n4. Table 4 shows the results of adding positional encodings, but what does it have to do with stalk dimension in the table captions? (p.s., ‘3.51 ± 5.05’ in the table seems to be wrong?)\n\n[1] Sheaf neural networks. In NeurIPS 2020 Workshop.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "-MlDIhQVnDu", "reviewer": "Reviewer_2nUo", "summary": "In this paper, the authors define a study a notion of graph neural networks that involves a notion of \"sheafs\" on graphs, which are vector spaces and linear operators attached to the nodes and edges of the graph. A givencellular sheaf thus defines a particular notion of message passing, where messages are transformed by the linear maps during propagation. This defines a generalized notion of Laplacian, as a block matrice involving the linear operators. The authors perform a basic harmonic study of this Laplacian, whose dominant eigenvector determines the infinite-time limit of the corresponding diffusion process. They study different classes of restricted sheafs, and their power to separate data by this diffusion process. Finally, a sheaf learning procedure is presented, similar to a generalized attention process.", "questions": "- in practice, there is no guarantee to learn effectively the right sheaf that will separate the data, is your asymptotic analysis robust to perturbed sheaf?\n- if you learn only a single for all layers to simulate the diffusion process, do you learn what is expected in your analysis? Eg on simple two-communities graphs?", "limitations": "Discussion is appropriate.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n- an original notion, grounded in algebraic geometry and topology, with an original instanciation on graphs\n- a quite complete investigation\n\nWeaknesses:\n- the paper could be more explicit regarding the relationship with the proposed model and existing ones. In particular, when the sheaf must be learned, unless I am wrong the proposed model falls under the classical paradigm of message-passing (but with a generalized notion of \"attention\" that compute matrices between nodes). So, all the Weisfeiler Lehman analysis still applies (for instance), and statements like the end of Sec 5 \"SCNs are more expressive than GCNs\" are a bit misleading.\n- Regarding this, the proposed architecture probably brings some implicit bias to the training, but it is difficult to which extent this really is more \"powerful\" than classical MPNNs (it seems SCNs could be, for instance, simulated with enough layers and MLPs). Moreover, in practice a different \"sheaf\" is learned at each layer, so it is not clear how the limit diffusion analysis is really observed in practice.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept