Clustering with Non-adaptive Subset Queries

Authors: hadley  black
euiwoong  lee
arya  mazumdar
u c san
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 22:51:38

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)$.

Main paper: 
 introduction: 
 Clustering is one of the most fundamental problems in unsupervised machine learning, and permeates beyond the boundaries of statistics and computer science to social sciences, economics and so on. The goal of clustering is to partition items so that similar items are in the same group. The applications of clustering are manifold. However, finding the underlying clusters is sometimes hard for an automated process due to data being noisy, incomplete, but easily 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 users can provide feedback whether a cluster needs to be merged or split. Perhaps a simpler query model would be where users only need to answer the number of clusters, and that too only on a subset of points without requiring to analyze the entire clustering. This scenario is common in unsupervised learning problems, where a centralized algorithm aims to compute a clustering by crowdsourcing. The crowd-workers play the role of an oracle here, and are able to answer simple queries that involve a small subset of the universe.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, v, 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, e.g. [14] . Moreover, clustering with pair-wise queries is intimately related to several well-studied problems such as correlation clustering [15, 16, 17, 10, 18] , edge-sign prediction problem [19, 7] , 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 a crowdsourcing setting being non-adaptive is a 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 n is the number of points in the ground set to be clustered and k (unknown) is the number of clusters. However as shown in [5] and our Theorem C.1, even for k = 3, even randomized non-adaptive algorithms can do no better than the trivial O(n 2 ) 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 a subset query oracle. More precisely, we assume that there exists a groundtruth partitioning of U = k i=1 C i , and upon querying with a subset S ⊆ U , the oracle returns q(S) = |{i : C i ∩ S ̸ = ∅}|, 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 better non-adaptive algorithms.In addition to being a 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 ∈ {0, 1} n , the goal is to reconstruct x using queries of the form q(S) := i∈S x i for S ⊆ [n]. It is known that Θ(n/ log n) is the optimal number of queries [29, 30, 31] , which can be obtained by a non-adaptive algorithm. There are improvements for the case when ∥x∥ 1 = d for d ≪ n [32, 33, 34] . Moreover, there has been significant work on graph reconstruction where the task is to reconstruct a hidden graph G = (V, E) from queries of the form q(S, T ) := |{(u, v) ∈ E : u ∈ S, v ∈ T }| for subsets S, T ⊆ 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] .It is not too difficult to show that an algorithm making O(n log k) queries (Appendix H) is possible for k-clustering, while Ω(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 n = 2 n log k . In fact, it is possible to have an algorithm with O(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.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 1 -δ, for any arbitrary constant δ > 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 O(n log 2 n log k) subset queries.For constant k, this dependency can be further improved.Theorem 1.2. (Theorem 2.2, simplified) There is a randomized, non-adaptive k-clustering algorithm making O(n log log n) subset queries when k is any constant.Note that the algorithm of Theorem 1.2 works for any value of 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 k 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, s. 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 Ω(n 2 ) queries even for k = 3. Since a subset query on S can be simulated by |S| 2 pair queries, we immediately get the following theorem. Theorem 1.3. (Corollary C.2, restated) Any non-adaptive k-clustering algorithm that is only allowed to query subsets of size at most s must make at least Ω(min( n 2 s 2 , n)) queries. Theorems 1.1 and 1.2 above show that this can be bypassed by allowing larger subset queries. However, some of these queries are of size Ω(n), and this raises the question, is there a near-linear non-adaptive algorithm which only queries subsets of size at most O( √ n)? We answer this in the affirmative, implying that our lower bound is tight in terms of s. Theorem 1.4 (Theorem A.1, informal). There is a non-adaptive k-clustering algorithm making O(n log n log log n) subset queries of size at most O( √ n) when k is any constant. For all sufficiently small s = o( √ n), the algorithm makes O( n 2 s 2 log n) subset queries of size at most s. The result also extends to arbitrary k with slightly worse dependency on s (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 is a set formed by independent, uniform samples. I.e. the algorithm specifies a query size t ≤ s, and then receives (S, q(S)) where S is formed by t i.i.d. uniform samples from U . Being sample-based enables the algorithm to leave the task of curating 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.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 us call such a clustering "roughly balanced". 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 a 2-round deterministic k-clustering algorithm making O(n log k) subset queries. There is a randomized 2-round algorithm for recovering a roughly-balanced k-clustering making O(n log log k) subset queries.Organization: The remainder of the paper is organized as follows. In Section 2, we give our main results developing non-adaptive algorithms with near-linear query complexity Theorems 1.1 and 1.2. Our results for sample-based, bounded query algorithms are given in Appendix A. Finally, we prove 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. 
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 k is assumed to be a constant. In general, the dependence on the number of clusters is O(k log k). In Section 2.2, we give an alternative algorithm with O(n) query complexity for any k ≤ n.Warm Up. When there are only 2 clusters, there is a trivial non-adaptive algorithm making O(n) pair queries: Choose an arbitrary x ∈ U and query {x, y} for every y ∈ U . The set of points y where q({x, 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 O(n) query algorithm. However, for non-adaptive 3-clustering it is impossible to do better than the trivial O(n 2 ) algorithm (see Theorem C.1). Essentially, this is because in order to distinguish the clusterings ({x}, {y}, U \ {x, y}) and ({x, y}, ∅, U \ {x, y}) the algorithm must query {x, y} and their are n 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| ≥ n/3, it is easy to find: sample a random x ∈ U and query {x, y} for every y ∈ U . The cluster containing x is precisely {y ∈ U : q({x, y}) = 1}. With probability at least 1/3, we have x ∈ 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, we can exploit larger subset queries to explore U \ A since q(S \ A) = q(S) -1(S ∩ A ̸ = ∅). Importantly, the algorithm is non-adaptive and so the choice of S cannot depend on A, but we are still able to exploit this trick with the following two strategies. Let δn = |B| denote the size of B and note that this implies |A| ≥ (1 -2δ)n since the third cluster is of size at most B.Strategy 1: Suppose a query S contains exactly one point outside of A, i.e. S \ A = {x} . Then, for y / ∈ A, q(S ∪ {y}) = q(S) iff x, y belong to the same cluster. Thus, we can query S ∪ {y} for every y ∈ U to learn the cluster containing x. If S is a random set of size t ≈ 1/δ, then the probability that|S \ A| = 1 is at least t • δ • (1 -2δ) t-1 = Ω(1). Of course, we do not know δ, but we can try t = 2 p for every p ≤ log n and one of these choices will be within a factor of 2 from 1/δ. This gives us an O(n log n) query algorithm since we make n queries per iteration.Strategy 2: Suppose S intersects A and contains exactly two points outside of A, i.e. S \ A = {x, y}. Then, q({x, y}) = q(S) -1 which tells us whether or not x, y belong to the same cluster. If 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 a subset of one of the remaining two clusters. In particular, if the induced subgraph, G[B], is connected, then we recover B. Moreover, if S is a random set of size t ≈ 1/δ, then the probability that two points land in B and the rest land in A is at least t 2 • δ 2 • (1 -2δ) t-2 = Ω(1). A basic fact from random graph theory says that after ≈ |B| ln |B| ≤ δn ln n occurrences of this, G[B] becomes connected with high probability and so querying Ω(δn ln n) random S of size ≈ 1/δ will suffice. Again, we try t = 2 p for every p ≤ log n, resulting in a total of ≈ n ln n p 2 -p = O(n 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 δ ≤ 1 log n , then we only need to try t = 2 p ≥ log n and so the query complexity becomes ≈ n ln n p≥log log n 2 -p = O(n). On the other hand, if we assume that δ > 1 log n , then in strategy (1) we only need to try p ≤ 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 -α)-fraction of points. In this setting we can ignore the case of δ < α/2 (recall the definition of δ above) as this will only result in an incorrect classification of an α-fraction of points. Thus, for example, one can employ "strategy 1" above, but only iterate over p ≤ log(2/α), leading to an O(n log 1 α ) query algorithm. However, in this paper we focus on the more challenging task 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 ∈ {0, 1, . . . , log n} where the goal of the algorithm during the p'th iteration is to learn all remaining clusters of size at least n 2k•2 p . This is accomplished by two different strategies depending on whether p is small or large.When p ≤ log log n, the algorithm samples O(k log k) random sets T formed by 2 p samples from U and makes a query on T and T ∪ {x} for every x ∈ U (see lines 5-9 of Alg. 1). Let R p be the union of all clusters reconstructed before phase p (i.e., clusters of size at least n 2k•2 p-1 ). If such a T contains exactly one point z ∈ T \ R p belonging to an unrecovered cluster, then we can use these queries to learn the cluster containing z (see lines 24-28 of Alg. 1), since for x ∈ U \ R p , q(T ) = q(T ∪ {x}) if and only if x, z belong to the same cluster. Moreover, we show that this occurs with probability Ω(1) and repeat this O(k log k) times to ensure that every clusterC where |C| ∈ [ n 2k•2 p , n 2k•2 p-1) is learned with high probability. The total number of queries made during iterations p ≤ log log n is O(n log log n • k log k).When p > log log n, the algorithm queries O(nk • log n 2 p ) random sets T again formed by 2 p samples from U (see lines 11-14 of Alg. 1). Note that p>log log n 2 -p = O(1 log n ) and so the total number of queries made during these iterations is O(nk).We now describe the reconstruction phase (see lines 32-37 of Alg. 1). If T contains exactly two points x, y ∈ T \ R p belonging to unrecovered clusters, then we can use the fact that we already know the clustering on R p to tell whether or not x, y belong to the same cluster or not, i.e. we can compute q({x, y}) ∈ {1, 2} from q(T ). We then consider the set of all such pairs where q({x, y}) = 1 (this is Q ′′ p defined in line 34) and consider the graph G with this edge set, and vertex set U \ R p , the set of points whose cluster hasn't 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 everyC where |C| ∈ [ n 2k•2 p , n 2k•2 p-1). This is accomplished by applying a 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 O(n log log n • k log k) subset queries and succeeds with probability at least 1 -δ for any constant δ > 0 1 .The following Lemma 2.3 establishes that after the first p iterations of the algorithm's query selection and reconstruction phases, all clusters of size at least n 2k•2 p 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. 1 succeeds with probability at least 99/100 by an appropriate union bound. The choice of 99/100 is arbitrary, and can be made 1 -δ for any constant δ. Lemma 2.3. For each p = 0, 1, . . . , log n, let E p denote the event that all clusters of size at least n 2k•2 p have been successfully recovered immediately following iteration p of Alg. 1. Then,Pr[¬E 0 ] ≤ 1 100kandPr[¬E p | E p-1 ] ≤ 1 100kfor all p ∈ {1, 2 . . . , log n}.Proof of Theorem 2.2: Before proving Lemma 2.3, we first observe that it immediately implies the correctness of Alg. 1 and thus proves Theorem 2.2. Let I 0 = ( n 2k , n] and for 1 ≤ p ≤ log n, letI p = [ n 2k•2 p , n 2k•2 p-1 ). If there are no clusters C for which |C| ∈ I p , then trivially Pr[¬E p | E p-1 ] = 0, and otherwise Pr[¬E p | E p-1 ] ≤ 1100k by the lemma. Since there are k clusters, clearly there are at most k values of p for which there exists a cluster with size in the interval I p . Using this observation and a union bound, we havePr[¬E log n ] ≤ Pr[¬E 0 ] + log n p=1 Pr[¬E p | E p-1 ] ≤ 1 100which completes the proof of correctness since the algorithm succeeds iff E log n occurs.Query complexity: During iterations p < log log n the algorithm makes at mostO(n log log n • k log k) queries. During iterations p > log log n, it makes at most O(nk log n) p>log log n 2 -p = O(nk) queries since k ≤ n.We assume that obtaining a uniform random sample from a set of size n can be done in O(1) time. Thus, since the algorithm makes O(n log log n • k log k) queries and each is on a set of size at most n, the total runtime of the query selection phase (lines 3-15) is bounded by O(n 2 log log n • k log k). We now account for the runtime in the reconstruction phase. Lines (25) (26) (27) (28) clearly can be performed in O(n) time and so the time spent in lines (24) (25) (26) (27) (28) is We now prove the main Lemma 2.3.O(|Q p | • n). Now, for T ∈ Q p , checking if |T \ R p | = 2Proof. of Lemma 2.3. Let C p denote the set of clusters recovered before phase p and let R p = C∈Cp 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 |C| ≥ n 2k . Note that in this iteration the sets T sampled by the algorithm in line (7) are singletons. We need to argue that one of these singletons will land in C, and thus C is recovered in line (28) , with probability at least 1 -1 100k 2 . Since there are at most k clusters, applying a union bound completes the proof in this case.A uniform random element lands in C with probability at least 1 2k and so this fails to occur for all |Q 0 | ≥ 4k ln 10k samples with probability at most (1-1 2k ) 4k ln 10k ≤ exp(-2 ln 10k) = 1 100k 2 , as claimed. Case 2: 1 ≤ p ≤ log log n. Let C denote some cluster with size |C| ∈ [ n 2k•2 p , n 2k•2 p-1). Note that we are conditioning on the event that every cluster of size ≥ n 2k•2 p-1 has already been successfully recovered after iteration p -1. Thus, the number of elements belonging to unrecovered clusters is|U \ R p | ≤ k • n 2k•2 p-1 = n 2 p .We need to argue that the set Q p will contain some T sampled in line ( 7) such that T \ R p = {z} where z ∈ C, and thus C is successfully recovered in line (28) , with probability at least 1 -1 100k 2 . Once this is established, the lemma again follows by a union bound. We havePr T : |T |=2 p [|T \R p | = 1 and T \R p ⊆ C] = |T |• |C| n • |R p | n |T |-1 ≥ 2 p k • 2 p+1 1 - 1 2 p 2 p ≥ 1 2ekand so the probability that this occurs for someT ∈ Q p is at least 1 -(1 -1 2ek ) 4ek ln 10k ≥ 1 -1 100k 2 , as claimed. Case 3: p > log log n. Let C denote some cluster with size |C| ∈ [ n 2k•2 p , n 2k•2 p-1 ). Note that |U \ R p | ≤ k • n 2k•2 p-1 = n 2 p .Recall from lines (34) (35) the definition of Q ′′ p and recall that G p is the graph with vertex set U \ R p and edge set Q ′′ p . We need to argue that the induced subgraph G p [C] is connected, and thus C is successfully recovered in lines (36) (37) , with probability at least 1 -1 100k 2 . Once this is established, the lemma again follows by a union bound. We rely on the following standard fact from the theory of random graphs. For completeness, we give a proof in Appendix D.2. Fact 2.4. Let G(N, p) denote an Erdös-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 x ∈ U \ R p , then q(T ) = q(T ∪ {x}) iff x, z are in the same cluster;If p ≥ 1 -(δ/3N ) 2/N , then G(N, p) is connected with probability at least 1 -δ.Pr T : |T |=2 p [T \ R p = {x, y}] = 2 p 2 • 1 n 2 • |R p | n 2 p -2 ≥ 2 2p 3n 2 1 - 1 2 p 2 p ≥ 2 2p 10n 2 .28 Thus, we add {x ∈ U \ R p : q(T ) = q(T ∪ {x})} to C p+1 ;29 end end end if p > log log n then Let Q ′ p = {T \ R p : T ∈ Q p and |T \ R p | = 2}. Since each T ∈ Q p is a uniform random set, the elements of Q ′ p are uniform random pairs in U \ R p ; Let Q ′′ p = {{x, y} ∈ Q ′ p : q({x, y} = 1)} denote the set of pairs in Q ′ p where both points lie in the same cluster. This set can be computed since q(T \ R p ) = q(T ) -q(T ∩ R p ) and q(T ∩ R p ) is known since at this point we have reconstructed the clustering on R p ; Let G p denote the graph with vertex set U \ R p and edge setQ ′′ p ; Let C 1 , . . . , C ℓ denote the connected components of G p with size at least n 2k•2 p ; Add C 1 , . . . , C ℓ to C p+1 ; end end Output clustering C log n+1Recall that the algorithm queries|Q p | = 40•nk ln(300nk 2 ) 2 p random sets T of size 2 p . Thus, Pr Qp [(x, y) ∈ E(G p [C])] = Pr Qp {x, y} ∈ Q ′′ p = Pr Qp [∃T ∈ Q p : T \ R p = {x, y}] ≥ 1 -1 - 2 2p 10n 2 40 n 2 p •k ln(300nk 2 ) ≥ 1 -exp - 2 p n • 4k ln(300nk 2 )and using |C| ≥ n 2k•2 p and |C| ≤ n, we obtainPr Qp [(x, y) ∈ E(G p [C])] ≥ 1 -exp - 2 ln(300nk 2 ) |C| ≥ 1 -exp - 2 ln(300k 2 |C|) |C| = 1 - 1 300k 2 |C| 2 |C| . Thus, (x, y) is an edge in G p [C] with probability at least 1 - 1 300k 2 |C| 2 |C| and so by Fact 2.4 G p [C]is connected with probability at least 1 -1 100k 2 , as claimed.Bounded Query Size We can restrict the query size to s ≤ √ n, and still achieve a 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 an O(n log n log log n) query non-adaptive sample-based algorithm using subset queries of size at most O( √ n). The main idea is to employ "Strategy 2" described in the warm-up section of Section 2.1 with a slight alteration. Let A, B denote the largest, and second largest clusters, respectively, where |B| = δn and so |A| ≥ (1 -2δ)n. Observe that if we take a random set S of size t ≈ 1/δ, then the probability that two points land in B and the rest land in A is at leastt 2 • δ 2 • (1 -2δ) t-2 = Ω(δ).Recalling the definition of the graph G and the discussion in Section 2.1, after querying Ω(n ln n) such S, the induced subgraph G[B] becomes connected with high probability, thus recovering the clustering. Similar ideas let us generaize to any s, and achieve an optimal dependency on s as stated in Corollary C.2 for constant k.We now consider the situation with general k, for which our algorithm and analysis follow a completely different approach by using techniques from combinatorial group testing.Warm up. The main subroutine in our algorithm is a procedure for recovering the support of a Boolean vector via OR queries. Given a vector v ∈ {0, 1} n , an OR query on a set S ⊆ [n] returns OR S (v) = i∈S v i , i.e. it returns 1 iff v has a 1-valued coordinate in S. The problem of recovering the support of v, supp(v) = {i : v i = 1} via OR queries is a basic problem from the group testing and coin-weighing literature. The relevance of this problem for k-clustering with subset queries is as follows. Consider a hidden clusteringC 1 ⊔ • • • ⊔ C k = U . Given x ∈ U , let C(x) denote the cluster containing U = {x 1 , . . . ,x n } (an arbitrary ordering of U ), and let v (x) ∈ {0, 1} n denote the Boolean vector where v(x) i = 1(x i ∈ C(x)). An OR query on set S to v (x) can be simulated by a subset query to the clustering on sets S and S ∪ {x} sinceOR S (v (x) ) = i∈S v (x) i = 1(C(x) ∩ S ̸ = ∅) = 1(q(S ∪ {x}) = q(S)).Thus, the problem or reconstructing C(x) via subset queries is equivalent to the problem of recovering v (x) via OR queries, up to a factor of 2 in the query complexity.Then, to learn a cluster C with size n 2 p ≤ |C| ≤ n 2 p-1 it suffices to sample O(2 p ) random x (one of which lands in C with high probability) and then recover C(x) using O( n 2 p log n δ ) OR queries. Iterating over every p ≤ log n and boosting the number of samples to guarantee a high probability of success for all k clusters yields our algorithm. This algorithm can also be restricted to only make subset queries of size at most s, and the query complexity scales with 1 s . Theorem 2.5. For every s ∈ [2, n], there is a non-adaptive k-clustering algorithm making O(n log n log k • ( n s + log s)) subset queries of size at most s. In particular, for unbounded query size the algorithm makes O(n log2 n log k) queries.Proof of Theorem 2.5 We will use the following lemma for recovering supp(v) = {i : v i = 1} via OR queries. We prove and discuss this lemma in Appendix D.1 (see Lemma D.5). Lemma 2.6. Let v ∈ {0, 1} n and s, t ≥ 1 be positive integers where s ≤ n t . There is a non-adaptive algorithm that makes O( n s log n δ ) OR queries on subsets of size s, and if |supp(v)| ≤ t, returns supp(v) with probability 1 -δ, and otherwise certifies that |supp(v)| > t. The algorithm runs in time O(n log n δ ).Recall that OR S (v (x) ) = 1(q(S ∪ {x}) = q(S)), i.e. an OR query on S is simulated by subset queries on sets S and S ∪ {x}. To accomplish this, we sample Θ(2 p log k) random points x ∈ U (line 4-5) and for each one, call the subroutine with t = n 2 p-1 (line 6), which is an upper bound on the sizes of the clusters we are trying to learn.Note that we always invoke the corollary with query size r = min(s, 2 p-1 ) ≤ s, enforcing the query size bounded stated in Theorem 2.5. Query complexity: Note that the number of queries made in line (6) during the p'th iteration is O( n s log n) when 2 p-1 ≥ s, and O( n 2 p log n) when 2 p-1 < s. Therefore, the total number of queries made is at mostO(log k)   p : 1≤2 p-1 <s O(2 p • n 2 p log n) + p : s≤2 p-1 ≤n O(2 p • n s log n)   .The first sum is bounded by O(n log n log s) and the second sum is bounded by O( n 2 s log n). The time-complexity is clearly identical by Corollary 2.7.We assume that attaining a uniform sample from a set of size n can be performed in O(1) time. The procedure in line ( 6) has runtime at most O(n log n) since we set δ = Θ( 1 k ). Thus, the total runtime of the algorithm is O(n log n log k) • p≤log n 2 p = O(n 2 log n log k).Correctness: Consider any cluster C and let p ∈ {1, . . . , log n} be such that n 2 p ≤ |C| ≤ n 2 p-1 . Let E C denote the event that some element x ∈ C is sampled in line (5) during iteration p. Let R C denote the event that C ∈ C when the algorithm terminates. Observe that by Corollary 2.7,Pr[R C | E C ] ≥ 1 -δ = 1 -1 200k. Moreover, using our lower bound on C we havePr[¬E C ] ≤ 1 - |C| n 2 p ln 200k ≤ 1 - 1 2 p 2 p ln 200k ≤ 1 200k.Thus,Pr[¬R C ] ≤ Pr[¬E C ] + Pr[¬R C | E C ] ≤ 1 100kand taking another union bound over all k clusters completes the proof.In this section we present an algorithm using subset queries with size bounded by s, which matches the lower bound of Theorem C.1, up to a log n-factor. Our algorithm has the additional desirable property of being sample-based, meaning that the subsets it queries are formed by taking uniform independent samples. In addition to Theorem A.1, we also obtain a non-adaptive sample-based algorithm using O(nk log n) unbounded queries in Theorem G.1, using a similar approach. We also show a lower bound of Ω(n log n) for any k ≥ 2 in Appendix C.2 for sample-based algorithms, showing that the dependence on n is optimal for this special class of algorithms. For convenience, we will parameterize the query-size bound by s = n 1/r where r is any positive real number in the range 2 ≤ r ≤ 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 a for-loop iterating over all p ∈ {0, 1, . . . , log r log n -1} where the goal of the algorithm during the p'th iteration is to learn all remaining clusters of size at least n k • 2 -r p+1 . We prove that this occurs with high probability in Lemma 2.3, which gives the main analysis. If each iteration is successful in doing so than the entire clustering has been learned successfully after iteration p = log r log n -1 (since 2 -r log r log n = 2 -log n = 1 n ), and we justify this formally just after the statement of Lemma A.2.We describe the algorithm and it's analysis informally for the case of r = 2, i.e. when the query sizes are bounded by s = √ n. We also refer the reader to Section 2 for discussion of the ideas for the simple case of k = 3. Consider some iteration p ∈ {0, 1, . . . , log log n -1} and suppose that prior to this iteration, all clusters of size at least n k • 2 -2 p have been successfully recovered. Let C p denote the collection of all such clusters and let R p = C∈Cp C be the set of points they contain. The goal in iteration p is to learn every clusterC with |C| ∈ [ n k • 2 -2 p+1 , n k • 2 -2 p). The algorithm queries O(nk log n) random sets T formed by 2 2 p samples 3 from U (see lines 5-7 of Alg. 3). Similar to the proof of Theorem 2.2, if T contains exactly two points x, y ∈ T \ R p belonging to unrecovered clusters, then we can use the fact that we already know the clustering on R p to tell whether or not x, y belong to the same cluster or not, i.e. we can compute q({x, y}) ∈ {1, 2} from q(T ). We then consider the set of all such pairs where q({x, y}) = 1 (this is Q ′′ p defined in line 16) and consider the graph G with this edge set, and vertex set U \ R p , the set of points whose cluster hasn't 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 G[C] will be connected for everyC where |C| ∈ [ n k • 2 -2 p+1 , n k • 2 p). This is accomplished by applying a basic fact from the theory of random graphs, namely Fact 2.4.The following Lemma A.2 establishes that after the first p iterations of the algorithm's query selection and reconstruction phases, all clusters of size at least n k • 2 -r p+1 have been learned with high probability. This is the main effort of the proof. After stating the lemma we show it easily implies that Alg. 3 succeeds with probability at least 99/100 by an appropriate union bound. Lemma A.2. For each p = 0, 1, . . . , log r log n -1, let E p denote the event that all clusters of size at least n k • 2 -r p+1 have been successfully recovered immediately following iteration p of Alg. 3. Then,Pr[¬E 0 ] ≤ 1 100kandPr[¬E p | E p-1 ] ≤ 1 100kfor all p ∈ {1, 2, . . . , log r log n -1}.Before proving Lemma A.2, we observe that it immediately implies Theorem A.1 as follows. LetI 0 = [ n k • 2 -r, n] and for 1 ≤ p < log r log n, let Let R p = C∈Cp C denote the points belonging to these clusters;I p = [ n k • 2 -r p+1 , n k • 2 -r p ).Initialize C p+1 ← C p ; Let Q ′ p = {T \ R p : T ∈ Q p and |T \ R p | = 2}. Since each T ∈ Q p is a uniform random set, the elements of Q ′ p are uniform random pairs in U \ R p ; Let Q ′′ p = {{x, y} ∈ Q ′ p : q({x, y} = 1)} denote the set of pairs in Q ′ p where both points lie in the same cluster. This set can be computed since q(T \ R p ) = q(T ) -q(T ∩ R p ) and q(T ∩ R p ) is known since at this point we have reconstructed the clustering on R p ; Let G p denote the graph with vertex set U \ R p and edge set Q which completes the proof of correctness since the algorithm succeeds iff E log r log n-1 occurs.Query complexity: Note that the total number of queries made is O(nk log n)• log r log n p=12 r p (1-2 r ) . When r = 2, the summation evaluates to log log n which establishes the query complexity in item (a) of Theorem A.1.Otherwise, let r = 2 + C for some constant C > 0. We will argue that 2 r p (1-2 r ) ≤ 1 2 2 r p+1 (1-2 r ) for any p ≤ log r log n -1 greater than some constant and thus the summation is bounded aslog r log n p=1 2 r p (1-2 r ) = O(2 r log r log n (1-2 r ) ) = O(n 1-2 r ) = O(n/s 2 )establishing the query complexity in item (b) of Theorem A.1. Observe that2 r p (1-2 r ) ≤ 1 2 2 r p+1 (1-2 r ) is equivalent to r p (1 -2 r ) ≤ r p+1 (1 -2 r ) -1, or equivalently r p-1 ≥ 1 (r -1)(r -2) = 1 C(1 + C)which clearly holds as long as p -1 > log s 2 k log n log log n), which dominates the runtime of the query selection phase. We now prove the main Lemma A.2.Proof. of Lemma A.2. Let R p denote the set of points belonging to a cluster which has been recovered before iteration p.Case 1: p = 0. In this iteration, the algorithm queries |Q 0 | ≥ 8 • nk ln(300nk 2 ) • 2 r-2 random pairs and we need to show that it successfully recovers all clusters with size at least n k•2 r with probability at least 1 -1 100k . Let C denote any such cluster and recall from lines (16) (17) the definition of the graph G 0 with vertex set U and edge set Q ′′ 0 . We will show that the induced subgraph G 0 [C] is connected, and thus C is correctly recovered in lines (18) (19) , with probability at least 1 -1 100k 2 . Since there are at most k clusters, the lemma holds by a union bound.0 | ≥ 2n 2 ln(300nk 2 ) |C| since |C| ≥ n k•2 r .We lower bound the probability that (x, y) is an edge in G 0 [C] as follows. Note that this occurs iff {x, y} ∈ Q 0 . Thus,Pr Q0 [(x, y) ∈ E(G 0 [C])] = Pr Q0 [{x, y} ∈ Q 0 ] = 1 -1 - 1 n 2 |Q0| ≥ 1 -exp - 2 ln(300nk 2 ) |C| ≥ 1 -exp - 2 ln(300k 2 |C|) |C| = 1 - 1 300k 2 |C| 2 |C| (1)and so by Fact 2.4, G 0 [C] is connected with probability at least 1 -1 100k 2 as claimed. Case 2: 1 ≤ p < log r log n. Recall from lines (12-13) that C p denotes the set of clusters recovered prior to iteration p and R p = C∈Cp C is the set of points belonging to these clusters. Note that we are conditioning on the event that every cluster of size at least n k • 2 -r p has been recovered prior to iteration p. Let C denote some cluster with size|C| ∈ n k • 2 -r p+1 , n k • 2 -r p and note that |U \ R p | ≤ k • n k • 2 -r p = n • 2 -r p .Recall from lines (16) (17) the definition of Q ′′ p and that G p is the graph with vertex set U \ R p and edge set Q ′′ p . We need to argue that the induced subgraph G p [C] is connected, and thus C is correctly recovered in lines (18) (19) , with probability at least 1 -1 100k 2 . Since there are at most k clusters, a union bound completes the proof of the lemma.Consider any two vertices x, y ∈ C. We lower bound the probability that (x, y) is an edge in G p [C], which occurs iff there is some T ∈ Q p where T \ R p = {x, y}. We havePr T : |T |=2 r p [T \ R p = {x, y}] = 2 r p 2 • 1 n 2 • |R p | n t-2 ≥ 2 2r p 3n 2 1 -2 -r p t ≥ 2 2r p 10n 2 and since |Q p | = 20nk ln(300nk 2 ) • 2 r p+1 (1-2 r ) , we have Pr Qp [(x, y) ∈ E(G p [C])] = Pr Qp {x, y} ∈ Q ′′ p = Pr Qp [∃T ∈ Q p : T \ R p = {x, y}] ≥ 1 -1 - 2 2r p 10n 2 20•nk•2 r p+1 -2r p ln(300nk 2 ) ≥ 1 -exp - 2 • 2 r p+1 k ln(300nk 2 ) n and plugging in |C| ≥ n k • 2 -r p+1 and |C| ≤ n into the RHS yields Pr Qp [(x, y) ∈ E(G p [C])] ≥ 1 -exp - 2 ln(300nk 2 ) |C| ≥ 1 -exp - 2 ln(300k 2 |C|) |C| = 1 - 1 300k 2 |C| 2 |C| . Therefore, (x, y) is an edge in G p [C] with probability at least 1 - 1 300k 2 |C| 2 |C|, which by Fact 2.4 implies that G p [C] is connected with probability at least 1 -1 100k 2 as claimed.B The Special Case of Balanced ClustersGiven B ≥ 1, we say that a k-partition C 1 , . . . , C k is B-balanced if n Bk ≤ |C i | ≤ Bn k for all i ∈ [k].In this section we prove the following theorem, which gives a non-adaptive algorithm for recovering a roughly balanced k-clustering making O(n log k) subset queries when k = O( n log 3 n ). We give an alternative algorithm making O(n log 2 k) queries for arbitrary k in Appendix E. We also described a two-round algorithm for this setting making O(n log log k) queries in Appendix F. Pseudocode for the algorithm is given in Alg. 4. In line (3) we draw s = Θ(B 2 log k) sets T 1 , . . . , T s each formed by k/B samples from U and in line (5) learn the clustering over their union using Theorem 2.5. I.e., for T = T 1 ∪ • • • ∪ T s , we find R j = T ∩ C j . Then, we query T i and T i ∪ {x} for every x ∈ U and every i ∈ [s] in line (5) . Now, consider some point x ∈ U and let j * be it's cluster's index. Note that q(T i ∪ {x}) = q(T i ) iff T i intersects C j * . Thus, if T i does not intersect C j * , then every cluster j that T i intersects can be ruled out as a candidate for being the cluster containing x. The set J x computed in line ( 8) is the set of all j which can be ruled out in this way. If for every j ̸ = j * , there is some T i containing j, but not j * , then J x = {j * } and we determine j * in line (9) . This occurs for every x ∈ U if the following holds: for every pair (j, j ′ ) ∈ U 2 , there exists T i intersecting C j , but not C j ′ . We show in Claim B.2 that this happens with high probability. O(k 2 B 2 ln 4 k). Line (5) costs O(n • s) = O(B 2 n ln k) time. Constructing J x in line (8) amounts to checking if q(T i ∪ {x}) ̸ = q(T i ) and if T i ∩ R j ̸ = ∅ for each i ∈ [s] and j ∈ [k]. This can be done in time O(|T i | • |R j |) = O(k 2 ln k) simply using |R j | ≤ |R| = O(Bk ln k) and |T i | = k/B.Thus, the total runtime of lines (7) (8) (9) (10) (11) (12) (13) (14) is dominated by O(nk 2 ln k).Correctness: We now prove correctness, which is due to the following claim.EQUATION)Algorithm 4: Algorithm for the B-Balanced Case Input: Subset query access to a B-balanced partitionC 1 ⊔ • • • ⊔ C k = U of |U | = n points;(Query Selection Phase) Choose s = 2eB 2 ln(100k 2 ) sets T 1 , . . . , T s each formed by k B uniform samples from U ; Run the algorithm from Theorem 2.5 to learn the clustering restricted on R = s i=1 T i . Let R 1 , . . . , R k be the output of the algorithm. I.e., if the algorithm is successful, then R j = R ∩ C j for all j ∈ [k]; Query T i and T i ∪ {x} for all i ∈ [s] and all x ∈ U ;(Reconstruction Phase) for x ∈ U do Let J x = i∈[s] : q(Ti∪{x})̸ =q(Ti) {j ∈ [k] : T i ∩ R j ̸ = ∅}. Note that T i ∩ R j ̸ = ∅ iff T i ∩ C j ̸ = ∅. Note that q(T i ∪ {x}) ̸ = q(T i ) iffx does not belong to any cluster that is hit by T i . Thus, J x is the collection of all j such that some set T i has revealed that x / ∈ C j ;if |J x | = k -1 then Add x to R j * where j * is the unique element of [k] \ J x ; else Output fail; end end Output clustering (R 1 , . . . , R k );Proof. Firstly, for fixed i ∈ [s] and j ̸ = j ′ , since each cluster's size is bounded in the interval[ n Bk , Bn k ], we have Pr Ti [E i,j ∧ ¬E i,j ′ ] = Pr[E i,j ] • Pr[¬E i,j ′ | E i,j ] = 1 -1 - |C j | n |Ti| • 1 - |C j ′ | n |Ti|-1 ≥ 1 -1 - 1 Bk k/B • 1 - B k k/B ≥ 1 -exp B -2 • 1 e ≥ 1 2eB 2and so for a fixed (j, j ′ ) ∈ [k] 2 , we havePr T1,...,Ts [∀i ∈ [s] : ¬ (E i,j ∧ ¬E i,j ′ )] ≤ 1 - 1 2eB 2 2eB 2 ln(100k 2 ) ≤ 1 100k 2and the claim follows by a union bound over all (j, j ′ ) ∈ [k] 2 .By Claim B.2, with probability at least 99/100, for every j ̸ = j ′ ∈ [k] we have some T i such thatT i ∩ C j ̸ = ∅ and T i ∩ C j ′ = ∅.In particular, for x ∈ U , let C j * be the cluster containing x. For every j ̸ = j * we have some T i such that T i ∩ C j ̸ = ∅ and T i ∩ C j * = ∅ which means that in line ( 9) of the algorithm, we have J x = [k] \ {j * } and so we successfully identify the cluster containing x. Moreover, this occurs for all x. Finally, line (4) succeeds with probability 99/100 and thus the entire algorithm succeeds with probability at least 49/50 by a union bound. Proof. For every (x, y) ∈ U 2 consider the following pair of partitions: P 1x,y = ({x, y}, ∅, U \ {x, y}) and P 2x,y = ({x}, {y}, U \ {x, y}).Observe that the oracle returns the same value for P 1x,y and P 2 x,y on every possible query except on the set {x, y}. Thus, if query set Q ⊆ U × U distinguishes these two clusterings, then Q ∋ {x, y}. Therefore, the number of pairs {x, y} such that Q distinguishes P 1x,y and P 2 x,y is at most |Q|. Now, let A be any non-adaptive pair-query algorithm which successfully recovers an arbitrary 3-clustering with probability ≥ 2/3. The algorithm A queries a random set Q ⊆ U × U according to some distribution, D A . In particular, for every {x, y} ∈ U 2 , Q distinguishes P 1x,y and P 2 x,y with probability ≥ 2/3. Thus,2 3 n 2 ≤ {x,y}∈( U 2 ) Pr Q∼D A [Q distinguishes P 1 x,y and P 2 x,y ] = E Q∼D A {x, y} ∈ U 2 : Q distinguishes P 1x,y and P 2x,y ≤ |Q| using linearity of expectation, and this completes the proof.Corollary C.2. Non-adaptive 3-clustering requires Ω(n 2 /s 2 ) subset queries of size at most s.Proof. This follows from Theorem C.1 since one s-sized query can be simulated by s 2 pairqueries.Thus, in order to achieve a near-linear non-adaptive upper bound for 3-clustering, we require an algorithm which makes queries of size Ω( √ n). Proof. Let |U | = n be even and let A, B ⊆ U be two disjoint sets of size |A| = |B| = n/2. Let P = (A, B) and for any x ∈ U let P x denote the partition obtained by switching the set that x belongs to. We show that it requires Ω(n log n) sample-based subset queries to distinguish P from P x for all x. For x ∈ U and T ⊆ U , let E x,T denote the event that querying T distinguishes P from P x . Note that E x occurs iff x ∈ T and T \ x ⊆ A or T \ x ⊆ B. Thus, for a random set T of size s ≥ 2, we haveEQUATIONsince 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 P from every P x iff E x,T occurs for every x and some T . By eq. ( 3) and a standard coupon-collector argument, if |Q| = o(n log n), then with high probability there will be some x for which ¬ T ∈Q E x,T occurs.D.1 Vector Support Recovery from OR QueriesGiven x ∈ {0, 1} n , let supp(x) = {i : x i = 1} denote the support of x. An OR-query on set S ⊆ [n] returns OR S (x) = i∈S x i = 1 (supp(x) ∩ S ̸ = ∅) .This section discusses the problem of recovering the support of a 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 coin-weighing literature. See e.g. [26, 28] and also [48] , who applied these results to obtain query algorithms for graph connectivity. Lemma D.1. Let x ∈ {0, 1} n such that |supp(x)| = 1. There is a deterministic, non-adaptive algorithm that makes ⌈log n⌉ OR queries and returns supp(x). The runtime is also O(log n).and soPr[i ∈ X] = Pr ¬E i,ℓ for all ℓ ∈ [m] ≤ 1 - 1 et m ≤ δ N since m = e • t ln N δ .Thus, by a union bound, we have Pr[X ̸ = supp(x)] ≤ δ.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 on a set S can be simulated by |S| s queries of size at most s.Combining this observation with Lemma D.3 gives the following lemma.Lemma D.5. Let x ∈ {0, 1} n and s, t ≥ 1 be positive integers where s ≤ n t . There is a non-adaptive algorithm that makes O( n s log n δ ) OR queries on subsets of size s, and if |supp(x)| ≤ t, returns supp(x) with probability 1 -δ, and otherwise certifies that |supp(x)| > t. The algorithm runs in time O(n log n δ ).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,1 -(δ/3n) 2/n ≈ 1 -exp(- 2 ln(3n/δ) n ) ≈ ln(3n/δ) n .Thus, Fact D.6 asserts that for sufficiently large n a random graph containing ≫ n ln n edges is connected with high probability, which may be a more familiar statement to the reader. However, we need such a bound to be true even for very small n and so we give the following more broadly applicable version.Fact D.6. Let G(n, p) denote an Erdös-Rényi random graph. If p ≥ 1 -(δ/3n) 2/n , then G(n, p) is connected with probability at least 1 -δ.Proof. A graph G = (V, E) is connected if and only if for every cut S ⊂ V , there exists an edge (u, v) ∈ E ∩ (S × S). When G is drawn from G(n, p), this does not occur for a cut S of size |S| = t with probability exactly (1 -p) t(n-t) . There are exactly n t such cuts. Thus, taking a union bound over all cuts and using our lower bound on p, we havePr G∼G(n,p) [G not connected] ≤ n-1 t=1 n t δ 3n 2 n •t(n-t) ≤ 2 ⌊n/2⌋ t=1 n t δ 3n 2 n •t(n-t) ≤ 2 ⌊n/2⌋ t=1 n t δ 3n 2 n • tn 2 ≤ 2 ⌊n/2⌋ t=1 n t δ 3n t = 2 ⌊n/2⌋ t=1 (δ/3) t ≤ δand this completes the proof.E An O(n log 2 k) Algorithm for the Balanced CaseIn Appendix B, we gave an algorithm for k-clustering making O(n log k + k log 4 k) subset queries when the cluster sizes are balanced within any constant factor. This query complexity simplifies to O(n log k) as long as k = O( n log 3 n ). In this section we give an alternative algorithm which is more efficient when k ≫ n log 3 n . Theorem E.1. There is a non-adaptive algorithm for recovering a B-balanced k-clustering using O(B 2 n log 2 k) subset queries of size O(k) which succeeds with probability 99/100.Proof. Recall that for a vector v ∈ {0, 1} n , an OR query on a set S ⊆ [n] returns OR S (v) = i∈S v i . We will use the following lemma for recovering supp(v) = {i : v i = 1} via OR queries. We prove and discuss this lemma in Appendix D.1 (see Lemma D.2).There is a deterministic, non-adaptive algorithm that takes an arbitrary v ∈ {0, 1} n , makes 2⌈log n⌉ OR queries, and certifies whether |supp(v)| = 0, |supp(v)| = 1, or |supp(v)| > 1. If |supp(v)| = 1, then it outputs supp(v). The runtime is O(log n).Given x ∈ U = {x 1 , . . . , x n }, let C(x) denote the cluster containing it. Let v (x) ∈ {0, 1} n denote the Boolean vector with v (x) i = 1(x i ∈ C(x)). As in Section 2.2, we have OR S (x) = 1(q(S ∪ {x}) = q(S)). I.e. OR queries to v (x) are simluted by two subset queries to the clustering. This implies the following corollary. The pseudocode for the algorithm is given in Alg. The correctness of the algorithm now follows immediately from the following claim.Claim E. 4 . With probability at least 99/100, for every j ∈ [k], there exists i ∈ [s] such that|R i ∩ C j | = 1. Proof. Fix j ∈ [k] and i ∈ [s]. We have Pr[|R i ∩ C j | = 1] = |R i | • |C j | n • 1 - |C j | n |Ri|-1 ≥ k B • 1 Bk • 1 - B k k/B ≥ 1 eB 2 and so for a fixed j ∈ [k], Pr[∀i ∈ [s] : |R i ∩ C j | ̸ = 1] ≤ 1 - 1 eB 2 eB 2 ln(100k) ≤ 1 100kand so by a union boundEQUATION100 and this completes the proof.In this section we describe two algorithms that use two rounds of adaptivity. That is, these algorithms are 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 a randomized algorithm for recovering a balanced clustering with O(n log log k) queries in Appendix F.2. Both algorithms exploit the additional round of queries to first compute a set containing exactly one representative from every cluster. Define R = {x t : q(P t ) -q(P t-1 ) = 1} containing exactly one point from every cluster; For each y ∈ R, define cluster R y = {y}; Round 2: for x ∈ U do Use the O(log k) deterministic non-adaptive algorithm of Corollary F.2 to find the unique y ∈ R for which x, y lie in the same cluster;Place x into R y ; end Output clustering (R y : y ∈ R);Proof. Pseudocode for the algorithm is given in Alg. 6. The runtime is clearly dominated by the for-loop (lines 7-9) which run in time O(n log k) by Corollary E.3. Fix an arbitrary ordering U = {x 1 , . . . , x n }. The first round of queries (lines 3-5) is used to compute a set R ⊆ U containing exactly one representative from every cluster. This is done by querying every prefix P t = {x 1 , . . . , x t } and observing that q(P t ) -q(P t-1 ) = 1 iff x t is the only representative for its cluster in P t . Thus, the set R computed in line (4) contains, for each cluster C, the first member of C in the ordering x 1 , . . . , x n . In particular, it contains exactly one representative from every cluster. The second round of queries is used to determine, for every x ∈ 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. • The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 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. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce 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 paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs 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 it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?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 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 a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
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 a specific model for the very broadly applicable problem of clustering, it is 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 or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness 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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 a 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 as 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 or 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe 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)? 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 a 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 a best faith effort. 12. Licenses for existing assets Question: 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? Answer: [NA] Justification: The paper does not use existing assets. Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a 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 of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.38th Conference on Neural Information Processing Systems (NeurIPS 2024).For simplicity of exposition, we use a constant δ in our proofs. The success probability can be boosted to any 1 -1 poly(n) by paying a log n factor in the query complexity in all algorithms.For intuition, if the subroutine is called with r = n t , then Corollary 2.7 makes O(t log n δ ) queries.Note that p ≤ log log n -1 and so2 2 p ≤ 2 1 2 log n = √ n. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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: 
1. Adaptive queries
2. Non-adaptive queries. 
Adaptive 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: 
- 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).
- An O(n log log{n}) algorithm for constant values of k. This is using a simple randomized method.
strength_weakness: strength_weakness: - 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.
questions: 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: limitations: This work is theoretical, and there are no potential negative societal impact.
paper_summary: paper_summary: The paper studies the clustering problem with non-adaptive subset queries. The problem formulation is as follows. Suppose we are given an oracle $q: \mathcal{V}\rightarrow \mathbb{R}$ such that for any query on a subset $S\subseteq V$ of vertices, the oracle returns how many clusters are in $S$ in the optimal clustering. The goal is to recover the optimal clustering with subset queries that are as small as possible. The problem setting is similar to the clustering with same-cluster query problem, where the oracle returns whether two vertices $(u,v)$ are in the same cluster in the optimal clustering. Both problems are motivated by scenarios where we could use semi-supervised learning to obtain such types of oracles. However, in that setting, the number of necessary queries becomes $\Omega(n^2)$ when $k$ is at least $3$. As such, to circumvent this strong barrier, it is natural to look into the new model with extra power for the queries. 

In the new model, we can easily obtain an algorithm $O(n\log{k})$ queries by binary search. However, such an algorithm requires at least $\Theta(\log{k})$ rounds of adaptivity. The paper focused on the non-adaptive setting, where the queries have to be made *independent* of the results of previous queries. The main results include $i).$ an algorithm that makes $O(n \log\log{n})$ queries when $k=O(1)$ (linear dependency on $k$), and; $ii).$ an algorithm that makes $O(n\log^{2}{n} \log{k})$ queries for general $k$. The paper also studied the case when the maximum size of $S$ is bounded and obtained tight bounds when ${|S|}\leq \sqrt{n}$.

