So, uh, good.
So far we talked about a single graph neural network layer.
What I'm going to talk about next is to talk about, uh,
how do we stack, uh,
layers into a multi-layer,
uh, graph neural network.
So, we first talked about, uh,
designing and defining a single layer of a graph neural network,
where we said that it comp- it composes of
a message transformation operation and a message aggregation operation.
We also talked about additional,
uh, things you can add to training,
which is like batch normalization,
choice of different activation functions,
choice of L2 normalization,
um, things like that.
What we want to talk next is to talk about how can you stack these, uh,
layers one on top of each other and, uh, for example,
how can you add or skip connections to graph neural networks?
So that's the, uh,
topic I wanna, uh, discuss next.
So the question is,
how do I construct a graph neural network based on
the single layer that I have, already defined.
And, ah, a standard way,
a usual way would be to stack graph neural networks sequentially.
So basically the idea is I- under- as the embedding of node at layer 0,
I simply use the raw node features of the node and then I'm, you know,
transporting them individually layer by layer up to some,
uh, number of layers.
For example, in this case,
we have now a three-layer, uh,
graph neural network where on the input I get the raw node features x.
They get transformed into the embedding at a level 3 of, uh,
node v. That is actually an important issue in,
uh, graph neural networks that prevents us from stacking too many layers, uh, together.
And the important point here that I want to make
is introduce you the notion of over-smoothing,
um, and discuss how to prevent it.
And then one thing I wanna also make, uh,
a point about is that the depth of the graph neural network
is different than the depth in terms of number of layers in,
let's say convolutional neural networks.
So the depth of graph neural networks really tells me how many
hops away in the network do I go to collect the information.
And it doesn't necessarily say how complex or how expressive, uh,
the entire network is,
because that depends on the design of each individual layer of the graph neural network.
So kind of the point I'm trying to make,
the notion of a layer in
a graph neural network is different than the notion of a layer in,
let's say, a convolutional neural network.
So the issue of stacking many GNN layers together is
that GNNs tend to suffer from what is called an over-smoothing problem.
And the over-smoothing problem is that kind of node embeddings,
you know, converge to the same or very similar value.
And the reason why this is happening is because,
uh, if the receptive fields,
as I'm going to define them later of the- of the networks are too big,
then basically all the network- all the neural networks collect the same information,
so at the end, the final output is also the same for all different nodes.
And we don't want to have this problem of over-smoothing
because we want embeddings for different nodes to be different.
So let me tell you more about what is an over-smoothing problem
and why does it happen and how do we, uh, remedy it.
So first, we need to define this notion of a receptive field.
A receptive field, uh,
is a set of nodes that determine the embedding of the node of interest.
So in a K layer GNN, uh,
each node has a receptive field of k-hops- k-hop neighborhood around that node.
And this becomes, uh,
important because for example,
if you say I wanted to link prediction between the two yellow nodes,
uh, in this graph.
Then the question is,
how ma- as I increase the,
uh, depth of the network,
how many, uh, and look at
the corresponding computation graphs of the two, uh, yellow nodes?
uh, the question is, how, um,
how big, uh, how big is the receptive field, right?
So for example, what I'm trying to show here is for a single node, uh,
the receptive field at one layer,
so one hop away is, you know,
this four, uh, five different,
uh, red nodes denoted here.
If I say now, let's do a two-layer neural network.
This is now the receptive field.
It's all neighbors and all the neighbors of neighbors.
It's like one-hop neighborhood and two-hop neighborhood.
And if I go to a three-layer neural network,
in this case of a small graph,
now, notice that basically,
majority or almost every node in the net- in the- in
the underlying network is part of my graph neural network architecture.
So this means that this yellow node is going to collect information from
every other node in the network to combi- to determine its own, uh, embedding.
Now, if you, for example wanna do link prediction, um,
then you, uh, you wanna say whether a pair of nodes is,
uh, connected or not.
And what is interesting in this case is that, um,
the- the number of neighbors that are shared grows very
quickly as we increase the number of hops in the graph neural network.
So now, uh, I have a different visualization here.
I have two nodes denoted by yellow and I
compute one-hop neighborhoods from each and I say what nodes are in the intersection?
What nodes are shared?
And here, one node is shared.
Then if I say, let's compute 2-hop neighborhood,
now, all these neighbors are shared.
And if I say how many neighbors are shared, uh,
between 3-hops, how many nodes are share- shared within three hops?
Again, you see that basically almost all the nodes are shared.
And the problem then becomes that as the network is aggregating all this information
and all the- all the nodes- all the graph neural networks basically get the same inputs,
it will be increasingly hard to differentiate between different nodes, uh, you know,
let's say the nodes that are- that are going to be connected in
the network and the nodes that are not connected in the network.
So, uh, you know,
how do we explain the notion of over-smoothing with this definition of a receptive field?
Uh, you know, we know that the embedding of a node is-
this determined by its receptive field, right?
And if two nodes have highly overlapping receptive fields,
there- there- then their embeddings are also going to be most likely, uh, similar.
So this means that if I stack many GNN layers together,
then it means nodes will have highly overlapping receptive fields, uh,
which means they will collect information from
the same part of the network and they will aggregate it in the same way.
So node embeddings will be highly similar.
So it means it can be very hard for us to distinguish between
different nodes and this is what we call an over-smoothing problem, right?
It's like you collect too much information from the neighborhood and then,
um, if you collect kind of too much,
everyone collects the same information,
so every node kind of has the same information,
computes the same embedding and it is very hard to differentiate between them.
So the question is,
how do we overcome over-smoothing?
Uh, first is that we are cautious about how many,
um, layers, how many GNN layers, uh, do we use.
So what this means that, unlike in, uh,
neural networks in other domains like
convolutional neural networks for image classification,
adding more layers to our graph neural network does not always skip.
So first, what we need to do, uh,
to determine how many layers is good is to analyze then the-
the amount of information we need to make a good prediction.
So basically, analyze different depths,
different receptive fields, and try to get a good, uh,
balance between the diameter of the network and the amount of
information that a single GNN is aggregating goal.
Because if the depth is too big, then basically,
the receptive field of a single node may basically be the entire, uh, network.
The second thing is that we wanna s- setup the number of GNN layers L to be, uh,
a bit, uh, more than the receptive field we, uh,
we like, but we don't wanna make L to be unnecessarily large.
Um, so that's one way,
uh, to deal with this.
Another way to deal with this is to say,
how do we enhance expressive power of a GNN if the number of layers is smaller?
The way we do this is the following.
Um, right, how do we make GNNs more- more
expressive if we cannot make them more expressive but making them deeper.
One option is to- to add more expressive power within a GNN layer.
So what this means is that in our previous examples, uh,
each transformation or aggregation function was only one linear transformation.
But we can make aggregation and transformation become deep neural networks by themselves.
So for example, we could make the aggregation operator and the transformation operator,
let's say a three-layer- um,
uh, multilayer perceptron network, uh,
and not just a simple, uh,
linear, uh, layer in the network.
In this way add, um,
express- ex- expressiveness, uh, to the neural network.
Right, so now our single layer graph neural network is really a three-layer,
uh, deep neural network, right?
So the notion of a layer in a GNN and a notion of
a layer in terms of transformations, uh, is different.
So another way how we can make shallow GNNs more expressive is to add,
uh, layers that do not pass messages.
So what this means is that a GNN does not
necessarily have to contain only GNN layers, right?
We can, for example, have, uh,
multilayer perceptron layers before and after the GNN layers.
And you can think of these as pre-processing and post-processing layers.
To give you the idea, right,
we could take the input- uh,
massive inputs- um, input features,
transform them through the preprocessing step of
multilayer perceptron, apply the graph neural network layers,
and then again have a couple of, um, um, multilayer,
uh, perceptron layers that do the post-processing of embeddings.
So we can think of these as pre-processing layers that are-
that are important when encoding node features.
For example, if node features represent images or text,
we would want to have an entire CNN here, for example.
Um, and then we have our post-processing layers, uh,
which are important when we are reasoning,
or- or transforming over whether the node, uh, embeddings.
Uh, this becomes important if you are doing,
for example, graph classification or knowledge graphs,
where the transformations here add a lot to
the expressive power of the graph neural networks, right?
So in practice, adding these pre-processing and post-processing layers,
uh, works great in practice.
So it means we are combining classical neural network layers with graph,
uh, neural network layers.
So, uh, the- the last way how we can,
um, uh, think about, uh,
shallower graph neural networks,
but being the more expressive is to add this notion of a skip connection, right?
And the observation from Over-Smoothing problem that I discussed was
that node embeddings in earlier GNN layers can sometime,
um, better differentiate between different nodes earlier,
meaning lower layer, uh, embeddings.
And the solution is that we can increase the impact of
earlier layers on the final known embedding to add the shortcuts,
uh, in the neural network,
or what do we mean by shortcuts is skip connections, right?
So if I go now back to my picture from the previous slide,
what I can add is,
when I have the, um- the GNN layers,
I can add this red connections that basically skip a layer and go from,
um connectly- directly connect,
let's say the GNN layer 1 to the GNN layer 3,
and they skip this layer 2, uh, in-between.
So the idea is that this is now a skip connection.
Uh, so the message now gets duplicated.
One message goes into the transformation layer and,
uh, weight update,
while the same message also gets dup- duplicated and just kind of
sent forward and then the two branches are summed up.
So before adding skip connections,
we simply took the message and transformed it.
Now with a skip connection,
we take the message, transform it,
but then sum it up or aggregate it with the untransformed, uh, message itself.
So that is, um,
an interesting, uh, approach, um, as well.
So why do we care about skip connections and why do skip connections work?
Um, intuition is that skip connections create what is called, uh, mixture models.
Mixture model in a sense that now your model is
a weighted combination of a previous layer and the current layer message.
In this way basically means that you- you have now mixing
together two different layers or two different, uh, models.
Um, there is a lot of skip connections to add, right?
If you, um- if you have, let's say,
n skip connections, then there is 2 to the n possible message-passing paths,
which really allows you to increase the expressive power and gives neural network,
uh, more flexibility in terms of how
messages are passed and how messages are, uh, aggregated.
Uh, and, uh, first right, um,
we can also automatically get a mixture of automa- uh, shallow GNNs,
as well as the deep GNNs through the,
uh, message-passing layers, right?
So basically what I mean by this is you could have a three-layer,
uh, neural network and then by adding skip connections,
you can basically now have the final output to
be some combination of a one-layer neural network,
a two-layer neural network,
A one-layer neural network fed into the, uh,
third layer of the neural network and all this aggregated,
um, into the final output.
So now you can think that the final output is a- is a- is a combination of, uh,
in this case, four different, uh,
neural network, uh, architectures, right?
And, you know, the way you can- you can think of it is to say, oh,
I have three layers,
I add these three skip connections.
What this really does is,
you can think of it now that you have
four different neural network architectures that you are mixing or adding together,
uh, for, uh- during learning.
So it's a very efficient representation that really you can think of it in this,
um- in this second way.
So how would you apply skip connections,
uh, to graph neural networks?
For example, if we take a classical, uh,
graph convolutional neural network, uh,
architecture and add skip connections to it,
uh, this is how it would look like.
Before in the standard GNN layer- GCN layer,
we take the messages from the neighbors, uh,
transform them, and, uh,
average them together and we can think of this as our f of x from the previous slide.
So a GCN layer with a skip connection would be the same f of x plus,
uh, the lay- the message, uh,
from the previous, uh, layer, right?
So here we are just adding in the message from the previous layer and then
passing it all through the, um, non-linearity.
So this is- what this means is we added
the skip connection here in a single layer through this,
uh, blue part, uh, here.
And of course, um,
we have many other options for skip connections.
We can make them skip one layer,
we can make them skip, uh, multiple layers.
Um, there is a- there is an interesting paper, uh,
from ICML called Jumping Knowledge Networks, where for example,
the proposal is to add these skips from a given layer
all the way to the- to the last layer where you basically now can think,
Oh, I have a o- one-layer neural network,
I have a two-layer neural network,
I have a three-layer neural network.
I take their inputs and,
uh- and then aggregate them to get the final, uh, output.
So by basically directly skipping to the- to the last- to the finals- final layer, um,
the final layer can then aggregate all these embeddings from
neural networks of different depths and this way basically,
uh, determine what information is more important,
uh, for, let's say for the prediction task.
Is it the information from very close by
nearby nodes or is it really about aggregating bigger parts of the network?
And by adding these skip connections,
basically this allows us to weigh or to determine what information is more important,
something that has been aggregated across multiple hops, or something that has been,
let say, aggregated over zero hops or over only a single hop?
Um, and that is very interesting and again,
adds to expressivity, uh, and,
uh, improves the performance,
uh, of graph neural, uh, networks.