Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation

High-dimensional data are ubiquitously in many areas like image processing, DNA microarray technology, etc. The high-dimensional data can often be well approximated by a set of linear subspaces, but the subspace membership of a certain sample is unknown [1, 2]. Subspace clustering aims to divide the data samples into different subspaces, which is an important tool to model the high-dimensional data. The state-of-the-art subspace clustering methods [3, 4] are based on self-expressiveness, which represent high-dimensional data by the linear combination of itself, and enforce a subspace-preserving prior on the self-representation matrix. The representation coefficients capture the global geometric relationships of samples and can act as an affinity matrix, and the subspace segmentation can be obtained by applying spectral clustering on the generated affinity matrix. The most well-known subspace clustering methods include sparse subspace clustering [3] and low-rank representation [4].

In many real-world applications, some supervisory information is available, e.g., the label information of a dataset, and the relationships between two samples. Generally, those supervisory information can be represented by two kinds of pairwise constraints, i.e., must-link constraints and cannot-link constraints indicating whether two samples belong to the same category or not. As the supervisory information is widespread and provides a discriminative description of the samples, many semi-supervised subspace clustering methods [5, 6, 7, 8, 9, 10, 11, 12, 13] were proposed to incorporate them. Based on the type of the supervisory information, we roughly divide these methods into three classes. The first kind of methods include the must-link constraints. For example, [5, 6] incorporated the must-links as hard constraints, which restricted the samples with a must-link to have exactly the same representation. The second kind of methods integrate the cannot-link constraints. For instance, [7] required the affinity relationship of two samples with a cannot-link to be 0. Liu et al. [8] first enhanced the initial cannot-links by a graph Laplacian term, and then inhibited the affinity of two samples with a cannot-link. The third kind of methods can incorporate both the must-links and cannot-links, which generally assume two samples with a must-link should have a higher affinity, while those with a cannot-link should have a lower affinity [9, 10, 11, 12, 13]. However, the above-mentioned semi-supervised subspace clustering methods exploit the supervisory information from a local perspective, but overlook the global structure of the pairwise constraints, which is also important to semi-supervised affinity matrix learning. In other words, the previous methods under-use the supervisory information to some extent.

To this end, we propose a new semi-supervised subspace clustering method shown in Fig. 1, which explores the supervisory information from a global manner. Specifically, in the ideal case, the pairwise constraint matrix is low-rank, as if all the pairwise relationships of samples are available, we could encode the pairwise constraint matrix as a binary low-rank matrix. Meanwhile, the ideal affinity matrix is also low-rank, as a sample should only be represented by the samples from the same class. More importantly, they share an identical low-rank structure. Based on such an observation, we stack them into a 3-dimensional tensor, and regulate a global low-rank constraint to the formed tensor. By seeking the tensor low-rank representation, we can refine the affinity matrix with the available pairwise constraints, and at the same time, augment the initial pairwise constraints with the learned affinity matrix. Besides, we encode the local geometry structure of the data samples to complement the global low-rank prior. The proposed model is formulated as a convex optimization model, which can be solved efficiently. Finally, we use the augmented pairwise constraint matrix to further refine the affinity matrix. Extensive experiments on 8 datasets w.r.t. 2 metrics demonstrate that our method outperforms the state-of-the-art semi-supervised subspace clustering methods to a large extent.

In this letter, we denote tensors by boldface Euler script letters, e.g., $\mathcal{A}$, matrices by boldface capital letters, e.g., $\mathbf{A}$, vectors by boldface lowercase letters, e.g., $\mathbf{a}$, and scalars by lowercase letters, e.g., $a$. $\|\cdot\|_{2,1}$, $\|\cdot\|_{\infty}$, $\|\cdot\|_{F}$ and $\|\cdot\|_{*}$ are the $\ell_{2,1}$ norm, the infinity norm, and the Frobenius norm, and the nuclear norm (i.e., the sum of the singular values) of a matrix. $\mathbf{X}\!=\![\mathbf{x}_{1},\mathbf{x}_{2},...,\mathbf{x}_{n}]\in\mathbb{R}^{d\times n}$ is the data matrix, where $\mathbf{x}_{i}\in\mathbb{R}^{d\times 1}$ specifies the $d$-dimensional vectorial representation of the $i$-th sample, and $n$ is the number of samples. Let $\mathbf{\Omega}_{m}\!=\!\left\{(i,j)\mid\mathbf{x}_{i}\right.$ and $\mathbf{x}_{j}$ belong to the same class$\}$ and $\mathbf{\Omega}_{c}\!=\!\left\{(i,j)\mid\mathbf{x}_{i}\right.$ and $\mathbf{x}_{j}$ belong to different classes$\}$ stand for the available must-link set and cannot-link set. We can encode the pairwise constraints as a matrix $\mathbf{B}\in\mathbb{R}^{n\times n}$:

Subspace clustering aims to segment a set of samples into a group of subspaces. Particularly, self-expressive-based subspace clustering methods have attracted great attention, which learn a self-representation matrix to act as the affinity. For example, Liu et al. [4] proposed to learn a low-rank affinity matrix by optimizing

where $\mathbf{Z}\!\in\!\mathbb{R}^{n\times n}$ is the representation matrix, $\mathbf{E}\in\mathbb{R}^{d\times n}$ denotes the reconstruction error, and $\lambda\!>\!0$ is a hyper-parameter.

Recently, many semi-supervised subspace clustering methods were proposed by incorporating the pairwise constraints [5, 6, 7, 8, 9, 10, 11, 12, 13]. How to include the supervisory information is the crux of semi-supervised subspace clustering. Generally, the existing methods incorporate the pairwise constraints from a local perspective, i.e., expand (resp. reduce) the value of $\mathbf{Z}_{ij}$ if $\mathbf{x}_{i}$ and $\mathbf{x}_{j}$ has a must-link (resp. cannot-link).

In this section, we evaluated the proposed model on 8 commonly-used benchmark datasets, including ORL, YaleB, COIL20, Isolet, MNIST, Alphabet, BF0502 and Notting-Hill¹¹1ORL, YaleB, COIL20, Isolet and MNIST can be found in http://www.cad.zju.edu.cn/home/dengcai/Data/data.html, BF0502 in https://www.robots.ox.ac.uk/~vgg/data/nface/index.html, Notting-Hill in https://sites.google.com/site/baoyuanwu2015/.. Those datasets cover face images, object images, digit images, spoken letters, and videos. To generate the weakly-supervisory information, following [7], we inferred the pairwise constraints from the randomly selected labels.

We compared our method with LRR [4] and six state-of-the-art semi-supervised subspace clustering methods, including DPLRR [8], SSLRR [7], L-RPCA [19], CP-SSC [20], SC-LRR [9] and CLRR [5]. We performed standard spectral clustering in [17] on all the methods to generate the clustering result. We adopted the clustering accuracy and normalized mutual information (NMI) to measure their performance. For both metrics, the larger, the better. For fair comparisons, we carefully tuned the hyper-parameters of the compared methods through exhaustive grid search to achieve the best result. To comprehensively evaluate the different methods, for each dataset, we randomly selected various percentages of initial labels $(\{5\%,10\%,15\%,20\%,25\%,30\%\})$ to infer the pairwise constraints. We used the same label information for all the compared methods in every case. To reduce the influence of the random selection, we repeated the experiments 10 times with the randomly selected labels each time, and reported the average performance.

We have proposed a novel semi-supervised subspace clustering model. We first stacked the affinity matrix and pairwise constraint matrix to form a tensor, and then imposed a tensor low-rank prior on it to learn the affinity matrix and augment the pairwise constraints simultaneously. In addition to the global tensor low-rank term, we added a Laplacian regularization term to model the underlying local geometric structure. Furthermore, the learned affinity matrix was refined by the augmented pairwise constraints. The proposed model was formulated as a convex problem, and solved by ADMM. The experimental results demonstrated that our model outperforms other semi-supervised subspace clustering methods significantly.

In the future, we will investigate how to incorporate our work with the existing semi-supervised learning neural networks [21, 22, 23, 24]. For example, we can use the proposed pairwise constraint enhancement as a loss function to train the neural networks in an end-to-end manner. Moreover, we will improve our method by solving the noisy pairwise constraints problem.