Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper introduces a new 2.5-approximation LP-based algorithm for Chromatic Correlation Clustering improving upon existing state-of-the-art 3.0-approximation result of Klodt et al. The authors also present a two-phase greedy algorithm (without guarantees) and demonstrate empirically that it performs better in terms of clustering found (minimizing number of disagreements) with improved time complexity compared to previous state-of-the-art solution of Klotz et al. 

strengths_and_weaknesses: ## Strengths
+ Well-written with clear presentation of main results. 
+ New rounding procedure based on the LP solution with careful analysis leading to 2.5-approximation compared to previous state-of-the-art theoretical result of Klotz et al. 
+ GreedyVote algorithm which performs better empirically compared to previous methods on standard CCC datasets. 

## Weaknesses
- Limited impact for wider Neurips audience - More suited to KDD/WWW possibly?
  
questions: N/A
limitations: N/A
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The authors develop a 2.5-approximation algorithm for chromatic correlation clustering (CCC), which is a generalization of the well-known correlation clustering problem introduced in 2012. Their algorithm is LP-based, while it improves the best-known approximation ratio of 3 developed in 2021. A greedy heuristic is also developed and compared against state-of-the-art algorithms on real-world data, showing promising results. 
strengths_and_weaknesses: + the authors develop the best approximation algorithm for chromatic correlation clustering. In contrast with the previous best 3-approximation algorithm, their algorithm is not color blind, which is interesting.  
+ the experimental evaluation on real-world data is promising (although still preliminary)
+ the paper is well written and organized

- the theoretical results are not surprising with some of the ideas already presented in [2] and [3]
- it is not clear whether the analysis of their algorithm is tight. That is, is there an example where their algorithm produces solutions with an approximation ratio of 2.5?
- the experimental evaluation is not convincing. As most of the algorithms are randomized, the authors should report the variance of their results. As their results are very close to the ones of [20], there might not be much difference, statistically. Also it seems that the parameters of their algorithms have been optimized w.r.t. to the datasets considered (eps and m have been set to 0.55 and 10 respectively), while the default settings for the other algorithms have been used. It is not clear why, the Cooking dataset from [20] has not been included in their experimental evaluation. This does not seem to be a fair evaluation.
- the code of their algorithm does not seem to be publicly available

some other comments:
- “It is noted that CCC is a generalized version of CC and hence also has an integrality gap of 2 as the lower bound for  any achievable approximation ratio for it. “ This claim is ambiguous. It should be noted that this lower bound holds only for the LP-formulation considered in the paper. This claim alone does not prevent the existence of another LP-formulation with smaller integrality gap or a completely different algorithm with approximation guarantee < 2. 
- there seems to be some confusion between randomly and arbitrarily (e.g. line 116)
- theorem 3.1, it should be stated that the approx is in expectation.
- which LP-solver has been used in the experimental evaluation?

Overall the paper contains some interesting ideas, while it has strong potential. In particular they provide the best approximation algorithm for CCC. However, I feel that the points discussed above should be addressed before being accepted for publication.


questions: see my comments above.
limitations: There doesn't seem to be any negative societal impact.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: In this paper, the authors propose two algorithms to tackle the chromatic correlation clustering problem. The first algorithm is a randomized algorithm that outputs a feasible solution to the chromatic correlation clustering problem that is a 2.5-approximation on average. The second procedure is instead a heuristic. The authors provide a theoretical analysis regarding the first method as well as numerical experiments that show the effectiveness of the second algorithm.
strengths_and_weaknesses: The paper is overall well-written and easy to read. The authors argue well why this problem is relevant. On the one hand, they improve by 0.5 the previously best ratio for a chromatic correlation clustering approximation algorithm. On the other one, their heuristic algorithm outperforms the current state-of-the-art heuristics on the tested data sets.

There are four main weaknesses: 
1. The approximation algorithm (which should be the main result of this paper) has not been implemented and tested on the data sets. It is somehow disappointing to only see computational experiments for the heuristic approach. In particular, it would have been nice to see how tight the approximation ratio is in practice.
2. The statement in the abstract about the approximation algorithm is misleading. The information that the approximation algorithm is a randomized algorithm appears for the first time in Section 3. Moreover, the authors show that the approximation ration is attained in expectation and therefore not always. This is in contradiction to the (deterministic) statements in the abstract and introduction.
3. The choice of references a bit odd. It would be nice if the vast literature on the clique partitioning/multicut problem was cited. In this literature, the correlation clustering ILP is studied in great detail. See e.g. Groetschel & Wakabayashi, Chopra & Rao, Deza & Groetschel & Laurent, Bandelt et. al. ... (and references therein).
4. The approximation algorithm (Algorithm 1) is only defined for unweighted complete graphs even if the chromatic correlation clustering problem is defined in general for arbitrary graphs. The authors do not bring up this issue, nor explain how (if?) their approach could be generalized to arbitrary graphs (would the same approximation ratio hold in this case?). Note that here there is no generic cost objective function so that it would suffice to add edges of zero costs, and in this way trivially transform any graph in a complete graph. 

Below are further comments:
1. The first sentence in the abstract sounds a bit as if Bonchi et. al. had introduced regular CC.
2. In the last sentence of the abstract, "efficiency of our proposed algorithms", I would remove the plural since experiments are included for one of the two algorithms only.
3. In the first part of the introduction where the problem is introduced informally, a reader could get the impression that a multigraph is considered whenever there exist two types of relationships between two given nodes.
4. Page 2, line 49: The authors mention several times that CC has an integrality gap of 2, and that therefore this transfers to the chromatic correlation clustering. However, they are actually only talking about approximations obtained by rounding some LP relaxation. If one were not to use LP relaxation in order to derive approximations algorithm, this is not necessarily true anymore. In fact, having an integrality gap of 2 does not imply that there cannot be an approximation algorithm with a better guarantee than 2 in general. The authors should be more open and clear about it.
5. Page 2, line 72: it would be nice if the meaning of gamma was described with words. From my understanding, an edge labeled with gamma is a "must cut" edge. I would suggest the authors to provide this intuition sometime before equation (1).
6. Page 2 (and everywhere it is stated): CCC-LP cannot be a formulation of the chromatic correlation clustering. In fact, an optimal solution to CCC-LP is in general fractional and cannot correspond to a clustering. An INTEGER solution does, not a fractional. Therefore, if the authors were to add binary constraints to CCC-LP, then they would have a proper formulation of the chromatic correlation clustering. Currently, the LP model they propose, CCC-LP, is just a relaxation of the chromatic correlation clustering, not a formulation.
7. Page 2, starting from line 82 and then a bit everywhere in the paper: the authors should add the corresponding quantifiers whenever they write x^c_{uv}, x^c_u, x^c_v and similar things. Is it for all c,u,v or just a subset? If so, which?
8. Advice about Algorithm 1 line 3, observation 4.1 and related issues: I would make it explicit that for a fixed v there exists a unique c such that x_v^c < 1/2, and I would write this remark early on, as soon as the reader reads the algorithm so that it is clear that line 3 is well-defined.
9. Algorithm 1, line 9: what does "pivot" mean? Is it just any node in S_c or does a node need to satisfy specific properties in order to be a pivot?
10. Page 3, line 101-102: also lines 5,6 in the algorithm provide a partitioning.
11. Page 3, line 108: I would replace "rationality" with something more like "motivation, intuition, idea behind it...".
12. Page 3, lines 109-110: "as to" --> "with respect to"?
13. Page 4, first paragraph: Note that the rounding of x_u^c does not affect the objective value. I do not understand what is supposed to be greedy here.
14. Page 4, line 125: "until every vertex in S_c is included in a cluster" from the way it is written it sounds like all these vertices become singletons, while this is not the case since you grow these clusters C_k.
15. Page 4, lines 130-133: the authors should mention where the proof can be found. Note that the complete proof is not available in this manuscript since part of it has been moved to the appendix.
16. Page 4, line 145: what is LP? CCC-LP?
17. Page 5, line 158: write "some alpha >= 2" to emphasize that in inequality does not need to hold for every alpha. Observe that if it were for all alphas, then it would hold also for alpha = 2 and we would have a 2-approximation.
18. Page 5, line 175: it looks to me like E^t_c should be E^t_c \setminus E^{t+1}_c.
19. End of page 5: Why is it necessary to argue with submartingales? Here, we are dealing with an expected value of a finite sum and the linearity of the expected value should be all that is necessary for this argument.
20. Algorithm 2: Why is not Output described here? See Algorithm 1.
21. Algorithm 2, line 3: "a set" not "the set". 
22. Algorithm 2: see second question in section "3. Questions".
23. Algorithm 2, line 7: One can get the impression that being a "seed" vertex is a special property. But by my understanding every vertex in "S_k" is a seed vertex. For me, it would be easier to understand if it just said "Let each vertex in S_k vote...".
24. Algorithm 2: Why are the clusters called S instead of C as above?
25. Page 7, line 220: I would introduce this notation before so that the reader is not confused when he/she first reads it in the fourth line of the algorithm.
26. Page 8, line 241: It would be nice to see how the constant m affects the runtime.
27. Checklist 1b: I do not see a discussion of the limitations neither in the abstract nor in section 6.
28. Checklist 3c: the error bars are not present in the main paper.
questions: - Is the analysis in section 4 tight?
- Why are we guaranteed that Algorithm 2 does not get stuck in the first while loop? In fact, as long as E has at least one edge we stay in the loop, however we need at least m edges to perform all the operations inside of the while loop (and then remove edges from E). It looks to me like the algorithm could arrive at a point where E is not empty but contains less than m edges. This would result in getting stuck in the loop.
limitations: The discussion is adequate for this theoretical work.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors propose improved algorithms for the chromatic correlation clustering (CCC), which is a generalization of the correlation clustering problem to multiple labels. The authors present a 2.5 approximation algorithm for this problem based on rounding of a linear program; this bound is tighter than the best-known approximation of 3. The authors also propose a heuristic motivated by their rounding procedure. Experimental results show that the proposed heuristic outperforms existing heuristics and approximation algorithms in minimizing the objective function.
strengths_and_weaknesses: Strengths:
- Rigorous theoretical results and an improved approximation bound to a problem that has been of interest in the past 10 years
- Proposed heuristic outperforms existing alternatives
- Compelling mix of theoretical and empirical results
- Supplementary material makes it very easy to reproduce the results in the paper

Weaknesses:
- Lack of experimental results for the approximation algorithm
- Impact is somewhat unclear. How does the improvement in performance in the objective function translate to a practical benefit?
questions: Have you implemented LP-Clustering?
Can you provide experimental results for LP-Clustering?
How does the improvement in performance in the objective function translate to a practical benefit? GE and GER have very similar performance.
limitations: Yes
review_title: null

Meta-review: metareview: The papers studied that Chromatic Correlation clustering problem, the author(s) introduce(s) a new 2.5-approximation LP-based algorithm  improving upon existing state-of-the-art. 

The result is not particularly novel but the paper contains a new algorithm for a well-studied problem and prove that ideas inspired from their theory are impactful in practice so it would be a nice contribution to the NeurIPS program.

The committee suggestion is to accept the. paper as a poster.
confidence: Certain
Decision: Accept