Flexible Multi-View Representation Learning for Subspace Clustering

1 Introduction

Subspace clustering is a fundamental method for recovering the subspace structure of data, especially for highdimensional data. Recently, self-representation-based subspace clustering methods [Elhamifar and Vidal, 2013; Liu et al., 2013; Hu et al., 2014] have been proposed, which are based on the assumption that each data point can be reconstructed using the dictionary formed by all data points. Sparse Subspace Clustering (SSC) [Elhamifar and Vidal, 2013] clusters data based on sparse representation which can be obtained by ℓ1-norm. Low-Rank Representation (LRR) [Liu et al., 2013] aims to search for a lowest-rank representation among all the candidates. Smooth Representation clustering (SMR) [Hu et al., 2014] introduces the grouping effect for subspace clustering. The above mentioned methods have produced promising performances, however, they only focus on boosting single-view clustering.

In many real-world applications, data are often from multiple sources. For example, a document might be described by images, video, text, and audio. Human activities may be captured by video cameras, depth cameras, and on-body sensors. These different views often contain complementary information to each other, hence exploiting the complementarity among multiple views could potentially advance the clustering performance.

Considering that each individual view is insufficient for depicting data points, recently, subspace clustering has been extended to multi-view cases [Cao et al., 2015; Zhang et al., 2015; Zhang et al., 2017]. With the introduction of low-rank tensor constraint or exploration of the diversity among different subspace representations, LT-MSC [Zhang et al., 2015] and DiMSC [Cao et al., 2015] could well explore complementary information from multiple sources and improve the subspace clustering by a large margin. However, there are two main limitations in these approaches: (1) they reconstruct data within each single view using original noisy features, which is insufficient to describe data; (2) they only exploit linear subspaces of data in the raw feature space, which is not enough for capturing complex correlations among real-world data.

One important technique for identifying the relationships among different views and simultaneously constructing a common space is Canonical Correlation Analysis (CCA) [Chaudhuri et al., 2009]. Although simple, CCA-based methods have the following limitations: (1) they project multiple views into a common space by improving their correlations, but cannot well address the complementarity of different views; (2) the dimensionalities of different views are reduced to the same, which is not suitable for the cases when the dimensionalities of two views are extremely unbalanced; (3) multi-view common representation learning process is separated from subspace clustering, which will cause the common representation not well-adapted to subspace clustering.

To address above issues, we propose a novel Flexible Multi-view Representation (FMR) learning method to construct a latent representation. Differing from CCA, we adopt the kernel dependence measure to drive the latent representation closely correlated to each view, so that there is no need to project multiple views into a common space. By mapping original features into the kernel space, the high-order and nonlinear dependence among different views can be captured.

The latent representation effectively facilitates subspace clustering, and meanwhile its comprehensiveness is promoted by subspace reconstruction. The main contributions of this paper include:

• We propose to conduct subspace clustering based on Flexible Multi-view Representation (FMR) learning, which avoids using partial information for data reconstruction and makes the latent representation welladapted to subspace clustering.
• We propose to construct a latent representation by encouraging it to be similar to different views in a weighted way, which implicitly enforces it to encode complementary information from multiple views.
• We introduce the kernel dependence measure: Hilbert Schmidt Independence Criterion (HSIC), to capture high-order, non-linear relationships among different views, which benefits recovering underlying cluster structure of data.
• Our model can be efficiently optimized by the Alternating Direction Minimization (ADM) method. Extensive experiments on benchmark datasets show its effectiveness.

2 RelatedWork

For single-view subspace clustering methods, the major difference lies in the constraint on subspace representation. LRR [Liu et al., 2013] and SSC [Elhamifar and Vidal, 2013] encourage subspace representations to be low-rank and sparse, respectively. Multi-Subspace Representation (MSR) [Luo et al., 2011] combines both criteria of LRR and SSC. Least Squares Regression (LSR) [Lu et al., 2012] improves grouping effect of data by Frobenius norm. Recently, researchers propose some subspace clustering methods based on latent space [Liu and Yan, 2011; Patel et al., 2013]. Latent Space Sparse Subspace Clustering (LS3C) [Patel et al., 2013] integrates dimensionality reduction and subspace clustering into a unified framework. Latent Low-Rank Representation (LatLRR) [Liu and Yan, 2011] is an enhanced version of LRR, which constructs the dictionary using both observed and unobserved data. Above mentioned methods implement subspace clustering in the single view without considering the multi-view cases.

