Clustering with a faulty oracle

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

DOI

  • Kasper Green Larsen
  • Michael Mitzenmacher, Harvard University
  • ,
  • Charalampos Tsourakakis, Boston University

Clustering, i.e., finding groups in the data, is a problem that permeates multiple fields of science and engineering. Recently, the problem of clustering with a noisy oracle has drawn attention due to various applications including crowdsourced entity resolution [33], and predicting signs of interactions in large-scale online social networks [20, 21]. Here, we consider the following fundamental model for two clusters as proposed by Mitzenmacher and Tsourakakis [28], and Mazumdar and Saha [25]; there exist n items, belonging to two unknown groups. We are allowed to query any pair of nodes whether they belong to the same cluster or not, but the answer to the query is corrupted with some probability . Let 1 > δ= 1 - 2q > 0 be the bias. In this work, we provide a polynomial time algorithm that recovers all signs correctly with high probability in the presence of noise with queries. This is the best known result for this problem for all but tiny d, improving on the current state-of-the-art due to Mazumdar and Saha [25].

Original languageEnglish
Title of host publicationWWW '20 : Proceedings of The Web Conference 2020
Editors Yennun Huang, Irwin King, Tie-Yan Liu, Maarten van Steen
Number of pages4
Place of publicationNew York
PublisherAssociation for Computing Machinery
Publication yearApr 2020
Pages2831-2834
ISBN (print)9781450370233
DOIs
Publication statusPublished - Apr 2020
EventWWW '20: The Web Conference 2020 - Taipei , Taiwan
Duration: 20 Apr 202024 Apr 2020

Conference

ConferenceWWW '20
LandTaiwan
ByTaipei
Periode20/04/202024/04/2020

    Research areas

  • active learning, clustering, randomized algorithms

See relations at Aarhus University Citationformats

ID: 191050192