Differentially Private Supervised Manifold Learning with Applications like Private Image Retrieval

Praneeth Vepakomma, Julia Balla, Ramesh Raskar

Abstract

Differential Privacy (DP) offers strong guarantees such as immutable privacy under post-processing. This work focuses on supervised manifold learning to generate fine-tuned manifolds for specific use cases. We present PrivateMail, a novel differentially private method for supervised manifold learning. We provide a novel private geometric embedding scheme for private content-based image retrieval. Experiments on standard benchmarks show extensive privacy-utility tradeoffs, demonstrating the computational efficiency and practicality of our methods.

Introduction

Image retrieval—finding the "nearest neighbors" to a query image in a large database—is a cornerstone of modern computer vision. However, in sensitive contexts like medical imaging or biometric search, the query image itself is private data. Existing solutions face a "trilemma": non-private methods lack security, cryptographic methods (like Homomorphic Encryption) are computationally prohibitive, and standard Differential Privacy (DP) methods often destroy utility by adding noise that washes out subtle data signals.

PrivateMail bridges this gap by creating a DP mechanism that utilizes supervised information (labels) to preserve utility while maintaining formal privacy guarantees. By mathematically bounding the sensitivity of a supervised embedding process, the framework allows clients to query remote databases using deep features without revealing the original query image.

The PrivateMail Framework

The core of this approach is the Supervised Manifold Learning Query (SMLQ) and its privatized version, PrivateMail.

SMLQ Objective

The algorithm seeks a low-dimensional embedding that minimizes a dual objective: preserving the local geometric structure of the data (the manifold) while simultaneously maximizing the separation between different classes using labels. This supervision acts as a "noise buffer"; by pushing classes apart in the embedding space, the resulting structure becomes robust enough to survive the addition of DP noise.

The PrivateMail Protocol

The protocol enables secure interaction between a client and a server:

  1. Feature Extraction: The client extracts deep features from their private query image and a small "public" dataset.
  2. Privatization: The client runs the first iteration of SMLQ and adds Gaussian noise calibrated to a derived global sensitivity bound.
  3. Iterative Refinement: Due to the post-processing invariance of DP, subsequent iterations can be run without further depleting the privacy budget (epsilon).
  4. Alignment: The server uses the public dataset as an "anchor" to align the client's private embedding with its own database using a rigid-body transformation (Kabsch-Umeyama algorithm).
Figure 1: The PrivateMail system architecture, illustrating the interaction between the server's database and the client's private query through a shared public data anchor.

Experimental Evaluation

The researchers evaluated PrivateMail on three standard image retrieval benchmarks: CUB-200-2011 (fine-grained birds), Cars196, and CIFAR-100. They utilized state-of-the-art deep features (ResNet-50) as input to the manifold learning process.

Key Results

PrivateMail demonstrates a superior privacy-utility trade-off compared to major baselines, including Private PCA and DP-dSNE (an unsupervised manifold method).

  • High Utility at Low Epsilon: On the CARS196 and CIFAR-100 datasets, PrivateMail's Recall@8 performance approaches that of non-private methods even at high privacy levels (low epsilon).
  • Superiority over Unsupervised DP: It significantly outperforms DP-dSNE across all tested privacy budgets. For example, on CIFAR-100, PrivateMail maintains high recall at epsilon=2, where other private methods' performance collapses.
  • Efficiency: The iterative update rule avoids expensive matrix inverses and reaches peak utility in fewer than 10 iterations.
Figure 6: Privacy vs. utility results across three datasets. PrivateMail (purple stars) consistently outperforms other private baselines like DP d-SNE and Private PCA, approaching non-private performance as the privacy budget increases.

Discussion and Conclusion

The success of PrivateMail stems from two key insights. First, supervision as a noise buffer: labels provide a stronger signal-to-noise ratio than unsupervised methods. Second, public data as an anchor: using a shared reference point allows for coordinate alignment without leaking private query information.

While the current implementation relies on global sensitivity, future work could explore smooth sensitivity to further reduce noise. Additionally, while tested on image retrieval, the underlying SMLQ framework is generalizable to other sensitive manifold learning tasks, such as private drug discovery or financial fraud detection.

Summary updated

Abstract

Differential Privacy offers strong guarantees such as immutable privacy under post processing. Thus it is often looked to as a solution to learning on scattered and isolated data. This work focuses on supervised manifold learning, a paradigm that can generate fine-tuned manifolds for a target use case. Our contributions are two fold. 1) We present a novel differentially private method \textit{PrivateMail} for supervised manifold learning, the first of its kind to our knowledge. 2) We provide a novel private geometric embedding scheme for our experimental use case. We experiment on private "content based image retrieval" - embedding and querying the nearest neighbors of images in a private manner - and show extensive privacy-utility tradeoff results, as well as the computational efficiency and practicality of our methods.
BibTeX
@inproceedings{vepakomma2022differentially,
  author = {Praneeth Vepakomma and Julia Balla and Ramesh Raskar},
  title = {{Differentially Private Supervised Manifold Learning with Applications like Private Image Retrieval}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i8.20827},
}
Figure