Local Methods for Estimating PageRank Values

Abstract

The Google search engine uses a method called PageRank, together with term-based and other ranking techniques, to order search results returned to the user. PageRank uses link analysis to assign a global importance score to each web page. The PageRank scores of all the pages are usually determined off-line in a large-scale computation on the entire hyperlink graph of the web, and several recent studies have focused on improving the efficiency of this computation, which may require multiple hours on a typical workstation. However, in some scenarios, such as online analysis of link evolution and mining of large web archives, it may be desirable to quickly approximate or update the PageRanks of individual nodes without performing a large-scale computation on the entire graph. We address this problem by studying several methods for efficiently estimating the PageRank score of a particular web page using only a small subgraph of the entire web.

Introduction

As the World Wide Web has grown from a few thousand pages ten years ago to several billion pages at present, traditional term-based ranking techniques have become increasingly insufficient at returning good results. For this reason, a large number of studies have proposed new ranking techniques based on the analysis of the hyperlink structure of the Web. Probably the two best-known examples of link-based ranking methods are the HITS [ 18 ] and PageRank [ 22 ] algorithms. The PageRank algorithm, in particular, is used in the highly successful Google search engine.

PageRank is based on the idea of assigning a global importance score, called PageRank value, to each page on the web based on the number of hyperlinks pointing to the page and the importance of the pages containing those hyperlinks. PageRank values are usually computed in an off-line manner, during a largescale iterative computation on the entire web graph. Several recent studies [ 3, 10, 13, 17 ] have looked at ways to optimize this computation, which may take many hours on a typical workstation for large graphs.

However, there are some situations in which a global computation on the entire graph is impractical, e.g., if the the link information of the whole web graph is not easily accessible and we need a quick estimation for a particular web page. In particular, users may have only access to a limited subset of the web, or may have to access the graph via a remote connectivity server [ 5 ] such as the link: query facility in AltaVista, or via a similar interface to a local meta data repository in a disk-based relational database. For example, we might be interested in the evolution of the PageRank of a particular page tracked by the Internet Archive, but cannot afford multiple PageRank computations on billions of pages (We note that the Internet Archive does currently not yet provide the remote Connectivity Server functionality that would be needed in this case).

In this paper, we study local methods for determining reasonable estimates of the PageRank values of individual nodes. The basic approach in all our methods is to expand a small subgraph around the target node and to use this subgraph as the basis for our estimation. Our goal is to minimize the cost of our methods, as measured in terms of the size of the subgraph that is retrieved, while maximizing the accuracy of our estimation. We show that on average, a reasonable estimate of the PageRank of a node can be obtained by visiting a few dozen to a few hundred nodes. We compare several methods, and in the process also discuss the correlation between PageRank and simple statistical measures such as weighted and unweighted in-degrees. Our approach can also be used to estimate current PageRank values based on slightly outdated values from an old graph, but under different assumptions than the work in [ 11 ].

14 1 10

The remainder of the paper is organized as follows. We first provide a brief review of the PageRank method. Section 3 is the main section of this paper, and describes our local methods for estimating PageRank values and evaluates their performance on a large subgraph of the web. Section 4 discusses related work, and finally Section 5 provides some concluding remarks. 2

Review of PageRank

In this section, we review the PageRank technique. Recall that the Web can be viewed as a directed graph whose nodes are web pages and whose edges are the hyperlinks between pages. The in-degree of a node is the number of edges (hyperlinks) pointing to it, and the out-degree of a node is the number of distinct hyperlinks out of it. We use to denote the number of nodes in the graph.

The Basic Idea: PageRank was proposed in [ 7, 22 ] as a ranking mechanism for the Google search engine that assigns to each page a global importance score based on link analysis. The basic idea is that if page has a link to page , then the author of is implicitly saying that page is somehow important to . Thus, page is conferring some amount of importance onto , and this amount is determined by the importance of itself and the number of outlinks in over which it is divided. This recursive definition of importance can be described by the stationary distribution of a simple random walk over the graph, where we start at an arbitrary node and in each step choose a random outgoing edge from the current node. (Several papers [ 8, 6, 24 ] have proposed heuristics for assigning different weights to the outgoing edges in a node; we assume each edge is selected with equal probability though our techniques could be adjusted to other choices.) According to this random walk model, the importance of a page is determined as: "#! (*) +#, # labeled from to , and define matrix by if there is a link from node to node and where is the out-degree of page . This can be rewritten in matrix form as follows. Let the nodes be otherwise. (Thus, is a ”degree-scaled” version o%f$’t&he adjacency matrix of the graph.) Then we obta$in 3.1

The General Idea

