Spectral Clustering

by Eric Bunch

---

Posted on 01 Jun 2018

---

Introduction

Spectral clustering is a way to cluster data that has a number of benefits and applications. It relies on the eigenvalue decomposition of a matrix, which is a useful factorization theorem in matrix theory. We will look into the eigengap heuristic, which give guidelines on how many clusters to choose, as well as an example using breast cancer proteome data.

Graph Clustering Method

Spectral clustering should really be viewed as a graph clustering algorithm, in the sense that a data clustering problem is first translated to a graph clustering problem, graph clusters are found, and then translated back to the data clustering problem. Spectral clustering gives a way of grouping together nodes in a graph that are similarly connected.

Pros & Cons

Here is a short list of some pros and cons of spectral clustering compared to other clustering methods.

Pros

• Clusters not assumed to be any certain shape/distribution, in contrast to e.g. k-means. This means the spectral clustering algorithm can perform well with a wide variety of shapes of data.
• Do not necessarily need the actual data set, just similarity/distance matrix, or even just Laplacian
  • Because of this, we can cluster one dimensional data as a result of this; other algos that can do this are k-medoids and heirarchical clustering.

Cons

• Need to choose the number of clusters $k$, although there is a heuristic to help choose
• Can be costly to compute, although there are algorithms and frameworks to help

Speak here about importance of assumptions of kmeans clustering.

Eigenvalue Decomposition

For a square $n\times n$ matrix $M$, with $n$ linearly independent eigenvectors, we can find a factorization of $M$ as

\[M = UDU^{-1}\]

Where $D$ is the diagonal matrix of eigenvalues of $M$. The $i^{th}$ column of $U$, ${\bf u_i}$ is the eigenvector corresponding to the $d_{i,i}$ entry of $D$.

Adjacency Matrix and Laplacian

In order to formulate the spectral clustering algorithm, we need to translate the data into a graph representation. Our aim will be to form the Laplacian matrix of the graph, and then perform spectral clustering on that. To do this we need a few objects:

• Graph representation of the data
• Degree matrix of the graph
• Adjacency matrix of the graph

Representing the Data as a Graph

There are a number of meaningful ways to represent a data set as a graph, and the most appropriate one to choose will of course depend on the particular data set and problem being addressed. We’ll outline a few standard methods here to get us started.

Similarity Graphs

In the following three similarity graphs, the set of nodes of the graph is defined to be the set of data points in the data set; denote them by ${v_1,…,v_n }$.

• $\epsilon$-neighborhood Graph Here real number $\epsilon$ is fixed, and all nodes that are less than $\epsilon$ in distance apart are connected with an edge. This graph is typically considered as an unweighted graph.

• $k$-nearest Neighbor Graph Here we place an edge between $v_i$ and $v_j$ if $v_j$ is among the $k$ nearest neighbors of $v_i$ or if $v_i$ is among the $k$ nearest neighbors of $v_j$.

• Mutual $k$-nearest neighbor graph Here we place an edge between $v_i$ and $v_j$ if $v_j$ is among the $k$ nearest neighbors of $v_i$ and if $v_i$ is among the $k$ nearest neighbors of $v_j$.

Degree, Adjacency, and Laplacian Matrices of the Graph

For these definitions, we’ll think in general terms of a graph, and then come back to our special case. So let $G = (V, E)$ be an undirected graph with vertex set $V = {v_1,…,v_n}$.

Degree Matrix

The degree matrix $D$ of a graph $G = (V, E)$ is the $\mid V\mid \times \mid V\mid$ matrix defined by

\[D_{i,j} := \begin{cases} deg(v_i) & \text{if} \hspace{5pt} i = j \\ 0 & \text{otherwise} \end{cases}\]

where $deg(v_i)$ of a vertex $v_i \in V$ is the number of edges that terminate at $v_i$.

Adjacency Matrix

The adjacency matrix $A$ of a simple graph–no edges starting and ending at the same vertex–$G = (V, E)$ the adjacency matrix is the $\mid V\mid \times \mid V\mid$ matrix defined by

\[A_{i,j} := \begin{cases} 1 & \text{if there is an edge between } v_i \text{ and } v_j \\ 0 & \text{otherwise} \end{cases}\]

Notice that since we assumed $G$ was a simple graph, the diagonal entries of $A$ are all zero.

Lapacian Matrix

The Laplacian matrix $L$ of a simple graph $G$ is defined as

\[L = D - A.\]

Stated differently,

\[L_{i, j} = \begin{cases} deg(v_i) & \text{if } i = j \\ -1 & \text{if } i eq j \text{ there is an edge between } v_i \text{ and } v_j\\ 0 & \text{otherwise} \end{cases}\]

Normalized Laplacian

The normalized Laplacian matrix $L_{norm}$ of a simple graph $G$ is defined to be

\[L_{norm} := D^{-1}L = I - D^{-1}W\]

Algorithm

Input: Similarity matrix $S \in \mathbb{R}^{n×n}$, number $k$ of clusters to construct.

