2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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 en.wikipedia.org/wiki/Spectrum_of_a_matrix. $\endgroup$ – nbro Nov 6 '20 at 18:15
  • $\begingroup$ 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. $\endgroup$ – Manish Kausik Hari Baskar Nov 6 '20 at 18:20
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ – Manish Kausik Hari Baskar Nov 8 '20 at 18:00
  • $\begingroup$ @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. $\endgroup$ – pasaba por aqui Nov 8 '20 at 19:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.