Multi-view Regression Clustering via Low-Rank Manifold Decomposition

1 Introduction

Clustering is a fundamental problem in unsupervised learning, aiming to partition samples into homogeneous groups such that intra-cluster similarity is maximized while intercluster similarity is minimized. Due to its broad applicability, clustering has been extensively studied in data mining, image processing, bioinformatics, and related fields [Zhao et al., 2026; Zhao et al., 2016]. With the rapid diversification of data acquisition modalities, modern datasets are increasingly collected from multiple heterogeneous sources or perspectives. This has given rise to multi-view clustering (MvC), which seeks to exploit complementary yet consistent information across views to obtain more accurate and robust clustering results than single-view approaches.

∗Corresponding author.

Among existing MvC methods, similarity-graph-based models have demonstrated strong capability in capturing complex, non-Gaussian cluster structures. Typically, viewspecific similarity graphs are constructed and fused into a shared graph, from which clustering results are obtained via spectral decomposition. To improve partition quality, adaptive graph-based methods impose rank constraints on the Laplacian matrix, forcing the shared graph to decompose into exactly c connected components, each corresponding to a cluster [Nie et al., 2017a; Wang et al., 2019; Zhao et al., 2026]. More recent studies further refine this framework by disentangling view-specific graphs into consistent and inconsistent components, or by modeling highorder neighborhood relations through tensors, hypergraphs, or diffusion processes [Huang et al., 2022; Lin et al., 2023; Liu et al., 2025; Jiang et al., 2025a].

Despite their effectiveness, graph-based MvC methods suffer from a fundamental scalability bottleneck. Constructing an n × n similarity graph requires O(n2 ) pairwise computations (where n is the number of samples), followed by a spectral decomposition with O(n3 ) complexity, which limits scalability to large datasets [Jiang et al., 2025b]. More importantly, this computational burden is tightly coupled with a deeper modeling issue: pseudo-labels are not learned directly from the data geometry but are instead obtained through a secondary clustering step applied to spectral embeddings. As a result, pseudo-label inference is inherently decoupled from the original data distribution and the optimization objective, which may lead to suboptimal clustering solutions.

To reduce graph construction costs, anchor-based MvC methods replace the similarity graph with an n × m bipartite graph (m ≪ n) linking samples to a compact anchor set. Within this framework, two paradigms have emerged: the first adopts matrix factorization, decomposing each viewspecific data matrix into anchor representations and a bipartite coefficient matrix [Wang et al., 2022; Liu et al., 2022b; Zhang et al., 2024]; the second directly models sampleto-anchor relationships, avoiding explicit anchor alignment across views [Qiang et al., 2021; Shi et al., 2023; Chen et al., 2025]. Although these reduce computational complexity, they introduce new challenges.

Specifically, increasing the number of anchors improves representational capacity but inevitably degrades efficiency, leading to an inherent trade-off between clustering accuracy and computational cost. Moreover, determining the optimal number of anchors is an NP-hard problem, making anchor selection highly sensitive and data-dependent. More fundamentally, most anchor-based methods inherit the twostage pipeline of graph-based clustering, where representation learning and pseudo-label inference are performed separately and final cluster assignments are obtained via postprocessing steps such as spectral clustering or K-Means. Consequently, pseudo-label learning remains decoupled from the intrinsic data geometry, and scalability is achieved at the expense of modeling consistency.

In essence, existing graph-based and anchor-based MvC methods are constrained by an inherent conflict between scalability and geometry-consistent pseudo-label learning. Addressing one aspect often exacerbates the other. This observation naturally raises the following question: Can multi-view clustering be reformulated to directly infer pseudo-labels from multi-view data in a scalable manner, without relying on explicit similarity graph construction or anchor selection?

To answer this question, we propose Multi-view Clustering via Manifold Decomposition (MvMD). Fig. 1 illustrates the overall framework of MvMD, which reformulates multiview clustering as a regression problem, where the cluster assignment matrix F is directly optimized rather than obtained via a post hoc clustering step. Within linear-time complexity, MvMD preserves the low-rank structure of F, enforces manifold-based smoothness, and mitigates the risk that improper initialization fails to identify small clusters commonly observed in real-world data. The main contributions are summarized as follows:

• We propose a novel multi-view clustering framework by reformulating MvC as a unified multi-view regression problem, which enables direct inference of cluster assignments and alleviates the tendency to miss small clusters through a global balance regularization.
• We introduce a symmetric matrix factorization on similarity matrices to enforce the low-rank property and enhance the local smoothness of cluster labels, which is efficiently realized via truncated SVD-based low-rank approximation without explicit graph construction.
• We develop an efficient alternating optimization algorithm. Extensive experiments on benchmark datasets demonstrate that the proposed method consistently outperforms state-of-the-art approaches in terms of both clustering accuracy and computational efficiency.

Throughout this paper, matrices are denoted by bold Roman uppercase letters (e.g., M), vectors by bold Roman lowercase letters (e.g., m), and scalars by regular lowercase letters (e.g., m). The operators M⊤, Tr(M), and rank(M) represent the transpose, trace, and rank of a matrix, respectively. The Frobenius norm of M is defined as ∥M∥F . The symbols 1, 0, and I represent a column vector of ones, a zero matrix, and an identity matrix, respectively.

2 RelatedWork

2.1 Unsupervised Regression Clustering

As a label-free technique, unsupervised regression clustering captures linear relationships between samples and their pseudo-labels, making it well suited for clustering. Early efforts mainly focus on enhancing robustness and discriminability by incorporating graph regularization [Hou et al., 2014], non-negativity and sparsity constraints [Li and Tang, 2015], or sparse residual modeling to suppress outliers [Shi et al., 2014]. However, most of these methods decouple similarity graph construction from regression optimization, typically relying on Gaussian kernels or k-NN graphs built in a preprocessing step, thereby overlooking their intrinsic interaction. To address this issue, Li et al. [Li et al., 2018] proposed a unified framework that jointly learns the similarity graph and regression model, enabling adaptive neighborhood structures. Peng et al. [Peng et al., 2019] further improved robustness by imposing low-rank constraints on the learned graph and sparsity on feature selection. Despite these advances, existing approaches still depend on explicit graph construction, which limits scalability on large-scale data.

2.2 Similarity-DrivenMulti-ViewClustering

Similarity graph learning constitutes a core component of most multi-view clustering methods. The dominant paradigm follows a two-stage process: constructing view-specific graphs and integrating them for partitioning. Early methods use fixed similarity measures like Gaussian kernels, which are efficient but often insufficient for complex structures. To improve flexibility, recent studies focus on adaptive and unified graph learning. Chen et al. [Chen et al., 2021] proposed a low-rank tensor graph framework that jointly learns representations and affinity matrices, enhancing robustness. Jiang et al. [Jiang et al., 2022] incorporated latent-space feature enhancement and self-expressiveness to preserve inter-view consistency. Along this line, Nie et al. introduced adaptive view weighting to jointly optimize graph construction and clustering, inspiring a series of subsequent works [Li et al., 2019; Shi et al., 2024; Zhao et al., 2025]. Nevertheless, these methods still rely on spectral decomposition of similarity graphs, posing scalability challenges.

3 Methodology

Regression-based clustering directly treats cluster assignments as optimization variables, enabling one-step inference of clustering results rather than relying on post hoc partitioning [Liu et al., 2017; Zhang et al., 2020]. This property motivates us to revisit multi-view clustering from a regression perspective and develop the proposed model as follows:

where p is the number of views. For the v-th view, Xv ∈ Rdv×n denotes the data matrix, whose columns are normalized to unit length with non-negative features; Wv ∈ Rdv×c is the projection matrix ensuring uncorrelated subspace dimensions; and bv ∈ R1×c denotes the bias. F denotes cluster assignment matrix, with fij indicating the probability of assigning the i-th sample to the j-th cluster. α = [α1, . . . , αp]⊤ denotes the view-weight vector. λ is the regularization parameter. The first term promotes cross-view consistency in the clustering space by minimizing the weighted regression error between the projected features of each view and the unified cluster assignment matrix. The second term prevents the optimal solution of F from converging to a hard clustering [Liu et al., 2022a], while ensuring a more balanced assignment distribution, thus mitigating the issue where improper initialization may fail to detect small clusters.

Symmetric nonnegative matrix factorization (SNMF) has proven effective for clustering data with nonlinear structure [Kuang et al., 2015]. To further enhance the local smoothness of cluster assignments, we improve SNMF by relaxing part of the nonnegativity constraint while enforcing stronger low-rank properties on F. For the normalized data Xv in the v-th view, the symmetric nonnegative similarity matrix is constructed as:Sv = X⊤v Xv (2)

where Sv ≥ 0 represents the pairwise similarity between samples. After performing truncated SVD on X⊤v , we obtain the top c left singular vectors Cv ∈ Rn×c , and the corresponding singular value matrix Λv ∈ Rc×c . Consequently, the low-rank version of Sv is expressed as:

where Qv ∈ Rc×c is an arbitrary orthonormal matrix. It is obvious that Q⊤v Qv = QvQ⊤v = I. According to the EckartYoung-Mirsky theorem, ̂Sv is the optimal rank-c approximation of Sv under both the Frobenius and spectral norms. We thus formulate the low-rank symmetric matrix factorization for the v-th view as:

(4)

To avoid the quadratic complexity of Eq. (4), we derive a tractable surrogate as follows:

By applying the sub-multiplicative property of the Frobenius norm and the triangle inequality, we obtain ∥FF⊤ - (CvΛvQv)(CvΛvQv)⊤∥F ≤ (∥F∥F +∥CvΛvQv∥F )∥FCvΛvQv∥F where ∥F∥2F ≤ n. Under the common low-rank assumption in clustering, i.e., c ≪ n and the dominant energy is captured by the leading singular values, ∥CvΛvQv∥F is bounded and grows significantly slower than n. Consequently, the objective function in Eq. (4) can be upperbounded by a scaled version of ∥F-CvΛvQv∥F . Furthermore, the low-rank structure of CvΛvQv induces an approximate low-rank property in F.

To achieve high-quality multi-view clustering, Eqs.(1) and (5) can be integrated into a unified framework. Consequently, the MvMD model is formulated as:

where the regularization parameter β controls the trade-off between local manifold regularization and regression fidelity.

4 Optimization Algorithm

In this subsection, we propose an alternating optimization algorithm to solve Eq. (6) by cyclically updating each variable while keeping the others fixed.

(1) Optimize bv

When Qv, F, Wv, and αv are fixed, bv can be updated by:

(2) Optimize Wv

When Qv, F, bv, and αv are fixed, the Eq. (6) reduces to:

where Pv = XvX⊤v ∈ Rdv×dv . It is evident that Eq. (8) can be equivalently reformulated as:

where ˜Pv = δIdv -Pv, and δ is a regularization parameter introduced to ensure the positive definiteness of ˜Pv. To solve this optimization problem, we adopt the following power iteration method proposed in [Nie et al., 2017b].

(3) Optimize Qv

WhenWv, F, bv, and αv are fixed, the Eq. (6) reduces to:

Since Eq. (10) shares the same structure as Eq. (9), the corresponding minimization problem can similarly be reformulated as a maximization problem. UnlikeWv in Eq. (9), the matrix Qv satisfies both QvQ⊤v = I and Q⊤v Qv = I. Therefore, the Eq. (10) can be further simplified as:

This subproblem reduces to an orthogonal Procrustes problem, and the optimal solution of Qv can be optimized by performing SVD on (CvΛv)⊤F.

(4) Optimize F

When Wv, Qv, bv, and αv are fixed, the Eq. (6) can be reformulated as follows:

where A = ∑pv=1 α2v (X⊤v Wv+1b⊤v +βCvΛvQv) ∑pv=1 α2v (1+β) . By introducing the auxiliary variable B, and setting B = F, the corresponding augmented Lagrangian function is formulated as:

where Ψ is the Lagrange multiplier matrix, and µ is the penalty parameter.

The subproblem for B is expressed as:

Setting the derivative of the objective function in Eq. (14) with respect to B to zero, we have:

The subproblem for F is formulated as:

Notably, each row of F can be solved independently through the method proposed in [Nie et al., 2014].

Finally, the Lagrange multipliers are updated as follows:

where ρ is the learning rate. The complete optimization procedure for Eq. (12) is summarized in Algorithm 1.

(5) Optimize αv

WhenWv, Qv and F are fixed, the Eq. (6) reduces to:

where µv = ∥∥∥X⊤v Wv + 1b⊤v - F∥∥∥2 F +β ∥CvΛvQv - F∥2F . By introducing the Lagrange multiplier ξ, the corresponding Lagrangian function of Eq. (19) can be formulated as:

By taking the derivative of Eq. (20) with respect to ξ and setting it to zero, we obtain:

Algorithm 1 Efficient Algorithm for Eq. (12)

Input: Normalized data matrix X = {X1, . . . ,Xp}, initial cluster assignment matrix F, projection matrices Wv, Qv, truncated SVD factors CvΛv, bias vectors bv, weights αv, and regularization parameters β and λ.

Output: The cluster assignment matrix F.

1: Initialize

• 2: B= F;
• 3: µ = 0.01; ρ = 1.1; Ψ = 0;
• 4: while not converge do
• 5: Update B by Eq.(15);
• 6: Update F by solving Eq.(16);
• 7: Update Ψ by Eq.(17);
• 8: Update µ by Eq.(18);

By applying the Karush-Kuhn-Tucker (KKT) conditions under the constraint 1⊤α = 1, the optimal solution for each αv can be derived as:

The complete optimization procedure for Eq. (6) is summarized in Algorithm 2.

5 Complexity Analysis

The time complexity of MvMD consists of an initialization stage and an iterative optimization stage. In the initialization stage, for each view, the matrix CvΛv is constructed from Xv via truncated singular value decomposition, resulting in a time complexity of O(ndvc + nc2 ). In the iterative stage, updating all bv incurs O(ndc), where d = ∑pv=1 dv. Updating Wv and Qv across all views requires O(c ∑pv=1 d2v +ndc+dc2 ); updating F involves computing the auxiliary matrix A with complexity O(ndc) followed by a row-wise optimization costing O(nc log c); and updating the view weights α requires O(ndc + pnc2 ).

Given that c ≪ d ≪ n and p ≪ n, which typically holds for large-scale datasets, the overall computational complexity of MvMD can be approximated as O(ndcT), where T denotes the number of iterations in Algorithm 2.

6 Experiments

6.1 Experimental Setup

MvMD is compared with nine representative multi-view clustering algorithms: Graph-based Multi-view Clustering (GMC) [Wang et al., 2019], Structured Graph Learning for Scalable Subspace Clustering: From Single View to Multi-view (SGL) [Kang et al., 2021], Efficient One-Pass

1 https://predictioncenter.org/

2 http://lig-membres.imag.fr/grimal/data.html#

3 https://www.cs.tau.ac.il/∼wolf/ytfaces/

Algorithm 2 : Efficient Algorithm for Eq. (6)

Input: Normalized data matrix {X1, . . . ,Xp}, and regularization parameters β and λ.

Output: The cluster assignment matrix F.

• 1: Initialize F;
• 2: Initialize the projection matrices Wv and Qv to satisfy W⊤ v Wv = I and Q⊤v Qv = I, respectively;
• 3: Initialize αv = 1/p for all views;
• 4: repeat
• 5: Update bv by bv = ( 1n F⊤1-W⊤ v Xv1);
• 6: UpdateWv by solving Eq. (9);
• 7: Update Qv by solving Eq. (11);
• 8: Update F via Algorithm 1;
• 9: Update αv according to Eq.(22);
• 10: until Convergence.

Multi-view Subspace Clustering with Consensus Anchors (EOMSC) [Liu et al., 2022c], Efficient Multi-view K-Means Clustering with Multiple Anchor Graphs (EMKMC) [Yang et al., 2023], Auto-Weighted Multi-view Clustering for Large-Scale Data (AWMvC) [Wan et al., 2023], Efficient Multi-view Graph Clustering with Local and Global Structure Preservation (EMvGC) [Wen et al., 2023], Efficient Multiview Clustering via Unified and Discrete Bipartite Graph Learning (UDBGL) [Fang et al., 2024], Dual-Constraint Multi-view Fuzzy Clustering with Scalable Anchor Graph Learning (DMFC) [Cui et al., 2025], and Fast Multiview Anchor-Graph Clustering (FMAGC) [Yang et al., 2025].

The datasets used in our experiments are shown in Table 1. For each view, samples are normalized to unit length and have non-negative feature values. To evaluate clustering performance, we adopt three widely used metrics: Accuracy (ACC), F1-score, and Normalized Mutual Information (NMI), where higher values indicate better performance. For our MvMD, the regularization parameters β and λ are selected from {10-4 , 10-3 , 10-2 , 10-1 , 100 , 101 , 102 , 103 , 104 }. The initial cluster assignment matrix is obtained by applying Kmeans++ to the concatenated multi-view features. For other methods, the number of anchors m is selected from {2c, 3c, 4c, 5c}; other hyper-parameters follow their original papers. Each algorithm is executed 10 times, and the average best results are reported. All experiments are conducted in MATLAB R2021b on Linux with an Intel Core i7-12700KF CPU and 64GB RAM.

6.2 Clustering Results

Table 2 reports the clustering performance of ten MvC methods, where variances are not applicable for non-randomized (deterministic) algorithms. We observe: (1) FMAGC typically outperforms most anchor-based clustering methods. A possible explanation is that it derives discrete pseudo-labels directly through similarity graph decomposition, thereby avoiding secondary clustering. This highlights the benefit of decomposing similarity graphs for clustering. By comparison, GMC constructs a complete large-scale similarity graph, but its reliance on secondary clustering tends to introduce instability. (2) The proposed MvMD consistently achieves the best performance across most datasets. For example, on BDGP, MvMD surpasses the second-best method by 2.5% (ACC), 4.7% (F1-score), and 4.73% (NMI). This advantage stems from its ability to jointly capture global and local structural information. Specifically, the balance-constrained unsupervised regression directly produces cluster labels, promoting globally consistent assignments, while low-rank approximation preserves local label smoothness. These complementary components contribute to the superior performance of MvMD.

6.3 Running Time

To evaluate the efficiency of MvMD, Fig. 2 presents its running time alongside baseline methods across all datasets. MvMD achieves a runtime comparable to the most efficient baselines, consistent with the theoretical analysis indicating linear complexity in sample size.

6.4 Parameter Sensitivity and Convergence

MvMD involves two hyper-parameters, β and λ. In unsupervised settings, we select parameters based on ACC. Fig. 3 reports the sensitivity results, where good performance is consistently achieved at β = 100 and λ = 100.

To examine the convergence of Algorithm 2, the objective value is tracked across iterations. As shown in Fig. 3, it decreases monotonically and converges within 20 iterations, confirming empirical convergence.

6.5 Ablation Experiments

Five ablation variants are designed to evaluate the contribution of each module in MvMD. Ab-1 to Ab-5 respectively retain: (i) only the regression term, (ii) only the low-rank approximation term, (iii) the regression termwith balance regularization, (iv) the regression termwith low-rank approximation, and (v) the low-rank approximation with balance regularization. The ACC results are reported in Fig. 4.

In most cases, combining any two components improves clustering performance over each individual component. Moreover, all ablation variants underperform the complete MvMD model, highlighting the necessity of jointly integrating all components. This suggests that neither low-rank manifold decomposition nor balance-aware regularization alone suffices to fully exploit unsupervised regression clustering. Their joint integration with proper weighting is crucial for superior performance.

7 Conclusion

In this paper, we proposed MvMD, a scalable multi-view clustering framework that directly learns cluster assignments from multi-view data. By formulating clustering as a unified multi-view regression problem with balance-aware and geometry-preserving regularization, MvMD avoids explicit similarity graph construction and anchor selection. Extensive experiments on benchmark datasets demonstrate that MvMD consistently outperforms SOTA methods in both clustering accuracy and efficiency.

Acknowledgments

This work is supported by the National Natural Science Foundation of China (Grant Nos. 62506279 and 62541326), and the Major Scientific and Technological Innovation Project of Xianyang (Grant No. L2025-ZDKJ-ZDGG-RGZN-001).