Federated Multi-View Clustering via Tensor Factorization

1 Introduction

Multi-view clustering has been an effective unsupervised method to deal with multi-view data in recent years because it fully explores the complementary and consistent information between views. Existing multi-view clustering methods can be roughly classified into two categories [Fang et al., 2023b]: deep multi-view clustering [Liu et al., 2023; Yan et al., 2023; Xu et al., 2022] and heuristic multi-view clustering [Xing et al., 2023; Cai et al., 2023]. For example, [Xu et al., 2023] unties the entanglement between useful and meaningless information to learn disentangled and interpretable representations. [Chen et al., 2023] introduces federated learning to deep multi-view clustering to deal with security concerns by exploiting complementary cluster structures across clients and sharing non-sensitive information to avoid data leakage. Despite the outstanding performance of deep multi-view clustering, the high computation limits its realworld application. Therefore, heuristic multi-view clustering methods still show their application significance in practice. Among heuristic multi-view clustering methods, multi-view K-means methods have drawn considerable attention due to their low complexity and high efficiency [Yang and Sinaga, 2019]. However, most methods adopt centralized settings, while real-world multi-view data may well be collected and held by different clients who expect their data to be secret.

To address this issue, federated multi-view K-means were developed inspired by federated learning [Dong et al., 2022]. For example, [Huang et al., 2022] built a federated multiview clustering based on non-negative matrix factorization (NMF) and K-means; [Hu et al., 2023] proposed a federated multi-view fuzzy K-means with efficiency improvement. Nonetheless, they leveraged randomly initialized cluster centroids and thus suffered from unstable clustering performance. The intrinsic weaknesses of the underlying Kmeans greatly limit the practical performance of these federated multi-view clustering methods based on K-means. Although this issue has been widely discussed by existing works [Pei et al., 2022], it is nontrivial to apply them directly in federated scenarios due to the distributed properties and privacy preservation requirements.

To overcome these weaknesses, we propose a novel Federated Multi-View Clustering method via Tensor Factorization (TensorFMVC). The proposed method mitigates the sensitivity of K-means to centroid initialization by adopting centerless K-means. Besides, it employs an anchor-based affinity matrix rather than Euclidean distance, such that it effectively reduces the computational complexity and alleviates the weaknesses of traditional K-means that it cannot handle linearly non-separable data. Besides, inspired by tensorbased methods, we introduce the Schatten p-norm to extract the complementary information shared by all views. To validate the proposed method in federated scenarios, we develop a distributed optimization algorithm, enabling the model to be optimized collaboratively. Specifically, the main contributions of our work are summarized as follows:

• We propose a federated centerless multi-view K-means that can solve the initialization problem of traditional federated multi-view K-means. By replacing the Eu-

clidean distance with an anchor-based affinity graph, the proposed method can better handle linearly nonseparable data and well reduce the computational complexity;

• We build a three-order tensor by stacking the indicator matrix of each view and introduce a tensor Schatten pnorm based regularizer to explore the complementary information, which can be solved by tensor singular value decomposition (t-SVD);
• We develop an optimization algorithm to support that multiple clients could collaboratively train the proposed model without exchanging any private multi-view data;
• Extensive experiments and analyses with several methods are conducted on several multi-view datasets, and the experimental results indicate the effectiveness and superiority of our Tensor-FMVC.

2 RelatedWork

2.1 FederatedMulti-ViewK-means

Multi-view K-means clustering is widely used due to its low computational cost and easily parallelized process [Cai et al., 2013]. For example, [Huang et al., 2018] utilized the cappednorm loss as the objective in multi-view K-means clustering to remove the negative effect of the outliers. For a similar purpose, [Chen et al., 2020] considered both attribution outliers and class outliers and simultaneously performed clustering and outliers detection on the multi-view data to remove the negative influence of outliers. MVASM [Han et al., 2020] utilized consistency, independence, and complementary information between views by a common membership matrix with the proper sparseness. Federated multi-view clustering enables multiple clients to construct a global model with distributed multi-view data, which satisfies the requirements of data privacy preservation in the federal scenario [Feng and Yu, 2020]. [Huang et al., 2022] proposed an efficient multiview clustering model with NMF and K-means (FedMVL), which can handle the stragglers and fault tolerance. Similarly, [Hu et al., 2023] realized a federated multi-view fuzzy C-means (FedMVFCM).

2.2 Schatten p-Norm

Schatten p-norm is defined on the singular value of a matrix and helps to exploit the complementary information in multiview learning [Kong et al., 2018; Wang et al., 2023], which has been widely applied in multi-view clustering [Zhang et al., 2019]. [Li et al., 2023] introduced auto-weighted tensor Schatten p-norm to multi-view clustering and it can also automatically and appropriately shrink singular values to fully capture spatial structure in the graph tensor. [Zhao et al., 2022] employed the Schatten p-norm to minimize the divergence between graphs of different views to learn optimal clustering results, and an adaptive weighted strategy was adopted to adjust the contribution of each view. Similar work was also proposed in [Lu et al., 2023]. For easier presentation, we present the preliminaries of Schatten p-norm in this section [Liu et al., 2019].

Definition 1 (Tensor Singular Value Decomposition, t-SVD). Give a tensorM∈ Rn1×n2×n3 , then we have its t-SVD:

where U ∈ Rn1×n1×n3 , V ∈ Rn2×n2×n3 are both orthogonal tensors, and S ∈ Rn1×n2×n3 is diagonal tensor. Moreover, all frontal slices of S are diagonal matrixes, and the i-th singular value of k-th frontal slices of S is denoted as S k (i).

Definition 2. The tensor Schatten p-norm for tensor M is defined as below:

S k (i) is the i-th singular value of matrix S k . with 0 ≤ p ≤ 1, the tensor Schatten p-norm is better rank approximation than other norms.

Definition 3. For B ∈ Rn1×n2×n3 and C ∈ Rn1×n2×n3 , the function

has the optimal solution given by

where U and V are gotten from t-SVD of C, i.e. C = U ∗ S ∗ V T , and Dτ,p (C(m) ) = diag (ζ (C(m) )), where ζ (C(m) ) = GST (σ (S(m) , τ, p)). The GST algorithm is introduced in [Gao et al., 2020].

3 Method

3.1 Problem Statement

In a federated scenarios, there is a server S along with M clients, and the multi-view data is denoted as X = {X(1) ,X(2) , · · ·,X(M) }, where M is the number of views. The data distributed on client m is denoted as X(m) ∈ RN×d(m) (m = 1, 2, · · ·,M) where N is the sample number and d(m) is the feature dimension. The proposed method tries to leverage the local data of all clients to learn the cluster assignment in the federated scenarios.

3.2 ProposedMethod

Taking the m-th view as an example, the single-view Kmeans can be expressed as:

where A1,A2, · · ·,AC represent the C clusters and m(m) k = ∑xj∈AC xj nk is the centroid of Ak.

K-means requires an initialization of centroids, which greatly influences the clustering performance. We follow the work [Lu et al., 2023] to build a centerless K-means. Suppose D(m) is the distance matrix of the m-th view H(m) = [h(m) 1 , h(m) 2 , · · ·, h(m) N ]T ∈ RN×K is the indicator matrix, where h(m) ij = 1 indicates x(m) i ∈ Aj and h(m) i is a one-hot vector. Then, Eq. (5) can be simplified into:

To further simplify the problem, we assume that the number of samples in each cluster to be same. Thus, each cluster has n = NK samples. In other words, H(m) T H(m) = nI. The Eq. (6) becomes:min

By performing K-means on each view, we obtain the multiview K-means as follows:

Moreover, by introducing client weight to each client to measure its contribution to the global model, the objective function becomes:

Tensor-based regularizer: As H(m) is the indicator matrix of the data on m-th client, it may vary across different clients. Since one sample should be assigned to the same cluster in all clients regardless of data heterogeneity, the divergence between all H(m) should be minimized. Therefore, we introduce a regularizer based on the tensor Schatten pnorm to enforce the model to learn a complementary clustering result, and the objective function becomes:

where H ∈ RN×K×M is constructed by stacking all H(m) and λ is the trade-off parameter.

Construction of D(m) : Traditional K-means adopts the Euclidean distance to construct the distance matrix D(m) , which results in high computational complexity and cannot well process linearly non-separable data. Thus, we replace it with an anchor-based affinity matrix [Lu et al., 2023; Li et al., 2020b] and construct D(m) locally as follows: Firstly, we utilize directly alternate sampling(DAS) [Li et al., 2020b] to choose the anchors A(m) ∈ Rθ×d(m) effectively, and θ is the number of anchors.

Secondly, we use square Euclidean distance to measure the difference between samples and anchors. Specifically, according to the parameter-free and effective bipartite graph construct strategy [Li et al., 2020b], we obtain local anchor graph B(m) according to by solving :

where h (x(m) i , a(m) j ) is the square Euclidean distance of ith sample and j-th anchor of m-th view, and b(m) i is the ith row of B(m) . Moreover, the regularization parameter γ can be adaptively determined. The anchor points can well cover the entire samples, thus alternately sampling data points according to their feature representations that could reflect

some similarity relations over the clusters.

Thirdly, by introducing the Lagrangian function to the closed form of Eq. (11), we have:

where η and µ are the Lagrangian multipliers and p(m) ij = h (x(m) i , a(m) j ). According to KKT conditions, we have:

(13)

Fourthly, Supposing each sample is only connected to its k adaptive anchors and solving Eq. (13), we have µ = 1k + 1 2γk ∑kj=1 p(m) ij . Following [Li et al., 2020b], we set γ = k2 p(m) i,k+1 - 12 ∑kj=1 p(m) ij , and we can obtain b(m) ij by:

where (a)+ = max(0, a).

Fifthly, the symmetric and doubly-stochastic adjacency matrixW(m) is obtained according to [Liu et al., 2010]:

where ∆(m) jj = ∑Ni=1 b(m) ij and it is a diagonal matrix.

Finally, based on W(m) , we obtained the adjacency matrix D(m) by:

where Ω is a hyperparameter. By leveraging the adjacency matrix instead of the Euclidean distance matrix, our method can well handle linearly non-separatable data and can also reduce the computational complexity [Lu et al., 2023; Li et al., 2020b].

3.3 Optimization Algorithm

In federated scenarios, considering data security, D(m) obtained from local data X(m) cannot be transmitted to the server or other clients. However, H(m) , which indicates the cluster assignment based on local data, does not cause data leakage. Therefore, it can be transmitted between the server and the client. Based on the above constraints, we propose the following optimization algorithm. Firstly, we introduce augmented Lagrange multiplier(ALM) to Eq. (10):

where Q is the Lagrange multiplier and µ is the penalty parameter. Through observation of Eq. (17), we can find that:

• There are three variables that need to be optimized, namely α(m) , H, and G.
• α(m) can be updated locally on Cm because it is only related to the local variables H(m) and D(m) ;
• The update of H seems to involve all the data. To allow updating it locally, we decompose it intoM independent subproblems that are only related to local variables α(m) and variables G and Q transmitted from the server.
• The update of G involves t-SVD operation, and thus it needs to be performed globally. Moreover, the update of G relates toQ andH.

The federated training of the three variables requires several communication rounds between clients and the server. The data that needs to be transmitted include:(1) each client transmits its updated H(m) to the server, and (2) the server transmits Q(m) and G(m) to the m-th client after Q and G are updated. The detailed optimization algorithm is described as follows.

(1)Solving α(m) with fixedHand G by Cm: WhenHand G are fixed, we only need to focus on the first term:

By introducing the Lagrange multiplier to Eq. (18), we get:

where γ and θm are hyperparameters. According to KKT conditions, we have the following equations satisfied for all

m= 1, 2, · · ·,M:

where ∂L ∂α(m) = rα(m) r-1Tr (H(m) T D(m)H(m)) -γ-θm. By solving this, we can get the optimization function of α(m) :

(2)Solving H with fixed α(m) and G by S: With fixed α(m) and G, the objective function w.r.t H becomes:

Eq. (22) can be changed into:

Apparently, the first term is only related to H(m) which is the cluster assignment on m-th client, and the second term involves H(m) of all the clients. Considering the independence of H, G, and Q, we decompose Eq. (23) into M independent subproblems, where the m-th subproblem is defined as below:

Furthermore, we can decompose Eq. (24) into N subproblems at the sample level because of the independence of all rows of H(m) .

Regarding the first item of Eq. (24), we have:

When solving the h(m) t , fix all h(m) i (i ̸= t), and considering the duality of i and j and d(m) ii = 0, then the function becomes:

Then, regarding the second term of Eq. (24) , we have:

Similarly to solving the first term, we can obtain:

where G(m) = [g(m) 1 , g(m) 2 , · · ·, g(m) n ]T , Q(m) = [q(m) 1 , q(m) 2 , · · ·, q(m) n ]T . With the above analyses, we have:

where Z(m) t = G(m) - Q(m) µ = [z(m) 1 , z(m) 2 , · · ·, z(m) n ]T . As h(m) t is a one-hot vector, the optimization of Eq. (29) is:

(3)Solving G with fixed α(m) andH: With fixed α(m) and H, the objective function w.r.t G becomes:

where P = H - Qµ . From Definition 4, we can get the optimal solution of Eq. (31):

where U and V are acquired via t-SVD of P, i.e., P = U ∗ S ∗ V T .

Algorithm 1 TensorFMVC

Input: The data X = {X(1) ,X(2) , ...,X(M) } on M local clients, pre-constructed D(m) , cluster number C;

Parameter: µ, p, λ, r, Ω;

Output: Cluster assignment H

• 1: InitializeH(m) with randomone-hot vector andα(m)= 1M for all client. Initialize Q and G to be all zero.
• 2: while not converged do
• 3: for m = 1 to M do
• 4: ▷ on m-th client Cm
• 5: Update weight α(m) according to Eq. (21)
• 6: Update H(m) according to Eq. (30)
• 7: Send H(m) and α(m) to the global server
• 8: Compute Tr (H(m) T D(m)H(m)) 1 1-r and send it to the global server
• 9: end for

10:

▷ on Server S

• 11: Stack all H(m) to construct tensor H
• 12: Update G with newHaccording to Eq. (32)
• 13: Update Q according toQ←-Q+µ(H-G)
• 14: Send H(m) , G(m) , and Q(m) to Cm
• 15: Compute ∑Mm=1 Tr (H(m) T D(m)H(m)) 1 1-r and send it to all clients
• 16: end while
• 17: S aggregates H(m) into Hwith Eq. (33)
• 18: returnH

Workflow: We depict the workflow in Fig. 1 and summarize it in Alg. 1 to illustrate how parameters are optimized collaboratively. Firstly, each client Cm conducts initialization by setting H(m) with random one-hot vectors and α(m) with 1M , and Q and G as zero tensors. After initialization, Cm updates H(m)with Eq. (30), and computes Tr (H(m) T D(m)H(m)) 1 1-r , then sends them and α(m) to the global server S. The server S, after receiving all the parameters, stacks all the H(m) into a tensor H, and then update G with Eq. (32) and Qwith Q+µ(H-G). Subsequently, S will also compute ∑Mm=1 Tr (H(m) T D(m)H(m)) 1 1-r and send it together with updated Q and G to all the clients, with which the client Cm could update α(m) with Eq. (21). The above process (except the initialization) repeats until convergence. Finally, the server S aggregates the latest H(m) into the final clustering indicator matrix H:

Complexity Analysis: We evaluate computational complexity: For client Cm, the complexity of pre-constructing D(m) and model update is O (MNθd(m) +MNθlog(θ)) and O(NC). For the server S, the complexity of aggregation is O (MNClog(MN) +M 2NC ). Both of them are linear to N indicating its low computational complexity.

4 Experiment

4.1 Experiment Settings

We validate our method on eight multi-view datasets and compare it with seven multi-view clustering methods and one federated multi-view clustering method. For the federating scenario, our experiment includes a server and multiple clients, and each client holds the data with one view.

Datasets: We evaluate our method on eight public multiview datasets: (1)3-sources is a three-view text dataset with 169 samples sourced from three reputable news outlets. (2)BBCSport [Greene and Cunningham, 2006] is composed of 544 sports news articles sourced from the BBC Sport website and is categorized into five distinct topical areas. It has two views and the dimensions are 3283 and 3183. (3)ORL [Samaria and Harter, 1994] is a three-view dataset of 400 facial images, categorized into 40 classes. (4)Sonar [Sejnowski and Gorman, ] includes three views and extracts its multi-view features from 208 patterns. (5)Yale is a two-view dataset of 165 facial images of 11 people. (6)Vehicle Sensor((VS) [Duarte and Hu, 2004] is a four-view dataset whose features are gathered from distributed sensors. (7)Human Activity Recognition(HAR) [Reyes-Ortiz and Parra, 2012] is a four-view dataset with 10299 samples that documents six daily activities performed; (8)SentencesNYU v2(RGBD) [Silberman et al., 2012] includes images of indoor scenes and corresponding descriptions. We process the dataset following the method in [Trosten et al., 2021].

Compared methods: We compared our methods with seven multi-view clustering methods: (1)DiMSC [Cao et al., 2015];(2)MvLRSSC [Brbi´c and Kopriva, 2018];(3)RMSL [Li et al., 2019];(4)GMC [Wang et al., 2019];(5)MvDGNMF [Li et al., 2020a];(6)UDBGL[Fang et al., 2023a];(7)FastMICE[Huang et al., 2023]; and one federated method (8)FedMVL [Huang et al., 2022];

4.2 Experiment Results

The experimental results are illustrated in Table 1 and Table 2. The best results are in bold, and the second best results are underlined. We can reach the following conclusions: (1) Our method shows superiority to the compared federated method(i.e., FedMVL). Compared with the FedMVL on the ORL dataset, the proposed method is 48.00%, 32.93%, and 44.75% higher on ACC, NMI, and PUR, demonstrating TensorFMVC effectively overcomes the weaknesses of existing federated multi-view clustering methods. (2) TensorFMVC achieves the best performance even when compared with centralized methods. For example, compared with the bestperformance centralized method on ORL, TensorFMVC is 16.75%, 6.61%, and 12.00% higher on ACC, NMI, and PUR. This may be because the tensor Schatten p-norm explores the complementary information between various views.

Convergence analysis: Fig. 2 shows the convergence curves of ACC and the values of the objective function. It shows that within limited iterations, both the ACC and Eq.

(10) reach the convergence state rapidly. The convergence curve can be divided into three parts. In the first stage, the value of the objective function decreases rapidly and ACC increases rapidly. In the second stage, the value of the objective function decreases relatively slowly while the accuracy rate increases slowly as well. Eventually, the two tend to converge. Moreover, the proposed method possesses a stable convergence because the objective function values can reach a stable value within 50 iterations on the four datasets.

Parameter analysis: There are three parameters in Eq. (10), i.e., λ, p, and r, and one parameter Ω in Eq. (16). We study the influence of their values on the clustering performance, whose results are illustrated in Fig. 3. We conclude that: (1) TensorFMVC achieves relatively poor performance when the λ is too small or too large, and the probable reason is that λ adjusts the contribution of the tensor Schatten p-norm. Thus, a small λ makes the model unable to learn the global cluster assignment correctly, while a big value results in ignoring the complementary information of different values. The suggested range for λ is [10, 100]. (2) A larger r represents the smaller difference in client contributions to the global model. The ACC curve w.r.t. r indicates that an appropriate increase in r helps to improve the clustering accuracy. Thus, the suggested range of r is 5 to 7. (3) p's value greatly influences the ACC, because when 0 ≤ p ≤ 1, the tensor Schatten p-norm helps to obtain a better approximation than other norms. It achieves the best performance when p = 0.9 because it learns the spatial structure from all clients. (4) The ACC curve w.r.t. Ω illustrates that the clustering performance deteriorates when Ω is too large or too small. Hence, the recommended value of Ω is 0.01.

Figure 3: Parameter analysis on 3-sources, RGB-D, and Sonar.

Ablation Study: We have conducted ablation experiments in three cases: (1) TensorFMVC without tensor-based regularizer(case 1);(2) TensorFMVC without anchor-based affinity graph(case 2)(By using Euclidean distance instead); (3) TensorFMVC without tensor-based regularizer and anchorbased affinity graph(case 3) and the results are shown in Table. 3. Results indicate TensorFMVC achieves better performance compared with all three cases, showing the significant contribution of each component.

5 Conclusion

This paper presents a novel federated multi-view clustering method with tensor factorization named TensorFMVC. It effectively addresses the sensitivity of K-means to centroid initialization through centerless K-means. Additionally, it employs an anchor-based affinity matrix instead of Euclidean distance to reduce complexity and improve efficiency. Inspired by tensor-based methods, we introduce the Schatten pnorm to extract the complementary information shared across all views. To validate the proposed method in federated scenarios, we develop a distributed optimization algorithm, enabling the model to be optimized collaboratively. Experimental results demonstrate the efficacy of TensorFMVC and its superiority to state-of-the-art methods.

Acknowledgements

This research was partially supported by the National Key Research and Development Project of China No.2021ZD011070, National Science Foundation of China under Grant No. 62102306, the Natural Science Basic Research Program of Shaanxi Province under Grant No. 2023-JC-YB-534, the Science and Technology project of Xian under Grant No. 2022JH-JSYF-0009, Initiative Postdocs Supporting Program under Grant No. BX20190262.