Same-Cluster Querying for Overlapping Clusters

Wasim Huleihel, Arya Mazumdar, Muriel Médard, Soumyabrata Pal

Introduction

In traditional clustering, we typically assume every data point belongs to exactly one group—a concept known as disjoint clustering. However, the real world is rarely so neat. A person can belong to multiple social circles, and a movie can span several genres. This scenario is known as overlapping clustering.

Recent research has demonstrated how to use "active querying"—asking an oracle if two items belong together—to speed up disjoint clustering. But the overlapping case introduces significant complexity. If an oracle says "yes" for elements $u$ and $v$, it might mean they share one cluster, or they might share five. If the oracle is restricted to a binary "yes/no," even more information is lost. This paper tackles the challenge of recovering overlapping clusters by asking an oracle simple "same-cluster" questions, aiming to find the minimum number of queries (query complexity) needed to perfectly recover these overlapping memberships.

Methodology: Decoding the Similarity Matrix

The authors approach the problem through the lens of the similarity matrix $AA^T$, where $A$ is an $n \times k$ matrix indicating which of the $n$ elements belong to which of the $k$ clusters.

Example of a similarity matrix indicating shared clusters (e.g., movie genres) between elements.

To provide theoretical guarantees and efficient algorithms, the researchers employ several key techniques:

  1. Generative Modeling: They analyze two random models: a Uniform Ensemble (where each element belongs to exactly $\Delta$ clusters) and an i.i.d. Ensemble (where membership is determined by a Bernoulli process).
  2. Rank Factorization: For "Direct Responses" (where the oracle reveals exactly how many clusters two items share), they leverage the fact that the similarity matrix is low-rank. By querying a small subset of elements to form a basis, they can reconstruct the rest of the matrix with far fewer than $O(n^2)$ queries.
  3. Triangle Counting (Profile Matching): For "Quantized/Noisy Responses" (binary yes/no with errors), they use a clever statistical trick. To determine if $u$ and $v$ share many clusters, they count how many other elements $w$ are "similar" to both. This "triangle count" acts as a robust proxy for true underlying similarity, even with unknown noise levels.
  4. Maximal Cliques: For worst-case scenarios lacking statistical assumptions, they propose an algorithm that builds a similarity graph and extracts maximal cliques to identify clusters.

Key Insights

A major breakthrough in the paper is identifying the Uniqueness Trap: knowing the similarity matrix $AA^T$ perfectly is not enough to recover the clusters $A$ without specific constraints. The authors prove that under their generative models, the factorization becomes unique (up to column permutation), making the problem solvable.

Furthermore, by treating the clustering matrix as a low-rank completion problem, they reduce the query complexity from $O(n^2)$ to roughly $O(nk)$ or $O(n \log n)$. Remarkably, their algorithms for noisy binary queries are parameter-free; they don't need to know the noise probability beforehand, inferring structure simply by comparing relative "similarity profiles."

Results and Performance

The authors provide information-theoretic lower bounds proving their algorithms are order-optimal. For a regime where the number of clusters $k = O(\log n)$, they show that $O(n \log n)$ queries are sufficient for recovery.

Performance metrics for $\Delta=2$, showing the decrease in errors and clustering failures as the number of observed entries (queries) increases.

When tested on the real-world MovieLens Dataset (using movie genres as ground-truth overlapping clusters), the algorithm achieved perfect recovery of movie categories using only about 10% of the total possible pairwise queries for movies belonging to up to two categories ($\Delta=2$). The algorithms also demonstrated strong noise tolerance, remaining effective even when the oracle's answers were randomly flipped.

Limitations and Future Work

While the query complexity is impressively low, the computational complexity of the worst-case algorithm involves finding maximal cliques—an NP-hard problem (though manageable for sparse graphs). Additionally, some of the strongest results rely on a "Direct Response" oracle that provides exact counts of shared clusters, whereas human crowdsourcing is typically better suited for binary "yes/no" answers. Finally, the query complexity for noisy responses scales exponentially with the number of overlaps ($\Delta$), leaving the efficient handling of highly overlapping data as an open challenge for future research.

Summary updated

Abstract

Overlapping clusters are common in models of many practical data-segmentation applications. Suppose we are given $n$ elements to be clustered into $k$ possibly overlapping clusters, and an oracle that can interactively answer queries of the form ``do elements $u$ and $v$ belong to the same cluster?'' The goal is to recover the clusters with minimum number of such queries. This problem has been of recent interest for the case of disjoint clusters. In this paper, we look at the more practical scenario of overlapping clusters, and provide upper bounds (with algorithms) on the sufficient number of queries. We provide algorithmic results under both arbitrary (worst-case) and statistical modeling assumptions. Our algorithms are parameter free, efficient, and work in the presence of random noise. We also derive information-theoretic lower bounds on the number of queries needed, proving that our algorithms are order optimal. Finally, we test our algorithms over both synthetic and real-world data, showing their practicality and effectiveness.
BibTeX
@inproceedings{huleihel2019same,
  author = {Wasim Huleihel and Arya Mazumdar and Muriel Médard and Soumyabrata Pal},
  title = {{Same-Cluster Querying for Overlapping Clusters}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=mqY4Q6JKZ4q},
}
Figure