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

In this video I do a deep dive into the graph convolutional networks paper!

It's currently the most cited paper in the GNN literature at the time of making this video.

You'll learn about:
✔️ All the nitty-gritty details behind GCN
✔️ 3 different perspectives (spectral, WL, MPNN)

▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 
✅ GCN paper: https://arxiv.org/abs/1609.02907
✅ T.Kipf's awesome website: https://tkipf.github.io/graph-convolutional-networks/
✅ M.Bronstein's blog on GNN depth: https://towardsdatascience.com/do-we-need-deep-graph-neural-networks-be62d3ec5c59
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 

⌚️ Timetable: 

00:00 Intro to GCNs
01:00 Graph Laplacian regularization methods
06:00 GCN method (in-depth explanation)
12:40 Vectorized form explanation
17:05 Spectral methods (the motivation behind GCNs)
29:20 Visualizing GCN hidden features (t-SNE) 
30:17 Explanation of semi-supervised learning process
32:07 Graph embedding methods, results
34:12 Different variations of GCN
36:30 Speed benchmarking & limitations
39:30 Weisfeiler-Lehman perspective (GCN vs GIN)
44:25 GAT perspective, consequences of WL
46:45 GNN depth 

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

#graphconvolutionalnetwork #graphs #deeplearning
 What's up? In this video I'm continuing with a series on graph neural networks and I'm going to cover the semi-supervised classification with graph convolutional networks or GCNs for short. That's the most cited paper in the GNN literature and it was published by Thomas Kipf and Max Welling. So basically this paper can be looked at from three different perspectives. So the one they showed here in the beginning of the paper, which I'll briefly explain, is the spectral. So just considering their method as a special case as an approximation to spectral graph methods. The second perspective you can take is considering this as a generalized Weiss-Vallemann algorithm. And the third approach is basically just treating this as a specific case of a message passing neural network or like maybe even a get graph attention network, which was the paper I covered in my last video. So I'm just going to before I jump into explaining the method and the spectral perspective, I'm going to just tell you about these explicit graph laplacian regularization methods. So previously before GCN came and those spectral methods came, we mostly had like two classes of algorithms. We had on one side the graph embedding algorithms such as DeepWalk, such as Planetoid, etc. And on the other side we had these methods that did semi-supervised learning using these explicit graph laplacians. So let me just show you what this regularization term does. So basically if you take a look at the semi-supervised loss here, we have the supervised portion, the L0, and we have this regularization. So and you can see here how it looks like. So basically what it does is it enforces the nodes which are connected to have the same label or similar label. So it just smoothens out the labels. And there's just a hypothesis, there's just a prior, the bias this method has. It wants to make that the locally connected nodes have the same label, which is something that not, that might not be a good thing to do in all in all of the problems, but sometimes may be a good idea as well. So they say here the formulation of equation one relies on the assumption that connected nodes in the graph are likely to share the same label. This assumption, however, might restrict modeling capacity as graph edges need not necessarily encode node similarity, but could contain additional information. So GCNs showed later, we'll see the results, that they outperformed all of these baselines. And it's much better idea to just let the neural network learn from the features and from the graph structure than by just encoding this bias into the model. So what this thing does, and I'm going to draw a simple graph here because we'll need the adjacency matrices and all the terminology later. So let me just draw a simple toy graph here and do some simple connections like this. And this may be node number one, node number two, three, and finally four. So how the adjacency matrix looks like is the following. So that's an important concept and I'm going to repeat it even though I covered it in my last video. So basically what it does, it just represents the connection pattern of the graph. So we have zero here because node one doesn't connect itself, it doesn't have a self-connection, and we have ones here because it connects to all of the other nodes. And the other nodes just connect to node number one, so we'll have ones here and we'll have zeros elsewhere. So basically now what this equation does here is you just iterate through this adjacency matrix and you take the corresponding labels and you just subtract them and you square them. So basically that means if we go through the row number one, we'll basically have, we'll take this one and let's say for the sake of argument this one has the label two, node one has label one, node three has maybe label three, and this one also has label two. So what we'll do here is we'll take, because we have, so this is node number one, this is node number two, we have one here so that means it will get included into this sum and we'll just take the label. So the label from this node is two, so we take two, we subtract one, and we square it up. And we repeat that the same procedure for wherever we have one or wherever we have a connection in the adjacency matrix. So basically we'll have label three here, we'll take three, minus one, and we'll square it up. And again we'll have two here, minus one, and we'll square it up. And we can see that none of these goes to zero and that's what this graph laplacian regularization term enforces the method to do. So in order for this to get to zero all of these labels should be changed to basically to one because that's what this node has. So that's it in a nutshell. So again f is just a function that maps the feature vectors that are associated with every node and just gives us the class. And we want those to be similar and smooth. So basically this regularization term won't allow the method to assign label 10, for example, to node number three if we assume we have 10 classes. So that's it in a nutshell. So now I'm going to first cover how the GCM works because it's better to have a clear mental picture of how it works before we go into the spectral perspective. So this is how the equation two, how the GCM works. So we have this constant term which won't change during the propagation because it contains the adjacency matrix with added self connections which is the tilde term here, the tilde symbol, and then we have degree matrices which also contain self connections and those are just raised to the power of minus 1 half, which I'll briefly explain what that means in a sec. And then we have h which is just like a matrix of feature vectors for every single node and we have w which is just the linear projection layer. And again for the sake of easier understanding this part I'll just draw this graph. So I'll take the same example as before. So we have a graph, we have some connections like this one, and now what we do is the following. So we again have the matrix, adjacency matrix A, and so we had like the pattern was like this, we had ones here because node one connects to both nodes two, three, and four, hence the ones here, and then we have ones here because node number two connects only to to node number one, and we have zeros elsewhere. So now in order to make this like the tilde version we just need to add an identity matrix here which basically just adds the self connections. We'll have ones here, we'll have ones here, we'll have ones along the diagonal pretty much. And what this does is basically assumes we have self connections on every single node. So once we have this matrix A tilde we need to normalize it and we do that by using these degree tilde minus one half terms. So what does this represent? What does this mean? Basically this degree tilde matrix just does the summation row wise along this A tilde matrix. So we'll have a diagonal matrix which contains four here because we when we sum up we'll get four four here and that's what it means is basically this is a degree. We have four connections going to this node number one. That's why we have four here. Then we have two, two, and two because all the other nodes have only two connections. Okay so the next step is just to inverse it and do a square root. So basically what we end up doing once we once we multiply D tilde raised to the minus one half times A tilde and we do the same thing here we basically normalize all of these ones with this term. With one over square root of DI times DJ. Now what DI means is it's basically the degree of a node I and DJ is degree of node J. So basically this particular node which now has one corresponds to so that's a connection between node one and node two right? So that's this connection and because this node has degree of two that's the DJ and with this one has degree four we'll basically just normalize this term so this one here with one over square root four times two and that's square root of eight whatever that is. So that's what we do and that's how we normalize this matrix. And now all of this will hopefully fit together in a moment so I just wanted to explain how that matrix is calculated. So how the process looks like in the GCI method is the following. So all of these nodes have associated a feature vector and for the sake of being less abstract let me say this one has thousand four hundred thirty three features and for example this number is not like random. Quora data set the citation network which this paper also used as a benchmark has this many features per node where every node represents a paper in a citation graph. So basically all of these nodes will have this feature vector and high level what the method does is it first projects these these feature vectors using this matrix W which we can see here projects the projects I mean to some lower usually lower dimensional space. So it will basically be a fully connected feed-forward layer without the activation at this point or you can just treat it as an identity activation which is the same thing. And so basically this one will maybe have 64 dimensions and once we do this for every single node in the graph we end up having so that's this part and now what this part does and I'll explain why it basically just accumulates or aggregates which is a term used in the graph literature these features and it just scales them using these square root over di dj things and you add them up and you get the new representation. So basically this node one will accumulate all of the vectors because all of them connect all of these nodes connect to it so it will have so its final representation will contain some portions of all of these other feature vectors. On the other hand if we take node two it will have only the feature vector that came from itself and the came from node one. So that's the difference. So you just basically take the one hop neighborhood you just aggregate those projected features you sum them up but before you sum you use those like scale these scaling factors and that's it. You basically only apply after you do that you apply some nonlinear differentiable activation functions such as ReLU and I assume everybody knows what ReLU is but I'm gonna just draw it for the sake of argument so basically it's like a zero here and pretty much y equals to x in this part. So if you still can't associate this equation with the process I just described I'm going to go once more and explaining the exact process that goes on in this vectorized form. So I want to explain concepts I try and do it as intuitive as possible but like these all of these equations are usually vectorized and which makes them less maybe less intuitive but once you kind of get the hang of it it becomes really easy. So let me try and explain every single matrix. So H matrix is basically as I said you just we just stack horizontally all of these feature vectors. So because we have n nodes this H matrix in the zeroth level so initially it will just be basically n times whatever the dimension here is and that's we said 1433. So this one will be so again it will be n times 1433 that's the size. Then we have this w matrix and w projects from 1433 into we said I took like as an example I took 64. So it will be a matrix that has the same dimension here will be here so we'll have pretty much 1433 times 64. So we'll have 64 dimensions here. So basically this corresponds to this one and once you multiply these matrices so H times w we'll end up with a new matrix which contains the projected feature vectors for every single vector for every single node in the in the in the graph. So we'll end up with a new matrix some intermediate matrix that has a dimension n times this times 64 and those are these small vectors I draw here and here etc. So hopefully that part is so far so good. So that's this part okay and finally we need to multiply by this by this normal by this normalized adjacency matrix and let's let's figure out that part. So now we have so let me take this example we already have concrete numbers here I just don't have these 1 over di dj parts but you can just imagine they are there and what we do so I'm going to redraw it again here just to make it a bit more clear. So we have ones here we have ones here and because of the self connections we have ones along the diagonal as well everything else is zero. So I just stack four nodes because n equals to 4 here right in our small graph we have only four nodes. So we stack up those 64 dimensional vectors and I won't draw every single element because they are initially just some random values. So basically what we do is the following so the first node as you can see because it has all ones it will basically take into account every single projected vector and that's what I previously explained so because it's connected to everything it will take all of the feature vectors the projected ones and it will just add them up and we have those terms as I mentioned which I want whatever like square root whatever corresponds to the degrees of those nodes. So that's the case for the node 1 but let's take for example node 2. So node 2 only has one here and one here and it has zeros here that means once you multiply this row with this matrix you'll just basically take these two feature vectors and that corresponds to the thing I mentioned previously and that's just you just take this feature vector and you just take this feature vector and you add them up and you use those scales again and that's that's why the equation works and it's basically does the same thing as what I just intuitively explained here using the drawing. Hopefully this this makes sense and I went into a lot of details please let me know if this was too too detailed painfully detailed or it was just right so appreciate the feedback. Now the reason they use these coefficients here to to to normalize the adjacency matrix values is because if we didn't do that we'd have a problem with exploding or vanishing gradients which can nicely be seen through this spectral prism which I'm going to explain right now. So basically if you're familiar with eigen decompositions what those scaling coefficients do is basically they make sure that the largest eigenvalue of our matrix is equal to 1. So basically they make sure that the range of eigenvalues is between 0 and 1 and by just continually applying that matrix we won't have exploding or vanishing gradients. So that's that's that's the trick. So this part by just constantly multiplying by this term if the eigenvalue range is in a good in a good range basically we won't have the problem I just mentioned with vanishing or exploding gradients. So because the the spectral part is really complicated it deserves a video for itself I'm just going to briefly explain the main ideas here and hopefully if you think that that could be useful I'll cover the specs some of the spectral methods in one of the next videos although they are not as popular as these spatial methods where GCN is one representative, GET is another representative, etc. GraphSAGE, etc. So how it works how the spectral graph convolutional method works in a nutshell is the following. So you take the Laplacian matrix which is basically the Green matrix and you subtract the adjacency matrix and you find the eigen decomposition of this matrix and you get eigenvectors and you get eigenvalues. So once you stack up those eigenvectors in a matrix you get these U matrices and what you do is you take the signal on your graph X so what's the signal? So just for the just for the sake of being of being clear so basically you take these feature vectors you take maybe first feature from every single feature vector and you can treat those as as a signal. So basically imagine we have we just align these nodes linearly and we take those first features from all of the feature vectors and maybe this one has value like this maybe this has a bit bigger value and you basically can treat this if I interpolate some random interpolation you can treat it as a signal a discretized signal on the graph. So what we do here in the spectral method is we project that signal into the into the new basis defined by the laplacian eigenvectors and those are contained in U. Then we have this this is what is learned in these methods so we don't learn the W matrix as previously in GCN we'll learn this filter G theta G sub theta and now the problem with this is and it says here it's computationally expensive as multiplication with the eigenvector matrix is O and so big O notation n square so basically because this matrix U is m times n and X is n times 1 because we remember we just took the like first feature or whatever like just one feature instead of the whole feature fully blown X matrix which has all of the features so basically that's why we have a computational cost of n squared and that's not the only problem the second problem is that doing the eigen decomposition of the laplacian is super expensive it's I think it depends on the like there are more optimal methods depending on certain like details but like O of n squared n cubed is probably a good estimate of the complexity and so that's super expensive so then there were so Hammond and his collaborators suggested that we can just instead of learning all of the n parameters here so where n is the side of the graph which can be in the size of billions if we're dealing dealing with for example Facebook graph or Pinterest wherever and basically you can we can treat this we can just compute like a like a K polynomial and using using Chebyshev polynomial and we can just use this approximation now I won't get into details how this approximation came to be there will be a separate video but like just trust me on this one and it can be shown that instead of using so this matrix here lambda contains eigenvalues we can ditch computing the eigen decomposition and we can save those n cubed computations and we can just do a Chebyshev polynomial using the this this laplacian matrix instead instead of using the eigenvalues matrix so Chebyshev you can see a simple recursion again won't get into much details it's really simple recursion we start with one and X and this is how you combine them to get the next polynomial terms and you basically end up having so this is how we do convolution spectral convolution now so we just have K terms here we have K parameters so these are scalars we just learned these and it's much more efficient this time so the thing with this this equation here approximation is that it's in contrast to the pure spectral methods like this one this one is K localized and that means that pretty much means that all of the if we have a graph and you take a single node it will only capture the features from its k-hop neighborhood so meaning the the neighbors which are further away are only our K edges far far off from from this target node so why that is is because if you know something about adjacency matrix properties if you just raise it to the power of K what you end up doing is the term ij in this matrix will tell you how many paths there are between nodes i and j like k length paths so basically that's that's the reason why why why we have a k-hop neighborhood here now again if you didn't understand this detail it's totally fine that's not the point of this video so now what GCN does is basically it starts from this approximation so this is a an approximation of the fully blown spectral method and it does the following it just says let's just treat let's just take a look at one hop neighborhoods we don't care about k-hop neighborhoods we want to make we set k to 1 so no so as they say here now imagine we will limit it the layer wise convolution operation to k1 so that's the first approximation they do and so they say it here nicely we intuitively expect that such a model can alleviate the problem of overfitting on local neighborhood structures for graphs with very wide node degree distributions such as social networks citation networks knowledge graphs and many other real world graph datasets so that's the explanation the the argument why they set k to 1 basically for certain graphs like citation networks which they are using as benchmarks in this paper like Cora sites here etc they can be they are basically something called small world networks and this approximation makes sense the second approximation they do is they say here we further approximate lambda max so the maximum eigenvalue to be approximately 2 as we can expect that neural network parameters will adapt to this change in scale during training okay so basically once you take those so k equals to 1 and lambda max equals to 2 you basically going from this equation you end up with with this one and basically now you can just if you take a look at what well lambda y y l minus identity here is because they're using they're having a Chebyshev polynomial of this scaled laplacian so basically what that means is so if we expand this polynomial we'll end up with first term will be I the second one will be this L tilde then we'll have 2 L tilde squared minus I etc depending how many how big the K is so if we if we consider L max to be 2 we'll ditch this term and we'll end up with L minus identity and that's what we get here so that's the L minus identity part and now finally there is one more approximation they do and that's constraining these two to be the same thing so theta 0 and theta 1 let's read them to be the same parameter and you can extract it and basically you get this equation and the last trick they do because if you take a look at this matrix the range of eigenvalues will be from 0 to 2 which means if we continually keep on multiplying features X projected features we have theta here times this matrix will end up increasing the values or the consequently the gradients will either explode or diminish and that's something we want to avoid and that's why they do this normalization trick and what they basically do is they add up self connections and we saw that when I was explaining the method itself so basically that's it once you once you just swap this part with this part you end up with the final method and that's the the form I previously I previously explained so that the good thing about this method it has a complexity that's proportional to the number of edges in the graph and not to do like a number of nodes like raise the power of three for like spectral spectral methods which was super super compute intensive so yeah it was a it was a mouthful there is a lot of details and you need to read a couple of papers to understand every single part so for example why this approximation works why we can why we can swap eigenvalues with laplacians here and yeah that's probably the hardest part then you can just this is simple thing this one is also conceptually simple and a couple more steps in your where the final stage but that's why I said that maybe not looking at at the GCN through this spectral prism but by looking at GCN maybe as a special case of get method or as a message passing network in general is much more like feels more natural than than treating it as a special as a spectral method because it's not spectral method we don't have to compute it's not like the final expression doesn't have to do anything with spectrum we don't have to compete to compute eigenvalues you don't have to compute eigenvectors so is that it was just motivated by by the spectral methods but it's not a spectral method itself so just avoid being confused there the hardest part we covered the method we covered how it was motivated by the spectral methods and we saw how the explicit graph laplacian regularization works so now let me just walk you through the rest of the paper a couple of more things details so once you pre train GCN with two layers on the core data set and you extract the hidden layers the hidden features you can project them into 2d space using t-sne and you get this and if you remember if you if you watch my previous video on get you can see that get maybe had a bit better separation between a Cora classes than GCN but once you actually once you and you can also verify that because it had had better accuracy than GCN but I'll get to those results in a bit but basically you can you can see that get actually has on these types of networks on citation networks the attention coefficients it used for the neighborhood are pretty similar and kind of approximate GCN although it's more more expressive and thus has a better results okay so again semi-supervised learning pretty simpler simple thing and I explained that in get but like for the sake of being complete here you just do cross entropy so you basically have a huge network and you just take for every single class and Cora has like seven classes you only take 20 notes whose labels you're going to use you don't use other labels you do use the features but you don't use the labels and finally once you get to the final layer the feature vectors now have the number of classes like seven for Cora and you'll just do you'll just do cross entropy loss on on those on those on those values and that's how you train these models so basically for the sake of being clear so what would we do again let's say this is Cora so we start with thousand four hundred thirty three we do the projection we do the aggregation so in the hidden layer we'll have maybe 64 features and again we do apply in our layer and because Cora has seven classes the final feature vectors will only have seven features and we do softmax so we end up with a probability distribution and we just take a look where the true classes and we do the cross entropy so if it's maybe 0.4 the loss will be log 0.4 and just a minus there and that means this needs to go to one for the ground truth class in order for the loss to go to zero which makes sense and you just do gradient based learning and they used Adam for GCN and that's it in a nutshell and again they visualize these features here let's see a couple more things in this paper the next thing is so I already mentioned we have previously to GCN and the spectral methods we have we had two broad categories the ones that use explicit graph laplation and the one that used a graph embedding approach so the graph embedding approach basically creates random walks it's similar to vertebrae if you're familiar with NLP yeah it's basically the same idea just apply to graphs you treat random walks on graphs as sentences and you basically train your embeddings such that they are such that the ones that appear close to each other attend to have similar embeddings in a nutshell so I mentioned previously they used three citation networks sites here core and PubMed there's this knowledge graph as benchmarks and yeah I mentioned that Cora has thousand so this we're using this example as a as a as a as on the fly example throughout this video and basically you can see some statistics related to that like data set and it has seven classes as I already mentioned so and I mentioned they're using only 20 labels per class so so that means so you have so you have the core has 2,700 nodes but you only use for hundred forty to train the the GCN method okay they also have some random graphs I'll explain those briefly why they mentioned those ones okay so here are the results you can basically they compared against these these methods used at explicit graph laplation regularization deep walk and planetoid our graph embedding methods and here is GCN and we can see on every single data set they have a significant improvement compared to the baselines and yeah that's nice okay finally they compared different methods and this is the reason I had to go into a bit more details in the spectral section part so basically they compare the Chebyshev so the one that the the approximation of the full spectral method and they tried using K2 and K3 so that means they're using K 2 hop and 3 hop neighborhoods and you can see the results are worse than GCN method and the renormalization trick is the official the final GCN method you can see so here going from top to bottom are the approximation we were making so here we just set K to 1 then we we we constrain these two tatas to be the same here in the single parameter row and we can see that all of the results are worse than by using the final the final GCN version they also compared against the first order term only so they ditch this part and they just use the the first order term and we also get worse results and finally the reason I highlighted MLP here is that it doesn't use the graph structure and you can see that the the performance the the accuracy is far like lower than all of the other methods so that's the reason so even so so basically it's really important to use the the graph structure because it contains a lot of information so how they train the MLP I suppose is so again you have you have the graph and you have features associated with them and you just basically independently apply the MLP here so this is maybe the first layer and then you have the second layer and you end up with seven classes here and you just take those four hundred hundred forty notes sorry to to basically train this MLP and you basically repeat the same so these are the same weights these are the shared weights you apply them to the first feature vector then you go to the second one blah blah blah you apply the the the cross entropy loss and you train the MLP and that's and that's so so you can see in this process it's not using the connectivity pattern so it's ignoring the connectivity pattern altogether okay let's continue and finish up wrap up this paper there are a couple more things I want to mention the first thing is and this is interesting so so basically you can see the training times here on the y-axis we have seconds per epoch and on the x-axis we have number of edges and this is where those random graphs can come into place so what they did is they just create n notes and they just take two n edges and they randomly uniformly just connect all of these notes and that's the graphs they were using and they just use a featureless approach where basically you just have a one hot vector or the adjacency matrix is pretty much the identity matrix and they use these graphs to just a benchmark like the test the speed of these their models and we can see that as we go to a huge number of edges the speed is still around one to ten seconds on CPU and GPU and compare that transformers which need days upon days of like huge machines to train them and but once you think about it it's not that interesting because we only have a W matrix in the case of GCN to train and that's a small number of parameters although as the number of nodes gets bigger the computation also gets bigger but using sparse dense matrix multiplication and some methods you can you can speed it up but it's interesting it's really it's really fast to train these networks and that's that's cool okay let's go and see a couple more things so I mentioned memory requirement and so I'm actually currently implementing the graph attention network and I'll open source it in a couple of weeks probably but like the the hardest part I found like implementing these networks is how to efficiently implement the layer and that's that's pretty much everything because you want to there is all of these like sparse formats and matrix sparse dense matrix multiplications happening and how what's the best way to represent your edges whether using edge index or just using the plain old sparse adjacency matrix and then finding some suitable format to represent it anyways I don't want to get into too much detail just keep that in mind that pretty much the hard hardest part here is to like efficiently implement these methods yeah they see here our framework currently does not naturally support edge features and is limited to undirected graphs weighted or unweighted that's that's something to keep in mind because both Cora and all of these benchmarks they used they don't have any edge features they just have like simple binary connections okay that was the the main part of paper I mentioned in the beginning of this video that I have three perspectives we can treat this so we can we can look at this GCN paper through three different perspectives the one is spectral method perspective and now let me show you the second one the Weiss-Feyler-Lehmann algorithm so basically WL algorithm or Weiss-Feyler-Lehmann specifically the 1D case of this algorithm what it does it's a simple isomorphism graph isomorphism test what that means is basically you have two graphs so graph G1 and you take second graph graph G2 and you pass it in into this test and if the if the final something called node colorings are the same no if they're different then you're most you're sure that these two graphs are not isomorphic if they're the same you're still not completely sure because there are special special cases where Weiss-Feyler-Lehmann like fails but like you're pretty certain that those two graphs are isomorphic and what isomorphic means is basically you those are just two same graphs but just have different maybe different labeling and if you find some different like permutation of labels you can see that those two graphs are the same and there are some really nice examples I'll show it here on the screen and you can see those two graphs are are the same even though they look differently like at the first glance so that's the idea with the Weiss-Feyler-Lehmann algorithm and now you can treat GCN as a pretty much as a generalized version of of of this Weiss-Feyler-Lehmann algorithm and with a disclaimer I'll in a couple of seconds explain why that's not completely true but let's for the sake of argument now let's play that game so this is how the algorithm looks like so we start with initial node coloring and you can treat maybe this the same as so we have those features the same as we use so far and basically the algorithm stops once those features stabilize and it's basically the same structure so we have repeat until is basically going through the layers of our GCN and we for every single node what we do is we aggregate the features or the colorings in this in this case that we aggregate them and we hash them and that's what's what our updated representation looks like and if you think about it it's really similar to what we have with GCN so basically we aggregate across the neighborhood again and we have these C ij's which I've mentioned a lot of times already and that equals to one over square root di dj where those are degrees of those particular notes and if you take a look at it it's the same format you can treat just the hash part is maybe the non-linearity and these projections and scaling but it's it has a similar structure and they say here this loosely speaking and it's really important to to highlight the loosely speaking part because it's not completely true and you'll see in a minute allows us to interpret our GCN model as a differentiable and parameterized generalization of the one-dimensional Weissweiler-Lehmann algorithm on graphs and now the disclaimer so basically later this paper called graph isomorphism networks appeared and it showed that GCN is not quite there so they say here this is just a snippet from the paper so we will see that these GNN variants get confused by surprisingly simple graphs and are less powerful than the WL device Weissweiler-Lehmann test nonetheless models with mean aggregators like GCN perform well for node classification tasks and we used exactly the node classification benchmarks in this paper so this paper used those benchmarks so that's why we couldn't notice I mean you this paper appear only later so it was hard for them to to compare but anyways they show that these gene GIN networks are more expressive than GCN's and more expressive that gets also so that's something to keep in mind I won't get into too much details but basically there are certain families of graphs which if you input them so you have graph one and you have graph two and they are different but once you pass them into GCN it would give it will give them the same node coloring which means GCN treats these two graphs the same like they are isomorphic but they're not they're different so GCN can fail on some on certain graph families as well as get but yeah that's something I thought it's worth mentioning just to keep connecting those dots across different papers finally so I mentioned the third perspective get perspective so basically can treat the GCN as a particular case of get where you have instead of learning those weights you just have them hard coded as this expression which I've mentioned multiple times already so that's about that's it and finally as a nice consequence of of this of the fact that you can treat this as a WL algorithm so they say here from the analogy with the WL we can understand that even an untrained GCN model with random weights can serve as powerful feature extractor for nodes in a graph so what we do here we just take these W matrices and we live them we leave them like a random and basically so this a hat is the term with the tilde mine raised to the power of minus one half etc suggest the constant term so we just apply three layers here three GCN layers and this is what we end up with so we have they showed here that if we take this correct correct karate club network so if you take this network and you just take a feature as approach meaning all of these nodes don't have some meaningful features they're just like the adjacency matrix is pretty much identity matrix and if you pass it through the untrained GCN it will still learn how to separate different classes so what it did is so basically the last layer of this GCN has only two so the node features have only two dimensions and thus they can easily be plotted on a 2d chart like here and you can see that clusters like this one which have the same labels also appear in the same part of the space in this 2d space here so that's interesting that means that GCN can without any training already have some discriminative power just because of the graph structure and finally once you start training this GCN the through layer GCN I just mentioned you can see it gets you in better separation and finally after 300 iterations the classes are clearly separated and that's that's awesome one more last thing is experimenting with depth so if you if you think about it all of the networks GCNs as I mentioned so far had either two or three layers so what's up what's up with that you know if you're familiar with computer vision you know that CNNs usually have bunch of layers like Resnets had I had 151 or more layers and basically here we'll use two or three so what's what's the thing so basically they showed here that and they've added these skip connections basically just adding the representations from the previous layer like this and this is the original equation so using these models they showed that after two or three layers we get to peak performance on the test and we don't need anything to go any further so and that's that's interesting and the the the explanation here you can you can search for it Michael Brunstein had a really nice blog wrote a nice blog about this and I'll just quickly summarize it so basically since grids are special graphs there certainly are examples of graphs on which depth helps it's just a quote from his blog and what that means is that pretty much you can treat image as a as a grid as a regular graph and we know that for images depth helps so that means there are certain classes of graphs where depth does help but here on these citation and knowledge graph graphs for some reason depth doesn't help and one of the explanation that Michael gave here is that one of the differences is that the letter letter are similar to small world networks with low diameter where one can reach any node from any other node in a few hops so you probably heard about this Facebook graph where at least I heard about it I'm not sure if the numbers are truly correct but like you can you can get to any single person on the graph on the Facebook graph by just in like six or seven hops so that means that the diameter of the of the Facebook graph is around seven I'm not sure if that's entirely correct but you get the point so it's so intricately connected that already after a couple of layers you've basically touched a lot of the neighborhoods neighborhood neighboring nodes and you don't need any more layers to to achieve better performance so that pretty much wraps it up hopefully you found this video useful I'm experimenting and I'm still figuring this out so if you have any feedback for me I really appreciate it I'll continue creating GNN videos throughout January and if you have any any requests please write them down in the comment section I'll try and maybe create some video depending on what you folks like suggest me if you like this video and if you found this channel useful please consider subscribing and click the bell icon to get notified when I upload a new video so that you can get my videos as soon as they get uploaded and until next time keep learning deep
