Efficient Federated Multi-View Clustering with Integrated Matrix Factorization and K-Means

1 Introduction

Multi-view data [Wang et al., 2023] can provide a comprehensive description of an object from different perspectives, such as modalities and features, where each view provides consistent and complementary information [Xu et al., 2013]. For instance, human activities can be captured through cameras, video recorders, and textual descriptions. Due to the high expense of reliable label acquisition, multi-view clustering has emerged as a popular unsupervised learning method within the field of multi-view learning [Sun et al., 2020]. Existing multi-view clustering methods can be roughly divided into five categories [Yang and Wang, 2018]: Co-training style algorithms [Jiang et al., 2013], Multi-view graph clustering [Huang et al., 2019; Wen et al., 2020], Multi-kernel learning [Tzortzis and Likas, 2012], Multi-view subspace clustering [Zheng et al., 2023], and Multi-task multi-view clustering [Al-Stouhi and Reddy, 2014].

∗Corresponding Author

Although multi-view clustering methods have exhibited promising performance, they are mainly designed for centralized scenarios where multi-view data is located in a single party. In reality, however, multi-view data is often collected and maintained by different entities [Chen et al., 2023; Huang et al., 2020; Feng and Yu, 2020]. Due to data privacy concerns, these data holders are generally unwilling to share their data with others directly. To address this challenge, federated learning was introduced, enabling collaborative training of multi-view clustering models without the need for direct data sharing [McMahan et al., 2017]. For example, [Chen et al., 2023] proposed a federated deep multiview clustering method with global self-supervision, which has demonstrated remarkable clustering performance. [Ren et al., 2024] both consider unaligned and incomplete data in federated multi-view clustering.

The utilization of deep federated models incurs significant computation and communication costs, rendering them unsuitable for scenarios that show a requirement for efficiency. Consequently, several heuristic federated multiview clustering methods have been developed based on nonnegative matrix factorization (NMF) [Huang et al., 2022] and K-means. Owing to their simplicity and efficiency, these methods can better satisfy the efficiency requirements in computation/communication-sensitive applications. Nonetheless, it is widely recognized that both NMF and Kmeans are unable to process linearly inseparable data and retain the local geometric structure of the original data. For another, existing heuristic federated multi-view clustering performs feature extraction and clustering in two separate procedures [Huang et al., 2022; Hu et al., 2023], and hence, the clustering results cannot guide the extraction process. These limitations lead to the potential risk of performance degradation and greatly restrict their application.

To overcome these weaknesses, we develop an efficient Federated Multi-View Clustering with Integrated Matrix Factorization and K-Means (FMVC-IMK). It integrates KMeans into Federated NMF, enabling itself to enhance the performance of each other for superior clustering results.

Besides, considering the heterogeneity of distributed data, we introduce an adaptive update weight that can be locally computed to quantify each client's contribution to the global model. To improve the performance on linearly inseparable multi-view data, a graph-based regularizer is introduced to retain the local geometric structure information. Finally, we design a federated optimization algorithm to optimize the model without sharing any original multi-view data. To summarize, the main contributions of the work are as follows:

• We propose a novel FMVC-IMK for federated multiview clustering. It performs federated multi-view NMF and K-means in an integrated step by approximating the coefficient matrix of NMF with the indicator matrix and centroid matrix of K-means. Therefore, it can learn a better clustering structure from multi-view data located in different clients.
• To retain the geometric structure in the original data, we introduce a graph-based regularizer to constrain the learned indicator to be consistent with the original data, which helps enhance the clustering performance, particularly for data that exhibit non-linear separability
• We develop an optimization algorithm with adaptive weights to cooperatively optimize the objective function among the server and multiple clients. The adaptive weights dynamically adjust the contribution of each client's locally trained model to the global model.
• We conduct extensive experiments on eight multi-view datasets and compare FMVC-IMK with several methods. The experimental results demonstrate the effectiveness and superiority of our method.

2 RelatedWork

2.1 Heuristic Multi-ViewClustering

Heuristic multi-view clustering [Huang et al., 2021] shows higher computational efficiency and demonstrates its significance in many computation-sensitive applications. NMF becomes an effective method to build multi-view clustering methods because they could well exploit the information of different views. For example, [Liu et al., 2013] formulated a multi-view clustering method via joint NMF to learn a common consensus; ONMF is an variant of NMF with orthogonal constraints and [Liang et al., 2020] applied co-orthogonal constraints on representation matrices and basis matrices to further capture the diversity within views and learn the appropriate basis matrices.

Apart from NMF, K-means is another popular method to build multi-view clustering [Cai et al., 2013]. To handle linearly inseparable data, [Gao et al., 2019b] introduced a multi-manifold regularizer to learn the hypergraph weights. Similarly, [Zhu et al., 2020] imposed the constraints on highlevel manifold consensus, aiming to capture deeper underlying structures of the data. Besides, [Zheng et al., 2023] proposed a novel one-pass method, which achieves better clustering performance than traditional NMF-based methods. However, all the methods mentioned above are designed for centralized applications and cannot be directly utilized in federated scenarios.

2.2 FederatedMulti-ViewClustering

Federated learning, as a distributed machine learning paradigm, aims to train models on multiple local clients without transferring raw data or other sensitive data, which can be roughly categorized into horizontal federated learning (HFL) [Gao et al., 2019a; Zhao et al., 2021], Vertical federated learning (VFL) [Sun et al., 2021; Liu et al., 2020], and Federated Transfer Learning (FTL) [Kevin et al., 2021; Yang et al., 2020]. The federated learning is quickly extended to federated multi-view learning [Che et al., 2022]. In terms of federated multi-view clustering, [Chen et al., 2023] developed federated deep multi-view clustering with global selfsupervision. Effective as it is, the deep model it adopts is computationally expensive and thereby cannot satisfy the efficiency requirements in some scenarios. Differently, [Huang et al., 2022] built a federated multi-view clustering method via NMF and K-means that helps reduce the computational cost. [Hu et al., 2023] realized a federated multi-view fuzzy C-means (FedMVFCM). Nevertheless, these methods still confront the intrinsic weaknesses of NMF and K-means.

3 Method

3.1 Problem Statement

Suppose X = {X(1) ,X(2) , · · ·,X(M) } denotes the multiview data, where M is the number of views and X(m) ∈ RN×d(m) (m = 1, 2, ...,M) is the data matrix of the m-th view; N is the number of samples and d(m) represents the feature dimension. Suppose that in a federated setting, there exists a centralized server S and M local clients, with each client Cm holding the data X(m) . Our design goal is to collaboratively learn a clustering model while considering the privacy of client data.

3.2 Objective Function

Given the X(m) of the m-th view, we can factorize it into two matrices with lower dimensions via ONMF:

where G(m) ∈ RN×c and F(m) ∈ Rc×d(m) are the coefficient matrix and the basis matrix of the m-th device, respectively. Considering the m-view data held by the m-th local clients, we have the following objective function for Federated multiview clustering:

Since it has been proved that K-means is a matrix factorization problem [Bauckhage, 2015], by performing K-means on the coefficient matrix G(m) , we have:

where H(m) ∈ RN×k is the indicator matrix, of which the i-th row H(m) i is a one-hot vector and H(m) i,j = 1 indicates that it assigns i-th sample of the m-view to the j-th cluster. By integrating (1) and (3), we have:

Similar to [Huang et al., 2022], we remove the nonnegative constraint of F(m) to expand the application scope because the input data is also not constrained to be nonnegative. We set an adaptive updating weight α(m) (m = 1, 2, · · ·,M) for each local client based on their contribution to the global model to adjust the impact of each view on the clustering performance:

It should be noted that H(m) i is a discrete one-hot vector and thus difficult to optimize. Therefore, we introduce a regularization term ||H(m) T H(m) - I||2F to obtain a relaxed solution. For another, since we aim to learn a global clustering structure from multi-view data, we introduce a global indicator matrix H and constrain it with H(1) = H(2) = · · · = H(M) = H to enforce the model to learn a consistent clustering structure:

Graph-Based Regularization: NMF-based methods usually cannot handle data that are not linearly separated. To address this issue, we employ a graph-based regularization term to retain the local geometric structure, such that similar samples should be assigned to the same clusters:

where S(m) is the similarity matrix of the m-th view and can be locally calculated by m-th client as follows:

where N (m) p,i represents the p-nearest neighbors of x(m) i in the m-th view. It has been proved in [Yang et al., 2022] that (7) is equal to:

where L(m) = D(m) - S(m) is the Laplacian matrix; D(m) is a diagonal matrix and D(m) ii = ∑Nj=1 S(m) ij .

Introducing the above two regularization terms into (5), we get the final objective function:

where µ and λ are penalty parameters.

3.3 Adaptive Update of α(m)

As aforementioned, we leverage α(m) to adjust the influence of each client for better performance, which incurs a problem of how to decide the value of α(m) . By observing (10), we find that updating α(m) is only related to the first term, i.e., (5). According to Theorem 1, the weight of each device can be determined automatically.

Theorem 1. If the weight of each client is fixed, solving the problem (5) is equivalent to solving the following problem

Proof. Taking Γ and Λ as the Lagrange multiplier and the proxy for the constraint to F(m) , respectively, the Lagrange function is as follows:

We then take the partial derivative of (12) with respect to (w.r.t.) F(m) :

Introducing Γ and Λ to (5), we get the Lagrange function:

Similarly, taking the partial derivative of (14) w.r.t. F(m) :

If we fix all the weight α(m) to the same, (5) is equivalent to (11). So the corresponding partial derivatives (13) and (15) should be equal. By solving this equation, we have:

Thus, α(m) adaptively updates according to (16).

3.4 Optimization Algorithm

(10) can be easily optimized in centralized scenarios, but it becomes challenging in federated settings because data with different views is held by different clients. Therefore, we develop a collaborative optimization algorithm to learn the optimal solution of (10). We first obtain the following observations from (10):

• There are four parameters to be optimized: H(m) , W(m) , F(m) , and H;
• The update of Hmust be conducted centrally because it is only related to parameter H(m) and does not involve local data on the client;
• F(m) , W(m) , and α(m) can be updated locally on each client because it is related to local private data;
• The update of H(m) is related to centralized parameters H, local parameters F(m) and H(m) , and most importantly, it is related to local private data X(m) , its update can only be performed locally. Therefore, it is the only parameter that needs to be transferred between each local client and the centralized server. Moreover, since H(m) is the cluster assignment of samples on each client, it will not result in any data leakage, which fulfills the privacy requirements of federated learning.

Based on the observations, the federated optimization algorithm is as follows:

(1) SolvingHwith fixedH(m) ,W(m) , F(m) by S: In this case, solving H in function (10) is equivalent to solving the following objective with a fixed H(m) :

To solve (17), we introduce a new term in the function derived from the constraint and Augmented Lagrangian function of (17) concerning H:

where Φ(m) is the Lagrangian multiplier of client Cm, ρ is the penalty parameter, and ⟨·, ·⟩ is the inner product operation. We take the partial derivative of LH w.r.t. H and set it to 0, we have:

By solving (19), we can get

where

Clearly, the optimization of H can be performed centrally with H(m) from all clients.

(2) Solving F(m) with fixed H(m) , W(m) , and H by Cm: Because the second term of (10) is independent of F(m) , we only focus on the first term and the function becomes:

By taking its partial derivative w.r.t. F(m) and set it to 0:

By simple algebra, we obtain its solution as follows:

1. Solving W(m) with fixed H(m) and F(m) , H by Cm: Similar to F(m) , by taking partial derivatives w.r.t. W(m) and setting it to 0, we can obtain the solution of W(m) :

(4) Solving H(m) with fixed F(m) , W(m) , and H by Cm: To solve H(m) , we follow the work [Smith et al., 2018] and similar to the update of H, we introduce a new term transformed from the constraint and Augmented Lagrangian function of (10) w.r.t. H(m) , then we get:

If we have ∆H(m) , then H(m) ←- H(m) +∆H(m) .The problem is changed to solving ∆H(m) on Cm. We define the m-th sub-problem on m-th client to solve ∆H(m) :

where

By solving the above sub-problem locally according to [Smith et al., 2018], we can update H(m) on m-th client locally by H(m) ←- H(m) +β∆H(m) as long as the m-th client has parameter H.

3.5 Communication Rounds

As shown in Fig. 1, FMVC-IMK requires transmitting some parameters to support collaborative and privacy-preserving

Algorithm 1 FMVC-IMK

Input: The data X = {X(1) ,X(2) , ...,X(M) } in M local clients; the number of cluster k; Penalty parameter µ, λ, ρ, θ Output: Global cluster result H

• 1: Each client Cm initializes W(m) , F(m) , H(m) , and

α(m)= 1M ; 2: S aggregates L(m) into ∑Mm=1 L(m) via PHE; 3: while not converged do 4: for m = 1 to M do 5: ▷ on m-th client Cm 6: Update F(m) according to (24) 7: UpdateW(m) according to (25) 8: Get ∆H(m) by solving (27), and update H(m) by H(m) ←- H(m) + β∆H(m) 9: Update α(m) according to (16) 10: Send H(m) to S 11: end for 12: ▷ on the Server S 13: Update H according to (20) 14: Resend H to all clients 15: end while 16: returnH

model training. To better illustrate how FMVC-IMK works, we herein provide a brief introduction to its workflow.

In the initialization stage, each client Cm locally computes the similarity matrix S(m) and generates the Laplacian matrix L(m) . Then, C(m) transmits L(m) to server S, which aggregates all the L(m) to obtain ∑Mm=1 L(m) . Considering that L(m) may reveal local data distribution of Cm, we adopt partially homomorphic encryption(PHE) to ensure that S can only obtain the aggregated result rather than the concrete L(m) . Since PHE achieves better efficiency and this process is only executed once at the beginning, it will not introduce much computation and communication overhead.

In the optimization stage, Cm locally updates F(m) and W(m) with (24) and (25), respectively. Then, Cm gets the ∆H(m) and updated α(m) with (27) and(16) and updated H(m) ←- H(m) + β∆H(m) . The updated H(m) is transmitted to S, who subsequently leverage (20) to update H with all the H(m) collected. This process repeats until the model converges. Finally, we summarize the workflow in Alg. 1.

