防御鏈接預測攻擊的隱私保護方法

韓學波，王利娥，黃絲曼，劉 鵬，李先賢

(廣西師范大學 廣西多源信息挖掘與安全重點實驗室，廣西 桂林 541004)

0 引 言

針對采用深度學習方法預測鏈接帶來的隱私問題，目前只有極少的研究借鑒深度學習的對抗攻擊方法，將生成對抗樣本的方法用于欺騙深度學習的鏈接預測方法，進而對敏感鏈接預測錯誤，從而保護敏感鏈接的隱私。但是目前提出的方法的計算復雜度較高，只適用于小型社交網絡。隨著大數據的發展，目前社交網絡的規模變得越來越大，針對這一不足，本文提出一種基于積分梯度的局部擾動算法，該算法通過劃分敏感鏈接的閉合子圖來縮小擾動范圍，只計算擾動范圍內的鏈接的積分梯度，降低了計算復雜度，適用于大規模的社交網絡。該算法將深度學習模型對擾動圖中敏感鏈接的錯誤預測作為結束擾動的判斷依據，不需要提前設置擾動鏈接的數量，從而減少了擾動鏈接數量，提高了隱私保護發布圖的效用性。該算法能夠防御基于相似性和深度學習的鏈接預測算法，具有普適性。

1 相關工作

鏈接預測攻擊采用現有的鏈接預測方法[1]發現數據發布者隱藏的敏感鏈接信息。防御鏈接預測攻擊的隱私保護方法一般針對需要保護的敏感鏈接信息，采用刪除、擾動等方法阻止敏感鏈接被預測出來[2]。目前，主要的鏈接預測算法都是基于網絡結構設計的，因此數據發布者可以在原始網絡中添加干擾，降低鏈接預測攻擊導致的敏感鏈接泄露的風險。但是，發布社交網絡數據的主要目的是進行有價值的研究分析，因此需要限制鏈接的擾動程度，確保發布網絡數據的效用性。

在鏈接預測算法的研究中，基于相似性的算法是最主流的鏈接預測方法，它假定兩個節點越相似，它們越有可能產生聯系。根據相似性計算需要的鄰居最大跳數進行分類，分為一階、二階和高階啟發式算法。一階啟發式算法只涉及兩個目標節點的單跳鄰居，例如，共同鄰居CN(common neighbor)算法[3]假設兩個節點的共同鄰居越多，那么它們越容易產生鏈接。優先連接PA(preferential attachment)算法[4]認為節點更有可能和度數較高的節點產生鏈接。二階啟發式算法根據目標節點的兩跳鄰居計算相似度，例如，AA(adamic-adar)算法[5]根據共同鄰居節點的度為每個節點賦予一個權重值，該權重等于該節點度的對數的倒數。于是AA算法計算出的相似值就等于兩個節點的所有共同鄰居的權重值的和。資源分配RA(resource allocation)算法[6]的形式與AA算法差不多，不同的是RA的權重形式變成了節點的度的倒數。高階啟發式算法根據目標節點的三跳及以上鄰居計算相似性，如局部路徑指標LP(local path)[7]在二跳鄰居的基礎上考慮三跳鄰居。Katz算法[8]是基于全局網絡的算法，根據整個網絡計算相似度，全面考慮節點在網絡中的路徑信息，對網絡中兩節點之間所有路徑做加權求和，它的缺點是計算復雜度太高。目前已經有一些工作提出了防御基于相似性的鏈接預測算法的隱私保護方法。文獻[2]針對基于相似性的鏈接預測算法RA，提出一種啟發式和進化擾動算法，降低了RA算法預測敏感鏈接的性能。文獻[9]針對鏈接預測能夠暴露兩人的敏感關系的情況，提出一種社交用戶逃避鏈接預測算法的隱私保護方法。文獻[10]通過刪除鏈接來攻擊基于相似性的鏈接預測。

近年來，隨著深度學習不斷的發展，逐漸促進了鏈接預測性能的提高。文獻[11]提出了一種網絡嵌入方法DeepWalk，通過截斷隨機游走學習出網絡節點的向量表示。文獻[12]提出一種node2vec方法，改進了DeepWalk方法的隨機游走生成過程。文獻[13]將自編碼器遷移到了圖領域，提出了一種用于鏈接預測任務的圖自動編碼器GAE(graph auto-encoders)模型，這一模型用已知的圖數據經過編碼(圖卷積)學到節點向量表示的分布，在分布中采樣得到節點的向量表示，然后進行解碼(鏈接預測)重新構建圖。文獻[14]提出一種基于圖神經網絡的鏈接預測DGCNN模型，通過對閉合子圖的分類來預測敏感鏈接是否存在，提高了基于相似性的預測鏈接的準確度和通用性。

