Graphormer - Do Transformers Really Perform Bad for Graph Representation? | Paper Explained
❤️ Become The AI Epiphany Patreon ❤️ ► https://www.patreon.com/theaiepiphany
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬

Paper: Do Transformers Really Perform Bad for Graph Representation?

In this video, I cover Graphormer a new transformer model that achieved SOTA results on the OGB large-scale challenge benchmark.

It achieved that by introducing 3 novel types of structural biases/encodings into the classic transformer encoder.

▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 
✅ Paper: https://arxiv.org/abs/2106.05234
✅ What can GNNs learn blog: https://andreasloukas.blog/2019/12/27/what-gnn-can-and-cannot-learn/
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 

⌚️ Timetable: 
00:00 Key points of the paper
02:15 Graph-level predictions and why we need structural information
05:35 GNNs basics
09:40 Centrality encoding explained in depth
14:15 Spatial encoding explained in depth
18:00 Edge encoding explained in depth
22:30 Results on OGB LSC
23:30 Graphormer handles over-smoothing
25:10 Other results and ablation study
28:20 Graphormer is more expressive than WL
30:30 Mean aggregation as a special case of Graphormer
35:00 Sum aggregation as a special case of Graphormer

▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 
💰 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! ❤️

Huge thank you to these AI Epiphany patreons:
Petar Veličković
Zvonimir Sabljic
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 

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

