Integrating Tensor Similarity to Enhance Clustering Performance

Clustering aims to separate observed data into different categories. The performance of popular clustering models relies on the sample-to-sample similarity. However, the pairwise similarity is prone to be corrupted by noise or outliers and thus deteriorates the subsequent clustering. A high-order relationship among samples-to-samples may elaborate the local manifold of the data and thus provide complementary information to guide the clustering. However, few studies have investigated the connection between high-order similarity and usual pairwise similarity. To fill this gap, we first define a high-order tensor similarity to exploit the samples-to-samples affinity relationship. We then establish the connection between tensor similarity and pairwise similarity, proving that the decomposable tensor similarity is the Kronecker product of the usual pairwise similarity and the non-decomposable tensor similarity is generalized to provide complementary information, which pairwise similarity fails to regard. Finally, the high-order tensor similarity and pairwise similarity (IPS2) were integrated collaboratively to enhance clustering performance by enjoying their merits. The proposed IPS2 is shown to perform superior or competitive to state-of-the-art methods on synthetic and real-world datasets. Extensive experiments demonstrated that tensor similarity is capable to boost the performance of the classical clustering method.


INTRODUCTION
Clustering refers to separating observed data into subgroups, within which similar samples are quantified by some similarity measurements [1], [2], [3]. Therefore, similarity metrics play a dominant role in clustering performance [4], [5], [6]. In most of the popular methods, the similarity matrix is defined by a distance for two samples. The distance could be predefined or adaptively learned from the data. For example, the k-nearest neighbors algorithm (k-NN) or its variants use a predefined distance, such as the Euclidean distance, to quantify pairwise similarity. [7] used data-driven techniques to learn the distance function.
Additionally, there are a few clustering methods considering enhancing the sample-to-sample similarity by exploiting local manifold among multiple samples [8], [9]. For example, [10] defined the similarity for two sample subsets by introducing a hypergraph. In the hypergraph, each vertex denotes a subset of samples while the weight along the hyperedge is the similarity between two vertices. It leverages the spatial distribution of the samples to guide the clustering [11].
However, the aforementioned hypergraph clustering is still based on pairwise similarity, which can only demonstrate a sample-to-sample correlation and is prone to corruption by outliers or noise [12]. There is an old Chinese say "Birds of a feather flock together". The wisdom phrase implies that accurate clustering can be achieved through grouping multiple similar subjects simultaneously. This paper aims to fulfill this gap by exploiting the similarity of multiple samples for enhancing the popular pairwise routine clustering. We firstly define a tensor similarity of pair- to-pair samples using tensor notations. We then establish the relationship between the high-order tensor similarity with the routine pairwise similarity. By this way, we build a bridge between relationship of sample-to-sample and samples-to-samples for learning a new high-order similarity. The introduced tensor similarity allows one to have a larger freedom in using various distance functions, which is prohibited in routine clustering. To exploit the merits of tensor similarity, we further propose to fuse the new high-order similarity learned from it and pairwise similarity together, and prove that the popular pairwise clustering could be enhanced through the new high-order similarity.
In addition, we prove that the high-order tensor similarity thereby is capable of enhancing the robustness of clustering in radical cases. Extensive experiments have been conducted validating that the proposed model achieves superior performances compared with state-of-art algorithms. This paper achieves four contributions summarized as follows: 1) We establish the relationship between the tensor similarity and the regular pairwise one. An intrinsic flaw inherited in the popular pairwise similarity was made up by the proposed tensor similarity and thus being able to enhance the performance of classical clustering method. 2) We also establish the relationship between the leading eigenvectors of the Laplacian matrix for both the pairwise and tensor similarities, setting up a bridge to employ the classical graph spectral on the tensor similarity.
3) The generated tensor similarity serves as an complementary information of pairwise affinity relationship. By integrating it with pairwise similarity collaboratively, our algorithm achieves superior clustering per-formances. 4) Extensive experiments on both real-world and synthetic datasets validate the effectiveness and robustness of the tensor similarity in providing complementary information for regular pairwise similarity in clustering. The remainder of the paper is structured as following: In Section 2, we review the previous works on pairwise clustering and hypergraph clustering methods. Section 3 describes our proposed method of formulating tensor similarity for learning high-order affinity relationship of data. Then, we summarize the detailed procedures of our algorithm in section 4. Section 5 demonstrates the effectiveness of our approach through extensive experiments performed on synthetic datasets and real-world datasets. Finally, we provide conclusions in Section 6.

