Welcome back to deep learning. So today we want to look a bit into how to process graphs and we will talk a bit about graph convolutions.

So let's see what I have here for you. Topic today will be an introduction to graph deep learning.

So what's graph deep learning? Well, you could say this is a graph, right?

We know that from math that we can plot graphs, but this is not what we're going to talk about today.

Also, you could say a graph is like a plot like this one, but these are also not the plots that we want to talk about today.

So is it a Stiffy graph? No, we are also not talking about Stiffy graph.

So what we actually want to look at are more things like this, like diagrams that can be connected with different nodes and edges.

So a computer scientist thinks of a graph as a set of nodes and they are connected through edges.

So this is the kind of graphs that we want to talk about today.

For a mathematician, a graph is a manifold, but a discrete one.

So now how would you define a convolution on Euclidean space?

Well, both for computer scientists and mathematician, this is too easy.

So this is the discrete convolution, which is essentially just a sum.

And we remember we had many of those discrete convolutions when we are setting up the kernels for our convolutional deep models.

In the continuous form, it actually takes the following form.

So it's essentially an integral that is computed over the entire space.

And I brought an example here.

So if you want to convolve two Gaussian curves, then you essentially move them over each other,

multiply at each point and sum them up.

And of course, a convolution of two Gaussians is a Gaussian again.

So this is also easy.

So how would you define a convolution on graphs now?

The computer scientist thinks really hard.

But what the heck?

Well, the mathematician knows that we can use Laplace transforms in order to describe convolutions.

And therefore, we look into the Laplacian that is here given as the divergence of the gradients.

So in math, we can deal with these things more easily.

So this then brings us to this manifold idea.

We know how to convolve manifolds.

We can discretize convolutions.

And this means that we know how to convolve graphs.

So let's diffuse some heat.

So we know that we can describe Newton's law of cooling as the following equation.

So we know that the development over time can be described with the Laplacian.

So f of xt is then the amount of heat at point x at time t.

Then you need to have an initial heat distribution.

So you need to know how the heat is in the zero state.

Then you can use the Laplacian in order to express how the system behaves over time.

And here you can see that this is essentially the difference between f of x and the average of f on an infinitesimal small sphere around x.

Now, how do we express the Laplacian in discrete form?

Well, that's the difference between f of x and the average of f on an infinitesimal sphere around x.

So the smallest step that we can do is actually connect the current node with its neighbors.

So we can express the Laplacian as a weighted sum over the edge weights a i j.

And this is then the difference of our center node fi minus fj. And we divide the whole thing by the number of connections that actually are incoming into fi.

So this is going to be given as di.

Now, is there another way of expressing this?

Well, yes. And we can do this if you look at an example graph here.

So we have the nodes 1, 2, 3, 4, 5, and 6.

And we can now compute the Laplacian matrix using the matrix D.

And D is now simply the number of incoming connections into the respective nodes.