逆鏈路預(yù)測(cè)方法研究綜述

李 晶,蔣忠元,馬建峰

西安電子科技大學(xué) 網(wǎng)絡(luò)與信息安全學(xué)院 西安 中國(guó) 710071

1 引言

在現(xiàn)實(shí)世界中,許多系統(tǒng)都可以表示為網(wǎng)絡(luò)(network/graph),例如社交網(wǎng)絡(luò)[1-2],生物網(wǎng)絡(luò)[3],通信網(wǎng)絡(luò)[4],交通網(wǎng)絡(luò)[5]等,可謂網(wǎng)絡(luò)無(wú)處不在。通常,節(jié)點(diǎn)(node/vertex)為網(wǎng)絡(luò)中的行為對(duì)象,而鏈路或鏈接(link/edge)為對(duì)象之間的某類(lèi)關(guān)聯(lián)關(guān)系,比如好友關(guān)系、郵件交流、化學(xué)反應(yīng)、物質(zhì)傳遞等。特別地,某些網(wǎng)絡(luò)系統(tǒng)(尤其是社交網(wǎng)絡(luò))是動(dòng)態(tài)的,并且此類(lèi)網(wǎng)絡(luò)中的鏈接始終隨時(shí)間而不斷變化[6-7]。基于此類(lèi)網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行分析,進(jìn)而判斷網(wǎng)絡(luò)中未發(fā)現(xiàn)的或?qū)?lái)會(huì)形成、更改的鏈接,通常被稱(chēng)為鏈路預(yù)測(cè)過(guò)程。鏈路預(yù)測(cè)對(duì)我們進(jìn)行網(wǎng)絡(luò)深入分析、獲取網(wǎng)絡(luò)未知信息具有重要的作用,能夠?yàn)楦鞣N實(shí)際應(yīng)用帶來(lái)好處,因此已被應(yīng)用于許多重要的領(lǐng)域中。例如,如果已知了恐怖分子的部分通信網(wǎng)絡(luò)或親屬關(guān)系網(wǎng)絡(luò),則可以通過(guò)鏈路預(yù)測(cè)來(lái)發(fā)現(xiàn)一些隱藏的鏈接,從而發(fā)現(xiàn)潛在的恐怖分子[8]。鏈路預(yù)測(cè)也可以用于推薦系統(tǒng)[9-10],網(wǎng)絡(luò)重構(gòu)[11]和節(jié)點(diǎn)分類(lèi)[12]等。

在過(guò)去的幾十年中,許多關(guān)于鏈路預(yù)測(cè)的研究被相繼提出。然而,在鏈路預(yù)測(cè)被廣泛用于網(wǎng)絡(luò)分析的同時(shí),也導(dǎo)致了越來(lái)越多的個(gè)人信息可以在網(wǎng)上被他人獲取,引起了人們對(duì)于隱私問(wèn)題的擔(dān)憂(yōu)。例如,在社交網(wǎng)絡(luò)中,可能存在一些敏感鏈接,表示兩個(gè)人之間的某種關(guān)系,比如通信關(guān)系、交易或戀愛(ài)關(guān)系[56]。這些敏感關(guān)系通常涉及個(gè)人隱私,因此人們不愿意將其公開(kāi)并將其隱藏。Mislove等人[13]證明,通過(guò)分析 Facebook的社交網(wǎng)絡(luò)結(jié)構(gòu),不僅可以推斷出其他Facebook用戶(hù)的私人信息,而且可以推斷某些用戶(hù)的屬性。隨著惡意攻擊者利用鏈路預(yù)測(cè)等分析方法引發(fā)的各種攻擊帶來(lái)的嚴(yán)重安全威脅,如何保護(hù)網(wǎng)絡(luò)中的敏感隱私鏈接,避免被鏈路預(yù)測(cè)這一網(wǎng)絡(luò)分析工具攻擊引起了越來(lái)越多研究者的關(guān)注。

針對(duì)鏈路預(yù)測(cè)可能導(dǎo)致的隱私泄漏這一問(wèn)題,大量關(guān)于個(gè)人隱私保護(hù),欺騙鏈路預(yù)測(cè)模型的方法被提出,我們將這一類(lèi)研究稱(chēng)為逆鏈路預(yù)測(cè)問(wèn)題。逆鏈路預(yù)測(cè)研究的出發(fā)點(diǎn)與鏈路預(yù)測(cè)相反,它試圖分析各種鏈路預(yù)測(cè)模型的脆弱性,產(chǎn)生可以對(duì)抗鏈路預(yù)測(cè)的方法以及保護(hù)網(wǎng)絡(luò)中的敏感鏈接。基于研究的不同目的和適用場(chǎng)景,我們將目前已有的逆鏈路預(yù)測(cè)方法分為了三類(lèi): 基于對(duì)抗的逆鏈路預(yù)測(cè)方法、基于魯棒性攻擊的逆鏈路預(yù)測(cè)方法和基于隱私保護(hù)的逆鏈路預(yù)測(cè)方法。

基于對(duì)抗的逆鏈路預(yù)測(cè)方法是指通過(guò)對(duì)原始網(wǎng)絡(luò)進(jìn)行一些擾動(dòng),使得鏈路預(yù)測(cè)方法在擾動(dòng)后的網(wǎng)絡(luò)上的結(jié)果與本應(yīng)得到的在原始網(wǎng)絡(luò)上的預(yù)測(cè)結(jié)果大相徑庭,從而達(dá)到保護(hù)隱私鏈接的作用。由于鏈路預(yù)測(cè)旨在發(fā)現(xiàn)一些大概率存在但不可觀察的鏈接,因此針對(duì)鏈路預(yù)測(cè)的對(duì)抗方法也以一些敏感鏈接為隱藏目標(biāo),也就是說(shuō)必須防止目標(biāo)鏈接被鏈路預(yù)測(cè)成功預(yù)測(cè)。鏈接干擾是此類(lèi)研究中的一種常用技術(shù)[57],例如,數(shù)據(jù)發(fā)布者可以隨機(jī)地修改原始網(wǎng)絡(luò)上的鏈接以防止敏感鏈接被識(shí)別。它是一種針對(duì)鏈路預(yù)測(cè)的防御方法,也是對(duì)鏈路預(yù)測(cè)的攻擊方法。

基于魯棒性攻擊的逆鏈路預(yù)測(cè)方法研究了在各種鏈路預(yù)測(cè)對(duì)抗策略下一些預(yù)測(cè)方法的魯棒性。盡管先前已經(jīng)出現(xiàn)了許多有效的鏈路預(yù)測(cè)方法,但其魯棒性尚未得到廣泛的討論。鏈路預(yù)測(cè)在遭受欺騙時(shí)能否依然保持預(yù)測(cè)結(jié)果的準(zhǔn)確性,是在評(píng)價(jià)一個(gè)鏈路預(yù)測(cè)方法時(shí)同樣需要考慮到的因素。上面的鏈路預(yù)測(cè)對(duì)抗方法被用來(lái)分析預(yù)測(cè)模型的脆弱性。

基于隱私保護(hù)的逆鏈路預(yù)測(cè)方法從隱私保護(hù)的角度切入,對(duì)需要進(jìn)行隱私保護(hù)的敏感鏈路進(jìn)行隱私函數(shù)定義、證明與提出解決方案,并通過(guò)大量的實(shí)驗(yàn)進(jìn)行系統(tǒng)驗(yàn)證。

當(dāng)然,隱私保護(hù)方法也可能被攻擊者不正當(dāng)?shù)厥褂?。個(gè)人、社區(qū)和數(shù)據(jù)發(fā)布者可采用鏈路預(yù)測(cè)對(duì)抗網(wǎng)絡(luò)作為應(yīng)對(duì)過(guò)多網(wǎng)絡(luò)分析的隱私保護(hù)工具,但當(dāng)黑客濫用對(duì)抗性攻擊掩蓋其非法社區(qū)時(shí),將會(huì)有極大的安全威脅。例如,他們可以通過(guò)更改很小部分的鏈接來(lái)掩蓋穆罕默德·阿塔在世貿(mào)中心恐怖主義網(wǎng)絡(luò)中的領(lǐng)導(dǎo)地位[14]。有效的防御將協(xié)助反恐部門(mén)和執(zhí)法機(jī)構(gòu)根據(jù)大眾對(duì)社交媒體的日益依賴(lài)發(fā)現(xiàn)罪犯和恐怖分子。許多基于鏈路預(yù)測(cè)方法的推薦系統(tǒng)也可能被欺騙,這可能會(huì)使欺詐者將他們的產(chǎn)品推薦給無(wú)辜的用戶(hù)。因此,迫切需要衡量鏈路預(yù)測(cè)算法的魯棒性,研究鏈路預(yù)測(cè)對(duì)抗的防御方法。目前關(guān)于防御方法的研究還比較少,我們將在后面的章節(jié)進(jìn)行介紹。

本文對(duì)現(xiàn)有的逆鏈路預(yù)測(cè)方法及其防御對(duì)策進(jìn)行了綜述。首先從鏈路預(yù)測(cè)方法入手,介紹了目前使用較為廣泛的預(yù)測(cè)方法的分類(lèi)及原理。接下來(lái)將從鏈路預(yù)測(cè)對(duì)抗、鏈路預(yù)測(cè)方法的魯棒性和隱私保護(hù)三個(gè)方面來(lái)總結(jié)現(xiàn)有的逆鏈路預(yù)測(cè)工作。然后介紹了針對(duì)逆鏈路預(yù)測(cè)方法的防御策略。本文的主要貢獻(xiàn)如下:

1.我們對(duì)這一方面的工作進(jìn)行了完整的綜述,總結(jié)了現(xiàn)有研究工作的核心貢獻(xiàn),并根據(jù)較合理的依據(jù)在攻擊和防御任務(wù)方面從系統(tǒng)的角度對(duì)它們進(jìn)行了分類(lèi)闡述。

2.對(duì)現(xiàn)有研究的相關(guān)評(píng)價(jià)指標(biāo)進(jìn)行了系統(tǒng)梳理與對(duì)比分析,對(duì)可用的網(wǎng)絡(luò)資源等進(jìn)行了梳理與介紹。

3.綜合分析了現(xiàn)有逆鏈路預(yù)測(cè)方法的優(yōu)劣性,展望了未來(lái)可能的研究方向。

2 鏈路預(yù)測(cè)

鏈路預(yù)測(cè)能夠基于可觀察的鏈接和網(wǎng)絡(luò)中的其他信息嘗試發(fā)現(xiàn)未知的鏈接或用來(lái)預(yù)測(cè)節(jié)點(diǎn)之間未來(lái)形成鏈接的可能性。它源于數(shù)據(jù)挖掘領(lǐng)域,隨著網(wǎng)絡(luò)科學(xué)研究的蓬勃發(fā)展而引起了眾多學(xué)者的關(guān)注。

目前已經(jīng)有許多成熟的鏈路預(yù)測(cè)方法可以被廣泛地應(yīng)用于各項(xiàng)研究領(lǐng)域,這一章節(jié)將對(duì)現(xiàn)有的鏈路預(yù)測(cè)方法依據(jù)不同的分類(lèi)進(jìn)行闡述說(shuō)明,并對(duì)一些常見(jiàn)算法的原理進(jìn)行說(shuō)明。將預(yù)測(cè)方法分為了以下三大類(lèi): 基于相似性的鏈路預(yù)測(cè)方法、基于機(jī)器學(xué)習(xí)的鏈路預(yù)測(cè)方法以及基于最大似然的鏈路預(yù)測(cè)方法。

2.1 基于相似性的鏈路預(yù)測(cè)方法

此類(lèi)方法將節(jié)點(diǎn)間相似性的大小作為判斷它們之間存在鏈接可能性的依據(jù)。由于節(jié)點(diǎn)的基本屬性通常是隱藏不可獲得的,難以用來(lái)評(píng)定節(jié)點(diǎn)間的相似性,因此此小節(jié)中列出的方法以網(wǎng)絡(luò)結(jié)構(gòu)的相似性為基礎(chǔ)進(jìn)行判別。其中,每對(duì)節(jié)點(diǎn)x和y通過(guò)方法的計(jì)算公式會(huì)獲得一個(gè)得分sxy,sxy就定義為x和y之間的相似度。網(wǎng)絡(luò)中所有未觀察到的鏈接均根據(jù)其相似度進(jìn)行排名,最終節(jié)點(diǎn)間相似度越高的鏈接被認(rèn)為具有更大的存在可能性。不同方法的主要區(qū)別之一就是它們定義的節(jié)點(diǎn)相似性指標(biāo)不同。圖 1描述了鏈路預(yù)測(cè)算法的基本過(guò)程,使用RA指標(biāo)來(lái)計(jì)算節(jié)點(diǎn)間的相似性,首先利用鏈路預(yù)測(cè)算法對(duì)網(wǎng)絡(luò)中所有不可觀察的鏈接進(jìn)行相似度的計(jì)算,節(jié)點(diǎn)對(duì)間的相似度越大就越有可能形成鏈接,網(wǎng)絡(luò)中節(jié)點(diǎn)對(duì)i和j間的相似度最大,因此被鏈路預(yù)測(cè)算法成功地預(yù)測(cè)出來(lái)。

這類(lèi)鏈路預(yù)測(cè)方法的相似性指標(biāo)共有20個(gè),可以分為三種不同的評(píng)價(jià)方向: 基于局部信息、基于全局信息以及基于類(lèi)局部信息[15]。

圖1 鏈路預(yù)測(cè)算法過(guò)程的舉例Figure 1 An example of link prediction algorithm process

2.1.1 基于局部信息的方法

共同鄰居 (common neighbors,CN)指標(biāo)[16]是基于局部信息的方法中最基礎(chǔ)的相似性指標(biāo),它關(guān)注網(wǎng)絡(luò)的局部信息結(jié)構(gòu),計(jì)算節(jié)點(diǎn)對(duì)之間的共同鄰居個(gè)數(shù),共同鄰居越多則兩個(gè)節(jié)點(diǎn)越相似。以CN算法為基礎(chǔ),加入對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)度的考慮,可以得到下面其他的方法: Salton指標(biāo)[17]、Jaccard指標(biāo)[18]、Sorensen指標(biāo)[19]、大度節(jié)點(diǎn)有利指標(biāo) (hub promoted index,HPI)[20]、大度節(jié)點(diǎn)不利指標(biāo)(hub depressed index,HDI)和LHN-I指標(biāo)[21]。另一個(gè)只考慮節(jié)點(diǎn)度的方法為優(yōu)先連接指標(biāo) (preferential attachment,PA)[58]。另外,還有考慮到度不同的共同鄰居節(jié)點(diǎn)的重要程度不同而設(shè)計(jì)的 Adamic- Adar (AA)指標(biāo)[22],以及從網(wǎng)絡(luò)資源分配角度提出的資源分配 (Resource Allocation,RA)指標(biāo)[23]。

這類(lèi)相似性指標(biāo)共有10種,它們?cè)诤?jiǎn)單高效的計(jì)算過(guò)程中充分考慮了節(jié)點(diǎn)的共同鄰居或者節(jié)點(diǎn)度等網(wǎng)絡(luò)中的局部信息,并且預(yù)測(cè)的結(jié)果具有較高的預(yù)測(cè)精確度。由于它的計(jì)算過(guò)程較為簡(jiǎn)單,復(fù)雜度低執(zhí)行效率高,有較好的準(zhǔn)確性,且適用的網(wǎng)絡(luò)范圍很廣,因此是使用的最為廣泛的一類(lèi)指標(biāo)之一。表1列出了這 10種基于局部信息的相似性指標(biāo)的定義,對(duì)于網(wǎng)絡(luò)中的節(jié)點(diǎn)x,定義它的鄰居為δ（x）,為節(jié)點(diǎn)x的度。

表1 基于局部信息的相似性指標(biāo)定義Table 1 Definitions of similarity metrics based on local information

2.1.2 基于全局信息的方法

基于全局信息的方法有7種,包括Katz指標(biāo)[24]、LHN-II指標(biāo)[21]、平均通勤時(shí)間(Average Commute Time,ACT)[25]、基于隨機(jī)游走的余弦相似性(Cos+)指標(biāo)[26]、重啟的隨機(jī)游走(Random Walk with Restart,RWR)[27]、SimRank指標(biāo)[28]以及矩陣森林指標(biāo)(Matrix Forest Index,MFI)[29]。

與上面的基于局部信息的方法相比,基于全局信息的鏈路預(yù)測(cè)方法要求提供完整的網(wǎng)絡(luò)拓?fù)湫畔?。盡管基于全局信息可以提供比基于局部信息更準(zhǔn)確的預(yù)測(cè),但基于全局信息進(jìn)行計(jì)算非常耗時(shí),因此這類(lèi)方法通常不適用于大規(guī)模網(wǎng)絡(luò); 并且在現(xiàn)實(shí)世界中經(jīng)常會(huì)有無(wú)法獲得網(wǎng)絡(luò)的完整拓?fù)湫畔⒌那闆r,這使得此類(lèi)鏈路預(yù)測(cè)方法的應(yīng)用與上一類(lèi)相比受到了限制。

2.1.3 基于類(lèi)局部信息的方法

基于類(lèi)局部信息的方法有 3種,即局部路徑指標(biāo)(Local Path Index,LP)[30]、局部隨機(jī)游走(Local Random Walk,LRW)[31]和疊加的局部隨機(jī)游走(Superposed Random Walk,SRW)[31]。

基于類(lèi)局部信息的鏈路預(yù)測(cè)方法是基于局部信息和全局信息的折衷方案。他的計(jì)算復(fù)雜度低于基于全局信息的方法,它不需要網(wǎng)絡(luò)的全局拓?fù)湫畔?但比基于局部信息的方法考慮更多的網(wǎng)絡(luò)結(jié)構(gòu),在計(jì)算中放棄了對(duì)鏈路預(yù)測(cè)精確度沒(méi)有貢獻(xiàn)或貢獻(xiàn)很小的多余網(wǎng)絡(luò)信息,預(yù)測(cè)結(jié)果通常具有更高的準(zhǔn)確性。

2.2 基于機(jī)器學(xué)習(xí)的鏈路預(yù)測(cè)方法

現(xiàn)有的鏈路預(yù)測(cè)方法除了基于相似性的研究之外,隨著機(jī)器學(xué)習(xí)的蓬勃發(fā)展,許多機(jī)器學(xué)習(xí)算法被應(yīng)用到鏈路預(yù)測(cè)領(lǐng)域,誕生了許多不同類(lèi)型的基于機(jī)器學(xué)習(xí)的方法。這一小節(jié)將著重介紹現(xiàn)有的逆鏈路預(yù)測(cè)研究涉及的基于機(jī)器學(xué)習(xí)的鏈路預(yù)測(cè)方法,主要與深度學(xué)習(xí)模型相關(guān)。

近年來(lái),隨著深度學(xué)習(xí)模型的飛速發(fā)展,網(wǎng)絡(luò)嵌入算法在許多網(wǎng)絡(luò)任務(wù)中都取得了卓越的性能,例如: 節(jié)點(diǎn)分類(lèi)[76-77]、鏈路預(yù)測(cè)[33]等。受語(yǔ)言模型word2vec[32]發(fā)展的啟發(fā),諸如DeepWalk[33],LINE[34]和 node2vec[35]等無(wú)監(jiān)督學(xué)習(xí)的網(wǎng)絡(luò)嵌入方法取得了巨大的成功,這些模型學(xué)習(xí)得到的嵌入結(jié)果可以直接應(yīng)用于網(wǎng)絡(luò)的鏈路預(yù)測(cè)任務(wù)[33]。Kipf等人[36]提出了用于鏈路預(yù)測(cè)的圖自編碼器(graph auto-encoder,GAE)模型,它使用圖卷積網(wǎng)絡(luò)(Graph Convolutional Network,GCN)作為編碼器,受計(jì)算機(jī)視覺(jué)領(lǐng)域的卷積神經(jīng)網(wǎng)絡(luò)啟發(fā),GCN可以直接在圖上實(shí)現(xiàn)卷積[74],這個(gè)過(guò)程可用一行簡(jiǎn)短的公式表達(dá):

將GCN視為一個(gè)函數(shù),節(jié)點(diǎn)的特征矩陣X和鄰接矩陣A作為輸入,輸出Z∈RN×f,N表示網(wǎng)絡(luò)節(jié)點(diǎn)數(shù),f為嵌入結(jié)果的維度,Z代表的就是所有節(jié)點(diǎn)的嵌入結(jié)果; 使用節(jié)點(diǎn)特征的點(diǎn)積和激活函數(shù)作為解碼器來(lái)重構(gòu)原始的圖,即:

并且根據(jù)損失函數(shù)使用梯度下降來(lái)優(yōu)化模型中的參數(shù)。

由于深度學(xué)習(xí)方法具有非線(xiàn)性和分層的特性,因此它們?cè)阪溌奉A(yù)測(cè)及其他網(wǎng)絡(luò)分析任務(wù)中顯示出強(qiáng)大的功能和巨大的潛力。這些模型在保留網(wǎng)絡(luò)初始結(jié)構(gòu)和節(jié)點(diǎn)間鄰近度的前提下,將網(wǎng)絡(luò)中的所有節(jié)點(diǎn)表示為低維的向量形式,由此得到的嵌入結(jié)果可以直接應(yīng)用于各種網(wǎng)絡(luò)任務(wù),包括鏈路預(yù)測(cè),且有較好的預(yù)測(cè)效果,近年來(lái)也得到了較為廣泛的應(yīng)用。對(duì)于常用的網(wǎng)絡(luò)嵌入算法,清華大學(xué)開(kāi)源了一個(gè)較為完整的網(wǎng)絡(luò)表示學(xué)習(xí)的 python工具包①https://github.com/thunlp/OpenNE便于搭建與調(diào)試。

2.3 基于最大似然的鏈路預(yù)測(cè)方法

基于最大似然的鏈路預(yù)測(cè)方法的基本原理是:根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)的產(chǎn)生和組織方式以及目前已經(jīng)觀察到的鏈路計(jì)算網(wǎng)絡(luò)的似然值,并認(rèn)為真實(shí)的網(wǎng)絡(luò)使得網(wǎng)絡(luò)似然值最大,然后通過(guò)最大化網(wǎng)絡(luò)的似然值來(lái)計(jì)算任何未觀察到的節(jié)點(diǎn)間產(chǎn)生鏈接的可能性。該方法適合于處理具有明顯層次組織的網(wǎng)絡(luò)類(lèi)型,且對(duì)這類(lèi)網(wǎng)絡(luò)具有較好的精確度。

基于最大似然的方法可以再具體分為層次結(jié)構(gòu)模型[61]和隨機(jī)分塊模型[62]兩種。由于目前針對(duì)此類(lèi)方法的逆鏈路預(yù)測(cè)研究較少,本文將不再針對(duì)這兩種模型進(jìn)行單獨(dú)地討論。

從實(shí)際應(yīng)用的角度來(lái)看,最大似然法的一個(gè)明顯缺點(diǎn)是非常耗時(shí),計(jì)算時(shí)間復(fù)雜度高。設(shè)計(jì)較好的該類(lèi)算法能夠在合理的時(shí)間內(nèi)處理數(shù)千個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò),但肯定無(wú)法處理包含了數(shù)百萬(wàn)個(gè)節(jié)點(diǎn)的龐大在線(xiàn)網(wǎng)絡(luò)。另外,基于最大似然的方法與前面幾種鏈路預(yù)測(cè)方法相比,可能通常不是最準(zhǔn)確的方法,但是,基于最大似然的方法為網(wǎng)絡(luò)組織提供了非常有價(jià)值的見(jiàn)解,而這是無(wú)法從其他鏈路預(yù)測(cè)模型中獲得的。

3 逆鏈路預(yù)測(cè)

隨著各類(lèi)型鏈路預(yù)測(cè)技術(shù)的不斷完善及其日益廣泛的應(yīng)用,近兩年來(lái),對(duì)于逆鏈路預(yù)測(cè)的相關(guān)研究也引起了眾多的關(guān)注。逆鏈路預(yù)測(cè)的目的是欺騙或攻擊鏈路預(yù)測(cè)模型,使得到的結(jié)果與真實(shí)情況不符或隱藏網(wǎng)絡(luò)中的部分鏈接使其不被預(yù)測(cè)模型發(fā)現(xiàn),從而使鏈路預(yù)測(cè)的結(jié)果失效。它試圖分析各種鏈路預(yù)測(cè)模型的脆弱性,產(chǎn)生可以對(duì)抗鏈路預(yù)測(cè)的方法以及保護(hù)網(wǎng)絡(luò)中的敏感鏈接。

對(duì)于進(jìn)行逆鏈路預(yù)測(cè),最常采用的手段就是添加或刪除網(wǎng)絡(luò)中鏈接,也可以稱(chēng)為鏈接干擾或重寫(xiě),通過(guò)這種手段就可以使網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和一些節(jié)點(diǎn)間的相似性發(fā)生變化,產(chǎn)生截然不同的預(yù)測(cè)結(jié)果,從而隱藏網(wǎng)絡(luò)修改者不希望被別人發(fā)現(xiàn)的鏈接或關(guān)系。不同方法的主要區(qū)別之一就是判斷對(duì)哪些鏈接進(jìn)行添加或刪除的算法不同,設(shè)計(jì)者期望通過(guò)改動(dòng)盡可能少的鏈接數(shù),對(duì)預(yù)測(cè)結(jié)果的準(zhǔn)確性產(chǎn)生盡可能大的影響。圖 2描述了逆鏈路預(yù)測(cè)算法的基本過(guò)程,使用RA相似性指標(biāo)作為鏈路預(yù)測(cè)方法進(jìn)行計(jì)算,目標(biāo)鏈接在原始網(wǎng)絡(luò)的預(yù)測(cè)結(jié)果中是得分最大的鏈接,會(huì)被鏈路預(yù)測(cè)算法識(shí)別,逆鏈路預(yù)測(cè)算法通過(guò)添加和刪除部分鏈接的干擾方式形成了可用于公開(kāi)的對(duì)抗網(wǎng)絡(luò),最終鏈路預(yù)測(cè)算法對(duì)對(duì)抗網(wǎng)絡(luò)進(jìn)行預(yù)測(cè)時(shí)將得到錯(cuò)誤的結(jié)果,達(dá)到了目標(biāo)鏈接被成功隱藏的目的。

圖2 逆鏈路預(yù)測(cè)算法過(guò)程的舉例Figure 2 An Example of reverse link prediction algorithm process

本章節(jié)將對(duì)現(xiàn)有的逆鏈路預(yù)測(cè)研究進(jìn)行全面的梳理和總結(jié)。根據(jù)研究目的和適用場(chǎng)景的不同,逆鏈路預(yù)測(cè)研究可以分為以下三類(lèi): 基于對(duì)抗的逆鏈路預(yù)測(cè)方法、基于魯棒性攻擊的逆鏈路預(yù)測(cè)方法和基于隱私保護(hù)的逆鏈路預(yù)測(cè)方法。

3.1 基于對(duì)抗的逆鏈路預(yù)測(cè)方法

基于對(duì)抗的逆鏈路預(yù)測(cè)方法通常是從攻擊者角度對(duì)鏈路預(yù)測(cè)模型進(jìn)行的一種欺騙和對(duì)抗。由于鏈路預(yù)測(cè)的結(jié)果會(huì)依據(jù)概率由大到小對(duì)可能存在但不可觀察的鏈接進(jìn)行排序,因此針對(duì)鏈路預(yù)測(cè)的對(duì)抗方法以一些敏感鏈接為隱藏目標(biāo),盡可能降低其排序,也就是說(shuō)必須防止目標(biāo)鏈接被預(yù)測(cè)方法成功預(yù)測(cè)。下文中的目標(biāo)鏈接指的就是要進(jìn)行隱藏的敏感鏈接。

由于基于對(duì)抗的逆鏈路預(yù)測(cè)方法是對(duì)鏈路預(yù)測(cè)模型的一種攻擊,它們通常是針對(duì)某一種鏈路預(yù)測(cè)模型提出的,在近年來(lái)的研究中,越來(lái)越多的研究者在確定所提出逆鏈路預(yù)測(cè)方法對(duì)該種預(yù)測(cè)模型具有較高攻擊性的同時(shí),也傾向于判斷該方法是否具有可轉(zhuǎn)移性,即證明所提出方法對(duì)其他種類(lèi)的鏈路預(yù)測(cè)模型是否也具有攻擊性。由于鏈路預(yù)測(cè)方法的種類(lèi)較多,因此具有可轉(zhuǎn)移性的攻擊方法也具有更廣闊的應(yīng)用場(chǎng)景,引起了許多研究者的重視。下面的介紹中將對(duì)具有可轉(zhuǎn)移性的逆鏈路預(yù)測(cè)方法進(jìn)行特別地說(shuō)明。

此類(lèi)方法根據(jù)其算法依靠的基礎(chǔ)方法的不同分為基于相似性指標(biāo)的方法、基于深度學(xué)習(xí)模型的方法和基于其他算法的方法三類(lèi)。

3.1.1 基于相似性指標(biāo)的方法

此類(lèi)方基于鏈路預(yù)測(cè)的相似性指標(biāo),并結(jié)合其他策略來(lái)選擇要進(jìn)行添加或刪除的鏈接,通常也用于針對(duì)基于相似性的鏈路預(yù)測(cè)方法。

Zhou等人[37]對(duì)通過(guò)鏈接刪除來(lái)攻擊基于相似性的鏈路預(yù)測(cè)問(wèn)題進(jìn)行了全面的算法研究,重點(diǎn)研究了此類(lèi)方法的兩大類(lèi),一類(lèi)僅使用有關(guān)目標(biāo)鏈接的局部信息,另一類(lèi)使用全局網(wǎng)絡(luò)信息。基于局部信息的方法思路如下: 將U=｛ui｝表示為目標(biāo)鏈接集H中的兩端節(jié)點(diǎn)的集合,稱(chēng)為目標(biāo)節(jié)點(diǎn)。假設(shè)U=n。W= ｛w1,w2,… ,wm｝是目標(biāo)節(jié)點(diǎn)共同鄰居的集合,其中每個(gè)wi∈W連接到U中的至少兩個(gè)節(jié)點(diǎn)。合理的攻擊者只會(huì)刪除W中的節(jié)點(diǎn)和U中的節(jié)點(diǎn)之間的邊,否則刪除其他類(lèi)型的邊都不會(huì)導(dǎo)致兩個(gè)ui間共同鄰居數(shù)減少,從而使得節(jié)點(diǎn)間相似度減小。并且使用決策矩陣X∈｛0,1｝m×n表示W(wǎng)和U中節(jié)點(diǎn)之間的鏈接狀態(tài),如果wi和uj之間存在鏈接,則X的第i行和第j列的數(shù)值xij等于1,否則xij= 0。因此,決策矩陣X完全捕獲了目標(biāo)鏈接集的總相似度f(wàn)t。最終作者將基于局部相似度的攻擊表述為優(yōu)化問(wèn)題來(lái)決定要進(jìn)行刪除的鏈接,

其中X0是原始決策矩陣,而Sum函數(shù)表示逐元素求和,k表示最多可以刪除網(wǎng)絡(luò)中的k條鏈接。通過(guò)求解上述優(yōu)化問(wèn)題得到新的決策矩陣X,從而有節(jié)點(diǎn)之間新的鏈接狀態(tài),判斷要進(jìn)行刪除的邊。使用網(wǎng)絡(luò)全局信息的方法原理與上面類(lèi)似,作者用 Katz和ACT指標(biāo)求解優(yōu)化問(wèn)題計(jì)算出了要進(jìn)行刪除的鏈接集合。該方法針對(duì)不同的相似性指標(biāo)優(yōu)化模型不同,有較好的對(duì)抗效果,當(dāng)選擇的相似性指標(biāo)發(fā)生變化時(shí),要依據(jù)當(dāng)前指標(biāo)的特點(diǎn)設(shè)計(jì)不同的優(yōu)化模型。

3.1.2 基于深度學(xué)習(xí)模型的方法

近年來(lái),深度學(xué)習(xí)模型在鏈路預(yù)測(cè)中顯示了出強(qiáng)大的功能和巨大的潛力。然而,另一方面,深度學(xué)習(xí)模型的脆弱性也被揭露了出來(lái)。在計(jì)算機(jī)視覺(jué)領(lǐng)域,精心設(shè)計(jì)的對(duì)抗樣本容易欺騙深度學(xué)習(xí)模型,這些樣本對(duì)原始的圖像略微施加干擾,從而使模型無(wú)法獲得正確的結(jié)果[38-39]。這些改動(dòng)通常很難被人們注意到,并且讓深度學(xué)習(xí)模型以高置信度得到了錯(cuò)誤的結(jié)果[38,40]。針對(duì)鏈路預(yù)測(cè)的深度學(xué)習(xí)模型是否也可以被對(duì)抗樣本攻擊,從而產(chǎn)生錯(cuò)誤的預(yù)測(cè)結(jié)果是這類(lèi)方法的研究核心。

Chen等人[41]提出并正式定義了鏈路預(yù)測(cè)的對(duì)抗攻擊問(wèn)題,他們提出了一種基于圖自編碼器(GAE)中梯度信息的迭代梯度攻擊(iterative gradient attack,IGA)方法,并討論了對(duì)其他預(yù)測(cè)方法的可轉(zhuǎn)移性。由于在實(shí)際網(wǎng)絡(luò)中,不存在的鏈接通常比現(xiàn)有的鏈接要多得多,換句話(huà)說(shuō),負(fù)樣本遠(yuǎn)遠(yuǎn)大于正樣本,因此作者將公式(3)中的損失函數(shù)構(gòu)造為加權(quán)的交叉熵,以防止負(fù)樣本過(guò)度擬合:

其中Yt∈ ｛ 0,1｝是目標(biāo)鏈接Et的真實(shí)鏈接狀態(tài),而t是GAE計(jì)算得出的Et存在的概率。在指定了損失函數(shù)的情況下,則可以計(jì)算對(duì)鄰接矩陣的偏導(dǎo)數(shù),從而獲得梯度矩陣:

進(jìn)行鏈路預(yù)測(cè)時(shí),在梯度下降過(guò)程中會(huì)將損失函數(shù)L取到一個(gè)很小的值,以獲得良好的預(yù)測(cè)能力。逆鏈路預(yù)測(cè)方法則相反,在這里需要最大化目標(biāo)損失函數(shù),以使模型錯(cuò)誤地預(yù)測(cè)目標(biāo)鏈接。梯度矩陣中的值可以為正或負(fù),正或負(fù)梯度表示最大化目標(biāo)損失函數(shù)的方向是在鄰接矩陣的相應(yīng)位置中增大或減小該值。由于網(wǎng)絡(luò)數(shù)據(jù)是離散的,僅允許添加或刪除鏈接的操作,即只能在鄰接矩陣中置1或置0。要進(jìn)行添加或刪除的鏈接的選擇取決于它們梯度的大小,因?yàn)樘荻缺砻髁嗽撴溄訉?duì)損失函數(shù)的影響程度,數(shù)值越大,鏈接對(duì)目標(biāo)損耗的影響就越大。但要特別注意的是,無(wú)論數(shù)值有多大都無(wú)法對(duì)其梯度為正/負(fù)的現(xiàn)有/不存在的鏈接進(jìn)行修改,這些邊被認(rèn)為是不可攻擊的。與梯度下降過(guò)程相同,對(duì)抗網(wǎng)絡(luò)的生成也是迭代的。在每一次迭代中,選擇梯度最大并且同時(shí)可對(duì)其進(jìn)行攻擊的n條鏈接進(jìn)行修改。通過(guò)將這些步驟重復(fù)k次,就可以得到最終的對(duì)抗網(wǎng)絡(luò),該網(wǎng)絡(luò)可以欺騙鏈路預(yù)測(cè)方法。IGA可以有效地對(duì)各種鏈路預(yù)測(cè)方法進(jìn)行對(duì)抗,有可轉(zhuǎn)移性,可攻擊包括基于深度學(xué)習(xí)的鏈路預(yù)測(cè)方法(deepwalk,node2vec等)和經(jīng)典的基于相似性的鏈路預(yù)測(cè)方法 (CN等)。

針對(duì)基于深度學(xué)習(xí)模型的鏈路預(yù)測(cè),Chen等人[42]還對(duì)動(dòng)態(tài)網(wǎng)絡(luò)進(jìn)行了研究,提出了對(duì)動(dòng)態(tài)網(wǎng)絡(luò)鏈路預(yù)測(cè)(dynamic network link prediction,DNLP)進(jìn)行對(duì)抗性攻擊的第一項(xiàng)研究。所提出的攻擊方法為時(shí)間感知梯度攻擊(time-aware gradient attack,TGA),利用跨不同快照的深度動(dòng)態(tài)網(wǎng)絡(luò)嵌入(DDNE[43])生成的梯度信息來(lái)修改一些鏈接,從而使 DDNE無(wú)法準(zhǔn)確預(yù)測(cè)目標(biāo)鏈接。論文通過(guò)兩種方式來(lái)實(shí)現(xiàn)TGA: 一種是基于遍歷搜索(traversal search)的方法,即TGA-Tra; 另一個(gè)為提高效率簡(jiǎn)化為貪婪搜索(greedy search),即TGA-Gre。TGA在攻擊DNLP算法方面具有出色的性能。與上面的方法類(lèi)似,根據(jù)梯度信息可以找到要進(jìn)行修改的鏈接,從而實(shí)現(xiàn)攻擊。修改涉及節(jié)點(diǎn)i和j間鏈接的梯度gt（i,j）的大小和符號(hào),分別決定了候選鏈接以及應(yīng)如何修改它們。為了降低修改成本,修改的重點(diǎn)將放在梯度最大的鏈接上,因?yàn)榇祟?lèi)鏈接的變化對(duì)的影響比其他鏈接更大。TGA在DDNE上生成的對(duì)抗示例也可以用于有效攻擊其他DNLP算法這一事實(shí)證明了TGA方法的可轉(zhuǎn)移性。作者通過(guò)大量實(shí)驗(yàn)發(fā)現(xiàn),長(zhǎng)時(shí)間的動(dòng)態(tài)預(yù)測(cè)更容易受到對(duì)抗攻擊的影響,而已知更長(zhǎng)的歷史信息可以增強(qiáng) DNLP算法的魯棒性。稀疏網(wǎng)絡(luò)相對(duì)比較容易受到對(duì)抗性攻擊的干擾,也就是說(shuō),稀疏網(wǎng)絡(luò)上的DNLP算法不那么健壯。由于TGA-Tra比較了大量的修改方案,因此通常是更有效的,但是它具有相對(duì)較高的時(shí)間復(fù)雜度。TGA-Tra的性能優(yōu)于 TGA-Gre,但后者的效率要高得多,因此在實(shí)際應(yīng)用中更加實(shí)用。TGA-Tra和TGA-Gre之間性能的顯著差距也說(shuō)明每次迭代中的最大下降有時(shí)不會(huì)導(dǎo)致最佳的攻擊性能。二者在一些具體細(xì)節(jié)和適用場(chǎng)景方面也有一些區(qū)別,首先,TGA-Tra更有可能在較早的歷史快照上修改鏈接,而 TGA-Gre傾向于更改最新鏈接的鏈接; 其次,TGA-Tra傾向于添加而不是刪除鏈接,而 TGA-Gre具有相反的趨勢(shì)。這樣的觀察表明,TGA-Tra對(duì)網(wǎng)絡(luò)進(jìn)行的修改應(yīng)該比TGA-Gre更不容易被發(fā)現(xiàn),因?yàn)槿藗儍A向于更加關(guān)注最近的事件,例如最近網(wǎng)絡(luò)快照中的鏈接更改。另一方面,如果想獲得一些短期攻擊效果,則應(yīng)該首選TGA-Gre。此外,由于在真實(shí)的社交網(wǎng)絡(luò)中添加鏈接總是比刪除鏈接容易,因此 TGA-Tra似乎具有較低的社交成本。

3.1.3 基于其他算法的方法

除了以上兩種較有針對(duì)性的基于對(duì)抗的逆鏈路預(yù)測(cè)方法外,還有一些方法是基于其他各種類(lèi)型的算法提出的。

Yu等人[44]提出了一種對(duì)抗RA指標(biāo)鏈路預(yù)測(cè)模型,防止敏感鏈接泄露的方法。在論文中主要運(yùn)用了三類(lèi)方法,包括了隨機(jī)鏈接干擾、啟發(fā)式鏈接干擾以及進(jìn)化式鏈接干擾。每種方法的具體實(shí)施過(guò)程如下:隨機(jī)鏈接干擾分為了鏈接重寫(xiě)和鏈接交換兩種,鏈接重寫(xiě)是隨機(jī)刪除和插入一定數(shù)量的鏈接,鏈接交換指的是每次隨機(jī)抽取兩個(gè)節(jié)點(diǎn)對(duì),交叉連接,這樣可以保持所有節(jié)點(diǎn)的度不變。啟發(fā)式鏈接干擾是一種專(zhuān)門(mén)針對(duì)鏈路預(yù)測(cè)方法精確度的方法,降低測(cè)試集節(jié)點(diǎn)對(duì)在鏈路預(yù)測(cè)結(jié)果中的排名。它通過(guò)遍歷降序的鏈路預(yù)測(cè)結(jié)果集,對(duì)排名前n的節(jié)點(diǎn)對(duì)根據(jù)所屬集合(訓(xùn)練集、測(cè)試集或者不存在的鏈接集合)執(zhí)行不同的操作,例如,如果鏈接屬于訓(xùn)練集則直接刪除該鏈接,這樣該鏈接就可以作為相似度極高的未觀察到的鏈接,讓預(yù)測(cè)者誤以為預(yù)測(cè)到了有用的結(jié)果。進(jìn)化式鏈接干擾運(yùn)用了兩種不同的算法,包括遺傳算法(Genetic Algorithm,GA)[63]和分布估計(jì)算法(Estimation of Distribution Algorithm,EDA)[64],兩種方法根據(jù)適應(yīng)度函數(shù)來(lái)選擇要進(jìn)行添加和刪除的鏈接,EDA與遺傳算法GA有著明顯的區(qū)別。GA 采用交叉和變異等操作產(chǎn)生新個(gè)體,EDA則通過(guò)對(duì)搜索空間采樣和統(tǒng)計(jì)學(xué)習(xí)來(lái)預(yù)測(cè)搜索的最佳區(qū)域,進(jìn)而產(chǎn)生優(yōu)秀的新個(gè)體。相比于 GA 基于基因的微觀層面的進(jìn)化方式,EDA采用基于搜索空間的宏觀層面的進(jìn)化方法,具備更強(qiáng)的全局搜索能力和更快的收斂速度。該方法還考慮了提出的進(jìn)化式算法的執(zhí)行效率問(wèn)題,對(duì)計(jì)算過(guò)程進(jìn)行了改進(jìn)來(lái)加速適應(yīng)度的計(jì)算: 只計(jì)算相似度發(fā)生變化的鏈接集,進(jìn)行增量更新,從而避免了冗余計(jì)算,降低時(shí)間復(fù)雜度。研究發(fā)現(xiàn)在大部分網(wǎng)絡(luò)中進(jìn)化式鏈接擾動(dòng)的防御效果更高,尤其是分布估計(jì)算法,啟發(fā)式鏈接擾動(dòng)的精確度更高,這是意料之中的,因?yàn)樗脑O(shè)計(jì)原理就是針對(duì)預(yù)測(cè)結(jié)果中相似度排名較高的鏈接。最后作者證明了分布估計(jì)算法產(chǎn)生的鏈接干擾結(jié)果具有可轉(zhuǎn)移性,可抵御基于節(jié)點(diǎn)對(duì)之間的高階相似性的其他鏈路預(yù)測(cè)攻擊,例如deepWalk等部分節(jié)點(diǎn)嵌入算法。

3.2 基于魯棒性攻擊的逆鏈路預(yù)測(cè)方法

基于魯棒性攻擊的逆鏈路預(yù)測(cè)方法通常是研究者從理性的角度利用一些攻擊手段或其他的方法對(duì)鏈路預(yù)測(cè)模型進(jìn)行抗攻擊程度的分析,對(duì)鏈路預(yù)測(cè)方法的魯棒性進(jìn)行測(cè)試。

Wang等人[45]在論文中研究了幾種主流鏈路預(yù)測(cè)方法CN、AA、RA、LP及Katz,在多種網(wǎng)絡(luò)攻擊策略下的魯棒性,包括隨機(jī)攻擊(random attack,RDA),基于中心性的攻擊(centrality based attacks,CA),基于相似性的攻擊(similarity based attacks,SA)和基于模擬退火算法[65]的攻擊(simulated annealing based attack,SAA)。其中CA包括基于中介性的攻擊(betweenness based attack,BA)和基于權(quán)重的攻擊(weight based attack,WA)兩種。上述攻擊方法的具體做法是不斷刪除每種攻擊策略中計(jì)算得到的得分最大的鏈接。例如,SA中現(xiàn)有鏈接的重要性由相似度指標(biāo)的大小決定,在每一次操作中刪除當(dāng)前相似度最大的鏈接。刪除的鏈接數(shù)越多,預(yù)測(cè)的精確度越低。作者通過(guò)大量的實(shí)驗(yàn)測(cè)試得出結(jié)論,幾種攻擊方法中,通常 SAA具有最強(qiáng)的攻擊有效性,攻擊效率最高,其次是SA,最后是CA,有時(shí)某些CA攻擊策略的性能,例如基于中介性的攻擊(BA)甚至比 RDA還差,這是一個(gè)令人驚訝的結(jié)論,因?yàn)樵谄渌麍?chǎng)景中,BA策略已被證明非常有效[46]。實(shí)驗(yàn)發(fā)現(xiàn)攻擊對(duì)于鏈路預(yù)測(cè)的精度有巨大影響。在 5種基于相似性的鏈路預(yù)測(cè)方法中,RA可以比其他方法獲得更精確的預(yù)測(cè)效果,但是它非常容易受到網(wǎng)絡(luò)攻擊。因此作者得出鏈路預(yù)測(cè)方法魯棒性的重要結(jié)論: 具有高性能的鏈路預(yù)測(cè)方法可能具有較低的攻擊魯棒性,反之亦然。

Zhang等人[47]提出目前為止的鏈路預(yù)測(cè)方法驗(yàn)證主要在假定的無(wú)噪聲網(wǎng)絡(luò)中進(jìn)行,缺少對(duì)如果觀察到的網(wǎng)絡(luò)數(shù)據(jù)不再準(zhǔn)確將如何影響預(yù)測(cè)結(jié)果的清楚理解。在該文獻(xiàn)中,作者全面研究了在存在某些鏈路丟失,偽造或與其他鏈路交換的真實(shí)網(wǎng)絡(luò)中,現(xiàn)有基于局部信息相似性的鏈路預(yù)測(cè)算法的魯棒性。提出了一種指標(biāo)來(lái)量化和比較不同鏈路預(yù)測(cè)方法的魯棒性,它計(jì)算不同比例的噪聲數(shù)據(jù)下,預(yù)測(cè)精度曲線(xiàn)下的面積。其中,隨機(jī)噪聲和偏置噪聲均被考慮,噪聲實(shí)際上指的就是對(duì)網(wǎng)絡(luò)中的鏈路進(jìn)行改動(dòng)。在將真實(shí)網(wǎng)絡(luò)劃分為訓(xùn)練集ET和測(cè)試集EP之后,一些鏈接會(huì)隨機(jī)添加到ET或從ET中刪除。通過(guò)定義一個(gè)數(shù)量比率ratio,來(lái)測(cè)量隨機(jī)添加或刪除的鏈接占原訓(xùn)練集總鏈接數(shù)的比例。當(dāng)比率為正時(shí),條鏈接被隨機(jī)添加到訓(xùn)練集中; 當(dāng)比率為負(fù)時(shí),條鏈接從訓(xùn)練集中隨機(jī)刪除。為了保持網(wǎng)絡(luò)連接,ET中不能刪除太多鏈接,作者將范圍設(shè)定為 -4 0% ≤ratio≤ 1 00%。在隨機(jī)噪聲中可以觀察到,AUC通常隨的增大而減小。但在某些網(wǎng)絡(luò)中,隨機(jī)添加一些鏈接可以提高Jaccard方法的準(zhǔn)確性。這種現(xiàn)象與參考文獻(xiàn)[48]中的結(jié)果相似,可以通過(guò)添加一些鏈接來(lái)提高推薦的準(zhǔn)確性。造成這種情況的根本原因是隨機(jī)鏈接改善了網(wǎng)絡(luò)的連通性,使相似度矩陣更加密集,因此使用這些隨機(jī)添加的鏈接可以預(yù)測(cè)到許多由于連接性低而無(wú)法預(yù)測(cè)的鏈接。實(shí)驗(yàn)的另一觀察結(jié)果是,給定一種鏈路預(yù)測(cè)方法,在給定相同ratio的情況下,隨機(jī)刪除鏈接比隨機(jī)添加鏈接更具有破壞性。偏置噪聲的施加方式是隨機(jī)選擇兩個(gè)鏈接,a-b和c-d,然后將鏈接交換為a-d和c-b,通過(guò)這樣的方式保持節(jié)點(diǎn)度的大小不變,但可以使網(wǎng)絡(luò)隨機(jī)化。這種噪聲不會(huì)影響節(jié)點(diǎn)的度,但會(huì)更改網(wǎng)絡(luò)中的詳細(xì)連接。兩種噪聲處理的實(shí)驗(yàn)證明對(duì)于鏈路預(yù)測(cè)的準(zhǔn)確性,丟失的鏈接比偽造和交換的鏈接更具破壞性。在研究的基于相似性的鏈路預(yù)測(cè)方法中,某些方法的預(yù)測(cè)精度較低,但它們往往在“噪聲”的環(huán)境中更可靠。由于鏈接改動(dòng)造成的偏差會(huì)降低鏈路預(yù)測(cè)算法的準(zhǔn)確性,從而更加有必要考慮在網(wǎng)絡(luò)數(shù)據(jù)不干凈的網(wǎng)絡(luò)中鏈路預(yù)測(cè)算法的魯棒性。論文提出了一種稱(chēng)為算法魯棒性(algorithm robustness)的度量標(biāo)準(zhǔn),以量化鏈路預(yù)測(cè)算法可以在多大程度上抵抗網(wǎng)絡(luò)中的噪聲。

Pouya等人[49]為了分析鏈路預(yù)測(cè)模型的魯棒性和可解釋性,提出了一種對(duì)圖進(jìn)行對(duì)抗性修改的方法,引入了一種有效的方法通過(guò)近似嵌入結(jié)果發(fā)生的變化,來(lái)估計(jì)當(dāng)前改動(dòng)的效果,及對(duì)鏈路預(yù)測(cè)模型的影響大小。論文通過(guò)確定對(duì)鏈路預(yù)測(cè)模型影響性最大的修改方式來(lái)研究其可解釋性,并通過(guò)評(píng)估鏈路預(yù)測(cè)模型當(dāng)原網(wǎng)絡(luò)的鏈接發(fā)生添加或修改時(shí)的敏感性來(lái)研究其魯棒性。作者想設(shè)計(jì)一種方法,當(dāng)最小程度地更改圖結(jié)構(gòu)時(shí),可以使目標(biāo)鏈接重新獲得的嵌入結(jié)果有最大程度地改變,提出了一種稱(chēng)為通過(guò)對(duì)抗圖編輯實(shí)現(xiàn)的魯棒性和可解釋性(Completion Robustness and Interpretability via Adversarial Graph Edits,CRIAGE)的算法模型。首先,論文考慮了刪除目標(biāo)鏈接的相鄰鏈接這一干擾方式,來(lái)確定其中對(duì)目標(biāo)鏈接的預(yù)測(cè)影響最大的鏈接; 還研究了將假鏈接添加到網(wǎng)絡(luò)中的干擾方式,以評(píng)估鏈路預(yù)測(cè)模型對(duì)網(wǎng)絡(luò)發(fā)生少量鏈接添加時(shí)的魯棒性和敏感性。

還有一些關(guān)于鏈路預(yù)測(cè)算法魯棒性的結(jié)論。Marcin等人[50]在論文中評(píng)估了9種不同基于相似性的鏈路預(yù)測(cè)算法的攻擊耐受性,發(fā)現(xiàn)它們的彈性隨著網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的增加而趨于增加,隨著網(wǎng)絡(luò)平均度的降低而趨于降低。并且證明鏈路預(yù)測(cè)算法在較小的網(wǎng)絡(luò)和密度較高的網(wǎng)絡(luò)中操縱更容易受到攻擊的影響。

3.3 基于隱私保護(hù)的逆鏈路預(yù)測(cè)方法

基于隱私保護(hù)的逆鏈路預(yù)測(cè)方法是網(wǎng)絡(luò)中的個(gè)體或網(wǎng)絡(luò)發(fā)布者想要保護(hù)一些敏感連接或隱私關(guān)系而產(chǎn)生的方法。

Marcin等人[51]為社交平臺(tái)中的用戶(hù)設(shè)計(jì)了一種通過(guò)有策略地更改其鏈接,使得其某些敏感鏈接無(wú)法被成功預(yù)測(cè)的方法,該方法針對(duì)相似性的鏈路預(yù)測(cè)模型。論文提出了兩種啟發(fā)式方法,可以讓普通用戶(hù)輕松地在現(xiàn)有的社交媒體上應(yīng)用,且實(shí)驗(yàn)結(jié)果表明這些啟發(fā)式方法在各種網(wǎng)絡(luò)上以及針對(duì)大量鏈路預(yù)測(cè)算法的有效性。第一種方法稱(chēng)為移除封閉三角形(Closed-Triad-Removal,CTR),它從網(wǎng)絡(luò)中刪除有策略地選擇的鏈接,鏈接的刪除要使網(wǎng)絡(luò)中的封閉三角形個(gè)數(shù)減少。如果進(jìn)行刪除的鏈接會(huì)導(dǎo)致多個(gè)封閉三角形的消失,且每個(gè)封閉三角形都包含要隱藏的敏感鏈接,那么該算法甚至可以更有效。CTR方法的設(shè)計(jì)旨在通過(guò)檢查用戶(hù)可以刪除的所有可能選擇并刪除一個(gè)對(duì)敏感鏈接的隱藏最有效的鏈接,它的主要思想如圖3所示,如果社交平臺(tái)中用戶(hù)w希望隱藏他與x,y和z的關(guān)系,那么CTR建議w盡可能多地取消與x,y和z的朋友的好友關(guān)系。這種方法可以輕松地應(yīng)用于Facebook或ins中,因?yàn)槊總€(gè)用戶(hù)和他的任何朋友的共同總是可見(jiàn)的。在圖3中,通過(guò)刪除（v,w）在網(wǎng)絡(luò)中刪除了三個(gè)封閉三角形: 一個(gè)包含節(jié)點(diǎn)v,w,x,另一個(gè)包含v,w,y,第三個(gè)包含v,w,z,因此（w,x）,（w,y）和（w,z）的相似性得降低。

圖3 CTR啟發(fā)式方法的主要思想說(shuō)明Figure 3 An illustration of the main idea behind the CTR heuristic

另一種方法叫做創(chuàng)建開(kāi)放式三角形(Open-Triad-Creation,OTC),即通過(guò)添加新的鏈接形成不封閉的三角形。對(duì)于一條敏感連接e,OTC通過(guò)降低e的相似性得分來(lái)隱藏該鏈接,同時(shí)可以增加e附近某些不存在鏈接的相似性得分,這樣的方式同樣會(huì)降低e在所有不存在鏈接中,基于相似度的排名中的位置,從而降低鏈路預(yù)測(cè)算法識(shí)別出e的可能性。由于創(chuàng)建開(kāi)放式三角形可以增加其中不存在鏈接的相似性得分,因此通過(guò)添加新鏈接產(chǎn)生的開(kāi)放式三角形越多則越好,因?yàn)檫@可能會(huì)增加更多數(shù)量的不存在鏈接的相似性得分。根據(jù)這一觀察結(jié)果,OTC會(huì)檢查用戶(hù)可進(jìn)行添加的所有可能選擇,并添加一條導(dǎo)致敏感鏈接在不存在鏈接中排名最大程度降低的鏈接。它的主要思想如圖4所示,（v,w）的添加會(huì)創(chuàng)建兩個(gè)開(kāi)放的三角形: 一個(gè)包含節(jié)點(diǎn)x,v,w; 另一個(gè)包含v,w,y。因此,（x,w）和（y,v）的相似性得分增加,而（w,u）的相似性得分降低。OTC可以通過(guò)一種簡(jiǎn)單的方式應(yīng)用于流行的社交媒體平臺(tái)。例如,如果用戶(hù)u和w希望隱藏他們的關(guān)系,那么他們中的任何一個(gè)(例如w)都可以向好友列表中包含盡可能多的與自己無(wú)關(guān)的人的用戶(hù)發(fā)送好友請(qǐng)求。 即使很難找到這樣的人,仍然可以向高度聯(lián)系的陌生人發(fā)送隨機(jī)的友誼請(qǐng)求,希望其中一些人會(huì)接受該請(qǐng)求,這種做法是合理的,因?yàn)楣烙?jì)有55%的人在Facebook上接受來(lái)自完全陌生人的友誼請(qǐng)求[75]。兩種啟發(fā)式方法在實(shí)踐中都是有效的,前者通常比后者更有效一些。最后作者評(píng)估了 9種不同的基于相似性的鏈路預(yù)測(cè)算法的攻擊耐受性,發(fā)現(xiàn)它們的彈性隨著網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的增加而趨于增加,而隨著網(wǎng)絡(luò)平均度的降低而趨于降低。他們?cè)诹硪黄撐闹羞M(jìn)行了補(bǔ)充性的研究[50],表明有策略地選擇要修改的鏈接非常關(guān)鍵,因?yàn)殡S機(jī)地重新建立鏈接可能最終暴露出個(gè)人的敏感關(guān)系而不是隱藏所討論的鏈接,突出了有策略選擇的重要性。

圖4 OTC啟發(fā)式方法的主要思想說(shuō)明Figure 4 An illustration of the main idea behind the OTC heuristic

本文作者蔣忠元等在文獻(xiàn)[54]中提出目標(biāo)隱私保護(hù)概念。實(shí)際網(wǎng)絡(luò)中,并非所有鏈接都是敏感的,往往只有一小部分鏈接是重要且敏感的,亟需隱私保護(hù)。因此,我們將此類(lèi)少量的重要且敏感的鏈接定義為目標(biāo),因?yàn)樗鼈兺枪粽叩墓魧?duì)象。我們提出基于網(wǎng)絡(luò)模體(motif)的節(jié)點(diǎn)相似性定義,其中模體是實(shí)際網(wǎng)絡(luò)構(gòu)建的單元,比如三角形、四邊形等。將兩個(gè)節(jié)點(diǎn)的相似性定義為包含該兩個(gè)節(jié)點(diǎn)間鏈路的某種模型的數(shù)量值,比如參與的三角形個(gè)數(shù),即常用的基于共同鄰居的相似性。目標(biāo)集的隱私函數(shù)定義為所有目標(biāo)在當(dāng)前網(wǎng)絡(luò)中的相似度之和。

實(shí)現(xiàn)目標(biāo)隱私保護(hù)的主要步驟有: 1)從網(wǎng)絡(luò)中刪除目標(biāo)集,但僅刪除目標(biāo)遠(yuǎn)遠(yuǎn)不夠,因?yàn)楝F(xiàn)有鏈路預(yù)測(cè)算法可以有效預(yù)測(cè)出隱藏的目標(biāo),因此需要進(jìn)行步驟2); 2)刪除一定數(shù)量(預(yù)算,budget)的其他鏈路(被稱(chēng)為保護(hù)者,Protector)來(lái)進(jìn)一步保護(hù)隱藏的目標(biāo),使得現(xiàn)有的鏈路算法難以預(yù)測(cè)出隱藏的目標(biāo)。

論文主體上探討了三種場(chǎng)景下的目標(biāo)隱私保護(hù)問(wèn)題,分別為: 1)單全局預(yù)算的保護(hù)鏈路選擇; 2)多局部預(yù)算的跨目標(biāo)鏈路選擇; 3)多局部預(yù)算的順序目標(biāo)鏈路選擇。論文對(duì)三種場(chǎng)景下多目標(biāo)隱私保護(hù)分別進(jìn)行了數(shù)學(xué)建模,并理論證明了保護(hù)鏈路選擇具有單調(diào)性和子模性,并提出相應(yīng)的貪婪算法進(jìn)行求解。為了進(jìn)一步提高計(jì)算速度,作者所有貪婪算法進(jìn)行了加速,并通過(guò)大量的實(shí)驗(yàn)驗(yàn)證。

此外,作者對(duì)網(wǎng)絡(luò)的可用性(utility)從端到端的距離、核數(shù)、特征值、模塊度等方面進(jìn)行了評(píng)估,研究發(fā)現(xiàn),目標(biāo)隱私保護(hù)一般針對(duì)少量的重要目標(biāo)進(jìn)行隱私保護(hù),隱私保護(hù)后的網(wǎng)絡(luò)的可用性可以得到很好的保持。

更進(jìn)一步,作者還證明了在其他相似性指標(biāo)(比如RA,AA等)下以及其他網(wǎng)絡(luò)結(jié)構(gòu)擾動(dòng)機(jī)制(比如增加鏈路、重連鏈路)下隱私函數(shù)是否具有單調(diào)性與子模性。

進(jìn)一步地,作者在文獻(xiàn)[55]中提出基于路徑的相似性指標(biāo)(其與Katz指標(biāo)不同,其選擇的路徑不包含回路)。定義了目標(biāo)集的隱私函數(shù),通過(guò)理論證明了該隱私函數(shù)具有單調(diào)性與子模性,進(jìn)而提出貪婪算法可求得近似解。然而貪婪算法需要計(jì)算節(jié)點(diǎn)間符合一定路徑長(zhǎng)度的所有路徑,在大規(guī)模網(wǎng)絡(luò)中變得不可用。作者提出使用無(wú)回路隨機(jī)游走(self-avoid random walk)方法對(duì)需要保護(hù)的節(jié)點(diǎn)對(duì)之間的路徑進(jìn)行采樣?；诓蓸拥玫降穆窂郊?論文提出的貪婪方法依然具有單調(diào)性與子模性,在采樣次數(shù)達(dá)到一定數(shù)量后,得到的結(jié)果與群舉法得到的結(jié)果非常相近,但計(jì)算速度提升了成百上千倍。

本章節(jié)詳細(xì)介紹了現(xiàn)有的逆鏈路預(yù)測(cè)算法的原理及核心貢獻(xiàn),并在表2中對(duì)上述的所有逆鏈路預(yù)測(cè)方法進(jìn)行了簡(jiǎn)單的對(duì)比與總結(jié),便于參考。

表2 現(xiàn)有逆鏈路預(yù)測(cè)方法的對(duì)比與總結(jié)Table 2 Comparison and summary of existing reverse link prediction methods

4 逆鏈路預(yù)測(cè)的防御

隨著近年來(lái)逆鏈路預(yù)測(cè)方法的出現(xiàn),一些方法確實(shí)在隱私保護(hù)方面發(fā)揮了重要的作用,然而,存在惡意攻擊者利用現(xiàn)有的逆鏈路預(yù)測(cè)方法對(duì)鏈路預(yù)測(cè)模型進(jìn)行攻擊,以達(dá)到他們危害性的目的。因此,對(duì)衡量并提高鏈路預(yù)測(cè)算法的魯棒性,研究鏈路預(yù)測(cè)對(duì)抗的防御方法的需求日益迫切。目前,在這一方面的有關(guān)研究非常少,本章節(jié)將對(duì)這些防御方法進(jìn)行介紹。

Chen等人[52]在這篇論文中第一次討論針對(duì)網(wǎng)絡(luò)對(duì)抗攻擊的防御方法,為GNN提出針對(duì)網(wǎng)絡(luò)對(duì)抗攻擊的防御策略。論文針對(duì)全局性和目標(biāo)性的對(duì)抗性攻擊提出了不同的防御策略,并通過(guò)大量實(shí)驗(yàn)測(cè)試了其防御效率。所提出的防御策略的核心是平滑GNN訓(xùn)練過(guò)程中的梯度信息,因此減小了可用于形成對(duì)抗網(wǎng)絡(luò)的梯度的幅度。這篇論文與文獻(xiàn)[41]中應(yīng)用的網(wǎng)絡(luò)對(duì)抗攻擊方法對(duì)應(yīng)。作者提出了四種防御策略,為網(wǎng)絡(luò)提供多樣化的防御。針對(duì)全局網(wǎng)絡(luò)攻擊,提出了全局對(duì)抗訓(xùn)練(Global Adversarial Training,Global-AT)以提高 DNN 的魯棒性,并針對(duì)目標(biāo)性網(wǎng)絡(luò)攻擊提出了目標(biāo)對(duì)抗訓(xùn)練(Target Label Adversarial Training,Target-AT)的方法。 此外,還有平滑蒸餾和平滑交叉熵?fù)p失函數(shù)兩種防御策略來(lái)實(shí)現(xiàn)梯度掩蓋,這使攻擊者很難利用模型的梯度信息來(lái)構(gòu)造攻擊。

Zhou等人[5]從博弈論的研究角度提出了一種用來(lái)提高基于相似性的鏈路預(yù)測(cè)的魯棒性的方法,通過(guò)為對(duì)網(wǎng)絡(luò)進(jìn)行鏈路預(yù)測(cè)的分析人員提供一組有限的可靠查詢(xún),這些可靠查詢(xún)可以精確地獲取所查詢(xún)鏈接是否存在。分析人員旨在通過(guò)最佳地利用可靠的查詢(xún)來(lái)穩(wěn)健地預(yù)測(cè)可能的鏈接的集合,要進(jìn)行可靠查詢(xún)的鏈接集需要有策略地選取。論文借助貝葉斯斯坦博格博弈模型對(duì)分析人員(防御方)與隱藏鏈接者(攻擊方)的策略和收益進(jìn)行分析,在該博弈中,分析人員首先可以進(jìn)行可靠的查詢(xún),接下來(lái)對(duì)手刪除網(wǎng)絡(luò)中剩余的一部分鏈接。模型中分析人員不能確定對(duì)手試圖隱藏的特定目標(biāo)鏈接,而對(duì)手則具有有關(guān)分析人員和網(wǎng)絡(luò)的完整信息。首先對(duì)網(wǎng)絡(luò)數(shù)據(jù)收集進(jìn)行建模,分析人員提交一組節(jié)點(diǎn)對(duì)查詢(xún)并會(huì)獲得每個(gè)查詢(xún)是存在的連接或不存在的鏈接的響應(yīng),基于查詢(xún)結(jié)果,假設(shè)分析人員將構(gòu)建一個(gè)子圖并使用相似性度量來(lái)評(píng)估不在查詢(xún)集中的鏈接存在的可能性。在論文方法的設(shè)置中,攻擊者可以通過(guò)將有限查詢(xún)子集的鏈接進(jìn)行刪除的方式來(lái)修改查詢(xún)結(jié)果,以隱藏目標(biāo)鏈接。例如,犯罪分子會(huì)恐嚇一些調(diào)查者,以使他們不透露已知的隱秘關(guān)系。為了應(yīng)對(duì)此類(lèi)攻擊,作者假設(shè)分析人員可以使他們的查詢(xún)子集可靠,例如,他們可以通過(guò)多次調(diào)查以及其他方式(比如監(jiān)視通信)來(lái)確定特定的關(guān)系,從而顯著降低攻擊者成功隱藏現(xiàn)有鏈接的可能性。實(shí)驗(yàn)證明了攻擊者進(jìn)行的攻擊不會(huì)總是損害防御者,由于這是一個(gè)非零和博弈,因此在某些情況下攻擊實(shí)際上可能會(huì)增加防御者的收益。在攻擊會(huì)降低防御者收益的情況下,論文提出了一種啟發(fā)式算法僅通過(guò)一小部分可靠的鏈接查詢(xún)就可以大大減少攻擊的損害,論文同時(shí)也表明,如果不仔細(xì)選擇要進(jìn)行可靠查詢(xún)的鏈接,該方法可能不會(huì)有較好的效果,特別地,增加隨機(jī)選擇的可靠查詢(xún)的數(shù)量有時(shí)可能會(huì)降低防御者的收益。

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

在本節(jié)中,我們將介紹逆鏈路預(yù)測(cè)任務(wù)中常見(jiàn)的度量標(biāo)準(zhǔn)、數(shù)據(jù)集以及一些對(duì)照方法,這些指標(biāo)和方法有些用于攻擊任務(wù)中,另一些則用于防御方案中。對(duì)照方法是多篇論文實(shí)驗(yàn)中都采用了的用于突顯新提出算法優(yōu)越性的基礎(chǔ)方法,特別地,它們是針對(duì)攻擊任務(wù)的對(duì)照方法。

5.1 常用指標(biāo)

精確度(Precision)[67]。它是鏈路預(yù)測(cè)中最基礎(chǔ)常用的指標(biāo),計(jì)算的是在前k個(gè)預(yù)測(cè)結(jié)果中被成功預(yù)測(cè)的鏈接比例。如果有m個(gè)預(yù)測(cè)是準(zhǔn)確的,即排在前k的預(yù)測(cè)結(jié)果中有m個(gè)在測(cè)試集。

AUC值(Area Under Curve)[66]。它的大小是ROC曲線(xiàn)與坐標(biāo)軸圍成的圖形的面積。AUC值計(jì)算的意義是隨機(jī)選擇出一對(duì)正負(fù)樣本時(shí),正樣本的預(yù)測(cè)得分高于負(fù)樣本的機(jī)率。隨機(jī)地選取一條測(cè)試集中的邊作為正樣本,再?gòu)木W(wǎng)絡(luò)所有不存在的鏈接中隨機(jī)選取一條作為負(fù)樣本,若正樣本的預(yù)測(cè)得分大于負(fù)樣本,那么就加1,若二者相等則加0.5,若負(fù)樣本的預(yù)測(cè)指標(biāo)值大于了正樣本則不加分。假如正負(fù)樣本比較了n次,其中n'次正樣本預(yù)測(cè)指標(biāo)值大于負(fù)樣本,n''次兩者值相等,那么AUC指標(biāo)的計(jì)算公式定義如下:

排序得分(Ranking Score)[68]。它主要考慮測(cè)試集中的邊在預(yù)測(cè)結(jié)果最終排序中的位置。令H為測(cè)試集中的邊和網(wǎng)絡(luò)中不存在的邊的并集,ri表示測(cè)試集中鏈接i∈EP在排序中的排名。則該條未知邊的Ranking Score值為遍歷所有測(cè)試集中的鏈接,得到系統(tǒng)的Ranking Score值為:

這些指標(biāo)常用于鏈路預(yù)測(cè)任務(wù),但有時(shí)也會(huì)用來(lái)測(cè)試逆鏈路預(yù)測(cè)任務(wù)的有效性。

5.2 攻擊和防御的指標(biāo)

攻擊成功率(Attack Success Rate,ASR),用于衡量攻擊的有效性。ASR是在一定的鏈接干擾預(yù)算內(nèi)成功攻擊目標(biāo)的比率。也就是修改鏈接使得成功隱藏的目標(biāo)鏈接與所有目標(biāo)鏈接的比率。ASR越大,攻擊效果越好。ASR的公式如下:

平均防御率(average defense rate,ADR),用于衡量防御的有效性。即有防御和無(wú)防御時(shí)攻擊的 ASR之差與無(wú)防御時(shí)攻擊的ASR之比。ADR越高,防御效果越好。

損失預(yù)防率(Damage Prevention Ratio,DPR)是用博弈論分析提高鏈路預(yù)測(cè)算法魯棒性的論文中提出的指標(biāo)。預(yù)防損失的定義是衡量可以通過(guò)防御預(yù)防的損失程度。假設(shè)L0是防御者在沒(méi)有攻擊時(shí)的損失,LA是攻擊策略 A下的防御者的損失,LD是防御策略D下的防御者的損失。更好的防御策略會(huì)得到更大的DPR。

平均修改鏈接(Average Modified Links,AML),用于衡量攻擊算法的效率。 AML是為網(wǎng)絡(luò)拓?fù)涔舳O(shè)計(jì)的,它表示成功攻擊時(shí)的平均干擾的鏈接數(shù)量的大小。假設(shè)攻擊者用于攻擊目標(biāo)網(wǎng)絡(luò)的可以干擾的鏈接數(shù)量有限,那么經(jīng)過(guò)修改的鏈接(添加或刪除)數(shù)量會(huì)一直累積,直到攻擊者達(dá)到目標(biāo)或預(yù)算用完為止。

算法魯棒性,用于量化鏈路預(yù)測(cè)算法可以在多大程度上抵抗網(wǎng)絡(luò)中的虛假連接。即公式(8)。

5.3 常用數(shù)據(jù)集

表3總結(jié)了逆鏈路預(yù)測(cè)研究中常用到的一些數(shù)據(jù)集,可以看出它們大部分都是規(guī)模較小的網(wǎng)絡(luò)。

5.4 對(duì)照方法

隨機(jī)攻擊(Random Attack,RAN),分為鏈接重寫(xiě)和鏈接交換兩種。鏈接重寫(xiě)是隨機(jī)刪除原始網(wǎng)絡(luò)中的鏈接,同時(shí)隨機(jī)連接最初未連接的節(jié)點(diǎn)對(duì)。鏈接交換指的是每次隨機(jī)抽取兩個(gè)節(jié)點(diǎn)對(duì),交叉連接,這樣可以保持所有節(jié)點(diǎn)的度不變,但網(wǎng)絡(luò)的連接方式卻發(fā)生了無(wú)變化。RAN是最簡(jiǎn)單的攻擊方法,經(jīng)常作為對(duì)照方法用于突顯新算法優(yōu)越性。

相似性攻擊(similarity based attacks,SA),可以利用基于相似性的具體鏈路預(yù)測(cè)方法作為攻擊方法進(jìn)行鏈接刪除與新算法對(duì)比,比如,基于共同鄰居的攻擊(Common-Neighbor-based Attack,CNA),也經(jīng)常作為對(duì)照方法。

6 未來(lái)的研究方向

目前,針對(duì)逆鏈路預(yù)測(cè)問(wèn)題所進(jìn)行的研究并不多,在這一領(lǐng)域仍有廣闊的研究前景,存在許多值得通過(guò)觀察現(xiàn)有研究方法進(jìn)行研究的問(wèn)題。在本節(jié)中,我們嘗試介紹幾個(gè)主要的研究方向。我們將從逆鏈路預(yù)測(cè)研究中的攻擊、防御以及評(píng)價(jià)指標(biāo)的角度分別進(jìn)行闡述。

高效有效的算法。從目前提出的攻擊方法來(lái)看,最常用的數(shù)據(jù)集通常是較小的網(wǎng)絡(luò)。當(dāng)前,大多數(shù)提議的方法都無(wú)法攻擊大型圖,原因是它們需要處理大量的網(wǎng)絡(luò)信息,從而導(dǎo)致了較高的時(shí)間復(fù)雜度。為了解決這個(gè)問(wèn)題,文獻(xiàn)[44]做出了一些努力,即只計(jì)算相似度發(fā)生變化的鏈接集,進(jìn)行了增量更新,從而避免了冗余計(jì)算,同時(shí)保持了有效的攻擊性能。然而,該方法目前也尚不適用于較大規(guī)模的網(wǎng)絡(luò),在大網(wǎng)絡(luò)上執(zhí)行效率較低。鑒于無(wú)法在大規(guī)模網(wǎng)絡(luò)上進(jìn)行攻擊的缺點(diǎn),研究一種更有效且高效的攻擊方法來(lái)解決這一實(shí)際問(wèn)題是非常必要的。

可轉(zhuǎn)移性。由于現(xiàn)有的鏈路預(yù)測(cè)方法有較多的種類(lèi),其中,每一種又有許多不同的模型,因此,探討所提出逆鏈路預(yù)測(cè)方法的可轉(zhuǎn)移性也越來(lái)越受到研究者的重視,目前已經(jīng)有一些具有可轉(zhuǎn)移性的攻擊方法被提出。具有可轉(zhuǎn)移性的逆鏈路預(yù)測(cè)方法同時(shí)也具有更廣闊的應(yīng)用場(chǎng)景,因此研究一種攻擊性強(qiáng)且具有可轉(zhuǎn)移性的方法是一個(gè)值得思考的研究方向。

逆鏈路預(yù)測(cè)的防御任務(wù)。目前只有少數(shù)文獻(xiàn)[52-53]嘗試研究和改善網(wǎng)絡(luò)中的鏈路預(yù)測(cè)任務(wù)模型的魯棒性,并提出有效的防御方法。因此,對(duì)于改進(jìn)各種預(yù)測(cè)模型的魯棒性,提出現(xiàn)有逆鏈路預(yù)測(cè)方法的防御方法或?qū)?dāng)前防御方法轉(zhuǎn)移給其他模型具有寶貴的思考價(jià)值。

攻擊成本計(jì)量。當(dāng)前沒(méi)有太多指標(biāo)可用來(lái)研究攻擊模型的效率。已知的方法通過(guò)所修改鏈接的數(shù)量粗略地衡量了成本,引發(fā)了今后更多的對(duì)于設(shè)計(jì)一個(gè)計(jì)量攻擊成本的指標(biāo)的思考,即是否存在另一個(gè)角度來(lái)更精確地量化攻擊和防御的成本。在真實(shí)的網(wǎng)絡(luò)中,通常添加鏈接的成本與刪除鏈接的成本是不同的,因此這兩種鏈接修改方式的成本不同,這需要一些更合理的評(píng)估指標(biāo)。

鏈路預(yù)測(cè)與逆鏈路預(yù)測(cè)的博弈。鏈路預(yù)測(cè)有助于數(shù)據(jù)挖掘與豐富應(yīng)用,但存在隱私泄露,造成網(wǎng)絡(luò)安全風(fēng)險(xiǎn)。逆鏈路預(yù)測(cè)可加強(qiáng)敏感信息的隱私保護(hù)或提高網(wǎng)絡(luò)安全系數(shù),但降低了網(wǎng)絡(luò)鏈路的可預(yù)測(cè)性。二者之間需要平衡或折中,這屬于博弈范疇,有待廣大學(xué)者深入研究。

隱私保護(hù)與網(wǎng)絡(luò)可用性。當(dāng)前,逆鏈路預(yù)測(cè)方法以擾動(dòng)網(wǎng)絡(luò)結(jié)構(gòu)為主,會(huì)造成網(wǎng)絡(luò)的可用性(utility)下降?，F(xiàn)有少量逆鏈路預(yù)測(cè)機(jī)制考慮了網(wǎng)絡(luò)的可用性,并進(jìn)行了評(píng)估。但大多機(jī)制缺乏系統(tǒng)的分析與評(píng)估,在未來(lái)研究工作中有待進(jìn)一步加強(qiáng)。

7 總結(jié)

逆鏈路預(yù)測(cè)方法的研究具有巨大的潛力,在近年來(lái)引發(fā)了越來(lái)越多的關(guān)注。通過(guò)總結(jié)現(xiàn)有的經(jīng)驗(yàn)和研究來(lái)加深對(duì)于逆鏈路預(yù)測(cè)的理解是非常重要的,這些理解不僅可以提供有關(guān)攻擊和防御策略的知識(shí),而且還可以為后續(xù)的研究提供設(shè)計(jì)的思路和見(jiàn)解。

本文對(duì)現(xiàn)有的逆鏈路預(yù)測(cè)方法及其防御對(duì)策進(jìn)行了綜合性的討論。我們對(duì)這一方面的研究進(jìn)行了完整的綜述,總結(jié)了現(xiàn)有作品的核心貢獻(xiàn),并根據(jù)合理的標(biāo)準(zhǔn)在攻擊和防御任務(wù)方面從系統(tǒng)的角度對(duì)它們進(jìn)行了分類(lèi)闡述,并且對(duì)現(xiàn)有研究的相關(guān)評(píng)價(jià)指標(biāo)進(jìn)行了系統(tǒng)梳理與對(duì)比分析,對(duì)可用的網(wǎng)絡(luò)資源及對(duì)照方法等進(jìn)行了梳理與介紹,最后綜合分析了現(xiàn)有逆鏈路預(yù)測(cè)方法的優(yōu)劣性,展望了未來(lái)可能的研究方向。