Fast Unpaired Multi-view Clustering

1 Introduction

In recent years, driven by rapid advancements in science and technology, significant volumes of data have been amassed from diverse sources or feature extractors to delineate a singular entity, giving rise to the construction of multi-view data [Cai et al., 2024; Yao et al., 2023; Zhang et al., 2022; Li et al., 2023a]. For instance, a singular news story can be preserved and disseminated through various formats such as video, audio, and text. Moreover, it can also be reported in disparate nations, spanning distinct languages like Chinese, English, Russian, and French. The recent surge in multi-view clustering (MVC) finds its impetus in its ability to harness the affinity between samples and views [Zhang et al., 2023; Chen et al., 2023b; Lu et al., 2023; Sun et al., 2023b]. This allows for the effective amalgamation of consistency and complementary attributes inherent in multi-view data, ultimately leading to the attainment of optimal cluster allocation outcomes [Cai et al., 2022; Chen et al., 2024; Sun et al., 2023a; Li et al., 2022].

∗Corresponding author.

The existing MVC critically hinges on an implicit assumption that each sample collected and stored from different views is perfectly aligned and paired, implying the same positional arrangement across all views. However, this assumption is facilely contradicted in practical applications, destroying the cross-view consistency and complementary of paired data and causing intricate challenges in dealing with unpaired multi-view data, named the Arbitrary View-unpaired Problem (AVP). Presently, only a few deep or shallow attempts have been made to address view-unpaired data [Yu et al., 2021; Lin et al., 2022; Huang et al., 2020; Yang et al., 2021; Yang et al., 2023]. To our knowledge, existing most deep methods [Huang et al., 2020; Yang et al., 2021; Yang et al., 2023] require partially paired data as the training data, which greatly limits practicality. Comparatively, the above shallow methods [Yu et al., 2021; Lin et al., 2022] apply to handle fully unpaired multi-view data. Regrettably, these shallow endeavors involve constructing sample n square affinity graphs, whose computations suffer from n cube computational complexity and n square storage complexity, both waning their applicability in large-scale data tasks.

As a potent approach for handling large-scale data, the anchor technique facilitates the sampling or learning of a limited set of m representative anchor points (m << n) from n original multi-view samples. Constructing a bipartite graph of dimensions m ∗ n, these techniques remarkably alleviate the spatial and temporal complexities from O(n2 ) and O(n3 ) to O(n), consequently significantly diminishing the computational and storage burdens. Existing anchor techniques emerge two primary classes: (1) static anchor learning encompasses methods such as random extraction, kmeans, and VDA anchor selection policies [Kang et al., 2021;

Xia et al., 2022]. (2) dynamic anchor learning simultaneously learns anchors and bipartite graphs dynamically, where also a consistent bipartite graph is learned to feed into final clustering [Wang et al., 2021; Ji and Feng, 2023; Dong et al., 2023]. Both for static and dynamic anchor learning, learning a consistent bipartite graph plays a vital role in the final clustering results. Unlike static learning, dynamic anchor learning adjusts anchors dynamically in line with the model's requirements during optimization. Existing dynamic anchor learning based methods mainly include two classes: View-consistent anchor learning [Chen et al., 2022] and view-specific anchor learning [Wang et al., 2022]. Although effective, they can only address paired multi-view data. While multi-view data tends to be unpaired in real applications, causing existing anchor based methods to fail. Taking two views of Fig. 1 as an example, both popular viewconsistent anchor learning in Fig. 1 (b) and view-specific anchor learning in Fig. 1 (c) would fail to directly learn a consistent bipartite graph from the unpaired multi-view data. Because consistency and complementary of multiple views get disrupted.

Intuitively, it is difficult to directly learn consistent anchors from unpaired data via Fig. 1 (b). So we use view-specific anchor learning of Fig. 1 (c) to learn a consistent bipartite graph from unpaired multi-view data for clustering. We observe two challenging issues required to be considered: (1) How to avoid learning unaligned or weak cross-view anchors from unpaired data? See Fig. 1 (c), blue anchor (blue star) of View 1 and red anchor (red star) of View 2 have unaligned order and unaligned number; Even worse, View 2 may suffer from blue anchor absence. (2) With the aligned and powerful anchors, how to learn a consistent bipartite graph from the unpaired multi-view data? To address these two challenging issues, we propose a novel Fast Unpaired Multiview Clustering (FUMC) framework for large-scale multiview clustering. Specifically, for a first tricky challenge, we dexterously designed a novel inverse local manifold learning paradigm to learn aligned and powerful view-specific anchors by predefining a prior similarity matrix according to the desired anchor order and anchor number. With the aligned and powerful anchors, we further design a bipartite graph matching framework, which enforces multiple view-specific bipartite graphs to align a powerful bipartite graph learned from best-view data. To do so, we could learn a consistent bipartite graph from unpaired multi-view data for fast clustering. Primary contributions are summarized as follows:

• We design a new inverse local manifold learning paradigm to enforce the learned anchors towards pairing and balancing, thereby ensuring alignment, fairness, and power of learned anchors in unpaired multi-view data.
• We design an ingenious bipartite graph matching framework to align unpaired bipartite graphs, obtaining a consistent bipartite graph from unpaired multi-view data.
• We propose a novel FUMC framework. To the best of our knowledge, this is the first attempt to handle unpaired multi-view data with the anchor technique. Extensive experiments on shallow and deep SOTA methods verify the superiority of our FUMC.

2 RelatedWork

2.1 UnpairedMulti-view Subspace Clustering

Lately, only a handful of studies have attempted to address the Arbitrary View-unpaired Problem for Unpaired Multi-view Subspace Clustering (UMSC) [Yu et al., 2021; Lin et al., 2022]. These endeavors involve constructing candidate affinity graphs for each view, expanding them into nsquare dimensions, and subsequently aligning them using nby-n matching matrices to learn an aligned consensus graph. This aligned graph is fed into spectral clustering to obtain final clustering results. Note that both n-by-n graphs and n-by-n matching matrices suffer from O(n3 ) time complexity and O(n2 ) space complexity, which waning their applicability in large-scale tasks. Compared to the above shallow methods, although some deep unpaired multi-view clustering methods are proposed [Huang et al., 2020; Yang et al., 2021; Yang et al., 2023], they suffer from the limitation of partially paired data as the training data.

2.2 Anchor-basedMulti-viewClustering

Recently, dynamic anchor learning-based multi-view clustering [You et al., 2023; Ji and Feng, 2023] has been highly effective in efficiently managing extensive datasets and achieved promising progress. Their success critically hinges on an implicit assumption that each sample across views is perfectly aligned and paired, such that they could make full use of the consistent and complementary information of paired multi-view data. Further, due to m ≪ n, they could alleviate time and space complexities significantly [Dong et al., 2023]. Two widely used base paradigms are

where S ∈ Rm∗n is a consistent bipartite graph, which builds a connection between view-consistency/view-specific anchor P ∈ Rk∗m/Pr ∈ Rdr ∗m and paired multi-view data {Yr }vr=1 ∈ Rdr ∗n . m and k are anchor number and dimension of shared subspace, respectively. dr is the dimension of r-th view. The final clustering result is obtained from S and its quality greatly depends on final performance. Φ(·) and Ψ(·) denotes view-consistency and view-specific anchor graph learning frameworks, respectively. R is the regularization term. From Fig. 1, when samples across different views become unpaired/unaligned, causing inconsistent bipartite graph structures across views naturally. Thus, existing anchor-based multi-view clustering would fail since they cannot learn a consistent S from the unpaired multi-view data.

3 Formulation

3.1 FUMC Framework

From the analysis of Fig. 1, using anchor technique to perform unpaired multi-view clustering need to address two challenges. To address these two issues, we propose a novel general anchor graph learning framework, named Fast Unpaired Multi-view Clustering (FUMC). Specifically, we first design an inverse local manifold learning paradigm, which aims to learn cross-view anchors with manifold pro-

tection like in Fig. 2 (b) from the high-dim manifold spaces

in Fig. 2 (a). Then, we further design a bipartite graph match-

ing framework, which enforces multiple view-specific bipar-

tite graphs to align a powerful bipartite graph learned from

best-view data.

Overall, FUMC aims to learn powerful and paired viewspecific anchors from unpaired multi-view data, and then construct a consistent graph for clustering. To learn powerful and paired anchors, we first require our learned anchors to have five following properties:

• P1: Intra-view Inter-cluster Discriminative: Anchor features in distinct clusters should manifest robust independence and relate to separate low-dimensional linear subspaces.
• P2: Intra-view Intra-cluster Compressible: Anchor features within the same cluster should display significant correlation and be linked to a common low-dimensional linear subspace.
• P3: Inter-view anchor order alignment: The order of anchors in the same clusters from different views is equal.
• P4: Intra-viewMaximally Diverse Anchors: Anchor features should be as large as possible as long as anchor features for each cluster stay uncorrelated from the other clusters.
• P5: Inter-view anchor number alignment: The number of anchors in the same clusters from different views is equal.

To achieve this goal, we design the following inverse local manifold learning scheme as the following:

R∆P (Pb , Pr , G) = ∑vr=1 ∑mi=1 ∑mj=1 (∥pbi - prj ∥2F )gij + ∑vr=1 ∥(Pr )⊺Pr - Im∥2F , where the G ∈ Rm∗m is the prior matrix to guide the learned anchors to satisfy 5 properties (P1-P5). Each element gij of G encodes the similarity between i-th anchor pbi of b-th best view and j-th anchor prj of r-th view in the manifold space. Thus, if we require pbi and prj to be paired in the same cluster, gij should be greater than zero to drag these two anchors to be closer. Inversely, gij = 0 would separate pbi and prj as possible. Inspired by this, we predefine a prior G to enforce cross-view anchors toward satisfying P1-P4 properties. Meanwhile, orthogonal constraints make anchor matrices satisfy the P5. Pb is an anchor matrix corresponding to the best-view data Xb , which is learned beforehand by performing Silhouette Coefficient [Lin et al., 2022] on {X}vr=1 . To do so, the learned cross-view anchors avoid order misalignment, number misalignment, or even anchor absence in some clusters as shown in Fig. 1 (c).

With the paired cross-view anchors at hand, we further construct bipartite graphs from these anchors, and then align them to generate a consistent graph for clustering by the following bipartite graph matching framework

R∆S (Sb , Sr ,Wr ,G) = Tr(∑vr=1 (Sb )⊺LGWr Sr ) + ∥Z∥ETNN, where Z ∈ Rm∗n∗v = Ψ(Sb ,Wr Sr , · · · ,Wv Sv ) is a tensor stacked by a best-view bipartite graph Sb ∈ Rm∗n and multiple bipartite graphs {Sr ∈ Rm∗n }vr=1,r̸=b with rotation matrices {Wr ∈ Rm∗m}vr=1,r̸=b . ∥ · ∥ETNN is a new Enhanced Tensor Nuclear Norm (ETNN) to exploit the better lowrank property of the core matrix whose entries are from the diagonal elements of a core tensor. Laplacian matrix LG = T-G, where the degree matrix T is a diagonal matrix with Tii = ∑mj=1 Gij . Overall, R∆S (Sb , Sr ,Wr , G) could align Sr to Sb with rotation matrixWr and G. In this way, a consistent bipartite graph S∗ = Sb + ∑vr=1,r̸=b Wr Sr /v is learned to obtain the final clustering results. We seamlessly integrate Eq. (1), Eq. (2), and (3) to get the final objective function as

where γ, β, and α are the control parameters. Qr ∈ Rdr ×k is the projection matrix for r-th veiw.

3.2 Optimization of FUMC

To solve Eq. (4), the auxiliary variable H is introduced to make Eq. (4) separable. Then, Eq. (4) is rewritten as the following augmented Lagrangian function

For the sake of easy optimization, Pr in the second term of the R∆P can be analytically solved. Therefore, we put it as constraint. Eq. (5) could be separately solved by developing an alternating iterative algorithm as follows.

• Step-1.1: Solving Sr with P, Q, W, Sb , and H fixed. Then, Sr -subproblem of Eq. (5) changes to

th column vector of ˆSr is defined as ˆsrj , whose i-th element is ˆ zr i,j . For the r-th view, letting ˆsrj and ˆ sri,j be the j-th column and ij-th element of ˆsr , respectively, updating sr converts to the following column form.

Following Theorem 1, Eq. (7) could be optimized. Theorem 1. [Li et al., 2023d] Given arbitrary v vectors { ˆ sj}vj=1 , we obtain the following closed-form solution s∗j

• Step-1.2: Solving Sb with P, Q, W, Sr , and H fixed. Then, Sb -subproblem of Eq. (5) changes to

where ˆSb = (Pb )⊺ (Qb )⊺Xb-0.5βDb+0.5µHb-0.5Yb (1+0.5µ)I and Db = L⊺G ∑vr=1 Wr Sr . Similar to optimize Sr , Eq. (9) could be solved via Theorem 1.

• Update-2: Solving Q with S, P, and W fixed. In this case, Q-subproblem of Eq. (5) can be written as

where Er = Xr (Sr )⊺ (Pr )⊺ . Eq. (10) can be solved via the SVD operator [Li et al., 2024; Li et al., 2023b] with complexity O(v ˆ d(nm + k2 + km)) for each iteration, where ˆ d = ∑vp=1 dp .

• Step-3-1 update Pr : Optimizing Pr with the irrelevant variables fixed is equivalent to the following optimization problem

where Cr = γ(Qr )⊺Xr (Sr )⊺ - βPbLG. The optimal solution of optimizing Pr can be effectively obtained via singular value decomposition (SVD) on Cr .

▶ Step-3-2 update Pb : Similar to optimize Pr , the optimal Pb is obtained by perform SVD on the Cb = γ(Qb )⊺Xb (Sb )⊺ - β ∑vr=1,r̸=b L⊺GPr . The complexity of optimizing P is O(v(ndk + nmk + m2k)) per iteration, where dall = ∑vr=1 dl .

• Step-4 update W: Fixing the irrelevant variables, and updating W as

where Br = µ2 (Hr -Yr )(Sr )⊺ -αL⊺GSb (Sr )⊺ . The optimal solution of optimizing Wr can be effectively obtained via singular value decomposition (SVD) on Br with complexity O(vd(nm+km+k2 )) per iteration.

• Step-5 update H: Ignoring the irrelevant items H, updating H subproblem is

Which can be solved into two steps as follows: (1) minimizing the core matrix, and (2) minimizing t-TNN. (1) Updating core matrix as

where regularization parameter λ = 1/(max(m, v)n) 12 . And the tensor Z is obtained from t-SVD on the temporary variable F, F = U ∗ Z ∗ V. (2) Updating H as

With the learned low-rank core matrix P(Z), we can use t-product to reconstruct a tensor as J = U ∗P(Z)-1 ∗ V. The learned J can further produce a closed-form solution [Li et al., 2023c; Li et al., 2023d].

Updating ADMM variables are written as

where µ = 1e-4 and µmax = 1010 , and the complexity is O(n). The whole optimization procedure of Eq. (5) is outlined in Algorithm 1, where convergence criterion is checked by computing the objective value obj t at the t-th iteration.

3.3 Complexity Analysis

Time complexity. In the optimizing Algorithm 1, Step-1, Step-2, Step-3, Step-4, Step-5, and ADMM variables costs O(v ˆ dnm), O(vd(nm+k2+km)), O(v(ndk+m2k+nmk)), O(vd(nm+km+k2 )), O (v2nm + vnm log(n)), and O(v) per iteration. After completing Algorithm 1, the final S∗

Algorithm 1 The algorithm of FUMC

Require: Unpaired multi-view data {Xr }vr=1, cluster number c, latent space dimension k, and parameters α, β, γ.

Initialize Qr = Ik, and the others matrices as 0.

• 1: repeat
• 2: Update Sr and Sb by using Eq. (6) and Eq. (9);
• 3: Update Qr , Pr , Pb ,Wr , andHvia Eqs (10)-(13);
• 4: Update ADMM variables via Eq. (16);
• 5: until convergence.
• 6: Obtain the left singular value matrix US∗ fromS∗ .

Ensure: Clustering performance

costs O(nm2 ) by performing SVD and the subsequent kmeans. Totally, the calculation complexity of our FUMC is O(t(v ˆ dnm+v ˆ d(nm+ k2 + km) + v(n ˆ dk +m2k + nmk) + v2nm+ vnmlog(n) + nm2 )). In our FUMC optimization, m ≪ n and k ≪ n. Thus, time complexity of optimizing FUMC is approximatively O(n).

Space complexity. The space consumption of our FUMC mainly comes from Qr ∈ Rdp×m, Xr ∈ Rn×dp , Pr ∈ Rm×k , Sr ∈ Rn×m, S ∈ Rm×n×v , and Y ∈ Rm×n×v . Therefore, the total space complexity of FUMC costs (n + k)m+3mnv+ ˆ d(n+m). Similar to time complexity, m ≪ n and k ≪ n deduce that Algorithm 1 inherits linear space complexity to sample numbers.

4 Experiments

4.1 Experimental Setting

Datasets. In the experiments, seven fully paired multi-view data are employed to compare with shallow methods, including ORL, BBCSport, MSRCv1, Mnist, YTF-10, YTF-20, and YTF-100 [Chen et al., 2022; Lin et al., 2022]. Four partially paired multi-view data with pair ratio (ϕ = 50%) to compare with deep methods, including Scene-15, Animal, LandUse21, and RGBD [Yang et al., 2023]. Their detailed statistical information is summarized in Table 1. We generate misaligned data by randomly shuffling sample arrangement of different views, where source codes are requested from author of [Lin et al., 2022] to ensure the fairness of experiments. The implementation of all competitors is collected from their public homepages or requested from authors. For shallow methods, our experiments are conducted on a 32GB RAM and Intel Core i7 CPU, 2021 Mac mini computing platform with Matlab 2021b, while deep methods are on PyTorch 1.8.1, and an NVIDIA 3090 GPU with Ubuntu 18.04.

To the best of our knowledge, a small amount of effort has been attempted to address arbitrary view-unpaired problem. On four common metrics [Wang et al., 2022; Wen et al., 2022; Kang et al., 2020], 14 shallow and 7 deep competitors are totally employed to evaluate the validity and efficiency of our FUMC to handle arbitrary view-unpaired data, i.e., fully unpaired and partially unpaired ones. Concretely, for shallow methods with fully unpaired data: Two unpaired multi-view clustering methods: T-UMC [Lin et al., 2022], MVC-UM [Yu et al., 2021]; And 12 paired methods : FSMSC [Chen et al., 2023c], FMVACC [Wang et al., 2022], OMSC[Chen et al., 2022], FPMVS [Wang et al., 2021] WTNNM [Gao et al., 2020] t-SVD-MSC [Xie et al., 2018], ETLMSC [Wu et al., 2019], LTMSC [Zhang et al., 2015], RMSC [Xia et al., 2014], LMSC [Zhang et al., 2020], AMGL [Nie et al., 2016], SC,[Ng et al., 2002]. For deep methods with partially unpaired data: Seven unpaired competitors includes: PVC [Huang et al., 2020], MVCLN [Yang et al., 2021], DSIMVC [Tang and Liu, 2022], MFLVC [Xu et al., 2022], CVCL[Chen et al., 2023a], DCP [Lin et al., 2023], SURE [Yang et al., 2023].

4.2 Experiment Results

The average clustering performance and standard deviations (Each experiment is repeated 20 times.) are reported on four fully unpaired datasets in Table 2 and Table 3. Further, Table 4 only compares four anchor based multi-view clustering methods on the paired and fully unpaired large-scale datasets since other shallow competitors suffer from n cube time and n square space complexities. The best and second-best averages are marked in bold and underlined, respectively. Fig. 4 reports learned consistent bipartite graphs from aligned and unaligned Synthetic datasets. According to reported tables and figures, we can observe that:

Effectiveness and superiority over shallow fully unpaired competitors. (1) Due to the carefully designed matching module, our FUMC and unpaired multi-view subspace clustering (T-UMC and MVC-UM) are superior to tensor based multi-view clustering (WTNNM, t-SVD-MSC, ETLMSC, and LTMSC), graph based multi-view clustering baselines (RMSC, LMSC, and AMGL), and single view SC by a large margin. Furthermore, compared to T-UMC and MVC-UM, our FUMC may contain less redundant information by learning the high-quality anchor features in the refined subspaces; Meanwhile, FUMC could also capture more compact high-order tensor low-rank structure by deeper exploring the low-rank core matrix of entries in core tensor than existing TNN. Thus, our FUMC consistently outperforms all these paired and unpaired clustering methods.

(2) Compared to shallow anchor based multi-view clustering (FSMSC, FMVACC, OMSC, FPMVS, and SMVSC), our FUMC significantly outperforms them when performing unpaired multi-view clustering. The main reason is that unpaired data destroys the cross-view consistency and complementary of paired data, which greatly reduces the quality of anchors and bipartite graphs. Especially in Table 4, these anchor based multi-view clustering methods obtain comparatively higher performance on the paired datasets. However, for unpaired datasets, their performance drops dramatically except for our FUMC, which is consistent with Fig. 4. Fig. 4 indicates that existing anchor based multi-view clustering methods are almost impossible to learn a consistent bipartite graph from unpaired multi-view data except our FUMC. Based on (1) and (2), effectiveness and superiority of FUMC are demonstrated.

Efficiency. Table 5 reports the time cost of three unpaired multi-view clustering methods, MVC-UM, T-UMC, and our FUMC. As can be seen, the time cost of our FUMC is far below than existing MVC-UM and T-UMC, demonstrating the efficiency of FUMC.

Effectiveness and superiority over deepmethods. (Most of them are partially paired methods) These partially paired deep methods must require partially paired data as the train data, so we set the paired ratio ϕ = 50% for four deep comparison datasets. From Table 6, our FUMC consistently outperforms all the competitors, which demonstrates the effectiveness and superiority of our FMUC.

4.3 Ablation Analysis

To demonstrate the significance and effectiveness of crossview graph matching term, we remove R∆P (Pb ,Pr ,G) and R∆S (Sb , Sr ,W,G) as Ablation1 and Ablation 2, respectively. Whether removing R∆P (Pb ,Pr ,G) or R∆S (Sb , Sr ,W,G), our model degrades largely as mentioned in Table 7. The main reasons are that R∆P (Pb ,Pr ,G) ensures the learned anchors satisfying the 1-5 properties, i.e., intra-view inter-cluster discriminative, intra-view intra-cluster compressible, intra-view maximally diverse, inter-view anchor number and order alignment. R∆S (Sb , Sr ,W, G) ensures the learned bipartite graphs to be rotated and matching the bipartite graph of the best view. Thus, both proposed R∆P (Pb ,Pr ,G) and R∆S (Sb , Sr ,W, G) are significant and effective.

4.4 Parameter Settings and Convergence

Algorithm 1 involves three parameters to be set properly, parameters α β, γ. Through this paper, only m = 2c anchors are learned and fixed for all datasets. The consensus dimension is also fixed as k = 2c. As shown in Fig. 3, our FUMC only

provides the parameter settings and convergence of YTF20∗ .

4.5 Conclusion

In this paper, we propose a novel FUMC framework to handle unpaired large-scale multi-view clustering. To our knowledge, FUMC presents the first study of addressing unpaired multi-view data through anchor learning. The carefully designed inverse local manifold learning and bipartite graph matching can respectively learn the powerful and aligned anchors and bipartite graphs from unpaired multi-view data. Comprehensive experiments and analysis have proved the superiority and efficiency of our method.

Acknowledgments

This work was supported by the National Natural Science Foundation of China (Grant No. 62372235), the A*STAR Career Development Fund (Grant No.C222812019), the Mianyang Science and Technology Program (Grant No. 2022ZYDF089), and the Base Strengthening Program of National Defense Science and Technology (Grant No. 2022-JCJQ-JJ-0292), the Postgraduate Research & Practice Innovation Program of Jiangsu Province (Grant No. KYCX23_0487), and the China Scholarship Council No. 202306840101.