Geometric significance of the dimensional reduction part of spectral clustering?

Question

While performing spectral clustering of the original data $\{x_1,...x_n\}$, $ x_i\in \mathbb{R}^{d\times 1}$ (column vectors), into $k$ clusters, we

Step 1: take the first (smallest) $k$ (column) eigenvectors $\{u_1,...u_k\}$ of the Laplacian $L=D-W$, where, $D=$degree matrix, $W=$ weight or affinity matrix,

Step 2: form the matrix $U\in \mathbb{R}^{n\times k}$ with $u_i$'s as columns,

Step 3: then take the rows $\{y_i:1\leq i \leq n\}$ of $U$ and then perform k-means clustering or a distortion minimizing clustering on these rows. See the screenshot of the algorithm here:

My questions are these:

(1) Let the rows of $U\in \mathbb{R}^{n\times k}$ be $\{y_i:1\leq i \leq n\}$. Then the $k$-dimensional vectors $y_i$'s represent a reduced dimensional interpretation of the original data. But is this lower dimensional representation of the original data any meaningful either geometrically or statistically? By 'geometrically meaningful' I mean: is the map $G: \mathbb{R}^d \to \mathbb{R}^k, G(x_i)= y_i$ locally distance preserving or angle preserving, or at least approximately preserving? By 'statistically meaningful' I mean: if the same map $G$ preserves some statistical properties of the original data, e.g. mean pr covariance, remains the same or approximately the same when we project the data into $\mathbb{R}^{k}$ using the matrix $U$.

(2) Since the distortion minimizing algorithms like k-means that we apply in the final step, assumes that clusters are globular (i.e. "like a ball" or convex from a Euclidean point of view), I wonder what properties do the reduced dimensional representation of the data have that allows us to apply k-means? For example, If we the new data $Y=\{y_1,...y_n\}$, what's the guarantee that it'll have convex clusters?

Answer 1

Spectral embedding, the dimensional reduction part of spectral clustering, preserves topological features of the adjacency graph, not metric properties of the embedded data set. Your $W$ is an affinity matrix - either a nearest-neighbors adjacency matrix, or a dissimilarity matrix from a Gaussian radial basis kernel, etc. The spectral embedding algorithm can be interpreted as a min-cut algorithm, it finds cuts that splits the graph into connected components.

This is in contrast to methods like multidimensional scaling, MDS, which is constrained to match pairwise distances between the original and projected dataset. It preserves the distances and therefore the inner products.

This gives an idea:

import numpy as np
from sklearn.manifold import SpectralEmbedding
from sklearn.datasets import load_digits
from sklearn.utils._testing import set_random_state
from sklearn.neighbors import kneighbors_graph
from sklearn.metrics import euclidean_distances

X, _ = load_digits(return_X_y=True)
X = X[880:885]

n_neighbors = 2
n_components = 2
transformer_se = SpectralEmbedding(n_components=n_components,
                                   affinity='nearest_neighbors',
                                   n_neighbors=2)

set_random_state(transformer_se)
X_trans1 = transformer_se.fit_transform(X)

transformer_mds = manifold.MDS(dissimilarity='euclidean', eps=0.001, 
max_iter=5, metric=True, n_components=3, n_init=2,
                           n_jobs=None, random_state=0, verbose=0)
set_random_state(transformer_mds)
X_trans2 = transformer_mds.fit_transform(X)


In [41]: kneighbors_graph(X_trans1, n_neighbors=2, include_self=True).toarray()                                                                                                                                   
Out[41]: 
array([[1., 0., 1., 0., 0.],
       [1., 1., 0., 0., 0.],
       [1., 0., 1., 0., 0.],
       [0., 0., 0., 1., 1.],
       [0., 0., 0., 1., 1.]])

In [42]: kneighbors_graph(X, n_neighbors=2, include_self=True).toarray()                                                                                                                                          
Out[42]: 
array([[1., 0., 1., 0., 0.],
       [1., 1., 0., 0., 0.],
       [1., 0., 1., 0., 0.],
       [0., 0., 0., 1., 1.],
       [0., 0., 0., 1., 1.]])

In [43]: kneighbors_graph(X_trans2, n_neighbors=2, include_self=True).toarray()                                                                                                                                   
Out[43]: 
array([[1., 0., 1., 0., 0.],
       [0., 1., 1., 0., 0.],
       [1., 0., 1., 0., 0.],
       [0., 0., 0., 1., 1.],
       [0., 0., 0., 1., 1.]])

So spectral embedding reproduces the nearest neighbors graph, MDS doesn't.

However,

In [45]: euclidean_distances(X)                                                                                                                                                                                   
Out[45]: 
array([[ 0.        , 50.15974482, 36.68787266, 47.23346271, 50.60632372],
       [50.15974482,  0.        , 51.04899607, 50.76416059, 53.89805191],
       [36.68787266, 51.04899607,  0.        , 59.37171044, 52.60228132],
       [47.23346271, 50.76416059, 59.37171044,  0.        , 37.09447398],
       [50.60632372, 53.89805191, 52.60228132, 37.09447398,  0.        ]])

In [46]: euclidean_distances(X_trans1)                                                                                                                                                                            
Out[46]: 
array([[0.        , 1.15470054, 0.57735027, 0.63169869, 0.63169869],
       [1.15470054, 0.        , 1.73205081, 1.31619777, 1.31619777],
       [0.57735027, 1.73205081, 0.        , 0.85579003, 0.85579003],
       [0.63169869, 1.31619777, 0.85579003, 0.        , 0.        ],
       [0.63169869, 1.31619777, 0.85579003, 0.        , 0.        ]])

In [47]: euclidean_distances(X_trans2)                                                                                                                                                                            
Out[47]: 
array([[ 0.        , 52.7809299 , 34.1894608 , 44.14053578, 53.79196188],
       [52.7809299 ,  0.        , 47.64948448, 52.05151916, 53.96227945],
       [34.1894608 , 47.64948448,  0.        , 61.78778799, 49.82688904],
       [44.14053578, 52.05151916, 61.78778799,  0.        , 36.73674785],
       [53.79196188, 53.96227945, 49.82688904, 36.73674785,  0.        ]])

MDS preserves pairwise distances much better, something spectral embedding doesn't attempt to do.

Regarding (2), the embedding steps attempts to retain blobs that might live on a higher-dimensional manifold that is not a hyperplane, to flatten them out so that kmeans in lower dimensions can separate easily. I can provide a more quantitative answer, but that is the idea.