Scientist Stories: Michael Bronstein, Deep Learning on Graphs

Good morning, everyone. Welcome to the Joint Data Science Seminar and Heidelberg AI event. It's my great pleasure to welcome Michael Bronstein today. He's a professor at Imperial College London and as you may know, one of the world's leading experts on graph neural networks. He has received his PhD with distinction from the Israel Institute of Technology. And then before joining the Department of Computing at Imperial, He has served as a professor at USI Lugano, Switzerland, and also held visiting positions at Stanford, Harvard, MIT, TUM, and Tel Aviv University. His track record is so intimidating. 5 ERC grants, more than 30 patents, H-index of 63, 2 Google Faculty Research Awards, 2 Amazon Machine Learning Research Awards, Facebook Computational Social Science Award, Royal Academy of Engineering Silver Medal, just to name a few. I saw a great keynote by Michael at MIDDLE 2019. This eventually led to this invitation here today. I'm also following him on Twitter, and what I like is that he also sometimes shares quite some sense of humor. So I'm really looking forward to his talk today, and with this I would like to hand over to him. The questions later will be handled by Paul Jäger, so please use your respective chats.

Thank you, thank you very much, Lena. Really very, very, very, very nice introduction. So it was really— it's, it's really a pleasure for me to be here. So I don't know if you can see the slides. Yeah, so thanks a lot again. Thanks for joining and thanks for the invitation. Today I would like to talk about deep learning on graphs, or maybe more generally what we call geometric deep learning, and a little bit overview of where these methods come from, what are the current challenges, and what I believe to be the next steps in this field. So maybe before we dive into deep learning or geometric deep learning, let's take a step back and look at the important concept that is important not only in deep learning but in machine learning in general, and this is the notion of inductive bias. So if we take a very simple neural network such as perceptron, which is probably almost 70 years old, basically what it does, it takes an input, weights it by some set of learnable weights, and then passes it through an activation function. Now, this is a very simple neural network, and it was criticized for being unable to represent certain functions such as XOR. But if you concatenate two such neural networks, basically what is called one hidden layer, you're able to represent step functions. The moment you are able to represent step functions, you can approximate any continuous function to any desired accuracy. This is what we call universal approximation property. It was proven in the late '80s, and in a sense, it's a very good piece of news. Basically, we can represent anything we want, more or less. The problem, of course, that this is a very weak inductive bias. So when we try to apply these simple neural networks to real-world high-dimensional data such as images, they tend to fail miserably. And this was one of the reasons for the so-called AI winter that happened probably around the '70s or even before. So let me show you an example. So this is probably one of the simplest problems in computer vision, the problem of digit classification. So we see here an image and we want to say that this is digit 3. So how do we— can do it? We just stack this image into a vector of pixels and feed it into such a neural network. The problem happens when we allow for the images to undergo some transformations. So the simplest transformation is just the position of the digit. So if I shift just by 1 pixel this digit 3, the input into the neural network will be very different. And because the neural network is completely unaware of the geometry of the structure of the image, it will have a hard time to say or to learn that this is the same digit 3. So what we call shift invariance, the property that we want the outputs to be independent of the input, now has to be learned from the data. And because the data is high-dimensional, we need very complex architectures with a lot of parameters. And training them is really a nightmare. So in practice, it never really works. So what happened in computer vision is actually the ideas that made into working architectures of artificial neural networks came from the domain of neuroscience. The first studies of the visual cortex, such as the seminal work of Hubel and Wiesel, and these ideas of basically local receptive fields were first implemented by Fukushima in the Neocognitron in 1980, and then in a more rigorous formalized way in the classical work of Yann LeCun and co-authors, what we nowadays call convolutional neural networks. So basically, the idea of convolutional neural networks— we'll talk about it in depth— is to take advantage of self-similar structures in images at different positions and different scales. And it boils down to having local operations with shared weights that are shift-equivalent. And then shift invariance is achieved by means of pooling, or at least approximately. So in terms of computation, the nice property of convolutional neural networks is that they have a fixed number of parameters independent of the input size. So no matter how big the image is, we still have a fixed number of parameters. And the complexity is linear, at least per layer, basically applying such filters. Again, we'll talk about it later in a few minutes. And this happened to be extremely nicely parallelizable and mappable to single input multiple data, or SIMD, architectures such as GPUs. And this is what really made the breakthrough in computer vision about a decade ago. So if we look at these architectures from the standpoint of inductive biases, we see that the success of neural networks in computer vision was from the choice of the right inductive bias. Basically, this abandoning of the general universal approximation architectures towards something that has a built-in invariance that is suitable for the problem in hand. And these can be generalized. So instead of shift, we can generalize these architectures to groups. There are several works relatively recently, in particular the works from TacoCoin and Max Welling that can generalize, for example, CNNs to rotations and other group operations. But let me show you another type of data. So this is a molecule, and if you are curious, this is a molecule of caffeine. This is something that I, like many of you probably, are addicted to. So this is a graph. This is a very different kind of data, right? Here atoms are represented as nodes and the edges represent chemical bonds. And let's say that we want to predict some property of this molecule. Let's say the atomization energy. So this is a very, very standard and very important problem in, let's say, drug design. So you have a molecule, a drug candidate, and you want to predict how it will behave in a certain way. What will be its chemical and physical properties. So it is essential and crucial problem in computational chemistry. How can we do it now? Basically, we can again represent it as a vector of, let's say, features of the nodes of this graph and feed it into a neural network. The problem though is that now we have many more degrees of freedom because we don't really have a canonical way of ordering our nodes in a graph. If an image, at least we have some raster scan order so we can column or row stack the image. Here we can permute this representation in any way. And it appears that graphs are actually a very prominent type of data. So we see them, probably the most important example are social networks, where graphs represent relations and interactions between different users, such as on Facebook or on Twitter. But we also find graphs representing different biological interaction networks, what is called interactomes. They are also used maybe with a little bit more structure in the form of triangular meshes, in computer graphics and computer vision problems, functional networks in brain imaging, and so on and so forth. So graphs are really very ubiquitous and universal models for systems of relations and interactions. So what we call geometric deep learning, actually the term comes— well, Lena mentioned my ERC grant. So when I was writing the proposal for my consolidator grant, I think back in 2015 or something like this. I was interested in generalizing deep learning to geometric data, basically some form of geometric biases. And then we wrote a paper with, with João Bruno, Yann LeCun, Arthur Schlamann, and Gerwander Kainz, where we tried to bring together some disparate works that existed at that time and didn't really have anything in common. So we call this geometric deep learning. And you may encounter other terms as well, such as relational inductive biases or graph representation learning or graph neural networks, which is a particular implementation of these ideas. Now, the prototypical objects I would like to consider today are graphs and manifolds. So from some standpoint, let's say, of a classical mathematician, there is nothing less similar than graphs and manifolds. Right? People studying them even sit in different departments or on different floors of the same building, go to different conferences, don't talk to each other, and maybe even quietly hate each other. But I hope that I will convince you that at least from some standpoint, these objects have certain similarities. And I will primarily focus on graphs today. I will show towards the end, if I have time, how these ideas can be generalized into a broader range of objects that we call the four— 4G of geometric deep learning. So if we look at the difference or similarity between images and graphs, one of the immediate things to observe is that in an image, we have very regular structure. If I take a pixel and I open a window around it, I always have a fixed number of neighbors. Not only that the number of neighbors is fixed, they also come in some fixed order. On graphs, we have a very different situation. Not only that the number of neighbors is different, and social networks are maybe a good example. There are very popular users that have have millions of followers and normal mortal commons like myself, which have maybe a few thousands. But also, we don't have a canonical way of ordering the neighbors. And as a result, the kind of invariance that we will be getting in these problems will be very different. So the questions I would like to address today is how to generalize the building blocks of convolutional neural networks or deep learning pipelines in general to graphs. One of them is how to define something similar to convolution. Another one is how to do pooling and how to do all these computations efficiently. So let me start with convolution, and again, allow me to take a step back and basically question where the convolution operations come from. So if you look at the convolutional layer in a traditional CNN neural network, essentially it is wired in a sparse way. So each output receives inputs from just a signal from a few inputs, right? So in this case, it's just 3 inputs that are aggregated. The second thing that is also special is that the weights with which we aggregate these inputs are shared. They are always the same. So if you look at the matrix of weights that maps from the inputs to the output, it has this special multi-diagonal structure, right, where we have multiple diagonals and the weights are always the same on the diagonal. So these matrices have a special name. Basically, they are formed by taking a vector and shifting it by one position with some boundary conditions. So in this case, it's convenient to think of periodic boundary conditions. So it's shift with wraparound. This is called a circulant matrix. And convolution can be identified with circulant matrix. So it's a one-to-one representation. Now, what do we know about circulant matrices? One of them is that circulant matrices commute. So you know from basic courses in linear algebra that matrix multiplication is non-commutative, so AB usually doesn't equal BA. For circulant matrices, this is a special case. They commute, and in particular, they commute with a special kind of circulant matrix, which is the shift operator. It's a matrix with a shifted identity matrix which shifts the vector by one position. Now, this is a property that very often is called shift invariance. The more correct term is shift equivariance. It means that we can first shift the signal, then convolve it, or vice versa. The result will be the same. Now, what else do we know about commuting matrices? We know that they are jointly diagonalizable. In this case, it means that we will have the same eigenvectors.. And as a result, we can pick one, one of the circulant matrices and look at its eigenvectors. We know that all the rest of the matrices will have the same eigenvectors. And it's convenient to look at the shift operator, and what we find is that its eigenvectors form the classical Fourier basis. These are the complex exponentials. So we sometimes say that convolution or circulant matrices are diagonalized by the discrete Fourier transform. Okay, so this is how it looks like. Now, different circular matrices have different eigenvalues. They have the same eigenvectors but different eigenvalues. The missing piece of this picture is that the eigenvalues actually are given by the Fourier transform of this vector w that forms the circulant matrix. So here we have this duality, basically two ways of implementing convolution. We can implement it in the spatial domain as product by circulant matrix, or in the frequency domain by first applying the Fourier transform. Then, because it diagonalizes convolution, we have element-wise product or product with the diagonal matrix, and then the inverse Fourier transform. And the two operations will result in the same, in the same output. So this is what signal processing people call the convolution theorem. Okay, so let me recap basically what we know, and I hope I am not saying anything new for you. You've seen this probably in this way or another. So convolution in spatial domain is a circulant matrix. You can think of it as local aggregation on adjacent nodes with shared parameters, and this structure comes from the underlying grid structure. Now we also see that circulant matrices are diagonalized by the DFT, which are eigenvectors of the shift, and therefore we can implement convolution in the frequency domain by first applying DFT, then element-wise product, then inverse DFT. And the complexity of computing it in the spatial domain, if the filter is small, is order of n. And in the frequency domain is n log n using fast Fourier transform algorithm, where for practical purposes, n log n is almost as good as order of n. So now we go from grids to graphs. And graphs in general, we can think of them as a collection of nodes and edges. So edges are ordered pairs of nodes if the graph is directed, or unordered pairs of nodes if the graph is undirected. So we can talk about neighbors, basically all the nodes that are connected by edges to a given node, and the degree of the node is the size of this neighborhood. We are interested in attributed graphs, so we can attach d-dimensional features to our nodes. We can also attach features to the edges in the same way, and a particular setting of it is a weighted graph where we have some, let's say, non-negative weights on the edges. So the structure of the graph can be represented by what is called the adjacency matrix. So it's a matrix which has non-zero values at positions which correspond to edges and zero elsewhere. And we know that for undirected graphs, the adjacency matrix is symmetric. Now, another important construction is what is called the Laplacian operator. So the Laplacian operator, what it does, it subtracts from the feature at the node i the weighted average of the features at the neighbor nodes. And you can think of it as a kind of local difference operator. So how am I different from my neighborhood? And you can represent it also as a matrix-vector product. The Laplacian can be represented by this sparse matrix that is given by the degree matrix and the adjacency matrix. You can use the Laplacian as a way of measuring the smoothness of a signal. Basically, how different a node is from its neighborhood is a way of telling how smooth the signal is on the nodes of the graph. This is what physicists sometimes call the Dirichlet energy of a signal, and it's given in the— as a quadratic form with respect to the Laplacian. So I should say that Laplacian is a very general construction. You can define it on a lot of different objects. You can define it on manifolds. In differential geometry, it's called the Laplace-Beltrami operator. You can discretize the Laplace-Beltrami operator on meshes. So this is what people in computer graphics like calling the cotangent Laplacian. And you can even define it on metric spaces. And for us, it will be primarily of interest how to define it on graphs. Okay, so what would be the analogy of convolution on graphs then, now when we have all these notions? And we've seen that there are two approaches. We can define it in the spatial domain as local aggregation with shared parameters, or we can define it using a generalization of the Fourier transform, which we call the graph Fourier transform. Okay, so let me start with this spectral formulation of the graph convolution first. Now, if I take a step back again and go back to the grid, you can think of a grid as what is called the ring graph, where each node is attached by an edge to the subsequent one, then we have periodic boundary conditions. So the first node is attached to the nth node. And if you look at the adjacency matrix of this graph, surprise, surprise, it looks exactly like the shift operator that we've seen before, right? So the idea of generalizing graph Fourier transform is to use the eigenvectors of the adjacency matrix or the graph Laplacian as the analogy of the Fourier transform. And the two are equivalent on grids, right, because they are all circulant matrices, so they are jointly diagonalizable. But on graphs, they are slightly different, and you will encounter different methods in the literature that either use the adjacency matrix or the graph laplacian. So for undirected graphs, what is nice is that these matrices are symmetric, so they have orthogonal eigenvectors. For directed graphs, the formulation is slightly more elaborate, so allow me not to go into details, and I invite you to check the references that appear here at the bottom. So this is how the Fourier basis looks like for the traditional ring graph, so that's the classical sines and cosines. And this is how eigenvectors look like on the general graph. So this is a road network, I think, of the state of Minnesota in the US. So here the red colors represent positive values in the eigenvectors and the blue colors represent negative values. And the eigenvalues can be thought of as the corresponding frequencies. So this gives us a completely straightforward way of applying convolution-like operations. So in order to compute convolution of x with w, we first apply the graph Fourier transform, right? We multiply our signal x by the graph Laplacian eigenvectors. So this is encoded by the matrix phi. Then we apply the filter by diagonal matrix multiplication, element-wise product, and then we apply the inverse Fourier transform. Okay, so, so far it looks exactly the same. Now the complexity unfortunately is significantly different. So phi is a dense matrix, so dense matrix multiplication by a vector costs us order of n squared, uh, because we don't have fast Fourier algorithms on graphs that use the redundancy of the classical Fourier transform. And this is just part of the problem. Computing these eigenvectors for a graph is a complexity that is roughly order of n³, probably a little bit less. Now, the application of the filter is still linear, and the inverse Fourier transform is quadratic as well. So here we are at a big disadvantage compared to the, to the number of operations that is required in the classical case, which is order of n, or worst case n log n. The number of parameters is also problematic. Here we have order of n, so these are the spectral coefficients of the filter, the diagonal matrix that we see here, as opposed to order of 1 that we had before. We also have a few nasty things, like we don't have spatial localization of the filters that we had on grids. The filters are isotropic, so they, they don't have a notion of direction. I will talk about it in a second. And probably the worst case is that the filters are dependent on the basis, and as a result, they do not generalize across domains. So I cannot compute a set of filters for one graph and then apply it to another. Let me show you an example of what I mean by this. So here we have a graph, or in this case it's a mesh. I have some signal on this graph. Let's say that I apply some filter, so that does edge detection for these red blobs. So I do it in the frequency domain, I do Fourier transform, diagonal matrix multiplication by the spectral coefficients of the filter, and then the inverse Fourier transform. Now I will slightly deform this graph by moving the horse a little bit. As a result, the Laplacian will change a little bit, the eigenvectors will change, actually quite significantly, especially at high frequencies. If I keep the filter coefficient the same, I will get a completely different result. So basically, it is not stable under perturbation. It doesn't generalize across even very similar domains. Now, I mentioned the problem of isotropic filters, and this comes from the fact that on grids we have canonical order of pixels, right? I can always talk about pixel to the left, pixel to the right, so I can give them some, some way of ordering them. On graphs, on the other hand, I can order my neighbors in arbitrary way, and as a result, we have local permutation environments. So there are no directions on graphs, and in fact, if you think of the Laplacian, what it does, it averages the neighbors. So it's a permutation rotation invariant operation. So rotation invariance means that we have isotropic filters. If I visualize them in the plane on a grid, they will look like concentric circles. I should say that on meshes or discrete manifolds, the situation is more optimistic because indeed here we have some ambiguity. I can choose, for example, the first vertex in an arbitrary manner, but once I did it, because manifolds are locally Euclidean, I can order the rest of the neighbors, let's say, in clockwise direction. So instead of permutation ambiguity, here we have rotation ambiguity. We have way more structure on meshes or on manifolds, and as a result, we can apply anisotropic filters. So let us again take a step back and try to look at the filtering process slightly differently. So we can think of it as a kind of matrix function that is applied to our matrix. And if we interpret the eigenvalues as frequencies, this matrix function P, which is a scalar function, can be thought of as a spectral transfer function, so as a filter. And if we make it parametric with fixed number of parameters, we solve the problem of number of parameters depending on the number of vertices of the graph. If we can express this function in terms of simple matrix operations, we can completely avoid the explicit computation of phi. Basically, we can write it as, for example, products of Laplacians or powers of Laplacians and so on. It is possible in this case to guarantee stability under graph perturbations, so we solve the problem of generalization across domains, and it is also possible to guarantee some form of localization, either compact support or exponential decay of the filter. So the simplest choice of such function is a polynomial, And here we have a fixed number of parameters, which are the coefficients of this polynomial. And we can, when we apply it to the Laplacian, basically we take just the p powers of the Laplacian. And because Laplacian is usually sparse, it is roughly order of n, right? Or more correctly, order of the number of edges in the graph. So you can see basically how this matrix looks like. It looks like it is sparse. Now, another thing to see is that Laplacian is a local operator. It affects only the neighbors of the So the pth power of the Laplacian affects neighbors p times removed. So the filters, as a result, will be localized to p hops on the graph. And as I mentioned, we can show generalization across different graphs. And basically, this approach, even though it comes from spectral motivation, it can be applied to any other operators. It can be applied to adjacency matrices, actually, which do not necessarily need to be symmetric because we don't require here any explicit eigen decomposition of this matrix. So we, we are not counting on orthogonal eigenvectors. So that was spectral graph convolution. And let us talk about the spatial view, right? And again, we've seen this analogy between the adjacency matrix and the shift operator. So another way of looking at convolution is actually seeing it as a weighted combination of the powers of the shift operator, right? So we've seen this multi-diagonal, uh, uh, circulant matrix. We can just decompose it into, uh, shifted diagonal matrices, right, with different weights that I denote here by, by w. And basically what we can think of, uh, of our convolution is nothing else but the same polynomial that we've seen before. So this distinction that in some references is made between spectral and spatial methods for deep learning on graphs is actually completely artificial. You see that they're completely the same. There is a very strong analogy between the spatial and— or duality between the spatial and the spectral formulation, same way as we have it in the classical case, right, that they're completely interchangeable. So here as well, this is what you see. Now, a slightly more general way of thinking of it, if we have d-dimensional features on the nodes of the graph, we can arrange them into a matrix that is n by d. n is the number of nodes and d is the dimension. And each row in this matrix corresponds to a feature vector that is attached to a node. Here is in red, for example, the features of node number 6. So to these matrix, we can do two things. We can first of all apply some shared node-wise transformation that is applied to the features at each node independently, and it is shared parameters. So in the simplest, in the simplest case, it is just multiplication by a matrix. So it's linear transformation, it's multiplying our feature matrix from the right. And we can also do diffusion, so we can aggregate information from our neighbors by multiplying this matrix from the left by either the adjacency matrix or the Laplacian or anything you want, right? And this is called graph convolutional networks. So this is work of Kiepfer and Welling that basically is a particular setting of the previous polynomial filter that I showed. And this is probably the simplest architecture that you can think of. For convolution-like operations on graphs. So you do, for example, this node-wise transformation diffusion, and then you apply some non-linearity. And if you want, for example, to do node-wise classification on a graph, you can do, let's say, 2 layers of such convolution and then softmax that will produce the binary output. Okay, so returning to the analogy between images and graphs, We've seen that we can define an analogy of convergence. So this is exchange of information, basically this linear aggregation from the neighbors, which is a form of message passing. Instead of local window, we have a one-hop neighborhood. We don't have constant number of neighbors. The number of neighbors is different, and we cannot order them canonically. So instead of shift invariance, we have permutation invariance. The good news is that we have linear complexity. We have a way of doing these operations with linear complexity. So let me say a few words about pooling. Basically, in images, pooling is just coarsening the grid and aggregating information in adjacent pixels by some shift invariant— sorry, permutation invariant operation. Usually it's maximum or average. So on graphs, we actually have many ways of doing it. It's a way of coarsening the graph. It can be done, for example, by collapsing pairs of nodes and aggregating the features in them. Basically, this way we create a hierarchy of domains and corresponding feature vectors on them. And we can interleave convolutional pooling layers. The special thing in graphs is that we can actually learn the way that we do the pooling. So what we've seen so far was a very simple linear convolution on graphs, right? So we can think of it as a matrix that is applied to our nodes. Node-wise features. And this matrix, importantly, is independent of X itself, of the features. Now we can do something more complicated. We can take this matrix and still make it a linear aggregation, but now the weights themselves with which we aggregate can depend on the features themselves. So the first architecture of this kind was done by my PhD student Federico Monti. And we call it MONET, from Mixture Model Networks. Another version of this is the Graph Attention Network, where the aggregation coefficients are computed as attention weights in the graph for the one-hop neighborhood. And finally, we can make this aggregation a nonlinear operator that depends on the features, maybe not only node features but also the edge features, And this is what is typically referred to as message-passing neural networks. So we did work in computer graphics community on point clouds where we call this also edge convolution. So let's look at this general form of message-passing neural network. So it has two basic operations. So we can aggregate the nodes, the features from the neighbor nodes, and we can update the node itself., right? So we have a node i, we take a look at all the neighbors, we aggregate the information from them by some permutation-invariant function, usually it's max, sum, or mean, and then we have a function that updates the feature itself. Now the question is, what is the right aggregation operation? And actually it appears to be quite important. So if I look at this neighborhood, so in this case the color represents different features, so the black node is xi, right, so my node that I'm trying to update. And here we have these two neighborhoods. One has two red features and one green feature. Another has one green feature and one red feature. So you see, by taking the maximum, I cannot disambiguate between these structures. On the other hand, if I take min, I am able to disambiguate between them. If, on the other hand, I look at these two structures on the right, we have 2 green nodes and 2 red nodes, so the mean will be the same. But this can be disambiguated by the sum. So the choice of the aggregation operation appears to be quite important. And it's probably appropriate to ask the question, how powerful are graph neural networks? And this question is not straightforward because unlike the traditional setting that we've seen, perceptrons, where we can talk about universal approximation property, it's not even clear how you define the expressive power of graph neural networks because they have different— they operate on different domains. So you can ask the question of basically whether they disambiguate within different graphs or whether they disambiguate between different functions on these. So a way, one way of formulating this problem is relating it to the question of graph isomorphism. So we say that graphs are isomorphic if there exists an edge-preserving bijective function between them. So in other words, if you look at their adjacency matrix, we can permute its rows and columns in a way that we get an adjacency matrix that is exactly the same as of another graph. So basically the graphs are the same up to the numbering of their nodes.

