A Tutorial on Spectral Clustering

Introduction

Clustering is one of the most widely used techniques for exploratory data analysis, with applications ranging from statistics, computer science, biology to social sciences or psychology. In virtually every scientific field dealing with empirical data, people attempt to get a first impression on their data by trying to identify groups of “similar behavior” in their data. In this article we would like to introduce the reader to the family of spectral clustering algorithms. Compared to the “traditional algorithms” such as $k$-means or single linkage, spectral clustering has many fundamental advantages. Results obtained by spectral clustering often outperform the traditional approaches, spectral clustering is very simple to implement and can be solved efficiently by standard linear algebra methods.

This tutorial is set up as a self-contained introduction to spectral clustering. We derive spectral clustering from scratch and present different points of view to why spectral clustering works. Apart from basic linear algebra, no particular mathematical background is required by the reader. However, we do not attempt to give a concise review of the whole literature on spectral clustering, which is impossible due to the overwhelming amount of literature on this subject. The first two sections are devoted to a step-by-step introduction to the mathematical objects used by spectral clustering: similarity graphs in Section 2, and graph Laplacians in Section 3. The spectral clustering algorithms themselves will be presented in Section 4. The next three sections are then devoted to explaining why those algorithms work. Each section corresponds to one explanation: Section 5 describes a graph partitioning approach, Section 6 a random walk perspective, and Section 7 a perturbation theory approach. In Section 8 we will study some practical issues related to spectral clustering, and discuss various extensions and literature related to spectral clustering in Section 9.

Similarity graphs

Given a set of data points $x_{1},\ldots x_{n}$ and some notion of similarity $s_{ij}\geq 0$ between all pairs of data points $x_{i}$ and $x_{j}$, the intuitive goal of clustering is to divide the data points into several groups such that points in the same group are similar and points in different groups are dissimilar to each other. If we do not have more information than similarities between data points, a nice way of representing the data is in form of the similarity graph $G=(V,E)$. Each vertex $v_{i}$ in this graph represents a data point $x_{i}$. Two vertices are connected if the similarity $s_{ij}$ between the corresponding data points $x_{i}$ and $x_{j}$ is positive or larger than a certain threshold, and the edge is weighted by $s_{ij}$. The problem of clustering can now be reformulated using the similarity graph: we want to find a partition of the graph such that the edges between different groups have very low weights (which means that points in different clusters are dissimilar from each other) and the edges within a group have high weights (which means that points within the same cluster are similar to each other). To be able to formalize this intuition we first want to introduce some basic graph notation and briefly discuss the kind of graphs we are going to study.

Let $G=(V,E)$ be an undirected graph with vertex set $V=\{v_{1},\ldots,v_{n}\}$. In the following we assume that the graph $G$ is weighted, that is each edge between two vertices $v_{i}$ and $v_{j}$ carries a non-negative weight $w_{ij}\geq 0$. The weighted adjacency matrix of the graph is the matrix $W=(w_{ij})_{i,j=1,\ldots,n}$. If $w_{ij}=0$ this means that the vertices $v_{i}$ and $v_{j}$ are not connected by an edge. As $G$ is undirected we require $w_{ij}=w_{ji}$. The degree of a vertex $v_{i}\in V$ is defined as

We consider two different ways of measuring the “size” of a subset $A\subset V$:

Intuitively, $|A|$ measures the size of $A$ by its number of vertices, while $\vol(A)$ measures the size of $A$ by summing over the weights of all edges attached to vertices in $A$. A subset $A\subset V$ of a graph is connected if any two vertices in $A$ can be joined by a path such that all intermediate points also lie in $A$. A subset $A$ is called a connected component if it is connected and if there are no connections between vertices in $A$ and $\overline{A}$. The nonempty sets $A_{1},\ldots,A_{k}$ form a partition of the graph if $A_{i}\cap A_{j}=\emptyset$ and $A_{1}\;\cup\;\ldots\;\cup\;A_{k}=V$.

2 Different similarity graphs

There are several popular constructions to transform a given set $x_{1},\ldots,x_{n}$ of data points with pairwise similarities $s_{ij}$ or pairwise distances $d_{ij}$ into a graph. When constructing similarity graphs the goal is to model the local neighborhood relationships between the data points.

The $\varepsilon$-neighborhood graph: Here we connect all points whose pairwise distances are smaller than $\varepsilon$. As the distances between all connected points are roughly of the same scale (at most $\varepsilon$), weighting the edges would not incorporate more information about the data to the graph. Hence, the $\varepsilon$-neighborhood graph is usually considered as an unweighted graph.

$k$-nearest neighbor graphs: Here the goal is to connect vertex $v_{i}$ with vertex $v_{j}$ if $v_{j}$ is among the $k$-nearest neighbors of $v_{i}$. However, this definition leads to a directed graph, as the neighborhood relationship is not symmetric. There are two ways of making this graph undirected. The first way is to simply ignore the directions of the edges, that is we connect $v_{i}$ and $v_{j}$ with an undirected edge if $v_{i}$ is among the $k$-nearest neighbors of $v_{j}$ or if $v_{j}$ is among the $k$-nearest neighbors of $v_{i}$. The resulting graph is what is usually called the $k$-nearest neighbor graph. The second choice is to connect vertices $v_{i}$ and $v_{j}$ if both $v_{i}$ is among the $k$-nearest neighbors of $v_{j}$ and $v_{j}$ is among the $k$-nearest neighbors of $v_{i}$. The resulting graph is called the mutual $k$-nearest neighbor graph. In both cases, after connecting the appropriate vertices we weight the edges by the similarity of their endpoints.

The fully connected graph: Here we simply connect all points with positive similarity with each other, and we weight all edges by $s_{ij}$. As the graph should represent the local neighborhood relationships, this construction is only useful if the similarity function itself models local neighborhoods. An example for such a similarity function is the Gaussian similarity function $s(x_{i},x_{j})=\exp(-{\|x_{i}-x_{j}\|^{2}}/({2\sigma^{2}}))$, where the parameter $\sigma$ controls the width of the neighborhoods. This parameter plays a similar role as the parameter $\varepsilon$ in case of the $\varepsilon$-neighborhood graph.

All graphs mentioned above are regularly used in spectral clustering. To our knowledge, theoretical results on the question how the choice of the similarity graph influences the spectral clustering result do not exist. For a discussion of the behavior of the different graphs we refer to Section 8.

Graph Laplacians and their basic properties

The main tools for spectral clustering are graph Laplacian matrices. There exists a whole field dedicated to the study of those matrices, called spectral graph theory (e.g., see Chung (1997)). In this section we want to define different graph Laplacians and point out their most important properties. We will carefully distinguish between different variants of graph Laplacians. Note that in the literature there is no unique convention which matrix exactly is called “graph Laplacian”. Usually, every author just calls “his” matrix the graph Laplacian. Hence, a lot of care is needed when reading literature on graph Laplacians.

