Sheaf4Rec: Sheaf Neural Networks for Graph-based Recommender Systems
Recent advancements in Graph Neural Networks (GNN) have facilitated their
widespread adoption in various applications, including recommendation systems.
GNNs have proven to be effective in addressing the challenges posed by
recommendation systems by efficiently modeling graphs in which nodes represent
users or items and edges denote preference relationships. However, current GNN
techniques represent nodes by means of a single static vector, which may
inadequately capture the intricate complexities of users and items. To overcome
these limitations, we propose a solution integrating a cutting-edge model
inspired by category theory: Sheaf4Rec. Unlike single vector representations,
Sheaf Neural Networks and their corresponding Laplacians represent each node
(and edge) using a vector space. Our approach takes advantage from this theory
and results in a more comprehensive representation that can be effectively
exploited during inference, providing a versatile method applicable to a wide
range of graph-related tasks and demonstrating unparalleled performance. Our
proposed model exhibits a noteworthy relative improvement of up to 8.53% on
F1-Score@10 and an impressive increase of up to 11.29% on NDCG@10,
outperforming existing state-of-the-art models such as Neural Graph
Collaborative Filtering (NGCF), KGTORe and other recently developed GNN-based
models. In addition to its superior predictive capabilities, Sheaf4Rec shows
remarkable improvements in terms of efficiency: we observe substantial runtime
improvements ranging from 2.5% up to 37% when compared to other GNN-based
competitor models, indicating a more efficient way of handling information
while achieving better performance. Code is available at
https://github.com/antoniopurificato/Sheaf4Rec.
Antonio Purificato, Giulia Cassarà, Federico Siciliano, Pietro Liò, Fabrizio Silvestri
# Sheaf Neural Networks for Graph-based Recommender Systems

###### Abstract.

Recent progress in Graph Neural Networks has resulted in wide adoption by many applications, including recommendation systems. The reason for Graph Neural Networks' superiority over other approaches is that many problems in recommendation systems can be naturally modeled as graphs, where nodes can be either users or items and edges represent preference relationships. In current Graph Neural Network approaches, nodes are represented with a static vector learned at training time. This static vector might only be suitable to capture some of the nuances of users or items they define. To overcome this limitation, we propose using a recently proposed model inspired by category theory: Sheaf Neural Networks. Sheaf Neural Networks, and its connected Laplacian, can address the previous problem by associating every node (and edge) with a vector space instead than a single vector. The vector space representation is richer and allows picking the proper representation at inference time. This approach can be generalized for different related tasks on graphs and achieves state-of-the-art performance in terms of F1-Score@N in collaborative filtering and Hits@20 in link prediction. For collaborative filtering, the approach is evaluated on the MovieLens 100K with a 5.1% improvement, on MovieLens 1M with a 5.4% improvement and on Book-Crossing with a 2.8% improvement, while for link prediction on the ogbl-ddi dataset with a 1.6% refinement with respect to the respective baselines.

Recommender systems, graph neural networks, link prediction, collaborative filtering +
Footnote †: conference: Proceedings in the 2015 ACM SIGKDD international conference on Knowledge and data mining, pp. 1-10. ACM, 2015.

+
Footnote †: conference: Proceedings in the 2015 ACM SIGKDD international conference on Knowledge and data mining, pp. 1-10. ACM, 2015.

+
Footnote †: conference: Proceedings in the 2015 ACM SIGKDD international conference on Knowledge and data mining, pp. 1-10. ACM, 2015.

+
Footnote †: conference: Proceedings in the 2015 ACM SIGKDD international conference on Knowledge and data mining, pp. 1-10. ACM, 2015.

+
Footnote †: conference: Proceedings in the 2015 ACM SIGKDD international conference on Knowledge and data mining, pp. 1-10. ACM, 2015.

+
Footnote †: conference: Proceedings in the 2015 ACM SIGKDD international conference on Knowledge and data mining, pp. 1-10. ACM, 2015.

+
Footnote †: conference: Proceedings in the 2015 ACM SIGKDD international conference on Knowledge and data mining, pp. 1-10. ACM, 2015.

+
Footnote †: conference: Proceedings in the 2015 ACM SIGKDD international conference on Knowledge and data mining, pp. 1-10. ACM, 2015.

+
Footnote †: conference: Proceedings in the 2015 ACM SIGKDD international conference on Knowledge and data mining, pp. 1-10. ACM, 2015.

+
Footnote †: conference: Proceedings in the 2015 ACM SIGKDD international conference on Knowledge and data mining, pp. 1-10. ACM, 2015.

+
Footnote †: conference: Proceedings in the 2015 ACM SIGKDD international conference on Knowledge and data mining, pp. 1-10. ACM, 2015.

+
Footnote †: conference: Proceedings in the 2015 ACM SIGKDD international conference on Knowledge and data mining, pp. 1-10. ACM, 2015.

+
Footnote †: conference: Proceedings in the 2015 ACM SIGKDD international conference on Knowledge and data mining, pp. 1-10. ACM, 2015.

+
Footnote †: conference: Proceedings in the 2015 ACM SIGKDD international conference on Knowledge and data mining, pp. 1-10. ACM, 2015.

+
Footnote †: conference: Proceedings in the 2015 ACM SIGKDD international conference on Knowledge and data mining, pp. 1-10. ACM, 2015.

+
Footnote †: conference: Proceedings in the 2015 ACM SIGKDD international conference on Knowledge and data mining, pp. 1-10. ACM, 2015.

+
Footnote †: conference: Proceedings in the 2015 ACM SIGKDD international conference on Knowledge and data mining, pp. 1-10. ACM, 2015.

+
Footnote †: conference: Proceedings in the 2015 ACM SIGKDD international conference on Knowledge and data mining, pp. 1-10. ACM, 2015.

