More Web Proxy on the site http://driver.im/

Article

Ranking on graph data

Author:

Shivani AgarwalAuthors Info & Claims

ICML '06: Proceedings of the 23rd international conference on Machine learning

Pages 25 - 32

https://doi.org/10.1145/1143844.1143848

Published: 25 June 2006 Publication History

Abstract

In ranking, one is given examples of order relationships among objects, and the goal is to learn from these examples a real-valued ranking function that induces a ranking or ordering over the object space. We consider the problem of learning such a ranking function when the data is represented as a graph, in which vertices correspond to objects and edges encode similarities between objects. Building on recent developments in regularization theory for graphs and corresponding Laplacian-based methods for classification, we develop an algorithmic framework for learning ranking functions on graph data. We provide generalization guarantees for our algorithms via recent results based on the notion of algorithmic stability, and give experimental evidence of the potential benefits of our framework.

References

[1]

Agarwal, S., Graepel, T., Herbrich, R., Har-Peled, S., & Roth, D. (2005). Generalization bounds for the area under the ROC curve. Journal of Machine Learning Research, 393--425.]]

Digital Library

[2]

Agarwal, S., & Niyogi, P. (2005). Stability and generalization of bipartite ranking algorithms. Proceedings of the 18th Annual Conference on Learning Theory.]]

Digital Library

[3]

Altschul, S. F., Madden, T. L., Schaffer, A. A., Zhang, J., Zhang, Z., Miller, W., & Lipman, D. J. (1997). Gapped BLAST and PSI-BLAST: a new generation of protein database search programs. Nucleic Acids Research, 25, 3389--3402.]]

[4]

Belkin, M., Matveeva, I., & Niyogi, P. (2004). Regularization and semi-supervised learning on large graphs. Proceedings of the 17th Annual Conference on Learning Theory.]]

[5]

Belkin, M., & Niyogi, P. (2004). Semi-supervised learning on Riemannian manifolds. Machine Learning, 56, 209--239.]]

Digital Library

[6]

Bousquet, O., & Elisseeff, A. (2002). Stability and generalization. Journal of Machine Learning Research, 2, 499--526.]]

Digital Library

[7]

Boyd, S., & Vandenberghe, L. (2004). Convex optimization. Cambridge University Press.]]

[8]

Burges, C. J. C. (1998). A tutorial on support vector machines for pattern recognition. Data Mining and Knowledge Discovery, 2, 121--167.]]

Digital Library

[9]

Chung, F. R. K. (1997). Spectral graph theory. American Mathematical Society.]]

[10]

Chung, F. R. K. (2005). Laplacians and the Cheeger inequality for directed graphs. Annals of Combinatorics, 9, 1--19.]]

[11]

Cohen, W. W., Schapire, R. E., & Singer, Y. (1999). Learning to order things. Journal of Artificial Intelligence Research, 10, 243--270.]]

[12]

Cortes, C., & Mohri, M. (2004). AUC optimization vs. error rate minimization. Advances in Neural Information Processing Systems 16.]]

[13]

Crammer, K., & Singer, Y. (2002). Pranking with ranking. Advances in Neural Information Processing Systems 14.]]

[14]

Freund, Y., Iyer, R., Schapire, R. E., & Singer, Y. (2003). An efficient boosting algorithm for combining preferences. Journal of Machine Learning Research, 4, 933--969.]]

Digital Library

[15]

Herbrich, R., Graepel, T., & Obermayer, K. (2000). Large margin rank boundaries for ordinal regression. Advances in Large Margin Classifiers, 115--132.]]

[16]

Joachims, T. (1999). Making large-scale SVM learning practical. Advances in Kernel Methods - Support Vector Learning.]]

Digital Library

[17]

Joachims, T. (2003). Transductive learning via spectral graph partitioning. Proceedings of the 20th International Conference on Machine Learning.]]

[18]

Murzin, A., Brenner, S. E., Hubbard, T., & Chothia, C. (1995). SCOP: A structural classification of proteins database for the investigation of sequences and structures. Journal of Molecular Biology, 247, 536--540.]]

[19]

Platt, J. (1999). Fast training of support vector machines using sequential minimal optimization. Advances in Kernel Methods - Support Vector Learning.]]

Digital Library

[20]

Roweis, S. T., & Saul, L. K. (2000). Nonlinear dimensionality reduction by locally linear embedding. Science, 290, 2323--2326.]]

[21]

Sindhwani, V., Niyogi, P., & Belkin, M. (2005). Beyond the point cloud: from transductive to semi-supervised learning. Proceedings of the 22nd International Conference on Machine Learning.]]

Digital Library

[22]

Strang, G. (1988). Linear algebra and its applications. Brooks Cole. 3rd edition.]]

[23]

Tenenbaum, J., de Silva, V., & Langford, J. C. (2000). A global geometric framework for nonlinear dimensionality reduction. Science, 290, 2319--2323.]]

[24]

Vapnik, V. N. (1998). Statistical learning theory. Wiley]]

Digital Library

[25]

Weston, J., Eliseeff, A., Zhou, D., Leslie, C., & Noble, W. S. (2004). Protein ranking: from local to global structure in the protein similarity network. Proceedings of the National Academy of Science, 101, 6559--6563.]]

[26]

