Faster approximate subgraph counts with privacy
Authors: Dung Nguyen, Mahantesh Halappanavar, Venkatesh Srinivasan, Anil Vullikanti
NeurIPS 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We experimentally evaluate our algorithm for counting #triangles (Section 6). We show that our algorithm for estimating the smooth sensitivity has very good approximation factor, and significantly better running time than the exact algorithm. Using approximate smooth sensitivity for counting #triangles gives good accuracy even for fairly low ϵ values, suggesting that using approximate smooth sensitivity does not compromise performance. Our algorithm also has good scaling, and is the first private algorithm for counting #triangles which has been run on networks with over 2 million edges. |
| Researcher Affiliation | Academia | Dung Nguyen Department of Computer Science and UVA Biocomplexity Institute and Initiative University of Virginia, USA dungn@virginia.edu Mahantesh Halappanavar Data Sciences and Machine Intelligence Group Pacific Northwest National Laboratory, USA hala@pnnl.gov Venkatesh Srinivasan Department of Mathematics and Computer Science Santa Clara University, USA vsrinivasan4@scu.edu Anil Vullikanti Department of Computer Science and UVA Biocomplexity Institute and Initiative University of Virginia, USA vsakumar@virginia.edu |
| Pseudocode | Yes | Algorithm 1 τ estimation Algorithm 2 Algorithm to compute S ,β(G) Algorithm 3 Fast algorithm using Approximate Smooth Sensitivity for Approximate Query Af Algorithm 4 Fast estimation of (aij)2 Algorithm 5 Estimating higher-order private local sensitivity. |
| Open Source Code | No | The paper does not provide an explicit statement or link indicating that the source code for the described methodology is publicly available. |
| Open Datasets | Yes | Datasets. We consider different real-world networks from [26] as inputs. ... [26] Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data, June 2014. |
| Dataset Splits | No | The paper does not provide specific dataset split information (exact percentages, sample counts, citations to predefined splits, or detailed splitting methodology) needed to reproduce the data partitioning into training, validation, and test sets. |
| Hardware Specification | Yes | We ran our experiments on a system with a 48-core Intel(R) Xeon(R) Gold 6248R CPU @ 3.00GHz and 1.5TB RAM and limit the number of parallel threads in all experiments to 40. |
| Software Dependencies | No | All algorithms are implemented in C++ and Open MP framework for parallelization. The paper does not provide specific version numbers for these software components. |
| Experiment Setup | Yes | Parameters. We test our algorithms at different privacy budgets ϵ {2{ 3, 2, 1,0,1}} and a fixed δ = 10 6. We report the average accuracy and runtime of five (5) repeats of the private triangle count via approximate smooth sensitivity experiments due to the randomness used in the algorithm. |