Stanford CS224W: ML with Graphs | 2021 | Lecture 2.2 - Traditional Feature-based Methods: Link

Summary

The script discusses traditional machine learning approaches for graph-level predictions, focusing on link prediction tasks. It explores two methods: predicting missing links at random and forecasting links over time in evolving networks. The script introduces various features for node pairs, including distance-based, local neighborhood overlap, and global neighborhood overlap metrics, with examples like Katz index to predict future links based on the network's structure.

Takeaways

• 🔍 The focus is on link prediction tasks in graph-level predictions, aiming to predict new links based on existing ones.
• 📈 The task involves ranking all unlinked node pairs at test time and identifying the top k pairs as predicted links.
• 🧠 Key to the task is designing features for node pairs that capture the structure of links in the network.
• 🔗 A simple approach is to concatenate features of two nodes, but this can lose important relational information.
• 📊 Two formulations for link prediction are discussed: 'missing at random' and 'predicting links over time'.
• 🕒 The 'missing at random' formulation assumes links are removed randomly, while 'predicting over time' considers network evolution.
• 📝 Evaluation of predictions is done by comparing the ranked list of predicted links with actual future links.
• 📌 Three types of link level features are discussed: distance-based, local neighborhood overlap, and global neighborhood overlap.
• 🛰 Distance-based features consider the shortest path between nodes but may lack depth in capturing connections.
• 🌐 Local neighborhood overlap features like common neighbors and Jaccard coefficient focus on immediate connections between nodes.
• 🌏 Global neighborhood overlap features, such as the Katz index, consider the entire graph structure for link prediction.

Q & A

What is the main focus of the investigation in the transcript?

The main focus of the investigation is on traditional machine learning approaches for graph-level predictions, specifically link prediction tasks and features that capture the structure of links in a given network.

What is the link level prediction task described in the transcript?

The link level prediction task is to predict new links based on the existing links in the network by evaluating all node pairs that are not yet linked at test time, ranking them, and proclaiming the top k node pairs as predicted links that are going to occur in the network.

How can the importance of information about the relationship between two nodes be lost?

The importance of information about the relationship between two nodes can be lost by simply concatenating the features of the two nodes and training a model on that representation, which often neglects the relational information between them.

What are the two different ways to formulate the link prediction task mentioned in the transcript?

The two ways to formulate the link prediction task are: 1) Assuming links in the network are missing at random, and 2) Predicting links over time in networks that naturally evolve, such as citation, social, or collaboration networks.

How is the performance of a link prediction algorithm evaluated in the context of networks that evolve over time?

The performance is evaluated by looking at a graph between two time points, t0 and t0', and based on the structure up to time t0', outputting a ranked list of predicted links that are expected to occur between times T1 and T1'. The algorithm's predictions are then compared to the actual links that appeared in that future time frame.

What is a feature descriptor for a pair of nodes in the context of link prediction?

A feature descriptor for a pair of nodes is a method to quantify the relationship between the two nodes in such a way that it can be used to predict or learn whether a link exists between them or not.

What is a distance-based feature in link prediction?

A distance-based feature in link prediction refers to the use of the shortest path distance between two nodes to characterize their relationship.

What is the local neighborhood overlap feature and how is it calculated?

The local neighborhood overlap feature captures the number of neighboring nodes shared between two nodes. It is calculated by taking the intersection of the neighbors of the two nodes, and can be normalized using the Jaccard coefficient or adjusted using the Adamic-Adar index.

What is the global neighborhood overlap feature and how does it differ from the local neighborhood overlap?

The global neighborhood overlap feature considers the entire graph structure to score the relationship between a pair of nodes, not just the immediate neighbors. It differs from the local neighborhood overlap by not being limited to two-hop distances and considering all possible paths between nodes.

How is the Katz index computed and what does it represent?

The Katz index is computed using the closed-form expression involving the inverse of the identity matrix minus beta times the adjacency matrix. It represents the global neighborhood overlap by counting the number of paths of all lengths between a pair of nodes, where paths are discounted exponentially with their length.

Why might the assumption of links missing at random not hold true in real-world scenarios?

The assumption of links missing at random might not hold true because in real-world scenarios, such as protein-protein interaction networks, the connections are often not tested at random but are influenced by previous positive results, leading to some areas of the network being more explored than others.

Outlines

00:00

🔗 Link Prediction in Graph Networks

The paragraph discusses the task of link prediction in graph networks, focusing on predicting new links based on existing ones. It emphasizes the importance of designing features for node pairs to capture the structure of links within the network. The speaker outlines two approaches to formulating link prediction tasks: one is treating links as missing at random and predicting them, and the other is predicting links over time in evolving networks. The paragraph also introduces the concept of evaluating these predictions by comparing the predicted links to actual future occurrences.

05:01

📏 Distance-Based and Local Neighborhood Features

