Graph Neural Networks: Theoretical Foundations Explained | GNN Theory

[00:00:00]good afternoon it is a pleasure for me to welcome dr peter velikovic who is going to deliver a talk on theoretical foundation of graph neural networks better started in 2012 as undergraduate at the computer laboratory i remember i received an email around may uh 2014 uh and he he was asking for a part two project in bioinformatics then the phd and his uh his examiner um was yura leskovic and immediately after submission of it is he started with deep mind he is now a senior research scientist peter is all these audience 400 people are going to listen to you thank you very much pietro for the fine introduction and uh thank you so much for showing up in such big numbers uh i'm truly humbled and i see so many people i know so it's a really a pleasure and an honor to be back to the computer lab even if it's virtual and to talk to you all about uh one of the topics that i've been most passionate about over the past few years and as i've grown to understand the field more and more i've also sort of tried to improve the way i present the whole field so i hope that you will find today's exposition interesting regardless of whether you're a seasoned g n particu practitioner or someone who's just getting started with with the area of graph representation learning so in this talk we will be covering neural networks that operate over graph structure data or they're more popularly known as graph neural networks or gnns for short first if you haven't come across the area before i would like to give you a little bit of an overview on why might be why might it be a good idea to study them by giving you an example of just a few fantastic graph neural nets you can find in the wild nowadays the first and perhaps the most direct example i like to give is the case of molecular data processing so you might fairly obviously see that molecules can be naturally represented as graphs you can look at here the molecule for paracetamol and look at the different atoms of the molecule as nodes and the molecular bonds as edges connecting them and then you can meaningfully attach some features to both the atoms and the bonds such as the atom type the charge the bond type are we located in a ring or not and so on and so forth so once you've featurized the molecule in this way one very interesting question you can ask a machine learning system is is this molecule going to be a potent drug and uh one particular way in which you can pose that question is a binary classification problem so taking a representation of a molecule as you have it you can ask a gnn will this molecule inhibit a certain bacterium for example a shariah e coli and then once you have set up a task like that with a training data set of uh molecules with known responses to e coli you can train a graph classification system using a g n to predict whether or not this bacteria is inhibited now one thing that's really cool about this is that once you've trained the system like that you can meaningfully apply it to any molecule even the ones you haven't seen in your training data so you can now execute your system on a large data set of known possible drug candidates and your model will give you some probabilities that those previously unseen drugs are going to inhibit e coli you can select the top 100 candidates and then ship them to chemists and have them thoroughly investigated and it just might happen that in these top 100 candidates lies a highly potent antibiotic that was previously overlooked by researchers in the area here i've shown you one such example of a compound that was discovered in this way which is halisin and uh you know of course this is a very important uh discovery of using graph representation learning to detect antibiotics so you obviously publish it in a high impact journal but then afterwards this basically kicks up a bit of a avalanche in the in the press so it gets re-shared by nature afterwards gets reported on by the financial times by the bbc and so on if you've seen at roughly the start of last year all of these titles like scientists discover powerful antibiotic using ai you can now know that actually underneath all that ai at the core is basically a graph neural network so this is still to this day probably the most popularized application of graph neural networks now for a completely different example which is much closer to what i've been involved in lately you can represent transportation networks like the ones you see on google maps naturally as graphs you can look at different nodes intersections and edges as the roads connecting them and you can put various interesting node features like the lengths and speeds onto these inputs and within deepmind we have a very successful collaboration with google maps where we deployed a graph neural network on road networks constructed in this way to predict what's the current estimated time of arrival which is obviously a very important problem in transportation modeling especially for a service like google maps and what's very interesting and as a success story of gnns we've already deployed the system in several major cities around the world you can see the picture on the right explaining some of these cities and in some of them such as sydney we have reduced the percentage of negative system predictions by over 40 so this is also one example how graph neural networks and graph representation learning are affecting basically billions of users every day if you're in any of the major cities around the world and you ask for the shortest path from point a to point b in google maps it's very likely that your query will be passed through our implemented graph neural network and generally they're a very hot research topic even outside of the realm of applications graph neural networks are regularly among the top and fastest growing keywords for the major machine learning conferences and also represent graph representation learning workshops are regularly the most attended one at conferences like nerfs so gnns can be seen as currently experiencing their image net moment and it's generally a very good point in time to start studying them and besides that you have a rich ecosystem of libraries if you want to get started with implementations regardless of whether you use pytorch tensorflow or jacks there is a library that can be found to suit your needs this talk will be recorded and released so you can check out the links afterwards but rather than just libraries there are also a wealth of useful data sets that you can use to validate your model such as the open graph benchmark tu data set and the data sets and benchmarking graph neural networks so hopefully now i've given you a convincing argument for why it's useful to study gnns if you'd like to see a bit more of these bleeding edge applications i've given a much longer talk on this at eml 2020 which is available on youtube and you can check it out what i want to do today is to give you good blueprints and context if you want to study the field further so i'm first going to drive gnns from first principles and then position that in the context of several independently studied directions that ended up deriving essentially the same idea so hopefully this is a perspective it will be useful both to newcomers that are looking for a good survey of related work and implementations to check out and also seasoned graph new network practitioners who might benefit from this particular perspective and way of looking at it of course i welcome any and all feedback so please let me know during or after the talk how you liked it the content is based on my current collaboration with john bruno michael brownstein and taco co and i'm categorizing geometric deep learning and you can see various contexts that i'm going to present here within chapter 7 of will hamilton's excellent graph representation learning textbook i also put some thought into the historical context behind everything here and i would like to thank the researchers outlined here for at various times presenting me with useful insights that i placed within this talk but of course any errors in admissions made are mine alone and please let me know if there's anything that i have misrepresented during this talk finally before we get into everything the talk content here is geared to a general computer science audience we'll just build useful functions that work over graphs and we will use concepts that you can commonly see in a computer science curriculum if you actually want to get started with implementing any of these models it will require a bit of background in machine learning with deep neural nets and you can use the great deep learning book to get started in the area by good fellow benjamin corville i recently put up a twitter thread which lists many useful graph new network resources and when you feel ready to start implementing alexa gorditch has recently put out a very influential github repository that presents our graph retention network model from the ground up and in my opinion it's probably the most gentle way to get started with the implementations with all that out of the way let's get started and let's try to drive gnns from the first principles so we will see how we can define useful functions that operate over graphs and basically we're going to study what are the properties that are useful for a function to operate meaningfully over graphs specifically what are the symmetries and invariances that a graph neural network should ideally preserve and to kind of jump into the study i'm going to revisit the known example that you've seen if you've done any kind of image processing is this idea of an image convolution and here provided a brief animation of how it works you have this small kernel matrix k which is slid across an image and locally captures patterns of interest around the image so what this kind of model encodes is this concept of translation and variance it means that a pattern is interesting no matter where i find it in the image that's why i slide the matrix across everywhere also it encodes an assumption of locality pixels that are close to each other are probably going to be far more strongly related than pixels that are far away in the image so these concepts are very useful for images what might be the case for graphs and in the case of graphs you might look at them for a little bit and realize that if you don't assume any particular geometry to them then the nodes of a graph are assumed to be not given in any order and that means if i give you two graphs that are completely isomorphic here i've given two examples of if you look at them you will see that they're actually the same graph we would want our graph neural network to give us exactly the same result for those two graphs and what we're going to do now is see what are the basic building blocks we can use to enforce exactly this this will bring us to the concepts of permutation and variance in permutation equivariance in order to simplify the setting for now i'm going to assume that our graphs have no edges so we just have a set of nodes v and in each one of those nodes we may have a feature vector x i for node i and the way in which we typically process this in graph representation learning land is we stack these row vectors into a matrix of shape n by k where there's n nodes and k features in every single one of them that is the i throw of the matrix corresponds to the i feature vector and one thing that's very important is that just by the act of stacking the nodes you've specified an order in which you're visiting them and we would ideally like any result of applying a graph neural network to not depend on an operation like this so it's useful to think about what are all the operations that might just change the node order and do nothing else you may know from mathematics operations like this are known as permutations for n nodes there's n factorial many of them and it's very nice that we can think about permutations and stay completely within the realms of linear algebra because each permutation defines a unique n by n matrix here given a matrix for the case of two four one three each of these matrices are called permutation matrices and they have exactly one one entry in every row and every column everywhere else they have zeros and as you can quickly see by a matrix product with one of these row stacked feature matrices the only effect they have is to uh permute the order in which you have your vertices and nothing else so these matrices are very useful as a tool to study this further so in order to design functions over these set matrices x that will not depend on the node order we basically want to say that if i were to apply a permutation matrix to the input that is if i were to change the order in which i present you the nodes that shouldn't change the result so this gives us a very useful notion of permutation and variance and we say that a function operating over sets is permutation invariant if no matter what permutation matrix p i apply to the set before applying the function i'll get the same result uh anyway like as if i never did the permutation in the first place you might have seen some models that exhibit permutation variance before one very generic form is the model presented in the deep sets paper published at nurbs 17 where you basically represent the function over sets as some independent function psi applied over the row vectors x i and then you perform some permutation invariant aggregation function which is agnostic to the ordering something like summation maximization or averaging and then afterwards you might also stitch an extra function at the end this phi function that operates over the aggregated representations and because you have this critical sum aggregation you're able to summarize your entire set in a way that is independent of the order of the nodes you've provided now this is a very good way to obtain outputs on the level of entire sets because we're aggregating the entire set but what if we want to do predictions on the level of individual nodes now if we want to do that we don't quite need permutation and variance we need something a bit more fine-grained we want to be able to once we've performed our function on sets to still be able to identify what part of the output belongs to which node and a permutation invariant aggregator would pretty much destroy that because it would kind of crunch together all the nodes into just a single vector so what we might instead seek in this case are functions that don't change the order of the nodes that is if i have a permutation specified by a permutation matrix p it doesn't matter if i permute the nodes with it before or after i apply the function the function itself will preserve the order so accordingly we can define the notion of permutation equivariance if no matter what permutation matrix i throw at this input it doesn't matter if i threw it before or after i applied the function and that's neatly summarized in the equation below now with this we can say that equivariance mandates that every node's row remains unchanged after i apply this function and we can think about it basically if we focus on the function as operating row wise this will be a very important perspective when we move to graphs so we can think about permutation equivalent functions on sets as these psi functions that are independently in isolation applied to every node i giving us latent vectors h i and once you stack the h's you can get a latent space matrix h which represents the features in each of your nodes once you've applied the transformation combined with invariance this gives us a very powerful blueprint if we stack together these equivalent functions that transform each node in isolation potentially with some invariant tail if we're interested in like results in the level of the entire set this gives us many useful functions on sets arguably this is as far as we can get with basic sets without assuming or inferring additional structure which i will get into later on during this talk so now that we have these concepts of invariance and equivariance on sets we can try to transfer them to graphs and it turns out to transfer quite easily so now we assume that rather than just having the nodes we also have some edges between them so we have a set of edges e which is a subset of the cartesian product of the nodes and we can often represent them conveniently with this adjacency matrix a which has one entries wherever there's an edge and zero otherwise and there are other additions you can add to this like edge features edge types and so on but i'm deliberately ignoring them to keep the blueprint simple it's usually quite easy to introduce all of these things back and the main things we want permutation variants and equivariance they still hold we just need to express them slightly differently so the main difference now is that when you apply a permutation to the nodes you're also applying a permutation on the edges right because the rows of the node feature matrix correspond to both the rows and the columns of the adjacency matrix you need to apply a permutation matrix to both the rows and the columns of a in isolation and this is conveniently written down as p ap transposed and this just gives you updated versions of the invariance and equivariance rules for graph structured inputs just as before so now our function takes in node features as well as an adjacency and if i were to permute the inputs and the adjacency appropriately it for invariance it doesn't matter if i did it before or after and for equivariance i'll still be able to identify all the node features regardless of whether i've done it before or after now this is a concept that very clearly generalizes but there is something extra we have on graphs that we couldn't quite do on sets uh like as we mentioned on images we really like this notion of local functions functions that operate only over a locality of a certain node and graphs give you a very nice context to do that which is the node's neighborhood so for a node you can define its one hop neighborhood as all of the nodes that are adjacent to it so there exists an edge connecting them and accordingly you can extract the set of features that are in the neighborhood by just pulling out all the x matrix rows for the nodes which are in your neighborhood and i've denoted this as x and i to denote all the feature vectors off the nodes adjacent to node i and if you want to define a local function you can say that now a local function g operates over a node and over this multi set of node features and this gives us a graph a recipe for generic graph neural networks because now if you want to build a generic permutation equivalent function you can just appropriately in a shared manner apply this local function g over all of your neighborhoods so and you stack the resulting latents as different rows of a matrix and in order to ensure that this thing is still equivariant we need to make sure that g does not depend on the order in which you present it at the neighborhoods so g should be typically constructed to be permutation invariant to the entries of x and i and this is just to give you a visual of everything that we've covered so far we're going to express graph neural networks as a local shared function g applied to every node and its neighborhood in isolation and as a result of applying g we will go from input features x i to latent features h i and here i've given this one example of a node b and its local neighborhood in a graph containing nodes a c d and e usually we also include node b itself and this function then transforms the neighborhood into the next step latents now once you have a gnn like this i'll just quickly look back at how you can use them to solve actual problems specified on graphs so imagine i give you a graph with some input features x and some adjacency matrix a such that x i contains the features of node i applying a g n on it transforms these x's into latent features by being mindful of their local surroundings and now if i have a node classification task i can look at each of the nodes latents in isolation and learn a classifier on them if i have a graph classification task i can use again a permutation invariant function such as sum to combine all the nodes into one representation and then apply my graph level classifier to classify them and for certain kinds of gnns if you want to predict uh properties of edges or even existence of edges which is known as link prediction you can also build a function that operates over the latency of the two nodes and potentially any edge features you might have between them so this is the general recipe of once you have a genen and you use it to get equivariant latents how can you then use those latents to do anything else that might be of interest on a graph so once you have a grasp of this main blueprint let's see what are the ways in which we would typically instantiate them so as mentioned we construct this permutation equivalent functions f by sharedly applying a local permutation invariant function g over all the neighborhoods and under various guises you might have seen g referred to as either diffusion propagation or message passing and now we're going to look at ways in which we can actually define g this is obviously a super intense area of research but very fortunately for us almost any layer that gets proposed nowadays can be classified as one of three spatial flavors of genomes and they are the convolutional attentional and message passing flavors which i will now present to you one at a time so first of all in the convolutional setting we are just giving an interaction constant cij that says how much do i value how much does node i value the features of node j and then they're basically coefficients in a well weighted sum or different kind of weighted combination of locally transformed features so i have a psi function applied to every node feature in isolation i aggregate them by weighing their contributions using the cij constant and i use some permutation invariant aggregators such as sum to combine them and then that gives me the recipe for the features of that node in the next step usually these weights cij will depend directly on what's in the adjacency matrix and some famous examples are the chebyshev networks the graph convolution networks and the simplified graph convolution networks they're very useful if your graph is thermophilus because when your edges encoded labels should be similar you can usually just get away with doing a very simple average of what's inside your nodes and it's also very useful because they're very scalable like if you know your graphs are going to be homophilus this kind of model is very lightweight and easy to implement using simple matrix operations and as a result it's much easier to scale to say billion node graphs then if you want to make things a little bit more complicated like let's say your edge is no longer just in code for label similarity but there could be some repulsion effects for example if i retweet someone it doesn't mean that i entirely agree with them i could actually thoroughly disagree with them we just replace these constant fixed weights with weights that are learnable and this if you've done something like transformers in the past might be familiar to you as an attention mechanism it is any function that takes features of the sender node and the receiver node this a function here and it gives you a coefficient that you can use to weigh that node's contributions to the receiver and this is one very elegant and powerful way to learn more complicated weighted combinations but it still doesn't require that much information to be computed and stored there's several models implementing this idea some of the earliest ones include the monet model the graph attention network and the gated attention network that are listed here and they're very useful as a sort of middle ground like if your edges do not encode strict homophily relations you might want some more complicated sums but you still want to just only compute one scalar for every edge so it's still reasonably scalable this is the choice that kind of offers the middle ground between the two and on the far end of the expressivity spectrum you have the message passing gnns where the sender and the receiver work together in this psi function to compute an arbitrary vector based message which is sent across to the receiver node so keep in mind in the attention case we still sent just the raw neighbors features weighted by some constant here the sender and the receiver collaborate together to compute what the message is going to be and it's appeared under various guises within interaction networks message passing neural networks and the graph nets model and they can be seen as the most generic gnn layer as a result this means they can fit some very complex simulation data like algorithmic reasoning physical simulations or computational chemistry but that could imply some scalability or learnability issues because now you have to store and compute an entire vector for every edge in your graph and there's typically a lot more edges than there are notes so now once i have covered this basic blueprint and the three basic ways in which you can instantiate it well you can see that presented in this way it looks quite clean but one thing you can remark is that we didn't actually start researching graph neural networks from a blueprint like this and if you've studied graph neural networks especially a few years ago you haven't seen them presented in this particular way you might have seen a perspective like spectacular versus spatial or deep walk in no to vec or something like this and the reason for that is that graphs very naturally arise across the different branches of science and different disciplines have found different tools to process them but now i'll give you a feel for how accurate this blueprint actually is by surveying a lot of these prior and concurrent approaches and showing how in most cases they map pretty much exactly to this blueprint that i've just shown you and if you've read up any kind of graph representation learning before there's a good chance you will have at least seen a few of these but it's perfectly fine if you haven't seen some of them uh i've left enough references that you can get started on any of them in isolation so the first one perhaps the most kind of traditional boom of deep learning on graphs came through node embedding techniques and they rely on finding good ways to embed nodes in a graph into vectors i've taken this figure with great thanks to will hamilton where he used the z notation for the embeddings i'll typically use h and it's using an encoder function but at the time all these encoder functions were actually lookup tables so you were just learning a flat representation of every node without any particular complicated function used to derive it and now the question is what makes this h vector good well graphs carry interesting structure and if you have a good representation of nodes it should ideally preserve this structure and what's the simplest possible notion of structure you can have well it's an edge so if i have features h i and h j of two nodes they should be somehow predictive of whether or not say there exists an edge between the two of them and this gives us a very straightforward unsupervised objective we can optimize these h vectors to be nearby if they formulate an edge or far away if not and this allows us to just take the dot product the dot product similarity of the two nodes will tell us what the estimate of this value is and then we can optimize it using standard binary cross entropy make these dot products high for edges in the graph and low for non edges in the graph and this is actually just a special case of a far wider family of methods called random walk objectives which tried to make this a little bit more interesting by refining the condition from they should be close together if they're in an edge to they should be close together if they co-occur in a short random walk so this allows you to slightly expand your receptive field it should be noted that this dominated unsupervised graph representation learning before gnns became a thing and you've if you've been around that area you've probably heard of approaches like deep walk or note to back or line which are sort of the flagship papers that uh spearheaded this area but one thing that's very important to note is that as i mentioned these random walk objectives force the embeddings to be close to each other if they are close together in the graph but what does a convolutional genuine do it summarizes an entire set of neighbors around you into a vector embedding so because in most of these like small world networks like the one i pictured here if you have two nodes like i and j here that are connected with an edge they're actually going to have a lot of overlapping nodes in their neighborhoods see like for the all the neighbors of i and j only two nodes this red and blue note on the side are not featured in both of their neighborhoods so if you just apply a g m without any particular training it should make them have similar embeddings just by design and basically from a representational perspective these deep walk style models emulate an untrained convolutional gnn one corollary of that is that typically it doesn't work that well to combine random walk objectives with gns and actually at times you can match the performance of deepwalk by a convolutional genome that hasn't been trained at all i first spotted this within the deep graph infomax paper as an accidental consequence of setting the number of epochs to zero and it was since then independently verified by several other researchers in the area so one thing that you also might find interesting here is that there is a clear correspondence between the node embedding techniques that i just mentioned and some of the more traditional word embedding techniques in natural language processing if you think of nodes as words if you think of these random walks as sentences you can basically equate node to vect with the word to vec objective and their optimization objectives are actually near equal they even both feature negative sampling and things like that and actually this is a correspondence that continues even nowadays some of the recent work on pre-training graph neural networks borrow a lot of concepts from bert and i've left the reference here if you would like to read a bit more about this but speaking of nlp let's make a quick remark about nlp so it's not just that gnn design is inspired by an lp sometimes you can see concepts going the other way if you look at words in a sentence they're obviously going to interact in some interesting ways like subject object and these kinds of relations and they interact in a way that's not trivial and not sequential that means that processing them using a simple recurrent model or a convolution model may not be the most accurate way to look at them we may actually want to use a more generic graph over them but the problem is what is this graph and one common assumption when you don't know what the graph is is to just use a complete graph and let the graph neural network infer what the relations are and if you worked at all the natural language processing over the past few years this should sound very familiar in fact i've literally just described transformers to you so this is no coincidence transformers actually can be seen as a special case of graph neural networks they fall very nicely into the blueprint i mentioned because they work on a fully connected graph and they use the attentional flavor of gnns how do you tell a transformer that it's still looking at a sequence it's by putting them these extra features these positional embeddings that tell you exactly where you are so that you're not just looking at a bag of words but if you were to drop these positional embeddings you get a very standard vanilla fully connected graph attention network model you can another very great perspective looking at this is that these attention coefficients can be seen as a means of inferring a soft adjacency matrix this is a very interesting area and the links have been brought about in much more clear detail by chaitanya joshi in this gradient publication so if you're interested to find out more about this link i would highly recommend that you check out this this paper but in the meantime i'm going to move on to one of the most popular early approaches to deploying graph representation learning you might have seen in many cases that early papers including one of my own would classify graph neural networks into spectral and spatial i am now going to hopefully show to you that in most cases this divide doesn't actually truly exist so how did we get there well one very useful quantity from digital signal processing is the convolution theorem which defines an identity that is very attractive to us because it's allowing us to express a convolution in some domain like the time domain as multiplication point wise multiplication and some other domain like the fourier domain and this is a detour to defining convolutions because defining an operator that does point-wise multiplication in a learnable way something that's quite easy for us to do but the problem is you know the convolution theorem and fourier transforms are usually defined over these time-specified signals so what would be the domains in the case of graphs well to get there we will first see how graphs come up when you look at discrete sequences we can imagine a kind of a time series or a sequence as this cyclical grid graph the reason why i've added a cycle from the first to the last time step is so i can more easily handle the boundary conditions but generally it doesn't change the findings that i'm going to have and we can express a convolution operation this is kind of by analogy to images as something that looks at a current time step and maybe some immediate neighborhood of it so we compute the updated features of node two the h2 by applying some local weighted sum of node two and maybe some immediate neighbors for example nodes one and three and let's say that the coefficients of this operation are these constants well sorry learnable uh constants a b and c now what's very important is take a look at the bottom of the slide this specifies a matrix operation that you're applying over every time step in isolation and we call these matrix circulant matrices they're called so because you can start with the first row and then as you go down the rows you always shift the all of the coefficients by one to the right any matrix that has this property is called a circulant matrix and in the case of 1d convolutions it's very evident now one very important property of circular matrices is that they commute that is no matter what vector i choose as the first vector of a circulant matrix i'm able to commutatively apply it with any other and matrices that commute are also known to be jointly diagonalizable that is the eigenvectors of one of them are eigenvectors of all of them that means that they eigen decompose in the same way and very conveniently all circular matrices decompose to exactly the discrete fourier basis of these vectors formed by the complex roots of unity and you can very easily compute these eigenvectors by studying one circulant matrix like the shift matrix which has only uh one parameter in the second position now if you stack these fourier basis vectors into a matrix you recover exactly the discrete fourier transform because if you multiply by the conjugate transpose of this matrix you transport your signal into the spectral domain and this also allows you because all the circular matrices share this eigen decomposition to decompose any circulant matrix as a product of the fourier basis times a diagonal matrix of eigenvalues times the conjugate transpose of the fourier basis and from this you can naturally derive the convolution theorem any circulant applied to a feature matrix x can be expressed using this eigen decomposition and therefore you can first multiply your features x with phi star to cast them into the fourier domain and then because you're multiplying by the eigenvalue matrix which is a diagonal matrix this exactly corresponds to just pointwise multiplication one very important corollary of this is that as long as you know phi these fourier basis vectors you can express your convolution just using its eigenvalues and not the actual parameters of the circulant to kind of summarize everything that i've said so far in the spatial domain we might apply convolution by applying a circulant matrix directly to the inputs x but now i've just offered you a detour i can instead first apply the discrete fourier transform phi star to transport x into the spectral domain and in this domain applying a convolution is just element-wise multiplying with that convolution's eigenvalues and then once i have the result in the spectral domain i can cast it back into the spatial domain by applying the inverse discrete fourier transform which is just phi so the key idea here is that i don't need to know what is the convolution operation if i know its eigenvalues with respect to the fourier basis and this gives us a recipe for graphs now the problem with graphs is that convolutions of interest are usually far more generic than circulant matrices so it's really hard to reason about what those matrices might look like but we can still use the concept of shared eigen bases so if we know some graph fourier basis for our graph we can only focus on learning that operations eigenvalues for grids we wanted to commute with shifts so that's why we had the circulants and we can think of these shifts as an adjacency matrix for the grid and this can generalize when you don't have a grid so if you have a grid convolution on n nodes your fourier basis was always the same it was the n-way discrete fourier transform basis but now for any graph you will just compute its own phi that's dependent on the graph structure previously the structure was fixed now one thing we would very much like our convolution to commute with is the adjacency matrix because that specifies the graph structure in the most direct way but unfortunately we cannot always eigen decompose the adjacency matrix so instead we choose to represent the information in the adjacency matrix in a way that's easily mathematically eigen decomposable and that leads us to the graph laplacian matrix which is the difference of the degree matrix and the adjacency matrix so here you see an example a plus matrix and you can see that it represents all the properties of the adjacency but in a way that's going to be shown to be more mathematically convenient so see you have in all the -1 entries the edges of the graph are encoded and along the main diagonal you have the degree of each vertex in the graph ordered from 0 to 5 in this case so assuming your graphs are undirected which i'll focus on here the laplace matrix is symmetric and positive semi-definite which means that we'll be able to eigen decompose it and this means we can express the laplace matrix as this specific fourier basis phi times some matrix of eigenvalues times phi star and now if i change these eigenvalues i get all the matrices that jointly diagonalize with l or i.e any matrix that commutes with l and we usually look at this expression as the graph fourier transform as popularized by john bruno at iclear 2014.

