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

A deep dive into the temporal graph networks paper.

You'll learn about:
✔️ What are dynamic graphs?
✔️ How to get a vectorized representation of time
✔️ All the nitty-gritty details behind the paper

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

⌚️ Timetable: 

00:00 Dynamic graphs
03:00 Suboptimal strategies
05:30 Terminology, temporal neighborhood
07:30 High-level overview of the system
08:35 We need to go deeper
13:30 Using temporal information to sample
14:10 Information leakage and the solution
16:55 Main modules explained
21:20 Memory staleness problem
24:00 Temporal graph attention
26:00 Vector representation of time
29:15 Batch size tradeoff
31:00 Results and ablation studies
33:55 Recap of the system
36:55 Some confusing parts

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

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

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

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

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

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

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

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

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

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

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

#temporalgraphnetworks #dynamicgraphs #graphml
 I want to make shout out to Shantanu who recommended I create a video on TGN temporal graph networks and it was about time since dynamic networks is such an interesting concept, interesting research direction and many real world applications such as social media networks rely on having the modeling these dynamic graphs. So what's a dynamic graph? So basically whenever you have, so in contrast with static graphs, basically here you have the nodes can be added, deleted, modified, same goes with edges. So we basically have two types of events. We have node-wise events and we have interaction or edge events. So let's say we have some simple network here like graph and it can be multi-graph in a general case and basically I'll be using Twitter as a running example since the authors of this paper, Emanuella Rossi, Ben Fabrizio, David Federico and Michael Bronstein are all from Twitter. Let's say Anna decides to join Twitter. So basically she signs up, she fills up this sign-up form and now she's a new node in Twitter, social graph and that's basically the node addition event. Now let's say after a couple of days she was just kind of retweeting people and every single retweet is basically an edge in that graph. Now Ben joins Twitter and because those two broke up, Anna is pissed off and she just deletes the Twitter account altogether and that's the node deletion event. Now Ben is also pissed off and so he decides to update his user profile, updates his description and by updating the description he's basically changing his feature vector and you can think of it maybe we take this text and we pass it in a BERT encoder and we basically have CLS here, token, hopefully you're familiar with BERT. If you're not, just treat it as a black box. We input the text here, we get out the condensed representation here and we use exactly this thing as the feature vector. So that's the node modification event. Now after a couple of days of activity he decides to retweet Andrew Eng's school post and basically now whatever the retweet text is that's the edge feature vector and now maybe he made a typo so he decides to modify the text even though that's not possible on Twitter, but let's say it is and for the sake of argument and basically that's the edge modification event where now the new text is again fed through BERT and we get the new feature vector and finally he decides to just delete the tweet altogether and that's the edge deletion event. So that's how the dynamic graph works in a nutshell. It's basically a multi-graph because every single node can have multiple edges between, so the nodes are connected by multiple edges and that's what's known as a multi-graph. Okay, dead out of the way, let's jump into the paper and see what they say. So they say here a few approaches have been proposed for dealing with graphs that are dynamic in nature. So basically most of the research in graph ML was focusing on static graphs and not on dynamic graphs and while it is possible to apply static graph deep learning models to dynamic graphs by ignoring the temporal evolution, this has shown been shown to be suboptimal. So what that means is the following. So you have this graph here and basically every single edge has a time stamp attached to it. So let's say Ben here has got maybe three retweets of Andrew Ang and this one happened at t1, this one happened at t2, this one happened just recently like a couple of seconds ago at t3 and you can treat this as a static graph, just a static multi-graph or you can kind of acknowledge the like the existence of these time stamps and use that to, when you sub sample your neighborhood later and we'll see why we do that a bit later, but when we sub sample the neighborhood we can just take the most recent edges and by doing that we have a much more optimal performance than just by treating this as a static graph and doing uniform sampling of the neighborhood. So yeah, basically that's suboptimal, you can treat it as a static graph but it's suboptimal, okay? And yeah, so learning on dynamic graphs is relatively recent and most of the previous work was focused on these discrete time dynamic graphs which is just a sequence of snapshots of the graph. So basically you have your graph that's evolving and what you do in this discrete time dynamic graph is the following. You just take a snapshot at equidistant moments, so maybe you had some graph at t1 that looked like this and then after some period and the important part here is that this is pretty much the same constant so you have equidistant moments when you take the snapshot and maybe a couple of more edges and nodes appeared etc. So like this, I don't know, whatever. And you do the same thing after the same time period t. This is basically the improvement over the static graph modeling but this discrete time dynamic graphs are still limited compared to the continuous ones that we're gonna see in this paper. Okay, a small recap basically when you want to compute the embeddings for the static graph, you just have basically accumulation over the neighborhood of these messages and h is just a trainable update function and that's how you get your embeddings. That's what this equation here stands for. But it's not so important now so I just want to kind of walk you through some terminology that we'll be using and that's as I already mentioned we have this discrete time dynamic graphs or DTDGs for short and we have continuous time dynamic graphs on the other hand and those are the ones we'll be treating in this video. And basically the point here is that you have to the point here is we treat it as a sequence of time stamped events. So every single event be it nodewise event, be it the edge event has a time stamp associated with it. Contrast that with static graphs where we had those equidistant snapshots. And I already explained those two and now the interesting concept, new concept that's not encountered in static graphs is this concept of a temporal neighborhood. So what it means basically is the following. So again you have some nodes in the graph and let's say there are multiple edges here and let's say this one happened at t5 and we're currently looking for some reason we're looking at a moment that happened before prior to t5 like at t4. That basically means that the neighborhood of this graph here is will ignore this edge. So everything that comes after this particular target moment of time is ignored and that's what you're left with. So all of the other edges here is what's known as the temporal neighborhood of this particular node at this point of time. Okay so that's a new concept and with that out of the way let's jump and see what are the main modules in this TGN network. Okay let me give you a quick high level overview of the system and then we'll slowly start building on and adding new details. So high level how we train this graph neural network, this whole system actually because it also has this thing called memory, is the following. So we do a self-supervised learning and we're learning how to do link prediction. So basically because we have all of those retweets and we have time stamps associated with them we can just do chronological sort over all of those interactions and we can just predict the interactions that haven't yet happened and that's basically the you just batch that chronologically sorted array of those edge interactions and you just predict the follow-up edges. It's a similar thing as transformers there you're trying to predict the follow-up word and here you're trying to predict what the next interaction will be. So that's the high level overview of how the thing works. So now let's see on this chart what happens basically. So you have you have and I'll just create a simple example here. We have node 1, we have nodes 2 and we have node 3. So 1 as you can see here at t1, 1 retweeted node 2 and at t2 node 2 retweeted node 3. So like this. So now what we do is the following. We have so because node 1 also had some other interactions maybe that happened even prior to these interactions. So let's say these happened at whatever t0 maybe. Okay so now what happens is that we have this embedding method and that's basically get. If you if you haven't watched my video on graph attention networks you can check it out. I'll link it somewhere here and you basically do one layer get over this node 1 over its temporal neighborhood and we already mentioned what that is. We do get and we calculate the embeddings for nodes 1, 2 and node 3 right and those are these z's. Once we have those we can just calculate the probability using a simple decoder. So they used MLP here. So you just concatenate these two embeddings. You just pass them through MLP and you just add the non-linear function like sigmoid non-linearity and that means this is basically probability. And now in order to train you do the following. So you want to make sure that P so given t1 what's the probability of interaction between 1 and 2 happening? And we know it's 100% it's 1 because it already happened. We have it in the data set right. We did it chronological sort. So you want to push the loss to go to 1, P to go to 1. I loss will be 0 because we're just using simple binary cross entropy here and we'll also have negative edges which we'll want to make sure that the probability goes to 0 and yeah that's it. So if you have maybe some nodes x and nodes y and this interaction hasn't happened we want to make sure that we push the probability to 0 for those node pairs. And we use a simple as I mentioned so loss is just a binary cross entropy that means that's a fancy name for you just put the log here. So basically if we have positive examples we'll just the loss will have a format like this minus log of P right and if I just draw it here that will look like this and basically we want to push the probability to go to 1 because then the loss goes to 0. For when we have negative examples we'll just have minus log of 1 minus P and that will just kind of mirror this chart here and it will look like this. So we have P on the x-axis, we have loss on the y-axis and the loss will look like this. Basically at 0 we have loss that's equal to 0 and at 1 it goes to infinity. So that's how we train it simple BC we have positives we have negatives we have the data set with and we just batch it and we use those batches to predict those links because we know they're there. So how the embedder part works so get leverage is something called memory or states in this TGN network. So what it is is basically every single node in our graph in Twitter graph has a state associated with it. So we have a huge table and every single node in this table has some representation and they said here basically the purpose is to represent the node's history in a compressed format and that's exactly what it does. So basically over the when the interactions are happening in Twitter we're basically using all of those to just update this memory state and then we can use those to later do some recommendations but I'll get to that in a moment okay. So we have these states and they are somehow calculated so we have some messages we do some aggregation we somehow use them to update the memory state and then the embedding method the get will just use those to calculate the embeddings and we can predict the links. So that's the high level overview and now we'll slowly start digging into details hopefully it was clear enough. Maybe one more thing worth mentioning when we are using get in this model the way we we sub sample the neighborhood is using the most recent edges so that's why we have timestamps. So basically if we have a bunch of edges we'll use we'll only sub sample the most recent k ones so we we sort the the neighborhood edges by timestamps and we just take the k most recent ones that may be like 10 most recent neighbors and then you just do the simple get aggregation and we'll see what exact features go inside here in a sec. Okay now the problem with this chart is if you maybe if you noticed is that we are using these interactions to calculate the messages to update the states and then we're using that those states to predict the links so that means we have information leakage here we're basically using this information to update states and then we're using the states to predict those links and that doesn't make any sense right but because you somehow have to you somehow have to calculate and use these message functions to get the states because otherwise you won't have any gradients flowing towards these trainable functions the aggregated messages and messages and this mem function they are all trainable so you somehow have to have this forward pass here but you can use this batch you'll just use the previous batches and that's the solution so basically they have a graph here okay you have to introduce this concept of a raw memory storage and now what you do here is from the previous batch you just store the previous batch you just stored all the necessary information inside here so now when you try to predict the the the existence of a link between one and two the the existence of of retweet in the case of twitter what you do is the following you use the the the last batch and i mean not just the last batch actually the whole history and you calculate the messages and we'll see how we do that so we have some data here that's necessary to calculate these messages then we just aggregate the messages so you see here that messages for the node two are kind of accumulated and then we update the states and they just use grue here and we'll see those details so what happens is basically you you you have the previous state so this is grue g r u you just use s2 and this is the old state and you use the the newest message this m2 aggregated and this will just spit out new state and we just write it down here so that's how we update the the states now the states have now we have this thing like included in the computation graph and we just use get to calculate embeddings and to we get to the loss so now gradient gradients can now flow through the whole system and all of these functions which will see what they exactly are so these egg these mem functions will be updated in the back propagation step okay so that's the important solution so introduction of raw message store is important because that allows us to train this part of the pipeline this part here okay okay hopefully that was clear enough um let me let me slowly start digging into into details of how the messages are computed and then once we have all of those details i'll again zoom out and try and explain everything okay so messages are computed the following once interaction happens between nodes i and j so we have node i we have j one of them retweeted the other so we have interaction that happened and it has feature vector associated with it so that's e i j right okay so how we calculate the message is basically we input the previous states and this t minus just means the state before this interaction happened for those notes so that's basically whatever is currently in the state table so we have si here we have sj so whatever is currently in there we use those and we input them in the message function and we additionally use the uh this feature vector i just mentioned so that's like the maybe birth encoding of retweet and we finally use this delta t which is the time that has elapsed between the previous interaction and this current interaction so that may be like 30 seconds or whatever and that's how we compute the message for this for this node i and then we do analogously to node j so that's the destination so that's the source and destination nodes and the only difference is these are permuted if you can if you can notice here so just permutation simple permutation and uh although this can be trainable what it did is they in practice use just identity function which means they are just doing simple concatenations uh between all of these features so you have some vector here vector you concatenate all of them and that's your message and this here is an interesting thing and i'll later explain uh how we convert time to a vector uh to a vector representation and just stay tuned for that okay so that's the uh so that's the part with with the messages okay and they say here a more complex message function that involves additional aggregation from the neighborhoods from the neighbors of nodes i and j is also possible and is left for future study so the thing with this paper is there is there is a it's a it's a work in progress there is a lot of things they still want to try and they haven't tried it so for example they have this uh node-wise uh memory but they also they say here while a global graph-wise memory can also be added to the model to track the evolution of the entire network we'll leave this as a future work so that's that's my point there is still a lot of things uh evolving in this work so yeah just just keep that in mind um okay so once we have the message function so that's this part right so that's the messages how do we aggregate them and here we just have a message aggregator and again it can be a trainable function but what they did is they just do a simple most recent message and mean message heuristic and you can even see it here so what it did is you have m2 at t1 you have m2 at t2 they just took the last message and that's the aggregation okay um in more general case they can also just do a mean or something else just kind of do make it trainable uh maybe pass it through an rnn or whatever okay but it's stuck with the most recent message and let's use it as the running example uh finally we have the memory updater i already explained that they used some form you can use whatever like rnn or lstm they used a grew which is a specific type of of lstm basically and i already explained how it works but let me just repeat okay let's this is grew and we have we have the state state i t minus we just get the new message and we just run this and there are like a if you know how if you don't know how grew works i'll just link uh chris ola's blog he has a really nice blog intuitive to understand how this works basically a bunch of forget and update gates and this spits out we can treat it as a black box for now it just spits out the new state si at point t so this was a t minus and here we have the current state so that's the memory updating part okay finally uh we have the embedding module uh and um so i haven't mentioned this but the main goal of the embedding module is to avoid the so-called memory staleness problem so what that means is the following so let's say we we have a graph and um like we have we had ben here and maybe ben stopped uh using twitter for maybe a month or two and now what happens is that his if you take a look at the memory so and we we take ben's state uh because he's not interacting with anybody anymore um we this this representation is not updated and so um we we we need to have uh some sort of of of embedding to to to make this relevant for ben when he returns so if we want to recommend to ben which tweets should he uh see so that's like your your home page on twitter you see a bunch of tweets so twitter somehow needs to figure out which tweets are relevant for you and also uh twitter should recommend you what's the what's what what are the persons you should probably follow so how they do that is the following so ben has uh his state b and in the simplest case you could just do the following you could just take sp and maybe andrew ang has his own state sa and you just do a dot product or mlp and uh whatever and that spits out some probability so if the probability is close to one uh twitter may recommend that you follow uh and you ang okay but now the problem is if this remains stale these predictions will not be as relevant anymore for ben because he he has changed in the meanwhile okay so the solution is to use what i already explained and that's using some kind of like a gnn module like get and you you get the updated version uh of the of the embedding because his friends presumably presumably his friends haven't stopped using twitter so their states are are being constantly being updated so we can use the the top so we can use that information to make a more relevant predictions for ben okay hopefully that makes sense and um they had a couple of baselines so the one i mentioned the the simplest one is just you take the you just take the state of of the user so that's this uh identity uh embedding so the final embedding is just whatever the state is and they show that this has a really bad performance on the later benchmarks okay and then we have this time projections simple equation you can check it out yourself i'll focus on on on the temporal graph attention so this is the important part this is the strongest baseline basically they had uh and the way it works it's it's the same thing as get uh just instead of using um the the attention uh that get used originally they just use the original of aswani attention so that means they have uh queries keys and values and everything else remains the same um basically the new information here is uh this phi function and the fact they're using multiple features concatenated here to get the final uh embedding representation okay so let's see how it exactly works so this h so for a particular node at a particular time t how they calculate the h is like this so they they take the state of that node at a particular time t and they take the node's features so that's basically maybe a description on your profile and then birth embedding blah blah blah blah and you basically just add them up and that's your zero zero that's the row that those are the raw features okay so we concatenate those with the with the uh basically edge information so let me let me draw uh example here it'll be easier we have a node we have a bunch of nodes here again we'll do the most recent uh neighbors will just kind of disregard all of the others so let's say we only take these two into account okay so we'll these are these will have some um these will have some features so if this is node one this is maybe node i so this is uh node i1 and this is node i j sorry j1 and uh so you just combine those information and you combine with phi so what's what's phi exactly here and uh it's a it's a there is a this nice paper called um time to work time to work and you can check it out but basically so that's one thing you could do and uh basically what you do is in order to get the vectorized representation of time you just map it into the following thing so you map it into a vector that has uh features like this so maybe uh w1 t plus uh n1 and then the second feature will be sine of w2 t plus n2 etc so you just continue using signs here and you increment um the arguments by one so we have w3 etc so these are learnable so you learn w2 and 2 w1 and 1 etc and if you take a closer look and you're familiar with the transformer this kind of resembles the positional encodings except that these are uh time aware okay and basically so you learn these and they showed in the time to work paper that you basically uh these are capturing the periodicity in the signal whereas this one is capturing something more uh constant in the signal so this one if you take a look this is just a simple uh basically a line and these here are sinusoids so you basically are learning sinusoids like this and the higher the w the the higher the frequency will be and if you have some smaller w then you'll have slower smaller frequency etc and these are just the offset these are just encoding the offset of your sinusoids so that's the simple heuristic they use to encode a time and once you have that you just do simple multi-head attention and you get the aggregated feature vector you concatenate it with the current feature vector and you pass it through an mlp so this thing here hi corresponds to this node and the second term here is the aggregated uh combination of these two because they are their most recent neighbors right so we kind of associate some alphas alpha one alpha two here and uh we combine them like a simple weighted sum and we get the features so that's how we calculate the embedding and they show that graph attention uh network is the best baseline we'll see that in a minute so that was that was all the nitty-gritty details um we saw how to train these uh uh how to how to pass how to pass some gradient information to these modules we saw how they exactly work and now we'll see a couple more details and then i'll zoom out um i already mentioned this part about the information leakage and so i'll skip it and so that's the reason we had to introduce the raw memory storage and this part is interesting so while from the perspective of the first interaction in the batch the memory is up to date since it contains information about all previous interactions in the graph from the perspective of the last interaction in the batch the same memory is out of date since it lacks information about previous interactions in the same batch this incentivizes the use of a big batch size so let me break it down for you um that means the following so we have the previous batch information we update the states and now this first because this is a batch that's chronologically sorted we have t5 t6 so this first interaction will be using states which are totally up to date but once this one is done we should basically have s1 and s2 updated because once an interaction happens we calculate the messages for the nodes that that are associated with that interaction and we update the states but we can't do that while we are in the batch so that means this to this one here two to three will use the same state as this one here and that means it's slightly out of date and now imagine the bigger batch and they use 200 as a nice trade-off and the the deeper you are in the batch let's call it that way the the more the more stale this current state representation is so that's the reason you don't want to have a too big of a batch but then again you don't want to keep it too slow too small because otherwise it will be really compute inefficient to have a small batch size okay so that's that part and now let me just show you the results before before i do a high level overview so they had some continuous this dynamic graph baselines here like jody tgad which is basically the same thing as t like this this paper at tgm it just doesn't have memory and the associated modules so it's a simplification of this of this paper basically it's a specific case specific instance and they also experimented with different basically different embedding methods using memory or not using memory module etc so they have a bunch of baselines and the results are the following so the tgm with attention achieves the best results overall on all of the three data sets so i was continuously using twitter as a running example but they also have wikipedia and reddit where this one is just users are notes and pages are notes and user editing a page is an interaction event and basically the edit text is what the feature for the edges etc okay similarly for reddit so it's those are bipartite graphs so we have have pages here we have users here and let me see what's also interesting they also did node-wise classification but that's not so so important for this paper and here are some ablation studies basically you can see that let me just zoom in a little bit basically the the tgm with attention is the best trade-off overall because it takes less time than these two whereas the performance is really similar so this one just uses two get layers and the reason one get layer is enough is because they are using this memory thing and the memory thing already implicitly contains the information from the neighboring nodes so using one layer you're basically you're basically accessing the features from the two hop neighborhood okay and using mean i think the mean just means they are using for the for the memory aggregation they are using the mean instead of the last last heuristic and you can see t get and jody and direp these other baselines are way lower performance wise than than this method some ablations again with their own model what they don't use the memory you can see the the worst curve is here when they add two layers again no memory it's a bit better and then as we add the memory and we add the the the the the last message aggregation heuristic we get the best results overall so that's pretty much it let me see if there is something else left that's it now let me just now with all the information you have in your head let me just briefly go ahead and explain it again okay now that we have all the information explained let me just kind of give you a holistic overview of the whole pipeline so here we have the information from the previous batches of these edge interactions okay and that means we have so rm1 is basically si contains si sj contains the delta t so the time that elapsed between the previous interaction and this interaction and we have ej which is the note the interaction features and we have the same tuples for all of the others the thing is we only focus on the nodes that we need so this thing may be huge and contain information for for many other notes in our graph we only care about nodes one two and three and that's why we only calculate those messages so we have we we just basically do a concatenation that's what they did and you get m1 you do a concatenation you get m2 etc at different timestamps okay now the aggregation they used either the mean or the last message so basically you just take let's say we we use the last message we just pass this message into the next step and that's the aggregated messages array once we have those we just have grew here and for every one of those we pass the state we have feed in the message we we spit out the new state when we update the states so now we have the states and the the computer this part is included into the computational graph now we use those states and we use get to create the embeddings now interesting thing here to note is so we have nodes one two and three but because this node one maybe has some other neighbors it will make sense it will make sense to have other states here as well so whatever the neighbors are i'll call them sn so those are these these guys here it will be useful to have the states for them updated as well because those will be included by a get because get accumulates the neighborhood information right so those will be accumulated by the get so i guess they just missed to to place sn here like the neighbors but whatever and finally you calculate the embeddings and now you just depending on the ground truth so these exist but the negative the negative ones don't exist so you just use binary cross entropy loss to train this whole pipeline end to end and now you have a system that can successfully predict uh given two nodes given two yeah given two nodes you can calculate their embeddings and you can predict whether they are likely to interact in the future and that's useful for twitter because you can use that to recommend for node a which node should that node follow in the future like maybe andre ang or which which tweets should that user see etc couple of strange things i've noticed in the paper maybe maybe a typo or something basically if you take a look at the query it doesn't have the edge information here so that means if you're doing a scale dot product between the the query and the keys you have a like a differently dimension vectors so you can do it so it's either a typo or they have some additional projection layer here that they didn't explicitly include here or i've missed something the second thing is i mentioned the memory staleness problem but basically if it's like they are implicitly stating that you need to retweet somebody else in order for your memory state to get updated but what if somebody retweets my post so i assume because that interaction involves my node and that person's node so because the way how the messages are computed my node state should be updated as well so i'm not sure um uh whether they're just simplifying it here in the paper but anyways uh just just keep that in mind that uh that's not super clear because for me it looks like that my state should be updated even though i'm not active on twitter because other people are interacting with me and thus my memory state is being updated constantly they're probably using a directed edge assumption here but it's not super clear from the paper uh one more thing to keep in mind is that this memory uh table is not uh let me open a pen is not trainable so what is trainable is the group here the lstm and potentially the message and aggregation functions even though they just use the concatenation so there's no learner learnable parameters here neither there is learnable parameters in their aggregation function so they're left up with learning mem so that means once the the model is fully trained uh you're basically once an interaction happens you just calculate the messages and you basically uh aggregate them and you update the states and um that's it and once you once you want to predict do some recommendation then you use the the get module and create those embeddings and just make the recommendation so that was all i had to say for this video you know the drill subscribe hit the bell icon and until next time keep learning deep you
[{"start": 0.0, "end": 6.8, "text": " I want to make shout out to Shantanu who recommended I create a video on TGN temporal graph networks"}, {"start": 6.8, "end": 13.52, "text": " and it was about time since dynamic networks is such an interesting concept, interesting research"}, {"start": 13.52, "end": 19.2, "text": " direction and many real world applications such as social media networks rely on"}, {"start": 19.2, "end": 25.44, "text": " having the modeling these dynamic graphs. So what's a dynamic graph? So basically whenever you have,"}, {"start": 25.44, "end": 31.12, "text": " so in contrast with static graphs, basically here you have the nodes can be added, deleted,"}, {"start": 31.12, "end": 37.44, "text": " modified, same goes with edges. So we basically have two types of events. We have node-wise events"}, {"start": 37.44, "end": 44.400000000000006, "text": " and we have interaction or edge events. So let's say we have some simple network here like graph"}, {"start": 44.400000000000006, "end": 50.88, "text": " and it can be multi-graph in a general case and basically I'll be using Twitter as a running"}, {"start": 50.88, "end": 58.080000000000005, "text": " example since the authors of this paper, Emanuella Rossi, Ben Fabrizio, David Federico and Michael"}, {"start": 58.080000000000005, "end": 63.92, "text": " Bronstein are all from Twitter. Let's say Anna decides to join Twitter. So basically she signs up,"}, {"start": 64.48, "end": 70.72, "text": " she fills up this sign-up form and now she's a new node in Twitter, social graph and that's"}, {"start": 70.72, "end": 75.12, "text": " basically the node addition event. Now let's say after a couple of days she was just kind of"}, {"start": 75.12, "end": 81.52000000000001, "text": " retweeting people and every single retweet is basically an edge in that graph. Now Ben joins"}, {"start": 81.52000000000001, "end": 86.56, "text": " Twitter and because those two broke up, Anna is pissed off and she just deletes the Twitter"}, {"start": 86.56, "end": 92.32000000000001, "text": " account altogether and that's the node deletion event. Now Ben is also pissed off and so he decides"}, {"start": 92.32000000000001, "end": 99.28, "text": " to update his user profile, updates his description and by updating the description he's basically"}, {"start": 99.28, "end": 106.0, "text": " changing his feature vector and you can think of it maybe we take this text and we pass it in a BERT"}, {"start": 107.28, "end": 113.28, "text": " encoder and we basically have CLS here, token, hopefully you're familiar with BERT. If you're"}, {"start": 113.28, "end": 120.48, "text": " not, just treat it as a black box. We input the text here, we get out the condensed representation"}, {"start": 120.48, "end": 126.48, "text": " here and we use exactly this thing as the feature vector. So that's the node modification event."}, {"start": 126.48, "end": 134.72, "text": " Now after a couple of days of activity he decides to retweet Andrew Eng's school post"}, {"start": 134.72, "end": 142.8, "text": " and basically now whatever the retweet text is that's the edge feature vector and now maybe he"}, {"start": 142.8, "end": 148.4, "text": " made a typo so he decides to modify the text even though that's not possible on Twitter,"}, {"start": 148.4, "end": 153.68, "text": " but let's say it is and for the sake of argument and basically that's the edge modification event"}, {"start": 153.68, "end": 159.68, "text": " where now the new text is again fed through BERT and we get the new feature vector and finally he"}, {"start": 159.68, "end": 166.24, "text": " decides to just delete the tweet altogether and that's the edge deletion event. So that's how the"}, {"start": 166.24, "end": 172.8, "text": " dynamic graph works in a nutshell. It's basically a multi-graph because every single node can have"}, {"start": 172.8, "end": 179.84, "text": " multiple edges between, so the nodes are connected by multiple edges and that's what's known as a"}, {"start": 179.84, "end": 187.68, "text": " multi-graph. Okay, dead out of the way, let's jump into the paper and see what they say. So they say"}, {"start": 187.68, "end": 191.36, "text": " here a few approaches have been proposed for dealing with graphs that are dynamic in nature."}, {"start": 191.36, "end": 197.36, "text": " So basically most of the research in graph ML was focusing on static graphs and not on dynamic"}, {"start": 197.36, "end": 203.52, "text": " graphs and while it is possible to apply static graph deep learning models to dynamic graphs by"}, {"start": 203.52, "end": 209.04, "text": " ignoring the temporal evolution, this has shown been shown to be suboptimal. So what that means"}, {"start": 209.04, "end": 214.4, "text": " is the following. So you have this graph here and basically every single edge has a time stamp"}, {"start": 214.4, "end": 221.12, "text": " attached to it. So let's say Ben here has got maybe three retweets of Andrew Ang and this one"}, {"start": 221.12, "end": 226.64, "text": " happened at t1, this one happened at t2, this one happened just recently like a couple of seconds"}, {"start": 226.64, "end": 233.2, "text": " ago at t3 and you can treat this as a static graph, just a static multi-graph or you can"}, {"start": 233.2, "end": 238.88, "text": " kind of acknowledge the like the existence of these time stamps and use that to, when you"}, {"start": 238.88, "end": 243.67999999999998, "text": " sub sample your neighborhood later and we'll see why we do that a bit later, but when we"}, {"start": 243.67999999999998, "end": 250.32, "text": " sub sample the neighborhood we can just take the most recent edges and by doing that we have a"}, {"start": 250.32, "end": 255.35999999999999, "text": " much more optimal performance than just by treating this as a static graph and doing uniform"}, {"start": 255.35999999999999, "end": 261.36, "text": " sampling of the neighborhood. So yeah, basically that's suboptimal, you can treat it as a"}, {"start": 261.36, "end": 268.72, "text": " static graph but it's suboptimal, okay? And yeah, so learning on dynamic graphs is relatively recent"}, {"start": 268.72, "end": 275.12, "text": " and most of the previous work was focused on these discrete time dynamic graphs which is just"}, {"start": 275.12, "end": 282.32, "text": " a sequence of snapshots of the graph. So basically you have your graph that's evolving and what you"}, {"start": 282.32, "end": 287.6, "text": " do in this discrete time dynamic graph is the following. You just take a snapshot at equidistant"}, {"start": 287.6, "end": 296.56, "text": " moments, so maybe you had some graph at t1 that looked like this and then after some period"}, {"start": 296.56, "end": 300.96000000000004, "text": " and the important part here is that this is pretty much the same constant so you have"}, {"start": 300.96000000000004, "end": 306.56, "text": " equidistant moments when you take the snapshot and maybe a couple of more edges and nodes appeared"}, {"start": 306.56, "end": 314.8, "text": " etc. So like this, I don't know, whatever. And you do the same thing after the same time period t."}, {"start": 314.8, "end": 319.6, "text": " This is basically the improvement over the static graph modeling but this discrete time"}, {"start": 321.04, "end": 325.68, "text": " dynamic graphs are still limited compared to the continuous ones that we're gonna see in this paper."}, {"start": 326.56, "end": 332.56, "text": " Okay, a small recap basically when you want to compute the embeddings for the static graph,"}, {"start": 332.56, "end": 339.12, "text": " you just have basically accumulation over the neighborhood of these messages and h is just"}, {"start": 339.12, "end": 345.04, "text": " a trainable update function and that's how you get your embeddings. That's what this equation here"}, {"start": 345.04, "end": 351.04, "text": " stands for. But it's not so important now so I just want to kind of walk you through some terminology"}, {"start": 351.04, "end": 355.6, "text": " that we'll be using and that's as I already mentioned we have this discrete time dynamic graphs"}, {"start": 355.6, "end": 361.84000000000003, "text": " or DTDGs for short and we have continuous time dynamic graphs on the other hand and those are"}, {"start": 361.84000000000003, "end": 367.84000000000003, "text": " the ones we'll be treating in this video. And basically the point here is that you have to"}, {"start": 367.84, "end": 374.08, "text": " the point here is we treat it as a sequence of time stamped events. So every single event"}, {"start": 374.08, "end": 382.0, "text": " be it nodewise event, be it the edge event has a time stamp associated with it. Contrast that with"}, {"start": 382.0, "end": 388.64, "text": " static graphs where we had those equidistant snapshots. And I already explained those two"}, {"start": 388.64, "end": 394.71999999999997, "text": " and now the interesting concept, new concept that's not encountered in static graphs is this"}, {"start": 394.72, "end": 399.76000000000005, "text": " concept of a temporal neighborhood. So what it means basically is the following. So again you have"}, {"start": 399.76000000000005, "end": 410.0, "text": " some nodes in the graph and let's say there are multiple edges here and let's say this one"}, {"start": 410.96000000000004, "end": 418.64000000000004, "text": " happened at t5 and we're currently looking for some reason we're looking at a moment that happened"}, {"start": 418.64, "end": 424.71999999999997, "text": " before prior to t5 like at t4. That basically means that the neighborhood of this graph here"}, {"start": 425.44, "end": 431.68, "text": " is will ignore this edge. So everything that comes after this particular target"}, {"start": 433.84, "end": 439.84, "text": " moment of time is ignored and that's what you're left with. So all of the other edges here is"}, {"start": 439.84, "end": 446.24, "text": " what's known as the temporal neighborhood of this particular node at this point of time. Okay so"}, {"start": 446.24, "end": 453.12, "text": " that's a new concept and with that out of the way let's jump and see what are the main modules in"}, {"start": 453.12, "end": 458.88, "text": " this TGN network. Okay let me give you a quick high level overview of the system and then we'll"}, {"start": 458.88, "end": 466.16, "text": " slowly start building on and adding new details. So high level how we train this graph neural"}, {"start": 466.16, "end": 472.08, "text": " network, this whole system actually because it also has this thing called memory, is the following. So"}, {"start": 472.08, "end": 479.59999999999997, "text": " we do a self-supervised learning and we're learning how to do link prediction. So basically because"}, {"start": 479.59999999999997, "end": 485.76, "text": " we have all of those retweets and we have time stamps associated with them we can just do"}, {"start": 485.76, "end": 491.84, "text": " chronological sort over all of those interactions and we can just predict the interactions that"}, {"start": 491.84, "end": 499.84, "text": " haven't yet happened and that's basically the you just batch that chronologically sorted array of"}, {"start": 499.84, "end": 505.76, "text": " those edge interactions and you just predict the follow-up edges. It's a similar thing as"}, {"start": 505.76, "end": 510.4, "text": " transformers there you're trying to predict the follow-up word and here you're trying to predict"}, {"start": 510.4, "end": 516.0799999999999, "text": " what the next interaction will be. So that's the high level overview of how the thing works. So now"}, {"start": 516.0799999999999, "end": 523.1999999999999, "text": " let's see on this chart what happens basically. So you have you have and I'll just create a simple"}, {"start": 523.2, "end": 534.48, "text": " example here. We have node 1, we have nodes 2 and we have node 3. So 1 as you can see here at t1,"}, {"start": 534.48, "end": 547.44, "text": " 1 retweeted node 2 and at t2 node 2 retweeted node 3. So like this. So now what we do is the following."}, {"start": 547.44, "end": 554.6400000000001, "text": " We have so because node 1 also had some other interactions maybe that happened even prior to"}, {"start": 554.6400000000001, "end": 563.0400000000001, "text": " these interactions. So let's say these happened at whatever t0 maybe. Okay so now what happens is that"}, {"start": 563.0400000000001, "end": 567.6, "text": " we have this embedding method and that's basically get. If you if you haven't watched my video"}, {"start": 568.24, "end": 573.7600000000001, "text": " on graph attention networks you can check it out. I'll link it somewhere here and you basically do"}, {"start": 573.76, "end": 580.88, "text": " one layer get over this node 1 over its temporal neighborhood and we already mentioned what that is."}, {"start": 580.88, "end": 588.72, "text": " We do get and we calculate the embeddings for nodes 1, 2 and node 3 right and those are these z's."}, {"start": 588.72, "end": 594.0, "text": " Once we have those we can just calculate the probability using a simple decoder. So they used"}, {"start": 594.0, "end": 600.48, "text": " MLP here. So you just concatenate these two embeddings. You just pass them through MLP"}, {"start": 600.48, "end": 606.24, "text": " and you just add the non-linear function like sigmoid non-linearity and that means this is"}, {"start": 606.24, "end": 611.76, "text": " basically probability. And now in order to train you do the following. So you want to make sure"}, {"start": 611.76, "end": 618.88, "text": " that P so given t1 what's the probability of interaction between 1 and 2 happening?"}, {"start": 618.88, "end": 623.04, "text": " And we know it's 100% it's 1 because it already happened. We have it in the data set right."}, {"start": 623.04, "end": 631.36, "text": " We did it chronological sort. So you want to push the loss to go to 1, P to go to 1."}, {"start": 632.0799999999999, "end": 639.4399999999999, "text": " I loss will be 0 because we're just using simple binary cross entropy here and we'll also have"}, {"start": 639.4399999999999, "end": 646.0, "text": " negative edges which we'll want to make sure that the probability goes to 0 and yeah that's it."}, {"start": 646.0, "end": 653.84, "text": " So if you have maybe some nodes x and nodes y and this interaction hasn't happened we want to make"}, {"start": 653.84, "end": 663.44, "text": " sure that we push the probability to 0 for those node pairs. And we use a simple as I mentioned"}, {"start": 663.44, "end": 670.96, "text": " so loss is just a binary cross entropy that means that's a fancy name for you just put the log here."}, {"start": 670.96, "end": 677.44, "text": " So basically if we have positive examples we'll just the loss will have a format like this minus"}, {"start": 677.44, "end": 687.6, "text": " log of P right and if I just draw it here that will look like this and basically we want to push"}, {"start": 687.6, "end": 693.76, "text": " the probability to go to 1 because then the loss goes to 0. For when we have negative examples"}, {"start": 693.76, "end": 704.56, "text": " we'll just have minus log of 1 minus P and that will just kind of mirror this chart here"}, {"start": 704.56, "end": 710.56, "text": " and it will look like this. So we have P on the x-axis, we have loss on the y-axis and the loss"}, {"start": 710.56, "end": 720.24, "text": " will look like this. Basically at 0 we have loss that's equal to 0 and at 1 it goes to infinity."}, {"start": 720.24, "end": 725.84, "text": " So that's how we train it simple BC we have positives we have negatives we have the data"}, {"start": 725.84, "end": 735.76, "text": " set with and we just batch it and we use those batches to predict those links because we know"}, {"start": 735.76, "end": 742.96, "text": " they're there. So how the embedder part works so get leverage is something called memory or"}, {"start": 742.96, "end": 748.96, "text": " states in this TGN network. So what it is is basically every single node in our graph in"}, {"start": 748.96, "end": 755.76, "text": " Twitter graph has a state associated with it. So we have a huge table and every single node in this"}, {"start": 755.76, "end": 761.84, "text": " table has some representation and they said here basically the purpose is to represent the node's"}, {"start": 761.84, "end": 768.5600000000001, "text": " history in a compressed format and that's exactly what it does. So basically over the when the"}, {"start": 768.5600000000001, "end": 773.2800000000001, "text": " interactions are happening in Twitter we're basically using all of those to just update"}, {"start": 773.28, "end": 780.24, "text": " this memory state and then we can use those to later do some recommendations but I'll get to that"}, {"start": 780.24, "end": 785.92, "text": " in a moment okay. So we have these states and they are somehow calculated so we have some messages"}, {"start": 785.92, "end": 793.12, "text": " we do some aggregation we somehow use them to update the memory state and then the embedding"}, {"start": 793.12, "end": 800.0799999999999, "text": " method the get will just use those to calculate the embeddings and we can predict the links."}, {"start": 800.08, "end": 805.5200000000001, "text": " So that's the high level overview and now we'll slowly start digging into details hopefully"}, {"start": 805.5200000000001, "end": 815.12, "text": " it was clear enough. Maybe one more thing worth mentioning when we are using get in this model"}, {"start": 815.84, "end": 821.84, "text": " the way we we sub sample the neighborhood is using the most recent edges so that's why we"}, {"start": 821.84, "end": 829.36, "text": " have timestamps. So basically if we have a bunch of edges we'll use we'll only sub sample the"}, {"start": 829.36, "end": 837.12, "text": " most recent k ones so we we sort the the neighborhood edges by timestamps and we just take the k most"}, {"start": 837.12, "end": 842.16, "text": " recent ones that may be like 10 most recent neighbors and then you just do the simple get"}, {"start": 842.16, "end": 849.36, "text": " aggregation and we'll see what exact features go inside here in a sec. Okay now the problem with"}, {"start": 849.36, "end": 856.72, "text": " this chart is if you maybe if you noticed is that we are using these interactions to calculate the"}, {"start": 856.72, "end": 863.44, "text": " messages to update the states and then we're using that those states to predict the links so"}, {"start": 863.44, "end": 869.2, "text": " that means we have information leakage here we're basically using this information to update states"}, {"start": 869.2, "end": 875.2, "text": " and then we're using the states to predict those links and that doesn't make any sense right but"}, {"start": 875.2, "end": 882.88, "text": " because you somehow have to you somehow have to calculate and use these message functions to get"}, {"start": 882.88, "end": 887.4399999999999, "text": " the states because otherwise you won't have any gradients flowing towards these trainable functions"}, {"start": 887.4399999999999, "end": 893.2, "text": " the aggregated messages and messages and this mem function they are all trainable so you somehow"}, {"start": 893.2, "end": 899.76, "text": " have to have this forward pass here but you can use this batch you'll just use the previous batches"}, {"start": 899.76, "end": 905.4399999999999, "text": " and that's the solution so basically they have a graph here okay you have to introduce this concept"}, {"start": 905.4399999999999, "end": 911.36, "text": " of a raw memory storage and now what you do here is from the previous batch you just store the"}, {"start": 911.36, "end": 917.76, "text": " previous batch you just stored all the necessary information inside here so now when you try to"}, {"start": 917.76, "end": 925.12, "text": " predict the the the existence of a link between one and two the the existence of of retweet in"}, {"start": 925.12, "end": 931.2, "text": " the case of twitter what you do is the following you use the the the last batch and i mean not just"}, {"start": 931.2, "end": 936.08, "text": " the last batch actually the whole history and you calculate the messages and we'll see how we do that"}, {"start": 936.08, "end": 941.12, "text": " so we have some data here that's necessary to calculate these messages then we just aggregate"}, {"start": 941.12, "end": 947.36, "text": " the messages so you see here that messages for the node two are kind of accumulated and then we"}, {"start": 947.36, "end": 953.84, "text": " update the states and they just use grue here and we'll see those details so what happens is basically"}, {"start": 953.84, "end": 964.88, "text": " you you you have the previous state so this is grue g r u you just use s2 and this is the old state"}, {"start": 964.88, "end": 972.96, "text": " and you use the the newest message this m2 aggregated and this will just spit out new state"}, {"start": 972.96, "end": 979.92, "text": " and we just write it down here so that's how we update the the states now the states have now we"}, {"start": 979.92, "end": 987.28, "text": " have this thing like included in the computation graph and we just use get to calculate embeddings"}, {"start": 987.28, "end": 992.8, "text": " and to we get to the loss so now gradient gradients can now flow through the whole system"}, {"start": 992.8, "end": 998.9599999999999, "text": " and all of these functions which will see what they exactly are so these egg these mem functions"}, {"start": 998.9599999999999, "end": 1005.52, "text": " will be updated in the back propagation step okay so that's the important solution so introduction"}, {"start": 1005.52, "end": 1011.5999999999999, "text": " of raw message store is important because that allows us to train this part of the pipeline this"}, {"start": 1011.5999999999999, "end": 1020.24, "text": " part here okay okay hopefully that was clear enough um let me let me slowly start digging into"}, {"start": 1020.24, "end": 1026.0, "text": " into details of how the messages are computed and then once we have all of those details i'll again"}, {"start": 1026.0, "end": 1032.16, "text": " zoom out and try and explain everything okay so messages are computed the following once interaction"}, {"start": 1032.16, "end": 1038.08, "text": " happens between nodes i and j so we have node i we have j one of them retweeted the other so we have"}, {"start": 1038.08, "end": 1043.36, "text": " interaction that happened and it has feature vector associated with it so that's e i j right"}, {"start": 1043.36, "end": 1052.56, "text": " okay so how we calculate the message is basically we input the previous states and this t minus"}, {"start": 1052.56, "end": 1059.9199999999998, "text": " just means the state before this interaction happened for those notes so that's basically"}, {"start": 1059.9199999999998, "end": 1066.08, "text": " whatever is currently in the state table so we have si here we have sj so whatever is currently"}, {"start": 1066.08, "end": 1071.4399999999998, "text": " in there we use those and we input them in the message function and we additionally use the"}, {"start": 1071.44, "end": 1075.52, "text": " uh this feature vector i just mentioned so that's like the maybe birth encoding of retweet"}, {"start": 1076.4, "end": 1081.68, "text": " and we finally use this delta t which is the time that has elapsed between the previous interaction"}, {"start": 1081.68, "end": 1087.44, "text": " and this current interaction so that may be like 30 seconds or whatever and that's how we compute"}, {"start": 1087.44, "end": 1095.04, "text": " the message for this for this node i and then we do analogously to node j so that's the destination"}, {"start": 1095.04, "end": 1100.48, "text": " so that's the source and destination nodes and the only difference is these are permuted if you can"}, {"start": 1100.48, "end": 1106.64, "text": " if you can notice here so just permutation simple permutation and uh although this can be trainable"}, {"start": 1106.64, "end": 1112.08, "text": " what it did is they in practice use just identity function which means they are just doing simple"}, {"start": 1112.08, "end": 1117.6, "text": " concatenations uh between all of these features so you have some vector here vector you concatenate"}, {"start": 1117.6, "end": 1124.0, "text": " all of them and that's your message and this here is an interesting thing and i'll later explain"}, {"start": 1124.0, "end": 1130.08, "text": " uh how we convert time to a vector uh to a vector representation and just stay tuned for that okay"}, {"start": 1130.64, "end": 1136.4, "text": " so that's the uh so that's the part with with the messages okay and they say here a more complex"}, {"start": 1136.4, "end": 1140.16, "text": " message function that involves additional aggregation from the neighborhoods from the"}, {"start": 1140.16, "end": 1146.16, "text": " neighbors of nodes i and j is also possible and is left for future study so the thing with this"}, {"start": 1146.16, "end": 1150.8, "text": " paper is there is there is a it's a it's a work in progress there is a lot of things they still want"}, {"start": 1150.8, "end": 1158.96, "text": " to try and they haven't tried it so for example they have this uh node-wise uh memory but they"}, {"start": 1158.96, "end": 1164.1599999999999, "text": " also they say here while a global graph-wise memory can also be added to the model to track"}, {"start": 1164.1599999999999, "end": 1169.04, "text": " the evolution of the entire network we'll leave this as a future work so that's that's my point"}, {"start": 1169.6, "end": 1176.24, "text": " there is still a lot of things uh evolving in this work so yeah just just keep that in mind"}, {"start": 1176.24, "end": 1183.36, "text": " um okay so once we have the message function so that's this part right so that's the messages how"}, {"start": 1183.36, "end": 1188.88, "text": " do we aggregate them and here we just have a message aggregator and again it can be a trainable"}, {"start": 1188.88, "end": 1195.68, "text": " function but what they did is they just do a simple most recent message and mean message"}, {"start": 1195.68, "end": 1203.44, "text": " heuristic and you can even see it here so what it did is you have m2 at t1 you have m2 at t2"}, {"start": 1203.44, "end": 1209.6000000000001, "text": " they just took the last message and that's the aggregation okay um in more general case they can"}, {"start": 1209.6000000000001, "end": 1216.72, "text": " also just do a mean or something else just kind of do make it trainable uh maybe pass it through an"}, {"start": 1216.72, "end": 1223.3600000000001, "text": " rnn or whatever okay but it's stuck with the most recent message and let's use it as the running"}, {"start": 1224.0800000000002, "end": 1230.16, "text": " example uh finally we have the memory updater i already explained that they used some form you"}, {"start": 1230.16, "end": 1236.64, "text": " can use whatever like rnn or lstm they used a grew which is a specific type of of lstm basically"}, {"start": 1237.2, "end": 1242.72, "text": " and i already explained how it works but let me just repeat okay let's this is grew and we have"}, {"start": 1243.52, "end": 1254.8000000000002, "text": " we have the state state i t minus we just get the new message and we just run this and there are"}, {"start": 1254.8000000000002, "end": 1259.76, "text": " like a if you know how if you don't know how grew works i'll just link uh chris ola's blog he has"}, {"start": 1259.76, "end": 1264.24, "text": " a really nice blog intuitive to understand how this works basically a bunch of forget and update"}, {"start": 1264.24, "end": 1269.52, "text": " gates and this spits out we can treat it as a black box for now it just spits out the new state"}, {"start": 1270.8799999999999, "end": 1278.8799999999999, "text": " si at point t so this was a t minus and here we have the current state so that's the memory"}, {"start": 1278.8799999999999, "end": 1287.84, "text": " updating part okay finally uh we have the embedding module uh and um so i haven't mentioned this but"}, {"start": 1287.84, "end": 1293.12, "text": " the main goal of the embedding module is to avoid the so-called memory staleness problem so what that"}, {"start": 1293.12, "end": 1300.08, "text": " means is the following so let's say we we have a graph and um like we have we had ben here"}, {"start": 1301.12, "end": 1307.84, "text": " and maybe ben stopped uh using twitter for maybe a month or two and now what happens is that his if"}, {"start": 1307.84, "end": 1315.4399999999998, "text": " you take a look at the memory so and we we take ben's state uh because he's not interacting with"}, {"start": 1315.44, "end": 1325.1200000000001, "text": " anybody anymore um we this this representation is not updated and so um we we we need to have"}, {"start": 1325.1200000000001, "end": 1332.24, "text": " uh some sort of of of embedding to to to make this relevant for ben when he returns so if we want to"}, {"start": 1332.24, "end": 1338.16, "text": " recommend to ben which tweets should he uh see so that's like your your home page on twitter you see"}, {"start": 1338.16, "end": 1343.28, "text": " a bunch of tweets so twitter somehow needs to figure out which tweets are relevant for you and"}, {"start": 1343.28, "end": 1348.6399999999999, "text": " also uh twitter should recommend you what's the what's what what are the persons you should"}, {"start": 1348.6399999999999, "end": 1354.08, "text": " probably follow so how they do that is the following so ben has uh his state b and in the"}, {"start": 1354.08, "end": 1359.12, "text": " simplest case you could just do the following you could just take sp and maybe andrew ang has his"}, {"start": 1359.12, "end": 1366.32, "text": " own state sa and you just do a dot product or mlp and uh whatever and that spits out some probability"}, {"start": 1366.32, "end": 1373.52, "text": " so if the probability is close to one uh twitter may recommend that you follow uh and you ang okay"}, {"start": 1373.52, "end": 1379.84, "text": " but now the problem is if this remains stale these predictions will not be as relevant anymore for"}, {"start": 1379.84, "end": 1386.08, "text": " ben because he he has changed in the meanwhile okay so the solution is to use what i already"}, {"start": 1386.08, "end": 1392.96, "text": " explained and that's using some kind of like a gnn module like get and you you get the updated"}, {"start": 1392.96, "end": 1400.08, "text": " version uh of the of the embedding because his friends presumably presumably his friends haven't"}, {"start": 1400.64, "end": 1406.96, "text": " stopped using twitter so their states are are being constantly being updated so we can use the the"}, {"start": 1406.96, "end": 1412.56, "text": " top so we can use that information to make a more relevant predictions for ben okay hopefully that"}, {"start": 1412.56, "end": 1420.32, "text": " makes sense and um they had a couple of baselines so the one i mentioned the the simplest one is"}, {"start": 1420.32, "end": 1427.4399999999998, "text": " just you take the you just take the state of of the user so that's this uh identity uh embedding"}, {"start": 1427.4399999999998, "end": 1433.6, "text": " so the final embedding is just whatever the state is and they show that this has a really bad"}, {"start": 1433.6, "end": 1439.4399999999998, "text": " performance on the later benchmarks okay and then we have this time projections simple equation you"}, {"start": 1439.4399999999998, "end": 1445.28, "text": " can check it out yourself i'll focus on on on the temporal graph attention so this is the important"}, {"start": 1445.28, "end": 1451.6, "text": " part this is the strongest baseline basically they had uh and the way it works it's it's the same"}, {"start": 1451.6, "end": 1459.36, "text": " thing as get uh just instead of using um the the attention uh that get used originally they just"}, {"start": 1459.36, "end": 1465.92, "text": " use the original of aswani attention so that means they have uh queries keys and values and everything"}, {"start": 1465.92, "end": 1474.96, "text": " else remains the same um basically the new information here is uh this phi function and the"}, {"start": 1474.96, "end": 1482.0, "text": " fact they're using multiple features concatenated here to get the final uh embedding representation"}, {"start": 1482.0, "end": 1488.64, "text": " okay so let's see how it exactly works so this h so for a particular node at a particular time t"}, {"start": 1488.64, "end": 1497.2800000000002, "text": " how they calculate the h is like this so they they take the state of that node at a particular time"}, {"start": 1497.2800000000002, "end": 1503.1200000000001, "text": " t and they take the node's features so that's basically maybe a description on your profile"}, {"start": 1503.1200000000001, "end": 1508.24, "text": " and then birth embedding blah blah blah blah and you basically just add them up and that's your"}, {"start": 1508.24, "end": 1515.8400000000001, "text": " zero zero that's the row that those are the raw features okay so we concatenate those with the"}, {"start": 1515.84, "end": 1524.24, "text": " with the uh basically edge information so let me let me draw uh example here it'll be easier"}, {"start": 1524.24, "end": 1533.28, "text": " we have a node we have a bunch of nodes here again we'll do the most recent uh neighbors will just"}, {"start": 1534.3999999999999, "end": 1539.04, "text": " kind of disregard all of the others so let's say we only take these two into account okay"}, {"start": 1539.04, "end": 1546.0, "text": " so we'll these are these will have some um these will have some features so if this is node one"}, {"start": 1546.56, "end": 1561.28, "text": " this is maybe node i so this is uh node i1 and this is node i j sorry j1 and uh so you just combine"}, {"start": 1561.28, "end": 1566.8799999999999, "text": " those information and you combine with phi so what's what's phi exactly here and uh it's a"}, {"start": 1566.88, "end": 1575.2800000000002, "text": " it's a there is a this nice paper called um time to work time to work and you can check it out"}, {"start": 1576.0, "end": 1582.48, "text": " but basically so that's one thing you could do and uh basically what you do is in order to get"}, {"start": 1582.48, "end": 1588.3200000000002, "text": " the vectorized representation of time you just map it into the following thing so you map it into"}, {"start": 1588.32, "end": 1600.24, "text": " a vector that has uh features like this so maybe uh w1 t plus uh n1 and then the second feature will"}, {"start": 1600.24, "end": 1616.8799999999999, "text": " be sine of w2 t plus n2 etc so you just continue using signs here and you increment um the arguments"}, {"start": 1616.88, "end": 1629.6000000000001, "text": " by one so we have w3 etc so these are learnable so you learn w2 and 2 w1 and 1 etc and if you take"}, {"start": 1629.6000000000001, "end": 1634.3200000000002, "text": " a closer look and you're familiar with the transformer this kind of resembles the positional"}, {"start": 1634.3200000000002, "end": 1641.7600000000002, "text": " encodings except that these are uh time aware okay and basically so you learn these and they"}, {"start": 1641.76, "end": 1648.08, "text": " showed in the time to work paper that you basically uh these are capturing the periodicity in the"}, {"start": 1648.08, "end": 1654.16, "text": " signal whereas this one is capturing something more uh constant in the signal so this one if you take"}, {"start": 1654.16, "end": 1662.56, "text": " a look this is just a simple uh basically a line and these here are sinusoids so you basically are"}, {"start": 1662.56, "end": 1670.32, "text": " learning sinusoids like this and the higher the w the the higher the frequency will be and if you"}, {"start": 1670.32, "end": 1677.9199999999998, "text": " have some smaller w then you'll have slower smaller frequency etc and these are just the offset"}, {"start": 1678.96, "end": 1685.2, "text": " these are just encoding the offset of your sinusoids so that's the simple heuristic they"}, {"start": 1685.2, "end": 1692.0, "text": " use to encode a time and once you have that you just do simple multi-head attention and you get"}, {"start": 1692.0, "end": 1697.2, "text": " the aggregated feature vector you concatenate it with the current feature vector and you pass it"}, {"start": 1697.2, "end": 1706.64, "text": " through an mlp so this thing here hi corresponds to this node and the second term here is the"}, {"start": 1706.64, "end": 1713.52, "text": " aggregated uh combination of these two because they are their most recent neighbors right so we"}, {"start": 1713.52, "end": 1724.88, "text": " kind of associate some alphas alpha one alpha two here and uh we combine them like a simple weighted"}, {"start": 1724.88, "end": 1731.68, "text": " sum and we get the features so that's how we calculate the embedding and they show that graph"}, {"start": 1731.68, "end": 1738.48, "text": " attention uh network is the best baseline we'll see that in a minute so that was that was all the"}, {"start": 1738.48, "end": 1746.3200000000002, "text": " nitty-gritty details um we saw how to train these uh uh how to how to pass how to pass some"}, {"start": 1746.3200000000002, "end": 1751.6000000000001, "text": " gradient information to these modules we saw how they exactly work and now we'll see a couple more"}, {"start": 1751.6, "end": 1758.0, "text": " details and then i'll zoom out um i already mentioned this part about the information leakage"}, {"start": 1758.0, "end": 1763.84, "text": " and so i'll skip it and so that's the reason we had to introduce the raw memory storage and this"}, {"start": 1763.84, "end": 1767.6, "text": " part is interesting so while from the perspective of the first interaction in the batch the memory"}, {"start": 1767.6, "end": 1772.24, "text": " is up to date since it contains information about all previous interactions in the graph"}, {"start": 1772.24, "end": 1776.6399999999999, "text": " from the perspective of the last interaction in the batch the same memory is out of date"}, {"start": 1776.64, "end": 1782.5600000000002, "text": " since it lacks information about previous interactions in the same batch this incentivizes"}, {"start": 1782.5600000000002, "end": 1789.6000000000001, "text": " the use of a big batch size so let me break it down for you um that means the following so we"}, {"start": 1789.6000000000001, "end": 1796.0800000000002, "text": " have the previous batch information we update the states and now this first because this is a batch"}, {"start": 1796.0800000000002, "end": 1803.2, "text": " that's chronologically sorted we have t5 t6 so this first interaction will be using states which"}, {"start": 1803.2, "end": 1810.64, "text": " are totally up to date but once this one is done we should basically have s1 and s2 updated because"}, {"start": 1810.64, "end": 1815.92, "text": " once an interaction happens we calculate the messages for the nodes that that are associated"}, {"start": 1815.92, "end": 1821.3600000000001, "text": " with that interaction and we update the states but we can't do that while we are in the batch"}, {"start": 1821.3600000000001, "end": 1829.1200000000001, "text": " so that means this to this one here two to three will use the same state as this one here and that"}, {"start": 1829.12, "end": 1835.12, "text": " means it's slightly out of date and now imagine the bigger batch and they use 200 as a nice trade-off"}, {"start": 1835.76, "end": 1842.6399999999999, "text": " and the the deeper you are in the batch let's call it that way the the more the more stale"}, {"start": 1842.6399999999999, "end": 1849.28, "text": " this current state representation is so that's the reason you don't want to have a too big of a batch"}, {"start": 1849.28, "end": 1853.6, "text": " but then again you don't want to keep it too slow too small because otherwise it will be really"}, {"start": 1853.6, "end": 1862.48, "text": " compute inefficient to have a small batch size okay so that's that part and now let me just show"}, {"start": 1862.48, "end": 1872.3999999999999, "text": " you the results before before i do a high level overview so they had some continuous this dynamic"}, {"start": 1872.3999999999999, "end": 1878.1599999999999, "text": " graph baselines here like jody tgad which is basically the same thing as t like this this paper"}, {"start": 1878.16, "end": 1883.6000000000001, "text": " at tgm it just doesn't have memory and the associated modules so it's a simplification of this of this"}, {"start": 1883.6000000000001, "end": 1889.6000000000001, "text": " paper basically it's a specific case specific instance and they also experimented with different"}, {"start": 1890.8000000000002, "end": 1896.72, "text": " basically different embedding methods using memory or not using memory module etc so they have a"}, {"start": 1896.72, "end": 1902.88, "text": " bunch of baselines and the results are the following so the tgm with attention achieves the best"}, {"start": 1902.88, "end": 1908.8000000000002, "text": " results overall on all of the three data sets so i was continuously using twitter as a running"}, {"start": 1908.8000000000002, "end": 1916.64, "text": " example but they also have wikipedia and reddit where this one is just users are notes and pages"}, {"start": 1916.64, "end": 1923.5200000000002, "text": " are notes and user editing a page is an interaction event and basically the edit text is what the"}, {"start": 1923.5200000000002, "end": 1930.16, "text": " feature for the edges etc okay similarly for reddit so it's those are bipartite graphs so we have"}, {"start": 1930.16, "end": 1936.5600000000002, "text": " have pages here we have users here and let me see what's also interesting they also did"}, {"start": 1937.28, "end": 1944.0800000000002, "text": " node-wise classification but that's not so so important for this paper and here are some"}, {"start": 1944.0800000000002, "end": 1949.3600000000001, "text": " ablation studies basically you can see that let me just zoom in a little bit basically the the"}, {"start": 1949.3600000000001, "end": 1958.0, "text": " tgm with attention is the best trade-off overall because it takes less time than these two whereas"}, {"start": 1958.0, "end": 1965.04, "text": " the performance is really similar so this one just uses two get layers and the reason one get layer"}, {"start": 1965.04, "end": 1970.0, "text": " is enough is because they are using this memory thing and the memory thing already implicitly"}, {"start": 1970.0, "end": 1974.08, "text": " contains the information from the neighboring nodes so using one layer you're basically"}, {"start": 1975.12, "end": 1981.6, "text": " you're basically accessing the features from the two hop neighborhood okay and using mean i think"}, {"start": 1981.6, "end": 1986.88, "text": " the mean just means they are using for the for the memory aggregation they are using the mean"}, {"start": 1986.88, "end": 1994.8000000000002, "text": " instead of the last last heuristic and you can see t get and jody and direp these other baselines are"}, {"start": 1994.8000000000002, "end": 2004.72, "text": " way lower performance wise than than this method some ablations again with their own model what"}, {"start": 2004.72, "end": 2010.96, "text": " they don't use the memory you can see the the worst curve is here when they add two layers again"}, {"start": 2010.96, "end": 2018.24, "text": " no memory it's a bit better and then as we add the memory and we add the the the the the last"}, {"start": 2019.04, "end": 2026.56, "text": " message aggregation heuristic we get the best results overall so that's pretty much it"}, {"start": 2027.68, "end": 2033.1200000000001, "text": " let me see if there is something else left that's it now let me just now with all the information"}, {"start": 2033.1200000000001, "end": 2040.08, "text": " you have in your head let me just briefly go ahead and explain it again okay now that we have all"}, {"start": 2040.08, "end": 2046.3999999999999, "text": " the information explained let me just kind of give you a holistic overview of the whole pipeline"}, {"start": 2046.3999999999999, "end": 2053.2799999999997, "text": " so here we have the information from the previous batches of these edge interactions okay and that"}, {"start": 2053.2799999999997, "end": 2063.84, "text": " means we have so rm1 is basically si contains si sj contains the delta t so the time that elapsed"}, {"start": 2063.84, "end": 2070.2400000000002, "text": " between the previous interaction and this interaction and we have ej which is the note the interaction"}, {"start": 2070.2400000000002, "end": 2079.28, "text": " features and we have the same tuples for all of the others the thing is we only focus on the"}, {"start": 2079.28, "end": 2085.04, "text": " nodes that we need so this thing may be huge and contain information for for many other notes in"}, {"start": 2085.04, "end": 2090.6400000000003, "text": " our graph we only care about nodes one two and three and that's why we only calculate those"}, {"start": 2090.64, "end": 2096.7999999999997, "text": " messages so we have we we just basically do a concatenation that's what they did and you get m1"}, {"start": 2096.7999999999997, "end": 2104.08, "text": " you do a concatenation you get m2 etc at different timestamps okay now the aggregation they used"}, {"start": 2104.08, "end": 2110.48, "text": " either the mean or the last message so basically you just take let's say we we use the last message"}, {"start": 2110.48, "end": 2115.7599999999998, "text": " we just pass this message into the next step and that's the aggregated messages array once we have"}, {"start": 2115.76, "end": 2122.96, "text": " those we just have grew here and for every one of those we pass the state we have feed in the message"}, {"start": 2122.96, "end": 2128.0, "text": " we we spit out the new state when we update the states so now we have the states and the the"}, {"start": 2128.0, "end": 2135.1200000000003, "text": " computer this part is included into the computational graph now we use those states and we use get to"}, {"start": 2135.1200000000003, "end": 2141.0400000000004, "text": " create the embeddings now interesting thing here to note is so we have nodes one two and three"}, {"start": 2141.04, "end": 2150.64, "text": " but because this node one maybe has some other neighbors it will make sense it will make sense"}, {"start": 2150.64, "end": 2156.64, "text": " to have other states here as well so whatever the neighbors are i'll call them sn so those are these"}, {"start": 2156.64, "end": 2163.6, "text": " these guys here it will be useful to have the states for them updated as well because those"}, {"start": 2163.6, "end": 2169.68, "text": " will be included by a get because get accumulates the neighborhood information right so those will"}, {"start": 2169.68, "end": 2175.2799999999997, "text": " be accumulated by the get so i guess they just missed to to place sn here like the neighbors"}, {"start": 2175.9199999999996, "end": 2181.68, "text": " but whatever and finally you calculate the embeddings and now you just depending on the"}, {"start": 2181.68, "end": 2187.04, "text": " ground truth so these exist but the negative the negative ones don't exist so you just use binary"}, {"start": 2187.04, "end": 2192.72, "text": " cross entropy loss to train this whole pipeline end to end and now you have a system that can"}, {"start": 2192.72, "end": 2198.48, "text": " successfully predict uh given two nodes given two yeah given two nodes you can calculate their"}, {"start": 2198.48, "end": 2203.6, "text": " embeddings and you can predict whether they are likely to interact in the future and that's useful"}, {"start": 2203.6, "end": 2209.68, "text": " for twitter because you can use that to recommend for node a which node should that node follow in"}, {"start": 2209.68, "end": 2216.72, "text": " the future like maybe andre ang or which which tweets should that user see etc couple of strange"}, {"start": 2216.72, "end": 2222.16, "text": " things i've noticed in the paper maybe maybe a typo or something basically if you take a look"}, {"start": 2222.16, "end": 2228.3999999999996, "text": " at the query it doesn't have the edge information here so that means if you're doing a scale dot"}, {"start": 2229.2799999999997, "end": 2237.2799999999997, "text": " product between the the query and the keys you have a like a differently dimension vectors so"}, {"start": 2237.2799999999997, "end": 2242.7999999999997, "text": " you can do it so it's either a typo or they have some additional projection layer here"}, {"start": 2242.7999999999997, "end": 2248.56, "text": " that they didn't explicitly include here or i've missed something the second thing is i"}, {"start": 2248.56, "end": 2254.08, "text": " mentioned the memory staleness problem but basically if it's like they are implicitly stating"}, {"start": 2254.08, "end": 2259.68, "text": " that you need to retweet somebody else in order for your memory state to get updated but what if"}, {"start": 2259.68, "end": 2266.48, "text": " somebody retweets my post so i assume because that interaction involves my node and that person's"}, {"start": 2266.48, "end": 2272.96, "text": " node so because the way how the messages are computed my node state should be updated as well"}, {"start": 2272.96, "end": 2279.28, "text": " so i'm not sure um uh whether they're just simplifying it here in the paper but anyways"}, {"start": 2279.28, "end": 2285.92, "text": " uh just just keep that in mind that uh that's not super clear because for me it looks like that my"}, {"start": 2285.92, "end": 2290.88, "text": " state should be updated even though i'm not active on twitter because other people are interacting"}, {"start": 2290.88, "end": 2295.92, "text": " with me and thus my memory state is being updated constantly they're probably using a directed edge"}, {"start": 2295.92, "end": 2300.56, "text": " assumption here but it's not super clear from the paper uh one more thing to keep in mind is that"}, {"start": 2300.56, "end": 2308.88, "text": " this memory uh table is not uh let me open a pen is not trainable so what is trainable is the"}, {"start": 2308.88, "end": 2315.44, "text": " group here the lstm and potentially the message and aggregation functions even though they"}, {"start": 2315.44, "end": 2321.2799999999997, "text": " just use the concatenation so there's no learner learnable parameters here neither there is"}, {"start": 2321.2799999999997, "end": 2326.32, "text": " learnable parameters in their aggregation function so they're left up with learning mem so that means"}, {"start": 2326.32, "end": 2331.92, "text": " once the the model is fully trained uh you're basically once an interaction happens you just"}, {"start": 2331.92, "end": 2338.1600000000003, "text": " calculate the messages and you basically uh aggregate them and you update the states"}, {"start": 2338.7200000000003, "end": 2344.32, "text": " and um that's it and once you once you want to predict do some recommendation then you use the"}, {"start": 2344.96, "end": 2351.04, "text": " the get module and create those embeddings and just make the recommendation so that was all i"}, {"start": 2351.04, "end": 2356.96, "text": " had to say for this video you know the drill subscribe hit the bell icon and until next time"}, {"start": 2356.96, "end": 2381.76, "text": " keep learning deep you"}]