RECORD
Query Complexity of Clustering with Side Information
Machine Learning · Submitted 23 Jun 2017
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim Our main contribution in this paper is to show the dramatic power of side information aka similarity matrix on reducing the query complexity of clustering.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
Suppose, we are given a set of $n$ elements to be clustered into $k$ (unknown) clusters, and an oracle/expert labeler that can interactively answer pair-wise queries of the form, "do two elements $u$ and $v$ belong to the same cluster?". The goal is to recover the optimum clustering by asking the minimum number of queries. In this paper, we initiate a rigorous theoretical study of this basic problem of query complexity of interactive clustering, and provide strong information theoretic lower bounds, as well as nearly matching upper bounds. Most clustering problems come with a similarity matrix, which is used by an automated process to cluster similar points together. Our main contribution in this paper is to show the dramatic power of side information aka similarity matrix on reducing the query complexity of clustering. A similarity matrix represents noisy pair-wise relationships such as one computed by some function on attributes of the elements. A natural noisy model is where similarity values are drawn independently from some arbitrary probability distribution $f_+$ when the underlying pair of elements belong to the same cluster, and from some $f_-$ otherwise. We show that given such a similarity matrix, the query complexity reduces drastically from $\Theta(nk)$ (no similarity matrix) to $O(\frac{k^2\log{n}}{\cH^2(f_+\|f_-)})$ where $\cH^2$ denotes the squared Hellinger divergence. Moreover, this is also information-theoretic optimal within an $O(\log{n})$ factor. Our algorithms are all efficient, and parameter free, i.e., they work without any knowledge of $k, f_+$ and $f_-$, and only depend logarithmically with $n$. Along the way, our work also reveals intriguing connection to popular community detection models such as the {\em stochastic block model}, significantly generalizes them, and opens up many venues for interesting future research.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Suppose, we are given a set of $n$ elements to be clustered into $k$ (unknown) clusters, and an oracle/expert labeler that can interactively answer pair-wise queries of the form, "do two elements $u$ and $v$ belong to the same cluster?". | background 0.99 | 0.09 | 0.02 | asserted 0.75 |
| s1 | The goal is to recover the optimum clustering by asking the minimum number of queries. | background 0.98 | 0.11 | 0.04 | asserted 0.90 |
| s2 | In this paper, we initiate a rigorous theoretical study of this basic problem of query complexity of interactive clustering, and provide strong information theoretic lower bounds, as well as nearly matching upper bounds. | contribution 1.00 | 0.95 | 0.11 | asserted 1.00 |
| s3 | Most clustering problems come with a similarity matrix, which is used by an automated process to cluster similar points together. | background 1.00 | 0.04 | 0.02 | asserted 0.98 |
| s4 | Our main contribution in this paper is to show the dramatic power of side information aka similarity matrix on reducing the query complexity of clustering. | contribution 0.94 | 0.95 | 0.90 | asserted 1.00 |
| s5 | A similarity matrix represents noisy pair-wise relationships such as one computed by some function on attributes of the elements. | background 0.75 | 0.09 | 0.02 | asserted 0.99 |
| s6 | A natural noisy model is where similarity values are drawn independently from some arbitrary probability distribution $f_+$ when the underlying pair of elements belong to the same cluster, and from some $f_-$ otherwise. | method 0.85 | 0.14 | 0.03 | asserted 0.65 |
| s7 | We show that given such a similarity matrix, the query complexity reduces drastically from $\Theta(nk)$ (no similarity matrix) to $O(\frac{k^2\log{n}}{\cH^2(f_+\|f_-)})$ where $\cH^2$ denotes the squared Hellinger divergence. | result 0.99 | 0.95 | 0.54 | asserted 1.00 |
| s8 | Moreover, this is also information-theoretic optimal within an $O(\log{n})$ factor. | result 0.91 | 0.91 | 0.13 | asserted 1.00 |
| s9 | Our algorithms are all efficient, and parameter free, i.e., they work without any knowledge of $k, f_+$ and $f_-$, and only depend logarithmically with $n$. | contribution 0.43 | 0.95 | 0.08 | asserted 1.00 |
| s10 | Along the way, our work also reveals intriguing connection to popular community detection models such as the {\em stochastic block model}, significantly generalizes them, and opens up many venues for interesting future research. | future work 0.42 | 0.93 | 0.06 | asserted 0.98 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
Suppose, we are given a set of $n$ elements to be clustered into $k$ (unknown) clusters, and an oracle/expert labeler that can interactively answer pair-wise queries of the form, "do two elements $u$ and $v$ belong to the same cluster?". The goal is to recover the optimum clustering by asking the minimum number of queries. In this paper, we initiate a rigorous theoretical study of this basic problem of query complexity of interactive clustering, and provide strong information theoretic lower bounds, as well as nearly matching upper bounds. Most clustering problems come with a similarity matrix, which is used by an automated process to cluster similar points together. Our main contribution in this paper is to show the dramatic power of side information aka similarity matrix on reducing the query complexity of clustering. A similarity matrix represents noisy pair-wise relationships such as one computed by some function on attributes of the elements. A natural noisy model is where similarity values are drawn independently from some arbitrary probability distribution $f_+$ when the underlying pair of elements belong to the same cluster, and from some $f_-$ otherwise. We show that given such a similarity matrix, the query complexity reduces drastically from $\Theta(nk)$ (no similarity matrix) to $O(\frac{k^2\log{n}}{\cH^2(f_+\|f_-)})$ where $\cH^2$ denotes the squared Hellinger divergence. Moreover, this is also information-theoretic optimal within an $O(\log{n})$ factor. Our algorithms are all efficient, and parameter free, i.e., they work without any knowledge of $k, f_+$ and $f_-$, and only depend logarithmically with $n$. Along the way, our work also reveals intriguing connection to popular community detection models such as the {\em stochastic block model}, significantly generalizes them, and opens up many venues for interesting future research.
Human review
How the literature uses it
1 arXiv paper cite this in 1 sentence
Papers citing it
Compares with it 1 paper
-
Mazumdar and Saha [ref] studied correlation clustering problem in a similar setting where edge similarity and dissimilarity information are assumed to be coming from two distributions.
Approximate Correlation Clustering Using Same-Cluster Queries · Introduction · 0.87
What it cites
Builds on 1 paper
-
The model of side information considered in this paper is a direct and significant generalization of the planted partition model, also known as the stochastic block model (SBM) [ref] .
Stochastic Block Model and Community Detection in the Sparse Graphs: A spectral algorithm with optimal rate of recovery · Introduction · 0.84
Compares with 1 paper
-
Perhaps conceptually closest to us is a recent work by Asthiani et al. [ref] , that was done independently of ours and appeared subsequent to a previous version of this work [ref] .
Clustering Via Crowdsourcing · Introduction · 0.92
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.