Federated Transformer: Multi-Party Vertical Federated Learning on Practical Fuzzily Linked Data

Thank you for your valuable comments; we have addressed all concerns below.

W1, L6. How FeT Relies on Linkage Quality: FeT is significantly less reliant on initial linkage quality than traditional VFL models like Top1Sim [4,5]. While Top1Sim trains only on records linked by privacy-preserving record linkage (PPRL) [3], FeT requires PPRL only to approximate the K-nearest neighbors and trains directly on these records, without needing them ordered by distance. Evidence for FeT's robustness includes:

• Ablation Study on K (Figure 14, "rebuttal.pdf"): FeT consistently outperforms baselines with many unrelated data records included (K > 50), showing resilience to low linkage quality.
• Performance with Different Fuzziness (Figure 12, "rebuttal.pdf"): FeT outperforms baselines with moderate to high noise in identifiers, demonstrating strong resilience to fuzziness.
• Dynamic Masking Visualization (Figure 11, "rebuttal.pdf"): The visualization demonstrates that dynamic masking plays a crucial role in handling low-quality linkage, effectively focusing on a few close and relevant records among 4,900 fuzzily linked ones.

Performance of FeT in "Less Ideal" Cases: FeT performs better in general fuzzy VFL scenarios but slightly underperforms Top1Sim [4,5] in ideal cases with precisely matched identifiers. This limitation is discussed in Appendix D with experiments on VFL datasets with randomly assigned precise IDs. Moreover, as shown in Figure 12 of "rebuttal.pdf," FeT only slightly underperforms compared to Top1Sim in low-noise conditions of gisette dataset.

W2, W3, L5. Why Focus on Performance Over Efficiency?: In multi-party fuzzy VFL, the main challenge is fuzzy VFL models like FedSim [2] perform worse than Solo training in multi-party setting, instead of computational efficiency. FeT, as the first effective approach for multi-party fuzzy VFL, prioritizes performance to address this critical gap. For clarity, we will change the title to "Federated Transformer: Multi-Party Vertical Federated Learning on Practical Fuzzily Linked Data" and other related contents.

Efficiency of FeT: We compared FeT's computational and memory efficiency with FedSim [2], the state-of-the-art fuzzy VFL model, as shown in Table 11 of "rebuttal.pdf," and identified three key findings:

1. Parameter Efficiency: FeT has a comparable or even smaller (23%-129%) number of parameters than FedSim, indicating that its performance improvement is due to model design rather than parameter scaling.

2. Memory Efficiency: FeT is significantly more memory efficient, consuming only 20-39% of the memory compared to FedSim. However, this efficiency comes at the cost of training speed. FeT performs neighbor search in parallel during real-time training, whereas FedSim spends hours linking top-K neighbors and preloads all linked neighbors into GPU memory, leading to longer linkage times, repeated data records, and higher memory usage.

3. Overhead of New Components: As detailed in Table 11 of "rebuttal.pdf," the additional components in FeT - dynamic masking and positional encoding - add minimal extra parameters (1k - 0.4M), causing only a slight computational overhead (0-5 seconds per epoch slowdown).

In summary, FeT delivers better performance and improved memory efficiency with a similar number of parameters compared to FedSim, despite slightly lower training speed. Further optimization techniques, such as pipeline parallelism, could enhance FeT’s training speed but are beyond this study's scope.

VFL with Limited Resources:

1. FeT's Limited GPU Memory Performance: Table 11 ("rebuttal.pdf") shows that FeT performs well even with GPU memory under 1 GB, making it viable for resource-constrained VFL scenarios.

2. Cross-Silo VFL Prevalence: Cross-device VFL with limited resources is rare. VFL typically occurs in cross-silo settings [3], involving dozens to hundreds of parties with adequate computational power. Discussions with industry collaborators providing commercial VFL services confirm that it's uncommon for a single user to have features spread across thousands of distinct parties.

W4, L4. Three of our datasets (house, taxi, hdb) are real-world VFL datasets, identical to those used in FedSim [2]. Each party's data comes from different real sources; for example, the taxi dataset includes data from New York taxis and CitiBike. These datasets effectively demonstrate FeT's performance in real VFL applications.

