A scalable approach to spectral clustering with SDD solvers

Nguyen Lu Dang Khoa, Sanjay Chawla

Research output: Contribution to journalArticlepeer-review

7 Scopus citations


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 expensive computational cost 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 near-linear time solver for symmetric diagonally dominant (SDD) linear systems 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
Pages (from-to)289-308
Number of pages20
JournalJournal of Intelligent Information Systems
Issue number2
StatePublished - Apr 2015
Externally publishedYes


  • Random projection
  • Resistance distance
  • SDD solver
  • Spectral clustering


Dive into the research topics of 'A scalable approach to spectral clustering with SDD solvers'. Together they form a unique fingerprint.

Cite this