• Construct a similarity graph by one of the ways described above. Let $W$ be its weighted adjacency matrix.
• Compute the normalized Laplacian $L_{norm}$.
• Compute the first $k$ eigenvectors $u_1,…, u_k$ of $L_{norm}$.
• Let $U \in \mathbb{R}^{n×k}$ be the matrix containing the vectors $u_1,…, u_k$ as columns.
• For ${i = 1,…, n}$, let $y_i \in \mathbb{R}^k$ be the vector corresponding to the $i^{th}$ row of $U$.
• Cluster the points $(y_i)_{i=1,…,n} $ in $\mathbb{R}^k$ with the $k$-means algorithm into clusters $C_1,…, C_k$. Output: Clusters $A_1,…, A_k$ with $A_i = {j| y_j ∈ C_i}$.

Example

In this section we will use spectral clustering on a manufactured data set from Scikit-learn; the noisy moons:

I chose to generate this data set to have 120 points, and a noise factor of 0.05. Below is a representation of the epsilon graph of this data set with $\epsilon = 0.1$.

As we can see from the plot of the data as well as the graph visualization, there are two distinct clusters represented. We then compute the normalized graph Laplacian matrix $L_{norm}$, and find the eigenvalue decomposition it; that is, we find an invertible matrix $U$ and diagonal matrix $D$ where

\[L_{norm} = UDU^{-1}\]

Since we are able to see the data, we can “cheat” and say we want to cluster the data into two clusters. In general, it is not possible to look at data and tell so easily how many clusters we should have. But there is a heuristic to help us choose the number of clusters, which we will learn about in the next section.

Since we have already determined that we are looking for two clusters, we take the two columns, ${\bf u_1}$ and ${\bf u_2}$, of $U$ corresponding to the two smallest eigenvalues of $L_{norm}$. Then we use $k$-means clustering with $k=2$ to obtain two clusters within the reduced data set $[{\bf u_1}, {\bf u_2}]$. We then “pull back” the cluster labels from $[{\bf u_1}, {\bf u_2}]$ to $U$, to $L_{norm}$, and finally to the data set. Labeling the clusters with different colors, we can see the graph depiction is colored as expected

And if we plot the original data set with the clusters marked with different colors, we get an expected picture.

How to Choose $k$: Eigengap Heuristic

With spectral clustering, there is a way to choose the number of clusters $k$ (of course it is not a hard rule, but a heuristic to help inform you). If we let $\lambda_1,…,\lambda_n$ be the eigenvalues of the Laplacian, the goal is to choose $k$ such that $\lambda_1,…,\lambda_k$ are relatively small, but $\lambda_{k+1}$ is relatively large. Unfortunately, it does not seem so far like there is a simple, single-number metric that can be used to evaluate what number of clusters should be chosen.

Example: Breast Cancer Proteomes

In this example we look at breast cancer proteome data. This data can be found on Kaggle, and contains the proteome profiles for 77 breast cancer samples. After some preprocessing, a sample of the data looks like this:

We will go through this example twice: once with forming the epsilon graph from the data, and proceeding with spectral clustering, and another with forming the mutual nearest neighbors graph instead.

Epsilon Graph

Taking $\epsilon = 0.37$, we can form the epsilon graph from the data, and get the following graph

Next, we perform eigenvalue decomposition on the normalized Laplacian; $L_{norm} = UDU^{-1}$. We then plot the eigenvalues of $L_{norm}$ in increasing order

Using the eigenmap heuristic, we wish to choose an $n$ such that the first $n$ eigenvalues are relatively small, and $\mid \lambda_{n+1} - \lambda_n\mid$ is relatively large. It’s now up to our discretion what to choose, but looking at the eigenvalue plot as well as the network graph, I think it is reasonable to choose $n=4$. We then proceed with the spectral clustering algorithm: we choose the four eigenvectors in $U$ corresponding to the first four eigenvalues. Then we cluster on the lower dimensional data, and assign clusters to the original dataset accordingly. We show the graph representation of the data with clusters colored:

These are fairly decent clusterings, although it is a little “clumpy”: there are two main tightly connected clusters and a lot of nodes that are more loosely connected.

Mutual Neighbors Graph

Next, we look at the same proteome data set, but this time we will form the mutual neighbors graph during the spectral clustering process. With a little experimentation, we can find a good number of neighbors: here I chose 9 neighbors for the following graph. Already, we can see that this graph does not have the same “clumpy” look as the epsilon graph, and looks to have better clusters.

We perform the eigenvalue decomposition on the normalized Laplacian $L_{norm}$ and again plot the eigenvalues

Using the eigengap heuristic, let’s choose 5 clusters to cluster the data into. Then we proceed with the spectral clustering algorithm, and display the graph with the clusters colored.

These clusters look much better than those from the epsilon graph.

Conclusion

We have seen how spectral clustering works, and how it differs from other methods like $k$-means, as well as the eigengap heuristic and how it can be used to choose the number of clusters. The code to generate the examples in this post as can be found here.

---