Large scale spectral clustering using resistance distance and spielman-teng solvers

Nguyen Lu Dang Khoa, Sanjay Chawla

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

19 Scopus citations

Abstract

The promise of spectral clustering is that it can help detect complex shapes and intrinsic manifold structure in large and high dimensional spaces. The price for this promise is the computational cost O(n 3) for computing the eigen-decomposition of the graph Laplacian matrix-so far a necessary subroutine for spectral clustering. In this paper we bypass the eigen-decomposition of the original Laplacian matrix by leveraging the recently introduced Spielman and Teng near-linear time solver for systems of linear equations and random projection. Experiments on several synthetic and real datasets show that the proposed approach has better clustering quality and is faster than the state-of-the-art approximate spectral clustering methods.

Original languageEnglish
Title of host publicationDiscovery Science - 15th International Conference, DS 2012, Proceedings
Pages7-21
Number of pages15
DOIs
StatePublished - 2012
Externally publishedYes
Event15th International Conference on Discovery Science, DS 2012 - Lyon, France
Duration: Oct 29 2012Oct 31 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7569 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference15th International Conference on Discovery Science, DS 2012
Country/TerritoryFrance
CityLyon
Period10/29/1210/31/12

Keywords

  • Spielman-Teng Solver
  • random projection
  • resistance distance
  • spectral clustering

Fingerprint

Dive into the research topics of 'Large scale spectral clustering using resistance distance and spielman-teng solvers'. Together they form a unique fingerprint.

Cite this