Skip to main navigation Skip to search Skip to main content

An Improved and Generalised Analysis of Spectral Clustering

Research output: Chapter or section in a book/report/conference proceeding › Chapter in a published conference proceeding

5 Downloads (Pure)

Abstract

We revisit the theoretical performances of Spectral Clustering, a classical algorithm for graph partitioning that relies on the eigenvectors of a matrix representation of the graph. Informally, we show that Spectral Clustering works well as long as the smallest eigenvalues appear in groups well separated from the rest of the matrix representation's spectrum. This arises, for example, whenever there exists a hierarchy of clusters at different scales, a regime not captured by previous analyses. Our results are very general and can be applied beyond the traditional graph Laplacian. In particular, we study Hermitian representations of digraphs and show Spectral Clustering can recover partitions where edges between clusters are oriented mostly in the same direction. This has applications in, for example, the analysis of trophic levels in ecological networks. We demonstrate that our results accurately predict the performances of Spectral Clustering on synthetic and real-world data sets.
Original languageEnglish
Title of host publicationLearning on Graphs Conference 2025
Number of pages24
DOIs
Publication statusE-pub ahead of print - 28 Nov 2025
EventThe Fourth Learning on Graphs Conference - https://logconference.org/, Phoenix, USA United States
Duration: 10 Dec 2025 → …

Conference

ConferenceThe Fourth Learning on Graphs Conference
Country/TerritoryUSA United States
CityPhoenix
Period10/12/25 → …

Keywords

  • spectral clustering
  • graph clustering

Fingerprint

Dive into the research topics of 'An Improved and Generalised Analysis of Spectral Clustering'. Together they form a unique fingerprint.

Cite this