Walking on Minimax Paths for k-NN Search
(2013)

Link-based dissimilarity measures, such as shortest path or Euclidean commute time distance, base their distance on paths between nodes of a weighted graph. These measures are known to be better suited to data manifold with nonconvex-shaped clusters, compared to Euclidean distance, so that k-nearest neighbor (NN) search is improved in such metric spaces. In this paper we present a new link-based dissimilarity measure based on minimax paths between nodes. Two main benefits of minimax path-based dissimilarity measure are: (1) only a subset of paths is considered to make it scalable, while Euclidean commute time distance considers all possible paths; (2) it better captures nonconvex-shaped cluster structure, compared to shortest path distance. We define the total cost assigned to a path between nodes as Lp norm of intermediate costs of edges involving the path, showing that minimax path emerges from our Lp norm over paths framework. We also define minimax distance as the intermediate cost of the longest edge on the minimax path, then present a greedy algorithm to compute k smallest minimax distances between a query and N data points in O(logN + k log k) time. Numerical experiments demonstrate that our minimax kNN algorithm reduce the search time by several orders of magnitude, compared to existing methods, while the quality of k-NN search is significantly improved over Euclidean distance. Introduction Given a set of N data points X = {x1, . . . ,xN}, k-nearest neighbor (k-NN) search in metric spaces involves finding k closest points in the dataset X to a query xq . Dissimilarity measure defines distance duv between two data points (or nodes of a weighted graph) xu and xv in the corresponding metric space, and the performance of k-NN search depends on distance metric. Euclidean distance ‖xu − xv‖2 is the most popular measure for k-NN search but it does not work well when data points X lie on a curved manifold with nonconvex-shaped clusters (see Fig. 1(a)). Metric learning (Xing et al. 2003; Goldberger et al. 2005; Weinberger and Saul 2009) optimizes parameters involving the Mahalanobis distance using Copyright c © 2013, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. labeled dataset, such that points in the same cluster become close together and points in the different cluster become far apart. Most of metric learning methods are limited to linear embedding, so that the nonconvex-shaped cluster structure is not well captured (see Fig. 1(b)). Link-based (dis)similarity measures (Fouss et al. 2007; Yen, Mantrach, and Shimbo 2008; Yen et al. 2009; Mantrach et al. 2010; Chebotarev 2011) rely on paths between nodes of a weighted graph, on which nodes are associated with data points and intermediate costs (for instance Euclidean distance) are assigned to edge weights. Distance between nodes depends on the total cost that is computed by aggregating edge weights on a path connecting those nodes of interest. Total cost associated with a path is often assumed to be additive (Yen, Mantrach, and Shimbo 2008), so the aggregation reduces to summation. Dissimilarity between two nodes is calculated by integrating the total costs assigned to all possible paths between them. Such integration is often determined by computing the pseudo-inverse of the graph Laplacian, leading to Euclidean commute time distance (ECTD), regularized Laplacian kernel, and Markov diffusion kernel (see (Fouss et al. 2007; Yen, Mantrach, and Shimbo 2008; Fouss et al. 2012) and references therein), which are known to better capture the nonconvex-shaped cluster structure (see Fig. 1(c)). However, all possible paths between nodes need to be considered to compute the distances and the inversion of N × N matrix requires O(N) time and O(N) space, so it does not scale well to the problems of interest. Shortest path distance (Dijkstra 1959) is also a popular link-based dissimilarity measure (Tenenbaum, de Silva, and Langford 2000), where only shortest paths are considered to compute the distances between two nodes. Computational cost is reduced, but the cluster structure is not well captured when shortest path distance is used for k-NN search (see Fig. 1(d)). The distance between two nodes is computed along the shortest path only, Randomized shortest path (RSP) dissimilarity measures were proposed as a family of distance measures depending on a single parameter, which has interesting property of reducing, on one end, to the standard shortest path distance when the parameter is large, on the other hand, to the commute time distance when the parameter is near zero (Yen, Mantrach, and Shimbo 2008). In this paper we present a new link-based k-NN search method with minimax paths (Pollack 1960; Gower and Ross (a) Euclidean (b) LMNN (c) ECTD (d) Shortest path (e) Minimax distance Figure 1: Real-world datasets usually contain nonconvex-shaped clusters. For example, two curved clusters (dots) and a query point (star) are given. Heat map shows the closeness to the query at each point, in terms of the distance measure used (best viewed in color; more reddish means closer to the query). (a) Euclidean distance cannot reflect the underlying cluster structure at all. (b) Metric learning (Weinberger and Saul 2009) cannot capture the nonconvex shapes. (c) Link-based distance (Fouss et al. 2007) captures the underlying cluster correctly, but requires a large amount of computation. (d) Shortest path distance is efficient to compute, but it is not reliable near the boundary between different clusters. (e) Our method is as efficient as computing the shortest path distance, while capturing the entire cluster structure correctly. 1969), which is well-known to capture the underlying cluster structure of data (e.g., Fig. 1(e)) (Kim and Choi 2007; Luo et al. 2008; Zadeh and Ben-David 2009). We develop a fast k-NN search algorithm that computes the minimax distance efficiently through the minimax paths between data points. Our method is as efficient as the shortest-path distance computation. More specifically, the overall time for kNN search with N data points is onlyO(logN+k log k). In image retrieval experiments on some public image datasets, our method was several orders of magnitude faster, while achieving the comparable search quality (in terms of precision). The main contributions of this paper are summarized: 1. We develop a novel framework for link-based (dis)similarity measures where we define the total cost (corresponding to dissimilarity) assigned to a path between nodes as Lp norm of intermediate costs of edges involving the path, showing that minimax path emerges from our Lp norm over paths framework. This framework has two main benefits: (1) it can reduce the number of paths considered for the link-based (dis)similarity computation, which improves the scalability greatly; (2) even using a small number of paths, it can capture any nonconvex-shaped cluster structure successfully. 2. We define minimax distance as the intermediate cost of the longest edge on the minimax path, then present a greedy algorithm to compute k smallest minimax distances between a query and N data points in O(logN + k log k) time, whereas the state of the arts, minimax message passing (Kim and Choi 2007) requires O(N) time for k-NN search. Aggregation over Paths: Lp Norm Link-based (dis)similarity is defined on a weighted graph, denoted by G = (X , E): • The set of nodes, X = {x1, . . . ,xN}, are associated with N data points. E = {(i, j) | i 6= j ∈ {1, . . . , N}} is a set of edges between the nodes, excluding self-loop edges. • The graph is usually assumed to be sparse such that the number of edges, |E|, is limited to O(N). A well-known example is the K-NN graph, where an edge (i, j) exists only if xi is one of the K nearest neighbors of xj or xj is one of the K nearest neighbors of xi in the Euclidean space. The value of K is set to a small constant (usually 5-20) for ensuring sparsity. Then a link-based (dis)similarity depends on the total cost associated with paths on the graph. In this section, we describe our Lp norm approach to the cost aggregation over paths to compute the total cost along paths. Let a = (a0, a1, . . . , am) be a path with m hops, connecting the nodes xa0 ,xa1 , . . . ,xam ∈ X through the consecutive edges {(a0, a1), (a1, a2), . . . , (am−1, am)} ⊆ E . We denote a set of paths with m hops between an initial node xu and a destination node xv by Auv = { a ∣∣ a0 = u, am = v, (a`, a`+1) ∈ E , a` 6= v, ∀` = 0, . . . ,m− 1 } , (1) and denote a set of all possible paths between xu and xv by Auv = ∪m=1Auv. (2) A weight c(i, j) is assigned to each edge (i, j), representing the intermediate cost of following edge (i, j), usually defined as the Euclidean distance, i.e., c(i, j) = ‖xi − xj‖. We define the total cost associated with a path a as