VF-PS: How to Select Important Participants in Vertical Federated Learning, Efficiently and Securely?

Jiawei Jiang, Lukas Burkhalter, Fangcheng Fu, Bolin Ding, Bo Du, Anwar Hithnawi, Bo Li, Ce ZhangNeurIPS 2022 · OpenReview

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:

  1. Scalability: As the number of participants grows, the communication and computation costs of encrypted protocols skyrocket.
  2. Diminishing Returns: In a large consortium, not every participant brings valuable data. Some features are redundant or even noisy.
VFL setup and the challenges of scalability and diminishing returns.

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.

Architecture of VF-MINE utilizing Fagin's algorithm for secure aggregation.

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

Abstract

Vertical Federated Learning (VFL), that trains federated models over vertically partitioned data, has emerged as an important learning paradigm. However, existing VFL methods are facing two challenges: (1) scalability when # participants grows to even modest scale and (2) diminishing return w.r.t. # participants: not all participants are equally important and many will not introduce quality improvement in a large consortium. Inspired by these two challenges, in this paper, we ask: How can we select l out of m participants, where l ≪ m, that are most important?We call this problem Vertically Federated Participant Selection, and model it with a principled mutual information-based view. Our first technical contribution is VF-MINE—a Vertically Federated Mutual INformation Estimator—that uses one of the most celebrated algorithms in database theory—Fagin’s algorithm as a building block. Our second contribution is to further optimize VF-MINE to enable VF-PS, a group testing-based participant selection framework. We empirically show that vertically federated participation selection can be orders of magnitude faster than training a full-fledged VFL model, while being able to identify the most important subset of participants that often lead to a VFL model of similar quality.
BibTeX
@inproceedings{jiang2022vf,
  author = {Jiawei Jiang and Lukas Burkhalter and Fangcheng Fu and Bolin Ding and Bo Du and Anwar Hithnawi and Bo Li and Ce Zhang},
  title = {{VF-PS: How to Select Important Participants in Vertical Federated Learning, Efficiently and Securely?}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=H1eUot0CKwm},
}
Figure