Stanford CS224W: Machine Learning with Graphs | 2021 | Lecture 4.3 - Random Walk with Restarts

Summary

This lecture explores random walk with restarts and personalized PageRank as extensions of the traditional PageRank algorithm. It discusses their application in recommendation systems, where measuring item similarity is crucial. The concept of teleportation in PageRank is introduced, where a random surfer can jump back to a set of nodes or a single starting node. The lecture explains how these methods can quantify item relatedness in a graph, with the aim of improving recommendations for users based on their interactions with items.

Takeaways

• 🔍 The lecture discusses the concept of random walk with restarts and personalized PageRank as extensions of the initial PageRank algorithm.
• 🛒 It uses the example of an online store or Netflix to illustrate how recommendations can be made based on user-item interactions, forming a bipartite graph.
• 🌐 The goal is to measure similarity or proximity in graphs to recommend items that are related to what a user has already purchased or interacted with.
• 📏 Traditional shortest path measures are not sufficient as they don't account for the strength of connections or the number of common neighbors.
• 🔄 PageRank is introduced as a solution to quantify item relatedness by considering not just the shortest path but also the number of paths and their lengths.
• 🌀 Personalized PageRank differs from standard PageRank by allowing the random walker to teleport back to a subset of nodes (S) that are of interest to the user.
• 🔁 Random walk with restarts is a specific case where the random walker always teleports back to the starting node, effectively measuring proximity to a single node.
• 📊 The process involves simulating a random walk over the graph, increasing visit counts at each step, and restarting with a certain probability.
• 📈 The visit counts can be used to determine the proximity of nodes, with higher counts indicating closer relationships.
• 🔢 The algorithm can be implemented using power iteration, which converges to the node importance vector, representing the limiting distribution of the random surfer's location.
• 💡 The approach is beneficial as it considers multiple factors like the number of paths, strength of connections, and node degrees, making it simple, scalable, and effective.

Q & A

What is the main topic discussed in the script?

The main topic discussed in the script is the concept of random walk with restarts and personalized PageRank as extensions of the initial PageRank idea, particularly in the context of recommendations and measuring similarity or proximity in graphs.

How does the script use the example of a bipartite graph to explain recommendations?

The script uses the example of a bipartite graph to represent the relationship between users and items, such as products or movies. It suggests that if two items are purchased by similar users, they are more related, and thus one item can be recommended to a user who has purchased the other.

What is the purpose of measuring proximity or relatedness in graphs?

Measuring proximity or relatedness in graphs is useful for making recommendations, such as suggesting items to users based on their past purchases or viewing habits, which can increase user engagement and satisfaction.

How does the script differentiate between PageRank, personalized PageRank, and random walk with restarts?

PageRank allows teleportation to any node in the graph, personalized PageRank restricts teleportation to a subset of nodes (S), and random walk with restarts teleports only to a single starting node (S).

What is the significance of the teleport set S in personalized PageRank?

The teleport set S in personalized PageRank represents a subset of nodes that are of interest to the user. It modifies the standard PageRank algorithm to focus on nodes that are more relevant to the user's specific interests or queries.

How does the script relate the concept of a random walk with restarts to the problem of recommendations?

The script relates random walk with restarts to recommendations by simulating a random walk that, with some probability, restarts at a query node. This process can identify items that are more closely related to the query item, which can then be recommended to the user.

What is the role of the parameter alpha in the random walk with restarts process?

The parameter alpha in the random walk with restarts process represents the probability of restarting the walk, which means jumping back to one of the query nodes, thus influencing how frequently the walk restarts and how closely it focuses on the query node.

How does the script suggest measuring the importance of nodes in a graph?

The script suggests measuring the importance of nodes in a graph by simulating a random walk where the nodes with the highest visit counts, indicating proximity to the query nodes, are considered the most important.

What is the mathematical approach discussed in the script to compute the importance of nodes?

The script discusses using power iteration to compute the importance of nodes, which involves representing the bipartite graph with a matrix and iterating to find the leading eigenvector of the stochastic adjacency matrix with teleportation.

What are the benefits of using random walk with restarts for measuring proximity in graphs?

The benefits include the ability to consider multiple paths and connections between nodes, the strength of those connections, and the degree of nodes, making it a comprehensive and scalable method for measuring similarity in graphs.

How does the script connect the intuitions of linear algebra, random walk, and link analysis?

