Tutorial: Parallel and Distributed Graph Neural Networks: An In-Depth Concurrency Analysis

good morning good afternoon good evening wherever you are on the planet my name is Torsten heffler I'm a professor at eth Zurich and together with a machiavesta I have the honor to present this tutorial at the very first learning on graphs conference a quickly emerging field today so the tutorial is going to focus on Parallel and distributed graph neural networks that is the foundation of much of what we're what this conference is about learning on graphs is very much a deep learning on graphs with graph neural networks and we're going to present an in-depth concurrency analysis really all the performance aspects and the aspects you may need to implement systems from the small scale to the extremely large scale supercomputer sized systems for the processing of graph neural networks our tutorial bases on the paper that you can see in the background with the same name that paper is on archive it has about 27 pages and you can refer to the paper for the greatest details that we may not be able to cover in this relatively short 90-minute tutorial here but again we try to give you the overview here the essence of the paper and then if you want to really dive in all the equations in the detailed systems aspects please refer to the text and it'll also be on most of the pages at the bottom so now to just introduce in general as we all know we wouldn't probably be here that graphs are extremely powerful and ubiquitous just to motivate you social science we all know social networking basis on social graphs engineering much of it basis on large-scale graphs biology brain scale graphs extremely large scale chemistry looking at bondings looking at newer materials communication our communication networks can be modeled as graphs medicine much of the the effects of medications on the human body can be modeled as graphs for the more cyber security web graph analysis and even philosophy are basing on very large scale sometimes very large scale graph problems so actually these very large scale graphs are of tremendous size so we have done an experiment or a performed a very large scale calculation on the largest supercomputer at the on the planet at the time in 2018 so we processed 70 trillion edges on 10 million cores together with our Chinese Partners at qingwa University um here there was a 12 trillion Edge real world internet graph that we could process in 8.5 seconds per iteration this is quite challenging this was in fact a finalist for the Gordon Bell award that is yearly given to the highest performing supercomputer application in the high performance Computing field um and this may still be the largest documented uh graph run a single graph run on the largest machine today so now the question is how do we go from here to processing these large graphs well as I mentioned graphs are extremely large so what are the computational properties they're extremely irregular this is much harder than today's computations their communication heavy and synchronization heavy if you go parallel furthermore they're extremely power hungry and can be quite time consuming in Practical processing so now we have processing of very large sparse data structures graphs and the Deep learning which traditionally has been quite dense so if you put these two together we get graph neural networks essentially and learning on graphs has been a very trendy um a very trendy field the last couple of years as we know so this is something that we should get into and understand how to do processing because as Joffrey mentioned in his 2018 uh in his part of the 2018 touring lecture really the deciding factor of the AI or deep learning Revolution was the increase in compute power furthermore he believes that a lot of credit for the Deep learning development goes to people that did develop the data sets but also the people who made the computers go fast so this is not incredibly important how do we make computers go fast for graph computations graph neural network computations graph deep learning so how do we make these computers go fast well we can ask last year's touring Award winner Jack dungara who who spent his career on making computers go fast for dense computations for high performance Computing extremely large scale so he and partners achieved that massively parallel systems are now more than 70 efficient at full scale at the largest machines on the planet millions of cars running density algebra and as you know most of the deep learning is in fact dense linear algebra processing models like gpt3 is a lot made of matrix multiplication however the same system deliver only 0.1 percent sorry 0.8 efficiency for sparse problems so to quote Jack think about having a race car that goes 200 miles per hours and you get only two miles per hours out of it but unfortunately that's most likely not going to make you very happy so there's still a lot left at the plenty of room at the top as we can see here and the top is the software environment how do we use these computer systems most efficiently in order to actually Implement graph neural networks in a way that they're cheap and scalable to extremely large scales so with this in mind we we wrote this paper that I mentioned that we need to understand parallel processing of graph neural networks because gnns fundamentally combine dense computations like standard deep learning with sparse computations like graph processing and this is a very challenging point to make a very challenging problem to solve furthermore there are lots of different options ranging from extremely fine scale parallelism to very core scale cluster level supercomputer level parallelism and in this tutorial we will be covering all of these options but before let me give you a little bit of a rough background of deep learning in a nutshell I'm pretty sure that most of you probably know it I just want to put us all in the same stage that we can follow the talk equally well so we have a set of input examples that we call samples here we have a network structure a deep neural network structure and then we take one of those input examples like this cute cat here run it through the Deep neural network which now implements a learnable function f of x x is the input sample and then we learn the model I mean this function is is essentially the model then we have some kind of prediction of the model and we look at the ground truth in this case it's a cat and then we do a layer wise weight update iteratively until the model converges to a good prediction to the cat there are now different ways to train to to feed these samples to the model we could first before we do a weight update run all of the samples to the model which is called a full batch method unfortunately it's extremely expensive because typically we have a lot of samples but we get a pretty good estimation of the gradient here and we get a pretty good convergence but extremely slow computation of course this depends on the quality of your data as you know and typically what people do is they take a part of the mini batch or a part of the batch which is then called a mini batch then that uses a less accurate weight update it's only a statistical sample so we take random samples but has much faster computation and at the end converges much faster um in more steps typically but much faster in compute time to a good solution so we'll be focusing mostly on Mini batch but we'll we'll see in the in the remaining talk um then if you look at parallelism in traditional deep learning what does that mean well we have the model itself and the model can typically be expressed as various layers and you see a very complex set of layers here here at the bottom we have a simpler set of layers we have a very simple convolutional input layers then two layers that are now have filters and then the output layer which is a simple classification layer in this particular case so we can Define parallelism on the data or we can Define parallelism on the model the data is usually relatively simple you cut multiple examples and run them separately through copies of the model the model is more complex because it has more options to be processed so now let me talk a little bit more in detail in this parallelism in deep learning traditional deep learning so we are still not at graph neural networks that's going to be more complex but in traditional deep learning what we could do with data parallelism We have basically full copies of the model here blue yellow and green and these full copies they get a part of the mini batch each mini batch so we run it in parallel and then we sum this all together at the end here for model parallelism which is an orthogonal way to paralyze so we can combine these ways of parallelism and actually typically for very large models this is the case we could cut each of those layers that we are seeing in multiple pieces and process them on different devices so we could now take the data parallelism and on top of it model parallelism and process each layer on different devices which is typically very communication heavy so that's typically the last form of parallelism that you want but it speeds up your model if you simply want to get a higher throughput or you want to get you want to fit larger models in your limited size accelerators you could go with pipeline parallelism where you take each of those layers the blue the um they're yellow and the Green Layer here and put them on separate devices and now you could of course imagine that you can combine all of these three forms data parallelism model parallels and pipeline parallelism into a single parallel system a parallel computation system that now works on all these three dimensions okay so this is standard deep learning or let's say traditional deep learning which is typically dense computation today and there's of course sparse computation in these models as well but most of the models today are processed learned densely um but now if you look at graph neural networks how does this model change how does this view change well again we have a very similar picture here we have the input samples but now these input samples they could still be photos but they are related by explicit relations so now a photo would not just be a part of a set but it would actually be a vertex in a graph and it would be connected to all the other vertices based on some certain specific property for example if the photos are taken in the same place or at a similar time they could be connected by edges right so now each of these little pictures is a vertex then we typically run each of these pictures also through a deep neural network but these deep neural networks are very often simpler than the networks we have today and other tutorials talk about how to increase the complexity how to grow the complexity from a data science perspective we are going to talk about it from a computational perspective here so keep in mind there are typically much smaller on graphene owner for various reasons that we don't cover here um so now what we do is we take an input sample which is now not independent or which may not be independent you can see here that has connections to other input samples we gather the information from the neighbors and that is now a big difference to a traditional deep neural networks because there are no neighbors we apply some graph neural nut or some deep neural network which is often quite simple to the information that we gathered from The Neighbors and then we have an optional non-linearity in our system and then we move on to the next layer the next layer quite often means just to rewind to the beginning and repeat the operation over and over again this is why layer is in quotes So the definition of layer in our context is twofold we first have a graph neural network layer where we repeat the operation and get a larger reach because every single time you collect your neighbors and see more and more and more of the graph but there's also another definition of layer like in this little deep neural network they're of course also multiple layers so there are lots of degrees of freedom how to construct these graph neural networks and then once we processed all the layers we have an output Vector which we can then use in a simple classification Network for example for learning specific tasks okay so basically um summarizing this here we have these different forms of parallelism data parallelism model parallelism and pipeline parallelism we also have these different forms of parallelism in graph neural networks but here it's a bit more complicated because specifically we have different forms of parallelism in the ability different forms of graph parallelism I mean data parallelism on the graph so there could first be graph parallelism which we could also call partition parallelism and then this is the left side where we have one large graph remember the 17 trillion vertex graph that we are learning a model on so this model could either learn specific features of vertices or it could learn a specific feature of the overall graph but we also have mini batch style parallelism whatever you would then look at subsets of graphs where we could have multiple graphs in fact and we could look at dependent mini batch parallelism or independent mini batch parallelism so dependent mini batch parallelism means we have um we have graphs that are relatively large that we need to cut enter the single vertices still go into different models but in the um in the um in the independent mini batch parallelism what we can what we usually do is we run graphs independently at pretty small graphs independently through the model which is very similar to traditional deep learning now in the model parallels inside we have a very similar set of options so we have deep neural network parallelism where the Network that sits on top of each Vertex or Edge much it will go into the on that in great detail will actually be separately processed or can can be distributed um we have operator parallelism which is very much the same as the operator parallelism that we are seeing on on the left side which here on the slide is called Model parallelism but we should really be called operator parallelism and then we have pipeline parallelism which is um the same as essentially the Deep neural network we had before the traditional deep neural networks but the pipeline parallelism itself is actually has has now two options there's the pipelining on the graph neural network layers which is this iteration that I mentioned before but there's also pipelining within a single deep neural network that sits on top of each of these vertices or edges so um with that I would like to give the word to vachi after giving you the motivation and the overview of this tutorial and he will go into great detail on the computational aspects of all of these graph neural networks and also the parallelism aspects that I've just summarized here to give you a rough roadmap of the talk and he will explain all the details thank you very much and hopefully see you in real life at some point okay wonderful so so yeah thanks to Austin a lot for for the very nice very nice first part let's not proceed with all the auditors so in the second part of the tutorial uh we'll first take a very brief recap at some of the important aspects of gnm that will need um in the Far Far parts then we will take a look at at all the model all the all the foundational par aspects of parallelism so we'll take a look at data parallels in gnns model parallelism in gnns including pipeline parallelism and we will then at the very end uh analyze a lot of different models trying to understand which which ones are coming with more parallelism at the fundamental level uh and we'll try to have a more broad Outlook and what are the insights coming from how to execute these different models efficiently in many parts we are trying we are going to have um to focus on getting the insights into on one hand what are the what are the differences between parallelism and traditional deep learning versus uh parallelism and graph neural networks um and also in as I mentioned how much parallelism is there in different parts of the gnl landscape so let's start with the recap of some important parts about gnns so at the very beginning of a of a whole genome computation pipeline we provide input which consists of the graph of the graph structure and also with our coming with our input feature vectors for vertices and also possibly for edges right then we are on our input through a GNN model which might include training and or inference and we finalize with taking the output and running them through our Downstream machine learning tasks such as classification or regression of edges nodes or the whole graphs and we are going to use in the tutorial we are going to quickly use the following symbol this is so this symbol indicates this picture sorry this picture indicates a single sample and that example is a vertex with some dependencies coming to other going to other samples and together with our feature Vector for this given sample let's now let's take a look at different types of these samples that we have in gnns together with their corresponding Downstream machine learning tasks so the First Fundamental type are are vertices that are samples vertices that are dependent right so we can see this explicit dependencies between these vertex samples and this setting we he will use in gnn's for example the model atoms with example classification task being to predict the atom element or for example predict the atom charge as an example regression task the next class of samples is our edges right so the edges are also dependent the other neighboring vertices and these edges can also become the first class citizens in our GNN Pipeline with an example being an atomic bond for which we would like to for example uh run the classification task to predict the bond type or render regression task to predict the bond balance right then we have the third class of samples which are independent graphs so this is a sort of a bit special type of samples in which a single sample is not really having any dependencies to other samples but it may have some infra sample edges right so an example the obvious situation here is is to have a chemical chemical molecule being modeled by such a small graph and an example classification or regression task being to predict some aspect of this molecule for example a class or a solubility etc etc and finally we may also have dependent graphs right so we can think easily of scenarios where these small graphs also have dependencies between themselves for example a network of interacting proteins in which this network is a graph itself and a single protein can also be modeled as a graph right so um why I'm mentioning all of these all of these kinds of samples well because the amount of parallelism and how we can run different genome pipelines efficiently will heavily depend on what type of sample we we are processing right so now if we picture all of the examples all of these classes of samples together then we compare it now to the traditional deep learning the samples The crucial difference here is the fact that we do have explicit dependencies between samples in gnns and even in a even in a setting where we have independent graphs even in this setting these these single samples these individual samples have infra sample dependencies that we have that we also have to consider in some way right and this as we are going to take a look and see in a couple of next slides this dependencies make parallelism in gnms really much more complicated than what we have in traditional deep learning okay so that's uh that's uh that was the the necessary recap now let's move to the first part of the presentation what we are going to focus on on the from the instrumental aspects of data parallelism in graph neural networks so data parallelism can be split into two subtypes on one hand we have stores and mentioned graph partition parallelism on the other hand we have mini batch parallelism that you can follow categorize into independent and dependent mini batch parallelism right so this means that in this high level GNN pipeline overview we are now going to speak about parallelizing this pipeline focusing on that part on the left which is now not not blurb right so this this across the sample dimension so let's start with graph partition parallelism right in this setting we are going to focus on on samples which are single vertices right so our setting is the common one where we have the large single graph that we want to process and run some predictions for with one vertex being a sample and now we would like to we can split this graph across different parallel workers right so in the all of the following slides the color code is the different colors are corresponding to different parallel workers right so the main goal for for using this graph partition parallel is really because we would like to fit the graph somehow in our memory and the graph is usually too large to be able to to fit a single single worker's memory right so that's why we split it across different workers processing this in parallel for example across different memories maybe across different disks and the important thing is that every vertex and every Edge and that in that scheme would fall into some partition right so you want to process the whole graph which means that every part of it will sit somewhere in some worker's memory now independent um dependent mini but parallelism the situation is the situation is slightly different so we again consider the same setting with one vertex being one sample but now the reason for for applying this parallelism is and this whole scheme is really to speed up convergence right so we use mini batching to have faster convergence and now one important thing is um is that a single sample may fall into more than one minibatch right so that's one of the differences between minibatch parallelism and and graph partition parallelism is that these vertices may be processed in more than a single single such mini batch partition the other difference is that not all the samples May necessarily belong to some minibatch right so this all depends on what what sampling scheme will use and we can easily imagine a scheme where some of these vertices will not be included and even a single mini batch and then we have something similar in the independent mini batch case right so in that case we deal with independent independent samples for example independent graphs so one sample is now one of these graphs and the reason for using this scheme is the same as in the dependent mean about parallelism namely we we do this partitioning and this mini batch into speed up convergence we have similar figures that on one hand some samples may fall into more than one mini batch while not all the samples will necessarily belong to to even one of the mini budgets right and now if we now compare these two forms of data parallels and we'll see the following differences so um The crucial difference between these two is the timing of updates to model weight namely we use partition graph partition parallelism usually together with fullback training because we process the whole graph that we can't fit into a single memory which means that in that scheme we apply the the updates to model weights after pressing the whole batch while in the minibatch parallelism we update the weights after we finish processing a given mini batch right so that's one crucial difference in the design of the whole GNN pipeline for for data parallelism the second crucial difference is the reason for being Incorporated and so we we incorporate graph partition parallelism to be able to fit the graph somehow in our combined memories and we apply mini batch parallelism to speed up convergence and then the third crucial difference is the way that we do the partitioning and especially the primary objective when partitioning so in graph partition parallelism we really focus on reducing the communication among the between the workers right because we this will improve our performance and many batch parallelism the the way we partition is really related to how how quickly we want to converge and to trying to make the statistical something as efficient as possible for that objective and then the final difference are the inter-sample dependencies that may heavily impact the design the system design of the genome pipeline for these two types of parallelism namely in graph partition parallelism There is almost always some dependency and there is only no dependency if our graph is disconnected between the samples right but for mini batch parallelism in the independent setting there will be no dependencies between the samples which would for example enable us to simplify a given part of the gnm pipeline for a given for a given independent mini batch setting so that is that was the high level overview of um of different forms of data parallelism and graph neural networks now let's move to model parallelism model parallelism is more complicated and more interesting uh in my view than data parallelism it splits into three parts we have a thing called operator parallelism pipeline parallelism and the DNM parallelism where DNN stands for deep neural network the traditional deep neural network setting right so again we take a look at this high level overview of a gnm pipeline so here we are going to think about parallelizing this whole part which is on the right side now right so the graph convolutional stage the the neural network digner network stage and the non-linearity stage and let's start with operator parallelism which is something we apply to the graph convolutional stage here we can again see our single vertex sample and in the first class of operator parallelism methods we have a class called feature parallelism in which we parallelize the processing of a single feature Vector right so it's a predefined grained way of parallelizing adrenal computation um we do it by assigning different different features to different workers then there is the other the other subtype um of this class of parallelization schemes namely the graph structure parallelism and this is even more fine-grained because we are now paralyzing the processing of a single individual feature right so we can see here that in this vector in this feature Vector each single feature is having is being it's been colored with these three different colors which will indicates that each of the workers is now processing this this feature in parallel conducting for example some aggregation so this is operator parallelism a very fine-grained way of paralyzing genome computations the next that we are going to discuss is DNN parallelism which is really about parallelizing the second part of this pipeline of the of the single gnm pipeline namely the the dense layer so here we also have two classes we have on one hand DNN pipeline parallelism in the in which so in this part as a star since Thursday mentioned we have we have the the MLP which we are using to process the feature vectors um of our vertices or for example of our edges and now we can see this this uh the MLP as basically the the place that we could apply an arbitrary way of paralyzing a traditional deep neural network pipeline right and this is exactly what we are doing here what we can do here we can apply DNN pipeline parallelism we should assign different workers to different stages of this small MLP which sits within a single GNN layer or we could also apply a more General DNA model parallelism in which we split this and the processing of this part more arbitrarily across different workers resembling um essentially imitating the the parallelization we would apply to a traditional deep neural network setting right so this is another very fine-grained way of parallelizing the processing of graph neural networks and then we have the third class of model parallelism schemes which is which is called pipeline parallelism it also has two subclasses micro and macro pipeline parallelism so let's start with the smaller with the more fine-grained one with the micro pipeline parallelism so here uh we apply we assign different workers to different stages within a single GNN layer right so so in this example one worker would be assigned to process the graph convolutionary convolutional layer one would be assigned to process the whole MLP dense neural network part and the final process would could for example be assigned to process the non-linearity final stage of this GNN layer execution it's also a reasonably fine-grained polarization routine but we can also now apply a more coarse grain parallel approach which is called macro pipeline parallelism because now you could think of assigning different workers to different genome layers right so here we can see that a given execution of a GNN has three GNN layers and one worker is responsible for the whole first layer the other is responsible for the whole second layer and the third worker is responsible for processing the whole third layer right so this is this is a pipeline execution of a GNN computation across different GNN layers and now there is one additional very interesting difference in the context of this micro pipeline parallelism between the traditional deep learning and graph graph neural networks basically in in traditional deep learning and we can also have pipeline parallelism where we assign different workers two different layers but the the thing is that in traditional deep newer networks we start with some data that we feed in through the first layer and after we do it we'll never really see the same data again right so we are then grabbing the outcomes of this first layer and proceeding to the next layer with some sort of transformed modified data and we continue like this right and this is in some way similar with gnns because we do the same with our input feature vectors we feed them at the very beginning and then we'll not only see them in the same shape again because we are going to constantly transform them across our GNN layers but at the same time when GN ends we also need to access the graph structure in our convolutional layers in the convolutional stages right which means that actually in gnns we do have to access the input data because the graph structure is a part of our input data at different stages not only at the very beginning which now implies that we need to consider this uh this this aspect in the design of our for example software Frameworks or Hardware accelerators because we have to we have to have this efficient access to this initial graph structure at uh almost every stage of our GNN pipeline right so um now let's um that we can take a look at um at the difference between traditional deep learning and gnms in the context of in the context of parallelism so on one hand parallelism gnns is clearly more complicated than in traditional deep learning right and it's all because we have these dependencies between the samples in ngns right so um on the other hand the second difference the kind of high level difference is that we have new forms of parallelism in GNN in the Gene and Landscape again because we have these dependencies so for example we have a dependent mini batch parallelism we have graph partition parallelism we have graph structural parallelism so these are the things that we don't really have in that shape in traditional deep learning landscape so this means we have also potential for more interesting research and opportunities to to provide more efficient pipelines considering more of these ways of parallelizing graphing neural networks okay so this was the overview of different forms of modern pipeline parallelism now let's um let's uh let's now take a look at how we can apply these different ways of parallelizing gnns in order to formally understand what parts of the genome landscape are more are coming with more or less parallelism but for this we need to First Take a look at some uh some way to formalize our genome processing so for this we are going to focus on two ways in which we can formally describe a GNN model so as we know on one hand we can describe a GNN model using the so-called local formulation where we formulate The genome model using functions that operate on single vertices and single edges so this is our well this is the well-known mathematical expression for the message passing graph neural network generic formulation in which we use the h symbol to denote vertex feature vectors I is our vertex ID and I are the neighboring vertices of the vertex so I then we have the L which indicates that GNN layer GNN layer index and then finally what we have are these these three functions PSI aggregation and and Phi and these functions specify the details of the model right so we we provide once we provide the specific expressions for these functions we have a concrete General model that we can use to run our our predictions but we also have another way to describe graph neural networks uh graph neural network models specifically the so-called Global formulation so in these formulations we construct a model using operations on matrices that group all the vertex and Edge related vectors right so this is so there's this is an example generic formulation for for this global view of graph neural network models again we have L which indicates our our layer GNN layer index um then we have the age Matrix which we use to group all the feature uh all the future vectors of vertices and then we have also the adjutancy Matrix which we use to describe the structure of our graph and finally we have also model parameters grouped in some instant parameter Matrix right and then what we also have are certain functions that we need to specify to provide the model details right so we can apply some transformation to The adjacency Matrix and then we can optionally provide an element device product with some more complex expression hidden here within these these two brackets that could make the model for example maybe more powerful so we'll see many examples of such models in the in the next couple of slides now just one important notion is that these formulations are not really fully equivalent which means so what I mean here is that some gnl models only have non-local formulation and vice versa we also have models that we only describe using the global formulation and not really the local one right and now we are going to use I'm going to use this um this formulations this this local and and Global um equations these equations for local and Global gnl model formulations to formally analyze the amount of parallelism in different GNN models so let's start with local formulations here we have we can see a cheat sheet showing the general equation and also the high level overview of of a single GNN layer all right and now I'm going to use a couple of symbols namely symbols that illustrate vectors and communication of these vectors so this is this is this red color that indicates a vector vector that we are we are communicating somewhere and the green color and the green vectors uh which indicate a vector on which we are doing some local computation indicated with this um with the circular Arrow without any communication right so now let's take a look at GNN single GNN layer in more detail through the perspective of this local gnm model right so as we know we have a couple of phases there one phase is the scatter phase which which is a part of the Phi function in this General sorry of the PSI function this General uh local formulation in this phase uh for we have our example graph here consisting of four vertices and three edges and now each of these vertices has some feature Vector right that we indicate here with this with these um with this red vectors here and in this phase we are now sending these vectors along our neighboring edges uh towards the in order to produce something some new output uh in the next phase right so in this phase in this cutter phase we are we are sending these vectors along the edges right and we can do all the extent in parallel and then the second phase in the update Edge phase we are using this um this this issued vectors in the previous phase to conduct some local computation and to generate new uh Edge feature vectors right and this in this phase we don't really do any communication and we can also apply all these changes in parallel in the third phase the reduce or also called aggregation phase uh we are now governing the outcomes of this previous phase and also we are governing the previous um Edge feature vectors and reducing them across across the edges right so for example for this one vertex here on the right side we only need to grab its adjacent single feature Vector of the of the corresponding Edge but also of its adjacent neighboring vertex right so we only need to reduce two verti uh two feature vectors in this um in this space for this one vertex here but then for the central vertex we need to conduct a reduction over many different uh many different vectors belonging to the adjacent neighbors and belonging to the adjacent edges and then the Final Phase in the update vertex phase which is which is forming the the final function the Phi function we then run some local computations for example nmlp or linear projection on the on the output of the third phase on the on the on the vertex feature vectors that we derived in the previous phase in the previous reduction phase again you can apply um the computation in this we can parallelize the computation in this space uh in full scope so we don't really have to synchronize with anybody else we can run all these changes locally in parallel for every every vertex and now we could think of applying different forms of of model parallelism to these different stages for example we a straightforward uh approach for polarizing paralleling this paralyzing these status in the context of what we what we said before is to is to apply different forms of operator parallelism to stage one and stage three and different forms of DNN parallelism applied to stage two and stage four now let's uh delve a bit into the formal foundations of parallelism in these in this in the gnl models expressed with local formulations right so for this we are going to use a certain theoretical framework known in parallel computation uh called the work depth so in this framework we picture any any computation that we have as an execution directed I think we graph edoc right so this graph here illustrates some arbitrary execution that we may have in our original pipeline so this can be something completely arbitrary what is important is that now the circular arrows indicate a single simple operation for example summation or multiplication of some arguments and then these arrows these straight arrows indicate dependencies of some operations on the previous operations right so we can use this formalism of educ to model essentially any type of execution and now there can be two um two properties of such an educ so one property is called work which counts the total number of such operations that we have in the cdac and the second one is called depth which really indicates the longest chain of sequential dependencies in a given educ ate right so on one hand the goal of when designing an algorithm a parallel algorithm would be to minimize the work right on the left side we can see here now some example amount of work which is quite high and we would like to minimize this amount of work namely the total number of operations in a given educ and the same for depth right so we would like to also minimize depth to remove or to minimize our sequential bottlenecks in a given execution so in this particular example we can see that there is a certain a certain part of this deck which is really long and would become a bottleneck for our computation and in this view we would like to minimize it by for example somehow eliminating this this path the sub-path of this um of this execution and have something which comes with much lower depth right so and the important takeaway from that slide is really that we have these two properties of a given execution but this can be these are also properties of a given for example GNN model um like work and depth so what does work what is depth world will tell us about the total number of operations we need to conduct in a given GNN model execution and that would be the sequential bottleneck so basically what is our bottleneck Beyond which we can't really go we can't really overcome this bottleneck regardless of how many processors we would be throwing at um at a given g and an execution right so I'm going to use the following notation in the following in the subsequent analysis and will indicate number of vertices it's the standard notation we use in our landscape m is number of edges K is number of features Big L is a number of layers in a in a GNN it's a number of GNN layers and D is the maximum degree in a given graph and also we are going to use a couple of different symbols to indicate different mathematical objects so this dot will indicate this color this will indicate a vector and then vector of dimensionality being the number of features we are also going to use quite often the symbol of a small dent Matrix with number of Dimensions being somewhere in the order of the number of features we are also going to use the tall and then Matrix so here the small Dimension is the number of features and the big Dimension is the number of vertices and finally we are also going to use the symbol of a sparse Matrix with the number of Dimensions being the number of vertices right and then the number of non-zeros in this big part Matrix is the number of edges right so this is this is really our our adjacency Matrix or something based on the adjacency Matrix with the same sparsity pattern so let's start with analyzing formally how much parallelism is there in the most in the in the very seminal uh graph convolutional Network model right so first let's disseminate this this gcn model into the fundamental functions that that form the local formulation right so first we have the the Phi um which is really just the multiplication of um of the feature Vector of a given neighbor uh with the normalized uh product uh with the inverse of the root of the square root of the degrees of of the of that vertex and its neighbor right so it's really our our Matrix normalization that we are applying at at the beginning of the gcn model right and now the important thing is the compute pattern of this function execution so in the compute pattern um this operation is really equivalent to multiplying a scalar some scalar number c with a dense Vector that has um the dimensionality of the number of features right but then we also have the two other functions in the local formulation we defy and aggregation the aggregation symbol and we treat them together just for Simplicity and they can be seen as they can be written as as this expression here so we have our our website that we are up here and then we conduct the aggregation over the neighborhood of the of the vertex I and finally we multiply the outcome with the parameter Matrix using a matrix Vector product right so here really the fundamental the fundamental compute pattern is doing some summation of the of the dense feature vectors uh summation that may span up to D different vectors right so we may we may be summing up to the maximum degree number of such such vectors and the outcome is multiplied by a dense Matrix of dimensionality K K times k and now what's the work and depth right so I'm not really going to derive this really step by step but but this model is anyway very simple so you can probably already see that the work for for this uh for this operation here for the PSI operation is really o of K right so the work is really proportional to number of our features and that is really all of one because so this operation is really trivially parallel right we can do this multiplication completely fully in parallel and and this means that that is is very nice it's all of one so we can uh yes so this this operation is not really any bottleneck for our parallel execution now for the second part of this model for the pi and aggregation here I'm going to derive the final work and final depth for the whole training single training iteration so this is uh here we are going to consider all of these executions of of PSI together with the aggregation and the multiplication across L different genome layers right so we can see that the work here is really a a sum of two of two terms in one term we have number of GNN layers L times number of edges in the whole graph times number of the features and the second we have eigen number of gnm layers times number of the vertices in the graph times the square of the number of features right so this is really the work that we have that we need to dedicate it doesn't it doesn't really look horrible but it also doesn't look like something very very very lower right so we have this square number of features which may actually get quite large so we may be actually a bit worried about how much work we need to throw at this model um but then what it turns out that the dev is actually very nice so depth is is really the the sum of the two terms in each term we have linear number of GNN layers L and then we have always the logarithm of something and on one hand we have the logarithm of the maximum degree in the graph on the other hand we have the logarithm of the number of features in our in our vectors all right so this is actually implying that uh depth is is quite low because our only uh the major bottleneck that we can see here is the number of genome layers right this is only the linear this is the only linear term in this equation all the others are logarithmic and also K we know is quite small in most cases which means logarithm would be even smaller right so that means that despite having some reasonably high amount of work the depth is going to be actually quite low and will not only have a major a major sequential bottleneck in the execution perhaps except for the number of GNN layers so that's our main conclusion for the gcn model now let's take a look at something a bit a bit more complicated let's take a look at the graph attention Network model here we have again way of disseminating this model through the local GNN model formulation format right so we have the three functions again the the PSI the Phi and the aggregation function and here it turns out that our first function execution that we need to conduct for every Edge between any vertex I and J is actually quite complicated right this expression actually looks a bit complex this is uh I mean what we are doing really here is uh is is the well-known part of the G80 model so in this model we need to conduct the attention over every neighbor of every vertex and then we need to normalize it with softmax that's really what this equation is about so let me um so enable allow me not to go into details of what this expression actually is doing because that's not only the most important part that already established a G80 model expression what is really important is um is is the compute pattern of this expression right so here we also have the expression for the for the Phi and the aggregation and also the corresponding compute pattern and you can see that the compute pattern for the for the for the PSI function is also quite complicated right so we need to do all these matrix multiplication uh Matrix Vector multiplications uh concatenations dot products and exponentiations on the contrary the aggregation and the Phi are actually quite simple so once we compute all these attention scores for every every vertex for every neighbor and every vertex we just need to plug them in here in this expression and conduct the final aggregation followed by multiplying by the parameter Matrix right so the corresponding compute pattern is also not very complicated but this one here is actually quite complex right so now we analyze work and depth again I'm not going to do this really step by step but this is actually quite simple because all you have to do is to identify the most time consuming is that as it's the big old notation all you have to do is to identify the most time consuming operations and reconsider them as the major culprits of that adapt to the work so it turns out that the work for the single execution of this function here is really Max degree in the graph times the square of the number of features uh so it looks actually pretty pretty large right because now we probably think that we need to conduct this for every every Edge in our graph which would adapt to a very large work finally and this is the case yes but what is important is that actually this execution is at the same time very nicely parallelizable so despite having all these different elements adding up to a lot of work we can run this thing and that being Only log K plus log d which means that's not really going to be a major bottleneck in our computation and then once we wrap together all these executions of the of the site and plug them into the final expression together with the aggregation in the Phi our final work will be as as you probably expected quite high so this is going to be proportional to the number of genome layers as before number of edges as before but then also the max degree and the square of the number of features and then plus L times n times K squared as before right so this is actually a lot but again the depth of the whole computation uh in that case single single training in the right integration is again only linearly dependent on the number of GNN layers right so all the other factors are being logarithmic so again this L is kind of um maybe worrying us but this D and K and the rest of this of these executions of this uh site here are not that uh not that bothering so so here's the final conclusion from that slide is really even for a complex and very work heavy graph attention Network model we also have plenty of parallels that we can apply now what we did was to analyze to conduct such an analysis for many different DNA models not just gcn and G80 so we summarize this analysis in this table here one row of this table is going to correspond to a single GNN model formulated using using the local formulation right so we can see gcn here we can see graph attention here we can also see others we can see Monet we can see vanilla attention comnet and many many others right now we have in our paper we have uniform formulation like we have formulations using uniform notation for these different models to simplify the analysis so these formulations are not not that greatly important for this presentation so let me let me indicate this with um with this white background what is really important is that you can categorize these different GN models into three classes we can categorize them into CG and nth so-called convolutional graph neural networks into agnns so so these are attentional graph neural networks and into mpgnns a message passing graph neural networks right and as you probably know these these classes differ in the output of the of the PSI function right so for the cgnn models this output of the PSI function for these models is a static is a static scholar for the attentional gnns this output is a learned scalar parameter and finally for MPG and ends this output is uh is a vector with an arbitrary vector now what we did was analyze and derive the compute pattern for each of these models right so we again can see this complex compute pattern for the for the graph attention and the compute pattern for gcn but also all the others right and we use this compute pattern to derive the work and depth of single execution of this of this type function here right and then now let's take a look at some of the insights we got in the process so what is quite obvious is that agnns and mpgnns so these two classes here are coming with much more complicated compute patterns than cgns right so this is pretty obvious because CG and ends are essentially just summing so the execution of size essentially just either multiplying the vector bias color or simply taking this input Vector as it is and this also um it's also kind of can be visible by work and depth because for cgnans work and depth are almost always of one so we either don't need any work and and ended up for or we just need of K work for c for gcn and maybe maybe some other models like this and then it turns out that nearly all of agnns and mpgnans have work and Dev which are so have o of K squared work so work is proportional to the to the square of the number of features and logarithmic depth logarithmic and in the number of features of a single vector this is the case even for the most computational intensive graph attention model that we that we analyzed right so so this means that all of these models despite maybe having quite some amount of work basically all of them are nicely parallelizable and as you can also see most of them basically again except for for graph attention are their depth is logarithmic and the number of features which is even better because number of features is usually lower than uh than for example the maximum degree in the graph so this is going to be a minor bottleneck in our executions of the single function site right so we again always at this moment speak about the function PSI but now once we compute the size we need to sum them using or aggregate them somehow using our aggregation right and for this we realize that aggregation is almost always an operation that is commutative and associative so this can be a main marks or a plain sum that means that essentially all of these aggregation schemes can be executed users using established parallel to reduction algorithms and essentially these algorithms all of them take a logarithmic depth in the in the maximum degree in the graph and work which is proportional to the to the product of the number of features and the number and the and the max degree right so that also means that uh aggregation may be actually a bigger bottleneck in depth in many of these models than for example the PSI function because our maximum degree in the graph is usually bigger at least in the current workload that we can see is usually bigger than the number of features right so this logarithmic uh this log this this log D in in depth of degradation may actually be in practice bigger than log K that we see in the depth of execution of the execution of the PSI function and finally we also have the the final function the Phi together with all of the previous ones so we would like to now try to see the parallelism and the five function but also how do all these functions add up together the final work and depth scores for these different GNN models so again we have a similar table as before one row of this table is one GNN model again we have these three classes that we saw before cgnns agnns and mpgnns and again we derived the formulation for the Phi function uh but again these formulations are not really important in this presentation so we can check them in the paper with our uniform notation here what is important is again the compute patterns that we have for each of these models so here we recognize the compute pattern for the gcn model it's again like the summation of this of these different feature vectors multiplied with the outcome being multiplied by some dense parameter Matrix and this pattern is actually very prevalent across different models right so we can see that this summation of feature vectors um and and then the multiplication by the by the parameter Matrix the dominant compute pattern in this in these different GN models in some models there may be no such multiplication but maybe just a plane summation and some other model there may be a bit more complicated uh compute pattern where we may for example have to do some concatenation but they don't really change primarily the part the Primal foundational compute work on the properties so we now take a look at these these results for these different models we'll see that um we'll see that the depth of a single genome layer is almost always logarithmic so this is actually a nice outcome because it indicates that in all of these models not only the execution of a single PSI and a single aggregation but with the execution of a whole G of a single GNN layers is always uh is always logarithmic in in depth which is which means that a single Gene layer does not post too much of the bottleneck for our potential computations on the other hand depth of one again and whole training iteration is usually linear in the number of GNN layers right so that's something we can't easily avoid we'll always have this number of genome layers that we need to provide and interleave interleague with our non-linearities which is why we can't really easily allocate this but we'll take a look a bit later how we can actually do it as well the work for different models varies so the total number of operations we need to apply uh virus across different models being the highest photograph attention but also reasonably high for other MP MPG and the models right so we can very often see the square of number of features that we need to throw in to uh to compute to process a given GNN model so now let's take a look at the global formulations right so so with this slide we finish our local formulation detailed analysis the the high level outcome is that despite their differences and how their compute patterns look like all of these models are pretty much very nicely parallelizable without major bottlenecks in the depth maybe having high amount of work which can be however alleviated by throwing more compute resources at them right now let's take a look at how it how it looks like for Global for during the models that will be formulate using the global formulations so let's start with the simple model the gcn model which we can not only formulate using local but also Global formulations right so we can see this model here at the top right in this formulation we to get the feature vectors in the layer in the GNN layer l plus one we need to multiply our adjacency Matrix times the times the feature Matrix that groups all the feature vectors in our given L iteration times the parameter Matrix right and this corresponds to our illustration here that the the kind of illustrates this in more detail we have this part of the Sensi Matrix times the feature Matrix times the parameter Matrix right with the big dimensionalities indicating the number of vertices and the small one small ones indicating number the number of features right and now this highlighted row here corresponds to the neighbors of a specific vertex V right it's for uh the whose feature Vector we are now we are now computing on the other hand this highlighted column corresponds to the specific feature F that is being computed for this vertex V right so one column of this H Matrix is a single feature one row of this a matrix is uh is a single is the neighborhood of a given vertex right and now we can we can we can we can we realize that I mean we know this that different parts different products in this in this matrix multiplication multiplication chain correspond to different parts um different phases of our local formulation so for example the product between the Ado sensory Matrix and the age Matrix is our reduction from the local formulation and the products between these the age Matrix and the W Matrix is the fourth update vertex phase essentially the Phi function from our from our local formulation and now in terms of parallelization we can process each of these rows in parallel so we can now we can consider these rows of of the adjacency Matrix in parallel it really corresponds to considering different vertices in the local formulation in parallel at the same time you can also consider each of these columns in parallel which would correspond to paralyzing across the feature Dimension processing different features in parallel however this moment where once we combine a with h we need to synchronize because once we have partial feature scores for a given vertex we need to sum them up and in this moment we need to we need to conduct some synchronization which is really our log D bottleneck our logarithmic bottleneck in the depth of the reduce of the reduced function that we have in the local formulation we also have such analysis for more models for example for the vanilla attention model which is very similar to the gcn model we can see this the the expression for for the vanilla attention here so our a is again the other sensory Matrix on the right side part you can see again the product with the with the feature Matrix and then the parameter Matrix but then what is different is this part of the middle right so we also have to conduct the element wise product with uh with a result of H Matrix times its transpose right so this is really the algebraic the linear algebraic way of writing that we need to combine we need to compute the attention score for every Edge and and then apply these scores to our adjacency sparse Matrix right so this corresponds to our picture here with these parts that we know from the previous slide and now the new parts that correspond to the edge attention scores we have to compute for every every Edge and this also and also these operations now correspond to the first and the second stage of the of the local formulation pipeline right so we have the parts namely the element wise product of the decency Matrix and the outcome of the age time is its transposed corresponding to the scatter function um and and the update H uh part which really corresponds to this product of these two of these two matrices here right but now again what is important is the parallelization right so the highlighted columns here in this picture in this in the central part of this picture uh correspond to two features that we are going to to Future vectors we are going to use to derive an attention score for a given Edge and now in terms of paralyzing on one hand you can apply all the ways of parallelizing this as we did in the gcn model and more right so on one hand we can now apply all these element y scores here element wise products between the adjacency Matrix and this dense Matrix here we can apply them all in parallel and the same for these dot products between these corresponding filter vectors right you can now apply the dot product computation fully in parallel to compute The Edge scores full in parallel for every Edge separately okay that was quite intense so now let's take a look again at some a bit more high level summary so what we have here is again is a similar table that we have that we had for the local formulations one row of this table corresponds to one specific GNN model um we again have some models so here we can see are some models that we also know from the previous table that we had for the local formulation so this is like gcn gin combinet we analyze this model also before and uh using work depth for the local formulations we also have now the algebraic formulations in the global in the global sense what is important is that all these models use the first power of the adjacency Matrix and their expressions right so we have we have the sensing Matrix and the first Power somewhere in these formulations and this is why we also can call these models linear models because they use the linear form of The adjacency Matrix but then there are more models in in our whole in the whole graph representation learning runscape other models in which we use the adjacency Matrix in a more complex form so in these models like deep walk or Orchard neck or node to vac we use some natural power of our decency Matrix and this is also why we call these models polynomial models because we use some polynomial power of the adjacency Matrix in the expressions of these models and then we have also the third class which is even more generic in which we use some operational power of the adjacency Matrix in the mathematical formulation which is why we also call these models rational r right so this is this is what we know is out there this is this is a well-known shape of the graph representation learning landscape we have these three classes linear polynomial and rational uh that we all can formulate using Global formulations and now again the question how do they infer in our parallelization analysis what is their work what is their depth do we have any patterns uh between these different models right so again we provide the the compute patterns of these different models we're not going to skip the read the details how we derive it but it's actually quite straightforward again you identify the most important operations and just picture them using the uh the The Matrix the the right Matrix right Matrix symbols and you can see that in the linear models the prevalent operation is the product of the sparsity Matrix times the tall feature Matrix times the parameter Matrix sometimes with some variations like for example having the vanilla attention computation or having a series of small parameter matrices if we have for example a full MLP applied at the end of the given layer right then for polynomial matrices we at some point have to sum our or apply some higher power to our adjacency Matrix which is however higher than the than the power one right so we for example in deep work we need to sum a series of our distance matrices to rise to different powers right and then we also at the very end also have to multiply by the by the feature Matrix and by the parameter Matrix and then in the rational models we may have to raise our decency Matrix from more arbitrary power for example minus one right and now we also provide the results for work and depth here again picture the results for one whole training iteration or inference um the conclusions are that depth of a single layer in linear models is always logarithmic so good news we can paralyze these models nicely propolynomial models depth of a whole training iteration is also logarithmic so in these models we don't really have usually don't really have non-linearities between layers so we only have this notion of of genome layers instead to govern the the information about the more remote parts of our graph instead of doing this this layer wise propagation We rise The Matrix to the higher power but as we don't really apply these nonlinearities in between we can nicely paralyze the rising this Matrix to the higher power which results in having logarithmic depths for the whole training iteration and similar outcomes for directional models despite having the most arbitrary formulation we can actually compute these these models in square logarithmic depth so it's not exactly logarithmic but it's almost logarithmic and it's actually also in practice quite parallelizable so uh now we have this very Broad View on both local and Global GNN formulations right so we have this again the teacher you have the local foundation on the left we have the global one on the right and now what is their differences right so um so on one hand some models have both formulations for example the gcn model can be expressed easily in both that's not always the case for many of these models but for such models like gcn they have at the fundamental level the same amount of parallelism because they come with the same work and the same depth right so regardless if we write now gcn in the local formulation or in the global formulation the amount of parallelism will be exactly the same in both formulations that now translates to more practical outcomes and how we actually implement this right because these formulations uh behind them there is hidden a whole world of different ways of implementing these models right because now we local formulation will be implemented differently from a global one but the amount of parallels in both implementations would be exactly the same however there are also now more fine-grained differences because we use different compute kernels in these different formulations so in local local formulations we use often kernels like concatenation of of two different vectors element wise product of two vectors summation of vectors dot products maybe a dense Matrix Vector product but the important thing is that when all of these kernels uh dimensionality is always K number of features which is not very large in practice compared to for example number of vertices right but in global formulations what we use are different kernels which are usually much bigger in scope so these are also these are also dense matrices for example Matrix times its own transpose or the product of two matrices one of them may be having a large Dimension being equal to the number of vertices but also we use sparse matrices right so spars are just NC matrices or even powers of these matrices and now it looks like um these computations are actually different in these in the context of these details and this is really the case because they would now come with potential for different optimizations the global formulations come with potentially more opportunities for vectorization right because we can now we have basically more numbers we could try to vectorize dimensions are bigger in many cases which is why we could apply vectorization uh probably more often and more successfully and done in local formulations but in local formulation we also have some Advantage mainly potential for more flexible scheduling right so as we deal with smaller kernels it may hurt our vectorization routines but at the same time we could now easily more easily schedule different kernels because now they are smaller in scope smaller in the amount of work and that we have to apply to them which means we can we can schedule them more effectively across fine-grained compute resources finally let's also take a look at the difference between linar versus the polynomial or rational formulations right so this is uh this is fully within the scope of global formulations as you remember we have linear ones where there is the first power of the original Matrix being utilized and then we have a polynomial and rational ones where we may have more complex powers for example in the node to vac we have the second power of the of the normal light adjacency Matrix and ppnp model we have the minus one power of the adjacency Matrix at some point right and they also offer parallelism right so this is the other takeaway we can also paralyze them at the fundamental level very nicely with log n depth for the polynomial models and log square and depth for the rational models right and this is really because uh while the L vanishes they require deriving a given power of the decency Matrix which may which complicates it a bit but at the same time it's really a way to to be able to paralyze them more effectively um however as we don't really have these non-linearities in this in these in these formulations uh very often this means that they may also come with some loss in the representative power right so so this is actually a trade-off now we can use these models maybe more willingly because we could run them faster but at the same time we may deal with some accuracy laws in our predictions so now let's move to the final part of this of this tutorial I'm going to focus here on this one one aspect that I mentioned that a couple of times during this slide so I used to say that we have this L term which is which is number of gnl layers and this theorem sounded a bit annoying because we had many times that there was this final depth uh which indicates our sequential bottleneck and in most of these models this this that was linar in this L right so we could not really reduce the sequential bottleneck of this L uh with this previous analysis but can we somehow alleviate this yes the answer is that we can actually do it and then we can do it in a couple of different ways let's just take a look at one class of schemes that we can now grab to actually make this l in practice lower so I'm not going to show you now any asymptotic advantages and only going to show you a path to actually doing this more effectively in the future because this is what I'm going to introduce now is is in most cases actually not yet explored in the context of the Practical implementations or outcomes so what I'm going to discuss are asynchronous graph neural networks in which we introduce some staleness in the formulation and or in the execution to get better throughput and then practice lower lower this L term I'm going to use the following symbols and colors so colors in that case are going to indicate different layer stages right so this will partially overlap with our parallelization of the of the of the of the GNN layer so red color will now indicate the sparse graph operation and the worker which is conducting the sparse graph operation the green color will indicate the dense neural network operation MLP in that case and the blue color will indicate the nonlinearity such as such as relu and also the worker doing this this stage next I'm going to use different lengths of blocks so the length of blocks in the case duration of of a given stage right so this the shorter the block the shorter the given stage of a genome layer will be will run the faster it will learn sorry now different shades of colors will indicate different GNN layers so in the following example we are going to take a look at two layers of a GNN execution both in the forward propagation the light shade colors are going to be layer one and the Deep shade will be layer 2. now the important thing every color and every shade is a different worker right so we are going to see two different layers each layer having three stages which means six workers in total and finally the P1 P2 and P5 symbols will indicate different graph partitions right so we are going to set this asynchronous GNN execution setting in the context of graph partition parallelism so asynchronous gnns we could now apply this asynchronous execution both to micro pipeline parallelism where you probably remember we we assign different workers to different stages of a single layer but also to the macro pipeline level where we paralyze across different GNN layers right this means we could now have four different combinations so let's start with the basic setting where we don't have any as an economy at all we are going to see here an example of a synchronous micropipeline combined with a synchronous macro pipeline execution so in this plot on the x-axis you can see the time right so we are proceeding with our computation from left to the right the y-axis is the number of is is the specific device or a worker right so this row here corresponds to worker one and layer one this row here corresponds to worker 2 and layer 1 this row here corresponds to worker 3 and layer one right and the same for Layer Two right so and then we have this line in the middle this dashed line which indicates enter interlier enter GNN layer synchronization between these two layers right and then we can see that in this polysynchronous execution first thing the neural operation executed by worker 2 must wait for the fully finishing of the of the execution of the of the red convolution operation done by worker one then non-linearity you have to wait for finishing the neural execution assigned to to P1 to um to to partition one and worker two right then we have to wait once we finish layer one we really have to wait uh until the whole computation of layer 1 is finished before we can start uh processing Layer Two right so this is full synchronous execution in both micro and macro pipeline right then what we can do we could introduce our synchronic at the very beginning in the micro pipeline level right so here what that means is that we still have this inter-gen and layer synchronization because we have again we have still synchronous execution in the micro micropipeline right so we don't really do an asynchrony across the genome layers but we do asynchronous in within a single GNN GNN layer in the micro at the micro pipeline level right so that means in practice that the worker 2 can start processing processing the neural operation right after the corresponding operation of a given graph partition is is the convolution operation of a given graph Partition by previous worker is being finished right so that means that in this moment we do introduce some staleness because this neural operation is going to only consider the finished results of a single graph partition and it will not wait for finishing the results of this partition 2 and partition three right so that also means that we may also at this point have some staleness in our outcomes right then we do the same in in Layer Two third the third combination we may apply is having the micro pipeline synchronous but introducing asynchronously at the macro pipeline level right so that means that in the micropipeline we can still the worker 2 still has to wait for all the graph partition to finish their graph convolution stage before grabbing that outcomes for the neural network stage the dense part right but we don't really have this the synchronization between the layers no longer which means that we can now start processing again the the corresponding computation belonging to layer 2. as soon as we finish processing non-linearity of the first partition of the previous gnm layer right so that means we again have some staleness this time of a different type because we don't really wait for example to finish this neural network operations um in the previous first layer but uh as before we have the we can see some some improvements in our time execution right so this is the I mean why we do it is because on one hand you can introduce you can improve the throughput which translates to having faster execution right so before at the very beginning we can we saw that in a fully synchronous execution we had long timeline that it took to process these two layers then introducing asynchronous one a part in the micro level or in the macro level reduces the the latency of the whole of the whole execution and then at the very end we can do the full asynchronic in the micro pipeline at the same time with the micro pipeline which fire improve the improves the throughput throughput fire reduces the latency but makes this execution potentially even more stable right we may see even more staleness here and then at the very final step we could even think of doing of removing the synchronization at the very end of the forward propagation pass and do the pipelining do the asynchronous pipelining with the backward propagation bus to have a fully fully asynchronous execution also considering forward and backward propagation pipelining right again having much higher throughput but at the same time having even more staleness right and then I'll be showing the paper is that you can actually also formally describe using the message passing graph neural network formulation right so here we have again our cheat sheet the mpg and then formulation that we know from the previous slides um and now one way to to extend it formulation towards a synchronym is to explicitly consider these graph partitions right so at this moment we still don't have any async already introduced I'm just only introducing the the graph partition explicitly into the mpg and N formulation right so we can see this by splitting the aggregation function across two types of neighborhoods right so now each one of the vertices may have neighbors in a local partition but also may have neighbors in some other remote partitions right and now we explicitly we can consider this explicitly at the model description level here by splitting this aggregation function into these two parts right and one part on the left we aggregate over feature vectors in our local neighborhood NL on the right side we do the aggregation in the remote across our remote neighborhoods of the remote Neighbors uh that I may be in other graph partitions right so of course these two must uh um I mean we must be able to you can compute the reunion and this Union must be the initial neighborhood of vertex I right and then once we have these outcomes of these two aggregations separately for the local and the remote ones we can conduct their final aggregation so aggregate them together with the final score right but then what I also uh and then we can further extend this towards the the asynchronous execution right so for this again let's take a look at the previous uh the equation here so here we have C you can see we have two indexes now one we have this L which as before indicates our adrenal layer but Tina also indicates the iteration the training iteration right so now we explicitly consider both the training iteration and the GNN layer and uh in this in this middle equation here that I just explained before we can see that this is still synchronous execution because the state of our feature Vector in for example layer l and training iteration T is based on the feature vectors of the same training iteration T right so T is also here always the same and also on the L minus one GNN layer so we do as we did before we grab the future vectors from L minus one G and N layer and we use them to compute the final to compute the feature Vector in the next GNN layer now moving to the lowest to the bottom equation this is exactly here how we introduce the staleness how we can do it at the level of the model formulation so we have now for example here in this L iteration indexes or in the in the gnm layer index we have parameters that that introduce the staleness so for example here this big L with Phi is a user parameter that specifies how far into the future in the worst case we can grab to grab to to fetch the feature the feature vectors from some iteration from some some genome layer Which is far far behind in the computation right so this if this L Phi is now for example equal to two or two three we would be using the feature vectors from two or even three iterations before right which really would have uh would make the exhibition stale and the same for training iteration right so we could now do this apply this concept both for the GNN layers and for the training iterations and that's really the way how to formally describe Junior models asynchronous DNA models at the at the model description level now an interesting research direction would we try to devise genuine models like the concrete models that actually apply this in practice and see how they infer uh both in terms of their predictive power convergence speed but also performance throughput and latency you can check the paper for many other details that we analyzed on one hand we provide many more details about the mathematical formulations of gnl models we actually have even more details and especially their correspondence to the programming paradigms right so we're now in gnns we now have on one hand mathematical formulations the global and local formulations but also we have our programming paradigms that that are actually there are a couple of these different paradigms many of them basing on scatter apply Edge Aggregate and update vertex uh programming kernels but also with others having even more more sophisticated ones and and we provide analysis into how these two correlate with each other again in the context of parallel execution right then we also provide more details about data parallelism specifically the neighborhood the neighborhood explosion phenomenon that was nicely described in the previous tutorial the way we can partition the graphs now so we can also apply more sophisticated schemes to the way that we partition the graph in the in the graph partition parallelism and also even more effects being analyzed together with their work and depth analysis then we have also details about synchronous gnm computations the context of computing gradients so we can also introduce asynchronously in Computing the gradient so you can also check this in the paper and then we use all these insights we got to analyze the parallel design of different existing GNN Frameworks and accelerators right so we analyze what is the support for parallelism introduced in different Frameworks different accelerators for example The Blaze support data parallelism if yes which mode do they support model and and um and pipeline parallelism and this for example could be used by uh to maybe disseminate like ways of paralyzing which are more powerful analyzing different Frameworks with their respective designs design differences trying to identify the most um the most advantageous way of paralyzing combined with the with the applicability into the model General model domain and finally you feel free to put our how we actually apply some of these insights from this investigation into devising new Gmail models that we use to solve problems such as link such as motive production or how we actually apply some of these comments into into more system design aspects of gnns for example combining gnns with graph databases thank you for your attention and please provide the feedback in the following form and now we can we can take your questions together resources when she has a question yeah so so thanks for for the very nice and very comprehensive presentation and as you said there are there are many many ways to parallelize the the GM and uh if they're uh a comprehensive study about how this different parallelism will affect the training time the accuracy and so forth or do you plan to to do some research about that we plan we plan to push this and to analyze this better together with developing new systems based on these insights okay thanks but just one maybe one um like the follow-up on this question is that uh the prevalent way so I would say at this point it's really not about uh and because like the development of these Frameworks is still and it's somewhat early stage and what you can see is something you would expect is that the simplest forms of parallelizing are being used more frequently right so what we saw was that most of these Frameworks actually apply data parallelism either in the short memory setting or in the distributed number setting but really data parallelism is the prevalent way of doing this on the other hand what this uh what you would also expect at this stage of development is that the most complex aspects are still not really touched right so for example while there are a couple of designs that do uh macro and micro pipeline parallels but only a few there is uh there is very very few that really touch on asynchronous parallelization right so this I didn't really see much in that direction because probably the most complicated but also would be interesting to analyze now how this um how this works in practice yeah definitely there are many many research questions are there thanks a lot yeah one one addition is also like once we scale graph neural networks to extremely large data sets and and larger models than we do today then we will require these other forms of parallelism um so for these small models that that we are looking at uh these days it's it's not yet required but I'm expecting that those will scale pretty massively like we're seeing in traditional deep learning with GPT models as soon as we figure out how to actually do it and there are data science issues still but I'm positive that they will be resolved and then we need the systems issues to be resolved as well yeah definitely yeah thank you very much and and hopefully see you in real life at some point see you bye bye bye