Clustering with Non-adaptive Subset Queries
Authors: Hadley Black
Euiwoong Lee
Arya Mazumdar
Barna Saha
Venue: NeurIPS 2024 poster (2024)
Keywords: Clustering
query algorithms
Primary area: learning_theory
TL;DR: We provide efficient non-adaptive algorithms that query a near-linear (and near-optimal) number of subset-queries to infer clustering of a set of elements exactly.

Abstract: Recovering the underlying clustering of a set $U$ of $n$ points by asking pair-wise same-cluster queries has garnered significant interest in the last decade. Given a query $S \subset U$, $|S|=2$, the oracle returns "yes" if the points are in the same cluster and "no" otherwise. We study a natural generalization of this problem to subset queries for $|S|>2$, where the oracle returns the number of clusters intersecting $S$. Our aim is to determine the minimum number of queries needed for exactly recovering an arbitrary $k$-clustering. We focus on non-adaptive schemes, where all the queries are asked in one round, thus allowing for the querying process to be parallelized, which is a highly desirable property. 

For adaptive algorithms with pair-wise queries, the complexity is known to be $\Theta(nk)$, where $k$ is the number of clusters. 
In contrast, non-adaptive pair-wise query algorithms are extremely limited: even for $k=3$, such algorithms require $\Omega(n^2)$ queries, which matches the trivial $O(n^2)$ upper bound attained by querying every pair of points. Allowing for subset queries of unbounded size, $O(n)$ queries is possible with an adaptive scheme.  However, the realm of non-adaptive algorithms remains completely unknown. Is it possible to attain algorithms that are non-adaptive while still making a near-linear number of queries?

In this paper, we give the first non-adaptive algorithms for clustering with subset queries. We provide, (i) a non-adaptive algorithm making $O(n \log^2 n \log k)$ queries which improves to $O(n \log k)$ when the cluster sizes are within any constant factor of each other, (ii) for constant $k$, a non-adaptive algorithm making $O(n \log{\log{n}})$ queries. In addition to non-adaptivity, we take into account other practical considerations, such as enforcing a bound on query size.  For constant $k$, we give an algorithm making $\smash{\widetilde{O}(n^2/s^2)}$ queries on subsets of size at most $s \leq \sqrt{n}$, which is optimal among all non-adaptive algorithms within a $\log n$-factor. For arbitrary $k$, the dependence varies as $\tilde{O}(n^2/s)$.

Clustering with Non-adaptive Subset Queries
Hadley Black
Euiwoong Lee
Arya Mazumdar UC San Diego
Barna Saha UC San Diego
UC San Diego
University of Michigan
Abstract
Recovering the underlying clustering of a set of n. points by asking pair-wise same-cluster queries has garnered significant interest in the last decade. Given query C U. |S| = 2, the oracle returns yes if the points are in the same cluster and otherwise. We study a natural generalization of this problem subset queries for |S] > 2, where the oracle returns the number of clusters intersecting determine the minimum number of queries needed for exactly
S. Our aim recovering an arbitrary k-clustering. We focus on non-adaptive schemes, where all the queries are asked in one round, thus allowing for the querying process be parallelized, which is a highly desirable property.
For adaptive algorithms with pair-wise queries, the complexity is known to be (nkk), where is the number of clusters. contrast, non-adaptive pair-wise query algorithms are extremely limited: even for k = 3, such algorithms require Q(n²) queries, which matches the trivial O(n²) upper bound attained by querying every pair of points. Allowing for subset queries of unbounded size, O(n) queries is possible with an adaptive scheme. However, the realm of non non- adaptive algorithms remains completely unknown. Is it possible to attain algorithms that are non- adaptive while still making a near-linear number of queries?
In this paper, we give the first non-adaptive algorithms for clustering with subset queries. We provide, (i) a non-adaptive algorithm making (n log n log k) queries which improves to (( log k) when the cluster sizes within any constant factor each other, (ii) for constant k, non-adaptive algorithm making O log log n) queries. In addition non-adaptivity, we take into account other practical con- siderations, such as enforcing bound on query size. For constant k, we give an algorithm making Ón²² /²) queries on subsets of size at most vT, which is optimal among all non-adaptive algorithms within a log n-factor. For arbitrary k; the dependence varies as (nn² 2/2/// /s).
Introduction
Clustering is one of the most fundamental problems unsupervised machine learning, and permeates beyond the boundaries of statistics and computer science social sciences, economics and The goal of clustering is to partition items so that similar items are in the same group. The applications of clustering manifold. However, finding the underlying clusters is sometimes hard for automated process due to data being noisy, incomplete, but casily discernible by humans. Motivated by this scenario, in order to improve the quality of clustering, early works have studied the so-called clustering under "limited supervision" (e.g.-[1. 2]). Balcan and Blum initiated the study of clustering under active feedback [3] where given the current clustering solution, the whether a cluster needs to be merged or split. Perhaps simpler query model would be where users only need to answer the number clusters, and that too only on subset points without requiring to analyze the entire clustering. This scenario is common in unsupervised learning problems, where a centralized algorithm aims to compute clustering by crowdsoureing. The cookerworkers play the role of an oracle here, and are able to answer simple queries that involve a small subset of the universe.
provide feedback
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Mazumdar and Saha [4, 5, 6], and in independent works Mitzenmacher and Tsourakis [7], as well as Asthani, Kushagra and Ben-David [8] initiated a theoretical study of clustering with pair-wise aka same-cluster queries. Given any pair of points u, vt the oracle returns whether u and v belong to the same cluster or not. Such queries are easy to answer and lend itself to simple implementations [9]. This has been subsequently extremely well-studied in the literature, e.g. [10, 11, 4, 12, 13]. In fact, triangle-queries have also been studied, c.g. [14]. Moreover, clustering with pair-wise queries is intimately related to several well-studied problems such correlation clustering [15, 16, 17, 10, 18], edge-sign prediction problem [19, 7J, stochastic block model [20, 21] etc.
Depending on whether there is an interaction between the learner/algorithm and the oracle, the querying algorithms can be classified as adaptive and non- adaptive [5]. In adaptive querying, the learner can decide the next query based on the answers to the previous queries. An algorithm is called non-adaptive if all of its queries can be specified in one-round. Non-adaptive algorithms can parallelize the querying process as they decide the entire set of queries apriori. This may greatly speed up the algorithm in practice, significantly reducing the time to acquire answers [22]. Thus, in crowdsourcing setting being non-adaptive is highly desirable property. On the flip side, this makes non-adaptive algorithms significantly harder to design. In fact, when adaptivity is allowed, nk pair-wise queries are both necessary and sufficient to recover the entire clustering, where is the number of points in the ground set to be clustered and (unknown) is the number of clusters. However shown in [5] and our Theorem C.I. even for k 3, even randomized non adn-aiaeeive algorithms can do no better than the trivial (n²) upper bound attained by querying all pairs.
We study a generalization of pair-wise queries to subset queries, where given any subset of points, the oracle returns the number of clusters in it. We consider the problem of recovering an unknown k-clustering (a partition) on a universe U of n points via black-box access to subset query oracle. More precisely, assume that there exists a groundtruth partitioning of U =L-= C. and upon querying with a subset S C U, the oracle returns (SS) = Hi: : n & 0}|, the number of clusters intersecting S. Considering the limitations of pair-wise queries for non-adaptive schemes, we ask the question if it is possible to use subset queries to design significantly hetter non-adaptive algorithms.
In addition to being natural model for interactive clustering, this problem also falls into the growing body of work known as combinatorial search [23, 24] where the goal is to reconstruct a hidden object by viewing it through the lens of some indirect query model (such as group testing [25, 26, 24, 27, 28]). The problem is also intimately connected to coin weighing where given a hidden vector x E {0, 1)", the goal is to reconstruct using queries of the form (S) == Eies I3 for S S [m]] It is known that (nn/ log n) is the optimal number of queries [29, 30, 31J. which can be obtained by non-adaptive algorithm. There are improvements for the case when |||||| = d for d < n [32, 33, 34]. Moreover, there has been significant work on graph reconstruction where the task is to reconstruct hidden graph G = (V, E)) from queries of the form ((5, T) == ((,, v) E E : u E S, E T] for subsets S, C V. [35, 36, 37, 38). There are also algorithms that perform certain tasks more efficiently than learning the whole graph (sometimes using different types of queries) [39, 40, 41, 42, 43, 44, 45, 46), and quantum algorithms that use fewer queries than classical algorithms [47].
is not too difficult to show that an algorithm making On log k) queries (Appendix H) is possible for k-clustering, while I(n) queries is an obvious information theoretic lower bound since each query returns log k bits of information and the number of possible k-clusterings is k" = 2n lug k In fact, it possible to have an algorithm with (n) query complexity (personal communication, Chakrabarty and Liao). However, both of these algorithms are adaptive, ruling them out for the non-adaptive setting. So far, the non- adaptive setting of this problem remained unexplored.
1.1 Results
Our main results showcase the significant strength of using subset queries in the non-adaptive setting. We give randomized algorithms that recover the exact clustering with probability ō, for any arbitrary constant 6 > 0 using only near-linear number of subset queries.
Theorem 1.1. (Theorem 2.5 simplified) There is a randomized, non-adaptive k-clustering algorithm making On log² n log k) subset queries.
For constant k this dependency can be further improved.
2

---

Theorem 1.2. (Theorem 2.2, simplified) There is randomized, non-adaptive k-clustering algorithm making (n log log n. subset queries when & is any constant.
Note that the algorithm of Theorem 1.2 works for any value k, but its dependence on this parameter is inferior to that of Theorem 1.1 (see the formal version Theorem 2.2 for the exact dependence on k). Thus, we state the theorem above for constant & to emphasize the much improved dependence on n.
Our algorithms also run in polynomial time, and generalizes to work with queries of bounded size.
Bounding query size: Another practical consideration is query size, Depending on the scenarios, and capabilities of the oracle, it may be easier to handle queries on small subsets. An extreme case is pair-wise queries (s = 2), where O(nk) pair queries are enough with adaptivity but any non-adaptive algorithm has to use 22(=²) queries even for k = 3. Since a subset query on S can be simulated by (()) pair queries, we immediately get the following theorem.
Theorem 1.3. (Corollary C.2, restated) Any non non-adaptive k-clustering algorithm that is only allowed to query subsets of size at most s must make at least Qimin( (5r n1) queries.
Theorems 1.1 and 1.2 above show that this be bypassed by allowing larger subset queries. However, some of these queries are of size (m)), and this raises the question, is there a near-linear non-adaptive algorithmm which only queries subsets of size at most O(vn)? We answer this in the affirmative, implying that our lower bound is tight in terms of s.
Theorem 1.4 (Theorem A.I, informal). There is non non-adaptive k-clustering algoritim making O n log log n) subset queries of size at most ((vr) when is is any constant. For all sufficiently small s ol / /n), the algorithm makes 0 n²
gz log n)) subset queries of size most
The result also extends arbitrary k with slightly worse dependency on (Theorem 2.5). Our algorithm for bounded queries from Theorem 1.4 has the additional desirable property of being sample-based meaning that each of its queries a set formed by independent, uniform samples. L.e the algorithm specifies query size t S s. and then receives (S. (55) where S is formed by t i.i.d. uniform samples from U. Being sample-baser each query up to the individual answering the query. The algorithm needs only to specify the query sizes, and then recover the clustering once the queries have been curated and answered.
enables the algorithm to leave the task of curating
The "roughly balanced" case: Next, we consider the natural special case of recovering a k-clustering when the cluster sizes are within a constant factor of one another. Informally, let call such clustering "roughly balanced".
Theorem 1.5 (Theorems B.1 and E.1, informal). There are non-adaptive algorithms for recovering roughly balanced k-clustering which make (a) On log k) subset queries when k S O log ) and (b) (n log" k) subset queries for any k S n.
n
Allowing two rounds of adaptivity Finally, we show if we allow an extra round of adaptivity, then that helps to improve the dependency on the logarithmic factors further. Specifically, we prove the following theorems.
Theorem 1.6 (Theorems F.1 and F.3, informal). There is 2-round deterministic k-clustering algorithu making On log k) subset queries. There is randomized 2-round algorithm for recovering a roughly-balancee k-clustering making (n log log k) subset queries.
The remainder of the paper is organized as follows. In Section 2, we give our main results developing non-adaptive algorithms with linear query complexity Theorems 1.1 and 1.2. Our results for sample-basee our results for the balanced setting in Appendix B, our lower bounds in Appendix C, and our results for two-round algorithms in Appendix F.
Organization:
bounded query algorithms are given in Appendix A. Finally, we prove
2 Algorithms with Nearly Linear Query Complexity
In this section we describe the algorithms behind our main results, Theorems 1.1 and 1.2, and give formal proofs of their correctness. In Section 2.1 we describe an algorithm making O(n log log n) subset queries when the number of clusters & is assumed to be constant. In general, the dependence on the number of clusters O(k log k). In Section 2.2, we give an alternative algorithm with (m)) query complexity for any k < n.
3

---

2.1
An On log logg)) Algorithm for Constant k
Warm Up. When there are only 2 clusters, there is a trivial non-adaptive algorithm making (n)) pair queries: Choose an arbitrary x E U and query {a, y) for every y E U. The set of points y where q( (2. y}) = 1 form one cluster, and the second cluster is the complement. If we allow one more round of adaptivity, then for 3-clustering we could repeat this one more time and again get an (n)) query algorithm. However, for non-adaptive 3-clustering it is impossible to do better than the trivial (n=²) algorithm (see Theorem C.I). Essentially, this is because in order to distinguish the clusterings (12), {u), U \ {z, v}) and (f2,y) 0, U \ {z, 3}) the algorithm must query {I, y and their are (2) ways to hide this pair. Overcoming this barrier using subset queries require significant new ideas.
Our main ideas are best communicated by focusing on the case of 3-clustering. It suffices to correctly reconstruct the two largest clusters, since the third cluster is just the complement of their union. Let A, B denote the largest, and second largest clusters, respectively. Since [A] 2 n//3, it is easy to find: sample random x E U and query {x, y for every y U. The cluster containing is precisely {y E U: (({z,)) y)) = 1}. With probability at least 1/3, we have x E A and so repeating this a constant number of times will always recover A. On the other hand, B may be arbitrarily small and in this case the procedure clearly fails to recover it. The first observation is that once we know A, can exploit larger subset queries to explore U \ A since g5 \ A) = (S)) 1(S O A # 0). Importantly, the algorithm is non-adaptive and so the choice of S cannot depend on A, but we are still able exploit this trick with the following two strategies. Let En |B] denote the size of B and note that this implies |A| 2 (1 26)n since the third cluster is of size at most B.
Strategy 1: Suppose query S contains exactly one point outside of A, i... S A\A= {x} Then, for y E A, g(S U {w)) = (SS iff x, y belong to the same cluster. Thus, we can query S U (リ) for every y E U to learn the cluster containing x. If S is a random set of size t z 1/6. then the probability I2().. Of course, we do not know 6, but we can try t = 2" for every p S log n and one of these choices will be within a factor of 2 from 1/6. This gives us O(n n.) query algorithm since we make n queries per iteration.
that [S \ A| = 1 is at least t- 5. (1 28)
Strategy 2: Suppose S intersects A and contains exactly two points outside of A, i.e. S\A fxr y). Then, (((,, v)) = (SS) - 1 which tells us whether or not æ. y belong to the same cluster. x, y belong to same cluster, add it to a set E, and let G(U \ A, E)) denote a graph on the remaining points with this set of edges. By transitivity, a connected component in this graph corresponds to subset of one of the remaining two clusters. In particular, if the induced subgraph, G[B). is connected, then recover B. Morcover, S is a random set of size Rs 1/5, then the probability that two points land in B and the rest land in is at least (6) 82. -8) (1 - 28) f- = +2((). A basic fact from random graph theory says that after = [B] In [B| S ôn In n occurrences of this, G[B] becomes connected with high probability and so querying Q 6n In n.) random S of size = 1/8 will suffice. Again, we try = 2 for every p S log n, resulting in a total of & n nnnn Ep 2-P = O log n) queries.
Finally, we can combine strategies (1) and (2) as follows to obtain our O(n log log n) query algorithm. The main observation is that the query complexity of strategy (2) improves greatly if we assume that [B] is small enough. If we know that 6 S log n then we only need to try = 2D 2 log n and so the query complexity becomes 22 n In > 2p lognn 2n p = O(n). On the other hand, if we assume that > Jog n then in strategy (1) we only need to try p S log log n yielding a total of O(n log log n) queries. Combining these yields the final algorithm.
Remark 2.1 (On approximate clustering). We point out that these ideas can be used to obtain more efficient algorithms for the easier task of correctly clustering a (1 - a))-raction of points. In this setting can ignore the case of 8 < a/2 (recall the definition of 5 above) as this will only result in an incorrect classification of an a-fraction of points. Thus, for example, one can employ "strategy I" above, but only iterate over p S 1og((2/)), 22)) leading an O(n log _ query algorithm. However, in this paper we focus on the more challenging lask of recovering the clustering exactly, and leave the possibility of more efficient approximate algorithms as a possible direction of future work.
Algorithm. A full description of the algorithm is given in pseudocode Alg. 1, which is split into two phases: a "query selection phase", which describes how queries are chosen by the algorithm, and a "reconstruction phase" which describes how the algorithm uses the query responses to determine the clustering. Both phases contain a for-loop iterating over all p E {0, I,..,.., log n) where the goal

---

of the algorithm during the p' 'hth iteration is to learn all remaining clusters of size at least 24-2" This accomplished by two different strategies depending on whether p is small or large.
When & log log n, the algorithm samples O(k log k) random sets T formed by 2" samples from U and makes query T and T {x} for every U (see lines 5-9 of Alg. 1). Let R2 be the union of all clusters reconstructed before phase (i.e., clusters of size at least Ek-2r-T) ). If such a I contains exactly one point 2 E ''' R belonging an unrecovered cluster, then we can use these queries to learn the cluster containing = (see lines 24-28 of Alg. 1), since for Z E U Ry g(T) q(T U {z}) if and only if æ, belong to the same cluster. Moreover, we show that this occurs with probability (11) and repeat this Ok log k) times to ensure that every cluster C' where |C] [ 2F-2F 24-2* is learned with high probability. The total number of queries made during iterations p I log log is O log log n k loog k).
When > log log n, the algorithm queries Onnk- from U (see lines 11-14 of Alg. 1). Note that Σ of queries made during these iterations is (nk)..
random sets T again formed by 2 samples ppllog logn P ( 1 and so the total number log
log 2D
We now describe the reconstruction phase (see lines 32-37 of Alg. 1). If contains exactly two points x. E T Ry belonging to unrecovered clusters, then we can use the fact that we already know the clustering on R. tell whether not F., y belong the same cluster or not, i.e. we can compute q( (z; y}) E (1, 2} from (7)) We then consider the set of all such pairs where q( (xr y)) = 1 (this is 0% defined in line 34) and consider the graph G with this edge set, and vertex set U \ Ry, the set of points whose cluster hasn't It yet been determined. If two points belong to the same connected component in this graph, then they belong to the same cluster. Thus, the analysis for this iteration boils down to showing that with high probability, the induced subgraph G[C*] will be connected for every where |C| 2k-2F= 2k-29-1 This is accomplished by applying basic fact from the theory of random graphs, namely Fact 2.4.
Analysis We restate the main theorem for this section.
Theorem 2.2. There is a non-adaptive algorithm for k-clustering that uses (n log log log k) subset queries and succeeds with probability at least 1 for any constant > 0'.
The following Lemma 2.3 establishes that after the first p iterations of the algorithm's 's query selection and reconstruction phases, all clusters of size at least 24-2F have been learned with high probability. This is the main technical component of the proof. After stating the lemma we show it easily implies that Alg. succeeds with probability at least 10000 by appropriate union bound. The choice of 99/100 is arbitrary, and can be made 1 - ö for any constant 6.
Lemma 2.3. For each p = 0, 1,..... log n, let E, denote the event that all clusters of size at least n have been successfully recovered immediately following iteration of Alg. 1. Then, 2h.27
1 and Pr|-Ep Ep-1)
1
Pri-Cu] 100k
100k for all p ( logn).
Proof of Theorem 2.2: Before proving Lemma 2.3, we first observe that it immediately implies
the correctness of Alg. and thus proves Theorem 2.2. Let To (2x n] and for 1 p < log n. let Ip 28.2" 22-20-1): ). If there are no clusters C' for which |C| E Ip. then trivially Pr|-Ep Ep-1]
n
ToDE by the lemma. Since there are & clusters, clearly there are at most A values of p for which there exists cluster with size in the interval 4p. Using this observation
and otherwise Pr Ey-1] S I
and a union bound, we have
log
1
Pr[ Pr(-Eiogn| I Pr[-Ea]+ +
18 <
100
p=1 which completes the proof of correctness since the algorithm succeeds iff Eiog n occurs.
Query complexity:
During iterations p < log log the algorithm makes at most O(n log log
l log k) queries. During iterations > log log n, it makes at most Onk log n) Σ Ep>log log 2-P =
Onnk) queries since k < n.
For simplicity of exposition, we use a constant ò in our proofs. The success probability can be boosted to any 1 polyinj by paying log factor in the query complexity in all algorithms.
5

---

Time complexity: We assume that obtaining uniform random sample from set of size n can be done in (1) time. Thus, since the algorithm makes O(n log logn n k log kt) queries and each is on set of size at most the total runtime of the query selection phase (lines 3-15) is bounded by O(n log log k log k). We now account for the runtime the reconstruction phase. Lines (25-28) clearly can be performed in O(n) time and so the time spent in lines (24-28) is O(1Qpl n).. Now, for T E Qp. checking if [T') \ Rpl = 2 can clearly be done in (n) time and so lines (33-34) run in time p - -2). Line (36) amounts to finding every connected component in Gp which can be done in time O(1 + n = Ol12p + n) by iteratively running a BFS (costing time linear in the number of edges plus the number of vertices). Thus, the runtime of the p th iteration of the for-loop is always dominated by 0(12p1 n). Since the total number of queries is On log log n k log k). the total runtime of the reconstruction phase (n log log n log k)) We now prove the main Lemma 2.3.
Proof- of Lemma 2.3. Let Cp denote the set of clusters recovered before phase p and let R. Ucec, C. When p 0, both of these sets are empty. We will consider three cases depending on the value of p.
Case 1: p 0. Let C' denote some cluster of size CI 2 2t- Note that in this iteration the sets T sampled by the algorithm in line (7) are singletons. We need to argue that one these singletons will land in C, and thus C is recovered in line (28), with probability at least 1 100RZ Since there at most clusters, applying a union bound completes the proof in this case.
A uniform random element lands in C' with probability at least 1 and so this fails to occur for all 2X
IQul 2 4k In 10k samples with probability most (1 claimed.
) 4k In 10k I exp(-2 In 10k) 10082 as
2k
Case 2: S & log log Let C denote some cluster with size |C E 2F.2F 26:2--1 ) Note that we are conditioning on the event that every cluster of size 2 26-20-r has already been successfully recovered after iteration
1. Thus, the number of elements belonging to unrecovered clusters is R. We need to argue that the set Qp will contain some T' sampled line
IU V R S k (7) such that T Rp
2 27
{2} where C, and thus C' is successfully recovered in line (28), with Once this is established, the lemma again follows by union bound.
probability at least 1 100k
We have
Pr [ = and RR S C = |T]- | |Cl ( [Ryl
[T|-1
2F
2
2
T:
k:
20+1
2F
2ek
and so the probability that this occurs for some T E Qp is at least 1 as claimed.
jek In 10k
Zek
1006
Case 3: p > log log n. Let C' denote some cluster with size |C| E 2F-2F 2-)) Note that Recall from lines (34-35) the definition of O2 and recall that Gp is the graph with vertex set U R. and edge set Q" We need argue that the induced subgraph G,IC] is connected, and thus C' is successfully recovered in lines (36-37), with probability least 1 T0DK Once this is established, the lemma again follows by union bound. We rely the following standard fact from the theory of random graphs. For completeness, we give a proof in Appendix D.2.
IU \ Rpl < k 24-2
Fact 2.4. Let G(N.p) .) denote an Erdös Erdös-Rényí Rényi random graph. That is, the graph contains N vertices and there is an edge between each pair of vertices with probability p. If p 2 - (8/3N)2 G(N,p) p) is connected with probability least 1 8.
2/N then
Consider any E C. and observe that
(P))
2
22p
1
2
22p
Pr T Rp = [x. 2F
1
>
2
n²
3n2
2p
10n2*

---

Algorithm I: Non-adaptive Algorithm for Constant k
Input: Subset query access to a hidden partition C₁ U....L L. C of [0] = n points;
(Query Selection Phase) 3 for p = 0, 1,.,,, log do
Initialize 2 0;
pf' S. log log then
Repeat 4ek (10kk) times;
Sample T' C formed by 2" independent uniform samples from U:
Query T and T {x} for all EU;
Add T to Op:
end 10
ify p >
log log then
Repeat 40nk (3000kk))) times;
12
2p Sample 7 C U formed by 2" independent uniform samples from U;
13
14
Query I and add it to Qpi
end
16 end
17 (Reconstruction Phase)
Initialize learned cluster set Co 0;
19
for p = 0, I...., log n do
Let C, denote the collection of clusters reconstructed before iteration p;
21
Let R2 = UcEE, C denote the points belonging to these clusters;
22
Initialize Cp+1 Cp: p S log log then for T' Qp do
23
24
25
[T' Rp = 1 Let denote the unique point in T') RR;
then
If E U \ Rp. then (T) = qT {x+) iff x. 2 are in the same cluster;
27
Thus, add {i U (TT) qT {x))) to Cp+1i
29
end
30
end
31
end
if p > loglog then
33
Let 2 = (T) Ry: 7 E Qn and [T)) R
= 2}. Since each T E Qp is a uniform
random set, the elements of Q are uniform random pairs in U \ Ry:
34
Let 02 [(x v} E Op: q( {z. y} = 1)} denote the set of pairs in Ø where both points lie in the same cluster. This set can be computed since q(T) \ R2,) (()) (T n R.,) and ( n R.,)) is known since at this point have reconstructed the clustering on Ry: Let Go denote the graph with vertex set U RS and edge set 0";
35
36
Let Ci,...,
.....,,o Cp denote the connected components of G with size at least 26-2
37
Add CI,..., Ce to Cp+1:
38
end
end
40 Output clustering Clogn+1

---

Recall that the algorithm queries [Qpl
40-nk (3000kk
random sets 7 of size 2". Thus,
2F
Pr
Pr[(x,))
E[Gp|C]]
Pr [[z, y)
Q71
Pr
Op: T R fa.yHl
4p
22
O
2
40 A In(300nk²)
2 1
10m²
2P
2 1 exp
4k In(300nk2))
n
and using |C| 2
n and |C| S n, we obtain 2F-2
2 ln(300mk
Pr((a,y) E E(G,[C]) 2 exp 4p
ICI
2 In(00k CT)
2 1 exp
=1
|C'
300
Thus, (z, y) is edge in Gp[C] with probability at least 1 connected with probability at least 1ook2, claimed.
and by Fact 2.4 Gp.C]
300k
n
Bounded Query Size We can restrict the query size
Vr, and still achieve near-linear
query complexity. We sketch the main ideas here for the case of k: = 3 similar to the "warm-up" in Section 2.1. Details are provided in Appendix A. Our Theorem 1.4 gives O(n log log n) query non-adaptive sample-based algorithm using subset queries of size at most (vyn). The main idea is employ "Strategy 2" described in the warm-up section of Section 2.1 with slight alteration. Let A, B denote the largest, and second largest clusters, respectively, where |B| = on and so ||| 2 (1 28)n. Observe that if we take a random set S of size ~ v1/5. then the probability that two points land in B and the rest land in A is at least (6) 62 (1- 20) 2(6). Recalling the definition of the graph G and the discussion in Section 2.1, after querying Ω(n In)) such S, the induced subgraph GB becomes connected with high probability, thus recovering the clustering. Similar ideas let us generaize to any 8, and achieve an optimal dependency on as stated Corollary C.2 for constant
2.2 An (n log" n log k) Algorithm for General k:
We now consider the situation with general k. for which our algorithm and analysis follow completely different approach by using techniques from combinatorial group testing.
Warm up.
The main subroutine in our algorithm is procedure for recovering the support of Boolean vector via OR queries. Given a vector u E {0. 1)",, , an OR query on a set S S [n] returns OR₂(u) = Vic ies U; i.e. it returns 1 iff has 1-valued coordinate in S. The problem of recovering the support of v, supp(v) and coin-weighine weighing literature. The relevance of this problem for k-clustering with subset queries is as follows. Consider hidden clustering C1 ... L C2 U. Given æ E U. let C(x) denote the cluster containing U {z ... } (an arbitrary ordering of U), and let ((()) E {0, 1)" denote the Boolean vector where vi
{i: u, 1} via OR queries is basic problem from the group testing
(z) 1(x, C(x)). An OR query set S to g(*) can be simulated by subset query to the clustering on sets S and S U {o} since
ORs(v(*)
V o (x)
1(C(z) ns ns + 0) = 1(g q(S)).
#E
Thus, the problem reconstructing C(x) via subset queries is equivalent to the problem of recovering g((*) via OR queries, up factor of 2 in the query complexity.
Then, to learn cluster C with size 2F of which lands in C' with high probability) and then recover C(xx) using 0 log " OR queries. Iterating over every p S log and boosting the number of samples to guarantee a high probability of success for all & clusters yields our algorithm.
a < |C| < - suffices to sample ((2P) random x (one
8

---

This algorithm can also be restricted to only make subset queries of size at most and the query complexity scales with a.
Theorem 2.5. For every 8 E n2, there is a non-adaptive k-clustering algorithm making O(nlog log (" + s)) subset queries of size at most s. In particular, for unbounded query size the algorithm makes On log" log k) queries.
Proof of Theorem 2.5 We will use the following lemma for recovering supp(v) {i: v 1 via OR queries. We prove and discuss this lemma in Appendix D.1 (see Lemma D.5).
Lemma 2.6. Let {0, 1 and s, 2 be positive integers where S 7. There is non-adaptive algorithm that makes O log ) OR queries on subsets of size s, and if (supp(u)] S t, returns supp(e) with probability 6, and otherwise certifies that [supp(u)] > t. The algorithm runs in time (n log? 15)
Recall that ( = (S (x}) = q(S)), ( i.e. an OR query on S is simulated by subset queries on sets S and SU (z). Thus, we immediately get the following corollary.
Corollary 2.7. Let I E U and r 2 2, 2 be positive integers where r S 7. There is a non- adaptive algorithm that makes O log 7 subset-queries on sets of size al most r, and if C(x) S I, returns (xx) with probability 6, and otherwise certifies that [C(x)] > L. The algorithm runs in time (n log )-
Algorithm The pseudocode for the algorithm given in Alg. 2. The idea is to draw random points U (line 5) and then use the procedure from Corollary 2.7 subroutine try to learn C(x) (line 6). By the corollary, this will succeed with high probability in recovering C(z) as long as f is set to something larger than C(x)]. Note that the query complexity of this subroutine depends on t. If cluster C is small, then Pr[w E CJ is small, but we can call the subroutine with small 4, while if C(x) large, then Pr(x E CJ is reasonably large, though we will need to call the subroutine with larger l. Concretely, the algorithm iterates over every P E (1,...,log, log n (line 3), and in iteration the goal is to learn every cluster C with C E 2P:
12 2P-T). To accomplish this, we sample O log k) random points x E U (line 4-5) and for each one, call the subroutine with f -- (line 6). which is an upper bound on the sizes of the clusters we are trying to learn.Nott that always invoke the corollary with query size min(s, 2 < 8, enforcing the query size bounded stated in Theorem 2.5.
Algorithm 2: Non-adaptive Algorithm for General k
Input: Subset query access to hidden partition C₁ L...... C2 = U of [0] n points;
2 Initialize hypothesis clustering + 0:
for p 1, .., log do
Repeat 2" (200k) times:
Sample U uniformly at random;
Run the procedure from Corollary 2.7 with I query-size r min(s, 2 and error probability 8
2008 This outputs C(x), the cluster containing x, with
probability at least - 8 if [zx) < t;
7
If the procedure returns a set C, then set + CU (C). Otherwise, continue;
8 end
Output the clustering C.
Query complexity:
Note that the number of queries made in line (6) during the p'th iteration is
O log when 20-1 2 8, and O n logn) when 2 < s. Therefore, the total number of queries made is most
Zp
Ollog k)
n 0(2
logn) n) +
Σ
n 0(2
log nogn]
2p
s
4522--111 15n
The first sum is bounded by (n log n log s) and the second sum is bounded by O(" logn). The time-complexity clearly identical by Corollary 2.7.
For intuition, if the subroutine is called with f. then Corollary 2.7 makes O(t #) queries.

---

Time complexity: We assume that attaining a uniform sample from a set of size n can be performed in (1) time. The procedure line (6) has rumtime at most (n log n) since we å (.)) Thus, the total runtime of the algorithm is (n log n log k) Ep n
2 On? log n log k))
Correctness:
Consider any cluster C' and let E {-..... log n be such that 3 E |C| 1 n
Let &c denote the event that some element E C is sampled in line (5) during iteration p. Let Re denote the event that C' E C when the algorithm terminates. Observe that by Corollary 2.7, Moreover, using our lower bound C' we have
Pr[Re Ec] 2 1 - d
1
200k
(1-19) ICI)
2" In 200k
2" In 2008
1
Pr|-Ecl =
n
200k
Thus, Pr[-Rc] S
Pr(-Eq + Pr[-RR [c] S
1ook and taking another union bound over all
clusters completes the proof.
Acknowledgements. Hadley Black, Arya Mazumdar, and Barna Saha were supported by NSF TRIPODS Institute grant 2217058 (EnCORE) and NSF 2133484. Euiwoong Lee also supported in part by NSF grant 2236669 and Google. The collaboration is the result of an EnCORE Institute Workshop.
10

---

References
[1] David Cohn, Rich Caruana, and Andrew McCallum. Semi-supervised clustering with user feedback. Constrained clustering: advances in algorithms, theory, and applications, 4(1):17-32, 2003.
[2] Eric Bair. Semi-supervised clustering methods. Wiley Interdisciplinary Reviews: Computational Statistics, (99:349-361. 2013. 1
[3] Maria-Florina Balcan and Avrim Blum. Clustering with interactive feedback. In International Conference on Algorithmic Learning Theory, pages 316-328 Springer, 2008. 1
[4] Arya Mazumdar and Barna Saha. theoretical analysis of first heuristics of crowdsourced entity resolution. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
[5] Arya Mazumdar and Barna Saha. Clustering with noisy queries. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors, Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 5788-5799, 2017.
[6] Arya Mazumdar and Barna Saha. Query complexity of clustering with side information. In Advances in Neural Information Processing Systems 30: Annual Conference Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, 2017. 2
[7] Michael Mitzenmacher and Charalampos E Tsourakakis. Predicting signed edges with onn +o()) log n) queries. arXiv preprint arXiv: 2016. 2
[8] Hassan Ashtiani, Shrinu Kushagra, and Shai Ben-David. Clustering with same-cluster queries. Advances in neural information processing systems, 29, 2016. 2
[9] Arya Mazumdar and Soumyabrata Pal. Semisupervised clustering, and-queries and locally encodable source coding. Advances in Neural Information Processing Systems, 30, 2017. 2
[10] Barna Saha and Sanjay Subramanian. Correlation clustering with same-cluster queries bounded by optimal cost. In 27th Annual European Symposiun on Algorithms (ESA 2019). Schloss- Dagstuhl-Leibniz Zentrum für Informatik, 2019. 2
[11] Alberto Del Pia, Mingchen Ma, and Christos Tzamos. Clustering with queries under semi- random noise. In Conference Learning Theory, pages 5278-5313, PMLR, 2022. 2
[12] Marco Bressan, Nicolò Cesa-Bianchi, Silvio Lattanzi, and Andrea Paudice. Exact recovery of mangled clusters with same-cluster queries. Advances in Neural Information Processing Systems, 33:9324 93344,9933,25 2020.
[13] Wasim Huleihel, Arya Mazumdar, Muriel Médard, and Soumyabrata Pal. Same-cluster querying for overlapping clusters. Advances in Neural Information Processing Systems, 32, 2019. 2
[14] Ramya Korlakai Vinayak and Babak Hassibi. Crowdsourced clustering: Querying edges vs triangles. Advances in Neural Information Processing Systems, 29, 2016.
[15] Nikhil Bansal, Avrim Blum, and Shuchi Chawla. Correlation clustering. Machine learning, 56(1):89-113, 2004. 2
[16] Nir Ailon, Moses Charikar, and Alantha Newman. Aggregating inconsistent information: Ranking and clustering. Journal of the ACM, 55(5):1-27, 2008. 2
[17] Shuchi Chawla, Konstantin Makarychev, Tselil Schramm, and Grigory Yaroslavtsev. Near optimal LP rounding algorithm for correlation clustering on complete and complete k-partite graphs. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC), pages 219 219-228, 2015. 2

---

[18] Nairen Cao, Vincent Understanding the cluster ip for correlation clustering. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC), 2024.
Euiwoong Lee, Shi Li, Alantha Newman, and Lukas Vogl.
[19] Jure Leskovec, Daniel Huttenlocher, and Jon Kleinberg. Predicting positive and negative links online social networks. In Proceedings of the 19th international conference on World wide web, pages 641-650, 2010. 2
[20] Emmanuel Abbe. Community detection and stochastic block models: recent developments. Journal of Machine Learning Research, 18(177):1-86, 2018.
[21] Chandra Sekhar Mukherjee, Pan Peng, and Jiapeng Zhang. Recovering unbalanced communities in the stochastic block model with application clustering with faulty oracle. Advances in Neural Information Processing Systems, 36, 2024. 2
[22] Quanquan Gu and Jiawei Han. Towards active learning on graphs: An error bound minimization approach. In 2012 IEEE 12th International Conference on Data Mining, pages 882-887. IEEE, 2012.
[23] Martin Aigner. Combinatorial search. John Wiley & Sonn, Inc., 1988. 2
[24] Dingzhu Du and Frank K Hwang. Combinatorial group testing and its applications. World Scientific, 12, 2000. 2
[25] Dingzhu Du, Frank K Hwang, and Frank Hwang. Combinatorial group testing and its applica- tions, volume 12. World Scientific, 2000. 2
[26] F. Hwang and V. Sós. Non-adaptive hypergeometrie group testing. Studia Sci. Math. Hungar, 1987. 2, 19
[27] Arya Mazumdar. Nonadaptive group testing with random set of defectives. IEEE Transactions on Information Theory, (2(12)7552-7551, 2016. 2
[28] Ely Porat and Amir Rothschild. Explicit non-adaptive combinatorial group testing schemes. In Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Lecture Notes in Computer Science, 2008. 2, 19
[29] Bernt Lindström. On a combinatory detection problem A Magyar Tudonányos Akadémia Matematikai Kutató Intézetének Közleményei, 91122):155-077, 1964. 2
[30] Bernt Lindström. On a combinatory detection problem. ii. Studia Sci. Math. Hungar, 1:353-361, 1966. 2
[31] David G Cantor and WH Mills. Determination of a subset from certain combinatorial properties. Canadian Journal of Mathematics, 18:42-48, 1966. 2
[32] Nader Bshouty. Optimal algorithms for the coin weighing problem with a spring scale. In COLT, volume 2009, page 82, 2009. 2
[33] Nader H. Bshouty and Hanna Mazzawi. On parity check (0, 1)-matrix over zP. In Proceedings, ACM-SIAM Symposium on Discrete Algorithms (SODA), 2011. 2
[34] Nader H. Bshouty and Hanna Mazzawi. Algorithms for the coin weighing problems with the presence of noise. Electron. Colloquium Comput. Complex., TR11-124, 2011. 2
[35] Dana Angluin and Jiang Chen. Learning a hidden graph using o(log n) queries per edge. 2004.
2
[36] Sung-Soon Choi and Jeong Han Kim. Optimal query complexity bounds for finding graphs. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 749-758. 2008. 2
[37] Hanna Mazzawi. Optimally reconstructing weighted graphs using queries. In Proceedings of the Twenty-Fing First Annual ACM-SIAM Symposium on Discrete Algorithms, pages 608-615 SIAM. 2010. 2
12

---

[38] Sung-Soon Choi. Polynomial time optimal query algorithms for finding graphs with arbitrary real weights. In Conference on Learning Theory, pages 797-818. PMLR, 2013. 2
[39] Aviad Rubinstein, Tselil Schramm, and Matthew Weinberg. Computing exact minimum cuts without knowing the graph. arXiv preprint arXiv:1711.03165. 2017.
[40] Sagnik Mukhopadhyay and Danupon Nanongkai. Weighted min-cut: sequential, cut-query, and streaming algorithms. In Proceedings, ACM Symposium on Theory of Computing (STOC), 2020.
2
[41] Sepehr Assadi, Deeparnab Chakrabarty, and Sanjeev Khanna. Graph connectivity and single element recovery via linear and or queries. In 29th Annual European Symposium on Algorithms (ESA 2021). Diihoss-Dasttuhh-Liibiizzz Zentrum für Informatik, 2021. 2
[42] Simon Apers, Yuval Efron, Pawel Gawrychowski, Troy Lee, Sagnik Mukhopadhyay, and Danupon Nanongkai. Cut query algorithms with star contraction. In Proceedings, IEEE Symposium on Foundations of Computer Science (FOCS), 2022.
[43] Hang Liao and Deeparnab Chakrabarty. Learning spanning forests optimally in weighted undirected graphs with cut queries. In International Conference on Algorithmic Learning Theory, pages 785-807. PMLR, 2024.
[44] Paul Beame, Sariel Har-Peled, Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian, and Makrand Sinha. Edge estimation with independent oracles. ACM Trans. Algorithms, 1 16(4):52:1-52:27, 2020.
[45] Xi Chen, Amit Levi, and Erik Waingarten. Nearly optimal edge estimation with independent set queries. In Shuchi Chawla, editor, Proceedings, ACM-SIAM Symposium on Discrete Algorithms (SODA), 2020. 2
[46] Raghavendra Addanki, Andrew McGregor, and Cameron Musco. Non-adaptive edge counting and sampling via bipartite independent set queries. In Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, and Grzegorz Herman, editors, 30th Annual European Symposium Algorithmss ESA 2022, September 5-9, 2022, Berlin/Potsdam, Germany, volume 244 of LIPlcs, pages 2:1-2:16. Schloss Dagstuhl- Leibniz-Zentruu für Informatik, 2022. 2
[47] Troy Lee, Miklos Santha, and Shengyu Zhang. Quantum algorithms for graph problems with cut queries. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 939-958. SIAM, 2021.
[48] Sepehr Assadi, Deeparnab Chakrabarty, and Sanjeev Khanna. Graph connectivity and single element recovery via linear and OR queries. In Petra Mutzel, Rasmus Pagh, and Grzegorz Herman, editors, 29th Annual European Symposium on Algorithms, ESA 2021, September 6-8, 2021, Lisbon, Portugal (Virtual Conference), volume 204 of LIPIcs, pages 7:1-7:19. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2021.
[49] Vladimir Grebinski and Gregory Kucherov. Optimal reconstruction graphs under the additive model. Algorithmica, 28(1): 104 124, 2000. 24
13

---

A Bounded Query Size and Sample-Based Algorithms
In this section we present an algorithm using subset queries with size bounded by s, which matches the lower bound of Theorem C.I, up to a log r--accor. Our algorithm has the additional desirable property of being comple-basede meaning that the subsets queries are formed by taking uniform cample-base
independent samples. In addition to Theorem A. we also obtain a non-adaptive algorithm using O(nk log n) unbounded queries in Theorem G.I, using a similar approach. We also show a lower bound of S2(n log n) for any k 2 2 in Appendix C.2 for sample-based algorithms, showing that the dependence on n is optimal for this special class of algorithms.
Theorem A.I. There are non-adaptive, sample-based k-clustering algorithms making (a) (nk log n log log n. subsel queries of size at most (V))), and (b) ( (5rr log n) subset queries of size at most & = n 1/2- for any constant ā E (0. 1/2). Each algorithm is correct with probability at least 99/100.
For convenience, we will parameterize the query-size bound by = n//r where is any positive real number in the range 2 S r S. log n. Before proving the theorem formally, we informally describe the algorithm and its analysis. A full description of the algorithm is given in pseudocode in Alg. 3. which is split into two phases: a "query selection phase", describing how queries are chosen by the algorithm, and a "reconstruction phase". describing how the algorithm uses the query responses to determine the clustering. Both phases contain for-loop iterating over all E {0, I,... log, log - 1} where the goal of the algorithm during the p' 'tt iteration is to learn all remaining clusters of size at least E. 2 2-r We prove that this occurs with high probability in Lemma 2.3, which gives the main analysis. If each iteration successful in doing so than the entire clustering has been learned successfully after iteration p log, log n - 1 (since 2 -plo,. = 2 log n formally just after the statement of Lemma A.2.
) and we justify this
We describe the algorithm and it's analysis informally for the case of r = 2, i.e. when the query sizes bounded by
/n. We also refer the reader Section 2 for discussion of the ideas for the simple case of h = 3. Consider some iteration p E {0, I.... log log to this iteration, all clusters of size at least h 2-2" have been successfully recovered. Let Cp denote the collection of all such clusters and let R2 =Licec,
1} and suppose that prior
be the set of points they contain. The goal n -2-2+t1 n 222 2-22"). The algorithm queries [k
in iteration p to learn every cluster C with |C| E
Onk log n.) random sets T formed by 2 samples² from U (see lines 5-7 of Alg. 3). Similar the proof of Theorem 2.2, if I' contains exactly two points æ, y E T R, belonging to unrecovered clusters, then we can use the fact that we already know the clustering on R, to tell whether or not x, belong to the same cluster or not, i.e. we can compute ((22,) w}) E {1, 23 from ((T)). We then consider the set of all such pairs where q( (z. y)) = 1 (this is 0% defined in line 16) and consider the graph G with this edge set, and vertex set U \ Rp. the set of points whose cluster hasn't i's yet been determined. If two points belong to the same connected component in this graph, then they belong to the same cluster. Thus, the analysis boils down to showing that with high probability, the induced
subgraph GCC] will be connected for every C' where |C| E E - 2 -R 2P. This is accomplished by applying basic fact from the theory of random graphs, namely Fact 2.4.
Proof of Theorem A.I: The following Lemma A.2 establishes that after the first p iterations of the algorithm's 's query selection and reconstruction phases, all clusters of size at least E/- 22.2-11 2- have been learned with high probability. This is the main effort of the proof. After stating the lemma we show it casily implics that Alg. 3 succeeds with probability at least 99/100 by an appropriate union bound.
Lemma A.2. For each p- 0, I.... log, log n - 1, let Ep denote the event that all clusters of size at -- have been successfully recovered immediately following iteration p of Alg. 3. Then,
least
1 100k and Pr[-Ep E 100k
1
Prl S
for all p (1,2,... log, log 1}.
Before proving Lemma A.2, we observe that it immediately implies Theorem A. as follows. Let Io 2 n| and for 1 < p log, log n, let 1p = .2- p+1
2 --)"). If there are clusters
NNte that p S log log n and so 2dd < 2 log
Vn.
14

---

Algorithm 3: Sample-Based Algorithm Using Bounded Queries
Input: Subset query access to hidden partition C1 L.... C+ of |0| n points;
(Query Selection Phase)
3 for p = 0, i,....,.oo... log, log do Initialize query set Qp f- 0;
Repeat nk (3000kk2²) 2 (1- times;
Sample T - U formed by 2nd independent uniform samples from U;;
Query T and add it to Qp:
end (Reconstruction Phase)
Initialize learned cluster set Co 0:
11 for p = 0, .,, log, log - do
Let C, denote the collection of clusters reconstructed before iteration pt
13
Let Ry = Ucec, C denote the points belonging to these clusters;
Initialize Cp+1 t Cy:
15
Let 2 = {T') Ry:Te T' Q2 and IT' Rpl 2}. Since each I' E Qp is a uniform random set, the elements of 2, are uniform random pairs in U Ry:
16
Let O" = H( y) E 2 q((,, y = })} denote the set of pairs in Q2 where both points lie in the same cluster. This set can be computed since q(T") \ Rp) g(T) q n R,)) and
q(T n R,)) is known since at this point we have reconstructed the clustering on Ryi Let Gp denote the graph with vertex set U Rp and edge set 0";
17
Let C1 ..,....C.. C2 denote the connected components Gp with size at least -2 2-r
18
19
Add CI,..., Ce to Cp+1:
end
21
Output clustering Clog, logni
for which |C] I.- then trivially Pr[-Ep Ep-1]= O, and otherwise &r 1
Took by
the lemma. Since there are clusters, clearly there are at most i values of p for which there exists cluster with size in the interval Lp. Using this observation and union bound, we have
log,, Ing
Pr[- log n- - S Pr(-Eo] +
Σ
Pr[-Ep Ep-11 - 100
which completes the proof of correctness since the algorithm succeeds iff Elog, logn-1 occurs.
Query complexity: Note that the total number of queries made Onk log n) Elog, log n (1-
When the summation evaluates log log n which establishes the query complexity item (a) of Theorem A.1.
Otherwise, let r 2 C' for some constant C > O. We will argue that (1 #) _ 12 #) for any S log, log greater than some constant and thus the summation bounded as
log, log
21 2) 0(2 lorr log " (1- R))
establishing the query complexity in item (b) of Theorem A.1. Observe that (1- 12 (1-=)( equivalent rP(1 2) < p+1
1, or equivalently
1
pp- ()(r 2)
C(1 C(1+C)
which clearly holds as long
log J since >>> 2.
Time complexity: assume that sampling a uniform random element from set of size n can be done in (()) time. Thus any set that is sampled during the course of the algorithm can be constructed
15

---

in ((s), time. No matter the value of s, the number of queries made by the algorithm is dominated
by O " klog n log log n). Thus, the runtime of the query selection phase (lines 3-7) bounded by O k Kloo n log log n). Now for the reconstruction phase. In line (15), |T') \ Rpl can be computed in O(n) time and so lines (15-16) take time O[10p1 n2. Line (18) amounts to finding every connected component in Gp which can be done in time (( + n) = O + n)) by iteratively running a BFS (costing time linear in the number of edges plus the number of vertices). Thus, the runtime of the p th iteration of the for-loop is always dominated by 0[12pl n2). Since the total number of queries is dominated by O ( log ri log log n),, the total runtime of the reconstruction phase (lines 11-19) is O(") 3o k log n log log n.), which dominates the runtime of the query selection phase.
0
We now prove the main Lemma A.2.
Proof. of Lemma A.2. Let R. denote the set of points belonging to cluster which has been recovered before iteration p.
Case 1: p = 0. In this iteration, the algorithm queries IQol 2 8 nk In(300nk3) 2r-2 random pairs and we need to show that it successfully recovers all clusters with size least 2-2F with probability at least 1 - 100k- Go with vertex set U and edge set Q"- We will show that the induced subgraph Go(C] is connected, and thus C is correctly recovered in lines (18-19), with prohability at least 100k Since there are at most clusters, the lemma holds by a union bound.
1 Let C' denote any such cluster and recall from lines (16-17) the definition the graph
Consider any two vertices 2, y C' and note that [Qol 2 bound the probability that (I,, y) is an edge in Go[C] follows. Note that this occurs iff {2, n) E Qo- Thus,
2n lu(300n4") since |C| 2
We lower
[C]
K-2"
Qul
Pr((a,y) E E(G][C)) Qo
Pr((., w) E Qol -1 Qo
n2
2 230000))
1 exp
10|
(- 2II(300A2IIC)
[
2 1 exep
(1)
|C|
300
and so by Fact 2.4, Gn[C] is connected with probability at least
TooK as claimed.
Case 2: < log, log Recall from lines (12-13) that Cp denotes the set of clusters recovered prior to iteration p and R,p Ucec, is the set of points belonging to these clusters. Note that we
conditioning on the event that every cluster of size least iteration p. Let C. denote some cluster with size
2-r" has been recovered prior to
CC
7 E
P+1 n T 2-2"") and note that IU \ Rpl
n 2-r" = 2222 K
K
Recall from lines (16-17 17) the definition of Q" and that G, is the graph with vertex set U \ R2 and edge set Q3 We need to argue that the induced subgraph GP is connected, and thus C is correctly recovered in lines (18-19), with probability at least Took Since there are at most k clusters, a union bound completes the proof of the lemma.
Consider any two vertices x, E C. We lower bound the probability that (x,y) y) is an edge in Gy[C], which occurs iff there is some T E Qp where T R {I, We have
(2
Rpp
22r²
3nd (1 (1- (1-2-10)
2--11²²²
22r
Pr T RS -
= [x. =
2
n
10n
16

---

and since 1ppl = 20 In(00kkk)))
2- we have
Pr [(x,,)) E F[G,|C]) 4p
Pr [<x; y) E Q
= Pr
Op: T R2
Q,
20-nk-2"t 11 -2 ln(300nk2)
22r
2 1
10n²
2nd
h kIn (3000k))
2 1 exp
and plugging in |C| 2 / 2- and |C| S n into the RHS yields
2 lm(3300kk)
Pr((x,y)= E(G)(C)) 2
exp
4
IC|
2 In(3004"|C])
2 1 - exp
= 1
|C7
300k
Therefore, (x. 3) is an edge Gp with probability at least 300k-Ic1
which by Fact 2.4
implies that Gy[C] connected with probability at least 1ook? as claimed.
B The Special Case of Balanced Clusters
Given B I, we say that a k-partition Ci...., C& B-balanced if n S |C Bn for all i [k]. In this section we prove the following theorem, which gives non-adaptive algorithm for recovering roughly balanced k-clustering making O(n log k) subset queries when k = O( ;, We give an alternative algorithm making On log* k)) queries for arbitrary in Appendix E. We also described
&
two-round algorithm for this setting making On log log k) queries in Appendix F.2.
Theorem B.1. There non-adaptive algorithm that recovers a B-balanced k-clustering using O(B"n log k) + O(Bk log" k) subset queries of size O(k log k) and succeeds with probability 49/ 49/50.
... T, each formed by k/ B samples from U and in line (5) learn the clustering over their union using Theorem 2.5. Le., for T = Ti U -.. U T., we find R, = T n Cj. Then, we query T, and T₃ U {z} for every x E U and every i [s] in line (5). Now, consider some point E U and let be it's cluster's index. Note that gT; U {x}) = ((T,) iff T; intersects Cj-. Thus, if T; does not intersect Cj+, then every cluster j that T; intersects
Pseudocode for the algorithm is given in Alg. 4. In line (3) we draw 5 = O log k) sets Ti.....
be ruled out candidate for being the cluster containing The set Ja computed in line (8) is the set of all j which can be ruled out in this way. If for every j * j", there some T; containing j. but not j then Jg = {i"} and we determine j in line (9). This occurs for every x E if the following holds: for every pair (j.J') E (2), there exists T; intersecting Cj, but not Cyr. We show in Claim B.2 that this happens with high probability.
Proof of Theorem B.1 There are O log k) queries made in line (5) and O(B-k k log k) queries in line (4), since Uiete Til = O(Bk k).
Time complexity: We assume the attaining a uniform sample from any set can be done ((1) time. Thus, constructing sets T, in line (3) costs O(Bk In k)) time and by Theorem 2.5 line (4) costs O Ba In k)). Line (5) costs O(n 8) O(B2n In k)) time. Constructing Ja in line (8) amounts to checking if (T; {x:) # (TT)) and n R2 * for each i [s] and j E [k.). This can be done in time O(TTa) [R, O(k-2 In k) simply using R2 S [R] = O In k) and [T.] k/ B. Thus,
the total runtime of lines (7-14) is dominated by (nk In k).
We now prove correctness, which is due to the following claim. Claim B.2. For E [s].] E [K). let Ex, denote the event that T, n C, # 0. Then,
Correctness:
[k]] 2
99
Pr T T.......
vG.55')
3i E [s]: En, A Es, >
(2)
100"
17

---

Algorithm 4: Algorithm for the B-Balanced Case
Input: Subset query access to a B-balanced partition C1 L.... LI U of [U] = n points;
(Query Selection Phase)
Choose 2e (n(100k²) sets Ti..... Ta each formed by Y/2 uniform samples from U;
Run the algorithm from Theorem 2.5 to learn the clustering restricted R = - 7; Let
R1..... R4 be the output of the algorithm. Le., if the algorithm is successful, then
R3 = Cj for all j [kt]:
5 Query Ti and T; U { for all i E [s] and all x E U:
(Reconstruction Phase)
for x E U do
Let Jz Ulets): (T) {j E [k]: n * 0}. Note that T. n Ri * 0 iff
T; n C2 + W. Note that Q U (=}) * (TT,) iff x does not belong to any cluster that is hit by T. Thus, Ju is the collection of all such that some set T; has revealed that & Cy: then
if J2 =
10
Add Ry where j is the unique element of [k] \ Jai
11
else
Output fail;
13
end
14
end
Output clustering (Ri...., Rk);
Proof. Firstly, for fixed E [s] and j # j', since each cluster's size is bounded in the interval Ba], we have
Pr(Es A -E,s== [ao]=Prpp Pr(Eey] Pr( EGp1
T.
C3
[T.
(1
1crl)
[T|-1
n
n
K/B
k/B
B
1 1
2 (1 -
exp
(B-2))
(B
Bk
k
e
2e
and so for fixed (j.j") (1k)
have
BeB² In(100k2)
Pr e - (E,, A EG (1- Be
1
Ti T2.... To
1006
and the claim follows by a union bound over all (j.j") (1h))
By Claim B.2, with probability least 99/100. for every j + E [k] we have some T₁ such that Ti Cj & 0 and T; Cy. = 0. In particular, for x E U. let Cj- be the cluster containing x. For every j * j have some T; such that T; nC # 0 and T, n C,-- 0 which means that in line (9) of the algorithm, we have J2 = [k] { and so we successfully identify the cluster containing Moreover, this occurs for all Finally, line (4) succeeds with probability 99/100 100 and thus the entire algorithm succeeds with probability at least 49/50 by a union bound.
C Lower Bounds
C.1 An 2 ( Lower Bound for Non-adaptive 3-Partition Recovery
((m²)
Theorem C.1. Non-adaptive 3-clustering requires 2(n?) pair queries.
Proof. For every (x, y) E ( consider the following pair of partitions:
p1 ((I,y).0. 0,U (x,v)) and P ((z), (v). (x.2)).
18

---

Observe that the oracle returns the same value for my and P on every possible query except on the set {x, v). Thus, if query set Q S U x U distinguishes these two clusterings, then Q - {z, y Therefore, the number of pairs {z, y) such that Q distinguishes P and P is at most [Q]. Now, let A be any non-adaptive pair-query algorithm which successfully recovers an arbitrary 3-clustering with probability 2 2/3. The algorithm A queries random set Q - according to some distribution, DA- particular, for every {ar, y) E (2), Q distinguishes P2, and P2 z. with probability 2 2/3. Thus.
12
Σ
Pr IQ distinguishes P2.y and p2 z.y. QuDA
3 2
(n.))(()
[[ (o..v E (o): distinguishes Paly and p2 2.0
21
= EQQ-DA
S <
using linearity of expectation, and this completes the proof.
Corollary C.2. Non-adaptive 3-clustering requires 1 subset queries of size at most
Proof. This follows from Theorem C.I since one s-sized query can be simulated by (+) pair- queries.
Thus, in order achieve near-linear non-adaptive upper bound for 3-clustering, we require an algorithm which makes queries of size (z)
C.2 An (n l) Lower Bound for Sample-Bass Based 2-Partition Recovery
Theorem C.3. Sample-based 2- 2-clustering requires [n log subset queries.
Proof. Let [U] = n be even and let A, B C U be two disjoint sets size |A = |B| = = n/2. Let P (A, B) and for any
U let P. denote the partition obtained by switching the set that belongs to. We show that it requires Qin log n) sample-based subset queries to distinguish P from P. for all r. For U and T U, let &,,y denote the event that querying T distinguishes P from
P.. Note that E occurs iff x E and
C Aor x C B. Thus, for a random set of size
2 2, have
1/2
8-1
8
Pr T: =8
= S
72
72
since the second-to-last quantity is clearly maximized when s = 2. Now, let Q be a collection of sets, each of which consists of some of number of independent uniform samples. Note that the cardinality of these sets can differ from one another. Note that Q distinguishes from every P. iff &x, occurs for every x and some T. By eq. (3) and standard coupon-collector argument, if |Q| o log n). then with high probability there will be some x for which Vreq Ex, occurs.
D Useful Lemmas
D.1 Vector Support Recovery from OR Queries
Given x E {0, 1)",, , let supp(æ) = { 2; }} denote the support of x. An OR-query on set S C [n] returns
(Rs(2) V x; (supp(x) S Ø). SES
This section discusses the problem of recovering the support of vector via OR queries. In particular, we are interested in non adaptive algorithms for this problem. The results in this section are standard in the combinatorial group testing and voin-weighing literature. See e.g. [26, 28] and also [48], who applied these results to obtain query algorithms for graph connectivity.
Lemma D.I. Let æ E (0, 13" such that (supp(x)) algorithu that makes [log n] OR queries and returns supp(x). The runtime is also O(logn).
There is a deterministic, non-udaptive
19

---

Proof. Since [supp(x)] = 1, an OR query on set S is equivalent to taking (z, v) where vi = 1 iff i E S. Let M be the [log n x n matrix whose i'th column is simply b' E {0. 13 [log nn the binary representation of i. The rows of M correspond to OR queries. Then, Mr Ei= nz E: === b' = by where j the unique coordinate where 2
Lemma D.2. Let [0,1)", There is deterministic, non-adaptive algorithm SER1bit that makes 2 2[log n OR queries and certifies whether |supp(a)] = 0, [supp(()) = 1, or [supp(0)] > 1. If [supp(x) x) = L, then it output supp(x). The runtime is also Oloogn).
Proof. Let M be the [log n X n matrix described in the proof of Lemma D.1. Let 1 = 1 [lg x =|xn denote the all I's matrix with the same dimensions. We query M and (1 M) x where here (.) denotes the "OR product". Iee. the i i'th coordinate of M x is 1 ((Mx); > 0). Note that 1 - M is obtained by flipping every bit in M. Note that if [supp(>)] the unique coordinate where x has a one, as in the proof of Lemma D.1. Thus, it suffices to show that we can use these queries to determine whether [supp(>)) is 0, or strictly greater than 1.
1, then M 2: is guaranteed return
First, [supp(x)] = iff (M - =)1, = and ((1- M) x) = since the sets of 1-coordinates in the first row of M and 1 - M partition [n]]
such that (M - z): = 1 and ((1 (1) x)2 = 1. Note that for every row i, the 1-coordinates in the i'th row of M and 1 - M partition (n]. Thus, clearly (M-z); = and ((1 M) x)); = 1, then there are at least coordinates where x has a one. Now we prove the converse. Suppose there exists i * j E [n] where z; = 2j 1. Let b¹ 12 E {0, 10 [log]] n1 denote the binary representations of i, respectively. Since + j. there exists some bit i where by & 1/g. Without loss of generality let bj. = 1 and by 0. Then,
Next, we claim that [supp(x)) > iff there exists some i E [[og n
(M+x)K=1 =1
Σ sebe
>0 =
Σ
1/ > = 1,
c: x==1=1
(1-M)-x)) =1
[ xe 66) (T-")
>0 =1
Σ
n
(1- (5))
00) =1
k
E: zc
and this completes the proof.
Next, we describe a randomized non-adaptive algorithm for recovering the entire support of x.
Lemma D.3. Let E {0, 1)". There is non-adaptive algorithm that makes log 4) OR queries on subsets of size [ and if |supp(xx) S t. returns supp(x) with probability 1 - 8, and otherwise certifies that ss)p((=)] t. The algorithm's runtime is O(n log 3
Proof. For brevity, assume that t divides n. Let Si...., Sm. each formed by taking n/t i.idd uniform samples from [n] and define
in 7. We make OR queries on sets
X = [n]
U
Se.
(E[m]: ORs, (x)==
If | > f, we certify |supp(x)) > t and if [X| < t, then we output X.
Assuming a uniform sample from [m] can be obtained in O(1) time, the runtime of the algorithm is
O(m . :)) = ((n In 7).
Suppose that (x)p > t. Observe that supp(xr) X and so [X] > t with probability 1. Thus, the algorithm is always correct in this case.
Now suppose ( < t. We argue that X (x) with probability at least - 8. Consider some é supp(#), (z). Note that i ş X iff there is some query S 3 for which St n supp(x:) 0. Let E,e denote the event that i E St and Se supp(z)) = 0. Then, since |supp(z)] < f, we have
n 1 (1 (1- [supp(<)))
--1
Pr(E(e]
1
>
t
ct
20

---

and so
Pr[i E X] = Pr [-E,, for all & [ml] 1 (1
et (1-
1 m
N
since fln N.p Thus, by union bound, have Pr(X + supp(z)) S 6.
Finally, we make the following simple observation regarding algorithms that are restricted to making OR queries on subsets of bounded size.
Observation D.4. A single OR query set S can be simulated by [S] queries of size most
Combining this observation with Lemma D.3 gives the following lemma.
Lemma D.5. Let x E {0. 1 and s, 1 be positive integers where S 7. There is non-adaptive algorithm that makes O th log x) OR queries subsets of size and if |supp(x)) L, returns supp(x) with probability time On log )-
8, and otherwise certifies that [supp(x)] > 1. The algorithm runs in
D.2 Connectivity of Erdös-Rényi Random Graphs
Our proofs in Section 2.1, Appendix A, and Appendix G make use of the following bound on the probability of a random graph being connected. For intuition, note that for sufficiently large n,
- 16/33)) 2/n = exp( 1n(33//))
In(3n/8)
Thus, Fact D.6 asserts that for sufficiently large random graph containing > n In edges is connected with high probability, which may be a more familiar statement to the reader. However, need such bound to be true for very small and give the following more broadly applicable version.
Fact D.6. Let G(n,p) denote an Erdös-Rényi random graph. 1fp 2 101-06/330 (6/3n)22/n then G(n,)) p) is connected with probability at least
Proof. A graph G EV is connected if and only if for every cut S C. V. there exists edge (u, (S S). When G is drawn from G(n, p). this does not occur for cut S of size |S| = t with probability exactly (1 ((n-t) There are exactly (?) such cuts. Thus, taking union bound over all cuts and using our lower bound on p. we have
(n)-)
Pr [G not connected] G~G((n)))
3n
(-((n-t)
7
2
t
3n
1=1
n/2
n
3 tm
[n/2|
8
t
1n/2]
n
Σ
(8/3)*
< 6
3n
and this completes the proof.
E An (n log? k:) Algorithm for the Balanced Case
In Appendix B, we gave an algorithm for k-clustering making O(n log k + klog k) subset queries when the cluster sizes are balanced within any constant factor. This query complexity simplifies to log k) long efficient when >
O log" In this section we give an alternative algorithm which is more Tnm
Theorem E.1. There is non-adaptive algorithm for recovering B-balanced k-clustering using O log" k) subset queries of size O(k) which succeeds with probability 99/ 1000.
21

---

Proof. Recall that for a vector v E {0, 1)", an OR query on a set S S [n|] returns ORs(v) = Vies % We will use the following lemma for recovering supp(r) = {i: 02 = 1} via OR queries. We prove and discuss this lemma in Appendix D.1 (see Lemma D.2).
Lemma E.2. There is a deterministic, non-adaptive algorithm that takes an arbitrary u E {0.1}", makes 2 flog n OR queries, and certifies whether |supp[t)] 0, [supp(u)] 1. or |supp(u)] > 1. If [fppppp)) u) = 1, then it outputs supp(v). The runtime is (log
Given E U foi.-... 1 Fn), let C(z) denote the cluster containing it. Let u(() E 10,
denote the Boolean vector with vf = (x; E C(x)). As in Section 2.2, we have (R)(x)
1 1[((S U (x})- g(S)). Le. OR queries to v(2) are simluted by two subset queries to the clustering. This implies the following corollary.
Corollary E.3. Given a k-clustering on U of size n and an element x E U, let C(z) denote the cluster containing x. There is deterministic von-adaptive algorithm which takes input and set R S U, makes (log [R]) subset queries, and if R n C(x)] = 1, then the algorithm returns the unique = R (x), and otherwise certifies that [R C(x) + 1. The runtime is O(log RR).
The pseudocode for the algorithm is given in Alg. 5. In words, Corollary E.3 says that if we have a set R containing exactly one representative from C(x), then with O(log RR)) subset queries we can identify that representative. Thus, suppose we have collection of sets R ..... R, such that for every cluster j E [k]. there is some R& containing a unique representative from Cj. Consider the bipartite graph where on the left we have U and the right we have Rí U-.. J R. Then, for every a E U and every R, we can run the procedure from Corollary E.3, and if returns a representative y E R, C(rr), then we add the edge (z. y) to this graph. By the property of RI.... R., two vertices I, y E U belong to the same cluster iff they are connected by a path of length 2 in this graph. We show that setting = @(B² log k) and letting each R2 be random sample of k. elements from U results in collection of sets with this good property with high probability. This leads to query complexity of n Ollog k) = O(n log" k).
Algorithm 5: Second Algorithm for the B-Balanced Case
Input: Subset query access to B-balanced partition C1 U.C. = U of [U] = n points; Choose eB² In( 100k)) sets Ri...., R, each formed by &/2 uniform samples from U; Construct bipartite graph G(U, R,, E) as follows;
for x E U and e [s] do
Run the algorithm from Corollary E.3 on input x and Rg; if the algorithm certifies there unique y E R₁ such that x, y are the same cluster then
Add the edge (v. to E(G);
end
end
10 Let Ci...., C2 denote the connected components of G;
Output the clustering CC....,C.)):
Query complexity and time complexity: The algorithm makes - O(log ) O(B log² k) queries. We assume that a uniform random sample can be obtained in O(1) time. Thus, line (2) runs in O(Bk In k) time. By Corollary E.3, line (5) runs in time O(IR; (2 = Ō k). Thus, the entire lor- (lines 4-9) runs in time (ns log k) O BB22n log² k). The bipartite graph G has at most O(n+ Bk log k) vertices and at most O(ns) O O log k) edges. Thus, line (10) can be executed in time O B2n log k) time. The total runtime is thus dominated by O log" k).
The correctness of the algorithm now follows immediately from the following claim.
Claim E.4. With probability at least 99/100, for every j E [k), there exists i E [8] such that RR n C21 = 1.
22

---

Proof. Fix j E [k] and i [s]. We have
Pr[lR, Cj| 1] [Ral [c]
(1-12)
|R
k
1
B
2/B
n
n1
Bk
eB²
and so for a fixed j E [M]]
eBa ln(100k)
Pr[Vi E [+]: Ran #1|
cB²
100%:
and so by union bound and this completes the proof.
1
Pr[3j E [b], vi E [s]: RR n
C2
#
1
100
F Two-Round Algorithms
In this section we describe two algorithms that use two rounds of adaptivity. That is, these algorithms allowed to specify a round of queries, receive the responses, perform some computation, then specify a second round of queries and receive the responses, before finally recovering the clustering. We give a simple deterministic algorithm making O(n log k) queries in Appendix F.1 and random- ized algorithm for recovering a balanced clustering with On log log k) queries in Appendix F.2. Both algorithms exploit the additional round of queries to first compute set containing exactly one representative from every cluster.
F.1 A Two Round On k) Deterministic Algorithm using Single Element Recovery
Theorem F.1. There is two-round, non-adaptive, deterministic algorithm for k-clustering using O(n k) subset queries.
Algorithm 6: Deterministic 2-Round Algorithm
I......,,, Input: Subset query access to hidden partition Ci,...,, CR of U (21,...,,T..
2 Round I:
Query P: (w:: i < 1) for every E [n]:
Define R = (ax: ((P)) - q( PP)-1) = 1) containing exactly one point from every cluster;
For each y E R. define cluster Ry {y):
6 Round 2:
for E U do
8
Use the O(log k) deterministic non-adaptive algorithm of Corollary F.2 to find the unique y R for which 2; y lie in the same cluster;
Place x into Ry:
10 end
Output clustering (Ry E R);
Proof. Pscudocode for the algorithm is given in Alg. 6. The runtime is clearly dominated by the for-loop (lines 7-9) which run in time On log k) by Corollary E.3. Fix an arbitrary ordering U = {#1...., Fr }. The first round of queries (lines 3-5) is used to compute set R C U containing exactly one representative from every cluster. This is done by querying every prefix P, = {21...... x,, and observing that (P.) (Pt-1) 1 iff x, is the only representative for its cluster in Pt. Thus, the set Rt computed in line (4) contains, for each cluster C, the first member of C' in the ordering representative from every cluster. The second round of queries is used to determine, for every x E U, the unique representative of C(x) in R (see line 8). To accomplish this we recall Corollary E.3 from Appendix E which we restate below. This completes the proof.
31, . .n- .n. In particular, it contains exactly
Corollary F.2. Given a k-clustering on U of size n and an element x E U, let C(x) denote the cluster containing x. There is deterministic non-adaptive algorithm which takes as imput and set R C U, makes Olog RR)) subset queries, and if R n C(x)] = 1, then the algorithm returns the unique R.. Cz)), and otherwise certifies that R C(x)
23

---

F.2 A Two Round log log k) Algorithm for Balanced Clusters
Recall that a clustering C1 L....U CR = U is B-balanced if n <
Bn k
BE Theorem F.3, There is a two round, non-adaptive algorithm which recovers a B-balanced k- clustering using O log log k) subset queries.
Proof. We will use the following result of [49] on query-based reconstruction of bipartite graphs as black-box. Given bipartite graph GVV, W, E), an edge-count query (S, where 5 C V. T & W returns |E AS x T the number of edges between S and T.
Lemma F.4 ([49), see Section 4.3). There is a non-adaptive algorithm which reconstructs any bipartite graph G(V, W. E.) where (a) [V] = n, (b) [W] m, and (c) every vertex in V has degree at most I, using O(n
log edge-count queries.
log
We will say a set A S U is an independent set if cach element of A belongs to a distinct cluster. Given two independent sets A, B let [A,, B) be the matching where there is edge from x E A to E B if æ, y belong to the same cluster. We observe that edge-count queries in ((A, B) can be simulated by subset queries, leading to the following corollary.
Corollary F5, Suppose that A, BBC C U are independent sets. There is a deterministic, non-adaptive algorithm which reconstructs M (A, B3 using O([A]-
log LAI subset queries. Tog
Proof. We need to show that edge-coum query () where S C A, C T can be simulated by a constant number of subset queries. Let m (S, ') denote the number of edges in M (A, B3) between S and T. Since A, B are independent sets, S, T are also independent sets, and so we have
m( (SS) + (TT) (())
since (S, T) is the number of clusters intersected by both S and T. Thus, one edge-count query to ((A, B) can be simulated by three subset queries and this completes the proof.
Pseudocode for the algorithm is given in Alg. 7. The algorithm is parameterized in terms of a value > 1 which we will choose later in the proof so as to minimize the query complexity. The first round is used accomplish the following. In lines (4-5) we construct set R containing exactly one representative from every cluster and use this to define an initial clustering. In line (6) we sample random sets I ....... Ig and in line (8) make a query to each to check whether or not it is an independent set. Line (10) defines V which is the union of all the I;'s which are independent sets. We now describe the second round. In line (14) we run the procedure of Corollary F.5 to construct the matching M M(I, (I, R) whenever I; is an independent set. Finally, we determine for every E U, the unique y E R for which x; belong to the same cluster. x E V this is done in lines (18-20) by taking xt' neighbor in MT; R)) for some independent set 7,. If x é V, this is done in lines (23-24) by running the procedure of Corollary F.2.
The algorithm always either outputs fail in line (11), or correctly reconstructs the clustering by Corollary F.5 and Corollary F.2. Thus we only need argue that /U [ < 2 occurs with probability at least 99/100 allowing it to pass the check in line (11), and that conditioned on this, the algorithm makes On In In k)) queries when we set 7 appropriately. Let us first count the number of queries conditioned on this event. Line (8) performs queries. Since each T, of size V and |R] = k. by Corollary F.5, lines (13-14) perform a total of (( In = O(VB B n In r) queries. Lines (22-23) use IU' \ V(log k) O(2 1 log k) queries. Setting T OIn k) yields query complexity of O( Bn log log k). We now prove in Claim F.6 that the required bound on |U \ V holds with high probability, and this completes the proof.
Claim F.6. With probability at least 99/ /000, we have IU \A S
Proof. We prove an appropriate bound on E|JU \ V|] and then apply Markov's inequality. Fix x U. For i E [s]. let Ex denote the event that x E 4; and I; is an independent set. Observe that x E U V iff E does not occur for every E [s]. We first lower bound the probability of Engú Observe that Pr[Ex.a] P.
Pr[x E 4:] Pr[4 an independent set
1t]
(5)
24

---

Algorithm 7: Two Round Algorithm for Balanced Clustering
Input: Subset query access to a hidden partition C1 Li... L. of [0| n points;
Round I:
3 Query Pt = { i i t] for every E [n];
Define R { P(P)) ((P.-) 1] containing exactly one point from every cluster;
5 For each y E R. define cluster Ry {w}
Sample 1 T
h mn(00007) sets I,...., l. C U each formed by
&
samples from U;;
10B
7 for i [s] do Query I, (This is to check if (I.) |[,], i.e. whether I is independent set.);
9 end
Let V Use[s): -(4))1111 be the points in U lying in independent among Ii,..., Iss 11 If [ < n1 - 4), then output fail. Otherwise, continue;
12 Round 2:
for i (T.)) |T/] do
14 Run the algorithm from Corollary E.5 on sets 7,, and let Mj C T x R be the output;
end
16
for x
EEU U do
i E V then
18
Choose I such that æ E I, and I, is an independent set; Let y E denote the neighbor of x in the matching M; C R: Place x into Rg:
19
20
21
end
22
a E U V then
23
Use the Oloog k) deterministic non-adaptive algorithm of Corollary F.2 to find the unique E R for which æ, y lie in the same cluster;
24
Place z into Rg:
25
end
26 end
Output clustering (By: y E R):
and
Pr(p E 1.] =1 (1- (1)1-((11)) 1.
1ral
2 exp
2n
B
Sn
where we have used the inequality exp(-2) < - for over all pairs in and the fact that every cluster is bounded |Cyl
[0, 1]. Next, by simple union bound
< Bn we have
B
Pr[7: not an independent set
E I4]
<
2
<
k
10'
Plugging these bounds back into Equation (5) yields Pr,, [Ez,a] events are independent due to the 1t's being independent yields
10n and noting that these
B
k V
Pr(x & V) = Er, Wi [b]] S
exp((In
(6)
10n
1007
where we have used the definition of 8 = 100 B/k - n In(100)). Finally, this implies E[ \ VI] <
n and so by Markov's inequality Pr[ \ VI > =1 <
TOU This completes the proof.
1007
G Sample-Based Algorithm using Unbounded Queries
Theorem G.1. There a non-adaptive, sample-based k-clustering algorithm making Onkk logn) subset queries which is correct with probability at least 99/100. 100..
25

---

Proof. The algorithm is defined in Alg. 8. The proof techniques are quite similar to that of Theo- rems 2.2 and A.1 detailed Section 2.1 and appendix A. We also refer the reader Section 2 for discussion on the main ideas.
Algorithm 8: Sample-Based Algorithm Using Unbounded Queries
Input: Subset query access to a hidden partition C1 L.... ( Quuery Selection Phuse)
LUC. Cx of [U] n points;
3 for p = 0, 1,....., log do
Initialize query set Qp + 0;
Repeat 40nk (3000mk)))
times;
2" Sample T S U formed by 2" independent uniform sample from U;
Query T and add it Qp:
end
(Reconstruction Phase)
Initialize hypothesis clustering Co 0::
11 for p = 0, l., log do Let C, denote the collection of clusters reconstructed before phase p;
......,logg.
12
13
Let R2 = =CEE, C denote the points belonging to these clusters;
Initialize Cp+11 f Cpi
15
Let 2 = (T) Ry:Te Op and |T' Rpl = 2}. Since each T E Qp is a uniform random set, the elements of Q2 are uniform random pairs in U Rp:
Let 27 - (( y E 2- o(( = 1)} denote the set of pairs in Q2 where both points lie in the same cluster. This set can be computed since q(T) Rp) ((T) g n R,p) and q(T' n Rp) is known since at this point we have reconstructed the clustering on R.p Let Gp denote the graph with vertex set R, and edge set Q";
16
17
18
Let CI....,
....,,C Ce denote the connected components of Gp with size at least 2k-20
19
Add CI,..., Ct to Cp+1:
20
end
Output clustering Clogn+1
O1), the number of queries made by the algorithm is Onk To prove correctness it suffices to prove the following lemma.
log Since Doog 2
Lemma G.2. For each p = 0, 0,1...., logn, n, let Ep denote the event that all clusters of size at least have been successfully recovered immediately followiig iteration p of Alg. 8. Then,
26.27
1 100k
Pr| S 100k and Prl Ep-1]
for all p E {1, 21,2.... log
The proof that Lemma G.2 implies Theorem G.I is identical to the proof that Lemma 2.3 implies Theorem 2.2 given just after the statement of Lemma 2.3. Thus, we move on to proving Lemma G.2.
Proof. of Lemma G.2. First consider the case of p In this iteration, the algorithm queries IQul 2 40 nk (300mkk)) random pairs and we need to show that it successfully recovers all clusters with size least n with probability least 1 100k Let C' denote any such cluster and recall from lines (16-17) the definition of the graph Go with vertex U and edge set Qi We will show that the induced subgraph GC is connected, and thus is correctly recovered in lines (18-19), with Since there are at most & clusters, the lemma holds by union bound.
2k
probability least 1 1OOK2
Consider any two vertices x, y E C' and note that [Qol >
We lower bound the probability that (ar, y) is an edge in Go[C] as follows. Note that this occurs iff {x, y) E Qo- Using an identical calculation that of eq. (1), this probability at least 1 300k
20n² In(300nk3) since |C|
|2/|C| implying
that Go C| is connected with probability least 1
1oog by Fact 2.4.
The argument for the case of p > 0 is identical to the argument given in "Case 3" of in the proof of Lemma 2.3 in Section 2.
D
26

---

H An On log k) Adaptive algorithm
log k) queries. Suppose, we have identified 0, and we have i I h always). Suppose they are X= f2 22, 22,..., 2.. We now want find the cluster to which new point y belongs to. We first query {X,y): y. If the answer is + 1, then is part of a new cluster and i grows to i + 1. Otherwise, y is part of the clusters, and we detect the cluster to which y belongs to using binary search. We consider the two sets X1 ( .., [1/2] J. and X2 { +1; .., (.). We then query (X1, v)- If the answer is [i/2] + 1, then we search recursively in X2, else if the query answer is [i/2], then we search recursively in X₁. Clearly, the query complexity is (log k) per item, and it requires
Here sketch a simple adaptive algorithm using log one element from i clusters (initially
(llg k)) rounds of adaptivity even to place one element.
27

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: All of our claims made in the abstract and theorems stated in the introduction are proved formally in the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: All of our results are theoretical and are expressed in the form of theorem statements, which any assumptions are explicitly stated.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sellsspeciiiationn asymptotic approximations only holding locally). ). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
28

---

Answer: [Yes]
Justification: All of our results are theoretical and the paper contains a complete formal proof of every result.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: Our paper does not include any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibilityy may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
29

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
Our paper does not include any experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: /nipp. ccppp.ccpppulcc///eecccc/ geppliiiiggdde....ee /CodeSubmia agionoiicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: Our paper does not include any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: Our paper does not include any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
30

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: Our paper does not include any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with NeurlPS Code of Ethics https http://neeripppe httpps.cc/ppppeee ctc//ppbicc/thhcstsiiiiiiieeeeee
Answer: [Yes]
Justification: Our results are all purely theoretical and did not require the use of any data-sets or human subjects and don't 't pose any potential violation of the code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Since all of our results are theoretical and pertain to specific model for the very broadly applicable problem of clustering, difficult to meaningfully discuss the specific societal impact of our work.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
31

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswi twwode..ooo..... com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
32

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
33


Reviews:
[{"review_id": "h2pzJPG3CZ", "reviewer": "Reviewer_MjFn", "summary": "The paper gives results on clustering a dataset using \"subset queries.\" This is a generalization of \"same-cluster queries.\" The same cluster query asks whether two given elements belong to the same optimal cluster. The subset query asks how many different clusters the elements of a given subset span. There has been recent interest in clustering using same-cluster queries. This paper is an extension of this line of work. Clearly, O(n^2) queries are sufficient to cluster all the points. We would want to explore the possibility of making a much smaller number of queries.  There are two sub-models to consider when discussing subset queries: \n1. Adaptive queries\n2. Non-adaptive queries. \nAdaptive queries allow the query algorithm to adapt new queries based on the response for the earlier queries, whereas, in the non-adaptive model, all subsets should be predefined before making any queries. Adaptive queries are more powerful since O(nk) adaptive same-cluster queries are sufficient, whereas O(n^2) are required in the non-adaptive setting. This paper gives results in the non-adaptive setting: \n- An O(n log^2{n} log{k}) query algorithm for general values of k. This is using a reduction to a known problem in group testing. This is improved to O(n log{k}) for the balanced case (when cluster sizes are within a constant factor of each other).\n- An O(n log log{n}) algorithm for constant values of k. This is using a simple randomized method.", "questions": "- Subset queries may not be easy to answer accurately, specifically when the subsets are large. However, answering such queries approximately (within some margin of error) may be possible. It may be interesting to explore whether some interesting clustering can be obtained using a small number of such \"inaccurate approximate queries.\"", "limitations": "This work is theoretical, and there are no potential negative societal impact.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- From a purely theoretical point of view, the results are interesting. The discussion is elaborate, with various special cases discussed. Except for logarithmic factors, the bounds are tight.\n- The writing is good. The intuition is clearly stated within the main write-up, and the proofs are in the appendix.", "weaknesses": "- The motivation for considering subset queries is not immediately clear. The motivation for same-cluster queries was easier to understand since one can set up a crowdsource platform and ask users to check whether two objects (say images) belong to the same class. Setting up subset queries for large subsets may be tricky since answering such queries is not simple.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the thoughtful evaluation of the paper. Please see the global response for the motivation of the model.\n\n**Subset queries may not be easy to answer accurately**\n\nThis is a fantastic point. Clustering under noisy subset queries is a direction we're interested in exploring in follow-up work. Positive results under a meaningful/realistic noise model would create a more convincing justification for studying subset queries. We believe that our work is an important first step towards this.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2K5JZwxvVs", "reviewer": "Reviewer_SHzL", "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. \n\nIn 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}$.\n\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.", "questions": "Most of the questions are asked in the ‘weakness’ part. Two MISC questions:\n- Line 165: should it be $p\\leq \\log\\log{n}$?\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.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "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:\n- 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.\n- 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.\n- 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$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for this very encouraging message. Please see the responses to your evaluation below.\n\n**It might be good to further clarify what ‘non-adaptive’ means in your paper**\n\nThank you, that is a good point. Our notion of non-adaptivity is only that the queries are made in one round. I.e. queries are not made based on responses from previous queries. Once the query responses are obtained there is no adaptivity-esque restriction on how the algorithm recovers the clusters. We agree that this should be clarified, and will do so in the future version.\n\n**Experiments**\n\nBeing a theoretical paper, we thought simulations will not add a lot of value to the paper; however we can certainly add simulation of our algorithm. \n\n**The dependence on $k$**\n\nThank you, that is a great point. We will add clarification regarding the dependence on $k$ directly after the theorem statement.\n\n**Line 165: should it be $p \\leq \\log \\log n$?**\n\nNo, here $p \\leq \\log n$ is correct since $\\delta$ could be as small as $1/n$ and we need $2^p$ to approximate $1/\\delta$ within a constant factor for some $p$. Note that in this paragraph we are only describing how this strategy leads to a $O(n \\log n)$ query algorithm and the $O(n \\log \\log n)$ comes by combining the two strategies as described in the subsequent paragraphs.\n\n**If we just want the clustering of an $\\alpha$ fraction of the vertices, can we use an even smaller number of queries?**\n\nThis is a great question. Identifying the cluster containing any one point requires $\\Omega(\\log k)$ bits and so determining the clustering of $\\alpha n$ points requires $\\Omega(\\alpha n \\log k)$ bits. Since a query gives $O(\\log k)$ bits of information we require $\\Omega(\\alpha n)$ queries to cluster an $\\alpha$-fraction of the points. In particular, for any constant $\\alpha$, the $\\Omega(n)$ lower bound still holds. \n\nTo answer your question directly, we do think there is a simple way to modify our algorithm to give improved query complexity in this case. For instance in \"Strategy 1\" described in line 161, we only need to handle the case of $\\delta \\geq \\alpha/2$ since we can ignore clusters that are smaller than $\\frac{\\alpha}{2}n$ (we are talking specifically about the $k=3$ case, but this could be generalized). Thus we only need to iterate over $p \\leq \\log \\frac{2}{\\alpha}$ and this naturally leads to a $O(n \\log \\frac{1}{\\alpha})$ query algorithm, which is $O(n)$ for constant $\\alpha$. We will add this to the paper.\n\nIt would be interesting to see if it is possible to get close to $O(\\alpha n)$ for general $\\alpha$, and we don't immediately see how to achieve this using our current ideas. Thank you for the great question.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AZ7tyRnVYb", "reviewer": "Reviewer_WJzB", "summary": "The problem of cluster recovery via membership queries asks to assign each point in a dataset to its $k$ ground-truth cluster by using as few queries as possible to an oracle. A well-studied oracle is the same-cluster oracle that answers, given two points, whether the points are in the same or in different clusters. The complexity of adaptive algorithms for this problem is $\\Theta(nk)$, but non-adaptive algorithms require $\\Omega(n^2)$ for $k \\geq 3$. The authors of this paper consider subset queries to surpass this barrier. Given a set of points $S$, a subset query returns the number of clusters the points in $S$ belong to. It is known that the complexity of an adaptive algorithm is $O(n)$. The authors consider non-adaptive algorithm and obtain the following results.\n\nFor general subset queries, they obtain an algorithm that makes $O(n \\log^2 n \\log k)$ queries for unbalanced clusters, and $O(n \\log k)$ queries for balanced clusters. For constant $k$, they obtain an algorithm that makes $O(n \\log \\log n)$ queries. If the allowed subset size of the queries is bounded by $s \\leq \\sqrt{n}$, their algorithms need an essentially optimal $\\tilde{O}(n^2 / s^2)$ number of queries for constant $k$, and $\\tilde{O}(n^2 / s)$ for arbitrary $k$. Finally, they show that 2-round adaptivity can improve on the log factors in the complexity.\n\nThe algorithms follow two algorithmic approaches. For constant $k$, the authors observe that one can use subset queries to identify an isolated point representing its cluster in a subset and explore the cluster from this point, or one can use subset queries that contain two points from the same cluster to sample intra-cluster edges. The two strategies have a reverse complexity with respect to the cluster size, and a combination of them give the final complexity trade-off. For general $k$, the authors related subset queries to Boolean OR queries, and use these to recover clusters one by one.", "questions": "/", "limitations": "/", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper provides a rather rich collection of results on foundational variants of the non-adaptive cluster recovery problem with near-linear complexity for unbounded subsets.", "weaknesses": "Unbounded subset size may be a rather strong assumption, and the results for bounded subset size of non-adaptive algorithms are not near-linear and almost trivial for constant subset size. One may be interested in few-round adaptive algorithms with bounded subset size.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the very thoughtful review.\n\n**Unbounded subset size**\n\nWe agree that unbounded subset size is a strong assumption and we would like to better understand the query complexity for bounded size in follow-up work. We have shown that $O(\\frac{n^2}{s^2} k\\log n)$ is possible non-adaptively with $s \\ll \\sqrt{n}$ and this is essentially optimal in terms of $n$ and $s$. It would be interesting to know if near-linear query complexity is possible with query sizes that are even smaller than $\\sqrt{n}$, say ${\\rm poly}\\log(n)$. We know this is not possible non-adaptively, but your idea of studying bounded subset size algorithms with few rounds of adaptivity is a great idea to look at in follow-up work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PNuBuOdipk", "reviewer": "Reviewer_hP14", "summary": "**[Setting]**\nThis paper studies the problem of clustering $n$ items into $k$ clusters using an oracle that can tell how many ground-truth clusters are represented in any given subset $S$ of items. The goal is to develop non-adaptive algorithms (where all queries are chosen before the oracle answers anything) and study their sample complexity.\n\n**[Contributions]**\n1. Randomized non-adaptive algorithms for constant k that make:\n    1. $O(n k \\log \\log n \\log k)$ queries when subsets of any size can be queried\n    2. $O(n k \\log n \\log\\log n)$ queries when $|S| = O(\\sqrt{n})$\n2. Randomized non-adaptive algorithms for general k that make:\n    1. $O(n \\log n \\log k (n/s + \\log s))$ queries of size at most $s$\n3. An $\\Omega(\\min(n^2 / s^2, n))$ lower bound for any non-adaptive algorithm that is allowed to query subsets of size at most $s$.\n\nThe developed algorithms run in polynomial time. \n\nAdditionally, the paper also presents results for the case when :\n1. Clusters are roughly balanced (i.e., their sizes are within constant factors of each other). Here, the algorithm makes $O(n \\log k)$ queries when $k = O(n/\\log^3 n)$ and $O(n \\log^2 k)$ queries for any $k$.\n2. An adaptive round is allowed. This improves dependency on logarithmic factors.\n\nFor these results, the details are only in the appendices.", "questions": "1. Please address point 1 under weaknesses.\n2. It seems to me that both Algorithm 1 and 2 work for any value of k. Can the authors elaborate on what they mean by constant $k$ and general $k$? Do you have two algorithms because one of them has a better dependence on $k$ ($O(\\log k)$ instead of $O(k \\log k)$)? On a similar note, how should one go about choosing between Algorithm 1 and 2 in practice?\n3. Your lower bound is based on the idea of converting subset queries to pairwise queries. Unfortunately, this hides the dependence on $k$. Are you aware of any lower bounds in the pairwise case that depend on $k$ as well?", "limitations": "While it is true that all theorems have their assumptions listed, it would help the readers if the authors include a dedicated paragraph pointing out some of the research gaps that are left open by their work.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. The paper is fairly comprehensive and presents query complexity results in a wide range of settings. The proposed algorithm are optimal up to logarithmic factors.\n2. The algorithms are well motivated. I especially appreciate the high-level intuition because of the clarity it adds to the paper.\n3. While I have some concerns about the problem setting (see Weaknesses), I believe the presented results are a very good first step towards filling an interesting research gap - non-adaptive algorithm for clustering with subset queries.", "weaknesses": "1. My primary concern is with the feedback model. The oracle returns the number of clusters in the subset $S$, which implies that it knows the correct grouping in $S$. Why then would it only return the number of clusters in $S$ in practice and not the clusters themselves? Perhaps there are bandwidth constraints on response in some applications? But wouldn't one require way fewer queries if the oracle returns the clusters in $S$, which alleviates the bandwidth concerns, especially in the non-adaptive setting?\n2. This is a relatively minor concern, but the paper defers a lot of details to the appendix without even including high-level ideas. I recommend including some details in the main paper, perhaps at the cost of a few technical details from Section 2. For example,\n    1. What changes to the algorithm allow the query complexity to improve for the roughly balanced case?\n    2. What is the \"extra round of adaptivity\"?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for this constructive evaluation. Please see the global response for the question related to motivation. The rest of the responses are provided below. We will also add some high level ideas from the appendix to the main paper as suggested. \n\n**Can the authors elaborate on what they mean by constant $k$ and general $k$**\n\nYou are correct that both algorithms work for any value of $k$. We have two algorithms because one of them has better query complexity when $k$ is small and the other has better query complexity when $k$ is large. Specifically, the algorithm of Theorem 1.2 makes $O(n \\log \\log n \\cdot k \\log k)$ queries while Theorem 1.1 gives $O(n \\log^2 n \\log k)$. Thus, to be precise, Theorem 1.1 is better when $k \\leq O(\\frac{\\log^2 n}{\\log \\log n})$ and Theorem 1.2 is better otherwise. In practice, the algorithm should be chosen based on where $k$ falls with respect to this threshold. We wrote \"constant $k$\" because we wanted to emphasize that Theorem 1.2 gives query complexity $O(n \\log \\log n)$ when $k$ is a constant and \"general $k$\" to emphasize that Theorem 1.1 gives query complexity $O(n \\log^2 n \\log k)$ for all $k$. We will add a few lines in the write up to make this more clear.\n\n**Are you aware of any lower bounds in the pairwise case that depend on $k$ as well?**\n\nFor non-adaptive pairwise query algorithms there is an $\\Omega(n^2)$ lower bound for $k=3$ which is as strong as possible (for any $k\\geq 3$) since $O(n^2)$ is also a trivial upper bound for any $k$. For $k = 2$, $O(n)$ is possible non-adaptively and this is optimal since the algorithm will need at least one pairwise query involving every point. Thus, this is the complete picture for non-adaptive pairwise query algorithms.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We sincerely thank all of the reviewers for their very thoughtful reviews and comments. 

**Motivation for Subset Queries.**

As reviewer SHzL has pointed out, clustering with subset queries is a natural extension of the well-studied same-cluster queries. While with same-cluster queries we would require $O(n^2)$ non-adaptive queries to recover the clusters even for small $k$, here we show that just near-linear number of queries suffice with subset queries. To address the questions related to the practical motivation for the model, we provide a few justifications below. Rest of the questions have been addressed with a response to each reviewer separately. 

- In the paper, we have considered non-adaptivity where queries are asked in one round as a major practical motivation. Several prior works have shown it is extremely time consuming to get query answers adaptively from a crowd. Subset queries is the only way to get good query complexity while considering non-adaptivity.
- As a reviewer pointed out, bounded size queries are more practical than unbounded size queries. We have studied the effect of query size for both of our algorithms. Our strategy 1 gives optimal dependency on query size. 
- Our work serves as a stepping stone for future work to consider few rounds of adaptivity (partial answers have been provided in Appendix F), and where errors are allowed in query answers.
- As reviewer hP14 brings up, if there is a bandwidth constraint, then returning just a number is much easier. Suppose the algorithm sends its queries $S_1,\ldots,S_q$ off to $q$ different entities. Suppose these entities have a bandwidth constraint in that they do not want to send back much information. Answering a subset query requires them to send only $O(\log k)$ bits (just a number), instead of $O(|S_i| \log k)$ needed for describing the whole clustering on $S_i$. The total number of bits sent is $O(q \log k) = \widetilde{O}(n)$ and the max number of bits sent by any entity is $O(\log k)$. 
 - If the model was instead that the query returned the entire clustering on $S$, then the problem is trivially solvable with $1$ query when unbounded size is allowed. On the other hand, for bounded size queries, it does not change the information theoretic lower bound. 
 - Consider the problem of counting the number of clusters represented in $S$ vs computing the clustering in $S$ from the perspective of an entity answering a query. The counting problem is easier, because one does not have to resolve ambiguities in assignments. Therefore, even if assignments can be erroneous, counts are likely to be correct (hence more robust).


Again, thank you to all of the reviewers. We greatly appreciate the time and effort you've invested to carefully read and evaluate our work.

Meta-review: This paper studies the problem of reconstructing a clustering by asking queries to the oracle, and proposes a new model for such interaction. The main weakness of the paper, mentioned by all four reviewers, is an unrealistically strong assumption that the oracle can return the exact count of clusters in an unbounded size query. This is a quite serious concern especially given that what we get from this strong assumptions (compared to the more standard pairwise same-cluster queries) is the ability to ask queries nonadaptiviely and to still get a nontrivial upper bound. I'm not entirely convinced by the arguments brought in the rebuttal, but the reviewers seem to be very positive about the paper regardless, so I lean towards acceptance.
Decision: Accept (poster)