# On the Vulnerability of Retrieval in High Intrinsic Dimensionality Neighborhood

Teddy Furon

► To cite this version:

Teddy Furon. On the Vulnerability of Retrieval in High Intrinsic Dimensionality Neighborhood. IEEE Transactions on Information Forensics and Security, 2025, 20, pp.3576-3586. 10.1109/TIFS.2025.3553067. hal-05012282

HAL Id: hal-05012282

https://hal.science/hal-05012282v1

Submitted on 31 Mar 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# On the Vulnerability of Retrieval in High Intrinsic Dimensionality Neighborhood

Teddy Furon

***Abstract***—This article investigates the vulnerability of the nearest neighbors search, which is a pivotal tool in pattern analysis and data science. The vulnerability is gauged as the relative amount of perturbation that an attacker needs to add to a dataset point in order to modify its proximity to a given query. The statistical distribution of the relative amount of perturbation is derived from simple assumptions, outlining the key factor that drives its typical values: The higher the intrinsic dimensionality, the more vulnerable is the nearest neighbors search. Experiments on six large-scale datasets validate this model up to some outliers, which are explained as violations of the assumptions.

***Index Terms***—Nearest Neighbors Search, Vulnerability

## I. INTRODUCTION

THE search of Nearest Neighbors (NN) not only appears in the top-10 algorithms in data mining according to [1], but it is also at the root of many information processing and pattern analysis methods ranging from retrieval, detection [2], classification [3], and regression [4]. Chen and Shah explain its popularity because it is a flexible, non-parametric, interpretable, and computationally efficient method [5].

As such, many security or safety-oriented applications rely on information retrieval operated by the NN search. The existence of an attacker intentionally circumventing the NN search becomes a plausible threat. For instance, social networks often compare uploaded content to a collection of materials to detect ‘forbidden’ content (terrorism, pedopornography, fake news, etc.) or to identify copyright holders (content monetization). Search Engine Optimization makes one’s items (websites, goods, etc.) appear at the top of the search results [6]. This is a crucial tool in struggles between competitive businesses and also for political influence [7]. Detecting outliers to spot fraud in financial transactions or intrusion in security systems is another example of critical applications of the NN search [2].

The NN search is also a defense mechanism, as it recently helped rescue some machine learning techniques. At training time, NN search is a key tool for sanitizing the training set by detecting mislabeled data [8] or poisoned training samples [9]. At test time, NN search is a defense against adversarial examples to robustify regression [10] or classification [11]. Studies [12]–[14] share the same idea to detect adversarial images by considering them as outliers different than NN, whose effect is mitigated in [11], [15].

The versatility and ubiquity of the NN search motivate research on its intrinsic vulnerability, independently of any

application. It is of utmost importance to analyze the security of this key primitive before its deployment in applications where security matters.

**Experimental Evidence of the Vulnerability** Some works have already shown the vulnerability of the NN search, especially in computer vision. The forgery of a query image deflecting NN search has indeed a long history in Content-Based Image Retrieval (CBIR) and image classification. Do et al. motivate their work by pinpointing that CBIR became a technology brick used in applications where security is at stake, like content monetization or curation on social networks [16]. In the pre-Deep Learning era, these authors delude such a mechanism (i.e. a given dataset image is no longer returned by the k-NN search) by exploiting the Achilles’ heel of the SIFT local description (orientation). Tolias et al. play the opposite game with nowadays deep learning representation: the query image (e.g. depicting a flower) is manipulated to retrieve images matching another visual content (e.g. the Eiffel tower) to protect the privacy of the querying user [17]. The striking result is that the manipulation of query images remains almost invisible to the human eyes. On the same line, Xiao and Wang investigate the same scenario but with black-box transferability [18]. The general poor level of security is due to two weak points: i) deep neural networks provide discriminative but sensitive feature vectors easily corrupted by image manipulation, a well-known fact in the literature of adversarial examples [19], and ii) a small move in this high dimensional feature space may be sufficient to dramatically change the nearest neighbors, as demonstrated by [20].

Our paper is dedicated to this later vulnerability and is a follow-up study of [20].

**Our contributions** This work deals with features extracted from objects, considered as vectors living in high-dimensional space, and compared with the Euclidean distance. The objective is to quantify the amount of perturbation in this feature space needed to delude the retrieval mechanism in terms of modification of the nearest neighbors. This is exemplified by the scenario where the attacker modifies the $k_x$-th nearest neighbor in the dataset to reduce its rank to a target $k_t < k_x$.

Under some broad assumptions listed in Sec. III, our contribution models the necessary amount of perturbation as a random variable and reveals its precise distribution. This statistical approach pinpoints what governs typical values of the distortion: the ranks $k_x$ and $k_t$, the size $n$ of the dataset, and the scalar index $\ell$ characterizing the distances of the dataset points in the neighborhood of the query. This index is referred to as the *local intrinsic dimensionality* in [21]. Section IV shows that the necessary amount of perturbation

T. Furon is with Centre de Recherche Inria de l'Université de Rennes, France. Work supported by the French project *Compromis*, ANR-22-PECY-00XX-02.

Manuscript submitted August 2024.
converges to a simple distribution when the dataset size $n$ grows to infinity. This asymptotical distribution gets concentrated when the ratio $k_t/k_x$ is large or when the local intrinsic dimensionality is high. This reveals that some feature spaces are more vulnerable. Our study outlines that this phenomenon is not related to the representational dimension of the features (the number of components of the feature vectors) but to their intrinsic dimensionality. If this quantity is high, then the neighborhood of the query may not be 'safe' because an attacker could have easily modified it with little distortion.

Experiments in Sect. V over six large-scale datasets (four of them gather one billion dataset points each) of a different nature show a very close fit with the asymptotical model. Section VI extends the results to a plurality of scenarios where the point is moved farther away from the query (i.e. $k_t > k_x$), and/or the attacker perturbs the query while the dataset points are fixed. In the end, this section discusses some implications for the feature extraction function, often trained with supervised learning.

## II. RELATED WORK

Xing et al. study the theoretical robustness of NN classifiers under noise corruption on the inputs [22], whereas Sitawarin et al. and L. Wang et al. efficiently create adversarial examples against NN classifiers [23], [24]. Y. Wang et al. propose a theoretical explanation by extending the theoretical analysis of classification based on nearest neighbors [25]. The classic theory shows how the probability of correct classification behaves for fixed $k$ and $n$ increasing [26, Chap. 5] or the universal consistency when $k$ is allowed to grow with $n$ s.t. $k/n \to 0$ [26, Chap. 6]. Y. Wang et al. generalize this to the adversarial risk by introducing the concept of astuteness [25]: not only a query $q$ should be correctly classified, but so are all the points surrounding it at a distance lower than a robustness radius $r$. They outline the vulnerability of NN classifier in the following way: zero robustness is expected for a fixed $k$, and one has to set $k$ to a very large amount $\Omega(\sqrt{dn \log n})$ to asymptotically reach the robustness of the optimal Bayesian classifier.

Our work strongly differs because it considers NN retrieval, not NN classification: There is no label and thus no law $p(Y|X)$, but just a collection of $n$ points in space $\mathbb{R}^d$.