And the—

it is interesting that the question of testing whether the two graphs are isomorphic, we don't even know what is the theoretical complexity of it. So we, we know for sure that currently there is no known polynomial algorithm, but on the other hand, it's not NP-hard. So usually it's put in a special complexity class that is called GI complexity, graph isomorphism complexity. And this is a classical problem in graph theory. Actually, the first attempt, or the hope to have found a polynomial isomorphism test is due to Andrei Lehmann and Boris Weisfeller, two Soviet mathematicians that hoped that they have found a polynomial test algorithm. And it was actually disproved by counterexample a year later. And what this WL test, how it is called, does, it does a kind of color refinement. So by color, I mean a discrete label. So you start with a graph that is colored with the same color. And then what the WL test does, it looks at the neighborhood of a node and represents it as a multiset. So multiset is a set where the same element can be repeated multiple times. Basically, I look at the colors of all my neighbors and of myself, and I hash it using an injective function. And basically, you see here that, for example, two nodes with different connectivity, with different number of neighbors, will result in different colors. I define the color, I can do it again, and here I obtain another color. But if I do it again, I now see that the color remains the same. When the colors stop changing, we can just compute the histogram of different colors and this will be the descriptor of the graph. Now, given another graph, I can do the same thing and I get another descriptor. So if these two histograms for two different input graphs are different, we can say for sure the graphs are non-isomorphic. If the descriptors are the same, we can say only that they are possibly isomorphic, but not necessarily. So this is a necessary but insufficient condition. There are examples of very simple structures that evade the detection of the WL test. So for example, these pairs of graphs, one of them has triangles,, and another one doesn't. And nevertheless, from this simplistic color refinement standpoint, they look the same. So we say that in this case, the WL test fails. So the seminal work, actually two papers by Xu and Morris from 2019, showed that message passing is equivalent to color refinement for some choices of the aggregation function. Therefore, graph neural networks, or the message-passing type of graph neural networks, are at most as powerful as the WL test. Now, I should say that WL test, it's not a single test. There is an entire hierarchy of WL tests, what is called KWL tests, which are high-dimensional and they use k-tuples of nodes instead of just pairs of nodes or simple neighborhoods. They are non-local, they have high computational complexity, and there was a formulation of equivalent high-dimensional GNNs, in particular due to Hagai Maron from Weizmann Institute in Israel. The problem, of course, is that they are computationally expensive. So the 3WL equivalent GNN has a complexity of n squared in space and cube in complexity. So this makes this good in theory but completely impractical. So What we did with the work with my PhD student Georgios Bouritsas and a colleague from Twitter, Fabrizio Frasca, is what we call Graph Substraction Network, or GSN. Basically, we know that WLTST or message-passing neural networks cannot detect certain structures. So let's help them. Let's precompute these structures. Let's count them and provide them as features of the nodes. It is a kind of node encoding. So this is a positional or structural encoding. So there are several works that try to say that if I can disambiguate the nodes in the graph, then I can do better message passing, right? Because if I know, for example, who my neighbors are, maybe I will learn a different rule of how to aggregate from. So in the extreme case, this can be done in the form of random features, for example, that are completely unique. The problem with random features, there is no mechanism of how to repeatedly do random features for different graphs. So this might be a very expressive way, but it doesn't generalize well. So here we are doing structural encoding. So we are looking at how the structure of the local neighborhood of a node looks like. And this is done by counting substructures of size k, and then we pass this information as an extra feature in standard message passing. And the good thing is that the architecture of the neural network itself, the training and the inference, looks exactly like standard message passing. So it has linear complexity. There is this extra step of precomputation that in the worst case, it takes order of n to the power k, which is as bad as high-dimensional graph neural networks. But in practice, for many structures, we can count them more efficiently, or we can count them approximately by some randomized algorithms, some of which have performance bounds. Now, what do we gain in this way? What we gain in this way is that we are strictly more powerful than WL, at least with certain structures that are, let's say, any, anything more complex than star-shaped graphs. We can also have, uh, we can show that we are at least not less powerful than FreeWL, and this can be shown by counterexample. We can show an example of these strongly irregular graphs. One of them has, for example, 4 cliques, and another one just has only triangles. So this is probably undetectable by 3W-L test, but if we count these structures, we can disambiguate them using our GSN architecture. And these can be extended to higher-order graphs as well. Now, if we look at standard datasets, applications of graph neural networks, we know that in some cases, in some domains, that certain structures are more prominent and more informative. For example, in social networks, clicks tend to be a prominent structure that is important. In chemical datasets, for example, these are cycles. Okay? And if we use this as an inductive bias in our graph neural network, we can obtain significantly better results than previous approaches. And let me show you the result with a molecule. So here we are trying to predict some properties of molecular graphs by counting structures of circle structures, ring structures of size k. So we see that the error drops dramatically when we allow for structures of size 5 and 6. And in fact, these are very common ring structures in organic molecules. So the rings of size 6, for example, they're aromatic rings that also appear in molecules such as my favorite molecule of caffeine. And there are many examples where we can know a priori what kind of structures are important and informative. So in the remaining time, let me talk a little bit about what's next, what is still missing in this field. And I would say that I started working on geometric deep learning first, deep learning on manifolds and meshes and then on graphs. And I was expecting that something similar to what happened in computer vision will come to this field as well, a kind of revolution that will completely wipe out the existing methods. And unfortunately, this has not happened, so quite disappointingly. So we do now have graph neural networks everywhere, but You cannot really point to an application and say that this was completely transformed or revolutionized by these methods. And I think there are several reasons why this has not happened yet. One of them, one of the reasons for the success of convolutional neural networks in computer vision was the availability of large training sets. ImageNet, for example, was really what allowed this breakthrough. In 2012. We don't have yet anything similar in graph learning, so ImageNet for graphs. One of the reasons is that the problems of learning on graphs are much more varied. So we can talk about problems such as node classification, graph classification, edge prediction, and each of these problems requires different types of data and different datasets. Another problem is that large graphs are usually owned by companies just a handful of companies, and they are very reluctant to release this data publicly. One of the reasons that now we have draconian privacy laws such as the GDPR in Europe, which make it extremely hard to share these data publicly. So I should say that at Twitter, we organized the Raxys Challenge earlier this month where we released probably one of the largest datasets in the industry of interactions of Twitter users with tweets, about 150 million such interactions. And it was a headache how to release this dataset to be compliant with the GDPR legislation. So now there is an effort of Open Graph Benchmark, OGB, that is spearheaded by Yuri Leskovec from Stanford. And this is becoming the de facto standard for testing graph neural networks. So I hope that this will be the analogy of image for graphs. Second thing is software libraries. So this is something that was completely lacking just a couple of years ago. Now we do have professionally maintained libraries such as EGL or PyTorch Geometric. Second problem is efficiency and scalability. So many of the algorithms that you find in the literature, when you try to apply them in large-scale settings such as Facebook or Twitter graphs, they simply do not scale. Their complexity, the way that they access memory, the way that their algorithms are designed and structured make it prohibitively expensive and impossible. So it is relatively recently that the academic community has started looking at efficient and scalable graph neural network models. Another challenge is dynamic graphs. So many graphs, especially in social networks, they are actually not static. So they are not just a snapshot of the user relations or interactions. They change all the time. Good to think of them as a kind of stream of asynchronous events that form or change this graph. Another thing is that if you look at the majority of works in graph learning literature, they consider nodes and edges. So message passing mechanism is one example of this, but we know that in many complex networks, in biological networks, in social networks, it is actually higher-order structures that matter. We know that, for example, there are certain motifs or graphlets that are more prominent in nature, in biological or in social networks, than simple random graphs. So these kind of structures are not taken into account, and GSN is maybe a very simplistic, I would say even to some extent naive, approach to account for these structures. But probably we really want to go beyond the message passing mechanism and extend it to higher-order structures. Another interesting point is what I call latent graphs. So in many cases, we actually— we don't have the graph to start with that is given in the input. This was the assumption throughout this talk. I assume that somebody gives us the graph, and then we do some kind of diffusion on this graph. So in many cases, the graph is not given, or maybe it is noisy, or maybe it is known only partially. Or actually, in some cases, we see more and more works where we try to decouple the input graph from the computational graph that is used to do message passing and diffusion. And there are many reasons why you want to do it. One of them is what's called the information bottleneck, where you try to aggregate information from a lot of neighbors, you run into an oversquashing problem that you need to squeeze a lot of information into just a single feature vector. And there are missing links such as theoretical understanding, the expressive power of graph neural networks. There are many interesting works on this, how these expressive neural networks, how well they generalize, whether they are robust to adversarial attacks. So there are beautiful works, for example, from the group of Stefan Guhnemann at the Technical University of Munich that tries to adversarially attack graph neural networks and prove some certificates of robustness to such attacks, and so on and so forth. I would like to end with the last thing that was probably missing and what prevented the kind of revolution that happened in computer vision in this domain is the killer apps, right? So you can think that computer vision and maybe NLP and speech recognition were really the poster children, so to say, of deep learning. And what would be the kind of these killer apps for graphs? I should say that the community has really recently embraced graph neural networks. So if you look at the popularity of works on graph neural networks, so this is statistics from recent ICLR conference, that this is one of the most popular topics in the field currently. And it's not surprising because graphs, as I mentioned in the beginning, are really ubiquitous abstract models of systems of relations and interactions. So you can apply them practically everywhere. And I would argue that you can apply them if you look, let's say, at us as people very broadly. We can apply graphs to model different processes that govern us at all scales, from macro to nano, whether it's individual molecules, biomolecules that exist in our body, such as proteins or drugs, whether it's interactions between these molecules, interaction networks or interactomes, or maybe social graphs such as graphs of patients or interaction graphs such as Twitter or Facebook. Let me start with this application in social science. So everybody is now talking about fake news. So when irresponsible politicians tweet something on Twitter, then this story is picked up without being maybe fact-checked and becomes viral and spreads. This is what we call fake news, right? So how can we detect such fake news that are really becoming important and a real threat to our society? So this is what we try to do in our startup that I co-founded with my students. And we tried to develop a graph neural network algorithm that will classify fake news and distinguish them from non-fake news, whatever you— how you define it, from the way that these stories propagate on the social network, in this case on Twitter. And you can see here an example of how a piece of news spreads over Twitter, very similarly to propagation of infection in the society, such as the coronavirus. And our company was acquired by Twitter in 2019, so that's how I ended up at Twitter, where I direct the graph learning research in the London office. So at Twitter, one of the obvious things where these methods can be applied are recommender systems. So we can create graph embeddings where we represent nodes as some vectors in some high-dimensional space. And then, for example, we can try to build the graph back from these representations. So it's kind of autoencoder architecture for graphs. So these representations can be used to predict, for example, whom to follow or which content to suggest to a user. Another pretty cool field where graph neural networks are recently becoming prominent is high-energy physics or particle physics in particular, where what you see here is an example from the Large Hadron Collider, where a collision of two particles creates these jets of different particles that decay into each other and detected by these huge detectors. Of different types. And one of the main challenges is how to classify interesting events that happen in such colliders, because these events happen at the rate of millions per second and they generate petabytes of data. So you cannot store all this data, you need to discard it on the fly as these events happen. And crafting neural networks is probably the next step in doing it. And I was involved in a collaboration with the IceCube, a neutrino observatory where we try to apply graph neural networks to detect astrophysical neutrinos. Now, another application, and this is probably what I consider a killer app, is the problem in computational chemistry and design and development of drugs. So if you look at the space of, of all possible synthesizable molecules, it is extremely large, probably almost as large as the number of atoms in the universe. And on the other hand, the number of compounds that we can test experimentally in the clinic is extremely small. It is very expensive and takes a lot of time to test the drugs. So somehow we need to mitigate, to bridge this gap between the all the possible candidates and what can be tested experimentally. So this is done usually by simulation methods such as molecular dynamics or DFT, density functional theory, are used as a kind of virtual screening for drugs. So graph neural networks stand somewhere at the same level of accuracy as DFT, but several orders of magnitude faster. And this was already an old work by Justin Gilmer from DeepMind. Now they're way more sophisticated architectures, more accurate methods. And I should mention earlier this year, there was a publication in Cell where graph neural networks were used for virtual screening in detecting, discovering new class of antibiotics. That was a work by the group of Collins from MIT. Now, I myself had an excursion with colleagues from EPFL into this domain, fascinating domain of biology. And we were looking at using geometric deep learning methods to represent proteins and to see how they bind to each other. And you see here a very famous protein complex, what is called the programmed death ligand, or PD-1/PD-L1, that plays crucial role in cancer immunotherapy. This was recognized by the Nobel Prize in Medicine in 2018. So the way that it works, usually we have a mechanism that prevents our immune system, the T cells, from destroying destroying healthy tissues. And this comes in the form of these PD-1/PD-L1 proteins that are expressed on the healthy cells and they block the T cells. Now, some cancers tend to develop these proteins and as a result, they become immune to the normal functioning of the immune system. So the idea of immunotherapy is blocking one of these proteins and allow the immune system to do its job. And the key problem here is how to how to develop, how to design a binder, a molecule that will bind to this target. And usually these targets are difficult to be addressed by small molecules, so it's called undruggable. Basically, the interfaces do not have pockets, they tend to be flat. And that's where biological drugs that are based on proteins or peptides come into the play. So we want to design a protein that will bind to another protein. And this is what we did with geometric deep learning with Michael Brejers, Pablo Gainza, and Bruno Correa in Lausanne. And we had the luck to appear on the COVID of Nature Methods in the February issue. So taking ourselves to a higher level of abstraction, we can also think of drug molecules as the way that they interact with proteins. Proteins are really ubiquitous used as drug targets. But most of the drugs that we find in medical practice, they are not specific. So I think on average, a drug will typically bind to something like 50 different proteins. So as a result, because proteins interact with each other, we have about 20,000 proteins that are encoded in our gene, exist in our body, synthesized by our cells. They interact with each other. So if I disrupt one of them by basically binding a drug to them, then I can disrupt entire pathways, entire biological processes. And accounting for these network effects is extremely important. And that's what we do with— also we can do with graph-based methods. And what we try to do with collaborators from Imperial College with Kirill Beselkov is to find drug-like molecules in foods. And we developed a classifier that takes as input oncological drugs and tries to predict whether another molecule that, for example, comes from a plant is similar and has similar anti-cancer properties as FDA-approved drugs. And actually, it's not surprising because we know that many plants contain drug molecules. And actually, many immunotherapy or many cancer therapy drugs are originally derived from natural substances. And there are many, many reasons why this is the case. And basically using these methods, we were able to identify food ingredients that are rich with anti-cancer drug-like molecules. And we call this the Food Map. So you can find a lot of boring and actually simple and cheap foods such as carrots and cabbage and green tea So I think it goes without saying that it's a good idea to integrate this into your diet. I should say that take it with a word of caution because what we are not accounting for are interactions between different compounds. And this plays a crucial role because in foods we have hundreds or maybe thousands of such molecules. And the cool part of this project, of course, because food is cool and food is nice, and we are collaborating with a molecular chef that actually takes the molecules that we discovered in food and produces nice and both aesthetically and tasty dishes out of them. So I should say that, well, I think I'm running out of time. So one last example that I will show is combinatorial drug therapy. So talking about interactions within drugs, was a very interesting work from Malinka Zitnik from then at Stanford, now she's at Harvard, predicting adverse side effects of polypharmacy when people are administered multiple drugs at the same time. And some of these interactions can be negative, some of them actually can be synergistic. So I'm working with Mila, the group of Joshua Elkington in Canada, as well as from a startup, Relation Therapeutics, where we try to find drug repositioning and combinatorial drug therapies for COVID-19. If you think this is probably the most important cause nowadays, and it would be very exciting if graph neural networks are able to provide a solution for this important problem. So last problem that I would like to mention is application in computer vision and graphics. We can use graph neural networks on meshes and manifolds, both for analysis and synthesis of objects. So this is an example of markerless motion capture, basically virtual and augmented reality effects that you can do now on your phone. So this is an example of the kind of things that we can do. So here you can see an application to virtual avatars. So this was a work of my PhD student Dominique Coulon, in collaboration with the British startup Aerial AI, where this application runs in real time, or actually about 10 times faster than real time, on your iPhone. So let me draw this talk towards the end. I talked today primarily about graphs, a little bit about manifolds, but we can really think of the 4G of geometric deep learning. These are grids, groups, graphs, and gauges. And I think a good analogy is what is known in the history of mathematics as the Erlangen program of the mathematician Felix Klein, which provide a uniform, uh, unifying framework for different zoo of geometries that existed in the 19th century and was a fundamental insight in physics with the famous Noether theorem that actually showed that you can derive different conservation laws, such as conservation of energy or conservation of momentum, from the principles of symmetry or some invariance. So same thing probably is true for deep learning. So you can derive convolutional networks from the principle of shift invariance. You can generalize it to groups. So shifts are just one example. Of course, you can also apply it to rotations. In graphs, this will be permutation invariance.. And on manifolds, this is an example of a non-homogeneous space, similar to what— to the generalization of ideas of Klein by Élie Cartan and other geometers to non-homogeneous spaces and manifolds. So to conclude, I think graphs are very general abstractions, useful everywhere in a lot of practical problems, and What I showed today, graph neural networks in particular, are a way of capturing meaningful geometric inductive biases that are suitable for graph-structured data. It is really cross-disciplinary research, and at least in my career, I've had the luck to work with people that otherwise I would not even meet in the same conferences, whether it's protein engineers or particle physicists or clinicians or even the chef. And this is a very hot field in machine learning, so if for some reason you happen to be a PhD student, I think this is a good topic to work on nowadays. There are already several success stories and some first examples of industrial applications. But I think what is most important, that there are many, many interesting, profound, deep open questions that are still unsolved and wait to be addressed in this field. So last but not least, I would like to give credit to many of my wonderful colleagues and collaborators with whom I've had the honor to be working in the past years.

