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 using the graph's spectral properties. These properties include eigenvalues and eigenvectors of matrices associated with the graph, such as the graph's adjacency matrix or Laplace matrix.

Spectral embeddings describe the placement of the graph's vertices, but do not describe the embedding of edges. If relevant, the edges are usually assumed embedded as straight lines between the vertices. A spectral embedding is not guaranteed to be an embedding in the strict sense of being injective. Different vertices may be mapped to the same point and edges might intersect.

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.

If the graph is regular of degree $\delta$, then both adjacency matrix and Laplace matrix yield the same spectral embeddings. The embedding to the adjacency eigenvalue $\theta$ corresponds to the embedding to the Laplacian eigenvalue $\delta -\theta$.

Example

Trivial embedding

The adjacency matrix of a connected graph has a unique maximal eigenvalue $\theta _{1}$ of multiplicity one. The associated spectral embedding is 1-dimensional.

The Laplace matrix of a connected graph has the eigenvalue $\lambda _{1}=0$ of multiplicity one. The corresponding spectral embedding is 1-dimensional and maps every vertex to the same non-zero point.

Complete graph

The adjacency spectrum of the complete graph $K_{n}$ is $\{n^{1},0^{n-1}\}$, where the exponents denote multiplicities. The corresponding spectral embeddings are as follows:

• the trivial embedding to $\theta _{1}=n$.
• the spectral embedding to $\theta _{2}=0$ embeds the $n$ vertices in affinely independent position in ${\mathbb {R}}^{n-1}$, forming the vertices of an $n$-dimensional simplex.

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.

Cycle graph

The cycle graph $C_{n}$ has adjacency eigenvalues $\theta _{i}=2\cos(2\pi i/n)$ for $i\in \{1,...,n\}$. All eigenvalues are of multiplicity two, except for $\theta _{1}$ and, if $n$ is even, $\theta _{n}$, which are of multipliciyt one.

The spectral embedding to $\theta _{2}$ looks like a regular $n$-gon, while embeddings to smaller eigenvalues resemble regular star polygons. The figure shows all embeddings for a 12-gon.

Graph drawing

Further information: Spectral layout

Spectral embeddings can be used to create visualizations of a graph. This approach can have advantages over other visualization techniques:

• no special structural properties of the graph are required (e.g. being planar, being a tree, etc). A spectral embedding always exists and is somewhat canonical.
• Most global properties of a graph are at least somehow encoded in its spectral properties, which are then expressed in the visualization.
• Spectral embeddings can be aesthetic, especially if the underlying graph has strong structural properties, such as symmetries.

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 results in 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 following visualization.

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. This 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, it holds

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

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

If the spectral embedding is constructed using an orthonormal basis of eigenvectors, then it realizes the symmetries of the graph even as isometries.

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

Find edge weights on a graph so as to maximize its second-smallest Laplacian eigenvalue $\lambda _{2}$. Since the second-smallest eigenvalue can be increased by scaling all edge weights with a positive constant, an additional normalization requirement is necessary. It is common to require that the edge weights sum up to $2|E|$, as they would do if all weights are set to one. The optimization problem then reads

${\begin{array}{rl}\max &\lambda _{2}(L_{w})\\{\text{s.t.}}&\sum _{ij\in E}w_{ij}=2|E|\\&w_{ij}\in {\mathbb {R}}\end{array}}$

${\begin{array}{rl}\min &\sum _{ij\in E}w_{ij}\\{\text{s.t.}}&\lambda _{2}(L_{w})\geq 1\\&w_{ij}\in {\mathbb {R}}\end{array}}$

${\begin{array}{rl}\min &\sum _{ij\in E}w_{ij}\\{\text{s.t.}}&L_{w}+\mu \mathbf {1} -\lambda _{2}\mathbf {I} \succeq 0\\&\lambda _{2}\geq 1\\&w_{ij}\in {\mathbb {R}},\lambda _{2},\mu \end{array}}$

External links

• www.example.com