A Theory-Based Evaluation of Nearest Neighbor Models Put Into Practice

In the $k$-nearest neighborhood model ($k$-NN), we are given a set of points $P$, and we shall answer queries $q$ by returning the $k$ nearest neighbors of $q$ in $P$ according to some metric. This concept is crucial in many areas of data analysis and data processing, e.g., computer vision, document retrieval and machine learning. Many $k$-NN algorithms have been published and implemented, but often the relation between parameters and accuracy of the computed $k$-NN is not explicit. We study property testing of $k$-NN graphs in theory and evaluate it empirically: given a point set $P \subset \mathbb{R}^\delta$ and a directed graph $G=(P,E)$, is $G$ a $k$-NN graph, i.e., every point $p \in P$ has outgoing edges to its $k$ nearest neighbors, or is it $\epsilon$-far from being a $k$-NN graph? Here, $\epsilon$-far means that one has to change more than an $\epsilon$-fraction of the edges in order to make $G$ a $k$-NN graph. We develop a randomized algorithm with one-sided error that decides this question, i.e., a property tester for the $k$-NN property, with complexity $O(\sqrt{n} k^2 / \epsilon^2)$ measured in terms of the number of vertices and edges it inspects, and we prove a lower bound of $\Omega(\sqrt{n / \epsilon k})$. We evaluate our tester empirically on the $k$-NN models computed by various algorithms and show that it can be used to detect $k$-NN models with bad accuracy in significantly less time than the building time of the $k$-NN model.


Introduction
The k-nearest neighborhood (k-NN) of a point q with respect to some set of points P is one of the most fundamental concepts used in data analysis tasks such as classification, regression and machine learning. In the past decades, many algorithms have been proposed in theory as well as in practice to efficiently answer k-NN queries [e.g., 1, 7-10, 17, 19, 22, 25, 26, 29, 35]. For example, one can construct a k-NN graph of a point set P , i.e., a directed graph G = (P, E) of size n = |P | such that E contains an edge (p, q) for every k-nearest neighbor q of p for every p ∈ P , in time O(n log n + kn) for constant dimension δ [8]. Due to restrictions on computational resources, approximations and heuristics are often used instead (see, e.g., [9,10] and the discussion therein for details). Given the output graph G of such a randomized approximation algorithm or heuristic, one might want to check whether G resembles a k-NN graph before using it, e.g., in a data processing pipeline. However, the time required for exact verification might cancel out the advantages gained by using an approximation algorithm or a heuristic. On the other hand, testing whether G is at least close to a k-NN graph will suffice for many purposes. Property testing is a framework for the theoretical analysis of decision and verification problems that are relaxed in favor of sublinear complexity. One motivation of property testing is to fathom the theoretical foundations of efficiently assessing approximation and heuristic algorithms' outputs.
Property testing [31], and in particular property testing of graphs [20], has been studied quite extensively since its founding. A one-sided error -tester for a property P of graphs with average degree bounded by d has to accept every graph G ∈ P and it has to reject every graph H that is -far from P with probability at least 2/3 (i.e., if graphs that are -far are relevant, it has precision 1 and recall 2/3). A graph H of size n is -far from some property P if more than dn edges have to be added or removed to transform it into a graph that is in P. A two-sided error -tester may also err with probability less than 1/3 if the graph has the property. The computational complexity of a property tester is the number of adjacency list entries it reads, denoted its queries. Many works in graph property testing focus on testing plain graphs that contain only the pure combinatorial information. However, most graphs that model real data contain some additional information that may, for example, indicate the type of an atom, the bandwidth of a data link or spatial information of an object that is represented by a vertex or an edge, respectively. In this work, we consider geometric graphs with bounded average degree. In particular, the graphs are embedded into R δ , i.e., every vertex has a coordinate x ∈ R δ . The coordinate of a vertex may be obtained by a query.

