基于雙視角的耦合網(wǎng)絡(luò)表示學(xué)習(xí)算法①

倪琦瑄,張 霞,卜 湛

1(南京財(cái)經(jīng)大學(xué) 信息工程學(xué)院,南京 210003)

2(南京中醫(yī)藥大學(xué) 人工智能與信息技術(shù)學(xué)院,南京 210023)

3(南京財(cái)經(jīng)大學(xué) 江蘇省電子商務(wù)重點(diǎn)實(shí)驗(yàn)室,南京 210003)

1 引言

現(xiàn)實(shí)世界中許多的社會(huì),物理和信息系統(tǒng)都是以復(fù)雜網(wǎng)絡(luò)的形式存在的[1].在這些網(wǎng)絡(luò)中,人們通過(guò)挖掘網(wǎng)絡(luò)的潛在信息可以解決許多實(shí)際的問(wèn)題,例如鏈路預(yù)測(cè)[2],鏈路重構(gòu)[3],節(jié)點(diǎn)分類[4],邊分類等.網(wǎng)絡(luò)表示學(xué)習(xí)將節(jié)點(diǎn)映射到潛在空間[5],并保留了豐富的結(jié)構(gòu)信息,為這些下游數(shù)據(jù)挖掘任務(wù)提供了一種新的解決方法,已在許多論文中被證明能夠非常有效地解決上述任務(wù)[6-13].

近10年里,有很多能夠保持網(wǎng)絡(luò)的結(jié)構(gòu)特性的方法被提出來(lái).然而,以往的研究往往只注重節(jié)點(diǎn)視角下的網(wǎng)絡(luò)拓?fù)湫畔?而沒(méi)有充分考慮邊視角.現(xiàn)有的網(wǎng)絡(luò)表示學(xué)習(xí)算法可以分為兩大類:基于隨機(jī)游走的網(wǎng)絡(luò)表示學(xué)習(xí)算法和基于深度學(xué)習(xí)框架的網(wǎng)絡(luò)表示學(xué)習(xí)算法.基于隨機(jī)游走的網(wǎng)絡(luò)表示學(xué)習(xí)算法,例如DeepWalk[8]和Node2Vec[9],主要分為隨機(jī)游走和Skip-gram[10]算法兩部分,他們通過(guò)隨機(jī)游走以獲取節(jié)點(diǎn)視角下的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),再利用Skipgram 模型對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行更新學(xué)習(xí),Node2Vec在DeepWalk的基礎(chǔ)上,加入了帶有偏置的隨機(jī)游走,使得其能以不同偏好的游走方式獲取節(jié)點(diǎn)的同質(zhì)性和結(jié)構(gòu)等價(jià)性.Line[11]也是一種基于鄰域相似假設(shè)的網(wǎng)絡(luò)表示學(xué)習(xí)算法,通過(guò)設(shè)置兩種鄰近性構(gòu)造目標(biāo)函數(shù)來(lái)獲取節(jié)點(diǎn)的局部相似性和鄰居相似性.然而,這些算法往往只關(guān)注了節(jié)點(diǎn)視角下網(wǎng)絡(luò)拓?fù)湫畔?而沒(méi)有充分考慮邊視角.基于深度學(xué)習(xí)的網(wǎng)絡(luò)表示算法,如SDNE[12],利用半監(jiān)督的自動(dòng)編碼器模型來(lái)學(xué)習(xí)網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的表示向量,DNGR[13]則通過(guò)Random Surfing 模擬隨機(jī)游走過(guò)程獲取網(wǎng)絡(luò)拓?fù)湫畔?再利用堆疊降噪自編碼器對(duì)節(jié)點(diǎn)表示向量進(jìn)行訓(xùn)練.GAE[14]通過(guò)圖卷積作為自編碼器的編碼方式,為每個(gè)節(jié)點(diǎn)聚合其鄰居的特征信息,再利用解碼器重構(gòu)網(wǎng)絡(luò)的鄰接信息.這些基于深度學(xué)習(xí)架的網(wǎng)絡(luò)表示學(xué)習(xí)算法往往效果很好,但其涉及到許多復(fù)雜計(jì)算,其空間和時(shí)間復(fù)雜度隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大面臨著巨大的挑戰(zhàn),同時(shí),這些算法也只關(guān)注了節(jié)點(diǎn)視角下的節(jié)點(diǎn)之間的連接信息,而沒(méi)有考慮過(guò)邊視角.而在已有的針對(duì)邊的一些研究中,大多考慮的是邊上的屬性或標(biāo)簽信息[15,16].如NEES[15]通過(guò)邊計(jì)算節(jié)點(diǎn)之間關(guān)系的相似性,從而設(shè)置帶有偏好的隨機(jī)游走,使得節(jié)點(diǎn)的隨機(jī)游走的每一步都與上一步有盡可能相似的關(guān)系.ELAINE[16]則通過(guò)重構(gòu)每種邊的標(biāo)簽向量,使得最終學(xué)習(xí)得到的節(jié)點(diǎn)向量能夠同時(shí)包含邊的標(biāo)簽信息和網(wǎng)絡(luò)結(jié)構(gòu)信息.事實(shí)上,不同的視角會(huì)帶來(lái)不同的有效信息,比如不同的社區(qū)劃分.因此,本文將研究重點(diǎn)從節(jié)點(diǎn)轉(zhuǎn)移到邊.利用邊圖(line graph)[17]從邊的角度觀察網(wǎng)絡(luò).在邊圖中,原始網(wǎng)絡(luò)的邊表現(xiàn)為邊圖中的節(jié)點(diǎn),邊圖中的邊表示原始網(wǎng)絡(luò)中邊之間的連接關(guān)系.Ahn 等人[18]在對(duì)重疊社區(qū)發(fā)現(xiàn)問(wèn)題的研究中就提出了邊社區(qū)的概念,他們通過(guò)邊而不是節(jié)點(diǎn)來(lái)劃分社區(qū),并指出邊的層次結(jié)構(gòu)與原始網(wǎng)絡(luò)中的節(jié)點(diǎn)層次結(jié)構(gòu)有所不同,從邊的角度觀察目標(biāo)網(wǎng)絡(luò)可以發(fā)現(xiàn)更多的特征.

一個(gè)好的網(wǎng)絡(luò)表示學(xué)習(xí)算法應(yīng)該能夠有效地保存網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)[9],為了達(dá)到這一效果,現(xiàn)有的基于隨機(jī)游走的網(wǎng)絡(luò)表示學(xué)習(xí)方法如DeepWalk 主要采用隨機(jī)游走獲取網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的上下文信息,繼而采用Skip-gram 模型學(xué)習(xí)其低維表示,從而使得具有相似拓?fù)鋵傩缘墓?jié)點(diǎn)具有相似的低維表示.過(guò)往的研究表明[19],一個(gè)社區(qū)的內(nèi)部連接應(yīng)該多于其外部連接,由于社區(qū)內(nèi)的連接密度應(yīng)該比較高,所以隨機(jī)游走時(shí)停留在自己社區(qū)內(nèi)節(jié)點(diǎn)上的概率要高于到外部的概率.為了進(jìn)一步了解邊圖,本文選擇DBLP 數(shù)據(jù)集[20],分別在原始網(wǎng)絡(luò)和對(duì)應(yīng)的邊圖上進(jìn)行隨機(jī)游走.在設(shè)置相同的總采樣次數(shù)的情況下,在圖1中畫出了其不同視角下的節(jié)點(diǎn)采樣頻率分布,橫坐標(biāo)表示原始網(wǎng)絡(luò)中的節(jié)點(diǎn)在不同視角下的采樣過(guò)程中的出現(xiàn)次數(shù),縱坐標(biāo)表示對(duì)應(yīng)出現(xiàn)次數(shù)的節(jié)點(diǎn)數(shù)量,可以看到在兩種視角下隨機(jī)游走得到的節(jié)點(diǎn)頻率分布是不同的,這是因?yàn)檫厛D可以為我們提供更多的連接信息,進(jìn)而可以為我們更好地揭示原始網(wǎng)絡(luò)中的層次結(jié)構(gòu).

圖1 對(duì)DBLP 數(shù)據(jù)集進(jìn)行隨機(jī)游走的節(jié)點(diǎn)采樣頻率分布

綜上所述,本文提出了一種融合節(jié)點(diǎn)視角和邊視角的耦合網(wǎng)絡(luò)表示學(xué)習(xí)算法DPBCNE (Dual Perspectives Based Coupled Network Embedding).分別從兩個(gè)視角下學(xué)習(xí)網(wǎng)絡(luò)拓?fù)湫畔?在這個(gè)耦合模型中,可以同時(shí)學(xué)習(xí)節(jié)點(diǎn)和邊的低維表示.通過(guò)使用節(jié)點(diǎn)-邊的耦合訓(xùn)練機(jī)制,可以將節(jié)點(diǎn)和邊映射到相同的低維空間中.與大多數(shù)現(xiàn)有的網(wǎng)絡(luò)表示學(xué)習(xí)方法間接獲取邊的表示方法不同,DPBCNE 可以直接學(xué)習(xí)得到節(jié)點(diǎn)和邊的表示,更具有解釋性.本文在4 個(gè)真實(shí)復(fù)雜網(wǎng)絡(luò)中驗(yàn)證了DPBCNE的性能,并通過(guò)節(jié)點(diǎn)分類,邊分類,鏈路預(yù)測(cè)和鏈路重構(gòu)4 個(gè)任務(wù)來(lái)比較DPBCNE 與當(dāng)下最先進(jìn)的網(wǎng)絡(luò)表示學(xué)習(xí)方法的效果.在鏈路預(yù)測(cè)任務(wù)中,與基準(zhǔn)方法相比,DPBCNE 取得了較好的結(jié)果,在合作者網(wǎng)絡(luò)中僅次于CN 算法.而在節(jié)點(diǎn)分類,邊分類和鏈路重構(gòu)任務(wù)中,DPBCNE 均優(yōu)于其他所有網(wǎng)絡(luò)表示學(xué)習(xí)基準(zhǔn)方法.

2 基于雙視角的耦合網(wǎng)絡(luò)表示學(xué)習(xí)算法

本文提出了一種新的基于雙視角的耦合網(wǎng)絡(luò)表示學(xué)習(xí)算法.其主要模型框架如圖2所示,模型可以分為兩個(gè)部分:第1 部分,獲取兩種視角下的網(wǎng)絡(luò)結(jié)構(gòu)信息,給定一個(gè)原始網(wǎng)絡(luò),首先構(gòu)建邊圖,在原始網(wǎng)絡(luò)和邊圖上分別進(jìn)行隨機(jī)游走,得到不同視角下的節(jié)點(diǎn)采樣序列.第2 部分,耦合更新原始網(wǎng)絡(luò)中的節(jié)點(diǎn)向量和邊向量,根據(jù)節(jié)點(diǎn)和邊之間的對(duì)應(yīng)關(guān)系以及不同視角下中心詞節(jié)點(diǎn)和其上下文節(jié)點(diǎn)的關(guān)系,將上述兩個(gè)視角結(jié)合起來(lái)進(jìn)行耦合更新,在更新過(guò)程中共享節(jié)點(diǎn)和邊的向量表示,最終獲得融合兩種視角下網(wǎng)絡(luò)結(jié)構(gòu)信息的節(jié)點(diǎn)向量和邊向量.

圖2 DPBCNE 模型框架示例

2.1 融合兩種視角的網(wǎng)絡(luò)表示學(xué)習(xí)

對(duì)于邊視角,本文首先根據(jù)原始網(wǎng)絡(luò)構(gòu)建邊圖(line graph) 來(lái)獲取邊視角下的結(jié)構(gòu)信息.給定的圖G(V,E),其中V表示節(jié)點(diǎn)集合,E表示邊集合.令圖G對(duì)應(yīng)的邊圖為Glink.在邊圖Glink中,圖G的邊集合E映射為邊圖的節(jié)點(diǎn)集合Vlink,節(jié)點(diǎn)集合則映射為邊圖的邊集合Elink.通過(guò)這種轉(zhuǎn)化構(gòu)建的邊圖記為Glink＜Vlink,Elink＞.

對(duì)于兩種視角下信息的獲取,本文采用DeepWalk的方法.通過(guò)對(duì)不同視角下的節(jié)點(diǎn)進(jìn)行隨機(jī)游走得到語(yǔ)料庫(kù),每一個(gè)隨機(jī)游走序列都可以看作是自然語(yǔ)言處理中的一個(gè)句子,然后用Skip-gram 算法最大化中心詞節(jié)點(diǎn)和其上下文的共現(xiàn)概率,從而得到不同視角下每個(gè)節(jié)點(diǎn)的表示向量,使得在同一視角下具有相似結(jié)構(gòu)的節(jié)點(diǎn)具有相似的向量.

因此,雙視角下網(wǎng)絡(luò)結(jié)構(gòu)信息獲取的目標(biāo)函數(shù)分別為:

其中,N為節(jié)點(diǎn)網(wǎng)絡(luò)中節(jié)點(diǎn)的個(gè)數(shù),S為隨機(jī)游走得到的節(jié)點(diǎn)序列集合,w表示窗口大小,v表示節(jié)點(diǎn)網(wǎng)絡(luò)中的節(jié)點(diǎn).Slink為邊圖中隨機(jī)游走得到的序列集合,Nlink為邊圖中的節(jié)點(diǎn)個(gè)數(shù)即原始網(wǎng)絡(luò)中邊的數(shù)量,vlink表示邊圖中的節(jié)點(diǎn)也即原始網(wǎng)絡(luò)中的邊.

該部分總的目標(biāo)函數(shù)為:

為了得到有效的網(wǎng)絡(luò)潛在特征,本文同時(shí)融合節(jié)點(diǎn)視角和邊視角進(jìn)行網(wǎng)絡(luò)表示學(xué)習(xí).介于節(jié)點(diǎn)與邊的一對(duì)多的關(guān)系,節(jié)點(diǎn)與其對(duì)應(yīng)邊的向量應(yīng)當(dāng)更相似,通過(guò)不斷耦合更新得到包含兩種視角下網(wǎng)絡(luò)拓?fù)湫畔⒌墓?jié)點(diǎn)向量和邊向量,將另一視角的網(wǎng)絡(luò)信息聚合到當(dāng)前視角的節(jié)點(diǎn)向量學(xué)習(xí)上.節(jié)點(diǎn)和邊視角耦合關(guān)聯(lián)模型目標(biāo)函數(shù)分別如下:

關(guān)聯(lián)部分總的目標(biāo)函數(shù)為:

其中,Cnode(vi)表示原始網(wǎng)絡(luò)中與節(jié)點(diǎn)vi直接相連的所有邊的集合.表示原始網(wǎng)絡(luò)中與邊直接相連的所有節(jié)點(diǎn)的集合.

根據(jù)上述內(nèi)容,DBPBCNE 算法的總目標(biāo)函數(shù)如下:

其中,α ∈[0,1]是用來(lái)平衡不同視角重要性的一個(gè)參數(shù),通過(guò)聯(lián)合優(yōu)化使得在節(jié)點(diǎn)學(xué)習(xí)的過(guò)程中耦合邊視角下的信息,以得到更有效的節(jié)點(diǎn)表示,同時(shí)也能學(xué)習(xí)得到耦合兩個(gè)視角下信息的邊向量.

2.2 耦合訓(xùn)練過(guò)程

本文使用隨機(jī)梯度上升(SGA)來(lái)訓(xùn)練模型,通過(guò)Softmax 公式來(lái)計(jì)算上述公式中的概率公式,例如式(1)中使用的P(vi+j|vi),可以通過(guò)下列方式來(lái)計(jì)算:

為降低時(shí)間復(fù)雜度,本文采用負(fù)采樣的方法對(duì)公式(8)進(jìn)行簡(jiǎn)化.除了更新窗口中的已知鄰居節(jié)點(diǎn)外,為給定節(jié)點(diǎn)生成k個(gè)負(fù)樣本.在計(jì)算公式(1)中的梯度時(shí),便不需要在每個(gè)梯度步驟中枚舉式(8)中的所有節(jié)點(diǎn),只需要計(jì)算根據(jù)詞分布構(gòu)建的負(fù)樣本和已知的正樣本.假設(shè)給定鄰居節(jié)點(diǎn)vi+j的負(fù)樣本集合為NEG(vi+j)={v1,v2,···,vk}則:

其中,表示待定參數(shù),為這部分要更新得到的節(jié)點(diǎn)向量,指示函數(shù)對(duì)求導(dǎo)可以得出:

從而可以得到原始網(wǎng)絡(luò)中的節(jié)點(diǎn)在節(jié)點(diǎn)視角下通過(guò)上下文節(jié)點(diǎn)進(jìn)行更新的公式如下:

對(duì)于節(jié)點(diǎn)-邊耦合關(guān)聯(lián)模型部分,本文通過(guò)用原始網(wǎng)絡(luò)中與邊相連的節(jié)點(diǎn)更新邊,用與節(jié)點(diǎn)相連的邊更新節(jié)點(diǎn),從而使得最終得到的原始網(wǎng)絡(luò)的節(jié)點(diǎn)和邊向量同時(shí)學(xué)習(xí)得到兩個(gè)視角下的網(wǎng)絡(luò)信息.

對(duì)于節(jié)點(diǎn)向量更新部分,給定一個(gè)原始網(wǎng)絡(luò)中的節(jié)點(diǎn)vi和對(duì)應(yīng)的一個(gè)相連邊,其負(fù)采樣得到的負(fù)樣本集合為同樣,對(duì)于邊向量更新部分,給定一個(gè)邊圖中的節(jié)點(diǎn)和他對(duì)應(yīng)的一個(gè)原始網(wǎng)絡(luò)中的節(jié)點(diǎn)vc,其通過(guò)負(fù)采樣得到的負(fù)樣本集合為NEG(vc)={v1,v2,···,vk}

原始網(wǎng)絡(luò)中節(jié)點(diǎn)在關(guān)聯(lián)部分的向量更新公式如下:

原始網(wǎng)絡(luò)中的邊在關(guān)聯(lián)部分的向量更新公式如下:

為了更加詳盡地介紹本文提出的DPBCNE 算法的具體流程,本文給出了算法偽代碼如算法1所示.

算法1.基于雙視角的耦合網(wǎng)絡(luò)表示學(xué)習(xí)算法輸入:圖,窗口大小,向量維度,隨機(jī)游走次數(shù),總迭代次數(shù),游走長(zhǎng)度,學(xué)習(xí)率,負(fù)采樣個(gè)數(shù).Xv∈RN×dXvlink∈RNlink×d輸出:節(jié)點(diǎn)表示向量矩陣,邊表示向量矩陣.G(V,E) wd γ ITERl η k X Xlink 1.初始化,G(V,E) Glink＜Vlink,Elink＞2.根據(jù) 構(gòu)建邊圖i=0 γ 3.For to:Ω=shu f fle(V)4.Ωlink=shu f fle(Vlink)5.6.For each do S=RandomWalk(G,vi,l)vi∈Ω 7.8.End for i ∈Ωlink 9.For each do vlink Slink=RandomWalk(Glink,vlink i,l)10.11.End for 12.End for iter=1,2,3,···,ITER 13.For do s∈S 14.For each do Xv X′v 15.根據(jù)式(13)和式(14)更新和Xv X′vlink 16.根據(jù)式(15)和式(16)更新和17.End for slink∈Slink 18.For each do Xvlink X′vlink 19.根據(jù)式(18)和式(17)更新和Xvlink X′v 20.根據(jù)式(19)和式(20)更新和21.End for 22.End for

算法可以分為第一步獲取雙視角下的網(wǎng)絡(luò)結(jié)構(gòu)信息部分和第二步耦合更新部分.第2-10 行分別對(duì)節(jié)點(diǎn)視角和邊視角下的網(wǎng)絡(luò)進(jìn)行隨機(jī)游走采樣獲取兩個(gè)視角下的網(wǎng)絡(luò)結(jié)構(gòu)信息,第14-22 行表示耦合更新過(guò)程,第14-17 行對(duì)于第1 步在原始網(wǎng)絡(luò)中采樣得到的所有節(jié)點(diǎn)序列中的每個(gè)節(jié)點(diǎn),分別用其對(duì)應(yīng)的上下文節(jié)點(diǎn)和對(duì)應(yīng)的邊進(jìn)行耦合更新,同樣,第18-21 行是對(duì)于邊圖中的采樣得到的所有節(jié)點(diǎn)序列中的節(jié)點(diǎn),也即原始網(wǎng)絡(luò)中的邊,分別用其上下文節(jié)點(diǎn)和對(duì)應(yīng)的原始網(wǎng)絡(luò)中的關(guān)聯(lián)節(jié)點(diǎn)進(jìn)行迭代耦合更新,最終得到融合兩個(gè)視角的原始網(wǎng)絡(luò)的節(jié)點(diǎn)向量和邊向量.

對(duì)于每一輪的迭代,第一部分的對(duì)原始網(wǎng)絡(luò)隨機(jī)游走的時(shí)間復(fù)雜度為Nrl,對(duì)邊圖的隨機(jī)游走時(shí)間復(fù)雜度為Nlinkrl,第二步耦合更新部分,對(duì)于節(jié)點(diǎn)的更新過(guò)程時(shí)間復(fù)雜度為Ngdk+Ndwrlk,其中g(shù)表示原始網(wǎng)絡(luò)中節(jié)點(diǎn)的平均度,對(duì)于邊的更新過(guò)程時(shí)間復(fù)雜度為2Nlinkdk+Nlinkdwrlk,其中,每個(gè)網(wǎng)絡(luò)的平均度通常都有一個(gè)最大值,其余的d,w,r,l,k均為可以設(shè)置的常數(shù).

3 實(shí)驗(yàn)分析

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

本文主要針對(duì)傳統(tǒng)的網(wǎng)絡(luò)表示學(xué)習(xí)研究只是通過(guò)節(jié)點(diǎn)視角這一單一的視角而沒(méi)有考慮邊視角的問(wèn)題,提出了一種新的基于雙視角的耦合網(wǎng)絡(luò)表示學(xué)習(xí)算法(DPBCNE).本文在4 個(gè)真實(shí)的復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)集中分別驗(yàn)證了該方法的性能,分別為Facebook[21],GRQC[22],HEPTH[22]和DBLP[20]數(shù)據(jù)集.其中Facebook為社交網(wǎng)絡(luò),總共有193 種節(jié)點(diǎn)標(biāo)簽;GRQC和HEPTH為合作者網(wǎng)絡(luò),數(shù)據(jù)集中沒(méi)有標(biāo)簽信息;DBLP為引文網(wǎng)絡(luò),總共有4 種節(jié)點(diǎn)標(biāo)簽.

3.2 基準(zhǔn)方法

在學(xué)習(xí)到節(jié)點(diǎn)的表示向量后,本文分別在4 個(gè)任務(wù)中與當(dāng)下主流的網(wǎng)絡(luò)表示學(xué)習(xí)算法進(jìn)行比較,其中,(1)-(3)項(xiàng)是基于隨機(jī)游走的網(wǎng)絡(luò)表示學(xué)習(xí)算法,(4)-(6)項(xiàng)是基于深度學(xué)習(xí)的網(wǎng)絡(luò)表示學(xué)習(xí)算法,此外,針對(duì)鏈路預(yù)測(cè)和鏈路重構(gòu)任務(wù),本文還選擇了一種效果良好的傳統(tǒng)鏈路預(yù)測(cè)方法Common Neighbor[23]作為對(duì)比方法,相關(guān)基準(zhǔn)算法簡(jiǎn)介如下:

(1)DeepWalk[8]:對(duì)節(jié)點(diǎn)采用隨機(jī)游走和Skip-gram模型以學(xué)習(xí)得到每個(gè)節(jié)點(diǎn)的表示向量.

(2)Node2Vec[9]:在DeepWalk的基礎(chǔ)上,引入了帶偏置的隨機(jī)游走,以選擇不同的搜索方式采樣節(jié)點(diǎn).其中,偏置參數(shù)p=0.25,q=0.5.

(3)Line[11]:通過(guò)分別定義損失函數(shù)同時(shí)保存網(wǎng)絡(luò)中節(jié)點(diǎn)的一階鄰近度和二階鄰近度.

(4)SDNE[12]:使用自動(dòng)編碼器通過(guò)聯(lián)合優(yōu)化目標(biāo)函數(shù)來(lái)保持節(jié)點(diǎn)一階和二階鄰近性.該方法采用高度非線性的函數(shù)對(duì)網(wǎng)絡(luò)的鄰接矩陣進(jìn)行編碼.

(5)DNGR[13]:利用Random Surfing 策略生成概率共現(xiàn)矩陣,再作為疊加去噪自動(dòng)編碼器的輸入進(jìn)行節(jié)點(diǎn)表示的學(xué)習(xí).

(6)GAE[14]:使用圖卷積網(wǎng)絡(luò)(GCN)編碼器和內(nèi)積解碼器.該方法利用GCN 學(xué)習(xí)節(jié)點(diǎn)間的高階關(guān)系.

(7)Common Neighbor (CN)[20]:以每個(gè)節(jié)點(diǎn)對(duì)之間的公共鄰居數(shù)作為節(jié)點(diǎn)之間的相似度評(píng)分,以進(jìn)行鏈路預(yù)測(cè).

在實(shí)驗(yàn)過(guò)程中,為保證公平比較,所有實(shí)驗(yàn)的參數(shù)均統(tǒng)一設(shè)置.對(duì)于網(wǎng)絡(luò)表示學(xué)習(xí)算法,其維度為128,負(fù)采樣樣本數(shù)為5,窗口大小為5,每個(gè)節(jié)點(diǎn)的隨機(jī)游走次數(shù)為10,步長(zhǎng)是40,邊圖的設(shè)置與原始網(wǎng)絡(luò)相同.學(xué)習(xí)率為0.01,最大迭代次數(shù)為200.

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

為驗(yàn)證DPBCNE的有效性,本文分別在鏈路預(yù)測(cè),鏈路重構(gòu),節(jié)點(diǎn)分類和邊分類4 個(gè)任務(wù)上進(jìn)行了對(duì)比實(shí)驗(yàn).

對(duì)于鏈路預(yù)測(cè)和鏈路重構(gòu),采用了AUC(Area Under Curve)和AP(Average Precision) 指標(biāo)來(lái)驗(yàn)證最終的效果.

AUC表示當(dāng)隨機(jī)選擇一個(gè)正樣本和一個(gè)負(fù)樣本時(shí),正樣本分?jǐn)?shù)高于負(fù)樣本的概率.例如,在鏈路預(yù)測(cè)任務(wù)中,隨機(jī)挑選測(cè)試集中的一條邊和一條不存在的邊并進(jìn)行比較,重復(fù)進(jìn)行n次,其中有n′次測(cè)試集中邊的分?jǐn)?shù)大于不存在的邊,有n′′次兩者獲得同樣的分?jǐn)?shù),那么最終得到的AUC計(jì)算公式如下:

AP表示平均準(zhǔn)確率,其計(jì)算公式如下:

其中,Precision表示每個(gè)類別的準(zhǔn)確率,M表示類別數(shù).

對(duì)于節(jié)點(diǎn)分類和邊分類實(shí)驗(yàn),采用了Micro-F1和Macro-F1 來(lái)作為評(píng)價(jià)指標(biāo).定義如下:

其中,F1(A)表示標(biāo)簽A的F1 得分,C表示所有的標(biāo)簽集.Pr表示總的準(zhǔn)確率,R表示總的召回率.

3.4 節(jié)點(diǎn)分類

節(jié)點(diǎn)分類是網(wǎng)絡(luò)表示學(xué)習(xí)中用以驗(yàn)證算法有效性的一個(gè)重要任務(wù).此任務(wù)在Facebook和DBLP 數(shù)據(jù)集上驗(yàn)證了DPBCNE 算法,首先移除數(shù)據(jù)集中沒(méi)有標(biāo)簽的節(jié)點(diǎn),將數(shù)據(jù)集按照30%的比例劃分訓(xùn)練集,剩余的節(jié)點(diǎn)作為測(cè)試集,將每個(gè)節(jié)點(diǎn)學(xué)習(xí)得到的表示向量作為邏輯回歸分類器的輸入進(jìn)行訓(xùn)練,通過(guò)計(jì)算Micro-F1和Macro-F1 來(lái)比較不同模型之間的效果,最終結(jié)果如表1所示.

表1 節(jié)點(diǎn)分類實(shí)驗(yàn)結(jié)果

從表1中可以看到,DPBCNE 模型地結(jié)果在兩個(gè)數(shù)據(jù)集上都優(yōu)于其他算法.在Facebook 數(shù)據(jù)集中,DPBCNE的Macro-F1 得分比其他算法中表現(xiàn)最好的DNGR 算法高出了0.99%,Micro-F1 得分則比DNGR算法高出了1.19%.這表明,通過(guò)融合兩種視角下的網(wǎng)絡(luò)表示學(xué)習(xí)能夠獲取比在單一視角下更豐富的節(jié)點(diǎn)采樣結(jié)果,也就是更豐富的網(wǎng)絡(luò)結(jié)構(gòu)信息,使得其在節(jié)點(diǎn)的類別劃分上比只關(guān)注單一視角的效果更好.而在DBLP數(shù)據(jù)集中,DPBCNE 算法的Macro-F1和Micro-F1 得分比DNGR 分別高了0.3%和0.55%.DPBCNE 模型在Facebook 數(shù)據(jù)集中的提升效果比在DBLP 數(shù)據(jù)集中更好,這是因?yàn)镕acebook 數(shù)據(jù)集中每個(gè)節(jié)點(diǎn)具有多個(gè)標(biāo)簽,而DBLP 數(shù)據(jù)集的每個(gè)節(jié)點(diǎn)有且只有一個(gè)標(biāo)簽,融合了邊視角的耦合網(wǎng)絡(luò)表示學(xué)習(xí),也更能區(qū)分出節(jié)點(diǎn)的重疊社區(qū).

3.5 邊分類

傳統(tǒng)的網(wǎng)絡(luò)表示學(xué)習(xí)算法通常使用兩個(gè)節(jié)點(diǎn)向量簡(jiǎn)單相連或相加來(lái)作為兩個(gè)節(jié)點(diǎn)之間的邊的表示[9].在本任務(wù)中,對(duì)于所有的網(wǎng)絡(luò)表示學(xué)習(xí)基準(zhǔn)算法,首先學(xué)習(xí)到每個(gè)節(jié)點(diǎn)的向量,再用(vi+vj)/2表示節(jié)點(diǎn)vi和節(jié)點(diǎn)vj之間的邊向量.而對(duì)于DPBCNE,通過(guò)耦合學(xué)習(xí),可以直接得到每條邊的表示,使其更具解釋性.本任務(wù)采用Facebook 數(shù)據(jù)集進(jìn)行驗(yàn)證,聚合每對(duì)節(jié)點(diǎn)的標(biāo)簽,作為其對(duì)應(yīng)邊的標(biāo)簽,按照1%～9%的比例對(duì)于網(wǎng)絡(luò)中的邊劃分出訓(xùn)練集作為邏輯回歸分類器的輸入.本任務(wù)采用了Micro-F1和Macro-F1 指標(biāo)來(lái)衡量最終的效果,具體結(jié)果如圖3所示.

圖3 邊分類實(shí)驗(yàn)結(jié)果

圖3中,DeepWalk (Link) 方法通過(guò)直接對(duì)邊圖的節(jié)點(diǎn)進(jìn)行隨機(jī)游走,不進(jìn)行耦合訓(xùn)練直接得到邊向量.DeepWalk (Link)在邊分類任務(wù)中也取得了比只在節(jié)點(diǎn)上進(jìn)行DeepWalk 學(xué)習(xí)節(jié)點(diǎn)表示再拼接成邊向量更好的結(jié)果,這說(shuō)明對(duì)于邊向量的計(jì)算,在邊圖上直接進(jìn)行學(xué)習(xí)得到是有效的.同時(shí),DPBCNE 始終高于其他所有方法包括效果良好的DeepWalk (Link),這說(shuō)明融合兩個(gè)視角的耦合訓(xùn)練學(xué)習(xí)得到的邊向量可以更好地保存網(wǎng)絡(luò)中的信息.

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

在這個(gè)任務(wù)中,首先將網(wǎng)絡(luò)中所有的邊劃分為測(cè)試集和訓(xùn)練集(比例為3:7),同時(shí)保持網(wǎng)絡(luò)的連通性,通過(guò)對(duì)訓(xùn)練集進(jìn)行網(wǎng)絡(luò)表示學(xué)習(xí),得到網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的表示,再計(jì)算|vi-vj|作為vi和vj之間的邊的表示.本文認(rèn)為兩個(gè)節(jié)點(diǎn)之間是否存在邊可以由節(jié)點(diǎn)對(duì)應(yīng)向量的絕對(duì)差來(lái)決定[4].將測(cè)試集中的邊看作為正例,對(duì)每一個(gè)正例等比例地構(gòu)建一條不存在的邊當(dāng)作負(fù)例,將其作為邏輯回歸分類器的輸入.本任務(wù)用AUC和AP作為本任務(wù)的評(píng)價(jià)指標(biāo),具體結(jié)果如表2所示.

由表2可以看到,DPBCNE的AUC指標(biāo)都在75%以上,這說(shuō)明DPBCNE 可以有效地預(yù)測(cè)網(wǎng)絡(luò)中的未知邊.在Facebook 數(shù)據(jù)集以及DBLP 數(shù)據(jù)集中,DPBCNE 取得了最好的效果,在GRQC 與HEPTH 數(shù)據(jù)集中DPBCNE的效果僅次于CN 算法,這說(shuō)明在合作者網(wǎng)絡(luò)中,節(jié)點(diǎn)之間的關(guān)系非常受共同鄰居的影響,復(fù)雜的學(xué)習(xí)反而沒(méi)有簡(jiǎn)單的指標(biāo)來(lái)得有效,但DPBCNE仍然高于其他所有基于隨機(jī)游走和深度學(xué)習(xí)的網(wǎng)絡(luò)表示學(xué)習(xí),由于融合了兩種視角,DPBCNE 能夠更好地預(yù)測(cè)網(wǎng)絡(luò)中未知的邊.

表2 鏈路預(yù)測(cè)實(shí)驗(yàn)結(jié)果

3.7 鏈路重構(gòu)

鏈路重構(gòu)任務(wù)類似于鏈路預(yù)測(cè),不同的是鏈路重構(gòu)所重構(gòu)的是現(xiàn)有的邊,而不是去預(yù)測(cè)未知的邊.給定一個(gè)網(wǎng)絡(luò),使用不同的鏈路重構(gòu)方法來(lái)重構(gòu)原始網(wǎng)絡(luò)的所有邊.在這個(gè)任務(wù)中,依舊使用兩個(gè)節(jié)點(diǎn)表示向量之間的絕對(duì)差作為每條邊的表示.同樣,采用AUC和AP作為評(píng)價(jià)指標(biāo).具體結(jié)果如表3所示.

表3 鏈路重構(gòu)實(shí)驗(yàn)結(jié)果

可以看到,DPBCNE 模型的AUC 結(jié)果都接近于1,這說(shuō)明該方法能夠很好地保存網(wǎng)絡(luò)的鄰接關(guān)系.在4 個(gè)數(shù)據(jù)集中,DPBCNE 始終效果是最好的,相比于傳統(tǒng)的鏈路預(yù)測(cè)方法CN,DPBCNE在AUC指標(biāo)上提升了1.03%～17.59%,在AP指標(biāo)上提升了0.87%～17.16%,相比于效果最好的基于隨機(jī)游走的算法LINE,DPBCNE在AUC指標(biāo)上提升了0.96%～19.05%,在AP指標(biāo)上提升了0.69%～24.1%,對(duì)比效果最好的基于深度學(xué)習(xí)的算法DNGR,DPBCNE在AUC指標(biāo)上提升了1.76%～5.3%,在AP指標(biāo)上提升了1.7%～7.73%.

4 結(jié)論與展望

本文討論了兩種不同視角在社區(qū)結(jié)構(gòu)和隨機(jī)游走方面的差異,通過(guò)經(jīng)驗(yàn)分析,本文得出邊視角和節(jié)點(diǎn)視角在隨機(jī)游走中出現(xiàn)的節(jié)點(diǎn)分布是不同的,這意味著通過(guò)不同的視角,可以獲得更多的網(wǎng)絡(luò)拓?fù)湫畔?因此,本文提出了一種新的網(wǎng)絡(luò)表示學(xué)習(xí)算法DPBCNE,可以同時(shí)考慮邊視角和節(jié)點(diǎn)視角,并通過(guò)耦合學(xué)習(xí),學(xué)習(xí)得到節(jié)點(diǎn)向量和邊向量.本文在節(jié)點(diǎn)分類,邊分類,鏈路預(yù)測(cè)和鏈路重構(gòu)4 個(gè)任務(wù)上驗(yàn)證了該方法的效果.DPBCNE在4 個(gè)任務(wù)中都展現(xiàn)了其良好的性能.本文只在靜態(tài)網(wǎng)絡(luò)中進(jìn)行了任務(wù)驗(yàn)證,而在現(xiàn)實(shí)生活中,網(wǎng)絡(luò)是不斷變化的,因此,未來(lái)的研究 將該算法考慮擴(kuò)展到動(dòng)態(tài)網(wǎng)絡(luò)以及加入深度學(xué)習(xí)框架以獲得更好的效果[24].同時(shí),鑒于DPBCNE 可以直接學(xué)習(xí)得到每條邊的表示,還將考慮將其擴(kuò)展到知識(shí)圖譜的應(yīng)用研究中[25].