+
Footnote †: conference: Proceedings in the 2015 ACM SIGKDD international conference on Knowledge and data mining, pp. 1-10. ACM, 2015.

+
Footnote †: conference: Proceedings in the 2015 ACM SIGKDD international conference on Knowledge and data mining, pp. 1-10. ACM, 2015.

+
Footnote †: conference: Proceedings in the 2015 ACM SIGKDD international conference on Knowledge and data mining, pp. 1-10. ACM, 2015.

+
Footnote †: conference: Proceedings in the 2015 ACM SIGKDD international conference on Knowledge and data mining, pp. 1-10. ACM, 2015.

+
Footnote †: conference: Proceedings in the 2015 ACM SIGKDD international conference on Knowledge and data mining, pp. 1-10. ACM, 2015.

+
Footnote †: conference: Proceedings in the 2015 ACM SIGKDD international conference on Knowledge and data mining, pp. 1-10. ACM, 2015.

+
Footnote †: conference: Proceedings in the 2015 ACM SIGKDD international conference on Knowledge and data mining, pp. 1-10. ACM, 2015.

+
Footnote †: conference: Proceedings in the 2015 ACM SIGKDD international conference on Knowledge and data mining, pp. 1-10. ACM, 2015.

+
Footnote †: conference: conference: Proceedings in the 2015 ACM SIGKDD international conference on Knowledge and data mining, pp. 1-10. ACM, 2015.

+
Footnote †: conference: conference: Proceedings in the 2015 ACM SIGKDD international conference on Knowledge and data mining, pp. 1-10. ACM, 2015.

+
Footnote †: conference: conference: Proceedings in the 2015 ACM SIGKDD international conference on Knowledge and data mining, pp. 1-10. ACM, 2015.

+
Footnote †: conference: conference: Proceedings in the 2015 ACM SIGKDD international conference on Knowledge and data mining, pp. 1-10. ACM, 2015.

+
Footnote †: conference: conference: Proceedings in the 2015 ACM SIGKDD international conference on Knowledge and data mining, pp. 1-10. ACM, 2015.

+
Footnote †: conference: conference: Proceedings in the 2015 ACM SIGKDD international conference on Knowledge and data mining, pp. 1-10. ACM, 2015.

+
Footnote †: conference: conference: Proceedings in the 2015 ACM SIGKDD international conference on Knowledge and data mining, pp. 1-10. ACM, 2015.

+
Footnote †: conference: conference: conference: Proceedings in the 2015 ACM SIGKDD international conference on Knowledge and data mining, pp. 1-10. ACM, 2015.

+
Footnote †: conference: conference: conference: Proceedings in the 2015 ACM SIGKDD international conference on Knowledge and data mining, pp. 1-10. ACM, 2015.

+
Footnote †: conference: conference: conference: Proceedings in the 2015 ACM SIGKDD international conference on Knowledge and data mining, pp. 1-10. ACM, 2015.

+
Footnote †: conference: conference: conference: Proceedings in the 2015 ACM SIGKDD international conference on Knowledge and data mining, pp. 1-10. ACM, 2015.

+
Footnote †: conference: conference: conference: conference: conference: conference: conference: conference: conference: conference: conference: conference: conference:: conference: conference: conference: conference: conference: conference: conference: conference: conference: conference:: conference:: conference: conference: conference:: conference: conference: conference: conference:: conference: conference: conference: conference: conference: conference:: conference: conference: conference: conference: conference:: conference: conference: conference: conference:: conference: conference: conference:: conference: conference: conference: conference: conference: conference: conference: conference: conference: conference: conference: conference: conference: conference: conference: conference: conference: conference: conference: conference: conference: conference:: conference: conference: conference: conference:: conference: conference: conference: conference: conference:: conference:: conference: conference: conference: conference: conference:: conference: conference: conference:: conference:: conference: conference: conference: conference: conference:: conference: conference: conference:: conference: conference:: conference: conference: conference: conference:: conference: conference:: conference: conference: conference:: conference: conference: conference:: conference:: conference: conference: conference:: conference: conference: conference:: conference: conference:: conference:: conference:: conference:: conference: conference:: conference: conference: conference:: conference: conference:: conference: conference:: conference: conference: conference:: conference:: conference: conference:: conference: conference:: conference: conference:: conference: conference:: conference: conference:: conference: conference:: conference: conference: conference:: conference: conference:: conference:: conference: conference:: conference: conference: conference: conference:: conference: conference:: conference: conference:: conference: conference: conference: conference:: conference: conference:: conference: conference:: conference: conference:: conference: conference:: conference: conference: conference:: conference:: conference: conference: conference:: conference: conference:: conference: conference:: conference: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference: conference:: conference:: conference: conference:: conference: conference:: conference:: conference:: conference:: conference:: conference:: conference: conference:: conference:: conference: conference:: conference:: conference: conference:: conference:: conference:: conference:: conference: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference: conference:: conference:: conference:: conference:: conference:: conference: conference:: conference: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference::: conference: conference:: conference:: conference::: conference:: conference:: conference:: conference::: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference::: conference:: conference:: conference:: conference:: conference::: conference: conference:: conference::: conference:: conference:: conference:: conference::: conference:: conference:: conference:: conference:: conference:: conference::: conference:: conference:: conference::: conference:: conference:: conference:: conference:: conference:: conference:: conference::: conference::: conference:: conference:: conference::: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference::: conference:: conference:: conference::: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference::: conference:: conference:: conference: conference:: conference:: conference:: conference: conference:: conference:: conference:: conference:: conference:: conference:: conference: conference:: conference: conference:: conference:: conference:: conference: conference:: conference:: conference: conference:: conference::: conference: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference: conference:: conference:: conference:: conference: conference: conference:: conference:: conference:: conference:: conference: conference:: conference:: conference:: conference:: conference: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference: conference:: conference:: conference:: conference:: conference:: conference:: conference: conference:: conference:: conference:: conference:: conference: conference:: conference:: conference:: conference: conference:: conference:: conference:: conference:: conference: conference:: conference:: conference:: conference: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference:: conference::: conference:: conference:: conference:: conference:: conference:: conference: conference:: conference:: conference: conference: conference:: conference
we are proposing, in this research, to use a novel class of GNN architectures: "_Sheaf Neural Networks_".

Sheaf Neural Networks (SNNs) are a recently proposed and novel class of Graph Neural Network models inspired by Category Theory. It has been used in many different tasks and has been proven superior to GNNs (Beng et al., 2015). In this class of models, the basic building blocks are _Cellular Sheaves_. Cellular sheaves associate a vector space with each node and edge of a graph and linear maps between these spaces. Simply put, Sheaf Neural Networks are Graph Neural Networks that operate over Cellular Sheaves (Beng et al., 2015). SNNs work by computing a generalization of the well-known Graph Laplacian, the so-called _Sheaf Laplacian_(Chen et al., 2016). Sheaf Laplacian is indeed a generalization of Graph Laplacian because when the vector spaces of the cellular sheaves are 1-dimensional, and we apply identity maps between them, then the two Laplacians are perfectly equivalent. The Sheaf Laplacian is computed via the restriction map in a non-parametric manner at pre-processing time (Beng et al., 2015).

Our research extends the results in the literature on the theory of SNNs, to two real-world problems: item recommender systems and link prediction. In particular, we show that applying SNNs to the task of graph-based recommender systems greatly improves the performance of both item recommender and link prediction systems. Experiments show that our proposed SNN-based models outperform all state-of-the-art models in the respective tasks. We show that in the case of recommendation, we outperform the state-of-the-art method by 5.1% on MovieLens 100k, 5.4% on MovieLens 1M and 2.8% on Book-Crossing. In the case of link prediction, we have a 1.6% improvement on the ogbl-ddi dataset.

The innovative contributions of this research work are the following:

* We propose a novel architecture for products and link recommender systems based on Sheaf Neural Networks that achieve state-of-the-art results in their respective tasks.
* We demonstrate the relation between our model and the use of the Bayesian Personalised Ranking loss function using different experiments.
* We perform extensive experiments on multiple datasets for top-N recommendation and link prediction tasks, which verify our solution's rationality and potential. Experimental results show that SNNs outperforms all the other baselines on the two tasks we focus on in this paper. In recommendation tasks, we beat the state-of-the-art method by 5.1% on MovieLens 100k, 5.4% on MovieLens 1M, and 2.8% on Book-Crossing. In the case of link prediction, we have a 1.6% improvement on the ogbl-ddi dataset.

The rest of the paper is organized as follows. Section 2 shows recent works in the current literature. Section 3 gives a background to Graph Neural Networks and sheaf theory. Section 4 explains our approach. Section 5 shows some implementation details as the dataset choice and the setting for the experiments. In section 6, we demonstrate the effectiveness of the proposed solution, and we conclude in 7 with pointers to future ideas.

## 2. Related Work

This section introduces some examples of state-of-the-art recommender systems.

### Deep learning-based recommender systems

We can distinguish between two categories in the existing DL-based recommendation models. For every category, it is shown an example.

* Recommendation based on neural building blocks (Han et al., 2015): the DL technique determines the recommendation model's applicability. For example, MLPs can simply model the non-linear interactions between users and items; CNNs can extract local and global representations from heterogeneous data sources like text and image; recommender systems can model the temporal dynamics and sequential evolution of content information using RNNs.
* Recommendation based on deep hybrid models (Zheng et al., 2016): this technique is based on a mix of deep learning techniques that change depending on the task. One common idea is to mix long-term and short-term networks to model long-term preferences and short-term preferences. Usually, this approach achieves better results with respect to the previous one.

Zheng et al. (Zheng et al., 2016) first convert a user's implicit feedback into a "like" vector and a confidence vector, and then they model the probability of the "like" vector, weighted by the confidence vector.

Dong et al. (Dong et al., 2015) propose a hybrid model which jointly performs deep users and items' latent factors learning from side information and collaborative filtering from the rating matrix. The output of this model approximates the predicted rating, and then a list of ranked items is generated for each user based on these prediction ratings.

### Autoencoder-based recommender systems

Autoencoder is an unsupervised model attempting to reconstruct its input data in the output layer. In general, the bottleneck layer (the middle-most layer) is used as a salient feature representation of the input data (Sachdeva et al., 2017). The main variants of Autoencoders can be considered as denoising Autoencoder (Wang et al., 2017) or variational Autoencoder (VAE) (Sachdeva et al., 2017). There are two ways to apply Autoencoder to a recommender system:

* Using Autoencoder to learn lower-dimensional feature representations at the bottleneck layer.
* Filling the blanks of the interaction matrix directly in the reconstruction layer.

Sachdeva et al. (Sachdeva et al., 2017) introduce a recurrent version of the VAE, where instead of passing a subset of the whole history regardless of temporal dependencies, they pass the consumption sequence subset through a recurrent neural network. At each time-step of the RNN, the sequence is fed through a series of fully-connected layers, the output of which models the probability distribution of the most likely future preferences.

Han et al. (Han et al., 2015) improve the previous idea. They first pre-train an autoencoder with the local kernelised weight matrix, which transforms the data from one space into the feature space by using a 2d-RBF kernel. Then, the pre-trained autoencoder is fine-tuned with the rating matrix, produced by a convolution-based global kernel, which captures the characteristics of each item.
Background

