Supervised ranking of vertices of a directed graph

[0001] Many search engine services, such as GOOGLE and OVERTURE, provide for searching for information that is accessible via the Internet. These search engine services allow users to search for display pages, such as web pages, that may be of interest to users. After a user submits a search request (i.e., a query) that includes search terms, the search engine service identifies web pages that may be related to those search terms. To quickly identify related web pages, the search engine services may maintain a mapping of keywords to web pages. This mapping may be generated by “crawling” the web (i.e., the World Wide Web) to identify the keywords of each web page. To crawl the web, a search engine service may use a list of root web pages to identify all web pages that are accessible through those root web pages. The keywords of any particular web page can be identified using various well-known information retrieval techniques, such as identifying the words of a headline, the words supplied in the metadata of the web page, the words that are highlighted, and so on. The search engine service identifies web pages that may be related to the search request based on how well the keywords of a web page match the words of the query. The search engine service then displays to the user links to the identified web pages in an order that is based on a ranking that may be determined by their relevance to the query, popularity, importance, and/or some other measure.

[0002] Three well-known techniques for page ranking are PAGERANK, HITS (“Hyperlink-Induced Topic Search”), and DirectHIT. PAGERANK is based on the principle that web pages will have links to (i.e., “out links”) important web pages. Thus, the importance of a web page is based on the number and importance of other web pages that link to that web page (i.e., “in links”). Web pages and their links can be represented as a web graph. A web graph represents web sites as vertices of the graph and links between web pages of the web sites as edges between the vertices. The edges are directed to differentiate in and out links. A web graph can be represented as an adjacency matrix A_i where A_ij represents the number of out links from web page i to web page j. The importance score w_j for web page j can be represented by the following equation:

[0003] $w_j=\sum _i{A}_{\mathrm{ij}}{w}_i$

[0004] This equation can be solved by iterative calculations based on the following equation:
A^Tw=w
where w is the vector of importance scores for the web pages and is the principal eigenvector of A^T.

[0005] The HITS technique is additionally based on the principle that a web page that has many links to other important web pages may itself be important. Thus, HITS divides “importance” of web pages into two related attributes: “hub” and “authority.” “Hub” is measured by the “authority” score of the web pages that a web page links to, and “authority” is measured by the “hub” score of the web pages that link to the web page. In contrast to PAGERANK, which calculates the importance of web pages independently from the query, HITS calculates importance based on the web pages of the result and web pages that are related to the web pages of the result by following in links and out links. HITS submits a query to a search engine service and uses the web pages of the result as the initial set of web pages. HITS adds to the set those web pages that are the destinations of in links and those web pages that are the sources of out links of the web pages of the result. HITS then calculates the authority and hub score of each web page using an iterative algorithm. The authority and hub scores can be represented by the following equations:

[0006] $a\left(p\right)=\sum _{q->p}h\left(q\right)$ $\mathrm{and}$ $h\left(p\right)=\sum _{p->q}a\left(q\right)$
where a(p) represents the authority score for web page p and h(p) represents the hub score for web page p. HITS uses an adjacency matrix A to represent the links. The adjacency matrix is represented by the following equation:

