Secure Metric Learning via Differential Pairwise Privacy

Jing Li, Yuangang Pan, Yulei Sui, Ivor W. Tsang

TL;DR

Distance Metric Learning (DML) relies on pairwise data, which inherently leaks sensitive relationship information (e.g., two patients sharing a disease) that traditional Differential Privacy (DP) cannot protect due to data correlation. This paper introduces Differential Pairwise Privacy (DPP), a novel framework that models pairwise data as a graph to bound an attacker's prior knowledge. By coupling DPP with a clever gradient sensitivity reduction technique, the authors train secure DML models with almost no loss in accuracy.

What Problem Does This Paper Address?

Distance Metric Learning (DML) is a foundational machine learning technique used to project data into a space where similar samples are grouped together and dissimilar ones are pushed apart. To do this, DML models are trained on pairwise data—labels indicating whether sample A and sample B are similar or dissimilar. In fields like healthcare, this pairwise relationship is highly sensitive (e.g., revealing that Alice and Bob have the same rare disease).

Traditional Differential Privacy (DP) protects data by assuming training samples are independent. However, pairwise data breaks this assumption. If Alice and Bob share a disease, and Bob and Jim share the same disease, an attacker can easily infer that Alice and Jim share the disease. Because individuals participate in multiple pairs, the data is correlated. Standard DP fails to protect against attackers who leverage these transitive correlations, creating a need for a new privacy definition tailored specifically to pairwise data.

Methods

To solve this, the authors propose Differential Pairwise Privacy (DPP).

  • Graph-Based Formulation: The authors model the dataset as an undirected graph where nodes are individuals and edges are the pairwise labels and feature differences. They use graph theory (specifically Menger's Theorem regarding edge-disjoint paths) to quantify the "worst-case" prior knowledge of an attacker. To protect a target pair, the algorithm must inject enough randomness to break the inference paths connecting them.
  • DPP-DML Algorithm: The authors implement DPP for DML using gradient perturbation during Empirical Risk Minimization (ERM) with a contrastive loss function. Noise is injected into the gradients during training to mask the presence of any specific pairwise relationship.
  • Gradient Sensitivity Reduction (The Novelty): Because pairwise data is highly correlated, the theoretical maximum gradient sensitivity (how much one pair can change the model) is very high. Adding noise scaled to this maximum destroys model utility. The authors introduce a dynamic sensitivity reduction technique that analyzes the actual distribution of pairs within a specific minibatch. By finding a tighter, localized bound for the sensitivity, they can inject significantly less Laplacian noise while maintaining the same rigorous privacy guarantee.

Datasets

The authors evaluate their approach on one synthetic dataset and four real-world benchmarks:

  • Synthetic Toy Dataset: A 2D dataset with two Gaussian classes used to visually demonstrate how the learned metric transforms the data space.
  • Adult: 1994 Census database containing personal income information.
  • Bank: Data related to direct marketing campaigns of a Portuguese banking institution.
  • IPUMS-BR & IPUMS-US: Census microdata collected from IPUMS-International.

Key Insights and Ideas

  • Pairwise Privacy is a Graph Problem: Protecting pairwise data isn't just about hiding a single data tuple; it requires breaking inference cycles in a graph. DPP effectively generalizes edge DP and node DP to handle the unique correlations of metric learning.
  • Transitive vs. Intransitive Relationships: The paper highlights a crucial semantic difference in pairwise data. Transitive relationships (e.g., "has the same disease") require much stricter privacy bounds than intransitive ones (e.g., "is friends with") because transitivity creates cascading inference paths.
  • Dynamic Sensitivity Saves Utility: You don't always have to use the absolute theoretical maximum sensitivity for noise injection. By looking at the maximum difference between a given batch and its neighboring batch during stochastic gradient descent, you can dynamically shrink the sensitivity bound. This "free lunch" dramatically improves the utility of the trained model.

Key Results

  • High Utility: The proposed DPP-S (DPP with sensitivity reduction) maintains excellent classification accuracy. Across all benchmark datasets, the accuracy declines by less than 0.01 compared to a non-private baseline when the privacy budget ($\epsilon$) is set to 4.
  • Beating Baselines: DPP-S consistently outperforms existing privacy workarounds like Node DP and Input Perturbation. Node DP injects too much noise due to loose bounds, while Input Perturbation destroys too much downstream utility by perturbing the data before training.
  • Faster Convergence: Thanks to the sensitivity reduction technique, the objective function of the DPP-S algorithm converges much faster and with less fluctuation than vanilla DPP, proving that reducing redundant noise stabilizes training.

Limitations and Future Work

  • Limitations: Calculating the exact graph parameter ($\kappa$) that bounds the attacker's prior knowledge can be computationally complex, though the authors provide an efficient approximation in the appendix. Additionally, the main implementation focuses specifically on the contrastive loss function.
  • Future Work: The authors suggest extending this privacy implementation to other popular metric learning objectives, such as triplet loss or N-pair loss. They also propose exploring how to use database statistics, rather than direct pairwise data, to perform distance metric learning with even higher utility.

Summary updated

Abstract

Distance Metric Learning (DML) has drawn much attention over the last two decades. A number of previous works have shown that it performs well in measuring the similarities of individuals given a set of correctly labeled pairwise data by domain experts. These important and precisely-labeled pairwise data are often highly sensitive in real world (e.g., patients similarity). This paper studies, for the first time, how pairwise information can be leaked to attackers during distance metric learning, and develops differential pairwise privacy (DPP), generalizing the definition of standard differential privacy, for secure metric learning. Unlike traditional differential privacy which only applies to independent samples, thus cannot be used for pairwise data, DPP successfully deals with this problem by reformulating the worst case. Specifically, given the pairwise data, we reveal all the involved correlations among pairs in the constructed undirected graph. DPP is then formalized that defines what kind of DML algorithm is private to preserve pairwise data. After that, a case study employing the contrastive loss is exhibited to clarify the details of implementing a DPP- DML algorithm. Particularly, the sensitivity reduction technique is proposed to enhance the utility of the output distance metric. Experiments both on a toy dataset and benchmarks demonstrate that the proposed scheme achieves pairwise data privacy without compromising the output performance much (Accuracy declines less than 0.01 throughout all benchmark datasets when the privacy budget is set at 4).
BibTeX
@article{li2020secure,
  author = {Jing Li and Yuangang Pan and Yulei Sui and Ivor W. Tsang},
  title = {{Secure Metric Learning via Differential Pairwise Privacy}},
  journal = {IEEE Trans. Inf. Forensics Secur.},
  year = {2020},
  url = {https://openreview.net/forum?id=ZDkQ1cH0psq},
}

Loading related content...

Figure