We briefly review the necessary background to understand the solution we propose. We start by summarizing the main characteristics of GNNs, and we then introduce cellular sheaf theory to finally present the learning algorithm we use: _Neural Sheaf Diffusion_.

### Graph Neural Networks

The rise of GNN mainly originates from the advancement of convolutional neural network (CNN) and Graph Representation Learning (GRL) (Goh et al., 2017). When applied to regular Euclidean data such as images or texts, CNN is extremely effective in extracting localized features. However, for non-Euclidean data like graphs, CNN requires generalization to handle the situations where operation objects (e.g., pixels in images or nodes on graphs) are non-fixed in size. In terms of GRL, it aims to generate low-dimensional vectors for graph nodes, edges, or subgraphs, which represent complex connection structures of graphs.

A graph is represented as \(G=(V,E)\), where \(V\) is the set of nodes and \(E\) is the set of edges. The set of edges can also be described by an adjacency matrix \(A\). Let \(v_{i}\in V\) be a node and \(e_{ij}=(v_{i},v_{j})\in E\) be an edge pointing from \(v_{j}\) to \(v_{i}\). \(A\) is defined as:

\[A_{ij}=\begin{cases}1\text{ if }\ e_{ij}\in E\\ 0\text{ otherwise}\end{cases} \tag{1}\]

The neighbourhood of a node \(v\) is denoted as:

\[N(\mathbf{o})=\{\mathbf{u}\in V\mid(\mathbf{o},\mathbf{u})\in E\} \tag{2}\]

The degree matrix of \(G\) is a matrix \(D\) which contains information about the number of edges attached to each vertex.

\[D_{ij}=\begin{cases}degree(i)\text{ if }i=j\\ 0\text{ otherwise}\end{cases} \tag{3}\]

Using the definition of degree matrix \(D\) and adjacency matrix \(A\) the Laplacian can be easily defined as:

\[L=D-A \tag{4}\]

Given the graph data, the main idea of GNN is to iteratively aggregate feature information from neighbours and integrate the aggregated information with the current central node representation during the propagation process. From the perspective of network architecture, GNN stacks multiple propagation layers consisting of aggregation and update operations. The formulation of propagation is:

\[Update:H^{(I)}=f(H^{(I-1)},A) \tag{5}\]

\[Aggregate:H^{(I)}=\sigma(D_{\mathbf{o}}^{-\frac{1}{2}}AW^{0}D_{\mathbf{e}}^{-1 }D_{\mathbf{o}}^{-\frac{1}{2}}W^{(I)}) \tag{6}\]

Where the aggregation function is for a hypergraph neural network. \(\sigma\) is the activation function, \(D_{\mathbf{o}}\) and \(D_{\mathbf{e}}\) denote the diagonal matrices of the edge degrees and the vertex degrees, respectively.

### Sheaf theory

A cellular sheaf \((G,\mathcal{F})\) on an undirected graph \(G=(V,E)\) consists of:

* A vector space \(\mathcal{F}(\mathbf{o})\) for each \(v\in V\);
* A vector space \(\mathcal{F}(\mathbf{e})\) for each \(v\in E\);
* A linear map \(\mathcal{F}_{v\ni\mathbf{e}}:\mathcal{F}(v)\rightarrow\mathcal{F}(e)\) for each incident node-edge pair \(v\trianglelefteq e\);

The vector spaces of the node and edges are called stalks, while the linear maps are called restriction maps. Given a sheaf \((G,\mathcal{F})\) we define the space of 0-cochains \(C^{0}(G,\mathcal{F})\) as the direct sum over the vertex stalks:

\[C^{0}(G,\mathcal{F})=\bigoplus_{v\in V}\mathcal{F}(v) \tag{7}\]

The space of 1-cochains \(C^{1}(G,\mathcal{F})\) is the direct sum over the edge stalks.

Given some arbitrary orientation for each edge \(e\) we define the co-boundary map:

\[\delta:C^{0}(G,\mathcal{F})\to C^{1}(G,\mathcal{F})=\delta(x)_{e}= \mathcal{F}_{v\trianglelefteq e}x_{\mathbf{o}}-\mathcal{F}_{u\trianglelefteq e}x_{u} \tag{8}\]

The sheaf Laplacian of a sheaf is defined as:

\[L_{\mathcal{F}}=\delta^{T}\delta=\sum_{v,u\trianglelefteq e}\mathcal{F}_{v \trianglelefteq e}^{T}(F_{v\trianglelefteq e}x_{\mathbf{o}}-F_{u\trianglelefteq e}x_{u}) \tag{9}\]

It can be seen how the sheaf Laplacian is strictly related to the Laplacian defined in 4 but considers restriction maps instead of edges. In fact, the sheaf Laplacian is a generalization of the graph Laplacian that encodes additional relational structure parameterized by the underlying graph. The normalised sheaf Laplacian \(\Delta_{\mathcal{F}}\) is defined as:

\[\Delta_{\mathcal{F}}=D^{-\frac{1}{2}}L_{\mathcal{F}}D^{-\frac{1}{2}} \tag{10}\]

With \(D\) block-diagonal of \(L_{\mathcal{F}}\).

### Neural sheaf diffusion

Given a graph \(G=(V,E)\) where each node of the graph \(v\in V\) has a \(d\)-dimensional feature vector \(x_{\mathbf{o}}\in\mathcal{F}(v)\) we construct an \(nd\)-dimensional vector \(x\in C^{0}(G,\mathcal{F})\) by column-stacking the individual vectors \(x_{\mathbf{o}}\). We produce the feature matrix \(\mathbf{X}\in\mathbb{R}^{(nd)\times f}\) where the columns of \(\mathbf{X}\) are vectors in \(C^{0}(G,\mathcal{F})\).