Article [20] is the only work we know of studying the core robustness of the NN retrieval out of any supervision task. Amsaleg et al. show that, asymptotically, as $n$ increases, the necessary relative amount of perturbation has a simple expression. This article is a follow-up study<fnref n="1" /> of [20]. With the same assumptions, a more accurate model of the amount of perturbation reveals its asymptotical and non-asymptotical distributions.

## III. PROBLEM STATEMENT

Let us consider a dataset $\mathcal{D}$ of $n$ points $\{\mathbf{x}_i\}_{i=1}^n \subset \mathbb{R}^d$, plus a query point $\mathbf{q}$ wherever in this space. Suppose that a program bases its decision on the dataset points that are the $k_t$

nearest neighboring the query. Suppose that the dataset point $\mathbf{x}$ is not part of this neighborhood. In other words, $\mathbf{x}$ is only the $k_x$ nearest neighbor of $\mathbf{q}$ with $1 \le k_t < k_x \le n$. This work is interested in the amount of perturbation to be applied to dataset point $\mathbf{x}$ so that the program now considers it.

### A. Definition of the Relative Amount of Perturbation

As shown in Fig. 1, we denote by $\mathbf{t}$ the dataset point that is the $k_t$ nearest neighbor of $\mathbf{q}$. We also introduce $\mathbf{t} := \|\mathbf{t} - \mathbf{q}\|$ and $\mathbf{x} := \|\mathbf{x} - \mathbf{q}\|$ (Euclidean norm) ; we have $\mathbf{t} < \mathbf{x}$. The perturbation pushes $\mathbf{x}$ to a new point $\mathbf{y}$ with the goal that its neighbor rank is $k_y \le k_t$, thus at a distance $\mathbf{y} := \|\mathbf{y} - \mathbf{q}\| \le \mathbf{t}$.

The relative amount of perturbation is evaluated by the ratio $\delta := \|\mathbf{x} - \mathbf{y}\|/\|\mathbf{x} - \mathbf{q}\|$, with $\delta \in (0, 1)$. It measures the norm of the perturbation $\mathbf{y} - \mathbf{x}$ relatively to the original distance of $\mathbf{x}$ from $\mathbf{q}$. The authors of [19] also use this metric in their experimental study. This implies that:

$$k_y \le k_t \iff y \le t \iff \delta \ge 1 - \frac{t}{x} \quad (1)$$

This ratio is set to the minimum if $\mathbf{x}$ is pushed onto $\mathbf{y}$ in a direct line towards $\mathbf{q}$ so that $\mathbf{y}$ belongs to the line segment $\overline{\mathbf{x}\mathbf{q}}$ as shown in Fig. 1. The sequel assumes that this strategy is feasible, and we set $\delta = 1 - t/x$.

### B. Statistical Model

In this study, $k_x$ and $k_t$ are fixed integers reflecting the goal of the attacker: to push $\mathbf{x}$ of rank $k_x$ such that its rank becomes $k_t$. Knowing this, the relative amount of perturbation also depends on the configuration of the dataset points locally around $\mathbf{q}$. Like the authors of [20], our model considers that this dataset of points is indeed random. This means that distances $t$ and $x$ are occurrences of random variables $T_n$ and $X_n$ (note that $0 < T_n < X_n$), and so is the relative amount of perturbation $\delta$ w.r.t. random variable $\Delta_n := 1 - T_n/X_n$. The subscript $n$ stresses that the size of the dataset is a major factor.

We do not impose a specific distribution of the dataset points in $\mathbb{R}^d$, but only assume a statistical distribution of their distances from $\mathbf{q}$.

**Assumption 1.** The distances of the dataset points w.r.t. the query $\mathbf{q}$ are random variables independent and identically distributed, whose c.d.f. is denoted by $F: \mathbb{R}^+ \to [0, 1]$ and p.d.f. $f: \mathbb{R}^+ \to \mathbb{R}^+$.

<figure><img src="image_2.png" /><figcaption>Fig. 1. Configuration of the dataset neighbors $\mathbf{x}$ and $\mathbf{t}$, and the manipulated point $\mathbf{y}$ with respect to the query $\mathbf{q}$.</figcaption></figure>

<footnote n="1">¹The author was a contributor of [20].</footnote>
<table><caption>TABLE I
SUMMARY OF THE NOTATIONS</caption><tr><td>A, a</td><td>a random variable, one realization</td></tr><tr><td>A, a</td><td>a random vector, one realization</td></tr><tr><td>n</td><td>number of points in the dataset</td></tr><tr><td>q, y</td><td>query and adversarial points</td></tr><tr><td>x, t</td><td>two neighboring points of q</td></tr><tr><td>k<sub>x</sub>, k<sub>t</sub></td><td>ranks of neighbors x and t</td></tr><tr><td>k<sub>y</sub></td><td>rank of the adversarial point y</td></tr><tr><td>x, y, t</td><td>distances from the query q of points x, y, and t</td></tr><tr><td>δ</td><td>relative amount of perturbation measured as 1 − t/x</td></tr><tr><td>X<sub>n</sub>, T<sub>n</sub></td><td>distances for the k<sub>x</sub> and k<sub>t</sub> neighbours<br>in a dataset of n random points</td></tr><tr><td>F</td><td>c.d.f. of the distances from q</td></tr><tr><td>Δ<sub>n</sub>, F<sub>Δ<sub>n</sub></sub></td><td>random relative amount of perturbation and its c.d.f.</td></tr><tr><td>Δ, F<sub>Δ</sub></td><td>asymptotical r.v. of Δ<sub>n</sub> as n → inf and its c.d.f.</td></tr></table>

We should have written $F_q$ and $f_q$ to outline that this statistical model only holds for the distances from $q$; we omit this subscript for simplicity. A second assumption deals with the behavior of c.d.f. $F$ around 0.

**Assumption 2.** The distances of the dataset points w.r.t. the query **q** are absolutely continuous r.v., whose c.d.f. $F$ is a regularly varying function [27] around $0^+$ with index $\ell > 0$ in the sense that, $\forall \lambda > 0$

$$ \lim_{x \to 0^+} \frac{F(\lambda x)}{F(x)} = \lambda^\ell. \qquad (2) $$

Again, we use a simplified notation although the value of the index $\ell$ of the regular variation is specific to the given **q** because it models the distribution of the distance from **q**. Indeed, this index is called the *Local Intrinsic Dimensionality* (LID) in [20], [21] to insist that it only characterizes the local neighborhood of the query point.

This assumption is motivated by the theory of extreme values [28, Chap.VIII]. As $n$ increases while the ranks $k_x$ and $k_t$ are fixed, the distances of the $k_x$ and $k_t$ nearest neighbors tap into the lower tail of the distance distribution, which ought to be regularly varying because it is lower bounded by 0. This implies that the *absolute* amount of perturbation $X_n - T_n$ asymptotically goes to zero. Yet, the asymptotical behavior of the *relative* amount $\Delta_n = (X_n - T_n)/X_n$ is not trivial. Ultimately, the neighborhood of **q** is parametrized with the single index $\ell$. For example, if the neighbors are Gaussian normal distributed spanning an affine hyperplane of dimension $d' \le d$ and passing through query **q**, then $\ell = d'$. The converse is, of course, not true. Indeed, index $\ell$ can be much smaller than the representational dimension $d$ (see Sect. V).

# IV. STATISTICS OF THE RELATIVE PERTURBATION

## A. Finite Dataset Size $n$

The probability distribution of $(T_n, X_n)$ is the joint distribution of two order statistics ranked at $k_t$ and $k_x$ over $n$ i.i.d. random variables [29, Eq. 2.2.1]: For $1 \le k_t < k_x \le n$, if $x > t \ge 0$, then

$$ g_n(t, x) = \frac{F^{k_t-1}(t)[F(x) - F(t)]^{k_x-k_t-1}[1-F(x)]^{n-k_x}}{B(k_t, k_x - k_t)B(k_x, n - k_x + 1)} \times f(t)f(x), \qquad (3) $$

and 0 otherwise ($B$ is the Beta function). The c.d.f. $F_{\Delta_n}$ of random variable $\Delta_n$ is given by

$$ F_{\Delta_n}(\delta) = \mathbb{P}(\Delta_n \le \delta) = \mathbb{P}(X_n(1-\delta) \le T_n) \quad (4) $$

$$ = \int_{0}^{+\infty} \left( \int_{(1-\delta)x}^{x} g_n(t, x) dt \right) dx. \quad (5) $$

Figure 2 illustrates function $g_n$ and the domain of integration.

**Proposition 1.** The c.d.f. of the minimal relative amount of perturbation is given by:

$$ F_{\Delta_n}(\delta) = 1 - \mathbb{E} \left[ I_{F((1-\delta)F^{-1}(\Xi))/\Xi}(k_t, k_x - k_t) \right]. \quad (6) $$

with $\Xi \sim \text{Beta}(k_x, n - k_x + 1)$ and $I_x(\alpha, \beta)$ the regularized incomplete beta function, i.e. the c.d.f. of distribution $\text{Beta}(\alpha, \beta)$.

*Proof:* The c.d.f. $F_{\Delta_n}$ given in (5) writes as: $\forall \delta \in (0, 1)$

$$ F_{\Delta_n}(\delta) = \frac{\int_0^{+\infty} H(\delta, x) f(x) [1-F(x)]^{n-k_x} dx}{B(k_x, n-k_x+1)}, \quad (7) $$

with

$$ \begin{aligned} H(\delta, x) &:= \frac{\int_{(1-\delta)x}^{x} F^{k_t-1}(t) f(t) [F(x) - F(t)]^{k_x-k_t-1} dt}{B(k_t, k_x - k_t)} \\ &= F(x)^{k_x-1} \int_{\frac{F((1-\delta)x)}{F(x)}}^{1} \frac{\tau^{k_t-1} [1-\tau]^{k_x-k_t-1}}{B(k_t, k_x - k_t)} d\tau \\ &= F(x)^{k_x-1} \left(1 - I_{F((1-\delta)x)/F(x)}(k_t, k_x - k_t)\right), \quad (8) \end{aligned} $$

where the change of variable is defined by $\tau := F(t)/F(x)$. In the end, with another change of variable $\xi := F(x)$

$$ F_{\Delta_n}(\delta) = \frac{\int_0^1 H(\delta, F^{-1}(\xi))(1-\xi)^{n-k_x} d\xi}{B(k_x, n-k_x+1)} \quad (9) $$

$$ = 1 - \mathbb{E} \left[ I_{F((1-\delta)F^{-1}(\Xi))/\Xi}(k_t, k_x - k_t) \right], \quad (10) $$

with $\Xi \sim \text{Beta}(k_x, n - k_x + 1)$. ■

<figure><img src="image_3.png" /><figcaption>Fig. 2. Visualization of the part of $g_n(t, x)$ to be integrated in (5), for $\delta = 1/3$, $k_t = 2$, $k_x = 4$, $n = 40$, and $F(x) = x^5$.</figcaption></figure>
### B. Infinite Dataset Size $n \to +\infty$

We now look for a better understanding of the distribution of $\Delta_n$ asymptotically as $n \to +\infty$. Figure 3 shows that its c.d.f. $F_{\Delta_n}$ seems to converge to an asymptotic function. This section discovers this asymptotic function thanks to the following version of Laplace's method [30]:

**Lemma 1.** Let $g, h: (0, 1) \to \mathbb{R}$ two continuous functions s.t.

* $\int_0^1 |g(\xi)|e^{h(\xi)}d\xi < +\infty$

* $\exists \delta_0 > 0, \forall \delta \in (0, \delta_0), \forall \xi \in [\delta, 1), h(x) < h(\delta)$

* Around $0^+, 2$

$$g(\xi) \sim A\xi^{\alpha}, \quad \text{with } \alpha > -1,$$

$$h(\xi) = a - c\xi^{\beta} + o(\xi^{\beta}), \quad \text{with } c > 0, \beta > 0.$$

Then, as $n \to +\infty$

$$\int_0^1 g(\xi)e^{nh(\xi)}d\xi \sim \frac{A}{\beta}\Gamma\left(\frac{\alpha+1}{\beta}\right)e^{an}(cn)^{-\frac{\alpha+1}{\beta}}.$$

We rewrite (9) in the form $\int_0^1 g(\xi)e^{nh(\xi)}dx/B(k_x, n-k_x+1)$ with $h(\xi) = \log(1-\xi)$ and

$$g(\xi) = \left(1 - I_{F((1-\delta)F^{-1}(\xi))/\xi}(k_t, k_x - k_t)\right) \xi^{k_x-1} (1-\xi)^{-k_x}.$$

Thanks to assumption 2, we know that

$$\lim_{\xi \to 0^+} \frac{F((1-\delta)F^{-1}(\xi))}{\xi} = \lim_{x \to 0^+} \frac{F((1-\delta)x)}{F(x)} = (1-\delta)^{\ell}. \quad (11)$$

This allows us to instantiate the constants defined in Lemma 1:

$$\begin{aligned} A &= I_{1-(1-\delta)^{\ell}}(k_x - k_t, k_t), & \alpha &= k_x - 1, \\ a &= 0, & c &= 1, & \beta &= 1. \end{aligned} \quad (12)$$

leading to the following asymptotical expression as $n \to +\infty$:

$$F_{\Delta_n}(\delta) \sim I_{1-(1-\delta)^{\ell}}(k_x - k_t, k_t) \frac{n!}{n^{k_x}(n-k_x)!}, \quad (13)$$

and to the limit function $F_\Delta: \forall \delta \in (0, 1)$

$$F_\Delta(\delta) := \lim_{n \to +\infty} F_{\Delta_n}(\delta) = I_{1-(1-\delta)^{\ell}}(k_x - k_t, k_t), \quad (14)$$

thanks to the asymptotic equivalence $\Gamma(n+\alpha) \sim \Gamma(n)n^\alpha$. This can be restated as the main result of this paper:

**Proposition 2.** Given two ranks $k_x > k_t$, the relative amount of perturbation $\Delta_n$ converges in distribution to $\Delta = 1 - B^{1/\ell}$ with $B \sim \text{Beta}(k_t, k_x - k_t)$ as the size $n$ of the dataset increases.

