# Exact Recovery of Clusters in Finite Metric Spaces Using Oracle Queries

arXiv: https://arxiv.org/abs/2102.00504 · HTML: https://mlsanity.com/paper/2102.00504/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 40 references that are in the map.
- First posted on arXiv 31 Jan 2021.

## Builds on (most cited first, 11 of 11)

- [Clustering with Same-Cluster Queries](https://mlsanity.com/paper/1606.02404/) (2016)
- [S2: An Efficient Graph Based Active Learning Algorithm with Application to Nonparametric Classification](https://mlsanity.com/paper/1506.08760/) (2015)
- [Query Complexity of Clustering with Side Information](https://mlsanity.com/paper/1706.07719/) (2017)
- [Exact Recovery of Mangled Clusters with Same-Cluster Queries](https://mlsanity.com/paper/2006.04675/) (2020)
- [Active Learning on Trees and Graphs](https://mlsanity.com/paper/1301.5112/) (2013)
- [Phase transitions in semisupervised clustering of sparse networks](https://mlsanity.com/paper/1404.7789/) (2014)
- [Maximal Closed Set and Half-Space Separations in Finite Closure Systems](https://mlsanity.com/paper/2001.04417/) (2020)
- [Nearly optimal classification for semimetrics](https://mlsanity.com/paper/1502.06208/) (2015)
- [Search Improves Label for Active Learning](https://mlsanity.com/paper/1602.07265/) (2016)
- [Active Learning for Community Detection in Stochastic Block Models](https://mlsanity.com/paper/1605.02372/) (2016)
- [Active learning in the geometric block model](https://mlsanity.com/paper/1912.06570/) (2019)

## Built on by (most cited first, 9 of 9)

- [Active Learning with Simple Questions](https://mlsanity.com/paper/2405.07937/) (2024)
- [Bandits with Abstention under Expert Advice](https://mlsanity.com/paper/2402.14585/) (2024)
- [Efficient Algorithms for Learning Monophonic Halfspaces in Graphs](https://mlsanity.com/paper/2405.00853/) (2024)
- [On Margin-Based Cluster Recovery with Oracle Queries](https://mlsanity.com/paper/2106.04913/) (2021)
- [Active Learning of Classifiers with Label and Seed Queries](https://mlsanity.com/paper/2209.03996/) (2022)
- [Learning Weakly Convex Sets in Metric Spaces](https://mlsanity.com/paper/2105.06251/) (2021)
- [Efficient Algorithms for Learning and Compressing Monophonic Halfspaces in Graphs](https://mlsanity.com/paper/2506.23186/) (2025)
- [Fuzzy Clustering with Similarity Queries](https://mlsanity.com/paper/2106.02212/) (2021)
- [Self-Directed Learning of Convex Labelings on Graphs](https://mlsanity.com/paper/2409.01428/) (2024)

## Abstract (arXiv)

We investigate the problem of exact cluster recovery using oracle queries. Previous results show that clusters in Euclidean spaces that are convex and separated with a margin can be reconstructed exactly using only O(log n) same-cluster queries, where n is the number of input points. In this work, we study this problem in the more challenging non-convex setting. We introduce a structural characterization of clusters, called (β,γ)-convexity, that can be applied to any finite set of points equipped with a metric (or even a semimetric, as the triangle inequality is not needed). Using (β,γ)-convexity, we can translate natural density properties of clusters (which include, for instance, clusters that are strongly non-convex in ℝd) into a graph-theoretic notion of convexity. By exploiting this convexity notion, we design a deterministic algorithm that recovers (β,γ)-convex clusters using O(k2 log n + k2 (6/βγ)dens(X)) same-cluster queries, where k is the number of clusters and dens(X) is the density dimension of the semimetric. We show that an exponential dependence on the density dimension is necessary, and we also show that, if we are allowed to make O(k2 + klog n) additional queries to a "cluster separation" oracle, then we can recover clusters that have different and arbitrary scales, even when the scale of each cluster is unknown.