王 慧，樂孜純，龔 軒，武玉坤，左 浩

1(浙江工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，杭州 310023)2(江西理工大學(xué) 應(yīng)用科學(xué)學(xué)院，江西 贛州 341000)3(浙江工業(yè)大學(xué) 理學(xué)院，杭州 310023)

1 引 言

網(wǎng)絡(luò)數(shù)據(jù)挖掘作為一項(xiàng)主流的、重要的數(shù)據(jù)挖掘技術(shù)，主要包括社區(qū)檢測(cè)、結(jié)構(gòu)網(wǎng)絡(luò)分析、網(wǎng)絡(luò)可視化.其中最有趣的一個(gè)研究方向是鏈路預(yù)測(cè)LP，LP在計(jì)算機(jī)領(lǐng)域已有一些研究成果，它處理的是信息科學(xué)中最基本的問題—缺失信息，虛假信息，新增信息，關(guān)鍵鏈路的預(yù)測(cè).該問題從已觀察到的網(wǎng)絡(luò)結(jié)構(gòu)、節(jié)點(diǎn)屬性、圖結(jié)構(gòu)特征入手，預(yù)測(cè)存在但未被觀察到，錯(cuò)過或者未來可能會(huì)出現(xiàn)或消失的鏈路，這是一個(gè)有意義的研究方向.他們采用的主要技術(shù)和方法是機(jī)器學(xué)習(xí)、基于圖的深度學(xué)習(xí)和Markov鏈.2000年Sarukkai[1]等人提出了利用Markov鏈進(jìn)行概率鏈路預(yù)測(cè)，將強(qiáng)大的概率模型應(yīng)用于Web路徑分析和鏈路預(yù)測(cè).2003年，Popescul等人[2]提出了一種結(jié)構(gòu)邏輯回歸(SLR)方法，利用引文信息、正文標(biāo)題、摘要、作者姓名和所屬單位，以及會(huì)議和期刊的名稱等外部信息預(yù)測(cè)文獻(xiàn)之間的引用關(guān)系.2004年Zhu等人[3]使用Markov模型進(jìn)行鏈路預(yù)測(cè)，以幫助新用戶瀏覽網(wǎng)站，提出了一種轉(zhuǎn)移概率矩陣壓縮算法進(jìn)一步提高了鏈路預(yù)測(cè)的效率.此外，應(yīng)用節(jié)點(diǎn)屬性的預(yù)測(cè)方法也有很多，例如Lin[4]通過節(jié)點(diǎn)的屬性特征確定節(jié)點(diǎn)間的相似性，認(rèn)為屬性越相似的節(jié)點(diǎn)越可能產(chǎn)生鏈接.2018年Zhang[5]等人基于圖的深度學(xué)習(xí)來研究鏈路預(yù)測(cè)問題.研究成果表明應(yīng)用節(jié)點(diǎn)屬性，圖結(jié)構(gòu)特征等外部信息的確可以得到很好的預(yù)測(cè)效果.雖然各領(lǐng)域的專家們提出了許多的鏈路預(yù)測(cè)方法，但是結(jié)合這些方法的綜述文章卻非常少.

盡管在2010年至2018年間呂琳媛周濤等研究人員相繼提出了一些關(guān)于復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)的綜述文章，但是這些文章主要強(qiáng)調(diào)從物理學(xué)角度的貢獻(xiàn).例如：2010年9月呂琳媛[6,7]在電子科技大學(xué)學(xué)報(bào)發(fā)表了一篇綜述文章，該篇文章介紹了基于最大似然估計(jì)的鏈路預(yù)測(cè)，基于相似性的鏈路預(yù)測(cè)和基于概率模型的鏈路預(yù)測(cè).同年，呂琳媛，周濤[8]在Physica A發(fā)表了一篇名為《Link Prediction in Complex Networks：A Survey》的文章，文章綜述了鏈路預(yù)測(cè)的研究進(jìn)展及常用的算法，提出了基于隨機(jī)游走的方法和最大似然方法，介紹了三種典型應(yīng)用，網(wǎng)絡(luò)重構(gòu)、網(wǎng)絡(luò)演化機(jī)制和標(biāo)記分類.隨后2015年5月張斌和馬費(fèi)成[9]在中國(guó)圖書館學(xué)報(bào)發(fā)表了一篇名為《科學(xué)知識(shí)網(wǎng)絡(luò)中的鏈路預(yù)測(cè)研究述評(píng)》，該篇文章以“科學(xué)知識(shí)網(wǎng)絡(luò)中的鏈路預(yù)測(cè)”為主要對(duì)象，對(duì)鏈路預(yù)測(cè)的類型、研究思路和方法進(jìn)行了綜述.2016年Cubero[10]在ACM Computing Surveys期刊發(fā)表了一篇《A Survey of Link Prediction in Complex Network》的綜述文章，該篇文章把當(dāng)前的鏈路預(yù)測(cè)技術(shù)分為四類，分別為基于相似性的方法、基于概率和統(tǒng)計(jì)的方法、計(jì)算方法、預(yù)處理的方法，并對(duì)每種方法的復(fù)雜度和精確度進(jìn)行了詳細(xì)的分析.以上這些文章主要采用網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)作為輸入特征，計(jì)算簡(jiǎn)單，復(fù)雜度低，在物理學(xué)的視角分析復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)，強(qiáng)調(diào)物理學(xué)家近年來的研究成果.

2016年4月呂琳媛，任曉龍和周濤[11]在中國(guó)計(jì)算機(jī)學(xué)會(huì)通訊發(fā)表了一篇綜述文章，該篇文章除了介紹了物理學(xué)的研究方法外，還介紹了信息學(xué)中的鏈路預(yù)測(cè)方法即基于機(jī)器學(xué)習(xí)的方法，該方法包括三部分：基于概率圖模型的鏈路預(yù)測(cè)、基于特征分類的鏈路預(yù)測(cè)和基于矩陣分解的鏈路預(yù)測(cè).這篇文章雖然涉及到了一些信息學(xué)中的鏈路預(yù)測(cè)方法，但是沒有涉及當(dāng)前最新的基于圖特征的深度學(xué)習(xí)鏈路預(yù)測(cè)技術(shù).到目前為止，從信息學(xué)的角度分析復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)的綜述少之又少，本文試圖從信息學(xué)的視角全面分析在計(jì)算機(jī)領(lǐng)域許多經(jīng)典的和最新的鏈路預(yù)測(cè)技術(shù)，并對(duì)這些鏈路預(yù)測(cè)技術(shù)進(jìn)行了系統(tǒng)的分類，把分層的思想引入分類模型的創(chuàng)建，將分類模型分為三層，輸入層，處理層和輸出層，其中：輸入層包括輸入元數(shù)據(jù)(網(wǎng)絡(luò)結(jié)構(gòu)，屬性特征，標(biāo)簽，中心性，角色，社區(qū)和語義信息).處理層包括常用的監(jiān)督，半監(jiān)督，無監(jiān)督和強(qiáng)化學(xué)習(xí)技術(shù).輸出層包括邊，子圖和全圖信息.

本文的組織結(jié)構(gòu)如下：下一節(jié)介紹了常用的鏈路預(yù)測(cè)方法，提出了一種新的鏈路預(yù)測(cè)分類模型，對(duì)計(jì)算機(jī)領(lǐng)域常用的、經(jīng)典的、最新的鏈路預(yù)測(cè)算法進(jìn)行了分類，對(duì)其復(fù)雜性、輸入特征和開源實(shí)現(xiàn)進(jìn)行了詳細(xì)的分析.第三節(jié)分析了鏈路預(yù)測(cè)未來的發(fā)展方向.第四節(jié)給出了結(jié)論.

2 常用的鏈路預(yù)測(cè)方法

2.1 分層模型

從信息學(xué)的角度分析復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)，這是一個(gè)典型的二分類問題，令x，y∈V為圖G(V，E)中的節(jié)點(diǎn)，l(x，y)為節(jié)點(diǎn)對(duì)實(shí)例(x，y)的標(biāo)簽，如果節(jié)點(diǎn)之間存在鏈接，那么這對(duì)節(jié)點(diǎn)標(biāo)記為正鏈接，否則，這對(duì)節(jié)點(diǎn)標(biāo)記為負(fù)鏈接.

本文把當(dāng)前信息學(xué)中的鏈路預(yù)測(cè)方法按分層模型進(jìn)行劃分(如圖1所示).該模型分為三層，輸入層，處理層和輸出層.

圖1 復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)分層模型 Fig.1 Link prediction hierarchical model for complex networks

2.1.1 第一層輸入層

特征選取和特征輸入是分類問題中的首要問題，因此選擇輸入層作為分層模型的第一層，目前研究較多的輸入特征主要包括基于節(jié)點(diǎn)與邊的屬性特征、圖形(像)特征、基于節(jié)點(diǎn)所處網(wǎng)絡(luò)的拓?fù)涮卣骱洼o助特征.下面分別介紹常用的4種不同類型的輸入特征.

1)網(wǎng)絡(luò)結(jié)構(gòu)

對(duì)于輸入的元數(shù)據(jù)其中有部分是采用基于網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)信息，Liben-Nowell和Kleinberg[12]討論了基于圖的結(jié)構(gòu)特點(diǎn)，在他們的工作之后，提出了許多基于拓?fù)涞亩攘糠椒?根據(jù)這些度量的特征可以分為基于共同鄰居的度量和基于路徑的度量.

2013年王等人[13]發(fā)表了一篇名為《Similarity index based on the information of neighbor nodes for link prediction of complex network》的文章，該篇文章提出了一種基于共同鄰居節(jié)點(diǎn)對(duì)邊的貢獻(xiàn)的新指標(biāo)，并證明了該指標(biāo)具有較好的預(yù)測(cè)能力，具有較低的復(fù)雜度，特別是對(duì)于聚類系數(shù)較低的網(wǎng)絡(luò)，具有較好的預(yù)測(cè)效率.

2009年呂琳媛和周濤[14]等人提出了一種局部路徑指標(biāo)來評(píng)估兩個(gè)節(jié)點(diǎn)之間存在鏈接的可能性.與公共鄰域CN和Katz指標(biāo)相比，局部路徑指數(shù)具有較高的有效性和效率.

2)屬性特征

許多研究表明，使用節(jié)點(diǎn)和鏈接的文本或圖形屬性(如用戶的年齡、興趣、照片等)作為輸入特征可以顯著提高鏈路預(yù)測(cè)的性能.

李等人[15]提出了一種基于圖核的學(xué)習(xí)方法使用年齡、受教育程度、關(guān)鍵詞作為輸入特征，取得了較好的預(yù)測(cè)效果.

Scellato[16]等人在基于位置的社交網(wǎng)絡(luò)中考慮了社會(huì)特征、地點(diǎn)特征和全局特征，利用監(jiān)督的學(xué)習(xí)框架進(jìn)行鏈路預(yù)測(cè).

3)標(biāo)簽

標(biāo)簽特征包括節(jié)點(diǎn)標(biāo)簽和邊標(biāo)簽.2007年Raghavan和Albert[17]等人提出了一種基于網(wǎng)絡(luò)的簡(jiǎn)單標(biāo)簽傳播算法用于解決鏈路預(yù)測(cè)問題，它以節(jié)點(diǎn)標(biāo)簽作為輸入的元數(shù)據(jù)，每個(gè)節(jié)點(diǎn)都初始化為唯一的標(biāo)簽，假設(shè)一個(gè)網(wǎng)絡(luò)中的節(jié)點(diǎn)X有K個(gè)鄰居，X的每個(gè)鄰居都有一個(gè)標(biāo)簽，來顯示它們各自的屬性歸屬于哪個(gè)社區(qū).算法規(guī)定每個(gè)節(jié)點(diǎn)都選擇加入那個(gè)所有直接鄰居中標(biāo)簽數(shù)據(jù)最多的那個(gè)社區(qū).最終，在同一個(gè)社區(qū)中包含了相同標(biāo)簽的節(jié)點(diǎn)群.該標(biāo)簽傳播算法具有較低的時(shí)間復(fù)雜度，能較好的捕捉網(wǎng)絡(luò)的動(dòng)態(tài)演化，對(duì)鏈路預(yù)測(cè)有重要的指導(dǎo)意義.

4)輔助信息

·角色

一個(gè)實(shí)體的角色是指該實(shí)體與其他實(shí)體之間關(guān)系的集合.用圖論的方法來描述的話，即頂點(diǎn)V的角色是所有與V相連的邊組成的集合.一般來說，自同構(gòu)的頂點(diǎn)具有相同的角色，并且具有著最大的角色相似性.角色相似性描述的是如果兩個(gè)頂點(diǎn)和相似的頂點(diǎn)有相似數(shù)目的關(guān)系.

2013年伍杰華[18]提出了差分化社會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)角色的鏈路預(yù)測(cè)模型，采用Clauset-Newman-Moore算法挖掘社會(huì)網(wǎng)絡(luò)結(jié)構(gòu)屬性，同時(shí)引入節(jié)點(diǎn)連接度和社區(qū)理論，差分處理社區(qū)內(nèi)外節(jié)點(diǎn)和不同社區(qū)的貢獻(xiàn)，可以提高社會(huì)網(wǎng)絡(luò)中的鏈路預(yù)測(cè)精度，有效的解決量化鄰接節(jié)點(diǎn)貢獻(xiàn)權(quán)重的問題.

·社區(qū)

以社區(qū)信息作為輸入元數(shù)據(jù)能夠幫助我們分析網(wǎng)絡(luò)結(jié)構(gòu)、預(yù)測(cè)網(wǎng)絡(luò)行為，發(fā)現(xiàn)潛在的規(guī)律，并更好的理解和解釋網(wǎng)絡(luò)的功能.通過社區(qū)的劃分能夠使得同一社區(qū)的節(jié)點(diǎn)關(guān)系緊密，不同社區(qū)的節(jié)點(diǎn)關(guān)系稀疏.

2012年Soundarajan[19]發(fā)表了一篇名為《Using community information to improve the precision of link prediction methods》文章，該篇文章考慮了幾種基于相似性的度量方法，用社區(qū)信息作為輸入元數(shù)據(jù)補(bǔ)充了相似性的計(jì)算，實(shí)驗(yàn)結(jié)果表明，利用社區(qū)信息可以改善鏈路預(yù)測(cè)的性能和準(zhǔn)確性.

同年，Rebaza[20]等人發(fā)表了一篇文章，該篇文章結(jié)合了局部相似性和社區(qū)信息，提高了鏈路預(yù)測(cè)的精度.實(shí)驗(yàn)結(jié)果表明，該方法是可行的，它的性能優(yōu)于CN、AA、JC、RA和PA.能有效地應(yīng)用于有向和非對(duì)稱大規(guī)模網(wǎng)絡(luò).

2013年伍杰華[21]發(fā)表了一篇名為《基于劃分社區(qū)和差分共鄰節(jié)點(diǎn)貢獻(xiàn)的鏈路預(yù)測(cè)》的文章，該篇文章通過改進(jìn)基于節(jié)點(diǎn)相似度的樸素貝葉斯模型，引入GN和CMN兩種經(jīng)典的劃分社區(qū)算法，挖掘社區(qū)屬性預(yù)測(cè)節(jié)點(diǎn)的影響，給予共鄰節(jié)點(diǎn)不同的連接度和社區(qū)的貢獻(xiàn)度，并計(jì)算其貢獻(xiàn)權(quán)重，實(shí)驗(yàn)表明，有較高的預(yù)測(cè)精度.

·中心性

本篇文章考慮了節(jié)點(diǎn)在網(wǎng)絡(luò)中的影響力，利用節(jié)點(diǎn)的度中心性、介數(shù)中心性、緊密中心性和特征向量中心性作為輸入的元數(shù)據(jù)來進(jìn)行復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè).

2016年陳嘉穎[22]等人在基于局部相似性鏈路預(yù)測(cè)算法的基礎(chǔ)上，充分利用了節(jié)點(diǎn)度中心性、緊密中心性和介數(shù)中心性的信息，提出了考慮節(jié)點(diǎn)重要性的CN、AA、RA鏈路預(yù)測(cè)相似性指標(biāo).實(shí)驗(yàn)結(jié)果表明，改進(jìn)的算法預(yù)測(cè)精度均高于共同鄰居算法.

·語義信息

語義信息指通過領(lǐng)悟?qū)嶓w的運(yùn)動(dòng)狀態(tài)及其變化方式的邏輯含義，由此獲得的信息.

