Information about Random walk on Graphs

Presented "Random Walk on Graphs" in the reading group for Knoesis. Specifically for Recommendation Context.

Referred: Purnamrita Sarkar, Random Walks on Graphs: An Overview

Referred: Purnamrita Sarkar, Random Walks on Graphs: An Overview

Agenda • Introduction – Motivation • Background – Graphs – Matrices • Random Walk – PageRank – Personalized PageRank – Topic Sensitive PageRank • Applications – Specifically in Recommender Systems

Random Walk A drunk man will find his way home, but a drunk bird may get lost forever.

Motivation: Link prediction in social networks 4

Motivation: Basis for recommendation 5

Since I had very less slides and More time – Graphs • Undirected Graphs

Since I had very less slides and more time in hand-- Graphs • Directed Graphs

Since I had very less slides and more time in hand – Matrix Rows Columns i j i j k i,j k

Adjacency and Transition Matrix Transition matrix P Adjacency matrix A 1 1 1 1 1 1 1/2 1/2 9

Markov Property (Basic) • Given the present state, the future and past states are independent

Stochastic • Wikipedia: In probability theory, a purely stochastic system is one whose state is nondeterministic so that the subsequent state of the system is determined probabilistically. 1 1 • Matrix – Stochastic Row/Column? 1/2 1/2

Random Walk on Graphs

Random Walk on Graphs

Random Walk on Graphs

Random Walk on Graphs The random sequence of points selected this way is a random walk on the graph

Again: Transition Matrix j k i i j k Transition matrix P Probability? 1 1 1/2 1/2 16

Probability Distributions • xt(i) = probability that the surfer is at node i at time t • xt+1(i) = ∑j(Probability of being at node j)*Pr(j->i) =∑jxt(j)*P(j,i) • xt+1 = xtP = xt-1*P*P= xt-2*P*P*P = …=x0 Pt Matrix Multiplication? • What happens when the surfer keeps walking for a long time? 17

Property of Adjacency Matrix Adjacency matrix A 1 1 1 1

What is a stationary distribution? Intuitively and Mathematically • The stationary distribution at a node is related to the amount of time a random walker spends visiting that node. • Remember that we can write the probability distribution at a node as – xt+1 = xtP • For the stationary distribution v0 we have – v0 = v0 P • Whoa! that’s just the left eigenvector of the transition matrix ! 19

Eigen Value and Eigen Vector?

Interesting questions • Does a stationary distribution always exist? Is it unique? – Yes, if the graph is “well-behaved”. • What is “well-behaved”? – We shall talk about this soon. • How fast will the random surfer approach this stationary distribution? – Mixing Time! 21

Well behaved graphs • Irreducible: There is a path from every node to every other node. What about connected undirected Graph? Irreducible Not irreducible 22

Well behaved graphs • Aperiodic: The GCD of all cycle lengths is 1. The GCD is also called period. Periodicity is 3 Aperiodic 23

Implications of the Perron Frobenius Theorem • If a markov chain is irreducible and aperiodic then the largest eigenvalue of the transition matrix will be equal to 1 and all the other eigenvalues will be strictly less than 1. – Let the eigenvalues of P be {σi| i=0:n-1} in non-increasing order of σi . – σ0 = 1 > σ1 > σ2 >= ……>= σn • These results imply that for a well behaved graph there exists an unique stationary distribution. • More details when we discuss pagerank. 24

Some fun stuff about undirected graphs • A connected undirected graph is irreducible • A connected non-bipartite undirected graph has a stationary distribution proportional to the degree distribution! • Makes sense, since larger the degree of the node more likely a random walk is to come back to it. 25

Proximity measures from random walks b a • How long does it take to hit node b in a random walk starting at node a? --- Hitting time. • How long does it take to hit node b and come back to node a? --- Commute time. 26

Hitting and Commute times b a • Hitting time from node i to node j – Expected number of hops to hit node j starting at node i. – Is not symmetric. h(a,b) > h(a,b) – h(i,j) = 1 + ΣkЄnbs(A) p(i,k)h(k,j) 27

Hitting and Commute times b a • Commute time between node i and j – Is expected time to hit node j and come back to i – c(i,j) = h(i,j) + h(j,i) – Is symmetric. c(a,b) = c(b,a) 28

Random Walk (versions) • PageRank – Personalized PageRank – Topic Sensitive PageRank • Recommender Systems (My interests)

Recommender Networks • For a customer node i define similarity as – H(i,j) – C(i,j) – Or the cosine similarity Lij Lii Ljj • Now the question is how to compute these quantities quickly for very large graphs. – Fast iterative techniques (Brand 2005) – Fast Random Walk with Restart (Tong, Faloutsos 2006) – Finding nearest neighbors in graphs (Sarkar, Moore 2007) 30

PageRank (Initial) • Intuition – PageRank of “A” is higher if the pages that links to “A” has higher PageRank • User behavior where a surfer clicks on links at random with no regard towards content – One page's PageRank is not completely passed on to a page it links to, but is divided by the number of links on the page.

PageRank • Intuitively v (i ) v (j ) i degout ( j ) j • v works out to be the stationary distribution of the markov chain corresponding to the web.

Pagerank & Perron-frobenius • Perron Frobenius only holds if the graph is irreducible and aperiodic. • But how can we guarantee that for the web graph? – Do it with a small restart probability c. • At any time-step the random surfer – jumps (teleport) to any other node with probability c – jumps to its direct neighbors with total probability 1-c. ~ P (1 c )P cU Uij 1 n i , j ~ P cP (1 c)U U ij 1 i, j n 33

Pagerank • We are looking for the vector v s.t. v (1 c ) vP cr • r is a distribution over web-pages. • If r is the uniform distribution we get pagerank. • What happens if r is non-uniform? Personalization 34

Personalized Pagerank1,2,3 • The only difference is that we use a non-uniform teleportation distribution, i.e. at any time step teleport to a set of webpages. • In other words we are looking for the vector v s.t. v (1 c ) vP cr • r is a non-uniform preference vector specific to an user. • v gives “personalized views” of the web. 1. Scaling Personalized Web Search, Jeh, Widom. 2003 2. Topic-sensitive PageRank, Haveliwala, 2001 3. Towards scaling fully personalized pagerank, D. Fogaras and B. Racz, 2004 35

Topic-sensitive pagerank (Haveliwala’01) • Divide the webpages into 16 broad categories • For each category compute the biased personalized pagerank vector by uniformly teleporting to websites under that category. • At query time the probability of the query being from any of the above classes is computed, and the final page-rank vector is computed by a linear combination of the biased pagerank vectors computed offline. 36

Random Walk for Recommendations • Collaborative Filtering by Shang et.al • Graph – Vertices: Users (U), Items (I), Item Information (T) and User Profiles (P) – Edges with weights • • • • u has a rating for i i has a tag for t u belongs to profile category p u to u if they are connected in the social network • Edge weights assignments

Random Walk for Recommendations Connectivity/Transition Generally 0.85 Preference Vector

Most of it from • Purnamrita Sarkar, Random Walks on Graphs: An Overview • Random Walks on Graphs: A Survey, Laszlo Lov'asz • OBVIOUSLY: Wikipedia :D • Random Walk on Graphs: Ankit Agarwal

Thanks

A random walk is a mathematical formalization of a path that consists of a succession of random steps. For example, the path traced by a molecule as it ...

Read more

Random Walks on Graphs Basic Theory Introduction. ... Interpreting the chain as a random walk on a graph, sketch the graph and find a conductance function.

Read more

Random Walks on Graphs: A Survey 3 the asymptotic enumeration of these objects). We’ll survey some of these applications along with a number of more ...

Read more

PageRank and random walks on graphs Fan Chung and Wenbo Zhao University of California, San Diego La Jolla, CA 92093, US ffan,pedu,w3zhaog@ucsd.edu

Read more

Random Walks on Graphs 1. Introduction to Graph Theory The intuitive notion of a graph is a ﬁgure consisting of points and lines adjoining these points.

Read more

Documentation / Algorithms A random walk on a graph Idea. This algorithm create a given number of entities first associated with random nodes in the graph.

Read more

In network science, a biased random walk on a graph is a time path process in which an evolving variable jumps from its current state to one of various ...

Read more

Random walks on quasirandom graphs Ben Barber ∗ Eoin Long † April 3, 2013 Abstract Let G be a quasirandom graph on n vertices, and let W be a random ...

Read more

Random walks on random graphs Martin Barlow Department of Mathematics University of British Columbia Random walks on random graphs – p. 1/24

Read more

Random Walks on Graphs Josep F abrega Journ ees Combinatoire et Algorithmes du Littoral Mediterran een UPC, Barcelona, 7{8 June 2011

Read more

## Add a comment