mlsanityData to 7 Oct 2026

RetrievalGuard: Provably Robust 1-Nearest Neighbor Image Retrieval

arXiv 2206.11225 ↗First posted 17 Jun 2022cs.IR cs.LGcited by 15

Not on the map. Why?

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.

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

Builds on

33 of 47 references.

References · 33

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2013Intriguing properties of neural networkscited by 5,114
  3. 2015FaceNet: A Unified Embedding for Face Recognition and Clusteringcited by 2,833
  4. 2019Theoretically Principled Trade-off between Robustness and Accuracycited by 1,510
  5. 2019Certified Adversarial Robustness via Randomized Smoothingcited by 1,324
  6. 2018Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examplescited by 1,259
  7. 2017Evasion Attacks against Machine Learning at Test Timecited by 686
  8. 2018Certified Robustness to Adversarial Examples with Differential Privacycited by 462
  9. 2015Deep Metric Learning via Lifted Structured Feature Embeddingcited by 449
  10. 2019Multi-Similarity Loss with General Pair Weighting for Deep Metric Learningcited by 368
  11. 2019Provably Robust Deep Learning via Adversarially Trained Smoothed Classifierscited by 328
  12. 2020A Metric Learning Reality Checkcited by 317
21 more
  1. 2017Sampling Matters in Deep Embedding Learningcited by 285
  2. 2019Towards Stable and Efficient Training of Verifiably Robust Neural Networkscited by 204
  3. 2020Proxy Anchor Loss for Deep Metric Learningcited by 195
  4. 2018Evaluating the Robustness of Neural Networks: An Extreme Value Theory Approachcited by 181
  5. 2018Certified Adversarial Robustness with Additive Noisecited by 178
  6. 2019Orthogonal Convolutional Neural Networkscited by 122
  7. 2020A unifying mutual information view of metric learning: cross-entropy vs. pairwise lossescited by 100
  8. 2020Revisiting Training Strategies and Generalization Performance in Deep Metric Learningcited by 99
  9. 2020Curse of Dimensionality on Randomized Smoothing for Certifiable Robustnesscited by 56
  10. 2020Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and Morecited by 56
  11. 2021PointGuard: Provably Robust 3D Point Cloud Classificationcited by 49
  12. 2020Black-Box Certification with Randomized Smoothing: A Functional Optimization Based Frameworkcited by 45
  13. 2020Transferable, Controllable, and Inconspicuous Adversarial Attacks on Person Re-identification With Deep Mis-Rankingcited by 42
  14. 2020Random Smoothing Might be Unable to Certify ℓ_∞ Robustness for High-Dimensional Imagescited by 35
  15. 2018Universal Perturbation Attack Against Image Retrievalcited by 31
  16. 2018RecurJac: An Efficient Recursive Algorithm for Bounding Jacobian Matrix of Neural Networks and Its Applicationscited by 27
  17. 2019Design and Interpretation of Universal Adversarial Patches in Face Detectioncited by 22
  18. 2020Adversarial Ranking Attack and Defensecited by 14
  19. 2020Adversarial Attack on Deep Product Quantization Network for Image Retrievalcited by 13
  20. 2021Exploring Adversarial Robustness of Deep Metric Learningcited by 4
  21. 2022Boosting Barely Robust Learners: A New Perspective on Adversarial Robustnesscited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 6; 2024: 3; 2025: 2; 2026: 2.

15 papers.

Sort:

By area:

  1. 2023A Resilient and Accessible Distribution-Preserving Watermark for Large Language Modelscited by 47
  2. 2022Faster Adaptive Federated Learningcited by 35
  3. 2025MM-PoisonRAG: Disrupting Multimodal RAG with Local and Global Poisoning Attackscited by 24
  4. 2022Adversarial Weight Perturbation Improves Generalization in Graph Neural Networkscited by 21
  5. 2024A Watermark for Order-Agnostic Language Modelscited by 14
  6. 2024De-mark: Watermark Removal in Large Language Modelscited by 11
  7. 2023Solving a Class of Non-Convex Minimax Optimization in Federated Learningcited by 10
  8. 2024Distortion-free Watermarks are not Truly Distortion-free under Watermark Key Collisionscited by 10
  9. 2023Decentralized Riemannian Algorithm for Nonconvex Minimax Problemscited by 7
  10. 2023Enhance Diffusion to Improve Robust Generalizationcited by 3
  11. 2023Serverless Federated AUPRC Optimization for Multi-Party Collaborative Imbalanced Data Miningcited by 3
  12. 2026Adversarial Hubness Detector: Detecting Hubness Poisoning in Retrieval-Augmented Generation Systemscited by 2
3 more
  1. 2023Cooperation or Competition: Avoiding Player Domination for Multi-Target Robustness via Adaptive Budgetscited by 0
  2. 2025See the Speaker: Crafting High-Resolution Talking Faces from Speech with Prior Guidance and Region Refinementcited by 0
  3. 2026Nearest-Neighbor Radii under Dependent Samplingcited by 0