And thank you very much. All right. Thanks, Michael. Thanks for this excellent talk. This is Paul from Heidelberg AI. I really liked your thorough introduction. And so I'm going to be moderating the questions. Please post all your questions in the chat room so I can forward them to Michael now. And maybe let me start with one question. I particularly liked your introductory perspective on different inductive biases to motivate graph neural networks. And so I have a question. So I understand that if your input data has already this notion of a graph or it has features that you can interpret intuitively as a graph, it makes sense to give this inductive bias to the network. To facilitate learning. I saw some of your work on latent graph learning, particularly the one in with medical application where you have kind of like a— the way I understand it, of the standard patient classification problem where each patient has different features and you want to classify the patients, and you say let's just transform this input space into a latent space and then start picking the representation in this latent space and start applying our inductive bias here according to some thresholds and distances. And this is kind of counterintuitive to me. Like, if this representation space is already optimized towards the classification problem, why here? Why should it be helped here in this latent space to now explicitly hardcode any distances between representations?

Yeah, that would be my question. Yeah, so it's next Excellent question. I think you can have multiple perspectives on this problem of latent graphs. And one of them could be very, let's say, pragmatic computational considerations, such as what is the better graph to do message passing. I would say that I like the analogy to manifold learning techniques. And actually, I've recently written a blog post on Towards Data Science about this, basically manifold learning 2.0. So if you remember about 20 years ago, at least when I was a student, these are very popular approaches. Methods such as isomap or locally linear encoding or Laplace and eigenmaps and so on. So basically these were mostly used and still used, quite popular methods for data visualization. So it's nonlinear dimensionality reduction. Basically what the premise of these methods is that even though your data lives in a very high-dimensional space, the underlying structure is intrinsically low-dimensional. That's why it's called manifold learning. A good metaphor for it is that you have a low-dimensional manifold that is embedded in a very high-dimensional space, and then the data is somehow sampled from this manifold. So if you think of face images, for example, they might be million-dimensional, but actually the intrinsic dimension, the number of degrees of freedom that explains them, is very small. And the usual blueprint for these methods was you start with this set of, let's say, faces or digits or whatever. You represent its local structure, usually in the form of a graph, k-nearest neighbor graph. And then you try to find a low-dimensional representation. Basically, you embed this structure into low-dimensional space by preserving something. So in isomath, for example, you try to— you use multi-dimensional scaling techniques to preserve geodesic distances on this graph. And then you can apply machine learning, usually it was in the form of clustering, to basically detect whatever you want. Now, what was unsuccessful about these methods is that the process of constructing the graph and preserving some structure and doing the machine learning were completely decoupled. So you had to fine-tune a lot how you construct the graph, and then you had to massage the data into some representation where this graph makes sense. So what I'm claiming is that now with graph deep learning pipelines, you can put all these stages into a single end-to-end pipeline. So basically, you can create, you can learn task-specific optimal representation of the data where building this graph will make sense. And you mentioned the patient networks. Sometimes, actually, what we see is that the graph itself is more interesting than the downstream task. It can explain your problem. It can explain your data set. So for example, when you try to diagnose patients, let's say, from brain features, it is obvious for a doctor, for example, that certain structures in the brain of a 5-year-old child and a 90-year-old adult have very different interpretation. There are some processes that evolve with age, but what would be completely abnormal in a young person, let's say. Basically, the graph in this case somehow groups patients together. It is maybe a little bit naive way of representing similarities because this is mostly homophilic type of similarity. But still, I think it's an important step towards, in some sense, interpretable architectures.

