防御鏈接預(yù)測(cè)攻擊的隱私保護(hù)方法

韓學(xué)波，王利娥，黃絲曼，劉 鵬，李先賢

(廣西師范大學(xué) 廣西多源信息挖掘與安全重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004)

0 引 言

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

1 相關(guān)工作

鏈接預(yù)測(cè)攻擊采用現(xiàn)有的鏈接預(yù)測(cè)方法[1]發(fā)現(xiàn)數(shù)據(jù)發(fā)布者隱藏的敏感鏈接信息。防御鏈接預(yù)測(cè)攻擊的隱私保護(hù)方法一般針對(duì)需要保護(hù)的敏感鏈接信息，采用刪除、擾動(dòng)等方法阻止敏感鏈接被預(yù)測(cè)出來[2]。目前，主要的鏈接預(yù)測(cè)算法都是基于網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計(jì)的，因此數(shù)據(jù)發(fā)布者可以在原始網(wǎng)絡(luò)中添加干擾，降低鏈接預(yù)測(cè)攻擊導(dǎo)致的敏感鏈接泄露的風(fēng)險(xiǎn)。但是，發(fā)布社交網(wǎng)絡(luò)數(shù)據(jù)的主要目的是進(jìn)行有價(jià)值的研究分析，因此需要限制鏈接的擾動(dòng)程度，確保發(fā)布網(wǎng)絡(luò)數(shù)據(jù)的效用性。

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

近年來，隨著深度學(xué)習(xí)不斷的發(fā)展，逐漸促進(jìn)了鏈接預(yù)測(cè)性能的提高。文獻(xiàn)[11]提出了一種網(wǎng)絡(luò)嵌入方法DeepWalk，通過截?cái)嚯S機(jī)游走學(xué)習(xí)出網(wǎng)絡(luò)節(jié)點(diǎn)的向量表示。文獻(xiàn)[12]提出一種node2vec方法，改進(jìn)了DeepWalk方法的隨機(jī)游走生成過程。文獻(xiàn)[13]將自編碼器遷移到了圖領(lǐng)域，提出了一種用于鏈接預(yù)測(cè)任務(wù)的圖自動(dòng)編碼器GAE(graph auto-encoders)模型，這一模型用已知的圖數(shù)據(jù)經(jīng)過編碼(圖卷積)學(xué)到節(jié)點(diǎn)向量表示的分布，在分布中采樣得到節(jié)點(diǎn)的向量表示，然后進(jìn)行解碼(鏈接預(yù)測(cè))重新構(gòu)建圖。文獻(xiàn)[14]提出一種基于圖神經(jīng)網(wǎng)絡(luò)的鏈接預(yù)測(cè)DGCNN模型，通過對(duì)閉合子圖的分類來預(yù)測(cè)敏感鏈接是否存在，提高了基于相似性的預(yù)測(cè)鏈接的準(zhǔn)確度和通用性。

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

本文針對(duì)目前防御鏈接預(yù)測(cè)攻擊的隱私保護(hù)方法的不足，提出一種基于積分梯度的局部擾動(dòng)方法，這種方法不需要提前設(shè)定鏈接擾動(dòng)數(shù)量，適用于大規(guī)模網(wǎng)絡(luò)，不但能夠保護(hù)用戶的鏈接隱私，而且可以保證發(fā)布圖的效用性。本文的主要貢獻(xiàn)如下：

(1)本文劃分敏感鏈接的閉合子圖作為擾動(dòng)范圍，只計(jì)算擾動(dòng)范圍內(nèi)鏈接的積分梯度，降低了計(jì)算復(fù)雜度，適用于大規(guī)模網(wǎng)絡(luò)的鏈接隱私保護(hù)；

(2)本文將鏈接預(yù)測(cè)模型對(duì)擾動(dòng)圖中敏感鏈接的錯(cuò)誤預(yù)測(cè)作為結(jié)束擾動(dòng)的判斷依據(jù)，不需要提前設(shè)置擾動(dòng)鏈接的數(shù)量，減少了鏈接擾動(dòng)數(shù)量，提高了隱私保護(hù)發(fā)布圖的效用性；

(3)本文通過敏感鏈接的保護(hù)成功率評(píng)估敏感鏈接的實(shí)際保護(hù)效果，利用平均鏈接修改數(shù)量評(píng)估發(fā)布圖的效用性。通過針對(duì)主流鏈接預(yù)測(cè)算法的防御實(shí)驗(yàn)，驗(yàn)證本文提出的隱私保護(hù)方法的普適性。

2 問題定義和預(yù)備知識(shí)

2.1 問題定義

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

(1)

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

(2)

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

2.2 圖自動(dòng)編碼器GAE模型

GAE模型是一種主流的基于深度學(xué)習(xí)的鏈接預(yù)測(cè)方法，通過兩層圖卷積網(wǎng)絡(luò)從距離中心節(jié)點(diǎn)最多2跳的節(jié)點(diǎn)信息中學(xué)習(xí)節(jié)點(diǎn)表示，極大提升了鏈接預(yù)測(cè)的性能。本文以GAE模型為例，將GAE模型作為敏感鏈接預(yù)測(cè)的攻擊工具，根據(jù)GAE模型提出一種敏感鏈接的隱私保護(hù)方法。下面介紹一下GAE模型。

(1)計(jì)算GCN層提取的每個(gè)節(jié)點(diǎn)的嵌入向量矩陣Z

(3)

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

As=s(ZZT)

(4)

其中，s是sigmoid函數(shù)，As是分?jǐn)?shù)矩陣, 當(dāng)分?jǐn)?shù)矩陣中的分?jǐn)?shù)元素大于閾值0.5時(shí)，預(yù)測(cè)對(duì)應(yīng)的鏈接存在，反之不存在。

(3)為了訓(xùn)練模型，構(gòu)造監(jiān)督訓(xùn)練的交叉熵?fù)p失函數(shù)L

(5)

ω是加權(quán)交叉熵的權(quán)重，用于防止對(duì)負(fù)樣本的過度擬合，因?yàn)樵诂F(xiàn)實(shí)世界的網(wǎng)絡(luò)中，不存在的鏈接通常比存在的鏈接多得多。

2.3 積分梯度

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

(6)

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

(7)

3 隱私保護(hù)方法

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

下面只介紹單個(gè)敏感鏈接的保護(hù)算法，由于本文采用局部擾動(dòng)的方式，當(dāng)需要同時(shí)保護(hù)多個(gè)敏感鏈接時(shí)可以對(duì)該算法采用并行計(jì)算，減少算法的運(yùn)行時(shí)間。

3.1 確定擾動(dòng)范圍

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

3.2 構(gòu)造敏感鏈接的交叉熵?fù)p失函數(shù)

(8)

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

3.3 確定擾動(dòng)鏈接的順序

因?yàn)橹暗难芯恐袌D神經(jīng)網(wǎng)絡(luò)的梯度計(jì)算次數(shù)只有一次，梯度的計(jì)算結(jié)果不準(zhǔn)確，所以文獻(xiàn)[18]在圖數(shù)據(jù)中引入積分梯度，提高了梯度計(jì)算的準(zhǔn)確性，表明積分梯度可以準(zhǔn)確反映擾動(dòng)鏈接對(duì)圖神經(jīng)網(wǎng)絡(luò)模型輸出和損失函數(shù)的影響。本文受到這一研究的啟發(fā)，將積分梯度用于衡量擾動(dòng)鏈接 (i,j) 對(duì)敏感鏈接損失函數(shù)的影響，擾動(dòng)鏈接的積分梯度值越大，說明這個(gè)鏈接對(duì)敏感鏈接的損失函數(shù)的影響越大。因?yàn)榉e分梯度可以一次計(jì)算出鏈接對(duì)敏感鏈接損失函數(shù)的影響，所以本文根據(jù)積分梯度對(duì)擾動(dòng)范圍中除敏感鏈接外的所有存在鏈接和不存在鏈接進(jìn)行從大到小排序，從而確定擾動(dòng)鏈接的順序。

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

(9)

(10)

3.4 擾 動(dòng)

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

本文算法的偽代碼如下。

算法1：LDIG算法

輸入：原圖G，計(jì)算積分梯度的步驟數(shù)m，迭代次數(shù)K，擾動(dòng)鏈接數(shù)量n

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

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

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

(5)IfAij=1；

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

(7)Else

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

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

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

(11)初始化擾動(dòng)數(shù)量n=0；

(12)通過迭代擾動(dòng)來逐漸實(shí)現(xiàn)模型的錯(cuò)誤預(yù)測(cè)，當(dāng)模型對(duì)敏感鏈接預(yù)測(cè)錯(cuò)誤時(shí)，結(jié)束擾動(dòng)；

(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

由于本文提出的隱私保護(hù)方法只考慮對(duì)網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行擾動(dòng)，所以這種方法能夠有效防御只考慮網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行預(yù)測(cè)的鏈接預(yù)測(cè)方法，針對(duì)綜合考慮節(jié)點(diǎn)屬性和網(wǎng)絡(luò)結(jié)構(gòu)的方法也有一定的保護(hù)效果，不適用于只考慮節(jié)點(diǎn)屬性的方法。因?yàn)橹豢紤]節(jié)點(diǎn)屬性的鏈接預(yù)測(cè)方法是很少的，大部分的鏈接預(yù)測(cè)方法都要考慮網(wǎng)絡(luò)結(jié)構(gòu)，所以本文提出的隱私保護(hù)方法具有一定的普適性。

4 實(shí) 驗(yàn)

我們的實(shí)驗(yàn)環(huán)境為：操作系統(tǒng)為ubuntu18.04 LTS；CPU核數(shù)為8核，CPU頻率為2.50 GHz，型號(hào)為Intel(R) Xeon(R) Silver 4215；GPU的顯存為16 160 M，型號(hào)為Tesla V100-FHHL。

4.1 數(shù)據(jù)集

為了更全面測(cè)試本文提出的算法性能，本文選擇了不同規(guī)模和不同類型的網(wǎng)絡(luò)數(shù)據(jù)集，見表1，這些數(shù)據(jù)集都是無向圖。

表1 數(shù)據(jù)集信息統(tǒng)計(jì)

Facebook是一個(gè)大型社交網(wǎng)絡(luò)數(shù)據(jù)集，其中節(jié)點(diǎn)代表用戶，鏈接是他們的友誼關(guān)系。Cora和Citeseer是引文網(wǎng)絡(luò)數(shù)據(jù)集，每個(gè)節(jié)點(diǎn)表示一篇科學(xué)論文，節(jié)點(diǎn)之間的鏈接表示兩篇論文存在引用關(guān)系。Pumbed是一個(gè)大型生物醫(yī)學(xué)方面的引文網(wǎng)絡(luò)數(shù)據(jù)集。

4.2 實(shí)驗(yàn)方法

本文隨機(jī)選擇整個(gè)網(wǎng)絡(luò)鏈接集中10%的鏈接作為需要保護(hù)的敏感鏈接測(cè)試集，驗(yàn)證防御方法對(duì)敏感鏈接的保護(hù)效果，其它的鏈接作為訓(xùn)練集。

我們比較了3種防御鏈接預(yù)測(cè)攻擊的隱私保護(hù)方法。

(1)分布估計(jì)算法

分布估計(jì)算法EDA(estimation of distribution algorithm)是文獻(xiàn)[2]針對(duì)RA算法提出的一種進(jìn)化擾動(dòng)算法，根據(jù)個(gè)體染色體的適應(yīng)值對(duì)染色體進(jìn)行抽樣估計(jì),然后根據(jù)統(tǒng)計(jì)學(xué)方法估計(jì)刪除鏈接和添加鏈接的概率分布，最后根據(jù)各自的分布產(chǎn)生n個(gè)染色體。本文在實(shí)驗(yàn)中將敏感鏈接的鏈接度k設(shè)置為算法的迭代次數(shù)。

(2)迭代梯度攻擊算法

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

(3)LDIG算法

由于本文提出的LDIG算法不提前設(shè)定修改鏈接的數(shù)量，為了與之前的兩個(gè)算法進(jìn)行合理對(duì)比，當(dāng)LDIG算法的鏈接修改數(shù)量小于敏感鏈接度k時(shí)才確定為成功保護(hù)，其中計(jì)算積分梯度的步數(shù)m設(shè)置為10。

4.3 評(píng)價(jià)指標(biāo)

(1)保護(hù)成功率

保護(hù)成功率是模型錯(cuò)誤預(yù)測(cè)敏感鏈接的數(shù)量與所有敏感鏈接的比例。本文通過保護(hù)成功率評(píng)估隱私保護(hù)方法的實(shí)際效果。保護(hù)成功率越大，說明隱私保護(hù)方法對(duì)敏感鏈接的保護(hù)效果越好。

(2)平均鏈接修改數(shù)量

平均鏈接修改數(shù)量是導(dǎo)致模型錯(cuò)誤預(yù)測(cè)敏感鏈接的平均擾動(dòng)鏈接的數(shù)量。本文利用平均鏈接修改數(shù)量評(píng)估發(fā)布圖的效用性，平均鏈接修改數(shù)量越小，隱私保護(hù)發(fā)布圖的效用性越好。

4.4 隱私保護(hù)方法的普適性

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

4.5 實(shí)驗(yàn)結(jié)果

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

本文首先介紹一下LDIG算法與IGA的實(shí)驗(yàn)對(duì)比結(jié)果，在保護(hù)成功率方面，LDIG算法在4個(gè)數(shù)據(jù)集的平均值分別比IGA高0.07%、0.12%、0.04%和1.04%，其中LDIG算法防御GAE、PA、CN和RA算法的成功率比IGA算法高，防御LP、LRW、node2vec算法的成功率與IGA算法不相上下，但是防御Katz算法的成功率不如IGA。在平均擾動(dòng)鏈接數(shù)量方面，LDIG算法在4個(gè)數(shù)據(jù)集的平均值分別比IGA少6.07、1.04、1.09和1.84。這表明LDIG算法在保證敏感鏈接保護(hù)效果的同時(shí)，減少了網(wǎng)絡(luò)的擾動(dòng)鏈接數(shù)量，提高了發(fā)布數(shù)據(jù)的效用性。這是因?yàn)長(zhǎng)DIG算法只考慮局部網(wǎng)絡(luò)信息，所以更有針對(duì)性的防御鏈接預(yù)測(cè)攻擊，同時(shí)減少了鏈接擾動(dòng)數(shù)量，而IGA算法考慮全局結(jié)構(gòu)信息，更利于防御基于全局網(wǎng)絡(luò)的Katz算法，但是擾動(dòng)鏈接的數(shù)量比較多。

表2 各種鏈接預(yù)測(cè)算法的預(yù)測(cè)性能比較

表3 不同隱私保護(hù)算法的防御效果

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

4.6 算法復(fù)雜度

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

表4 算法平均運(yùn)行時(shí)間/s

5 結(jié)束語(yǔ)

本文針對(duì)采用深度學(xué)習(xí)預(yù)測(cè)鏈接導(dǎo)致敏感關(guān)系隱私泄露的問題，提出了一種基于積分梯度的局部擾動(dòng)算法，欺騙深度學(xué)習(xí)對(duì)敏感鏈接預(yù)測(cè)錯(cuò)誤，防止敏感鏈接的隱私泄露。該算法適用于大規(guī)模的社交網(wǎng)絡(luò)數(shù)據(jù)，同時(shí)減少了擾動(dòng)鏈接的數(shù)量，提高了發(fā)布數(shù)據(jù)的效用性。防御主流鏈接預(yù)測(cè)算法的實(shí)驗(yàn)結(jié)果表明，這種算法可以防御主流的鏈接預(yù)測(cè)攻擊，具有普適性。本文沒有考慮基于節(jié)點(diǎn)屬性的鏈接預(yù)測(cè)方法，而節(jié)點(diǎn)屬性也是社交網(wǎng)絡(luò)中重要的一部分，因此接下來研究如何防御基于節(jié)點(diǎn)屬性的鏈接預(yù)測(cè)攻擊。