Deep Linear Coding for Fast Graph Clustering

1 Introduction

Clustering algorithms [Jain et al., 1999] have been widely applied in AI problems: pattern recognition, computer vision, information retrieval, bioinformatics. Like other unsupervised learning algorithms [Barlow, 1989], it is purely data-driven, and therefore, requests least supervised knowledge. There are a wide variety of clustering methods that target at different problems or application scenarios [Jain et al., 1999]. The most popular ones are K-means [Hartigan and Wong, 1979] and spectral clustering [Ng et al., 2002; Von Luxburg, 2007]. K-means keeps updating the cluster centers by current cluster assignments and then updating the assignments by the nearest neighbor rule. Although it only ends up with local solutions, its fast implementation makes it

∗This research is supported in part by the NSF CNS award 1314484, ONR award N00014-12-1-1028, ONR Young Investigator Award N00014-14-1-0484, and U.S. Army Research Office Young Investigator Award W911NF-14-1-0218.

Yun Fu

Department of ECE, College of CIS Northeastern University Boston, MA 02115, USA {yunfu}@ece.neu.edu

a fundamental tool in data analysis. However, K-means suffers from strong assumptions on the data, and local optimum.

Differently, spectral clustering has a solid theoretical foundation [Chung, 1997], and is able to reach a global solution. Besides, it has close relations with other methods such as graph cut [Shi and Malik, 2000], random walk [Meila and Shi, 2001], and thus is more intuitive and understandable. In addition, the non-parametric property and many fast implementations make it very suitable for large-scale data analysis under complex distributions [Fowlkes et al., 2004]. However, the time-consuming graph construction and eigendecomposition make it still inferior to K-means in terms of speed. Note there are also variations of K-means such as kernel K-means that can identify non-linear structure; however, they are proved equal to spectral clustering under mild conditions [Dhillon et al., 2004].

Recently, deep structure has been widely applied in learning problems [Hinton et al., 2006; Bengio, 2009] as it can extract better representations for learning tasks [Bengio et al., 2013]. It is especially useful for clustering tasks since it can disentangle explanatory factors in a low-dimensional non-linear feature space in unsupervised fashion. In addition, the greedy layerwise training strategy [Bengio et al., 2007] and improvement of computing hardware make the fast implementation of deep methods possible [Dean et al., 2012]. Notably, there are a few deep methods proposed recently for clustering tasks [Song et al., 2013; Huang et al., 2014; Tian et al., 2014]. In this paper, we propose a novel Deep Linear Coding (DLC) scheme for fast data clustering. Inspired by the common objective of K-means and spectral clustering methods, we jointly learn a linear feature transform and codings for the test data under single-layer marginalized denoising autoencoder framework, which can minimize the reconstruction error of the data/similarity graph. In addition, we propose to refine the learned representations by feeding them to the next layers and repeat the joint learning procedure. Experimental results on clustering tasks demonstrate the superiority of our method in terms of speed and accuracy.

2 RelatedWork

Spectral clustering utilizes both pairwise similarity graph and spectral theory to cut the graph with the minimal loss, and therefore is usually referred as graph clustering. The advantage over conventional K-means is the locality awareness due to the non-parametric formulation of graph. In the original formulation of spectral clustering, a pairwise sparse graph is built first based on the kNN rule, where non-zero values in the graph are Gaussian similarities between two samples. Then the graph is normalized and its first several smallest eigenvectors's row space is considered as the new representations in the embedding space. Finally K-means is implemented on the new representations. Although it can identify the NonGaussian data distributions, the graph construction and followed eigen-decomposition are not cheap, which have the time complexity of O(kn2 ) and O(n3 ), respectively, where k is the number of neighbors, and n is the number of samples.