I agree. Thanks. Cool. So I think Lena also has a question.

Yeah.

Am I— do you hear me?

Yes.

Yeah. Very impressive talk.

Many thanks.

I don't worry about your killer applications. I think once the data is there, you have enough killer applications. I was wondering, you mentioned your field is very cross-disciplinary and you certainly review a lot of papers and you advise collaborators, supervise students. What would you say are the most common and maybe even non-obvious pitfalls that people encounter when they start working on graph neural networks?

Yeah, good question. So I think probably as always in deep learning, the tendency to apply methods as black boxes without understanding it. I think unfortunately in graph learning, we don't really understand when and how these methods work, or maybe more importantly, when and how they fail. So I think this is really only the beginning of understanding. For example, the works on expressive power, they shed light on, for example, which structures at all you cannot detect. So it's hoped less to try to make, for example, these neural networks deeper because no matter how deep you go, you will not be able to count triangles, let's say. So once you have this knowledge, you will not even be trying some things in a futile way. And then of course, the question is how to make different architectures that can address these problems. So I would say this is probably the main pitfall. That probably still exists. Another pitfall is testing is lacking. We still see in this community people testing new architectures or graph neural networks on the CoRA dataset, which is a very small citation network. It's like the MNIST dataset. So everything works well on CoRA, and the performance on this dataset is not at all indicative of the real strengths or weaknesses of an architecture. So Now there is these big efforts to make more interesting datasets and benchmarks. And I think this is important progress in the field. I would say the third thing, and this is my personal favorite, and I don't have a convincing opinion on this, what paradoxically, well, it may be counter to what I was using in this talk, deep learning on graphs, actually most of the architectures are not deep learning. They have maybe 2 or 3 layers at most. And we actually see that depth is, in many cases, detrimental. And there are deep reasons why this happens in some cases. One of them, what I mentioned, is this information bottleneck. When you have applications where you depend on long-range interactions, such as in molecular graphs, the property of a molecule can depend on atoms at the very ends of a molecular graph that might be 20 hops away. And on the other hand, the graph tends— the number of neighbors tends to grow exponentially, such as in small world networks. Basically, you get into the situation when you have a lot of data that you need to squeeze into a single feature vector. This results in oversquashing. So how to break this bottleneck, to at least to understand whether it exists in your problem, is important. And that's why just blindly adding more layers sometimes doesn't work. And you see many papers that show that even with a lot of tricks, deeper neural networks produce worse results than shallower ones.

Thanks. All right, thanks. We have a question from Tim. I think this is coming from— or this could reflect thoughts that many people in the audience have coming from the imaging or computer vision side. So in computer vision, when we train an algorithm, we have different training samples, right? Different grids that we show to train on, and then we generalize to different grids at test time. So how does this work with graphs? Are we training on the same graph? Do we have different graphs in training? Do we generalize to different graphs or inside one graph? Can you maybe draw a little analogy here for the computer vision people?

Right, so I think it really depends on the application because in graphs there is a variety of applications. You can think of problems where the graph is fixed, let's say a social network, and you have a signal that changes in it, or at least approximately. You have applications such as classifying molecular graphs where the graphs are different. So I think in computer vision you can, at least some class of problems, I can say that you have a fixed grid and the signal on the grid varies. In graph problems, you can have both the signal and the domain different. So one of the challenges is how to make an architecture that can generalize across different graphs. And that's why, for example, I mentioned the positional encoding. So if you have a fixed graph, such as the PPI graph, the protein-to-protein interaction, so this is a fixed graph. So the proteins do not change from my body to your body. We have all the same proteins, at least, right? At least within the same species. Now, in this case, you can actually encode, you can enumerate the vertices and say this is protein X, this is protein Y. If it's, for example, a molecular graph, each node in this case is an atom, and of course they are very different if you are talking about different molecules. So the kind of methods that you will be using will be completely different. So in this case, for example, you want to use, you cannot use let's say, some unique features you want to use, maybe something similar to structural encoding. And the message passing algorithm needs to account for different number of nodes in the neighborhood and so on and so forth.