L1. In Figure 15 of "rebuttal.pdf," we present a real-world application involving travel cost prediction in a city through collaboration among taxi, car, bike, and bus companies. Since personal travel information is private and cannot be shared, VFL is essential. Additionally, route identifiers - starting and ending GPS locations - can only be fuzzily linked, but linking closely related source and destination points with multi-party fuzzy VFL can significantly improve prediction accuracy.

L2. We have fixed this typo in the revision.

L3. The 80% communication reduction is straightforward from calculations, as the communication reduction is nearly proportional to the party dropout rate. Dropped parties don't participate in gradient and representation exchanges, which account for most communication in VFL.

References

[1] Li, et al. "Learnable fourier features for multi-dimensional spatial positional encoding." NeurIPS 21.

[2] Wu et al. "A coupled design of exploiting record similarity for practical vertical federated learning." NeurIPS 22.

[3] Vatsalan et al. "Privacy-preserving record linkage for big data: Current approaches and research challenges." Handbook of big data technologies, 17.

[4] Hardy et al. Private federated learning on vertically partitioned data via entity resolution and additively homomorphic encryption. arXiv 17.

[5] Nock et al. Entity resolution and federated learning get a federated resolution. arXiv, 18.

Thank you for your valuable comments; we have addressed all concerns as follows.

W1, L1. Real Application of Multi-party Fuzzy VFL: In Figure 15 of "rebuttal.pdf," we present a real-world application involving travel cost prediction in a city through collaboration among taxi, car, bike, and bus companies. Since personal travel information is private and cannot be shared, VFL is essential. Additionally, route identifiers - starting and ending GPS locations - can only be fuzzily linked, but linking closely related source and destination points with multi-party fuzzy VFL can greatly improve prediction accuracy.

German Record Linkage Center (GRLC) and VFL: Previous VFL studies [1-3] show that record linkage is a necessary preprocessing step for VFL, making it inherently involved in all real VFL applications. While VFL studies are relatively new, record linkage has been extensively studied and widely applied. Thus, our study, along with [1], considers GRLC applications to be reflective of VFL applications.

Prevalence of Multi-party Fuzzy VFL in the Real World: Traditional VFL assumes that each data record represents a user, making the assumption of a universal user ID natural. However, in real-world applications, these records often represent various real-world objects - such as a room (e.g., house and hdb datasets) or a travel route (e.g., taxi dataset). Expecting all real-world objects to have a universal, precise ID is unrealistic, which is why case studies in [1] found that over 70% of applications cannot be linked exactly.

W2, L2. We adopt privacy-preserving record linkage (PPRL) [4] for similarity calculation. PPRL is a well-studied area separate from VFL, and we do not impose constraints on specific PPRL approaches, including linkage strategies, representation of fuzzy identifiers, or privacy mechanisms. For example, FEDERAL [5], a PPRL method, transforms fuzzy identifiers into Bloom filters that offer provable privacy guarantees. These Bloom filters' similarities reflect the original fuzzy identifiers' similarities. Our approach, like other fuzzy VFL algorithms [1-3], operates on these calculated similarities. While changing the PPRL method might impact the quality of the similarity measures, it does not affect FeT's superiority compared to other VFL algorithms.

W3, L3. Design Rationale: Dynamic masking filters out unrelated data records with low similarities before they reach deep attention layers. FeT feeds the top-K similar records into the transformer, but this can introduce many unrelated records, leading to overfitting. To prevent this, a simple MLP creates a mask based on current identifiers, allowing the attention layers to focus on a narrower neighborhood and reducing overfitting.

Why Dynamic Masking is Necessary: In our ablation study (Table 3 of Appendix C.1), removing dynamic masking (FeT w/o DM) results in significant performance loss across all five datasets. For example, on MNIST, training without dynamic masking led to a 13 percentage point drop in accuracy, demonstrating its necessity.

How Dynamic Masking Functions: The dynamic masking module, a simple two-layer MLP, takes identifiers as input and outputs a mask added to the attention keys (used in torch.nn.MultiHeadAttention as key_padding_mask). The learned dynamic masks, visualized in Figure 11 of "rebuttal.pdf," reveal two key observations:

• Dynamic masking effectively focuses on a localized area around the primary party's identifiers without accessing them directly. Records with distant identifiers on secondary parties (shown in cool colors) receive small negative mask values, reducing their significance in the attention layers.
• The focus area varies in scale and direction across samples, indicating that the dynamic masking layer generates sample-specific masks to reduce overfitting.

W4. Party dropout is a novel feature in VFL, distinct from traditional Dropout, introduced alongside our split-sum neural network design. Almost all previous VFL models [1-3,6] use a split-concat design, where representations are concatenated at the cut layer and passed to the aggregation model, requiring all parties to be present in each training step. In contrast, we use secure multi-party computation to average the representations, allowing some parties to be absent. This enables party dropout, which disables training of entire encoders of some parties in each step, rather than specific layers. Combined with SplitAvg, party dropout significantly reduces communication costs in multi-party VFL by the dropout ratio.

W5. Our primary goal is to protect representations from secondary parties against an honest-but-curious primary party. We achieve this by applying differential privacy, adding noise to the representations. In VFL, unlike horizontal FL, data across parties are related. Thus, the primary party gains access to more related representations as more parties join. This typically requires adding more noise to maintain the same level of differential privacy, thus reducing utility. To address this, we use secure multi-party computation, letting the primary party know only the sum of the representations, keeping noise levels constant regardless of the number of parties.

References

[1] Wu et al. "A coupled design of exploiting record similarity for practical vertical federated learning." NeurIPS 22.

[2] Nock et al. "The impact of record linkage on learning from feature partitioned data." ICML 21.

[3] Nock et al. Entity resolution and federated learning get a federated resolution. arXiv 18.

[4] Vatsalan et al. "Privacy-preserving record linkage for big data: Current approaches and research challenges." Handbook of big data technologies, 17.

[5] Karapiperis et al. "FEDERAL: A framework for distance-aware privacy-preserving record linkage." TKDE 18.

[6] Liu, et al. "Vertical federated learning: Concepts, advances, and challenges." TKDE 24.

Thank you for your valuable comments; we have addressed all concerns as follows.

W1.1 Design of Dynamic Masking: Dynamic masking is a simple two-layer MLP that can be easily optimized and performs well across all five datasets. Our ablation study in Table 3 of Appendix C.1 demonstrates that dynamic masking consistently and significantly improves performance on all five datasets. For example, on the MNIST dataset, omitting dynamic masking results in a 13 percentage point drop in accuracy. To provide further insight, we visualize the learned dynamic mask in Figure 11 of the attached "rebuttal.pdf."

This visualization reveals two key observations: First, dynamic masking effectively focuses on a localized area around the identifiers of the primary party. Data records with more distant identifiers on secondary parties (shown in cooler colors) are assigned small negative mask values, reducing their influence in the attention layers. Second, the focus area varies in scale and direction across different samples, indicating that the dynamic masking layer learns to generate sample-specific masks, which helps to reduce overfitting.

W1.2 Design of Positional Encoding (PE) Averaging: This design is specifically applicable to VFL scenarios with independent and identically distributed (i.i.d.) identifiers, similar to the FedAvg approach. VFL with heterogeneous or non-i.i.d. identifiers (e.g., one party using GPS coordinates while another uses postal codes) remains an open problem, posing significant challenges for identifier alignment - an area not yet explored in VFL research. Our ablation study in Table 5 of Appendix C.3 shows that PE averaging improves performance compared to non-PE-averaging FeT (average frequency = 0) in most datasets.

W2 Privacy Trade-offs: The trade-off between privacy and performance is illustrated in Figure 5 and Figure 9 of the paper. Both performance (measured by accuracy) and privacy (denoted by $\varepsilon$) are influenced by the noise scale $\sigma$. Generally speaking, $\varepsilon$ reflects the probability bound of determining whether a specific data record exists in the training set based on the representations, regardless of the attack method. Thus, a lower $\varepsilon$ indicates higher privacy. To achieve high privacy, such as $\varepsilon = 1$, a noise scale of approximately $\sigma \approx 8$ is required, which significantly reduces utility, causing FeT to perform similarly to Solo. Conversely, when $\varepsilon$ is larger, such as $\varepsilon = 8$, the required noise scale decreases to $\sigma = 1$, which allows FeT to maintain relatively good performance.

