Now, we are going to talk about embedding entire graphs.
So rather than embedding individual nodes,
we're going to talk about how do you embed,
or find an embedding for an entire graph.
And the method we are going to talk about is based on anonymous, uh, random walks.
So we are going to continue the theme of, uh,
random walks, but this random walks will be anonymous.
So let me explain. All right?
The goal now is to embed a sub-graph or
an entire graph into the embedding space, uh, z. Um,
and, uh, you may wanna do these because you may wanna do for example,
molecule classification to predict which molecules are toxic versus which are non-toxic.
Or you wanna do some kind of graph anomaly detection,
um, and you want to do this in the embedding space.
So the goal is to embed an entire graph or you can think of it
also as embedding a subset of the nodes in the graph.
So first idea, that is very simple and people have tried.
So the idea is that you run standard node embedding,
uh, uh, technique, uh,
like we- what- like we already dis- discussed in terms of node to walk or, uh, deep walk.
And then, just sum up or average, uh,
node embeddings, either in the entire graph,
or in the sub-graph, right?
So the idea is, um, to say,
the embedding of the graph is simply a sum of the embeddings of the nodes in that graph.
And for example, this method was used in 2016, to classify,
uh, molecules, uh, based on the graph structure,
and it was very, um- very successful.
So even though simplistic,
um, uh, works quite well in practice.
An improvement over this initial idea of averaging node embeddings is
to introduce a virtual node to represent an entire graph or a sub-graph,
and then run a standard graph embedding or node embedding technique,
uh, and then think of the- this virtual node as the embedding for the graph.
So let me explain.
Uh, here is the idea, right?
I will create these virtual node.
I will connect it to the set of nodes I want to embed.
Now I can run node to walk on this,
uh- on this, um- on this graph to determine the embedding of this virtual node.
And, uh, now the embedding of the- of the- of the let's say set of nodes s,
is simply the embedding of this, uh, virtual node,
um, in the embedding space as computed by deep walk or,
uh, node to walk.
And of course, if I would want to embed the entire graph, then this,
uh, virtual node would connect to all other nodes in the network.
I'd run, uh, deep walk,
uh, or an node to walk over this,
determine the embedding of the virtual node and
represent the embedding of the entire graph as the embedding,
uh, of the red node.So that's,
um, idea number, uh, 2.
Now, for idea number 3,
we are going to define this notion of anonymous, uh, walks.
And the way we will think of this is that states in
the anonymous walk correspond to the indexes
of the first time when a given node was- was visited,
uh, on the walk.
So for example, here is a- here is a graph,
uh, uh, you know, a small subpart of the graph of interest.
Then here are a few random walks on this graph.
For example, from A we go to B,
C, B, uh, and C,
or another random walk starts at C, goes to D,
goes to B, goes to D,
and back to B.
But then we are not going to represent the random walk as a sequence of nodes it visits,
but a sequence of times when node was first visited.
So for example, these two random walks,
one and two here, get the- get the same representation.
It is one because A was visited at step 1,
then it's two because B was visited at step 2.
Then it's three because node C was visited at step 3,
then we visited B again,
but B was already visited so it doesn't get a new- new,
uh, index, but it gets value 2.
And then we went back to C. So, um,
so again, um, we have, uh, number 3.
And then this other random walk that started at C went to D,
B, D, B, um,
gets actually the same sequence, right?
C gets one, uh,
D gets two, B gets three.
Then we go back to D. So it's again two,
and then we go to B and it's again three.
And then for example, this other random walk now has
a different anonymous representation because we go from A to B to A to B to D, right?
So it's 1, 2, 1, 2, uh,
3 because at time 3 or, uh,
node D was visited as a third node, uh, in the graph.
So, uh, this anonymous walks,
uh, basically this is,
uh- this is- they are agnostic to the identity of the nose,
of the nodes visited.
That's why they're called anonymous.
Um, and this means that node- that random nodes that have visited the different nodes,
but kind of in the same order that get the same anonymous walk representation.
Now, uh, you may wonder how- how does the number of walks,
uh, increase with the length?
The number of possible anonymous walks increases exponentially.
Uh, here's- here's the graphic for example,
for- there are five anonymous walks of length 3. You know, here they are.
You can basically stay at the same node three times.
You can go- you can stay two times at the same node and then navigate to the second node.
You can go from first node to the second,
back to the first.
You can go from first to the second, stay on the second,
or you navigate from node 1 to node 2 to node 3.
And these are the five possible anonymous walks of length 3.
And then, you know, of length 4, uh,
it will be- it will be more,
that would be 15.
And of length 12, that would be,
I know, four million as it shows here.
So how are we going now to embed a graph?
One idea is to simply simulate anonymous walks of length L, uh,
and record their counts and then represent
the graph as a probability distribution over these walks.
So for example, if I pick anonymous walks of length 3,
then we can represent a graph as a five dimensional vector
because there are five different anonymous walks of length 3.
As I explained earlier,
where, uh, you know,
the embedding of the graph, uh,
the ith coordinate of that embedding is simply the probability that anon-, uh,
the probability or the fraction of times anonimou-
anonymous walk of type I has occurred in
the graph G. So now this would basically mean that we are
embedding a graph as a five dimensional representation.
Now if you want higher number of dimensions,
you increase the length, uh,
of the anonymous, uh, walk.
That's the idea for the- for the anonymous walks, uh,
and how you can basically count them and then have a probability distribution over the,
uh, fraction of times each anonymous walk occurs on your graph.
You, uh, uh, said that the dimensionality of the presentation by basically setting,
uh, the- the length of the,
uh, anonymous, uh, walk.
Now, of course the question also becomes,
how- how many random walks do you need?
And that is very nice mathematical formula that
tells you how many anonymous walks you wanna
sample such that your estimates in
the frequency or the probabilities of occurrence are, uh, accurate.
And you can quantify accuracy by two parameters,
Epsilon, um, and, um, and Delta, uh,
where basically we say we want the distribution of these, uh, uh,
probabilities of anonymous walks to have error of no more than Epsilon,
with probability, uh, less than Delta.
You can plug in these two numbers into
the following equation and that will tell you the number of,
uh, anonymous walks you may wanna,
uh, you may need to sample.
So for example, if you consider anonymous walk of length 7,
there is 877 of them.
If you set the Epsilon to 0.1 and Delta to, uh, 0.01,
then you would need to sample about 120,000, uh,
random walks that you can estimate this probability distribution over this,
er, 877, uh, different, uh, anonymous walks.
So that's the idea in terms of anonymous walks.
And, um, we can further, um,
enhance this idea, uh,
to actually learn embeddings of the walks themselves.
So let me explain how we can do this.
So rather than simply representing each walk by the fraction of time it occurs,
we can learn an embedding Z_i of anonymous walk W_i.
And then we can learn also our graph embedding
Z- Z_G together with the anonymous walk, uh, embeddings.
So this means, uh,
for a- for a- we are going to learn- the number of embeddings we're going to learn,
will be the number of anonymous walks plus 1 because
we are learning an embedding for every anonymous walk plus the embedding,
uh, for the graph.
Right? So again, how are we going to learn
these embeddings of graph and the anonymous walks?
We can- we do this in a very similar way to what we did for DeepWalk or node2vec.
We wanna embed walks so that,
uh, walks adjacent to it can be predicted.
So let me explain the idea.
So the idea is that again,
we will have this vector G that describes the graph.
We are going to have the, uh,
and this will be the embedding of the entire graph we are going to learn.
Let's say we start from some no- node 1 and we sample anonymous,
uh, random walks from it.
So then the idea is to learn to predict walks that co-occur in some, uh, uh,
uh, Delta window size, um, um,
around as we are sampling this random walks,
uh, from a given node.
So the idea is that the objective function is we wanna go,
um, over this window size Delta,
where this W_t are random wa- are anonymous random walks that all start at,
uh, at a starting node 1 and,
uh, Z_G is the embedding of the graph.
And now we basically sum these-
these objective over all starting nodes, uh, in the graph.
So the idea is that we will run T different random walks from each, uh,
node u of length l. So now our notion of neighborhood is not a set of nodes,
but it's a set of anonymous,
uh, random walks, uh,
here labeled by W. And then we want to learn to predict walks
that co-occur in a window of size, uh, Delta.
So the idea is that you wanna em- em- estimate
the embedding Z_i on anony- of anonymous walks W_i,
um, and then, uh,
maximize these given objective where basically we go over, uh,
er, all the random walks that we run from the- from the- from the given node.
Uh, this- this is a sequence of random walks that occ- or anonymous walks that occurred.
Our goal is to find the embedding of the graph as well as the embeddings of
the anonymous walks so that we can predict what is the next anonymous walk,
what is the identity of the next anonymous walk that is going, uh,
to occur in these, uh,
in these sampling of anonymous walks.
So essentially this is the same objective function as we used in note to record DeepWalk,
but the difference is the following,
is that when we are defining this notion of neighborhood,
we don't define neighborhood over the nodes that are visited,
but we define it over the, uh,
anonymous walks that occur,
uh, starting from node u.
So here W is an entire anonymous walk,
it's an ID of an anonymous walk.
If you want more details and, uh,
and read more there was- there is a paper link
down here that you can read for further details.
But the idea here is right that- now that we have learned
both the embedding of the node as well as the embedding of the walks,
we can- sorry, as we learn the embedding of the graph,
you can use these, er, er,
Z_G as a- as
a descriptor of the graph and we can use it in downstream prediction task, right?
So to summarize, we obtain the graph embedding, uh, Z_G,
which is learnable after this optimization,
and then we can use Z_G to make predictions for example, for graph classification.
We can use, uh,
the dot product the same way as we were using so far,
or we could use a neural network that takes, er, er,
Z_G as an- as an input into our classifier and tries to predict some label this,
uh, graph G. Uh, both options,
uh, are, er, feasible in this case.
So in this, ah, part of the lecture,
we discussed three ideas about how to embed entire graphs.
First was simply average or sum up embeddings of the nodes in
the graph where the embeddings of the nodes are computed by DeepWalk or, um, node2vec.
The second idea was to create a super-node that spans
the subgraph of interest and that embed that super-node.
And then the idea number 3 was to use this notion of anonymous walk embeddings,
uh, where do we sample anonymous, uh,
walks, um, to represent graph as a fraction of times each anonymous walk occurs,
so that's one idea.
And the second more complex idea was to embed anonymous walks and then,
um, either, for example,
concatenate their embeddings or use these Z- Z_G to define the notion,
uh, of the embedding of the entire graph.
What we are going to, um,
consider in the future is also more, um,
er, different approaches to graph embeddings, and in particular,
many times graphs tend to have this type of community or
cluster structure so it becomes a good question how do we hierarchically aggregate,
um, the- the network, er,
to obtain the embedding,
uh, of the entire graph.
And later in Lecture 8,
I'm going to discuss such a- such an approach that uses,
uh, graph neural networks,
uh, to be able to do this.
So, um, to- to conclude,
to keep kind of towards- moving towards the ends of the lecture,
the next question is,
you know, how do we use these embeddings Z_i of the node for example?
Um, you can use them, for example,
to cluster, uh, the points.
Basically, you take the graph, compute the embeddings,
and then run a clustering algorithm over the embeddings, for example,
the do community detection or any kind of social rolling identification.
Uh, you can use these embeddings for a node classification.
Simply predict the label of node i based off it- it's embedding Z. Um,
and you can also use them for, uh,
link prediction where basically you can think nodes, uh,
i and j and you can concatenate their embeddings and then,
uh, based on the concatenation,
uh, you can make a prediction.
When, um, when you are combining this node embeddings,
you have several options.
As I said, one is simply concatenating them, uh,
another option would be to combine them by doing per coordinate product.
Uh, this is- this is nice for undirected graphs because this operation is commutative.
Um, you can also sum or average them.
Another communi- commutative operation meaning that, you know,
probability of link from i to j is the same as from j to i. Um,
or you could measure some kind of L2 distance and then make a prediction
based on these kind of different aggregations of the two- of the two embeddings.
If you wanna make predictions in directed graphs,
then concatenation is nice because you are able to
output a different probability depending on,
you know, is it from i to j or from j to i?
For graph classification, node embedding,
uh, ah, can be computed via aggregating, uh,
node embeddings or through anonymous walks or through this anonymous walk embedding plus,
uh, the graph, ah,
embedding approach, uh, that we have discussed.
So, uh, to summarize,
today, we discussed, um,
graph representation learning as a way to learn node and graph embeddings, uh,
independent of downstream prediction tasks and without any manual feature engineering.
We had discussed this encoder decoder framework, where encoder,
you simply an embedding lookup and decoder
predicts the score or network-based similarity,
uh, based on the pos- the embeddings of the nodes.
Um, and we defined, uh,
notion of node similarity based on the random walks.
We discussed two methods,
DeepWalk and node2vec that use the same optimization problem,
the same negative sampling approach, uh,
but DeepWalk uses a very simple random walk,
basically a first-order random walk while node2vec
uses a second-order random walk that can- where you can kind of,
uh, fine tune the way the network is explored.
Um, and then we also discussed extensions, uh,
to, uh, graph embeddings, um,
which means that we can simply aggregate
node embeddings and we also talked about anonymous, er, random walks,
where the anonymous random walk represents the walk not by the identities of the nodes,
but by the time or by the index at
what ti- at what time a given node was first, uh, visited.
So, uh, these are- this is a set of approaches,
um, I wanted to, uh, discuss today.
Um, and thank you very much for watching and,
uh, attending the lecture.