基于特征加強的異構網絡潛在摘要模型

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

1.吉林大學 計算機科學與技術學院，長春130012

2.符號計算與知識工程教育部重點實驗室，長春130012

3.吉林大學 人工智能學院，長春130012

圖摘要是圖挖掘領域中處理大規模圖數據的一項非常重要的技術，其目的是產生原始圖的一種緊湊表示，用于壓縮和簡化數據以實現高效計算、高效查詢等。例如，將原圖的多個節點映射到一個超節點，將原有的邊映射到一個超邊上，輸出一個超圖摘要，以實現對原圖的壓縮，同時可以通過錯誤邊界調整摘要大小，進而實現在摘要圖中的高效查詢。

然而，現實世界中大多數網絡都含有多種類型的節點和邊，也就是廣義上的異構信息網絡[1]，例如，在Movie 數據集中有導演、電影、演員等不同類型的節點，這些節點間的關系包括執導、參演等。因此，異構信息網絡的復雜性在于其節點和邊類型的多樣性，以及由此產生的復雜結構和豐富語義，如何在異構網絡中獲取圖的摘要是當前的重要挑戰。

傳統的摘要方法[2]通常將節點映射到超節點從而導出超圖，并不能導出節點表示。為了將節點表示與網絡摘要融合起來，本文提出了基于特征加強的異構網絡潛在摘要模型FELS。不同于傳統的摘要方法，FELS 模型的目標是在潛在空間中獲取節點的低維表示，使得它獨立于圖的大小，即圖節點和邊的數量。FELS 模型不僅能夠獲取潛在的圖摘要，還能夠獲取節點的表示。主要貢獻如下：

（1）利用多種關系算子捕獲節點間不同結構信息，通過迭代的方式增強對節點鄰域結構的學習。同時，提出桶映射概念，將不同圖屬性映射到不同桶，解決了特征偏斜問題。

（2）FELS 模型的輸出大小獨立于網絡數據的大?。ü濣c數量），僅與數據的復雜度有關，并且可以控制摘要大小，以及動態推導出節點表示，以達到高精度和高壓縮的選擇。

（3）FELS模型通過減少對重復特征的處理，降低了模型復雜度，減少了計算內存，有助于實現對更大數據集的處理。

（4）通過將FELS 模型應用到異構網絡數據集上，在鏈路預測任務上，與最先進的方法相比，FELS精度提升了近4個百分點，在空間占比上，FELS具有更明顯的優勢。

1 相關工作

1.1 網絡表示

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

1.2 圖摘要

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

網絡摘要和網絡表示是互補的學習任務，具有不同的目標和輸出，潛在網絡摘要的目標是將兩者結合，如圖1所示，學習獨立于圖大小的摘要表示，并獲取節點表示。本文通過應用更豐富的特征和關系算子捕獲高階子圖信息，加強了對圖結構信息的提取。此外，針對異構網絡，例如有向圖、權重圖、標簽圖等，提出了不同的解決策略，生成獨立于輸入圖大?。ü濣c和邊）的潛在摘要，并且能夠獲取節點表示。

2 問題描述與相關定義

問題描述潛在網絡摘要：給定包含|V|=N個節點和|E|=M條邊的任意圖，潛在網絡摘要的目標是將圖G映射到大小為K×C的低維摘要表示S中，其中K,C?M,N，且與圖的大小無關。輸出的潛在網絡摘要能夠重構節點表示，同時獲得的節點表示能夠為下游任務如鏈接預測提供服務。

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

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

定義3（關系算子φ）關系算子φ(x,R)∈Φ為對特征向量x進行運算并返回單個值的基本函數，x與一組相關元素R相關聯。例如，x為N×1的向量，R是節點i的鄰居節點集合Ni，φ表示和算子，φ(x,R)將返回從節點i可到達的鄰居的計數（節點i的未加權出度）。

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

3 FELS模型

圖摘要主要用于解決大規模網絡數據存儲和計算方面的問題，本文圖摘要工作基于特征加強的異構網絡潛在摘要模型FELS，如圖2，主要包括三部分：首先，基于關系算子對選取的基本圖特征進行特征加強，提取結構信息；其次，為了處理特征加強過程中可能導致的偏斜問題，針對不同屬性的異構網絡進行分類，根據不同的節點類型或邊類型以及其他屬性分別進行上下文提取，以獲得優質的節點特征；最后，針對上下文特征矩陣使用奇異值分解獲取潛在摘要，同時獲得節點表示。

圖2 特征加強的異構網絡潛在摘要模型Fig.2 Feature-enhanced latent summarization model of heterogeneous network

3.1 基本特征選取與特征加強

