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.
Introduction
Clustering is a fundamental task in data science, yet traditional "flat" models—where each data point belongs to exactly one group—often fail to capture the complexity of real-world relationships. In social networks, individuals belong to multiple circles (e.g., family, colleagues, hobbyists). In content recommendation, a movie might span several genres. This paper addresses the challenge of active clustering for overlapping structures. In this paradigm, an algorithm interactively queries an "oracle" (such as a human expert) to determine if two elements $u$ and $v$ share at least one cluster. The objective is to reconstruct the full overlapping membership structure using the minimum number of queries.
Methodology
The problem is modeled using a membership matrix $A \in \{0, 1\}^{n \times k}$, where $A_{i,j}=1$ if element $i$ belongs to cluster $j$. The similarity matrix $S = AA^T$ captures the number of shared clusters between pairs. The authors explore three oracle models:
- Direct: The oracle returns the exact count of shared clusters ($S_{i,j}$).
- Quantized (Binary): The oracle returns a binary indicator $\mathbb{1}(S_{i,j} > 0)$.
- Noisy/Dithered: Binary responses are corrupted by noise with probability $q$.
To recover $A$ from $S$, the authors propose several strategies:
- Factorization Algorithms: Leveraging the low-rank structure of $S$ to decompose it into $A$.
- Triangle Counting: A statistical approach for noisy environments that counts mutual neighbors to infer true connectivity.
- Worst-Case Algorithm: A parameter-free method that identifies clusters by finding maximal cliques in a similarity graph, robust even without specific generative assumptions.
Key Insights: The Uniqueness Hurdle
A primary challenge in overlapping clustering is that the similarity matrix $S = AA^T$ does not always uniquely determine the membership matrix $A$. This "uniqueness hurdle" is a fundamental theoretical barrier that the authors address.
The authors prove that for random generative models (like Uniform or i.i.d. Bernoulli ensembles), factorization becomes unique with high probability as the number of elements $n$ increases. Furthermore, they demonstrate that their algorithms are order optimal, matching information-theoretic lower bounds on query complexity.
Experimental Results
The algorithms were evaluated on synthetic data and the MovieLens dataset. For MovieLens, the goal was to recover genre memberships for movies that belong to multiple categories.
Key findings include:
- Query Efficiency: On MovieLens (with $\Delta=2$ overlaps), the "Worst-Case" algorithm achieved perfect recovery using only ~10% of possible queries. In some configurations, error rates vanished with as few as 2.5% of queries.
- Scalability: For a fixed number of clusters $k$, the complexity is polynomial in $n$. If $k$ grows as $O(\log n)$, it remains quasi-polynomial.
- Noise Robustness: The "Noisy Responses" algorithm successfully reconstructed clusters without prior knowledge of the noise level $q$, proving its utility for crowdsourced data.
Conclusion
This work extends active clustering to the more realistic domain of overlapping memberships. By providing order-optimal algorithms that are both efficient and noise-robust, the authors bridge the gap between theoretical query complexity and practical data segmentation. Future work may focus on approximate recovery to further scale these methods for massive datasets.
Summary updated