RELATED WORK
The measurement of similarity is fundamental to the clustering model. Traditionally, the clustering performance relies on the sample-to-sample similarity. It is commonly expressed as a function of metric [13] to reflect the strength of the relationship between the two samples. Different metrics result in distinct outcomes. For example, [14] propose an approximation on Euclidean distance to measure the color similarity and spatial proximity between image pixels. The cosine similarity measurement is widely adopted for measuring the similarity between documents [15]. [16] use Manhattan distance to deal with projected clustering problem.
Recently, the hypergraph scheme is a natural way to represent high-order relationship of data, which is employed to enhance the pairwise clustering by leaving a local manifold among the samples [17], [18], [19]. Hypergraph generates hyperedge with two or more samples, thus it can study a new form of high-order similarity [20]. It has been shown in [10] that the hypergraphs can be reduced into a standard graph, and most recent works have largely followed this basic concept with various extensions [21], [22], [23]. Thereby, the hypergraph plays a role of transition in firstly learning a high order representation of data, which can be used to model the pairwise similarity [24], [25].

INTEGRATING TENSOR SIMILARITY WITH PAIR-WISE SIMILARITY
In this section, we aim to show that the tensor similarity provides complementary information for the routine pairwisesimilarity-based clustering models. To demonstrate this concept, we first introduce some notations and properties required in our algorithm. Next, we establish the relationship between the tensor similarity and the usual pairwise similarity, suggesting that a decomposable tensor similarity is a special high-order form of the pairwise similarity. Thereby, a non-decomposable tensor similarity provides complementary information for which the pairwise similarity can not. Finally, to enjoy the merits of tensor similarity and pairwise similarity, we propose a fusion model to consolidate them to enhance the performance of the clustering models based on pairwise similarity.

Notation and Background on Kronecker product
Throughout the paper, vectors are signified by bold lowercase letters and matrices are denoted by bold uppercase letters. We let scalar variables be denoted by normal symbols for clarity. For example, given an observed dataset with m samples and n features X = [x 1 , x 2 , · · · , x m ], let S m×m denote the pairwise similarity. Each entry S(i, j) measures the strength of the relationship between the i-th and j-th samples. Let v denote the leading eigenvector of the corresponding Laplacian matrix L = D − 1 2 SD − 1 2 . Matrix D is diagonal with the value being the row summation of S. Let a four-dimensional tensor T m×m×m×m denote the tensor similarity for two pairs. Each entry T (i, j, k, l) denotes the pairs-wise similarity of pair (i, j) to pair (k, l). The tensor could be concatenated along a direction, which is called unfolding. LetT denote the matrix obtained by unfolding the tensor T vertically andv denote the eigenvector of pairsto-pairs Laplacian matrixL corresponding toT . We use n to denote a set {1, 2, · · · , n}.
We also briefly introduce the definition and some properties of the Kronecker product [26] used in our algorithm.

Then the Kronecker product (or tensor product) of A and B is defined as the matrix
Theorem 3.2. Let A ∈ R n×n have eigenvalues λ i , i ∈ n, and let B ∈ R m×m have eigenvalues µ j , j ∈ m.
Detailed proof of these theorems are described in SI Appendix, Section 1.1.

Decomposable Tensor Similarity Is the Kronecker Product of Pairwise Similarity
Classical pairwise clustering is achieved by defining sample-to-sample similarity. In this paper, we consider samples-to-samples similarity to incorporate local structures, thereby establishing the relationship between pairwise similarity and tensor similarity. For ease of presentation, we first consider the decomposable tensor similarity T .

Theorem 3.3.
If tensor similarity T is decomposable for some pairwise similarity S, that is, T ijkl = S(i, j) * S(k, l), for i, j, k, l ∈ m, then the unfolded similarity matrix satisfieŝ T = S ⊗ S.
According to Def. 3.1, it is clear thatT = S ⊗S holds. An illustrative example is shown in Fig. 1. The example consists of three ordered sub-clusters, and the Kronecker product of its pairwise similarity matrix also contains three diagonal blocks ( Fig. 1(b)). It is clear see that the unfolded tensor similarity matrixT computed by Theo. 3.3 in Fig. 1(a) is identical to the Kronecker product of the pairwise similarity matrix S. In standard spectral clustering algorithm, the eigenvector of the graph Laplacian matrix conveys important information about the underlying manifold structures and is used to guide clustering. Similarly, we now establish the relationship between the eigenvector for the pairwise and pairs-to-pairs Laplacian matrix corresponding to decomposable tensor similarity. The detailed proof of Theo. 3.4 is also provided in SI Appendix, Section 1.1. Furthermore, Theo. 3.4 combines with the aforementioned theorem to build a bridge between the regular pairwise similarity and the unfolded tensor similarity (Fig. 2). It also demonstrates that the eigenvector of the Laplacian matrix for the tensor similarity matrix is simply the Kronecker product of the eigenvector of the Laplacian matrix for the regular pairwise similarity; that is, tensor similarity can be used to achieve equivalent clustering results to the standard spectral graph when it is decomposable. We sketch the equivalence in Fig. 2.

Non-decomposable Tensor Similarity Provides Complementary Information for Pairwise Similarity
The decomposable tensor similarity is the Kronecker product of pairwise similarity. However, there exist some inherit drawbacks of pairwise similarity. The major drawback is that pairwise similarity defined by a unique distance function is scalar and thus easily distorted by noise or outliers.
To overcome this drawback, we can use the non-decomposable tensor similarity to provide complementary information, which the pairwise similarity fails to obtain. Additionally, such high-order similarity among pairs characterizes the local manifold among the samples. Therefore, tensor similarity defined for the two pairs could be in a high dimension and not be necessarily scalar.
In view of this concept, we use the following distance definition for two pairs (i, j) and (k, l): where de(·, ·) denotes the distance between two samples. Parameter ε is a given small parameter less than 0.001 to overcome the instability caused by a zero denominator. The defined distance measurement is indecomposable and achieves a maximum value when (1) pair (i, j) falls into cluster c; and (2) pair (k, l) falls into cluster c ′ , and c = c ′ . It computes the ratio of the between cluster distance and the within cluster distance so that it can well separate pairs that belong to different clusters.
Naturally, we define the tensor similarity based indecomposable distance measurement as T i,j,k,l = e −σd(i,j,k,l) , where parameter σ is the kernel size. Tensor similarity T is non-decomposable and can greatly enhance the capability of adaption of clustering due to the modification that uses various distance functions. Analogous to the decomposable case, we obtain the unfolded tensor similarityT as the similarity matrix of pairs and compute its dominant eigenvector v of the corresponding pairs-to-pairs Laplacian matrixL. As shown earlier, by reshaping eigenvectorv into a m × m dimension matrix S n , it can be viewed as a new pairwise similarity of data in lower dimensional space. Therefore, the new high-order similarity S n generated by the eigenvector contains the spatial structure information of data that can serve as complementary information for pairwise similarity.

