基于特征加強(qiáng)的異構(gòu)網(wǎng)絡(luò)潛在摘要模型

徐正祥，王 英，汪洪吉，王 鑫+

1.吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，長(zhǎng)春130012

2.符號(hào)計(jì)算與知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室，長(zhǎng)春130012

3.吉林大學(xué) 人工智能學(xué)院，長(zhǎng)春130012

圖摘要是圖挖掘領(lǐng)域中處理大規(guī)模圖數(shù)據(jù)的一項(xiàng)非常重要的技術(shù)，其目的是產(chǎn)生原始圖的一種緊湊表示，用于壓縮和簡(jiǎn)化數(shù)據(jù)以實(shí)現(xiàn)高效計(jì)算、高效查詢等。例如，將原圖的多個(gè)節(jié)點(diǎn)映射到一個(gè)超節(jié)點(diǎn)，將原有的邊映射到一個(gè)超邊上，輸出一個(gè)超圖摘要，以實(shí)現(xiàn)對(duì)原圖的壓縮，同時(shí)可以通過錯(cuò)誤邊界調(diào)整摘要大小，進(jìn)而實(shí)現(xiàn)在摘要圖中的高效查詢。

然而，現(xiàn)實(shí)世界中大多數(shù)網(wǎng)絡(luò)都含有多種類型的節(jié)點(diǎn)和邊，也就是廣義上的異構(gòu)信息網(wǎng)絡(luò)[1]，例如，在Movie 數(shù)據(jù)集中有導(dǎo)演、電影、演員等不同類型的節(jié)點(diǎn)，這些節(jié)點(diǎn)間的關(guān)系包括執(zhí)導(dǎo)、參演等。因此，異構(gòu)信息網(wǎng)絡(luò)的復(fù)雜性在于其節(jié)點(diǎn)和邊類型的多樣性，以及由此產(chǎn)生的復(fù)雜結(jié)構(gòu)和豐富語(yǔ)義，如何在異構(gòu)網(wǎng)絡(luò)中獲取圖的摘要是當(dāng)前的重要挑戰(zhàn)。

傳統(tǒng)的摘要方法[2]通常將節(jié)點(diǎn)映射到超節(jié)點(diǎn)從而導(dǎo)出超圖，并不能導(dǎo)出節(jié)點(diǎn)表示。為了將節(jié)點(diǎn)表示與網(wǎng)絡(luò)摘要融合起來(lái)，本文提出了基于特征加強(qiáng)的異構(gòu)網(wǎng)絡(luò)潛在摘要模型FELS。不同于傳統(tǒng)的摘要方法，F(xiàn)ELS 模型的目標(biāo)是在潛在空間中獲取節(jié)點(diǎn)的低維表示，使得它獨(dú)立于圖的大小，即圖節(jié)點(diǎn)和邊的數(shù)量。FELS 模型不僅能夠獲取潛在的圖摘要，還能夠獲取節(jié)點(diǎn)的表示。主要貢獻(xiàn)如下：

（1）利用多種關(guān)系算子捕獲節(jié)點(diǎn)間不同結(jié)構(gòu)信息，通過迭代的方式增強(qiáng)對(duì)節(jié)點(diǎn)鄰域結(jié)構(gòu)的學(xué)習(xí)。同時(shí)，提出桶映射概念，將不同圖屬性映射到不同桶，解決了特征偏斜問題。

（2）FELS 模型的輸出大小獨(dú)立于網(wǎng)絡(luò)數(shù)據(jù)的大小（節(jié)點(diǎn)數(shù)量），僅與數(shù)據(jù)的復(fù)雜度有關(guān)，并且可以控制摘要大小，以及動(dòng)態(tài)推導(dǎo)出節(jié)點(diǎn)表示，以達(dá)到高精度和高壓縮的選擇。

（3）FELS模型通過減少對(duì)重復(fù)特征的處理，降低了模型復(fù)雜度，減少了計(jì)算內(nèi)存，有助于實(shí)現(xiàn)對(duì)更大數(shù)據(jù)集的處理。

（4）通過將FELS 模型應(yīng)用到異構(gòu)網(wǎng)絡(luò)數(shù)據(jù)集上，在鏈路預(yù)測(cè)任務(wù)上，與最先進(jìn)的方法相比，F(xiàn)ELS精度提升了近4個(gè)百分點(diǎn)，在空間占比上，F(xiàn)ELS具有更明顯的優(yōu)勢(shì)。

1 相關(guān)工作

1.1 網(wǎng)絡(luò)表示

網(wǎng)絡(luò)表示方法在廣義上可分為三類：（1）基于矩陣分解方法[3]。De Ridder等人[4]假設(shè)每個(gè)節(jié)點(diǎn)在潛在空間內(nèi)都是其鄰節(jié)點(diǎn)的結(jié)合，將約束最優(yōu)化問題簡(jiǎn)化成特征值問題，截取較大特征值對(duì)應(yīng)的特征量作為輸出；Belkin等人[5]保證當(dāng)權(quán)重矩陣的權(quán)值較高，所對(duì)應(yīng)的兩個(gè)節(jié)點(diǎn)在嵌入空間的距離較近，將較小的正則化的拉普拉斯矩陣特征值所對(duì)應(yīng)的特征向量作為輸出；Ahmed 等人[6]分解了圖的鄰接矩陣，最小化了損失函數(shù)；Cao等人[7]通過考慮全局結(jié)構(gòu)信息，提出了一種學(xué)習(xí)加權(quán)圖節(jié)點(diǎn)向量表示的新模型；Ou等人[8]通過最小化相似度矩陣與頂點(diǎn)嵌入矩陣的距離，并使用奇異值分解（singular value decomposition，SVD）獲取節(jié)點(diǎn)表示。（2）基于隨機(jī)游走方法。Perozzi等人[9]利用截?cái)嗟碾S機(jī)序列表示節(jié)點(diǎn)的近鄰，然后將得到的序列結(jié)合當(dāng)作自然語(yǔ)言處理中的一個(gè)句子作為詞向量的輸入，進(jìn)而得到節(jié)點(diǎn)表示；Tang 等人[10]為了緩解一階近鄰的稀疏性，考慮了更多的近鄰豐富節(jié)點(diǎn)的表示，例如，二階近鄰主要考察兩個(gè)節(jié)點(diǎn)的共同鄰居，共同鄰居數(shù)越多，兩個(gè)節(jié)點(diǎn)的二階相似度越高；Grover等人[11]通過最大限度地增加隨機(jī)游走（DeepWalk）中后續(xù)節(jié)點(diǎn)發(fā)生的概率，產(chǎn)生了更優(yōu)質(zhì)的節(jié)點(diǎn)嵌入。（3）基于深度學(xué)習(xí)方法。Kipf等人[12]提出通過在圖上定義卷積運(yùn)算符解決圖的稀疏問題，該方法迭代地聚集節(jié)點(diǎn)的鄰居，并和之前迭代中獲得的嵌入共同來(lái)獲得新的嵌入；Wang等人[13]提出使用深度自動(dòng)編碼器保存網(wǎng)絡(luò)的第一階和第二階相似性，通過共同優(yōu)化這兩個(gè)距離實(shí)現(xiàn)這一目標(biāo)，該方法使用高度非線性的函數(shù)獲得節(jié)點(diǎn)表示；Guo等人[14]將三頭注意力與時(shí)序卷積網(wǎng)絡(luò)結(jié)合，探索出一種基于時(shí)間卷積網(wǎng)絡(luò)的特征學(xué)習(xí)方法，以獲得節(jié)點(diǎn)表示；Ribeiro等人[15]忽略節(jié)點(diǎn)和邊緣屬性以及它們?cè)诰W(wǎng)絡(luò)中的位置來(lái)評(píng)估節(jié)點(diǎn)之間的結(jié)構(gòu)相似性，然后建立層次結(jié)構(gòu)來(lái)度量節(jié)點(diǎn)在不同尺度上的結(jié)構(gòu)相似性，為節(jié)點(diǎn)生成隨機(jī)上下文。

1.2 圖摘要

圖摘要用于解決大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)存儲(chǔ)和計(jì)算方面的問題，當(dāng)前圖摘要工作主要分為三類：（1）基于分組和聚合的方法，通過應(yīng)用現(xiàn)有的聚類算法將節(jié)點(diǎn)[16]或邊[17]分組為超節(jié)點(diǎn)或超邊的集合。Zhu等人[18]根據(jù)節(jié)點(diǎn)的標(biāo)簽和結(jié)構(gòu)相似性將節(jié)點(diǎn)聚合成超節(jié)點(diǎn)來(lái)處理每個(gè)實(shí)體。（2）基于簡(jiǎn)化與稀疏的方法，Li 等人[19]提出了一種四步無(wú)監(jiān)督算法，該算法使用邊過濾來(lái)進(jìn)行異構(gòu)社交網(wǎng)絡(luò)的自我中心信息抽象。（3）基于壓縮的方法，Shah等人[20]通過最小化存儲(chǔ)輸入圖所需的存儲(chǔ)空間獲取摘要。Jin等人[21]利用一組關(guān)系運(yùn)算符和關(guān)系函數(shù)（運(yùn)算符的組合）分別捕獲網(wǎng)絡(luò)結(jié)構(gòu)和高階子圖結(jié)構(gòu)，通過奇異值分解獲得潛在摘要表示。另外，在文本摘要領(lǐng)域，周才東等人[22]通過局部注意力機(jī)制與卷積神經(jīng)網(wǎng)絡(luò)結(jié)合的方式提取文本的高層次特征，將其作為編碼器輸入，通過基于全局注意力機(jī)制的解碼器生成摘要；田珂珂等人[23]結(jié)合基于自注意力機(jī)制的Transformer 模型，提出一種基于編碼器共享和門控網(wǎng)絡(luò)的文本摘要方法。

