I was solving a problem recently and have been thinking whether order of nodes in laplacian matrix change clusters in spectral clustering?
I have doubts about this because the next step after calculating the laplacian matrix is to get the eigen values and vector for the laplacian matrix and then depending upon the sign of the values in 2nd smallest eigen vector, we cluster the nodes into two separate clusters. I am not able to imagine how changing the order of nodes in laplacian matrix would affect the sign of values (corresponding to nodes) in 2nd smallest eigen vector.
Edit: for example, if I choose to make adjacency matrix and degree matrix for graph and let the indices represent nodes of graph in increasing order/lexicographically. Then create a laplacian matrix and perform spectral clustering by simply creating subgraphs from 2nd smallest eigen bector based upon the sign of the values in the vectors (note that the ordering of nodes let me know which nodes belongs to which cluster). Now, if I change the ordering of nodes to some random order and then do the same process, will it change the clusters formed / subgraphs created?
You're correct. One way to express this is to let $P$ be a permutation matrix: i.e., a matrix which is 0 except for exactly one 1 in each row and in each column. The matrix $A' = PAP^{-1}$ is the result of permuting all the rows and all the columns of $A$ according to $P$. If the eigendecomposition of $A$ is $Q \Lambda Q^{-1}$, then the eigendecomposition of $A'$ is $(PQ)\Lambda(PQ)^{-1}$. Each column of $PQ$ (i.e., each eigenvector of $PA$) is a permuted eigenvector of $A$.