Welcome everyone, uh, to the class.
What we are going to talk today about is,
um, some advanced topics,
and in particular we are going first to talk about limitations of,
uh, graph neural networks,
um, and then we are also going about how do we improve
their expressive power and how do we, um,
then, uh, study, uh,
how robust are graph neural networks against, um, adversarial attacks.
So the idea for today's lecture is- lecture is the following.
Um, what would the perfect GNN model do, right,
if we wanna say about what are some limitations of graph neural networks and
especially when we looked at their expressive power in terms of the,
um, in terms of the, um,
uh, WL kernel, right?
If we go through a thought experiment then we could say,
what would a perfect graph neural network do?
And the k-layer graph neural network embeds a node
based on the K-hop neighborhood structure around that node, right?
And this picture tries to illustrate that.
That is that basically if I wanna embed this particular, um, node here,
I can take the graph structure around this node and then,
um, through message passing,
I wanna compute the embedding of that node;
and a perfect GNN would be such that it would build
an injective function between the neighborhood structure around the target node,
um, and the embedding that it produces.
So essentially, what we'd like to do is- with
a perfect GNN would take every different node neighborhood structure,
uh, and embed it into a different position,
uh, in the embedding space.
Um, there are two important, uh,
observations, uh, building on this intuition.
First is that a perfect GNN will do the following, right?
If two nodes have the same neighborhood structure around the- around them,
then they will have the same embedding.
Again, here we are assuming there is no discriminative,
uh, feature information given to us.
So v1 and v2 in this- in this,
uh, graph, with, let's say,
two connected components will be embedded into
the- exactly the same point because their neighborhood structure,
uh, around them is identical,
and of course, right?
If we have two nodes that have different neighborhood structures, then, um,
we'd like them to be embedded into different points in the space
because the net- the- the neighborhood structures of these two nodes are different.
One is in a triangle,
the other one is in a square,
so they should be embedded into different points.
So that's kind of what we'd like to do.
That's what we'd like our perfect,
uh, GNN to do.
However, these observations, 1 and 2 may not be always, uh, true.
For example, the- the observation 1,
um, can have kind of the following, uh, issues.
Even though two nodes may have the same neighborhood structure around them,
we may wanna assign,
um, different embeddings to them.
Um, and this is because, uh, you know,
nodes may appear in different positions or in different locations in the graph.
Um, and we, uh,
we are going to call, uh, uh,
this notion of a position in the graph and
these tasks that require us understanding the position,
we'll call those position-aware tasks.
And I'm going to define this more, uh,
precisely throughout, uh, the lecture, right?
So basically even a- a perfect GNN,
that has that, um, injective,
uh, function between the neighborhood structure and
the embedding will fail at these, uh, tasks.
Uh, for example, here if I have a simple grid graph and I have nodes v1 and v2,
and I'd like them to be embedded into different points in space because they
are kind of at the opposite ends of the- of the underlying uh,
graph, actually a graph neural network is going to embed them, uh,
into the same position because the neighborhood structure around them is identical.
They are both in the corner,
uh, of the grid.
Um, so this is kind of one issue that, uh,
graph neural networks, as we have defined them so far,
uh, are not able to do.
Um, the second important, uh,
implication of the observation 2 is that,
um, GNNs that we have introduced so far are kind of not perfect, right?
Their expressive power, um,
is not- is not enough, right?
Uh, and in- particularly in lecture 9,
we discussed that the expressive power of our graph neural network,
this message passing graph neural network with indiscriminative features, uh,
it's expressive power is upper binded- bounded by the Weisfeiler-Lehman,
um, graph isomorphism test.
So, uh, for example, um,
if I have nodes v1 on a cycle of length 3 and a node v2 on cycle of length 4,
if I look at the structure of their computation graphs,
um, the structure of the two computation graphs will be the same.
So without any discriminative node features
or if assuming all node features are the same,
graph neural network is not going to be able to distinguish, um,
or it won't be able to assign different embeddings to nodes 1 and, uh, 2.
So basically nodes v1 and v2 will always be embedded into the same space, uh,
under the assumption that there is no useful node features,
um, because their computation graphs,
uh, are identical even though one
resides in a triangle and the other one resides in a square.
So, uh, the plan for the lecture today is that we wanna resolve both of
these issues by building or designing more expressive graph neural networks.
Uh, and the way we are going to fix these issues is the following.
Uh, to fix the issue, um, uh, one,
we are going to create node embeddings based on their positions in the graph.
Um, and the idea will be that we wanna create reference points in
the graph and then quantify the position of a node against those,
uh, reference points, and the class of models that
allow us to do this are called position-aware graph neural networks.
And then to fix the issue number- number 2, um,
we- we- we are going to build, uh,
message-passing GNNs that are more expressive than the WL, uh, test.
Um, and the method, an example of such a mes- message- method,
is called Identity-aware graph neural network.
So this is what is going to be the,
uh, plan for the, uh,
for the first part of the lecture,
and then in the last part I'm going to talk about adversarial attacks.
So, uh, here is our approach,
and this is how we wanna think about it.
So, um, we will use the following thinking.
Um, given two different, uh, inputs,
for example, nodes, uh, graphs, uh,
uh, edges, um, er,
let's assume they are labeled differently,
and we are going to say that, you know, kind of,
the model fails, um,
if it- i- if it is always going to
assign the same embedding to these different inputs,
or these different objects,
and a successful model is going to assign different embeddings to these,
uh, different, uh, types of objects.
Um, so if we focus,
let's say on node-level embeddings, then, you know,
embeddings in a GNN are determined,
uh, by the underlying computation graph.
Right? And in my case,
imagine again I have a graph with two connected components.
I have two vertices, v1 and v2.
Imagine v1 and v2 are labeled with different labels.
V1 is labeled with A,
v2 is labeled with B.
The goal will be to build a graph neural network that is
going to assign different embeddings to node v1,
then to the node v2.
Again, under the assumption that node features are the same,
uh, or, non-discriminative between uh, v1 and v2;
and perhaps what is- you may seem- or you may say
striking or interesting is that the models we have,
uh, um, developed so far,
uh, actually fail to distinguish v1 and v2.
Like, even though we have built
so much super cool machinery that works amazingly well in practice, uh,
and empirically, um, we still cannot
distinguish v1 and v2 in this kind of corner case, uh, example.
So what we are going to do is to understand how can we resolve this?
How can we build a network that- a graph neural network that will be able to distinguish,
uh, basically, uh, v1 and v2.
So meaning assign them different embeddings,
so that then we can assign v1, one label,
and we can assign v2, the other label,
because we cannot assign them different label if they both map into the same point.
So a naive solution to this,
that kind of doesn't work, would be,
uh, to use one hold and- one-hot encoding.
So we would like to say,
Okay, we don't have any features,
but let us- let's assign each node a
different ID and then we can always differentiate different nodes,
um, in- in a graph or different edges or even different graphs.
So if I have, you know,
two- two graphs here,
uh, as we had before,
I could simply assign a one-hot encoding to every node,
um, and now of course,
because nodes now have, uh, features,
it will be- the computational graphs will be distinguishable because,
you know, v1 will have, uh,
two children, one with 0100,
and the other one with, you know, 001;
and v2 is going to have,
um, different, um, types of, um, uh,
neighbors because their- their,
um, one-hot encodings, uh, will be different.
Then, even though with the two,
if they will be the same at the first level,
they won't be the same on the second level.
So basically, computational graphs will be different,
so our GNN will be able to, uh, distinguish them.
Um, what are the issues with this?
The- there are two very important issues.
First is that this approach is not scalable;
meaning we need an order N feature dimensions
where N- N is the number of nodes to be able to encode, right?
Basically, we need a separate feature for every individual node,
and if, you know,
if we have a 10,000 or a 100,000 or a million node network,
then every node has now a million features,
basically a one-hot encoding of its ID.
Uh, and then the second problem is that this is in- this is not inductive;
meaning it won't generalize to new- new nodes or
new graphs because these one-hot encodings are kind of arbitrary,
node ordering is arbitrary,
so the map- the network,
it could basically learn according to that node ordering,
and then if we, um,
try to transfer this to a new graph,
or if a new node appears in the network,
this won't- this won't work, right.
If a new node appears we'll have to expand- extend the feature dimensionality because
we wanna encode- use one-hot encoding for that node as well and we'd have to retrain.
Uh, or if we wanna transfer to a new graph,
we have no guarantees because, uh,
the one-hot encoding and node IDs are kind of arbitrary,
so it won't, uh, it won't generalize.
So this is why, you know,
this is a bad- bad idea,
but, ah, this idea kind of to enrich,
uh, the nodes so that we can, um,
differentiate different computational graphs is a good idea.
Just one-hot encoding, uh,
doesn't work in this case.