Differentially Private Vertical Federated Clustering (2022-08-02T00:00:00.000000Z)

TL;DR

The algorithm proposed in this paper is the first practical solution for differentially private vertical federated k -means clustering, where the server can obtain a set of global centers with a provable differential privacy guarantee and improves the estimation accuracy in the setting with more than two data parties.

Abstract

In many applications, multiple parties have private data regarding the same set of users but on disjoint sets of attributes, and a server wants to leverage the data to train a model. To enable model learning while protecting the privacy of the data subjects, we need vertical federated learning (VFL) techniques, where the data parties share only information for training the model, instead of the private data. However, it is challenging to ensure that the shared information maintains privacy while learning accurate models. To the best of our knowledge, the algorithm proposed in this paper is the first practical solution for differentially private vertical federated k -means clustering, where the server can obtain a set of global centers with a provable differential privacy guarantee. Our algorithm assumes an untrusted central server that aggregates differentially private local centers and membership encodings from local data parties. It builds a weighted grid as the synopsis of the global dataset based on the received information. Final centers are generated by running any k -means algorithm on the weighted grid. Our approach for grid weight estimation uses a novel, light-weight, and differentially private set intersection cardinality estimation algorithm based on the Flajolet-Martin sketch. To improve the estimation accuracy in the setting with more than two data parties, we further propose a refined version of the weights estimation algorithm and a parameter tuning strategy to reduce the final k -means loss to be close to that in the central private setting. We provide theoretical utility analysis and experimental evaluation results for the cluster centers computed by our algorithm and show that our approach performs better both theoretically and empirically than the two baselines based on existing techniques.

Authors

Tianhao Wang

3 papers

Zitao Li

1 papers

Ninghui Li

1 papers

TL;DR

Abstract

Authors

References81 items

Improving Privacy-Preserving Vertical Federated Learning by Efficient Communication with ADMM

Federated Matrix Factorization with Privacy Guarantee

Locally Private k-Means in One Round

Hybrid Differentially Private Federated Learning on Vertically Partitioned Data

Differentially Private Two-Party Set Operations

Differentially Private Clustering: Tight Approximation Ratios

VAFL: a Method of Vertical Asynchronous Federated Learning

Federated Doubly Stochastic Kernel Learning for Vertically Partitioned Data

Privacy preserving vertical federated learning for tree-based models

Differentially-Private Multi-Party Sketching for Large-Scale Statistics

Membership Inference Attacks and Defenses in Classification Models

Efficient Differentially Private F0 Linear Sketching

Advances and Open Problems in Federated Learning

The Secret Revealer: Generative Model-Inversion Attacks Against Deep Neural Networks

Federated Learning With Differential Privacy: Algorithms and Performance Analysis

FDML: A Collaborative Machine Learning Framework for Distributed Features

Learning Privately over Distributed Features: An ADMM Sharing Approach

Cheaper Private Set Intersection via Differentially Private Leakage

Answering Multi-Dimensional Analytical Queries under Local Differential Privacy

The Value of Collaboration in Convex Machine Learning with Differential Privacy

Federated Forest

Cardinality Estimators do not Preserve Privacy

Distributed learning of deep neural network over multiple agents

Optimal Differentially Private Algorithms for k-Means Clustering

Differentially Private k-Means with Constant Multiplicative Error

The Secret Sharer: Evaluating and Testing Unintended Memorization in Neural Networks

Learning Differentially Private Recurrent Language Models

Back to the Future: an Even More Nearly Optimal Cardinality Estimation Algorithm

Distributed Cardinality Estimation of Set Operations with Differential Privacy

Locally Differentially Private Protocols for Frequency Estimation

Differentially Private Clustering in High-Dimensional Euclidean Spaces

Clustering Algorithms for the Centralized and Local Models

Exposed! A Survey of Attacks on Private Data

Rényi Differential Privacy

Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms

Membership Inference Attacks Against Machine Learning Models

Deep Learning with Differential Privacy

K-Means Clustering with Distributed Dimensions

Locating a Small Cluster Privately

Communication-Efficient Learning of Deep Networks from Decentralized Data

Differentially private subspace clustering

Differentially Private K-Means Clustering

Fast and Private Computation of Cardinality of Set Intersection and Union

Scikit-learn: Machine Learning in Python

Efficient Set Operations in the Presence of Malicious Adversaries

Private coresets

Efficient Oblivious Pseudorandom Function with Applications to Adaptive OT and Secure Computation of Set Intersection

Et al

NP-hardness of Euclidean sum-of-squares clustering

Efficient Protocols for Set Intersection and Pattern Matching with Security Against Malicious and Covert Adversaries

HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm

Smooth sensitivity and sampling in private data analysis

V-Measure: A Conditional Entropy-Based External Cluster Evaluation Measure

Calibrating Noise to Sensitivity in Private Data Analysis

Privacy-Preserving Set Operations

Privacy-preserving decision trees over vertically partitioned data

Practical privacy: the SuLQ framework

Privacy-Preserving Datamining on Vertically Partitioned Databases

On coresets for k-means and k-median clustering

Efficient Private Matching and Set Intersection

Privacy-preserving k-means clustering over vertically partitioned data

Similarity estimation techniques from rounding algorithms

Silhouettes: a graphical aid to the interpretation and validation of cluster analysis

Probabilistic Counting Algorithms for Data Base Applications

New Directions in Cryptography

(Nearly) All Cardinality Estimators Are Differentially Private

The Flajolet-Martin Sketch Itself Preserves Differential Privacy: Private Counting with Minimal Space

How to Make Private Distributed Cardinality Estimation Practical, and Get Differential Privacy for Free

Privacy-Preserving Secure Cardinality and Frequency Estimation

B.Kacsmar,B.Khurram,N.Lukas,A.Norton,M.Shafieinejad,Z.Shang,Y.Baseri,M.Sepehri,S.Oya,andF.Kerschbaum.Differentiallyprivatetwo-partyset operations.In

and W

Privacy-Preserving SVM Classification on Vertically Partitioned Data without Secure Multi-party Computation

On Approximate Geometric k -Clustering

Algorithmas136:Ak-meansclusteringalgorithm

Some methods for classification and analysis of multivariate observations

Home credit default risk