poster

An iterated graph laplacian approach for ranking on manifolds

Authors:

Mikhail Belkin,

Nathan SrebroAuthors Info & Claims

KDD '11: Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining

Pages 877 - 885

https://doi.org/10.1145/2020408.2020556

Published: 21 August 2011 Publication History

Abstract

Ranking is one of the key problems in information retrieval. Recently, there has been significant interest in a class of ranking algorithms based on the assumption that data is sampled from a low dimensional manifold embedded in a higher dimensional Euclidean space.

In this paper, we study a popular graph Laplacian based ranking algorithm [23] using an analytical method, which provides theoretical insights into the ranking algorithm going beyond the intuitive idea of "diffusion." Our analysis shows that the algorithm is sensitive to a commonly used parameter due to the use of symmetric normalized graph Laplacian. We also show that the ranking function may diverge to infinity at the query point in the limit of infinite samples. To address these issues, we propose an improved ranking algorithm on manifolds using Green's function of an iterated unnormalized graph Laplacian, which is more robust and density adaptive, as well as pointwise continuous in the limit of infinite samples.

We also for the first time in the ranking literature empirically explore two variants from a family of twice normalized graph Laplacians. Experimental results on text and image data support our analysis, which also suggest the potential value of twice normalized graph Laplacians in practice.

References

[1]

M. Belkin and P. Niyogi. Laplacian Eigenmaps for Dimensionality Reduction and Data Representation. Neural Comp, 15(6):1373--1396, 2003.

Digital Library

[2]

M. Belkin and P. Niyogi. Convergence of Laplacian Eigenmaps. In B. Schölkopf, J. Platt, and T. Hoffman, editors, Advances in Neural Information Processing Systems 19, pages 129--136. MIT Press, Cambridge, MA, 2007.

[3]

M. Belkin and P. Niyogi. Towards a Theoretical Foundation for Laplacian-Based Manifold Methods. Journal of Computer and System Sciences, 74(8):1289--1308, 2008.

Digital Library

[4]

A. Berlinet and C. Thomas-Agnan. Reproducing Kernel Hilbert Spaces in Probability and Statistics. Kluwer Academic Publishers, 2003.

[5]

O. Chapelle, B. Schölkopf, and A. Zien, editors. Semi-Supervised Learning. MIT Press, Cambridge, MA, 2006.

Digital Library

[6]

F. Chung and S.-T. Yau. Discrete Green's functions. J. Combinatorial Theory (A), 91:191--214, 2000.

Digital Library

[7]

R. R. Coifman and S. Lafon. Diffusion maps. Applied and Computational Harmonic Analysis, 21(1):5--30, 2006.

[8]

R. R. Coifman and M. Maggioni. Diffusion wavelets. Applied and Computational Harmonic Analysis, 21(1):53--94, 2006.

[9]

A. Grigor'yan. Heat kernels on weighted manifolds and applications. Cont. Math., 398:93--191, 2006.

[10]

M. Hein. Geometrical aspects of statistical learning theory. PhD thesis, Wissenschaftlicher Mitarbeiter am Max-Planck-Institut für biologische Kybernetik in Tübingen in der Abteilung, 2005.

[11]

M. Hein, J.-Y. Audibert, and U. V. Luxburg. Graph Laplacians and their Convergence on Random Neighborhood Graphs. Journal of Machine Learning Research, 8:1325--1368, 2007.

Digital Library

[12]

M. Maier, M. Hein, and U. von Luxburg. Optimal construction of k-nearest-neighbor graphs for identifying noisy clusters. Theoretical Computer Science, 410(19):1749--1764, 2009.

Digital Library

[13]

B. Nadler, N. Srebro, and X. Zhou. Semi-Supervised Learning with the Graph Laplacian: The Limit of Infinite Unlabelled Data. In Twenty-Third Annual Conference on Neural Information Processing Systems, 2009.

[14]

S. A. Nene, S. K. Nayar, and H. Murase. Columbia Object Image Library (COIL-20). Technical Report CUCS-005--96, February 1996.

[15]

A. Oliva and A. Torralba. Modeling the shape of the scene: a holistic representation of the spatial envelope. International Journal of Computer Vision, 42(3):145--175, 2001.

Digital Library

[16]

B. D. Reddy. Introductory Function Analysis, with Applications to Boundary Value Problems and Finite Elements. Springer, 1997.

[17]

A. Smola and R. Kondor. Kernels and regularization on graphs. In 16th Annual Conference on Learning Theory and 7th Kernel Workshop. Springer Verlag, 2003.

[18]

M. L. Stein. Interpolation of Spatial Data: Some Theory for Kriging. Springer, New York., 1999.

[19]

M. E. Taylor. Partial Differential Equations I: Basic Theory. Springer, New York, 1996.

[20]

U. von Luxburg. A Tutorial on Spectral Clustering. Statistics and Computing, 17(4):395--416, 2007.

Digital Library

[21]

U. von Luxburg, M. Belkin, and O. Bousquet. Consistency of spectral clustering. Ann. Statist., 36(2):555--586, 2008.

[22]

G. Wahba. Spline Models for Observational Data. Volume 59 of CBMS-NSF Regional Conference Series in Applied Mathematics, Philadelphia: SIAM, 1990.

[23]

D. Zhou, J. Weston, A. Gretton, O. Bousquet, and B. Schölkopf. Ranking on Data Manifolds. In Advances in Neural Information Processing Systems (NIPS) 16, pages 169--176. MIT Press, 2004.

[24]

X. Zhou and M. Belkin. Semi-supervised Learning by Higher Order Regularization. In G. Gordon, D. Dunson, and M. Dudík, editors, The 14th International Conference on Artificial Intelligence and Statistics, 2011.

[25]

