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
    Commented Nov 6, 2020 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$ Commented Nov 6, 2020 at 18:20

1 Answer 1

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$ Commented Nov 8, 2020 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$ Commented Nov 8, 2020 at 19:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .