A Coupled Design of Exploiting Record Similarity for Practical Vertical Federated Learning
Authors: Zhaomin Wu
Qinbin Li
Bingsheng He
Venue: NeurIPS 2022 Accept (2022)
Keywords: Vertical federated learning

Abstract: Federated learning is a learning paradigm to enable collaborative learning across different parties without revealing raw data. Notably, vertical federated learning (VFL), where parties share the same set of samples but only hold partial features, has a wide range of real-world applications. However, most existing studies in VFL disregard the "record linkage'' process. They design algorithms either assuming the data from different parties can be exactly linked or simply linking each record with its most similar neighboring record. These approaches may fail to capture the key features from other less similar records. Moreover, such improper linkage cannot be corrected by training since existing approaches provide no feedback on linkage during training. In this paper, we design a novel coupled training paradigm, FedSim, that integrates one-to-many linkage into the training process. Besides enabling VFL in many real-world applications with fuzzy identifiers, FedSim also achieves better performance in traditional VFL tasks. Moreover, we theoretically analyze the additional privacy risk incurred by sharing similarities. Our experiments on eight datasets with various similarity metrics show that FedSim outperforms other state-of-the-art baselines. The codes of FedSim are available at https://github.com/Xtra-Computing/FedSim.

A Coupled Design of Exploiting Record Similarity for Practical Vertical Federated Learning
Zhaomin Wu, Qinbin Li, Bingsheng He
National University of Singapore shhaomin.qinbi,.eeb.. http:/nnnnnnbbeooommnooteiitt @comp..uu.eduu
Abstract
Federated learning is learning paradigm enable collaborative learning across different parties without revealing raw data. Notably, vertical federated learning (VFL), where parties share the same set of samples but only hold partial features, has wide range of real-world applications. However, most existing studies in VFL disregard the "record linkage" process. They design algorithms either assuming the data from different parties can be exactly linked or simply linking each record with its most similar neighboring record. These approaches may fail to capture the key features from other less similar records. Moreover, such improper linkage cannot be corrected by training since existing approaches provide no feedback on linkage during training. In this paper, we design a novel coupled training paradigm, FedSim, that integrates one-to-many linkage into the training process. Besides enabling VFL in many real-world applications with fuzzy identifiers, FedSim also achieves better performance traditional VFL tasks. Morcover, we theoretically analyze the additional privacy risk incurred by sharing similarities. Our experiments on eight datasets with various similarity metrics show that FedSim outperforms other state-of- tfaee-of-theattt art baselines. The codes of FedSim available at /ettss//gitthb... com Xtra- Computing/FedS:
Introduction
Federated learning is a collaborative learning framework to train a model from distributed datasets with privacy guarantees. A commonly existing and widely studied scenario of federated learning is vertical federated learning [32
62 (VFL), where multiple parties sharing the same set of samples have different sets of features. We focus the setting where only one party holds the labels like
most of the studies 333 39 60). The party holding labels named primary party; the parties without labels are named secondary parties. In VFL, the features that exist multiple parties called common features. The vector of common features in a data record is called the identifier the record.
27 39 40 formulate VFL two separated processes: linkage and training. In the linkage process, the datasets on different parties are linked according to the identifiers. In the training process, these distributed but linked data records are trained by VFL algorithms. Specifically, in the linkage process existing studies, each data record is linked to data record with the exactly matched the most similar identifier (i.e., one-to-one linkage). Nonetheless, according our study on all the completed projects in German Record Linkage Center 4 (GRLC), only 27.3% of the record-linkage applications linked exact identifiers. The other projects rely fuzzy identifiers such as addresses, in which one-to-one linkage can seriously impair the accuracy of the VFL model for the following
Existing studies [22
reasons.
First, only linking the records with top similarity (i.e., one-to-one linkage) does not necessarily capture the key features, which can be demonstrated by two real-world applications. 1) Considering the VFL for price prediction between a real estate company and a house leasing company linked by
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Price distributioon by locations
Siriaely score of Commard & Compue &: Ticerism Wars'
40.00
picc 201
PM price on dM
Comereed Concuer Knno wuh
39.90
1M
commadd Coniue (191)
Conseen
Cammand & Cansuan ked hart Conmanen Chalegg
Coneeedo
Conmaade Sind Daadey
Conmrndee andern stuuk the cance
39.92
corsecel Horpe
Comber Masion
Conara
116.52 116.84
(i) Housing prices by geolocations Beijing
(ii) Games with similar titles to "Command & Conquer 3: Tiberium
Wars"
Figure 1: Examples of real-world record linkage (house and game dataset in the experiments)
GPS locations of houses, as shown in Figure I(i) the closest house to house A (purple) may not be in the same price level as A. 2) Considering the VFL between steam games and IGN games linked by the game titles, as shown in Figure I(ii] linking not only the exactly matched game but also other games in the same series intuitively benefits game recommendation tasks. Even in applications where identifiers can be exactly matched (e.g., identifiers are ID), some features are missing or biased, one-to-one linkage prevents the training process from enhancing these features from other similar records. These applications commonly exist in practice according to our investigation. An opposite extreme case is to link each record with all the records in another party (one-to-all linkage), which keeps all the information but too expensive for both linkage and training. Therefore, a one-to-many linkage approach is needed
balance between efficiency and performance.
Second, separating the linkage from the training also harms the performance of VFL. In existing VFL approaches, since the linkage process cannot obtain any feedback from the training process, the linkage is conducted with the goal of finding true-matched pairs of records instead of finding the pairs that reduce the training loss. Hence, an integrated VFL framework that conducts one-to-many linkage under the guide of training is desired.
To address these two drawbacks, we link each data record to the records with top-K similar identifiers in another party and design coupled framework of linkage and training. Our main challenge is to effectively exploit these linked pairs and their similarities to boost the performance of VFL. To tackle camilarity-basedd coupled VFL framework FedSim on the top of SplitNN [56] which is a VFL algorithm for neural networks. In FedSim, similarity is dominant feature that determines the order and the weight of each pair of linked records. The weights (i.c., impact) of similarities are also adjusted in each training iteration. After the training, each similarity is mapped to weight based on its contribution to reducing the loss.
this challenge, we propose
Furthermore, to address the additional data privacy issue incurred by FedSim, we first add Gaussian noise to the similarities and analyze the privacy of FedSim under differential privacy [15]. Our analysis suggests that differential privacy that provides rigorous guarantees for every individual record regardless of the type of attack is impractical for FedSim. As an alternative, we propose an intuitive greedy attack to infer identifiers from similarities, followed by theoretical bound of the probability of its success.
Our main contributions can be summarized below. 1) We propose a novel asymmetric training paradigm, named FedSim, and a training-free metric to estimate the improvement of FedSim on baseline approaches; 2) we analyze the privacy of FedSim under differential privacy: 3) we propose greedy attack on FedSim and the corresponding defense method that can theoretically bound the success rate of this attack; 4) we conduct extensive experiments on three synthetic datasets and five real-world datasets, which indicates that FedSim outperforms state-of-the-ar baselines.
2 Preliminaries
Privacy-Preserving Record I Linkage. Privacy-preserving record linkage (PPRL) (55) aims to link the data records from two parties that refer to the same sample without revealing real identifiers. Most
2

---

