Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: In this work, the authors introduce and study an interesting and pragmatic variant of the popular Correlation Clustering (Minimizing Disagreements) problem. In this problem, we are given a limited budget on the number of queries allowed to make to an expensive oracle that given an edge returns the true labeling of the edge (returned by possibly a large ML model). Moreover, we are also given unlimited access to a cheap but less accurate second oracle (for example embedding-based models, etc.). The authors propose an extension of the well-known KWIKCLUSTER algorithm, that uses the cheaper oracle wisely to reduce the number of queries to the expensive oracle. They prove a matching (to the original version of the problem) 3-approximation for a stronger assumption on the cheap oracle, except for an additive error. They show that the additive error term is unavoidable by demonstrating a tight lower-bound instance. They extend their algorithm to work for the more practical assumptions on the cheaper oracle, but with no theoretical guarantees. An extensive empirical analysis is performed to motivate the problem formulation, demonstrate the superior performance of their algorithm over baselines, and ablation studies on all tunable parameters of their algorithm.
strength_and_weaknesses: The proposed model (with strong-expensive and weak-cheap oracles) is powerful and pragmatic, in the sense that it allows one to navigate the trade-offs imposed due to the computationally-expensive process of obtaining the actual similarities between entities in real-world datasets. Further, this model helps one to leverage the existence of weaker-yet-useful models for predicting similarities to obtain more scalable algorithms. The theoretical results obtained complement the known results for the original version of the problem, except for the additive error term. The algorithm is simple and efficient (and as demonstrated in previous work has scope for parallelism as well.) The set of experiments performed is well-motivated and supports all the claims of the paper well.
clarity,_quality,_novelty_and_reproducibility: The model proposed is of incredible interest, especially due to the increasing use of large-scale ML models to predict the similarity between entities. Correlation clustering, being a very popular clustering paradigm with several applications (especially as a pre-processing step), is a suitable problem to be studied under this framework.
summary_of_the_review: Overall, this is a very well-written paper. The problem considered is of significant importance, the proposed algorithm is simple and efficient, and the empirical evaluation is extensive and supports the claims well. Therefore, I think this paper is a good fit for ICLR. Following are a few minor line-by-line comments:

Minor Comments:
- Page 2: Sec 1.1, para 2, line 1 - cluster -> clustering
- Page 3: para 1, line 4 - queries in for -> queries for
- Page 3: Sec 1.2, para 1, line 5 - “we use” is written twice
- Page 5: Thm 2.1 Proof Sketch, Line 1: inocrrectly -> incorrectly
- Page 6: Last para of Section 3, Line 10 - two cluster -> two clusters
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies a version of correlation clustering where the learner has access to a weak predictor of node similarity in addition to an accurate stronger predictor. The weak model is assumed to have negligible query cost, and can be used in addition to the stronger model. For a free parameter $\epsilon$, he paper proposes a new algorithm which uses both the weak and strong oracle to retrieve a clustering which has objective value at most $3 \text{OPT} + \epsilon n^2$, and makes $O (d \gamma / \epsilon)$ queries to the strong oracle - here $\text{OPT}$ is the optimal objective value, $n$ is the number of nodes in the graph, $d$ is the average degree of the graph, and $\gamma$ captures the approximation power of the weak oracle compared to the strong oracle. The algorithm is implemented in practice and shown to have significant improvements in practical performance compared to standard baselines - a 64% relative improvement in clustering quality (in terms of F1 score) averaged over 9 datasets, and over > 3.5x reduction in number of queries made to the strong predictor compared to the best baseline.
strength_and_weaknesses: I like the paper, and think the contribution is interesting. The experimental results are very good.

The paper focuses on the number of queries made to the strong oracle. However, the theoretical number of queries made to the weak oracle is reported nowhere. I think this is important, as the runtime of the algorithm might be end up being governed by the number of queries to the weak model if it is indeed queried many times.

The paper also claims (or cites) that correlation clustering is "perhaps the most natural formulation of clustering". I feel this is a subjective statement, and is better off not in the paper.