Main Results
Our first result is a property tester with one-sided error for the property that a given geometric graph G with bounded average degree is a k-nearest neighborhood graph of its underlying point set (i.e., it has precision 1 and recall 2/3 when taking -far graphs as relevant). Theorem 1. Given an input graph G = (V, E) of size n = |V | with bounded average degree d, there exists a one-sided error -tester that tests whether G is a k-nearest neighbourhood graph. It has query complexity c · √ n k 2 ψ δ / 2 , where ψ δ is the δ-dimensional kissing number and c > 0 is a universal constant.
We emphasize that it is not necessary to compute the ground truth (i.e., the k-NN of P ) in order to run the property tester. Furthermore, the tester can be easily adapted for graphs G = (P ∪ Q, E) such that P ∩ Q = ∅ and we only require that for every q ∈ Q, E contains an edge (q, p) for every k-nearest neighbor p of q in P . This is more natural when we think of P as a training set and Q as a test set or query domain. To complement this result, we prove a lower bound that holds even for two-sided error testers. Theorem 2. Testing whether a given input graph G = (V, E) of size n = |V | is a k-nearest neighbourhood graph with one-sided or two-sided error requires max( n/(8 k), kψ δ /6) queries.
Finally, we provide an experimental evaluation of our property tester on approximate nearest neighbor (ANN) indices computed by various ANN algorithms. Our results indicate that the tester requires significantly less time than the ANN algorithm to build the ANN index, most times just a 1 /10-fraction. Therefore, it can often detect badly chosen parameters of the ANN algorithm at almost no additional cost and before the ANN index is fed into the remaining data processing pipeline.

Related Work
We give an overview of sublinear algorithms for geometric graphs, which is the topic of research that is most relevant to our work. As mentioned above, the research on k-NN algorithms is very broad and diverse. See, e.g., [15,32] for surveys. Testing whether a geometric graph that is embedded into the plane is a Euclidean minimum spanning tree has been studied by Ben-Zwi et al. [3] and Czumaj and Sohler [11]. In [3], the authors show that any non-adaptive tester has to make Ω( √ n) queries, and that any adaptive tester has query complexity Ω(n 1/3 ). In [11], a one-sided eror tester with query complexityÕ( n/ ) is given. In a fashion similar to property testing, Czumaj et al. [14] estimate the weight of Euclidean Minimum Spanning Trees inÕ( √ n · poly( )) time, and Czumaj and Sohler [12] approximate the weight of Metric Minimum Spanning Trees inÕ(n · poly( )) time for constant dimension, respectively. Hellweg et al. [21] develop a tester for Euclidean (1 + δ)-spanners. Property testers for many other geometric problems can, for example, be found in [13,28].

Preliminaries
Let d, δ, , k ≥ 0, d ≥ k be fixed parameters. In this paper, we consider property testing on directed geometric graphs with bounded average degree d.
Definition 1 (geometric graph). A graph G = (V, E) with an associated function coord : V → R d is a geometric graph, where each vertex v is assigned a coordinate coord(v). Given v ∈ V , we denote its degree by d(v) and the set of adjacent vertices N(v) := {u | (v, u) ∈ E}.
The Euclidean distance between two points x, y is denoted by dist(x, y). For the sake of simplicity, we write dist(u, v) := dist(coord(u), coord(v)) for two vertices u, v ∈ V . When there is no ambiguity, we also refer to coord(v) by simply writing v. We denote the size of the graph G = (V, E) at hand by n = |V |.
Definition 2 (k-nearest neighborhood graph). A geometric graph G = (V, E) is a k-nearest neighbourhood (k-NN) graph if for every v ∈ V , the k points u 1 , . . . , u k ∈ V that lie nearest to v according to dist(·, ·) are neighbors of v in G, i.e., (v, u i ) ∈ E for all i ∈ [k] (breaking ties arbitrarily).
Let G = (V, E) be a geometric graph. We say that a graph G is -far from a geometric graph property P if at least dn edges of G have to be modified in order to convert it into a graph that satisfies the property P. We assume that the graph G is represented by a function , a degree function d G : V → N that outputs the degree of a vertex and a coordinate function coord G : V → R δ that outputs the coordinates of a vertex.
Definition 3 ( -tester). A one-sided (error) -tester for a property P with query complexity q is a randomized algorithm that makes q queries to f G , d G and coord G for a graph G. The algorithm accepts if G has the property P. If G is -far from P, then it rejects with probability at least 2/3. The motivation to consider query complexity is that the cost of accessing the graph, e.g., through an ANN index, is costly but cannot be influenced. Therefore, one should minimize access to the graph.
} define the subset of knn(v) that is not adjacent to v. If wit(v) = ∅ or d(v) < k, we call v incomplete, and we call elements of wit(v) the witnesses of v.
If G is -far from being a k-nearest neighborhood graph, an -fraction of its vertices are incomplete.
Lemma 5. If G is -far from being a k-nearest neighborhood graph, at least dn/(2k) vertices are incomplete.
Proof. Assume the contrary. For every incomplete vertex v, delete k edges such that the distance to the property does not increase and insert the missing edges from v to its k nearest neighbors. By the assumption, the total number of inserted or deleted edges is less than dn/(2k) · 2k. Therefore, G is -close to being a k-nearest neighborhood graph.
The main challenge for the property tester will be to find matching witnesses for a fixed set of incomplete vertices. The following result from coding theory for Euclidean codes bounds the maximum number of points q i that can have the same fixed point p as nearest neighbor.

