We continue with our investigation of traditional machine learning approaches uh,
to uh, graph level predictions.
And now we have- we are going to focus on
link pre- prediction tasks and features that capture,
uh, structure of links,
uh, in a given, uh, network.
So the link le- level prediction tasks is the following.
The task is to predict new links based on the existing links in the network.
So this means at test time,
we have to evaluate all node pairs that are not yet linked,
uh, rank them, and then, uh,
proclaim that the top k note pairs, as, um,
predicted by our algorithm,
are the links that are going to occur,
uh, in the network.
And the key here is to design features for a pair of nodes.
And of course, what we can do, um, uh,
as we have seen in the node level, uh,
tasks, we could go and, uh,
let say concatenate, uh,
uh, the features of node number 1,
features of the node number 2,
and train a model on that type of, uh, representation.
However, that would be very, um,
unsatisfactory, because, uh, many times this would, uh,
lose, uh, much of important information about the relationship between the two nodes,
uh, in the network.
So the way we will think of this link prediction task is two-way.
We can formulate it in two different ways.
One way we can formulate it is simply to say,
links in the network are,
let say missing at random,
so we are given a network,
we are going to remove, uh,
at random some number of links and then trying to predict,
uh, back, uh, those links using our,
uh, machine learning algorithm.
That's one type of a formulation.
And then the other type of a formulation is that we are going to predict links over time.
This means that if we have a network that naturally evolves over time, for example,
our citation network, our social network,
or our collaboration network,
then we can say, ah,
we are going to look at a graph between time zero and time zero,
uh, prime, and based on the edges and the structure up to this uh,
the time t 0 prime, uh,
we are going then to output a ranked list L of
links that we predict are going to occur in the future.
Let's say that are going to appear between times T1 and T1 prime.
And the way, uh, we can then evaluate this type of approach is to say ah,
we know that in the future, um,
n new links will appear, let's, uh,
let's rank, uh, the- the potential edges outputed by
our algorithm and let's compare it to the edges
that actually really appeared, uh, in the future.
Uh, this type of formulation is useful or natural
for networks that evolve over time like transaction networks,
like social networks, well, edges, uh, keep,
um- keep adding, while for example,
the links missing at random type formulation is more useful, for example,
for static networks like protein- protein interaction networks,
where we can assume,
even though this assumption is actually heavily violated, that, you know,
biologists are testing kind of at random connections between proteins,
um, and we'd like to infer what other connections in the future, uh,
are going for- for biologists are going to discover, uh, in the future,
or which links should they probe with the,
uh- that lab, uh, experiments.
Of course, in reality,
biologists are not exploring the physical, uh,
protein-protein interaction network, uh, um, at random.
Um, you know, they are heavily influenced by positive results of one another.
So essentially some parts of this network suddenly well explored,
while others are very much, uh, under explored.
So with these two formulations, uh,
let's now start thinking about, um,
how are we going to, uh,
provide a feature descriptor,
uh, for a given, uh, pair of nodes?
So the idea is that for a pair of nodes x, y,
we are going to compute some score,
um, uh, c, uh, x, y.
For example, a score, uh,
could be the number of common neighbors between nodes, uh, X and Y.
And then we are going to sort all pairs x,
y according to the decreasing, uh,
score C, um, and we will predict top end pairs as the new links that are going to appear,
uh, in the network.
And then we can end, uh, the test-time, right,
we can actually go and observe which links actually appear and compare these two lists,
and this way determine how well our approach,
our algorithm, um, is working.
We are going to review, uh,
three different ways how to, uh,
featurize or create a descriptor of the relationship between two nodes in the network.
We are going to talk about distance-based features,
local neighborhood overlap features,
as well as global neighbor- neighborhood overlap, uh, features.
And the goal is that for a given pair of nodes,
we are going to describe the relationship, um,
between the two nodes, uh,
so that from this relationship we can then predict or
learn whether there exists a link between them or not.
So first, uh, we talk about distance-based feature.
Uh, this is very natural.
We can think about
the shortest path distance between the two nodes and characterize it in this way.
So for example, if we have nodes B and H,
then the shortest path length between them, uh, equals two.
So the value of this feature would be equal to two.
However, if you look at this, uh, this does,
uh- what this- what this metric does not capture it, it captures the distance,
but it doesn't measure,
kind of capture the degree of neighborhood overlap or the strength of connection.
Because for example, you can look in this network
nodes B and H actually have two friends in common.
So the- the connection here in some sense is stronger between them.
Then for example, the connection between, uh,
node D and, uh, node, uh,
F, um, because they only have kind of- there is
only one path while here there are two different paths.
So the way we can, um,
try to capture the strength of connection between two nodes would be to ask, okay,
how many neighbors, uh,
do you have in common, right?
What is the number of common friends between a pair of nodes?
And this is captured by the notion of local neighborhood overlap,
which captures the number of neighboring nodes shared between two nodes,
v and, uh- v1 and v2.
Uh, one way to capture this is you simply say,
what is the- what is the number of common neighbors, right?
We take the neighbors of node V1,
take the neighbors of node V2,
and take the intersection of these two sets.
Um, a normalized version of this, uh,
same idea is Jaccard coefficient,
where we take the intersection-
the size of the intersection divided by the size of the union.
The issue with common neighbors is that, of course,
nodes that have higher degree are more likely to have neighbors with others.
While here in the Jaccard coefficient, in some sense,
we are norma- we are trying to normalize, um,
by the degree, uh,
to some degree by saying what is the union of the number of,
um, neighbors of the two nodes.
Uh, and then, uh,
the other type of, uh,
uh, local neighborhood overlap, uh,
metric that is- that actually works quite well in practice is called,
uh, Adamic- Adar index.
And simply what this is saying is,
let's go over the,
um- let's sum over the neighbors that nodes v1 and v2 have in common,
and let's take one over the log, uh, their degree.
So basically, the idea here is that we count how many neighbors,
um, the two nodes have in common,
but the importance of uneven neighbor is,
uh- is low, uh- decreases, uh, with these degrees.
So if you have a lot of,
um, neighbors in common that have low degree,
that is better than if you have a lot of high-
highly connected celebrities as a set of common neighbors.
So this is a- a net- a feature that works really well in a social network.
Of course, the problem with, uh, local, um,
network neighborhood overlap is the limitation is that this, uh,
metric always returns zero if two- two nodes are not- do not have any,
uh, neighbors in common.
So for example, in this case,
if we would want to say what is the neighborhood overlap between nodes A and E,
because they have no neighbors in common,
they are more than, um,
uh, two hops away from each other.
Then the- if only in such cases,
the return- the value of that it will be returned to will always be, zero.
However, in reality, these two nodes may still potentially be connected in the future.
So to fix this problem,
we then define global neighborhood overlap matrix.
That is all of this limitation by only, uh,
focusing on a hop- two hop distances and
two-hop paths between a pairs- pair of nodes and consider,
um, all other distances or the entire graph as well.
So let's now look at global neigh- neighborhood overlap type, uh, metrics.
And the metric we are going to talk about is called Katz index,
and it counts the number of all paths, uh,
of all different lengths between a given pair of nodes.
So now we need to figure out two things here.
First is, how do we compute number of paths of a given length,
uh, between, uh, two, uh, nodes?
This can actually be very elegantly computed by
using powers of the graph adjacency matrix.
So let me give you a quick illustration or a quick proof why this is true.
So the uh, first,
I wanna give you the intuition around the powers of adjacency matrix, right?
The point is that what we are going to show is
that computing number of paths between uh, two nodes um,
reduces down to computing powers of the graph adjacency matrix or
essentially taking the graph adjacency matrix and multiplying it with itself.
So first graph adjacency matrix recall,
it has a value 1 at every entry uv if- if nodes u and v are connected.
Then let's say that p,
uv uh superscript capital K counts the number of paths of
length K between nodes u and v. And our goal is to show that uh,
uh, if we are interested in the number of paths uh,
uh, of length K,
then we have to uh,
compute A to the power of k and that entry uv will tell us the number of pets.
The capital K here is the same as uh,
uh, a small case,
so the Kth power of A measures the number of paths of a given length.
And if you think about it right,
how many paths of length 1 are there between a pair of
nodes that is exactly captured by the graph adjacency matrix, right?
If a pair of nodes is connected,
then there is a value 1,
and if a pair of nodes is not connected,
then there is the value 0.
Now that we know how to compute um,
the number of paths of length 1 between a pair of nodes.
Now we can ask how many- how do we compute
the number of paths of length 2 between a pair of nodes u.
And we are going to do this via the two- two-step procedure.
Uh, and we are going to do this by decompose the path of
length 2 into a path of length 1 plus another path of length 1.
So the idea is that we compute the number of paths of length 1
between each of u's neighbors and v,
and then um, add one to that.
So the idea is the following,
the number of paths between nodes u and v of length 1- of length 2 is
simply a summation over the nodes i that are the neighbors of the starting node u,
um, times the number of paths now from
this neighbor i to the target node v. And this will
now give us the number of paths of length 2 between u and v. And now what you can see,
you can see a substitute here back, the adjacency matrix.
So all these is a sum over i,
u- A _ui times A_iv.
So if you see this,
this is simply the product of matrices uh,
of made- of adjacency matrix A_ iu itself.
So this is now uh,
the entry uv of the adjacency matrix A uh, squared.
Um, this is uh,
now by basically by induction,
we can keep repeating this and get a higher powers that count paths of longer lengths um,
as- as this is uh, increasing.
Another way to look at this,
here is a visual proof is that uh,
what is A squared?
A squared is A multiplied by itself,
so when we are interested in a given,
let's say entry, here these are entry,
these are neighbors of Node 1.
These are um, now the,
the number of paths of length 1 between one- one's neighbors and node number 2.
So after the multiplication,
the value here will be 1,
which we mean that there is one path of length 2 between node 1 uh, and Node 2.
So this is how powers of adjacency matrix give
account paths of length K between a pair of nodes uh, in the network.
What this means is that now we can define the- we have developed
the first component that will allow us to count- to compute the cuts index,
because it allows us to count the number of paths between a pair of nodes for a given K.
But what we still need to decide is how do we do this for all the path lengths,
from one to infinity.
So to compute the pets, as we said,
we are going to use powers of the adjacency matrix uh,
you know, uh, the adjacency matrix itself tells us powers of length 1,
square of it tells us power of,
uh squared tells us paths of length 2,
and the adjacency matrix raised to
the power l counts the number of paths of length l between a pair of nodes.
NOW, the Katz index goes over from 1 path lengths all the way to infinity.
So the- the Katz index uh,
global neighborhood overlap between nodes v1 and
v2 is simply a summation of l from one to infinity.
We have this Beta raised to the power of l by basically
a disc- discount factor that gives lower- lower importance
to paths of longer lengths and A to b_l counts
the number of paths of length l between nodes of v1 and v2.
And now what is interesting about Katz index is that, um,
um,uh, we can actually compute this particular expression in a closed-form.
And here is- here is the- the formula for the Katz index again,
and basically what uh,
here is a closed form expression that will exactly compute the sum,
and the reason um,
why this is true or y there is inequality is this.
We notice that this is simply uh,
geometric series uh, for matrices,
and for that there exists
a closed form expression that all that it requires us is take the identity matrix
minus Beta times adjacency matrix inverted that and
then again then subtract the identity matrix again.
And the entries of this matrix S will give us
the Katz neighborhood overlap scores for any pair uh, of nodes.
So to summarize, uh, link level features.
Uh, we- we described three types of them.
We talked about distance-based features that users, for example,
shortest path between a pair of nodes and does not capture neighborhood overlaps.
Then we talked about this neighborhood overlap metrics like common neighbors, Jaccard,
and the Dmitry data that captures find- in a fine-grained wait,
how many neighbors does a pair of nodes have in common?
But the problem with this is that nodes that are more than two hops apart,
nodes that have no neighbors in common,
the metric will return value 0.
So the global neighborhood overlap type metrics,
for example, like Katz, uh,
uses global graph structure to give us a score for a pair of nodes and Katz index counts
the number of pets of all lands between a pair of
nodes where these paths are discounted um,
exponentially with their length.