一種融合差分隱私的隨機(jī)游走算法

華雯麗，黃 剛，唐 震

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

0 引 言

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

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

文中的主要工作就是在保證推薦的同時(shí)，進(jìn)行差分隱私操作，保護(hù)用戶以及好友的個(gè)人隱私，主要分為以下幾步：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖3 A到e的路徑比較

1.3 PageRank

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

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

1.4 差分隱私的介紹

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

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

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

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

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

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

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

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

(2)拉普拉斯機(jī)制。

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

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

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

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

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

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

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

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

圖4 交互式框架

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

圖5 非交互式框架

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

2 算法設(shè)計(jì)

2.1 PersonalRank隨機(jī)游走算法

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

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

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

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

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

或者寫成：

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

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

r=(1-?)r0+?MTr

解方程得到：

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

因?yàn)橹豢聪鄬?duì)的大小，而取r中元素排序的前k個(gè)值，則忽略1-?的具體值，只要計(jì)算(1-?MT)-1的值，并且該式是高度稀疏矩陣，容易計(jì)算。

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

圖6 二分圖

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

2.2 融合差分隱私的模型計(jì)算

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

圖7 融合差分隱私流程

輸入：用戶物品評(píng)分和目標(biāo)用戶u；

輸出：輸出給目標(biāo)用戶的推薦物品item。

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

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

(3)根據(jù)PersonalRank的公式計(jì)算每個(gè)節(jié)點(diǎn)PR分值;

3 實(shí)驗(yàn)與分析

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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