#graphormer #graphs #transformers
 What's up? In this video I'm covering this new paper called Do Transformers Really Perform Bad for Graph Representation? Introducing the Graformer model by Zhengxuan Jing, Jiang Lekai, Zhengjie Luo and others from... they did this as an internship at Microsoft Research Asia basically. So what is cool about this paper is that this is the first time that Transformer has outperformed classical graph neural networks on this important benchmark called OGB Large Scale Challenge. And the whole point of the paper, the whole idea is to encode structural inductive biases into the transformer model and they show that by adding three of those encodings they can actually outperform obviously those classical GNNs, which is super exciting. Having said that, so basically we up until now we knew that Transformers are really good for sequence modeling so they dominated the NLP world. Then recently we had the Vision Transformer entering the computer vision world but and outperforming like a bunch of different computer vision models. But like the only downside there was that it required a huge amount of pre-training so like it used 300M, a million data points to pre-train it. And a couple of days ago I have also covered this paper where the VIT, the Vision Transformer, used this sharpness aware minimization objective to actually not need any pre-training anymore and it still outperforms a resonant baselines, which is really cool. But up until now, up until Graphformer, we didn't have the same thing happening in the GraphML field where GNNs were dominating pretty much. And so let me just briefly show you how it looks pictorially. So they add three encodings. They have this thing called a centrality encoding. They used something called degree centrality. They also add these edge encoding and spatial encoding information directly as a bias before the softmax in the self-attention layer. And those just kind of encode the edge information as well as the structural information into the Graphformer model. And we'll soon see the details. But yeah, that was a high-level picture. So now let's start digging into the paper. So the Transformer architecture has become a dominant choice in many domains such as natural language processing and computer vision. Yet it has not achieved competitive performance on popular leaderboards of graph-level prediction compared to mainstream GNN variants. So just as a small digression here, what graph-level means is the following. So if you have a graph, a simple graph here, you can do multiple types of tasks on this graph. You can do node-wise, so node-level predictions. You can do edge-level predictions. Or you can do graph-level predictions. So a graph-level prediction would be if you have a molecule here. If this graph represents a certain molecule. So for the graph-level, you take into account all of the node and edge features and you try to regress maybe the solubility of this molecule. On the other hand, if you had edge prediction, for example, you could have multiple edges here and these nodes can be maybe drugs and you're trying to predict the side effect between you by using the two drugs together. And for example, you may regress that this edge has a probability of 0.9. That means that this side effect has a huge probability of occurring. On the other hand, this edge here may be un-plausible because the probability is only 0.001, for example. And that would be edge-level prediction task. But here we're focusing on graph-level prediction tasks and most of the benchmarks actually contain molecules, so that makes sense. Next up, our key insight to utilizing transformer in the graph is the necessity of effectively encoding the structural information of a graph into the model. So what it means is the following. So if you know how transformers work and you hopefully do, and I'll link the paper somewhere here so you can check it out and understand transformers, hopefully you do. But like this is a 101. Basically, if we have some sequence of tokens like this, and what transformers do, let me draw another one, is every single token will be attending to each other tokens including itself. It will be attending to this one, it will be attending to this one, it will be attending to this one. And the same goes for all of the other tokens. And as you can see, what it implicitly assumes is that the underlying data forms a fully connected graph. So if I can just redraw this in a bit different fashion, like this. And what happens is that transformer assumes that all of these tokens, nodes, whatever they may be, it can be image patches in the case of a vision transformer, they can be like subware tokens in the case of NLP. And so it assumes this structure. But sometimes when you have a molecule, for example, you know that the molecule is connected like this. You know that this is the connection. And you want to somehow encode this information into the transformer. And that's what the graph former did. And we'll soon see how those exactly look like, but that's the whole point. You want to ingrain the structural information into the transformer to make it more performant. Okay, and finally, many popular genome variants could be covered as a special cases of graph former and I'll later show you this in the appendix and I'll explain how this comes to be. Okay, having said that, let me just give you like a brief introduction to GNNs. If you're not familiar with them, I have a whole graph ML playlist. You can check it out. I'll link it somewhere here. But like, just let me shortly explain you how this works. So what you usually have is in this one family of graph neural networks called MPNNs. So you have this aggregation step and you have this combined step. And so let me draw a small graph here, something like this. And what happens is the following. So let me connect these like this. So these are the direct neighbors and we have some indirect neighbors. So what will happen is that for this, so every single node, so that's the first point, every single node and every single edge will have a certain feature vector associated with it. So why is that? Well, basically assume you have, assume this is like, these are atoms. So this graph represents a molecule. So this edge, this feature vector may contain the information such as is this a single bond, is this a double bond, is this an aromatic bond, etc. So that can be, as you can see, useful information encoded directly into the edge feature vector. So what you do is the following. So you have this, as I said, aggregate step. So what that does is the following. So it will take the neighbors, so either the one hop or the multi hop neighbors, but let's assume we have one hop neighborhood here. So that means that this i node will take into account this vector, this vector, this vector, as well as the edges. And it will somehow aggregate that information. So that may be like a mean. You basically add them up and you just divide them by the number of elements or like sum or whatever. There can be different aggregation methods. But once you have that, so again, you have the original feature vector here and you have the one you just formed by aggregation. And now the following step is this combined method. As you can see, so this is the aggregated one, so this is this one, and then you have the original one, that's this one. And you somehow combine them. So they can be maybe via MLP, you just pass them through a multilayer perceptron and you form a novel representation here, which will look something like this. Okay, so that will be how graph neural networks roughly work. And you then stack a bunch of these layers together. Finally, you have some, depending on the task, you just have some classification head, whatever, you back prop, you train these weights and that's it. So that's it. And now there is one more thing. If you want to do graph level prediction, what you usually do is you have this readout function. And what it does, as you can see, it just takes the nodes from the set of nodes of that graph and you just kind of combine them somehow. So again, you have layer one and you do, on the layer one, you do a processing that looks something like this. So you do those kind of aggregations and you combine them and you repeat that multiple times. So you have layer two all the way up until layer L, whatever that number may be. And then you take the node feature vectors from that layer and you, for example, sum them up and that will be a readout function. So you have a single vector which you can then use to maybe regress something or whatever. And so that's how the pipeline roughly looks like for graph neural networks. So now having said that, let me just briefly tell you about Transformer. And as I said, so I won't be delving into details here, but you have a couple of procedures here. So you basically first project your feature vectors into these query vectors, into key vectors, into value vectors. Then you find the similarity between the query and the keys and that will provide you with this attention scores, which then you apply just a softmax and you then use those attention coefficients to aggregate the value vectors. So that's just a high-level overview. As I said, you can watch my video to understand this. That's not the point of this paper. And now let's start digging into the encodings that's the meat of this paper. Okay, first up, let's see the centrality encoding. So node centralities is a really abstract concept. There can be many things and they concretely use something called degree centrality. We'll see that in a moment. But the rough notion is that those centrality measures tell you how important a certain node or an edge is in that particular graph. So they say it here in equation four, the equation four is just a transformer equation for like accumulating value vectors. The attention distribution is calculated based on the semantic correlation between nodes. So that's the query keys dot product. However node centrality, which measures how important a node is in the graph, is usually a strong signal for graph understanding. For example, celebrities who have a huge number of followers are important vectors in predicting the trend of a social network. As you can imagine, if Elon Musk tweets something, you can assume that a nice portion of the Twitter graph will be copy pasting his, retweeting his content. So you can kind of predict just because of a single node, you can predict the behavior of many other nodes. So that's maybe rough intuition for why this works. And as I mentioned, they're using degree centrality and that's a simple concept. So again, assume you have a node and assume you have some edges. So you have some ingoing edges, you have some outgoing edges here. So what node centrality is, is the following. So basically the out degree will be three here. As you can see, we have three edges. So that will mean we have out degree three and we'll have two ingoing edges. So the degree centrality of the, so of the in degree is two. So that's basically, so that's the number, that's the measure we want here. So for an influencer node, you'll have like thousands and thousands of these ingoing edges, which kind of signal that it's an important node. And how they include that information into this graph former is the following way. So as you can see, this is the original feature vector in your graph. And let me try and draw this. So again, you have a small graph here and it's connected with some other nodes. And so what happens is the following. You have the original, so this X side, that's the original feature vector. Okay. And you add up to that feature vector, these additional embeddings. So you basically form, what they do is they form a table which has two columns. So one column will correspond to the in degree vectors and the other will correspond to the out degree vector. And now if you focus on this specific node here, and yeah, assuming we have, assuming this one is maybe in degree, maybe these two, maybe these two is out, outgoing edge, you can see that we can basically form the degree numbers and we have two for the out degree and we have one for the in degree. And so using that information, we can basically index into this embedding table, which is initially just randomly initialized. So what we'll do is we'll have, as you can see here, so this will be zero slot, first slot, second slot. We'll just take this vector here and we'll add it directly to this one. So we'll just add it up to this one. And because we have one in degree, we'll go to the in degree column and we'll just index into this one. So this is one and we'll take this vector and we'll again add it up to this representation. Okay. So as you can see, that's basically what they do. And yeah, they say it here. Where Z minus and Z plus are d-dimensional real valued vectors, so our learnable embedding vector specified by the in degree and out degree respectively. So what this roughly does, now you can imagine if you had certain node, which is an influencer node, which had a bunch of these in going the edges, maybe thousand and you had another node that also had a thousand of these in degree edges. Okay. That means that they'll be indexing the same, the very same vector here will be used in both of those and that kind of can signal to this graph former that these are somehow special. That's the rough intuition behind all of this and because behind this first embedding embedding procedure. So the second thing which is really important is this spatial encoding and they say here, concretely for any graph G we consider a function Phi between VI and VJ. So we have node space and we had no space just a Cartesian product and we map that into real number. So which measures the spatial relation between VI and VJ in graph G. So this is very abstract. Let's make it a bit more concrete. So in this paper we choose Phi to be the distance of the shortest path. So the shortest path distance between VI and VJ if the two nodes are connected, if not, we set the output of Phi to be a special value, for example, minus one. Okay. Let's see what this practically means. So again, we have this equation. As you can see, this is basically transformer equation. We have just the dot product between. So this is the query vector. This is the key vector. We do a dot product. This is transposed and we just kind of scale it where D is the number of dimensions in those vectors. We just take a square root. Okay. So this is the transformer part and that's not that interesting. So what's interesting here is they add a bias. So this is a learnable scalar as they say here to encode this information of the structure in the graph and they do that by you can see here this Phi is used to index into this B array. So B will be again as we had the we had this embeddings here. Now we'll have similarly array that will call B and which will be able to index using this Phi where Phi is the shortest path between the any two points. So that means the following again, let me draw a simple diagram. So we have maybe something like let me draw like a path diagram. So we have a simple path diagram a path graph and as you can see the this node here will have so this this node here will be have a distance of one this note here will have a distance of two. So that's the shortest path and finally this one will have distance of three. So that means when we do when we form a query vector here and keys here what we'll do is the following. So we'll be adding so for this particular node here will be adding. Let me just change the color. So this is 0 1 2 3. So for this one will be using exactly this one will be using this scalar then for the second one will be using this scalar. So now you can imagine that this can help us learn some interesting stuff. So they say here for example, if B is learned to be a decreasing function with respect to Phi so as we so that what they say is as we go down this B array if this becomes like smaller and smaller so they say that for each note the model will likely pay more attention to the notes near it and pay less attention to the notes far away from it and in the extreme case imagine you have you have maybe 0 here for the first note and you have minus infinity for all of the other ones. So this is minus infinity what will happen is because you're adding those to the attention score after applying softmax all of those nodes which have minus infinity the attention coefficients will drop to 0. Whereas for this one it will be nonzero will be probably one. So in this particular graph, so we'll be focusing. So what we'll end up doing is focusing on only this note here and ignoring the other the rest of these. So if we had more neighbors more direct neighbors would be basically focusing only on the one hop neighborhood just because of this learnable scalar here. So that's the idea there. This is how they encode this structural information of the graph why these shortest path distance scalars. Okay, that's the second important encoding and the third one and the final one is this edge encoding and they said here there are mainly two edge encoding methods used in previous works in the first method the edge features are added to the associated nodes features in the second method for each node its associated edge feature will be used together with the node features in the aggregation. However, such ways of using edge feature only propagate the edge information to its associated nodes which may not be an effective way to leverage edge information in the representation of the whole graph. So in a nutshell what this means is the following. So if you have a if you have a graph again, let me draw a simple graph here. What they do is if you have a graph like this and when you do those aggregation and combine steps in the first layer of the GNN what will end up with what we'll end up doing is will be end up will end up including this information. So these two edges and information from these two nodes into this novel representation that will form here and we are ignoring these edges here. We're ignoring them in the first best least and what they are suggesting here is that it may be wise to kind of ingrain that information straight away and like during this aggregation process just kind of use that edge information from all of the other nodes and that's how they do that is the following. So again, you can see simple stuff. We have the transformer part. We have the spatially embedding part, which I just explained. And we have this novel edge encoding part, which is this fancy formula, which I'm now going to try to explain. So again, we'll have a embedding table. So we'll have a table which will correspond to these learnable edge features and like the length of this table will just be the following thing. The length will be the maximum shortest path in the graph. So you find all of the so between every single node in your graph, you find the shortest paths and you find the maximal such path and that will be the length of this table. Let's call it. I don't know maybe E and okay. So once we have that we do the following thing. So let's assume we want to find. So let's assume we are finding a tension score between I and J. So if this is I and if this node here is J, what we'll do is the following. So we'll have we'll have some feature vectors which are associated with these edges, right? So we'll have this and this and this and we'll do the following will take the first edge. So we'll have edges here. So these are again random initialize initially. So we have 123, etc. So we'll take this vector here will do a product between that vector and this vector here. So we'll do the product between those two because this is the first edge on the shortest path. So the shortest path is this one. So we have this is the shortest path between I and J. So we'll first do a dot product between those two. Then we'll take the following vector will do a dot product between that vector and this vector and we'll take the third vector because this is the third vector on this path and we'll do dot product and what we'll just do is we'll just sum them up as you can see here and divide them by n which is the number of edges in the path, which is 3 here. So these are the edge features. These are the learnable edge features and finally just sum them up and divide by n. That's it. And intuitively what this does is we ingrain the edge information across so between I and J along the shortest path and they show that in the ablation studies later that this helps boost the performance of the graph form model. Okay. So those are the main ideas of this paper. These three encodings and now I'll just again. So everything else remains the same as in the transformer model. They just ingrain these encodings. Everything else remains the same. You have the multi-head attention sub module. You have the FFN. So the fully the fully the feed-forward network module. You have the layer normalization standard stuff. So I won't go into those details and I'll skip this an interesting part for now which shows that classical GNNs can be considered as a special case of this graph form module. But before that let me show you the experiment results. So looking at the baselines here. So again, this is this large-scale challenge data set. It has 3.8 million graphs. So it's huge compared that to previous GNN popular graph ML benchmarks such as Quora sites here or PubMed and you'll see that this is much bigger and so much a much better benchmark compared to those. And we compare with GCN. So that's graph convolutional network with GINs with GCNs with the virtual node etc. And we have this is some modification of a transformer also an attempt to apply transformers to graph level prediction tasks, but not as successful as graph former as we'll see. So as you can see looking at the test, this is mean absolute error we achieve. So graph former achieves the lowest error on compared to all of these other classical GNNs. So those are some nice results and there's one thing I want to mention here. Let me just see where it is. It basically yeah, as stated in section 3.3 we further find the proposed reformer does not encounter the problem of over smoothing. I the train invalidate error keep going down along with the growth of depth and width of models. So now that this may be strange if you're not familiar with graph neural networks, but basically compared to CNNs where depth more depth basically take resonance for example, so the more depth you have the more expressive and powerful and performant the models are here in the GNN literature. Basically that doesn't necessarily help. So you usually see those shallow GNNs like two or three layer deep and those work just fine. So the reason for that are there are multiple reasons. So one of them is maybe bottleneck. So that means if you have if you take a look at the one hop neighborhood, you'll have maybe hundred neighbors. If you take a look at the two hop neighborhood, you may end up with 10,000 neighbors. If you take a look at the three hop neighborhoods, that's the third layer of the GNN. You'll maybe be attending to millions of notes and just but if you try and average all of those feature vectors, you'll end up basically collapsing into a single feature vector and that's something that's called over smoothing. So basically all of your feature vectors start collapsing into very same representation and thus you don't have the discriminative power to kind of figure out whatever the task at hand is. So maybe predict the solubility of the molecule whatever. So that's the over smoothing problem and it seems that Graphformer kind of dealt with it and I'd be really really excited. I'm really excited to see like what the future research shows and explains why this is. Finally, they also show some results on other OGP data sets. Again, these are mostly molecular data sets and you can see again, it just outperforms all of the other baselines. This flag is just a simple adversarial augmentation. So just that you know what this suffix means and yeah on zinc again lowest mean absolute error compared to the previous baselines. So that's that's pretty much it. They also did some ablations showing that all of these encodings boost up the performance. So this is the edge encoding as you can see the error drops when they added same goes for the nose centrality same goes for the spatial encoding. They always have these boosts in the performance when they add those particular encodings. Finally, as we know, basically transformers have problem with the scalability of these the vanilla transformer. We have this quadratic dependency between the tokens because of this attention attending mechanism and so the quadratic complexity of the self-attention modular stricts reformers application on large graphs, which is pretty much obvious. So that means that even though it achieved really nice results on these benchmarks, which are molecular data sets molecular graphs, I can imagine that this still can't be used to any like like huge graphs such as maybe social media graph. And so yeah, I can I just expect to see people kind of using the ideas that came from the transformer literature like lean former performer, etc. to kind of make this thing more efficient and then we'll see whether it can achieve some nice results even on larger graphs. Having said that, that's the those are the main ideas of this paper. And now I want to focus on this on this fact one and kind of delve a bit deeper into it and explain why this is. Okay, let's focus on this part by choosing proper weights and distance function five the graph former layer can represent aggregate and combine steps of popular gene and modules models such as gene GCN and graph sage. Moreover, we show further that by using our special encoding graph former can go beyond classic message passing gene ends whose expressive power is no more than the vice file a lemon one test. So by the way, there is a bit of confusion about this vice file a lemon test and the thing is all of these expressivity like statements basically only are valid for and so-called anonymous graph neural networks whereby anonymous. I mean that the node feature vectors are actually basically nonexistent or they are not discriminative. So that means where well by using standard graph neural networks, you always have those no features. So these analysis are not that they can be kind of tricky. I'll link this blog down in the description. You can see it on the screen which explains this problematic really good and kind of explains what a gene ends can learn and what they can learn and so do check it out. It's really really cool. Having said that let's focus on this part. How can we how can we treat these classical gene ends as a special case? Okay, but let's start first with this vice file a lemon thing. So so vice file a lemon or the color test basically what it does it it outputs color histogram and if the color case runs are the same it claims that those two graphs are isomorphic and we can clearly see that these two graphs here are not isomorphic but vice file a lemon tells us that they are isomorphic because we have four red colors and we have two blue colors and because of that vice file a lemon would falsely claim that these are isomorphic on the other hand if you focus on the shortest path distance, so let's let's see what I see here. So these two graphs cannot be distinguished by vice file a lemon one test by the SPD sets. I the SPD from each node to others are different the two types of nodes in the left graph have SPD sets as you can see here and let me explain let me kind of break it down for you what this means. So obviously the shortest path distance between this node this this red node and itself is zero. It has one distance until it reaches this distance these nodes and two for these two and finally three and as you can see here that's 0 1 1 2 2 3 and for all of the red nodes. We have the same SPD set. Okay, finally for this blue node again. We have trivially zero shortest path to itself. We have 1 1 1 here. So that's 3 1. So those are these ones here and finally we have to to which are these two and similarly goes for this graph here and we can see that the SPD sets are different thus this SPD will help us determine that these graphs are not isomorphic. I they are non isomorphic. So that's a like a visual explanation and a particular example where they showed the graph former is more powerful than those simple like vice versa lemon one test kind of architectures. Okay. Now let's focus on the really important part and that's these how we how can we basically show that GNN's are some GNN's are special case of graph of this graph or module. So let's focus on mean aggregate function and explaining how that works. So we begin by showing that self-attention module with spatial encoding can represent mean aggregation. This is achieved by in equation 6 settings. So this is equation 6. This is your transformer. This is your basically bias using this shortest path function. Okay, so by setting the scalar when Phi equals 1 so direct neighbors to 0 and to minus infinity otherwise where Phi is the shortest path distance and setting these two matrices so the query projection matrix and a key projection matrix to 0 matrix and the value projection matrix to identity matrix then the softmax gives the average represent of representations of the neighbors and let's let me let me try and break it down how this exactly works. It's quite a simple. So we have a note here. We have some direct neighbors. Let's say we have three direct neighbors. These are connected and finally, let's say we have some undirect indirect like neighbors. Okay, like these two. So what happens is the following. So as we know these will have and we are focusing on this node and trying to figure out the next layer presentation. So we can see that these nodes here have distance one and these nodes here have distance 2 and finally 3. Okay. So what I say is the following if we set these bees to 0. So if we set this one to 0 this one to 0 and this one to 0 and if we set these to minus infinity then as you can see looking at this formula here will have that after we apply softmax these will get to 0 and these will get will have some nonzero value and now the second portion is this these matrices should be zero matrices and the value should be identity that will help us achieve the the mean aggregation of neighbors. So let's see. So for now we just have some arbitrary nonzero values here and we have zeros here for the attention coefficients. So now let me let me do it like this. So let's focus on this particular node and so we have some feature vector once we map them this feature vector using the key query and value matrices will get the following thing. So query and key so key and query will just be zero vectors because remember we have zero matrices there and this one here because we have an identity matrix will be the same just a copy pasted version of this vector here. So this is V. This is we as well. So this is the value vector. Okay, and now we do the same thing for all of the nodes in the graph and as you can see if we take this query vector which is all zeros and we do adopt products between any of the keys because all the keys are also all zero vectors will always have this thing going to zero. So this this term in the equation will go to zero and finally as I already explained will have this bias terms will be zero for the local neighbors direct neighbors and minus infinity there. So that means we'll basically end up having the same coefficients here and that's going to be one over three. And these will be zero. So we'll only be will end up attending only these nodes here and we'll take a mean average of those three feature vectors. Okay, so if you're confused by one three, it's pretty simple. So it's just soft max thing. So you'll have E. So let's focus on for example on this note will have e raised to power of zero because that's the attention. That's the attention score we got and down in the denominator. We'll just have a sum and that sum will be equal to three because we'll have three times. You raised to the power of zero and we'll have two times. You raised to the power of minus infinity, which is obviously zero and that's why we achieve. That's why we discuss to one over three. And that means that yeah, basically those are the attention coefficients that this node will use to accumulate the value vectors of the direct neighbors and as you can see, we literally achieved this mean aggregation. So that was the first the first part. Now the sum aggregate part is pretty easy. Once we understand this first mean aggregate part, but let me let me let me zoom in a bit here and explain it. The summary Asian can be realized by first performing mean aggregation and then multiply the node degrees. We'll see what that means. So specifically the node degrees can be extracted from centrality encoding. So that's the degree encoding by an additional head and be concatenated to the representations after mean aggregation. Then the fully the feed-forward network module in graph former can represent the function of multiplying the degree of the dimensions of average representations by the universal approximation theorem of fully of fully feed-forward networks. Okay. So let me kind of break that down. It's pretty simple and I'll just draw it over this chart. So let's assume the first head gives us the mean representation for this vector. Okay, so we have that part and now what they say is the following let's take another head. So we have multiple attention heads. Remember this is transformer. So what that have will do it will learn how to extract the degree of this note, which is as you can see here just consider with some direct graphs. It's three. So we'll learn how to extract maybe something like a vector which will have all zeros and only three at the bottom here. Okay. And so how that will happen is the following. So remember this so this this vector here is formed by taking the original vector and adding to it those embeddings for the degree centrality. So basically will be adding those note those vectors which contain the degree information and this head can learn how to extract from this vector how to extract this number here. So that have will learn how to do that. And once we have that we do the following. We basically concatenate because if you remember how transformer works every single head attention head will basically output a representation. Those will get concatenated. Then we'll have some MLPs. So again, we'll have the following will have the mean representation and we'll have the degree of the node and then by this universal by this theorem of universal approximation theorem where these MLPs can basically like giving up enough width and depth. They can basically approximate any function. So what we get here is after mapping them. It can learn how to take this number. Let's say three and multiply it with every single feature dimension here. So with this thing with this thing with this thing with this thing and if we do that will just end up with a sum aggregation instead of a mean of irrigation. And hopefully this was clear enough. This is how I understood it basically. And yeah, if I'm wrong, feel free to comment down. But yeah, I think that's in a nutshell how it works. So similar thing for max aggregate similar thing for combine and mean readout. You can you can do it yourself. But this is the whole logic the whole point how this works. And yeah, we saw we can emulate these as a special case of graph warmer and that's super cool. Having said that if you like this video consider sharing subscribe and until next time. Bye bye.