All right, and I guess then if you have a problem that is within one graph, then it's kind of like a semi-supervised setup where only some nodes are labeled and then you try to get labels for the unlabeled nodes.

At inference time. Right. So basically inductive and transductive settings. So in one case, basically when you do your training, you see all the graph, but you know only the labels of a few nodes. But the more interesting, the inductive setting. So this is the transductive setting. The inductive setting is when actually at test time there are new nodes that you have never seen before or new edges. Now, the semi-supervised or the self-supervised setting would be What I mentioned, for example, the graph, the node embeddings, where you try to embed the nodes of the graph in some vector space from which you can reconstruct the edges. So this is typically the problem of edge prediction that is used in recommender systems, where you try to suggest whom to follow, for example, on a social network.

All right, thanks. Then Tom is asking, most natural networks are sparse. Is this taken into account in a special way when performing deep learning on these graphs?

It is taken into account. And actually, when the networks are large, you must somehow sample. So really, one of the first algorithms for scalable architectures is GraphSAGE from Will Hamilton, Yuri Lester, and co-authors. Basically, SAGE stands for Sample and Aggregate. So it involves some kind of sampling of the neighborhood. So you are not You don't run into problems where you have a popular user on social networks such as Donald Trump with, I don't know, 50 million followers. So you don't want to aggregate from all these 50 million neighbors, so you will sample. And it appears that graph sampling actually improves the— not— so it should be used not only for computational reasons, but it actually improves performance. And there are several reasons why. One of them is the bottleneck problem. So Stefan Günnemann, that I mentioned before, also had a problem that diffusion helps graph learning. And what they were doing is rewiring the graph. So this is related to the problem of latent graphs and decoupling the input graph from the message passing graph.

