Query-Efficient Correlation Clustering with Noisy Oracle
Authors: Yuko Kuroki
Atsushi Miyauchi
Francesco Bonchi
Wei Chen
Venue: NeurIPS 2024 poster (2024)
Keywords: Correlation Clustering; Online Learning; Pure Exploration of Multi-armed Bandits
Primary area: optimization
TL;DR: We study a general correlation clustering problem with noisy weighted similarity queries, introducing two novel online learning formulations and designing efficient algorithms with theoretical guarantees.

Abstract: We study a general clustering setting in which we have $n$ elements to be clustered, and we aim to perform as few queries as possible to an oracle that returns a noisy sample of the weighted similarity between two elements. Our setting encompasses many application domains in which the similarity function is costly to compute and inherently noisy. We introduce two novel formulations of online learning problems rooted in the paradigm of Pure Exploration in Combinatorial Multi-Armed Bandits (PE-CMAB): fixed confidence and fixed budget settings. For both settings, we design algorithms that combine a sampling strategy with a classic approximation algorithm for correlation clustering and study their theoretical guarantees. Our results are the first examples of polynomial-time algorithms that work for the case of PE-CMAB in which the underlying offline optimization problem is NP-hard.

Query-Efficient Correlation Clustering with Noisy Oracle
Yuko Kuroki CENTAI Institute Turin, Italy
Atsushi Miyauchi
CENTAI Institute Turin, Italy
yuko.
atsushi hww.hhhi...aacchheeentttt...
Francesco Bonchi
Wei Chen
CENTAI Institute, Turin, Italy Eurecat, Barcelona, Spain bonchi@centai.co
Microsoft Research Beijing, China veic@microooff com
Abstract
We study general clustering setting in which have n elements to be clustered, and we aim to perform as few queries as possible to an oracle that returns noisy sample of the weighted similarity between two elements. Our setting encompasses many application domains in which the similarity function is costly to compute and inherently noisy. We introduce two novel formulations of online learning problems rooted in the paradigm of Pure Exploration in Combinatorial Multi-Armed Bandits (PE-CMAB): fixed confidence and fixed budget settings. For both settings, we design algorithms that combine sampling strategy with classic approximation algorithm for correlation clustering and study their theoretical guarantees. Our results are the first examples of volynomial-time. algorithms that work for the case PE-CMAB in which the underlying offline optimization problem is NP-hard.
Introduction
Given a set = [rx] of n objects and a pairwise similarity measure s: (5) + [0, 1] (where (K) is the set of unordered pairs of elements of V, and the value closer to 1 means higher similarity), the goal of Correlation Clustering [7] is to cluster the objects so that, to the best possible extent, similar objects put in the same cluster and dissimilar objects cluster identifiers are represented by natural numbers, a clustering C can be represented as a function f: V:V- N, where each cluster is maximal set of objects sharing the same label. The objective is to minimize the following cost:
put in different clusters. Assuming that
costs(")
Σ (1-s(I,))) +
Σ
s(x,v).
( ((x)=(())
( {(x))(()))
The intuition underlying the above problem definition is that if two objects x and are dissimilar, expressed by small value of s(x. y). yet they assigned to the cluster, we should incur high cost. Conversely, if s(x, y) high, indicating that x and are very similar, but they are assigned different clusters, we should also incur a high cost.
Two key features make correlation clustering quite suitable in real-world applications. Firstly, it does not require the number of clusters as part of the input; instead, it automatically finds the optimal number, performing model selection. Secondly, it only requires the pairwise information without
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

assuming any specific structure of the data. This reasonably eliminates the need for domain knowledge about complex data. Correlation clustering has been applied to a wide range of problems across various domains, including duplicate detection and similarity joins [34, 46], spam detection [2], co-reference resolution [66]. biology [9, 14], image segmentation [54], social network analysis [13],
and clustering aggregation [42].
Correlation clustering is NP-hard even in the simplest formulations [7, 75], and minimizing the cost function in (1) is APX-hard [20]; thus, we cannot expect a polynomial-time approximation scheme. Nevertheless, there are number of constant- factor approximation algorithms for various settings [1, 3, 7, 20, 22, 30-32]. For the formulation of (1), Ailon et al. [3] presented KwikCluster, a simple 5-approximation algorithm. The algorithm randomly picks a pivor u E V and constructs a cluster by taking all the vertices similar to u; then, the algorithm removes the cluster and repeats the process until V is fully clustered. The simplicity and theoretical guarantees of KwikCluster have produced a lot of variations in different scenarios [13, 29, 61, 69, 76, 79].
In practice, preparing the similarity function involves costly measurements. Given n items to be clustered, ((n²) similarity computations are needed to prepare the input to correlation clustering algorithms. Moreover, computing the similarity s(x, y) might have additional expenses (e.g.. human effort or financial resources) besides the mere computational cost. To mitigate these issues, some query-efficien methods have been proposed based on the active learning framework [11, 15, 40]. In this framework, the similarity function is initially unknown but an oracle that returns the true similarity {0, 1} for pair of objects is sequentially queried. In particular, these studies provided a randomized algorithm that, given budget T of queries, attains solution whose expected cost is at most 3- OPT ((4)). ). where OPT is the optimal value of the problem.
However, the above methods for query-efficient correlation clustering have significant limitations. Indeed, all the aforementioned works [1 1, 15, 40] only consider the binary similarity of (0, while the similarity between two objects are often non- non-binary in real-world scenarios. For example, in biological sciences, protein- -rrotiin interaction networks are commonly analyzed, where the strength of the interactions among proteins is represented as a real-valued similarity [68]. As another example, in entity resolution, i.e., task central to data integration [80], real-valued similarity is used indicate the likelihood of matches of objects instead of binary decisions. Therefore, allowing the similarity to be real-valued in the interval [o, 1] would be more practical and flexible. Furthermore, the above works assume the access to the strong oracle that returns the true value of s(x,, y) (= 0 or 1), while evaluating s(x, y) might be inherently noisy, due error-prone experiments, noisy measurements, or biased judgments. In the above first example the strength of the interactions among proteins is often measured based on biological experiments involving unavoidable noise, while in the second example the likelihood of matches of objects is usually obtained based on biased human judgements.
In this paper, we focus on the challenging scenario where (i) the underlying similarity measure can take any real value in [0, 1] rather than being binary, and (ii) we can only query a noisy oracle that provides inaccurate evaluations of the weighted similarity s(x, v). The goal of this paper is devise clustering algorithms that perform as few queries on s(x, y) as possible to an oracle that returns noisy answers s(x. (). In pursuit of this goal, we introduce two novel formulations based on multi-armed bandits problems, both of which achieve a reasonable trade-off between the number of queries to the oracle and the quality of solutions.
While our problem formulations are novel, recent prior work has explored related issues. Silwal et al. [76] proposed a practical model using the strong oracle along with cheaper but inaccurate oracle. Their algorithm achieves a cost of 3- OPT + en using n + O(?) queries to the strong oracle, where y 0 is the error level of noisy oracle and > 0 is the additive error. However, they still focus on the binary similarity and there is no guarantee on the query upper bound for the noisy oracle. Unlike theirs, our models are designed to handle the weighted similarity and do not rely on any strong oracle. Aronsson and Chehreghani [4, 5] studied a non- porrsissttt noise model where the oracle returns the true value of s(x; y) with probability 7 and noisy value otherwise. Their algorithm handles general weighted similarity but provides neither query complexity nor approximation guarantee.
1.1 Our contributions
In this paper, study the problem of query-efficient correlation clustering with noisy oracles, where the similarity function (>) + [0, 1] is initially unknown, and only noisy feedback instead of

---

the true similarity s(x, y) is observed when querying pair of objects (z, y). In this scenario, it desired achieve reasonable trade-off between the number of queries to the oracle and the cost of clustering. To this end, we introduce two formulations of online learning problems rooted in the paradigm of Pure Exploration of Combinatorial Multi-Armed Bandits (PE-CMAB). In the fixed confidence setting (Problem 1), given a confidence level g E (0, 1), the learner aims to find a -ell-approximate solution with probability at least ô while minimizing the number of queries required to determine the output. Conversely, in the fixed budget setting (Problem 2). given querying budget T. the learner aims to maximize the probability that the output is a well-approximate solution. Our contributions can be summarized as follows:
For Problem with KwikCluster. We prove that given confidence level 8 E (0, 1), KC-FC finds a solution whose expected cost is at most OPT + c with probability at least optimal value of the problem, and provide the upper bound of the number of queries (Theorem 1).
we design KC-FC (Algorithm 1), which effectively combines threshold bandits
8, where OPT is the
We design KC-FB (Algorithm 3) for Problem 2, which adaptively determines the number of queries for each pair of objects based on KwikCluster. We prove that the error probability of the expected cost being worse than 5 OPT + e decreases exponentially with budget T (Theorem 2).
We empirically validate our theoretical findings by demonstrating that KC-FC and KC-FB out- perform baseline methods in terms of the sample complexity and cost of clustering, respectively.
It is worth noting that our approximation guarantees in Theorems and match the approximation ratio 5 of KwikCluster [3], where s: ( + [0, 1] is known in advance, up to the additive error e >> 0. These results are not achievable using existing PE-CMAB algorithms due the NP-hardness of correlation clustering. In the standard PE-CMAB, a learner aims to identify the best action that maximizes the lincar reward from the combinatorial decision set D C 2(ml with m--bse arms. Existing algorithms for PE-CMAB (e.g.. [23, 25, 35, 52, 82]) rely on the assumption that the offline problem is polynomial-time solvable. Redesigning them to obtain a well-approximate solution while running efficiently is quite challenging, as the exact optimization of the offline problem is crucial to achieving statistical validity and a correctness guarantee for the output. Ours are the first polynomial- time algorithms that work for the case of PE-CMAB where the underlying offline optimization is NP-hard, filling a critical gap in existing PE-CMAB algorithms, which is of independent interest.
1.2 Related work
Correlation clustering with noisy input. The bulk of the literature noisy correlation clustering (see Section 4.6 of Bonchi et al. [10]) considers the binary similarity and assumes that there is the ground-truth clustering but some of the s(x: y) wrong: they are 0 instead of 1, vice versa. The seminal work by Bansal et al. [7] and Joachims and Hopcroft [49] provided the bounds on the error with which correlation clustering recovers the ground truth under simple probabilistic model over graphs. Mathieu and Schudy [64] studied the model starting from an arbitrary partition of the elements into clusters, where $(x; y) is perturbed independently with probability p. and a more general model with the adversary. They proposed an algorithm that achieves some approximation ratio and manages to approximately recover the ground truth. Chen al. [28] extended the framework to sparse Erdōs-Rént random graphs and obtained an algorithm that conditionally recovers the ground truth. Finally, Makarychev et al. [62] overcame some limitations of Mathieu and Schudy [64] and Chen et al. [28]; they assumed very little about the observations and gave two approximation algorithms. Unlike the above models, ours is based on online learning with an unknown distribution with mean of s(x. y). which is in general not binary, and does not assume any ground-trum -rutt clustering.
Combinatorial multi-armed bandits. Multi-Armed Bandit (MAB) a classical decision-males model [57, 59, 73]: There are m possible actions (called arms), whose expected reward μ4i for each i E [m]] is unknown. At each round, learner chooses an arm to pull and observes a stochastic reward sampled from an unknown probability distribution. The most popular objective is to minimize the cumulative regret [16, 18]. Another popular objective is to identify the arm with the maximum expected reward. This problem, called the Best Arm Identification (BAI) or Pure Exploration (PE) in MAB, has also received much attention [6, 8, 17, 21, 24, 37, 38, 41, 48, 53). The model of Combinatorial Multi-Armed Bandits (CMAB) is generalization of MAB [19, 26). where an interested subset of arms forms a certain combinatorial structure such as spanning tree, matching, or path. Since its introduction by Chen et al. [25], the study of PE-CMAD has been actively pursued
3

---

in various settings [23, 35, 36, 47, 50, 55, 56, 67, 78, 82]. Notably, Gullo et al. [44] addressed regret minimization for correlation clustering by adapting UCB-type algorithms. However, regret minimization in CMAB is quite different from pure exploration framework when working with approximation oracles (i.e., offline approximation algorithms) for solving NP-hard problems. For regret minimization, we can incorporate approximation oracles with the UCB framework, consistent with the optimization under uncertainty principle (c.g,, [26, 27, 81]). However, in pure exploration, the lack of uniqueness of a-approximate solutions makes it difficult to determine the stopping condition in the FC setting. In the FB setting, the Combinatorial Successive Accept Reject algorithm proposed by Chen et al. [25] iteratively solves the so-called Constrained Oracle problem, which often NP-hard, as later addressed in Du et al. [35]. We anticipate a similar NP-hard problem in correlation clustering, requiring different approach.
Other clustering settings. Ailon et al. [2] and Saha and Subramanian [74] studied correlation clustering with same-cluster queries, where all similarities of (2) are known in advance and their query is further allowed access the optimal clustering. Our setting differs significantly as we are interested in the case where similarities are unknown and only noisy similarity values are received rather than same-cluster queries. Finally, is worth mentioning that Xia and Huang [83] and Gupta et al. [45] proposed MAB approach for clustering reconstruction with noisy same-cluster queries [58, 65, 70, 71, 77]. However, this clustering reconstruction problem does not directly offer any algorithmic result for correlation clustering. The detailed comparison is deferred to Appendix A.
2 Problem statements
Here we formally define our formulations of PE-CMAB for correlation clustering. Our problem instances are characterized by (V,s), where = [x] is the set of elements to be clustered and 8 (2) + [0, 1] is the pairwise similarity function, which is unknown to the learner. Define the set of unordered pairs as E = (%) with = [B]
1,2.... a learner will pull (i.e., query) one arm (i.c., pair of elements in V) from action space E' = (b) based on past observations. After pulling e E E, the learner can observe the random feedback Xe),), which is independently sampled from unknown distribution such as Bernoulli or R-sub-Gauut Gaussian with unknown mean s(e) E [0. 1].' After some exploration rounds, the learner must identify well-approximate solution. Let OPT(s) be the optimal value of the offline problem minimizing the cost function (1) and let Cout be the output by an algorithm. For a 2 1 and <> O, we say Cout be an (a, e) >)aappooximate solution if cost,, (Cont) S OPT(ss the following two formulations: Fixed Confidence (FC) and Fixed Budget (FB) settings.
At each round
We study
Problem 1 (Fixed confidence setting). Let a 2 1. Given a confidence level ò E (0,1) and additive error > O, the learner aims to guarantee that the output Cout is (a., c)-approximate solution with probability at least 1- 5. The evaluation metric of an algorithu is the sample complexity, i.e., the number of queries to the oracle the learner uses.
Problem 2 (Fixed budget setting). Let 2 1. Given querying budget T and additive error O. the learner aims to maximize the probability that the output Cou. is an (a,, -)aproxxiee solution.
Note that the case of a corresponds to the standard PE-CMAB formulations. However, as the offline problem minimizing the cost function (1) is APX-hard [20], we cannot expect any polynomial- time algorithm that can handle a in the above formulations.
3 Fixed confidence setting
In this section, we design KC-FC (Algorithm 1) for Problem 1, built on a novel combination of KwikCluster (detailed in Algorithm 4 in Appendix B) and techniques of threshold bandits. The key idea of the proposed method is to first identify pairs with seemingly high similarity, which are then passed to KwikCluster to produce a high-quality clustering.
We use Bernoulli distribution for the sake of simplicity, ie.. Xi(e) ~ Bern(s(e)). where s(e) is the unknown mean. We can consider Sab-Gaussian distribution and our results carry on, by simply adjusting the statement of the Hoeffding inequality accordingly.

---

Algorithm 1 KwikCluster with Fixed Confidence (KC-FC)
Input Confidence level ò, V of n objects, and error Ei f E. Vi < V.r < 1, and Cout + 0;
2 Compute G by TB-HS (Algorithm with é' 12m
3 Define [(v) := {u V {u, E Gel::
while V > 0 do
Pick pivot Pr V, uniformly at random;
Cout Cout U [Cr,, where C, == (fpr) (u(p))))))))) nV; V++++ + V, C, and r + +1
8 return Cout.
For the first phase, we leverage one of the variants of MAB, called the threshold bandits [51, 60, 63], which is defined as follows: Given a confidence level 6 and m-arms, the learner must return the set of good arms, i.e., arms whose expected rewards are greater than a given threshold 0 > as soon as possible, and stops when the learner believes that there is no remaining good arm, w.p. at least 1 1-6. 6. TB-HS (detailed Algorithm 2) is our key procedure, which designed for identifying seemingly high similarity pairs. Note that, if we naively use the existing algorithm by Kano et al. [51]
for threshold bandits where the set of arms is F = (2) and the threshold is 0 = 0.5, the algorithm not even guaranteed to terminate; the resulting sample complexity becomes infinitely large s(c) = s(e') for different e, E E or if there exists E E with s(e) = 0.5, which may frequently happen in practice. Our strategy to avoid such an unbounded sample complexity is to allow TB-HS to misidentify pairs of elements with similarity close to 0.5, taking advantage of the fact that the output accuracy can guaranteed despite such misidentification.
Algorithm details. Let (e) be the empirical mean of the similarity for each pair E F. kept at round t. Let (e) be the number of queries of e E E that has been pulled by the end of round t. TB-HS maintains the confidence bound defined as rad,(e) = V /ogí (. for each E E. The arm selection at round is based on the
2N.(e)
Bound (LCB) score, i.c.. (e) = (e)))rad (e) and the Upper-Confidence- Bound (UCB) score, i.c., (e) == Se +rad((e).. We pull the arm èi with the highest LCB (line 5) and the arm èy with the lowest UCB (line 6). Then Ee will be added to G if its LCB is no less than 0.5 e, and ét will be added to B, if its UCB is no greater than 0.5 e. TB-HS continues this procedure until every e E E' is added to either G. or e. B. Our main algorithm KC-FC invokes TB-HS to compute Ge with parameter é'
12m Then it carries out KwikCluster using the predicted similarity by G. as follows. Until an unclustered element exists, picks one pivot element pr uniformly at random, builds a cluster C, around by adding those among the unclustered elements that seemingly have high similarity with pivot pr (based on G.), and removes all the elements in C, from the list of unclustered elements.
Analysis. For a given e E (0, 0.5), we define the following sets, which appear only in the theoretical analysis and are unknown to the learner: Ejo.210] = {e E E |0.5 s(e) I c).
E(0.5+c,1] := {e E s(e) 0.5 + e}. and E0,00.5-)) == {e E s(e) < 0.5 - -). For
C (0, 0.5), we introduce the definition of the gaps that characterize sample complexity:
se.::= (A. + min ( Amin: 2) for e E [m),
where A, : [s(e)) 0.5| for e E [m] and Amin == min.e[m] Ac.
Now we present our theorem, guaranteeing that KC-FC finds (5, approxxiae solution with high probability and provides an upper bound of the number of queries, i.e., the sample complexity.
Theorem 1. Given confidence level 8 E (0, 1) and additive error e O, KC-FC (Algorithm 1)
guarantees that
(Cout) 55 OPT(s) + + 1-88
5

---

Algorithm 2 Threshold Bandits for indentifying High Similarity pairs with E (0, 0.5) (TB-HS).
Input :Set of m-arms and confidence level ö
1 Gg 6 0 and B, < D:
Pull each E' once to initialize empirical mean (m),), +- m, and Eg + E;
3 Compute red ;=
Ne for e E Eg;
2N-(e)
while F. > 0 do
Pull é == argmax.eccc... eE (c)(c) - re)) once;
Pull èt == argmin F, (e) + (e); once;
Update & and rad; for Eg and é
(ef) := Se(ef) rade > 0.5 then
L Add éf to good arms, i.e., G. G. U (ef), and delete eg from Fig
i. == (e)) re)) v 0.5 + then
Add é bad arms, i.e. B, B, { and delete ét from E,;
11
12
E+42 + Es; t 1
13
return G.
and letting è' the sample complexity T is
12m
o 3
n
n1
n²
log
log
+
A2
22 22
max { Amins
el 2
KEEE
c,c'
Furthermore, KC-FC runs in time polynomial in n.
Sketch. For the outputs G. and B. of TB-HS (Algorithm 2) with parameters é E (0, 0.5) and 5 E (0, 1), by using the Hoeffding inequality and the procedure of TB-HS (lines 8 and 10), it is easy to see that 1(0.5+e.1] C G. and E.. C B, w.p. at least
Consider the similarity
function 5 E [0, 1] such that for each E E, ä(e) s(e) if E1o.0.--) U (o.5+...]. and 5. otherwise, where 5. is an arbitrary value that satisfies (s(c) Fel 2c. Noticing that KC- FC corresponds to KwikCluster associated with a certain choice of s (i.e., 5e for e E Ej.. we can show that E Eccosts(Coo)) (Cout)l S 5 OPT(s) - Ee. for the output Cout, providing the approximation guarantee. The rest of the proof requires the analysis of the upper bound of the number of queries that TB-HS used to stop. This can be done hased on a prior analysis of threshold bandits [51) while carefully handling
0. The complete proof for analysis is given in Appendix C.
For the time complexity, each iteration of sub-routine TB-HS takes ((m) steps naive implemen- tation or amortized Ollog 7') steps if we manage arms using two heaps corresponding to LCB/UCB values, and the other procedure KC-FC runs in time polynomial in n.
Comparison with existing PE-CMAB methods in the FC setting. Existing methods for PE- CMAB (e.g.. [23, 25, 35, 82]) are limited by their reliance on the polynomial-time solvability of the underlying offline problem. If
efficient approximation algorithm in those existing methods, their stopping conditions no longer have a guarantee of the quality of the output. Specifically, such existing methods use the LUCB-type strategy, and its stopping condition requires the exact computation of the empirical best solution and the second empirical best solution to check if the current estimation enough or not. When we only have an approximate oracle (i.e., approximation algorithm), such existing stopping conditions are no longer valid, and the algorithm is not guaranteed to stop. In contrast, KC-FC runs in time polynomial in while ensuring sample complexity and approximation guarantee. We also note that A.. the distance between s(e) and 0.5, interestingly characterizes our sample complexity, as we show that the learning task boils down to identifying E(o.5+e'.1) and E thanks to the behavior of KC-FC they leverage the property that by accurately estimating the mean of the base arms (i.e., pairs of elements). we can maintain the approximation guarantee of KwikCluster in the offline setting with small additive error.

---

Statistical efficiency. In the noise-fres free setting, (2) queries are sufficient, while in the noisy setting, there even no trivial upper bound on the sample complexity to achieve some desired approximation guarantee (e.g., our (5, -apppooximtiion) Note that the value of &e, defined in (2) always has the following lower bound: A.. = A. + e// (> 0) if c/2 2 Aii holds and Å..e = A. - c Amin 2 (> 0) otherwise. Therefore, our sample complexity T given in Theorem is always bounded, contrasting existing results for threshold bandits [51]. The naive sampling algorithm (Uniform-FC in Appendix E) requires 0 log ))) samples to achieve the (5, -)aappoxximmiionn w.p. at least 1 6. KC-FC achieves much better sample complexity than Uniform-FC, as EeER A
Ed + 5)² < o when Amin S & < De for most e E E. which is often the case in practice. To the best of our knowledge, lower bounds on the sample complexity related to PE-CMAB are known only for the following settings: (i) the time complexity of algorithms can be exponential, or (ii) the underlying offline problem is assumed to be polynomial-ting solvable and to have the unique correct (namely optimal) solution [25, 35, 391. Deriving an effective lower bound on the number of samples required to guarantee approximate solution is particularly challenging because necessitates dealing with multiple correct solutions [33], while most existing approaches rely on the uniqueness of the correct solution. Evaluating the necessity of the second term
max
and investigating lower bound for case crucial and remain important future work. However, it is worth noting that the additional term is independent of a dominating term involving log J-
Remark. If we utilize TB-HS within the loop (Algorithm 5 in Appendix B), the algorithm achieves (5, e) apappppoxintioon guarantee with probability at least 1 - 5, and the sample complexity T is:
o
Σ
1
log
72
log
n
V
A 2,
A E,,Y
max A min.r 5.
eElv, (p.)
(p.))))) (p.))), where 1: is the total number of loops in Algorithm 5, 6 <=:==<(12)7 c/(12
Iv, (D,)) 5 E represents the set of pairs between the pivot pr selected in phase r and its neighbors in Vr, and Amin.r := millely, (p.) Ag. When l < the above sample complexity can be better than that of Theorem 1. However, it should be noted that the symbols related to r and the total number of loops k. especially instance-dependee
gaps Ae.e.. are all random variables. In contrast, the current Theorem I does not contain any random variables. Specifically, the significant term related to log d 1 is characterized by the gap Åe, or Ae, which represents the distance from 0.5 and not a random variable.
4 Fixed budget setting
In this section, we investigate Problem 2 and design KC-FB (Algorithm 3). KC-FB is inspired by the successive reject algorithm [6] and exploits KwikCluster to determine the number of queries for each pair adaptively.
Algorithm. KC-FB proceeds in at most n phases and maintains the subset of elements V, C V in each phase r E [n] starting with Vi = V. We denote the set of pairs that can be formed with in V, by (v)
E V,J. In each phase r, the algorithm chooses the pivot Pr uniformly at random from Vr, and pulls each e E Iv. (pr) for appropriately determined T, times. Based on the empirical mean 8, (e) : EE (e) Tr for each e E Ty, (pr). it finds one cluster C, = {pr) U Tv. (pr.3,), where Tv. Vv (p., == {u E V, (, u) > 0.5). and updates Vr+1 + Vn \ Cr. This procedure will be continued until |V/ = 0 and finally the algorithm outputs Cout consisting of all clusters computed. Updating the number of pulls T, (line 8) is a key to prove the statistical property. Intuitively, т, represents a fixed budget of queries when E (7) would be pulled: In the initial phase, we allocate 71 == [T/m to each e E (V)). Notice that the surplus, the sum of the pre- nixfixed budgets of pairs that have been removed without being queried,
(( u} E (V))
is 71 (1(2) - ((2) - ([V) - 1)). because the number of pairs that have been removed in this phase is ((2) - ((2)) ), and among those pairs, the number of pairs that have been actually pulled by
the algorithm is ([Vi-- - 1). This surplus is additionally redistributed equally to each E (V)). This will be also done for the remaining phases = 2,...,n.
7

---

Algorithm 3 KwikCluster with Fixed Budget (KC-FB)
Input Budget T O, set V of objects, additive error Vi < V. < T, < [T/mm], and Cout + 0;
while V do
Pick pivot Pr V, uniformly at random:
Pull each e Iv, for 7r times and observe random feedback {Xx(e))ī=i
Compute empirical mcan (e) Σi= Xx(e)/T,, for each e Iv, (p+); Cout f Cout (.C,) where C, == (pr UT, (p,,8));
Vo+1 Cr;
T 1-11" -(VV.I 1( ((2+1
T++1 c Tr +
and r t +
return Cout.
Analysis. The following theorem states that KC-FB outputs well-approximate solution with high probability. The proof of Theorem is deferred to Appendix D.
Theorem 2. For 0, define the minimal gap Amin. as
c
min max eEE
De for E (0,0.5):
m Eio.s.c)) Ae
for é 2 0.5, where A. = (s((e) 0.5l (Ve E).
min eEE
max
6m
Then, KC-FB (Algorithm 3) uses at most ' queries output Cout that satisfies
2T min.e
Pr[E[costt, (Cout) < 5 OPT(s) + 2 for s 2n exp
(3)
n²
Assuming that each query takes (1) time, the time complexity of iC-FB O(T + n²)).
We can show the random event Pr "n E,] occurs with high probability, where E, = (Ve E Iv. (pr); -,),),,,e)), < max {e, A.) for each phase r E [n]] (See Lemma 8 in Appendix D.1). Under the assumption of such estimation success event n E,, by utilizing the unique feature of KwikCluster, we can maintain the approximation guarantee of KwikCluster in the noise-free setting up additive error (See Lemma in Appendix D.2). Simply combining
Proof Sketch. Sketch.
-
these lemmas with adjusted parameter e' E (0, 0.5), defined 6max [1.1000.aa-)]] if < 0.5 and 6m otherwise, will conclude the proof (See Appendix D.3 for details).
The parameter& å (0, 1) in (3) represents the error probability of Cout being worse than any (5, e)- approximate solution, and it decays exponentially to the querying budget T. larger parameter Amin,e provides the better guarantee; KC-FB performs better when the similarity function clearly expresses similarity (+1) or dissimilarity (-1), as min A. tends to be large.
To evaluate the significance of our results, we analyze the uniform sampling algorithm (Uniform-FB in Appendix E): Uniform-FB queries each e E uniformly [T/m] times to obtain S(e), and then applies any a-approximation algorithm to instance (V,8) of the offline problem minimizing (1). We see that the error probability that the output is not an (a,, apppoxixiee solution is bounded by Tea
O (n² exp which enables us to query essential pairs of elements, i.e., pairs whose estimated similarity values affect the behavior of cluster construction, more times than [T/m]. This leads better performance in the cost of clustering in practice (see Section 5).
a )) In contrast, KC-FB adaptively allocates the budget the remaining pairs,
Comparison with existing PE-CMAB methods in the FB setting. In the literature of PE-CMAB, the FB setting presents even more computational challenges and scarcity of theoretical results. The current state-of state-of-the of-the-art algorithms [6. 25, 36] suffer from one or more of the following issues: (i) inability to handle a partition structure in correlation clustering, (ii) requiring exponential running time, and (iii) lacking any approximation guarantees when the underlying problem is NP-hard. By leveraging the properties of KwikCluster, our approach ensures the polynomial-time complexity of OTT + n?)) while guaranteeing that the probability of obtaining a well-approximate solution exponentially increases with the budget T, along with instance-dependent analysis.

---

5 Experimental evaluation
In this section, we evaluate the performance of our proposed algorithms, KC-FC and KC-FB, using various datasets, providing empirical evidence to support our theoretical findings.
Datasets. We use publicly-availale real- world graphs presented in Table 1. In the FC setting, to observe the behavior of the sample complexity with respect to the hidden minimum gap Amin in (2), we generate our instances as follows. For each graph, we vary the lower bound on Amin. which we denote by I.B in {0.10, 0.15, 0.20, 0.503. For each pair of vertices
Table 1: Real-world graphs used in our experiments.
Name
of vertices
of edges
Description
Lesnis
77
254
Curappearance network
Adjnoun
112
425
Word adjacency network
Football
115
613
Sports leam network
Jazz
198
2.742
Social network
Enail
1,133
5,451
Communication network
ego-Facebook
4,039
88,234
Social network
Wiki Vote
7,066
100,736
Wikipedia voting network
set s(u, v) uniform[0.5 LB3am 1] if u, have edge in the graph, and s(u, v) = uniform[0, 0.5 Li.. otherwise, where uniform (a, bj is the value drawn from the interval [a, b] uniformly at random. On the other hand, in the FB setting, we employ more re- alistic setting: For each graph, our problem instance is generated by embedding the vertices into d- d-dimensional Euclidean space using node2vec [43], obtaining vector vec(u) Rd for each vertex v. Specifically, we used the parameter settings (particularly d 64). Then, define the unknown similarity of each pair of ver- sim.os
Python module of node2vec* with default
tices u, u as s(u, v) (xeecon(Vee()))...... veccv)))) (al())))-mii_eee m-in_cos E [0, 1]. where min_ _aoos and max_co ___o__ss__ are the
max cos mmin_cniee _cs
minimal and maximal cosine similarities, respectively, among all pairs of vertices. We note that max cos >> min cos holds for all instances. In all experiments, noisy feedback when querying a pair e E E is generated by a Bernoulli distribution with mean s(e).
Baselines. We compare our methods with Uniform-FC in the FC setting and Uniform-FB in the FB setting, whose pseudocode and full analysis are given in Appendix E. Uniform- pulls each e E E for 18m22
2m times and employs KwikCluster with respect to the empirical similarity, while log A.
Uniform-FB is its adaption to the FB setting. Moreover, we compare the cost of clustering of our
algorithms with that of KwikCluster having access to the unknown (true) similarity, which is regarded as the stronger baseline than other KwikCluster-based methods for the binary case [11, 15, 40, 76].
Machine and code. The experiments were performed on a machine with Apple MI Chip and 16 GB RAM. The code was written in Python 3, which is available online.
Performance of KC-FC. We evaluate the performance of algorithms in terms of not only the cost of clustering but also the sample complexity. In both KC-FC and Uniform-FC, we set c vn allowing each element to make only 1/vn mistakes, and 6 0.01 following a standard choice in PE-MAB. Taking into account the limited scalability of the algorithms, we only use the instances with n < 1,000. particular, as will be shown later, Uniform-FC requires a large number of samples, which makes the algorithm prohibitive even for quite small instances. Therefore, we do not run the algorithm and just report the sample complexity, which can be calculated without running it. For each LB ami.. we run both KC-FC and KwikCluster having access to the unknown similarity 100 times and report the average value and the standard deviation.
Fooctal
Samppe comtecky
Latform-e Ko-r
Liitom-7
Unitam-FC
Unlom-tC
KoTC
KDTC
KC-FC
JONSE LOUTd Are.
LooE bound Ave.
Lowe bourd Ara.
Lowa bourd on Are
Figure 1: Sample complexity of KC-FC & Uniform-FC.
The results are depicted in Figures and 2. As can be seen, the sample complexity of KC-FC is much smaller than that of Uniform-FC. In fact, the sample complexity of Uniform-FC makes the algorithm
hhttps://githul httpg//gihuuucomaaaeeeeeeee com/atsushiitttecoooooooc http:/assssssiaassaaaaaaaaaaaaee -iyaacciic----a-aaaaa Ca-aaaaaccc/

