mathematics//graph theory//spectral coordinates

Decomposing a state into modes and using modes to give coordinates to nodes are two different operations, even though both use eigenvectors. Let \(U=[v_1\;\cdots\;v_n]\) be an orthonormal basis of modes of a symmetric Laplacian.

Decomposing a state into modes and using modes to give coordinates to nodes are two different operations, even though both use eigenvectors. Let U=[v1  ⋯  vn]U=[v_1;\cdots;v_n]U=[v1​⋯vn​] be an orthonormal basis of modes of a symmetric Laplacian.

Modal coordinates of a state. A vector x∈Rnx\in\mathbb R^nx∈Rn holds the present value at each node. Its modal coordinates are a=UTxa=U^{\mathsf T}xa=UTx, x=Uax=Uax=Ua. aia_iai​ says how much the mode viv_ivi​ takes part in this state; when xxx changes, its coefficients change. It is a complete change of basis: nothing is lost while every mode is kept. In a non-orthonormal basis the corresponding inverse is used; for eigenvectors VVV normalized as VTMV=IV^{\mathsf T}MV=IVTMV=I the coordinates are a=VTMxa=V^{\mathsf T}Mxa=VTMx (modes).

Spectral coordinates of a node. Select rrr modes and form Ur∈Rn×rU_r\in\mathbb R^{n\times r}Ur​∈Rn×r. The row iii,

ξi=(v1(i),…,vr(i)),\xi_i=\bigl(v_1(i),\ldots,v_r(i)\bigr),ξi​=(v1​(i),…,vr​(i)),

is a new representation of node iii. It does not say how much mode there is in some initial condition: it says what value each selected pattern assigns to that node. Columns are full patterns over all nodes; rows are the new coordinates of each node. This difference is the heart of spectral clustering.

What depends on a choice. The sign of an eigenvector is arbitrary. For a repeated eigenvalue the basis of its subspace can be rotated. "Positive" and "negative" labels are not physical identities of communities. A common orthogonal rotation of the represented space preserves Euclidean distances and the K-means objective; selecting only part of a degenerate subspace or changing scales can alter the geometry. Diffusion maps weight coordinates with temporal factors such as μjkvj(i)\mu_j^k v_j(i)μjk​vj​(i), favoring the modes that persist at the chosen scale; not every spectral representation carries that weighting.

Relation and difference with PCA. In PCA the eigenvectors of a covariance live in the space of measured variables and the samples are projected onto them. In a graph of samples the Laplacian eigenvectors have one component per sample. They share spectral algebra but do not diagonalize the same object nor preserve the same criterion.

Dimensionality reduction is where exact representation and compression part ways; two-community graph computes rows and patterns explicitly.