Top-k頻繁子圖挖掘的差分隱私保護算法

徐 捷，楊 庚,2，白云璐,3

(1.南京郵電大學 計算機學院，江蘇 南京 210046；2.江蘇省大數據安全與智能處理重點實驗室，江蘇 南京 210023；3.南京中醫藥大學 信息技術學院，江蘇 南京 210003)

0 引 言

由于在現實世界的應用程序中越來越多地使用圖結構，圖挖掘已經變得非常流行。頻繁子圖挖掘是圖挖掘中一個重要且有趣的問題，其目標是提取給定數據集中的出現次數高于指定閾值的子圖[1]。頻繁子圖挖掘的應用非常廣泛，推薦系統就是最常見的應用，通過對瀏覽痕跡的挖掘，推斷用戶的購買意向，從而進行相關的推薦。同時，在軟件工程、生物化學、金融等領域，頻繁子圖挖掘都有非常廣闊的應用前景[2-3]。

盡管頻繁子圖挖掘具有很高的實際應用價值，但是在挖掘和發布子圖時都存在著隱私泄露的風險[4]。假設有一個醫療保健的圖數據庫D，D中的每條記錄表示一個用戶的健康狀況，子圖表示某種疾病。對D進行頻繁子圖挖掘，挖掘結果顯示了共有10個人患有肝炎。當新用戶Allen的記錄加入數據集D后，再次進行挖掘，肝炎患者的數量變為11，就可以推斷出Allen是肝炎患者，Allen的隱私因此泄露。由此可見，頻繁子圖挖掘的結果不經過處理就發布很容易造成隱私的泄露，通過分析單個記錄變化所引起的查詢結果的變化，攻擊者就可以輕易推斷出用戶的個人信息，這種攻擊模式叫做差分攻擊[4]。

差分隱私保護技術有別于傳統的隱私保護技術，以成熟的概率分布知識為基礎，通過添加隨機噪聲擾動輸出結果實現隱私保護，能夠有效地抵御差分攻擊。在差分隱私模型下，可以通過某種差分隱私隨機算法K來發布數據，并為用戶提供搜索界面，該算法保證了挖掘結果不會因為數據集中任一記錄的改變而受到顯著的影響[5]。

目前，能夠實現差分隱私保護的頻繁子圖挖掘算法并不多，而且這些算法難以同時滿足高可用性與安全性，要么為了實現隱私保護，添加了過量的噪聲，挖掘出的結果并不正確，數據的可用性大大降低；要么，隱私保護的力度不夠，達不到ε-差分隱私。為此，該文提出了一種滿足差分隱私的top-k頻繁子圖挖掘算法DP-TGM，其主要貢獻如下：

(1)為了實現差分隱私保護，在算法的三個階段都使用拉普拉斯機制給子圖的支持度添加噪音，將閾值也一直更新為隊列中的最小噪音支持度。

(2)為了提高數據可用性，采用均分法和特殊級數法來分配隱私預算，降低誤差；同時，不斷更新變大的閾值減少了子圖的擴展比較次數，進一步提升準確性。

(3)理論證明，算法實現了差分隱私保護；通過對比實驗，在不同規模的真實圖數據集上，DP-TGM算法都展現出了更高的數據可用性。

1 相關工作

近些年來，已經有不少學者提出了滿足差分隱私的top-k頻繁模式挖掘算法。2012年，Li等人提出了PrivBasis算法[6]，該算法通過將輸入數據投影到人們所關心的少數選定維度上來應對高維性的挑戰。PrivBasis算法在高維數據集上的表現遠優于TF算法，但其可用性卻因隨機截斷引起的截斷誤差而大受影響。針對此問題，蔣辰等人[7]提出了TrunSuper算法，該算法使用新的截斷方法，將事務中支持度較小的項剔除，通過降維減小項集的支持度誤差。

在滿足差分隱私的top-k子圖挖掘方面，2013年，Shen等人[8]提出了一種基于采樣的頻繁子圖挖掘算法Diff-FPM，該算法可概括為以下兩個步驟：

(1)采樣：使用馬爾可夫鏈蒙特卡羅抽樣(MCMC)的方法來擴展指數機制，并使用擴展指數機制直接從圖數據集中選擇頻繁子圖，重復此過程，直到獲得了top-k頻繁子圖；

(2)擾動：對獲得的top-k子圖的支持度添加符合拉普拉斯分布的噪音。

然而，當樣本的分布不可觀察時，驗證MCMC的收斂仍然是一個懸而未決的問題，Diff-FPM算法僅僅滿足較弱的(ε,δ)-差分隱私。此外，算法從所有子圖構成的空間中進行挑選，引入的噪音過大，數據的可用性較差。

張嘯劍等人[9]提出的DP-tokP算法在差分隱私保護的模型下進行top-k頻繁模式的挖掘，可用于top-k子圖挖掘，其思想如下：

(1)挖掘出圖數據集中所有支持度大于閾值的頻繁子圖，存入集合S中；

(2)設置打分函數為子圖的支持度，為S中的每個子圖進行打分。使用指數機制為每個子圖按照分值賦予權重，并降序排列，從排列好的子圖中不放回地抽取k個子圖，形成最終的top-k子圖集合；

(3)為挖掘出的top-k子圖的支持度添加拉普拉斯噪音。

該算法同樣使用了差分隱私的兩種機制，滿足ε-差分隱私保護。但是，在使用指數機制挑選子圖之前，需要挖掘出所有的候選集，初始閾值的選擇不同，候選集的個數就不同，候選集越多，產生的擾動越大，挖掘結果的準確性就越低。

以上算法在兼顧安全性和數據可用性方面依舊有很大的提升空間，難以運用于實際應用。為此，該文提出了DP-TGM算法，采用合理的隱私預算分配方法，提高數據可用性，在挖掘過程和發布數據時達到隱私保護的效果。

2 理論基礎

2.1 差分隱私

定義1 近鄰數據集。給定兩個數據集D和D'，當且僅當兩數據集之間只相差一條記錄時，可稱之為近鄰數據集[10]。

定義2ε-差分隱私。給定兩個近鄰數據集D和D'，若算法A作用在數據集D和D'上的結果滿足不等式(1)，則稱算法滿足ε-差分隱私。

Pr[A(D)=O]≤exp(ε)×Pr[A(D')=O]

(1)

不等式中，Pr[X]是事件X發生的概率，即隱私泄露的概率，它由算法A的隨機屬性確定。參數ε是隱私保護預算，ε值與隱私保護程度成反比，ε越小，兩個近鄰數據集的相同輸出的概率越接近，隱私保護的程度越高。

定義3 全局敏感度。對于任意一個函數f：D→Rn，它的全局敏感性Δf定義為：

(2)

R表示所映射的實數空間，n表示函數f的查詢維度。全局敏感度的大小與具體的數據集無關，由查詢函數決定，反映了函數f在D和D'上變化的最大范圍[11]。

添加噪聲是使算法實現差分隱私保護的主要途徑，最常用的噪聲添加機制是拉普拉斯(Laplace)機制和指數機制，其中，拉普拉斯機制主要適用于數值型輸出，而指數機制適用于非數值型輸出[12]。

定義4 拉普拉斯機制。拉普拉斯機制通過在查詢結果上添加滿足Laplace分布的噪音來實現隱私保護。給定數據集D，若有函數f：D→Rd，其敏感度為Δf，當算法A的輸出結果滿足下列等式：

A(D)=f(D)+

(3)

則算法A滿足ε-差分隱私，其中，Lapi(Δf/ε)(1≤i≤n)是相互獨立的拉普拉斯變量。噪聲大小與Δf成正比，與ε成反比。

定義5 指數機制。指數機制首先需要制定一個打分函數u:(D×O)→R,設A為指數機制下的某個算法，則輸出結果為：

(4)

由公式(4)可知，分值越高，添加的噪聲就越大，被輸出的概率也越大。

2.2 頻繁子圖挖掘

頻繁子圖挖掘是頻繁模式挖掘的問題之一，其任務是找出圖數據庫中頻繁出現的子圖結構。

定義7 支持度。子圖g的支持度指的是圖數據庫中包含子圖g的記錄的個數，同一記錄中出現多次也只記一次，文中支持度用Sup(g)表示。

定義8 噪音支持度[12]。某一子圖g在其支持度Sup(g)上添加噪音形成的支持度稱為噪音支持度，如式(5)所示：

NSup(g)=Sup(g)+noise

(5)

其中，NSup(g)表示子圖g的噪音支持度，noise表示添加的噪音。

定義9 頻繁子圖挖掘。給定圖數據庫D={G1,G2,…,Gn}和閾值θ，支持度大于等于θ的子圖被稱為頻繁子圖，頻繁子圖挖掘就是找出圖數據庫中所有的頻繁子圖。

定義10 top-k頻繁子圖挖掘[14]。給定圖數據庫D={G1,G2,…,Gn}和用戶自定義值k(一般來說，k的取值較低)，top-k頻繁子圖挖掘就是找出圖數據庫中支持度排名前k的頻繁子圖。

3 DP-TGM算法

DP-TGM算法的挖掘對象是圖數據集中支持度排名前k的子圖，算法共分為三個階段：預處理階段、深度挖掘階段和噪音添加階段。

3.1 DP-TGM算法概述

算法使用兩個優先級隊列QK和QS，QK用來存儲臨時挖掘到的top-k頻繁子圖，噪音支持度小的優先級高；QS用來存儲待拓展的頻繁邊，支持度高的優先級高。算法將隱私預算ε分為三份，分別用于預處理、深度挖掘和噪音添加階段，算法1展示了算法的整體框架。

算法1:DP-TGM算法。

輸入：圖數據集GD；隱私預算ε；k。

輸出：top-k頻繁子圖及其噪音支持度。

1.Initialize the priority queueQK；

2.Initialize the priority queueQS；

3.ε=ε1+ε2+ε3；

4.Pre-mining(GD,ε1)；

5.Top-k-mining(GD,ε2,QS)；

6.Add-noise(QK,ε3)；

7.returnQK。

如算法1所示：給定圖數據集D，隱私預算ε和k，算法通過三個階段的挖掘處理，最終得到top-k頻繁子圖集合QK。其中，預處理階段主要用來獲取頻繁點和頻繁邊，分配隱私預算ε1；深度挖掘階段將預處理階段所得的頻繁邊進行深度挖掘，得到最終的top-k子圖集合，分配隱私預算ε2；噪音添加階段對挖掘結果的支持度添加拉普拉斯噪音進行擾動，分配隱私預算ε3。

下面將對三個階段展開講解。

3.2 預處理階段

預處理階段是DP-TGM算法的第一階段，將圖數據集進行遍歷，獲得頻繁點和頻繁邊，更新QK和QS并得到新的閾值。預處理階段的算法如下。

算法2：預處理算法Pre-mining(GD，ε1)。

輸入：圖數據集GD；隱私預算ε1。

輸出：預處理階段的top-k子圖集合QK，QS。

1.θ=10；

2.挖掘出頻繁的點和邊，并存入QK中；

3.if (|QK|>k) //|QK|表示隊列的大小

4. 刪去QK中支持度較低的子圖；

5.end if

6.依據QK對數據集GD剪枝；

7.將QK中的頻繁邊復制并存入QS中；

8.for each subgraph s inQK:

9.Nsup(s)=sup(s)+Laplace(|QK|/ε1)；

10.End for

11.θ=Nsup(QK.peek)；//閾值更新為QK中的最小噪音支持度;

12.returnQK，QS。

算法2是對預處理階段的具體描述，首先設置一個較低的閾值θ(例如θ=10)，遍歷數據集GD，挖掘出支持度大于閾值的頂點和邊，存入QK中。若是QK中的子圖個數大于k，則將支持度低的子圖移出隊列，依據QK進行剪枝。QS中放入QK中的頻繁邊，用來進行下一輪的拓展。最后將QK中的子圖添加上拉普拉斯噪音，更新閾值為QK中噪音支持度的最小值。

定理1：算法2滿足ε1-差分隱私。

證明：在圖數據集GD中，添加或刪除一條記錄，對每個子圖的支持度影響最多為1，所以算法2的敏感度為1。因此，如算法2的第7行所示，給QK中的每個子圖添加的噪音為Laplace(|QK|/ε1)(|QK|表示隊列QK的大小)，則每個子圖都滿足ε1/|QK|-差分隱私，由定義6可得，算法2滿足ε1-差分隱私。

證畢。

3.3 深度挖掘階段

DP-TGM算法在深度挖掘階段有兩大重要思想：

(1)不斷更新閾值。在深度挖掘階段，閾值θ隨著優先權隊列QK的變化而不斷改變，始終將其更新為QK中的最小噪音支持度，這樣可以有效地提高挖掘效率。

(2)合理分配隱私預算。隱私預算的分配涉及到噪音添加的強度，也直接影響到數據的可用性與安全性。在深度挖掘階段，將會使用兩種隱私預算分配方法：均分法和特殊級數法，對ε2進行兩次分配，以更低的速度釋放隱私預算，提高挖掘結果的準確性。

算法3：深度挖掘算法Top-k-mining(GD，ε2，QS)。

輸入：圖數據集GD；隱私預算ε2；k；算法1得到的QK，QS。

輸出：top-k子圖集合QK。

1.εa=ε2/|QS|；

2.whileQSis not empty：

3.g←pop the subgraph with highest priority inQS；

4.ifQKcontainsgthen

5.初始化優先權隊列Q；//支持度越高，則優先級越高;

6.對g擴展，并將擴展的圖存入Q；

7.for eachginQ：

9. Nsup(i)=Sup(i)+Laplace(1/εi) ;

10.` if (min(g) && Nsup(g)>θ)

11.store g intoQK；

12. if |QK|>kthen

13.QK.pop()；

14.θ=Nsup(QK.peek)；

15. end if

16. else

17.break;

18. end for

19. else

20. break;//算法結束

21.end while

22.returnQK。

算法3首先將隱私預算等分為εa=ε2/|QS|，將QS中優先級最高(支持度最高)的子圖g彈出。如果QK不包含g，則算法終止，因為g是待拓展的子圖里支持度最高的，而g被QK剔除，說明其支持度不夠。如果QK中包含g，則將g按照最右路徑規則進行拓展，并將拓展的圖放入優先級隊列Q中。將Q中的每個圖s按特殊級數法進行隱私預算的分配，添加拉普拉斯噪聲，如果噪音支持度大于θ，則將s插入QK中，然后判斷QK的大小，按情況對QK進行更新，且將支持度始終設置為QK中的最小噪音支持度。若是s的噪音支持度小于閾值，則關于g的擴展結束。當QS為空時或QS中優先級最高的邊都不滿足要求，則算法結束，此時，QK存儲的就是最終的top-k頻繁子圖。

定理2：差分隱私保護方法中，特殊級數法[15]采用如下預算分配方式：

(6)

則有限次隱私預算分配滿足ε-差分隱私。

證明：因為任意一次隱私預算分配量εi>0，(i∈N+)，有限次(n<∞)分配的隱私預算分配量之和為：

(7)

則有限次隱私預算分配ε-滿足差分隱私。

證畢。

定理3：算法3滿足ε2-差分隱私。

證明：算法3首先使用均分法將ε2分為εa=ε2/|QS|，QS中的每個子圖得到了εa的隱私預算。算法依次將QS中優先級最高的子圖g移出隊列，進行深度挖掘，使用特殊級數法進行隱私預算分配，由定理2可得，每個子圖g的深度挖掘滿足εa-差分隱私。又由定義6可得，整個算法2滿足εa×|QS|=ε2-差分隱私保護。

證畢。

3.4 噪音添加階段

噪音添加階段是DP-TGM算法的最后一個階段，主要思想是對挖掘出的top-k頻繁子圖的真實支持度添加拉普拉斯噪聲進行擾動。

算法4：噪音添加算法Add-noise(QK，ε3)。

輸入：算法2得到的QK，隱私預算ε3。

輸出：加噪后的top-k子圖集合QK。

1.for subgraphGiinQK:

2.εi=ε3/k;

3.Nsup(Gi)=sup(Gi)+Laplace(εi);

4.end for

5.ReturnQK。

定理4：算法4滿足ε3-差分隱私。

證明：這里使用均分法將隱私預算均分為k份，QK中的每個頻繁子圖添加的噪音為Laplace(k/ε3)。算法4和算法2一樣使用均分法來分配隱私預算，所以同理可證，算法4滿足ε3-差分隱私。

證畢。

3.5 DP-TGM算法隱私性證明

定理5：DP-TGM算法滿足ε-差分隱私保護。

證明：DP-TGM算法將隱私預算分為三份，分別用于三個階段：預處理(ε1)、top-k子圖挖掘(ε2)、噪音添加(ε3)。該文設定隱私預算的分配比例ε1:ε2:ε3=1∶5∶4。由定理1可得，算法1滿足ε1-差分隱私，由定理3可得，算法2滿足ε2-差分隱私，由定理4可得，算法3滿足ε3-差分隱私。由定義6差分隱私的序列組合性可得，算法滿足(ε1+ε2+ε3)-差分隱私保護，而DP-FGM算法的整體隱私預算ε=ε1+ε2+ε3，所以DP-FGM算法滿足ε-差分隱私保護。

證畢。

4 實驗結果與分析

本節將通過對比實驗來驗證算法的數據可用性。實驗環境為 Inter(R) Core(TM) i5-8250U CPU @1.60 GHz，8.00 GB內存Windows10 64位操作系統。

實驗將在三個真實的圖數據集上進行測試，分別是NCI1、Protein和Reddit-multi。NCI1是抗非小細胞肺癌和卵巢癌細胞系活性篩選的化合物數據集，Protein是蛋白質分子結構數據集，Reddit-multi則是社交網絡數據集。表1展示了各數據集的具體特征，包括圖的個數(graph count)，平均節點數(avg-nodes)和平均邊數(avg-edges)。

表1 圖數據集信息

該文將DP-TGM算法與DP-tokP算法和Diff-FPM算法進行比對，實驗所涉及的代碼均由java語言實現。由于噪聲的加入，數據具有隨機性，實驗結果存在不確定性，因此采取多次試驗取平均值的方式來記錄結果。

4.1 度量指標

該文使用兩個度量標準：F1-Score和RE。F1-Score主要衡量挖掘的頻繁子圖結果的可用性，RE則用來衡量子圖支持度的準確性。F1-Score的比較結果使用條形圖展示，而RE的比較結果用折線圖展示。

定義11 F1-Score[16]：

(8)

其中，Accuracy表示精確率，Recall表示召回率。Accuracy=(Up∩Us)/Up，Recall=(Up∩Us)/Us，Up是在差分隱私下進行頻繁子圖挖掘的結果，Us則是頻繁子圖挖掘的準確結果。F1-Score將精確率和召回率綜合考量，取值區間為[0,1]，F1-Score的值越大，則代表數據效用越好。

定義12 RE(相對錯誤率)：

(9)

式中，Nsupv(i)(0≤i≤k-1)是結果集中第i個子圖的噪音支持度，Sup(i)則是第i個子圖的真實支持度。RE用來衡量挖掘到的頻繁子圖的支持度的錯誤率，取值區間為[0,∞]。RE的值與引入的噪音量大小相關，噪音越大，噪音支持度與真實支持度的差值越大，RE的值就越高，數據可用性就越差。所以，RE的值越小，算法的數據效用越高。

4.2 可用性隨k取值的變化

DP-TGM算法是進行top-k頻繁子圖挖掘的算法，k的大小將影響隱私預算的分配。實驗通過調整k的大小來對比三個算法的F1-Score和RE值。這里，統一設置隱私預算ε為1，k從30變化到150，間隔為30，在三個數據集上進行測試，結果如圖1～圖3所示。隨著k的變大，三個算法的F1-Score都在降低，而RE值在增大，說明隨著k增大，算法的數據效用在降低。而當k相同時，DP-TGM算法的F1-Score始終要比DP-tokP算法和Diff-FPM算法高，而RE要比它們低，驗證了DP-TGM算法的優越性。

圖1 數據集NCI1隨k變化時可用性變化情況

圖2 數據集Protein隨k變化時可用性變化情況

圖3 數據集Reddit-multi隨k變化時可用性變化情況

4.3 可用性隨隱私預算ε取值的變化

隱私預算ε的取值可以影響到噪聲的大小，而每個算法隱私預算的分配也不相同，所以ε的變化會影響挖掘結果的數據效用。這里統一設置k為50，ε從0.5變化到1.5，間隔為0.25，在NCI1和Protein兩個數據集上進行測試，實驗結果如圖4、圖5所示。

圖4 數據集NCI1隨ε變化時可用性變化情況

圖5 數據集Protein隨ε變化時可用性變化情況

隨著ε的增大，三種算法的F1-Score值都在增大，而RE值在減小，這是因為ε的增大，引入的噪音減小，提高了數據效用。而在ε從0.5變化到1.5的過程中，DP-TGM算法的F1-Score值始終最高，RE值始終最低，再次驗證了文中算法的優越性。

5 結束語

設計并實現了一個滿足差分隱私的top-k子圖挖掘算法DP-TGM，通過不斷地更新優先權隊列QK，將不滿足要求的子圖剔除，同時更新閾值，提高挖掘的效率。為了提高數據的可用性，使用均分法和特殊級數法進行隱私預算的分配，以更低的速度釋放隱私預算。同時，在不同規模的真實圖數據集上的測試成果也顯示了算法具有更高的數據可用性。為了提高挖掘性能和結果的準確性，在挖掘子圖的過程中浪費了一些隱私預算，因此下一步將研究如何減少隱私預算的浪費。