Hypergraph Learning-Based Semi-Supervised Multi-View Spectral Clustering

Abstract

Graph-based semi-supervised multi-view clustering has demonstrated promising performance and gained significant attention due to its capability to handle sample spaces with arbitrary shapes. Nevertheless, the ordinary graph employed by most existing semi-supervised multi-view clustering methods only captures the pairwise relationships between samples, and cannot fully explore the higher-order information and complex structure among multiple sample points. Additionally, most existing methods do not make full use of the complementary information and spatial structure contained in multi-view data, which is crucial to clustering results. We propose a novel hypergraph learning-based semi-supervised multi-view spectral clustering approach to overcome these limitations. Specifically, the proposed method fully considers the relationship between multiple sample points and utilizes hypergraph-induced hyper-Laplacian matrices to preserve the high-order geometrical structure in data. Based on the principle of complementarity and consistency between views, this method simultaneously learns indicator matrices of all views and harnesses the tensor Schatten p-norm to extract both complementary information and low-rank spatial structure within these views. Furthermore, we introduce an auto-weighted strategy to address the discrepancy between singular values, enhancing the robustness and stability of the algorithm. Detailed experimental results on various datasets demonstrate that our approach surpasses existing state-of-the-art semi-supervised multi-view clustering methods.

1. Introduction

Clustering is a fundamental task in machine learning and pattern recognition [1] that aims to partition given samples into several meaningful groups. With the rapid advancement of computer technology and the proliferation of various digital devices, a vast amount of multi-view data has emerged. Multi-view data generally refers to diverse information distinguished by attributes, sources, and characteristics of objects. Clustering methods that utilize multi-view data [2,3] can take advantage of the consistent and complementary information present in the data, resulting in learning outcomes that are more effective and accurate compared to using a single view of the data.

Multi-view clustering has become a major topic in artificial intelligence and pattern recognition over the past two decades, with numerous related methods being developed. For instance, Yang and Hussain [4] extended unsupervised k-means (UKM) clustering to a multi-view k-means clustering, called unsupervised multi-view k-means (U-MV-KM). The proposed U-MV-KM algorithm can automatically find an optimal number of clusters without any initialization for clustering multi-view data. Xia et al. [5] presented a robust multi-view spectral clustering scheme (RMSC) for mining valid information within graphs. This method considers potential noise in the input data and employs low-rank and sparse decomposition to determine the shared transfer probability matrix. After that, a standard Markov chain model is applied to the learned transfer probability matrix for clustering. In the work of Nie et al. [6], an auto-weighted multiple graph learning (AMGL) method was proposed which automatically and without human intervention assigns reasonable weights to each graph. Peng et al. [7] developed a cross-view matching clustering (COMIC) method for multi-view clustering that automatically learns almost all parameters. This approach eliminates heterogeneous gaps between multiple views and learns view-specific representations, thereby improving the clustering process. Furthermore, it has been found that algorithms can achieve impressive performance by incorporating deep metric learning networks into multi-view clustering [8,9]. Considering the scalability and generalization of the spectral embedding, Shaham et al. introduced a deep learning approach to spectral clustering and proposed a network called SpectralNet [10], which learns a map that embeds input data points into the eigenspace of their associated graph Laplacian matrix and subsequently clusters them.

Although the abovementioned studies have achieved satisfactory results, they have all been unsupervised. In reality, complex data structures, data noise, or data corruption can significantly impact the performance of unsupervised clustering methods. Moreover, due to different user preferences, there may be more than one reasonable clustering result for the same dataset. Consequently, it is crucial to incorporate a small amount of label information into multi-view clustering.

However, labeled samples are often scarce in practical applications, and only a limited amount of label information can be used to address clustering problems. As a result, semi-supervised clustering methods have emerged. Semi-supervised clustering aims to incorporate limited prior information into clustering algorithms to satisfy user preferences and enhance data partitioning accuracy. Through the persistent efforts of researchers, semi-supervised multi-view clustering methods [11,12] have made significant progress in both theoretical research and practical applications, with a continuous stream of novel related algorithms being proposed. For instance, Liang et al. [13] introduced a method called graph-regularized partially shared non-negative matrix factorization (GPSNMF), which preserves the inherent geometric structure of the data while leveraging the available label information. Bai et al. [14] improved the label propagation algorithm to utilize label information and pairwise constraints simultaneously. Their proposed method addresses the misalignment problem of label propagation, manages pairwise constraints, and effectively explores and mines various types of prior knowledge.

Although existing semi-supervised multi-view clustering methods have achieved satisfactory results, there are several limitations that need to be addressed:

(1) Certain methods, such as AMGL [6], depend heavily on predefined graphs of different views. Clustering performance can be significantly compromised when the quality of the graphs is poor. Moreover, the ordinary graphs used by most methods only consider pairwise relationships, inevitably leading to information loss when dealing with practical problems involving complex data structures.

(2) Each view in the multi-view data contains specific attribute information, and different views exhibit consistency and complementarity. Only by comprehensively utilizing these diverse data can the essence of the subjects be fully reflected. However, certain clustering algorithms assume that all views have identical indicator matrices, and may not fully consider the differences among different views. This lack of consideration can lead to underfitting in practical applications.

(3) Several existing methods fail to fully exploit the spatial structure and complementary information contained in the indicator matrices of multiple views, even though this information is essential for improving the accuracy of multi-view clustering.

We present an efficient hypergraph learning-based semi-supervised multi-view spectral clustering approach to address the aforementioned challenges. A hypergraph is a generalization of a graph in which an edge can connect more than two vertices. Compared with ordinary graphs, hypergraphs can offer more accurate representation of the relationships between objects exhibiting multiple associations. Our method combines hypergraph learning and semi-supervised multi-view spectral clustering into a cohesive framework that effectively preserves complementary information and higher-order structures by constructing hypergraph-induced hyper-Laplacian matrices on view-specific graphs and applying the tensor Schatten p-norm to the tensor formed from the indicator matrix. We outline our key contributions as follows:

• Our proposed method adaptively learns the graph for each view to avoid overdependence of clustering performance on predefined graphs. Furthermore, this approach considers the relationships between multiple sample points in the graph to prevent the loss of valuable information, preserving higher-order geometric structures through hypergraph-induced hyper-Laplacian matrices.
• The proposed method concurrently learns the indicator matrices of all views. It employs the tensor Schatten p-norm to extract these views’ complementary information and low-rank spatial structures. As a result, the learned common indicator matrix offers an effective representation of the clustering structure.
• In our proposed method, we design a straightforward auto-weighted scheme for the tensor Schatten p-norm which adaptively determines the ideal weighted vector to handle differences between singular values. This enhances the flexibility and stability of the algorithm in practical applications. Comprehensive experiments on a wide range of datasets demonstrate the superiority of our proposed approach.

2. Related Works

Clustering methods are mainly divided into subspace-based methods, matrix decomposition based methods, and graph-based methods, as shown in Figure 1. As one of the most extensively researched multi-view clustering techniques, graph-based clustering has exceptionally characterized sample relationships and elucidated intricate data structures. At the heart of graph-based clustering [15,16] lies the construction of high-quality graphs, which has been the focus of numerous studies.

Currently, numerous graph-oriented multi-view clustering methods have been proposed. Recognizing that different views have consistent clustering structures, Kumar et al. [17] developed a co-regularized multi-view spectral clustering method. The indicator matrices of all views were jointly optimized to achieve consistent clustering results by applying co-regularization while following the performance of standard spectral clustering for each view. Considering the impact of similarity matrix construction and weighting strategy design on multi-view clustering, Cheng et al. [18] fused multiple graphs to obtain a more meaningful similarity matrix and leveraged known information to set corresponding weights for each view. Their method fully accounts for the differences between each view, enhancing the algorithm’s stability and providing a supplementary direction for various graph-based clustering methods. Cai et al. [19] developed a multi-modal spectral clustering algorithm (MMSC) which combines diverse features to generate a common graph Laplacian matrix. In addition, they introduced non-negative relaxation in the objective function to directly obtain the discrete cluster indicator matrix and ensure the algorithm’s convergence. To properly integrate multiple data representations to achieve the optimal linear combination, Karasuyama et al. [20] proposed a sparse multiple graph integration algorithm (SMGI). This method effectively avoids the impact of noisy graphs on clustering reliability by computing sparsity weights. To improve algorithmic flexibility, Cai et al. [21] presented an adaptive multi-modality semi-supervised clustering algorithm (AMMSS) that automatically assigns appropriate weights to different modalities and learns a common indicator matrix representing the class of unlabeled samples. To enhance clustering performance through reliable graphs, Zhan et al. [22] introduced a multi-view clustering algorithm for graph learning (MVGL). This algorithm reflects clustering results by ensuring that the global graph integrated from each view has an explicit number of connected components through a rank constraint on the Laplacian matrix. Nie et al. [23] proposed a multi-view learning method with an adaptive neighbor (MLAN), which can automatically assign the optimal weight to each view without requiring additional parameters or human intervention. This method directly divides the learned ideal graph into specific clusters through reasonable rank constraints, improving the algorithm’s effectiveness. To achieve a breakthrough in efficiency, Zhang et al. developed a fast multi-view semi-supervised learning method (FMSSL) [24]. By combining anchor-based graphs with multi-view semi-supervised learning strategies, FMSSL reduces the computational complexity of clustering and enhances algorithm effectiveness by exploiting feature and label information.

As is evident from the literature, graph-oriented methods have been extensively investigated and demonstrate promising performance thanks to their ability to uncover hidden structures within data. However, the aforementioned clustering approaches are all based on ordinary graphs. Many real-world problems involve highly complex data structures, and ordinary graphs, which focus solely on relationships between two sample points, often fail to provide sufficient information. Hypergraphs possess powerful characterization ability, allowing them to effectively model various networks, systems, and data structures with intricate interlocking relationships. Consequently, several methods attempt to incorporate hypergraph learning into clustering research to overcome the limitations of ordinary graphs.

Aiming to explore relationships among multiple sample points, Zhou et al. [25] extended spectral clustering techniques typically employed on ordinary graphs to hypergraphs. They further designed transductive inference and hypergraph embedding methods based on the hypergraph Laplacian. Gao et al. [26] integrated sparse coding and hypergraph learning within a unified framework, taking full advantage of hypergraphs’ higher-order structure and significantly enhancing the robustness of the coding results. Yin et al. [27] incorporated hypergraph Laplacian regularization into low-rank representation to obtain a global low-dimensional representation matrix while accounting for the nonlinear geometric structure of the data. Xie et al. [28] proposed a hyper-Laplacian regularized multilinear multi-view to improve the clustering performance of a multi-view nonlinear feature subspace self-representation algorithm (HLR-M²VS). This algorithm employs tensor low-rank and hyper-Laplacian regularization to preserve the global consensus and local high-order geometrical structure.

3. Notation and Background

3.1. Notation

This section lays out the notation and definitions utilized throughout the paper. Bold calligraphy, bold uppercase, bold lowercase, and lowercase letters are used to indicate tensors, matrices, vectors, and elements, respectively. For example, $\mathcal{F}\in \mathbb{R}{}^{n_1\times n_2\times n_3}$ denotes three-order tensors, $\mathbf{F}\in \mathbb{R}{}^{n_1\times n_2}$ is a matrix, $\mathbf{f}\in \mathbb{R}{}^{n_1}$ is an $n_1$-dimensional vector, and $f_{ijk}$ represents the entries of $\mathcal{F}$. Moreover, ${\mathbf{F}}^{\left(i\right)}$ denotes the i-th frontal slice of $\mathcal{F}$. We obtain $\overline{\mathcal{F}}$ by taking the discrete Fast Fourier transform (FFT) of the tensor $\mathcal{F}$ along the third dimension, that is, $\overline{\mathcal{F}}=fft(\mathcal{F},\left[\right],3)$. Obviously, the inverse FFT of $\overline{\mathcal{F}}$ along the third dimension can be represented as $\mathcal{F}=ifft(\overline{\mathcal{F}},\left[\right],3)$. The Frobenius norm of tensor $\mathcal{F}$ is specified by ${∥\mathcal{F}∥}_F=\sqrt{{{\sum }_{i,j,k}\left|f_{ijk}\right|}^2}$. The trace of matrix $\mathbf{F}$ is represented by $tr\left(\mathbf{F}\right)$, and $\mathbf{I}$ is an identity matrix.

Definition 1 

(t-product [29]). Suppose that $\mathcal{X}\in {\mathbb{R}}^{n_1\times m\times n_3}$ and $\mathcal{Y}\in {\mathbb{R}}^{m\times n_2\times n_3}$; then, the t-product $\mathcal{X}*\mathcal{Y}\in {\mathbb{R}}^{n_1\times n_2\times n_3}$ is defined as

$$\mathcal{X}*\mathcal{Y}=ifft(\mathrm{bdiag}\left(\overline{X}\overline{Y}\right),\left[\right],3),$$

(1)

where we use $\overline{X}=\mathrm{bdiag}\left(\overline{\mathcal{X}}\right)$ to denote the block diagonal matrix with blocks that are frontal slices of $\overline{\mathcal{X}}$.

By using the t-product, we have the following new product decompositions of tensors (to save space, the definitions of the orthogonal tensor, f-diagonal tensor, and tensor transpose are omitted, though see [29]).

Definition 2 

(t-SVD [29]). The tensor Singular Value Decomposition (t-SVD) of $\mathcal{F}\in {\mathbb{R}}^{n_1\times n_2\times n_3}$ is provided by $\mathcal{F}=\mathcal{U}*\mathcal{S}*{\mathcal{V}}^{\mathrm{T}}$, where $\mathcal{U}$ and $\mathcal{V}$ are orthogonal tensors of size $n_1\times n_1\times n_3$ and $n_2\times n_2\times n_3$, respectively, $\mathcal{S}$ is an f-diagonal tensor of size $n_1\times n_2\times n_3$, and * denotes the t-product.

3.2. Hypergraph Preliminaries

Graphs can be used to illustrate the pairwise relationship between research objects. Nevertheless, real-world problems are often described by extremely elaborate relationships between data. In [25,28], it has been shown that compressing the elaborate relationships between data into simple pairwise relationships undoubtedly results in lost information that could be useful for clustering tasks. One way to remedy the problem of information loss occurring in ordinary graphs is to represent the data in hypergraph form. It is worth noting that a hypergraph can consider the relationship between multiple vertices, allowing the high-order information and complex relationship of the data to be explored. For a given hypergraph $\mathbf{Z}=(\mathbf{V},\mathbf{E},\mathbf{W})$, $\mathbf{V}={\left\{v_i\right\}}_{i=1}^n$ represents the set of n vertices in the hypergraph, and $\mathbf{E}={\left\{e_j\right\}}_{j=1}^t$ denotes the set of hyperedges, each of edge $e_j$ of which can be connected to any number of vertices. Values can be assigned to each hyperedge to build a weighted hypergraph based on a specific problem. In general, hyperedge $e_j$ is assigned a non-negative number $w\left(e_j\right)$, which is the j-th diagonal element of the weight matrix $\mathbf{W}\in {\mathbb{R}}^{t\times t}$. The incidence matrix $\mathbf{H}\in {\mathbb{R}}^{n\times t}$ clearly and concisely represents the interrelationship between hyperedges and vertices, and is made up of the following entries:

$$\begin{array}{c}h(v_i,e_j)=\left\{\begin{array}{c}1,if{v}_i\in e_j\hfill \\ 0,otherwise\hfill \end{array}\right.\hfill \end{array}$$

(2)

Figure 2 displays a hypergraph structure comprised of 3 hyperedges and 8 vertices. As can be seen from Figure 2a, hyperedge $e_1$ connects a set of vertices $\{v_2,v_4,v_8\}$, hyperedge $e_2$ connects vertices $\{v_3,v_5,v_7\}$, and hyperedge $e_3$ connects three vertices $\{v_1,v_6,v_7\}$. The incidence matrix $\mathbf{H}$ in Figure 2b corresponds to the hypergraph of Figure 2a, which succinctly represents the connectivity of vertices and hyperedges.

Following the above definitions, we can calculate the unnormalized hyper-Laplacian matrix [25] as follows:

$$\begin{array}{c}{\mathbf{L}}_h={\mathbf{D}}_{\mathbf{V}}-{\mathbf{HWD}}_{\mathbf{E}}^{-1}{\mathbf{H}}^{\mathrm{T}}\hfill \end{array}$$

(3)

where ${\mathbf{D}}_{\mathbf{E}}$ and ${\mathbf{D}}_{\mathbf{V}}$ indicate the degree matrices, the diagonal elements of which respectively correspond to the degree of each hyperedge $e_j$ and the degree of each vertex $v_i$. Based on the discussion presented above, it is evident that an edge in a hypergraph can connect to more than two vertices. An ordinary graph is a specialized form of a hypergraph in which each edge contains only two vertices. Unlike ordinary graphs, hypergraphs offer more accurate representation of the relationships between objects exhibiting multiple associations.

4. Methodology

4.1. Auto-Weighted Multiple Graph Learning (AMGL)

Before presenting our method, it is worth reviewing the AMGL [6], which is one of the most influential semi-supervised multi-view clustering methods that facilitate multiple graph learning. Let ${\mathbf{X}}^{\left(v\right)}\in {\mathbb{R}}^{d_v\times n}$($v=1,2,\dots m$) represent the multi-view data matrix with m views, where $d_v$ denotes the dimensionality of the v-th view and n indicates the number of samples in dataset. Here, ${\mathbf{X}}^{\left(v\right)}$ contains l tagged data and u untagged data that can be divided into c categories. Suppose that ${\mathbf{G}}^{\left(v\right)}=\left\{g_{ij}^{\left(v\right)}\right\}\in {\mathbb{R}}^{n\times n}$ is the adjacency matrix of the v-th view and the corresponding Laplacian matrix is ${\mathbf{L}}_{{\mathbf{G}}^{\left(v\right)}}={\mathbf{D}}_{{\mathbf{G}}^{\left(v\right)}}-({\left({\mathbf{G}}^{\left(v\right)}\right)}^T+{\mathbf{G}}^{\left(v\right)})/2$, where ${\mathbf{D}}_{{\mathbf{G}}^{\left(v\right)}}\in {\mathbb{R}}^{n\times n}$ represents the degree matrix with ${\sum }_j(g_{ij}^{\left(v\right)}+g_{ji}^{\left(v\right)})/2$ as the i-th diagonal element. Assume that $\mathbf{F}=[{\mathbf{f}}_1;{\mathbf{f}}_2;\dots ;{\mathbf{f}}_n]\in {\mathbb{R}}^{n\times c}$ is the cluster indicator matrix, where c denotes the number of classes. Thus, the objective function of AMGL can be represented by

$$\begin{array}{c}\underset{\mathbf{F}\in {\mathbb{R}}^{n\times c}}{min}\sum _{v=1}^m\sqrt{tr\left({\mathbf{F}}^{\mathrm{T}}{\mathbf{L}}_{{\mathbf{G}}^{\left(v\right)}}\mathbf{F}\right)}\hfill \\ \mathrm{s}.\mathrm{t}.{\mathbf{f}}_i={\mathbf{y}}_i\forall i=1,2,\dots ,l\hfill \end{array}$$

(4)

The label matrix ${\mathbf{Y}}_l=[{\mathbf{y}}_1;{\mathbf{y}}_2;...;{\mathbf{y}}_l]$, where ${\mathbf{y}}_i\in {\mathbb{R}}^{1\times c}$ denotes the label vector of the i-th data point. If the i-th sample falls under the j-th class, its element is represented by $y_{ij}=1$; otherwise, it is represented by $y_{ij}=0$.

Although AMGL achieves promising results, it has a number of deficiencies: (1) it cannot model unpaired relationships effectively in complex scenes, and its performance heavily relies on predefined graphs, limiting its practical applications. (2) AMGL requires the same indicator matrix $\mathbf{F}$ for different views, which is too strict and may lead to underfitting. This constraint can reduce clustering accuracy, especially for datasets with pronounced differences between views. (3) AMGL ignores the spatial structure and complementary information in the indicator matrices for multiple views, which is imperative when seeking to strengthen clustering capability.

4.2. Problem Formulation and Objective Determination

In this paper, we propose a semi-supervised multi-view clustering model that addresses the aforementioned problems. To be more precise, the proposed method is inspired by the tensor Schatten p-norm (TSP) [30,31] and combines the insights mentioned above. It simultaneously learns the indicator matrix ${\mathbf{F}}^{\left(v\right)}\in {\mathbb{R}}^{n\times c}$ of all views and leverages the TSP regularizer on the tensor $\mathcal{F}\in {\mathbb{R}}^{n\times m\times c}$ to encode the main spatial structure and complementary information contained in multiple views. The three-mode tensor $\mathcal{F}$ is constructed by merging a different matrix ${\mathbf{F}}^{\left(v\right)}$ and then rotating its dimensionality to $n\times m\times c$ (see Figure 3). For the constructed tensor $\mathcal{F}$, its m-th frontal slice ${\Delta }^{\left(m\right)}$ describes the similarity between n sample points and the m-th cluster in different views. The idea indicator matrix ${\mathbf{F}}^{\left(v\right)}$ should ensure that the relationship between the n data points and the m-th cluster is consistent in different views. Because different views usually show different cluster structures, we impose a tensor Schatten p-norm minimization constraint on tensor $\mathcal{F}$, ensuring that each ${\Delta }^{\left(m\right)}$ has low-rank spatial structure. Thus, ${\Delta }^{\left(m\right)}$ well encodes discriminative information and utilizes the complementary information embedded in inter-views, which helps to improve the clustering results. For all data points, we need to randomly select l points as the labeled samples, while the remaining u points correspond to the unlabeled samples. For greater convenience of derivation and description, we rearrange all the data points such that the first l points are labeled samples and the subsequent u points correspond to unlabeled samples. This processing ensures the randomness of data point selection and while not affecting the result. Thus, ${\mathbf{F}}^{\left(v\right)}$ is split into two parts, ${\mathbf{F}}_l^{\left(v\right)}$ and ${\mathbf{F}}_u^{\left(v\right)}$, i.e., ${\mathbf{F}}^{\left(v\right)}=\left[{\mathbf{F}}_l^{\left(v\right)};{\mathbf{F}}_u^{\left(v\right)}\right]$, ${\mathbf{F}}_l^{\left(v\right)}\in {\mathbb{R}}^{l\times c}$, ${\mathbf{F}}_u^{\left(v\right)}\in {\mathbb{R}}^{u\times c}$, and $l+u=n$. On this basis, we rewrite (4) as

$$\begin{array}{c}\hfill \underset{\genfrac{}{}{0pt}{}{{\mathbf{F}}_l^{{}^{\left(v\right)}}={\mathbf{Y}}_l\hfill }{}}{min}\alpha \sum _{v=1}^m\sqrt{tr\left({\left({\mathbf{F}}^{\left(v\right)}\right)}^{\mathrm{T}}{\mathbf{L}}_{{\mathbf{G}}^{\left(v\right)}}{\mathbf{F}}^{\left(v\right)}\right)}+{\parallel \mathcal{F}\parallel }_{\omega ,\overline{)\mathit{S}\mathit{p}}}^p\end{array}$$

(5)

where $\alpha$ is the balance parameter and ${\parallel \mathcal{F}\parallel }_{\omega ,\overline{)\mathit{S}\mathit{p}}}$ denotes the weighted tensor Schatten p-norm [32] of the tensor $\mathcal{F}$, which can be defined as

$$\begin{array}{c}\hfill {\parallel \mathcal{F}\parallel }_{\omega ,\overline{)\mathit{S}\mathit{p}}}={\left(\sum _{i=1}^c{∥{\overline{\mathbf{F}}}^{\left(i\right)}∥}_{\omega ,\overline{)\mathit{S}\mathit{p}}}^p\right)}^{\frac{1}{p}}={\left(\sum _{i=1}^c\sum _{j=1}^{min(n,m)}{\omega }_j*{\sigma }_j{\left({\overline{\mathbf{F}}}^{\left(i\right)}\right)}^p\right)}^{\frac{1}{p}}\end{array}$$

(6)

where ${\sigma }_j({\overline{\mathbf{F}}}^{\left(i\right)})$ is the j-th largest singular value of ${\overline{\mathbf{F}}}^{\left(i\right)}$ and ${\omega }_j$ is the j-th element of the weighted vector $\omega$. We can take advantage of the power processing scheme to bring the rank of the learned consensus indicator matrix as close to the target rank as possible by considering $0<p\le 1$ as the power parameter.

In (5), it is necessary to consider the difference between singular values to fully explore the higher-order tensorial structure and set a reasonable weighted vector $\omega$. However, due to the complexity and unpredictability of the data distribution, predefining the weighted vector $\omega$ manually is not easy or circumscribed. Therefore, an adaptive weighting strategy is introduced to solve this problem. The relevant lemma is as follows.

Lemma 1. 

For minimization of the weighted tensor Schatten p-norm, a closed-form global minimizer can be acquired if the singular values are in non-increasing order and the weighted values are in non-decreasing order [32,33].

There are significant differences between the singular values of a tensor. Because large singular values can usually describe the main structure of the data, these values should shrink less. Based on the above insights and Lemma 1, an effective automatic weighting strategy is designed to improve the algorithm’s flexibility. Specifically, the j-th element of the weighted vector $\omega$ is defined as

$${\omega }_j=\frac{\sqrt{n\times m}}{{\sigma }_j+\psi },$$

(7)

where $\sqrt{n\times m}$ is an empirical value, n and m respectively represent the number of samples and the number of views, ${\sigma }_j$ denotes the j-th singular value, and $\psi$ is a very small value which is set to ${10}^{-6}$ in the experiment. It is worth noting that the weighted value ${\omega }_j$ indicates the degree to which the j-th singular value shrinks, that is, the larger singular value should shrink less and the smaller singular value should shrink more. As can be seen from Figure 4, if the singular values are in non-increasing order, the corresponding weighted values ${\omega }_j$ are in non-decreasing order. In other words, this strategy can automatically calculate a reasonably weighted vector $\omega$ for different datasets, improving the flexibility and stability of the algorithm.

In terms of (5), the Lagrangian function can be expressed as follows:

$$\begin{array}{c}\hfill \alpha \sum _{v=1}^m\sqrt{tr\left({\left({\mathbf{F}}^{\left(v\right)}\right)}^{\mathrm{T}}{\mathbf{L}}_{{\mathbf{G}}^{\left(v\right)}}{\mathbf{F}}^{\left(v\right)}\right)}+{\parallel \mathcal{F}\parallel }_{\omega ,\overline{)\mathit{S}\mathit{p}}}^p+\zeta ({\rm Y},\mathcal{F})\end{array}$$

(8)

where the formalized term $\zeta ({\rm Y},\mathcal{F})$ derives from the constraints and ${\rm Y}$ represents the Lagrange multipliers. Setting the derivative concerning ${\mathbf{F}}^{\left(v\right)}$ to zero provides us with

$$\begin{array}{c}\hfill \alpha \sum _{v=1}^m{\lambda }^{\left(v\right)}\frac{\partial tr\left({\left({\mathbf{F}}^{\left(v\right)}\right)}^{\mathrm{T}}{\mathbf{L}}_{{\mathbf{G}}^{\left(v\right)}}{\mathbf{F}}^{\left(v\right)}\right)}{\partial {\mathbf{F}}^{\left(v\right)}}+\frac{{\partial \parallel \mathcal{F}\parallel }_{\omega ,\overline{)\mathit{S}\mathit{p}}}^p}{\partial {\mathbf{F}}^{\left(v\right)}}+\frac{\partial \zeta ({\rm Y},\mathcal{F})}{\partial {\mathbf{F}}^{\left(v\right)}}=0,\end{array}$$

(9)

where

$$\begin{array}{c}\hfill {\lambda }^{\left(v\right)}=\frac{1}{2\sqrt{tr\left({\left({\mathbf{F}}^{\left(v\right)}\right)}^{\mathrm{T}}{\mathbf{L}}_{{\mathbf{G}}^{\left(v\right)}}{\mathbf{F}}^{\left(v\right)}\right)}}\end{array}$$

(10)

It is worth noting that in (10) there is a dependency of ${\lambda }^{\left(v\right)}$ on ${\mathbf{F}}^{\left(v\right)}$; therefore, (9) is inconvenient to solve directly. Inspired by previous multi-view clustering approaches [6,34], if ${\lambda }^{\left(v\right)}$ is set to be stationary, then (9) can be regarded as the solution to (11) provided below:

$$\begin{array}{c}\hfill \underset{\genfrac{}{}{0pt}{}{{\mathbf{F}}_l^{{}^{\left(v\right)}}={\mathbf{Y}}_l\hfill }{}}{min}\alpha \sum _{v=1}^m{\lambda }^{\left(v\right)}tr({({\mathbf{F}}^{\left(v\right)})}^{\mathrm{T}}{\mathbf{L}}_{{\mathbf{G}}^{\left(v\right)}}{\mathbf{F}}^{\left(v\right)})+{\parallel \mathcal{F}\parallel }_{\omega ,\overline{)\mathit{S}\mathit{p}}}^p\end{array}$$

(11)

For (11), it is challenging to manually obtain a suitable graph to represent the correlation between samples due to the complexity of the data distribution and the differences between the views. Moreover, if the predefined graph is not adequate, the performance of the clustering algorithm may become severely degraded. In order to overcome this limitation, we introduce adaptive learning graphs to our model, which can enhance its stability by avoiding dependency on a fixed graph.

Furthermore, we adopt the hypergraph learning approach and use hypergraph-induced hyper-Laplacian matrices in our method to reveal the higher-order geometric structure of the data. This strategy can effectively capture the relationship between multiple sample points, preserve essential information from the data, and improve the stability and flexibility of the clustering method. Therefore, we formulate our objective function as follows:

$$\begin{array}{cc}\hfill & \underset{{\mathbf{F}}_l^{{}^{\left(v\right)}}={\mathbf{Y}}_l}{min}\sum _{v=1}^m\frac{1}{{\tau }^{\left(v\right)}}{\parallel {\mathbf{G}}^{\left(v\right)}-{\mathbf{S}}^{\left(v\right)}\parallel }_F^2+\beta {\parallel \mathcal{F}\parallel }_{\omega ,\overline{)\mathit{S}\mathit{p}}}^p\hfill \\ \hfill & +\alpha \sum _{v=1}^m{\lambda }^{\left(v\right)}tr\left({\left({\mathbf{F}}^{\left(v\right)}\right)}^{\mathrm{T}}{\mathbf{L}}_{\mathrm{h}}^{\left(v\right)}{\mathbf{F}}^{\left(v\right)}\right)\hfill \\ \hfill & \mathrm{s}.\mathrm{t}.{\mathbf{S}}^{\left(v\right)}\ge 0,{\mathbf{S}}^{\left(v\right)}\mathbf{1}=\mathbf{1},{\tau }^{\left(v\right)}\ge 0,{\sum }_{v=1}^m{\tau }^{\left(v\right)}=1\hfill \end{array}$$

(12)

where ${\mathbf{S}}^{\left(v\right)}\in {\mathbb{R}}^{n\times n}$ is the learned graph for the v-th view, which represents the affinities among all the samples. For the sake of avoiding the negative effects of scale, we impose the non-negative normalization constraint $0\le {\mathbf{S}}^{\left(v\right)}\le 1$, ${\mathbf{S}}^{\left(v\right)}\mathbf{1}=\mathbf{1}$, to maintain a unified range of values for the affinities of all sample points via regression. Here, $\beta$ represents a trade-off parameter and ${\tau }^{\left(v\right)}$ describes the magnitude of the non-negative normalized weight for the v-th view.

In Formula (12), ${\mathbf{L}}_{\mathrm{h}}^{\left(v\right)}$ represents the hyper-Laplacian matrix of the v-th view constructed from the affinity matrix ${\mathbf{S}}^{\left(v\right)}$. Because ${\mathbf{S}}^{\left(v\right)}$ is adaptively learned, hypergraphs constructed based on the affinity matrix ${\mathbf{S}}^{\left(v\right)}$ do not depend on fixed predefined graphs; in this way, the relationship between data points can be better described. When ${\mathbf{L}}_{\mathrm{h}}^{\left(v\right)}$ in the model is replaced by ${\mathbf{L}}_{{\mathbf{S}}^{\left(v\right)}}$, it becomes an ordinary Laplacian matrix constructed based on ${\mathbf{S}}^{\left(v\right)}$, and the corresponding hyper-Laplacian regularization is simplified into the traditional graph Laplacian constraint that can only capture the pair relationship between samples.

To be more specific, in the process of building the hyper-Laplacian matrix ${\mathbf{L}}_{\mathrm{h}}^{\left(v\right)}$ we regard each sample in the multi-view dataset as a vertex in the hypergraph, take each vertex $p_i^{\left(v\right)}$ as the centroid vertex, and construct the corresponding hyperedge $e_j^{\left(v\right)}$ using the k-nearest neighbor method; that is to say, the hypergraph constructed for each view is composed of n hyperedges and each hyperedge contains k vertices. Accordingly, the view-specific incidence matrix ${\mathbf{H}}^{\left(v\right)}\in {\mathbb{R}}^{n\times n}$ can be obtained according to Formula (2), that is, in the v-th view, we have $h_{ij}^{\left(v\right)}=1$ if vertex $p_i^{\left(v\right)}$ belongs to hyperedge $e_j^{\left(v\right)}$ and $h_{ij}^{\left(v\right)}=0$ otherwise. Because the affinity matrix ${\mathbf{S}}^{\left(v\right)}$ of each view is adaptively learned in Formula (12), a weight $w\left(e_j^{\left(v\right)}\right)$ can be assigned to each hyperedge $e_j^{\left(v\right)}$ on each view according to the following formula:

$$\begin{array}{c}\hfill w\left(e_j^{\left(v\right)}\right)=\sum _{p_i^{\left(v\right)}\in e_j^{\left(v\right)}}{S}_{ij}^{\left(v\right)}\end{array}$$

(13)

The corresponding weight matrix ${\mathbf{W}}^{\left(v\right)}\in {\mathbb{R}}^{n\times n}$ is a diagonal matrix with $w\left(e_j^{\left(v\right)}\right)$ as its diagonal element, i.e., ${\mathbf{W}}^{\left(v\right)}=diag\left(w\left(e_1^{\left(v\right)}\right),w\left(e_2^{\left(v\right)}\right),\dots ,w\left(e_n^{\left(v\right)}\right)\right)$. Based on this, the edge degree ${\mathbf{D}}_{\mathbf{E}}^{\left(v\right)}$ and the vertex degree ${\mathbf{D}}_{\mathbf{P}}^{\left(v\right)}$ corresponding to the v-th view can be calculated according to the following formula:

$$\begin{array}{c}d\left(e_j^{\left(v\right)}\right)={\displaystyle \sum _{i=1}^n}h(p_i^{\left(v\right)},e_j^{\left(v\right)})\hfill \\ d\left(p_i^{\left(v\right)}\right)={\displaystyle \sum _{j=1}^n}w\left(e_j^{\left(v\right)}\right)h(p_i^{\left(v\right)},e_j^{\left(v\right)})\hfill \end{array}$$

(14)

where ${\mathbf{D}}_{\mathbf{E}}^{\left(v\right)}$ and ${\mathbf{D}}_{\mathbf{P}}^{\left(v\right)}$ are diagonal matrices with diagonal elements that correspond to the degrees of each hyperedge $e_j^{\left(v\right)}$ and the degrees of each vertex $p_i^{\left(v\right)}$, respectively.

Finally, the view-specific hyper-Laplacian matrix ${\mathbf{L}}_{\mathrm{h}}^{\left(v\right)}$ built on the affinity matrix ${\mathbf{S}}^{\left(v\right)}$ can be formulated as follows:

$$\begin{array}{c}\hfill {\mathbf{L}}_h^{\left(v\right)}={\mathbf{D}}_{\mathbf{P}}^{\left(v\right)}-{\mathbf{H}}^{\left(v\right)}{\mathbf{W}}^{\left(v\right)}{{\mathbf{D}}_{\mathbf{E}}^{\left(v\right)}}^{-1}{{\mathbf{H}}^{\left(v\right)}}^{\mathrm{T}}\end{array}$$

(15)

To sum up, each vertex in the hypergraph constructed in this paper is connected with at least one hyperedge, and each hyperedge is associated with a weight. The proposed model first adaptively learns the affinity matrix ${\mathbf{S}}^{\left(v\right)}$ of each view, then fully considers the relationship between multiple sample points, constructs the hypergraph using the acquired affinity matrix, and preserves the higher-order geometric structure through the hypergraph-induced hyper-Laplacian matrix ${\mathbf{L}}_{\mathrm{h}}^{\left(v\right)}$. In this way, the model realizes the effective exploration of the higher-order information and complex structure in the data while avoiding dependence on predefined graphs.

4.3. Optimization

It is infeasible to solve (12) directly due to the presence of multiple variables. The Augmented Lagrange Multiplier (ALM) method is an efficient solver for the above model (12). In order to solve optimization problems with separable structures, the Alternating Direction Method of Multipliers (ADMM) is proposed, which is used to obtain the solution of the global problem by coordinating the solutions of the subproblems. To adopt an alternating direction minimization strategy with the model, we first introduce auxiliary variables $\mathcal{J}$ and ${\mathbf{K}}^{\left(v\right)}$ to replace $\mathcal{F}$ and ${\mathbf{S}}^{\left(v\right)}$, respectively, that is to say, $\mathcal{F}=\mathcal{J}$ and ${\mathbf{S}}^{\left(v\right)}={\mathbf{K}}^{\left(v\right)}$. Then, we substitute $\mathcal{F}$ and ${\mathbf{S}}^{\left(v\right)}$ into (12); by simple algebraic operations, we can then rewrite (12) as the following augmented Lagrangian function:

$$\begin{array}{cc}\hfill & \underset{{\mathbf{F}}_l^{{}^{\left(v\right)}}={\mathbf{Y}}_l}{min}\alpha \sum _{v=1}^m{\lambda }^{\left(v\right)}tr\left({\left({\mathbf{F}}^{\left(v\right)}\right)}^{\mathrm{T}}{\mathbf{L}}_{\mathrm{h}}^{\left(v\right)}{\mathbf{F}}^{\left(v\right)}\right)+\beta {\parallel \mathcal{J}\parallel }_{\omega ,\overline{)\mathit{S}\mathit{p}}}^p\hfill \\ \hfill & +\frac{\mu }{2}{\parallel \mathcal{F}-\mathcal{J}+\frac{\mathcal{Q}}{\mu }\parallel }_F^2+\sum _{v=1}^m\frac{1}{{\tau }^{\left(v\right)}}{\parallel {\mathbf{G}}^{\left(v\right)}-{\mathbf{K}}^{\left(v\right)}\parallel }_F^2\hfill \\ \hfill & +\sum _{v=1}^m\frac{\gamma }{2}{\parallel {\mathbf{S}}^{\left(v\right)}-{\mathbf{K}}^{\left(v\right)}+\frac{{\mathbf{T}}^{\left(v\right)}}{\gamma }\parallel }_F^2\hfill \\ \hfill & \mathrm{s}.\mathrm{t}.{\mathbf{S}}^{\left(v\right)}\ge 0,{\mathbf{S}}^{\left(v\right)}\mathbf{1}=\mathbf{1},{\tau }^{\left(v\right)}\ge 0,{\sum }_{v=1}^m{\tau }^{\left(v\right)}=1\hfill \end{array}$$

(16)

where $\mathcal{Q}$ and ${\mathbf{T}}^{\left(v\right)}$ are used to indicate Lagrange multiplier while $\mu >0$ and $\gamma >0$ denote the penalty factor. We use an alternate optimization strategy to solve (16), which involves the following subproblems.

• Solving ${\mathbf{K}}^{\left(v\right)}$ with fixed ${\mathbf{S}}^{\left(v\right)}$, ${\mathbf{T}}^{\left(v\right)}$, and $\frac{1}{{\tau }^{\left(v\right)}}$. Now, the optimization problem with respect to ${\mathbf{K}}^{\left(v\right)}$ in (16) can be simplified as

  $$\begin{array}{c}\underset{{\mathbf{K}}^{\left(v\right)}}{min}\sum _{v=1}^m\frac{1}{{\tau }^{\left(v\right)}}{\parallel {\mathbf{G}}^{\left(v\right)}-{\mathbf{K}}^{\left(v\right)}\parallel }_F^2+\sum _{v=1}^m\frac{\gamma }{2}{\parallel {\mathbf{S}}^{\left(v\right)}-{\mathbf{K}}^{\left(v\right)}+\frac{{\mathbf{T}}^{\left(v\right)}}{\gamma }\parallel }_F^2\hfill \end{array}$$

  (17)
  Because ${\left\{{\mathbf{K}}^{\left(v\right)}\right\}}_{v=1}^m$ are independent, we can solve each ${\mathbf{K}}^{\left(v\right)}$ independently. Setting the derivative to zero with respect to ${\mathbf{K}}^{\left(v\right)}$, we obtain

  $$\begin{array}{c}\hfill -\frac{2}{{\tau }^{\left(v\right)}}{\mathbf{G}}^{\left(v\right)}+(\gamma \mathbf{I}+\frac{2}{{\tau }^{\left(v\right)}}\mathbf{I}){\mathbf{K}}^{\left(v\right)}-\gamma ({\mathbf{S}}^{\left(v\right)}+\frac{{\mathbf{T}}^{\left(v\right)}}{\gamma })=0\end{array}$$

  (18)
  By simple algebra, the optimal solution for ${\mathbf{K}}^{\left(v\right)}$ is provided by

  $$\begin{array}{c}\hfill {\mathbf{K}}^{\left(v\right)}=\frac{\gamma {\mathbf{S}}^{\left(v\right)}+{\mathbf{T}}^{\left(v\right)}+\frac{2}{{\tau }^{\left(v\right)}}{\mathbf{G}}^{\left(v\right)}}{\gamma +\frac{2}{{\tau }^{\left(v\right)}}}\end{array}$$

  (19)
• Solving ${\mathbf{S}}^{\left(v\right)}$ with fixed ${\mathbf{K}}^{\left(v\right)}$ and ${\mathbf{T}}^{\left(v\right)}$. According to (16), the solution to this subproblem can be calculated as follows:

  $$\begin{array}{c}\underset{{\mathbf{S}}^{\left(v\right)}}{min}\sum _{v=1}^m\frac{\gamma }{2}{\parallel {\mathbf{S}}^{\left(v\right)}-\frac{\gamma {\mathbf{K}}^{\left(v\right)}-{\mathbf{T}}^{\left(v\right)}}{\gamma }\parallel }_F^2\hfill \\ \mathrm{s}.\mathrm{t}.{\mathbf{S}}^{\left(v\right)}\ge 0,{\mathbf{S}}^{\left(v\right)}\mathbf{1}=\mathbf{1}\hfill \end{array}$$

  (20)
  It should be noted that there is no dependence between all ${\mathbf{S}}^{\left(v\right)}(v=1,\dots ,m)$ in (20). The closed-form solution ${\mathbf{S}}^{{\left(v\right)}^{*}}$ of each ${\mathbf{S}}^{\left(v\right)}$ is provided by ${\mathbf{S}}^{{\left(v\right)}^{*}}(i,:)=(\frac{{\mathbf{B}}^{\left(v\right)}(i,:)}{\gamma }{+\varrho \mathbf{1})}_{+}$  [35], where ${\mathbf{B}}^{\left(v\right)}=\gamma {\mathbf{K}}^{\left(v\right)}-{\mathbf{T}}^{\left(v\right)}$ and $\varrho$ is the Lagrangian multiplier.
• Solving ${\mathbf{F}}^{\left(v\right)}$ with fixed $\mathcal{J}$, $\mathcal{Q}$, ${\mathbf{L}}_{\mathrm{h}}^{\left(v\right)}$, and ${\lambda }^{\left(v\right)}$. At this point, the optimization problem in (16) with respect to ${\mathbf{F}}^{\left(v\right)}$ can be formulated as

  $$\begin{array}{cc}\hfill \underset{\genfrac{}{}{0pt}{}{{\mathbf{F}}_l^{{}^{\left(v\right)}}={\mathbf{Y}}_l\hfill }{}}{min}& \alpha \sum _{v=1}^m{\lambda }^{\left(v\right)}tr\left({\left({\mathbf{F}}^{\left(v\right)}\right)}^{\mathrm{T}}{\mathbf{L}}_{\mathrm{h}}^{\left(v\right)}{\mathbf{F}}^{\left(v\right)}\right)+\frac{\mu }{2}{\parallel \mathcal{F}-\mathcal{J}+\frac{\mathcal{Q}}{\mu }\parallel }_F^2\hfill \end{array}$$

  (21)
  We denote ${\mathbf{F}}^{\left(v\right)}=\left[{\mathbf{Y}}_l;{\mathbf{F}}_u^{\left(v\right)}\right]$, ${\mathbf{J}}^{\left(v\right)}=\left[{\mathbf{J}}_l^{\left(v\right)};{\mathbf{J}}_u^{\left(v\right)}\right]$, ${\mathbf{Q}}^{\left(v\right)}=\left[{\mathbf{Q}}_l^{\left(v\right)};{\mathbf{Q}}_u^{\left(v\right)}\right]$, and ${\mathbf{L}}_{\mathrm{h}}^{\left(v\right)}=\left[\begin{array}{cc}{\mathbf{L}}_{ll}^{\left(v\right)}& {\mathbf{L}}_{lu}^{\left(v\right)}\\ {\mathbf{L}}_{ul}^{\left(v\right)}& {\mathbf{L}}_{uu}^{\left(v\right)}\end{array}\right]$, then substitute them into (21). Moreover, the fact that ${\left\{{\mathbf{F}}^{\left(v\right)}\right\}}_{v=1}^m$ are independent allows each ${\mathbf{F}}^{\left(v\right)}$ to be solved independently. Therefore, by simple algebra, (21) becomes

  $$\begin{array}{cc}\hfill & \underset{{\mathbf{F}}^{\left(v\right)}}{min}\alpha {\lambda }^{\left(v\right)}tr({\left[\begin{array}{c}{\mathbf{Y}}_l\hfill \\ {\mathbf{F}}_u^{\left(v\right)}\hfill \end{array}\right]}^{\mathrm{T}}\left[\begin{array}{c}{\mathbf{L}}_{ll}^{\left(v\right)}\hfill \\ {\mathbf{L}}_{ul}^{\left(v\right)}\hfill \end{array}\right.\left.\begin{array}{c}{\mathbf{L}}_{lu}^{\left(v\right)}\hfill \\ {\mathbf{L}}_{uu}^{\left(v\right)}\hfill \end{array}\right]\left[\begin{array}{c}{\mathbf{Y}}_l\hfill \\ {\mathbf{F}}_u^{\left(v\right)}\hfill \end{array}\right])\hfill \\ \hfill & +\frac{\mu }{2}{∥\left[\begin{array}{c}{\mathbf{Y}}_l\hfill \\ {\mathbf{F}}_u^{\left(v\right)}\hfill \end{array}\right]-\left[\begin{array}{c}{\mathbf{J}}_l^{\left(v\right)}\hfill \\ {\mathbf{J}}_u^{\left(v\right)}\hfill \end{array}\right]+\frac{1}{\mu }\left[\begin{array}{c}{\mathbf{Q}}_l^{\left(v\right)}\hfill \\ {\mathbf{Q}}_u^{\left(v\right)}\hfill \end{array}\right]∥}_F^2\hfill \\ \hfill & =\mathrm{Const}+2\alpha {\lambda }^{\left(v\right)}tr\left({\left({\mathbf{F}}_u^{\left(v\right)}\right)}^{\mathrm{T}}{\mathbf{L}}_{ul}^{\left(v\right)}{\mathbf{Y}}_l\right)+\alpha {\lambda }^{\left(v\right)}tr\left({\left({\mathbf{F}}_u^{\left(v\right)}\right)}^{\mathrm{T}}{\mathbf{L}}_{uu}^{\left(v\right)}{\mathbf{F}}_u^{\left(v\right)}\right)\hfill \\ \hfill & +\frac{\mu }{2}tr\left({\left({\mathbf{F}}_u^{\left(v\right)}\right)}^{\mathrm{T}}{\mathbf{F}}_u^{\left(v\right)}\right)-\mu tr\left({\left({\mathbf{F}}_u^{\left(v\right)}\right)}^{\mathrm{T}}({\mathbf{J}}_u^{\left(v\right)}-\frac{{\mathbf{Q}}_u^{\left(v\right)}}{\mu })\right)\hfill \end{array}$$

  (22)
  Setting the derivative to zero with respect to ${\mathbf{F}}_u^{\left(v\right)}$, we obtain the v-th class indicator ${\mathbf{F}}_u^{\left(v\right)}$ for the unlabeled data as follows:

  $${{\mathbf{F}}_u^{\left(v\right)}}^{*}={(\alpha {\lambda }^{\left(v\right)}{\mathbf{L}}_{uu}^{\left(v\right)}+\frac{\mu }{2}\mathbf{I})}^{-1}(\frac{\mu }{2}({\mathbf{J}}_u^{\left(v\right)}-\frac{{\mathbf{Q}}_u^{\left(v\right)}}{\mu })-\alpha {\lambda }^{\left(v\right)}{\mathbf{L}}_{ul}^{\left(v\right)}{\mathbf{Y}}_l)$$

  (23)
• Solving $\mathcal{J}$ with fixed $\mathcal{F}$ and $\mathcal{Q}$. In this case, the solution to this subproblem can be simplified as follows:

  $$\underset{\mathcal{J}}{min}\beta {\parallel \mathcal{J}\parallel }_{\omega ,\overline{)\mathit{S}\mathit{p}}}^p+\frac{\mu }{2}{∥\mathcal{F}-\mathcal{J}+\frac{\mathcal{Q}}{\mu }∥}_F^2$$

  (24)
  To solve (24), we need the following theorem.

Theorem 1 

([32]). For $\mathcal{A}\in {\mathbb{R}}^{n_1\times n_2\times n_3}$, $h=min(n_1,n_2)$, which has t-SVD $\mathcal{A}=\mathcal{U}*\mathcal{S}*{\mathcal{V}}^{\mathrm{T}}$, the optimal solution of (25) is

$$\underset{\mathcal{X}}{argmin}\frac{1}{2}{∥\mathcal{X}-\mathcal{A}∥}_F^2+\epsilon {∥\mathcal{X}∥}_{\omega ,\overline{)\mathit{S}\mathit{p}}}^p$$

(25)

which can be written as

$${\mathcal{X}}^{*}={\Gamma }_{\epsilon *\omega }\left(\mathcal{A}\right)=\mathcal{U}*ifft\left({\mathbf{P}}_{\epsilon *\omega }\left(\overline{\mathcal{A}}\right)\right)*{\mathcal{V}}^T$$

(26)

where ${\mathbf{P}}_{\epsilon *\omega }\left(\overline{\mathcal{A}}\right)\in {\mathbb{R}}^{h\times h\times n_3}$ is an f-diagonal tensor with diagonal elements that can be found using the GST algorithm introduced in Lemma 1 of [32] and $\overline{\mathcal{A}}=ifft(\mathcal{A},\left[\right],3)$.

According to the above two theorems, the solution of (24) is

$${\mathcal{J}}^{*}={\Gamma }_{\frac{\beta }{\mu }*\omega }(\mathcal{F}+\frac{\mathcal{Q}}{\mu }).$$

(27)

• Solving ${\tau }^{\left(v\right)}$ with other fixed variables. According to (16), this subproblem can be solved by

  $$\begin{array}{c}\hfill \underset{{\tau }^{\left(v\right)}}{min}\sum _{v=1}^m\frac{\parallel {\mathbf{G}}^{\left(v\right)}-{\mathbf{S}}^{\left(v\right)}{\parallel }_F^2}{{\tau }^{\left(v\right)}},\mathrm{s}.\mathrm{t}.\sum _{v=1}^m{\tau }^{\left(v\right)}=1,{\tau }^{\left(v\right)}\ge 0\end{array}$$

  (28)
  In the case of $e^{\left(v\right)}=\parallel {\mathbf{G}}^{\left(v\right)}-{\mathbf{S}}^{\left(v\right)}{\parallel }_F$, (28) can be expressed as

  $$\begin{array}{c}\hfill \underset{{\tau }^{\left(v\right)}}{min}\sum _{v=1}^m\frac{{e^{\left(v\right)}}^2}{{\tau }^{\left(v\right)}},\mathrm{s}.\mathrm{t}.\sum _{v=1}^m{\tau }^{\left(v\right)}=1,{\tau }^{\left(v\right)}\ge 0\end{array}$$

  (29)
  Considering that ${\sum }_{v=1}^m{\tau }^{\left(v\right)}=1$, based on the Cauchy-Schwartz inequality, we can find the following:

  $$\sum _{v=1}^m\frac{{e^{\left(v\right)}}^2}{{\tau }^{\left(v\right)}}=\left(\sum _{v=1}^m\frac{{e^{\left(v\right)}}^2}{{\tau }^{\left(v\right)}}\right)\left(\sum _{v=1}^m{\tau }^{\left(v\right)}\right)⩾{\left(\sum _{v=1}^m{e}^{\left(v\right)}\right)}^2$$

  (30)
  Equation (30) only holds if $\sqrt{{\tau }^{\left(v\right)}}\propto \frac{e^{\left(v\right)}}{\sqrt{{\tau }^{\left(v\right)}}}$. Because the right-hand side of (30) is the constant, the optimal solution for ${\tau }^{\left(v\right)}$ ($v=1,2,\dots ,m$) can be deduced as follows:

  $$\begin{array}{c}\hfill {\tau }^{\left(v\right)}=e^{\left(v\right)}/\sum _{i=1}^m{e}^{\left(i\right)}\end{array}$$

  (31)
• Solving ${\lambda }^{\left(v\right)}$ with fixed ${\mathbf{F}}^{\left(v\right)}$. Similar to ${\lambda }^{\left(v\right)}$ in (11), ${\lambda }^{\left(v\right)}$ in (16) can be updated by

  $$\begin{array}{c}\hfill {\lambda }^{\left(v\right)}=\frac{1}{2\sqrt{tr\left({\left({\mathbf{F}}^{\left(v\right)}\right)}^{\mathrm{T}}{\mathbf{L}}_{\mathrm{h}}^{\left(v\right)}{\mathbf{F}}^{\left(v\right)}\right)}}\end{array}$$

  (32)
• Update ${\mathbf{T}}^{\left(v\right)}$, $\mathcal{Q}$, $\gamma$, and $\mu$. Below are the formulas for updating these variables:

  $$\begin{array}{c}\hfill {\mathbf{T}}^{\left(v\right)}={\mathbf{T}}^{\left(v\right)}+\gamma ({\mathbf{S}}^{\left(v\right)}-{\mathbf{K}}^{\left(v\right)})\end{array}$$

  (33)

  $$\begin{array}{c}\hfill \mathcal{Q}=\mathcal{Q}+\mu (\mathcal{F}-\mathcal{J})\end{array}$$

  (34)

  $$\begin{array}{c}\hfill \gamma =\min (\rho \gamma ,{\gamma }_{max})\end{array}$$

  (35)

  $$\begin{array}{c}\hfill \mu =\min (\rho \mu ,{\mu }_{max})\end{array}$$

  (36)

  where ${\mu }_{max}$, ${\gamma }_{max}$, and $\rho$ are constants.
  After obtaining ${\mathbf{F}}_u^{\left(v\right)}$, we can obtain discrete labels for unlabeled data using

  $$\begin{array}{c}{l}_i=\underset{j\in \left\{1,2,\dots ,c\right\}}{argmax}{\mathbf{F}}_u(i,j),\forall i=1,2,\dots ,u\hfill \end{array}$$

  (37)

  where ${\mathbf{F}}_u(i,j)$ refers to the i-th row and j-th column item of ${\mathbf{F}}_u=\left({\displaystyle \sum _{v=1}^m}{\lambda }^{\left(v\right)}{\mathbf{F}}_u^{\left(v\right)}\right)/m$. We denote the discrete label matrix ${\mathbf{Y}}_u=[{\mathbf{y}}_1;{\mathbf{y}}_2;...;{\mathbf{y}}_u]$, with elements $y_{ij}=1$ if $l_i=j$ ($j=1,2,\dots c$) and $y_{ij}=0$ otherwise.

Presented in Algorithm 1 is the complete pseudocode needed to solve (12).

Algorithm 1 Hypergraph Learning-Based Semi-Supervised Multiview Spectral Clustering

Input: Graph ${\mathbf{G}}^{\left(v\right)}$ for m views, label matrix ${\mathbf{Y}}_l$, the cluster number c, parameter $\alpha$, $\beta$ and p.

Output: Label information for unlabeled samples.

1: Initialize ${\mathbf{K}}^{\left(v\right)}={\mathbf{T}}^{\left(v\right)}=0$, ${\mathbf{S}}^{\left(v\right)}={\mathbf{G}}^{\left(v\right)}$, ${\lambda }^{\left(v\right)}=\frac{1}{m}$, ${\tau }^{\left(v\right)}=\frac{1}{m}$$(v=1,2,\dots ,m)$. $\mathcal{Q}=\mathcal{J}=\mathbf{0}$, $\mu =\gamma =0.1$, $\rho =2$, ${\mu }_{max}={\gamma }_{max}={10}^{10}$.  2: while not converge do  3:    Construct hyper-Laplacian matrices ${\left\{{\mathbf{L}}_{\mathrm{h}}^{\left(v\right)}\right\}}_{v=1}^m$ based on ${\left\{{\mathbf{S}}^{\left(v\right)}\right\}}_{v=1}^m$ by (15);  4:    Update ${\left\{{\mathbf{K}}^{\left(v\right)}\right\}}_{v=1}^m$ by using (19);  5:    Update ${\left\{{\mathbf{S}}^{\left(v\right)}\right\}}_{v=1}^m$ by solving (20);  6:    Update ${\left\{{\mathbf{F}}_u^{\left(v\right)}\right\}}_{v=1}^m$ by using (23);  7:    Update $\mathcal{J}$ according to (27);  8:    Update ${\tau }^{\left(v\right)}$ by solving (31);  9:    Update ${\lambda }^{\left(v\right)}$ by calculating (32); 10:   Update ${\left\{{\mathbf{T}}^{\left(v\right)}\right\}}_{v=1}^m$ and $\mathcal{Q}$ according to (33) and (34), respectively; 11:   Update $\gamma$ and $\mu$ according to (35) and (36), respectively; 12: end while 13: Return the indicator matrix $\mathbf{F}$. 14: Calculate label matrix ${\mathbf{Y}}_u$ by (37).

5. Experiment

5.1. Experimental Setting

Dataset. A comprehensive set of experiments was conducted to verify the validity and stability of the proposed model on four different datasets, including the following.

Yale dataset (http://vision.ucsd.edu/content/yale-face-database (accessed on 15 May 2023)). This dataset, created by Yale University, contains 165 face images of fifteen individuals. Each individual is represented by eleven grayscale images with varying postures, facial expressions, and lighting conditions. In the experiment, we chose 4096-dimensional (D) intensity features, 3304-D LBP features, and 6750-D Gabor features as three distinct types of views.

Caltech-101 dataset [36] This dataset comprises 8677 images divided into 101 classes, each containing 40 to 800 image files. For our experiment, we selected 1474 images belonging to seven categories: Snoopy, Windsor-Chair, Stop-sign, Face, Garfield, Dollar-Bill, and Motorbikes. We considered three types of features as distinct views, including 1160-D LBP features, 620-D HOG features, and 2560-D SIFT features.

ORL dataset (http://www.uk.research.att.com/facedatabase.html (accessed on 15 May 2023)). The ORL dataset includes 400 facial photographs of forty individuals, some taken at different times, resulting in variations in facial expressions, facial details, and lighting angles. We selected 6750-D Gabor features, 4096-D intensity features, and 3304-D LBP features as different views.

MSRC dataset [37] This dataset consists of 240 images in eight categories. We chose seven categories for our experiments: tree, building, cow, face, plane, car, and bicycle. We employed five visual features to construct multiple views, including 24-D CM features, 254-D Centrist features, 256-D LBP features, 512-D GIST features, and 576-D HOG features.

Comparison algorithms. In this paper, we evaluated the performance of the proposed clustering algorithm by comparing it with seven other clustering algorithms, namely, Adaptive Semi-Supervised Learning Approach for Multiple Feature Modalities (AMMSS) [21], i.e., the semi-supervised learning strategy for integration of multiple graphs based on sparse weights under label propagation (SMGI) [20], Multiple Graph Clustering Framework based on Automatic Weighting Strategy (AMGL) [6], Semi-Supervised Image Classification using Multiple-Modal Curriculum Learning (MMCL) [38], Multi-View Clustering with Adaptive Neighbors (MLAN) [23], Hyper-Laplacian Regularization-based Semi-Supervised Clustering with Multiple Views (HLR-M²VS) [28], and Fast Multi-View Semi-Supervised Learning (FMSSL) [24].

Evaluation Metrics. To comprehensively evaluate clustering performance, we employed three fundamental metrics in our experiments: accuracy (ACC) [39], purity [40], and normalized mutual information (NMI) [41]. For each of these metrics, a higher value signifies better clustering capability.

Parameter Settings. Our proposed model incorporates three trade-off parameters ($\alpha$, $\beta$, and p) that affect the final results. To obtain optimal performance, we adjusted $\alpha$ within the range of $[0.001,0.005,0.01,0.05,0.1,0.5,1,5]$, $\beta$ within the range of $[0.001,0.005,0.01,0.05,0.1,$$0.5,1]$, and the power parameter p within the range of $(0,1]$ with an interval of $0.1$. For the other comparison algorithms, we followed the experimental settings described in the respective studies or adjusted the parameters for optimal results.

5.2. Experimental Results

Results Analysis. To discover more valid information about the unlabelled data from the limited labeled data, we randomly selected between 10% and 60% of the labeled samples to be used in semi-supervised learning. Without loss of generality, the outcome is the average value obtained after repeating each experiment 10 times. Figure 5, Figure 6, Figure 7 and Figure 8 report the experimental results of the eight clustering algorithms under different label proportions on the four datasets. According to these clustering results, the following observations can be drawn.

(1) The overall performance of our algorithm and the HLR-M²VS algorithm is superior to that of the other six algorithms. This is because the other algorithms only consider pairwise relationships in the graph, resulting in the loss of effective information. Our work and the HLR-M²VS algorithm both focus on relationships between multiple sample points and employ hypergraph-induced hyper-Laplacian matrix to preserve higher-order geometric structures. In addition, both our work and the HLR-M²VS algorithm are based on the tensor, which can unearth the complementary information and spatial structure hidden in multi-view data. The other algorithms do not consider this factor. Despite this, it is apparent from the figures that the HLR-M²VS algorithm is less accurate and stable than ours. For example, on the Caltech-101 dataset the accuracy of the HLR-M²VS algorithm is 7.02% lower than ours for the case containing 10% of the labeled samples. The reason for this is that the HLR-M²VS algorithm assumes that all views have the same indicator matrix. It adopts the tensor nuclear norm instead of the tensor Schatten p-norm as the global constraint to ensure the consistency principle without considering the significant differences of all views and different singular values, resulting in poor algorithm performance in practical application.

(2) Overall, our method is significantly superior to the other seven methods on all four datasets. For example, on the Yale dataset, our method shows a remarkable increase in comparison to the MMCL of around 10.48%, 11.83%, and 10.48% in terms of ACC, NMI, and purity, respectively, for 40% labeled samples. On the MSRC dataset, for 20% labeled samples, our method shows a relative improvement of 2.38%, 5.08%, and 2.38% in terms of the ACC, NMI, and purity compared to the second-best method, HLR-M²VS. Our method emphasizes each view’s role in clustering by adaptively allocating appropriate weights for different views, thereby improving the algorithm’s flexibility. Moreover, our method integrates hypergraph learning and semi-supervised multi-view spectral clustering into a unified framework, and leverages the tensor Schatten p-norm to encode the complementary information and low-rank spatial structure. Thus, the learned indicator matrix is well able to characterize the clustering structure, and the clustering results accurately represent the categories of samples. It is worth noting that the clustering results on databases with different dimensions show that the dimension of the data affects the clustering results, and our method is sensitive to the data complexity.

(3) For the same dataset, the clustering performance of most algorithms improves with an increasing number of labeled samples. For example, as the proportion of labeled samples in the Caltech-101 dataset increases from $10\%$ to $60\%$, the clustering accuracy of the AMMSS algorithm correspondingly increases from $60.90\%$ to $73.63\%$, an improvement of $12.73\%$. Similarly, the clustering accuracy of our algorithm increases from $90.48\%$ to $97.25\%$, an increase of $6.77\%$. This shows that semi-supervised clustering can use limited labeled data to mine hidden information in unlabeled data for better clustering performance. In addition, a large amount of prior information can enhance the ability to infer unknown labels, further improving the clustering accuracy of the algorithm.

Parameters analysis. In (12), the $\beta$ parameter is utilized to balance the proportion of the tensor Schatten p-norm, while the $\alpha$ parameter represents the impact of the spectral clustering term on the model. To analyze the influence of these two parameters on the clustering performance of our model, we present a 3D histogram in Figure 9 that visualizes the clustering accuracy obtained with different parameter settings on the Caltech-101, Yale, ORL, and MSRC datasets.

Specifically, in order to determine the most favorable results, all of our experiments were conducted with the $\alpha$ parameter in the range of [0.001, 0.005, 0.01, 0.05, 0.1, 0.5, 1, 5] and the $\beta$ parameter in the range of [0.001, 0.005, 0.01, 0.05, 0.1, 0.5, 1]. Based on the data in Figure 9, the clustering performance fluctuates significantly with varying $\alpha$ and $\beta$. Our approach achieves optimal clustering performance on the Yale dataset when $\alpha =0.5$ and $\beta =1$, and the case is similar for the Caltech-101, ORL, and MSRC datasets.

The experimental results are relatively stable within a specific range. When $\alpha >0.05$, the clustering performance of our model substantially improves. This improvement may be attributed to the spectral clustering term preserving higher-order geometric structures using the hypergraph-induced hyper-Laplacian matrix, which helps the model to perform better. Furthermore, the tensor Schatten p-norm explores the complementary content between different views. Therefore, selecting a reasonable value for $\beta$ after determining the value of $\alpha$ contributes to higher model accuracy.

Convergence analysis. Research suggests that demonstrating the convergence of inexact ALM with three or more block variables remains an open question [42]. Consequently, it is not easy to demonstrate the convergence of Algorithm 1 theoretically. To facilitate further analysis, we recorded ${\displaystyle \sum _{v=1}^m}{∥{\mathbf{F}}_{(t+1)}^{\left(v\right)}-{\mathbf{J}}_{(t+1)}^{\left(v\right)}∥}_{\infty }$ for each iteration on the four databases presented in Figure 10. Note that ${\mathbf{F}}_{(t+1)}^{\left(v\right)}$ and ${\mathbf{J}}_{(t+1)}^{\left(v\right)}$ respectively represent the ${\mathbf{F}}^{\left(v\right)}$ and ${\mathbf{J}}^{\left(v\right)}$ matrices obtained by the ($t+1$)-th iteration. The x-axis represents the number of iterations for each sub-plot, while the y-axis corresponds to the variable error. Figure 10 illustrates that the variable error drops rapidly within relatively few iterations and stabilizes as the number of iterations increases, indicating that our model converges sufficiently.

Complexity Analysis. Our method consists of two stages, namely, construction of hypergraphs and optimization by iteratively solving Equation (16). The cost of constructing the initial k-nearest neighbors graph is ${𝒪}_1(m{n}^{2}d+m{n}^{2}log\left(n\right))$. Then, we mainly focus on the optimization of four variables, i.e., ${\mathbf{F}}^{\left(v\right)}$, $\mathcal{J}$, ${\mathbf{S}}^{\left(v\right)}$, and ${\mathbf{K}}^{\left(v\right)}$. For the ${\mathbf{F}}^{\left(v\right)}$ subproblem, it takes ${𝒪}_2(m{u}^3+mucn)$ in each iteration. For the $\mathcal{J}$ subproblem, calculating the 3D FFT and 3D inverse FFT of an $n\times m\times c$ tensor and c SVDs of $n\times m$ matrices in the Fourier domain dominates the main computation. Because we have $n\gg m$ in the multi-view setting, the computation at each iteration takes ${𝒪}_3(mnclog\left(mn\right)+m^{2}cn)$. In terms of the ${\mathbf{S}}^{\left(v\right)}$ subproblem, it takes ${𝒪}_4\left(m{n}^{2}log\left(n\right)\right)$ in each iteration. For the ${\mathbf{K}}^{\left(v\right)}$ subproblem, it takes ${𝒪}_5\left(m{n}^2\right)$ in each iteration. Therefore, the main computational complexity of our proposed method in each iteration is $𝒪={𝒪}_1+{𝒪}_2+{𝒪}_3+{𝒪}_4++{𝒪}_5$.

6. Conclusions

In this paper, we propose a hypergraph learning-based semi-supervised multi-view spectral clustering method. This method first adaptively learns the affinity matrix of each view, then fully considers the relationship between multiple sample points. It uses the learned affinity matrix to construct hypergraphs while preserving the higher-order geometric structure through the hypergraph-induced hyper-Laplacian. This technique effectively explores higher-order information and complex structures in the data while avoiding dependence on predefined graphs. Moreover, the proposed method simultaneously learns the indicator matrix for all views, and employs the tensor Schatten p-norm to uncover the low-rank spatial structure and complementary content hidden in these views. As a result, the learned common indicator matrix can more effectively reflect the cluster structure. We additionally design a simple auto-weighted scheme for the tensor Schatten p-norm which adaptively determines the ideal weighted vector to accommodate differences between singular values, thereby enhancing the algorithm’s flexibility and stability in practical applications. Experiments on four real datasets demonstrate that our method outperforms cutting-edge competitors regarding overall effectiveness.

The hypergraph learning approach and automatic weighting strategy proposed in this paper can serve as valuable references for researchers in other fields. In future work, we intend to continue to investigate more effective methods for mining higher-order information and complex structures in data. In semi-supervised learning, we intend to study the ratio between labeled and total samples in order to identify the optimal proportion, enabling the algorithm to achieve the best possible clustering performance with minimal labeled data as support. The research work in this paper focuses on the construction of multiple complex relationships between data while ignoring the generalization and scalability of the algorithm. Due to its high computational complexity, the proposed algorithm is not suitable for large-scale data. In future studies, the proposed method could be improved based on the relevant theory of anchors to make it more applicable to large-scale data. On the other hand, thanks to the powerful nonlinear mapping ability and feature extraction ability of deep learning, it has become a research trend to flexibly apply deep learning to different fields. Therefore, in forthcoming research another possibility is to use the traditional clustering model with deep learning or to effectively integrate traditional methods with deep networks as a means of effectively improving clustering performance.