Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-08T18:00:49.780Z
Answers.Text: 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?
Answers.UserDisplayName: Manish Kausik Hari Baskar
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-08T19:04:08.563Z
Answers.Text: @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.
Answers.UserDisplayName: pasaba por aqui
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-06T19:43:29.923Z
Answers.LastActivityDate: 2020-11-08T19:01:14.440Z
Answers.LastEditDate: 2020-11-08T19:01:14.440Z
Answers.UserDisplayName: pasaba por aqui
Body: <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>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-11-06T18:15:33.220Z
Comments.Text: 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.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-11-06T18:20:09.877Z
Comments.Text: 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.
Comments.UserDisplayName: Manish Kausik Hari Baskar
Tags: <graphs><clustering><linear-algebra><graph-theory><spectral-analysis>
Title: What exactly is the eigenspace of a graph (in spectral clustering)?
UserDisplayName: Manish Kausik Hari Baskar
ThreadText: # 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**: @username_0: 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.  
  
  ---
  
  