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.
Paper
Similar papers
Peer review
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.
Strengths
S1) Good originality: the paper studies two novel problem formulations for correlation clustering with unknown similarity values and an oracle with noisy feedback. S2) The settings considered in this work are well-motivated in the Introduction. S3) The paper is overall well-written and very well-contextualized relative to prior work (>80 references) on similar topics. S4) 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. W2) 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. W3) Limited reproducibility: the source code is not provided with the submission. W4) 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. W5) The paper is not clear in the following aspects: - 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? - 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. - 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}? - 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. - 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. Minors: - The font size in Figures 1, 2, and 3 is too small and difficult to read. - 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. - 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. - 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.
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? Q2) 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) Q3) How is the noisy feedback provided to the learner in the experiments when querying a particular pair of objects? Q4) How is the sample complexity of the Uniform-FC algorithm computed without running it? Q5) In the experiments, why is epsilon set to sqrt(n), delta to 0.001, and T to n^2.2? Q6) 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?
Rating
7
Confidence
4
Soundness
3
Presentation
3
Contribution
4
Limitations
Yes
Summary
**[Setting]** This 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: 1. [Fixed confidence setting] Minimize the number of queries and return a clustering with cost at most $\alpha OPT + \epsilon$ with high probability 2. [Fixed budget setting] Minimize the probability of returning a clustering with cost more than $\alpha OPT + \epsilon$ for a given query budget $T$ **[Contributions]** 1. 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. 2. 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. 3. Empirical validation that the algorithms work as expected
Strengths
1. This paper considers an oracle that returns values in range [0, 1] instead of a binary response, as in existing works. 2. Results for both fixed confidence and fixed budget settings are included. 3. The paper is well-written and easy to follow. 4. 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. 2. 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. 3. 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.
Questions
Please respond to the points under weaknesses
Rating
6
Confidence
2
Soundness
3
Presentation
3
Contribution
2
Limitations
Yes, the authors addressed the lack of a lower bound.
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.
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. The 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. The 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.
Questions
What is the main challenge to extend this approach for 3-approximation algorithms?
Rating
7
Confidence
3
Soundness
3
Presentation
3
Contribution
3
Limitations
N/A
Summary
This paper copes with the problem of active (weighted) correlation clustering when oracle queries are corrupted by random noise. Authors 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. Theoretical results are supported by numerical experiments.
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. The 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. The 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. 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. 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 numerical evaluation it may be good to consider adding the above baselines in problems where the similarities are binary. 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. I'm (partially) satisfied with the authors answer, and increase my score accordingly.
Questions
N/A
Rating
5
Confidence
3
Soundness
2
Presentation
2
Contribution
2
Limitations
N/A
Follow-up discussion
I appreciate the detailed response from the authors, which clarified most of my concerns, especially the one concerning W2/Q2. Regarding W1, I understand that the theoretical guarantees of KC-FC and KC-FB rely on the approximation ratio of 5 provided by KwikCluster and thus do not extend to the general setting of correlation clustering. I have a follow-up question: would it be problematic in your analysis to work with a non-constant approximation guarantee for the noisy oracle? If not, extending your work to the general setting might be more feasible by building the algorithmic framework around, for example, the algorithm proposed by Demaine et al. [34], which offers $O(\log n)$ approximation guarantees for general correlation clustering by solving a linear programming relaxation. Admittedly, this would necessitate a more complex algorithmic design and analysis, as, in your response to Reviewer S1WA, you noted that designing an online algorithm when the offline algorithm solves a linear programming relaxation of the problem is quite challenging. Specifically, when using LP-based approximation algorithms, it becomes essential to evaluate the optimal value of the LP—estimated under uncertainty—against the true optimal value, which presents a significant analytical challenge. However, I am curious why this represents a significant challenge and how it differs from the challenge that arises in every CMAB problem, where it is necessary to relate the optimal value of an instance with uncertainty (provided by the mean estimates of the arms) to the true optimal value.
Challenges in Pure Exploration for NP-hard problems
We appreciate you taking the time to review our rebuttal thoroughly and adding the discussion with your constructive questions! > I have a follow-up question: would it be problematic in your analysis to work with a non-constant approximation guarantee for the noisy oracle? If not, extending your work to the general setting might be more feasible by building the algorithmic framework around, for example, the algorithm proposed by Demaine et al. [34], which offers 𝑂(log𝑛) approximation guarantees for general correlation clustering by solving a linear programming relaxation. Admittedly, this would necessitate a more complex algorithmic design and analysis, as, in your response to Reviewer S1WA, you noted that designing an online algorithm when the offline algorithm solves a linear programming relaxation of the problem is quite challenging. Specifically, when using LP-based approximation algorithms, it becomes essential to evaluate the optimal value of the LP—estimated under uncertainty—against the true optimal value, which presents a significant analytical challenge. The non-constant approximation ratio itself is not problematic in the analysis. Rather, the behavioral property of an algorithm employed is crucial. Even if KwikCluster admitted only $\alpha$-approximation ratio (e.g., $O(\log n)$) for our offline problem, KC-FC/KC-FB would also admit an $\alpha$-approximation. The reason why KC-FC and KC-FB are able to solve the PE-CMAB problems with theoretical guarantees is that 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 in the offline setting, as shown in Lemma 5 for the FC setting and Lemma 9 for the FB setting. However, as you pointed out, building upon the LP-based $O(\log n)$-approximation algorithm in the PE-CMAB setting would present significant analytical challenges, because the region-growing algorithm does not have any desired property, unlike KwikCluster. >However, I am curious why this represents a significant challenge and how it differs from the challenge that arises in every CMAB problem, where it is necessary to relate the optimal value of an instance with uncertainty (provided by the mean estimates of the arms) to the true optimal value. Regret minimization in CMAB is quite different from Pure Exploration 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 (Chen et al. [26, 27]; Wang and Chen [81]). However, for Pure Exploration, the main difficulty working with approximation oracles lies in determining the stopping condition --- unlike the optimal value, objective values of $\alpha$-approximate solutions are not unique, causing it difficult to decide whether the Pure Exploration algorithm has already found a sufficiently good solution to terminate. When an exact computation oracle is available for an offline problem, the use of LCB and UCB scores with exact solutions can set a stopping condition, as seen in many existing LUCB-type approaches in the FC setting. However, this approach becomes invalid when dealing with $\alpha$-approximate oracles. In the FB setting, the Combinatorial Successive Accept Reject algorithm proposed by Chen et al. [24] iteratively solves the so-called Constrained Oracle problem, which is often NP-hard, as later addressed in Du et al. [35]. We anticipate a similar NP-hard problem in our Correlation Clustering problem, requiring a different approach. We hope that the explanation addresses your additional questions. We intend to incorporate a summary of these discussions into the revised version.
I sincerely thank the authors for the further discussion and clarifications. The rebuttal has strengthened my confidence in the quality of this work, and as a result, I have raised my score.
Thank you for taking time to address my questions. **Regarding Algorithm1:** Am I correct in saying that moving the sampling step inside the loop does not improve the current $O(n^2 / \Delta^2)$ bound **in the worst case** when $k=n$? If so, isn't the $O(nk/\Delta^2)$ bound doing the same thing while being a bit more general? I also did not completely understand your argument about sample complexity depending on worst-case instance gap. Theorem 1 already depends on $\Delta_{\min}$. Not sure why moving sampling inside the loop will change it. Therefore, while I agree that the modification does not change the worst-case sample complexity, it is more general and allows the algorithm to perform better when $k << n$. **Regarding adding more context:** I appreciate your clarification regarding Mathieu and Schudy (2010). While this is not very important, what I meant was adding a statement like "In an easier problem setting where the true similarities follow a specific structure, making $n^2$ observations is enough to bound the error probability by ________. However, the learner pays a price for being in the more general setting, and the error probability is only bounded by ________ after $n^2$ observations." More important perhaps is a practical comparison. Sample edges uniformly at random for $T$ steps and threshold the values to obtain a signed graph. Use [MS10] to cluster this graph and plot clustering cost vs $T$. How does this curve compare to KC-FB in Fig.3? I understand that [MS10] make assumptions that you don't. But this is one way to compare the practical performance of your algorithm with theirs in a more general setting.
Further Clarification on Sequential Use of TB-HS and Comparison with Mathieu and Schudy [64]
Thank you for dedicating your time to review our rebuttal and for your constructive questions. > Regarding Algorithm1: Am I correct in saying that moving the sampling step inside the loop does not improve the current $O(n^2/\Delta^2)$ bound in the worst case when $k=n$? If so, isn't the $O(nk/\Delta^2)$ bound doing the same thing while being a bit more general? I also did not completely understand your argument about sample complexity depending on worst-case instance gap. Theorem 1 already depends on $\Delta_\mathrm{min}$. Not sure why moving sampling inside the loop will change it. Therefore, while I agree that the modification does not change the worst-case sample complexity, it is more general and allows the algorithm to perform better when $k$ << $n$. If we utilize TB-HS within the loop while maintaining the $(5,\epsilon)$-approximation guarantee, we obtain the following sample complexity (omitting the log-log factor, for simplicity here) which, as you pointed out, is better than the sample complexity of Theorem 1 when $k << n$: $$O\left( \sum_{r=1}^{k} \left( \sum_{e \in I_{V_r}(p_r)} \frac{1}{\tilde{\Delta}^2_{e, \epsilon_r^\prime}} \log \left(\frac{n}{\tilde{\Delta}^2_{e, \epsilon_r^\prime} \delta}\right) + \frac{|V_r|}{\max ( \Delta_{\min,r}, \frac{\epsilon_r^\prime}{2})^2 } \right) \right),$$ where $\epsilon_r^\prime:=\epsilon/(12|I_{V_r}(p_r)|)$, $I_{V_r}(p_r) \subseteq E$ represents the set of pairs between the pivot $p_r$ selected in phase $r$ and its neighbors in $V_r$, and $\Delta_{\min,r}:=\min_{e \in I_{V_r}(p_r)} \Delta_e$. (We recall that $\tilde{\Delta}_{e, \epsilon_r^\prime}$ is defined as in Equation (2).) It should be noted that the symbols related to $r$ and the total number of loops $k$, especially instance-dependent gaps $\tilde{\Delta}_{e, \epsilon_r^\prime}$, are all random variables and complicated. Also, It is not common practice to present a sample complexity with random variables remaining. In contrast, the current Theorem 1 does not contain any random variables. Specifically, the significant term related to $\log \delta^{-1}$ is characterized by the gap $\tilde{\Delta}_{e,\epsilon}$ or $\Delta_e$, which represents the distance from 0.5 and not a random variable. As we appreciate the suggested variant of our algorithm and its analysis, we will include the above discussion as a remark of Theorem 1 in the revised version. Thank you again for your helpful suggestion. > More important perhaps is a practical comparison. Sample edges uniformly at random for $T$ steps and threshold the values to obtain a signed graph. Use [MS10] to cluster this graph and plot clustering cost vs $T$. How does this curve compare to KC-FB in Fig.3? I understand that [MS10] make assumptions that you don't. But this is one way to compare the practical performance of your algorithm with theirs in a more general setting. Mathieu and Schudy [64] devised two algorithms: MainCluster algorithm and Large Cluster algorithm. The first algorithm solves an SDP-relaxation (more precisely, a doubly-nonnegative programming relaxation) for Correlation Clustering, which obviously does not scale to instances with hundreds of elements. As for the second algorithm, according to their runtime analysis (see Section 5.6 in their paper), it takes $O(n^{12\ell})$ time, where $\ell$ is a positive integer, which is again impractical.
Thank you again for your response. Adding a remark as you have suggested would be useful. I also understand that comparing with other baseline methods is challenging. I have increased my score from 4 to 6. All the best for your submission ! :)
Thank you for the detailed response. I will maintain my score.
Decision
Accept (poster)