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

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

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

0 引 言

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

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

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

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

2 理論基礎(chǔ)

2.1 差分隱私

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

定義2ε-差分隱私。給定兩個(gè)近鄰數(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的隨機(jī)屬性確定。參數(shù)ε是隱私保護(hù)預(yù)算，ε值與隱私保護(hù)程度成反比，ε越小，兩個(gè)近鄰數(shù)據(jù)集的相同輸出的概率越接近，隱私保護(hù)的程度越高。

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

(2)

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

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

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

A(D)=f(D)+

(3)

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

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

(4)

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

2.2 頻繁子圖挖掘

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

定義7 支持度。子圖g的支持度指的是圖數(shù)據(jù)庫中包含子圖g的記錄的個(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的子圖，算法共分為三個(gè)階段：預(yù)處理階段、深度挖掘階段和噪音添加階段。

3.1 DP-TGM算法概述

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

算法1:DP-TGM算法。

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

下面將對(duì)三個(gè)階段展開講解。

3.2 預(yù)處理階段

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

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

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

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

1.θ=10；

2.挖掘出頻繁的點(diǎn)和邊，并存入QK中；

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

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

5.end if

6.依據(jù)QK對(duì)數(shù)據(jù)集GD剪枝；

7.將QK中的頻繁邊復(fù)制并存入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是對(duì)預(yù)處理階段的具體描述，首先設(shè)置一個(gè)較低的閾值θ(例如θ=10)，遍歷數(shù)據(jù)集GD，挖掘出支持度大于閾值的頂點(diǎn)和邊，存入QK中。若是QK中的子圖個(gè)數(shù)大于k，則將支持度低的子圖移出隊(duì)列，依據(jù)QK進(jìn)行剪枝。QS中放入QK中的頻繁邊，用來進(jìn)行下一輪的拓展。最后將QK中的子圖添加上拉普拉斯噪音，更新閾值為QK中噪音支持度的最小值。

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

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

證畢。

3.3 深度挖掘階段

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

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

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

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

輸入：圖數(shù)據(jù)集GD；隱私預(yù)算ε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)隊(duì)列Q；//支持度越高，則優(yōu)先級(jí)越高;

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

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

(6)

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

證明：因?yàn)槿我庖淮坞[私預(yù)算分配量εi>0，(i∈N+)，有限次(n<∞)分配的隱私預(yù)算分配量之和為：

(7)

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

證畢。

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

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

證畢。

3.4 噪音添加階段

噪音添加階段是DP-TGM算法的最后一個(gè)階段，主要思想是對(duì)挖掘出的top-k頻繁子圖的真實(shí)支持度添加拉普拉斯噪聲進(jìn)行擾動(dòng)。

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

輸入：算法2得到的QK，隱私預(yù)算ε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-差分隱私。

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

證畢。

3.5 DP-TGM算法隱私性證明

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

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

證畢。

4 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

4.1 度量指標(biāo)

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

定義11 F1-Score[16]：

(8)

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

定義12 RE(相對(duì)錯(cuò)誤率)：

(9)

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

4.2 可用性隨k取值的變化

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

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

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

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

4.3 可用性隨隱私預(yù)算ε取值的變化

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

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

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

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

5 結(jié)束語

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