點差分隱私下圖數據的度直方圖發布方法

張宇軒 魏江宏 李 霽 劉文芬 胡學先

1(數學工程與先進計算國家重點實驗室(中國人民解放軍戰略支援部隊信息工程大學) 鄭州 450001)2 (廣西密碼學與信息安全重點實驗室(桂林電子科技大學) 廣西桂林 541004) (bigzhangq@163.com)

隨著互聯網和信息技術的飛速發展，許多組織機構搜集的個人數據規模急劇增長，隨之而來的用戶隱私保護問題變得日益重要.對這些搜集的數據進行深入挖掘和分析后所能得到的潛在社會效益和經濟價值，如精準醫療、智慧城市、廣告投放等，又驅使這些組織機構傾向于發布關于這些搜集數據的統計信息.另一方面，在隱私保護下的數據分析領域，其主要目標是安全地發布關于數據集的統計信息，同時又不會泄露數據集中所涉及用戶的隱私信息，如醫療數據中的病人基本信息、位置數據中的用戶運動軌跡等.顯然，發布數據集中數據分布的有用信息和保護數據集中的用戶隱私這2個目標是相沖突的，如何在這兩者之間形成折衷就成了一個十分具有挑戰性的問題，而差分隱私技術[1]被認為是解決該問題最為理想的方案之一，可以保證相鄰數據集上查詢結果的分布很接近.

圖數據作為一種典型的數據類型，隨著社交網絡、推薦系統、協作網絡等信息系統的廣泛使用而變得越發常見，如何在保證用戶隱私不被泄露的前提下發布這些數據也逐漸受到了學者的關注.早期通用的方法主要是對圖數據進行簡單的匿名化處理來實現用戶隱私的保護，如用無意義的字符表示圖中節點、刪除/添加某些邊等等.但是，對于按照這種匿名化方法處理后的圖數據，利用主動攻擊和被動攻擊[2]仍能恢復出原始圖中的節點信息和節點之間邊的關系，進而導致用戶敏感信息泄露.2009年Hay等人[3]首次利用差分隱私技術來實現圖數據的安全發布，并提出了差分隱私在圖數據發布領域的2種變體，即邊差分隱私和點差分隱私.

在邊差分隱私中，2個相鄰圖僅相差1條邊，而在點差分隱私中，2個相鄰圖相差1個節點以及與此節點相連的所有邊.對于一個節點數目為|V|=n的圖G=(V,E)(其中V是所有節點的集合、E為所有邊的集合)，刪除1條邊只影響這條邊上2個節點度的變化，而刪除1個節點在最壞情況下會導致n-1條邊被刪除.因此，圖數據中的點差分隱私比邊差分隱私更難滿足，但卻能提供更高強度的隱私保護.

度分布是圖的一種重要統計特性，也是圖數據發布過程中的保護重點.如何在點差分隱私約束下實現圖的度分布發布在近年來得到了廣泛關注，其主要目標是要在滿足點差分隱私的條件下給出一種盡可能接近圖的度的真實分布的近似分布.目前，解決該問題的一種主要技術是將原始圖投影到1個節點度數不超過最大值θ的壓縮圖，以此來降低度發布過程中的敏感度，而這其中的關鍵又在于如何在投影過程中盡可能多地保留原始圖的信息.

在TCC 2013上，Kasiviswanathan等人[4]提出利用截斷(truncation, T)的方法對原始圖進行投影，即除去原始圖中所有度大于給定門限值θ的節點.這種方法雖可降低敏感度，但卻刪除了許多本沒必要刪除的邊，損失了原始圖中大量的有效信息.Blocki等人[5]考慮了通過邊移除(edge-removal, ER)的方法來降低敏感度，即任意選擇一個邊序列作為刪邊的次序，當邊的2個頂點存在deg(v)>θ的情況時刪除此邊，否則保留此邊，最后對保留的邊組成的圖的度分布進行差分隱私發布.Raskhodnikova和Smith[6]基于指數機制，利用流圖的方法將圖的度分布映射到一個直方圖，但卻仍具有較高的敏感度6θ.在SIGMOD 2016上，Day等人[7]提出了一種加邊機制πθ來降低敏感度，即首先對原始圖的邊進行穩定排序(如字典序)，然后刪除原圖中所有的邊，只保留節點，再按照穩定排序添加邊，當所添加邊的2頂點存在deg(v)>θ的情況時跳過此邊，最后當所有邊被遍歷完后對所得到的重構圖的度分布進行差分隱私發布.但是，邊排序的不確定性導致Day等人[7]提出的方法仍不能最大程度地保留原始圖的邊信息.