A straightforward way to speed up the problem above is to exploit fast kNN implementation and sparse eigendecomposition [Chen et al., 2011]. Differently, Nystrom method [Fowlkes et al., 2004] samples a few data, and builds a dense graph containing the connections only between sampled data and all data. Then eigenvectors of the original graph can be approximated by this substantially small graph. Recently, landmarks based methods either build a landmarksonly graph [Yan et al., 2009] or a factor matrix of the original graph [Chen and Cai, 2011], and significantly save the running time of eigen-decomposition. However, none of them can get rid of eigen-decomposition, and some of them may even sacrifice certain performance due to the approximation operations [Yan et al., 2009]. Different from them, our method enjoys the formulation of spectral clustering, but excludes the time-consuming eigen-decomposition operations.

Recently, deep learning methods have been applied on data clustering. One of the pioneer work adds the pairwise constraint between data samples and current affiliated centers to the loss function of the deep autoencoders [Song et al., 2013]. A more recent work uses the deep sparse autoencoders to explore the representations of the normalized similarity graph, and proves that the deep model works similarly to the spectral clustering on the graph reconstruction [Tian et al., 2014]. Finally, both locality constraint and group sparsity are introduced to RBMs for the purpose of clustering [Huang et al., 2014]. However, all these methods do not explicitly consider the efficiency, especially for large-scale data. Thus, they may suffer from extremely long running time in practice.

3 Methodology

3.1 Background andMotivations

The common idea of K-means and spectral methods is to reconstruct the data/graph and use the indicator vector/matrix of the reconstruction as the new feature for clustering:

where X is the data samples (K-means) or normalized affinity graph (spectral clustering), Φ is the reconstruction function, Σ is approximate cluster centers (K-means), or singular values diagonal matrix (spectral clustering), and A is the indicator vector/matrix. In K-means, the objective function essentially minimize the average square distance between samples and their affiliated center, where indicators play the roles of reconstruction coefficients. On the other hand, spectral clustering manages to find a low-rank approximation of the normalized affinity graph, and the eigenvectors are the indicators.

In our model, we also propose to find a new representation of the data with minimal reconstruction loss that can be used as the indicators for clustering. Recently, linear coding has been widely used in high level feature extraction and data representation [Lee et al., 2006; Yang et al., 2009]. Specifically, it has been adapted in the decomposition of affinity graph for fast spectral clustering [Chen and Cai, 2011]. Typically, the objective function of linear coding aims at minimizing the following reconstruction loss:

where D is the dictionary, A is the learned codes, and R(A) is a regularizer that encourages small magnitude or sparse solutions of A. A popular choice of R(A) is l1 norm that induces sparsity on the feature vectors. However, for data clustering, especially large-scale problems, the weakness is obvious: 1) the solution to Eq. (2) is computationally expensive due to the non-smooth property of the objective function; 2) the sparse kernel approximation introduced in [Chen and Cai, 2011] trades the approximation accuracy for speed.

In the proposed model, we manage to address the two problems above, and provide a fast coding scheme appropriate for large-scale data clustering. We introduce a linear transform matrixW for the coding part to compensate for the large reconstruction loss between X and DA due to the induced sparsity. In addition, our method is still able to provide low-rank approximation of the affinity graph without time consuming eigen-decomposition, which significantly saves running time. Next, we detail the single-layer linear coding scheme.

3.2 Method Details

Given a set of data X ∈ Rd×n , where d is the dimensionality of the data and n is the number of data samples, the proposed Single-layer Linear Coding (SLC) scheme can be written as:

where W ∈ Rd×d is the linear transform function, D ∈ Rd×m is the dictionary, A ∈ Rm×n is the codes for dataset X, λ is the weight of the regularizer, and in most cases n > m, n ≫ d. In our problem, D is also referred as a set of m landmarks, and fixed during the optimization. Therefore, the proposed model manages to solve two variables at the same time; however, to the best of our knowledge, such problem does not have a closed-form solution. In fact, the objective in Eq. (3) is convex in either W or A, but not in both. Therefore, we resort to an iterative solution that is able to solve one unknown variable at a time by fixing the other.