---

LOSTER
Adjozan
Fousbal
7800
KCFC
KSFC
Kos BC un
Swirdustetk.
3403
307
1204
120
4500
0 0.0
I00
2800
194
(WIE Tourd on
JAt C-S R20
222 3.6 EAV Lower boare
122 222 1.6 1.7 E20
Loaer bound
Lowet boand in dar
Figure 2: Cost of clustering of KC-FC & KwikCluster having the access to the unknown similarity.
prohibitive even for very small instances. Moreover, consistent with the theoretical analysis, as (the lower bound I.B on) Amin increases, the sample complexity of KC-FC becomes smaller. This desirable property is not possessed by Uniform-FC. Remarkably, looking at Figure 2, we see that KC-FC outputs a clustering whose quality comparable with that of KwikCluster having access to the unknown similarity.
Table 2: Cost of clustering of KC-FB & baselines (n 2 1,000).
Name
KC-FB
Unitorm KwilKCluster(V.s)
Email 2go-Facebook
218k
221k=t0.5k
209k:t0.5k
3.716k1336.5k
3,780k 6k
3.373k=59.8k
Wiki-Vote
10,222k:445555k
10,428k
9,749k=34.7k
Performance of KC-FB. Here we evaluate the performance of KC-FB. For small instances with
n < 1,000, we vary 7 in {n²-1 n2.22 ....,; n ..000 and observe the cost of clustering with respect to the budget T. For large instances with n 1,000, we fix T 2.2 for scalability. For each instance and T. we run both KC-FB and Uniform-FB 100 times and report the average value and the standard deviation. As KwikCluster having access the unknown similarity is independent of T' we just run it 100 times for each instance.
Adprsun
Fostball
KC-FR
Uniform-ng KinkCksterl (V:2)
1912
2008
Uni
Unelorms
1912
750
Figure 3: Cost of clustering of KC-FB & baselines (n 1,000).
The results are shown in Figure 3 and Table 2. As can be seen, KC-FB outperforms the baseline method Uniform-FB. In fact, for all instances and almost all values of T, KC-FB outputs better clustering than that of Uniform-FB. We can see that this superiority comes from the fact that KC-FB estimates the unknown similarity better than Uniform-FB thanks to its sophisticated sampling strategy. Indeed, KwikCluster having access to the unknown similarity showcases the best performance, verifying the importance of the precise estimation of the unknown similarity.
6 Conclusions
We studied the online learning problems of correlation clustering, where the similarity function is initially unknown and only noisy feedback is observed. For the FC setting, we devised KC-FC and proved the upper bound of the number of queries required to find clustering whose cost is at most OPT +e with high probability. For the FB setting, we devised KC-FB and showed that the error probability of the expected cost being worse than 5 OPT +e decays exponentially with budget T. Importantly, our algorithms are the first examples of PE-CMAB with NP-hard offline problems. One future work, yet a significant challenge, is to derive information-theorett lower bounds of PE-CMAB in the case where the offline problem is NP-hard. Investigating other variants of correlation clustering exploring the case where the variance of random feedback differs across pairs, namely heteroscedastic noise, would also be worthwhile directions.
10

---

Acknowledgment
The work of Yuko Kuroki is supported by Japan Science and Technology Agency (JST) Strategic Basic Research Programs PRESTO "R&D Process Innovation by Al and Robotics: Technical Foundations and Practical Applications" grant number JPMJPR24T2, and was partially supported by Microsoft Research Asia and JST Strategic Basic Research Programs ACT-X grant number JPMJAX200E while she was The University of Tokyo. The authors would like thank the anonymous reviewers for their insightful comments and useful feedback.
References
[1] Ahmadian, S., Epasto, A., Kumar, R., and Mahdian, M. (2020). Fair correlation clustering, In Proc. Int. Conf. on Artificial Intelligence and Statistics (AISTATS), pages 4195-4205.
[2] Ailon, N., Bhattacharya, A., and Jaiswal, R. (2018). Approximate correlation clustering using same-cluster queries. In Proc. Latin American Symp. on Theoretical Informatics (LATIN), pages 14-27.
[3] Ailon, N., Charikar, M., and Newman, A. (2008). Aggregating inconsistent information: Ranking and clustering. Journal of the ACM, 55(5):1-27.
[4] Aronsson, L. and Chehreghani, M. H. (2024a). Correlation clustering with active learning of pairwise similarities. Transactions on Machine Learning Rexearch.
[5] Aronsson, L. and Chehreghani, M. H. (2024b). Effective acquisition functions for active correla- tion clustering.
[6] Audibert, J.-Y., Bubeck, S., and Munos, R. (2010). Best arm identification in multi-armed bandits. In Proc. Conf. on Learning Theory (COLT), pages 41-53,
[7] Bansal, N., Blum, A., and Chawla, S. (2004). Correlation clustering. Machine Learning. 56(1-3):89-113.
[8] Barrier, A., Garivier, A., and Stoltz, G. (2023), On best-arm identification with a fixed budget in non- non-parametric multi-armn bandits. In Proc. Int. Conf. on Algorithmic Learning Theory (ALT), pages 136-181.
[9] Ben-Dor, A., Shamir, R., and Yakhini, Z. (1999). Clustering gene expression patterns. Journal of Computational Biology, 6(3/4):281-29)
[10] Bonchi, F., Gareía-Soriana D., and Gullo, (2022). Correlation Clustering, volume 12 of Synthesis Lectures on Data Mining and Knowledge Discovery. Morgan & Claypool Publishers.
[11] Bonchi, F., Gareia-Soriano, D., and Kutzkov, K. (2013a). Local correlation clustering, arXiv preprint 112
[12] Bonchi, F., Carcfa-Soriano, D., and Liberty, E. (2014). Correlation clustering: From theory to practice. In Proc. ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining (KDD).
[13] Bonchi, F. Gionis, A., Gullo, F., Tsourakakis, C., and Ukkonen, A. (2015). Chromatic correlation clustering. ACM Transactions on Knowledge Discovery from Data, 944:1124.
[14] Bonchi, F., Gionis, A., and Ukkonen, A. (2013b). Overlapping correlation clustering. Knowledge and Information Systems, 3-(1):1-32.
[15] Bressan, M., Basa-Bianchi,, N., Paudice, A., and Vitale, F. (2019). Correlation clustering with adaptive similarity queries. In Proc. Conf. on Advances in Neural Information Processing Systems (NeurIPS), pages 12510-12519.
[16] Bubeck, S. and Desa-Bianchi, N. (2012). Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends@ in Machine Learning, 5:1-1
[17) Bubeck, S., Munos, R., and Stoltz, G. (2011). Pure exploration in finitely-armed and continuous- armed bandits. Theoretical Computer Science, 412(19):1832 1852.

---

[18] Cesa-Biance -iaanhi, N. and Lugosi, G. (2006). Prediction. Learning, and Games. Cambridge University Press.
[19] Cesa-Bianchi, N. and Lugosi, G. (2012). Combinatorial bandits. Journal of Computer and System Sciences, 18055:1404-144
[20] Charikar, M., Guruswami, V., and Wirth, A. (2005), Clustering with qualitative information. Journal of Computer and System Sciences, 7163):360-383.
[21] Chaudhuri, A. R. and Kalyanakrishnan, S. (2019). Pac identification of many good arms in stochastic multi-armed bandits. In Proc. Int. Conf. on Machine Learning (ICML), pages 991-1000.
[22] Chawla, S., Makarychev, K., Schramm, T., and Yaroslavtsev, G. (2015). Near optimal LP rounding algorithm for correlation clustering complete and complete k-partite graphs. In Proc. ACM Symp. on Theory of Computing (STOC), pages 219-228.
[23] Chen, L., Gupta, A., and Li, J. (2016a). Pure exploration of multi-armed bandit under matroid constraints. Proc. Conf. on Learning Theory (COLT), pages 647-669.
[24] Chen, L. and Li, J. (2015). On the optimal sample complexity for best arm identification. arXiv preprint arXiv: 15..03777
[25] Chen, S., Lin, T., King, I., Lyu, M. R.,, and Chen, W. (2014a). Combinatorial pure exploration of multi-armann armddd bandits. Proc. Conf. on Advances Neural Information Processing Systems (NIPS), pages 379-387.
[26] Chen, W., Wang, Y., and Yuan, Y. (2013). Combinatorial multi-armed bandit: General frame- work and applications. In Proc. Int. Conf. on Machine Learning (ICML), pages 151-159.
[27] Chen, W., Wang, Y., Yuan, Y., and Wang, Q. (2016b). Combinatorial multi-armed bandit and its extension to probabilistically triggered arms. Journal of Machine Learning Research, 17(50):1-33,
[28] Chen, Y., Jalali, A., Sanghavi, S., and Xu, H. (2014b). Clustering partially observed graphs via convex optimization. Journal of Machine Learning Research, 15(1):2213222) 3-2238.
[29] Chierichetti, F., Dalvi, N., and Kumar, R. (2014). Correlation clustering in MapReduce. In Proc. ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining (KDD), page 641-650.
[30] Cohen-Addad, V., Lee, E., Li, S., and Newman, A. (2023). Handling correlated rounding error via preclustering: A 1.73-aprroximation for correlation clustering. In Proc. IEEE Symp. on Foundations of Computer Science (FOCS), pages 1082-1104.
[31] Cohen-Addad, V., Lee, E., and Newman, (2022). Correlation clustering with Sherali-Adame In Proc. IEEE Symp. on Foundations of Computer Science (FOCS), pages 651-661.
[32] Davies, S., Moseley, B., and Newman, H. (2023). Fast combinatorial algorithms for min max correlation clustering. In Proc. Int. Conf. on Machine Learning (ICML), pages 7205-7230.
[33] Degenne, and Koolen, W. M. (2019). Pure exploration with multiple correct answers. In Proc. Conf. on Advances in Neural Information Processing Systems (NeurIPS), pages 14591-1460.
[34] Demaine, E. D., Emanuel, D.,, Fiat, A., and Immorlica, N. (2006). Correlation clustering in general weighted graphs. Theoretical Computer Science, (61
[35] Du, Y., Kuroki, Y., and Chen, W. (2021a). Combinatorial pure exploration with bottleneck reward function. In Proc. Conf. on Advances in Neural Information Processing Systems (NeurIPS), pages 23956-23967.
[36] Du, Y., Kuroki, Y., and Chen, W. (2021b). Combinatorial pure exploration with full-bandit or partial linear feedback. In Proc. AAAI Conf. on Artificial Intelligence (AAAI), pages 7262-7270.
[37] Even-Dar, E., Mannor, S., and Mansour, (2002). PAC bounds for multi-armed bandit and Markov decision processes. In Proc. Conf. Learning Theory (COLT), pages 255-270.
12

---

[38] Even- Oeen-Dar,&a E.. Mannor, S., and Mansour, Y. (2006). Action elimination and stopping conditions for the anmti- bandit and reinforcement learning problems. Journal of Machine Learning Research, 7:1079-1105.
[39] Fiez, T., Jain, I.., Jamieson, K. G., and Ratliff, L. (2019). Sequential experimental design for transductive linear bandits. In Proc. Conf. on Advances in Neural Information Processing Systems (NeurIPS), pages 10667-10677.
[40] Garcia-Sorianc D., Kutzkov, K., Bonchi, F., and Tsourakakis, C. E. (2020). Query-efficient correlation clustering. In Proc. The Web Conference, pages 1468-1478.
[41] Garivier, A. and Kaufmann, E. (2016). Optimal best arm identification with fixed confidence. Proc. Conf. on Learning Theory (COLT), pages 998-1027.
[42] Gionis, A., Mannila, H., and Tsaparas, P. (2007). Clustering aggregation. ACM Transactions Knowledge Discovery from Data, 1(1).
[43] Grover, A. and Leskovec, (2016). Node2vec: Scalable feature learning for networks. In Proc. ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining (KDD), page 855-864.
[44] Gullo, F., Mandaglio, D., and Tagarelli, A. (2023). A combinatorial multi-armed bandit approach to correlation clustering. Data Mining and Knowledge Discovery, 37:1-62.
[45] Gupta, S., W Staar, P., and de Sainte Marie, C. (2024). Clustering items from adaptively collected inconsistent feedback. In Proc. Int. Conf. on Artificial Intelligence and Statistics (AISTATS), pages 604-612.
[46] Hassanzadeh, O., Chiang, F., Lee, H. C., and Miller, R. J. (2009). Framework for evaluating clustering algorithms in duplicate detection, Proc. the VLDB Endowment (PVLDB), 2(1):1282- 1293.
[47] Huang, W., Ok, J., Li, L., and Chen, W. (2018). Combinatorial pure exploration with contin- uous and separable reward functions and its applications. In Proc. Int. Joint Conf. on Artificial Intelligence (IJCAI), pages 2291-2297.
[48] Jamieson, K., Malloy, M., Nowak, R., and Bubeck, S. (2014). UUU An optimal exploration algorithm for multi-armed bandits. Proc. Conf. on Learning Theory (COLT), pages 423-439.
[49] Joachims, T. and Hopcroft, J. E. (2005), Error bounds for correlation clustering. In Proc. Int. Conf. on Machine Learning (ICML), pages 385-392. ACM.
[50] Jourdan, M., Mutný, M., Kirschner, J., and Krause, A. (2021). Efficient pure exploration for combinatorial bandits with bani-bandit feedback. In Proc. Int. Conf. on Algorithmic Learning Theory (ALT), pages 805-849.
[51] Kano, H., Honda, J., Sakamaki, K., Matsuura, K., Nakamura, A., and Sugiyama, M. (2019). Good arm identification via bandit feedback. Machine Learning, 108:721-745.
[52] Katz-Samuels, J., Jain, L., Karnin, Z., and Jamieson, K. (2020). An empirical process approach the union bound: Practical algorithms for combinatorial and linear bandits. In Proc. Conf. on Advances in Neural Information Processing Systems (NeurIPS).
[53] Kaufmann, E.. Cappé, O., and Garivier, A. (2016). On the complexity of best-arm identification in multi-armed bandit models. Journal of Machine Learning Research, 17:1-42.
[54] Kim, S., Nowozin, S., Kohli, P., and Yoo, C. D. (2011). Higher- correlation clustering for image segmentation. In Proc. Conf. on Advances in Neural Information Processing Systems (NIPS), pages 1530-1538.
[55] Kuroki, Y., Miyauchi, A., Honda, J., and Sugiyama, M. (2020a). Online dense subgraph discovery via blurred-graph feedback. Proc. Int. Conf. on Machine Learning (ICML), pages 5522-5532.
13

---

[56] Kuroki, Y., Xu, L.. Miyauchi, A., Honda, J., and Sugiyama. M. (2020b). Polynomial-tinn time algo- rithms for multiple-arm identification with full-bandit feedback. Neural Computation, 32(9))17333- 1773.
[57] Lai, T. L. and Robbins, H. (1985). Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6
[58] Larsen, K. G., Mitzenmacher, M., and Tsourakakis, C. E. (2020). Clustering with a faulty oracle. Proc. The Web Conference, page 2831-2834.
[59] Lattimore, T. and Szepesvári, C. (2020). Bandit Algorithms. Cambridge University Press.
[60] Locatelli, A., Gutzeit, M., and Carpentier, A. (2016). An optimal algorithm for the thresholding bandit problem. In Proc. Int. Conf. on Machine Learning (ICML), pages 1690-1698.
[61] Makarychev, K. and Chakrabarty, S. (2023). Single-pass pivot algorithm for correlation clustering. Keep it simple! In Proc. Conf. Advances in Neural Information Processing Systems (NeurIPS).
[62] Makarychev, K., Makarychev, Y., and Vijayaraghavan, A. (2015). Correlation clustering with noisy partial information. Proc. Conf. on Learning Theory (COLT), pages 1321-1342.
[63] Mason, B., Jain, L., Tripathy, A., and Nowak, R. (2020), Finding all e-good arms stochastic bandits. In Proc. Conf. Advances in Neural Information Processing Systems (NeurIPS), volume 33, pages 20707-20718.
[64] Mathieu, C. and Schudy, W. (2010). Correlation clustering with noisy input. In Proc. ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 712-728.
[65] Mazumdar, A. and Saha, B. (2017). Clustering with noisy queries. In Proc. Conf. on Advances in Neural Information Processing Systems (NIPS), page 5790-5801.
[66] McCallum, A. and Wellner, B. (2005). Conditional models of identity uncertainty with applica- tion to noun coreference. In Proc. Conf. on Advances in Neural Information Processing Systems (NIPS), pages 905-912.
[67] Nakamura, S. and Sugiyama. M. (2024). Thompson sampling for real-valued combinatorial pure exploration of multi-armed bandit. In Proc. AAAI Conf. on Artificial Intelligence (AAAI).
[68] Nepusz, T., Yu, H., and Paccanaro, (2012). Detecting overlapping protein complexes in protein-protein interaction networks. Nature Methods, 9(5):771-472.
[69] Pan, X., Papailiopoulos, D., Oymak, S., Recht, B., Ramchandran, K., and Jordan, M. I. (2015).
Parallel correlation clustering on big graphs. In Proc. Conf. on Advances in Neural Information Processing Systems (NIPS), pages 82-90.
[70] Peng, P. and Zhang, J. (2021). Towards query-optimal and time-efficient algorithm for clustering with a faulty oracle. In Proc. Conf. on Learning Theory (COLT), pages 3662-3680.
[71] Pia, A. D., Ma, M., and Tzamos, C. (2022). Clustering with queries under semi-random noise. Proc. Conf. on Learning Theory (COLT), pages 5278-5313.
[72] Ramachandran, A., Feamster, N., and Vempala, S. (2007). Filtering spam with behavioral blacklisting. In Proc. ACM Conf. on Computer and Communications Security (CCS), pages 342-351.
[73] Robbins, H. (1952). Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, 58:527-535.
[74] Saha, B. and Subramanian, S. (2019). Correlation Clustering with Same-Cluster Queries Bounded by Optimal Cost. In Proc. European Symp. on Algoritlums (ESA), pages 81:1-81:17.
[75] Shamir, R., Sharan, R., and Tsur, (2004). Cluster graph modification problems, Discrete Applied Mathematics, 14431-2):13-1182
14

