Query-Efficient Correlation Clustering with Noisy Oracle

We sincerely appreciate your review.

W1 and Q1: Thank you for your insightful question, which is precisely aligned with the critical discussions we had during the process of this work.

As 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!

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

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

Alternatively, 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.

W2 and Q2: Existing 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.

Specifically, 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.

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

Our algorithms are the first polynomial-time algorithms that work for the case of PE-CMAB where the underlying offline optimization is NP-hard.

W3: We will make our source code publicly available.

W4: We will include the proof sketch of Theorem 2, which is based on Lemma 9 and Lemma 8, to the main text.

W5 including Q3–Q6:

• [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.
• [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. If 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.
• [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. The experiments were performed using a desktop, which has moderate computational resources.
• [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.

Minors: We will incorporate all of them accordingly. Thank you for your careful reading!

We sincerely appreciate your review.

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.

Thank 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. While 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.

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.

Our FB setting of PE-CMAB formulation and the planted noise models in Mathieu and Schudy [64] are not directly comparable:

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

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.

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

We sincerely appreciate your review.

The paper could benefit from a more detailed discussion of the limitations of the current to achieve 3-approximation. What is the main challenge to extend this approach for 3-approximation algorithms?

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

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

In our revised version, we will feature the above as one of the interesting future directions in the concluding section. Thank you for your suggestion!

We sincerely appreciate your review.

One aspect that should be clarified is the precise runtime of KC-FC which I recommend to include in the statement of Theorem 1.

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

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.

Historically, 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.

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.

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

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?

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

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

In the numerical evaluation it may be good to consider adding the above baselines in problems where the similarities are binary.

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

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.

We hope that our response has addressed all of your concerns accordingly.