Hello, welcome to the AI Coffee Break! Today, Ms. Coffee Bean has prepared the definitive introduction to Graph Neural Networks! Or GNNs in short. But Ms. Coffee Bean, are you not a little over-confident to say “definitive”? Phsssht! I just wonder if… psshht! Ok, ehm, here we go: I always struggled with Graph Neural Networks in machine learning classes. But one day, I could not get around them anymore and had to learn them! They are such a huge topic in machine learning for a very obvious reason: graphs are everywhere! And not just here artistically represented in this stock image. Let’s take for example air travel. Flights from origin to destination with perhaps a stop in the middle, can be represented as a graph, where airlines try to maximize the number of passengers transported by trying to minimize fuel, time and other costs. Navigation systems on smaller scales, on street maps, also do graph optimization for getting you to your destination. Other examples of graphs are personal connections or graphs that social media apps live of. Or even text is also a graph if we think of it not as a sequence, but if we analyze it linguistically in terms of the dependency parse, for example. Images are graphs too in multiple senses: We make one kind of graph interpretation of images when we represent each pixel as a graph node and each pixel is connected with an edge to its neighbors. This is a very regular kind of graph, a grid. Another, more semantic graph interpretation of an image, can be in terms of the scene graph, where objects and entities are nodes, connected by their relation in the image. One more example and we get finally to Graph Neural Networks: In NLP people are interested in the knowledge graphs comprising facts about the world, like these true facts here. Well, I hope you are now convinced now how ubiquitous graphs are, so of course we need a deep neural model to handle these structures, right? Well, graph neural networks are the deep and neural solution to this. They come in many shapes and flavors, but we want here to stay simple and explain only the Graph Convolutional Neural Networks. If you understand this one, you will also understand the basics of the others architectures, because they work based on the same principles. And Graph Convolutional Neural Nets are not hard, you just have to apply this formula iteratively and you are done. Wait what? Well if that’s it, let’s break it down to every detail: First, let’s talk about the nodes. They are denoted here with h, where h is a vector representation of the nodes. These vectors are chosen depending on the application: They can be word vectors when working with knowledge bases, they can be pixel values when working with images. They can be a combination of image features and word vectors if working with scene graphs! In Graph Neural Networks, the idea is that we have initial vector representations for our problem. But we can do even better, if we take the neighbors and relations into account. So in principle, we update our initial vectors using information in the graph structure and get vectors that represent the problem better. So the key is not in the initial representation of the nodes, but in how one aggregates the representations of the neighbors in order to get an even better representation than the original. This is why we apply this formula recursively, to get another, better vector h at each time step. Only the question now, is how do we exactly get this better representation? First, when computing the new representation, we want to keep something from the old one. For example when working with a knowledge base that truthfully says that Ms. Coffee Bean is a star, when computing a new vector for her, now knowing that she is a star, we still want to keep the knowledge of her identity. This is why, we take the old representation and multiply it by a weight matrix, deciding how this previous knowledge should be transformed. But how do we know this weight matrix? Well, we don’t! We let a neural network decide for it! We train it on our given data of node labels, edge labels or other predictions from the graph structure. When training with these objectives, the neural network learns to make right predictions given the new representations, so it better should learn the weight matrix that helps to get this new representation. This is how we decide on what and how to keep from our original representation. Now, we also want to aggregate the information from the neighbors. So we take their representation and also let a neural network decide how to transform it and what to keep from it for being able to solve the given task, for example node label prediction. And here is where the magic of the graph convolutional neural network happens: In the aggregation function. By this sum we say that we sum over all transformed neighbor representations. By c_ij we mean that we normalize the vectors differently for each neighbor. But this is not really important, because crucial here, is that the normalizing sum here is a permutation-invariant aggregation function. A whaat now? Well, this means that however we aggregate the information from the neighbors, the way we do this has to be insensitive to order. Because there is no intrinsic ordering to a graph, how would we ever decide if we take node 4 or node 2 first? So we don’t decide, because we take a permutation-invariant function, delivering the same result given any order. Another example for a permutation-invariant function would be the product or the maximum function, because they do not depend on argument order. And because we aggregate the information from the nodes, similarly to how we do in CNNs (convolutional neural networks), this is then called the convolutional graph neural network. Of course, the name “convolution” is misleading, because the convolution in images is not permutation-invariant (you can check it), but still, it is a valid operation if we regard images as graphs, because images are a special type of graphs, where the order is given. So yes, the name convolution is misleading, but it is how it is! And here we are: If we apply this formula iteratively, at each timestep we learn a better graph representation comprising node information also from neighbors and their neighbors. These new informed and refined representations should be then suitable to be used for the new task of, for example link prediction, node classification or even entire graph classification and many other tasks. GNNs have been successfully applied in the medical domain for example, to predict side-effects due to drug interactions. Or in numerous graph optimization problems, like the travelling salesman problem. Or for various applications in knowledge graph prediction. They can be even used for predicting object trajectories from video. These applications are just a few from a very big list. Where there is a graph (so everywhere), there can be a graph neural network solving the problem. So this was it, we hope that now you have a better understanding of Graph Neural Networks and are curious enough to go out and explore the topic of GNNs by yourself! Hey, do not forget to like and subscribe! See you!