Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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. 
strengths_and_weaknesses: Pros: 
1. The problem is interesting and timely
2. The idea is simple and the results demonstrate its power
3. The paper is easy to read

Cons: 
1. Lack of theoretical analysis of the proposed method
2. The privacy analysis seems to be weak; can it be linked to differential privacy? 
3. 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. 
4. The computational complexity is not discussed (and comparing with other method) 
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?
 
Q2: The merge gate is not clear; can you provide a formal description?

Q3: How the privacy guarantee relates to differential privacy?

Q4: Computationally, will the approach introduce additional cost?

limitations: No
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper describes a framework for enabling VFL while addressing records linkage as a part of the training process. 
The 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. 
Even through the paper is primary focuses on 2 parties VFL the authors also describe how to extend their framework to multiple parties.

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.

questions: Can you describe how the presented work can be further improved? 
What 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.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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. 

This 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.
strengths_and_weaknesses: Strengths:

S1: Identify a good topic that needs to be addressed in VFL. 

S2: 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).

S3: Provide sufficient experiments.

Weaknesses:

W1: Lack of brief introduction for the PPRL method, making the proposal somewhat hard to understand without seeing [19].

W2: Limited contribution to introducing PPRL into VFL. 

W3: The privacy guarantees provided by perturbing identifiers using Gaussian noises need to be further discussed.
questions: Q1: Introducing PPRL into VFL seems a limited contribution.
Although 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.

Q2: About performance comparisons.
Although 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.

Q3: About the high-dimensional identifier case
In 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.

Q4: About the background of the Bloom Filter PPRL method
Bloom 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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths: 
1. The paper is easy to follow: the motivation is sound, the flow is smooth and the presentation is clear.
2. 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.

Weaknesses:
1. 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'. 
2. 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'.
3. 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)?
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).
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper proposes a framework for vertical federated learning (VFL), called FedSim. 

In 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. 

FedSim 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. 
strengths_and_weaknesses: ## Originality
The main idea of the paper is to use similar but not exactly matched samples to assist vertical federated learning. 

+ **Pros** The idea is somewhat new in VFL. The common practice of VFL is that training is only performed on exactly matched samples. 

- **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. 

## Quality
The 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. 
 
- **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. 

- **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. 
    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. 
    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. 
    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. 

## Clarity
The presentation of this paper is well-organized. I find it easy to follow the paper. 

## Significance. 
I 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. 

## Overall Strengths: 
- **Good Presentation**. The paper is well-presented and generally easy to follow. 
- **Discussion on privacy**. See 'quality'. 
- **Improvement estimation method is interesting**. See 'quality'. 

## Overall Weaknesses:
- **The insight seems to be overclaiming.**. See "originality". 
- **Strong and not realistic assumptions on the "common features"**. See 'quality'. 
- **Biased evaluation**. See "quality"
- **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. 
- **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.  

[1] Hamilton et al. Inductive Representation Learning in Large Graphs. NIPS 2017

[2] Kipf et al. Semi-supervised Classification using Graph Convolutional Networks. ICLR 2017

[3] Iscen et al. Label Propagation for Deep Semi-supervised Learning. CVPR 2019

[4] Sun et al. Vertical Federated Learning without Revealing Intersection Membership. Arxiv 2021.

questions: 1. How does a model learned by FedSim perform inference? Any additional procedures/overhead?

2. 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. 

3. 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.
review_title: null

Meta-review: metareview: This paper proposes a VFL technique that is effective in practice (for some datasets) but intuitively may not be general enough for a significant portion of common settings, such as when the identifiers are names. While we recommend to accept this work, we hope the authors can seriously revise this paper in the final version on:
1. Ensuring that overclaiming statements are removed.
2. Adding evidence showing that when the identifiers are names, it can also be effective, in the final version.
3. Adding discussion on how the idea of "similar but not exactly the same samples can be beneficial" used in other topics, e.g., kNN, graph neural networks, semi-supervised learning, personalized federated learning, etc. is related to the one used in VFL.
confidence: Less certain
Decision: Accept