Dynamic Fusion of the Regular Pairwise and High-Order Similarity for Clustering
The unfold non-decomposable tensor similarity T conveys a high-order relationship among the samples and thus preserves the local structure of data. In comparison, regular pairwise similarity only conveys the direct sample-tosample relationship. Hence, we can fuse direct and local information to achieve a more accurate result. To accomplish this task, we propose integrating new high-order similarity with pairwise similarity, called IPS2, to boost the clustering performance. The proposed IPS2 aims to solve the following optimization equation: (1) where S denotes the regular pairwise similarity matrix. S i , i ∈ c is obtained by reshaping the first c dominant eigenvectors of the corresponding Laplacian matrix of unfolded tensor similarity T . The c leading eigenvectors contain different levels of complementary label information of the samples, shown in Fig. 2. The weighting variables w i compete to capture a comprehensive structure with highorder complementary information. Variable S t is the fused similarity and is constrained by the rank norm to ensure the block structure for a more accurate clustering result.

NUMERICAL SCHEME FOR HIGH-ORDER CLUS-TERING
In this section, we provide a numerical scheme to solve the proposed IPS2 algorithm in Eq. (1).
Given a raw dataset, the first step is to construct nondecomposable tensor similarity T by calculating the affinity relationship of pairs (Fig. 3). It has a size of m 4 for m samples. The value is gargantuan, even for moderate size m; thus, it is impractical to compute all possible pair combinations exhaustively. Alternatively, we use a KD-tree for the computation and save the distances among the top k nearest neighbors for two pairs. For the others, the value of similarity is assigned to a small constant. Therefore, we obtain sparse tensor similarity T and unfold it into an m 2 × m 2 matrixT .
The integrated similarity matrix S t is estimated by solving Eq. (1). The rank constraint on S t ensures that there are at most c clusters. The rank constraint can be equivalently reformulated as max c c i=1 δ i (L), where L t is the corresponding Laplacian matrix of S t and δ i (L t ) denotes the i-th smallest eigenvalues of it [27]. Furthermore, by Ky Fan's Theorem [28], one has: for some orthogonal matrix P.
Therefore, the minimization in Eq. (1) could be rewritten as: subject to: It is an convex optimization problem and thus can be solved by alternative minimization methods. In particularly, the main problem is decomposed into three subproblems. Each subproblem solves one variable while fixing other variables. The three subproblems are solved iteratively until convergent.
Subproblem 1: By fixing w i , i ∈ c and P to solve variable S t , objective equation (2) take a derivative with respect to S t : Thus, solution is given by By fixing w i , i ∈ c and S t to update P, the minimization problem in (2) can simplified as min P T r(P T L t P), subject to: Its solution is given by the top c eigenvectors of matrix L t .
Subproblem 3: For the weight w i bounded in interval [0,1], we reshape similarity matrices S i , S, S t into vector v i , v and v t respectively. Thus, the approximation of w i is given by the linear regression of The aforementioned three steps update iteratively until convergence. We sketch the pseudocode of algorithm in Alg. 1.

EXPERIMENTAL RESULTS
In this section, we conducted extensive experiments on both synthetic datasets and real-world datasets to demonstrate the effectiveness of our proposed model, and provided a comprehensive analysis of our method.

Evaluation Metrics and Baseline Methods
We used five widely used metrics to evaluate the performance of the proposed method (SI Appendix, Section 1.2): accuracy (ACC), adjusted rand index (ARI), F-score(F-SCORE), normalized mutual information (NMI), and purity (Purity). The larger the value, the better the performance. Five methods were adopted to serve as baselines. A brief introduction and the parameter settings of these approaches is as follows: • Spectral clustering (SC) [29]: Run spectral clustering to demonstrate the improvement of other methods.
• Clique averaging+ncut (CAVERAGE) [30]: The hypergraph is approximated using clique averaging and resulting graph is partitioned using the normalized cuts algorithm.
• Finding hypergraph communities(HGC) [31]: Introduce a hypergraph generative model with a builtin group structure and derive a variational Bayes algorithm for finding network communities. We set parameters according to the authors' suggestion.