With the growing amount of data from multiple sources, multi-view clustering has been widely studied and applied in real-world applications. De Sa proposes to create a bipartite graph and performs spectral clustering based on "minimizingdisagreement" idea [De Sa, 2005]. Multi-view clustering via Canonical Correlation Analysis (CCA) [Chaudhuri et al., 2009] projects different views into a common lowdimensional space. Some approaches [Wei et al., 2009; Gao et al., 2013] employ matrix factorization technique for multi-view clustering. Gao et al. address large-scale issue under the K-means framework [Gao et al., 2013]. The co-regularized method [Kumar et al., 2011] searches for a consistent clustering result across different views with a coregularization constraint. The convex representation learning method [White et al., 2012] enforces the conditional independence among separate views and simultaneously reduces the dimensionality. Tao et al. conduct multi-view clustering in an ensemble clustering way, which constructs a consensus partition of data across different view-specific basic partitions [Tao et al., 2017; Tao et al., 2019]. Robust Multiview Spectral Clustering [Xia et al., 2014] recovers a shared low-rank transition probability matrix as an input to the standard Markov chain. The recently proposed subspace methods [Cao et al., 2015; Zhang et al., 2015; Zhang et al., 2017; Wang et al., 2017] incorporate multi-view information under the self-representation-based subspace clustering framework.

Different from linear cases, we further explore the highorder, nonlinear relationships among different original views, so that the latent representation could properly depict data and reveal the intrinsic cluster structure shared by multiple views.

3 Proposed Approach

3.1 Subspace Clustering

Self-representative subspace clustering is quite effective for high-dimensional data. Suppose X=[x1, x2, ..., xN] ∈ Rd×N is the sample matrix, each column of which represents a data point, d is the dimensionality of feature space and N is the number of samples. To cluster data into their respective subspaces, we infer an coefficient matrix Z that reflects the similarity among data points. Without loss of generality, the formulation of subspace clustering can be written as:

where L(·, ·) and Ω(·) are loss function associated with data reconstruction and regularization term respectively, and the scalar λ > 0 is used to balance these two terms. Based on the coefficient matrix Z, the similarity matrix S is further obtained by S = abs(Z) + abs(ZT ), where abs(·) is the element-wise absolute operator. Then it is taken as an input for spectral clustering algorithm [Ng et al., 2001] to produce the final results.

Although above methods have achieved promising performances, they tend to be affected by original features, especially when each single view is insufficient to depict data.

3.2 Measuring Dependence

In this work, we propose a novel method to flexibly learn a common latent representation H by maximizing the dependence between it and different views. In this paper, we adopt the Hilbert-Schmidt Independence Criterion (HSIC) to measure dependence in the kernel space. The basic idea is to map original views into the Reproducing Kernel Hilbert Spaces (RKHSs) to capture high-order, nonlinear dependence among different original features. Suppose that data points x and y are drawn from two feature spaces X and Y, respectively. φ(x) represents a mapping from x ∈ X to kernel space F. Similarly, ϕ(y) is a mapping from y ∈ Y to the other kernel space G. The linear cross-covariance operator Cxy is defined as:

where µx and µy are mean values of φ(x) and ϕ(y), respectively. ⊗ is the tensor product. Based on the cross-covariance operator, we have the following definition of HSIC:

Definition 3.1 [Gretton et al., 2005] Given separable RKHSs F, G and a joint distribution pxy, we define HSIC as the squared Hilbert-Schmidt norm of Cxy:

Given N independent observations drawn from the joint distribution pxy: {(x1, y1), ..., (xN , yN )} ⊆ X ×Y, denoted as X, Y, the empirical HSIC measure is defined as:

where Kx, Ky ∈ RN×N are Gram matrices with (Kx)ij = kx(xi, xj) =< φ(xi), φ(xj) >, (Ky)ij = ky(yi, yj) =< ϕ(yi), ϕ(yj) >, and where (L)ij = δij -N -1 centers the Gram matrices to have zero mean in the feature space, δij denotes the entity of identity matrix.

3.3 Formulation

Given N observations from V views, we denote the vth view of data as X(v) = {x(v) 1 , ..., x(v) N } ∈ Rdv×N , 1 ≤ v ≤ V . For exploring complementary information from different views, we employ HSIC as a measure of dependence to drive the latent representation H to be close to different views. Furthermore, considering the varying quality of different views, we give weight αγ v for the vth view, which encodes the degree of similarity between the vth view and the latent representation. γ is the parameter to adjust the weight distribution of different views [Wang et al., 2007]. That is to say, the view strongly correlated to H will be assigned large weight. Over all, the objective function to infer the latent representation is:

The latent representation is more comprehensive than any single view due to the encoded complementary information. We conduct subspace clustering on it and obtain the total objective function as follows:

The first term is used to integrate complementary information from multiple views into a latent representation. || · ||∗ denotes the nuclear norm, which enforces the subspace representation Z to be low-rank. We impose ℓ2,1-norm on reconstruction error E with ||E||2,1 = ∑Nj=1 √∑Ni=1 ([E]ij )2 to encourage columns of E to be zero [Liu et al., 2013]. The hyper-parameters λ1 and λ2 control the trade-off among the three terms.

4 Optimization

To make the objective function separable, we introduce an auxiliary variable J to replace Z, then Eq. (6) is converted to the following equivalent problem:

Accordingly, we solve the above problem by the Augmented Lagrange Multiplier (ALM) method, and induce the following objective function:

For convenience, we give the definition Φ(Y,C) = µ2 ||C||2F + 〈Y, C〉, where 〈·, ·〉 defines the matrix inner product, Y is Lagrange multiplier matrix, and µ is a positive penalty scalar. According to the LADMAP [Lin et al., 2011], Eq. (8) can be separated into the following subproblems:

H-subproblem. Fixing the other variables, we firstly update H by solving the following subproblem:

We optimize Eq. (9) with Gradient Descent algorithm (GD), where the gradient with respect to H is:

Z-subproblem. Fixing the other variables, we update Z by solving the following problem:

Taking the derivative with respect to Z and setting it to zero, we can update Z with the following rule:

E-subproblem. For updating the reconstruction error E, we solve the following problem:

The above subproblem can be solved by Lemma 4.1 in [Liu et al., 2013].

J-subproblem. The Lagrange function with respect to J can be optimized by:

This step can be solved by the Singular Value Thresholding (SVT) operator [Cai et al., 2010].

Algorithm 1: Optimization of our method

Input: Multi-view data: {X(1) , ...,X(V ) }, the number of clusters m, hyper-parameters λ1 and λ2, the dimensionality of latent representation K, and the parameter γ.

Initialize: E = 0, Z = J = 0, Y1 = 0, Y2 = 0, µ = 10-5 , ρ = 1.1, ε = 10-4 , maxµ = 1010 ; Initialize the latent representation Hwith random values and initialize the weight α = 1/V for all the views.

while not converged do

Update variables H, Z, E, J according to Eq. (10), (12)

-(14), respectively;

Update weight αv (1 ≤ v ≤ V ) according to Eq. (18); Update multipliers Y1,Y2 and penalty parameter µ according to Eq. (19);

Check the convergence conditions:

end

Output: H, Z, {α1,...,αV }.

Updating weights. αv (1 ≤ v ≤ V ): To update αv, we rewrite Eq. (7) as:

where

The Lagrange function of Eq. (15) is:

where β is the Lagrange multiplier. We set the derivative with respect to αv to zero, then we get:

Updating multipliers. Finally, the Lagrange multipliers Y1,Y2 and penalty parameter µ are updated according to LADMAP [Lin et al., 2011] algorithm:

where ρ is a positive scalar.

4.1 Complexity Analysis

The main complexities of self-representative subspace clustering methods (DiMSC [Cao et al., 2015], LT-MSC [Zhang et al., 2015], LMSC [Zhang et al., 2017]) are from the graph (with the size N ×N) involved, which leads to the computational cost of matrix operations (e.g., SVD decomposition and matrix inversion). There are two main steps for these methods, i.e., affinity matrix learning (step1) and spectral clustering (step2). We list the complexity of each step in Table 1. In general, the total complexities for all these methods on largescale data are O(N 3 ).

Table 1: Complexity analysis of different methods

5 Experiments

We conduct experiments on 7 datasets from different applications: images, text, and community networks.

• Yale 1 consists of 165 grayscale images of 15 individuals, from which 3 types of features are extracted.
• MSRC-v1 [Xu et al., 2016] consists of 210 images of 7 object classes, which includes 6 types of features.
• Notting-Hill [Wu et al., 2013] is a video face dataset consisting of 550 images of 5 main casts described from 3 different views. It is more challenging because of the rich facial expressions, changing angles, and varied light intensities.
• Reuters [Amini et al., 2009] is a multilingual dataset including 2000 newswire articles of 6 classes written in 5 languages (views).
• BBCSport 2 is composed of news articles in 5 topical areas from BBC website, which is associated with 2 views.
• Football 3 contains 248 English Premier League football players and clubs active on Twitter, which are described from 9 different views and associated with 20 clubs.
• ANIMAL [Lampert et al., 2014] contains 30475 images of 50 animal classes including 2 types of feature. 10158 samples are selected with fixed interval to generate a subset.

