面向鏈接預測的本地差分隱私圖數據建模方法

韓啟龍 吳曉明

摘? 要：針對工業企業圖數據鏈接預測過程中，節點間的敏感數據面臨隱私泄露的問題，以本地差分隱私理論為基礎，從鏈接預測任務表現的角度分析了現有的圖數據建模方法在隱私保護上的缺點和不足。提出在個性化采樣技術的隨機響應機制，減少用戶端噪聲添加，同時結合兩輪數據收集的子圖劃分策略，保留原始圖數據中子圖聚集特征，最終實現了一種個性化采樣隨機響應本地差分隱私（Personalized Sampling Randomized Response Local Differential Privacy，PSRR-LDP）圖數據建模算法，理論證明PSRR-LDP算法滿足ε-邊本地差分隱私。仿真實驗結果表明，PSRR-LDP算法在保證隱私的同時具有更優的鏈接預測效果。

關鍵詞：隱私保護技術；鏈接預測；本地差分隱私；個性化采樣；圖數據收集

DOI：10.15938/j.jhust.2023.05.007

中圖分類號： TP391

文獻標志碼： A

文章編號： 1007-2683（2023）05-0051-10

Local Differential Privacy Graph Data Modeling Method for Link Prediction

HAN Qilong1，? WU Xiaoming2

（1.College of Computer Science and Technology， Harbin Engineering University， Harbin 150001， China;

2.Law School， Harbin University of Commerce， Harbin 150028， China）

Abstract：To solve the problem of node sensitive link privacy being exposed in the process of link prediction on industrial business graph data， according to the theory of local differential privacy， the shortcomings of the existing graph privacy protection technology are analyzed from the perspective of link prediction task performance. Based on the existing randomized response mechanism， it introduces the personalized sampling technology to reduce the noise addition on the user side. At the same time， combined with the subgraph partitioning strategy of two rounds of data collection， the subgraph cluster feature of the original graph is retained. Finally， a personalized sampling randomized response local differential privacy （PSRR-LDP） graph data perturbing algorithm was implemented， and the PSRR-LDP algorithm is theoretically proved to satisfy the ε-edge Local differential privacy. The simulation experiments show that the PSRR-LDP algorithm has better link prediction performance while ensuring privacy.

Keywords：privacy-preserving techniques; link prediction; local differential privacy; personalized sampling; graph data collection

收稿日期： 2022-05-17

基金項目： 國家重點研發計劃（2020YFB1710200）；國家自然科學基金（61872105）；黑龍江省哲學社會科學研究規劃項目（19FXE275）.

作者簡介： 吳曉明（1976—），女，副教授，碩士生導師.

通信作者：

韓啟龍（1974—），男，教授，博士研究生導師，E-mail：hanqilong@hrbeu.edu.cn.

0? 引? 言

隨著互聯網、大數據、人工智能等信息技術的快速發展，社交網絡、工業互聯網等應用已經廣泛深入到人們的生產生活中。圖數據作為數據管理與分析的重要手段，因其網絡結構特征及科學運算的模式，圖數據挖掘已經成為當今學術界與工業界研究的熱點問題之一。鏈接預測（link prediction，LP）是圖數據挖掘的重要部分，可在現有圖數據基礎上預測未來節點間的鏈接關系［1］，在社交網絡、推薦系統、工業互聯網等網絡服務中有著廣泛的應用 ［2-6］。早期的探索式LP算法基于目標節點對的局部特征判斷目標鏈接是否會在將來出現［7］。最近，文［8］提出目標節點對的局部封閉子圖包含足夠的用于鏈接預測的特征同時提出可以使用圖神經網絡的方式提取這樣的特征。

近年來隱私泄漏事件的頻繁發生，如Facebook隱私信息泄漏事件、澳大利亞電信公司Optus數據泄漏事件等，用戶如何在使用網絡服務的同時保證敏感信息不被泄漏已經獲得了廣泛關注［9-16］。傳統的隱私保護技術，如k-鄰算法［10］，k-度匿名［11］，差分隱私［12-14］等，多是基于中心化場景下開展研究。這種方法要求具有可信第三方服務提供商，一旦服務提供商不可信或發生隱私泄漏，則無法保障用戶的隱私信息，所以研究者們基于本地差分隱私（local differential privacy，LDP）提出了LDPGen［15］、RABV（randomized adjacency bit vector） ［16］和GraphLDP［17］等去中心化技術解決中心化隱私保護中存在的不足。本地差分隱私技術通過在用戶端進行數據擾動保護敏感信息，然后將擾動后的數據發送給數據收集者，即使數據收集者不可靠，仍可有效保護用戶的敏感數據。LDP已經被成功用于各種數據分析任務中保護隱私，比如頻率估計［18-20］，頻繁項集挖掘［21］以及地理位置隱私保護［22］。

當前的圖數據LDP隱私保護工作主要分為圖數據合成與圖中統計量無偏估計兩大分析任務。LDPGen算法采用滿足LDP的方法收集節點度信息來合成圖，在保留圖拓撲特征的同時保護隱私，但為了平衡整體性統計特征和邊粒度統計特征，算法損失了圖中一些重要的局部特征。GraphLDP使用安全多方計算賦予節點假名從而將節點間連接假名化同時結合LDP算法收集節點的度，數據收集者根據假名化的節點間連接和節點的度重構一個保護隱私的圖結構。以上的工作都是關于圖數據合成，而另一類重要的任務是圖中統計量的無偏估計。LF-GDPR（local framework for graph with differentially private release）［15］算法在滿足LDP條件下對圖中的統計量進行無偏估計以達到隱私保護效果。文［23］提出了滿足LDP條件下圖中的三角計數和k-星計數方法。節點是否存在邊的概率主要依賴于圖的局部特征與圖拓撲結構［8］，因此，圖局部特征的損失會極大地影響LP算法對節點間是否存在邊的判斷，同樣，在收集圖數據時不考慮圖的拓撲結構也將對是否存在邊的結果產生重要影響。

綜上，現有的圖LDP算法存在破壞圖拓撲結構、局部特征損失等問題。本文提出一種個性化采樣隨機響應的本地差分隱私保護鏈接預測算法，利用個性化采樣隨機響應機制，對用戶的每一條數據使用不同的采樣概率，減少用戶端噪聲添加，結合兩輪數據收集方式與圖劃分機制，保留原始圖中邊分布的特征，理論證明了算法滿足LDP隱私，通過對比實驗分析，驗證了本文算法在圖數據鏈接預測任務中有更高的準確性。

1? 圖本地差分隱私鏈接預測

1.1? 本地差分隱私

為了解決第三方服務器可能的隱私泄露，在LDP中，用戶對敏感數據使用滿足LDP機制的本地擾動，然后發送給服務器。在圖LDP中包括邊差分隱私、節點差分隱私，其中邊差分隱私對圖中任意一條邊的添加或刪除進行保護，節點差分隱私對任一節點的增刪及其相關邊進行保護。

設圖中節點的集合V={v1，…，vn}，其中n為節點數量。節點vi與其他節點間的關系表示為一個n維位向量vi={b1，…，bn}，其中bj=1，j∈{1，…，n}，當且僅當節點vi與vj有邊，否則，bj=0。節點位向量形成用戶鄰接矩陣M={v1，…，vn}。

定義1? 節點本地差分隱私［15］。隨機算法A滿足ε-節點本地差分隱私（ε-node LDP），如果對任意兩個相鄰的節點位向量v與v′，有Pr（A（v）=s）Pr（A（v′）=s）≤eε，其中，s∈range（A），稱A滿足ε-node LDP。

定義2? 邊本地差分隱私［15］。隨機算法A滿足ε-邊本地差分隱私（ε-edge LDP），如果對任意兩個相鄰的節點位向量v與v′，這兩個相鄰位向量中只有一位不同，有Pr（A（v）=s）Pr（A（v′）=s）≤eε，其中，s∈range（A），稱A滿足ε-edgeLDP。

定理1? 序列組合原理［15］。若有n個獨立的隨機算法Ai（1≤i≤n），都分別滿足εi-node（edge） LDP，則算法Ai的組合仍然滿足（∑εi）-node（edge）LDP。

除了序列組合原理，LDP也內在的擁有后處理特性［24］。節點LDP相鄰數據庫定義在位向量的任意個比特位上，邊LDP的相鄰數據庫定義在節點位向量的某一位上。通常情況下，由于節點LDP也實現了邊LDP，節點LDP相比邊LDP具有更強的保護程度。在具體的實際應用場景中，選擇合適的隱私保護強度更有意義。如在社區發現與三角計數應用中，采用邊LDP在保證圖中邊的不可區分性的同時，又具有較好的數據可用性。因此，在圖數據挖掘中，多采用邊LDP機制進行對敏感數據的保護［15］。

1.2? 滿足LDP的圖鏈接預測

設有簡單無向圖G=（V，E），其中V為節點集合，E為邊集合，圖中不包括重邊和自環。M為圖G的鄰接矩陣，如果（i，j）∈E，則Mi，j=1，否則Mi，j=0。U表示節點間所有|V|·（|V|－1）2個可能的鏈結，其中|V|為集合V中的節點數量，則U-E表示所有當前不存在的邊。假設一些邊會在將來出現，鏈接預測的任務即是發現這些可能出現的邊。非隱私保護的鏈接預測算法能給出目標鏈接在將來可能出現的概率。

如果有一個非隱私保護的鏈接預測算法B，為了滿足邊LDP，使用一個滿足邊LDP的擾動算法A在用戶本地擾動數據，然后在收集端聚集所有用戶擾動后的數據獲得隱私保護的圖G～=（V，E～），之后使用非隱私的鏈接預測算法B去計算目標鏈接的存在概率。根據LDP的后處理性質［23］，此時算法B的輸出滿足LDP，因此能保護個人隱私。

2? PSRR-LDP圖生成算法

2.1? 個性化采樣隨機響應算法

隨機化鄰居列表算法是一個直接使用隨機響應機制（rondimized response mechanism， RR）滿足LDP的圖隱私化算法［15］。給定一個節點的位向量vi={b1，…，bn}，以及隱私預算ε，根據式（1）獲得擾動后的位向量i={1，…，n}。

j=bjw.p.eε1+eε

1－bjw.p.11+eε（1）

如果原始圖中邊密度為η，則收集的圖中真實邊比例為ηpηp+（1－η）（1－p），其中p=eε1+eε。假設節點vi的鄰居節點數為mi（1≤mi≤n-1），收集到的圖中真實邊比例在期望上應為

∑ni=1mip∑ni=1mip+∑ni=1（n－mi－1）（1－p）

即攻擊者在收集到的邊中推測出真實邊的概率，由于在社交網絡等實際應用場景中，圖通常具有稀疏性，攻擊者推測成功的概率較低。但直接采用RR方法對圖進行重構將導致生成圖中邊密度的快速膨脹，重構圖中將會包含過多的假邊，從而降低圖的可用性。如，在Facebook數據集中，原始邊密度為，η=0.0108，若隱私預算ε=1，采用RR算法狀態保留概率p=e11+e1≈0.7310，擾動后的邊密度為≈0.2739，是原始邊密度的25.36倍。此外，在無向圖上采用經典的RR機制雖然可實現ε-edge LDP，但因為用戶會對同一條邊進行兩次獨立擾動，對收集者只能實現2ε-edge LDP，同時，每個用戶獨立隨機化發送所有位向量給第三方收集者，也將導致較高的計算與通信開銷。

針對這些不足，本文提出個性化采樣隨機響應方法解決邊密度膨脹問題，并根據矩陣對稱性降低了計算與通信開銷。

假設用戶i表示為圖節點vi，同時與其他用戶間的連接關系表示為位向量vi={b1，…，bn}。假設r∈（0，1）為擾動后圖中真實邊的比例期望，ε為隨機響應的隱私預算，m為鄰居節點數量。為保證對數據收集者也滿足ε-edge LDP，根據鄰接矩陣的對稱性，算法只需處理上三角矩陣。鄰接矩陣每行對應一個節點的位向量，僅處理位向量中位置在［（i+1），（i+1+t mod n）］區間的元素，對前1≤i≤n2個節點，其中t=n2，否則t=n－12。將位向量vi中采樣的子集表示為Φi，則位向量中每個位bj的采樣概率πj如式（2）所示：

πj=1如果bj=1

min（meε（1－r）r（t－m），1）如果bj=0（2）

獲得子集Φi后，根據式（1）對子集中的位進行擾動，然后將擾動后比特值對應為1的索引發送給收集者。數據收集者根據索引值將鄰接矩陣對應位置填充為1，然后復制對稱位置的值，并對缺失位置用0進行填充，最終獲得完整的鄰接矩陣。

算法1：個性化采樣隨機響應算法

輸入：原始用戶位向量集合{v1，…，vn}

隱私預算ε

擾動后真實邊比例期望r

輸出：

擾動后的鄰接矩陣M～

//用戶端

1）用戶i計算傳輸范圍大小t，如果i≤n2則t=n2， 否則t=n－12;

2）每個用戶i在位向量vi上統計在傳輸范圍［（i+1），（i+1+t mod n）］內的鄰居節點數量m;

3）遍歷用戶位向量vi中在傳輸范圍內的每個比特bj， 使用式（2）計算每個比特的采樣概率πj;

4）對需要處理的比特bj根據對應的采樣概率πj進行伯努利采樣，將采樣獲得的比特值bj和對應的索引j記錄進集合Φi中;

5）遍歷集合Φi中的每個比特值bj進行如公式（1）的隨機響應得到擾動后的比特值j

6）用戶將對應擾動后比特值為1的索引發送給數據收集者;

//收集端

7）初始化一個n×n的全零矩陣M～;

8）每個用戶i的位向量vi對應矩陣中M～的一行，收集端根據每個用戶發送的索引集合將矩陣M～中對應位置的元素賦值為1;

9）以矩陣M～的主對角線為對稱軸復制對稱位置的元素;

10）返回處理后的矩陣M～。

在算法中鄰接矩陣的每一個對稱位置的元素只被擾動一次，因此對收集者也滿足ε-edge LDP。鄰接矩陣中所有被處理的位構成了一個上三角矩陣，其中真實邊的比例期望為r，將上三角矩陣元素復制到下三角矩陣中，則在圖中全部的真實邊比例期望仍為r。

2.2? 基于子圖劃分的圖生成算法

在實際應用中多數圖是低秩的，即圖中有明顯的多個子圖聚類的特點。同時社區結構有助于鏈接預測［25］。對子圖中某個特定的節點，與其他子圖所鏈接的邊數量通常是不同的，因此在算法中考慮到子圖間鏈接特點設置不同的采樣概率，可以在圖重構中保留原始圖的子圖聚類特征，從而增強后續鏈接預測算法的正確性。

提出了基于子圖劃分的個性化隨機響應圖生成算法。給定總的隱私預算ε和隱私分配系數α，將隱私預算分為兩個部分ε1和ε2，其中ε1=αε，ε2=（1-α）ε。在第一輪數據收集中，因為數據收集者沒有關于原始圖的信息，僅發送ε1給每個用戶，用戶根據算法1處理本地數據然后發送給數據收集者，收集者根據收到的數據形成鄰接矩陣M～1，然后收集者使用子圖發現算法，本文使用Louvain子圖發現算法［26］，獲得初步的子圖劃分C={c1，c2，…，ck}，其中k為子圖的數量，且每個節點只屬于一個子圖。在第二輪的交互中，收集者發送子圖劃分C和隱私預算ε2給每一個用戶，用戶i根據收到的信息將位向量中的位劃分到相應的子圖，然后計算每個節點在相應子圖的鄰居節點數量Δi={δi1，…，δik}以及子圖的大小Si={si1，…，sik}。假設位bj屬于子圖cj，則位bj被采樣的概率可根據式（3）計算。

πij=1如果 bj=1

min（δicjeε2（1－r）r（sicj－δicj），1）如果 bj=0（3）

對于同一個子圖的位設置相同的采樣概率，之后采樣獲得對應的子集Φi，之后使用式（1）進行擾動，并將擾動后的結果發送給數據收集者，收集者形成鄰接矩陣M～2。

算法2：基于子圖劃分的圖生成算法

輸入：原始用戶位向量集合{v1，…，vn}

隱私預算ε

擾動后真實邊比例期望r

輸出：擾動后的圖鄰接矩陣M～2

//第一輪數據收集

1）計算ε1=αε，ε2=（1-α））ε

2）使用隱私預算為ε1的算法1獲得M～1然后收集者使用社區發現算法在鄰接矩陣M～1上獲得子圖劃分C={c1，c2，…，ck}

//第二輪數據收集

//用戶端

3）用戶i計算傳輸范圍大小t，如果i≤n2則t=n2， 否則t=n－12;

4）遍歷用戶位向量vi在傳輸范圍［（i+1），（i+1+t mod n）］內的每個比特bj，然后將比特值bj和對應的索引j記錄到集合T中;

5）遍歷子圖劃分C中的每個子圖c，計算每個子圖在傳輸范圍內的節點數量sic=|c∩T|然后記錄到集合Si={si1，…，sik}以及計算c∩T中比特值為1的元素數量保存到Δi={δi1，…，δik};

6）遍歷集合T根據等式（3）計算每個比特bj∈T被采樣的概率，然后根據概率進行伯努利采樣如果被采樣中則記錄下被采樣元素的比特值bj和對應的索引j到集合Φi中;

7）使用隱私預算為ε2的隨機響應算法擾動集合Φi中的每個比特值，然后將擾動后比特值為1的元素對應的索引發送給數據收集者；

//數據收集端

8）和算法1類似，首先初始化一個n×n的全零矩陣M～2，然后根據每個用戶發送的索引集合填充矩陣M～2對應位置的元素為1，之后沿主對角線復制鄰接矩陣M～2對稱位置的元素，最后返回M～2。

2.3? 算法隱私分析

設有節點位向量v={b1，…，bn}與隱私預算ε。v′={b′1，…，b′n}與v={b1，…，bn}是鄰居數據庫，它們只相差一條邊τ，不失一般性，假設b′n≠bn使用符號PRR表示先采用個性化采樣獲得一個子集，然后在采樣后的子集上使用隨機響應機制這個過程。符號Ψ表示采樣過程，RR表示隨機響應過程。根據邊LDP定義和文［15］有如下定理。

定理1［15］? 給定任意兩個鄰居節點位向量v與v′，它們只差一條邊，在v上使用隱私預算ε的隨機響應機制，則如下兩個不等式成立：

Pr［RR（v）=o］Pr［RR（v′）=o］≤eε， Pr［RR（v′）=o］PR［RR（v）=o］≤eε（4）

其中o∈range（RR）表示隨機響應機制任何可能的輸出結果。

文［15］中證明了當在v上使用隱私預算為ε的隨機響應機制擾動后的結果滿足ε-edge LDP。

定理2? 給定任意的用戶位向量v，其每一個位都具有特定的采樣概率0≤π≤1，依據概率π在v中進行一次采樣獲得的子集Φ，在Φ上以隱私預算ε進行隨機響應的結果滿足ε-edge LDP。

證明：根據邊本地差分隱私的定義，為了證明PRR機制滿足ε-edge LDP，需要證明Pr［PRR（v）=s］≤eεPr［PRR（v′）=s］。其中s∈range（PRR）表示PRR機制任何可能的輸出。而Pr［PRR（v）=s］可以重寫為如下形式：

Pr［PRR（v）=s］=Pr［Ψ（v）=Φ］Pr［RR（Φ）=s］

其中：Φ表示從v中采樣出的比特子集；Φ′表示從v′中采樣出的比特子集。v與v′的采樣結果可以分為包括或不包括邊τ這兩種情況v－τ={b1，…，bn－1}，表示從v或者v′中去除邊τ之后的數據集。Φ-τ和Φ′-τ分別表示從v－τ和v′－τ中的采樣結果。因為v和v′只有邊τ不同，所以v－τ=v′－τ因此存在采樣結果Φ-τ=Φ′-τ。使用πτ表示邊τ在采樣過程中被采樣中的概率，則有如下等式成立：

Pr［PRR（v）=s］=

∑Φ－τv－τπτPr［Ψ（v－τ）=Φ－τ］Pr［RR（Φ）=s］+

∑Φ－τv－τ（1－πτ）Pr［Ψ（v－τ）=Φ－τ］Pr［RR（Φ－τ）=s］（5）

類似的有：

Pr［PRR（v′）=s］=

∑Φ－τv－τπτPr［Ψ（v－τ）=Φ－τ］Pr［RR（Φ′）=s］+

∑Φ－τv－τ（1－πτ）Pr［Ψ（v－τ）=Φ－τ］Pr［RR（Φ－τ）=s］

當假設邊τ被采樣中時，則相鄰數據庫v和v′上的采樣結果Φ和Φ′仍然是相鄰數據集，則由定理1可得如下不等式：

Pr［RR（Φ）=s］≤eεPr［RR（Φ′）=s］

當ε>0時，eε>1，因此將上述不等式帶入等式（5）得到如下式子：

Pr［PRR（v）=s］≤

∑Φ－τv－τπτPr［Ψ（v－τ）=Φ－τ］eεPr［RR（Φ′）=s］+

∑Φ－τv－τ（1－πτ）Pr［Ψ（v－τ）=Φ－τ］Pr［RR（Φ－τ）=s］≤

∑Φ－τv－τπτPr［Ψ（v－τ）=Φ－τ］eεPr［RR（Φ′）=s］+

∑Φ－τv－τ（1－πτ）eεPr［Ψ（v－τ）=Φ－τ］Pr［RR（Φ－τ）=s］=

eεPr［Ψ（v′）=Φ′］Pr［RR（Φ′）=s］=

eεPr［PRR（v′）=s］

根據對稱性原則，有：

Pr［PRR（v′）=s］≤eεPr［PRR（v）=s］

成立。因此，個性化采樣隨機響應機制滿足ε-edge LDP。證畢。

定理3? 基于子圖劃分的個性化采樣隨機響應機制的圖生成算法滿足ε-edge LDP。

證明：根據算法2的流程，總隱私預算ε被劃分為兩個部分ε1和ε2，分別用于第一輪和第二輪的個性化采樣隨機響應，根據邊LDP的序列組合原理結合定理2可得算法2滿足ε-edge LDP。證畢。

2.4? 算法復雜度分析

在用戶端，算法1多次遍歷了用戶位向量中的每個元素，因此算法1在用戶端的時間復雜度是O（n），其中n是參與的用戶數量。算法2在用戶和收集者第一次交互時使用了算法1，之后用戶和收集者又進行了第二輪交互，在第二輪交互中用戶端對用戶位向量進行了多次遍歷，綜上算法2在用戶端的時間復雜度是O（n）+O（n）=O（n）。算法1在收集端需要收集者遍歷每個用戶提交的索引集合因此算法1在收集端的時間復雜度是O（n2）。算法2在收集端需要在第一輪交互中調用算法1以及在第一輪交互中收集端使用Louvain社區發現算法進行子圖劃分而運行一次Louvain算法的時間復雜度是O（nlog（n））［27］，在第二輪交互中數據收集端同樣需要O（n2）的時間復雜度，因此綜上算法2在數據收集端需要O（nlog（n）+n2）的時間復雜度。在通信復雜性方面，我們將一個用戶和收集者之間的通信寬度作為通信復雜度。算法1中收集者首先發送參數到用戶此時通信復雜度是O（1）。然后用戶只需要發送一次部分位向量的索引集合，所以它的通信復雜度是O（n）。因此算法1的通信復雜度是O（n）。算法2第一次交互中使用算法1，第二次交互中數據收集端需要給用戶發送子圖劃分此時通信復雜度是O（n），之后用戶端需要發送位向量的索引集合則復雜度是O（n），綜上算法2的通信復雜度是O（n）。文獻中的方法RABV與LDPGen算法在用戶端的時間復雜度都較小為O（n），在收集端RABV的時間復雜度為O（n2），文［14］中表明LDPGen的時間復雜度是O（n2+n（k0+k1）），其中k0是LDPGen算法中初始賦予的節點聚類個數，k1是LDPGen算法計算出的調整后的節點聚類個數。此外RABV和LDPGen算法在用戶和收集者之間的通信復雜度為O（n）。

綜上，之前的算法與PSRR-LDP圖生成算法時間復雜度同階，后續的實驗結果同樣表明本文算法的時間復雜度與之前的算法相似，但是鏈接預測準確性有明顯的提升。

3? 對比實驗與結果分析

為了驗證PSRR-LDP算法的有效性，在以下4個領域內常用的公開數據集上進行實驗驗證。

USAir［28］：美國航空線路的網絡，數據集中包括332個節點與2126條邊。

NS［29］：網絡科學領域研究者的協作網絡數據集，包括1589個節點與2742條邊。

PB［30］：美國政治博客的網絡數據集，包括1222個節點與16714條邊。

Facebook［31］：美國Facebook社交網絡的快照數據集，包括4039個節點與88234條邊。

對比算法選取了無隱私保護機制的算法A，以及目前參考文獻中性能最優的隱私保護機制：RABV與LDPGen，為了證明子圖劃分的作用，還與個性化采樣隨機響應算法（personalized sampling randomized response algorithm， PRR）進行了性能比較。為評價算法所生成的圖數據在鏈接預測任務上的效果，選擇了CN［32］、Katz［32］、Node2vec［33］和SEAL［8］4個經典的鏈接預測算法進行驗證。與參考文獻中相同，設置Katz方法的影響系數為0.001，Node2vec方法的嵌入向量維度為80，其余的超參數設置與相應參考文獻中的默認值設置一致，對每個實驗進行10次圖收集，最終以平均結果作為衡量依據。一般而言，很難判斷哪些邊會在將來出現，實驗時為了測試鏈接預測算法的效果，隨機將當前的邊集E劃分為訓練集ET與驗證集EP兩部分。原始圖中10%的邊被隨機選擇作為正的驗證集。遵照鏈接預測數據處理中的常見操作，將相同數量的不存在的邊作為負的驗證集。將他們合在一起構成了總驗證集EP。剩余的邊構成了訓練集ET。通過訓練集ET，構建圖GT=（V，ET）用于算法訓練，對圖GT采用ε-edgeLDP機制進行重構，得到滿足邊LDP的圖G～T=（V，E～T），以此圖為基礎訓練圖鏈接預測算法。實驗使用Python語言在具有英特爾至強奔騰8260 CPU和500GB內存的服務器上面編寫實驗代碼。

3.1? 評價指標

本文采用AUC（area under the curve， AUC）指標［32］評價算法的鏈接預測效果。在驗證集上運行鏈接預測算法得出每條邊的分數，然后按如下方式計算出AUC值。從驗證集Ep中取出缺失邊與不存在邊進行比較。假設有z個獨立的比較結果，在結果中缺失邊的分數大于不存在邊的分數為x次，分數相等的次數為y，AUC值可以由以下公式得出：

AUC=x+0.5yz

若所有結果都來自一個獨立且相同的分布，則AUC的值會接近0.5，AUC值越大，算法相比于隨機選擇的效果越好。

3.2? 結果分析

在設置相同的隱私預算ε=0.1，相同的真實邊占比的期望r=0.5，隱私預算分配系數設置為α=0.1時，實驗結果如表1所示。為了衡量在鏈接預測任務中的效果，分別選取了CN，Katz，Node2vec和SEAL鏈接預測算法進行對比實驗，表1中A為未進行隱私保護的圖數據與不同的鏈接預測算法分別在4個數據集上的AUC指標值，實驗結果表明文章所提出PSRR-LDP算法的性能在所有的數據集和所有的鏈接預測算法中效果都是最優的。因為在用戶端有效地減少了噪聲邊的添加，同時保留了細粒度的圖結構特征，算法PSRR-LDP性能顯著優于RABV和LDPGen算法，在所有數據集上，性能至少提高了30%以上。

為了考查隱私預算ε發生變化時，所提出算法的效果，選取了Katz和SEAL鏈接預測算法分別在不同數據集上進行了實驗驗證，USAir數據集結果如圖1所示，NS數據集結果如圖2所示，PB 數據集結果如圖3所示，Facebook數據集結果如圖4 所示。與文獻中隱私預算設置相同，實驗中ε從0.1至7區間進行變化，PSRR-LDP算法幾乎在所有隱私預算下都優于對比方法。隨著隱私預算的增加，PSRR-LDP、PRR和RABV算法的AUC性能值顯著提升，在ε=6時會接近無隱私機制的AUC值并保持穩定。在NS數據集上，當隱私預算較小時PSRR-LDP與PRR算法有相似的表現，當隱私預算較大時，PSRR-LDP算法會明顯優于PRR算法，這是因為在NS數據集上具有明顯的社區結構，利用社區劃分算法可以獲得模塊度很高的社區劃分結果，但在社區數量較多，多數社區中的節點數量較少，因此不滿足PSRR-LDP算法的低秩需要。當隱私預算較小時第一輪數據收集后的社區劃分結果會引起大量小型社區的合并，從而導致無法有效獲取真實的社區結構，因此在效果上與PRR算法相似，當隱私預算較大時，算法第一輪數據收集可以獲得更好的接近真實社區結構的社區劃分結果，與PRR相比更好地保留了圖結構，所以具有更優的效果。

最后，比較不同的鄰接矩陣合成方法在收集端的運行時間，結果如表2所示。從結果可以看出運行時間從短到長分別是PRR，RABV，PSRR-LDP以及LDPGen。

3? 結? 語

針對圖數據中節點鏈接預測導致用戶敏感信息隱私泄露問題，提出了個性化采樣隨機響應機制捕獲用戶間的信息，并應用于圖數據的鏈接預測分析，同時在去中心化場景下實現了本地差分隱私保護，保護用戶隱私的同時提高了數據的可用性。在USAir、NS、PB、Facebook 4個不同真實數據集上的實驗結果表明本文算法的有效性和優越性。在后續的工作中，將在確保生成圖與原始圖之間具有更相似的社區劃分，以及減少通訊開銷等方面進行深入研究，同時擴展個性化采樣技術可解決其它特殊的圖類型與其他本地差分隱私場景，如屬性圖，均值估計和多維數據收集等。

參 考 文 獻：

［1］? LIBEN-NOWELL D， KLEINBERG J. The Link Prediction Problem for Social Networks［J］. Journal of theAmerican Society for Information Science and Technology， 2007， 58（7）：1019.

［2］? DE A， CHAKRABARTI S. Differentially Private Link Prediction with Protected Connections［C］// National Conference on Artificial Intelligence. Proceedings of the AAAI Conference on Artificial Intelligence. California： AAAI， 2021：63.

［3］? 伍杰華， 程智鋒. 聯合社區和影響節點的通用可擴展的鏈接預測［J］. 計算機工程與設計， 2022（2）：43.

WU Jiehua， CHENG Zhifeng. Integrating Community and Influential Node for General and Scalable Link Prediction［J］. Computer Engineering and Design， 2022（2）：43.

［4］? 李貞，吳勇，耿海軍.基于重引力搜索鏈接預測和評分傳播的大數據推薦系統［J］.計算機應用與軟件，2020，37（2）：39.

LI Zhen， WU Yong， GENG Haijun. Big Data Recommender System Based on Gravitational Search for Link Prediction and Ratings Propagation［J］. Computer Applications and Software，20，37（2）：39.

［5］? 唐晨，趙杰煜，葉緒倫，等.基于對抗圖卷積網絡的鏈接預測模型［J］.模式識別與人工智能，2021，34（2）：95.

TANG Chen， ZHAO Jieyu， YE Xulun， et al. Link Prediction Model Based on Adversarial Graph Convolutional Network ［J］. Pattern Recognition and Artificial Intelligence， 201，34（2）：95.

［6］? 趙曉娟，賈焰，李愛平，等.基于層級注意力機制的鏈接預測模型研究［J］.通信學報，2021，42（3）：36.

ZHAO Xiaojuan， JIA Yan， LI Aiping， et al. Research on Link Prediction Model Based on Hierarchical Attention Mechanism ［J］. Journal of Communications，2021，42（3）：36.

［7］? ZHOU Tao， LU Linyuan， ZHANG Yicheng. Predicting Missing Links via Local Information［J］. The European Physical Journal， 2009， 71， 623.

［8］? ZHANG Muhan， CHEN Yixin. Link Prediction Based on Graph Neural Networks.［C］//Advances in Neural Information Processing Systems， 2018：31.

［9］? 李志鵬，孫名松，宋增林. 移動智能終端的位置隱私保護技術［J］.哈爾濱理工大學學報，2018，23（2）：58.

LI Zhipeng，SUN Mingsong，SONG Zenglin. The Location Privacy Protection Technology of Mobile Intelligent Terminal［J］.Journal of Harbin University of Science and Technology，2018，23（2）：58.

［10］ZHOU Bin， PEI Jian. Preserving Privacy in Social Networks Against Neighborhood Attacks［C］// International Conference on Data Engineering. 2008 IEEE 24th International Conference on Data Engineering， IEEE Press， 2008：506.

［11］LIU Kun， TERZI E. Towards Identity Anonymization on Graphs［C］// Acm Sigmod International Conference on Management of Data. Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. ACM， 2008：93.

［12］XU Shengzhi， SU Sen， XIONG Li， et.al. Differentially Private Frequent Subgraph Mining［C］//International Conference on Data Engineering. 2016 IEEE 32nd International Conference on Data Engineering （ICDE）.IEEE Press， 2016：229.

［13］XIAO Qian， CHEN Rui， TAN K. Differentially Private Network Data Release via Structural Inference［C］// ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Proceedings of The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM， 2014：911.

［14］ZHANG Sen， NI Weiwei， FU Nan. Differentially Private Graph Publishing with Degree Distribution Preservation［J］. Computers & Security， 2021， 106（6）：102285.

［15］QIN Zhan， YU Ting， YANG Yin， et al. Generating Synthetic Decentralized Social Graphs with Local Differential Privacy［C］// Acm Sigsac Conference on Computer & Communications Security. Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. ACM， 2017：425.

［16］YE Qingqing， HU Haibo， MAN H A， et al. LF-GDPR： A Framework for Estimating Graph Metrics with Local Differential Privacy［J］. IEEE Transactions on Knowledge and Data Engineering， 2020， 34（10）：4905.

［17］張佳程，彭佳，王雷. 大數據環境下的本地差分隱私圖信息收集方法 ［J］. 信息網絡安全，2020，20（6）：44.

ZHANG Jiacheng， PENG Jia， WANG Lei. A Graph Information Collection Method Based on Local Differential Privacy in Big Data Environment［J］. Netinfo Security， 2020， 20（6）： 44.

［18］賀星宇，朱友文，張躍.基于OLH的效用優化本地差分隱私機制［J］.密碼學報，2022，9（5）：820.

HE Xingyu， ZHU Youwen， ZHANG Yue. Utility-Optimized Local Differential Privacy Mechanism Based on OLH［J］. Journal of Cryptologic Research，2022，9（5）：820.

［19］曹依然，朱友文，賀星宇，等.效用優化的本地差分隱私集合數據頻率估計機制［J］.計算機研究與發展，2022，59（10）：2261.

CAO Yiran， ZHU Youwen， HE Xingyu， et al. Utility-Optimized Local Differential Privacy Set-Value Data Frequency Estimation Mechanism［J］. Journal of Computer Research and Development，202，59（10）：2261.

［20］WANG Tianhao， JEREMIAH B， LI Ninghui. Locally Differentially Private Protocols for Frequency Estimation［C］//USENIX Security Symposium. 26th USENIX Security Symposium （USENIX Security 17）， USENIX， 2017：729.

［21］歐陽佳，印鑒，肖政宏，等.面向頻繁項集挖掘的本地差分隱私事務數據收集方法［J］.軟件學報，2021，32（11）：3541.

OUYANG Jia， YIN Jian， XIAO Zhenghong， et al. Transaction Data Collection for Itemset Mining Under Local Differential Privacy ［J］. Journal of Software，2021，32（11）：3541.

［22］馮立剛，朱友文.保護位置隱私的效用優化本地差分隱私機制［J］.計算機與現代化，2022，325（9）：99.

FENG Ligang， ZHU Youwen. Utility-Optimized Local Differential Privacy Mechanism for Protecting Location Privacy［J］. JISUANJI YU XIANDAIHUA，2022，325（9）：99.

［23］IMOLA J， MURAKAMI T， CHAUDHURI K. Locally Differentially Private Analysis of Graph Statistics［C］// USENIX Security Symposium， USENIX， 2021：983.

［24］DWORK C， ROTH A. The Algorithmic Foundations of Differential Privacy［M］. Foundations and Trends in Theoretical Computer Science，2014： 211.

［25］SHAO Junming， ZHANG Zhong， YU Zhongjing， et al. Community Detection and Link Prediction via Cluster-driven Low-rank Matrix Completion［C］//IJCAI. Proceedings of The 28th International Joint Conference on Artificial Intelligence. IJCAI， 2019：3382.

［26］BLONDEL V， GUILLAUME J， LAMBIOTTE R， et.al. Fast Unfolding of Communities in Large Networks［J］. Journal of Statistical Mechanics： Theory and Experiment， 2008， 200（10）：10008.

［27］LESKOVEC J. Community Structure in Networks［EB/OL］.［2023-02-15］.http：//snap.stanford.edu/class/cs224w-2019/slides/04-communities.pdf

［28］VLADIMIR B， ANDREJ M. Pajek datasets［EB/OL］.［2023-2-15］. http：//vlado.fmf.uni-lj.si/pub/networks/data/.

［29］NEWMAN M. Finding Community Structure in Networks Using the Eigenvectors of Matrices［J］. Physical Review， 2006， 74（3）：036104.

［30］ACKLAND R. Mapping The us Political Blogosphere： Are Conservative Bloggers More Prominent［C］//BlogTalk Downunder. Blog Talk Downunder 2005 Conference， 2005.

［31］LESKOVEC J， MCAULEY J. Learning to Discover Social Circles in Ego Networks［J］. Advances in Neural Information Processing Systems， 2012， 25.

［32］LU Linyuan， ZHOU Tao. Link Prediction in Complex Networks： A Survey［J］. Physica A： Statistical Mechanics and Its Applications， 2011， 390（6）：1150.

［33］GROVER A， LESKOVEC J. Node2vec： Scalable Feature Learning for Networks［C］//ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM， 2016：855.

（編輯：溫澤宇）