1 Introduction

The idea of using hyperlink mining algorithms in Web search engines appears since the beginning of the success of Google′s PageRank [24]. Hyperlink based methods are based on the assumption that a hyperlink implies that page votes for as a quality page. In this paper we address the computational issues [13,17,11,12] of personalized PageRank [24] and SimRank [16]. 字串9

Personalized PageRank (PPR) [24] enters user preferences by assigning more importance to the neighborhood of pages at the user′s selection. Jeh and Widom [16] introduced SimRank, the multi-step link-based similarity function with the recursive idea that two pages are similar if pointed to by similar pages. Notice that both measures are hard to compute over massive graphs: naive personalization would require on the fly power iteration over the entire graph for a user query; naive SimRank computation would require power iteration over all pairs of vertices.

We give algorithms with provable performance guarantees based on computation with sketches [7] as well as simple deterministic summaries; see Table 1 for a comparison of our methods with previous approaches. We may personalize to any single page from which arbitrary page set personalization follows by linearity [13]. Similarly, by our SimRank algorithm we may compute the similarity of any two pages or the similarity top list of any single page. Motivated by search engine applications, we give two-phase algorithms that first compute a compact database from which value or top list queries can be answered with a low number of accesses. Our key results are summarized as follows: 字串8

We give practical methods for serving unrestricted on-line personalized PageRank (Section 2.1) as well as SimRank queries with space a reasonable constant per vertex (Section 3). The methods are based on deterministic rounding.

We give a theoretically optimal algorithm for personalized PageRank value queries (Section 2.2) based on randomized sketching. Given an additive error and the probability of an incorrect result, we improve the disk usage bound from [11,12] to .

We give theoretically optimal algorithms for SimRank value and top list queries (Section 3.1) by a nontrivial reduction of SimRank to personalized PageRank.

We improve the communication complexity based lower

字串1

bounds of [11,12] for the size of the database (Section 4); our bounds are matched by our algorithms. Our sketch-based algorithms use optimal space; surprisingly for top list queries deterministic rounding is already optimal in itself.

In Section 5 we experimentally analyze the precision of approximation over the Stanford WebBase graph and conclude that our summaries provide better approximation for the top personalized PageRank scores than previous methods.

Table 1: Comparison of personalized PageRank algorithms for graphs of vertices, additive error and error probability .

字串8

1.1 Related Results

The scalable computation of personalized PageRank was addressed by several papers [13,18,17] that gradually increase the choice for personalization. By Haveliwala′s method [13] we may personalize to the combination of 16 topics extracted from the Open Directory Project. The BlockRank algorithm of Kamvar et al. [18] speeds up personalization to the combination of hosts. The state of the art Hub Decomposition algorithm of Jeh and Widom [17] computed and encoded personalization vectors for approximately 100K personalization pages.

字串4

To the best of our knowledge, the only scalable personalized PageRank algorithm that supports the unrestricted choice of the teleportation vector is the Monte Carlo method of [11]. This algorithm samples the personalized PageRank distribution of each page simultaneously during the precomputation phase, and estimates the personalized PageRank scores from the samples at query time. The drawback of the sampling approach is that approximate scores are returned, where the error of approximation depends on the random choice. In addition the bounds involve the unknown variance, which can in theory be as large as , and hence we need random samples. Indeed a matching sampling complexity lower bound for telling binomial distributions with means apart [1] indicates that one can not reduce the number of samples when approximating personalized PageRank. Similar findings of the superiority of summarization or sketching over sampling is described in [5]. The algorithms presented in Section 2 outperform the Monte Carlo method by significantly reducing the error. 字串4

We also address the computational issues of SimRank, a link-based similarity function introduced by Jeh and Widom [16]. The power iteration SimRank algorithm of [16] is not scalable since it iterates on a quadratic number of values, one for each pair of Web pages; in [16] experiments on graphs with no more than 300K vertices are reported. Analogously to personalized PageRank, the scalable computation of SimRank was first achieved by sampling [12]. Our new SimRank approximation algorithms presented in Section 3 improve the precision of computation. 字串7