The unnormalized graph Laplacian matrix is defined as

An overview over many of its properties can be found in Mohar (1991); Mohar (1997). The following proposition summarizes the most important facts needed for spectral clustering.

The matrix $L$ satisfies the following properties:

$L$ is symmetric and positive semi-definite.

$L$ has $n$ non-negative, real-valued eigenvalues $0=\lambda_{1}\leq\lambda_{2}\leq\ldots\leq\lambda_{n}$.

Proof. Part (1): By the definition of $d_{i}$,

Note that the unnormalized graph Laplacian does not depend on the diagonal elements of the adjacency matrix $W$. Each adjacency matrix which coincides with $W$ on all off-diagonal positions leads to the same unnormalized graph Laplacian $L$. In particular, self-edges in a graph do not change the corresponding graph Laplacian.

The unnormalized graph Laplacian and its eigenvalues and eigenvectors can be used to describe many properties of graphs, see Mohar (1991); Mohar (1997). One example which will be important for spectral clustering is the following:

Proof. We start with the case $k=1$, that is the graph is connected. Assume that $f$ is an eigenvector with eigenvalue $0$. Then we know that

Now consider the case of $k$ connected components. Without loss of generality we assume that the vertices are ordered according to the connected components they belong to. In this case, the adjacency matrix $W$ has a block diagonal form, and the same is true for the matrix $L$:

Note that each of the blocks $L_{i}$ is a proper graph Laplacian on its own, namely the Laplacian corresponding to the subgraph of the $i$-th connected component. As it is the case for all block diagonal matrices, we know that the spectrum of $L$ is given by the union of the spectra of $L_{i}$, and the corresponding eigenvectors of $L$ are the eigenvectors of $L_{i}$, filled with 0 at the positions of the other blocks. As each $L_{i}$ is a graph Laplacian of a connected graph, we know that every $L_{i}$ has eigenvalue 0 with multiplicity 1, and the corresponding eigenvector is the constant one vector on the $i$-th connected component. Thus, the matrix $L$ has as many eigenvalues $0$ as there are connected components, and the corresponding eigenvectors are the indicator vectors of the connected components. $\Box$

2 The normalized graph Laplacians

There are two matrices which are called normalized graph Laplacians in the literature. Both matrices are closely related to each other and are defined as

We denote the first matrix by $L_{\text{sym}}$ as it is a symmetric matrix, and the second one by $L_{\text{rw}}$ as it is closely related to a random walk. In the following we summarize several properties of $L_{\text{sym}}$ and $L_{\text{rw}}$. The standard reference for normalized graph Laplacians is Chung (1997).

The normalized Laplacians satisfy the following properties:

$\lambda$ is an eigenvalue of $L_{\text{rw}}$ with eigenvector $u$ if and only if $\lambda$ is an eigenvalue of $L_{\text{sym}}$ with eigenvector $w=D^{1/2}u$.

$\lambda$ is an eigenvalue of $L_{\text{rw}}$ with eigenvector $u$ if and only if $\lambda$ and $u$ solve the generalized eigenproblem $Lu=\lambda Du$.

$L_{\text{sym}}$ and $L_{\text{rw}}$ are positive semi-definite and have $n$ non-negative real-valued eigenvalues $0=\lambda_{1}\leq\ldots\leq\lambda_{n}$.

As it is the case for the unnormalized graph Laplacian, the multiplicity of the eigenvalue 0 of the normalized graph Laplacian is related to the number of connected components:

Proof. The proof is analogous to the one of Proposition 2, using Proposition 3. $\Box$

Spectral Clustering Algorithms

Now we would like to state the most common spectral clustering algorithms. For references and the history of spectral clustering we refer to Section 9. We assume that our data consists of $n$ “points” $x_{1},\ldots,x_{n}$ which can be arbitrary objects. We measure their pairwise similarities $s_{ij}=s(x_{i},x_{j})$ by some similarity function which is symmetric and non-negative, and we denote the corresponding similarity matrix by $S=(s_{ij})_{i,j=1\ldots n}$.

There are two different versions of normalized spectral clustering, depending which of the normalized graph Laplacians is used. We name both algorithms after two popular papers, for more references and history please see Section 9.

Note that this algorithm uses the generalized eigenvectors of $L$, which according to Proposition 3 correspond to the eigenvectors of the matrix $L_{\text{rw}}$. So in fact, the algorithm works with eigenvectors of the normalized Laplacian $L_{\text{rw}}$, and hence is called normalized spectral clustering. The next algorithm also uses a normalized Laplacian, but this time the matrix $L_{\text{sym}}$ instead of $L_{\text{rw}}$. As we will see, this algorithm needs to introduce an additional row normalization step which is not needed in the other algorithms. The reasons will become clear in Section 7.

Graph cut point of view

The intuition of clustering is to separate points in different groups according to their similarities. For data given in form of a similarity graph, this problem can be restated as follows: we want to find a partition of the graph such that the edges between different groups have a very low weight (which means that points in different clusters are dissimilar from each other) and the edges within a group have high weight (which means that points within the same cluster are similar to each other). In this section we will see how spectral clustering can be derived as an approximation to such graph partitioning problems.

Given a similarity graph with adjacency matrix $W$, the simplest and most direct way to construct a partition of the graph is to solve the mincut problem. To define it, please recall the notation $W(A,B):=\sum_{i\in A,j\in B}w_{ij}$ and $\overline{A}$ for the complement of $A$. For a given number $k$ of subsets, the mincut approach simply consists in choosing a partition $A_{1},\ldots,A_{k}$ which minimizes

Here we introduce the factor $1/2$ for notational consistency, otherwise we would count each edge twice in the cut. In particular for $k=2$, mincut is a relatively easy problem and can be solved efficiently, see Stoer & Wagner (1997) and the discussion therein. However, in practice it often does not lead to satisfactory partitions. The problem is that in many cases, the solution of mincut simply separates one individual vertex from the rest of the graph. Of course this is not what we want to achieve in clustering, as clusters should be reasonably large groups of points. One way to circumvent this problem is to explicitly request that the sets $A_{1},\ldots,A_{k}$ are “reasonably large”. The two most common objective functions to encode this are $\Ratiocut$ (Hagen & Kahng (1992)) and the normalized cut $\Ncut$ (Shi & Malik (2000)). In $\Ratiocut$, the size of a subset $A$ of a graph is measured by its number of vertices $|A|$, while in $\Ncut$ the size is measured by the weights of its edges $\vol(A)$. The definitions are:

Note that both objective functions take a small value if the clusters $A_{i}$ are not too small. In particular, the minimum of the function $\sum_{i=1}^{k}(1/|A_{i}|)$ is achieved if all $|A_{i}|$ coincide, and the minimum of $\sum_{i=1}^{k}(1/\vol(A_{i}))$ is achieved if all $\vol(A_{i})$ coincide. So what both objective functions try to achieve is that the clusters are “balanced”, as measured by the number of vertices or edge weights, respectively. Unfortunately, introducing balancing conditions makes the previously simple to solve mincut problem become NP hard, see Wagner & Wagner (1993) for a discussion. Spectral clustering is a way to solve relaxed versions of those problems. We will see that relaxing $\Ncut$ leads to normalized spectral clustering, while relaxing $\Ratiocut$ leads to unnormalized spectral clustering (see also the tutorial slides by Ding (2004)).

Let us start with the case of $\Ratiocut$ and $k=2$, because the relaxation is easiest to understand in this setting. Our goal is to solve the optimization problem

Now the $\Ratiocut$ objective function can be conveniently rewritten using the unnormalized graph Laplacian. This is due to the following calculation:

Altogether we can see that the problem of minimizing (1) can be equivalently rewritten as

This is exactly the unnormalized spectral clustering algorithm for the case of $k=2$.

2 Approximating RatioCut\boldsymbol{\Ratiocut} for arbitrary 𝒌\boldsymbol{k}

The relaxation of the $\Ratiocut$ minimization problem in the case of a general value $k$ follows a similar principle as the one above. Given a partition of $V$ into $k$ sets $A_{1},\ldots,A_{k}$, we define $k$ indicator vectors $h_{j}=(h_{1,j},\ldots,h_{n,j})^{\prime}$ by

where $\Tr$ denotes the trace of a matrix. So the problem of minimizing $\Ratiocut(A_{1},\ldots,A_{k})$ can be rewritten as

Similar to above we now relax the problem by allowing the entries of the matrix $H$ to take arbitrary real values. Then the relaxed problem becomes:

This is the standard form of a trace minimization problem, and again a version of the Rayleigh-Ritz theorem (e.g., see Section 5.2.2.(6) of Lütkepohl (1997)) tells us that the solution is given by choosing $H$ as the matrix which contains the first $k$ eigenvectors of $L$ as columns. We can see that the matrix $H$ is in fact the matrix $U$ used in the unnormalized spectral clustering algorithm as described in Section 4. Again we need to re-convert the real valued solution matrix to a discrete partition. As above, the standard way is to use the $k$-means algorithms on the rows of $U$. This leads to the general unnormalized spectral clustering algorithm as presented in Section 4.

3 Approximating Ncut\boldsymbol{\Ncut}

Techniques very similar to the ones used for $\Ratiocut$ can be used to derive normalized spectral clustering as relaxation of minimizing $\Ncut$. In the case $k=2$ we define the cluster indicator vector $f$ by

Again we relax the problem by allowing $f$ to take arbitrary real values:

Now we substitute $g:=D^{1/2}f$. After substitution, the problem is

For the case of finding $k>2$ clusters, we define the indicator vectors $h_{j}=(h_{1,j},\ldots,h_{n,j})^{\prime}$ by

Then we set the matrix $H$ as the matrix containing those $k$ indicator vectors as columns. Observe that $H^{\prime}H=I$, $h_{i}^{\prime}Dh_{i}=1$, and $h_{i}^{\prime}Lh_{i}=\Cut(A_{i},\overline{A}_{i})/\vol(A_{i})$. So we can write the problem of minimizing $\Ncut$ as

Relaxing the discreteness condition and substituting $T=D^{1/2}H$ we obtain the relaxed problem

Again this is the standard trace minimization problem which is solved by the matrix $T$ which contains the first $k$ eigenvectors of $L_{\text{sym}}$ as columns. Re-substituting $H=D^{-1/2}T$ and using Proposition 3 we see that the solution $H$ consists of the first $k$ eigenvectors of the matrix $L_{\text{rw}}$, or the first $k$ generalized eigenvectors of $Lu=\lambda Du$. This yields the normalized spectral clustering algorithm according to Shi & Malik (2000).

4 Comments on the relaxation approach

There are several comments we should make about this derivation of spectral clustering. Most importantly, there is no guarantee whatsoever on the quality of the solution of the relaxed problem compared to the exact solution. That is, if $A_{1},\ldots,A_{k}$ is the exact solution of minimizing $\Ratiocut$, and $B_{1},\ldots,B_{k}$ is the solution constructed by unnormalized spectral clustering, then $\Ratiocut(B_{1},\ldots,B_{k})-\Ratiocut(A_{1},\ldots,A_{k})$ can be arbitrary large. Several examples for this can be found in Guattery & Miller (1998). For instance, the authors consider a very simple class of graphs called “cockroach graphs”. Those graphs essentially look like a ladder, with a few rimes removed, see Figure 2.

Obviously, the ideal $\Ratiocut$ for $k=2$ just cuts the ladder by a vertical cut such that $A=\{v_{1},\ldots,v_{k},v_{2k+1},\ldots,v_{3k}\}$ and $\overline{A}=\{v_{k+1},\ldots,v_{2k},v_{3k+1},\ldots,v_{4k}\}$. This cut is perfectly balanced with $|A|=|\overline{A}|=2k$ and $\Cut(A,\overline{A})=2$. However, by studying the properties of the second eigenvector of the unnormalized graph Laplacian of cockroach graphs the authors prove that unnormalized spectral clustering always cuts horizontally through the ladder, constructing the sets $B=\{v_{1},\ldots,v_{2k}\}$ and $\overline{B}=\{v_{2k+1},\ldots,v_{4k}\}$. This also results in a balanced cut, but now we cut $k$ edges instead of just $2$. So $\Ratiocut(A,\overline{A})=2/k$, while $\Ratiocut(B,\overline{B})=1$. This means that compared to the optimal cut, the $\Ratiocut$ value obtained by spectral clustering is $k/2$ times worse, that is a factor in the order of $n$. Several other papers investigate the quality of the clustering constructed by spectral clustering, for example Spielman & Teng (1996) (for unnormalized spectral clustering) and Kannan et al. (2004) (for normalized spectral clustering). In general it is known that efficient algorithms to approximate balanced graph cuts up to a constant factor do not exist. To the contrary, this approximation problem can be NP hard itself Bui & Jones (1992).

Of course, the relaxation we discussed above is not unique. For example, a completely different relaxation which leads to a semi-definite program is derived in Bie & Cristianini (2006), and there might be many other useful relaxations. The reason why the spectral relaxation is so appealing is not that it leads to particularly good solutions. Its popularity is mainly due to the fact that it results in a standard linear algebra problem which is simple to solve.

Random walks point of view

Another line of argument to explain spectral clustering is based on random walks on the similarity graph. A random walk on a graph is a stochastic process which randomly jumps from vertex to vertex. We will see below that spectral clustering can be interpreted as trying to find a partition of the graph such that the random walk stays long within the same cluster and seldom jumps between clusters. Intuitively this makes sense, in particular together with the graph cut explanation of the last section: a balanced partition with a low cut will also have the property that the random walk does not have many opportunities to jump between clusters. For background reading on random walks in general we refer to Norris (1997) and Brémaud (1999), and for random walks on graphs we recommend Aldous & Fill (in preparation) and Lovász (1993). Formally, the transition probability of jumping in one step from vertex $v_{i}$ to vertex $v_{j}$ is proportional to the edge weight $w_{ij}$ and is given by $p_{ij}:=w_{ij}/d_{i}$. The transition matrix $P=(p_{ij})_{i,j=1,\ldots,n}$ of the random walk is thus defined by

If the graph is connected and non-bipartite, then the random walk always possesses a unique stationary distribution $\pi=(\pi_{1},\ldots,\pi_{n})^{\prime}$, where $\pi_{i}=d_{i}/\vol(V)$. Obviously there is a tight relationship between $L_{\text{rw}}$ and $P$, as $L_{\text{rw}}=I-P$. As a consequence, $\lambda$ is an eigenvalue of $L_{\text{rw}}$ with eigenvector $u$ if and only if $1-\lambda$ is an eigenvalue of $P$ with eigenvector $u$. It is well known that many properties of a graph can be expressed in terms of the corresponding random walk transition matrix $P$, see Lovász (1993) for an overview. From this point of view it does not come as a surprise that the largest eigenvectors of $P$ and the smallest eigenvectors of $L_{\text{rw}}$ can be used to describe cluster properties of the graph.

A formal equivalence between $\Ncut$ and transition probabilities of the random walk has been observed in Meila & Shi (2001).

Now the proposition follows directly with the definition of $\Ncut$. $\Box$

This proposition leads to a nice interpretation of $\Ncut$, and hence of normalized spectral clustering. It tells us that when minimizing $\Ncut$, we actually look for a cut through the graph such that a random walk seldom transitions from $A$ to $\overline{A}$ and vice versa.

The commute distance

A second connection between random walks and graph Laplacians can be made via the commute distance on the graph. The commute distance (also called resistance distance) $c_{ij}$ between two vertices $v_{i}$ and $v_{j}$ is the expected time it takes the random walk to travel from vertex $v_{i}$ to vertex $v_{j}$ and back Lovász (1993); Aldous & Fill (in preparation). The commute distance has several nice properties which make it particularly appealing for machine learning. As opposed to the shortest path distance on a graph, the commute distance between two vertices decreases if there are many different short ways to get from vertex $v_{i}$ to vertex $v_{j}$. So instead of just looking for the one shortest path, the commute distance looks at the set of short paths. Points which are connected by a short path in the graph and lie in the same high-density region of the graph are considered closer to each other than points which are connected by a short path but lie in different high-density regions of the graph. In this sense, the commute distance seems particularly well-suited to be used for clustering purposes.

Remarkably, the commute distance on a graph can be computed with the help of the generalized inverse (also called pseudo-inverse or Moore-Penrose inverse) $L^{\dagger}$ of the graph Laplacian $L$. In the following we denote $e_{i}=(0,\ldots 0,1,0,\ldots,0)^{\prime}$ as the $i$-th unit vector. To define the generalized inverse of $L$, recall that by Proposition 1 the matrix $L$ can be decomposed as $L=U\Lambda U^{\prime}$ where $U$ is the matrix containing all eigenvectors as columns and $\Lambda$ the diagonal matrix with the eigenvalues $\lambda_{1},\ldots,\lambda_{n}$ on the diagonal. As at least one of the eigenvalues is 0, the matrix $L$ is not invertible. Instead, we define its generalized inverse as $L^{\dagger}:=U\Lambda^{\dagger}U^{\prime}$ where the matrix $\Lambda^{\dagger}$ is the diagonal matrix with diagonal entries $1/\lambda_{i}$ if $\lambda_{i}\neq 0$ and $0$ if $\lambda_{i}=0$. The entries of $L^{\dagger}$ can be computed as $l_{ij}^{\dagger}=\sum_{k=2}^{n}\frac{1}{\lambda_{k}}u_{ik}u_{jk}$. The matrix $L^{\dagger}$ is positive semi-definite and symmetric. For further properties of $L^{\dagger}$ see Gutman & Xiao (2004).

Let $G=(V,E)$ a connected, undirected graph. Denote by $c_{ij}$ the commute distance between vertex $v_{i}$ and vertex $v_{j}$, and by $L^{\dagger}=(l_{ij}^{\dagger})_{i,j=1,\ldots,n}$ the generalized inverse of $L$. Then we have:

This result has been published by Klein & Randic (1993), where it has been proved by methods of electrical network theory. For a proof using first step analysis for random walks see Fouss et al. (2007). There also exist other ways to express the commute distance with the help of graph Laplacians. For example a method in terms of eigenvectors of the normalized Laplacian $L_{\text{sym}}$ can be found as Corollary 3.2 in Lovász (1993), and a method computing the commute distance with the help of determinants of certain sub-matrices of $L$ can be found in Bapat et al. (2003).

The embedding used in unnormalized spectral clustering is related to the commute time embedding, but not identical. In spectral clustering, we map the vertices of the graph on the rows $y_{i}$ of the matrix $U$, while the commute time embedding maps the vertices on the rows $z_{i}$ of the matrix $(\Lambda^{\dagger})^{1/2}U$. That is, compared to the entries of $y_{i}$, the entries of $z_{i}$ are additionally scaled by the inverse eigenvalues of $L$. Moreover, in spectral clustering we only take the first $k$ columns of the matrix, while the commute time embedding takes all columns. Several authors now try to justify why $y_{i}$ and $z_{i}$ are not so different after all and state a bit hand-waiving that the fact that spectral clustering constructs clusters based on the Euclidean distances between the $y_{i}$ can be interpreted as building clusters of the vertices in the graph based on the commute distance. However, note that both approaches can differ considerably. For example, in the optimal case where the graph consists of $k$ disconnected components, the first $k$ eigenvalues of $L$ are 0 according to Proposition 2, and the first $k$ columns of $U$ consist of the cluster indicator vectors. However, the first $k$ columns of the matrix $(\Lambda^{\dagger})^{1/2}U$ consist of zeros only, as the first $k$ diagonal elements of $\Lambda^{\dagger}$ are $0$. In this case, the information contained in the first $k$ columns of $U$ is completely ignored in the matrix $(\Lambda^{\dagger})^{1/2}U$, and all the non-zero elements of the matrix $(\Lambda^{\dagger})^{1/2}U$ which can be found in columns $k+1$ to $n$ are not taken into account in spectral clustering, which discards all those columns. On the other hand, those problems do not occur if the underlying graph is connected. In this case, the only eigenvector with eigenvalue $0$ is the constant one vector, which can be ignored in both cases. The eigenvectors corresponding to small eigenvalues $\lambda_{i}$ of $L$ are then stressed in the matrix $(\Lambda^{\dagger})^{1/2}U$ as they are multiplied by $\lambda_{i}^{\dagger}=1/\lambda_{i}$. In such a situation, it might be true that the commute time embedding and the spectral embedding do similar things.

