Optimal Algorithms for Learning Partitions with Faulty Oracles

Authors: adela frances depavia
olga  medrano
martín  del campo
erasmo  tani
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 22:44:36

Abstract: We consider a clustering problem where a learner seeks to partition a finite set by querying a faulty oracle. This models applications where learners crowdsource information from non-expert human workers or conduct noisy experiments to determine group structure. The learner aims to exactly recover a partition by submitting queries of the form ``are $u$ and $v$ in the same group?'' for any pair of elements $u$ and $v$ in the set. Moreover, because the learner only has access to faulty sources of information, they require an error-tolerant algorithm for this task: i.e. they must fully recover the correct partition, even if up to $\ell$ answers are incorrect, for some error-tolerance parameter $\ell$. We study the question: for any given error-tolerance $\ell$, what is the minimum number of queries needed to learn a finite set partition of $n$ elements into $k$ groups? We design algorithms for this task and prove that they achieve optimal query complexity. To analyze our algorithms, we first highlight a  connection between this task and correlation clustering. We then use this connection to build a Rényi-Ulam style analytical framework for this problem, which yields matching lower bounds. Our analysis also reveals an inherent asymmetry between the query complexity necessary to be robust against false negative errors as opposed to false positive errors.

Main paper: 
 introduction: 
 Learning cluster structure from data is a fundamental task in machine learning. While the statistical setting is typically concerned with using batch data to approximately recover cluster structure with high probability, some applications allow for the learner to make explicit queries, and some require exact recovery guarantees.We highlight two key settings. In several scientific domains, particularly bioinformatics, researchers conduct physical experiments to learn whether two objects are part of the same class [9, 11, 20, 35] . Another major application is learning cluster structure by collecting information from human workers via crowdsourcing services [15, 30, 37] . While some traditional methods focus on querying workers for class labels, alternative approaches use simpler same-cluster queries. For example, Vinayak and Hassibi [37] point out that, given images of birds, it may be easier for non-experts to correctly answer the question "Do these two birds belong to the same species?" as opposed to "What species does this bird belong to?" In both of these application domains, the learner typically seeks to minimize the number of queries made, as queries require carrying out potentially expensive measurements or time-consuming experiments.We consider a very general setting and develop algorithms that make no assumptions about the specific type of data involved, but rather rely solely on the same-cluster queries to infer structure.In particular, we model this task by assuming that the algorithm only interfaces with the data via a same-cluster oracle. In this setting, the learner obtains information about a hidden partition C of a finite set V by repeatedly choosing two elements u, v ∈ V and asking questions of the form "Are u and v part of the same cluster?", i.e. given C and V , a same-cluster oracle is an oracle α C that takes as input u and v in V , and returns 1 if u and v belong to the same cluster in C, and -1 otherwise. The power and limitations of same-cluster oracles have been studied in a variety of settings, including the clustering problem described above [8, 26, 33, 34] .However, previous work on this model makes the arguably unrealistic assumption that all queries return the correct answer. In the motivating applications, queries are often at risk of failure that results from relying on non-expert workers or suffering from experimental noise. The learner's goal is to recover the partition in spite of these errors. Such errors are also often not persistent: in the presence of noise, repeating an experiment multiple times may yield different answers, and querying different human workers may result in conflicting responses. Nonetheless, practitioners may need to achieve exact recovery of the underlying partition. However, existing theory either focuses on the error-free regime [26, 33] , assumes that errors are persistent [16, 32] , or focuses on probabilistic guarantees rather than exact recovery [15] .To address this literature gap, we study algorithms for partition learning via same-cluster oracles that are robust to non-persistent errors. A typical way to incorporate uncertainty and noise is to assume that errors occur independently at random with some small probability on every query. However, it is not possible to guarantee exact recovery of the underlying clusters in this model. Instead, we focus on a model in which the learner sets an error-tolerance parameter ℓ, and they require guaranteed full recovery of the hidden partition as long as the error incurred is within this tolerance. In particular, we say a same-cluster oracle α C is ℓ-faulty if it may return an incorrect answer up to ℓ times. We do not assume that errors are persistent: if a single pair of elements is queried repeatedly, an ℓ-faulty oracle may return inconsistent responses. We define the ℓ-bounded error partition learning (ℓ-PL) problem, as the problem of exactly recovering a hidden partition via access to an ℓ-faulty same-cluster oracle.We design algorithms for the ℓ-PL problem and related variants, and analyze their query complexity. We introduce a two-player game based on correlation clustering, and we show that the minimax value of this game is closely linked to the query complexity of the ℓ-PL problem. We then use this game as a framework to give tight lower bounds for the query complexity of this task, proving the proposed algorithms are optimal.We find that the ℓ-PL problem occupies a unique position at the intersection of different research streams. In fact, the study of this problem complements work on clustering with same-cluster query advice, and the techniques used for its analysis draw from the theory of graph learning with oracle queries and the study of Rényi-Ulam liar games 1 . We are hopeful that the impact of these connections will go beyond the results presented in this paper.Clustering with same-cluster oracles In the error-free regime, Liu and Mukherjee [26] studied the query complexity of recovering partitions of a finite set in different oracle models. They prove tight lower bounds on the query complexity of learning partitions with error-free same-cluster oracles, and point out that an algorithm proposed by Reyzin and Srivastava [33] exactly achieves this query complexity.In many motivating applications of this model queries may return the wrong answer, such as when labels result from non-expert human input or noisy scientific experiments. Vinayak and Hassibi [37] consider multiple query models for collecting information from human workers, pointing out that same-cluster queries can accomplish similar end goals as label queries while potentially being easier questions for non-experts to answer correctly. They also provide an algorithm that works for the setting in which triangle queries-which ask the worker to provide all pairwise relationships between three data points-are made. Mazumdar and Saha [30] initiate the formal study of clustering with same-cluster oracles in the presence of persistent i.i.d. errors. They point out that under these assumptions, learning a partition has a strong relationship to recovering community structure in the stochastic block model (SBM). This work inspired a productive line of research on the i.i.d. noise model, which also leverages connections to the SBM to study related problems. In fact, this problem has been studied in the setting when k = 2 [22] , when the underlying clusters are nearly-balanced [32] , and in the semi-random noise model, in which errors occur with some i.i.d. probability, but when they do occur the (erroneous) answer may be chosen adversarially [16] . Models for non-persistent error have also been considered. Chen et al. [15] study same-cluster queries in the presence of i.i.d. error, allowing for repeated querying of pairs. They give an efficient algorithm with recovery guarantees that does not require a-priori knowledge of the probability of query failure. Similar results were also subsequently established in a recent paper by Gupta et al. [23] . Our work complements this line of research by considering a setting in which exact recovery is possible in spite of errors and providing a full characterization of the query complexity of the problem in this setting.In his autobiography, Stanisław Ulam, introduced the following two-player game [36] . One player (the responder) thinks of a number in x ∈ [N ] for some N ∈ N, and the other player (the questioner), given N , tries to guess x by asking only yes/no questions. The main twist to this setup is that the responder is allowed to lie up to ℓ times. The term "Rényi-Ulam games" has since been used to identify a wide range of problems involving asking questions to an oracle who is allowed some limited amount of lying (see e.g. [31] ). The question of finding the worst-case query complexity of the ℓ-PL problem can be naturally formulated as a Rényi-Ulam game, in which the learning algorithm takes the role of the questioner, and the oracle plays the part of the responder.Correlation clustering Bansal et al. [10] introduced correlation clustering. In this problem, one is given a signed graph G = (V, E, σ), where σ : E → {±1} is a function representing one's prior belief about which pairs of vertices belong to the same cluster. The goal of the problem is to return a partition of the vertices of G into clusters that minimizes the amount of disagreement with the edge signs given by σ. The problem is known to be NP-Hard. Many variations of problem have been proposed, including versions with weighted edges [2, 17] , a version where the number of clusters is constrained to some fixed k [19] , and an agreement maximization setting. Different assumptions have also been studied, such as instance stability and noisy partial information [27] [28] [29] .In the previous sections, we introduce a problem in which a learner has to exactly recover a hidden partition by making same-cluster queries that could be subject to up to ℓ errors. Other plausible models for learning partitions with errors could be considered. In this section, we discuss some of the key design features of the model and provide justification and examples.In general, even in the regime in which k the number of clusters is known to the learner, it is not possible to recover the partition exactly unless one is able to resolve all but at most 2 of the pairwise same-cluster relationship between the elements. This follows from a result of Reyzin and Srivastava (this is a key idea leveraged in the proof of Proposition 3 in [33] ). In particular, simple extensions of these core arguments imply that in the setting in which the answers to the queries are persistent, it is impossible to solve the problem even for small constant values of of ℓ [18, 33] . Furthermore, this implies that even in the non-persistent error-model, one cannot solve the problem for a value of ℓ that grows linearly with n. Below, we give two general motivating examples, in the technology and scientific domains respectively, illustrating the role of ℓ in partition learning tasks.Example 1: Robustness to Misinformation Consider a setting where a user is trying to cluster a dataset by crowdsourcing information in the form of same-cluster questions. However, the user suspects that an ill-intentioned competitor organization is attempting to corrupt the learning process by entering a number of bad actors in the crowd to strategically mislabel queries. If the user selects a new person every time they submit a query, then the number of adversarial answers they encounter is finite and does not grow with the number of queries submitted. In this scenario, ℓ plays the role of a security parameter, and the algorithm is guaranteed to be robust to up to ℓ-many poisoned responses. The user can set ℓ based on, e.g., their prior belief about the resources of the competitor organization. Our results can be interpreted as quantifying the cost (in queries / crowd size) of implementing a fixed security parameter ℓ.Example 2: Trustworthy Science Consider a setting in which a scientist is attempting to group items into classes by running experiments that reveal whether two items are in the same class, such as the example of clustering compatible molecules described in Gupta et al. [23] . The scientist has limited resources (e.g. limited materials or time) and can only conduct a finite number of experiments. Our results allow the scientist to derive the maximum number of errors to which their learning procedure can be tolerant, given their fixed query budget. They can use this maximum value asQUERY COMPLEXITY k-KNOWN k-UNKNOWN WEIGHTED ℓ-PL (THM. 1, 3, AND 5) Θ RS k (n, k) + (n -k)ℓyes + k 2 ℓno O RS u (n, k) + (n -k) max{ℓyes, ℓno} + k 2 ℓno ℓ-PL (COR. 2 AND 4, THM. 5) Θ RS k (n, k) + (n -k)ℓ + k 2 ℓ Θ RS u (n, k) + (n -k)ℓ + k 2 ℓ ℓ-PL FN (THM. 1, 3, AND 19) Θ RS k (n, k) + k 2 ℓ Θ RS u (n, k) + (n -k)ℓ + k 2 ℓ ℓ-PL FP (THM. 1, 3, AND 21) Θ RS k (n, k) + (n -k)ℓ Θ (RS u (n, k) + (n -k)ℓ)ERROR-FREE (RESULTS FROM [26, 33] )RS k (n, k) RS u (n, k)Table 1 : The query complexity of the different variants of the ℓ-PL problem, for both the k-known ad the k-unknown setting. We obtain matching upper and lower bounds for all the variants with the exception of the weighted ℓ-PL problem in k-unknown setting, for which the upper bound does not match the lower bound (given for the k-unknown case) exactly. The results are given in terms of the complexity RS k (n, k) and RS u (n, k) (defined in Equations 1 and 2) of solving the problem without errors.the setting for ℓ, and then use our algorithms to guide their choice of experiments. Our analysis would then allow them to measure the significance of their findings by quantifying the number of experiments that would need to have failed for the finding to be incorrect. 
