Recommender Systems using Graph Neural Networks

Key Takeaways

hey there based on your latest votes we will have a look at recommender systems using gnns today in the first part of this video i will talk a bit about classical recommendation methods and then we will have a look at some examples using gnns before we get started i wanted to emphasize that recommender systems are a huge research field and there is no way to capture everything in this short video i will however include the most basic concepts and ideas to get you started recommender systems have a lot of applications from e-commerce like amazon recommending suitable products to social media platforms like pinterest or instagram and also entertainment such as netflix movies spotify music or of course youtube the main motivation for recommenders is to reduce the huge amount of items to a small tangible subset people nowadays are overloaded with content and with these systems we can filter out the relevant items and also discover new things that might be interesting the two most popular classical approaches for recommender systems are content-based filtering and collaborative filtering content-based filtering uses the similarities between items to recommend items that the user might like for example if you watch the first part of harry potter a likely recommendation would be the second part similarities can be calculated based on all sorts of item features such as name content type or producer collaborative filtering on the other hand uses the similarities between the user to filter out elements that can be recommended the basic idea is that users with similar purchase history will also like similar things collaborative filtering is often modeled as a matrix completion problem that can be visualized in such a grid the values in the grid represent ratings from users for specific items and obviously we don't have that for all the items that's why the task is to fill up the missing cells a very popular method to fill up these cells is called matrix factorization it maps the users and items to embeddings that are arranged in the same embedding space these are also called latent factors and the whole thing is then called latent factor model so here you can see that every user and item has a bar next to it which represents a learned embedding vector that represents the user or item characteristics this vector can contain obvious features but also totally uninterpretable values in order to map the latent codes into the same embedding space a dot product between the user vectors and the item vectors is used as similarity measure for this the item matrix is transposed so that the shapes match this dot product generates the predicted matrix on which high values indicate that a user item combination matches and low values that we should better not recommend this item formerly this predicted rating matrix can be expressed like this this means we are decomposing the matrix r into the product of two lower ranked matrices we initialize the latent code somehow for example randomly and because we have the true ratings for some of these cells we can very easily optimize the latent codes with respect to some loss functions such as mean squared error this matrix factorization idea has many extensions such as considering user biases for the ratings including additional features or also considering temporal effects when you think about it we decompose the values of this matrix in such a way so that each of the latent factors contains typical characteristics of that product or item and this is already some sort of representation learning however this is based on a matrix today we want to have a look at how we can model this as a graph representation task this matrix can quite easily be represented as a graph and not any type of graph but a bipartite graph so this is simply a graph that consists of two sets one user set and then an item set and then you have connections between these different nodes and this is the most common form of modeling graph based recommender systems in a few minutes we will also see some alternative ways how we can arrange this graph in this most basic form a connection between a user and item simply means that the user has interacted with this item in some way if available we can also extend the edge information with an edge weight that corresponds to the rating from this point it's very easy to build a graph neural network that performs link prediction which means it predicts which user and items match with the highest probability one immediate advantage of gnns compared to matrix factorization is that they are able to aggregate multi-hop neighborhoods whereas matrix representations typically only account for direct connections for the next minutes i want to invite you to a journey through some of the literature on this topic and i hope that you enjoy it one of the earlier works using gnns comes from fondenberg kipf and welling and is called graph convolutional matrix completion the rating matrix on the left is converted into a bipartite graph and the edges are enriched with the rating scores each user and item is represented by a feature vector the heart of the model is a graph auto encoder which has a task to compress the edge information in such a way that it is possible to reconstruct it from the compressed representation to do so the bipartite graph is sent through several message passing layers in order to learn a representation for each user and item these layers also consider the different rating types are and apply different transformations per type then link prediction is performed based on the final item and user embeddings as a formula this can be expressed like this which means the users are multiplied with items and a learnable transformation queue is applied finally softmax is used to predict probabilities for the different edge types are in some sense this is very similar to the matrix completion problem we've seen before we learned some embeddings for the users and items which were the latent codes previously and used them in the end to predict the cells on the matrix the big difference is the way how these embeddings are generated which is based on message passing here another gnn based recommender model is called pinsage and was developed by researchers from pinterest and stanford university on pinterest the users can have boards on which they pin items they are interested in such as images recipes clothes and more of course these items can be shared among the boards and modeled as a graph we end up with another bipartite graph so far so good the only issue is that they have really a lot of items available which makes this graph too big to fit into the gpu memory in fact their data set has 18 billion edges and 3 billion nodes pin sage is a scalable gnn model that can handle such big graphs by sampling a neighborhood around a node this allows the model to train on a subset of the nodes but generate embeddings even for unseen data overall this idea is based on graph sage which also uses sampling to make the learning process inductive the difference is however that the sampling is based on random walks or more specifically the visit count of random walks which assesses the importance of specific nodes and this means the size of the neighborhood can be reduced significantly they also propose some parallelization patterns that can speed up the training you might have asked yourself how the nodes are represented in this graph what do we use as node features we can't simply use an image or a text we need to compress it somehow and the images were converted into embeddings using a vgg16 cnn model and all of the text was converted with a word to wag model as a result each node could be represented by a combined vector of visual and textual information in the end this model produces embeddings in a joint embedding space which can be used to find their nearest neighbor in order to recommend related pins so far we were only looking at bipartite graphs without further information there are how many many works that additionally exploit the social network of the users this is then typically called social recommendation and it's pretty straightforward the fundamental idea is that people are most of the time heavily influenced by their friends or colleagues and therefore this relationship can be used to propose better recommendations two popular papers in this field are diffnet plus plus and graph rack both of them apply separately for the social space and the user item network graph attention layers to capture the information of the neighborhood in the end those vectors are simply concatenated and used to predict the ratings besides social recommendation there is also knowledge graph based recommendation which additionally exploits features from a connected knowledge graph there is one more type of recommendation systems i want to mention here and those are sequential recommenders a typical scenario is the following a user buys a sequence of items first a table then a monitor and a keyboard and finally some headphones based on this purchase history what might be the next item it seems like he's building a home office setup and therefore an office chair is probably a good recommendation this can also be based on the purchase history of other users that might have already bought this item now how do you model this setup as a graph representation learning task a recently published paper called dynamic gnns for a sequential recommendation uses temporal gnns to learn spatial and temporal embeddings the first step is to convert these item sequences per user into a graph representation this is done by building a dynamic graph let's have a look at our previous example to see how this could look like a dynamic graph is simply a graph that changes over time in this case the edges between the items and users depend on the time step when we look at the specific time step t in this case t2 the graph snapshot might look like this so we have three interactions from each of the users and only the edges of the current and past interactions are part of this graph other items and users can also be part of the graph but are maybe not connected so far the task is then to predict which item a user is connected to next in the paper a graph snapshot is defined as follows users u items i a time step t and additionally information about the ordering of the interactions this is simply a counter that tells us how many interactions a user or item already has this allows the model to also learn sequential information so overall this is also just a bipartite graph but just with an additional temporal dimension and additionally we have this ordering information two time steps later the graph might look like this as you can imagine this graph would explode over time as it just keeps growing because of that the authors only sample the most recent interactions so now i think the dynamic graph should be clear and the next step is to pass this graph through a spatiotemporal gen n which is called dynamic gnn here as you might know i've already uploaded a video for these kinds of models and here we simply have a special variant of it this message passing is separated into item user propagations and user item propagations this effectively means that there are two embedding spaces one with the user focus and the other one with the item focus in both cases the model learns long-term dependencies and short-term dependencies the long-term dependencies are modeled with gated recurrent units and represent general characteristics of a node the short-term dependencies represent the latest properties of a nodes and are modeled with an attention mechanism between the last interaction and all other interactions for further details the paper is linked in the video description this module is stacked several times for example 3 as in the paper for a specific user the embeddings after each layer are then combined and used to perform link prediction with a set of candidate items this can then be optimized with a cross-entropy using the labels of the chronologically next interaction by the way this reminds me a bit of next token prediction in nlp problems so i hope this video helps you to get started with graph based recommender systems also here are some data sets you can use to build gnn recommenders all of them are part of python geometrics so you can easily download them but you might need to do some adjustments here and there based on your project with that have a great day and see you soon in the next video