Clustering with Non-adaptive Subset Queries

Abstract

Recovering the underlying $k$-clustering of a set $U$ of $n$ points by asking pair-wise same-cluster queries has garnered significant interest in the past few years. Given a query $S\subset U$, $|S|=2$, the oracle returns "yes" if the points are in the same cluster and "no" otherwise. For adaptive algorithms, the query complexity is known to be $\hat{I}˜(nk)$, while non-adaptive algorithms are extremely limited: even for $k=3$, such algorithms require $\hat{I}\text{c◯}(n^2)$ queries, matching the trivial upper bound. However, non-adaptivity is highly desirable since it allows queries to be asked in parallel. To break the quadratic barrier for non-adaptive queries, we study a natural generalization of this problem to subset queries for $|S|>2$, where the oracle returns the number of clusters intersecting $S$. Previous work obtained an $O(n)$ query adaptive algorithm, but the realm of non-adaptive algorithms remained completely unknown. In this paper, we give the first non-adaptive algorithms for clustering with subset queries. Our main result is a non-adaptive algorithm making $O(n\log k\cdot (\log k+\log \log n{)}^2)$ queries, improving to $O(n\log \log n)$ when $k$ is constant. In addition to non-adaptivity, we make other practical considerations, such as enforcing a bound, $s$, on the query size. We show $\hat{I}\text{c◯}(\max (n^2/s^2,n))$ queries are necessary and obtain algorithms making $\tilde{O}(n^{2}k/s^2)$ queries for any $s\le \sqrt{n}$ and $\tilde{O}(n^2/s)$ queries for any $s\le n$. Finally, we obtain improved upper bounds when the clusters are roughly balanced, and when the algorithm is allowed two rounds of adaptivity.

Minor fixes