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

Hendrik Fichtenberger, Dennis Rohde

Abstract

In the $k$-nearest neighborhood model ($k$-NN), we are given a set of points $P$ and must answer queries $q$ by returning the $k$ nearest neighbors of $q$ in $P$ according to a specific metric. While many $k$-NN algorithms exist, the relationship between their parameters and the resulting accuracy is often opaque. This paper investigates property testing of $k$-NN graphs: given a point set $P \subset \mathbb{R}^\delta$ and a directed graph $G=(P,E)$, is $G$ a true $k$-NN graph, or is it $\epsilon$-far from being one? We develop a randomized algorithm with one-sided error that decides this question with a complexity of $O(\sqrt{n} k^2 / \epsilon^2)$. Empirical evaluation demonstrates that our tester can detect low-accuracy $k$-NN models significantly faster than the time required to construct the models themselves.

Introduction: The Verification Gap

The $k$-nearest neighbor model is a fundamental component of modern data analysis, powering applications from computer vision to recommendation engines. As datasets scale into the millions, computing exact $k$-NN graphs becomes computationally prohibitive. Consequently, practitioners rely on Approximate Nearest Neighbor (ANN) algorithms such as HNSW or KGraph.

However, these approximations introduce a "verification gap." ANN algorithms depend on sensitive hyper-parameters; incorrect settings can result in graphs that are significantly inaccurate. Traditionally, verifying graph quality required either computing the ground truth—which defeats the efficiency of using an approximation—or waiting for downstream performance failures. This research proposes a "smoke detector" for $k$-NN graphs: a mathematical framework to verify graph integrity without inspecting every edge.

Theoretical Framework: Property Testing

The authors utilize the framework of Property Testing to bridge this gap. A property tester is a randomized algorithm designed to distinguish between an object having a specific property (being a true $k$-NN graph) and being "$\epsilon$-far" from that property. In this context, $\epsilon$-far means that more than an $\epsilon$-fraction of the edges in the graph would need to be modified to transform it into a valid $k$-NN graph.

The Algorithm

The proposed tester (Algorithm 1) employs a sublinear sampling strategy:

  1. Vertex Sampling ($S$): The algorithm selects a small, random subset of vertices to inspect.
  2. Witness Sampling ($T$): It selects another random subset of vertices to serve as potential "witnesses."
  3. The Proximity Test: For every vertex in $S$, the algorithm checks if any vertex in $T$ is closer than the neighbors currently assigned in the graph $G$.
  4. Degree Pruning: To maintain efficiency, the algorithm ignores vertices with an disproportionately high degree, a step justified by geometric constraints.

The complexity of this tester is $O(\sqrt{n} k^2 / \epsilon^2)$, which is significantly more efficient than the $O(n \log n)$ or $O(n^2)$ time typically required for full graph construction or exhaustive verification.

Key Insights

  • Geometric Constraints: The theory relies on the "kissing number" ($\psi_\delta$), the maximum number of non-overlapping unit spheres that can touch a central unit sphere. This geometric constant helps bound the number of points that can share the same nearest neighbor, ensuring the algorithm's efficiency.
  • One-Sided Error: The tester is conservative. If it identifies a single witness (a point closer than the listed neighbors), it rejects the graph with absolute certainty. If no such witness is found, it accepts the graph as likely accurate.
  • Independence from Ground Truth: A major advantage of this approach is that it does not require the actual $k$-nearest neighbors to be known beforehand. It only needs to find any point closer than the current edges to prove the graph is flawed.

Empirical Results

The tester was evaluated using three standard high-dimensional benchmarks: MNIST (60,000 images), Fashion-MNIST (60,000 images), and SIFT (1,000,000 descriptors). These were tested against popular ANN implementations including KGraph, HNSW, and SW-graph.

  • Efficiency: In practice, the property tester required approximately 1/10th of the time it took to build the initial index.
  • Sensitivity: The algorithm successfully identified poorly tuned parameters. It could distinguish between an index with 1% accuracy and one with 99% accuracy using very few queries.
  • Dimensionality Limits: Performance remained consistent up to approximately 800 dimensions. Beyond this, the "curse of dimensionality" begins to affect the geometric assumptions, suggesting that dimensionality reduction (e.g., PCA) should precede testing in extremely high-dimensional spaces.

Conclusion and Future Work

This property testing approach provides a robust, theory-based method for validating $k$-NN models in production pipelines. While highly effective, the authors note that the current definition of "$\epsilon$-far" treats all incorrect edges equally. Future work may explore a "context-sensitive" distance where an edge to a $(k+1)$-th neighbor is penalized less than an edge to a distant outlier. Additionally, mitigating the exponential growth of the kissing number in higher dimensions remains a key challenge for scaling these methods to even larger feature spaces.

Summary updated

Abstract

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.
BibTeX
@inproceedings{fichtenberger2018theory,
  author = {Hendrik Fichtenberger and Dennis Rohde},
  title = {{A Theory-Based Evaluation of Nearest Neighbor Models Put Into Practice}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
}
Figure