Summary
The paper studies the clustering problem with non-adaptive subset queries. The problem formulation is as follows. Suppose we are given an oracle $q: \mathcal{V}\rightarrow \mathbb{R}$ such that for any query on a subset $S\subseteq V$ of vertices, the oracle returns how many clusters are in $S$ in the optimal clustering. The goal is to recover the optimal clustering with subset queries that are as small as possible. The problem setting is similar to the clustering with same-cluster query problem, where the oracle returns whether two vertices $(u,v)$ are in the same cluster in the optimal clustering. Both problems are motivated by scenarios where we could use semi-supervised learning to obtain such types of oracles. However, in that setting, the number of necessary queries becomes $\Omega(n^2)$ when $k$ is at least $3$. As such, to circumvent this strong barrier, it is natural to look into the new model with extra power for the queries.
In the new model, we can easily obtain an algorithm $O(n\log{k})$ queries by binary search. However, such an algorithm requires at least $\Theta(\log{k})$ rounds of adaptivity. The paper focused on the non-adaptive setting, where the queries have to be made *independent* of the results of previous queries. The main results include $i).$ an algorithm that makes $O(n \log\log{n})$ queries when $k=O(1)$ (linear dependency on $k$), and; $ii).$ an algorithm that makes $O(n\log^{2}{n} \log{k})$ queries for general $k$. The paper also studied the case when the maximum size of $S$ is bounded and obtained tight bounds when ${|S|}\leq \sqrt{n}$.
**Techniques.** The two main algorithms used different ideas. For the algorithm with constant $k$, the key observation is that after recovering the biggest cluster(s) in the queried set, there are non-trivial probability that the remaining of the queried set has exactly one or two points. For the two cases, we can recover clusters via subset queries for some specific sizes. As such, we can repeat enough times, and use a ‘valid’ set to recursively recover the clusters in the reconstruction phase. For the algorithm with general $k$, the paper reduces the problem to solving the OR queries of boolean vectors. In this way, the paper provides some new results for OR queries and obtains the desired bound.
Strengths
I have a positive view of the paper. In my opinion, the problem setting is well-motivated, and it is a natural extension of the well-studied same-cluster query model. The paper is well-written, and the authors did a nice job explaining the ideas in the high-level overview. Therefore, although the techniques are non-trivial, I managed to follow the ideas well. Given the page limits of the conference, the paper still managed to do fairly well in terms of organization.
Weaknesses
I don’t see any major issue in the paper. Some minor issues to address:
- It might be good to further clarify what ‘non-adaptive’ means in your paper. I think in your algorithm, you could still adaptively ‘add on’ to clusters *after* making the queries. For a moment I thought your algorithm could conduct $\log {n}$ rounds *in parallel* to recover all clusters, which will be even stronger in the ‘non-adaptive’ notion.
- The paper doesn’t contain experiments. I’m personally OK with it, but I think for NeurIPS you might want to justify why this is not an issue. I think AKB [NeurIPS’16] (‘clustering with same-cluster queries’) gives a nice motivation for the same-cluster oracle model, and maybe this paper should provide some similar justifications.
- The dependence on $k$ should be mentioned after theorem 1.2. I think $O(nk)$ is really not that bad – I thought it was something like $2^k$.
Questions
Most of the questions are asked in the ‘weakness’ part. Two MISC questions:
- Line 165: should it be $p\leq \log\log{n}$?
- If we just want the clustering of an $\alpha$ fraction of the vertices, can we use an even smaller number of queries?
Limitations
I do not see any potential negative societal impacts.