Top 15im
e 9)
4 Top1 nearest now nneightor of of" Exact di Execcly matched records of"
Aggregiete Ai
predictions
Bf ())
SplitMNN
SpliewN
di 8/ (xr"))))
Local model g
Local model 0%
Local model 0%+
Each record in
FeatureSim
d'
Each record
records
Data records
Data records Su
af
in
neighhers of of
Primary Party
Secondary Parties
neighbors
K nearest
X sinitarttess
(d) AvgSim
Forward and back- pack-propagation of SplitNN
(ii) Structure of baseline models
Figure 2: Structure of SplitNN and baseline VFL models
consist of three main steps: blocking, comparison, and classification. First, in the blocking step, data records that are unlikely to linked are pruned to reduce the number of comparisons. Then, in the comparison step, similarity between identifiers is computed for each candidate pair of data records. Finally, in classification, each candidate pair is classified as "matches" or "non-matches" which is usually done by manually set threshold. Notably, although blocking ensures sample scalability, party scalability remains challenge in PPRL. Therefore, we focus on linkage and training process of two parties and provide an extension to multiple parties in this paper.
PPRL methods 28 53 55
Although the training of FedSim does not rely on any specific PPRL framework, our privacy analysis is based on state-of-the-as PPRL framework FEDERAL (29 Coordinated by an coonest-but-curion server, FEDERAL calculates similarities by comparing Bloom filters (55) generated from identifiers. It is theoretically guaranteed that all the identifiers generate Bloom filters containing similar numbers of ones; thus, attackers are hard to distinguish identifiers based on Bloom filters. More detailed background of FEDERAL is introduced in Appendix !
Vertical Federated Learning. In this paragraph, we present a formal definition of VFL between two parties. Suppose two parties P and S want to cooperate with each other to train machine learning model. P is the primary party holding m samples and labels (x", .y} & {x y4 ) S is the secondary party holding samples x & {x;*) } which can also benefit the machine learning task. In order to perform linkage, we assume there are some common features between {x." )m and {-; ( in Fi i.c., {x." )m = [df", k J: k
[ J = {d) 1.5 Ji=1 where ky"", A, are common features used for linkage and df d$ are remaining features used for training with dimension (p. ls. We denote d & {d] Lm
1i=1, d & {d. } for simplicity. Our goal is to enable party P to exploit x
to train model that minimizes the global loss. Formally, aim to optimize the following formula:
T min m
1U(00=p,x*)) w) + AΩ(O)
where L(-) is the loss function, J(-) is the VFL model, and AQ(() is the regularization term
SplitNN. Most vertical federated learning algorithms only support simple models like logistic regression 25 which are ineligible to handle many real-world applications. Therefore, we adopt SplitNN (56) which is a popular and state-of-the- of-thc-rrt VFL algorithm that supports neural networks. The main idea of SplitNN is to split a model into multiple parties and conduct training by transferring gradients and intermediate outputs across parties. As shown in Figure 20) global model split into
an aggregation model 6aar and H local models 8P, {88=|v |u [1. H 1]}, where H is the number of parties. In each iteration, the outputs of local models are calculated by forward propagation and sent to the primary party Po which holds the labels. After concatenating the outputs of local models, P continues forward propagation to derive the final prediction ý and the loss Then, performs back- proppprppaatiion until the input of the aggregation model. The gradients w.r.t. the outputs of each local model are calculated and sent to the corresponding secondary party. Finally, all H parties finish back- proppaaatttiinn with the gradients.
3

---

3 Baseline Approaches
By extensively reviewing the existing VFL approaches, we find that all the existing approaches only use exactly matched (Exact) or most similar (Top1Sim) pairs of data records in the training. We denote these approaches that separate the linkage and training and as separated approaches. According to our detailed study in Appendix [D] only 27.3% of the record-linkage applications in GRLC based on exact identifiers are suitable for these approaches. To design a coupled approach that effectively exploits linkage information, we analyze the main drawback of existing approaches and some baseline coupled frameworks.
a.b)) These baseline separated approaches that only link exactly matched or most similar pairs neglect information of less similar but useful pairs, resulting in poor performance of VFL model in many real applications such as those in GRLC.
Exact 7 18 26 35
36 59, 60//Top 12 27
39
40). (Figure 2
AvgSim. (Figure 2 d)) We propose AvgSim as a baseline coupled approach that considers multiple pairs of records. Specifically, each data record in x. party P is linked with its K most similar data records in party S. The prediction of x. is an average of prediction when linking xf with its K nearest 2... Though considering more pairs, AvgSim overemphasizes the pairs with medium similarities, leading to redundant noise added to the model. Unaware of the similarity of each pair, the model is unable to filter out this redundant noise.
FeatureSim. (Figure 2(i]e)) We propose FeatureSim as a coupled baseline approach that adopts similarities to the training. Each of in party P is linked with its K most similar data records in party S, and the similarity between each pair is appended to the record. Nonetheless, similarity, which contains critical linkage information, is treated equally to other features. This drawback limits the ability of VFL models to extract information from similarities, thus affecting the overall performance. Such an impact can be significant according to our experiments.
Based on the above analyses, we clearly observe that the record linkage should be coupled with the design of VFL by taking advantage of record similarity not only during the linkage procedure but also during the training procedure. Meanwhile, according to the analysis on AvgSim, more advanced models are needed to merge the outputs of linked pairs with K largest similarities. These analyses motivate our design of FedSim as a coupled framework of linkage and training.
4 Our Approach: FedSim
Our approach has two components: soft linkage and similarity-based VFL. In soft linkage, after finding top-K similar pairs by existing PPRL methods, the server preprocesses the similarities by normalization and Gaussian noise perturbation. The scale of noise can be determined by constant bound of the attacker's success rate, which is further analyzed in Section 5 Then, the aligning information and aligned similarities are sent to party P or S which will align the data records accordingly. In similarity- based VFL, we design a model (as shown in F) by adding additional components around SplitNN to effectively exploit similarities. Finally, this model, taking the aligned data records and aligned similarities as input, is trained by back-propagation like SplitNN, Although we use SplitNN as an example, the idea of soft linkage and similarity- based learning can be extended to other federated learning algorithms.
4.1 Soft Linkage
Soft linkage, following traditional PPRL in "blocking" and "comparison" steps. directly outputs the similarities with normalization and noise addition without performing the "classification" step. Same as many existing PPRL approaches (28-30 54), we assume there exists an honest-but-curious server coordinating the linkage process. Specifically, soft linkage, taking k" and k as input, outputs the alignment information (i.e., indices that indicate the order of records) and similarities. First, each sample x!" in party P is linked with samples containing K most similar identifiers in party S. The similarities between identifiers of these linked pairs are calculated by a PPRL protocol. To fully utilize S for each sample or,", K should be large enough to ensure that all the pairs which may benefit the model are included. Notably, setting a large K hardly leads to overfitting according to our experiments in Appendix F22 Second, the server calculates the raw similarities Pij between these

---

linked pairs; the raw similarity Pıj is defined as normalized negative distance. Formally,
Ps - -iist(ke' k
-
(1)
ao
where Mo and og are the mean and standard variance of all negative distances dkf k2). To prevent the attacker from guessing the vectors bo or kef from similarities (further discussed in Section 5) we add Gaussian noise of scale a to each Pij- Formally, for Vi E [1, ml, Vj [1, []
Sij = Pij + o(0,
For simplicity, we denote s; _ {ssg and s - {
After the similarities are calculated, the server directly sends the similarities to party P and sends the aligning information (i.e., indices that indicate orders) to both parties. Finally, parties P and align their samples or similarities according to the aligning information to ensure that each =f". x and s; refer to the same sample.
4.2 Similarity-Basee VFL
The training process is summarized in Algo- rithm D and the model structure is shown in Fig- ure As discussed in Section 7 FedSim is
Matrix
designed on top of SplitNN [56]. which makes
Merge Gate
Merge model (ChN)) d
Functions
Outputs
preliminary predictions o; (with Im dimensions) for each d, and its K neighbors di (lines 4-7). Specifically, we add three gates (weight gate, merge gate, sort gate) around SplitNN and train the whole model similarly to SplitNN, The main function of these gates is to effectively exploit similarities 8; to merge the preliminary outputs o, into the final prediction J.
SplrNN
(a)
Sort Gate
Multiply Sort
(R D
Wy
0,
(R kx)
Extension to multiple parties
Weight Gate
Aggregnete model
SplitNN
Similritty model gain
Local model 6
Output of T Party
Output of occa model
Weight Gate. One straightforward idea is that more similar pairs of samples contribute more to the performance. Thus, the rows in o, with higher similarities should be granted a larger weight. Directly multiplying the similarities to o; inappropriate since the values of similar- ities do not directly represent the importance of records. Therefore, weight gate, we use similarity model, a simple neural network with mie-iimensional input and one-dimensional out- put, to non-linearly map the similarities weights w, which indicates the importance of the record (line 8). Then, the weighted outputs are calculated as a matrix multiplication (line 9).
(K
similanties
Duplicated each record in
Party S.
T
Soft Linkage
Figure 3: Model structure of FedSim
Merge Gate. The merge gate contains merge model to aggregate the information in of (line 11). For tasks that only require a linear aggregation, setting the merge model as an "average over rows" of of is sufficient to obtain promising result. However, for tasks that require non-linear aggregation, a neural network required to be deployed as a merge model. In this case, although the merge model can be implemented by multi-layer perceptron (MLP) which takes flattened of as input, such an approach usually lcads to over-fitting due to large number of parameters. Meanwhile, the flatten operation causes information loss because the merge model is unaware of which K features in the flattened of correspond to the same output feature in o'. Considering these two factors, we set the merge model as 2D convolutional neural network (CNN) with kernel size Keone X 1. o', containing K output vectors with Im dimensions, is regarded as 2D input of size K x Im for the CNN merge gate. Then, the merge gate effectively merges these output vectors with close similarities.
Sort Gate, The sort gate is an optional but sometimes crucial module depending on the property of the chosen merge model. For merge models that are insensitive to the order of of (e.g.. averaging over rows), sorting is not needed because the order does not affect the output of the merge model. However, for merge models that are sensitive to the order of of (c.g., neural networks), inconsistent
5

---

order of features can incur irregular sharp gradients which makes the merge model hard to converge. Thus. of should be sorted by similarities (line 10) to stabilize the updates on the merge model. Also, grouping the pairs with close similarities together helps the merge gate effectively aggregate the information.
Algorithm 1: Training Process of FedSim
Input :Aligned datasets and labels d d y; similarities s; number of similar samples K; number of epochs number samples m in party P:
Output :SplitNN parameter 05" 0g ,00ss; similarity model parameter 05 merge model parameter 05" // FP: forward propagation; EP: back-propagation
Initialize 06 06, 00 ,00 0000 for f. 4 to do
for i +- to m do Party S loads i-th batch d from =
calculates cf = f(f: d and sends cf to party P: Party P loads i-th sample df from df:
// Local model FP
receives c/ from party S and calculates o, f(0]: ; of, df"); loads similarities s; from and calculates calculates weighted outputs of diag(w. (i.o: sorts the of o by (or w:):
// SplitNN FP // Similarity model FP
f(0t ;s:);
// Sort gate // Merge model FP
11
calculates J = f(0r" o with sorted o'; calculates gradients gf Lih,, 8s), gtt oetm L(h,, 8c). gl" = Vap Lih. w)).
12
gi = c I vi) and sends gi to party S:
// Merge and similarity model BP
13
updates parameters
0141 0.30 0.0.00.0 . = 0. ng 0 = 0p0m neg tim 0.41 0," -mgg""
14
Party S receives gi from party P and continues calculating gradients gi Vog gi:
15
updates parameters 0f+ 0 mmg.:
// Local model BP
The whole model with SplitNN and three gates performs back-propagation by transferring gradients like SplitNN (lines 12, 14). After gradients are calculated, all the parameters are updated by gradient descent (lines 13, 15). According to the experiment in Appendix F.4 FedSim incurs longer but acceptable training time compared to Exact and Top1Sim. During the inference, for each data record the primary party, K most similar data records in secondary parties are linked. These linked data records are fed into the FedSim model derive the final prediction. More insights into the weight gate and merge gate are elaborated by visualization Appendix F.3
4.3 Improvement Estimation
60) in VFL, we mainly focus on the two-party setting which has many real-world applica- tions (e.g., bank and fintech company 600). Meanwhile, we also support an extension to the multiple-pan party setting as elaborated in Appendix C
Similar many existing studies 7 22
Similarities (scaled to [0.1])
Redundant information
In this subsection, we propose data- bata-linkage-based metric to es- timate the improvement of FedSim over baselines (i.e., AvgSim, Top1 Exact) without training. Calculating all the similarities between z!" and every { we can plot the sorted similarities of each pair as a curve. For example, Figure 4 displays the curve of AvgSim with top-K neighboring records. The performance of these baselines is impeded by two main factors: 1) lost informa- tion some pairs of samples with small similarities are neglected. For example, in Figure 4 the samples above the threshold are neglected; 2) redundant information some pairs of samples with smaller similarities are treated equally to those pairs with large similarities. For example, Figure some samples below the threshold with medium similarities are overestimated. To jointly estimate these two factors, we intuitively assume the information contained
Threshold
Figure 4: Estimated improve- ment of FedSim AvgSim with top-K neighbors

---

in each pair is proportional to its similarity; then, the lost information and the redundant information can be estimated by the similarities. We formally define the metric as follows.
Definition 1. Given a data linkage between x" & {oā li=1 and xa & {az in 1j=1.for for a data record x; in P. VFL algorithm F divide the indices of n records in S into matches and non-matches, denoted as Smatcee and Smon matches. respectively. Denote 8ij as the scaled similarity between x; and az, the improvement of FedSim F for sf. is defined (F) A LjeSmmtt (1 86)) + EjESmmmannnt the overall improvement of FedSim on F is defined as A E (F).
As shown in Figure 5( this metric can effectively estimate the improvement of FedSim compared with the other baselines in the experiments.
5
Privacy
The shared information FedSim includes:
(I) similarities shared to party P:
(2) intermediate results in SplitNN shared to party P:
intermediate results in PPRL shared to the server.
The intermediate results in SplitNN and PPRL respectively studied in [57] and 29] (see Section 2 for details), both of which are orthogonal to this paper. Therefore, we mainly study the privacy risk caused by similarities s.
5.1 Differential Privacy
According to Equation| and 2 each similarity sij is calculated from k."" and k.f. We formally define this procedure as G below.
Procedure G: Take kS as the input. Each k. E k is linked to multiple k-f k5; the similarities between kf and k. are calculated by 8ij = || -ff- 112 NO, o²), where N(0, o²) refers to Gaussian distribution with variance o², Output the similarities s.
-3e /VTS.. Suppose the size of k" is n 8. If Theorem 1. Suppose E > and 0 < 8 < 1/2 - e 30
procedure G is (c, DD- then a 2 Ag/ Ag/V2 /2e, where Ag = n max
1+ 88
d
The proof of Theorem 1 is included in Appendix A.1
As observed from Theorem 1 the noise scale a increases linearly by n. The large scale of noise derived from differential privacy would seriously affect the performance of FedSim. Hence, further analyze the privacy risk of FedSim against
specific attacks.
5.2 Privacy Against Greedy Attacks
In this subsection, our analysis focuses on greedy attacker who first predicts the most likely distance from each 8ij and then predicts the most likely Bloom filter from the predicted distance. Assuming the attacker already knows the scaling parameters μoo do. we formulate the attack method as follows.
Attack Method. To obtain k.S as prediction of k:y, the attacker 1) predicts set of normalized negative distances P.y (i E Q) from Sij (i Q). respectively, by maximum a posteriori (MAP) estimation with Gaussian prior (0, 1), Pij arg max p.y P(Pt) sty): 2) calculates each distance úij by scaling back ò.g with parameters μoo og. i.c., úij = -ooPi - P4 (i Q); 3) uniformly guesses k-s from all possible values satisfying Vi Q, dist(k"", (.lkKK",... k5)) = uyg which have the same probability of being the real k.y.
Besides the greedy attack, advanced attackers may predict through the probability distribution of distances rather than predict through the most likely distance. Some attackers may even know some side information like the prior distribution of k.5 and employ this side information to launch attacks.
These advanced attacks are further discussed in Appendix B
7

---

Although not satisfying differential privacy, we prove that the success probability of greedy attacks is always bounded by a small constant related to og and regardless of the choice of Q if an attacker follows the attack method (Theorem 2
Theorem 2. Given a finite set of perturbed similarities Sij (i E Q) between [Q] bloom-filters
k. E Q) in party P and one fittrr k in party S. if an attacker knows the scaling parameters No, To and follows the procedure of the attack method, the probability of the attacker's 's predicted Bloom filter kif equaling the real Bloom filter hi is bounded by constant T. Formally,
Pr 1 = -k3 (ssyle E Q), (k, Q}. No. oo. A ST
where constant T = erf
vo'tI ): crf(-) the error function, ie., erf(x) -F do e- dt; event 2v/oro
A: attackers follow the given attack method.
The proof of Theorem 2 is included in Appendix A From Theorem 2 we find two factors that affect the attacker's success rate: 1) noise added to the similarity (Ø); 2) standard variance of Bloom filters (oo). Among these factors, 0g determines the lower bound of the success rate because v0² + 1/ < 1/(22/20)) and a determines how close success rates FedSim can guarantee compared to the lower bound. When a is large enough, increasing o helps little with reducing the success rate. Therefore, to ensure the good privacy of FedSim, we should first guarantee a large enough variance among the Bloom filters and then add a moderate noise to the similarities. Taking house dataset (see Section (. as an example where μıo -6223.77 78, ap = 21178. Letting 2.96 x 10 implies that there is almost
5 = 1005 no differential privacy guarantce at all. Nonetheless, the attacking success rate T = 1.94 x 10-5 suggests that the privacy risk from certain attacks is very low. Considering the 19479 samples in the training set of party S, only 0.378 (smaller than one) Bloom filters are expected to be disclosed.
0.4, the differential privacy parameter
Experiment
6.1 Experimental Setup
Dataset. We evaluate FedSim on three synthetic datasets (sklearn 10], frog 13] boone, 14]
and five real-world datasets (house [ [4), taxi [8] 52), hdb [23 45 game [11 24 and company 12).. The details (c.g. dimension of identifiers) of these datasets are summarized in Appendix E For each real-world dataset, we collect two public datasets from different real-world parties and conduct VFL on both public datasets. For each synthetic dataset, we first create global dataset by generating with sklearn API [10] (sklearn) collecting from public (frog, boone). Then, we randomly select some features as common features and randomly divide the remaining features equally to both parties. Common features not used in training for all methods except Combine. To simulate the real-world applications, for synthetic datasets, we also add different scales o.f of Gaussian noise to the common features. Specifically, for each identifier v,, the perturbed identifier v = v, + (o I) will be used for linkage. For datasets with numeric identifiers (house, taxi, hdb, syn boone, frog), Euclidean distance is adopted to calculate similarities. For game dataset, Levenshtein distance is adopted to calculate similarities. For company dataset, we first generate Bloom filters from strings following [29]. then calculate similarities based on Hamming distances.
Training. Similarity model is multi-layer perceptron (MLP) with one hidden layer. The merge model contains a 2D convolutional layer with keone x kernel followed by a dropout layer and an MIP with one hidden layer. Both the local model and aggregate model in SplitNN are ML.s with one hidden layer. We adopt LAMB [63]. the state-of-ther art large-batch optimizer, to train all the models. Each dataset is split into training, validation, and test sets by 7:1:2. We run each algorithm five times and report the mean and standard variance (range is reported instead in figures) of performance on the test set. We present root mean square error (RMSE) or R-squared value (IR²) for regression tasks and accuracy for classification tasks. The choices of hyperparameters are introduced in Appendix B
We compare FedSim with nine baselines in our experiments. Besides the four baselines (Exact, ToplSim, AvgSim, FeatureSim) introduced in Section 3 the remaining baselines include: 1) Solo: only dataset d is trained; 2) Combine: [d. .d$] is trained (only applicable for synthetic datasets); 3) FedSim-MI.P the CNN in FedSim is changed to an MIP with a similar number of parameters. 4) FedSim w/o sort: FedSim without sorting gate. 5) FedSim w/o weight: FedSim
Baselines.
8

---

Table 1: Performance real-world datasets
house (numeric)
bike (numeric)
hdb (numeric)
game (string) A 1.14
company (string)
Algorithms
A 34.05
Á 14.26
A 20.69
A 10.50
Solo
58.3120.28
272.83+1.50
29.75:0.15
83.27=0.225 2.9%%
42.67=0.66
Exact
89,25=0. 12%
44,44+1.99
Top1Sim
58.54+0.35
256.19+1.39
31.56+0.21
92.71=0.08%%
42.84+0.77
FeatureSim
66.39+0.1 15
273.29+0.37
37.39+0.29
91.13=0.2300
39.24+1 1.80
AvgSim
51.9240.65
239.8540.40
34.1240.19
80.8420.11 14%
38.1920.99
FedSim (w/o Weight)
42.82+0.20
236.79+0.29
27.18+0.08
92.79=0. 133%%
41.00+1.19
FedSim (w/o Sort)
52.14+0.58
238.30+0.81
36.35+0.42
92.79=0. 10%
38. 18.2
FedSim (w/o CNN)
42.62+0.20
235.97+0.42
27.76+0.13
92.50=0. 12%
39. 1.36
FedSim
42.12+0.23
235.67=0027
27.13+0.06
92.88=0.1 11%
37.08=0.61
12
03
Performance synthetic datasets
(ii) Simop vs, perf.
Figure 5: Performance on synthetic datasets and the effectiveness of A A(ToplSim)
oouse
game
0.9
0.55
0.6
0.06
0.82
H0-3
10th
20
12P
10
25
15
12
Board coess rite
Soand success rite
Eound SICCESS rite
Bhand success
FedSim
BolSin
AwgSin
Raytu iii
Figure 6: Performance with different scale of noise on similarities
without weight gate (similarities directly regarded as weights). Notably, Exact is only evaluated on game and company because no exactly matched identifiers can be found on other datasets.
6.2 Performance
We evaluate the performance of FedSim on three synthetic datasets under differrnt def and five real-world datasets. The results of synthetic datasets are presented in Figure 50) from which two observations can be made. First, FedSim consistently has better or close performance compared all the baselines. Second, FedSim is more robust to the noise on the identifiers. For example, in frog, the accuracy of Top1 Sim drops 84% as oef 0.2, while the accuracy of FedSim remains 91%.
The results of real-world datasets are summarized in Table 1 We also calculate the estimated improvement ATTopl Sim. (denoted A for simplicity) according our proposed metric. The relationship between A(Topl Sim) and the relative improvement on Top1 is presented in Fig- ure 5 Three observations can be made from the results. First, FedSim consistently produces the best performance on all five datasets, while the baselines (especially the separated approaches) only have good performances on specific datasets. For example, ToplSim has close performance to FedSim on game, but fails on bike; AvgSim has close performance to FedSim on bike, but fails on game. Second, ATTopSSim indicating that the metric can be effectively used to estimate the improvement of FedSim without training. This also implies that FedSim can effectively reduce the effect of lost information and redundant information as expected. Third, comparing the performance of removing each component from FedSim, the sort gate makes the most significant contribution to the performance of FedSim by stabilizing the updates of the merge model. The improvement of the weight gate indicates that
positively correlated with real improvement on Top1

