Supervised Random Walk

This is one of the paper discussed and written in course Social Media Analysis 10-802 in Spring 2011

Citation

Lars Backstrom & Jure Leskovec "Supervised Random Walks: Predicting and Recommending Links in Social Networks"

Online version

Link to paper

Summary

This paper addresses the problem of Link Prediction using the method of Random walk with restart. Supervised Random Walk is interesting because it ranks the nodes based the network information and also using rich node and edge attributes that exist in the dataset. The method is supervised learning task where the goal is to learn the parameters of the function that assigns the strength of the edge (probability of taking that edge) such that a random walker is more likely to reach nodes to which new links will be created in future.

This method is used to recommend friends on Facebook dataset and also in predicting links in collaboration network in arXive database.

Method

Typically, Random walk with restart involves giving probabilities to every edge, which indicate the probability of taking that edge by a random walker given he is at any one of the node on either side of the edge. These probabilities decide which nodes are closer to the node from which we restart our random walks. One simple method that is to assign each edge out of a given node equal probability. However, supervised random walk presented in this paper provides the method to learn the probabilities so that the random walker restarting from node s is more likely to reach the "positive" nodes than "negative" nodes. Positive nodes are the one for which the links were formed in the training dataset and negative nodes are rest all nodes which are not connected the nodes s. The method is formulated into an optimization problem for which an efficient estimation procedure is derived.

Problem Formulation

Given a graph $G=(V,E)$ and the training data which has set of $D$ the positive nodes for which the links were formed by s and all other nodes in the graph to which linked were not formed as $L$. Assume that we are learning the probability assignments for edges with respect to a single s. Each edge $(u,v)$ has a vector of features $\psi _{uv}$, which could be features of the interaction between nodes $u,v$ or could be features on individual nodes $u,v$. Also, if there is a function $f_{w}(\psi _{uv})=a_{uv}$ which is parameterized function that assigns edge strengths or probabilities $a_{uv}$ given feature vector $\psi _{uv}$. The problem formulation is to learn the parameter, $w$ that such that if we do random walk with restarts from s on the graph where the edge strengths are assigned based $f_{w}$, the random walk station distribution $p$ has property that for each $d\in D,l\in L\ \ p_{l}<p_{d}$. This means that are more likely to reach the positive nodes $D$ than nodes in negative set $L$. Hence, the optimization problem is to regularize the parameter vector satisfying this condition, which is given below.

$\min _{w}F(w)=||w||^{2}$

such that

$\forall d\in D,l\in L:p_{l}<p_{d}$

The above formulation is the "hard" constraint that the stationary probabilities of all negative scores should be less than that of a positive node. The constraint is relaxed by introducing an error function $h$ which is such that $h(p_{l}-p_{d})=0$ if $p_{l}-p_{d}<0$ however $h(p_{l}-p_{d})>0$ in case $p_{l}-p_{d}>0$ where the constraint is violated. With this "soft" constraints the following is the an optimization problem formulation

$\min _{w}F(w)=||w||^{2}+\lambda \sum _{d\in D,l\in L}h(p_{l}-p_{d})$

In the above formulation $\lambda$ is regularization parameter that trades-off between the complexity (measured in norm of $w$) for the fit of the model ( how many constraints are violated).

Solving Optimization Problem

In order to solve the optimization problem formulated, the expression is differentiated. Firstly, the loss function $h$ has to be differential and secondly, they derive the relationship between parameters $w$ and random walk scores $p$. The edge strength $a_{uv}=f_{w}(\psi _{uv})$ then the stochastic transition matrix $Q'$ is given as following