3.6 Complexity Analysis

The computational cost of our method consists of two parts: the client side and the global server side. Suppose N, E, C, and d(m) denote the sample number, iteration number, cluster number, and data dimension of m-th view, and assume C ≪ N and C ≪ d(m) .

For client Cm, the complexity of initialization, Laplacian matrix construction, and model update is O (d(m) +N ), O (N 2 ), and O (N 2d(m)E);

For the global server S, the complexity of model aggregation process is O (N 2E).

4 Experiment

4.1 Experiment Settings

We compare our method with eight multi-view clustering methods on eight multi-view datasets. For the federating settings, 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 sourced from three reputable news outlets: BBC, Reuters, and the Guardian with 169 samples. (2)BBCSport [Greene and Cunningham, 2006] is a two-view dataset consisting of 544 samples of five categories sourced from BBC Sport; (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 multiview features from 208 patterns(samples). Then the 60 features are divided into three views equally. (5)Yale is a twoview dataset of 165 facial images of 11 people. (6)Vehicle Sensor [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; (8)SentencesNYU v2(RGB-D) [Silberman et al., 2012] includes images and descriptionsof indoor scenes . We process this dataset following [Trosten et al., 2021].

Compared Methods: We compared FMVC-IMK with: (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., 2020];(6)UDBGL[Fang et al., 2023];(7)FastMICE[Huang et al., 2023] (8)FedMVL [Huang et al., 2022].(1)-(7) are centralized methods, and (8) is federated method.

4.2 Experiment Results and Analysis

Table 1 and Table 2 illustrate the experimental results, from which we can observe that our method achieves better clustering than FedMVL because FMVC-IMK integrates NMF and K-means into a single step and leverages a graph-based regularizer to retain geometric structure information of the original data. Even compared with centralized multi-view clustering methods, our method shows comparative performance and achieves the best performance on most datasets. Especially, on the Sonar dataset, FMVC-IMK obtains 74.52% ACC, 18.03% NMI, and 74.52% PUR, achieving 9.62%, 9.32%, and 9.62% higher than the sub-optimal method. This demonstrates the superiority of FMVC-IMK.

Convergence analysis: We record the value of the objective function at each iteration on four datasets to verify the convergence property, as shown in Fig. 2. It can be seen that the objective value decreases rapidly and converges within 100 iterations on all four datasets. ACC increases rapidly, but the whole process fluctuates. The reason is that the global cluster assignment is obtained by aggregating all local cluster assignments in each iteration, which inevitably affects ACC. Nevertheless, ACC still converges within 100 iterations.

Parameter Analysis: (10) indicates that our objective function involves two hyperparameters: λ and µ, and Fig.3 depicts the ACC when λ and µ take values on the interval of [0.0001, 0.001, 0.01, 0.1, 1, 10] on four datasets. We can observe that: (1) When λ is too small, the accuracy is low because the local geometric structure is not well retained. However, when λ is too large, the accuracy is low due to the excessive influence of the local geometric structure; (2) Smaller µ reduces accuracy because it hinders learning a consistent cluster assignment, but bigger µ also reduces accuracy because local data heterogeneity is ignored. Proper values of λ and µ help improve the cluster performance of FMVC-IMK.

Ablation Experiments : We conduct the ablation studies and summarize them in Table 3. We test the performance of FMVC-IMK in three cases: (1)two-step FMVC-IMK without Graph Regularizer(case 1); (2)FMVC-IMK without Graph Regularizer(case 2); (3)the complete FMVC-IMK (case 3). From Table 3, the ACC, NMI, and PUR on BBCSport in case 2 outperforms that in case 1 by 26.29%, 31.58%, and 17.34%, which means that integrating NMF and K-means effectively improves the clustering performance. Besides, on the same dataset, the three metrics in case 3 are increased by 4.74%, 3.98%, and 3.55% when compared with case 2, indicating the graph regularizer helps to improve the clustering performance by enforcing the clustering to be consistent with the original data.

5 Conclusion

The paper presents a novel federated multi-view clustering method named FMVC-IMK to solve the multi-view clustering problem in the federated setting. By integrating matrix factorization and K-means clustering into a single step and introducing graph-based regularization, FMVC-IMK enhances clustering performance and preserves data privacy simultaneously. Additionally, we introduce an adaptive weight for all clients and establish the update strategy. Furthermore, we design a collaborative optimization algorithm to facilitate the application of our method in federated scenarios. Extensive experiments demonstrate the superiority of FMVC-IMK.

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, Shaanxi Continuing Higher Education Teaching Reform Research Project No. 21XJZ014, 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-JSYF0009, Initiative Postdocs Supporting Program under Grant No. BX20190262.