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

edit

Let   be a graph with   vertices. Let   be its adjacency matrix (one can also use any other matrix, but adjacency and Laplace matrix are most common).

Let   be an eigenvalue of   of multiplicity  . The corresponding eigenspace is spanned by   linearly independent eigenvectors  . We consider the matrix

 

This matrix has   rows  . The spectral embedding of   to the eigenvalue   is an embedding into   that maps the  -th vertex of   to the point  . Edges are usually assumed embedded as straight lines between the vertices.

If  , then the  -eigenspace is the kernel (or nullspace) of   and the corresponding embedding is also known as the nullspace embedding of   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  . A different choice will result in the same embedding up to an invertible linear transformation. It is common to choose an orthonormal basis  , 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  , then both adjacency matrix and Laplace matrix yield the same spectral embeddings. The embedding to the adjacency eigenvalue   corresponds to the embedding to the Laplacian eigenvalue  .

Example

edit

Trivial embedding

edit

The adjacency matrix of a connected graph has a unique maximal eigenvalue   of multiplicity one. The associated spectral embedding is 1-dimensional.

The Laplace matrix of a connected graph has the eigenvalue   of multiplicity one. The corresponding spectral embedding is 1-dimensional and maps every vertex to the same non-zero point.

Complete graph

edit

The adjacency spectrum of the complete graph   is  , where the exponents denote multiplicities. The corresponding spectral embeddings are as follows:

  • the trivial embedding to  .
  • the spectral embedding to   embeds the   vertices in affinely independent position in  , forming the vertices of an  -dimensional simplex.

Cube graph

edit

The cube graph has spectrum   where the exponents denote mutiplicities. The corresponding spectral embeddings are as follows:

  • The spectral embedding to   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   is 3-dimensional. It is the skeleton of the cube.
  • The spectral embedding to   is 3-dimensional. It is the skeleton of the tetrahedron. The cube graph double-covers the complete graph   and in this embedding antipodal vertices in the cube graph are mapped to the same vertex of the tetrahedron.
  • The spectral embedding to   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

edit

The cycle graph   has adjacency eigenvalues   for  . All eigenvalues are of multiplicity two, except for   and, if   is even,  , which are of multipliciyt one.

The spectral embedding to   looks like a regular  -gon, while embeddings to smaller eigenvalues resemble regular star polygons. The figure shows all embeddings for a 12-gon.

Graph drawing

edit

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

edit
  • 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

edit

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

 

This can be interpreted as the vertex   being in equilibrium between two types of forces. First, a force that repells   from the origin and is propotional to   and  . Second, for each adjacent vertex  , a force that pulls   towards   and is propotional to  .

Using the Laplace matrix in place of the adjacency matrix gives an analogous interpretation, but the force repelling from the origin is proportional to   and  , 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.[citation needed]

Applications

edit

Semidefinite optimization

edit

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.

Graph drawing

edit

Polytope theory

edit

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

Symmetry properties

edit

Spectral embeddings realize all symmetries of a graph geometrically. This means that for each combinatorial symmetry   there exists a geoemtric symmetry   that permutes the vertices in the spectral embedding according to  . More precisely, it holds

 

This is a consequence of the fact that eigenspaces of   are invariant subspaces of  , the permutation matrix to  .

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


Properties

edit
  • 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  .
  • Cutting the spectral embedding to the  -th largest eigenvalue with a central hyperplane results in at most   connected components. This is a result of Courant's nodal domains theorem.


Occurances

edit
  • 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

edit

Find edge weights on a graph so as to maximize its second-smallest Laplacian eigenvalue  . 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  , as they would do if all weights are set to one. The optimization problem then reads

 

 

 

References

edit
edit