*Proof:* The Laplace's method finds the simple limit $F_\Delta(\delta) = I_{L(\delta)}(k_x - k_t, k_t)$ with $L(x) := 1 - (1-x)^\ell$. Since function $L$ is a strictly increasing function, $F_\Delta(\delta)$ can be expressed as the c.d.f. of the random variable $L^{-1}(B') = 1 - (1 - B')^{1/\ell}$ with $B' \sim B(k_x - k_t, k_t)$:

$$\mathbb{P}(L^{-1}(B') \le \delta) = \mathbb{P}(B' \le L(\delta)) = F_\Delta(\delta). \quad (15)$$

<figure><img src="image_4.png" /><figcaption>Fig. 3. Convergence of $F_{\Delta_n}$ to $F_\Delta$ as $n$ increases from $10^2$ to $10^6$, $k_t = 2$, $k_x = 4$, and $F(x) = x^\ell$ with $\ell = 5$.</figcaption></figure>

Knowing that $B = 1 - B'$ is distributed as $B(k_t, k_x - k_t)$, we have $\Delta = 1 - (1 - B')^{1/\ell} = 1 - B^{1/\ell}$. ■

Figure 4 shows how the mode of the p.d.f. of $\Delta$ decreases as $\ell$ increases, especially for large $k_x$. This means that the relative amount of adversarial perturbation is weaker in high intrinsic dimension regions of the feature space. The next section highlights this phenomenon by computing some statistics. This figure also illustrates that it becomes more peaky around its mode. This means that the outcome of an attack (success or failure) becomes less random.

### C. Statistics of Random Variable $\Delta$

This section derives the mean, the median, and the mode associated with the asymptotical distribution of $\Delta$.

**Proposition 3.** The r. v. $\Delta$ has the following statistics:

* **Expectation:** for $k_x \gg 1$,

$$\mathbb{E}[\Delta] \approx 1 - (k_t/k_x)^{1/\ell} \left(1 - \frac{\ell-1}{2\ell^2} \frac{k_x - k_t}{k_t(k_x + 1)}\right) \quad (16)$$

* **Median:** for $k_t \ge 2$ and $k_x \ge k_t + 2$,

$$\begin{aligned} \bar{\Delta} &= 1 - (I_{1/2}^{-1}(k_t, k_x - k_t))^{1/\ell} \\ &\approx 1 - (k_t/k_x)^{1/\ell} \left(1 + \frac{2k_t - k_x}{k_t(3k_x - 2)}\right)^{1/\ell} \end{aligned} \quad (17)$$

* **Mode:**

$$\text{mode} = 1 - \left(\frac{k_t}{k_x}\right)^{1/\ell} \left(1 + \frac{(\ell+1)k_t - k_x}{\ell k_x k_t - (\ell+1)k_t}\right)^{1/\ell}. \quad (18)$$

*Proof:* The proof uses the fact that $\Delta = 1 - B^{1/\ell}$.

**Expectation** We did not find any close-form expression for $\mathbb{E}[\Delta]$. Yet, the expectation and the variance of $B \sim \text{Beta}(k_t, k_x - k_x)$ shows that $B$ concentrates around its expectation as $k_x$ becomes large:

$$\mathbb{E}[B] = \frac{k_x - k_t}{k_x}, \quad \mathbb{V}[B] = \frac{\mathbb{E}[B](1 - \mathbb{E}[B])}{(k_x + 1)}. \quad (19)$$

<footnote n="2">²Asymptotical equivalence $a(x) \sim b(x)$ means $a(x) = b(x)(1 + o(1))$.</footnote>
The Taylor series of $\Delta = 1 - B^{1/\ell}$ around $\mathbb{E}[B]$ gives

$$ 
\begin{aligned}
\Delta &= a + b(B - \mathbb{E}[B]) + c(B - \mathbb{E}[B])^2 + o((B - \mathbb{E}[B])^2) \\
a &= 1 - \mathbb{E}[B]^{1/\ell}, \quad b = -\frac{1}{\ell}\mathbb{E}[B]^{1/\ell-1}, \quad c = -\frac{(\frac{1}{\ell}-1)}{2\ell}\mathbb{E}[B]^{1/\ell-2}.
\end{aligned}
$$

Applying the expectation on both sides, we obtain:

$$ \mathbb{E}[\Delta] \approx 1 - \mathbb{E}[B]^{1/\ell} - \frac{1}{2\ell} \left( \frac{1}{\ell} - 1 \right) \mathbb{E}[B]^{1/\ell-2} \mathbb{V}[B] \quad (20) $$

$$ \approx 1 - \left( \frac{k_t}{k_x} \right)^{1/\ell} \left( 1 - \frac{\ell - 1}{2\ell^2} \frac{k_x - k_t}{k_t(k_x + 1)} \right). \quad (21) $$

**Median** Translating quantiles of $B$ to quantiles of $\Delta$ is easy as $x \to 1-x^{1/\ell}$ is a strictly decreasing function over $(0, 1)$: The $p$-quantile of $B$ equals $I_p^{-1}(k_t, k_x - k_t)$ so that the $p$-quantile of $\Delta$ equals $1 - (I_{1-p}^{-1}(k_t, k_x - k_t))^{1/\ell}$. For instance, the median $\bar{\Delta}$ of $\Delta$ is simply $\bar{\Delta} = 1 - \bar{B}^{1/\ell}$. The median $\bar{B}$ of $\text{Beta}(\alpha, \beta)$ is usually approximated by $(\alpha - 1/3)/(\alpha + \beta - 2/3)$ for $\alpha \ge 2$ and $\beta \ge 2$. This translates to the following approximation: for $k_t \ge 2$ and $k_x \ge k_t + 2$:

$$ \bar{\Delta} \approx 1 - \left( \frac{k_t - 1/3}{k_x - 2/3} \right)^{1/\ell} = 1 - (k_t/k_x)^{1/\ell} \left( 1 + \frac{2k_t - k_x}{k_t(3k_x - 2)} \right)^{1/\ell}. $$

**Mode** We first compute the p.d.f. by derivating $F_\Delta$ (14):

$$ f_\Delta(\delta) = \frac{\ell \left(1 - (1 - \delta)^\ell\right)^{k_x - k_t - 1} (1 - \delta)^{k_t \ell - 1}}{B(k_x - k_t, k_t)} \mathbb{I}_{[0,1]}(\delta). \quad (22) $$

If $k_t \ell > 1$ and $k_x - k_t > 1$, the derivative of the p.d.f. cancels in three points: $\delta \in \{0, \delta_m, 1\}$. Since $f_\Delta(0) = f_\Delta(1) = 0$, and $f_\Delta(\delta) \ge 0$, $\forall \delta \in (0, 1)$, this shows that

$$ 
\begin{aligned}
\delta_m &:= 1 - \left( \frac{k_t \ell - 1}{(k_x - 1)\ell - 1} \right)^{1/\ell} \\
&= 1 - \left( \frac{k_t}{k_x} \right)^{1/\ell} \left( 1 + \frac{(\ell + 1)k_t - k_x}{\ell k_x k_t - (\ell + 1)k_t} \right)^{1/\ell}
\end{aligned}
\quad (23) $$

is the unique maximum, i.e. the mode of this distribution. ■

**Remark.** If $k_t = 1$, then $B \sim \text{Beta}(1, k_x - 1)$ and $K := B^{1/\ell} = 1 - \Delta$ follows by definition a Kumaraswamy distribution $K(\ell, k_x - 1)$. This gives simpler formulas:

$$ \mathbb{E}[\Delta] = 1 - (k_x - 1)B(1 + 1/\ell, k_x - 1), \quad (24) $$

$$ \bar{\Delta} = 1 - \bar{K} = 1 - \left(1 - 2^{-\frac{1}{k_x-1}}\right)^{\frac{1}{\ell}}, \quad (25) $$

$$ \text{mode} = 1 - \left( \frac{\ell - 1}{(k_x - 1)\ell - 1} \right)^{\frac{1}{\ell}}. \quad (26) $$

Statistics (16), (17), and (18) are expressed to outline the quantity $1 - (k_t/k_x)^{1/\ell}$ already appearing in [20, Th. 2]. Quoting this article, “the amount of perturbation required to subvert neighborhood rankings diminishes with the local intrinsic dimensionality” $\ell$ of this neighborhood. For instance, for large $\ell$, this term further simplifies into $\approx \ell^{-1} \log(k_x/k_t)$, which

<figure><img src="image_5.png" /><figcaption>Fig. 4. Asymptotic p.d.f. of $\Delta$ as a function of $\delta \in [0, 0.4]$ for $k_x = 4$ (magenta) or $k_x = 100$ (olive green) and $k_t = 2$ and $\ell \in \{10, 20, \dots, 70\}$ (from dark to light).</figcaption></figure>

shows that $\ell$ is the key factor. It has a bigger impact than the ratio $k_x/k_t > 1$ due to the log scale. However, our previous article [20] also claims that this quantity is the “sufficient” amount of perturbation which is not true. More precisely, their Theorem 2 states that if the relative amount of perturbation $\delta$ is strictly bigger than $1 - (k_t/k_x)^{1/\ell} + \epsilon$, then $x$ has been modified into a point $y$ whose rank $k_y < k_t$. Yet, that $\epsilon$ is fuzzily defined in [20, Th. 2]: “For any sufficiently small real value $\epsilon > 0$”. Our result refines this statement: That amount of perturbation is almost sufficient in the sense that the attack is successful with probability $F_\Delta (1 - (k_t/k_x)^{1/\ell}) = 1 - I_{k_t/k_x}(k_t, k_x - k_t)$.

## V. EXPERIMENTAL WORK

### A. Experimental Protocol

The experimental protocol uses six datasets: ImageNet, CIFAR, BigANN, DEEP, MSSPACEV, MSTuring. The first four datasets are related to computer vision. They correspond to global feature vectors extracted from images thanks to a deep neural network (ResNet50 for ImageNet and CIFAR, GoogLeNet for DEEP [31]) or to local hand-crafted descriptors (SIFT for BigANN [32]). MSTuring and MSSPACEV [33] are related to web search. They consist of vector encoding of text documents and/or queries to capture the intent of the search better. ImageNet, CIFAR, and BigANN are classic computer vision datasets, whereas DEEP, MSSPACEV, and MSTuring are used in the NeurIPS’21 Approximate Nearest Neighbor Search Challenge<fnref n="3" />. Table II summarizes these data.

The experimental protocol is as follows. The NeurIPS’21 Approximate Nearest Neighbor Search Challenge offers a set of queries randomly sampled over each dataset. For each query, an exhaustive search finds the $k_x$-nearest neighbors in the dataset and their distances $\{d_i\}_{i=1}^{k_x}$ to the query. The minimum relative amount of perturbation is computed by $\delta = 1 - t/x$ where $t = d_{k_t}$ and $x = d_{k_x}$ are the distances of the $k_t$-th and $k_x$-th nearest neighbors. For each query, the index $\ell$,

<footnote n="3">³https://big-ann-benchmarks.com</footnote>
<table><caption>TABLE II
DETAILS ABOUT THE DATASETS</caption><thead><tr><th>dataset</th><th>d</th><th>type</th><th>(n, q)</th><th>k<sub>x</sub></th></tr></thead><tbody><tr><td>ImageNet</td><td>2048</td><td>float</td><td>(1,2M,10K)</td><td>1K</td></tr><tr><td>CIFAR</td><td>2048</td><td>float</td><td>(50K,10K)</td><td>1K</td></tr><tr><td>BigANN</td><td>128</td><td>uint8</td><td>(1B,10K)</td><td>100</td></tr><tr><td>DEEP</td><td>96</td><td>float</td><td>(1B,10K)</td><td>100</td></tr><tr><td>MSTuring</td><td>100</td><td>float</td><td>(1B,100K)</td><td>100</td></tr><tr><td>MSSPACEV</td><td>100</td><td>uint8</td><td>(1B,29K)</td><td>100</td></tr></tbody></table>

<figure><img src="image_6.png" /><figcaption>Fig. 5. Empirical p.d.f. of Hill estimations $\hat{\ell}$ (27) with the kernel density estimator of [35].</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Fig. 6. Comparison of the empirical and theoretical p.d.f. of the normalized r.v. $\tilde{\Delta}$ defined in Prop. 4 with $\ell_0 = 10$, $k_x = 1000$, $k_t = 1$.</figcaption></figure>

so-called local intrinsic dimensionality, is estimated using the maximum likelihood estimator, a.k.a. the Hill estimator [34]:

$$ \hat{\ell} = - \left( k_x^{-1} \sum_{i=1}^{k_x} \log(d_i/d_{k_x}) \right)^{-1} . \quad (27) $$

The protocol provides *q* pairs of measurements $\{(\hat{\ell}_i, \delta_i)\}_{i=1}^q$ (one per query). We consider the neighborhoods with similar estimation values $\hat{\ell}_i$ as independent realizations of our statistical model described by assumptions 1 and 2. Figure 5 shows that the datasets have different ranges of indices. The index $\ell$ takes values often bigger than 30 in CIFAR and ImageNet, whereas DEEP, MSSPACEV and MSTuring are peculiar with index values often below 5. Note that these ranges are weakly related to the space dimension (see Tab. II).

## B. Statistical Analysis

The kernel density estimator of [36] learns an empirical joint p.d.f. $\pi(\ell, \delta)$ defined over $\mathbb{R}^+ \times [0, 1]$ from the measurements. In the same way, we learn an empirical marginal p.d.f. $\hat{f}_L(\ell)$ from the estimations $\{\hat{\ell}_i\}_{i=1}^q$ (3rd cardinal spline KDE with Silverman rule [35]). Our goal is to compare the empirical joint p.d.f. $\pi(\ell, \delta)$ to the one based on our model, $f_\Delta(\delta|\ell)\hat{f}_L(\ell)$, coming from (22). Figure 6 shows a very good match between the empirical and joint models for ImageNet. The same observation holds for the other datasets (see figures in App. A).

For further investigation, we would like to compare the empirical marginal and the asymptotical p.d.f. of $\Delta$. To gather

a large number of observations, we normalize the LID index $\ell$ with the following transformation:

**Proposition 4.** Suppose that $\Delta$ follows the asymptotical distribution given in Prop. 2 with index $\ell$ and the ranks $(k_t, k_x)$, then $\tilde{\Delta} = 1 - (1 - \Delta)^{\ell/\ell_0}$ also follows the asymptotical distribution with the same ranks, but index $\ell_0$.

*Proof:* Since $B = (1 - \Delta)^\ell \sim \text{Beta}(k_t, k_x - k_t)$, then $\tilde{\Delta} = 1 - (1 - \Delta)^{\ell/\ell_0} = 1 - B^{1/\ell_0}$. ■

We apply this trick to create the samples $\{\tilde{\delta}_i\}_{i=1}^q$ with one common unique index value $\ell_0 = 10$. It is as if all the measurements came from independent neighborhoods, realizing the statistical model with index $\ell_0$. The empirical p.d.f. of $\tilde{\Delta}$ is learned with the method of [35]. Figure 7 compares this p.d.f. with the asymptotical model $f_\Delta$ in (22) for different pairs $(k_t, k_x)$. One can see that it fits the theoretical model very closely, although the datasets are of different natures, sizes, and setups.

Such a good fitting is surprising because we only made two assumptions about the data, and moreover, they are violated by some datasets. For instance, MSSPACEV and BigANN contains quantized vectors belonging to $\{0, 1, \dots, 255\}^d$. Therefore, the distances between points take discrete values, and this is a clear violation of assumption 2. Our model is indeed robust to tackle a fine enough granularity of the distance values.

## C. Discrepancies and Explanations

This section presents the limits of the proposed model. It first explains the light discrepancies visible in Fig. 7, and then exhibits typical scenarios where the model fails.

1) **Convergence Rate:** In Fig. 7, CIFAR and ImageNet p.d.f. shows a small shift of $\approx 0.03$ compared to the theoretical curve. This is because they do not yet reach the asymptotical regime as their size is not so large (see Tab. II). Indeed, a similar offset is already visible in Fig. 3 even for a dataset size of one million.
<figure><img src="image_8.png" /><figcaption>Fig. 7. Comparison of the empirical p.d.f. of the normalized data $\tilde{\Delta}$ and the related asymptotical model of Prop. 4 with $\ell_0 = 10$ and $(k_t, k_x) \in \{(1, 100), (10, 100), (1, 1000)\}$. Markers: $\mathbb{E}[\Delta]$ (△), $\tilde{\Delta}$ (○), and mode (□).</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>Fig. 9. Empirical average of Kolmogorov-Smirnov test values as a function of $\hat{\ell}$. The estimated indices are binned into intervals of length 5.</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>Fig. 8. Kolmogorov-Smirnov goodness of fit test value w.r.t. to the size of the dataset. Same setup as in Fig. 7.</figcaption></figure>

