Attributed Subspace Clustering

1 Introduction

Representation-based subspace clustering is to partition data points into their respective low-dimensional subspaces by finding effective self-representations [Vidal and Favaro, 2014]. It assumes that every data point in a union of subspaces can be represented as a linear combination of other data points. Due to the insensitivity to initialization and easy-to-solve with standard linear algebra [Liu et al., 2014], the representation based subspace clustering has been widely used in computer vision and pattern recognition [Rao et al., 2010; Liu et al., 2013; Zhou et al., 2014].

∗Corresponding author

Recently, various self-representation based methods have been proposed [Vidal and Favaro, 2014; Wu et al., 2015; Zhang et al., 2017]. The sparse subspace clustering (SSC) [Elhamifar and Vidal, 2009] seeks the sparse solution of selfrepresentation, which tends to be block diagonal. The lowrank representation (LRR) [Liu et al., 2010] aims to preserve low-rank data structure. The least squares regression (LSR) [Lu et al., 2012] uses grouping effect for modeling correlation structure of data and is more efficient than SSC and LRR. The correlation adaptive subspace segmentation (CASS) [Lu et al., 2013] simultaneously performs automatic data selection and groups correlated data, which can adaptively balance SSC and LSR. Based on LSR, the smooth representation (SMR) [Hu et al., 2014] incorporates a weight matrix that measures the spatial closeness of data. Given a dataset with multiple types of features, [Cao et al., 2015] proposed a diverse multi-view subspace clustering (DiMSC) which learns a complementary representation shared by multiple features. [Zhang et al., 2017] then proposed latent multi-view subspace clustering (LMSC) method, which clusters data points with latent representation and simultaneously explores underlying complementary information from multiple views. With the utilization of prior information, NNLRR [Fang et al., 2015] encodes label information with graph-based regularization to seek low-rank and sparse representation simultaneously with nonnegativity constraints. Later, LRRADP [Wang et al., 2018] was proposed by using adaptive distance penalty to construct an affinity graph, which enforces the representations of every two consecutive neighboring data to be similar.

These representation-based approaches, which incorporate regularization terms or prior information for more accurate learning, all tend to intuitively utilize the features of original data as a whole and learn a single self-representation. However, real data are complex and consist of multiple subfeatures or attributes [Changpinyo et al., 2013; Ou et al., 2015]. As shown in Figure 1, the face images consist of multiple attributes including facial expressions, ethnicity and shadows, and the cat images have different rotations and shapes. Since each attribute represents one aspect of data and contains specific information, exploring diverse and complementary information among multiple attributes is of vital importance to learn a more accurate self-representation.

Moreover, the exploration of attributes may lead to multiple clustering solutions that provide a more comprehensive understanding of data. Taking the Yale in Figure 1 as an example, current subspace clustering methods can only obtain one clustering solution based on the single selfrepresentation, i.e., grouping all face images of a person into one group, which is often rather limited to depict and understand the dataset adequately. However, with multiple selfrepresentations corresponding to attributes (e.g. shadow and expression), the face images could be clustered as happy/dull expression, with/without glass or left/right-lit. In fact, the effectiveness of attribute exploration has also been demonstrated in some other research fields, including network embedding, ordinal embedding, information retrieval and so on [Niu et al., 2014; Liao et al., 2018; Mazaheri et al., 2018].

In this paper, we propose an innovative representation based subspace clustering approach, called Attributed Subspace Clustering (ASC), which interprets data from different perspectives and obtains multiple clustering solutions by leveraging the data's multiple attributes. Specifically, ASC learns multiple self-representations based on latent representations which are drawn from the original data. Utilizing Hilbert-Schmidt Independence Criterion (HSIC) [Gretton et al., 2005] to co-regularize the latent representations, each self-representation is enforced to be independent and correspond to a particular attribute. Adding all these selfrepresentations together results in an integrated representation which leads to a more accuracy clustering by capturing comprehensive information.

2 Attributed Subspace Clustering

2.1 Preliminary

Given n data matrix X = [x1, x2, . . . , xn] ∈ Rm×n , where each data vector xi is m-dimensional, we need to find effective self-representations for constructing an affinity matrix and applying spectral clustering methods [Shi and Malik, 2000] to cluster the data into their respective subspaces. To achieve so, representation-based approaches assume that every data point in a union of subspaces can be represented as a linear combination of other data points, i.e., X = XZ+E, where Z ∈ Rn×n is the learned self-representation matrix and E ∈ Rn×n is the error term. It can be formulated as the following optimization problem to compute the optimal Z:

where α is the trade-off parameter, Θ(E) is the noise term. Ω(X,Z) and T are the regularizer and constraint set on Z, respectively.

Taking LRR, one of the most representative subspace clustering methods as an example, it seeks the low rank representation by solving the objective function:

Obviously, the self-representation of LRR is learned straightforwardly from the features of original data without exploring sub-features. Hence, it cannot represent multiple attributes and capture the diverse information among them. To understand and represent data thoroughly and in-depth, we propose our attributed subspace clustering (ASC) below.

2.2 The Proposed ASC

As seen in (2), the self-representation Z is learned from the original features of X by using X itself as a basis matrix. Hence, if X comes with V attributes, we can modify (2) to learn multiple self-representations Z(v) simultaneously, with each one corresponding to one attribute:

where H(v) contains sub-features that can represent the v-th attribute of X and so called latent representation. Considering that every H(v) describes one aspect of X, given a basis matrix W(v) ∈ Rm×k(v) with a reduced dimensionality k(v) , the product of eachW(v) and the corresponding H(v) could well approximate X, hence we can easily factorize X as

However, since there is no constraint for learning H(v) , the diverse information of multiple attributes may not be explored effectively, as every H(v) could be very close to or even equal to each other. Consequently, if we simply combine (4) and (3), Z(v) will also be similar to each other, so that the distinct information of each attribute cannot be fully explored.

Given a case of data xi, with two attributes, v and w, the latent distinct information of each attribute cannot be fully explored unless the representations of two attributes, i.e., h(v) i and h(w) i , are enforced to be independent to each other. For n data vectors, if we assume that each vth attribute is drawn from X space and the wth attribute from Y space, essentially, we aim to learn a mapping function G of their representations from S := {(h(v) 1 , h(w) 1 ), (h(v) 2 , h(w) 2 ), . . . , (h(v) n , h(w) n )} ⊆ X × Y, i.e., G: X → Y, to minimize the dependence between the data representations in the X and Y. To do so, we employ the Hilbert-Schmidt Independence Criterion (HSIC) due to its simplicity and neat theoretical properties such as exponential convergence. HSIC computes the square of the norm of the cross-covariance operator over the domain X × Y in Hilbert Space. As an effective measure of dependence, HSIC has been applied to several machine learning tasks recently [Song et al., 2007; Zhang and Zhou, 2010; Niu et al., 2010]. Mathmatically, an empirical estimate of HSIC [Gretton et al., 2005] is defined as

where K(v) and K(w) are the centered Gram matrices of kernel functions defined over H(v) and H(w) , respectively. R = I - 1n eeT , where I is an identity matrix and e is an all-one column vector.

It is worth noticing that by utilizing the inner product kernel for HSIC, namely, K(v) = H(v) T H(v) and ignoring the scaling factor (n - 1)-2 for notational convenience, we can derive HSIC(H(v) ,H(w) ) into a very simple F-norm formulation as

Combining (3), (4) and (6) gives us the final objective function:

Here λ1 > 0, λ2 > 0 and λ3 > 0 are the trade-off parameters to balance the diversity among attribute representations, errors and intrinsic data structures for all V attributes, respectively. Specifically, the first term uncovers the underlying representations {H(v) }Vv=1 from the original data matrix X by using the second term as a regularizer. The first two terms guide the learning process of self-representation {Z(v) }Vv=1 in the third term. The last term regularizes {Z(v) }Vv=1 to capture the low rank structure of data of each attribute.

Remarks ASC is not limited to one specific subspace clustering method such as LRR. In fact, it can also be flexibly adapted and applied to most if not all current representationbased subspace clustering approaches such as SSC, LSR and SMR which differ mainly on regularization on Z. For example, SSC can be advanced as

Thus, SSC could be more powerful and practical by simultaneously learning spare self-representation and exploring multiple attributed self-representations, which we will investigate in our future work.

2.3 Optimization

Since the optimization problem (7) is not convex for each variable W(v) , H(v) and Z(v) , it is infeasible to find the global minimum. Hence we divide (7) into three subproblems and alternately update each subproblem with the other two fixed.

W(v) -subproblem: It is a standard matrix factorization decomposition, so we obtain

H(v) -subproblem: Updating H(v) with other subproblems fixed leads to the following objective function:

The problem (10) is smooth convex. Differentiating (10) with respect to H(v) and setting it to be 0, we get the following optimal solution H(v) which satisfies

The equation above is a standard Sylvester equation [Bartels and Stewart, 1972]. To avoid the instability issue, we ensure A(v) to be strictly positive definite by ˆ A(v) = A(v) + ϵI, where I is an identity matrix and ϵ ∈ (0, 1]. In the following, we prove it has a unique solution.

Proposition 1. The Sylvester equation (11) has a unique solution.

Proof. The Sylvester equation A(v)H(v) + H(v)B(v) = C(v) has a unique solution for H(v) exactly when there are no common eigenvalues of A(v) and -B(v) [Bartels and Stewart, 1972]. Since A(v) is a positive definite matrix, all of its eigenvalues are positive: α(v) i > 0. For B(v) is a positive semi-definite matrix, all of its eigenvalues are nonnegative: β(v) i ≥ 0. Hence, for any eigenvalues of A(v) and B(v) , α(v) i +β(v) j > 0. Accordingly, the Sylvester equation (11) has a unique solution.

Z(v) -subproblem: Updating Z(v) with other subproblems fixed leads to

This can be solved via the following lemma.

Lemma 1 [Favaro et al., 2011]. Let A = UΛVT be the SVD of a given matrix A. The optimal solution to minC ‖C‖∗ + τ2 ‖A-AC‖2F is

where U = [U1U2], Λ =diag(Λ1,Λ2), and V = [V1V2] are partitioned according to the sets I1 = {i : σi > 1/√τ} and I2 = {i : σi ≤ 1/√τ}, where σi is the ith entry of Λ. Moreover, the optimal value is

The whole procedure of ASC is summarized in Algorithm 1.

Algorithm 1 Solving ASC

Input: Original data matrix X, Number of attributes V , Number of subspaces p, Parameters λ1, λ2, λ3 Output: Clustering result.

Initialize W(v) , H(v) and Z(v) with random values.

end for

while not converge do

Fixing H(v) and Z(v) , updateW(v) by (9).

FixingW(v) and Z(v) , update H(v) by solving (11).

FixingW(v) and H(v) , update Z(v) by solving (12).

end for

end while

Construct an integrated self-representation matrix Z = ∑Vv=1 Z(v) and a similarity matrix S = |Z| + |ZT |. Segment the data into p groups by Normalized Cuts.

2.4 Complexity and Convergence Analysis

The complexity of updatingW(v) in (9) is O(mnk(v)+k(v) 3 ) and H(v) in (11) is O(k(v) 3 ) by using Bartels Stewart algorithm for solving the Sylvester equation. Updating Z(v) has O(n3 ) complexity as it involves SVD decomposition. Since usually k(v) ≪ n, the overall cost is ∑Vv=1 O(mnk(v) + n3 ) which is the same as that of LRR. Hence, we can conclude that ASC does not increase the complexity with respect to n as the result of exploring attributes, while in the meantime, multiple representations are learned to depict data comprehensively. Since the optimizations of all subproblems are convex and we can obtain each optimal solution, the value of (7) is monotonically decreasing. Therefore, the objective function (7) converges as it has trivial lower-bound 0.

3 Experiments

3.1 Dataset

To demonstrate the effectiveness of ASC, we carried experiments on several benchmark datasets. The Yale 1 contains

1 http://www.cad.zju.edu.cn/home/dengcai/Data/FaceData.html

11 face images for each of 15 subjects. The face images of each subject are either in different facial expressions (such as happy or sad) or configurations (such as with or without glasses). The COIL20 2 is composed of 1440 images for 20 objects. The 72 images of each object were captured by a fixed camera at a pose intervals of 5 degree. Some sample images of the two objects are shown in Figure 1. The Extended YaleB (YaleB) [Hu et al., 2014] contains 38 individuals and around 64 near frontal images under different illuminations for each individual. We use the first 10 classes of this dataset, which consists of 640 frontal face images. The ORL 3 dataset consists of 40 subjects with each containing 10 face images with various lighting and facial expressions. The Notting-Hill [Zhou et al., 2014] is a video face dataset, which is derived from the movie "Notting Hill". We used the 4660 faces from 5 main casts. The USPS [Hu et al., 2014] contains 9298 images of handwritten digits belonging to ten digits, 0-9. We use the first 100 images of each digit for our experiments. The images vary in each class but have common stroke attributes (such as 3 and 8) in different classes.

3.2 Experiment Setup

We compared ASC against the state-of-the-arts SSC [Elhamifar and Vidal, 2009], LRR [Liu et al., 2013], LSR [Lu et al., 2012], SMR [Hu et al., 2014] and L2-Graph [Peng et al., 2017]. The parameters of these methods were tuned to achieve the best performance for a fair comparison. For ASC, we empirically fixed (λ1, λ2) = (0.2λ3, 0.1λ3) and tuned λ3 from [0.1, 0.2, 0.3, 0.4, 0.5]. We also fixed the number of attributes V = 3 and each reduced dimension k(v) = 50 for all experiments. For all approaches, the similarity matrices were conducted on the typical similarity measures [Georghiades et al., 2001] and Normalized Cuts [Shi and Malik, 2000] was employed to produce the final clustering results. Four widely used evaluation metrics, including accuracy, normalized mutual information (NMI), Purity and F-score are used to assess the quality of the results with a comprehensive evaluation, and the best results are highlighted in boldface.

3.3 Performance Analysis

