Why do we use the Laplacian matrix in Spectral Clustering?

Question

When we perform spectral clustering, given a similarity matrix $S$, we define the Laplacian matrix $L$ (normalized or unnormalized). Then, we do eigenvalue decomposition on $L$ and get its eigenvector matrix.

Why do we do eigenvalue decomposition on $L$, and not on the similarity matrix $S$?

It seems that a graph's spectrum (i.e. the eigenvalues of its Laplacian matrix) contains the structural information of a graph, but why? Why does it explain the graph structure?

Answer 1

Why the Laplacian?

The main idea in Spectral clustering is:

1. Find a graph representation of the data
2. Find a partition of the graph into $k$ highly inter-connected and lowly intra-connected 'clusters'

Step 2. can be reformulated as finding the minimum 'cut' of edges required to separate the graph into $k$ components.

It turns out* that minimising the value of the cut is equivalent to minimising a function of the Laplacian $L = D - W$:

$$\min_{A_1,...,A_k} \textrm{Tr}(H'LH) \textrm{ subject to } H'H = I$$

Where the columns of $H \in \mathbb{R}^{n \times k}$ are the indicator vectors of the $k$ vertex sets $A_1,...,A_k$ partitioning the graph.

Note: the solution of this is in general NP-hard given the definition of $H$, but a relaxed version where its entries can take any real value is solved by choosing $H$ as the matrix which contains the first $k$ eigenvectors of $L$ as columns.

These eigenvectors span a space containing a lower dimensional embedding of our graph, within which (due to the nature of the minimisation problem) our clusters are now easily separable.

Properties of the Laplacian

Intuition for this may be motivated by recognising the Laplacian has several useful properties absent in the adjacency matrix:

• The smallest eigenvalue of $L$ is $\lambda_0 = 0$ and its multiplicity equals the number of connected components in the graph.
• The eigenspace of $\lambda_0$ is spanned by the indicator vectors of those components.
• $L$ is singular
• $L = UU^T$ where $U$ is the incidence matrix of the (arbitrarily directed) graph (and hence $L$ is positive-semidefinite)

---

Further reading

^{* See Chapter 5 of the following document for a full derivation:}

^{... the main trick is to change the representation of the abstract data points $x_i [∈ \mathbb{R}^n]$ to points $y_i ∈ \mathbb{R}^k$. It is due to the properties of the graph Laplacians that this change of representation is useful. We will see in the next sections that this change of representation enhances the cluster-properties in the data, so that they can be trivially detected in the new representation. In particular, the simple k-means clustering algorithm has no difficulties to detect the clusters in this new representation.}

^{- A Tutorial on Spectral Clustering (2006)}

^{For further reading, see the original papers proposing he method:}

^{Spectral clustering goes back to Donath and 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.}

^{Note Fiedler himself states prior to this the Adjacency matrix (and incidence matrix) were indeed previously used to characterize graphs:}

^{We recall that many authors, e.g. A. J. HOFFMAN, M. DOOB, D. K. RAY-CHAUDHURi, J. J. SEIDEL have characterized graphs by means of the spectra of the $(0, 1)$ and $(0, 1, —1)$ adjacency matrices.}