---

[76] Silwal, S., Ahmadian, S., Nystrom, A.. McCallum, A., Ramachandran, D., and Kazemi, S. M. (2023). Kwikbucks: Correlation clustering with cheap-weak and expensive-strong signals. In Proc. Int. Conf. on Learning Representations (ICLR).
[77] Tsourakakis, C. E., Mitzenmacher, M., Larsen, K. G., Blasiok, J., Lawson, B., Nakkiran, P., and Nakos, V. (2020). Predicting positive and negative links with noisy queries: Theory & practice.
[78] Tzeng, R.-C., Wang, P.-A., Proutiere, A., and Lu, C.-J (2023). Closing the computational- statistical gap in best arm identification for combinatorial cemi-bandits. In Proc. Conf. on Advances in Neural Information Processing Systems (NeurIPS).
[79] Veldt, N. (2022). Correlation clustering via strong triadic closure labeling: Fast approximation algorithms and practical lower bounds. In Proc. Int. Conf. on Machine Learning (ICML), pages
[80] Wang. J., Kraska, T., Franklin, M. J., and Feng. J. (2012). Crowder: Crowdsourcing entity resolution. Proc. the VLDB Endowment (PVLDB), 5(1 1):1433-1494.
[81] Wang. Q. and Chen, W. (2017). Improving regret bounds for combinatorial cemi-bandits with probabilistically triggered arms and its applications. In Proc. Conf. Advances in Neural Information Processing Systems (NeurIPS), page 1161-1171.
[82] Wang, S. and Zhu, J. (2022). Thompson sampling for (combinatorial) pure exploration. In Proc. Int. Conf. on Machine Learning (ICML), pages 23470-23483.
[83] Xia, and Huang, Z. (2022). Optimal clustering with noisy queries via multi-armed bandit, In Proc. Int. Conf. on Machine Learning (ICML), pages 14315-243311
15