---

adjusting the distribution of similarities can slightly benefit the performance. Besides, CNN merge gate can also slightly improve on MLP merge gate by reducing overfitting.
As elaborated in Section D FedSim only boosts performance on the datasets satisfying a widely held assumption: the similarity between identifiers is related to the similarity between data records. Our experiments in Appendix [.6 indicate that FedSim has close (small K) or lower (large K) performance compared baselines on synthetic dataset with independent identifiers.
6.3 Privacy
In this subsection, to study how additional noise on similarities affects the performance FedSim, we conduct experiments five real-world datasets (the result of company is included in Appendix F.T due to page limit). Specifically, string or numeric identifiers are converted to Bloom filters according to [29] The Hamming distances between Bloom filters used calculate raw similarities. Then, given an acceptable success rate т, a noise scale a is calculated according to Theorem 2 Finally, Gaussian noise with scale is added the raw similarities according to Equation - The results are presented in Figure 0 Exact is not evaluated since few Bloom filters have exactly the same bits. From Figure 6 we observe that FedSim robust to the noise on similarities; therefore, the attacking success rate can be reduced to [10-4 10 10-$1 without evident performance loss. Notably, the performance when T is not necessarily the same as the performance in Section 6.2 since similarities are calculated based on different distances.
7 Related Work
in VFL focus on training and simply assumes record linkage has been done (i.e., the implicit exact linkage on record ID), which is impractical since most real-world federated datasets are unlinked. Some approaches exactly link the identifiers by exact PPRL 7 or private set intersection (PSI) 7 36 60). Nonetheless, these approaches incur performance loss of VFL and are also impractical since the common features of many real-world federated datasets cannot be exactly linked (e.g. GPS location).
Most studies 18
26
37
50
56
61
22 greedily links the most similar identifiers in PPRL, which negatively impacts performance since some beneficial pairs with relatively low similarity may be neglected. [39, 40) explore the impact of record linkage on the performance of VFL, which also adopted by (27). However, all of them focus only on the most similar identifiers and assume there is a one-to-one mapping between the data records of two parties, which is not always true in practice.
Current VFL frameworks support various machine learning models including linear regression [7,, logistic regression (25), support vector machine (3), gradient boosting decision trees 77 60) FDML [26] supports neural networks but it requires all the parties to hold labels. SplitNN [56] focuses on neural networks and provides new idea of collaborative learning where the model is split and held by multiple parties. Since we study the scenario where only one party holds the labels and want to support commonly used neural networks, build FedSim on top of SplitNN.
8 Conclusion
In this paper, we propose FedSim, novel VFL framework based similarities to boost the performance of VFL by directly utilizing the similarities calculated in PPRL and skipping the classification process. We also theoretically analyze the additional privacy risk introduced by sharing similarities and provide a bound for the success rate of an intuitive attack. In our experiment, FedSim consistently outperforms all the baselines.
Acknowledgements
This research is supported by the National Research Foundation, Singapore under its AI Singapore Programme (AISG Award No: AISG2-RP-2020-011 Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not reflect the views of National Research Foundation, Singapore. Qinbin is also in part supported by a Google PhD Fellowship.
10

---

References
[1] Airbnb. Airbnb prices. http:://hnsideeirrbbb. wwwp://bw...oootttttteeeeeeeeeee seeet--the-dat.hhhee 2019.
[2] Manfred Antoni and Arne Bethmann. Pass-befragungssdlen verknüifft mit administrativen daten des iab, 2014.
[3] Manfred Antoni, Ernst Maug, and Stefan Obernberger. Private equity and human capital risk. Journal of Financial Economics, 133(3))334-577, 2019.
[4] Manfred Antoni and Rainer Schnell. The past, present and future of the german record linkage center (grlc). Jahrbücchrr für Nationalökonomic und Statistik, 239(2):11--331, 2019.
[5] Borja Balle and Yu-Xiang Wang. Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. In International Conference on Machine Leamning pages 394-403. PMLR, 2018.
[6] Thierry Bertin- Daniel PW Ellis, Brian Whitman, and Paul Lamere. The million song dataset, 2011.
[7] Kewei Cheng, Tao Fan, Yilun Jin, Yang Liu, Tianjian Chen, and Qiang Yang. Secureboost: A lossless federated learning framework. arXiv, 2019.
[8] CitiBike. Citi bike system data.
http::/wwww.aaeee...oo.oooeeeeea 2016.
[9] Michela Coppola, Bettina Lamla, et al. Saving and old age provision in germany (save). design and enhancements. Schmollers Jahrbuch, 133(1):109-16, 2013.
[10] David Cournapeau. Sklearn API: make maaeeclassiffiation 2021.
[11] Nik Davis. Steam store games (clean dataset). http::/wwww...gll...coooo/o
steam store- games 2019.
[12] Michaël Defferrard, Kirell Benzi, Pierre Vandergheynst, and Xavier Bresson. Fma: A dataset for music analysis. arXiv, 2016.
[13] Dheeru Dua and Casey Graff. UCI machine learning repository, 2017.
[14] Dheeru Dua and Casey Graff. UCI machine learning repository, 2017.
[15] Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations differential privacy, Founda- tions and Trends@ in Theoretical Computer Science, 9(3-4):211-40)) 2014.
[16] Johanna Eberle and Michael Weinhardt. Record linkage of the linked employer-emplowe survey of the socio-cconomic panel study (soep-Iee) and the establishment history panel (bhp). German Record Linkage Center Working Paper Series, 2016.
[17] Siwei Feng and Han Yu. Multi-participant multi-class vertical federated learning. arXiv, 2020.
[18] Fangcheng Fu, Yingxia Shao, Lele Yu, Jiawei Jiang, Huanran Xue, Yangyu Tao, and Bin Cui. VP2 Very fast vertical federated gradient boosting for cross-enterprise learning. In SIGMOD, 2021.
[19] Daniel Fuß, Jutta von Maurice, and Hans- Günther Roßbach. A unique research data infrastrue- ture for educational research and beyond: The national educational panel study. Jahrbücher für Nationalökonomie und Statistik, 236(4):517-528, 2016.
[20] Tobias Gramlich. strokes'-record -record linkage der schlaganfälle in hessen 2007-2010 (strokes-record linkage of stroke cases hesse 2007-2010). Available at SSRN 3549212, 2014.
[21] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
[22] Stephen Hardy, Wilko Henecka, Hamish Ivey-Law, Richard Nock, Giorgio Patrini, and et al. Private federated learning on vertically partitioned data via entity resolution and additively homomorphic encryption. arXiv, 2017.

