社交網(wǎng)絡(luò)鏈路預(yù)測的個(gè)性化隱私保護(hù)方法

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

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

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

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

為了解決現(xiàn)有隱私保護(hù)機(jī)制的問題和不足，本文設(shè)計(jì)了一種社交網(wǎng)絡(luò)鏈路預(yù)測的個(gè)性化隱私保護(hù)方法，避免不可信的服務(wù)商和不可信的朋友對用戶敏感鏈路的推測，并在維持鏈路預(yù)測準(zhǔn)確性的前提下提升了隱私保護(hù)效果.本文主要的貢獻(xiàn)包括3個(gè)方面：

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

2) 提出了一種個(gè)性化隱私保護(hù)的方法.為了避免不可信服務(wù)商和不可信朋友的攻擊，將噪聲干擾分解為每個(gè)用戶可獨(dú)立處理的分量.同時(shí)，為敏感信息和非敏感信息添加不同強(qiáng)度的噪聲干擾，有效抵御重構(gòu)攻擊的同時(shí)保證鏈路預(yù)測的準(zhǔn)確度.

3) 從理論上證明我們的個(gè)性化的分布式隱私保護(hù)機(jī)制滿足ε-差分隱私，并在真實(shí)數(shù)據(jù)集上驗(yàn)證了其有效性.實(shí)驗(yàn)結(jié)果表明本文提出的機(jī)制實(shí)現(xiàn)了隱私保護(hù)和鏈路預(yù)測準(zhǔn)確性之間的有效平衡.

1 相關(guān)工作

本節(jié)主要介紹了2類典型的鏈路預(yù)測算法，以及現(xiàn)有的面向鏈路預(yù)測的隱私保護(hù)算法.

1.1 鏈路預(yù)測算法

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

1.2 社交網(wǎng)絡(luò)中鏈路預(yù)測的隱私保護(hù)算法

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

由于目前基于pointwise的鏈路預(yù)測的隱私保護(hù)機(jī)制不能直接應(yīng)用于基于pointwise的鏈路預(yù)測方法，因此結(jié)合現(xiàn)有隱私保護(hù)機(jī)制的問題和不足，以及用戶個(gè)性化的需求，針對基于pairwise的鏈路預(yù)測方法，還需要提出新的鏈路預(yù)測隱私保護(hù)方法.

2 理論基礎(chǔ)

2.1 ε-差分隱私

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

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

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

則稱算法M滿足ε-差分隱私要求，概率P表示隱私泄露的風(fēng)險(xiǎn)，隱私預(yù)算ε用于衡量隱私保護(hù)強(qiáng)度.

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

為了利用Laplace機(jī)制實(shí)現(xiàn)差分隱私，我們結(jié)合Laplace分布的性質(zhì)，將其分解為服從高斯分布和指數(shù)分布的2個(gè)隨機(jī)數(shù)的計(jì)算值.

2.2 推斷攻擊與重構(gòu)攻擊

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

重構(gòu)攻擊則利用公開的信息來重新構(gòu)建模型，進(jìn)而推斷出用戶的隱私信息[7,12].為了抵御重構(gòu)攻擊，F(xiàn)redrikson 等人[7]證實(shí)可以通過極低隱私預(yù)算的差分隱私機(jī)制來抵御重構(gòu)攻擊，但是極低的隱私預(yù)算將嚴(yán)重影響模型的性能.目前還無法在鏈路預(yù)測中抵御重構(gòu)攻擊的同時(shí)保障鏈路預(yù)測的準(zhǔn)確度.

3 問題描述

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

4 社交網(wǎng)絡(luò)鏈路預(yù)測的個(gè)性化隱私保護(hù)方法

4.1 基本模型

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

(1)

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

4.2 社交網(wǎng)絡(luò)鏈路預(yù)測的隱私保護(hù)框架

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

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

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

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

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

4.3 面向鏈路預(yù)測的隱私保護(hù)方法

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

(4)

其中，γ為學(xué)習(xí)步長(learning rate)，目標(biāo)函數(shù)J1關(guān)于Ui,Vj,θi的偏導(dǎo)數(shù)為

(7)

(8)

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

1) 對于某條敏感鏈路Xij，Vj的偏導(dǎo)數(shù)即為

2)對于不敏感鏈路Xij，Vj的偏導(dǎo)數(shù)為

3)對于未知鏈路Xij=0，Vj的偏導(dǎo)數(shù)為

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

輸入：隱私預(yù)算εsen和εnon、學(xué)習(xí)步長γ、鏈路矩陣X、正則項(xiàng)權(quán)重λ、敏感矩陣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 隱私保護(hù)步驟及理論分析

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

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

(9)

(10)

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

(11)

(12)

綜上所述，定理3得證.

證畢.

5 實(shí)驗(yàn)與結(jié)果

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

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

(13)

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

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

5.1 鏈路預(yù)測效果對比

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

隨著敏感鏈路比例的變化，與PPLR及BPR的實(shí)驗(yàn)對比結(jié)果如圖1所示.由于我們是基于BPR的模型，所以在敏感鏈路較少時(shí)噪聲干擾導(dǎo)致我們鏈路預(yù)測效果明顯低于BPR，這說明噪聲干擾和隱私保護(hù)確實(shí)存在著博弈關(guān)系.而隨著敏感鏈路的增加，由于隱私保護(hù)機(jī)制激勵(lì)用戶將更多的敏感鏈路加入鏈路預(yù)測的過程，所以鏈路預(yù)測效果反而超過了沒有噪聲干擾的BPR.總的來說，隨著敏感鏈路數(shù)目的增長，雖然我們?yōu)槊總€(gè)用戶都添加了較大的噪聲，我們?nèi)匀荒軌蚓S持較高的鏈路預(yù)測準(zhǔn)確度.

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

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

5.2 隱私保護(hù)效果對比

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

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

5.3 參數(shù)ε的影響

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

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

5.4 參數(shù)β的影響

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

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

6 總 結(jié)

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