User:MWinter4/Spectral graph embedding

In graph theory a spectral (graph) embedding (or spectral drawing, representation or realization) or sometimes spectral layout is an embedding of a graph into Euclidean space 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.

Spectral embeddings directly describe placements only for the vertices of the graph, but not for the edges. The edges are usually embedded as straight lines between the vertices. A spectral embedding is not guaranteed to be an embedding in the strict sense of an injective map: different vertices can be mapped to the same point and edges might intersect.

Spectral embeddings are both a theoretical tool, as well as useful for applications.

Construction

Let $G$ be a graph with $n$ vertices. Let $A=A(G)\in {\mathbb {R}}^{n\times n}$ be its adjacency matrix (one can also use any other matrix, but adjacency and Laplace matrix are most common).

Let $\theta$ be an eigenvalue of $A$ of multiplicity $d$. The corresponding eigenspace is 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}$. The spectral embedding of $G$ to the eigenvalue $\theta$ is an embedding into ${\mathbb {R}}^{d}$ that maps the $i$-th vertex of $G$ to the point $v_{i}$. Edges are usually assumed embedded as straight lines between the vertices.

If $\theta =0$, then the $\theta$-eigenspace is the kernel (or nullspace) of $A$ and the corresponding embedding is also known as the nullspace embedding of $G$ w.r.t. the adjacency matrix. For example, every Colin de Verdière embedding is a nullspace embedding w.r.t. a Colin de Verdière matrix.

The procedure involves a choice for the spanning eigenvectors $u_{1},...,u_{d}$. A different choice will result in the same embedding up to an invertible linear transformation. It is common to choose an orthonormal basis $u_{1},...,u_{d}$, which results in embeddings with desirable geometric properties.

The linear dimension of the spectral embedding is determined by the multiplicity of the chosen eigenvalue. Other procedures are conveivable, where one chooses only some eigenvectors or also eigenvectors to other eigenvalues.

Example

Cube graph

The cube graph has spectrum $\{3^{1},1^{3},(-1)^{3},(-3)^{1}\}$ where the exponents denote mutiplicities. The corresponding spectral embeddings are as follows:

• The spectral embedding to $\theta _{1}=3$ is 1-dimensional. It maps all vertices to the same point. Since this point is not at the origin, the embeddings is indeed 1-dimensional.
• The spectral embedding to $\theta _{2}=1$ is 3-dimensional. It is the skeleton of the cube.
• The spectral embedding to $\theta _{3}=-1$ is 3-dimensional. It is the skeleton of the tetrahedron. The cube graph double-covers the complete graph $K_{4}$ and in this embedding antipodal vertices in the cube graph are mapped to the same vertex of the tetrahedron.
• The spectral embedding to $\theta _{4}=-3$ is 1-dimensional. It is a line segment. The cube graph is bipartite, and each bipartition class is mapped to one end of the line segment. This is a 1-dimensional embedding.

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 three 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. The sum of the eigenspace is therefore 3-dimensional and one can choose three linearly independent vectors. This results in the picture below.

Equilibrium interpretation

Spectral embeddings can be viewed as embeddings in a force equilibrium.

$\sum _{j\colon ij\in E}(v_{i}-v_{j})=\sum _{j\colon ij\in E}v_{i}-\sum _{j\colon ij\in E}v_{j}=\mathrm {deg} (i)v_{i}-\theta v_{i}=(\mathrm {deg} (i)-\theta )\cdot v_{i}.$

This can be interpreted as the vertex $v_{i}$ being in equilibrium between two types of forces. First, a force that repells $v_{i}$ from the origin and is propotional to $\|v_{i}\|$ and $\mathrm {deg} (i)-\theta$. Second, for each adjacent vertex $v_{j}$, a force that pulls $v_{i}$ towards $v_{j}$ and is propotional to $\|v_{i}-v_{j}\|$.

Using the Laplace matrix in place of the adjacency matrix gives an analogous interpretation, but the force repelling from the origin is proportional to $\|v_{i}\|$ and $\theta$, in particular, independent of the vertex' degree. If the embedding is 2-dimensional, this allows for a direct physical interpretation: the graph is placed on a rotating disc (the rotation axis is at the origin). Then each vertex is flung outwards by the centrifugal force . At the same time the vertices are held together by springs along edges that act according to Hook's law. The rotation speed of the disc depends on the eigenvalue. This interpretation gave rise to the rotational dimension graph invariant.

Applications

Semidefinite optimization

Some semidefinite programs have an interpretation as a graph embedding probelm. The optimal embedding is a spectral embedding (actually nullspace embedding) of the optimal matrix.

Polytope theory

Skeleta of polytopes are spectral embeddings of their edge graphs. This is a result due to Ivan Izmestiev.

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 a connected graph, the adjacency matrix (and Laplace matrix) has the largest (resp. smallest) eigenvalue always of multiplicity one. The corresponding spectral embedding is a single point. Since the point is not at the origin, the embedding is considered as 1-dimensional.

• If a graph is bipartite, then its adjcency spectrum is symmetric (see the example of the cube). The smallest eigenvalue then corresponds to an embedding as a line segment, where each bipartition class is mapped to one end of the segment.

• 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