[{"start": 0.0, "end": 4.92, "text": " What's up? In this video I'm continuing with a series on graph neural networks"}, {"start": 4.92, "end": 8.28, "text": " and I'm going to cover the semi-supervised classification with graph"}, {"start": 8.28, "end": 13.48, "text": " convolutional networks or GCNs for short. That's the most cited paper in the GNN"}, {"start": 13.48, "end": 19.400000000000002, "text": " literature and it was published by Thomas Kipf and Max Welling. So basically"}, {"start": 19.400000000000002, "end": 25.240000000000002, "text": " this paper can be looked at from three different perspectives. So the one"}, {"start": 25.24, "end": 30.52, "text": " they showed here in the beginning of the paper, which I'll briefly"}, {"start": 30.52, "end": 36.92, "text": " explain, is the spectral. So just considering their method as a special"}, {"start": 36.92, "end": 41.959999999999994, "text": " case as an approximation to spectral graph methods. The second perspective you"}, {"start": 41.959999999999994, "end": 47.36, "text": " can take is considering this as a generalized Weiss-Vallemann algorithm."}, {"start": 47.36, "end": 52.8, "text": " And the third approach is basically just treating this as a specific case of a"}, {"start": 52.8, "end": 56.599999999999994, "text": " message passing neural network or like maybe even a get graph attention"}, {"start": 56.599999999999994, "end": 62.519999999999996, "text": " network, which was the paper I covered in my last video. So I'm just going to"}, {"start": 62.519999999999996, "end": 68.52, "text": " before I jump into explaining the method and the spectral"}, {"start": 68.52, "end": 74.44, "text": " perspective, I'm going to just tell you about these explicit graph laplacian"}, {"start": 74.44, "end": 79.6, "text": " regularization methods. So previously before GCN came and those spectral"}, {"start": 79.6, "end": 84.39999999999999, "text": " methods came, we mostly had like two classes of algorithms. We had on"}, {"start": 84.39999999999999, "end": 88.39999999999999, "text": " one side the graph embedding algorithms such as DeepWalk, such as"}, {"start": 88.39999999999999, "end": 94.39999999999999, "text": " Planetoid, etc. And on the other side we had these methods that did"}, {"start": 94.39999999999999, "end": 99.6, "text": " semi-supervised learning using these explicit graph laplacians. So let me just"}, {"start": 99.6, "end": 106.44, "text": " show you what this regularization term does. So basically if you take a look at"}, {"start": 106.44, "end": 112.03999999999999, "text": " the semi-supervised loss here, we have the supervised portion, the L0, and we"}, {"start": 112.03999999999999, "end": 117.32, "text": " have this regularization. So and you can see here how it looks like. So basically"}, {"start": 117.32, "end": 123.92, "text": " what it does is it enforces the nodes which are connected to have the same"}, {"start": 123.92, "end": 128.8, "text": " label or similar label. So it just smoothens out the labels. And there's just a"}, {"start": 128.8, "end": 134.4, "text": " hypothesis, there's just a prior, the bias this method has. It wants to make that"}, {"start": 134.4, "end": 138.24, "text": " the locally connected nodes have the same label, which is something that not,"}, {"start": 138.24, "end": 142.68, "text": " that might not be a good thing to do in all in all of the problems, but sometimes"}, {"start": 142.68, "end": 146.94, "text": " may be a good idea as well. So they say here the formulation of equation one"}, {"start": 146.94, "end": 150.32, "text": " relies on the assumption that connected nodes in the graph are likely to share"}, {"start": 150.32, "end": 155.8, "text": " the same label. This assumption, however, might restrict modeling capacity as graph"}, {"start": 155.8, "end": 160.76, "text": " edges need not necessarily encode node similarity, but could contain additional"}, {"start": 160.76, "end": 165.48, "text": " information. So GCNs showed later, we'll see the results, that they outperformed"}, {"start": 165.48, "end": 169.56, "text": " all of these baselines. And it's much better idea to just let the neural"}, {"start": 169.56, "end": 173.95999999999998, "text": " network learn from the features and from the graph structure than by just"}, {"start": 173.95999999999998, "end": 181.2, "text": " encoding this bias into the model. So what this thing does, and I'm"}, {"start": 181.2, "end": 186.0, "text": " going to draw a simple graph here because we'll need the adjacency matrices"}, {"start": 186.0, "end": 194.12, "text": " and all the terminology later. So let me just draw a simple toy graph here and do"}, {"start": 194.12, "end": 200.08, "text": " some simple connections like this. And this may be node number one, node number"}, {"start": 200.08, "end": 206.64, "text": " two, three, and finally four. So how the adjacency matrix looks like is the"}, {"start": 206.64, "end": 211.08, "text": " following. So that's an important concept and I'm going to repeat it even though I"}, {"start": 211.08, "end": 217.68, "text": " covered it in my last video. So basically what it does, it just represents the"}, {"start": 217.68, "end": 224.04000000000002, "text": " connection pattern of the graph. So we have zero here because node one"}, {"start": 224.04000000000002, "end": 227.44, "text": " doesn't connect itself, it doesn't have a self-connection, and we have ones here"}, {"start": 227.44, "end": 231.84, "text": " because it connects to all of the other nodes. And the other nodes just connect"}, {"start": 231.84, "end": 238.0, "text": " to node number one, so we'll have ones here and we'll have zeros elsewhere. So"}, {"start": 238.0, "end": 243.56, "text": " basically now what this equation does here is you just iterate through this"}, {"start": 243.56, "end": 249.28, "text": " adjacency matrix and you take the corresponding labels and you just"}, {"start": 249.28, "end": 252.8, "text": " subtract them and you square them. So basically that means if we go through"}, {"start": 252.8, "end": 260.44, "text": " the row number one, we'll basically have, we'll take this one and"}, {"start": 260.44, "end": 266.6, "text": " let's say for the sake of argument this one has the label two, node one has label"}, {"start": 266.6, "end": 272.44, "text": " one, node three has maybe label three, and this one also has label two. So what"}, {"start": 272.44, "end": 277.72, "text": " we'll do here is we'll take, because we have, so this is node number one, this is"}, {"start": 277.72, "end": 283.28000000000003, "text": " node number two, we have one here so that means it will get included into this sum"}, {"start": 283.28000000000003, "end": 287.90000000000003, "text": " and we'll just take the label. So the label from this node is two, so we take"}, {"start": 287.90000000000003, "end": 294.88, "text": " two, we subtract one, and we square it up. And we repeat that the same procedure for"}, {"start": 294.88, "end": 299.71999999999997, "text": " wherever we have one or wherever we have a connection in the adjacency matrix. So"}, {"start": 299.71999999999997, "end": 306.52, "text": " basically we'll have label three here, we'll take three, minus one, and we'll"}, {"start": 306.52, "end": 314.32, "text": " square it up. And again we'll have two here, minus one, and we'll square it up."}, {"start": 314.32, "end": 320.64, "text": " And we can see that none of these goes to zero and that's what this graph"}, {"start": 320.64, "end": 325.8, "text": " laplacian regularization term enforces the method to do. So in order for this to"}, {"start": 325.8, "end": 333.36, "text": " get to zero all of these labels should be changed to basically to one"}, {"start": 333.36, "end": 339.2, "text": " because that's what this node has. So that's it in a nutshell. So again f is"}, {"start": 339.2, "end": 343.84, "text": " just a function that maps the feature vectors that are associated with every"}, {"start": 343.84, "end": 350.2, "text": " node and just gives us the class. And we want those to be similar and smooth. So"}, {"start": 350.2, "end": 356.12, "text": " basically this regularization term won't allow the method to"}, {"start": 356.12, "end": 361.03999999999996, "text": " assign label 10, for example, to node number three if we assume we have 10"}, {"start": 361.03999999999996, "end": 365.36, "text": " classes. So that's it in a nutshell. So now I'm going to first"}, {"start": 365.36, "end": 371.59999999999997, "text": " cover how the GCM works because it's better to have a clear mental"}, {"start": 371.59999999999997, "end": 375.64, "text": " picture of how it works before we go into the spectral"}, {"start": 375.64, "end": 381.64, "text": " perspective. So this is how the equation two, how the GCM works. So we"}, {"start": 381.64, "end": 388.4, "text": " have this constant term which won't change during the propagation because it"}, {"start": 388.4, "end": 393.0, "text": " contains the adjacency matrix with added self connections which is the tilde"}, {"start": 393.0, "end": 398.32, "text": " term here, the tilde symbol, and then we have degree matrices which also contain"}, {"start": 398.32, "end": 403.68, "text": " self connections and those are just raised to the power of minus 1 half, which"}, {"start": 403.68, "end": 409.32, "text": " I'll briefly explain what that means in a sec. And then we have h which is"}, {"start": 409.32, "end": 414.24, "text": " just like a matrix of feature vectors for every single node and we have w which"}, {"start": 414.24, "end": 418.5, "text": " is just the linear projection layer. And again for the sake of easier"}, {"start": 418.5, "end": 424.88, "text": " understanding this part I'll just draw this graph. So I'll take the"}, {"start": 424.88, "end": 430.84000000000003, "text": " same example as before. So we have a graph, we have some connections like this"}, {"start": 430.84, "end": 438.88, "text": " one, and now what we do is the following. So we again have the matrix, adjacency"}, {"start": 438.88, "end": 447.71999999999997, "text": " matrix A, and so we had like the pattern was like this, we had ones here because"}, {"start": 447.71999999999997, "end": 454.79999999999995, "text": " node one connects to both nodes two, three, and four, hence the ones here, and"}, {"start": 454.8, "end": 460.8, "text": " then we have ones here because node number two connects only to to node"}, {"start": 460.8, "end": 466.8, "text": " number one, and we have zeros elsewhere. So now in order to make this like the"}, {"start": 466.8, "end": 471.08000000000004, "text": " tilde version we just need to add an identity matrix here which basically"}, {"start": 471.08000000000004, "end": 475.6, "text": " just adds the self connections. We'll have ones here, we'll have ones here, we'll"}, {"start": 475.6, "end": 480.44, "text": " have ones along the diagonal pretty much. And what this does is basically assumes"}, {"start": 480.44, "end": 487.64, "text": " we have self connections on every single node. So once we have this matrix A tilde"}, {"start": 487.64, "end": 494.2, "text": " we need to normalize it and we do that by using these degree tilde"}, {"start": 494.2, "end": 501.12, "text": " minus one half terms. So what does this represent? What does this mean? Basically"}, {"start": 501.12, "end": 507.64, "text": " this degree tilde matrix just does the summation row wise along this A tilde"}, {"start": 507.64, "end": 512.48, "text": " matrix. So we'll have a diagonal matrix which contains four here because we when"}, {"start": 512.48, "end": 517.84, "text": " we sum up we'll get four four here and that's what it means is basically this"}, {"start": 517.84, "end": 522.1999999999999, "text": " is a degree. We have four connections going to this node number one. That's why"}, {"start": 522.1999999999999, "end": 528.96, "text": " we have four here. Then we have two, two, and two because all the other nodes have"}, {"start": 528.96, "end": 535.6, "text": " only two connections. Okay so the next step is just to inverse it and do a"}, {"start": 535.6, "end": 542.12, "text": " square root. So basically what we end up doing once we once we multiply D tilde"}, {"start": 542.12, "end": 549.12, "text": " raised to the minus one half times A tilde and we do the same thing here we"}, {"start": 549.12, "end": 559.2, "text": " basically normalize all of these ones with this term. With one over square root"}, {"start": 559.2, "end": 570.32, "text": " of DI times DJ. Now what DI means is it's basically the degree of a node I and DJ"}, {"start": 570.32, "end": 576.2800000000001, "text": " is degree of node J. So basically this particular node which now has one"}, {"start": 576.2800000000001, "end": 581.6400000000001, "text": " corresponds to so that's a connection between node one and node two right? So"}, {"start": 581.6400000000001, "end": 587.6400000000001, "text": " that's this connection and because this node has degree of two that's the DJ and"}, {"start": 587.64, "end": 592.56, "text": " with this one has degree four we'll basically just normalize this term so"}, {"start": 592.56, "end": 599.8, "text": " this one here with one over square root four times two and that's square root of"}, {"start": 599.8, "end": 604.1999999999999, "text": " eight whatever that is. So that's what we do and that's how we normalize this"}, {"start": 604.1999999999999, "end": 609.24, "text": " matrix. And now all of this will hopefully fit together in a moment so I"}, {"start": 609.24, "end": 614.3199999999999, "text": " just wanted to explain how that matrix is calculated. So how the process"}, {"start": 614.32, "end": 618.32, "text": " looks like in the GCI method is the following. So all of these nodes have"}, {"start": 618.32, "end": 623.24, "text": " associated a feature vector and for the sake of being less abstract let me say"}, {"start": 623.24, "end": 628.6800000000001, "text": " this one has thousand four hundred thirty three features and for example"}, {"start": 628.6800000000001, "end": 632.98, "text": " this number is not like random. Quora data set the citation network which this"}, {"start": 632.98, "end": 639.36, "text": " paper also used as a benchmark has this many features per node where every node"}, {"start": 639.36, "end": 643.86, "text": " represents a paper in a citation graph. So basically all of these nodes will"}, {"start": 643.86, "end": 650.72, "text": " have this feature vector and high level what the method does is it first"}, {"start": 650.72, "end": 655.6800000000001, "text": " projects these these feature vectors using this matrix W which we can see"}, {"start": 655.6800000000001, "end": 661.2, "text": " here projects the projects I mean to some lower usually lower dimensional"}, {"start": 661.2, "end": 669.2, "text": " space. So it will basically be a fully connected feed-forward layer without the"}, {"start": 669.2, "end": 672.64, "text": " activation at this point or you can just treat it as an identity activation which"}, {"start": 672.64, "end": 677.3199999999999, "text": " is the same thing. And so basically this one will maybe have 64 dimensions and"}, {"start": 677.3199999999999, "end": 684.3199999999999, "text": " once we do this for every single node in the graph we end up having so that's"}, {"start": 684.3199999999999, "end": 688.92, "text": " this part and now what this part does and I'll explain why it basically just"}, {"start": 688.92, "end": 694.28, "text": " accumulates or aggregates which is a term used in the graph literature these"}, {"start": 694.28, "end": 701.6, "text": " features and it just scales them using these square root over di dj things and"}, {"start": 701.6, "end": 709.2, "text": " you add them up and you get the new representation. So basically this"}, {"start": 709.2, "end": 714.24, "text": " node one will accumulate all of the vectors because all of them connect all"}, {"start": 714.24, "end": 718.44, "text": " of these nodes connect to it so it will have so its final representation will"}, {"start": 718.44, "end": 722.32, "text": " contain some portions of all of these other feature vectors. On the other hand"}, {"start": 722.32, "end": 728.24, "text": " if we take node two it will have only the feature vector that came from itself"}, {"start": 728.24, "end": 732.5600000000001, "text": " and the came from node one. So that's the difference. So you just basically take"}, {"start": 732.5600000000001, "end": 736.76, "text": " the one hop neighborhood you just aggregate those projected features you"}, {"start": 736.76, "end": 742.5600000000001, "text": " sum them up but before you sum you use those like scale these scaling factors"}, {"start": 742.5600000000001, "end": 748.04, "text": " and that's it. You basically only apply after you do that you apply some"}, {"start": 748.04, "end": 752.8, "text": " nonlinear differentiable activation functions such as ReLU and I assume"}, {"start": 752.8, "end": 756.24, "text": " everybody knows what ReLU is but I'm gonna just draw it for the sake of"}, {"start": 756.24, "end": 762.6800000000001, "text": " argument so basically it's like a zero here and pretty much y equals"}, {"start": 762.6800000000001, "end": 770.76, "text": " to x in this part. So if you still can't associate this equation with the process"}, {"start": 770.76, "end": 775.08, "text": " I just described I'm going to go once more and explaining the exact process"}, {"start": 775.08, "end": 781.28, "text": " that goes on in this vectorized form. So I want to explain concepts I try and do"}, {"start": 781.28, "end": 785.6, "text": " it as intuitive as possible but like these all of these equations are usually"}, {"start": 785.6, "end": 790.96, "text": " vectorized and which makes them less maybe less intuitive but once you kind"}, {"start": 790.96, "end": 795.36, "text": " of get the hang of it it becomes really easy. So let me try and explain every"}, {"start": 795.36, "end": 800.48, "text": " single matrix. So H matrix is basically as I said you just we just stack"}, {"start": 800.48, "end": 805.44, "text": " horizontally all of these feature vectors. So because we have n nodes this"}, {"start": 805.44, "end": 813.4, "text": " H matrix in the zeroth level so initially it will just be basically n"}, {"start": 813.4, "end": 820.52, "text": " times whatever the dimension here is and that's we said 1433. So this one will be"}, {"start": 820.52, "end": 829.6, "text": " so again it will be n times 1433 that's the size. Then we have this w matrix and"}, {"start": 829.6, "end": 836.68, "text": " w projects from 1433 into we said I took like as an example I took 64. So it will"}, {"start": 836.68, "end": 842.72, "text": " be a matrix that has the same dimension here will be here so we'll have"}, {"start": 842.72, "end": 855.96, "text": " pretty much 1433 times 64. So we'll have 64 dimensions here. So basically this"}, {"start": 855.96, "end": 863.88, "text": " corresponds to this one and once you multiply these matrices so H times w"}, {"start": 863.88, "end": 868.64, "text": " we'll end up with a new matrix which contains the projected feature"}, {"start": 868.64, "end": 872.56, "text": " vectors for every single vector for every single node in the in the in the"}, {"start": 872.56, "end": 877.3199999999999, "text": " graph. So we'll end up with a new matrix some intermediate matrix that has a"}, {"start": 877.3199999999999, "end": 884.56, "text": " dimension n times this times 64 and those are these small vectors I draw"}, {"start": 884.56, "end": 890.28, "text": " here and here etc. So hopefully that part is so far so good. So that's this part"}, {"start": 890.28, "end": 897.64, "text": " okay and finally we need to multiply by this by this normal by this normalized"}, {"start": 897.64, "end": 902.48, "text": " adjacency matrix and let's let's figure out that part. So now we have so let me"}, {"start": 902.48, "end": 906.88, "text": " take this example we already have concrete numbers here I just don't have"}, {"start": 906.88, "end": 914.6, "text": " these 1 over di dj parts but you can just imagine they are there and what we"}, {"start": 914.6, "end": 919.78, "text": " do so I'm going to redraw it again here just to make it a bit more clear. So we"}, {"start": 919.78, "end": 925.4399999999999, "text": " have ones here we have ones here and because of the self connections we have"}, {"start": 925.44, "end": 931.72, "text": " ones along the diagonal as well everything else is zero. So I just stack"}, {"start": 931.72, "end": 936.2800000000001, "text": " four nodes because n equals to 4 here right in our small graph we have only"}, {"start": 936.2800000000001, "end": 944.84, "text": " four nodes. So we stack up those 64 dimensional vectors and I won't draw"}, {"start": 944.84, "end": 950.1600000000001, "text": " every single element because they are initially just some random values. So"}, {"start": 950.1600000000001, "end": 954.5200000000001, "text": " basically what we do is the following so the first node as you can see because"}, {"start": 954.52, "end": 960.0799999999999, "text": " it has all ones it will basically take into account every single projected"}, {"start": 960.0799999999999, "end": 963.4, "text": " vector and that's what I previously explained so because it's connected to"}, {"start": 963.4, "end": 967.68, "text": " everything it will take all of the feature vectors the projected ones and"}, {"start": 967.68, "end": 974.4, "text": " it will just add them up and we have those terms as I mentioned which I want"}, {"start": 974.4, "end": 978.52, "text": " whatever like square root whatever corresponds to the degrees of those"}, {"start": 978.52, "end": 984.84, "text": " nodes. So that's the case for the node 1 but let's take for example node 2. So"}, {"start": 984.84, "end": 990.72, "text": " node 2 only has one here and one here and it has zeros here that means once"}, {"start": 990.72, "end": 996.0, "text": " you multiply this row with this matrix you'll just basically take these two"}, {"start": 996.0, "end": 999.96, "text": " feature vectors and that corresponds to the thing I mentioned previously and"}, {"start": 999.96, "end": 1003.8, "text": " that's just you just take this feature vector and you just take this feature"}, {"start": 1003.8, "end": 1010.0, "text": " vector and you add them up and you use those scales again and that's that's why"}, {"start": 1010.0, "end": 1014.0799999999999, "text": " the equation works and it's basically does the same thing as what I just"}, {"start": 1014.0799999999999, "end": 1018.52, "text": " intuitively explained here using the drawing. Hopefully this this makes sense"}, {"start": 1018.52, "end": 1024.2, "text": " and I went into a lot of details please let me know if this was too too"}, {"start": 1024.2, "end": 1029.32, "text": " detailed painfully detailed or it was just right so appreciate the feedback."}, {"start": 1029.32, "end": 1035.0, "text": " Now the reason they use these coefficients here to to to normalize"}, {"start": 1035.0, "end": 1042.56, "text": " the adjacency matrix values is because if we didn't do that we'd have a problem"}, {"start": 1042.56, "end": 1046.8799999999999, "text": " with exploding or vanishing gradients which can nicely be seen through this"}, {"start": 1046.8799999999999, "end": 1050.84, "text": " spectral prism which I'm going to explain right now. So basically if you're"}, {"start": 1050.84, "end": 1057.08, "text": " familiar with eigen decompositions what those scaling coefficients do is"}, {"start": 1057.08, "end": 1062.48, "text": " basically they make sure that the largest eigenvalue of our matrix is"}, {"start": 1062.48, "end": 1067.8, "text": " equal to 1. So basically they make sure that the range of eigenvalues is"}, {"start": 1067.8, "end": 1072.96, "text": " between 0 and 1 and by just continually applying that matrix we won't have"}, {"start": 1072.96, "end": 1077.24, "text": " exploding or vanishing gradients. So that's that's that's the trick. So this"}, {"start": 1077.24, "end": 1082.28, "text": " part by just constantly multiplying by this term if the eigenvalue range is in"}, {"start": 1082.28, "end": 1086.9199999999998, "text": " a good in a good range basically we won't have the problem I just mentioned"}, {"start": 1086.92, "end": 1093.04, "text": " with vanishing or exploding gradients. So because the the spectral part is really"}, {"start": 1093.04, "end": 1097.88, "text": " complicated it deserves a video for itself I'm just going to briefly explain"}, {"start": 1097.88, "end": 1102.72, "text": " the main ideas here and hopefully if you think that that could be useful I'll"}, {"start": 1102.72, "end": 1106.92, "text": " cover the specs some of the spectral methods in one of the next videos"}, {"start": 1106.92, "end": 1112.04, "text": " although they are not as popular as these spatial methods where GCN is one"}, {"start": 1112.04, "end": 1118.92, "text": " representative, GET is another representative, etc. GraphSAGE, etc. So how"}, {"start": 1118.92, "end": 1123.72, "text": " it works how the spectral graph convolutional method works in a nutshell"}, {"start": 1123.72, "end": 1128.96, "text": " is the following. So you take the Laplacian matrix which is basically the"}, {"start": 1128.96, "end": 1133.1599999999999, "text": " Green matrix and you subtract the adjacency matrix and you find the"}, {"start": 1133.1599999999999, "end": 1137.2, "text": " eigen decomposition of this matrix and you get eigenvectors and you get"}, {"start": 1137.2, "end": 1142.1200000000001, "text": " eigenvalues. So once you stack up those eigenvectors in a matrix you get these"}, {"start": 1142.1200000000001, "end": 1148.3600000000001, "text": " U matrices and what you do is you take the signal on your graph X so what's the"}, {"start": 1148.3600000000001, "end": 1156.72, "text": " signal? So just for the just for the sake of being of being clear so basically"}, {"start": 1156.72, "end": 1160.92, "text": " you take these feature vectors you take maybe first feature from every single"}, {"start": 1160.92, "end": 1166.32, "text": " feature vector and you can treat those as as a signal. So basically imagine we"}, {"start": 1166.32, "end": 1173.36, "text": " have we just align these nodes linearly and we take those first features from"}, {"start": 1173.36, "end": 1177.48, "text": " all of the feature vectors and maybe this one has value like this maybe this"}, {"start": 1177.48, "end": 1182.4399999999998, "text": " has a bit bigger value and you basically can treat this if I interpolate some"}, {"start": 1182.4399999999998, "end": 1186.24, "text": " random interpolation you can treat it as a signal a discretized signal on the"}, {"start": 1186.24, "end": 1192.7, "text": " graph. So what we do here in the spectral method is we project that signal into"}, {"start": 1192.7, "end": 1199.0800000000002, "text": " the into the new basis defined by the laplacian eigenvectors and those are"}, {"start": 1199.0800000000002, "end": 1203.8, "text": " contained in U. Then we have this this is what is learned in these methods so we"}, {"start": 1203.8, "end": 1208.92, "text": " don't learn the W matrix as previously in GCN we'll learn this filter G theta"}, {"start": 1208.92, "end": 1215.8400000000001, "text": " G sub theta and now the problem with this is and it says here it's"}, {"start": 1215.8400000000001, "end": 1219.8, "text": " computationally expensive as multiplication with the eigenvector"}, {"start": 1219.8, "end": 1227.08, "text": " matrix is O and so big O notation n square so basically because this matrix"}, {"start": 1227.08, "end": 1233.6399999999999, "text": " U is m times n and X is n times 1 because we remember we just took the"}, {"start": 1233.6399999999999, "end": 1239.1599999999999, "text": " like first feature or whatever like just one feature instead of the whole feature"}, {"start": 1239.1599999999999, "end": 1243.44, "text": " fully blown X matrix which has all of the features so basically that's why we"}, {"start": 1243.44, "end": 1249.1599999999999, "text": " have a computational cost of n squared and that's not the only problem the"}, {"start": 1249.16, "end": 1253.0400000000002, "text": " second problem is that doing the eigen decomposition of the laplacian is super"}, {"start": 1253.0400000000002, "end": 1257.68, "text": " expensive it's I think it depends on the like there are more optimal methods"}, {"start": 1257.68, "end": 1264.5800000000002, "text": " depending on certain like details but like O of n squared n cubed is probably"}, {"start": 1264.5800000000002, "end": 1269.64, "text": " a good estimate of the complexity and so that's super expensive so then there"}, {"start": 1269.64, "end": 1276.16, "text": " were so Hammond and his collaborators suggested that we can just instead of"}, {"start": 1276.16, "end": 1280.92, "text": " learning all of the n parameters here so where n is the side of the graph which"}, {"start": 1280.92, "end": 1284.44, "text": " can be in the size of billions if we're dealing dealing with for example"}, {"start": 1284.44, "end": 1290.5600000000002, "text": " Facebook graph or Pinterest wherever and basically you can we can treat this we"}, {"start": 1290.5600000000002, "end": 1296.3200000000002, "text": " can just compute like a like a K polynomial and using using Chebyshev"}, {"start": 1296.3200000000002, "end": 1302.0800000000002, "text": " polynomial and we can just use this approximation now I won't get into"}, {"start": 1302.08, "end": 1306.1999999999998, "text": " details how this approximation came to be there will be a separate video but"}, {"start": 1306.1999999999998, "end": 1313.1599999999999, "text": " like just trust me on this one and it can be shown that instead of using so"}, {"start": 1313.1599999999999, "end": 1318.48, "text": " this matrix here lambda contains eigenvalues we can ditch computing the"}, {"start": 1318.48, "end": 1324.36, "text": " eigen decomposition and we can save those n cubed computations and we can"}, {"start": 1324.36, "end": 1331.02, "text": " just do a Chebyshev polynomial using the this this laplacian matrix instead"}, {"start": 1331.02, "end": 1337.6, "text": " instead of using the eigenvalues matrix so Chebyshev you can see a simple"}, {"start": 1337.6, "end": 1342.06, "text": " recursion again won't get into much details it's really simple recursion we"}, {"start": 1342.06, "end": 1347.2, "text": " start with one and X and this is how you combine them to get the next polynomial"}, {"start": 1347.2, "end": 1354.16, "text": " terms and you basically end up having so this is how we do convolution spectral"}, {"start": 1354.16, "end": 1358.52, "text": " convolution now so we just have K terms here we have K parameters so these are"}, {"start": 1358.52, "end": 1365.16, "text": " scalars we just learned these and it's much more efficient this time so the"}, {"start": 1365.16, "end": 1371.8, "text": " thing with this this equation here approximation is that it's in contrast"}, {"start": 1371.8, "end": 1377.76, "text": " to the pure spectral methods like this one this one is K localized and that"}, {"start": 1377.76, "end": 1383.72, "text": " means that pretty much means that all of the if we have a graph and you take a"}, {"start": 1383.72, "end": 1389.64, "text": " single node it will only capture the features from its k-hop neighborhood so"}, {"start": 1389.64, "end": 1396.04, "text": " meaning the the neighbors which are further away are only our K edges far"}, {"start": 1396.04, "end": 1401.72, "text": " far off from from this target node so why that is is because if you know"}, {"start": 1401.72, "end": 1406.9, "text": " something about adjacency matrix properties if you just raise it to the"}, {"start": 1406.9, "end": 1414.88, "text": " power of K what you end up doing is the term ij in this matrix will tell you how"}, {"start": 1414.88, "end": 1423.2, "text": " many paths there are between nodes i and j like k length paths so basically"}, {"start": 1423.2, "end": 1430.24, "text": " that's that's the reason why why why we have a k-hop neighborhood here now again"}, {"start": 1430.24, "end": 1434.6000000000001, "text": " if you didn't understand this detail it's totally fine that's not the point"}, {"start": 1434.6, "end": 1438.84, "text": " of this video so now what GCN does is basically it starts from this"}, {"start": 1438.84, "end": 1442.08, "text": " approximation so this is a an approximation of the fully blown"}, {"start": 1442.08, "end": 1447.24, "text": " spectral method and it does the following it just says let's just treat"}, {"start": 1447.24, "end": 1451.28, "text": " let's just take a look at one hop neighborhoods we don't care about k-hop"}, {"start": 1451.28, "end": 1456.7199999999998, "text": " neighborhoods we want to make we set k to 1 so no so as they say here now"}, {"start": 1456.7199999999998, "end": 1461.08, "text": " imagine we will limit it the layer wise convolution operation to k1 so that's"}, {"start": 1461.08, "end": 1465.9199999999998, "text": " the first approximation they do and so they say it here nicely we intuitively"}, {"start": 1465.9199999999998, "end": 1470.36, "text": " expect that such a model can alleviate the problem of overfitting on local"}, {"start": 1470.36, "end": 1474.8, "text": " neighborhood structures for graphs with very wide node degree distributions such"}, {"start": 1474.8, "end": 1478.28, "text": " as social networks citation networks knowledge graphs and many other real"}, {"start": 1478.28, "end": 1483.82, "text": " world graph datasets so that's the explanation the the argument why they"}, {"start": 1483.82, "end": 1488.4399999999998, "text": " set k to 1 basically for certain graphs like citation networks which they are"}, {"start": 1488.44, "end": 1496.6000000000001, "text": " using as benchmarks in this paper like Cora sites here etc they can be they"}, {"start": 1496.6000000000001, "end": 1501.92, "text": " are basically something called small world networks and this approximation"}, {"start": 1501.92, "end": 1506.96, "text": " makes sense the second approximation they do is they say here we further"}, {"start": 1506.96, "end": 1512.98, "text": " approximate lambda max so the maximum eigenvalue to be approximately 2 as we"}, {"start": 1512.98, "end": 1515.92, "text": " can expect that neural network parameters will adapt to this change in"}, {"start": 1515.92, "end": 1520.96, "text": " scale during training okay so basically once you take those so k equals to 1 and"}, {"start": 1520.96, "end": 1526.3200000000002, "text": " lambda max equals to 2 you basically going from this equation you end up"}, {"start": 1526.3200000000002, "end": 1535.68, "text": " with with this one and basically now you can just if you take a look at what well"}, {"start": 1535.68, "end": 1542.96, "text": " lambda y y l minus identity here is because they're using they're having a"}, {"start": 1542.96, "end": 1551.88, "text": " Chebyshev polynomial of this scaled laplacian so basically what that means"}, {"start": 1551.88, "end": 1559.08, "text": " is so if we expand this polynomial we'll end up with first term will be I the"}, {"start": 1559.08, "end": 1569.3600000000001, "text": " second one will be this L tilde then we'll have 2 L tilde squared minus I"}, {"start": 1569.36, "end": 1577.24, "text": " etc depending how many how big the K is so if we if we consider L max to be 2"}, {"start": 1577.24, "end": 1584.24, "text": " we'll ditch this term and we'll end up with L minus identity and that's what we"}, {"start": 1584.24, "end": 1590.84, "text": " get here so that's the L minus identity part and now finally there is one more"}, {"start": 1590.84, "end": 1595.08, "text": " approximation they do and that's constraining these two to be the same"}, {"start": 1595.08, "end": 1601.36, "text": " thing so theta 0 and theta 1 let's read them to be the same parameter and you"}, {"start": 1601.36, "end": 1607.6, "text": " can extract it and basically you get this equation and the last trick they do"}, {"start": 1607.6, "end": 1612.12, "text": " because if you take a look at this matrix the range of eigenvalues will be"}, {"start": 1612.12, "end": 1619.1599999999999, "text": " from 0 to 2 which means if we continually keep on multiplying features"}, {"start": 1619.16, "end": 1625.92, "text": " X projected features we have theta here times this matrix will end up"}, {"start": 1625.92, "end": 1631.24, "text": " increasing the values or the consequently the gradients will either"}, {"start": 1631.24, "end": 1635.68, "text": " explode or diminish and that's something we want to avoid and that's why they do"}, {"start": 1635.68, "end": 1640.16, "text": " this normalization trick and what they basically do is they add up self"}, {"start": 1640.16, "end": 1644.5600000000002, "text": " connections and we saw that when I was explaining the method itself so"}, {"start": 1644.56, "end": 1652.48, "text": " basically that's it once you once you just swap this part with this part you"}, {"start": 1652.48, "end": 1657.96, "text": " end up with the final method and that's the the form I previously I previously"}, {"start": 1657.96, "end": 1663.08, "text": " explained so that the good thing about this method it has a complexity that's"}, {"start": 1663.08, "end": 1669.8, "text": " proportional to the number of edges in the graph and not to do like a number of"}, {"start": 1669.8, "end": 1675.28, "text": " nodes like raise the power of three for like spectral spectral methods which was"}, {"start": 1675.28, "end": 1682.28, "text": " super super compute intensive so yeah it was a it was a mouthful there is a lot"}, {"start": 1682.28, "end": 1686.8, "text": " of details and you need to read a couple of papers to understand every single"}, {"start": 1686.8, "end": 1692.6, "text": " part so for example why this approximation works why we can why we"}, {"start": 1692.6, "end": 1700.9199999999998, "text": " can swap eigenvalues with laplacians here and yeah that's probably the"}, {"start": 1700.9199999999998, "end": 1705.52, "text": " hardest part then you can just this is simple thing this one is also"}, {"start": 1705.52, "end": 1710.9599999999998, "text": " conceptually simple and a couple more steps in your where the final stage but"}, {"start": 1710.9599999999998, "end": 1717.76, "text": " that's why I said that maybe not looking at at the GCN through this spectral"}, {"start": 1717.76, "end": 1723.2, "text": " prism but by looking at GCN maybe as a special case of get method or as a"}, {"start": 1723.2, "end": 1728.56, "text": " message passing network in general is much more like feels more natural than"}, {"start": 1728.56, "end": 1732.04, "text": " than treating it as a special as a spectral method because it's not"}, {"start": 1732.04, "end": 1735.68, "text": " spectral method we don't have to compute it's not like the final expression"}, {"start": 1735.68, "end": 1739.04, "text": " doesn't have to do anything with spectrum we don't have to compete to"}, {"start": 1739.04, "end": 1743.76, "text": " compute eigenvalues you don't have to compute eigenvectors so is that it was"}, {"start": 1743.76, "end": 1747.6, "text": " just motivated by by the spectral methods but it's not a spectral method"}, {"start": 1747.6, "end": 1752.84, "text": " itself so just avoid being confused there the hardest part we covered the"}, {"start": 1752.84, "end": 1757.04, "text": " method we covered how it was motivated by the spectral methods and we saw how"}, {"start": 1757.04, "end": 1762.8999999999999, "text": " the explicit graph laplacian regularization works so now let me just"}, {"start": 1762.8999999999999, "end": 1767.6, "text": " walk you through the rest of the paper a couple of more things details so once"}, {"start": 1767.6, "end": 1772.1599999999999, "text": " you pre train GCN with two layers on the core data set and you extract the hidden"}, {"start": 1772.16, "end": 1777.68, "text": " layers the hidden features you can project them into 2d space using"}, {"start": 1777.68, "end": 1781.88, "text": " t-sne and you get this and if you remember if you if you watch my previous"}, {"start": 1781.88, "end": 1787.92, "text": " video on get you can see that get maybe had a bit better separation between a"}, {"start": 1787.92, "end": 1794.16, "text": " Cora classes than GCN but once you actually once you and you can also"}, {"start": 1794.16, "end": 1799.8000000000002, "text": " verify that because it had had better accuracy than GCN but I'll get to those"}, {"start": 1799.8, "end": 1805.8799999999999, "text": " results in a bit but basically you can you can see that get actually has on"}, {"start": 1805.8799999999999, "end": 1810.2, "text": " these types of networks on citation networks the attention coefficients it"}, {"start": 1810.2, "end": 1814.72, "text": " used for the neighborhood are pretty similar and kind of approximate GCN"}, {"start": 1814.72, "end": 1820.76, "text": " although it's more more expressive and thus has a better results okay so again"}, {"start": 1820.76, "end": 1825.56, "text": " semi-supervised learning pretty simpler simple thing and I explained that in get"}, {"start": 1825.56, "end": 1830.9199999999998, "text": " but like for the sake of being complete here you just do cross entropy so you"}, {"start": 1830.9199999999998, "end": 1835.56, "text": " basically have a huge network and you just take for every single class and"}, {"start": 1835.56, "end": 1840.44, "text": " Cora has like seven classes you only take 20 notes whose labels you're going"}, {"start": 1840.44, "end": 1844.8, "text": " to use you don't use other labels you do use the features but you don't use the"}, {"start": 1844.8, "end": 1851.6799999999998, "text": " labels and finally once you get to the final layer the feature vectors now have"}, {"start": 1851.68, "end": 1856.8, "text": " the number of classes like seven for Cora and you'll just do you'll just do"}, {"start": 1856.8, "end": 1860.72, "text": " cross entropy loss on on those on those on those values and that's how you train"}, {"start": 1860.72, "end": 1868.0, "text": " these models so basically for the sake of being clear so what would we do again"}, {"start": 1868.0, "end": 1873.88, "text": " let's say this is Cora so we start with thousand four hundred thirty three we do"}, {"start": 1873.88, "end": 1879.64, "text": " the projection we do the aggregation so in the hidden layer we'll have maybe 64"}, {"start": 1879.64, "end": 1885.24, "text": " features and again we do apply in our layer and because Cora has seven classes"}, {"start": 1885.24, "end": 1892.6000000000001, "text": " the final feature vectors will only have seven features and we do softmax so we"}, {"start": 1892.6000000000001, "end": 1897.48, "text": " end up with a probability distribution and we just take a look where the true"}, {"start": 1897.48, "end": 1904.96, "text": " classes and we do the cross entropy so if it's maybe 0.4 the loss will be log"}, {"start": 1904.96, "end": 1912.8, "text": " 0.4 and just a minus there and that means this needs to go to one for the"}, {"start": 1912.8, "end": 1917.32, "text": " ground truth class in order for the loss to go to zero which makes sense and you"}, {"start": 1917.32, "end": 1924.52, "text": " just do gradient based learning and they used Adam for GCN and that's it in a"}, {"start": 1924.52, "end": 1928.8, "text": " nutshell and again they visualize these features here let's see a couple more"}, {"start": 1928.8, "end": 1934.16, "text": " things in this paper the next thing is so I already mentioned we have"}, {"start": 1934.16, "end": 1938.48, "text": " previously to GCN and the spectral methods we have we had two broad"}, {"start": 1938.48, "end": 1942.8400000000001, "text": " categories the ones that use explicit graph laplation and the one that used a"}, {"start": 1942.8400000000001, "end": 1947.48, "text": " graph embedding approach so the graph embedding approach basically creates"}, {"start": 1947.48, "end": 1952.64, "text": " random walks it's similar to vertebrae if you're familiar with NLP yeah it's"}, {"start": 1952.64, "end": 1957.64, "text": " basically the same idea just apply to graphs you treat random walks on graphs"}, {"start": 1957.64, "end": 1964.2800000000002, "text": " as sentences and you basically train your embeddings such that they are such"}, {"start": 1964.2800000000002, "end": 1969.5200000000002, "text": " that the ones that appear close to each other attend to have similar embeddings"}, {"start": 1969.5200000000002, "end": 1977.2, "text": " in a nutshell so I mentioned previously they used three citation networks sites"}, {"start": 1977.2, "end": 1982.6000000000001, "text": " here core and PubMed there's this knowledge graph as benchmarks and yeah I"}, {"start": 1982.6, "end": 1987.8, "text": " mentioned that Cora has thousand so this we're using this example as a as a as a"}, {"start": 1987.8, "end": 1993.6799999999998, "text": " as on the fly example throughout this video and basically you can see some"}, {"start": 1993.6799999999998, "end": 1999.36, "text": " statistics related to that like data set and it has seven classes as I already"}, {"start": 1999.36, "end": 2005.6, "text": " mentioned so and I mentioned they're using only 20 labels per class so so"}, {"start": 2005.6, "end": 2012.28, "text": " that means so you have so you have the core has 2,700 nodes but you only use"}, {"start": 2012.28, "end": 2022.16, "text": " for hundred forty to train the the GCN method okay they also have some random"}, {"start": 2022.16, "end": 2029.08, "text": " graphs I'll explain those briefly why they mentioned those ones okay so here"}, {"start": 2029.08, "end": 2033.96, "text": " are the results you can basically they compared against these these methods used"}, {"start": 2033.96, "end": 2038.68, "text": " at explicit graph laplation regularization deep walk and planetoid"}, {"start": 2038.68, "end": 2044.28, "text": " our graph embedding methods and here is GCN and we can see on every single data"}, {"start": 2044.28, "end": 2049.96, "text": " set they have a significant improvement compared to the baselines and yeah"}, {"start": 2049.96, "end": 2057.2000000000003, "text": " that's nice okay finally they compared different methods and this is the reason"}, {"start": 2057.2000000000003, "end": 2062.28, "text": " I had to go into a bit more details in the spectral section part so basically"}, {"start": 2062.28, "end": 2067.32, "text": " they compare the Chebyshev so the one that the the approximation of the full"}, {"start": 2067.32, "end": 2072.92, "text": " spectral method and they tried using K2 and K3 so that means they're using K 2"}, {"start": 2072.92, "end": 2078.2000000000003, "text": " hop and 3 hop neighborhoods and you can see the results are worse than GCN method"}, {"start": 2078.2000000000003, "end": 2082.92, "text": " and the renormalization trick is the official the final GCN method you can"}, {"start": 2082.92, "end": 2090.0800000000004, "text": " see so here going from top to bottom are the approximation we were making so here"}, {"start": 2090.0800000000004, "end": 2096.2400000000002, "text": " we just set K to 1 then we we we constrain these two tatas to be the same"}, {"start": 2096.24, "end": 2102.52, "text": " here in the single parameter row and we can see that all of the results are"}, {"start": 2102.52, "end": 2108.3599999999997, "text": " worse than by using the final the final GCN version they also compared against"}, {"start": 2108.3599999999997, "end": 2113.8399999999997, "text": " the first order term only so they ditch this part and they just use the the"}, {"start": 2113.8399999999997, "end": 2118.68, "text": " first order term and we also get worse results and finally the reason I"}, {"start": 2118.68, "end": 2124.6, "text": " highlighted MLP here is that it doesn't use the graph structure and you can see"}, {"start": 2124.6, "end": 2129.72, "text": " that the the performance the the accuracy is far like lower than all of"}, {"start": 2129.72, "end": 2135.6, "text": " the other methods so that's the reason so even so so basically it's really"}, {"start": 2135.6, "end": 2139.8399999999997, "text": " important to use the the graph structure because it contains a lot of"}, {"start": 2139.8399999999997, "end": 2145.08, "text": " information so how they train the MLP I suppose is so again you have you have"}, {"start": 2145.08, "end": 2149.88, "text": " the graph and you have features associated with them and you just"}, {"start": 2149.88, "end": 2155.04, "text": " basically independently apply the MLP here so this is maybe the first layer"}, {"start": 2155.04, "end": 2159.76, "text": " and then you have the second layer and you end up with seven classes here and"}, {"start": 2159.76, "end": 2168.84, "text": " you just take those four hundred hundred forty notes sorry to to basically train"}, {"start": 2168.84, "end": 2175.0, "text": " this MLP and you basically repeat the same so these are the same weights these"}, {"start": 2175.0, "end": 2179.2400000000002, "text": " are the shared weights you apply them to the first feature vector then you go to"}, {"start": 2179.24, "end": 2184.4799999999996, "text": " the second one blah blah blah you apply the the the cross entropy loss and you"}, {"start": 2184.4799999999996, "end": 2189.04, "text": " train the MLP and that's and that's so so you can see in this process it's not"}, {"start": 2189.04, "end": 2192.8799999999997, "text": " using the connectivity pattern so it's ignoring the connectivity pattern"}, {"start": 2192.8799999999997, "end": 2197.8799999999997, "text": " altogether okay let's continue and finish up wrap up this paper there are a"}, {"start": 2197.8799999999997, "end": 2201.72, "text": " couple more things I want to mention the first thing is and this is interesting"}, {"start": 2201.72, "end": 2206.64, "text": " so so basically you can see the training times here on the y-axis we have seconds"}, {"start": 2206.64, "end": 2211.4, "text": " per epoch and on the x-axis we have number of edges and this is where those"}, {"start": 2211.4, "end": 2216.72, "text": " random graphs can come into place so what they did is they just create n"}, {"start": 2216.72, "end": 2224.52, "text": " notes and they just take two n edges and they randomly uniformly just connect"}, {"start": 2224.52, "end": 2229.68, "text": " all of these notes and that's the graphs they were using and they just use a"}, {"start": 2229.68, "end": 2234.72, "text": " featureless approach where basically you just have a one hot vector or the"}, {"start": 2234.72, "end": 2242.12, "text": " adjacency matrix is pretty much the identity matrix and they use these graphs"}, {"start": 2242.12, "end": 2246.8799999999997, "text": " to just a benchmark like the test the speed of these their models and we can"}, {"start": 2246.8799999999997, "end": 2253.68, "text": " see that as we go to a huge number of edges the speed is still around one to"}, {"start": 2253.68, "end": 2260.9199999999996, "text": " ten seconds on CPU and GPU and compare that transformers which need days upon"}, {"start": 2260.92, "end": 2265.56, "text": " days of like huge machines to train them and but once you think about it it's not"}, {"start": 2265.56, "end": 2271.64, "text": " that interesting because we only have a W matrix in the case of GCN to train and"}, {"start": 2271.64, "end": 2276.32, "text": " that's a small number of parameters although as the number of nodes gets"}, {"start": 2276.32, "end": 2281.7200000000003, "text": " bigger the computation also gets bigger but using sparse dense matrix"}, {"start": 2281.7200000000003, "end": 2285.96, "text": " multiplication and some methods you can you can speed it up but it's interesting"}, {"start": 2285.96, "end": 2291.16, "text": " it's really it's really fast to train these networks and that's that's cool"}, {"start": 2291.16, "end": 2297.32, "text": " okay let's go and see a couple more things so I mentioned memory requirement"}, {"start": 2297.32, "end": 2302.88, "text": " and so I'm actually currently implementing the graph attention"}, {"start": 2302.88, "end": 2308.04, "text": " network and I'll open source it in a couple of weeks probably but like the"}, {"start": 2308.04, "end": 2313.96, "text": " the hardest part I found like implementing these networks is how to"}, {"start": 2313.96, "end": 2317.6, "text": " efficiently implement the layer and that's that's pretty much everything"}, {"start": 2317.6, "end": 2323.2400000000002, "text": " because you want to there is all of these like sparse formats and matrix"}, {"start": 2323.2400000000002, "end": 2328.28, "text": " sparse dense matrix multiplications happening and how what's the best way to"}, {"start": 2328.28, "end": 2332.76, "text": " represent your edges whether using edge index or just using the plain old sparse"}, {"start": 2332.76, "end": 2336.84, "text": " adjacency matrix and then finding some suitable format to represent it anyways"}, {"start": 2336.84, "end": 2340.92, "text": " I don't want to get into too much detail just keep that in mind that pretty much"}, {"start": 2340.92, "end": 2348.2400000000002, "text": " the hard hardest part here is to like efficiently implement these methods yeah"}, {"start": 2348.2400000000002, "end": 2352.04, "text": " they see here our framework currently does not naturally support edge features"}, {"start": 2352.04, "end": 2357.64, "text": " and is limited to undirected graphs weighted or unweighted that's that's"}, {"start": 2357.64, "end": 2362.4, "text": " something to keep in mind because both Cora and all of these benchmarks they"}, {"start": 2362.4, "end": 2366.7200000000003, "text": " used they don't have any edge features they just have like simple binary"}, {"start": 2366.72, "end": 2373.68, "text": " connections okay that was the the main part of paper I mentioned in the"}, {"start": 2373.68, "end": 2377.08, "text": " beginning of this video that I have three perspectives we can treat this so"}, {"start": 2377.08, "end": 2382.14, "text": " we can we can look at this GCN paper through three different perspectives the"}, {"start": 2382.14, "end": 2386.64, "text": " one is spectral method perspective and now let me show you the second one the"}, {"start": 2386.64, "end": 2393.08, "text": " Weiss-Feyler-Lehmann algorithm so basically WL algorithm or Weiss-Feyler-Lehmann"}, {"start": 2393.08, "end": 2398.2, "text": " specifically the 1D case of this algorithm what it does it's a simple"}, {"start": 2398.2, "end": 2403.0, "text": " isomorphism graph isomorphism test what that means is basically you have two"}, {"start": 2403.0, "end": 2410.08, "text": " graphs so graph G1 and you take second graph graph G2 and you pass it in into"}, {"start": 2410.08, "end": 2415.64, "text": " this test and if the if the final something called node colorings are the"}, {"start": 2415.64, "end": 2420.12, "text": " same no if they're different then you're most you're sure that these two graphs"}, {"start": 2420.12, "end": 2424.52, "text": " are not isomorphic if they're the same you're still not completely sure because"}, {"start": 2424.52, "end": 2429.0, "text": " there are special special cases where Weiss-Feyler-Lehmann like fails but like"}, {"start": 2429.0, "end": 2434.2799999999997, "text": " you're pretty certain that those two graphs are isomorphic and what isomorphic"}, {"start": 2434.2799999999997, "end": 2439.2799999999997, "text": " means is basically you those are just two same graphs but just have different"}, {"start": 2439.2799999999997, "end": 2444.2999999999997, "text": " maybe different labeling and if you find some different like permutation of"}, {"start": 2444.2999999999997, "end": 2447.68, "text": " labels you can see that those two graphs are the same and there are some really"}, {"start": 2447.68, "end": 2451.7599999999998, "text": " nice examples I'll show it here on the screen and you can see those two graphs"}, {"start": 2451.7599999999998, "end": 2457.64, "text": " are are the same even though they look differently like at the first glance so"}, {"start": 2457.64, "end": 2460.58, "text": " that's the idea with the Weiss-Feyler-Lehmann algorithm and now you can treat"}, {"start": 2460.58, "end": 2468.2, "text": " GCN as a pretty much as a generalized version of of of this Weiss-Feyler-Lehmann"}, {"start": 2468.2, "end": 2472.48, "text": " algorithm and with a disclaimer I'll in a couple of seconds explain why that's"}, {"start": 2472.48, "end": 2476.52, "text": " not completely true but let's for the sake of argument now let's play that"}, {"start": 2476.52, "end": 2481.28, "text": " game so this is how the algorithm looks like so we start with initial node"}, {"start": 2481.28, "end": 2486.0, "text": " coloring and you can treat maybe this the same as so we have those features"}, {"start": 2486.0, "end": 2492.16, "text": " the same as we use so far and basically the algorithm stops once those features"}, {"start": 2492.16, "end": 2497.36, "text": " stabilize and it's basically the same structure so we have repeat until is"}, {"start": 2497.36, "end": 2501.44, "text": " basically going through the layers of our GCN and we for every single node"}, {"start": 2501.44, "end": 2507.84, "text": " what we do is we aggregate the features or the colorings in this in this case"}, {"start": 2507.84, "end": 2513.08, "text": " that we aggregate them and we hash them and that's what's what our updated"}, {"start": 2513.08, "end": 2517.44, "text": " representation looks like and if you think about it it's really similar to"}, {"start": 2517.44, "end": 2521.68, "text": " what we have with GCN so basically we aggregate across the neighborhood again"}, {"start": 2521.68, "end": 2526.8, "text": " and we have these C ij's which I've mentioned a lot of times already and"}, {"start": 2526.8, "end": 2534.04, "text": " that equals to one over square root di dj where those are degrees of those"}, {"start": 2534.04, "end": 2538.5600000000004, "text": " particular notes and if you take a look at it it's the same format you can treat"}, {"start": 2538.5600000000004, "end": 2543.5600000000004, "text": " just the hash part is maybe the non-linearity and these projections and"}, {"start": 2543.5600000000004, "end": 2549.6000000000004, "text": " scaling but it's it has a similar structure and they say here this loosely"}, {"start": 2549.6000000000004, "end": 2553.36, "text": " speaking and it's really important to to highlight the loosely speaking part"}, {"start": 2553.36, "end": 2557.44, "text": " because it's not completely true and you'll see in a minute allows us to"}, {"start": 2557.44, "end": 2560.6400000000003, "text": " interpret our GCN model as a differentiable and parameterized"}, {"start": 2560.6400000000003, "end": 2565.36, "text": " generalization of the one-dimensional Weissweiler-Lehmann algorithm on graphs"}, {"start": 2565.36, "end": 2572.8, "text": " and now the disclaimer so basically later this paper called graph isomorphism"}, {"start": 2572.8, "end": 2579.84, "text": " networks appeared and it showed that GCN is not quite there so they say here this"}, {"start": 2579.84, "end": 2583.88, "text": " is just a snippet from the paper so we will see that these GNN variants get"}, {"start": 2583.88, "end": 2588.48, "text": " confused by surprisingly simple graphs and are less powerful than the WL"}, {"start": 2588.48, "end": 2592.32, "text": " device Weissweiler-Lehmann test nonetheless models with mean aggregators"}, {"start": 2592.32, "end": 2598.44, "text": " like GCN perform well for node classification tasks and we used exactly"}, {"start": 2598.44, "end": 2603.04, "text": " the node classification benchmarks in this paper so this paper used those"}, {"start": 2603.04, "end": 2609.0, "text": " benchmarks so that's why we couldn't notice I mean you this paper appear"}, {"start": 2609.0, "end": 2614.28, "text": " only later so it was hard for them to to compare but anyways they show that these"}, {"start": 2614.28, "end": 2620.52, "text": " gene GIN networks are more expressive than GCN's and more expressive that gets"}, {"start": 2620.52, "end": 2625.6, "text": " also so that's something to keep in mind I won't get into too much details but"}, {"start": 2625.6, "end": 2631.48, "text": " basically there are certain families of graphs which if you input them so you"}, {"start": 2631.48, "end": 2638.72, "text": " have graph one and you have graph two and they are different but once you pass"}, {"start": 2638.72, "end": 2646.04, "text": " them into GCN it would give it will give them the same node coloring which means"}, {"start": 2646.04, "end": 2651.2799999999997, "text": " GCN treats these two graphs the same like they are isomorphic but they're not"}, {"start": 2651.2799999999997, "end": 2658.2, "text": " they're different so GCN can fail on some on certain graph families as well"}, {"start": 2658.2, "end": 2663.3199999999997, "text": " as get but yeah that's something I thought it's worth mentioning just to"}, {"start": 2663.32, "end": 2669.1200000000003, "text": " keep connecting those dots across different papers finally so I mentioned"}, {"start": 2669.1200000000003, "end": 2672.2400000000002, "text": " the third perspective get perspective so basically can treat the GCN as a"}, {"start": 2672.2400000000002, "end": 2677.76, "text": " particular case of get where you have instead of learning those weights you"}, {"start": 2677.76, "end": 2684.6800000000003, "text": " just have them hard coded as this expression which I've mentioned multiple"}, {"start": 2684.6800000000003, "end": 2693.0, "text": " times already so that's about that's it and finally as a nice consequence of of"}, {"start": 2693.0, "end": 2699.16, "text": " this of the fact that you can treat this as a WL algorithm so they say here from"}, {"start": 2699.16, "end": 2703.28, "text": " the analogy with the WL we can understand that even an untrained GCN"}, {"start": 2703.28, "end": 2708.12, "text": " model with random weights can serve as powerful feature extractor for nodes in"}, {"start": 2708.12, "end": 2713.64, "text": " a graph so what we do here we just take these W matrices and we live them we"}, {"start": 2713.64, "end": 2721.48, "text": " leave them like a random and basically so this a hat is the term with the tilde"}, {"start": 2721.48, "end": 2726.52, "text": " mine raised to the power of minus one half etc suggest the constant term so we"}, {"start": 2726.52, "end": 2733.56, "text": " just apply three layers here three GCN layers and this is what we end up with so"}, {"start": 2733.56, "end": 2738.56, "text": " we have they showed here that if we take this correct correct karate club network"}, {"start": 2738.56, "end": 2742.6, "text": " so if you take this network and you just take a feature as approach meaning all"}, {"start": 2742.6, "end": 2745.12, "text": " of these nodes don't have some meaningful features they're just like"}, {"start": 2745.12, "end": 2749.4, "text": " the adjacency matrix is pretty much identity matrix and if you pass it"}, {"start": 2749.4, "end": 2755.8, "text": " through the untrained GCN it will still learn how to separate different classes"}, {"start": 2755.8, "end": 2762.76, "text": " so what it did is so basically the last layer of this GCN has only two so the"}, {"start": 2762.76, "end": 2767.28, "text": " node features have only two dimensions and thus they can easily be plotted on"}, {"start": 2767.28, "end": 2771.64, "text": " a 2d chart like here and you can see that clusters like this one which have"}, {"start": 2771.64, "end": 2777.6, "text": " the same labels also appear in the same part of the space in this 2d space here"}, {"start": 2777.6, "end": 2782.88, "text": " so that's interesting that means that GCN can without any training already"}, {"start": 2782.88, "end": 2787.48, "text": " have some discriminative power just because of the graph structure and"}, {"start": 2787.48, "end": 2795.2799999999997, "text": " finally once you start training this GCN the through layer GCN I just mentioned"}, {"start": 2795.2799999999997, "end": 2799.56, "text": " you can see it gets you in better separation and finally after 300"}, {"start": 2799.56, "end": 2806.24, "text": " iterations the classes are clearly separated and that's that's awesome one"}, {"start": 2806.24, "end": 2812.24, "text": " more last thing is experimenting with depth so if you if you think about it all"}, {"start": 2812.24, "end": 2817.2799999999997, "text": " of the networks GCNs as I mentioned so far had either two or three layers so"}, {"start": 2817.2799999999997, "end": 2820.6, "text": " what's up what's up with that you know if you're familiar with computer vision"}, {"start": 2820.6, "end": 2826.16, "text": " you know that CNNs usually have bunch of layers like Resnets had I had 151 or"}, {"start": 2826.16, "end": 2830.9599999999996, "text": " more layers and basically here we'll use two or three so what's what's the thing"}, {"start": 2830.96, "end": 2836.36, "text": " so basically they showed here that and they've added these skip connections"}, {"start": 2836.36, "end": 2842.04, "text": " basically just adding the representations from the previous layer"}, {"start": 2842.04, "end": 2846.08, "text": " like this and this is the original equation so using these models they"}, {"start": 2846.08, "end": 2852.4, "text": " showed that after two or three layers we get to peak performance on the test and"}, {"start": 2852.4, "end": 2859.6, "text": " we don't need anything to go any further so and that's that's interesting and the"}, {"start": 2859.6, "end": 2863.7599999999998, "text": " the the explanation here you can you can search for it"}, {"start": 2863.7599999999998, "end": 2869.2799999999997, "text": " Michael Brunstein had a really nice blog wrote a nice blog about this and I'll"}, {"start": 2869.2799999999997, "end": 2875.2799999999997, "text": " just quickly summarize it so basically since grids are special graphs there"}, {"start": 2875.2799999999997, "end": 2879.4, "text": " certainly are examples of graphs on which depth helps it's just a quote from"}, {"start": 2879.4, "end": 2884.08, "text": " his blog and what that means is that pretty much you can treat image as a as"}, {"start": 2884.08, "end": 2890.08, "text": " a grid as a regular graph and we know that for images depth helps so that"}, {"start": 2890.08, "end": 2894.12, "text": " means there are certain classes of graphs where depth does help but here on"}, {"start": 2894.12, "end": 2899.72, "text": " these citation and knowledge graph graphs for some reason depth doesn't"}, {"start": 2899.72, "end": 2904.3199999999997, "text": " help and one of the explanation that Michael gave here is that one of the"}, {"start": 2904.3199999999997, "end": 2909.0, "text": " differences is that the letter letter are similar to small world networks with"}, {"start": 2909.0, "end": 2914.76, "text": " low diameter where one can reach any node from any other node in a few hops so"}, {"start": 2914.76, "end": 2918.84, "text": " you probably heard about this Facebook graph where at least I heard about it"}, {"start": 2918.84, "end": 2923.52, "text": " I'm not sure if the numbers are truly correct but like you can you can get to"}, {"start": 2923.52, "end": 2928.64, "text": " any single person on the graph on the Facebook graph by just in like six or"}, {"start": 2928.64, "end": 2932.44, "text": " seven hops so that means that the diameter of the of the Facebook graph"}, {"start": 2932.44, "end": 2935.8, "text": " is around seven I'm not sure if that's entirely correct but you get the point"}, {"start": 2935.8, "end": 2942.0800000000004, "text": " so it's so intricately connected that already after a couple of layers you've"}, {"start": 2942.0800000000004, "end": 2946.28, "text": " basically touched a lot of the neighborhoods neighborhood neighboring"}, {"start": 2946.28, "end": 2953.92, "text": " nodes and you don't need any more layers to to achieve better performance so"}, {"start": 2953.92, "end": 2958.5600000000004, "text": " that pretty much wraps it up hopefully you found this video useful I'm"}, {"start": 2958.5600000000004, "end": 2963.0, "text": " experimenting and I'm still figuring this out so if you have any feedback for"}, {"start": 2963.0, "end": 2969.68, "text": " me I really appreciate it I'll continue creating GNN videos throughout January"}, {"start": 2969.68, "end": 2974.2, "text": " and if you have any any requests please write them down in the comment section"}, {"start": 2974.2, "end": 2980.16, "text": " I'll try and maybe create some video depending on what you folks like"}, {"start": 2980.16, "end": 2984.52, "text": " suggest me if you like this video and if you found this channel useful please"}, {"start": 2984.52, "end": 2988.96, "text": " consider subscribing and click the bell icon to get notified when I upload a new"}, {"start": 2988.96, "end": 2994.2400000000002, "text": " video so that you can get my videos as soon as they get uploaded and until"}, {"start": 2994.24, "end": 3023.24, "text": " next time keep learning deep"}]