Entropy-Based Incomplete Cholesky Decomposition for a Scalable Spectral Clustering Algorithm: Computational Studies and Sensitivity Analysis

Abstract

Spectral clustering methods allow datasets to be partitioned into clusters by mapping the input datapoints into the space spanned by the eigenvectors of the Laplacian matrix. In this article, we make use of the incomplete Cholesky decomposition (ICD) to construct an approximation of the graph Laplacian and reduce the size of the related eigenvalue problem from N to m, with $m\ll N$. In particular, we introduce a new stopping criterion based on normalized mutual information between consecutive partitions, which terminates the ICD when the change in the cluster assignments is below a given threshold. Compared with existing ICD-based spectral clustering approaches, the proposed method allows the reduction of the number m of selected pivots (i.e., to obtain a sparser model) and at the same time, to maintain high clustering quality. The method scales linearly with respect to the number of input datapoints N and has low memory requirements, because only matrices of size $N\times m$ and $m\times m$ are calculated (in contrast to standard spectral clustering, where the construction of the full $N\times N$ similarity matrix is needed). Furthermore, we show that the number of clusters can be reliably selected based on the gap heuristics computed using just a small matrix R of size $m\times m$ instead of the entire graph Laplacian. The effectiveness of the proposed algorithm is tested on several datasets.

1. Introduction

In this paper, we deal with the data clustering problem. Clustering refers to a technique for partitioning unlabeled data into natural groups, where data points that are related to each other are grouped together and points that are dissimilar are assigned to different groups [1]. In this context, spectral clustering [2,3,4,5] has been shown to be among the most successful methods in many application domains, due mainly to its ability to discover nonlinear clustering boundaries. The algorithm is based on computing the eigendecomposition of a matrix derived from the data called Laplacian. The eigenvectors of the Laplacian represent an embedding of the input data, which reveals the underlying clustering structure. A major drawback of spectral clustering is its computational and memory cost. If we denote the number of datapoints by N, solving the eigenvalue problem has complexity $O\left(N^3\right)$, the construction of the Laplacian matrix has cost $O\left(N^2\right)$, and the Laplacian may not fit into the main memory when N is large. A number of algorithms have been devised to make spectral clustering feasible for large scale applications, which include power iteration clustering [6], spectral clustering in conjunction with the Nyström approximation [7], incremental spectral clustering techniques [8,9,10], kernel spectral clustering [11,12,13], parallel spectral clustering [14], consensus spectral clustering [15], vector quantization-based approximate spectral clustering [16], and approximate pairwise clustering [17]. In this article, we introduce a spectral clustering algorithm that exploits the incomplete Cholesky decomposition to reduce the size of the eigenvalue problem. The idea behind the proposed method is similar to [18], but a number of novelties are introduced. First, a new stopping criterion based on normalized mutual information is devised, which allows us to decrease the number m of selected pivots, and hence, the computational complexity. Second, the number of clusters is automatically selected by means of the eigen-gap heuristics computed on a small similarity matrix of size $m\times m$. Third, a sensitivity analysis shows how to select specific threshold values in order to achieve desired cluster quality, sparsity, and computational time. The rest of this paper is organized as follows. Section 2 summarizes the spectral clustering method and the incomplete Cholesky decomposition. In Section 3, the proposed algorithm is introduced. Section 4 describes the results of the experiments, Section 5 analyzes the computational cost of the proposed algorithm, and finally Section 6 concludes the article.

2. Spectral Clustering

Spectral clustering solves a relaxation of the graph partitioning problem. In its most basic formulation, one is provided with an unweighted/weighted graph and is asked to split it into k non-overlapping groups ${\mathcal{A}}_1,\dots ,{\mathcal{A}}_k$ in order to minimize the cut size, which is the number of edges running between the groups (or the sum of their weights). This idea is formalized via the mincut problem [19], that is, the objective of finding k subgraphs such that a minimal number of edges are cut off and that the sum of all weights of these cut edges is minimal. Furthermore, in order to favour balanced clusters, the normalized cut problem can be defined as follows:

$$\begin{array}{cccc}& \underset{G}{\text{min}}\hfill & & k-\mathrm{tr}\left(G^T{L}_{n}G\right)\hfill \\ & \text{subject}\text{to}\hfill & & G^{T}G=I_N\hfill \end{array}$$

(1)

where:

• $L_n=I-D^{-\frac{1}{2}}S{D}^{-\frac{1}{2}}$ is called the normalized Laplacian;
• S is the similarity matrix, which describes the topology of the graph;
• $D=\mathrm{diag}\left(\mathbf{d}\right)$, with $\mathbf{d}={[d_1,\dots ,d_N]}^T$ and $d_i={\sum }_{j=1}^N{S}_{ij}$, denotes the degree matrix;
• $G=[{\mathbf{g}}_1,\dots ,{\mathbf{g}}_k]$ is the matrix containing the normalized cluster indicator vectors ${\mathbf{g}}_l=\frac{D^{\frac{1}{2}}{\mathbf{y}}_l}{\left|\right|D^{\frac{1}{2}}{\mathbf{y}}_l{\left|\right|}_2}$;
• ${\mathbf{y}}_l$, with $l=1,\dots ,k$, is the cluster indicator vector for the l-th cluster. It has a 1 in the entries corresponding to the nodes in the l-th cluster and 0 otherwise. Moreover, the cluster indicator matrix can be defined as $Y=[{\mathbf{y}}_1,\dots ,{\mathbf{y}}_k]\in {\{0,1\}}^{N\times k}$;
• $I_N$ denotes the $N\times N$ identity matrix.

Since this is a NP-hard problem, a good approximate solution can be obtained in polynomial time, allowing G to take continuous values; i.e., $G\in {\mathbb{R}}^{N\times k}$. In this case it can be shown that solving problem (1) is equivalent to finding the solution to the following eigenvalue problem:

$$L_n{\mathbf{g}}_l={\lambda }_l{\mathbf{g}}_l,l=1,\dots ,k,$$

(2)

where ${\lambda }_1,\dots ,{\lambda }_k$ are the k smallest eigenvalues of the normalized Laplacian $L_n$, which contain the clustering information.

2.1. Incomplete Cholesky Decomposition

A Cholesky decomposition [20] of a matrix $A\in {\mathbb{R}}^{N\times N}$ is a decomposition of a symmetric positive definite matrix into the product of a lower triangular matrix and its transpose; i.e., $A=C{C}^T$, and it is widely used to solve linear systems. The incomplete Cholesky decomposition (ICD) [21] allows the reduciton of the computational time required by the Cholesky decomposition by computing a low rank approximation of accuracy τ of the matrix A in $O\left(m^{2}N\right)$, such that $\left|\right|A-C{C}^T{\left|\right|}_{\mathrm{F}}<\tau$, with $C\in {\mathbb{R}}^{N\times m}$ and $m\ll N$. In fact, the ICD selects the rows and the columns of A in an appropriate manner, such that the rank of the approximation is close to the rank of the original matrix. In other words, the selected rows and columns, also called pivots, are related to certain data points, and this sparse set of data points is a good representation of the full data set. As discussed in [22], the ICD leads to small numerical error only when there is a fast decay of the eigenvalues. However, as pointed out in [18], this condition is not always met. Therefore, the ICD stopping criterion based on the low rank assumption is not optimal.

2.2. A Reduced Eigenvalue Problem

As described in [18,22], the ICD technique briefly summarized in the previous section can be used to speed up the solution of the spectral clustering eigenvalue problem (2). In this section, we will review the main linear algebra operations that are needed for this purpose. Let’s start by considering the following eigenvalue problem:

$${\tilde{L}}_n{\mathbf{g}}_l=\widetilde{{\lambda }_l}{\mathbf{g}}_l,l=1,\dots ,k,$$

(3)

with ${\tilde{L}}_n=D^{-\frac{1}{2}}S{D}^{-\frac{1}{2}}$, whose eigenvalues ${\tilde{\lambda }}_l$ are related to the eigenvalues of $L_n$ by the relation $\widetilde{{\lambda }_l}=1-{\lambda }_l$ (the eigenvectors are the same). Therefore, the clustering information is contained in the eigenvectors corresponding to the largest eigenvalues of ${\tilde{L}}_n$. If we replace the similarity matrix S with its ICD, we obtain that ${\tilde{L}}_n\approx {\tilde{D}}^{-\frac{1}{2}}C{C}^T{\tilde{D}}^{-\frac{1}{2}}$. In order to reduce the size of the eigenvalue problem involving ${\tilde{L}}_n$, we can replace ${\tilde{D}}^{-\frac{1}{2}}C$ with its $QR$ factorization and substitute R with its singular value decomposition to obtain:

$${\tilde{L}}_n\approx {\tilde{D}}^{-\frac{1}{2}}C{C}^T{\tilde{D}}^{-\frac{1}{2}}\approx \left(QR\right){\left(QR\right)}^T\approx Q\left(U_R{\Sigma }_R{V}_R^T\right)\left(V_R{\Sigma }_R{U}_R^T\right)Q^T\approx Q{U}_R\left({\Sigma }_R^2\right)U_R^T{Q}^T,$$

