Near-Optimal Correlation Clustering with Privacy
Authors: Vincent Cohen-Addad, Chenglin Fan, Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Nikos Parotsidis, Jakub M. Tarnawski
NeurIPS 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper we introduce a simple and computationally efficient algorithm for the correlation clustering problem with provable privacy guarantees. Our additive error is stronger than those obtained in prior work and is optimal up to polylogarithmic factors for fixed privacy parameters... Our algorithm is given in Section 3 as Algorithm 1. Its privacy is proved in Section 4 (Theorem 4.5), and Section 5 is devoted to the approximation guarantees (Theorem 5.5)... We remark that the other known works on differentially private correlation clustering also do not provide experimental evaluations... |
| Researcher Affiliation | Collaboration | Vincent Cohen-Addad Google Research cohenaddad@google.com Chenglin Fan Pennsylvania State University fanchenglin@gmail.com Silvio Lattanzi Google Research silviol@google.com Slobodan Mitrovic UC Davis smitrovic@ucdavis.edu Ashkan Norouzi-Fard Google Research ashkannorouzi@google.com Nikos Parotsidis Google Research nikosp@google.com Jakub Tarnawski Microsoft Research jakub.tarnawski@microsoft.com |
| Pseudocode | Yes | In this section we formally define our algorithm, whose pseudo code is available in Algorithm 1 together with Definition 3.1. ... Algorithm 1: Private correlation clustering using noised agreement |
| Open Source Code | No | In the 'If you ran experiments...' section of the checklist, the response for 'Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)?' is [N/A], indicating no source code is provided. |
| Open Datasets | No | The paper is theoretical and does not present experimental results based on datasets. The checklist under 'If you ran experiments...' explicitly states 'N/A' for data and reproduction, and the Future Work section discusses the challenges of applying the algorithm to 'real-world datasets' and mentions that 'other known works... also do not provide experimental evaluations'. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments that would involve dataset splits. The checklist under 'If you ran experiments...' explicitly states 'N/A' for training details. |
| Hardware Specification | No | The paper is theoretical and does not describe any specific hardware used for running experiments. The 'If you ran experiments...' section of the checklist explicitly states 'N/A' for compute resources. |
| Software Dependencies | No | The paper is theoretical and does not describe specific software dependencies with version numbers needed to replicate experiments. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithm design and theoretical guarantees, rather than practical implementation details. No experimental setup details, such as hyperparameters or training settings, are provided in the text. |