---

[23] Singapore HDB. Resale flat prices in Singapore.
httpe://aata.goossgaaaaaa
resale-flat prices, flat--riceee 2018.
[24]
Trung Hoang. Video game dataset. rawg- game- dataset 2020.
https: wwwg://wwww.......co.o /
[25]
Yaochen Hu, Peng Liu, Linglong Kong, and Di Niu. Learning privately over distributed features: An admm sharing approach. arXiv, 2019.
[26] Yaochen Hu, Di Niu, Jianming Yang. and Shengping Zhou. Fdml: A collaborative machine learning framework for distributed features. In KDDD, 2019.
[27] Yan Kang, Yang Liu, and Tianjian Chen. Fedmvt: Semi-supervised vertical federated learning with multiview training. arXiv, 2020.
[28] Alexandros Karakasidis, Georgia Koloniari, and Vassilios S Verykios. Scalable blocking for privacy preserving record linkage. In KDD, 2015.
[29] Dimitrios Karapiperis, Aris Ahoulalas-Divanie and Vassilios S Verykios. Federal: A framework for distance-aware privacy-preserving record linkage. TKDE, 2017.
[30] Dimitrios Karapiperis and Vassilios S Verykios. An Ish-based blocking approach with homomorphic matching technique for preaeccire record linkage. TKDE, 2014.
[31] Martin Kroh, Simon Kühne, Jan Goebel, and Friederike Preu. The 2013 iab-soep migration sample (ml): Sampling design and weighting adjustment. Technical report, SOEP Survey Papers, 2015.
[32] Qinbin Li, Zeyi Wen, Zhaomin Wu, Sixu Hu, Naibo Wang, Yuan Li, Xu Liu, and Bingsheng He. survey on federated learning systems: vision, hype and reality for data privacy and protection. TKDE, 2021.
[33] Yang Liu, Yan Kang, Chaoping Xing, Tianjian Chen, and Qiang Yang. A secure federated transfer learning framework. IEEE Intelligent Systems, 2020.
[34] Yang Liu, Yan Kang, Xinwei Zhang, Liping Li, Yong Cheng, Tianjian Chen, Mingyi Hong, and Qiang Yang. A communication efficient collaborative learning framework for distributed features. arXiv, 2019.
[35] Yang Liu, Yingting Liu, Zhijie Liu, Yuxuan Liang, Chuishi Meng, Junbo Zhang, and Yu Zheng. Federated forest. IEEE Transactions on Big Data, 2020.
[36] Yang Liu, Xiong Zhang, and Libin Wang. Asymmetrically vertical federated learning. arXiv, 2020.
[37] Xinjian Luo, Yuncheng Wu, Xiaokui Xiao, and Beng Chin Ooi. Feature inference attack on model predictions vertical federated learning. In ICDE, 2021.
[38] Kevin P Murphy. Conjugate bayesian analysis of the gaussian distribution, 2007.
[39] Richard Nock, Stephen Hardy, Wilko Henecka, Hamish Ivey-Law, and et al. The impact of record linkage on learning from feature partitioned data. In International Conference Machine Learning. PMLR, 2021.
[40] Richard Nock, Stephen Hardy, Wilko Henecka, Hamish Ivey-Law, Giorgio Patrini, Guillaume Smith, and Brian Thoree Entity resolution and federated learning get federated resolution. arXiv, 2018.
[41] Anja Perry and Beatrice Rammstedt. The research data center piaac at gesis. Jahrbücher für Nationalákonomie und Statistik, 236(5):581-593, 2016.
[42] Leif E Peterson. K-nearest neighbor. Scholarpedia, 4(2):1883, 2009.
[43] Zhongang Qi, Saeed Khorram, and Fuxin Li. Visualizing deep networks by optimizing with integrated gradients. In CVPR Workshops, volume 2, 2019.
12