The key idea of our algorithms is that we use lossy representation of large vectors either by rounding or sketching. Sketches are compact randomized data structures that enable approximate computation in low dimension. To be more precise, we adapt the Count-Min Sketch of Cormode and Muthukrishnan [7], which was primarily introduced for data stream computation. We use sketches for small space computation; in the same spirit Palmer et al. [25] apply probabilistic counting sketches to approximate the sizes of neighborhoods of vertices in large graphs. Further sketching techniques for data streams are surveyed in [23]. Lastly we mention that Count-Min Sketch and the historically first sketch, the Bloom filter [2] stem from the same idea; we refer to the detailed survey [4] for further variations and applications.

字串3

Surprisingly, it turns out that sketches do not help if the top highest ranked or most similar nodes are queried; the deterministic version of our algorithms show the same performance as the randomized without even allowing a small probability of returning a value beyond the error bound. Here the novelty is the optimal performance of the deterministic method; the top problem is known to cause difficulties in sketch-based methods and always increases sketch sizes by a factor of . By using times larger space we may use a binary search structure or we may use sketches accessed times per query [7]. Note that queries require an error probability of that again increase sketch sizes by a factor of .

In Section 4 we show that our algorithms build optimal sized databases. To obtain lower bounds on the database size, we apply communication complexity techniques that are commonly used for space lower bounds [21]. Our reductions are somewhat analogous to those applied by Henzinger et al. [14] for space lower bounds on stream graph computation.

字串3

1.2 Preliminaries

We briefly introduce notation, and recall definitions and basic facts about PageRank, SimRank and the Count-Min sketch.

字串7

Personalized PageRank

Let us consider the web as a graph. Let denote the number of vertices and the number edges. Let and denote the number of edges leaving and entering , respectively. Details of handling nodes with and are omitted. 字串4

In [24] the PageRank vector , ..., is defined as the solution of the following equation , where , ..., is the teleportation vector and is the teleportation probability with a typical value of . If is uniform, i.e. for all , then is the PageRank. For non-uniform the solution is called personalized PageRank; we denote it by PPR. Since PPR is linear in [13,17], it can be computed by linear combination of personalization to single points , i.e. to vectors consisting of all 0 except for node where . Let PPRPPR.

An alternative characterization of PPR [10,17] is based on the probability that a length random walk starting at node ends in node . We obtain PPR by choosing random according to the geometric distribution: 字串9

PPR

(1)

the summation is along walks starting at and ending in . Thus

PPR PPR

(2)

字串1

Similarly we get PPR if we sum up only to instead of . An equivalent reformulation of the path summing formula (2) is the Decomposition Theorem proved by Jeh and Widom [17]:

PPR PPR

(3)

The Decomposition Theorem immediately gives rise to the Dynamic Programming approach [17] to compute personalized PageRank that performs iterations for , 2, ...with PPR:

PPR PPR

(4)

字串7

SimRank

Jeh and Widom [16] define SimRank by the following equation very similar to the PageRank power iteration such that Sim and

字串6

Sim

(5)

where summation is for .

字串4
Count-Min Sketch

The Count-Min Sketch [7] is a compact randomized approximate representation of non-negative vector , ..., such that a single value can be queried with a fixed additive error and a probability of returning a value out of this bound. The representation is a table of depth and width . One row of the table is computed with a random hash function . The ^th entry of the row is defined as . Then the Count-Min sketch table of consists of such rows with hash functions chosen uniformly at random from a pairwise-independent family. 字串7

Theorem 1 (Cormode, Muthukrishnan [7]) Let where the minimum is taken over the rows of the table. Then and Prob hold.

Count-Min sketches are based on the principle that any randomized approximate computation with one sided error and bias can be turned into an algorithm that has guaranteed error at most with probability by running parallel copies and taking the minimum. The proof simply follows from Markov′s inequality and is described for the special cases of sketch value and inner product in the proofs of Theorems 1 and 2 of [7], respectively. 字串3

