Walking on Minimax Paths for k-NN Search

Kye-Hyeon Kim, Seungjin ChoiAAAI 2013 · DOI

Abstract

This paper addresses the limitations of Euclidean distance in $k$-Nearest Neighbor ($k$-NN) search for data residing on non-convex manifolds. We introduce the minimax distance, defined by the "bottleneck" edge of the optimal path between points, as a robust alternative. By framing distance metrics within an $L_p$ norm framework, we show that minimax distance ($p \to \infty$) effectively captures manifold structures that Euclidean ($p=2$) and shortest-path ($p=1$) distances fail to resolve. We present MM-kNN, a greedy algorithm that achieves $O(\log N + k \log k)$ query complexity, offering a scalable solution for large-scale, high-precision manifold search.

Introduction

Standard $k$-NN search typically relies on Euclidean distance, which assumes that data points in the same cluster are physically close in a straight line. However, real-world data often lives on curved manifolds (like a "Swiss roll" or intertwined moons). In these cases, two points might be "close" in Euclidean space but belong to entirely different clusters.

Existing "link-based" distances, such as Commute Time Distance (ECTD), solve this by looking at paths through a graph of the data. While accurate, these methods usually require matrix inversions or eigen-decompositions, leading to $O(N^3)$ or $O(N^2)$ complexity—making them unusable for large datasets. Conversely, Shortest Path distance (used in Isomap) is efficient but often fails near cluster boundaries where a single "short-circuit" edge can bridge two distinct groups.

Methodology

The authors propose a unified framework using the $L_p$ norm to define path costs. Given a path between two nodes, the total cost is the $L_p$ norm of the weights of the edges along that path.

  • When $p=1$, the measure becomes the standard Shortest Path distance.
  • When $p \to \infty$, the measure becomes Minimax distance.

Minimax distance is defined as the weight of the longest edge on the path that minimizes this maximum edge weight. Intuitively, to travel from point A to point B, one seeks a path where the "widest gap" (bottleneck) is minimized.

The MM-kNN Algorithm

The core contribution is a greedy algorithm to find the $k$ smallest minimax distances for a query point. It functions similarly to Dijkstra’s algorithm but uses the minimax criterion to update distances. By utilizing a Fibonacci heap, they achieve a query time complexity of $O(\log N + k \log k)$, which is significantly faster than previous message-passing approaches for minimax distance.

Experimental Setup

The method was evaluated on several benchmarks:

  • Synthetic: A "Two-moon" toy dataset with up to 1,000,000 points to test scalability.
  • Image Retrieval: Datasets including Yale-B (faces), COIL-100 (objects), Animal (poses), and USPS (digits).

Results and Discussion

Qualitative comparison of distance metrics on a non-convex manifold. Minimax distance (e) successfully follows the data structure without 'leaking' across clusters, unlike Euclidean (a) or Shortest Path (d) distances. Source, p. 2

Qualitative comparison of distance metrics on a non-convex manifold. Minimax distance (e) successfully follows the data structure without 'leaking' across clusters, unlike Euclidean (a) or Shortest Path (d) distances.

The qualitative success of the minimax distance is demonstrated in Figure 1. Heatmaps show that minimax distance "flows" along the manifold of the data, whereas Euclidean distance "leaks" across the empty space between clusters.

Key insights include:

  • The Bottleneck Principle: Minimax distance is powerful because points within a dense cluster are connected by many short edges. To move to a different cluster, a path must eventually cross a sparse region via a long edge. This "bottleneck" edge becomes the defining distance, effectively separating non-convex clusters.
  • Efficiency: On the Two-moon dataset, MM-kNN was several orders of magnitude faster than the $L^+$ (Laplacian pseudo-inverse) method. For $N=10^6$, $L^+$ is computationally infeasible, while MM-kNN provides results in milliseconds.
  • Search Quality: In image retrieval tasks, MM-kNN significantly outperformed both Euclidean and Shortest Path distances in terms of precision.

Conclusion

While minimax distance is highly effective, it remains sensitive to the initial construction of the $K$-NN graph. If the graph is too dense, "short-circuit" edges may appear, causing the distance to underestimate cluster separation. However, its logarithmic scaling and superior precision on manifold data make it a viable candidate for web-scale $k$-NN search. Future work may explore automated ways to determine optimal graph sparsity for varying data distributions.

Summary updated

BibTeX
@inproceedings{kim2013walking,
  author = {Kye-Hyeon Kim and Seungjin Choi},
  title = {{Walking on Minimax Paths for k-NN Search}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2013},
  doi = {10.1609/aaai.v27i1.8588},
}
Figure