For the billion scale datasets of Tab. II, Figure 8 shows the Kolmogorov-Smirnov goodness of fit test value between the empirical and the asymptotical c.d.f. of $\tilde{\Delta}$ when downsizing the collection of points by a factor 10 or 100. This illustrates the slow convergence to the asymptotical model as $n$ increases.

2) **Inaccurate Estimation of the Index $\ell$:** All the empirical p.d.f.'s have a slightly different skewness than the theoretical plot. We do not have access to the index $\ell$; we can only estimate its value from the distances of the $k_x$ nearest neighbors. The measurement $\delta$ is normalized into $\tilde{\delta}$ by Prop. 4 applied with the estimated index $\hat{\ell}$. Even if $\delta$ were occurrences of r.v. $\Delta$, $\tilde{\delta}$ does not follow the normalized distribution due to the estimation noise in $\hat{\ell}$.

This discrepancy is almost not visible for CIFAR, ImageNet, and BigANN. For these datasets, the estimated index is rarely below 5, as shown in Fig. 5. We evaluate the inaccuracy of the Hill estimator by the Kolmogorov-Smirnov goodness of fit test value for typical estimations $\hat{\ell}$. Figure 9 shows that estimating indices smaller than 10 is indeed difficult. This is especially true for DEEP and may explain its heavier tail in Fig. 7. The joint p.d.f. displayed