All in all, it seems that the commute time distance can be a helpful intuition, but without making further assumptions there is only a rather loose relation between spectral clustering and the commute distance. It might be possible that those relations can be tightened, for example if the similarity function is strictly positive definite. However, we have not yet seen a precise mathematical statement about this.

Perturbation theory point of view

2 Comments about the perturbation approach

A bit of caution is needed when using perturbation theory arguments to justify clustering algorithms based on eigenvectors of matrices. In general, any block diagonal symmetric matrix has the property that there exists a basis of eigenvectors which are zero outside the individual blocks and real-valued within the blocks. For example, based on this argument several authors use the eigenvectors of the similarity matrix $S$ or adjacency matrix $W$ to discover clusters. However, being block diagonal in the ideal case of completely separated clusters can be considered as a necessary condition for a successful use of eigenvectors, but not a sufficient one. At least two more properties should be satisfied:

First, we need to make sure that the order of the eigenvalues and eigenvectors is meaningful. In case of the Laplacians this is always true, as we know that any connected component possesses exactly one eigenvector which has eigenvalue 0. Hence, if the graph has $k$ connected components and we take the first $k$ eigenvectors of the Laplacian, then we know that we have exactly one eigenvector per component. However, this might not be the case for other matrices such as $S$ or $W$. For example, it could be the case that the two largest eigenvalues of a block diagonal similarity matrix $S$ come from the same block. In such a situation, if we take the first $k$ eigenvectors of $S$, some blocks will be represented several times, while there are other blocks which we will miss completely (unless we take certain precautions). This is the reason why using the eigenvectors of $S$ or $W$ for clustering should be discouraged.

To summarize, the conclusion is that both unnormalized spectral clustering and normalized spectral clustering with $L_{\text{rw}}$ are well justified by the perturbation theory approach. Normalized spectral clustering with $L_{\text{sym}}$ can also be justified by perturbation theory, but it should be treated with more care if the graph contains vertices with very low degrees.

Practical details

In this section we will briefly discuss some of the issues which come up when actually implementing spectral clustering. There are several choices to be made and parameters to be set. However, the discussion in this section is mainly meant to raise awareness about the general problems which an occur. For thorough studies on the behavior of spectral clustering for various real world tasks we refer to the literature.

Constructing the similarity graph for spectral clustering is not a trivial task, and little is known on theoretical implications of the various constructions.

Which type of similarity graph

In the $\varepsilon$-neighborhood graph, we can see that it is difficult to choose a useful parameter $\varepsilon$. With $\varepsilon=0.3$ as in the figure, the points on the middle moon are already very tightly connected, while the points in the Gaussian are barely connected. This problem always occurs if we have data “on different scales”, that is the distances between data points are different in different regions of the space.

The $k$-nearest neighbor graph, on the other hand, can connect points “on different scales”. We can see that points in the low-density Gaussian are connected with points in the high-density moon. This is a general property of $k$-nearest neighbor graphs which can be very useful. We can also see that the $k$-nearest neighbor graph can break into several disconnected components if there are high density regions which are reasonably far away from each other. This is the case for the two moons in this example.

The mutual $k$-nearest neighbor graph has the property that it tends to connect points within regions of constant density, but does not connect regions of different densities with each other. So the mutual $k$-nearest neighbor graph can be considered as being “in between” the $\varepsilon$-neighborhood graph and the $k$-nearest neighbor graph. It is able to act on different scales, but does not mix those scales with each other. Hence, the mutual $k$-nearest neighbor graph seems particularly well-suited if we want to detect clusters of different densities.

The fully connected graph is very often used in connection with the Gaussian similarity function $s(x_{i},x_{j})=\exp(-\|x_{i}-x_{j}\|^{2}/(2\sigma^{2}))$. Here the parameter $\sigma$ plays a similar role as the parameter $\varepsilon$ in the $\varepsilon$-neighborhood graph. Points in local neighborhoods are connected with relatively high weights, while edges between far away points have positive, but negligible weights. However, the resulting similarity matrix is not a sparse matrix.

As a general recommendation we suggest to work with the $k$-nearest neighbor graph as the first choice. It is simple to work with, results in a sparse adjacency matrix $W$, and in our experience is less vulnerable to unsuitable choices of parameters than the other graphs.

The parameters of the similarity graph

Now let us give some rules of thumb. When working with the $k$-nearest neighbor graph, then the connectivity parameter should be chosen such that the resulting graph is connected, or at least has significantly fewer connected components than clusters we want to detect. For small or medium-sized graphs this can be tried out ”by foot”. For very large graphs, a first approximation could be to choose $k$ in the order of $\log(n)$, as suggested by the asymptotic connectivity results.

For the mutual $k$-nearest neighbor graph, we have to admit that we are a bit lost for rules of thumb. The advantage of the mutual $k$-nearest neighbor graph compared to the standard $k$-nearest neighbor graph is that it tends not to connect areas of different density. While this can be good if there are clear clusters induced by separate high-density areas, this can hurt in less obvious situations as disconnected parts in the graph will always be chosen to be clusters by spectral clustering. Very generally, one can observe that the mutual $k$-nearest neighbor graph has much fewer edges than the standard $k$-nearest neighbor graph for the same parameter $k$. This suggests to choose $k$ significantly larger for the mutual $k$-nearest neighbor graph than one would do for the standard $k$-nearest neighbor graph. However, to take advantage of the property that the mutual $k$-nearest neighbor graph does not connect regions of different density, it would be necessary to allow for several “meaningful” disconnected parts of the graph. Unfortunately, we do not know of any general heuristic to choose the parameter $k$ such that this can be achieved.

For the $\varepsilon$-neighborhood graph, we suggest to choose $\varepsilon$ such that the resulting graph is safely connected. To determine the smallest value of $\varepsilon$ where the graph is connected is very simple: one has to choose $\varepsilon$ as the length of the longest edge in a minimal spanning tree of the fully connected graph on the data points. The latter can be determined easily by any minimal spanning tree algorithm. However, note that when the data contains outliers this heuristic will choose $\varepsilon$ so large that even the outliers are connected to the rest of the data. A similar effect happens when the data contains several tight clusters which are very far apart from each other. In both cases, $\varepsilon$ will be chosen too large to reflect the scale of the most important part of the data.

