Graph Attention Network Project Walkthrough
❤️ Become The AI Epiphany Patreon ❤️ ► https://www.patreon.com/theaiepiphany
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬

In this video, I walk you through my recently open-source GAT project. I focus on 2 potential pain points in the implementation and I also highlight some of my previous projects you could find interesting.

You'll learn about:
✔️ Cora dataset
✔️ Highly-optimized GAT implementation
✔️ Other exciting DL projects you could play with

▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 
✅ My GAT project: https://github.com/gordicaleksa/pytorch-GAT
✅ Naive neural style transfer for videos: https://github.com/gordicaleksa/pytorch-naive-video-neural-style-transfer
✅ Planetoid: https://github.com/kimiyoung/planetoid 
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 

⌚️ Timetable: 
00:00 Intro to GAT project
00:35 My other deep learning projects
04:00 README walkthrough
07:35 Node degree statistics
10:10 Entropy histograms
12:05 t-SNE plots
12:50 Graph drawing layout
14:00 Jupyter walkthrough
15:22 Understanding Cora dataset
18:19 Feature vectors and labels
20:00 Building the edge index
22:40 Toy example (understanding the implementation)
29:00 Lifting
32:50 Neighborhood aware softmax and aggregate
38:18 Outro, exciting deep learning projects

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

