So, um, the third topic I wanna discuss is
scaling up graph neural networks by simplifying their architecture.
Um, and this is kind of an orthogonal approach,
uh, to the first two approaches.
And here is how we are going to do this.
We will start from a graph convolutional,
uh, uh, network, uh,
just as an example architecture,
and we are going to simplify it by removing
the non-linear activation from the GCN, right?
And actually, there's been a paper, uh,
two years ago or a year and a half ago that demonstrates that
the performance on- on benchmarks is not too much lower because you have,
uh, removed the non-linearity.
Uh, and this means that now,
this simplified GCN architecture turns out to be an extremely scalable,
uh, model that we can train very fast.
So basically, the idea here is you are going to simplify
the expressive power of the graph neural network so that you can train it faster.
Of course, this kind of deb- defeats the purpose of deep-learning a bit
because the point of deep learning or representation learning is a lot of data over,
uh, over complex models that can model complex, um, uh, representations.
Here, we are saying, simplify the model so it's fast to run on big data,
and of course, there is a trade off there.
So let me, uh, introduce the, uh,
GCN, uh, and then we'll continue from there, right?
So GCN takes in, uh, a graph,
uh, with, uh, node features.
And let's assume that every node includes a self-loop.
Uh, this would be, uh, convenient for,
uh, mathematical notation later.
And let's think of this as a full batch implementation, right?
So we basically set that the node embeddings
at layer- at layer 0 to be simply node features,
and then we are going to iterate for K,
uh, K layers, uh, where at, uh,
every- every node at layer k plus 1 is going
to take the embeddings of its neighbors from the previous layers,
sum them up, um,
and divide by the number of layers- number of neighbors, uh,
um, transform by this learned matrix and pass through a non-linearity.
And then we're going to run this, uh,
recursion for k iterations and whatever we end up in the end with,
whatever embedding we end up at the end,
that is what we call, uh, final embedding.
Now, what is- benefit of GCN is that it is so simple.
We can very nicely write it into the- in the matrix form.
So the way we are going to write it in the matrix form is that we are going to take
these embeddings and we are going to stack them into an embedding matrix.
And then A is our adjacency matrix where every node also has a self-loop.
Then the way you can write the sum over the neighbors of a given node- sum
of the embeddings of a- of a given no- of the neighbors of a given node,
you can simply write this as a- as a product between the adjacency matrix A
and the- and the embedding matrix H. And, uh,
what this means is that now,
we can also define this notion of D to be
a diagonal matrix where we- it is all of 0 only on the diagonal,
we have the degree of every node.
And then the inverse of D,
D to the minus 1 is the inverse of
the diagonal matrix which is just you put 1 over the degree,
uh, on the- on the diagonal entry for every node.
So now, the way you can write a summation over the neighbors
divided by the degree of that node is simply, uh,
the inverse of the diagonal matrix,
so one over the degree times the adjacency matrix A times the hidden- uh, uh,
embeddings matrix H. So this means that now,
given H at level l,
if we multiply it by A and multiply it by D to the minus 1,
we get the matrix of node embeddings at level h plus 1.
So basically, what is elegant here is that you can rewrite
this iteration just as a product of three matrices,
and of course, in the GCN,
we also have a ReLU non-linearity,
um, uh, and, uh, transformation here.
So going back to the GCN,
here is the node-based, uh, uh,
formulation of the GCN,
if you write it in the matrix form,
you can write it that this is
a non-linearity times this A tilde that is simply degree times, uh,
A, um, times the previous layer embeddings times,
uh, the W matrix which is the transformation matrix.
So basically, the equation- this equation,
uh, that is based on the network and the following matrix equation, they are equivalent.
So if you've- if you've computed this product of these matrices,
you have just computed that the k plus 1 layer
embedding for all the nodes of the network, and now,
you can kind of iterate this capital K times to compute the k layers.
So, um, this is what a matrix formulation of our GCN looks like.
So let's now go and simplify the GCN.
Let's assume and go and remove this ReLU, uh, non-linearity.
So let's- lets say,
what would happen if the GCN would- would be governed by the following equation, right?
So going back, this is the equation with a non-linearity, now,
we decided- now we decided to drop the non-linearity,
so here is our, you know,
simplified the GCN equation.
So now, let's go and unroll this- uh,
this iteration, let's- let's unroll this recursion, right?
So we say, ah, here is the final layer embeddings for the nodes,
uh, they depend on the layer k minus 1 embeddings of the nodes.
So let's now take this H_k minus 1 and insert it, uh,
with the way we compute, uh,
H_k to the minus- H to the layer k minus 1.
And you know, I take this part and just I insert it here.
And now, I notice this depends on H_k minus 2.
So again, I can go take H_k minus 2 and again expand it.
And if I do this all the way down to the 0 layer,
then, um, I- I know what to do, right?
Like H0 is simply the vector of,
uh- of, uh, node features X.
These A tildes just kind of get multiplied together.
So this is A tilde raised to the power k. And this here at the end, these, uh,
parameter matrices, it is just a product of parameter matrices that is still a matrix.
So I can rewrite this, uh,
recursive equa- equation if I expand it in the following way,
and then I realized that a product of
parameter matrices is just a parameter matrix, right?
So basically, I have just rewritten the K layer
GCN into this very simple equation that is non-recursive.
It's A tilde raised to the power k
times the feature vector times the transformation matrix.
So what is important?
What do you need to, uh,
remember here about A tilde raised to the power k?
Remember in I think Lecture 1 or 2,
we talked about what does powering the adjacency matrix to the- to the kth power mean?
It means we are counting paths,
it means we are connecting nodes that are neighbors of-
that are neighbors- neighbors of neighbors and so on.
So basically, what this means is that this til- A tilde to the k really
connects the target node to its neighbors, neighbors of neighbors,
neighbors of neighbors of neighbors,
and so on, um,
one-hop farther out in the network as we increase,
uh, uh, K, um,
and that's very interesting.
So now, why did- what can we conclude?
We can conclude that removing the non-linearity significantly simplifies the GCN.
Uh, notice also that, um,
these A tilde to the k times x does not
include- contain any learnable parameters so we can
actually pre-compute this on the- on the CPU even before we start, uh, training, right?
And this can be very efficiently computed because all I have to do is,
um, multiply the mat- uh,
A tilde with, uh,
x, uh, kind of with itself, uh,
multiple times, and I will be able to get to the A tilde raised to the power K times x.
So computing this part is very easy,
it does not depend on any, um,
model parameters so I can just pre-compute it even before I start learning.
So now, um, how about,
uh- so what we have learned is that this, uh,
A_k times x could be pre-computed and let's call this X tilde.
So now, uh, the simplified GCN,
the final embedding layer is simply this X tilde times the parameter matrix,
and this is just a linear transformation of the pre-computed matrix, right?
So the way I can- I can think of this,
this is basically just a pre-computed feature vector for node,
uh, v, uh, times its- uh,
times the matrix- learned matrix W. So embedding of node,
uh, v only depends on its own pre-processed, uh, features,
right, where I had- I say this X tilde is really
X tilde computed by A- A tilde raised to the power K times X, right?
But this is a matrix that has one row for every node,
so if I say what is the final layer embedding of a given node?
Is simply the- the corresponding row in
the matrix times the learned parameter matrix, uh,
W. But what is important to notice here is that once this X tilde has been computed,
then learn- then, uh, um,
the embedding of a given node only depends on
a given row of the X tilde that is fixed and constant.
And, uh, the only thing that changes that is learnable is W. So what this means is
that embe- embeddings of M nodes can be generated in linear ti- in the time linear,
um, with M because for a given, uh, node,
its final embedding only depends on its own,
uh, row in the matrix, uh, X tilde.
So I can easily sample a mini batch of nodes,
I sample a set of rows from the matrix X,
and then I multiply that with W to get the final layer embeddings of those,
uh, nodes, uh, in the mini-batch.
So, um, and of course this would be super fast because there is no dependencies between
the nodes or all the dependencies are already captured in this matrix, uh, X tilde.
So in summary, uh, Simplified GCN consists of two steps,
the pre-processing step where- uh,
where a pre- where we pre-compute this X tilde to be simply the adjacency matrix A,
um, with, uh, one over the degree of the node on the diagonal.
We call this A tilde,
we raise this to the Kth power so we multiply it with itself,
K step, K times,
and then we multiply this with the original features of the nodes x.
And all of this can be done on a CPU even before we start training.
So now what this means is that we have this matrix, uh, uh, uh,
X, uh, X tilde that has one row for every node, um,
and that's all- all we need for
the training step where basically for each mini-batch we are going to sample uh,
M nodes at random,
and then we simply compute their embeddings by taking,
uh, W and, uh,
multiplying it with uh, with uh,
uh, with the corresponding, uh, uh,
entry in the- in the matrix, uh,
X tilde that corresponds to that,
uh, node, uh, um, uh, uh,
v. And we simply compute the final layer embeddings of all the nodes in the mini-batch,
um, and then, you know,
we can use these embeddings to make predictions,
compute the loss, uh,
and then update the matrix- the parameter matrix,
uh, W. So, um,
the- the good point here is that now the embedding of every node,
uh, computation of it is independent from the other nodes.
It is a simple, uh,
matrix times vector product where
the matrix W is what we are trying to learn and this can be done,
uh, super, super fast.
So, um, now let's,
uh, uh, summarize and kind of, uh,
compare, uh, uh, Cluster-GCN with,
uh, uh, other methods we have learned, uh, today.
The simplified GCN generates node embeddings much more, uh, efficiently.
There is no need to create the giant computation graph,
there is no need to do graph sampling,
it is all very, very simple, right?
You just do those matrix products and then the learning step is also very easy.
So, um, it seems great, but what do we lose?
Um, right, compared to Cluster-GCN,
mini-batch of nodes in a simplified GCN can be sampled completely at random from,
uh, the entire set of nodes.
As I said, there is no need to do group- uh,
to do node groups to do the,
uh, like in Cluster-GCN,
no need to do the induced subgraph, uh, nothing like this.
So this me- this means that, uh,
our- the training is very stable, um,
and the- the variance of the gradients,
uh, is much more under control.
But, right, what is the price?
The price is that this model is far,
far, uh, less expressive.
Meaning, compared to the original graph neural network models,
simplified GCN is far less
expressive because it lacked- it doesn't have the non-linearity,
uh, in generating, uh, node embedding.
So it means that the theory that we discussed
about computation graphs, Weisfeiler-Lehman isomorphism test,
keeping the structure of the underlying subgraphs, uh,
through that injective mapping,
all that is out of the window because we don't have the non-linearity anymore.
So that really makes a huge difference in the expressive power, uh, of the model.
Right? But, you know,
in many real-world cases,
a simplified GCN, uh,
tends to work well, um,
and tends to kind of work just slightly worse than the original graph neural networks,
even though being far less, uh,
expressive in, uh, theory.
So the question is, uh, why is that?
And the reason for that is something that is called graph homophily,
which basically means, uh,
this is a concept from social science, uh,
generally people like to call it, uh,
birds of feather, uh, sto- stick together.
So or birds of feather flock together.
So basically the idea is that similar people tends to connect with each other, right?
So that basically, you know,
computer scientists know each other,
uh, people who study music know each other.
So essentially, the idea is that you have
these social communities that are tightly compact where people share
properties and attributes just because it is easier
to connect to people who have something in common with you,
with whom you share some, uh, interest, right?
So basically what this means in,
let's say networks, both in social, biological,
knowledge graphs is that nodes connected by edges tend to
share the same labels they tend to have similar features.
Right? In citation networks,
papers from the same- same area tend to cite each other.
In movie recommendation, it's like people are interested in
given genres and you watch multiple movies from the same genre.
So these movies are kind of similar to each other.
So, um, and, you know,
why- why is this important for a simplified GCN?
Because, um, the t- the three- pre-processing step of
a simplified GCN is simply feature aggregation over a k-hop, uh, neighborhood, right?
So the pre-processing features obtained by- is- are
obtained by iteratively averaging, um, um, uh,
features of the neighbors and features of the neighbors of neighbors
without learned transformation and will- without any non-linearity.
So, as a result,
nodes connected by edges tend to have similar pre-processing,
uh, features, and now with labels, um,
are also clustered kind of across the homophilis parts of the network,
um, if the labels kind of cluster a- across the network,
then simplified GCN will work, uh, really well.
So, uh, basically, the- the- when does the simplified GCN work?
The premise is that the model uses the pre-process node features to make prediction.
Nodes connected by edges tend to get
similar pre-processed features because it's all
about feature averaging across local neighborhoods.
So if nodes connected by edges tend to be in the same class,
tend to have the same label, then simplified GCN,
uh, is going to, uh,
make very accurate, uh,
predictions, uh, so basically if the graph has this kind of homophily structure.
Now, if the graph doesn't have this homophily structure,
then the simplified GCN is going to fail,
uh, quite, uh, quite bad.
So that's kind of the intuition,
and of course, ahead of time,
we generally don't know whether labels are clustered together
or they're kind of the- kind of sparkled, uh, across the network.
So to summarize, simplified GCN removes non-linearity in GCN and then reduces,
uh, the- uh, to simple, uh,
pre-processing of the node features and graph adjacency matrix.
When these pre-processed features are obtained on the CPU, a very scalable,
simple mini-batch- batch gra- stochastic gradient descent
can be directly applied to optimize the parameters.
Um, simplified GCN works surprisingly well in- in many benchmarks.
Uh, the reason for that being is that those benchmarks are easy.
Um, uh, nodes of similar label tend to link to each other.
They tend to be part,
uh, of the same network,
and meaning that just simple averaging of their features, um, uh,
without any nonlinearities and without any weight or different weighing of them,
um, gives you, uh,
good performance, uh, in practice.