Clustering Results. Table 1 summarizes the average clustering results along with standard deviations. We can see that ASC performs the best on all datasets, which proves the effectiveness of exploring diverse information among attributes. Especially for YaleB dataset, ASC outperforms the second best result achieved by LRR with a large margin, i.e., 11.68%. This could be due to two reasons. One is that YaleB comes with heavy noises and outliers. LRR learns self-representation based on the original data X but ASC is based on latent representations {H(v) }3v=1 , the features of which are extracted from the original data with noises alleviated by the first term in (7). Hence, the learned selfrepresentations of ASC are more accurate and lead to a higher accuracy. The other reason is that ASC learns more comprehensive information of data by exploring diverse information among multiple independent self-representations and integrating them together. However, LRR learns a single selfrepresentation based on the features of original data only. To validate our reasoning, below we take a close look at the selfrepresentations.

2 http://www1.cs.columbia.edu/CAVE/software/softlib/coil-

20.php

3 http://www.cad.zju.edu.cn/home/dengcai/Data/FaceData.html

Study of Attributes. Figure 2 illustrates the learned selfrepresentation matrices of ASC and LRR for the Yale dataset. We only demonstrate the images of four subjects for clearer visualization, as well as two (out of three) attributed selfrepresentations Z(1) and Z(2) of ASC due to page limitation. We can see that the closeness among images are different in Z(1) and Z(2) . For example, the face images with shadow are very close to each other in Z(1) while the faces with happy/surprised expressions are close in Z(2) . Apparently, these representations enable the understanding of the data from multiple perspectives, which could be hardly achievable by current subspace clustering approaches. It is worthy noticing that the image that enclosed in blue rectangle in Z(1) is also represented in Z(2) , which means that the same image could be grouped differently based on different attributes.

Moreover, in terms of the whole features of data (i.e., subject), the integrated Z of ASC shown in Figure 2 has a much clearer data structure than that of LRR. This will undoubtedly lead to better clustering results which are in line with the results given in the Table 1. We further tested ASC on COIL20, a larger dataset, and demonstrated some example clustering results in Figure 3. Again, the results are quite impressive and promising, with multiple clusters being obtained through different attributes (rotation, shape, etc), which is beyond what existing subspace clustering approaches can offer.

Parameter Analysis. Here we tested the sensitivity of parameters λ1, λ2 and λ3 on clustering results. We varied λ3 from 0.1 to 0.5 with an increment of 0.1 and we experimentally fixed (λ1, λ2) = (0.2λ3, 0.1λ3). Since the performance on each dataset has a similar tendency, we show the parameters' effects on the accuracy for Yale and YaleB only. As shown in Figure 4, ASC shows a relatively stable performance on the two datasets, which demonstrates the robustness to parameter tuning. Also, the performance of ASC is consistently better than LRR when λ3 is tuned in a suitable range. Taking the Yale as an example, ASC performs better when λ3 ∈ [0.3, 0.5] than 0.5727 that is achieved by LRR (Table 1). Worth to mention that, the better accuracies could be expected by grid search λ1, λ2 and λ3, though it will inevitably incur a higher cost of the parameter tuning. We also evaluated the effect of the number of attributes V for both Yale and YaleB. Here we fixed λ3 = 0.5 and gradually increased V from 1 to 5. As illustrated it in Figure 5, the accuracy for both datasets increases when V is tuned from 1 to 3, which signifies the effectiveness of the exploration of multiple attributes. However, the accuracy decreases when V increases from 3 to 5. The fluctuation could be due to a compromise between the amount of available features for each H(v) and the diverse information among them. When V increases, more diverse information can be utilized. However, when V exceeds the number of prominent attributes, the amount of discriminative features for each H(v) could be insufficient for representing an attribute.

Convergence Analysis. Having proven the convergence of ASC in the Section 2.4, here we experimentally demonstrate its convergence in Figure 6, where the horizontal axis is the number of iterations and the vertical axis is the value of objective function. It can be seen that the values of the objective function are non-increasing and drop sharply around 10 iterations on the Yale.

4 Conclusion

In this paper, we have proposed an attributed subspace clustering (ASC) approach which explores multiple attributes of data to understand data from various aspects. Different from existing subspace clustering approaches that seek for a single self-representation based on original data, ASC simultaneously learns multiple self-representations with each one corresponding to one attribute and obtains an aggregated selfrepresentation by adding them together. Extensive experiments on six image benchmarks have clearly shown that ASC not only achieves multiple clustering solutions with each one reflecting one property of data, but also improves the clustering accuracy based on an aggregated self-representation. Though ASC has shown the effectiveness for each dataset with the same number of attributes being fixed in our experiments, nevertheless, investigating the optimal number of attributes for each dataset with model selection which could potentially enable ASC to be more desirable and practical. This could be our future work.

Acknowledgements

This work was partially supported by JSPS KAKENHI (No. 19H01114), JST AIP and JSPS KAKENHI (No. 18J12201).