FORA [1] — Hao Wu

Suppose that we know the values of $\pi^o(s, t)$ for all $t \in V$ and $r(s, v_i)$ for all $v_i \in V$ . We would like to evaluate the value of

\pi(s, t) = \pi^o(s, t) + \sum_{i = 1}^n r(s, v_i) \pi(v_i, t)

where $\pi(v_i, t)$ denotes the probability of a random starts from $v_i$ and terminate at $t$ . Let $\tilde \pi(v_i, t)$ be our estimation of $\pi(v_i,t)$ , then we have an estimation of $\pi(s, t)$ :

\tilde\pi(s, t) = \pi^o(s, t) + \sum_{i = 1}^n r(s, v_i) \tilde\pi(v_i, t)

To get $\tilde\pi(v_i, t)$ , we perform $w_i$ (a value to be determined latter) random walks that start from $v_i$ and count the fraction of walks that terminate at $t$ . Formally, let $X_{i, j}$ be a Bernoulli random variable that takes value 1 if the $j$ -th walk from $v_i$ terminates at $t$ . Then

E[X_{i,j}] = \pi(v_i, t)

Let $\tilde \pi(v_i, t) = \frac{1}{w_i} \sum_{j = 1}^{w_i} X_{i,j}$ , so

E[r(s, v_i) \tilde \pi(v_i, t)] = \frac{r(s, v_i)}{w_i} \sum_{j = 1}^{w_i} E[X_{i,j}] = r(s, v_i) \pi(v_i, t)

A naïve use of Chenoff bound to us $w_i = \Omega(\frac{\log (1 / p_{fail} ) }{\epsilon^2 \pi(v_i, t)} )$ (which is even worse than evaluating $\pi(s, t)$ by Monte Carlo directly), such that $r(s, v_i) \tilde \pi(v_i, t)$ takes value within $\big[(1 - \epsilon) r(s, v_i) \pi(v_i, t), (1 + \epsilon) r(s, v_i) \pi(v_i, t)\big]$ with probability $1 - p_{fail}$ . The problem here is that when $\pi(v_i, t)$ is small, we need large number of random walks to get a good approximation of it. On the other hand, when $\pi(v_i, t)$ is small, the contribution of $r(s, v_i)\pi(v_i, t)$ to $\sum_{i = 1}^n r(s, v_i) \pi(v_i, t)$ is small, which means that more deviation is allowed on the estimation of $\pi(v_i, t)$ .

What if the amount of deviation on the estimation of $r(s, v_i) \pi(v_i, t)$ we allow is $\pi(s, t)$ ? How about $\pi(s, t) / n$ ? More clever way of allocating deviation? Better Chernoff bound?

[1] solves this by bounding the cumulative deviation of $\sum_{i = 1}^n r(s, v_i) \tilde \pi(v_i, t)$ as a whole. The statistical tool it turns to is a special Chernoff bound:

Theorem

Let $Y_1, Y_2, ..., Y_w$ be independent random variables with
$Pr[Y_i = 1] = p_i \qquad Pr[Y_i = 0 ] = 1 - p_i.$
Let $Y = \frac{1}{w} \sum_{i = 1}^w b_i Y_i$ with $b_i > 0$ , and $v = \frac{1}{w} \sum_{i = 1}^w b_i^2 p_i$ . Then
$Pr[|Y - E[Y]| \ge \lambda ] \le 2 \exp \big(-\frac{\lambda^2 w} {2 v + 2 b \lambda / 3} \big)$
where $b = \max\{ b_1, b_2, ..., b_w\}$

To apply this bound, we perform in total $w = \sum_{i = 1}^n w_i$ random walks. The first $w_1$ walks starts from $v_1$ , the next $w_2$ walks starts from $v_2$ , and so on. Let

\{ Y_{1}, ..., Y_{w_1}, Y_{w_1 + 1}, ..., Y_{w_1 + w_2}, ..., Y_{\sum_{i = 1}^{n -1}w_i + 1}, ..., Y_{w} \}

be the corresponding independent indicator random variables that take value 1 if the walks terminate at $t$ and

b_j = \frac{w}{w_i} r(s, v_i)

if the $j$ -th walk starts from vertex $v_i$ . So

b = \max \{b_1, b_2, ..., b_w\} = \max_{1 \le i \le n} \frac{w}{w_i} r(s, v_i)

It can be verified that