Experiments on Synthetic and Real-world Datasets to Demonstrate the Superiority of Tensor Similarity Term
We first tested the proposed method on two synthetic datasets. The first dataset was composed of 50 samples and 60 features, which were generated by a normal distribution. These samples belonged to three clusters and each subclusters contained 20, 20 and 10 samples, respectively. To further test the performance on the imbalanced dataset with highdimensional features, the second synthetic dataset contained 50 samples and 2,360 features and had the same mean and variance as the first dataset. The number of k nearest neighbors was 10.
We then conducted experiments on four real-world datasets to further demonstrate the performance of the proposed method. With the exception of the Soybean data, the numbers of features were all larger than those for the samples in the other datasets. Additionally, BBCSports and Yale are multiview datasets; thus, we selected one view for our experiments. The data statistics are summarized in Table 1. A detailed description and parameter settings of four data are as follows: • Soybean dataset is a small subset of the original soybean database containing 47 distinct instances. Each subject has 35 attributes to describe its growth indicators.  We applied the SC, CAVERAGE, HGC, and proposed IPS2 on the synthetic datasets and real-world datasets. To investigate the effectiveness of the tensor similarity measurement, we also compared the clustering results without the combination of pairwise similarity, which is denoted by PPC. We highlighted the best results in red to separate them from other method. Additionally, the sub-optimal results are highlighted in blue. For a fair comparison, each method was tested on these datasets 20 times. The mean value and standard deviation of the five measurements are recorded and are reported in Table 2.
First, we observed that our IPS2 uniformly achieved the superior results or comparable results compared with the other methods on most datasets, for example, two synthetic datasets, SCADI dataset, BBCSports dataset, and Yale dataset. On synthetic dataset 2, the performance of IPS2 was less satisfactory than CAVERAGE in terms of accuracy. However, the other four metric values for IPS2 were superior to those of the other methods. The good performance is attributed to the combination of the new highorder similarity and pairwise similarity and they worked together to reveal complete structure information of the data.
Second, we would like to emphasize the potential of incorporating tensor similarity to enhance the information description power of the IPS2 algorithm. For example, the performance of the SC, which only used the ordinary pairwise similarity, was always sub-optimal for IPS2. This result suggests that tensor similarity indeed enhanced the robustness of the algorithm and improved clustering performance. To enable a visual explanation of this potential, we plotted the heat map of SC, PPC, and IPS2 over the BBCSports dataset and Yale dataset in Fig. 4. Comparing the results in the first column and third column of Fig. 4, we observed that pairwise similarity barely described the structure and discriminated clusters of data on some datasets, for example, BBCSports dataset in Fig. 4(g). Instead, our algorithm combined with tensor similarity performed much better, and clearly indicated the diagonal structure over all datasets. This stable result provides evidence that strongly proves the effectiveness and superiority of tensor similarity.
Third, comparing the results in the first column and second column of Fig. 4, we could clearly see that tensor similarity indeed indicated the spatial information and preserved the structure information of pairs; unlike hypergraph clustering, the affinity relationship derived from tensor similarity was inadequate for the analysis of the structure of data. The pairwise similarities accross in the four datasets were contaminated by the noise or outliers and thus there remains many misclassified point within the off-diagonal areas. In comparsion, both the tensor and fused similarities possess clear boundary along the diagonal. Within the offdiagonal regions, there are few misclassified samples. Therefore, the tensor similarity became strongly complementary for a sample-to-sample relationship and enhanced the ro- bustness of algorithm. The performance of PPC in Table 2 proves this argument. Fourth, the hypergraph clustering method, such as CAV-ERAGE, performed better than SC but worse than IPS2, as shown in Table 2. This implies that high-order similarity explored by hypergraph is beneficial for exploring the underlying information of datasets. Despite this, similarity learned based on a hypergraph still has some limitations, so it is not always helpful for improving clustering performance. We plotted the heat map of CAVERAGE and IPS2 over synthetic dataset 1 and Yale dataset in Fig. 5. We observed that the structure of the integrated similarity learned by our algorithm was more salient than CAVERAGE because of the improvement of information integration with tensor similarity.