where is the outdegree of page . A natural question is to what degree PageRank is related to weighted in-degree, and we will run into this question later on. ! # J:) +#, # In the matrix formulation, we define a new matrix with if there is a link from node to ,;OJ @) J / node and otherwise, and then use instead of .%$’In& our experiments, we use .

W$ eighted In-Degree: One simplistic explanations of PageRank would be of the form ”very sFimilar to in-degree, except it matters where the pointers come from”. This would suggest that the PageRank value of a node might be strongly correlated with its in-degree (which had been previously proposed as a ranking function [ 19 ]). It was observed in [ 23 ] that this is in fact not the case. One obvious reason is that the amount of PageRank sent across an edge depends on the out-degree of the sending node. This motivates us to define the weighted in-degree of a node as: In our problem setup, we assume that we have a fetch operation that allows us, given a URL or page ID, to retrieve the in-degree and out-degree of the corresponding page plus the sources and destinations of incoming and outgoing links, respectively. Our cost measure is the number of fetch operations performed. (In the case where there are many incoming links, our best methods actually do not require information about all sources of links.) All our methods follow the same simple approach based on three phases: (1) Expansion: We build a subgraph starting from the target node for which we are interested in estimating the PageRank value, by expanding backwards from the target node following reverse hyperlinks. We stop this expansion phase after a while based on some criterium. The cost of this phase is equal to the size of the subgraph we build. An example of a subgraph is shown in Figure 1, with a target node on the right, three internal nodes, and five boundary nodes on the left side. 3

Algorithms and Experimental Results

We start by describing the main idea underlying the methods that we propose. After introducing our experimental setup, we then describe and evaluate our methods one after the other.

(3) Iteration: We run the standard iterative algorithm for PageRank on the subgraph, in each step putting our estimated value into the boundary nodes, adding the random jump value of to the internal nodes, and removing any flow leaving the subgraph. After some iterations, we us eF the PageRank in the target node as our estimate. This phase also does not involve any fetch operations. : B 7@)H values, respectively. The other one is called precision, defined as . Thus, precision tells 7 Two measurements are used to identify the accuracy of our methods. One is relative error of a target G report our experimental results for a set of randomly chosen target nodes. @ : )H 7 @ 7 node , defined as , where and are the estimated and precise PageRank graph was only used in one of the experiments.) Following Haveliwala [ 13 ], we pruned the graph twice by removing leak nodes; this resulted in a highly connected graph with nodes and links, for an average out-degree of in the new graph. We then stored the linD k information for the graph in a Berkeley DB database which req uFired about GB storage space. This provides an adjacency-list type interface to the graph similar to connectivity serveD rs [ 5 ] and search engines with support for link: queries, or relational web meta data repositories, with each fetch operation requiring a disk access. To measure the accuracy of our estimations, we also performed the global PageRank computation on the entire graph. We us whether we tend to over- or underestimate the correct result. We typically plot our results in terms of the average relative error and standard deviation, and also show scatter plots for precision. *) then estimate the PageRank of each boundary node as , the average value in the graph. The results are G error of at an average cost of fetch operations per estimation.

G slightly below , though at a high cost. For example, with three levels, we obtain an average relative In this method, we build the subgraph by simply expanding from the target node backwards for a fixed number of levels , i.e., we include all nodes from which the target can be reached in at most steps. We shown in Figure 2, which shows on the left the average error and cost per target node, and on the right a scatter plot of the precision and cost values for levels. As we see, we eventually get average relative errors

We notFe that the size of the subgr aDp hD explodes to about nodes after six levels, but even at that size errors are . In the following, we look at smarterD techniques that do not expand the graph in a brute-force mannF er. 3.3

A Naive Method 3.4

The Simple Influence Method

Considering the boundary nodes of the subgraph, we can ask about the impact that each boundary node has on the estimation at the target node. It should be obvious that for some nodes, the impact is low since most of the PageRank value entering the node will never arrive at the target node, while others will have more impact since most paths from this node go to the target node. We formally define the influence of a node as the fraction of PageRank value at this node that will eventually arrive at the target node without performing a random jump in between. We note that influence is related to the inverse distance measure defined by Jeh and Widom in [ 16 ]. The overall impact that a node has on the estimation error at the target 17 4 depends on its influence and the absolute PageRank estimation error at the node (which we do not know). Formally, the absolute estimation error at the target is upper-bounded by the sum over all boundary nodes of the product of the absolute amounts of these two terms, though for large numbers of boundary nodes we expect errors with different signs to largely cancel each other out.

