Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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.

Clarity 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).

I am less confident about the significance of the presented work, due to several reasons:
- 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.
- 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.
- 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).

limitations_and_societal_impact: The authors discuss limitations of the proposed method. There is no negative social impact I am aware of.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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. 
main_review: Pros:
- Written clearly.
- Code is provided in the supplementary.
- The proposed method seems to be a nice improvement over the prior work in terms of speed.

Cons:
- 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?

minor:
- 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'').
- 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?
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.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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.

> 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.

> 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.

> Minor: please refrain from only using color to distinguish curves as in Figure 3 as it is not friendly to readers with color-blindness.
limitations_and_societal_impact: The authors adequately addressed the limitations and potential negative societal impact of their work
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.

main_review: ## Positives

- 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.
- The paper is very well-written and easy to follow, explaining most parts explicitly. The paper also provides good discussions of
  - the different aspects of the GeoAdEx algorithm,
  - the various design choices while clearly contrasting against existing work,
  - the optimizations and approximations made to make the proposed GeoAdEx computationally tractable, and
  - the results of the empirical evaluation, explicitly highlighting a possible reason behind the improved performance of GeoAdEx
- The authors connect to many really recent papers, positioning the proposed scheme well.


## Questions/concerns

My 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).

Moreover, it is not clear how robust the proposed scheme is in terms of its empirical performance:
- It is not clear how sensitive GeoAdEx is to the choice of $m$ in the approximate version and other hyperparameters.
- It would be good to understand the "convergence" of GeoAdEx in terms of the "runtime/iterations vs perturbation norm" tradeoff.
- It is not clear how the hyperparameters of the proposed scheme and the baselines were tuned.
- How critical the proposed scheme is to the Sitawarin & Wagner (2020) initialization of $\epsilon$ in terms of computational time vs. perturbation norm tradeoffs.
- 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.


### Specific Questions:

Beyond 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:

- 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?
- 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?
- L207-208 ".. we can safely filter out these facets ...": How do we do the filtering without computing distance to facet?
- 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?
- 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.
- Lemma 2 follow from Lemma 1 and then structure of the algorithm. What is the main novelty/technical difficulty here?

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.
review_title: null

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)