Research map / Graph learning / Graph algorithms and clustering
Learning Nearest Neighbor Graphs from Noisy Distance Samples
Blake Mason, Ardhendu Tripathy, Robert Nowak
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use active querying with triangle-inequality bounds instead of random sampling | ANNTri · UT Zappos50K, 85 shoes | sample complexity: 5-10x | Improved |
| Use active querying with triangle-inequality bounds instead of ordinal embedding | ANNTri · UT Zappos50K, 85 shoes | sample complexity: up to 16x | Improved |
| Add triangle-inequality bounds to active nearest-neighbor search | ANNTri versus ANN · UT Zappos50K, 85 shoes | sample complexity: 2x | Improved |
| Add triangle-inequality bounds to active nearest-neighbor search | ANNTri versus ANN · UT Zappos50K, 85 shoes | sample complexity: around 2x | Improved |
| Use triangle-inequality bounds rather than Euclidean anchor triangulation | ANNTri · 2D simulated embedding | error rate | Improved |
| Use active triangle-based search rather than random sampling | ANNTri · Simulated 10 clusters of 10 points | error rate | Improved |
| Use triangle-inequality bounds rather than the simplified ANNEasy procedure (ablation) | ANNTri · Simulated 10 clusters of 10 points | error rate | Improved |
| Use triangle-inequality bounds rather than active sampling without them | ANNTri versus ANN · UT Zappos50K, 85 shoes | sample complexity: 2x | Improved |
| Use STE ordinal embedding instead of ANNTri | STE · UT Zappos50K, 85 shoes | nearest-neighbor accuracy: up to 16x | Hurt |
| Provide STE the full triplet set rather than a matched-size subsample | STE · UT Zappos50K, 85 shoes | nearest-neighbor error rate: 52% | No clear effect |
Closest papers by meaning
- One for All: Simultaneous Metric and Preference Learning over Multiple Users (NeurIPS 2022 · similarity 0.88)
- Near-Neighbor Methods in Random Preference Completion (AAAI 2019 · similarity 0.87)
- How Many Pairwise Preferences Do We Need to Rank a Graph Consistently? (AAAI 2019 · similarity 0.86)
- Graph Resistance and Learning from Pairwise Comparisons (ICML 2019 · similarity 0.86)
- A Theory-Based Evaluation of Nearest Neighbor Models Put Into Practice (NeurIPS 2018 · similarity 0.86)
- Embedding Dimension of Contrastive Learning and $k$-Nearest Neighbors (NeurIPS 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