The script connects these intuitions by showing that they all lead to the same optimization problem and can be solved using the same iterative approach, power iteration, which computes the limiting distribution of the random surfer's location representing node importance.

Outlines

00:00

🔍 Introduction to Random Walk with Restarts and Personalized PageRank

The paragraph introduces the concepts of Random Walk with Restarts and Personalized PageRank as extensions of the basic PageRank algorithm. It uses the context of a recommendation system to explain the utility of these algorithms. The speaker discusses the construction of a bipartite graph representing user-item interactions, such as purchases or movie watches. The goal is to measure the similarity or proximity between items in the graph to recommend products or movies to users based on their past interactions. The paragraph highlights the limitations of using only shortest path as a measure of similarity and suggests that a more nuanced metric is needed, which is where PageRank extensions come into play. Personalized PageRank is described as a variation where a 'random surfer' or walker can teleport back to a subset of nodes (S) that are of interest to the user, rather than any node in the graph.

05:05

🛤️ Random Walks with Restarts and Proximity in Graphs

This paragraph delves deeper into the mechanics of Random Walks with Restarts, explaining how each node's importance is distributed among its edges and passed to neighbors. It introduces the concept of a set of query nodes (S) and simulates a random walk over the graph, where the walker can choose to restart the walk by jumping back to any of the query nodes with a certain probability (alpha). The visit count of nodes is used to determine their proximity to the query nodes, with higher counts indicating closer proximity. The paragraph also touches on the pseudocode for this process and mentions an alternative method of computing proximity using power iteration with a stochastic adjacency matrix. The benefits of this approach are highlighted, including its simplicity, scalability, and effectiveness in measuring node similarity by considering various factors such as the number of connections, strength of connections, and node degrees.

10:06

📊 Summary of PageRank Extensions and Their Mathematical Formulations

The final paragraph summarizes the lecture's discussion on PageRank extensions. It contrasts classical PageRank, where the random walker can teleport to any node, with personalized PageRank, where the teleport vector has non-zero elements only for certain nodes, reflecting a user's interests. Random walk with restarts is also described as a special case where the teleportation vector is a single node, always leading back to the starting point. The paragraph emphasizes that despite their different applications, all these formulations can be solved using the same power iteration method. It also explains how a graph can be represented as a matrix and how the random walk process defines a stochastic adjacency matrix. The concept of PageRank as a limiting distribution of the surfer's location, representing node importance, is reiterated. The paragraph concludes by noting the convergence of linear algebra, random walk intuition, and the idea of links as votes into a single optimization problem solved by power iteration.

Keywords

💡Random Walk with Restarts

Random Walk with Restarts is a stochastic process that models a random walker who traverses a graph, with the possibility of returning to a starting node after each step. This concept is central to the video's discussion on measuring similarity or proximity in graphs, particularly in recommendation systems. For instance, if a user has purchased item Q, the algorithm might recommend item P if many users who bought P also bought Q. The script uses this concept to explain how to quantify the relatedness of different items in a graph, suggesting that items with more common neighbors and shorter paths between them are more related.

💡Personalized PageRank

Personalized PageRank is an extension of the traditional PageRank algorithm that allows for a subset of nodes (S) to be defined as interesting to the user, and the random walker is more likely to teleport to these nodes. This concept is used in the video to discuss how recommendations can be tailored to users based on their past behavior and the behavior of similar users. The video explains that in personalized PageRank, the teleport set is not the entire graph but a specific subset of nodes that are of interest to the user.

💡Bipartite Graph

A Bipartite Graph is a type of graph where the set of nodes can be divided into two disjoint sets such that every edge connects a node from one set to a node in the other set. In the context of the video, a bipartite graph represents the relationship between users and items, such as customers and products or movies. The video uses the bipartite graph to illustrate how interactions between users and items can be visualized and analyzed.

💡Proximity

Proximity, in the video, refers to the closeness or similarity between nodes in a graph, which is a measure of how related two items are based on the structure of the graph. It is used to determine which items to recommend to a user, as items that are 'close' or have a high proximity to a user's past choices are more likely to be of interest. The video discusses how different paths and common neighbors can indicate proximity.

💡Teleportation

