Graph Attention Networks (GAT) | GNN Paper Explained
❤️ Become The AI Epiphany Patreon ❤️ ► https://www.patreon.com/theaiepiphany
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬

In this video, I do a deep dive into the graph attention network paper!

GATs have a lot in common with transformers a reason more to keep an eye out for them!

You'll learn about:
✔️ Basic graph theory
✔️ All the nitty-gritty details behind GAT

▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 
✅ GAT website: https://petar-v.com/GAT/
✅ GAT paper: https://arxiv.org/abs/1710.10903
✅ M. Bronstein's blog: https://towardsdatascience.com/do-we-need-deep-graph-neural-networks-be62d3ec5c59
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 

⌚️ Timetable: 
00:00 - A note on geometric deep learning
00:50 - Graph theory basics
08:35 - Intro to GATs (related work)
10:15 - A detailed explanation of the method
16:20 - A multi-head version of the GAT
19:05 - Visualizations, spatial pooling, GNN depth
21:20 - A recap of GAT properties
23:35 - Receptive field of spatial GNNs
24:35 - Datasets, transductive vs inductive learning
30:35 - Results on transductive/inductive benchmarks
35:30 - Representations visualization (t-SNE)

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

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

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

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

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

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

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

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

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

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

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

#graphs #attention #deeplearning
 So I started doing geometric deep learning and the first paper I want to kick off this series with is graph attention networks. But before I do that let me let me give you a quick note. So as I said I started doing geometric deep learning and I've been collecting a bunch of resources. So cool blogs, useful blogs, videos, papers and I've read already a lot of them and I'll be creating a video in the future covering how you can approach learning this exciting field. So similarly to how I did it for transformers, if you are familiar with those videos I created. So I'll basically create one video where I'll help you structure your learning through geometric deep learning. So without further ado let me get back to to get to graph attention networks. So you can see, so first I want to shout out to Petar Velichkovich. He's my friend from Serbia and he did this work while he was back in Montreal. So that's why you can see Josje Benjio on the list. Pietro Leo is his PhD advisor from Cambridge and his colleagues whom unfortunately I don't know but I guess they're they're great researchers as well. So let me start with abstract. We present graph attention networks novel neural network architectures that operate on graph structure data and because this is the first video in this series I'm gonna do like a quick tangent here and explain like briefly explain the notation and how it in generally works and then I'll jump to the method. So if you just want to see the method feel free to skip I'll put the timestamps on the on the video so you can jump wherever you want. Okay let me start with this one. So let me open a pen. Okay my god my god. Let me do a quick recap of graph theory which will help you better understand this paper as well as all of the other papers I'll cover. Some include spectral methods, some include spatial methods. I'll explain briefly like in a couple of minutes what those are. So let me start with graph theory 101. So basically a graph is a collection a set of nodes. So let me like depict the nodes as these small circles and we have so that set is usually known as V and then we have the cardinality number of that set which is the number of elements in that set and that's usually denoted as N. So nodes are connected via edges so let me maybe create some random graph like this one and they are somehow connected and what I've just draw here is our undirected edges but they can also be directed edges. They can also there can also be multiple edges and those things are called multi graphs or hyper graphs and but we won't be focusing on those now because this paper the GAT paper only focuses on undirected graphs but it's easy to to generalize the method as well as other methods to both directed graphs and those more complicated types of graphs which have maybe self self connections or multiple edges etc. So what happens now is that each of these nodes have something called like a feature vector associated with each single node and so you maybe have like F features there and all of these nodes have the same thing associated so they have they have different feature vectors and aside from that edges also can have feature vector associated with them and the set of edges is usually denoted by E and this is the number of edges in your graph. So now aside from these things there is something called adjacency matrix which is useful a concept to have as we will briefly see why and it's noted as A and it just tells you the connection pattern of your graph so basically it's an M by N matrix where N is the number of nodes in your graph and it just tells you which node is connected to which one so if we label these nodes numerically like this 0 1 2 3 the node 0 is connected to 1 2 & 3 but it's not connected to itself because I haven't added this thing called a self connection or maybe without the edge but anyways and so we'll have a pattern like this so 0 because the node 0 is connected to it's not connected to itself then we have 1 1 1 and if we take a look at the node 1 it's only going to be connected to node 0 and it's going to have zeros elsewhere so once you have this adjacency matrix you can construct something called a laplacian matrix which is used heavily used in spectral methods to construct something called laplacian eigen basis which is a generalization of the Fourier basis if you're familiar with that and once you have the eigen basis you can basically construct the signal on the graph as a weighted sum of those eigen vectors and if that didn't make any sense let me just briefly explain it even though it's not so important for this paper but I'm doing a recap so why not so what the signal on the graph is so you basically take like the feature number one from all of these feature vectors and that represents one signal so maybe signal one let me do know it like s1 and what I just said is you can once you connect what once you create those eigenvectors you can just represent s1 as some as a weighted sum so maybe W eyes and let me denote the eigenvectors as L eyes so that's it so that's a similar thing as as in a signal processing when you're using Fourier basis where you can represent any any signal as a sum as a weighted sum of sinusoids and this is a generalization where once you have a regular graph and not just any arbitrary graph like this one the laplacian eigen basis would actually correspond to the Fourier basis just to make this graph a bit less abstract so as an example because this paper uses these citation networks so what these nodes would be in this in these particular data sets is the following so you have so this node would be like like one paper so maybe this one is get paper maybe this one is transformer and we don't we drop the directionality so even though get sighted transformer and not vice versa we just drop the directionality for now and we just use undirected edge and that does hurt the performance a bit but not a lot not by a lot and so what I wanted to say here is that the feature vector for this particular paper may for example be the following so you just take the abstract and you basically just like embed all of these words using for example word2vec and you just then do bag of words so you'll basically whatever number of words curious like maybe 500 words in the abstract and all of the all of the word2vec embeddings are maybe 256 dimensionality so just average all of these 500 vectors that have this dimensionality and you end up with a single 256 vector and that's your feature for this node and once you have that you train the model later on to to do whatever you want so that's all I want to cover there so what I mentioned that one is because you basically have when you're trying to to do this graph representation learning and do something interesting with those representations maybe do some classification or regression you basically have either spatial methods or you have spectral methods and get here is a good a good example of a spatial method and that's why I just wanted to create this distinction so the paper itself heavily relies on the attention mechanism obviously so that's like the name of the paper is graph attention networks and especially the the famous the original transformer paper by Vasvani and his collaborators they it's a decent pretty similar idea as well as well as soon see but like back in 2017 when this paper was created the the the transformers were not as near as popular as they are now in 2020 so now what we get by doing this is so we do inherit some nice properties of transformers and that's that the operation is efficient meaning we can basically parallelize and do those representation learnings across nodes and across edges which is what makes this method really efficient it can be applying to graph nodes having different degrees now what are degrees I forgot to mention that one so basically however many edges we have connected to our notes that's the degree so this is the degree of this note would be one the degree of this note would be three this would be two etc so let me go back here so it can be applied to graph nodes having whatever the number of degrees beat one beat like 370 whatever if you have social network maybe and second nice third nice property is that the model is directly applicable to inductive learning problems and we'll see what's trans talked to you when what's inductive a bit later but just keep keep that in mind now let me finally jump into the method itself so how the method functions is is the following so I'll just be following these equations and hopefully help you better understand what those means better created really nice visualizations here so we can maybe leverage those as well and we have the final set of equations here okay let me let me try and go and explain every single one of these so how it how it works so the method works is the following so we have again I'm going to just draw simple graph here and I'm going to do some random connections like previously maybe like this okay and now what we do for every single node we do the following so let's say this is note zero this is node one two and three basically we find what the neighbors of the current nodes a node are so zero node zero has all of these nodes as neighbors and what we're going to do is we'll have something like this simple matrix W which we're going to linearly linearly project the feature vectors which we as like let me let me let me draw them here quickly and they have dimensionality like F and this matrix will project them into the space where where they'll have like dimension F prime so that means this matrix will be simply be like F F prime and once we do like multiplication with these vectors we'll just project them into that space so basically what it does it's a you can you can treat it as a simple neural network although there is no non linearity at the moment so project this into a space where we have F prime features and yeah it just is just fully connected so once we have those intermediate representations and those are denoted here like this so they use the notation that's a bit different than I have been using so far so basically I haven't been using any notations but anyways so so this would be denoted like the feature vector for node 3 would be noted as h3 with a small arrow above which is kind of interesting because it associates with me with physics and this doesn't have to be it doesn't have to do anything with physics so let me denote once once we project into the F prime space let me denote those representations as having a tilde above so once you have that now we are going to do the attention part and how it works in get paper is they just do so this is h0 arrow and tilde because we projected into F prime space and now what we do is we just concatenate h0 with maybe h1 if we want to see what the attention wait for h1 should be we just concatenate these two and I'm gonna just denote this with square brackets and then we just multiply that with this a arrow vector which will have the dimensionality to F prime and it's basically you can treat it as a dot product and we get we basically get and then we apply the like non-linearity and they used something called leaky value and we get a value out here which they denote as e i j so there's gonna be some some number and we're going to do that not just for h1 we're going to do it for h2 as well we're going to do for h3 3 and finally for h0 and doing that we'll get these scores which then will just be passed into softmax and that means we got a sum of one when you sum all of those softmax values we'll get they'll sum up to one and then we can just do a weighted sum of all of those all of these F prime representation so the ones that have tilde will just sum those up and we'll get the new representation for for every single node and aside from that we'll just apply a non-linearity and they usually used relu or even elu or e elu non-linearities there so that's let me jump into the equations you can see it here as I just said you basically just concatenate those intermediate representations you do a dot product here you pass it into relu and then you just do softmax and that's how you get the weights which you then use to do a simple weighted sum over the neighbors so j goes over the neighbors of I and we just saw that the neighbors of I are all of these other nodes 1 2 & 3 so those are the equations and as you can see it's it's pretty similar to the transformer although I have actually asked better better and he told me they tried in the Q K V matrices but the the the network itself overfitted these small data sets because they're using core sites here and PubMed which are decently small citation and network so it turned out that just using one of these weighted matrices does the job so now there is a simple extension to the method and that's using k hats like the same thing as the transformers you have multiple hats in your attention and it's a decently simple generalization you basically have so until now you had per layer you had a single matrix w and the single vector a arrow and those are all the trainable parameters you have so now you just have K of those and you independently apply all of them and you just concatenate the results as you can see here this is the operator for concatenation so you do the same thing but you just concatenate all of the feature vectors and you get the new representation so basically let me maybe do a quick explanation of that in practice what I did is so we say the maybe the F was the dimension of the initial representations was maybe 64 what they would do is those WK matrices would project this vector into maybe only eight dimensions so you just do blah blah blah just do the fully connected thing you get you get a vector that has only eight dimensions and then you do the attention you do the weighted average and you just concatenate the results for all of those and you end up at the end with again 64 dimensional representation in the end that goes into the second get layer and so forth so there is one more interesting detail and that's this equation number six where they basically showed that they do it a bit differently so they don't apply the non-linearity and then concatenate they just average out all of those vectors so representations they average them out by K and then just applied non-linearity which would be because this is the last layer this would either be softmax or maybe logistic sigmoid I think they said it somewhere here so it's a softmax or logistic sigmoid in the case they're using this for classification problems as they did in the get paper so that means that they won't be doing this sub like dimensionality reduction they'll just the last layer will actually have all of the K hats just operating on the 64 the output will be 64 and not 8 and then they'll just average these out and not concatenate them so hopefully that was that made any any sense let's take a quick look on these visualizations and you can see the thing I just explained so basically we have these intermediate representations which I denoted as with tildes and you just concatenate them you do the star product with this a arrow vector and basically then you apply some non-linearity like non like leaky relu and you apply the softmax and you get these attention weights which you then just use as the weights in the weighted average some to get the final representations and these squiggly lines here like the purple green and the straight blue line just represent different various hats and as I said you either concatenate them in in the in the layers before the last one or you just average them out in the last layer and that's how you get the next representation so it's pretty pretty pretty pretty easy and all of these graph neural networks work like conceptually really similar so you basically have a graph and you pass it through all air we just modify these representations and outcomes the processed graph G although there is this concept of spatial resolution reduction the same as you have with convolutional neural networks where you have maybe the input image then gets like down sampled by maybe two and then by two that's like VGG and many networks do it like that so you can do a similar thing here doing for some clustering and then just reducing the dimension of the graph but gets and many methods I've read usually don't do this reduction and what's also really interesting with graph neural networks is they're a much shallower than the CNNs which you usually encounter in computer vision and Mikhail Brunstein created a series of nice blocks which I'll maybe even link in this video where he explained he actually explored why that is why is it that in graph neural networks like deeper isn't better and I won't get into that at this point of time okay so let me recap a couple of things that hopefully we we already saw so computationally gets are really highly efficient and that's something that's a property they share with transformers and again I mentioned laplacian I can decompositions those are really costly and that's why you want to avoid them and not only because of that but also they are not localized meaning the spread so you don't have this nice property of just attending over the local neighborhood like one hop neighborhood or two hop neighborhood you actually touch every single every single node and that's that's oftentimes not desirable because graphs are you usually have the information of interest somewhere locally in your community and yeah this equation just pretty much sums up like the just the the calculations we just saw and yeah the attention enables a leaping model capacity so compared to say GCN the graph convolutional neural network that Thomas Kipf and others created they use they have a isotropic filtering in a way because they give a same weight to all of the feature vectors around the current node of interest whereas get actually can do a weighted can because of the tension it can do different weightings for different feature vectors depending on how they interact again as I said it's pretty trivial to to make this undirected so if to make it directed so say if you have a if you have a maybe nodes like this you'll just ignore oops you'll just ignore these I'm retarded today so just ignore these that go they have just outward connections and you'll just take these nodes as the neighbors which point to the current node of interest I so that's pretty pretty simple stuff and one more interesting thing receptive field again if you're familiar with the CNN's so receptive field of our model is upper bounded by the depth of the network so why that is is the following so as I already mentioned you basically first attend each node in a single layer attends to the to a one hop neighborhood so what happens here because this node had his neighbors like maybe here that means in the first get layer it will contain some information from this representation so in the second layer this one will be attending this one and the last layer this one attended this one so that's why you effectively after after doing to get layers you'll be attending effectively to a to hop neighborhood and that's what I say say here okay let me jump into data sets and their results and evaluations and let's see what happens what results they achieved they had four data sets that they've tested and those are Cora sites here and PubMed which are citation networks and they have this PPI data set which has to do with protein to protein interactions so I mentioned previously transductive versus inductive learning so what's the difference here so the difference is the following basically when you have transductive learning you have one huge graph so you have you maybe have a citation graph like this and nodes cite each other and for now we'll just assume they are undirected even though technically one paper is citing in other papers so that would be a directed relationship but they usually just drop out the directionality and that does hurt performance a little bit but it's it's it's okay in the sense okay so what happens during these transactive learning trainings is the following so you usually have so if we take for example PubMed you can see that it has around 20k and nodes and it has three classes and basically what they do is they just take 20 nodes out of all of those three classes and they use those 60 nodes and you can see the number 60 here so the training nodes as 60 and they use those to do a semi supervised learning but they also do see all of those other nodes which will be later be tested so you basically see the representation of those test nodes during the training which is not something we're used to in the world of maybe computer vision or even in graph learning when doing active learning you don't see you shouldn't you shouldn't see the test nodes but here in transactive learning you do see the test nodes but you only see the structure you only see the connections you don't see the labels they have so that's the those are the two approaches we have so let me quickly go how this looks like so I'll add one more node so again how this transactive approach learning works is the following so out of all of these nodes only you're using the information like the label information from maybe a single node here from this one so what will happen is during the maybe let's say we have a two layer get so first so this node here will be take we'll take a look at these representations because those are his one hope one hop neighborhoods neighbors and maybe during the second had during the second layer it will also take a look it will also use this nodes representation and then finally it will get its own final representation and after we apply the softmax we'll just get a probability distribution over different classes and say PubMed had three classes so that means this will have only three fields here and basically so then we have a classical like classic classification setup you basically what I do is you take the ground truth label so say this second this is the first class second class and third class say this node belongs to a second class so what you'll do you'll just do a log whatever is in here some probability maybe if it's 0.3 then we're going to and we have a minus so we're gonna heavily penalize it because this is some big value right and we want to have so once we have one the loss will go down to zero and that's what we want to do so then we'll just do like a gradient based learning using your favorite optimizer and that's how you update all of those W and a arrow matrices in all of the get layers so you have this node but because the network is really huge we have around 20k nodes will have 60 of these labels and but we'll we'll also be using the structural information so the connectivity and representations from different nodes but we won't be using their labels so then in the test time we'll try and predict what this once we train this thing we'll try and predict what the label of all of these other nodes are and that's transactive learning and I felt like explaining this a bit better because this was a new concept for me as well I wasn't familiar with this so yeah it's interesting anyways what's interesting is that PP PP PP I has several labels per node whereas all of these others have a single label per node and let's see what the results are before that just one more thing so I mentioned calculating those attention weights so what they additionally do is they do a dropout on those attention weights and some of those will get pulled down to zero which means you basically end up stochastically sampling the neighborhood so we applied dropout to normalize attention coefficients critically this means that at each training iteration each node is exposed to a stochastically sampled neighborhood so that's one one more detail that's interesting and the same thing is applied in transformer so again a parallel there and finally let's see what the results look like so they tested their method against various baselines and so this table here is about transactive results and this one is about inductive results where so inductive if I haven't mentioned it so we have training graphs so we train the network on a bunch of graphs and then we have a separate like testing graphs where we test our model our pre trained get model so that's the usual thing you see all around NLP and computer vision world so some of the baselines they they use for for the transactive datasets are basic multi-layer perceptron like label propagation algorithm deep walk this is a graph embedding method really really interesting one where they use random walks and approach similar to if you're familiar with vertebrate they use this skip gram model to train to train this model planetoid again uses similar to deep walk uses semi supervised learning whereas deep walk only uses unsupervised learning and then you have Chabishov which is one of those spectral methods where although they they improved it like the compute efficiency because they just do some like polynomial expansion of the laplacian and that saves them some compute GCN is a famous model by Thomas Kipf and it's basically you can maybe even treat it as a special case of get where the weights are the same it's similar it's not the same but it's in a way it's similar and then Monette is nice paper where they generalized all of these methods can be actually be treated as a special case of Monette so finally the results and yeah one more thing GCN 64 is just they optimize GCN so that it's the most fair comparison and they tuned the hyper params and these are the results they get so get achieves the state-of-the-art on Quora as well as on sites here it matches the state-of-the-art on PubMed and although these results are like clearly show that get is better than all of these previous baselines in 2020 there was this paper that showed that these benchmarks we should question like their validity because they are really small and the model can easily overfit and it's not easy to compare now in 2020 especially different gene and models and we are we are we are actually as a community like looking for for a new and better data sets where we can evaluate these gene ends results on inductive learning data set is the following so they they took as the baselines random again multilayer perceptron and this graph sage method which is similar to GCN except that it does a uniform sampling of the neighborhood and thus they they showed that it can be I can be applied to much larger like a social network like size graphs with billions of nodes and they have just a different ways of accumulating the neighborhoods they are using max pooling LSTM even and then just simple mean element-wise mean aggregation etc so yeah I won't get into a lot of details about these methods if you're familiar with them this will maybe be a nice recap and again they showed that we get improvements with get on this desk as well so they they state here that larger predictive power can be leveraged by observing the entire neighborhood so the thing is with with graph sage basically so if you have a huge neighborhood I'll denote it like a like a curve here and this is the second hop neighborhood so what the what GNN does is it basically attends to every single node in the one hop neighborhood whereas graph sage will actually just take a sub sample randomly sub sample these neighbors in the first layer and then repeat that in the second layer so yeah it's just that's that's the the hypothesis that that's the reason why I get this better although that does imply a greater unnecessary compute but that's the trade-off and yep it depends on your application so that was it there's just one more interesting chart here and this one I just want to quickly explain what this is basically once you pre-train the get on the Quora data set what you do is the following so let me let me depict the graph initial graph like like this circle we have the first get layer so this is get layer number one outcomes like the modified version of the graph representations and then there is one more layer and then we do the soft maxes and stuff so if we take the representations out of this layer and we apply this thing this dimensionality reduction method called t-sne that was introduced by Hinton and his collaborators we basically project those those vectors into 2d space and we get this and because Quora let me just jump to the table above because Quora had seven classes as you can see here and around 2,700 notes that's why we get seven different colors here and you can see that the first get layer learns how to nicely separate and cluster similar similar classes so it's pretty easy to later learn some classifier which would learn how to separate all of these and have a nice predictive generalization so that was pretty much it those are just some references so if you found this video useful click that subscribe button and also consider clicking the bell icon to get notified when they upload a new video if you'd love me to create more of these videos please write it down in the comment section I'm just starting reviewing these papers and hopefully you found this useful so anyways until next time keep learning deep
