A tutorial on spectral clustering
By Ulrike von Luxburg. 2007
11,492 citations recorded by the source corpus.
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.
Subfields: Artificial Intelligence, Geometry and Topology, Statistical and Nonlinear Physics, Graph Learning
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Yoshua Bengio
- Mohit Bansal
- Dacheng Tao
- Sergey Levine
- Jianfeng Gao
- Quoc V. Le
- Percy Liang
- Trevor Darrell
In Geometry and Topology
- Bernhard Schölkopf
- Michael M. Bronstein
- Huan Liu
- Pierre Vandergheynst
- René Vidal
- Santo Fortunato
- Jure Leskovec
- David Lopez-Paz
In Statistical and Nonlinear Physics
- Jure Leskovec
- Charu C. Aggarwal
- Huan Liu
- Stephan Günnemann
- Michael M. Bronstein
- William L. Hamilton
- Pierre Vandergheynst
- Jiliang Tang
In Graph Learning
- Jure Leskovec
- Stephan Günnemann
- Michael M. Bronstein
- William L. Hamilton
- Aleksandar Bojchevski
- Xavier Bresson
- Pierre Vandergheynst
- Joan Bruna
Citations in the corpus
- Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering (2016, background): “The emerging field of GSP aims at bridging the gap between signal processing and spectral graph theory [6, 3, 21], a blend between graph theory and harmonic analysis.”
- Spectral Networks and Locally Connected Networks on Graphs (2013, methodology): “ combinatorial Laplacian L= D Wor graph Laplacian L= I D 1=2WD 1=2 are generalizations of the Laplacian on the grid; and frequency and smoothness relative to Ware interrelated through these operators [2, 25]. For simplicity, here we use the combinatorial Laplacian. If xis an m-dimensional vector, a ”
- Deep Convolutional Networks on Graph-Structured Data (2015, methodology): “In this work, we construct such neighborhoods at different scales using multi-resolution spectral clustering [20], and consider both average and max-pooling as in standard convolutional network architectures.”
- 3D Instance Segmentation of MVS Buildings (2021, neutral): “Based on the similarity matrix, one alternative option for mask clustering is spectral clustering [57].”
- Comprehensive Privacy Analysis of Deep Learning: Stand-alone and Federated Learning under Passive and Active White-box Inference Attacks (2018, methodology): “After the training, we use the Spectral clustering algo-rithm [ 14] to divide the input samples into two clusters.”
- Graying the black box: Understanding DQNs (2016, background): “In order to capture the game dynamics, DQN represents a state by a sequence of history frames and pads initial states with zero frames.”
- Bayesian Learning of Kernel Embeddings (2016, methodology): “Outside of kernel methods, the same basic conundrum arises in spectral clustering in the choice of the parameters for the similarity graph (Von Luxburg, 2007, Section 8.1) and it is implicitly an issue in any unsupervised statistical method based on distances or dissimilarities, like the distance…”
- Identifying Finite Mixtures of Nonparametric Product Distributions and Causal Inference of Confounders (2013, methodology): “Probabilistic mixture models or other clustering meth-ods can be used to identify the mixture components (clusters) (e.g., Von Luxburg (2007); B¨ohning & Seidel (2003); Rasmussen (2000); Iwata et al. (2013)).”
- Causal Interpretability for Machine Learning - Problems, Methods and Evaluation (2020, methodology): “In traditional machine learning, approaches such as PCA [44], ICA [42] and spectrum analysis [100] are proposed to discover disentangled components of data.”
- Geometric Deep Learning: Going beyond Euclidean data (2016, methodology): “of the Laplacian) carries information on the graph partition with minimal cut [73], and the popular PageRank algorithm approximates page ranks with the principal eigenvector of a modified Laplacian operator.”
- Unsupervised Deep Embedding for Clustering Analysis (2015, background): “Spectral clustering and its variants have gained popularity recently (Von Luxburg, 2007).”
- Comprehensive Privacy Analysis of Deep Learning: Passive and Active White-box Inference Attacks against Centralized and Federated Learning (2018, methodology): “After the training, we use the Spectral clustering algorithm [14] to divide the input samples into two clusters.”
- The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains (2012, methodology): “It has proved particularly useful for the construction of expander graphs [21], graph visualization [17, Section 16.7], spectral clustering [22], graph coloring [17, Section 16.9], and numerous other applications in chemistry, physics, and computer science (see, e.g., [23] for a recent review).”
- Community detection in graphs (2009, methodology): “…have proposed an algorithm, called Kcut, that applies recursively the method by White and Smyth, in a slightly modified form: after a first application to the full graph, in the next iteration the method is applied to all clusters of the first partition, treated as independent networks, and so on.”
- Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec (2017, background): “story of network embedding stems from Spectral Clustering [4, 43], a general data clustering technique, which selects eigenvalues/eigenvectors of a data affinity matrix to obtain a data representation that can be clustered or embedded in a low-dimensional space.”
- Learning Deep Representations for Graph Clustering (2014, methodology): “We used two versions of spectral clustering: unnormalized spectral clustering (Von Luxburg 2007), which aims to minimize ratio cut, and normalized spectral clustering (Shi and Malik 2000), which aims to minimize normalized cut.”