Private Graph Property Testing
该论文研究的是「差分隐私图性质测试」这一此前几乎空白的交叉方向。图性质测试（graph property testing）的基本问题是：给定一个规模极大的图，能否只做亚线性（sublinear）次数的查询，就判断它满足某个性质，还是与满足该
#graph-algorithms
共收录 4 条相关情报。
← 返回所有主题A Graph-Based Framework for Extending Metric Differential Privacy Mechanisms
本文研究度量差分隐私（metric differential privacy, mDP）机制的可扩展构造问题。mDP 适合定义在结构化的秘密域上（例如路网、地理网格、坐标空间），因为它的隐私保证随秘密值之间的度量距离变化，比标准差分隐私更贴
Lower Bounds for Private Graph Optimization Problems using Reconstruction Attacks
本文研究差分隐私（DP）约束下的基础图优化问题，并给出基于“重构攻击”思路的新型下界证明。作者考虑图 G=(V,E,w⃗)，其中顶点集 V 与边集 E 是公开的，只有边权函数 w:E→ℝ 需要满足 ℓ1 邻接关系下的差分隐私。研究对象包括两
Secure Graph Analysis at Scale.
本文提出了一个高度可扩展的安全计算图算法框架，用于保护图拓扑及节点/边关联数据的隐私。在该框架中，图的所有节点和边都以秘密共享形式分布在多个服务器上，服务器间通过安全计算协议协同计算，而不泄露任何图结构或节点属性信息。虽然该方案具有一定的普