What exactly is the eigenspace of a graph (in spectral clustering)? 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?
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.