網(wǎng)絡(luò)摘要和網(wǎng)絡(luò)表示是互補(bǔ)的學(xué)習(xí)任務(wù)，具有不同的目標(biāo)和輸出，潛在網(wǎng)絡(luò)摘要的目標(biāo)是將兩者結(jié)合，如圖1所示，學(xué)習(xí)獨(dú)立于圖大小的摘要表示，并獲取節(jié)點(diǎn)表示。本文通過應(yīng)用更豐富的特征和關(guān)系算子捕獲高階子圖信息，加強(qiáng)了對(duì)圖結(jié)構(gòu)信息的提取。此外，針對(duì)異構(gòu)網(wǎng)絡(luò)，例如有向圖、權(quán)重圖、標(biāo)簽圖等，提出了不同的解決策略，生成獨(dú)立于輸入圖大?。ü?jié)點(diǎn)和邊）的潛在摘要，并且能夠獲取節(jié)點(diǎn)表示。

2 問題描述與相關(guān)定義

問題描述潛在網(wǎng)絡(luò)摘要：給定包含|V|=N個(gè)節(jié)點(diǎn)和|E|=M條邊的任意圖，潛在網(wǎng)絡(luò)摘要的目標(biāo)是將圖G映射到大小為K×C的低維摘要表示S中，其中K,C?M,N，且與圖的大小無(wú)關(guān)。輸出的潛在網(wǎng)絡(luò)摘要能夠重構(gòu)節(jié)點(diǎn)表示，同時(shí)獲得的節(jié)點(diǎn)表示能夠?yàn)橄掠稳蝿?wù)如鏈接預(yù)測(cè)提供服務(wù)。

定義1異構(gòu)網(wǎng)絡(luò)通常被定義為圖G=(V,E)，其中V是所有節(jié)點(diǎn)的集合，E是所有邊的集合。在圖上存在一個(gè)節(jié)點(diǎn)類型映射函數(shù)θ和邊類型映射函數(shù)ξ，對(duì)于每一個(gè)節(jié)點(diǎn)v∈V都有θ(v)∈O，O是所有節(jié)點(diǎn)類型的集合，同時(shí)，對(duì)于每一條邊e∈E都有ξ(e)∈R，R是所有邊類型的集合。如果在信息網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)都有特定的節(jié)點(diǎn)類型，或者每條邊都有特定的邊類型，即|O|＞1或|R|＞1，那么這個(gè)網(wǎng)絡(luò)為異構(gòu)網(wǎng)絡(luò)。

定義2（t類型鄰居Nt）給定圖G=(V,E)中任意一個(gè)節(jié)點(diǎn)i，節(jié)點(diǎn)i的t類型的鄰居節(jié)點(diǎn)集合，即從i出發(fā)沿邊e∈E一跳距離內(nèi)的類型為t的節(jié)點(diǎn)集合。特別地，Ni表示節(jié)點(diǎn)i的所有鄰居節(jié)點(diǎn)集合。

定義3（關(guān)系算子φ）關(guān)系算子φ(x,R)∈Φ為對(duì)特征向量x進(jìn)行運(yùn)算并返回單個(gè)值的基本函數(shù)，x與一組相關(guān)元素R相關(guān)聯(lián)。例如，x為N×1的向量，R是節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)集合Ni，φ表示和算子，φ(x,R)將返回從節(jié)點(diǎn)i可到達(dá)的鄰居的計(jì)數(shù)（節(jié)點(diǎn)i的未加權(quán)出度）。

定義4（關(guān)系函數(shù)fφ）關(guān)系函數(shù)是一系列關(guān)系算子φ的組合，即fφ=(φ1°φ2°…°φh)，表示將不同關(guān)系算子應(yīng)用到與R相關(guān)聯(lián)的特征向量x進(jìn)行運(yùn)算返回的向量。fφ為h階關(guān)系函數(shù)。

3 FELS模型