in App. A confirms this phenomenon: for all datasets, the differences between empirical and theoretical are more visible at lower index values (i.e. on the left side of the heat map representation).

3) **Mixture of Distributions:** Figure 10 shows typical failures of the model (see also App. A). We use some of the earlier datasets (MSSPACEV, MSTuring, and DEEP) but on a specific setup where $k_t = 1$. Note that this setup is not an issue for BigANN, CIFAR, and ImageNet in Fig. 7.

Assumption 1 supposes that the distances from the query are drawn from a unique distribution. This might not be the case for some queries. We envisage the following cases: The $k_x$ smallest distances may correspond to:

1) a subset of documents matching the query,

2) a subset of documents not matching the query,

3) the union of two matching / non-matching subsets.

Cases 1 and 2 comply with the assumption of a unique distribution, but not case 3. Case 3 faces a mixture of two distance distributions, each of them following Assumption 2 but with a different index $\ell$ and also a different convergence speed to the asymptotical regime (2). The estimator (27) then gives a global value that may be irrelevant.

Note that MSSPACEV and MSTuring are collections of data related to web search with vector encodings of queries and documents. It is expected that a web search ends up with returned documents ranked first because they have a semantic connection to the query (i.e. a match) or because it statistically happens that their distances are small although they are not related to the query (i.e. a non-match). Case 3 might also happen with DEEP a collection of features extracted from "images of the web", quoting [31]. Over such a huge collection of pictures scrapped from the internet, duplicates or quasi-copy of some query images likely exist in the dataset, yielding case 3.

We now explain with a hand-waving rationale that the mixture of distributions explains the heavy tails in Fig. 10. Suppose, for instance, that the $k_m$ nearest neighbors are matches following a different distribution than the $k_x - k_m$ followers, with $k_t \le k_m < k_x$. Measurement $\hat{\ell}$ may be corrupted by this mixture of distributions, but since it is
<figure><img src="image_11.png" /><figcaption>Fig. 10. Cases of failure. Comparison of the empirical p.d.f. of the normalized data $\bar{\Delta}$ and the asymptotical model of Prop. 4) with $\ell_0 = 10$ and $(k_t, k_x) = (1, 100)$. Markers: $\mathbb{E}[\Delta](\circ)$, $\bar{\Delta}(\circ)$, and mode (□).</figcaption></figure>

essentially the inverse of an average over $k_x$ distances (27), the estimate is robust provided that $k_m \ll k_x$. On the contrary, measurement $\delta$ is sensitive to distance $t$ (1). Therefore, if $k_t < k_m$, distance $t = d_{k_t}$ is expected to be significantly smaller than the others, and $\delta$ gets close to 1. Moreover, a value $\delta \lesssim 1$ is indeed spread over a wide upper interval due to the normalization mapping of Prop. 4 tuned with a very low ratio $\ell_0/\ell$. Figure 9 indeed shows that DEEP, MSSPACEV, and MSTuring have queries with low estimates $\ell$. This amplifies the discrepancy and explains the heavy upper tail. This means that, under case 3, the perturbation is bigger than statistically predicted by the model. These failures do not happen in Fig. 7 where $k_t = 10$ because $1 < k_m < 10$ in DEEP, MSSPACEV, and MSTuring. Indeed, the larger $k_t$ the less likely a case 3 occurs.

Case 3 is not expected on CIFAR and ImageNet. For these last two datasets, the feature vectors are extracted with a classifier deep neural network, and the images come from a collection meant for classification. For instance, if the query is an image of a dog, it will match the hundreds of dog images in the collection. Therefore, case 1 is likely, and this does not violate our assumption.

# VI. DISCUSSIONS

## A. Extensions

The analysis can be extended to two cases: 1) The modified point goes away from a reference point in the sense that the target rank $k_t$ is bigger than the actual rank $k_x$, 2) It is the query $q$ that is perturbed, and the dataset points are untouched. The query is pushed closer to (away from) a target dataset point so that its rank decreases (resp. increases).

The first point is easily handled by re-defining $\Delta_n = T_n/X_n - 1$ with $T_n \ge X_n$.

**Proposition 5.** For two ranks $k_x < k_t$, the relative amount of perturbation $\Delta_n$ converges in distribution to $\Delta = B^{-1/\ell} - 1$ with $B \sim \text{Beta}(k_x, k_t - k_x)$, as the size $n$ of the dataset increases.

*Proof:* From Prop. 2, the ratio of two neighbor distances converges to $B^{1/\ell}$ with $B$ following a Beta distribution. Here, we have $X_n < T_n$, so that $(X_n/T_n)^\ell \le 1$ converges to $\text{Beta}(k_x, k_t - k_x)$ and $\Delta_n$ converges to $\Delta = B^{-1/\ell} - 1$. ■

The second point also applies, provided the index $\ell$ now characterizes the distances from the targeted dataset point. As $n$ increases, the query and this dataset point get closer (for a fixed rank $k_x$), and Amsaleg et al. argue that they asymptotically share the same index value [20]. In other words, the index $\ell$ can be considered a very smooth continuous function over the location in the space.

## B. Limitations and Implications

The first limitation stems from the basic tools underlying the study: the Euclidean distance and the assumption that the adversarial point is pushed toward the target over a straight line. This may not make sense for data points lying over manifolds. This study could be generalized to more complex differentiable geometries adapted to the nature of the manifold. Another possibility is to capture the geometry directly from the data points thanks to the complete graph of the nearest neighbors [37], [38].

The second limitation comes from the study taking place in the feature space. The retrieval vulnerability also depends on the ability to forge an object, say an image, whose extracted feature vector exactly corresponds to $y$. This point is out of our scope, and works like [19] and [17] give experimental evidence as far as description with deep neural networks is concerned. If one knows the Lipschitz constant $C$ of the neural network, then $C^{-1}\Delta$ gives a statistical lower bound of the Euclidean distortion in the input space. Targeting point $y$ reduces the distortion in the feature space but not necessarily in the input space. Moreover, the image whose feature vector equals $y$ may not exist because the description may not be a surjection.

The amount of perturbation concentrates to lower values as $\ell$ increases. The implication is to extract features whose local intrinsic dimensionalities are low or at least under control. Including an entropy regularizer in the training might be a good direction as done recently in [39] or [40]. This regularization evenly spreads the feature vectors over the unit hypersphere and would alleviate the increase of $\ell$.

# VII. CONCLUSION

This work shows that the relative amount of perturbation necessary to delude the NN search is not driven by the representation dimension $d$ of the feature space but by the Local Intrinsic Dimension. This amount not only decreases in expectation but also concentrates around this expectation when the Local Intrinsic Dimension increases for a fixed rank ratio $k_t/k_x$. The experimental work warns that the LID takes a wide range of values from one dataset to another, but also within a dataset. This means that some feature spaces or regions of a feature space are more vulnerable than others. This warns the designer of a feature extraction on the importance of controlling the LID.
REFERENCES

[1] X. Wu, V. Kumar, J. R. Quinlan, J. Ghosh, Q. Yang, H. Motoda, G. J. McLachlan, A. Ng, B. Liu, S. Y. Philip et al., "Top 10 algorithms in data mining," *Knowledge and information systems*, vol. 14, no. 1, pp. 1–37, 2008.

[2] X. Gu, L. Akoglu, and A. Rinaldo, "Statistical analysis of nearest neighbor methods for anomaly detection," *arXiv preprint arXiv:1907.03813*, 2019.

[3] Y.-Y. Yang, C. Rashtchian, Y. Wang, and K. Chaudhuri, "Robustness for non-parametric classification: A generic attack and defense," in *Proc. of AISTATS*. PMLR, Aug 2020, pp. 941–951.

[4] L. Devroye, L. Gyorfi, A. Krzyzak, and G. Lugosi, "On the strong universal consistency of nearest neighbor regression function estimates," *The Annals of Statistics*, vol. 22, no. 3, pp. 1371–1385, 1994.

[5] G. H. Chen and D. Shah, *Explaining the Success of Nearest Neighbor Methods in Prediction*, 2018.

[6] D. Sharma, R. Shukla, A. K. Giri, and S. Kumar, "A brief review on search engine optimization," in *Int. Conf. on Cloud Computing, Data Science & Engineering (Confluence)*, 2019, pp. 687–692.

[7] J.-P. Stahl, R. Cohen, F. Denis, J. Gaudelus, A. Martinot, T. Lery, and H. Lepetit, "The impact of the web and social networks on vaccination, new challenges and opportunities offered to fight against vaccine hesitancy," *Médecine et Maladies Infectieuses*, vol. 46, no. 3, pp. 117–122, 2016.

[8] D. Bahri, H. Jiang, and M. Gupta, "Deep k-NN for noisy labels," in *Proceedings of the 37th International Conference on Machine Learning*. PMLR, 13–18 Jul 2020, pp. 540–550.

[9] S. Weerasinghe, T. Abraham, T. Alpcan, S. M. Erfani, C. Leckie, and B. I. P. Rubinstein, "Closing the big-LID: An effective local intrinsic dimensionality defense for nonlinear regression poisoning," in *Proc. of the 30th IJCAI*, 8 2021, pp. 3176–3184.

[10] A. T. Nguyen and E. Raff, "Adversarial attacks, regression, and numerical stability regularization," *AAAI'19 Workshop on Engineering Dependable and Secure Machine Learning Systems*, 2018.

[11] C. Sitawarin and D. Wagner, "On the robustness of deep k-nearest neighbors," in *IEEE Security and Privacy Workshops*. IEEE, 2019, pp. 1–7.

[12] G. Cohen, G. Sapiro, and R. Giryes, "Detecting adversarial samples using influence functions and nearest neighbors," in *Proceedings of the IEEE/CVF Conference on CVPR*, June 2020.

[13] N. Papernot and P. McDaniel, "Deep k-nearest neighbors: Towards confident, interpretable and robust deep learning," *arXiv preprint arXiv:1803.04765*, 2018.

[14] X. Ma, B. Li, Y. Wang, S. M. Erfani, S. Wijewickrema, G. Schoenebeck, D. Song, M. E. Houle, and J. Bailey, "Characterizing adversarial subspaces using local intrinsic dimensionality," in *International Conference on Learning Representations*, 2018.

[15] A. Athalye, N. Carlini, and D. Wagner, "Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples," in *Proceedings of the 35th ICML*, vol. 80. PMLR, 10–15 Jul 2018, pp. 274–283.

[16] T.-T. Do, E. Kijak, L. Amsaleg, and T. Furon, "Enlarging hacker's toolbox: deluding image recognition by attacking keypoint orientations," in *IEEE ICASSP*, 2012, pp. 1817–1820.

[17] G. Tolias, F. Radenovic, and O. Chum, "Targeted mismatch adversarial attack: Query with a flower to retrieve the tower," in *Proc. of the IEEE/CVF ICCV*, 2019, pp. 5037–5046.

[18] Y. Xiao and C. Wang, "You see what i want you to see: Exploring targeted black-box transferability attack for hash-based image retrieval systems," in *Proc. of the IEEE/CVF CVPR*, June 2021, pp. 1934–1943.

[19] S. Sabour, Y. Cao, F. Faghri, and D. J. Fleet, "Adversarial manipulation of deep representations," in *ICLR*, 2016.

[20] L. Amsaleg, J. Bailey, A. Barbe, S. M. Erfani, T. Furon, M. E. Houle, M. Radovanović, and N. X. Vinh, "High intrinsic dimensionality facilitates adversarial attack: Theoretical evidence," *IEEE Transactions on Information Forensics and Security*, pp. 1–1, 2020.

[21] L. Amsaleg, O. Chelly, T. Furon, S. Girard, M. E. Houle, K.-I. Kawarabayashi, and M. Nett, "Extreme-value-theoretic estimation of local intrinsic dimensionality," *Data Mining and Knowledge Discovery*, vol. 32, no. 6, pp. 1768–1805, Nov. 2018.

[22] Y. Xing, Q. Song, and G. Cheng, "Predictive power of nearest neighbors algorithm under random perturbation," in *Proc. of The 24th AISTATS*, ser. Proceedings of Machine Learning Research, vol. 130. PMLR, 13–15 Apr 2021, pp. 496–504.

[23] C. Sitawarin, E. Kornaropoulos, D. Song, and D. Wagner, "Adversarial examples for k-nearest neighbor classifiers based on higher-order voronoi diagrams," in *Advances in Neural Information Processing Systems*, vol. 34, 2021, pp. 15486–15497.

[24] L. Wang, X. Liu, J. Yi, Z.-H. Zhou, and C.-J. Hsieh, "Evaluating the robustness of nearest neighbor classifiers: A primal-dual perspective," *arXiv preprint arXiv:1906.03972*, 2019.

[25] Y. Wang, S. Jha, and K. Chaudhuri, "Analyzing the robustness of nearest neighbors to adversarial examples," in *International Conference on Machine Learning*. PMLR, 2018, pp. 5133–5142.

[26] L. Devroye, L. Gyorfi, and G. Lugosi, *A Probabilistic Theory of Pattern Recognition*. Springer-Verlag, 1996.

[27] N. H. Bingham, C. M. Goldie, and J. L. Teugels, *Regular Variation*, ser. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 1987.

[28] W. Feller, *An Introduction to Probability Theory and Its Applications*, 2nd ed. Wiley, 1991, vol. 2.

[29] H. A. David and H. N. Nagaraja, *Order Statistics*, 3rd ed. Wiley, 2003.

[30] V. Bonnaillie-Noël, "Méthode de Laplace et de la phase stationnaire," ENS de Cachan, Tech. Rep., 2004.

[31] A. Babenko and V. Lempitsky, "Efficient indexing of billion-scale datasets of deep descriptors," in *Proc. of IEEE/CVF CVPR*, 2016, pp. 2055–2063.

[32] H. Jégou, R. Tavenard, M. Douze, and L. Amsaleg, "Searching in one billion vectors: re-rank with source coding," in *IEEE ICASSP*. Prague, Czech Republic: IEEE, May 2011, pp. 861–864.

[33] M. Qi and Q. Chen, "Github of MSSPACEV." [Online]. Available: https://github.com/microsoft/SPTAG/tree/main/datasets/SPACEV1B

[34] B. M. Hill, "A Simple General Approach to Inference About the Tail of a Distribution," *The Annals of Statistics*, vol. 3, no. 5, pp. 1163 – 1174, 1975.

[35] D.-T. Pham, "Fast algorithms for mutual information based independent component analysis," *IEEE Transactions on Signal Processing*, vol. 52, no. 10, pp. 2690–2700, 2004.

[36] Z. I. Botev, J. F. Grotowski, and D. P. Kroese, "Kernel density estimation via diffusion," *The Annals of Statistics*, vol. 38, no. 5, pp. 2916 – 2957, 2010.

[37] A. Iscen, G. Tolias, Y. Avrithis, T. Furon, and O. Chum, "Efficient diffusion on region manifolds: Recovering small objects with compact cnn representations," in *Proceedings of the IEEE conference on computer vision and pattern recognition*, 2017, pp. 2077–2086.

[38] A. Iscen, Y. Avrithis, G. Tolias, T. Furon, and O. Chum, "Fast spectral ranking for similarity search," in *Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition*, 2018, pp. 7632–7641.

[39] A. El-Nouby, N. Neverova, I. Laptev, and H. Jégou, "Training Vision Transformers for Image Retrieval," Feb. 2022, working paper or preprint.

[40] E. Pizzi, S. D. Roy, S. N. Ravindra, P. Goyal, and M. Douze, "A self-supervised descriptor for image copy detection," in *Proc. of the IEEE/CVF CVPR*, 2022, pp. 14532–14542.

<figure><img src="image_12.png" /></figure>

**Teddy Furon** (Ph.D. Telecom ParisTech (2002), Senior Member, IEEE) is Directeur de Recherche at Inria centre at Rennes University. His research interests include the security related to multimedia, signal processing, and artificial intelligence. He has been an Associate Editor for four journals, including IEEE Transactions on Information Forensics and Security. He has been named the French AID chair in Security of Artificial Intelligence.
# APPENDIX

## MORE EXPERIMENTAL RESULTS

This appendix shows the figures comparing the empirical joint p.d.f. $\pi(\ell, \delta)$ (learned with k.d.e. [31]) and its theoretical counterpart on the left, and, below, the comparison of the empirical and theoretical p.d.f. of the normalized r.v. $\tilde{\Delta}$ defined in Prop. 4 (with $\ell_0 = 10$). Theoretical expectation ($\triangle$), median ($\circ$), and mode ($\square$) are also displayed.

Figures 11, 12, 13, 14, 15, 16, and 17 show examples validating the theoretical model.

Figures 18, 19, and 20 show examples of failure.

<figure><img src="image_13.png" /><figcaption>Fig. 11. BigANN with $k_x = 100, k_t = 1$.</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>Fig. 13. DEEP with $k_x = 100, k_t = 10$.</figcaption></figure>

<figure><img src="image_15.png" /><figcaption>Fig. 12. BigANN with $k_x = 100, k_t = 10$.</figcaption></figure>

<figure><img src="image_16.png" /><figcaption>Fig. 14. MSSPACEV with $k_x = 100, k_t = 10$.</figcaption></figure>
<figure><img src="image_17.png" /><figcaption>Fig. 15. MSTuring with $k_x = 100$, $k_t = 10$.</figcaption></figure>

<figure><img src="image_18.png" /><figcaption>Fig. 17. ImageNet with $k_x = 1000$, $k_t = 1$.</figcaption></figure>

<figure><img src="image_19.png" /><figcaption>Fig. 16. CIFAR with $k_x = 1000$, $k_t = 1$.</figcaption></figure>

<figure><img src="image_20.png" /><figcaption>Fig. 18. DEEP with $k_x = 100$, $k_t = 1$.</figcaption></figure>
<figure><img src="image_21.png" /><figcaption>Fig. 19. MSSPACEV with $k_x = 100$, $k_t = 1$.</figcaption></figure>

<figure><img src="image_22.png" /><figcaption>Fig. 20. MSTuring with $k_x = 100$, $k_t = 1$.</figcaption></figure>