VF-PS: How to Select Important Participants in Vertical Federated Learning, Efficiently and Securely?
Authors: Jiawei Jiang
Lukas Burkhalter
Fangcheng Fu
Bolin Ding
Bo Du
Anwar Hithnawi
Bo Li
Ce Zhang
Venue: NeurIPS 2022 Accept (2022)
Keywords: Vertical federated learning
participant valuation
participant selection
mutual information

Abstract: Vertical Federated Learning (VFL), that trains federated models over vertically partitioned data, has emerged as an important learning paradigm. However, existing VFL methods are facing two challenges: (1) scalability when # participants grows to even modest scale and (2) diminishing return w.r.t. # participants: not all participants are equally important and many will not introduce quality improvement in a large consortium. Inspired by these two challenges, in this paper, we ask: How can we select l out of m participants, where l ≪ m, that are most important?
We call this problem Vertically Federated Participant Selection, and model it with a principled mutual information-based view. Our first technical contribution is VF-MINE—a Vertically Federated Mutual INformation Estimator—that uses one of the most celebrated algorithms in database theory—Fagin’s algorithm as a building block. Our second contribution is to further optimize VF-MINE to enable VF-PS, a group testing-based participant selection framework. We empirically show that vertically federated participation selection can be orders of magnitude faster than training a full-fledged VFL model, while being able to identify the most important subset of participants that often lead to a VFL model of similar quality.