$\displaystyle {\begin{array}{lcll}Q'_{uv}&=&{\frac {a_{uv}}{\sum _{w}a_{uw}}}\ &if\ (u,v)\ \in E\\&=&0\ &otherwise\\\end{array}}$

From this stochastic transition matrix $Q'$ we can obtain the transition probability matrix $Q$ when we do Random walk with restart. The following $\alpha$ is the restart probability.

$Q_{uv}=(1-\alpha )Q'_{uv}+\alpha \mathbf {1} (v==s)$

Given this transition probability matrix, the stationary distribution $p$ of Random walk with restart is given by eigenvector equation.

$p^{T}=p^{T}Q$

With this we can find the relation ship between parameters $w$ and stationary distribution $p$. Hence if we differentiate the optimization problem we get the following equation. We can consider $\delta _{ld}=p_{l}-p_{d}$

${\frac {\partial F(w)}{\partial w}}=2w+\sum _{l,d}{\frac {\partial h(p_{l}-p_{d})}{\partial w}}$

${\frac {\partial F(w)}{\partial w}}=2w+\sum _{l,d}{\frac {\partial h(\delta _{ld})}{\partial \delta _{ld}}}({\frac {\partial p_{l}}{\partial p_{w}}}-{\frac {\partial p_{d}}{\partial p_{w}}})$

Now since we know $p$ is principal eigen vector for the transition probability matrix we have $p_{u}=\sum _{j}p_{j}Q_{ju}$ and hence

${\frac {\partial p_{u}}{\partial w}}=\sum _{j}Q_{ju}{\frac {\partial p_{j}}{\partial w}}+p_{j}{\frac {\partial Q_{ju}}{\partial u}}$

In the above equation ${\frac {\partial p_{u}}{\partial w}}$ can be computed by Power Iteration method and ${\frac {\partial Q_{ju}}{\partial u}}$ can be computed using the definition of transition probability matrix.

Optimization problem is then solved using Gradient Descent method and $F(w)$ is minimized.

Datasets Used

This paper for link prediction and link recommendation uses the following two datasets

• Facebook dataset is dataset of Facebook users in Iceland. They chose Iceland, as they have seen the penetration was highest in Iceland and hence new links were formed more rapidly than other countries.
• Collaboration network in arXive database.

Experiments

The paper does experiments of ranking the nodes using the supervised random walks both on synthetic dataset and real world dataset.

Experimental Setup

The following are some of the general considerations of loss function, edge strength function, choice of $\alpha$ and regularization parameter $\alpha$

Edge Strength Function

Edge strength function with a parameter $w$ takes as input the feature vector $\psi _{uv}$ and outputs the edge strength. The following are some possibility of the edge strength

• Exponential edge strength: $a_{uv}=exp(\psi _{uv}\cdot w)$
• Logistic edge strength: $a_{uv}={\frac {1}{1+exp(-\psi _{uv}\cdot w)}}$

Loss Function

As said earlier we need to consider loss function $h$ such that it is differentiable. The following are some of th possible loss functions considered

• Squared loss with margin:

$h(x)=\max\{x+b,0\}^{2}$

• Huber loss with margin b and window z > b

${\begin{array}{lcll}h(x)&=&0&if\ \ x\leq -b\\&=&(x+b)^{2}/(2z)&if\ \ -b<x\leq z-b\\&=&(x+b)-z/2&if\ \ x>z-b\\\end{array}}$

Choice of $\alpha$

The choice of $\alpha$ decides how far we do the random walk before we restart our random walk from s. As $\alpha$ approaches 1, the random walks crossing more than 2 hops becomes increasingly unlikely.

Regularization parameter $\lambda$

This parameter controls the over-fitting of the model, and in this paper they set $\lambda =1$ which gave best performance.

Experimental Results

Synthetic dataset

They generate a scale-free graph with 10,000 nodes. For each edge $(u,v)$ they create two independent Gaussian features with mean 0 and variance 1. The strength of each edge is given by $a_{uv}=exp(\psi _{uv1}-\psi _{uv2})$ and hence $w*=[1,-1].$. On this graph they run the experiment with $\alpha =0.2$ and obtain the PageRank scores $p^{*}$. Using these scores they pick the destination nodes or positive nodes in two ways. First, is to pick the top K nodes and second way is to pick K nodes with probability equal to their scores. They also add the Gaussian noise to the features and vary the noise and verify the performance.

They generate 100 graphs using the way explained above and use 50 graphs for learning the parameters and 50 graphs to test the performance. The measure of performance is AUC (area under the curve) which measures the accuracy of the prediction, AUC = 1 meaning the prediction were perfect. The Figures shown below provides the performance measures both in case of deterministic top K nodes and probabilistic top K nodes. The un-weighted version is the case where we assign equal weight to all the edges. We can see that performance of the learned graph(blue) is better than the un-weighted version (red) and most importantly as the noise increases the learned parameters performs better then the true parameters (green) both in case of deterministic and probabilistic ways.

Real world dataset

They run it on both the Facebook dataset and arXive database dataset and show that the performance of the supervised random walk is better than doing a typical Random walk with restart method, or a logistic regression with the network features extracted out to predict the nodes for which a given s gets linked to. As the number of nodes in the graph get really high, they consider the nodes that are not very far in terms of number of hops as potential candidates so that the method does not bloat up the size of transition matrix.

Conclusion

Supervised random walk algorithm, takes into consideration both network structures and features of the nodes/edges, therefore has better performance than a typical Random walk with restarts which assigns all the equal weight. The problem is formulated as an optimization problem and is solved using gradient descent. Experiments were done on synthetic dataset and on real world Facebook and co-authorship dataset and shown that it performs better. This can be applied to various other applications like Link recommendation, ranking nodes in the graph, missing link analysis.