User:MWinter4/Spectral graph embedding

In spectral graph theory a spectral graph embedding (or spectral graph drawing, representation or realization) is an embedding of a graph constructed from the graph's spectral properties, that is, from eigenvalues and eigenvectors of matrices associated with the graph, such as its adjacency matrix or Laplace matrix.

Let $G$ be a graph with $n$ vertices. The procedure described below can be executed for every matrix associated with $G$. This article focuses exemplarily on the adjacency matrix $A=A(G)$. Let $\theta$ be an eigenvalue of $A$ of multiplicity $d$. The corresponding eigenspace is then spanned by $d$ linearly independent eigenvectors $u_{1},...,u_{d}\in \mathbb {R} ^{n}$. We consider the matrix

$U:={\begin{pmatrix}|&&|\\u_{1}&\!\!\cdots \!\!&u_{d}\\|&&|\end{pmatrix}}\in \mathbb {R} ^{n\times d}$

This matrix has $n$ rows $v_{1},...,v_{n}\in \mathbb {R} ^{d}$ which can be associated to the vertices of the graph. Embedding the $i$-th vertex at $v_{i}$ defines an embedding of $G$ into ${\mathbb {R}}^{d}$. The procedure does not explicitly give embeddings for the edges, which are usually assumed embedded as straight lines between the vertices.

A spectral embedding is not guaranteed to be faithful or injective: different vertices might be embedded at the same point or edges might intersects.

The procedure involves a choice for the spanning eigenvectors. It turns out that a different choice of eigenvectors yields the same embedding up to a linear transformation. Often one chooses an orthonormal basis $u_{1},...,u_{d}$, which yields embeddings with desirable geometric properties.

The sketched procedure yields an embedding whose dimension is dictated by the chosen eigenvalue of the matrix. Other procesures are conveivable, where one chooses only some eigenvectors or also eigenvectors to other eigenvalues.

Graph drawing

Further information: Spectral layout

Empirically, spectral embeddings using the second-smallest eigenvalue yield the best visual results.

Here one aims for embeddings that are 2- or 3-dimensional. This can be achieved as follows. If the desired eigenspace is too large, then one chooses only two (or three) vectors from it instead of a complete basis. If the desired eigenspace is too small, then one adds further eigenspaces until a basis of the desired size can be chosen.

Examples

• The second-smallest eigenvalue of the edge graph of the 120-cell has multiplicity four. Choosing any linearly independent eigenvectors yields the picture below.
• The second-smallest eigenvalue of the graph shown below has multiplicity one. The third-smallest eigenspace has multiplicity two. Their sum is therefore 3-dimensional and one can choose three linearly independent vectors, which yields the picture below.

Equilibrium interpretation

Spectral embeddings can be viewed as embeddings with a certain force equilibrium.

A spectral embedding can be interpreted as an embedding in a force equilibrium. Each vertex is repelled by the origin, and each edge applies a force to aech incident vertex pulling them closer together. In a spectral embedding, these forces are in equilibrium.

Symmetry properties

Spectral embeddings realize all symmetries of a graph geometrically. That means, that for each combinatorial symmetry $\sigma \in \mathrm {Aut} (G)$ there exists a geoemtric symmetry $X_{\sigma }\in \mathrm {GL} ({\mathbb {R}}^{d})$ that permutes the vertices in the spectral embedding according to $\sigma$. More precisely

$X_{\sigma }v_{i}=v_{\sigma (i)}\quad {\text{for all }}i\in \{1,...,n\}.$

This is a consequence of the fact that all eigenspaces of $A$ are invariant subspaces of $P_{\sigma }$, the permutation matrix to $\sigma$.

For some types of symmetry the converse is true as well. If the geometric symmetry group of a graph embedding acts irreducibly and distance transitively, then the embedding is a spectral embedding. In particular, the embedding realizes all the symmetries of the graph, not only a distance-transitive sub-group. If the geometric symmetry group is reducible, then the latter is still true, but embedding might be spectral to several eigenspaces. All this follows from the fact that the eigenspaces of a distance-transitive graph are exactly the irreducible subspaces of its symmetries.

Properties

• Usually symmetries in a graph force it to have large eigenspaces and therefore high-dimensional spectral realizations. There are however also graphs with trivial automorphism groups with large eigenspaces, such as strongly regular graphs, or more generally, distance-regular graphs.

• For the adjacency matrix (and Laplace matrix) the largest eigenvalue is always of multiplicity one. The corresponding spectral embedding is a single point.

• For spectral embeddings to any eigenvalue other than the largest one, the spectral embedding is centered. That means that $v_{1}+\cdots +v_{n}=0$.

• Cutting the spectral embedding to the $k$-th largest eigenvalue with a central hyperplane results in at most $k$ connected components. This is a result of Courant's nodal domains theorem.

Occurances

• Nullspace embeddings are a special name for spectral embeddings to the eigenvalue 0. The corresponding eigenspace is the kernel of the matrix.
• Colin de Verdière embeddings are nullspace embeddings w.r.t. a Colin de Verdière matrix of the graph.
• Skeleta of polytopes are spectral embeddings of the polytope's edge graph to a special Colin de Verdière matrix.

Eigenvalue optimization

...

External links

• www.example.com