Fair and Efficient Contribution Valuation for Vertical Federated Learning

We sincerely appreciate your positive comments and valuable feedback on our paper. Following your feedback, we have made significant efforts to conduct comparison experiments. We are confident that these efforts have greatly enhanced the quality and strength of our paper. In light of this enhancement to the paper, we kindly hope that you could consider re-evaluating your score. We are confident that our work now better addresses your concerns, and we hope that the updates better reflect the contribution we aim to make to the field. We reply to each of the weaknesses and questions below.

Reply to Weakness 1

Thank you for your valuable feedback. We extend the experiments to compare with alternatives including request embeddings for all data points and based on update mini-batch.

We first define a deviation metric for the upcoming comparison experiments. For client $i$, denote its percentage of VerFedSV relative to the total VerFedSV from all clients as $s_i$. These VerFedSVs are calculated using matrix completion to estimate all embeddings. Meanwhile, we compute a ground-truth scenario where full embeddings are calculated in each training round. In this scenario, the percentage of Shapley value for client i relative to the sum of all Shapley values is denoted as $s_i^{gt}$. With $M$ representing the number of clients, the metric Deviation(VerFedSV, Ground truth) is defined as $\frac{1}{M} \sum_{m=1}^{M} \frac{|s_m - s^{gt}_m|}{s^{gt}_m}$. Similarly, the metric Deviation(Mini-batch, Ground truth) measures the deviation of Shapley value computed with mini-batch from the ground-truth scenario.

The comparison results are shown as follows. The deviation metric is shown in mean$\pm$std format, where mean and std are calculated from 5 independent runs.

To conclude, VerFedSV stably achieves low deviation since it can accurately recover the full embeddings. In contrast, the Shapley values under the Mini-batch scenario exhibit a larger variance than VerFedSV.

Preparing a separate validation set under the VFL scenario is a non-trivial research topic. In the VFL scenario, the server should not possess any knowledge about the client dataset, including even the feature dimensions. The server and clients have to collaborate prudently and complicatedly to prepare and utilize the validation set while properly addressing the privacy issue. Considering this challenge, we propose using the full training set directly. This approach offers several advantages. Firstly, it utilizes the entire training set for computing Shapley value, thereby avoiding potential errors introduced by sampling mini-batches. Additionally, it ensures that the computation process of the Shapley value does not leak private information and that the resulting Shapley value remains private to each client.

For baselines, we would like to draw the reviewer's attention to SHAP [1] baseline in Section D.2. This experiment shows that VerFedSV reflects the importance of clients’ local features. However, to the best of our knowledge, no other suitable baseline exists that considers both privacy and fairness simultaneously. Actually, the SHAP baseline cannot be directly applied to the VFL task, as it requires access to all the local datasets and may breach privacy. Meanwhile, the baselines involving the model-independent utility would cause fairness issue in the asynchronous VFL scenario, since they rely on the client's data but ignores the computational resources contributed by the client. To explain this, we have an example in Sec. 7.2. Imagine two clients with identical datasets. Using the model-independent utility function, both clients would be evaluated as having equal contributions. However, in an asynchronous environment, Client 1 may have superior hardware and transmission power. This advantage allows for a larger batch size and facilitates more frequent communication, resulting in a higher number of asynchronous training rounds. In such a scenario, Client 1's contribution should be greater, yet the model-independent utility function fails to recognize this, leading to an unfair assessment.

[2] Scott M. Lundberg, Su-In Lee. A Unified Approach to Interpreting Model Predictions. NeurIPS 2017: 4765-4774

Reply to Weakness 2

Thank you for your feedback regarding the technical novelty of our learning-based basis selection approach. We understand your concerns and appreciate the opportunity to emphasize our contributions:

• We addressed an important problem rarely explored in the literature, that is, how to fairly value the contributions of different clients in the field of vertical federated learning (VFL).
• Our proposed VerFedSV utilized the local embedding to construct the utility function. We have indeed employed techniques developed by pioneers in related fields (like local embeddings), but our work combines these techniques and applies them in a novel context.
• VerFedSV is applicable for both synchronous and asynchronous VFL. In synchronous VFL, we utilize matrix completion to obtain the full embedding of all training sets. We demonstrate that the target embedding matrices are approximately low-rank and provide an approximation guarantee for VerFedSV. Under the asynchronous VFL setting, we show that VerFedSV successfully reflects the strength of clients' local computational resources.

To conclude, our integrated VerFedSV provides a pioneering and exemplary framework for contribution evaluation in VFL, and this approach constitutes a solid contribution.

Reply to Question 1

In the asynchronous setting, each client may require different amounts of time to complete a training iteration and may have varying batch sizes. However, in the synchronous setting, all clients have the same time per iteration and the same batch size. As described in Section 6, our approach in the asynchronous setting involves the transmission of mini-batches from the clients to the server to update the server embeddings. There is no need to use matrix completion so that the Shapley value is proportional to the client's computational strength. In the synchronous setting, we complete the full embedding, because, in this way, the entire training set is utilized for computing Shapley value, effectively avoiding potential errors from mini-batch sampling.

Reply to Question 2

Please refer to our response in Weakness 1 regarding preparing and utilizing a separate validation set in the VFL setting.

Reply to Minor Suggestions

Misspellings We will ensure the misspellings are thoroughly correct in the final version.

Explanation for why the embeddings are sufficient For linear regression, $f$ is mean square error, and for logistic regression, $f$ is cross-entropy loss. The client model can be a linear model or a neural network. We next explain why VerFedSV only relies on embeddings and is irrelevant to the function form of $f$ or whether the task is one-class or multi-class classification.

We first recap the one-class case and then explain the multi-class case. In one-class case, we defined the embedding matrix $\mathcal{H}^m \in \mathbb{R}^{T \times N}$ where each element $(t,i)$ is defined as $\mathcal{H}_{t,i}^m = (h_i^m)^{(t)}$. In the context of the multi-class classification problem with $l > 2$ classes, the model parameter $\theta_m$ is in space $\mathbb{R}^{d^m \times l}$. Consequently, the embedding $h_i^m = \theta_m^\intercal x_i^m$ is in $\mathbb{R}^l$. Now, the embedding $\mathcal{H}^m$ is a tensor in $\mathbb{R}^{T \times N \times l}$. We reorder the tensor dimensions and lower it to a matrix $\mathcal{H}^m \in \mathbb{R}^{(l\cdot T) \times N}$.

Regarding the general function case, $h_i^m = \theta_m^\intercal x_i^m$ becomes $h_i^m = g(x_i^m; \theta_m)$, where $g$ can be a neural network with weights $\theta_m$. VerFedSV by Definition 2 in Section 4 only requires $h^i_m$ and does not depends on does not depend on the specific form of $g$.

Explain covering number Covering number $\mathcal{N}(\mathcal{D},\epsilon)$ represents the minimum number of "balls" or "sets" with radius $\epsilon$ that are needed to cover a given dataset $\mathcal{D}$. In other words, it quantifies the complexity of $\mathcal{D}$. Please refer to Definition 5 in Section B for detailed formulation.

Clients send the IDs The client will send the batch $B$ that contains the IDs of data points. We will revise it in the final version.

Report $N$ and $T$ Please refer to Table 2 in Section C for the number of training data points $N$ in different datasets. As for $T$, under the synchronous setting, it is 160, 160, 800, and 320 for each dataset, and under the asynchronous setting, it is 100. We apologize for any confusion caused and assure to be clarified in the final version.

We sincerely appreciate your positive comments and valuable feedback on our paper. We reply to each of the weaknesses and questions below.

Reply to Weakness 1

Thank you for your valuable feedback. Our experiments indeed encompass multi-class (e.g., on Covtype) and general function cases (e.g., 2-layer perceptron model on RCV1). We will ensure providing concrete explanations in the final version.

