在局部差分隐私保护下，利用加密技术辅助的图度序列发布

《ACM Transactions on the Web》：Crypto-Assisted Graph Degree Sequence Release under Local Differential Privacy

　　摘要
要查看此由AI生成的摘要，您必须具有高级访问权限。了解更多信息请登录。

**摘要**
给定一个在域G中定义的图G，我们研究了局部差分隐私机制，以发布一个能够准确近似实际度分布的度序列。现有的解决方案大多使用基于边删除过程的图投影技术，并通过阈值参数θ来限制节点的度。然而，这种方法在阈值参数选择上存在一个根本性的权衡：较大的θ值会在发布的度序列中引入大量噪声，而较小的θ值则会导致删除过多的边。此外，θ的选择还会导致过高的通信成本。为了解决现有解决方案的不足，我们提出了CADR-LDP，这是一个结合了加密技术和差分隐私机制的有效框架，用于发布度序列。在CADR-LDP中，我们首先使用加密辅助的最优θ选择方法来选择具有低通信成本的最优参数。然后，我们使用LPEA-LOW方法在局部投影中为每个节点添加一些边。LPEA-LOW优先处理低度节点的投影，这样可以保留这些节点的更多边并减少投影误差。理论分析表明，CADR-LDP满足?节点局部差分隐私。在八个图数据集上的实验结果表明，我们的解决方案优于现有方法。

**AI生成的摘要（实验）**
此摘要是使用自动化工具生成的，并非由文章作者编写或审核。它旨在帮助发现、评估相关性，并协助来自相关研究领域的读者理解该工作。它旨在补充作者提供的摘要，后者仍然是论文的主要摘要。完整文章是权威版本。点击此处了解更多信息。点击此处评论此摘要的准确性、清晰度和实用性。您的反馈将有助于改进和未来重新生成的版本。要查看此由AI生成的通俗语言摘要，您必须具有高级访问权限。

**1 引言**
在图数据中，度序列旨在描述度概率分布，从而提供有关图结构和属性的见解。然而，图度序列的发布是在敏感的图数据上进行的，这些数据可能会通过出版结果泄露[1, 2, 5]。因此，需要能够发布度序列同时仍保持图中个体隐私的模型。一个有前景的模型是局部差分隐私（LDP）[7, 8]，其中每个用户在将其数据提交给收集器之前会对其进行局部编码和扰动。该模型消除了对可信收集器的需求，使用户能够控制自己的实际度信息。两种自然的LDP变体特别适合图数据：边LDP [25] 和节点LDP [29]。直观地说，前者保护节点之间的关系，而后者通过保护每个个体及其相关关系提供更强的隐私保障。尽管节点LDP提供的隐私保障更为强大，但实现起来更具挑战性。这是因为，在最坏的情况下，删除一个节点可能会影响多达n-1个其他节点（其中n是节点总数），这可能导致度序列发布的敏感性很高，特别是在大型图中。如果应用Laplace机制[9, 10]（例如，添加从Lap(n?1?)采样的噪声）来保护度计数，那么产生的扰动可能会严重扭曲真实值。因此，大多数现有方法[11, 13, 14, 15, 16, 17, 18, 23, 25, 29]采用边LDP来保护图数据的发布。

**为了解决高敏感性问题，满足节点LDP的关键技术是图投影，它将图投影到一个最大度不超过θ的θ度受限图中[5, 20, 21, 22]。当前的研究通常采用边删除或边添加过程来限制每个节点的度计数[20, 21, 22]。一个关键挑战是在从投影图中发布度序列的同时，尽可能保留关于边的信息。然而，现有的投影解决方案[5, 20]仅针对中心差分隐私模型提出，不能直接用于边LDP。这是因为中心设置允许全局估计θ，而在局部设置中，每个用户仅限于自己的度信息，无法观察邻居的数据。估计整个图的θ是具有挑战性的。现有研究（例如EDGE-REMOVE [21, 22]）通常依赖于边删除过程来发布度序列。给定参数θ，在边删除过程中，每个用户ui从其邻居节点中随机采样di?θ条边进行删除，其中di表示ui的度。然而，边删除过程会删除比必要的更多的边。基于边删除过程的解决方案有三个尚未解决的问题：（1）难以获得最优参数θ。较大的θ会导致添加的噪声幅度更大，而较低的θ会导致删除更多的边；（2）现有解决方案没有考虑被删除边的用户的意愿，从而导致过度删除边；（3）这些方法没有考虑其邻居节点之间度计数的排序。为了说明这些限制，图1展示了一个使用边删除过程的例子。**图1. EDGE-REMOVE、RANDOM-ADD和LPEA-LOW的比较**

**示例1**
给定θ=1，节点B的度为3。我们需要从集合{BA, BC, BD}中随机删除两条边。如果删除边BC和BD，则受限图如图1(2)所示。删除BD后，节点D的度变为零。尽管如此，由于其只有一条边（BD），节点D会根据其边删除意愿抵制这次删除。

与依赖边删除投影的现有节点LDP方法不同，我们的分析表明，随机边添加投影（例如RANDOM-ADD [5]）比边删除具有更高的准确性。基于Facebook数据集，我们使用MAE和|E′||E|比率来衡量上述两种方法的准确性，其中E′和E分别表示投影图和原始图的边集。如图2所示，当投影参数θ从1变化到50时，基于边添加过程的解决方案在MAE和|E′||E|比率方面都优于基于边删除的方法。

**图2. Facebook数据集上EDGE-REMOVE、RANDOM-ADD和LPEA-LOW的比较**
尽管基于边添加过程的解决方案可以提高度分布的准确性，但它们没有考虑边添加的顺序；相反，它们是随机执行的。我们的分析表明，从低度节点开始添加边可以在投影图中保留更多的功能边。阈值限制了可以保留的边数。因此，低度用户在选择边时灵活性较低，因此更有可能失去原始的连接信息。基于此分析，我们提出了LPEA-LOW，这是一种优先处理低度节点并依次添加边直到满足θ的局部边添加投影方法。图2显示LPEA-LOW优于RANDOM-ADD和EDGE-REMOVE。基于图1，我们给出了第二个示例来展示LPEA-LOW的优势，如示例2所示。

**示例2**
给定θ = 1，假设节点开始局部投影的顺序是：B→C→A→D。在EDGE-REMOVE中，如果节点B随机删除边BC和BD以达到θ = 1，则节点B完成其投影。然后节点C开始投影，但由于它只有一条边，因此不需要删除。节点A开始投影并随机删除边AC以达到θ = 1，之后节点A完成其投影。节点D没有边，因此不需要删除。EDGE-REMOVE投影的结果如图1(2)所示，其中只剩下边BA。在RANDOM-ADD中，如果节点B随机添加边BC，节点B和C达到θ = 1并完成它们的投影。尽管节点A和D没有达到θ=1的条件，但边BA、AC和BD不能再添加。RANDOM-ADD投影的结果如图1(3)所示，其中只剩下边BC。在LPEA-LOW中，节点B不随机选择要添加的边，而是优先选择与其低度邻居D连接。同样，节点C优先与其低度邻居A连接。在达到θ = 1后，LPEA-LOW的投影结果如图1(4)所示。这个例子表明，在相同条件下，我们的方法保留了更多的边。