Teleportation, in the context of the video, refers to the random walker's ability to jump to a different node in the graph, not necessarily following the edges. This is a key feature of the PageRank algorithm and its extensions, where the random walker can teleport to any node (in standard PageRank), a subset of nodes (in personalized PageRank), or a single starting node (in random walk with restarts). The video uses the concept of teleportation to explain how the algorithm can jump back to a node of interest.

💡Eigenvector

An Eigenvector of a matrix is a non-zero vector that does not change its direction after the transformation (multiplication by the matrix). In the video, the Eigenvector is used to represent the limiting distribution of the random surfer's location, which corresponds to the importance of nodes in the graph. The video explains that computing the leading eigenvector of the stochastic adjacency matrix with teleportation can give the same results as running the random walk simulation.

💡Stochastic Adjacency Matrix

A Stochastic Adjacency Matrix is a matrix representation of a graph where each element represents the probability of moving from one node to another. The video discusses how this matrix is used in the random walk process, where the importance of each node is distributed evenly among its edges and pushed to the neighbors, which is analogous to the random surfer model in PageRank.

💡Recommendation System

A Recommendation System is an information filtering system that seeks to predict the 'interest' a user has in an item. The video uses the concept of recommendation systems to explain the practical application of random walk with restarts and personalized PageRank. It illustrates how these algorithms can be used to recommend products or movies to users based on their past behavior and the behavior of similar users.

💡Power Iteration

Power Iteration is an iterative algorithm used to compute the principal eigenvector of a matrix. In the video, power iteration is mentioned as a method to solve for the PageRank values, where the algorithm converges to the limiting distribution of the surfer's location, representing node importance. The video suggests that this method can be used in place of simulating the random walk for more efficiency.

💡Flow Equations

Flow Equations, in the context of the video, refer to the system of equations that describe how the importance of a node is derived from the importance of other nodes that link to it. The video explains that the limiting distribution of the random surfer's location, which represents node importance, can also be found by solving these flow equations using the power iteration method.

Highlights

Introduction to random walk with restarts and personalized PageRank as extensions of the initial PageRank concept.

Example of using graph theory for recommendations in online stores or platforms like Netflix.

Explanation of bipartite graph representation for user-item interactions.

Importance of measuring similarity or proximity on graphs for recommendation systems.

Challenge of quantifying proximity or relatedness of different items in a graph.

Discussion on the limitations of shortest path as a measure of item relatedness.

Intuition behind why personalized PageRank could be a better measure than shortest path.

Definition and explanation of personalized PageRank and its difference from traditional PageRank.

Concept of teleportation in PageRank and how it relates to personalized PageRank.

Introduction to the random walk with restarts as a special case of personalized PageRank.

Explanation of how the teleport set S is defined differently in PageRank, personalized PageRank, and random walk with restarts.

Description of the random walk with restarts process and its significance in measuring node importance.

Graphical illustration of how a random walk with restarts simulates user behavior on a bipartite graph.

Pseudocode explanation of the random walk with restarts algorithm.

Discussion on the benefits of using random walk with restarts for measuring proximity in graphs.

Explanation of how the random walk with restarts can be computed using power iteration.

Summary of the lecture discussing the extensions of PageRank and their applications.

Highlight of the algorithmic efficiency of random walk with restarts in measuring graph proximity.

Final thoughts on the practical applications and scalability of the discussed algorithms.

Transcripts

So we are going to talk about random walk with restarts and personalized PageRank.

And this will be extensions of our initial,

uh, PageRank idea that we have just discussed.

So let me give you an example how this would be very useful.

So we are going to talk about a problem of recommendations.

Imagine you- you have a set of users, customers,

uh, and a set of items,

uh, perhaps products, movies.

And then you create interactions between users and items by

basically saying a given user perhaps purchased a given item,

or a given user watched a given movie, right?

So this is now our bipartite graph representation,

uh, here of this user to item relation.

And then what we want to do is somehow measure similarity or proximity on graphs.

Why is this useful?

This is useful because if you are a online store or if you are Netflix,

you want to ask yourself,

what items should I recommend to a user who,

you know, purchased an item Q.

And the idea would be that if you know two items, P and Q,

are purchased by a lot of, uh, similar users,

a lot of other users have, let say,

bought or enjoyed the same- the same item,

the same movie, then- then whenever a user is looking at item Q,

we should also recommend, uh,

item P. So now,

how are we going to quantify this notion of proximity or

relatedness of different items in this graph.

So the question is, for example,