All right, thanks.

Then Uldrich is asking, "Can you say more about graph coarsening pooling, especially learnable variations?" Yeah, so basically this is something that doesn't have analogy in computer vision because, well, there it's a grid and you just do max pooling typically. So the coarsening, you can think of it as— basically you can think of two branches of a graph neural network, right? So one produces the node features and another one produces the coarsening operator. So usually some sparse matrix that tells you that I want to aggregate information from this set of nodes. So this is produced by another graph neural network. What happens is that usually the signal from the downstream task is insufficient. So you need to add some auxiliary losses. And the methods differ in what auxiliary loss they use. There was, I think, the original paper on differentiable pooling, also from the group of Leskowitz, they used some entropy loss. The more recent works use something similar to graph cuts.

Thanks. Then Matthias is asking, what are your thoughts on graph GANs? What are the key differences in networks trained adversarially having CNNs GANS versus GCNs as core layers?

Good question. So I think in general, these generative methods for graphs— so one of the differences between images and graphs, and this is not only GANs, but in general, autoencoder type of architectures, is that in images, usually, it is very easy, or at least in principle, to say that you have an input, right? So you encode it into some latent space. Then you decode it back into an image, and then you usually train with some form of reconstruction loss, right? So you compare the input image to the output image. And in images, it's simple because you have canonical order of pixels. In graphs, it's difficult because you input a graph into a— you encode it into a vector, then you decode it into something, and then what? You have two graphs. How do you compare them? So this is one of the problems in, let's say, in generating molecular graphs. I would say a bigger problem is actually that molecules are not just any graph. So they have a strict set of rules that allow to generate them. So you know that certain atoms cannot connect to other atoms, for example, certain limitations on the node degree and whatnot. And the second issue that actually chemists do not think of molecules as graphs, they think of them as structures. So, and the better methods for generating molecules, such as junction tree autoencoders, they generate graphs as structures. So it's a good question of actually where do these structures come from? Can you learn them? And, or can you basically come with a fixed vocabulary of structures? Maybe in chemistry we know what are the typical chemical groups that exist, Maybe even further, chemists actually don't think of graphs as structures. They think of them, sorry, of molecules as structures. They think of them as reactions. So it's a chemical reaction. You mix this compound with this compound with these conditions to produce this resulting molecule. So really the holy grail of the field is what is called retrosynthesis. So produce a chemical reaction that can be optimized, for example, for the yield, for the costs, for the toxic waste and so on, that will produce the target molecule that has, let's say, drug-like properties and binds to the target and is not toxic and is soluble, and so on and so forth. We are probably far away from this, but hopefully one day we will have automatically generated drugs.

