2
$\begingroup$

I have generated this output, where L is the Laplacian Matrix, D is the degree and A is the adjacency matrix:

enter image description here

I can see the eigenvalues and eigenvectors are returned. I am unsure how to interpret these, to tell me how many clusters are in this graph? Can someone explain to me how you interpret the output returned? I was reading about something called a Fiedler value and how this is the second smallest eigenvalue (so in this case, 0?) and how I can use that? But I don't understand the logic?

So my specific question is how do you use the information provided above, to identify how many clusters are in this graph/matrix?

$\endgroup$

1 Answer 1

5
+25
$\begingroup$

TLDR: The multiplicity of $0$ as an eigenvalue of $L$ gives the number of connected components in the graph. The eigenspace of $0$ gives us a way to partition the graph. The application to your problem is at the end of the post.


One common proof of this uses two facts:

  1. $\lambda_2$, often called the algebraic connectivity of the graph, is positive if and only if $L$ has exactly one connected component.
  2. The spectrum of a block diagonal matrix is the union (with multiplicty) of the spectra of the blocks.

Each connected component corresponds to a block of $L$ (we could permute $A$ and $L$ to show the blocks without changing anything since this is just a relabeling of the graph), so $L$ will have one block per component and each component contributes exactly one eigenvalue of $0$. I'll use $K$ as the number of components.

This tells us how many components there are, and the eigenvectors of zero tell us how to partition the graph. We can connect the two by using the result that $$ x^T L x = \sum_{u\sim v} A_{uv}(x_u - x_v)^2. $$ A vector $x$ can be thought of as assigning a value to each node in the graph with $x_v$ being the value for node $v \in V$. $x^T L x$ tell us if $x$ tends to have big changes between well-connected nodes. I like to picture this by thinking of the graph as a collection of balls and springs and initially placing it flat on a table. Then, given some $x$, we raise or lower each node $v$ to a height of $x_v$ (lowering it if $x_v< 0$) and then $x^T L x$ is like how much stress this configuration has. If we have nodes with strong springs between them that we are moving far apart, i.e. $A_{uv}$ and $(x_u - x_v)^2$ are large, then the configuration is high stress. Minimizing $x^T L x$ is like finding a way to raise some nodes and lower others so that the graph is relatively stress-free and changes in $x$ happen over weak edges.

We always have one stress-free assignment: assign every node the same value. This shows that we can always achieve $x^T L x = 0$, which confirms how every component has an eigenvalue of $0$ by itself. If $K=1$ then the only stress-free assignments are constant vectors. If we are required to cut the graph into two pieces then we will incur some loss, but one good way to do it is to use an eigenvector of $\lambda_2$ which is what the Fiedler vector is. I'll denote such a vector by $f$. Since $0 = \lambda_1 < \lambda_2$ in this case we know $f^T\mathbf 1 = 0$ (this is due to eigenspaces of different eigenvalues being orthogonal) so this means $f$ will have some positive values and some negative values. $f$ makes $x \mapsto x^T L x$ as small as we can while being orthogonal to $\mathbf 1$, so it finds the least stressful non-trivial (i.e. we don't just put everything in th same cluster) partition of the graph, and $\lambda_2$ is the associated loss which is why $\lambda_2$ being small means the graph is less connected.

But if $K>1$ then we'll have a more interesting situation. Now we'll have a $K$-dimensional solution space to $x^T L x = 0$. There are lots of bases for this space, but one appealing one is$\newcommand{\one}{\mathbf 1}$$\{\one_{C_1}, \dots, \one_{C_K}\}$ where $\one_{C_j}$ denotes the vector that is $1$ on the nodes in component $j$ and $0$ elsewhere. Effectively these are component indicators. Each one of these gives a totally stress-free configuration because there are no springs between $C_i$ and $C_j$ for $i\neq j$.

The only trick here is that there are lots of bases for this eigenspace so we don't always get this exact one and it may not be easy for a human to read off the components from the eigenvectors. But if we finish the spectral clustering algorithm with k-means then we'll recover the components since no matter what basis we choose, it will be constant on each cluster so the nodes within a component will all be mapped to the same point and k-means will effortlessly collect them.


Applying this to your problem: you have $K=4$ and your four eigenvectors of $0$ let us easily read off the components. The first eigenvector is constant on nodes 1,2, and 3 and shows that's $C_1$. Then the next three eigenvectors are indicators for single nodes so we have one component of three nodes and then the other 3 components are just of isolated nodes with no neighbors. The self-degree of node 6 doesn't matter for this.

For more reading, Luxburg's Tutorial on Spectral Clustering is a fantastic and popular resource. Fan Chung's Spectral Graph Theory is also great although she uses a normalized Laplacian so some results may look a little different. I also really like Daniel Spielman's writings, such as this textbook draft on spectral graph theory. Ng et al's famous paper on spectral clustering is also very helpful for the difference between the noise-free case when clustering can be perfectly achieved vs. the more realistic noisy case.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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