Consistent Spectral Clustering in Hyperbolic Spaces

In the realm of machine learning, the pivotal process of categorizing data points into cohesive groups remains vital for uncovering patterns, extracting insights, and facilitating various applications such as customer segmentation, anomaly detection, and image understanding [1]. Among the paradigms of clustering algorithms [2], alongside Partitional, Hierarchical, and Density-based techniques, Spectral Clustering on Euclidean spaces has garnered extensive research attention [3]. Spectral clustering operates in the spectral domain, utilizing the eigenvalues and eigenvectors of the Laplacian of a similarity graph constructed from the data. This algorithm initially constructs a similarity graph, where nodes represent data points and edges indicate pairwise similarities or affinities among the data points. It then computes the graph Laplacian matrix, capturing the graph’s structural properties and encoding relationships among the data points. Since its inception [See [4] and [5]], the Euclidean version of Spectral Clustering has significantly evolved. For simple clustering with two labels, this method considers the eigenvector corresponding to the second smallest eigenvalue of a specific graph Laplacian constructed from the affinity matrix based on the spatial position of the sample data. It then performs the $2$-means clustering on the rows of the Eigenmatrix [whose columns consist of the eigenvectors corresponding to the smallest two eigenvalues], treating the rows as sample data points, and finally returns the cluster labels to the original dataset. This particular form of spectral clustering finds applications [6] in Speech Separation [7], Image Segmentation [8], Text Mining [9], VLSI design [10], and more. A comprehensive tutorial is also available at [3]. Here, we will briefly review the most commonly used Euclidean Spectral Clustering Algorithm.

When connectedness is a crucial criterion for the clustering algorithms, the conventional form of Spectral Clustering emerges as a highly effective approach. It transforms the standard data clustering problem in a given Euclidean space into a graph partitioning problem by representing each data point as a node in the graph. Subsequently, it determines the dataset labels by discerning the spectrum of the graph. Beginning with a set of data points $X:={x_{1},x_{2},...,x_{N}}\in\mathbb{R}^{l}$. A symmetric similarity function (also known as the kernel function) $k_{i,j}:=k(x_{i},x_{j})$, along with the number of clusters $k$, we construct the similarity matrix $W:=w(i,j)=k_{ij}$. In its simplest form, Spectral Clustering treats the similarity matrix $W$ as a graph and aims to bipartite the graph to minimize the sum of weights across the edges of the two partitions. Mathematically, we try to solve an optimization problem [3] of the following form:

where $L:=D-W$ is the Graph Laplacian and the degree matrix $D:=diag(d_{1},d_{2},,,,d_{N}),d_{i}:=\sum_{j=1}^{N}w(i,j)$ and $L^{\prime}:=D^{-1/2}LD^{-1/2}=I-D^{-1/2}WD^{-1/2}$. $U$ is a label feature matrix, $l$ being the number of label features. Then, the simplest form of spectral clustering aims to minimize the trace by the feature matrix $U$ by considering the first $l$ eigenvectors of $L^{\prime}$ as its rows.

In order to extend the algorithm to form $k(>2)$ clusters, we consider the $k$ eigenvectors $[u_{1},u_{2},...,u_{k}]\in\mathbb{R}^{N}$ corresponding to the $k$ smallest eigenvalues of $\tilde{L}$. Then, treating the $N$ rows of the Eigenmatrix $U:=[u_{1},u_{2},...,u_{k}]$ as sample data points in $\mathbb{R}^{k}$, we perform the $k-$means clustering and label them. Finally, we return the labels to the original data points in the order they were taken to construct the degree matrix $W$. Some of the variants of this algorithm can be found at [3].

This form of Euclidean Spectral Clustering works well on Euclidean datasets, which are relatively simple and have some distinct connectedness. But as data evolves rapidly and takes extremely complex shapes, Euclidean space becomes a more inefficient model space in capturing the intricate patterns in the data and thereby helping learning algorithms in that set-up. Thus, visualizing data from a more complex topological perspective and developing unsupervised learning techniques on these complex shapes can have a consequential impact on revealing the true nature of the data. Although Deep Neural Networks on hyperbolic spaces have recently gained some attention and found applications in various computer vision problems [see [11], [12], [13], [14]], clustering algorithms or non-deep machine learning models on non-Euclidean Spaces are one of the least explored domains. In this paper, we scrutinize this domain by proposing a spectral clustering algorithm on hyperbolic spaces. While Euclidean Space fails to provide meaningful information and lacks its representational power in implementing arbitrary tree/graph-like structures or hierarchical data, that can not be embedded in Euclidean Spaces with arbitrary low dimensions, and at the same time, these spaces do not preserve the associated metric (similarity measure/dissimilarity measure), hyperbolic spaces can be beneficial to implement the structure obtained from these examples [see [15], [16]] and even some hyperbolic spaces with shallow dimension can be very powerful to represent these data and clustering on these spaces can result in far better efficiency compared to the clustering in Euclidean Spaces like Figure 1. Our main contributions to this paper are:

• •

  We propose the spectral clustering algorithm on hyperbolic spaces in which an appropriate hyperbolic similarity matrix replaces the Euclidean similarity matrix.

• •

  We also provide a theoretical analysis concerning the weak consistency of the algorithm and prove that it converges (in the sense of distribution) at least as fast as the spectral clustering on Euclidean spaces.

• •

  Advancing a step further, we present the hyperbolic versions of some of the well-known variants of Euclidean spectral clustering, such as Fast Spectral Clustering with approximate eigenvectors (FastESC) [18] and the Approximate Spectral Clustering with $k-$ means-based Landmark Selection [39].

Having said that, we organize the rest of our paper in the following way. In Section 2, we will give a brief overview of the works related to the Euclidean Spectral Clustering and its variants. We will also discuss why we need to consider a hyperbolic version of the Euclidean Spectral Clustering and some of its variants. Section 3 lays out the mathematical backgrounds pertaining to our proposed algorithm. We will discuss several results which will enable us to formulate the algorithm in a rigorous manner. We give the details of our proposed algorithm in Section 4. We discuss the motivation behind the steps related to our algorithm. Section 5 has been dedicated for the proof of the weak consistency of the proposed algorithm. Section 6 presents and discusses the experimental results. Finally, conclusions are drawn in Section 7.

We commence with a brief overview of prominent variants of Euclidean spectral clustering:

1. 1.

   Bipartite Spectral Clustering on Graphs (ESCG): Introduced by Liu et al. [17] in 2013, this algorithm primarily aims to reduce the time complexity during spectral decomposition of the affinity matrix by appropriately transforming the input similarity matrix of a Graph dataset. The method involves randomly selecting $d(\ll n)$ seeds from a given Graph of input size $n$, followed by generating $d$ supernodes using Dijkstra’s Algorithm to find the shortest distance from the Graph nodes to the seeds. This process reduces the size of the similarity matrix $\tilde{W}:=RW$, where $R$ is the indicator matrix of size $d\times n$ and $W$ is the original affinity matrix. Subsequently, it proceeds with spectral decomposition of the normalized $Z:=D_{2}^{-1/2}\tilde{W}D_{1}^{-1/2}$, where $D_{1}$ and $D_{2}$ are diagonal matrices containing the column and row sums of $\tilde{W}$, respectively. The algorithm computes the $k$ largest eigenvectors of $ZZ^{t}$ and generates $k$ clusters based on the $k$-means algorithm on the matrix $U:=D_{1}^{-1/2}X$, where $X$ is the right singular matrix in the singular value decomposition of $Z$.

2. 2.

   Fast Spectral Clustering with approximate eigenvectors (FastESC): Developed by He et al. [18] in 2019, this algorithm initially performs $k$-means clustering on the dataset with a number of clusters greater than the true clusters and then conducts spectral clustering on the centroids obtained from the $k$-means. Similar to ESCG, this algorithm also focuses on reducing the size of the input similarity matrix for spectral clustering.

3. 3.

   Low Rank Representation Clustering (LRR): Assuming a lower-rank representation of the dataset $X:=[x_{1},x_{2},...,x_{n}]$, where each $x_{i}$ is the $i$-th data vector in $\mathbb{R}^{D}$, this algorithm aims to solve an optimization problem to minimize the rank of a matrix $Z$ subject to $X=AZ$. Here, $A=[a_{1},a_{2},...,a_{m}]$ is a dictionary, and $Z:=[z_{1},z_{2},...,z_{n}]$ is the coefficient matrix representing $x_{i}$ in a lower-dimensional subspace. The algorithm iteratively updates $Z$ and an error matrix $E$ as proposed by Liu et al. in [19].

Among other variants of Spectral Clustering, such as Ultra-Scalable Spectral Clustering Algorithm (U-SPEC) [20] or Constrained Laplacian Rank Clustering (CLR) [21], the primary objective remains consistent - to enhance efficiency by reducing the burden of the spectral decomposition step through minimizing the size of the input similarity matrix. However, there has been minimal exploration regarding the translation of these algorithms into a hyperbolic setup. In this context, this marks the initial attempt to elevate non-deep machine learning algorithms beyond Euclidean Spaces.