First, suppose we have already obtained a dictionary D and corresponding codes A for each data sample in X, then the original SLCmodel is converted to:

where ˜X = DA represents the reconstructed data samples through learned dictionary and codes. Intuitively, Eq. (4)

Input: Dataset X, number of landmarks m, number of nearest neighbor k, threshold ϵ.

Output: Codes A for X

• 1 Find m landmarks of X by K-means, and assign to D.
• 2 Compute the sparse codings by kernel approximations:

[A]ij(1 ≤ i ≤m, 1 ≤ j ≤ n) = φ(xi,xj) ∑u φ(xu,xj) , xu is within the first k nearest neighbors of xj in D, xi ∈ {xu}, and φ(·, ·) is the Gaussian kernel with bandwidth σ.

3 for t = 1 to T do

• 4 Fix dictionary D and codes A, and update linear transformWby Eq. (4).
• 5 Fix linear transformWand dictionary D, and update codes A by Eq. (6).
• 6
• If ‖X-WDA‖2F < ϵ, terminate the algorithm.

7 end

Algorithm 1: Algorithm of Single-layer Linear Coding.

manages to find a linear transform (rotation) by which the reconstructed data ˜X can match the original data, despite of the limit basis in D and sparse coefficients from A. Obviously, this problem can be converted to ordinary least square problems [Hastie et al., 2009] with closed-form solutions as:

Second, since we have already found the linear transform W, we could achieve the new representation of the dictionary ˜D = WD and update the coding in the following way:

which is essentially a ridge regression problem, with λ as the balancing parameter. The closed-form solution for this problem is:

where I is a m × m identity matrix. The introduced regularizer is able to suppress arbitrarily large coefficients in A and avoid over-fitting. The updated coding and dictionary can be used again to learn the new linear transform. We name this algorithm as Single-layer Linear Coding (SLC), which is summarized in Algorithm 1.

3.3 Relations to ExistingMethods

Marginalized Denoising Autoencoder

People might be curious why the proposed SLC model is appropriate for feature learning and data clustering. Here we elaborate a few connections with existing methods, and therefore highlight the advantage of SLC.

Recall in the first step of SLC algorithm, we solve Eq. (4) to find a linear transform, which is able to reconstruct the original input by perturbed samples DA. This is essentially a single-layer denoising autoencoder using DA as the corrupted data. Arbitrary noises can not guarantee a stable performance, but in general, more reasonable noisy samples yield a much better result. However, this will add tremendous computational burden when the noisy patterns go to infinity.

Recently, a marginalized denoising autoencoder has been proposed to solve the computation problem above [Chen et al., 2012]. Instead of exhaustedly sampling contaminated data, they compute the empirical expectation over the original data X, and find the linear transform in the following

where ΛP (ΛQ) is d×d matrix encoding joint survival ratios of two single features from xi and ˜xi (both from ˜xi), and ⊗ is the element-wise multiplication. Although the proposed SLC does not explicitly model the marginalization procedure, the following the theorem demonstrates that SLC is also a singlelayer marginalized denoising autoencoder:

Theorem 1 Problem stated in Eq. (4) is a single-layer marginalized denoising autoencoder, where factor matrix Q is the empirical expectation of the covariance matrix of landmarks up to a constant c, and P is the empirical expectation of the covariance matrix of landmarks up to a constant cW.

Proof. For Qwe can easily check that

where ai is the i-th column vector in A, and c is a constant compensating for different column sizes between D and DA. Similar to Eq. (8), Eq. (9) is the empirical expectation of DD⊤ with AA⊤ encoding the joint survival probability of every two features. Different from Eq. (8) that uses different survival probability for features from the same data sample, ai assigns the same probability to all features from a single data sample. For P we have the following deductions:

where we take advantage of the fact that X≈WDA in the inner loop of Algorithm 1. Similar to Q, P is the empirical expectation of covariance matrix of D up to a constant factor matrix cW. This completes the proof.

Spectral Clustering

From the reconstruction point of view, spectral clustering attempts to minimize the following graph approximation loss with a low-rank constraint:

where ˜G is the approximate graph, r is a predefined matrix rank. According to Eckart-Young-Mirsky theorem [Eckart and Young, 1936], its solution is ˜G = UΣU⊤, where U ∈ Rn×r are the first r eigenvectors of graph G, and Σ is a matrix with corresponding eigenvalues on the diagonal. Recall the loss function in Eq. (3), we also try to minimize the reconstruction error, but on the original data X. Next proposition shows that the proposed SLC also seeks a low-rank approximation of the linear similarity graph X⊤X ∈ Rn×n .

Proposition 1 The objective function in Eq. (3) seeks for a low-rank approximation of linear similarity graph X⊤X in the sense of X⊤X≈A⊤˜ΣA, and rank(A⊤˜ΣA) ≤ min{m, d, n}, where ˜Σ = D⊤W⊤WD.

We can see that the solution of SLC is also a low-rank approximation of linear kernel similarity graph X⊤X, and its rank depends on the values of m, d and n. In most cases, n is the largest one, especially in the large-scale case. Therefore, SLC essentially provides a rank (≤ min{d, m}) approximation of X⊤X, which works in a similar way as spectral clustering.

3.4 Deep Layerwise Feature Learning

Recent works on representation learning take advantage of deep structure to build discriminative features [Bengio et al., 2013]. They usually use RBMs or autoencoders as the basic building blocks to learn a deep structure, and employ greedy layerwise training to obtain a better initializations for fine tuning. Finally either hidden layers or supervised layer on top will be used for classification tasks. The insight behind is deep structure can gradually refine the features from coarse to fine, and layerwise training helps to find better local solutions for the non-convex objective [Bengio et al., 2007].

In the proposed SLC model, features can be refined in a similar layerwise way, meaning the learned features A can be considered as the input features of the second layer, and is able to build new landmarks. Suppose the l-th layer's coding is Al, dictionary is Dl, and linear transform is Wl, then we first update the dictionary in the (l + 1)-th layer by Dl+1 = K-means(Al). Second, we solve Wl+1 by Wl+1 = ΨW(Dl+1,Al), where ΨW indicates Eq. (5). Finally, we update the (l + 1)-th layer's coding Al+1 = ΨA(Wl+1, Dl+1, Al), where ΨA indicates Eq. (7). We summarize such layerwise feature learning procedure in Algorithm 2, and name it Deep Linear Coding (DLC) in this paper.

Input: Dataset X, and the number of clusters.

Output: Codes AL for dataset X, and cluster labels of

each sample.

• 1 for l = 1 to L do
• 2 Use Algorithm 1 to learnWl,Dl and codes Al
• 3 Set Xl+1 =Al
• 4 end
• 5 Run K-means on the column space of AL, and obtain the cluster labels.

Algorithm 2: Algorithm of Deep Linear Coding (DLC).

3.5 Time Complexity

The time cost of DLC mainly includes four parts:

1. Find landmarks D through K-means,
2. Find k nearest neighbors fromD for each sample,
3. Solve the ordinary least square problem in Eq. (4),
4. Solve the ridge regression problem in Eq. (6).

First, K-means usually takes time of O(sdmn), where s is the number of iterations of K-means. In our experiments, we found that a small number of iterations, e.g., 10, will provide good results. Therefore, it is less expensive compared to conventional K-means algorithms for clustering purpose. Second, the brute-force way of kNN search usually takes time of O(kmn); however, many off-the-shelf algorithms can substantially speedup this process, e.g., FLANN library [Muja and Lowe, 2014]. Third, the ordinary least square problem includes a few matrix multiplications, and a matrix inverse operation, and the total running time is O(d2 (d + n)). Finally, similar to the last step, the time complexity of ridge regression is O(m(2md +m2 + dn)). Therefore, the total time complexity for SLC is approximately equal to:

where T is the number of iterations in SLC. Then, total time cost of DLC is: LtSLC, where L is the number of layers.

4 Experimental Results

In this section, we evaluate the proposed DLC method through data clustering on seven benchmark datasets in terms of both accuracy and running time. Dataset details are listed in Table 1.

4.1 Datasets and Configurations

Corel The dataset has been widely used in computer vision and image processing. We use its subset from [Chen et al., 2011] as our test, where 2074 images, 144 features including shape, texture, color, are chosen for evaluations.

Coil20 An object image database with 20 different objects. Each of them has 72 images under different view point, with 5 degree as the interval. All images are resized to 32×32 pixels and we use the raw pixels as our features.

YaleB This database is popular in face recognition algorithms evaluations, including 38 people, 64 lighting conditions, and 9 poses. A subset of 10 people, 5850 faces are adopted for data clustering. 1200 features are extracted for each image.

Pendigit This is a handwritten digit data set including 10992 samples from 44 writers. A sampled coordination information (16 features) is taken for the feature.

Letter The dataset consists of 26 capital letters in the English alphabet and 16 character image features are selected for clustering task.

Mnist Another handwritten digits benchmark dataset widely used in clustering evaluations. We use raw pixels including 784 features in the evaluations.

Covtype A large scale scientific dataset containing cartographic variables for predicting forest cover type. Each sample has 54 attributes, and in total there are over 580k samples.

Note for all datasets, each data sample is normalized to have unit length. We set the number of neighbors in kNN search at 5, and the number of landmarks in the first and second layers at 1000 unless otherwise specified. In addition, we set both the balancing parameter λ and Gaussian kernel bandwidth σ at 1. To balance the performance and speed, the number of iterations in each layer is set to T = 5. In all tests, we run our algorithm 20 times, and average results are reported. For all compared methods, we strictly follow their recommended configurations. Finally, we introduce two performance measurement in our evaluations: clustering accuracy and normalized mutual information (NMI).

Clustering accuracy is the average performance of label matching results between resulted labels and ground truth labels, which can formulated as: ∑i (yi == f(li))/n, where f is a mapping function that maps category label to different cluster labels. Since clustering is an unsupervised process, we need f to work as a permutation operation, and maximize this fraction as the final clustering accuracy.

Normalized mutual information (NMI) measures the mutual information entropy between resulted cluster labels and ground truth labels, followed by a normalization operation which guarantees that NMI ranges from 0 to 1. Mathematically, it can be written as:

where ni and nj denotes the number of data in cluster i and category j, and ni,j denotes the number of data in both cluster i and category j. Therefore, if the data are randomly partitioned, NMI is inclined to 0.

4.2 Experimental Results

Comparisons with Spectral Methods

First, we compare our method with state-of-the-art graph clustering methods, as ours enjoys the similar formulation of these methods; however, the linear coding scheme is able to significantly speed up the process. We compare with the following methods in the experiments:

Spectral Original spectral clustering method with Gaussian similarity kernel. Sparse kNN graph is used for graph construction, and k is set to a small number, following the conventional configuration [Von Luxburg, 2007].

KASP A divide and conquer based fast spectral clustering method proposed in [Yan et al., 2009], which uses K-means for landmarks. For efficiency and a fair comparison, we take a Matlab implementation of the multi-way partition version in the evaluations.

Nystrom It uses sampled data to approximate the original graph, and the eigen-decomposition, which saves substantial time. We choose the Matlab implementation with orthogonalization as our evaluation method [Chen et al., 2011].

LSC-K Landmark-based spectral clustering using K-means for landmark-selection [Chen and Cai, 2011]. It takes advantage of graph factorization for fast eigen-decomposition.