technical preliminaries: 
 Basic definitions Given a positive integer n we denote with [n] the set {1, ..., n}. Given any finite set V we denote with V 2 the set {{i, j}⊆ V | i ̸ = j}. A graph G = (V, E) is a pair containing a finite vertex set V and a subset E ⊆ V 2 . Given a finite set V a k-partition of V is a collection of k pairwise disjoint non-empty subsets C = {C 1 , ..., C k } of V such that k a=1 C a = V .We will denote by n the cardinality |V | of V and we may assume without loss of generality thatV = [n]. Given two elements u and v of V , we write u ∼ C v (resp. u ̸ ∼ C v) for the statement ∃C ∈ C, {u, v} ⊆ C (resp.∄ C ∈ C, {u, v} ⊆ C). We denote by [u] C the equivalence class of u with respect to C, i.e. [u] C is the unique C ∈ C containing u. Given two partitions C 1 and C 2 we say C 2 is a refinement of C 1 if for every C ∈ C 2 there is a C ′ ∈ C 1 such that C ⊆ C ′ . 
a hierarchy of problems: 
 In the introduction we consider learning a partition C of a finite set V by asking questions of the form "Are u and v part of the same cluster in C?", where up to ℓ of the answers may be incorrect. We refer to this as the ℓ-PL problem. We characterize the hardness of the ℓ-PL problem by considering a family of related tasks. In particular, we introduce a hierarchy of problems with different degrees of difficulty (see Figure 1 ) and establish matching upper lower bounds in nearly all of these tasks. We summarize our results in Table 1 .At the bottom of the hierarchy, we have the problem first studied by Reyzin and Srivastava [33] of learning partitions with same-cluster queries, where the answer to every query is guaranteed to be correct. They give an algorithm that can learn the underlying partition with:EQUATIONmany queries when the number k of clusters is known to learner and:EQUATIONwhen k is unknown to the learner. Recently, Liu and Mukherjee [26] showed that no algorithm can guarantee full recovery of the underlying partition in fewer that RS k (n, k) (resp. RS u (n, k)) queries when k is known (resp. unknown) to the learner, showing that the algorithms of Reyzin and Srivastava are optimal down to the exact constants. Since this is the "easiest" version of the problem we will be considering, the lower bounds of Liu and Mukherjee immediately imply the same lower bounds for all the other problems in the family.We then consider two variants of this problem, each only admitting one-sided error. In the first variant, which we refer to as the ℓ-bounded error partition learning with false positives (ℓ-PL FP ) problem, the oracle might return the answer +1 even when two elements are not part of the same cluster. We refer to this kind of fault as a false positive answer. Here, we restrict the oracle to return at most ℓ many false positive answers, for some fixed positive integer ℓ, and to always return -1 when the two elements being queried are not part of the same cluster.In the second variant, which we refer to as the ℓ-PL FN problem, the oracle behaves the opposite way, and it may return -1 even if the two elements being queried are part of the same cluster in the hidden partition (a false negative answer), but it cannot return a false positive answer. Similarly to the previous variant, we restrict the number of false negative answers to be at most some fixed ℓ. We give precise definitions of the ℓ-PL FP and ℓ-PL FN problems below.The ℓ-PL problem is then a generalization of all of the three variants described above (false positives, false negatives and no error), and hence, it inherits hardness results from all three of these problems. Instead of directly designing an algorithm for the ℓ-PL problem, we consider a yet more general version of the problem, and use results from that generalized version to obtain algorithms for all of the other problems in the class. This final variant is a more fine-grained problem, which allows false positive answers and false negative answers to incur different penalties. In particular we consider a weighted version of ℓ-PL, which is formalized in the following definition: Definition 1 ( (ℓ yes , ℓ no )-Faulty Oracle and Weighted ℓ-PL Problem). Let V be a finite set, and C be a partition of V . A (ℓ yes , ℓ no )-faulty oracle for C is an algorithm α C which, given as input a pair of elements uv, returns a value r =∈ {±1} so that for any sequence of queries {u t v t } t∈[T ] the sequence of responses {r t = α C (u t v t )} t∈[T ] satisfies:|{t : u t ̸ ∼ C v t ∧ r t = +1}| ℓ yes + |{t : u t ∼ C v t ∧ r t = -1}| ℓ no ≤ 1.Note that we assume the oracle can maintain an internal state, so its answers may depend on the query history. The weighted ℓ-PL problem asks one to recover an unknown k-partition of V given access to an (ℓ yes , ℓ no )-faulty oracle for C.Observe that by setting ℓ yes < 1 (resp. ℓ no < 1) one would require the oracle to not return any false positive (resp. false negative) answer. As a convention, we will write ℓ yes = 0 or ℓ no = 0 to indicate any setting that ensures the oracle may not return any false positive or false negative answers respectively. We note that, up to rescaling ℓ yes and ℓ no by a factor of 2, this problem is equivalent to a version of the problem in which the oracle has separate constraints for the number of false positive answers and false negative answers, a simple fact which we prove in Appendix B.Given this definition, the (unweighted) ℓ-PL can be cast as a homogeneous version of the above, one in which ℓ yes = ℓ no , as follows: Definition 2 (ℓ-Faulty Oracle and ℓ-PL Problem). An ℓ-faulty oracle is an (ℓ, ℓ)-faulty oracle. The ℓ-PL problem is the problem of learning a partition with access to an ℓ-faulty oracle.The ℓ-PL FP and ℓ-PL FN problems discussed above can now be formally described as special instances of the weighted ℓ-PL problem. In the rest of the paper, we will always assume that the set V , its cardinality n, and the parameters (ℓ yes , ℓ no ) are known to the learner. We will consider both the k-known setting, in which the number k of clusters is known to learner, and the k-unknown setting, in which it is not. It is easy to see that the query complexity of every problem in the k-unknown setting is no smaller than that of the same problem in the k-known setting, since any learning algorithm could simply ignore the value of k.We design separate algorithms for the k-known and the k-unknown setting, while the lower bounds, which we only prove for the k-known setting, apply directly to the k-unknown setting.In the next section we describe a number of algorithmic results to solve variants of the ℓ-PL problem.In particular, Theorem 1 describes the performance of an algorithm for the weighted ℓ-PL problem in the k-known setting. We briefly comment that it is actually not necessary for the number of false negatives ℓ no to be bounded or known in advance in order to run this algorithm and achieve optimal query complexity. Rather the value of ℓ no that appears in the query complexity analysis will be the true number of false-negative responses that occur during the execution of the algorithm. In particular, this implies that in the version of the problem in which no false positives can occur, one does not need to set any upper bound on the error at all. In contrast in the k-unknown setting, in order to achieve the bound described in Theorem 3 our proposed algorithm does require a user-chosen value for ℓ no .Here, a simple argument shows that it is impossible to guarantee one has found the correct answer unless they can upper bound both ℓ yes and ℓ no . 
