Improving Spectral Clustering Using Spectrum-Preserving Node Aggregation

We first construct a standard k-NN graph $G$. Then, based on the node proximity measure proposed in [13], the spectral similarity of two nodes $p$ and $q$ can be calculated as:

where $\mathbf{X}:=(\mathbf{x}^{(1)},\dots,\mathbf{x}{{}^{(K)}})$ is obtained by applying Gauss-Seidel relaxation to solve ${L}_{G}\mathbf{x}^{(i)}=0$ for $i=1,\dots,K$, starting with $K$ random vectors. We aggregate the nodes with high spectral similarity to form a few spectral-representative nodes to reduce the graph size while preserving the spectrum of the original graph. By aggregating nodes based on spectral similarity, the reduced graph can best represent the original data set in the sense of minimizing the structural distortion [12], as shown in Figure 2.

Then the standard spectral clustering is performed on the aggregated nodes. Spectral clustering algorithm needs to perform a very computational expensive eigen-decompistion procedure with $O(n^{3})$ time complexity to calculate the first $k$ non-trivial eigenvectors of the graph Laplacian, where $n$ is number of nodes. By using spectral-representative nodes to represent the global structure of the original data set, number of nodes $n$ can be reduced and thus leads to speedup of eigen-decomposition. If the desired size of node set is not reached, the nodes can be further aggregated layer by layer by utilizing a multi-level aggregation scheme [8]: given the graph Laplacian ${L}_{G}$ and the mapping operators from the finest level $1$ to the coarsest level $r$, ${L}_{R}=\mathbf{H}_{G}^{R}{L}_{G}\mathbf{H}_{R}^{G}$, where $\mathbf{H}_{G}^{R}=\mathbf{H}_{1}^{2}\mathbf{H}_{2}^{3}\cdots\mathbf{H}_{r-1}^{r}$ and $\mathbf{H}_{R}^{G}=\mathbf{H}_{2}^{1}\mathbf{H}_{3}^{2}\cdots\mathbf{H}_{r}^{r-1}$

However, the goal of data clustering is to find cluster membership of original samples in the data set rather than the clusters of the pseudo aggregated nodes. In this paper, we propose to map the cluster membership back from the pseudo aggregated nodes to the original real data points. Specifically, we build a correspondence table using the mapping operators of each layer to associate each original sample to its aggregated nodes in the final layer. For each original data points, we assigning it to the cluster as its corresponding aggregated node. The complete algorithm flow has been shown in Algorithm 1.

One drawback of spectral clustering is that it is highly sensitive to noisy nodes in the graph, which limits the capability to accurately discover clusters: if a few noisy nodes form a narrow bridge between two densely connected communities, the algorithm tends to report the two communities plus the noisy nodes as a single community.

Relying on the very strong capability of spectrum-preserving pseudo nodes in preserving the spectrum of the graph Laplacian and global manifold of the data set, almost all the original nodes including the noisy nodes can be removed together. For example, for the MNIST data set with $70,000$ nodes, only $109$ spectral-representative nodes are enough for representing the global structure of the data set, which means $99.84\%$ of nodes can be removed so that the noise nodes won’t exist in the aggregated graph. As a result, the clustering accuracy improves from $64.20\%$ to $82.94\%$ for the MNIST data set.

Even though other approximate spectral clustering methods can also significantly reduced to node set size with a small amount of representative nodes, however, without using spectral analysis to choose spectrally-critical nodes, their representative nodes are not able to truthfully encode the spectrum of original graph Laplacian. So their clustering accuracy gains from denoising are counteracted with the loss of spectrum information.

The computational complexity of spectrum-preserving node reduction is $O(|E_{G}|log(|V|))$, where $|E_{G}|$ is the number of edges in the original graph and $|V|$ is the number of nodes. The computational complexity of reduced standard spectral clustering is $O(P^{3})$ where $P$ is the number of aggregated nodes. The complexity of cluster membership retrieving is $O(N)$, where $N$ is the number of samples in the original data set.

One mid-sized data set (USPS), one large data set (MNIST) and one very large data set (Covtype) are used in our experiments. They can be downloaded from the UCI machine learning repository ²²2https://archive.ics.uci.edu/ml/ and LibSVM Data³³3https://www.csie.ntu.edu.tw/ cjlin/libsvmtools/datasets/: USPS includes $9,298$ images of USPS hand written digits with $256$ attributes; MNIST is a data set from Yann LeCun’s website⁴⁴4 http://yann.lecun.com/exdb/mnist/, which includes $70,000$ images with each of them represented by $784$ attributes; Covtype includes $581,012$ instances for predicting forest cover type from cartographic variables and each instance with $54$ attributes is from one of seven classes.

We compare the proposed method against both the baseline and the state-of-the-art fast spectral clustering methods including: (1) the standard spectral clustering algorithm [9], (2) the Nyström method [7], (3) the Landmark-based spectral clustering (LSC) method that uses random sampling for landmark selection [5], and (4) the KASP method using k-means for centroids selection [6]. For fair comparison, we use the same parameter setting in [5] for compared algorithms: the number of sampled points in Nyström method ( or the number of landmarks in LSC, or the number of centroids in KASP ) is set to 500.

Clustering accuracy ($ACC$) is the most widely used measurement for clustering quality [5, 4]. It is defined as follows:

where $N$ is the number of data samples, $y_{i}$ is the ground-truth label, and $c_{i}$ is the label generated by the algorithm. $\delta(x,y)$ is a delta function defined as: $\delta(x,y)$=1 for $x=y$, and $\delta(x,y)$=0, otherwise. $map(\bullet)$ is a permutation function which can be realized using the Hungarian algorithm [14]. A higher value of $ACC$ indicates better clustering quality.

Table 1 shows the clustering accuracy results of compared methods and our method with node reduction ratios of $5X$, $10X$ and $50X$. The runtime of the eigen-decomposition and k-means steps are reported in Table 2. As observed, the proposed method can consistently lead to dramatic performance improvement, beating all competitors in clustering accuracy across all the three data sets: our method achieves more than $10\%$ accuracy gain on USPS, $11\%$ gain on MNIST and $15\%$ gain on Covtype over the second-best methods; for the USPS and MNIST data sets, our method achieves over $17\%$ and $18\%$ accuracy gain over the standard spectral clustering method, respectively. The superior clustering results of our method clearly illustrate that spectrum-preserving concise representation can improve clustering accuracy by removing redundant or false relations among data samples.

As shown in Table 3, the $50X$ reduced graphs generated by our framework have only $138$, $1182$ and $8192$ nodes for USPS, MNIST and Covtype data sets, respectively, thereby allowing much faster eigen-decompositions. As shown in Fig. 3 and Fig. 4, with increasing node reduction ratio, the proposed method consistently produces high clustering accuracy. For the very large data set Covtype, our method is the only one that enables us to accelerate spectral clustering algorithm without loss of clustering accuracy.