A Tutorial on Spectral Clustering

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.

References in corpus (1)

• Empirical graph Laplacian approximation of Laplace--Beltrami operators: Large sample results

Cited by in corpus (34)

• Community detection in graphs
• Spectral Networks and Locally Connected Networks on Graphs
• Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
• Clustering multi-way data: a novel algebraic approach
• Capacity Releasing Diffusion for Speed and Locality
• Physics-informed cluster analysis and a priori efficiency criterion for the construction of local reduced-order bases
• On the Application of Network Slicing for 5G-V2X
• Multimodal diffusion geometry by joint diagonalization of Laplacians
• Localization on low-order eigenvectors of data matrices
• LICORS: Light Cone Reconstruction of States for Non-parametric Forecasting of Spatio-Temporal Systems
• Variational Community Partition with Novel Network Structure Centrality Prior
• Structural Temporal Graph Neural Networks for Anomaly Detection in Dynamic Graphs
• Social Network Fusion and Mining: A Survey
• Mapping Topographic Structure in White Matter Pathways with Level Set Trees
• A useful variant of the Davis--Kahan theorem for statisticians
• Graph Laplacians on Singular Manifolds: Toward understanding complex spaces: graph Laplacians on manifolds with singularities and boundaries
• Graph Laplacians and their convergence on random neighborhood graphs
• $p$-Norm Flow Diffusion for Local Graph Clustering
• Multiclass Diffuse Interface Models for Semi-Supervised Learning on Graphs
• Introduction to Clustering Algorithms and Applications
• Model-based clustering in very high dimensions via adaptive projections
• The Mathematics Behind Spectral Clustering And The Equivalence To PCA
• LATTE: Application Oriented Social Network Embedding
• Mutual Community Detection across Multiple Partially Aligned Social Networks
• Persistence Atlas for Critical Point Variability in Ensembles
• Measuring inter-cluster similarities with Alpha Shape TRIangulation in loCal Subspaces (ASTRICS) facilitates visualization and clustering of high-dimensional data
• Name Disambiguation from link data in a collaboration graph using temporal and topological features
• Faster Clustering via Non-Backtracking Random Walks
• Discovering Multiple Design Approaches in Programming Assignment Submissions
• ${\ell }_2$-norm Flow Diffusion in Near-Linear Time
• Algorithms and Hardness for Linear Algebra on Geometric Graphs
• Pseudoinverse Graph Convolutional Networks: Fast Filters Tailored for Large Eigengaps of Dense Graphs and Hypergraphs
• Zero-Shot Feature Selection via Transferring Supervised Knowledge
• Farthest sampling segmentation of triangulated surfaces