if I have this graph as I show here,

and I have items, you know,

A and A prime and B and B prime.

The question is which two are more related?

So you could do- one thing to do would be to say,

you know, let's measure shortest path.

So A has a shorter path than B to B-prime,

so, you know, A and A prime are more related.

However, the issue becomes,

is that- that you could then say, oh,

but if I have another example,

let's say this one where I have C and C prime.

And now C and C prime have to users that

bo- that both of let say purchased these two items,

then C and C prime intuitively are more related,

are at closer proximity than A and A prime, right?

So now, the question is,

how would I develop a metric that would allow me to kind of say,

hi, it's kind of the shortest path,

but it's also about how many different, uh,

neighbors you have in

common and how many different paths allow you to go from one, uh, to another.

And they- the idea here is that, er,

PageRank is going to solve this because

in this third example, you know, if you would just say,

let's count common neighbors, then let say, uh,

C and C prime are related as D and D prime.

And again, this is- um,

this is perhaps intuitively not what we want because, er,

you know item D,

this user has enjoyed a lot of different items as well.

This other user has enjoyed a lot of different items there.

So this relationship is less strong than the relationship here because here,

it's really two items,

two items that- that's all- that's all there is.

So, you know, how could we capture this

mathematically algorithmically to be able to run it on networks?

And, uh, this is where the notion of extension of PageRank happens.

Um, so PageRank tells me

the importance of a node on the graph and ranks nodes by importance.

And it has this notion of a teleport where we discuss that- that,

um, a random surfer teleports uniformly over any node in the graph.

So now, we will have- we will first define a notion of what is

called personalized PageRank, where basically,

the only difference with the original PageRank is that whenever we

teleport or whenever the random walker teleports,

it doesn't teleport anywhere in the graph,

but it only teleports,

jumps back to a subset of nodes S. Okay?

So basically, we say, you know,

there is a set of nodes S that are interesting to the user.

So whenever the random walker teleports,

it teleports back to that subset S and not to,

uh, every node in the graph.

And then in terms of, uh,

you know, er, proximity in graphs,

you can now take this notion of

a teleport set S and you can shrink it even further and say,

what if S is a single node?

So it means that the random walker can walk,

but whenever it decides to teleport,

it always jumps back to the starting point

S. And this is what is called a random walk with restart, where basically,

you always teleport back to the starting node S.

So essentially, PageRank, personalized PageRank,

and random walk with restarts are the same algorithm with one important difference,

that in PageRank, teleport set S is all of the nodes of the network,

all having equal probability.

In personalized PageRank, the teleport set S is a subset of nodes,

so you only can jump to the subset.

And in a random walker with restart,

the teleportation set S is

a simple node- is simply one node and that's the starting node,

our, you know, query node item,

uh, Q, uh, from the previous slide.

So let me now talk more about random walks with restarts.

So the idea here is that every node has some importance,

and the importance gets evenly split among all edges,

uh, and pushed to the neighbors.

And this is essentially the same as what we were discussing in,

uh, page- in the original PageRank formulation.

So in our case, we are going to say let's have a set of query nodes.

Um, uh, this is basically the set S. And let's

now physically simulate the random walk over this graph, right?

We will make a step at random neighbor,

um, and record the visit to that neighbor.

So we are going to increase the visit count of that neighbor.

And with some probability alpha,

we are going to restart the walk,

which basically means we are going to jump back to

any of the query nodes and restart the walk.

And then the nodes with the highest query- highest visit count

will have the highest proximity to the- uh,

to the query- to the nodes in the query nodes, uh, set.

So this is essentially the idea.

So let me now show you graphically, right?

So we have this bipartite graph.

Imagine my query nodes set Q is simply one node here.

Then we are going to simulate,

really, like a random walk that basically says,

I'm at Q. I pick one of its,

uh, links at random,

and I move to the user.

Now, I am at the user.

I pick one of the links at random, uh, move to,

uh- to the- to the other side and I increase the visit count, uh, one here.

And now I get to decide do I restart,

meaning go back to Q,

or do I continue walking by picking one of- one link,

um, to go to the user,

pick another link to go back,

and increase the visit count?

And again, ask myself do I want to restart or do want to continue walking?

So the pseudocode is written here and it's really what I just say.

It's basically, you know, pick a random neighbor for- for- for,

uh, start at a- at a query,

pick a random user,

uh, pick a random item,

increase the revisit count of the item,

uh, pick a biased coin.

If the coin says, uh, let restart,

you'll simply, uh, jump back to the query nodes.

You can jump, uh, uniformly at random to any of them,

or if they have different weights,

you can sample them, uh, by weight.

And that is- that is this notion of a random walk, uh, with, uh, restart.

And if you do this, then you will have the query item and then you will also get

this visit counts and- and the idea is that items that are more, uh,

related, that are closer in the graphs,

will have higher visit counts because it means

that the random walker will visit them more often,

which means you have more common neighbor,

more paths lead from one to the other,

these paths are short so that, uh,

the random walker does not decide to restart,

uh, and so on and so forth.

And this allows us to measure proximity in graphs very efficiently.

And here, we are measuring it by actually, uh,

un- kind of simulating this random walk physically.

But you could also compute this using

the power iteration where you would represent this bipartite graph with a matrix, uh,

M, you would then start with, uh, um,

rank vector, um, uh,

to be- to have a given value.

You would then, uh,

transfer them to the stochastic adjacency matrix with teleportation,

uh, matrix, and then round power iteration on top of it.

And it would, um, converge to the same- uh,

to the same set of, uh,

uh, node importance as we- as we show

here by basically running this quick, uh, simulation.

Um, so what are the benefits of this approach?

Um, this is a good solution because it

measures similarity by considering a lot of different,

um, things that are important, right?

It considers how many connections or how many paths are between a pair of nodes.

Um, what is the strength of those connections?

Are these connections direct or are they indirect?

They also- it also considers the- the degree of the nodes on the path.

Because, uh, the more edges it has,

the more- the more likely we- for the random walker,

is to kind of walk away and don't go to the node.

Let's say that- that we are interested in.

So in all these cases, um,

this is a very- uh,

has a lot of properties that we want.

It's very simple to implement,

it's very scalable, and,

uh, works, uh, really well.

So let me summarize this part of the lecture.

So basically, here, we talked about extensions of PageRank.

We talked about classical PageRank where the random walker teleports to any node.

So, you know, if I have a graph with 10 nodes,

then its teleport set S. You can think

of it is- it includes all the nodes and each node has,

uh, equal probability of the random walker landing there.

This is called PageRank.

Then the personalized PageRank,

sometimes also called topic-specific PageRank,

is basically, the only difference is that now

the teleport vector only has a couple of- of non-zero elements.

And this now means that whenever a random walker decides to jump,

you know, 50 percent of the times,

it will jump to this node,

10 percent to this node,

20 percent to this one and that one.

So that's, uh, what is called personalized PageRank.

And then random walk with restarts is again PageRank.

But here, the teleportation vector is a single node.

So whenever the-the surfer decides to

teleport it always teleports to the- to one, uh, single node.

But mathematically, all these formulations are the same,

the same power iteration can solve them.

Uh, we can also solve, for example,

especially the random walk with restarts by actually simulating the random walk,

which in some cases, might be- might be,

um, faster, but it is approximate.

Um, and the same algorithm works,

only thing is how do we define the set S,

the teleportation, uh, set.

So to summarize, uh,

a graph can naturally be represented as a matrix.

We then define the random walk process over, er, the graph.

We have this notion of a random surfer moving across links,

uh, with- er, together with having a-a way to teleport,

uh, out of every node.

This defined- allowed us to define this stochastic adjacency matrix M that

essentially tells us with what probability

the random surfer is going to navigate to each edge.

And then we define the notion of PageRank,

which is a limiting distribution of a- of the surfer location.

Um, and this limiting distribution of the surfer location represents node importance.

And then another beautiful thing happened is that we showed that this

limiting distributions- distribution can be computed or

corresponds to the leading eigenvector of

the transform adjacency matrix M. So it

basically means that by computing the eigenvector of M,

we are computing the limiting distribution of this, uh,

random surfer, and we are also computing this solution to the system of equations,

of, uh, flow equations where the importance of a node is,

you know, some of the importances of the other nodes that point to it.

So all these three different, uh, intuitions.

So the linear algebra, eigenvector eigenvalue,

the Random Walk intuition,

and these links as votes intuition are of the same thing.

They all boil down to the same optimization problem,

to the same algorithm,

to the same formulation that is solved with

this iterative approach called power iteration.