Zhou, D., Huang, J., & Schöölkopf, B. (2005). Learning from labeled and unlabeled data on a directed graph. Proceedings of the 22nd International Conference on Machine Learning.]]

Digital Library

[27]

Zhou, D., & Schöölkopf, B. (2004). A regularization framework for learning from graph data. ICML Workshop on Statistical Relational Learning.]]

[28]

Zhou, D., Weston, J., Gretton, A., Bousquet, O., & Schöölkopf, B. (2004). Ranking on data manifolds. Advances in Neural Information Processing Systems 16.]]

Cited By

Cai JZhang YFan JDu YGuo WLarson K(2024)Dual contrastive graph-level clustering with multiple cluster perspectives alignmentProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence10.24963/ijcai.2024/417(3770-3779)Online publication date: 3-Aug-2024
https://dl.acm.org/doi/10.24963/ijcai.2024/417
Mao HMao MMao F(2024)Ranking on user–item heterogeneous graph for Ecommerce next basket recommendationsKnowledge-Based Systems10.1016/j.knosys.2024.111863296:COnline publication date: 19-Jul-2024
https://dl.acm.org/doi/10.1016/j.knosys.2024.111863
Shi YQuan PXiao YLei MNiu L(2023)Graph Influence NetworkIEEE Transactions on Cybernetics10.1109/TCYB.2022.316447453:10(6146-6159)Online publication date: Oct-2023
https://doi.org/10.1109/TCYB.2022.3164474
Show More Cited By

Index Terms

Ranking on graph data
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
  2. Probability and statistics
    1. Statistical paradigms
      1. Statistical graphics

Recommendations

Dynamic link-based ranking over large-scale graph-structured data
Retrieving keyworded subgraphs with graph ranking score

Keyword queries have long been popular to search engines and to the information retrieval community and have recently gained momentum for its usage in the expert systems community. The conventional semantics for processing a user query is to find a set ...
Optimal vertex ranking of block graphs

A vertex ranking of an undirected graph G is a labeling of the vertices of G with integers such that every path connecting two vertices with the same label i contains an intermediate vertex with label j>i. A vertex ranking of G is called optimal if it ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ICML '06: Proceedings of the 23rd international conference on Machine learning

June 2006

1154 pages

ISBN:1595933832

DOI:10.1145/1143844

Program Chairs:
William Cohen,
Andrew Moore

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 June 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

ICML '06 Paper Acceptance Rate 140 of 548 submissions, 26%;

Overall Acceptance Rate 140 of 548 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

81
Total Citations
View Citations
1,214
Total Downloads

Downloads (Last 12 months)34
Downloads (Last 6 weeks)6

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Cai JZhang YFan JDu YGuo WLarson K(2024)Dual contrastive graph-level clustering with multiple cluster perspectives alignmentProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence10.24963/ijcai.2024/417(3770-3779)Online publication date: 3-Aug-2024
https://dl.acm.org/doi/10.24963/ijcai.2024/417
Mao HMao MMao F(2024)Ranking on user–item heterogeneous graph for Ecommerce next basket recommendationsKnowledge-Based Systems10.1016/j.knosys.2024.111863296:COnline publication date: 19-Jul-2024
https://dl.acm.org/doi/10.1016/j.knosys.2024.111863
Shi YQuan PXiao YLei MNiu L(2023)Graph Influence NetworkIEEE Transactions on Cybernetics10.1109/TCYB.2022.316447453:10(6146-6159)Online publication date: Oct-2023
https://doi.org/10.1109/TCYB.2022.3164474
Alsaif SHidri AHidri M(2021)Towards Inferring Influential Facebook UsersComputers10.3390/computers1005006210:5(62)Online publication date: 9-May-2021
https://doi.org/10.3390/computers10050062
Kelly T(2021)Crashproofing the Original NoSQL Key-Value StoreQueue10.1145/3487019.348735319:4(5-18)Online publication date: 19-Sep-2021
https://dl.acm.org/doi/10.1145/3487019.3487353
Tiganov DNguyen Quang Do LAli K(2021)Designing UIs for Static Analysis ToolsQueue10.1145/3487019.348702619:4(97-118)Online publication date: 16-Sep-2021
https://dl.acm.org/doi/10.1145/3487019.3487026
Nadeem A(2021)Human-Centered Approach to Static-Analysis-Driven Developer ToolsQueue10.1145/3487019.348702419:4(68-95)Online publication date: 16-Sep-2021
https://dl.acm.org/doi/10.1145/3487019.3487024
Thomson P(2021)Static Analysis: An IntroductionQueue10.1145/3487019.348702119:4(29-41)Online publication date: 16-Sep-2021
https://dl.acm.org/doi/10.1145/3487019.3487021
Quigley ELin WZhu YFedkiw R(2021)Three Dimensional Reconstruction of Botanical Trees with Simulatable GeometryProceedings of the ACM on Computer Graphics and Interactive Techniques10.1145/34801464:3(1-16)Online publication date: 27-Sep-2021
https://dl.acm.org/doi/10.1145/3480146
Kim NLing HXie Zvan de Panne M(2021)Flexible Motion Optimization with Modulated Assistive ForcesProceedings of the ACM on Computer Graphics and Interactive Techniques10.1145/34801444:3(1-25)Online publication date: 27-Sep-2021
https://dl.acm.org/doi/10.1145/3480144
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents