2021網(wǎng)絡(luò)學(xué)習(xí)綜述

網(wǎng)絡(luò)表示學(xué)習(xí)綜述引言網(wǎng)絡(luò)數(shù)據(jù)形式可以自然地表達(dá)物體和物體間的聯(lián)系,在我們的日常生活與工作中無處不在.舉例來說Facebook和新浪微博等構(gòu)成了人與人之間的社交網(wǎng)絡(luò)互聯(lián)網(wǎng)上成千上萬個(gè)頁面構(gòu)成了網(wǎng)頁鏈接的網(wǎng)絡(luò);國家城市間的運(yùn)輸交通構(gòu)成了物流網(wǎng)絡(luò).由此可見,信息網(wǎng)絡(luò)是我們生產(chǎn)生活中最為常見的一種信息載體和形式.信息社會(huì)中很多網(wǎng)絡(luò)節(jié)點(diǎn)擁有豐富的文本等外部信息,形成典型的復(fù)雜信息網(wǎng)絡(luò).基于復(fù)雜信息網(wǎng)絡(luò)的廣泛存在,對(duì)這類網(wǎng)絡(luò)信息進(jìn)行研究與分析具有非常高的學(xué)術(shù)價(jià)值和潛在應(yīng)用價(jià)值.對(duì)于復(fù)雜信息網(wǎng)絡(luò)的分析,根據(jù)信息網(wǎng)絡(luò)載體的不同,也會(huì)具有非常廣的普適性.在學(xué)術(shù)價(jià)值方面,信息網(wǎng)絡(luò)是信息的重要表達(dá)形式.隨著大數(shù)據(jù)和深度學(xué)習(xí)技術(shù)的突飛猛進(jìn),人工智能研究正面臨新一輪的爆發(fā)式發(fā)展,能否對(duì)復(fù)雜信息網(wǎng)絡(luò)做出有效合理的數(shù)據(jù)分析是今后學(xué)術(shù)研究上的熱門話題.在應(yīng)用價(jià)值方面,信息網(wǎng)絡(luò)中擁有著非常廣泛的應(yīng)用場景,如節(jié)點(diǎn)分類、鏈接預(yù)測、|V|×kRepresentationlearning

Features classificationLinkpredictionVertexsimilarity...G=(V,E)

Networkembeddings圖1(網(wǎng)絡(luò)版彩圖)網(wǎng)絡(luò)表示學(xué)習(xí)流程圖Figure1(Coloronline)The?owchartofNRL具有實(shí)際的應(yīng)用價(jià)值綜上所述針對(duì)復(fù)雜信息網(wǎng)絡(luò)的研究與應(yīng)用是人工智能學(xué)科發(fā)展的學(xué)術(shù)前沿問題,是智能信息處理和服務(wù)發(fā)展的基礎(chǔ)技術(shù)保障,針對(duì)大規(guī)模復(fù)雜信息網(wǎng)絡(luò)的學(xué)習(xí)研究十分必要.在類似Facebook和新浪微博等社交網(wǎng)絡(luò)的快速發(fā)展下,很多研究者著力于在網(wǎng)絡(luò)數(shù)據(jù)上設(shè)計(jì)快速有效的算法.在有關(guān)網(wǎng)絡(luò)的研究中,一個(gè)重要的問題就是如何合適的表示網(wǎng)絡(luò)信息.傳統(tǒng)的網(wǎng)絡(luò)表示一般使用高維的稀疏向量.但是高維稀疏的表示也成為了人們使用統(tǒng)計(jì)學(xué)習(xí)方法時(shí)的局限所在,因?yàn)楦呔S的向量將會(huì)花費(fèi)更多的運(yùn)行時(shí)間和計(jì)算空間.隨著表示學(xué)習(xí)技術(shù)在自然語言處理等領(lǐng)域的發(fā)展和廣泛應(yīng)用,研究者們轉(zhuǎn)而探索將網(wǎng)絡(luò)中的節(jié)點(diǎn)表示為低維稠密的向量表示的方法.直覺上來看,在網(wǎng)絡(luò)中拓?fù)浣Y(jié)構(gòu)相似的節(jié)點(diǎn)也應(yīng)該具有相近的向量表示.這里向量表示的相似性一般用向量間的余弦距離或者歐氏距離來表示.之后這些作為節(jié)點(diǎn)表示的向量就可以用作對(duì)應(yīng)節(jié)點(diǎn)的特征并應(yīng)用到后續(xù)的任務(wù)場景中.,尋找解決信息網(wǎng)絡(luò)背景下的各種實(shí)際問題的普適方法,有效融合網(wǎng)絡(luò)結(jié)構(gòu)與節(jié)點(diǎn)外部信息,形成更具區(qū)分性的網(wǎng)絡(luò)表示.近年來,網(wǎng)絡(luò)表示學(xué)習(xí)問題吸引了大量的研究者的目光,相關(guān)的論文工作也層出不窮,本文將針對(duì)近年來的網(wǎng)絡(luò)表示學(xué)習(xí)工作進(jìn)行系統(tǒng)性的介紹和總結(jié).網(wǎng)絡(luò)表示學(xué)習(xí)的定義本節(jié)將形式化地介紹網(wǎng)絡(luò)表示學(xué)習(xí)的意義.如圖1所示,網(wǎng)絡(luò)表示是銜接網(wǎng)絡(luò)原始數(shù)據(jù)和網(wǎng)絡(luò)應(yīng)用任務(wù)的橋梁.網(wǎng)絡(luò)表示學(xué)習(xí)算法負(fù)責(zé)從網(wǎng)絡(luò)數(shù)據(jù)中學(xué)習(xí)得到網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的向量表示,之后這些節(jié)點(diǎn)表示就可以作為節(jié)點(diǎn)的特征應(yīng)用于后續(xù)的網(wǎng)絡(luò)應(yīng)用任務(wù),如節(jié)點(diǎn)分類、鏈接預(yù)測和可視化等.ttVEV是節(jié)點(diǎn)集合E是邊的集合evivjEvi到vj的一條邊.AR|V|×|V|,Aij1(vivjE,Aij0.鄰接矩陣是網(wǎng)絡(luò)數(shù)據(jù)的一種簡單直接的表達(dá)形式.A的每一行表示了一個(gè)節(jié)點(diǎn)和所有其他節(jié)點(diǎn)的鏈接關(guān)系,可以看作是對(duì)應(yīng)節(jié)點(diǎn)的一種表示.雖然方便直接,使用鄰接矩陣的網(wǎng)絡(luò)表示受到計(jì)算效率問題的影響.A|V||V|的存儲(chǔ)空間,|V|增長到百萬級(jí)時(shí)通常是不可接受的.另一方面,0,數(shù)據(jù)十分稀疏.這種數(shù)據(jù)稀疏性使得快速有效的統(tǒng)計(jì)學(xué)習(xí)方法的應(yīng)用變得困難[1].因此,研究者們轉(zhuǎn)而為網(wǎng)絡(luò)中的節(jié)點(diǎn)學(xué)習(xí)低維稠密的向量表示.形式化地,網(wǎng)絡(luò)表示學(xué)習(xí)的目標(biāo)v∈VRv∈Rk,k|V|..通過優(yōu)化算法自動(dòng)得到而不需要特征工程的節(jié)點(diǎn)表示可以進(jìn)一步用于后續(xù)的網(wǎng)絡(luò)應(yīng)用任務(wù),如節(jié)點(diǎn)分類.這些低維的向量表示使得快速高效的算法設(shè)計(jì)成為可能,而不必再去考慮原本的網(wǎng)絡(luò)結(jié)構(gòu).基于網(wǎng)絡(luò)結(jié)構(gòu)的網(wǎng)絡(luò)表示學(xué)習(xí)隨著機(jī)器學(xué)習(xí)技術(shù)的發(fā)展,對(duì)于網(wǎng)絡(luò)中節(jié)點(diǎn)的特征學(xué)習(xí)已經(jīng)成為了一項(xiàng)非常重要的任務(wù).網(wǎng)絡(luò)表示學(xué)習(xí)算法將網(wǎng)絡(luò)信息轉(zhuǎn)化為低維稠密的實(shí)數(shù)向量,并將其用作已有的機(jī)器學(xué)習(xí)算法的輸入.舉例來說,節(jié)點(diǎn)的表示可以作為特征,送到類似支持向量機(jī)的分類器中.同時(shí),節(jié)點(diǎn)表示也可以轉(zhuǎn)化成空間坐標(biāo),用于可視化任務(wù)[2～5].下面將介紹已有的網(wǎng)絡(luò)表示學(xué)習(xí)算法和相關(guān)進(jìn)展.基于矩陣特征向量計(jì)算較早的用于網(wǎng)絡(luò)表示學(xué)習(xí)的算法主要?dú)w于此類.譜聚類算法通過計(jì)算關(guān)系矩陣的前k個(gè)特征向量或奇異向量來得到k維的節(jié)點(diǎn)表示.關(guān)系矩陣一般就是網(wǎng)絡(luò)的鄰接矩陣或者Laplace矩陣.這類方法強(qiáng)烈的依賴于關(guān)系矩陣的構(gòu)建,不同的關(guān)系矩陣的評(píng)測結(jié)果差異很大.一般來講,基于譜聚類方法的時(shí)間復(fù)雜度較高,因?yàn)樘卣飨蛄亢推娈愊蛄康挠?jì)算時(shí)間是非線性的.另一方面,譜聚類方法需要將關(guān)系矩陣整體存于內(nèi)存之中,所以空間復(fù)雜度也是不能忽略的.這些局限性阻止了這類算法在大規(guī)模數(shù)據(jù)和在線平臺(tái)上的擴(kuò)展應(yīng)用.現(xiàn)在將展示幾種譜聚類算法的實(shí)例.這些方法的適用性如表1所示.(locallylinearembedding)[6,7]假設(shè)節(jié)點(diǎn)的表示是從同一個(gè)流形中采樣得到的.局部線性表示假設(shè)一個(gè)節(jié)點(diǎn)和它鄰居的表示都位于該流形的一個(gè)局部線性的區(qū)域.也就是說,一個(gè)節(jié)點(diǎn).局部線性表示使用鄰居節(jié)點(diǎn)表示的加權(quán).最小化損失函數(shù)的優(yōu)化問題最終轉(zhuǎn)化成某個(gè)關(guān)系矩陣特征向量計(jì)算問題求解.Laplace(Laplaceeigenmap)[8,9]簡單的假設(shè)兩個(gè)相連的節(jié)點(diǎn)的表示應(yīng)該相近.特別地,這里表示相近是由向量表示的歐氏距離的平方來定義Laplace矩陣的特征向量計(jì)算問題.有向圖表示(directedgraphembedding)[10]進(jìn)一步擴(kuò)展了Laplace特征表方法,給不同點(diǎn)的損失函數(shù)以不同的權(quán)重.其中點(diǎn)的權(quán)重是由基于隨機(jī)游走的排序方法來決定,如PageRank.不同于前面的方法,Liu[11](com-munity)的強(qiáng)度,(modularity)引入了損失函數(shù).模塊性是衡量網(wǎng)絡(luò)分離程度的指標(biāo),高的模塊性值意味著在同一模塊內(nèi)節(jié)點(diǎn)連接緊密,而不同模塊間節(jié)點(diǎn)連接稀疏.最終該優(yōu)化問題轉(zhuǎn)化為Laplace矩陣的特征向量計(jì)算此類方法一般先定義一個(gè)關(guān)于節(jié)點(diǎn)表示的線性或二次損失函數(shù).然后將最優(yōu)化問題轉(zhuǎn)化為某個(gè)關(guān)系矩陣的特征向量計(jì)算問題.這一類方法最主要的缺點(diǎn)在于復(fù)雜度:大規(guī)模矩陣的特征向量計(jì)算是非常消耗計(jì)算時(shí)間和空間的.表1局部線性表示(LLE)、Laplace特征表(Laplaceeigenmap)、有向圖表示(DGE)的適用性比較Table1ThecomparisonofLLE,Laplaceeigenmap,andDGEGraphtypeModel Undirected DirectedLLE C – –Laplaceeigenmap C C –DGE C C C表2DeepWalk算法和word2vec的類比Table2ThecomparisonbetweenDeepWalkandword2vecModelTargetInputOutputWord2vecWordsSentencesWordembeddingsDeepWalkNodesNodesequencesNodeembeddings基于簡單神經(jīng)網(wǎng)絡(luò)的算法3.1小節(jié)介紹的方法中,對(duì)最優(yōu)化問題求最優(yōu)解的過程,如特征向量的計(jì)算,對(duì)于大規(guī)模的網(wǎng)絡(luò)數(shù)據(jù)來說是非常耗時(shí)的.另一方面,基于神經(jīng)網(wǎng)絡(luò)的方法已經(jīng)在自然語言和圖像處理領(lǐng)域上取得了非常突出的成果.雖然梯度下降的參數(shù)更新方法無法保證總是得到最優(yōu)化問題的最優(yōu)解,但是神經(jīng)網(wǎng)絡(luò)的方法一般更加快速而且也能得到相當(dāng)不錯(cuò)的結(jié)果.DeepWalk算法[1]第一次將深度學(xué)習(xí)中的技術(shù)引入到網(wǎng)絡(luò)表示學(xué)習(xí)領(lǐng)域.DeepWalk算法充分利用了網(wǎng)絡(luò)結(jié)構(gòu)中的隨機(jī)游走序列的信息.使用隨機(jī)游走序列而不是鄰接矩陣的優(yōu)勢有兩點(diǎn):首先,隨機(jī)游走序列只依賴于局部信息,所以可以適用于分布式和在線系統(tǒng),而使用鄰接矩陣就必須把所有信息存儲(chǔ)于內(nèi)存中處理,面臨著較高的計(jì)算時(shí)間和空間消耗.第二,對(duì)隨機(jī)游走序列進(jìn)行建?？梢越档徒?-1二值鄰接矩陣的方差和不確定性.無監(jiān)督表示學(xué)習(xí)方法在自然語言處理領(lǐng)域已經(jīng)得到了廣泛的學(xué)習(xí)與應(yīng)用.Perozzi等[1]通過實(shí)驗(yàn)驗(yàn)證了隨機(jī)游走序列中節(jié)點(diǎn)和文檔中的單詞一樣都遵從指數(shù)定律(power-law),從而進(jìn)一步將著名的詞表示學(xué)習(xí)算法word2vec[12～14]應(yīng)用在隨機(jī)游走序列上,學(xué)習(xí)節(jié)點(diǎn)表示.w形式化地,viwvi?wvi?1vi+1vi+w.vi,產(chǎn)生兩側(cè)節(jié)點(diǎn)的概率.作為模型簡化,Skip-Gram模型忽略了節(jié)點(diǎn)的順序和距離中心節(jié)點(diǎn)的距離.(1)表示:wminR

kw,k=0

?logPr(vi+k|Ri), (1)其中Pr(vi+k|Ri)由式(2)定義的softmax函數(shù)得到:exp(RiCT)∑||Pr(vj|Ri)= Vk∑||

jkexp(RiCT)k

. (2)2word2vec的類比情況.首先在網(wǎng)絡(luò)上采樣生成大量的隨機(jī)游走序列,Skip-gramHierarchicalSoftmax模型對(duì)隨機(jī)游走序列中每個(gè)局部窗口內(nèi)的節(jié)點(diǎn)對(duì)進(jìn)行概率建模,最大化隨機(jī)游走序列的似然概率,并最終使用隨機(jī)梯度下降學(xué)習(xí)參數(shù).表3不同網(wǎng)絡(luò)表示學(xué)習(xí)方法的比較Table3ThecomparisonofvariousNRLmethodsMethod Matrix Accuracy Speed Spectralclustering L Precise Lowk=1KGraRep Ak,k=1KGraRep Ak,k=1,...,K Precise Slow

Approximate Medium基于簡單神經(jīng)網(wǎng)絡(luò)的另一個(gè)代表性的網(wǎng)絡(luò)表示學(xué)習(xí)算法就是LINE算法[15].Tang等[15]提出了一種可以適用于大規(guī)模的有向帶權(quán)圖的網(wǎng)絡(luò)表示學(xué)習(xí)算法.為了對(duì)節(jié)點(diǎn)間的關(guān)系進(jìn)行建模,LINE算法用觀察到的節(jié)點(diǎn)間連接刻畫了第一級(jí)相似度關(guān)系,用不直接相連的兩個(gè)節(jié)點(diǎn)的共同鄰居刻畫了這兩個(gè)點(diǎn)之間的第二級(jí)相似度關(guān)系.直覺上說,對(duì)直接相連的兩個(gè)節(jié)點(diǎn)間關(guān)系的刻畫等價(jià)于對(duì)原始網(wǎng)絡(luò)的鄰接矩陣的建模.但是一個(gè)網(wǎng)絡(luò)中的邊關(guān)系往往是非常稀疏的,所以有必要進(jìn)一步刻畫第二級(jí)相似度關(guān)系來考慮雖然并不直接相連,但是共同鄰居較多的節(jié)點(diǎn)對(duì),從而對(duì)第一級(jí)相似度的信息予以補(bǔ)充.具體來說,LINE算法對(duì)所有的第一級(jí)相似度和第二級(jí)相似度節(jié)點(diǎn)對(duì)進(jìn)行了概率建模,并最小化該概率分布和經(jīng)驗(yàn)分布之間的KL距離.參數(shù)學(xué)習(xí)由隨機(jī)梯度下降算法決定.基于矩陣分解的方法給定關(guān)系矩陣,對(duì)關(guān)系矩陣進(jìn)行矩陣分解達(dá)到降維的效果,從而得到節(jié)點(diǎn)的網(wǎng)絡(luò)表示.Yang等[16]證明了DeepWalk算法實(shí)際上等價(jià)于某個(gè)特定關(guān)系矩陣的矩陣分解.由此可見,矩陣分解算法也是學(xué)習(xí)網(wǎng)絡(luò)表示的一種重要手段.GraRep算法[17]考慮了一種特別的關(guān)系矩陣.GraRepSVD分解對(duì)該關(guān)系矩陣進(jìn)行降維從k步網(wǎng)絡(luò)表示.形式化地,A進(jìn)行行歸一化處理,A中每行的加1.GraRepkAk,k步的隨機(jī)游走抵達(dá)的概率.更進(jìn)一步,GraRepk值,k值對(duì)k步網(wǎng)絡(luò)表示拼接起來,.GraRep的主要缺點(diǎn)在Ak的時(shí)候計(jì)算效率很低.Yang等[18]在其后續(xù)工作中將基于矩陣分解或者可以轉(zhuǎn)化為矩陣分解的方法總結(jié)成同一個(gè)算法框架:第一步構(gòu)建節(jié)點(diǎn)間的關(guān)系矩陣,第二步對(duì)該矩陣進(jìn)行矩陣分解操作得到網(wǎng)絡(luò)表示.該工作將譜聚類方法[11],DeepWalk和GraRep方法第一步構(gòu)建關(guān)系矩陣的過程進(jìn)行了分析對(duì)比,并總結(jié)在表3中,其中L是Laplace矩陣.通過對(duì)表3的觀察,可以得出兩個(gè)結(jié)論.一是對(duì)更高階的關(guān)系矩陣Ak的構(gòu)建可以提升網(wǎng)絡(luò)表示的效果,二是精確的計(jì)算高階的關(guān)系矩陣Ak計(jì)算效率很低.這兩個(gè)結(jié)論促使我們尋找一種可以間接近似高階的關(guān)系矩陣且不增加計(jì)算復(fù)雜度的方法.Yang等[18]提出了一種簡單的網(wǎng)絡(luò)表示更新策略NEU,如式(3)所示:Rnew=R+λ1A·R+λ2A·(A·R), (3)其中λ1,λ2是超參數(shù),一般設(shè)置為0.5和0.25.該工作證明了式(3)中的策略可以讓更新后的網(wǎng)絡(luò)表示近似等價(jià)于從更高階的關(guān)系矩陣中分解而來,而不增加計(jì)算復(fù)雜度.實(shí)際上,當(dāng)該算法作用于DeepWalk算法的輸出結(jié)果時(shí),只占用DeepWalk算法1%的時(shí)間,就可以有非常顯著的提升效果.Unsupervisedcomponent(Localstructurepreservedcost)

Unsupervisedcomponent(Localstructurepreservedcost)SupervisedcomponentSupervisedcomponent(Globalstructurepreservedcost)ParametersharingLaplaceeigenmapsi j圖2(網(wǎng)絡(luò)版彩圖)SDNE算法(修改自文獻(xiàn)[19]）Figure2(Coloronline)TheframeworkofSDNE(modi?edfrom[19])基于深層神經(jīng)網(wǎng)絡(luò)的方法和之前使用淺層神經(jīng)網(wǎng)絡(luò)的方法不同,SDNE[19]使用深層神經(jīng)網(wǎng)絡(luò)對(duì)節(jié)點(diǎn)表示間的非線性進(jìn)行建模.整個(gè)模型可以被分為兩個(gè)部分:一個(gè)是由Laplace矩陣監(jiān)督的建模第一級(jí)相似度的模塊,另一個(gè)是由無監(jiān)督的深層自編碼器對(duì)第二級(jí)相似度關(guān)系進(jìn)行建模.最終SDNE算法將深層自編碼器的中間層作為節(jié)點(diǎn)的網(wǎng)絡(luò)表示,模型如圖2所示.基于社區(qū)發(fā)現(xiàn)的算法如譜聚類算法中展示的,研究者已經(jīng)考慮從社區(qū)發(fā)現(xiàn)角度學(xué)習(xí)網(wǎng)絡(luò)表示.具體來說,就是讓節(jié)點(diǎn)表示的每一維對(duì)應(yīng)該節(jié)點(diǎn)從屬于一個(gè)社區(qū)的強(qiáng)度,然后設(shè)計(jì)最優(yōu)化目標(biāo)進(jìn)行求解.這類算法會(huì)學(xué)習(xí)得到上述的社區(qū)強(qiáng)度關(guān)系表示,然后轉(zhuǎn)化為社區(qū)發(fā)現(xiàn)的結(jié)果.而學(xué)習(xí)社區(qū)強(qiáng)度關(guān)系表示的過程可以看作是無監(jiān)督的非負(fù)節(jié)點(diǎn)表示學(xué)習(xí)的過程.BIGCLAM[20]作為一個(gè)可覆蓋社區(qū)發(fā)現(xiàn)算法,為每個(gè)網(wǎng)絡(luò)中的節(jié)點(diǎn)學(xué)習(xí)了一個(gè)上述的k維非負(fù)向量表示.BIGCLAM算法對(duì)網(wǎng)絡(luò)中每條邊的生成概率進(jìn)行建模:兩個(gè)點(diǎn)的向量表示內(nèi)積越大,那么這兩個(gè)點(diǎn)之間形成邊的概率也就越高.算法的最大化目標(biāo)是整個(gè)網(wǎng)絡(luò)結(jié)構(gòu)的最大似然概率.最優(yōu)化求解參數(shù)的過程由隨機(jī)梯度下降算法實(shí)現(xiàn).保存特殊性質(zhì)的網(wǎng)絡(luò)表示使用向量表示代替原始網(wǎng)絡(luò)的策略在帶來便利的同時(shí),也會(huì)丟失很多原始網(wǎng)絡(luò)中的信息.比如大.但內(nèi)積或者余弦距離都.如社區(qū)(community)等信息,也會(huì)在網(wǎng)絡(luò)表示學(xué)習(xí)的過程中丟失.SlidingwindowSlidingwindowVertexembeddingsCommunityembeddingAssignedcommunitiesCommunityembeddingsVertexsequence1234567RandomwalksonanetworkCommunity12Community2Community3713564圖3(網(wǎng)絡(luò)版彩圖)CNRL算法(修改自文獻(xiàn)[22])Figure3(Coloronline)TheframeworkofCNRL(modi?edfrom[22])HOPE[21]為每個(gè)節(jié)點(diǎn)刻畫了兩種不同的表示,并著眼于保存原始網(wǎng)絡(luò)中的非對(duì)稱性信息.HOPE構(gòu)建了不同的非對(duì)稱的關(guān)系矩陣,JDGSVD算法進(jìn)行矩陣降維得到節(jié)點(diǎn)的網(wǎng)絡(luò)表示.CNRL算法[22]考慮了在節(jié)點(diǎn)表示中嵌入網(wǎng)絡(luò)隱藏的社區(qū)信息.如圖3所示,CNRL假設(shè)每個(gè)節(jié)點(diǎn)屬于多個(gè)社區(qū),也就是每個(gè)節(jié)點(diǎn)在所有的社區(qū)上有一個(gè)概率分布.DeepWalk將隨機(jī)游走生成的節(jié)點(diǎn)序列看作句子,將序列中的節(jié)點(diǎn)看作文本中的詞,直接用訓(xùn)練詞向量的Skip-Gram模型來訓(xùn)練節(jié)點(diǎn)向量.受這種類比的啟發(fā),CNRL將網(wǎng)絡(luò)中的社區(qū)看作文本中的主題,也就是說,網(wǎng)絡(luò)中相關(guān)的節(jié)點(diǎn)傾向于行程社區(qū),而文本中相關(guān)的詞則會(huì)構(gòu)成主題.因此,CNRL算法在生成的隨機(jī)游走序列上,將每個(gè)節(jié)點(diǎn)序列看成一篇文檔,通過基于Gibbs采樣的LDA[23]來學(xué)習(xí)每個(gè)節(jié)點(diǎn)的社區(qū)分布,并通過隨機(jī)采樣的方式,來給序列中的節(jié)點(diǎn)分配其對(duì)應(yīng)的社區(qū)標(biāo)簽.隨后,在Skip-Gram模型的基礎(chǔ)上,用中心節(jié)點(diǎn)的節(jié)點(diǎn)表示和對(duì)應(yīng)的社區(qū)表示同時(shí)去預(yù)測隨機(jī)游走序列中的鄰近節(jié)點(diǎn),從而將社區(qū)結(jié)構(gòu)信息保存在節(jié)點(diǎn)表示中.為了對(duì)通過主題模型檢測出的社區(qū)有一個(gè)直觀的感受,驗(yàn)證將網(wǎng)絡(luò)中的社區(qū)類比為文本中的主題的正確性,CNRL對(duì)一個(gè)小的Karate網(wǎng)絡(luò)進(jìn)行了社區(qū)發(fā)現(xiàn)結(jié)果的可視化,如圖4所示.可以發(fā)現(xiàn),CNRL能夠有效檢測出不同規(guī)模的有重疊的社區(qū),以及有效的識(shí)別出社區(qū)邊界. 4(網(wǎng)絡(luò)版彩圖)Karate(CNRL-2CNRL-4)([22])Figure4(Coloronline)CommunitydetectionresultsonKarateunfolding,CNRL-2,CNRL-4)(modi?edfrom[22])M|V| kMWTft |V|WTHT|V| HT|V|圖5(網(wǎng)絡(luò)版彩圖)TADW算法(修改自文獻(xiàn)[16])Figure5(Coloronline)TheframeworkofTADW(modi?edfrom[16])結(jié)合外部信息的網(wǎng)絡(luò)表示學(xué)習(xí)真實(shí)世界中的網(wǎng)絡(luò)節(jié)點(diǎn)往往會(huì)伴隨著豐富的外部信息,.而傳統(tǒng)網(wǎng)絡(luò)表示學(xué)習(xí)主要依賴于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息,而忽略了這些異質(zhì)的外部信息.因此,如何能夠在網(wǎng)絡(luò)表示學(xué)習(xí)過程中考慮這些外部信息提高網(wǎng)絡(luò)表示的質(zhì)量和增強(qiáng)表示向量在網(wǎng)絡(luò)分析任務(wù)上的效果,是網(wǎng)絡(luò)表示學(xué)習(xí)領(lǐng)域的重要挑戰(zhàn).結(jié)合文本信息的方法在網(wǎng)絡(luò)數(shù)據(jù)中,除去節(jié)點(diǎn)間的邊信息以外,也會(huì)有很多依存于網(wǎng)絡(luò)的文本信息.比如社交網(wǎng)絡(luò)中,除去用戶間的好友關(guān)系,也會(huì)有豐富的用戶狀態(tài)或者博客內(nèi)容等文本信息.我們可以利用這些文本信息作為網(wǎng)絡(luò)結(jié)構(gòu)信息的補(bǔ)充,進(jìn)一步增強(qiáng)網(wǎng)絡(luò)節(jié)點(diǎn)表示的強(qiáng)度和效果.[16]在矩陣分解框架下,將節(jié)點(diǎn)的文本特征引入網(wǎng)絡(luò)表示學(xué)習(xí).5所示,算法算法進(jìn)一步加強(qiáng)得到:M3個(gè)小的矩陣乘積,其T是固定的文本特征向量,另外兩個(gè)矩陣是參數(shù)矩陣.算法使用共軛梯度下降法WH矩陣求解參數(shù).真實(shí)世界中的網(wǎng)絡(luò)節(jié)點(diǎn)在與其他節(jié)點(diǎn)進(jìn)行交互時(shí),往往會(huì)展現(xiàn)出不同方面的特點(diǎn).例如,一個(gè)研究者與不同的研究者發(fā)生合作關(guān)系往往因?yàn)椴煌难芯恐黝};社交媒體中的用戶會(huì)因?yàn)椴煌脑蚺c其他用戶建立聯(lián)系.然而,已有的網(wǎng)絡(luò)表示學(xué)習(xí)方法會(huì)給每個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)學(xué)習(xí)一個(gè)固定的表示向量,不能展現(xiàn)出同一節(jié)點(diǎn)對(duì)于不同鄰居節(jié)點(diǎn)角色的變化.此外,這些方法不能對(duì)節(jié)點(diǎn)之間的關(guān)系進(jìn)行有效的建模和解釋.因此,CANE[24]利用網(wǎng)絡(luò)節(jié)點(diǎn)的文本信息來對(duì)節(jié)點(diǎn)之間的關(guān)系進(jìn)行解釋,來為網(wǎng)絡(luò)節(jié)點(diǎn)根據(jù)不同的鄰居學(xué)習(xí)上下文相關(guān)的網(wǎng)絡(luò)表示. apFaqColumn-pooling+softmaxRow-pooling+apFaqColumn-pooling+softmaxRow-pooling+softmaxPQAuvConvolutionalunit(V)ut=P·apTextembeddingEdgeTextdescriptionTextdescriptionConvolutionalunittanh(PTAQ)(V)ut=Q·aqFigure6TheframeworkofCANE(modi?edfrom[24])CANE假設(shè)每個(gè)節(jié)點(diǎn)的表示向量由文本表示向量及結(jié)構(gòu)表示向量構(gòu)成,其中,文本表示向量的生成過程與邊上的鄰居相關(guān),所以生成的節(jié)點(diǎn)表示也是上下文相關(guān)的.如圖6所示,CANE利用卷積神經(jīng)網(wǎng)絡(luò)對(duì)一條邊上兩個(gè)節(jié)點(diǎn)的文本信息進(jìn)行編碼.在文本表示生成的過程中,利用相互注意力機(jī)制,選取兩個(gè)節(jié)點(diǎn)彼此最相關(guān)的卷積結(jié)果構(gòu)成最后的文本表示向量.半監(jiān)督的網(wǎng)絡(luò)表示學(xué)習(xí)無監(jiān)督的網(wǎng)絡(luò)表示學(xué)習(xí)中,其后續(xù)任務(wù)很多是以節(jié)點(diǎn)表示作為特征的節(jié)點(diǎn)分類任務(wù).之前的工作主要基于無監(jiān)督的網(wǎng)絡(luò)表示學(xué)習(xí),在針對(duì)節(jié)點(diǎn)分類等機(jī)器學(xué)習(xí)任務(wù)時(shí),缺少區(qū)分性.半監(jiān)督的網(wǎng)絡(luò)表示學(xué)習(xí)的想法就是把已經(jīng)標(biāo)注的節(jié)點(diǎn)的節(jié)點(diǎn)類別或者標(biāo)簽利用起來,加入到網(wǎng)絡(luò)表示學(xué)習(xí)的過程中,從而針對(duì)性的提升節(jié)點(diǎn)網(wǎng)絡(luò)表示在后續(xù)分類任務(wù)中的效果.為了解決這個(gè)問題,Tu等[25]提出了一種半監(jiān)督的網(wǎng)絡(luò)表示學(xué)習(xí)方法MMDW,來學(xué)習(xí)有區(qū)分性MMXTboundaryMax-marginclassifierClassificationBiasedgradient SupportvectorsYDeepWalkasmatrixfactorization圖7(網(wǎng)絡(luò)版彩圖)MMDW算法(修改自文獻(xiàn)[25])Figure7(Coloronline)TheframeworkofMMDW(modi?edfrom[25])的網(wǎng)絡(luò)表示.如圖7所示,MMDW同時(shí)學(xué)習(xí)矩陣分解形式的網(wǎng)絡(luò)表示模型和最大間隔分類器.為了增大網(wǎng)絡(luò)表示的區(qū)分性,MMDW會(huì)針對(duì)分類邊界上的支持向量計(jì)算其偏置向量,使其在學(xué)習(xí)過程中向正確的類別方向進(jìn)行偏置,從而增大表示向量的區(qū)分能力..MMDW模型使用半監(jiān)督訓(xùn)練表示的優(yōu)勢.此外,在網(wǎng)絡(luò)表示的可視化中(8),.[26]也采用了類似的方式,模型和最大間隔分類器,來提高網(wǎng)絡(luò)節(jié)點(diǎn)分類的效果.Node2vec[27]算法.選取隨機(jī)游走序列中下一個(gè)節(jié)點(diǎn)的方式是均勻隨機(jī)分布的.node2vecpq將寬度.寬度優(yōu)先搜索注重鄰近的節(jié)點(diǎn)并刻畫了相對(duì)局部的一種網(wǎng)絡(luò)表示,寬度優(yōu)先中的節(jié)點(diǎn)一般會(huì)出現(xiàn)很多次,從而降低刻畫中心節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的方差;深度優(yōu)先搜索反應(yīng)了更高層面上的節(jié)點(diǎn)間的同質(zhì)性.特別地,node2vecpq控制隨機(jī)游走序列的跳轉(zhuǎn)概率,9所示,假設(shè)上一步(t,v),v的不同鄰居,node2vecpq定義了不同的鄰居的跳轉(zhuǎn)概率,p控制跳向上一個(gè)節(jié)點(diǎn)的鄰居的概率q控制跳向上一個(gè)節(jié)點(diǎn)的非鄰居的概率具體的未歸一的跳轉(zhuǎn)概(a)10(a)86Dimension1Dimension14Dimension1Dimension12024681015 10 5 0 5 10 Dimension2

8(b)6(b)420246815 10 5 0 5 10Dimension2圖8(網(wǎng)絡(luò)版彩圖)DeepWalk和MMDW可視化結(jié)果(修改自文獻(xiàn)[14])Figure8(Coloronline)Thevisualizationresultsof(a)DeepWalkand(b)MMDW(modi?edfrom[14])xx1x2α=1vα=1/qα=1/qα=1/px3t圖9Node2vec算法(修改自文獻(xiàn)[27])Figure9Theframeworkofnode2vec(modi?edfrom[27])率值πvx=αpq(t,x)如下所示:

αpq(t,x)=

1,ifdtx=0,p,ifdtx=p11

(4)q,ifdtx=2.其中,dtx表示節(jié)點(diǎn)t和x之間的最短距離.為了獲得最優(yōu)的超參數(shù)p和q的取值,node2vec通過半監(jiān)督形式,利用網(wǎng)格搜索最合適的參數(shù)學(xué)習(xí)節(jié)點(diǎn)表示.其他的半監(jiān)督網(wǎng)絡(luò)表示學(xué)習(xí)方法還包括:GCN[28]設(shè)計(jì)了一種作用于網(wǎng)絡(luò)結(jié)構(gòu)上的卷積神經(jīng)網(wǎng)絡(luò),并使用一種基于邊的標(biāo)簽傳播規(guī)則實(shí)現(xiàn)半監(jiān)督的網(wǎng)絡(luò)表示學(xué)習(xí).Planetoid[29]聯(lián)合地預(yù)測一個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)和類別標(biāo)簽,類別標(biāo)簽同時(shí)取決于節(jié)點(diǎn)表示和已知節(jié)點(diǎn)標(biāo)簽,從而進(jìn)行半監(jiān)督表示學(xué)習(xí).EdgeautoencoderEdgeautoencoderReconstructededgevectorulv′TranslationmechanismBinaryedgevectorLabel#5Edgewithmulti-labelsLabel#2uv圖10(網(wǎng)絡(luò)版彩圖)TransNet算法(修改自文獻(xiàn)[30])Figure10(Coloronline)TheframeworkofTransNet(modi?edfrom[30])結(jié)合邊上標(biāo)簽信息的網(wǎng)絡(luò)表示學(xué)習(xí)節(jié)點(diǎn)與節(jié)點(diǎn)之間也存在著豐富的交互信息例如社交;論文合作網(wǎng)絡(luò)中,研究者之間存在合作的論文的具體信息.然而,已有的網(wǎng)絡(luò)表示學(xué)習(xí)模型更側(cè)重于節(jié)點(diǎn)本身的信息,0,1值或者連續(xù)的實(shí)值而忽略邊上豐富的語義信息同時(shí),而忽略了對(duì)節(jié)點(diǎn)之間具體關(guān)系的建模和預(yù)測能力.為了解決關(guān)系的建模和預(yù)測問題,等[30]模型,利用平移機(jī)制來解決社會(huì)關(guān)系抽取問題.10所示,假設(shè)頭結(jié)點(diǎn)表示向量加上關(guān)系表示向量等于尾節(jié)點(diǎn)表示向量.其中,,對(duì)交互文本抽取出標(biāo)簽集合來表示關(guān)系.隨后,通過深層自動(dòng)編碼器對(duì)標(biāo)簽集合進(jìn)行壓縮,來得到關(guān)系的表示向量.該模型能夠有效地預(yù)測未標(biāo)注的邊上的標(biāo)簽集合,在社會(huì)關(guān)系抽取任務(wù)上取得了顯著的提升.評(píng)測任務(wù)和應(yīng)用場景節(jié)點(diǎn)分類在進(jìn)行網(wǎng)絡(luò)數(shù)據(jù)的分析時(shí),一個(gè)最常見的場景就是對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行合理的劃分.舉例來說,在社交網(wǎng)絡(luò)上,不同的用戶可以根據(jù)他們的興趣愛好不同分為不同的類別.然而實(shí)際數(shù)據(jù)中的類別標(biāo)注信息是十分稀疏的,所以需要設(shè)計(jì)算法利用節(jié)點(diǎn)間的連接關(guān)系以及少量的已標(biāo)注分類信息,對(duì)大量表4Cora數(shù)據(jù)集上的分類結(jié)果Table4Classi?cationresultsonCoraAccuracy(%)

10%a)10%a)50%a)90%a)GF50.8(68.0)61.8(77.0)64.8(77.2)4(+0.1)SC55.9(68.7)70.8(79.2)72.7(80.0)1(+0.1)DeepWalk71.3(76.2)76.9(81.6)78.7(81.9)31(+0.1)LINE1st64.8(70.1)76.1(80.9)78.9(82.2)62(+0.1)LINE2nd63.3(73.3)73.4(80.1)75.6(80.3)67(+0.1)node2vec76.9(77.5)81.0(81.6)81.4(81.9)56(+0.1)TADW78.1(84.4)83.1(86.6)82.4(87.7)2(+0.1)GraRep70.8(76.9)78.9(82.8)81.8(84.0)67(+0.3)Thenumbermeanstrainingratio.表5BlogCatalog數(shù)據(jù)集上的分類結(jié)果Table5Classi?cationresultsonBlogCatalogMacro-F1(%) Micro-F1

1%a)1%a)5%a)9%a)1%a)5%a)9%a)GF6.6(7.9)9.8(11.3)10.3(12.2)17.0(19.6)22.2(25.0)23.7(26.7)19(+1)SC8.4(9.3)13.1(14.8)14.5(17.0)19.4(20.3)26.9(28.1)29.0(31.0)10(+1)DeepWalk12.4(13.6)18.3(20.1)20.4(22.0)24.9(26.4)31.5(33.7)33.7(35.9)935(+1)LINE1st11.1(12.2)16.6(18.3)18.6(20.1)23.1(24.7)29.3(31.6)31.8(33.5)241(+1)LINE2nd10.3(11.2)15.0(16.8)16.5(18.3)21.5(25.0)27.9(31.6)30.0(33.6)244(+1)node2vec12.5(13.0)19.2(19.8)21.9(22.5)25.0(27.0)31.9(34.5)35.1(37.2)454(+1)a)ThesameasinTable4.表6Flickr數(shù)據(jù)集上的分類結(jié)果Table6Classi?cationresultsonFlickrMacro-F1(%) Micro-F1

1%a)1%a)5%a)9%a)1%a)5%a)9%a)GF4.3(5.2)4.9(5.4)5.0(5.4)21.1(21.8)22.0(23.1)21.7(23.4)241(+8)SC8.6(10.9)11.6(14.3)12.3(15.0)24.1(29.2)27.5(34.1)28.3(34.7)102(+8)DeepWalk10.5(11.6)17.1(17.8)19.1(19.8)31.8(33.1)36.3(36.7)37.3(37.6)9,292(+8)LINE1st10.3(10.7)16.0(16.6)17.6(18.2)32.0(32.7)35.9(36.4)36.8(37.2)2,664(+8)LINE2nd7.8(8.5)13.1(13.5)14.7(15.2)30.0(31.0)34.2(34.4)35.1(35.2)2,740(+8)a)ThesameasinTable4.的未標(biāo)注節(jié)點(diǎn)的分類情況進(jìn)行標(biāo)注.類似的任務(wù)場景還有對(duì)互聯(lián)網(wǎng)上的各個(gè)網(wǎng)頁進(jìn)行內(nèi)容上的分類.在節(jié)點(diǎn)分類的應(yīng)用上,根據(jù)算法預(yù)測的未標(biāo)注節(jié)點(diǎn)的類別可以為節(jié)點(diǎn)的標(biāo)簽進(jìn)行推薦,節(jié)約手工標(biāo)注的人力成本在各類網(wǎng)絡(luò)場景都有非常實(shí)際的應(yīng)用.4～6Cora,BlogCatalogFlickr3個(gè)公開數(shù)據(jù)集上的節(jié)點(diǎn)分類效果對(duì)比.NEU更新后的分類效果.時(shí)間一列記錄了各算法的運(yùn)行時(shí)間,NEU更新算法所花費(fèi)的額外運(yùn)行CNJaccardSaltonGFGF+NEUSCSC+NEUCNJaccard