Graph SAGE - Inductive Representation Learning on Large Graphs | GNN Paper Explained
❤️ Become The AI Epiphany Patreon ❤️ ► https://www.patreon.com/theaiepiphany
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬

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

The first paper that started pushing the usage of GNNs for super large graphs.

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

▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 
✅ Graph SAGE paper: https://arxiv.org/abs/1706.02216
✅ Chris Olah on LSTMs: https://colah.github.io/posts/2015-08-Understanding-LSTMs/
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 

⌚️ Timetable:
00:00 Intro
00:38 Problems with previous methods
04:30 High-level overview of the method
06:10 Some notes on the related work
07:13 Pseudo-code explanation
12:03 How do we train Graph SAGE?
15:40 Note on the neighborhood function
17:40 Aggregator functions
23:30 Results
28:00 Expressiveness of Graph SAGE
30:10 Mini-batch version
35:30 Problems with graph embedding methods (drift)
40:30 Comparison with GCN and GAT

▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 
💰 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/ 
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬

#graphsage #gnns #graphtheory
 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 GraphSAGE. So basically the main proposition of GraphSAGE is that they developed a method that's inherently inductive and can work on huge graphs. So the later paper that came after GraphSAGE is PinSAGE and I'll be covering that one in one of the next videos and this is basically a precursor to that paper which is really awesome and has an awesome implication as a recommender system in Pinterest. So 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 nodes. So let me do just a quick recap of how those methods basically work. So what you have is, you have a Static 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 n, where n is the number of nodes. So basically this. And this dimension is d, which is a hyperparameter and is 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 node somewhere further away, connected by some intermediate node with one, and let's call it maybe three, and maybe it's somewhere here in the table. So we want to 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 let me draw it like this. So basically let's say this thing, we pick 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 initialized randomly because we still don't know anything about those and we have to train those. So now 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 too here has totally different random walk statistics than this graph here and so this embedding table won't make any sense if you try and just use it here. So you'll basically have to retrain the whole thing or find some way to kind of align nodes between these two graphs and in any case it's cumbersome and we'll now see what GraphSage did. So basically they said here instead of training individual embeddings for each node, we'll learn a function that generates embeddings by sampling and aggregating features from a node's local neighborhood. And GraphSage is not super different from GET or GCN if you looked at my previous videos, but there are some differences which make it more like generalizable to large graphs and more efficient than GET and GCN and now I'll show you why. So by the way, GraphSage, the Sage part is just an acronym from sample and aggregate. And let's see those two steps. I'll just first start high level and then I'll have a pseudocode 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 GETs, we basically just do a uniform sample from the neighborhood and then we repeat that through a couple of GraphSage layers and we end up with this. So basically this red node in the middle will end up having some parts, like some mixture of representations of these orange nodes. And basically these aggregate feature, aggregate functions are trainable and they're general here. So the paper itself 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 1 over square root of di dj, where those are the degrees of corresponding nodes. And GET did this via attention, so it dynamically figured out these coefficients with all of these representations and then we just multiplied them and added them up. So that was just a high level overview and I'll slowly start digging into depth, but let's start with some related work. Basically before GraphSage, there was a couple of methods that did similar things and Planetoid inductive, i stands for inductive, version of Planetoid did something similar, but the difference is it only used the graph structure during training, whereas GraphSage and GCN and other spatial methods actually use the graph structure during the inference time and that makes them different. And also they later kind of, so GraphSage in a way generalized the GCN algorithm to an inductive setting and then 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 laplation is known during training. And yeah, a simple variant of our 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 GraphSage algorithm. It's, if you're familiar with GCN and GET, they have a really similar structure. Let me try and go through the pseudocode and make some sense out of it. So first the notation. So they have a graph G that contains these sets of nodes and edges. They have initial node features and which are like problem specific. Maybe if we have a citation network like this, maybe those node features would be, let me connect them somehow, maybe this paper cited these three ones. So these node features would maybe correspond to, you take the abstract of the paper, you just apply word2back 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 node 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 GraphSage 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 in a couple of minutes. We have non-linearities, 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 this fence notation for neighborhood function. This is basically the power set of V. So this is basically just a fancy way of saying maybe node one, so this is maybe node one, two, three, four. The whole power set would have 16 elements so the empty set you'd have the particular nodes and have the tuples, you have the triples and finally you have the every single node and basically one particular mapping could be one, maps two, two, three, four and that's the particular scenario we have here. So one gets these neighbors, these are the nodes that are neighbors of one. Okay and let's see how the algorithm itself functions. So basically 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 have and that's really important because they want to use this algorithm on huge graphs like maybe having which the graphs which have like billions of nodes so you don't want to have to iterate over every single node in the graph, you want to have just iterate over subsets but the idea is very similar. So we iterate over every single layer so Ks, so we iterate over different graph sage layers and for every node in the in the graph we do the following. We basically take the neighborhoods so in this particular case for node this would be maybe node v and these are the neighbors and we just aggregate those representations. So now aggregate is 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 max pooling, a bunch of different stuff but basically you have a way to somehow take these representations and 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 will lie somewhere on the on that sphere and we just repeat that over a couple of layers and that's it. We get the final representations which are denoted as zv. So now once we have these representations how do we train graph 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 so that the the the nodes that are close each other that are connected 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 to let's just parse this equation so basically sigma here is nothing but a sigmoid function which looks like this it basically we have zero five here and in the limit it approaches one so this is sigmoid's limit and so basically here once you do a dot product between 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 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 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 and we have this q factor we just which is a hyperparameter and it determines how important it is to to have these minimized down to zero so that's the how the the unsupervised method and learning procedure for graph sage works and they see here a generator from futures 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 inductive setting we are training those wk matrices and we're training those aggregate functions which we'll see what exactly they are in graph sage in a minute graph sages can also be trained and in a supervised manner and for example if you have a classification task is just you just figure out the representations you do pretty much cross entropy and you train 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 neighborhood nodes what they do is they never in contrast to to get 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 neighbors in the second layer of graph sage and what that means is in the first layer of graph sage you basically take only a uniformly sample and take 25 neighbors and you aggregate those representations only and in the second layer you'll just take 10 and that means uh you're basically um that means that um this node here will basically potentially see up to 250 different uh nodes okay where was i here and they mentioned that here so using we're using overloaded definition we we define the neighborhood as a fixed size 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 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 trade-off between the performance and between the uh efficiency of this algorithm so now let's jump to those aggregator architectures and they are using 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 can concatenate that representation with this nodes 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 ditch the the concatenation altogether 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 method they call it graph sage dash gcm because it's similar to gcn other than the the normalization constants are not the same and they mentioned that here so this differs from kipf kipf is the author of gcm exact equation by a minor normalization constant so if you remember gcn had this one over square root di 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 if you remember so they just uh 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 lstms and now the problem with lstms is that they are inherently they are sequential and they they are they are ordered so that means 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 nodes 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 would help you understand groose and lstms so basically it's initialized lstm is initialized with some random uh h0 state and you would input the first node representation i'll call it maybe v1 whatever and then you'd have some new state here and finally you'd output the second neighbor from the current permutation and anyways you you end up with a final aggregated representation that combined all of the previous uh node uh 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 max pooling so basically this approach is inspired by this point nets paper and in a nutshell the point nets paper showed that this max pooling worked really well for them even better than doing mean pooling or doing attention based poolings so in a nutshell what this paper did it it works with point clouds and it starts with maybe endpoints and every single point has three features and those features are just the coordinates x y z and once you do some transforms and mlp transformations you end up with this n where n is number of points and you have 1024 features and they just did so they just do 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 coefficients for all of these for all of these vectors rows so you have maybe alpha one for the first row you'll calculate all of those alphas you'll finally have alpha n and now what we would do is you would basically just multiply these these corresponding row vectors by alphas and that's how you'd aggregate and you'll get the global feature finally so that's pretty much everything you needed to know about graph sage aside from that detail about how do they do the mini batch part and i'll explain that in a couple minutes but first let's let's just go through the experiments and as i previously said the main like advantage of this paper is that they are really good at inductive setting and they use this ppi protein protein traction data set and there they have these entirely unseen graphs which is something that's really challenging for all of those graph method graph embedding methods and for all those previous methods that were inherently transductive um methods that were inherently transductive 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 apply deep walk since since because of this fact so the so in the multi graph setting we cannot apply deep walk since the embedding space is generated by running the deep walk 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 they had four baselines the random classifier they just use the raw features so those are those i mentioned those 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 um on the other hand they had deep walk which was trained a bit smarter basically it encodes to 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 gcm 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 what we can see here is that basically yeah they got better results than all of those baselines and now there is the best aggregator functions seem to be lstm and pooling whereas pooling is a lot cheaper so they finally gave it a slight edge and they they said that the pooling had the best performance altogether it's probably the best overall because it has um that the best trade-off between the performance and the efficiency uh yeah here they just in this chart they just um showed that these graph embedding methods such as deep walk 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 thousand 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 uh increase as we increase the 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 uh empirically they just figured out that some smaller neighborhood sizes such as 25 and 10 are performing the best overall okay that was pretty much it 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 based 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 um 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 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 batch mini batch part and something related to graph embedding methods which will be interesting basically the main part the only difference is this so we won't be iterating over everything 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 nodes 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 b zero set b one and set b two 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 that will be a superset of b1 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 we initially initialized b1 b1 we initialize 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 we'll have neighbors that are here and thus we'll we'll slowly build up b1 and then we'll slowly build up b0 and then the main loop what we do is we first initialize the initial representations with features feature vectors coming from b0 set so we'll have we'll only need to take we'll 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 hopefully luckily we already 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 luckily have all of these representations calculated from the last iteration so we can finally have all of the representations that we are interested in in b2 calculated and put into zv zus 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 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 sampling with replacement so yeah that's a small detail and this is one more interesting detail 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 thousand edges they'll just sub sample 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 down sample the edges in all graphs before feeding them into the graph sage algorithm in particular we sub sample edges so that no node has a degree larger than 128 the final thing i want to mention is the part that i mentioned in the beginning and that's these what's the problem once you're once you're dealing with these embedding tables so basically what you're doing by doing those 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 nodes this is the hidden dimension d and you're if you do transpose this z matrix into zt and you just do multiplication what you end up is this matrix m which basically contains all of these similarities between vectors so 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 etc 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 you find this implicit m matrix which contains the random walk statistics you know the problem is that as you can see here you can basically have a whole family of these z matrices which basically add up to m and that means those those embedding vectors can rotate they can the whole space can rotate and you'd still have the same matrix m so now what 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 nodes 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 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 had 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 in vain and so yeah they mentioned here moreover if we update all embeddings during training not just for the new nodes as suggested by deep walk then the embedding space can arbitrarily rotate compared to the embedding space that we train our classifier on which only further exasperates the problem so basically once you add again re-dating once you add the nodes 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 all of those families are still add up to this matrix m and they suggested here a couple of reasonable approaches so some reasonable approaches 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.e. to ensure that every dot product in the skip gram objective is a product of an already trained node and a new test node so that means once you're doing those random walks you only take 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 word2vec 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 nodes that are already trained as the context there was a lot of information packed in this video 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 gnn 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 nodes aggregate all of the node features and before before they add them up they just scale them with a certain coefficients so basically gcn 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 scale them with this that's gcm and 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 get once you multiply them you just add them up and then you do a simple projection followed by a simple non-linearity such as relu so you have this let's call it aggregated features whatever and then we just take those we project them and we do non-linearity such as relu on the other side what graph sage does is 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 those features in bunch of different ways some of them you saw like mean you can do lstm aggregation whatever and finally you again do a projection and followed by a non-linearity so the pattern is really similar graph sage is a bit more efficient because it's sub samples the neighborhood and it experimented with different aggregation function and also some of the other details you heard during this video so that was it if you found this video useful i'd really appreciate you leaving some feedback in the form of a comment in the comment section that will help me like twofold 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 these videos like because of the the way youtube algorithm functions so anyways if you found this video useful consider subscribing and consider hitting the bell icon if you want to get notified for every single video i make and yep until next time keep learning deep
