一種基于差分隱私的頻繁有權子圖挖掘算法

陶曉玉 寧 博 李冠宇

(大連海事大學信息科學技術學院 遼寧 大連 116026)

0 引 言

隨著信息網絡的發展，大量的網絡數據產生，如社交網絡、通信網絡和商業貿易網絡等。這些網絡數據一般采用圖來表示，圖中的節點可能表示的是個體及其屬性或是一個公司機構等，邊用來表示節點間存在一定的關系，其中，一些圖的邊上還帶有一定的權重值，這些權重值可能代表著公司之間的交易金額或是關系的親密程度等。圖中的這些頂點和邊可能包含著大量敏感信息，例如：個人的身份證號碼、電話號碼、銀行賬戶和交易金額等信息。一直以來，從圖數據集中挖掘頻繁子圖是圖數據分析的重要任務。挖掘頻繁子圖可以發現一些公共的子結構，從而為進一步的研究分析提供幫助。然而，當圖數據集中包含著敏感信息，直接發布挖掘到的頻繁子圖將會導致個人隱私的泄露。因此需要對頻繁子圖的挖掘過程采取保護措施。本文主要針對有權網絡圖的頻繁子圖挖掘過程中的隱私保護進行研究。

近年來，針對隱私保護方面的研究，已有許多匿名方法被提出。其中，Dwork等[1-2]提出的差分隱私保護方法是基于數據失真的一種方法，對隱私泄露風險有嚴格定量化的定義和證明且極大地保證了數據的可用性。在此定義下，對數據庫的計算處理結果對于具體某個記錄的變化是不敏感的，單個記錄在數據集中或者不在數據集中，都對計算結果的影響微乎其微。所以，一個記錄因其加入到數據集中所產生的隱私泄露風險被控制在極小的、可接受的范圍內，攻擊者無法通過觀察計算結果而獲取準確的個體信息。目前，差分隱私技術已被越來越多地應用于圖數據方面的研究，如社區發現、圖的節點和邊的保護、頻繁子圖挖掘。

目前，差分隱私技術應用到無權圖數據方面的保護工作已有很多且相對效果都比較好[3-5]。Xiao等[3]利用HRG( hierarchical random graph )模型將圖轉換成樹形結構，以便處理圖的復雜結構，并采用馬爾可夫蒙特卡羅(MCMC)方法對HRG模型空間進行采樣，同時滿足差分隱私。該方法降低了噪聲的產生，有效地保留了基本的網絡結構特性。Dong等[5]在Xiao等的工作基礎上做出了改進，考慮大規模的圖數據集的保護，基于分而治之的思想，算法為每個社區構建HRG，并將子級HRG合并為一個完整的HRG，從而消除了處理大型圖時原算法存在低效率的問題。但是無權圖的保護工作中的算法不能直接用來保護有權重圖，由于將權重考慮到圖中的復雜性，在有權圖數據方面的隱私保護工作中，大多數研究采用k-匿名的方法[6-8]來保護隱私。此外，也有很多嘗試采用差分隱私的方法保護權重，但在保護邊的權重的過程中，許多工作未考慮圖的結構保護。Li等[9]將圖中邊的權重序列轉化為未歸屬直方圖，進而采用差分隱私保護圖中權重信息。具體的操作是將社交網絡圖中有相同的邊權重的桶合并到一個組，進而減少噪聲的量，并采用k-indistinguishability方法保證差分隱私不孤立。最后，采用CI(Consistency Inference)保證最短路徑不改變。但這只考慮了圖中權重的隱私保護，沒有考慮圖中結構的保護。

另外，已有一些工作在頻繁子圖挖掘過程中采用差分隱私這一保護技術，進而保護頻繁子圖的隱私。Shen等[10]將頻繁圖模式挖掘算法與差分隱私的保證統一應用于MCMC的框架中，是針對無權重頻繁子圖挖掘的保護。同時，為了保證隱私性和效用性，提出了一個有效的近鄰計數技術。Cheng等[11]在Shen等基礎上，解決了輸出空間太大而導致挖掘結果不精確以及弱差分隱私保護的問題，提出了DFG算法。該算法主要分為兩個階段，在第一階段隱私地識別頻繁的子圖，并且在第二階段計算每個識別的頻繁子圖的噪聲支持，每個階段都有有效的方法被提出，整個算法滿足ε-差分隱私，很大程度地保證了數據效用性和隱私性。挖掘頻繁子圖的算法已有很多被提出，本文采用的gSpan算法[12]是基于圖的深度優先搜索的一種頻繁子圖挖掘算法。該算法將圖集中的每個圖映射到DFS碼(一個邊的序列)，圖中的每條邊采用五元組的形式表示，根據DFS碼構建詞典順序并制定規則選出最小DFS碼，從而篩選出頻繁子圖。

本文利用差分隱私這一嚴格隱私保護模型對有權頻繁子圖進行挖掘，同時保護邊的權重值和圖的結構。首先，對有權圖采用編碼方式，將邊的權重考慮到編碼中，構建詞典序列，并對編碼中的權重值添加Laplace噪聲進行數據干擾；在噪聲添加的過程中，合理地分配隱私預算。其次，在子圖挖掘過程中，同時采用差分隱私的Laplace機制和指數機制[1,13]，輸出滿足條件的擾動后的頻繁子圖集，并在理論上分析算法的隱私性。最后，在多個真實數據集集上驗證算法的效用性，并采用多個實驗指標與其他算法進行對比分析。

1 相關定義

1.1 差分隱私

差分隱私(Differential Privacy，DP)目前被廣泛地應用于推薦系統、基于位置的服務等領域。該模型不需要特殊的攻擊假設，不關心攻擊者具有的背景知識，并對隱私泄露風險給出了定量化分析。下面給出差分隱私的相關定義及性質。

定義1ε-差分隱私。設隨機算法M，Range(M)為算法M所有可能輸出結果的集合。對于任意兩個鄰近數據集D和D′以及Range(M)的任何子集S，若滿足Pr(M(D)∈S)≤Pr(M(D′)∈S)×exp(ε)，則稱算法M滿足ε-差分隱私。

其中，ε是隱私預算，用來控制概率分布的相似性，當ε越小時，exp(ε) 越接近于1，保護強度越大，擾動也就越多，因此，ε值的選取通常需要衡量信息安全性與數據可用性。

差分隱私主要有兩個實現機制：Laplace機制和指數機制[13]。

該機制通常用于數值型的保護，可以用到有權圖中權重值的擾動上，相當于是對權重添加一個符合Laplace函數的噪聲。

該機制通常用于非數值型的保護，如分類值或是一個結構。可以用來保護網絡圖數據的結構。在指數機制的實現過程中，最重要的是確定效用函數u，得分越高的結果越容易被選中。

差分隱私在使用的過程中最重要的兩個方面如下。① 隱私預算。決定了隱私保護強度，ε值越小，隱私保護水平越高。② 噪聲機制。決定了查詢準確性。

此外，差分隱私具有序列組合性和并行組合性兩種特性[1]，序列組合性強調隱私預算可以在方法的不同步驟進行分配，而并行組合性則是保證滿足差分隱私的算法在其數據集的不相交子集的隱私性。

1.2 頻繁子圖挖掘(Frequent Subgraph Mining,FSM)

無向有權圖可以表示為G=，其中，V是圖中節點的集合，E是邊的集合，W對應于圖中的邊的權重值。本文考慮的圖是無向、無自循環和無多個邊的圖。數據挖掘就是從圖數據集中發現一組公共的子結構，即子圖結構。下面給出圖的一些相關定義。

定義3如果圖G′的頂點集V′是V的子集，并且它的邊集E′是E的子集，則圖G′=(V′,E′)是另一個圖G=(V，E)的子圖，子圖關系記作G′∈sG。

定義4給定圖集GD，圖G的支持support為GD中G存在子圖同構的圖G′的個數。

定義5給定圖集GD，GD={G1,G2,…,Gn},最小支持為min_sup。若圖g是頻繁圖，當且僅當sup(g)≥min_sup。

定義6給定圖數據集GD和閾值T，頻繁子圖挖掘就是為了找到數據集GD中所有支持不小于T的頻繁子圖。

如圖1所示，圖數據集GD的大小為3，其中，G1是G2的子圖，若閾值T=2，則可以得到圖數據GD中的頻繁子圖是g。

圖1 頻繁子圖挖掘圖

2 基于差分隱私挖掘有權頻繁子圖

在頻繁子圖挖掘的過程中，大致包括的幾個環節是圖的合理表示→候選集的產生→候選集的修剪→篩選出頻繁子圖。適當的圖的表示，將有助于頻繁子圖的輸出。在對圖進行統一編碼之后，會產生對應的候選集，通常候選集是非常大的，而其中的頻繁子圖所占的比例是很小的，因此，需要對產生的候選集進行修剪，以減少搜索空間，再對子圖進行支持計算并判斷，輸出頻繁子圖集。

2.1 網絡圖中的權重保護

有權網絡圖中邊的權重通常包含著重要的信息，這些權重值可能代表著交易的金額、朋友關系的親密程度等。例如，在對社交網絡進行分析時，通常把社交網絡可以看成一個圖的結構，圖中節點表示個體，邊表示著個體之間的關系，權重值可能是具體的隱私信息或是用戶之間的關系程度等。當這些權重值攜帶著敏感信息，若不在圖發布之前對邊的權重值進行處理則很容易造成用戶的個人信息暴露，因而保護圖中邊的權重的隱私是很有必要的。

2.1.1圖的編碼算法EDFS(ExtendedDFSAlgorithm)

首先，本文是在擴展gSpan算法[12]的基礎上表示圖的，把權重值考慮到編碼中，將擴展的算法稱之為EDFS。對同一圖進行深度優先搜索(DFS)時，可以得到多個不同結果，即可以有多個同構的DFS樹，例如，圖2中的(b)-(d)與(a)是同構的。

圖2 深度優先搜索樹圖

對圖中的頂點深度優先搜索會形成一個線性順序，根據查詢時間先后來設置下標。i

假設e1=(i1,j1)，e2=(i2,j2)。1) 若i1=i2且j1

那么就可以根據深度優先搜索的時間先后對圖進行DFS編碼。EDFS算法在構造DFS編碼的過程中，將圖中的邊表示成六元組的形式，即，其中，i、j是標號，Wij是邊的權重，li、l(i,j)、lj是頂點和邊的標簽，i可以表示成 <0，1，3，X，Y>。DFS碼的一個定義如下：

另外，生殖醫學中心中的其他潔凈輔助用房（冷凍室、工作室、潔凈走廊等）可按Ⅳ級潔凈用房設計，局部集中送風。所有裝修材料均不應有對工作造成不良影響的化學源和放射源，不得使用有刺激性氣味的設備和材料。取卵室應按Ⅱ級潔凈用房設計，并采用局部集中送風；以上噪聲均應不大于50dB（A）。

給定一個圖G的DFS樹，可以基于

因此，可以得到的DFS碼如表1所示。

表1 DFS碼

可以看出，同一個圖可以有多個DFS碼。因此，對DFS碼構造詞典順序。EDFS算法在構造詞典順序時應遵循的規則如下：假設當前有兩個邊e1=(vi,vj,Wij,l(vi),l(vj))，e2=(vx,vy,Wxy,l(vx),l(y))。 若e1

(1) (vi,vj)<(vx,vy)。

(2) (vi,vj)=(vx,vy)且Wij>Wxy。

(3) (vi,vj)=(vx,vy)且Wij=Wxy且(l(vi),l(vj))<(l(vx),l(vj))

若是有邊標簽的圖，則條件3為(vi,vj)=(vx,vy)且Wij=Wxy且(l(vi),l(i,j),l(vj))<(l(vx),l(x,y),l(vj))。