Finally, if one uses a fully connected graph together with a similarity function which can be scaled itself, for example the Gaussian similarity function, then the scale of the similarity function should be chosen such that the resulting graph has similar properties as a corresponding $k$-nearest neighbor or $\varepsilon$-neighborhood graph would have. One needs to make sure that for most data points the set of neighbors with a similarity significantly larger than 0 is “not too small and not too large”. In particular, for the Gaussian similarity function several rules of thumb are frequently used. For example, one can choose $\sigma$ in the order of the mean distance of a point to its $k$-th nearest neighbor, where $k$ is chosen similarly as above (e.g., $k\sim\log(n)+1$ ). Another way is to determine $\varepsilon$ by the minimal spanning tree heuristic described above, and then choose $\sigma=\varepsilon$. But note that all those rules of thumb are very ad-hoc, and depending on the given data at hand and its distribution of inter-point distances they might not work at all.

In general, experience shows that spectral clustering can be quite sensitive to changes in the similarity graph and to the choice of its parameters. Unfortunately, to our knowledge there has been no systematic study which investigates the effects of the similarity graph and its parameters on clustering and comes up with well-justified rules of thumb. None of the recommendations above is based on a firm theoretic ground. Finding rules which have a theoretical justification should be considered an interesting and important topic for future research.

2 Computing the eigenvectors

To implement spectral clustering in practice one has to compute the first $k$ eigenvectors of a potentially large graph Laplace matrix. Luckily, if we use the $k$-nearest neighbor graph or the $\varepsilon$-neighborhood graph, then all those matrices are sparse. Efficient methods exist to compute the first eigenvectors of sparse matrices, the most popular ones being the power method or Krylov subspace methods such as the Lanczos method Golub & Van Loan (1996). The speed of convergence of those algorithms depends on the size of the eigengap (also called spectral gap) $\gamma_{k}=|\lambda_{k}-\lambda_{k+1}|$. The larger this eigengap is, the faster the algorithms computing the first $k$ eigenvectors converge.

3 The number of clusters

Choosing the number $k$ of clusters is a general problem for all clustering algorithms, and a variety of more or less successful methods have been devised for this problem. In model-based clustering settings there exist well-justified criteria to choose the number of clusters from the data. Those criteria are usually based on the log-likelihood of the data, which can then be treated in a frequentist or Bayesian way, for examples see Fraley & Raftery (2002). In settings where no or few assumptions on the underlying model are made, a large variety of different indices can be used to pick the number of clusters. Examples range from ad-hoc measures such as the ratio of within-cluster and between-cluster similarities, over information-theoretic criteria (Still & Bialek (2004)), the gap statistic (Tibshirani et al. (2001)), to stability approaches (Ben-Hur et al. (2002); Lange et al. (2004); Ben-David et al. (2006)). Of course all those methods can also be used for spectral clustering. Additionally, one tool which is particularly designed for spectral clustering is the eigengap heuristic, which can be used for all three graph Laplacians. Here the goal is to choose the number $k$ such that all eigenvalues $\lambda_{1},\ldots,\lambda_{k}$ are very small, but $\lambda_{k+1}$ is relatively large. There are several justifications for this procedure. The first one is based on perturbation theory, where we observe that in the ideal case of $k$ completely disconnected clusters, the eigenvalue $0$ has multiplicity $k$, and then there is a gap to the $(k+1)$th eigenvalue $\lambda_{k+1}>0$. Other explanations can be given by spectral graph theory. Here, many geometric invariants of the graph can be expressed or bounded with the help of the first eigenvalues of the graph Laplacian. In particular, the sizes of cuts are closely related to the size of the first eigenvalues. For more details on this topic we refer to Bolla (1991), Mohar (1997) and Chung (1997).

We would like to illustrate the eigengap heuristic on our toy example introduced in Section 4. For this purpose we consider similar data sets as in Section 4, but to vary the difficulty of clustering we consider the Gaussians with increasing variance. The first row of Figure 4 shows the histograms of the three samples. We construct the 10-nearest neighbor graph as described in Section 4, and plot the eigenvalues of the normalized Laplacian $L_{\text{rw}}$ on the different samples (the results for the unnormalized Laplacian are similar). The first data set consists of four well separated clusters, and we can see that the first 4 eigenvalues are approximately 0. Then there is a gap between the 4th and 5th eigenvalue, that is $|\lambda_{5}-\lambda_{4}|$ is relatively large. According to the eigengap heuristic, this gap indicates that the data set contains 4 clusters. The same behavior can also be observed for the results of the fully connected graph (already plotted in Figure 1). So we can see that the heuristic works well if the clusters in the data are very well pronounced. However, the more noisy or overlapping the clusters are, the less effective is this heuristic. We can see that for the second data set where the clusters are more “blurry”, there is still a gap between the 4th and 5th eigenvalue, but it is not as clear to detect as in the case before. Finally, in the last data set, there is no well-defined gap, the differences between all eigenvalues are approximately the same. But on the other hand, the clusters in this data set overlap so much that many non-parametric algorithms will have difficulties to detect the clusters, unless they make strong assumptions on the underlying model. In this particular example, even for a human looking at the histogram it is not obvious what the correct number of clusters should be. This illustrates that, as most methods for choosing the number of clusters, the eigengap heuristic usually works well if the data contains very well pronounced clusters, but in ambiguous cases it also returns ambiguous results.

Finally, note that the choice of the number of clusters and the choice of the connectivity parameters of the neighborhood graph affect each other. For example, if the connectivity parameter of the neighborhood graph is so small that the graph breaks into, say, $k_{0}$ connected components, then choosing $k_{0}$ as the number of clusters is a valid choice. However, as soon as the neighborhood graph is connected, it is not clear how the number of clusters and the connectivity parameters of the neighborhood graph interact. Both the choice of the number of clusters and the choice of the connectivity parameters of the graph are difficult problems on their own, and to our knowledge nothing non-trivial is known on their interactions.

4 The kk-means step

5 Which graph Laplacian should be used?

A fundamental question related to spectral clustering is the question which of the three graph Laplacians should be used to compute the eigenvectors. Before deciding this question, one should always look at the degree distribution of the similarity graph. If the graph is very regular and most vertices have approximately the same degree, then all the Laplacians are very similar to each other, and will work equally well for clustering. However, if the degrees in the graph are very broadly distributed, then the Laplacians differ considerably. In our opinion, there are several arguments which advocate for using normalized rather than unnormalized spectral clustering, and in the normalized case to use the eigenvectors of $L_{\text{rw}}$ rather than those of $L_{\text{sym}}$.

The first argument in favor of normalized spectral clustering comes from the graph partitioning point of view. For simplicity let us discuss the case $k=2$. In general, clustering has two different objectives:

We want to find a partition such that points in different clusters are dissimilar to each other, that is we want to minimize the between-cluster similarity. In the graph setting, this means to minimize $\Cut(A,\overline{A})$.

