In spectral clustering, it's standard practice to solve the eigenvector problem

$$L v = \lambda v$$

where $L$ is the graph Laplacian, $v$ is the eigenvector related to eigenvalue $\lambda$.

My question: why bother taking the graph Laplacian? Couldn't I just solve the eigenvector problem for the graph (affinity matrix) itself, like the guy did in this video?


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 the same space spanned by the partition indicator vectors, a space containing a lower dimensional embedding of our graph within which (due to the nature of the minimisation problem) our clusters are now more 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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.