[{"start": 0.0, "end": 3.2, "text": " What's up? In this video I'm covering this new paper called"}, {"start": 3.2, "end": 6.6000000000000005, "text": " Do Transformers Really Perform Bad for Graph Representation?"}, {"start": 6.6000000000000005, "end": 13.8, "text": " Introducing the Graformer model by Zhengxuan Jing, Jiang Lekai, Zhengjie Luo"}, {"start": 13.8, "end": 19.8, "text": " and others from... they did this as an internship at Microsoft Research Asia basically."}, {"start": 19.8, "end": 24.0, "text": " So what is cool about this paper is that this is the first time that"}, {"start": 24.0, "end": 31.0, "text": " Transformer has outperformed classical graph neural networks on this important"}, {"start": 31.0, "end": 36.4, "text": " benchmark called OGB Large Scale Challenge. And the whole point of the"}, {"start": 36.4, "end": 42.2, "text": " paper, the whole idea is to encode structural inductive biases into the"}, {"start": 42.2, "end": 46.6, "text": " transformer model and they show that by adding three of those encodings they can"}, {"start": 46.6, "end": 52.0, "text": " actually outperform obviously those classical GNNs, which is super exciting."}, {"start": 52.0, "end": 57.6, "text": " Having said that, so basically we up until now we knew that Transformers are"}, {"start": 57.6, "end": 62.6, "text": " really good for sequence modeling so they dominated the NLP world. Then recently"}, {"start": 62.6, "end": 67.4, "text": " we had the Vision Transformer entering the computer vision world but and"}, {"start": 67.4, "end": 71.6, "text": " outperforming like a bunch of different computer vision models. But like the only"}, {"start": 71.6, "end": 76.1, "text": " downside there was that it required a huge amount of pre-training so like it"}, {"start": 76.1, "end": 82.1, "text": " used 300M, a million data points to pre-train it. And a couple of days ago I"}, {"start": 82.1, "end": 86.3, "text": " have also covered this paper where the VIT, the Vision Transformer, used this"}, {"start": 86.3, "end": 92.0, "text": " sharpness aware minimization objective to actually not need any pre-training"}, {"start": 92.0, "end": 95.8, "text": " anymore and it still outperforms a resonant baselines, which is really cool."}, {"start": 95.8, "end": 99.39999999999999, "text": " But up until now, up until Graphformer, we didn't have the same thing"}, {"start": 99.39999999999999, "end": 104.0, "text": " happening in the GraphML field where GNNs were dominating pretty much. And so"}, {"start": 104.0, "end": 108.3, "text": " let me just briefly show you how it looks pictorially. So they add three"}, {"start": 108.3, "end": 111.8, "text": " encodings. They have this thing called a centrality encoding. They used something"}, {"start": 111.8, "end": 117.8, "text": " called degree centrality. They also add these edge encoding and spatial encoding"}, {"start": 117.8, "end": 122.4, "text": " information directly as a bias before the softmax in the self-attention layer."}, {"start": 122.4, "end": 127.3, "text": " And those just kind of encode the edge information as well as the structural"}, {"start": 127.3, "end": 133.0, "text": " information into the Graphformer model. And we'll soon see the details."}, {"start": 133.0, "end": 137.5, "text": " But yeah, that was a high-level picture. So now let's start digging into the paper."}, {"start": 137.5, "end": 142.6, "text": " So the Transformer architecture has become a dominant choice in many domains"}, {"start": 142.6, "end": 146.4, "text": " such as natural language processing and computer vision. Yet it has not achieved"}, {"start": 146.4, "end": 150.7, "text": " competitive performance on popular leaderboards of graph-level prediction"}, {"start": 150.7, "end": 156.0, "text": " compared to mainstream GNN variants. So just as a small digression here, what"}, {"start": 156.0, "end": 160.2, "text": " graph-level means is the following. So if you have a graph, a simple graph here,"}, {"start": 160.2, "end": 168.5, "text": " you can do multiple types of tasks on this graph. You can do node-wise, so"}, {"start": 168.5, "end": 172.1, "text": " node-level predictions. You can do edge-level predictions. Or you can do"}, {"start": 172.1, "end": 175.1, "text": " graph-level predictions. So a graph-level prediction would be if you have a"}, {"start": 175.1, "end": 178.89999999999998, "text": " molecule here. If this graph represents a certain molecule. So for the graph-level,"}, {"start": 178.89999999999998, "end": 182.79999999999998, "text": " you take into account all of the node and edge features and you try to"}, {"start": 182.79999999999998, "end": 187.0, "text": " regress maybe the solubility of this molecule. On the other hand, if you had"}, {"start": 187.0, "end": 191.0, "text": " edge prediction, for example, you could have multiple edges here and these nodes"}, {"start": 191.0, "end": 195.1, "text": " can be maybe drugs and you're trying to predict the side effect between you by"}, {"start": 195.1, "end": 198.8, "text": " using the two drugs together. And for example, you may regress that this edge"}, {"start": 198.8, "end": 202.6, "text": " has a probability of 0.9. That means that this side effect has a huge"}, {"start": 202.6, "end": 206.8, "text": " probability of occurring. On the other hand, this edge here may be"}, {"start": 206.8, "end": 212.2, "text": " un-plausible because the probability is only 0.001, for example. And that"}, {"start": 212.2, "end": 216.1, "text": " would be edge-level prediction task. But here we're focusing on graph-level"}, {"start": 216.1, "end": 219.9, "text": " prediction tasks and most of the benchmarks actually contain molecules, so"}, {"start": 219.9, "end": 223.7, "text": " that makes sense. Next up, our key insight to utilizing"}, {"start": 223.7, "end": 227.5, "text": " transformer in the graph is the necessity of effectively encoding the"}, {"start": 227.5, "end": 232.5, "text": " structural information of a graph into the model. So what it means is the"}, {"start": 232.5, "end": 235.9, "text": " following. So if you know how transformers work and you hopefully do, and"}, {"start": 235.9, "end": 239.0, "text": " I'll link the paper somewhere here so you can check it out and understand"}, {"start": 239.0, "end": 243.29999999999998, "text": " transformers, hopefully you do. But like this is a 101."}, {"start": 243.3, "end": 249.10000000000002, "text": " Basically, if we have some sequence of tokens like this, and what"}, {"start": 249.10000000000002, "end": 254.0, "text": " transformers do, let me draw another one, is every single token will be attending"}, {"start": 254.0, "end": 257.8, "text": " to each other tokens including itself. It will be attending to this one, it will"}, {"start": 257.8, "end": 261.6, "text": " be attending to this one, it will be attending to this one. And the same goes"}, {"start": 261.6, "end": 266.0, "text": " for all of the other tokens. And as you can see, what it implicitly assumes is"}, {"start": 266.0, "end": 271.1, "text": " that the underlying data forms a fully connected graph. So if I"}, {"start": 271.1, "end": 277.70000000000005, "text": " can just redraw this in a bit different fashion, like this. And what"}, {"start": 277.70000000000005, "end": 283.6, "text": " happens is that transformer assumes that all of these tokens, nodes, whatever"}, {"start": 283.6, "end": 287.0, "text": " they may be, it can be image patches in the case of a vision transformer, they"}, {"start": 287.0, "end": 292.40000000000003, "text": " can be like subware tokens in the case of NLP. And so it assumes this"}, {"start": 292.40000000000003, "end": 296.8, "text": " structure. But sometimes when you have a molecule, for example, you know that the"}, {"start": 296.8, "end": 302.0, "text": " molecule is connected like this. You know that this is the connection. And you"}, {"start": 302.0, "end": 306.90000000000003, "text": " want to somehow encode this information into the transformer. And that's what"}, {"start": 306.90000000000003, "end": 312.1, "text": " the graph former did. And we'll soon see how those exactly look like, but that's"}, {"start": 312.1, "end": 315.3, "text": " the whole point. You want to ingrain the structural information into the"}, {"start": 315.3, "end": 320.8, "text": " transformer to make it more performant."}, {"start": 320.8, "end": 325.6, "text": " Okay, and finally, many popular genome variants could be covered as a special"}, {"start": 325.6, "end": 328.8, "text": " cases of graph former and I'll later show you this in the appendix and I'll"}, {"start": 328.8, "end": 334.1, "text": " explain how this comes to be. Okay, having said that, let me just give you"}, {"start": 334.1, "end": 339.20000000000005, "text": " like a brief introduction to GNNs. If you're not familiar with them, I have a"}, {"start": 339.20000000000005, "end": 342.90000000000003, "text": " whole graph ML playlist. You can check it out. I'll link it somewhere here."}, {"start": 342.90000000000003, "end": 349.1, "text": " But like, just let me shortly explain you how this works. So what you usually"}, {"start": 349.1, "end": 355.0, "text": " have is in this one family of graph neural networks called MPNNs. So"}, {"start": 355.0, "end": 360.5, "text": " you have this aggregation step and you have this combined step. And so let me"}, {"start": 360.5, "end": 367.5, "text": " draw a small graph here, something like this. And what happens is the following."}, {"start": 367.5, "end": 371.1, "text": " So let me connect these like this. So these are the direct neighbors and we"}, {"start": 371.1, "end": 376.4, "text": " have some indirect neighbors. So what will happen is that for this, so every"}, {"start": 376.4, "end": 380.5, "text": " single node, so that's the first point, every single node and every single edge"}, {"start": 380.5, "end": 384.6, "text": " will have a certain feature vector associated with it. So why is that? Well,"}, {"start": 384.6, "end": 389.1, "text": " basically assume you have, assume this is like, these are atoms. So this graph"}, {"start": 389.1, "end": 393.6, "text": " represents a molecule. So this edge, this feature vector may contain the"}, {"start": 393.6, "end": 397.5, "text": " information such as is this a single bond, is this a double bond, is this an"}, {"start": 397.5, "end": 401.70000000000005, "text": " aromatic bond, etc. So that can be, as you can see, useful information encoded"}, {"start": 401.70000000000005, "end": 406.1, "text": " directly into the edge feature vector. So what you do is the following. So you"}, {"start": 406.1, "end": 410.20000000000005, "text": " have this, as I said, aggregate step. So what that does is the following. So it"}, {"start": 410.2, "end": 414.59999999999997, "text": " will take the neighbors, so either the one hop or the multi hop neighbors, but"}, {"start": 414.59999999999997, "end": 417.5, "text": " let's assume we have one hop neighborhood here. So that means that this"}, {"start": 417.5, "end": 422.4, "text": " i node will take into account this vector, this vector, this vector, as well"}, {"start": 422.4, "end": 427.59999999999997, "text": " as the edges. And it will somehow aggregate that information. So that may"}, {"start": 427.59999999999997, "end": 431.4, "text": " be like a mean. You basically add them up and you just divide them by the number"}, {"start": 431.4, "end": 436.09999999999997, "text": " of elements or like sum or whatever. There can be different aggregation methods."}, {"start": 436.1, "end": 442.0, "text": " But once you have that, so again, you have the original feature vector here and"}, {"start": 442.0, "end": 447.0, "text": " you have the one you just formed by aggregation. And now the following step"}, {"start": 447.0, "end": 451.0, "text": " is this combined method. As you can see, so this is the aggregated one, so this is"}, {"start": 451.0, "end": 456.5, "text": " this one, and then you have the original one, that's this one. And you somehow"}, {"start": 456.5, "end": 461.0, "text": " combine them. So they can be maybe via MLP, you just pass them through a"}, {"start": 461.0, "end": 465.6, "text": " multilayer perceptron and you form a novel representation here, which will"}, {"start": 465.6, "end": 471.90000000000003, "text": " look something like this. Okay, so that will be how graph neural networks"}, {"start": 471.90000000000003, "end": 475.6, "text": " roughly work. And you then stack a bunch of these layers together. Finally, you"}, {"start": 475.6, "end": 479.0, "text": " have some, depending on the task, you just have some classification head,"}, {"start": 479.0, "end": 484.20000000000005, "text": " whatever, you back prop, you train these weights and that's it. So that's"}, {"start": 484.20000000000005, "end": 488.6, "text": " it. And now there is one more thing. If you want to do graph level prediction,"}, {"start": 488.6, "end": 492.0, "text": " what you usually do is you have this readout function. And what it does, as"}, {"start": 492.0, "end": 497.0, "text": " you can see, it just takes the nodes from the set of nodes of that graph and"}, {"start": 497.0, "end": 503.8, "text": " you just kind of combine them somehow. So again, you have layer one and you do, on"}, {"start": 503.8, "end": 507.1, "text": " the layer one, you do a processing that looks something like this. So you do"}, {"start": 507.1, "end": 512.0, "text": " those kind of aggregations and you combine them and you repeat that"}, {"start": 512.0, "end": 517.1, "text": " multiple times. So you have layer two all the way up until layer L, whatever that"}, {"start": 517.1, "end": 522.1, "text": " number may be. And then you take the node feature vectors from that layer and"}, {"start": 522.1, "end": 525.6, "text": " you, for example, sum them up and that will be a readout function. So you have"}, {"start": 525.6, "end": 531.6, "text": " a single vector which you can then use to maybe regress something or whatever."}, {"start": 531.6, "end": 535.8000000000001, "text": " And so that's how the pipeline roughly looks like for graph neural"}, {"start": 535.8000000000001, "end": 539.7, "text": " networks. So now having said that, let me just briefly tell you about"}, {"start": 539.7, "end": 543.9, "text": " Transformer. And as I said, so I won't be delving into details here, but you"}, {"start": 543.9, "end": 548.1999999999999, "text": " have a couple of procedures here. So you basically first project your feature"}, {"start": 548.1999999999999, "end": 552.6, "text": " vectors into these query vectors, into key vectors, into value vectors. Then you"}, {"start": 552.6, "end": 557.6, "text": " find the similarity between the query and the keys and that will provide you"}, {"start": 557.6, "end": 563.6, "text": " with this attention scores, which then you apply just a softmax and you then"}, {"start": 563.6, "end": 569.4, "text": " use those attention coefficients to aggregate the value vectors. So that's"}, {"start": 569.4, "end": 573.3, "text": " just a high-level overview. As I said, you can watch my video to understand this."}, {"start": 573.3, "end": 578.4, "text": " That's not the point of this paper. And now let's start digging into the"}, {"start": 578.4, "end": 582.3, "text": " encodings that's the meat of this paper. Okay, first up, let's see the centrality"}, {"start": 582.3, "end": 588.9, "text": " encoding. So node centralities is a really abstract concept."}, {"start": 588.9, "end": 593.0999999999999, "text": " There can be many things and they concretely use something called degree"}, {"start": 593.0999999999999, "end": 596.6999999999999, "text": " centrality. We'll see that in a moment. But the rough notion is that those"}, {"start": 596.7, "end": 603.3000000000001, "text": " centrality measures tell you how important a certain node or an edge is in"}, {"start": 603.3000000000001, "end": 607.3000000000001, "text": " that particular graph. So they say it here in equation four, the equation four"}, {"start": 607.3000000000001, "end": 612.4000000000001, "text": " is just a transformer equation for like accumulating value vectors. The"}, {"start": 612.4000000000001, "end": 615.6, "text": " attention distribution is calculated based on the semantic correlation"}, {"start": 615.6, "end": 620.6, "text": " between nodes. So that's the query keys dot product. However node centrality,"}, {"start": 620.6, "end": 625.1, "text": " which measures how important a node is in the graph, is usually a strong signal"}, {"start": 625.1, "end": 628.7, "text": " for graph understanding. For example, celebrities who have a huge number of"}, {"start": 628.7, "end": 632.3000000000001, "text": " followers are important vectors in predicting the trend of a social"}, {"start": 632.3000000000001, "end": 637.0, "text": " network. As you can imagine, if Elon Musk tweets something, you can assume"}, {"start": 637.0, "end": 641.9, "text": " that a nice portion of the Twitter graph will be copy pasting his, retweeting"}, {"start": 641.9, "end": 645.3000000000001, "text": " his content. So you can kind of predict just because of a single node, you can"}, {"start": 645.3000000000001, "end": 649.5, "text": " predict the behavior of many other nodes. So that's maybe rough intuition"}, {"start": 649.5, "end": 653.5, "text": " for why this works. And as I mentioned, they're using degree centrality and"}, {"start": 653.5, "end": 657.7, "text": " that's a simple concept. So again, assume you have a node and assume you"}, {"start": 657.7, "end": 661.7, "text": " have some edges. So you have some ingoing edges, you have some outgoing"}, {"start": 661.7, "end": 667.8, "text": " edges here. So what node centrality is, is the following. So basically the"}, {"start": 667.8, "end": 671.7, "text": " out degree will be three here. As you can see, we have three edges. So that"}, {"start": 671.7, "end": 677.4, "text": " will mean we have out degree three and we'll have two ingoing edges. So the"}, {"start": 677.4, "end": 681.8, "text": " degree centrality of the, so of the in degree is two. So that's basically,"}, {"start": 681.8, "end": 686.0, "text": " so that's the number, that's the measure we want here. So for an influencer"}, {"start": 686.0, "end": 689.6999999999999, "text": " node, you'll have like thousands and thousands of these ingoing edges,"}, {"start": 689.9, "end": 693.9, "text": " which kind of signal that it's an important node. And how they include"}, {"start": 693.9, "end": 697.9, "text": " that information into this graph former is the following way. So as you can"}, {"start": 697.9, "end": 701.9, "text": " see, this is the original feature vector in your graph. And let me try and"}, {"start": 701.9, "end": 707.5999999999999, "text": " draw this. So again, you have a small graph here and it's connected with"}, {"start": 707.6, "end": 715.0, "text": " some other nodes. And so what happens is the following. You have the"}, {"start": 715.0, "end": 721.2, "text": " original, so this X side, that's the original feature vector. Okay. And you"}, {"start": 721.2, "end": 726.7, "text": " add up to that feature vector, these additional embeddings. So you basically"}, {"start": 726.7, "end": 732.1, "text": " form, what they do is they form a table which has two columns. So one"}, {"start": 732.1, "end": 736.4, "text": " column will correspond to the in degree vectors and the other will"}, {"start": 736.4, "end": 740.8, "text": " correspond to the out degree vector. And now if you focus on this specific"}, {"start": 740.8, "end": 748.1999999999999, "text": " node here, and yeah, assuming we have, assuming this one is maybe in"}, {"start": 748.1999999999999, "end": 753.5, "text": " degree, maybe these two, maybe these two is out, outgoing edge, you can"}, {"start": 753.5, "end": 759.5, "text": " see that we can basically form the degree numbers and we have two"}, {"start": 759.6, "end": 764.6999999999999, "text": " for the out degree and we have one for the in degree. And so using that"}, {"start": 764.7, "end": 767.9000000000001, "text": " information, we can basically index into this embedding table, which is"}, {"start": 767.9000000000001, "end": 772.5, "text": " initially just randomly initialized. So what we'll do is we'll have, as"}, {"start": 772.5, "end": 778.3000000000001, "text": " you can see here, so this will be zero slot, first slot, second slot."}, {"start": 778.6, "end": 783.0, "text": " We'll just take this vector here and we'll add it directly to this one."}, {"start": 783.2, "end": 787.8000000000001, "text": " So we'll just add it up to this one. And because we have one in degree,"}, {"start": 788.0, "end": 792.1, "text": " we'll go to the in degree column and we'll just index into this one."}, {"start": 792.1, "end": 796.8000000000001, "text": " So this is one and we'll take this vector and we'll again add it up to"}, {"start": 796.8000000000001, "end": 798.0, "text": " this representation."}, {"start": 798.0, "end": 804.0, "text": " Okay. So as you can see, that's basically what they do. And yeah, they"}, {"start": 804.0, "end": 808.8000000000001, "text": " say it here. Where Z minus and Z plus are d-dimensional real valued"}, {"start": 808.8000000000001, "end": 812.3000000000001, "text": " vectors, so our learnable embedding vector specified by the in degree"}, {"start": 812.3000000000001, "end": 813.8000000000001, "text": " and out degree respectively."}, {"start": 814.1, "end": 817.4, "text": " So what this roughly does, now you can imagine if you had certain"}, {"start": 817.4, "end": 821.5, "text": " node, which is an influencer node, which had a bunch of these in going"}, {"start": 821.5, "end": 825.6, "text": " the edges, maybe thousand and you had another node that also had a"}, {"start": 825.6, "end": 827.9, "text": " thousand of these in degree edges."}, {"start": 828.4, "end": 828.9, "text": " Okay."}, {"start": 830.0, "end": 834.1, "text": " That means that they'll be indexing the same, the very same"}, {"start": 835.4, "end": 841.5, "text": " vector here will be used in both of those and that kind of can signal"}, {"start": 841.5, "end": 845.4, "text": " to this graph former that these are somehow special."}, {"start": 846.2, "end": 849.8, "text": " That's the rough intuition behind all of this and because behind this"}, {"start": 849.8, "end": 852.5999999999999, "text": " first embedding embedding procedure."}, {"start": 852.9, "end": 855.9, "text": " So the second thing which is really important is this spatial encoding"}, {"start": 856.1999999999999, "end": 859.8, "text": " and they say here, concretely for any graph G we consider a function"}, {"start": 860.0, "end": 862.3, "text": " Phi between VI and VJ."}, {"start": 862.4, "end": 866.6999999999999, "text": " So we have node space and we had no space just a Cartesian product"}, {"start": 866.6999999999999, "end": 868.1999999999999, "text": " and we map that into real number."}, {"start": 868.3, "end": 872.1999999999999, "text": " So which measures the spatial relation between VI and VJ in graph G."}, {"start": 872.1999999999999, "end": 873.5999999999999, "text": " So this is very abstract."}, {"start": 873.5999999999999, "end": 874.9, "text": " Let's make it a bit more concrete."}, {"start": 874.9, "end": 879.9, "text": " So in this paper we choose Phi to be the distance of the shortest path."}, {"start": 879.9, "end": 884.1999999999999, "text": " So the shortest path distance between VI and VJ if the two nodes are"}, {"start": 884.1999999999999, "end": 887.3, "text": " connected, if not, we set the output of Phi to be a special value,"}, {"start": 887.3, "end": 888.4, "text": " for example, minus one."}, {"start": 888.6999999999999, "end": 889.1999999999999, "text": " Okay."}, {"start": 889.3, "end": 890.6999999999999, "text": " Let's see what this practically means."}, {"start": 890.6999999999999, "end": 893.0, "text": " So again, we have this equation."}, {"start": 893.9, "end": 896.0, "text": " As you can see, this is basically transformer equation."}, {"start": 897.0, "end": 898.6999999999999, "text": " We have just the dot product between."}, {"start": 898.9, "end": 900.1999999999999, "text": " So this is the query vector."}, {"start": 900.1999999999999, "end": 901.1999999999999, "text": " This is the key vector."}, {"start": 901.1999999999999, "end": 902.3, "text": " We do a dot product."}, {"start": 902.3, "end": 906.4, "text": " This is transposed and we just kind of scale it where D is the number"}, {"start": 906.4, "end": 908.0, "text": " of dimensions in those vectors."}, {"start": 908.6999999999999, "end": 909.6999999999999, "text": " We just take a square root."}, {"start": 909.6999999999999, "end": 910.1999999999999, "text": " Okay."}, {"start": 910.3, "end": 912.5, "text": " So this is the transformer part and that's not that interesting."}, {"start": 912.6999999999999, "end": 915.0, "text": " So what's interesting here is they add a bias."}, {"start": 915.0999999999999, "end": 920.3, "text": " So this is a learnable scalar as they say here to encode this information"}, {"start": 920.5, "end": 925.0, "text": " of the structure in the graph and they do that by you can see here"}, {"start": 925.0, "end": 929.3, "text": " this Phi is used to index into this B array."}, {"start": 929.3, "end": 934.1999999999999, "text": " So B will be again as we had the we had this embeddings here."}, {"start": 934.1999999999999, "end": 940.4, "text": " Now we'll have similarly array that will call B and which will be able"}, {"start": 940.4, "end": 944.1999999999999, "text": " to index using this Phi where Phi is the shortest path between the"}, {"start": 944.1999999999999, "end": 945.0, "text": " any two points."}, {"start": 945.1999999999999, "end": 948.0, "text": " So that means the following again, let me draw a simple diagram."}, {"start": 948.0, "end": 952.3, "text": " So we have maybe something like let me draw like a path diagram."}, {"start": 952.3, "end": 957.8, "text": " So we have a simple path diagram a path graph and as you can see the"}, {"start": 957.8, "end": 962.8, "text": " this node here will have so this this node here will be have a distance"}, {"start": 962.8, "end": 965.5, "text": " of one this note here will have a distance of two."}, {"start": 965.5999999999999, "end": 968.1999999999999, "text": " So that's the shortest path and finally this one will have distance"}, {"start": 968.1999999999999, "end": 968.6999999999999, "text": " of three."}, {"start": 969.0, "end": 973.8, "text": " So that means when we do when we form a query vector here and keys"}, {"start": 973.8, "end": 976.5, "text": " here what we'll do is the following."}, {"start": 976.5, "end": 981.0999999999999, "text": " So we'll be adding so for this particular node here will be adding."}, {"start": 981.5, "end": 982.8, "text": " Let me just change the color."}, {"start": 982.8, "end": 989.0999999999999, "text": " So this is 0 1 2 3."}, {"start": 989.3, "end": 993.1999999999999, "text": " So for this one will be using exactly this one will be using this"}, {"start": 993.1999999999999, "end": 998.9, "text": " scalar then for the second one will be using this scalar."}, {"start": 999.0999999999999, "end": 1004.8, "text": " So now you can imagine that this can help us learn some interesting"}, {"start": 1004.8, "end": 1005.0999999999999, "text": " stuff."}, {"start": 1005.0999999999999, "end": 1009.8, "text": " So they say here for example, if B is learned to be a decreasing"}, {"start": 1009.8, "end": 1014.4, "text": " function with respect to Phi so as we so that what they say is as"}, {"start": 1014.4, "end": 1019.5999999999999, "text": " we go down this B array if this becomes like smaller and smaller"}, {"start": 1020.0, "end": 1024.3999999999999, "text": " so they say that for each note the model will likely pay more attention"}, {"start": 1024.3999999999999, "end": 1027.8999999999999, "text": " to the notes near it and pay less attention to the notes far away"}, {"start": 1027.8999999999999, "end": 1033.0, "text": " from it and in the extreme case imagine you have you have maybe 0"}, {"start": 1033.0, "end": 1036.8999999999999, "text": " here for the first note and you have minus infinity for all of the"}, {"start": 1036.8999999999999, "end": 1037.5, "text": " other ones."}, {"start": 1037.5, "end": 1041.5, "text": " So this is minus infinity what will happen is because you're adding"}, {"start": 1041.5, "end": 1046.0, "text": " those to the attention score after applying softmax all of those"}, {"start": 1046.0, "end": 1049.5, "text": " nodes which have minus infinity the attention coefficients will"}, {"start": 1049.5, "end": 1050.3, "text": " drop to 0."}, {"start": 1050.3, "end": 1053.6, "text": " Whereas for this one it will be nonzero will be probably one."}, {"start": 1053.6, "end": 1056.6, "text": " So in this particular graph, so we'll be focusing."}, {"start": 1056.6, "end": 1062.0, "text": " So what we'll end up doing is focusing on only this note here and"}, {"start": 1062.0, "end": 1064.0, "text": " ignoring the other the rest of these."}, {"start": 1064.0, "end": 1068.3, "text": " So if we had more neighbors more direct neighbors would be basically"}, {"start": 1068.3, "end": 1072.6, "text": " focusing only on the one hop neighborhood just because of this"}, {"start": 1072.6, "end": 1074.4, "text": " learnable scalar here."}, {"start": 1074.4, "end": 1076.0, "text": " So that's the idea there."}, {"start": 1076.0, "end": 1081.0, "text": " This is how they encode this structural information of the graph"}, {"start": 1081.0, "end": 1084.2, "text": " why these shortest path distance scalars."}, {"start": 1084.2, "end": 1088.7, "text": " Okay, that's the second important encoding and the third one and"}, {"start": 1088.7, "end": 1092.7, "text": " the final one is this edge encoding and they said here there are"}, {"start": 1092.7, "end": 1096.1000000000001, "text": " mainly two edge encoding methods used in previous works in the"}, {"start": 1096.1000000000001, "end": 1099.6000000000001, "text": " first method the edge features are added to the associated nodes"}, {"start": 1099.6000000000001, "end": 1102.9, "text": " features in the second method for each node its associated edge"}, {"start": 1102.9, "end": 1106.0, "text": " feature will be used together with the node features in the"}, {"start": 1106.0, "end": 1106.7, "text": " aggregation."}, {"start": 1107.1000000000001, "end": 1110.6000000000001, "text": " However, such ways of using edge feature only propagate the edge"}, {"start": 1110.6000000000001, "end": 1114.2, "text": " information to its associated nodes which may not be an effective"}, {"start": 1114.2, "end": 1117.6000000000001, "text": " way to leverage edge information in the representation of the whole"}, {"start": 1117.6000000000001, "end": 1118.1000000000001, "text": " graph."}, {"start": 1118.4, "end": 1121.7, "text": " So in a nutshell what this means is the following."}, {"start": 1121.7, "end": 1125.6000000000001, "text": " So if you have a if you have a graph again, let me draw a simple"}, {"start": 1125.6000000000001, "end": 1126.3, "text": " graph here."}, {"start": 1127.9, "end": 1132.8, "text": " What they do is if you have a graph like this and when you do"}, {"start": 1132.8, "end": 1135.5, "text": " those aggregation and combine steps in the first layer of the"}, {"start": 1135.5, "end": 1139.3, "text": " GNN what will end up with what we'll end up doing is will be end"}, {"start": 1139.3, "end": 1142.2, "text": " up will end up including this information."}, {"start": 1142.2, "end": 1146.6000000000001, "text": " So these two edges and information from these two nodes into"}, {"start": 1146.6000000000001, "end": 1150.8, "text": " this novel representation that will form here and we are ignoring"}, {"start": 1150.8, "end": 1152.0, "text": " these edges here."}, {"start": 1152.0, "end": 1155.2, "text": " We're ignoring them in the first best least and what they are"}, {"start": 1155.2, "end": 1159.6, "text": " suggesting here is that it may be wise to kind of ingrain that"}, {"start": 1159.6, "end": 1164.3999999999999, "text": " information straight away and like during this aggregation process"}, {"start": 1164.3999999999999, "end": 1167.8999999999999, "text": " just kind of use that edge information from all of the other"}, {"start": 1167.8999999999999, "end": 1171.8, "text": " nodes and that's how they do that is the following."}, {"start": 1171.8, "end": 1174.5, "text": " So again, you can see simple stuff."}, {"start": 1174.5, "end": 1176.3, "text": " We have the transformer part."}, {"start": 1176.3, "end": 1179.7, "text": " We have the spatially embedding part, which I just explained."}, {"start": 1179.7, "end": 1185.7, "text": " And we have this novel edge encoding part, which is this fancy"}, {"start": 1185.7, "end": 1187.9, "text": " formula, which I'm now going to try to explain."}, {"start": 1187.9, "end": 1190.1000000000001, "text": " So again, we'll have a embedding table."}, {"start": 1190.1000000000001, "end": 1194.4, "text": " So we'll have a table which will correspond to these learnable"}, {"start": 1194.4, "end": 1197.9, "text": " edge features and like the length of this table will just be"}, {"start": 1197.9, "end": 1198.6000000000001, "text": " the following thing."}, {"start": 1198.6000000000001, "end": 1201.8, "text": " The length will be the maximum shortest path in the graph."}, {"start": 1201.8, "end": 1205.2, "text": " So you find all of the so between every single node in your"}, {"start": 1205.2, "end": 1208.3, "text": " graph, you find the shortest paths and you find the maximal"}, {"start": 1208.3, "end": 1211.3, "text": " such path and that will be the length of this table."}, {"start": 1211.3, "end": 1211.8, "text": " Let's call it."}, {"start": 1211.8, "end": 1215.1, "text": " I don't know maybe E and okay."}, {"start": 1215.1, "end": 1217.1, "text": " So once we have that we do the following thing."}, {"start": 1217.1, "end": 1219.8999999999999, "text": " So let's assume we want to find."}, {"start": 1219.8999999999999, "end": 1223.6, "text": " So let's assume we are finding a tension score between I and J."}, {"start": 1223.6, "end": 1228.8, "text": " So if this is I and if this node here is J, what we'll do is"}, {"start": 1228.8, "end": 1229.3, "text": " the following."}, {"start": 1229.3, "end": 1234.1, "text": " So we'll have we'll have some feature vectors which are associated"}, {"start": 1234.1, "end": 1235.1, "text": " with these edges, right?"}, {"start": 1235.1, "end": 1239.1, "text": " So we'll have this and this and this and we'll do the following"}, {"start": 1239.1, "end": 1241.6, "text": " will take the first edge."}, {"start": 1241.6, "end": 1243.1999999999998, "text": " So we'll have edges here."}, {"start": 1243.1999999999998, "end": 1246.3, "text": " So these are again random initialize initially."}, {"start": 1246.3, "end": 1251.3, "text": " So we have 123, etc."}, {"start": 1251.3, "end": 1256.0, "text": " So we'll take this vector here will do a product between that"}, {"start": 1256.0, "end": 1257.6, "text": " vector and this vector here."}, {"start": 1257.6, "end": 1261.5, "text": " So we'll do the product between those two because this is the"}, {"start": 1261.5, "end": 1263.3, "text": " first edge on the shortest path."}, {"start": 1263.3, "end": 1265.6, "text": " So the shortest path is this one."}, {"start": 1265.6, "end": 1268.8, "text": " So we have this is the shortest path between I and J."}, {"start": 1268.8, "end": 1271.3999999999999, "text": " So we'll first do a dot product between those two."}, {"start": 1271.3999999999999, "end": 1274.3, "text": " Then we'll take the following vector will do a dot product"}, {"start": 1274.3, "end": 1277.3, "text": " between that vector and this vector and we'll take the third"}, {"start": 1277.3, "end": 1281.3, "text": " vector because this is the third vector on this path and"}, {"start": 1281.3, "end": 1284.8, "text": " we'll do dot product and what we'll just do is we'll just sum"}, {"start": 1284.8, "end": 1288.1, "text": " them up as you can see here and divide them by n which is the"}, {"start": 1288.1, "end": 1291.3999999999999, "text": " number of edges in the path, which is 3 here."}, {"start": 1291.4, "end": 1294.9, "text": " So these are the edge features."}, {"start": 1294.9, "end": 1300.1000000000001, "text": " These are the learnable edge features and finally just sum"}, {"start": 1300.1000000000001, "end": 1301.8000000000002, "text": " them up and divide by n."}, {"start": 1301.8000000000002, "end": 1302.7, "text": " That's it."}, {"start": 1302.7, "end": 1306.0, "text": " And intuitively what this does is we ingrain the edge"}, {"start": 1306.0, "end": 1311.1000000000001, "text": " information across so between I and J along the shortest path"}, {"start": 1311.1000000000001, "end": 1313.8000000000002, "text": " and they show that in the ablation studies later that this"}, {"start": 1313.8000000000002, "end": 1316.5, "text": " helps boost the performance of the graph form model."}, {"start": 1316.5, "end": 1317.7, "text": " Okay."}, {"start": 1317.7, "end": 1320.6000000000001, "text": " So those are the main ideas of this paper."}, {"start": 1320.6, "end": 1324.1999999999998, "text": " These three encodings and now I'll just again."}, {"start": 1324.1999999999998, "end": 1328.3, "text": " So everything else remains the same as in the transformer model."}, {"start": 1328.3, "end": 1330.0, "text": " They just ingrain these encodings."}, {"start": 1330.0, "end": 1331.3, "text": " Everything else remains the same."}, {"start": 1331.3, "end": 1333.6, "text": " You have the multi-head attention sub module."}, {"start": 1333.6, "end": 1334.5, "text": " You have the FFN."}, {"start": 1334.5, "end": 1338.5, "text": " So the fully the fully the feed-forward network module."}, {"start": 1338.5, "end": 1340.8, "text": " You have the layer normalization standard stuff."}, {"start": 1340.8, "end": 1343.6, "text": " So I won't go into those details and I'll skip this an"}, {"start": 1343.6, "end": 1348.1, "text": " interesting part for now which shows that classical GNNs can"}, {"start": 1348.1, "end": 1351.0, "text": " be considered as a special case of this graph form module."}, {"start": 1351.0, "end": 1355.3, "text": " But before that let me show you the experiment results."}, {"start": 1355.3, "end": 1357.6999999999998, "text": " So looking at the baselines here."}, {"start": 1357.6999999999998, "end": 1361.6999999999998, "text": " So again, this is this large-scale challenge data set."}, {"start": 1361.6999999999998, "end": 1364.3999999999999, "text": " It has 3.8 million graphs."}, {"start": 1364.3999999999999, "end": 1368.6999999999998, "text": " So it's huge compared that to previous GNN popular graph ML"}, {"start": 1368.6999999999998, "end": 1372.6999999999998, "text": " benchmarks such as Quora sites here or PubMed and you'll see"}, {"start": 1372.6999999999998, "end": 1376.1999999999998, "text": " that this is much bigger and so much a much better benchmark"}, {"start": 1376.1999999999998, "end": 1376.8999999999999, "text": " compared to those."}, {"start": 1376.9, "end": 1379.2, "text": " And we compare with GCN."}, {"start": 1379.2, "end": 1382.3000000000002, "text": " So that's graph convolutional network with GINs with GCNs"}, {"start": 1382.3000000000002, "end": 1384.0, "text": " with the virtual node etc."}, {"start": 1384.0, "end": 1387.3000000000002, "text": " And we have this is some modification of a transformer also"}, {"start": 1387.3000000000002, "end": 1391.4, "text": " an attempt to apply transformers to graph level prediction"}, {"start": 1391.4, "end": 1394.5, "text": " tasks, but not as successful as graph former as we'll see."}, {"start": 1394.5, "end": 1398.2, "text": " So as you can see looking at the test, this is mean absolute"}, {"start": 1398.2, "end": 1399.8000000000002, "text": " error we achieve."}, {"start": 1399.8000000000002, "end": 1404.9, "text": " So graph former achieves the lowest error on compared to"}, {"start": 1404.9, "end": 1407.3000000000002, "text": " all of these other classical GNNs."}, {"start": 1407.3000000000002, "end": 1411.1000000000001, "text": " So those are some nice results and there's one thing I want"}, {"start": 1411.1000000000001, "end": 1412.0, "text": " to mention here."}, {"start": 1412.0, "end": 1413.6000000000001, "text": " Let me just see where it is."}, {"start": 1413.6000000000001, "end": 1418.8000000000002, "text": " It basically yeah, as stated in section 3.3 we further find"}, {"start": 1418.8000000000002, "end": 1421.6000000000001, "text": " the proposed reformer does not encounter the problem of"}, {"start": 1421.6000000000001, "end": 1422.6000000000001, "text": " over smoothing."}, {"start": 1422.6000000000001, "end": 1426.7, "text": " I the train invalidate error keep going down along with the"}, {"start": 1426.7, "end": 1429.4, "text": " growth of depth and width of models."}, {"start": 1429.4, "end": 1432.8000000000002, "text": " So now that this may be strange if you're not familiar with"}, {"start": 1432.8, "end": 1436.2, "text": " graph neural networks, but basically compared to CNNs where"}, {"start": 1436.2, "end": 1439.8999999999999, "text": " depth more depth basically take resonance for example, so the"}, {"start": 1439.8999999999999, "end": 1442.3999999999999, "text": " more depth you have the more expressive and powerful and"}, {"start": 1442.3999999999999, "end": 1445.2, "text": " performant the models are here in the GNN literature."}, {"start": 1445.2, "end": 1447.7, "text": " Basically that doesn't necessarily help."}, {"start": 1447.7, "end": 1450.8, "text": " So you usually see those shallow GNNs like two or three"}, {"start": 1450.8, "end": 1453.1, "text": " layer deep and those work just fine."}, {"start": 1453.1, "end": 1456.0, "text": " So the reason for that are there are multiple reasons."}, {"start": 1456.0, "end": 1457.5, "text": " So one of them is maybe bottleneck."}, {"start": 1457.5, "end": 1460.3999999999999, "text": " So that means if you have if you take a look at the one hop"}, {"start": 1460.3999999999999, "end": 1462.3, "text": " neighborhood, you'll have maybe hundred neighbors."}, {"start": 1462.3, "end": 1464.7, "text": " If you take a look at the two hop neighborhood, you may end"}, {"start": 1464.7, "end": 1466.0, "text": " up with 10,000 neighbors."}, {"start": 1466.0, "end": 1468.5, "text": " If you take a look at the three hop neighborhoods, that's the"}, {"start": 1468.5, "end": 1469.6, "text": " third layer of the GNN."}, {"start": 1469.6, "end": 1474.0, "text": " You'll maybe be attending to millions of notes and just"}, {"start": 1474.0, "end": 1477.2, "text": " but if you try and average all of those feature vectors,"}, {"start": 1477.2, "end": 1480.6, "text": " you'll end up basically collapsing into a single feature"}, {"start": 1480.6, "end": 1483.3, "text": " vector and that's something that's called over smoothing."}, {"start": 1483.3, "end": 1485.8, "text": " So basically all of your feature vectors start collapsing"}, {"start": 1485.8, "end": 1488.3999999999999, "text": " into very same representation and thus you don't have the"}, {"start": 1488.4, "end": 1492.6000000000001, "text": " discriminative power to kind of figure out whatever the task"}, {"start": 1492.6000000000001, "end": 1493.1000000000001, "text": " at hand is."}, {"start": 1493.1000000000001, "end": 1496.1000000000001, "text": " So maybe predict the solubility of the molecule whatever."}, {"start": 1496.1000000000001, "end": 1498.7, "text": " So that's the over smoothing problem and it seems that"}, {"start": 1498.7, "end": 1503.9, "text": " Graphformer kind of dealt with it and I'd be really really"}, {"start": 1503.9, "end": 1504.4, "text": " excited."}, {"start": 1504.4, "end": 1507.6000000000001, "text": " I'm really excited to see like what the future research shows"}, {"start": 1507.6000000000001, "end": 1509.3000000000002, "text": " and explains why this is."}, {"start": 1509.3000000000002, "end": 1514.7, "text": " Finally, they also show some results on other OGP data sets."}, {"start": 1514.7, "end": 1518.3000000000002, "text": " Again, these are mostly molecular data sets and you can"}, {"start": 1518.3, "end": 1522.8, "text": " see again, it just outperforms all of the other baselines."}, {"start": 1522.8, "end": 1526.2, "text": " This flag is just a simple adversarial augmentation."}, {"start": 1526.2, "end": 1530.8, "text": " So just that you know what this suffix means and yeah on"}, {"start": 1530.8, "end": 1537.2, "text": " zinc again lowest mean absolute error compared to the previous"}, {"start": 1537.2, "end": 1537.7, "text": " baselines."}, {"start": 1537.7, "end": 1539.8, "text": " So that's that's pretty much it."}, {"start": 1539.8, "end": 1543.5, "text": " They also did some ablations showing that all of these"}, {"start": 1543.5, "end": 1545.3, "text": " encodings boost up the performance."}, {"start": 1545.3, "end": 1549.5, "text": " So this is the edge encoding as you can see the error drops"}, {"start": 1549.5, "end": 1552.5, "text": " when they added same goes for the nose centrality same goes"}, {"start": 1552.5, "end": 1553.5, "text": " for the spatial encoding."}, {"start": 1553.5, "end": 1557.5, "text": " They always have these boosts in the performance when they"}, {"start": 1557.5, "end": 1559.3999999999999, "text": " add those particular encodings."}, {"start": 1559.3999999999999, "end": 1565.6, "text": " Finally, as we know, basically transformers have problem with"}, {"start": 1565.6, "end": 1569.3, "text": " the scalability of these the vanilla transformer."}, {"start": 1569.3, "end": 1572.5, "text": " We have this quadratic dependency between the tokens"}, {"start": 1572.5, "end": 1575.2, "text": " because of this attention attending mechanism and"}, {"start": 1575.2, "end": 1577.5, "text": " so the quadratic complexity of the self-attention modular"}, {"start": 1577.5, "end": 1580.5, "text": " stricts reformers application on large graphs, which is"}, {"start": 1580.5, "end": 1581.4, "text": " pretty much obvious."}, {"start": 1581.4, "end": 1585.5, "text": " So that means that even though it achieved really nice results"}, {"start": 1585.5, "end": 1588.9, "text": " on these benchmarks, which are molecular data sets molecular"}, {"start": 1588.9, "end": 1593.0, "text": " graphs, I can imagine that this still can't be used to any"}, {"start": 1593.0, "end": 1597.7, "text": " like like huge graphs such as maybe social media graph."}, {"start": 1597.7, "end": 1602.8, "text": " And so yeah, I can I just expect to see people kind of"}, {"start": 1602.8, "end": 1605.5, "text": " using the ideas that came from the transformer literature"}, {"start": 1605.5, "end": 1607.5, "text": " like lean former performer, etc."}, {"start": 1607.5, "end": 1610.5, "text": " to kind of make this thing more efficient and then we'll see"}, {"start": 1610.5, "end": 1613.8, "text": " whether it can achieve some nice results even on larger graphs."}, {"start": 1613.8, "end": 1618.3, "text": " Having said that, that's the those are the main ideas of"}, {"start": 1618.3, "end": 1618.8, "text": " this paper."}, {"start": 1618.8, "end": 1623.3, "text": " And now I want to focus on this on this fact one and kind of"}, {"start": 1623.3, "end": 1626.1, "text": " delve a bit deeper into it and explain why this is."}, {"start": 1626.1, "end": 1630.5, "text": " Okay, let's focus on this part by choosing proper weights"}, {"start": 1630.5, "end": 1632.9, "text": " and distance function five the graph former layer can"}, {"start": 1632.9, "end": 1635.9, "text": " represent aggregate and combine steps of popular gene and"}, {"start": 1635.9, "end": 1639.8, "text": " modules models such as gene GCN and graph sage."}, {"start": 1640.8, "end": 1644.0, "text": " Moreover, we show further that by using our special encoding"}, {"start": 1644.0, "end": 1646.8, "text": " graph former can go beyond classic message passing gene"}, {"start": 1646.8, "end": 1650.6, "text": " ends whose expressive power is no more than the vice"}, {"start": 1650.6, "end": 1652.4, "text": " file a lemon one test."}, {"start": 1652.7, "end": 1657.5, "text": " So by the way, there is a bit of confusion about this vice"}, {"start": 1657.5, "end": 1661.5, "text": " file a lemon test and the thing is all of these expressivity"}, {"start": 1662.8, "end": 1667.2, "text": " like statements basically only are valid for and so-called"}, {"start": 1667.2, "end": 1670.5, "text": " anonymous graph neural networks whereby anonymous."}, {"start": 1670.5, "end": 1675.1, "text": " I mean that the node feature vectors are actually basically"}, {"start": 1675.1, "end": 1677.6, "text": " nonexistent or they are not discriminative."}, {"start": 1677.8, "end": 1682.5, "text": " So that means where well by using standard graph neural"}, {"start": 1682.5, "end": 1683.9, "text": " networks, you always have those no features."}, {"start": 1683.9, "end": 1687.3, "text": " So these analysis are not that they can be kind of tricky."}, {"start": 1687.3, "end": 1689.3999999999999, "text": " I'll link this blog down in the description."}, {"start": 1689.3999999999999, "end": 1692.0, "text": " You can see it on the screen which explains this problematic"}, {"start": 1692.0, "end": 1695.5, "text": " really good and kind of explains what a gene ends can"}, {"start": 1695.5, "end": 1698.7, "text": " learn and what they can learn and so do check it out."}, {"start": 1698.7, "end": 1699.7, "text": " It's really really cool."}, {"start": 1699.8999999999999, "end": 1701.6, "text": " Having said that let's focus on this part."}, {"start": 1701.6, "end": 1704.8999999999999, "text": " How can we how can we treat these classical gene ends as"}, {"start": 1704.8999999999999, "end": 1705.7, "text": " a special case?"}, {"start": 1706.1, "end": 1710.3999999999999, "text": " Okay, but let's start first with this vice file a lemon"}, {"start": 1710.3999999999999, "end": 1710.7, "text": " thing."}, {"start": 1711.1, "end": 1715.7, "text": " So so vice file a lemon or the color test basically what"}, {"start": 1715.7, "end": 1719.5, "text": " it does it it outputs color histogram and if the color"}, {"start": 1719.5, "end": 1723.1000000000001, "text": " case runs are the same it claims that those two graphs"}, {"start": 1723.1000000000001, "end": 1726.5, "text": " are isomorphic and we can clearly see that these two graphs"}, {"start": 1726.5, "end": 1730.4, "text": " here are not isomorphic but vice file a lemon tells us that"}, {"start": 1730.4, "end": 1735.1000000000001, "text": " they are isomorphic because we have four red colors and we"}, {"start": 1735.1000000000001, "end": 1741.0, "text": " have two blue colors and because of that vice file a lemon"}, {"start": 1741.0, "end": 1744.8, "text": " would falsely claim that these are isomorphic on the other"}, {"start": 1744.8, "end": 1747.8, "text": " hand if you focus on the shortest path distance, so let's"}, {"start": 1747.8, "end": 1748.8, "text": " let's see what I see here."}, {"start": 1749.0, "end": 1752.8, "text": " So these two graphs cannot be distinguished by vice file"}, {"start": 1752.8, "end": 1755.2, "text": " a lemon one test by the SPD sets."}, {"start": 1755.5, "end": 1758.8, "text": " I the SPD from each node to others are different the two"}, {"start": 1758.8, "end": 1762.7, "text": " types of nodes in the left graph have SPD sets as you can"}, {"start": 1762.7, "end": 1765.5, "text": " see here and let me explain let me kind of break it down"}, {"start": 1765.5, "end": 1766.6, "text": " for you what this means."}, {"start": 1766.7, "end": 1769.8999999999999, "text": " So obviously the shortest path distance between this node"}, {"start": 1770.0, "end": 1772.3999999999999, "text": " this this red node and itself is zero."}, {"start": 1772.4, "end": 1776.8000000000002, "text": " It has one distance until it reaches this distance these"}, {"start": 1776.8000000000002, "end": 1781.1000000000001, "text": " nodes and two for these two and finally three and as you"}, {"start": 1781.1000000000001, "end": 1786.4, "text": " can see here that's 0 1 1 2 2 3 and for all of the red"}, {"start": 1786.4, "end": 1786.8000000000002, "text": " nodes."}, {"start": 1786.8000000000002, "end": 1788.2, "text": " We have the same SPD set."}, {"start": 1788.2, "end": 1791.6000000000001, "text": " Okay, finally for this blue node again."}, {"start": 1791.6000000000001, "end": 1795.3000000000002, "text": " We have trivially zero shortest path to itself."}, {"start": 1795.5, "end": 1799.0, "text": " We have 1 1 1 here."}, {"start": 1799.0, "end": 1799.8000000000002, "text": " So that's 3 1."}, {"start": 1799.8, "end": 1804.2, "text": " So those are these ones here and finally we have to to"}, {"start": 1804.8, "end": 1808.6, "text": " which are these two and similarly goes for this graph"}, {"start": 1808.6, "end": 1813.2, "text": " here and we can see that the SPD sets are different thus"}, {"start": 1813.7, "end": 1817.3999999999999, "text": " this SPD will help us determine that these graphs are"}, {"start": 1817.3999999999999, "end": 1818.3, "text": " not isomorphic."}, {"start": 1818.3, "end": 1819.8, "text": " I they are non isomorphic."}, {"start": 1820.2, "end": 1824.3999999999999, "text": " So that's a like a visual explanation and a particular"}, {"start": 1824.3999999999999, "end": 1827.3, "text": " example where they showed the graph former is more powerful"}, {"start": 1827.3, "end": 1831.7, "text": " than those simple like vice versa lemon one test kind of"}, {"start": 1831.7, "end": 1832.3, "text": " architectures."}, {"start": 1832.3, "end": 1832.6, "text": " Okay."}, {"start": 1833.5, "end": 1836.1, "text": " Now let's focus on the really important part and that's"}, {"start": 1836.1, "end": 1841.0, "text": " these how we how can we basically show that GNN's are"}, {"start": 1841.0, "end": 1843.6, "text": " some GNN's are special case of graph of this graph or"}, {"start": 1843.6, "end": 1844.0, "text": " module."}, {"start": 1844.3999999999999, "end": 1847.6, "text": " So let's focus on mean aggregate function and explaining"}, {"start": 1847.6, "end": 1848.3999999999999, "text": " how that works."}, {"start": 1848.6, "end": 1851.0, "text": " So we begin by showing that self-attention module with"}, {"start": 1851.0, "end": 1853.7, "text": " spatial encoding can represent mean aggregation."}, {"start": 1854.0, "end": 1856.6, "text": " This is achieved by in equation 6 settings."}, {"start": 1856.6, "end": 1857.8, "text": " So this is equation 6."}, {"start": 1857.8, "end": 1859.3, "text": " This is your transformer."}, {"start": 1859.3999999999999, "end": 1863.3, "text": " This is your basically bias using this shortest path"}, {"start": 1863.8, "end": 1864.3, "text": " function."}, {"start": 1864.5, "end": 1871.6, "text": " Okay, so by setting the scalar when Phi equals 1 so direct"}, {"start": 1871.6, "end": 1876.5, "text": " neighbors to 0 and to minus infinity otherwise where Phi"}, {"start": 1876.5, "end": 1879.3, "text": " is the shortest path distance and setting these two matrices"}, {"start": 1879.3, "end": 1881.8999999999999, "text": " so the query projection matrix and a key projection matrix"}, {"start": 1882.0, "end": 1886.1, "text": " to 0 matrix and the value projection matrix to identity"}, {"start": 1886.1, "end": 1889.1999999999998, "text": " matrix then the softmax gives the average represent of"}, {"start": 1889.1999999999998, "end": 1891.8999999999999, "text": " representations of the neighbors and let's let me let me"}, {"start": 1891.8999999999999, "end": 1894.0, "text": " try and break it down how this exactly works."}, {"start": 1894.3, "end": 1895.1, "text": " It's quite a simple."}, {"start": 1895.3999999999999, "end": 1897.1, "text": " So we have a note here."}, {"start": 1897.3, "end": 1898.8, "text": " We have some direct neighbors."}, {"start": 1899.8999999999999, "end": 1901.6999999999998, "text": " Let's say we have three direct neighbors."}, {"start": 1901.6999999999998, "end": 1904.8, "text": " These are connected and finally, let's say we have some"}, {"start": 1905.3, "end": 1907.8, "text": " undirect indirect like neighbors."}, {"start": 1907.8, "end": 1908.6, "text": " Okay, like these two."}, {"start": 1909.0, "end": 1911.3, "text": " So what happens is the following."}, {"start": 1911.3999999999999, "end": 1915.3999999999999, "text": " So as we know these will have and we are focusing on this"}, {"start": 1915.4, "end": 1920.2, "text": " node and trying to figure out the next layer presentation."}, {"start": 1920.6000000000001, "end": 1924.3000000000002, "text": " So we can see that these nodes here have distance one and"}, {"start": 1924.3000000000002, "end": 1927.4, "text": " these nodes here have distance 2 and finally 3."}, {"start": 1927.4, "end": 1927.8000000000002, "text": " Okay."}, {"start": 1928.3000000000002, "end": 1934.1000000000001, "text": " So what I say is the following if we set these bees to 0."}, {"start": 1934.1000000000001, "end": 1938.7, "text": " So if we set this one to 0 this one to 0 and this one to 0"}, {"start": 1939.3000000000002, "end": 1944.5, "text": " and if we set these to minus infinity then as you can see"}, {"start": 1944.5, "end": 1948.3, "text": " looking at this formula here will have that after we apply"}, {"start": 1948.3, "end": 1952.0, "text": " softmax these will get to 0 and these will get will have"}, {"start": 1952.0, "end": 1956.5, "text": " some nonzero value and now the second portion is this these"}, {"start": 1956.5, "end": 1958.9, "text": " matrices should be zero matrices and the value should be"}, {"start": 1958.9, "end": 1962.7, "text": " identity that will help us achieve the the mean aggregation"}, {"start": 1962.7, "end": 1963.3, "text": " of neighbors."}, {"start": 1963.6, "end": 1964.2, "text": " So let's see."}, {"start": 1964.2, "end": 1966.9, "text": " So for now we just have some arbitrary nonzero values here"}, {"start": 1966.9, "end": 1969.3, "text": " and we have zeros here for the attention coefficients."}, {"start": 1969.7, "end": 1971.7, "text": " So now let me let me do it like this."}, {"start": 1971.7, "end": 1975.8, "text": " So let's focus on this particular node and so we have"}, {"start": 1975.8, "end": 1979.3, "text": " some feature vector once we map them this feature vector"}, {"start": 1979.3, "end": 1982.8, "text": " using the key query and value matrices will get the following"}, {"start": 1982.8, "end": 1983.1000000000001, "text": " thing."}, {"start": 1983.1000000000001, "end": 1988.9, "text": " So query and key so key and query will just be zero vectors"}, {"start": 1988.9, "end": 1992.3, "text": " because remember we have zero matrices there and this one"}, {"start": 1992.3, "end": 1996.5, "text": " here because we have an identity matrix will be the same"}, {"start": 1996.5, "end": 1999.2, "text": " just a copy pasted version of this vector here."}, {"start": 1999.2, "end": 2000.0, "text": " So this is V."}, {"start": 2000.1000000000001, "end": 2001.1000000000001, "text": " This is we as well."}, {"start": 2001.1, "end": 2002.6, "text": " So this is the value vector."}, {"start": 2002.6, "end": 2007.3999999999999, "text": " Okay, and now we do the same thing for all of the nodes"}, {"start": 2007.3999999999999, "end": 2011.3, "text": " in the graph and as you can see if we take this query vector"}, {"start": 2011.3, "end": 2015.1999999999998, "text": " which is all zeros and we do adopt products between any"}, {"start": 2015.1999999999998, "end": 2018.1, "text": " of the keys because all the keys are also all zero vectors"}, {"start": 2018.1, "end": 2020.8999999999999, "text": " will always have this thing going to zero."}, {"start": 2020.8999999999999, "end": 2024.6, "text": " So this this term in the equation will go to zero and"}, {"start": 2024.6, "end": 2028.3, "text": " finally as I already explained will have this bias terms"}, {"start": 2028.3, "end": 2031.6, "text": " will be zero for the local neighbors direct neighbors and"}, {"start": 2031.6, "end": 2032.8, "text": " minus infinity there."}, {"start": 2033.0, "end": 2036.5, "text": " So that means we'll basically end up having the same"}, {"start": 2036.5, "end": 2039.3999999999999, "text": " coefficients here and that's going to be one over three."}, {"start": 2040.6, "end": 2042.3999999999999, "text": " And these will be zero."}, {"start": 2042.6, "end": 2047.6, "text": " So we'll only be will end up attending only these nodes"}, {"start": 2047.6, "end": 2053.2, "text": " here and we'll take a mean average of those three feature"}, {"start": 2053.2, "end": 2053.5, "text": " vectors."}, {"start": 2053.5, "end": 2056.6, "text": " Okay, so if you're confused by one three, it's pretty simple."}, {"start": 2056.6, "end": 2058.2999999999997, "text": " So it's just soft max thing."}, {"start": 2058.2999999999997, "end": 2059.9, "text": " So you'll have E."}, {"start": 2060.0, "end": 2064.9, "text": " So let's focus on for example on this note will have e raised"}, {"start": 2064.9, "end": 2067.7999999999997, "text": " to power of zero because that's the attention."}, {"start": 2067.7999999999997, "end": 2071.6, "text": " That's the attention score we got and down in the denominator."}, {"start": 2071.6, "end": 2074.9, "text": " We'll just have a sum and that sum will be equal to three"}, {"start": 2075.1, "end": 2077.2, "text": " because we'll have three times."}, {"start": 2078.2999999999997, "end": 2081.4, "text": " You raised to the power of zero and we'll have two times."}, {"start": 2081.4, "end": 2085.6, "text": " You raised to the power of minus infinity, which is obviously"}, {"start": 2085.6, "end": 2088.2000000000003, "text": " zero and that's why we achieve."}, {"start": 2088.2000000000003, "end": 2090.5, "text": " That's why we discuss to one over three."}, {"start": 2091.5, "end": 2094.6, "text": " And that means that yeah, basically those are the attention"}, {"start": 2094.6, "end": 2098.2000000000003, "text": " coefficients that this node will use to accumulate the value"}, {"start": 2098.2000000000003, "end": 2101.1, "text": " vectors of the direct neighbors and as you can see, we literally"}, {"start": 2101.1, "end": 2102.7000000000003, "text": " achieved this mean aggregation."}, {"start": 2102.7000000000003, "end": 2105.4, "text": " So that was the first the first part."}, {"start": 2105.4, "end": 2109.2000000000003, "text": " Now the sum aggregate part is pretty easy."}, {"start": 2109.2, "end": 2112.2, "text": " Once we understand this first mean aggregate part, but let me"}, {"start": 2112.2, "end": 2114.5, "text": " let me let me zoom in a bit here and explain it."}, {"start": 2114.5, "end": 2117.3999999999996, "text": " The summary Asian can be realized by first performing mean"}, {"start": 2117.3999999999996, "end": 2120.2, "text": " aggregation and then multiply the node degrees."}, {"start": 2120.2, "end": 2121.2, "text": " We'll see what that means."}, {"start": 2121.5, "end": 2124.2, "text": " So specifically the node degrees can be extracted from"}, {"start": 2124.2, "end": 2125.3999999999996, "text": " centrality encoding."}, {"start": 2125.3999999999996, "end": 2128.6, "text": " So that's the degree encoding by an additional head and be"}, {"start": 2128.6, "end": 2132.2, "text": " concatenated to the representations after mean aggregation."}, {"start": 2132.2999999999997, "end": 2135.6, "text": " Then the fully the feed-forward network module in graph"}, {"start": 2135.6, "end": 2138.2, "text": " former can represent the function of multiplying the"}, {"start": 2138.2, "end": 2141.1, "text": " degree of the dimensions of average representations by the"}, {"start": 2141.1, "end": 2145.7, "text": " universal approximation theorem of fully of fully feed-forward"}, {"start": 2145.7, "end": 2146.2, "text": " networks."}, {"start": 2146.3999999999996, "end": 2146.7999999999997, "text": " Okay."}, {"start": 2148.1, "end": 2150.7999999999997, "text": " So let me kind of break that down."}, {"start": 2150.8999999999996, "end": 2155.2999999999997, "text": " It's pretty simple and I'll just draw it over this chart."}, {"start": 2155.2999999999997, "end": 2161.0, "text": " So let's assume the first head gives us the mean representation"}, {"start": 2161.0, "end": 2161.7999999999997, "text": " for this vector."}, {"start": 2162.5, "end": 2165.8999999999996, "text": " Okay, so we have that part and now what they say is the"}, {"start": 2165.9, "end": 2169.2000000000003, "text": " following let's take another head."}, {"start": 2169.3, "end": 2171.1, "text": " So we have multiple attention heads."}, {"start": 2171.1, "end": 2172.3, "text": " Remember this is transformer."}, {"start": 2172.7000000000003, "end": 2176.7000000000003, "text": " So what that have will do it will learn how to extract the"}, {"start": 2176.7000000000003, "end": 2179.9, "text": " degree of this note, which is as you can see here just"}, {"start": 2180.3, "end": 2181.7000000000003, "text": " consider with some direct graphs."}, {"start": 2181.7000000000003, "end": 2182.4, "text": " It's three."}, {"start": 2182.9, "end": 2186.6, "text": " So we'll learn how to extract maybe something like a vector"}, {"start": 2186.6, "end": 2190.0, "text": " which will have all zeros and only three at the bottom here."}, {"start": 2190.1, "end": 2190.4, "text": " Okay."}, {"start": 2191.2000000000003, "end": 2193.6, "text": " And so how that will happen is the following."}, {"start": 2193.6, "end": 2199.7999999999997, "text": " So remember this so this this vector here is formed by taking"}, {"start": 2199.7999999999997, "end": 2205.5, "text": " the original vector and adding to it those embeddings for the"}, {"start": 2205.5, "end": 2206.5, "text": " degree centrality."}, {"start": 2206.5, "end": 2210.4, "text": " So basically will be adding those note those vectors which"}, {"start": 2210.4, "end": 2214.6, "text": " contain the degree information and this head can learn how"}, {"start": 2214.6, "end": 2218.5, "text": " to extract from this vector how to extract this number here."}, {"start": 2219.4, "end": 2221.1, "text": " So that have will learn how to do that."}, {"start": 2221.4, "end": 2223.2, "text": " And once we have that we do the following."}, {"start": 2223.2, "end": 2225.6, "text": " We basically concatenate because if you remember how"}, {"start": 2225.6, "end": 2228.7, "text": " transformer works every single head attention head will"}, {"start": 2228.7, "end": 2230.7, "text": " basically output a representation."}, {"start": 2230.7999999999997, "end": 2232.2, "text": " Those will get concatenated."}, {"start": 2232.2999999999997, "end": 2233.6, "text": " Then we'll have some MLPs."}, {"start": 2233.7999999999997, "end": 2237.5, "text": " So again, we'll have the following will have the mean"}, {"start": 2237.5, "end": 2244.8999999999996, "text": " representation and we'll have the degree of the node and"}, {"start": 2244.8999999999996, "end": 2248.3999999999996, "text": " then by this universal by this theorem of universal"}, {"start": 2248.3999999999996, "end": 2251.2999999999997, "text": " approximation theorem where these MLPs can basically like"}, {"start": 2251.3, "end": 2253.7000000000003, "text": " giving up enough width and depth."}, {"start": 2254.0, "end": 2255.9, "text": " They can basically approximate any function."}, {"start": 2256.1000000000004, "end": 2260.2000000000003, "text": " So what we get here is after mapping them."}, {"start": 2261.2000000000003, "end": 2264.5, "text": " It can learn how to take this number."}, {"start": 2264.6000000000004, "end": 2269.6000000000004, "text": " Let's say three and multiply it with every single feature"}, {"start": 2269.6000000000004, "end": 2270.4, "text": " dimension here."}, {"start": 2270.6000000000004, "end": 2274.3, "text": " So with this thing with this thing with this thing with"}, {"start": 2274.3, "end": 2278.2000000000003, "text": " this thing and if we do that will just end up with a sum"}, {"start": 2278.3, "end": 2280.7000000000003, "text": " aggregation instead of a mean of irrigation."}, {"start": 2280.7, "end": 2282.2999999999997, "text": " And hopefully this was clear enough."}, {"start": 2283.1, "end": 2285.6, "text": " This is how I understood it basically."}, {"start": 2285.7, "end": 2288.2, "text": " And yeah, if I'm wrong, feel free to comment down."}, {"start": 2288.2999999999997, "end": 2290.5, "text": " But yeah, I think that's in a nutshell how it works."}, {"start": 2290.7, "end": 2294.2, "text": " So similar thing for max aggregate similar thing for"}, {"start": 2294.2, "end": 2295.7999999999997, "text": " combine and mean readout."}, {"start": 2295.7999999999997, "end": 2296.8999999999996, "text": " You can you can do it yourself."}, {"start": 2296.8999999999996, "end": 2300.7999999999997, "text": " But this is the whole logic the whole point how this works."}, {"start": 2300.8999999999996, "end": 2305.1, "text": " And yeah, we saw we can emulate these as a special case"}, {"start": 2305.1, "end": 2307.2999999999997, "text": " of graph warmer and that's super cool."}, {"start": 2307.6, "end": 2310.2999999999997, "text": " Having said that if you like this video consider sharing"}, {"start": 2310.3, "end": 2312.2000000000003, "text": " subscribe and until next time."}, {"start": 2312.2, "end": 2340.2, "text": " Bye bye."}]