Results from Table 2 and 4 demonstrate that our method provides comparable accuracy (Pendigit, Mnist, Covtype) or even better accuracy (Corel, Letter) with reduced running time. The advantage of our method lies in the flexible feature dimensions and linear coding scheme instead of time consuming eigen-decomposition. Specifically, the relative high dimension features fed to K-means in the last step are favored by the natural scene/color images. However, in most of fast implementations of spectral methods, the final feature dimensions for K-means usually depend on the number of clusters. In addition, the linear coding scheme substantially reduces the time complexity and makes large-scale clustering easy. Compared to the original spectral clustering, our method is 1500 times faster, and compared to Nystrom, ours only needs less than half of its running time, but with large improvement.

Comparisons with Deep Methods

Second, since our method also utilizes the deep structure to further refine the representation for clustering tasks, we compare with the most recent state-of-the-art deep clustering methods. The details of them are listed below:

AEC A deep autoencoder with compactness constraint added on the top layer, which is specifically tailored for clustering tasks [Song et al., 2013].

LDR A deep sparse autoencoder to refine the normalized affinity graph, followed by a K-means clustering [Tian et al., 2014]. We evaluate on a Matlab implementation with recommended configurations.

DEN A deep structure with RBM as building blocks, and takes advantage of locality preserving constraint and group sparsity for clustering purpose [Huang et al., 2014].

From Table 3, we can see that the proposed method is significantly faster than other competitors, while achieves comparable performance. The main reason is our method does not need time-consuming back propagation, pre-training and fine tuning techniques that are frequently used in the deep approaches. Admittedly, those learning tricks are critical in learning deep non-linear features; however they are too expensive in fast clustering tasks. In addition, the clustering tasks usually prefer transductive learning fashion, and the inductive model learned from deep methods seems too "heavy" for the problem.

Model Discussions

There are a few model parameters to be tuned in DLC: number of landmarks and number of layers in the deep structure. To find the appropriate settings, we conduct two experiments by setting one parameter fixed while changing the other.

First, we experiment by Single-layer Linear Coding (SLC) scheme and vary the number of landmarks from 100 to 1500, which is shown in Figure 1. In each subfigure, "Layer-1" means the results of SLC, and the Y-Axis illustrates the clustering accuracy or running time. Apparently, more landmarks takes more running time, but it also improves the final clustering performance. Without loss of generality, we set the number of landmarks in the first layer at 1000, which also provides acceptable performance, and add the second layer on top to further refine the feature. In four subfigures, we use "Layer-

2" to indicate such settings. It can be seen that a moderate number of landmarks leads to better results. Thus, we still set the number of landmarks in this layer at 1000. Although we may obtain better results by other settings, the current ones have already been comparable with existing methods.

Second, we conduct experiments to find out the appropriate number of layers used in DLC. Similar to last experiment, we set the the number of landmarks in each layer at 1000, and gradually add the layer of the deep structure. Clustering accuracy results on a few datasets are shown in Figure 2. From this result, we can conclude that a two-layer DLC is a good choice in terms of both accuracy and time cost.

Finally, since DLC is iteratively solved in two subproblems, and there are no closed-form solutions, we need to guarantee the objective is monotonously decreased. To this end, we experiment on Corel and YaleB datasets with SLC and a two-layer DLC, and show the objective values in different iterations in Figure 3. Note in this experiment value in the X-Axis indicates the number of iterations for both SLC and DLC. Clearly, the objective values are gradually decreased, and a deeper model can significantly speed up this process.

5 Conclusions

In this paper, we proposed a novel deep linear coding scheme for fast graph clustering. Different from previous methods either relying on eigen-decomposition or time consuming deep autoencoders, our method jointly learned a linear transform and codings at the same time, and utilized deep structure to further refine the discriminative features. Extensive evaluations on seven benchmark datasets demonstrated the effectiveness of our methods, especially for large-scale data.