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

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

0 引 言

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

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

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

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

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

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

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

1 相關工作

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

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

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

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

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

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

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

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

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

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

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

2 理論基礎

2.1 差分隱私

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

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

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

(1)

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

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

(2)

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

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

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

A(D)=f(D)+

(3)

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

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

(4)

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

2.2 頻繁子圖挖掘

頻繁子圖挖掘是頻繁模式挖掘的問題之一，其任務是找出圖數(shù)據(jù)庫中頻繁出現(xiàn)的子圖結(jié)構(gòu)。

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

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

NSup(g)=Sup(g)+noise

(5)

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

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

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

3 DP-TGM算法

DP-TGM算法的挖掘?qū)ο笫菆D數(shù)據(jù)集中支持度排名前k的子圖，算法共分為三個階段：預處理階段、深度挖掘階段和噪音添加階段。

3.1 DP-TGM算法概述

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

算法1:DP-TGM算法。

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

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

3.2 預處理階段

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

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

輸入：圖數(shù)據(jù)集GD；隱私預算ε1。

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

1.θ=10；

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

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

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

5.end if

6.依據(jù)QK對數(shù)據(jù)集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)，遍歷數(shù)據(jù)集GD，挖掘出支持度大于閾值的頂點和邊，存入QK中。若是QK中的子圖個數(shù)大于k，則將支持度低的子圖移出隊列，依據(jù)QK進行剪枝。QS中放入QK中的頻繁邊，用來進行下一輪的拓展。最后將QK中的子圖添加上拉普拉斯噪音，更新閾值為QK中噪音支持度的最小值。

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

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

證畢。

3.3 深度挖掘階段

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

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

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

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

輸入：圖數(shù)據(jù)集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.初始化優(yōu)先權(quán)隊列Q；//支持度越高，則優(yōu)先級越高;

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;//算法結(jié)束

21.end while

22.returnQK。

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

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

(6)

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

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

(7)

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

證畢。

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

證明：算法3首先使用均分法將ε2分為εa=ε2/|QS|，QS中的每個子圖得到了εa的隱私預算。算法依次將QS中優(yōu)先級最高的子圖g移出隊列，進行深度挖掘，使用特殊級數(shù)法進行隱私預算分配，由定理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 實驗結(jié)果與分析

本節(jié)將通過對比實驗來驗證算法的數(shù)據(jù)可用性。實驗環(huán)境為 Inter(R) Core(TM) i5-8250U CPU @1.60 GHz，8.00 GB內(nèi)存Windows10 64位操作系統(tǒng)。

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

表1 圖數(shù)據(jù)集信息

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

4.1 度量指標

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

定義11 F1-Score[16]：

(8)

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

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

(9)

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

4.2 可用性隨k取值的變化

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

圖1 數(shù)據(jù)集NCI1隨k變化時可用性變化情況

圖2 數(shù)據(jù)集Protein隨k變化時可用性變化情況

圖3 數(shù)據(jù)集Reddit-multi隨k變化時可用性變化情況

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

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

圖4 數(shù)據(jù)集NCI1隨ε變化時可用性變化情況

圖5 數(shù)據(jù)集Protein隨ε變化時可用性變化情況

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

5 結(jié)束語

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