由于基于节点LDP的图投影缺乏全局视图，该过程依赖于节点之间的相互协商以及节点与收集器之间的消息交换来确定每个节点邻居的度计数顺序。然而，直接协商和交换会导致几个隐私风险：（1）θ的选择可能会泄露隐私，因为收集器只能通过汇总每个节点的实际度计数来获得最优θ。（2）边删除和边添加过程可能会引入隐私泄露，因为这些操作可能会揭示一个节点的度是否大于θ。（3）投影后的度可能会泄露隐私。为了解决这些问题，EDGE-REMOVE使用WRR [26]机制、OPE [28]加密协议和安全聚合技术来在节点LDP下发布度序列。然而，这种方法可能会导致较高的计算和通信成本。这是因为每轮聚合都需要局部投影。受到低度节点的边添加过程的启发，这可以提高发布度序列的准确性，我们提出了一个名为CADR-LDP的加密辅助框架来发布度序列。我们的主要贡献有三个方面：
- 为了克服现有基于边删除的图投影方法中的过度边丢失问题，我们提出了LPEA-LOW，该方法使用边添加过程来限制原始图。我们的核心思想是优先处理低度节点的边添加，这是基于大多数图遵循长尾度分布的事实，其中低度节点占主导地位。因此，我们的方法可以保留这些节点中的更多边。为了防止在边添加过程中泄露隐私，我们结合了WRR、指数和Laplace机制来保护节点度信息。
- 为了推导出最优投影参数θ，我们提出了两种加密辅助的优化方法：Optimal-θ-Selection-by-Sum和Optimal-θ-Selection-by-Deviation。这两种方法采用不同的优化策略：（1）经验最小化总和误差函数；（2）通过误差函数微分进行解析推导，以确定θ。值得注意的是，后一种方法的通信成本低于前者。
- 在真实图数据集上的广泛实验表明，我们提出的方法可以在隐私和效用之间实现更好的权衡。

**2 初步**
本节介绍了问题定义、节点LDP和安全聚合。通过确保扰动后的度满足?-node-LDP，收集者无法高置信度地区分某个度与其他可能的度。定义2.1。（node-LDP）[29] 如果对于任意vi,vj∈V，它们的相邻向量Bi和Bj最多只相差n位，并且对于任意输出o∈O，以下条件成立：Pr[M(Bi)=o]≤exp?(ε)×Pr[M(Bj)=o]，（3）则随机算法M满足?-node-LDP，其中参数?被称为隐私预算，用于在随机算法M中平衡效用和隐私之间的权衡。较小的?值意味着更高的隐私保护水平。O表示M的输出域。

拉普拉斯机制[9, 10]。满足差分隐私的一种方法是在查询的输出中添加噪声。在拉普拉斯机制中，为了在满足?-差分隐私的同时释放f(G)，其中f:D→Rd，人们会释放M(G)=f(G)+Lap(Δf?)，其中Δf=max|G?G′|f(G)?f(G′)|，并且Pr[Lap(β)=x]=1/2βe^(-|x|/β)。

指数机制[24]。这种机制适用于我们希望选择最佳响应的情况，但直接在计算出的量中添加噪声。给定一个数据集G（G∈G）和一个效用函数u:G×O→R，该函数将数据集/输出对映射到效用分数u(G,o)。直观地说，对于一个固定的图G，用户希望该机制以与exp(?u(G,o)^2Δu)成比例的概率输出O中的某个元素o，其中Δu=max|u(G,o)?u(G′,o)|是分数函数的敏感性。这种机制保持了?-差分隐私。

沃纳随机响应[26]：WRR。在LDP中，这种机制是生成敏感布尔问题随机值的一个构建块。具体来说，每个用户以概率p发送真实值，以概率1-p发送虚假值。为了使WRR满足?-LDP，我们设置p如下：p=e^(-?)/e^(-?+1)。

组合属性[24]。这个属性保证，对于任何计算序列M1,M2,...,Mk，如果每个Mi都满足?i-差分隐私，那么释放所有M1,M2,...,Mk的结果将满足∑i=1k?i-差分隐私。

2.3 安全聚合
正式地，安全聚合[3]构成了一个私有的{MPC}协议，其中用户在加性秘密共享下传输掩码输入，确保收集者只能了解到用户数据的聚合和。掩码生成遵循Diffie-Hellman（记为DH [6]）密钥交换协议。DH协议使两方能够在不安全的通信通道上建立共享秘密。每个用户独立生成一个私钥ai∈Z_q，并使用一个公知的循环群G的生成器g计算相应的公钥pki=g_a^i。在交换公钥后，双方可以推导出相同的共享秘密ki,j=ga_a^i*a_j，而不会泄露他们的私钥。这个属性为聚合协议中的安全成对掩码提供了基础。DH协议被参数化为三元组：DH=(KA.param,KA.gen,KA.agree)，其中KA.param(1^λ)→(Q,g,q)输出一个阶为q的群G和生成器g，给定一个安全参数λ。这里，1^λ表示安全参数λ的一元编码，用于指示算法的运行时间取决于λ的位长度（例如，密钥大小）。KA.gen(Q,g,q)→(sk,pk)生成私钥sk=a←Z_q和公钥pk=ga。这里，←$表示均匀随机采样。例如，a←Z_q意味着a是从有限域Z_q中随机选择的。KA.agree(sk,pk)→ki,j计算共享秘密ki,j=pk*a_j。kj,i是使用相同的公钥参数(Q,g,q)推导出来的，这确保了ki,j=kj,i。在DH协议中，每个用户生成ai∈Z_q并计算pki=g_a^i。在交换公钥后，双方推导出共享秘密ki,j=ga_a^i*a_j。假设i< />< />< />< />θ}|=0?n?=|{i:di>θ}|（7），其中??θ(max(0,di?θ)) = -1当di>θ时。由于实际度超过θ的用户数量未知，我们使用-|{i:di>θ}|来代替??θ(max(0,di?θ))，其中|{i:di>θ}|表示度超过θ的用户数量。根据算法3，我们知道最优θ是度序列的（1 - 1?）分位数。这个分位数保证了n?个度超过θ的用户，从而最小化了总误差。因此，算法3利用收集者的全局视图来计算（1 - 1?）分位数。收集者在候选参数范围内进行二分搜索。在每次迭代中，收集者选择该范围的中位数θ*作为候选投影参数，并与所有用户共享θ*（第2-5行）。每个用户将其度di与θ*进行比较。如果di>θ*，用户设置r=1，否则r=0（第6-11行）。然而，设置r可能包含敏感信息，这有助于收集者推断用户的真实度。例如，如果用户i的度di=3，收集者将通过询问di>2和di<4来推断该值。为了保护ri，用户需要依赖安全聚合来加密它（第12-14行），收集者聚合加密后的设置，表示为∑_i=1^n Enc(ri)。如果∑_i=1^n Enc(ri)≥n?，收集者更新边界θL←θ*+1，否则θL←θ*?1（第17-21行）。迭代直到找到最优θ=θL。

