Alekh Agarwal
ABSTRACT
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.
- Agarwal, A., Chakrabarti, S., & Aggarwal, S. (2006). Learning to rank networked entities. SIGKDD Conference (pp. 14--23). Google Scholar
Digital Library
- Agarwal, S. (2006). Ranking on graph data. ICML (pp. 25--32). Google ScholarDigital Library
- Agarwal, S., Cortes, C., & Herbrich, R. (Eds.). (2005). Learning to rank, NIPS Workshop.Google Scholar
- Agarwal, S., & Niyogi, P. (2005). Stability and generalization of bipartite ranking algorithms. COLT (pp. 32--47). Bertinoro. Google ScholarDigital Library
- Balmin, A., Hristidis, V., & Papakonstantinou, Y. (2004). Authority-based keyword queries in databases using ObjectRank. VLDB. Toronto.Google Scholar
- Bousquet, O., & Elisseeff, A. (2002). Stability and generalization. Journal of Machine Learning Research, 2, 499--526. Google ScholarDigital Library
- Brin, S., & Page, L. (1998). The anatomy of a large-scale hypertextual web search engine. WWW Conference. Google ScholarDigital Library
- Burges, C., Shaked, T., Renshaw, E., Lazier, A., Deeds, M., Hamilton, N., & Hullender, G. (2005). Learning to rank using gradient descent. ICML. Google ScholarDigital Library
- Burges, C. J. C., Ragno, R., & Le, Q. V. (2006). Learning to rank with nonsmooth cost functions. NIPS.Google Scholar
- Chakrabarti, D., Zhan, Y., & Faloutsos, C. (2004). R-MAT: A recursive model for graph mining. ICDM.Google Scholar
- Chung, F. (2005). Laplacians and the Cheeger inequality for directed graphs. Annals of Combinatorics, 9, 1--19.Google ScholarCross Ref
- Cover, T. M., & Thomas, J. A. (1991). Elements of information theory. John Wiley and Sons, Inc. Google ScholarDigital Library
- Herbrich, R., Graepel, T., & Obermayer, K. (1999). Support vector learning for ordinal regression. International Conference on Artificial Neural Networks (pp. 97--102).Google ScholarCross Ref
- Jeh, G., & Widom, J. (2003). Scaling personalized web search. WWW Conference (pp. 271--279). Google ScholarDigital Library
- Jeong, H., Tombor, B., Albert, R., Oltvai, Z. N., & Barabáási, A.-L. (2000). The large-scale organization of metabolic networks. Nature, 407, 651--654.Google ScholarCross Ref
- Joachims, T. (2002). Optimizing search engines using clickthrough data. SIGKDD Conference. ACM. Google ScholarDigital Library
- Langville, A. N., & Meyer, C. D. (2004). Deeper inside PageRank. Internet Mathematics, 1, 335--380.Google ScholarCross Ref
- Matveeva, I., Burges, C., Burkard, T., Laucius, A., & Wong, L. (2006). High accuracy retrieval with multiple nested ranker. SIGIR Conference (pp. 437--444). Seattle, Washington, USA. Google ScholarDigital Library
- Rudin, C. (2006). Ranking with a p-norm push. COLT (pp. 589--604). Google ScholarDigital Library
- Smola, A., & Kondor, R. (2003). Kernels and regularization on graphs. COLT (pp. 144--158).Google Scholar
- Taskar, B. (2004). Learning structured prediction models: A large margin approach. Doctoral dissertation, Stanford University. Google ScholarDigital Library
- Zhou, D., Huang, J., & Schöölkopf, B. (2005). Learning from labeled and unlabeled data on a directed graph. ICML (pp. 1041--1048). Google ScholarDigital Library
- Zhou, D., & Schöölkopf, B. (2004). A regularization framework for learning from graph data. ICML Workshop on Statistical Relational Learning.Google Scholar
Recommendations
Random Walks on Regular and Irregular Graphs
For an undirected graph and an optimal cyclic list of all its vertices, the cyclic cover time is the expected time it takes a simple random walk to travel from vertex to vertex along the list until it completes a full cycle. The main result of this ...
Short Random Walks on Graphs
The short-term behavior of random walks on graphs is studied, in particular, the rate at which a random walk discovers new vertices and edges. A conjecture by Linial that the expected time to find $\cal N$ distinct vertices is $O({\cal N}^{3})$ is ...
Coalescing random walks and voting on graphs
PODC '12: Proceedings of the 2012 ACM symposium on Principles of distributed computingIn a coalescing random walk, a set of particles make independent discrete-time random walks on a graph. Whenever one or more particles meet at a vertex, they unite to form a single particle, which then continues the random walk through the graph. ...
Comments