Secure Metric Learning via Differential Pairwise Privacy

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

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).

The Privacy Leakage Problem in DML

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 achieve this, DML models are trained on pairwise data—labels indicating whether sample A and sample B are similar or dissimilar. In sensitive fields like healthcare, these relationships are highly confidential; for instance, revealing that two patients are "similar" might expose that they share a rare disease.

Figure 1: Illustration of how an attacker can infer sensitive pairwise relationships by matching query results with conjectures.

Traditional Differential Privacy (DP) protects data by assuming training samples are independent. However, pairwise data inherently 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 also share it. Because individuals participate in multiple pairs, the data is correlated. Standard DP fails to protect against attackers who leverage these transitive correlations, necessitating a new privacy definition tailored specifically to pairwise data.

Methods: Differential Pairwise Privacy (DPP)

To address these vulnerabilities, the authors propose Differential Pairwise Privacy (DPP). This framework moves beyond independent tuples to consider the interconnected nature of pairwise labels.

Figure 2: Overview of Randomized Distance Metric Learning, where noise makes the projected spaces of similar datasets hardly distinguishable to an attacker.

Graph-Based Formulation

The authors model the dataset as an undirected graph where nodes represent individuals and edges represent pairwise labels and feature differences. By applying graph theory—specifically Menger's Theorem regarding edge-disjoint paths—they quantify the "worst-case" prior knowledge an attacker might possess. To protect a target pair, the algorithm must inject sufficient randomness to break the inference paths connecting them.

DPP-DML Algorithm and Sensitivity Reduction

The DPP framework is implemented 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.

A major challenge is that correlated pairwise data often leads to high theoretical maximum gradient sensitivity, which would normally require massive amounts of noise, destroying 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 sensitivity, they can inject significantly less Laplacian noise while maintaining rigorous privacy guarantees.

Key Insights and Ideas

  • Pairwise Privacy as a Graph Problem: Protecting pairwise data requires breaking inference cycles in a graph. DPP generalizes edge and node DP to handle the unique correlations found in metric learning.
  • Transitive vs. Intransitive Relationships: The paper distinguishes between transitive relationships (e.g., "has the same disease"), which require strict privacy bounds due to cascading inference paths, and intransitive ones (e.g., "is friends with").
  • Dynamic Sensitivity Saves Utility: By calculating the maximum difference between a given batch and its neighboring batch during stochastic gradient descent, the authors dynamically shrink the sensitivity bound. This approach dramatically improves the utility of the trained model.

Experimental Results

The authors evaluated their approach on a synthetic toy dataset and four real-world benchmarks (Adult, Bank, IPUMS-BR, and IPUMS-US).

  • High Utility: The proposed DPP-S (DPP with sensitivity reduction) maintains excellent classification accuracy. Across all benchmark datasets, accuracy declines by less than 0.01 compared to a non-private baseline at a privacy budget ($\epsilon$) of 4.
  • Superior Performance: DPP-S consistently outperforms existing workarounds like Node DP (which injects too much noise) and Input Perturbation (which destroys utility by perturbing data before training).
  • Faster Convergence: Sensitivity reduction stabilizes training, allowing the objective function to converge faster and with less fluctuation than vanilla DPP.

Limitations and Future Work

While effective, calculating the exact graph parameter ($\kappa$) for the attacker's prior knowledge can be computationally complex (though efficient approximations exist). Future research could extend DPP to other metric learning objectives, such as triplet or N-pair loss, and explore using database statistics to further enhance 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},
}
Figure