4
$\begingroup$

Basically, spectral clustering is an application of spectral graph theory, which utilizes the eigenvalues and eigenvectors of a Laplacian matrix or adjacency matrix to disclose the connected components of a graph.

Let's talk about the Laplacian matrix. Ideally, for a graph with a few connected components, the values of the eigenvector corresponding to the 2nd smallest eigenvalue is a piecewise linear vector that perfectly corresponds to the components. As showed in the following figure: enter image description here

The figure shows five connected components (clusters). However, I wonder if there are any actual meaning for the magnitudes of these values?

For example, the 4th component has the smallest absolute values while 5th component has the largest, what does that tell us about these two components?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Suppose that we've got a graph with $k$ connected components. We'll denote the unnormalized Laplacian by $L$ and let $E_\lambda$ be the eigenspace corresponding to eigenvalue $\lambda$. If there are $k$ connected components then we'll find that $\dim E_0 = k$, and any basis for this space will have each vector be constant on each component (which we'll denote by $C_j$, $j = 1, \dots,k$). When we've got an eigenspace with dimension > 1 we know that the particular eigenvectors aren't important, it's the space as a whole that matters.

So with spectral clustering, when we run our algorithm (in the noiseless case) our eigensolver will produce a basis for $E_0$. But this particular basis isn't important, so we don't care about the particular values each vector takes but rather how they work together.

For example, consider the graph below: graph

One basis for $E_0$ is $$ B_1 = \begin{bmatrix}1 & 1 \\ 1 & 1 \\ 1 & 1 \\ 1 & -1 \\ 1 & -1 \end{bmatrix} $$ and another is $$ B_2 = \begin{bmatrix}1 & 0 \\ 1 & 0 \\ 1 & 0 \\ 0 & 1 \\ 0 & 1 \end{bmatrix}. $$

Which one you get from your particular eigensolver is a matter of its implementation and has nothing to do with the graph. Also note how we can rescale the values of the basis vectors on each component without changing anything.

That was for the totally noiseless case. Now let's suppose that we actually observe $\hat A = A + E$ where $E$ is some noisy matrix perturbing the "true" adjacency matrix $A$. $A$ is neatly separated into $k$ components but $\hat A$ is not.

This is where the stability of the eigenspaces comes into play. If the eigengap is large, i.e. $\lambda_{k+1} \gg 0$, then we'll still be able to recover our clusters effectively because the span of the first $k$ eigenvectors of $\hat L$ will be close to $E_0$. This is described in a number of papers, such as the well-known one by Ng, Jordan, and Weiss. The point of this, as mentioned in that paper, is that it's important to think in terms of the subspaces, not the particular eigenvectors since they are arbitrary.

Does that help?

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks. But isn't the eigensolver supposed to follow the Courant-Fischer Theorem? How about let's assume the eigensolver follows this theorem, then I thought this the solution in your example will be [[1,1,1,1,1]^T, [1,1,1,-1.5,-1.5]^T], and the solution is unique up to scaling and sign flipping. (so the relative difference of absolute values remains the same), isn't it this case? $\endgroup$
    – user42004
    Commented Apr 24, 2017 at 18:54
  • $\begingroup$ If $k=2$ and you're fixing the first vector then the other vector is also determined up to multiplication by a scalar. But if $k=3$ then even if the first eigenvector $v_1 = \mathbf 1$, I don't think Courant-Fischer provides a canonical way to choose the two remaining vectors (although I don't know the details of how eigensolvers work, but i do know that the math behind spectral clustering doesn't depend on eigensolver implementation) $\endgroup$
    – jld
    Commented Apr 24, 2017 at 19:22
  • $\begingroup$ Yeah, I am not exactly sure what happens in k=3 case either. Your answer is very helpful and I agree with you that spectral clustering is independent of the eigensolver, but that does not necessarily mean we don't have to be curious about the meaning of eigenvector, because it might be useful somewhere else, or may be helpful in improving the method, right? :) $\endgroup$
    – user42004
    Commented Apr 24, 2017 at 19:51
  • $\begingroup$ @HaohanWang definitely! The reason I tend to focus much more on the eigenspaces than on the eigenvectors is because that's how the perturbation arguments go, so that's where the insight is for how well you can recover the noiseless partition, but especially for the $k=2$ case the actual vector itself can be very meaningful $\endgroup$
    – jld
    Commented Apr 24, 2017 at 19:56

Your Answer

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