算法3提供了一个理论解决方案，与算法2在参数选择精度上有所不同，因为后者基于实际误差值进行聚合。这种方法使算法2能够实现更高的精度，而算法3则受益于更低的计算成本。因此，它们之间的选择应取决于具体应用需求。

3.3 邻居的度顺序编码：NDOE
算法1表明，节点vi在获取θ后开始边添加过程。图2显示，先从度较小的节点添加边可以获得更好的度序列释放精度。然而，这个过程要求vi知道其邻居的度顺序。由于邻居的度计数包含私人信息，这些用户拒绝明确与vi共享它们。[28]提出了一种适合多用户的保持顺序的加密协议，但它需要一个可信的第三方并且通信成本较高。[4]提出了一种编码方法OP_εc，可以实现部分顺序保持。这种方法允许用户在本地保护数据的同时实现部分顺序保持。然而，这种方法不能直接应用于节点LDP模型，因为该方法通常只保护一个值，而节点LDP需要保护与节点相关的所有边信息。因此，基于节点LDP，我们提出了带有OPεc和指数机制的NODE方法，如算法4所示。NODE编码了vi’相邻节点的度信息，并使用编码结果作为它们的度顺序信息。在算法4中，用户i计算所有区间内扰动的概率pi,j，其中pi,j是节点vi被扰动到第j个分区的概率（第1-4行）。然后，给定|O|个位置，用户i获得每个位置的相关扰动概率{pi,1,...,pi,|O|}。最后，用户i以概率pi从编码范围O中采样其度顺序信息oi（第5行）。如算法1所解释的，用户i使用从收集器共享的两个参数P和O来设置得分函数u和灵敏度Δu。NODE实现了偏序保持，因为它确保用户i采样其度所在的位置。给定用户i的度di和第j个分区，得分函数u=-|di?median(P[j])|，其中median(P[j])是第j个分区的中位数值。得分函数u的灵敏度Δu计算如下：Δu=maxo∈O?maxdi?dj?|u(di,o)?u(dj,o)|=maxo∈O?maxdi?dj?||dj?median(P[o])|?|di?median(P[o])||。（8）从方程（8）可以看出，当di=dmax和dj=dmin时，Δu=dmax?dmin。因此，用户i以概率pi从范围O中随机采样一个值oi作为度顺序，并将其发送给所有邻居。

定理3.1。NODE算法满足αε2-节点LDP。证明。设di和dj分别是G中vi和vj的度。根据指数机制，对于di和dj，NODE算法输出的度顺序编码o满足以下等式：Pr[NDOE(di,αε2)=o]=(exp?(u(di,o)?αε22Δu)∑o′∈Oexp?(u(di,o′)?αε22Δu))，Pr[NDOE(dj,αε2)=o]=(exp?(u(dj,o)?αε22Δu)∑o′∈Oexp?(u(dj,o′)?αε22Δu))。（10）根据定义2.1，Pr[NODE(di,α?2)=o]Pr[NODE(dj,α?2)=o]≤exp?((u(di,o)?u(dj,o))?α?22Δu)×exp?(|dj?di|)?α?22Δu≤exp?(α?2)。□因此，NODE算法满足α?2-节点LDP。

