Practical and Accurate Local Edge Differentially Private Graph Algorithms
Published in Very Large Data Bases (VLDB), 2025
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: k-core decomposition and triangle counting. Our approach leverages previously unexplored input-dependent private graph properties, specifically the degeneracy and maximum degree of the graph, to improve theoretical utility. Unlike prior methods, our error bounds are determined by the maximum degree rather than the total number of edges, resulting in significantly tighter theoretical guarantees. For triangle counting, we improve upon the previous work of Imola, Murakami, and Chaudhury [USENIX Security 21, 22] which bounds error in terms of the total number of edges. Instead, our algorithm achieves error bounds based on the graph’s degeneracy by leveraging a differentially private out-degree orientation, a refined variant of Eden et al.’s [ICALP `23] randomized response technique, and a novel, intricate analysis, yielding improved theoretical guarantees over prior state-of-the-art.
Beyond theoretical improvements, we are the first to evaluate the practicality of local DP algorithms in a distributed simulation environment, unlike previous works that tested on a single processor. Our experiments on real-world datasets demonstrate substantial accuracy improvements, with our k-core decomposition achieving errors within 3x the exact values—far outperforming the 131x error in the baseline of Dhulipala et al. [FOCS `22]. Additionally, our triangle counting algorithm reduces multiplicative approximation errors by up to six orders of magnitude compared to prior methods, all while maintaining competitive runtime performance.