E[Y] = \frac{1}{w} \sum_{i = 1}^w E[Y_i] = \frac{1}{w} \sum_{i = 1}^n \sum_{j = 1}^{w_i} \frac{w}{w_i} r(s, v_i) \pi(v_i, t) = \sum_{i = 1}^n r(s, v_i) \pi(v_i, t)

To bound the deviation of $\tilde \pi(s, t)$ from $\pi(s, t)$ , we notice that

|\tilde \pi(s, t) - \pi(s, t)| = | \sum_{i = 1}^n r(s, v_i) \tilde \pi(v_i, t) - \sum_{i = 1}^n r(s, v_i) \pi(v_i, t)| = |Y - E[Y]|

Pr[|Y - E[Y]| \ge \epsilon \pi(s, t)] \le 2 \exp ( - \frac{ \epsilon^2 \pi^2(s, t) \ w}{2 v + 2 b \epsilon \pi(s, t) / 3})

But notice that

v = \frac{1}{w} \sum_{i = 1}^w b_i^2 p_i \le \big( \frac{b}{w} \sum_{i = 1}^w b_i p_i \big) = b \ E[Y] \le b \ \pi(s, t)

Thus

\begin{align} Pr[|Y - E[Y]| \ge \epsilon \pi(s, t)] &\le 2 \exp ( - \frac{ \epsilon^2 \pi^2(s, t) \ w}{2 v + 2 b \epsilon \pi(s, t) / 3}) \\\\ &\le 2 \exp ( - \frac{ \epsilon^2 \pi^2(s, t) \ w}{2 b \pi(s, t) + 2 b \epsilon \pi(s, t) / 3}) \\\\ &\le 2 \exp ( - \frac{ \epsilon^2 \pi (s, t) \ w}{b (2 + 2\epsilon / 3)}) \\\\ &\le p_{fail} \end{align}

w \ge b \frac{2 + 2\epsilon / 3}{\epsilon^2 \delta} \log \frac{2}{p_{fail} }

We would like to minimize $b$ in order to minimize $w$ , which can be formulated as an convex optimization problem:

\begin{align} \min \quad &b \\\\ s.t. \quad &b \ge r(s, v_i) / k_i \\\\ &\sum_i k_i = 1 \\\\ &k_i \ge 0 \end{align}

Here we rewrite $\frac{w_i}{w} = k_i$ . One simple way to solve this is to guess that $b$ is minimized when all ${r(s, v_i)}/{k_i}$ equals. This gives $k_i = r(s, v_i) / r_{sum}$ . We can prove this is indeed optimal: if this is not the case, there must be some $k_i < r(s, v_i) / r_{sum}$ . Then $b \ge r(s, v_i) / k_i > r_{sum}$ .

We can also solve this problem by a heavy mechanism: KKT conditions. First, define

L(b, k, \lambda, \beta, , \mu) = b + \sum_{i = 1}^n \lambda_i (r(s, v_i) / k_i - b) + \sum_{i = 1}^n \beta_i (0 - k_i) + \mu (\sum_{i = 1}^n k_i - 1)

Thus, the KKT conditions are

\begin{align} & r(s, v_i) / k_i - b \le 0 &\forall i \in [1, n] \\\\ & -k_i \le 0 &\forall i \in [1, n] \\\\ & \sum_i k_i - 1 = 0 \\\\ & \lambda_i \ge 0, \beta_i \ge 0 &\forall i \in [1, n] \\\\ & \lambda_i (r(s, v_i) / k_i - b) = 0 &\forall i \in [1, n] \\\\ &\beta_i (0 - k_i) = 0 &\forall i \in [1, n] \\\\ & \frac{\partial L}{\partial b} = 1 - \sum_{i = 1}^n \lambda_i = 0 \\\\ & \frac{\partial L}{\partial k_i} = -\lambda_i r(s, v_i) / k_i^2 - \beta_i + \mu = 0 &\forall i \in [1, n]\\\\ \end{align}

So one solution is given by

\begin{align} &b = r_{sum} \\\\ &k_i = r(s, v_i) / r_{sum} & \forall i \in [1, n] \\\\ &\lambda_i = r(s, v_i) / r_{sum}^2 & \forall i \in [1, n] \\\\ &\beta_i = 0 & \forall i \in [1, n] \\\\ &\mu = 1 \end{align}

which implies

w \ge b \frac{2 + 2\epsilon / 3}{\epsilon^2 \delta} \log \frac{2}{p_{fail} } \\\\ w_i = w k_i = \frac{w r(s, v_i)}{r_{sum} }

Citations

[1] Wang, Sibo, et al. "FORA: Simple and Effective Approximate Single-Source Personalized PageRank." Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2017.