W3. Theoretical Proof: The full proof of Theorem 3 is provided in Appendix A. Background theorems and definitions of differential privacy are covered in Section 2, while the threat model is detailed in Section 4. Since Theorem 3 is based on differential privacy, its assumptions inherit the assumptions of differential privacy.

W4 Experiments on More Scenarios of VFL: We have added experiments using the VertiBench [1] datasets to cover a broader range of VFL scenarios, as detailed in the attached "rebuttal.pdf." The results demonstrate that: 1) FeT outperforms baselines across varying levels of imbalance between parties, and 2) FeT shows better performance in VFL scenarios where parties have more balanced features.

Q1. Scenario Application: Images and texts can be effectively handled by transformer structures, as demonstrated in many existing works [2]. Thus, adapting FeT to other unstructured data should not pose a significant challenge. The two main ideas - 1) encoding common features as positions and 2) dynamic masking -are particularly useful for multimodal alignment in these scenarios. The primary challenge, however, lies in the significant heterogeneity of features across parties. As shown in Figure 13 of the "rebuttal.pdf," although FeT outperforms baselines, its performance on imbalanced features requires further improvement. We are actively working on addressing this issue.

Q2. Please refer to W2. Privacy Tradeoffs.

Q3. Significant Heterogeneous Features We have conducted additional experiments using the VertiBench [1] datasets with varying heterogeneity (balance level $\alpha$) across parties, as shown in Figure 13 in the attached "rebuttal.pdf." The results demonstrate that while FeT's absolute performance decreases under severely heterogeneous feature distributions (very low $\alpha$), its improvement over Solo training becomes more pronounced in such heterogeneous scenarios.

L1. Large Scale Cases: Unlike horizontal federated learning, Vertical Federated Learning (VFL) is primarily observed in cross-silo scenarios [3] rather than cross-device scenarios [4], as it is unlikely that a single user would have features distributed across thousands or even millions of distinct parties. This observation is supported by our communication with industry collaborators that provide commercial VFL service. Therefore, we focus on the cross-silo case, where collaborations among dozens or hundreds of parties are more common.

L2. Privacy Trade-offs: We agree that malicious parties, rather than our assumed honest-but-curious parties, would present a greater privacy risk to the model design. We will acknowledge this limitation and plan to explore such scenarios in future work.

References

[1] Wu et al. "VertiBench: Advancing feature distribution diversity in vertical federated learning benchmarks." ICLR 24.

[2] Han et al. "A survey on vision transformer." TPAMI 22.

[3] Huang et al. "Cross-silo federated learning: Challenges and opportunities." arXiv 22.

[4] Karimireddy et al. "Breaking the centralized barrier for cross-device federated learning." NeurIPS 21.

Thank you for your valuable comments; we have addressed all concerns as follows.

W1. We will include a formal definition in Section 4 and the introduction. Our scenario extends the two-party fuzzy VFL model defined in FedSim [1] to a multi-party setting. Below, we clarify the key terms:

• Multi-party VFL: Federated learning tasks involving $k+1$ parties, denoted as $\{S_h\}_{h=0}^k$. Each party $S_h$ has $n_h$ data records, represented as $\mathbf{x}^{S_h} \in \mathcal{R}^{n_h \times (c + m_h)}$, where $c$ is the number of common features shared by all parties, and $m_h$ refers to the unique features held by each party $S_h$.

• Identifier: For each data instance $x_i^{S_h} \in \mathbf{x}^{S_h}$, the $c$ common features $k_i^{S_h} \in \mathcal{R}^{1 \times c}$ are termed the identifier or key of $x_i^{S_h}$. All identifiers for $S_h$ are denoted as $\mathbf{k}_i^{S_h} := \{k_i^{S_h}\}_{i=1}^{n_h}$.

• Fuzzy Identifier: In multi-party VFL, if two parties $S_a$ and $S_b$ have identifiers such that $\forall k_i \in \mathbf{k}_i^{S_a}$ and $\forall k_j \in \mathbf{k}_j^{S_b}$, $k_i \neq k_j$, then $\mathbf{k}_i^{S_a}$ and $\mathbf{k}_j^{S_b}$ are fuzzy identifiers.

