華雯麗，黃 剛，唐 震

(南京郵電大學(xué) 計算機學(xué)院、軟件學(xué)院、網(wǎng)絡(luò)空間安全學(xué)院，江蘇 南京 210023)

0 引 言

近些年，由于移動互聯(lián)網(wǎng)的興起，數(shù)以億計的人已經(jīng)深度接入了互聯(lián)網(wǎng)。2020年第1季度，全球各大網(wǎng)絡(luò)社交應(yīng)用平臺用戶數(shù)量進一步膨脹：推特3.7億，微信12億，抖音5.18億，F(xiàn)acebook 20億。龐大的社交網(wǎng)絡(luò)數(shù)據(jù)，一方面，可以為人們提供越來越符合心意的推薦，Georg Groh和Christian Ehmig的研究[1]表明，在幾個真實的推薦系統(tǒng)中，基于社會化推薦系統(tǒng)的用戶滿意度，明顯高于基于協(xié)同過濾算法的系統(tǒng)，其最關(guān)鍵的部分是基于好友的選擇進行推薦。但是另一方面，個人信息的選擇暴露在網(wǎng)絡(luò)中。用戶的個人隱私得不到保障，既會損失用戶的利益，也會因此反過來丟失注意隱私的用戶。對此，需要設(shè)計一些機制，盡量保證數(shù)據(jù)的隱私性。

針對保護隱私的方法，一般有兩種，一種是對匿名方法[2]，但是網(wǎng)絡(luò)圖的特殊性，使得匿名數(shù)據(jù)遇到節(jié)點度數(shù)或者結(jié)構(gòu)的攻擊，更容易被識別出來，比如，在并不想披露朋友之間的關(guān)系的情況下，識別出該獨特關(guān)系的圖數(shù)據(jù)。另一種算法─差分隱私保護(differential privacy)[3-6]，是由Dwork等提出的新型隱私保護模型，從定義上保證隱私，且與大量的背景知識無關(guān)，這種隱私保護算法不僅僅從理論上可以保護隱私，也被用在現(xiàn)實工業(yè)應(yīng)用中[7-10]。

文中的主要工作就是在保證推薦的同時，進行差分隱私操作，保護用戶以及好友的個人隱私，主要分為以下幾步：

(1)處理用戶和物品的二分圖，轉(zhuǎn)化成轉(zhuǎn)移矩陣作為數(shù)據(jù)的輸入；

(2)對轉(zhuǎn)移矩陣基于拉普拉斯機制加噪，再進行隨機游走；

(3)隨機游走得到推薦物品與推薦目標的關(guān)聯(lián)性分值列表；

(4)將每個推薦結(jié)果的分值，根據(jù)指數(shù)機制得到最終的推薦結(jié)果。

1 相關(guān)概念以及背景知識

1.1 用戶行為數(shù)據(jù)的二分圖表示

用戶行為有很多種方法可以表示，本節(jié)主要討論用二分圖表示用戶行為[11]。

由二元組能夠表示用戶的行為，例如一個二元組(u,i)代表用戶u和物品i有行為關(guān)系。這些二元組可以直接組成一個二分圖。例如，將用戶頂點和物品頂點構(gòu)成一個用戶物品二分圖，其中頂點之間的邊表示用戶u對物品i產(chǎn)生的行為。如圖1所示，左邊表示用戶和物品節(jié)點，用戶A對a,b,d都產(chǎn)生行為，轉(zhuǎn)化成二分圖，將A和a,b,d連接起來。

圖1 用戶與物品之間的二分圖

1.2 二分圖節(jié)點的重要性

得到用戶與物品的二分圖之后，需要對指定用戶進行個性化的推薦，則主要是計算節(jié)點之間的相關(guān)性，在用戶未選擇的物品列表中，選擇對指定用戶節(jié)點重要性最高的那個節(jié)點，節(jié)點重要性越高，對于指定用戶節(jié)點相關(guān)性就越高。

節(jié)點之間的重要性比較，第一個重要性是路徑個數(shù)，指定用戶節(jié)點到相關(guān)的物品節(jié)點之間的路徑越多，該物品節(jié)點對于指定用戶節(jié)點的重要性越高。舉一個例子，如圖2所示，假設(shè)目標用戶是A，A已經(jīng)連接a,b,d,需要比較c,e兩個節(jié)點對A節(jié)點的重要性，圖中左邊的二分圖中，加粗的線表示A到c有一條路徑，長度為3，為(A,a,B,c);圖中右邊的二分圖中，有兩組從A到e的路徑，長度也為3，為(A,b,C,e)和(A,d,D,e)，相對于c來說，e的重要性更高。

圖2 A與a,e之間相關(guān)性比較

另外一個重要性比較是從節(jié)點之間的路徑來看，越分散，重要性越差。如圖3所示，從A到e的兩條路徑，(A,b,C,e)經(jīng)過的頂點的出度為(3,2,2,2),而另外一條(A,d,D,e)經(jīng)過的頂點個數(shù)為(3,2,3,2),兩者比較，(A,d,D,e)經(jīng)過節(jié)點D的出度較大，重要性分散較多。所以，對于節(jié)點A到e的重要性而言，路徑(A,b,C,e) 比路徑(A,d,D,e)的貢獻要大。

圖3 A到e的路徑比較

1.3 PageRank

隨機游走算法[12]的主要思想來自Google的PageRank，可以計算不同網(wǎng)頁之間的重要性，進行排名顯示重要性高的節(jié)點，該算法的公式如下：

其中，PR(i)是節(jié)點i被訪問到的概率，?是用戶繼續(xù)訪問節(jié)點的概率，N是所有節(jié)點的數(shù)量，in(i)是所有指向節(jié)點i的節(jié)點集合，out(j)是節(jié)點j指向的其他節(jié)點集合。

1.4 差分隱私的介紹

差分隱私算法[13-14]在于，向查詢輸出結(jié)果中添加噪聲，從而隱藏敏感數(shù)據(jù)，同時能夠保證處理之后的數(shù)據(jù)，不會影響數(shù)據(jù)挖掘的結(jié)果。假設(shè)一個攻擊者，有足夠大的背景知識的支撐下，就能夠從N-1條數(shù)據(jù)記錄中查詢做差得到被攻擊者的隱私，但是差分隱私能夠從定義上解決這個問題。

其核心思想主要體現(xiàn)在兩個方面，其一，在插入和刪除任意一條數(shù)據(jù)記錄時不會影響輸出的結(jié)果；其二，無論是否有足夠的背景知識，隱私信息也不會泄露。其定義如下：

定義：對于兩個數(shù)據(jù)集D和D'，D和D'相差一條記錄，記作|DΔD'|≤1，現(xiàn)有一個隨機算法A，range(A)表示該算法的取值范圍，如果A在D和D'數(shù)據(jù)集上輸出的結(jié)果S，S∈range(A)，符合下面的公式，則稱A滿足ε-差分隱私。

Pr[A(D)∈S]≤eε×Pr[A(D')∈S]

其中，ε是指隱私保護參數(shù)，可以表示隱私保護的程度，該值越小，表示保護的程度越高，Pr[]是隱私被泄露的概率。

(1)敏感度：函數(shù)的敏感度可以分為全局敏感度和局部敏感度。這里主要說明全局敏感度，全局敏感度是指對于該函數(shù)，在兩個D和D'數(shù)據(jù)集上輸出的最大差別，其形式化定義如下：

對于一個任意函數(shù)f:D→Rd，d表示函數(shù)f的維度，則函數(shù)f的Lk全局敏感度Sk(f)為：

其中：數(shù)據(jù)集D和D'相差一條記錄，‖·‖k表示Lk范數(shù)。

(2)拉普拉斯機制。

Dwork等人在文獻[6]中提出差分隱私保護模型，提出拉普拉斯機制，可以取得差分隱私保護效果，就是通過添加拉普拉斯隨機噪聲，可以實現(xiàn)差分隱私保護。拉普拉斯分布的概率密度函數(shù)為：

其中，Δf是針對函數(shù)f的全局敏感度，ε是差分隱私保護參數(shù)。產(chǎn)生的噪聲與Δf成正比，與ε成反比。

(3)指數(shù)機制。

指數(shù)機制的原理是定義一個打分函數(shù)q，用來評價每種輸出可能性的分值，分值高的輸出可能性就會有更高的概率被發(fā)布，主要是用于計數(shù)統(tǒng)計，例如投票計算。指數(shù)機制可以用下面的定義表示。

針對隨機算法A，q(D,r)→R，數(shù)據(jù)集D，輸出為一實體對象r∈Range,q(D,r)→R為可用性函數(shù)，用來表示輸出的可能性。若算法A以正比于eε*q(D,r)/2Δq的概率，從Range中選擇并輸出r，Δq是函數(shù)的敏感度，那么算法M提供ε差分隱私保護。

指數(shù)機制的敏感度：S(q)=max‖q(T1,R)-q(T2,r)‖，其中r是任意合法的輸出。

差分隱私數(shù)據(jù)保護框架一般分為以下兩種[15]：

(1)交互式保護：用戶請求查詢數(shù)據(jù)庫，數(shù)據(jù)庫將真實的結(jié)果進行差分隱私保護，比如加上噪聲，然后將加上噪聲的結(jié)果返回給用戶，如圖4所示。

圖4 交互式框架

(2)非交互式保護：數(shù)據(jù)庫直接用差分隱私進行保護，形成隱私數(shù)據(jù)庫，直接與用戶交互的數(shù)據(jù)庫是隱私數(shù)據(jù)庫，如圖5所示。

圖5 非交互式框架

文中主要使用的兩種融合的交互式保護，先將原始數(shù)據(jù)轉(zhuǎn)化成轉(zhuǎn)移矩陣，根據(jù)拉普拉斯進行加噪，再將加噪的數(shù)據(jù)作為輸入數(shù)據(jù)，進行PersonalRank排序，得到的結(jié)果再根據(jù)指數(shù)機制進行差分隱私保護。

2 算法設(shè)計

2.1 PersonalRank隨機游走算法

得到用戶物品的二分圖之后，對指定用戶u進行個性化推薦，就需要在二分圖上進行隨機游走[13]。啟始點為用戶節(jié)點Vu，以?的概率決定是不是繼續(xù)往下走，還是停止，從Vu繼續(xù)重新開始走。如果是決定往下走，那就從當前節(jié)點所連接的節(jié)點中隨機選擇一個節(jié)點，作為下次游走的節(jié)點，繼續(xù)重復(fù)這樣的操作，每個物品節(jié)點就會收斂成一個穩(wěn)定的概率，最后的推薦中，物品的分值就是物品節(jié)點的訪問概率。以上步驟可以簡化為以下公式：

其中，PR(v)表示v的點擊概率，就是物品v的分值，out(v')表示物品節(jié)點v'的出度，?表示留在當前的概率。

對比PageRank算法，PersonalRank算法不同點只在于r的值不同，意思便是每次都是從目標用戶節(jié)點出發(fā)，進行隨機游走。PageRank是針對所有節(jié)點，計算各點的訪問概率，而PersonalRank算法是所有物品頂點相對于目標用戶節(jié)點的概率。

PersonalRank算法雖然能夠很好地在物品二分圖上進行迭代，但是因為每推薦一次，都要在整個二分圖上迭代，直到整個二分圖的概率穩(wěn)定，使得這個過程時間復(fù)雜度較高，生成的推薦結(jié)果很耗時，同時也無法在線提供實時推薦。

為了解決整個問題，有兩種方法，第一種是控制迭代的次數(shù)，設(shè)定一個指定迭代次數(shù)，在收斂之前就可以停止。但是這種方法有個問題，準確度無法保證，但是影響不大。另一種是轉(zhuǎn)化成矩陣計算，將二分圖轉(zhuǎn)化成轉(zhuǎn)移矩陣的形式，公式如下：

或者寫成：

將v轉(zhuǎn)移為v'，得到的是一個概率值，|out(v)|是v的出度，是一個實數(shù)，那么1/|out(v)|就可以表示這個節(jié)點v轉(zhuǎn)移以后的概率矩陣。

那么，迭代公式可以轉(zhuǎn)化為：

r=(1-?)r0+?MTr

解方程得到：

r=(1-?MT)-1(1-?)r0

因為只看相對的大小，而取r中元素排序的前k個值，則忽略1-?的具體值，只要計算(1-?MT)-1的值，并且該式是高度稀疏矩陣，容易計算。

舉個例子來說，如圖6所示，將二分圖轉(zhuǎn)換成轉(zhuǎn)移矩陣，每一列表示一個節(jié)點出邊的權(quán)重，例如第一列表示節(jié)點A的出邊，它對a,c兩個節(jié)點分別有一條邊，權(quán)重為1/2，所以該圖對應(yīng)的轉(zhuǎn)移矩陣如下：

圖6 二分圖

第一行是各個節(jié)點轉(zhuǎn)移到節(jié)點A的概率，而r的第一列分別是各個節(jié)點當前的PR值，因此用M的第一行乘以r的第一列，所得結(jié)果就是節(jié)點A的最新PR值。

2.2 融合差分隱私的模型計算

為滿足差分隱私，先將數(shù)據(jù)集處理，針對二分圖轉(zhuǎn)化成轉(zhuǎn)移矩陣，計算對應(yīng)點的PR值，加入拉普拉斯噪聲，進行PersonalRank隨機游走，根據(jù)得到的每個物品節(jié)點的分值，篩去目標用戶已經(jīng)做出選擇的物品。由于物品數(shù)量很多，推薦結(jié)果只需要一個，可以將得到的物品分值取出Top10，以這10個物品的分值作為打分函數(shù)，以滿足指數(shù)機制的概率輸出一個目標物品。圖7是整體的流程圖。

圖7 融合差分隱私流程

輸入：用戶物品評分和目標用戶u；

輸出：輸出給目標用戶的推薦物品item。

(1)處理輸入數(shù)據(jù)，轉(zhuǎn)化成二分圖模型；

(2)計算轉(zhuǎn)移矩陣，加上拉普拉斯噪聲；

(3)根據(jù)PersonalRank的公式計算每個節(jié)點PR分值;

3 實驗與分析

3.1 數(shù)據(jù)集

根據(jù)以上提出的計算方法，本節(jié)將在真實數(shù)據(jù)集上進行實驗，用來驗證新算法。實驗結(jié)果表示不但可以進行差分隱私保護，同時也能達到一定的推薦準確率。

數(shù)據(jù)集是ratings15000.csv，截取自MovieLens數(shù)據(jù)集，來自http://grouplens.org /datasets/movielens/，主要結(jié)構(gòu)如表1所示。

表1 數(shù)據(jù)集結(jié)構(gòu)

3.2 實驗結(jié)果

實驗?zāi)J迭代次數(shù)iter_num為100次，只要滿足迭代條件，迭代停止。圖8是iter_num 隨α變化而變化的折線圖，這里取0.8，比較符合實際。

圖8 iter_num 隨α變化而變化的折線圖

另一個主要的參數(shù)是隱私保護參數(shù)ε，由文獻[16]可知隱私預(yù)算ε越大，數(shù)據(jù)可用性越高，安全性越低，當隱私預(yù)算ε=0時，數(shù)據(jù)失去意義。

該實驗得到的結(jié)果，主要是以節(jié)點分值為打分函數(shù)，以指數(shù)概率輸出，每次得到推薦物品并不一定相同，以下圖標是統(tǒng)計分值前十的物品，在100次查詢中，不同的隱私預(yù)算的情況被輸出的次數(shù)(見圖9)。

圖9 推薦位序前十物品每次輸出頻率

由圖9可以得知，該模型能夠很好地保護輸出的結(jié)果，高概率的分值以指數(shù)高概率輸出，低概率的分值以指數(shù)低概率輸出，每次查詢的結(jié)果并不一定相同，同時，由于是取的分值前十，也在一定程度上保證了推薦的準確度，同時也驗證了隱私預(yù)算越大，數(shù)據(jù)可用性越高。

4 結(jié)束語

為了保證推薦結(jié)果的隱私性，通過差分隱私的拉普拉斯機制和指數(shù)機制，以PersonalRank都得到的分值，敏感度為最大分值減去最小分值，篩選目標用戶選擇的物品，取Top10為打分函數(shù)，以滿足差分隱私的概率輸出推薦物品。該模型每次輸出的推薦結(jié)果不一定相同，分值高的節(jié)點輸出概率更高，因為滿足指數(shù)機制，可以保證攻擊者不會通過查詢作差得到目標用戶或者其他用戶對物品的行為。但是該模型針對大型網(wǎng)絡(luò)圖數(shù)據(jù)迭代時間復(fù)雜度過高，應(yīng)用中需要根據(jù)實際情況選擇。