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.