VF-PS: How to Select Important Participants in Vertical Federated Learning, Efficiently and Securely?
Jiawei Jiang 1.233 Lukas Burkhalter Fangcheng Fu Bolin Ding
Bo Du Anwar Hithnawi Bo Li Ce Zhang
1 School of Computer Science, Institute of Artificial Intelligence,
Hubei Key Laboratory of Multimedia and Network Communication Engineering, National Engineering Research Center for Multimedia Software, Wuhan University
ETH Zürich OceanBase, Ant Group
Peking University University of Illinois at Urbana- -hbbaa-Chhampagn alawei.jiang dubo J0hhu. edu. en (lukas. burkhalter, anwar hithnawi, zhang) @inf www.f.eth...c...e ch
Alibaba Group
ccchengff@pku.
hemppkuuedu.com edu. cn bolin. ding@al ibaba-inc. com lbo@illinois, edu
Abstract
Vertical Federated Learning (VFL), that trains federated models over vertically partitioned data, has emerged as an important learning paradigm. However, existing VFL methods are facing two challenges: (1) scalability when # participants grows to even modest scale and (2) diminishing return w.r.t. participants: not all participants are equally important and many will not introduce quality improvement in a large consortium. Inspired by these two challenges, in this paper, we ask: How select out of m participants, where I < m. that most important?
We call this problem Vertically Federated Participant Selection, and model with a principled mutual information-based view. Our first technical contribution is VF- MINE-a Vertically Federated Mutual INformation Estimator-thal uses one of the most celebrated algorithms in database theory-Fagin 's algorithm as a building block. Our second contribution is to further optimize VF-MINE to enable VF-PS, group testing-basee based participant selection framework. We empirically show that vertically federated participation selection can be orders of magnitude faster than training full-fledged VFL model, while being able to identify the most important subset of participants that often lead to VFL model of similar quality.
Introduction
The quality of machine learning models heavily relies on the quality and volume of available data. As our understanding of machine learning shifts towards such a data-centric view, mechanisms of making data available to machine learning have attracted intensive interests [ 2 Towards this goal, Federated Learning 3 an emerging research area that focuses on training single ML. model using all data available in federated "data consortium" in secure and privacy-preserving way.
Vertical Federated Learning. In this paper, focus on specific federated learning scenario: Vertical Federated Learning (VFL) [5]. As illustrated in Figure [(a]] the VFL setting involves a data consortium that consists of m participants = {PI.... .... P. }. Each participant holds a disjoint subset of features associated with the same entity (c.g.. different hospitals holding medical records of the same patient but for different types discases). The goal of vertical federated learning is to train a single ML model over the joint feature space, in a secure and mrivacy-rresevvng way, without communicating their data each other 10
"Corresponding author.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

(i) Scalability
[d] Diminishing Return
0.4
Communication
Run Time tocell
an00
Gain
6000
0.2
4000
Purticipant (Coondinator)
2000
0.0
Participant P2
Participant P3
# Participants
Participants
Iiil Qualityy vs. Run Time
Labels
Model Quality
0.8
0.6
0.4
Features
Features
Features
RunTima (secs)
(a) In the Vertical Federated Learning (VFL) setting. each participant holds a disjoint set of features for the same set of entities; the coordinator also holds the ground truth labels. These participants commu- nicate secure and privacy preserving way in order to train a single machine learning model over the joint feature space.
(b) VFL faces two challenges: (i) Scalability and (ii) Diminishing Retun w.r. # participants, since many participants in large consortium might not provide significant quality gain. As result, (iii) dominating amount of the computation cost for large consortium might not lead to any quality gain. (LR, Bank dataset)
Figure 1: Vertical federated learning and challenges
Technical Challenges of VFL. Despite many recent efforts that significantly improved the scalability and efficiency of model training in the VFL setting, two great challenges linger, as illustrated in Figure [(b) The first challenge is scalability w.r.t # participants. Because of the requirement on secu- rity and privacy, many VFL approaches have to resort to expensive methods such as Homomorphic Encryption [1 12 and Secure Multi-party Computation I3 14]. This greatly limits the scalability of today's 's VFL systems. Another challenge is diminishing return, also when # participants grows. Since not all participants contribute equally informative knowledge, it is not unusual to observe that adding more participants does not provide significant quality gain on the final ML model. These two challenges, when put together, form a quite "ironic" picture, as illustrated in Figure [(b) supporting a large data consortium makes training time significantly longer, however, a dominating amount of these computations might not be translated into any significant quality gain.
Vertically Federated Participant Selection (VF-PS). Whereas designing more efficient model training methods in the VFL setting continues to be crucially important, in this paper, focus on an orthogonal direction to accommodate these challenges. Given a data consortium with m participants, instead of trying to speed-up the training of single ML model over all m participants, we ask: "Can we identify < m participants that are most important, and only train expensive VFL models on them instead?" We call this problem Vertically Federated Participant Selection (VF-PS). From Feature Selection (FS) to VF-PS: Connections and New Challenges. At first glance. the VF- PS problem is closely connected to traditional feature selection problems [15 16]. This is definitely true and is what, in our opinion, makes VF-PS promising - the last half-century of study on feature selection provides not only principled theoretical framework but also strong evidence that should be able to significantly decrease # participants (# features) involved but still obtain similar quality. However, VF-PS imposes unique challenges compared feature selection. VF-PS should (1) provide no weaker security and privacy guarantees compared with other VFL training systems 9 and (2) should be much more efficient than training single VFL model over all participants.
Summary of Technical Contributions. In this paper, we focus on a specific, while one of the most natural, way of modeling VF-PS: we should select the subset of participants that jointly preserve the greatest amount of mutual information (MI) between features and labels. Under this view, designing VF-PS algorithm involves two technical issues: (1) how to estimate MI for subset of participants? and (2) how to search the subset of participants that preserve the greatest amount of MI?
(C1) Our first contribution is VF-MINE-2 Vertically Federated Mutual INformation Estimator. Given a subset of participants, VI-MINE estimates MI between the features of these participants and the labels. VF-MINE protects data privacy via homomorphic encryption. The most surprisingly

---

technical observation is that one of the most popular MI estimators [17], used by sklearn, can be made orders of magnitude faster. This is by optimizing data movement between different participants, with Fagin's 's algorithm [18] as building block.
(C2) Our second contribution is VF-PS, that uses VE-MINE to search for the subset of participants that preserves the greatest amount of MI in group testing-based framework. We provide a set of optimization techniques to further optimize data movement between different participants.
(C3) We provide rigorous security analysis for the proposed methods. We then empirically show that, our VF-PS framework can be up to two orders of magnitude faster than training full-fledged VFL models. Moreover, VF-PS can often select much smaller subset of participants but maintain a similar model quality.
2 Preliminaries
Federated Learning. Federated learning is category of distributed learning technique that enables different organizations or users to collaboratively learn machine learning (ML) models, without exposing their personal data to other parties 21 Assume X' denotes instance features, Y denotes instance labels and I denotes instance IDs, federated learning can be classified into two categories, i.e., horizontal federated learning and vertical federated learning, according to how (X, )) I) are distributed across different participants.
Privacy Protection Techniques. Preserving the privacy of input data is a crucial requirement of many deployments of federated learning. Therefore, these systems often used in conjunction with privacy protection techniques. In what follows, we briefly summarize key techniques used in this space. 1) Differential Privacy randomly perturbs the transferred data (c.g.. gradient) with noises, such as Gaussian noise [22). Laplacian noise [23). and Binomial noise (24). 2) Homomorphic Encryption encrypts all data before they are transferred 12 25 26 and supports arithmetic computation on encrypted data. 3) Secure Multiparty Computation (MPC) enables multiple parties to collaboratively compute an agreed-upon function without leaking local input to any other party except for what can
be inferred from the output [3 14 27 28
Vertically Federated Participant Selection via Mutual Information
In this section, we describe our algorithm for Vertically Federated Participant Selection (VF-PS).
3.1 Vertically Federated Participant Selection
We assume standard data model, following previous efforts in VFL 7 8
let there be m participants and N data instances, and X E RNF be the joint feature space where is the dimension of the joint feature space. In the VFL setting, this joint feature space X is vertically partitioned over different participants - each participant P; E P holds a subset of features (columns) of X, denoted by X,. Without loss of generality, we have: X = [X1 ......... Xm) Among all m, there a leader participant, which holds the instance labels Y. We assume that all participants agree on the same identifier (ID) of each data instance.
Security Requirements. Following previous systems, e.g., Pivot 9. VI 29 we have the following standard security requirements. 1) Feature Security: Features X, on each participant cannot be shared with any other party. 2) Aggregation Security: Only the leader participant can obtain an aggregated result over all participants" local data. 3) Identity Security: No other party, except the participants, can obtain the identifiers (IDs) of instances.
Murual Information based VF-PS. Similar to the classic feature selection problem, we focus one of the most natural ways to VF-PS we aim selecting the subset of participants that jointly preserve the greatest amount of mutual information with the label. Formally, the computation that we hope to conduct, under the previous security requirements and vertically partitioned data model, is
max MI ... ...l:,;;) s.t, Vi e [4] a; E [m]] and Vi,j E [4] aq & ag.
(I)
Ori Or1....00
where MT(() estimates the mutual information from finite samples, and < m is pre-defined constant specifying the number of participants to select.
3

---

3.2 VF-MINE: A Vertically Federated Mutual Information Estimator
As we see Equation I solving this problem involves two different questions: (1) how to estimate MI given fixed subset of participants, i.e., MI(X,, ... Xx. Y)? and (2) how to efficiently search for the best subset, i.e., max without enumerating exponential many possibilities? We focus on the first problem in this section, and leave the second question to Section 3.3
3.2.1 Baseline Method
KNN-based MI Estimator: We focus on standard family of MI estimators that is widely used practice (e.g.. in sklearn's 's feature selection module), which based on k-nearest neighbors (KNN) 30) Let there be N data pairs D {[,, Ms}} where y; is a label and æ is feature vector, KNN-based MI estimator enumerates multiple query data pairs. For each query g = (xg. My):
1. We first compute Nq. the number of examples in D that share the same labels as yg. i.e.,
Ng = ( y) E D y = Mg
2. We then construct N N...,, containing all k-nearest neighbors among data examples that share the same label. Let dg be the maximal distance between examples in N NNK.,, and Zg..
3. We then compute my. the number of examples in D that has distance to 24 smaller than dy.
Given Q as a subset of query data pairs, we estimate the mutual information as fol- lows: 121 Eg (N²(N- - (N,)) + ab( - (m,)), where &b is the digamma function rb(x))
du (n(T( ~ Inx 22
Baseline Implementation of VF-MINE. We now provide baseline implementation of this estimator in the vertically federated setting. We assume that we use Euclidean distance as our distance metric, but our technique can be naturally applied to other distance metrics. We choose additive homomorphic encryption (HE) to protect data privacy since it is widely adopted in the literature g 11 25). We HE.Enn(-) Dec())
denote the encryption/decryptio function, and [-] an encrypted data item. Below, we present a single VF-MINE routine. There are three roles in the system key server, aggregation server, and participant:
Key server The key server generates public and private HE (homomorphic eneryption) keys (pk, sk). allocates sk to the leader participant, and pk to all participants and the aggregation server. We assume the key server is trusted and does not collude with any party.
Aggregation server. An aggregation server provides
addition operator that securely aggregates multiple encrypted data items: [d] = E. u. ( [[]d]]]; : pk).
Participant. Each participant P; holds feature subset of all N data instances. For query data pair = (Ig. 34), each participant P. calculates di = [(I.g. x2,1)² for (2). E D). the distances between its local features of x, and data pairs in D. We call d2 the partial distances. Then, P, encrypts partial distances and sends dd] = H..Enet Enc(d;; pk) to the aggregation server via the addition operator. There is a leader participant that holds the labels. It receives the complete distances [d] from the aggregation server, decrypts it to = H F. Dec((d) sk), and calculates MI, responding to the procedure of KNN-based estimator.
3.2.2 Fagin- Inspired Method
The baseline method has potential performance issue, that is, it has aggregate all the data instances. Since the operation through homomorphic encryption is often time-consuming, this baseline method can be inefficient in practice, especially for many large-scale datasets. To decrease the cost, a potential way is to decrease the number of aggregated instances. Motivated as such, our first question is can we aggregate fewer data instances and meanwhile obtain the correct results? We observe that the vertical KNN task can be seen as aggregating multiple "sub-ranking"s "s into a "global ranking". Based on this interpretation, we propose to leverage a textbook aggregation algorithm, called Fagin, to efficiently find k-nearest neighbors.
Fagin Algorithm. The problem of top-k query aims at finding & instances with the highest (or lowest) scores from multiple lists of instances. Assume there are parties and N instances, each party i has a score for each instance j. denoted by 85. On each party, the instances are sorted by their scores. Globally, each instance is assigned an overall score by combining the scores all parties using an

