What exactly is the eigenspace of a graph (in spectral clustering)?

Question

When we find the eigenvectors of a graph (say in the context of spectral clustering), what exactly is the vector space involved here? Of what vector space (or eigenspace) are we finding the eigenvalues of?

Answer 1

In spectral clustering we not find the eigenvectors of a graph (a graph is not a matrix) but the eigenvalues/eigenvectors of the Laplacian matrix related to the adjacency matrix of the graph:

graph => adjacency matrix => Laplacian matrix => eigenvalues (spectrum).

The adjacency matrix describes the "similarity" between two graph vertexs. In the most simple case (undirected unweighted simple graph), a value "1" in the matrix means two vertex joined by an edge, a value "0" means no edge between these vertex.

So, the space under the adjacency matrix is the space of connectivity, being row "i" of a column vector a measure of the connectivity with vertex "i". In other words, the adjacency and Laplacian matrix map from vertexs to vertex connectivity.

Example

Assume a simple graph with 3 vertex {1,2,3} and edges (1,2) and (2,3). The respective Laplacian matrix is:

$$ A=\begin{pmatrix} 1 & -1 & 0\\ -1 & 2 & -1\\ 0 & -1 & 1 \end{pmatrix} $$

a) vertex 1, than in vertex space is (1,0,0) maps to:

$$ A\begin{pmatrix} 1\\ 0\\ 0 \end{pmatrix} = \begin{pmatrix} 1\\ -1\\ 0 \end{pmatrix} $$

if we analyze the product result, component by component, it means:

• vertex 1 is connected to 1 node.
• vertex 2 is connected to vertex 1
• vertex 3 is not connected to vertex 1.

b) the set of vertexs 1 and 2, that is represented in vertex space as (1,1,0), maps to:

$$ A\begin{pmatrix} 1\\ 1\\ 0 \end{pmatrix} = \begin{pmatrix} 0\\ 1\\ -1 \end{pmatrix} $$

meaning that:

• vertex 1 is internal or external to the set {1,2}, not frontier (in this concrete case, it is internal: belongs to set and has no edge with any node out of the set).
• vertex 2 is a vertex in the set and connected to one vertex out of the set (internal frontier).
• vertex 3 is a vertex not in the set but connected to it (external frontier).

Finally, see what happens if multiply (inner/scalar product) previous result by the vertex vector again:

$$ \begin{pmatrix} 1 & 1 & 0 \end{pmatrix} A\begin{pmatrix} 1\\ 1\\ 0 \end{pmatrix} = 1 $$

it gives the number of edges that connects the set of nodes {1,2} with the remainder graph.