[00:38:28]so now if you want to convolve like apply your graph convolution into some new feature matrix specified on the nodes you first multiply with this previously precomputed phi star you've entered the spectral domain now you pointwise multiply with these theta coefficients which now can be learnable you can specify them as something that can be learned by gradient descent and finally once you have the result of that product you can cost back to the spatial domain by multiplying again with phi now however directly learning these thetas that i just mentioned is usually inappropriate because it doesn't localize it doesn't generalize to other graph structures it's computationally expensive so there's a lot of problems with directly learning the coefficients even if it gives you a much more powerful class of operators instead what we commonly do to make this tractable is to make the eigenvalues related to the eigenvalues of the laplacian and usually we force the eigenvalues in this diagonal matrix to be a polynomial function of the eigenvalues of the laplacian and some popular choices for this polynomial are cubic splines chebyshev polynomials or k-la polynomials now one thing that's important to note is that once you force yourself to use a polynomial in the laplacian you have defined a convolutional g n because you can literally compute the polynomial of the laplacian and use it to specify coefficients c i j in the blueprint that i previously mentioned and basically most like most of the efficient spectral gen approaches spatialize themselves in a way like this so basically this spatial spectral divide that many papers talk about is not really often a divide because the true spectral non-spatial operators typically don't have the computational performances that we would like or localization properties that we would like now before moving on to the next perspective i'd like to just briefly look at transformer positional encodings again if you've read the transformer paper you'd know that these positional encodings in each of the nodes is given by these complex series of sines and cosines that are related to the position and sines and cosines are very related to the eigenvectors of the discrete fourier transform so one could actually interpret these positional embeddings as eigenvectors of the grid graph and that was the connectivity between the words that we initially assumed like this cyclical grid graph of uh time series coordinates and you can actually use this idea to run transformers over generic graph structures just change these positional encodings with some top k eigenvectors of the laplacian of the particular graph that you're assuming of your data and this was actually recently applied in the graph transformer model from widget and xavier verson which in my opinion is one very exciting direction to consider in rougher presentation learning so uh having finished the spectral section i will completely shift gears and look at it from a more probabilistic perspective the perspective of probabilistic graphical models so far we've used edges in a graph to say there's some kind of relation between the nodes but i wasn't very explicit about what kind of that what kind of relation that is but we can instead take a more probabilistic view and say nodes correspond to random variables and edges are dependencies between their distributions this allows you to specify these notion of probabilistic graphical models and these edges help you decompose a joint probability distribution into a product of much more manageable distributions so in this canonical example bayesian network at the bottom you can decompose the overall probability of a b c d and e as a product of probabilities specified by the edges of the graph and i've kind of color coded it here so that it makes sense a directed edge means a direct dependence but one particular pgm that we will study here is the markov random field which allows you to decompose the joint into a product of these edge potentials specifically if we assume nodes can be represented by inputs and the latent representation that we wish to compute so h i for node i and h i is the uh x is the input for node i and h i is the latent for node i uh there we can assume that they are related for every node in isolation and then assume that the latents are related to each other only according to the edges of the graph and this factorizes your probability distribution into something that's proportional to one potential function applied to the x and the h for the same node and a product of potentials of pairs of latents across all the edges of your graph so these phi and psi are any real valued functions which tell you the energy of this particular node latent or latent latent pair and that specifies the probability distribution now if you want to embed nodes if you have some inputs x i and you want to compute h i you need to sample these vectors from the posterior distribution p of h given x now even if you know the potential functions this is generally intractable and you need some approximations to actually do it properly and one popular method that resolves this is so called mean field variational inference where you assume that the posterior can be approximated by a product of these node level densities q which are specified for every node in isolation and they're well defined and easy to compute and sample from such as say a gaussian distribution and then we can obtain the parameters of q by trying to minimize the kl divergence or some other notion of distance to the true posterior p of h given x now minimizing the scale is intractable but it does admit a very favorable approximation algorithm and if you look at the final formula the actual way in which we derive this formula is unfortunately out of scope we can iteratively update q of h starting from some initial guess by just following this formula to get q of t plus 1 having q of t now if you stare this equation for long enough you'll actually see that it corresponds quite nicely to the computations of a message passing jnn i've specifically isolated what would correspond to a message function what would correspond to a permutation variant aggregator and what would correspond to a final transformation so essentially you can embed all of these standard pgm computations within gene and computations the key difference is that in pgms do you expect the potential functions to be specified and known up front but here the gnn defines them implicitly within its latents the actual first model derived in this way structured to vect was not it was not in itself quite unlike typical mpns but recently there's been a whole lot of other approaches that unify graph new networks with pgms and in my opinion it's a very exciting area to look at for the future finally i would like to make a few remarks on the booming area of graphisomorphism testing and some future implications so we might often ask ourselves the question of how powerful are gnns they're a powerful tool for processing graph data but they won't solve any task on a graph accurately and one canonical example we use to estimate the power is the example of deciding graph isomorphism are we able to use the gnn to distinguish two non-isomorphic graphs so if you have graphs g1 and g2 that are non-isomorphic will i get the different embeddings for the two of them by applying my genetic if i cannot do that then any task where i need to discriminate these two graphs is hopeless because they're going to get exactly the same encoding and one very simple way of distinguishing isomorphic graphs is passing random hashes along the edges and summing them up this is the weiss file lemon algorithm which as you can see in the bottom right corner aligns really well with computations of a com gnn and this connection was spotted very early including the first gtcn paper by thomas kiff and it explains why these untrained gnns work really well untrained gnns are basically relatable to a random hash function one thing that's important to note is that this test is quite powerful but it does fail at times for example it cannot distinguish the two graphs in red and blue that i've highlighted here keep this example in mind i will come back to it in a second now one thing that's very important and somewhat surprising is that over discrete features graphene inlets can only be as powerful as this test that i just described to you and in order to reach the maximal expressivity it's important that your aggregation function is something that's injective such as a sum graph isomorphism networks propose one maximally expressive gnn that follows this principle you can see the sum aggregator over there and you can actually start to make gnns stronger by looking at what are the failure cases of this wise file layman algorithm for example as you can see in the bottom right corner it cannot detect that you're in a closed triangle which gnns cannot do as well by corollary so augmenting the nodes with some randomized position features that will tell you where you are in the graph or counting interesting subgraphs is one way in which we can make them a bit stronger and we can also look at having sub graphs of k nodes and embedding them together which was exploited by one two three gnns and there are other very interesting avenues like directional graph nets or invariant and equivalent graphics of hagai maron which further elaborate on the idea of expressive graph neural networks now one final remark i'd like to make here is that things actually change quite a bit when we drop the discrete feature assumption so so far i've assumed that my features in the nodes were discrete but if my features are continuous which is very common in real world applications the proof of the injectivity of the some aggregator falls apart and here i've just given you a few examples where you can look at the two neighborhoods of node v and show that actually the sum aggregator and also many other aggregators will fail at distinguishing them particularly the example it's third from the left where both mean and minimizing and maximizing fail at distinguishing the two neighborhoods so now the question is what's the best aggregator in this case and uh in the principal neighborhood aggregation paper by gabriela corso luca caballero and others we actually proved that there isn't one in order to discriminate between neighborhoods of size n when the features are continuous you need at least that many aggregators to fully discriminate them and check out the paper in my opinion it has a really cool proof that relies on the famous borsa coulomb theorem and in the paper guided by this theorem we prepare we propose one particular empirically powerful combination of aggregators for general purpose g nets um finally i would like to remark very briefly that we use this blueprint of invariances and equivalences to describe gnns and to also cast many other research lines on graph representation learning into it and in fact it's remarkably powerful beyond graphs so if you have this local and equivariant layer that looks at neighborhoods an appropriate choice of activation functions and potentially maybe some pooling layers that make the structure more coarse and maybe at the end some global or invariant layer over the entire domain you can actually recover many standard architectures like cnns and transformers but besides that you can also recover a much more interesting class of geometric deep learning architectures that sit somewhere in the middle between convolutions and graphs and they may be broadly summarized as groups and gauges so groups might encompass some notions of rotational symmetry so if your signal is specified on a sphere it might need to satisfy certain symmetries gauges might relate to more generic manifolds like this human pose on the right hand side and alongside michael bronstein john bruno and taco cohen we are actively working on categorizing these four g's of geometric deep learning and i've just listed a few standard instantiations of appropriate domains neighborhood metrics and groups that you want to be invariant to and how they recover architectures such as cnns gnns deep sets and transformers but also many interesting architectures in between like spherical cnns or gauge equivalent mesh cnns before closing off i would like to just very quickly mention how did we get here like how did we come to this particular point and in fact you know processing data on graphs is so important that early forms of graph neural networks can be traced back to the early 1990s but they usually looked at very specific uh directed acyclic graph structures and they didn't like treat graphs as a first class citizen and kind of the first fully proper treatments of generic graph structure processing happened in the 2000s from two groups in italy the gnn framework from marco gorey franco scarcely and others and the neural network for graphs framework from alessia mckelly and this gen and model of glorious scarcely and others primarily use these recurrent style updates which have been updated for modern best practices by ugely's gated gnn layer however one completely independent line of research that deserves to be mentioned at the very end is computational chemistry here's a quote that i found on twitter in response to one of my threads chemistry disrupts machine learning not the other way around and it's a very important and concurrent area that develop gnns from computational chemistry obviously graphs are very relevant to chemistry because molecules can be naturally modeled as graphs and first gnn-like machine learning models of molecular properties arise also in the 1990s including models like camnet and the work of baskin and others in fact the molecular graph net paper that came out in 2005 already proposes many of the elements you'd commonly find in the modern uh message passing your owlette and the drive pushed well into the more later years including work on genens for molecular fingerprinting from david duvano and gns for quantum chemistry from justin gilmer finally recall the very first example i showed you for detecting anti antibiotics effectively chemistry is to this day a leading outlet for gnns and is a very important subfield to study if you want to learn more about graphnet development and implementations on that note i would very much like to thank you for listening and i hope you found this enjoyable and that the perspective was useful for you if you have any questions you can feel free to reach out to me offline either via email or all my social networks are listed on my website many thanks to will hamilton john bruno michael brownstein and taco cohen for their inspiring work that helped drive this slide deck and i'm now happy to take any questions thank you so much peter i think you're muted peter there are already a few questions in the chat would you like to pick up three or four that you think are more relevant to for your token it's a there's an interesting question from from guy i think better can you see this one so far you've spoken about learning repetition representations only from the graph however we often know something about the vertices outside of the graph context for example the semantics of words which appear in a knowledge graph what are some ways of incorporating this information this is a very good and very important question which sort of relates to kind of partial observability of the entire system and what i would say like one kind of classical way in which we would represent all this external information is you can just summarize it if you have no further assumptions about it you can just summarize it as one kind of uh global vertex which uh is connected to everything else in your graph so you know that something else exists you know it interacts with everything else you don't necessarily know how so kind of the most natural way to represent it is this sort of master node that interacts with everything within your graph now obviously there are more clever ways you can do if you actually know something about the structure or the relations of this hidden context but yeah without knowing any additional information about it i would say a masternode is probably like one standard way of tackling it okay that's great um i thought it might sort of cheekily take advantage of my position chairing to ask my own question um so you mentioned will hamilton's sort of excellent textbook a few times during the talk and he finishes the he concludes this book by highlighting two directions that he thinks are going to be important in the future and obviously you've just given this excellent talk on sort of where dnns have come from and i thought maybe you could comment on this will says we'll highlight latent graph inference and going beyond message passing as a formulation so what's your perspective on this where do you think where do you think things are going do you think there's another area um yeah what do you think yeah so thinking about future prospects is something that i regularly uh like to do and michael bronstein actually put out a very nice blog on what 2021 holds for graph machine learning where myself and a few others contributed a few thoughts on what are the relevant papers you should check out if you want to look at emerging trends in my opinion latent graph inference is definitely important so even without improving the basic blueprint of message passing we can still go a super long way if we choose the right edges very often the edges that are given to us in the data are actually not the best edges for solving the problem and actually sometimes we don't even have the edges so we have to make very crude heuristics to assume them so if we get better at techniques that automatically extract edges that can give us a huge boost in performance because it might shorten the path that signal needs to travel before it hits an important part of the graph even without improving the message passing mechanism itself that being said besides learning the graph structure you might also find it very useful to um to indeed like learn new forms of message passing which may not depend directly just on the features of the sender and the receiver and kind of narrowly combining them into representation we can look at more interesting functions that combine the sender and the receiver we can look at more interesting ways to define aggregation directions i particularly like this directional graph networks idea i think it's a very very cool future approach and yeah otherwise personally i'm very involved in using graphical networks for combinatorial optimization unfortunately i had almost no time to mention anything about this in the talk but i'll just say when you start using graph new networks to solve classical algorithmic problems you discover a whole new wealth of prescriptions on how to design them so i feel like if you want to look at where the bleeding edge is happening look no further than algorithmic reasoning and physical simulations cool that's great i think we had we had a few questions in the chat relating to this actually so uh maybe you can talk a little bit more about other areas so indigo asks uh whether there are any particular emerging fields um with prompting applications so it sounds like you've already highlighted one and then so i think related to that um you know i think your survey was obviously really interesting about you know where these things have been independently developed do you think there's sort of like anywhere else where these methods have been used maybe that hasn't been connected to the sort of like the the family of people looking at a gnn type methods um or if there's something that sort of recently become connected that you think is gonna be a very sort of fruitful area for people to work in i guess you could just expand on what you've just said yeah i guess i'll just very quickly highlight one area because there's a lot like i see graphs pop up in areas where i would never expect them necessarily that's because they really are such ubiquitous way of representing information one area that i particularly enjoy recently and i think ben you can also confirm this for me is particle physics i think that particle physicists are starting to discover this notion of symmetries and invariances in graph neural networks and they're finding it quite attractive to model uh important events especially unlike these high energy systems like the large hadron collider i think kyle cranmer had a lot of very interesting talks in the area that i would recommend if you want a brief intro but just very quickly saying i think that particle physics is going to be a very fruitful area of graph representation techniques yeah i think that's definitely going to be the case it's another one of these areas where the workshops just keep getting bigger every year um i'll just pick out some some more questions i think um there was a there was a question early on about um relating to attention and the questions about some tradition it's from vadim and it says uh some traditional methods uh often enforce um some kind of symmetric properties uh and they mentioned that the dot product attention is traditionally not symmetric um but it still works and they ask when when is it important to enforce symmetry when's it not needed but you can comment on that that's a that's a very important question and i would say that generally speaking with graphs generally and with this whole area of geometric learning the answer is unfortunately it depends so you need to look at the specifics of the problem that you're solving what are the kinds of invariances you would like to preserve and then design your model such that those invariances are as preserved as possible i think in algorithmic reasoning i see a lot of examples of this where we've recently concluded that if you really want the best possible extrapolation performance which is very important if you're learning a generic algorithm you need to design both your features and your systems so that what you need to learn is basically roughly a linear function so you know so you can get very stringent conditions on what your message passing should look like or what your feature should look like based on the requirements of your field so if extrapolation is very important this is what i would do if instead you care more about interpolation then i would just put a sum aggregator and kind of throw it at the maximally expressive architecture possible and it's usually going to work really well so yeah i guess it really depends unfortunately i cannot give a wide range of prescriptions but there's obviously a lot of papers dealing with these issues yeah of course um yeah thank you so i think i think that there are loads more questions i don't know how how long you're happy to keep answering questions for they just keep coming in um should we take some more yeah we can take uh we can stay until like 4 10 or so and answer a few more okay great um okay let's have a look so i know there was a question from emma who is asking about whether augmenting with node position uh whether this breaks permutation invariants yes exactly this breaks permutation variance if you explicitly specify a node position as a feature and this is actually exactly the approach that rpgn is used which is one of the methods that i've cited and the long and short of it is you need to be careful to kind of break that well to fix that breakage that you've just induced and what they do in that paper is theoretically what they do is they actually aggregate their prediction over all the possible permutations of the nodes now of course this is a k factorial kind of thing and you cannot actually compute this but they've shown that in practice if you just run it on a few randomized permutations and you average the results you get performance which actually converges to the actual performance if you use all the permutations so like there are ways to both theoretically and empirically go around that problem but yes definitely introducing these features does violate uh permutation variance and you have to be careful about that okay cool um so there's a question from from pablo um about incorporating sort of higher order um things like higher order simplicities um i think this is quite hot topic for going beyond message passing um do you have any generally thoughts about this um so things like uh incorporating information about you know faces with you know in higher high dimensional cells um yeah this is a very promising approach i'm seeing it uh not only in like computational chemistry is where i've seen most of it where you can kind of naturally figure out parts of a molecule like you know motifs or functional groups and this like representing them explicitly and assigning them explicit feature vectors is not only a way in which you can increase the representational power of your model but also it can help you even generate novel uh molecular structures more easily because you start by generating this higher order blueprint and then the lower order one so definitely it comes comes up a lot when hierarchy is necessary i've seen it also recently in these like relational inference approaches where you not only reason about the objects at the bottom but you can also think about the wider classes of objects or clusters of objects moving together and generally the more of these symmetries on higher orders that you can bake into your model and not make your model learn it the model is going to have an easier time so generally i'm very excited about those approaches and they're already showing quite some promise in uh computational chemistry approaches for sure yeah definitely um okay so we've got another question that's uh from zacharias uh asking about uh in standard cnn's we have we have some kind of course tonight we have down some plane um he's asking about whether there'll be principal ways of doing this obviously this scenario that has been explored within uh geometry deep learning um but they're asking if there's any sort of principle ways of doing this yeah so coarsening is something that we're actually working within our write-up to try to categorize it as well as possible but for now there's been quite a wide family of approaches proposed for graph for generic graph structures which seems to work well in various uh in various settings so in my opinion currently the most promise comes from actually topologically analyzing the graph structure like those are the kinds of approaches that i think are most robust there's obviously approaches that look at just the features and kind of try to soft cluster them to course in the graph but i feel like uh currently or at least with the benchmarks we have right now in graph classification we cannot quite uh make a cutting edge for those models as opposed to just running a simple graph model and aggregating all the vertices at the end right so i would say that currently the most promising approach if you want to kind of principally course in a graph is to look at topological uh methods of doing that like drag class min cut pooling click pulling and these kinds of things are the approaches that i would highlight there but i believe that sometime in the future when we have better data and a bit more principled methods we should get to a point of being able to more principally course and graphs based on features as well yeah i think it's i think it's definitely really exciting so we had a question from andre uh i think this is from sort of quite early in the talk asking about if transformers are dnns um why don't we just directly use genens and nlp and what are the disadvantages there so i mean okay i'll give i'll answer this in two ways the first of all the most generic gnm that you might have is this message passing genetics so you could try to go further from attention and actually compute messages from everywhere to every other word i believe that it's just that trade-off wise this obviously gives you an expense in terms of computational cost and representational cost and maybe it doesn't justify the trade-off maybe transformers are just so easy to scale up that you don't need to worry about the special case but i would also like to remark that recently in nlp there's a booming body of literature trying to make more efficient version of transformers that don't attend over all the words pairs but instead they choose like this locally sensitive hashes or something like that you know reformer performer all these different formers and uh at this point when you apply something like this on sentential input i mean you're basically running a gnn at this point so i that would be my answer to this question i think that everybody who applies a transformer is applying in gnn there's not really a distinction there that i would make yeah i think i'd agree yeah perhaps the better question is uh when do we expect to just have transformers be the only genome that we're using um okay so another one was um from luger who asks uh do you see have you seen um i guess this would be the last question um have you seen any exciting recent research lines on continuously evolving graphs um such as social networks or uh abstract syntax trees this is yes i think this is a very exciting line of research i mean my work on algorithmic reasoning is also dynamically evolving because as the algorithm executes as a simulation runs state updates on the graph at all times but uh that's a very specific class of graphs known as spaceship temporal graphs where the graph structure is always fixed and you just basically have a time series in every node and arguably there's a lot of research going on there very exciting for traffic forecasting and so on but i think that it's a very special case of a more exciting area called dynamic graphs where edges can arbitrarily be added and removed and features arbitrarily kind of interpolated extrapolated as you go along and on those lines i know of two models that seem very exciting one is the temporal graph attention network and the other one is the temporal graph network from from twitter so those two i'm aware of uh try to do a really principled attack at this class of this class of graphs i think you know it's we're still early stages there's going to be a lot more interesting work especially as we gather more principal data sets data sets are always the issue but those two i would highlight if you want to like really get started on dynamic graph representation learning i think it's a very exciting area um i think we have time maybe for one more question uh yeah sure so um i mean did you see any questions that you're particularly interested in i think there's there's loads of things um let me see let me see something maybe we won't talk to you yeah there's there's a lot of very exciting questions here by the way if you would like to see me because zoom is probably going to drop these questions after we're done if you'd like to see answers to some of these questions please like i've put a twitter thread on my twitter profile you can kind of send the question in there um okay and i'll be happy to answer it afterwards so okay let's uh let's answer uh the question from joao which talks about an area that i used to work on and i haven't had a chance to i haven't had a chance to talk about it in this talk unfortunately like you mentioned a work that combines some ideas from burke with gnns do you think pre-training will become as relevant in the graph domain as it is in other areas of deep learning uh my answer to that is an unequivocal yes i think it's already a big area it's just that most of these applications remain hidden from you because companies are applying them to get efficient graph embeddings but basically in many like social networks of interest you don't necessarily know what the task of interest is going to be at the time of specifying the graph so it's very useful very cool computationally if it's computationally very hard to run a gnn in production so it's much easier if you can use a gnn to kind of bootstrap good features using these unsupervisor self-supervised losses and then just use a simple mlp to classify amazon recently put out this peak companion paper which illustrates this very nicely they said we cannot use a gnn to like online serve queries of people buying products so we're going to use a gnn on a product graph to bootstrap the features and then we're going to use an mlp in production so i think it's a very important area that probably many companies are already doing it's just a question of how much they're talking about it and in that area you know i worked on methods like dji and the recently we put out a paper called bootstrap representation learning on graphs which i think is a very uh exciting addition to the family that's attractive because it doesn't require any negative sampling and yeah just generally i think there's going to be a lot more work in this area that needs to be done before we're really really competitive on all kinds of structural and kind of the main scenarios but yeah without a doubt i think it's already very important and pre-training and embedding learning on graph nets is going to become super impactful cool well um i mean there's still there's still like tons of questions but i think um people can just go and get onto your uh twitter um probably ask them that i i've actually been dismissing a lot of the questions that we've been answering which i think i'll try and add those back into the thing and then hopefully they're in the recording um yeah that sounds good so i'd like to thank you all once again for sticking around for like 15 more minutes i see there's still quite a lot of you and i see i know a lot of you so thank you so much for showing up um i hope you enjoyed the talk i hope you found the perspective useful if you have any comments on how it was presented anything you'd like to see done differently basically how how did you respond to this talk in particular i would be very much interested to hear because like after iterating on how to present graph representation learning for many years i've sort of converged to this particular direction and kind of i'd hope that it that it's as attractive to others as as it was attracted to me so yeah please let me know and thank you so much once again uh most appreciated and thank you ben for sharing the session and asking the questions well yeah i mean thanks thanks for an excellent talk um and yeah a great quick question session uh you really got grilled i think [Laughter] cool cool all right so take care everybody stay safe and well i hope to see you in person at whenever conferences become physical again thank you so much