We first recap the one-class case and then explain the multi-class case. In one-class case, we defined the embedding matrix $\mathcal{H}^m \in \mathbb{R}^{T \times N}$ where each element $(t,i)$ is defined as $\mathcal{H}_{t,i}^m = (h_i^m)^{(t)}$. In the context of the multi-class classification problem with $l > 2$ classes, the model parameter $\theta_m$ is in space $\mathbb{R}^{d^m \times l}$. Consequently, the embedding $h_i^m = \theta_m^\intercal x_i^m$ is in $\mathbb{R}^l$. Now, the embedding $\mathcal{H}^m$ is a tensor in $\mathbb{R}^{T \times N \times l}$. We reorder the tensor dimensions and lower it to a matrix $\mathcal{H}^m \in \mathbb{R}^{(l\cdot T) \times N}$.

Regarding the general function case, $h_i^m = \theta_m^\intercal x_i^m$ becomes $h_i^m = g(x_i^m; \theta_m)$, where $g$ can be a neural network with weights $\theta_m$. Since our method does not depend on the specific form of $g$ and only requires $h_i^m$, it can be extended to the general function case. Admittedly, Proposition 1 on the bound of embedding matrix’s $\epsilon$-rank may not necessarily hold. However, in practice (See Section 7.1, RCV1 dataset) we still observe that embedding is approximately low-rank, so matrix completion is still an effective strategy.

Reply to Weakness 2

Thank you for your feedback on the baselines. We would like to mention that data Shapley value [1] can be easily extended to the HFL scenario but not to the VFL scenario. This is because VFL's clients partition the dataset along feature dimensions, while the data Shapley value [1] was designed to assess the importance of individual data points.

We would like to draw the reviewer's attention to our extra experiment in Section D.2, where SHAP [2] is employed as a baseline to test whether VerFedSV reflects the importance of clients’ local features. It is worth noting that the SHAP baseline cannot be directly applied to the VFL task, as it requires access to all the local datasets and may breach privacy. Nevertheless, the results presented in Table 5 of Section D.2 indicate that VerFedSV is indeed capable of capturing feature importance.

[1] Amirata Ghorbani, James Y. Zou. Data Shapley: Equitable Valuation of Data for Machine Learning. ICML 2019: 2242-2251 [2] Scott M. Lundberg, Su-In Lee. A Unified Approach to Interpreting Model Predictions. NeurIPS 2017: 4765-4774

Reply to Question 1

In VerFedSV, it will be inefficient to sum over all subsets $S\subset[M]$. However, this is a common issue in Shapley Value and well-studied in literature. Various sampling methods [1,3] are proposed for this issue. In our experiment, as mentioned in Section C, VerFedSV is computed exactly when the number of clients $M \le 10$, and approximately using Monte-Carlo sampling when the number of clients $M > 10$.

VerFedSV is efficient because it does not require model retraining. The key idea is to calculate the Shapley value for a client in each iteration of training and then aggregate these values over all iterations to determine the final contribution of the client.

[3] Jiayao Zhang, Qiheng Sun, Jinfei Liu, Li Xiong, Jian Pei, Kui Ren. Efficient Sampling Approaches to Shapley Value Approximation. Proc. ACM Manag. Data 1(1): 48:1-48:24 (2023)

Reply to Question 2

FedSV [4] and VerFedSV are applied in different scenarios -- HFL and VFL, respectively. Furthermore, it's worth noting that FedSV is specifically designed for the synchronousFL setting and relies on training rounds. In contrast, VerFedSV in Section 6 applies to the asynchronous FL setting.

[4] Tianhao Wang, Johannes Rausch, Ce Zhang, Ruoxi Jia, Dawn Song. A Principled Approach to Data Valuation for Federated Learning. Federated Learning 2020: 153-167

We sincerely appreciate the valuable suggestions you provided during the review process. Following your suggestions, we have devoted great effort to an expanded ablation study. We believe that these improvements have strengthened the paper substantially. In light of these efforts and the resulting improvements to the paper, we kindly hope that you could consider re-evaluating your score. We are confident that our work now better addresses your concerns, and we hope that the updates better reflect the contribution we aim to make to the field. We reply to each of the weaknesses and questions below.

Reply to Weakness on Writing

Thank you for your suggestions on writing and clarity. We will revise $d^m$ to $d^{(m)}$ to prevent potential misinterpretation and will thoroughly correct the typos.

Concerning the utilization of low-rank matrix completion, we initially introduced its motivation, formulation, and application in Section 5. We will further enrich the backgrounds for its solving algorithm in the appendix, including a taxonomy of existing algorithms and more detailed explanations.

In Proposition 1, $\mathcal{D}^{(m)}$ is the local data set for client $m$ defined in Section 3. Regarding the term $\gamma^{(m)}$, we deeply regret any confusion it may cause. This term is defined in Section B.2 as the bound on the $L_2$ norm of the model parameters. To be specific, it is denoted as $\gamma^{(m)} = \max_{t \in [T]}\|\theta_m^{(t)}\|$.

Finally, in line with your recommendations, we will revise the notation $\cdot^m$ to $\cdot^{(m)}$ and state Proposition 3 as an Example to enhance understanding.

Reply to Questions on Experiments

Question 1 For the dimension of each dataset, please refer to Table 2 (Metadata of all data sets) in the paper.

Question 2 Table 1 reveals that artificial clients, which submit randomly generated features, are assigned substantially lower Shapley values compared to regular clients providing real features. In this table, the Shapley value of one artificial client is compared against that of the regular clients. This setup’s purpose is to show that artificial clients are indeed evaluated as having lower contributions.

Question 3 The hyperparameter $r$ is based on approximated $\epsilon$-rank in our experiment. As for $\lambda$, we observe that the performance of VerFedSV remains relatively insensitive across a wide range of $\lambda$. To support these observations, we conduct new ablation studies as follows.

We define a deviation metric for the upcoming ablation study. For client $i$, denote its percentage of VerFedSV relative to the total VerFedSV from all clients as $s_i$. These VerFedSVs are calculated using matrix completion to estimate all embeddings. Meanwhile, we compute a ground-truth scenario where full embeddings are calculated in each training round. In this scenario, the percentage of Shapley value for client i relative to the sum of all Shapley values is denoted as $s_{i}^{gt}$ . With $M$ representing the number of clients, the deviation metric is defined as $\frac{1}{M} \sum_{m=1}^{M} \frac{|s_m - s^{gt}_m|}{s^{gt}_m}$.

Please refer to this anonymous link for the results.

The left part of the figure displays the deviation w.r.t the hyperparameter $r$, based on five independent runs. The median deviation of these runs is depicted by the solid line, while the shaded area represents the interquartile range (25% to 75% quantiles) of deviations. Take the Adult dataset as an example for analysis. The figure demonstrates that deviations are significant for $r<5$, since inadequate rank cannot accurately recover full embeddings. However, deviation decreases rapidly as $r$ increases and stabilizes at a low value when $r\ge 5$.

Practically, obtaining full embeddings is resource-intensive due to communication costs or limited resources on the client side. Thus, approximating $\epsilon$ rank may be difficult. However, the server (with sufficient computational resources), after collecting the mini-batch embeddings, can test with several increasing values of $r$. The Shapley value will converge to the ground-truth value as revealed by our ablation study.

The right part of the figure illustrates the deviation w.r.t the hyperparameter $\lambda$. It demonstrates that the performance of VerFedSV remains relatively insensitive across a wide range of $\lambda$ and we can safely set $\lambda=0.1$ for various datasets.

Thanks for your response. I have raised my score. Please also update the pdf.

If all clients' Shapley value is shifted by the minimum of the Shapley value, then is $g_m^{GT}=0$ for the client with the smallest Shapley value?