---

Appendix
A Additional comparison with other clustering models
Cluster recovering with noisy same-cluster queries. Another line of studies has focused on clustering reconstruction with noisy same-cluster queries, which was first proposed by Mazumdar and Saha [65] and further investigated by Larsen et al. [58], Peng and Zhang [70], Pia et al. [71], Tsourakakis al. [77] and Xia and Huang [83]. In this model, given a set of n elements, the goal is to recover the underlying ground-truth k- k-clustering by asking pairwise queries to an oracle, which tells us if the two elements belong to the same cluster, but whose answer correct only with probability G. Recently, Gupta al. [45] first considered noisy and inconsistent oracle, in contrast to consistent oracle that returns the same answer when queried. Although this clustering reconstruction problem shares the intuition with correlation clustering. there are also important differences which do not allow to transfer algorithmic results from one to the other. Firstly, in correlation clustering the input information might be inconsistent (e.g., very similar b, which very similar c, but a is not similar to c), instead in clustering reconstruction this is not possible: if a is in the same cluster of b and b in the same cluster of c, then is in the same cluster of c. Secondly, the aim is to reconstruct the exact underlying clustering, while we aim at minimizing the cost function in (I). Lastly and more importantly, the number of clusters is part the input to the problem, while in correlation clustering it is unknown. Therefore, the theoretical results and techniques for solving the clustering reconstruction problem cannot be directly applied to correlation clustering.
Query-based correlation clustering. As fully discussed the main text, our work lies in query- efficient correlation clustering, for which we utilize the methodology of PE-CMAB. Table 3 summa- rizes how existing query-based settings differ from our attempt. Note that the oracle in Aronsson and Chehreghani [4, 5] is assumed to return the true value of s(x, 3) with probability 1 y and a noisy value with probability 7, which is different from our models; we only observe a random
variable independently sampled from an unknown distribution with mean s(x, y) E [o. 1]. While one might consider using majority voting on repeated queries to handle noise when the underlying distribution is Bernoulli, this approach lacks any approximation guarantees and query complexity bounds. Moreover, for R-sub-Gaun GaubGaa noise, majority voting is not well-defined. Instead, using sample mean estimates, as done in PE-MAB methods, is standard. Our approach leverages these principles, ensuring a (5, apppoxiaooiiiiiioonn guarantee with fewer queries and statistical guarantees.
Table 3: Different problem settings in correlation clustering with queries.
Feature/Study
Similarity
Similarity
Oracle
Theoretical Guarantce
Function
Type
Ailon et al. [2]
Saha and Subramanian [74]
Known
Binary
Strong with access to same-cluster
querics in the optimal clustering
Bonchi al. [11]
Bressan al. [15]
Unknown
Binary
Strong with access to the true value of s(ar,) E {0. 1}
Garcia-Soriamo el ul. [40]
Silwal et al. [76]
Unknown
Binary
Both strong with access to the true
value of s(ar.)) E {0. 1] and noisy
Aronsson and Chehreghani [4. 5]
Unknown
Weighted
Noisy (true value s(x,8) is re-
Not provided
turned with probability 1 and
noisy value is retuned otherwisc)
Our Work
Unknown
Weighted
Noisy (stochastic feedback)
B Pseudocode of KwikCluster and Algorithm 5
We detail the pseudocode of KwikCluster [3] in Algorithm 4. The approximation guarantee of KwikCluster is 5 for the weighted similarity case (and 3 for the restricted binary similarity case). We also detail the pseudocode of Algorithm 5, which sequentially uses TB-HS at each phase the framework of KC-FC.
16