---

Participant
Aggregation Server
Party A
Party
Pant
J 4
W
Xa
Inibence
Score
Inatance
Score
Instance
Score
+
0.9
0.8
<7
0.7
0.5
Shuffle
Seot
-9
Participant Pg
Participant P
<4
0.1
46
0.0
F
[d]
Ays
Reindex
Enoty
[
51 1.9
MI
Key Server
0.7
keys
(a) Fagin Algorithm
(b) Implementation with HE
Figure 2: Fagin-inspired method for estimating MI
aggregate function. This problem has been extensively studied by series of algorithms [31]. In this work, we choose Fagin as it widely used [8]. Fagin requires that the aggregation function aggr is monotone: aggr($1, 82, .... 8m) (ggr(s (1 8/2 ... smm) if < 5 for every v.
Figure 2(a) shows an example of Fagin algorithm that selects top-2 instances from three parties with the addition aggregation function. The processing of Fagin algorithm contains three major steps: 1) sequentially scan the sorted lists from all parties until there are k instances that have been seen in all lists, 2) obtain the scores of all the instances seen so far (including those have not yet occurred in all lists), and 3) use the aggregation function compute global scores for candidate instances found in the previous step and select top-k instances therein. In the example of Figure 2(a) Fagin scans three rows and finds that s and 83 are in three lists. Afterwards, the scores of all instances in three rows (i.e., 81, 82, 83, 54) are aggregated. We denote math. math.Fagin(S Fagin(-) the standard Fagin algorithm in this paper, that takes multiple lists of instance IDs as input and outputs candidate IDs.
Ragin-inspiree Optimization for VF-MINE. We now implement the Fagin inspired method. The key allocation (step 1) is the same as the baseline method. The key is to aggregate "sub-ranking"s with Fagin algorithm while preserving their privacy. The implementation of the secure Fagin operator is shown in Figure 2(b) (step 2)-5). We propose a shuffle strategy - each participant uses the same seed randomly shufile local data instances (step @)) Then, we generate "pseudo ID" for each instance that is equal to the index after shuffling. Each participant P. sends the sub-ranking of pseudo IDs, denoted by It the aggregation server, instead of sending the real IDs (step 3-@). The aggregation server runs the standard Fagin algorithm to find k-nearest candidates from all sub-rankings. Since the estimation of MI depends on the label, the leader participant is responsible for stopping Fagin. The aggregation server sends the pseudo IDs of Fagin candidates, denoted by T to each participant (step @). After the Fagin operator, the participants re-index these pseudo IDs to their original IDs (step
)). The following steps are similar to the baseline method (step 7)))).
3.3
VF-PS: Group Testing-based Participant Selection
The second component in our framework is to search for the subset of participants that maximizes MI. We adopt a standard group lesting-based search procedure.
Group-testing Framework. The VF-PS problem under the group testing framework runs as follows:
1. We select collection of T tests, each of which corresponds to subset of participants S, S P;
2. For each S, we estimate its mutual information and use as the score;
3. For each participant, we compute its importance as the average score in all tests it participated in.
4. We pick the top-k k most important participants.
Formally, let U(S) be the score of group S C P defined as the mutual information over Ne validation
x m the participating matrix, where A if participant belongs to the 1-th test group. Corresponding to each row of A is "score" U(A (I) = U( = 1)). Consider A as the test design, the total score of participant P; 24 [ -U .... UA[T 1])]. The participant selection is conducted using these scores.
data pairs: V V= [[==,,,0 v))), and let A of dimension
5

---

