Query-Efficient Correlation Clustering with Noisy Oracle

2024-02-02 · Yuko Kuroki, Atsushi Miyauchi, Francesco Bonchi, Wei Chen

We study a general clustering setting in which we have $n$ elements to be clustered, and we aim to perform as few queries as possible to an oracle that returns a noisy sample of the weighted similarity between two elements. Our setting encompasses many application domains in which the similarity function is costly to compute and inherently noisy. We introduce two novel formulations of online learning problems rooted in the paradigm of Pure Exploration in Combinatorial Multi-Armed Bandits (PE-CMAB): fixed confidence and fixed budget settings. For both settings, we design algorithms that combine a sampling strategy with a classic approximation algorithm for correlation clustering and study their theoretical guarantees. Our results are the first examples of polynomial-time algorithms that work for the case of PE-CMAB in which the underlying offline optimization problem is NP-hard.

📄 PDF Abstract BibTeX arXiv:2402.01400

Code (0)

등록된 구현이 없습니다.

Tasks

ClusteringMulti-Armed Bandits

Clustering with Noisy Queries

2017-06-22 · NeurIPS 2017 12 · Arya Mazumdar, Barna Saha

In this paper, we initiate a rigorous theoretical study of clustering with noisy queries (or a faulty oracle). Given a set of $n$ elements, our goal is to recover the true clustering by asking minimum number of pairwise …

Clustering Entity Resolution Stochastic Block Model

Metric $k$-clustering using only Weak Comparison Oracles

2026-01-27 · Rahul Raychaudhury, Aryan Esmailpour, Sainyam Galhotra, Stavros Sintos arxiv

Clustering is a fundamental primitive in unsupervised learning. However, classical algorithms for $k$-clustering (such as $k$-median and $k$-means) assume access to exact pairwise distances -- an unrealistic requirement …

Correlation Clustering with Same-Cluster Queries Bounded by Optimal Cost

2019-08-14 · Barna Saha, Sanjay Subramanian

Several clustering frameworks with interactive (semi-supervised) queries have been studied in the past. Recently, clustering with same-cluster queries has become popular. An algorithm in this setting has access to an ora…

Clustering Graph Clustering

Towards a Query-Optimal and Time-Efficient Algorithm for Clustering with a Faulty Oracle

2021-06-18 · Pan Peng, Jiapeng Zhang

Motivated by applications in crowdsourced entity resolution in database, signed edge prediction in social networks and correlation clustering, Mazumdar and Saha [NIPS 2017] proposed an elegant theoretical model for study…

Clustering Entity Resolution Open-Ended Question Answering Stochastic Block Model

Error-Tolerant Exact Query Learning of Finite Set Partitions with Same-Cluster Oracle

2023-05-22 · Adela Frances DePavia, Olga Medrano Martín del Campo, Erasmo Tani

This paper initiates the study of active learning for exact recovery of partitions exclusively through access to a same-cluster oracle in the presence of bounded adversarial error. We first highlight a novel connection b…

Active Learning Clustering