#gat #graphattentionnetwork #project
 What's up folks? So for those of you who don't know, four days ago I open sourced a brand new project. It's the implementation of the Graph Attention Network. So in this video I thought doing a quick walkthrough and just going to read me and potentially try and explain the potential pain points in the Jupyter notebook. Mainly the implementation itself, like the core part of how the get method works. But before that, I just want to remind you that aside from this project, I've got a lot more interesting projects on my GitHub. So I've been working and implementing these projects for at least a year. So aside from this one, which is super popular, I've open sourced this four days ago and it's got almost 600 stars, which is better than all of my previous projects. Like the best one was Transformer, which had around 400 stars. And I'm really glad I don't treat these as a vanity metric. I'm just glad that I see that the community is actually using the stuff I produce. So that makes me happy and makes me want to create these even more. So as I said, aside from the PyTorch get, which I'll cover in this video, I had some really interesting projects, especially if you're like a newcomer to deep learning field. Like you should check out this Deep Dream project. It's got really like just look at this imagery. It's so so freaking exciting and looks really nice, if nothing else. But you'll learn a lot by doing these projects. And I'll always recommend something like this to a beginner. So if you're a beginner, you should consider doing something like this, something like Deep Dream as your first or like second project, whatever. And yeah, it's just so awesome. And I think the reason it's not as popular, so it's only it only has like 56 stars, is I haven't added the Jupyter notebook yet. And I think I'll just invest like a couple of days in a couple in a couple of months to just add the Jupyter notebooks to all of the projects that don't have it. So that will hopefully make it even more accessible than than the current state of the project. OK, aside from Deep Dream, you should check out the Neural Style Transfer project. That's how I started the whole this whole YouTube channel. I started with the Neural Style Transfer series, but it wasn't as popular, so it kind of dumped it and started doing other things. But I really enjoyed creating this project. And just again, just look at this like like if somebody told me like a couple of years ago that like a neural network create like a piece of art like this, I'd be really surprised. It's amazing. And the reason like the pure fact that it's so visual helps you maybe at least help me better engage with this project and made it so much interesting than just doing something that you can. It's not as palpable as this thing. And also I've got implementation of a couple of different GAN architectures like I implemented the original GAN architecture. And you can see here the generator slowly learns how to generate MNIST digits. And finally, the outputs are almost indistinguishable from the inputs. But this is a simple data set, so it's not hard to to learn that. And I also had the conditional GAN implementation and DC GAN where I'm just using this Celibate data set to generate faces. So I encourage you to check out these projects and play with them. I hate seeing them not being as used as much as as the current as the GAT project, even though they're really cool and an awesome learning resource. And I'll try and add the Jupyter really soon. With that out of the way, let me jump back to the topic of this video. And that's a graph attention network. I just want to quickly walk you through the readme and show you what you can see here. So the first thing, just go and click click around these links. There are many awesome applications I've linked here. Those are mostly short blogs which you can just read. And if you're not familiar with GNNs, I strongly encourage you to just go and explore and read about all of the awesome applications that GNNs not just get like graph neural networks in general enable. OK, so in this schematic, what you can see is the like a schematic representation of GAT where basically you can see the H1 area, which is the feature vector of this node one. And the edges just they just represent the other feature vectors that will get used to update this node's feature vector. And the differently colored and these squiggly lines just represent multiple attention heads. And in this image, it seems like this GAT has three attention heads. And after you just kind of accumulate and you weigh the feature vectors and you aggregate them, you get the updated version H1 prime. And again, I encourage you if you have if you're not familiar with GAT, go and watch my video on graph attention network. I got it covered thoroughly. So that's pretty much a prerequisite to understand this project. And yet so I encourage you go check it out. Let me continue here. So for the time being, I've only got a core citation network data set covered. So that's the transductive approach. And I'll be I'll be probably adding PPI or the protein protein interaction data set really soon, which is the inductive setup, which will make this project even more useful for you. So what you can see here is just the visualization of Cora. And what I did here is that the size of the node so Cora has two thousand seven hundred eight nodes. And what I did here to plot it is the following. Basically, the size of the node corresponds to the degree of that particular node where the degree is the number of edges. So the bigger the node, the more the edges. And you can see there are like a couple of nodes that are really big and most of them are really small. And we'll see that in a minute. Like some nicer plots that will explain that. Second thing, the colors are the classes. So Cora has got seven classes. And that's why we have seven colors in this in this chart. And finally, the edges. So the thickness of the edge is pretty much correlates with the something called edge between us. Basically, you want to take a particular edge and you want to find the number of geodesics, i.e. the the number of shortest paths that go through that particular edge. So you have all of those nodes in the in the in the graph. Right. And for every single pair of those nodes, you just go through the command control space and you find all the pairs and you ask the question, what's the shortest path between this node and this node? And while looking at a particular edge, you want to know how many of those shortest paths go through this through that edge. And that kind of quantifies the popularity of that edge. And so the thicker the edge, the more shortest paths go through it. Hopefully, that was clear enough. So that's the chart you can see here. And going down here. So in this chart, we can see is the like the node degree of every single node in core. So we've got two thousand seven hundred eight nodes on the x axis is the node ID on the y axis. We get the edge count for a particular node. And we can see there is one node that has one hundred sixty nine like edges. And the rest are have much, much, much, much less edges. And the final this bottom plot shows really nicely that the accumulation happens around two to five edges. So most of the nodes in Cora have only two to five edges. And this plot shows it really nicely. So it goes up until hundred sixty nine. That's the this this node and that's the big green node in this chart above. OK, that's that was Cora. We showed I showed you the schematic of GATT. And finally, once you once you train the GATT model and hopefully understand how GATT works, basically, you know that it tries to to to assign attention coefficient to every single of its neighbor in order to aggregate those and update the representation. So what we see here is the the the edges, the thickness of the edge is proportional to the attention coefficient. And because we can see that every single edge here is of the same thickness, we can deduce that the GATT model on Cora data set learns to to just output constant attention pattern, which is not as interesting. And the reason is because this data is pretty simple for forget its homophilic, meaning that similar nodes cluster together. You can see here by just looking at the color. So the blue node here, you can see that mostly the blue nodes connect to the blue node. And that's something known as the homophilic property of of of of graphs. And yeah, that's that's the reason why why GATT learns these boring constant attention patterns. But yeah, in this node here is one of the nodes with the most edges. Most of you'll see nodes like this. So as I said, two to five edges is the common number. So this one is a common representative you'll find in Cora. And again, the edges are the same thickness, meaning constant attention. There is one more interesting way to to understand the attention patterns that GATT is learning. And that's this entropy histograms method. And what we do here basically is the following. So because all of these sum up to one, because we applied the softmax while producing these attention coefficients, we can just treat all of these neighborhoods as a simple as simple distributions. And because you have a probability distribution, you can calculate the entropy. And now the point I want to want to stress here is that you don't need to know a lot about information theory. Actually, you don't need to know anything. The whole point with entropy histograms is the following. So you take the ideal, the hypothetical GATT model on your particular data set in Cora here, and you make it have like a constant attention, like a perfectly constant attention. That means you always have the uniform distributions. And what you do is you just plot, you just calculate the entropies, you create a histogram. And that's the orange histogram in this chart. And then you take your GATT trained, your trained GATT model, and you do the same procedure. And if the histograms match with that hypothetical GATT, that means your GATT has learned constant attention. And you can see here basically that the orange and the blue histograms totally match with each other, which means our GATT learned to produce constant attention patterns. And yeah, that's just another way to look at this. And if we had some different data set like PPI, which I'll soon add, the histograms would be like, would have much less matching than on this chart. So yeah, that's a second really nice visualization that helps you understand the attention patterns that GATT is learning. Okay. Having said that, in the paper you could see the t-SNE plot. I did the same thing here. Basically, you take the final from the final layer, you take the embeddings, and you use t-SNE, project them into 2D, and you get this nice chart here showing us basically that GATT has learned to cluster nodes of the same class in the same part of the 2D space, which is awesome, which means we can easily train a classifier to kind of just classify these edges into one of seven classes. Okay. That was pretty much it. I've got the setup usage and everything here. You can just go and read through the README, and you'll hopefully have no problems starting this project. One more thing I want to note here is that you'll usually see these circular patterns. So the thing is the graph drawing is a subfield for itself, like something similar to tokenizers if you're familiar with transformers. It's something you just take for granted, but it's a field for itself. So I usually use this Rhine Gold Tilford circular layout, and you'll get charts like this one, but you can use some other techniques and layouts like Kamadi Kawai, this one, and you'll get charts like this one. So this one, the Rhine Gold Tilford, is really adequate for true-like graphs, and because this is basically MRE3, I've used this layout, and it gives really nice results. But just be aware there are multiple layouts, and I've been using iGraph plotting package, so you can just go explore some other layouts, but for this particular problem, I think this does the job. Okay. That was everything I wanted to cover in the README. Now I'll jump into the Jupyter and OneNote and try and explain a couple of potential pain points. And welcome to the Jupyter Notebook. So I'll give you time to go through the Jupyter Notebook by yourself, by your own pace. What I want to do in this video is just kind of focus on two specific pain points, potential pain points for you, and just focus on that one. So first things first is data. What I did here is you'll usually see, if you take a look at the official GATT implementation or some re-implementations like PyGATT project, you'll see a bunch of files which actually date back from the planetoid paper. And the thing is, like most of those implementations, just copy-pasted the same snippets for processing the Quora. And so I just decided to do the processing and just save those into files so that you can just import the node features like this, the node labels like this, and finally the structure of the graph, the edges and connections through one line of code. Hopefully this will make it a bit easier for you to just not have to look through some pre-processing stuff. Let me quickly just explain how these structures look like, and then I'll jump into explaining how the GATT method itself works. Okay, so node features. So those of you who watched my previous video on GATT, this will probably be familiar, but let me just recap here because I'll be using these structures later when explaining the implementation of the GATT method itself. So first things first, node features. It's a matrix like this. We basically, so Quora has 2,708 nodes, and I've been working so much with Quora that I know every single number on top of my head. And the second dimension is 1,433. Now that may seem like an arbitrary number, and it's actually not. I'll just explain how they got that number. So yeah, so that's the feature vectors for every single node. And so how they got this number is the following. So they took all of the research papers. They just created a simple histogram of words, meaning on the x-axis you have a word, on the y-axis you have the frequency of that word throughout all of those research papers. And now what they did is the following. They just created a cutoff frequency, like maybe 10, which means just disregard the words that have a frequency less than 10 across all documents, and just keep all of the rest, and they ended up with 1,433 words. So now how you create a feature vector for a specific research paper, which is a node in Quora, right? You do the following. You just go through the words of the research paper, and you see if some of the words from this vocabulary we just created is present in that research paper. So maybe if we had attention is all you need paper, and in the vocab we had the attention word, we put one where that field is. So basically, let me just draw it here. If this is the feature vector, and this particular slot, so this is again 1,433, and if this one corresponds to attention, you take a specific research paper and you ask, does it have the word attention present inside? If it does, we put a 1, and by doing that you create a feature vector, and it will look something like this, and it will mostly be sparse, so most of these will be zeros, and I'll show you how it actually looks like in a second, but let's take this for a moment, and later you'll see in the code the feature normalization part, and what it does, it's a really simple thing. You just sum up all of these ones, and you just divide all of the numbers by the sum, and we'll end up with having 1 over 2 here, and 1 over 2 here, because we only had two ones in this particular example. So in a more general case, you'll just have 1 over n, where n is the number of ones in your feature vector. So that's the normalization part, and now let me just show you how the feature vectors look like. Okay, so I just opened up the PyGad project, and you can see here on the screen the feature vectors for every single node in Quora, and most of the numbers are zeros. You see a couple of ones here, but it's pretty sparse representation. And finally, the labels, I mentioned seven labels, so they're genetic algorithms, probabilistic methods, case-based theory, reinforcement learning, etc. So what I did is I just assigned a number 0 through 6 to all of these strings, and we'll be using that as labels. So that leads me to the second structure, and that's the node labels, and the shape is pretty straightforward. So basically we have, again, 2,708 nodes here, and we only have one here, because we have a single class, right? So these numbers will be 0 through 6, maybe this one will be 5, so this node with this feature vector will have class 5. So that's the node labels structure. And finally, we've got this adjacency list dictionary, which just contains the connections, the edges in the Quora, and the structure, it's a simple dictionary, meaning the keys are node IDs, maybe 0, and 0 will have associated with it all of the edges, maybe something like, I don't know, 1, 2, 3, 25, whatever. And those are the nodes that 0 connects to. And finally, once we have this, the third most important structure that you'll see used throughout the code is something called the edge index. And what edge index is, it's a simple way to, it's a dense way to represent your connectivity in your graph. So I just copy-pasted that snippet that creates the edge index, and you can see it uses this structure, the adjacency list we have here. It just needs a number of nodes, and we'll be adding self-edges, and we'll see that in a moment. So what happens is the following. I just iterate through this dictionary object, and I create the edge index doing the following thing. So, by the way, the shape is just 2, comma, E, where E is, I think, 13,264 edges. And how we create that is really simple. So we have 0 and the corresponding list of target nodes here, so I'll just go through the list, and I'll see 0, 1, okay. We add 0, 1 topple to the edge. Then we add 0, 2 topple to the edge. Finally, we add 0, 3, 0, blah, blah, blah, 0, 25. And after I do that for every single node, so 0, 25, I don't know how to write today, and I'll just iterate through all of the keys, and finally, I'll just add the self-edges. So that means after I finish all of this procedure, going through this dictionary, I'll just add 0, 0, meaning node 0 connects to itself, and the same goes for every single node up until 2,707. So that's the edge index, and you can see the shape is just a bunch of these topples, and there are this many of these topples, and that's the edge index structure. And hopefully, this makes it easier for you to now tackle the Jupyter notebook yourself. I'll just cover the... I'll try and cover the method. It's complicated. I'll use a dumb example, and we'll see if it works. Going back to the Jupyter notebook, and just scrolling to the main part, to the meat of this project, so we've got some visualizations. We saw this in the readme. You'll be able to just generate those yourself, just go through the Jupyter, and yeah, this is the main part. So we have the high-level class, and we have the actual implementation. And so the only part that will probably create you some problems to understand how it works is a couple of lines of code, so namely this. So from this huge, huge, huge, huge Jupyter notebook, the only part that's actually maybe hard to understand is this one. And so I'll try and now explain how this part works. Maybe you should first just go yourself through this code, and then continue watching this video. Okay, I'll try and use a toy example here to explain how the implementation works. So just a quick recap. Let me use this as a running example. Three nodes, just two edges here, and also self-connections are here. And now I'll just add some IDs here. So this is node 0, this is node 1, and this is node 2. So how GAT works is the following. So we have associated a feature vector with every single node, and what we do is we basically need to find the attention coefficient for this feature vector, and for this one, and for this one, in order to update the feature vector, this feature vector, okay? And so we first project those feature vectors into some smaller subspace, and then how we find those attentions is the following. We just concatenate this representation with this one. We apply something called like a scoring function, and that one is basically densely connected like a linear layer here, and that will give us a score for this particular edge. We do the same thing here, we do the same thing for the self-edge, and which means for the self-edge we'll have this same vector duplicated two times, and we just apply the same scoring function, so these weights here. Once we have the scores, we apply the softmax, that will make them sum up to 1, and then we just multiply this particular vector with that specific attention coefficient, we'll multiply this one with its attention coefficient, and the same goes for this vector, and we'll end up with a new representation, and that's the updated representation. I missed some details like Rayleigh uses, blah blah blah, but this is the core concept, so you want to find those attention coefficients, you want to multiply the projected vectors using those coefficients, and you want to aggregate all of those using the sum into a new updated representation. So hopefully that kind of just refreshes your mind on how GAT works. Okay, let's build up the structures we'll need in order to go through this example. So, first assumption is I only have a single attention head, I'll ditch the eight attention heads that we have in the actual implementation, I'll just work with a single attention head, otherwise it gets really hard to explain it, but it's the same thing, we just duplicate whatever I say here, eight times, that's it. They are totally independent, so it makes sense to reduce this problem to a single attention head. So, first thing we have node vectors, so that means we have three here because we have three nodes, and these are 1,433. The second thing we have is the edge index, and let's see how the edge index looks like. So let's first see which nodes connect to zero. So, one connects to zero, two connects to zero, and zero connects to zero. Then let's see which nodes connect to one. So, zero connects to one, and one connects to one. And finally, which nodes connect to two, and that's zero connects to two, and to itself connects to itself, right? So this is the edge index structure for this particular graph. Okay? Once we have that, let's see how the method works. So what I do is, the first thing, you have this projection layer, and you just project this thing into some smaller subspace. So this gets projected into eight dimensional vectors. So we'll have three by eight. And if we had multiple attention heads, the only thing that would be different, you would have eight by eight independent columns here, and that's the only difference. And the actual implementation detail is that you'll project this vector into 64 dimensional vector, and then you just apply this view function, which basically just doesn't change anything. It changes like the stride, a couple of parameters in the matrix itself, but it doesn't change the underlying memory layout. So that's the important thing to notice. Okay, so once we have this projected thing, what do we do? We do the following. We need to first lift these. So we first need to calculate these scores for every single edge, because that's how get works. It requires these scores, and then transforms them into attention coefficients, and let's see how we actually do it through code. So after we project them, we do the following. We apply these left and right scoring functions. And let me just explain that, why that works. So basically, you can treat this as the left side and the right side, and you just apply, so let me draw it again. So instead of holistically applying, concatenating the feature vectors, and then applying a single scoring function, you can do the following. You can take this feature vector, put it here, and apply a single, the source, I called it the source scoring function, and you find the score here. And you take the second feature vector, and you apply a separate scoring function, the target scoring function, and you get the score. And if you just sum them up, that's exactly the same result as by just doing a single scoring function on the concatenated version of these vectors, okay? Hopefully that makes sense. So that's the main potential pain point for you. So it's conceptually, it's a bit different, but like it's the same thing at the end. It's semantically the same thing, okay? So what we'll do here is we'll take these projected vectors, we'll apply the left and the right scoring function, which will, so we'll end up with three by one. So we have scores, so these are the source scores, and these are the target scores. Okay. So that's again three by one. And now there is this thing called lifting in the code. So what lifting does is it uses this edge index structure to just copy these projected vectors and these source and target scores. So what I mean by that is the following. So we'll take the source scores, and we'll take the source column. So this is the source column, and this is the target column. Remember, this means one, the source node points to zero, the target node. So that's this directed edge. And because we have both, we just read the core as undirected graph. So we'll just do the following. So one means we take score one and we copy it here. Let me just draw it like this. So we'll have, so because this has how many edges, like seven. So this one will have seven edges here and one after being lifted. So we'll take one, we copy score one here. We see two, we copy score two here. We see zero, we copy score zero here, et cetera. And that's how we lift up the source scores. We do the same thing for the target scores, but we just use the target column of the index this time. And the same procedure goes. So we'll have zero, so we'll copy zero here, blah, blah, blah. And we form the lifted versions of these structures. And finally, we do the same thing for this projected vectors and we use the source index. And it will hopefully make sense why we are using the source index here. But like for the time being, let me just copy it here. So we'll end up with seven, seven rows and the same concept goes. So the same idea again, we just copy. So we have one, we copy the projected vector one here. We have two, we copy the projected vector two here. And so on and so on. And that's how we form these lifted versions. So now for the fun part. So what do we do now? So we take and we just add up these scores. And we end up with something that calls scores per edge. And after applying a ReLU, we just apply a ReLU, Leaky ReLU, and we get the final scores per edge. So why do we do the lifting? So the idea is really simple, because we have score for node one here and we have score for node zero here. What we effectively did by summing up these two and putting them here is we calculated the score for this particular edge. And that's what we want, because we need scores, we need those scores in order to calculate the attention coefficients and we need those in order to create the updated version of the feature vector. So again, by doing this simple lifting, we calculated the scores only for those edges that we care about. So if this was a fully connected graph, we'd have much more edges and we don't need to calculate the scores for the edges that don't exist. And that's, so if you take a look at implementation one and two of my project, you'll see exactly that. I'm calculating the scores for every single possible edge and then doing some smart masking, we just finally find the attention coefficients only for the edges. But it's far less efficient than this implementation, even though this one is conceptually, as you can see, a bit harder to explain and to understand. But it's super simple, like once you invest a little bit of time, you'll be able to understand everything. OK, so we've got the scores per edge. How do we convert these scores per edge into those attention coefficients we need? Well, the following we do the following. We basically again take the target column of the edge index and we do something called a neighborhood aware softmax. And that's something I just dubbed it like that. That's not official literature term. That's something just I dubbed it like that. That's how I name my variables. And what happens is the following. So we take the edge index and we can see there are zeros here. That means we want to make sure that these scores here sum up to one. That's the neighborhood aware portion. So using the edge index, you know, you know exactly which parts of this scores per edge structure need to sum up to one. So because these correspond to node zero, we want them. We want to we want to make sure that they sum up to one. And then we have ones here. So that means we want to make sure that this chunk here sums up to one. And finally, because we have twos here, we want to make sure that these sum up to one. So how we do that is the following. We just we first raise this structure. We just do exponential of this structure, because if you remember like the softmax, we got e to the i. And then you've got sums of e to the like these are scores. And basically, this is some particular score for node i. And this is for the other neighbors. And because of that, because we have that exponential, we want to exponentiate. That's even a word, this structure. So we have the same dimensions. These are now just exponents. So this is seven. This is one. In general, this will be e. So for Quora, this will be, if we remember, 13,264, whatever. And now we want to make sure that the summations go over these neighborhoods I just defined. So that means in the code, you'll see something called scatter add. And what scatter add does is the following. It will just sum up these. And so we'll get a smaller structure. So this thing will actually end up being three. Or in general, this will be the number of nodes in your graph. And once we do that, we just want to lift it up again. And you'll see in a moment why. Hopefully you already understand. So we'll lift it up again by copying the lifting up using the target portion of the edge index. And once we have these numbers, now it's pretty simple. We just divide these by these, because these here are the same numbers, and they are just the sum of these three elements. So once we divide this, that's basically doing this portion. And we end up having the attention coefficients. So after we do division, after we divide, let me denote it like this, this vector with this one, we end up with the attention coefficients. And now we're really close. Now it's really simple. Now we do the following. We just take these attention coefficients and we multiply them with this. And if you remember, we use the source portion of the edge index to project, to lift these up. And now we just multiply these, and that's the weighted part of the... And now we just need to aggregate all of those, and that's the get method, right? So after we multiply this coefficient to this projected vector and to this and to this, we'll get what we semantically did for get, right? And hopefully now we can see why we use the source portion, the source column of the edge index to lift the projected vectors. Because this now is node 1 representation, this is node 2 representation, or the projected feature vector. And once we multiply it with this coefficient, we basically get what we want, and that's we accumulate, we aggregate. So this is... so 1, that's this one, 2, that's this one, and we just multiply with the attention coefficients and we get the weighted feature vectors. And now we just want to do the aggregation. How do we do the aggregation? So after multiplying these two structures, we'll end up with the weighted structure, again 7 and 8 here, because remember the projected vectors had dimension 8. And finally, again, simple scatter add using the target index will make sure that we sum up the right nodes, the right nodes, yep, and we'll finally end up with 3 by 8. And that's... those are the new representations that we wanted. Again, we use the target column of the edge index to do the scatter add, and that will make sure that we... so we have zeros here, that means these feature vectors connect to zero, and we'll just scatter add them, and that's the final representation here. Hopefully this made it a bit easier for you to understand it. I don't know if I explained it perfectly, I tried my best. I just want to wrap it up, reminding you again to just check out other projects, and this one got un-proportionally more popular than the other ones. I don't like that, I think that the other projects are worthy as well. And if I refresh this, so if you remember at the beginning we had... I had almost 600 stars, let me see if I went over 600 stars. If I refresh it, 607 stars. So this project is so popular, I'm not sure why, I know I did a good job, but please take a look at other projects, and go ahead and play with them. If you're a beginner, I recommend you go and play with Neural Style Transfer. This is the fast version of the Neural Style Transfer, this is the Johnson's method, which is much faster, but a bit worse results. And Deep Dream is awesome, so I recommend you start with these projects, they're awesome. I also have one more, which is hidden, which is not pinned, which actually creates videos using this naive approach, so that means there is no temporal loss included, so they'll be a bit jittery. But yeah, I won't get into those details, just check them out, and... yep. As a fun fact, this image here was created using this Deep Dream project, so that's something I created, and you can create your own images yourself, so yeah, go ahead, enjoy, play, and hopefully you found this video useful. If you did, you know the drill, just subscribe, hit that bell icon, and that will help me grow this channel, if you found some value in it, and until next time, keep learning deep.