圖摘要主要用于解決大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)存儲(chǔ)和計(jì)算方面的問題，本文圖摘要工作基于特征加強(qiáng)的異構(gòu)網(wǎng)絡(luò)潛在摘要模型FELS，如圖2，主要包括三部分：首先，基于關(guān)系算子對(duì)選取的基本圖特征進(jìn)行特征加強(qiáng)，提取結(jié)構(gòu)信息；其次，為了處理特征加強(qiáng)過程中可能導(dǎo)致的偏斜問題，針對(duì)不同屬性的異構(gòu)網(wǎng)絡(luò)進(jìn)行分類，根據(jù)不同的節(jié)點(diǎn)類型或邊類型以及其他屬性分別進(jìn)行上下文提取，以獲得優(yōu)質(zhì)的節(jié)點(diǎn)特征；最后，針對(duì)上下文特征矩陣使用奇異值分解獲取潛在摘要，同時(shí)獲得節(jié)點(diǎn)表示。

圖2 特征加強(qiáng)的異構(gòu)網(wǎng)絡(luò)潛在摘要模型Fig.2 Feature-enhanced latent summarization model of heterogeneous network

3.1 基本特征選取與特征加強(qiáng)

異構(gòu)網(wǎng)絡(luò)包含上萬(wàn)甚至百萬(wàn)個(gè)節(jié)點(diǎn)，原圖（節(jié)點(diǎn)集和邊集）的鄰接矩陣并不適合直接作為輸入。本節(jié)通過基于節(jié)點(diǎn)屬性從輸入圖中為每個(gè)節(jié)點(diǎn)生成一組基本圖特征，作為原圖的輸入，然后應(yīng)用特定關(guān)系算子組成的關(guān)系函數(shù)聚合節(jié)點(diǎn)高階子圖鄰域間的結(jié)構(gòu)特征，迭代生成一組包含自身節(jié)點(diǎn)和高階子圖結(jié)構(gòu)特征的矩陣。

3.1.1 基礎(chǔ)特征

基礎(chǔ)特征根據(jù)不同的節(jié)點(diǎn)屬性定義獲得，本文將這種屬性定義為B，屬性可以指節(jié)點(diǎn)的鄰接矩陣的行/列，或者與節(jié)點(diǎn)相關(guān)的其他導(dǎo)出向量，例如有向圖，可以同時(shí)考慮節(jié)點(diǎn)的入/出/總出入度/加權(quán)度等?；A(chǔ)特征矩陣F(0)由多個(gè)向量fb構(gòu)成，fb∈Fb由特征函數(shù)Ff獲得，可以指選擇的屬性，然后將特征函數(shù)Ff應(yīng)用到每一個(gè)節(jié)點(diǎn)，可以得到fb：

式中，b∈B，fb是N×1 的特征向量。例如，如果b表示出度的特征，那么fb＜b,N＞則表示圖G中所有N個(gè)節(jié)點(diǎn)的出度特征向量，fb＜b,Ni＞表示Ni節(jié)點(diǎn)的出度。通過不同的節(jié)點(diǎn)屬性信息B（出度、入度等），則可以得到N×|B|的基礎(chǔ)特征矩陣F(0)：

式中，b1,2,…,|B|∈B。例如，節(jié)點(diǎn)間的邊有向且?guī)в袡?quán)重，基礎(chǔ)特征矩陣可?。?/p>

式中，bi、bo、bio分別表示入/出/總度，biw、bow、bw分別表示入/出/總邊權(quán)重的特征。

基礎(chǔ)特征矩陣F(0)聚集了原圖N個(gè)節(jié)點(diǎn)的度特征以及所連邊的權(quán)重特征，但是基礎(chǔ)特征僅包含節(jié)點(diǎn)自身結(jié)構(gòu)特征，計(jì)算過程類似于線性累加，不能學(xué)習(xí)鄰域節(jié)點(diǎn)以及高階鄰域間的結(jié)構(gòu)特征，因此加強(qiáng)對(duì)基礎(chǔ)特征提取，進(jìn)而獲取鄰域結(jié)構(gòu)特征。

3.1.2 基于關(guān)系函數(shù)的特征加強(qiáng)

基礎(chǔ)特征矩陣F(0)聚集了原圖N個(gè)節(jié)點(diǎn)的度特征以及所連邊的權(quán)重特征，但是基礎(chǔ)特征僅包含節(jié)點(diǎn)自身結(jié)構(gòu)特征，計(jì)算過程類似于線性累加，不能學(xué)習(xí)鄰域節(jié)點(diǎn)以及高階鄰域間的結(jié)構(gòu)特征，因此進(jìn)一步對(duì)基礎(chǔ)特征加強(qiáng)，進(jìn)而獲取鄰域結(jié)構(gòu)特征。

為了自動(dòng)導(dǎo)出復(fù)雜的非線性節(jié)點(diǎn)特征，選擇應(yīng)用不同的關(guān)系算子加強(qiáng)對(duì)基礎(chǔ)特征F(0)的鄰域結(jié)構(gòu)學(xué)習(xí)。本文迭代地將關(guān)系算子φ∈Φ應(yīng)用于基礎(chǔ)特征F(0)，聚合生成基本節(jié)點(diǎn)屬性間的線性和非線性結(jié)構(gòu)特征矩陣F(l)，關(guān)系算子φ包含均值、方差、和、最大值、最小值、L1距離、L2距離。將關(guān)系算子按特定順序組合成關(guān)系函數(shù)(φ1,φ2,…,φ|Φ|)，運(yùn)用在節(jié)點(diǎn)的鄰域網(wǎng)絡(luò)上，捕獲節(jié)點(diǎn)l跳鄰域的高階結(jié)構(gòu)特征。例如，fo表示由節(jié)點(diǎn)方向的出度組成的特征向量，sum 關(guān)系算子捕獲節(jié)點(diǎn)i的一階鄰域Ni的出度和；max 關(guān)系算子捕獲節(jié)點(diǎn)i的一階鄰域Ni中的最大出度數(shù)，對(duì)所有節(jié)點(diǎn)應(yīng)用max 算子形成新的特征向量max(fo,N)，其中每個(gè)值記錄相應(yīng)節(jié)點(diǎn)鄰域內(nèi)的最大出度數(shù)。

如圖3 所示，以節(jié)點(diǎn)3 為例，左側(cè)展示了節(jié)點(diǎn)的一階鄰域（藍(lán)色虛線）與二階鄰域（粉色虛線）；右側(cè)描述了節(jié)點(diǎn)通過關(guān)系算子max 傳遞鄰域間最大度數(shù)的方式以及以迭代方式傳遞最大節(jié)點(diǎn)度的過程。迭代過程中每次max 只考慮一階鄰域間最大度數(shù)，將max 關(guān)系算子應(yīng)用到上一層獲得的max(fb,N)上可以聚集更遠(yuǎn)鄰域間的結(jié)構(gòu)特征。

圖3 max關(guān)系算子Fig.3 max relational operator

定義關(guān)系算子的迭代層數(shù)為l∈{1,2,…,L}，可以發(fā)現(xiàn)迭代學(xué)習(xí)獲得結(jié)構(gòu)特征是呈指數(shù)增長(zhǎng)的。迭代過程如下：

式中，φ為一種關(guān)系算子；F(l)為迭代聚合第l層的結(jié)構(gòu)特征矩陣；°為對(duì)F(l-1)進(jìn)行關(guān)系算子φ操作；F(0)為基礎(chǔ)特征矩陣。

本文使用了定義的所有關(guān)系算子，即對(duì)特征矩陣的每一列特征向量都使用了|Φ|個(gè)不同關(guān)系算子的聚合操作，應(yīng)用關(guān)系算子的特定順序記錄了關(guān)系函數(shù)是如何生成的，然后將這組關(guān)系函數(shù)與模型層數(shù)存放在中。與F(0)記錄了結(jié)構(gòu)特征矩陣F(l)的生成過程。

對(duì)于l層結(jié)構(gòu)特征矩陣F(l)，|F(l)|=|B|×|Φ|(l)，|F(l)|表示特征列數(shù)大小，|Φ|表示定義的關(guān)系算子個(gè)數(shù)，可以發(fā)現(xiàn)F(l)特征列數(shù)是隨著|Φ|大小呈指數(shù)增長(zhǎng)的。本文的實(shí)驗(yàn)設(shè)置關(guān)系算子個(gè)數(shù)|Φ|=7，特征迭代次數(shù)L=2，有向圖設(shè)置基本特征個(gè)數(shù)|B|=3，有向權(quán)重圖設(shè)置基本特征個(gè)數(shù)|B|=6。

3.2 基礎(chǔ)特征

3.2.1 上下文提取

使用關(guān)系函數(shù)(φ1,φ2,…,φ|Φ|)遞歸地提取結(jié)構(gòu)特征，獲得多層結(jié)構(gòu)特征矩陣F(l)。如果直接作為節(jié)點(diǎn)表示導(dǎo)出，并不能達(dá)到很好的預(yù)期效果，這是由于無(wú)差別結(jié)構(gòu)保留導(dǎo)致的特征偏斜。本小節(jié)通過考慮不同圖屬性隱藏的豐富的上下文信息，處理無(wú)差別結(jié)構(gòu)提取造成的特征偏斜問題，最終生成異構(gòu)網(wǎng)絡(luò)的上下文矩陣。

