Exact Recovery of Clusters in Finite Metric Spaces Using Oracle Queries
arXiv:2102.00504
Abstract
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 same-cluster queries, where 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 ) into a graph-theoretic notion of convexity. By exploiting this convexity notion, we design a deterministic algorithm that recovers -convex clusters using same-cluster queries, where is the number of clusters and 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 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.
arXiv commentAccepted for presentation at the Conference on Learning Theory (COLT) 2021
References in corpus (7)
- Phase transitions in semisupervised clustering of sparse networks
- Clustering with Same-Cluster Queries
- Active Learning on Trees and Graphs
- Active Semi-Supervised Learning using Submodular Functions
- Query Complexity of Clustering with Side Information
- Active Learning for Community Detection in Stochastic Block Models
- Exact Recovery of Mangled Clusters with Same-Cluster Queries