Theory

Introduction

The Laplace operator $\Delta$ on smooth functions on ${\mathbb{R}}^n$ may be written in a variety of ways:

$$\begin{array}{rl}\Delta f& =\mathrm{div}(\nabla f)\\ & \\ & =\nabla \cdot \nabla f\\ & \\ & =\frac{{\partial }^{2}f}{\partial x_1^2}+\cdots +\frac{{\partial }^{2}f}{\partial x_n^2}\end{array}$$

We would like to extend the concept of $\Delta f$ to

1. smooth manifolds (coordinate independent version)
2. graphs (combinatorial version)

Laplace-Beltrami operator

The extension of the concept of $\Delta$ to smooth manifolds is called the Laplace-Beltrami operator. It is still defined as the divergence of the gradient, but these too must be upgraded to the context of manifolds.

Write $C^{\infty }(M)$ for the space of smooth functions $M\to \mathbb{R}$. Write ${\Omega }^n(M)$ for the space of differential $n$-forms on $M$. The exterior derivative is a map:

$$d_n:{\Omega }^n(M)\to {\Omega }^{n+1}(M)$$

and the co-differential is a map:

$${\delta }_{n+1}:{\Omega }^{n+1}(M)\to {\Omega }^n(M)$$

(It is defined using the Hodge star operator.) Then $\Delta f=(\delta \circ d)(f)$.

The spectrum of $\Delta$ is the set of eigenfunctions $f:M\to \mathbb{R}$, meaning functions satisfying:

$$\Delta f=\lambda f$$

for some $\lambda$.

If you know the complete spectrum of $M$, then you know a lot about the shape of $M$ (although you may not be able to recover $M$ completely).

Laplacian for graphs

In spectral graph theory one studies the spectrum of a combinatorial extension of the Laplacian concept to a graph.

We start with a weighted graph:

• Vertices $\{x_1,\dots ,x_n\}$
• Edges with weights $w_{ij}$

The adjacency matrix $A$ is the matrix $(w_{ij})$ for off-diagonal elements, and zeros on the diagonal. (No self-loops.)

The graph Laplacian $\Delta$ is the matrix with $(w_{ij})$ off-diagonal, and the diagonal entries given as follows:

$$D_{ii}=\sum _{\begin{array}{c}j=1\\ j\ne i\end{array}}^n{w}_{ij}$$

Then:

$$\Delta =D-A$$

Explanation:

For a graph $G$, let

• $C_1(G)$ be the vector space with edges of $G$ as basis
• $C_0(G)$ be the vector space with vertices of $G$ as basis

Then define

$$d_1:C_1(G)\to C_0(G)$$

by $d:(x_i,x_j)\mapsto x_j-x_i$.

There is an adjoint (transpose) map $C_0(G)\to C_1(G)$.

Laplacian eigenmaps process

Let us be given a scale $\sigma$ and a target dimension $k$.

Form a weighted graph:

• Vertices $\{x_1,\dots ,x_m\}$
• Edge weights: $w_{ij}$ as follows:

$$w_{ij}=\{\begin{array}{ll}\exp \left(-\frac{d_M(x_i,x_j{)}^2}{\sigma }\right)& d_M(x_i,x_j)<\sigma \\ & \\ 0& d_M(x_i,x_j)>\sigma \end{array}$$

Let $W=(w_{ij})$ and $D$ by $D_{ii}={\sum }_j{w}_{ij}$. The graph Laplacian is $\Delta =D-W$.

Consider the matrix with columns given by eigenvectors corresponding to the $k$-largest eigenvalues of $L$. The rows of this matrix define points $y_i\in {\mathbb{R}}^k$. Define $\theta$ by assigning

$$\theta :x_i⟼y_i$$

This definition of $y_1,\dots ,y_m$ minimizes the error:

$$\mathcal{E}=\sum _{i,j}|y_i-y_j{|}^2{w}_{ij}$$

Given the definition of $w_{ij}$, this error penalizes most strongly nearby points $x_i,x_j$ that are sent to distant points $y_i,y_j$.

The Laplacian eigenmaps process does not work well for spheres and other noncontractible spaces that are not covered by a single coordinate chart.