基于噪声邻接矩阵的边缘本地差分隐私子图计数

在分析图内连接模式时，子图计数是一种有效且基础的方法。边缘本地差分隐私（edge-LDP）和混洗模型已被用于在隐私保护情境下实现子图计数。现有算法受到高时间复杂度、过高下载成本、低准确性或依赖可信第三方等问题的困扰。

为解决上述挑战，我们提出了噪声邻接矩阵（NAM），它将差分隐私与图的邻接矩阵相结合。NAM具有强大的通用性和可扩展性，适用于更广泛的DP变体、DP机制和图类型。

基于NAM，我们设计了五种算法（TriOR、TriTR、TriMTR、QuaTR和2STAR）来计数三种类型的子图：三角形、四边形和2-星。理论和实验结果表明：

• 在三角形计数中，TriOR在一轮算法中以降低的时间复杂度最大化准确性
• TriTR实现最佳准确性
• TriMTR在低下载成本下实现最高准确性
• QuaTR成为纯边缘LDP下的首个四边形计数算法

我们通过置信区间启发的方法对噪声数据实现边缘LDP，为随机化数据提供DP保证。我们的2STAR算法在2-星计数中实现最高准确性，并可作为两轮三角形或四边形计数算法的副产品导出，从而在两次查询轮次内实现三角形、四边形和2-星数量的高效联合估计。