RetrievalGuard: Provably Robust 1-Nearest Neighbor Image Retrieval
This addresses the problem of adversarial robustness in image retrieval for users relying on secure and reliable retrieval systems, representing a novel method for a known bottleneck.
The paper tackled the vulnerability of image retrieval models to adversarial attacks by proposing RetrievalGuard, a provably robust 1-nearest neighbor algorithm that ensures Recall@1 remains invariant to perturbations within a calculable radius, with experimental validation on image retrieval tasks.
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 $\ell_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 $\ell_2$ adversarial perturbations. Experiments on image retrieval tasks validate the robustness of our RetrievalGuard method.