What exactly is the eigenspace of a graph (in spectral clustering)?
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 =&gt; adjacency matrix =&gt; Laplacian matrix =&gt; eigenvalues (spectrum).
The adjacency matrix describes the &quot;similarity&quot; between two graph vertexs. In the most simple case (undirected unweighted simple graph), a value &quot;1&quot; in the matrix means two vertex joined by an edge, a value &quot;0&quot; means no edge between these vertex.
So, the space under the adjacency matrix is the space of connectivity, being row &quot;i&quot; of a column vector a measure of the connectivity with vertex &quot;i&quot;. 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 &amp; -1 &amp; 0\\
-1 &amp; 2 &amp; -1\\
0 &amp; -1 &amp; 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 &amp; 1 &amp; 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.