Learning random walks to rank nodes in graphs

Agarwal, Alekh ; Chakrabarti, Soumen (2007) Learning random walks to rank nodes in graphs In: ICML '07 Proceedings of the 24th International Conference on Machine Learning, June 20 - 24, 2007, Corvallis, Oregon.

PDF - Other

Official URL: http://dl.acm.org/citation.cfm?id=1273498


Ranking nodes in graphs is of much recent interest. Edges, via the graph Laplacian are used to encourage local smoothness of node scores in SVM-like formulations with generalization guarantees. In contrast, Page-rank variants are based on Markovian random walks. For directed graphs, there is no simple known correspondence between these views of scoring/ranking. Recent scalable algorithms for learning the Pagerank transition probabilities do not have generalization guarantees. In this paper we show some correspondence results between the Laplacian and the Pagerank approaches and give new generalization guarantees for the latter. We enhance the Pagerank-learning approaches to use an additive margin. We also propose a general framework for rank-sensitive score-learning and apply it to Laplacian smoothing. Experimental results are promising.

Item Type:Conference or Workshop Item (Paper)
Source:Copyright of this article belongs to ICML '07 Proceedings of the 24th International Conference, Association for Computing Machinery.
ID Code:100062
Deposited On:12 Feb 2018 12:27
Last Modified:12 Feb 2018 12:27

Repository Staff Only: item control page