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

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

圖(網(wǎng)絡(luò))是節(jié)點與邊的集合,其中節(jié)點代表了一類特定的事物,而邊則代表了節(jié)點與節(jié)點之間的關(guān)聯(lián).現(xiàn)實世界中的大量數(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é)點成為了關(guān)鍵所在.傳統(tǒng)的獨熱碼方式(one-hot),由于其空間復(fù)雜度會隨著節(jié)點規(guī)模的擴增而快速增大,嚴(yán)重限制了大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)處理和分析的能力,并且獨熱碼無法表達(dá)節(jié)點間的相關(guān)性,間接影響了下游任務(wù)的效果.近年來,隨著深度神經(jīng)網(wǎng)絡(luò)和表征學(xué)習(xí)在圖像、自然語言處理等領(lǐng)域取得重大的成功,不少研究者開始關(guān)注如何對圖中的節(jié)點進行低維表征,使得該表征可以保留網(wǎng)絡(luò)節(jié)點間的相關(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é)點分類[4-5]、鏈接預(yù)測[6-7]、社區(qū)發(fā)現(xiàn)[8-9]等.

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

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

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

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

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

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

1 相關(guān)工作

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

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

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

1.2 互信息估計

(1)

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

(2)

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

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

(3)

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

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

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

2 問題定義

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

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

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

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

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

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

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

3.1 總體框架

如圖3所示,本文提出的PMI模型主要分為2個模塊:1)K階互信息估計模塊用于捕捉每個節(jié)點的位置信息;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階互信息估計模塊的優(yōu)化函數(shù),而JAE則對應(yīng)了網(wǎng)絡(luò)重構(gòu)模塊的優(yōu)化目標(biāo),超參數(shù)α和β用來權(quán)衡兩者.接下來,我們逐一介紹面向K階鄰居的互信息最大化和基于自動編碼機的結(jié)構(gòu)學(xué)習(xí)模塊,最后對本文方法的復(fù)雜度進行分析并給出優(yōu)化方案.

3.2 面向K階鄰居的互信息估計

(5)

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

(6)

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

(7)

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

(8)

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

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

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

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

自編碼機的編碼器部分采用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é)點的表征X=X(2).

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

Z=σ(XTX),

(10)

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

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

(11)

3.4 復(fù)雜度分析

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

4 實驗評估

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

4.1 實驗設(shè)置

我們使用的真實網(wǎng)絡(luò)數(shù)據(jù)來自多個不同領(lǐng)域,統(tǒng)計數(shù)據(jù)如表2所示,各個數(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/,其中每個節(jié)點代表一部電影,節(jié)點間的連邊表示2部電影出自同一位導(dǎo)演.

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

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

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

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

4.2 多標(biāo)簽分類

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

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

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

4.4 鏈接預(yù)測

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

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

4.5 案例研究

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

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

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

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

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

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

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

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

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

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

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

5 總 結(jié)

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