algorithmic results: 
 Our first result is an algorithm for the weighted ℓ-PL problem in the k-known setting. Theorem 1. There exists an algorithm for the weighted ℓ-PL problem which recovers the full partition C in the k-known setting with query complexity bounded byO(RS k (n, k) + (n -k)ℓ yes + k 2 ℓ no ).We observe an asymmetry in the dependence on ℓ yes and ℓ no respectively, indicating that falsenegative and false-positive errors cause the algorithm to incur different costs. In Section 5 we prove lower bounds showing that this is not a mere artifact of the algorithm or its analysis, but rather a fundamental aspect of the problem.We describe the algorithm and prove Theorem 1 in Section 6. Throughout the paper, when considering the k-known setting, we shall assume that k ̸ ∈ {1, n}, for otherwise the problem is trivially solved without the need to query the oracle. Because the weighted ℓ-PL problem generalizes the ℓ-PL problem, this yields an algorithm for the ℓ-PL problem as well:Corollary 2. There exists an algorithm for the ℓ-PL problem which learns the correct partition in the k-known setting with query complexity bounded byO(RS k (n, k) + (n -k)ℓ + k 2 ℓ).As our final algorithmic result, in Section D we show that the algorithm can be adapted to obtain optimal asymptotic performance for the ℓ-PL problem in the k-unknown setting.Theorem 3. There exists an algorithm for the weighted ℓ-PL problem which recovers the full partition C in the k-unknown setting with query complexity bounded byO RS u (n, k) + (n -k) max{ℓ yes , ℓ no } + k 2 ℓ no .An immediate corollary bounds the query complexity of the ℓ-PL problem in the k-unknown setting.Corollary 4. There exists an algorithm for the ℓ-PL problem which learns the correct partition in the k-unknown setting with query complexity bounded byO RS u (n, k) + ℓ(n -k) + k 2 ℓ .In the following section we show that all the bounds discussed in this section are asymptotically optimal. While the results are stated only asymptotically, we note that the upper bounds we obtain are only a small constant factor away from the lower bounds, and we give the exact upper bounds in Section D, where we prove Theorem 3. 
lower bound techniques: correlation clustering and the chip-liar game: 
 Underlying our lower bound analysis is a connection between partition learning problems, Rényi-Ulam and Chip-Liar games, and correlation clustering. The Rényi-Ulam game, as defined in the background is equivalent to the following Chip-Liar game (see e.g. Chapter 15, in the book of Alon and Spencer [5] ). In the game, N chips, numbered 1 to N are placed on a game board that has ℓ + 1 positions, labeled 0, . . . , ℓ. At the start of the game, all of the chips begin at position 0 on the board. The game takes place in rounds. On each round the questioner player Q selects a subset S of the chips, and the responder player R decides on one of the following moves: they can either increase the position of every chip in S by 1, or increase the position of every chip in S by 1. If a chip at position ℓ is in a group whose position is advanced, the chip is said to have fallen off the board. After this point such chips will no longer advance. The rules of the game constrain R's responses; R must ensure that on every round, at least one chip remains on the board at position i ≤ ℓ. The game terminates when there is a unique chip remaining on the board.Note that one can think of the ℓ-PL problem as a constrained version of this Chip-Liar game. In the k-known setting2 , the chips are equivalent to k-partitions of the finite set V , so that the number N of chips is the Stirling Number of the second kind N = n k . Moreover, unlike the general Chip-Liar game, in our setup the questioner may only select specific subsets S: for any pair of elements u, v ∈ V , the questioner can select S to be the set of all partitions in which u and v are part of the same cluster. When the questioner submits a query ("Are u and v in the same group?"), all chips whose partitions are inconsistent with the response advance by one position on the board. This allows one to adopt the following perspective. One may think of the queries {u t v t } t∈[T ] made by the questioner together with the signs given by the responses to the queries as making up an instance of the correlation clustering problem. The position of a chip on the board will then be equal the cost of the corresponding partition as a solution of the correlation clustering instance constructed. In Appendix E.1 and Appendix E.2, we formalize this intuition by defining Rényi-Ulam Correlation Clustering (RUCC) games, which are the key tools we use to lower bound query complexity.Leveraging the above techniques, we lower bound the query complexity of the ℓ-PL FN and ℓ-PL FP problems. Combining these lower bounds with results in the error-free regime yield the following lower bounds on the ℓ-PL problem.Theorem 5. Every algorithm for the ℓ-PL problem requires at least:Ω(max{RS(n, k), ℓ(n -k), ℓk 2 })queries both in the k-known and in the k-unknown setting. Moreover every algorithm for the weighted ℓ-PL problem requires at least:Ω(max{RS(n, k), ℓ yes (n -k), ℓ no k 2 })queries both in the k-known and in the k-unknown setting. Here RS(n, k) represents RS k (n, k) in the k-known setting, and RS u (n, k) in the k-unknown setting.This theorem is a corollary of Theorems 19 and 21, which we prove in Appendix F.1 and Appendix F.2.Intuitively, the difference in complexity we observe between the case of false negative errors and the case of false positive errors is due to the following. On one hand, certifying the existence of k-clusters using positive answers requires building a spanning forest, which has (n -k) edges. On the other hand, accomplishing the same task using negative answers requires constructing a clique on k vertices which requires O(k 2 ) edges. This intuition is made precise in Section E in the proofs of Theorem 19 and 21 respectively. 