Upper Bound
The idea of the tester is as follows (see Algorithm 1). Two samples are drawn uniformly at random: S , which shall contain many incomplete vertices if G is -far from being a k-nearest neighborhood graph and T , which shall contain at least one witness of an incomplete vertex in S . For every v ∈ S , the algorithm should query its degree, its coordinate as well as every adjacent vertex and their coordinates and calculate the distance to them. If d(k) < k or if one of the vertices in T is a witness of v, the algorithm found an incomplete vertex, and hence rejects. Otherwise, it accepts.
However, we have to deal with the case that some vertices in S have non-constant degree, say, Ω(1/ ), such that querying all their adjacent vertices would require too many queries. To this end, we prove that one can prune these vertices to obtain a subset S ⊆ S of low degree vertices that still contains many incomplete vertices with sufficient probability. T ← sample ln(10) · k · ψ δ · √ n vertices from V u.a.r. with replacement; Proof of Theorem 1 We prove that Algorithm 1 is an -tester as claimed by Theorem 1. Since Algorithm 1 does never reject a k-nearest neighbourhood graph, assume without loss of generality that G = (V, E) is -far from being a k-nearest neighborhood graph. Algorithm 1 only queries the neighbors of S, and therefore its query complexity is at most |S| · 100k/ = O( √ nk 2 / 2 ). It remains to prove the correctness.
In the following, let L := {v ∈ V | d(v) ≤ 100k/ } denote the set of all vertices in G that have low degree, let I denote the set of incomplete vertices in L, and let I S ⊆ S denote the set of incomplete vertices in S. By an averaging argument, |V \L| ≤ dn/(100k). It follows from Lemma 5 that L contains at least dn/(4k) incomplete vertices, and therefore we focus on finding incomplete vertices that have low degree. The following random variable identifies witnesses of vertices incomplete vertices in S ⊂ L.
Definition 7. Given u ∈ T , let W S (u) be a random variable that is 1 if u is a witness of an incomplete vertex v ∈ I S and 0 otherwise.
The proof of Theorem 1 follows from the following three claims. First, note that S is a uniform sample without replacement from L whose size |S| is random. However, |S| is sufficiently large with constant probability.
Proof. The expected cardinality of S \S is d √ n. Therefore, the probability that |S| is less than 20 √ n/ is at most 1/10 by Markov's inequality.
In the subsequent sections, we prove the following two claims. Given that S is sufficiently large, it will contain at least √ n incomplete vertices with constant probability.
Finally, we show that if S contains at least √ n incomplete vertices, then T will contain at least one witness of such an incomplete vertex with constant probability.
The correctness follows by a union bound over these three bad events.
Analysis of the Sample S: Proof of Claim 9 We bound the cardinality of S such that S contains at least √ n incomplete vertices.
Proof. Since S was sampled without replacement, the random variable |I S | follows the hypergeometric distribution. Let X be a random variable that denotes the number of draws that are needed to obtain √ n incomplete vertices in S, which therefore follows the negative hypergeometric distribution. By Lemma We apply Markov's inequality to obtain Analysis of the Sample T: Proof of Claim 10 We prove the following lower bound on the number of witnesses in G, which will imply a bound on |T | by k-reducing it to the case k = 1.
Proposition 12. Given a point set P ⊂ R δ , p ∈ P and k ∈ N, the maximum number of points q i ∈ P that can have p as k-nearest neighbor is bounded by k · ψ δ .
We note that this bound is tight, as shown in Lemma 15.
( * ) Pick a point q ∈ Q that lies furthest from w and let Proof of Proposition 12. We apply Definition 13 to p and prove that the size of Q at the beginning of the process is at most k · ψ δ , which proves the claim. At first we show that every vertex that is picked by ( * ) stays in Q: Let q 1 , q 2 be arbitrary points that are picked by ( * ) in the process of k-reducing, with q 1 being picked in an earlier iteration than q 2 . The latter implies dist(q 2 , p) < dist(q 1 , p). Assume that q 1 ∈ Q q 2 at the time q 2 is selected, and therefore q 1 is removed from Q. Since q 1 is deleted by (#), it holds that dist(q 1 , p) < dist(q 2 , p), which is a contradiction as q 1 has been selected before q 2 .
We continue to bound the maximum number of vertices that share their k-nearest neighbor: Because p is the nearest point for the remaining q ∈ Q, we apply Lemma 6 and conclude that at most ψ δ vertices are remaining in Q after k-reducing. Since every iteration of step (#) removed at most k − 1 points from Q, the cardinality of Q at the beginning of the process was at most Since at most k · ψ δ vertices can share a witness by Proposition 12, there are at least |I S | k·ψ δ distinct witnesses of vertices in S. We employ this bound to calculate the size of the sample T such that it contains at least one witness of an incomplete vertex in S with constant probability. Lemma 14. If |S| ≥ 10 √ n and |T | ≥ ln(10) · k · ψ δ · √ n, then Pr w∈T W S (w) = 0 ≤ 1 10 .
Proof. Since every vertex is sampled uniformly at random with replacement, the event that one vertex is a witness is a Bernoulli trial with probability Pr w∈V [W S (w) = 1] ≥ |I S | k·ψ δ · 1 n = |I S | k·ψ δ ·n . Therefore Pr w∈V [W S (w) = 0] ≤ 1 − |I S | k·ψ δ ·n . We have By Claim 9, Eq. (1) holds for |S| as chosen in Algorithm 1. In Eq. (2) we use the fact that 1 − x ≤ e −x and in Eq. (5) we use that all events W S (u) = 0 for u ∈ T are independent Bernoulli trials.
Finally, we observe that the factor k that is introduced in Proposition 12 is tight.
Lemma 15. For every δ ≥ 3, k ≥ 2, there exists a point set P ⊂ R δ such that there is a set of kψ δ points q i ∈ P that have the same k-nearest neighbor.

Lower Bound
We prove the first lower bound by constructing two (distributions of) graphs that are composed of multiple copies of the same building block. All graphs in one distribution are k-nearest neighborhood graphs, and all graphs in the other distribution are -far from the property. It suffices to show that no deterministic algorithm that makes o( √ n) queries can distinguish these two distributions with sufficiently high probability. Our building block is defined as follows.
Note that a line gadget is a k-nearest neighborhood graph itself. In the following, let k := k + 1. The graphs in the first distribution D 1 are composed of n/k line gadgets with sufficiently large pair-wise distances that maintain the k-nearest neighborhood property. The construction of the distribution of -far graphs D 2 is a bit more complicated. Basically, we want to move n/k line gadgets to the exact position of n/k other line gadgets such that in the resulting graph, n/k pairs of line gadgets share the same coordinates. However, we have to make sure that the algorithm is oblivious of this relocation with sufficiently high probability. Lemma 17. Testing whether a graph is a k-nearest neighborhood graph with two-sided error requires n/(8 k ) queries.
Proof. For the sake of simplicity, let n be a multiple of k . Let G = (V, E) be a graph that is composed of n/k line gadgets L 3k i for i ∈ [n/k ], and let D 1 be the uniform distribution over all vertex labellings of G. All graphs in D 1 are k-nearest neighborhood graphs. For every graph G ∈ D 1 , we define a random graph G as follows. Let S(G) = (s i ) i∈[2 n/k ] be a sequence of random numbers, drawn without replacement from the uniform distribution over [n]. For every i ∈ n/k , move the line gadget L 3k s i to the coordinates of L 3k s i+ n/k such that G contains no L 3k s i but two L 3k s i+ n/k afterwards. Note that G is -far from being a k-nearest neighborhood graph. Let D 2 be the uniform distribution over G∈D 1 G .
We may assume that if the tester queries for (a neighbor of) a vertex v, then the oracle returns the whole line gadget that v belongs to. This is only beneficial for the query complexity of the algorithm. We consider the knowledge graph of the algorithm, which is defined as the subgraph of the input graph that consists of the vertices, edges and non-edges that are revealed by the answers to the queries. Without loss of generality, we may assume that the algorithm only asks queries whose answers cannot be deduced from the knowledge graph. To prove the theorem, it is sufficient to show that for any deterministic algorithm that makes o( √ n) queries, the distributions of knowledge graphs that are obtained from distributions D 1 and D 2 , respectively, have small statistical distance.
First, note that every query of the algorithm to a graph from D 1 reveals a line gadget that is not in the knowledge graph yet. Let R be the set of revealed vertices after the i-th query q i . Then, the probability that q i+1 reveals a line gadget L 3k j is k /(n − k i) if L 3k j / ∈ R and 0 otherwise. We turn to D 2 now. Consider the i-th query q i . We claim that conditioned on the event that q 1 , . . . , q i+1 do not reveal two instances of a line gadget that is contained twice in the graph, then the line gadget that is revealed by q i+1 is distributed uniformly. Given G ∈ D 2 , let S j (G) be the j-th half of S(G) for j ∈ {1, 2} such that S(G) is the concatenation of S 1 (G) and S 2 (G), and let S 2 (G) denote the subset of S 2 (G) that has already been revealed. Let D 2 be the restriction of D 2 to the graphs that are compatible with the current knowledge graph, and the let be the support size of D 2 . We denote the event that a line gadget L 3k j is revealed by E j . Fix some arbitrary j. We have Therefore, the knowledge graph distribution of D 2 is exactly the same as the distribution of D 1 , i.e., uniform over all graphs that are compatible with current knowledge graph, as long as the algorithm does not reveal two line gadgets with the same coordinates. The probability that two line gadgets with the same coordinates are revealed by the first b = n/(8 k ) queries is upper bounded by the probability that for any pair of queries (i, j) ∈ [b] 2 , query i hits one of the k vertices in one of the n/k line gadgets L 3k s + n/k such that ∈ n/k , times the probability that query j hits the same gadget. In particular, by the union bound this probability is at most n k · k n · k n ≤ b 2 k n ≤ 1/4. Therefore, the total variation distance between the knowledge graph distributions is at most 1/4. In property testing, it is common to fix problem specific parameters such as the dimension and analyze the asymptotic behavior with respect to n and . However, it may be interesting that the computational complexity of a tester for k-nearest neighborhood graphs is at least linear in ψ δ . Lemma 18. Testing whether a graph of size n is a k-nearest neighborhood graph with two-sided error requires at least kψ δ /6 queries.
Proof sketch. Let P (q) be a point set as constructed in the proof of Lemma 15 with the common k-nearest neighbor located at q. Without loss of generality, assume that n = (c + 1) · |P | for some c ∈ N. Let q i = (i, 0, . . . , 0) ∈ R δ for i ∈ [c]. By scaling P accordingly, we can construct a set R = P (q 1 ) ∪ . . . ∪ P (q c ) such that for every i ∈ [c] and every p ∈ R ∩ P (q i ) \ {q i }, q i ∈ Q is the k-nearest neighbor of p. Let G be the k-nearest neighborhood graph of R.
We construct two graphs, G and H, and prove that one requires at least kψ δ /6 queries to distinguish between uniform distributions over all labellings of G and H, respectively. For i ∈ [ 2 c ] and some sufficiently small δ, we move q i to q i = (i − δ, 0, . . .) and insert a new point q i = (i + δ, 0, . . . , 0). Now, at least half of the vertices from P (q i ) have one of these points as k-nearest neighbor. Without loss of generality, let q i be this point. We obtain G by applying this modification to G . We obtain H from G by moving q i for every i ∈ [ 2 c ] to (−1, 0, . . . , 0) and recalculating the k-nearest neighbors for all these points. It follows that H is a k-nearest neighborhood graph, while G is -far from being a k-nearest neighborhood graph.
By the union bound, the probability to sample a point from Applying the union bound once again, it follows that the first kψ δ /6 queries to G or H will not contain any point from Q with probability greater than 1/3.

Experiments
As discussed above, property testing aims at distinguishing perfect objects and objects that have many flaws at very small cost. Given the output of an approximate nearest neighbor (ANN) algorithm, a natural use case for a property tester is to decide whether the nearest neighbor index computed by the ANN algorithm is accurate or resolves many queries incorrectly.
Although Algorithm 1 already gives values for the sizes of |S| and |T |, one would probably want to minimize the running time of the tester beyond worst-case analysis in practice. When used as a tool to assess an ANN index before actually putting it to work, it is also important that the tester actually reduces the total computation time compared to observing poor results at the end of the data processing pipeline (e.g., bad classification results) and starting over. Therefore, we seek to answer the following questions: Setup We implemented our property tester in C++ and integrated it into the Python framework ANN-Benchmarks [2,4]. The key-idea of ANN-Benchmarks is to compare the quality of the indices built by ANN implementations, with respect to their running times and query-answer times. To evaluate our property tester, we chose three algorithms with the best performance observed in [2]: KGraph [1] and hnsw and SW-graph from the Non-Metric Space Library [7,27]. All of the ANN algorithms are implemented in C / C++ and build upon nearest neighbor / proximity graphs. We computed the ground truth, i.e., a k-NN graph of the input data, for the Euclidean datasets MNIST (size 60 000, dimension 960, [24]), Fashion-MNIST (size 60 000, dimension 960, [30]) and SIFT (size 1 000 000, dimension 128, [18]) to evaluate the answers of the tester.
We ran our benchmarks on identical machines with 60 GB of free RAM guaranteed and an Intel Xeon E5-2640 v4 CPU running at 2.40 GHz (capable of running 20 concurrent threads) and measured CPU time. To minimize interference between different processes, a single instance of an ANN algorithm was run exclusively on one machine at a time.
The C++ source code of the property tester that was used for the experiments is available here [16]. The modified version of ANN-Benchmarks is available here [6].
Q1: Parameterization of the Property Tester We analyze how different choices for |S | and |T | in Algorithm 1 affect which quality of ANN indices the tester is likely to reject. All ANN algorithms were run ten times for each choice of parameters built into ann-benchmarks (as listed in [5]) and every dataset. Then the tester was run once for each output and for every choice from {0.001, 0.01, 0.1} × {0.05, 0.5, 5} for (c 1 , c 2 ) in |S | = c 1 · 8k √ n and |T | = c 2 · k √ n log(10), with oracle access to the resulting ANN index. We chose to evaluate the tester for k = 10 because indices that are very close to 10-NN graphs -which is the hard case for the property tester to detect -can be computed by the ANN algorithms in reasonable time, and we support this decision by an additional experiment for k = 50. The ground truth, i.e., a k-NN graph of each dataset, and the -distance (see Section 2) of each ANN index to a k-NN graph was computed offline.
We evaluate the recall of the property tester by distance of a tested ANN index to ground truth, where graphs that are no k-NN graphs are relevant (note that the tester always provides a witness when it rejects, so its precision is 1). Since the quality of an ANN index varies depending on the ANN algorithm's parameters and internal randomness, we group the computed ANN indices into buckets according to their distance to ground truth and depict the resulting recall on these classes in Fig. 1 for all datasets combined and for each dataset individually. As the oracle access that is provided to the property tester is oblivious of the underlying ANN algorithm, the figures show the combined results for all algorithms.
We observe that for distances and parameters that result in a reasonable overall recall, say, at least greater than 0.75, the property tester behaves comparable on all datasets. Since the property tester is guaranteed to have precision 1, even parameterizations with low recall on a small distance can be amplified by running the tester multiple times, possibly for different values of c 1 , c 2 . In summary, after choosing a target distance that the property tester should detect, the tested parameters seem suitable for data with dimensions up to roughly 800. For higher dimensions, it is likely advisable to apply dimensionality reduction techniques first before computing and using nearest neighbors in Euclidean space.
To get an indication of how the tester behaves for larger k, we conducted an additional experiment where we ran the tester on KGraph indices with k = 50. As one might expect, less indices are close to being a 50-NN graph than a 10-NN graph for the same sets of KGraph parameters (although the distance is normalized by k and therefore it allows more errors), but the results indicate that it is also easier for the property tester to spot errors. This suggests that, at least for KGraph, errors are spread quite uniformly in the index rather than they are concentrated on some vertices.
Q2: Performance Consider the following scenario: an algorithm that processes data employs an ANN index. The quality of the algorithm's result (e.g., the classification rate) depends on the quality of the ANN index. However, the best parameters for the ANN algorithm are not known, and conclusions about the quality of the ANN index can only be drawn by looking at the algorithm's final result, which may be a long costly way to go. Does it pay out to run the property tester on the ANN index and recompute the index using different parameters if the tester rejects? We address this question by measuring the tester's performance. However, whether to use the tester or not depends heavily on the cost incurred otherwise. Therefore, we compare the property tester against the minimum cost that every algorithm that uses an ANN index must invest before it can employ it or even just draw conclusions about its quality: the build time of the index. Figure 3 shows the time required by the property tester normalized (divided) by the time required to build the ANN index for each ANN algorithm and each dataset. There are two plots: one for all graphs that are between 0.005 and 0.01-close to a 10-NN graph, and one for all graphs that are between 0.01 and 0.02-close to a 10-NN graph.
In general, the running time of the property tester is always smaller than the build time for hnsw and SW-graph and at most five times the build time for KGraph. Mostly, it is even smaller than 1 /10 of the build time, and therefore running the property tester comes at almost no additional cost. For the runs of the tester on KGraph indices with k = 50, the testing time is also upper bounded by five times the build time and the tester time vs. build time ratio is 0.1 for k = 10 (restricted to MNIST and Fashion-MNIST) and k = 50.

Conclusion
We have studied the task of efficiently identifying NN models with low accuracy by exploring possibilities within the theoretical framework of sublinear algorithms and evaluated our approach by moving to experiments. In particular, we have proved that there is a one-sided error property tester with complexity O( √ nk 2 / 2 ), i.e., a sublinear (randomized) algorithm that decides whether an input graph G is a k-NN graph or requires many edge modifications to become a k-NN graph (i.e., precision 1 and recall 2/3 when taking -far graphs as relevant). We also proved that even a two-sided error property tester requires complexity Ω( n/( k)). Our experiments of the property tester on ANN indices computed by various algorithms indicate that testing comes at almost no additional cost, i.e., the testing time is significantly smaller than the building time of the ANN index that is tested.
From the perspective of applications, it would be desirable to analyze the tester for a more context sensitive notion of edit distance. For example, an edge to the (k + 1)-nearest neighbor of a point instead of an edge to its k-nearest neighbor might be a defect that is much less severe than an edge to the k 2 -nearest neighbor. It would be interesting to investigate what results can be obtained under established oracle access models, which are oblivious of the graph's structure, and whether other useful models can be devised.