• Multi-party Fuzzy VFL: A VFL scenario involving parties with fuzzy identifiers.

Importance of Fuzzy Identifiers: The critical role of linkage quality in VFL performance has been shown both empirically [1] and theoretically [2]. This impact is even more pronounced in multi-party settings with increasing noise, as demonstrated by our significant improvement over FedSim in such scenarios.

Prevalence of Multi-party Fuzzy VFL in the Real World: Traditional VFL assumes that each data record represents a user, making the assumption of a universal user ID natural. However, in real-world applications, these records often represent various real-world objects - such as a room (e.g., house and hdb datasets) or a travel route (e.g., taxi dataset). Expecting all real-world objects to have a universal, precise ID is unrealistic, which is why case studies in [1] found that over 70% of applications cannot be linked exactly.

W2. Privacy-Preserving Record Linkage (PPRL) is a linkage algorithm that calculates identifier similarities but lacks learning mechanisms, serving as a preprocessing step for most VFL algorithms. As such, PPRL is not directly comparable to VFL approaches like FeT.

An extension of PPRL, known as Top1Sim [3,4], performs VFL on the most similar records identified by PPRL. We have thoroughly compared Top1Sim as a baseline. However, this simple extension overlooks significant information, which led to the development of learning-integrated approaches like FedSim [1] and FeT. Notably, Top1Sim incurs a 42% higher RMSE compared to FeT on the house dataset.

W3. Efficiency of FeT: We compared FeT's computational and memory efficiency with FedSim, the state-of-the-art fuzzy VFL model, as shown in Table 11 of "rebuttal.pdf," and identified three key findings:

1. Parameter Efficiency: FeT has a comparable or even smaller (23%-129%) number of parameters than FedSim, indicating that its performance improvement is due to model design rather than parameter scaling.

2. Memory Efficiency: FeT is significantly more memory efficient, consuming only 20-39% of the memory compared to FedSim. However, this efficiency comes at the cost of training speed. FeT performs neighbor search in parallel during real-time training, whereas FedSim spends hours linking top-K neighbors and preloads all linked neighbors into GPU memory, leading to longer linkage times, repeated data records, and higher memory usage.

3. Overhead of New Components: As detailed in Table 11 of "rebuttal.pdf," the additional components in FeT - dynamic masking and positional encoding - add minimal extra parameters (1k - 0.4M), causing only a slight computational overhead (0-5 seconds per epoch slowdown).

In summary, FeT delivers better performance and improved memory efficiency with a similar number of parameters compared to FedSim, despite slightly lower training speed. Further optimization techniques, such as pipeline parallelism, could enhance FeT’s training speed but are beyond this study's scope.

Privacy of FeT: Figures 5(b, d) and 10 in the paper show FeT's privacy superiority. Since related studies use similar Gaussian noise mechanisms, we compare the noise scale at the same $\varepsilon$ rather than accuracy. At the same $\varepsilon$, FeT requires much less noise than RDP, a previous pure DP approach like FedOnce [5], generally leading to better model utility.

MW1. Real Application of Multi-party Fuzzy VFL: In Figure 15 of "rebuttal.pdf," we present a real-world application involving travel cost prediction in a city through collaboration among taxi, car, bike, and bus companies. Since personal travel information is private and cannot be shared, VFL is essential. Additionally, route identifiers - starting and ending GPS locations - can only be fuzzily linked, but linking closely related source and destination points with multi-party fuzzy VFL can significantly improve prediction accuracy.

MW2. The 13% improvement comes from comparing FeT to FeT without dynamic masking, as shown in Table 2 of Appendix C.1.

MW3. We will correct this formulation in the revision.

References

[1] Wu et al. "A coupled design of exploiting record similarity for practical vertical federated learning." NeurIPS 22.

[2] Nock et al. "The impact of record linkage on learning from feature partitioned data." ICML 21.

[3] Hardy et al. Private federated learning on vertically partitioned data via entity resolution and additively homomorphic encryption. arXiv, 17.

[4] Nock et al. Entity resolution and federated learning get a federated resolution. arXiv, 18.

[5] Wu et al. "Practical vertical federated learning with unsupervised representation learning." IEEE Transactions on Big Data, 2022.