标题： 实用且准确的局部边差分隐私图算法 显示英文标题

标题： Practical and Accurate Local Edge Differentially Private Graph Algorithms

摘要： 随着跨多个领域的大型网络的兴起，需要复杂的图分析，这通常涉及敏感数据并引发隐私问题。 本文使用本地差分隐私（LDP）来解决这些挑战，LDP在个体层面强制隐私，其中不信任任何第三方实体，与假设有一个可信管理者的集中式模型不同。 我们为两种基本的图统计量：k-core分解和三角形计数引入了新颖的LDP算法。 我们的方法利用输入相关的私有图属性，特别是图的退化性和最大度，以提高理论效用。 与之前的方法不同，我们的误差界限由最大度而不是边的总数决定，从而产生显著更紧的保证。 对于三角形计数，我们改进了Imola、Murakami和Chaudhury的工作[USENIX Security `21, `22]，后者根据边数界定了误差。 相反，我们的算法通过利用私有出度方向，这是Eden等人[ICALP `23]的随机响应技术的改进变体，以及一种新的分析方法，实现了基于图退化性的边界，提供了比之前工作更强的保证。 除了理论上的优势，我们在分布式模拟中首次评估了本地DP算法，而之前的工作仅在单个处理器上进行测试。 在真实世界图上的实验显示了显著的准确性提升：我们的k-core分解误差在精确值的3倍以内，远远优于Dhulipala等人[FOCS `22]基准的131倍误差。 我们的三角形计数算法将乘法近似误差减少了多达六个数量级，同时保持了具有竞争力的运行时间。 显示英文摘要

摘要： 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 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 guarantees. For triangle counting, we improve upon the work of Imola, Murakami, and Chaudhury [USENIX Security `21, `22], which bounds error in terms of edge count. Instead, our algorithm achieves bounds based on graph 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 k-core decomposition achieves errors within 3x of exact values, far outperforming the 131x 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.