攻擊者采用基于深度學習的鏈接預測算法，可以更精確預測出社交網絡用戶的敏感關系，之前針對相似性鏈接預測的防御方法并不能起到很好的防御效果，基于深度學習的鏈接預測方法給隱私保護方法的研究帶來了新的挑戰。由于深度學習的脆弱性，人們針對深度學習的對抗攻擊展開了一系列研究，本文借鑒深度學習的對抗攻擊方法，將生成對抗樣本方法用于防御基于深度學習的鏈接預測，使深度學習的鏈接預測方法對敏感鏈接預測錯誤，從而保護敏感鏈接的隱私。其中，文獻[15]對圖深度學習的魯棒性及對抗攻擊進行了開創性研究，針對圖神經網絡模型分別提出了基于強化學習、遺傳算法和梯度的對抗攻擊方法。文獻[16]將生成對抗樣本的方法用于保護用戶的鏈接隱私，假設數據發布者對圖自動編碼器GAE模型有充分的了解，針對圖自動編碼器GAE模型提出迭代梯度攻擊(IGA)進行隱私保護，降低了GAE模型對特定敏感鏈接的預測性能，同時也可以作為一種衡量鏈接預測算法的魯棒性的方法。然而這種迭代梯度攻擊方法有兩個不足：①這種方法需要通過計算圖中所有鏈接梯度來確定擾動鏈接，同時又需要迭代計算梯度，從而導致這種方法的計算復雜度比較高，不適用于大規模網絡；②這種方法需要提前設置算法的迭代次數和每次迭代中鏈接擾動的數量，缺乏擾動過程中對擾動效果的判斷依據。

本文針對目前防御鏈接預測攻擊的隱私保護方法的不足，提出一種基于積分梯度的局部擾動方法，這種方法不需要提前設定鏈接擾動數量，適用于大規模網絡，不但能夠保護用戶的鏈接隱私，而且可以保證發布圖的效用性。本文的主要貢獻如下：

(1)本文劃分敏感鏈接的閉合子圖作為擾動范圍，只計算擾動范圍內鏈接的積分梯度，降低了計算復雜度，適用于大規模網絡的鏈接隱私保護；

(2)本文將鏈接預測模型對擾動圖中敏感鏈接的錯誤預測作為結束擾動的判斷依據，不需要提前設置擾動鏈接的數量，減少了鏈接擾動數量，提高了隱私保護發布圖的效用性；

(3)本文通過敏感鏈接的保護成功率評估敏感鏈接的實際保護效果，利用平均鏈接修改數量評估發布圖的效用性。通過針對主流鏈接預測算法的防御實驗，驗證本文提出的隱私保護方法的普適性。

2 問題定義和預備知識

2.1 問題定義

定義1 鏈接預測：給定原始圖G=(V,E)，V表示所有節點的集合，E表示所有鏈接的集合。E分為兩組，Eo是可以觀察到的鏈接，Eu是需要預測的未知鏈接，其中Eo∩Eu=?，Eo∪Eu=E。 鏈接預測是基于V和Eo的信息來預測Eu。

(1)

其中，Eβ+∪Eβ-=Eβ，Eβ+∩Eβ-=?，Eβ-?Eo，Eβ+?(Ω-E), Ω={(i,j),(i,j)∈V,i≠j}。

(2)

其中， I(·)∈{0,1} 是一個指示函數(indicator function)，m是鏈接修改的最大數目，Eβ=Eβ+∪Eβ-。

2.2 圖自動編碼器GAE模型

GAE模型是一種主流的基于深度學習的鏈接預測方法，通過兩層圖卷積網絡從距離中心節點最多2跳的節點信息中學習節點表示，極大提升了鏈接預測的性能。本文以GAE模型為例，將GAE模型作為敏感鏈接預測的攻擊工具，根據GAE模型提出一種敏感鏈接的隱私保護方法。下面介紹一下GAE模型。

(1)計算GCN層提取的每個節點的嵌入向量矩陣Z

(3)

(2)計算所有鏈接的概率

As=s(ZZT)

(4)

其中，s是sigmoid函數，As是分數矩陣, 當分數矩陣中的分數元素大于閾值0.5時，預測對應的鏈接存在，反之不存在。

(3)為了訓練模型，構造監督訓練的交叉熵損失函數L

(5)

ω是加權交叉熵的權重，用于防止對負樣本的過度擬合，因為在現實世界的網絡中，不存在的鏈接通常比存在的鏈接多得多。

2.3 積分梯度

對于給定的模型F∶Rnn→[0,1]， 其中x∈Rn是輸入，x′是基線輸入(例如，圖像數據的黑色圖像)。計算從基線輸入x′到輸入x的直線路徑的所有梯度，通過累積這些梯度得到積分梯度。輸入x的第i個特征的積分梯度(IG)的計算公式如下

(6)

積分梯度可以通過求和來有效地逼近，利用足夠小的間隔對從基線輸入x′到輸入x的直線路徑上的點的梯度求和，積分梯度的近似計算公式如下

(7)

3 隱私保護方法

本文提出一種基于積分梯度的局部擾動方法，欺騙深度學習對敏感鏈接做出錯誤預測，從而防止敏感鏈接的隱私泄露。該方法的主要思想是：首先劃分敏感鏈接的二階閉合子圖作為擾動范圍，只擾動二階閉合子圖中的鏈接，就會改變敏感鏈接的鄰居節點，導致GAE模型提取錯誤的鄰居節點信息，然后計算擾動范圍內每個鏈接的積分梯度，衡量這些鏈接修改對敏感鏈接損失函數的影響，最后按照積分梯度從大到小的順序擾動鏈接，當鏈接預測模型對擾動圖的敏感鏈接預測錯誤時結束擾動。

下面只介紹單個敏感鏈接的保護算法，由于本文采用局部擾動的方式，當需要同時保護多個敏感鏈接時可以對該算法采用并行計算，減少算法的運行時間。

3.1 確定擾動范圍

本文將原圖G中敏感鏈接 (i′,j′) 的節點對i′和j′的直接和間接鄰居節點以及它們之間的鏈接構成的閉合子圖Gh作為擾動范圍，擾動范圍中的鏈接可以任意修改。GAE模型使用兩層GCN提取距離中心節點最多2跳的鄰居節點信息，然而GAE模型判斷鄰居節點的依據是節點間是否存在鏈接，所以擾動敏感鏈接的閉合子圖，就會改變敏感鏈接的鄰居節點，導致GAE模型錯誤的提取鄰居節點信息，從而提高敏感鏈接預測錯誤的概率。文獻[14]驗證了目標鏈接的閉合子圖包含了相似性算法預測目標鏈接所需的大部分結構信息，而閉合子圖以外的結構信息對于目標鏈接預測的幫助很小。所以本文只將敏感鏈接閉合子圖的所有鏈接作為擾動范圍，使得擾動更有針對性，減少了計算復雜度。

3.2 構造敏感鏈接的交叉熵損失函數

(8)

其中，Ai′j′為敏感鏈接 (i′,j′) 在原圖中的真實值，Ai′j′∈{0,1}， 其中0代表敏感鏈接不存在，1代表敏感鏈接存在；Yi′j′(A) 為GAE模型敏感鏈接存在的概率值。

3.3 確定擾動鏈接的順序

因為之前的研究中圖神經網絡的梯度計算次數只有一次，梯度的計算結果不準確，所以文獻[18]在圖數據中引入積分梯度，提高了梯度計算的準確性，表明積分梯度可以準確反映擾動鏈接對圖神經網絡模型輸出和損失函數的影響。本文受到這一研究的啟發，將積分梯度用于衡量擾動鏈接 (i,j) 對敏感鏈接損失函數的影響，擾動鏈接的積分梯度值越大，說明這個鏈接對敏感鏈接的損失函數的影響越大。因為積分梯度可以一次計算出鏈接對敏感鏈接損失函數的影響，所以本文根據積分梯度對擾動范圍中除敏感鏈接外的所有存在鏈接和不存在鏈接進行從大到小排序，從而確定擾動鏈接的順序。

根據鏈接是否存在，分為兩種計算積分梯度的方法，具體如下：

(9)

(10)

3.4 擾 動

積分梯度只是反映了每個鏈接對敏感鏈接損失函數造成的影響，但是這種影響會導致兩種情況，一種情況是使敏感鏈接的損失函數變大，另一種是使敏感鏈接的損失函數變小，本文要想增大GAE模型預測敏感鏈接的錯誤概率，就應該選擇敏感鏈接損失函數值最大化的擾動鏈接。積分梯度分為正梯度和負梯度，正梯度意味著目標損失最大化的方向是在鄰接矩陣的相應位置增加值，負梯度則是在鄰接矩陣的相應位置減小值。由于網絡數據是離散的，我們只允許添加或刪除鏈接。因為積分梯度有正負，所以本文按照積分梯度的絕對值從大到小排序，對原圖進行迭代擾動，算法的偽代碼展示了每一次迭代擾動的具體過程。

本文算法的偽代碼如下。

算法1：LDIG算法

輸入：原圖G，計算積分梯度的步驟數m，迭代次數K，擾動鏈接數量n

(1)確定敏感鏈接 (i′,j′) 的閉合子圖；

(3)輸入原圖訓練GAE模型；

(4)計算閉合子圖中所有鏈接的積分梯度；

(5)IfAij=1；

(6)Ab=0，計算IG(i,j)

(7)Else

(8)Ab=1，計算IG(i,j)

(9)根據積分梯度的絕對值對擾動范圍中除敏感鏈接外的所有鏈接從大到小排序；

(10)確定最大積分梯度IG_max和對應的鏈接 (i,j)；

(11)初始化擾動數量n=0；

(12)通過迭代擾動來逐漸實現模型的錯誤預測，當模型對敏感鏈接預測錯誤時，結束擾動；

(14) ifAij=0 and IGmax(i,j)>0

(15)Aij=1， IGmax(i,j)=0

(16) else ifAij=1 and IGmax(i,j)<0

(17)Aij=0， IGmax(i,j)=0

(18) Else

(19) continue

由于本文提出的隱私保護方法只考慮對網絡結構進行擾動，所以這種方法能夠有效防御只考慮網絡結構進行預測的鏈接預測方法，針對綜合考慮節點屬性和網絡結構的方法也有一定的保護效果，不適用于只考慮節點屬性的方法。因為只考慮節點屬性的鏈接預測方法是很少的，大部分的鏈接預測方法都要考慮網絡結構，所以本文提出的隱私保護方法具有一定的普適性。

4 實 驗

我們的實驗環境為：操作系統為ubuntu18.04 LTS；CPU核數為8核，CPU頻率為2.50 GHz，型號為Intel(R) Xeon(R) Silver 4215；GPU的顯存為16 160 M，型號為Tesla V100-FHHL。

4.1 數據集

為了更全面測試本文提出的算法性能，本文選擇了不同規模和不同類型的網絡數據集，見表1，這些數據集都是無向圖。

表1 數據集信息統計

Facebook是一個大型社交網絡數據集，其中節點代表用戶，鏈接是他們的友誼關系。Cora和Citeseer是引文網絡數據集，每個節點表示一篇科學論文，節點之間的鏈接表示兩篇論文存在引用關系。Pumbed是一個大型生物醫學方面的引文網絡數據集。

4.2 實驗方法

本文隨機選擇整個網絡鏈接集中10%的鏈接作為需要保護的敏感鏈接測試集，驗證防御方法對敏感鏈接的保護效果，其它的鏈接作為訓練集。

我們比較了3種防御鏈接預測攻擊的隱私保護方法。

(1)分布估計算法

分布估計算法EDA(estimation of distribution algorithm)是文獻[2]針對RA算法提出的一種進化擾動算法，根據個體染色體的適應值對染色體進行抽樣估計,然后根據統計學方法估計刪除鏈接和添加鏈接的概率分布，最后根據各自的分布產生n個染色體。本文在實驗中將敏感鏈接的鏈接度k設置為算法的迭代次數。

(2)迭代梯度攻擊算法

迭代梯度攻擊算法IGA(iterative gradient attack)是文獻[16]針對GAE模型提出的一種基于梯度的對抗攻擊方法，通過迭代計算梯度產生擾動。IGA算法分為無限攻擊和單節點攻擊，其中的無限攻擊可用于數據發布，本文與IGA算法的無限攻擊作對比。無限攻擊沒有任何修改鏈接的限制，唯一的限制是修改鏈接的總數。本文在實驗中將保護敏感鏈接的鏈接修改數量設置為敏感鏈接度k， 其中鏈接度k是構成鏈接的兩個節點的度的總和，將k設置為算法的迭代次數，每次迭代修改的鏈接數量n設置為1。

(3)LDIG算法

由于本文提出的LDIG算法不提前設定修改鏈接的數量，為了與之前的兩個算法進行合理對比，當LDIG算法的鏈接修改數量小于敏感鏈接度k時才確定為成功保護，其中計算積分梯度的步數m設置為10。

4.3 評價指標

(1)保護成功率

保護成功率是模型錯誤預測敏感鏈接的數量與所有敏感鏈接的比例。本文通過保護成功率評估隱私保護方法的實際效果。保護成功率越大，說明隱私保護方法對敏感鏈接的保護效果越好。

(2)平均鏈接修改數量

平均鏈接修改數量是導致模型錯誤預測敏感鏈接的平均擾動鏈接的數量。本文利用平均鏈接修改數量評估發布圖的效用性，平均鏈接修改數量越小，隱私保護發布圖的效用性越好。

4.4 隱私保護方法的普適性

盡管本文提出的算法可以抵御鏈接預測GAE的攻擊，但是攻擊者也可以使用其它鏈接預測方法，因此，了解LDIG算法的普遍適用性是十分重要的。本文通過其它鏈接預測算法的防御實驗，驗證LDIG算法的普遍適用性。由于鏈接預測算法的種類眾多，同時基于網絡結構相似性和基于深度學習的方法是目前比較流行的方法，所以本文采用這兩類中比較有代表性的算法。表2為選出的具有代表性的鏈接預測算法的預測性能比較。

4.5 實驗結果

表3給出了LDIG、EDA和IGA算法的保護成功率和平均鏈接擾動數量。從表中可以看出，LDIG算法的整體性能不錯。

本文首先介紹一下LDIG算法與IGA的實驗對比結果，在保護成功率方面，LDIG算法在4個數據集的平均值分別比IGA高0.07%、0.12%、0.04%和1.04%，其中LDIG算法防御GAE、PA、CN和RA算法的成功率比IGA算法高，防御LP、LRW、node2vec算法的成功率與IGA算法不相上下，但是防御Katz算法的成功率不如IGA。在平均擾動鏈接數量方面，LDIG算法在4個數據集的平均值分別比IGA少6.07、1.04、1.09和1.84。這表明LDIG算法在保證敏感鏈接保護效果的同時，減少了網絡的擾動鏈接數量，提高了發布數據的效用性。這是因為LDIG算法只考慮局部網絡信息，所以更有針對性的防御鏈接預測攻擊，同時減少了鏈接擾動數量，而IGA算法考慮全局結構信息，更利于防御基于全局網絡的Katz算法，但是擾動鏈接的數量比較多。

表2 各種鏈接預測算法的預測性能比較

表3 不同隱私保護算法的防御效果

本文然后介紹一下LDIG算法與EDA的實驗對比結果，在保護成功率方面，LDIG算法在4個數據集的平均值分別比EDA高6.88%、7.82%、5.74%和9.56%，其中LDIG算法防御8種鏈接預測的保護成功率都高于EDA。在平均擾動鏈接數量方面，LDIG算法在4個數據集的平均值分別比EDA多0.39、0.55、0.48和0.98。這表明LDIG算法比EDA算法的敏感鏈接保護效果提高了不少，同時在可接受的范圍內增加了鏈接擾動數量，所以LDIG算法從整體上優于EDA算法。這是由于EDA算法考慮一跳鄰居的信息，LDIG算法在一跳鄰居的基礎上考慮二跳鄰居的信息，所以LDIG算法防御高階鄰居的鏈接預測的成功率比EDA高，同時增加了鏈接擾動數量，由于LDIG算法能夠自動判斷擾動效果來結束擾動，所以這個算法能夠在可接受的范圍內增加鏈接擾動數量。

4.6 算法復雜度

如表4所示，本文比較了3個算法保護單個敏感鏈接的平均運行時間，LDIG算法在4個數據集中的平均時間分別比IGA少1175.58 s、510.35 s、502.01 s和5708.62 s，遠遠小于IGA。LDIG算法在4個數據集中的平均時間分別比EDA算法多2.91 s、1.2 s、1.2 s和14.58 s，LDIG算法比EDA算法增加的時間很少，增加的時間在可接受范圍內。這表明LDIG算法的時間復雜度比較低。這是由于LDIG算法劃分敏感鏈接的二階閉合子圖作為擾動范圍，只計算擾動范圍中的鏈接的積分梯度，與IGA算法相比，大大降低了計算復雜度。

表4 算法平均運行時間/s

5 結束語

本文針對采用深度學習預測鏈接導致敏感關系隱私泄露的問題，提出了一種基于積分梯度的局部擾動算法，欺騙深度學習對敏感鏈接預測錯誤，防止敏感鏈接的隱私泄露。該算法適用于大規模的社交網絡數據，同時減少了擾動鏈接的數量，提高了發布數據的效用性。防御主流鏈接預測算法的實驗結果表明，這種算法可以防御主流的鏈接預測攻擊，具有普適性。本文沒有考慮基于節點屬性的鏈接預測方法，而節點屬性也是社交網絡中重要的一部分，因此接下來研究如何防御基于節點屬性的鏈接預測攻擊。