Algorithm Fagin-inspired Participant Selection with Communication Batching Key Server:
(pk, sk) H. KeyGen) /ggenerate homomorphic public and private keys
Send pk to aggregation server, send (pk, sk) to participants
Participants:
(Leader) Generate groups G = (Si...., and send them to aggregation server //find Fagin candidate instances, whose IDs are 7
1: [d[]] = HEHHEEEE E.EEEEEc(d((.. pk): /enerypt partial distances Fagin candidates
2: Server.addition/ (df)) //send encrypted partial distances to aggregation server
3: { [ds]] Server. schedulere)))) //receive aggregated distances from aggregation server
4: I''t mmahharrgorry E. De sk]} /dccryppt and sort aggregated distances
5: [ Server.scheduler .callbcckk ( (1's) //send local sorted indices to aggregation server
6: (Leader) scores group group.testing ( (Is).G.)) //leader calculates MI scores
Aggregation Server:
function Server addiitond [[[ }]:
{[dses]} = {H E. S.m (Id." ]:pe Sk:pk); E 9}
function Struersschhauule(((
randomly assign ( [[dsea]} I to participants
function Server.scheduler beceheddueer.cllaacc((((( www.lbcccl(l.... (T'a))
return {1s} } = reinder( ( S E G) to leader participant
Implementation of Group Testing. The implementation of group testing for Fagin-inspired method quite natural. Specifically, we run Fagin-inspired MI estimation over each test group (subset of participants). The counterpart using the baseline method can be obtained by skipping the Fagin stage.
1. Generate testing groups. The leader participant randomly generates T groups (e.g.. the first group
S { and the second group S2 = [Pl, P2)), which are sent to other participants.
2. Run inggin-isppiee method. The proposed framework handles each test group independently. Specifically, for each validation instance, the participants in test group A [t] jointly run Fagin- inspired KNN and calculate the mutual information. The score of the group, U (A(t)), is averaged over all the validation instances.
3. Participant selection. Once running all the groups, the leader participant calculates the MI-based score of each participant, with which most valuable participants are selected.
3.3.1 Group Testing with Communication Batching
The naive implementation of the group testing routine has a critical drawback. The Fagin candidates generated by different groups may contain overlapping instances, causing significant amount of redundant overheads. As we will show, by leveraging what we call the Inclusion Property of the Fagin algorithm, can batch the communication and computation of all test groups.
Inclusion Property of Fagin. The principle of the Fagin algorithm to scan the sub-rank sub-rankings from multiple participants until k distinct instances are found in all the sub-rankings. Given two subsets of participants, S₁ and S2, what we can say about their data access pattern?
Theorem 1. (Fagin's 's Inclusion Property) Given two groups of participants S₁ C and S2 S P, their k-nearest candidates generated by Fagin algorithm satisfy F, C F2 Ff S2.
Proof. For the group S2, assume the Fagin algorithm scans F rows of sub-rankings (Ra, Vp, 82) before finding instances D = =x1, I2,, Fx occurring in Vy E S2. The ranking of each instance in D should satisfy:
1 1 p/) S F, for Vz, E D and fj S2
Since S₁ is subset of Sz, we can directly infer:
I(x, pk) < F, for Vx, E D and Pk S
The above implies that we can find in each participant p E S before scanning F' rows The Fagin candidate set of S2 contains all the unique instances within F rows:
F₂ Set(Up:es, Fl)

---

Datasets
Synihesis
G2-4
G2-128
Bank
Unbalance
Letter
Binchl
Binch2
instances
1000
2048
2048
3200
6500
20K
100K
100K
Teatures
50
128
16
2
2
classes
2
26
100
100
partitions
Table 1: Evaluated datasets.
Similarly, the Fagin candidate set of S is subset of all unique samples within F rows:
Fi S Sel(Umes, R:|: F))
Since Sj subset of S2, all the samples appear within F rows of S₁ also appear in S2: Set(UpiEs, R.l: F)) S SettUp,es,R.l F))
Therefore, we can conclude: 5 F2.
Theorem indicates that the Fagin candidates of all groups can be found in those of the "complete group" that consists of all the participants. Based on this observation, we propose to batch the Fagin tasks of different groups in single execution.
Implementation of Batch Optimization. The batching optimization is illustrated in Algorithm T The leader participant generates groups G (. and sends G to the aggregation server. The following shows the steps after getting the Fagin candidates, Ix. for the complete group P.
1. Each participant P. encrypts partial distances with homomorphic encryption. (line 1)
2. Each participant sends encrypted partial distances of Fagin candidates, i.c.. [d,"), to the aggregation server through Server addition (line 2). For each group G, the aggregation server calculates the sum of all partial distances in S.
3. A random scheduler,
serruerscheduler. on the aggregation server sends the aggregated distances of each group (denoted by [ds]) to participant randomly (line 3).
4. For each received [ds]. the participant performs decryption and gets the sorted index I'g (line 4).
5. The sorted indices sent the aggregation server through scruerrscheduler _collback (line 5). The aggregation server lets the random scheduler associate them with the corresponding groups. Then, the aggregation server sends the sorted IDs of all the groups, {Ts}. to the leader participant.
6. The leader participant calculates the MI-based scores using the method of group testing and performs participant selection (line 6).
3.4 Security Analysis
this work, we assume that the key server honest and does not collude with any involved party. The aggregation server and all the participants are donest-but-curien
common knowledge threat model used in the federated learning literature [28] 32). The security properties of our proposed methods are summarized follows (recall security requirements in Section 3.1. Feature security is protected against any curious party since the participants do not share their loeal features. Aggregation security assured against curious aggregation server by homomorphic encryption. Regarding curious or colluding participants, aggregation security is also assured the leader participant is benign. Identity security is achieved against curious server there is no server-participan collusion, because the proposed methods do not share instance identifiers / with the server.
Evaluation
We conducted experiments to validate the efficiency and effectiveness of the proposed methods.
4.1 Experimental Setting
Implementation. Numpy and PyTorch libraries are used to perform data loading and tensor manipula- tions. We implement RPC communication with proto2 and gRPC. TenSEAL (3 is a homomorphic library built on top of Microsoft SEAL 34 We run experiments cluster, in which each machine is equipped with 24 GB memory, cores and 10 Gbps bandwidth.
7

---

Synthesis
02-4
02-128
Bank
Unbalance
0.9
1.0
Accuracy
0.c5
Random Lasse
0.
VF-PS
All Train
X
X
0LE
0.55
0.7
0.8
0d
5002
5010
20320
20000
30032
(secal
(sees)
time
Figure 3: Selection performance (Pivot, 50% participants). "All-Train" refers to training on all participants. The other datasets are not reported because cach training task costs more than one day.
Synthesis
G2-4
G2- 128
Bank
Unbalance
Letter
Birch1
Birch2
Accuracy
Random Lasse
Wi-FS
Train
>0
X
X
bat
530200
Run time (seca)
Run time iseca)
Run time (sacs)
Run time (seca)
Run time (seca)
Run time (secs)
Run time (seca]
Run time (secs)
Figure 4: Selection performance (LR, 50% participants).
Synthesis
Bank
X
1.0
bB
Accuracy
Randoo Lasso
VF-P5 All Train
X
X
3000
5033 Run
20020
10000
20003
50300
500320
500033
(secal
time
Run (secs)
Figure 5: Selection performance (KNN, 50% participants).
Datasets, Table Iillustrates all datasets that we used. Synthesis is a synthesis dataset by randomly generating separation hyperplane, based on which data instances sampled. The other datasets are collected from online repository [35 36 and prior work (37-39] Each dataset split into training set (80%), validation set (10%). and a test set (10%). We randomly partition the training set into several vertical partitions and put each partition on one machine.
ML Models. We choose Pivot [9] vertically federated tree training engine, as the downstream ML model. Additionally, we also implement logistic regression (LR), and k-nearest neighhor (KNN).
Participant Selection Baselines. We compare the following baselines on participant selection. 1) RANDOM: We randomly choose participants and run ML model. The result averaged over ten runs assure the robustness. 2) LASSO. Lasso regression is standard feature selection method in scikit-learn. We train Lasso model and choose high-impa iighiimprrtance participants according to the absolute sum of coefficients each participant. 3) VF-Ps is our proposed method.
Protocols. We implement Adam 40 and vanilla SGD as the optimization algorithm for LR and Lasso. We grid search the optimal learning rate in {0.001, 0.01, 0.1) and the regularization term in (10-4, 10-3 10-2). and set batch size 256. We terminate the task after 50 epochs or the validation loss does not decrease within 5 epochs. For Pivot, choose GBDT tree, and tune tree depth in {2, 3, 4} and tree number {1, 2. The number groups T set 10. The other hyper-parameters are set as default.
4.2 Evaluation of Participant Selection
Selection Performance. We first study the following question: can our proposed method outperform buselines regarding the selection of high-importance participants? We compare R RANDMM, LASSO and VF-Ps in terms their performance of participant selection. When the downstream classification model is Pivot, Figure 3 shows the performance of all methods for selecting 50% participants. RANDOM the fastest by instantly choosing participants; however, its selection accuracy can be much worse on many datasets. LASSO is the slowest since it needs to multiple epochs until convergence and tunes the typer-parameters. VF-PS is only slightly slower than RANDOM and significantly faster than LASSO. Meanwhile, VF-Ps selects comparable, and often better, subsets of participants, indicated by the accuracy training Pivot only on selected subsets. When the classification model becomes LR and KNN, observe similar phenomena, shown in Figure
Comparison Full-fledged Training. We then turn to another question: does participant selection provide benefits compared to training with all the participants? To answer this question, also

---

Synihesis
G2-4
G2-128
Bank
Unbalance
Letter
Birchl
Birch2
Vr-Ps/500%
0.60
0.68
1.0
0.89
0.93
0.89
0.1
0.99
VF-Ps/25%
0.59
0.61
0.8
0.83
Brute force/50%%
0.60
0.68
1.0
0.93
0.93
0.94
0.1
0.99
Brute- f5rte-forve/25%
0.63
0.93
Table 2: Comparison the brute-force strategy on KNN. The metric is the test accuracy.
VF-PS w/o Bath
VF-P5 w/o Batch
VF-P5 w/o Fagin Fagin
VF-PS
Synthesis
62-4
G2-128
Bank
10
seconds
1.0
1.00
100
Unbalance
Letter
Birch1
Birch2
seconds
10
107
10
100
10
10
Figure 6: Ablation study of proposed method.
show the result of training using all participants ("All-Train") in Figure 3
As we can see, the selection time of VF-Ps is orders of magnitude faster than the training time using all the participants; meanwhile, if we were to train a model only on the selected subset, we can achieve similar test accuracy most datasets. On some datasets, e.g., Synthesis, G2-128, and Letter, we even observe higher accuracy after participant selection compared to the full-fledged training. This shows that some participants may have negative impacts on the model quality, and it is beneficial to choose high-importance participants. These experimental results verify the effectiveness and efficiency of participant selection.
Comparison to Brute-force Strategy, Intuitively, the brute-force solution for participant selection is to enumerate all the possible groups and choose the best one. Although this method is too time- consuming (up to two orders of magnitude slower according to our results), it provides the best possible selection strategy that can be used to understand how big is the gap between our selection strategy and the optimal (brute-force strategy)? Table[] the results of VF-Ps and brute-force on KNN (other models are too slow to run the brute-force strategy). When the selection ratio is 50%, VF-PS gets the same selection quality on six datasets out of eight. Overall, the gap of selection quality moderate most datasets. It is interesting future direction come up with better participant selection criteria, going beyond mutual information.
Ablation Study. We now validate that both system optimizations (Fagin and Batching) significantly improve the system performance. We compare VF-Ps with three variants-wil Fagin, w/o batching, and w/o both as illustrated in Figure We see that both optimizations are crucial to the performance disabling either of them significantly slows down the runtime on all datasets.
Related Work
Federated Learning. Federated Learning (FL) is category of distributed machine learning approach that lets multiple clients jointly train machine learning models over their personal data without data leakage 33 Since the feature space and sample space of participating parties may not be identical, federated learning can be classified into horizontally federated learning and vertically federated learning. Horizontally federated learning a scenario in which different parties share the same feature space but different sample space. In contrast, in vertically federated learning, different parties have the same sample space but different feature space.
Vertically Federated Learning. Hardy et al. (8) proposed three-party vertically federated logistic regression solution by entity resolution and additively homomorphic encryption. Yang al. 41 from WeBank and Yang et al. [42) from Baidu further extended vertically federated logistic regression to Quasi-Newtoon optimization and non-coordinator scenario. Feng and Yu [6] designed a multi- participant and multi-class federated learning framework for vertical training data. VAFL [7] was a vertically federated learning framework that allows each client to asynchronously run stochastic gradient algorithms without coordination with other clients. Pyvertical 43 was proposed to train multi-headed SplitNNs in the context of vertically federated learning using private set intersection.
Liu et al. [4] proposed asymmetrical vertically federated learning framework that protects sample

---

IDs with the private set intersection protocol. Pivot [9] was proposed to train privacy- preseeving vertical decision tree using MPC protocol.
Federated Participant Selection. In the horizontally federated scenario, FedCS 45 tried to solve the resource heterogeneity in federated setting and conducted client selection accelerate system performance. FedMCCS [46] further introduced multicriteria approach for client selection, con- sidering clients resources including CPU, memory, energy, and time. To address limited bandwidth in the presence of many clients, Huang et al. 47 proposed a selection policy to improve training efficiency while assuring client fairness. Different from these works that studied participant selection for system heterogeneity [48], our work focuses individual participant for the trained model. A few early, seminal works studied contribution-base participant selection in horizontally federated learning [49]
selection regarding the contribution of each
6 Limitation
Although VF-PS works well range of workloads, it still has several limitations:
Multiple training stages. In this paper, we treat VF-PS as a task that is similar to feature selection, which is pre-processing step that is often fonce-and-for-all However, there are use cases in which the importance of each participant changes during different training stages, then VF-PS may not find the optimal result.
Reward assessment. The goal of this work is to measure the mutual information of each participant To come up with a "reward", it needs to be carefully "normalized" over the "importance" of each participant- - directly using the mutual information provided by VF-PS as "reward" could cause problems on fairnsss. This problem definitely requires careful further studies.
Generalization of MI estimator: KNN-based MI estimator can be biased towards smaller local feature subsets with Euclidean distance. Our technique also go beyond Euclidean distance as long as local scores can be aggregated using a monotonic aggregation function, most, if not all, of our optimizations for feature selection, our methods will probably also inherit. We will study other distance metrics in future work.
still be applied. But still, whatever limitations that MI-based method has
Large-scale federated network. It is an interesting future research direction to understand real- world VFL scenarios where the federated network consists of an even larger number of partic- ipants/organizationn.. When this number becomes very large, we do expect that VF-PS could encounter performance degradation due to the limitation of the Fagin strategy. We will study this challenging problem in future work.
7 Conclusion
In this work, we study participant selection in the context of vertically federated learning. We model this problem as a mutual information- based view. We first propose novel mutual information estimator, called VF-MINE, that uses Fagin's algorithm. To perform participant selection, we propose a group testing-batt base framework VF-PS on top of VF-MINE. We implement our proposed method using homomorphic encryption and design a batching optimization. We analyze the security properties of the proposed methods and show that our methods achieve orders of magnitude improvements.
Acknowledgments and Disclosure of Funding
This work is supported by the National Natural Science Foundation of China under Grant No. 62225113, OccanBase, and Ant Group. CZ and the DS3Lab gratefully acknowledge the support from the Swiss State Secretariat for Education, Research and Innovation (SERI) under contract number MB22.00036 (for European Research Council (ERC) Starting Grant TRIDENT 101042665), the Swiss National Science Foundation (Project Number 200021 100021_184628, and 197485), Innosuisse/SNF BRIDGE Discovery (Project Number 40B2-0 187132), European Union Horizon 2020 Research and Innovation Programme (DAPHNE, 957407), Botnar Research Centre for Child Health, Swiss Data Science Center, Alibaba, Cisco, eBay, Google Focused Research Awards, Kuaishou Inc., Oracle Labs, Zurich Insurance, and the Department of Computer Science at ETH Zurich.
10

---

References
[1] Arun Kumar, Matthias Boehm, and Jun Yang. Data management in machine learning: Chal- lenges, techniques, and systems. In Proceedings of the 2017 ACM SIGMOD International Conference on Management of Data, pages 1717-1722, 2017.
[2] Neoklis Polyzotis, Sudip Roy, Steven Euijong Whang, and Martin Zinkevich. Data manage- ment challenges in production machine learning. In Proceedings of the 2017 ACM SIGMOD International Conference on Management of Data, pages 1723-17266 2017.
[3] Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Chal- lenges, methods, and future directions. IEEE Signal Processing Magazine, 37(3):50-60, 2020.
[4] Keith Bonawitz, Hubert Eichner, Wolfgang Grieskamp, Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloe Kiddon, Jakub Konečný, Stefano Mazzocchi, H Brendan McMahan, et al. Towards federated learning at scale: System design. arXiv preprint arXiv: /902: 01 0104,, 2019.
[5] Qiang Yang, Yang Liu, Tianjian Chen, and Yongxin Tong. Federated machine learning: Concept and applications. ACM Transactions on Intelligent Systems and Technology (TIST), 10(2):1-19, 2019.
[6] Siwei Feng and Han Yu. Multi-participant multi-class vertical federated learning. arXiv preprint arXiv:2001. 154, 2020.
[7] Tianyi Chen, Xiao Jin, Yuejiao Sun, and Wotao Yin. Vafl: method of vertical asynchronous federated learning, arXiv preprint arXiv:2007.06081, 2020.
[8] Stephen Hardy, Wilko Henecka, Hamish Ivey-Law, Richard Nock, Giorgio Patrini, Guillaume Smith, and Brian Thorne. Private federated learning on vertically partitioned data via entity resolution and additively homomorphic encryption. arXiv preprint 1111.
2017.
[9] Yuncheng Wu, Shaofeng Cai, Xiaokui Xiao, Gang Chen, and Beng Chin Ooi. Privacy preserving vertical federated learning for tree-based models. Proceedings of the VLDB Endowment, 13 (11):2090-210) 2103, 2020.
[10] Arash Fard, Anh Le, George Larionov, Waqas Dhillon, and Chuck Bear. Vertica-ml: Distributed machine learning in vertica database. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, pages 755-768, 2020.
[11] Michael Nachrig, Kristin Lauter, and Vinod Vaikuntanathan. Can homomorphic encryption be practical? In Proceedings of the 3rd ACM workshop on Cloud Computing Security Workshop, pages 113-124, 2011.
[12] Abbas Acar, Hidayet Aksu, A Selcuk Uluagac, and Mauro Conti. A survey on homomorphic encryption schemes: Theory and implementation. ACM Computing Surveys (CSUR), 51(4): 1-35, 2018
[13] Payman Mohassel and Yupeng Zhang. Secureml: A system for scalable privacy-preserving machine learning. In 2017 IEÉE Symposium on Security and Privacy, pages 19-38, 2017.
[14] Wenting Zheng, Ryan Deng, Weikeng Chen, Raluca Ada Popa, Aurojit Panda, and lon Stoica. Cerebro: platform for multi-party cryptographic collaborative learning. In 30th USENIX Security Symposium (USENIX Security), 2021.
[15] Kenji Kira and Larry A Rendell. A practical approach feature selection. In Machine Learning Proceedings, pages 249-256. 1992.
[16] Shay Cohen, Eytan Ruppin, and Gideon Dror. Feature selection based on the shapley value. In Proceedings of the 19th International Joint Conference on Artificial Intelligence, pages 665-670, 2005.
[17] Brian Ross. Mutual information between discrete and continuous data sets. PloS one, 9(2): c87357, 2014.
11

---

[18]
Ronald Fagin, Amnon Lotem, and Moni Naor. Optimal aggregation algorithms for middleware. Journal of Computer and System Sciences, 66(4):614-656, 2003.
[19] Essam Mansour, Kavitha Srinivas, and Katja Hose. Federated data science to break down silos [vision]. ACM SIGMOD Record, 50 222116222222222 2022.
[20] Evangelia Kalyvianaki, Marco Fiscato, Theodoros Salonidis, and Peter Pietzuch. Themis: Fairness in federated stream processing under overload. In Proceedings of the 2016 ACM SIGMOD International Conference on Management of Data, pages 2011,,,,,016..
[21] Sebastian Baunsgaard, Matthias Boehm, Ankit Chaudhary, Behrouz Derakhshan, Stefan Geißelsöder, Philipp M Grulich, Michael Hildebrand, Kevin Innerebner, Volker Markl, Claus Neubauer, et al. Exdra: Exploratory data science on federated raw data, In Proceedings of the 2021 / ACM SIGMOD International Conference Management of Data, pages 2450-2463, 2021.
[22] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. Proceedings of the 2016 ACM SIGSAC Conference Computer and Communications Security, pages 308-33 308-318, 2016.
[23] Luca Melis, George Danezis, and Emiliano De Cristofaro. Efficient private statistics with succinct sketches. arXiv preprint arXiv: 1508.0/ 10, 2015.
[24] Naman Agarwal, Ananda Theertha Suresh, Felix Yu, Sanjiv Kumar, and H Brendan Memahan. cpsgd: coamuuication--ffcienn and differentially-privaad distributed sgd. arXiv preprint 1805. 10559, 2018.
[25] Valeria Nikolaenko, Udi Weinsberg, Stratis Ioannidis, Mare Joye, Dan Boneh, and Nina Taft. ridge regression on hundreds of millions of records. In 2013 IEEE Sympo- sium on Security and Privacy, pages 334-348, 2013.
[26] Ronald L. Rivest, Len Adleman, Michael I. Dertouzos, et al. On data banks and privacy homomorphisms. Foundations of Secure Computation, 4(11):169-188) 1978.
[27] Wenliang Du, Yunghsiang S Han, and Shigang Chen. preeeyyp multivariate statistical analysis: Linear regression and classification. In Proceedings of the 2004 SIAM International Conference on Data Mining, pages 222-222-2222222222222222222 223, 2004.
[28] Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for privacy-preserving machine learning. In Proceedings of the 2017 ACM SIGSAC Conference Computer and Communications Security, pages 1175-1191, 2017.
[29] Fangcheng Fu, Yingxia Shao, Lele Yu, Jiawei Jiang, Huanran Xue, Yangyu Tao, and Bin Cui. Vf2boost: Very fast vertical federated gradient boosting for cross-enterprise learning. In Proceedings of the 2021 ACM SIGMOD International Conference Management of Data, pages 563-576, 2021.
[30] Alexander Kraskov, Harald Stögbauer, and Peter Grassberger. Estimating mutual information. Physical Review E, 69(6):06613) 18,,, 2004.
[31] Yingbo Zhou, Utkarsh Porwal, Ce Zhang, Hung Q Ngo, XuanLong Nguyen, Christopher Ré, and Venu Govindaraju. Parallel feature selection inspired by group testing. Advances in Neural Information Processing Systems, 27, 2014.
[32] Reza Shokri and Vitaly Shmatikov. Privacy- preeeevipreeriiggg deep learning. Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, pages 1310-1321, 2015.
[33] Ayoub Benaissa, Bilal Retiat, Bogdan Cebere, and Alaa Eddine Belfedhal. Tenseal: A library for encrypted tensor operations using homomorphic encryption, 2021. URI, sttttp:://gihhi thub com Com//peemMined/TenStall
12

---

[34] SEAL. Microsoft SEAL (release h0...t/g///gtaaub.oooo//ttttrsss March 2022.
Microsoft Research, Redmond, WA.
[35] Rong-En En Fan. Libsvm data: Classification, regression, and multi-label. URL https://www
csie. ntu. edu. http:/ahww....ggaaaaaa/aaaaaaaaa
[36] Pasi Fränti and Sami Sieranoja. K-means properties on six clustering benchmark datasets, 2018.
URL http:://s//s...... uef. f1/ sts/spp//aat/ httppp//aaaatss////esm
[37] Pang Wei Koh and Perey Liang. Understanding black-box predictions via influence functions.
In International Conference on Machine Learning, pages 1885-1899 194, 2017.
[38] Ruoxi Jia, David Dao, Boxin Wang, Frances Ann Hubis, Nick Hynes, Nezihe Merve Gürel, Bo Li, Ce Zhang, Dawn Song, and Costas Spanos. Towards efficient data valuation based on the shapley value. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1167-1176, 2019.
[39] Bojan Karlaš, Peng Li, Renzhi Wu, Nezihe Merve Gürel, Xu Chu, Wentao Wu, and Ce Zhang. Nearest neighbor classifiers over incomplete information: from certain answers to certain predictions. Proceedings of the VLDB Endowment, 14(3):255-267, 2020.
[40] Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6995 62800 2014.
[41] Kai Yang. Tao Fan, Tianjian Chen, Yuanming Shi, and Qiang Yang. A quasi-newton method based vertical federated learning framework for logistic regression. arXiv preprint 19210:111..00513. 2019.
[42] Shengwen Yang. Bing Ren, Xuhui Zhou, and Liping Liu. Parallel distributed logistic regression for vertical federated learning without parrt- coordinator. arXiv preprint arXiv: 1,0029924 2019.
[43] Daniele Romanini, Adam James Hall, Pavlos Papadopoulos, Tom Titcombe, Abbas Ismail, Tudor Cebere, Robert Sandmann, Robin Roehm, and Michael A Hoeh. Pyvertical: A vertical federated learning framework for multi-headed spliton. arXiv preprint arXiv:2 (0l::2/044000 104.0044099 2021.
[44] Yang Liu, Xiong Zhang, and Libin Wang. Asymmetrical vertical federated learning. arXiv preprint arXiv:2004.07427, 2020.
[45] Takayuki Nishio and Ryo Yonetani. Client selection for federated learning with heterogeneous resources in mobile edge. In ICC 2019-2019 IEEE International Conference on Communications (ICC), pages 1-7, 2019.
[46] Sawsan AbdulRahman, Hanine Tout, Azzam Mourad, and Chamseddine Talhi. Fedmces: Multicriteria client selection model for optimal iot federated learning. IEEE Internet of Things Journal, 86):473344735, 2020.
[47] Tiansheng Huang, Weiwei Lin, Wentai Wu, Ligang He, Keqin Li, and Albert Y Zomaya. An dfficiency-boosttng client selection scheme for federated learning with faimess guarantee. IEEE Transactions on Parallel and Distributed Systems, 32(7):1552-1564 2020.
[48] Yae Jee Cho, Jianyu Wang, and Gauri Joshi. Client selection in federated learning: Convergence analysis and power-of-choice selection strategics. arXiv preprint arXiv:2010.01243, 2020.
[49] Tianhao Wang, Johannes Rausch, Ce Zhang, Ruoxi Jia, and Dawn Song. A principled approach to data valuation for federated learning. In Federated Learning, pages 153-167. 2020.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them?
[Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as URL.)? [Yes] See the supplemental material.
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (c.g., with respect to the random seed after running experiments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're re using/curating? [Yes]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [Yes]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable?
[N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "IDjkOk-9nSw", "reviewer": "Reviewer_2byC", "summary": "In this work, the authors propose a new method for efficient vertical FL. Specifically, the authors propose to find a small subset of clients whose features could be used to learn a model that yields high accuracy with significantly less amount of time using 1. Mutual Information to evaluate how informative a selected subset of features is, 2. a group testing method. Empirical results show that the proposed method is able to achieve comparable/stronger performance than regular training with significantly less time.", "questions": "Questions are listed in the previous section.", "limitations": "Limitations are listed in weakness section.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n- Overall this paper is well written with clear intuitions on how each component of the algorithm is designed. The novel idea of using mutual information with homomorphic encryption is interesting and sensible.\n- The authors evaluate on a thorough set of datasets and the empirical results show that the proposed method is strong compared to prior baselines.\n\nWeakness:\n- The authors propose a group testing method to select the best k clients. However, this method could be potentially costly. Could the authors provide any justification how the number of tests $T$ affects the convergence of finding best top-k clients? Moreover, the experiments in this work focus on cases where the number of clients is small (<5). Could this method generalize to large scale federated network where the number of partitions is large?\n- For all the datasets evaluated in this work, the authors use a logistic regression model to evaluate the proposed method. Could the authors provide evaluations of VF-PS on more sophisticated ML task, e.g. non convex loss?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "9BAXgNNFuid", "reviewer": "Reviewer_63Y2", "summary": "The authors studies the problem of participant selection in vertical federated learning, and model it with a mutual information-based view. The first technical contribution is VF-MINE, a vertically federated mutual information estimator. The second contribution is to further optimize VF-MINE and get a group testing-based participant selection framework, VF-PS. Some experimental evaluations were conducted to show the performance of VF-PS.", "questions": "The paper seems to suggest that VS-PF is a once-and-for-all method. But what if the “good selection of participants” varies in different stages of training?", "limitations": "The authors have addressed the limitations that the mutual information may not be the best selection criterion. Beyond that, the authors may need to consider the social impact of inequality of contribution and reward between selected and unselected participants.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n+ The idea of boosting the efficiency of vertical federated learning with participant selection is novel and interesting.\n+ The Fagin-inspired optimization is novel.\n+ The analysis of security and the experimental results are good.\n\n\n**Weaknesses:**\n- Some parts of the algorithms are not clear and easy to follow. Please see my questions below. \n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["Discrimination / Bias / Fairness Concerns"]}, "extra_text": {}}, {"review_id": "-xRhDXi660s", "reviewer": "Reviewer_jzaC", "summary": "The paper studies the problem of client sampling in the context of Vertical FL, i.e., FL-PS, where each client corresponds to a feature subset and thus differs in their importance to the global model. Specifically, a mutual information (MI) based approach is used for importance evaluation. The Fagin algorithm and a so-called batched group testing scheme are employed to make the selection efficient. Security analysis is provided. Results of evaluation on various classification datasets show that the proposed framework is competitve to full-participation training with very low sampling overheads.  ", "questions": "- Is it possible that the kNN-based MI estimator is biased towards smaller local feature subsets with Euclidean distance?\n- In the Security Analysis, is the framework still secure when the leader participant is curious and seeks to reconstruct non-local features?\n- How are the groups for testing generated? How is the number of groups $T$ determined?", "limitations": "The methodology, in my understanding, is practically limited from two aspects: i) a globally aligned, complete instance space $\\mathcal{D}$, as mentioned above, and that ii) the MI-based design is only applicable to classification tasks, which is a common limitation for most VFL algorithms/frameworks though.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Client/feature subsets sampling in VFL is an intriguing problem under-explored in the field of FL.\n- The authors introduce multiple techniques, e.g., Fagin, group testing, batching, to make their MI-based sampling framework more practicaly feasible.\n- The empirical results are relatively comprehensive, covering different scale of data settings and multiple models.\n- Privacy protection is considered in the whole process.\n\nWeaknesses:\n- An identical instance space $\\mathcal{D}$ is assumed, which may not be the case for many VFL scenarios.\n- The complexity  and efficacy of group testing scheme is subject to how groups are generated. Random grouping over a multitude of clients can be problematic.\n- Some usage of symbols and terms seem to be too casual. E.g., \"# participants\", \"$NN_{k, y_q}$\", \"All-train\", etc.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept