Friendly Introduction to Temporal Graph Neural Networks (and some Traffic Forecasting)

Key Takeaways

hey there in this video we will have a look at temporal graph neural networks these are simply dnns that can handle graphs that change over time temporal graphs occur very naturally in many areas such as social networks or traffic systems gnns per se can only handle the spatial information of graphs but are not able to cope with this additional temporal dimension that's what temporal dnns were designed for sometimes they are also called spatiotemporal or spatial temporal gnns i try to explain the architecture of some of these models and will also provide you with a google collab notebook with an implementation for traffic forecasting in the next video the paper sources can be found in the video description so i hope you enjoy the following overview and you can always leave a comment if you have further questions first of all there are different ways how graphs can change over time which can be roughly divided into two categories the first one are simply static graphs that have temporal signals and signals simply means the information that is received at each time step t here we could for instance receive a sequence of different node feature information which is highlighted by different colors an example for this category are road networks with sensors that measure different traffic flows every 10 minutes or so the second category are dynamic graphs with temporal signals these graphs do not only provide different node or edge information for each step but might also change the topological structure over time a classical example is a social network with the user sign in and create new connections to other users and so on this category can also be seen as a superset of the other one as every static graph can be modeled as a dynamic graph that simply doesn't change generally for both of these cases we have a specific timestamp attached to each of the graphs for the graphs on the left this time stamp is only relevant for the note and edge features as this is the only part that can change so those are indexed with t for the graphs on the right we additionally have a timestamp for the topological information such as the set of nodes or the adjacency matrix so all elements that define the graph depend on t here there are many interesting applications of temporal dnns so first i wanted to give you a quick insight to some of the current use cases as already mentioned they are used in traffic systems for predicting the traffic flow or speed based on information captured by different sensors this makes sense because the predictions do not only depend on where the traffic is located but also how it evolves over time another interesting area is motivated by the recent covet situation and aims to predict the spread of a disease within a country which has both spatial and also temporal aspects temporal gnns can also be utilized in the field of motion detection as a motion can also be represented as a sequence of graphs the paper mstgn uses a spatio-temporal dnn to predict motions like walking eating or smoking for example finally applications in electrical or sensor networks can be found in the literature for example to forecast the solar power in switzerland now it's time to have a look at how these temporal gnns are implemented for this i've set up a simple example that should help to understand everything let me introduce you to this road network on which we will perform traffic speed forecasting in the next minutes we also have some traffic signs as well as traffic lights and we of course have some traffic typically these traffic systems have sensors such as loop detectors that can measure things like traffic speed or volume those are spread all over the place and can be used to model this whole system as a graph the nodes in this graph are simply the sensors like illustrated here there are different strategies to connect them here we will just build edges according to how the sensors follow the road so most of the time the sensors are simply connected to the next sensor in their lane and in case of intersections there are several edges between the nodes also note that we use directed edges here to incorporate the direction of travel an alternative way to model traffic networks is to use the streets or segments of streets as nodes and whenever two streets are connected there will also be an edge in the graph at this point we can also remove all of the other things as we have a full graph representation of the traffic system at the moment we only have notes and edges but of course there are also note and edge features the sensors measure the speed and traffic volume for this specific node we have a speed of 50 in whatever unit and maybe 120 cars per minute for another note we have node features 10 and 55. these are the signals for our graph in addition to the node features we can also include properties on the edges for instance by calculating the proximity between two sensors those two are two thousand meters away from each other for the ones on the bottom it's only 900 meters the information however is static in our example because it will not change over time that's why we will ignore the edge features in the following now that we have everything prepared let's simplify this drawing a bit this is our initial graph at time step t more specifically it's a static graph with temporal signals those signals are the different sensor measurements on the nodes in our example the only time variant information are there for the node features i colored them in different shades of blue to indicate that each sensor measures different information by the way later i will also quickly talk about dynamic graphs so graphs that also change their set of nodes or edges but let's start with the static variant first the note features of this first node are called x indexed with n1 at timestamp t they give us information about the current traffic situation at this specific sensor in for example 5 minute intervals we now receive new information for each of the nodes and node 1 has now new features called x and 1 at timestamp t plus 1. here we for example measure a larger volume of cars and a reduced speed another five minutes later there are even more cars and a lower speed here we find information in two dimensions one is the spatial dimension so the graph structure that describes which entities are related the second one is the temporal dimension that tells us how the entities evolved over time and here it's simply a sequence of sensor measurements let's first inspect those dimensions individually to handle the spatial dimension with machine learning we already know gnns that are able to produce great representations of the context of a specific node for the temporal dimension which is nothing else but a time series problem there exists traditional forecasting models like arima but also deep learning models such as lstms or gated recurrent units what happens if you combine models of those two dimensions yes exactly a temporal graph neural network results a spatial temporal deep learning model is the combination of graph representation learning and time series forecasting there are many variants of these models out there but all of them share the same idea to make it short you can treat a temporal gnn as a two-step process first you calculate the spatial embeddings by sending the graph at each time stamp t through a regular gnn this can consist of any gnn layer such as graph convolution or graph attention the embeddings of consecutive layers could for instance be expressed by this formula the adjacency matrix is multiplied with the previous embeddings and the learnable transformation as applied finally relu serves as non-linear activation this gives us spatial features that describe the context of each note i try to make the colors of the note features go from dark to bright to indicate that each note has gathered information about all other notes in order to include the temporal information we need a model that is able to store information over time you can think of it as a sort of memory typical deep learning choices are long short term memory or a gated recurrent unit these models have a learnable gating mechanism that allows them to store and drop information from a sequence of signals we can now send the spatial features per nodes that we calculated in a step before through one of these models for time step t we have no historical information so far so the embeddings basically stay the same at t plus one however the temporal model updates the spatial features per node with the historical features as a result some of the embeddings additionally hold some properties of the previous time step which is highlighted in blue here in time step t plus 2 the temporal model again takes the spatial embeddings created by the gnn and updates them with the information of the previous time step these final embeddings now successfully combine both the spatial and the temporal information in one representation per node we can use these embeddings now to perform all sorts of predictions the great thing about this overall architecture is that it is fully differentiable which means all learnable components can be optimized in an end-to-end fashion when we use a gated recurrent unit as a temporal model the update formulas look more or less like the following ones there are two gates an update gate u and a reset gate r those take the inputs of the g n so the spatial features as well as the historical hidden states and apply some learnable transformations using these two gates it's possible to create a new hidden state ht which is the combination of the previous one as well as a candidate hidden state i won't go further into detail around these formulas here as there are many good resources out there on how these skating mechanisms work one final remark it is of course also possible to include the temporal features into the spatial aggregation so basically to perform message passing on spatiotemporal features this is something that is also done in some of the papers talking about papers let's have a look at some variants this is an excerpt from the paper for the library pytorch geometric temporal which we will also use for the traffic prediction data set in the next video as you can see there are many different types of temporal gnn blocks and they mainly differ regarding the layers used for temporal and spatial aggregation tgcn for instance uses graph convolutional layers and incorporates the temporal dependence using a gated recurrent unit at each time step the graph is fed through both of these modules and the gru additionally incorporates the information of the previous time step just for clarification this gcn block consists of several gcn layers for example aids this determines how broad the local graph filters on the gnn are of course it's also possible to stack several layers in the gru block this will allow the model to learn more complex temporal features another very interesting work is called graph multi-attention network it deploys the attention mechanism both in the spatial and temporal dimension the special attention simply attends to all of the neighboring nodes in the context of traffic systems this allows the model to pay more attention to specific roads or sensors in the network the temporal attention additionally attends to all of the previous time steps with this the model can pay more attention to specific historical events the previous papers were great examples of temporal dnns applied on static graphs until now we did not talk about dynamic graphs however what do you do if the topological structure of the graph changes this means edges and nodes can be added or removed from the graph and the node and edge features might change as well the paper temporal graph networks which was published last year provides a framework to handle the situation in a sense it's not much different than the previous ones we also have a message passing neural network so basically a gnn that collects the spatial information for a specific time step just like before there's also a memory module to learn temporal features in the paper they experiment with a gated recurrent unit the main difference to other papers is the following the neighborhood from which the gnn aggregates the information can be dynamic so there can be different neighborhoods depending on the time step also the memory module is only updated for the nodes where changes happened this means if a new node was added or connections to a node change the new embeddings are used to update the hidden state in the paper they also experiment with several message functions and also apply attention so check it out if you're interested in further details so that's all for this little introduction to temporal gns let me know if you found it helpful in the next video i will build a simple traffic prediction model using pytorch geometric temporal i will also quickly talk about the library and how to use it so see you soon in the next part