Nearly Tight Bounds For Differentially Private Multiway Cut
Authors: Mina Dalirrooyfard, Slobodan Mitrovic, Yuriy Nevmyvaka
NeurIPS 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Finally, we empirically evaluate the approximation of our differentially private min s-t cut algorithm and show that it almost matches the quality of the output of non-private ones. ... We perform an empirical evaluation on the additive error of Algorithm 1 and validate our theoretical bounds. |
| Researcher Affiliation | Collaboration | Mina Dalirrooyfard Machine Learning Research Morgan Stanley mina.dalirrooyfard@morganstanley.com Slobodan Mitrovic Department of Computer Science UC Davis smitrovic@ucdavis.edu Yuriy Nevmyvaka Machine Learning Research Morgan Stanley yuriy.nevmyvaka@morganstanley.com |
| Pseudocode | Yes | Algorithm 1: Given a weighted graph G, this algorithm outputs a DP min s-t cut. ... Algorithm 2: Given a weighted graph G, this algorithm outputs a multiway k-cut. |
| Open Source Code | No | The paper does not provide any explicit statements about releasing source code or a link to a code repository for the described methodology. |
| Open Datasets | Yes | As our base graph, we use email-Eu-core network [22] which is an undirected unweighted 1,005-node 25,571-edge graph. ... [22] Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data, June 2014. |
| Dataset Splits | No | The paper describes how graph instances are generated and how parameters like epsilon are varied for evaluation, but it does not specify explicit training, validation, and test dataset splits for a machine learning model or experiment in the traditional sense. |
| Hardware Specification | No | The paper does not provide any specific details about the hardware used for running the experiments, such as GPU/CPU models or memory specifications. |
| Software Dependencies | No | The paper does not provide specific software dependencies with version numbers, such as programming language versions or library versions. |
| Experiment Setup | Yes | Set-up. As our base graph, we use email-Eu-core network [22] which is an undirected unweighted 1,005-node 25,571-edge graph. ... To make the graph more realistic, we add random weights to the edges from the exponential distribution with a mean of 40 (rounded to an integer) to denote the number of emails sent between two nodes. We take 10 percent of the nodes and contract them into a terminal node s, and take another 10 percent of the nodes and contract them into another terminal node t. We make different instances of the problem by choosing the nodes that contract into s or t uniformly at random. ... We first set ϵ = 0.5. We then consider 50 graph instances, and for each of them, we evaluate the average private error over 50 rounds of randomness used in Algorithm 1, see Figure 1(left) for the results. ... We next change ϵ and repeat the set-up above for each ϵ ∈ { 1/14, ..., 1/2, 1}. For each value of ϵ, the set up is the same as in the left figure. For each ϵ in this set we produce 50 graph instances, measure the average private error over 100 rounds of randomness for each, and then average the terminal cut error and mean private cut error for each graph instance. |