Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the correlation clustering problem under edge differential privacy constraints. In the correlation clustering problem, given a complete graph with + and – labels on the edges, the goal is to partition the vertices so as to minimize the number of + edges between parts, plus the – edges inside parts. With edge differential privacy (DP), Given two graphs on the same set of vertices that differ in only one edge, the goal is to make sure, for any set of outcomes of an algorithm, the probability of returning that outcome is roughly the same (within a multiplicative $e^\epsilon$ and additive $\delta$) for both graphs. This problem was studied by BEK21 where they give an $(\epsilon, \delta)$-DP algorithm that approximates the optimal clustering cost (OPT) with cost $O(1) OPT + O(n^{1.75}log(n/\delta)/\epsilon)$. There is also a concurrent paper of Liu22 with the additive term of $\tilde{O}(n^{1.5}log(n/\delta)/\sqrt{\epsilon})$. BEK21 also prove an $\Omega(n)$ lowerbound on the additive approximation of DP algorithms on path graphs.

This paper improves the additive term to $O(nlog^2(n)log(n/\delta)/{\epsilon}^2)$. Inspired by CALM+21’s paper on correlation clustering in the parallel setting, they make the steps in that algorithm private in such a way to make sure the cost approximation remains within the mentioned bound. They also add to the lowerbound results by proving a linear lower bound on the approximation in complete unweighted graphs.

strengths_and_weaknesses: The problem considered in this paper is natural and important. The paper is very well written, and the ideas are clearly presented. Although I did not check all the proofs in detail, the logic seems solid to me. The paper borrows ideas from the literature, but they had to do nontrivial work to prove the DP and cost guarantees.

My only comment for the authors is to elaborate on how well the algorithm scales. How parallelizable it is, or maybe bring empirical studies to argue about this. In general, this paper could benefit from empirical studies on how well the algorithm actually performs in practice. For example, the dependence on $\epsilon$ is quadratic, what are some ranges of $\epsilon$ that are used in practice. Or in general, please elaborate on the significance of your result in the real-world setting. 



questions: As mentioned above, I recommend the authors elaborate on various aspects of the performance of their algorithm.
limitations: I do not see any serious limitations.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors develop an approximation algorithm for correlation clustering in complete unweighted graphs with privacy guarantees. The additive error of their algorithm is stronger than prior work, while it is optimal up to polylogarithmic factors. It also matches the additive error of the exponential mechanism up to a logn factor. They also show that linear error is necessary even for complete unweighted graphs and (eps,delta)-privacy.
strengths_and_weaknesses: Strenghts:
- the paper is very well written and organized
- the additive error of their algorithm is stronger than prior work and optimal, up to polylog factors. To this end, the authors also prove that linear error is necessary even for complete unweighted graphs.
- the authors borrow some ideas from [CALM21], however, a deeper analysis of the algorithm in [CALM21] and several novel ideas are developed. 

Weaknesses:
- their results seem to only apply to complete unweighted graphs (in contrast to [BEK21] and [LIU22] )
- some of the ideas were presented in [CALM21], however, the paper contains significant novel contributions
questions: -
limitations: No negative societal impact, as far as I could check.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper discusses the min-disagree correlation clustering problem. It gives an (\eps, \delta)-differentially private algorithm that provides O(1) multiplicative and O(n log^2n) additive approximation. The additive approximation is close to the optimal bound of \Omega(n), which is also shown in the paper. Theorems 1.1 and 1.2 appropriately summarise the main results of the paper. 
strengths_and_weaknesses: Strengths: 
- The paper gives an improvement over previous work, improving the additive approximation guarantee. 
- The lower bound result also improves the previously known results.
- The intuition behind the algorithm and the analysis is presented well.


Weaknesses: 
- I do not find any significant weakness in the paper. One aspect that may not appeal to practitioners is that the results in this paper are theoretical. There are no experimental evaluations presented.
questions: Even though the theoretical results in the paper are appreciated, it may be nice to have a discussion on the applied aspects of the results. Are there specific application scenarios where the results of this paper may be useful?
limitations: The work is theoretical. I do not see any negative societal impact.
review_title: null

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: The authors applied differential privacy to correlation clustering, using graph notations. They first added noise to the degree of vertices and discarded edges using the definition of noised agreement. The authors added noise to the number of edges and defined a vertex is light or heavy. Finally, they discarded the edge and output the heavy vertices in a cluster. Also, the authors proposed approximated method.
strengths_and_weaknesses: [Strengths]
- The authors carefully analyzed to support their argument, and provided time complexity.
- The authors applied differential privacy to recent work, especially using noised agreement have novelty.

[Weaknesses]
- There are some minor issues in the paper. For example, in lines 20-21, the authors need to say the sum of the “absolute value” of negative edges to prevent confusion.
- It seems that the privacy budget is wrongly calculated. In Line 1 of Algorithm 1, the authors added noise to every d(v). Since d(v) = |N(v)| where N is the set of neighbors of a vertex v, d(v)s(for v in V) are not independent, the privacy budget is accumulated by composition theorem. This implies the privacy budget is higher than the authors argued, exactly |G|/2 times higher than expected(The sensitivity of d is 2, as mentioned in line 227, and the sensitivity of d(v) is 1).
- It would be better if the authors change the arXiv references in the final submission. For example, [CALM+21], which appears to have motivated the authors is accepted by ICML.

questions: I’ve never seen the term “(0,0)-differential private” before(In the proof of Lemma 4.2). Is it widely used? If not, what about using post-processing or saying "it does not spend privacy budget"? 
limitations: The authors assumed every weight of an edge is -1 or  1.
review_title: null

Meta-review: metareview: The paper gives a new algorithm for correlation clustering in the edge differential privacy model i.e. two graphs are neighbor if they differ by one edge. The problem has been studied extensively in the nonprivate setting and there are several previous works on the problem in the private setting. The new algorithm has nearly optimal additive error and it is quite simple and efficient. The new additive error is nearly linear in n, the number of nodes, as opposed to n^1.5 in the previous polynomial time algorithms. All reviewers appreciate the near optimal solution to a well studied problem. The reviewers highly value the theoretical contribution but also suggest that the paper can be strengthened with some empirical evaluation.
confidence: Certain
Decision: Accept