Graph SAGE - Inductive Representation Learning on Large Graphs | GNN Paper Explained

Key Takeaways

hi in this video i'm continuing with graph neural network series and i'll be covering this paper called inductive representation learning on large graphs or also known as graph sage so basically the main proposition of graph sage is that they developed a method that's inherently inductive and can work on huge graphs so the later paper that came after graph sage is spin sage and i'll be covering that one in the one of the next videos and it's basically this is basically a precursor to that paper which is really awesome and has an awesome implication as a recommender system uh in pinterest so um basically they say here most existing approaches require that all nodes in the graph are present during training of the embeddings these previous approaches are inherently transductive and do not naturally generalize to unseen notes so let me do just a quick recap of how those methods basically work so what you have is you you you have a steady graph so let's draw some toy graph here and i'll be using this one throughout the series and basically what you're trying to do is you're trying to train the embeddings for all of these nodes so basically an embedding table and this one has dimension n so this vertical dimension is m where n is the number of nodes so basically this and uh this dimension is d which is a hyper parameter and it's usually something lower dimensional than the input feature vectors so all of the nodes have features associated with them and we want to find a lower dimensionality representation of those nodes which would encode both the features and the neighborhood information now the problem with these methods is that so they would basically what they did is so if you have for example this node and this node here you want to make those two embedding vectors as similar to each other so if we just represent those vectors in 2d space like this we want to have one and two close to each other and on the other hand if we have some nodes some somewhere further away connected by some intermediate node uh with one and let's call it maybe three and maybe it's somewhere here in the table so we wanna make it be dissimilar to those two vectors okay so what's the problem with this approach so the problem is once you train this embedding table it's really hard to generalize to new unseen nodes and to new graphs so uh let me draw it like this so basically let's say this thing you we pack it up into this blob and we call it g1 and if you want to add new node or maybe even two new nodes you basically have the following you have this table which was previously trained and has meaningful vectors and you just append two new vectors here which are initial initialized randomly because we still don't know anything about those and we have to train those so now it's there are a lot of problems with doing this and i'll address some of them later but it's basically even harder once you want to generalize to unseen graphs because this graph 2 here has totally different random work statistics than this uh graph here and so this embedding uh table uh won't make any sense if you try and uh just uh use it here so you'll basically have to retrain the whole thing or or find some way to kind of align uh notes between these two graphs and it's in in any case it's cumbersome and we'll now see what graph sage did so basically they they said here uh instead of training individual embeddings for each node we learn a function that generates embeddings by sampling and aggregating uh features from a node's local neighborhood and graph sage is not uh super different from get or gcn if you looked at my previous videos but i'll um but there are some differences uh which make it make it more like uh generalizable to to do to large graphs and more efficient than get ngcn now i'll show you why so uh by the way uh graph sage so the sagebar is just an acronym from from sample and aggregate and let's see those two steps i'll just first start high level and then i'll have a pseudo code and i'll explain in detail how the algorithm works but basically what we do is instead of taking the whole neighborhood as we did with gcns and and gets we basically just do a uniform sample from the neighborhood and then we repeat that after uh through a couple of uh graph stage layers and we end up with this so basically this red node in the middle will end up having uh some parts like some mixture of representations of these orange nodes and uh basically uh these aggregate feature aggregate functions are trainable and will in their general here so the the paper itself uh suggested a couple of different variants and we'll see those in a minute but if you remember so basically what gcns did they would just simply do add these up but they would be normalized by one over square root of d i d j where those are the degrees of uh corresponding uh notes and get uh did this by attention so it dynamically figured out these coefficients uh with all of these representations and then we'll just multiply them and add them up so that was just a high level overview and i'll slowly start digging in into depth uh but like let's start with some related work uh basically before before graph sage there was a couple of methods that did similar things and planetoid uh inductive i stands for inductive uh version of planetoid uh did something similar but the difference is it only used the graph structure during training whereas graph sage and gcn and other spatial methods actually use the graph structure during the inference time and that makes them that makes them different and also uh they they later kind of so graph sage in a way generalized uh the gcn algorithm to an inductive setting and so they say here the original gcn algorithm is designed for semi supervised learning in a transductive setting and the exact algorithm requires that the full graph location is known uh during training and yeah a simple variant for algorithm can be viewed as an extension of the gcn to inductive setting and we'll see that in a couple of minutes and this is the pseudocode for the graph sage algorithm it's uh if you're familiar with gcn and get uh they have a really similar structure uh let me try and go through the pseudo code and makes uh make some sense out of it so um first the notation so they have a graph g uh that contains these sets of notes and edges they have initial uh node features uh and which are like problem specific maybe if we have a citation network uh like this uh maybe those note features would be let me connect them somehow maybe this be presided these three ones uh so these new features would maybe correspond to um you take the abstract of the paper you just apply uh word to back to every single word you just do some bag of words and so you basically average them out and you maybe add some additional information like the no degree so this one has three these ones have one etc you just append the node degree here and you append the abstract information here and that would be a particular node feature so those are these axes we have depth which is basically the number of layers in graph sage and we have these weight matrices wks which are trainable and so those will be trained during the unsupervised and supervised training process and i'll show those uh in a couple of minutes we have okay non-linearity sigma and these are important differentiable aggregated functions because they are also trainable so wks and these functions are something that we'll want to train and finally we have um this fence notation uh for neighborhood function this is basically the power set of of v so this is basically uh just a fancy way of saying maybe uh node one so this is maybe node one two three four the whole power cell would have 16 elements so the empty set you'd have the particular nodes and have the doubles you have the the triples and finally you have the the every single note and basically uh one particular mapping could be one maps to two three four and that's the particular scenario we have here so one uh gets these neighbor these are these are the nodes that are neighbors of of one okay and let's see how the the the algorithm itself functions so basically uh we start by initializing these representations with initial node features for every single node in the graph and later i'll show you the the mini batch version they they have and that's really important because they want to use this algorithm on huge graphs like maybe uh having which the graphs which have like billions of nodes so you you don't want to have to iterate over every single node in the graph you want to have uh just iterate over subsets but the idea is very similar so we iterate over every single layer so k is so iterated over different graph stage layers and for every node in the in the graph we do the following we basically take the neighborhoods so in in this particular case uh for node this would be maybe node v and these are the neighbors and we just aggregate those representations so uh now aggregate is uh can be a bunch of things and we'll get to that in a moment but it's basically either mean maybe you can use lstms you can use a max pooling a bunch of different stuff but basically you have a way to somehow take these these these representations and uh combine them aggregate them once you have that you just concatenate the current representation so the current nodes representation so we are currently at v and this is v so we take its representation and we concatenate it with the aggregated representation and we just do a feed forward layer and that's it there is one additional detail they just do this normalization step which basically makes these vectors unit norm which makes them lie on the unit hypersphere and now hypersphere is just a fancy name of saying like sphere in higher dimensions so basically if you have if the if the number of of dimensions in these representations was three we would basically have a 3d sphere and these vectors would lie somewhere on the on that sphere and we just repeat that over a couple of layers and that's it the we we get the final representations which are denoted as zv so now once we have uh these representations uh how do we train graphs sage and it turns out they used two approaches we can either train graph sage in an unsupervised manner let me just yeah here so we can either train it like this so basically if you're familiar with graph embedding methods which i mentioned we we want to make sure that these um so that uh the the the nodes that are close to each other that are connected uh have similar embeddings similar representations and on the other hand we want to to have these nodes which are not connected in the graph have very dissimilar representations and i'll try and help you out to to let's just parse this equation so basically sigma here is nothing but a sigmoid function which looks like this basically we have 0 5 here and in the limit it approaches 1. so this is sigmoid's limit and so basically here once you do a dot product between two two node representations so let's say we have a graph we have a graph like this and maybe not all of the nodes are directly connected and let's take this double here so because they are connected we want their representations after we after we do a couple of iterations through the graph sage we get the final representations and we want those representations to be as close to each other because once they are really close so once they once those vectors are really close this value gets really big and sigmoid from a big value gets closer to one and log of one equals zero so that means we are minimizing the loss function and that's something we want to do and then we have this part of the equation where we do a similar thing so we take maybe we take this node this is the negative sample and we want this two nodes to be very dissimilar so we we what we do is we want to make them as dissimilar because once they are really dissimilar they'll get really negative and because of the minus here they will be really positive and that means the loss again gets pulled down to zero so uh and we have this q factor we just uh uh which is a hyper parameter and it determines how important it is to to have these uh minimized down to zero so that's the the how the the unsupervised uh method and learning procedure for graph sage works and they see here a generator from features contained within a node's local neighborhood rather than training a unique embedding for each node so the difference between graph embedding graph embedding methods and graph sage is that we don't have a embedding table here so we are not training those fixed tables which are not prone to being later used in an inductive setting we are training those wk matrices and we are training those aggregate functions which we'll see what exactly they are in graph sage in a minute uh graph sages can also be trained in a supervised manner and for example if you have a classification task you just you just figure out the representations you do uh pretty much uh cross-entropy and you train uh those wks and those aggregation functions so i won't get into much details there an important thing about graph sage is that once we have so if we have a node and we have some huge neighborhood maybe some of these networks have like maybe over a thousand uh neighborhood notes what they do is they never uh in contrast to to gets and in contrast to gcns they never sample they never try and aggregate all of the neighborhoods they just uh sub sample maybe they use in particular they used 25 on the first layer neighbors and they used 10 uh neighbors in the second layer of of graph sage and what that means is in the first layer of of graph sage you basically take only a uniformly sample and take 25 neighbors and you aggregate those representations only and in the second uh layer you'll just take 10 and that means uh you're basically that means that this node here will basically potentially see up to 250 different uh notes okay where was i here and they mentioned that here so using we're using overloaded definition we we defined the neighborhood as a fixed sized uniform draw from uh from the set of of of those edges so from all of these neighbors from the full set from the full neighborhood and we draw different uniform samples at each iteration so that means uh this node will have uh for every single layer of graph sage will have different neighborhoods picked up so it's stochastic and uh yeah they mentioned here also so they usually use the product should be less than 500 so to to just have this uh trade-off between the performance and between the uh efficiency of this algorithm so now let's jump to those aggregator architectures and are using uh basically three different architectures so one is the mean aggregator so that means once you take so so so once you have once you sample some maybe 25 neighbors you just do element-wise mean and then you concatenate that representation with this notes with this node feature vector and you do the forward forward uh feed forward layer right so that's that's one way how you can aggregate and that's the dumbest way pretty much uh the second way they propose is similar to gcm so they they uh ditch the the concatenation all together and they just take they just take all of these so they take the neighbors the sample neighbors representations they take this representation and they do a mean over all of those they don't have any concatenation so that means this particular aggregation this this uh method they call it uh graph sage dash gcn because it's similar to gcn uh other than the the normalization constants are not the same and they mentioned that here so this differs from kipf is the author of gcm exact equation by minor normalization constant so if you remember gcn had this 1 over square root d i dj which are basically degrees of of these nodes so this node has some degree and maybe one of these neighbors has some degree so once you combine those two you normalize them with this constant whereas here they don't do that so um yeah they mentioned here an important distinction between this convolutional aggregator and our other proposed aggregators is that it does not perform the concatenation operation in line five of algorithm one so that means here you remember so they just don't do this concat part they just aggregate all of these together that's the difference whoops okay so that's the the mean aggregation function now they also tried and used lstm so now the problem with lstms is that they are inherently they're sequential and they they they are they're ordered so that means um uh basically they they had to find a way how to use lstm as a symmetric aggregator and what they did is they just applied random permutations to know its neighbors so once you have the neighborhood you just do some random permutation and then you just find the aggregation doing the following so basically if you're familiar with lstms if you're not i'll just link a really good blog from christopher ola which could help you understand gru's and lstms so basically it's initialized lstm is initialized with some random h0 state and you would input the first node representation i'll call it maybe v1 whatever and then you'd uh have some new state here and finally you dealt with the second neighbor from the current permutation and anyways you you end up with a final aggregated representation that combined all of the previous node features and that's how the lstm aggregator works so those parameters inside the lstm would be trained together with those wk matrices and those are those are all of our learnable parameters finally they have this max pooling aggregator function and what they do here is they just take the neighborhood again so they take those representations they take some subset of those representations and they just apply a feed-forward neural network here and so once we have those transformed features they would just do an element-wise uh max pooling so basically this approach is inspired by this pointnets paper and in a nutshell the pointnet's paper showed that this max pooling worked really well for them even better than doing mean pulling or doing attention based pullings so in a nutshell what this paper uh did it it works with uh point clouds and it starts with maybe end points and every single point has uh three features and those features are just the coordinates xyz and once you do some transforms and mlp transformations you end up with this um n where n is number points and you have 1024 features and they just did so they just do um element-wise max pooling so that means whatever the max element in this column is that will be put here and then you do the same for every single column and as i mentioned they they tried also doing the mean of this column and they tried doing the attention so the attention what the attention does is you basically find uh coefficients for all of these for all of these vectors rows uh so you'll have maybe alpha one for the first row you'll calculate all of those alphas you'll you finally have alpha n and now what you would do is you would basically uh just multiply this these corresponding row vectors by alphas and that's how you'd aggregate and you'll you'll get the global feature uh finally so that's pretty much everything you needed to know about graph sage aside from that detail about me how do they do the mini batch part and i'll explain that in a couple of minutes but first let's let's just go through the experiments and uh as as i previously said the the main um uh like advantage of this paper is that they're really good at inductive setting and they use this ppi protein protein traction data set and uh there they have these entirely unseen graphs which is something that that's really challenging for all of those graph method graph embedding methods and for all those previous uh methods that were inherently transductive um as i already mentioned they used sampling sizes of 25 neighbors in the first layer 10 in the second layer and one more detail is that in the multi graph setting they can't apply deep walk since um since uh because of this fact so so the uh so in the multi-graph uh setting we cannot apply deepwook since the embedding space is generated by running the depot algorithm on different disjoint graphs can be arbitrarily rotated with respect to each other and i'll touch on that a bit later but just for now just keep that in hand that those graph embedding methods are really hard to to to to generalize to inductive setting okay let's see the results uh they had four baselines the random classifier they just used the raw features so those are those i mentioned those uh maybe you have the abstract here you have uh degree information and that's your feature vector and here they just use those raw features and maybe just do some mlp on top of those and that's how they learn to classify without using any graph structure information whatsoever on the other hand they had deep walk which was trained a bit smarter basically it encodes this graph structure as well and here is a combination of doing both of those and then they have uh four different graph sage algorithms depending on the aggregation function they use so we have gcn we have mean lstm and pool and here we can see it pretty much steadily increases here and also they have the unsupervised trained graph sage and they have the supervised trained graph sage and you can also you can also expect that this will increase and it did so uh what we can see here is that uh basically yeah they they got better results than all of those baselines and um now there is a the best aggregator functions seem to be lstm and pooling whereas pulling is a lot cheaper so they uh finally gave it a slight edge and they they they said that the pulling had the best performance altogether it's probably the best overall because it has the best trade-off between the performance and the efficiency uh yeah here they just in this chart they just uh showed that these graph embedding methods such as steep book have a really high cost to do the inference on on the full test set because they have to recalculate to retrain uh those embeddings and that's really computationally costly and this is log scale here so that's 1000 seconds that's much more than what graph sage takes they also have a small chart here where they plot how the performance so the f1 score and how the runtime increase as we increase the sample size so if you remember we had we had 25 and we used 10 and here they just experimented they went all the way on up to 75 neighbors and we can see that the performance does increase as well as the runtime so empirically they just figured out that some um smaller neighborhood sizes such as 25 and 10 are performing the best overall okay that was pretty much it uh for this main part of the paper uh yeah they mentioned here that so graph sage lstm is significantly slower than graph sage pool so approximately twice so perhaps giving the pooling base the aggregator a slight edge overall um one more interesting theorem here and they have a whole proof for this thing that's like four pages long and i won't get into the mathematics in this video but i just want to briefly explain what they said here um what they say here is that graph sage even though it heavily relies on features and like aggregating those features and stuff it understands the graph structure really well so how they proved that is the following so they they showed that the final representation so zvs if you remember from the pseudo algorithm uh can be made like arbitrarily close to these cvs which are basically cluster something called clustering coefficients and um and i'll now explain what those are so this equation again tells us that we can make the representations arbitrarily close so the whatever epsilon you give me how no matter how small like maybe you give me 0.01 i can make the zv close enough to the real um clustering coefficient so what's the clustering coefficient basically if you have some small graph here something like this and let's say this node one is connected to these three nodes basically um the clustering coefficient let's call it c for node one is uh if these are all connected together like this so they form a clique then the clustering coefficient equals one because the neighborhood nodes have the the highest connectivity pattern that's possible and that's a fully connected graph so if we were to just disconnect maybe these two edges would be left with this one and the clustering coefficient would drop to one third so basically what they state here is that the graph sage can learn all of these uh so this is like a structural information in the graph and they can learn it to an arbitrary precision okay uh let me wrap up this paper explaining the mini but mini batch part and something related to graph embedding methods which will be interesting um basically the main part the only difference is this so we won't be iterating over every single node in the graph because the graph can be really huge uh like maybe a couple of billion notes so basically they calculate these b sets so uh if we have let's assume we have two layers in graph sage that means they'll be calculating set b0 set b1 and set b2 and let me try and illustrate what what those are and how they look like so basically if we have some huge graph that has a couple of billion nodes maybe we're only interested in representations of a small subset of nodes which we'll call b2 now because of the way how graph sage works it just aggregates the neighborhood of every single node in a particular layer that means we'll need one hop neighborhood of the nodes in b2 and let's call that b1 and now because we have two layers we'll also need the one hop neighborhood of b1 which is basically b0 and there will be a superset of p1 which is itself a superset of b2 so this would this this is what the the algorithm would um put in these b sets so let me just zoom in a little bit on this one so we start with the so these are the target nodes that we want to calculate the representation for and so we initialize b2 with that one and then we start going towards one we we initially initialized b1 b1 we initialized it with b2 nodes and then we iterate over b2's nodes so over these nodes and we just add up we just do a union of all of the neighbors of all of the nodes in b2 so we'll go through nodes and maybe some of these nodes will have neighbors that are here and thus will will slowly build up b1 and then we'll slowly build up b0 and then in the main loop uh what we do is we first initialize the initial representations with features uh feature vectors coming from b0 set so we'll have we'll only need to uh take we only need to think about b0 vectors we don't have to care about any of these nodes so we have we gain efficiency and so now the algorithm what it does we start with the with b1 so we start with this with these nodes so we iterate over those nodes and we do aggregations some of them will belong to b0 and i hope luckily we already uh we have already have those in memory and we have those feature vectors so we can calculate all of the representations in b1 and once we have b1 in the next cycle once k gets to 2 we'll be iterating over nodes in b2 and we'll be building up representations and we'll likely have all of these representations calculated from the last iteration so we can finally have all of the representations that we're interested in in b2 uh calculated and put into zv zu's and that's pretty much it that's how the mini batch algorithm works and hopefully that was clear enough if you have any questions please comment down in the comment section i'll try and answer uh all of them and yeah one interesting thing is they sample with replacement in cases where the sample size is larger than the nodes degree so maybe we have a node and it only has maybe three neighbors like this but if you remember s1 was 25 and s2 was 10 which means we'll have to repeat some of these features before we call the aggregate function so maybe we'll have eight of these we'll have eight of these and we'll have nine of these and then we'll call the aggregate function so that means uh sampling with replacement so yeah um that's a small detail and this is one more interesting detail uh and as you can see graph sage is all about these small details which are making the implementation a lot more efficient and it can later be used on huge graphs and here what they say is basically they do a pre-processing step on these huge graphs and in case some of the nodes has maybe 1000 edges they'll just subsample up to 128 of them so every single node will have its degree less than or equal to 128 and they say here due to heavy tailed nature of degree distributions we downsample the edges in all graphs before feeding them into the graph sage algorithm in particular with subsample edges so that no node has degree larger than 128. uh the final thing i want to mention is the part that i mentioned in the beginning and that's these um what's the problem with once you're once you're dealing with these embedding tables so um basically what you're doing by doing those um uh trying to make some vectors similar and some dissimilar you're basically doing implicit factorization so basically you're trying to calculate that z matrix and this is number of notes this is the hidden dimension d and your if you do transpose this as z matrix into z t and you just do multiplication what you end up is this matrix m which basically contains um all of these uh similarities between vectors so you you have you have a you have a how similar vector one is with vector one and you'll have how similar vector one is with vector two et cetera so you have a huge m by n matrix which basically tells you how similar or dissimilar those embedding feature vectors are and you're basically by doing those random walks and training those graph embedding methods you're you're implicitly trying to find this uh implicit m matrix which contains the random walk uh statistics you know the problem is that uh as you can see here you can basically have a whole family of these z matrices which uh basically add up to m and that means uh those those embedding vectors can rotate they can the whole space can rotate and you'd still have the same matrix m so now why why is that the problem so the problem is once you try to add new nodes to your graph as we saw in the beginning so basically if you try and you have graph g1 you have embedding table for g1 and you try to add maybe two new notes and what happens is you'll have to update the table and if you just do the following if you just if you maybe so you see basically you had this table previously and now you're trying to add two new vectors but the thing is you train a classifier for those vectors here so you have some some classification head here which was trained for those and once you add up these two new random vectors and if you try to retrain everything then these won't be working correctly with this classifier anymore and you'll mess up everything you you all of the training will be pretty much uh in vain and so yeah they mention it here moreover if we update all embeddings during training not just for the new nodes as suggested by deepwalk uh then the embedding space can arbitrarily rotate compared to the embedding space that we trained our classifier on which only further exasperates the problem so basically once you add again read reading once you add notes if you just do this naive retraining you'll mess up the classifier because all of these will start rotating because as we already saw uh all of those families are still add up to this matrix m and they suggested here a couple of reasonable approaches so some reasonable approach is to alleviate this issue of statistical drift are to not update the already trained embeddings when optimizing the embeddings for new test nodes so that means we pretty much freeze up all of these so we freeze them up we don't change those and second to only keep existing nodes as context nodes in the sample random box i to ensure that every dot product in the skipgram objective is a product of an already trained node and a new test node so that means once you're doing those random works uh you only take uh context nodes from these that are already trained so you you can take for example if this is a new node let's call it node number three and this is also a new node and even though this node three is on this random walk because it's a new node we won't be using it as a context node if you're familiar with how the where to back and these graph embedding methods work you'll understand what i'm talking about and so basically the second approach the the the second suggestion they have is only use notes that are already trained as the context there was a lot of information back in this video i i think it's worth just comparing graph sage with get and with gcn because all of the three are spatial methods and get and gcn are the most cited papers in the genome literature so the structure is really similar if you take a look at it so we have a we have a node and we have a neighborhood and what gcn and what get do is the following they just aggregate all of the node features uh and before before they add them up they just scale them with a certain coefficients so basically gcn uh takes this one over square root di times tj which are the degrees of those nodes and so we we take both the neighborhood features as well as the current nodes feature and we just uh scale them with this uh that's gcm and uh what get does instead it just computes dynamically these alpha coefficients which are just attention coefficients and then multiplies those nodes with these coefficients that's good once you multiply them you just add them up and then you do a simple projection followed by a simple non-linearity such as value so you have this let's call it aggregated features whatever and then we just take those we we project them and we do nonlinearity such as value uh on the other side what graph sage does is uh it also it it doesn't take the full neighborhood it takes a sub-sample uniform some sample of the neighborhood and it again aggregates uh those features in bunch of different ways some of them you saw like mean you can do lstm regulation whatever and finally you again do uh projection and followed by a non-linearity so the pattern is really similar graph sage is a bit more efficient because it subsamples the neighborhood and it experimented with different aggregation function and also some of the other details you heard uh during this video so that was it uh if you found this video useful um i'd really appreciate you leaving some feedback in the form of a comment in the comment section that will help me like two-fold first thing is i'll get much better by reading your feedback what i'm doing right what i'm doing wrong and secondly you'll boost uh these videos uh like because of the the way youtube algorithm functions so anyways if you found this video useful consider subscribing and consider hitting that bell icon if you want to get notified for every single video i make and yep until next time keep learning deep [Music]