[0007] $b_{\mathrm{ij}}=\{\begin{array}{c}1\mathrm{if}\mathrm{page}i\mathrm{has}a\mathrm{link}\mathrm{to}\mathrm{page}j,\\ 0\mathrm{otherwise}\end{array}$

[0008] The vectors a and h correspond to the authority and hub scores, respectively, of all web pages in the set and can be represented by the following equations:
a=A^Th and h=Aa
Thus, a and h are eigenvectors of matrices A^T A and AA^T. HITS may also be modified to factor in the popularity of a web page as measured by the number of visits. Based on an analysis of click-through data, b_ij of the adjacency matrix can be increased whenever a user travels from web page i to web page j.

[0009] Although these techniques for ranking web pages based on analysis of links can be very useful, these techniques assume that the underlying data (e.g., web pages and their links) upon which importance is based is both accurate and reliable. Unfortunately, the underlying data can have inaccuracies and the links may not be a reliable representation of importance, resulting in reduced reliability of the determination of importance. Web pages and links may be missing from the underlying data for several reasons, making the data inaccurate. For example, when crawling web sites, some links may be missed due to an HTML parsing error or expiration of a URL. If the importance of scholarly papers is being determined, some citations may be lost due to different formats of abbreviations in the references. The underlying data may also have links that are not reliable representations of importance. For example, the links may include many “spam” links. “Spamming” in general refers to a deliberate action taken to unjustifiably increase the popularity or importance of a web page or web site. In the case of link spamming, a spammer can manipulate links to unjustifiably increase the importance of a web page. For example, a spammer may increase a web page's hub score by adding out links to the spammer's web page. A common technique for adding out links is to create a copy of an existing link directory to quickly create a very large out link structure. As another example, a spammer may provide a web page of useful information with hidden links to spam web pages. When many web pages point to the useful information, the importance of the spam web pages is indirectly increased. As another example, many web sites, such as blogs and web directories, allow visitors to post links. Spammers can post links to their spam web pages to directly or indirectly increase the importance of the spam web pages. As another example, a group of spammers may set up a link exchange mechanism in which their web sites point to each other to increase the importance of the web pages of the spammers's web sites. Spam links may also be present in scholarly papers. For example, an author may prefer to include a citation to a previous paper of the author even though another paper may be more relevant and more authoritative.

[0010] A method and system for ranking importance of vertices of a directed graph based on links between the vertices and some prior knowledge of importance of the vertices is provided. A ranking system inputs an indication of the vertices along with an indication of the links between the vertices as the directed graph. The ranking system generates a transition-probability matrix that represents the probability of transitioning from vertex to vertex. The ranking system then generates a ranking of the vertices based on the links between the vertices represented by the stationary distribution of the transition-probability matrix that is minimally perturbed to satisfy the prior knowledge, which may be a partial ranking of the vertices. This ranking is supervised in that the ranking of importance is influenced by the prior knowledge. The ranking system can be used to generate a supervised ranking for any data that can be represented as a directed graph with transition probabilities associated with transitioning from vertex to vertex along the links, such as web pages and their hyperlinks and scholarly articles and their citations.

[0011] This Summary is provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used as an aid in determining the scope of the claimed subject matter.

[0015] A method and system for ranking importance of documents based on links between the documents and some prior knowledge of importance of the documents is provided. In one embodiment, a ranking system inputs an indication of the documents along with an indication of the links between the documents. For example, if the documents are web pages, then the ranking system may represent the web pages and the links between the web pages using an adjacency matrix. The ranking system also inputs some prior knowledge of the ranking of the documents such as a partial ordering of some documents. For example, the ranking system may input from a person an indication of the relative ranking of pairs of web pages. The ranking system may also input other prior knowledge such as the popularity of a web page derived from analysis of click-through data. The popularity of some web pages may indicate a relative ordering of their rankings. The ranking system then generates a ranking of the documents based on the links between the documents while attempting to satisfy the partial ranking constraints of the prior knowledge. This ranking is supervised in that the ranking of importance is influenced by the partial ranking. The ranking system uses the additional partial ranking, which is not susceptible to the same inaccuracies and unreliability of the underlying data. Thus, the ranking system can generate a more accurate and reliable ranking of importance than techniques that rely solely on documents and their links. Moreover, the ranking system can be used to generate a supervised ranking for any data that can be represented as a directed graph with transition probabilities associated with transitioning from vertex to vertex along the links.

[0016] In one embodiment, when importance is based on a page rank-type algorithm, the ranking system attempts to perturb (or adjust) the transition-probability matrix so that the stationary distribution, which represents the ranking of the vertices, satisfies the partial rankings. In doing so, the ranking system attempts to minimize the perturbation to the transition-probability matrix so that the ranking reflects, to the extent possible, the influence of the unperturbed transition-probability matrix. Unfortunately, the goal of minimizing the perturbation while calculating the stationary distribution of the transition-probability matrix (i.e., the eigenvector) has a feasible domain that is not convex. The feasible domain is not convex because the minimization is constrained by the stationary distribution that is defined in terms of the perturbation that is to be minimized. The finding of a solution to a problem with a non-convex feasible domain is very computationally complex. To avoid this computational complexity, the ranking system reformulates the optimization problem so that its feasible domain is convex. The ranking system removes this constraint and adds the constraining equation to the objective function that is to be minimized. As described below in detail, the ranking system then uses an interactive optimization algorithm to iteratively and interactively solve the reformulated objective function, which is non-convex. The interactive optimization algorithm iteratively fixes the perturbation and calculates the eigenvector and then fixes the eigenvector and calculates the perturbation until the perturbation and the eigenvector converge on a solution, with the principal eigenvector representing the ranking of the vertices.

[0017] In one embodiment, the ranking system may collect prior knowledge of the ranking or importance of documents from various sources. For example, the ranking system can input expert opinions as to which scholarly papers have more impact in a specific domain than others. The ranking system may also use the number of visitors of web pages as an indication of their ranking or importance. The ranking system may represent this prior knowledge by partial order constraints. For example, if vertex 1 is known to be more important than vertex 2, and vertex 3 is known to be more important than vertex 4, the ranking system may represent the partial order constraints represented by the following equations:

[0018] $\begin{array}{cc}\left[\begin{array}{cccc}1& 0& 0& 0\\ 0& 0& 1& 0\end{array}\right]\pi >\left[\begin{array}{cccc}0& 1& 0& 0\\ 0& 0& 0& 1\end{array}\right]\pi & \left(1a\right)\\ \mathrm{or}& \\ A\pi >B\pi & \left(1b\right)\\ \mathrm{where}& \\ A=\left[\begin{array}{cccc}1& 0& 0& 0\\ 0& 0& 1& 0\end{array}\right]& \\ \mathrm{and}& \\ B=\left[\begin{array}{cccc}0& 1& 0& 0\\ 0& 0& 0& 1\end{array}\right].& \end{array}$

[0019] Given these constraints, the ranking system perturbs the transition-probability matrix according to the following equation:
P₁=P−E  (2)
where P₁ is the perturbed transition-probability matrix, P is the original transition-probability matrix derived from the adjacency matrix, and E is a perturbation matrix. The ranking system perturbs the transition-probability matrix so that the stationary distribution of the new Markov chain will be consistent with the constraints as much as possible. Many different perturbation matrices can be used to satisfy the partial order constraints. If the transition-probability matrix is perturbed too much, most of the information on importance derived from the directed graph will be lost. Although the information on importance may be to some extent inaccurate and unreliable, much of the information is accurate and reliable. To prevent the transition-probability matrix from being perturbed too much, the ranking system formulates the supervised ranking as an optimization problem in which the perturbation is minimized subject to those partial order constraints as represented by the following equations:
min∥E∥_F²  (3)
s.t. (P−E)e=e  (3a)
(P−E)≧0  (3b)
π^T=π^T(P−E)  (3c)
e^Tπ=1  (3d)
π≧0  (3e)
Aπ>Bπ  (3f)
where Equation 3 represents the objective function (e.g., the minimization of the perturbation matrix), Equations 3a-3f represent the constraints e represents a vector of 1's, π represents the eigenvector, (P−E)≧0 means that each element of the matrix P−E is non-negative, and ∥E∥_F represents the Frobenius norm of the matrix E. Any other matrix norm may also be used although the ranking system may use the Frobenius norm for its computation simplicity. Equations 3a and 3b ensure that the perturbed transition-probability matrix is still a row-stochastic transition-probability matrix. Equations 3c, 3d, and 3e ensure that π is the stationary distribution of the perturbed Markov chain. Equation 3f is the supervision which is given according to the prior knowledge.

[0020] The constraints of Equations 3a, 3b, 3d, 3e, and 3f are affine functions of π or E. However, the constraint of Equation 3c contains interweaved terms of π and E, which makes the feasible domain non-convex. Because of the computational complexity of solving optimization problems with feasible domains that are non-convex, the ranking system moves the constraint of Equation 3c to the objective function and reformulates the optimization problem as represented by the following equations:
min∥E∥_F²+cπ^T(I+E−P)(I+E−P)^Tπ  (4)
s.t. (P−E)e=e  (4a)
(P−E)≧0  (4b)
e^Tπ=1  (4c)
π≧0  (4d)
Aπ>Bπ  (4e)
where c in Equation 4 is a trade-off parameter (e.g., 100). The reformulated problem has a feasible domain that is convex.

[0021] Although the feasible domain of the problem of Equation 4 is convex, the objective function is not. To solve this problem, the ranking system decomposes this problem into two convex sub-problems. In each sub-problem, the ranking system fixes one parameter (π or E) and finds the optimal value of the other. By iteratively solving these sub-problems one after the other using an interactive optimization algorithm, the ranking system can get a close-to-optimal solution of the original problem. The ranking system represents the first sub-problem by the following equation:

[0022] $\begin{array}{cc}\pi \left(E\right)=\arg \underset{\pi }{\min }{E}_F^2+c{\pi }^T\left(I+E-P\right){\left(I+E-P\right)}^T\pi & \left(5\right)\end{array}$
s.t. e^T=1  (5a)
π>0  (5b)
Aπ>Bπ  (5c)
where the perturbation matrix E is fixed and π is optimized. This sub-problem is a linearly constrained quadratic optimization problem, which can be solved very efficiently. Since both the feasible domain and the objective function are convex, this problem has a global minimum π(E).

[0023] The ranking system represents the second sub-problem by the following equations:

[0024] $\begin{array}{cc}E\left(\pi \right)=\arg \underset{E}{\min }{E}_F^2+c{\pi }^T\left(I+E-P\right){\left(I+E-P\right)}^T\pi & \left(6\right)\end{array}$
s.t. (P−E)e=e  (6a)
(P−E)>0  (6b)
where the stationary distribution π is fixed and the perturbation matrix E is optimized. This sub-problem is also a linearly constrained quadratic convex optimization problem, for which the global minimum E(π) can be solved efficiently. The interactive optimization algorithm is represented by the following pseudo code:

[0025]

	Given E0
	repeat
	find the global optimal πi by fixing E = Ei–1
	find the global optimal Ei by fixing π = πi
	until πi and Ei converge
	End

[0026] Well-known techniques exist for finding the global optimal such as variations of Newton's method. These variations include interior-point methods as described in Boyd and Vandenberghe, Convex Optimization, Cambridge University Press, 2004, Chap. 11. Interior-point methods can achieve specified optimization accuracy with a computational complexity that does not exceed a polynomial of the problem dimensions. The space complexity, however, for the second sub-problem is O(n²). Since there are millions of web pages n, the space complexity is very large. In one embodiment, the ranking system takes advantage of the sparseness of the adjacency matrix representing the directed graph to reduce the space complexity. For example, regardless of the number of web pages, the average is only about ten out links per page. Similarly, regardless of the number of papers in a domain, the average is in the tens of citations per paper. Thus, although there are approximately O(n²) possible vertex pairs, there are actually only O(n) edges. To reduce the space complexity, the ranking system only perturbs the non-constant elements in P (which correspond to those actual edges between vertices). Although this simplification may lead to a drop in effectiveness, it may be a reasonable tradeoff between efficiency and effectiveness.

[0027] FIG. 1 is a block diagram that illustrates components of the ranking system in one embodiment. The ranking system 150 is connected via communications link 120 to various web servers 110. The web servers serve the web pages of various web sites. The ranking system may include a crawl web sites component 161 and an adjacency matrix store 162. The crawl web sites component crawls the various web sites provided by the web servers to identify web pages and their links. The crawl web sites component stores a representation of the corresponding web graph in the adjacency matrix store. The ranking system may also include a search engine component 181, an identify relevant web pages component 182, and a rank web pages component 183. The search engine component receives queries for web pages and invokes the identify relevant web pages component to identify the web pages that are relevant to a query. The search engine component then invokes the rank web pages component to generate an ordering for the web pages to be returned as a result of the query. The rank web pages component may factor in the relevance of the web page to the query, the importance of a web page as indicated by the supervised ranking of web pages, the popularity of the web pages, and so on. The ranking system may also include a generate supervised ranking component 171, an optimize interactively component 172, a supervised ranking store 173, a collect partial ordering component 174, and a partial ordering store 175. The collect partial ordering component may collect a partial ordering of the web pages from a user or some other source and store the partial ordering in the partial ordering store. The generate supervised ranking component generates a ranking for the web pages using the adjacency matrix store and the partial ordering store. The generate supervised ranking component invokes the optimize interactively component to generate the ranking and stores the ranking of each web page in the supervised ranking store.

[0028] The computing device on which the ranking system is implemented may include a central processing unit, memory, input devices (e.g., keyboard and pointing devices), output devices (e.g., display devices), and storage devices (e.g., disk drives). The memory and storage devices are computer-readable media that may be encoded with computer-executable instructions that implement the ranking system, which means a computer-readable medium that contains the instructions. In addition, the instructions, data structures, and message structures may be stored or transmitted via a data transmission medium, such as a signal on a communication link. Various communication links may be used, such as the Internet, a local area network, a wide area network, a point-to-point dial-up connection, a cell phone network, and so on.

[0029] Embodiments of the ranking system may be implemented in various operating environments that include personal computers, server computers, hand-held or laptop devices, multiprocessor systems, microprocessor-based systems, programmable consumer electronics, digital cameras, network PCs, minicomputers, mainframe computers, cell phones, personal digital assistants, smart phones, personal computers, programmable consumer electronics, distributed computing environments that include any of the above systems or devices, and so on.

[0030] The ranking system may be described in the general context of computer-executable instructions, such as program modules, executed by one or more computers or other devices. Generally, program modules include routines, programs, objects, components, data structures, and so on that perform particular tasks or implement particular abstract data types. Typically, the functionality of the program modules may be combined or distributed as desired in various embodiments. For example, a separate computing system may crawl the web and generate the web graphs. Also, a separate computing system may provide search engine capabilities. Thus, the crawling and search engine functions can be separate from the supervised ranking functions. For example, one company may generate a supervised ranking component and distribute it to other companies for use in various applications, such as ranking web pages, scholarly articles, and so on.

[0031] FIG. 2 is a flow diagram that illustrates the processing of the generate supervised ranking component of the ranking system in one embodiment. The component is provided with a directed graph represented by a transition-probability matrix and with a partial ranking of the vertices of the directed graph. The component then generates a ranking of the vertices while attempting to satisfy the constraints of the partial ranking. In block 201, the component generates a transition-probability matrix from the adjacency matrix. The component may initialize the probability of each non-zero element of each row of the adjacency matrix to 1/n, where n is the number of non-zero elements in the row. In block 202, the component retrieves the partial ranking constraints. In block 203, the component invokes the optimize interactively component to rank the vertices of the web graph. In block 204, the component stores the ranking in the supervised ranking store and then completes.

[0032] FIG. 3 is a flow diagram that illustrates the processing of the optimize interactively component of the ranking system in one embodiment. The component is passed a transition-probability matrix and constraints. The component iteratively solves the first and second sub-problems and outputs the stationary distribution as the ranking of the vertices. In block 301, the component optimizes the stationary distribution with the perturbation matrix fixed according to the objective function of Equation 4. In block 302, the component optimizes the perturbation matrix with the stationary distribution according to the objective function of Equation 5. In decision block 303, if the perturbation matrix has converged, then the component continues at block 304, else the component loops to block 301 to perform the next iteration. In decision block 304, if the stationary distribution has converged, then the component continues at block 305, else the component loops to block 301 to start the next iteration. In block 305, since the perturbation matrix and stationary distribution have converged on a solution, the component outputs the stationary distribution as a ranking of the vertices and then returns.

[0033] Although the subject matter has been described in language specific to structural features and/or methodological acts, it is to be understood that the subject matter defined in the appended claims is not necessarily limited to the specific features or acts described above. Rather, the specific features and acts described above are disclosed as example forms of implementing the claims. The ranking system may be adapted to provide supervised ranking in conjunction with algorithms other than page rank algorithms. For example, the ranking system may be adapted to be used in conjunction with HITS- and DirectHit-based algorithms. The ranking system may also be used to rank vertices of a directed graph regardless of what the vertices and links represent. As described above, the vertices and links may represent web pages and their hyperlinks, scholarly articles and their citations, authors of scholarly articles and authors of their citations, and so on. In general, the ranking system attempts to rank the vertices of a directed graph by modifying the rankings indicated by the links as little as possible to satisfy the prior knowledge of the ranking. The ranking system may effect this minimal modification of the rankings indicated by the links by a minimal perturbation of the transition-probability matrix. Accordingly, the invention is not limited except as by the appended claims.