儲(chǔ)曉愷 范鑫鑫 畢經(jīng)平

1(中國科學(xué)院大學(xué) 北京 100049) 2(中國科學(xué)院計(jì)算技術(shù)研究所 北京 100190)

圖(網(wǎng)絡(luò))是節(jié)點(diǎn)與邊的集合,其中節(jié)點(diǎn)代表了一類特定的事物,而邊則代表了節(jié)點(diǎn)與節(jié)點(diǎn)之間的關(guān)聯(lián).現(xiàn)實(shí)世界中的大量數(shù)據(jù)均可抽象為圖結(jié)構(gòu)數(shù)據(jù),比如社交網(wǎng)絡(luò)、生物網(wǎng)絡(luò)、學(xué)術(shù)網(wǎng)絡(luò)等.為了更好地支持這些基于圖結(jié)構(gòu)數(shù)據(jù)的應(yīng)用和分析,如何合理有效地表征網(wǎng)絡(luò)節(jié)點(diǎn)成為了關(guān)鍵所在.傳統(tǒng)的獨(dú)熱碼方式(one-hot),由于其空間復(fù)雜度會(huì)隨著節(jié)點(diǎn)規(guī)模的擴(kuò)增而快速增大,嚴(yán)重限制了大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)處理和分析的能力,并且獨(dú)熱碼無法表達(dá)節(jié)點(diǎn)間的相關(guān)性,間接影響了下游任務(wù)的效果.近年來,隨著深度神經(jīng)網(wǎng)絡(luò)和表征學(xué)習(xí)在圖像、自然語言處理等領(lǐng)域取得重大的成功,不少研究者開始關(guān)注如何對(duì)圖中的節(jié)點(diǎn)進(jìn)行低維表征,使得該表征可以保留網(wǎng)絡(luò)節(jié)點(diǎn)間的相關(guān)性,即網(wǎng)絡(luò)表征學(xué)習(xí)[1-3].現(xiàn)如今,網(wǎng)絡(luò)表征學(xué)習(xí)已經(jīng)在多種網(wǎng)絡(luò)處理和分析任務(wù)上證明其有效性,包括網(wǎng)絡(luò)節(jié)點(diǎn)分類[4-5]、鏈接預(yù)測(cè)[6-7]、社區(qū)發(fā)現(xiàn)[8-9]等.

迄今為止,學(xué)術(shù)界已經(jīng)提出許多網(wǎng)絡(luò)表征學(xué)習(xí)方法[1,10-11].大部分方法通常關(guān)注如何建模節(jié)點(diǎn)的近鄰信息.然而,少有方法重視節(jié)點(diǎn)的位置信息在表征中的作用.對(duì)于每個(gè)節(jié)點(diǎn),它相對(duì)于網(wǎng)絡(luò)中其他節(jié)點(diǎn)的最短距離標(biāo)定了該節(jié)點(diǎn)在網(wǎng)絡(luò)中的位置.相較于近鄰信息,節(jié)點(diǎn)的位置信息包含更寬的感受野和更全面的結(jié)構(gòu)上下文信息,而這類信息在一些與結(jié)構(gòu)分析相關(guān)的數(shù)據(jù)挖掘任務(wù)中是至關(guān)重要的.如圖1所示,如果只重視近鄰信息,那么用戶(節(jié)點(diǎn))A和B因其直接相連將會(huì)獲得相似的節(jié)點(diǎn)表征.然而,當(dāng)我們考慮兩者的位置信息,會(huì)發(fā)現(xiàn)他們?cè)诓煌木嚯x上有著完全不同的鄰居節(jié)點(diǎn),這意味兩者的表征應(yīng)具有較大的差異性.因此,如果表征模型可以感知到2個(gè)節(jié)點(diǎn)在各階鄰居上的差異,那么學(xué)到的表征將能夠支撐更多與網(wǎng)絡(luò)結(jié)構(gòu)或與節(jié)點(diǎn)距離相關(guān)的下游任務(wù).然而,現(xiàn)有的方法通常只關(guān)注節(jié)點(diǎn)的近鄰信息,雖然部分方法(如GraRep[12])通過計(jì)算節(jié)點(diǎn)間轉(zhuǎn)移概率的方式捕捉中心節(jié)點(diǎn)與高階節(jié)點(diǎn)間的相關(guān)性,但這種方式卻模糊了各階鄰居間的界限,使得模型仍然無法捕捉節(jié)點(diǎn)的位置信息.

Fig. 1 The importance of positional information in network embedding圖1 位置信息在節(jié)點(diǎn)表征中的作用

為了將節(jié)點(diǎn)的位置信息嵌入到節(jié)點(diǎn)表征中,本文提出了一種基于k階互信息估計(jì)[13-14]的位置感知網(wǎng)絡(luò)表征學(xué)習(xí)模型(position-aware network rep-resentation learning viak-step mutual information estimation, PMI),該模型通過最大化節(jié)點(diǎn)與其各階鄰居之間的互信息,從而捕捉到節(jié)點(diǎn)的全局位置信息.其直觀解釋在于:處于不同網(wǎng)絡(luò)位置的節(jié)點(diǎn),在不同階結(jié)構(gòu)上通常擁有不同的鄰居,因此在模型訓(xùn)練的過程中,激勵(lì)每個(gè)節(jié)點(diǎn)去分別記住并區(qū)別自身在各階的鄰居節(jié)點(diǎn).通過這種方式,模型可以從節(jié)點(diǎn)的各階鄰居獲取不同的上下文信息，從而學(xué)得更具區(qū)分性的節(jié)點(diǎn)表征.本文的主要貢獻(xiàn)涵蓋3個(gè)方面：

1) 提出了一種基于K階互信息最大化的表征學(xué)習(xí)模型PMI,該模型不僅可以保留節(jié)點(diǎn)的局部結(jié)構(gòu)信息,還可以捕捉節(jié)點(diǎn)的全局位置信息;

2) 為了捕捉節(jié)點(diǎn)的位置信息,PMI最大化每個(gè)節(jié)點(diǎn)與其K階鄰居間的互信息,從而讓每個(gè)節(jié)點(diǎn)能夠識(shí)別并記住其各階鄰居;

3) 在4種不同類型的真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行多種代表性網(wǎng)絡(luò)分析實(shí)驗(yàn),包括鏈接預(yù)測(cè)、多標(biāo)簽分類、網(wǎng)絡(luò)重構(gòu)等.實(shí)驗(yàn)結(jié)果表明PMI可以有效地獲取高質(zhì)量的節(jié)點(diǎn)表征.此外,在另一項(xiàng)鄰居匹配任務(wù)上的實(shí)驗(yàn)結(jié)果表明：相較于現(xiàn)有的工作,本文提出的PMI模型可以有效地捕捉節(jié)點(diǎn)的位置信息.

1 相關(guān)工作

1.1 網(wǎng)絡(luò)表征學(xué)習(xí)

隨著網(wǎng)絡(luò)數(shù)據(jù)的大規(guī)模增加,近年來大量研究者對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)表征開展了研究[1,6,10].本文主要針對(duì)同質(zhì)網(wǎng)絡(luò)下的網(wǎng)絡(luò)表征學(xué)習(xí)問題,即節(jié)點(diǎn)與邊的類型有且僅有一種.大部分研究類比自然語言和網(wǎng)絡(luò)節(jié)點(diǎn)在統(tǒng)計(jì)特征上的相似性[1],提出基于語言模型的網(wǎng)絡(luò)表征學(xué)習(xí).文獻(xiàn)[1]提出了DeepWalk模型,首先通過隨機(jī)游走(random walks)獲取節(jié)點(diǎn)序列,再利用語言模型SkipGram[15]獲取節(jié)點(diǎn)的表征.在DeepWalk的基礎(chǔ)上,文獻(xiàn)[10]修改了節(jié)點(diǎn)的采樣策略,提出了一種帶偏好的隨機(jī)游走策略(biased random walks),該策略權(quán)衡了廣度優(yōu)先搜索(breadth first search, BFS)和深度優(yōu)先搜索(depth first search, DFS).除此之外,一些文獻(xiàn)也通過直接建模鄰居間的相關(guān)性來學(xué)習(xí)節(jié)點(diǎn)表征.基于近鄰相似的假設(shè),文獻(xiàn)[13]著重捕捉一階或二階鄰居間的關(guān)系,并采用負(fù)采樣策略對(duì)大型網(wǎng)絡(luò)進(jìn)行訓(xùn)練.文獻(xiàn)[12]通過計(jì)算節(jié)點(diǎn)的K階轉(zhuǎn)移矩陣來建模高階節(jié)點(diǎn)間的相關(guān)性,并通過矩陣分解獲取節(jié)點(diǎn)表征.一些工作[11]也利用自動(dòng)編碼機(jī)來學(xué)習(xí)節(jié)點(diǎn)表征,通過最小化自動(dòng)編碼機(jī)的輸入和輸出來學(xué)習(xí)節(jié)點(diǎn)的表征.文獻(xiàn)[11]證明這種方式等同于學(xué)習(xí)節(jié)點(diǎn)間的二階關(guān)系.不同以上基于近鄰假設(shè)的方法,文獻(xiàn)[16]認(rèn)為空間結(jié)構(gòu)相似的節(jié)點(diǎn)在表征空間中也應(yīng)當(dāng)相近,基于結(jié)構(gòu)相似性假設(shè),作者建立一個(gè)多層次的帶權(quán)重網(wǎng)絡(luò)來衡量節(jié)點(diǎn)間的結(jié)構(gòu)相似性.然而,上述工作均無法捕捉節(jié)點(diǎn)的位置信息.針對(duì)該問題,本文提出一種基于K階互信息估計(jì)的網(wǎng)絡(luò)表征學(xué)習(xí)方法,最大化節(jié)點(diǎn)與其各階鄰居間的互信息,讓每個(gè)節(jié)點(diǎn)能夠記住并識(shí)別來自不同階的鄰居,從而將位置信息融入節(jié)點(diǎn)表征中.

除了上述針對(duì)同質(zhì)網(wǎng)絡(luò)的表征學(xué)習(xí)方法,一些研究者提出在其他不同類型網(wǎng)絡(luò)場(chǎng)景下的表征學(xué)習(xí)方法,包括異構(gòu)信息網(wǎng)絡(luò)[17-18]、多層網(wǎng)絡(luò)[19-20]、符號(hào)網(wǎng)絡(luò)[21-23]、屬性網(wǎng)絡(luò)[24-25]等.此外,一些文獻(xiàn)著手于為不同的應(yīng)用設(shè)計(jì)對(duì)應(yīng)的表征學(xué)習(xí)方法,如社區(qū)發(fā)現(xiàn)[26-27]、結(jié)構(gòu)識(shí)別[28-29]等.近幾年,圖神經(jīng)網(wǎng)絡(luò)(graph neural networks, GNNs)[30-32]成為了屬性網(wǎng)絡(luò)表征學(xué)習(xí)的熱門,其在半監(jiān)督學(xué)習(xí)下的圖分類、節(jié)點(diǎn)分類等問題上超越了傳統(tǒng)方法,取得了優(yōu)異的效果.

1.2 互信息估計(jì)

(1)

盡管式(1)在形式上十分簡(jiǎn)潔,但它的精確計(jì)算僅適用于離散變量或是已明確先驗(yàn)分布的連續(xù)變量,因此,它的適用場(chǎng)景較為有限.為解決該問題,文獻(xiàn)[33]提出一種基于神經(jīng)網(wǎng)絡(luò)的互信息估計(jì)模型MINE,利用DV(Donsker-Varadhan)表征推導(dǎo)式(1)的下界:

(2)

其中,DM(·,·)是參數(shù)為M的雙線性函數(shù),該方法在學(xué)習(xí)更好的生成模型方面表現(xiàn)出了很強(qiáng)的一致性.

受到MINE的啟發(fā),文獻(xiàn)[14]首次將互信息的神經(jīng)估計(jì)應(yīng)用到無監(jiān)督圖像表征學(xué)習(xí)中,并提出DIM模型.作者認(rèn)為在很多場(chǎng)景下,并不需要關(guān)心具體的互信息值,而更關(guān)心變量間互信息的相對(duì)大小.因此,DIM模型用J-S散度(Jensen-Shannon divergence)替代K-L散度,并采用一種對(duì)抗訓(xùn)練的方式最大化正樣本間的互信息:

(3)

其中，sp(x)=log(1+ex)為softplus激活函數(shù),變量z為采樣出的負(fù)樣本.通過式(3),DIM最終最大化每張圖片的全局特征與其每個(gè)像素表征間的互信息,并取得了優(yōu)異的效果.

受到MINE的啟發(fā),文獻(xiàn)[34]提出模型DGI并首次將互信息估計(jì)應(yīng)用到屬性網(wǎng)絡(luò)節(jié)點(diǎn)表征學(xué)習(xí)中,最大化網(wǎng)絡(luò)全局表征與節(jié)點(diǎn)局部表征間的互信息.而文獻(xiàn)[35]提出了模型GMI,該模型最大化中心節(jié)點(diǎn)表征與其一階鄰居屬性間的互信息.本文所提出的PMI模型與上述DGI和GMI模型存在較大的不同,如圖2所示:1)本文針對(duì)的是網(wǎng)絡(luò)結(jié)構(gòu)表征,并不包含屬性信息;2)本文方法通過最大化中心節(jié)點(diǎn)與其各階鄰居間的互信息,從而獲取每個(gè)節(jié)點(diǎn)的位置信息.

Fig. 2 Difference from current mutual information-based embedding models圖2 本文工作與現(xiàn)有基于互信息的圖表征模型的不同

2 問題定義

首先給出本文方法涉及到的相關(guān)定義,表1列出了本文的主要符號(hào)以及對(duì)應(yīng)的含義.

Table 1 Primary Notations and Explanations表1 主要符號(hào)和對(duì)應(yīng)含義

定義1.同質(zhì)網(wǎng)絡(luò).給定一個(gè)無向圖G=(V,E;A),其中V={v1,v2,…,vn}代表節(jié)點(diǎn)集，E代表邊集合,矩陣A是圖G的鄰接矩陣,其中Ai,j=1當(dāng)且僅當(dāng)節(jié)點(diǎn)v1和v2間存在一條邊,否則Ai,j=0.

本文方法通過最大化每個(gè)節(jié)點(diǎn)與其各階鄰居間的互信息學(xué)習(xí)節(jié)點(diǎn)的表征,其中第k階鄰居和網(wǎng)絡(luò)表征學(xué)習(xí)的定義分別如下:

定義3.網(wǎng)絡(luò)表征學(xué)習(xí).給定圖G,網(wǎng)絡(luò)表征學(xué)習(xí)旨在學(xué)習(xí)圖G中節(jié)點(diǎn)的表征矩陣X∈n×d,其中d是表征維度,其中矩陣的每一行向量Xi,:表示節(jié)點(diǎn)vi的表征.在后續(xù)的論述中為了簡(jiǎn)明起見,也用xi代表vi的表征.

現(xiàn)有的網(wǎng)絡(luò)表征學(xué)習(xí)模型無法學(xué)習(xí)到節(jié)點(diǎn)的位置信息.為了解決該問題,我們認(rèn)為關(guān)鍵在于訓(xùn)練的過程中,適當(dāng)?shù)丶?lì)節(jié)點(diǎn)記住并區(qū)別其在各階上的鄰居節(jié)點(diǎn).為此,我們嘗試將互信息神經(jīng)估計(jì)融入網(wǎng)絡(luò)表征學(xué)習(xí)中,為各種下游分析任務(wù)生成位置感知的節(jié)點(diǎn)表征.

3 基于互信息估計(jì)的位置感知表征學(xué)習(xí)方法

3.1 總體框架

如圖3所示,本文提出的PMI模型主要分為2個(gè)模塊:1)K階互信息估計(jì)模塊用于捕捉每個(gè)節(jié)點(diǎn)的位置信息;2)網(wǎng)絡(luò)重構(gòu)模塊用于學(xué)習(xí)網(wǎng)絡(luò)的基本結(jié)構(gòu)信息.因此,最終優(yōu)化函數(shù)也分為2部分:

Fig. 3 An illustration of the proposed model PMI圖3 本文提出的PMI模型

(4)

其中JMI代表K階互信息估計(jì)模塊的優(yōu)化函數(shù),而JAE則對(duì)應(yīng)了網(wǎng)絡(luò)重構(gòu)模塊的優(yōu)化目標(biāo),超參數(shù)α和β用來權(quán)衡兩者.接下來,我們逐一介紹面向K階鄰居的互信息最大化和基于自動(dòng)編碼機(jī)的結(jié)構(gòu)學(xué)習(xí)模塊,最后對(duì)本文方法的復(fù)雜度進(jìn)行分析并給出優(yōu)化方案.

3.2 面向K階鄰居的互信息估計(jì)

(5)

接下來,介紹最大化中心節(jié)點(diǎn)vi與第k階鄰居節(jié)點(diǎn)集合的互信息.在式(3)的基礎(chǔ)上,我們定義互信息估算公式為

(6)

因此,面向第k階鄰居的互信息最大化的優(yōu)化目標(biāo)定義為

(7)

其中X是待學(xué)習(xí)的表征矩陣.最終,總優(yōu)化目標(biāo)定義為與階數(shù)k相關(guān)的加權(quán)和:

(8)

考慮到位于更高階的鄰居節(jié)點(diǎn)對(duì)于中心節(jié)點(diǎn)的影響力往往越弱,在式(8)中,我們添加了一個(gè)與階數(shù)相關(guān)的衰減函數(shù)Φ(k)來控制不同階的鄰居對(duì)于中心節(jié)點(diǎn)影響力的強(qiáng)弱,該衰減函數(shù)滿足Φ(k+1)≤Φ(k),并且當(dāng)k>0時(shí)有Φ(k)>0.

3.3 基于自動(dòng)編碼機(jī)的結(jié)構(gòu)學(xué)習(xí)

面向K階鄰居的互信息最大化模塊盡管可以讓節(jié)點(diǎn)表征獲取節(jié)點(diǎn)對(duì)應(yīng)的位置信息,但無法學(xué)習(xí)到網(wǎng)絡(luò)中最基本的結(jié)構(gòu)信息,即邊信息,而邊信息在多種下游任務(wù)中是極其重要和基礎(chǔ)的,丟失該信息將會(huì)極大地影響下游任務(wù)的效果.因此,PMI模型需要另一個(gè)模塊來學(xué)習(xí)網(wǎng)絡(luò)中的基本結(jié)構(gòu)信息.盡管當(dāng)前對(duì)于結(jié)構(gòu)信息的表征學(xué)習(xí)模型[2,11-12]層出不窮,但我們發(fā)現(xiàn)自動(dòng)編碼機(jī)模型是最契合本文方法的一類模型,因?yàn)樗梢灾苯咏＝忛g的關(guān)系而不對(duì)互信息估計(jì)產(chǎn)生影響.同時(shí),這也有助于我們?cè)O(shè)計(jì)一種端到端的學(xué)習(xí)模式.

盡管已有大量工作基于不同假設(shè)設(shè)計(jì)不同的自編碼機(jī)模型[11,36-37],但PMI模型僅需要一個(gè)能夠捕捉基本結(jié)構(gòu)信息的模塊,因此我們采用一種簡(jiǎn)單的自編碼機(jī)模型,通過直接重建網(wǎng)絡(luò)中的邊來學(xué)習(xí)網(wǎng)絡(luò)結(jié)構(gòu).

自編碼機(jī)的編碼器部分采用2層的DNN(deep neural network),其中第i層的DNN定義為

X(i)=σ(W(i)X(i-1)+b(i)),

(9)

其中，X(i)是第i層DNN的輸入特征,且有X(0)=A為網(wǎng)絡(luò)的鄰接矩陣,W(i)和b(i)為待學(xué)習(xí)的參數(shù),σ(·)為激活函數(shù),這里我們使用修正線性單元ReLu(·)作為激活函數(shù).第2層DNN的輸出就是節(jié)點(diǎn)的表征X=X(2).

對(duì)于解碼器模塊,我們采用一個(gè)簡(jiǎn)單的點(diǎn)乘形式重構(gòu)整個(gè)網(wǎng)絡(luò):

Z=σ(XTX),

(10)

其中σ(·)=1/(1+e-x)為sigmoid函數(shù).這種簡(jiǎn)單的點(diǎn)乘形式不僅有效減少本模型的參數(shù)量，而且可以避免繁重的編碼機(jī)預(yù)訓(xùn)練過程[11,38].

最后,自編碼機(jī)的優(yōu)化目標(biāo)為重構(gòu)出的網(wǎng)絡(luò)與真實(shí)網(wǎng)絡(luò)的距離：

(11)

3.4 復(fù)雜度分析

模型的復(fù)雜度主要分為2個(gè)部分：K階互信息估計(jì)模塊和自動(dòng)編碼機(jī)模塊.對(duì)于前者,每一階的互信息估算的復(fù)雜度為O(d2|V|),對(duì)于自動(dòng)編碼機(jī)模塊,DNN層的計(jì)算復(fù)雜度為O(d(i-1)d(i)|V|),其中d(i-1)和d(i)代表第i層DNN的輸入和輸出維度.因此,整個(gè)模型的復(fù)雜度為

4 實(shí)驗(yàn)評(píng)估

為了評(píng)估本文提出的PMI模型的有效性,我們將模型訓(xùn)練得到的節(jié)點(diǎn)表征作為下游網(wǎng)絡(luò)分析任務(wù)的輸入,測(cè)試其在多標(biāo)簽分類、鏈接預(yù)測(cè)和網(wǎng)絡(luò)重構(gòu)任務(wù)上的效果.此外,為了驗(yàn)證學(xué)到的表征是否能夠捕捉其全局位置信息,我們?cè)?.5節(jié)進(jìn)行對(duì)于表征中位置信息的進(jìn)一步分析,測(cè)試模型在鄰居對(duì)齊任務(wù)上的效果.最后,我們對(duì)PMI模型中的參數(shù)敏感度進(jìn)行實(shí)驗(yàn)分析.

4.1 實(shí)驗(yàn)設(shè)置

我們使用的真實(shí)網(wǎng)絡(luò)數(shù)據(jù)來自多個(gè)不同領(lǐng)域,統(tǒng)計(jì)數(shù)據(jù)如表2所示,各個(gè)數(shù)據(jù)集的具體描述如下:

1) PPI[10].該網(wǎng)絡(luò)是蛋白質(zhì)相互作用網(wǎng)絡(luò)(protein-protein interactions)的子圖,數(shù)據(jù)來源于文獻(xiàn)[3].

2) IMDB[39].該網(wǎng)絡(luò)數(shù)據(jù)抽取自MovieLens(1)https://grouplens.org/datasets/movielens/,其中每個(gè)節(jié)點(diǎn)代表一部電影,節(jié)點(diǎn)間的連邊表示2部電影出自同一位導(dǎo)演.

3) WordNet(2)http://www.mattmahoney.net/dc/textdata/.該網(wǎng)絡(luò)為維基百科中的單詞共現(xiàn)網(wǎng)絡(luò),每個(gè)節(jié)點(diǎn)表示一個(gè)單詞,而單詞間的連接表示2個(gè)單詞在同一個(gè)文檔中共同出現(xiàn).

4) VoteNet[1].該數(shù)據(jù)來自于斯坦福的公開數(shù)據(jù)集who-votes-on-whom,是一個(gè)投票網(wǎng)絡(luò).

Table 2 Network Statistics表2 各數(shù)據(jù)集的網(wǎng)絡(luò)統(tǒng)計(jì)數(shù)據(jù)

為了驗(yàn)證PMI模型的效果,我們與當(dāng)前7種具有代表性的網(wǎng)絡(luò)表征學(xué)習(xí)方法進(jìn)行比較,包括基于隨機(jī)游走的方法(DeepWalk[1]和Node2Vec[10])、基于近鄰估計(jì)的方法(LINE[2]和GraRep[12])、基于自動(dòng)編碼機(jī)的方法(SDNE[11])和基于互信息的方法(DGI[34]和GMI[35]).為了公平比較,包括本文方法在內(nèi)的所有方法的節(jié)點(diǎn)表征維度d均設(shè)置為128.對(duì)于模型Node2Vec,我們采用grid search方法在參數(shù)空間p,q∈{0.25,0.5,1,2,4}中搜索其最佳參數(shù);對(duì)于LINE,我們分別優(yōu)化1階近鄰和2階近鄰,并將兩者學(xué)到的表征進(jìn)行拼接獲取最終表征;對(duì)于模型GraRep,我們同樣采用grid search在參數(shù)空間K∈{1,2,3,4,5}中搜索其最佳超參.由于本文PMI模型僅考慮網(wǎng)絡(luò)結(jié)構(gòu)信息,我們將歸一化后的鄰接矩陣作為模型SDNE,DGI,GMI和PMI的輸入.此外,遵循文獻(xiàn)[11]中的策略,我們使用深度置信網(wǎng)絡(luò)(deep belief network, DBN)[38]對(duì)SDNE模型進(jìn)行參數(shù)初始化.本文方法的其他超參設(shè)置為：最大階數(shù)K=3,負(fù)采樣數(shù)目nz=5,自動(dòng)編碼機(jī)的各層輸出維度分別為256和128,超參數(shù)α=β=1,并使用Φ(k)=k-1作為衰減函數(shù).

4.2 多標(biāo)簽分類

我們首先測(cè)試各模型在多標(biāo)簽分類任務(wù)上的效果.采用multi-class SVM[40]作為模型分類器,并將節(jié)點(diǎn)表征作為SVM的輸入特征來訓(xùn)練分類器.選擇20%的標(biāo)簽節(jié)點(diǎn)作為訓(xùn)練樣本,剩下的80%用作測(cè)試和效果評(píng)估.對(duì)于每個(gè)模型,重復(fù)上述實(shí)驗(yàn)5次并計(jì)算每個(gè)模型的Micro-F1,實(shí)驗(yàn)結(jié)果如表3所示.結(jié)果表明,本文方法在所有數(shù)據(jù)集上均取得最好的效果,在各數(shù)據(jù)集上分別有1.63%，1.36%和1.59%的提升.進(jìn)一步分析可以發(fā)現(xiàn):基于隨機(jī)游走的方法(DeepWalk和Node2Vec)在各數(shù)據(jù)集上的效果優(yōu)于其他對(duì)比方法;而LINE和SDNE的表現(xiàn)也較為穩(wěn)定,但由于這2種方法過于強(qiáng)調(diào)近鄰相似,導(dǎo)致整體效果不佳;相比之下,GraRep的表現(xiàn)在各個(gè)數(shù)據(jù)集上非常不穩(wěn)定,比如其在PPI上的分類效果較差,這主要因?yàn)镚raRep引入的高階信息中包含了大量的噪音,這些信息影響了節(jié)點(diǎn)分類的效果，也影響了節(jié)點(diǎn)表征的區(qū)分性;另外2種基于互信息的方法DGI和PMI在多標(biāo)簽分類任務(wù)上的表現(xiàn)也欠佳,這2種方法的表征依賴于高質(zhì)量的節(jié)點(diǎn)屬性信息,當(dāng)輸入的網(wǎng)絡(luò)結(jié)構(gòu)信息并不包含具有鮮明特性的局部結(jié)構(gòu)信號(hào)時(shí),它們無法學(xué)到具有區(qū)分性的節(jié)點(diǎn)表征.相比之下,由于本文方法采用了一種K階互信息最大化策略,其目的是讓每個(gè)節(jié)點(diǎn)記住它的各階鄰居,PMI模型可以有效地從上下文信息中學(xué)到結(jié)構(gòu)相似性,從而最終在多標(biāo)簽分類任務(wù)上取得較好的效果.

Table 3 Results of Multi-label Classification表3 多標(biāo)簽分類結(jié)果 %

4.3 網(wǎng)絡(luò)重構(gòu)

網(wǎng)絡(luò)重構(gòu)任務(wù)測(cè)試學(xué)到的節(jié)點(diǎn)表征是否可以保留原網(wǎng)絡(luò)的結(jié)構(gòu)信息.在本文中,實(shí)驗(yàn)設(shè)置與文獻(xiàn)[11]類似:每個(gè)模型依據(jù)學(xué)到的表征相似性推理出k條可能在網(wǎng)絡(luò)中存在的邊,計(jì)算精確率precision@k,該指標(biāo)表示在k次預(yù)測(cè)的邊中有多少在原網(wǎng)絡(luò)中是真實(shí)存在的.我們以IMDB和VoteNet數(shù)據(jù)集為例,比較每個(gè)模型的推理精確率.

如圖4所示,PMI模型在2個(gè)數(shù)據(jù)集上都展現(xiàn)出更加穩(wěn)定的提升.盡管SDNE和LINE在k較小時(shí)表現(xiàn)較優(yōu),但當(dāng)更多的邊需要被推測(cè)時(shí)(即更大的k),2種方法的精確率都出現(xiàn)大幅度下降.另一個(gè)比較有趣的發(fā)現(xiàn)是,2種基于互信息的方法(DGI和GMI)也取得了較為不錯(cuò)的效果,這說明通過加強(qiáng)節(jié)點(diǎn)與局部鄰居的互信息或增強(qiáng)節(jié)點(diǎn)與全局結(jié)構(gòu)的互信息都有助于表征獲取豐富的網(wǎng)絡(luò)結(jié)構(gòu)信息.另一方面,PMI模型由于采用一種K階互信息最大化的策略,使得每個(gè)節(jié)點(diǎn)的表征都攜帶其全局位置信息,可以在網(wǎng)絡(luò)重構(gòu)任務(wù)上取得最好的效果.

Fig. 4 Performance on network reconstruction圖4 網(wǎng)絡(luò)重構(gòu)結(jié)果

4.4 鏈接預(yù)測(cè)

鏈接預(yù)測(cè)是網(wǎng)絡(luò)分析中的重要任務(wù)，其目的在于預(yù)測(cè)網(wǎng)絡(luò)中缺失的或潛在的連接關(guān)系，我們通過探究表征是否可以捕捉一些潛在的關(guān)聯(lián)信息來進(jìn)一步比較表征質(zhì)量.對(duì)每個(gè)網(wǎng)絡(luò)數(shù)據(jù)集,我們首先隨機(jī)刪除20%的邊作為測(cè)試集,剩下的部分則作為每個(gè)模型的輸入用作表征學(xué)習(xí).對(duì)測(cè)試集中的每條邊,我們采樣一條網(wǎng)絡(luò)中不存在的邊作為負(fù)樣本,將鏈接預(yù)測(cè)任務(wù)轉(zhuǎn)為二分類任務(wù)進(jìn)行評(píng)估,并使用AUC(area under curve)作為評(píng)價(jià)指標(biāo).實(shí)驗(yàn)結(jié)果如表4所示.

從實(shí)驗(yàn)結(jié)果中可以發(fā)現(xiàn),本文提出的PMI模型在3個(gè)數(shù)據(jù)集上均取得最好的效果,說明采用的K階互信息最大方法可以有效地捕捉網(wǎng)絡(luò)結(jié)構(gòu)信息.此外,其他2種基于互信息的方法(DGI和GMI)均可取得非常不錯(cuò)的效果,結(jié)合4.3節(jié)在網(wǎng)絡(luò)重構(gòu)任務(wù)上的效果,我們可以得到這樣一個(gè)結(jié)論：最大化節(jié)點(diǎn)與其近鄰或全局結(jié)構(gòu)的互信息有助于模型捕捉網(wǎng)絡(luò)更深層的結(jié)構(gòu)信息.其他幾種方法,如DeepWalk,Node2Vec,GraRep也在其中幾個(gè)數(shù)據(jù)上取得不錯(cuò)的效果,但整體效果并不穩(wěn)定.我們認(rèn)為出現(xiàn)該問題的原因在于表征無法獲得節(jié)點(diǎn)的全局位置信息.直觀上,在圖上距離越近的節(jié)點(diǎn)越容易產(chǎn)生關(guān)聯(lián),因此節(jié)點(diǎn)的位置信息對(duì)于鏈接預(yù)測(cè)任務(wù)而言是非常重要的.而相反,本文提出的PMI方法通過最大化中心節(jié)點(diǎn)與各階鄰居的互信息,讓中心節(jié)點(diǎn)能夠記住其任意階的鄰居,從而使得學(xué)到的表征可以保留全局位置信息,捕捉更多網(wǎng)絡(luò)結(jié)構(gòu)中的隱藏信息,最終在鏈接預(yù)測(cè)任務(wù)上取得令人滿意的效果.

4.5 案例研究

為了研究本文提出的PMI模型是否可以使得表征學(xué)習(xí)到節(jié)點(diǎn)的全局位置信息,本節(jié)進(jìn)行一個(gè)新穎的實(shí)驗(yàn):鄰居對(duì)齊.該實(shí)驗(yàn)的目標(biāo)是讓每個(gè)節(jié)點(diǎn)識(shí)別來自同一階的節(jié)點(diǎn)并區(qū)分來自不同階的節(jié)點(diǎn).通過該實(shí)驗(yàn),我們可以從側(cè)面知曉學(xué)到的表征是否包含了位置信息.

1) 本文方法在2個(gè)數(shù)據(jù)集上均取得最優(yōu)的效果.這說明通過本文方法學(xué)到的節(jié)點(diǎn)表征可以有效記住各階的鄰居信息,從而區(qū)分不同階的節(jié)點(diǎn).

2) 大部分方法都可以有效地識(shí)別1階鄰居,這主要是由于近鄰假設(shè)導(dǎo)致1階鄰居節(jié)點(diǎn)通常與中心節(jié)點(diǎn)在向量空間中更近,因此較為容易區(qū)分.但對(duì)于其他階的鄰居節(jié)點(diǎn),我們發(fā)現(xiàn)大部分方法(尤其是基于隨機(jī)游走和自編碼機(jī)方法)的效果存在明顯下降,比如SDNE在PPI上區(qū)分3階鄰居時(shí)僅有52%左右的準(zhǔn)確率,而DeepWalk在2個(gè)數(shù)據(jù)集上識(shí)別3階鄰居時(shí)均只有55%左右的準(zhǔn)確率.這些實(shí)驗(yàn)結(jié)果均說明當(dāng)前方法通常會(huì)混淆來自不同階的鄰居節(jié)點(diǎn).

Fig. 5 Results of neighbor alignment圖5 鄰居對(duì)齊結(jié)果

3) GraRep在區(qū)分3階鄰居的效果上與本文方法相當(dāng),這是因?yàn)镚raRep建模節(jié)點(diǎn)對(duì)間的轉(zhuǎn)移概率,而較高階的轉(zhuǎn)移概率會(huì)遠(yuǎn)小于低階的轉(zhuǎn)移概率,因此GraRep可以比較有效地識(shí)別3階鄰居節(jié)點(diǎn).盡管如此,在2個(gè)數(shù)據(jù)集上GraRep均無法有效地區(qū)分近鄰節(jié)點(diǎn)(如1階鄰居),這說明GraRep易混淆1階鄰居和其他階的鄰居節(jié)點(diǎn),無法有效地捕捉到節(jié)點(diǎn)位置信息.在4.2和4.4節(jié)的實(shí)驗(yàn)中,相關(guān)任務(wù)均要求模型能夠有效地捕捉近鄰信息,本節(jié)的實(shí)驗(yàn)結(jié)果也解釋了為什么GraRep在之前的實(shí)驗(yàn)中效果并不理想.

小結(jié):本文提出的PMI模型可以激勵(lì)節(jié)點(diǎn)表征記錄其各階鄰居的信息,從而有效地識(shí)別來自于不同階的鄰居節(jié)點(diǎn).結(jié)合PMI模型在4.2～4.4節(jié)實(shí)驗(yàn)中杰出的表現(xiàn),我們可以發(fā)現(xiàn)節(jié)點(diǎn)的位置信息對(duì)于下游網(wǎng)絡(luò)分析任務(wù)而言是極其重要的.

4.6 參數(shù)學(xué)習(xí)

本節(jié)探究不同的超參設(shè)置對(duì)PMI模型的影響.我們選擇PPI和VoteNet兩個(gè)數(shù)據(jù)集,并在2個(gè)常見分析任務(wù)(多標(biāo)簽分類和鏈接預(yù)測(cè))上進(jìn)行參數(shù)學(xué)習(xí).

我們首先研究衰減函數(shù)Φ(x)和最大階數(shù)K對(duì)于模型的影響,比較5種具有不同衰減速度的衰減函數(shù)在最大階數(shù)K∈{1,2,3,4,5}上的效果,相關(guān)實(shí)驗(yàn)結(jié)果如圖6(a)所示.從結(jié)果中我們發(fā)現(xiàn)不同網(wǎng)絡(luò)分析任務(wù)對(duì)于2類超參的偏好是不同的.在多標(biāo)簽分類任務(wù)中,當(dāng)不考慮衰減函數(shù)時(shí)(即Φ(x)=1),整體效果會(huì)隨著階數(shù)K的增大而快速降低;相反,Φ(x)=1在鏈接預(yù)測(cè)任務(wù)上可以取得不錯(cuò)的效果,其準(zhǔn)確率隨K的增大而升高.總體而言,衰減函數(shù)Φ(x)=x-1,21-x,e1-x較為契合本文PMI模型.同時(shí),對(duì)多標(biāo)簽分類任務(wù)來說,階數(shù)K=2較為合適,這也暗示近鄰信息往往決定節(jié)點(diǎn)的類別.而相反,隨著K的增大,鏈接預(yù)測(cè)的效果普遍上升,說明高階信息對(duì)于鏈接預(yù)測(cè)任務(wù)是比較重要的,因?yàn)楦唠A信息可以讓表征在更加寬的感受野中學(xué)習(xí)節(jié)點(diǎn)的位置信息.

Fig. 6 Parameter study on two different tasks圖6 在2種不同任務(wù)上的參數(shù)學(xué)習(xí)結(jié)果

接下來,我們研究損失函數(shù)中超參α和β對(duì)于效果的影響,兩者用于平衡互信息估計(jì)和網(wǎng)絡(luò)重構(gòu)損失的權(quán)重.我們以0.1為步長,將α和β分別從0.0增加到1.0,并用熱力圖展示不同參數(shù)組合對(duì)多標(biāo)簽分類和鏈接預(yù)測(cè)效果的影響,結(jié)果如圖6(b)所示.總體上,PMI模型對(duì)于兩者的取值并不是很敏感,但當(dāng)α和β分別取0時(shí),方法有明顯的下降,這也從側(cè)面反映位置信息和結(jié)構(gòu)信息對(duì)于節(jié)點(diǎn)表征都很重要.另一方面,我們也發(fā)現(xiàn)2類任務(wù)對(duì)于超參的偏好也是不一樣的.對(duì)于多標(biāo)簽分類任務(wù)而言,顏色較深的區(qū)域往往靠近對(duì)角線附近,這說明對(duì)于分類任務(wù),位置信息和結(jié)構(gòu)信息同等重要;而對(duì)于鏈接預(yù)測(cè)任務(wù),右下角的區(qū)域顏色較深,這意味著一個(gè)較大的α值會(huì)取得更好的效果,也說明節(jié)點(diǎn)的位置信息對(duì)于鏈接預(yù)測(cè)而言更加重要.

5 總 結(jié)

本文主要針對(duì)現(xiàn)有網(wǎng)絡(luò)表征學(xué)習(xí)方法中位置信息缺失的問題,提出一種位置感知的網(wǎng)絡(luò)表征學(xué)習(xí)PMI模型.在本文方法中,我們最大化每個(gè)中心節(jié)點(diǎn)與其各階鄰居之間的互信息,從而在訓(xùn)練的過程中激勵(lì)每個(gè)節(jié)點(diǎn)記住其K階鄰居的信息，我們?cè)?個(gè)不同領(lǐng)域的真實(shí)數(shù)據(jù)集上進(jìn)行了多標(biāo)簽分類、鏈接預(yù)測(cè)、網(wǎng)絡(luò)重構(gòu)實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果表明本文所提PMI模型較現(xiàn)有表征學(xué)習(xí)模型不僅在各類下游網(wǎng)絡(luò)分析任務(wù)上有所提升,并且通過在鄰居對(duì)齊任務(wù)上的進(jìn)一步分析，驗(yàn)證了PMI模型學(xué)到的表征可以有效地獲取節(jié)點(diǎn)的位置信息.