---

Algorithm 4 KwikCllster(V.s)
Input Set V of n objects, and similarity function s
C f- 0;
2 while V > 0 do
Pick pivot E V uniformly at random:
Cu (ptC where Cp = (p) u :sp 0.5}:
Vev/o Cp:
return C
Algorithm 5 KC-FC variant with sequential use of TB-HS
Input Confidence level 6, set V of n objects, and error
Ei <- E. Ví < V. r <- 1, and Cour < 0;
while V,I > 0 do
Pick pivot pr V, uniformly at random:
Let (p,) E be the set of pairs between the pivot Pr and its neighbors in Vy;
11
c. == (v2 (pr))):
Compute G by TB-HS (Algorithm 2) with the input of error e, confidence level ó/n, and the set of pairs Lv, (pr);
Define (v) == {u E V {u, E G.:
Cout + Cout (frr), where C, = ((pr) (p.)) 14
15
VA+1 V, C, and + 1
return Cout.
C Analysis of KC-FC
In this section, we provide complete proof of Theorem in Section 3. In particular, Lemma guarantees the accuracy of the subroutine TB-HS, and based this, Lemma 5 assures the (5, e)- approximation using the properties of KwikCluster. Moreover, Lemma establishes an upper bound crucial for the sample complexity via novel analysis dependent and Amin (Lemma 7). Finally, by combining the sample complexity required by subroutine TB-HS (Lemma 6) and the output guarantee of KC-FC (Lemma 5), Theorem is demonstrated.
C.1 Basic lemmas
first introduce the Hoeffding inequality, which will be frequently used in our proof. Note that consider Bernoulli distribution for the sake of simplicity, but results would carry for R-sub-Gaussiae distribution by simply adjusting the Hoeffding inequality for the case accordingly.
Lemma (Hoeffding inequality for bounded random variables). Let X1y..., Xx be k independent random variables such that, [[X,] = p. and S X, S for each i [k)]. Let X Σk X; denote the average of these random variables. Then, for any X >> 0, we have
(-10-)) a)
21
S X] S exp
The next lemma presents the probability that some random event happens, which will be used later. Lemma 2. Let Be.k be the empirical mean of the rewards when has been pulled k times. For each e E [m] and ki, define the random event Ee, as follows:
log (ms(4mk2//
Ee = (s(e) -e, <
Let Ex, be the random event that for all E [m]) the random event Ee,k happens. Then we have
Pr Ex 2 8.

---

Proof of Lemma 2.
We have
logí log(4ml) (4mkk)
2
Pr E
Eo,k
Pr
((())
Se,al
2k
2mk
12m
m
L
A=
k=
where the first inequality follows from the Hoeffding inequality (Lemma 1). Therefore, by taking the union bound, we have
Pr
&k
Pr
U
Ece
8.
<E k=1
C.2 Approximation guarantee
We provide the following lemmas for guaranteeing the quality of the output.
Lemma 3. Let E (0, 0.5) and ó (0, TB-HS (Algorithm 2) with parameter c, outputs, with probability least 8, G. and Be such that
s(e) 2 0.5 e for every e Ge,
s(e) S 0.5 + for every E Be:
G. u B. = E, G.n 0.
Proof of Lemma 3. The proof is almost straightforward by the procedure of the algorithm, line 8 and 10, as follows. By Lemma 2, we have Pr Pr & 2 1 5. Now we assume that N & happens. Let t 0 be the stopping time, where every e E E has been added to either G, or B.. For e E G.. from the stopping condition and the random event n &x. it is easy to that 8(e) 2 (e) - rady (e) 2 0.5 e, where I' denotes the round that arm e was added G.. For E Be, it is also easy to see that s(e) S (e) - rade (e) < 0.5 + e, where l' denotes the round that arm was added to B.. The third condition is obvious from the stopping condition of the algorithm.
Lemma 4. Let E 0.5) and d E 1). Let G. and B, be the output of TB-HS (Algorithm 2) with parameters e, 8. Then, with probability at least 1 5, we have that (i) every e E(o.5+c,1] included in Go, and (ii) every E0,,0.5-e) is included in B..
Proof of Lemma 4. We have Pr [ - Ex] 2 - by Lemma 2 again, and we assume that n Ek happens. Consider any e [00.5-e.11 Suppose that is not included in G.. Then, from Lemma we see that B,, and thus s(e) < 0.5 + which contradicts the fact that E Eqo.s+e.1). Therefore, e is included G. Similarly, consider any e E E10.0.5-r-- Suppose that e not included in B. Then, from Lemma 3, that E Ge, and thus s(e) 2 0.5 c, which contradicts the fact that E Fip.0.5-e-- Therefore, is included in B,.
Based on Lemma 4, prove the following key lemma.
Lemma 5 (Approximation guarantee). Let e E (0, 0.5) and (0, 1). With probability at least 1 -- 8, the output Cout of KC-FC (Algorithm 1), where subroutine TB-HS (Algorithm 2) is invoked with parameters e, is a (5, (eeeBipstel)-appppooa problem minimizing (1).
solution for instance (V,s) of the offline
Proof of Lemma 5. By Lemma 4, we have E(0.5+e,1) C G and Ejo,u.-e) C B. w.p. at least 1 8.
Construct the similarity function á. E + [0, 1] such that for each E E,
s(e) if Epo.0.--) U Eco.s.r,1):
5(e)
otherwise,
18

---