algorithm for weighted ℓ-pl with k-known: 
 In this section we give an algorithm that solves the weighted ℓ-PL problem in the k-known setting with asymptotically optimal query complexity. We later adapt this algorithm to the k-unknown setting in Appendix D.We begin by briefly providing intuition for the algorithm. The algorithm maintains C ′ a refinement of the correct hidden partition C. At the start of the algorithm C ′ is the set of all singleton elements in V . The algorithm repeatedly makes sequences of queries that guarantee progress towards either (a) learning C, in the form of establishing that a pair of vertices u and v must be part of the same cluster, or (b) certifying that an error has occurred in the oracle's responses.In particular, the algorithm repeatedly attempts to construct (k + 1)-cliques of -1 responses. If at any point the oracle responses form such a clique, then a false-negative response must have occurred, as vertices in V belong to at most k distinct clusters (note that k is assumed to be known to the algorithm). In this case, the algorithm has certified a false-negative response. On the other hand, the only way that this process may be interrupted is if the algorithm receives a (+1) response to some query uv. However, if such a positive response is received, repeatedly querying the pair uv will either quickly determine that u and v must be part of the same cluster or it will reveal that an error has occurred. In the first case, the algorithm makes progress towards learning C, and in the second case it has certified the occurrence of an error.We provide the pseudocode for the algorithm and describe in prose the main functions of each subroutine. The algorithm is comprised of subroutines Learn, Get_New, Insert and Compare:Learn This is the core component of the algorithm. It maintains a partition C ′ for V . Throughout the algorithm, C ′ is guaranteed to be a refinement of the true hidden partition C. C ′ is initialized as the set of singletons for every element in V . The algorithm then repeatedly tries to construct a clique of negative answers, supported on some set S ⊆ V until |S| = k + 1. It does so by inserting new vertices v into S by calling the subroutine Insert. Insert may then either make progress towards constructing the clique (by increasing the size of S) or towards learning the hidden partition by decreasing the size of C ′ (merging two clusters together).Get_New Given S ⊆ V and C ′ a partition of V , Get_New returns an element v ∈ V \S representing a cluster in C ′ that's not yet represented in S, i.e. v ̸ ∈ [u] C ′ for any u ∈ S.Insert Given an element v and a subset S ⊆ V , Insert compares v against every element in S by passing u and v to the function Compare. Compare returns result∈ {±1}. If Compare returns a negative result for each u ∈ S, then Insert adds v to the subset S. On the other hand, if Compare returns a positive result for v and some element u ∈ S, then Insert updates the partition C ′ to reflect that u and v must be in the same cluster. The latter is done by merging[u] C ′ with [v] C ′ .Compare Given two vertices u and v, Compare repeatedly submits query uv to the oracle. Compare maintains count to record information about the number of positive and negative responses received for this query. If at any point Compare has received strictly more negative responses than positive responses, it returns result= -1.Algorithm 1: Learn(V, α, k, ℓ yes ) Input: A finite set V , an (ℓ yes , ℓ no )-faulty oracle α C , a target number of clusters k, and error parameters ℓ yes . Output: A partition C ′ of V . S ← {}, C ′ ← {{v} | v ∈ V } while |C ′ | > k do v ←Get_New(S, C ′ ) C ′ , S ← Insert(V, α, S, C ′ , ℓ yes ) if |S| = k + 1 then S ← {} end end return C ′ Algorithm 2: Get_New(S, C ′ ) Input: A partition C ′ of some finite set V , and a subset S ⊂ V such that |S| ≤ |C ′ | Output: An element v ∈ V representing a set in C ′ which is currently not represented by any element of S. for v ∈ V do if [v] C ′ ∩ S = ∅ thenif result = +1 then new_set ← [v] C ′ ∪ [u] C ′ C ′ ← (C ′ \ {[v] ′ C , [u] C ′ }) ∪ new_set return C ′ , S end end // If S is empty or if result = -1 for every u ∈ S then a new item is inserted into S S ← S ∪ {v} return C ′ , SWe briefly remark that for the k-unknown setting, Algorithm 9 proposed in the appendix, works in an analogous fashion. The key difference between the two settings is that rather than building cliques of size k + 1, Algorithm 9 builds the largest clique possible. We then give a charging argument that shows that this strategy does not lead to a significantly higher query complexity. The algorithm and analysis are presented in Section D. In this paper we initiated the study of learning partitions from same-cluster queries subject to bounded adversarial errors. We completely characterize the query complexity of the core problem as well as some of its relevant variants. To do so, we introduce a novel Rényi-Ulam style game based on correlation clustering.The aim of this paper is to resolve the query complexity of exact recovery with a fixed error tolerance. In particular, the results in this paper do not apply to any setting in which the error may exceed the tolerance ℓ, e.g. when errors occur probabilistically and independently on every query. This limitation is analogous to those encountered when considering the Hamming (worst-case, bounded) model of error in the theory of error-correcting codes (see e.g. [24] ). Thus, like the theory for bounded-error codes, results in this paper should be assumed to hold verbatim in stochastic error settings.The results in this paper open up several avenues for future research. First, while we settle the complexity of all the variants of the problem in the k-known setting, the exact complexity of weighted ℓ-PL problem in the setting of k-unknown remains to be determined. Specifically, the lower bounds of Ω(k 2 ℓ no ) and Ω((n -k)ℓ yes ) that we prove for k-known directly extend to the k-unknown setting. However, the analysis of Algorithm 9 can be used to establish upper bounds with terms O(k 2 ℓ no + (n -k) max{ℓ yes , ℓ no }). The question of whether the upper bounds can be tightened to O(k 2 ℓ no + (n -k)ℓ yes ), or whether the corresponding lower bound can be strengthened to e.g. Ω((n -k) max{ℓ yes , ℓ no }) in the k-unknown setting, remains open. Another interesting open question is whether there exist algorithms that can achieve exact recovery in the setting of k-known when the number of false-positives, ℓ yes , is not known to the algorithm a priori. In this work we established that such algorithms exist without knowing ℓ no in advance, but it is unclear whether ℓ yes has analogous properties.We focus on same-cluster queries due to their popularity and simplicity, but there are other practical query models that may interest the community. One such example includes the triangle queries introduced by Vinayak and Hassibi [37] in which a worker is asked to input all pairwise same-cluster responses for three data points at a time. It would be interesting to explore whether the analysis techniques introduced in this work can determine the query complexity of learning partitions under other query models.Comparison of random and adversarial error Most of the prior work on clustering with faulty same-cluster queries focuses on the random-error model. Different models of random error have been considered. The most similar works to this paper are the papers of Gupta et al. [23] and Chen et al. [15] . These papers consider non-persistent random error. In this setting, the best known upper bounds on the query complexity of partition learning areÕ nk f (p)where p is the probability of error and f is some function that tends to 0 as p → 1/2 [15, 23] . It is difficult to compare the scaling of query complexity under random error as a function of probability of error versus the scaling of query complexity under adversarial error as a function of parameter ℓ. However one interesting qualitative distinction is that in this work the tight upper and lower bounds on query complexity under adversarial error never pay for a term as large as n • k • ℓ. Instead in the setting of adversarial error, query complexity bounds scale with(n + k 2 ) • ℓ.Comparison of persistent and non-persistent error Prior literature has also studied the persistent random error version of this problem. The seminal work of Mazumdar and Saha [30] inspired a series of followup works in this setting [16, 22] . For this problem, upper and lower bounds which match up to log factors are known: Mazumdar and Saha [30] establish a lower bound stating that any algorithm achieving probability of recovery at least 3/4 must make at leastΩ nk (1 -2p) 2queries. They further give a (time-inefficient) algorithm which recovers the maximum-likelihood clustering estimate with high probability when p < 1/2, usingO nk log(n) (1 -2p) 2queries [30] . In particular, while a piori the persistent-error versions of the problem can be no easier than the non-persistent-error ones, we are not aware of any result that shows a gap in query complexity between these two different settings.We note that a model imposing persistent adversarial error does not allow for any non-trivial algorithmic results.Active learning of graphs with oracles The field of graph learning focuses on learning graph structure with oracle access to the graph in question. 3 Numerous settings have been considered in the literature, including instances where the target graphs are matchings [6] , stars or cliques [4] , or Hamiltonian cycles [35] . Further research examines Las Vegas algorithms [1] and the role that adaptivity plays in the query complexity of these problems [14, 21] . In a related paper, Reyzin and Srivastava [33] give an algorithm that learns the partitions of a graph with n vertices using O(nk) shortest path queries, as well as an algorithm that learns such partitions using O(n log n) edge counting queries. Angluin and Chen [7] give an algorithm that can learn a graph with n vertices using O(log n) edge detection queries per edge. Following this line of inquiry, Liu and Mukherjee [26] find that the exact worst-case number of queries needed to learn a partition of [n] into k clusters in the same-cluster query model is exactly n(k -1) -k 2 if k is known by the learner a priori, and nk -k+1 2 otherwise.Geometric clustering with oracle advice Ashtiani et al. [8] introduce the problem of clustering data when the learner can make limited same-cluster queries, and they show that this leads to a polynomial-time algorithm for k-means clustering under certain geometric assumptions. In recent years, the model of Ashtiani et al. has inspired a variety of other related works which aim to understand the benefits of accessing a same-cluster oracle (e.g. [12, 13, 16] ). Ailon et al. [3] show that making a small number of queries to a same-cluster oracle allows one to improve exponentially the dependency on the approximation parameter ε and on the number k of clusters for polynomial time approximation schemes for some versions of correlation clustering. Saha and Subramanian [34] also consider the problem of using same-cluster queries to aid the solution of a correlation clustering instance, and they give algorithms with performance guarantees that are functions of the optimal value of the input instance.In this section, we argue that, up to changing the parameters by a factor of at most 2, the weighted ℓ-PL problem is equivalent to one in which the oracle may return up to ℓ yes many false positive answers and ℓ no many false negative ones. We refer to this problem as the asymmetric ℓ-PL problem. Definition 4 (Asymmetric ℓ-PL Problem). Given a finite set V , and a partition C of V , an (ℓ yes , ℓ no )asymmetric oracle for C is an algorithm α C which, given as input a pair of elements uv, returns a value r =∈ {±1} so that for any sequence of queries {(u t , v t )} t∈[T ] the sequence of responses{r t = α C (u t v t )} t∈[T ] satisfies:: |{t | r t = 1 ∧ u t ̸ ∼ C v t }| ≤ ℓ yes and |{t | r t = -1 ∧ u t ∼ C v t }| ≤ ℓ no .The asymmetric ℓ-PL problem is the problem of recovering C by making queries to an (ℓ yes , ℓ no )asymmetric oracle.It is easy to see that any (ℓ yes , ℓ no )-faulty oracle is also an (ℓ yes , ℓ no )-asymmetric oracle and hence the query complexity of the asymmetric ℓ-PL problem is no larger than that of the weighted ℓ-PL problem for the same choice of parameters. Conversely, we have the following: Proposition 6. For any algorithm which solves the weighted ℓ-PL problem by making at most q(n, k, ℓ yes , ℓ no ) queries, there exists an algorithm which solves the asymmetric ℓ-PL problem by making at most q(n, k, 2ℓ yes , 2ℓ no ) queries.Proof. This simply follows from the fact that any (ℓ yes , ℓ no )-asymmetric oracle is also an (ℓ yes /2, ℓ no /2)-faulty oracle.Query Accounting For the sake of analysis, we will assume that the algorithm maintains a global history of all the queries made to the oracle and the responses received. We will also let the algorithm assign labels to query-response pairs. This is done in order to charge the queries made to some measure of progress towards either learning the partitions or certifying that errors have occurred. The lines of pseudocode assigning labels to the query history, written in blue, are not necessary for the algorithm to work correctly but rather are included only to facilitate the analysis. Lemma 7. Throughout the execution of Algorithm 5, C ′ is always a refinement of the true partition.Proof of Lemma 7. C ′ is essentially a global variable. We begin by noting that C ′ is trivially a refinement of the correct partition at the beginning of the algorithm. The only point in the algorithm at which C ′ is modified is on Lines 7 and 8 of Insert. In that step, the algorithm modifies C ′ by merging the cluster containing v with the cluster containing u. This lines are executed only if the value of the variable result, output by Compare, is +1. This happens only if count/ℓ yes > 1 on Line 16 of Compare, in which case the latest call to Compare has obtained more than ℓ yes many uv queries returning +1.We now argue that if that happens, u and v must have been part of the same cluster in the ground-truth partition C. If u and v were not part of the same of the same cluster in C, we derive a contradiction, as this would imply:FP ≥ count > ℓ yes and hence FP /ℓ yes > 1. Hence, if C ′ was a refinement of C before merging the clusters containing u and v, then it is still a refinement of C after merging the two clusters. This invariant is then maintained throughout the algorithm, and the lemma holds.Algorithm 5: Learn(V, α, k, ℓ yes ) Input: A finite set V , an (ℓ yes , ℓ no )-faulty oracle α C , a target number of clusters k, and error parameters ℓ yes .Output: A partition C ′ of V . S ← {}, C ′ ← {{v} | v ∈ V } while |C ′ | > k do v ←Get_New(S, C ′ ) C ′ , S ← Insert(V, α, S, C ′ , ℓ yes , ℓ no ) if |S| = k + 1 then S ← {} end end return C ′ Algorithm 6: Get_New(S, C ′ ) Input: A partition C ′ of some finite set V , and a subset S ⊂ V such that |S| ≤ |C ′ | Output: An element v ∈ V representing a set in C ′ which is currently not represented by any element of S. for v ∈ V do if [v] C ′ ∩ S = ∅ then return v end end return ⊥ Algorithm 7: Insert(v, α, C ′ , S, ℓ yes )Input: A finite set V ,a same-cluster oracle α for V , a partial clique S, a candidate partition C ′ of V , and error parameters ℓ yes . Output: A new candidate cluster C ′ , partial clique S. for u ∈ S do // Returns either result = -1 or +1 result ← Compare(u, v, α, ℓ yes , ℓ no ) // If +1: it is guaranteed that u and v are part of the same cluster and C ′ is edited to reflect this if result = +1 then Re-label all 'clique' queries made during this execution of Insert (and all calls to Compare therein) as 'merge-'new_set ← [v] C ′ ∪ [u] C ′ C ′ ← (C ′ \ {[v] ′ C , [u] C ′ }) ∪ new_set return C ′ , S end end // If S is empty or if result = -1 for every u ∈ S then a new item is inserted into S S ← S ∪ {v} return C ′ , S Lemma 9.At the end of the algorithm, the history of queries contains at most 2 max{ℓ yes , ℓ no } queries labelled 'spurious'.Proof of Lemma 9. Each query uv labelled 'spurious' can be paired uniquely with another query uv labelled spurious which returned the opposite answer. Hence, the number of erroneous answers returned by the oracle is at least the number of spurious queries divided by two. This number is upper bounded by max{ℓ yes , ℓ no } and the result follows.Lemma 10. At the end of the algorithm, the history of queries contains at most (ℓ no + 1) k+1 2 queries labelled 'clique'.Proof of Lemma 10. The algorithm only labels queries as 'clique' in Line 9 of Compare. Thus every 'clique' query is made between two elements u and v such that both u and v were inserted into some construction of a clique, supported on the set S.If S reaches cardinality k + 1, the if block on Line 5 of Insert is executed. We refer to this occurrence as a clique event. When a clique event occurs, queries have made up new a clique of -1 responses of size k + 1. In order for all of these responses to have been correct, the ground-truth partition would need to have been size at least k + 1, hence every time a clique event happens, a false negative error must have occurred. Since every clique event can be charged to a false negative error, at most ℓ no clique events can occur.We will charge every 'clique' query made before a clique event to the first clique event following the query's creation. These queries represent a distinct edge uv of a clique built on S which eventually reaches size k + 1, and hence exactly k+1 2 many of these 'clique' queries will occur per clique event. Finally, all 'clique' queries occurring after the last clique event make up the edges of a clique supported on the set S, which never reaches size k + 1, and hence there are less than k+1 2 such queries.The result then follows.Lemma 11. If Algorithm 5 makes a finite number of queries, then it must terminate.Proof of Lemma 11. We show that if Algorithm 5 makes a finite number of queries, then Line 4 of Algorithm 5 is executed a finite number of times. This implies termination of Algorithm 5.When Line 4 of Algorithm 5 executes, Algorithm 5 calls Algorithm 7, Insert. If S is nonempty on the execution of Line 4, then Insert calls Compare on some pair of elements. On every call to Compare, Line 4 of Compare executes at least once, and hence the algorithm makes at least one query. If S is empty on the execution of Line 4, then Insert increases the size of S by 1. This implies that on the next execution of Line 4, S will be nonempty. Thus in order for Algorithm 5 to execute Line 4 infinitely many times, the algorithm must make infinitely many queries, yielding the result.We now analyze the number of queries made by the algorithm. We begin by noting that when the algorithm terminates, every query made will hold exactly one of the following labels: 'merge-', 'merge+', 'clique', 'spurious'. The analysis proceeds by showing how labels of each category contribute to either (a) correctly identifying the true partition, or (b) correctly certifying the occurrence of errors.Equipped with these lemmata, we now prove Theorem 1.Proof of Theorem 1. Let |'merge-′ |, |'merge+ ′ |, |'spurious ′ |, |'clique ′ |be the number of 'merge-', 'merge+', 'spurious' and 'clique' queries made by the algorithm respectively. By Lemmata 8, 9, and 10, the algorithm makes at most |'merge-′ |+|'merge+ ′ | + |'spurious ′ | + |'clique ′ | ≤ nk -k 2 + (ℓ yes + 1)(n -k) + 2 max{ℓ yes , ℓ no } + (ℓ no + 1) k + 1 2 = O RS k (n, k) + (n -k)ℓ yes + k 2 ℓ noIn this section we describe an algorithm for the weighted ℓ-PL problem in the k-unknown setting, and further prove that it achieves optimal asymptotic performance for the unweighted version of the problem. A complete description of the algorithm is given in the pseudocode below. Note that the algorithm makes use of subroutines defined in Section D. The main challenge in adapting Algorithm 5 in Section 6 is that the algorithm crucially relies on knowing the value of k to build a lower bound to the number of observed errors, by counting the number of (k + 1)-cliques of -1 answers observed.To overcome this problem, the new algorithm will instead simply aim to build the largest possible clique of -1 answers. We show that, remarkably, when false positive and false negative errors are equivalent (ℓ yes = ℓ no = ℓ), this suffices to match the optimal guarantees of Algorithm 5, up to small constant factors.Algorithm 9: Learn_k_unknown(V, α, ℓ yes , ℓ no ) Input: A finite set V , a same-cluster oracle α, error parameters ℓ yes and ℓ no .Output: A partition C ′ of V . C ′ ← {{v} | v ∈ V }, idx← 1 S idx ← {} while idx ≤ ℓ no + 1 do v ←Get_New(S, C ′ ) if v ==⊥ then idx+ = 1 S idx ← {} end else C ′ , S idx ← Insert(V, α, S idx , C ′ , ℓ yes ) end end return C ′The intuition behind the success of Algorithm 9 is that, for the algorithm to construct large cliques (significantly larger than the cardinality k of the hidden partition), the oracle must return many incorrect answers. We formalize this intuition in Lemma 12.Consider the execution of Algorithm 9. The algorithm will repeatedly construct cliques of -1 queries supported on vertex sets S i , adding elements to S i until all elements of V belong to an equivalence class [u] C ′ for some u ∈ S i . Once this condition is met, the algorithm increments i and initializes S i+1 as the empty set. The following lemma shows that the maximum size of any such set S i constructed by the algorithm is bounded as a function of the true unknown partition size k and the error parameter ℓ no .Consider the set S i constructed by Algorithm 9 while idx = i. We will denote by n i the maximum cardinality attained by this set S i . For convention we will also set n 0 = n. Moreover, we let ℓ i denote the number of false negative responses returned while idx = i. Lemma 12. For any i ≥ 1, we have:EQUATIONProof. Note that, if the hidden partition has cardinality k, and the algorithm obtains a clique of -1 responses on n i vertices, then the number of false negative errors contained in the clique responses is at least the minimum number of within-cluster edges of any k-partition of the complete graph K ni .I.e. a lower bound to the number of false negative errors that must have occurred is given by:ℓ i ≥ min    k j=1 c j 2 c 1 , ..., c k ∈ N, k j=1 c j = n i    ≥ min    k j=1 c j (c j -1) 2 c 1 , ..., c k ∈ R >0 , k j=1 c j = n i    . Note that the function f (x) = x(x-1)2 is convex, and hence by Karamata's Inequality (Theorem 1 from [25] ) the right-hand side above is lower bounded by:ℓ i ≥ k j=1 ni k ni k -1 2 = 1 2 n i n i k -1 .Re-arranging, we find that n 2 i -kn i ≤ 2ℓ i k. Completing the square we obtain:n i - 1 2 k 2 ≤ 2ℓ i k + 1 4 k 2giving:n i - 1 2 k ≤ 2ℓ i k + 1 4 k 2 ≤ 2ℓ i k + 1 2 k,and hence:n i ≤ 2ℓ i k + k, as needed.Crucially, we note that as with Algorithm 5, the partition C ′ maintained by Algorithm 9 is always a refinement of the ground-truth. Lemma 13. Throughout the execution of Algorithm 9, C ′ is always a refinement of the true partition.The proof of this lemma is identical to the proof of Lemma 7. Lemma 14. Algorithm 9 terminates.Proof. We show that Lines 6 and 10 in Algorithm 9 execute finitely many times. This implies termination of the algorithm.Every time Line 6 executes, the value of idx is incremented by 1. Once the value of idx exceeds ℓ no + 1, the while loop in Algorithm 9 exits, and thus Line 6 can only execute finitely many times.To show that Line 10 executes finitely many times, we show that every time Line 10 executes, either C ′ decreases in cardinality or S idx increases in cardinality. This follows from considering Algorithm 7, Insert. On each call to Insert, either result = +1 for some u ∈ S, in which case the cardinality of C ′ is reduced in Line 8, or result = -1 for every u ∈ S. In the latter case, the size of S is increased in Line 13.By Lemma 13, C ′ is always a refinement of C and thus its cardinality cannot decrease more than (n -k) times. Similarly, for each value idx = i, |S i | ≤ n so S i can increase in size finitely many times for each value of idx ∈ [1, ℓ no + 1]. This implies that Line 10 can only execute finitely many times, completing the proof.Lemma 15. When Algorithm 9 terminates C ′ is equal to the ground-truth partition C.Proof. By Lemma 13 C ′ is always a refinement of C. Therefore to show that the partition C ′ returned is equal to C, it remains to show that the cardinality of C ′ upon termination is the true unknown value k.Assume for the sake of contradiction that this does not hold. Once initialized, the only place where C ′ is modified during the execution of Algorithm 9 is in Lines 7 and 8 of Insert. There, the algorithm modifies C ′ by merging two previously disjoint equivalence classes. This reduces the number of disjoint equivalence classes in C ′ , and so in particular the cardinality of C ′ montonically decreases during the execution of Algorithm 9. Thus if upon termination the cardinality of C ′ is strictly greater than k, then this was true at all points during the algorithm's execution.Recall that n i is defined to be the maximum cardinality attained by set S i . In particular, S i attains maximum size when Line 6 of Algorithm 9 is executed. When this happens, S i contains exactly one representative from every cluster in C ′ at the time of execution. If the size of C ′ is strictly greater than k at all points during the execution of Algorithm 9 thenn i > k ∀i ∈ [0, ℓ no + 1].In particular for every value i ∈ [1, ℓ no + 1], for every distinct u, v ∈ S i Algorithm 9 receives at least one response -1 for query (u, v). This response is consistent with the scenario in which u and v belong to disjoint sets in the ground truth partition C. If n i > |C| then at least one of these responses must have been a false negative error. As this holds for every value i ∈ [1, ℓ no + 1], this implies least ℓ no + 1 false negative responses occur during the execution of Algorithm 9. In particular this violates the assumption that α is an (ℓ yes , ℓ no )-faulty oracle, and we thus conclude that the size of C ′ cannot be greater than k upon termination, implying that the partition returned by the algorithm satisfiesC ′ = C.As with the analysis of Algorithm 5, bounding the query complexity of Algorithm 9 reduces to bounding the number of queries with labels 'merge-', 'merge+', 'clique', 'spurious' upon termination of the algorithm.Lemma 16. When Algorithm 9 terminates the history of queries contains at most 1 + √ 2 (ℓ no + 1)k 2 queries labelled 'clique'.Proof. All queries labeled 'clique' upon termination must have been created during the construction of some set S i while idx= i. Given n i the maximum cardinality attained by set S i , the number of 'clique' queries present upon termination that were constructed while idx= i is exactlyn i 2 = 1 2 (n 2 i -n i ) ≤ k 2 + 2k 2kℓ i + 2kℓ i -n iwhere the upperbound follows from Lemma 12 and ℓ i denotes the number of false negative responses returned by the oracle while idx= i. Summing the total number of such queries over all iterates idx= 1, . . . , ℓ no + 1, we obtain:ℓno+1 i=1 n i 2 ≤ 1 2 ℓno+1 i=1 k 2 + 2k 2kℓ i + 2kℓ i -n i = 1 2 (ℓ no + 1)k 2 + √ 2 ℓno+1 i=1 k kℓ i + k ℓno+1 i=1 ℓ i - 1 2 ℓno+1 i=1 n i ≤ 1 2 (ℓ no + 1)k 2 + √ 2k ℓno+1 i=1 ℓ i + k 2 + k ℓno+1 i=1 ℓ i - 1 2 ℓno+1 i=1 n i = 1 2 (ℓ no + 1)k 2 + kℓ no √ 2 + (ℓ no + 1)k 2 √ 2 + kℓ no - 1 2 k(ℓ no + 1).The last line follows by observing that by definition of ℓ i , ℓ+1 i=1 ℓ i ≤ ℓ no . We can simplify the above expression using the fact that for integer k it holds that k ≤ k 2 , to obtain the bound:1 2 (ℓ no + 1)k 2 + kℓ no √ 2 + (ℓ no + 1)k 2 √ 2 + kℓ - 1 2 k(ℓ no + 1) = 1 2 + 1 √ 2 (ℓ no + 1)k 2 + kℓ no ≤ 1 + √ 2 (ℓ no + 1)k 2 .Lemma 17. Upon termination of Algorithm 9, the history of queries contains at most 2 max{ℓ yes , ℓ no } queries labelled 'spurious'.The proof follows analogously to that of Lemma 9. Lemma 18. Upon termination of Algorithm 9, the history of queries contains at most (ℓ yes +1)(n-k) queries labelled 'merge+', and at most(n -k) max (1 + √ 2)k, k + ℓ no √ 2queries labelled 'merge-'.Proof. Similarly to the analysis of Algorithm 5, we analyze the numbers of 'merge+' and 'merge-' queries, by considering merge events. A merge event is defined as the execution of Line 5 in Insert.Recall that n i is define to be the maximum cardinality attained by set S i . In particular, S i attains maximum size when Line 6 of Algorithm 9 is executed. When this happens, S i contains exactly one representative from every cluster in C ′ at the time of execution. Thus n i -n i+1 is equal to the number of clusters merged while idx = (i + 1), i.e. the number of merge events that occurred while idx = (i + 1). Moreover the size of C ′ upon termination of Algorithm 9 is equal to n ℓno+1 , and hence by Lemma 15 n ℓno+1 = k. This impliesℓno i=0 n i -n i+1 = n 0 -n ℓno+1 = n -k.As with the proof of Lemma 8, we note that each 'merge+' query can be charged to a unique merge event in such a way that exactly ℓ yes + 1 'merge+' queries are charged to each merge event. As a result, the number |'merge+ ′ | of 'merge+' queries satisfies:|'merge+ ′ | = ℓno i=0 (ℓ yes + 1)(n i -n i+1 ) = (ℓ + 1)(n -k)Similarly, 'merge-' queries are only created in correspondence with a merge event. Specifically, 'merge-' are created when 'clique' queries are re-labelled as 'merge-'. When idx = (i + 1) on any single execution of Insert, at most one 'clique' query is created for every element in the current set S (i+1) . Hence at most n i+1 'merge-' queries correspond to each merge event that occurs while idx = (i + 1). Summing over all values attained by idx, this implies the total number of queries labeled 'merge-' is bounded by|'merge-′ | ≤ ℓno i=0 n i+1 (n i -n i+1 ) ≤ ℓno i=0 (k + 2kℓ i+1 )(n i -n i+1 ) = k ℓno i=0 (n i -n i+1 ) + √ 2k ℓno i=0 (n i -n i+1 ) ℓ i+1 ,where the second inequality follows from the bound in Lemma 12. Invoking the fact that ℓno i=0 n in i+1 = n -k, we can bound the above and obtain:|'merge-′ | ≤ k • (n -k) + √ 2k • max i ℓ i+1 • ℓno i=0 (n i -n i+1 ) ≤ k + 2kℓ no (n -k) ≤ (n -k) • max (1 + √ 2)k, k + ℓ no √ 2yielding the result.Equipped with the above lemmata, we proceed to prove Theorem 3.Proof of Theorem 3. By Lemmata 14 and 15, Algorithm 9 terminates and returns the correct hidden partition. It thus remains to bound the number of queries made during execution.Let |'merge-′ |, |'merge+ ′ |, |'spurious ′ |, |'clique ′ |be the number of 'merge-', 'merge+', 'spurious' and 'clique' queries made by the algorithm respectively. By Lemmata 16, 17, and 18, the algorithm makes at most|'merge-′ |+|'merge+ ′ | + |'spurious ′ | + |'clique ′ | ≤ (n -k) max (1 + √ 2)k, k + ℓ no √ 2 + (ℓ yes + 1)(n -k) + 2 max{ℓ yes , ℓ no } + (1 + √ 2)(ℓ no + 1)k 2 = O RS u (n, k) + (n -k) max{ℓ yes , ℓ no } + k 2 ℓ no many queries.E.1 Lower bounds for the easy problem: ℓ-false negativesWe prove the following lower bound on the query complexity of the ℓ-PL FN problem. Theorem 19. Every algorithm for the ℓ-PL FN problem which guarantees full recovery of the correct partitions requires RS k (n, k) + Ω(k 2 ℓ) queries in the worst case.Because the ℓ-PL FN problem is no harder than the ℓ-PL problem, this immediately implies the same lower bound on the query complexity of the ℓ-PL problem.To establish this result, we introduce and analyze a game between a Quetionner and a Responder, representing the algorithm and the oracle respectively.Definition of the RUCC FN game. We define the following game, which we call the RUCC FN game. The game is played by two players, the questioner (Q) and the responder (R) and it is parametrized by a finite set V of cardinality n, a positive integer k ∈ {2, ..., n -1}, and a non-negative integer ℓ.The goal of the questioner is to infer a k-partition of V given input from the responder. At the start of the game, we are given a complete undirected graph G 0 on vertex set V . G 0 = (V, E, w + 0 , w - 0 ) has two associated edge weight functions w + 0 : E → R and w - 0 : E → R, both of which are set to zero at the beginning of the game.At each iteration t, the questioner Q submits a query uv for distinct u and v in V . The responder R then issues a response r t ∈ {±1}. If r t = +1, then w + is updated by setting w + t (uv) = w + t-1 (uv)+1. Otherwise, if r t = -1, then w -is updated by setting w - t (uv) = w - t-1 (uv) + 1. We then set G t = (V, E, w + t , w - t ). For any partition C of V , we define the cost:cost FN Gt (C) def = uv∈E u∼ C v w - t (uv) + I    uv∈E u̸ ∼ C v w + t (uv) = 0    ,where I is the convex indicator function. Intuitively, the value of cost FN Gt (C) is the number of incorrect negative (-1) answers that the responder would have to have given if C was the correct partition, or infinity if the responder would have had to given any incorrect positive (+1) answer.We require that the responder must, at each iteration t, reply in a way that guarantees that there exists some k-partition C of V such that:cost FN Gt (C) ≤ ℓ. The game terminates when cost FN Gt (C) is strictly more than ℓ for all but one k-partition C of V , indicating that the responder is left with a single feasible partition and hence they have learned the ground truth. If the game terminates at iteration T , then the payoff to the responder player is T , and the payoff to the questioner is -T . Given a questioner strategy Q and a responder strategy R, we let Game FN (Q, R) be the number of iterations the game lasts when questioner Q plays against responder R, as a function of the parameters n, k and ℓ. The query complexity of the ℓ-PL FN problem is the value:min Q∈Q max R∈R Game FN (Q, R),where Q is the set of all possible questioner strategies and R is the set of all possible responder strategies. A simple argument then shows: Lemma 20. Let f be a non-negative real valued function. If there exists a responder strategy R * such that: ∀n, k, ℓ ∈ N 0 : minQ∈Q Game FN (Q, R * ) ≥ f (n, k, ℓ),then the query complexity of the ℓ-PL FN problem is at least f (n, k, ℓ).Proof. This follows from:min Q∈Q max R∈R Game FN (Q, R) ≥ min Q∈Q Game FN (Q, R * ) ≥ f (n, k, ℓ).In Theorem 23 in Appendix F.1 we show that there exists a responder strategy R * satisfyingmin Q∈Q Game FN (Q, R * ) ≥ (ℓ + 1) k + 1 2 -1 = Ω(ℓk 2 )queries. Lemma 20 and Theorem 23, together with the lower bound of Liu and Mukherjee for the problem without errors [26] immediately imply Theorem 19.We prove the following lower bound on the query complexity of the ℓ-PL FP problem: Theorem 21. Every algorithm for the ℓ-PL FP problem which guarantees exact recovery of the correct partition requires RS k (n, k) + Ω(ℓ(n -k)) queries in the worst case.As in Section E.1, this result immediately implies the same lowerbound for the ℓ-PL problem. In order to analyze the query complexity of learning partitions with ℓ false positives, we consider a very similar game to that defined above in Appendix E.1.Definition of the RUCC FP game. The RUCC FP game is defined with the same setup as the RUCC FN game. The questioner Q, responder R, finite set V , and gameplay graph G t = (V, E, w + t , w - t ) are all defined as in Appendix E.1. The core distinction between the RUCC FP game and the RUCC FN game is the notion of cost employed. For the RUCC FP game, for any partition C of V we define the costcost FP Gt (C) def = uv∈E u̸ ∼ C v w + t (uv) + I    uv∈E u∼ C v w - t (uv)    .Intuitively, the value of cost FP (C) is either the number of incorrect positive answers (+1) that the responder would have to have given if C were the correct partition, or the value is infinity if the responder would have given any incorrect negative (-1) answer.The rules of the game require that at each iteration t, the responder must reply in such a way that guarantees the existence of some k-partition C * of V such that cost FP Gt (C * ) ≤ ℓ. The game terminates when there exists a unique k-partition C * such that cost FP Gt (C * ) ≤ ℓ. The query complexity of the ℓ-PL FP problem can be characterized asmin Q∈Q max R∈R Game FP (Q, R),where Game FP (Q, R) indicates the number of iterations in the RUCC FP game when questioner strategy Q plays against responder R. As in Appendix E.1, this characterization allows us to lower bound the query complexity of the problem by analyzing the RUCC FP game: Lemma 22. Let f be a non-negative real valued function. If there exists a responder strategy R * such that ∀n, k, ℓ ∈ N 0 : minQ∈Q Game FP (Q, R * ) ≥ f (n, k, ℓ)then the query complexity of learning partitions with ℓ false positives is at least f (n, k, ℓ).The proof is entirely analogous to that of Lemma 20.In Theorem 25 from Appendix F.2 we show that there exists a responder strategy R * which satisfies:min Q∈Q Game FP (Q, R * ) ≥ (ℓ + 1)(n -k + 1)) 2 = Ω(ℓ(n -k)).This, together with Lemma 22 immediately implies Theorem 21.F One-sided error lower bounds strategies F.1 A responder strategy for the RUCC FN gameIn this section we show that there exists a responder strategy for the RUCC FN game that guarantees the game lasts at least Ω(ℓk 2 ) iterations. We consider a responder strategy which we call the (k + 1)-groups responder strategy, denoted R (k+1) . In this strategy, the responder fixes an arbitrary (k + 1)-partition of V , denoted C * = {C * i } k+1 i=1 . We define R (k+1) as the responder strategy in which the responder replies consistently with C * whenever the rules of the RUCC FN game allow, i.e. whenever this does not cause the cost of every k-partition to exceed ℓ. We lower bound the number of iterations needed for any questioner strategy to terminate the RUCC FN game when playing against R (k+1) : C ij = {C * a } a∈[k+1]\{i,j} ∪ {C * i ∪ C * j }.We show that the questioner cannot increase the cost of more than one of these partitions C ij on any single iteration (a claim which we prove afterwards):Claim 24. Suppose that cost FN Gt (C ij ) ≤ ℓ. Then on iteration t + 1 the cost of C ij increases only if the questionner submits a query uv for u ∈ C * i and v ∈ C * j .We now prove Theorem 23 using Claim 24. Consider the potential function:EQUATIONNote that, ϕ (0) = 0 and, by Claim 24, at every step t of the game we have:EQUATIONSuppose that the game terminates at iteration T . Then by the rule of the RUCC FN game, for all but one k-partitions C, it must be the case that cost FN G T (C) > ℓ. In particular, all but at most one of the partitions C ij must have cost at least ℓ + 1, implying:EQUATIONto the query {u, v} is +1. Hence, it must be the case that cost FP Gt (C w ) ≥ ℓ + 1 for all such w. Hence, for any w ∈ S * \ {u, v}:EQUATIONOn the other hand, since the responder is replying to the query uv with -1, their answer is simultaneously consistent with both C u and C v . We then have:EQUATIONIn particular, Equations ( 9) and ( 10) directly imply ϕ (t+1) = ϕ (t) .This concludes the proof of Claim 26 (and in turn the proof of Theorem 25).NeurIPS Paper Checklist Guidelines:• The answer NA means that the paper has no 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 (e.g., independence assumptions, noiseless settings, model well-specification, 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 a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness. • 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 acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. Justification: The authors have carefully reviewed the ethics guidelines, and ensured that the papers complies with them fully. 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). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [NA] Justification: The work carried out in this paper is of entirely foundational nature and has no direct path to any negative applications. 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. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.We provide the reader with relevant background from these areas in Section 1.1 and Appendix A.Note that an analogous game can be defined for the k-unknown setting, where chips are equivalent to any partition of V and N is the Bell number Bn.In this paper, we invoke the phrase "graph learning" in reference to problems which seek to exactly recover graph structure by actively making queries to some graph oracle, as opposed to the wide field of problems pertaining to learning graphs from data, which often focus on approximate or probabilistic results (i.e. such topics as surveyed by[38]). 
 
 Appendix:  


Decision: The reviewers are generally positive about this paper. The query complexity of finding a partition with faulty oracle is a well-motivated problem. However, there is concern regarding how the results are presented and the thoroughness of literature review. In fact, the persistent query model is strictly harder to handle than the non-persistent model in the case of random independent errors. The authors should elaborate if that remains true for the case for the adversarial error model. The reference to practitioners here is quite misleading in this context. Is it possible to do a comparison with Mazumdar and Saha ([31] in the paper) to show the "adversarial error" query complexity is different from "random error" query complexity? In general there is a quite substantial literature on same-cluster queries (eg. multiple papers by Mazumdar and Saha, Chien et al) - it would be useful to include a discussion on and comparison to this literature.

Reviews: review: paper_summary: paper_summary: This paper studies the query complexity of clustering with a faulty oracle. Given a set of $n$ points $V$, which is partitioned into $k$ hidden clusters, the learner wants to recover the hidden partition by querying whether two points are in the same clusters or not. There has been a line of work that studies the query complexity of the problem where the response of each query has iid error. This paper studies a different query model, where the learner is allowed to make repeat queries for the same pair of points but the responses could be adversarially flipped at most $\ell$ times. This paper provides lower bounds for the query complexity of several variants of the problem and also designs efficient learning algorithms with a query complexity matching the lower bound.
strength_weakness: strength_weakness: My main concern is about the significance of the learning model studied in the paper.
For graph clustering problems, the error is usually defined over the graph instead of over the queries, and sometimes repeated queries are not allowed. This is because sometimes by allowing the use of repeated queries, the learning problem could be easy to solve. For example, when iid noise is presented.
In this paper, the error is defined over an unbounded sequence of queries but only allows a constant number of mistakes to happen. In particular, knowing the number of mistakes seems to be very important to make the learning algorithm designed in this paper work. These two points seem to be too idealized to model problems that arise from real applications.
questions: questions: My questions are about the weakness pointed out above.
1. Can you provide any real applications that motivated the study of such a learning model? (Only a constant number of mistakes are made over the queries and such a number is known)
2. How would the learner know the error parameter $\ell$ in advance and if we do not have the parameter $\ell$ as input would it be possible to achieve exact recovery?
3. If repeated queries are not allowed and the mistakes are placed by an adversary, would it still be possible to (almost) recover the underlying clusters?
limitations: limitations: N/A
paper_summary: paper_summary: The paper studies the problem of finding a hidden partition into $k$ clusters of a given universe.
In many applications an algorithm has only access to a same-cluster oracle. A query to this oracle reveals whether two elements belong to the same cluster or not. This problem has been previously studied and tight bounds on the query complexity, i.e., the minimal number of queries required to solve the problem, are known (Reyzin and Srivastava, and Liu and Mukherjee).
In this paper, the authors add the realistic assumption that the same-cluster oracle may not always reveal the correct answer. In their model, they (in advance) set a number \ell which bounds the maximum number of wrong answers which the oracle is allowed to make. The goal of an algorithm is still to compute the hidden cluster with as few queries as possible. In particular, for the same tuple of elements the oracle may give different answers for different oracle calls, and the algorithm does not receive any information on whether the response of the oracle was correct or not. The authors present an algorithm and analyze its query complexity. This bound is generally larger than in the setting with a correct oracle, and depends on the parameter \ell. If \ell=0, the presented analysis recovers the results by Reyzin and Srivastava. Furthermore, they give a tight lower bound using an argumentation based on Renyi-Ulam games and correlation clustering.
They moreover study a slightly more general setting where the algorithm can set in advance more fine-grained bounds on how many false positive and false negative answers the oracle can give, and, for all problems they consider both, the setting where the number of hidden clusters k is known or not.
strength_weakness: strength_weakness: - I think the main weakness of the model is that the upper bound \ell on the number of faulty oracle responses must be set in advance and stays fixed. This could be a major drawback when applying this model and the algorithm in practice, because it seems not clear why a faulty oracle should be consistent with such a bound. 
- It seems that the main algorithms is quite similar to the algorithm without faulty oracle. I think it would be helpful for the reader to have a paragraph where the difference to this original algorithm is explained. 

Further comments:
- Line 236: missing 'and'
questions: questions: Is there anything known for the setting where the number \ell is unknown to the algorithm, and it only appears in the analysis? I.e. a strong lower bound or an obvious workaround? Such insights or discussions could make the main weakness less severe.
limitations: limitations: Limitations have been addressed.
paper_summary: paper_summary: **[Setting]**:
This paper studies the problem of clustering n items into k clusters using an oracle that adversarially answers same-cluster queries for item pairs under the constraint that it makes at most $\ell$ errors for a known constant $\ell$. The goal is to exactly recover all clusters always (instead of just w.h.p.).

**[Contributions]**:
1. A lower bound on the number of queries when k is known/unknown. The authors formulate the problem in terms of Chip-Liar game to get this result.
2. For known k, an algorithm that iteratively merges cluster using two heuristics:
    1. If there is a (k+1)-clique of all -1s then the oracle has returned at least one false negative
    2. More than $\ell$ "+1" responses from oracle for a given pair guarantees that it is in the same cluster
3. Sample complexity of the proposed algorithm that matches the lower bound.

The results extend to a more general problem where individual limits on false positive and false negative errors are known.

The paper also studies an algorithm for k-unknown case in the appendix. Sample complexity in this case is not optimal.
strength_weakness: strength_weakness: 1. The problem setting (oracle making at most $\ell$ errors with $\ell$ being a known constant) is not very practical in my opinion, which in-turn makes it hard to judge the significance of the results. Even for the examples given in the paper (L23-32), it is not clear why the oracle will make at most $\ell$ errors (e.g., an experiment failing in bioinformatics) or why $\ell$ will be known in advance. Do the authors have concrete applications in mind?
2. Clarity-wise, while the details in the paper are mostly clear, it would be helpful to include more details from the appendix into the main paper. For example, the following can be included by making Section 3 more concise,
    1. What does "The position of a chip on the board will then be equal to the cost of the corresponding partition .." (L234-235) mean?
    2. Some high-level details about the unknown-k algorithm.
    3. Some intuition about why false-negative and false-positive error budgets inherently have a different contribution towards minimum sample complexity
questions: questions: Please respond to point 1 under weakness


**Minor suggestions**:
1. Typo in L100 - "A many" -> "Many" 
2. A more recent paper (Gupta et al. 2024) studies a more general setting than Chen et al. (2023), which is closest to your work.


Gupta et al. Clustering Items From Adaptively Collected Inconsistent Feedback - AISTATS, 2024
limitations: limitations: Yes
paper_summary: paper_summary: This paper studies the problem to recover an exact $k$ partition of a set with access to a same-cluster oracle that is allowed to lie $\ell$ times. This papers gives an algorithm with optimal query complexity up to constants and a lower bound.
strength_weakness: strength_weakness: I'm very satisfied with this paper, just two things I think it can improve on the writing.

1. The algorithm is quite simple and intuitive. On the other hand, the lower bound is more complicated and more technical. I think it might be better to write less on the algorithm but explain more on the lower bound, especially how to construct a good responder's strategy.

2. I think it's worth mentioning what's the optimal algorithm for the no-error oracle and compare your algorithm with theirs. 

Also something I would not like to call it a weakness since I think it's beyond the scope of the paper:

1.  You justified the inconsistent error assumption (but I think the consistent error assumption can also be justified). But from the pure theoretical point of view, this assumption does make the algorithm design a lot easier and less interesting since the algorithm can make the same query many times. If the error model prevents such behavior of the algorithm, it is more interesting.
questions: questions: 1. Is it possible to get better query complexity bounds if the goal is to recover the partition approximately but not exactly?

