Adversarial Examples for k-Nearest Neighbor Classifiers Based on Higher-Order Voronoi Diagrams
Authors: Chawin Sitawarin
Evgenios M. Kornaropoulos
Dawn Song
David Wagner
Venue: NeurIPS 2021 Poster (2021)
Keywords: adversarial examples
k-nearest neighbors
robustness
Voronoi diagram

Abstract: Adversarial examples are a widely studied phenomenon in machine learning models. While most of the attention has been focused on neural networks, other practical models also suffer from this issue. In this work, we propose an algorithm for evaluating the adversarial robustness of $k$-nearest neighbor classification, i.e., finding a minimum-norm adversarial example. Diverging from previous proposals, we propose the first geometric approach by performing a search that expands outwards from a given input point. On a high level, the search radius expands to the nearby higher-order Voronoi cells until we find a cell that classifies differently from the input point. To scale the algorithm to a large $k$, we introduce approximation steps that find perturbation with smaller norm, compared to the baselines, in a variety of datasets. Furthermore, we analyze the structural properties of a dataset where our approach outperforms the competition.

Adversarial Examples for k:-eerest Neighbor Classifiers Based on Higher-Order Voronoi Diagrams
Chawin Sitawarin
Evgenios M. Kornaropoulos George Mason University evgenios@gmu edu edu
UC Berkeley chawins@eecs. htwpnneeeeeeeebbbbeeeeeeeeeeeeee berkeley. edu
Dawn Song
David Wagner
UC Berkeley dawnsong@cs. berkeley.ed edu
UC Berkeley dawêcs. berkeley.cc..oc...........ee. edu
Abstract
Adversarial examples are a widely studied phenomenon in machine learning models. While most of the attention has been focused on neural networks, other practical models also suffer from this issue. this work, we propose an algorithm for evaluating the adversarial robustness of k-nearest neighbor classification, i.e., finding a minimum-norm adversarial example. Diverging from previous proposals, propose the first geometric approach by performing search that expands outwards from a given input point. On a high level, the search radius expands to the nearby higher-order Voronoi cells until we find cell that classifies differently from the input point. To scale the algorithm to large k, we introduce approximation steps that find perturbation with smaller norm, compared the baselines, in a variety of datasets. Furthermore, we analyze the structural properties of a dataset where our approach outperforms the competition.
Introduction
is well-known that machine learning models easily be misled by maliciously crafted inputs, called adversarial examples, which are generated by adding tiny perturbation to test samples [Biggio al., 2013. Szegedy the context of neural networks, leaving the problem largely unexplored for other classifiers. The k- nearest neighbor, or simply A-NN, classifier a simple yet widely used model in various applications such as data mining, recommendation. and anomaly detection systems where interpretability and simplicity are preferred [Wu et al., 2008]. This non-parane non-paraeetric classifier does not require training phase and has well well-understood and elegant geometric foundation [Okabe et al., 1992]. &-NN is also an active area of research with lots of developments in popular libraries like Google's 's ScaNN [Guo et al., 2020] and Facebook's 's FAISS [Johnson et al., 2017]. In recent works [Papernot and McDaniel, 2018, Dubey et al.. 2019, Sitawarin and Wagner, 2019b), k-NN is combined with neural networks to enhance the robustness and the interpretability. Despite the importance of k-NN, there are only handful of works that study its robustness [Wang et al., 2018, Yang et al., 2020, Wang et al., 2019, Sitawarin and Wagner, 2019a, 2020].
2013, Goodfellow al., 2015]. Adversarial examples are often studied in
The first step towards evaluating the robustness of classifier generate an adversarial example that is close to given test point, under some definition of closeness. In the case of I--N where 1, this problem is challenging as the computation involves high-dimensional polytopes that satisfy set of geometric properties, the so-called Voronoi cells.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

