PinSage - Graph Convolutional Neural Networks for Web-Scale Recommender Systems | Paper Explained
❤️ Become The AI Epiphany Patreon ❤️ ► https://www.patreon.com/theaiepiphany
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬

In this video, I do a deep dive into the PinSage paper!

It was the first application of the GNN as a huge scale recommender system such as the one at Pinterest.

You'll learn about:
✔️All the nitty-gritty details behind PinSage

▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 
✅ paper: https://arxiv.org/pdf/1806.01973.pdf
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 

⌚️ Timetable: 

00:00 Intro to PinSage and Pinterest
02:40 High-level overview of engineering innovation
05:40 MapReduce framework - a quick overview
08:00 Quick overview of the algorithm
09:10 High-level overview of algorithmic innovation
10:15 Tasks and related work
13:00 Problem setting (bipartite graph)
14:40 Detailed explanation of the algorithm
18:00 Neighborhood sampling and importance pooling
21:45 Model training and supervised data
23:50 Max margin ranking loss function explanation
29:18 Negative (hard) samples and curriculum learning
35:30 Pin features and baselines description
39:00 Offline evaluations and metrics (hit-rate, MRR)
43:00 Analysis of the embedding space (cosine sim)
45:15 User studies and A/B testing
49:00 Embedding space visualizations (t-SNE)

▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 
💰 BECOME A PATREON OF THE AI EPIPHANY ❤️ 

If these videos, GitHub projects, and blogs help you,
consider helping me out by supporting me on Patreon! 

The AI Epiphany ► https://www.patreon.com/theaiepiphany
One-time donation: 
https://www.paypal.com/paypalme/theaiepiphany 

Much love! ❤️
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 

💡 The AI Epiphany is a channel dedicated to simplifying the field of AI using creative visualizations and in general, a stronger focus on geometrical and visual intuition, rather than the algebraic and numerical "intuition". 

▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 
👋 CONNECT WITH ME ON SOCIAL 
LinkedIn ► https://www.linkedin.com/in/aleksagordic/ 
Twitter ► https://twitter.com/gordic_aleksa 

Instagram ► https://www.instagram.com/aiepiphany/ 
Facebook ► https://www.facebook.com/aiepiphany/ 

👨‍👩‍👧‍👦 JOIN OUR DISCORD COMMUNITY:
Discord ► https://discord.gg/peBrCpheKE

📢 SUBSCRIBE TO MY MONTHLY AI NEWSLETTER:
Substack ► https://aiepiphany.substack.com/

💻 FOLLOW ME ON GITHUB FOR COOL PROJECTS: 
GitHub ► https://github.com/gordicaleksa 

📚 FOLLOW ME ON MEDIUM:
Medium ► https://gordicaleksa.medium.com/
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬

#pinsage #graphneuralnets #recommendersystems
 Continuing with the graph neural network series and this video I'm covering graph convolutional neural networks for web scale recommender systems or Pinsage for short and as you can tell by the title of the video is going to be more about like this huge Engineering system that's deployed at Pinterest and then about novel Algorithms like propagation rules or something like that. So anyways One thing worth mentioning is that this is a direct continuation of the graph sage Paper which I've covered in my previous video. So if you don't know anything about graph sage It's probably a good idea to just go and check out that video. I'll link it somewhere in the in somewhere here So basically the authors are basically the same Rex, Ying, Hamilton and Leskowitz Were the authors on graph sage paper and we have some additional authors for Pinsage here. Mm-hmm So let me start we describe a large scale deep recommendation engine that we developed and deployed at Pinterest And I so happened to have opened a new account today. So let me just show you how it all functions So basically and why I'm showing you this is because they're they're training Pinsage for two specific recommendation tasks the first one is this home feed a recommendation where basically the goal is to give you To give you like yeah most relevant pins on your home feed and the reason I'm mostly having like a motor cars here and motorbikes is Because the only pin I have is of a muscle car so initially I just picked some categories and What Pinterest did was it gave me pretty much uniformly for from all of those categories a couple of pins And what I did I went and pinned a certain pin and now I'm pretty much getting related pins to the last pin I've made And we'll see that in the paper They actually explicitly mentioned that that's how this home feed our recommendation works and it seems they haven't changed that thing so another task they are doing is if I open a specific pin and What they do here is they they offer you this list of similar pins. So more like this So these are the related pins to the pin you're just chosen and There is also aside from the concept of a pin. They have something called boards and so this user Harry saved this particular pin to this board V road and basically boards just Just basically Accumulate similar like similar pins in a logical unit and that's that's everything I wanted to cover Let me get back to the paper So they say here we deploy pinsage at Pinterest and train it on 7.5 billion examples on a graph with 3 billion nodes representing pins and boards in 18 billion edges So hopefully because I went through the platform if you if you're not familiar with Pinterest this will kind of contextualize Both the problem and how how everything fits together. So let me let me start and show you the some engineering innovations they introduced as well as some algorithmic innovations so first off they say here traditional GCN algorithms perform graph convolutions by multiplying feature matrices by powers of the full graph laplation and what that basically means if you if you if you're familiar with GCN and here I'll just open I'll open this paper which I've covered in one of my previous videos and you can see the update rule for GCN and Basically this part the a tilde part is in a structure similar to laplation even though it's not laplation and That's what they're basically saying they're saying that you need to store this whole huge adjacency or laplation matrix which is m by n where n is the number of nodes and in the case of Pinterest we have like 3 billion nodes at a time that the paper was written and so basically that's not that's not An option at all. So let me let me get back here So what it did as is the same as in graph sage they basically they are just sub sampling the neighborhoods Although they are not Doing uniform sampling they're doing something more clever and I'll get to that in a bit The second thing worth mentioning is that they have so on the on the engineering side is that they have this producer consumer pipeline and basically what it means is that We have in so in parallel the cpu is Preparing mini batches while the gpu is doing propagations and then you can just optimize and sync them so that GPU is never starving and they say it here cpu bound producer efficiently samples node network neighborhoods a gpu bound TensorFlow model consumes those And thirdly they have this efficient map reduce inference and why do they have this well basically? and we'll see that in a bit a bit in a bit more detail, but the the Pinterest graph is huge and what they do is they train the Pinsage model only on a subset of that huge graph and once they have the model trained They just use this map reduce pipeline to basically compute the embeddings for every single other node in the graph That's pretty much it So they say it here that can so map reduce pipeline can distribute the trained model to generate embeddings for billions of nodes While minimizing repeated computations, so that's this is the the the important part and Just on a small tangent. Let me let me quickly explain the map reduce pipeline and it's really simple So I thought it's worth mentioning it Basically here on an example This is a canonical example of doing uh finding out word frequencies in a document in documents And here is just a toy example with three sentences You can imagine a huge corpora here like imagine transformers which have multiple terabytes of textual data Which needs to get somehow maybe like the word frequency needs to get calculated And here on this example what happens is we basically have two modules We have this mapping part and we have the reduce part and hence the name mapping use and basically Inside the mapping module. We first just split the data. So here every single sentence will go there in in a separate module and what then happens is we we just map those parts those those Those samples of data into key value pairs and in this example of figuring out the frequencies of the words, we basically end up with like a Deer having one bear one, etc. And then what we do is we shuffle which is basically clustering These key value pairs by the key and we end up with these And finally the reduce stage sums these values up And it depends on how you define those reduce and map scripts And finally just aggregate those And you get the final result every single word has its frequency associated with it and this is a simplified example, obviously You'll have multiple shuffling and reducing stages in a in a in a real production system. So again It's supposed to minimize repeated computations and If you're familiar with graph sage, this will be really This image will make sense If not, i'll just i'll briefly do an overview as well here But like the repeated computations are these here. So basically the node a This computation here is the same as this one here and the same as this one here So what map reduce does is it it does this projection only once? For every single node in the graph and thus saves us a lot of computation unnecessary computation So that's the role of map reduce And on a short note how this works is the following so let me take I'll just ignore Because this is these are two layers of the pin sage algorithm I'll just ignore one layer and i'll focus on the on a single layer and basically to calculate For a specific node and you can see a toy graph here and we are interested in this target node So to calculate the representation of this node a what we do is the following so we basically concatenate it It's it's last layer representation with the aggregated neighborhood representation which we again get by doing some aggregation And in pin sage they introduce this thing called important sampling important spooling and i'll i'll explain that in a lot more detail a bit later But for now just this is some aggregation function like in graph sage you had max pooling you had lstms means so this is something similar And so what we do is we take the neighbors you can see b c and d are the neighbors of a here so we take those neighbors We just project their representations here and we aggregate them and that's how we get the aggregated portion So that's how the algorithm works in a nutshell There are a couple of innovations which i'll now briefly do a high level of and so these are the innovations in algorithmic sense Basically they don't do they show that the random sampling uniform land random sampling they used in graph sage is suboptimal So they do this thing called importance pooling where they are basically picking the the the those those neighbors which have the most influence on the target node And that will get clear in a couple of minutes So they say here an additional benefit is that each node now has an important score and those scores will be used in this importance pooling I'll explain that a bit later one more algorithmic innovation is this curriculum training where basically the algorithm is fed harder and harder negative examples And we'll we'll see what those exactly are in a couple of minutes So that's a high level overview of what the both the engineering as well as the algorithmic innovations are And now i'm going to slowly dig into details of this paper So first first things first the tasks as I mentioned are related pin recommendation and home feed recommendation tasks and we saw that on the platform itself So just keep that in mind So in terms of the algorithmic design they they are basically as I said continuing the graph sage paper so the work on that paper and they took a couple of ideas from from fast gcn by Chen and his collaborators Basically the the importance pooling part those ideas were borrowed from from from this paper And again engineering details and I'll have a lot of these throughout the video because this this this this paper is there is a lot of engineering that went into this this work so I think it's just worth mentioning some of them and I'll omit like most of them but I still want to mention a couple of them So we fundamentally improve upon graph sage by removing the limitation that the whole graph be stored in a GPU memory so basically they are using that producer consumer pipeline so we don't have to hold the whole graph in GPU you hold it in CPU and that's where the producer is and then the GPU the consumer just takes many batches and basically that's how it trains Okay one more thing to note they they they they mentioned here why we can't use those shallow graph embedding methods so like deep walk and note to work the reason is they basically have for every single embedding is stored in the table in a lookup table so this table would be huge like because this is in and it's a number of notes and because Pinterest has like multiple like billions of notes This is like pretty much intractable and not only that but it's also inherently transacting methods which means you will have to get re-optimized to get when new pins are introduced into the system which is also not desirable and lastly these methods only use the co-occurrence statistics of the graph and they can use the features and as you probably can assume pins in in the graph pins in in in this graph have a rich features associated with them because they have like imagery and they have like maybe some let me just draw something here okay and they have they also have textual information associated with them so these methods can even make use of these so yeah that that those are multiple reasons why you just can't use those graph embedding methods for this task okay let's let's continue and see how they structure how they model the the the problem so basically the model of the the the graph the following so you have on one side you have pins or more generally items and on one side you have you have boards or more generally collections and what they do is they just create a by by part of the graph where basically as we saw one board has multiple related pins associated with with it so this is how the the graph will look like something like this and they mentioned they have around two billion pins and about one billion boards so this is how the the graph looks like and yeah I mentioned this pins are associated with both rich text and image features and the goal is to leverage both the features and the graph structure to to find those embeddings which can later be used to recommend related pins etc okay so now that we know how the problem is structured and what the what the tasks are and let's dig into some details yeah by the way they treat both the pins and the boards as the same nodes even though only the pins basically have features so they say here for notational convenience in generality when we describe the pin sage algorithm we simply refer to the node set of the full graph with V so it's a union between items and collections and they do not explicitly distinguish between pin and board nodes okay this is the algorithm basically if you're familiar with graph sage it has the same structure same old structure so here this one line corresponds to this line concatenation corresponds to this line and normalization corresponds to this line there are a couple of innovations though the first one is how they sampled the neighborhood that's the first innovation the second one importance pooling and that's pretty much it there is not a lot of new things that happen here everything else pretty much remain the same so a couple more nodes before I explain the importance pooling and before I explain the neighborhood they empirically so they say here empirically we observe significant performance gains when we look at the operation instead of the average operation as in 21 which is GCN paper so basically this year they showed empirically that it's better to use concatenation than just the thing that GCN did and that's just pretty much scaled weighted mean of these features and secondly normalization part so this part here in line three makes training more stable and it's more efficient to perform approximate nearest neighbor search for normalized embeddings and I'll explain what that is in a sec so first normalization what it does is basically make sure that all of our embeddings lie on a hypersphere and there's just a fancy name saying a sphere in higher dimensions if that sphere was in three dimensions and that sphere was in three dimensions then that sphere is a hyper sphere and that's the only thing that's important to know about this so basically we have we have that sphere lying around the coordinate beginning and all of the embeddings would lie on the edge of that sphere hopefully you can see that so again maybe here we have a huge sphere and all of the embeddings lie somewhere on this sphere all of our pins all of our boards lie somewhere on this sphere so they say here so it's more efficient to perform approximate nearest neighbor search so why do we care about approximate nearest neighbor search in this context so the reason is pretty simple so once you have so you basically have the embedding space and you embed your pins like maybe you'll maybe take this motorcycle and you'll embed it here and that's pin one and then you'll have all of the pins embedded and basically if you want to do related pin recommendation what you pretty much do is you find the k nearest neighbors to this target node p1 so if you're if I'm interested what the related pins to the motorcycle are I just find the closest ones and now because there are so many embeddings in this space so there are billions of embeddings we can't do exact nearest neighbor so they just use methods such as locality sensitive hashing to which are really good approximative methods to to do k nearest neighbors so that's why they mention nearest neighbors here and so normalization helps helps calculate those those nearest neighbors okay with those details out of the way let me explain the two most important parts and that's neighborhood and important sampling so basically this is what looks like we have a target node and we have its neighborhood so this is the one hop neighborhood this is the two hop neighborhood three hop et cetera so what we do basically is the following we take a bunch of random walks which are decently short and we we run them in parallel and what we do is we just count up the number of wizards every single node had so this one maybe had two wizards this one had only one visit maybe some of them had three wizards like this one maybe had three this one maybe had three and we basically take the t nodes that had the highest visit count and that's it so t was 15 there in their scenario so one thing worth mentioning is that these random walks are not biased and what that means is basically if you're at this node you'll go to your next node will be one of the neighboring nodes with equal probability contrast that to biased nodes such as so node2vec for example method used biased biased random walks where if you you have some parameters there like p and q and depending how you set them up you'll either prefer going in like a bfs manner so breadth first search or you'll be preferring depth first search traversals of the graph so here we just have pure unbiased random walks we we figure out we run multiple of them and in parallel and we just find the counts and that's the that's our neighborhood so for example if t was if t was maybe three we only take this neighbor we take this neighbor and we take this one and so how does that fit in into important sampling well it's pretty easy once you think of it so basically what we do is we take the their visit counts and we just normalize them by the sum so this will be a three three and two that's eight so we'll have the final weights will be this and then the importance pooling part just works you just take these weights you sum up their projected representations and so you multiply the representations the projected representations by these weights so this one so this representation this feature vector will get multiplied by this one and this feature vector will get multiplied with this weight and you just sum them up and that's the gamma part that's the importance pooling part so contrast that the graph sage which has just had max pooling and there we didn't have these weights we just find the like element wise max and that's that's the difference okay so they say they mentioned here the neighborhood of a node u is defined as the t-notes and I mentioned that's 50 that exert the most influence on node u and you it's pretty much intuitive that all of those nodes which had the highest visit counts are in a sense the most influential ones because we have the highest probability of visiting them they are the most connected in a way to our target node u and again about the importance pooling we implemented gamma as a weighted mean with weights defined according to the l1 normalized visit counts which is the thing I just explained and they refer to this as importance pooling so that those are the main innovations they had but there are some more things that I want to cover so let's just continue with model training so if you remember a graph sage how graph sage was trained it was basically trained either in an unsupervised manner using negative sampling or we had task specific supervised loss like cross entropy in the case of classification so here pin sage uses this thing called max margin ranking loss and we'll see what that is in a sec but before that what's the data so the goal of the training phase is to optimize the pin sage parameters so that the output embeddings of pairs query and i from this set l in the labeled set are close together so what's this set l so basically what it is is the following they just tracked the engagement on pinterest so if you for example had if you were playing with pin q and the first next pin that you opened or interacted with had an engagement with was pin i then they just put this pair in this set l they just add this pair to this set l and that's how they collect basically the supervised data set just through natural engagement of users on pinterest they through time get a huge huge training set l okay now let's jump in understand how the loss works and i'll i'll skip through this mini batch version of the algorithm i just showed you because it's equivalent to the graph sage algorithm they just instead of working on the whole pinterest graph they just take a subset and they just work on on that sub graph instead of using the whole graph so i'll just keep it for now and let's focus on the loss function and this is this is interesting part so basically the following happens so as zq z and q all of these are the final representations that you end up having after you run the pin sage algorithm so you end up with these as the vectors and once you have them what you do is the following so you have you have q which is the query query embedding and you have positive samples which is z i and you have negative samples which is n k and the goal here is the following you basically want to make sure that the similarity between q and i which is by definition a related pin this thing should be bigger than the similarity between q and this negative sample by at least a margin so for example if this similarity was three and the margin was which is a hyper parameter itself so if the margin was two that means we need to make sure that this part is at least five five or bigger five plus and why is that because we have a max between zero and this term here which means the loss goes to zero once this becomes negative and this becomes negative once this part once this part becomes bigger than the similarity between the query and negative sample plus the margin so that's this this portion of the loss now if you're like me you you're probably confused or you were confused at one point of your life with this part the expected value and what this basically says is the following so the higher the probability of a certain negative sample the more important it is to minimize its associated term here so let me let me try and visualize that here so basically first maybe a mathematical definition of what expected value is maybe it will be for some of you will make sense so expected value of a random variable x and some function g of x where this small x is just one of the possible outcomes of this random variable big X is the following is just a plain sum of the probability of those outcomes times the value of the function g at that particular outcome x and let me now contextualize and associate these two so g of x is basically this part this max part and let's see where the p part comes from so if we have a graph like this if we have a graph and we have a couple of notes and maybe this is the query node and this is the the the related node that's ground truth because of the engagement and the way how Pinterest collects these so we know this is the related one and we know this is the query pin so now let's say there are a couple there so every other pin every other node in the graph is a potential negative sample assuming that this is the only related pin to query pin so what we do is the following so let's let's say that during the training we maybe take seven times we take this this node as a negative sample as the NK so remember the notation we had ZNK so seven times maybe we take this one one time maybe we take this one zero times and this one two times so basically what happens is because this one was this one was sampled most oftenly seven times compared to two and one it's really important to minimize its associated values so g of x had to be as close to zero as possible right because we'll have we'll have one time one time something so the last will be one times x plus two times so this is two times its loss that's y plus seven times times Z where Z is the loss value associated with this negative sample so that means it's the most important so the most important thing we can do is minimize this part so because this is the highest the highest the highest number and if we translate these into probabilities into empirical probabilities because we had ten times we draw negative samples ten times this will be seven over ten this will be two over ten and this will be one over ten and that's where the p of x comes from so basically we have zero point seven times this max and we that's the reason we want to make sure that the higher the probability we want to make sure that the term is the lowest okay hopefully this wasn't too much confusing okay let me continue what else again some engineering details we design a producer consumer pattern to run GPU computation at the current iteration and CPU computation at the next iteration in parallel so that's what I mentioned already and this further reduces the training time by almost a half so even though conceptually this is a small thing like it's a really hard engineering problem and b it led to like a huge improvement in efficiency of the algorithm and training time okay and one more engineering detail is that they are to improve efficiency when training with large batch sizes we sample a set of five hundred negative items to be shared by all training examples in each mini batch so they won't be finding for every single node they won't be figuring out the negative examples they'll just pre compute five hundred negative items and they'll be sharing those for different query and related pins enough about engineering details let's let's see one more important part algorithmically so however ensuring that the inner product of the positive example so pair of items q and i is larger than that of the q and each of the five hundred negative items is too easy and why is it too easy because if you take a random negative example from the huge data set they have like a multiple billions of pins there is a huge probability that will be totally different from the related pins and that means it's really too easy to to optimize this this problem and here they show so they show an example of what they mean and they make of what they mean and they mentioned here so to solve the above problem for each positive training example so the item pair q and i we had hard negative examples so we make a distinction between hard negative examples and like maybe easy and negative examples and you can see here visually basically this is a query so we have some flower on an embroidery and then we have a positive example so that's the eye pin had this image and you can see it's also an embroidery and it's also flower so a random negative example so the easy negative sample would be this so this is neither embroidery and it's neither a flower so just some random hat and this is the hard example because it is embroidery so it's a similar in a way similar to these two but the content is a bird instead of a flower so that's what what what makes it hard okay so now that we know that let me see what they what they do and how they calculate how did they figure out these a hard example so they are generated by ranking items in a graph according to their personalized page rank scores with respect to the query item q items ranked at 2000 to 5000 are randomly sampled as hard negative items so a page rank is you probably heard of it page rank is Google initial the initial algorithm that Google use for research and intuitively it just looks at the edges and using that finds how important certain web page or element in general is important depending on how many links point to that particular note so what I do is they take the query pin and they just calculate these personalized page rank scores they just saw them by the score and they just take for example from 2k to 5k they consider so there's just a simple some heuristic they they figure out makes sense and they just randomly sample elements from from this subset and those are the hard hard examples in the training and for the part so this part tells us about the curriculum learning so in the first epoch of the training no hard negative items are used so that the algorithm quickly finds an area in the parameter space where the loss is relatively small at each epoch epoch and the training we had and minus one hard negative items to the set of negative items for each item so that means in epoch to they'll be adding one so that's a minus one so they'll be adding only one hard example as the epoch progress at epoch 10 they'll be adding nine negative items to the set of negative items for each item and that's how they progressively stimulate and make it harder to to optimize that loss okay that was that was all I had to say about the like some of the some some things were about engineering some things about were about algorithmic innovation and now let's switch topic a little bit and see how they how they tested this thing and what they what they did so again just just a fun fact so so for the home feed recommendation task we select the pins that are closest in the embedding space to one of the most recently pinned items by the user and if you remember I initially showed you that I have bunch of cars here and the reason and motorcycles now because I was interacting with a motorcycle but like basically they are they are the the the last pin you made is heavily influences this home feed recommendations and I can just empirically see that and verify it although it's not as simple as we saw like this motorcycle me engaging with this pin change my home feed here okay so again I mentioned this day they defined the set tell by using the historical user engagement data okay before we we we we see some results let me just detail a little bit how the features for every single pin are constructed so basically every single pin has some image associated with it so that some image and then we have also have some annotations so textual information and this notice also has some connections with some other notes so how they construct the final feature vector is the following so they past the image through a VGG network so there's just a convolutional neural net and they take one of the flat one of the feed forward activations and they use that as one part of the feature vector then they use they do a virtual back the train a virtual back model on the annotations and they embed the annotations also in a I think it was 256 dimensional vector and they concatenate these two and finally they add the log of the degree of this note of this particular pin so this is the degree so maybe this note has just ignore these so we have four four four notes connecting to this one so we'll just add log four as a feature so in a general case log the I where this is no I and this is the degree of the note and now that we know how the feature vectors are constructed for the pins for pins in pins age let's see how the baselines are constructed we have this visual baseline which basically does the following so for every single pin it just takes the image that's associated with that pen and does the same thing as pins age so just passes it through a VGG network takes out those features from certain fully connected layer and embeds that directly uses that as the final embedding and so once you embed that into so once you embed this thing into embedding space how you recommend how this simple baseline recommends is just using canerous neighbors so the same as as pin stages he just has a much less delicate method it doesn't use it doesn't use the graph information the graph structure it's a content recommender system okay second baselines super similar just uses only annotations instead of the image so it uses textual information third one combines both of those entrains MLP on top of them and finally the fourth one is pixie which uses random walks to find the the the the recommendations and basically doesn't use the those features just uses the random walks so that's the method that was previously used in production at Pinterest okay and yeah they don't compare with other methods because basically the scale is so huge that none of the previous methods could be simply used in this setting finally they just modify pins age and in a couple of ways and use those as baselines as well so here this max pooling one uses instead of using the importance pooling it uses max pooling and it just doesn't use those hard negative samples which I showed you previously so yeah that's the those are the baselines and now we'll see the results again some engineering details huge pages hadoop which is an open source implementation of the map reduce framework which I previously showed you and explained you so yep let's see the results yeah unfortunately these are not metrics you're probably familiar with so let me just briefly explain why what these are so we have something called hit rate hit rate and we have something called mean reciprocal rank and what hit rate is is the following so basically you have the query pin and you have the related pin I which we got by collecting like through engagement data right and so now our recommender system basically gives out a list of related pins to this query pin and the length of this list is K which is a hyper parameter and they used 500 in this paper so now what the hit rate is is the following so we're interested whether this ground truth pin is somewhere inside the recommended recommended pins if it is we that's a good thing if it's not that's a bad thing and basically hit rate just tells you going through the test set so going through various cues these cues and various eyes you basically see the percentage of time that the ground truth pin appeared in your recommendations and okay looking at that you can see that pinsage has 67% hit rate compared to these simple baselines like visual annotation and the combined one is combined one is better as expected than purely using like text or images and pinsage is also better than all of these maybe simpler baselines of pinsage so the second metric is this mean reciprocal rank and you can see the formula here and let me just make some sense out of it so basically it's super similar to hit rate except that we are interested into where exactly this pin this ground truth pin I appeared so let's assume that among the recommended items pins we we we did have this pin I and it was a location maybe 256 then that's much worse than having it the location one right so if we'd ideally want to recommend this ground truth pin somewhere closer to position one and that's that's this our term here and they just sum up those values and they just divided by the number of nodes in the test and that's it and if you take a look and the hundred is just hard coded so it's just empirically chosen value so that once we have so that we can distinguish when this is on one position to 1000 versus 2000 and that should make that will still make difference otherwise if this wasn't here the difference between what one over 1000 one over 2000 is super small and this makes it bigger so that's the reason they put the conjures here and again looking at the mixed reciprocal rank we can see it greatly improves with pinsage so those those were the offline evaluations they also did a be testings and user studies and I'll get into those in a minute but first one more important analysis they did is the exploration of the embedding space that the pins age method created against these baselines so the annotation visual baselines so basically what it did so they they took the embedding so you have a bunch of pins and they're embedded and you just took take two random pins and their embeddings and you do the cosine similarity so basically you're interested in the so if these are embedding vectors so you're interested in cosine of the angle between them cosine theta and you just plot that and you'd ideally one day to be distributed as as much as possible because that means they are not there not all the embeddings are similar and similarly oriented you want to have them or if they're if you pick the random pins you want to have them randomly distributed in space oriented in space so looking at the graph here you can see that the the pin sage has the most distributed curve here and the worst one is this one because it's highly it's really close to to one so you get one once you have because all of the embeddings remember they are they are normalized to unit length unit norm so that means this what you get one only when the vectors of the both embeddings totally coincide and if you if you if you take a look at the annotation baseline you can see it has the worst results it's 14 percent hit rate against 17 and 0.9 and so it's it's the worst method and these curves here tell the same thing pretty much and if you can introduce some fancy mathematics into this statistics so basically the court curdosis statistical measure of the cosine similarities of pin sage embedding is 020 43 compared to 2.49 for annotation embeddings and 1.20 for visual embeddings so you want to have this as small as possible this pretty much measures how heavy the details of the distribution are so that's this statistical measure the curdosis okay so those were the offline metrics and this analysis of the embedding space now for the user studies so they basically formed a group of people and they gave them a side by side different baseline so pin sage and visual baseline pin sage and annotation baseline pin sage and pixie and they asked them which one is more relevant to the query to the query pin so this is a query pin and then they they give them some results from different baselines and they asked them what's better and you can see so first the table again pin sage has the highest fraction of winds so that's not much information there so let's see some visual results okay so given this query pin where you can see some some like young plants here the visual baseline makes some semantical errors so it returns the image imagery of food which is visually related but it's not what we what we are interested in it's not as related conceptually on the other hand annotations are returning some results pixie also but like none of these are as relevant as pin sage which basically also gave both visually similar things but conceptually the topic that's the same those are also some like young plants here and here and here so you can see visually that pin sage gives the best recommendations finally one more example here we see some logs in the query pin so the visual one again made mistake giving some war photos which are like grayscale and confuse them thus with the topic that's similar to this one and that's just logging and you can see that pin sage gave both the visually similar picks and most importantly the most relevant pictures pins in general okay I mentioned they did a bit testing so what they were testing in production is they were testing home feed and they were testing this re pin rate so a user saving a pin to a board is a high value action that signifies deep engagement of the user so once you recommend something to the user on the home feed and user engages with some of the pins and saves them into some of his or her boards that's a really good signal and that's what they were testing like in a be tests at Pinterest so I assume they took some geographic location they use some baseline there and then took some other location they took pin sage and they compared how much the engagement varies between the different production systems and they figure out that pin sage is again performing better so all of the three metrics both the offline metrics all of both the user studies both the a be tests show that pin sage improved the results so let me wrap up the paper basically couple more details this one is interesting so after training completes due to the highly efficient map reduce inference pipeline the whole inference procedure to generate embeddings for three billion items can finish in less than 24 hours so this is impressive and you can see how much engineering went into this system and yeah it's just there is a lot of innovation happening in engineering also it's not only about research couple more interesting charts here so what they did is they took the embeddings of pin sage and they just did some t-sne reduction to 2d chart and you can see that if I zoom in embeddings that are really close into the space are topically similar so you can see some fashion images here you can see some covers here so yeah all in all semantically it makes sense finally they were exploring the number of neighbors so if you remember how the neighborhood is computed we basically take the t neighbors that had the highest count and here they showed that taking 50 neighbors has the highest hit rate and mixed this mean reciprocal rank where the training time was still acceptable 78 hours compared to these so that was pretty much it I covered bunch of details in this paper I still omitted some details but those are probably the most important details you should understand about this work and yeah if you found this video useful consider subscribing and hitting that bell icon to get notified when I upload each new video and if you have any feedback any comment how I can improve or whatever you have to say please write it down in the comment section that will also help me boost the YouTube algorithm so yeah until next time keep learning deep