We want to find a partition such that points in the same cluster are similar to each other, that is we want to maximize the within-cluster similarities $W(A,A)$ and $W(\overline{A},\overline{A})$.

Both $\Ratiocut$ and $\Ncut$ directly implement the first objective by explicitly incorporating $\Cut(A,\overline{A})$ in the objective function. However, concerning the second point, both algorithms behave differently. Note that

Hence, the within-cluster similarity is maximized if $\Cut(A,\overline{A})$ is small and if $\vol(A)$ is large. As this is exactly what we achieve by minimizing $\Ncut$, the $\Ncut$ criterion implements the second objective. This can be seen even more explicitly by considering yet another graph cut objective function, namely the $\MinmaxCut$ criterion introduced by Ding et al. (2001):

Compared to $\Ncut$, which has the terms $\vol(A)=\Cut(A,\overline{A})+W(A,A)$ in the denominator, the $\MinmaxCut$ criterion only has $W(A,A)$ in the denominator. In practice, $\Ncut$ and $\MinmaxCut$ are often minimized by similar cuts, as a good $\Ncut$ solution will have a small value of $\Cut(A,\overline{A})$ anyway and hence the denominators are not so different after all. Moreover, relaxing $\MinmaxCut$ leads to exactly the same optimization problem as relaxing $\Ncut$, namely to normalized spectral clustering with the eigenvectors of $L_{\text{rw}}$. So one can see by several ways that normalized spectral clustering incorporates both clustering objectives mentioned above.

Now consider the case of $\Ratiocut$. Here the objective is to maximize $|A|$ and$|\overline{A}|$ instead of $\vol(A)$ and $\vol(\overline{A})$. But $|A|$ and $|\overline{A}|$ are not necessarily related to the within-cluster similarity, as the within-cluster similarity depends on the edges and not on the number of vertices in $A$. For instance, just think of a set $A$ which has very many vertices, all of which only have very low weighted edges to each other. Minimizing $\Ratiocut$ does not attempt to maximize the within-cluster similarity, and the same is then true for its relaxation by unnormalized spectral clustering.

So this is our first important point to keep in mind: Normalized spectral clustering implements both clustering objectives mentioned above, while unnormalized spectral clustering only implements the first objective.

Consistency issues

A completely different argument for the superiority of normalized spectral clustering comes from a statistical analysis of both algorithms. In a statistical setting one assumes that the data points $x_{1},\ldots,x_{n}$ have been sampled i.i.d. according to some probability distribution $P$ on some underlying data space $\mathcal{X}$. The most fundamental question is then the question of consistency: if we draw more and more data points, do the clustering results of spectral clustering converge to a useful partition of the underlying space $\mathcal{X}$?

For both normalized spectral clustering algorithms, it can be proved that this is indeed the case von Luxburg et al. (2004); von Luxburg et al. (2005); von Luxburg et al. (to appear). Mathematically, one proves that as we take the limit $n\to\infty$, the matrix $L_{\text{sym}}$ converges in a strong sense to an operator $U$ on the space $C(\mathcal{X})$ of continuous functions on $\mathcal{X}$. This convergence implies that the eigenvalues and eigenvectors of $L_{\text{sym}}$ converge to those of $U$, which in turn can be transformed to a statement about the convergence of normalized spectral clustering. One can show that the partition which is induced on $\mathcal{X}$ by the eigenvectors of $U$ can be interpreted similar to the random walks interpretation of spectral clustering. That is, if we consider a diffusion process on the data space $\mathcal{X}$, then the partition induced by the eigenvectors of $U$ is such that the diffusion does not transition between the different clusters very often von Luxburg et al. (2004). All consistency statements about normalized spectral clustering hold, for both $L_{\text{sym}}$ and $L_{\text{rw}}$, under very mild conditions which are usually satisfied in real world applications. Unfortunately, explaining more details about those results goes beyond the scope of this tutorial, so we refer the interested reader to von Luxburg et al. (to appear).

In contrast to the clear convergence statements for normalized spectral clustering, the situation for unnormalized spectral clustering is much more unpleasant. It can be proved that unnormalized spectral clustering can fail to converge, or that it can converge to trivial solutions which construct clusters consisting of one single point of the data space von Luxburg et al. (2005); von Luxburg et al. (to appear). Mathematically, even though one can prove that the matrix $(1/n)L$ itself converges to some limit operator $T$ on $C(\mathcal{X})$ as $n\to\infty$, the spectral properties of this limit operator $T$ can be so nasty that they prevent the convergence of spectral clustering. It is possible to construct examples which show that this is not only a problem for very large sample size, but that it can lead to completely unreliable results even for small sample size. At least it is possible to characterize the conditions when those problem do not occur: We have to make sure that the eigenvalues of $L$ corresponding to the eigenvectors used in unnormalized spectral clustering are significantly smaller than the minimal degree in the graph. This means that if we use the first $k$ eigenvectors for clustering, then $\lambda_{i}\ll\min_{j=1,\ldots,n}d_{j}$ should hold for all $i=1,\ldots,k$. The mathematical reason for this condition is that eigenvectors corresponding to eigenvalues larger than $\min d_{j}$ approximate Dirac functions, that is they are approximately 0 in all but one coordinate. If those eigenvectors are used for clustering, then they separate the one vertex where the eigenvector is non-zero from all other vertices, and we clearly do not want to construct such a partition. Again we refer to the literature for precise statements and proofs.

For an illustration of this phenomenon, consider again our toy data set from Section 4. We consider the first eigenvalues and eigenvectors of the unnormalized graph Laplacian based on the fully connected graph, for different choices of the parameter $\sigma$ of the Gaussian similarity function (see last row of Figure 1 and all rows of Figure 5). The eigenvalues above $\min d_{j}$ are plotted as blue stars, the eigenvalues below $\min d_{j}$ are plotted as red diamonds. The dashed line indicates $\min d_{j}$. In general, we can see that the eigenvectors corresponding to eigenvalues which are much below the dashed lines are “useful” eigenvectors. In case $\sigma=1$ (plotted already in the last row of Figure 1), Eigenvalues 2, 3 and 4 are significantly below $\min d_{j}$, and the corresponding Eigenvectors 2, 3, and 4 are meaningful (as already discussed in Section 4). If we increase the parameter $\sigma$, we can observe that the eigenvalues tend to move towards $\min d_{j}$. In case $\sigma=2$, only the first three eigenvalues are below $\min d_{j}$ (first row in Figure 5), and in case $\sigma=5$ only the first two eigenvalues are below $\min d_{j}$ (second row in Figure 5). We can see that as soon as an eigenvalue gets close to or above $\min d_{j}$, its corresponding eigenvector approximates a Dirac function. Of course, those eigenvectors are unsuitable for constructing a clustering. In the limit for $n\to\infty$, those eigenvectors would converge to perfect Dirac functions. Our illustration of the finite sample case shows that this behavior not only occurs for large sample size, but can be generated even on the small example in our toy data set.