This section delves into the specifics of distance-based features for link prediction, such as the shortest path distance between nodes. However, it points out the limitations of such features in capturing the strength of connections. The paragraph then introduces local neighborhood overlap features, like the number of common neighbors and the Jaccard coefficient, which provide a more nuanced view of node relationships. It also mentions the Adamic-Adar index, which adjusts for the degree of common neighbors to better predict links in social networks.

10:08

🌐 Global Neighborhood Overlap Metrics

The speaker addresses the limitations of local neighborhood overlap metrics, which return zero for nodes without common neighbors, potentially overlooking future connections. To overcome this, global neighborhood overlap metrics like the Katz index are introduced. The Katz index considers all paths of varying lengths between nodes, discounting them by their length to give more importance to shorter paths. The paragraph explains how the Katz index can be computed using the powers of the adjacency matrix and provides a formula for its closed-form calculation.

15:11

🔍 Link Level Feature Summary

In conclusion, the paragraph summarizes the different types of link level features discussed: distance-based, local neighborhood overlap, and global neighborhood overlap. It highlights the Katz index as a global metric that accounts for all path lengths between nodes, providing a comprehensive score for potential links. The summary underscores the importance of these features in accurately predicting links in graph networks.

Keywords

💡Link Prediction

Link prediction is the task of predicting the likelihood of links forming between pairs of nodes in a network. It is a central concept in the video, which focuses on predicting future connections in networks like social or citation networks. The script discusses how to evaluate and rank node pairs that are not yet connected to predict potential future links.

💡Node Pairs

Node pairs refer to any two nodes within a network that could potentially be connected by a link. The video script emphasizes the importance of designing features for these pairs to effectively predict new links, which is a core part of the link prediction task.

💡Features

In the context of the video, features are attributes or properties used to describe node pairs for the purpose of machine learning. The script discusses various types of features, such as distance-based and neighborhood overlap features, which are crucial for predicting links between nodes.

💡Graph Level Predictions

Graph level predictions refer to making predictions about the entire structure of a graph or network, rather than individual nodes. The video's investigation into link prediction tasks is an example of graph level predictions, as it considers the network's structure as a whole.

💡Network Structure

Network structure refers to the arrangement of nodes and links within a network. The script discusses how features designed for link prediction must capture the structure of links in a given network to be effective.

💡Common Neighbors

Common neighbors is a local neighborhood overlap feature that counts the number of neighboring nodes shared between two nodes. It is used in the video to illustrate how the number of shared connections can indicate the strength of a potential link between nodes.

💡Jaccard Coefficient

The Jaccard coefficient is a measure used to capture local neighborhood overlap. It is calculated as the size of the intersection divided by the size of the union of the neighborhoods of two nodes. The video uses this coefficient to normalize the count of common neighbors by the total number of neighbors.

💡Adamic-Adar Index

The Adamic-Adar index is another local neighborhood overlap metric mentioned in the script. It sums the inverse logarithm of the degrees of common neighbors, giving more weight to less connected nodes. This index is particularly effective for social networks.

💡Katz Index

The Katz index is a global neighborhood overlap metric that counts all paths of different lengths between a pair of nodes, with paths of greater length being discounted. The video explains how this index can be computed using the powers of the adjacency matrix of a graph.

💡Adjacency Matrix

An adjacency matrix is a square matrix used to represent a network, where the entry at row u and column v is 1 if nodes u and v are connected, and 0 otherwise. The video script uses the concept of the adjacency matrix to explain how to compute path lengths and the Katz index.

💡Graph Evolution

Graph evolution refers to changes in the network over time, such as the addition or removal of nodes and links. The video discusses predicting links over time in evolving networks like social networks, where the structure naturally changes.

Highlights

Investigating traditional machine learning approaches for graph-level predictions.

Focusing on link prediction tasks and features capturing the structure of links in a network.

The task is to predict new links based on existing links in the network.

Evaluating all node pairs not yet linked at test time and ranking them.

Proclaiming the top k node pairs as predicted links by the algorithm.

Designing features for a pair of nodes is key to the link prediction task.

Concatenating features of two nodes may lose important relational information.

Link prediction can be formulated as predicting missing links at random or predicting links over time.

For evolving networks, predicting links between two time points is a natural approach.

Evaluating the approach by comparing predicted links with actual future links.

For static networks, assuming links are missing at random can be useful.

Biologists do not explore protein-protein interaction networks at random, influencing the exploration pattern.

Providing a feature descriptor for a given pair of nodes is crucial.

Scoring pairs of nodes based on the number of common neighbors.

Sorting all pairs according to the score and predicting the top pairs as new links.

Reviewing three different ways to featurize or create a descriptor of the relationship between two nodes.

Discussing distance-based features, such as shortest path distance between nodes.

Local neighborhood overlap features capture the number of shared neighbors.

Global neighborhood overlap features consider the entire graph structure.

Katz index counts all paths of different lengths between a pair of nodes, discounted by their length.

Computing the Katz index in closed form using the inverse of the adjacency matrix.

Transcripts

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.