[{"start": 0.0, "end": 8.0, "text": " What's up folks? So for those of you who don't know, four days ago I open sourced a brand new project."}, {"start": 8.0, "end": 11.0, "text": " It's the implementation of the Graph Attention Network."}, {"start": 11.0, "end": 26.0, "text": " So in this video I thought doing a quick walkthrough and just going to read me and potentially try and explain the potential pain points in the Jupyter notebook."}, {"start": 26.0, "end": 34.0, "text": " Mainly the implementation itself, like the core part of how the get method works."}, {"start": 34.0, "end": 44.0, "text": " But before that, I just want to remind you that aside from this project, I've got a lot more interesting projects on my GitHub."}, {"start": 44.0, "end": 47.0, "text": " So I've been working and implementing these projects for at least a year."}, {"start": 47.0, "end": 58.0, "text": " So aside from this one, which is super popular, I've open sourced this four days ago and it's got almost 600 stars, which is better than all of my previous projects."}, {"start": 58.0, "end": 62.0, "text": " Like the best one was Transformer, which had around 400 stars."}, {"start": 62.0, "end": 65.0, "text": " And I'm really glad I don't treat these as a vanity metric."}, {"start": 65.0, "end": 69.0, "text": " I'm just glad that I see that the community is actually using the stuff I produce."}, {"start": 69.0, "end": 73.0, "text": " So that makes me happy and makes me want to create these even more."}, {"start": 73.0, "end": 84.0, "text": " So as I said, aside from the PyTorch get, which I'll cover in this video, I had some really interesting projects, especially if you're like a newcomer to deep learning field."}, {"start": 84.0, "end": 88.0, "text": " Like you should check out this Deep Dream project."}, {"start": 88.0, "end": 90.0, "text": " It's got really like just look at this imagery."}, {"start": 90.0, "end": 95.0, "text": " It's so so freaking exciting and looks really nice, if nothing else."}, {"start": 95.0, "end": 97.0, "text": " But you'll learn a lot by doing these projects."}, {"start": 97.0, "end": 100.0, "text": " And I'll always recommend something like this to a beginner."}, {"start": 100.0, "end": 108.0, "text": " So if you're a beginner, you should consider doing something like this, something like Deep Dream as your first or like second project, whatever."}, {"start": 108.0, "end": 111.0, "text": " And yeah, it's just so awesome."}, {"start": 111.0, "end": 120.0, "text": " And I think the reason it's not as popular, so it's only it only has like 56 stars, is I haven't added the Jupyter notebook yet."}, {"start": 120.0, "end": 130.0, "text": " And I think I'll just invest like a couple of days in a couple in a couple of months to just add the Jupyter notebooks to all of the projects that don't have it."}, {"start": 130.0, "end": 136.0, "text": " So that will hopefully make it even more accessible than than the current state of the project."}, {"start": 136.0, "end": 141.0, "text": " OK, aside from Deep Dream, you should check out the Neural Style Transfer project."}, {"start": 141.0, "end": 144.0, "text": " That's how I started the whole this whole YouTube channel."}, {"start": 144.0, "end": 151.0, "text": " I started with the Neural Style Transfer series, but it wasn't as popular, so it kind of dumped it and started doing other things."}, {"start": 151.0, "end": 153.0, "text": " But I really enjoyed creating this project."}, {"start": 153.0, "end": 165.0, "text": " And just again, just look at this like like if somebody told me like a couple of years ago that like a neural network create like a piece of art like this, I'd be really surprised."}, {"start": 165.0, "end": 166.0, "text": " It's amazing."}, {"start": 166.0, "end": 181.0, "text": " And the reason like the pure fact that it's so visual helps you maybe at least help me better engage with this project and made it so much interesting than just doing something that you can."}, {"start": 181.0, "end": 184.0, "text": " It's not as palpable as this thing."}, {"start": 184.0, "end": 193.0, "text": " And also I've got implementation of a couple of different GAN architectures like I implemented the original GAN architecture."}, {"start": 193.0, "end": 198.0, "text": " And you can see here the generator slowly learns how to generate MNIST digits."}, {"start": 198.0, "end": 202.0, "text": " And finally, the outputs are almost indistinguishable from the inputs."}, {"start": 202.0, "end": 207.0, "text": " But this is a simple data set, so it's not hard to to learn that."}, {"start": 207.0, "end": 214.0, "text": " And I also had the conditional GAN implementation and DC GAN where I'm just using this Celibate data set to generate faces."}, {"start": 214.0, "end": 220.0, "text": " So I encourage you to check out these projects and play with them."}, {"start": 220.0, "end": 231.0, "text": " I hate seeing them not being as used as much as as the current as the GAT project, even though they're really cool and an awesome learning resource."}, {"start": 231.0, "end": 234.0, "text": " And I'll try and add the Jupyter really soon."}, {"start": 234.0, "end": 239.0, "text": " With that out of the way, let me jump back to the topic of this video."}, {"start": 239.0, "end": 242.0, "text": " And that's a graph attention network."}, {"start": 242.0, "end": 247.0, "text": " I just want to quickly walk you through the readme and show you what you can see here."}, {"start": 247.0, "end": 251.0, "text": " So the first thing, just go and click click around these links."}, {"start": 251.0, "end": 255.0, "text": " There are many awesome applications I've linked here."}, {"start": 255.0, "end": 257.0, "text": " Those are mostly short blogs which you can just read."}, {"start": 257.0, "end": 271.0, "text": " And if you're not familiar with GNNs, I strongly encourage you to just go and explore and read about all of the awesome applications that GNNs not just get like graph neural networks in general enable."}, {"start": 271.0, "end": 285.0, "text": " OK, so in this schematic, what you can see is the like a schematic representation of GAT where basically you can see the H1 area, which is the feature vector of this node one."}, {"start": 285.0, "end": 297.0, "text": " And the edges just they just represent the other feature vectors that will get used to update this node's feature vector."}, {"start": 297.0, "end": 303.0, "text": " And the differently colored and these squiggly lines just represent multiple attention heads."}, {"start": 303.0, "end": 308.0, "text": " And in this image, it seems like this GAT has three attention heads."}, {"start": 308.0, "end": 318.0, "text": " And after you just kind of accumulate and you weigh the feature vectors and you aggregate them, you get the updated version H1 prime."}, {"start": 318.0, "end": 325.0, "text": " And again, I encourage you if you have if you're not familiar with GAT, go and watch my video on graph attention network."}, {"start": 325.0, "end": 327.0, "text": " I got it covered thoroughly."}, {"start": 327.0, "end": 332.0, "text": " So that's pretty much a prerequisite to understand this project."}, {"start": 332.0, "end": 336.0, "text": " And yet so I encourage you go check it out."}, {"start": 336.0, "end": 338.0, "text": " Let me continue here."}, {"start": 338.0, "end": 344.0, "text": " So for the time being, I've only got a core citation network data set covered."}, {"start": 344.0, "end": 346.0, "text": " So that's the transductive approach."}, {"start": 346.0, "end": 359.0, "text": " And I'll be I'll be probably adding PPI or the protein protein interaction data set really soon, which is the inductive setup, which will make this project even more useful for you."}, {"start": 359.0, "end": 363.0, "text": " So what you can see here is just the visualization of Cora."}, {"start": 363.0, "end": 371.0, "text": " And what I did here is that the size of the node so Cora has two thousand seven hundred eight nodes."}, {"start": 371.0, "end": 374.0, "text": " And what I did here to plot it is the following."}, {"start": 374.0, "end": 382.0, "text": " Basically, the size of the node corresponds to the degree of that particular node where the degree is the number of edges."}, {"start": 382.0, "end": 384.0, "text": " So the bigger the node, the more the edges."}, {"start": 384.0, "end": 389.0, "text": " And you can see there are like a couple of nodes that are really big and most of them are really small."}, {"start": 389.0, "end": 391.0, "text": " And we'll see that in a minute."}, {"start": 391.0, "end": 394.0, "text": " Like some nicer plots that will explain that."}, {"start": 394.0, "end": 397.0, "text": " Second thing, the colors are the classes."}, {"start": 397.0, "end": 399.0, "text": " So Cora has got seven classes."}, {"start": 399.0, "end": 403.0, "text": " And that's why we have seven colors in this in this chart."}, {"start": 403.0, "end": 405.0, "text": " And finally, the edges."}, {"start": 405.0, "end": 414.0, "text": " So the thickness of the edge is pretty much correlates with the something called edge between us."}, {"start": 414.0, "end": 424.0, "text": " Basically, you want to take a particular edge and you want to find the number of geodesics, i.e. the the number of shortest paths that go through that particular edge."}, {"start": 424.0, "end": 427.0, "text": " So you have all of those nodes in the in the in the graph."}, {"start": 427.0, "end": 428.0, "text": " Right."}, {"start": 428.0, "end": 440.0, "text": " And for every single pair of those nodes, you just go through the command control space and you find all the pairs and you ask the question, what's the shortest path between this node and this node?"}, {"start": 440.0, "end": 447.0, "text": " And while looking at a particular edge, you want to know how many of those shortest paths go through this through that edge."}, {"start": 447.0, "end": 450.0, "text": " And that kind of quantifies the popularity of that edge."}, {"start": 450.0, "end": 454.0, "text": " And so the thicker the edge, the more shortest paths go through it."}, {"start": 454.0, "end": 456.0, "text": " Hopefully, that was clear enough."}, {"start": 456.0, "end": 458.0, "text": " So that's the chart you can see here."}, {"start": 458.0, "end": 461.0, "text": " And going down here."}, {"start": 461.0, "end": 466.0, "text": " So in this chart, we can see is the like the node degree of every single node in core."}, {"start": 466.0, "end": 471.0, "text": " So we've got two thousand seven hundred eight nodes on the x axis is the node ID on the y axis."}, {"start": 471.0, "end": 475.0, "text": " We get the edge count for a particular node."}, {"start": 475.0, "end": 480.0, "text": " And we can see there is one node that has one hundred sixty nine like edges."}, {"start": 480.0, "end": 486.0, "text": " And the rest are have much, much, much, much less edges."}, {"start": 486.0, "end": 495.0, "text": " And the final this bottom plot shows really nicely that the accumulation happens around two to five edges."}, {"start": 495.0, "end": 499.0, "text": " So most of the nodes in Cora have only two to five edges."}, {"start": 499.0, "end": 501.0, "text": " And this plot shows it really nicely."}, {"start": 501.0, "end": 504.0, "text": " So it goes up until hundred sixty nine."}, {"start": 504.0, "end": 511.0, "text": " That's the this this node and that's the big green node in this chart above."}, {"start": 511.0, "end": 513.0, "text": " OK, that's that was Cora."}, {"start": 513.0, "end": 516.0, "text": " We showed I showed you the schematic of GATT."}, {"start": 516.0, "end": 522.0, "text": " And finally, once you once you train the GATT model and hopefully understand how GATT works,"}, {"start": 522.0, "end": 530.0, "text": " basically, you know that it tries to to to assign attention coefficient to every single of its neighbor"}, {"start": 530.0, "end": 534.0, "text": " in order to aggregate those and update the representation."}, {"start": 534.0, "end": 545.0, "text": " So what we see here is the the the edges, the thickness of the edge is proportional to the attention coefficient."}, {"start": 545.0, "end": 549.0, "text": " And because we can see that every single edge here is of the same thickness,"}, {"start": 549.0, "end": 558.0, "text": " we can deduce that the GATT model on Cora data set learns to to just output constant attention pattern,"}, {"start": 558.0, "end": 560.0, "text": " which is not as interesting."}, {"start": 560.0, "end": 565.0, "text": " And the reason is because this data is pretty simple for forget its homophilic,"}, {"start": 565.0, "end": 568.0, "text": " meaning that similar nodes cluster together."}, {"start": 568.0, "end": 571.0, "text": " You can see here by just looking at the color."}, {"start": 571.0, "end": 576.0, "text": " So the blue node here, you can see that mostly the blue nodes connect to the blue node."}, {"start": 576.0, "end": 582.0, "text": " And that's something known as the homophilic property of of of of graphs."}, {"start": 582.0, "end": 590.0, "text": " And yeah, that's that's the reason why why GATT learns these boring constant attention patterns."}, {"start": 590.0, "end": 595.0, "text": " But yeah, in this node here is one of the nodes with the most edges."}, {"start": 595.0, "end": 598.0, "text": " Most of you'll see nodes like this."}, {"start": 598.0, "end": 602.0, "text": " So as I said, two to five edges is the common number."}, {"start": 602.0, "end": 605.0, "text": " So this one is a common representative you'll find in Cora."}, {"start": 605.0, "end": 609.0, "text": " And again, the edges are the same thickness, meaning constant attention."}, {"start": 609.0, "end": 615.0, "text": " There is one more interesting way to to understand the attention patterns that GATT is learning."}, {"start": 615.0, "end": 618.0, "text": " And that's this entropy histograms method."}, {"start": 618.0, "end": 621.0, "text": " And what we do here basically is the following."}, {"start": 621.0, "end": 628.0, "text": " So because all of these sum up to one, because we applied the softmax while producing these attention coefficients,"}, {"start": 628.0, "end": 632.0, "text": " we can just treat all of these neighborhoods as a simple as simple distributions."}, {"start": 632.0, "end": 636.0, "text": " And because you have a probability distribution, you can calculate the entropy."}, {"start": 636.0, "end": 644.0, "text": " And now the point I want to want to stress here is that you don't need to know a lot about information theory."}, {"start": 644.0, "end": 646.0, "text": " Actually, you don't need to know anything."}, {"start": 646.0, "end": 649.0, "text": " The whole point with entropy histograms is the following."}, {"start": 649.0, "end": 656.0, "text": " So you take the ideal, the hypothetical GATT model on your particular data set in Cora here,"}, {"start": 656.0, "end": 661.0, "text": " and you make it have like a constant attention, like a perfectly constant attention."}, {"start": 661.0, "end": 665.0, "text": " That means you always have the uniform distributions."}, {"start": 665.0, "end": 670.0, "text": " And what you do is you just plot, you just calculate the entropies, you create a histogram."}, {"start": 670.0, "end": 674.0, "text": " And that's the orange histogram in this chart."}, {"start": 674.0, "end": 680.0, "text": " And then you take your GATT trained, your trained GATT model, and you do the same procedure."}, {"start": 680.0, "end": 688.0, "text": " And if the histograms match with that hypothetical GATT, that means your GATT has learned constant attention."}, {"start": 688.0, "end": 695.0, "text": " And you can see here basically that the orange and the blue histograms totally match with each other,"}, {"start": 695.0, "end": 700.0, "text": " which means our GATT learned to produce constant attention patterns."}, {"start": 700.0, "end": 703.0, "text": " And yeah, that's just another way to look at this."}, {"start": 703.0, "end": 707.0, "text": " And if we had some different data set like PPI, which I'll soon add,"}, {"start": 707.0, "end": 714.0, "text": " the histograms would be like, would have much less matching than on this chart."}, {"start": 714.0, "end": 722.0, "text": " So yeah, that's a second really nice visualization that helps you understand the attention patterns that GATT is learning."}, {"start": 722.0, "end": 728.0, "text": " Okay. Having said that, in the paper you could see the t-SNE plot."}, {"start": 728.0, "end": 730.0, "text": " I did the same thing here."}, {"start": 730.0, "end": 736.0, "text": " Basically, you take the final from the final layer, you take the embeddings, and you use t-SNE, project them into 2D,"}, {"start": 736.0, "end": 747.0, "text": " and you get this nice chart here showing us basically that GATT has learned to cluster nodes of the same class in the same part of the 2D space,"}, {"start": 747.0, "end": 757.0, "text": " which is awesome, which means we can easily train a classifier to kind of just classify these edges into one of seven classes."}, {"start": 757.0, "end": 762.0, "text": " Okay. That was pretty much it. I've got the setup usage and everything here."}, {"start": 762.0, "end": 770.0, "text": " You can just go and read through the README, and you'll hopefully have no problems starting this project."}, {"start": 770.0, "end": 776.0, "text": " One more thing I want to note here is that you'll usually see these circular patterns."}, {"start": 776.0, "end": 785.0, "text": " So the thing is the graph drawing is a subfield for itself, like something similar to tokenizers if you're familiar with transformers."}, {"start": 785.0, "end": 789.0, "text": " It's something you just take for granted, but it's a field for itself."}, {"start": 789.0, "end": 797.0, "text": " So I usually use this Rhine Gold Tilford circular layout, and you'll get charts like this one,"}, {"start": 797.0, "end": 805.0, "text": " but you can use some other techniques and layouts like Kamadi Kawai, this one, and you'll get charts like this one."}, {"start": 805.0, "end": 815.0, "text": " So this one, the Rhine Gold Tilford, is really adequate for true-like graphs, and because this is basically MRE3,"}, {"start": 815.0, "end": 819.0, "text": " I've used this layout, and it gives really nice results."}, {"start": 819.0, "end": 824.0, "text": " But just be aware there are multiple layouts, and I've been using iGraph plotting package,"}, {"start": 824.0, "end": 830.0, "text": " so you can just go explore some other layouts, but for this particular problem, I think this does the job."}, {"start": 830.0, "end": 833.0, "text": " Okay. That was everything I wanted to cover in the README."}, {"start": 833.0, "end": 840.0, "text": " Now I'll jump into the Jupyter and OneNote and try and explain a couple of potential pain points."}, {"start": 840.0, "end": 848.0, "text": " And welcome to the Jupyter Notebook. So I'll give you time to go through the Jupyter Notebook by yourself, by your own pace."}, {"start": 848.0, "end": 856.0, "text": " What I want to do in this video is just kind of focus on two specific pain points, potential pain points for you,"}, {"start": 856.0, "end": 861.0, "text": " and just focus on that one. So first things first is data."}, {"start": 861.0, "end": 867.0, "text": " What I did here is you'll usually see, if you take a look at the official GATT implementation"}, {"start": 867.0, "end": 878.0, "text": " or some re-implementations like PyGATT project, you'll see a bunch of files which actually date back from the planetoid paper."}, {"start": 878.0, "end": 888.0, "text": " And the thing is, like most of those implementations, just copy-pasted the same snippets for processing the Quora."}, {"start": 888.0, "end": 896.0, "text": " And so I just decided to do the processing and just save those into files so that you can just import the node features like this,"}, {"start": 896.0, "end": 905.0, "text": " the node labels like this, and finally the structure of the graph, the edges and connections through one line of code."}, {"start": 905.0, "end": 910.0, "text": " Hopefully this will make it a bit easier for you to just not have to look through some pre-processing stuff."}, {"start": 910.0, "end": 922.0, "text": " Let me quickly just explain how these structures look like, and then I'll jump into explaining how the GATT method itself works."}, {"start": 922.0, "end": 929.0, "text": " Okay, so node features. So those of you who watched my previous video on GATT, this will probably be familiar,"}, {"start": 929.0, "end": 936.0, "text": " but let me just recap here because I'll be using these structures later when explaining the implementation of the GATT method itself."}, {"start": 936.0, "end": 945.0, "text": " So first things first, node features. It's a matrix like this. We basically, so Quora has 2,708 nodes,"}, {"start": 945.0, "end": 952.0, "text": " and I've been working so much with Quora that I know every single number on top of my head."}, {"start": 952.0, "end": 960.0, "text": " And the second dimension is 1,433. Now that may seem like an arbitrary number, and it's actually not."}, {"start": 960.0, "end": 969.0, "text": " I'll just explain how they got that number. So yeah, so that's the feature vectors for every single node."}, {"start": 969.0, "end": 973.0, "text": " And so how they got this number is the following. So they took all of the research papers."}, {"start": 973.0, "end": 981.0, "text": " They just created a simple histogram of words, meaning on the x-axis you have a word, on the y-axis you have the frequency of that word"}, {"start": 981.0, "end": 985.0, "text": " throughout all of those research papers. And now what they did is the following."}, {"start": 985.0, "end": 993.0, "text": " They just created a cutoff frequency, like maybe 10, which means just disregard the words that have a frequency less than 10"}, {"start": 993.0, "end": 1000.0, "text": " across all documents, and just keep all of the rest, and they ended up with 1,433 words."}, {"start": 1000.0, "end": 1007.0, "text": " So now how you create a feature vector for a specific research paper, which is a node in Quora, right?"}, {"start": 1007.0, "end": 1015.0, "text": " You do the following. You just go through the words of the research paper, and you see if some of the words from this vocabulary"}, {"start": 1015.0, "end": 1020.0, "text": " we just created is present in that research paper. So maybe if we had attention is all you need paper,"}, {"start": 1020.0, "end": 1026.0, "text": " and in the vocab we had the attention word, we put one where that field is."}, {"start": 1026.0, "end": 1040.0, "text": " So basically, let me just draw it here. If this is the feature vector, and this particular slot, so this is again 1,433,"}, {"start": 1040.0, "end": 1049.0, "text": " and if this one corresponds to attention, you take a specific research paper and you ask, does it have the word attention present inside?"}, {"start": 1049.0, "end": 1056.0, "text": " If it does, we put a 1, and by doing that you create a feature vector, and it will look something like this,"}, {"start": 1056.0, "end": 1062.0, "text": " and it will mostly be sparse, so most of these will be zeros, and I'll show you how it actually looks like in a second,"}, {"start": 1062.0, "end": 1069.0, "text": " but let's take this for a moment, and later you'll see in the code the feature normalization part,"}, {"start": 1069.0, "end": 1077.0, "text": " and what it does, it's a really simple thing. You just sum up all of these ones, and you just divide all of the numbers by the sum,"}, {"start": 1077.0, "end": 1086.0, "text": " and we'll end up with having 1 over 2 here, and 1 over 2 here, because we only had two ones in this particular example."}, {"start": 1086.0, "end": 1093.0, "text": " So in a more general case, you'll just have 1 over n, where n is the number of ones in your feature vector."}, {"start": 1093.0, "end": 1099.0, "text": " So that's the normalization part, and now let me just show you how the feature vectors look like."}, {"start": 1099.0, "end": 1108.0, "text": " Okay, so I just opened up the PyGad project, and you can see here on the screen the feature vectors for every single node in Quora,"}, {"start": 1108.0, "end": 1115.0, "text": " and most of the numbers are zeros. You see a couple of ones here, but it's pretty sparse representation."}, {"start": 1115.0, "end": 1124.0, "text": " And finally, the labels, I mentioned seven labels, so they're genetic algorithms, probabilistic methods, case-based theory, reinforcement learning, etc."}, {"start": 1124.0, "end": 1132.0, "text": " So what I did is I just assigned a number 0 through 6 to all of these strings, and we'll be using that as labels."}, {"start": 1132.0, "end": 1138.0, "text": " So that leads me to the second structure, and that's the node labels, and the shape is pretty straightforward."}, {"start": 1138.0, "end": 1148.0, "text": " So basically we have, again, 2,708 nodes here, and we only have one here, because we have a single class, right?"}, {"start": 1148.0, "end": 1157.0, "text": " So these numbers will be 0 through 6, maybe this one will be 5, so this node with this feature vector will have class 5."}, {"start": 1157.0, "end": 1167.0, "text": " So that's the node labels structure. And finally, we've got this adjacency list dictionary, which just contains the connections, the edges in the Quora,"}, {"start": 1167.0, "end": 1177.0, "text": " and the structure, it's a simple dictionary, meaning the keys are node IDs, maybe 0, and 0 will have associated with it all of the edges,"}, {"start": 1177.0, "end": 1186.0, "text": " maybe something like, I don't know, 1, 2, 3, 25, whatever. And those are the nodes that 0 connects to."}, {"start": 1186.0, "end": 1196.0, "text": " And finally, once we have this, the third most important structure that you'll see used throughout the code is something called the edge index."}, {"start": 1196.0, "end": 1203.0, "text": " And what edge index is, it's a simple way to, it's a dense way to represent your connectivity in your graph."}, {"start": 1203.0, "end": 1211.0, "text": " So I just copy-pasted that snippet that creates the edge index, and you can see it uses this structure, the adjacency list we have here."}, {"start": 1211.0, "end": 1215.0, "text": " It just needs a number of nodes, and we'll be adding self-edges, and we'll see that in a moment."}, {"start": 1215.0, "end": 1222.0, "text": " So what happens is the following. I just iterate through this dictionary object, and I create the edge index doing the following thing."}, {"start": 1222.0, "end": 1234.0, "text": " So, by the way, the shape is just 2, comma, E, where E is, I think, 13,264 edges."}, {"start": 1234.0, "end": 1244.0, "text": " And how we create that is really simple. So we have 0 and the corresponding list of target nodes here, so I'll just go through the list, and I'll see 0, 1, okay."}, {"start": 1244.0, "end": 1253.0, "text": " We add 0, 1 topple to the edge. Then we add 0, 2 topple to the edge."}, {"start": 1253.0, "end": 1265.0, "text": " Finally, we add 0, 3, 0, blah, blah, blah, 0, 25. And after I do that for every single node, so 0, 25, I don't know how to write today,"}, {"start": 1265.0, "end": 1270.0, "text": " and I'll just iterate through all of the keys, and finally, I'll just add the self-edges."}, {"start": 1270.0, "end": 1279.0, "text": " So that means after I finish all of this procedure, going through this dictionary, I'll just add 0, 0, meaning node 0 connects to itself,"}, {"start": 1279.0, "end": 1290.0, "text": " and the same goes for every single node up until 2,707. So that's the edge index, and you can see the shape is just a bunch of these topples,"}, {"start": 1290.0, "end": 1294.0, "text": " and there are this many of these topples, and that's the edge index structure."}, {"start": 1294.0, "end": 1304.0, "text": " And hopefully, this makes it easier for you to now tackle the Jupyter notebook yourself. I'll just cover the... I'll try and cover the method."}, {"start": 1304.0, "end": 1308.0, "text": " It's complicated. I'll use a dumb example, and we'll see if it works."}, {"start": 1308.0, "end": 1315.0, "text": " Going back to the Jupyter notebook, and just scrolling to the main part, to the meat of this project, so we've got some visualizations."}, {"start": 1315.0, "end": 1322.0, "text": " We saw this in the readme. You'll be able to just generate those yourself, just go through the Jupyter, and yeah, this is the main part."}, {"start": 1322.0, "end": 1326.0, "text": " So we have the high-level class, and we have the actual implementation."}, {"start": 1326.0, "end": 1339.0, "text": " And so the only part that will probably create you some problems to understand how it works is a couple of lines of code, so namely this."}, {"start": 1339.0, "end": 1347.0, "text": " So from this huge, huge, huge, huge Jupyter notebook, the only part that's actually maybe hard to understand is this one."}, {"start": 1347.0, "end": 1359.0, "text": " And so I'll try and now explain how this part works. Maybe you should first just go yourself through this code, and then continue watching this video."}, {"start": 1359.0, "end": 1365.0, "text": " Okay, I'll try and use a toy example here to explain how the implementation works."}, {"start": 1365.0, "end": 1381.0, "text": " So just a quick recap. Let me use this as a running example. Three nodes, just two edges here, and also self-connections are here."}, {"start": 1381.0, "end": 1388.0, "text": " And now I'll just add some IDs here. So this is node 0, this is node 1, and this is node 2."}, {"start": 1388.0, "end": 1409.0, "text": " So how GAT works is the following. So we have associated a feature vector with every single node, and what we do is we basically need to find the attention coefficient for this feature vector, and for this one, and for this one, in order to update the feature vector, this feature vector, okay?"}, {"start": 1409.0, "end": 1418.0, "text": " And so we first project those feature vectors into some smaller subspace, and then how we find those attentions is the following."}, {"start": 1418.0, "end": 1438.0, "text": " We just concatenate this representation with this one. We apply something called like a scoring function, and that one is basically densely connected like a linear layer here, and that will give us a score for this particular edge."}, {"start": 1438.0, "end": 1453.0, "text": " We do the same thing here, we do the same thing for the self-edge, and which means for the self-edge we'll have this same vector duplicated two times, and we just apply the same scoring function, so these weights here."}, {"start": 1453.0, "end": 1474.0, "text": " Once we have the scores, we apply the softmax, that will make them sum up to 1, and then we just multiply this particular vector with that specific attention coefficient, we'll multiply this one with its attention coefficient, and the same goes for this vector, and we'll end up with a new representation, and that's the updated representation."}, {"start": 1474.0, "end": 1490.0, "text": " I missed some details like Rayleigh uses, blah blah blah, but this is the core concept, so you want to find those attention coefficients, you want to multiply the projected vectors using those coefficients, and you want to aggregate all of those using the sum into a new updated representation."}, {"start": 1490.0, "end": 1494.0, "text": " So hopefully that kind of just refreshes your mind on how GAT works."}, {"start": 1494.0, "end": 1516.0, "text": " Okay, let's build up the structures we'll need in order to go through this example. So, first assumption is I only have a single attention head, I'll ditch the eight attention heads that we have in the actual implementation, I'll just work with a single attention head, otherwise it gets really hard to explain it, but it's the same thing, we just duplicate whatever I say here, eight times, that's it."}, {"start": 1516.0, "end": 1534.0, "text": " They are totally independent, so it makes sense to reduce this problem to a single attention head. So, first thing we have node vectors, so that means we have three here because we have three nodes, and these are 1,433."}, {"start": 1534.0, "end": 1551.0, "text": " The second thing we have is the edge index, and let's see how the edge index looks like. So let's first see which nodes connect to zero. So, one connects to zero, two connects to zero, and zero connects to zero."}, {"start": 1551.0, "end": 1565.0, "text": " Then let's see which nodes connect to one. So, zero connects to one, and one connects to one. And finally, which nodes connect to two, and that's zero connects to two, and to itself connects to itself, right?"}, {"start": 1565.0, "end": 1572.0, "text": " So this is the edge index structure for this particular graph. Okay?"}, {"start": 1572.0, "end": 1585.0, "text": " Once we have that, let's see how the method works. So what I do is, the first thing, you have this projection layer, and you just project this thing into some smaller subspace."}, {"start": 1585.0, "end": 1603.0, "text": " So this gets projected into eight dimensional vectors. So we'll have three by eight. And if we had multiple attention heads, the only thing that would be different, you would have eight by eight independent columns here, and that's the only difference."}, {"start": 1603.0, "end": 1617.0, "text": " And the actual implementation detail is that you'll project this vector into 64 dimensional vector, and then you just apply this view function, which basically just doesn't change anything."}, {"start": 1617.0, "end": 1626.0, "text": " It changes like the stride, a couple of parameters in the matrix itself, but it doesn't change the underlying memory layout. So that's the important thing to notice."}, {"start": 1626.0, "end": 1644.0, "text": " Okay, so once we have this projected thing, what do we do? We do the following. We need to first lift these. So we first need to calculate these scores for every single edge, because that's how get works."}, {"start": 1644.0, "end": 1657.0, "text": " It requires these scores, and then transforms them into attention coefficients, and let's see how we actually do it through code. So after we project them, we do the following. We apply these left and right scoring functions."}, {"start": 1657.0, "end": 1667.0, "text": " And let me just explain that, why that works. So basically, you can treat this as the left side and the right side, and you just apply, so let me draw it again."}, {"start": 1667.0, "end": 1674.0, "text": " So instead of holistically applying, concatenating the feature vectors, and then applying a single scoring function, you can do the following."}, {"start": 1674.0, "end": 1685.0, "text": " You can take this feature vector, put it here, and apply a single, the source, I called it the source scoring function, and you find the score here."}, {"start": 1685.0, "end": 1693.0, "text": " And you take the second feature vector, and you apply a separate scoring function, the target scoring function, and you get the score."}, {"start": 1693.0, "end": 1702.0, "text": " And if you just sum them up, that's exactly the same result as by just doing a single scoring function on the concatenated version of these vectors, okay?"}, {"start": 1702.0, "end": 1718.0, "text": " Hopefully that makes sense. So that's the main potential pain point for you. So it's conceptually, it's a bit different, but like it's the same thing at the end. It's semantically the same thing, okay?"}, {"start": 1718.0, "end": 1729.0, "text": " So what we'll do here is we'll take these projected vectors, we'll apply the left and the right scoring function, which will, so we'll end up with three by one."}, {"start": 1729.0, "end": 1739.0, "text": " So we have scores, so these are the source scores, and these are the target scores. Okay. So that's again three by one."}, {"start": 1739.0, "end": 1755.0, "text": " And now there is this thing called lifting in the code. So what lifting does is it uses this edge index structure to just copy these projected vectors and these source and target scores."}, {"start": 1755.0, "end": 1763.0, "text": " So what I mean by that is the following. So we'll take the source scores, and we'll take the source column. So this is the source column, and this is the target column."}, {"start": 1763.0, "end": 1775.0, "text": " Remember, this means one, the source node points to zero, the target node. So that's this directed edge. And because we have both, we just read the core as undirected graph."}, {"start": 1775.0, "end": 1785.0, "text": " So we'll just do the following. So one means we take score one and we copy it here. Let me just draw it like this."}, {"start": 1785.0, "end": 1793.0, "text": " So we'll have, so because this has how many edges, like seven. So this one will have seven edges here and one after being lifted."}, {"start": 1793.0, "end": 1804.0, "text": " So we'll take one, we copy score one here. We see two, we copy score two here. We see zero, we copy score zero here, et cetera."}, {"start": 1804.0, "end": 1816.0, "text": " And that's how we lift up the source scores. We do the same thing for the target scores, but we just use the target column of the index this time."}, {"start": 1816.0, "end": 1828.0, "text": " And the same procedure goes. So we'll have zero, so we'll copy zero here, blah, blah, blah. And we form the lifted versions of these structures."}, {"start": 1828.0, "end": 1836.0, "text": " And finally, we do the same thing for this projected vectors and we use the source index."}, {"start": 1836.0, "end": 1845.0, "text": " And it will hopefully make sense why we are using the source index here. But like for the time being, let me just copy it here."}, {"start": 1845.0, "end": 1860.0, "text": " So we'll end up with seven, seven rows and the same concept goes. So the same idea again, we just copy. So we have one, we copy the projected vector one here."}, {"start": 1860.0, "end": 1869.0, "text": " We have two, we copy the projected vector two here. And so on and so on. And that's how we form these lifted versions."}, {"start": 1869.0, "end": 1876.0, "text": " So now for the fun part. So what do we do now? So we take and we just add up these scores."}, {"start": 1876.0, "end": 1892.0, "text": " And we end up with something that calls scores per edge. And after applying a ReLU, we just apply a ReLU, Leaky ReLU, and we get the final scores per edge."}, {"start": 1892.0, "end": 1902.0, "text": " So why do we do the lifting? So the idea is really simple, because we have score for node one here and we have score for node zero here."}, {"start": 1902.0, "end": 1913.0, "text": " What we effectively did by summing up these two and putting them here is we calculated the score for this particular edge."}, {"start": 1913.0, "end": 1925.0, "text": " And that's what we want, because we need scores, we need those scores in order to calculate the attention coefficients and we need those in order to create the updated version of the feature vector."}, {"start": 1925.0, "end": 1932.0, "text": " So again, by doing this simple lifting, we calculated the scores only for those edges that we care about."}, {"start": 1932.0, "end": 1939.0, "text": " So if this was a fully connected graph, we'd have much more edges and we don't need to calculate the scores for the edges that don't exist."}, {"start": 1939.0, "end": 1945.0, "text": " And that's, so if you take a look at implementation one and two of my project, you'll see exactly that."}, {"start": 1945.0, "end": 1955.0, "text": " I'm calculating the scores for every single possible edge and then doing some smart masking, we just finally find the attention coefficients only for the edges."}, {"start": 1955.0, "end": 1963.0, "text": " But it's far less efficient than this implementation, even though this one is conceptually, as you can see, a bit harder to explain and to understand."}, {"start": 1963.0, "end": 1970.0, "text": " But it's super simple, like once you invest a little bit of time, you'll be able to understand everything."}, {"start": 1970.0, "end": 1973.0, "text": " OK, so we've got the scores per edge."}, {"start": 1973.0, "end": 1977.0, "text": " How do we convert these scores per edge into those attention coefficients we need?"}, {"start": 1977.0, "end": 1979.0, "text": " Well, the following we do the following."}, {"start": 1979.0, "end": 1986.0, "text": " We basically again take the target column of the edge index and we do something called a neighborhood aware softmax."}, {"start": 1986.0, "end": 1993.0, "text": " And that's something I just dubbed it like that. That's not official literature term. That's something just I dubbed it like that."}, {"start": 1993.0, "end": 1995.0, "text": " That's how I name my variables."}, {"start": 1995.0, "end": 1997.0, "text": " And what happens is the following."}, {"start": 1997.0, "end": 2001.0, "text": " So we take the edge index and we can see there are zeros here."}, {"start": 2001.0, "end": 2008.0, "text": " That means we want to make sure that these scores here sum up to one."}, {"start": 2008.0, "end": 2010.0, "text": " That's the neighborhood aware portion."}, {"start": 2010.0, "end": 2021.0, "text": " So using the edge index, you know, you know exactly which parts of this scores per edge structure need to sum up to one."}, {"start": 2021.0, "end": 2025.0, "text": " So because these correspond to node zero, we want them."}, {"start": 2025.0, "end": 2029.0, "text": " We want to we want to make sure that they sum up to one."}, {"start": 2029.0, "end": 2031.0, "text": " And then we have ones here."}, {"start": 2031.0, "end": 2035.0, "text": " So that means we want to make sure that this chunk here sums up to one."}, {"start": 2035.0, "end": 2040.0, "text": " And finally, because we have twos here, we want to make sure that these sum up to one."}, {"start": 2040.0, "end": 2042.0, "text": " So how we do that is the following."}, {"start": 2042.0, "end": 2045.0, "text": " We just we first raise this structure."}, {"start": 2045.0, "end": 2052.0, "text": " We just do exponential of this structure, because if you remember like the softmax, we got e to the i."}, {"start": 2052.0, "end": 2057.0, "text": " And then you've got sums of e to the like these are scores."}, {"start": 2057.0, "end": 2060.0, "text": " And basically, this is some particular score for node i."}, {"start": 2060.0, "end": 2063.0, "text": " And this is for the other neighbors."}, {"start": 2063.0, "end": 2068.0, "text": " And because of that, because we have that exponential, we want to exponentiate."}, {"start": 2068.0, "end": 2071.0, "text": " That's even a word, this structure."}, {"start": 2071.0, "end": 2074.0, "text": " So we have the same dimensions."}, {"start": 2074.0, "end": 2076.0, "text": " These are now just exponents."}, {"start": 2076.0, "end": 2077.0, "text": " So this is seven."}, {"start": 2077.0, "end": 2078.0, "text": " This is one."}, {"start": 2078.0, "end": 2080.0, "text": " In general, this will be e."}, {"start": 2080.0, "end": 2085.0, "text": " So for Quora, this will be, if we remember, 13,264, whatever."}, {"start": 2085.0, "end": 2092.0, "text": " And now we want to make sure that the summations go over these neighborhoods I just defined."}, {"start": 2092.0, "end": 2096.0, "text": " So that means in the code, you'll see something called scatter add."}, {"start": 2096.0, "end": 2098.0, "text": " And what scatter add does is the following."}, {"start": 2098.0, "end": 2101.0, "text": " It will just sum up these."}, {"start": 2101.0, "end": 2104.0, "text": " And so we'll get a smaller structure."}, {"start": 2104.0, "end": 2108.0, "text": " So this thing will actually end up being three."}, {"start": 2108.0, "end": 2112.0, "text": " Or in general, this will be the number of nodes in your graph."}, {"start": 2112.0, "end": 2116.0, "text": " And once we do that, we just want to lift it up again."}, {"start": 2116.0, "end": 2118.0, "text": " And you'll see in a moment why."}, {"start": 2118.0, "end": 2120.0, "text": " Hopefully you already understand."}, {"start": 2120.0, "end": 2130.0, "text": " So we'll lift it up again by copying the lifting up using the target portion of the edge index."}, {"start": 2130.0, "end": 2133.0, "text": " And once we have these numbers, now it's pretty simple."}, {"start": 2133.0, "end": 2143.0, "text": " We just divide these by these, because these here are the same numbers, and they are just the sum of these three elements."}, {"start": 2143.0, "end": 2147.0, "text": " So once we divide this, that's basically doing this portion."}, {"start": 2147.0, "end": 2149.0, "text": " And we end up having the attention coefficients."}, {"start": 2149.0, "end": 2160.0, "text": " So after we do division, after we divide, let me denote it like this, this vector with this one, we end up with the attention coefficients."}, {"start": 2160.0, "end": 2162.0, "text": " And now we're really close."}, {"start": 2162.0, "end": 2163.0, "text": " Now it's really simple."}, {"start": 2163.0, "end": 2165.0, "text": " Now we do the following."}, {"start": 2165.0, "end": 2170.0, "text": " We just take these attention coefficients and we multiply them with this."}, {"start": 2170.0, "end": 2177.0, "text": " And if you remember, we use the source portion of the edge index to project, to lift these up."}, {"start": 2177.0, "end": 2183.0, "text": " And now we just multiply these, and that's the weighted part of the..."}, {"start": 2183.0, "end": 2187.0, "text": " And now we just need to aggregate all of those, and that's the get method, right?"}, {"start": 2187.0, "end": 2198.0, "text": " So after we multiply this coefficient to this projected vector and to this and to this, we'll get what we semantically did for get, right?"}, {"start": 2198.0, "end": 2205.0, "text": " And hopefully now we can see why we use the source portion, the source column of the edge index to lift the projected vectors."}, {"start": 2205.0, "end": 2213.0, "text": " Because this now is node 1 representation, this is node 2 representation, or the projected feature vector."}, {"start": 2213.0, "end": 2221.0, "text": " And once we multiply it with this coefficient, we basically get what we want, and that's we accumulate, we aggregate."}, {"start": 2221.0, "end": 2233.0, "text": " So this is... so 1, that's this one, 2, that's this one, and we just multiply with the attention coefficients and we get the weighted feature vectors."}, {"start": 2233.0, "end": 2236.0, "text": " And now we just want to do the aggregation. How do we do the aggregation?"}, {"start": 2236.0, "end": 2250.0, "text": " So after multiplying these two structures, we'll end up with the weighted structure, again 7 and 8 here, because remember the projected vectors had dimension 8."}, {"start": 2250.0, "end": 2267.0, "text": " And finally, again, simple scatter add using the target index will make sure that we sum up the right nodes, the right nodes, yep, and we'll finally end up with 3 by 8."}, {"start": 2267.0, "end": 2272.0, "text": " And that's... those are the new representations that we wanted."}, {"start": 2272.0, "end": 2290.0, "text": " Again, we use the target column of the edge index to do the scatter add, and that will make sure that we... so we have zeros here, that means these feature vectors connect to zero, and we'll just scatter add them, and that's the final representation here."}, {"start": 2290.0, "end": 2297.0, "text": " Hopefully this made it a bit easier for you to understand it. I don't know if I explained it perfectly, I tried my best."}, {"start": 2297.0, "end": 2306.0, "text": " I just want to wrap it up, reminding you again to just check out other projects, and this one got un-proportionally more popular than the other ones."}, {"start": 2306.0, "end": 2311.0, "text": " I don't like that, I think that the other projects are worthy as well."}, {"start": 2311.0, "end": 2318.0, "text": " And if I refresh this, so if you remember at the beginning we had... I had almost 600 stars, let me see if I went over 600 stars."}, {"start": 2318.0, "end": 2332.0, "text": " If I refresh it, 607 stars. So this project is so popular, I'm not sure why, I know I did a good job, but please take a look at other projects, and go ahead and play with them."}, {"start": 2332.0, "end": 2343.0, "text": " If you're a beginner, I recommend you go and play with Neural Style Transfer. This is the fast version of the Neural Style Transfer, this is the Johnson's method, which is much faster, but a bit worse results."}, {"start": 2343.0, "end": 2349.0, "text": " And Deep Dream is awesome, so I recommend you start with these projects, they're awesome."}, {"start": 2349.0, "end": 2361.0, "text": " I also have one more, which is hidden, which is not pinned, which actually creates videos using this naive approach, so that means there is no temporal loss included, so they'll be a bit jittery."}, {"start": 2361.0, "end": 2368.0, "text": " But yeah, I won't get into those details, just check them out, and... yep."}, {"start": 2368.0, "end": 2383.0, "text": " As a fun fact, this image here was created using this Deep Dream project, so that's something I created, and you can create your own images yourself, so yeah, go ahead, enjoy, play, and hopefully you found this video useful."}, {"start": 2383.0, "end": 2402.0, "text": " If you did, you know the drill, just subscribe, hit that bell icon, and that will help me grow this channel, if you found some value in it, and until next time, keep learning deep."}]