**Techniques.** The two main algorithms used different ideas. For the algorithm with constant $k$, the key observation is that after recovering the biggest cluster(s) in the queried set, there are non-trivial probability that the remaining of the queried set has exactly one or two points. For the two cases, we can recover clusters via subset queries for some specific sizes. As such, we can repeat enough times, and use a ‘valid’ set to recursively recover the clusters in the reconstruction phase. For the algorithm with general $k$, the paper reduces the problem to solving the OR queries of boolean vectors. In this way, the paper provides some new results for OR queries and obtains the desired bound.
strength_weakness: strength_weakness: I don’t see any major issue in the paper. Some minor issues to address:
- It might be good to further clarify what ‘non-adaptive’ means in your paper. I think in your algorithm, you could still adaptively ‘add on’ to clusters *after* making the queries. For a moment I thought your algorithm could conduct $\log {n}$ rounds *in parallel* to recover all clusters, which will be even stronger in the ‘non-adaptive’ notion.
- The paper doesn’t contain experiments. I’m personally OK with it, but I think for NeurIPS you might want to justify why this is not an issue. I think AKB [NeurIPS’16] (‘clustering with same-cluster queries’) gives a nice motivation for the same-cluster oracle model, and maybe this paper should provide some similar justifications.
- The dependence on $k$ should be mentioned after theorem 1.2. I think $O(nk)$ is really not that bad – I thought it was something like $2^k$.
questions: questions: Most of the questions are asked in the ‘weakness’ part. Two MISC questions:
- Line 165: should it be $p\leq \log\log{n}$?
- If we just want the clustering of an $\alpha$ fraction of the vertices, can we use an even smaller number of queries?
limitations: limitations: I do not see any potential negative societal impacts.
paper_summary: paper_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.

For 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.

The 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.
strength_weakness: strength_weakness: 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.
questions: questions: /
limitations: limitations: /
paper_summary: paper_summary: **[Setting]**
This 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.

**[Contributions]**
1. Randomized non-adaptive algorithms for constant k that make:
    1. $O(n k \log \log n \log k)$ queries when subsets of any size can be queried
    2. $O(n k \log n \log\log n)$ queries when $|S| = O(\sqrt{n})$
2. Randomized non-adaptive algorithms for general k that make:
    1. $O(n \log n \log k (n/s + \log s))$ queries of size at most $s$
3. 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$.

The developed algorithms run in polynomial time. 

Additionally, the paper also presents results for the case when :
1. 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$.
2. An adaptive round is allowed. This improves dependency on logarithmic factors.

For these results, the details are only in the appendices.
strength_weakness: strength_weakness: 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?
2. 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,
    1. What changes to the algorithm allow the query complexity to improve for the roughly balanced case?
    2. What is the "extra round of adaptivity"?
questions: questions: 1. Please address point 1 under weaknesses.
2. 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?
3. 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: 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.

Comments: title: Acknowledgement
comment: Sorry for the confusion, that was my bad, and thank you for the clarification!

Edit note for review: Taking the whole rebuttal into account, I think this paper should be accepted (change score 6 -> 7).
Thanks for your response. I have no further questions. I will maintain my current score.
Thank you taking time to respond to my questions. I appreciate the added motivation for subset queries and the clarification regarding constant-vs-general k. All the best for your submission !
Thanks for the clarifications and the response. I do not have any further questions.
Thank you for seeking clarification. We apologize if there were some ambiguities in the previous response. 

Our result is optimal for all values of $s \leq \sqrt{n}$ within a $\log n \log \log n$ factor. 

In particular, our algorithm in Theorem A.1 (or the simplified version, 1.4) achieves $O(\frac{n^2}{s^2} k \log n \log \log n)$ non-adaptive queries for any $s  \leq \sqrt{n}$. Thus for constant k (which is the regime for Theorem A.1 and 1.4), our bounds are optimal for all values of $s  \leq \sqrt{n}$ within the $O(\log n \log \log n)$ factor since $\frac{n^2}{s^2}$ is a lower bound for non-adaptive queries. 

So to summarize, it is not correct that the bound is optimal only for "the largest possible" $s \in o(\sqrt{n})$. Instead, the bound is optimal for all values of $s \leq \sqrt{n}$.
Thank you for your response! If I understand correctly, the details you provided agree with my understanding at large, and in particular, the bound is essentially optimal for "the largest possible" $s \in o(\sqrt{n})$ only (and not all $1 \leq s \ll \sqrt{n}$). If that's not the case, please follow up and feel free to let me know.