X. Zhou and N. Srebro. Error Analysis of Laplacian Eigenmaps for Semi-supervised Learning. In G. Gordon, D. Dunson, and M. Dudík, editors, The 14th International Conference on Artificial Intelligence and Statistics, 2011.

[26]

X. Zhu. Semi-Supervised Learning Literature Survey. Technical report, 2008. University of Wisconsin Madison, Computer Sciences TR 1530.

Cited By

YUAN ACALDER JOSTING B(2021)A continuum limit for the PageRank algorithmEuropean Journal of Applied Mathematics10.1017/S095679252100009733:3(472-504)Online publication date: 27-Apr-2021
https://doi.org/10.1017/S0956792521000097
Yadav RAbhishek Verma SVenkatesan S(2020)Regularization on a rapidly varying manifoldInternational Journal of Machine Learning and Cybernetics10.1007/s13042-019-01059-5Online publication date: 18-Jan-2020
https://doi.org/10.1007/s13042-019-01059-5
Kim KRichardt CChang H(2020)Combining Task Predictors via Enhancing Joint PredictabilityComputer Vision – ECCV 202010.1007/978-3-030-58517-4_26(439-455)Online publication date: 10-Oct-2020
https://doi.org/10.1007/978-3-030-58517-4_26
Show More Cited By

Index Terms

An iterated graph laplacian approach for ranking on manifolds
1. Information systems
  1. Information retrieval
    1. Retrieval models and ranking

Recommendations

Complete local Fisher discriminant analysis with Laplacian score ranking for face recognition

In this paper, we propose a novel manifold learning method, called complete local Fisher discriminant analysis (CLFDA), for face recognition. LFDA often suffers from the small sample size problem, which makes the local within-class scatter matrix ...
Local linear Laplacian eigenmaps

We have derived local linear Laplacian eigenmaps (LLLE) a manifold learning algorithm.The LLLE finds multiple local linear structures.The LLLE used P artificial neighbors to construct the adjacency graph.The experimental results indicate that it can ...
Graph embedding discriminant analysis on Grassmannian manifolds for improved image set matching
CVPR '11: Proceedings of the 2011 IEEE Conference on Computer Vision and Pattern Recognition

A convenient way of dealing with image sets is to represent them as points on Grassmannian manifolds. While several recent studies explored the applicability of discriminant analysis on such manifolds, the conventional formalism of discriminant analysis ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

KDD '11: Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining

August 2011

1446 pages

ISBN:9781450308137

DOI:10.1145/2020408

General Chair:
Chid Apte
IBM Research
,
Program Chairs:
Joydeep Ghosh
UT Austin
,
Padhraic Smyth
UC Irvine

Copyright © 2011 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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 August 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Poster

Conference

KDD '11

Sponsor:

KDD '11: The 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

August 21 - 24, 2011

California, San Diego, USA

Acceptance Rates

Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

22
Total Citations
View Citations
380
Total Downloads

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

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

YUAN ACALDER JOSTING B(2021)A continuum limit for the PageRank algorithmEuropean Journal of Applied Mathematics10.1017/S095679252100009733:3(472-504)Online publication date: 27-Apr-2021
https://doi.org/10.1017/S0956792521000097
Yadav RAbhishek Verma SVenkatesan S(2020)Regularization on a rapidly varying manifoldInternational Journal of Machine Learning and Cybernetics10.1007/s13042-019-01059-5Online publication date: 18-Jan-2020
https://doi.org/10.1007/s13042-019-01059-5
Kim KRichardt CChang H(2020)Combining Task Predictors via Enhancing Joint PredictabilityComputer Vision – ECCV 202010.1007/978-3-030-58517-4_26(439-455)Online publication date: 10-Oct-2020
https://doi.org/10.1007/978-3-030-58517-4_26
Anis AEl Gamal AAvestimehr AOrtega A(2019)A Sampling Theory Perspective of Graph-Based Semi-Supervised LearningIEEE Transactions on Information Theory10.1109/TIT.2018.287989765:4(2322-2342)Online publication date: Apr-2019
https://doi.org/10.1109/TIT.2018.2879897
Alaíz CFanuel MSuykens J(2019)Robust classification of graph-based dataData Mining and Knowledge Discovery10.1007/s10618-018-0603-933:1(230-251)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1007/s10618-018-0603-9
Calder JSlepčev D(2019)Properly-Weighted Graph Laplacian for Semi-supervised LearningApplied Mathematics & Optimization10.1007/s00245-019-09637-3Online publication date: 7-Dec-2019
https://doi.org/10.1007/s00245-019-09637-3
Curado MEscolano FLozano MHancock E(2018)net4Lap: Neural Laplacian Regularization for Ranking and Re-Ranking2018 24th International Conference on Pattern Recognition (ICPR)10.1109/ICPR.2018.8545303(1366-1371)Online publication date: Aug-2018
https://doi.org/10.1109/ICPR.2018.8545303
Kim KPark JTompkin J(2018)High-Order Tensor Regularization with Application to Attribute Ranking2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition10.1109/CVPR.2018.00457(4349-4357)Online publication date: Jun-2018
https://doi.org/10.1109/CVPR.2018.00457
Feng FNie LWang XHong RChua TKando NSakai TJoho HLi Hde Vries AWhite R(2017)Computational Social IndicatorsProceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval10.1145/3077136.3080773(455-464)Online publication date: 7-Aug-2017
https://dl.acm.org/doi/10.1145/3077136.3080773
Wei WGao BLiu TWang TLi GLi H(2016)A Ranking Approach on Large-Scale Graph With Multidimensional Heterogeneous InformationIEEE Transactions on Cybernetics10.1109/TCYB.2015.241823346:4(930-944)Online publication date: Apr-2016
https://doi.org/10.1109/TCYB.2015.2418233
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