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