Welcome back to Deep Learning. So today we want to continue talking about the graph

convolutions and today we will look into the second part where we now see whether we can

now stay in this spectral domain or whether we can also go back to spatial domain. So

let's look what I have for you. So you remember we had this polynomial that we used in order

to define a convolution in spectral domain and we've seen that by computing the eigenvectors

of the Laplacian matrix we were able to find an appropriate Fourier transform that would

then give us a spectral representation of the graph configuration. Then we could do

our convolution in spectral domain and transform back. Now this was kind of very expensive

because we have to compute U and for U we have to do the eigenvalue decomposition for

this entire symmetric matrix and so on. And also we've seen that we can't use tricks

of the fast Fourier transform because this doesn't necessarily hold for our U-T. So

how can we choose now k and theta in order to get rid of U? Well, so if we choose k equals

to 1, theta 0 to 2 theta and theta 1 to minus theta we get the following polynomial. So

we still have the configuration that we have X transformed into Fourier space times our

polynomial expressed as matrix times the inverse Fourier transform here. Now let's look into

the configuration of g hat. g hat can actually be expressed as 2 times theta times lambda

to the power of 0. Remember lambda is a diagonal matrix so we take every element to the power

of 0. So this is actually a unity matrix and we subtract theta times lambda to the power

of 1. Well, this is actually just lambda and then we can express our complete matrix g

hat in this way. Of course we can then pull in our U from the left hand side and the right

hand side which is giving us the following expression. Now we use the property that theta

is actually a scalar so we can pull it to the front. The lambda to the power of 0 cancels

out because this is essentially just an identity matrix and the lambda on the right hand side

term still remains but we can also pull out the theta. Well, the U transpose just cancels

out so this is again the identity matrix and we can use our definition of the symmetric

version of our graph Laplacian and you can see that we just find it here in our equation

so we can also replace it with this one and you see now U is suddenly gone. So we can

pull out theta again and all that remains is that we have two times the identity matrix

minus the symmetric version of the graph Laplacian. If we now plug in the definition of the symmetric

version associated to the original adiacency matrix and the degree matrix we can see that

we still can plug this definition in then one of the identity matrices cancels out and

we finally get identity plus d to the power of minus 0.5 times A times d to the power

of minus 0.5. So remember d is a diagonal matrix so we can easily invert the elements

on the diagonal and we can also take element wise the square root so this is perfectly

fine. So this way we don't have U at all coming up here and we can express our entire

graph convolution in this very nice way using the graph Laplacian matrix. Now let's analyze

this term a little more so we can see this identity on the left hand side we see we can

convolve x in spectral domain and we can construct g hat as a polynomial of Laplacian filters

then we can see with a particular choice k equals one and theta zero equals to two theta

and theta one equals to minus theta then this term suddenly only depends on the scalar value

theta and with all these tricks we got rid of the Fourier transform U transpose so we

suddenly can express graph convolutions in this simplified way. Well this is the basic

graph convolution operation and you can find this actually shown in reference number one

you can essentially do this with a scalar value you use your degree matrix and plug

it in here you use your adhacency matrix and you plug it in here and then you can optimize

with respect to theta in order to find the weight for your convolutions. Well now the

question is is it really necessary to motivate the graph convolution from spectral domain

and the answer is no so we can also motivate it spatially as well. So let's look at the

following concept for a mathematician a graph is a manifold but a discrete one we can discretize

the manifold and do spectral convolution using the Laplacian matrix so this led us to spectral