#subgraph-counting

共收录 1 条相关安全情报。

← 返回所有主题
推荐 8.5
Conf: 50%
👥 作者: Xian Chen, Ruobing Bai, Pan Peng

本文首次研究了差分隐私下的范围子图计数问题(DPRSC)。子图计数是图分析中的基本问题,传统方法通常计算整个图中特定模式的出现次数。然而,实际应用常需对由多维属性范围选中的顶点诱导子图进行查询,同时保护隐私。差分隐私子图计数面临重大挑战:子图计数是非线性函数且敏感度高,单个边的修改可能影响大量子图出现次数。为此,本文提出了一种高效算法,通过引入子图投影,将DPRSC转化为加权正交范围计数问题。利用范围树和局部敏感度估计,实现了低加性误差的私有查询响应。此外,还通过将重构攻击归约为DPRSC并利用离散理论,证明了任何差分隐私算法都必须承受随维度指数增长的加性误差。实验表明,所提算法在准确性和运行时间上显著优于基线方法,同时保持强隐私保证。该研究为图数据分析中的隐私保护提供了新工具,尤其适用于社交网络、生物信息学等需敏感数据查询的场景。

💡 推荐理由: 首次解决了带范围约束的子图计数差分隐私问题,为图数据分析中的隐私查询提供了理论基础和实用算法。

🎯 建议动作: 学术关注

排序因子: 影响边界/网络设备 (+5) | 来自 arXiv 其他板块 (+2) | Community 数据源 (+1) | LLM 评分加成 (+0.5)