(4)

where $Q\in {\mathbb{R}}^{N\times m}$, $R\in {\mathbb{R}}^{m\times m}$, $R=U_R{\Sigma }_R{V}_R$, and $U_R,{\Sigma }_R,V_R\in {\mathbb{R}}^{m\times m}$. Notice that now we have to solve an eigenvalue problem of size $m\times m$ involving matrix $R{R}^T$, which can be much smaller than the size $N\times N$ of the original problem (3). Furthermore, the eigenvectors of problem (3) can be estimated as ${\widehat{\mathbf{g}}}_l=Q{U}_{R,l}$, whose related eigenvalues are ${\widehat{\lambda }}_l={\sigma }_{R,l}^2$. Finally, the extraction of the cluster indicator matrix from the top k eigenvectors can be achieved by computing a pivoted $LQ$ decomposition of the eigenvector matrix $D^{-\frac{1}{2}}\widehat{G}$ as proposed in [23]:

$$\widehat{Y}=PL{Q}_{\widehat{G}}$$

(5)

where $\widehat{G}=[{\widehat{\mathbf{g}}}_1,\dots ,{\widehat{\mathbf{g}}}_k]$, $P\in {\mathbb{R}}^{N\times N}$ is a permutation matrix, $L\in {\mathbb{R}}^{N\times k}$ is a lower triangular matrix, and $Q\in {\mathbb{R}}^{k\times k}$ denotes a unitary matrix. In real-world scenarios, the clusters present a certain amount of overlap. Therefore, matrix $\widehat{Y}$ becomes real-valued and the cluster assignment for point ${\mathbf{x}}_i$ is computed as:

$$j_i={\arg \max }_{l=1,\dots ,k}\left(\right|{\widehat{Y}}_{il}\left|\right).$$

(6)

3. Proposed Algorithm

As explained previously, the classic ICD algorithm is based on the assumption that the spectrum of the Laplacian matrix is characterized by a fast decay. Since this property in some cases does not hold [18], in this article we introduce a novel stopping criterion, which will be explained now.

3.1. New Stopping Criterion

The new stopping condition only assumes that the cluster assignments after the selection of each pivot tend to converge. In particular, given the cluster assignments ${\mathbf{j}}^s$ at step s and ${\mathbf{j}}^{s-1}$ at iteration $s-1$, with $\mathbf{j}=[j_1,\dots ,j_N]$, we can compute the normalized mutual information (NMI) [24] as follows:

$${\mathrm{nmi}}^s=\mathrm{NMI}({\mathbf{j}}^s,{\mathbf{j}}^{s-1}).$$

(7)

The value ${\mathrm{nmi}}^s$ measures the statistical information shared between the cluster assignments ${\mathbf{j}}^s$ and ${\mathbf{j}}^{s-1}$, and takes values in the range $[0,1]$. It tells us how much knowing one of these clusterings reduces our uncertainty about the other. The higher the NMI, the more useful the information in ${\mathbf{j}}^s$ helps us to predict the cluster memberships in ${\mathbf{j}}^{s-1}$ and viceversa. In practice, this means that when the cluster assignments between two consecutive iterations are the same (up to the labelling), ${\mathrm{nmi}}^s=1$. On this basis, we propose to terminate the ICD algorithm when $|{\mathrm{nmi}}^s-1|<{\mathrm{THR}}_{\mathrm{stop}}$, ${\mathrm{THR}}_{\mathrm{stop}}$ being a user-specified threshold value. Furthermore, to speed up the procedure, we start to check the convergence of the cluster assignments only when the approximation of the similarity matrix is good enough. An approximation of matrix S implies that the degree of each datapoint is also approximated. Therefore, the ratio $r_{\mathrm{deg}}=\frac{\min (\tilde{\mathbf{d}})}{\max (\tilde{\mathbf{d}})}$ can be used to have an idea of the quality of the approximation [18], where $\tilde{\mathbf{d}}=C{C}^T{\mathbf{1}}_N$, and min and max denote the minimum and maximum element of a vector. In particular, the convergence of the cluster assignments begins to be monitored when $\frac{\min (\tilde{\mathbf{d}})}{\max (\tilde{\mathbf{d}})}>{\mathrm{THR}}_{\mathrm{deg}}$. From our experience ${\mathrm{THR}}_{\mathrm{stop}}={\mathrm{THR}}_{\mathrm{deg}}={10}^{-6}$ represents a good choice, which prevents termination of the ICD algorithm too early (with poor clustering performance), but also not too late (by selecting more pivots than needed). In this realm, a sensitivity analysis (the study is related to the dataset Three 2D Gaussians) of the proposed algorithm with respect to different threshold settings is depicted in Figure 1. In Figure 2, the trend of ${\mathrm{nmi}}^s$ as a function of the number of selected pivots is shown for the synthetic datasets analysed in this paper.

3.2. Choosing the Number of Clusters

The number of clusters k present in the data is not known beforehand and must be chosen carefully to ensure meaningful results. To tackle this issue, we exploit the theoretical fact that the multiplicity of the eigenvalue 1 of the Laplacian $L_n$ equals the number of connected components (i.e., clusters) in the graph. In other words, we use the eigen-gap heuristics [4], which unlike standard spectral clustering, in our case is computed using the $m\times m$ R matrix (see Equation (4)) rather than the original $N\times N$ Laplacian matrix. Furthermore, we consider an eigenvalue to have converged if $|{\widehat{\lambda }}_l-1|<{\mathrm{THR}}_{\mathrm{eig}}$. For simplicity, we set ${\mathrm{THR}}_{\mathrm{eig}}={\mathrm{THR}}_{\mathrm{stop}}={10}^{-6}$, which from our experiments, turned out to be a good choice. In Figure 3, we show through several examples that a meaningful value for k can be detected using only the information provided by the m selected pivots. However, it should be pointed out that the eigengap heuristic can fail in real situations when, due to some overlap between the clusters, the sharp decay of the eigenvalues of the ideal case quickly deteriorates. In this case, the Gershgorin circle theorem, which provides upper bounds on the eigenvalues of the Laplacian matrix, can be utilized to determine a meaningful interval for the number of clusters [25]. Another alternative to select the number of clusters, although more computationally demanding, could be the use of any internal cluster validity criterion in conjunction with the current cluster assignments.

The complete clustering algorithm proposed in this paper, which we call ICD-NMI, is summarized in Algorithm 1. Furthermore, a Matlab implementation can be downloaded from [26].

4. Experimental Results