Consider a dataset with a hierarchical structure, represented as a top-to-bottom tree. As we traverse along nodes away from the root, the distance among nodes at the same depth but with different parents grows exponentially with respect to their heights. This exponential growth renders Euclidean Space unsuitable as a model space for representing the hierarchy. Hyperbolic spaces are better suited for this purpose, where distance grows exponentially as we move away from the origin/root node. Some of these issues have been addressed in a series of papers [11], [12], [14] in the context of Deep Neural Networks. Recently in context to downstream self-supervised tasks, the authors in [22] presented scalable Hyperbolic Hierarchical Clustering (sHHC), which learns continuous hierarchies in hyperbolic space. Leveraging these hierarchies from sound and vision data, hierarchical pseudo-labels are constructed, leading to competitive performance in activity recognition compared to recent self-supervised learning models. In this work, we propose a general-purpose spectral clustering algorithm on a chosen hyperbolic space after embedding the original Euclidean dataset into the space in a particular way that minimally perturbs the inherent hierarchy.

For detailed exposure to the theoretical treatment, refer to [23], [24], and [25].

Before discussing the proposed spectral clustering algorithm, we will briefly talk about an equivalent formulation of the Euclidean Spectral Clustering algorithm. In the Introduction LABEL:sec:introduction section, we described the spectral clustering problem as trace minimization problem. In its simplest form, if the two clusters are $A$ and $B$, then solving 1.1 is equivalent to minimize the normalized cut (N-Cut) problem

where $Cut(A,B):=\sum_{i\in A,j\in B}W(i,j)$ and $Vol(A):=\sum_{i\in A,j\in V}W(i,j),Vol(B):=\sum_{i\in B,j\in V}W(i,j)$. But 4.1 is an NP-hard problem in general. To ease this problem, we tend to solve another equivalent minimization problem

Here we choose $y\in\mathbb{R}^{N}$ such that $y_{i}:=\begin{cases}\frac{1}{Vol(A)},\text{if}\hskip 7.74997pti\in A\\ \frac{-1}{Vol(B)},\text{if}\hskip 7.74997pti\in B.\end{cases}$

In order to solve 4.2 we construct the Normalized Graph Laplacians as

or

and then converting 4.2 to

where $\tilde{L}$ is either $L^{\prime}$ or $L^{\prime\prime}$. Then solving the generalized eigenvalue problem of the form $Lf=\lambda Df$ of 4.2 is transformed into an eigenvalue problem of the form $\tilde{L}f=\lambda f$. Since the smallest eigenvalue of $\tilde{L}$ is $0$, the Rayleigh Quotient 4.3 is minimized at the eigenvector corresponding to the next smallest eigenvalue. More generally, if the number of clusters is $k$, we have to choose the eigenvectors corresponding to the $k$ smallest eigenvalues.

Having all these preliminaries and the equivalent formulations, we are now ready to discuss our proposed algorithm. At first, we need to identify carefully the appropriate model space on which we will consider our data points. Since the hyperbolic space of dimension $n$ is not bounded, if we consider data points spreading across the entire space, we might run into problems to verify its consistency. To remove this shortcoming, we will consider only a compact subset of our model space chosen carefully.

Since the boundary of the model hyperbolic space $\mathbb{H}^{n}$ is at infinite distance from the origin (for example, the plane $x_{n}=0$ in Poincaré half space model or the unit circle in Poincaré disc model), we have to consider only a compact subset of $\mathbb{H}^{n}$ in order to talk about general notion of convergence. More specifically, we will fix some $\delta>0$ and consider the following subsets of $\mathbb{H}^{n}$ for either Poincaré half space model or disc model:

• •

  Poincaré Half Space Model: Consider $H^{\prime}:=\{(x_{1},x_{2},...,x_{n})|x_{n}\geq\delta\}$.

• •

  Poincaré Disc Model: Consider $H^{"}:=\{x\in\mathbb{D}^{n}\hskip 7.74997pt\text{such that}\hskip 7.74997pt\|x\|\leq(1-\delta)\}$.

Note that if we choose $\delta>0$ sufficiently small, then the clusters will not be affected by the choice of $\delta$. Since the formation of clusters depends only on the spatial position of the data points among themselves, choosing a bigger $\delta$ only affect in terms of scaling. However, in order to utilize the hyperbolic nature of $\mathbb{H}^{n}$ we will choose $\delta$ to be very small, let’s say in the order of $10^{-4}$.

Since every $n-$ dimensional model hyperbolic space is isometric to each other by the Killing-Hopf Theorem, for the purpose of convergence, it is reasonable to talk about a compact subset of only one of the model hyperbolic spaces. For our purpose, we will only consider the above mentioned compact subset of the Poincaré Disc Model and denote it by $H$, more explicitly, $H:\{x\in\mathbb{D}^{n}\hskip 3.87498pt\textit{with}\hskip 3.87498pt\|x\|\leq(1-\delta)\}$ equipped with the Poincaré metric