考慮到權重值通常表示著關系的親密程度或是交易金額，權重越大的應該被選擇出來，因而定義權重越大的邊越早被選擇出來。根據上述建立的詞典順序可以得到最小的DFS碼是圖2(c)對應的DFS碼，這樣每一個圖都可以對應一個唯一的最小DFS碼。

2.1.2邊的權重保護算法Diff-WS

算法1Diff-WS

輸入：邊的權重序列集WS，隱私預算ε1；每個圖中的邊數為Ei，圖集GD，大小為N，總邊數為E

輸出：擾動后的邊的權重序列集WS’

1：fori=1 toNdo

2： for eachWSi∈WSdo

3： forj=1 toM

/*對每個序列WSi中的每個權重wj添加Laplace噪聲*/

5： if (w′j<0) then

//對擾動后的權重判斷

6: back to Line 4;

7：WSi′←w′j

//將每個擾動后的權重w′j存入到WSi′

8: end for

9： end for

10:end for

11: returnWS′

2.1.3隱私效用分析

噪聲添加的數量將會取決于隱私預算的分配以及敏感度的計算。由于對數據集中的權重添加噪聲的過程中是將每個圖中的邊的權重看成一個個序列，即一個大小為N的圖集對應N個權重序列。在此過程中每一個序列依次獨立進行處理，所以，敏感度依然是ΔQ=Wmax-Wmin，Wmax是最大的權重值，Wmin是最小的權重值。

2.2 頻繁有權子圖挖掘

圖集GD中的每個大小為i的圖，記作i-graph。i表示圖中含有邊的數量。頻繁子圖的挖掘過程是將1-graph作為候選集并從中篩選出滿足閾值判定條件的候選集，重復此過程直到篩選出最理想的符合條件的頻繁子圖集。差分隱私在此過程中有兩處被用到，一是閾值條件篩選候選子圖時利用Laplace機制擾動候選子圖的支持，二是在噪聲閾值條件篩選出的候選子圖集的基礎上，利用指數機制再篩選，從而保證數據效應性和隱私性。具體過程如算法2所示。

算法2Subgraph_Mining

輸入： i-subgraph候選集Ci；隱私預算ε2、ε3；閾值T；頻繁i-graph的數量ni

輸出：Frequenti-subgraphFi

1：ifs≠min_DFS (s) then

//先判斷子圖s是否滿足最小DFS碼條件

2：return

3：FS←FS∪{s}

4: forj=1 tonido

for eachs∈Cido

5： enumerates∈G?GDand count its children

6： for eachc，ciss’child with one edge growth in GD do

8：Ci′←c

9： end if

10： end for

11： ifCi′≠ then

13： RemovegjfromCi

14：Fi←gj

15： Subgraph_Mining(GD，ε2，ε3，FG，s)

16： end if

17： end for

18：returnFi

算法2用來挖掘頻繁有權子圖。首先，判斷子圖的編碼是否為最小編碼，若是滿足最小碼條件，則找出每個子圖的孩子(child)，以每次增長一條邊的形式生成child。對子圖的孩子的支持添加Laplace機制形成噪聲支持，由于相差只有一個圖的圖數據集，則添加Laplace噪聲的敏感度為1，分配的隱私預算為ε2。隨后，判斷該噪聲支持是否滿足閾值條件，不斷地重復子圖挖掘過程。最后，篩選出的子圖滿足差分隱私指數機制。

2.3 Diff-Wfsm 算法

算法3是本文提出的Diff-Wfsm算法，用于在頻繁有權子圖的挖掘過程中保護隱私。

算法3Diff-Wfsm

輸入：圖數據集GD，閾值T，隱私預算(ε1,ε2,ε3ε1+ε2+ε3≤ε)

輸出：擾動后的頻繁子圖集合FS

1: Diff-WS(WS,ε1，WS′) /*邊的權重進行擾動*/

2: sort labels of the vertices and edges in GD by their frequency

/*對圖集進行預處理操作*/

3：remove infrequent vertices and edges

/*移除非頻繁節點和非頻繁邊*/

4：relabel the remaining vertices and edges in descending frequency forGD

5: sortFS1 in DFS lexicographic order

6：FS←FS1

7：for each edgee∈FS1 do

8： initialize 1-edge graphswithe

9： Subgraph_Mining(GD，ε2，ε3，FS，s)

/*頻繁子圖挖掘過程*/

10：GD←GD-e

11: if |GD|

12: break

13: end if

14: end for

算法3首先對圖數據集的每個圖中的邊權重進行擾動，也就是2.1.2節中的 Diff-WS 算法，根據每個圖中的邊數不同，分配不同大小的隱私預算，避免了隱私預算分配一致的問題。處理完權重后，繼續對圖進行預處理和編碼操作，根據頂點和邊的頻繁度，移除非頻繁節點和非頻繁邊，再對剩下的邊和頂點以頻繁度由大到小的順序重新標簽。最后對篩選出的1-edge圖進行頻繁子圖挖掘，在挖掘過程中先對候選集的支持添加Laplace噪聲，再對篩選出的噪聲候選子圖集采用指數機制，篩選出相對理想的頻繁子圖集，也就是2.2節中的 Subgraph_Mining算法，直到不滿足閾值條件時算法結束。

2.4 隱私保護分析

3 實驗與結果分析

本節將結合實驗結果來分析和評估算法的效用。在不同真實數據集下，采用RE和F1-score這兩個效用指標評估隱私預算大小、閾值大小對算法的影響。實驗結果顯示本文提出的方法是有效的，隱私預算添加得越多，數據效用越高，誤差越小。閾值設置的越大，數據效用越高，即F1-score值越大；閾值越小，誤差越大，即RE越大。

3.1 實驗設置

算法在1.60 GHz CPU，內存為4 GB RAM，Windows7 64位操作系統的PC中采用Java語言實現。

實驗中采用三個數據集驗證算法的有效性，如表2所示。Grd[14]是含有340個圖、9 317條邊的圖集，權重在0到5之間，邊的分布相對不均勻，最小的邊數為7條，最大邊數達到179條，IBM[15]中邊的分布相對均勻，平均邊數為21，權重值在0到10之間。EIB是在原有非權重數據集的基礎上，利用正態分布隨機產生的權重值，權重值范圍在0到50之間。閾值Threshold和隱私預算ε的選擇根據實際情況決定，通常ε的設置不會太大，若ε設置過大，保護工作基本無效。Threshold設置過大，可能導致挖掘結果只有一個或零個，是沒有實際意義的。因此為了更好地觀察兩個參數對算法效果的影響，實驗中隱私預算ε取0到30之間，按照ε1∶ε2∶ε3=5∶3∶2的比例分配，閾值Threshold取值為0.1～0.6。

表2 實驗數據集

本文采用RE和F1-score兩個評估指標來檢驗算法的性能，分別定義如下：

RE (相對誤差)是用來衡量挖掘結果的可信度，如式(1)所示。

(1)

F1-score是用來衡量挖掘結果的數據可用性，如式(2)所示。

(2)

3.2 結果分析

圖3顯示對三個數據集的權重序列添加不同隱私預算的噪聲后權重序列誤差的變化。隱私預算ε 越大，權重序列誤差WSE就越小，保護程度就越高。噪聲的添加是根據Laplace函數產生的，具有一定的隨機性，實驗中圖集中的邊數越多，保護程度越高，擾動的結果由數據集中邊的分布、隱私預算的大小決定的。

圖3 Grd：不同數據集下邊權重的WSE變化

由于當前還沒有與挖掘有權頻繁子圖的相關算法，所以實驗中在挖掘過程中只采用Laplace機制的算法作為實驗對比，記作Basic算法。

如圖4-圖6所示，隨著閾值Threshold的增加，F1-score呈上升趨勢，這是因為閾值設置得越大，可滿足的頻繁子圖的候選就越少，挖到真實的子圖的可能性越大，因而數據效用就越高，即F-score越大；在三個數據集上，本文算法Diff-Wfsm都優于Basic算法，F1-score至少可以達到0.7以上，最高可以達到0.9，而Basic算法一般都是在0.6～0.7，總體來看都是Diff-Wfsm算法相對較好。

圖4 Grd：不同閾值下F1-score的變化

圖5 IBM：不同閾值下F1-score的變化

圖6 EIB：不同閾值下F1-score的變化

如圖7-圖9所示，在三個數據集上，RE都是隨著閾值的增加而減少，當閾值選取很小時，可滿足條件的頻繁子圖個數就越大，那么可能存在的非真實的頻繁子圖就越多，這樣就會導致相對誤差越大。Diff-Wfsm算法一般最多不超過0.2，Basic算法甚至要達到0.3，而且最低也一般在0.1左右，而Diff-Wfsm算法可以達到0.02左右。

圖7 Grd：不同閾值下RE的變化

圖8 IBM：不同閾值下RE的變化

圖9 EIB：不同閾值下RE的變化

圖10-圖12中，受隱私預算的影響，F1-score依然在不斷增加，Diff-Wfsm算法可以基本上保持在0.8以上，這是因為隱私預算添加得越多，保護程度就越低，也就是干擾影響越少，因而數據效用性就越高。另外，Diff-Wfsm算法在子圖挖掘過程中對候選采用指數機制再篩選，這樣就保證選出來的頻繁子圖集的數據效用性更大，即F1-score更大。

圖10 Grd：不同隱私預算下F1-score的變化

圖11 IBM：不同隱私預算下F1-score的變化

圖12 EIB：不同隱私預算下F1-score的變化

圖13-圖15中，隨著隱私預算的不斷增加，干擾影響就越大，RE在減少，Diff-Wfsm算法相對穩定，總體上都要優于Basic算法，尤其在IBM、EIB中，Diff-Wfsm算法的RE基本上都在0.1之下，誤差是很小的。

圖13 Grd：不同隱私預算下RE的變化

圖14 IBM：不同隱私預算下RE的變化

圖15 EIB：不同隱私預算下RE的變化

圖16是算法在三個數據集上挖掘頻繁子圖所需要的時間。閾值的設置影響著所需要的時間，總體來看，閾值越大，需要的時間越小，尤其在數據集EIB上較為明顯。主要是因為閾值設置越大，可以滿足條件的頻繁子圖就越少，需要花費的挖掘時間也就越少。在數據集IBM中用的時間較多，可以看出圖越復雜，花費的時間就越多。

圖16 不同數據集中的運行時間

因此，通過以上多個實驗驗證可以看出，本文算法Diff-Wfsm無論是F1-score還是RE指標下，相對效果都要更好，不僅保護了頻繁有權子圖的隱私，而且提高了頻繁有權子圖挖掘結果的效用性。其次，隱私預算大小選取和閾值大小的設定都對實驗結果有著很大影響，具體要根據實際的需求來設定。另外，在三個分布略有不同的數據集上，本文算法的相對效用都很高。

4 結 語

本文采用差分隱私的保護技術挖掘頻繁有權子圖，提出了Diff-Wfsm算法，同時保證了頻繁子圖的結構與邊權重的隱私。先是擴展原有的頻繁子圖挖掘算法，把邊的權重值考慮到DFS編碼中，即EDFS算法，并在頻繁子圖挖掘之前對圖的權重值干擾，為了保證添加噪聲不一致，采用了按邊分配預算的策略，即Diff-WS算法。挖掘過程中同時采用Laplace機制和指數機制來提高挖掘結果的隱私性和效用性，先對候選子圖的支持添加Laplace噪聲干擾，再采用指數機制進一步篩選理想的頻繁子圖集。最后，在不同的真實數據集進行實驗驗證，實驗結果證明本文方法是可行和有效的。未來研究方向是進一步提高算法的效率和挖掘結果的精確度，并減少噪聲量的添加，同時爭取擴展到整個有權網絡圖的隱私保護。