為進一步降低點差分隱私約束下圖的度分布發布過程中的敏感度，本文在現有幾種投影方法的基礎上提出了一種新的投影方法，并基于此給出了2種點差分約束下圖的度分布的直方圖發布機制.具體而言，本文的主要貢獻包括3個方面：

1) 提出了一種基于度排序的邊移除(sequence edge-removal, SER)投影方法，通過依節點度的大小刪除與該節點相連的邊，最終將節點度限制在給定的門限值內.相比已有方法，該方法在降低敏感度的同時，保留了原始圖中更多的邊，減小了投影圖和原始圖之間的誤差.

2) 基于SER投影方法提出了2種度分布的直方圖發布機制，即SER-(θ,Ω)-直方圖發布和SER-累積直方圖發布，并在理論上證明了這2種度分布發布機制滿足點差分隱私的定義.

3) 不同數據集上的仿真測試結果表明，相比已有的點差分隱私約束下圖的度分布發布機制，本文提出的基于SER投影方法的度分布直方圖發布機制在提供同等隱私保護水平的條件下，更好地刻畫了真實數據的度分布，提高了發布數據的可用性.

1 相關工作

差分隱私使用擾動技術對數據集或者查詢結果添加隨機噪聲，使得數據或查詢結果失真，但又保持了數據整體良好的統計特性和可用性，以便后續的數據挖掘和發布.具體而言，令X是需要發布統計信息的數據集，f是查詢函數，則ε-差分隱私機制就給出一個擾動的輸出f(X)+Y，而不是直接輸出真實答案f(X)，這里面Y就是所添加的噪聲.

自2006年Dwork[1]提出差分隱私的概念以來，由于其嚴謹的數學理論保證和可證明隱私安全性，這種隱私保護技術得到了廣泛的認可和關注.相較傳統的隱私保護模型(如k-anonymity[8],l-diversity[9]等)需要對攻擊者的背景知識和攻擊模型給出特定的假設，差分隱私不依賴攻擊者的特定背景知識，并且可以提供可量化的隱私保證.近年來，關于差分隱私技術的理論研究[10-13]取得了長足進展，已逐步應用到了數據分析和挖掘的各領域.

1.1 差分隱私約束下的圖數據發布

差分隱私技術在圖數據發布領域的應用有2種變體，即邊差分隱私和點差分隱私.

在圖的邊差分隱私中，2個相鄰圖僅相差1條邊.Nism等人[14]為降低查詢輸出中的噪聲，提出了局部敏感度的概念和抽取聚合框架，并應用其解決了邊差分隱私約束下圖中三角形的計數問題;Rastogi等人[15]通過引入Bayesian攻擊者，將原有邊差分隱私的定義進行了削弱，提出了邊差分隱私定義的變體——邊對抗隱私(edge adversarial privacy)，并基于此給出了可對任何子圖進行計數查詢的通用算法;Karwa等人[16]進一步對Nism等人[14]的工作進行了擴展，即對圖中的k-stars子圖計數實現了ε-差分隱私，對k-triangles子圖計數實現了(ε,δ)-差分隱私;Zhang等人[17]提出了用指數機制實現邊差分隱私約束下的子圖計數的階梯框架，并在其中給出了定義查詢函數含噪輸出的概率分布的方法.

在圖的點差分隱私中，2個相鄰圖相差1個節點以及與此節點相連的所有邊.鑒于許多針對圖數據的查詢函數在(最大)度θ較小的圖Gθ上具有較低的敏感度，因此一般通過將圖G轉換為度上界為θ的圖Gθ來實現節點差分隱私[4-5]，即將圖G中度高于θ的節點刪除.Chen和Zhou[18]針對節點差分隱私提出了一種迭代機制.給定圖G和實值函數f，他們定義了一個具有遞歸單調性質的實值函數序列0=f0(G)≤f1(G)≤…≤fm(G)=f(G)，再利用這種遞歸方法實現節點差分隱私約束下的任何類型子圖的計數.但是，構造這樣的函數序列fi(G)通常是NP困難的，因此如何高效地實現這種機制仍然是一個挑戰.

1.2 差分隱私約束下的直方圖發布

將數據以直方圖的形式表示后能夠顯著降低查詢函數的敏感度，為數據發布帶來很大便利[19].對于一個具有N條記錄的直方圖，差分隱私機制可用來保護每條記錄的頻率.

為減少直方圖中添加過多噪聲所帶來的誤差，Xu等人[20]利用最小化查詢函數集的均方差的方法給出了2種分割策略.Qardaji等人[21]考慮了直方圖上的范圍查詢函數，以一種分層的方式分割屬性值，并將屬性值范圍分配到一個樹上.Hay等人[22]定義了約束推理來調整查詢函數的輸出，并提出了2種具體的一致性約束.Lin和Kifer[23]將有序直方圖集合看作1個Markov鏈，基于Bayesian決策理論給出了一個新的隱私保護的排序直方圖問題的估計算法.張嘯劍等人[24]利用Markov鏈蒙特卡洛方法中Metropolis-Hastings技術與指數機制，提出了一種有效的排序方法，并對排序后的直方圖，給出了一種基于懶散分組下界的自適應貪心聚類方法，進一步減少了發布后直方圖中的誤差.Lee等人[25]將直方圖中對加噪數據的后處理過程抽象為帶約束的極大似然估計問題，并給出了一種快速、通用的解決方法.

2 基礎知識

本文主要考慮邊和節點均不帶標簽和權重的無向圖G=(V,E)，并用deg(i)表示節點i的度，hist(G)表示圖G的度直方圖.

2.1 差分隱私基本概念

差分隱私技術的思想源自一個很簡單的觀察：對于給定的包含個體U的數據集S，進行任何查詢操作f(例如計數、求和、平均值等)后所得到的結果為f(S)，如果將U的信息從S中移除，查詢結果仍然為f(S)或與f(S)十分接近，就可以認為S沒有額外地泄漏U的信息.而差分隱私技術就是要保證無論個體數據在或不在數據集中，對最終的查詢結果都沒有顯著影響.基于這種思想，ε-差分隱私的嚴格定義如下：

定義1[1].ε-差分隱私.若隨機算法K對任意一對相鄰數據集D,D′及任意輸出S?range(K)均滿足：

Pr[K(D)∈S]≤exp(ε)×Pr[K(D′)∈S]，

則稱算法K滿足ε-差分隱私.

在定義1中，相鄰數據集D和D′是指這2個數據集僅相差1條數據記錄，即|DD′|=1，并用D?D′表示這種相鄰關系.可以看出，差分隱私的嚴格數學定義保證了無論數據樣本是否存在于數據集D中，算法輸出的概率分布幾乎不變，而隱私系數ε的大小則反映了隱私保護程度的強弱，即ε的值越小，算法在相鄰數據集上的輸出的概率分布就越相近，提供更高強度的隱私保護，同時算法輸出的可用性也會越低.

2.2 噪聲機制

噪聲機制是實現差分隱私的主要技術，即在算法輸出中加入一定量的噪聲，而所添加噪聲的多少依賴于具體的噪聲機制和查詢函數的全局敏感度.Dwork等人[26]提出的Laplace機制是目前應用最廣泛的差分隱私機制，其通過向算法輸出中添加Laplace噪聲實現差分隱私.

定義2[26]. 全局敏感度.對于任意1個實值查詢函數f和相鄰數據集D,D′，查詢函數f的全局敏感度定義為

定義3[26]. Laplace機制.對于給定的數據集D和實值查詢函數f，令Δf為f在數據集D上的全局敏感度，則隨機算法K:K(D)=f(D)+Y滿足ε-差分隱私，其中Y～Lap(Δfε)是加入的隨機噪聲量，服從尺度參數值為b=Δfε的Laplace分布.

在定義3中，Laplace機制的概率密度函數為

Laplace機制通過添加Laplace噪聲實現差分隱私，要求查詢函數f的輸出必須是實數，這在一定程度上限制了其應用.為此，Mcsherry和Talwar[27]提出了指數機制，采用滿足特定分布的隨機抽樣來代替添加噪聲，以此來實現差分隱私，從而使得指數機制具有更加廣泛的應用范圍.

粗略來講，指數機制定義了效用函數q，使得每一種輸出方案都對應著1個由q刻畫的效用函數值，而效用函數值最大的輸出方案有更大的概率被采用.

定義4[27]. 指數機制.對于給定的數據集D，令q是評估數據集D上所有輸出方案的效用函數，如果算法K滿足輸出為r的概率與exp(εq(D,r)2Δq)呈線性關系，則算法K滿足ε-差分隱私，其中Δq為效用函數q的敏感度:

2.3 差分隱私的組合性質

對于一個復雜且困難的隱私保護問題，應根據數據集自身特性多次、分步驟地使用差分隱私機制，進而使得問題得到有效解決，但是總的隱私預算ε卻是有限的.因此，為了將整體隱私預算控制在ε內，需要對整個過程的每步合理地分配隱私預算，而這就需要使用差分隱私機制的2個組合性質：

2.4 度量方法

2個度分布之間的KS-距離從另一個角度刻畫了它們的接近度.對于度分布D和D′,它們之間的KS-距離定義為

其中，CDFD(i)為分布D上度為i的累積分布函數值.

3 基于度排序的邊移除投影方法

為降低度分布發布過程中的敏感度，提高發布后數據的可用性，本節提出一種新的圖投影方法，即基于度排序的邊移除投影方法(SER).粗略來講，該方法按照度的大小依次刪除圖G=(V,E)中與度數較大的節點相連的邊，最終將圖中每個節點的度限制到給定的門限值θ之內，同時又使得G中原有的邊能最大程度地保留，為差分隱私機制在壓縮圖中的應用提供基礎.SER投影方法的細節以算法的形式給出：

算法1. 基于度排序的邊移除算法.

輸入：圖G(V,E)、度限制θ；

輸出：限制圖SERθ(G).

①sorted_l；*計算deg(i),按從大到小排序[i,deg(i)]*

② while maxdeg(i)>θdo

③sort_list；*找i的所有相鄰節點j按deg(j)從大到小排序[j,deg(j)]*

④ whiledeg(i)>θdo

⑤deg(i)=deg(i)-1；

⑥deg(j)=deg(j)-1；*j遍歷Sort_list，直到deg(i) =θ*

⑦ end while

⑧sorted_l；*對sorted_l按deg(i)從大到小重排序*

⑨ end while

⑩ returnGθ(V,Eθ).

該算法首先計算圖G=(V,E)中所有節點的度并按照從大到小排序；然后找出度最大的節點i，將其相鄰節點按度從大到小進行排序，并按照此序列對與節點i相連的邊進行刪邊處理，直到deg(i)=θ時結束本次運算；對所有節點按照度從大到小進行重新排序，重復進行上述操作，直至所有節點都滿足條件，結束算法.

為了更直觀地說明算法1的流程，圖1給出了相關3種圖投影方法的例子,門限值θ=2，其中ER使用的邊排序為隨機序列，我們設邊排序為：10,9,8,7,6,5,4,3,2,1；πθ使用的邊序列為字典序：1,2,3,4,5,6,7,8,9,10.可以看出，使用文獻[5]中的ER方法時，我們按照假設的隨機邊序列進行減邊，當存在構成邊的頂點的度大于θ時，我們刪除此邊，遍歷邊序列，我們可知最后能保留4條邊；使用文獻[7]中的πθ方法時，我們首先刪除所有的邊只保留節點，然后按照邊序列進行加邊，當存在構成邊的頂點的度大于θ時，我們跳過此邊，遍歷邊序列，我們可知最后能保留5條邊；而使用我們提出的SER投影方法時，首先對節點按照度大小進行排序，找出度最大的節點d，然后再對d的相鄰節點進行排序，當deg(d)>θ時，對d按照相鄰節點序列進行刪邊，直到deg(d)=θ時，結束此次計算，并對節點按照度大小再次進行排序，依照上述方法計算，直到所有節點的度都小于等于θ時，結束算法.通過SER投影方法可知，最后能保留6條邊.

Fig. 1 ER,πθ, SER method example圖1 ER,πθ,SER方法舉例

從圖1簡單例子可以看出，ER方法對要刪除的邊進行隨機排序，這雖然保證了算法的運行效率，但卻損失了很多原始圖的邊信息；πθ這種方法從形式上看似是在增加邊，但其本質仍還是刪除多余的邊，進而把圖中節點的度限制在給定的門限值內，同樣沒有對要刪除的邊做一定規則的排序；而我們提出的SER投影方法，規定了邊的排序規則，在限制度的前提下，更多的保留了原始圖中的邊，減小了投影圖和原始圖之間的誤差，從而提高了差分隱私保護后的數據可用性.

事實上，無論采取何種投影方法，最終目的都是要使得圖1中所有節點的度小于給定的門限值θ.基于此，我們可以將圖數據中的節點簡單地分成2類，即節點度deg>θ和deg≤θ.圖2給出了這2類節點在圖數據中的所有連接方式，在圖2中邊依據其頂點度與θ之間的大小關系也相應地分為Ⅰ,Ⅱ,Ⅲ 三類.為了盡可能多地保留原始圖中的邊，我們希望在降低節點度的過程中所刪除的全都是Ⅰ類邊.但是，實際應用中的圖數據很難滿足這種理想情況，此時我們就需要去刪除Ⅱ類邊.在這種情形下，如果不對要刪除的邊進行排序，就會在沒有刪除完Ⅰ類邊的情況下去刪除Ⅱ類邊，造成不必要的信息損失.而本文所設計的算法1，就是在盡可能地把Ⅰ類邊刪除完的情況下再去刪除Ⅱ類邊，從而實現盡可能多地保留原始圖中邊的目的.

Fig. 2 Two nodes of connection in graph圖2 2類節點在圖中的連接方式

從上述分析可以看出，本文所提出的基于度排序的邊移除算法已經最大程度上逼近了原始圖中所能保留邊的最大數目.此外，該算法通過不斷地更新度排序，在算法運行效率和運行結果之間實現了較好地平衡.下面我們通過定理1說明，圖G=(V,E)在SER投影方法處理后，所得到壓縮圖SER(G)的直方圖hist(SER(G))的全局敏感度Δhist被限定在2θ+1的范圍內.

定理1. 對任意2個僅相差1個節點的圖G和G′(相鄰圖)，在經過SER投影方法所生成的度直方圖的敏感度為

證畢.

4 基于SER的點差分隱私度直方圖發布

在文獻[29]中，最早提出了把聚合的思想應用到直方圖中來減少誤差；Day等人[7]通過結合增邊的圖投影方法πθ和聚合的思想，提出了2種高效的點差分隱私度直方圖發布方法，即(θ,Ω)-直方圖發布和累計度直方圖發布.在本節，我們基于第3節所提出的SER投影方法和文獻[7]中的直方圖發布機制，給出2種新的點差分隱私下度分布發布機制，并證明其全局敏感度的大小和隱私安全性.

4.1 SER-(θ,Ω)-直方圖

在SER-(θ,Ω)-直方圖發布方法中，先用預先設置好的聚合規則Ω和Θ值得出一個由(θi,Ωj)組成的候選集T，并計算質量函數，然后通過指數機制選擇(θi,Ωj)，再運用提出的SER投影方法和度門限值θi對原始圖進行壓縮，最后用選擇的聚合規則Ωj對壓縮圖的度直方圖進行聚合并加噪，并做尾部處理.在我們的仿真實驗中，Θ的值為[1,100]中的整數，聚合規則Ω在文獻[7]中給出.

在第3節我們已經證明了SER投影方法在直方圖中的全局敏感度為2θ+1，則其質量函數為

其中,eh為創建直方圖過程中引入的誤差:

eh(G,θi,Ωj)=

在上述參數約束下，所用指數機制中的全局敏感度為6Θ+4[7].進而，基于SER投影方法的點差分隱私(θ,Ω)-直方圖發布機制可通過算法2給出，其中ε1，ε2為進行差分隱私機制中所需隱私預算.

算法2. SER-(θ,Ω)-直方圖發布算法.

輸入：圖G(V,E)、隱私預算ε1,ε2、候選集T；

輸出：加噪后的度分布D.

③ 通過算法1來投影圖G，得到Gθ*；

⑤ 通過算法5對h做尾部處理，得到h′；

⑥ returnD=h′

該算法中我們首先計算每個候選組(θi,Ωj)所對應的質量函數，其中θi遍歷[1,100]中的整數.然后通過指數機制來選擇候選組，并用候選組中的θi對輸入圖G進行壓縮得到Gθ*.最后，用聚合規則Ω*對Gθ*的度直方圖進行合并，用拉普拉斯機制對合并后的直方圖加噪.由于算法1的原因，直方圖在靠近θi的部分會明顯高于相鄰桶，不符合一般度分布的規律，所以我們在第5步設計了尾部處理(這一部分將在4.3節中詳細介紹).

4.2 SER-累積度直方圖

在SER-累計度直方圖發布機制中，第k個桶的計數為cumhistk=|v:deg(v)≤k|，即圖中度不超過k的節點的個數.下面我們通過定理2證明在累積度直方圖發布機制中，SER投影方法的全局敏感度Δcumhist為θ+1.

定理2. 對任意2個僅相差一個節點的圖G和G′(相鄰圖)，在經過SER后所生成的累積度直方圖的敏感度為

證畢.

在界定SER投影方法在累積直方圖發布機制中的全局敏感度之后，則滿足累積度直方圖的質量函數可定義為

而用指數機制選擇參數時的全局敏感度為2Θ+2.因此，基于SER投影方法的累積度直方圖發布機制如算法3所示：

算法3. SER-累積度直方圖發布算法.

輸入：圖G(V,E)、隱私預算ε1,ε2、候選集T；

輸出：加噪后的度分布D.

③ 通過算法1來投影圖G,得到Gθ*;

⑤ 通過算法4對ch做拆分處理，得到h；

⑥ 通過算法5對h做尾部處理；

⑦ returnD=h′

該算法中我們首先計算每個候選組θi所對應的質量函數，其中θi遍歷[1,100]中的整數.然后通過指數機制來選擇候選組，并用算法1對輸入圖G進行壓縮得到Gθ*.最后，對Gθ*的累積直方圖用拉普拉斯機制加噪.由于我們最后得到是累積度直方圖，為了方便實驗對比，我們還要用算法4(下面會詳細介紹)對直方圖進行拆分.同算法2，對拆分后的直方圖進行尾部處理.

累積度直方圖除了具有添加噪聲少的優點外，同時還具有單調性,即直方圖中桶的值是遞增的.基于此，我們把累積直方圖轉化為普通直方圖，設計了一種校準直方圖的算法，對發布結果進行調整，同時也方便進行對照實驗.在算法4中，如果前一個桶比后一個桶小，則直接用差值作為當前桶的計數.但是，由于噪聲的破壞，有可能會出現前一個桶比后一個桶大的情況，這時就需要在直方圖桶i到θ中找到1個大于桶i的桶j，在桶i到桶j中均勻地分配計數(行⑤～).

算法4. 提取累積直方圖.

輸入：界限為θ噪聲累積直方圖ch；

輸出：界限為θ度直方圖h.

①ch0=0,i=1；

② ifch1<0 then

③ch1=0；

④ end if

⑤ whilei≤θdo

⑥ ifchi

⑦hi=chi-chi-1；

⑧i=i+1；

⑨ else

⑩j∈[i,θ],從i到θ遍歷集合找到第1個使得chi

4.3 直方圖尾部處理

通過觀察原始圖可以發現，度分布一般遵循長尾分布，低度節點的計數通常較大，高度節點的計數通常較小且作出的直方圖類似于長尾.但是，經過投影后的圖的度分布卻與此不符：在度為θ的節點周圍的計數很大.這就導致最后發布的度分布與原始分布有較大的差異，并且當噪聲不夠大時，很有可能造成隱私泄露.事實上，這是由于所設計投影算法把度大于θ的節點全部投影在了度等于θ的節點周圍，進而導致θ周圍桶的計數過大.針對此類問題，一般采用基于線性回歸的尾部處理方案，即通過直方圖中除去θ的后半部分進行學習，得出線性回歸的斜率k和截距b，然后對加噪后的分布進行處理.

結合所提SER投影方法的細節，下面給出適用于基于SER投影方法的2種度分布發布機制的尾部處理方法：

算法5. 基于線性回歸的尾部處理.

輸入：直方圖H={h1,h2,…,hθ},n=|V|；

輸出：處理過的直方圖h.

①H′={hθ2,hθ2+1,…,hθ-1,hθ}；

② 根據H′擬合出二次函數F，并找出二次函數的拐點j；

③budget=sum([hj+1,hj+2…,hθ])；*設直方圖中度從拐點j開始到θ的計數為預算*

④H={hθ2,hθ2+1,…,hj}；*取直方圖中除去預算的部分作為回歸學習的樣本*

⑥ 根據H學習出線性回歸的斜率k和截距b.

⑦ fori=jton

⑧ ifk<0 then

⑨hi=k×i+b；

⑩ else

算法5的主要思想根據前半段符合長尾分布的直方圖學習出線性回歸的斜率和截距，然后把靠近θ的異常桶計數按照學習出的參數進行分配.此過程擴展了直方圖的橫軸，使得經過差分隱私后的度直方圖更加符合原始圖的分布.

4.4 隱私安全性證明

我們需要說明基于SER投影方法的(θ,Ω)-直方圖和累積直方圖的隱私安全性并通過定理給出.

定理3. 基于SER投影方法的(θ,Ω)-直方圖發布機制滿足(ε1+ε2)-點差分隱私.

證明. 在算法2中，行①②計算質量函數并通過指數機制來選擇參數.相當于n個查詢，這n個查詢記為Q1.由4.1節可知，刪除圖G中的1個節點，最多影響圖G中的6Θ+4個節點的度，則ΔQ1=6Θ+4.根據定義4可知行①②滿足ε1-差分隱私.行③④對壓縮圖的聚合直方圖利用拉普拉斯機制添加噪聲.由于聚合組的大小已知，相當于查詢每個組的計數總和，該類查詢記為Q2.由定理1可知，ΔQ1=2θ+1.根據定義3可知行③④滿足ε2-差分隱私.根據引理1及1.1節中對圖的點差分隱私描述可知，基于SER投影方法的(θ,Ω)-直方圖發布機制滿足(ε1+ε2)-差分隱私.

證畢.

同理可知基于SER投影方法的累積直方圖也滿足(ε1+ε2)-點差分隱私，其隱私安全性證明與定理3類似，不再贅述.

5 實驗與結果

為評估本文所提SER投影方法以及基于該算法的直方圖度發布機制的性能，本節將SER投影方法和已有的3種圖投影方法Truncation，ER，πθ[4-5,7]在不同數據集上的運行效果做一對比.仿真實驗所用的數據集包括社交網絡(Facebook,Twitter)、選舉投票(Wiki-Vote)、電子郵件(Email-Enron)、協作網絡(Ca-HepPh,DBLP)6個現實世界中的真實數據集，均來自Stanford Large Network Dataset Collection網站[30].表1給出了這6個數據集的部分特征，其中degmax表示圖中節點的最大度，degavg表示圖中節點的平均度.實驗平臺采用Intel?CoreTMi5-7400 CPU、8GB內存主機.

Table 1 Information About Dataset表1 數據集信息

5.1 實驗設置

由于把節點度限制到門限值θ時，大量度大于θ的節點投影成了度小于等于θ的節點，進而導致了度等于θ的節點的計數增加，從而影響L1誤差的計算結果，掩蓋了投影方法的其他特性.因此，在表2的對比結果中，為了更好地反映出投影方法的優劣，我們在計算L1誤差時刪除了度等于θ的節點計數.

在點差分隱私約束下直方圖度發布算法的對比實驗中，由于存在拉普拉斯噪聲，為了更好地反映算法的優勢，我們對每個ε取值計算30次，最后取平均值作為輸出.同時，取候選集的大小為100，即Θ∈[1,100].

Table 2 The Results on Different Datasets表2 Truncation,ER,πθ,SER方法在5個數據集上的實驗結果

5.2 結果分析

表2給出了Truncation[4]，ER[5]，πθ[7]3種圖投影算法和本文所提出的SER投影方法在6個不同數據集上，θ取16,64,128時的實驗結果，其中E′為經過投影后保留的原始圖的邊個數，L1為定義的L1誤差，越小表示數據可用性越好.

從表2中可以看出，隨著度門限值θ的增加，這4種算法中保留邊的數目都在不斷增加，同時L1不斷減小.但是，與其他3種已有算法相比，本文所提SER投影方法能在保留邊最多的情況下，同時也能保持較好的L1誤差.這說明SER方法在投影后能更好的保證原始圖的度分布的形狀，使其更加接近真實分布，為后續的數據分析和處理奠定基礎.圖3比較了在L1，KS這2種不同的度量指標下，本文提出的方法與文獻[4]、文獻[7]提出的方法在刻畫節點度分布時的差異.其中圖3(a)～(f)左半部分是用L1度量的結果，圖3(a)～(f)右半部分為用KS度量的結果.從圖3可以看出，隨著數據集的變化，截斷算法下的L1，KS一直是所有方法里面最大的，說明截斷算法的效果最差.這是由于算法本身刪除了許多本沒必要刪除的邊，損失了原始圖中的大量有效信息，造成了度分布的誤差過大.(θ,Ω)-直方圖發布方法和累積度直方圖發布方法的結果表明：對不同數據集，隨著規模的增大，2種方法的誤差呈現減小趨勢；對于相同的數據集，隨著隱私預算的增大，2種方法的誤差呈現減小趨勢，這符合我們一般的規律.

Fig. 3 Comparison of two histogram publishing methods圖3 2種直方圖發布方法實驗

從表1可以看出，Twitter和DBLP這2個數據集的邊個數差距不大，但是DBLP有更多的節點，Twitter有更大的最大度和平均度，這說明DBLP所構成的圖相較Twitter來說更加分散.反映到圖3中就是在2種直方圖發布方法下，DBLP相較Twitter的誤差更小，這說明了分散圖的度分布更好去刻畫.這是由于分散圖存在大量的節點p，其中deg(p)≤θ.而我們提出的方法能更好地保留度小于θ的節點所連接的邊，所以出現這種情況.同時為了方便對比，我們把同一類型的縱坐標取到相同的范圍，這使得最后2個數據集的效果不能很好地區分，不過從原始數據來看，我們提出的2種基于SER投影方法的直方圖發布方法效果要好于文獻[7]中的方法，這也符合前4種數據集的實驗結果.

總的來說，累積直方圖發布方法要優于(θ,Ω)-直方圖發布方法，基于SER投影方法的2種直方圖發布方法在不同數據集上的效果優于基于πθ的直方圖發布算法和截斷算法.特別地，當隱私預算ε≤1時，這種優勢更為明顯.這說明本文所提點差分隱私約束下度分布發布算法適用于對隱私預算控制很嚴格的情況，更符合隱私保護的相關要求.

6 總 結

隨著社交網絡、推薦系統等新型信息系統的廣泛使用，圖數據在大數據處理領域變得越發常見.大數據分析技術在圖數據上的廣泛應用可以帶來巨大的經濟價值和社會效益，這又促使各種組織機構開始搜集和發布大規模的圖數據集.另一方面，所搜集的圖數據中又包含用戶的敏感信息，如何在保護用戶隱私的前提下發布這些數據變得尤為迫切.

本文重點關注點差分隱私約束下的圖的度分布發布機制的設計，首先提出了一種基于度排序的邊移除(SER)算法，通過將原始圖投影到一個壓縮圖來降低發布機制中的全局敏感度.進一步地，基于所提SER投影方法給出了2種滿足點差分隱私的度直方圖發布機制，并證明了其隱私安全性.仿真實驗表明：相比已有方法，在相同的約束條件下，本文所提SER投影方法能最大程度地保留原始圖中的邊信息，為后續的數據處理奠定了良好的基礎.與已有度分布發布方法相比，基于SER投影方法的度直方圖發布機制在L1誤差和KS-距離這2個評估指標上均具有優勢，使得發布后的度分布更接近原始圖的度分布，可用性也越高.