That's good. I would say two more questions maybe. So the first one would be, can edge features make up for the permutation ambiguity between neighbors? E.g., on a grid, one could encode left neighbor and right neighbor by an edge feature. Can this be generalized to more general graphs?

Well, even node features can disambiguate, right? So if you have a way of positionally encoding the nodes, so it can be random noise, for example, it can be the Fiedler vector of the graph Laplacian, right? So it can be basically the first non-trivial eigenvector of the graph Laplacian allows you to enumerate your nodes. So it's not a problem to uniquely encode nodes of the graph. The problem is how to make it repeatable. So expressive power is a lesser problem in graph neural networks than generalization. Very little is known about generalization. So it's usually a trade-off between how expressive you are and how well you generalize.

All right. And then last question. Thank you so much. What do you think about transformer architecture for graphs? It has now been announced to be complete replacement for CNN. And in NLP, it's the de facto standard, and it's also the best in Kaggle Molecule competition.

Well, Transformers are Graph Neural Networks, so it's a generalization. So that's your answer? So I have only good things to say about Transformers. Basically, they are GNNs. Okay. And actually, in NLP, now people try to go beyond fully connected graphs and introduce some graph structure for maybe some side information that can improve the quality of the NLP algorithms. So injecting some prior knowledge in the form of a graph actually makes a lot of sense in NLP.

All right, thank you. So yeah, I think we close with the questions. Thank you so much, Michael. I think Lena would like to have some last words maybe.

Maybe I could give you one last question because you mentioned the increase in papers on graph neural networks. So if you look at the papers that you saw this year and you had, you now need to make a bet on which paper will be the most impactful in say 3 or 5 years.

Can you pick one? Difficult question. So I probably, there are many interesting papers. I would say one that I liked in particular, I'm not sure actually it was accepted to NeurIPS, probably it was rejected. And this is the paper of Odi Alon from Israel on graph bottlenecks. So basically they identify and exemplify this problem of oversquashing and show that if you just add fully connected, basically all-to-all layer into graph neural network, just this extremely trivial naive trick improves performance. Basically it helps train deeper neural network.

I like this very much. Okay, thanks. So now the audience has homework to do. Many thanks for coming. That was a great talk, gentle introduction, and then really interesting applications.

Many thanks.

Thank you, thank you, Paul and Doreen. See you.

Bye. Thank you.