This leads to the question of designing an algorithm to optimize $Q_1 + \alpha Q_2$ where $Q_1$ is the number of queries to the strong model, and $Q_2$ is the number of queries to the weak model. $\alpha = 0$ is the setting studied in this paper, $\alpha = 1$ corresponds to the standard correlation clustering setting (since given a choice, one would always query the stronger model over the weaker one).


clarity,_quality,_novelty_and_reproducibility: Paper is written clearly and the setting considered is original and interesting in theory and practice.
summary_of_the_review: I think the paper considers an interesting problem, and I think it is a fit for ICLR.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: Please refer to Summary Of The Review.
strength_and_weaknesses: Please refer to Summary Of The Review.
clarity,_quality,_novelty_and_reproducibility: Please refer to Summary Of The Review.
summary_of_the_review: In this study, the author(s) propose(s) a novel correlation clustering algorithm named KwikBucks. It’s an extension of a well-known correlation clustering algorithm KwikCluster with the consideration of the limited query budget for reliable pairwise similarity. So the designed KwikBucks algorithm less the queries for expensive-strong signal by adding cheap-weak signal acquisition steps. The performance of the KwikBucks algorithm was tested by 9 datasets with different properties (having density changes of strong signal and weak signal). The experimental results shows KwikBucks can get a lower objective function value and higher F1 scores. Besides, it obtain 3-pproximation more efficiently.

The topic of this paper is meaningful as the problem of high cost of obtaining correlations among samples does exist because of the high computation of some machine learning models. Meanwhile, the theories about this work is sufficient. As a reader, I summarize some detailed issues as follows.

1) The introduction section overemphasizes the high cost of some machine learning models in obtaining the similarity between points, and neglects the in-depth analysis of the existing works and problems related to this paper. So the motivation and innovation of this paper are not presented well.
2) On page 1, there is too much analysis of experimental results so that parts of section 4 are repeated. Please just summarize in short words.
3) I believe that when we talk about correlation clustering, it is necessary to mention the research of Bansal (for ex. Bansal N, Blum A, Chawla S. Correlation clustering. Machine learning, 2004, 56(1):89–113).
4) On page 3, the differences with the existing work are not clearly explained. For example, how does the algorithm proposed by Guha et al. differ from the work in terms of obtaining information from multiple sources? What are the advantages and disadvantages of the existing work?
5) Section 1.2 has an extra ‘we use’ in the first paragraph.
6) What is the basis for Assumption 2.1? Also, what is the significance of the \gamma parameter? Why is it not specifically analyzed through experiments to explain its influence on the proposed algorithm in section 4, or explain this parameter theoretically?
7) The statement on page 8 that for many datasets such as Cora and Search, B1 and B2 are the best among our five baselines is not rigorous because only B2 is the best among five baselines on Cora and Search datasets.

In general, this paper needs more carefully revisions before fully accepting it.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This work develops a  pragmatic variant of the well-studied Correlation Clustering problem, with an emphasis on its “Minimizing Disagreements” version. We are given a budget on the number of queries allowed to make to an expensive oracle---perhaps a large ML model---that, given an edge e, returns the true labeling of e. We are also given unlimited access to a cheap but less-accurate such oracle, e.g., based on embedding-based models that can be queried fast. The paper develops extension of the KWIKCLUSTER algorithm that uses the cheaper oracle carefully to reduce the number of queries to the expensive oracle. They prove a 3-approximation for a stronger assumption on the cheap oracle, except for an additive error, and this additive error is shown to be inherent. The 3-approximation also runs faster than before. A thorough empirical analysis is performed to motivate the problem formulation, demonstrate the superior performance of their algorithm over baselines, and to conduct ablation studies on the tunable hyperparameters.

This framework is pragmatic, and helps one leverage weaker-yet-useful models for predicting similarities to obtain scalable algorithms. The theoretical results obtained match the results for the original version of the problem, except for the additive error. The algorithm is simple and efficient; the experiments support the claims of the paper. The paper is well-written.

The authors are encouraged to develop good bounds on the number of queries to the second oracle. 

justification_for_why_not_higher_score: The paper does not rise to the level of the oral/spotlight papers that I have seen at ICLR and other top-tier ML/AI conferences. 
justification_for_why_not_lower_score: The novelty and theory + experimental results are quite substantial.
Decision: Accept: poster