Welcome everyone, uh, back to the class.
Uh, super excited to,
uh, talk to you all today.
Um, we are going to discuss,
um, several very interesting topics.
Uh, first, we are going to finish,
uh, some of the parts, uh,
that are left unfinished from the last lecture,
and then we are going to dig into the theory of,
uh, graph neural networks.
So let's first talk about,
uh, where we ended last time, right?
So last time we talked about how do you design graph neural networks?
What kind of, um, uh,
design choices do you make and, eh,
how do you set up the entire,
let's call it training inference pipeline.
And we talked about how do you setup the input graph?
How do you define the graph neural network architecture?
How do you then use it to create node embeddings?
And then we also talked about how do you get from
node embeddings to the prediction- prediction head.
And we talked about the different prediction heads, uh,
based on node classification, uh,
link, uh, prediction as well as graph classification.
We talked about how do you then make predictions?
How do you compare those predictions with ground truth labels, uh,
to optimize the loss function and be able to do
back-propagation all the way down to the graph neural network structure?
And then we also talked about various kinds of, uh,
evaluation metrics you can use, uh,
to assess, estimate, uh,
the performance of your model.
One thing that still remains, uh,
unanswered is, uh, how do we set up the tasks?
How do we properly split into the training,
validation, uh, and test set?
And what I wanna talk, uh,
in this part of the lecture,
is address this question,
how do we split our datasets- our graph dataset into train, validation, and test sets?
So, um, we have two options,
um, when we are splitting a dataset.
We can, uh, split our dataset at once and call this a fixed split, where basically,
we want to take a dataset and split it into three disjoint independent pieces.
We wanna have a training set that we are going to use to optimize GNN model parameters.
We are going to use a validation set which we- we can use to
tune hyperparameters and various kinds of con- constants and decision choices,
uh, in terms of,
uh, the modeling architecture.
And once basically using the training set and the validation set,
we finalize our final model,
final- final values of hyper-parameters,
final values of different design dimensions.
Uh, we are then going to apply our model to
this new independent test set that was held out all the time,
and we only use it to report final, uh, performance.
And this is a fair way to evaluate because we
used training and validation to build the model,
then we fix the model and we apply it to this, uh, independent,
unseen never touched before test set and we pre- uh,
we report, uh, our performance.
Um, what is interesting in graphs, is that, uh,
sometimes we cannot guarantee that the test set will really be held out,
meaning that there will be no information leakage
from training and validation sets into the test set.
And this is why, uh, this becomes interesting.
So that's that's in terms of a fixed split.
Once we have created the fixed split,
we could actually make it such that it is a random.
And what this would mean, is that we could randomly split our data into training,
validation, and test set,
and then we could kind of report- rather than on a single split,
we could report average performance over different,
uh, uh, let's call them, uh, random splits.
So one is just to create the split and work with it forever.
The other one is to kind of create the split,
but one component of that split is that there is some randomness and we can
then try out many different instantiation of the split and report the average,
uh, to provide even more,
uh, robust, uh, results.
So, um, you know,
why is splitting graphs special?
Uh, imagine if you have an image dataset or a document dataset.
Then in such datasets,
you assume that, uh,
uh, data points are independent from, uh, each other.
So this means that, uh,
each data point here is an image, and, uh,
because they are independent from each other,
it is easy to split them into training, test,
uh, and validation, uh, set.
Um, and there is no leakage because each image is a data- data point, uh, by its own.
Uh, splitting a graph is different.
Um, the problem with the graph is that nodes are connected with each other.
So for example, in node classification,
each data point is a node now, um,
but these nodes are not independent from each other.
The nodes are actually connected, uh,
with each other, meaning that,
you know, for example, in this case,
if I look at node 5, in order to predict node 5, it will,
in terms of a graph neural network also collect information from nodes,
uh, 1 and 2.
So this means that, uh,
nodes, um, 1 and, um, uh,
2, um, will affect,
uh, the prediction on- on- of node 5.
So if 1 and 2 are the training dataset and 5 is the test dataset,
then clearly we have some,
um, information, uh, leakage.
So, uh, this is why this is interesting.
So then the question is,
um, what are our options?
What can we- uh, what can we do?
Um, we can do the following.
Um, the first solution is to do what we call,
um, a transductive setting,
where the input graph can be observed over, for all the dataset splits.
So basically we- we will work with the same graph structure for training,
validation, and, uh, test set.
And we will only split the node- the node labels,
meaning we'll keep the graph structure as is,
but we're going to put some nodes into the training,
test and, uh, validation, uh, set.
So we are only splitting, uh, node labels.
This means that at the training time,
we compute embeddings of nodes,
let's say 1 and 2 because they are our training set, uh,
using the entire graph,
but only labels of 1 and 2.
And at validation time we compute embeddings of the, uh,
entire graph and only evaluate on, uh, uh, uh,
labels of nodes 3 and 4 because we have the data, uh, for them.
So this would be one possible,
uh, approach, uh, to do this.
Another approach is what we call,
uh, an inductive setting, where we, uh,
break the edges between the splits into, uh,
multiple graphs or multiple independent graphs, multiple independent components.
So now we have, uh,
three graphs that are independent.
Um, and in our case that would mean is that we would just drop these , uh, dotted edges.
So now we have three different graphs and we can call one a training graph,
a validation graph, um, and a test graph.
Um, so this means that when now we are making,
let's say a prediction, uh,
in the test set about node five,
we are not affected, uh,
by the, uh, prediction of- uh,
by the label or the structure from- information from node 1 anymore.
So this means that at the training time we compute embeddings
only over the graph that includes nodes 1 and 2,
um, and only, uh,
in using the labels of 1 and 2.
And at validation time,
we compute the embedding using the graph, uh,
over nodes 3 and 4, uh,
and evaluate based on the nodes, uh, 3 and 4.
Of course, the problem with this- with this approach,
is that now I have- I have thrown away quite a few edges,
quite a bit of graph information,
and if my graphs are small,
this is not, uh, preferred.
So kind of the trade-off is either I have some leakage of structured information between,
uh, training, validation and test set,
but at least the labels are independent in
the transductive setting or in an inductive setting,
I actually have to throw away the edges so that I chop
the graph in two different independent pieces and then,
uh, run or evaluate over those pieces.
So in- the solution in that transactive setting is that the in- input graph, uh,
can be, uh, observed, uh,
for all, uh, dataset splits,
training, validation, and test.
Um, and this is- this is interesting because, um,
it allows us to basically operate in this what you could also think of
as semi-supervised setting where the graph is given, uh,
the- the edges of all the nodes are given,
uh, the features of all the nodes are given,
but the lab- but the labels of nodes are only,
uh, only a subset of node labels, uh, is observed.
So, uh, to summarize,
in the transactive setting,
we have training, test,
and validation split, uh,
all on the same graph.
Where data consists of one connected graph.
The entire graph can be observed,
uh, uh, in all the data splits.
So it means all the nodes,
all the edges and all the node features,
uh, but we only split the,
uh, the labels, meaning, uh,
some labels are observed,
other labels- labels are unobserved.
And this, uh, setting is applicable both to node prediction,
uh, as well as edge class- edge prediction tasks.
The inductive setting, which is the training,
validation, and test sets,
are on different graphs.
Uh, the dataset here consists of multiple graphs that are independent from each other.
We only observe the graph structure- note features as well as,
ah, let say node labels,
uh, within the split.
Um, and this allows us to really test how can we generalize to unseen graphs.
The- the drawback of this approach is that we
have to take the original graph and chop it into many,
uh, different, uh, small, uh, pieces.
Uh, and this way we throw away some, uh, graph formation.
This was now in terms of node classification.
Here I give you an example in terms of transductive classification,
you simply split, uh, nodes into training,
uh, validation, and test sets.
Um, in the inductive setting, uh,
we basically- we can assume we have multiple different, uh, graphs, um,
uh, given and we can, um, uh,
take some graphs into the training set,
others in the validation and test set.
If we don't have multiple graphs,
we have to create multiple graphs by basically dropping the edges
or cutting the edges between them so that we get to these different,
uh, connected components and then put them in the training, test,
uh, and validation, uh, set.
So now that we have talked about node classification,
let's switch and let's go to the next, uh,
classification task, which is graph classification.
In graph classification, uh,
induc- inductive setting is well defined because we have independent graphs,
um, and we can simply split them into the training, validation, and test sets.
So basically, we put some graphs into the training set,
some in the validation set,
and some in the test set.
Se here, we basically have independent, uh, graphs.
It's easy to split them,
there is no crosstalk,
there is no information leakage,
um, and this can be done.
Perhaps, um, the trickiest of all the settings,
uh, for machine learning with graphs is link prediction.
Um, and the goal of link prediction is to predict missing edges.
And setting up link prediction requires a bit of thought and it
can be tricky because link prediction is an unsupervised,
uh, or self-supervised task.
We need to create labels and the data splits,
uh, on our own.
So this means that we need to hide some of the edges from
the GNN and let the GNN predict the existing edges.
So the idea is, for example,
if I have the original graph,
I have to hide a couple of edges,
for example, these two red edges,
so that I say this is the input and I want my- my GNN to be able to predict these two,
uh, output, uh, edges, right?
So in some sense, we'll have to take some edges out,
hide them from ourselves and try to, uh, predict them.
So, uh, this is interesting and it creates a bit more complexity because,
um, in a GNN,
we have two types of edges.
We will have the message-passing edges,
so edges that the GNN can use to create the embedding,
and then we'll have these what we'll call supervision edges,
which are the edges that are part of,
let's say, our training, uh, dataset.
So for, uh, link prediction,
we need to split edges twice.
In first step, we assign two types of edges to the original graph.
As I said, some edges we'll call message passing edges.
They are edges used for the GNN to operate over.
And then we'll also call- what we'll call supervision edges.
These are the edges for us to compute the objective function,
loss function, performance of the model, and so on.
Um, and after the step 1, um,
only message edges will remain in the graph and supervision edges are the,
uh, edges that are used for supervision of, uh, edge prediction,
uh, made by the model and will not be used, uh, by the GNN.
Um, so this- this is the first step.
And then in the second step, we split, uh,
edges into train, test, and validation set.
Um, and we have two options.
One is to do what is called inductive link prediction split, where, you know,
we- let's say we have a dataset with three graphs and each split will be,
uh, indepe- will be an independent graph.
So we'll have a training set,
we'll have our validation set and a test set, three different graphs,
and each graph will have a different, um, uh,
split in terms of training,
validation, and test edges, right?
So here this would be the message-passing edges and the supervision edges.
In the second validation graph,
y- you know, we'll have different, um, uh,
supervision edges and different message-passing edges,
and then, in the test set, uh, the same.
So this is, uh,
one way, um, uh, to do this.
Another way to do this is to do this in,
uh, the transductive setting.
And if we do transductive link prediction split, um,
this is generally the default when people talk about link prediction.
And suppose we only have one- one input graph.
What we have to do in this, uh, one,
um, input graph, by definition,
the transductive- of the- uh,
what we mean by transductive learning,
the entire graph can be observed,
uh, for all the datasets' splits.
But since edges are both, uh,
part of the graph structure and the supervision,
we need to hold out, uh,
validation and test edges.
Um, and then to train the training set,
we need to further hold out, uh,
the supervision edges, uh, on the training set.
So let me now, uh,
show you how exactly to do this.
So, uh, for transductive link predict- um, link prediction,
we will take the original graph and we are going to create
a training dataset where we'll have a couple of training edges,
um, er, for message-passing as well as the supervision edges.
At validation time, we are going to use the training edges and the, uh,
training message-passing edges and training supervision edges,
uh, to be able to predict the validation edges.
And then at the test time,
we are going to use the training message edges,
training supervision edges, as well as validation edges to predict the test edges.
So now you can see how, uh,
at training time the graph is sparser,
at the validation time,
we need- we get to see the supervision edges,
but we have to predict the validation edges,
and at the final test time,
we get to see all the edges but the test edges,
and we need to predict,
uh, the test edges.
So here you see how, uh, basically, these,
uh, sets are nested in one another.
So, um, why do we use a growing number of edges?
Because one way to think of this if- is if the graph is evolving over time,
then you could say at some early time,
this was the graph, then it grew by adding this edge.
So that was the graph and it added another edge,
and so on and so forth.
So you can think of this almost like as splitting it along, uh, uh,
uh, three- into thee- three different,
um, time, uh, intervals.
And that's perhaps the best way to define,
uh, link prediction, uh, on a graph.
So to summarize, transductive link prediction split is a bit, um, um,
uh, tricky because we need to take
the original graph and s- and basically have four types of edges.
Training message-passing edges, training supervision edges,
validation edges, as well as,
uh, test edges.
Um, and we have nice,
uh, even though this, you know,
might be a bit cumbersome, uh, to split, uh,
around, uh, this allows us, uh,
to do- uh, to do the- to do things well because we have, uh, good tools,
meaning DeepSNAP and GraphGym that allow us,
uh, to do this, uh, for free, uh, for us.
So, uh, to summarize, uh,
we- we talked about the entire GNN training pipeline from evaluation metrics,
loss functions, labels, as well as, uh, the predictions.
And these are some of the tools, uh,
you can use that allow you to kind of manage these in an end-to-end, uh, fashion.
So to summarize, uh,
we talked about, um, uh,
the GNN layer and how do we define it,
we talked about how to stack different GNN layers together,
and then we also talked about graph augmentation in
terms of feature augmentation and graph structure augmentation,
and what I talked, uh,
now was about learning, uh,
objectives and, uh, how do we,
uh, set up different, uh, tasks.