It is very important to stress that those problems only concern the eigenvectors of the matrix $L$, and they do not occur for $L_{\text{rw}}$ or $L_{\text{sym}}$. Thus, from a statistical point of view, it is preferable to avoid unnormalized spectral clustering and to use the normalized algorithms instead.

Which normalized Laplacian?

Outlook and further reading

Spectral clustering goes back to Donath & Hoffman (1973), who first suggested to construct graph partitions based on eigenvectors of the adjacency matrix. In the same year, Fiedler (1973) discovered that bi-partitions of a graph are closely connected with the second eigenvector of the graph Laplacian, and he suggested to use this eigenvector to partition a graph. Since then, spectral clustering has been discovered, re-discovered, and extended many times in different communities, see for example Pothen et al. (1990), Simon (1991), Bolla (1991), Hagen & Kahng (1992), Hendrickson & Leland (1995), Van Driessche & Roose (1995), Barnard et al. (1995), Spielman & Teng (1996), Guattery & Miller (1998). A nice overview over the history of spectral clustering can be found in Spielman & Teng (1996).

In the machine learning community, spectral clustering has been made popular by the works of Shi & Malik (2000), Ng et al. (2002), Meila & Shi (2001), and Ding (2004). Subsequently, spectral clustering has been extended to many non-standard settings, for example spectral clustering applied to the co-clustering problem Dhillon (2001), spectral clustering with additional side information Joachims (2003) connections between spectral clustering and the weighted kernel-$k$-means algorithm Dhillon et al. (2005), learning similarity functions based on spectral clustering Bach & Jordan (2004), or spectral clustering in a distributed environment Kempe & McSherry (2004). Also, new theoretical insights about the relation of spectral clustering to other algorithms have been found. A link between spectral clustering and the weighted kernel $k$-means algorithm is described in Dhillon et al. (2005). Relations between spectral clustering and (kernel) principal component analysis rely on the fact that the smallest eigenvectors of graph Laplacians can also be interpreted as the largest eigenvectors of kernel matrices (Gram matrices). Two different flavors of this interpretation exist: while Bengio et al. (2004) interpret the matrix $D^{-1/2}WD^{-1/2}$ as kernel matrix, other authors Saerens et al. (2004) interpret the Moore-Penrose inverses of $L$ or $L_{\text{sym}}$ as kernel matrix. Both interpretations can be used to construct (different) out-of-sample extensions for spectral clustering. Concerning application cases of spectral clustering, in the last few years such a huge number of papers has been published in various scientific areas that it is impossible to cite all of them. We encourage the reader to query his favorite literature data base with the phrase “spectral clustering” to get an impression no the variety of applications.

The success of spectral clustering is mainly based on the fact that it does not make strong assumptions on the form of the clusters. As opposed to $k$-means, where the resulting clusters form convex sets (or, to be precise, lie in disjoint convex sets of the underlying space), spectral clustering can solve very general problems like intertwined spirals. Moreover, spectral clustering can be implemented efficiently even for large data sets, as long as we make sure that the similarity graph is sparse. Once the similarity graph is chosen, we just have to solve a linear problem, and there are no issues of getting stuck in local minima or restarting the algorithm for several times with different initializations. However, we have already mentioned that choosing a good similarity graph is not trivial, and spectral clustering can be quite unstable under different choices of the parameters for the neighborhood graphs. So spectral clustering cannot serve as a “black box algorithm” which automatically detects the correct clusters in any given data set. But it can be considered as a powerful tool which can produce good results if applied with care.

In the field of machine learning, graph Laplacians are not only used for clustering, but also emerge for many other tasks such as semi-supervised learning (e.g., Chapelle et al. (2006) for an overview) or manifold reconstruction (e.g., Belkin & Niyogi (2003)). In most applications, graph Laplacians are used to encode the assumption that data points which are “close” (i.e., $w_{ij}$ is large) should have a “similar” label (i.e., $f_{i}\approx f_{j}$). A function $f$ satisfies this assumption if $w_{ij}(f_{i}-f_{j})^{2}$ is small for all $i,j$, that is $f^{\prime}Lf$ is small. With this intuition one can use the quadratic form $f^{\prime}Lf$ as a regularizer in a transductive classification problem. One other way to interpret the use of graph Laplacians is by the smoothness assumptions they encode. A function $f$ which has a low value of $f^{\prime}Lf$ has the property that it varies only “a little bit” in regions where the data points lie dense (i.e., the graph is tightly connected), whereas it is allowed to vary more (e.g., to change the sign) in regions of low data density. In this sense, a small value of $f^{\prime}Lf$ encodes the so called “cluster assumption” in semi-supervised learning, which requests that the decision boundary of a classifier should lie in a region of low density.

An intuition often used is that graph Laplacians formally look like a continuous Laplace operator (and this is also where the name “graph Laplacian” comes from). To see this, transform a local similarity $w_{ij}$ to a distance $d_{ij}$ by the relationship $w_{ij}=1/d_{ij}^{2}$ and observe that

This intuition has been made precise in the works of Belkin (2003), Lafon (2004), Hein et al. (2005); M. et al. (2007), Belkin & Niyogi (2005), Hein (2006), Giné & Koltchinskii (2005). In general, it is proved that graph Laplacians are discrete versions of certain continuous Laplace operators, and that if the graph Laplacian is constructed on a similarity graph of randomly sampled data points, then it converges to some continuous Laplace operator (or Laplace-Beltrami operator) on the underlying space. Belkin (2003) studied the first important step of the convergence proof, which deals with the convergence of a continuous operator related to discrete graph Laplacians to the Laplace-Beltrami operator. His results were generalized from uniform distributions to general distributions by Lafon (2004). Then in Belkin & Niyogi (2005), the authors prove pointwise convergence results for the unnormalized graph Laplacian using the Gaussian similarity function on manifolds with uniform distribution. At the same time, Hein et al. (2005) prove more general results, taking into account all different graph Laplacians $L$, $L_{\text{rw}}$, and $L_{\text{sym}}$, more general similarity functions, and manifolds with arbitrary distributions. In Giné & Koltchinskii (2005), distributional and uniform convergence results are proved on manifolds with uniform distribution. Hein (2006) studies the convergence of the smoothness functional induced by the graph Laplacians and shows uniform convergence results.

Apart from applications of graph Laplacians to partitioning problems in the widest sense, graph Laplacians can also be used for completely different purposes, for example for graph drawing Koren (2005). In fact, there are many more tight connections between the topology and properties of graphs and the graph Laplacian matrices than we have mentioned in this tutorial. Now equipped with an understanding for the most basic properties, the interested reader is invited to further explore and enjoy the huge literature in this field on his own.

References