異構網絡包含上萬甚至百萬個節點，原圖（節點集和邊集）的鄰接矩陣并不適合直接作為輸入。本節通過基于節點屬性從輸入圖中為每個節點生成一組基本圖特征，作為原圖的輸入，然后應用特定關系算子組成的關系函數聚合節點高階子圖鄰域間的結構特征，迭代生成一組包含自身節點和高階子圖結構特征的矩陣。

3.1.1 基礎特征

基礎特征根據不同的節點屬性定義獲得，本文將這種屬性定義為B，屬性可以指節點的鄰接矩陣的行/列，或者與節點相關的其他導出向量，例如有向圖，可以同時考慮節點的入/出/總出入度/加權度等?；A特征矩陣F(0)由多個向量fb構成，fb∈Fb由特征函數Ff獲得，可以指選擇的屬性，然后將特征函數Ff應用到每一個節點，可以得到fb：

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

式中，b1,2,…,|B|∈B。例如，節點間的邊有向且帶有權重，基礎特征矩陣可取：

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

基礎特征矩陣F(0)聚集了原圖N個節點的度特征以及所連邊的權重特征，但是基礎特征僅包含節點自身結構特征，計算過程類似于線性累加，不能學習鄰域節點以及高階鄰域間的結構特征，因此加強對基礎特征提取，進而獲取鄰域結構特征。

3.1.2 基于關系函數的特征加強

基礎特征矩陣F(0)聚集了原圖N個節點的度特征以及所連邊的權重特征，但是基礎特征僅包含節點自身結構特征，計算過程類似于線性累加，不能學習鄰域節點以及高階鄰域間的結構特征，因此進一步對基礎特征加強，進而獲取鄰域結構特征。

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

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

圖3 max關系算子Fig.3 max relational operator

定義關系算子的迭代層數為l∈{1,2,…,L}，可以發現迭代學習獲得結構特征是呈指數增長的。迭代過程如下：

式中，φ為一種關系算子；F(l)為迭代聚合第l層的結構特征矩陣；°為對F(l-1)進行關系算子φ操作；F(0)為基礎特征矩陣。

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

對于l層結構特征矩陣F(l)，|F(l)|=|B|×|Φ|(l)，|F(l)|表示特征列數大小，|Φ|表示定義的關系算子個數，可以發現F(l)特征列數是隨著|Φ|大小呈指數增長的。本文的實驗設置關系算子個數|Φ|=7，特征迭代次數L=2，有向圖設置基本特征個數|B|=3，有向權重圖設置基本特征個數|B|=6。

3.2 基礎特征

3.2.1 上下文提取

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

圖4 特征抽取Fig.4 Feature extraction

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

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

對于第l層結構特征矩陣F(L)：

式中，N為圖G的節點數。

考慮結構統一性，以無向無屬性圖為例，將F(L)看作行向量：

ci形式如下：

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

3.2.2 針對其他屬性圖的策略

針對其他屬性的網絡圖G，節點和邊往往具有多種類型，處理多類型節點和邊的思想是單獨考慮每一個類型，將節點和邊按照不同的類型進行分區處理，即將節點鄰居按不同的類型分配到不同的桶中。針對不同屬性圖的處理如下：

3.3 異構網絡潛在摘要

對異構網絡學習得到的上下文矩陣一般較大，并且上下文矩陣可能存在重復結構，利用奇異值分解對上下文矩陣進行特征選擇以獲得潛在摘要與節點表示。

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

具體的摘要過程如下：

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

節點表示Y如下：

摘要表示SC如下：

通過摘要表示獲得節點表示的過程：

其中摘要表示SC、關系函數(φ1,φ2,…,φ|Φ|)和基礎特征矩陣F(0)組成了原潛在摘要S={F(0),(φ1,φ2,…,φ|Φ|),SC}，S保留了原圖的結構信息，能夠動態導出保持節點相似性的節點表示Y，潛在摘要S主體部分摘要表示SC與原圖大小無關，實現了對大規模異構網絡數據的壓縮。

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

算法1FELS

輸入：屬性圖G，關系算子集Φ，節點嵌入維度K，上下文桶個數b。

輸出：潛在摘要表示S。

4 實驗與結果

4.1 實驗設置

4.1.1 數據集

本文使用6個真實世界的異構網絡數據集Hhar3、Hhar10、Reut3、Reut10、Movie、American，數據集地址http://networkrepository.com。其中Hhar3 和Hhar10屬于不同邊集規模的同一類數據集，Reut3 和Reut10屬于不同邊集規模的同一類數據集。數據集中包括標簽圖、權重圖、有向圖，詳細數據統計如表1所示。

表1 數據集Table 1 Dataset

4.1.2 對比方法

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

