Consensus graph and spectral representation for one-step multi-view kernel based clustering

Knowledge-Based Systems 241 (2022) 108250 Contents lists available at ScienceDirect Knowledge-Based Systems journal homepage: www.elsevier.com/locate/knosys Consensus graph and spectral representation for one-step multi-view kernel based clustering S. El Hajjar b, F. Dornaika a,b,c,∗, F. Abdallah d,e, N. Barrena b aSchool of Computer and Information Engineering, Henan University, Kaifeng, China bUniversity of the Basque Country UPV/EHU, San Sebastian, Spain cIKERBASQUE, Basque Foundation for Science, Bilbao, Spain dLebanese University, Beirut, Lebanon eLuxembourg Institute of Socio-Economic Research (LISER), Esch-sur-Alzette, Luxembourg article info Article history: Received 29 April 2021 Received in revised form 17 January 2022 Accepted 19 January 2022 Available online 25 January 2022 Keywords: Multi-view clustering One-step clustering Graph learning Spectral representation Nonnegative embedding Automatic weighting Clustering algorithms abstract Recently, multi-view clustering has received much attention in the fields of machine learning and pattern recognition. Spectral clustering for single and multiple views has been the common solution. Despite its good clustering performance, it has a major limitation: it requires an extra step of clustering. This extra step, which could be the famous k-means clustering, depends heavily on initialization, which may affect the quality of the clustering result. To overcome this problem, a new method called Multiview Clustering via Consensus Graph Learning and Nonnegative Embedding (MVCGE) is presented in this paper. In the proposed approach, the consensus affinity matrix (graph matrix), consensus representation and cluster index matrix (nonnegative embedding) are learned simultaneously in a unified framework. Our proposed method takes as input the different kernel matrices corresponding to the different views. The proposed learning model integrates two interesting constraints: (i) the cluster indices should be as smooth as possible over the consensus graph and (ii) the cluster indices are set to be as close as possible to the graph convolution of the consensus representation. In this approach, no post-processing such as k-means or spectral rotation is required. Our approach is tested with real and synthetic datasets. The experiments performed show that the proposed method performs well compared to many state-of-the-art approaches. ©2022 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/). 1. Introduction Clustering is one of the most important research topics in machine learning, which aims to group samples into different groups, called clusters, without knowing their labels [1,2]. In the last decades, many clustering approaches have been developed. In particular, multi-view clustering algorithms have been used and developed to obtain additional information to improve the final clustering [3–9]. Among these methods, Spectral Clustering (SC) [10–13] methods are the most popular approaches due to their well-defined mathematical framework and ease of implementation. After constructing the similarity matrix between the data points, these methods generate a nonlinear projection of the data by mapping the dataset into a space where clusters can be easily identified (spectral embedding). A major drawback of these methods is the use of a post-processing step such as k-means to obtain the final clustering result, which can be affected by the initialization or the presence of outliers. Matrix ∗Corresponding author at: University of the Basque Country UPV/EHU, San Sebastian, Spain. E-mail address: [email protected] (F. Dornaika). factorization methods [14,15] can be used for dimensionality reduction. For example, the method in [15] called Integration by Matrix Factorization (IMF). This method generates different representative clustering matrices computed independently for each view, generates an intermediate matrix for all views, and then performs a factorization process on this matrix to reconcile the different clustering matrices generated from the different views. Matrix factorization methods have a low computational cost compared to other methods. This is because factorization of a particular matrix decomposes it into its constituent parts, which can also simplify the matrix operations as they are applied to the obtained matrices and not to the original complex matrix. However, these methods cannot deal with the nonlinearity of the data. To deal with the problem of nonlinearity of data, several approaches have proposed a solution based on multiple kernels [7,16,17]. With these methods, the data is mapped into a space where it is linearly separable. However, it is noted that multi-view clustering still needs improvement. To address this issue, in this paper we present a novel approach that provides a consistent non-negative embedding matrix to determine the final cluster assignment. Our proposed method estimates the clustering of the data directly without any additional post-processing. https://doi.org/10.1016/j.knosys.2022.108250 0950-7051/©2022 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/bync-nd/4.0/). S. El Hajjar, F. Dornaika, F. Abdallah et al. Knowledge-Based Systems 241 (2022) 108250 It enforces that the cluster index matrix is a kind of convolution of a unified spectral representation over a consistent graph. The method we propose is called multi-view clustering via consensus graph learning and nonnegative embedding (MVCGE). It can overcome some drawbacks of other approaches. The proposed method can simultaneously provide the consistent similarity graph, the non-negative cluster index matrix and the unified spectral projection matrix across all views. Moreover, this method automatically calculates the weight of each view without using any additional parameters. The proposed method combines the advantages of graph-based methods and multiple kernel methods. In other words, our method retains two interesting properties that the current methods NESE in [18] and MVCSK in [19] do not have simultaneously. The first property, inspired by NESE, is the non-dependence on a particular clustering algorithm such as k-means clustering. The other property (inspired by MVCSK) is the simultaneous estimation of a consistent unified graph and a unified spectral representation. Since our method combines the advantages of NESE and MVCSK, the main goal of our study is to outperform the previous two methods. Therefore, these two methods are used as the main competing methods in our study. The contributions of the paper are summarized below. 1. Unlike other approaches based on multilevel learning, our method can simultaneously provide the consensus similarity matrix, the nonnegative index cluster matrix, the spectral projection matrix, and the weight of each view automatically. 2. It generates the final clustering assignment directly without any post-processing step. Our method inherits the advantages of matrix factorization methods and graph based methods. 3. The proposed model successfully finds nonlinear interactions between different views. This method is able to compute the exact graph considering the underlying correlations from numerous views by using a kernel representation of each view. 4. The cluster index matrix, which is the consequence of the convolution of the coherent spectral projection matrix over the coherent graph, is learned as part of the proposed learning technique. 5. It has been validated on real and synthetic datasets. This validation shows that this approach can give better results compared to state-of-the-art clustering methods. The rest of the paper is organized as follows. Section 2introduces the main concepts and some related work. Section 3describes our proposed method in detail. Section 4reports experimental results obtained on real and synthetic datasets. Section 5concludes the paper. 2. Preliminaries and related work 2.1. Notations We consider a data matrix Xvwith ndata points as (xv 1,xv 2,..., xv n)∈Rdv×n, where dvis the number of features in the corresponding view v. We represent the matrices in bold uppercase letters, the vectors in bold lowercase letters, and the constants in non-bold letters. The trace of a matrix Mis denoted by Tr(M) and its transpose by MT. The Frobenius norm of Mis given by ∥M∥F= ∥M∥2=√∑n i=1∑d j=1|Mij|2.I,1n,Dand Lare the identity matrix, the column vector with nelements equal to one, the diagonal matrix, and the Laplacian matrix of the graph, respectively. The number of clusters is denoted by K. The similarity matrix, the nonnegative embedding matrix, the spectral projection matrix, and the kernel matrix are denoted by S,H,Pand K, respectively. 2.2. Related work Recently, several multiview clustering approaches have been proposed. The current approaches can be divided into several groups: Spectral clustering algorithms [12,13,20,21], Graph based clustering algorithms [22], Weighted multiview clustering approaches [10,21,23–25], Automatically weighted multiview clustering algorithms [19,26–28], Multiview subspace based clustering approaches [29,30], Kernel based Approaches [19], Matrix factorization approaches [15,18,31], Nonnegative matrix factorization methods [18,32], etc. In this section, we present several methods that belong to these categories. A popular category of approaches is Spectral clustering [12,13,20,21]. This method constructs a similarity graph between data points and then constructs a data representation matrix using the eigenvectors of the corresponding Laplacian of the graph. Therefore, a postprocessing step is used to obtain the final clustering assignment. An example of a spectral clustering algorithm is the famous cotraining clustering algorithm [12], which adjusts the similarity matrix of a given view based on the clustering result of another view so that the same instance is placed in the same cluster in different views. Moreover, co-regulated spectral clustering [13] combines the similarity matrices obtained from different views with an adaptive scheme to obtain the result. weighted multiview clustering approaches [10,23–25] assign weights to each view to account for the contribution of each view to the final clustering result. Moreover, these approaches use a consistent scheme to merge the different views. A drawback of these approaches is the use of additional weighting parameters. To overcome this drawback, Automatically weighted multi-view clustering algorithms have been proposed [19,26–28]. Moreover, another approach related to the above categories is presented, which extends the spectral clustering algorithm with the idea of weighted views. This method is called Adaptive Weighted Procrustes (AWP) [21]. The final clustering assignment of this method is achieved by spectral rotation. Moreover, this method provides accurate clustering with low computational cost. Another famous category named Multiview Subspace based Clustering approach (MVSC) was introduced in [29,30] to learn the best and consistent representation of the data. Moreover, a Multi-view Learning method with Adaptive Neighbors (MLAN) is proposed in [33] to jointly learn the similarity graph and perform the final clustering assignment. The kernel-based approaches (e.g., [19]) are used to overcome the problem of nonlinearity of the data by mapping them to a space in which they are linearly separable, and then they solve the problem caused by the multiple shapes of the data. The matrix factorization approaches (e.g., [15,18,31]) are used because of their low computational cost, which makes them efficient for dimensionality reduction. They can provide high clustering performance compared to other methods. However, this category of clustering methods cannot handle nonlinear data. In [32], the authors propose a Non-negative Matrix Factorization (NMF) approach that uses dual constraints. This approach exploits the labeling of some images and the sparsity of representations. In [34], the authors introduced a unified framework for Joint clustering and distance metric learning. These are solved via rank reduced regression. The approach provided some new insights for learning a clustering that adopts distance metric learning. In [35], the authors presented an Ensemble clustering method based on efficient propagation of clusterwise similarities via random walks. The work of [36] proposed a Locality Adaptive Latent MultiView Clustering (LALMVC) method. It simultaneously learns the latent consensus representation via linear transformations, the joint spectral representation and the consensus graph. The learned consensus graph matrix is then used in spectral clustering to obtain a cluster index matrix. 2 S. El Hajjar, F. Dornaika, F. Abdallah et al. Knowledge-Based Systems 241 (2022) 108250 Fig. 1. Illustration of the proposed method. In [37], the authors propose a model in which the individual graphs, a fused graph, and a spectral projection are estimated simultaneously. Self-representativeness of the data was used in estimating the individual graphs. In [38], a non-negative matrix factorization with multiple views is proposed. The model estimating the view-based two non-negative matrices integrates manifold regularization in the low-dimensional subspace and the pairwise consistencies of interview similarity in these lowdimensional subspaces. In [17], the authors jointly estimate an optimal graph and an adequate consensus kernel for clustering by forcing the global kernel matrix to be a convex combination of a set of basis kernels. Their proposed model enforces a regularization of the unified graph and the final kernel matrix. In [39], the authors use the correntropy-induced metric (CIM) to deal with the noise that exists in each view. They use viewspecific embedding from an information theoretic perspective. In [40], the authors propose the algorithm Cross-view Matching Clustering (COMIC), which can cluster data with multiple views. The algorithm can also estimate the number of clusters. COMIC provides cross-view consensus on view-specific similarity graphs instead of view-specific data representations. In [41], the authors provide an overview of multi-view clustering. This survey describes a wide range of multi-view clustering methods, including both generative and discriminative approaches. Furthermore, the authors of this survey divide these algorithms into many groups and give numerous examples of how they are used for multi-view clustering. In [42], the authors introduce a method called Multi-view cluster analysis with incomplete data to understand treatment effects. Indeed, sometimes data entries are missing in several of the views. Current multiview co-clustering approaches are not able to successfully deal with incomplete data, especially when there are many patterns of incomplete data. By using an indicator matrix whose entries indicate which data items are present, and measuring clustering performance based solely on the observed values, this method provides an improved approach for multi-view coclustering algorithms to deal with the missing data problem. Moreover, this method is less prone to imputation uncertainty than standard methods that substitute missing data to perform regular multi-view data clustering. 3. Proposed approach We introduce a new approach called Multi-View Clustering via Consensus Graph Learning and Nonnegative Embedding (MVCGE), which combines the advantages of graph learning methods and matrix factorization methods. MVCGE achieves the clustering results without any additional step. Fig. 1 shows an illustration of our proposed multi-view clustering method. The proposed method can simultaneously estimate (1) the consensus similarity matrix, (2) the consensus data representation matrix, and (3) the nonnegative cluster index matrix. Moreover, the weight of each view is automatically updated without any additional parameters. Given nsamples and Vviews (feature vectors), the data matrix of each view can be represented as Xv= [xv 1,xv 2,...,xv n] ∈ Rdv×n, where dvrepresents the number of features in the corresponding view, where v= 1,...,V. The corresponding kernel matrices are denoted by Kv. The dataset is to be grouped into Kclusters based on the V views. The unknown matrices are S∈Rn×n,P∈Rn×K, and H∈Rn×K. Our proposed method estimates these matrices simultaneously by integrating several properties such as graph construction using self-representation of data, smoothness of cluster labels, and spectral data convolution. Thus, our proposed criterion has three main terms. To obtain the first term of our proposed criterion, we used the idea of MVCSK method in [19]. To estimate a consistent graph matrix, this method exploits the property of the data to express itself, where the data is mapped nonlinearly. Therefore, the consistent graph matrix S should satisfy the condition min ∑V v=1∥Φ(Xv)−Φ(Xv)S∥ = ∑V v=1√Tr (Kv−2KvS+STKvS), where Kv=Φ(Xv)TΦ(Xv) and Φ() is a given nonlinear mapping, which should not be explicitly stated, since only the knowledge of the kernel matrix Kv is needed. Moreover, to avoid the trivial solution of the consistent graph matrix, a regularization term is used to control the values in this matrix. The first term is as follows: min S V ∑ v=1√Tr (Kv−2KvS+STKvS)+α∥S∥2 2s.t.S≥0.(1) 3 S. El Hajjar, F. Dornaika, F. Abdallah et al. Knowledge-Based Systems 241 (2022) 108250 Fig. 2. Visualization of the original synthetic datasets: (a) Tetra, (b) Hepta, and (c) Chainlink. It is also important to assign a weight parameter to each view to represent the contribution of each view to the clustering process. The square root in Eq. (1) is used to automatically update the weight of each view [19] automatically. The weight of the view wvis given by: wv=1 2√Tr (Kv−2KvS+STKvS) .(2) By using the weight expression in Eq. (2), it can be shown that problem (1) is equivalent to the following problem: min S V ∑ v=1 wvTr (Kv−2KvS+STKvS)+α∥S∥2 2s.t.S≥0.(3) The clustering result is obtained from the nonnegative embedding matrix H, which provides the cluster indices by taking the index of the highest element in the row vector Hi∗∈RK. Since the matrix His used for the final cluster assignment, it is important to use a smoothing term for this matrix so that it is more coherent with the graph entries. The smoothing term ensures that two data points xv iand xv jthat are similar (i.e., the value of the corresponding value in the similarity matrix Sij is large) are necessarily in the same cluster (i.e., the corresponding cluster index Hi∗and Hi∗are close). Therefore, the second term of our criterion is given by: min H 1 2∑ i∑ j ∥Hi∗−Hj∗∥2Sij =min HTr (HTL H),(4) where L=D−S∈Rn×nis the Laplacian matrix of the consistent graph matrix, and Dis a diagonal matrix whose elements are given by: Dii =∑n j=1 Sij+Sji 2. The third term of our proposed method states that the cluster index of the ith instance (the row vector Hi,∗) is set to the convolution of the spectral representation Pwith the ith row of the graph matrix Si,∗. This approach has two main advantages. First, the clustering is performed in a single step. Second, the clustering uses the consolidated spectral representation of the neighbors obtained in the consensus graph. Moreover, inspired by the principle of data convolution, the nonnegative embedding matrix used to obtain the final clustering assignment will be equal to ‘‘H=max(S P,0)". This means that the nonnegative matrix is the result of the convolution of the spectral data representation with the graph. The third term of our criterion binds the cluster index label to the consensus spectral representation. Therefore, the cluster index matrix should satisfy the following condition: min H≥0∥H−S P∥2 F(5) where the matrix P∈Rn×Kis a consensus data representation. In our work, it is initialized to a unified spectral representation of the data. The proposed method tunes this representation according to a global objective. Since the matrix Pis orthogonal, Eq. (5) can take another form to illustrate the factorization of the graph matrix Susing the nonnegative embedding matrix Hand the spectral projection matrix P. It can be written as: min H,P∥S−H PT∥2 Fs.t.H≥0,PTP=I.(6) Our final objective function is obtained by adding the three terms from Eqs. (1),(4), and (6). min S,P,H V ∑ v=1 wvTr (Kv−2KvS+STKvS)+α∥S∥2 2 +λ1Tr (HTL H)+λ2∥S−H PT∥2 2 s.t.S≥0,PTP=I,HTH=I,H≥0,(7) where α,λ1and λ2are three regularization parameters. Optimization. We use an iterative update procedure to solve our objective function. In MVCGE, three matrices are unknown: S,H, and P. An alternating optimization scheme is used for the optimization procedure. We proceed as follows: Step 1: Fix all, estimate H: The problem (7) is: min HTr (HTL H)+λ2 λ1 ∥S P −H∥2 2s.t.HTH=I,H≥0.(8) Vanishing the derivative of (8) w.r.t. Hyields: H=(L+λ2 λ1 I)−1λ2 λ1 S P.(9) To satisfy the orthogonality and non-negativity constraints, an orthogonalization step is first applied to the obtained H, then the negative values of Hare set to zero. Step 2: Fix all, estimate P: The problem (7) becomes: min P∥S−H PT∥22.(10) Since Pis orthogonal, i.e., PTP=I,Pis obtained by performing the singular value decomposition of STH. Let UΣVT=SVD (STH), then the solution of (10) is given by: P=U VTwith UΣVT=SVD (STH).(11) Step 3: Fix all, estimate S: 4 S. El Hajjar, F. Dornaika, F. Abdallah et al. Knowledge-Based Systems 241 (2022) 108250 Fig. 3. t-SNE of the spectral projection and nonnegative embedding matrices obtained by the proposed clustering method MVCGE for different datasets. If we fix Hand P, we need to solve the following problem: min S V ∑ v=1 wvTr (Kv−2KvS+STKvS)+α∥S∥2 2 +λ1Tr (HTL H)+λ2∥S−H PT∥2 2s.t.S≥0.(12) After the spectral clustering analysis, we have the known identity: Tr (HTL H)=1 2∑ i∑ j Hi∗−Hj∗  2Sij =Tr (Q S),(13) where Hi∗is the ith row of H. The symmetric matrix Qdenotes the pairwise distance associated with the rows of the matrix H. It is given by Qij =1 2 Hi∗−Hj∗  2. Substituting Eq. (13) into Eq. (12), the latter becomes: min S V ∑ v=1 wvTr (Kv−2KvS+STKvS)+α∥S∥2 2 +λ1Tr (Q S)+λ2∥S−H PT∥2 2s.t.S≥0.(14) 5 S. El Hajjar, F. Dornaika, F. Abdallah et al. Knowledge-Based Systems 241 (2022) 108250 Fig. 4. Visualization of the two clusters obtained by three different methods for the Chainlink dataset. By making the derivative of Eq. (14) w.r.t. Svanish, we obtain S as (ReLU() is the Rectified Linear Unit function): S=ReLU ⎧ ⎨ ⎩(V ∑ v=1 wvKv+(α+λ2)I)−1 ×(V ∑ v=1 wvKv+λ2H PT−1 2λ1Q)}.(15) Step 4: Fix H,P,and S,and update wv(v=1,...,V)using Eq. (2). The main steps of the proposed approach ‘‘Multi-view Clustering via Consensus Graph Learning and Nonnegative Embedding" (MVCGE) are summarized in Algorithm 1. Algorithm 1 MVCGE Input: Data samples in Vviews Xv∈Rn×dv, v =1,...,V. The graph matrices Sv, v =1,...,V. The spectral embedding matrices Pv, v =1,...,V. Parameters α,λ1,λ2. Output: The consensus graph matrix S. The consensus spectral representation matrix P. The cluster index matrix (nonnegative embedding matrix) H. Initialization: The weight of each view wv=1 V. Compute the kernel matrix Kvfor each view. Initialize Sand Pby taking the average of the matrices Svand Pv. Repeat Update Husing Eq. (9). Update Pusing Eq. (11). Update Susing Eq. (15). Update wvusing Eq. (2). Until convergence To initialize the two matrices Sand P, the efficient method used in [43] is used. This method finds the similarity matrix and the corresponding spectral projection matrix for each view. To 6 S. El Hajjar, F. Dornaika, F. Abdallah et al. Knowledge-Based Systems 241 (2022) 108250 Table 1 Description of the real datasets used in the paper. View COIL20 ORL Out-Scene BBCSport MSRCv1 1Intensity-1024 GIST-512 GIST-512 Intensity-3183 GIST-512 2LBP-3304 LBP-59 LBP-48 LBP-3203 LBP-256 3Gabor-6750 HOG-864 HOG-256 – Color moment-24 4– Centrist-254 Color mom.-432 – Centrist-254 5– – – – Sift-512 # Samples 1440 400 2688 544 210 # Classes 20 40 8 5 7 View Extended-Yale MNIST MNIST-1000 1Covariance ch9 gray-45 Resnet50-2048 Resnet50 Pooling-2048 2LBP-900 VGG16-4096 VGG16 FC1-4096 3– – – 4– – – 5– – – # Samples 1774 10000 1000 # Classes 28 10 10 obtain the initial unified matrix, the average of all the individual matrices is used. 4. Performance evaluation 4.1. Datasets The effectiveness of the proposed approach is evaluated using eight real image datasets and three synthetic datasets. The MNIST dataset is relatively large. Table 1 describes the real datasets. We also used three synthetic datasets: Tetra, Hepta, and Chainlink. They were selected from the Fundamental Clustering Problem Suite (FCPS). For these datasets, only one view is considered. Tetra contains 400 3D points divided into four groups. Hepta contains 212 3D points grouped into seven well-defined clusters with different variances. Chainlink is formed by two clusters that are not linearly separable. It consists of 1000 3D points. These datasets are visualized in Fig. 2 [44]. All these synthetic datasets use 3D data points pi∈R3. The 3-dimensional datasets are transformed into high-dimensional datasets xi∈R100 using the following linear and nonlinear mappings xi=σ(Uσ(W pi)) where the sigmoid function σis used to introduce nonlinearity, W∈R10×3and U∈R100×10 are two matrices whose entries follow the Gaussian distribution with zero-mean unit variance i.i.d. 4.2. Experimental setup Several competing methods are used for comparison: (1) Cotraining approach for multi-view Spectral Clustering (CotSC) [12], (2) Co-regularized approach for multi-view Spectral Clustering (CorSC) [13], (3) Multi-view Learning Clustering with Adaptive Neighbors (MLAN) [33], (4) Self-weighted Multi-view Clustering with multiple graphs (SwMC) [45], (5) Affinity Aggregation for Spectral Clustering (AASC) [46], (6) Graph Learning for MultiView clustering (MVGL) [22], (7) Parameter-free Auto-weighted Multiple Graph Learning (AMGL) [28], (8) Multi-view clustering via Adaptively Weighted Procrustes (AWP) [21], (9) Autoweighted Multi-View Clustering via Kernelized graph learning (MVCSK) [19], (10) Multi-view spectral clustering via integrating Non-negative Embedding and Spectral Embedding (NESE) [18], (11) Sparse Multi-view Spectral Clustering (S-MVSC) [47], (12) Consistency-aware and Inconsistency-aware Graph-based MultiView Clustering (CI-GMVC) [48], (13) Multi-View Clustering in Latent Embedding Space (MCLES) [49] and (14) multi-view spectral clustering via Constrained Nonnegative Embedding (CNESE) [9]. We also report the Spectral Clustering best view result (SC) [20]. The clustering performance of the proposed approach is compared with other methods by using the authors’ source codes with the default or proposal parameter settings,1or by directly reporting the best experimental results from the corresponding published papers.2A Gaussian kernel function is used to construct the kernel matrix of each view. To initialize our algorithm, we use the same method as in [18], which constructs the similarity matrix of each view according to a smoothing constraint, an ℓ2regularization term, and a non-negativity constraint. Then, the corresponding spectral projection matrix of each view is computed, and the final unified similarity matrix and spectral projection matrix is the average of the corresponding matrix of all views. In this way, we obtain the initial values of the matrices Sand P. In our method, three parameters are used: α,λ1and λ2. The values of αare in the range [0.005 0.9], the values of the parameter λ1vary over the set {10−10, 10−9, 10−8, 10−7, 10−6, 10−5, 10−4, 10−3} and the values of the parameter λ2vary over the set {10−7, 10−6, 10−5, 10−410−3, 10−2, 10−1}. In our experiments, the range for each parameter is chosen to encompass a wide range. This ensures that the optimal values for these parameters are within this range. In selecting the values in these ranges, we used a grid search method. Grid search is a method for exhaustively searching a manually defined subset of the parameter space of a given algorithm. The number of parameters of the algorithm is the spatial dimension of the grid. So in our case, the grid is in a 3D space. This method starts by creating the grid, sampling the predefined regions. Then, for each parameter combination (represented by the nodes of the grid), a model is created to find the best parameter combination that provides the best clustering performance. The best clustering result is indicated by a cluster performance metric. To compare our method with other methods, we use four clustering performance metrics: Accuracy (ACC), Normalized Mutual Information (NMI), Purity, and Adjusted Rand Index (ARI). Their definition can be found in [50]. 4.3. Experimental results Our algorithm is tested on real and synthetic datasets. Table 2 shows the results obtained by MVCGE and some other methods on the datasets: ORL, Out-Scene, and Coil20. In this table, the highest scores are marked in bold. The proposed method MVCGE was superior on these datasets. For some competing methods listed in Table 2, the corresponding method is repeated in multiple trials, and then a standard deviation for each indicator is given in parentheses. From this table, we can see that our method 1This concerns SC, MVCSK, NESE, S-MVSC, CI-GMVC, MCLES and CNESE. 2This concerns the following methods: CotSC, CorSC, MLAN, SwMC, AASC, MVGL, AMGL and AWP. 7 S. El Hajjar, F. Dornaika, F. Abdallah et al. Knowledge-Based Systems 241 (2022) 108250 Table 2 Clustering performance on the ORL, Outdoor-Scene and Coil20 datasets. Dataset Method ACC NMI Purity ARI ORL SC-Best [20] 0.66 (±0.02) 0.76 (±0.02) 0.71 (±0.02) 0.67 (±0.01) AWP [21] 0.80 (±0.00) 0.91 (±0.00) 0.83 (±0.00) 0.76 (±0.00) MLAN [33] 0.78 (±0.00) 0.88 (±0.00) 0.82 (±0.00) 0.67 (±0.00) SwMC [45] 0.77 (±0.00) 0.90 (±0.00) 0.83 (±0.00) 0.62 (±0.00) AMGL [28] 0.75 (±0.02) 0.90 (±0.02) 0.82 (±0.02) 0.63 (±0.09) AASC [46] 0.82 (±0.02) 0.91 (±0.01) 0.85 (±0.01) 0.76 (±0.02) MVGL [22] 0.75 (±0.00) 0.88 (±0.00) 0.80 (±0.00) 0.55 (±0.00) CorSC [13] 0.77 (±0.03) 0.90 (±0.01) 0.82 (±0.03) 0.72 (±0.04) CotSC [12] 0.75 (±0.04) 0.87 (±0.01) 0.78 (±0.03) 0.67 (±0.03) NESE [18] 0.82 (±0.00) 0.91 (±0.00) 0.85 (±0.00) 0.75 (±0.00) MVCSK [19] 0.85 (±0.02) 0.94 (±0.01) 0.88 (±0.02) 0.81 (±0.02) S-MVSC [47] 0.80 (±0.02) 0.93 (±0.01) 0.82 (±0.02) 0.89 (±0.01) CI-GMVC [48] 0.81 (±0.00) 0.92 (±0.00) 0.85 (±0.00) 0.74 (±0.00) MCLES [49] 0.84 (±0.00) 0.94 (±0.00) 0.88 (±0.00) 0.79 (±0.00) CNESE [9] 0.87 (±0.00) 0.95 (±0.00) 0.89 (±0.00) 0.84 (±0.00) MVCGE 0.93 (±0.00)0.97 (±0.00)0.95 (±0.00)0.92 (±0.00) Out-Scene SC-Best [20] 0.47 (±0.01) 0.39 (±0.01) 0.57 (±0.01) 0.34 (±0.01) AWP [21] 0.65 (±0.00) 0.51 (±0.00) 0.65 (±0.00) 0.42 (±0.00) MLAN [33] 0.55 (±0.02) 0.47 (±0.01) 0.55 (±0.02) 0.33 (±0.03) SwMC [45] 0.50 (±0.00) 0.47 (±0.00) 0.50 (±0.00) 0.38 (±0.00) AMGL [28] 0.51 (±0.05) 0.45 (±0.03) 0.52 (±0.04) 0.34 (±0.05) AASC [46] 0.60 (±0.00) 0.48 (±0.00) 0.60 (±0.00) 0.35 (±0.00) MVGL [22] 0.42 (±0.00) 0.31 (±0.00) 0.43 (±0.00) 0.16 (±0.00) CorSC [13] 0.51 (±0.04) 0.39 (±0.03) 0.52 (±0.03) 0.31 (±0.02) CotSC [12] 0.38 (±0.02) 0.22 (±0.01) 0.39 (±0.02) 0.16 (±0.01) NESE [18] 0.63 (±0.00) 0.53 (±0.00) 0.66 (±0.00) 0.46 (±0.00) MVCSK [19] 0.65 (±0.01) 0.52 (±0.00) 0.65 (±0.01) 0.42 (±0.00) S-MVSC [47] 0.48 (±0.01) 0.54 (±0.02) 0.65 (±0.01) 0.46 (±0.04) CI-GMVC [48] 0.35 (±0.01) 0.31 (±0.00) 0.35 (±0.01) 0.19 (±0.00) MCLES [49] 0.65 (±0.00) 0.53 (±0.00) 0.67 (±0.00) 0.46 (±0.00) CNESE [9] 0.66 (±0.00) 0.55 (±0.00) 0.67 (±0.00) 0.47 (±0.00) MVCGE 0.70 (±0.00)0.55 (±0.00)0.70 (±0.00)0.47 (±0.00) COIL20 SC-Best [20] 0.73 (±0.01) 0.82 (±0.01) 0.75 (±0.01) 0.68 (±0.02) AWP [21] 0.68 (±0.00) 0.87 (±0.00) 0.75 (±0.00) 0.71 (±0.00) MLAN [33] 0.84 (±0.00) 0.92 (±0.00) 0.88 (±0.00) 0.81 (±0.00) SwMC [45] 0.86 (±0.00) 0.94 (±0.00) 0.90 (±0.00) 0.84 (±0.00) AMGL [28] 0.80 (±0.04) 0.91 (±0.02) 0.85 (±0.03) 0.74 (±0.07) AASC [46] 0.79 (±0.00) 0.89 (±0.00) 0.83 (±0.00) 0.76 (±0.00) MVGL [22] 0.78 (±0.00) 0.88 (±0.00) 0.81 (±0.00) 0.75 (±0.00) CorSC [13] 0.68 (±0.04) 0.78 (±0.02) 0.70 (±0.03) 0.62 (±0.03) CotSC [12] 0.70 (±0.03) 0.80 (±0.02) 0.72 (±0.03) 0.65 (±0.03) NESE [18] 0.77 (±0.00) 0.88 (±0.00) 0.82 (±0.00) 0.69 (±0.00) MVCSK [19] 0.65 (±0.04) 0.80 (±0.02) 0.70 (±0.03) 0.61 (±0.05) S-MVSC [47] 0.62 (±0.01) 0.86 (±0.02) 0.77 (±0.02) 0.97 (±0.02) CI-GMVC [48] 0.86 (±0.00) 0.94 (±0.00) 0.90 (±0.00) 0.83 (±0.00) MCLES [49] 0.79 (±0.00) 0.88 (±0.00) 0.83 (±0.00) 0.75 (±0.00) CNESE [9] 0.82 (±0.00) 0.88 (±0.00) 0.82 (±0.00) 0.78 (±0.00) MVCGE 1.00 (±0.00)1.00 (±0.00)1.00 (±0.00)1.00 (±0.00) and methods MVCSK, NESE S-MVSC, CI-GMVC, MCLES and CNESE perform best, so we can adopt them to test the other datasets. Table 3 shows a comparison between our method and the aforementioned methods for the BBCSport, MSRCv1, ExtendedYale, MNIST and MNIST-1000 datasets. For the MNIST dataset, which is a large image dataset (i.e., the number of samples is equal to 10000), each image has two deep descriptors, which means that the data already has some nonlinearity. Then, the use of the large kernel matrices can be skipped. Therefore, the criterion of our method reduces to the last two terms, where we only update the spectral projection matrix and the non-negative embedding matrix. Our method is applied to the synthetic datasets: Tetra, Chainlink, and Hepta. The results are presented in Table 4. 4.4. Ablation study Our proposed criterion (7) contains three main terms: the graph construction and its regularization, the smoothness term and the convolution term. To illustrate the relevance of the proposed criterion and its terms, we generate four different models with different combinations. These four different variants of MVCGE are: MVCGE-G, MVCGE-S, MVCGE-C and MVCGE-SC. (1) No graph regularization term in the global objective function (7) (i.e., αis set to zero), and we call the obtained method MVCGE-G, which means that only the smoothness and convolution terms in MVCGE are used, (2) No smoothness constraint (λ1is set to zero), and we call the obtained method MVCGE-S, (3) No convolution term (λ2is set to zero), and we call the obtained method MVCGEC, and (4) No smoothness and no convolution terms (λ1and λ2 are set to zero). This method is called MVCGE-SC because it is reduced to a consistent graph construction followed by a spectral clustering step. The results obtained with MVCGE-G, MVCGE-S, MVCGE-C, MVCGE-SC and MVCGE are summarized in Table 5. We used three datasets: ORL, MSRCv1 and Tetra. From the results in Table 5, we can see that the regularization of the graph is indeed crucial, since the last two terms depend on this graph. For the ORL and Tetra datasets, it can be seen from the table that the 8 S. El Hajjar, F. Dornaika, F. Abdallah et al. Knowledge-Based Systems 241 (2022) 108250 Table 3 Clustering performance on the BBCSport, MSRCv1, Extended-Yale, MNIST and MNIST-1000 datasets. Dataset Method ACC NMI Purity ARI MVCSK [19] 0.90 (±0.07) 0.82 (±0.02) 0.90 (±0.02) 0.85 (±0.07) BBCSport NESE [18] 0.72 (±0.00) 0.69 (±0.00) 0.75 (±0.00) 0.60 (±0.00) S-MVSC [47] 0.58 (±0.07) 0.67 (±0.01) 0.73 (±0.02) 0.83 (±0.04) CI-GMVC [48] 0.61 (±0.00) 0.46 (±0.00) 0.63 (±0.00) 0.36 (±0.00) MCLES [49] 0.88 (±0.00) 0.80 (±0.00) 0.88 (±0.00) 0.83 (±0.00) CNESE [9] 0.72 (±0.00) 0.68 (±0.00) 0.76 (±0.00) 0.60 (±0.00) MVCGE 0.98 (±0.00)0.94 (±0.00)0.98 (±0.00)0.95 (±0.00) MVCSK [19] 0.70 (±0.02) 0.59 (±0.03) 0.70 (±0.02) 0.50 (±0.04) MSRCv1 NESE [18] 0.77 (±0.00) 0.72 (±0.00) 0.80 (±0.00) 0.64 (±0.00) S-MVSC [47] 0.60 (±0.00) 0.69 (±0.02) 0.74 (±0.02) 0.79 (±0.01) CI-GMVC [48] 0.74 (±0.00) 0.72 (±0.00) 0.77 (±0.00) 0.59 (±0.00) MCLES [49] 0.90 (±0.01) 0.83 (±0.02) 0.90 (±0.01) 0.77 (±0.00) CNESE [9] 0.86 (±0.00) 0.76 (±0.00) 0.86 (±0.00) 0.72 (±0.00) MVCGE 0.93 (±0.00)0.87 (±0.00)0.93 (±0.00)0.85 (±0.00) MVCSK [19] 0.33 (±0.00) 0.42 (±0.00) 0.34 (±0.00) 0.18 (±0.00) ExtendedNESE [18] 0.43 (±0.00) 0.58 (±0.00) 0.47 (±0.00) 0.25 (±0.00) Yale S-MVSC [47] 0.48 (±0.03) 0.61 (±0.01) 0.60 (±0.01) 0.36 (±0.05) CI-GMVC [48] 0.32 (±0.00) 0.34 (±0.00) 0.35 (±0.00) 0.02 (±0.00) MCLES [49] 0.48 (±0.03) 0.48 (±0.00) 0.48 (±0.01) 0.10 (±0.05) CNESE [9] 0.60 (±0.00) 0.75 (±0.00) 0.60 (±0.00) 0.51 (±0.00) MVCGE 0.88 (±0.00)0.86 (±0.00)0.88 (±0.00)0.77 (±0.00) MVCSK [19] 0.49 (±0.00) 0.41 ( ±0.00) 0.50 (±0.00) 0.29 (±0.00) MNIST NESE [18]0.81 (±0.00)0.83 (±0.00) 0.85 (±0.00) 0.76 (±0.00) S-MVSC [47] 0.77 (±0.01) 0.81 ( ±0.01) 0.81 (±0.02) 0.76 (±0.07) CI-GMVC [48] 0.66 (±0.00) 0.71 ( ±0.00) 0.71 (±0.00) 0.51 (±0.00) MCLES [49] 0.80 (±0.00) 0.83 (±0.00) 0.85 (±0.00) 0.77 (±0.00) CNESE [9]0.81 (±0.00) 0.83 (±0.00) 0.86 (±0.00)0.78 (±0.00) MVCGE 0.81 (±0.00)0.83 (±0.00) 0.85 (±0.00) 0.77 (±0.00) MVCSK [19] 0.70 (±0.00) 0.61 ( ±0.00) 0.70 (±0.00) 0.52 (±0.00) MNIST-1000 NESE [18] 0.78 (±0.00) 0.79 (±0.00) 0.83 (±0.00) 0.71 (±0.00) S-MVSC [47] 0.66 (±0.02) 0.76 ( ±0.01) 0.76 (±0.00) 0.77 (±0.05) CI-GMVC [48] 0.65 (±0.00) 0.71 (±0.00) 0.73 (±0.00) 0.50 (±0.00) MCLES [49] 0.73 (±0.02) 0.72 (±0.01) 0.77 (±0.02) 0.58 (±0.04) CNESE [9] 0.77 (±0.00) 0.77 (±0.00) 0.81 (±0.00) 0.68 (±0.00) MVCGE 0.86 (±0.00)0.83 (±0.00)0.86 (±0.00)0.78 (±0.00) Table 4 Clustering performance on the three synthetic datasets. Dataset Method ACC NMI Purity ARI NESE [18] 0.64 0.75 0.75 0.63 Tetra MVCSK [19] 0.97 0.93 0.97 0.92 S-MVSC [47] 0.70 0.50 0.44 0.70 CI-GMVC [48] 0.63 0.52 0.67 0.43 MCLES [49] 0.85 0.88 0.89 0.80 CNESE [9] 0.66 0.62 0.75 0.54 MVCGE 1.00 1.00 1.00 1.00 NESE [18] 0.81 0.79 0.85 0.73 Hepta MVCSK [19] 0.89 0.85 0.89 0.80 S-MVSC [47] 0.66 0.63 0.47 0.70 CI-GMVC [48] 0.77 0.76 0.81 0.68 MCLES [49] 0.87 0.82 0.84 0.80 CNESE [9] 0.78 0.70 0.79 0.63 MVCGE 0.92 0.85 0.92 0.83 NESE [18] 0.93 0.69 0.93 0.73 Chainlink MVCSK [19] 0.63 0.05 0.63 0.07 S-MVSC [47] 0.67 0.14 0.78 0.12 CI-GMVC [48] 0.55 0.01 0.55 0.01 MCLES [49] 0.90 0.72 0.86 0.76 CNESE [9] 0.95 0.70 0.95 0.78 MVCGE 0.96 0.78 0.96 0.85 smoothness term has a larger impact on the clustering results. However, for the MSRCv1 dataset, the convolution term is more important than the smoothness term. This is normal and is due to the different types of datasets used in this work. The results obtained with MVCGE-SC show the importance of the last two terms in the objective function for all datasets. All these results indicate that the inclusion of all terms in the objective function Table 5 Ablation study with different models. The best performance for each indicator is in bold. Dataset Variant ACC NMI Purity ARI MVCGE-G 0.46 0.66 0.48 0.27 ORL MVCGE-S 0.75 0.88 0.76 0.72 MVCGE-C 0.86 0.94 0.88 0.81 MVCGE-SC 0.69 0.86 0.75 0.57 MVCGE 0.93 0.97 0.95 0.92 MVCGE-G 0.68 0.57 0.68 0.45 MSRCv1 MVCGE-S 0.72 0.63 0.74 0.54 MVCGE-C 0.70 0.60 0.70 0.50 MVCGE-SC 0.59 0.54 0.61 0.37 MVCGE 0.93 0.87 0.93 0.85 MVCGE-G 0.70 0.59 0.72 0.55 Tetra MVCGE-S 0.91 0.79 0.91 0.77 MVCGE-C 0.97 0.93 0.97 0.92 MVCGE-SC 0.56 0.35 0.57 0.33 MVCGE 1.00 1.00 1.00 1.00 contributed to the good clustering performance of our proposed method. 4.5. Analysis of results and method comparison According to Table 2, the performance of all multi-view clustering methods is better than that of SC-Best, which corresponds to the spectral clustering method applied to the best single view. In fact, the presence of multiple views brings additional information to the clustering method so that it can process the datasets better. The proposed method gives the best performance followed by NESE, MVCSK, S-MVSC, CI-GMVC, MCLES and CNESE 9