In this work, we propose the GeoAdEx algorithm for finding adversarial examples for k-NN classifiers. GeoAdEx is the first algorithm that exploits the underpinning geometry of the h-NN classifier. Specifically, our approach performs a principled search on the underlying high-order Voronoi diagram by expanding the search radius around the test point until finds an adversarial, or simply incorrect, classification. The geometric foundation of GeoAdEx allows to locate nearby adversarial cells that the other attacks typically miss. GeoAdEx follows the footsteps of the work by Jordan et al. [2019] who exploited the geometry of neural networks for verifying the outputs. Our algorithmic approach stands in sharp contrast to previous attacks for k-NN [Yang et al., 2020, Wang et al., 2019] which refine the exhaustive approach by heuristic-basee based filtering.
Furthermore, we introduce optimizations and approximations the main algorithm, and as result, the experiments show that GeoAdEx discovers the smallest adversarial distance compared to all of the baselines in the vast majority of our experiments for E (3. 5. 7). GeoAdEx finds up to 25% smaller mean adversarial distance compared to the second best attack. We note that one inherent shortcoming of our geometrie approach is the increased computation time, an aspect that can be further improved.
Finally, we present experiments that demonstrate that GeoAdEx performs significantly better when points from different classes are "mixed" together, i.e., there is no clear separation between classes. On a high level, such a setup generates a more intricate spatial tessellation with nearby cells that alternate classes. In this challenging case, GeoAdEx performs up 5x better than the baselines.
2 Background and Related Work
2.1 Background
Let X = (z1...., Fn, be a set of points from R4, also called generators, and let Y
(yi,...,
................................ .n.
be the class of each point from set of possible classes {l...., c). Let d(x, x') denote metric
between x' E RRd. Let ((k) ()) be the set of all possible subsets consisting of l points from X, i.., Z
( ..... L
L (. where L {_........ Fik y. Big E X and (
We define as order-k Voronoi cell associated with 2,(4) the set V(z,")) that includes the points of Rd that are closer to -,(h) than any other k points of X. More formally:
v(L = {p max{d(p, 1)I E (x0 s min(d(p, E X }
With the term Voronoi facet, or simply facet, refer boundary of an order-k: Voronoi cell. We define as bisector B B x6,} the set of points from Rd that are equidistant from va E X and xg E X. There is tight connection between bisectors and facets. Every Voronoi facet is part of bisector, but not every bisector, (*) in total, includes a facet. We call the bisectors that do include a facet active bisectors and those that do not inactive bisectors. We also note that an order-k Voronoi cell has at most k(n k) facets. The collection of order-k Voronoi cells for all L is called order-k Voronoi diagram. In this work, we assume the standard non-cocircularity assumption' to avoid degenerate cases. We only consider the Euclidean distance for the k-NN, i.e., d(sta, ||.. 2-l12-
Up to this point, we have not used the classes of the X. In this work. we focus on k-NN classifiers that classify based on the majority (class) vote of the k-nearest points. We define as adversarial cell with respect to (z; y) any order-k Voronoi cell that has different majority than label y. We denote with A(x) the set of all adversarial cells with respect to (I., v). With the term adversarial faces with respect to (x. y) we refer to a facet that belongs to cell from A(z).
2.2 Related Work
Adversarial Robustness of k-NN Classifiers. Wang et al. [2018] study the robustness property of k-NN classifiers from a theoretical perspective. The authors show that a k-NN classifier can be as robust the optimal Bayes classifier given sufficiently large number of generators and k. Wang et al. [2018] and Yang et al. [2020] also propose potential methods for improving the robustness of k-NN by pruning away some of the "ambiguous" generators. Other works consider different alternatiees for
IIn practice this can be achieved by adding a small random noise on each generator to break potential cocircularity between them.

---

enhancing the robustness of neural networks by combining them with k-NN. [Papernot and McDaniel, 2018, Sitawarin and Wagner, 2019b, Dubey al., 2019]
Attacks on k-NN Classifiers. Sitawarin and Wagner [2019a, 9a, 2020] propose method for finding minimum-nore norm adversarial examples on k-NN and deep k--N classifiers [Papernot and McDaniel, 2018). Their method approximates a k-NN classifier with soft differentiable function adversarial examples can be found via a gradient- based optimization algorithm. While the approach is efficient and scalable to large k, it provides no guarantee for finding the nearest adversarial example and overlooks the geometry of k-NN.
Yang ct al. [2020] and Wang et al. [2019] take similar approach for finding the adversarial example closest a given test z, Their method follows an exhaustive search by computing the distance between r and all the Voronoi cells that have different class from X. Both of them show that this but does not scale well for k > Consequently, they introduce
can be done exactly when heuristics to improve the efficiency by choosing only subset of the Voronoi cells. However, in the process, they lose the optimality guarantee on the resulted adversarial example. More importantly, the heuristics will miss an exponential number of cells as k increases.
Attacks Based on Geometric Insights. The problem of verifying or finding the nearest adversarial examples in neural networks is an active research direction where solutions still do not scale to satisfactory degree [Huang et al., 2017, Katz et al., 2017, Tjeng et al., 2017, Wong and Kolter, 2018, Weng et al., 2018, Cohen et al., 2019, Jordan et al., 2019]. Among these works, Jordan et al. [2019] proposed an alternative for a ReLU network, using a geometric approach. Specifically, the authors notice that piecewise linear networks partition the imput space into numerous polytopes where points of the same polytope are classified with the same label. Armed with this observation, they propose an algorithm that iteratively searches through these polytopes that are further away from the test sample until they find a polytope with a different label.
3 The GeoAdEx Algorithm
Objective. The goal of the algorithm is find the smallest perturbation 8 that moves a test point (xr, y) to an adversarial cell. This objective can be expressed as the following optimization problem:
8"
arg min
||0112
s.t. x 5 A(x)
We define as E optimal adversarial distance where ex = 1|0* The norm of any other (non-optimal) perturbation 5 that misclassifies (z. y), i.e., x E A(x), is simply called adversarial distance.
A First Approach. The constraint of the above formulation implies that + 8 must be member of an adversarial cell from A(x). A simple approach to solve this minimization is to build a series of optimization problems, one for each of the cells in A(z), and pick the solution with the minimum adversarial distance. Unfortunately, this would require solving O(()) quadratic programs each of which has k(n k) constraints. While this complexity may be manageable when A = 1 and n is small, it does not scale with k. On high level, Yang al. [2020) and Wang et [2019] take this approach and additionally develop heuristics to scale to cases with k > 1.
The GeoAdEx Approach. The core idea of GeoAdEx is to perform a principled geometric explo- ration around the test point GeoAdEx processes order-k Voronoi cells à la breadth-first search until discovers an adversarial cell. Algorithm provides a pseudocode of the main steps of GeoAdEx, 3-NN classifier with two classes. In the fol-
and Figure illustrates some steps of GeoAdEx lowing subsections, we explain these steps in detail and describe performance speedups as well as approximation steps scale the algorithm to k > 1.
3.1 Data Structures
We maintain a priority queue PQ as an auxiliary data structure that is defined for given test point (I,y). PQ tracks the progress made so far towards locating the optimal adversarial distance.
3

---

(1.2.))
(1.2.5)
(1.34)
(1.3,5)
(2,3,5)
X Test Point
(3,4,5)
[3.4.8]
(3,5,6)
(2.5
(3.5.))
(4.5.8)
(5.7.8)
(4,7.8) 383
Figure I: GeoAdEx on a Voronoi diagram for k 3 in IR? with two classes. The color of each numbered generator point shows its class, and the color of each cell indicates its classification outcome. The illustration presents the step where GeoAdEx has processed the facets of ((22, 5, 6}) and transitioning the next closest cell ((2,, 3, 5}). The arrows indicate the facets that are inserted to priority queue PQ. When GeoAdEx terminates, outputs the closest adversarial facet (orange line); ; this transition is indicated with the orange arrow, and the orange triangle is the optimal adversarial example for
Algorithm 1: GeoAdEx Algorithm
Data: Test point (x.
Result: Adversarial distance
Initialize the smallest adversarial distance found so far as e f- o0;
Initialize PQ by inserting the facets of the order-k Voronoi cell that falls into. Mark this cell as visited;
Call deleteMin from PQ until the returned facet is part of an unvisited order-k Voronoi cell. Initialize Y to this unvisited Voronoi cell;
while V is not an adversarial cell do
Find the set of facets & that comprise unvisited cell vr (Section 3.2);
Compute the distance between query point and each of the facets in & (Section 3.3);
If (i) facet from & is adversarial facet, and (ii) the distance this adversarial facet implies smaller
than e, then update e;
Insert to PQ the facets in & with their distance smaller than e;
Call deleteMin from PQ until the returned facet is part of an unvisited order-k Voronoi cell. Update T to the new unvisited Voronoi cell;
10 end
11 an adversarial facet is removed from PQ via delete.in, the algorithm return the optimal adversarial distance (see Lemma l); return c;
Specifically, PQ performs the operations insert (resp. deleteMin) where the input (resp. output) is a facet the order-k Voronoi diagram of X. Every facet in PQ is accompanied by the distance between the test point and the facet. Priority is given to the facet with the minimum distance to x. We also need to mark which Voronoi cells are processed. For that, we use a hash table (Python's native dictionary object) that has entry for every order-k Voronoi cell that the algorithm has visited. We refer to Voronoi cells that are part of the dictionary as visited and those that are not as unvisited.
3.2 Find Neighbors of Voronoi Cell
Line 3 of Algorithm 1, GeoAdEx discovers an unvisited order-k Voronoi cell V. In Line GeoAdEx needs to find the facets that comprise V, which is equivalent to finding the Voronoi cells that are neighboring with cell V. We present three options for implementing the discovery of neighbors; the choosing among them depends the application, the size of the dataset, and the value of k.

---

(A) Neighbors via Order-k Voronoi Diagram. The exact computation of an order-k Voronoi diagram in high dimensions constitutes a computationally challenging task. The cost of this option amortizes when there is a large number of test points to be processed, and the dataset is fairly small in size and dimension. However, it is highly unlikely to scale when
which the goal of our work.
(B) Neighbors via Enumerating Bisectors. In this approach, one has to process a quadratic number of bisectors that are potentially active with respect to the Voronoi cell v (see the definition from Section 2). Interestingly, we can filter out this set by only considering the bisectors whose generator, exactly one of the two, also generates cell V. Consequently, the task of finding the facets of the current cell V is reduced to testing the activeness of k(n k) bisectors. Jumping ahead, this step can be accomplished simultancously with computing distance from æ to each bisector so we defer its analysis for Section 3.3. For comparison, the complexity of this step is (ppoly(n n, d, k)) without any speedups, and in the worst case, which is extremely unlikely in practice, it can be called up to N times where N is the number of all cells (N is ((H)))
(C) Neighbors via Order-1 Voronoi Diagram. This approach is the middle ground between the first two. That is, it still tests whether bisector is active, much like (B), but it uses the Voronoi diagram, much like (A), to reduce the number of bisectors to test. Given a Voronoi cell with & genera- tors, e.g., V((=1,..., 3k-1 vxk) we know that its neighboring cells must have set of generators I,,,, that differs by exactly one point, e.g., V( 21)), We draw a connection between the
Voronoi diagrams of order 1 and k and show that the new point on must be neighboring with at least one of the order-1 cells V (((1)), (. proof be found in Appendix D.
We formalize this in Theorem 1, and its
Theorem 1. Let S {=1....... (........0 (xx....,KK_1 C X be set of k - generators. Let Tb. 2₁ two generators such that Ik. 21 & S. If VSS U {xx}) and V(S J {xi}) are two neighboring order-k Voronoi cells, then the order-1 Voronoi cell [((xi) is neighboring with at least one of the ((1z1))...., V((xx-1)) (Hzx)).
X be
With this insight, we can narrow down significantly the number of bisectors considered in ap- proach (B). More formally, let nb(x') denote the set of generators of order-1 Voronoi cells that neighbor with (a²)) Let V be the Voronoi cell V( xx)). By Theorem it is enough {x1,..., zz)-
to consider the bisectors between
{21...., 2 and E' (Ui_,
Hence, the total number of bisectors we need to test is at most is I nb(x;)) Assuming that = max; [nb(x;)),, ). the number of bisectors cannot exceed &.2.. Hence, approach (C) is much faster than approach (B) when A < In this work, use approach (B) for the k 1 case. However, in order to scale to large datasets and >> 1, we propose some approximations steps that are rooted in approach (C) later in Section 3.5.2.
3.3 Computing Distance & Testing Activeness
Now we describe Line Algorithm 1, i.e. how to compute the distance between a point x and a facet. Then, expanding this process, we detail how to test the activeness of bisectors.
Distance computation.
Voronoi cell a polytope that can also be described as an intersection
of halfspaces: {a Az < b}. A bisector can be described as a hyperplane: {a (z. a) = i). The corresponding facet needs to both be part of the polytope and satisfy the equation of the hyperplane. Thus, the shortest distance from r to a facet is given by the square root of the optimum of the following quadratic program:
min ||= - x
s.t. Az < b and (2, = bb
This problem can be solved by any off-the-shelf solver, but in Appendix F, we describe faster method also used by Wang et [2019].
Testing Bisector Activeness. Assuming that {= A2 < b) * 0, the bisector (2, â) = b is active if and only if Eqn. (2) is feasible since their intersection has to be non-empty. In case this problem
5

---

is infeasible, the bisector is inactive. From duality theory, we know that Eqn. (2), i.c. the primal, is feasible and only if the dual objective is unbounded since the dual problem is always feasible in this case. Checking the unboundedness can be accomplished as we are solving Eqn. (2) in its dual form so we can combine the steps of "distance computation" and "testing activeness" into a single function that either returns the distance or indicates that the bisector is inactive.
3.4 Optimality of GeoAdEx
Here, we formally state two lemmas that together prove the output optimality of GeoAdEx. The next lemma is straightforward as it is direct consequence of Lemma C.2 from Jordan et al. [2019]. For completion, we prove it in Appendix D.
Lemma (Correctness of GeoAdEx). Provided no time limil, GeoAdEx terminates when finds the optimal adversarial examples or equivalently, one of the solutions of Eqn. (1).
The next lemma states that if GeoAdEx terminates early, i.c. in case we enforce a time limit for performance purposes (see Section 3.5.2), it can still guarantee a lower bound to e*. Specifically, the distance to æ from the most recent facet deleted from PQ serves lower bound to E".
Lemma 2 (Lower bound guarantee). If GeoAdEx terminates early, the distance from test point to the last deleted facet facet from PQ is lower bound to the optimal adversarial distance e-
We note that if GeoAdEx terminates early, then serves as upper bound of et None of the previous approaches on adversarial examples for k-NN provide both an upper and lower bound guarantee.
3.5 Towards Scaling GeoAdEx
For simplicity, in Algorithm 1, present the main algorithmic steps that need be performed to compute the optimal adversarial distance using the geometric structure of the problem. In this section delve into details how accelerate the performance of GeoAdEx by performance optimization and approximation steps.
3.5.1 Optimizing Computation Time
We introduce four performance optimizations that significantly speed up GeoAdEx. We present the two most important ones here and the rest in Appendix E.
(I) Pruning Distant Facets. Given any adversarial distance, e.g., the intermediate result from Algorithm 1, we know that any facet that is more than afar from æ is not the facet associated with the optimal adversarial distance, i.e., acts as upper bound that is refined during the execution. Hence, we can safely filter out these facets, and it is unnecessary to compute their distance to æ, test activeness, insert them to PQ. This technique distance computation (Section 3.3). A benefit of our principled geometric approach is that we can apply geometric arguments eliminate redundant computation Voronoi cells that are far away
be used both before and during the facet
(II) Rethinking the Initialization of 6, Recall that Line of Algorithm I initializes to ao. Given the upgraded role of in the previous paragraph, is clear that a non- simplisiiiiic initialization would filter out more unnecessary computation early on and scale the overall performance. For our experiments, we run Sitawarin and Wagner [2020] to initialize since it yields reasonable and is faster than the other attacks.
3.5.2 Acceleration via Approximations
As mentioned in Section 3.2, approach (C) for finding the neighbors of an order-k Voronoi cell still requires the knowledge of the first-order cells. This can be obtained by either computing the entire order-1 Voronoi diagram or enumerating all possible facets of order- 1 cells. Nonetheless, first-order cells in high-dimension dataset may have large number of neighbors, and building a Voronoi diagram can easily become a bottleneck high-dimensions.
this case, approach (C) is no better than approach (B) of Section 3.2. To scale to large and high-dimension datasets, we introduce some approximations. Here, we propose the approximate version of GeoAdEx built upon the relationship between order-1 and order-k neighbors from Theorem 1.

---

Description. To circumvent the expensive (in high dimensions) computation of the order-1 neigh- bors, we approximate approach (C) of Section 3.2. Specifically, instead of operating on the neighbors of the order-1 I cell [. we operate on subset of m points chosen from the entire set of X according to a fast heuristic. In other words, nb(x;;) is (roughly) approximated by a new subset of fixed size m denoted as ndn (zz). For cell Vf ,2, and given generator 24 of this cell, we select from X the m closest points to z; that are not in {zI....,Tx). Mathematically, we define nbm (I;) as:
(x,) = (o, E X d();, S d(z Fa(m)) \ f01,...,22, 353
where [x(m)) is the m-th nearest neighhor of z;. With the above heuristic we guarantee that for each cell, we only have to compute the distance (and test activeness) for at most k²m facets and, thus, sidestep the computation of the first order Voronoi diagram in high dimensions. Each subsequent optimization problem has most kam constraints. Finding m nearest points to a single point x; is a well studied problem and can be approximately solved very fast [Johnson et al., 2017, Aumüller al., 2017, Andoni et al., 2018].
Limitations due to Approximation. Due to the above approximation, it is possible that some of the true order-1 I neighbors not included in U nab.. (z,). Hence, some active facets and cells may be missed completely?. This leads to two limitations. The first limitation is that we can no longer guarantee the optimality of GeoAdEx through Lemmas and 2. In other words, we cannot conclude whether the adversarial distance returned by the approximate version of GeoAdEx is the optimal adversarial distance (or its lower bound).
The second limitation is that the approximation may affect the correctness of the distance computation. Recall that in the exact version of GeoAdEx, we have shown that it possible to replace the bisectors in the constraint of the optimization problem in Eqn. (2) with bisectors between {x1,.... .x) and U nb(x;). But with the approximation, the new feasible set in Eqn. (2) becomes a superset of the one in the exact version. Consequently, the steps in Section 3.3 may falsely label an inactive bisector as active or return smaller distance than the true value.
Addressing Limitations. The first limitation is inherent to the deployment of heuristics to boost performance; similar issue appears in Sitawarin and Wagner [2020] well as the approximate version of Yang et al. [2020] and Wang et al. [2019]. It is difficult to avoid without increasing the runtime significantly. However, the second limitation can be addressed, and we do so by using the full set of bisectors when computing the distance and testing the activeness of adversarial facets like the exact version. This incurs only a small computational cost. We do not need to do the same for non-adversarial cells since their distance and activeness do not affect the correctness of GeoAdEx.
4 Experiments
We compare GeoAdEx to all of the previously proposed attacks on N--N classifiers, namely Sitawarin and Wagner [2020]. Yang et al. [2020], and Wang et al. [2019]. The attacks are evaluated seven datasets most of which were used in the experiments by Yang et al. [2020]. Namely, we evaluate the attacks in that following datasets: Australian, Covtype, Diabetes, Fourelass, and fmnist06 (a two-class subset, 'O' and '6', of MaSSion-MNISTT). Additionally, we also evaluate on Gaussian and Letters datasets which have more classes and data points. More details on the datasets and the computational setup are included in Appendix A.
4.1 Main Findings
Table 1 compares the proposed GeoAdEx attack against the three baselines with respect to the mean perturbation norm. Interestingly, GeoAdEx outperforms the other baselines on all of the seven datasets for I = 5 and on four of them for l: = 7. In the three remaining datasets, Sitawarin and
DDepending on the dataset and ma the chance of this happening may not be high for two reasons: (i) For large A. U rub... (I:)) becomes a large set and is likely to cover most, if not entire, U nb(x;)) (ii) Even if we miss some cells neighbors of particular order-k cell, they may still be picked up by the other cells.
7

---

Table 1: Mean of the adversarial perturbations 100 random points datasets (lower is better). We report the numbers averaged over 10 runs with random training lest splits. error, highlighted gray, is the 95%-confieenc interval. The numbers in parentheses is the ratio of the mean perturbation norm found by GeoAdEx over that of the best baseline. The smallest mean perturbation norm among the attacks for each dataset and each & is bolded.
Attacks
Australian
Covtype
Diabetes
Fourclass
Gaussian
Letters
fimiis066
S&W
.4242
.1931
.1055
.1079
.0422
.1128
.1554
+.020
+.0148
+.0068
+.0039
+.0028
#.0049
+.012
Yang et al.
.4658
.2385
.1922
.1209
.1138
.1370
.1773
1. L.0258
1.0101
1.0077
1.0055
1.0023
1 1.0046
1.0043
3
Wang et al.
.4466
.2134
.1164
.1117
.0825
.1218
.1643
=.0255
+.0170
+.0052
=.0039
=.0030
E.0050
+ +.0047
GeoAdEx
.3646
.1448
.0786
.1073
.0426
.1911
.1509
- +.0250
+.0116
+.0042
+.0045
- +.0015
- F,0066
- 0076
(.8595)
(.7499)
(7450)
(99944)
(.9638)
(9672)
(9911)
S&W
.4488
.2281
.1215
.1877
.0463
.1344
.648
t.0199
H.0121
E.0060
1.0052
1.0030
+ E.0064
+ 0093
Yang et al.
.5524
.3047
.1824
.1309
.1776
.1503
.0877
+.0141
+.0161
t.0068
+.0043
+.0031
+.0048
+.0059
Wang ct al.
..5110
.2613
.1322
.1127
.1195
.1298
.1877
L.0147
1.0110
I. 1.0056
1.0054
1.0047
1. L.0055
1. L.0088
GeoAdEx
.4608
.1866
.0211
.0666
.0401
.1300
1632
1.1155
1.0218
1.0065
1.0048
1.0023
1.0021
1.075
(.9705)
(.817)
(8403)
(.981))
(.8611)
(.9655)
(.9903)
S&W
.5110
.2528
.1259
.1129
.0463
.1277
.1662
#.0145
+.0211
1.0089
+.0043
5.0022
+ 4.0049
00001
Yang et al.
6010
.3335
2005
.4033
.2044
.637
2328
.0140
+.0245
t.0097
+.0053
#.0021
- E.0035
+ t.0057
Wang al.
.5410
.3078
.6611
.182
.1570
.395
.0100
0018
+.0145
+.0083
+.0051
+.0017
+.0034
+.0556
GeoAdEx
.5134
.2153
.1202
.1109
.0425
.1151
.1692
+ 0149
+.0174
+.0049
+.0019
+.0033
+.0065
+ +.055
(1.0047)
(.8517)
(9547)
(99222)
(.9081)
(1.0213)
(1.0181)
Wagner [2020] performs best and narrowly better than GeoAdEx. GeoAdEx performs notably well on datasets Gaussian and Covtype with up to 25% smaller perturbation norm than the second best attack. On average, GeoAdEx reduces the perturbation norm by 11%, 8%. and 4% for k respectively. Since the results of the exact attacks for k = are not the main focus of this work, they appear in Appendix B.
We report that while our attack finds an adversarial distance that is closer to the optimal compared to the baselines, its main limitation is the runtime. In some cases, the runtime of GeoAdEx be order of magnitude larger than the second best attack. This is discussed in more detail in Section 4.3.
It is also important to note that each of the proposed attacks (including GeoAdEx) performs better when the underlying data present certain structural properties. As a result, there no single attack, so far, that performs universally better across all datasets. In Section 4.2, we explore the property of datasets that make our attack superior.
4.2 Advantages of a Geometric Search
Intuitively, GeoAdEx is based on a search that expands outwards from the original test point. As result, performs significantly better than the baselines when there exists an adversarial cell in relatively close proximity to the given test point. In other words, GeoAdEx performs really well on datasets when the class-conditioned distributions are closer or present significant "overlap." In this case, GeoAdEx is less likely to miss small adversarial cells that are close to the test point as confirmed by the main experiment. verify this hypothesis in the following experiment where we control the closeness of classes and study the performance of GdoAdEx compared to the basclines.

---

Ratio of Perturbation Norm
Ratio of Perturhation Norm
2.5
GooAdEs S&W
Yang
2.0
Wang et al.
1.5
1.0
10"
10"
Datetos ELa0
Foundea GLaa)
Bosseds (6-11) Ani de Leters
Class Closeness
Class Closeness
(a) Gaussian (A
5)
(b) Real datasets (k 3)
Figure 2: Mean perturbation norm found by the attacks as function of the class closeness (lower is better).
Australian
Covtype
Diabetes
01.25
0.15
Moun Adverarial Distane
0.49
Meon Advensriial Distmnee
0.26
Meax Advenarial Distange
0.14
0.46
0.24
0.13
0.49
++
0.22
0.12
0.20
0.42
0.18
0.10
0.16
0.34
0.08
10
10
10
10
10"
Total Rumrime (4)
Total Rumime (5)
Total Runtime (6)
(a) Australian
(b) Covtype
(c) Diabetes
Figure 3: Mean adversarial distance vs. total runtime for GeoAdEx and all the baselines with different choices of hyperparameters on (a) Australian, (b) Covtype, and (c) Diahetes. Each point represents single with unique set of hyperparameters. For a given runtime, an attack with lowest mean adversarial distance is best. GeoAdEx utilizes the extra runtime better and outperforms the baselines.
Experiments with Class Closeness. Given a dataset with e class-conditioned data distributions Dı,..., De, we can compute the minimum KL-divergence between a pair of distributions D, and D, () Now we define as class closeness of given data distribution as the average of the above set minima, i.c., 1 Σ min, (,y)):))))). The smaller the class closeness, the closer their distributions are and, consequently the larger the degree of "mixing" between Voronoi cells of different classes. For each dataset, we record the associated class closeness and the ratio of the mean perturbation norm of each baseline over that of GeoAdEx.
First, confirm this hypothesis on synthetic datasets where each of the two classes is generated by Gaussian distributions, i.e., D1, D2, in R220 Note that for Gaussian, KL-divergence can be analytically computed the closed form exists. In this case, Figure 2a shows that GeoAdEx significantly outperforms all the baselines by a larger margin when the class closeness is small, That is, for datasets that challenging classify, GeoAdEx outperforms the competition.
Furthermore, we revisit the real datasets from Table and re-interpret the results under the lens of their class closeness. Since the true data distributions of these datasets are unknown, we approximate the KL-divergence via data samples using the estimator in Equation (5) from Wang et al. [2009]. Indeed, Figure 2b shows that the datasets which GeoAdEx clearly outperforms Yang et al. [2020] and Wang et al. [2019], are the ones with small class closeness (e.g., Diabetes, Gaussian).
4.3 Runtime Comparisons
Runtimes of the experiments in Table are reported in Table 4. Through the choice of hyperparam- eters, we attempt to control the runtime of each algorithm to roughly be within the same order of magnitude, but this has proven difficult given that we do not wish fine-tune the hyperparameters specifically per dataset. To better compare the algorithms under a similar set of runtimes, we repeat the experiments with different sets of hyperparameters chosen at certain intervals and plot the mean adversarial distance the total runtime for each experiment in Figure 3.

---

For each algorithm, we started with its default hyperparameters and adjusted them (either linearly or exponentially) in the direction that should find smaller adversarial perturbations with longer runtime. Each point on the curves represents an experiment with one set of hyperparameters. One way to read the plot is to fix a partieular runtime and compare the mean adversarial distance from each line. This experiment is expensive so we only run it for the first three datasets from Table 1.
For Australian and Diabetes, in a regime with very short runtime (~~10ss total or 1s per sample), there is at least one baseline that is both faster and finds smaller adversarial perturbation than GeoAdEx. However, with longer runtimes, our GeoAdEx outperforms all the baselines by a large margin (10%. 15% and 20% improvement over the second best for Australian, Covtype, and Diabetes, respectively). In most settings, the baselines do not benefit much, if all, from the increased runtime. Conversely, GeoAdEx always finds smaller adversarial distances given longer time limit. More details and discussions of this experiment are in Appendix B.2.
Effect of the initialization attack. The initialization of e with Sitawarin and Wagner [2020] attack, as described in the performance optimization (II), also improves the total runtime of GeoAdEx. Depending on the dataset, the runtime reduction range from 2% to 75%. In the interest of space, ablation study and analysis of the initialization attack is included in Appendix B.3.
5 Discussion & Open Problems
GeoAdEx has been shown to be successful in discovering adversarial examples for k-NN classifiers with k 2 1. Compared to the baselines, it finds adversarial examples with considerably smaller perturbation norm on most of the commonly tested datasets.
The main limitation of GeoAdEx is its runtime, particularly in the short-runtime regime. Sitawarin and Wagner [2020] is always the fastest, generally followed by Wang et al. [2019]. Yang et al. [2020], and then GeoAdEx. However, in the long-runtime regime, our GeoAdEx outperforms the baselines by large margin given the same runtime. GeoAdEx utilizes a longer runtime by expanding the search radius while the baselines search more cells without a particular order or prioritization. As result, the adversarial distance found by Sitawarin and Wagner [2020], Yang et al. [2020], and Wang et al. [2019] typically does not improve much further with more computation.
We note that compared to the geometric approach by Jordan et al. [2019], our experiments were run on significantly larger scale. Specifically, Jordan et al. [2019] was tested on neural networks with only up to 70 ReLUs, which are much smaller than typical networks used in practice. This is equivalent to Voronoi cells with only 70 neighbors/facets in our setting. GeoAdEx was tested on datasets with over ten thousand generator points and & up to 7, which results in a substantially larger number of polytopes to search through.
GeoAdEx has shown convincing results with our new geometric take on the problem, but there is room for improvement in terms of efficiency. Additional speedups can be introduced via parallclization, GPU utilization, and faster optimization technique. A more sophisticated heuristic for determining the order-1 I neighbors can also be used. Furthermore, geometric properties of a high-order Voronoi diagram may better exploited to save unnecessary computation on aov-asversa cells. For instance, multiple neighboring non-adversarial cells may be combined and approximated as single large cell we can guarantee that there is no adversarial cell inside this new polytope. This would remove large number of distance computations surrounding the given test point, which is the main bottleneck of GeoAdEx, Additionally, GeoAdEx can also be extended to other space-partitioning classifiers such as decision trees and random forests.
6 Conclusion
We propose GeoAdEx, an algorithm based on geometric insights for finding adversarial examples on k-NN classifiers. We leverage the structural properties of higher-order Voronoi diagrams to propose efficient approximations and speedup the final algorithm. While GeoAdEx typically requires a higher computational cost, it significantly outperforms the baselines in most of the datasets. Finally, for the case where there is no clear separation between the classes (a typical characteristic of real data) GeoAdEx significantly outperforms the competition.
10

---

Acknowledgement
The first author of this paper was supported by the Hewlett Foundation through the Center for Long-Term Cybersecurity (CLTC) and by generous gifts from Open Philanthropy and Google Cloud Research Credits program with the award GCP19980904.
The second and third authors were supported by the Center for Long- Long-Term Cybersecurity (CLTC), the Berkeley Deep Drive project, NSF grant
and Open Philanthropy.
References
A. Andoni, P. Indyk, and I. Razenshteyn. Approximate nearest neighhor search in high dimensions. arXiv preprint arXiv: (00.. 09823, 7, 2018.
M. Aumüller, E. Bernhardsson, and A. Faithfull. Ann- nan-benchmarrk: A benchmarking tool for approximate nearest neighbor algorithms. In International Conference on Similarity Search and Applications, pages 34 44, Springer, 2017.
B. Biggio, I. Corona, D. Maiorca, B. Nelson, N. Šmdić, P. Laskov, G. Giacinto, and F. Roli. Evasion attacks against machine learning at test time, H. Blockeel, K. Kersting, S. Nijssen, and F. Zelezný, editors, Machine Learning and Knowledge Discovery in Databases, pages 387-402, Berlin, Heidelherg, 2013. Springer Berlin Heidelberg. ISBN 978-3-644-44099--.
Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, USA, 2004. ISBN 0521833787.
C.-C. Chang and C.-. Lin. LIBSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2:27:1-27:27, 2011. Software available at http://wwr caie. ntu .tt.unuuuuuuuuuue.uuu tw/ "cjlin/iibsvm.
J. M. Cohen, E. Rosenfeld, and J. Z. Kolter. Certified adversarial robustness via randomized smoothing. arXiv preprint arXiv:1902.0000 18, 2019.
Dubey, L. van der Maaten, Z. Yalniz, Li, and D. Mahajan. Defense against adversarial images using web-scale nearest-neighhor search. CORR, abs/1 100.01112, 2019.
I. Goodfellow, Shlens, and Szegedy. Explaining and harnessing adversarial examples. In International Conference on Learning Representations, 2015.
R. Guo, P. Sun, E. Lindgren, Q Geng, D. Simeha, F. Chern, and S. Kumar. Accelerating large-scale inference with anisotropic vector quantization. In International Conference Machine Learning. 2020.
X. Huang, M. Kwiatkowska, S. Wang, and M. Wu. Safety verification of deep neural networks. In R. Majumdar and V. Kunčak, editors, Computer Aided Verification, pages 3-29, Cham, 2017. Springer International Publishing.
J. Johnson, M. Douze, and H. Jégou. Billion-scale similarity search with gpus. arXiv preprint 1702.00777 2017.
M. Jordan, J. Lewis, and A. G. Dimakis. Provable certificates for adversarial examples: Fitting a ball in the union of polytopes. In Advances in Neural Information Processing Systems, pages 14082-14092, 2019.
G. Katz, C. W. Barrett, D. L. Dill, K. Julian, and M. J. Kochenderfer. Reluplex: An efficient SMT solver for verifying deep neural networks. CoRR, 7bs/0102.01135, 2017. URL htthttt::/arxxivvoor wttp://www.rraaa///////aaa////// 001111111...11..5..111111
A. Okabe, B. Boots, and K. Sugihara. Spatial Tessellation:: Concepts and Applications of Voronoi Diagrams. John Wiley & Sons, Inc., USA, 1992. ISBN 0471934305.
Papernot and P. D. McDaniel. Deep k- nearest neighbors: Towards confident, interpretable and robust deep httg/bbb/1803 04765.
learning. CoRR, abs/1 803.04765, 2018. URL http: /ttp::/aaee
C. Sitawarin and D. Wagner. On the robustness of deep k-nearest neighbors. volume abs/ htts/1903.08333. 2019a. URL http: //axiiv.///////////////// www.vvooorrgaaaeeoo werg/abs/1900 08333.
C. Sitawarin and D. Wagner. Defending against adversarial examples with k-nearest neighbor. arXiv preprint 100.05990 2019b.
C. Sitawarin and D. Wagner. Minimum norm adversarial examples on knn and knn-based models. ArXiv. abs/2003.06559, 2020.

---

C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, J. Goodfellow, and R. Fergus. Intriguing properties of neural networks. CoRR, abs/133...199, 2013. URL http::/aazaiii. http:/..gga/////// abs/1312.....///.../.mmaaaama1ta 6199.
V. Tjeng, K. Xiao, and R. Tedrake. Evaluating robustness of neural networks with mixed integer programming. arXiv preprint arXiv:1711.0735, 2017.
L. Wang, X. Liu, J. Yi, Z.-H. Zhou, and C.-J. Hsieh. Evaluating the robustness of nearest neighbor classifier; A primal-dual perspective. arXiv preprini arXiv:1906.03972, 2019.
Q. Wang, S. R. Kulkarni, and S. Verdu. Divergence estimation for multidimensional densities via k-nearest- neighbor distances. IEEE Transactions on Information Theory, 55(5):2392-2405, 2009.
Y. Wang, S. Jha, and K. Chaudhuri. Analyzing the robustness of nearest neighbors to adversarial examples. In J. Dy and A. Krause, editors, Proceedings of the 35th International Conference Machine Learning. volume 80 Proceedings Machine Learning Research, pages 5133 5142, Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018. PMLR. URL http:/ http::tttppo/eeee http:///roceeeenss.e/ee mlr press/ pwwss/v0///s//eeeepee
v80/ wates///00wwaag188 wang18c. html.
T.-W. Weng, Zhang, H. Chen, Z. Song, C.-J. Hsieh, D. Boning, I. S. Dhillon, computation of certified robustness for relu networks. arXiv preprint wrXiv::804.09666 2018.
Daniel. Towards fast
convex outer adversarial polytope. volume 80 of Proceedings of Machine Learning Research, pages 5286-5295, Stockholmsmässan Stockholm Sweden, 10-15 Jul 2018. PMLR. URL http:/ / pwwppeedeoenns..eeeee mlr hatpas/////////og///// html.
Wong and Kolter. Provable defenses against adversarial examples
htmml.
X. Wu, V. Kumar, J. Ross Quinlan, J. Ghosh, Q. Yang, H. Motoda, G. J. McLachlan, A. Ng. B. Liu, S. Yu, Z. Zhou, M. Steinbach, D. J. Hand, and D. Steinberg. Top 10 algorithms in data mining. Knowledge and Information Systems, 14(1):1-37, Jan. 2008. ISSN 0219-3116. doi: 10.1007/ 101111001110000000 15-007-0114-2.
Y-Y. Yang, C. Rashtchian, Y. Wang, and K. Chaudhuri. Robustness for non- parametric classification: A generic attack and defense. In International Conference on Artificial Intelligence and Statistics, pages 941-951 PMLR, 2020.
12


Reviews:
[{"review_id": "pSy4r93auY", "reviewer": "Reviewer_hZxG", "summary": "Prior adversarial attacks on k-nearest neighbor (k-NN) do not scale well with the increase of k and the number of data. This paper proposed a set of better heuristics towards speeding up this problem. Theoretically, they show that their method still finds the optimal solution if no time limit. Empirically, they show that their methods can provide stronger attacks than prior works. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n- Written clearly.\n- Code is provided in the supplementary.\n- The proposed method seems to be a nice improvement over the prior work in terms of speed.\n\nCons:\n- In one of your cited papers (Yang et al., [2020]), they also proposed a defense algorithm proposed for $k$-NN, how does your algorithm work on $k$-NN with the defense applied?\n\nminor:\n- It is a bit confusing for Table 4 in the supplementary material and the text around it. It appears that Yang et al. is faster in many of the datasets (Australian, Covtype, Diabetes, and Fourclasses) than GeoAdEx. But the description says generally GeoAdEx is faster. If I am reading it correctly, the authors should mean that GeoAdEx is faster when the dataset and k are larger (instead of ``in general'').\n- Can the method proposed in this work be applied to the certification of relu networks (the setting in Jordan et al. [2019] cited in the paper)? Can it perform well there?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations are described clearly on page 7, and I am not aware of any potential negative social impact of this paper.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "nTKWNQywImV", "reviewer": "Reviewer_FLts", "summary": "This paper proposed a method to run adversarial attacks on a k-NN classifier based on a breadth-first search. The proposed algorithm gradually expands the radius of searching until an adversarial example is found. The authors theoretically studied the optimality of the proposed method and proposed necessary approximations. The limitation and advantages of this method are also addressed. Finally, the experimental results show the effectiveness of this method.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In general, I think this paper is well-written and intuitive. The theoretical studies are rigorous. I briefly checked the proof and they seem to be correct to me. Though the running time still poses the biggest disadvantage of this method, the experimental results show clear improvement to the existing method in terms of the mean norm. So I am recommending an accept. My detailed comments are as follows.\n\n> I think more explanation is needed for the approximation proposed in 3.5.2, especially how fast would this approximation converge to the original problem. As mentioned in line 244, this has a domino effect on the result of the adversarial distance, I think it would be great if the authors can provide a more detailed analysis of this approximation.\n\n> Given the dramatic increase in running time in Table 4, I think it may be necessary to also have a figure showing the proposed method's performance vs. running time by terminating it at different times.\n\n> Minor: please refrain from only using color to distinguish curves as in Figure 3 as it is not friendly to readers with color-blindness.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitations and potential negative societal impact of their work", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "KZouAlleyZf", "reviewer": "Reviewer_jVor", "summary": "The paper describes a \"white box\" adversarial attack on k-NN classifiers that is based on the geometry of the Voronoi diagram. The paper first defines the relevant geometric elements - Voronoi cells and their facets (which reside on bisectors - hyperplanes that are equidistant to two data points) and when they are considered *adversarial*. The paper then proposes an algorithm (GeoAdEx) for searching for the nearest adversarial facet for a given test point, using a priority queue in a BFS manner. GeoAdEx is shown to provide an optimal (min L2) attack. To allow scaling GeoAdEx to k>1 and large data, several approximations are suggested (which may result in a suboptimal attack). The experimental section compares the mean attack size for seven datasets against three other kNN attacks (for k=3, 5, 7) and shows that GeoAdEx results in a smaller-norm attack.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: The very active research area of *adversarial examples* seems to focus on deep neural networks and there are only few works discussing adversarial examples for k-NN classifiers. The current work handles this case and improves upon an earlier work, which is more heuristics-based. The presented geometric algorithm seems to be novel.\n\nClarity and quality: The paper is clearly written and describes the geometric setting in an accurate and easy to follow manner. In addition, the analysis of the proposed algorithm seems sound. The experimental section seems to support the claim that GeoAdEx results in smaller perturbations than earlier methods (20%-30% reduction in L2 norm). The run-time of the different attacks is not provided, but is later discussed in section 5 (being up to two orders of magnitude slower).\n\nI am less confident about the significance of the presented work, due to several reasons:\n- The basic GeoAdEx algorithm is elegant and well-justified, but in order to scale it to typical use cases, several heuristics and approximations are added. In the end, it results in a slightly better attack but at the expense of much larger runtime.\n- Considering the contribution of current work to *adversarial examples* research in general (which aims at understanding why adversarial examples exist, what kind of models are vulnerable to such examples and how to make the models more robust), I'm not sure that a reduced-norm attack on a kNN classifier is a significant contribution.\n- Related to the above point, the authors cite Wang et al showing that \"a k-NN classifier can be as robust as the optimal Bayes classifier\". It is not clear if the attack L2 values reported in Table 1 are \"insignificant perturbations\", similar to adversarial attacks on CNNs (indicating that kNN is not robust), or large perturbations that are required to fool a robust model. If the latter is true, the setting, in my opinion, is less interesting. It is also not clear if in some settings, a kNN classifier would be robust against earlier attacks, but vulnerable to GeoAdEx. (This is perhaps discussed in the class closeness case).\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discuss limitations of the proposed method. There is no negative social impact I am aware of.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "3OrR185-Mz", "reviewer": "Reviewer_dxry", "summary": "This paper focuses on the problem of generating adversarial perturbations for $k$-nearest-neighbor classifiers. Focusing on the geometric nature of $k$-nearest-neighbor classification, the proposed scheme GeoAdEx works with order-$k$ Voronoi cells and facets to search around the test point being attacked by gradually increasing the search radius around it and updating the upper and lower bounds to the optimal adversarial perturbation norm. Beyond this novel algorithm to generate the optimal perturbation, the paper focuses on making this algorithm meaningfully scalable in high dimensional data with $k>1$ nearest-neighbors. The first optimization is the observation that the task of finding the neighboring order-$k$ Voronoi cells to the current cell in question can be solved by finding the neighboring order-$1$ Voronoi cells -- this is an improvement though finding order-$1$ Voronoi cells in high dimensions is still a very significant bottleneck, and hence needs to be approximated by just using the $m$ nearest neighbors of all the $k$ points in the current cell. This introduces a significant approximation that appears to be necessary to make the proposed algorithm tractable. Without this approximation, the proposed algorithm is guaranteed to find optimal perturbation; the above approximation does not have any such property. Empirically, the proposed algorithm is evaluated against existing baselines, with significant improvement, however, with an order of magnitude more computational cost. The empirical evaluation also study the effect of the class separation on the relative performance of the proposed GeoAdEx against baselines, demonstrating the intuitive result that GeoAdEx performs better with small class separations since the baselines tend to miss the closeby small order-$k$ Voronoi cells which GeoAdEx almost exhaustively searches over.\n", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Positives\n\n- This paper focuses on a very interesting problem on generating adversarial perturbations for $k$-nearest-neighbor classifiers and differs from recent existing literature in that the existing literature leverages optimization based approaches combined with heuristics to handle $k > 1$ while the proposed GeoAdEx leverages a geometric breadth-first search over all order-$k$ Voronoi cells to find the optimal adversarial perturbations.\n- The paper is very well-written and easy to follow, explaining most parts explicitly. The paper also provides good discussions of\n  - the different aspects of the GeoAdEx algorithm,\n  - the various design choices while clearly contrasting against existing work,\n  - the optimizations and approximations made to make the proposed GeoAdEx computationally tractable, and\n  - the results of the empirical evaluation, explicitly highlighting a possible reason behind the improved performance of GeoAdEx\n- The authors connect to many really recent papers, positioning the proposed scheme well.\n\n\n## Questions/concerns\n\nMy main concern is the computational cost of this method, and the lack of some form of parity between the baselines and GeoAdEx. The original GeoAdEx is essentially performing a breadth-first exhaustive search over the set of order-$k$ Voronoi cells. This makes the computational time fairly intractable. However, when comparing to baselines, it is not clear how the performance would compare when all schemes use approximately the same amount of time. The authors claim that some of the baselines cannot really perform better even if they are given more amount of time. In such cases, it would be good to understand what level of performance GeoAdEx is able to obtain within the time used by the baselines (potentially by leveraging early-stopping).\n\nMoreover, it is not clear how robust the proposed scheme is in terms of its empirical performance:\n- It is not clear how sensitive GeoAdEx is to the choice of $m$ in the approximate version and other hyperparameters.\n- It would be good to understand the \"convergence\" of GeoAdEx in terms of the \"runtime/iterations vs perturbation norm\" tradeoff.\n- It is not clear how the hyperparameters of the proposed scheme and the baselines were tuned.\n- How critical the proposed scheme is to the Sitawarin & Wagner (2020) initialization of $\\epsilon$ in terms of computational time vs. perturbation norm tradeoffs.\n- The results presented in the main paper do not have any error bars or significance tests so it is not clear how significant these gains for GeoAdEx are over the baselines.\n\n\n### Specific Questions:\n\nBeyond the above concerns, there are some specific critical parts of the paper that are not clear to me. Most of these following questions pertain to me trying to understand how we can perform some of the mentioned operations in the proposed algorithm in a non-exhaustive manner:\n\n- How is the \"visited\" order-$k$ Voronoi cell tracked? Do we ever need to explicitly write out all the $n\\choose{k}$ order-$k$ Voronoi cells? How is a particular facet connected to a cell?\n- L128-129 \"GeoAdEx needs to ... with cell $\\Psi$\": How easy is it to enumerate the facets than comprise a cell $\\Psi$? How is it done efficiently?\n- L207-208 \".. we can safely filter out these facets ...\": How do we do the filtering without computing distance to facet?\n- L230-232: $x_{\\pi(m)}$ should not be the $m$-th nearest-neighbor of $x_i$ but the $m$-th nearest-neighbor not in $\\{x_1, \\ldots, x_k\\}$. Also, as per the definition, $\\widetilde{nb}_m(x_i)$ will change for any given $x_i$ as the algorithm progresses so these $m$-neighbors have to found for each cell. Is that right? This makes the computation cost still fairly high -- how is this handled?\n- L253-256: \"However, the second limitation can be addressed ....\": It is not clear how the second limitation can be addressed without having the exact $\\cup_{i=1}^k nb(x_i)$. This needs to be clarified.\n- Lemma 2 follow from Lemma 1 and then structure of the algorithm. What is the main novelty/technical difficulty here?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have discussed limitations which is mainly the computational complexity of this proposed scheme. The authors have not discussed any potential negative societal impact. \n", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies algorithms to find adversarial examples for k-NN classifiers in a white box fashion. The reviewers have generally agreed that the work is novel, and that the experiments demonstrate an improvement over prior work. However, some comments have not been addressed in the paper, and there are many parts of the discussion that should inform improvements to the next version of the paper. For example, when designing new attack algorithms, it is important to be evaluating against good defense algorithms, such as the one from Yang et al., which appears to be missing. Similarly, it is important to provide reproducible results and error bars, especially when the improvement over existing work is small. Overall, I believe the merits outweighs the shortcoming, and that this paper provides a number of contributions to the literature around k-NN adversarial examples. I weakly recommend acceptance of this paper.
Decision: Accept (Poster)