Robustness of Clustering over Imbalance Data with Increasing Features
To identify the stability and robustness of our algorithm, we further investigated the imbalance data in which the number of features was much greater than the number of samples. The imbalance level of a dataset is determined by the rate of the number of features to the number of samples. We fixed the number of samples at 55 and selected features from 60 to 2,360 to generate 14 new datasets over Yale dataset. Next, we tested the five algorithms on these 14 datasets (SI Appendix, Table 1) and plotted the NMI value of them in Fig. 6. As it is shown, the proposed algorithm outperformed other methods on all datasets, even on the dataset with an obvious imbalance level. In addition, the NMI of CAVERAGE and SC shown that hypergraph clustering model cannot improve the clustering performance apparently when there exist an imbalance level on the dataset, e.g. dataset with 2,160 features. Such result suggests that the tensor similarity plays a strong coordinated role in enhancing the performance and robustness of IPS2.
To better understand the superiority of IPS2, we focused on the performance of SC, PPC, and IPS2, applying three algorithm over synthetic dataset 2 with the number of features varying from 60 to 1,560. The performance is shown in Fig. 7 and the growth rate of the NMI gain of IPS2 compared with SC is also included to enable the visual comparison of results (SI Appendix, Table 2). As shown, the proposed algorithm outperformed the other methods on all datasets, even on the dataset with an obvious imbalance level. The performance of the SC algorithm scarcely grow when the number of features was up to 1,260, whereas that for other increased. Additionally, the NMI gain of IPS2 increased from 0.01 to 0.13 and achieved the largest value on the last dataset, which suggests that the more apparent the imbalance level of the dataset, the more evident the advantage of integrating the tensor similarity.

CONCLUSIONS
We incorporate the high-order tensor similarity among the samples-to-samples to boost the clustering performance. This is motivated by that the performance of most of the current clustering models relies on sample-to-sample similarity, whereas the pairwise similarity is prone to corruption by noise or outliers, and thus deteriorates the subsequent clustering. We introduced two types of tensor similarity: the decomposable tensor similarity and non-decomposable tensor similarity. We proved that the decomposable tensor similarity is the Kronecker product of the usual pairwise similarity. Then, we focused on the non-decomposable tensor similarity and demonstrated that it provides complementary information, which pairwise similarity does not. Besides, the information preserved by the non-decomposable tensor similarity is inadequate in terms of fully understanding the fine-scale view of data. Finally, we proposed a model, called IPS2 to fuse the tensor similarity and pairwise similarity to enhance the clustering performance. We compared the performance of our algorithm with that of the classical spectral clustering method and two existing hypergraph clustering algorithms on synthetic datasets and real-world datasets. In all experiments, the IPS2 algorithm outperformed its competitors both in term of clustering accuracy and clustering robustness to feature changes in all datasets. Our study manifests that incorporating tensor similarity as clustering metric has potential influence on effectiveness and robustness of clustering performance on the imbalance datasets.

