w_{ij}=s_{ij}\) if \(v_iv_j \in E\).
\(f^TLf=\frac{1}{2}\sum^n_{i,j=1}w_{ij}(f_i-f_j)^2\) holds for any \(f \in \mathbb{R}^n\).
\(L\) has \(n\) non-negative real eigenvalues: \(0=\lambda_1 \leq \lambda_2 \leq\ldots \leq \lambda_n\).
The smallest eigenvalue of \(L\) is \(0\), and the corresponding eigenvector is \(\vec{1}\).
The number of connected components \(A_1,\ldots,A_k\) in graph \(G\) equals to the number of eigenvalues of \(L\) equal to \(0\), and the eigenspace of eigenvalue \(0\) is spanned by vectors \(\vec{1}_{A_1},\ldots,\vec{1}_{A_k}\).
For our purpose, we define normalized Laplacian slightly differently here: \(L_{rw}=D^{-1}L=I-D^{-1}W\). It is denoted as \(L_{rw}\), since it is related to the random walk matrix.
\(L_{rw}u=\lambda u\) if and only if \(\lambda\) and \(u\) solve the generalized eigenproblem \(Lu=\lambda Du\).
\(L_{rw}\) has \(n\) non-negative real eigenvalues: \(0=\lambda_1 \leq \lambda_2 \leq\ldots \leq \lambda_n\).
The smallest eigenvalue of \(L_{rw}\) is \(0\), and the corresponding eigenvector is \(\vec{1}\).
The number of connected components \(A_1,\ldots,A_k\) in graph \(G\) equals to the number of eigenvalues of \(L_{rw}\) equal to \(0\), and the eigenspace of eigenvalue \(0\) is spanned by vectors \(\vec{1}_{A_1},\ldots,\vec{1}_{A_k}\).
Now, we are ready to see two basic spectral clustering algorithms. The first algorithm uses unnormalized Laplacian, and the second one uses normalized Laplacian. The two algorithms are very similar to each other, and the only difference is they use different graph Laplacians. However, using different graph Laplacians may lend to different outcomes of clustering. We will discuss which algorithm is more preferable at the end of Section Six.
Before running the spectral clustering algorithms, first measure the pairwise similarities \(s_{ij}\) for each pair of data \(x_i\) and \(x_j\). Form similarity matrix \(S= (s_{ij})_{i,j=1,\ldots,n}\).
Unnormalized Spectral Clustering Algorithm Input: Similarity matrix \(S \in \R^{n\times n}\), number \(k\) of clusters to construct.
Construct a similarity graph by one of the ways described before. Let \(W\) be its weighted adjacency matrix.
Compute the unnormalized Laplacian \(L\).
Compute the first \(k\) eigenvectors \(u_1,\ldots,u_k\) of \(L\).
Let \(U \in \R^{n\times k}\) be the matrix containing the vectors \(u_1,\ldots,u_k\) as columns.
For $i = 1,\ldots,n,$ let \(y_i \in \R^k\) be the vector corresponding to the \(i\)-th row of \(U\).
Cluster the points \((y_i)_{i=1,\ldots,n}\) in \(\R^k\) with \(k\)-means algorithm to obtain clusters \(C_1,\ldots,C_k\).
Output: Clusters \(A_1,\ldots,A_k\) with \(A_i = \{j|y_j \in C_i\}\).
Construct a similarity graph by one of the ways described before.} Let \(W\) be its weighted adjacency matrix.
Compute the first \(k\) eigenvectors \(u_1,\ldots,u_k\) of the generalized eigenproblem \(Lu = \lambda Du\).
For \(i = 1,\ldots,n\), let \(y_i \in \R^k\) be the vector corresponding to the \(i\)-th row of \(U\).
We see the only difference between these two algorithms is step 3. For normalized clustering algorithm, the first \(k\) eigenvectors of the generalized eigenproblem \(Lu = \lambda Du\) are exactly the first \(k\) eigenvectors of the normalized Laplacian \(L_{rw}\) if \(D\) is invertible (by the first property of normalized Laplacian). Thus, essentially the only difference between these two algorithms is they use different Laplacians to obtain the first \(k\) eigenvectors. The reason the normalized algorithm does not use \(L_{rw}\) directly is that \(L_{rw}\) is not defined when \(D\) is not invertible.
Note that the number of clusters \(k\) to be constructed is an input of the algorithms. Unfortunately, in general it is not an easy task to figure out the appropriate \(k\). A useful heuristic will be discussed in Section Six.
In both algorithms, each row of the matrix \(U\) is a vector in the Euclidean space \(\R^k\). We think of each row vector of \(U\) as a vector representation of one data point. In other words, we obtain an embedding of the original data set in \(\R^k\) by making use of the first \(k\) eigenvectors of the Laplacian. We hope this is a meaningful embedding, and when the last step of the algorithms (i.e., the \(k\)-means clustering step) is performed on this vector embedding, a clustering can be easily identified and it induces a good clustering of the original data set. We will see this is indeed the case.
For completeness, we briefly introduce the \(k\)-means algorithm as in the last step of the spectral clustering algorithms.
\(k\)-means clustering is a NP-hard problem.
Input: \(n\) vectors, number \(k\) of clusters to be constructed.
Randomly pick \(k\) vectors as the initial group centers.
Assign each vector to its closest center, and obtain a grouping.
Recalculate the centers by taking means of the groups.
In general, this algorithm runs efficiently, but there are cases the algorithm converges very slowly.
Let's consider a toy example to get some intuition on the spectral clustering algorithms.
\begin{equation*} As discussed before, each row of this matrix is a vector representation of a data point, so we see data points \(1,2,3\) are represented by the same vector \((a_1,a_2, a_3)\) in \(\R^3\), \(4,5,6\) are all represented by \((b_1,b_2, b_3)\), and \(7,8,9\) are all represented by \((c_1,c_2, c_3)\). Moreover, since the three eigenvectors span a \(3\)-dimensional space, \((a_1,a_2, a_3)\), \((b_1,b_2, b_3)\) and \((c_1,c_2, c_3)\) must be three distinct points in \(\R^3\). Now, if we apply the \(k\)-means clustering algorithm on this vector embedding of the data points, we will trivially get each of the three vectors as one cluster in \(\R^3\). This clustering in \(\R^3\) induces the clustering of \(\{1, 2, 3\}, \{4, 5, 6\}\), and \(\{7, 8, 9\}\) of the original data set, which is exactly the correct clustering.
By this toy example, we see the spectral algorithms do seem to capture certain fundamental properties of clustering.
The toy example above provides some intuitive idea why the spectral algorithms make sense. In this section, some additional intuitive justification is given.
A graph \(G\) is disconnected if and only if there exist at least \(2\) eigenvalues of the Laplacians equal to \(0\). (Fact 1) This fact follows directly from the last property of both Laplacians.
a graph \(G\) has a sparse cut if and only if there exist at least \(2\) eigenvalues of the Laplacians close to \(0\). (Fact 2) This fact follows from Cheeger's inequality. Cheeger's inequality shows that the graph conductance can be approximated by the second eigenvalue of the Laplacian. In other words, a graph has a small conductance if and only if the second eigenvalue of the graph Laplacian is small. Thus, Fact 2 follows.
It is obvious that Fact 2 is an approximate version of Fact 1.
Naturally, we may ask if there is an analogous characterization for an arbitrary \(k\). It turns out this is indeed the case. In the paper by Lee, Oveis Gharan and Trevisan (2012), it is shown that a graph \(G\) can be partitioned into \(k\) sparse cuts if and only if there exist \(k\) eigenvalues close to 0.
This shows the small eigenvalues and their eigenvectors have some strong connection with the sparse partitioning of a graph. Hence, it does make sense to use the first \(k\) eigenvectors to find clustering of the data set.
The previous section gives some intuitive justification for the spectral algorithms. Now, let's see some rigorous justification. The