2 Personalized PageRank

We give two efficient realizations of the dynamic programming algorithm of Jeh and Widom [17]. Our algorithms are based on the idea that if we use an approximation for the partial values in certain iteration, the error will not aggregate when summing over out-edges, instead the error of previous iterations will decay with the power of . Our first algorithm in Section 2.1 uses certain deterministic rounding optimized for smallest runtime for a given error, while our second algorithm in Section 2.2 is based on Count-Min sketches [7].

The original implementation of dynamic programming [17] relies on the observation that in the first iterations of dynamic programming only vertices within distance have non-zero value. However, the rapid expansion of the -neighborhoods increases disk requirement close to after a few iterations, which limits the usability of this approach². Furthermore, an external memory implementation would require significant additional disk space.

We may justify why dynamic programming is the right choice for small-space computation by comparing dynamic programming to power iteration over the graph of Fig. 1. When computing PPR, power iteration moves top-down, starting at , stepping into its neighbors and finally adding up all their values at . Hence when approximating, we accumulate all error when entering the large in-degree node and in particular we must compute PPR values fairly exact. Dynamic programming, in contrast, moves bottom up by computing the trivial PPR vector, then all the PPR, then finally averages all of them into PPR. Because of averaging we do not amplify error at large in-degrees; even better by looking at (4) we notice that the effect of earlier steps diminishes exponentially in . In particular even if there are edges entering from further nodes, we may safely discard all the small PPR values for further computations, thus saving space over power iteration where we require the majority of these values in order to compute PPR with little error. 字串7

We measure the performance of our algorithms in the sense of intermediate disk space usage. Notice that our algorithms are two-phase in that they preprocess the graph to a compact database from which value and top list queries can be served real-time; preprocessing space and time is hence crucial for a search engine application. Surprisingly, in this sense rounding in itself yields an optimal algorithm for top list queries as shown by giving a matching lower bound in Section 4. The sketching algorithm further improves space usage by a factor of and is hence optimal for single value queries. For finding top lists, however, we need additional techniques such as binary searching as in [7] that loose the factor gain and use asymptotically the same amount of space as the deterministic algorithm. Since the deterministic rounding involves no probability of giving an incorrect answer, that algorithm is superior for top list queries.

字串5

The key to the efficiency of our algorithms is the use of small size approximate values obtained either by rounding and handling sparse vectors or by computing over sketches. In order to perform the update step of Algorithm 1 we must access all vectors; the algorithm proceeds as if we were multiplying the weighted adjacency matrix for with the vector parallel for all values of . We may use (semi)external memory algorithms [27]; efficiency will depend on the size of the description of the vectors. 字串9

The original algorithm of Jeh and Widom defined by equation (4) uses two vectors in the implementation. We remark that a single vector suffices since by using updated values within an iteration we only speed convergence up. A similar argument is given by McSherry [22] for the power iteration, however there the resulting sequential update procedure still requires two vectors.

字串5

2.1 Rounding

字串8

In Algorithm 1 we compute the steps of the dynamic programming personalized PageRank algorithm (4) by rounding all values down to a multiple of the prescribed error value . As the sum of PPR for all equals one, the rounded non-zeroes can be stored in small space since there may be at most of them. 字串9

We improve on the trivial observation that there are at most rounded non-zero values in two ways as described in the next two theorems. First, we observe that the effect of early iterations decays as the power of in the iterations, allowing us to similarly increase the approximation error for early iterations . We prove correctness in Theorem 2; later in Theorem 4 it turns out that this choice also weakens the dependency of the running time on the number of iterations. Second, we show that the size of the non-zeroes can be efficiently bit-encoded in small space; while this observation is less relevant for a practical implementation, this is key in giving an algorithm that matches the lower bound of Section 4. 字串2

Theorem 2 Algorithm 1 returns values between PPR and PPR.

Proof. By induction on iteration of Algorithm 1 we show a bound that is tighter for than that of the Theorem:

PPR

By the choice of and we have , thus the case is immediate since