一種融合差分隱私的隨機游走算法

華雯麗，黃 剛，唐 震

(南京郵電大學 計算機學院、軟件學院、網絡空間安全學院，江蘇 南京 210023)

0 引 言

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

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

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

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

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

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

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

1 相關概念以及背景知識

1.1 用戶行為數據的二分圖表示

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

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

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

1.2 二分圖節點的重要性

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

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

圖2 A與a,e之間相關性比較

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

圖3 A到e的路徑比較

1.3 PageRank

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

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

1.4 差分隱私的介紹

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

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

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

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

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

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

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

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

(2)拉普拉斯機制。

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

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

(3)指數機制。

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

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

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

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

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

圖4 交互式框架

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

圖5 非交互式框架

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

2 算法設計

2.1 PersonalRank隨機游走算法

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

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

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

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

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

或者寫成：

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

那么，迭代公式可以轉化為：

r=(1-?)r0+?MTr

解方程得到：

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

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

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

圖6 二分圖

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

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

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

圖7 融合差分隱私流程

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

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

(1)處理輸入數據，轉化成二分圖模型；

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

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

3 實驗與分析

3.1 數據集

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

數據集是ratings15000.csv，截取自MovieLens數據集，來自http://grouplens.org /datasets/movielens/，主要結構如表1所示。

表1 數據集結構

3.2 實驗結果

實驗默認迭代次數iter_num為100次，只要滿足迭代條件，迭代停止。圖8是iter_num 隨α變化而變化的折線圖，這里取0.8，比較符合實際。

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

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

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

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

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

4 結束語

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