Learning Nearest Neighbor Graphs from Noisy Distance Samples

Blake Mason, Ardhendu Tripathy, Robert D. Nowak

Abstract

We consider the problem of learning the nearest neighbor graph of a dataset of $n$ items. The metric is unknown, but we can query an oracle to obtain a noisy estimate of the distance between any pair of items. This framework applies to problem domains where one wants to learn people's preferences from responses commonly modeled as noisy distance judgments. In this paper, we propose an active algorithm to find the graph with high probability and analyze its query complexity. In contrast to existing work that forces Euclidean structure, our method is valid for general metrics, assuming only symmetry and the triangle inequality. Furthermore, we demonstrate efficiency of our method empirically and theoretically, needing only $O(n \log(n)\Delta^{-2})$ queries in favorable settings, where $\Delta^{-2}$ accounts for the effect of noise. Using crowd-sourced data collected for a subset of the UT Zappos50K dataset, we apply our algorithm to learn which shoes people believe are most similar and show that it beats both an active baseline and ordinal embedding.

Introduction

In many real-world scenarios—ranging from estimating internet topology via network delays to understanding human preferences—the goal is to determine which items are "closest" or "most similar" to one another. However, direct access to true underlying distances is rare. Instead, researchers often rely on a "stochastic oracle" that provides noisy estimates of distances between pairs of items.

The objective is to construct the Nearest Neighbor (NN) Graph, where every point is connected to its closest neighbor, using a minimum number of queries. Traditional approaches frequently assume that data resides in a low-dimensional Euclidean space ($\mathbb{R}^d$). This assumption is often too restrictive, particularly for subjective human judgment data. This work addresses the problem for general metrics, requiring only that distances satisfy symmetry and the triangle inequality.

The ANNTri Algorithm

The core contribution of this research is ANNTri (Active Nearest Neighbor with Triangle inequality). This active learning algorithm improves upon standard multi-armed bandit frameworks, specifically "best-arm identification," through two primary mechanisms:

  1. Symmetry and Information Sharing: When the algorithm queries the distance between $x_i$ and $x_j$ to identify $x_i$'s neighbor, it caches the result for future use when determining $x_j$'s neighbor.
  2. Triangle Inequality Pruning: By leveraging the triangle inequality, ANNTri derives upper and lower bounds on unmeasured distances. If $x_i$ is known to be close to $x_j$, and $x_j$ is far from $x_k$, the algorithm can mathematically infer that $x_i$ is likely far from $x_k$ without a direct query.
Illustration of clustered and hierarchical data structures exploited by ANNTri.

The algorithm employs a modified Successive Elimination strategy. It maintains an "active set" of potential nearest neighbors for each point and prunes candidates whose lower distance bounds exceed the minimum possible upper bound. This geometric pruning is particularly effective in clustered or hierarchical data structures, as shown in the figure above.

Key Insights

  • Geometric Filtering: The triangle inequality acts as a powerful filter. In clustered data, once the algorithm identifies a point's general neighborhood, it can eliminate the vast majority of the dataset as potential nearest neighbors without direct measurement.
  • Metric-Agnosticism: Unlike methods like Stochastic Triplet Embedding (STE) that force data into Euclidean constraints, ANNTri respects raw metric structure. This makes it more robust for human judgments, which may violate Euclidean axioms but typically follow basic metric principles.
  • Complexity and Separation: While the algorithm's complexity can depend on the processing order of points, this dependence diminishes for well-separated clusters, leading to optimal discovery rates.

Experimental Results

The authors evaluated ANNTri using synthetic simulations and the UT Zappos50K shoe dataset. For the latter, crowd-sourced "triplet" judgments were converted into a distance metric to simulate a human oracle.

Comparison of error rates for Rand, ANN, and ANNTri algorithms.

Key Findings:

  • Theoretical Efficiency: In favorable settings, ANNTri achieves a query complexity of $O(n \log n \Delta^{-2})$, matching lower bounds for noiseless versions while accounting for noise.
  • Empirical Performance: On the Zappos dataset, ANNTri was 5–10x more sample-efficient than random sampling. As shown in the error curves, ANNTri (green) achieves a low error rate with significantly fewer samples per point compared to the standard ANN (red) and random (blue) baselines.
  • Superior Accuracy: ANNTri significantly outperformed STE in predicting nearest neighbors, demonstrating that avoiding rigid Euclidean assumptions improves performance in subjective tasks.

Limitations and Future Work

While highly effective, ANNTri assumes a strict metric. Human judgments sometimes form "quasi-metrics" that violate the triangle inequality. While the algorithm can be adjusted with multiplicative constants, this remains a challenge. Additionally, maintaining all-pairs triangle bounds can be computationally intensive ($O(n^3)$). Future research may extend this framework to $k$-nearest neighbor graphs or more complex topologies.

Summary updated

Abstract

We consider the problem of learning the nearest neighbor graph of a dataset of n items. The metric is unknown, but we can query an oracle to obtain a noisy estimate of the distance between any pair of items. This framework applies to problem domains where one wants to learn people's preferences from responses commonly modeled as noisy distance judgments. In this paper, we propose an active algorithm to find the graph with high probability and analyze its query complexity. In contrast to existing work that forces Euclidean structure, our method is valid for general metrics, assuming only symmetry and the triangle inequality. Furthermore, we demonstrate efficiency of our method empirically and theoretically, needing only O(n log(n)Delta^-2) queries in favorable settings, where Delta^-2 accounts for the effect of noise. Using crowd-sourced data collected for a subset of the UT Zappos50K dataset, we apply our algorithm to learn which shoes people believe are most similar and show that it beats both an active baseline and ordinal embedding.
BibTeX
@inproceedings{mason2019learning,
  author = {Blake Mason and Ardhendu Tripathy and Robert D. Nowak},
  title = {{Learning Nearest Neighbor Graphs from Noisy Distance Samples}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=O9aAkHRrsw},
}
Figure