Thank you for your response. As we mentioned earlier, in the new ablation study (verifying hyper-parameter sensitivity of VerFedSV), $s_i^{gt}$ is positive, because we have this setup: clients equally partition all features and thus each client has some contributions. The deviation metric makes sense in this context.

Considering the above ablation study has already verified the conclusion on hyper-parameter sensitivity, we did not test on more general cases mentioned above (where $s_i^{gt}$ can be negative). We will add the detailed setup, intermediate result (the value of $s_i^{gt}$), and the additional results to the updated pdf now and upload it soon.

We sincerely appreciate your positive comments and valuable feedback on our paper. We have addressed your comments and made the necessary corrections to improve the paper. We would like to draw your attention to the novelty and broader impact of our research and hope that you might reconsider increasing the score based on the comprehensive merits of our research. Thank you once again for your time and valuable input. We reply to each of the weaknesses and questions below.

Reply to Weaknesses

Regarding Weakness 1: Thank you for your insightful feedback. The model-independent utility function relies on the client's data but ignores the computational resources contributed by the client. This oversight can lead to unfairness in the asynchronous scenario.

Actually, we have an example in Sec. 7.2. Imagine two clients with identical datasets. Using the model-independent utility function, both clients would be evaluated as having equal contributions. However, in an asynchronous environment, Client 1 may have superior hardware and transmission power. This advantage allows for a larger batch size and facilitates more frequent communication, resulting in a higher number of asynchronous training rounds. In such a scenario, Client 1's contribution should be greater, yet the model-independent utility function fails to recognize this, leading to an unfair assessment. We provided detailed numerical results in Sec. 7.2 to support this example. Based on your valuable feedback, we will enhance the clarity of this explanation in Sec. 2 to better communicate the potential fairness issues arising from the model-independent utility function in asynchronous settings.

Regarding Weakness 2: We appreciate your suggested references and acknowledge the importance of a comprehensive literature survey in this area. Our work VerFedSV is different from the existing works like ShapleyFL [1]. ShapleyFL applies Shapley Value in FL against malicious clients, while VerFedSV focuses on computing Shapley Value efficiently in the VFL scenario. We will include more literature works in the final version of our paper, including but not limited to, the references you suggest, more recent works on Shapley Value and its extension to HFL and VFL.

[1] Sunqi Heng et al. ShapleyFL: Robust Federated Learning Based on Shapley Value. KDD 2023

Regarding Weakness 3: Thank you for pointing out the need for a clearer explanation of the embedding $h_i^m$ in Sec. 3. The term $h_i^m$ represents the embedding of a local data point $x_i^m$ from the $m$-th client, transformed by the local model's parameters $\theta_m$. For linear and logistic regression models, this embedding is computed as $h_i^m = \langle \theta_m, x_i^m \rangle = \theta_m^\intercal x_i^m$. Then, each client uploads local embeddings $h_i^m$ to the server. The server aggregates these embeddings to obtain a global embedding $h_i$ for $i$-th data point, i.e., $h_i = \sum_{m=1}^M h_i^m$. This global embedding is employed to compute the loss, denoted by $f(h_i,y_i)$. Here, $f$ is a differentiable function. For linear regression, mean square error is employed, and for logistic regression, cross-entropy loss is employed.

We illustrated these concepts in Sec.3 and we will make sure they are more clearly explained in the final version.

Regarding Weakness 4: We have included this particular weakness in the future work section. However, it does not mean the weakness cannot be solved. One potential solution is to implement secure statistical testing before FL training and exclude clients with extremely similar datasets. This would be an orthogonal and promising future direction. We will further clarify it in the paper.

Regarding Weakness 5: We sincerely apologize for the typos and will thoroughly correct them.

Reply to Questions

For Question 1, see our reply to Weakness 1.

For Question 2, to our best knowledge, this paper is the first work of model-dependent utility function in VFL. Regarding related works of Shapley value in the VFL, we acknowledge the rapidly evolving dynamics within this research community, so we will surely update the final version of our paper with a comprehensive review.

For Question 3, see our reply to Weakness 3.