Sheaf diffusion is a process on \((G,\mathcal{F})\) governed by the following differential equation:

\[\mathbf{X}(0)=\mathbf{X},\ \ \ \mathbf{X}(t)=-\Delta_{\mathcal{F}}\mathbf{X}(t) \tag{11}\]

which is discretised via the explicit Euler scheme with unit step size:

\[\mathbf{X}(t+1)=\mathbf{X}(t)-\Delta_{\mathcal{F}}\mathbf{X}(t)=(\mathbf{I}_{ nd}-\Delta_{\mathcal{F}})\mathbf{X}(t) \tag{12}\]

In the model used by (Bang et al., 2017) the previous equation is discretised in the following way:

\[\mathbf{X}(t+1)=\mathbf{X}(t)-\sigma(\Delta_{\mathcal{F}(t)}(\mathbf{I}_{ \mathbf{o}}\otimes\mathbf{W}_{1}^{t})\mathbf{X}_{t}\mathbf{W}_{2}^{t}) \tag{13}\]

With the sheaf \(\mathcal{F}(t)\) and the weights \(\mathbf{W}_{1}^{t}\in\mathcal{R}^{d\times d}\) and \(\mathbf{W}_{2}^{t}\in\mathcal{R}^{f\times f}\) time-dependent, meaning that the underlying geometry evolves.

## 4. Method

### Collaborative filtering

We consider the information that a generic user embedding would have at each layer of the GNN. The user nodes are the input embeddings provided to the model in the input Layer, as shown in Figure 2. After the input Layer, a new item embedding is generated and is passed to Layer 1. The user node embedding will then get updated with a new item embedding containing semantic information related to its connected users. Note that, during this layer, the nodes
learn not only from the embedding they obtained in the input Layer but also from this new embedding. In Layer 2 the previous item embedding is updated with a new one. In this way, we try to cluster users with the same item interests. As a result, the user node in the final layer will gain knowledge about the embeddings of users 2-hops away in the GNN.

Semantically, in terms of recommendations, we have made this user's node embedding more similar to other users who share the same item interests. The reason behind the choice of node embedding is straightforward: at the node level, an embedding vector is generated with each node in the graph. This embedding vector can hold the graph representation and structure. At each step, the user's node embedding is more similar to other users who share the same item interests. Essentially, nodes in close proximity should also have vectors in close proximity to each other.

One advantage of our approach is that the connection between the proposed embedding and the architecture is extremely easy. SNN takes as input an embedding vector with the modified representation of users and items and the size of the graph (sum of the number of users and items). Then all the information from the embedding is stored in the corresponding vector spaces. The complete process can be found in Figure 1.

#### 4.1.1. Loss function

A surrogate loss function is used to enable efficient gradient-based optimization and also to work in the best way with sheaves. Specifically, we use the Bayesian Personalized Ranking (BPR) loss as the surrogate. To understand BPR, we need to define the notion of positive and negative edges: positive edges are those that exist in the graph and negative edges are those that don't.

In our bipartite graph, we can define the score of the user \(u\) for the item \(v\) is:

\[f_{\theta}(u,v)=e_{u}^{T}e_{v} \tag{14}\]

Where \(e_{u}\) is the embedding related to the user \(u\) and \(e_{v}\) is the embedding related to the item \(v\). Consequently, we can define for the user \(u\) the set of all positive edges containing \(u\) as \(s(p)=f_{\theta}(u,v_{pos})\) and the set of all negative edges containing u as \(s(n)=f_{\theta}(u,v_{neg})\). The BPR is:

\[BPR(u)=\sum_{p,n}-ln(\sigma(s(p)-s(n)) \tag{15}\]

To efficiently estimate the BPR loss and optimize \(f_{\theta}\), we train the model by sampling mini-batches. For each mini-batch, we sample the set of users and for each user sample one positive item (the item from a positive edge containing the user in question) and one negative item.

### SheafNN and recommendation

The improvements in this work are due to the use of topology. Since SNN works using sheaves we need to use an update function based on simplicial complexes (Bordes and T
\[m_{B}^{t+1}(\sigma)=AGG_{\tau\in B(\sigma)}(M_{B}(h_{\sigma}^{t},h_{ \tau}^{t})) \tag{16}\] \[m_{\uparrow}^{t+1}(\sigma)=AGG_{\tau\in N_{\uparrow},\beta eC( \sigma,t)}(M_{\uparrow}(h_{\sigma}^{t},h_{\tau}^{t},h_{\beta}^{t})) \tag{17}\]

The update function is:

\[h_{\sigma}^{t+1}=\bigcup\left(h_{\sigma}^{t},m_{B}^{t}(\sigma),m_{\uparrow}^{t +1}(\sigma)\right) \tag{18}\]

\(\sigma,\tau\) and \(\delta\) are cells while \(B\) represents a boundary. The update function \(h\) receives as input two different types of messages \(m_{B}\) and \(m_{\uparrow}\).

Our network transforms a standard graph into a sheaf. An example of a sheaf can be found in Figure 3.

We consider the node \(V\) as the user \(V\) and the node \(U\) as the user \(U\). We work in the following way:

\(\mathcal{F}(U_{e})\) is the vector space containing all the opinions of \(V\) that we split into positive and negative opinions and the same is for \(\mathcal{F}(U_{u})\) and user U. Up to this moment the main difference is that the information about a certain user is stored in the corresponding vector space.

\(U_{e}\) is the edge containing all the items in common between the two users. The features of the item are modelled into the vector space \(\mathcal{F}(U_{e})\). Every iteration of the training updates these features for all the users. From the previous chapter, we also know that \(f_{\theta}(u,v)=e_{u}^{T}e_{e}\) is the score for the user \(u\). But with this representation, we have the user embedding into \(\mathcal{F}(U_{u})\) and the item embedding into \(\mathcal{F}(U_{e})\). As a result, the score can be simply found in the restriction maps \(\mathcal{F}_{u\in\mathcal{E}}\) and \(\mathcal{F}_{\sigma\in\mathcal{E}}\) and the more we train our network the higher the score. For this reason, we have chosen to use the BPR loss, in fact with this representation it is extremely simple to be computed.

### Link prediction

The goal of SNN is to learn the embeddings of each node and to use them to predict edges in the graph. But SNN computes node embeddings for all nodes in the graph, but what we want to do is make predictions on pairs of nodes. For this reason, it is created a module in pairs of node embeddings (i.e., an edge) that classifies if the edge connecting two drugs exists or not. This module is a simple neural network called Link Predictor.

The Link predictor (shown in Figure 4) takes the element-wise product of the real-valued embedding vector of \(2\) nodes (\(h_{i}\) and \(h_{j}\)) and computes the probability score of whether there exists a link between the \(2\) nodes through a multi-layer perceptron.

Also in this case it is created a node embedding. The creation of the embedding is of primary importance for the training. Since the task is different, SNN is used differently. Given two generic nodes \(U\) and \(V\), the vector space \(\mathcal{F}(U_{u})\) associated to node \(U\) contains information about the molecule \(U\) and the same for \(V\). The restriction maps \(\mathcal{F}_{u\mathcal{E}\mathcal{E}}\) and \(\mathcal{F}_{v\mathcal{E}\mathcal{E}}\) contain information about the interaction between \(U\) and \(V\). During the training at every iteration the vector space \(\mathcal{F}(U_{e})\) related to the edge \(e\) and the restriction maps are updated with new features about the corresponding molecules. Also in this case SNN takes as input simply the embedding vector computed in the previous step.

#### 4.3.1. Loss function

The objective is to maximize the probability of correct edges (positive predictions \(p\)) while minimizing the probability of incorrect edges (negative predictions \(n\)). The loss function is the following:

\[\mathcal{L}=-\mu(ln(p))+\mu(ln(1-n)) \tag{19}\]

Where \(\mu\) represents the mean.

## 5. Experiments

In this section, we test the performance of Sheaf Neural Networks on two different tasks: collaborative filtering and link prediction. For collaborative filtering, three different datasets are used: MovieLens 100k, MovieLens 1M and the Book-Crossing dataset. For link prediction, it is used the ogbl-ddi dataset.

### Datasets description

#### 5.1.1. Book-Crossing dataset

The Book-Crossing dataset (Song et al., 2016) is a collection of user ratings of books. It comes with both explicit ratings (1-10 stars) and implicit ratings (user interacted with the book). It is composed by 278858 members of Book-Crossing and 1157112 ratings, referring to 271379 distinct ISBNs.

#### 5.1.2. MovieLens

MovieLens 1M dataset contains around 1 million anonymous ratings of approximately 3900 movies by 6040 users, where each user rated at least 20 items.

MovieLens 100k dataset contains around 100k anonymous ratings of approximately 1700 movies by 1000 users, where each user rated at least 20 items. The ratings in MovieLens 1M and MovieLens 100K datasets are made on a 5-star scale, with 1-star increments. In both datasets, each user is described by demographic info (age, gender, occupation).

A good way to visualize the interactions in a recommender system is by using a bipartite graph with the users and items (movies in this case) as nodes and edges between them indicating user-item interactions. The graph will be bipartite because users can be interested in items, but items and users can't be interested in other items or users, respectively.

#### 5.1.3. ogbl-ddi

This dataset contains 4,267 nodes and 1,334,889 edges representing the drug-drug interaction network. In the ogbl-ddi dataset, each node represents an FDA-approved or experimental drug. Edges represent interactions between drugs and can be interpreted as a phenomenon where the joint effect of taking two drugs together is considerably different from the expected effect in which drugs act independently of each other. It is implemented a protein-target split, meaning that drug edges are split according to

Figure 3. Sheaf structure. It is possible to see the stalks associated with each node and the restriction maps.
what proteins those drugs target in the body. As a result, the test set consists of drugs that predominantly bind to different proteins from drugs in the train and validation sets. This means that drugs in the test set work differently in the body, and have a rather different biological mechanism of action than drugs in the train and validation sets.

### Competitors

We compare our model with various baselines and current state-of-the-art models including recently published neural architectures and we now present a brief summary of our competitors to provide a better understanding of these models.

#### 5.2.1. Collaborative filtering

* CoFM (Krishnan et al., 2017) jointly trains FM and TransE by sharing parameters or regularization of aligned items and entities.
* MVAE (Krishnan et al., 2017) is an extension of variational autoencoders (VAEs) to collaborative filtering for implicit feedback.
* SVAE (Savaghi et al., 2018) is an improvement of MVAE using sequential VAEs based on a recurrent neural network.
* LinUCB (Liu et al., 2019) is a multi-armed bandit approach which recommends items to the user based on the contextual information about the user and items.
* SVD (Krishnan et al., 2017) is a popular algorithm utilizing Singular Value Decomposition for the process of recommendation.
* DeepMF (Wang et al., 2018) is a state-of-the-art neural network architecture based Matrix Factorization Method for recommendation.
* MDP (Krishnan et al., 2017) works as a reinforcement learning agent modeling collaborative filtering as a Markov Decision Process (MDP).
* LibFM (Liu et al., 2019) is a widely used feature-based factorization model for CTR prediction.
* RippleNet (Wang et al., 2018) is a memory-network-like approach that propagates users' preferences on the KG for recommendation.
* KGNN-LS (Wang et al., 2018) transforms the graph into a weighted graph and uses a GNN to compute item embeddings.

#### 5.2.2. Link prediction

* Node2Vec (Chen et al., 2017) learns a mapping of nodes to a low-dimensional space of features that maximizes the likelihood of preserving network neighbourhoods of nodes.
* SEAL (Wang et al., 2018) learns a function mapping the subgraph patterns to link existence.
* GCN (Glorot et al., 2017) is based on an efficient variant of convolutional neural networks which operate directly on graphs.
* GraphSAGE (Chen et al., 2017) leverages node feature information to efficiently generate node embeddings for unseen data.

### Metrics

#### 5.3.1. Collaborative filtering

We use three evaluation metrics that have been widely used in previous work:

* Precision@N: It is the fraction of the items recommended that are relevant to the user. We compute the mean of all the users as final precision;
* Recall@N: It is the proportion of items relevant to the user that have been successfully recommended. We compute the mean of all users as final recall.
* F1-score@N: It is the harmonic mean of precision at rank N and recall at rank N.

#### 5.3.2. Link prediction

The performance is evaluated by Hits@20: each true drug interaction is ranked among a set of approximately

\begin{table}
\begin{tabular}{c c c} \hline \hline  & MovieLens 100k & MovieLens 1M \\ \hline Number of users & 943 & 6040 \\ Number of items & 1682 & 3952 \\ Number of ratings & 100000 & 1000029 \\ Number of all genres & 19 & 18 \\ Average number of genres & 1.7 & 1.6 \\ \hline \hline \end{tabular}
\end{table}
Table 1. Main stats about MovieLens 100k and MovieLens 1M.

Figure 4. Link predictor architecture. It takes as input \(h_{i}\odot h_{j}\) and outputs the probability of a link between node \(i\) and node \(j\).
100,000 randomly-sampled negative drug interactions, and count the ratio of positive edges that are ranked at 20-place or above.

## 6. Results

All the experiments were performed on a single NVIDIA RTX A6000 with 10752 CUDA cores and 48 GB RAM. In all the experiments different values of seed are used to see how the results of the models change with the split.

### ogbl-ddi

In this section, we test the performance of SNN on the ogbl-ddi dataset. During the comparison, the learning rate and the weight decay are fixed and equal to 0.003 and 0.0005, respectively. The model is trained with Adam optimizer, and 300 epochs are performed, completing the training phase in about 18 hours. Training our model takes quite a long time due to the inherent complex structure of SNNs, and the operations performed make computing the backpropagation algorithm less time efficient than other architectures.

It is important to notice that the variance of our results, compared to our competitors, decreases consistently. Our network is less affected by variations in the parameters than the other architectures making our method stable and, therefore, fitter to be used in different problems.

We run statistical tests on the results obtained by our models on this task to assess the significance of the differences. We used the student's unpaired t-test between our predictions and the predictions of our competitors with independent and identically distributed samples. By selecting \(p=0.05\) we demonstrated that our results are statistically significant if we compare them against GraphSage, GCN, and Node2Vec.

### MovieLens 1M

In this section, we test the performance of SNN on MovieLens 1M. We used a 90-10 train-test split. 90% of the samples are used for training and 10% for testing. This is the most common example of a split for this dataset. During the comparison, the learning rate and the weight decay are fixed and equal to 0.005 and 0.0001. The model is trained with a computational time of 210 minutes. The selected size for the embedding vector is 64; consequently, the input size of SNN is 64.

We use as a loss function the BPR loss, as explained in chapter 4. For the sake of completeness, we also experimented with different loss functions. In recommender systems, the most common example of a loss function is the Root Mean Squared Error (RMSE) loss. We also tested our approach using this loss function, but our experimental results show that the F1-Score was lower. The main advantage of BPR over RMSE is on the computational time. Table 3 shows that BPR is up to 50% faster than RMSE. We also tested Binary Cross-Entropy (BCE) loss. In this case, the efficiency of the method was comparable, but the performance in terms of F1-Score was much worse. Thus, we also did not consider this loss when training our models.

The choice of F1-Score@10 and F1-Score@100 as evaluation metrics is not random. In fact, by choosing \(N=10\) and \(N=100\) we are working with tho different sizes for the sets of relevant items for the users. The most common recommender systems based on graphs have a high F1-Score@N for small values of N. In our case also with high values of N the F1-Score is really high. In Figure 5 it is possible to compare our result with other state-of-the-art systems and we demonstrate that our solution is able to achieve good performance also with high values of \(N\). In this Image was not possible to represent the values of F1-Score@N for values of \(N>50\) because the other approaches obtained very bad results. Finally, in Table 4 we can see that SNN outperforms all the baselines in terms of F1-Score and Recall.

In Figure 6 we have tested the value of F1 when increasing the number of returned recommendations, \(K\). We can observe that F1-Score starts decreasing for \(K>60\). This is different from our competitors, where this value ranges between 20 and 40. This experiment shows that this architecture can achieve good results also when we produce a high number of recommended, and potentially relevant for the users, items. For example, consider MovieLens. The MovieLens dataset contains movie ratings, therefore, the higher the number of movies that we are able to recommend the more satisfied the user.

### MovieLens 100K

In this section, we test the performance of SNN on MovieLens 100k. We used an 80-20 train-test split. 80% of the samples are used for training and 20% for testing. The value of the hyperparameters is different from the previous experiment: the learning rate is fixed at 0.001 while the weight decay is 0.0002. The model is trained with

\begin{table}
\begin{tabular}{c c c} \hline \hline Model & Validation Hits@20 & Test Hits@20 \\ \hline Node2Vec & 0.329\(\pm\)0.012 & 0.233\(\pm\)0.021 \\ SEAL & 0.285\(\pm\)0.027 & 0.306\(\pm\)0.039 \\ GCN\({}^{\dagger}\) & 0.555\(\pm\)0.021 & 0.370\(\pm\)0.051 \\ GraphSAGE \({}^{\dagger}\) & 0.626\(\pm\)0.037 & 0.539\(\pm\)0.047 \\
**SNN (our)**\({}^{\dagger}\) & **0.632\(\pm\)0.036** & **0.555\(\pm\)0.044** \\ \hline \hline \end{tabular}
\end{table}
Table 2. Results of the evaluation using the ogbl-ddi dataset. SNN has a 32% improvement on the test hits with respect to the baseline and a 1.6% improvement with respect to the best model. \(\dagger\) means statistically significantly (Student’s unpaired t-test, p \(<\) 0.05)

\begin{table}
\begin{tabular}{c c c c} \hline \hline Loss & \#Layers & F1-Score@10 & Time \\ \hline RMSE & 2 & 0.112 & 283 \\ RMSE & 5 & 0.148 & 371 \\ BCE & 2 & 0.087 & 198 \\ BCE & 5 & 0.101 & 262 \\ BPR & 2 & 0.163 & 163 \\ BPR & 5 & 0.192 & 210 \\ \hline \hline \end{tabular}
\end{table}
Table 3. Performance of the same model using different loss functions and numbers of layers. The computational time is in minutes, \(\downarrow\) is better.
Adam optimizer and 50 epochs are performed with a computational time of 30 minutes. It is possible to see how our solution outperforms all the baselines in terms of F1-Score. The results can be seen in Table 5.

One of the advantages of SNN is the possibility of preventing over-smoothing. Deeply stacking the number of layers does not decrease the performance. In a lot of GNNs the features become progressively smoother with increased depth (Krizhevsky et al., 2017). In our case, the best results are obtained using 5 layers, as shown in Figure 7.

### Book-Crossing

In this section, we test the performance of SNN on Book-Crossing. During the comparison, the learning rate and the weight decay are fixed and equal to 0.001 and 0.0005. The model is trained for 70 epochs with a computational time of 251 minutes using as loss function the BPR loss. The computational time is a bit higher with respect to the previous experiments because the dataset is bigger and also contains a lot of side information, so the processing time is higher. In this experiment, we obtained better results by setting the selected size for the embedding vector to 32. As we can see in Table 6 we outperform the state-of-the-art results both on Recall@10 and Recall@100.

## 7. Conclusions and Future Work

Associating each node and each edge with a vector space is an effective strategy to sequence recommendation. To prove this, we used our architecture SNN, and the experimental evaluation highlights the capability of SNN to outperform state-of-the-art models on two different tasks consistently.

\begin{table}
\begin{tabular}{c c c c c c c} \hline \hline Model & Precision@10 & Recall@10 & F1-Score@10 & Precision@100 & Recall@100 & F1-Score@100 \\ \hline \hline MVAE\({}^{\dagger}\) & 0.090 & 0.091 & 0.091 & 0.054 & 0.414 & 0.096 \\ SVAE\({}^{\dagger}\) & 0.144 & 0.125 & 0.134 & 0.069 & 0.494 & 0.121 \\ CoFM\({}^{\dagger}\) & **0.321** & 0.130 & 0.178 & 0.354 & 0.135 & 0.189 \\
**SNN (our)** & 0.284 & **0.145** & **0.192** & 0.122 & **0.520** & **0.198** \\ \hline \hline \end{tabular}
\end{table}
Table 4. Results of the evaluation using the MovieLens 1M dataset. SNN has a 5.4% improvement on F1@10 with respect to the baseline and a 0.7% improvement with respect to the best model.

Figure 5. F1-Score values on MovieLens 1M compared with state-of-the-art solutions. The value of F1-Score for CAKR (Krizhevsky et al., 2017), RippleNet (Zhu et al., 2017) and Ripp-MKR (Ripp et al., 2018) goes down extremely fast. The value of the F1-Score of our model goes down less fast.

Figure 6. The value of F1-Score of our solution starts decreasing with a value of K between 60 and 70.

\begin{table}
\begin{tabular}{c c c c c c c} \hline \hline Model & Precision@10 & Recall@10 & F1-Score@10 & Precision@20 & Recall@20 & F1-Score@20 \\ \hline LinUCB\({}^{\dagger}\) & 0.321 & 0.135 & 0.192 & 0.286 & 0.203 & 0.238 \\ SVD\({}^{\dagger}\) & 0.343 & 0.163 & 0.222 & 0.282 & 0.245 & 0.272 \\ DeepMF\({}^{\dagger}\) & 0.344 & 0.160 & 0.219 & 0.314 & 0.244 & 0.262 \\ MDP\({}^{\dagger}\) & **0.357** & 0.168 & 0.228 & **0.313** & 0.251 & 0.278 \\
**SNN (our)** & 0.210 & **0.287** & **0.243** & 0.265 & **0.309** & **0.285** \\ \hline \hline \end{tabular}
\end{table}
Table 5. Results of the evaluation using the MovieLens 100k dataset. SNN has a 5.1% improvement on F1@10 with respect to the baseline and a 1.5% improvement with respect to the best model.

\(\dagger\) is used when the results are taken from the original paper.
These results finally prove the applicability of algebraic topology to machine learning tasks. In the future, we are interested in using this architecture in new studies. Thanks to its topological structure, we think this network could obtain good results on different applications storing the side information of the nodes in the corresponding stalks. A possible future direction could be the Next Point-Of-Interest recommendation to provide users with where to go and how to plan the day based on previous visits as well as current status or feature selection.
