社交網絡鏈路預測的個性化隱私保護方法

孟緒穎 張琦佳 張瀚文 張玉軍 趙慶林

1(中國科學院計算技術研究所 北京 100190)2(中國科學院大學 北京 100049)3(澳門科技大學 澳門 519020)

鏈路預測(link prediction)是一種預測節點間關系的重要技術，在社交關系預測[1]、商品推薦[2]等領域得到了學術界和工業界的廣泛關注.然而，鏈路預測過程需要用戶社交關系、用戶屬性等信息，這些信息涉及用戶隱私，比如通過用戶關注的對象可以分析出用戶的宗教信仰等敏感信息.用戶為了避免隱私泄露，可能不愿意提供這些信息，這將帶來鏈路預測效果的下降，進一步傷害用戶體驗.

已有研究提出了在鏈路預測的過程中為用戶提供隱私保護的方法，但目前還存在較多的不足：1)大多數的隱私保護完全依賴于服務商[3].2)有些研究考慮了不可信的服務商，卻忽視了不可信的朋友[4].3)為了解決不可信服務商和不可信朋友的問題，部分研究利用加密技術來保證不可信的服務商和朋友不能獲取單個用戶的個人信息[5].但是，除了加密解密過程帶來的計算開銷的增加，攻擊者仍然可以分析收到的準確計算結果來推斷出用戶隱私[6].4)社交網絡中，用戶常常會公開大量非隱私信息，這些信息被攻擊者用來反推出用戶的隱私信息(即重構攻擊[7])，而已有研究都還無法抵御此類攻擊.

為了解決現有隱私保護機制的問題和不足，本文設計了一種社交網絡鏈路預測的個性化隱私保護方法，避免不可信的服務商和不可信的朋友對用戶敏感鏈路的推測，并在維持鏈路預測準確性的前提下提升了隱私保護效果.本文主要的貢獻包括3個方面：

1) 提出了一種半集中式的框架.由用戶和服務商共同合作完成整個鏈路預測過程.

2) 提出了一種個性化隱私保護的方法.為了避免不可信服務商和不可信朋友的攻擊，將噪聲干擾分解為每個用戶可獨立處理的分量.同時，為敏感信息和非敏感信息添加不同強度的噪聲干擾，有效抵御重構攻擊的同時保證鏈路預測的準確度.

3) 從理論上證明我們的個性化的分布式隱私保護機制滿足ε-差分隱私，并在真實數據集上驗證了其有效性.實驗結果表明本文提出的機制實現了隱私保護和鏈路預測準確性之間的有效平衡.

1 相關工作

本節主要介紹了2類典型的鏈路預測算法，以及現有的面向鏈路預測的隱私保護算法.

1.1 鏈路預測算法

鏈路預測作為數據挖掘方向的經典問題，在學術界和工業界都受到了廣泛關注和重視[1-2].目前鏈路預測方法主要分為2類：1)基于pointwise的鏈路預測方法[8].該類方法將訓練集中的每對節點作為一個訓練數據，將節點間是否建立鏈路作為分類問題來解決.2)基于pairwise的鏈路預測方法[1].該類方法的訓練數據是2個節點對，通過對這2個節點對的偏序關系來學習一個鏈路預測模型，使得學習后得到的偏序關系和真實節點間的偏序關系一致.相對于pointwise的方法，基于pairwise的鏈路預測考慮了節點對之間的相對關系，因而在實際排序中能取得更高的準確性，目前基于pairwise的鏈路預測方法得到了廣泛關注[1,9].

1.2 社交網絡中鏈路預測的隱私保護算法

現有的隱私保護研究都是針對基于pointwise的鏈路預測的隱私保護方法，包括基于非加密和基于加密2類.1)基于非加密的隱私保護方法主要是由服務商來保護用戶的隱私，服務商利用k-匿名[10]等以組為單位進行鏈路預測，從而使得攻擊者無法通過鏈路預測結果推測目標用戶的敏感鏈路信息.然而，完全依靠服務商存在極大的安全隱患.2)基于加密的隱私保護方法能一定程度上解決不可信服務商的問題，通過設計加密算法對用戶的特征信息進行加密，使得服務商無法獲知用戶的具體隱私信息[5].但這類方法計算開銷較大，而且服務商利用獲取的最終真實計算值仍然可以推斷出用戶的隱私信息(即推斷攻擊[6]).

由于目前基于pointwise的鏈路預測的隱私保護機制不能直接應用于基于pointwise的鏈路預測方法，因此結合現有隱私保護機制的問題和不足，以及用戶個性化的需求，針對基于pairwise的鏈路預測方法，還需要提出新的鏈路預測隱私保護方法.

2 理論基礎

2.1 ε-差分隱私

差分隱私是一種常用的隱私保護方法，具有堅實的理論基礎.通過在原始數據集中加入噪聲干擾，確保數據集中單個數據的變化不會對最終輸出結果產生顯著影響，能較好地抵御推斷攻擊[11].

定義1.ε-差分隱私[11].設有隨機算法M，Range(M)為所有可能的輸出結果構成的集合，對于任意2個最多只有1個元素不同的數據集D1和D2以及S?Range(M)，如果算法M滿足

P[M(D1)∈S]≤eε×P[M(D2)∈S]，

則稱算法M滿足ε-差分隱私要求，概率P表示隱私泄露的風險，隱私預算ε用于衡量隱私保護強度.

定理1.Laplace機制[11].對于任意一個函數f:D→RK，若算法M的輸出結果滿足等式M(D)=f(D)+[Lap1(GS(D)ε),Lap2(GS(D)ε),…,LapK(GS(D)ε)]，則算法M滿足ε-差分隱私.其中Lapi(GS(D)ε),(1≤i≤K)是相互獨立的Laplace隨機數，且對于任意2個最多只有1個元素不同的數據集D1和

為了利用Laplace機制實現差分隱私，我們結合Laplace分布的性質，將其分解為服從高斯分布和指數分布的2個隨機數的計算值.

2.2 推斷攻擊與重構攻擊

推斷攻擊常常用于推測數據集中是否包含目標用戶的某條信息[6]，而差分隱私可以通過噪聲干擾來降低對目標用戶的單條信息對最終結果的影響，因而被廣泛應用于抵御推斷攻擊[5,11].

重構攻擊則利用公開的信息來重新構建模型，進而推斷出用戶的隱私信息[7,12].為了抵御重構攻擊，Fredrikson 等人[7]證實可以通過極低隱私預算的差分隱私機制來抵御重構攻擊，但是極低的隱私預算將嚴重影響模型的性能.目前還無法在鏈路預測中抵御重構攻擊的同時保障鏈路預測的準確度.

3 問題描述

社交網絡中包含n個用戶，這些用戶間的關系構成鄰接矩陣X∈Rn×n.將用戶對(i,j)的關系表示為Xij∈{1,?}，1表示已建立有向社交關系(即用戶i已關注用戶j)，?表示用戶間目前還未建立社交關系，這里我們可以把?當作0.令用戶對建立鏈路的預

4 社交網絡鏈路預測的個性化隱私保護方法

4.1 基本模型

以目前最常用的貝葉斯個性化排序模型(Bayesian personalized ranking, BPR)[13]作為基本模型，來實現基于pairwise的鏈路預測：

(1)

這里定義三元集oijk={(i,j,k)|Xij=1∧Xik=0}，σ(x)=1(1+e-x)為可將任何值歸一化到區間(0,1)的函數，ψ是避免過擬合的正則項，λ為控制正則項范圍的超參數.

4.2 社交網絡鏈路預測的隱私保護框架

在學習鏈路預測模型時，服務器需要根據所有已知鏈路關系Xij和用戶對特征向量fij(包括Xsen,Ysen)，來學習、計算出其他變量(即U,V,θ).顯然，U,V,θ的整個計算過程都集中在服務器端，這將導致服務商能輕易獲取用戶的敏感隱私信息.

1) 用戶對的特征向量fij不僅能夠體現用戶i的敏感信息，也能反映用戶j的敏感信息，所以用戶j并不應該將個人敏感信息分享給用戶i，這為計算fij,θi帶來難題；

2) 由于關注與被關注的鏈路關系是成對出現的，服務器端V的計算需要U的參與，而每個Ui僅保存在每個用戶i本地，所以難以在不傷害用戶隱私的前提下完成V的計算;

3) 每個用戶的隱私設置不同，用戶對相同的關注或特征的敏感與否的判斷不同.

為了解決這些難題，我們將介紹求得變量Ui,V,θi最優解的具體算法.

4.3 面向鏈路預測的隱私保護方法

首先采用梯度下降[9]的方式來學習求得滿足式(1)的最優解，迭代更新Ui,Vj,θi直至收斂，在第t次的迭代公式為

(4)

其中，γ為學習步長(learning rate)，目標函數J1關于Ui,Vj,θi的偏導數為

(7)

(8)

此外，我們分別為Pj,Qj賦予不同大小的隱私預算εsen和εnon，其中εsen=βεnon，β∈(0,1)，并定義ε=βεnon(1+β).對于不同情況的鏈路，提供不同幅度的噪聲干擾，在涉及敏感鏈路的計算提供較強的隱私保護，且保證不會大幅削弱整體鏈路預測效果：

1) 對于某條敏感鏈路Xij，Vj的偏導數即為

2)對于不敏感鏈路Xij，Vj的偏導數為

3)對于未知鏈路Xij=0，Vj的偏導數為

算法1.鏈路預測隱私保護算法(PrivLP).

輸入：隱私預算εsen和εnon、學習步長γ、鏈路矩陣X、正則項權重λ、敏感矩陣F、用戶對的特征f；

輸出：U,V,θ.

① 初始化U,V,θ；

② for max iterations

③ forj=1,2,…,n

④ foriwhereFij=1

⑤ 從用戶i獲取φ1；

⑥ end for

⑦ foriwhereFij=0

⑧ 從用戶i獲取φ2；

⑨ end for

⑩ foriwhereXij=0

4.4 隱私保護步驟及理論分析

由于每個用戶對鏈路敏感與否的設置是不同的，且服從Laplace分布的隨機數之和并不服從Laplace分布，這為滿足差分隱私帶來了挑戰.

證明. 令εsen=(1+β)ε,εnon=(1+1β)ε.同時，根據高斯分布特征，顯然且c服從N(0,1).式(6)涉及到的噪聲為

(9)

(10)

由于D1,D2只有1個鏈路不同，假設這是條敏

(11)

(12)

綜上所述，定理3得證.

證畢.

5 實驗與結果

為了驗證社交網絡鏈路預測的個性化隱私保護算法的鏈路預測和隱私保護效果，本文選擇購物網站Ciao的數據集驗證本文提出的PrivLP算法的鏈路預測和隱私保護效果.Ciao數據集[14]中，一共包括18 998個用戶及145 826條有向社交關系，用戶-用戶鏈路矩陣的稀疏度為99.96%，適用于基于矩陣分解的方法.我們為每個用戶隨機抽取了80%的數據加入作為訓練集Dtrain，剩余20%加入測試集Dtest，即訓練集中，在服務器端學習V、在用戶端學習Ui,θi，然后根據學習到的變量計算出用戶對間的鏈路預測值，并在測試集中檢驗鏈路預測及隱私保護效果.在這個過程中，用戶敏感特征Ysen不需要參與服務器端V的計算，僅參與用戶本地的θi的計算.另外，由于每個用戶的個性化隱私設置數據難以獲取，而對于某些用戶的關注更可能被設置敏感鏈路，所以我們隨機抽取用戶，對這些用戶的被關注鏈路(即這些用戶在鏈路中是被關注用戶)中80%為敏感鏈路，不斷抽取用戶直至訓練集Dtrain和測試集Dtest中敏感鏈路的比例為x%，這里x∈{10,30,50}.

我們采取了曲線下面積[13](area under curve, AUC)來衡量鏈路預測和隱私保護效果，并將基于AUC的衡量指標LAUC定義為

(13)

其中,E(i)={(j,k)|(i,j)∈Dtest∧(i,k)?(Dtest∪Dtrain)}.對鏈路預測而言，較高的LAUC意味較好的鏈路預測效果；對隱私保護而言，較低的LAUC表示提供了較高的隱私保護.

我們選擇了目前最具代表性的鏈路預測隱私保護方法PPLR[4]以及基本模型BPR[13]作為對比.為了簡化實驗過程，為每個用戶統一選擇了3個特征用于PrivLP：用戶i的好友個數、用戶j的好友個數、用戶i和j的共同好友個數.ε=0.1,β=0.1.

5.1 鏈路預測效果對比

由于BPR沒有提供隱私保護，所以我們沒有將Dtrain中的Xsen加入鏈路預測的訓練中.

隨著敏感鏈路比例的變化，與PPLR及BPR的實驗對比結果如圖1所示.由于我們是基于BPR的模型，所以在敏感鏈路較少時噪聲干擾導致我們鏈路預測效果明顯低于BPR，這說明噪聲干擾和隱私保護確實存在著博弈關系.而隨著敏感鏈路的增加，由于隱私保護機制激勵用戶將更多的敏感鏈路加入鏈路預測的過程，所以鏈路預測效果反而超過了沒有噪聲干擾的BPR.總的來說，隨著敏感鏈路數目的增長，雖然我們為每個用戶都添加了較大的噪聲，我們仍然能夠維持較高的鏈路預測準確度.

Fig. 1 Link prediction comparison on LAUC with different percentages of sensitive links圖1 隨著隱私鏈路數目變化的鏈路預測LAUC比較

Fig. 2 Privacy protection comparison on LAUC with different percentages of sensitive links圖2 隨著隱私鏈路數目變化的隱私保護LAUC比較

5.2 隱私保護效果對比

鏈路預測的過程中，由于用戶i的敏感特征Yisen僅需要在本地參與θi的計算，而不會泄露給服務商或其他用戶，所以僅需要考慮對敏感鏈路的隱私保護效果.由于BPR沒有提供隱私保護，所以服務器端能夠直接得到Dtrain中的所有數據，并可以根據訓練出的變量值預測Dtest中的敏感鏈路.對于PPLR，所有的參數都存在于每個用戶本地，所以僅利用Dtrain中的Xnon,Ynon進行訓練，并將學習出的變量用于預測Dtest中的敏感鏈路.最后，對于PrivLP，由于每個用戶的特征選擇數目和種類都各不相同，所以攻擊者對模型的重構不考慮fij,θi，通過利用共享的V以及訓練集中的非敏感數據Xnon重新訓練模型

從圖2可以看出，PrivLP的隱私保護效果始終處于領先地位.同時，結合圖1和圖2的結果，我們可以得出結論：我們的方法能夠在維持較高鏈路預測效果的同時有效保護用戶隱私.

5.3 參數ε的影響

為了衡量PrivLP隨參數ε的變化，我們將x固定為10，β固定為0.01.觀察隨著ε={0.001,0.05,0.01,0.1,0.5,1,10}的變化對PrivLP效果的影響.從理論來說，隱私預算ε越低，數據干擾強度越高，隱私保護效果越好.從圖3可見，隨著ε的增長，鏈路預測和隱私保護的LAUC值處于增長趨勢，實驗驗證了ε的增長能提高鏈路預測效果，降低隱私保護效果.

Fig. 3 The impact of ε圖3 ε的影響

5.4 參數β的影響

為了衡量PrivLP隨參數ε的變化，我們將x固定為10，ε固定為0.01.由于β∈(0,1)，所以我們觀察隨著β={0.001,0.05,0.01,0.1,0.5,1}的變化對PrivLP效果的影響.從理論來說，敏感預算與非敏感預算的比例β越高，對于敏感鏈路數據干擾強度越高，隱私保護效果越好.從圖4可見，隨著β的增長，鏈路預測和隱私保護的LAUC值都處于下降趨勢，實驗驗證了β的增長將降低鏈路預測效果，提高隱私保護效果.

Fig. 4 The impact of β圖4 β的影響

6 總 結

為了打消用戶隱私泄露的顧慮，我們提出了一種社交網絡鏈路預測的個性化隱私保護方法.擺脫對服務商的完全依賴，讓用戶和服務商共同合作來完成鏈路預測；并為敏感信息和非敏感信息添加不同強度的噪聲干擾，保護敏感鏈路不被泄露的同時維持較好的鏈路預測效果；根據用戶個性化的隱私設置，為用戶提供個性化的隱私保護.最后，理論證明了提出的方法滿足ε-差分隱私，并在真實數據集上驗證了隱私保護和鏈路預測準確性之間的有效平衡.下一步工作將研究如何在動態的鏈路預測中實現隱私保護.