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

article

Laplacian Eigenmaps for dimensionality reduction and data representation

Authors:

Mikhail Belkin,

Partha NiyogiAuthors Info & Claims

Neural Computation, Volume 15, Issue 6

Pages 1373 - 1396

https://doi.org/10.1162/089976603321780317

Published: 01 June 2003 Publication History

Abstract

One of the central problems in machine learning and pattern recognition is to develop appropriate representations for complex data. We consider the problem of constructing a representation for data lying on a low-dimensional manifold embedded in a high-dimensional space. Drawing on the correspondence between the graph Laplacian, the Laplace Beltrami operator on the manifold, and the connections to the heat equation, we propose a geometrically motivated algorithm for representing the high-dimensional data. The algorithm provides a computationally efficient approach to nonlinear dimensionality reduction that has locality-preserving properties and a natural connection to clustering. Some potential applications and illustrative examples are discussed.

References

[1]

Belkin, M., & Niyogi, P. (2002). Laplacian eigenmaps and spectral techniques for embedding and clustering. In T. K. Leen, T. G. Dietterich, & V. Tresp (Eds.), Advances in neural information processing systems, 14. Cambridge, MA: MIT Press.

[2]

Bernstein, M., de Silva, V., Langford, J. C., & Tenenbaum, J. B. (2000). Graph approximations to geodesics on embedded manifolds. Available on-line: http://isomap.stanford.edu/BdSLT.pdf.

[3]

Chung, Fan R. K. (1997). Spectral graph theory. Providence, RI: American Mathematical Society.

[4]

Chung, Fan R. K., Grigor'yan, A., & Yau, S.-T. (2000). Higher eigenvalues and isoperimetric inequalities on Riemannian manifolds and graphs. Communications on Analysis and Geometry, 8, 969-1026.

[5]

Hadley, S. W., Mark, B. L., & Vanelli, A. (1992). An efficient eigenvector approach for finding netlist partitions. IEEE Transactions on Computer-Aided Design, 11(7), 885-892.

Digital Library

[6]

Haykin, S. (1999). Neural networks: A comprehensive foundation. Upper Saddle River, NJ: Prentice Hall.

Digital Library

[7]

Hendrickson, B., & Leland, R. (1993). Multidimensional spectral load balancing. In Proceedings of the Sixth SIAM Conference on Parallel Processing for Scientific Computing (pp. 953-961). Philadelphia: SIAM.

[8]

Indyk, P. (2000). Dimensionality reduction techniques for proximity problems. Paper presented at the Eleventh Symposium on Discrete Algorithms, San Francisco.

Digital Library

[9]

Kondor, R. I., & Lafferty, J. (2002). Diffusion kernels on graphs and other discrete input spaces. In Proceedings of the ICML 2002.

Digital Library

[10]

Nash, J. (1954). C1 isometric imbeddings. Annals of Mathematics, 56, 383-396.

[11]

Nash, J. (1956). The imbedding problem for Riemannian Manifolds. Annals of Mathematics, 63, 20-63.

[12]

Ng, A. Y., Jordan, M., & Weiss, Y. (2002). On spectral clustering: Analysis and an algorithm. In T. K. Leen, T. G. Dietterich, & V. Tresp (Eds.), Advances in neural information processing systems, 14. Cambridge, MA: MIT Press.

[13]

Rosenberg, S. (1997). The Laplacian on a Riemannian manifold. Cambridge: Cambridge University Press.

[14]

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

[15]

Schölkopf, B., Smola, A., & Müülller, K.-R. (1998). Nonlinear component analysis as a kernel eigenvalue problem. Neural Computation, 10(5), 1299-1319.

Digital Library

[16]

Seung, H. S., & Lee, D. D. (2000). The manifold way of perception. Science, 290, 2268-2269.

[17]

Shi, J., & Malik, J. (1997). Normalized cuts and image segmentation. IEEE Conf. Computer Vision and Pattern Recognition (pp. 731-737).

Digital Library

[18]

Simon, H. D. (1991). Partitioning of unstructured problems for parallel processing. Computing Systems in Engineering, 2, 135-148.

[19]

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

Cited By

Song ZWu ZChen SZhu H(2024)Transductive classification via patch alignmentAI Communications10.3233/AIC-22017937:1(37-51)Online publication date: 21-Mar-2024
https://dl.acm.org/doi/10.3233/AIC-220179
Li YYou ZWang SMi CWang MHuang YYi H(2024)Attention-Based Learning for Predicting Drug-Drug Interactions in Knowledge Graph Embedding Based on Multisource Fusion InformationInternational Journal of Intelligent Systems10.1155/2024/51559972024Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1155/2024/5155997
Wang DLi TDeng PLuo ZZhang PLiu KHuang W(2024)DNSRF: Deep Network-based Semi-NMF Representation FrameworkACM Transactions on Intelligent Systems and Technology10.1145/367040815:5(1-20)Online publication date: 7-Nov-2024
https://dl.acm.org/doi/10.1145/3670408
Show More Cited By