3.4 本地投影边添加-低：LPEA-LOW
在获得最优投影参数θ和邻居节点的度顺序后，每个用户开始与其度较小的邻居进行边连接协商。然而，这种相互协商过程本质上涉及双方之间交换私有信息。因此，我们提出了带有WRR机制的LPEA-LOW来保护这一过程，具体细节见算法5。在算法5中，用户i首先设置一个全零向量Bi―来记录添加的边（第2行）。在边添加过程之前，用户将Bi―中所有已建立边的位置值设置为1（第3行）。随后，用户将没有建立边的邻居标记为集合U1，并向它们发送边添加请求（第4-5行）。对于U1中的用户，如果|Bi―|<θ，则以p=e?e?+1响应“是”，否则以q=1e?+1响应“否”。p和q的值会互换（第7-12行）。在第7-12行中，我们使用wrr机制来保护用户i’邻居的隐私。如果邻居节点vj∈u1拒绝边添加请求，就表明vj’的度超过了参数θ，这是一个敏感信息。用户i调整所有邻居的“是”响应数量，得到调整后的数量c′。用户将c′与θ?|bi―|进行比较，得到最小值s，即s←min(θ?|bi―|)，其中θ?|bi―|表示节点vi的剩余边容量。最后，用户选择s个度较小的邻居形成集合u3，并与它们建立边（第15-21行）。 定理3.2。设|u1|为响应边添加请求的邻居数量，c为实际可用于建立边的邻居数量，c′为经过lpea-low算法处理后的数量。对于任何节点vi，我们有e[c′]=c。证明。设|U2|为对边添加请求响应为“是”的邻居数量，则以下等式成立：|U2|=c?eεeε+1+(|U1|?c)?1eε+1。（12）由于节点vi无法知道c的真实值，因此计算出相应的估计值c′：c′=|U2|?(eε+1)?|U1|eε?1。（13）因此，期望值E[c′]可以表示为：E[c′]=E[|U2|]?(eε+1)?|U1|eε?1。（14）根据这个等式和公式12，我们得出E[c′]=c成立。□ 3.5 度序列发布：dsr 在算法1中，当所有用户使用参数θ投影他们的度时，他们将具有灵敏度θ的拉普拉斯噪声注入到投影后的度中。然后他们将带噪声的度计数发送给收集器。基于这个想法，我们提出了dsr算法，如算法6所示。在算法6中，每个用户首先根据本地投影的邻接向量bi―计算其度di―（第3行）。然后用户使用具有灵敏度θ的拉普拉斯机制来扰动di―，得到噪声度di~。同时，用户将di~发送给收集器（第4-5行）。收集器汇总噪声度计数并计算噪声度序列和分布（第8-9行）。 定理3.3。dsr算法满足（1?α）ε-节点ldp。证明。设di―和dj―是任意两个节点vi和vj的两个投影度。dsr算法的噪声输出d~满足以下等式：pr[dsr(d―i,(1?α)ε)=d~]Pr[DSR(d―j,(1?α)ε)=d~]=exp?(?|d~?d―i|?(1?α)εθ)exp?(?|d~?d―j|?(1?α)εθ)=exp?((|d~?d―j|?|d~?d―i|)?(1?α)?θ)≤exp?(|d―i?d―j|?(1?α)?θ)≤exp?((1?α)ε）。□根据定义2.1，DSR算法满足（1?α）?-节点LDP。 定理3.4。cadr-ldp满足ε-节点ldp。证明。在cadr-ldp框架中，node算法使用具有隐私预算α?2的指数机制。lpea-low算法使用具有隐私预算α?2的wrr机制。dsr算法使用具有隐私预算（1?α）?的拉普拉斯机制。所有其他步骤都是独立的，并在噪声输出上执行。根据组合属性[24]，cadr-ldp满足ε-节点ldp。□ 3.6 cadr-ldp的复杂性分析 我们从用户的角度分析cadr-ldp的整体计算复杂性。首先，我们分析每个用户执行的每个算法的复杂性，然后评估整体用户级别的复杂性。 （1）在算法2中，每个用户在每次迭代中执行一次本地边添加投影，每次迭代的复杂度为dmax。经过k次迭代后，这导致本地计算成本为o(kdmax)。同时，每次聚合轮次需要每个用户与n?1个其他用户进行密钥协商，导致每轮的成本为o(n)。在k次迭代中，密钥协商成本变为o(nk)。由于这一项占主导地位，算法2的整体时间复杂度为o(nk)。 （2）在算法3中，每次迭代需要每个用户进行一次度比较。在k次迭代过程中（需要log22k步），通过二分搜索辅助，每个用户的本地计算复杂度为o(log22k)。然而，主要成本来自密钥协商：在每次聚合轮次中，每个用户必须与n?1个其他用户建立协议。将这些因素结合起来，算法的整体计算复杂度为o(nlog22k)。 （3）在算法4中，每个用户扰动其真实的度以确定度排序。对于每个分区，用户需要计算其扰动概率。结果复杂度为o(psize)。 （4）在算法5中，每个用户对每个边添加请求执行一次扰动计算。由于最多有n个用户发送边添加请求，复杂度为o(n)。 （5）在算法6中，所有用户需要在投影和扰动步骤后报告他们的噪声度。由于这个报告过程对每个用户来说是常数时间操作，整体复杂度为o(1)。 如上述分析所示，用户在cadr-ldp框架下发布他们的度序列的整体时间复杂度要么是o(nk)，要么是o(nlog22k)，具体取决于所选的算法。 3.7 cadr-ldp的误差分析 定理3.5。设vi是图中的任意用户节点，di表示vi的原始度。设di~表示在cadr-ldp下发布的节点vi的噪声度。那么，以下效用界限成立：mse(di?d~i)≤(|τi|+vi)2+2b2，mae(di?d~i)≤|τi|+vi+b，其中vi≤|u1|eα?2(eα?2?1)2，b=θ(1?α)?，τi=di?di?，di?=Πθ(di)。这里，Πθ表示强制度阈值θ的确定性投影运算符，τi表示vi的度值的确定性投影失真，U1表示在投影阶段使用的候选节点集。ε是总隐私预算。 证明。设|u1|表示u1的基数。对于u1中的每个查询候选节点vj，我们定义一个二进制指示器tj=><θ}，其中|b―j|是vj已经建立的边数。设xj∈{0,1}是vj的随机响应。如果tj=1，则xj=1，否则xj=0，p=eα?2eα?2+1，q=1eα?2+1。我们定义|u2|=∑j∈u1xj和c=∑j∈u1tj。根据定理3.2，c的无偏估计量为c′=|u2|?|u1|qp?q。设c=θ?di(0)，其中di(0)是vi的初始度。我们使用s=min(c′,c)和s?=min(c,c)来表示c′和c的截断结果。因此，vi的投影度为di―=di(0)+s。投影误差可以表示为δi=di??d―i=s??s。我们将误差di?d~i分解为三个部分：确定性投影失真τi、随机投影误差δi和拉普拉斯噪声ηi。即di?d~i=di?di??τi+di??d―i?δi?ηi。（16）随机响应误差。在算法5中，随机响应机制使用wrr实现，这本质上引入了随机响应误差。根据定理3.2，我们有c的无偏估计量c′=(|u2|?|u1|q)/(p?q)，其中|u2|=∑jxj。由于随机变量xj的独立性，我们有以下方差，var(c′)=|u1|pq(p?q)2=vi。投影截断误差。在算法5中，我们使用θ来投影每个节点的度，并使用c=θ?di(0)来截断c和c′，即s=min(c′,c)和s?=min(c,c)。因此，我们得到δi=s??s。由于截断满足1-lipschitz，我们有|δi|=|s??s|=|min(c,c)|≤|c?c′|。由于e[c′]=c在定理3.2中，我们有e[δi2]≤var(c′)=vi。均方误差。根据公式16和δi和ηi的独立性，我们有e[(di?d~i)2]=e[(τi+δi)2]=e[(τi+δi)2]+e[ηi2]。应用柯西-施瓦茨不等式和e[δi2]的界限，我们有e[(τi+δi)2]≤(|τi|+e[δi2])2≤(|τi|+vi)2。由于ηi～lap(b)且e[ηi2]=2b2，我们得到mse界限e[(di?d~i)2]≤(|τi|+vi)2+2b2。均绝对误差。同样，根据三角不等式和柯西-施瓦茨不等式，我们有e[|di?d~i|]≤|τi|+e[|δi|]+e[|ηi|]≤|τi|+vi+b。这完成了证明。

4 实验
在本节中，我们报告了将我们提出的解决方案与现有技术进行比较的实验结果，并分析了我们提出的解决方案的不同方面如何影响效用。

4.1 数据集和设置
我们的实验在配备intel core i5-7300hq cpu、16 gb ram的python客户端上运行，操作系统为windows 10。我们使用了来自snap（https://snap.stanford.edu/data/）的8个真实世界图数据集，如表1所示。这些数据集来自不同的领域，包括引用、电子邮件和社交网络。我们预处理了所有图数据，使其无向且对称。表1还显示了一些额外信息，如|v|、|e|、dmax和davg，其中|v|表示节点数，|e|表示边数，dmax表示最大度，davg表示平均度。我们将我们的方法lpea-low和lpea-high与random-add和edge-remove进行比较，以发布节点度序列同时满足节点ldp。lpea-high是lpea-low的一个变体，在添加边时优先考虑度较高的节点。random-add算法使用边添加过程在节点之间随机添加边。edge-remove算法使用边删除过程在节点之间删除边。这四种投影方法在非私密和私有场景下进行了比较，所有结果都是20次运行的平均值。

表1. 图|v||e|dmaxdavg
facebook 4,039 88,23 41,0 45 43.69
wiki-vote 7,115 100,76 21,0 65 28.32
ca-hepph 12,008 118,50 54 9119.74
cit-hepph 34,546 420,89 98 46 24.37
email-enron 36,692 183,83 11,38 310.02
loc-brightkite 58,228 214,078 1,134 7.35
x（以前称为twitter）81,306 1,342,303 33.02
com-dblp 317,080 1,049,866 343 6.62

4.2 非私有环境中的性能比较
基于上述8个数据集，我们首先将我们提出的投影方法lpea-low（简称ll）与第4.1节中提到的其他三种投影方法er（edge-remove）、ra（random-add）和lh（lpea-high）进行直接比较。我们使用两个指标：mae误差和|e′||e|，其中e′表示投影后的边。表2中的每个数据集包含三行：第一行显示发布度序列的mae，第二行显示度分布的mae，第三行显示|e′||e|的比率。我们考虑了三个θ值，θ = 16, 64, 128。最低误差和最高的保留边比率用粗体突出显示以便于比较。

表2. 图θ=16 θ=64 θ=128
erralhllerralhllerralhll
facebook 34.56 31.98 32.58 31.02 16.17 14.90 15.92 13.38 5.80 5.79 6.34 4.71 1.27 1.27 1.28 1.27 0.49 0.50 0.50 0.50 0.52 0.26 0.27 0.28 0.27 0.21 0.27 0.25 0.29 0.63 0.66 0.64 0.69 0.87 0.87 0.85 0.89
wiki-vote 24.31 23.04 23.40 21.46 4.73 14.05 14.94 12.23 8.01 7.82 8.58 6.82 0.95 1.12 1.18 0.68 0.40 0.56 0.59 0.31 0.22 0.31 0.34 0.17 0.14 0.19 0.24 0.48 0.50 0.47 0.57 0.72 0.72 0.70 0.76
ca-hepph 13.87 13.32 13.45 12.67 7.71 7.44 7.61 6.58 4.75 4.54 4.80 3.80 0.49 0.53 0.58 0.47 0.18 0.19 0.22 0.17 0.12 0.13 0.14 0.09 0.30 0.33 0.33 0.35 0.61 0.62 0.61 0.67 0.76 0.77 0.81
cit-hepph 15.70 15.45 15.78 13.56 5.10 5.35 5.68 4.41 1.72 1.77 1.79 1.62 0.94 0.98 1.02 0.94 0.19 0.25 0.29 0.18 0.08 0.08 0.06 0.36 0.36 0.35 0.44 0.79 0.78 0.77 0.82 0.93 0.93 0.93 0.93
email-enron 6.71 6.71 6.77 6.20 4.07 4.25 4.35 3.72 2.60 2.76 2.85 2.42 0.62 0.75 0.77 0.55 0.41 0.52 0.54 0.28 0.30 0.42 0.45 0.18 0.32 0.33 0.32 0.38 0.59 0.57 0.56 0.63 0.74 0.72 0.71 0.76
loc-brightkite 3.71 3.74 3.81 3.30 1.51 1.58 1.65 1.34 0.71 0.75 0.76 0.65 0.27 0.42 0.44 0.22 0.08 0.13 0.14 0.05 0.04 0.06 0.07 0.02 0.49 0.49 0.48 0.55 0.79 0.78 0.78 0.82 0.90 0.90 0.90 0.91
x 26.14 25.07 25.73 23.66 14.78 14.53 15.59 12.97 8.62 8.66 9.39 7.70 0.93 0.96 1.00 0.93 0.31 0.38 0.46 0.28 0.16 0.19 0.25 0.21 0.24 0.22 0.28 0.55 0.56 0.53 0.61 0.73 0.73 0.71 0.77

4.2 非私有环境中的性能比较
基于上述8个数据集，我们首先将我们提出的投影方法lpea-low（简称ll）与第4.1节中提到的其他三种投影方法er（edge-remove）、ra（random-add）和lh（lpea-high）进行直接比较。我们使用两个指标：mae误差和|e′||e|，其中e′表示投影后的边。表2中的每个数据集包含三行：第一行显示发布度序列的mae，第二行显示度分布的mae，第三行显示|e′||e|的比率。我们考虑了三个θ值，θ = 16, 64, 128。最低误差和最高的保留边比率用粗体突出显示以便于比较。 (p?q)，其中|u2|=∑jXj。由于随机变量Xj的独立性，我们有以下方差，Var(c′)=|U1|pq(p?q)2=Vi。投影截断误差。在算法5中，我们使用θ来投影每个节点的度，并使用C=θ?di(0)来截断c和c′，即s=min(c′,C)和s?=min(c,C)。因此，我们得到Δi=s??s。由于截断满足1-Lipschitz，我们有|Δi|=|s??s|=|min(c,C)|≤|c?c′|。由于E[c′]=c在定理3.2中，我们有E[Δi2]≤Var(c′)=Vi。均方误差。根据公式16和Δi和ηi的独立性，我们有E[(di?d~i)2]=E[(τi+Δi)2]=E[(τi+Δi)2]+E[ηi2]。应用柯西-施瓦茨不等式和E[Δi2]的界限，我们有E[(τi+Δi)2]≤(|τi|+E[Δi2])2≤(|τi|+Vi)2。由于ηi～Lap(b)且E[ηi2]=2b2，我们得到MSE界限E[(di?d~i)2]≤(|τi|+Vi)2+2b2。均绝对误差。同样，根据三角不等式和柯西-施瓦茨不等式，我们有E[|di?d~i|]≤|τi|+E[|Δi|]+E[|ηi|]≤|τi|+Vi+b。这完成了证明。 4 实验 在本节中，我们报告了将我们提出的解决方案与现有技术进行比较的实验结果，并分析了我们提出的解决方案的不同方面如何影响效用。 4.1 数据集和设置 我们的实验在配备intel core i5-7300hq cpu、16 gb ram的python客户端上运行，操作系统为windows 10。我们使用了来自snap（https: snap.stanford.edu data ）的8个真实世界图数据集，如表1所示。这些数据集来自不同的领域，包括引用、电子邮件和社交网络。我们预处理了所有图数据，使其无向且对称。表1还显示了一些额外信息，如|v|、|e|、dmax和davg，其中|v|表示节点数，|e|表示边数，dmax表示最大度，davg表示平均度。我们将我们的方法lpea-low和lpea-high与random-add和edge-remove进行比较，以发布节点度序列同时满足节点ldp。lpea-high是lpea-low的一个变体，在添加边时优先考虑度较高的节点。random-add算法使用边添加过程在节点之间随机添加边。edge-remove算法使用边删除过程在节点之间删除边。这四种投影方法在非私密和私有场景下进行了比较，所有结果都是20次运行的平均值。 表1. 图|v||e|dmaxdavg facebook 4,039 88,23 41,0 45 43.69 wiki-vote 7,115 100,76 21,0 65 28.32 ca-hepph 12,008 118,50 54 9119.74 cit-hepph 34,546 420,89 98 46 24.37 email-enron 36,692 183,83 11,38 310.02 loc-brightkite 58,228 214,078 1,134 7.35 x（以前称为twitter）81,306 1,342,303 33.02 com-dblp 317,080 1,049,866 343 6.62 4.2 非私有环境中的性能比较 基于上述8个数据集，我们首先将我们提出的投影方法lpea-low（简称ll）与第4.1节中提到的其他三种投影方法er（edge-remove）、ra（random-add）和lh（lpea-high）进行直接比较。我们使用两个指标：mae误差和|e′||e|，其中e′表示投影后的边。表2中的每个数据集包含三行：第一行显示发布度序列的mae，第二行显示度分布的mae，第三行显示|e′||e|的比率。我们考虑了三个θ值，θ=16, 64, 128。最低误差和最高的保留边比率用粗体突出显示以便于比较。 表2. 图θ=16 θ=64 θ=128 erralhllerralhllerralhll facebook 34.56 31.98 32.58 31.02 16.17 14.90 15.92 13.38 5.80 5.79 6.34 4.71 1.27 1.27 1.28 1.27 0.49 0.50 0.50 0.50 0.52 0.26 0.27 0.28 0.27 0.21 0.27 0.25 0.29 0.63 0.66 0.64 0.69 0.87 0.87 0.85 0.89 wiki-vote 24.31 23.04 23.40 21.46 4.73 14.05 14.94 12.23 8.01 7.82 8.58 6.82 0.95 1.12 1.18 0.68 0.40 0.56 0.59 0.31 0.22 0.31 0.34 0.17 0.14 0.19 0.24 0.48 0.50 0.47 0.57 0.72 0.72 0.70 0.76 ca-hepph 13.87 13.32 13.45 12.67 7.71 7.44 7.61 6.58 4.75 4.54 4.80 3.80 0.49 0.53 0.58 0.47 0.18 0.19 0.22 0.17 0.12 0.13 0.14 0.09 0.30 0.33 0.33 0.35 0.61 0.62 0.61 0.67 0.76 0.77 0.81 cit-hepph 15.70 15.45 15.78 13.56 5.10 5.35 5.68 4.41 1.72 1.77 1.79 1.62 0.94 0.98 1.02 0.94 0.19 0.25 0.29 0.18 0.08 0.08 0.06 0.36 0.36 0.35 0.44 0.79 0.78 0.77 0.82 0.93 0.93 0.93 0.93 email-enron 6.71 6.71 6.77 6.20 4.07 4.25 4.35 3.72 2.60 2.76 2.85 2.42 0.62 0.75 0.77 0.55 0.41 0.52 0.54 0.28 0.30 0.42 0.45 0.18 0.32 0.33 0.32 0.38 0.59 0.57 0.56 0.63 0.74 0.72 0.71 0.76 loc-brightkite 3.71 3.74 3.81 3.30 1.51 1.58 1.65 1.34 0.71 0.75 0.76 0.65 0.27 0.42 0.44 0.22 0.08 0.13 0.14 0.05 0.04 0.06 0.07 0.02 0.49 0.49 0.48 0.55 0.79 0.78 0.78 0.82 0.90 0.90 0.90 0.91 x 26.14 25.07 25.73 23.66 14.78 14.53 15.59 12.97 8.62 8.66 9.39 7.70 0.93 0.96 1.00 0.93 0.31 0.38 0.46 0.28 0.16 0.19 0.25 0.21 0.24 0.22 0.28 0.55 0.56 0.53 0.61 0.73 0.73 0.71 0.77 4.2 非私有环境中的性能比较 基于上述8个数据集，我们首先将我们提出的投影方法lpea-low（简称ll）与第4.1节中提到的其他三种投影方法er（edge-remove）、ra（random-add）和lh（lpea-high）进行直接比较。我们使用两个指标：mae误差和|e′||e|，其中e′表示投影后的边。表2中的每个数据集包含三行：第一行显示发布度序列的mae，第二行显示度分布的mae，第三行显示|e′||e|的比率。我们考虑了三个θ值，θ=16, 64,>
4 实验
在本节中，我们报告了将我们提出的解决方案与现有技术进行比较的实验结果，并分析了我们提出的解决方案的不同方面如何影响效用。

4.1 数据集和设置
我们的实验在配备intel core i5-7300hq cpu、16 gb ram的python客户端上运行，操作系统为windows 10。我们使用了来自snap（https://snap.stanford.edu/data/）的8个真实世界图数据集，如表1所示。这些数据集来自不同的领域，包括引用、电子邮件和社交网络。我们预处理了所有图数据，使其无向且对称。表1还显示了一些额外信息，如|v|、|e|、dmax和davg，其中|v|表示节点数，|e|表示边数，dmax表示最大度，davg表示平均度。我们将我们的方法lpea-low和lpea-high与random-add和edge-remove进行比较，以发布节点度序列同时满足节点ldp。lpea-high是lpea-low的一个变体，在添加边时优先考虑度较高的节点。random-add算法使用边添加过程在节点之间随机添加边。edge-remove算法使用边删除过程在节点之间删除边。这四种投影方法在非私密和私有场景下进行了比较，所有结果都是20次运行的平均值。

表1. 图|v||e|dmaxdavg
facebook 4,039 88,23 41,0 45 43.69
wiki-vote 7,115 100,76 21,0 65 28.32
ca-hepph 12,008 118,50 54 9119.74
cit-hepph 34,546 420,89 98 46 24.37
email-enron 36,692 183,83 11,38 310.02
loc-brightkite 58,228 214,078 1,134 7.35
x（以前称为twitter）81,306 1,342,303 33.02
com-dblp 317,080 1,049,866 343 6.62

4.2 非私有环境中的性能比较
基于上述8个数据集，我们首先将我们提出的投影方法lpea-low（简称ll）与第4.1节中提到的其他三种投影方法er（edge-remove）、ra（random-add）和lh（lpea-high）进行直接比较。我们使用两个指标：mae误差和|e′||e|，其中e′表示投影后的边。表2中的每个数据集包含三行：第一行显示发布度序列的mae，第二行显示度分布的mae，第三行显示|e′||e|的比率。我们考虑了三个θ值，θ = 16, 64, 128。最低误差和最高的保留边比率用粗体突出显示以便于比较。

表2. 图θ=16 θ=64 θ=128
erralhllerralhllerralhll
facebook 34.56 31.98 32.58 31.02 16.17 14.90 15.92 13.38 5.80 5.79 6.34 4.71 1.27 1.27 1.28 1.27 0.49 0.50 0.50 0.50 0.52 0.26 0.27 0.28 0.27 0.21 0.27 0.25 0.29 0.63 0.66 0.64 0.69 0.87 0.87 0.85 0.89
wiki-vote 24.31 23.04 23.40 21.46 4.73 14.05 14.94 12.23 8.01 7.82 8.58 6.82 0.95 1.12 1.18 0.68 0.40 0.56 0.59 0.31 0.22 0.31 0.34 0.17 0.14 0.19 0.24 0.48 0.50 0.47 0.57 0.72 0.72 0.70 0.76
ca-hepph 13.87 13.32 13.45 12.67 7.71 7.44 7.61 6.58 4.75 4.54 4.80 3.80 0.49 0.53 0.58 0.47 0.18 0.19 0.22 0.17 0.12 0.13 0.14 0.09 0.30 0.33 0.33 0.35 0.61 0.62 0.61 0.67 0.76 0.77 0.81
cit-hepph 15.70 15.45 15.78 13.56 5.10 5.35 5.68 4.41 1.72 1.77 1.79 1.62 0.94 0.98 1.02 0.94 0.19 0.25 0.29 0.18 0.08 0.08 0.06 0.36 0.36 0.35 0.44 0.79 0.78 0.77 0.82 0.93 0.93 0.93 0.93
email-enron 6.71 6.71 6.77 6.20 4.07 4.25 4.35 3.72 2.60 2.76 2.85 2.42 0.62 0.75 0.77 0.55 0.41 0.52 0.54 0.28 0.30 0.42 0.45 0.18 0.32 0.33 0.32 0.38 0.59 0.57 0.56 0.63 0.74 0.72 0.71 0.76
loc-brightkite 3.71 3.74 3.81 3.30 1.51 1.58 1.65 1.34 0.71 0.75 0.76 0.65 0.27 0.42 0.44 0.22 0.08 0.13 0.14 0.05 0.04 0.06 0.07 0.02 0.49 0.49 0.48 0.55 0.79 0.78 0.78 0.82 0.90 0.90 0.90 0.91
x 26.14 25.07 25.73 23.66 14.78 14.53 15.59 12.97 8.62 8.66 9.39 7.70 0.93 0.96 1.00 0.93 0.31 0.38 0.46 0.28 0.16 0.19 0.25 0.21 0.24 0.22 0.28 0.55 0.56 0.53 0.61 0.73 0.73 0.71 0.77

4.2 非私有环境中的性能比较
基于上述8个数据集，我们首先将我们提出的投影方法lpea-low（简称ll）与第4.1节中提到的其他三种投影方法er（edge-remove）、ra（random-add）和lh（lpea-high）进行直接比较。我们使用两个指标：mae误差和|e′||e|，其中e′表示投影后的边。表2中的每个数据集包含三行：第一行显示发布度序列的mae，第二行显示度分布的mae，第三行显示|e′||e|的比率。我们考虑了三个θ值，θ = 16, 64, 128。最低误差和最高的保留边比率用粗体突出显示以便于比较。>主要原因是LPEA-LOW从度数较小的节点开始添加边。4.3 最优投影参数选择为了探索最优参数θ的选择，我们使用?={1.0,1.5,2.0,2.5,3.0}评估了算法2和算法3的性能。表3显示了结果。从表3中我们可以看出，当?=3.0时，算法3获得了最优的θ，这最小化了度序列发布的MAE。然而，算法3可能无法保证找到最小化总误差的最优θ，而只是近似最优解。这是因为对于度数di≥θ的用户，投影造成的度数损失等于|di?θ|，而对于di<θ的用户，则没有度数损失。根据算法2的定义，真正的度数损失应该是di?di―。因此，算法2可以识别出最小化总误差的投影参数。但是，获取di―需要用户进行一轮额外的局部投影，从而增加了通信开销。表3。graphε=1 ε=1.5 ε=2 ε=2.5 ε=3 facebook 115 253 442 wiki-vote 124 1016 ca-hepph 135 79 cit-hepph 191 52024 email-enron 12345 loc-brightkite 11234 x18152127 com-dblp 13455 最优投影参数θ 4.4 私密环境下的性能比较在私有环境中，图4-6展示了lpea-low、lpea-high、random-add和edge-remove的度序列和分布发布情况。我们首先对这四种方法应用θ={1,2,…,100}和?=3，并在图4中报告了实验结果。结果表明，随着θ的变化，度序列发布的mae和mse呈现出凸趋势。这种趋势是因为投影引起的lae误差随着θ的增加而单调减少，而来自拉普拉斯噪声的llap误差随着θ的变化而增加。因此，这两种误差形成了一个优化权衡，决定了最优θ值。从图4的结果中我们可以看出，与其他三种算法相比，lpea-low在8个数据集上始终实现了更低的mae和mse。这是因为lpea-low从度数较小的相邻节点开始添加边，这在稀疏图中特别有效（例如loc-brightkite和com-dblp）。图5展示了使用表3中最优θ的所有方法的度序列发布的mae和mse，其中?从1变化到3。结果表明，随着?的减小，mae和mse都有所下降。我们提出的解决方案lpea-low在所有数据集上都取得了良好的准确性，并且优于所有其他差分隐私方法。例如，在loc-brightkite数据集中，当隐私预算相对较大时（例如?=3.0），其mae和mse始终保持在6.1和40.0以下。当?减小时，准确性会下降，但其mae仍然小于11.0。其他方法的性能不如我们的方法，因为在添加边时，我们考虑了度数相对较小的相邻用户的意愿。图4. 在?=3.0时，不同数据集上算法的mae和mse变化情况。图5. 在不同数据集上，随着?变化，算法的mae和mse变化情况。图6. 在α=0.1、ε=3以及表3中的最优θ设置下，比较了lpea-low与其他算法（lpea-high、random-add和edge-remove）的度分布质量。origin-graph线表示原始图的真实度分布。实验结果表明，edge-remove的表现最差，其次是random-add和lpea-high。观察中间结果，我们注意到edge-remove与origin-graph相差甚远。我们提出的方法显著优于其他三种方法，尤其是在较大的数据集上，能够得到相当准确的度分布。5 相关工作已经广泛研究了将节点中心差分隐私（node-cdp）应用于度分布和度序列。我们认为使用node-cdp比edge-cdp更有意义，因为node-cdp提供了对图数据的个人隐私控制。[12]中的工作研究了在edge-cdp下发布度序列的问题，该方法直接使用拉普拉斯机制生成lap(2?)噪声，并进行一致性推断以提高噪声序列的准确性。随后的几项工作[19, 30]探讨了发布度序列或分布的方法。然而，这些方法在node-cdp下变得不可行，因为敏感性可能是无界的。研究了使用图投影来限制敏感性的技术，以便在node-cdp下发布度分布[1, 5, 20]。在[5]中引入的边添加过程，随机将与度数超过θ的节点相关联的边插入。相比之下，截断方法[20]消除了所有度数超过θ的节点。同时，边删除过程[1]按随机顺序遍历所有边，并移除与度数超过θ的节点相连的边。然而，现有的投影方法仅适用于node-cdp，不适用于node-ldp和edge-ldp。在局部环境中，现有工作几乎都使用edge-ldp来研究各种图统计量，如度分布[29]、子图计数[11, 13, 14, 15, 16, 17, 18, 23]和合成图生成[25, 27]。例如，[29]中的工作提出了一种结合wrr [26]机制的一轮方法lf-gdrr来重建图结构以回答统计查询。基于lf-gdrr，[16, 17]分别提出了local2rounds和arrtwons方法。前者通过引入下载策略减少了三角形计数误差，后者通过结合非对称随机响应（arr）和条件下载策略提高了前者的准确性并降低了通信成本。随后，ws [18]解决方案被提出用于回答三角形和4环计数查询。这种方法采用楔形洗牌技术来实现隐私放大，同时减少了与local2rounds和arrtwons相比的误差。与local2rounds相比，tcrr [11]方法依赖于wrr的不同后处理来回答三角形计数查询，可以获得结果的方差的上界和下界。与[11, 16, 17, 18]不同，privet [23]引入了一种联邦三角形计数估计器，通过边关系-ldp来保护隐私，专门为相关数据收集场景设计。同时，dbe [13]专注于使用edge-ldp进行二分图的蝴蝶计数，而oddcyclec [14]针对度数有界的图进行循环计数。与上述局部模型中的工作不同，一些研究专注于在edge-ldp下生成合成图。ldpgen [25]提出了一种新颖的多阶段合成去中心化社交图生成方法，而sgldp [27]在保持图属性（如度分布、社区结构和属性分布）的同时，仔细估计了在edge-ldp下的属性图数据的联合分布。尽管上述方法使用edge-ldp来降低对图统计量的敏感性，但它们在度序列发布方面存在以下限制：（1）edge-ldp提供的隐私保障比node-ldp弱；（2）这些方法中的每个用户都需要发送长度为n的邻接向量，导致高通信成本。为了解决这些限制，edge-remove [21, 22]使用node-ldp和加密技术来发布度序列和分布，该方法采用边删除过程来投影原始图中每个节点的度数。这项工作的一个关键贡献在于它能够同时提供更高的发布准确性和增强隐私保障。然而，从图2中我们可以看出，由于忽略了每个用户的意愿，edge-remove可能会导致不必要的边被删除。此外，加密辅助的参数选择过程要求每个用户在每次迭代中进行一轮局部投影，导致高通信成本。与现有工作相比，我们的方法cadr-ldp引入了一种带有加密技术的边添加过程，进一步提高了效用并满足了node-ldp的要求。6 结论本研究专注于在node-ldp下使用加密技术保护节点隐私以发布度序列和分布。为了在效用和隐私之间取得更好的平衡，我们首先提出了一种边添加过程，该过程使用最优投影参数θ在局部限制了每个用户的度数。为了获得θ，我们进一步提出了两种估计方法，并引入了加密技术和指数机制来提供隐私保障。最后，在真实世界数据集上的广泛实验表明，我们的解决方案优于其竞争对手。 ε=1.5 ε=2 ε=2.5 ε=3 facebook 115 253 442 wiki-vote 124 1016 ca-hepph 135 79 cit-hepph 191 52024 email-enron 12345 loc-brightkite 11234 x18152127 com-dblp 13455 最优投影参数θ 4.4 私密环境下的性能比较在私有环境中，图4-6展示了lpea-low、lpea-high、random-add和edge-remove的度序列和分布发布情况。我们首先对这四种方法应用θ={1,2,…,100}和?=3，并在图4中报告了实验结果。结果表明，随着θ的变化，度序列发布的MAE和MSE呈现出凸趋势。这种趋势是因为投影引起的lAE误差随着θ的增加而单调减少，而来自拉普拉斯噪声的lLAP误差随着θ的变化而增加。因此，这两种误差形成了一个优化权衡，决定了最优θ值。从图4的结果中我们可以看出，与其他三种算法相比，LPEA-LOW在8个数据集上始终实现了更低的MAE和MSE。这是因为LPEA-LOW从度数较小的相邻节点开始添加边，这在稀疏图中特别有效（例如Loc-Brightkite和Com-dblp）。图5展示了使用表3中最优θ的所有方法的度序列发布的MAE和MSE，其中?从1变化到3。结果表明，随着?的减小，MAE和MSE都有所下降。我们提出的解决方案LPEA-LOW在所有数据集上都取得了良好的准确性，并且优于所有其他差分隐私方法。例如，在Loc-Brightkite数据集中，当隐私预算相对较大时（例如?=3.0），其MAE和MSE始终保持在6.1和40.0以下。当?减小时，准确性会下降，但其MAE仍然小于11.0。其他方法的性能不如我们的方法，因为在添加边时，我们考虑了度数相对较小的相邻用户的意愿。图4. 在?=3.0时，不同数据集上算法的MAE和MSE变化情况。图5. 在不同数据集上，随着?变化，算法的mae和mse变化情况。图6. 在α=0.1、ε=3以及表3中的最优θ设置下，比较了LPEA-LOW与其他算法（LPEA-HIGH、RANDOM-ADD和EDGE-REMOVE）的度分布质量。ORIGIN-GRAPH线表示原始图的真实度分布。实验结果表明，EDGE-REMOVE的表现最差，其次是RANDOM-ADD和LPEA-HIGH。观察中间结果，我们注意到EDGE-REMOVE与ORIGIN-GRAPH相差甚远。我们提出的方法显著优于其他三种方法，尤其是在较大的数据集上，能够得到相当准确的度分布。5 相关工作已经广泛研究了将节点中心差分隐私（node-cdp）应用于度分布和度序列。我们认为使用node-cdp比edge-cdp更有意义，因为node-cdp提供了对图数据的个人隐私控制。[12]中的工作研究了在edge-cdp下发布度序列的问题，该方法直接使用拉普拉斯机制生成lap(2?)噪声，并进行一致性推断以提高噪声序列的准确性。随后的几项工作[19, 30]探讨了发布度序列或分布的方法。然而，这些方法在node-cdp下变得不可行，因为敏感性可能是无界的。研究了使用图投影来限制敏感性的技术，以便在node-cdp下发布度分布[1, 5, 20]。在[5]中引入的边添加过程，随机将与度数超过θ的节点相关联的边插入。相比之下，截断方法[20]消除了所有度数超过θ的节点。同时，边删除过程[1]按随机顺序遍历所有边，并移除与度数超过θ的节点相连的边。然而，现有的投影方法仅适用于node-cdp，不适用于node-ldp和edge-ldp。在局部环境中，现有工作几乎都使用edge-ldp来研究各种图统计量，如度分布[29]、子图计数[11, 13, 14, 15, 16, 17, 18, 23]和合成图生成[25, 27]。例如，[29]中的工作提出了一种结合wrr [26]机制的一轮方法lf-gdrr来重建图结构以回答统计查询。基于lf-gdrr，[16, 17]分别提出了local2rounds和arrtwons方法。前者通过引入下载策略减少了三角形计数误差，后者通过结合非对称随机响应（arr）和条件下载策略提高了前者的准确性并降低了通信成本。随后，ws [18]解决方案被提出用于回答三角形和4环计数查询。这种方法采用楔形洗牌技术来实现隐私放大，同时减少了与local2rounds和arrtwons相比的误差。与local2rounds相比，tcrr [11]方法依赖于wrr的不同后处理来回答三角形计数查询，可以获得结果的方差的上界和下界。与[11, 16, 17, 18]不同，privet [23]引入了一种联邦三角形计数估计器，通过边关系-ldp来保护隐私，专门为相关数据收集场景设计。同时，dbe [13]专注于使用edge-ldp进行二分图的蝴蝶计数，而oddcyclec [14]针对度数有界的图进行循环计数。与上述局部模型中的工作不同，一些研究专注于在edge-ldp下生成合成图。ldpgen [25]提出了一种新颖的多阶段合成去中心化社交图生成方法，而sgldp [27]在保持图属性（如度分布、社区结构和属性分布）的同时，仔细估计了在edge-ldp下的属性图数据的联合分布。尽管上述方法使用edge-ldp来降低对图统计量的敏感性，但它们在度序列发布方面存在以下限制：（1）edge-ldp提供的隐私保障比node-ldp弱；（2）这些方法中的每个用户都需要发送长度为n的邻接向量，导致高通信成本。为了解决这些限制，edge-remove [21, 22]使用node-ldp和加密技术来发布度序列和分布，该方法采用边删除过程来投影原始图中每个节点的度数。这项工作的一个关键贡献在于它能够同时提供更高的发布准确性和增强隐私保障。然而，从图2中我们可以看出，由于忽略了每个用户的意愿，edge-remove可能会导致不必要的边被删除。此外，加密辅助的参数选择过程要求每个用户在每次迭代中进行一轮局部投影，导致高通信成本。与现有工作相比，我们的方法cadr-ldp引入了一种带有加密技术的边添加过程，进一步提高了效用并满足了node-ldp的要求。6>