A precise computation of the influence of a node on target node is quite expensive, and thus we approximate this value as follows. We place one unit of rank value onto , and then simulate PageRank for a while until most of the rank value has either left the subgraph (including random jumps) or arrived at the target. In particular, we adopt the OPIC approach recently proposed by Abiteboul et al. in [ 1 ] for this problem. In this approach, we select a node currently containing some rank value, and fire it, resulting in its rank value being pushed out of the node to other nodes. We remove any rank arriving at the target, leaving the subgraph, or taking a random jump, and terminate this process when the amount of rank still in the subgraph has decreased below some threshold. We then estimate the influence by the total amount of value that has arrived at the target. The process can be made more efficient by firing in each step the node that contains the most rank value (based on a heap structure), and thus after firings the influence value can be estimated within an additive term , where is the size of the su b29><gr a6ph.

(right) versus cost for simple influence method.

as before. (c) estimate the PageRank using the weighted in-degree defined in Section 2. We note that this would assume that this measure is precomputed and stored in the database, which may not be realistic. *) estimating their value as is also a problem, potentially even if their influence is low, since such nodes The influence test provides useful information for choosing when to stop expanding. However, some nodes with large in-degree can create problems. If their influence is above the threshold, then expanding them would be very expensive as we have to fetch all nodes pointing to them. Not expanding them and just typically have a large absolute PageRank. The impact of such a node on the estimation at the target is given by the product of its influence and its (in this case large) absolute estimation error.

Thus, we need to refine our approach. In particular, we use the following rule: If the influence of a node divided by its in-degree is greater than the threshold , we expand the node by fetching its predecessors; otherwise, we stop. This solves the first of the above issues. To solve the second issue, we experiment with heuristics for estimating the PageRank of the boundary nodes. We compared the following approaches: G G an average relative error around with a cost of , which is much better than before. However, the standard deviation is still significantly higher than the average error due to a few estimates that are way off. , J @) transmits a PageRank value of , where is the total number of hyperlinks in the graph. (b) estimate the PageRank by assuming that each edge from outside the subgraph into the boundary node Rank values due to random incoming jumps and from other nodes in the subgraph can be directly computed and do not need to be estimated.

G Concerning absolute numbers, using method (b) we get an average relative error below with a cost

In Figure 4 we show the cost of the method and the average relative errors for all three estimation approaches (the cost stays the same), for various thresholds . Also, Figure 5 compares the naive and simple influence methods from the previous subsections to the method (b) above in terms of the error/cost tradeoff. We see from Figure 4 that using the number of links together with the influence to decide whether to expand decreases the cost for a given threshold value compared to the simple influence method, and that methods (b) and (c) perform much better than (a) in terms of error. Also, we see from Figure 5 that (b) achieves an overall better error/cost tradeoff than our earlier approaches, while Figure 4 shows improvements in the standard deviation due to fewer outliers. of fetch operations. We note that the cost of the influence computations and of the PageRank iterations in the third phase are insignificant, and thus the number of fetches provides a reasonable model.

19 6 G old graph (shaded part of column), for values of from to the total number of nodes. On the right

On the left side of Figure 6, we show how many of the pages ranked in the top in the new graph were present in the old graph (total height of column) and how many were also ranked in the top in the side, we show results for a site-level view, where each site is represented by its highest-ranked URL (with PageRank computed on a page-level graph as before). We see clearly that pages that are highly ranked in the To check the correctness of our code, we also ran an experiment where we estimated the boundary nodes using their exact PageRank values, to see if we would also obtain the exact value at the target node (we did). This test raised the following question for us: Suppose we have outdated PageRank values of some or all nodes available from a previous crawl, and we want to estimate the current value, can we do better by following our approach and estimating the rank values of the boundary nodes using the old values? To test this hypothesis, we used two different crawls that we performed about months apart using the Polybot web crawler [25] on the same set of start pages and crawl policies. Thus, both crawls have million pages before pruning, and about million afterwards. The two snapshots have about 13.6 milDlion pages and one million sites in common (we consider two pages as the same if they have same URL). We now briefly discuss the observed changes between the two graphs. new graph were also likely to have existed and been crawled in the old graph, and in fact often were already ranked high in the old graph. This tendency is even stronger at the site level since in some cases sites move their most highly ranked page to a different URL. We note that according to [ 20 ], a breadth-first crawl of sufficiently large size is likely to visit most pages with large PageRank. We also refer to [ 4 ] for additional discussion of PageRank in the context of web evolution.