where Se is an arbitrary value that satisfies (s(e) - < 2c. Consider running KwikCluster with the similarity Let Co be the output of this algorithm. Then we have (Ccos)
< (Coo )1 + 2e 26| Bjo.stte
- 5 OPT + 2c| E Elo.5:+e]
< 5 (OPT(s) + 2c| (o + 2c Ejo.sael
5 OPT(s) + 12e|
Noticing that KC-FC corresponds to the above algorithm associated with certain choice of 5 (i.e., be for e E E)o. we have the lemma.
C.3 Sample complexity analysis and proof of Theorem
We prove the following main lemma evaluate the sample complexity of TB-HS. Let mg be the number of pairs (i.e., arms) whose similarity is no less than threshold 0.5. Without loss of generality, we assume that E [m] indexed as s(1) .... 2....ssm... 2 0.5 s(mg + +1) ....2
s(m) in whole analysis.
Lemma 6 (Sample complexity). The upper bound of the sample complexity of TB-HS (Algorithm 2) with parameters 0.5) and 5 E (0, 1) is
(vm/5 log A2 2,6
vm/ō ))
T == O Σ
m
log
A2
22
max Amin. < c/2}2
VEEE
E,E
To prove Lemma 6, we begin with the following lemma. Recall that Âe, and A defined by (2). Lemma 7. Let E 0.5) and d E 10, Define
1
(4/m/8
5 m//
ke =
log
log
A2
A2
A2
Let Se,k Be, log(1mkk2/0) /5) and Se,k := Be V log log(1mk2//)) 2k
where Be,k is the empirical mean
2h of the rewards when has been pulled ls times. If k. 2 ke holds, then
Pr[se, k S 0.5 c] I cxp(-2k max min c/2)2), Ve E [m,].
Pr|se,k 2 0.5 - e] S exp(- 1 2k max Ains e/2}?), Ve E [m] \ [mg]
It also holds that
E
1
[S S 0.5 -
Ve E [mg]. < lic + 2 max Amiu c/2]2*
E
1 B 0.5 cc
< ke +
Ve [m] [my]
2 maxf e/2]2*
Proof of Lemma 7, Suppose that
log( 4mkk///// (8)
E < A. max Amin
2k
2
Then, for each E [mg]. we have
log (mik2mk22/ 2/2k2/8)
Pr(s.,x 0.5 c) = Pr
Se,k - s((s < - -c V
2k
< Pr
Be, s(e) & - - c A. - -max Amin
-
E
= Pr
Se.t s(e) < - max Amin, 2
(Amiu
c $12)
< exp
-2k max
2
19

---

where the last inequality follows from the Hoeffding equality (Lemma 1). Now we show, via similar analysis of Lemma in Kano al. [51], that for kes it indeed holds that
log 4mk2/
< A. max Amin C, -2
(5)
2k
Let Co = (Ao + min {e Amin 21)² for simplicity, Then we can rewrite k 2 ki as
41 mm/m
log
Ce
Ce
5y m//h 6z
for some / > log
1. Then have
log 1og(4m22/00 I A. + min {o
Amin:
2k
2
+ log(4mk² 18) S 2cck
4t/m/6
4m
log
16t m cg0
+ log
log
c/
4t 4t/m// m66
+ log
S 2t
Ce
4 4ym/0
+ t - 1 1+ log
S 2t
Ce
4/m888
+ log
<t,
Ce
where e is the base of natural logarithms and log / S ( - is used. Therefore, 2 log 5y/m66 sufficient to fulfill (5).
is
The second statement of Lemma 7 can easily be shown by adapting the proof of Lemma 3 in Kano al. [51]. For each E [m,], we have
he
1 [SS S 0.5 - |]
E
1 [se.k I 0.5 - c)
< R
k=ke+1
ke
Prisa, 5.. cc
k=1
< hi
+
exp( - 23: max Amiu. e/232)
k=1
< he +
c max Amin Aaii 2/23
S he + 2max Amin, c/2}
For e [m] [my]. we omit the proof, as the analysis is essentially the same as the case for
E [m,]
D
20

---

Proof of Lemma 6. Let a(t) E (2) Then we have
denote the selected pair (i.e., arm) by the algorithm in round t.
T Ma(l) E [m].
Σ [a((t) [myl < TT + Σ 1 [a(t) [m] \myltt
[a(()) E [myl]
[a(t) E [m] \ [myl]
[a((t = +| +
Σ
la((t) = e]
eE m [=1
[m, t=1
[a((t) (.c) k]
l[a(t) Nc(e) =
e5 [m
e cE(m]} [m)] [m]]] t= k=1
= eal()=,,N(C k)
+ Σ Σ
(aal)) = e, N.(e) =k} }
eE|ma]
cEIm] Mm)] k=
1=1
where the third inequality follows from the fact that event {a(t) Ni k} occurs for at most one E N. For e E [mg]. we have
Σ A=1
N. = k}
SE
Σ 1 [ S -
S lie + 2max (min; e/222²
where the second inequality follows from Lemma 7. Similarly, for each e [m]] [my]. we have
Σ Uia(t)= = N.(e) = k} 1==
SE
Σ 1==1
[5. 2 0.5 +.5 +c]
S ke +
1
2 mmax Amin, e/2)2
Therefore, by combining the above, we have
m 2 max Amin e/2]2'
T
ke +
which concludes the proof.
Proof of Theorem I. Finally, we are ready to complete the proof of Theorem 1. In KC-FC, TB-HS run with parameter e' < and confidence Therefore, by Lemma 5 for é', we have the approximation guarantee:
12m
E(coot, < 5 OPT(s) + 12e' (2ce(B).stee)) < 5 SPPP(s) +
The sample complexity of KC-FC is equal to that of TB-HS with parameters 8,,8, which is given by Lemma 6 for e',ò.
D Analysis of KC-FB
In this section, we prove Theorem 2 in Section 4.
D.1 Basic analysis of some random event and its occurrence probability
The following lemma states that 8, for phase r E [r]] well-estimated with high probability. The
proof is almost straightforward from the Hoeffding inequality (Lemma 1) and union bounds.
21

---

Lemma 8. Lete (0, 0.5). Given phase E [ni], we define the random event
E = (Ve Iv, (v,(,,), (s(e) Se( < max (c, A.)).
Then, we have
2T min E max fc, A,
Pr
&
2 2n exp exp
n²
Proof. We first evaluate Pr (() s(c) 2 max {c, Ae]] for fixed phase E [n] and E Iv. (pr)- Each E Iv, (pr) has been pulled at least [T/m] times because the initial budget for the pair was set to TI = [T/m] and the budget has not decreased the later iterations. Then we have
Pr (e) s(e) 2 max {e, A.J] Pr
Xx(e)/Tr- - -((e)
2 max {er Ao)
< Pr
Xx(e)/T, s(e)
2 max {e, A
k=1
2 2xxp
-2,, max {e, Ae)
2T max {e, Ae
2exp
m
where the second inequality follows from Lemma 1. Taking union bound for E [x]] and all e E Iv. (pr), we further have
Pr
&
Σ
Σ
Pr [r] s(e) 2 max fc. A.Hl
r=1 clley, (pr)
2
Σ Σ
Σ
Pr[[s((e) - s(e)) 2 max fc, Acll
WEV. (1),
2T max {c, A
21 ΣΣ Σ
2exp
m
VEV (E)
2T min.gr max {e, A0}² m
=1 Σ
2/V- 1vv
2T min g max {e, Ae}² m
=1 Σ
2/V7 - exp
27 minegr max {e, Ao}²
2 Σ 2n exp
m
21 min.gg max {e, )
1 - 2 exp
m
where the third inequality follows from (7).
D.2 Theoretical guarantee of the output
Next we prove a key lemma that provides the theoretical guarantee of the output Cout of KC-FB.
Lemma 9, Let e (0, 0.5). Under the assumption that Dr= E, happens, the output Cout of KC-FB is a (5, 6e| Epo lappprxxmmatttt solution for instance (V,s) of the offline problem minimizing (1).
Proof. Let E C be the set of pairs that have been pulled in the algorithm. For == {u, v) E Σ, let be the phase, in which either or is selected pivot. Construct the weight 5 E - [0, such
22

---

that for each e E E,
s(c) Sr. (c) s(e)
if E E(o.5t:) 0 E,
otherwise.
Consider running KwikCluster (Algorithm 4) with the similarity 8 while respecting the selection of pivots py of KC-FB, that is, in the r-th iteration, the algorithm selects the pivot p, it exists. In the first iteration, the algorithm definition of's and the assumption the lemma, we have Fv, (P1.3) 3) = Tv, (P1, $1). In fact, for any element in Ví (except for p1), the cluster produced exactly the same as C1 in KC-FB. In the second iteration, the algorithm can select P2 because P2 not contained in the cluster of the first iteration, and by applying the same argument as above, we see that the cluster this iteration is exactly the same as C2 in KC-FB. The later iterations can be handled in the same way. Therefore, we see that the output of the above algorithm coincides with that of KC-FB.
select the pivot P1 and construct the cluster {p1) UT v. (P1.5). By the
that 5(p1, u) > 0.5 if and only S(p) u) > 0.5. Therefore,
Then it suffices show that the output of the above algorithm has the desired approximation guarantee. Let C.ue be the output of the above algorithm. Recalling that KC-FB picks pivot pt uniformly at random, have
E E/cost, (C'ut)
v T6| ((oost Flo..=e))
< 5 OPT(P) P(o.
s (OPT(s) c| + p..s4ll
5 OPT(s) 6e (oostell
where the first and third inequalities follow from the fact that s(e) and ((e) may be different only for E Blo.stte) (n E) and the difference there is at most from the assumption of the lemma.
D.3
Proof of Theorem 2
Proof of Theorem 2. For > define e' E (0, as 6 [ if < 0.5 and 6m
other-
wise. By Lemma 8 for é', we have that
2T mineeg max (e', Ac)
Pr
&
2 - 2n2 exp
n²
where & is the random event for phase r E (1,.....,) n) that is defined by (6) with e'. Therefore, using Lemma for c', we that the output Cout of KC-FB is a (5, a)apprxxima solution for instance
2T min.e max c'A.) }
(V,s) of the offline problem minimizing (1) w.p. at least - 2n exp
Finally, we can easily confirm that KC-FB does not exceed the given budget due to the algorithm procedure of line 8, which coneludes the proof.
E
Uniform sampling algorithms
Here we provide the complete description and analysis of the naive uniform-sampling algorithms for both the FC setting (Algorithm 6) and the FB setting (Algorithm 7). Note that in the FC setting, no feasible stopping conditions are known from previous studies to guarantee that the output is an approximate solution, even with uniform or arbitrary sampling strategies. Therefore existing analysis of uniform sampling given in Chen et al. [25] is not applicable to our case with offline optimization being ha-hard.
First, we show a basic analysis of the cost of clustering when the estimate $ is close to the unknown similarity
Lemma 10. Let E 0.5.. Assume that (s(e) - -B(e)) S for every E E. Let Cant be the oulput of any a-approximation algorithm for instance (V,8) of the offline problem minimizing (1). Then Cout is (a, (a + (eem)aapprximmat solution for instance (V,s) of the offline problem.
23

---

Algorithm 6 Uniform sampling in the FC setting (Uniform-FC)
Input Set V of n objects, confidence level 6, additive error
2m for each E E; 5 2 Sample each E E for Tee) times and compute empirical mean 8(e);
[m=1))m² log T(e) - 2c
C < solution of approximation algorithm for instance (V,8) of the offline problem minimizing
(1);
return Cout ==
Algorithm 7 Uniform sampling the FB setting (Unilorm-FB) Input Set V of objects, budget T
Sample each E for [T/m] times and compute the empirical mean S(e);
C solution of an approximation algorithm for instance (V,8) of the offline problem minimizing (I);
return
Cout == C
Proof. We have
E coost (Cout)
< [[(oosy(Cout]] + em
S a (PPOPT(S) + em
< a: (OPT(s) + em)
= a OPT()) (a - 1)em.
Next we evaluate the performance of Algorithm 6.
Proposition 1. Given confidence level 8 (0, 1) and an additive error E 00,0.5), the uniform sampling algorithm with an a-approximation oracle for the FC setting (Algorithm 6) outputs Cout that satisfies
Pr [costig (Cout) (O-P(((s) + 2 1-6,
and the upper bound of the number of samples is
T T= n log
2n
Proof. As the algorithm samples each e E E for T(e) times, by the Hoeffding incquality (Lemma 1), it holds that
2cxp (- (T 1)3m²
(T(e))²
Pr
[s(e) - s(e)) (a 1)m
Note that T(e)= >
(a+1)²m² 22a
2m gives log
o
(T(e)c exp [a+ 1)2m²
5 2m
S
Therefore, by taking a union bound, we have
Pr ((e) s(e)) < (a 1)m"
Ve E
2 1 6.
By Lemma 10 for (a+t) we see that Cout is an (ax, e) apprroxiaate solution for instance (V,s) of the offline problem minimizing (1) w.p. at least 8, as desired.
The next proposition evaluates the performance of Algorithm 7.

---

Proposition 2. Given sampling budget T and additive enoor e E (0, 0.5), the uniform sampling
algorithm with a-approximation oracle for the FB setting (Algorithm 7) outputs Cout that satisfies
Pr (Cout) a OPT(s) + +c]= - (0(" exp (- T'²
a22 (
Proof. As e E E has been pulled at least
T times, by Lemma I, we have
(- 2T (a 1)2m3
Pr [(c) s(e)) (a 1)m
S 2exp
Taking union bound for all E E, we have
27
Pr ((e) - s(e)] < (a + 1Im
Ve E
2 21-2 Σ exp
(a + 1)3m3
e
2
1 2m exp
(a + 1)mm²
By Lemma 10, when for all E, [(c)) ss(e] < (a+1)m we have (Cout) a OPT((s + which concludes the proof.
25

---

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]
The main claims made in the abstract and introduction (Section 1) reflect the paper's contributions and scope including theoretical results and its importance in the literature as well as empirical evidences.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We have discussed in detail the limitations of our work, specifically the absence of lower bounds for our novel formulations, and additionally provided auxiliary analysis by devising naive algorithms. We also included future directions in Section 6.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should 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 or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best 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.
3. Theory Assumptions and Proofs
26

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All theorems (Theorem and Theorem 2), formulas, and proofs are numbered and cross-referenced. Assumptions are clearly stated in Section 2. Complete proofs are included in the appendix (Appendix C for Theorem 1, Appendix for Theorem 2, and Appendix E for analysis of baselines). Short sketch provided in Section 3 is complemented by Appendix C. All theorems and lemmas are properly referenced in the proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: As detailed in Section 5, we fully disclosed all the information needed to reproduce the main experimental results of the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make 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 to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require 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 the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
27

---

(d)
reproducible, they We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification:
The paper does not provide open access the data and code as its primary
focus is on theoretical contributions, with experiments included to support the theoretical findings.
Guidelines:
The answer means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm 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 (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / /nips.cee wwtpcccppppppppeeeeeceeccccceeee htte//uwdies/eee/eeeeee weeieeee//ooeSummmeseeeee ssiisioicccc) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to 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
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: Although our proposed method does not involve training or hyperparameters, all relevant parameters for problem setup, such as the values of ô, and T', as well as all parameters related to instance generation, are detailed Section 5.
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 a 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
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
28

---

Justification:
The experimental results reported in Section 5 confidence intervals or standard deviation as well as averages.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror 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.)
The assumptions made should be given (c.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: As in Section 5, the paper provides sufficient information on the computer resources needed reproduce the experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs 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 https::/neuripp: http:://oorrpp..ccppii//////eeea hccppppbllcc/hhicccteeeellllllll ines?
Answer: [Yes]
Justification: The research conducted in the paper conforms, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- cration due to laws or regulations their jurisdiction).
10. Broader Impacts
29

---

Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This work is regarded as a theoretical study from an algorithmic perspective. The authors believe this will not lead any negative social impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional 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 ML).
11. Safeguards
Question: Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
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 encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
The original papers that produced the code package or dataset are properly credited in Section 5.
Justification:
Guidelines:
30

---

The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset'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 release assets.
Researchers should communicate the details the dataset/code/mooel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing 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 much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing research with human subjects.
31

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor 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 expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
32


Reviews:
[{"review_id": "nG5xfqAFzT", "reviewer": "Reviewer_B6XK", "summary": "This paper copes with the problem of active (weighted) correlation clustering when oracle queries are corrupted by random noise. \n\nAuthors frame two variants of the problem where high probability guarantees are required: the fixed-confidence and the fixed budget settings; algorithms for the these settings are provided in order. \n\nTheoretical results are supported by numerical experiments.", "questions": "N/A", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The subject considered in this paper is of interest, as also confirmed by the vast literature on this problem: indeed, correlation clustering (CC) is one of the most popular clustering framework.\n\nThe proposed algorithms are simple to understand and easy to implement. One aspect that should be clarified is the precise runtime of KC-FC which I recommend to include in the statement of Theorem 1. \n\nThe performance guarantees in Th. 1 is nice in being instance dependent.", "weaknesses": "Related works: it is not clear to me why authors only refers to [40] when mentioning the SOTA bounds for active CC in the noiseless setting, when also [15] nature essentially the same performance guarantee.\n\nAs for Theorem 1, the guarantees does not recover the 3 apx. factor when the true similarities are binary, instead settles for the much worse 5 apx. factor. \n\nFor binary queries, it seems to me that a simple strategy that ask roughly log(n) times queries for each edge queried (e.g.. the choice of kwick cluster) and takes the majority vote, would be equivalent to an algorithm running on the true similarity and should feature a 3 apx. factor. Could authors comment on that? A similar question holds for similarities in [0,1], how about replacing the majority voting above with a simple average, and then running a standard algorithm on the top?\n\nIn the numerical evaluation it may be good to consider adding the above baselines in problems where the similarities are binary.\n\nMy main concerns revolves around the relevance of the contribution provided by this paper, if you can provide convincing arguments, I'm willing to raise my score.\n\nI'm (partially) satisfied with the authors answer, and increase my score accordingly.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your review. \n\n> One aspect that should be clarified is the precise runtime of KC-FC which I recommend to include in the statement of Theorem 1.\n\nAs stated in Lines 224–227, each iteration of the while-loop of TB-HS takes $O(m)$ steps in a naive implementation or amortized $O(\\log \n T)$ steps if we manage the arms using two heaps corresponding to LCB/UCB values. Moreover, the number of iterations of the while-loop is upper bounded by $O(T)$. Therefore, TB-HS runs in $O(Tm)$ time in a naive implementation or $O(T\\log T)$ time if we manage the arms using the two heaps. As KwikCluster runs in $O(m)$ time, those two values directly characterize the overall running time of Algorithm 1. In our revised version, we will add the above to Theorem 1. \n\n> Related works: it is not clear to me why authors only refers to [40] when mentioning the SOTA bounds for active CC in the noiseless setting, when also [15] nature essentially the same performance guarantee.\n\nHistorically, Bonchi et al. [11] in 2013 (i.e., the preprint version of Garcia-Soriano et al. [40]) first provided the guarantee of $3\\cdot \\mathrm{OPT}+O(n^3/T)$. Then, in 2019, Bressan et al. [15] presented essentially the same guarantee. For reference, see the table in Section 1.1 in Bressan et al. [15], where the authors stated “see also Bonchi et al.” for the guarantee. In the current manuscript, we cite Garcia-Soriano et al. [40] because it is the official conference version of Bonchi et al. [11]. In our revised version, we can also refer to Bressan et al. [15], though it has already been cited in the main text.\n\n\n> As for Theorem 1, the guarantees does not recover the 3 apx. factor when the true similarities are binary, instead settles for the much worse 5 apx. factor.\n\nWhen the true similarities are binary, the value of 5 of the $(5,\\epsilon)$-approximation can easily be replaced by 3, using the approximation ratio of 3 of KwikCluster for the binary offline problem. However, we would not highlight this fact in Theorem 1, as the case of binary similarities is not of our interest. As emphasized in Lines 49–61, dealing with only the binary similarities is one of the significant limitations of existing query-efficient correlation clustering algorithms, which indeed initiates our study. \n\n> For binary queries, it seems to me that a simple strategy that ask roughly log(n) times queries for each edge queried (e.g.. the choice of kwick cluster) and takes the majority vote, would be equivalent to an algorithm running on the true similarity and should feature a 3 apx. factor. Could authors comment on that? A similar question holds for similarities in [0,1], how about replacing the majority voting above with a simple average, and then running a standard algorithm on the top?\n\nIn the above reviewer’s comments, the definition of “binary queries” is not clear. We suppose that the reviewer considers the case where the true similarities are in $[0,1]$ but the noisy feedback of the oracle follows a Bernoulli distribution. In this case, even if the algorithm suggested by the reviewer performs a sufficiently large number of queries (not necessarily $\\log n$ times) for obtaining accurate estimations, the approximation guarantee cannot be 3. This is because we are discussing the approximation guarantee in terms of the cost function (1) defined on the true similarities in $[0,1]$ rather than the similarities determined by the majority voting. It is worth noting that KwikCluster for the offline problem of minimizing the cost function (1) is a 5-approximation algorithm, and it is not known that KwikCluster has a better approximation ratio for the problem. The same discussion applies to the second question.\n\nIn case where the reviewer means “binary queries\" by the oracle that behaves as follows: for a given $e\\in E$, if $\\mathrm{s}(e)=0$ holds, the oracle returns 0 with probability greater than $0.5$ and returns 1 otherwise, whereas if $\\mathrm{s}(e)=1$ holds, the oracle returns 1 with probability greater than $0.5$ and returns 0 otherwise, the value returned by the oracle no longer follows any distribution with a mean equal to the true similarity value $0$ or $1$. Therefore, this setting is out of our model. It is worth noting that the above model is more similar to those reviewed in Lines 111–124. As for the case of non-binary similarities, the strategy mentioned above has already been employed in our algorithm. \n\n> In the numerical evaluation it may be good to consider adding the above baselines in problems where the similarities are binary.\n\nWe note that the algorithm design and the statistical metrics of the algorithms are different across the FB setting (error probability) and in the FC setting (sample complexity). Indeed, in the FB-setting, if one queries $\\log n$ times for each pair of the pivot and its neighbor at every iteration, it can exceed the given budget $T$, resulting in an invalid algorithm. In the FC-setting, such an algorithm does not have any approximate guarantee on the output while the sample complexity is trivially bounded by $O(n^2 \\log n)$. Only algorithms that are $(\\epsilon, \\delta)$-PAC are of our interest, in line with the standard experimental practices of all other PE-MAB studies.\n\n\n> My main concerns revolves around the relevance of the contribution provided by this paper, if you can provide convincing arguments, I'm willing to raise my score.\n\nWe hope that our response has addressed all of your concerns accordingly.", "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": "qHPS1TA5cF", "reviewer": "Reviewer_S1WA", "summary": "This paper introduces algorithms for correlation clustering with noisy, expensive similarity functions. The authors present two formulations in the PE-CMAB framework: fixed confidence and fixed budget. Their proposed algorithms, KC-FC and KC-FB, combine sampling with KwikCluster approximation.", "questions": "What is the main challenge to extend this approach for 3-approximation algorithms?", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper addresses the realistic and challenging scenario of noisy and costly similarity functions, which differs from the traditional assumption that provides the exact similarities value.\n\nThe theoretical analysis looks solid. The problem setting is motivated by practical applications where computing similarities are expensive and noisy. The paper provides a strong practical evaluation. \n\nThe paper is clearly written and easy to read.", "weaknesses": "The paper could benefit from a more detailed discussion of the limitations of the current to achieve 3-approximation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your review. \n\n> The paper could benefit from a more detailed discussion of the limitations of the current to achieve 3-approximation.\n> What is the main challenge to extend this approach for 3-approximation algorithms?\n\nAs stated in Lines 35–39, for our offline problem (i.e., the problem of minimizing the cost function (1)), KwikCluster is a 5-approximation algorithm, and it is not known that KwikCluster has a better approximation ratio for the problem. Therefore, our algorithm admits exactly the same approximation ratio as that achieved by KwikCluster for the offline problem, up to an additive error $\\epsilon >0$. It is worth noting that when the true similarities are binary, the value of $5$ of the $(5,\\epsilon)$-approximation can easily be replaced by $3$, using the approximation ratio of $3$ of KwikCluster for the binary offline problem. \n\nTo achieve the $(3,\\epsilon)$-approximation in the general case, it seems essential to design an online algorithm that incorporates an approximation algorithm with an approximation ratio of $3$ (or better). For our offline problem, the only algorithm that meets the above condition is the one by Ailon et al. [3] with an approximation ratio of $2.5$, but it seems quite challenging to design an online algorithm incorporating it, because the offline algorithm solves a linear programming relaxation of the problem. When using LP-based approximation algorithms, it becomes necessary to evaluate the optimal value of the LP with the estimated similarities involving uncertainty, against the true optimal value of the LP, which requires a quite challenging analysis. \n\nIn our revised version, we will feature the above as one of the interesting future directions in the concluding section. Thank you for your suggestion!", "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": "ZVe6vRMaxa", "reviewer": "Reviewer_7MDd", "summary": "**[Setting]**\nThis paper studies correlation clustering using a noisy oracle. The learner queries a pair of items and receives a noisy estimate of their similarity in the range [0, 1] from an oracle. The goal is to either:\n1. [Fixed confidence setting] Minimize the number of queries and return a clustering with cost at most $\\alpha OPT + \\epsilon$ with high probability\n2. [Fixed budget setting] Minimize the probability of returning a clustering with cost more than $\\alpha OPT + \\epsilon$ for a given query budget $T$\n\n**[Contributions]**\n1. An algorithm (KC-FC) for the fixed confidence setting that makes roughly $\\tilde{O}(n^2/\\Delta_1^2)$ queries ($\\Delta_1$ being a custom gap-based metric) and returns a clustering with cost at most $5 OPT + \\epsilon$ with high probability.\n2. An algorithm (KC-FB) for the fixed budget setting that makes $T$ queries and returns clustering with cost at most $5 OPT + \\epsilon$ with probability at least $1 - O(n^3 \\exp(-2T\\Delta_2^2/n^2))$, where $\\Delta_2$ is another custom gap-based metric.\n3. Empirical validation that the algorithms work as expected", "questions": "Please respond to the points under weaknesses", "limitations": "Yes, the authors addressed the lack of a lower bound.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This paper considers an oracle that returns values in range [0, 1] instead of a binary response, as in existing works. \n2. Results for both fixed confidence and fixed budget settings are included.\n3. The paper is well-written and easy to follow. \n4. Experiments show that the cost of recovered clustering in the fixed-confidence setting is roughly the same as the cost of clustering obtained from KwikCluster if it is given the \"ground-truth\" similarity scores.", "weaknesses": "1. I am not entirely convinced by the strength of the theoretical results in the fixed confidence setting. Why not move sampling inside the clustering loop in Algorithm 1? Keep sampling $\\lbrace u, v_r \\rbrace$ for all unclustered nodes $u$ and the chosen pivot $v_r$ until $s(u, v_r) > 0.5 - \\epsilon$ or $s(u, v_r) < 0.5 + \\epsilon$ can be determined with high confidence. Then move nodes into the same cluster as $v_r$ if $s(u, v_r) > 0.5 - \\epsilon$. This would require $\\tilde{O}(n / \\Delta^2)$ queries per round $r$, leading to overall complexity of $\\tilde{O}(nk / \\Delta^2)$ instead of $\\tilde{O}(n^2 / \\Delta^2)$. Algorithm 3 already does something similar.\n2. The results will benefit from more context. For example, when $T = \\theta(n^2)$, the fixed budget bound becomes meaningless. How does this result compare to the case of noisy correlation clustering with only one sample per edge (e.g., Mathieu and Schudy, 2010 and similar results)? In the absence of a lower bound, such context would be very valuable.\n3. More context can also be added to experiments. For example, it would be useful to threshold the oracle's response and compare the query complexity with an approach for binary responses? The naïve baselines seem too simplistic.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your review. \n\n> I am not entirely convinced by the strength of the theoretical results in the fixed confidence setting. Why not move sampling inside the clustering loop in Algorithm 1? Keep sampling $\\{u,v_r\\}$ for all unclustered nodes $u$ and the chosen pivot $v_r$ until $s(u,v_r)>0.5-\\epsilon$ or $s(u,v_r)<0.5+\\epsilon$ can be determined with high confidence. Then move nodes into the same cluster as $v_r$ if $s(u,v_r)>0.5-\\epsilon$. This would require $\\tilde{O}(n/\\Delta^2)$ queries per round $r$, leading to overall complexity of $\\tilde{O}(nk/\\Delta^2)$ instead of $\\tilde{O}(n^2/\\Delta^2)$. Algorithm 3 already does something similar.\n\nThank you for your insightful question. Your observation is correct; we have also considered the procedure you suggested during this work. However, we have arrived at the current form to ensure the theoretical guarantees.\nWhile incorporating TB-HS within the loop, as you suggested, could potentially reduce the overall sample complexity, we must consider the worst-case scenario where the total number of loops (denoted by $k$ above) can be as large as $n$, and the sample complexity would depend on the worst-case instance gap. As for the latter, more precisely, if we employ the algorithm you suggested, the sample complexity for each loop will be characterized by the gap defined by the similarities between the pairs of $v_r$ and its unclustered neighbors​. In this context, the input to TB-HS will become a random variable. Additionally, randomization in the pivot selection is essential to guarantee the approximation ratio of KwikCluster. Overall, in the resulting analysis, which excludes random variables, the bound will depend on the worst-case instance gap, meaning that the above modification does not improve upon Theorem 1.\n\n> The results will benefit from more context. For example, when $T=\\theta(n^2)$, the fixed budget bound becomes meaningless. How does this result compare to the case of noisy correlation clustering with only one sample per edge (e.g., Mathieu and Schudy, 2010 and similar results)? In the absence of a lower bound, such context would be very valuable.\n\nOur FB setting of PE-CMAB formulation and the planted noise models in Mathieu and Schudy [64] are not directly comparable: \n- As discussed in Section 1.2, \"Correlation clustering with noisy input\" (Lines 111–124), the planted noise model proposed by Mathieu and Schudy [64] (2010) assumes the existence of a ground-truth clustering, where similarities are binary, and labels are flipped with a probability $p$. Makarychev et al. [62] (2015) extended this to general weighted graphs, proposing a model where edge labels ($+$ for similar pairs and $-$ for dissimilar pairs) can flip. However, their model assumes that all similarities $\\mathrm{s}(e)$ are known, which is a key difference from our model. Additionally, their model assumes the existence of a ground-truth clustering, and does not discuss sequential selection strategies.\n- In contrast, we do not assume the existence of such a ground-truth clustering. Instead, we consider a scenario where the similarities, represented by edge weights, are completely unknown, and where only noisy evaluations are available through sequential queries. Furthermore, the noisy feedback from all edges is probabilistic, and we consider models where this feedback is independently sampled from distributions such as a sub-Gaussian or Bernoulli distribution. Consequently, these models are not directly comparable; the planted noise models mentioned above do not incorporate sequential algorithmic elements, nor do they address the estimation of weights or the uncertainties present in our model. Our work is based on the PE-CMAB formulation within a sequential learning framework, where the total budget $T$ is naturally defined as being greater than the number of base arms (e.g., number of edges in the graph). This is consistent with all PE-MAB formulations in the FB setting.\n\n\n> More context can also be added to experiments. For example, it would be useful to threshold the oracle's response and compare the query complexity with an approach for binary responses? The naïve baselines seem too simplistic.\n\nPerforming KwikCluster on the rounded values obtained by taking the sample mean from a Bernoulli distribution and rounding it to 0 or 1 using the threshold of $0.5$ is an approach that has already been employed in our baselines and even our proposed methods for both the FC and FB settings. If you have another algorithm in mind or specific suggestions, please share the details. We would be happy to address them in our next response.", "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": "pTmYc08GvR", "reviewer": "Reviewer_RiHB", "summary": "The paper considers a correlation clustering setting with an unknown similarity function but with the ability to query a noisy oracle, i.e., the oracle may yield noisy feedback instead of the true similarity of the queried pair of objects. In this scenario, the goal is to achieve a reasonable trade-off between the number of queries to the oracle and the cost of the clustering. In the considered setting, the authors introduce two novel problem formulations within the paradigm of pure exploration of combinatorial multi-armed bandits (PE-CMAB): fixed confidence and fixed budget settings. For both problems, the paper introduces two novel algorithms (KC-FC and KC-FB) and analyzes their theoretical guarantees. Some experiments on real-world graph datasets with some artificially generated features validate the theoretical findings of the work by demonstrating that in both settings the proposed methods outperform a baseline method in terms of sample complexity and cost of the clustering.", "questions": "Q1) In the more general case of correlation clustering (see W1), the KwikCluster algorithm does not provide any theoretical guarantees (even in the offline setting), thus the theoretical guarantees of KC-FC and KC-FB algorithms should not hold either, is it correct? If yes, how can your proposed algorithms be modified to account for such a general setting? \n\nQ2) Besides the missing theoretical guarantees of existing “general-purpose” PE-CMAB on the specific PE-CMAB instance considered in this paper, are there any other reasons that make the applicability of such algorithms unfeasible in practice in the context of the problems considered in this paper? (See also W2)\n\nQ3) How is the noisy feedback provided to the learner in the experiments when querying a particular pair of objects?\n\nQ4) How is the sample complexity of the Uniform-FC algorithm computed without running it?\n\nQ5) In the experiments, why is epsilon set to sqrt(n), delta to 0.001, and T to n^2.2?\n\nQ6) Why did you decide to use different methods to generate the similarity values for the FC and FB settings. As an example, why not use the same strategy adopted for the FC setting for the FB setting as well, to observe, by varying Delta_{min}, how often the algorithm yields the desired approximate solution, i.e., estimate the probability in Equation 3?", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "S1) Good originality: the paper studies two novel problem formulations for correlation clustering with unknown similarity values and an oracle with noisy feedback.\n\nS2) The settings considered in this work are well-motivated in the Introduction.\n\nS3) The paper is overall well-written and very well-contextualized relative to prior work (>80 references) on similar topics.\n\nS4) The proposed algorithms are theoretically analyzed.", "weaknesses": "W1) The authors considered the most basic formulation for correlation clustering, where the costs of placing two objects in the same or different clusters sum to 1, and there is a cost for every pair of objects (Equation 1). The authors neither motivate the choice of this specific setting nor discuss the more general case where such costs are not related and some pairs are missing from the objective function. A discussion on how/if the results presented in this paper can be extended to the more general correlation clustering problem would have been appreciated.\n\nW2) Limited number of baselines used in the experiments. Besides their proposed method, the authors only tested against the baseline KwikCluster, which knows the true similarities, and Uniform-FB (Uniform-FC), which is defined by the authors themselves. The lack of comparison with existing methods for general-purpose PE-CMAB algorithms for the FB and FC settings is notable. The authors justify this choice by stating that the theoretical analysis of such algorithms does not hold in the context of correlation clustering considered in this paper (lines 220-227). However, comparing the proposed approach with existing general PE-CMAB approaches would have provided a more convincing argument about the ineffectiveness of existing approaches in practice for the considered problem. This represents a missed opportunity to demonstrate the necessity of their proposed algorithms with practical evidence.\n\nW3) Limited reproducibility: the source code is not provided with the submission.\n\nW4) Missing proof sketch for Theorem 2 in the main paper. As done for Theorem 1, the authors should include a proof sketch for Theorem 2 as well.\n\nW5) The paper is not clear in the following aspects:\n\n- It is not clear why the authors decided to use different methods to generate the similarity values for the FC and FB settings. In particular, why not use the same strategy adopted for the FC setting for the FB setting as well, to observe, by varying Delta_{min}, how often the algorithm yields the desired approximate solution, i.e., estimate the probability in Equation 3?\n\n- The authors specify how the similarity scores, hidden from the learning algorithm, are generated. However, the main paper does not explain how the noisy feedback is provided to the learner when querying a particular pair of objects. Are the defined similarities the mean of a Bernoulli or R-sub-Gaussian distribution? Are the noisy feedbacks generated by sampling from these distributions? Please specify this in the experimental evaluation section.\n\n- Some parameter values are not justified in the paper: why is epsilon set to sqrt{n}, delta = 0.001, and T = n^{2.2}? The latter is said to be for scalability, but why n^{2.2} and not n^{2.1}?\n\n- The motivation for using only instances with n < 1000 nodes for the experiments in Figures 1 and 2 is unconvincing. The authors could have used better hardware for the experiments, not just a notebook.\n\n- The authors do not run Uniform-FC algorithms in the experiments but report the sample complexity, which can be calculated without running it. How is this done? This is not clear and should be explicitly stated on line 325.\n\nMinors:\n- The font size in Figures 1, 2, and 3 is too small and difficult to read.\n- Algorithm 2, line 7: please specify that the updates are done for edges \\bar{e}_t^g and \\bar{e}_t^b to improve clarity.\n- State in the paragraph \"Algorithm details\" that the sets G and B correspond intuitively to the sets of \"good\" and \"bad\" pairs, respectively. This is only stated in the algorithm.\n- Line 323, “as it will be shown later” is too general. Please be more specific (using pointers) if it refers to something shown in the Figures or the Supplemental Material.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your review. \n\n**W1 and Q1:**\nThank you for your insightful question, which is precisely aligned with the critical discussions we had during the process of this work. \n\nAs you mentioned, our offline problem (minimizing the cost function (1)) is one of the most basic formulations for Correlation Clustering (CC), which was introduced by the seminal work of Bansal et al. [7], where CC itself was first proposed. The model is versatile, where the similarity is characterized in a value ranging in $[0,1]$. Owing to the importance, the model has extensively been studied in the literature (see e.g., Ailon et al. [3] and Chawla et al. [18]). In our revised version, we will clarify the position of this model. Thank you for your suggestion! \n\nThe theoretical guarantees of KC-FC and KC-FB are based on the approximation ratio of 5 of KwikCluster for the above model, and therefore, they do not hold for the general setting you suggested (i.e., our learning model with the general MinDisagree). \n\nExtending our learning model to the above general setting you suggested or even to other NP-hard problems (not necessarily clustering problems) is definitely an interesting direction. Our study shows that, while most existing PE-CMAB algorithms rely on exact algorithms tied to offline optimization problems, we successfully address an NP-hard problem by fully leveraging the properties of the offline algorithm, i.e., KwikCluster's thresholding property, to propose an online learning algorithm that obtains instance-dependent upper bounds.\n\nAlternatively, another potential approach to deal with a learning model with an offline NP-hard problem could be estimating the gap between the objective values of the worst $\\alpha$-approximate solution and the best non-$\\alpha$-approximate solution to adapt LUCB (Lower Upper Confidence Bound)-type algorithms in the FC setting or successive reject algorithms in the FB setting. However, estimating such a gap seems infeasible, and thus, designing a stopping condition or rejection strategy in such cases is not straightforward. Dealing with a learning model with an offline NP-hard problem is regarded as one of the major open problems in the field of PE-CMAB. \n\n**W2 and Q2:**\nExisting PE-CMAB methods for both the FC and FB settings require exponential runtime, which is infeasible in practice. Moreover, in the FC setting, even the stopping condition of the algorithm is invalid. As highlighted in Lines 103–109 and Lines 282–289, we emphasize that such existing PE-CMAB methods only work for the case where the offline problem can be solved exactly in polynomial time. However, this is not the case for CC. In fact, existing PE-CMAB methods essentially compute two candidate solutions and compare their goodness to select the currently empirically best solution as the final output, but this strategy cannot be used when only approximate solutions are available. \n\nSpecifically, in the FC-setting, existing methods [23, 25, 35, 82] use the LUCB type strategy, and its stopping condition requires the exact computation of the empirical best solution and the second empirical best solution to check if the current estimation is enough or not. When we only have an approximate oracle (i.e., approximation algorithm), such existing stopping conditions are no longer valid, and the algorithm is not guaranteed to stop. \n\nIn the literature of combinatorial bandits, the FB setting presents even more computational challenges and a scarcity of results. In the FB setting, the existing successive-reject type algorithm [6, 25, 35] cannot handle partition structures in CC, and require exponential running time.\n\nOur algorithms are the first polynomial-time algorithms that work for the case of PE-CMAB where the underlying offline optimization is NP-hard.\n\n\n**W3:**\nWe will make our source code publicly available.\n\n**W4:**\nWe will include the proof sketch of Theorem 2, which is based on Lemma 9 and Lemma 8, to the main text.\n\n**W5 including Q3–Q6:**\n\n- [To Q6] The dependence of the sample complexity on the minimal reward gap $\\Delta_\\min^{-2}$ (as proved in Theorem 1) in the FC setting and the dependence of the error probability on $\\exp(−T)$ (as proved in Theorem 2) in the FB setting are statistically significant characteristics. Evaluating the algorithm by varying $\\Delta_\\min$ in the FC setting and the budget $T$ in the FB setting is a standard experimental setup in the PE-MAB literature to provide empirical evidence for theoretical results. Therefore, we follow this practice. \n- [To Q3] While our model is capable of dealing with either type of observations (as noted in Lines 154–156), we used a Bernoulli distribution in our experiments, for simplicity. We will specify this in the experimental section. \nIf we allow each element to mistake a constant number of pairs compared to OPT, then $\\epsilon = O(n)$. However, this may be too many errors for practical applications. Therefore, we set a stricter threshold, allowing each element to make only $1/\\sqrt{n}$ mistakes, which corresponds to a stricter scale of $\\epsilon = O(\\sqrt{n})$ used in experiments.\n- [To Q5] Taking larger confidence level $\\delta \\in (0,1)$ means easier setting; we set it to a small enough, i.e., order of $10^{-3}$ following a standard choice in PE-MAB. Regarding the setting of $T$, even on the largest dataset Wiki-Vote, if we employ $T=n^{2.1}$, KC-FB and Uniform-FB query each pair only four times in their first iterations, which allows for randomness too much, and thus we employed $T=n^{2.2}$, where they query it more than ten times. \nThe experiments were performed using a desktop, which has moderate computational resources. \n- [To Q4] As written in Lines 312–313, the pseudocode of the baselines and full analysis are given in Appendix E. Given the Line 1 of Algorithm 5, we can see the precise number of samples that Uniform-FC uses.\n\n**Minors:**\nWe will incorporate all of them accordingly. Thank you for your careful reading!", "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:

Meta-review: The paper studies a correlation clustering problem where the similarity between each pair of elements can only be obtained by querying a noisy oracle.

The reviewers have mixed opinions on this paper, but generally on the positive side.  Most reviewers agree that the problem is well-motivated, with solid theoretical analysis and practical evaluation.  One reviewer initially had concerns on the strength of the theoretical results in the fixed confidence setting, but the authors' response has successfully changed the reviewer's mind. Two reviewers increased their scores following the authors' rebuttal, which is a positive development.
Decision: Accept (poster)