為了保證實驗的公平性，本文中的所有方法均使用128 維度大小的embedding 進行鏈接預測實驗，并且進行了5次實驗取平均值作為結果展示。

4.2 鏈路預測

為了測試不同方法在鏈路預測任務上的性能，對于每個數據集，隨機隱藏10%的網絡邊，使用剩余90%的邊作為訓練數據學習節點表示，對可能存在的邊進行預測。與基線方法相比，FELS 模型的實驗結果在各個數據集上均取得了最佳效果，AUC 與ACC比現有最好方法MLS 平均提高4 個百分點，具體實驗結果如表2所示。

表2 潛在摘要生成節點嵌入與基線方法生成嵌入應用于鏈接預測任務的結果對比Table 2 Comparison of results of latent summarization generation node embedding and baseline method generation embedding applied to link prediction tasks 單位：%

4.3 變體實驗

FELS 具有控制摘要與表示的能力，可以在精度和存儲方面進行選擇，即摘要體積越大，保留的圖信息越多，表示原圖能力就越強。本節設置了以下變體實驗：

FELS-128：本文默認模型，節點表示維度為128，算子迭代層數為3。

FELS-64：將節點表示維度設置為64。

FELS-256：將節點表示維度設置為256。

FELS-C：將關系算子迭代過程中獲得的特征進行拼接，節點表示維度設置為128。

FELS-L：關系算子迭代層數為2。

MLS：現有最好基線模型。

變體實驗1 如圖5 所示，在不同的數據集上，FELS-256模型的AUC分數都是最高的，同時圖中節點表示維度越大，鏈路預測的AUC 分數越高，證明FELS模型可以通過設置維度大小在精度和存儲空間上進行選擇。

圖5 變體實驗1Fig.5 Variation experiment 1

變體實驗2 如圖6 所示，與本文默認模型FELS-128相比，在不同的數據集上，FELS-C模型的數據結果相差不大，說明在關系算子迭代過程中，較前層特征信息包含在后層較大特征表示中；而FELS-L模型的實驗效果較差，說明在關系算子迭代過程中，較前層特征包含信息較少，后層特征信息更豐富。

圖6 變體實驗2Fig.6 Variation experiment 2

4.4 摘要存儲

存儲空間是度量摘要的一個關鍵指標，為了說明FELS方法在存儲空間方面的優越性，選擇大規模異構網絡數據集進行實驗，數據集包括Yahoo、Digg、Dbpedia、Bibsonomy，數據集地址http://networkrepository.com。詳細數據與實驗結果如表3所示。

表3 存儲空間對比Table 3 Comparison of storage space

從實驗結果可以看出，相較于節點表示存儲，FELS方法獲得的摘要表示僅占用其2%～10%的存儲空間，同時節點表示EMB 隨著圖的大小（節點集）的增大而增大，摘要表示FELS 大小與圖的大小無關，只與圖的復雜度（邊類型、圖類型）有關。

4.5 迭代層數L

本節對不同迭代層數的FELS模型進行了比較，從實驗結果表4可以看出，不同數據集對層數的訓練要求不同。例如，針對邊集數據較大的Movie 和Reut10 數據集，數據層數越大，AUC 分數越低；針對類型較多的Hhar 數據集，學習效果隨迭代層數增大而增大，增長速率降低。綜上，不同的數據集對迭代層數的受影響程度不同，不同的迭代層數表示對數據不同的學習程度，層數越深表示對數據學習得越充分，但是當層數達到一定深度的時候，可能會出現學習過于充分的問題。

表4 FELS-L鏈路預測對比Table 4 Comparison of link prediction of FELS-L

5 結束語

基于不同特征以及特征加強的方式，本文提出了基于特征加強的異質網絡潛在摘要模型FELS，利用融合節點特征和圖屬性獲得大規模異構網絡數據的摘要表示，即首先通過輸入圖的邊集，考慮原圖中不同的節點特征信息作為基礎特征，應用多種關系算子捕獲高階子圖結構信息；然后，根據不同的圖屬性通過一種特殊映射方式學習上下文的潛在子空間結構信息；最后，由矩陣分解并進行特征選擇從而獲得潛在摘要表示。潛在摘要獨立于輸入圖的大小，僅取決于網絡的復雜性與異構性，并且能夠捕獲網絡中關鍵的結構信息。與以往的方法相比，本文提出的FELS模型生成的節點表示在鏈路預測任務中，實驗效果中AUC分數與現有最好模型MLS相比，在不同大小的數據集上均有4 個百分點的提升；同時，FELS 模型更簡潔高效，潛在摘要僅占用原有節點嵌入的2%～10%的存儲空間。在未來，將研究如何利用全局結構信息促進對圖結構的提取，以獲取更優質的摘要與節點表示。