Now we look at what happens if we directly plug old PageRank values into boundary nodes instead of approximating them with our other techniques. For those nodes where no old PageRank values are available, we use approach (b) in Subsection 3.5, i.e., estimation by in-degree. Figure 7 shows the results for this method. The cost is the same as in Subsection 3.5, but the average error also appears to be comparable to those methods. There appear to be two issues with this approach. First, the old graph is quite old at months. Second, on closer examination we find that many of the nodes with high PageRank, which mostly already existed in the old graph, have significantly increased their in-degree and PageRank value. This problem could be addressed by maybe correcting the old Pagerank value for changes in in-degree, though this remains for future work. *) than estimating the value by for our purposes). On the other hand, the weighted in-degree measure was In one of our two best methods, we used the in-degree of the boundary nodes to estimate their PageRank, by multiplying the in-degree by the average edge flow in the entire graph. In the other one, we used the weighted in-degree with slightly better results. It was observed in [ 23 ] that the in-degree is in fact not strongly correlated to the PageRank value (although there is a slight correlation that makes it at least better not studied in [ 23 ]. This leads us to look at the correlation between iterated versions of the weighted and unweighted in-degree, shown in Table 3.1 below. We see that while there is some correlation with in-degree (I), not surprisingly this correlation largely disappears for two-level (I-I) and three-level (I-I-I) iterated indegree. On the other hand, for weighted in-degree (WI), the correlation is much higher and increases with more levels (WI-WI and WI-WI-WI) to close to . Of course, computing the weighted in-degree over several levels is really similar (but not identical) to expanding a subgraph by several levels (our naive method) and thus not really a more efficient alternative to our methods. We also show the correlation between new and old PageRank values for those nodes that exist in both graphs. Link analysis techniques are playing an increasingly important role in web search engines, and a large number of techniques have been proposed. The two best known approaches probably are PageRank, proposed in [ 7 ] and used by Google, and the HITS method proposed by Kleinberg [ 18 ]. A number of extensions of these approaches were subsequently described; see, e.g., [ 14, 24, 8, 16, 21 ]. We refer to [ 2, 9 ] for an overview of link ranking techniques.

Recent work by Chien et al. [ 11 ] studies the problem of maintaining the results of a PageRank computations under changes in the graph structure. Their technique is similar to ours in that they also expand a small subgraph around a point of interest, in this case a change to a link or node in this graph, and collapse the rest of the graph into one large supernode. Then resulting changes in the PageRank values are propagated only within this graph. An important difference is that in [ 11 ] the graph is expanded by following forward links from the point of interest, while we expand backwards until some appropriate stopping criterium is met. As discussed, our approach can also be used to estimate updated from outdated PageRank values, but in contrast to [ 11 ] no knowledge of the precise changes in the web graph is required.

Since the early days of search engines, counting the in-degree of a node to estimate the page importance has been used as a form of link-based ranking [ 19 ], and there is a wealth of research that studies the in-degree properties of the web graph. Simply counting the in-degree of a node encourages spamming and is thus not considered a good ranking method. However, it is interesting to try to relate in-degree to PageRank and more advanced methods. In this context, Pandurangan, Raghavan, and Upfal [ 23 ] studied the relationship between PageRank and in-degree and discuss random graph models for capturing the PageRank, in-degree, and out-degree distributions in the real Web. Their results showed that there is only very weak correlation between PageRank values and node degrees, which is relevant to our problem of estimating PageRanks of boundary nodes discussed in Section 3.

The notion of the influence between two nodes also plays a role in the work on Personalized Pagerank by Jeh and Widom [ 16 ], which studies the efficient computation of personalized PageRank values based on a combination of precomputation and online computation on small subgraphs. In our computation of the influence, we adapt a technique proposed by Abiteboul, Preda, and Cobena [ 1 ] for the purpose of approximating rank values during a crawl. Finally, we note that PageRank estimation during a crawl based on the already crawled part of the web is also performed in [ 15, 12 ]. However, these methods do not attempt to optimize the precision of their estimates by expanding a subgraph in a controlled fashion, but instead simply use the available subgraph. 5

Conclusions and Future Work

In this paper, we have described and evaluated several heuristic algorithms for estimating PageRank values of individual pages without a global computation over the entire graph. As we have shown, a reasonable estimate of the value is possible in a few seconds on a typical workstation based on maybe a few hundred disk or remote server accesses to retrieve an appropriate subgraph. On the other hand, even a larger amount of work does not result in a truly reliable estimate due to the structure of the graph and in particular due to the difficulty of dealing with boundary nodes with large PageRank that can have a large impact on the target node. For future work, it might be nice to evaluate the proposed methods under a formal web graph model. We are also interested in applying the methods to the analysis of large archives of web data with multiple versions of pages and an evolving link structure.

Acknowledgements: This work was supported by NSF CAREER Award NSF CCR-0093400 and the New York State Center for Advanced Technology in Telecommunications (CATT) at Polytechnic University, and by equipment grants from Sun Microsystems and Intel Corporation. Yen-Yu Chen was also supported by a Sun Foundation (Taiwan, R.O.C.) Fellowship.

References

[1] S. Abiteboul , M. Preda , and G. Cobena. Adaptive on-line page importance computation . In Proc. of the 12th Int. World Wide Web Conference , May 2003 .

[2] A. Arasu , J. Cho , H. Garcia-Molina , and S. Raghavan . Searching the web . ACM Transactions on Internet Technologies , 1 ( 1 ), June 2001 .

[3] A. Arasu , J. Novak , Tomkins A , and J. Tomlin . Pagerank computation and the structure of the web: Experiments and algorithms . In Poster presentation at the 11th Int. World Wide Web Conference , May 2002 .

[4] R. Baeza-Yates , F. Saint-Jean , and C. Castillo . Web dynamics, age and page quality . In String Processing and Information Retrieval (SPIRE) , September 2002 .

[5] K. Bharat , A. Broder , M. Henzinger , P. Kumar , and S. Venkatasubramanian . The connectivity server: Fast access to linkage information on the web . In 7th Int. World Wide Web Conference , May 1998 .

[6] K. Bharat and M. Henzinger . Improved algorithms for topic distillation in a hyperlinked environment . In Proc. 21st Int. Conf. on Research and Development in Inf. Retrieval (SIGIR) , August 1998 .

[7] S. Brin and L. Page. The anatomy of a large-scale hypertextual web search engine . In Proc. of the Seventh World Wide Web Conference , 1998 .

[8] S. Chakrabarti , B. Dom , D. Gibson , J. Kleinberg , P. Raghavan , and S. Rajagopalan . Automatic resource list compilation by analyzing hyperlink structure and associated text . In Proc. of the 7th Int. World Wide Web Conference , May 1998 .

[9] S. Chakrabarti , B. Dom , R. Kumar , P. Raghavan , S. Rajagopalan , A. Tomkins , David Gibson, and J. Kleinberg . Mining the web's link structure . IEEE Computer , 32 ( 8 ): 60 - 67 , 1999 .

[10] Y. Chen , Q. Gan , and T. Suel . I/O-efficient techniques for computing pagerank . In Proc. of the 11th International Conf. on Information and Knowledge Management , pages 549 - 557 , November 2002 .

[11] S. Chien , C. Dwork , R. Kumar , D. Simon , and D. Sivakumar . Link evolution: Analysis and algorithms . In Workshop on Algorithms and Models for the Web Graph , 2002 .

[12] J. Cho , H. Garcia-Molina , and L. Page . Efficient crawling through URL ordering . In 7th Int. World Wide Web Conference , May 1998 .

[13] T.H. Haveliwala . Efficient computation of pagerank . Technical report , Stanford University, October 1999 . Available at http://dbpubs.stanford.edu:8090/pub/1999-31.

[14] T.H. Haveliwala . Topic-sensitive pagerank . In Proc. of the 11th Int. World Wide Web Conference , May 2002 .

[15] M. R. Henzinger , A. Heydon , M. Mitzenmacher , and M. Najork . On near-uniform URL sampling . In Proc. of the 9th Int. World Wide Web Conference , May 2000 .

[16] G. Jeh and J. Widom . Scaling personalized web search . In 12th Int. World Wide Web Conference , 2003 .

[17] S. Kamvar , T. Haveliwala , C. Manning , and G. Golub . Extrapolation methods for accelerating pagerank computations . In Proc. of the 12th Int. World Wide Web Conference , May 2003 .

[18] J. Kleinberg . Authoritative sources in a hyperlinked environment . Journal of the ACM , 46 ( 5 ): 604 - 632 , 1999 .

[19] Y. Li . Toward a qualitative search engine . IEEE Internet Computing , August 1998 .

[20] M. Najork and J. Wiener . Breadth-first search crawling yields high-quality pages . In 10th Int. World Wide Web Conference , 2001 .

[21] A. Ng , A. Zheng , and M. Jordan . Stable algorithms for link analysis . In Proc. of the 24th Annual SIGIR Conf. on Research and Development in Information Retrieval , 2001 .

[22] L. Page , S. Brin , R. Motwani , and T. Winograd . The pagerank citation ranking: Bringing order to the web . Technical report , Computer Science Department, Stanford University, 1999 .

[23] G. Pandurangan , P. Raghavan , and E. Upfal . Using pagerank to characterize web structure . In Proc. of the 8th Annual Int. Computing and Combinatorics Conference (COCOON) , 2002 .