The PageRank Citation Ranking: Bringing Order to the Web

by Lawrence Page, Sergey Brin, Rajeev Motwani and Terry Winograd

This might be the famous paper introducing the PageRank to the ranking research and the famous search engine Google to the Internet. The key idea behind the PageRank that differentiate it from the back link counts is that a back link from an authorized site should be more valuable. Therefore the backlinks must be weighted by its own rank. So the last scanned paper's recursion makes sense.

A more interesting question is how to make a distributed version. I think in a way this is equivalent to solving some linear system but I haven't really try to derive it.

This could be a contributing factor for real ranking algorithm (which uses many other features as well).

The Intelligent Surfer: Probabilistic Combination of Link and Content Information in PageRank

by Matthew Richardson and Pedro Domingos

I started to read those papers by Domingos to follow their idea on Markov logic. Now I have already read a few pages from their tutorials and wish to know more about their past research background.

This paper talks about ranking, which I am not quite familiar with. This paper introduces two previous methods, i.e. HITS and PageRank, which I'd like to scan later. The HITS model is little bit complicated and can't be served online (they have to compute hubs and authorities at query time) while PageRank can utilize the PageRank at offline stage (i.e. after the crawling, they may compute the PageRank using incoming links and outgoing links, which later serves as a factor contributing to the final ranking function).

The graph PageRank builds consists of links:

• using the outgoing links and incoming links;
• if a webpage has no outgoing links, it links to all other pages;

So we may set a random walker on the graph and find the probability it gets to the page using the formula

\displaystyle P(j) = \frac{1 - \beta}{N} + \beta \sum_{i \in B(j)} \frac{P(i)}{|F_i|}

where B(j) contains all pages link to page j and F(i) contains the pages linked from page i.
This paper's main idea is to incorporate the query information into the PageRank, which, you may have already seen from tabove, contains nothing about the query q. Let

P_q(j) = (1 - \beta) P_q'(j) + \beta \sum_{i \in B_j} P_q(i) P_q(i \to j)

, where those query related terms are all derived from query relevance scores, e.g.

P_q'(j) = R_q(i) / \sum_{i \in W}R_q(i), \qquad P_q(i \to j) = R_q(i) / \sum_{j \in F_i} R_q(j)

.
To overcome the computation problem, the author suggests we pre-compute the ranking score for the search queries offline.

Evaluating Search Engines by Modeling the Relationship Between Relevance and Clicks

by Ben Carterette and Rosie Jones

This paper tells us about a method to evaluating two ranking reseults based on clicks of users. We know the ranking affects exposures of the links, i.e. the higher rank one item has, the more attension human beings pay to. Therefore it is more reasonable to use a discounted relavance called discounted cumulative gain (DCG)

\mathrm{DCG}_l = \mathrm{rel}_1 + \sum_{i = 2}^l \frac{\mathrm{rel}_i}{\log_2 i}.

That is, the rank 1 item has no discount while rank i item has a discount ratio of 1/\log_2 i.

So if we want to compare two ranking results, we have to calculate the relevance score given by given the query. This is not always known. People might have been asked to score the documents with discrete values (on a scale of 5, e.g.) but not all documents will be marked. We model this scale with a multinomial distribution and simulated the scoring procedure and compare the two DCG values. If for 95% cases, one is higher than the other, we might assert it is better.

The author proposed quite a simple model to model \Pr(X_i \mid q, c, ). It is an ordinal logistic regression model with linear and quadratic features. So when we trained the model, we can simulate the DCG and compare two rankings.

Support Vector Machine Learning for Image Retrieval

by Lei Zhang, Fuzong Lin and Bo Zhang

This is actually a vision paper. I am not sure whether the active learning is really just a version. In a query of similar images, the user labels some relevant and irrelevant images. A SVM is then used to rank the images correspondingly. This will help the query though but will not help the later search. A possible improvement is adding some manifold regularization. Quite contrary to my expectation. Hmm...

Structured Ranking Learning using Cumulative Distribution Networks

by Jim C. Huang and Brendan J. Frey

This NIPS paper further elucidates how to take advantage of CDN's idea to tackle a ranking problem. The author introduce a probability distributon for the preference variable given an ordered relationship. Therefore a natural choice of the ranking scheme is to maximize the likelihood or equivalently to minimize the negative log-likelihood (loss function). Once the ranking function could be parameterized, the optimization problem could be solved. The paper employs a nonparametric model. CDN here plays the role of setting up the CDF for the observed preference variable.

With this formulation, several earlier proposed algorithms could be regarded its special cases, such as RankNet, ListNet and ListMLE. I will take a close look at those ranking algorithms later.

Cumulative Distribution Networks and the Derivative-Sum-Product Algorithm

by Jim C. Huang and Brendan J. Frey

The paper first proposed novel probabilistic graphical model, i.e. CDN. The model differs with MRF and Bayesian belief network in several aspects. The basic idea of the network resembles the factor graph of MRF. The factor graph of an MRF consists a vertex set of two parts: one of the original vertices of the MRF, the other of each cliques. The representer theorem of MRF actually tells us each clique is a nonnegative potential function (unnormalized PDF, hence the vertex is often referred to by function vertex). In CDN, however, each function vertex corresponds to a CDF-like function (i.e. cumulative function as in the paper). As long as these cumulative functions satisfy several simple properties (which might be easily proved as in the paper), their product is a decent CDF.

To do inference in CDF, the authors proposed an algorithm that resembles sum-product algorithm for factor graphs (i.e. belief propagation for polytrees). We know the derivative of the CDF is PDF, therefore it looks natural their inference is called Derivative-Sum-Product (DSP) algorithm. I will read the details about the algorithm later.

This framework is applied to a ranking problem.

Here we can see, we have three teams, (X₁, X₂), (X₃, X₄) and (X₅, X₆, X₇). The function s_i(x_i) is the skill of the player. The performance of each team is the sum of all players, a function of x_i. And we get R₁, R₂ and R₃. We do have the rank of these teams, which comes as an ordered graph whose relationships are represented with h. The prediction is carried out with skill functions learned with previous results. In this model every function vertex is a CDF of a Gaussian and DSP could be computed easily. I think the details are worth trying to see.

In the end, several applications are pointed out, webpage ranking, collaborative filtering and etc. They also intended to focus on the learning part of the model in later research and the DSP algorithm, as the belief propagation, is only applicable to trees.

Several related topic:
convolutional factor graph: Convolutional factor graphs as probabilistic models, UAI 2004.

Learning Random Walks to Rank Nodes in Graphs

by Alekh Agarwal and Soumen Chakrabarti

Well, forget about the other Agarwal who published the ICML 06 paper (I mistook them for one). Sorry about my carelessness. Thanks for the anonymous reader who kindly pointed it out.

In this paper, they explore the relationship of two strategies for ranking graphs, one from NetRank, which seeks to minimize a KL divergence, one proposed in the paper mentioned above, which tackles a SVM-like optimization and is called Laplacian regularizer. Their main result contains (in theorems):

• The KL divergence bound suggests a bound for the Laplacian regularizer (which indicates a possibly acceptable smoothness of the ranking function).
• The generalization capability can be bounded (usu. in the form R <= R_emp + sth).

which I don't fully understand.

I think maybe I might read something about the PageRank and NetRank stuffs when I have time.

Ranking on Graph Data

by Shivani Agarwal

The ranking problem asks for a function which gives us an order of samples. This requirement can be found on search engines, which give the user a sequence of search results of the preferred order of the user. I don't have earlier experience of ranking problems, so I am just curious about this article. After scanning, it turns out highly related to SVM theory.

There is a ranking risk matrix that descibe the risk of ranking error.

So the empirical ranking risk can be formulated as a functional of ranking function, which is what we are looking for. As for a graph, the function degenerates to a vector. As is in SVM, a regularizer is chosen so as to smooth the function by punish the divergence of values on nearby vertices. On thinking about this, the Laplacian regularizer is a commonly used one. (Just think about the Laplacian Eigenmap, the optimized value)

Directed graphs can be treated likewise. The paper later suggests a connection to RKHS and application in bioinformatics. Indeed, multiple alignment requires a ranking result.

Since the loss function relaxed in this paper is still Hinge loss, the idea of Trading Convexity for Scalability should be applicable to it.