[{"start": 0.0, "end": 6.78, "text": " Continuing with the graph neural network series and this video I'm covering graph convolutional neural networks for web scale"}, {"start": 7.22, "end": 8.96, "text": " recommender systems or"}, {"start": 8.96, "end": 15.08, "text": " Pinsage for short and as you can tell by the title of the video is going to be more about like this huge"}, {"start": 15.64, "end": 20.080000000000002, "text": " Engineering system that's deployed at Pinterest and then about novel"}, {"start": 20.96, "end": 25.52, "text": " Algorithms like propagation rules or something like that. So anyways"}, {"start": 25.52, "end": 31.3, "text": " One thing worth mentioning is that this is a direct continuation of the graph sage"}, {"start": 31.7, "end": 36.34, "text": " Paper which I've covered in my previous video. So if you don't know anything about graph sage"}, {"start": 36.42, "end": 42.42, "text": " It's probably a good idea to just go and check out that video. I'll link it somewhere in the in somewhere here"}, {"start": 43.14, "end": 45.620000000000005, "text": " So basically the authors are basically the same"}, {"start": 46.3, "end": 49.4, "text": " Rex, Ying, Hamilton and Leskowitz"}, {"start": 49.4, "end": 56.36, "text": " Were the authors on graph sage paper and we have some additional authors for Pinsage here. Mm-hmm"}, {"start": 56.64, "end": 63.16, "text": " So let me start we describe a large scale deep recommendation engine that we developed and deployed at Pinterest"}, {"start": 63.16, "end": 69.75999999999999, "text": " And I so happened to have opened a new account today. So let me just show you how it all functions"}, {"start": 69.92, "end": 77.12, "text": " So basically and why I'm showing you this is because they're they're training Pinsage for two specific recommendation tasks"}, {"start": 77.12, "end": 79.80000000000001, "text": " the first one is this home feed a"}, {"start": 80.24000000000001, "end": 82.56, "text": " recommendation where basically the goal is to give you"}, {"start": 83.36, "end": 85.68, "text": " To give you like yeah"}, {"start": 86.28, "end": 92.16000000000001, "text": " most relevant pins on your home feed and the reason I'm mostly having like a motor cars here and motorbikes is"}, {"start": 92.64, "end": 95.60000000000001, "text": " Because the only pin I have is of a muscle car"}, {"start": 95.60000000000001, "end": 98.2, "text": " so initially I just picked some categories and"}, {"start": 98.64, "end": 104.24000000000001, "text": " What Pinterest did was it gave me pretty much uniformly for from all of those categories a couple of pins"}, {"start": 104.24, "end": 109.39999999999999, "text": " And what I did I went and pinned a certain pin and now I'm pretty much getting"}, {"start": 110.0, "end": 112.0, "text": " related pins to the last pin I've made"}, {"start": 112.64, "end": 114.11999999999999, "text": " And we'll see that in the paper"}, {"start": 114.11999999999999, "end": 120.56, "text": " They actually explicitly mentioned that that's how this home feed our recommendation works and it seems they haven't changed that thing"}, {"start": 120.56, "end": 124.39999999999999, "text": " so another task they are doing is if I open a specific pin and"}, {"start": 124.88, "end": 130.48, "text": " What they do here is they they offer you this list of similar pins. So more like this"}, {"start": 130.48, "end": 134.88, "text": " So these are the related pins to the pin you're just chosen and"}, {"start": 135.39999999999998, "end": 142.85999999999999, "text": " There is also aside from the concept of a pin. They have something called boards and so this user Harry saved this"}, {"start": 143.48, "end": 147.64, "text": " particular pin to this board V road and basically boards just"}, {"start": 148.6, "end": 150.2, "text": " Just basically"}, {"start": 150.2, "end": 157.23999999999998, "text": " Accumulate similar like similar pins in a logical unit and that's that's everything I wanted to cover"}, {"start": 157.24, "end": 159.24, "text": " Let me get back to the paper"}, {"start": 159.24, "end": 164.52, "text": " So they say here we deploy pinsage at Pinterest and train it on 7.5 billion examples"}, {"start": 165.24, "end": 170.76000000000002, "text": " on a graph with 3 billion nodes representing pins and boards in 18 billion edges"}, {"start": 170.76000000000002, "end": 176.96, "text": " So hopefully because I went through the platform if you if you're not familiar with Pinterest this will kind of contextualize"}, {"start": 177.52, "end": 183.32000000000002, "text": " Both the problem and how how everything fits together. So let me let me start and"}, {"start": 184.04000000000002, "end": 186.04000000000002, "text": " show you the"}, {"start": 186.04, "end": 188.04, "text": " some engineering"}, {"start": 188.04, "end": 190.51999999999998, "text": " innovations they introduced as well as some"}, {"start": 191.07999999999998, "end": 199.07999999999998, "text": " algorithmic innovations so first off they say here traditional GCN algorithms perform graph convolutions by multiplying feature matrices"}, {"start": 199.07999999999998, "end": 205.88, "text": " by powers of the full graph laplation and what that basically means if you if you if you're familiar with GCN and here"}, {"start": 205.88, "end": 207.88, "text": " I'll just open I'll open this"}, {"start": 208.68, "end": 214.35999999999999, "text": " paper which I've covered in one of my previous videos and you can see the update rule for GCN and"}, {"start": 214.36, "end": 220.28, "text": " Basically this part the a tilde part is in a structure similar to laplation even though it's not laplation and"}, {"start": 220.28, "end": 225.0, "text": " That's what they're basically saying they're saying that you need to store this whole huge"}, {"start": 225.56, "end": 230.92000000000002, "text": " adjacency or laplation matrix which is m by n where n is the number of nodes and in the case of"}, {"start": 231.32000000000002, "end": 237.72000000000003, "text": " Pinterest we have like 3 billion nodes at a time that the paper was written and so basically that's not that's not"}, {"start": 238.28000000000003, "end": 241.32000000000002, "text": " An option at all. So let me let me get back here"}, {"start": 241.32, "end": 247.23999999999998, "text": " So what it did as is the same as in graph sage they basically they are just sub sampling the neighborhoods"}, {"start": 247.64, "end": 249.64, "text": " Although they are not"}, {"start": 249.64, "end": 253.64, "text": " Doing uniform sampling they're doing something more clever and I'll get to that in a bit"}, {"start": 254.44, "end": 259.88, "text": " The second thing worth mentioning is that they have so on the on the engineering side is that they have this"}, {"start": 260.52, "end": 264.84, "text": " producer consumer pipeline and basically what it means is that"}, {"start": 265.48, "end": 268.52, "text": " We have in so in parallel the cpu is"}, {"start": 268.52, "end": 272.28, "text": " Preparing mini batches while the gpu is doing"}, {"start": 272.84, "end": 277.64, "text": " propagations and then you can just optimize and sync them so that"}, {"start": 278.12, "end": 285.0, "text": " GPU is never starving and they say it here cpu bound producer efficiently samples node network neighborhoods a gpu bound"}, {"start": 285.32, "end": 287.32, "text": " TensorFlow model consumes those"}, {"start": 288.35999999999996, "end": 294.91999999999996, "text": " And thirdly they have this efficient map reduce inference and why do they have this well basically?"}, {"start": 294.92, "end": 298.12, "text": " and we'll see that in a bit a bit in a bit more detail, but"}, {"start": 298.84000000000003, "end": 303.40000000000003, "text": " the the Pinterest graph is huge and what they do is they train the"}, {"start": 303.96000000000004, "end": 311.08000000000004, "text": " Pinsage model only on a subset of that huge graph and once they have the model trained"}, {"start": 311.40000000000003, "end": 319.08000000000004, "text": " They just use this map reduce pipeline to basically compute the embeddings for every single other node in the graph"}, {"start": 319.72, "end": 320.92, "text": " That's pretty much it"}, {"start": 320.92, "end": 328.68, "text": " So they say it here that can so map reduce pipeline can distribute the trained model to generate embeddings for billions of nodes"}, {"start": 329.08000000000004, "end": 334.20000000000005, "text": " While minimizing repeated computations, so that's this is the the the important part"}, {"start": 334.84000000000003, "end": 335.88, "text": " and"}, {"start": 335.88, "end": 340.76, "text": " Just on a small tangent. Let me let me quickly explain the map reduce pipeline and it's really simple"}, {"start": 340.92, "end": 342.92, "text": " So I thought it's worth mentioning it"}, {"start": 343.56, "end": 345.56, "text": " Basically here on an example"}, {"start": 345.56, "end": 351.64, "text": " This is a canonical example of doing uh finding out word frequencies in a document in documents"}, {"start": 351.88, "end": 354.6, "text": " And here is just a toy example with three sentences"}, {"start": 354.6, "end": 361.32, "text": " You can imagine a huge corpora here like imagine transformers which have multiple terabytes of textual data"}, {"start": 362.04, "end": 366.6, "text": " Which needs to get somehow maybe like the word frequency needs to get calculated"}, {"start": 367.16, "end": 371.96, "text": " And here on this example what happens is we basically have two modules"}, {"start": 371.96, "end": 378.35999999999996, "text": " We have this mapping part and we have the reduce part and hence the name mapping use and basically"}, {"start": 378.76, "end": 384.28, "text": " Inside the mapping module. We first just split the data. So here every single sentence will go there"}, {"start": 385.08, "end": 392.44, "text": " in in a separate module and what then happens is we we just map those parts those those"}, {"start": 393.56, "end": 398.35999999999996, "text": " Those samples of data into key value pairs and in this example"}, {"start": 398.36, "end": 403.40000000000003, "text": " of figuring out the frequencies of the words, we basically end up with like a"}, {"start": 404.12, "end": 410.12, "text": " Deer having one bear one, etc. And then what we do is we shuffle which is basically clustering"}, {"start": 410.84000000000003, "end": 414.84000000000003, "text": " These key value pairs by the key and we end up with these"}, {"start": 415.32, "end": 418.36, "text": " And finally the reduce stage sums these values up"}, {"start": 418.68, "end": 422.84000000000003, "text": " And it depends on how you define those reduce and map scripts"}, {"start": 422.84000000000003, "end": 424.84000000000003, "text": " And finally just aggregate those"}, {"start": 424.84, "end": 432.03999999999996, "text": " And you get the final result every single word has its frequency associated with it and this is a simplified"}, {"start": 432.76, "end": 434.76, "text": " example, obviously"}, {"start": 434.76, "end": 440.59999999999997, "text": " You'll have multiple shuffling and reducing stages in a in a in a real production system. So"}, {"start": 441.32, "end": 442.59999999999997, "text": " again"}, {"start": 442.59999999999997, "end": 445.79999999999995, "text": " It's supposed to minimize repeated computations and"}, {"start": 446.59999999999997, "end": 449.15999999999997, "text": " If you're familiar with graph sage, this will be really"}, {"start": 449.71999999999997, "end": 451.71999999999997, "text": " This image will make sense"}, {"start": 451.72, "end": 456.12, "text": " If not, i'll just i'll briefly do an overview as well here"}, {"start": 456.12, "end": 460.68, "text": " But like the repeated computations are these here. So basically the node a"}, {"start": 461.48, "end": 465.96000000000004, "text": " This computation here is the same as this one here and the same as this one here"}, {"start": 465.96000000000004, "end": 470.52000000000004, "text": " So what map reduce does is it it does this projection only once?"}, {"start": 471.08000000000004, "end": 476.28000000000003, "text": " For every single node in the graph and thus saves us a lot of computation unnecessary computation"}, {"start": 477.32000000000005, "end": 479.32000000000005, "text": " So that's the role of map reduce"}, {"start": 479.32, "end": 484.36, "text": " And on a short note how this works is the following so let me take"}, {"start": 485.0, "end": 486.44, "text": " I'll just ignore"}, {"start": 486.44, "end": 490.04, "text": " Because this is these are two layers of the pin sage algorithm"}, {"start": 490.04, "end": 495.32, "text": " I'll just ignore one layer and i'll focus on the on a single layer and basically to calculate"}, {"start": 495.8, "end": 500.28, "text": " For a specific node and you can see a toy graph here and we are interested in this target node"}, {"start": 500.28, "end": 506.2, "text": " So to calculate the representation of this node a what we do is the following so we basically concatenate it"}, {"start": 506.2, "end": 513.72, "text": " It's it's last layer representation with the aggregated neighborhood representation which we again get by doing some aggregation"}, {"start": 514.12, "end": 523.16, "text": " And in pin sage they introduce this thing called important sampling important spooling and i'll i'll explain that in a lot more detail a bit later"}, {"start": 523.16, "end": 530.52, "text": " But for now just this is some aggregation function like in graph sage you had max pooling you had lstms means so this is something similar"}, {"start": 530.52, "end": 538.04, "text": " And so what we do is we take the neighbors you can see b c and d are the neighbors of a here so we take those neighbors"}, {"start": 538.04, "end": 544.04, "text": " We just project their representations here and we aggregate them and that's how we get the aggregated portion"}, {"start": 544.04, "end": 546.04, "text": " So that's how the algorithm works in a nutshell"}, {"start": 547.24, "end": 556.04, "text": " There are a couple of innovations which i'll now briefly do a high level of and so these are the innovations in algorithmic sense"}, {"start": 556.04, "end": 564.04, "text": " Basically they don't do they show that the random sampling uniform land random sampling they used in graph sage is suboptimal"}, {"start": 564.04, "end": 576.04, "text": " So they do this thing called importance pooling where they are basically picking the the the those those neighbors which have the most influence on the target node"}, {"start": 576.04, "end": 578.04, "text": " And that will get clear in a couple of minutes"}, {"start": 578.04, "end": 588.04, "text": " So they say here an additional benefit is that each node now has an important score and those scores will be used in this importance pooling"}, {"start": 588.04, "end": 598.04, "text": " I'll explain that a bit later one more algorithmic innovation is this curriculum training where basically the algorithm is fed harder and harder negative examples"}, {"start": 598.04, "end": 602.04, "text": " And we'll we'll see what those exactly are in a couple of minutes"}, {"start": 602.04, "end": 608.04, "text": " So that's a high level overview of what the both the engineering as well as the algorithmic innovations are"}, {"start": 608.04, "end": 614.04, "text": " And now i'm going to slowly dig into details of this paper"}, {"start": 614.04, "end": 626.04, "text": " So first first things first the tasks as I mentioned are related pin recommendation and home feed recommendation tasks and we saw that on the platform itself"}, {"start": 626.04, "end": 628.04, "text": " So just keep that in mind"}, {"start": 628.04, "end": 642.04, "text": " So in terms of the algorithmic design they they are basically as I said continuing the graph sage paper so the work on that paper and they took a couple of ideas from from fast gcn by Chen and his collaborators"}, {"start": 642.04, "end": 648.04, "text": " Basically the the importance pooling part those ideas were borrowed from from from this paper"}, {"start": 648.04, "end": 670.04, "text": " And again engineering details and I'll have a lot of these throughout the video because this this this this paper is there is a lot of engineering that went into this this work so I think it's just worth mentioning some of them and I'll omit like most of them but I still want to mention a couple of them"}, {"start": 670.04, "end": 696.04, "text": " So we fundamentally improve upon graph sage by removing the limitation that the whole graph be stored in a GPU memory so basically they are using that producer consumer pipeline so we don't have to hold the whole graph in GPU you hold it in CPU and that's where the producer is and then the GPU the consumer just takes many batches and basically that's how it trains"}, {"start": 696.04, "end": 725.04, "text": " Okay one more thing to note they they they they mentioned here why we can't use those shallow graph embedding methods so like deep walk and note to work the reason is they basically have for every single embedding is stored in the table in a lookup table so this table would be huge like because this is in and it's a number of notes and because Pinterest has like multiple like billions of notes"}, {"start": 725.04, "end": 754.04, "text": " This is like pretty much intractable and not only that but it's also inherently transacting methods which means you will have to get re-optimized to get when new pins are introduced into the system which is also not desirable and lastly these methods only use the co-occurrence statistics of the graph and they can use the features and as you probably can assume pins in in the graph"}, {"start": 754.04, "end": 782.04, "text": " pins in in in this graph have a rich features associated with them because they have like imagery and they have like maybe some let me just draw something here okay and they have they also have textual information associated with them so these methods can even make use of these so yeah that that those are multiple reasons why you just can't use those graph embedding methods for this task"}, {"start": 782.04, "end": 811.04, "text": " okay let's let's continue and see how they structure how they model the the the problem so basically the model of the the the graph the following so you have on one side you have pins or more generally items and on one side you have you have boards or more generally collections and what they do is they just create a by by part of the graph where basically as we saw one board has multiple"}, {"start": 811.04, "end": 840.04, "text": " related pins associated with with it so this is how the the graph will look like something like this and they mentioned they have around two billion pins and about one billion boards so this is how the the graph looks like and yeah I mentioned this pins are associated with both rich text and image features and the goal is to leverage both the features and the graph structure to to find those embeddings which can later be used to recommend"}, {"start": 840.04, "end": 868.04, "text": " related pins etc okay so now that we know how the problem is structured and what the what the tasks are and let's dig into some details yeah by the way they treat both the pins and the boards as the same nodes even though only the pins basically have features so they say here for notational convenience in generality"}, {"start": 868.04, "end": 897.04, "text": " when we describe the pin sage algorithm we simply refer to the node set of the full graph with V so it's a union between items and collections and they do not explicitly distinguish between pin and board nodes okay this is the algorithm basically if you're familiar with graph sage it has the same structure same old structure so here this one line corresponds to this line concatenation corresponds to this line and normalization corresponds to this line"}, {"start": 897.04, "end": 922.04, "text": " there are a couple of innovations though the first one is how they sampled the neighborhood that's the first innovation the second one importance pooling and that's pretty much it there is not a lot of new things that happen here everything else pretty much remain the same so a couple more nodes before I explain the importance pooling and before I explain the neighborhood they empirically so they say here empirically we observe significant performance gains when we look at the"}, {"start": 922.04, "end": 945.04, "text": " operation instead of the average operation as in 21 which is GCN paper so basically this year they showed empirically that it's better to use concatenation than just the thing that GCN did and that's just pretty much scaled weighted mean of these features and secondly normalization part so this part here"}, {"start": 945.04, "end": 975.04, "text": " in line three makes training more stable and it's more efficient to perform approximate nearest neighbor search for normalized embeddings and I'll explain what that is in a sec so first normalization what it does is basically make sure that all of our embeddings lie on a hypersphere and there's just a fancy name saying a sphere in higher dimensions if that sphere was in three dimensions and that sphere was in three dimensions then that sphere is a hyper sphere and that's the only thing that's important to know about this so"}, {"start": 975.04, "end": 1005.0, "text": " basically we have we have that sphere lying around the coordinate beginning and all of the embeddings would lie on the edge of that sphere hopefully you can see that so again maybe here we have a huge sphere and all of the embeddings lie somewhere on this sphere all of our pins all of our boards lie somewhere on this sphere so they say here so it's more efficient to perform approximate nearest neighbor search so why do we"}, {"start": 1005.0, "end": 1034.96, "text": " care about approximate nearest neighbor search in this context so the reason is pretty simple so once you have so you basically have the embedding space and you embed your pins like maybe you'll maybe take this motorcycle and you'll embed it here and that's pin one and then you'll have all of the pins embedded and basically if you want to do related pin recommendation what you pretty much do is you find"}, {"start": 1034.96, "end": 1062.1200000000001, "text": " the k nearest neighbors to this target node p1 so if you're if I'm interested what the related pins to the motorcycle are I just find the closest ones and now because there are so many embeddings in this space so there are billions of embeddings we can't do exact nearest neighbor so they just use methods such as locality sensitive hashing to which are really good"}, {"start": 1062.12, "end": 1087.6, "text": " approximative methods to to do k nearest neighbors so that's why they mention nearest neighbors here and so normalization helps helps calculate those those nearest neighbors okay with those details out of the way let me explain the two most important parts and that's neighborhood and"}, {"start": 1087.6, "end": 1106.36, "text": " important sampling so basically this is what looks like we have a target node and we have its neighborhood so this is the one hop neighborhood this is the two hop neighborhood three hop et cetera so what we do basically is the following we take a bunch of random walks which are"}, {"start": 1106.36, "end": 1133.52, "text": " decently short and we we run them in parallel and what we do is we just count up the number of wizards every single node had so this one maybe had two wizards this one had only one visit maybe some of them had three wizards like this one maybe had three this one maybe had three and we basically take the t"}, {"start": 1133.52, "end": 1151.44, "text": " nodes that had the highest visit count and that's it so t was 15 there in their scenario so one thing worth mentioning is that these random walks are not biased and what that means is basically if you're at this node you'll go to your next"}, {"start": 1151.44, "end": 1181.3600000000001, "text": " node will be one of the neighboring nodes with equal probability contrast that to biased nodes such as so node2vec for example method used biased biased random walks where if you you have some parameters there like p and q and depending how you set them up you'll either prefer going in like a bfs manner so breadth first search or you'll be preferring depth first search traversals of the graph so here we just have pure unbiased random walks we we"}, {"start": 1181.36, "end": 1211.32, "text": " figure out we run multiple of them and in parallel and we just find the counts and that's the that's our neighborhood so for example if t was if t was maybe three we only take this neighbor we take this neighbor and we take this one and so how does that fit in into important sampling well it's pretty easy once you think of it so basically what we do is we take the their visit counts and we just normalize them by the"}, {"start": 1211.32, "end": 1234.3999999999999, "text": " sum so this will be a three three and two that's eight so we'll have the final weights will be this and then the importance pooling part just works you just take these weights you sum up their projected representations and so you multiply the representations the projected representations by these"}, {"start": 1234.4, "end": 1262.0, "text": " weights so this one so this representation this feature vector will get multiplied by this one and this feature vector will get multiplied with this weight and you just sum them up and that's the gamma part that's the importance pooling part so contrast that the graph sage which has just had max pooling and there we didn't have these weights we just find the like element wise max and that's that's the difference"}, {"start": 1262.0, "end": 1290.0, "text": " okay so they say they mentioned here the neighborhood of a node u is defined as the t-notes and I mentioned that's 50 that exert the most influence on node u and you it's pretty much intuitive that all of those nodes which had the highest visit counts are in a sense the most influential ones because we have the highest probability of visiting them they are the most connected in a way to our target node u"}, {"start": 1290.0, "end": 1319.36, "text": " and again about the importance pooling we implemented gamma as a weighted mean with weights defined according to the l1 normalized visit counts which is the thing I just explained and they refer to this as importance pooling so that those are the main innovations they had but there are some more things that I want to cover so let's just continue with model training so if you remember a graph sage"}, {"start": 1319.36, "end": 1341.36, "text": " how graph sage was trained it was basically trained either in an unsupervised manner using negative sampling or we had task specific supervised loss like cross entropy in the case of classification so here pin sage uses this thing called max margin ranking loss and we'll see what that is in a sec"}, {"start": 1341.36, "end": 1370.36, "text": " but before that what's the data so the goal of the training phase is to optimize the pin sage parameters so that the output embeddings of pairs query and i from this set l in the labeled set are close together so what's this set l so basically what it is is the following they just tracked the engagement on pinterest so if you for example had if you were playing with pin q"}, {"start": 1370.36, "end": 1399.36, "text": " and the first next pin that you opened or interacted with had an engagement with was pin i then they just put this pair in this set l they just add this pair to this set l and that's how they collect basically the supervised data set just through natural engagement of users on pinterest they through time get a huge huge training set l"}, {"start": 1399.36, "end": 1428.36, "text": " okay now let's jump in understand how the loss works and i'll i'll skip through this mini batch version of the algorithm i just showed you because it's equivalent to the graph sage algorithm they just instead of working on the whole pinterest graph they just take a subset and they just work on on that sub graph instead of using the whole graph so i'll just keep it for now"}, {"start": 1428.36, "end": 1450.36, "text": " and let's focus on the loss function and this is this is interesting part so basically the following happens so as zq z and q all of these are the final representations that you end up having after you run the pin sage algorithm so you end up with these as the vectors"}, {"start": 1450.36, "end": 1469.36, "text": " and once you have them what you do is the following so you have you have q which is the query query embedding and you have positive samples which is z i and you have negative samples which is n k and the goal here is the following"}, {"start": 1469.36, "end": 1490.36, "text": " you basically want to make sure that the similarity between q and i which is by definition a related pin this thing should be bigger than the similarity between q and this negative sample by at least a margin"}, {"start": 1490.36, "end": 1510.36, "text": " so for example if this similarity was three and the margin was which is a hyper parameter itself so if the margin was two that means we need to make sure that this part is at least five five or bigger five plus"}, {"start": 1510.36, "end": 1532.36, "text": " and why is that because we have a max between zero and this term here which means the loss goes to zero once this becomes negative and this becomes negative once this part once this part becomes bigger than the similarity between the query and negative sample plus the margin"}, {"start": 1532.36, "end": 1551.36, "text": " so that's this this portion of the loss now if you're like me you you're probably confused or you were confused at one point of your life with this part the expected value and what this basically says is the following so the higher the probability of a certain negative sample"}, {"start": 1551.36, "end": 1571.36, "text": " the more important it is to minimize its associated term here so let me let me try and visualize that here so basically first maybe a mathematical definition of what expected value is maybe it will be for some of you will make sense so expected value of a random variable"}, {"start": 1571.36, "end": 1596.36, "text": " x and some function g of x where this small x is just one of the possible outcomes of this random variable big X is the following is just a plain sum of the probability of those outcomes times the value of the function g at that particular outcome x"}, {"start": 1596.36, "end": 1615.36, "text": " and let me now contextualize and associate these two so g of x is basically this part this max part and let's see where the p part comes from so if we have a graph like this if we have a graph and we have a couple of notes and maybe this is the query node"}, {"start": 1615.36, "end": 1635.36, "text": " and this is the the the related node that's ground truth because of the engagement and the way how Pinterest collects these so we know this is the related one and we know this is the query pin so now let's say there are a couple there so every other pin every other node in the graph is a potential negative sample"}, {"start": 1635.36, "end": 1664.36, "text": " assuming that this is the only related pin to query pin so what we do is the following so let's let's say that during the training we maybe take seven times we take this this node as a negative sample as the NK so remember the notation we had ZNK so seven times maybe we take this one one time maybe we take this one zero times and this one two times so basically what happens is because this one was"}, {"start": 1664.36, "end": 1691.36, "text": " this one was sampled most oftenly seven times compared to two and one it's really important to minimize its associated values so g of x had to be as close to zero as possible right because we'll have we'll have one time one time something so the last will be one times x plus two times so this is two times"}, {"start": 1691.36, "end": 1718.36, "text": " its loss that's y plus seven times times Z where Z is the loss value associated with this negative sample so that means it's the most important so the most important thing we can do is minimize this part so because this is the highest the highest the highest number and if we translate these into probabilities into"}, {"start": 1718.36, "end": 1744.36, "text": " empirical probabilities because we had ten times we draw negative samples ten times this will be seven over ten this will be two over ten and this will be one over ten and that's where the p of x comes from so basically we have zero point seven times this max and we that's the reason we want to make sure"}, {"start": 1744.36, "end": 1773.36, "text": " that the higher the probability we want to make sure that the term is the lowest okay hopefully this wasn't too much confusing okay let me continue what else again some engineering details we design a producer consumer pattern to run GPU computation at the current iteration and CPU computation at the next iteration in parallel so that's what I mentioned already and this further reduces the training time by almost a half"}, {"start": 1773.36, "end": 1802.36, "text": " so even though conceptually this is a small thing like it's a really hard engineering problem and b it led to like a huge improvement in efficiency of the algorithm and training time okay and one more engineering detail is that they are to improve efficiency when training with large batch sizes we sample a set of five hundred negative items to be shared by all training examples in each mini batch so they won't be"}, {"start": 1802.36, "end": 1831.36, "text": " finding for every single node they won't be figuring out the negative examples they'll just pre compute five hundred negative items and they'll be sharing those for different query and related pins enough about engineering details let's let's see one more important part algorithmically so however ensuring that the inner product of the positive example so pair of items q and i is larger than that of the q and each of the five hundred negative items"}, {"start": 1831.36, "end": 1860.36, "text": " is too easy and why is it too easy because if you take a random negative example from the huge data set they have like a multiple billions of pins there is a huge probability that will be totally different from the related pins and that means it's really too easy to to optimize this this problem and here they show so they show an example of what they mean and they make"}, {"start": 1860.36, "end": 1886.36, "text": " of what they mean and they mentioned here so to solve the above problem for each positive training example so the item pair q and i we had hard negative examples so we make a distinction between hard negative examples and like maybe easy and negative examples and you can see here visually basically this is a query so we have some flower on an embroidery and then we have"}, {"start": 1886.36, "end": 1906.36, "text": " a positive example so that's the eye pin had this image and you can see it's also an embroidery and it's also flower so a random negative example so the easy negative sample would be this so this is neither embroidery and it's neither a flower so just some random hat and this is the hard"}, {"start": 1906.36, "end": 1927.36, "text": " example because it is embroidery so it's a similar in a way similar to these two but the content is a bird instead of a flower so that's what what what makes it hard okay so now that we know that let me see what they what they do and how they calculate how did they figure out these"}, {"start": 1927.36, "end": 1946.36, "text": " a hard example so they are generated by ranking items in a graph according to their personalized page rank scores with respect to the query item q items ranked at 2000 to 5000 are randomly sampled as hard negative items so a page rank is you probably heard of it page rank is"}, {"start": 1946.36, "end": 1972.36, "text": " Google initial the initial algorithm that Google use for research and intuitively it just looks at the edges and using that finds how important certain web page or element in general is important depending on how many links point to that particular note so what I do is they take the query pin"}, {"start": 1972.36, "end": 1997.36, "text": " and they just calculate these personalized page rank scores they just saw them by the score and they just take for example from 2k to 5k they consider so there's just a simple some heuristic they they figure out makes sense and they just randomly sample elements from from this subset and those are the hard"}, {"start": 1997.36, "end": 2018.36, "text": " hard examples in the training and for the part so this part tells us about the curriculum learning so in the first epoch of the training no hard negative items are used so that the algorithm quickly finds an area in the parameter space where the loss is relatively small at each epoch"}, {"start": 2018.36, "end": 2044.36, "text": " epoch and the training we had and minus one hard negative items to the set of negative items for each item so that means in epoch to they'll be adding one so that's a minus one so they'll be adding only one hard example as the epoch progress at epoch 10 they'll be adding nine negative items to the set of negative items for each item and that's how they progressively"}, {"start": 2044.36, "end": 2052.3599999999997, "text": " stimulate and make it harder to to optimize that loss"}, {"start": 2052.36, "end": 2079.36, "text": " okay that was that was all I had to say about the like some of the some some things were about engineering some things about were about algorithmic innovation and now let's switch topic a little bit and see how they how they tested this thing and what they what they did so again just just a fun fact so"}, {"start": 2079.36, "end": 2098.36, "text": " so for the home feed recommendation task we select the pins that are closest in the embedding space to one of the most recently pinned items by the user and if you remember I initially showed you that I have bunch of cars here and the reason and motorcycles now because I was"}, {"start": 2098.36, "end": 2118.36, "text": " interacting with a motorcycle but like basically they are they are the the the last pin you made is heavily influences this home feed recommendations and I can just empirically see that and verify it although it's not as simple as we saw like this motorcycle me engaging with this pin"}, {"start": 2118.36, "end": 2145.36, "text": " change my home feed here okay so again I mentioned this day they defined the set tell by using the historical user engagement data okay before we we we we see some results let me just detail a little bit how the features for every single pin are constructed so basically every"}, {"start": 2145.36, "end": 2169.36, "text": " single pin has some image associated with it so that some image and then we have also have some annotations so textual information and this notice also has some connections with some other notes so how they construct the final feature vector is the following so they"}, {"start": 2169.36, "end": 2190.36, "text": " past the image through a VGG network so there's just a convolutional neural net and they take one of the flat one of the feed forward activations and they use that as one part of the feature vector then they use they do a virtual back the train a virtual back model on the"}, {"start": 2190.36, "end": 2213.36, "text": " annotations and they embed the annotations also in a I think it was 256 dimensional vector and they concatenate these two and finally they add the log of the degree of this note of this particular pin so this is the degree so maybe this note has just ignore these so we have four"}, {"start": 2213.36, "end": 2231.36, "text": " four four notes connecting to this one so we'll just add log four as a feature so in a general case log the I where this is no I and this is the degree of the note and now that we know how the feature vectors are constructed for the pins for pins in"}, {"start": 2231.36, "end": 2248.36, "text": " pins age let's see how the baselines are constructed we have this visual baseline which basically does the following so for every single pin it just takes the image that's associated with that pen and does the same thing as pins age so just passes it through a VGG network takes out"}, {"start": 2248.36, "end": 2266.36, "text": " those features from certain fully connected layer and embeds that directly uses that as the final embedding and so once you embed that into so once you embed this thing into embedding space how you recommend how this simple baseline recommends is just using"}, {"start": 2266.36, "end": 2285.36, "text": " canerous neighbors so the same as as pin stages he just has a much less delicate method it doesn't use it doesn't use the graph information the graph structure it's a content recommender system okay second baselines super similar just uses only"}, {"start": 2285.36, "end": 2304.36, "text": " annotations instead of the image so it uses textual information third one combines both of those entrains MLP on top of them and finally the fourth one is pixie which uses random walks to find the the the the recommendations and basically doesn't use"}, {"start": 2304.36, "end": 2323.36, "text": " the those features just uses the random walks so that's the method that was previously used in production at Pinterest okay and yeah they don't compare with other methods because basically the scale is so huge that none of the previous methods could be"}, {"start": 2323.36, "end": 2341.36, "text": " simply used in this setting finally they just modify pins age and in a couple of ways and use those as baselines as well so here this max pooling one uses instead of using the importance pooling it uses max pooling and it just doesn't use those hard"}, {"start": 2341.36, "end": 2358.36, "text": " negative samples which I showed you previously so yeah that's the those are the baselines and now we'll see the results again some engineering details huge pages hadoop which is an open source implementation of the map reduce framework which I"}, {"start": 2358.36, "end": 2376.36, "text": " previously showed you and explained you so yep let's see the results yeah unfortunately these are not metrics you're probably familiar with so let me just briefly explain why what these are so we have something called hit rate hit rate and we have something"}, {"start": 2376.36, "end": 2400.36, "text": " called mean reciprocal rank and what hit rate is is the following so basically you have the query pin and you have the related pin I which we got by collecting like through engagement data right and so now our recommender system basically gives out a list of"}, {"start": 2400.36, "end": 2424.36, "text": " related pins to this query pin and the length of this list is K which is a hyper parameter and they used 500 in this paper so now what the hit rate is is the following so we're interested whether this ground truth pin is somewhere inside the recommended"}, {"start": 2424.36, "end": 2446.36, "text": " recommended pins if it is we that's a good thing if it's not that's a bad thing and basically hit rate just tells you going through the test set so going through various cues these cues and various eyes you basically see the percentage of time that the ground truth pin"}, {"start": 2446.36, "end": 2471.36, "text": " appeared in your recommendations and okay looking at that you can see that pinsage has 67% hit rate compared to these simple baselines like visual annotation and the combined one is combined one is better as expected than purely using like text or images and"}, {"start": 2471.36, "end": 2492.36, "text": " pinsage is also better than all of these maybe simpler baselines of pinsage so the second metric is this mean reciprocal rank and you can see the formula here and let me just make some sense out of it so basically it's super similar to hit rate except that we are interested"}, {"start": 2492.36, "end": 2520.36, "text": " into where exactly this pin this ground truth pin I appeared so let's assume that among the recommended items pins we we we did have this pin I and it was a location maybe 256 then that's much worse than having it the location one right so if we'd ideally want to recommend"}, {"start": 2520.36, "end": 2539.36, "text": " this ground truth pin somewhere closer to position one and that's that's this our term here and they just sum up those values and they just divided by the number of nodes in the test and that's it and if you take a look and the hundred is just hard coded so it's just"}, {"start": 2539.36, "end": 2568.36, "text": " empirically chosen value so that once we have so that we can distinguish when this is on one position to 1000 versus 2000 and that should make that will still make difference otherwise if this wasn't here the difference between what one over 1000 one over 2000 is super small and this makes it bigger so that's the reason they put the conjures here and again looking at the mixed reciprocal rank we can see it greatly improves with pinsage"}, {"start": 2568.36, "end": 2591.36, "text": " so those those were the offline evaluations they also did a be testings and user studies and I'll get into those in a minute but first one more important analysis they did is the exploration of the embedding space that the pins age method created against these baselines so the annotation visual"}, {"start": 2591.36, "end": 2610.36, "text": " baselines so basically what it did so they they took the embedding so you have a bunch of pins and they're embedded and you just took take two random pins and their embeddings and you do the cosine similarity so basically you're interested in the so if these are"}, {"start": 2610.36, "end": 2638.36, "text": " embedding vectors so you're interested in cosine of the angle between them cosine theta and you just plot that and you'd ideally one day to be distributed as as much as possible because that means they are not there not all the embeddings are similar and similarly oriented you want to have them or if they're if you pick the random pins you want to have them randomly distributed in space oriented in space so looking at the graph here you can see that"}, {"start": 2638.36, "end": 2640.36, "text": " the"}, {"start": 2640.36, "end": 2667.36, "text": " the pin sage has the most distributed curve here and the worst one is this one because it's highly it's really close to to one so you get one once you have because all of the embeddings remember they are they are normalized to unit length unit norm so that means this what you get one only when the vectors of the both embeddings totally coincide"}, {"start": 2667.36, "end": 2692.36, "text": " and if you if you if you take a look at the annotation baseline you can see it has the worst results it's 14 percent hit rate against 17 and 0.9 and so it's it's the worst method and these curves here tell the same thing pretty much and if you can introduce some fancy mathematics into this statistics so basically the"}, {"start": 2692.36, "end": 2714.36, "text": " court curdosis statistical measure of the cosine similarities of pin sage embedding is 020 43 compared to 2.49 for annotation embeddings and 1.20 for visual embeddings so you want to have this as small as possible this pretty much measures how heavy the details of the distribution are so that's this statistical measure the curdosis"}, {"start": 2714.36, "end": 2736.36, "text": " okay so those were the offline metrics and this analysis of the embedding space now for the user studies so they basically formed a group of people and they gave them a side by side different baseline so pin sage and visual baseline pin sage and annotation baseline"}, {"start": 2736.36, "end": 2763.36, "text": " pin sage and pixie and they asked them which one is more relevant to the query to the query pin so this is a query pin and then they they give them some results from different baselines and they asked them what's better and you can see so first the table again pin sage has the highest fraction of winds so that's not much information there so let's see some visual results"}, {"start": 2763.36, "end": 2789.36, "text": " okay so given this query pin where you can see some some like young plants here the visual baseline makes some semantical errors so it returns the image imagery of food which is visually related but it's not what we what we are interested in it's not as related conceptually on the other hand annotations are returning some"}, {"start": 2789.36, "end": 2811.36, "text": " results pixie also but like none of these are as relevant as pin sage which basically also gave both visually similar things but conceptually the topic that's the same those are also some like young plants here and here and here so you can see visually that pin sage gives the best recommendations"}, {"start": 2811.36, "end": 2839.36, "text": " finally one more example here we see some logs in the query pin so the visual one again made mistake giving some war photos which are like grayscale and confuse them thus with the topic that's similar to this one and that's just logging and you can see that pin sage gave both the visually similar picks and most importantly the most relevant pictures"}, {"start": 2839.36, "end": 2862.36, "text": " pins in general okay I mentioned they did a bit testing so what they were testing in production is they were testing home feed and they were testing this re pin rate so a user saving a pin to a board is a high value action that signifies deep engagement of the user so once you recommend something to the user on the home feed"}, {"start": 2862.36, "end": 2887.36, "text": " and user engages with some of the pins and saves them into some of his or her boards that's a really good signal and that's what they were testing like in a be tests at Pinterest so I assume they took some geographic location they use some baseline there and then took some other location they took pin sage and they compared how much the engagement varies between the different"}, {"start": 2887.36, "end": 2911.36, "text": " production systems and they figure out that pin sage is again performing better so all of the three metrics both the offline metrics all of both the user studies both the a be tests show that pin sage improved the results so let me wrap up the paper basically couple more details this one is interesting"}, {"start": 2911.36, "end": 2939.36, "text": " so after training completes due to the highly efficient map reduce inference pipeline the whole inference procedure to generate embeddings for three billion items can finish in less than 24 hours so this is impressive and you can see how much engineering went into this system and yeah it's just there is a lot of innovation happening in engineering also it's not only about research"}, {"start": 2939.36, "end": 2967.36, "text": " couple more interesting charts here so what they did is they took the embeddings of pin sage and they just did some t-sne reduction to 2d chart and you can see that if I zoom in embeddings that are really close into the space are topically similar so you can see some fashion images here you can see some"}, {"start": 2967.36, "end": 2993.36, "text": " covers here so yeah all in all semantically it makes sense finally they were exploring the number of neighbors so if you remember how the neighborhood is computed we basically take the t neighbors that had the highest count and here they showed that taking 50 neighbors has the highest hit rate and mixed this mean"}, {"start": 2993.36, "end": 3019.36, "text": " reciprocal rank where the training time was still acceptable 78 hours compared to these so that was pretty much it I covered bunch of details in this paper I still omitted some details but those are probably the most important details you should understand about this work and yeah if you found this video useful"}, {"start": 3019.36, "end": 3041.36, "text": " consider subscribing and hitting that bell icon to get notified when I upload each new video and if you have any feedback any comment how I can improve or whatever you have to say please write it down in the comment section that will also help me boost the YouTube algorithm so yeah until next time keep learning deep"}]