[{"start": 0.0, "end": 5.46, "text": " So I started doing geometric deep learning and the first paper I want to"}, {"start": 5.46, "end": 10.200000000000001, "text": " kick off this series with is graph attention networks. But before I do that"}, {"start": 10.200000000000001, "end": 15.64, "text": " let me let me give you a quick note. So as I said I started doing geometric deep"}, {"start": 15.64, "end": 20.72, "text": " learning and I've been collecting a bunch of resources. So cool blogs, useful"}, {"start": 20.72, "end": 28.560000000000002, "text": " blogs, videos, papers and I've read already a lot of them and I'll be"}, {"start": 28.56, "end": 35.16, "text": " creating a video in the future covering how you can approach learning"}, {"start": 35.16, "end": 39.519999999999996, "text": " this exciting field. So similarly to how I did it for"}, {"start": 39.519999999999996, "end": 43.08, "text": " transformers, if you are familiar with those videos I created. So I'll basically"}, {"start": 43.08, "end": 47.96, "text": " create one video where I'll help you structure your learning through"}, {"start": 47.96, "end": 53.76, "text": " geometric deep learning. So without further ado let me get back to to get to"}, {"start": 53.76, "end": 59.28, "text": " graph attention networks. So you can see, so first I want to shout out to"}, {"start": 59.28, "end": 65.0, "text": " Petar Velichkovich. He's my friend from Serbia and he did this work while"}, {"start": 65.0, "end": 69.96, "text": " he was back in Montreal. So that's why you can see Josje Benjio on the list."}, {"start": 69.96, "end": 77.4, "text": " Pietro Leo is his PhD advisor from Cambridge and his colleagues whom"}, {"start": 77.4, "end": 81.03999999999999, "text": " unfortunately I don't know but I guess they're they're great researchers as"}, {"start": 81.04, "end": 85.92, "text": " well. So let me start with abstract. We present graph attention networks novel"}, {"start": 85.92, "end": 89.4, "text": " neural network architectures that operate on graph structure data and"}, {"start": 89.4, "end": 94.32000000000001, "text": " because this is the first video in this series I'm gonna do like a quick tangent"}, {"start": 94.32000000000001, "end": 100.28, "text": " here and explain like briefly explain the notation and how it in generally"}, {"start": 100.28, "end": 104.04, "text": " works and then I'll jump to the method. So if you just want to see the method"}, {"start": 104.04, "end": 108.0, "text": " feel free to skip I'll put the timestamps on the on the video so you can"}, {"start": 108.0, "end": 117.04, "text": " jump wherever you want. Okay let me start with this one. So let me open a pen. Okay"}, {"start": 117.04, "end": 121.88, "text": " my god my god. Let me do a quick recap of graph theory which will help you better"}, {"start": 121.88, "end": 126.32, "text": " understand this paper as well as all of the other papers I'll cover. Some"}, {"start": 126.32, "end": 129.84, "text": " include spectral methods, some include spatial methods. I'll explain briefly"}, {"start": 129.84, "end": 134.52, "text": " like in a couple of minutes what those are. So let me start with graph theory"}, {"start": 134.52, "end": 143.76000000000002, "text": " 101. So basically a graph is a collection a set of nodes. So let me like depict the"}, {"start": 143.76000000000002, "end": 148.56, "text": " nodes as these small circles and we have so that set is usually known as V and"}, {"start": 148.56, "end": 152.60000000000002, "text": " then we have the cardinality number of that set which is the number of elements"}, {"start": 152.60000000000002, "end": 159.56, "text": " in that set and that's usually denoted as N. So nodes are connected via edges so"}, {"start": 159.56, "end": 165.92000000000002, "text": " let me maybe create some random graph like this one and they are somehow"}, {"start": 165.92000000000002, "end": 171.64000000000001, "text": " connected and what I've just draw here is our undirected edges but they can"}, {"start": 171.64000000000001, "end": 177.28, "text": " also be directed edges. They can also there can also be multiple edges and"}, {"start": 177.28, "end": 182.88, "text": " those things are called multi graphs or hyper graphs and but we won't be"}, {"start": 182.88, "end": 188.44, "text": " focusing on those now because this paper the GAT paper only focuses on"}, {"start": 188.44, "end": 193.72, "text": " undirected graphs but it's easy to to generalize the method as well as other"}, {"start": 193.72, "end": 198.16, "text": " methods to both directed graphs and those more complicated types of graphs"}, {"start": 198.16, "end": 205.96, "text": " which have maybe self self connections or multiple edges etc. So what happens"}, {"start": 205.96, "end": 211.32, "text": " now is that each of these nodes have something called like a feature vector"}, {"start": 211.32, "end": 218.88, "text": " associated with each single node and so you maybe have like F features there and"}, {"start": 218.88, "end": 223.6, "text": " all of these nodes have the same thing associated so they have they have"}, {"start": 223.6, "end": 229.48, "text": " different feature vectors and aside from that edges also can have feature vector"}, {"start": 229.48, "end": 235.28, "text": " associated with them and the set of edges is usually denoted by E and this"}, {"start": 235.28, "end": 243.48, "text": " is the number of edges in your graph. So now aside from these things there is"}, {"start": 243.48, "end": 249.44, "text": " something called adjacency matrix which is useful a concept to have as we will"}, {"start": 249.44, "end": 255.68, "text": " briefly see why and it's noted as A and it just tells you the connection pattern"}, {"start": 255.68, "end": 263.08, "text": " of your graph so basically it's an M by N matrix where N is the number of nodes"}, {"start": 263.08, "end": 267.56, "text": " in your graph and it just tells you which node is connected to which one so if we"}, {"start": 267.56, "end": 277.36, "text": " label these nodes numerically like this 0 1 2 3 the node 0 is connected to 1 2 &"}, {"start": 277.36, "end": 281.64, "text": " 3 but it's not connected to itself because I haven't added this thing"}, {"start": 281.64, "end": 288.0, "text": " called a self connection or maybe without the edge but anyways and so we'll"}, {"start": 288.0, "end": 292.0, "text": " have a pattern like this so 0 because the node 0 is connected to it's not"}, {"start": 292.0, "end": 297.6, "text": " connected to itself then we have 1 1 1 and if we take a look at the node 1 it's"}, {"start": 297.6, "end": 303.84, "text": " only going to be connected to node 0 and it's going to have zeros elsewhere so"}, {"start": 303.84, "end": 308.92, "text": " once you have this adjacency matrix you can construct something called a"}, {"start": 308.92, "end": 313.64, "text": " laplacian matrix which is used heavily used in spectral methods to construct"}, {"start": 313.64, "end": 317.92, "text": " something called laplacian eigen basis which is a generalization of the Fourier"}, {"start": 317.92, "end": 322.12, "text": " basis if you're familiar with that and once you have the eigen basis you can"}, {"start": 322.12, "end": 327.36, "text": " basically construct the signal on the graph as a weighted sum of those eigen"}, {"start": 327.36, "end": 331.0, "text": " vectors and if that didn't make any sense let me just briefly explain it"}, {"start": 331.0, "end": 334.92, "text": " even though it's not so important for this paper but I'm doing a recap so why"}, {"start": 334.92, "end": 339.32, "text": " not so what the signal on the graph is so you basically take like the feature"}, {"start": 339.32, "end": 346.72, "text": " number one from all of these feature vectors and that represents one signal"}, {"start": 346.72, "end": 352.76000000000005, "text": " so maybe signal one let me do know it like s1 and what I just said is you can"}, {"start": 352.76000000000005, "end": 356.68, "text": " once you connect what once you create those eigenvectors you can just"}, {"start": 356.68, "end": 365.44000000000005, "text": " represent s1 as some as a weighted sum so maybe W eyes and let me denote the"}, {"start": 365.44000000000005, "end": 372.52000000000004, "text": " eigenvectors as L eyes so that's it so that's a similar thing as as in a signal"}, {"start": 372.52000000000004, "end": 376.28000000000003, "text": " processing when you're using Fourier basis where you can represent any any"}, {"start": 376.28, "end": 381.55999999999995, "text": " signal as a sum as a weighted sum of sinusoids and this is a generalization"}, {"start": 381.55999999999995, "end": 386.59999999999997, "text": " where once you have a regular graph and not just any arbitrary graph like this"}, {"start": 386.59999999999997, "end": 392.2, "text": " one the laplacian eigen basis would actually correspond to the Fourier basis"}, {"start": 392.2, "end": 397.59999999999997, "text": " just to make this graph a bit less abstract so as an example because this"}, {"start": 397.59999999999997, "end": 404.47999999999996, "text": " paper uses these citation networks so what these nodes would be in this in"}, {"start": 404.48, "end": 408.68, "text": " these particular data sets is the following so you have so this node would"}, {"start": 408.68, "end": 416.0, "text": " be like like one paper so maybe this one is get paper maybe this one is"}, {"start": 416.0, "end": 422.24, "text": " transformer and we don't we drop the directionality so even though get sighted"}, {"start": 422.24, "end": 427.08000000000004, "text": " transformer and not vice versa we just drop the directionality for now and we"}, {"start": 427.08000000000004, "end": 431.72, "text": " just use undirected edge and that does hurt the performance a bit but not a lot"}, {"start": 431.72, "end": 439.48, "text": " not by a lot and so what I wanted to say here is that the feature vector for this"}, {"start": 439.48, "end": 444.64000000000004, "text": " particular paper may for example be the following so you just take the abstract"}, {"start": 444.64000000000004, "end": 453.68, "text": " and you basically just like embed all of these words using for example word2vec"}, {"start": 453.68, "end": 458.6, "text": " and you just then do bag of words so you'll basically whatever number of"}, {"start": 458.6, "end": 464.48, "text": " words curious like maybe 500 words in the abstract and all of the all of the"}, {"start": 464.48, "end": 470.48, "text": " word2vec embeddings are maybe 256 dimensionality so just average all of"}, {"start": 470.48, "end": 475.36, "text": " these 500 vectors that have this dimensionality and you end up with a"}, {"start": 475.36, "end": 481.08000000000004, "text": " single 256 vector and that's your feature for this node and once you have"}, {"start": 481.08000000000004, "end": 487.16, "text": " that you train the model later on to to do whatever you want so that's all I"}, {"start": 487.16, "end": 492.56, "text": " want to cover there so what I mentioned that one is because you basically have"}, {"start": 492.56, "end": 497.36, "text": " when you're trying to to do this graph representation learning and do"}, {"start": 497.36, "end": 499.92, "text": " something interesting with those representations maybe do some"}, {"start": 499.92, "end": 503.48, "text": " classification or regression you basically have either spatial methods or"}, {"start": 503.48, "end": 509.88, "text": " you have spectral methods and get here is a good a good example of a spatial"}, {"start": 509.88, "end": 515.12, "text": " method and that's why I just wanted to create this distinction so the paper"}, {"start": 515.12, "end": 521.68, "text": " itself heavily relies on the attention mechanism obviously so that's like the"}, {"start": 521.68, "end": 527.24, "text": " name of the paper is graph attention networks and especially the the famous"}, {"start": 527.24, "end": 535.2, "text": " the original transformer paper by Vasvani and his collaborators they it's"}, {"start": 535.2, "end": 541.64, "text": " a decent pretty similar idea as well as well as soon see but like back in 2017"}, {"start": 541.64, "end": 546.68, "text": " when this paper was created the the the transformers were not as near as"}, {"start": 546.68, "end": 555.24, "text": " popular as they are now in 2020 so now what we get by doing this is so we do"}, {"start": 555.24, "end": 558.04, "text": " inherit some nice properties of transformers and that's that the"}, {"start": 558.04, "end": 561.8, "text": " operation is efficient meaning we can basically parallelize and do those"}, {"start": 561.8, "end": 566.6, "text": " representation learnings across nodes and across edges which is what makes"}, {"start": 566.6, "end": 571.84, "text": " this method really efficient it can be applying to graph nodes having different"}, {"start": 571.84, "end": 577.84, "text": " degrees now what are degrees I forgot to mention that one so basically however"}, {"start": 577.84, "end": 583.76, "text": " many edges we have connected to our notes that's the degree so this is the"}, {"start": 583.76, "end": 589.08, "text": " degree of this note would be one the degree of this note would be three this"}, {"start": 589.08, "end": 595.32, "text": " would be two etc so let me go back here so it can be applied to graph nodes"}, {"start": 595.32, "end": 601.5200000000001, "text": " having whatever the number of degrees beat one beat like 370 whatever if you"}, {"start": 601.5200000000001, "end": 606.44, "text": " have social network maybe and second nice third nice property is that the"}, {"start": 606.44, "end": 610.44, "text": " model is directly applicable to inductive learning problems and we'll"}, {"start": 610.44, "end": 614.9200000000001, "text": " see what's trans talked to you when what's inductive a bit later but just"}, {"start": 614.9200000000001, "end": 622.96, "text": " keep keep that in mind now let me finally jump into the method itself so"}, {"start": 622.96, "end": 627.8000000000001, "text": " how the method functions is is the following so I'll just be following"}, {"start": 627.8000000000001, "end": 636.4000000000001, "text": " these equations and hopefully help you better understand what those means better"}, {"start": 636.4000000000001, "end": 644.0400000000001, "text": " created really nice visualizations here so we can maybe leverage those as well"}, {"start": 644.0400000000001, "end": 651.0, "text": " and we have the final set of equations here okay let me let me try and go and"}, {"start": 651.0, "end": 656.28, "text": " explain every single one of these so how it how it works so the method works is"}, {"start": 656.28, "end": 664.84, "text": " the following so we have again I'm going to just draw simple graph here and I'm"}, {"start": 664.84, "end": 672.84, "text": " going to do some random connections like previously maybe like this okay and now"}, {"start": 672.84, "end": 677.12, "text": " what we do for every single node we do the following so let's say this is note"}, {"start": 677.12, "end": 687.08, "text": " zero this is node one two and three basically we find what the neighbors of"}, {"start": 687.08, "end": 692.2, "text": " the current nodes a node are so zero node zero has all of these nodes as"}, {"start": 692.2, "end": 697.76, "text": " neighbors and what we're going to do is we'll have something like this simple"}, {"start": 697.76, "end": 704.36, "text": " matrix W which we're going to linearly linearly project the feature vectors"}, {"start": 704.36, "end": 711.32, "text": " which we as like let me let me let me draw them here quickly and they have"}, {"start": 711.32, "end": 716.28, "text": " dimensionality like F and this matrix will project them into the space where"}, {"start": 716.28, "end": 721.5600000000001, "text": " where they'll have like dimension F prime so that means this matrix will be"}, {"start": 721.5600000000001, "end": 729.16, "text": " simply be like F F prime and once we do like multiplication with these vectors"}, {"start": 729.16, "end": 733.52, "text": " we'll just project them into that space so basically what it does it's a you can"}, {"start": 733.52, "end": 738.4399999999999, "text": " you can treat it as a simple neural network although there is no non"}, {"start": 738.4399999999999, "end": 744.48, "text": " linearity at the moment so project this into a space where we have F prime"}, {"start": 744.48, "end": 750.1999999999999, "text": " features and yeah it just is just fully connected so once we have those"}, {"start": 750.1999999999999, "end": 755.6, "text": " intermediate representations and those are denoted here like this so they use"}, {"start": 755.6, "end": 762.36, "text": " the notation that's a bit different than I have been using so far so basically I"}, {"start": 762.36, "end": 768.36, "text": " haven't been using any notations but anyways so so this would be denoted like"}, {"start": 768.36, "end": 773.48, "text": " the feature vector for node 3 would be noted as h3 with a small arrow above"}, {"start": 773.48, "end": 781.86, "text": " which is kind of interesting because it associates with me with physics and this"}, {"start": 781.86, "end": 785.72, "text": " doesn't have to be it doesn't have to do anything with physics so let me denote"}, {"start": 785.72, "end": 788.76, "text": " once once we project into the F prime space let me denote those"}, {"start": 788.76, "end": 794.36, "text": " representations as having a tilde above so once you have that now we are going"}, {"start": 794.36, "end": 801.24, "text": " to do the attention part and how it works in get paper is they just do so"}, {"start": 801.24, "end": 809.0, "text": " this is h0 arrow and tilde because we projected into F prime space and now"}, {"start": 809.0, "end": 819.04, "text": " what we do is we just concatenate h0 with maybe h1 if we want to see what the"}, {"start": 819.04, "end": 823.96, "text": " attention wait for h1 should be we just concatenate these two and I'm gonna just"}, {"start": 823.96, "end": 830.56, "text": " denote this with square brackets and then we just multiply that with this a"}, {"start": 830.56, "end": 840.64, "text": " arrow vector which will have the dimensionality to F prime and it's"}, {"start": 840.64, "end": 846.7199999999999, "text": " basically you can treat it as a dot product and we get we basically get and"}, {"start": 846.7199999999999, "end": 851.8399999999999, "text": " then we apply the like non-linearity and they used something called leaky value"}, {"start": 851.8399999999999, "end": 859.16, "text": " and we get a value out here which they denote as e i j so there's gonna be some"}, {"start": 859.16, "end": 864.8399999999999, "text": " some number and we're going to do that not just for h1 we're going to do it for"}, {"start": 864.8399999999999, "end": 872.4399999999999, "text": " h2 as well we're going to do for h3 3 and finally for h0 and doing that we'll"}, {"start": 872.4399999999999, "end": 878.56, "text": " get these scores which then will just be passed into softmax and that means we"}, {"start": 878.56, "end": 884.76, "text": " got a sum of one when you sum all of those softmax values we'll get they'll"}, {"start": 884.76, "end": 889.8, "text": " sum up to one and then we can just do a weighted sum of all of those all of"}, {"start": 889.8, "end": 896.56, "text": " these F prime representation so the ones that have tilde will just sum those up"}, {"start": 896.56, "end": 903.72, "text": " and we'll get the new representation for for every single node and aside from"}, {"start": 903.72, "end": 910.36, "text": " that we'll just apply a non-linearity and they usually used relu or even elu"}, {"start": 910.36, "end": 917.64, "text": " or e elu non-linearities there so that's let me jump into the equations you can"}, {"start": 917.64, "end": 922.28, "text": " see it here as I just said you basically just concatenate those intermediate"}, {"start": 922.28, "end": 928.46, "text": " representations you do a dot product here you pass it into relu and then you"}, {"start": 928.46, "end": 933.2, "text": " just do softmax and that's how you get the weights which you then use to do a"}, {"start": 933.2, "end": 941.48, "text": " simple weighted sum over the neighbors so j goes over the neighbors of I and we"}, {"start": 941.48, "end": 948.6800000000001, "text": " just saw that the neighbors of I are all of these other nodes 1 2 & 3 so those"}, {"start": 948.6800000000001, "end": 952.32, "text": " are the equations and as you can see it's it's pretty similar to the"}, {"start": 952.32, "end": 957.12, "text": " transformer although I have actually asked better better and he told me they"}, {"start": 957.12, "end": 964.32, "text": " tried in the Q K V matrices but the the the network itself overfitted these"}, {"start": 964.32, "end": 969.32, "text": " small data sets because they're using core sites here and PubMed which are"}, {"start": 969.32, "end": 974.42, "text": " decently small citation and network so it turned out that just using one of"}, {"start": 974.42, "end": 982.6800000000001, "text": " these weighted matrices does the job so now there is a simple extension to the"}, {"start": 982.68, "end": 987.54, "text": " method and that's using k hats like the same thing as the transformers you have"}, {"start": 987.54, "end": 992.4, "text": " multiple hats in your attention and it's a decently simple generalization you"}, {"start": 992.4, "end": 998.9599999999999, "text": " basically have so until now you had per layer you had a single matrix w and the"}, {"start": 998.9599999999999, "end": 1005.8199999999999, "text": " single vector a arrow and those are all the trainable parameters you have so now"}, {"start": 1005.8199999999999, "end": 1012.0799999999999, "text": " you just have K of those and you independently apply all of them and you"}, {"start": 1012.08, "end": 1015.26, "text": " just concatenate the results as you can see here this is the operator for"}, {"start": 1015.26, "end": 1020.36, "text": " concatenation so you do the same thing but you just concatenate all of the"}, {"start": 1020.36, "end": 1026.04, "text": " feature vectors and you get the new representation so basically let me maybe"}, {"start": 1026.04, "end": 1034.28, "text": " do a quick explanation of that in practice what I did is so we say the"}, {"start": 1034.28, "end": 1041.16, "text": " maybe the F was the dimension of the initial representations was maybe 64"}, {"start": 1041.16, "end": 1049.2, "text": " what they would do is those WK matrices would project this vector into maybe"}, {"start": 1049.2, "end": 1054.0800000000002, "text": " only eight dimensions so you just do blah blah blah just do the fully"}, {"start": 1054.0800000000002, "end": 1060.2, "text": " connected thing you get you get a vector that has only eight dimensions and then"}, {"start": 1060.2, "end": 1065.64, "text": " you do the attention you do the weighted average and you just concatenate the"}, {"start": 1065.64, "end": 1074.3600000000001, "text": " results for all of those and you end up at the end with again 64 dimensional"}, {"start": 1074.3600000000001, "end": 1080.0400000000002, "text": " representation in the end that goes into the second get layer and so forth so"}, {"start": 1080.0400000000002, "end": 1086.2800000000002, "text": " there is one more interesting detail and that's this equation number six where"}, {"start": 1086.2800000000002, "end": 1092.1200000000001, "text": " they basically showed that they do it a bit differently so they don't apply the"}, {"start": 1092.12, "end": 1099.26, "text": " non-linearity and then concatenate they just average out all of those vectors so"}, {"start": 1099.26, "end": 1105.2399999999998, "text": " representations they average them out by K and then just applied non-linearity"}, {"start": 1105.2399999999998, "end": 1109.1599999999999, "text": " which would be because this is the last layer this would either be softmax or"}, {"start": 1109.1599999999999, "end": 1116.32, "text": " maybe logistic sigmoid I think they said it somewhere here so it's a softmax"}, {"start": 1116.32, "end": 1120.4399999999998, "text": " or logistic sigmoid in the case they're using this for classification problems"}, {"start": 1120.44, "end": 1127.52, "text": " as they did in the get paper so that means that they won't be doing this sub"}, {"start": 1127.52, "end": 1133.92, "text": " like dimensionality reduction they'll just the last layer will actually have"}, {"start": 1133.92, "end": 1140.92, "text": " all of the K hats just operating on the 64 the output will be 64 and not 8 and"}, {"start": 1140.92, "end": 1145.28, "text": " then they'll just average these out and not concatenate them so hopefully that"}, {"start": 1145.28, "end": 1151.08, "text": " was that made any any sense let's take a quick look on these visualizations and"}, {"start": 1151.08, "end": 1155.48, "text": " you can see the thing I just explained so basically we have these intermediate"}, {"start": 1155.48, "end": 1161.2, "text": " representations which I denoted as with tildes and you just concatenate them you"}, {"start": 1161.2, "end": 1167.54, "text": " do the star product with this a arrow vector and basically then you apply some"}, {"start": 1167.54, "end": 1172.56, "text": " non-linearity like non like leaky relu and you apply the softmax and you get"}, {"start": 1172.56, "end": 1177.8999999999999, "text": " these attention weights which you then just use as the weights in the weighted"}, {"start": 1177.8999999999999, "end": 1182.12, "text": " average some to get the final representations and these squiggly lines"}, {"start": 1182.12, "end": 1187.6399999999999, "text": " here like the purple green and the straight blue line just represent"}, {"start": 1187.6399999999999, "end": 1195.2, "text": " different various hats and as I said you either concatenate them in in the in the"}, {"start": 1195.2, "end": 1199.84, "text": " layers before the last one or you just average them out in the last layer and"}, {"start": 1199.84, "end": 1205.08, "text": " that's how you get the next representation so it's pretty pretty"}, {"start": 1205.08, "end": 1210.12, "text": " pretty pretty easy and all of these graph neural networks work like"}, {"start": 1210.12, "end": 1217.8999999999999, "text": " conceptually really similar so you basically have a graph and you pass it"}, {"start": 1217.8999999999999, "end": 1224.6399999999999, "text": " through all air we just modify these representations and outcomes the"}, {"start": 1224.64, "end": 1232.8000000000002, "text": " processed graph G although there is this concept of spatial resolution reduction"}, {"start": 1232.8000000000002, "end": 1237.1200000000001, "text": " the same as you have with convolutional neural networks where you have maybe the"}, {"start": 1237.1200000000001, "end": 1242.1200000000001, "text": " input image then gets like down sampled by maybe two and then by two that's like"}, {"start": 1242.1200000000001, "end": 1247.0800000000002, "text": " VGG and many networks do it like that so you can do a similar thing here doing"}, {"start": 1247.0800000000002, "end": 1252.48, "text": " for some clustering and then just reducing the dimension of the graph but"}, {"start": 1252.48, "end": 1258.68, "text": " gets and many methods I've read usually don't do this reduction and what's also"}, {"start": 1258.68, "end": 1263.3600000000001, "text": " really interesting with graph neural networks is they're a much shallower than"}, {"start": 1263.3600000000001, "end": 1269.56, "text": " the CNNs which you usually encounter in computer vision and Mikhail Brunstein"}, {"start": 1269.56, "end": 1273.84, "text": " created a series of nice blocks which I'll maybe even link in this video"}, {"start": 1273.84, "end": 1280.52, "text": " where he explained he actually explored why that is why is it that in graph"}, {"start": 1280.52, "end": 1286.12, "text": " neural networks like deeper isn't better and I won't get into that at this point"}, {"start": 1286.12, "end": 1294.24, "text": " of time okay so let me recap a couple of things that hopefully we we already saw"}, {"start": 1294.24, "end": 1299.12, "text": " so computationally gets are really highly efficient and that's something"}, {"start": 1299.12, "end": 1304.76, "text": " that's a property they share with transformers and again I mentioned"}, {"start": 1304.76, "end": 1310.76, "text": " laplacian I can decompositions those are really costly and that's why you want to"}, {"start": 1310.76, "end": 1315.12, "text": " avoid them and not only because of that but also they are not localized meaning"}, {"start": 1315.12, "end": 1319.22, "text": " the spread so you don't have this nice property of just attending over the"}, {"start": 1319.22, "end": 1323.32, "text": " local neighborhood like one hop neighborhood or two hop neighborhood you"}, {"start": 1323.32, "end": 1330.4, "text": " actually touch every single every single node and that's that's oftentimes not"}, {"start": 1330.4, "end": 1335.44, "text": " desirable because graphs are you usually have the information of interest"}, {"start": 1335.44, "end": 1340.96, "text": " somewhere locally in your community and yeah this equation just pretty much"}, {"start": 1340.96, "end": 1349.5, "text": " sums up like the just the the calculations we just saw and yeah the"}, {"start": 1349.5, "end": 1354.92, "text": " attention enables a leaping model capacity so compared to say GCN the graph"}, {"start": 1354.92, "end": 1362.68, "text": " convolutional neural network that Thomas Kipf and others created they use they"}, {"start": 1362.68, "end": 1368.0, "text": " have a isotropic filtering in a way because they give a same weight to all"}, {"start": 1368.0, "end": 1372.52, "text": " of the feature vectors around the current node of interest whereas get"}, {"start": 1372.52, "end": 1378.0800000000002, "text": " actually can do a weighted can because of the tension it can do different"}, {"start": 1378.0800000000002, "end": 1383.8400000000001, "text": " weightings for different feature vectors depending on how they interact again as"}, {"start": 1383.84, "end": 1390.76, "text": " I said it's pretty trivial to to make this undirected so if to make it"}, {"start": 1390.76, "end": 1398.08, "text": " directed so say if you have a if you have a maybe nodes like this you'll just"}, {"start": 1398.08, "end": 1404.36, "text": " ignore oops you'll just ignore these I'm retarded today so just ignore these"}, {"start": 1404.36, "end": 1410.12, "text": " that go they have just outward connections and you'll just take these"}, {"start": 1410.12, "end": 1417.0, "text": " nodes as the neighbors which point to the current node of interest I so"}, {"start": 1417.0, "end": 1422.1599999999999, "text": " that's pretty pretty simple stuff and one more interesting thing receptive"}, {"start": 1422.1599999999999, "end": 1427.2399999999998, "text": " field again if you're familiar with the CNN's so receptive field of our model is"}, {"start": 1427.2399999999998, "end": 1431.6399999999999, "text": " upper bounded by the depth of the network so why that is is the following"}, {"start": 1431.6399999999999, "end": 1438.4399999999998, "text": " so as I already mentioned you basically first attend each node in a single layer"}, {"start": 1438.44, "end": 1444.28, "text": " attends to the to a one hop neighborhood so what happens here because this node"}, {"start": 1444.28, "end": 1452.1200000000001, "text": " had his neighbors like maybe here that means in the first get layer it will"}, {"start": 1452.1200000000001, "end": 1456.72, "text": " contain some information from this representation so in the second layer"}, {"start": 1456.72, "end": 1461.48, "text": " this one will be attending this one and the last layer this one attended this"}, {"start": 1461.48, "end": 1468.24, "text": " one so that's why you effectively after after doing to get layers you'll be"}, {"start": 1468.24, "end": 1473.76, "text": " attending effectively to a to hop neighborhood and that's what I say say"}, {"start": 1473.76, "end": 1484.08, "text": " here okay let me jump into data sets and their results and evaluations and let's"}, {"start": 1484.08, "end": 1489.6, "text": " see what happens what results they achieved they had four data sets that"}, {"start": 1489.6, "end": 1496.52, "text": " they've tested and those are Cora sites here and PubMed which are citation"}, {"start": 1496.52, "end": 1501.9599999999998, "text": " networks and they have this PPI data set which has to do with protein to protein"}, {"start": 1501.9599999999998, "end": 1510.0, "text": " interactions so I mentioned previously transductive versus inductive learning so"}, {"start": 1510.0, "end": 1513.7199999999998, "text": " what's the difference here so the difference is the following basically"}, {"start": 1513.72, "end": 1519.92, "text": " when you have transductive learning you have one huge graph so you have you"}, {"start": 1519.92, "end": 1529.3600000000001, "text": " maybe have a citation graph like this and nodes cite each other and for now"}, {"start": 1529.3600000000001, "end": 1534.04, "text": " we'll just assume they are undirected even though technically one paper is"}, {"start": 1534.04, "end": 1537.8, "text": " citing in other papers so that would be a directed relationship but they usually"}, {"start": 1537.8, "end": 1541.76, "text": " just drop out the directionality and that does hurt performance a little bit"}, {"start": 1541.76, "end": 1550.2, "text": " but it's it's it's okay in the sense okay so what happens during these"}, {"start": 1550.2, "end": 1556.08, "text": " transactive learning trainings is the following so you usually have so if we"}, {"start": 1556.08, "end": 1562.36, "text": " take for example PubMed you can see that it has around 20k and nodes and it has"}, {"start": 1562.36, "end": 1568.76, "text": " three classes and basically what they do is they just take 20 nodes out of all of"}, {"start": 1568.76, "end": 1574.04, "text": " those three classes and they use those 60 nodes and you can see the number 60"}, {"start": 1574.04, "end": 1581.76, "text": " here so the training nodes as 60 and they use those to do a semi supervised"}, {"start": 1581.76, "end": 1586.96, "text": " learning but they also do see all of those other nodes which will be later be"}, {"start": 1586.96, "end": 1590.96, "text": " tested so you basically see the representation of those test nodes"}, {"start": 1590.96, "end": 1594.92, "text": " during the training which is not something we're used to in the world of"}, {"start": 1594.92, "end": 1599.68, "text": " maybe computer vision or even in graph learning when doing active learning you"}, {"start": 1599.68, "end": 1603.48, "text": " don't see you shouldn't you shouldn't see the test nodes but here in"}, {"start": 1603.48, "end": 1609.0, "text": " transactive learning you do see the test nodes but you only see the structure you"}, {"start": 1609.0, "end": 1614.72, "text": " only see the connections you don't see the labels they have so that's the those"}, {"start": 1614.72, "end": 1618.96, "text": " are the two approaches we have so let me quickly go how this looks like so I'll"}, {"start": 1618.96, "end": 1623.8000000000002, "text": " add one more node so again how this transactive approach learning works is"}, {"start": 1623.8, "end": 1628.52, "text": " the following so out of all of these nodes only you're using the information"}, {"start": 1628.52, "end": 1633.32, "text": " like the label information from maybe a single node here from this one so what"}, {"start": 1633.32, "end": 1638.8799999999999, "text": " will happen is during the maybe let's say we have a two layer get so first so"}, {"start": 1638.8799999999999, "end": 1643.8, "text": " this node here will be take we'll take a look at these representations because"}, {"start": 1643.8, "end": 1651.68, "text": " those are his one hope one hop neighborhoods neighbors and maybe during"}, {"start": 1651.68, "end": 1658.3600000000001, "text": " the second had during the second layer it will also take a look it will also"}, {"start": 1658.3600000000001, "end": 1666.16, "text": " use this nodes representation and then finally it will get its own final"}, {"start": 1666.16, "end": 1672.72, "text": " representation and after we apply the softmax we'll just get a probability"}, {"start": 1672.72, "end": 1677.3600000000001, "text": " distribution over different classes and say PubMed had three classes so that"}, {"start": 1677.36, "end": 1684.6399999999999, "text": " means this will have only three fields here and basically so then we have a"}, {"start": 1684.6399999999999, "end": 1690.24, "text": " classical like classic classification setup you basically what I do is you"}, {"start": 1690.24, "end": 1696.6799999999998, "text": " take the ground truth label so say this second this is the first class second"}, {"start": 1696.6799999999998, "end": 1701.1599999999999, "text": " class and third class say this node belongs to a second class so what you'll"}, {"start": 1701.1599999999999, "end": 1707.08, "text": " do you'll just do a log whatever is in here some probability maybe if it's 0.3"}, {"start": 1707.08, "end": 1712.76, "text": " then we're going to and we have a minus so we're gonna heavily penalize it"}, {"start": 1712.76, "end": 1719.1399999999999, "text": " because this is some big value right and we want to have so once we have one the"}, {"start": 1719.1399999999999, "end": 1724.56, "text": " loss will go down to zero and that's what we want to do so then we'll just do"}, {"start": 1724.56, "end": 1731.08, "text": " like a gradient based learning using your favorite optimizer and that's how"}, {"start": 1731.08, "end": 1740.72, "text": " you update all of those W and a arrow matrices in all of the get layers so you"}, {"start": 1740.72, "end": 1746.52, "text": " have this node but because the network is really huge we have around 20k nodes"}, {"start": 1746.52, "end": 1754.0, "text": " will have 60 of these labels and but we'll we'll also be using the structural"}, {"start": 1754.0, "end": 1758.04, "text": " information so the connectivity and representations from different nodes but"}, {"start": 1758.04, "end": 1763.36, "text": " we won't be using their labels so then in the test time we'll try and predict"}, {"start": 1763.36, "end": 1769.48, "text": " what this once we train this thing we'll try and predict what the label of all of"}, {"start": 1769.48, "end": 1773.72, "text": " these other nodes are and that's transactive learning and I felt like"}, {"start": 1773.72, "end": 1776.92, "text": " explaining this a bit better because this was a new concept for me as well I"}, {"start": 1776.92, "end": 1785.6, "text": " wasn't familiar with this so yeah it's interesting anyways what's interesting"}, {"start": 1785.6, "end": 1793.3999999999999, "text": " is that PP PP PP I has several labels per node whereas all of these others"}, {"start": 1793.3999999999999, "end": 1803.52, "text": " have a single label per node and let's see what the results are before that"}, {"start": 1803.52, "end": 1808.84, "text": " just one more thing so I mentioned calculating those attention weights so"}, {"start": 1808.84, "end": 1813.76, "text": " what they additionally do is they do a dropout on those attention weights and"}, {"start": 1813.76, "end": 1817.96, "text": " some of those will get pulled down to zero which means you basically end up"}, {"start": 1817.96, "end": 1822.92, "text": " stochastically sampling the neighborhood so we applied dropout to normalize"}, {"start": 1822.92, "end": 1826.92, "text": " attention coefficients critically this means that at each training iteration"}, {"start": 1826.92, "end": 1832.12, "text": " each node is exposed to a stochastically sampled neighborhood so that's one one"}, {"start": 1832.12, "end": 1835.96, "text": " more detail that's interesting and the same thing is applied in transformer so"}, {"start": 1835.96, "end": 1843.64, "text": " again a parallel there and finally let's see what the results look like so"}, {"start": 1843.64, "end": 1850.3200000000002, "text": " they tested their method against various baselines and so this table here is"}, {"start": 1850.3200000000002, "end": 1855.5200000000002, "text": " about transactive results and this one is about inductive results where so"}, {"start": 1855.5200000000002, "end": 1860.88, "text": " inductive if I haven't mentioned it so we have training graphs so we train the"}, {"start": 1860.88, "end": 1864.8400000000001, "text": " network on a bunch of graphs and then we have a separate like testing graphs"}, {"start": 1864.8400000000001, "end": 1871.88, "text": " where we test our model our pre trained get model so that's the usual thing you"}, {"start": 1871.88, "end": 1878.96, "text": " see all around NLP and computer vision world so some of the baselines they they"}, {"start": 1878.96, "end": 1886.72, "text": " use for for the transactive datasets are basic multi-layer perceptron like label"}, {"start": 1886.72, "end": 1892.0400000000002, "text": " propagation algorithm deep walk this is a graph embedding method really really"}, {"start": 1892.0400000000002, "end": 1896.5600000000002, "text": " interesting one where they use random walks and approach similar to if you're"}, {"start": 1896.56, "end": 1901.9199999999998, "text": " familiar with vertebrate they use this skip gram model to train to train this"}, {"start": 1901.9199999999998, "end": 1910.84, "text": " model planetoid again uses similar to deep walk uses semi supervised learning"}, {"start": 1910.84, "end": 1916.52, "text": " whereas deep walk only uses unsupervised learning and then you have Chabishov"}, {"start": 1916.52, "end": 1922.32, "text": " which is one of those spectral methods where although they they improved it"}, {"start": 1922.32, "end": 1928.52, "text": " like the compute efficiency because they just do some like polynomial expansion"}, {"start": 1928.52, "end": 1935.82, "text": " of the laplacian and that saves them some compute GCN is a famous model by"}, {"start": 1935.82, "end": 1941.8, "text": " Thomas Kipf and it's basically you can maybe even treat it as a special case of"}, {"start": 1941.8, "end": 1947.24, "text": " get where the weights are the same it's similar it's not the same but it's in a"}, {"start": 1947.24, "end": 1953.72, "text": " way it's similar and then Monette is nice paper where they generalized all of"}, {"start": 1953.72, "end": 1960.16, "text": " these methods can be actually be treated as a special case of Monette so finally"}, {"start": 1960.16, "end": 1966.4, "text": " the results and yeah one more thing GCN 64 is just they optimize GCN so that"}, {"start": 1966.4, "end": 1972.52, "text": " it's the most fair comparison and they tuned the hyper params and these are the"}, {"start": 1972.52, "end": 1979.52, "text": " results they get so get achieves the state-of-the-art on Quora as well as on"}, {"start": 1979.52, "end": 1986.48, "text": " sites here it matches the state-of-the-art on PubMed and although"}, {"start": 1986.48, "end": 1990.56, "text": " these results are like clearly show that get is better than all of these"}, {"start": 1990.56, "end": 1994.84, "text": " previous baselines in 2020 there was this paper that showed that these"}, {"start": 1994.84, "end": 1999.76, "text": " benchmarks we should question like their validity because they are really small"}, {"start": 1999.76, "end": 2004.6, "text": " and the model can easily overfit and it's not easy to compare now in 2020"}, {"start": 2004.6, "end": 2010.2, "text": " especially different gene and models and we are we are we are actually as a"}, {"start": 2010.2, "end": 2015.52, "text": " community like looking for for a new and better data sets where we can evaluate"}, {"start": 2015.52, "end": 2024.0, "text": " these gene ends results on inductive learning data set is the following so"}, {"start": 2024.0, "end": 2028.76, "text": " they they took as the baselines random again multilayer perceptron and this"}, {"start": 2028.76, "end": 2033.28, "text": " graph sage method which is similar to GCN except that it does a uniform"}, {"start": 2033.28, "end": 2038.96, "text": " sampling of the neighborhood and thus they they showed that it can be I can be"}, {"start": 2038.96, "end": 2044.84, "text": " applied to much larger like a social network like size graphs with billions"}, {"start": 2044.84, "end": 2050.44, "text": " of nodes and they have just a different ways of accumulating the neighborhoods"}, {"start": 2050.44, "end": 2057.84, "text": " they are using max pooling LSTM even and then just simple mean element-wise mean"}, {"start": 2057.84, "end": 2063.48, "text": " aggregation etc so yeah I won't get into a lot of details about these methods if"}, {"start": 2063.48, "end": 2067.6800000000003, "text": " you're familiar with them this will maybe be a nice recap and again they"}, {"start": 2067.6800000000003, "end": 2076.6000000000004, "text": " showed that we get improvements with get on this desk as well so they they state"}, {"start": 2076.6000000000004, "end": 2080.1600000000003, "text": " here that larger predictive power can be leveraged by observing the entire"}, {"start": 2080.1600000000003, "end": 2084.6400000000003, "text": " neighborhood so the thing is with with graph sage basically so if you have a"}, {"start": 2084.64, "end": 2089.3599999999997, "text": " huge neighborhood I'll denote it like a like a curve here and this is the second"}, {"start": 2089.3599999999997, "end": 2096.24, "text": " hop neighborhood so what the what GNN does is it basically attends to every"}, {"start": 2096.24, "end": 2102.64, "text": " single node in the one hop neighborhood whereas graph sage will actually just"}, {"start": 2102.64, "end": 2108.92, "text": " take a sub sample randomly sub sample these neighbors in the first layer and"}, {"start": 2108.92, "end": 2115.2000000000003, "text": " then repeat that in the second layer so yeah it's just that's that's the the"}, {"start": 2115.2000000000003, "end": 2121.0, "text": " hypothesis that that's the reason why I get this better although that does"}, {"start": 2121.0, "end": 2127.08, "text": " imply a greater unnecessary compute but that's the trade-off and yep it depends"}, {"start": 2127.08, "end": 2132.88, "text": " on your application so that was it there's just one more interesting chart"}, {"start": 2132.88, "end": 2138.0, "text": " here and this one I just want to quickly explain what this is basically once you"}, {"start": 2138.0, "end": 2144.72, "text": " pre-train the get on the Quora data set what you do is the following so let me"}, {"start": 2144.72, "end": 2151.36, "text": " let me depict the graph initial graph like like this circle we have the first"}, {"start": 2151.36, "end": 2160.32, "text": " get layer so this is get layer number one outcomes like the modified version"}, {"start": 2160.32, "end": 2165.48, "text": " of the graph representations and then there is one more layer and then we do"}, {"start": 2165.48, "end": 2170.16, "text": " the soft maxes and stuff so if we take the representations out of this layer"}, {"start": 2170.16, "end": 2175.28, "text": " and we apply this thing this dimensionality reduction method called"}, {"start": 2175.28, "end": 2181.76, "text": " t-sne that was introduced by Hinton and his collaborators we basically project"}, {"start": 2181.76, "end": 2189.72, "text": " those those vectors into 2d space and we get this and because Quora let me just"}, {"start": 2189.72, "end": 2196.6, "text": " jump to the table above because Quora had seven classes as you can see here"}, {"start": 2196.6, "end": 2203.8399999999997, "text": " and around 2,700 notes that's why we get seven different colors here and you can"}, {"start": 2203.8399999999997, "end": 2209.08, "text": " see that the first get layer learns how to nicely separate and cluster similar"}, {"start": 2209.08, "end": 2216.2799999999997, "text": " similar classes so it's pretty easy to later learn some classifier which would"}, {"start": 2216.28, "end": 2223.6800000000003, "text": " learn how to separate all of these and have a nice predictive generalization so"}, {"start": 2223.6800000000003, "end": 2231.0, "text": " that was pretty much it those are just some references so if you found this"}, {"start": 2231.0, "end": 2238.5600000000004, "text": " video useful click that subscribe button and also consider clicking the bell icon"}, {"start": 2238.5600000000004, "end": 2243.48, "text": " to get notified when they upload a new video if you'd love me to create more of"}, {"start": 2243.48, "end": 2247.32, "text": " these videos please write it down in the comment section I'm just starting"}, {"start": 2247.32, "end": 2252.72, "text": " reviewing these papers and hopefully you found this useful so anyways until next"}, {"start": 2252.72, "end": 2275.8399999999997, "text": " time keep learning deep"}]