Optimal Algorithms for Learning Partitions with Faulty Oracles
Authors: Adela Frances DePavia
Olga Medrano Martín del Campo
Erasmo Tani
Venue: NeurIPS 2024 poster (2024)
Keywords: clustering; error tolerant; partitions; query complexity; oracle advice; graph learning; active learning
Primary area: learning_theory
TL;DR: We design algorithms for the problem of learning partitions from faulty same-cluster oracle queries and prove that they achieve optimal query complexity.

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.

Optimal Algorithms for Learning Partitions with Faulty Oracles
Adela Frances DePavia University of Chicago adepavia@uchicago. edu
Olga Medrano Martín del Campo University of Chicago omedrranomdellcchhhhcc...oo
Erasmo Tani University of Chicago
etani cagni edu edu
Abstract
We consider clustering problem where learner seeks to partition finite set by querying faulty oracle. This models applications where learners crowdsource information from non-expert human workers or conduct noisy experiments determine group structure. The learner aims to exactly recover partition by submitting queries of the form "are and in the same group?" for any pair of elements and v in the set. Moreover, because the learner only has access 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 l answers are incorrect, for some error-tolerance parameter We study the question: for any given error-tolerance É, what is the minimum number of queries needed to learn a finite set partition of n elements into 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 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.
Introduction
Learning cluster structure from data 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. several scientific domains, particularly bioinformatics, researchers conduct physical experiments to learn whether two objects are part of the same class (9 11 20 355.
Another major application is learning cluster structure by collecting information from human workers via crowdsourcing services [15] 30 37.. While some traditional methods focus 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 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 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 same-cluster oracle. In this setting, the leamnrr obtains information about hidden partition C of finite set V by repeatedly choosing two elements u, E V and asking questions of the form "Are
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

and e part of the same cluster?", i.e. given C and V, a same-cluster oracle is an oracle ag that takes as imput u and v in V. and returns if and 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
26
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 achieve exact recovery of the underlying partition. However, existing theory either focuses on the error-free or focuses on probabilistic guarantees regime 226 33 assumes that errors are persistent [16 32
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-tolerane recovery of the hidden partition as long as the eπror incurred is within this tolerance. In particular, we say a same-cluster oracle ac is E-faulty if it may return an incorrect answer up to e times. We do not assume that errors are persistent: if a single pair of elements is queried repeatedly, an f-faulty oracle may return inconsistent responses. We define the f-bounded error partition learning (f-PL. problem, as the problem of exactly recovering a hidden partition via access to an f-faulty same-cluster oracle.
parameter É, and they require guaranteed full
We design algorithms for the E-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 the query complexity of the E-PL problem. We then use this game as framework to give tight lower bounds for the query complexity of this task, proving the proposed algorithms are optimal.
We find that the f-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-Ulan liar games]] We are hopeful that the impact of these connections will go beyond the results presented in this paper.
1.1 Background and related results
Clustering with same-cluster oracles In the error-free regime, Liu and Mukherjee (66 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 complexity.
33 exactly achieves this query
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 casier 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-clusted oracles in the presence of persistent i.i.d. errors. They point out that under these assumptions, learning a partition has strong relationship to recovering community structure in the stochastic block model (SBM). This work inspired 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 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
[22] when the underlying clusters are nearly-balanced
We provide the reader with relevant background from these areas in Section 1.1 and Appendix A

---

error have also been considered. Chen et al. [15] study same-cluster queries in the presence of ii.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 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.
Rényi-Ulam games In his autobiography, Stanislaw Ulam, introduced the following two-player game [36.. One player (the responder) thinks of number in z E [N] for some N E 1,, 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. (3I). The question of finding the worst-case query complexity of the É-PL problem can be naturally formulated as a Rényi- -lammmmmmmm 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, o), where o: E - }+1} is 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 a. The problem is known to be NP-Hard. Many variations of problem have been proposed, including versions with weighted edges 22] 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 (2729)
1.2 Discussion of the Model
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 result of Reyzin and Srivastava (this is 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 the queries are persistent, it is impossible to solve the problem even for small constant values of of & [1] Furthermore, this implies that even in the non-persistent error- mroee,, one cannot solve the problem for a value of E that grows linearly with n. Below, we give two general motivating examples, in the technology and scientific domains respectively, illustrating the role of l in partition learning tasks.
Example 1: Robustness to Misinformation Consider setting where a user is trying to cluster a dataset by crowdsoureing 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 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 E-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 fixed security parameter L.
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 Gupta et al. 23 The scientist has limited resources (e.g. limited materials or time) and can only conduct 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 as
3

---

QUERY COMPLEXITY
k-KNOWN
K-UNKNOWN
WEIGHTED E-PL AND
2 (RS (ne,
O (n, (n k) max fno) + k90)
(THM.
(n - k) + +xo
E-PL (COR. AND
(RS (n, k)e+ kje+
θ (RS (n," -)e (m
THM. 5
4-PL. AND 19
(RS (m,
e (RS (n)
(THM.
A-PL. FP
(RS* (n, + (n k)))
e (n, k)E)
(THM. AND 21
ERROR-FREE
RS* (m,
RS (n. k)
(RESULTS FROM 26 33
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 E-PL problem match the lower bound (given for the k-unknown case) exactly. The results are given in terms of the complexity RS* (n, k) and (SS(n, k) (defined Equations |and 2b of solving the problem without errors.
k-unknown setting, for which the upper bound does not
the setting for É, and then use our algorithms to guide their choice of experiments. Our analysis would then allow them to measure significance of their findings by quantifying the number of experiments that would need to have failed for the finding to be incorrect.
2 Technical preliminaries
Basic definitions Given a positive integer n we denote with [n] the set [1...., n3.
Given any finite
set V we denote with ( the set {{i V i j}. graph G (V, E)) is a pair containing a
finite vertex set V and subset F. C (2) Given a finite set V k-partition of V is a collection of k pairwise disjoint non-empty subsets by the cardinality [/] of V and may assume without loss of generality that V [ni]. Given two elements u and of V, we write u <e v (resp. u Ac v) for the statement 3C E C, [u, v} C (resp.2 C C, C,fu, v) C C). We denote by [u]c the equivalence class of with respect to C, i.. Julc the unique C' E C containing u. Given two partitions C1 and C2 we say C2 a refinement of C₁ for every C C2 there is C' C1 such that C C'.
(Ci, } of V such that U C. = V.
will denote
3 A hierarchy of problems
In the introduction we consider learning a partition C of a finite set 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 E-PL problem. We characterize the hardness of the {-PL problem by considering a family of related tasks. In particular, we introduce hierarchy of problems with different degrees of difficulty (see Figure [ and establish matching upper lower bounds in nearly all of these tasks. We summarize results in Table
At the bottom of the hierarchy, we have the problem first studied by Reyzin and Srivastava 3 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:
RS (n, k) = nlkk 1)
(1)
many queries when the number & of clusters is known to learner and:
RS k) nk ( 2
1
(2)
when & 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) (resp. RS (n, k)) queries when & 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 "casiest" 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 emror. In the first variant, which we refer to as the E-bounded error partition learning with false positives (P-PL")) problem, the oracle might return the answer +1 even when 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 f, and always return -1 when the two elements being queried are not part of the same cluster.
In the second variant, which we refer to the E-PL problem, the oracle behaves the opposite way, and may return 11 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 false positive answer. Similarly to the previous variant, we restrict the number of false negative answers to be at most some fixed l. We give precise definitions of the (-PL_FP and F-PL, problems below.
The 6-PI. problem then a generalization of 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 E-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 more fine-grained problem, which allows false positive answers and false negative answers to incur different penalties. In particular consider weighted version of É-PL, which is formalized in the following definition:
Definition 1 (Cys --Fultyy Oracle and Weighted 4-PL Problem). Let V be finite set, and C be a partition of V. A (fyes. -fautyy oracle for C is an algorithm ae which, given as input pair of elements ue, returns value r =E {=1} so that for any sequence of queries (ueeeheerr the sequence of responses (rz- (c(uu)))) satisfies:
Kt de ve Are +1H1
Kt : ue ~e U1 Art - -1 11
Eyes
Pno
Note that we assume the oracle can maintain an internal state, so its answers may depend on the query history. The weighted E-PL problem asks one to recover an unknown k-partition of V given access to an (Cyez; Lo -faulyy oracle for C.
Observe that by setting lyos < (resp. lo < 1) one would require the oracle not return any false positive (resp. false negative) answer. As convention, we will write Eyes 0 or e.o = 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 Eyan and Eno by factor of 2, this problem is equivalent to 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) 2-PL can be cast homogeneous version of the above, one in which Eyes = Lno. as follows:
Definition 2 (E-Faulty Oracle and 2-PI. Problem). f-faulty oracle is an (f, f)-faulty oracle. The (-PL problem is the problem of learning partition with access to f-faulty oracle.
The E-PI.EP FP and E- FM problems discussed above can now be formally described as special instances of the weighted (-PL problem.
5

---

Algorithms
Lower bounds
E-PL
Learning Partitions (No errors)
WEIGHTED i - PL
{ PL
F-PL
Figure 1: The lattice of problems considered in this paper. Algorithmic results propagate from left to right while lower bound results propagate right to left.
Definition 3 FL-PI.F Problem and FM Problem). The E-PI. problem is the problem of learning partition with access to an (f, 0)-faulty oracle. Intuitively, this corresponds to the problem of learning partitions subject
most false-positive responses and no false negatives. The 2-PL problem the problem of learning partition with access to an (0, f)-faulty oracle. This corresponds to learning partitions subject at most felse-negatives responses and no false positives.
In the rest of the paper, we will always assume that the set V. its cardinality n, and the parameters (fyes, ( are known to the learner. We will consider both the k-known setting, in which the number clusters is known to learner, and the k-unknown setting, which 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 the k-known setting, since any learning algorithm could simply ignore the value of 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 [ 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 Coo 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 occur, one does not need to set any upper bound on the error at all. contrast in the k-unknown setting, in order to achieve the bound described in Theorem 3 Jour proposed algorithm does require user-chosen value for Lno- Here, a simple argument shows that it is impossible to guarantee one has found the correct answer unless they can upper bound both Lyos and Loo.
4 Algorithmic results
Our first result is an algorithm for the weighted E-PL problem in the k-known setting. Theorem There exists an algorithm for the weighted E-PL. problem which recovers the full partition in the k-known setting with query complexity bounded by
ORS (n, k) (n k) k k=o))
We observe an asymmetry in the dependence on Eyea and eno respectively, indicating that false- negative 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 in Section Throughout the paper, when considering the k-known setting, we shall assume that & (1, for otherwise the problem is trivially solved without the need to query the oracle. Because the weighted É-PI. problem generalizes the (-PI. problem, this yields algorithm for the (-PL problem as well:

---

There exists algorithu for the E.PLproblen which learns the correct partition in the k-known setting with query complexity bounded by
Corollary 2.
ORRS (n, +
(m (n
k)) (m-
k²t).
As our final algorithmic result, in Section D we show that the algorithm can be adapted to obtain optimal asymptotic performance for the f-PL problem in the k-unknown setting.
Theorem 3. There exists an algorithun for the weighted E-PL problem which recovers the full partition C in the k-unknown setting with query complexity bounded by
O (RS (n, k) + +(n -) max (no) k2 kno)
An immediate corollary bounds the query complexity of the E-PL. problem in the k-unknown setting. Corollary There exists an algorithm for the E-PL problem which learns the correct partition the k-unknown setting with query complexity bounded by
O (RS (n, k) + e(n k:) h2().
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 only small constant factor away from the lower bounds, and we give the exact upper bounds in Section D where we prove Theorem
5 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,... L. At the start of the game, all of the chips begin position 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 position of every chip in S by 1, or increase the position of every chip in S by 1. If chip at position & group whose position is advanced, the chip is said to have naveffllen fallen off the board. After this point such chips will no longer advance. The rules of the game constrain It's responses; R must ensure that on every round, at least one chip remains on the board at position i s L. The game terminates when there is a unique chip remaining on the board.
of the following moves: they
either increase the
Note that one can think of the f-PL. problem as a constrained version of this Chip-Liar game. In the k-known setting") 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 = ["] Moreover, unlike the general Chip-Liar game, in setup the questioner may only select specific subsets S: for any pair of elements u, u V, the questioner can select 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 he made by the questioner together with the signs given by the responses the queries as making up an instance of the correlation clustering problem. The position of a chip the board will then be equal the cost of the corresponding partition as a solution of the correlation clustering instance constructed. In Appendix E. and Appendix E.2 we formalize this intuition by defining Rényi- Rényi-Ulam Correlation Clustering (RUCC) games, which are the key tools we use lower bound query complexity.
Leveraging the above techniques, we lower bound the query complexity of the (-PL FK and 4-P1. problems. Combining these lower bounds with results in the error-free regime yield the following lower bounds on the (-PL problem.
Note that analogous game can be defined for the k-unknown setting, where chips are equivalent to partition of V and N is the Bell number Bn.
7

---

Theorem 5. Every algorithm for the E-PL problem requires at least:
(m k), (n - E))
queries both in the k-known and in the k-unknown setting. Moreover every algorithm for the weighted (-PL problem requires at least: Smmmx ( (n, k), Cys((n k), knck²))
queries both in the k-known and in the k-unknown setting. Here RS(n, k)) represents RS (n, k) in the k-known setting, and RS" (n, k) in the k-unknown setring.
This theorem is a corollary of Theorems 19 and 21 which we prove in Appendix F.I and Appendix F.2
observe between the case of false negative errors and the case false positive errors is due to the following. On one hand, certifying the existence of k-clusters using positive answers requires building spanning forest, which has (n k) edges. On the other hand, accomplishing the same task using negative answers requires constructing a clique on A vertices which requires (k-)) edges. This intuition is made precise in Section E in the proofs of Theorem 19 and respectively.
Intuitively, the difference in complexity
Algorithm for weighted (-PL with k-knnown
In this section 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 e 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) cllliquess of - responses. If at any point the oracle responses form such a clique, then negatine response must have occurred, as vertices in V belong to at most &o distinct clusters (note that & is assumed to be known to the algorithm). In this case, the algorithm has certified a felse-ne 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 we. However, such positive response received, repeatedly querying the pair we will either quickly determine that u and must be part of the same cluster or it will reveal that error has occurred. In the first case, the algorithm makes progress towards learning C, and in the second case 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_ Insert and Compare:
Learn This the core component of the algorithm. maintains a partition C' for V. Throughout the algorithm, C' is guaranteed to be refinement of the true hidden partition C. C' is initialized as the set of singletons for every element V. The algorithm then repeatedly tries to construct a clique of negative answers, supported on some set S C 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 C V and C' partition of V. Get Net_New returns an element E V\S representing a cluster in C' that's not yet represented in S, i.e. u g [u]er for any S.
Insert Given an element and subset S C V, Insert compares v against every element in S by passing u and e to the function Compare. Compare returns resulte [+1]. Compare returns a negative result for each E S, then Insert adds v to the subset S. On the other hand, if Compare returns a positive result for e and some element u E S, then Insert updates the partition C' reflect that u and e must be in the same cluster. The latter is done by merging [u]er with [v]e.
8

---

Given two vertices u and v, Compare repeatedly submits query wo 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, returns result=
Compare
Algorithm 1: Learn (V, a, h; Eyes)
Input: finite V, an (Cyes: (n (no)--aultyy oracle ac, a target number of clusters k, and error parameters Eyee.
Output: partition C' of V.
S + ().C' < {10} |
2 while C*I > do
Ge-Get_Ne((S,
C. + Insert(V, S, C" kyea)
if S| k +11 then
5
end
end
return C'
Algorithm 2: Get "ett_New(S,C))
Input: A partition C' of some finite set V, and a subset C V such that |S| S |C'| Output: An element E representing set in C' which is currently represented by any element of S.
for E V do
if' [v]c n S = @ then
return
end
5 end
return
Algorithm 3: Insert(v, C"', S,
Input: A finite set V,a , same-cluster oracle a for V. a partial clique S, candidate partition of V, and error parameter lyes.
Output: A new candidate cluster C', partial clique S.
for E S do
// Returns either result = -1 +1
result t- Compare (u, v, at Eyea)
I/ +1: it is guaranteed that u and v are part of the same cluster and C' is edited to reflect this result +1 then
new new_set + [ule U fule
C' t (C' (ule [ule:] net_set
return C²
end
10 end
// If is empty or if result -1 for every S then item is inserted into S 12 S (u) return S
We briefly remark that for the k-unkknwwn 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 :: + 1, Algorithm builds the largest clique possible. We then give charging argument that shows that this strategy does not lead a significantly higher query complexity. The algorithm and analysis are presented in Section D

---

Algorithm 4: Compare a, Lyes)
Input: A pair of vertices u and u from some finite set V, a same-cluster oracle a for V, and error parameter yeas.
Output: result E {
// Initialize count track "how many more times have observed compared to -= 1-
count
while count 2 do
r a(. v)
if r 1 and count> ( then count count-
else if
and count= 0 then
If the number responses exceeds the number of responses seen so far, we return -
return -1
else 10
11
count count++
12
end
13
// If count/lyes' > 1 then we have verified that ~c. so return result = +1
14
count/lyes 3 then
return 1 end 16
15
end
7 Conclusions, Limitations, and Future Directions
In this paper initiated the study of learning partitions from same-cluster queries subject bounded adversarial errors. We completely characterize the query complexity of the core problem as well of its relevant variants. To do so, introduce novel Rényi-Ulan style game based correlation clustering.
The aim of this paper is to resolve the query complexity of exact recovery with fixed error tolerance. In particular, the results in this paper do not apply to any setting which the error may exceed the tolerance f, e.g. when errors occur probabilistically and independently 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-end codes, results in this paper should be assumed to hold verbatim in stochastic error settings.
every query. This limitation
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 the k--noww setting, the exact complexity of weighted É-PL. problem in the setting of k-unknown remains to be determined. Specifically, the lower bounds of (2))2 and Ω((n - Cye)) 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 eo + (n k) max{fyes. ).. The question of whether the upper bounds can be tightened to Okk + (n ka)) or whether the corresponding lower bound can be strengthened to e.g. (((n - k) max maxx(fyes )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- coleepposssives Eyee. is not known to the algorithm priori. In this work established that such algorithms exist without knowing en advance, but is unclear whether Eyea 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 worker asked to input 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.
10

---

Acknowledgements. The authors wish to thank Daniel Di Benedetto for providing helpful advice early on the project; Yibo Jiang for suggesting related work: Mark Olson, Angela Wang, and Nathan Waniorek for useful discussions. AD is supported by NSF DGE 2140001.
References
[1] H. Abasi and B. Nader. On learning graphs with edge-detecting queries. In Algorithmic Learning Theory, pages 3-30. PMLR, 2019.
[2] N. Ailon, M. Charikar, and A. Newman. Aggregating inconsistent information: ranking and clustering. Journal of the ACM (JACM), 55(5):1-27, 2008.
[3] N. Ailon, A. Bhattacharya, and R. Jaiswal. Approximate correlation clustering using same- cluster queries. In LATIN 2018: Theoretical Informatics: 13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings, pages 14-27. Springer, 2018.
[4] N. Alon and V. Asodi. Learning hidden subgraph. SIAM Journal Discrete Mathematics, 18 (4):697-712, 2005.
[5] N. Alon and J. H. Spencer. The probabilistic method. John Wiley & Sons, 2016.
[6] N. Alon, R. Beigel, S. Kasif, S. Rudich, and B. Sudakov. Learning a hidden matching. SIAM Journal Computing, 33(2):487-501, 2004.
[7] D. Angluin and Chen. Learning hidden graph using (logn) queries per edge. Journal of Computer and System Sciences, 74(4):546 556, 2008.
[8] H. Ashtiani, S. Kushagra, and S. Ben-David. Clustering with same-cluster queries. Advances in neural information processing systems, 29, 2016.
[9] D. Balding, W. Bruno, D. Torney, and E. Knill. A comparative survey of non-adaptive pooling designs. In Genetic mapping and DNA sequencing, pages 133-154. Springer, 1996.
[10] N. Bansal, A. Blum, and S. Chawla. Correlation clustering. In The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., pages 238-247, IEEE, 2002.
[11] M. Bouvel, V. Grebinski, and G. Kucherov. Combinatorial search on graphs motivated by bioinformatics applications: A brief survey, In Graph-Theoretic Concepts in Computer Science: 31 International Workshop, WG 2005, Metz, France, June 23-25, 2005, Revised Selected Papers 31, pages 16-27. Springer, 2005.
[12] M. Bressan, N. Cesa-Bianchi, Lattanzi, and A. Paudice. Exact recovery of mangled clusters with same-cluster queries. Advances in Neural Information Processing Systems, 33:9324-933 2020.
[13] M. Bressan, Cesa-Bianchi, S. Lattanzi, and A. Paudice. On margin- based cluster recovery with oracle queries. Advances in Neural Information Processing Systems, 2021.
[14] H. Chang, H.-L. Fu, and C.-H. Shih. Learning a hidden graph. Optimization Letters, 2341-2345 2014.
[15] Y. Chen, R. K. Vinayak, and B. Hassibi. Crowdsoureed clustering via active querying: Practical algorithm with theoretical guarantees. In Proceedings of the AAAI Conference on Human Computation and Crowdsourcing, volume 11, pages 27-37, 2023.
[16] A. Del Pia, M. Ma, and C. Tzamos. Clustering with queries under semi-random noise. In Conference on Learning Theory, pages
PMLR, 2022.
[17] E. D. Demaine, D. Emanuel, A. Fiat, and N. Immorlica. Correlation clustering in general weighted graphs. Theoretical Computer Science, 361(2-3):172-185 2006.
[18] A. DePavia, M. M. del Campo, and Tani. Error-tolerant exact query learning of finite set partitions with same-cluster oracle. arXiv preprint 24242 2023.
11

---

[19] I. Giotis and V. Guruswami. Correlation clustering with a fixed number of clusters. Theory OF Computing, 2:249- 266. 2006.
[20] V. Grebinski and G. Kucherov. Reconstructing a hamiltonian cycle by querying the graph: Application dna physical mapping. Discrete Applied Mathemalics, (8(1-3):147-165, 1998.
[21] V. Grebinski and G. Kucherov. Optimal reconstruction of graphs under the additive model. Algorithmica, 28: 1011004-22 124, 2000.
[22] K. Green Larsen, M. Mitzenmacher, and C. Tsourakakis. Clustering with faulty oracle. In Proceedings of The Web Conference 2020, pages 2831-2833 2020.
[23] S. Gupta, P. W. Staar, and C. de Sainte Marie. Clustering items from adaptively collected inconsistent feedback. In International Conference on Artificial Intelligence and Statistics, pages 604-612. PMLR, 2024.
[24] V. Guruswami, A. Atri Rudra, and M. Sudan. Essential coding theory, Oct 2023. URL https://cse. buffalo. buffall
[25] Z. Kadelburg. Dukie, M. Lukic, and I. Matic. Inequalities of karamata, schur and muirhead, and some applications. The Teaching of Mathematics, 8(1):31-45, 2005.
[26] X. Liu and S. Mukherjee. Tight query complexity bounds for learning graph partitions. In Conference on Learning Theory, pages 167-181. PMLR, 2022.
[27] K. Makarychev, Y. Makarychev, and A. Vijayaraghavan. Bilu-linial stable instances of max cut and minimum multiway cut. In Proceedings of the twenty-fifth anmual ACM-SIAM symposium on Discrete algorithms, pages 890-906. SIAM, 2014.
[28] K. Makarychev, Y. Makarychev, and A. Vijayaraghavan. Correlation clustering with noisy partial information. In Conference on Learning Thheory, pages 1321-1342. PMLR, 2015.
[29] C. Mathieu and W. Schudy. Correlation clustering with noisy input. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 712-728. SIAM, 2010.
[30] A. Mazumdar and B. Saha. Clustering with noisy queries. Advances in Neural Information Processing Systems, 30, 2017.
[31] A. Pelc. Searching games with errors-fifty years of coping with liars. Theoretical Computer Science, 270(1-2):71 2002.
[32] Peng and J. Zhang. Towards a query-optimal and time-efficient algorithm for clustering with a faulty oracle. In Conference on Learning Theory, pages 3662-3680. PMLR, 2021.
[33] L. Reyzin and N. Srivastava. Learning and verifying graphs using queries with focus edge counting. International Conference on Algorithmic Learning Theory, page 285-297, 2007.
[34] B. Saha and S. Subramanian. Correlation clustering with same-cluster queries bounded by optimal cost. arXiv preprint arXiv:1906 04976, 2019.
[35] A. Sorokin, A. Lapidus, V. Capuano, N. Galleron, P. Pujic, and S. D. Ehrlich. A new approach using multiplex long accurate per and yeast artificial chromosomes for bacterial chromosome mapping and sequencing. Genome research, 6(5):448443, 1996.
[36] S. M. Ulam. Adventures of Mathematician. Univ of Californa Press, 1991.
[37] R. Vinayak and B. Hassibi. Crowdsourced clustering: Querying edges vs triangles. Advances in Neural Information Processing Systems, 29, 2016.
[38] Xia, K. Sun, S. Yu, A. Aziz, L. Wan, S. Pan, and H. Liu. Graph learning: A survey. IEEE Transactions on Artificial Intelligence, 2(2):109-127, apr 2021. doi: 10.1109/hai200213377700.. URL https:://dl: org/ w11.:2/.11..1......... 2021 3076021
12

---

A Additional relevant background
Comparison of random and adversarial error Most of the prior work on clustering with faulty same-cluster queries focuses on the random-errol model. Different models of random error have been considered. The most similar works to this paper are the papers of Gupta et 23 and Chen et al. [[3]. These papers consider non pen-psisttent random error. In this setting, the best known upper bounds on the query complexity of partition learning are
Ô 0 nuk f(p)
where p is the probability of error and f is some function that tends to 0 as p + 1/2 [13 23]. 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 L. Instead in the setting of adversarial error, query complexity bounds scale with (n + k²) -
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 series of followup works in this setting [16 [2]. For this problem, upper and lower bounds which match up 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
Ω
(1 (T-2p)) 2p)
queries. They further give a tüme-inefficient algorithm which recovers the maximum-likelihood clustering estimate with high probability when p < 1/2, using
nkk log(n) o
(1 2p)
queries 30 In particular, while piori the persistent-error versions of the problem can be easier than the non-persistent-error ones, we are not aware of any result that shows a gap query complexity between these two different settings.
We note that a model imposing persistent adversarial error does not allow for any non-trivial algorith- mic 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 Numerous settings have been considered in the literature, including instances where the target graphs are matchings (6) stars 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 [4 21 In a related paper, Reyzin and Srivastava [33] give an algorithm that learns the partitions of 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 graph with vertices using Ologg 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 partition of [n] into k clusters in the same-cluster query model is exactly n(k 1) (+) if k is known by the learner a priori, and nk (*+)) 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-ting time algorithm for k-means clustering under certain geometric assumptions. In recent
IIn this paper, we invoke the phrase "graph learning" in reference 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 surveyed by (38).
13

---

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. [22 [6]). Ailon al. [3] show that making a small number of queries to same-cluster oracle allows one to improve exponentially the dependency on the approximation parameter E and on the number k of clusters for polynomial time approximation
schemes for some versions of correlation clustering. Saha and Subramanian [ 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.
B Equivalence between weighted problem and doubly constrained one
In this section, we argue that, up to changing the parameters by a factor of at most 2, the weighted E-PL problem is equivalent one in which the oracle may return up lyes many false positive answers and Eno many false negative ones. We refer to this problem as the asymmetric E-PL problem. Definition 4 (Asymmetric É-PL. Problem). Given finite set V, and a partition C of V, an (Cyaz, n- asymmetric oracle for an algorithm de which, given as input pair of elements wn, returns value = {+1} so that for any sequence of queries {u,, 2t) 26) herry the sequence of responses fre = (u4e)) [T) satisfies::
and 1[t rt = -1 A un me v.Hl S loo- The asymmetric É-PI. problem is the problem of recovering C by making queries to an (fyez, ln asymmetric oracle.
Ktt rt = 1 A un f v2) S Eyes
is easy to see that any (Lzas: ffaulty oracle also an (lyas, La ) Jssmmmetric oracle and hence the query complexity of the asymmetric É-PL problem is larger than that of the weighted é-PL problem for the same choice of parameters. Conversely, we have the following:
Proposition 6. For any algoritium which solves the weighted L-PL problem by making at most q(n, k yes: knd) queries, there exists an algorithm which solves the asymmetric t-PL problem by making at most q(n, k. ye. 20) queries.
Proof. This simply follows from the fact that any (Lyesr assymmetriii oracle is also an (2yes/2, / / oracle.
C Deferred proofs from Section 6
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, 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 global variable. We begin by noting that C' is trivially refinement of the correct partition at the beginning of the algorithm. The only point in the algorithm which C' modified is on Lines 7 and 8 Insert. In that step, the algorithm modifies C' by merging the cluster containing e with the cluster containing u. This lines are executed only if the on
value of the variable result, output by Compare, +1. This happens only if count/Lyes Line 16 of Compare. in which case the latest call to Compare has obtained more than Lyee many we 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 y were not part of the same of the same cluster in C, we derive contradiction, as this would imply:
FP count Lyea
and hence FP /Lyes > 1. Hence, if C' was refinement of C before merging the clusters containing and v, then it still refinement of after merging the two clusters. This invariant then maintained throughout the algorithm, and the lemma holds.
D
14

---

Algorithm Learn (aaani(,coo ki
Input: fimite set V, an (Cyeas ffautly oracle ac, a target number of clusters k, and error parameters Eyes.
Output: A partition of V.
f (), C' < {{o} V
2 while C*I > do
pe=Get_New(S,
C. - Insert(V, a, , Poo)
[[ k + then
5 0
end
end
9 return
Algorithm 6: Get_Neet Get_Neu(S,C')
Input: partition C' of some finite set V, and a subset V such that |S| Output: An element v E representing set in C' which is currently not represented by any element of
|C'
for E V do
[v]cr ns 0 then return
end end return J.
Algorithm 7: Insert(v, C', , S,yys)
Input: A finite set V.a same-cluster oracle a for V, a partial clique S, candidate partition C' of
V. and error parameters Eyez-
Output: A new candidate cluster C', partial clique S.
for u E S
// Returns either result - or
result <- Compare (t v, ax, Eyeas (no)
If +1: is guaranteed that u and part of the same cluster and C' is edited to reflect this result = +1 then
Re-label all 'clique" queries made during this execution of Insert (and all calls to
Compare therein) as 'merge-"
new_set -[ule U [ule
C' [ule [u]er U Unew_set
return C² S
10
end
11 end
12 If S is empty or if result for every u then new item is inserted into
13 S + U {u]
return C².5
15

---

Algorithm 8: Compare a, lyez)
Input: A pair of vertices u and u from some finite set V, a same-cluster oracle a for V, and error parameters yeas.
Output: result E [
// Initialize count track "how many more times have observed compared to -= -=
count
while count 2 0 do
r a(. v)
if r - and count> 0 then count count-l
else if
and count= 0 then If the number of responses exceeds the number responses seen so far, we return 1
Label last query as 'clique'
10
Label all other queries created on this execution of Compare as 'spurious'
11
return -1
else 12
13
count counnt+ end
14
15
// If count/ > 1 then we have verified that <-c. return result +1
16
count/lye > then
17
Label the last count-many queries which received positive responses as 'merge+ Label all other queries made during this exccution of Compare as "spurious" return 1
18
20
end
21 end
Lemma 8. At the end of the algorithm, the history of queries contains at most (Cyes 1)(n k) queries labelled 'merget 'and at most k(n - k) queries labelled 'merge-'.
Proof of Lemma Consider point in the algorithm in which Compare returns +1. When that happens, the if block starting on Line Insert is executed; we refer to this as merge event.
during execution of Algorithm At the start of the algorithm |C'| = n. At each merge event two clusters in C' are merged and the cardinality of C' decreases by 1. Since C' is always a refinement of the hidden k-partition (by Lemma 7). this implies that at most n - k merge events can occur during the execution of the algorithm.
We begin by arguing that most k merge events
Both 'merge-' and 'merge+' queries are only created in correspondence with a merge event. We now show that any merge event, most k 'merge-' queries and most Eyez 1 'merge+' queries created. By the above argument these results imply the statement of the lemma.
We now show that at most & 'merge-' queries are created during each merge event. 'merge-' queries are created when some 'clique" queries are re-labelled as 'merge-'. Specifically, the 'clique' queries created during every execution of Compare within the current execution of Insert are relabelled as 'merge-'. On any exccution Insert, at most one 'clique' query is created for every element in the current set S. During any iteration of the for loop at Insert Line the set S of size at most k. implying that at most 'clique' queries are created during one execution of Insert. As result at most à 'merge-' queries created at every merge event.
Similarly, 'merge+' queries are only created in correspondence with merge event. Specifically, merge events occur when Compare returns result= +1. When this happens, 'merge+' queries are created at Compare Line 17 When Line 17 is executed, the number of queries labelled 'merge+' equal to the current value of count, which is at most at most Eyas + 1. Therefore, at most lyea + "merge+'s queries are created in correspondence with each merge event, concluding the proof. O
16

---

Lemma 9. At the end of the algorithm, the history of queries contains at most mmx{flee no queries labelled 'spurious'.
Proof of Lemma 9 Each query labelled 'spurious' can be paired uniquely with another query wo labelled spurious which returned the opposite answer. Hence, the number of erroneous answers returned by the oracle is least the number of spurious queries divided by two. This number is upper bounded by max maxx(yas, ) and the result follows.
Lemma 10. At the end of the algorithm, the history of queries contains at most (eno + 1) 1)( (k+1) queries labelled 'clique'.
Proof of Lemmal 10
The algorithm only labels queries as 'clique" in Line 9 of Compare. Thus every "clique' query is made between two elements and such that both u and were inserted into some construction of a clique, supported on the set S.
If S reaches cardinality k 1, the if block Line of Insert is executed. We refer this occurrence as a clique event. When a clique event occurs, queries have made up new a clique -1 responses of size 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 a false negative error, at most f. clique events can occur.
1. order for all of these responses to have been correct, the ground-truth
We will charge every "clique' query made before clique event to the first clique event following the query's 's creation. These queries represent a distinct edge wv of clique built on which eventually reaches size & + 1, and hence exactly (k++)) 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 the set S, which never reaches size 1, and hence there less than (**1)) 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 finite number of queries, then Line of
Algorithm is executed a finite number of times. This implies termination Algorithm
When Line of Algorithm executes, Algorithm 5] Algorithm| 7 Insert. S is nonempty on the execution of Line 4 then Insert calls Compare to Compare, Lf Compare executes at least once, and hence the algorithm makes at least one query. If S is empty implies that on the next execution of Line 4, S will be nonempty. Thus in order for Algorithm510 execute Line 4 infiniteyyy many times, the algorithm must make infinitely many queries, yielding the result.
pair of elements. On every call
the execution of Line 4 then Insert increases the size of S by 1. This
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
7 Let |'merge-'I, 'merge+'|, ''surrouu') " Iariuussll"llqiuul |'clique'] be the number of 'merge-', 'merge+ 'spurious' and 'clique" queries made by the algorithm respectively. By g
Proof of Theorem
Lemmata g
and I0 the algorithm makes at most
'merge +||| "merge+' + |'ssuriooss' |'cliquee]
+1) (1)(ktt (1+ 2
$ nk 222 + (lyes + 1)(n - 1:) + 2 max (lyce, lao) ) + (lao +
0 (RS (n, k) + (n - k + k220))
17

---

many queries, By Lemma this implies that the algorithm must terminate.
When the algorithm terminates, the condition in the while loop of Learn is not met, and hence [c] S k. But since, by Lemma is a refinement of C, must hold that upon termination |C'| and hence C' C. The algorithm then returns the correct hidden partition C.
D The algorithm for k-unknown
In this section we describe an algorithm for the weighted E-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 subroutines defined in Section[D] The main challenge in adapting Algorithm in Section ii is that the algorithm crucially relies on knowing the value of &o to build a lower bound to the number of observed errors, by counting the number of (k + 1)-liquees 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 (fyes Eno = f), this suffices to match the optimal guarantees of Algorithm 5 up to small constant factors.
Algorithm 9: Learn k_ unkknwww or, lyes, (o))
Input: finite set V, a same-cluster oracle a, error parameters Cyas and lno.
Output: A partition C' of V.
C' + {1 e VJ idxt 1
Siax +
3 while d < no + do --Ge_NNe(( (S,w((SCC (S,
v = then
idxt 1
Siax +- 0
end
else
10
C², Siax f- Insert(V,. Staxi C', Eyea)
end
12 end
13
return C'
The intuition behind the success of Algorithm 9 is that, for the algorithm to construct large cliques (significantly larger than the cardinality & of the hidden partition), the oracle must return many incorrect answers. We formalize this intuition Lemma 12
Consider the execution of Algorithm 9 The algorithm will repeatedly construct cliques of -1 queries supported on vertex sets S;, adding elements to S, until elements of V belong to an equivalence class [uler for some E Sy. Once this condition is met, the algorithm increments and initializes S,+1 as the empty set. The following lemma shows that the maximum size of any such set S constructed by the algorithm is bounded as a function of the true unknown partition size k and the error parameter fno
Consider the set S; constructed by Algorithm 9 while idx = i. We will denote by n, the maximum cardinality attained by this S, For convention we will also set no = n. Moreover, let & denote the number of false negative responses returned while idx i.
Lemma 12. For any we have;
< k+ 2kl,
(3)
Proof. Note that, if the hidden partition has cardinality k., and the algorithm obtains clique of -1 responses on n, vertices, then the number false negative emoor contained in the clique responses at least the minimum number of within-cluster edges of any k-partition of the complete graph K
18

---

Le. lower bound to the number of false negative errors that must have occurred is given by:
k
k
4 2 min
C1
Ck E E,,,
Σ
Cj =
n2
2
j=1
co
min
Cly Cj E Ry0.
Σ
Cj =
n4
2
j=1
Note that the function (xx
is convex, and hence by Karamata's Inequality (Theorem the right-hand side above is lower bounded by:
x(=-1) 11
from 25
24 1) j=1
14 2 ns
-1).
&
2
k
Re-arranging, we find that nł kn S 26,k. Completing the square we obtain:
hi
S 2l,k + h?
giving:
26ih + 1 -k² S v 2l,k k 22,k
k S V
ki
and hence:
ni S v 22,k k,
as needed.
Crucially, note that as with Algorithm 5 the partition C' maintained by Algorithm 9 is always refinement the ground-truth truth.
Lemma 13. Throughout the execution of Algorithm C' is always refinement of the true partition.
The proof of this lemma is identical to the proof of Lemma
Lemma 14. Algorithm terminates.
Proof. We show that Lines 6 and TO 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 + the while loop in Algorithm exits, and thus 6 only execute finitely many times.
To show that Line executes finitely many times, we show that every time Line exeecuues either C decreases in cardinality or Siax increases in cardinality. This follows from considering Algorithm 7 Insert. On each call to Insert, either result = +1 for some u E 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]| S n so S; can increase in size finitely many times for each value of idx E (2 1]. This implies that Line 10 can only execute finitely many times, completing the proof.
Lemma 15. When Algorithm terminates is equal to the ground- tranh-hruahhhhe partition C.
Proof. By Lemma 13 C' is always refinement of C. Therefore to show that the partition C' returned equal to 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
19

---

modifies C² by merging two previously disjoint equivalence classes. This reduces the number of disjoint equivalence classes in C", and so particular the cardinality of C' montonically decreases during the execution of Algorithm Thus if upon termination the cardinality of C' is strictly greater than k then this was true at all points during the algorithm's 's execution.
Recall that n2 is defined to be the maximum cardinality attained by set St. In particular, S attains maximum size when Line Algorithm is executed. When this happens, S; 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 then n, & Vi E [0, E2o + 1].
In particular for every value i E [1, Co + 1]. for every distinct u, U E S, Algorithm Preceives at least one response -1 for query (u, r). This response is consistent with the scenario in which and belong to disjoint sets in the ground truth partition C. If n, > [C] then at least one of these responses must have been false negative error. As this holds for every value i [1. ao + 1]. this implies least no + 1 false negative responses occur during the execution of Algorithm [ In particular this violates the assumption that is an (lyes: ) -faulty oracle, and we thus conclude that the size of C" cannot be greater than & upon termination, implying that the partition returned by the algorithm satisfies C' C.
As with the analysis of Algorithm [ bounding the query complexity of Algorithm reduces to bounding the number of queries with labels 'merge-'. 'merge+', 'clique'. 'spurious' upon termination of the algorithm.
When Algorithm| 1)k² queries labelled 'clique..
Lemma 16.
terminates the history of queries contains at most (1 + v2) (eno +
Proof. All queries labeled 'elique' upon termination must have been created during the construction of some set S; while idx= i. Given the maximum cardinality attained by set S;, the number of 'clique' queries present upon termination that were constructed while idx= is exactly
n2:
1 [ - m.) < k2 2k 2kl; + 2kl;
where the upperbound follows from Lemma 12 and 4, 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,...,60 ln + 1, we obtain:
22 + 2kl, + 2kl, n
2
2 (lao + +1)1² + 2 lnt1
Ens +1
En +1
kl, + k
L
n2
i=1
i=1
< [ 6oo + 1)hh + 22k
1
Σ
& 4++ k
k
fm +1
4
Pas +1
n4:
2
2
2 1=1
t=1
1=1
1 (lao (lo
+ +)k²² + kloo
(eno
+ 1)k²
1
+ ke
2kl + 1).
V2
2
The last line follows by observing that by definition of l,, > ls eno-
We can simplify the above expression using the fact that for integer is it holds that k S k2, to obtain the bound:
2 (Lao + 1)x2+ + klao
1
(Cno + 1)k²
1 k(loo + +1)
(1 1
kl
2 v2) (Clo + 1)k² + klao)
V2
V2
2
s {11 v2) (lao + 1)k²
Lemma 17. Upon termination of Algorithm
9 the history of queries contains at most
2 max{Lyes ) queries labelled 'spurious'.
20

---

The proof follows analogously to that of Lemma
Lemma 18, Upon termination of Algorithm the history queries contains at most (Lyes +n queries labelled 'merget', and at most
(n k) max {1 v2)k: Lao
queries labelled 'merge-'.
Proof. Similarly to the analysis Algorithm 5 we analyze the numbers of 'merge+' and 'merge-' queries, by considering merge events. A merge event is defined the execution of Line Insert.
Recall that n, define maximum size when Line of Algorithm iis executed. When this happens, S; contains exactly one representative from every cluster in C' the time of execution. Thus n, n equal to the number of clusters merged while idx = (i + 1), i.e. the number of merge events that occurred while idx = + 1). Moreover the size of C' upon termination of Algorithm 9 is equal to oo and
the maximum cardinality attained by set S. In particular, S attains
hence by Lemma Me k. This implies
n4 n1+1 no Rl
As with the proof of Lemma we note that each 'merge+' query can be charged to unique merge event such way that exactly yye + 'merge+' queries are charged each merge event. As result, the number |meerge''| of 'merge+' queries satisfies:
'mmerge+'l
(g + 1)(n; 1 - (e 1) k) 1=0
Similarly, 'merge-' queries are only created in correspondence with merge event. Specifically, "merge-" are created when 'clique' queries are re-labelled '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(1+1)- Hence at most 14+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-'l '1
Σ
n (n. n1+11)
Ana
(k v 12hl2+
n241)
i=0
Fa (n, 11 + 22
k
(n: - 1441))m L41
==0
1=0
where the second inequality follows from the bound Lemma 12 M4+1 k. we can bound the above and obtain:
Invoking the fact that 60
== Y2
'merge-'I S k (n - k) + 2k max Vlnn
2
(nu
ni+11)
< k + v 2kk2 (n-k)
< (n k) max (1 + v2)k, k + V2
yielding the result.
Equipped with the above lemmata, proceed to prove Theorem
21

---

Proof of Theorem 3 By Lemmata 14 and 15 Algorithm 9 terminates and returns the correct hidden partition. It thus remains bound the number of queries made during execution.
Let I'merge-'l, /merge+'|, I'spurious' |l''liquee] be the number of 'merge-'. 'merge+' 'spurious' and ccl "elique' queries made by the algorithm respectively. By Lemmata T6 17 and 18 the algorithm makes at most
mmerge- +Hl'merg++'= + / I'spurious'l + l'cliquee
$ (n - k) max { (1 + v2),, + no /2 + (Eyes + 1)(n k)
+ 2 max (loos (oo) (1 + (f + 1)
O (RS (n, + (n kt) max lyaa 2 } k2 k2
many queries.
E Lower bound results
E.1 Lower bounds for the easy problem: f-false negatives
We prove the following lower bound on the query complexity of the E-PL problem.
Theorem 19. Every algorithm for the E-PL" problem which guarantees full recovery of the correct partitions requires RSS(n, (n, k) + 22(k2() queries in the worst case.
Because the {-PL." FMI problem is no harder than the É-PL. problem, this immediately implies the same lower bound on the query complexity of the e-PL problem.
To establish this result, we introduce and analyze a game between a Quetionner and Responder, representing the algorithm and the oracle respectively.
define the following game, which we call the RUCC game. The game is played by two players, the questioner (Q) and the responder (Rt) and it is parametrized by a finite set V of cardinality n, positive integer
Definition of the RUCC game.
{2, n }}, and a non-negative integer f. The goal of the questioner is to infer k k-partition of V given input from the responder. At the start of the game, we are given a complete undirected graph Go on vertex set V. Go = (V, E, w wy has two associated edge weight functions wat E + and wi + R. both which are set to zero at the beginning of the game.
At each iteration t, the questioner Q submits query ue for distinct u and in V. The responder then issues response E {=1}. If +1, then wt is updated by setting w,," (wv) = w (uv)+ +1. Otherwise, if -1, then w- is updated by setting wi (uv) w (uv) (uv) + 1. We then set
G, EV,E, wt"" w, ).
For any partition of V, we define the cost:
(C) duf Σ wi (uv) +
Σ w (we)
cost
WUEE u--e
uVEE MAfC
where is the convex indicator function. Intuitively, the value of cost (C) is the number of incorrect G. negative (-1) answers that the responder would have to have given if C was the correct partition, or infinity the responder would have had to given any incorrect positive (+1) answer.
We require that the responder must, at each iteration f, reply in a way that guarantees that there exists some k-partition of V such that:
cost
PK (C) E.
FN The game terminates when cost (C) is strictly more than for but one k-partition of V, indicating that the responder is left with a single feasible partition and hence they have learned the ground truth. the game terminates at iteration T, then the payoff to the responder player is T, and the payoff to the questioner is -T.
22

---

Given a questioner strategy Q and responder strategy R, we let Game (Q, R) be the number of iterations the game lasts when questioner Q plays against responder R. as a function of the parameters k and l. The query complexity of the É-PI. FM problem is the value:
min max Game (Q, QEQ RER
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:
Vn, k, E No
min Game (Q, R2) 2 s(n, k),
QEO
then the query complexity of the E-PL problem least f(n, k, E).
Proof. This follows from:
min max Game G R) 2 min (Q, 2 ((,,ke) Q IEE
QE
In Theorem 23 in Appendix F1 we show that there exists responder strategy R satisfying
) 2(Ek2)
k 2
min Game FK Ca,e""(Q,R") 2 (e+ QEΩ
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
E.2 Lower bounds for the easy problem: f-false positives
We prove the following lower bound on the query complexity of the E-PL problem:
Theorem 21. Every algorithm for the f-PL problem which guarantees exact recovery of the correct partition requires RS* k) + +s(E(n k:)) queries in the worst case.
As in Section E. 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 very similar game to that defined above in Appendix
Definition of the RUCC game. The RUCC game is defined with the same setup as the RUCC game. The questioner Q, responder R. finite V. and gameplay graph G, (V. E, w w,) are all defined as in Appendix E.1 The core distinction between the RUCC game and the RUCC game is the notion of cost employed. For the RUCC game, for any partition of V we define the cost
cost
G.
FP
(C) def Σ wt (uv) +I
Σ wi (uv)
Intuitively, the value of (C) either the number of incorrect positive answers (+1) that the responder would have to have given if C were the correct partition, 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 way that guarantees the existence of some k-partition C* of V such that
cost (C*) S f.
The game terminates when there exists a unique k- k-partition C* such that cost (C*) <
The query complexity of the (-PI.FP problem can characterized as
min max Game EP (Q, Rt,
QEQ RER
23

---

where Game (Q, (Q, R) indicates the number of iterations in the RUCC game when questioner strategy Q plays against responder R. As in Appendix [. this characterization allows to lower bound the query complexity of the problem by analyzing the RUCC game:
Lemma 22. Let f be a non-negative real valued function. If there exists responder strategy R such that
Vn, No
min Game (Q, 2 k)
QEQ
then the query complexity of learning partitions with & false positives is at least ['nn, k. E).
The proof is entirely analogous that of Lemma 20
In Theorem 25 from Appendix F2 we show that there exists a responder strategy R which satisfies:
min Game F2 (Q, (e+ 1)(n k ((+1)(n=+1)))
M(E(n k))-
QEQ
2
This, together with Lemma
22
immediately implies Theorem 21
One-sided error lower bounds strategies
F.1 A responder strategy for the RUCC
game
In this section we show that there exists responder strategy for the RUCC** game that guarantees the game lasts at least (((k²) iterations. We consider a responder strategy which we call the (ke + 1)-groups responder strategy, denoted R(441)- In this strategy, the responder fixes arbitrary (Is + -)-partition of V. denoted C = {C; i==1 which the responder replies consistently with C whenever the rules of the RUCC game allow, i.e. whenever this does not cause the cost of every k-partition to exceed L. We lower bound the number of iterations needed for any questioner strategy to terminate the RUCC game when playing against R(++1):
k+1 h=l We define R(++1) as the responder strategy in
Theorem 23. The (I + gr-gro responder strategy R(x+1) satisfies
((*2
+ -1) S((ek))
min Game R(44))) 2 1I+ QEQ
queries.
Proof. For i,j E [k: + 1). consider the k-partitions Cj. obtained by starting with C* and merging C and Cj i.e.:
Cjj {C* (ae())+1))))) U (C; UCJ).
We show that the questioner cannot increase the cost of more than one of these partitions Ci₃ on any single iteration (a claim which prove afterwards):
Flf (Cez) S Then on iteration t + 1 the cost of C.j increases only if the Claim 24. Suppose that cost
questionner submits query for Cj and Cj.
We now prove Theorem 23 using Claim 24 Consider the potential function:
((e)
min (C.)). (+).
(4)
(.E[[++1] 4250
Note that, (0)) and, by Claim 24 at every step of the game we have;
((++1) I (t)) + 1.
(5)
Suppose that the game terminates at iteration T. Then by the rule of the RUCC game, for all but one k-partitions must be case that cost.k (C) f. particular, all but at most one of partitions Cij must have cost at least + 1, implying:
((* (k+1) -1).
T 2 11+1)
(6)
2
24

---

V To Uk-2"
Figure 2: The partition C* used in the (k 1) responder strategy.
and hence:
T2 T2 (1+1) (( (
- -1) -1)= =Z((k=))
2
as needed.
We conclude this section by proving Claim 24
Proof of Claim 24 Consider G, such that cost (Ciy) < f and such that the RUCC Game has not yet terminated. Assume the query submitted by the questioner is not of the form we for any C u Cj. For any such ut, by the definition of Cjj the pair u, is in the same cluster with respect to partition Cij if and only if the pair is in the same cluster with respect to partition C*, Thus if the responder is able to return an answer consistent with C*, this response will also be consistent with Cij, and as a result cost (Ciz) = PM (Ciz).
remains to show that the responder able to reply consistently with C on such a query. By assumption cost PK (Ciz) L, and shown above responding consistently the query in manner consistent with C* will ensure cost Fy (Ct,) cost (C.j) l. Thus if the responder replies query consistently with C", there will still exist t-partition-namely Cıj-such that Fo Gr., (Ciz) < é. Thus the rules of the PNCC game allow the responder reply query consistently with C*, and by definition of strategy R(x+1) the responder will do so. Thus the cost of C.. iteration (t 1) does not increase when the questioner plays such pair wu.
F.2 A responder strategy for the RUCC
In this section, we show that there exists a responder strategy for the RUCC game that guarantees that the game lasts at least Q(E(n= - k)) iterations. In particular, we consider responder strategy which we call the (A: 1)-groups responder strategy, denoted R(k-1). This strategy fixes k arbitrary elements vi ..., v and then fixes the following (I: -ppatiiiio:::
c= (V (Vi, ... v2 (vi), .... (vū_2))
(See Figure Figure 2 Note that when k 2, the set of {uf } is just empty and the partition C* consists of a single set equal to V. We define the (k 1)-groups strategy, as the responder strategy which the responder replies consistently with C* whenever the rules of the RUC game allow them to.
25

---

Theorem 25. The (k - grouus responder strategy R( satisfies:
(e 1)(n () -
min Game" (Q, R(k-1)) 2
(((((n=)))
2
Proof. We will prove the theorem by considering subset of the partitions which are hard for the questioner to differentiate among when playing against this responder strategy. Let S == V (Vi, 2 and for any E 5" let C. be the partition:
C. := ((v).5' \ {u), {vi]..... (16-2)}
By definition of the RUCC game, at the end of the final iteration T, we must have cost (C.)) for all but one of the partitions host. particular, consider the potential function:
min(cost FP (C.),
BES
Then, the game ends at iteration T, we must have:
( N (e + 1)((5* - 1) = ( 1)(n 1).
(7)
On the other hand, we have:
(0)) = O.
(8)
We show that this potential ()(+) changes by small amount any given iteration of the RUCC game:
Claim 26. 1f) < (n +
then x(+11 S ((0) + 2.
An immediate consequence of Claim [6 and Equations required for the game to terminate is at least T 2 (n k 1)(E 1)/2, yielding the statement of Theorem 25
7 and (8) is that the number of iterations
We conclude by proving Claim 26
Proof of Claim 26 Let uv be the query submitted by the questioner on iteration & + 1. We will split the proof of the theorem into cases.
Case 1 Suppose {u, t g S Then, if the responder answers in way that's 's consistent with C*, their answer will also be consistent with C,p for every w S*. By consequence of the assumption that ((4) (n (n-k- k +)(E 1), a simple counting argument implies that there exists an element E S* such that:
cost S.
Since wy as defined above satisfies cost (Cu,,) S E, this implies that the responder can answer in way consistent with C* without violating the rules of the game. By the definition of the strategy, the responder then will answer way consistent with C* (and with all partitions C.y)) and hence, for all S*: cost (Cw)) cost (Cw), giving g((+1) ((t)
Case 2.a Suppose that vu C S", and that the responder replies in a way that's consistent with PP
C³ In this scenario, for any w S* \ {u, f} we have cost 1111 (C.,) cost (Cw.), while FP
cost (C.)) & cost (Cw) + and cost (Co)) S cost (C.) + 1. This immediately implies (((+1) < (1) +
Case 2.b Suppose that {u, v) C S* and that the responder replies in a way that is not consistent with C*, i.c. the responder replies to the query we with -1. Then by the definition of the responder strategy, must be the case that answering +1 to the query would violate the rules of the game, i.e. it would cause every k-partition of V to have cost.p FP (C) > t
But, for every S* (u, v. the cost of the partition C.,, does not increase if the response
26

---

to the query {u, u) is +1. Hence, it must be the case that cost FD (Cw) 2 L + 1 for all such Hence, for any w E 5* {u, v}:
minff + 1, cost G.., (Cw)) = min(é + 1, cost FP (C.:))
(9)
On the other hand, since the responder replying to the query ue with -1, their answer is simultaneously consistent with both C., and C.. We then have:
FP cost G (Cw.) = cost (C..) and cost (C.) = cost EP (Co).
(10)
In particular, Equations and 10 directly imply @(++1) = (61).
This concludes the proof of Claim 26 (and in turn the proof of Theorem 25
27

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The authors ensured that the content of the abstract accurately reflects that of the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
brief discussion of limitations of the results appears in Section
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 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 how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or 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 used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
28

---

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

---

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

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU 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 estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http://pw.....ooo.o./o/o/o//o//a
Answer: [Yes]
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 to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: 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.
31

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that 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 being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses 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 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 URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.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, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of 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.
32

---

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

---

For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
34


Reviews:
[{"review_id": "Utjluw8gRf", "reviewer": "Reviewer_E2Nr", "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.", "questions": "My questions are about the weakness pointed out above.\n1. 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)\n2. 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?\n3. 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": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper establishes a novel relation between the clustering problem and the Rényi-Ulam liar games, which could potentially be useful for proving lower bounds for other learning problems.\n2. The algorithm designed in this paper involves non-trivial techniques and has a query complexity that matches the lower bound proved in the paper.", "weaknesses": "My main concern is about the significance of the learning model studied in the paper.\nFor 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.\nIn 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your helpful comments and questions.\n\nWe begin by answering your questions, and we then discuss some of the weaknesses that were raised.\n\n**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)\"**\n\nIn the \"global\" response to all reviewers, we provide further examples. The first example we provide (Example 1: Robustness to Misinformation) gives a setting in which it is reasonable to assume that the user can estimate an upper bound on the number of errors, and this quantity does not grow with the number of queries made.\n\nIn general the aim of this project is to understand the fundamental trade-off between robustness to errors and query complexity when making same-cluster queries. In this context, the $\\ell$-faulty oracle may not necessarily model the behavior of a system, but rather serves as an analytical tool to prove formal guarantees about this tradeoff. The second example (Example 2: Trustworthy Science) describes a setting in which it may helpful to understand the trade-off between robustness to error and number of queries independently of assumptions about the error model.\n\n**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?\"**\n\nOne should think of $\\ell$ not as being given or known, but rather as being chosen by the user based on their desired error tolerance. This was briefly described in the introduction (L55-56). We will be happy to further emphasize this perspective in the paper. For the full recovery guarantees to apply, the parameter $\\ell$ does not need to be equal to the number of errors occurring, but it could simply be an upper bound to that quantity.\n\nWe briefly comment that in the $k$-known setting, it is actually not necessary for the number of false negatives ($\\ell_{no}$) to be bounded or known in advance in order to run our algorithm and achieve optimal query complexity. Rather the value of $\\ell_{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. Admittedly this may not be apparent since we pass $\\ell_{no}$ as one of the arguments in the pseudocode, so we will remove it for clarity. In contrast, in the $k$-unknown setting the algorithm does require a user-chosen value for $\\ell_{no}$. Here, a simple argument shows that it is impossible to guarantee one has found the correct answer unless they can upper bound both $\\ell_{yes}$ and $\\ell_{no}$.\n\n\n**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?\"**\n\nApproximate recovery of the partition in this setting is an interesting research direction and remains an area for future work. We note that if repeated queries are not allowed, exact recovery becomes impossible even for small values of $\\ell$ ($\\ell=3$). This follows from a simple extension of a previous result of Reyzin et al. and we would be happy to highlight this fact in the paper if accepted. These impossibility results are in part what motivated the study of our paper's model in the first place.\n\n**Discussion of weaknesses.**\nWhile it is true that allowing repeated queries makes the task easier for the learner, one should note that assuming that the errors are made over the graph--as opposed to over the queries--may also simplify the problem, since typically one assumes that an adversary would commit to corruptions before observing the set of queries being made. These graph-based error models may not be suited to modeling every setting. Our first example (Example 1: Robustness to Misinformation) emphasizes why one may want to model a stronger adversarial behavior in this sense. \n\nWith regards to the comment \"knowing the number of mistakes seems to be very important to make the learning algorithm designed in this paper work,\" we emphasize that alongside providing an algorithm, a core goal of this paper is characterizing the tradeoff between error occurrence and query complexity. The cost-robustness tradeoff studied in this work is common in fields like information and coding theory, in which one is interested in the best achievable rate of communication subject to some fixed worst-case error.\n\n\nWe thank you again for your helpful comments, and we hope that, in light of this discussion, you may deem our contributions more substantial. We are happy to answer any further questions during the discussion period.\n\n\nReyzin et al. Learning and Verifying Graphs using Queries with a Focus on Edge Counting", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "x1gS8JK6YP", "reviewer": "Reviewer_BYtw", "summary": "The paper studies the problem of finding a hidden partition into $k$ clusters of a given universe.\nIn 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).\nIn 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.\nThey 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.", "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 have been addressed.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- I think that the problem is important and appreciated by the ML-community, as clustering is a fundamental problem in machine learning. Moreover, the assumption that a same-cluster oracle may not always be correct seems quite reasonable and realistic. Thus, I think that this problem and the presented results could have many applications and an impact in certain areas.\n- The authors give a tight analysis of the considered algorithms.\n- Despite being tight up to constants, the main algorithm is well-presented, and easy to understand and implement.\n- Overall, I think that the paper is well-written and seems technically sound.", "weaknesses": "- 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. \n- 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. \n\nFurther comments:\n- Line 236: missing 'and'", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your response.\n\nWe begin by answering your question: **\"Is there anything known for the setting where the number $\\ell$ is unknown to the algorithm, and it only appears in the analysis?\"**. In fact in the $k$-known setting, the algorithm presented in the paper does not require knowledge of $\\ell_{no}$ in order to be correct. Admittedly this may not be apparent since we pass $\\ell_{no}$ as one of the arguments in the pseudocode, so we will make sure to remove it in order to make this less confusing to future readers. \n\nA consequence of this is that in the $k$-known setting, one does not require any a priori knowledge of $\\ell_{no}$, nor are they required to set any upper bound for $\\ell_{no}$ in advance, in order to achieve the optimal query complexity both in the weighted $\\ell$-PL problem and in the version of the problem in which only false negatives can occur. In particular, in this latter version, the learner would not require any knowledge of the error at all in order to achieve the optimal query complexity.\n\nWhether one could design an algorithm that also requires no knowledge of $\\ell_{yes}$ in the $k$-known setting is an interesting question and we will make sure to discuss it in the \"Conclusions, Limitations, and Future Directions\" section of the paper.\n\nWe note that in the $k$-unknown setting, without knowledge of $\\ell_{no}$ and $\\ell_{yes}$ it is impossible for an algorithm to make a finite number of queries and then output a partition that is guaranteed to be correct. To see this, suppose the oracle answers in a way that is consistent with some fixed partition $\\mathcal{C}$, then (1) if $\\ell_{no}$ is unknown to the learner it is impossible for them to establish whether $\\mathcal{C}$ is the true partition or a refinement of it, on the other hand, (2) if $\\ell_{yes}$ is unknown to the learner then it is impossible for them to tell whether $\\mathcal{C}$ is the true partition or a coarsening of it.\n\nIf the paper is accepted, we will add a summary of the above discussion to the manuscript. We will also be happy to elaborate on the similarities and differences with the algorithm for the error-free version of the problem. Finally, we have fixed the typo you found.\n\nWe thank you again for your time and your useful comments.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "A2PHZGkkdZ", "reviewer": "Reviewer_GCFN", "summary": "**[Setting]**:\nThis 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.).\n\n**[Contributions]**:\n1. 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.\n2. For known k, an algorithm that iteratively merges cluster using two heuristics:\n    1. If there is a (k+1)-clique of all -1s then the oracle has returned at least one false negative\n    2. More than $\\ell$ \"+1\" responses from oracle for a given pair guarantees that it is in the same cluster\n3. Sample complexity of the proposed algorithm that matches the lower bound.\n\nThe results extend to a more general problem where individual limits on false positive and false negative errors are known.\n\nThe paper also studies an algorithm for k-unknown case in the appendix. Sample complexity in this case is not optimal.", "questions": "Please respond to point 1 under weakness\n\n\n**Minor suggestions**:\n1. Typo in L100 - \"A many\" -> \"Many\" \n2. A more recent paper (Gupta et al. 2024) studies a more general setting than Chen et al. (2023), which is closest to your work.\n\n\nGupta et al. Clustering Items From Adaptively Collected Inconsistent Feedback - AISTATS, 2024", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The problem of guaranteed exact cluster recovery in the presence of noise is new. Having a hard limit on the number of errors made by the oracle makes this possible. Given concrete applications, this would be an interesting direction to explore.\n2. The sample complexity of the proposed algorithm matches the derived lower bound when k is known.\n3. The connection to Chip-Liar game for deriving the lower bound is interesting.", "weaknesses": "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?\n2. 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,\n    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?\n    2. Some high-level details about the unknown-k algorithm.\n    3. Some intuition about why false-negative and false-positive error budgets inherently have a different contribution towards minimum sample complexity", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for taking the time to provide thorough feedback on our work. We begin by addressing your main question. After that, we discuss some of the weaknesses you mentioned.\n\n**\"... it is not clear why the oracle will make at most $\\ell$ errors ... or why $\\ell$ will be known in advance. Do the authors have concrete applications in mind?\"**\n\nThe results in the paper characterize the minimum query cost needed in order to achieve a desired level of robustness to a number of errors. In particular, one may think of $\\ell$ as not being given or known, but rather as being chosen by the user based on their desired error tolerance. This was briefly described in the introduction (L55-56). In the \"global\" response to all authors we discuss two more examples in which our model may be applied, which we will include in the paper if it gets accepted. The first of these (Example 1: Robustness to Misinformation) describes a situation in which the number of corruptions that will occur is finite and does not scale with the number of queries submitted, and in this example the learner may set the value of $\\ell$ depending on their desired robustness to adversarial error. This type of cost-robustness trade-off is common in fields like information and coding theory, in which one is interested in the best achievable rate of communication subject to some fixed worst-case error.\n\nDually, one may also think of our results as resolving the optimal error robustness subject to a constraint on the number of queries. Our second example (Example 2: Trustworthy Science) outlines a scenario in which one may benefit from understanding this trade-off.\n\nWe note that it is impossible to design a protocol that allows the learner to exactly recover the full partition while remaining robust to a number of errors that grows as a constant fraction of the queries made. This follows trivially from known impossibility results (e.g. Proposition 1 of Reyzin et al.), and we will add a precise statement to the paper if it gets accepted.\n\nWe briefly comment that in the $k$-known setting, it is actually not necessary for the number of false negatives ($\\ell_{no}$) to be bounded or known in advance in order to run our algorithm and achieve optimal query complexity. Rather the value of $\\ell_{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. Admittedly this may not be apparent since we pass $\\ell_{no}$ as one of the arguments in the pseudocode, so we will remove it for clarity. In contrast, in the $k$-unknown setting the algorithm does require a user-chosen value for $\\ell_{no}$. Here, a simple argument shows that it is impossible to guarantee one has found the correct answer unless they can upper bound both $\\ell_{yes}$ and $\\ell_{no}$.\n\nEffectively conveying the specifics of the error model is a key aspect of communicating our results, and we thank you for prompting us to clarify the role of $\\ell$. We will update the manuscript to increase the emphasis on the above discussion, and we believe this will strengthen our paper. \n    \n**Further Discussion of Weaknesses**\n\n**``...it would be helpful to include more details from the appendix into the main paper.''** We thank you for this suggestion and we agree. If the paper is accepted, we will include an overview of the $k$-unknown algorithm, discuss intuition for the asymmetry between false-negative and false-positive errors, and elaborate on the role of the chip board analogy.\n\nWe now briefly answer the question: **``What does 'The position of a chip on the board will then be equal to the cost of the corresponding partition ...' (L234-235) mean?''** In the $\\ell$-PL constrained version of the Chip-Liar game, each chip corresponds to one partition of $n$ elements into $k$ groups. When the questioner submits a query (\"Are $u$ and $v$ in the same group?\"), the responder answers either \"yes\" or \"no\". All chips whose partitions are inconsistent with the response (i.e. if the responder answers \"yes\", then all partitions where $u$ and $v$ are not in the same group) advance by one position on the board. In L234-235 we highlight that under this procedure, the position of the chip on the board is then equal to the cost of the partition as a feasible solution to an instance of a correlation clustering problem.\n\nRegarding the **\"Minor Suggestions\"** we were not aware of the recent work of Gupta et al. and we appreciate the pointer. We will make sure to discuss and cite it appropriately. We will also fix the typo you found.\n\nWe conclude with a quick remark in response to the following: **\"The paper also studies an algorithm for $k$-unknown case in the appendix. Sample complexity in this case is not optimal.\"** While it is true that, in the $k$-unknown setting, our algorithm does not achieve the optimal query complexity in **every** variant of the problem, it does achieve the optimal query complexity in the (unweighted) $\\ell$-PL problem, i.e. the main variant in which false positive and false negative responses are penalized equally.\n\nLastly, we wish to thank you again for your time and your help in improving the paper. We hope that in light of the clarifications on the error model you may deem our contributions more substantial.\n\nReyzin et al. Learning and Verifying Graphs using Queries with a Focus on Edge Counting", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dnLdZh1v8z", "reviewer": "Reviewer_2QcX", "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.", "questions": "1. Is it possible to get better query complexity bounds if the goal is to recover the partition approximately but not exactly?\n\n2. 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": "The limitation of the paper is well addressed.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The result of this paper is clean and complete. The algorithm's query complexity matches the lower bound up to constants.\n\n2. The main algorithm is concise, simple and elegant. The idea of the algorithm captures the problem well and has proved optimal guarantees.\n\n3. The lower bound is non-trivial and has some interesting ideas.\n\n4. This paper is very well-written. The notations and explanations are clear. I didn't even catch a single typo. Enough background and motivation is included in the paper. The paper is cohesive and organized, easy to follow. Math and algorithmic ideas are explained clearly.\n\n5. I think this paper should be a spotlight.", "weaknesses": "I'm very satisfied with this paper, just two things I think it can improve on the writing.\n\n1. 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.\n\n2. I think it's worth mentioning what's the optimal algorithm for the no-error oracle and compare your algorithm with theirs. \n\nAlso something I would not like to call it a weakness since I think it's beyond the scope of the paper:\n\n1.  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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your thorough review.\n\nWe address your questions and comments in order. Regarding the writing: we agree that the details of the lower bound proof are technically more challenging and arguably more mathematically interesting, but we had previously decided to prioritize the algorithm since we thought the community might value it more. We will be happy to write more about the intuition behind the design of the responder strategy in the main body of the paper, and make the relevant appendix more detailed if the paper gets accepted.\n\nIn terms of comparing with the error-free algorithm, there certainly are similarities between the two algorithms, and we would be happy to include an extra appendix elaborating on this comparison. In fact, the algorithms proposed in this work nearly-generalize the original algorithms for the error-free regime; when $k$ is known, setting $\\ell_{{yes}}=\\ell_{{no}}=0$ causes the algorithm to perform a nearly-equivalent procedure to the corresponding $k$-known algorithm of Reyzin and Srivastava, and when $k$ is unknown, this setting yields an algorithm that is exactly equivalent.\n\nRegarding the inconsistent error assumption: while it is true that this assumption guarantees that the problem is solvable given unlimited queries, and makes the problem easier for the algorithm, we believe that the value of our result lies in understanding the query complexity in this setup. \n\nIf the model is chosen to prevent the algorithm from querying the same pair multiple times, then exact recovery is impossible even for very small values of $\\ell$ (say $\\ell = 3$). This follows from a previous result of Reyzin et al. This naturally leads to your question of partial recovery. This is an interesting research direction, and we believe that answering it may require a non-trivial amount of further work. The same applies to the stochastic error setting you suggested. It is worth noting that if one knows the expected number of errors, a simple application of Markov's inequality would allow one to run our algorithm with settings that guarantee success with probability 1-$\\delta$ while making a number of queries that grows linearly in $1/\\delta$. Stronger statements could likely be made by making further assumptions about the distribution of $\\ell$. We are hopeful that our work will serve as a first step towards answering more questions in this problem space.\n\nWe thank you again for your time and your help in improving the quality of our paper.\n\nReyzin et al. Learning and Verifying Graphs using Queries with a Focus on Edge Counting", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for their time. Multiple reviewers have asked for more examples in which our model could be applied. Below, we give two more general motivating examples, in the tech and scientific domains respectively, illustrating the role of $\ell$ in 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, $\ell$ plays the role of a security parameter, and the algorithm is guaranteed to be robust to up to $\ell$-many poisoned responses. The user can set $\ell$ 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 $\ell$.

**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. 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 as the setting for $\ell$, 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.

Meta-review: 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.
Decision: Accept (poster)