圖4 特征抽取Fig.4 Feature extraction

為了防止特征矩陣F(l)被映射過長(zhǎng)導(dǎo)致過度膨脹，選擇將節(jié)點(diǎn)特征向量f映射到大小的桶中，稱為桶映射，t為設(shè)置的縮放比例，桶映射方式為：的第一列值等于的鄰居節(jié)點(diǎn)數(shù)，f(i)表示節(jié)點(diǎn)i對(duì)應(yīng)特征向量的值。使用這種映射方式有兩個(gè)好處：（1）將特征向量f縮短到一個(gè)可管理的維度之內(nèi)；（2）使獲得的上下文表示對(duì)小的噪聲更具魯棒性，特別是對(duì)于高度較大的數(shù)據(jù)，使得小范圍的值被映射到桶中的一個(gè)值中。

上下文特征提取的形式化過程如下：對(duì)于節(jié)點(diǎn)i,其第l層特征F(L)(i)是|F(l)|=|B|×|Φ|(l)維行向量，形式如下：

對(duì)于第l層結(jié)構(gòu)特征矩陣F(L)：

式中，N為圖G的節(jié)點(diǎn)數(shù)。

考慮結(jié)構(gòu)統(tǒng)一性，以無(wú)向無(wú)屬性圖為例，將F(L)看作行向量：

ci形式如下：

式中，c1i為節(jié)點(diǎn)1 對(duì)應(yīng)i列值。ci為第i列特征向量f，對(duì)應(yīng)圖3中的度特征，通過桶映射的方法，第一個(gè)節(jié)點(diǎn)c1i被映射到dk1 向量上，大小為1×logtD，對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行桶映射，ci被映射成N×logtD大小的矩陣，對(duì)每列特征向量f=c進(jìn)行桶映射，結(jié)構(gòu)特征矩陣f(L)=C被桶映射為上下文矩陣P，維度大小為N×(logtD×Z)。

3.2.2 針對(duì)其他屬性圖的策略

針對(duì)其他屬性的網(wǎng)絡(luò)圖G，節(jié)點(diǎn)和邊往往具有多種類型，處理多類型節(jié)點(diǎn)和邊的思想是單獨(dú)考慮每一個(gè)類型，將節(jié)點(diǎn)和邊按照不同的類型進(jìn)行分區(qū)處理，即將節(jié)點(diǎn)鄰居按不同的類型分配到不同的桶中。針對(duì)不同屬性圖的處理如下：

3.3 異構(gòu)網(wǎng)絡(luò)潛在摘要

對(duì)異構(gòu)網(wǎng)絡(luò)學(xué)習(xí)得到的上下文矩陣一般較大，并且上下文矩陣可能存在重復(fù)結(jié)構(gòu)，利用奇異值分解對(duì)上下文矩陣進(jìn)行特征選擇以獲得潛在摘要與節(jié)點(diǎn)表示。

給定節(jié)點(diǎn)特征與圖屬性學(xué)習(xí)到的上下文矩陣C，通過矩陣的奇異值分解獲得潛在摘要的表示，分解為C=Y·SC，其中SC為摘要表示，Y為節(jié)點(diǎn)表示。

具體的摘要過程如下：

式中，U為左特征向量矩陣；Σ為特征值矩陣；V為右特征向量矩陣，·表示矩陣乘法。

節(jié)點(diǎn)表示Y如下：

摘要表示SC如下：

通過摘要表示獲得節(jié)點(diǎn)表示的過程：

其中摘要表示SC、關(guān)系函數(shù)(φ1,φ2,…,φ|Φ|)和基礎(chǔ)特征矩陣F(0)組成了原潛在摘要S={F(0),(φ1,φ2,…,φ|Φ|),SC}，S保留了原圖的結(jié)構(gòu)信息，能夠動(dòng)態(tài)導(dǎo)出保持節(jié)點(diǎn)相似性的節(jié)點(diǎn)表示Y，潛在摘要S主體部分摘要表示SC與原圖大小無(wú)關(guān)，實(shí)現(xiàn)了對(duì)大規(guī)模異構(gòu)網(wǎng)絡(luò)數(shù)據(jù)的壓縮。

算法1 中提供了FELS 模型訓(xùn)練過程的偽碼，具體如下。

算法1FELS

輸入：屬性圖G，關(guān)系算子集Φ，節(jié)點(diǎn)嵌入維度K，上下文桶個(gè)數(shù)b。

輸出：潛在摘要表示S。

4 實(shí)驗(yàn)與結(jié)果

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

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

本文使用6個(gè)真實(shí)世界的異構(gòu)網(wǎng)絡(luò)數(shù)據(jù)集Hhar3、Hhar10、Reut3、Reut10、Movie、American，數(shù)據(jù)集地址http://networkrepository.com。其中Hhar3 和Hhar10屬于不同邊集規(guī)模的同一類數(shù)據(jù)集，Reut3 和Reut10屬于不同邊集規(guī)模的同一類數(shù)據(jù)集。數(shù)據(jù)集中包括標(biāo)簽圖、權(quán)重圖、有向圖，詳細(xì)數(shù)據(jù)統(tǒng)計(jì)如表1所示。

表1 數(shù)據(jù)集Table 1 Dataset

4.1.2 對(duì)比方法

使用FELS模型獲得的節(jié)點(diǎn)表示進(jìn)行鏈路預(yù)測(cè)，對(duì)比的基線方法中，基于矩陣分解方法有GF[6]、HOPE[8]、LP[5]、LLE[4]；基于隨機(jī)游走方法有Dwalk[9]、S2vec[15]、N2vec[11]；基于深度學(xué)習(xí)方法有SDNE[13]；其他方法LINE[10]；MLS[21]與本文的FELS屬于潛在摘要方法。

為了保證實(shí)驗(yàn)的公平性，本文中的所有方法均使用128 維度大小的embedding 進(jìn)行鏈接預(yù)測(cè)實(shí)驗(yàn)，并且進(jìn)行了5次實(shí)驗(yàn)取平均值作為結(jié)果展示。

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

為了測(cè)試不同方法在鏈路預(yù)測(cè)任務(wù)上的性能，對(duì)于每個(gè)數(shù)據(jù)集，隨機(jī)隱藏10%的網(wǎng)絡(luò)邊，使用剩余90%的邊作為訓(xùn)練數(shù)據(jù)學(xué)習(xí)節(jié)點(diǎn)表示，對(duì)可能存在的邊進(jìn)行預(yù)測(cè)。與基線方法相比，F(xiàn)ELS 模型的實(shí)驗(yàn)結(jié)果在各個(gè)數(shù)據(jù)集上均取得了最佳效果，AUC 與ACC比現(xiàn)有最好方法MLS 平均提高4 個(gè)百分點(diǎn)，具體實(shí)驗(yàn)結(jié)果如表2所示。

表2 潛在摘要生成節(jié)點(diǎn)嵌入與基線方法生成嵌入應(yīng)用于鏈接預(yù)測(cè)任務(wù)的結(jié)果對(duì)比Table 2 Comparison of results of latent summarization generation node embedding and baseline method generation embedding applied to link prediction tasks 單位：%

4.3 變體實(shí)驗(yàn)

FELS 具有控制摘要與表示的能力，可以在精度和存儲(chǔ)方面進(jìn)行選擇，即摘要體積越大，保留的圖信息越多，表示原圖能力就越強(qiáng)。本節(jié)設(shè)置了以下變體實(shí)驗(yàn)：

FELS-128：本文默認(rèn)模型，節(jié)點(diǎn)表示維度為128，算子迭代層數(shù)為3。

FELS-64：將節(jié)點(diǎn)表示維度設(shè)置為64。

FELS-256：將節(jié)點(diǎn)表示維度設(shè)置為256。

FELS-C：將關(guān)系算子迭代過程中獲得的特征進(jìn)行拼接，節(jié)點(diǎn)表示維度設(shè)置為128。

FELS-L：關(guān)系算子迭代層數(shù)為2。

MLS：現(xiàn)有最好基線模型。

變體實(shí)驗(yàn)1 如圖5 所示，在不同的數(shù)據(jù)集上，F(xiàn)ELS-256模型的AUC分?jǐn)?shù)都是最高的，同時(shí)圖中節(jié)點(diǎn)表示維度越大，鏈路預(yù)測(cè)的AUC 分?jǐn)?shù)越高，證明FELS模型可以通過設(shè)置維度大小在精度和存儲(chǔ)空間上進(jìn)行選擇。

圖5 變體實(shí)驗(yàn)1Fig.5 Variation experiment 1

變體實(shí)驗(yàn)2 如圖6 所示，與本文默認(rèn)模型FELS-128相比，在不同的數(shù)據(jù)集上，F(xiàn)ELS-C模型的數(shù)據(jù)結(jié)果相差不大，說(shuō)明在關(guān)系算子迭代過程中，較前層特征信息包含在后層較大特征表示中；而FELS-L模型的實(shí)驗(yàn)效果較差，說(shuō)明在關(guān)系算子迭代過程中，較前層特征包含信息較少，后層特征信息更豐富。

圖6 變體實(shí)驗(yàn)2Fig.6 Variation experiment 2

4.4 摘要存儲(chǔ)

存儲(chǔ)空間是度量摘要的一個(gè)關(guān)鍵指標(biāo)，為了說(shuō)明FELS方法在存儲(chǔ)空間方面的優(yōu)越性，選擇大規(guī)模異構(gòu)網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，數(shù)據(jù)集包括Yahoo、Digg、Dbpedia、Bibsonomy，數(shù)據(jù)集地址http://networkrepository.com。詳細(xì)數(shù)據(jù)與實(shí)驗(yàn)結(jié)果如表3所示。

表3 存儲(chǔ)空間對(duì)比Table 3 Comparison of storage space

從實(shí)驗(yàn)結(jié)果可以看出，相較于節(jié)點(diǎn)表示存儲(chǔ)，F(xiàn)ELS方法獲得的摘要表示僅占用其2%～10%的存儲(chǔ)空間，同時(shí)節(jié)點(diǎn)表示EMB 隨著圖的大?。ü?jié)點(diǎn)集）的增大而增大，摘要表示FELS 大小與圖的大小無(wú)關(guān)，只與圖的復(fù)雜度（邊類型、圖類型）有關(guān)。

4.5 迭代層數(shù)L

本節(jié)對(duì)不同迭代層數(shù)的FELS模型進(jìn)行了比較，從實(shí)驗(yàn)結(jié)果表4可以看出，不同數(shù)據(jù)集對(duì)層數(shù)的訓(xùn)練要求不同。例如，針對(duì)邊集數(shù)據(jù)較大的Movie 和Reut10 數(shù)據(jù)集，數(shù)據(jù)層數(shù)越大，AUC 分?jǐn)?shù)越低；針對(duì)類型較多的Hhar 數(shù)據(jù)集，學(xué)習(xí)效果隨迭代層數(shù)增大而增大，增長(zhǎng)速率降低。綜上，不同的數(shù)據(jù)集對(duì)迭代層數(shù)的受影響程度不同，不同的迭代層數(shù)表示對(duì)數(shù)據(jù)不同的學(xué)習(xí)程度，層數(shù)越深表示對(duì)數(shù)據(jù)學(xué)習(xí)得越充分，但是當(dāng)層數(shù)達(dá)到一定深度的時(shí)候，可能會(huì)出現(xiàn)學(xué)習(xí)過于充分的問題。

表4 FELS-L鏈路預(yù)測(cè)對(duì)比Table 4 Comparison of link prediction of FELS-L

5 結(jié)束語(yǔ)

基于不同特征以及特征加強(qiáng)的方式，本文提出了基于特征加強(qiáng)的異質(zhì)網(wǎng)絡(luò)潛在摘要模型FELS，利用融合節(jié)點(diǎn)特征和圖屬性獲得大規(guī)模異構(gòu)網(wǎng)絡(luò)數(shù)據(jù)的摘要表示，即首先通過輸入圖的邊集，考慮原圖中不同的節(jié)點(diǎn)特征信息作為基礎(chǔ)特征，應(yīng)用多種關(guān)系算子捕獲高階子圖結(jié)構(gòu)信息；然后，根據(jù)不同的圖屬性通過一種特殊映射方式學(xué)習(xí)上下文的潛在子空間結(jié)構(gòu)信息；最后，由矩陣分解并進(jìn)行特征選擇從而獲得潛在摘要表示。潛在摘要獨(dú)立于輸入圖的大小，僅取決于網(wǎng)絡(luò)的復(fù)雜性與異構(gòu)性，并且能夠捕獲網(wǎng)絡(luò)中關(guān)鍵的結(jié)構(gòu)信息。與以往的方法相比，本文提出的FELS模型生成的節(jié)點(diǎn)表示在鏈路預(yù)測(cè)任務(wù)中，實(shí)驗(yàn)效果中AUC分?jǐn)?shù)與現(xiàn)有最好模型MLS相比，在不同大小的數(shù)據(jù)集上均有4 個(gè)百分點(diǎn)的提升；同時(shí)，F(xiàn)ELS 模型更簡(jiǎn)潔高效，潛在摘要僅占用原有節(jié)點(diǎn)嵌入的2%～10%的存儲(chǔ)空間。在未來(lái)，將研究如何利用全局結(jié)構(gòu)信息促進(jìn)對(duì)圖結(jié)構(gòu)的提取，以獲取更優(yōu)質(zhì)的摘要與節(jié)點(diǎn)表示。