Geometric and Topological Methods in ML

Notes and relevant papers / readings for geometric and topological methods in machine learning. IN PROGRESS.

2. Geometric graphs, construction, clustering

Basics: metric spaces / metrics, graphs. Geometric graphs have vertices as points in a metric space, with edges defined by low distances in the metric space.

kNN, $\epsilon$ -NN graphs. kNN construction via KD tree.

Shortest paths methods: Dijkstra’s (single source, $O(|E| + |V|\log |V|)$ Floyd Warshall (all pairs, $O(|V|^3)$

Dijkstra: notes

Floyd Warshall: notes

We are usually interested in using shortest paths to mimic geodesic distances. Also, Alamgir (ICML 2012) shows us that unweight 1-NN graphs lead us to weird paths (want to make least number of hops, so sometimes tends towards sparse areas of great distance in the metric), and that weighted distance converges to the length of the shortest path connecting two nodes.

Manifold learning based graph construction

Distance is converted to affinities via kernels (e.g. Gaussian kernel):

\text{affinity}_{i,j} = \exp \left( - \frac{\text{dist}(x_i, x_j)^2}{2 \sigma^2} \right).

The process usually goes data $\rightarrow$ calculate distances $\rightarrow$ calculate affinities.

Graph-based clusters / community detection

Hierarchical clustering:

Link neighbors
Link clusters

How do we measure distance between clusters? There are a couple of methods: single, average, and complete linkage. We can think of single linkage as linking the two closest points between two clusters, complete as linking the furthest, and average as linking the average. Single linkage is most common:

start with every point in its own cluster
merge the two closest clusters
recompute distances based on min distance to the newly formed cluster
repeat

Modularity

$A_{ij}$ is the actual affinity between $i,j$ .

$P_{i,j}$ the probability of an edge existing between $i,j$ , calculated by:

generate random edges of the same degrees
then the prob is $k_i * k_j / 2m$ , where $m$ is the total number of edges in the graph.

Modularity is the sum of $A_{ij} - P_{ij}$ overall:

Q = \frac{1}{2m} \sum_{i,j} (A_{ij} - \frac{k_i k_j}{2m}) \delta(c_i, c_j)

Modularity optimization: Louvain used to be standard, now most use Leiden. Louvain has two phases:

Finding communities:
- Consider each node individually
- See if the node should be moved into a neighboring community: select the community with the greatest change in modularity. If moving it corresponds with a positive change in modularity, move it.
- Check only $K$ neighbors of the node
Coarse graining:
- Each community in phase 1 becomes a node in phase 2
- Repeat phase 1

Why do we care about modularity? Based on its definition, we can think of it as a measure of the strength of a graph into modules / groups / communities. Networks with high modularity have dense connections between nodes within modules but sparse connections between nodes in different modules.

3. Data diffusion, diffusion maps, spectral clustering

Representation Learning

We want to find the “best” representation of our data; i.e., we want to preserve as much information as possible while obeyind some penalty that simplifies the representation.

What kind of information should be preserved, and how do we define “simple”?

Low-dimensional
Sparse
Independent components

These criteria aren’t necessarily mutually exclusive. Simple representations are good for interpretability (visualization), reducing computational cost (compression), and performance on supervised tasks (can be easier to classify / regress from).

Isomap (Tenanbaum, 2020)

Construct neighborhood graph
Find all pairs shortest paths
Apply MDS to compute low-dimensional coordinates that preserve distances

MDS (Multidimensional Scaling)

MDS finds an embedding of the data that preserves distances by optimizing point positions such that “stress” is minimized:

\text{stress}_{D} (x_1, x_2, ..., x_N) = \sqrt{ \sum_{i \neq j = 1, ..., N} (d_{ij} - ||x_i - x_j || )^2 }.

This can be done with gradient descent and other related procedures.

Isomap’s weakness: real data is often very noisy, and the shortest path algorithm results in noisy distances between points. More commonly, we might see UMAP being used or PHATE (geometry preserving, common in biology).

Diffusion maps

Diffusion distance can be more robust to noise! Introduced by Coifman and Lafon. 3 step process:

Compute affinities with Gaussian kernel
Compute degree matrix
Markovian diffusion operator gives us coordinates

Recall kernel functions (discussed previously for converting distances to affinities). If $(X, A, \mu)$ is a measurable space, a kernel function is a mapping $K : X \times X \rightarrow \R$ such that for any $x, y \in X,$

\begin{align*} K(x,y) &= K(y,x) \\ K(x,y) &\geq 0. \end{align*}

Kernels are generally nonlinear. Diffusion maps are specifically defined with respect to the Gaussian kernel:

k(x,y) = e^{-||x-y||^2 / \eps},

where $\eps$ is a bandwidth parameter. This kernel captures a notion of affinity/similarity between points in $X.$

The Gaussian kernel emphasizes local connections and pushes non-local connections to $0$ in a “softer” way than kNN. We can also threshold these outputs for computational purposes (so that the affinity graph wouldn’t be fully connected).

After computing affinities with the Gaussian kernel, we define the degree matrix. For a weighted graph, the degree of vertex $x$ is defined as the sum of similarities/affinities between its neighbors:

q(x) = \sum_{i=0}^{i < n} k(x, v_i).

The degree matrix is a diagonal matrix where $d_{i,i} = q(\text{vertex } i)$ .

We can now define the “diffusion operator”

P(x,y) = k(x,y) / q(x),

a matrix of transition probabilities with row-normalized affinities. Therefore, this matrix is Markov & describes a random walk over the data.

Since $P$ represents the 1-step transition probabilities, $P^t$ represents the $t$ -step random walk probabilities.

The diffusion map representation is a spectral embedding; that is, $P$ has a spectral decomposition that we can use to assign coordinates in the embedding to each data point.

Consider the matrix $A$ where

a(x,y) = \frac{k(x,y)}{\sqrt{q(x)} \sqrt{q(y)}} = q(x)^{1/2} * p(x,y) * q(y)^{-1/2}.

Then $A = Q^{1/2}*P*Q^{-1/2}$ and is symmetric, so there exists an eigendecomposition. In fact, $P$ and $A$ are similar, so they must have the same eigenvalues and related eigenvectors.

Let the eigenvectors of $A$ be $\phi_1, \phi_2, ..., \phi_n$ .

A left eigenvector of $P$ , $\psi_j$ , would be $= Q^{-1/2}\phi_j$ .
A right eigenvector of $P$ , $\Psi_j$ , would be $= \phi_j Q^{-1/2}.$

We can use these eigenpairs are used to compute the spectral decomposition of $P$ :

For $1 = \lambda_0 \geq \lambda_1 \geq \lambda_2 \geq ... \geq \lambda_\delta > 0,$

\begin{pmatrix} \phi_0 & \phi_1 & \phi_2 & \cdots & \phi_delta \end{pmatrix}

where each $\phi_i$ is a column eigenvector from $A$ , we can map a datapoint $x$ to its embedding coordinates as:

x \mapsto \phi^t(x) = [ \lambda_0^t \phi_0(x), \lambda_1^t \phi_1(x), \lambda_2^t \phi_2(x), ..., \lambda_\delta^t \phi_\delta(x)]^T.

Properties of the spectrum

Eigenvalues are in range $[0,1]$
1 is an eigenvalue
The first eigenvector is the steady state/stationary vector $\phi_0$ of all 1’s
Stationary distribution given as $\pi(y) = \frac{q(y)}{\sum_{z \in X} q(z)}$
Markov chain is reversible, e.g. $\pi(x)p(x,y) = \pi(y)p(y,x)$

Powers of the matrix $A$ make lower eigenvalues get lower:

notes

Hence powers of $A$ denoise in a low-pass filtering manner. When we map $x$ to its new coordinates, we can use only the first $k$ eigvals/eigvecs due to spectrum decay while still maintaining accuracy, which reduces our dimensionality.

Diffusion distance

Diffusion maps preserve diffusion distance, a family of $L^2$ distance on the transition probability distribution between 2 points:

D_t(x,y)^2 = ||p_t(x, \cdot) - p_t(y, \cdot) ||^2_{L^2(X, d\mu / \pi)}.

This is essentially the Euclidean distance between rows of the diffusion operator.

Diffusion distance can also be interpreted as the overall distance in walking probabilities after $t$ steps when starting out in point $x$ vs. point $y$ .

Diffusion maps do a good job at cleaning data, but are not necessarily great at visualization. This is partially because diffusion maps split information into multiple orthogonal directions, e.g. plotting in 2-D will likely only show us 2-ish trajectories.

notes

Partitioning data with K-means

In k-means, we want to find $k$ splits/partitions to minimize variance within each cluster:

initialize: pick $k$ random cluster centroids
assignment: assign each datapoint $x_i$ to cluster $S_j$ that has the nearest mean $\mu_j$
update: compute the means of clusters $\mu_i = \frac{1}{|S_i|} \sum_{x_j \in S_i} x_j$

k-means converges because each reassignment lowers the MSE:

\argmin_S \sum_{i=1}^k \sum_{x \in S_i} || x- \mu_i ||^2 = \argmin_S \sum_{i=1}^k |S_i|\text{var}(S_i).

Therefore, this optimization will reach a local minima. However, k-means only works well on data with certain characteristics. It assumes:

k is chosen correctly
data is distributed normally around the mean
clusters all have equal variance
clusters all have the same number of points

It is also sensitive to initialization and outliers.

An alternative is spectral clustering. Spectral clustering can use eigenvectors of the diffusion oeprator or Laplacian. Advantages of using the spectrum for k-means:

good for clusters of arbitrary shape
good for graph data
only need connectivity data

How it works:

construct a similarity graph
compute diffusion operator or graph Laplacian
using top k eigenvectors, run k-means