[{"start": 0.0, "end": 5.76, "text": " Hi, in this video I'm continuing with Graph Neural Network series and I'll be covering this paper called"}, {"start": 5.76, "end": 12.0, "text": " Inductive Representation Learning on Large Graphs or also known as GraphSAGE."}, {"start": 12.0, "end": 18.8, "text": " So basically the main proposition of GraphSAGE is that they developed a method that's inherently inductive"}, {"start": 18.8, "end": 25.6, "text": " and can work on huge graphs. So the later paper that came after GraphSAGE is PinSAGE and I'll be covering that one"}, {"start": 25.6, "end": 32.800000000000004, "text": " in one of the next videos and this is basically a precursor to that paper which is really awesome and has an"}, {"start": 32.800000000000004, "end": 40.0, "text": " awesome implication as a recommender system in Pinterest. So basically they say here,"}, {"start": 40.0, "end": 45.6, "text": " most existing approaches require that all nodes in the graph are present during training of the embeddings."}, {"start": 45.6, "end": 51.2, "text": " These previous approaches are inherently transductive and do not naturally generalize to unseen nodes."}, {"start": 51.2, "end": 57.6, "text": " So let me do just a quick recap of how those methods basically work. So what you have is,"}, {"start": 57.6, "end": 67.6, "text": " you have a Static Graph. So let's draw some toy graph here and I'll be using this one throughout the series."}, {"start": 67.6, "end": 74.80000000000001, "text": " And basically what you're trying to do is you're trying to train the embeddings for all of these nodes."}, {"start": 74.8, "end": 81.2, "text": " So basically an embedding table and this one has dimension n. So this vertical dimension is n,"}, {"start": 81.2, "end": 91.6, "text": " where n is the number of nodes. So basically this. And this dimension is d, which is a hyperparameter"}, {"start": 92.16, "end": 100.0, "text": " and is usually something lower dimensional than the input feature vectors. So all of the nodes have"}, {"start": 100.0, "end": 107.04, "text": " features associated with them and we want to find a lower dimensionality representation of those nodes,"}, {"start": 107.04, "end": 112.24, "text": " which would encode both the features and the neighborhood information. Now the problem with"}, {"start": 112.24, "end": 117.6, "text": " these methods is that, so they would basically what they did is, so if you have for example"}, {"start": 118.24000000000001, "end": 124.64, "text": " this node and this node here, you want to make those two embedding vectors as similar to each other."}, {"start": 124.64, "end": 130.32, "text": " So if we just represent those vectors in 2D space like this, we want to have one and two"}, {"start": 131.36, "end": 136.96, "text": " close to each other. And on the other hand, if we have some node somewhere further away,"}, {"start": 136.96, "end": 143.68, "text": " connected by some intermediate node with one, and let's call it maybe three, and maybe it's"}, {"start": 143.68, "end": 150.24, "text": " somewhere here in the table. So we want to make it be dissimilar to those two vectors. Okay,"}, {"start": 150.24, "end": 156.08, "text": " so what's the problem with this approach? So the problem is once you train this embedding table,"}, {"start": 156.08, "end": 163.04000000000002, "text": " it's really hard to generalize to new unseen nodes and to new graphs. So let me"}, {"start": 163.84, "end": 169.60000000000002, "text": " draw it like this. So basically let's say this thing, we pick it up into this blob and we call"}, {"start": 169.60000000000002, "end": 176.48000000000002, "text": " it G1. And if you want to add new node or maybe even two new nodes, you basically have the"}, {"start": 176.48, "end": 182.32, "text": " following. You have this table which was previously trained and has meaningful vectors and you just"}, {"start": 182.32, "end": 190.16, "text": " append two new vectors here which are initialized randomly because we still don't know anything"}, {"start": 190.16, "end": 198.39999999999998, "text": " about those and we have to train those. So now there are a lot of problems with doing this and"}, {"start": 198.39999999999998, "end": 203.12, "text": " I'll address some of them later, but it's basically even harder once you want to generalize to"}, {"start": 203.12, "end": 211.04, "text": " unseen graphs because this graph too here has totally different random walk statistics than this"}, {"start": 211.76, "end": 221.68, "text": " graph here and so this embedding table won't make any sense if you try and just use it here."}, {"start": 222.48000000000002, "end": 229.52, "text": " So you'll basically have to retrain the whole thing or find some way to kind of align nodes"}, {"start": 229.52, "end": 237.12, "text": " between these two graphs and in any case it's cumbersome and we'll now see what GraphSage did."}, {"start": 237.12, "end": 242.8, "text": " So basically they said here instead of training individual embeddings for each node,"}, {"start": 242.8, "end": 247.44, "text": " we'll learn a function that generates embeddings by sampling and aggregating"}, {"start": 248.32000000000002, "end": 255.12, "text": " features from a node's local neighborhood. And GraphSage is not super different from"}, {"start": 255.12, "end": 262.08, "text": " GET or GCN if you looked at my previous videos, but there are some differences which make it"}, {"start": 262.08, "end": 269.52, "text": " more like generalizable to large graphs and more efficient than GET and GCN and now I'll show you"}, {"start": 269.52, "end": 278.56, "text": " why. So by the way, GraphSage, the Sage part is just an acronym from sample and aggregate."}, {"start": 278.56, "end": 283.92, "text": " And let's see those two steps. I'll just first start high level and then I'll have a pseudocode"}, {"start": 283.92, "end": 289.28000000000003, "text": " and I'll explain in detail how the algorithm works. But basically what we do is instead of taking the"}, {"start": 289.28000000000003, "end": 297.92, "text": " whole neighborhood as we did with GCNs and GETs, we basically just do a uniform sample from the"}, {"start": 297.92, "end": 305.84000000000003, "text": " neighborhood and then we repeat that through a couple of GraphSage layers and we end up with"}, {"start": 305.84, "end": 313.35999999999996, "text": " this. So basically this red node in the middle will end up having some parts, like some mixture"}, {"start": 313.35999999999996, "end": 322.15999999999997, "text": " of representations of these orange nodes. And basically these aggregate feature, aggregate"}, {"start": 322.15999999999997, "end": 331.59999999999997, "text": " functions are trainable and they're general here. So the paper itself suggested a couple of"}, {"start": 331.6, "end": 337.28000000000003, "text": " different variants and we'll see those in a minute. But if you remember, so basically what GCNs did,"}, {"start": 337.28000000000003, "end": 347.44, "text": " they would just simply do add these up, but they would be normalized by 1 over square root of"}, {"start": 347.44, "end": 359.04, "text": " di dj, where those are the degrees of corresponding nodes. And GET did this via attention, so"}, {"start": 359.04, "end": 364.64000000000004, "text": " it dynamically figured out these coefficients with all of these representations and then we just"}, {"start": 364.64000000000004, "end": 370.08000000000004, "text": " multiplied them and added them up. So that was just a high level overview and I'll slowly start"}, {"start": 370.08000000000004, "end": 378.88, "text": " digging into depth, but let's start with some related work. Basically before GraphSage, there"}, {"start": 378.88, "end": 384.8, "text": " was a couple of methods that did similar things and Planetoid inductive, i stands for inductive,"}, {"start": 384.8, "end": 390.64, "text": " version of Planetoid did something similar, but the difference is it only used the graph structure"}, {"start": 390.64, "end": 397.44, "text": " during training, whereas GraphSage and GCN and other spatial methods actually use the graph"}, {"start": 397.44, "end": 406.0, "text": " structure during the inference time and that makes them different. And also they later kind of,"}, {"start": 406.0, "end": 412.08000000000004, "text": " so GraphSage in a way generalized the GCN algorithm to an inductive setting and then"}, {"start": 412.08, "end": 417.12, "text": " GCN algorithm to an inductive setting and so they say here the original GCN algorithm is designed"}, {"start": 417.12, "end": 422.0, "text": " for semi-supervised learning in a transductive setting and the exact algorithm requires that the"}, {"start": 422.0, "end": 428.24, "text": " full graph laplation is known during training. And yeah, a simple variant of our algorithm can"}, {"start": 428.24, "end": 433.36, "text": " be viewed as an extension of the GCN to inductive setting and we'll see that in a couple of minutes."}, {"start": 434.47999999999996, "end": 441.59999999999997, "text": " And this is the pseudocode for the GraphSage algorithm. It's, if you're familiar with GCN"}, {"start": 441.6, "end": 447.20000000000005, "text": " and GET, they have a really similar structure. Let me try and go through the pseudocode and"}, {"start": 447.20000000000005, "end": 454.96000000000004, "text": " make some sense out of it. So first the notation. So they have a graph G that contains these sets"}, {"start": 454.96000000000004, "end": 463.6, "text": " of nodes and edges. They have initial node features and which are like problem specific. Maybe"}, {"start": 463.6, "end": 470.32000000000005, "text": " if we have a citation network like this, maybe those node features would be, let me connect"}, {"start": 470.32, "end": 476.8, "text": " them somehow, maybe this paper cited these three ones. So these node features would maybe correspond"}, {"start": 476.8, "end": 484.15999999999997, "text": " to, you take the abstract of the paper, you just apply word2back to every single word, you just do"}, {"start": 484.15999999999997, "end": 489.6, "text": " some bag of words and so you basically average them out and you maybe add some additional"}, {"start": 489.6, "end": 496.0, "text": " information like the node degree. So this one has three, these ones have one, etc. You just append"}, {"start": 496.0, "end": 501.36, "text": " the node degree here and you append the abstract information here and that would be a particular"}, {"start": 501.36, "end": 507.44, "text": " node feature. So those are these axes. We have depth which is basically the number of layers in"}, {"start": 507.44, "end": 514.32, "text": " GraphSage and we have these weight matrices WKs which are trainable and so those will be trained"}, {"start": 514.32, "end": 520.0, "text": " during the unsupervised and supervised training process and I'll show those in a couple of minutes."}, {"start": 520.0, "end": 526.16, "text": " We have non-linearities, sigma and these are important differentiable aggregated functions"}, {"start": 526.16, "end": 532.24, "text": " because they are also trainable. So WKs and these functions are something that we'll want to train"}, {"start": 532.24, "end": 538.24, "text": " and finally we have this fence notation for neighborhood function. This is basically the"}, {"start": 538.24, "end": 548.0, "text": " power set of V. So this is basically just a fancy way of saying maybe node one, so this is maybe"}, {"start": 548.0, "end": 555.68, "text": " node one, two, three, four. The whole power set would have 16 elements so the empty set you'd have"}, {"start": 555.68, "end": 562.4, "text": " the particular nodes and have the tuples, you have the triples and finally you have the every single"}, {"start": 562.4, "end": 573.84, "text": " node and basically one particular mapping could be one, maps two, two, three, four and that's the"}, {"start": 573.84, "end": 580.64, "text": " particular scenario we have here. So one gets these neighbors, these are the nodes that are"}, {"start": 580.64, "end": 588.4, "text": " neighbors of one. Okay and let's see how the algorithm itself functions. So basically we start"}, {"start": 588.4, "end": 595.44, "text": " by initializing these representations with initial node features for every single node in the graph"}, {"start": 596.24, "end": 602.24, "text": " and later I'll show you the the mini batch version they have and that's really important because"}, {"start": 602.24, "end": 609.12, "text": " they want to use this algorithm on huge graphs like maybe having which the graphs which have like"}, {"start": 609.12, "end": 613.92, "text": " billions of nodes so you don't want to have to iterate over every single node in the graph,"}, {"start": 613.92, "end": 620.72, "text": " you want to have just iterate over subsets but the idea is very similar. So we iterate over every"}, {"start": 620.72, "end": 628.16, "text": " single layer so Ks, so we iterate over different graph sage layers and for every node in the"}, {"start": 628.16, "end": 635.76, "text": " in the graph we do the following. We basically take the neighborhoods so in this particular case"}, {"start": 636.8, "end": 643.1999999999999, "text": " for node this would be maybe node v and these are the neighbors and we just aggregate those"}, {"start": 643.1999999999999, "end": 650.24, "text": " representations. So now aggregate is can be a bunch of things and we'll get to that in a moment but"}, {"start": 650.24, "end": 656.0799999999999, "text": " it's basically either mean maybe you can use LSTMs, you can use max pooling, a bunch of different stuff"}, {"start": 656.08, "end": 664.48, "text": " but basically you have a way to somehow take these representations and combine them, aggregate them."}, {"start": 664.48, "end": 669.0400000000001, "text": " Once you have that you just concatenate the current representation so the current nodes"}, {"start": 669.0400000000001, "end": 676.0, "text": " representation so we are currently at v and this is v so we take its representation and we concatenate"}, {"start": 676.0, "end": 684.24, "text": " it with the aggregated representation and we just do a feed forward layer and that's it. There is one"}, {"start": 684.24, "end": 692.48, "text": " additional detail they just do this normalization step which basically makes these vectors unit"}, {"start": 693.04, "end": 699.6, "text": " norm which makes them lie on the unit hypersphere and now hypersphere is just a fancy name of saying"}, {"start": 699.6, "end": 705.76, "text": " like sphere in higher dimensions so basically if you have if the if the number of of dimensions"}, {"start": 705.76, "end": 710.64, "text": " in these representations was three we would basically have a 3d sphere and these vectors"}, {"start": 710.64, "end": 718.08, "text": " will lie somewhere on the on that sphere and we just repeat that over a couple of layers and that's"}, {"start": 718.08, "end": 726.64, "text": " it. We get the final representations which are denoted as zv. So now once we have these"}, {"start": 726.64, "end": 733.52, "text": " representations how do we train graph sage and it turns out they used two approaches we can either"}, {"start": 733.52, "end": 741.36, "text": " train graph sage in an unsupervised manner. Let me just yeah here so we can either train it like"}, {"start": 741.36, "end": 746.88, "text": " this so basically if you're familiar with graph embedding methods which I mentioned we we want to"}, {"start": 746.88, "end": 753.84, "text": " make sure that these so that the the the nodes that are close each other that are connected"}, {"start": 754.48, "end": 760.48, "text": " have similar embeddings similar representations and on the other hand we want to to have these"}, {"start": 760.48, "end": 766.4, "text": " nodes which are not connected in the graph have very dissimilar representations and I'll try and"}, {"start": 766.4, "end": 773.6800000000001, "text": " help you out to to to let's just parse this equation so basically sigma here is nothing"}, {"start": 773.6800000000001, "end": 780.16, "text": " but a sigmoid function which looks like this it basically we have zero five here"}, {"start": 780.16, "end": 791.68, "text": " and in the limit it approaches one so this is sigmoid's limit and so basically here"}, {"start": 791.68, "end": 797.68, "text": " once you do a dot product between two node representations so let's say we have a graph"}, {"start": 798.48, "end": 806.56, "text": " we have a graph like this and maybe not all of the nodes are directly connected and let's take"}, {"start": 806.56, "end": 813.76, "text": " and let's take this double here so because they are connected we want their representations"}, {"start": 813.76, "end": 818.0, "text": " after we after we do a couple of iterations through the graph sage we get the final"}, {"start": 818.0, "end": 823.1999999999999, "text": " representations and we want those representations to be as close to each other because once they are"}, {"start": 823.1999999999999, "end": 829.04, "text": " really close so once they once those vectors are really close this value gets really big"}, {"start": 829.04, "end": 836.56, "text": " and sigmoid from a big value gets closer to one and log of one equals zero so that means"}, {"start": 836.56, "end": 840.64, "text": " we are minimizing the loss function and that's something we want to do and then we have this"}, {"start": 840.64, "end": 848.3199999999999, "text": " part of the equation where we do a similar thing so we take maybe we take this node this is the"}, {"start": 848.3199999999999, "end": 857.68, "text": " negative sample and we want this two nodes to be very dissimilar so we we what we do is we want to"}, {"start": 857.68, "end": 862.7199999999999, "text": " we want to make them as dissimilar because once they are really dissimilar they'll get really"}, {"start": 862.7199999999999, "end": 870.0, "text": " negative and because of the minus here they will be really positive and that means the loss again"}, {"start": 870.0, "end": 878.8, "text": " gets pulled down to zero so and we have this q factor we just which is a hyperparameter and"}, {"start": 878.8, "end": 886.3199999999999, "text": " it determines how important it is to to have these minimized down to zero so that's the how the"}, {"start": 886.32, "end": 894.08, "text": " the unsupervised method and learning procedure for graph sage works and they see here a generator"}, {"start": 894.08, "end": 899.44, "text": " from futures contained within a node's local neighborhood rather than training a unique"}, {"start": 899.44, "end": 905.7600000000001, "text": " embedding for each node so the difference between graph embedding graph embedding methods and graph"}, {"start": 905.7600000000001, "end": 912.4000000000001, "text": " sage is that we don't have a embedding table here so we are not training those fixed tables which"}, {"start": 912.4, "end": 919.6, "text": " are not prone to being later used in inductive setting we are training those wk matrices and"}, {"start": 919.6, "end": 924.56, "text": " we're training those aggregate functions which we'll see what exactly they are in graph sage in a"}, {"start": 924.56, "end": 930.0, "text": " minute graph sages can also be trained and in a supervised manner and for example if you have a"}, {"start": 930.0, "end": 936.3199999999999, "text": " classification task is just you just figure out the representations you do pretty much cross entropy"}, {"start": 936.32, "end": 944.08, "text": " and you train those wks and those aggregation functions so i won't get into much details there"}, {"start": 944.08, "end": 949.84, "text": " an important thing about graph sage is that once we have so if we have a node and we have some huge"}, {"start": 949.84, "end": 955.84, "text": " neighborhood maybe some of these networks have like maybe over a thousand neighborhood nodes what"}, {"start": 955.84, "end": 963.9200000000001, "text": " they do is they never in contrast to to get and in contrast to gcns they never sample they never"}, {"start": 963.92, "end": 971.12, "text": " try and aggregate all of the neighborhoods they just uh sub sample maybe they use in particular"}, {"start": 971.12, "end": 981.1999999999999, "text": " they used 25 on the first layer neighbors and they used 10 neighbors in the second layer of graph sage"}, {"start": 981.1999999999999, "end": 989.4399999999999, "text": " and what that means is in the first layer of graph sage you basically take only a uniformly sample"}, {"start": 989.44, "end": 996.08, "text": " and take 25 neighbors and you aggregate those representations only and in the second layer you'll"}, {"start": 996.08, "end": 1006.08, "text": " just take 10 and that means uh you're basically um that means that um this node here will basically"}, {"start": 1006.08, "end": 1018.6400000000001, "text": " potentially see up to 250 different uh nodes okay where was i here and they mentioned that here so"}, {"start": 1018.64, "end": 1023.92, "text": " using we're using overloaded definition we we define the neighborhood as a fixed size uniform"}, {"start": 1023.92, "end": 1031.28, "text": " draw from uh from the set of of of those edges so from all of these neighbors from the full set"}, {"start": 1031.28, "end": 1035.92, "text": " from the full neighborhood and we draw different uniform samples at each iteration so that means"}, {"start": 1036.96, "end": 1043.28, "text": " this node will have uh for every single layer of graph sage will have different neighborhoods picked"}, {"start": 1043.28, "end": 1050.6399999999999, "text": " up so it's stochastic and uh yeah they mentioned here also so they usually use the product should"}, {"start": 1050.6399999999999, "end": 1058.32, "text": " be less than 500 so to to just have this trade-off between the performance and between the uh"}, {"start": 1058.32, "end": 1065.6, "text": " efficiency of this algorithm so now let's jump to those aggregator architectures and they are using"}, {"start": 1066.3999999999999, "end": 1072.32, "text": " basically three different architectures so one is the mean aggregator so that means once you take"}, {"start": 1072.32, "end": 1082.3999999999999, "text": " so so so once you have once you sample some maybe 25 neighbors you just do element wise mean and then"}, {"start": 1082.3999999999999, "end": 1089.9199999999998, "text": " you can concatenate that representation with this nodes with this node feature vector and you do the"}, {"start": 1089.9199999999998, "end": 1097.04, "text": " forward forward uh feed forward layer right so that's that's one way how you can aggregate and"}, {"start": 1097.04, "end": 1104.08, "text": " that's the dumbest way pretty much uh the second way they propose is similar to gcm so they they"}, {"start": 1104.08, "end": 1110.56, "text": " ditch the the concatenation altogether and they just take they just take all of these so they take"}, {"start": 1110.56, "end": 1116.24, "text": " the neighbors the sample neighbors representations they take this representation and they do a mean"}, {"start": 1116.24, "end": 1123.36, "text": " over all of those they don't have any concatenation so that means this particular aggregation this this"}, {"start": 1123.36, "end": 1131.52, "text": " method they call it graph sage dash gcm because it's similar to gcn other than the the normalization"}, {"start": 1131.52, "end": 1136.8, "text": " constants are not the same and they mentioned that here so this differs from kipf kipf is the author"}, {"start": 1136.8, "end": 1143.6799999999998, "text": " of gcm exact equation by a minor normalization constant so if you remember gcn had this"}, {"start": 1145.04, "end": 1152.0, "text": " one over square root di dj which are basically degrees of of these nodes so this node has some"}, {"start": 1152.0, "end": 1157.92, "text": " degree and maybe one of these neighbors has some degree so once you combine those two you normalize"}, {"start": 1157.92, "end": 1164.88, "text": " them with this constant whereas here they don't do that so um yeah they mentioned here an important"}, {"start": 1164.88, "end": 1169.44, "text": " distinction between this convolutional aggregator and our other proposed aggregators is that it"}, {"start": 1169.44, "end": 1176.16, "text": " does not perform the concatenation operation in line five of algorithm one so that means here"}, {"start": 1176.16, "end": 1182.72, "text": " if you remember so they just uh don't do this concat part they just aggregate all of these together"}, {"start": 1183.52, "end": 1192.4, "text": " that's the difference whoops okay so that's the the mean aggregation function now they also tried"}, {"start": 1192.4, "end": 1198.4, "text": " and used lstms and now the problem with lstms is that they are inherently they are sequential"}, {"start": 1198.4, "end": 1207.2800000000002, "text": " and they they are they are ordered so that means basically they they had to find a way how to"}, {"start": 1207.8400000000001, "end": 1214.0, "text": " use lstm as a symmetric aggregator and what they did is they just applied random permutations"}, {"start": 1214.0, "end": 1219.2, "text": " to nodes neighbors so once you have the neighborhood you just do some random permutation"}, {"start": 1219.2, "end": 1224.8000000000002, "text": " and then you just find the aggregation doing the following so basically if you're familiar"}, {"start": 1224.8, "end": 1230.08, "text": " with lstms if you're not i'll just link a really good blog from christopher ola which would help"}, {"start": 1230.08, "end": 1236.24, "text": " you understand groose and lstms so basically it's initialized lstm is initialized with some random"}, {"start": 1237.04, "end": 1242.8, "text": " uh h0 state and you would input the first node representation i'll call it maybe"}, {"start": 1242.8, "end": 1254.24, "text": " v1 whatever and then you'd have some new state here and finally you'd output the second neighbor"}, {"start": 1254.24, "end": 1261.68, "text": " from the current permutation and anyways you you end up with a final aggregated representation"}, {"start": 1261.68, "end": 1270.1599999999999, "text": " that combined all of the previous uh node uh features and that's how the lstm aggregator works"}, {"start": 1270.16, "end": 1278.0800000000002, "text": " so those parameters inside the lstm would be trained together with those wk matrices"}, {"start": 1279.28, "end": 1286.48, "text": " and those are those are all of our learnable parameters finally they have this"}, {"start": 1286.48, "end": 1294.64, "text": " max pooling aggregator function and what they do here is they just take the neighborhood again"}, {"start": 1294.64, "end": 1302.16, "text": " so they take those representations they take some subset of those representations and they just apply"}, {"start": 1302.16, "end": 1309.3600000000001, "text": " a feed-forward neural network here and so once we have those transformed features they would just do"}, {"start": 1309.3600000000001, "end": 1318.48, "text": " an element-wise max pooling so basically this approach is inspired by this point nets paper"}, {"start": 1318.48, "end": 1325.76, "text": " and in a nutshell the point nets paper showed that this max pooling worked really well for them"}, {"start": 1325.76, "end": 1333.44, "text": " even better than doing mean pooling or doing attention based poolings so in a nutshell what"}, {"start": 1333.44, "end": 1343.1200000000001, "text": " this paper did it it works with point clouds and it starts with maybe endpoints and every single point"}, {"start": 1343.12, "end": 1349.9199999999998, "text": " has three features and those features are just the coordinates x y z and once you do some transforms"}, {"start": 1349.9199999999998, "end": 1357.1999999999998, "text": " and mlp transformations you end up with this n where n is number of points and you have 1024"}, {"start": 1357.1999999999998, "end": 1364.56, "text": " features and they just did so they just do element-wise max pooling so that means whatever"}, {"start": 1364.56, "end": 1371.04, "text": " the max element in this column is that will be put here and then you do the same for every single"}, {"start": 1371.04, "end": 1376.96, "text": " column and as i mentioned they they tried also doing the mean of this column and they tried doing"}, {"start": 1376.96, "end": 1382.8, "text": " the attention so the attention what the attention does is you basically find coefficients for all of"}, {"start": 1382.8, "end": 1391.04, "text": " these for all of these vectors rows so you have maybe alpha one for the first row you'll calculate"}, {"start": 1391.04, "end": 1397.12, "text": " all of those alphas you'll finally have alpha n and now what we would do is you would basically"}, {"start": 1397.12, "end": 1403.4399999999998, "text": " just multiply these these corresponding row vectors by alphas and that's how you'd aggregate"}, {"start": 1403.4399999999998, "end": 1409.76, "text": " and you'll get the global feature finally so that's pretty much everything you needed to know about"}, {"start": 1409.76, "end": 1415.9199999999998, "text": " graph sage aside from that detail about how do they do the mini batch part and i'll explain that"}, {"start": 1415.9199999999998, "end": 1422.4799999999998, "text": " in a couple minutes but first let's let's just go through the experiments and as i previously said"}, {"start": 1422.48, "end": 1429.68, "text": " the main like advantage of this paper is that they are really good at inductive setting"}, {"start": 1429.68, "end": 1436.72, "text": " and they use this ppi protein protein traction data set and there they have these entirely"}, {"start": 1436.72, "end": 1443.44, "text": " unseen graphs which is something that's really challenging for all of those graph method graph"}, {"start": 1443.44, "end": 1449.6, "text": " embedding methods and for all those previous methods that were inherently transductive"}, {"start": 1449.6, "end": 1456.24, "text": " um methods that were inherently transductive as i already mentioned they used sampling sizes of"}, {"start": 1456.24, "end": 1462.6399999999999, "text": " 25 neighbors in the first layer 10 in the second layer and one more detail is that in the multi"}, {"start": 1462.6399999999999, "end": 1471.6, "text": " graph setting they can apply deep walk since since because of this fact so the so in the"}, {"start": 1471.6, "end": 1476.32, "text": " multi graph setting we cannot apply deep walk since the embedding space is generated by running"}, {"start": 1476.32, "end": 1481.52, "text": " the deep walk algorithm on different disjoint graphs can be arbitrarily rotated with respect"}, {"start": 1481.52, "end": 1487.52, "text": " to each other and i'll touch on that a bit later but just for now just keep that in hand that"}, {"start": 1487.52, "end": 1492.08, "text": " those graph embedding methods are really hard to to to to generalize to inductive setting"}, {"start": 1493.12, "end": 1497.76, "text": " okay let's see the results they had four baselines the random classifier they just"}, {"start": 1497.76, "end": 1504.1599999999999, "text": " use the raw features so those are those i mentioned those maybe you have the abstract here you have"}, {"start": 1504.16, "end": 1509.6000000000001, "text": " uh degree information and that's your feature vector and here they just use those raw features"}, {"start": 1509.6000000000001, "end": 1515.44, "text": " and maybe just do some mlp on top of those and that's how they learn to classify without using"}, {"start": 1515.44, "end": 1521.52, "text": " any graph structure information whatsoever um on the other hand they had deep walk which was"}, {"start": 1521.8400000000001, "end": 1527.8400000000001, "text": " trained a bit smarter basically it encodes to this graph structure as well and here is a combination"}, {"start": 1527.84, "end": 1534.3999999999999, "text": " of doing both of those and then they have uh four different graph sage algorithms depending on the"}, {"start": 1534.3999999999999, "end": 1541.1999999999998, "text": " aggregation function they use so we have gcm we have mean lstm and pool and here we can see it"}, {"start": 1541.1999999999998, "end": 1547.6799999999998, "text": " pretty much steadily increases here and also they have the unsupervised trained graph sage and they"}, {"start": 1547.6799999999998, "end": 1552.8799999999999, "text": " have the supervised trained graph sage and you can also you can also expect that this will increase"}, {"start": 1552.88, "end": 1560.16, "text": " and it did so what we can see here is that basically yeah they got better results than all"}, {"start": 1560.16, "end": 1569.6000000000001, "text": " of those baselines and now there is the best aggregator functions seem to be lstm and pooling"}, {"start": 1570.16, "end": 1577.6000000000001, "text": " whereas pooling is a lot cheaper so they finally gave it a slight edge and they they said that the"}, {"start": 1577.6, "end": 1583.4399999999998, "text": " pooling had the best performance altogether it's probably the best overall because it has um that"}, {"start": 1583.4399999999998, "end": 1590.24, "text": " the best trade-off between the performance and the efficiency uh yeah here they just in this chart"}, {"start": 1590.24, "end": 1597.4399999999998, "text": " they just um showed that these graph embedding methods such as deep walk have a really high cost"}, {"start": 1597.4399999999998, "end": 1604.6399999999999, "text": " to do the inference on on the full test set because they have to recalculate to retrain uh those"}, {"start": 1604.64, "end": 1610.96, "text": " embeddings and that's really computationally costly and this is log scale here so that's"}, {"start": 1610.96, "end": 1617.76, "text": " thousand seconds that's much more than what graph sage takes they also have a small chart here where"}, {"start": 1617.76, "end": 1627.0400000000002, "text": " they plot how the performance so the f1 score and how the runtime uh increase as we increase the"}, {"start": 1627.04, "end": 1635.44, "text": " the sample size so if you remember we had we had 25 and we used 10 and here they just experimented"}, {"start": 1635.44, "end": 1642.48, "text": " they went all the way on up to 75 neighbors and we can see that the performance does increase as"}, {"start": 1642.48, "end": 1650.1599999999999, "text": " well as the runtime so uh empirically they just figured out that some smaller neighborhood sizes"}, {"start": 1650.16, "end": 1661.68, "text": " such as 25 and 10 are performing the best overall okay that was pretty much it for this main part"}, {"start": 1661.68, "end": 1669.8400000000001, "text": " of the paper uh yeah they mentioned here that so graph sage lstm is significantly slower than graph"}, {"start": 1669.8400000000001, "end": 1676.72, "text": " sage pool so approximately twice so perhaps giving the pooling based aggregator a slight edge overall"}, {"start": 1676.72, "end": 1684.08, "text": " um one more interesting theorem here and they have a whole proof for this thing that's like four pages"}, {"start": 1684.08, "end": 1690.4, "text": " long and i won't get into the mathematics in this video but i just want to briefly explain what they"}, {"start": 1690.4, "end": 1697.76, "text": " said here um what they say here is that graph sage even though it heavily relies on features and like"}, {"start": 1697.76, "end": 1703.3600000000001, "text": " aggregating those features and stuff it understands the graph structure really well so how they proved"}, {"start": 1703.36, "end": 1709.9199999999998, "text": " that is the following so they they showed that um the final representation so zvs if you remember"}, {"start": 1709.9199999999998, "end": 1718.32, "text": " from the pseudo algorithm uh can be made like arbitrarily close to these cvs which are basically"}, {"start": 1718.32, "end": 1725.12, "text": " cluster something called clustering coefficients and um and i'll now explain what those are"}, {"start": 1725.12, "end": 1732.1599999999999, "text": " so this equation again tells us that we can make the representations arbitrarily close so the"}, {"start": 1732.1599999999999, "end": 1738.56, "text": " whatever epsilon you give me how no matter how small like maybe you give me 0.01 i can make the"}, {"start": 1738.56, "end": 1745.6, "text": " zv close enough to the real um clustering coefficient so what's the clustering coefficient"}, {"start": 1745.6, "end": 1751.52, "text": " basically if you have some small graph here something like this"}, {"start": 1751.52, "end": 1760.0, "text": " and let's say this node one is connected to these three nodes basically um the clustering"}, {"start": 1760.0, "end": 1769.44, "text": " coefficient let's call it c for node one is if these are all connected together like this"}, {"start": 1770.0, "end": 1778.0, "text": " so they form a clique then the clustering coefficient equals one because the neighborhood"}, {"start": 1778.0, "end": 1783.12, "text": " nodes have the the highest connectivity pattern that's possible and that's a fully connected"}, {"start": 1783.12, "end": 1791.44, "text": " graph so if we were to just disconnect maybe these two edges would be left with this one"}, {"start": 1791.44, "end": 1800.48, "text": " and the clustering coefficient would drop to one third so basically what they state here is that"}, {"start": 1800.48, "end": 1808.08, "text": " the graph sage can learn all of these uh so this is like a structural information in the graph and"}, {"start": 1808.08, "end": 1815.04, "text": " they can learn it to an arbitrary precision okay uh let me wrap up this paper explaining the mini"}, {"start": 1815.04, "end": 1820.48, "text": " batch mini batch part and something related to graph embedding methods which will be interesting"}, {"start": 1821.84, "end": 1827.3600000000001, "text": " basically the main part the only difference is this so we won't be iterating over everything"}, {"start": 1827.36, "end": 1832.0, "text": " the only difference is this so we won't be iterating over every single node in the graph"}, {"start": 1832.0, "end": 1837.1999999999998, "text": " because the graph can be really huge uh like maybe a couple of billion nodes so basically"}, {"start": 1837.1999999999998, "end": 1844.0, "text": " they calculate these b sets so uh if we have let's assume we have two layers in graph sage"}, {"start": 1844.0, "end": 1852.7199999999998, "text": " that means they'll be calculating set b zero set b one and set b two and let me try and illustrate"}, {"start": 1852.72, "end": 1859.84, "text": " what what those are and how they look like so basically if we have some huge graph that has"}, {"start": 1859.84, "end": 1865.76, "text": " a couple of billion nodes maybe we're only interested in representations of a small subset"}, {"start": 1865.76, "end": 1873.2, "text": " of nodes which we'll call b2 now because of the way how graph sage works it just aggregates the"}, {"start": 1873.2, "end": 1878.88, "text": " neighborhood of every single node in a particular layer that means we'll need one hop neighborhood"}, {"start": 1878.88, "end": 1887.92, "text": " of the nodes in b2 and let's call that b1 and now because we have two layers we'll also need"}, {"start": 1887.92, "end": 1896.0, "text": " the one hop neighborhood of b1 which is basically b0 and that will be a superset of b1 which is"}, {"start": 1896.0, "end": 1905.1200000000001, "text": " itself a superset of b2 so this would this this is what the the algorithm would um put in these"}, {"start": 1905.12, "end": 1911.1999999999998, "text": " b sets so let me just zoom in a little bit on this one so we start with the so these are the target"}, {"start": 1911.1999999999998, "end": 1917.52, "text": " nodes that we want to calculate the representation for and so we initialize b2 with that one and then"}, {"start": 1917.52, "end": 1928.9599999999998, "text": " we start going towards one we we we initially initialized b1 b1 we initialize it with b2"}, {"start": 1928.96, "end": 1938.0, "text": " nodes and then we iterate over b2's nodes so over these nodes and we just add up we just do a union"}, {"start": 1938.0, "end": 1944.88, "text": " of all of the neighbors of all of the nodes in b2 so we'll go through nodes and maybe some of these"}, {"start": 1944.88, "end": 1953.1200000000001, "text": " nodes we'll have neighbors that are here and thus we'll we'll slowly build up b1 and then we'll"}, {"start": 1953.12, "end": 1960.8799999999999, "text": " slowly build up b0 and then the main loop what we do is we first initialize the initial representations"}, {"start": 1960.8799999999999, "end": 1969.52, "text": " with features feature vectors coming from b0 set so we'll have we'll only need to take we'll only"}, {"start": 1969.52, "end": 1976.4799999999998, "text": " need to think about b0 vectors we don't have to care about any of these nodes so we have we gain"}, {"start": 1976.48, "end": 1983.52, "text": " efficiency and so now the algorithm what it does we start with the with b1 so we start with this"}, {"start": 1983.52, "end": 1990.4, "text": " with these nodes so we iterate over those nodes and we do aggregations some of them will belong"}, {"start": 1990.4, "end": 1998.56, "text": " to b0 and hopefully luckily we already we have already have those in memory and we have those"}, {"start": 1998.56, "end": 2004.88, "text": " feature vectors so we can calculate all of the representations in b1 and once we have b1 in the"}, {"start": 2004.88, "end": 2011.8400000000001, "text": " next cycle once k gets to 2 we'll be iterating over nodes in b2 and we'll be building up"}, {"start": 2011.8400000000001, "end": 2016.72, "text": " representations and we'll luckily have all of these representations calculated from the last"}, {"start": 2016.72, "end": 2021.92, "text": " iteration so we can finally have all of the representations that we are interested in in"}, {"start": 2021.92, "end": 2029.92, "text": " b2 calculated and put into zv zus and that's pretty much it that's how the mini-batch algorithm"}, {"start": 2029.92, "end": 2034.5600000000002, "text": " works and hopefully that was clear enough if you have any questions please comment down in the"}, {"start": 2034.56, "end": 2041.52, "text": " comment section i'll try and answer all of them and yeah one interesting thing is they sample"}, {"start": 2041.52, "end": 2046.6399999999999, "text": " with replacement in cases where the sample size is larger than the nodes degree so maybe we have"}, {"start": 2046.6399999999999, "end": 2057.36, "text": " a node and it only has maybe three neighbors like this but if you remember s1 was 25 and s2 was 10"}, {"start": 2057.36, "end": 2066.32, "text": " which means we'll have to repeat some of these features before we call the aggregate function"}, {"start": 2066.32, "end": 2072.4, "text": " so maybe we'll have eight of these we'll have eight of these and we'll have nine of these and"}, {"start": 2072.4, "end": 2079.52, "text": " then we'll call the aggregate function so that means sampling with replacement so yeah that's"}, {"start": 2079.52, "end": 2085.84, "text": " a small detail and this is one more interesting detail and as you can see graph sage is all about"}, {"start": 2085.84, "end": 2093.6000000000004, "text": " these small details which are making the implementation a lot more efficient and it can later be used"}, {"start": 2094.56, "end": 2101.76, "text": " on huge graphs and here what they say is basically they do a pre-processing step on these huge graphs"}, {"start": 2101.76, "end": 2111.1200000000003, "text": " and in case some of the nodes has maybe thousand edges they'll just sub sample up to 128 of them"}, {"start": 2111.12, "end": 2121.2, "text": " so every single node will have its degree less than or equal to 128 and they say here due to"}, {"start": 2121.2, "end": 2128.24, "text": " heavy tailed nature of degree distributions we down sample the edges in all graphs before feeding"}, {"start": 2128.24, "end": 2133.2, "text": " them into the graph sage algorithm in particular we sub sample edges so that no node has a degree"}, {"start": 2133.2, "end": 2140.16, "text": " larger than 128 the final thing i want to mention is the part that i mentioned in the beginning"}, {"start": 2140.16, "end": 2147.2, "text": " and that's these what's the problem once you're once you're dealing with these embedding tables"}, {"start": 2147.2, "end": 2155.3599999999997, "text": " so basically what you're doing by doing those trying to make some vectors similar and some"}, {"start": 2155.3599999999997, "end": 2159.8399999999997, "text": " dissimilar you're basically doing implicit factorization so basically you're trying to"}, {"start": 2159.8399999999997, "end": 2168.56, "text": " calculate that z matrix and this is number of nodes this is the hidden dimension d"}, {"start": 2168.56, "end": 2178.32, "text": " and you're if you do transpose this z matrix into zt and you just do multiplication what you end up"}, {"start": 2178.32, "end": 2187.92, "text": " is this matrix m which basically contains all of these similarities between vectors so you have"}, {"start": 2187.92, "end": 2194.32, "text": " you have a you have a how similar vector one is with vector one and you'll have how similar vector"}, {"start": 2194.32, "end": 2203.36, "text": " one is with vector two etc so you have a huge m by n matrix which basically tells you how similar"}, {"start": 2203.36, "end": 2212.56, "text": " or dissimilar those embedding feature vectors are and you're basically by doing those random walks"}, {"start": 2212.56, "end": 2217.2000000000003, "text": " and training those graph embedding methods you're you're implicitly trying to find this"}, {"start": 2217.2, "end": 2226.0, "text": " you find this implicit m matrix which contains the random walk statistics you know the problem is"}, {"start": 2226.0, "end": 2235.4399999999996, "text": " that as you can see here you can basically have a whole family of these z matrices which basically"}, {"start": 2235.4399999999996, "end": 2244.7999999999997, "text": " add up to m and that means those those embedding vectors can rotate they can the whole space can"}, {"start": 2244.8, "end": 2251.28, "text": " rotate and you'd still have the same matrix m so now what why is that the problem so the problem"}, {"start": 2251.28, "end": 2258.0, "text": " is once you try to add new nodes to your graph as we saw in the beginning so basically if you try and"}, {"start": 2258.0, "end": 2265.76, "text": " you have graph g1 you have embedding table for g1 and you try to add maybe two new nodes and what"}, {"start": 2265.76, "end": 2273.52, "text": " happens is you'll have to update the table and if you just do the following if you just if you maybe"}, {"start": 2273.52, "end": 2279.6, "text": " so basically you had this table previously and now you're trying to add two new vectors but the"}, {"start": 2279.6, "end": 2287.2, "text": " thing is you train a classifier for those vectors here so you have some some classification had here"}, {"start": 2288.24, "end": 2294.96, "text": " which was trained for those and once you add up these two new random vectors and if you try to"}, {"start": 2295.68, "end": 2303.04, "text": " retrain everything then these won't be working correctly with this classifier anymore"}, {"start": 2303.04, "end": 2310.16, "text": " and you'll mess up everything you you all of the training will be pretty much in vain and so"}, {"start": 2310.16, "end": 2315.92, "text": " yeah they mentioned here moreover if we update all embeddings during training not just for the new"}, {"start": 2315.92, "end": 2322.24, "text": " nodes as suggested by deep walk then the embedding space can arbitrarily rotate compared to the"}, {"start": 2322.24, "end": 2328.24, "text": " embedding space that we train our classifier on which only further exasperates the problem"}, {"start": 2328.24, "end": 2334.16, "text": " so basically once you add again re-dating once you add the nodes if you just do this naive"}, {"start": 2334.16, "end": 2339.68, "text": " retraining you'll mess up the classifier because all of these will start rotating because as we"}, {"start": 2339.68, "end": 2348.16, "text": " already saw all of those families are still add up to this matrix m and they suggested here a couple"}, {"start": 2348.16, "end": 2352.8799999999997, "text": " of reasonable approaches so some reasonable approaches to alleviate this issue of statistical"}, {"start": 2352.88, "end": 2358.1600000000003, "text": " drift are to not update the already trained embeddings when optimizing the embeddings for"}, {"start": 2358.1600000000003, "end": 2364.48, "text": " new test nodes so that means we pretty much freeze up all of these so we freeze them up we don't"}, {"start": 2364.48, "end": 2372.2400000000002, "text": " change those and second to only keep existing nodes as context nodes in the sample random box"}, {"start": 2372.2400000000002, "end": 2376.96, "text": " i.e. to ensure that every dot product in the skip gram objective is a product of an already"}, {"start": 2376.96, "end": 2386.88, "text": " trained node and a new test node so that means once you're doing those random walks you only take"}, {"start": 2386.88, "end": 2395.12, "text": " context nodes from these that are already trained so you you can take for example if this is a new"}, {"start": 2395.12, "end": 2402.64, "text": " node let's call it node number three and this is also a new node and even though this node three"}, {"start": 2402.64, "end": 2409.3599999999997, "text": " is on this random walk because it's a new node we won't be using it as a context node if you're"}, {"start": 2409.3599999999997, "end": 2414.72, "text": " familiar with how the word2vec and these graph embedding methods work you'll understand what"}, {"start": 2414.72, "end": 2421.44, "text": " i'm talking about and so basically the second approach the the the second suggestion they have"}, {"start": 2421.44, "end": 2428.24, "text": " is only use nodes that are already trained as the context there was a lot of information packed in"}, {"start": 2428.24, "end": 2435.2799999999997, "text": " this video i think it's worth just comparing graph sage with get and with gcn because all of the"}, {"start": 2435.2799999999997, "end": 2441.8399999999997, "text": " three are spatial methods and get and gcn are the most cited papers in the gnn literature so"}, {"start": 2442.24, "end": 2447.6, "text": " the structure is really similar if you take a look at it so we have a we have a node and we have a"}, {"start": 2447.6, "end": 2456.16, "text": " neighborhood and what gcn and what get do is the following they just aggregate all of the nodes"}, {"start": 2456.16, "end": 2463.6, "text": " aggregate all of the node features and before before they add them up they just scale them with"}, {"start": 2463.6, "end": 2473.2799999999997, "text": " a certain coefficients so basically gcn takes this one over square root di times tj which are the"}, {"start": 2473.2799999999997, "end": 2480.16, "text": " degrees of those nodes and so we we take both the neighborhood features as well as the current"}, {"start": 2480.16, "end": 2490.16, "text": " nodes feature and we just scale them with this that's gcm and what get does instead it just"}, {"start": 2490.16, "end": 2495.92, "text": " computes dynamically these alpha coefficients which are just attention coefficients and then"}, {"start": 2495.92, "end": 2506.64, "text": " multiplies those nodes with these coefficients that's get once you multiply them you just add"}, {"start": 2506.64, "end": 2513.68, "text": " them up and then you do a simple projection followed by a simple non-linearity such as"}, {"start": 2513.68, "end": 2523.2799999999997, "text": " relu so you have this let's call it aggregated features whatever and then we just take those we"}, {"start": 2523.2799999999997, "end": 2533.12, "text": " project them and we do non-linearity such as relu on the other side what graph sage does is it also it"}, {"start": 2533.12, "end": 2538.4, "text": " it doesn't take the full neighborhood it takes a sub sample uniform some sample of the neighborhood"}, {"start": 2539.3599999999997, "end": 2548.24, "text": " and it again aggregates those features in bunch of different ways some of them you saw like mean"}, {"start": 2548.24, "end": 2554.72, "text": " you can do lstm aggregation whatever and finally you again do a projection and followed by a"}, {"start": 2554.72, "end": 2560.88, "text": " non-linearity so the pattern is really similar graph sage is a bit more efficient because it's"}, {"start": 2560.88, "end": 2566.96, "text": " sub samples the neighborhood and it experimented with different aggregation function and also some"}, {"start": 2566.96, "end": 2572.88, "text": " of the other details you heard during this video so that was it if you found this video useful i'd"}, {"start": 2572.88, "end": 2577.84, "text": " really appreciate you leaving some feedback in the form of a comment in the comment section that will"}, {"start": 2577.84, "end": 2583.52, "text": " help me like twofold first thing is i'll get much better by reading your feedback what i'm doing"}, {"start": 2583.52, "end": 2589.12, "text": " right what i'm doing wrong and secondly you'll boost these videos like because of the the way"}, {"start": 2589.12, "end": 2594.96, "text": " youtube algorithm functions so anyways if you found this video useful consider subscribing"}, {"start": 2594.96, "end": 2600.72, "text": " and consider hitting the bell icon if you want to get notified for every single video i make"}, {"start": 2600.72, "end": 2619.6, "text": " and yep until next time keep learning deep"}]