Aarhus University Seal

SCAR - Spectral Clustering Accelerated and Robustified

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperConference articleResearchpeer-review


  • Ellen Hohma Ellen.Hohma@Tum.De, Technical University of Munich
  • ,
  • Christian M.M. Frey, Kiel University
  • ,
  • Anna Beer
  • Thomas Seidl, Ludwig Maximilian University of Munich

Spectral clustering is one of the most advantageous clustering approaches. However, standard Spectral Clustering is sensitive to noisy input data and has a high runtime complexity. Tackling one of these problems often exacerbates the other. As real-world datasets are often large and compromised by noise, we need to improve both robustness and runtime at once. Thus, we propose Spectral Clustering-Accelerated and Robust (SCAR), an accelerated, robustified spectral clustering method. In an iterative approach, we achieve robustness by separating the data into two latent components: cleansed and noisy data. We accelerate the eigendecomposition – the most time-consuming step – based on the Nyström method. We compare SCAR to related recent state-of-the-art algorithms in extensive experiments. SCAR surpasses its competitors in terms of speed and clustering quality on highly noisy data.

Original languageEnglish
JournalProceedings of the VLDB Endowment
Pages (from-to)3031-3044
Number of pages14
Publication statusPublished - Jul 2022
Event48th International Conference on Very Large Data Bases, VLDB 2022 - Sydney, Australia
Duration: 5 Sept 20229 Sept 2022


Conference48th International Conference on Very Large Data Bases, VLDB 2022

    Research areas

  • clustering

See relations at Aarhus University Citationformats

ID: 284490116