SimRank

SimRank

Given a directed graph $G = \left< V, E \right>$, the SimRank score $s(i,j)$ for each $i, j \in V$ measures the similarity between vertices $i$ and $j$, defined as thus

$$s(i,j) = \begin{cases} 1, &\text{ if } i = j \\ \frac{c}{|I(i)| |I(j)|} \sum_{a \in I(i), b \in I(j)} s(a,b), &\text{otherwise} \end{cases}$$

where $I(i)$ is the set of in-neighbors of $i \in V$, and $c \in (0, 1)$.

Interpretations

First Meeting Time of Non-Stop Random Walks

$s(i,j)$ can be interpreted as the value of

where $T_{i,j}$ is the random variable of the first time that a reverse random walk (a random walk that travel along the incoming edges of a vertex uniformly at random) from $i$ and a reverse random walk from $j$ meets. Note that

Therefore,

Meeting Probability of $\sqrt{c}$-Random Walks

There is another random walk interpretation fo SimRank:

1. First, notice that when $i \neq j$, [TX16] rewrites the SimRank as

2. Second, [TX16] defines the $\sqrt c$-random walk as

   • In any step, the walk stops with probability $1 - \sqrt c$.
   • With the other $\sqrt c$ probability, the walk chose the in-neighbors of the current vertex uniformly at random.

3. Finally $s(i,j)$ is interpreted as

   The probability of two $\sqrt c$ random walks ever meet, such that one of the random walks starts at vertex $i$ and the other starts at $j$.

Computation

Monte Carlo

A straightforward solution is to perform Monte Carlo simulation to calculate $s(i,j)$--we initialize two $\sqrt{c}$-random walks from $i$ and $j$ respectively, and simulate the two walks until they meet, or either walk stops.

We need not to worry about that this process continues forever. Since the expected number of steps of a $\sqrt c$ random walk is given by

which is a constant.

Chernoff Bound

We repeat this process $t$ times. Let $X_k$ be indicate for the event that the two walks meet in the $k$-th trial. It is easy to see that $X_k, k \in [t]$ is a sequence of i.i.d random variables with $\mathbb{E}[ X_k ] = s(i, j)$.

Let $\bar{X} \doteq (1 / t) \cdot \sum_{k \in [t]} X_k$ and $\mu \doteq s(i,j)$. By Chernoff Bound,

where $\lambda$ is relative error ratio and $\delta$ the error probability we would like to achieve.

Time Complexity

The previous section implies $t = \frac{3 }{ \mu \lambda ^2}\log \frac{ 2 }{ \delta }$. By setting $\epsilon = (1 + \lambda) \mu \Leftrightarrow \lambda = \frac{\epsilon}{\mu} - 1$, we get

Notice that when $\epsilon$ is small, say $0.01$, $\frac{1}{\epsilon^2}$ is large thus can not be neglected. The problem remains whether we could reduce the number of random walks.

Index

Another acute observation from [TX16] is that if two walks reach the same vertex, their following behavior follows the same probability distribution (since the walks are memoryless).

Motivated by this, define $h_i^\ell(k)$ as the hitting probability such that a walk begins at vertex $i$ and reaches vertex $j$ at the $\ell$-th step. $h_i^\ell(k)$ can be updated iteratively using

SimRank and Hitting Probability

Now we consider about bridging the gap between SimRank score and hitting probability.

For each $i, j \in V$, define the indicator $\mathbb{I} (i,j)$ for the event that two $\sqrt{c}$-random walks starting from $i$ and $j$ respectively ever meet.

$\mathbb{I} (i, j, k, \ell)$ the indicator the event that two random walks, starting from $i$ and $j$ respectively, meet at $\ell$-th step at $k$ and this is the last time they meet. In other word, these two walk never meet again after $\ell$-th step at $k$. It is easy to see that for different $k$ and $\ell$, the events indicated by the $\mathbb{I} (i, j, k, \ell)$'s are mutually disjoint. Therefore,

Let $d_k$ be the probability that two walks from $k$ never meet except for the first step. Then

and

Truncation

Notice that for a given $i$, there infinity many $h_i^\ell(k)$'s we need to kept, which is unfeasible. To get around this, we only keep the $h_i^\ell(k)$'s greater than $\epsilon_h$, where $\epsilon_h = O(\epsilon)$.

The probability that the $\sqrt c$-random walk does not to stop before $\ell$-th step is $\sqrt c ^\ell$, i.e.,

For a fixed $\ell$, at most $\sqrt c ^\ell / \epsilon_h$ number of $h_i^\ell(k)$'s are kept. So the total number of $h_i^\ell(k)$'s kept is bounded by

On the other hand, estimation of $d_k$ could be done by monte carlo simulation. By Chernoff bound, we can show that with

samples, $d_k$ could be estimated by $\bar{d_k}$ such that $| \bar{d_k} - d_k| < \epsilon_d$ holds with at least $1 - \delta_d$ probability, where $\epsilon_d = O(\epsilon)$.

Reference

[TX16] Boyu. Tian and Xiaokui. Xiao SLING: A Near-Optimal Index Structure for SimRank. SIGMOD'16