# RetrievalGuard: Provably Robust 1-Nearest Neighbor Image Retrieval

arXiv: https://arxiv.org/abs/2206.11225 · HTML: https://mlsanity.com/paper/2206.11225/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 47 references that are in the map.
- First posted on arXiv 17 Jun 2022.

## Builds on (most cited first, 30 of 33)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [FaceNet: A Unified Embedding for Face Recognition and Clustering](https://mlsanity.com/paper/1503.03832/) (2015)
- [Theoretically Principled Trade-off between Robustness and Accuracy](https://mlsanity.com/paper/1901.08573/) (2019)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples](https://mlsanity.com/paper/1802.00420/) (2018)
- [Evasion Attacks against Machine Learning at Test Time](https://mlsanity.com/paper/1708.06131/) (2017)
- [Certified Robustness to Adversarial Examples with Differential Privacy](https://mlsanity.com/paper/1802.03471/) (2018)
- [Deep Metric Learning via Lifted Structured Feature Embedding](https://mlsanity.com/paper/1511.06452/) (2015)
- [Multi-Similarity Loss with General Pair Weighting for Deep Metric Learning](https://mlsanity.com/paper/1904.06627/) (2019)
- [Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers](https://mlsanity.com/paper/1906.04584/) (2019)
- [A Metric Learning Reality Check](https://mlsanity.com/paper/2003.08505/) (2020)
- [Sampling Matters in Deep Embedding Learning](https://mlsanity.com/paper/1706.07567/) (2017)
- [Towards Stable and Efficient Training of Verifiably Robust Neural Networks](https://mlsanity.com/paper/1906.06316/) (2019)
- [Proxy Anchor Loss for Deep Metric Learning](https://mlsanity.com/paper/2003.13911/) (2020)
- [Evaluating the Robustness of Neural Networks: An Extreme Value Theory Approach](https://mlsanity.com/paper/1801.10578/) (2018)
- [Certified Adversarial Robustness with Additive Noise](https://mlsanity.com/paper/1809.03113/) (2018)
- [Orthogonal Convolutional Neural Networks](https://mlsanity.com/paper/1911.12207/) (2019)
- [Revisiting Training Strategies and Generalization Performance in Deep Metric Learning](https://mlsanity.com/paper/2002.08473/) (2020)
- [A unifying mutual information view of metric learning: cross-entropy vs. pairwise losses](https://mlsanity.com/paper/2003.08983/) (2020)
- [Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness](https://mlsanity.com/paper/2002.03239/) (2020)
- [Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and More](https://mlsanity.com/paper/2008.12952/) (2020)
- [PointGuard: Provably Robust 3D Point Cloud Classification](https://mlsanity.com/paper/2103.03046/) (2021)
- [Black-Box Certification with Randomized Smoothing: A Functional Optimization Based Framework](https://mlsanity.com/paper/2002.09169/) (2020)
- [Transferable, Controllable, and Inconspicuous Adversarial Attacks on Person Re-identification With Deep Mis-Ranking](https://mlsanity.com/paper/2004.04199/) (2020)
- [Random Smoothing Might be Unable to Certify ℓ_∞ Robustness for High-Dimensional Images](https://mlsanity.com/paper/2002.03517/) (2020)
- [Universal Perturbation Attack Against Image Retrieval](https://mlsanity.com/paper/1812.00552/) (2018)
- [RecurJac: An Efficient Recursive Algorithm for Bounding Jacobian Matrix of Neural Networks and Its Applications](https://mlsanity.com/paper/1810.11783/) (2018)
- [Design and Interpretation of Universal Adversarial Patches in Face Detection](https://mlsanity.com/paper/1912.05021/) (2019)
- [Adversarial Ranking Attack and Defense](https://mlsanity.com/paper/2002.11293/) (2020)

## Built on by (most cited first, 15 of 15)

- [A Resilient and Accessible Distribution-Preserving Watermark for Large Language Models](https://mlsanity.com/paper/2310.07710/) (2023)
- [Faster Adaptive Federated Learning](https://mlsanity.com/paper/2212.00974/) (2022)
- [MM-PoisonRAG: Disrupting Multimodal RAG with Local and Global Poisoning Attacks](https://mlsanity.com/paper/2502.17832/) (2025)
- [Adversarial Weight Perturbation Improves Generalization in Graph Neural Networks](https://mlsanity.com/paper/2212.04983/) (2022)
- [A Watermark for Order-Agnostic Language Models](https://mlsanity.com/paper/2410.13805/) (2024)
- [De-mark: Watermark Removal in Large Language Models](https://mlsanity.com/paper/2410.13808/) (2024)
- [Solving a Class of Non-Convex Minimax Optimization in Federated Learning](https://mlsanity.com/paper/2310.03613/) (2023)
- [Distortion-free Watermarks are not Truly Distortion-free under Watermark Key Collisions](https://mlsanity.com/paper/2406.02603/) (2024)
- [Decentralized Riemannian Algorithm for Nonconvex Minimax Problems](https://mlsanity.com/paper/2302.03825/) (2023)
- [Enhance Diffusion to Improve Robust Generalization](https://mlsanity.com/paper/2306.02618/) (2023)
- [Serverless Federated AUPRC Optimization for Multi-Party Collaborative Imbalanced Data Mining](https://mlsanity.com/paper/2308.03035/) (2023)
- [Adversarial Hubness Detector: Detecting Hubness Poisoning in Retrieval-Augmented Generation Systems](https://mlsanity.com/paper/2602.22427/) (2026)
- [Cooperation or Competition: Avoiding Player Domination for Multi-Target Robustness via Adaptive Budgets](https://mlsanity.com/paper/2306.15482/) (2023)
- [See the Speaker: Crafting High-Resolution Talking Faces from Speech with Prior Guidance and Region Refinement](https://mlsanity.com/paper/2510.26819/) (2025)
- [Nearest-Neighbor Radii under Dependent Sampling](https://mlsanity.com/paper/2605.14343/) (2026)

## Abstract (arXiv)

Recent research works have shown that image retrieval models are vulnerable to adversarial attacks, where slightly modified test inputs could lead to problematic retrieval results. In this paper, we aim to design a provably robust image retrieval model which keeps the most important evaluation metric Recall@1 invariant to adversarial perturbation. We propose the first 1-nearest neighbor (NN) image retrieval algorithm, RetrievalGuard, which is provably robust against adversarial perturbations within an ℓ2 ball of calculable radius. The challenge is to design a provably robust algorithm that takes into consideration the 1-NN search and the high-dimensional nature of the embedding space. Algorithmically, given a base retrieval model and a query sample, we build a smoothed retrieval model by carefully analyzing the 1-NN search procedure in the high-dimensional embedding space. We show that the smoothed retrieval model has bounded Lipschitz constant and thus the retrieval score is invariant to ℓ2 adversarial perturbations. Experiments on image retrieval tasks validate the robustness of our RetrievalGuard method.