A Tutorial on Spectral Clustering

2007/11/01 by Ulrike von Luxburg · 13 citations
Computer Science · #cs.DS #cs.LG

paper · pdf

published as Statistics and Computing 17(4), 2007

arxiv created 2007/11/01 · arxiv updated 2009/12/01

Abstract

In recent years, spectral clustering has become one of the most popular modern clustering algorithms. It is simple to implement, can be solved efficiently by standard linear algebra software, and very often outperforms traditional clustering algorithms such as the k-means algorithm. On the first glance spectral clustering appears slightly mysterious, and it is not obvious to see why it works at all and what it really does. The goal of this tutorial is to give some intuition on those questions. We describe different graph Laplacians and their basic properties, present the most common spectral clustering algorithms, and derive those algorithms from scratch by several different approaches. Advantages and disadvantages of the different spectral clustering algorithms are discussed.

Cited by

• Threshold Optimization and Dynamic Adaptation of Distributed Optimal Power Flow in 5G Networks
• Advancing Local Clustering on Graphs via Compressive Sensing: Semi-supervised and Unsupervised Methods
• Semantic Level of Detail for Knowledge Graphs: Discovering Abstraction Boundaries via Spectral Heat Diffusion
• Geometry-aware Active Learning of Spatiotemporal Dynamic Systems
• Label-independent hyperparameter-free self-supervised single-view deep subspace clustering
• Hierarchical Sparse Circuit Extraction from Billion-Parameter Language Models through Scalable Attribution Graph Decomposition
• Improving Open-World Object Localization by Discovering Background
• Early Detection of Multidrug Resistance Using Multivariate Time Series Analysis and Interpretable Patient-Similarity Representations
• Collaborative Multi-Agent Reinforcement Learning for Automated Feature Transformation with Graph-Driven Path Optimization
• Cequel: Cost-Effective Querying of Large Language Models for Text Clustering
• How Local Separators Shape Community Structure in Large Networks
• A Method for Handling Negative Similarities in Explainable Graph Spectral Clustering of Text Documents -- Extended Version
• A Survey on Archetypal Analysis

Related

• A Tighter Analysis of Spectral Clustering, and Beyond
• Fast and Simple Spectral Clustering in Theory and Practice
• Partitioning Well-Clustered Graphs: Spectral Clustering Works!
• The Mathematics Behind Spectral Clustering And The Equivalence To PCA
• Approximating Spectral Clustering via Sampling: a Review