Index Terms

Laplacian Eigenmaps for dimensionality reduction and data representation

Recommendations

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 ...
Discrete Hessian Eigenmaps method for dimensionality reduction

For a given set of data points lying on a low-dimensional manifold embedded in a high-dimensional space, the dimensionality reduction is to recover a low-dimensional parametrization from the data set. The recently developed Hessian Eigenmaps method is a ...
Constrained Laplacian Eigenmap for dimensionality reduction

Dimensionality reduction is a commonly used tool in machine learning, especially when dealing with high dimensional data. We consider semi-supervised graph based dimensionality reduction in this paper, and a novel dimensionality reduction algorithm ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Neural Computation

Neural Computation Volume 15, Issue 6

June 2003

246 pages

ISSN:0899-7667

Issue’s Table of Contents

Publisher

MIT Press

Cambridge, MA, United States

Publication History

Published: 01 June 2003

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1,634
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Song ZWu ZChen SZhu H(2024)Transductive classification via patch alignmentAI Communications10.3233/AIC-22017937:1(37-51)Online publication date: 21-Mar-2024
https://dl.acm.org/doi/10.3233/AIC-220179
Li YYou ZWang SMi CWang MHuang YYi H(2024)Attention-Based Learning for Predicting Drug-Drug Interactions in Knowledge Graph Embedding Based on Multisource Fusion InformationInternational Journal of Intelligent Systems10.1155/2024/51559972024Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1155/2024/5155997
Wang DLi TDeng PLuo ZZhang PLiu KHuang W(2024)DNSRF: Deep Network-based Semi-NMF Representation FrameworkACM Transactions on Intelligent Systems and Technology10.1145/367040815:5(1-20)Online publication date: 7-Nov-2024
https://dl.acm.org/doi/10.1145/3670408
Wu ZLi HChen GYu ZGu XWang YCai JKankanhalli MPrabhakaran BBoll SSubramanian RZheng LSingh VCesar PXie LXu D(2024)3D Question Answering with Scene Graph ReasoningProceedings of the 32nd ACM International Conference on Multimedia10.1145/3664647.3681517(1370-1378)Online publication date: 28-Oct-2024
https://dl.acm.org/doi/10.1145/3664647.3681517
Chen YWu YHan NFang XChen BWen JCai JKankanhalli MPrabhakaran BBoll SSubramanian RZheng LSingh VCesar PXie LXu D(2024)Partial Multi-label Learning Based On Near-Far Neighborhood Label Enhancement And Nonlinear GuidanceProceedings of the 32nd ACM International Conference on Multimedia10.1145/3664647.3681300(3722-3731)Online publication date: 28-Oct-2024
https://dl.acm.org/doi/10.1145/3664647.3681300
Piao MSheng YYan JJin C(2024)Image Hash Layer Triggered CNN Framework for Wafer Map Failure Pattern Retrieval and ClassificationACM Transactions on Knowledge Discovery from Data10.1145/363805318:4(1-26)Online publication date: 13-Feb-2024
https://dl.acm.org/doi/10.1145/3638053
Wang YYan XJin SHuang HXu QZhang QDu BJiang JBaeza-Yates RBonchi F(2024)Self-Supervised Learning for Graph Dataset CondensationProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671682(3289-3298)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671682
Ding WCherukumalli MChikoti SChaudhri VHui Yang GWang HHan SHauff CZuccon GZhang Y(2024)JPEC: A Novel Graph Neural Network for Competitor Retrieval in Financial Knowledge GraphsProceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval10.1145/3626772.3657677(2755-2759)Online publication date: 10-Jul-2024
https://dl.acm.org/doi/10.1145/3626772.3657677
Yao TSun JCao DZhang KChen GChua TNgo CKa-Wei Lee RKumar RLauw H(2024)MuGSI: Distilling GNNs with Multi-Granularity Structural Information for Graph ClassificationProceedings of the ACM Web Conference 202410.1145/3589334.3645542(709-720)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645542
Kim MBaek SChua TNgo CKa-Wei Lee RKumar RLauw H(2024)Hierarchical Position Embedding of Graphs with Landmarks and Clustering for Link PredictionProceedings of the ACM Web Conference 202410.1145/3589334.3645372(389-400)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645372
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents