Practical and Accurate Local Edge Differentially Private Graph Algorithms

Download PDF

Abstract

The rise of massive networks across diverse domains necessitates sophisticated graph analytics, often involving sensitive data and raising privacy concerns. This paper addresses these challenges using local differential privacy (LDP) , which enforces privacy at the individual level, where no third-party entity is trusted , unlike centralized models that assume a trusted curator. We introduce novel LDP algorithms for two fundamental graph statistics: 𝑘 -core decomposition and triangle counting. Our approach leverages input-dependent private graph properties—specifically degeneracy and maximum degree—to improve theoretical utility. Unlike prior methods, our error bounds depend on the maximum degree rather than the total edge count, yielding significantly tighter guarantees. For triangle counting, we improve on the work of Imola, Murakami, and Chaudhury [USENIX Security ’21, ’22], which bounds error in terms of edge count. Our algorithm instead achieves bounds based on degeneracy by leveraging a private out-degree orientation, a refined variant of Eden et al.’s randomized response technique [ICALP ’23], and a novel analysis, yielding stronger guarantees than prior work. Beyond theoretical gains, we are the first to evaluate local DP algorithms in a distributed simulation, unlike prior work tested on a single processor. Experiments on real-world graphs show substantial accuracy gains: our 𝑘 -core decomposition achieves errors within 3 x of exact values, far outperforming the 131 x error in the baseline of Dhulipala et al. [FOCS ‘22]. Our triangle counting algorithm reduces multiplicative approximation errors by up to six orders of magnitude , while maintaining competitive runtime.