Introduction
Vertical Federated Learning (VFL) allows multiple organizations to collaboratively train machine learning models over vertically partitioned data—meaning different organizations hold different features for the same set of individuals (e.g., a bank and an e-commerce site sharing data about the same customers). To keep this data private, VFL systems rely on heavy-duty cryptography like Homomorphic Encryption (HE).
However, VFL often suffers from a "more is less" problem: adding more participants increases computational costs exponentially due to encryption overhead, but often yields diminishing returns in model quality. This paper introduces VF-PS, a framework that uses a novel, secure mutual information estimator to identify and select only the most important participants, making VFL training orders of magnitude faster without sacrificing accuracy.
The Bottlenecks of VFL
The authors identify two major bottlenecks in current VFL paradigms:
- Scalability: As the number of participants grows, the communication and computation costs of encrypted protocols skyrocket.
- Diminishing Returns: In a large consortium, not every participant brings valuable data. Some features are redundant or even noisy.
The ironic result is that training on a massive consortium takes a massive amount of time, yet the final model might be no better than one trained on a small, high-quality subset. The authors ask: How can we select the most important participants efficiently and securely before we even start the expensive training process?
Methods: Selecting the Best Participants
The authors frame participant selection as a search for the subset that maximizes Mutual Information (MI) between features and labels. Their solution, VF-PS, consists of two main technical pillars:
1. VF-MINE (The Estimator)
Estimating MI usually requires finding $k$-nearest neighbors (KNN). Doing this across encrypted, distributed datasets is normally very slow. The authors adapt Fagin’s Algorithm—a classic tool from database theory—to find these neighbors. By only aggregating the top-ranked candidates rather than the entire dataset, they drastically reduce the amount of data that needs to be encrypted and sent. This turns a "big data" encryption problem into a much lighter "top-k" retrieval problem.
2. Group Testing (The Search)
Instead of testing every possible combination of participants (which is mathematically impossible for large groups), they use a group testing framework. They run a series of "tests" on random subsets of participants and use the results to calculate an "importance score" for each individual party.
To make this even faster, they introduce Communication Batching. They prove an "Inclusion Property": the candidates needed for a small group of participants are often a subset of those needed for a larger group. This allows them to process multiple test groups in a single execution.
Key Results and Insights
The researchers evaluated their framework on eight diverse datasets, ranging from synthetic benchmarks to large-scale real-world datasets (like Birch1/2 with 100,000 instances).
- Massive Speedups: VF-PS is up to two orders of magnitude faster than training a full-fledged VFL model on the entire group. Furthermore, the Fagin-inspired MI estimator (VF-MINE) is significantly faster than baseline KNN estimators used in popular libraries like scikit-learn.
- The "Less is More" Effect: The results confirm that training on all participants is often a mistake. On most datasets, selecting just 50% of the participants resulted in a model with nearly identical (and sometimes higher) test accuracy compared to using 100% of participants. This suggests that participant selection acts as a form of noise filtering.
- Accuracy and Security: In tests on the KNN model, VF-PS identified the same optimal subsets as a brute-force search on six out of eight datasets, but in a fraction of the time. Crucially, the method maintains the standard security guarantees of VFL (Feature, Aggregation, and Identity security).
Limitations and Future Work
While a major step forward, the authors note a few areas for improvement:
- Static Selection: Currently, participants are selected once at the start. In reality, a participant's importance might change during different stages of training.
- Metric Bias: The KNN-based MI estimator can be biased toward smaller local feature subsets when using Euclidean distance. Exploring other distance metrics is a suggested next step.
- Extreme Scalability: While it handles modest scales well, the authors acknowledge that in "mega-consortiums" with thousands of participants, even the Fagin-based approach might face performance degradation.
- Fairness: The paper focuses on accuracy, but "rewarding" participants based on MI scores raises complex questions about fairness and incentives in federated ecosystems.
Summary updated