Unfolded Self-Reconstruction LSH: Towards Machine Unlearning in Approximate Nearest Neighbour Search

Kim Yong Tan, Yueming Lyu, Yew Soon Ong, Ivor W. TsangarXiv 2023 · DOI · arXiv

Introduction

In the era of large-scale information retrieval, Approximate Nearest Neighbor (ANN) search has become a cornerstone for applications ranging from image retrieval to recommendation systems. However, the rise of privacy regulations such as GDPR and CCPA has introduced a significant challenge: the "Right to be Forgotten." When a user requests data deletion, modern high-performance ANN indices—which are often data-dependent—frequently require full retraining to ensure complete removal of the user's information. This paper introduces Unfolded Self-Reconstruction Locality-Sensitive Hashing (USR-LSH), a novel approach that bridges the gap between high-performance retrieval and efficient machine unlearning.

The Challenge of Machine Unlearning in ANN

Traditional Locality-Sensitive Hashing (LSH) methods fall into two categories. Data-independent hashing (e.g., SimHash) uses random projections, making it trivial to update but often resulting in mediocre retrieval accuracy. Conversely, data-dependent hashing learns from the underlying data distribution to produce highly accurate codes. However, these learned models are computationally expensive to retrain when data is deleted, creating a bottleneck for privacy compliance.

The core objective of USR-LSH is to achieve the accuracy of learned models while maintaining the update speed of random projection methods.

Methodology: Unfolded Self-Reconstruction

USR-LSH reinterprets hashing as a reconstruction problem. The goal is to find a binary code $b$ that, when decoded via a matrix $W$, minimizes the reconstruction error of the original data point $x$. The authors employ three primary innovations to make this process efficient and "unlearnable":

  1. Stacked Random Rotations: The decoder matrix $W$ is initialized as a series of stacked, orthogonal random matrices. This ensures the foundation of the hash remains data-independent.
  2. Optimization Unfolding: Finding the optimal binary code is a discrete optimization problem. USR-LSH relaxes this using a $tanh$ activation and "unfolds" the iterative optimization steps into a fixed-depth architecture ($T$ stages). This allows for deterministic, fast hashing without backpropagation.
  3. Instance-wise Learning: Because the optimization is performed per-instance during the hashing process, the system does not rely on global data distributions that would necessitate retraining upon deletion.

Datasets

The performance of USR-LSH was evaluated across several standard high-dimensional benchmarks, varying in size and distance metrics to ensure robustness across different data types.

Table 1: Summary of datasets used for benchmarking USR-LSH, including size, dimensionality, and distance metric.

These datasets represent a diverse range of use cases, from visual features (SIFT, Deep1B) to semantic word embeddings (GloVe).

Key Results and Insights

The experimental results demonstrate that USR-LSH effectively addresses the trade-off between accuracy and unlearning efficiency.

Retrieval Accuracy

USR-LSH significantly outperforms standard data-independent methods. In low-dimensional scenarios, it achieved an average improvement of 131% in Area Under the Precision-Recall Curve (PR-AUC) compared to SimHash. By focusing on local structure reconstruction, the method preserves more information than simple random projections.

Unlearning Efficiency

The primary advantage of USR-LSH is its near-instantaneous deletion capability. In USR-LSH, the only global parameter is a scalar coefficient $\alpha$ derived from the average Euclidean norm of the dataset. Deleting a point only requires updating this average.

On the Deep1B dataset, USR-LSH processed a deletion in approximately 2 seconds. In contrast, state-of-the-art data-dependent algorithms like Google’s Scann and Spotify’s Annoy required 81 seconds and 291 seconds respectively, as they necessitated index rebuilding or retraining to maintain integrity.

Pareto Efficiency

While the $T$ iterations of the unfolded optimization introduce a slight overhead compared to a single random projection, the substantial gains in precision place USR-LSH on a superior Pareto front. It offers a more favorable balance of query speed and retrieval quality for systems requiring frequent updates.

Conclusion

USR-LSH represents a significant step forward for privacy-preserving vector search. By "unfolding" optimization into a fixed architecture, the authors provide a method that rivals learned hashing in accuracy while remaining as flexible as random projections for data deletion. Future work will focus on integrating multi-probe techniques and optimizing the implementation in C++ to further reduce query latency.

Summary updated

Abstract

Approximate nearest neighbour (ANN) search is an essential component of search engines, recommendation systems, etc. Many recent works focus on learning-based data-distribution-dependent hashing and achieve good retrieval performance. However, due to increasing demand for users' privacy and security, we often need to remove users' data information from Machine Learning (ML) models to satisfy specific privacy and security requirements. This need requires the ANN search algorithm to support fast online data deletion and insertion. Current learning-based hashing methods need retraining the hash function, which is prohibitable due to the vast time-cost of large-scale data. To address this problem, we propose a novel data-dependent hashing method named unfolded self-reconstruction locality-sensitive hashing (USR-LSH). Our USR-LSH unfolded the optimization update for instance-wise data reconstruction, which is better for preserving data information than data-independent LSH. Moreover, our USR-LSH supports fast online data deletion and insertion without retraining. To the best of our knowledge, we are the first to address the machine unlearning of retrieval problems. Empirically, we demonstrate that USR-LSH outperforms the state-of-the-art data-distribution-independent LSH in ANN tasks in terms of precision and recall. We also show that USR-LSH has significantly faster data deletion and insertion time than learning-based data-dependent hashing.
BibTeX
@misc{tan2023unfolded,
  author = {Kim Yong Tan and Yueming Lyu and Yew Soon Ong and Ivor W. Tsang},
  title = {{Unfolded Self-Reconstruction LSH: Towards Machine Unlearning in Approximate Nearest Neighbour Search}},
  year = {2023},
  eprint = {2304.02350},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2304.02350},
}
Figure