---

[44] Qichen Qiu. Kaggle dataset: housing price in Beijing.
lianjia 2017.
[45] Salary.sg. Secondary school rankings in Singapore.
secondary-school----aki----- www.rraniing-222----------ee -utt--pss---------eeeee cut- 2020.
[46] Rory Sayres, Ankur Taly, Ehsan Rahimy, Katy Blumer, David Coz, Naama Hammel, Jonathan Krause, Arunachalam Narayanaswamy, Zahra Rastegar, Derek Wu, et al. Using a deep learn- ing algorithm and integrated gradients explanation to assist grading for diabetic retinopathy. Ophthalmology, 2019.
[47] U.S. Small Business Administration (SBA). Loan transactions between compa-
nies and banks in US. https://www.ksr wagg// com honn//attaeets//iloooroooogaaaat
should- loan- hete---oonnn---prroeeeeeeee sepproved-or-demieee 2019.
[48]
Christopher-Johamen Schild. Linking' orbis' company data with establishment data from the german federal employment agency. NO. WP-GRI.C-2016-02, 2016.
[49]
Christopher-Johanne Schild and Manfred Antoni. Linking survey data with administrative social security data-the project'interanee interactions between capabilities in work and private life'. German Record Linkage Center, Working Puper Series, No. WP- WP-GRLCC-001-022, 2014.
[50] Shreya Sharma, Chaoping Xing, and et al. Secure and efficient federated transfer learning. In 2019 JEEE International Conference on Big Data (Big Data), 2019.
[51] Mukund Sundararajan, Ankur Taly, and Qiqi Yan. Axiomatic attribution for deep networks, In ICML, 2017.
[53] Dinusha Vatsalan and Peter Christen. Scalable http://ww...uy..go///ttt////// databases. In CIKM, 2014.
[52] New York TLC. TLC trip record data. rle-trip-reccrd-datte page, 2016.
record linkage for multiple
[54] Dinusha Vatsalan and Peter Christen. Privacy-preserving matching of similar patients. Journal of biomedical informatics, 2016.
[55] Dinusha Vatsalan, Ziad Schili, Peter Christen, and Erhard Rahm. Privacy record linkage for big data: Current approaches and research challenges. In Handbook of Big Data Technologies. Springer, 2017.
[56] Pranceth Vepakomma, Otkrist Gupta, Tristan Swedish, and Ramesh Raskar. Split learning for health: Distributed deep learning without sharing raw patient data. arXiv, 2018.
[57] Praneeth Vepakomma, Abhishek Singh, Otkrist Gupta, and Ramesh Raskar, Nopeek: Informa- tion leakage reduction to share activations distributed deep learning. arXiv, 2020.
[58] Michael Weinhardt, Alexia Meyermann, Stefan Liebig, and Jürgen Schupp. The linked employer-employee study of the socio-economic panel (soep-lee); content, design and re- search potential. Jahrbücher für Nationalökonomie und Statistik, 237(5):457-467, 2017.
[59] Song WenJie and Shen Xuan. Vertical federated learning based on dfp and bígs. arXiv, 2021.
[60] Yuncheng Wu, Shaofeng Cai, Xiaokui Xiao, and al. Privacy preserving vertical federated learning for tree-based models. VLDB, 2020.
[61] Zhaomin Wu, Qinbin Li, and Bingsheng He. Practical vertical federated learning with unsuper- vised representation learning. IEEE Transactions on Big Data, 2022.
[62] Qiang Yang. Yang Liu, Tianjian Chen, and Yongxin Tong. Federated machine learning: Concept and applications. 7IST, 2019.
[63] Yang Jing Li, Sashank Reddi, Jonathan Hseu, Sanjiv Kumar, Srinadh Bhojanapalli, and al. Song. Large batch optimization for deep learning: Training bert in minutes. arXiv, 2019.
13

---

[64] Aakash Kishore Chotrani Zelalem Getahun, Agata. 7+ Million Company Dataset. https:// company-
www. . kaggle. ottpc///ccae//oooooaaaaaa////ere ottp:///aererraaoooooooooooooaaa
2019.
[65] Mingkai Zheng, Shan You, Lang Huang, Fei Wang, Chen Qian, and Chang Xu. Simmatch: Semi-supervised learning with similarity matching. In Proceedings of the IEEE/CVP Conference on Computer Vision and Pattern Recognition, pages 14471-14481, 2022.
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] See the last paragraph Section
(b) Did you describe the limitations of your work? [Yes] See Appendix
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See
Appendix H
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section 5
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix A
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes] The codes are included the supplementary materials. The data are all publicly available; the link or citations of data are presented in Appendix
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] All the details including data splits and hyperparameters are introduced in Section 6.1 Appendix
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] The variance is reported in all tables and figures.
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, cloud provider)? [Yes] See the "hardware" paragraph of Appendix E
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] See Section 6. and Appendix
(b) Did you mention the license of the assets? [Yes] See the "license" paragraph of
Appendix
(c) Did you include any assets either in the supplemental material URL? [Yes] Our codes are included in supplementary materials.
(d) Did you discuss whether and how consent was obtained from people whose data you 're using/curating? [Yes] See the "Consent of dataset" paragraph of Appendix H (e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [Yes] See the "Personally identifiable information" of Appendix H
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A] Our research is not related to human subjects.
(b) Did you deseribe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A] Our research not related to human subjects.
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A] Our research is not related to human subjects.
14


Reviews:
[{"review_id": "qZkpfsJO1vW", "reviewer": "Reviewer_gik3", "summary": "This paper describes a framework for enabling VFL while addressing records linkage as a part of the training process. \nThe authors motivated their work by applications where existing VFL record linkage solutions were insufficient. For instance, if the linking data include GPS coordinates or names it would make sense to perform fuzzy matching. Additionally, the authors buckled the trend when instead of dividing record linkage and training into separate phases they combined them into one coupled phase where the weight or top K similarities would also be discovered during training. \nEven through the paper is primary focuses on 2 parties VFL the authors also describe how to extend their framework to multiple parties.\n", "questions": "Can you describe how the presented work can be further improved? \nWhat are the potential privacy implications when choosing large K value for the number of soft linkages during training?", "limitations": "I believe the authors have sufficiently addressed the limitations of their work related to scalability and privacy.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper is well-written and addresses an important issue. It is well motivated and supported by strong results on multiple synthetic and real-world datasets. The authors attached source code and instructions on how to build the framework and how to run tests. So it appears that their work can be replicated.\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": ""}, "extra_text": {}}, {"review_id": "clAaUW6Aup4", "reviewer": "Reviewer_ddh8", "summary": "The paper proposes FedSim, a new VFL training paradigm. FedSim explicitly explores the similarity information between the non-matched pairs and couples the correspond module into SplitNN (an existing VFL training model). The authors also provide privacy guarantee to a greedy attack algorithm. Finally, they verify the effectiveness of their algorithm on synthetic and real datasets.", "questions": "I would like to see a **detailed** discussion of the limitations, application scope (beyond listing two positive examples) and comparison to existing approaches of FedSim. This will greatly benefit the practitioners. Say if two financial institutions want to vertically train a machine learning model, should they consider your algorithm or not and why?", "limitations": "The authors only point out a few extensions (e.g., generalization to multiple parties, other attack methods). ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n1. The paper is easy to follow: the motivation is sound, the flow is smooth and the presentation is clear.\n2. The paper makes solid contribution by witnessing the potential information loss in the process of exact-match record linkage, and coupling the similarity information with the existing SplitNN model to improve the performance of VFL. Overall this feels like a simple-but-effective idea to me and is the major factor that reflects my rating.\n\nWeaknesses:\n1. The author emphasize that 'non-matched pairs can also benefit VFL with a properly designed training method', and they see it as a 'counterintuitive' conclusion. While I agree that this is indeed a nice and novel observation, I would like to point out that in contrast to being 'counterintuitive', this feels most natural to me. Placing it in a broader context of machine learning, an analogy would be 'data-augmentation will benefit supervised learning'. I think the tone needs to be revised here --- it is ok to acknowledge that your approach is 'simple' --- this will actually serve as a plus if it is also 'effective'. \n2. Following the point above, while I believe that a specific type of data augmentation will be effective in **some** learning tasks, there **must** exist other scenarios where it won't work. Similarly, I don't think it is the case that FedSim **always** outperforms its counterparts. Sometimes exact-match is more favorable, for example, top-K record linkage based on the similarity of phone numbers does not make too much sense to me. The authors do **not** discuss the limitations of their approach at all, and specifically, the experiment results demonstrate that FedSim consistently beats other baselines in all **selected** tasks, which actually downgrades my overall rating of this paper --- I tend to believe that the experimental evaluations are 'crafted'.\n3. I also do not see enough discussions on the reliance of the training framework. Can the similarity-based module be easily incorporated into other VFL protocols (e.g., logistic regression based on homomorphic encryption)?", "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": "_NSBEaUxNWI", "reviewer": "Reviewer_S97P", "summary": "This paper introduces a novel FedSim approach which leverages the record similarity for soft linkage on top of the SplitNN. It is an improvement over the existing Vertical Federated Learning, which is mainly based on the Exact and Top1Sim. The paper also consider the privacy risk caused by similarity. The experimental results show the performance improvements of FedSim against some existing benchmarks. ", "questions": "Q1: There are many soft linkage research, i.e., matching pairs between different parties. Can you briefly explain what is the significance/novelty/difference between your approach and other approaches on record linkage?\n \nQ2: The merge gate is not clear; can you provide a formal description?\n\nQ3: How the privacy guarantee relates to differential privacy?\n\nQ4: Computationally, will the approach introduce additional cost?\n", "limitations": "No ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros: \n1. The problem is interesting and timely\n2. The idea is simple and the results demonstrate its power\n3. The paper is easy to read\n\nCons: \n1. Lack of theoretical analysis of the proposed method\n2. The privacy analysis seems to be weak; can it be linked to differential privacy? \n3. The experimental results are not convincing; lack of detailed ablation study. For instance, it will be interesting to know how different soft linkage approaches can help with the task. \n4. The computational complexity is not discussed (and comparing with other method) ", "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": "Og0Hc7y55hl", "reviewer": "Reviewer_W2Lk", "summary": "This paper proposes a framework for vertical federated learning (VFL), called FedSim. \n\nIn general, VFL contains two steps, the first being the record linkage, the second being the model learning. FedSim is based on the observation that existing methods separate these two steps and focus solely on the model learning step. For the record linkage step, existing works use simple exact/one-to-one matching, and thus fail to exploit information from non-matched entities. \n\nFedSim proposes a method to exploit similar records in VFL. It matches samples across parties according to similarity, and further uses the similarity information to adaptively fuse features from the other party. Further, a simple way to estimate the performance improvement is proposed, and a theoretically grounded method to ensure privacy is proposed. Experiments on several datasets show the effectiveness of FedSim. ", "questions": "1. How does a model learned by FedSim perform inference? Any additional procedures/overhead?\n\n2. I would like to see how FedSim performs on other datasets commonly used in VFL, e.g. Criteo and Avazu [4]. In these cases, no strong priors about indicative common features (e.g. longitude/latitude) exist. \n\n3. Please justify how the insights learned from FedSim differs from the insights learned from existing works on GNN and graph-based semi-supervised learning ([1-3]). Otherwise, you should tone down the claims in the Introduction. ", "limitations": "I don't see anything that raises ethical concerns. ", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Originality\nThe main idea of the paper is to use similar but not exactly matched samples to assist vertical federated learning. \n\n+ **Pros** The idea is somewhat new in VFL. The common practice of VFL is that training is only performed on exactly matched samples. \n\n- **Cons** The authors seem to be overclaiming on the originality and insights of the idea. The authors highlight the insight that \"non-matched pairs can also benefit VFL\" in line 68, Introduction, and regard it as 'counter-intuitive'. However, although the insight is indeed not explored in VFL, I would not consider the insight highly novel or counter-intuitive. Specifically, in the sense of general machine learning, the insight that \"similar but not the same samples can boost machine learning performance\" has been well recognized and exploited. For example, Graph Neural Networks (GNN) [1, 2] are perfect illustrations of this insight. The primary idea of graph neural networks is to aggregate features from neighboring nodes of the central node, which is basically using similar samples to improve feature learning for the central node. Furthermore, even though there may not be explicit links (e.g. friends in social networks, citations in academic networks), using general feature similarity to build implicit graphs is also a common idea. For example, [3] builds a nearest neighbor graph on latent features to facilitate deep semi-supervised learning. Therefore, the insight the authors claim has been known and used in a larger area and may not be \"counter-intuitive\" or \"new\". The authors indeed made a valid observation, but they should not over-claim. \n\n## Quality\nThe designed method to exploit record similarity contains a merge gate, a weight gate, and a sort gate. Similar but non-exactly matched samples are weighted by the sort gate and the weight gate to assist VFL. The authors also propose a method based on histogram to estimate performance gains. Further, the authors discuss the potential privacy leakage caused by the record similarity, and propose a method to protect data privacy with theoretical analysis. Experimental results show that FedSim outperforms simple baselines that utilize record similarity (Top1Sim, AvgSim). Also, the impact of privacy protection on accuracy is studied, and the improvement estimation method is shown to have positive correlation with the actual performance improvement. \n \n- **Pro**. I appreciate the authors' discussion and method about privacy leakage caused by the record similarity. As FL puts emphasis on data privacy, such discussion is necessary. Also, it is good to see the experiments on the tradeoff between privacy and accuracy. I also consider the improvement estimation method interesting. Experiments also validate the effectiveness of the estimation. \n\n- **Con**. The authors made two important assumptions in this paper, that some features are shared between the primary and the secondary parties, and that similarity of the shared features are indicative of the common information (Section 4.3). However, in practice, I would like to raise my doubts on both assumptions. \n    1. **Shared features**. In practical VFL applications where each sample corresponds to a user, the common features held by different parties are often limited [4]. Specifically, in most cases, the only shared feature may be the user ID, and practitioners apply private set intersection (PSI). In this case, FedSim cannot apply. \n    2. **Usefulness of shared features**. Even if such features do exist, it is non-trivial to determine whether the similarities between them are useful. For example, suppose there exist several quasi-identifiers regarding a user, e.g. name, phone number, email, and so on. It is generally hard to say that people with similar names/phone numbers/email service providers have similar properties. \n    3. **Experiments are biased towards the two assumptions**. Continuing from the unrealistic assumptions, I would like to point out that the authors have manually chosen datasets with indicative common features. For example, in the bike dataset, the shared features are longitudes and latitudes of start/end points, and the task is to predict the travel time. It is clear that routes with similar start/end points will have similar travel time, which leads to a bias that favors similarity-based methods against exact-matching-based ones. It is not clear how FedSim compares against exact-matching-based methods when no such indicative common features are present, e.g. the only common features are quasi-identifiers such as names. \n\n## Clarity\nThe presentation of this paper is well-organized. I find it easy to follow the paper. \n\n## Significance. \nI find the paper to be marginally significant. As said in the \"originality\" part, the paper builds on a known idea to improve the performance of VFL. Thus, while the idea and the techniques are sound, it may not bring much insight to the community. \n\n## Overall Strengths: \n- **Good Presentation**. The paper is well-presented and generally easy to follow. \n- **Discussion on privacy**. See 'quality'. \n- **Improvement estimation method is interesting**. See 'quality'. \n\n## Overall Weaknesses:\n- **The insight seems to be overclaiming.**. See \"originality\". \n- **Strong and not realistic assumptions on the \"common features\"**. See 'quality'. \n- **Biased evaluation**. See \"quality\"\n- **Inference procedure not discussed** The authors fail to discuss how the primary party does inference for new samples. Does it need to query similar samples from the secondary party? I would like to see a discussion on the extra procedures and extra costs of the inference phase. \n- **Minor issues**: Please use a better coloring to plot the figures. The current coloring is not friendly to black-and-white printers and color-blind readers.  \n\n[1] Hamilton et al. Inductive Representation Learning in Large Graphs. NIPS 2017\n\n[2] Kipf et al. Semi-supervised Classification using Graph Convolutional Networks. ICLR 2017\n\n[3] Iscen et al. Label Propagation for Deep Semi-supervised Learning. CVPR 2019\n\n[4] Sun et al. Vertical Federated Learning without Revealing Intersection Membership. Arxiv 2021.\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": ["I don’t know"]}, "extra_text": {}}, {"review_id": "ElKklpTWxVs", "reviewer": "Reviewer_8KCf", "summary": "Federated Learning (FL) is a collaborative learning framework for training a model from datasets owned by different parties. A commonly used paradigm for FL is Vertical Federated Learning (VFL), where parities share different features of the same set of samples. Before actually doing the privacy-preserving training process, parties need to first link features with the same or similar identifiers. Existing VFL solutions focus more on exact identifier linkage (one-to-one linkage) by leveraging hashing methods or cryptographic protocols like Private Set Intersection (PSI). However, in some scenarios, linking identifiers with high (but not top) similarity benefits the training. \n\nThis paper designed a coupled training paradigm, FedSim, that introduced Privacy-Preserving Record Linkage (PPRL) that supports high similarity linkage into VFL. Under the SplitNN framework, this paper introduced a new model structure that can take the advantage of the additional similarity information to train a better SplitNN model. The experiments show that the proposed framework can train a better model in a vertical federated manner with little additional cost.", "questions": "Q1: Introducing PPRL into VFL seems a limited contribution.\nAlthough this paper identified a good topic in VFL (Similarity linkage), directly introducing PPRL into VFL seems a straightforward way of solving the problem. I found the main contribution of the paper is not introducing PPRL into VFL, but a new framework (shown in Section 4.2) that leverages the additional similarity information for benefiting VFL. Also, this paper in fact introduced a new way of securing PPRL, i.e., adding Gaussian noises during the PPRL step. To the best of my knowledge, this method can be formalized using Gaussian Differential Privacy or related techniques. I strongly recommend the authors have further analysis and discussions on these two parts, instead of only highlighting the (somewhat limited) contribution of introducing PPRL into VFL.\n\nQ2: About performance comparisons.\nAlthough there are some methods that support similarity linkage, most of which introduce cryptographic tools (e.g., homomorphic encryption, public-key encryption). Such cryptographic tools would introduce high computation costs, making the VFL inefficient and hard to be deployed in practice. This paper introduced a lightweight solution to this problem, namely, the Bloom Filter method proposed in [19]. Even though the Bloom Filter method is lightweight compared with heavy cryptographic operations, it would still introduce some additional symmetric cryptographic operations (like hashes) and some additional communications (like sending Bloom Filters to the server and sharing the similarities). I am wondering if the authors can provide time consumption and communication costs for each phase of FedSim. I personally think these experimental results would further show the efficiency of FedSim.\n\nQ3: About the high-dimensional identifier case\nIn Section 6.1, the authors stated that the experiments used a perturbed identifier for linkage, which is generated by adding Gaussian noises with the same variance (\\sigma_{cf}) to each dimension (See P7, line 288). However, it seems that all experiments use only one dimension as the identifier. It would be better if the authors provide additional discussion on the high-dimensional identifier case.\n\nQ4: About the background of the Bloom Filter PPRL method\nBloom Filter is a well-known technique that has been used in many situations. The Bloom Filter PPRL method used in this paper is a modified one introduced in [19], which does not only support similarity computation between nominal inputs but also numeric inputs. Without the necessary background introduction about the Bloom Filter method proposed in [19], it seems hard for the reader to understand how to calculate the similarity for numeric identifier in FedSim. ", "limitations": "The authors provided limitations adequately in the Appendix. ", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nS1: Identify a good topic that needs to be addressed in VFL. \n\nS2: Give a reasonable and lightweight solution for the problem. The solution can provide some privacy guarantees under the weak security model (without formally provable security).\n\nS3: Provide sufficient experiments.\n\nWeaknesses:\n\nW1: Lack of brief introduction for the PPRL method, making the proposal somewhat hard to understand without seeing [19].\n\nW2: Limited contribution to introducing PPRL into VFL. \n\nW3: The privacy guarantees provided by perturbing identifiers using Gaussian noises need to be further discussed.", "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