skip to main content
10.1145/1871437.1871493acmconferencesArticle/Chapter ViewAbstractPublication PagescikmConference Proceedingsconference-collections
research-article

Multilevel manifold learning with application to spectral clustering

Published: 26 October 2010 Publication History

Abstract

In the past decade, a number of nonlinear dimensionality reduction methods using an affinity graph have been developed for manifold learning. This paper explores a multilevel framework with the goal of reducing the cost of unsupervised manifold learning and preserving the embedding quality at the same time. An application to spectral clustering is also presented. Experimental results indicate that our multilevel approach is an appealing alternative to standard techniques.

References

[1]
S. T. Barnard and H. D. Simon. A fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems. Concurrency: Practice and Experience, 6:101--107, 1994.
[2]
M. Belkin and P. Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation, 15(6):1373--1396, 2003.
[3]
Y. Bengio, J.-F. Paiement, P. Vincent, O. Delalleau, N. L. Roux, and M. Ouimet. Out-of-sample extensions for LLE, Isomap, MDS, Eigenmaps, and spectral clustering. In Advances in Neural Information Processing Systems 16. MIT Press, Cambridge, MA, 2004.
[4]
D. L. Boley. Principal direction divisive partitioning. Data Mining and Knowledge Discovery, 2(4):324--344, 1998.
[5]
T. Chan, B. Smith, and J. Zou. Multigrid and domain decomposition methods for unstructured meshes. In The 3rd International Conference on Advances in Numerical Methods and Applications, pages 53--62, Sofia, Bulgaria, 1994.
[6]
J. Chen, H.-r. Fang, and Y. Saad. Fast approximate kNN graph construction for high dimensional data via recursive Lanczos bisection. J. of Machine Learning Research, 10:1989--2012, 2009.
[7]
R. R. Coifman and S. Lafon. Diffusion maps. Appl. Comput. Harmon. Anal., 21:5--30, 2006.
[8]
V. de Silva and J. B. Tenenbaum. Global versus local methods in nonlinear dimensionality reduction. In Advances in Neural Information Processing Systems 15, pages 705--712. MIT Press, Cambridge, MA, 2003.
[9]
E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269--271, 1959.
[10]
D. L. Donoho and C. Grimes. Hessian eigenmaps: Locally linear embedding techniques for high-dimensional data. In Proceedings of the National Academy of Arts and Sciences, pages 100:5591--5596, 2003.
[11]
G. B. Huang, M. Ramesh, T. Berg, and E. Learned-Miller. Labeled faces in the wild: A database for studying face recognition in unconstrained environments. Technical Report 07-49, University of Massachusetts, Amherst, October 2007.
[12]
G. Karypis and V. Kumar. Multilevel k-way partitioning scheme for irregular graphs. J. Parallel Distrib. Comput., 48(1):96--129, 1998.
[13]
G. Karypis and V. Kumar. Multilevel k-way hypergraph partitioning. VLSI Design, 11(3):285--300, 2000.
[14]
S. Lafon and A. B. Lee. Diffusion maps and coarse-graining: a unified framework for dimensionality reduction, graph partitioning, and data set parameterization. IEEE Trans. Pattern Anal. Mach. Intell., 28(9):1393--1403, 2006.
[15]
R. B. Lehoucq, D. C. Sorensen, and C. Yang. ARPACK Users' Guide: Solution of Large-Scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods. SIAM Publications, 1998.
[16]
A. M. Martínez and A. C. Kak. PCA versus LDA. IEEE Trans. Pattern Anal. Mach. Intell., 23(2):228--233, 2001.
[17]
A. Y. Ng, M. Jordan, and Y. Weiss. On spectral clustering: Analysis and an algorithm. In Advances in Neural Information Processing Systems 14 (NIPS), 2002.
[18]
S. T. Roweis and L. K. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 290(5500):2323--2326, 2000.
[19]
S. Sakellaridi, H.-r. Fang, and Y. Saad. Graph-based multilevel dimensionality reduction with applications to eigenfaces and latent semantic indexing. In The 7th International Conference on Machine Learning and Applications (ICMLA), pages 194--200, Washington, DC, USA, 2008. IEEE Computer Society.
[20]
F. S. Samaria and A. C. Harter. Parameterisation of a stochastic model for human face identification. In The 2nd IEEE Workshop on Applications of Computer Vision, pages 138--142, 1994.
[21]
L. K. Saul and S. T. Roweis. Think globally, fit locally: Unsupervised learning of low dimensional manifolds. J. of Machine Learning Research, 4:119--155, 2003.
[22]
L. K. Saul, K. Q. Weinberger, J. H. Ham, F. Sha, and D. D. Lee. Spectral methods for dimensionality reduction. In Semisupervised Learning. MIT Press, Cambridge, MA, 2006.
[23]
F. Sha and L. K. Saul. Analysis and extension of spectral methods for nonlinear dimensionality reduction. In The 22nd international conference on Machine learning (ICML), pages 784--791, New York, NY, USA, 2005. ACM.
[24]
B. Shaw and T. Jebara. Minimum volume embedding. In The 11th Conference on Artificial Intelligence and Statistics (AISTATS), volume 2, pages 460--467, 2007.
[25]
G. W. Stewart and J.-g. Sun. Matrix Perturbation Theory. Academic Press, 1990.
[26]
A. Talwalkar, S. Kumar, and H. A. Rowley. Large-scale manifold learning. In IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), 2008.
[27]
J. B. Tenenbaum, V. de Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500):2319--2323, 2000.
[28]
J. Venna and S. Kaski. Neighborhood preservation in nonlinear production methods: An experimental study. In International Conference on Artificial Neural Networks (ICANN), pages 485--491, 2001.
[29]
J. Venna and S. Kaski. Local multidimensional scaling. Neural Networks, 19(6-7):889--899, 2006.
[30]
Q. Weinberger, B. D. Packer, and L. K. Saul. Nonlinear dimensionality reduction by semidefinite programming and kernel matrix factorization. In The 10th International Workshop on Artificial Intelligence and Statistics (AISTATS), pages 381--388, 2005.
[31]
K. Q. Weinerger and L. K. Saul. Unsupervised learning of image manifolds by semidefinite programming. International Journal on Computer Vision, 70(1):77--90, 2006.
[32]
S. X. Yu and J. Shi. Multiclass spectral clustering. In The 9th IEEE International Conference on Computer Vision (ICCV), pages 313--319, Washington, DC, USA, 2003. IEEE Computer Society.
[33]
Y. Zhao and G. Karypis. Empirical and theoretical comparisons of selected criterion functions for document clustering. Machine Learning, 55(3):311--331, 2004.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
CIKM '10: Proceedings of the 19th ACM international conference on Information and knowledge management
October 2010
2036 pages
ISBN:9781450300995
DOI:10.1145/1871437
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: 26 October 2010

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. manifold learning
  2. multilevel methods
  3. spectral clustering