5.1 ComparedMethods

We compare our approach with 8 state-of-the-art baselines. SPCBestSV [Ng et al., 2001] performs standard spectral clustering within the best single view. Min-D [De Sa, 2005] creates a bipartite graph to minimize the disagreement between two views. Co-Reg SPC [Kumar et al., 2011] coregularizes the clustering hypotheses to be consistent across multiple views. RMSC [Xia et al., 2014] constructs a joint low-rank transition probability matrix as an input for spectral clustering. DiMSC [Cao et al., 2015] explores the diversity among subspaces of all views through kernel technique. LTMSC [Zhang et al., 2015] employs low-rank tensor to capture high-order relationships among different views. LMSC [Zhang et al., 2017] constructs an underlying latent representation through linear mapping and then conducts subspace clustering on it. ECMSC [Wang et al., 2017] simultaneously explores the representation complementarity and indicator consistency among different views.

1 http://cvc.yale.edu/projects/yalefaces/yalefaces.html

2 http://mlg.ucd.ie/datasets/

3 http://mlg.ucd.ie/aggregation/

Table 2: Performance comparison of different methods

In experiments, we use four metrics to evaluate the clustering performances: Normalized Mutual Information (NMI), Accuracy (ACC), F-score, and Rand Index (RI). Higher values indicate better performances for all these metrics.

5.2 Experimental Results

For all compared methods, we tune the parameters to achieve the best performance and run each experiment 30 times to report the mean and standard deviation.

Experimental results. According to the performance comparisons of different methods shown in Table 2, we have the following observations: (1) our algorithm outperforms other baselines on most datasets. For example, our method gains large improvements around 6.77%, 8.13% over the second best baseline (ECMSC) in terms of NMI and ACC on Yale, respectively; (2) our method consistently obtains better performances than DiMSC, LT-MSC, and ECMSC, because we construct subspace representation based on the latent representation instead of each original single view; (3) our algorithm obviously boosts the clustering performance over LMSC, because it explores nonlinear and high-order relationships among different views using HSIC, while LMSC can only address linear cases.

Improvement of latent representation. To further investigate the improvement of latent representation, as shown in Table 3, we implement LRR [Liu et al., 2013] on each original view, Feature Concatenation (FeatConcate), and the common representations learned by CCA-based methods (CCA [Hotelling, 1936], KCCA [Bach and Jordan., 2002], DCCA [Andrew et al., 2013]). Note that we only list the results within the best two views. Intuitively, benefiting from encoding complementary information from multiple views, our method advances the clustering performance by a large margin. Besides, our method even outperforms deep neural networks based method (DCCA) on all the datasets. Figure 2 shows the t-SNE visualizations of different representations. As can be seen, our method better recovers the cluster structure of data due to the exploration of high-order, nonlinear correlations among multiple views.

5.3 Model Analysis

Parameter tuning. In our experiments, we set the dimensionality of latent representation as 200 and tune hyperparameters λ1 and λ2 from {10-5 , 10-4 , · · · , 10-1 , 100 } and {10-10 , 10-9 , · · · , 10-3 ,

10-2 }, respectively. Figure 1(a) shows the effect of changing values of λ1 and λ2 on clustering performance. We can observe that our method is less sensitive to λ2.

Figure 2: t-SNE visualizations of (a) FeatConcate, (b) KCCA, (c) DCCA, (d)FMR on MSRC-v1 (top row) and BBCSport (bottom row).

Convergence analysis. The convergence of inexact Augmented Lagrange Multiplier (ALM) method with three or more variable blocks is still difficult to theoretically prove [Liu et al., 2013], while there are six variable blocks in Algorithm 1. Fortunately, as shown in Figure 1(b), our method has strong convergence property in practice.

6 Conclusions

In this paper, we propose a novel method to flexibly learn a multi-view representation to improve subspace clustering. Different from data reconstruction within each single view, our method explores the complementary information among multiple views. Besides, we further extend the multi-view representation learning to nonlinear cases using HSIC. The learned latent representation can recover underlying cluster structure shared by multiple views and boost clustering performance greatly. Comprehensive evaluations on several benchmarks demonstrate the validity and superiority of our method.

Acknowledgements

This work was partly supported by National Natural Science Foundation of China (61602337, 61732011, 61702358), and Jiangsu Key Laboratory of Big Data Security & Intelligent Processing, NJUPT. Corresponding Author: Changqing Zhang.