2. I mentioned consistent error above. I'm also thinking a more generalized adversarial error where it could be stochastic, for example, the expected number of error is $\ell$. Does stochasticity makes things harder?
limitations: limitations: The limitation of the paper is well addressed.

Comments: title: Response to Rebuttal
comment: Dear Authors,
Thanks for all the clarifications you have provided so far. The paper is an enjoyable read. Is it possible to do a comparison with Mazumdar and Saha ([31] in the paper) to show the "adversarial error" query complexity is different from "random error" query complexity? Also the persistent query model is strictly harder to handle than the non-persistent model in the case of random independent errors. Is that the case for (your) adversarial error model? The reference to practitioners here is quite misleading in this context.

I general there is a quite substantial literature on same-cluster queries (eg. multiple papers by Mazumdar and Saha, Chien et al) - it would be useful to include a discussion on this literature.   

AC
Thank you for responding to my questions. I very much appreciate the added motivation and applications. Consequently, I have increased my score from 4 to 6. All the best for your submission ! :)
I thank the authors for their rebuttal. 

As far as I undernstand, there is still a major limitation to the result (at least for the k-known setting) because an algorithm requires to know $\ell$ upfront (expect that in the weighted setting $\ell_{no}$ can be unknown), which I think is not very realistic. I see that, in the k-unknown setting, there is a strong theorical lower bound, and I appreciate that you provided it. Overall, my opinion about the paper and my score remains: The paper has some nice insights and results, but also a major limitation to the model.
Thanks for spending time making the response. I would like to keep my score.
Thank you for your response! I hope to see this paper at NeurIPS 2024!