Qualifiers

  • Research-article

Conference

CIKM '10

Acceptance Rates

Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

Upcoming Conference

CIKM '25

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)12
  • Downloads (Last 6 weeks)1
Reflects downloads up to 20 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2022)Graph coarsening: from scientific computing to machine learningSeMA Journal10.1007/s40324-021-00282-x79:1(187-223)Online publication date: 10-Jan-2022
  • (2021)A solution-driven multilevel approach for graph coloringApplied Soft Computing10.1016/j.asoc.2021.107174104:COnline publication date: 1-Jun-2021
  • (2019)Engineering fast multilevel support vector machinesMachine Learning10.1007/s10994-019-05800-7Online publication date: 9-May-2019
  • (2019)Sampling and multilevel coarsening algorithms for fast matrix approximationsNumerical Linear Algebra with Applications10.1002/nla.223426:3Online publication date: 6-Mar-2019
  • (2014)Hybrid Manifold EmbeddingIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2014.230576025:12(2295-2302)Online publication date: Dec-2014
  • (2012)Distributed spectral cluster managementProceedings of the 6th ACM International Conference on Distributed Event-Based Systems10.1145/2335484.2335508(213-224)Online publication date: 16-Jul-2012
  • (2011)Terrorist organization behavior prediction algorithm based on context subspaceProceedings of the 7th international conference on Advanced Data Mining and Applications - Volume Part II10.1007/978-3-642-25856-5_25(332-345)Online publication date: 17-Dec-2011

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media