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":
- 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.
- 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.
- 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.
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