TDA Notes - Unit 05

Laplacian eigenmaps

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

$$\begin{array}{cc}\mathrm{\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 $\mathrm{\Delta }f$ to

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

01 Theory - Laplace-Beltrami operator

The extension of the concept of $\mathrm{\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 ℝ$. Write ${\mathrm{\Omega }}^n(M)$ for the space of differential $n$-forms on $M$. The exterior derivative is a map:

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

and the co-differential is a map:

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

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

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

$$\mathrm{\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).

02 Theory - 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 $\mathrm{\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:

$$\mathrm{\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}{cc}\exp \left({\displaystyle -\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 $\mathrm{\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 {ℝ}^k$. Define $\theta$ by assigning

$$\theta :x_i⟼y_i$$

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

$$ℰ=\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.

UMAP

Uniform Manifold Approximation and Prediction

The goal of UMAP is to rebuild the data in a high $N$ space ${ℝ}^N$ as:

• Low-dimensional manifold
  • The data is first cast as a weighted graph (1-dimensional)
• Uniform sampling assumption
  • Dense clusters are spread apart and sparse areas contracted

03 Theory - UMAP process

We are given a data cloud $\{x_1,\dots ,x_n\}\in {ℝ}^N$, and a neighbor-count $k$.

(1) Create weighted partial graphs local to each data point:

For each point $x_i$, define weights as follows:

• Set $w(x_i,y_1)=1$.
• All $y_j$ are infinitely far from each other: $w(w_i,w_j)=0$ for $i\ne j$.
• For $j\ge 2$:
  • Require that $w(x_i,y_j)$ is proportional to $d(x_i,y_j)-d(x_i,y_1)$,
  • Require that ${\sum }_{j=2}^{k}w(x_i,y_j)={\log }_{2}k$.

That is, the nearest neighbor $y_1$ is placed at distance $0$ from $x_i$, and the other $k-1$ neighbors are made closer to $x_i$ by the distance removed. For each fixed $i$, the collection ${\{w(x_i,y_j)\}}_{j=1,\dots ,k}$ encodes metric structure of the original data near $x_i$ but with the closest point $y_1$ substituted for $x_i$.

The weight $w(x_i,y_j)$ is supposed to be interpreted as the probability that the point $y_j$ will lie in the same cluster as the point $x_i$.

From these requirements it is possible to deduce a formula for $w(x_i,y_j)$, as follows:

Set $d_1=d(x_i,y_1)$. (Distance to the closest neighbor.) For each $i$, solve for ${\sigma }_i$ such that:

$$\sum _{j=1}^k\exp \left(\frac{-\max (0,d(x_i,y_j)-d_1}{{\sigma }_i}\right)={\log }_{2}k$$

The idea is that for the closest neighbor $y_1$, the weight $w(x_i,y_1)$ should be the highest; the weight should decrease for neighbors that are farther away.

---

(2) Glue partial metrics into a single weighted graph:

Now we define a single weighted graph with vertices the points $x_1,\dots ,x_n$ and weights coming from the set of partial graphs defined in Step (1).

Observe that a given pair of vertices $x_i,x_{i^{\prime }}$ could appear with finite distance in at most two partial graphs. The relation of being “nearest neighbor” is not in general symmetric:

Now, let us be given a pair of vertices $(x_i,x_{i^{\prime }})$.

If this pair appears (with finite weight) in only one partial graph, give the pair a weighted edge in the total graph with the same weight it had in that partial graph.

If this pair appears in two partial graphs, then $x_i$ is the center point in one of them and $x_{i^{\prime }}$ is the center in the other.

We combine the weights as follows:

• Let $p_1=w(x_i,x_{i^{\prime }})$
• Let $p_2=w(x_{i^{\prime }},x_i)$

Then the weight on the pair $(x_i,x_{i^{\prime }})$ shall be defined as:

$$1-(1-p_1)(1-p_2)=p_1+p_2-p_1{p}_2$$

Now we have defined a total weighted graph that combines the information from all the weighted partial (local) graphs.

---

(3) Embed the total weighted graph $G$ in a lower-dimensional space ${ℝ}^k$ as a weighted graph $H$.

This can be done with standard techniques that we don’t cover here. Briefly:

Start with the spectral graph embedding. Edge weights for edge $e$ are $p_e$ in $G$ and $q_e$ in $H$. Cross-entropy formula:

$$\sum _e{p}_e\log \left(\frac{p_e}{q_e}\right)+(1-p_e)\log \left(\frac{1-p_e}{1-q_e}\right)$$

Use this cross-entropy as a cost function and perform stochastic gradient descent to minimize the cost.

04 Theory - Gradient descent

Suppose we are given a cost function $f:M\to ℝ$.

Given any $x\in M$, the gradient of $f$, written $D_{𝐯}(f)$, is the direction of the largest rate of change of $f$.

$$𝐯=\nabla f=⟨\frac{\partial f}{\partial x_1},\dots ,\frac{\partial f}{\partial x_n}⟩$$

Smallest rate of change is $-\nabla f$.

05 Illustration

UMAP is based on an assumption that the data samples uniformly from a manifold.

Hausdorff manifolds?

Consider $X=ℝ\backslash \{0\}\bigsqcup \{B\}\bigsqcup \{R\}$ with the standard non-Hausdorff metric:

So the points $B$ and $R$ cannot be separated by a disjoint neighborhood.

But this can actually happen with data! Suppose flowers come in two colors, red and blue, but the value (lightness) ranges from very dark (black) to very light (white):

06 Illustration

(Böhm et al. 2022)