Learning Nearest Neighbor Graphs from Noisy Distance Samples

Blake Mason, Ardhendu Tripathy, Robert D. Nowak

Overview

In many real-world scenarios—from estimating internet topology to modeling human preferences—we need to identify the "most similar" item to a given object. However, we often lack a direct distance metric. Instead, we must rely on a "noisy oracle" (like a human judge or a fluctuating network sensor) that provides an estimate of the distance between two points.

Because querying an oracle is expensive, efficiency is paramount. Standard approaches often suffer from two major flaws:

  1. Restrictive Assumptions: They assume the data lives in a low-dimensional Euclidean space, which is often untrue for complex data like human perceptions.
  2. Wasted Information: They treat the search for each item's nearest neighbor as an independent task, failing to realize that a distance measurement between points $A$ and $B$ can tell us something about the distance between $B$ and $C$.

To address this, researchers introduce ANNTri (Active Nearest Neighbor with Triangle inequality), an active learning algorithm designed to reconstruct a nearest neighbor graph from noisy distance samples. By leveraging the triangle inequality to share information across queries, the algorithm achieves significant speedups over passive sampling and traditional embedding methods, especially in datasets with clustered structures.

The ANNTri Algorithm

The authors frame the problem as a variation of the "best-arm identification" problem in multi-armed bandits, but with a geometric twist. Key components of ANNTri include:

  • Active Sampling: Instead of querying all pairs equally, the algorithm uses a "successive elimination" strategy, focusing its budget on pairs that are most likely to be nearest neighbors.
  • The Triangle Inequality: This is the core innovation. If the algorithm has bounds on the distances $d(i, j)$ and $d(i, k)$, it uses the triangle inequality to derive lower and upper bounds for the unobserved distance $d(j, k)$.
  • Information Sharing: Unlike previous methods, ANNTri stores all empirical means and confidence intervals in symmetric matrices. This allows the results of a search for item $i$'s neighbor to prune the search space for item $j$'s neighbor.
  • Metric Generality: The approach only requires the metric to satisfy symmetry and the triangle inequality, making it far more flexible than Euclidean-based methods.
Clustered and hierarchical data structures

Geometry acts as a force multiplier here. The triangle inequality allows for "zero-cost" pruning. In clustered settings (like those shown above), the algorithm can rule out vast numbers of potential neighbors in distant clusters without ever querying the oracle for those specific pairs.

Datasets and Evaluation

The researchers evaluated ANNTri using both synthetic and real-world data:

  • Simulated Clustered Data: 10 clusters of 10 points in $\mathbb{R}^2$ with added Gaussian noise to test how the algorithm handles well-separated groups.
  • UT Zappos50K (Human Judgments): A subset of 85 shoe images. The "distances" were derived from crowd-sourced triplet judgments (e.g., "Is shoe A more similar to B or C?") collected via Amazon Mechanical Turk. This dataset is particularly interesting because human perception often violates strict Euclidean rules but generally follows "quasi-metric" properties.

Key Results

ANNTri avoids the bias introduced by traditional "ordinal embedding" (which tries to fit points into a $D$-dimensional map) by working directly with the metric properties of the samples. This leads to higher accuracy in predicting the true nearest neighbor.

Error curves comparing ANNTri to baselines
  • Query Complexity: In favorable clustered settings, the algorithm achieves a complexity of $O(n \log(n) \Delta^{-2})$, a massive improvement over the $O(n^2)$ complexity of passive approaches.
  • Sample Efficiency: As seen in the error curves, ANNTri demonstrated 5–10x gains in sample efficiency over random sampling on the Zappos dataset.
  • Superiority over STE: It outperformed the state-of-the-art Stochastic Triplet Embedding (STE) algorithm, showing up to 16x relative gains in identifying the correct nearest neighbors for shoe similarities.
  • Robustness: Even in Euclidean settings, ANNTri beat traditional "triangulation" methods because it is less sensitive to the noise propagation issues inherent in squared-distance estimations.

Limitations and Future Work

While ANNTri drastically reduces the number of queries to the oracle, its internal bookkeeping (updating triangle inequality bounds across matrices) can be computationally intensive for very large datasets ($n$). Furthermore, while the authors show it works empirically on "quasi-metrics," the theoretical guarantees rely on the triangle inequality holding strictly.

For future work, the authors suggest exploring hyperbolic embeddings, which naturally represent hierarchical or tree-like cluster structures better than flat metric spaces. They also aim to refine the algorithm for broader $k$-nearest neighbor graph construction.

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