mathematics//graph theory//spectral coordinates
Spectral coordinates are positions given to the nodes of a network by its eigenvectors, so that nodes wired closely together land close together. They are how spectral clustering finds communities in a social graph or groups of similar data samples, and how graph-drawing tools lay a network out without being told where anything goes.
Spectral coordinates are positions given to the nodes of a network by its eigenvectors, so that nodes wired closely together land close together. They are how spectral clustering finds communities in a social graph or groups of similar data samples, and how graph-drawing tools lay a network out without being told where anything goes.
λ20.459 λ30.674 nodes15 Each node placed at (v2(i), v3(i)), its entries in the second and third eigenvectors of the Laplacian: the columns are patterns over the nodes, the rows are new coordinates for each node, and nodes of one community land together.
Slide from the drawn layout to the spectral one and the communities fall into clusters. Tap a node to follow it.
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.
The modal coordinates of a state describe that 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).
The spectral coordinates of a node describe that node. Select rrr modes and form Ur∈Rn×rU_r\in\mathbb R^{n\times r}Ur∈Rn×r; its row iii is a new representation of node iii:
ξi=(v1(i),…,vr(i)).\xi_i=\bigl(v_1(i),\ldots,v_r(i)\bigr).ξi=(v1(i),…,vr(i)).
The row 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.
PCA shares the algebra but works on another object. 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.
?Are the signs and axes of these coordinates meaningful?
Not by themselves. The sign of an eigenvector is arbitrary. For a repeated eigenvalue the basis of its subspace can be rotated. The 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)μjkvj(i), favoring the modes that persist at the chosen scale; not every spectral representation carries that weighting.