Iill[23,24]等人提出了一種使用抽象語義信息研究標(biāo)題和事件特征，以改進(jìn)作者合作網(wǎng)絡(luò)中的鏈路預(yù)測(cè)問題，取得了較好的預(yù)測(cè)性能.

2017年Guo[25]等人研究了在低維向量空間中針對(duì)知識(shí)圖的鏈路預(yù)測(cè)問題，提出了SSE方法，它的核心思想是充分利用附加的語義信息作為輸入特征，使屬于同一語義類別的實(shí)體將在嵌入空間中彼此靠近.采用拉普拉斯特征映射和局部線性嵌入兩種學(xué)習(xí)算法進(jìn)行建模，較好的解決了數(shù)據(jù)的稀疏性問題，結(jié)果表明，該方法優(yōu)于TransE和SME等鏈路預(yù)測(cè)方法.

2.1.2 第二層處理層

模型的第二層特征處理層，用信息學(xué)的方法和思路進(jìn)行復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)，我們把該層主要分為無監(jiān)督學(xué)習(xí)、監(jiān)督學(xué)習(xí)、半監(jiān)督學(xué)習(xí)和強(qiáng)化學(xué)習(xí)的方法.

1)無監(jiān)督學(xué)習(xí)

傳統(tǒng)的無監(jiān)督的學(xué)習(xí)技術(shù)，從無標(biāo)注數(shù)據(jù)集中挖掘相互之間的隱含關(guān)系，主要采用網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)提取特征，使用這些無監(jiān)督的方法能夠發(fā)現(xiàn)網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)建立關(guān)系的概率.雖然無監(jiān)督的方法復(fù)雜度較低，計(jì)算簡(jiǎn)單.但是，無監(jiān)督的方法適合排序，如果要進(jìn)行鏈路預(yù)測(cè)任務(wù)，指標(biāo)閾值較難設(shè)定，特別對(duì)于權(quán)重網(wǎng)絡(luò)，使用無監(jiān)督的方法，預(yù)測(cè)性能在某些情況下會(huì)衰減.在針對(duì)節(jié)點(diǎn)分類等任務(wù)時(shí)，區(qū)分性較差.

本文介紹的無監(jiān)督學(xué)習(xí)方法主要包括DeepWalk，LINE，GraRep，DNGR，SDNE，Struct2vec，Node2Vec，HOPE，GraphGAN，下面分別進(jìn)行介紹：

·DeepWalk

Perozzi[26]等人提出了一種學(xué)習(xí)網(wǎng)絡(luò)中頂點(diǎn)潛在表示的新方法DeepWalk.DeepWalk概括了語言建模從單詞序列到圖形的無監(jiān)督特征學(xué)習(xí)方面的最新進(jìn)展.其主要思路就是利用構(gòu)造節(jié)點(diǎn)在網(wǎng)絡(luò)上的隨機(jī)游走路徑，來學(xué)習(xí)潛在的表示.DeepWalk可以按需生成隨機(jī)游走.由于Skip-gram模型也針對(duì)每個(gè)樣本進(jìn)行優(yōu)化，因此隨機(jī)游走和Skip-gram的組合使DeepWalk成為在線算法.其次，DeepWalk是可擴(kuò)展的，生成隨機(jī)游走和優(yōu)化Skip-gram模型的過程都是高效且并行化的.再次，DeepWalk引入了深度學(xué)習(xí)圖形的范例.

·LINE

·GraRep

GraRep[27]通過將圖形鄰接矩陣提升到不同的冪來利用不同尺度的節(jié)點(diǎn)共現(xiàn)信息.將奇異值分解(SVD)應(yīng)用于鄰接矩陣的冪，以獲得節(jié)點(diǎn)的低維表示.它的缺點(diǎn)是擴(kuò)展性較差.

·DNGR

DNGR[28]結(jié)合了隨機(jī)游走和深度自動(dòng)編碼器.該模型由3部分組成：隨機(jī)游走、正點(diǎn)互信息(PPMI)計(jì)算和疊加去噪的自動(dòng)編碼器.在輸入圖上使用隨機(jī)游走模型來產(chǎn)生概率共現(xiàn)矩陣，類似于HOPE中的相似矩陣.矩陣被轉(zhuǎn)換成一個(gè)PPMI矩陣，并將其輸入到一個(gè)疊加去噪自動(dòng)編碼器中，以獲得嵌入.輸入PPMI矩陣可以確保自動(dòng)編碼器模型能夠捕獲更高階的近似度.此外，使用疊加去噪自動(dòng)編碼器模型能夠捕獲更高階的近似度，以及捕獲鏈接預(yù)測(cè)任務(wù)所需的底層結(jié)構(gòu).

DNGR 與 SDNE 區(qū)別主要在于相似性向量的定義不同，DNGR 將兩個(gè)節(jié)點(diǎn)由隨機(jī)游走得到的共同路徑作為衡量其相似性的指標(biāo)，而 SDNE 直接用一階關(guān)系作為相似性的輸入.

·SDNE

2016年，王等人[29]提出一種結(jié)構(gòu)化的深度網(wǎng)絡(luò)嵌入方法SDNE，來保留網(wǎng)絡(luò)的一階和二階相似性，同時(shí)處理好稀疏性的問題，利用一階近似描述局部信息，使用二階近似由無監(jiān)督組件捕獲全局網(wǎng)絡(luò)結(jié)構(gòu)，對(duì)稀疏網(wǎng)絡(luò)具有較強(qiáng)的魯棒性.結(jié)果表明該方法具有較好的重建效果.特別是在多標(biāo)簽分類和鏈路預(yù)測(cè)領(lǐng)域獲得了實(shí)質(zhì)性的進(jìn)展.

SDNE將節(jié)點(diǎn)的相似性向量Si直接作為模型的輸入，通過自動(dòng)編碼器對(duì)這個(gè)向量進(jìn)行降維壓縮，得到其向量化后的結(jié)果Zi.其損失函數(shù)定義為：

其中Si是一個(gè)|V|維的輸入向量，而Zi的維數(shù)必然遠(yuǎn)小于前者.它的建模思路和矩陣分解是一致的，只是在降維時(shí)用的不是矩陣分解，而是自動(dòng)編碼器.

·Stuct2vec

2017年Ribeiro等人[30]提出了一種新的、靈活的Struct2vec框架，用于學(xué)習(xí)節(jié)點(diǎn)結(jié)構(gòu)標(biāo)識(shí)的潛在表示.Struct2vec使用層次結(jié)構(gòu)度量節(jié)點(diǎn)對(duì)的結(jié)構(gòu)相似性，并構(gòu)造多層圖對(duì)結(jié)構(gòu)相似性進(jìn)行編碼，為節(jié)點(diǎn)生成上下文結(jié)構(gòu)，利用上下文來學(xué)習(xí)節(jié)點(diǎn)的潛在表示.實(shí)驗(yàn)表明，Struct2vec在捕捉結(jié)構(gòu)特征方面非常出色，優(yōu)于DeepWalk和Node2Vec.

·Node2Vec

2016年Aditya[31]提出了一種學(xué)習(xí)網(wǎng)絡(luò)節(jié)點(diǎn)連續(xù)特征表示的算法框架Node2Vec.它是一種自動(dòng)學(xué)習(xí)節(jié)點(diǎn)特征的嵌入方法，主要用于社交網(wǎng)絡(luò)中的鏈路預(yù)測(cè)任務(wù).在Node2Vec中，學(xué)習(xí)了一種將節(jié)點(diǎn)映射到低維特征空間的方法，這種方法可以最大限度地保留節(jié)點(diǎn)的網(wǎng)絡(luò)鄰域.Node2Vec引入了 biased-random walks，用來刻畫每次隨機(jī)游走是偏深度探索(DFS)還是廣度探索(BFS)，分別側(cè)重社區(qū)結(jié)構(gòu)和節(jié)點(diǎn)重要性的信息，有效的探索了不同的鄰域.由于 node2vec 有 p 和 q 兩個(gè)超參數(shù)，所以它是一個(gè)比較靈活的模型框架.

2018年Li[32]等人提出了一種新的網(wǎng)絡(luò)嵌入方法TDL2Vec用于預(yù)測(cè)作者合作網(wǎng)絡(luò)中消失的鏈接問題，它是對(duì)Node2Vec算法的擴(kuò)展.該篇文章將消失鏈接的預(yù)測(cè)問題看作是一個(gè)二分類問題，并將支持向量機(jī)SVM作為嵌入后的分類器，實(shí)驗(yàn)結(jié)果表明，TDL2Vec具有較好的性能.

同年，Shawn[33]等人比較了三種網(wǎng)絡(luò)的嵌入方法Graphlets，Node2Vce和struc2vec，Graphlet比其他兩種方法結(jié)果更加的精確，計(jì)數(shù)更加的迅速，特別是在節(jié)點(diǎn)分類和鏈路預(yù)測(cè)領(lǐng)域.

實(shí)驗(yàn)結(jié)果表明，圖形將繼續(xù)在網(wǎng)絡(luò)科學(xué)領(lǐng)域留下自己的印記，通過圖理論進(jìn)行鏈路預(yù)測(cè)將成為未來的發(fā)展發(fā)向.這也進(jìn)一步證實(shí)，后面我們將要提到的基于圖形的深度學(xué)習(xí)方法對(duì)鏈路預(yù)測(cè)問題具有重要的意義.

·HOPE

·GraphGAN

2018年Wang[35]等人創(chuàng)新性的提出了一種新的圖形表示學(xué)習(xí)框架GraphGAN，它是一個(gè)在網(wǎng)絡(luò)生成學(xué)習(xí)中將生成模型和判別模型加以結(jié)合的框架.對(duì)于給定的頂點(diǎn)，生成器擬合Ptrue，判別器嘗試去判別兩個(gè)點(diǎn)之間是否有邊，實(shí)驗(yàn)在5個(gè)數(shù)據(jù)集上進(jìn)行了測(cè)試，結(jié)果表明GraphGAN比DeepWalk，LINE，Node2Vec和Struc2vec準(zhǔn)確性都更高.特別是在鏈路預(yù)測(cè)領(lǐng)域獲得了較佳的性能.

2)監(jiān)督學(xué)習(xí)

隨著機(jī)器學(xué)習(xí)技術(shù)的迅猛發(fā)展，一些計(jì)算機(jī)領(lǐng)域的專家們使用監(jiān)督學(xué)習(xí)技術(shù)來進(jìn)行復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè).監(jiān)督學(xué)習(xí)技術(shù)通過對(duì)有標(biāo)記的數(shù)據(jù)集進(jìn)行訓(xùn)練，預(yù)測(cè)未知的數(shù)據(jù).它能夠根據(jù)輸入特征自動(dòng)學(xué)習(xí)出分類模型，在一定程度上克服了傳統(tǒng)的無監(jiān)督學(xué)習(xí)方法的缺陷.

迄今為止，在計(jì)算機(jī)領(lǐng)域產(chǎn)生了許多基于監(jiān)督學(xué)習(xí)的研究成果.例如：2011年哈桑(Hasan)等人[36]提取合著網(wǎng)絡(luò)中科學(xué)家研究領(lǐng)域的關(guān)鍵詞作為輸入特征，用監(jiān)督學(xué)習(xí)中一些常用的分類算法(如決策樹、K近鄰法、多層感知器、支持向量機(jī)、徑向基網(wǎng)絡(luò))對(duì)缺失的連邊進(jìn)行較為精準(zhǔn)的預(yù)測(cè)，其中以支持向量機(jī)方法表現(xiàn)最佳.2012年P(guān)ujari和Kanawati[37]提出了一種監(jiān)督的社會(huì)選擇算法，他們使用這些數(shù)據(jù)來學(xué)習(xí)與每個(gè)計(jì)算特征相關(guān)聯(lián)的權(quán)重特征，然后使用這些權(quán)重在加權(quán)/監(jiān)督計(jì)算社會(huì)選擇算法預(yù)測(cè)新鏈接.隨后，劉等人[38]提出了一種基于監(jiān)督學(xué)習(xí)的框架，利用多種信息構(gòu)造出豐富多樣的基于路徑的特征進(jìn)行鏈路預(yù)測(cè)，該方法證實(shí)可以高效的學(xué)習(xí)動(dòng)態(tài)社交網(wǎng)絡(luò).2014年Raf[39]等人提出通過監(jiān)督學(xué)習(xí)中的集成學(xué)習(xí)結(jié)合RF方法預(yù)測(cè)加權(quán)合作網(wǎng)絡(luò)，實(shí)驗(yàn)結(jié)果表明，該方法準(zhǔn)確性較高.2019年趙素芬[40]提出了利用網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，學(xué)者的研究興趣，學(xué)者的學(xué)術(shù)地位作為輸入特征，使用了8種經(jīng)典的機(jī)器學(xué)習(xí)算法(K近鄰、logistic回歸、決策樹DT、支持向量機(jī)SVM、樸素貝葉斯、多層前饋神經(jīng)網(wǎng)絡(luò)MLP、集成學(xué)習(xí)隨機(jī)森林和Adaboost)進(jìn)行了合作關(guān)系的預(yù)測(cè)，并進(jìn)行了預(yù)測(cè)性能的比較.該項(xiàng)研究表明，在基本的機(jī)器學(xué)習(xí)模型中，多層感知機(jī)表現(xiàn)最好，因?yàn)樗碾[藏層可以捕捉特征之間的非線性關(guān)系，并在較高層次進(jìn)行抽象，所以能較好的擬合訓(xùn)練數(shù)據(jù)，訓(xùn)練出精度高的模型.而樸素貝葉斯表現(xiàn)最差，因?yàn)樗俣颂卣髦g的條件獨(dú)立性，在本問題中很難確定，因而影響了分類效果.其他幾種算法邏輯回歸、決策樹和SVM性能基本一致，KNN優(yōu)于樸素貝葉斯.2018年Aouay[41]等人提出了通過組合特征作為分類輸入數(shù)據(jù)，利用多個(gè)監(jiān)督的學(xué)習(xí)算法生成鏈路預(yù)測(cè)器(決策樹、KNN、樸素貝葉斯、徑向基函數(shù)和隨機(jī)森林)，取得了較好的效果.結(jié)果表明，隨機(jī)森林、KNN和PCA 表現(xiàn)突出，提高了預(yù)測(cè)精度.

目前常用的監(jiān)督學(xué)習(xí)方法有SVM，KNN，Logistic Regression，Random Forrest，Ensemble Learning，Multilayer Perceptron和Na?ve Bayes.下面分別對(duì)這些監(jiān)督學(xué)習(xí)算法進(jìn)行詳述：

·SVM

SVM(Support vector machine)使用一個(gè)核函數(shù)，將非線性問題變換為線性問題，它的核心思想就是找到能夠最大化樣本間隔的決策邊界，使得兩類樣本盡量落在面的兩邊.它的優(yōu)點(diǎn)是在面對(duì)過擬合問題時(shí)，SVM有極強(qiáng)的穩(wěn)健性，特別是在高維空間中.缺點(diǎn)是選擇正確的核函數(shù)需要一定的技巧，不適用于較大的數(shù)據(jù)集.

李等人[15]提出了一種基于SVM圖核的機(jī)器學(xué)習(xí)方法，利用網(wǎng)絡(luò)結(jié)構(gòu)，隨機(jī)游走路徑，節(jié)點(diǎn)特征在二部圖中進(jìn)行鏈路預(yù)測(cè)，將一個(gè)推薦問題轉(zhuǎn)化為一個(gè)鏈路預(yù)測(cè)問題，該方法其性能的優(yōu)劣很大程度上依賴于核函數(shù)的選擇.

Ichise[23，24]等人在基于監(jiān)督學(xué)習(xí)的框架下采用SVM，decision trees，利用網(wǎng)絡(luò)的結(jié)構(gòu)，語義信息和基于事件的特征研究作者合作網(wǎng)絡(luò)中的鏈路預(yù)測(cè)問題，通過在一特定的網(wǎng)絡(luò)中，去分析所構(gòu)造的預(yù)測(cè)器的算法結(jié)構(gòu)，可以獲悉哪些屬性是有價(jià)值的信息，對(duì)鏈路預(yù)測(cè)問題最有幫助.

·KNN

KNN根據(jù)一個(gè)距離函數(shù)(可以是歐式距離，曼哈頓距離，漢明距離)，搜尋最相似的訓(xùn)練樣本來預(yù)測(cè)新樣本的觀察值.它的優(yōu)點(diǎn)是理論簡(jiǎn)單，易實(shí)現(xiàn)，新數(shù)據(jù)可直接加入不必重新訓(xùn)練.缺點(diǎn)是它是內(nèi)存密集型算法，處理高維數(shù)據(jù)時(shí)的效果并不理想.同時(shí)還需要高效的距離函數(shù)來計(jì)算相似度.樣本不平衡時(shí)，預(yù)測(cè)偏差較大，對(duì)于樣本容量大的數(shù)據(jù)集計(jì)算量大.

Manisha[37]等人利用網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)特征，將KNN，NaiveBayes技術(shù)應(yīng)用于復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)中，提出了一種新的基于監(jiān)督的秩聚合的方法，雖然能夠聚合盡可能多的特征，但在時(shí)間復(fù)雜度方面有一定的局限性.

·Logistic Regression

邏輯回歸能夠?qū)B續(xù)值進(jìn)行預(yù)測(cè)，通過擬合一個(gè)邏輯函數(shù)來預(yù)測(cè)一個(gè)事件發(fā)生的概率.它的優(yōu)點(diǎn)是計(jì)算代價(jià)不高，易于理解和實(shí)現(xiàn).缺點(diǎn)是容易產(chǎn)生欠擬合，分類精度不高.

王等人[42]采用邏輯回歸模型使用網(wǎng)絡(luò)結(jié)構(gòu)和基于內(nèi)容的相似性度量預(yù)測(cè)合作關(guān)系，取得了較好的預(yù)測(cè)效果.

Chiang[43]等人在符號(hào)網(wǎng)絡(luò)中，使用邏輯回歸預(yù)測(cè)器進(jìn)行鏈路預(yù)測(cè)，不僅實(shí)現(xiàn)了準(zhǔn)確的符號(hào)預(yù)測(cè)，而且對(duì)于降低假陽性率是非常有效的.

Jure[44]等人也使用邏輯回歸模型在符號(hào)網(wǎng)絡(luò)中進(jìn)行鏈路預(yù)測(cè)，選取節(jié)點(diǎn)的度作為特征，實(shí)現(xiàn)了在符號(hào)網(wǎng)絡(luò)中高精度的預(yù)測(cè)效果.

·Random Forrest

隨機(jī)森林是一個(gè)樹型分類器，它采用多棵樹對(duì)樣本進(jìn)行訓(xùn)練，然后通過投票或加權(quán)平均的方式輸出結(jié)果.它的優(yōu)點(diǎn)是能夠?qū)崿F(xiàn)較高的精度，不用擔(dān)心過擬合問題，無需事先做特征選擇，每次只用隨機(jī)選取的幾個(gè)特征來訓(xùn)練樹.缺點(diǎn)是在某些噪音較大的分類或回歸問題上會(huì)過擬合.

Scellato等人[16]使用地理位置特征，社會(huì)特征和全局特征，運(yùn)用Na?ve Bayes和random forests在基于地理位置的社交網(wǎng)絡(luò)中進(jìn)行預(yù)測(cè)，實(shí)現(xiàn)了較高的預(yù)測(cè)精度.

·Multilayer Perceptron

多層感知機(jī)也叫人工神經(jīng)網(wǎng)絡(luò)，它的一個(gè)重要特點(diǎn)就是多層，除了輸入輸出層，它中間可以有多個(gè)隱層，最簡(jiǎn)單的MLP只含一個(gè)隱層，即三層的結(jié)構(gòu).MLP層與層之間是全連接的，它的最底層是輸入層，中間是隱藏層，最后是輸出層.MLP的優(yōu)點(diǎn)是可以學(xué)習(xí)非線性模型，能夠進(jìn)行實(shí)時(shí)學(xué)習(xí).缺點(diǎn)是要求調(diào)整一系列超參數(shù)，比如隱藏神經(jīng)元，隱藏層的個(gè)數(shù)以及迭代的次數(shù).其次，MLP對(duì)特征縮放比較敏感.

Andrej[45]等人利用多層感知器進(jìn)行時(shí)間序列預(yù)測(cè)，在反向傳播算法中，權(quán)值通常用小的隨機(jī)值初始化，適當(dāng)?shù)臋?quán)值初始化將使權(quán)值接近一個(gè)好的解決方案，從而減少訓(xùn)練時(shí)間.實(shí)驗(yàn)結(jié)果表明，采用適當(dāng)?shù)臋?quán)值初始化，可以獲得較好的預(yù)測(cè)性能.

·Ensemble Learning

集成學(xué)習(xí)通過構(gòu)建并結(jié)合多個(gè)學(xué)習(xí)器來完成學(xué)習(xí)任務(wù)，通常能夠獲得比單一學(xué)習(xí)器更優(yōu)越的泛化性能.Mitchell指出[46]集成學(xué)習(xí)技術(shù)可以結(jié)合各種方法，揚(yáng)長(zhǎng)補(bǔ)短發(fā)揮最優(yōu)性能.

2017年4月呂偉民等人提出結(jié)合鏈路預(yù)測(cè)與機(jī)器學(xué)習(xí)進(jìn)行科研合作推薦，運(yùn)用監(jiān)督學(xué)習(xí)方法通過集成學(xué)習(xí)中的隨機(jī)森林算法訓(xùn)練分類[47]，并利用遍歷算法求取分類結(jié)果的最優(yōu)權(quán)重組合，選取TOP排名靠前的結(jié)果作為合作推薦，取得了較好的效果.

Pachaury[48]等人提出了一種新穎的鏈路預(yù)測(cè)方法來尋找社交網(wǎng)絡(luò)中缺失的鏈接，該方法從網(wǎng)絡(luò)圖中提取拓?fù)涮卣鳎糜谟?xùn)練集成學(xué)習(xí)模型隨機(jī)森林分類器，訓(xùn)練后的模型用于預(yù)測(cè)缺失的鏈接，對(duì)兩個(gè)網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行實(shí)驗(yàn)評(píng)估，實(shí)驗(yàn)結(jié)果表明該方法預(yù)測(cè)精度高，能揭示社交網(wǎng)絡(luò)的隱藏鏈接.

·Na?ve Bayes

樸素貝葉斯是一種簡(jiǎn)單的概率分類器，它的核心思想是對(duì)于給定的待分類項(xiàng)，求解在該項(xiàng)出現(xiàn)的條件下各個(gè)類別出現(xiàn)的概率，值越大，該分類項(xiàng)即屬于此類別.優(yōu)點(diǎn)：該算法易于實(shí)現(xiàn)，且對(duì)于大型數(shù)據(jù)集非常有用.支持增量式運(yùn)算即可以實(shí)時(shí)的對(duì)新增的樣本進(jìn)行訓(xùn)練.缺點(diǎn)：由于使用了樣本屬性獨(dú)立性的假設(shè)，所以如果樣本屬性有關(guān)聯(lián)時(shí)其效果較差.

Valverde[49]等人提出了一種利用重疊結(jié)構(gòu)信息建立樸素貝葉斯模型的新方法，比較了四個(gè)著名的在線社交網(wǎng)絡(luò)的16項(xiàng)指標(biāo)，結(jié)果表明，該方法有助于提高鏈路預(yù)測(cè)精度.

隨后，Sa[50]等人在權(quán)重網(wǎng)絡(luò)中利用網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)特征，采用Na?ve Bayes方法證明使用權(quán)重信息可以提高監(jiān)督鏈路預(yù)測(cè)的效果.

·CNN

卷積神經(jīng)網(wǎng)絡(luò)CNN由紐約大學(xué)的Yann Le Cun于1998年提出，它能夠自動(dòng)提取特征，挖掘數(shù)據(jù)局部特性.

2017年，Niepert[51]等人指出許多重要的問題比如鏈路預(yù)測(cè)問題，能夠概括為從圖形數(shù)據(jù)中學(xué)習(xí)的過程，研究了一個(gè)通用的基于卷積神經(jīng)網(wǎng)絡(luò)CNN的學(xué)習(xí)框架，用于學(xué)習(xí)任意圖形的表示，這些圖可以是無向的，有向的，離散的或連續(xù)的節(jié)點(diǎn)和邊緣屬性.在輸入的局部連通區(qū)域上，提出了一種局部數(shù)據(jù)提取的通用方法，該方法取得了較高的效率.

2018年，舒堅(jiān)[52]等人借助CNN能夠自動(dòng)提取特征的優(yōu)勢(shì)，提出一種基于模型分類的多點(diǎn)間鏈路預(yù)測(cè)方法，該方法基于混沌時(shí)間序列理論確定機(jī)會(huì)網(wǎng)絡(luò)的切片時(shí)間，采用狀態(tài)圖表征網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，從狀態(tài)圖的演化過程中提取機(jī)會(huì)網(wǎng)絡(luò)的結(jié)構(gòu)特征，實(shí)現(xiàn)多點(diǎn)間的鏈路預(yù)測(cè).能較好地輔助研究人員進(jìn)行網(wǎng)絡(luò)分析并提供合理的決策支持.

3)半監(jiān)督學(xué)習(xí)

有監(jiān)督的學(xué)習(xí)算法雖然能夠自動(dòng)對(duì)特征進(jìn)行學(xué)習(xí)，但是需要大量標(biāo)記的數(shù)據(jù)，不能有效的利用未標(biāo)記的訓(xùn)練樣本.然而現(xiàn)實(shí)世界的多數(shù)數(shù)據(jù)是未標(biāo)記的，在一定程度上限制了有監(jiān)督的學(xué)習(xí)方法在鏈路預(yù)測(cè)領(lǐng)域的應(yīng)用.

與傳統(tǒng)的有監(jiān)督的學(xué)習(xí)方法相比，半監(jiān)督的學(xué)習(xí)方法能夠減少數(shù)據(jù)樣本進(jìn)行標(biāo)記的代價(jià)，只使用少量已標(biāo)記的數(shù)據(jù)結(jié)合未標(biāo)記的數(shù)據(jù)樣本就可以達(dá)到較好的預(yù)測(cè)效果.半監(jiān)督的學(xué)習(xí)方法適合于擁有大量隱性特征的網(wǎng)絡(luò)，可以利用少部分的顯式特征，推測(cè)隱藏信息.

特別是最近幾年，隨著基于圖的深度學(xué)習(xí)技術(shù)的發(fā)展，復(fù)雜網(wǎng)絡(luò)可以抽像成圖的結(jié)構(gòu)，通過對(duì)復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)特征的分析，可以選擇基于圖的半監(jiān)督學(xué)習(xí)方法預(yù)測(cè)用戶隱含的特征.因此，誕生了許多半監(jiān)督學(xué)習(xí)進(jìn)行鏈路預(yù)測(cè)的研究成果.下面分別進(jìn)行詳述：

·GCN

2017年Tomas[53]等人提出了一種基于卷積神經(jīng)網(wǎng)絡(luò)的半監(jiān)督學(xué)習(xí)方法GCN，作為最近幾年興起的一種基于圖結(jié)構(gòu)的神經(jīng)網(wǎng)絡(luò)，因?yàn)槠洫?dú)特的計(jì)算能力，而受到大量學(xué)者的關(guān)注與研究.傳統(tǒng)的深度學(xué)習(xí)模型LSTM和CNN在歐幾里得空間數(shù)據(jù)上取得了不錯(cuò)的成績(jī)，但是以非歐幾里得空間數(shù)據(jù)進(jìn)行處理卻存在一定的局限性.針對(duì)該問題，研究者們引入了圖論中抽象意義上的圖來表示非歐幾里得結(jié)構(gòu)化數(shù)據(jù)，并利用圖卷積網(wǎng)絡(luò)對(duì)圖數(shù)據(jù)進(jìn)行處理，以深入發(fā)掘其特征和規(guī)律.

GCN能夠同時(shí)對(duì)圖結(jié)構(gòu)和節(jié)點(diǎn)特征進(jìn)行編碼，它使用了基于一階近似的有效逐層傳播規(guī)則圖上的譜卷積，是一種高效的半監(jiān)督學(xué)習(xí)方法.它在圖形邊緣的數(shù)量上線性擴(kuò)展，并學(xué)習(xí)了編碼局部圖結(jié)構(gòu)和節(jié)點(diǎn)特征的隱層表示.在引文網(wǎng)和知識(shí)圖數(shù)據(jù)集上的大量實(shí)驗(yàn)表明，該方法有顯著的優(yōu)勢(shì).因?yàn)?GCN 在網(wǎng)絡(luò)結(jié)構(gòu)的基礎(chǔ)上，又考慮了節(jié)點(diǎn)的屬性信息，性能比僅僅考慮結(jié)構(gòu)信息的方法更佳.

2017年，Michael Schlichtkrull[54]等人提出了一種關(guān)系圖卷積網(wǎng)絡(luò)(R-GCNs)用于鏈路預(yù)測(cè)和實(shí)體分類.對(duì)于鏈路預(yù)測(cè)，采用R-GCN模型解碼的性能優(yōu)于直接優(yōu)化因子分解模型，在鏈路預(yù)測(cè)方面取得了較好的效果.

2018年Harade[55]等人提出了DCNN(Dual Convolution Neural Network)方法，從圖中自動(dòng)、靈活地提取特征，使用端到端的方式結(jié)合內(nèi)外部圖結(jié)構(gòu)來提取節(jié)點(diǎn)表示，通過在多個(gè)化學(xué)網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行預(yù)測(cè)，證實(shí)了該方法的有效性.

·LSTM

Hochreiter & Schmidhuber于1997年提出了長(zhǎng)短期記憶網(wǎng)絡(luò)LSTM，它是一種時(shí)間遞歸的神經(jīng)網(wǎng)絡(luò)，適用于預(yù)測(cè)時(shí)間序列中時(shí)間間隔和延遲時(shí)間較長(zhǎng)的事件.它的顯著特點(diǎn)是可以擬合時(shí)間序列數(shù)據(jù)，有效的解決梯度消失的問題.

2018年陳等人[56]提出一種圖卷積網(wǎng)絡(luò)GC-LSTM，嵌入式長(zhǎng)短時(shí)記憶網(wǎng)絡(luò)(LSTM)，用于端到端動(dòng)態(tài)網(wǎng)絡(luò)鏈路預(yù)測(cè).LSTM負(fù)責(zé)網(wǎng)絡(luò)快照的時(shí)間特征學(xué)習(xí)，GCN用于網(wǎng)絡(luò)快照的結(jié)構(gòu)學(xué)習(xí).目前的動(dòng)態(tài)網(wǎng)絡(luò)鏈路預(yù)測(cè)方法只能處理刪除的鏈接，而GC-LSTM可以同時(shí)預(yù)測(cè)添加和刪除的鏈接，通過大量的實(shí)驗(yàn)表明，GC-LSTM算法在預(yù)測(cè)精度，添加/刪除鏈路和關(guān)鍵鏈路等方面的性能優(yōu)于 CN，LINE等方法.

·GNN

圖神經(jīng)網(wǎng)絡(luò)GNN是圖數(shù)據(jù)最原始的半監(jiān)督深度學(xué)習(xí)方法.為了編碼圖的結(jié)構(gòu)信息，每個(gè)節(jié)點(diǎn)可以由低維狀態(tài)向量表示.

2018年張等人[57]提出一種利用圖從局部子圖學(xué)習(xí)高階啟發(fā)式的新方法GNN用于解決鏈路預(yù)測(cè)問題，通過提取每個(gè)目標(biāo)周圍的局部子圖鏈接，學(xué)習(xí)一個(gè)映射子圖模式到鏈接存在的函數(shù).自動(dòng)學(xué)習(xí)適合當(dāng)前網(wǎng)絡(luò)的“啟發(fā)式”.實(shí)驗(yàn)表明，通過比較各種啟發(fā)式算法，潛在特征方法和網(wǎng)絡(luò)嵌入方法，GNN顯示了良好的性能.它不僅適用于鏈路預(yù)測(cè)領(lǐng)域，而且還適用于知識(shí)圖補(bǔ)全和推薦系統(tǒng).

·GAN

生成式對(duì)抗網(wǎng)絡(luò)GAN是一種深度學(xué)習(xí)模型，它由兩部分組成即生成網(wǎng)絡(luò)G和判別網(wǎng)絡(luò)D，G和D通過不斷的博弈，使得G能夠從一段隨機(jī)數(shù)中生成清晰逼真的圖片.GAN的優(yōu)點(diǎn)是相比其他生成模型，它只用到了反向傳播，而不需要復(fù)雜的馬爾科夫鏈，它可以產(chǎn)生比其他模型更加清晰真實(shí)的樣本.GAN的缺點(diǎn)是不適合處理離散形式的數(shù)據(jù)，比如文本.

2019年Lei[58]等人提出了一種新的非線性模型GCN-GAN模型處理具有挑戰(zhàn)性的加權(quán)時(shí)間鏈路預(yù)測(cè)任務(wù).該模型充分利用了圖卷積網(wǎng)絡(luò)GCN，長(zhǎng)短時(shí)記憶LSTM以及GAN，利用GCN研究該算法的局部拓?fù)涮卣鳎幚砑訖?quán)動(dòng)態(tài)網(wǎng)絡(luò)中的時(shí)序鏈路預(yù)測(cè)問題，然后使用LSTM對(duì)每個(gè)快照進(jìn)行特征描述動(dòng)態(tài)網(wǎng)絡(luò)的演化過程.為了驗(yàn)證模型的有效性，對(duì)四個(gè)不同的數(shù)據(jù)集進(jìn)行了廣泛的實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明在加權(quán)動(dòng)態(tài)網(wǎng)絡(luò)中該模型優(yōu)于ED，SVD，NMF，GrNMF，AM-NMF和LSTM方法，具有較強(qiáng)的處理數(shù)據(jù)稀疏性的能力.

4)強(qiáng)化學(xué)習(xí)

強(qiáng)化學(xué)習(xí)介于監(jiān)督與無監(jiān)督學(xué)習(xí)之間，記錄不同行動(dòng)的結(jié)果并嘗試使用機(jī)器的歷史和經(jīng)驗(yàn)來做出決定，每一步預(yù)測(cè)或者行為都有部分反饋信息.

2019年You[59]等人提出了一種基于圖卷積網(wǎng)絡(luò)GCPN的強(qiáng)化學(xué)習(xí)目標(biāo)圖生成模型，GCPN使用強(qiáng)化學(xué)習(xí)執(zhí)行目標(biāo)導(dǎo)向的模塊化圖生成任務(wù)，以處理不可微的目標(biāo)和約束.將圖生成建模為馬爾可夫決策過程，將生成模型作為在圖生成環(huán)境中運(yùn)行的強(qiáng)化學(xué)習(xí)智能體，使用GCN來學(xué)習(xí)節(jié)點(diǎn)特征.實(shí)驗(yàn)結(jié)果表明，GCPN在多種圖生成問題上的有效性，特別是在處理鏈路預(yù)測(cè)問題，有較好的性能.

2018年Cao等人提出了MolGAN[60]方法，它也采用了同樣的思想，采用生成對(duì)抗網(wǎng)絡(luò)GAN直接對(duì)圖結(jié)構(gòu)數(shù)據(jù)進(jìn)行處理，同時(shí)與強(qiáng)化學(xué)習(xí)RL相結(jié)合，生成具有較高有效性的模塊化圖，MolGAN建議直接生成完整的圖，至少縮短5倍的訓(xùn)練時(shí)間.

2.1.3 第三層輸出層

該層為輸出層，把上層處理層通過常用的鏈路預(yù)測(cè)算法得到的結(jié)果輸出，該層輸出的是一組低維的表示圖形的向量.下面總結(jié)了三種輸出方式，即邊，子圖和全圖.

第一種方法輸出edge 邊，預(yù)測(cè)結(jié)果表明兩個(gè)節(jié)點(diǎn)之間是否存在鏈接，結(jié)果適用于鏈路預(yù)測(cè)和知識(shí)圖中的實(shí)體/關(guān)系預(yù)測(cè).在鏈路預(yù)測(cè)的應(yīng)用中，我們也會(huì)為每一條邊來輸出一個(gè)特征，并在后續(xù)工作中將其作為邊的特征來進(jìn)行一些分類任務(wù).第二種方法會(huì)輸出子圖，包括子結(jié)構(gòu).第三種是全圖，即為一個(gè)整圖來輸出適用于蛋白質(zhì)、分子這類數(shù)量較多的小圖.

2.2 復(fù)雜性分析

表1 常用預(yù)測(cè)方法復(fù)雜度分析
Table 1 Complexity analysis of common prediction methods

類別方法復(fù)雜度監(jiān)督學(xué)習(xí)SVMO(n2)KNNO(n?k)Logistic RegressionO(n?k+k)Ensemble LearningO(n)Random ForrestO(n?m?d)Na?ve BayesO(mn)半監(jiān)督學(xué)習(xí)GCNO(|E|d2)GNNO(|E|d2)LSTMO(nm+n2+n)無監(jiān)督學(xué)習(xí)DeepwalkO(d|V|log|V|)LINEO(d|E|)Struct2vecO(|V|3)GraRepO(|V||E|+d|V|2)SDNEO(dI|V|2)DNGRO(|V|2)Node2vecO(d|V|)HOPEO(d2I|E|)GraphGANO(|V|log|V|)強(qiáng)化學(xué)習(xí)GCPNO(d?d)

2.3 常用鏈路預(yù)測(cè)方法使用的特征(見表2)

表2 常用預(yù)測(cè)方法所使用的特征分析
Table 2 Common predictive methods used in feature analysis

類別方 法網(wǎng)絡(luò)結(jié)構(gòu)屬性特征文本屬性特征圖形(像)特征標(biāo)簽輔助信息角色社區(qū)中心性語義無監(jiān)督的方法DeepWalk[26]√LINE[27]√√√GraRep[27]√DNGR[28]√SDNE[29]√N(yùn)ode2Vec[31][32][33]√√√HOPE[34]√Struct2vec[30]√√GraphGAN[35]√√監(jiān)督的方法SVM[15][23][24]√√√KNN[37]√LogisticRegression[42][43][44]√√Random Forrest[16]√Ensemble learning[46][47][48]√Multilayer Perceptron[45]√N(yùn)a?ve Bayes[49][50]√√CNN[51][52]√√√半監(jiān)督的方法GCN[53][54][55]√√√GNN[56]LSTM[57]√√√√GAN[58]√√強(qiáng)化學(xué)習(xí)GCPN[59]√√√MolGAN[60]√√√

2.4 開源實(shí)現(xiàn)

本節(jié)提供了常用鏈路預(yù)測(cè)方法的實(shí)現(xiàn)代碼，提供了下載網(wǎng)址，對(duì)于較好的再現(xiàn)和比較不同的鏈路預(yù)測(cè)方法非常重要.編寫代碼是一項(xiàng)費(fèi)時(shí)費(fèi)力的工作，在寫這篇綜述論文的工作中，我們總結(jié)了常用鏈路預(yù)測(cè)方法的源代碼(如表3所列)，為科研人員進(jìn)一步的研究提供了方便.

2.5 各種鏈路預(yù)測(cè)方法實(shí)驗(yàn)結(jié)果

當(dāng)前衡量鏈路預(yù)測(cè)方法性能的評(píng)價(jià)指標(biāo)主要包括：AUC 和Precious值，AUC值從宏觀上衡量算法的準(zhǔn)確度，AUC值大于0.5的程度衡量了算法在多大程度上比隨機(jī)選擇的方法精確；而Precious只考慮對(duì)排前L位的邊是否預(yù)測(cè)準(zhǔn)確，Precious值越大預(yù)測(cè)越準(zhǔn)確.表4為常用鏈路預(yù)測(cè)方法的實(shí)驗(yàn)結(jié)果.

表3 基于學(xué)習(xí)的鏈路預(yù)測(cè)方法開源代碼實(shí)現(xiàn)
Table 3 Open source implementation of link prediction method based on learning

方 法編程語言Github鏈接DeepWalk[26]pythonhttps://github.com/phanein/deepwalkLINE[27]pythonhttps://github.com/tangjianpku/LINEGraRep[27]pythonhttps://github.com/benedekrozemberczki/GraRepDNGR[28]matlabhttp://github.com/ShelsonCao/DNGRSDNE[29]pythonhttp://github.com/suanrong/SDNENode2vec[31][32][33]pythonhttps://github.com/adocherty/node2vec_linkpredictionHOPE[34]Chttps://github.com/eXascaleInfolab/S-HUNEGraphGAN[35]pythonhttps://github.com/hwwang55/GraphGANStruct2Vec[30]pythonhttps://github.com/leoribeiro/struc2vecLink prediction based on unsupervised method (DeepWalk,LINE,Node2vec,SDNE,Struc2vec)pythonhttps://github.com/shenweichen/GraphEmbeddingGCN[53][54][55]pythonhttps://github.com/tkipf/gcnGNN[56]pythonhttps://github.com/weihua916/powerful-gnnsGAN[58]pythonhttps://github.com/jhayes14/GANLSTM[57]matlabhttps://github.com/huashiyiqike/LSTM-MATLABLink prediction based on supervised method[36]pythonhttps://github.com/alpecli/predligGCPN[59]pythonhttps://github.com/bowenliu16/rl_graph_generationMolGAN[60]pythonhttps://github.com/nicola-decao/MolGAN

表4 各種鏈路預(yù)測(cè)方法的實(shí)驗(yàn)結(jié)果
Table 4 Experimental results of various link prediction methods

類別方 法AUC值precious無監(jiān)督的方法DeepWalk0.7390.741LINE0.8140.836GraRep0.7320.035DNGR0.7040.793SDNE0.8360.912Node2Vec0.8540.845HOPE0.8810.612Struct2vec0.8100.821GraphGAN0.8590.855監(jiān)督的方法SVM0.9050.924KNN0.8810.923LogisticRegression0.8300.858Random Forrest0.8330.919Ensemble learning0.9090.748Multilayer Perceptron0.8970.740Na?ve Bayes0.8330.951CNN0.9580.901半監(jiān)督的方法GCN0.9150.912GNN0.9700.951LSTM0.8900.873GAN0.9010.914強(qiáng)化學(xué)習(xí)GCPN0.9210.855MolGAN0.9010.912

2.6 各種鏈路預(yù)測(cè)方法應(yīng)用建議

表5列出了各種鏈路預(yù)測(cè)方法的適用場(chǎng)景.

3 鏈路預(yù)測(cè)未來的發(fā)展方向

1)可解釋性

鏈路預(yù)測(cè)必須是可解釋的，例如，在醫(yī)學(xué)領(lǐng)域，可解釋性對(duì)于將計(jì)算機(jī)實(shí)驗(yàn)轉(zhuǎn)化為臨床應(yīng)用至關(guān)重要.

2)動(dòng)態(tài)與異構(gòu)性

目前大多數(shù)鏈路預(yù)測(cè)方法都是針對(duì)靜態(tài)網(wǎng)絡(luò)，但是實(shí)際的網(wǎng)絡(luò)是動(dòng)態(tài)變化的，例如，在社交網(wǎng)絡(luò)中，新人可以隨時(shí)進(jìn)入網(wǎng)絡(luò)，現(xiàn)有的人也可能隨時(shí)退出網(wǎng)絡(luò).在推薦系統(tǒng)中，產(chǎn)品可能有不同的類型，其中輸入可能有不同的形式，如文本或圖像.因此，應(yīng)該開發(fā)新的方法來處理動(dòng)態(tài)和異構(gòu)網(wǎng)絡(luò)的鏈路預(yù)測(cè)問題.

3)組合性

許多現(xiàn)有的鏈路預(yù)測(cè)方法可以協(xié)同工作，如何充分利用每一種方法的優(yōu)勢(shì)并將它們結(jié)合起來也是一個(gè)需要解決的關(guān)鍵問題.

4)跨學(xué)科性

鏈路預(yù)測(cè)已經(jīng)引起了各領(lǐng)域?qū)＜业年P(guān)注.跨學(xué)科交叉帶來了機(jī)遇和挑戰(zhàn).領(lǐng)域知識(shí)是用來解決具體問題的，但是跨領(lǐng)域知識(shí)的集成會(huì)使得模型設(shè)計(jì)更加困難.

4 結(jié)束語

本文提供了一個(gè)全面、系統(tǒng)的分類方法，涵蓋經(jīng)典的、最新的鏈路預(yù)測(cè)技術(shù)，鏈路預(yù)測(cè)問題，它給出鏈路預(yù)測(cè)的通用解決方案.特別是從信息學(xué)的角度提出了鏈路預(yù)測(cè)分層模型的思想，把當(dāng)前的鏈路預(yù)測(cè)技術(shù)分為：基于監(jiān)督學(xué)習(xí)的技術(shù)，基于半監(jiān)督學(xué)習(xí)的技術(shù)、基于無監(jiān)督學(xué)習(xí)的技術(shù)和基于強(qiáng)化學(xué)習(xí)的技術(shù)，并對(duì)這些方法的復(fù)雜性、優(yōu)缺點(diǎn)、適應(yīng)性和輸入特征進(jìn)行了分析和討論.最后，分析了未來鏈路預(yù)測(cè)的發(fā)展方向.

雖然，本文對(duì)當(dāng)前鏈路預(yù)測(cè)技術(shù)進(jìn)行了細(xì)致的劃分，但是主要是針對(duì)靜態(tài)網(wǎng)絡(luò).下一步工作將考慮以時(shí)間為輸入特征的動(dòng)態(tài)網(wǎng)絡(luò)和異構(gòu)網(wǎng)絡(luò)的分類.

表5 各種鏈路預(yù)測(cè)方法的應(yīng)用建議
Table 5 Suggestions on the application of various link prediction methods

類別方 法應(yīng)用建議無監(jiān)督的方法DeepWalk[26]它是并行的和可擴(kuò)展的,適用于大型的稀疏網(wǎng)絡(luò),廣泛應(yīng)用于網(wǎng)絡(luò)分類、鏈路預(yù)測(cè)和異常檢測(cè).LINE[27]它適用任意類型的大型網(wǎng)絡(luò),包括無向的,定向的和加權(quán)的網(wǎng)絡(luò)GraRep[27]它的并行性,對(duì)于大型網(wǎng)絡(luò)是非常有效的.DNGR[28]適用于加權(quán)網(wǎng)絡(luò),該方法給出了矩陣分解的一個(gè)新觀點(diǎn).SDNE[29]該方法對(duì)稀疏網(wǎng)絡(luò)具有較好的魯棒性.Node2Vec[31][32][33]該方法利用SVD優(yōu)化來實(shí)現(xiàn)高效率,對(duì)擾動(dòng)很健壯,適用于不同類型網(wǎng)絡(luò).HOPE[34]適合于有向網(wǎng)絡(luò),能較好的保持有向網(wǎng)絡(luò)的非對(duì)稱傳遞性.Struct2vec[30]該方法善于捕捉結(jié)構(gòu)方面的特征,能夠通過上下文學(xué)習(xí)節(jié)點(diǎn)的潛在表示,靈活性較好,適合于大型網(wǎng)絡(luò).GraphGAN[35]鏈路預(yù)測(cè),節(jié)點(diǎn)分類和推薦系統(tǒng)中,效果顯著,適合不同類型網(wǎng)絡(luò).監(jiān)督的方法SVM[15][23][24]難以實(shí)現(xiàn)大規(guī)模的訓(xùn)練樣本.KNN[37]該方法既適用于數(shù)值數(shù)據(jù)也適用于離散數(shù)據(jù),對(duì)多維數(shù)據(jù)處理不好.LogisticRegression[42][43][44]該方法不能用來解決非線性問題.Random Forrest[16]適合處理高維數(shù)據(jù).Ensemble learning[46][47][48]在處理高維稀疏數(shù)據(jù)集上的性能不如SVM.Multilayer Perceptron[45]能夠?qū)W習(xí)任意非線性輸入函數(shù).Na?ve Bayes[49][50]適用于大型數(shù)據(jù)集.CNN[51][52]適用于無向的、有向的、離散的或連續(xù)的節(jié)點(diǎn)和邊緣的網(wǎng)絡(luò),對(duì)非歐幾里得空間數(shù)據(jù)進(jìn)行處理存在一定的局限性.半監(jiān)督的方法GCN[53][54][55]不適合于大而密集的數(shù)據(jù)集的訓(xùn)練,復(fù)雜度較高.GNN[56]GNN的深度和寬度受限時(shí),性能較差.LSTM[57]該方法適合處理高度相關(guān)的時(shí)間序列問題, 對(duì)非歐幾里得空間數(shù)據(jù)進(jìn)行處理存在一定的局限性.GAN[58]不適合處理離散形式的數(shù)據(jù)和樣本.強(qiáng)化學(xué)習(xí)GCPN[59]訓(xùn)練數(shù)據(jù)集受限.MolGAN[60]適合小型網(wǎng)絡(luò).