In this section the outcomes of the experiments are presented. Given a dataset ${\left\{{\mathbf{x}}_i\right\}}_{i=1}^N$, with ${\mathbf{x}}_i\in {\mathcal{R}}^d$, we start by constructing a graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ where the N data points represent the vertices $\mathcal{V}={\left\{v_i\right\}}_{i=1}^N$, and their pairwise similarity $S_{ir}$ the weight of the edge between them $\mathcal{E}={\left\{S_{ir}\right\}}_{i,r=1}^N$. Throughout this paper, the radial basis function with parameter σ is taken as the similarity measure between two data points ${\mathbf{x}}_i$ and ${\mathbf{x}}_r$; i.e., $S_{ir}=W({\mathbf{x}}_i,{\mathbf{x}}_r)=\exp (-\frac{\left|\right|{\mathbf{x}}_i-{\mathbf{x}}_r{\left|\right|}_2^2}{2{\sigma }^2})$. For simplicity, the parameter σ is chosen based on the Silverman (the issue concerning the tuning of the bandwidth parameter is outside of the scope of the paper) rule of thumb [27]. To understand the behaviour of the proposed algorithm, we have performed simulations on a number of synthetic datasets that are commonly used to benchmark (the majority of the datasets has been downloaded from http://cs.joensuu.fi/sipu/datasets/) clustering algorithms. In Figure 3, the eigenvalues ${\widehat{\lambda }}_l$ that are estimated after selecting the last pivot are illustrated. We can notice how, in general, the number of eigenvalues that have converged to 1 up to threshold ${\mathrm{THR}}_{\mathrm{eig}}$ reflect the true number of clusters present in the data. Figure 2 shows the working principle of the stopping criterion introduced in Section 3.1: the value nmi${}^s$ converges to $1-{\mathrm{THR}}_{\mathrm{stop}}$ after a certain number of iterations. In Figure 4, the detected clusters are depicted together with the selected pivots. In all the datasets, a meaningful clustering result has been obtained, and the pivot elements represent the clustered structure of the related data distribution well.

Table 1. Comparison with other incomplete Cholesky decomposition (ICD)-based methods on toy datasets. Different algorithms are contrasted in terms of the number of selected pivots and clustering quality, in the case of three synthetic datasets. We can notice how the proposed technique obtains a high clustering performance in terms of Adjusted Rand Index (ARI), and at the same time it requires a small number of pivots. (Boldface numbers indicate the best performance.)

Dataset	Algorithm	Number of Pivots	ARI
Two spirals	ICD-NMI	$\mathbf{88}$	1
	[22]	129	1
	[18]	94	1
Three rings	ICD-NMI	$\mathbf{71}$	$\mathbf{1}$
	[22]	93	$0.85$
	[18]	87	$0.87$
Three 2D Gaussians	ICD-NMI	9	1
	[22]	21	1
	[18]	9	1

reports a comparison between the proposed method and two other clustering algorithms based on the incomplete Cholesky decomposition, namely algorithms (for a fair comparison, we report the results of the algorithm that does not use the $L_1$ regularization) [18,22]. The comparison concerns both the number of selected pivots and the match between the detected clusters and the true groupings, as measured by the Adjusted Rand Index ([28]). The results indicate that the proposed algorithm, namely ICD-NMI, requires a minor number of pivots, resulting in a sparser spectral clustering method with comparable or higher accuracy.

Figure 5 shows the convergence of the cluster assignments in the analysis of a number of large real-life databases. The results confirm the main observation that we have made in the case of the synthetic datasets; that is, the proposed technique requires a limited number of pivots (in the case of the poker dataset, the method stopped because it reached the maximum number of iterations without converging) to perform the clustering.

Table 2. Comparison with k-means and the Clustered Nyström method on three large real-life datasets Performance of different approaches in terms of runtime, Silhouette and DB criterion (average values over ten randomizations). (Boldface numbers indicate the best performance).

Algorithm	Covertype [31]			GalaxyZoo [32]			PokerHand [33]
	N		d	N		d	N		d
	$\mathbf{581}\mathbf{,}\mathbf{012}$		54	$\mathbf{667}\mathbf{,}\mathbf{944}$		9	$\mathbf{1}\mathbf{,}\mathbf{025}\mathbf{,}\mathbf{010}$		10
	Sil	DB	time (s)	Sil	DB	time (s)	Sil	DB	time (s)
ICD-NMI	$\mathbf{0}.\mathbf{93}$	$\mathbf{0}.\mathbf{14}$	$14.61$	$0.55$	$\mathbf{0}.\mathbf{55}$	$521.76$	$\mathbf{0}.\mathbf{16}$	$3.70$	$3408.5$
k-means [34]	$0.16$	$1.30$	$\mathbf{5}.\mathbf{57}$	$0.54$	$1.36$	$\mathbf{2}.\mathbf{89}$	$0.12$	$\mathbf{2}.\mathbf{20}$	$\mathbf{83}.\mathbf{56}$
Clustered Nyström [35]	$0.06$	$2.98$	$218.48$	$\mathbf{0}.\mathbf{56}$	$0.94$	$308.91$	$0.11$	$2.33$	$650.89$

reports a comparison with the k-means algorithm [1] used as baseline and an alternative low-rank method based on the Nyström approximation (the size of the subset should be less than 500 points to not get out-of-memory error). The cluster quality is measured in terms of the Silhouette index [29] and the Davies–Bouldin (DB) criterion [30], and the computational burden in terms of runtime. The results indicate that the proposed approach, although slower than k-means, reaches a higher clustering performance compared to the alternative approaches, in general.

5. Computational Complexity and Memory Requirements

In this section, the computational burden of the proposed method is analysed in more detail. In Algorithm 1, two main parts are present: (i) the computation of the current ICD approximation at each step, which scales linearly with respect to the total number of data points N; (ii) the steps involved in the calculation of the NMI between current and previous cluster assignments, all of which depend linearly on N. This reasoning is supported by Figure 6, where the runtime of the proposed approach is analysed by using one of the synthetic datasets mentioned earlier. It can be evinced how algorithm ICD-NMI scales linearly, i.e., has complexity $O\left(N\right)$.

Regarding the memory load, the proposed method has low requirements, because only matrices of size $N\times m$ and $m\times m$ need to be constructed. Furthermore, as we have shown, in general the algorithm selects a low number of pivots, even in case of very large datasets, meaning that $m\ll N$.

6. Conclusions

In this paper we have introduced a new stopping criterion for the incomplete Cholesky decomposition (ICD). The proposed criterion terminates the ICD when the change in the cluster assignments is below a given threshold, as measured by the normalized mutual information between consecutive partitionings. This allows the selection of a limited number of pivots compared to existing techniques, and at the same time, achieves good clustering quality, as shown for a number of synthetic and real-world datasets. Furthermore, the number of clusters is selected efficiently based on the eigengap heuristic computed on a small $m\times m$ matrix, with $m\ll N$. Finally, a sensitivity analysis demonstrated how specific threshold values can influence the desired cluster quality, sparsity, and computational burden. Future work may be related to exploiting memory mapping to handle bigger datasets that do not fit in memory.