<p>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:</p>
<p><strong>graph =&gt; adjacency matrix =&gt; Laplacian matrix =&gt; eigenvalues (spectrum)</strong>.</p>
<p>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.</p>
<p>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.</p>
<p><strong>Example</strong></p>
<p>Assume a simple graph with 3 vertex {1,2,3} and edges (1,2) and (2,3). The respective Laplacian matrix is:</p>
<p><span class="math-container">$$
A=\begin{pmatrix}
1 &amp; -1 &amp; 0\\
-1 &amp; 2 &amp; -1\\
0 &amp; -1 &amp; 1
\end{pmatrix}
$$</span></p>
<p>a) vertex 1, than in vertex space is (1,0,0) maps to:</p>
<p><span class="math-container">$$
A\begin{pmatrix}
1\\
0\\
0
\end{pmatrix}
=
\begin{pmatrix}
1\\
-1\\
0
\end{pmatrix}
$$</span></p>
<p>if we analyze the product result, component by component, it means:</p>
<ul>
<li>vertex 1 is connected to 1 node.</li>
<li>vertex 2 is connected to vertex 1</li>
<li>vertex 3 is not connected to vertex 1.</li>
</ul>
<p>b) the set of vertexs 1 and 2, that is represented in vertex space as (1,1,0), maps to:</p>
<p><span class="math-container">$$
A\begin{pmatrix}
1\\
1\\
0
\end{pmatrix}
=
\begin{pmatrix}
0\\
1\\
-1
\end{pmatrix}
$$</span></p>
<p>meaning that:</p>
<ul>
<li>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).</li>
<li>vertex 2 is a vertex in the set and connected to one vertex out of the set (internal frontier).</li>
<li>vertex 3 is a vertex not in the set but connected to it (external frontier).</li>
</ul>
<p>Finally, see what happens if multiply (inner/scalar product) previous result by the vertex vector again:</p>
<p><span class="math-container">$$
\begin{pmatrix}
1 &amp; 1 &amp; 0
\end{pmatrix}
A\begin{pmatrix}
1\\
1\\
0
\end{pmatrix}
= 1
$$</span></p>
<p>it gives the number of edges that connects the set of nodes {1,2} with the remainder graph.</p>

CC BY-SA 4.0
2020-11-08T18:00:49.780Z
Thank you for this beautiful answer! I have one follow up question. As you have told, we see the Laplacian as a linear transformation from the vertex space to the connectivity space. Are vertex and connectivity spaces vector spaces? Do they have an algebra equivalent to closure properties(like + and scalar multiplication)? If yes, how are these properties defined?
Manish Kausik Hari Baskar
CC BY-SA 4.0
2020-11-08T19:04:08.563Z
@ManishKausikHariBaskar: yes, they are. Fiedler value and vector is an example of its application. The problem that surpasses my mathematical knowledge is the meaning of a vertex vector not-unary (component values different of 0 and 1), as the ones present in the eigenvectors of the Laplacian. Could be something to ask in math stack exchange.
pasaba por aqui
CC BY-SA 4.0
2020-11-06T19:43:29.923Z
2020-11-08T19:01:14.440Z
2020-11-08T19:01:14.440Z
pasaba por aqui
<p>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?</p>

CC BY-SA 4.0
2020-11-06T18:15:33.220Z
Well, I am not really familiar with these clustering algorithms, but aren't you actually finding the eigenvectors of matrices such as the adjacency or similarity matrices of the graph? See also https://en.wikipedia.org/wiki/Spectrum_of_a_matrix.
nbro
CC BY-SA 4.0
2020-11-06T18:20:09.877Z
Yes we are, but these adjacency matrices are transformations from one vector space to another. I wanted to know if there exists any interpretation of either this  transformation or the domain and range vector spaces  in terms of the original graph.
Manish Kausik Hari Baskar
<graphs><clustering><linear-algebra><graph-theory><spectral-analysis>
What exactly is the eigenspace of a graph (in spectral clustering)?
Manish Kausik Hari Baskar
# What exactly is the eigenspace of a graph (in spectral clustering)?

(Asked by: username_0 on 2020-11-06)

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?

**Tags:** graphs, clustering, linear-algebra, graph-theory, spectral-analysis

> **Comments:**
> **username_1**: Well, I am not really familiar with these clustering algorithms, but aren't you actually finding the eigenvectors of matrices such as the adjacency or similarity matrices of the graph? See also https://en.wikipedia.org/wiki/Spectrum_of_a_matrix.  
> **username_0**: Yes we are, but these adjacency matrices are transformations from one vector space to another. I wanted to know if there exists any interpretation of either this  transformation or the domain and range vector spaces  in terms of the original graph.  

---

## 1 answers

### Answer by username_2 on 2020-11-06. Score: 1 | Accepted answer

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.

> **Comments:**
> **username_0**: Thank you for this beautiful answer! I have one follow up question. As you have told, we see the Laplacian as a linear transformation from the vertex space to the connectivity space. Are vertex and connectivity spaces vector spaces? Do they have an algebra equivalent to closure properties(like + and scalar multiplication)? If yes, how are these properties defined?  
> **username_2**: @ManishKausikHariBaskar: yes, they are. Fiedler value and vector is an example of its application. The problem that surpasses my mathematical knowledge is the meaning of a vertex vector not-unary (component values different of 0 and 1), as the ones present in the eigenvectors of the Laplacian. Could be something to ask in math stack exchange.  

---