ACKNOWLEDGMENTS
This work was partially supported by the National Natural Science Foundation of China (61472145, 61372141,61771007),  We briefly proof the properties of Kronecker product which are used in our algorithm. Definition 1. Let A ∈ R m×n , B ∈ R p×q . Then the Kronecker product (or tensor product) of A and B is defined as the matrix Proof. Simply verify that Let A ∈ R n×n have eigenvalues λ i , i ∈ n, and let B ∈ R m×m have eigenvalues µ j , j ∈ m. Then the mn eigenvalues of A ⊗ B are λ 1 µ 1 , · · · , λ 1 µ m , λ 2 µ 1 , · · · , λ 2 µ m , · · · , λ n µ m . Moreover, if x 1 , · · · , x p are linearly independent right eigenvectors of A corresponding to λ 1 , · · · , λ p (p ≤ n), and z 1 , · · · , z q are linearly independent right eigenvectors of B corresponding to µ 1 , · · · , µ q (q ≤ m), then x i ⊗ z j ∈ R mn are linearly independent right eigenvectors of A ⊗ B corresponding to λ i µ j , i ∈ p, j ∈ q.
Proof. Suppose that x and z are eigenvectors of A and B, respectively. The basic idea of the proof is as follows: Theorem 3.3. If the tensor similarity T is decomposable for some pairwise similarity S, i.e., T ijkl = S(i, j) * S(k, l), for i, j, k, l ∈ m. Then the unfolded similarity matrix satisfiesT = S ⊗ S.
Proof. Given a unfolded tensor similarity matrix each element ofT is the product of pair (i, j) and (k, l). According to the Def. 1, it is easy to know thatT = S ⊗ S holds.
Theorem 3.4. Let v andv being the eigenvectors associated with the pairwise Laplacian matrix L, and the pairs-topairs Laplacian matrixL, respectively, then the equalityv = v ⊗ v holds. Moreover, by unfolding the similarity matrix v * v T into a vector, it is the leading eigenvector of the Laplacian matrixv.
Proof. We first investigate the relationship between the normalized pair-to-pair Laplacian matrixL and pairwise Laplacian matrix L. The normalized pairwise Laplacian matrix computed by L = D − 1 2 SD − 1 2 where D is a diagonal matrix with each element D ii = m j=1 (S) ij . Thus, it is natural to underline thatD = D ⊗ D holds.
Then according to Theo. 3.1, we prove that normalized Laplacian matrix of pairs and pairwise Laplacian matrix also followed this property.L Based on Theo. 3.2, we prove thatv = v ⊗ v holds. Since the eigenvector v is an embedding of data, each element of v represents the power of a single point. Similarly, elements ofv can be viewed as the power of pairs which is similar to the pairwise similarity of two vertices. Furthermore, we rewritev as m × m dimension matrix S n and plot the heatmap of S n and v * v T in figure 1. It can be clearly seen that S n = v * v T , that is to say, unfolding the similarity matrix v * v T into a vector, it is the leading eigenvector of the Laplacian matrixv.

S.1.2 Details of Evaluation Metrics
We used five widely used metrics to evaluate the performance of the proposed method: accuracy (ACC), adjusted rand index(ARI), f-score(F-SCORE), normalized mutual information (NMI), and purity (Purity). For tested data with m where n ij denotes the number of samples with true label i and predicted label j. Parameter n i denotes the number of samples in the i-th cluster. In addition to ACC, ARI, F score and NMI, Purity is another frequently used evaluation metric which measures the pureness of the predicted clusters, with a larger value indicating a better prediction. It is defined as P urity(l,l) = 1 n k max j |l k l j |. Suppl.

S.2 Experiment on Synthetic Data to Test the Robustness of IPS2 over Dimension Imbalance
To identify the stability and robustness of our algorithm, We further investigate the imbalance data in which the number of features is much more than samples. The imbalance level of a dataset is decided by the rate of the number of features to the number of samples. We fix the number of samples as 55 and select features from 60 to 2,360 to generate 14 new datasets over Yale dataset. The results of five algorithms on these 14 datasets is shown in SI Appendix, Table 1.
To better understand the superiority of IPS2, we focus on the performance of SC, PPC, and IPS2, displaying three algorithms over synthetic dataset 2 with the number of features vary from 60 to 1,560. The performance of them are provided in SI Appendix, Table 2. To facilitate the visual comparison of results, the growth rate of the NMI gain of IPS2 compared to SC is also included.