結構增強的屬性網絡表示學習

竇 偉，張維玉，翁自強，夏忠秀

齊魯工業大學（山東省科學院）計算機科學與技術學院，濟南250353

在萬物互聯的信息時代，網絡[1]作為日常生活中描述實體之間聯系的重要數據形式，其表示學習的研究也受到廣泛關注。網絡表示學習旨在為網絡中的每個節點學習低維、稠密、實值的向量表示，從而解決諸如鄰接矩陣等傳統網絡表示面臨的高維、稀疏等問題[2]。通過網絡表示學習得到的低維向量具有一定的推理能力，可以直接應用現有的機器學習算法進行多種網絡分析任務來挖掘網絡數據中的潛在信息，例如節點分類[3]、鏈路預測[4]、社區發現[5]等。

早期的網絡表示學習主要基于網絡關系矩陣的計算，通過對關系矩陣進行特征值分解或者奇異值分解從而降低原矩陣的維度得到節點低維表示，關系矩陣是指網絡的鄰接矩陣或者拉普拉斯矩陣[6]。LLE[7]假設網絡中節點的表示是其鄰居節點表示的線性組合。Laplace eigenmap[8]假設網絡中相連的節點其表示也應該相近，并將距離定義為兩個向量的歐氏距離。由于此類方法計算復雜度高，所以難以應用于大規模的網絡分析，并且沒有結合屬性信息。近幾年人工神經網絡技術蓬勃發展，一些基于神經網絡的表示學習方法相繼被提出。DeepWalk[9]的提出掀起了網絡表示學習的研究熱潮，它在網絡中實施截斷隨機游走生成含有鄰接信息的節點序列，然后使用Word2Vec中的skip-gram[10]模型學習網絡表示。LINE[11]定義了網絡中節點的一階和二階的相似性，并設計和優化了兩個目標函數保存節點的相似性。Node2Vec[12]則拓展了DeepWalk隨機游走的方式，結合深度優先搜索和廣度優先搜索進一步探索網絡的結構信息。SDNE[13]將深度學習技術應用到網絡表示學習中，SDNE結合深度自動編碼器和拉普拉斯映射保留網絡結構一階和二階的相似性。然而上述網絡表示學習方法都集中于普通網絡的表示學習，忽略了節點豐富的屬性信息。隨著網絡中信息的多元化，網絡中的節點通常包含有豐富的屬性，例如常用的社交軟件微信、微博，用戶在注冊的時候通常都會填寫個人基本資料（地址、工作單位等）；學術論文的引用網絡，除了論文之間互相的引用關系，每篇論文都會有所屬的期刊/會議，研究主題等，這類具有節點屬性信息的網絡稱之為屬性網絡。

現實生活中大部分網絡都可以建模為屬性網絡，所以最近屬性網絡的表示學習引起學者廣泛研究。TADW[14]證明DeepWalk等價于矩陣分解，在此基礎之上，TADW對鄰接矩陣進行分解的同時使用文本表示矩陣進行約束，得到刻畫結構信息和屬性信息的網絡表示。TriDNR[15]耦合了DeepWalk和Doc2Vec[16]兩個模型，將結構、屬性和標簽考慮其中。FeatWalk[17]和Gat2Vec[18]的想法類似，都是在設計了一個兼容屬性和結構的隨機游走方法，后采用淺層神經網絡學習網絡表示。GraphRNA[19]則在一種屬性隨機游走的基礎之上設計了一種特殊的循環神經網絡框架來學習網絡表示。自動編碼器是無監督深度學習的結構，廣泛應用于各種無監督學習的任務。DANE[20]使用兩個深度自動編碼器通過一致性和互補性約束保留結構信息和屬性信息。MVC-DNE[21]也使用兩個深度自動編碼器，以多視圖學習的視角學習結構和屬性的網絡表示。VGAE[22]將圖變分自動編碼器遷移到屬性網絡表示學習領域。ARNL[23]結合自動編碼器和skip-gram模型共同學屬性和結構的表示并取得了良好的性能。

ANRL使用輸入和輸出不同的自動編碼器，將節點自身屬性信息作為自動編碼器的輸入，重構鄰居的屬性信息。ANRL一定程度結合了結構信息和屬性信息，但是如果自身的屬性信息與鄰居的屬性信息差別較大，即中心節點雖然與鄰居節點相連，但是它們的屬性信息有較大的差異時，則輸入與輸出差別較大自動編碼器在重構過程中會丟失大量信息，從而影響到最終的表示。GCN[24]是譜圖卷積的一階近似，使得處理圖像的卷積操作能夠簡單地被用到網絡結構數據中來，但是GCN是半監督的模型，需要依賴節點的標簽信息，真實的網絡數據的便簽是極為稀疏的，并且GCN只是節點分類的模型，沒有拓展到另一個網絡分析任務鏈路預測上。這里受GCN聚合思想的啟發，結合ANRL的框架結構，本文提出一種結構增強的屬性網絡表示學習方法SANRL（Structure-enhanced Attributed Network Representation Learning）。SANRL在表示學習前期就將結構信息與屬性信息無縫融合，增強了網絡中節點屬性信息的結構特征，并使用自動編碼器無監督地提取節點特征，結合skip-gram模型并通過聯合優化框架將結構信息和屬性信息映射到同一向量空間完成網絡表示學習。

1 相關定義

為了更好地對提出的方法進行闡述，本章對文中出現的字母和符號進行定義和描述。

定義1屬性網絡。用G=(V,ε,A,Z)表示屬性網絡，其中V表示網絡中所包含節點的集合；ε表示節點之間邊的集合；A∈Rn×n是描述網絡全局連接關系的鄰接矩陣，是n×n的方陣，n表示網絡中節點的個數；Z∈?n×m是描述節點屬性信息的屬性矩陣，同樣的，n表示節點的個數，m是屬性矩陣的維數。Ai表示鄰接矩陣A的第i行，是節點i鄰接信息的體現。Aij表示A的第i行第j列的元素，如果Aij=1表示節點i和節點j之間有邊相連，否則Aij=0。Zi表示屬性矩陣Z的第i行，是節點i的屬性信息，如果Zix>0則表示節點i與屬性x相關聯。

定義2屬性網絡表示學習。屬性網絡表示學習的目標就在給定屬性網絡G=(V,ε,A,Z)的情況下，學習一個映射函數f:V?Rd，將網絡中每個節點映射到d維的向量空間中，其中d?n。映射函數f不僅要保留節點的結構信息，還要保留節點的屬性信息。學習到的網絡表示向量可以當作特征向量作為后續網絡分析任務（例如節點分類、鏈路預測）的輸入。

2 結構增強的屬性網絡表示學習

SANRL使用統一的框架對網絡的結構信息和節點的屬性信息進行表示學習，在前期對節點的屬性信息進行鄰接性的增強，旨在更好地融合兩方信息學習最優網絡表示，SANRL的框架流程如圖1所示。本章將對SANRL進行詳細介紹。

圖1 SANRL模型框架Fig.1 Model framework of SANRL

2.1 全局結構信息和屬性信息的學習

網絡的結構信息和節點的屬性信息屬于異構信息，分開進行表示學習后將向量進行拼接也可以起到結合的作用，但是簡單的拼接操作不足以描述節點的結構和屬性之間的復雜關系。這里受GCN的啟發，通過反映全局結構信息的鄰接矩陣和節點屬性信息的屬性矩陣，對節點鄰居的屬性進行聚合操作，并且保留節點自身的屬性，具體的，數學上表示如式（1）所示：

A的每一行Ai表示了當前節點i的一階鄰接關系，與節點i直接相連的節點在Ai的對應位置為1，其余位置為0。當鄰接矩陣A與屬性矩陣Z進行乘積時，即節點i鄰居的屬性在所有維度的加和。因節點自身屬性也很重要，所以在A的基礎之上加一個單位矩陣In得到A?，如此在A?與Z相乘后，節點自身的屬性也被考慮進去。再與自身的度矩陣相乘后得到的新的矩陣M,實際上是節點自身屬性和鄰居屬性的加權平均。相比于普通屬性矩陣Z,M包含了自身和鄰居屬性信息，是網絡結構信息和屬性信息的融合。

得到聚合有自身屬性與鄰接屬性的矩陣M不是最終目標，而是對其降維并保留其中的全局結構信息和屬性信息。為了發揮深度學習自動提取特征的優勢，本文采用無監督的學習結構—自動編碼器進行表示學習。自動編碼器是進行表示學習典型的深度學習模型，它的思路很簡單：將輸入數據通過編碼器映射到某個特征空間，再通過解碼器將編碼器壓縮后的特征空間映射回輸入空間，對輸入數據進行重構，這樣神經網絡的中間層就保存了輸入數據的特征達到降維效果。對應本文的任務，將增強結構信息的屬性聚合矩陣M作為自動編碼器的輸入，數據經過編碼部分被映射到一個低維的向量空間中，然后在解碼部分對輸入的數據進行重構，“強迫”隱含層盡可能多地將輸入數據即結合有全局結構信息和屬性信息的聚合矩陣M的特征保存下來。因此，自動編碼器每一層的隱含表示如下：

其中，L表示自動編碼器的層數；σ(?)是每層網絡的激活函數，例如Tanh、ReLU等；W(l)和b(l)分別是神經網絡第l層的權重矩陣和偏置。自動編碼器不需要額外的監督信息，它通過不斷最小化輸入和輸出之間的重構誤差進行訓練，對應于文本的任務是最小化重構聚合矩陣M的損失，定義為：

2.2 局部結構信息的學習

在上一節中將網絡的全局結構信息和屬性信息可以通過自動編碼器合成到低維向量空間中，但是局部的結構信息需要進一步加強。skip-gram模型已被廣泛應用于網絡結構的表示學習。基于skip-gram模型網絡表示學習的基本假設是如果網絡中的節點擁有相同或者相似上下文節點其網絡表示應該相近，所以它的基本思想是通過網絡中節點之間的共現關系學習節點的向量表示。應用于本文，將自動編碼器提取到的結合有全局結構信息和屬性信息的低維表示通過skip-gram模型使在網絡中具有共現關系的節點的表示向量更加相似。skip-gram模型對局部窗口內的節點對進行概率建模，并最小化公式（7）所表示的對數似然概率：

其中，Ci={vi-w,…,vi+w}指的是隨機游走序列中心節點vi以w為窗口的上下文，條件概率Pr(vj|Mi)是指中心節點vi在結合全局結構信息和屬性信息后與上下文節點共現的可能性，將其定義為：

f(Mi)是中心節點vi的全局結構信息和屬性信息經過自動編碼器得到的低維表示，vj是節點vi上下文的低維表示。注意到公式（8）的分母部分，每一次迭代都需要遍歷網絡中所有的節點來完成計算，對于規模大一些的網絡這個計算是相當昂貴的。為了降低龐大的計算量并且保持結果的有效性，參考文獻[23，27]，本文采用Word2Vec[10]提出的負采樣策略，根據噪聲分布采樣一定數量的負樣本簡化訓練目標：

通過最小化Ls，則有相同的上下文的節點的網絡表示在向量空間中距離更近，數據及其鄰居在輸入空間中的鄰接關系在特征空間中仍然保留下來，使網絡表示的局部結構性得到加強。

2.3 聯合優化

前兩節介紹了如何通過自動編碼器和skip-gram模型捕捉網絡的全局、局部結構信息和屬性信息，因為本文的任務是將結構信息和屬性信息在同一個向量空間進行融合表示，所以結合在公式（6）和公式（10）定義的損失函數La和Ls，得到SANRL最終的損失函數：

本文使用隨機梯度下降來對L進行優化直至模型收斂，優化學習過程在算法1中展示，其中第7行和第9行是對SANRL中參數進行更新的過程。最后通過優化這個聯合損失，SANRL將網絡結構信息、節點屬性信息無縫的嵌入到同一表示空間中，學習最優網絡表示。

算法1SANRL的聯合優化框架

2.4 算法復雜度分析

首先，聚合矩陣的計算復雜度為O(||ε)，因為A?Z能夠被高效地以稀疏矩陣和稠密矩陣相乘的形式實現。其次SANRL以mini-batch的方式訓練神經網絡，其計算復雜度與mini-batch的樣本數和迭代次數相關，所以SANRL是可拓展的。

3 實驗與結果分析

為了驗證所提出的屬性網絡表示學習方法SANRL的有效性，本文在三個公開的真實的屬性網絡數據集上進行實驗。本章介紹了實驗所使用的數據集以及對比方法，通過節點分類和鏈路預測對SANRL進行評估。

3.1 數據集及對比方法介紹

本文使用的數據集是三個真實公開屬性網絡數據集：Cora（https：//snap.stanford.edu/data.）、Citeseer和Pubmed（https：//linqs.soe.ucsc.edu/data.），它們的大致情況如表1所示。鏈接表示論文的引用關系，屬性是對應論文的詞帶模型表示。

表1 三個真實數據集的統計信息Table 1 Statistics of three real-world datasets

為了評估本文提出的SANRL的性能，本文將其與7個具有代表性的網絡表示學習方法進行對比驗證，其中包括3個普通網絡表示學習方法和4個屬性網絡表示學習方法。

（1）DeepWalk[9]在網絡中進行隨機游走得到若干節點序列，將它們送入skip-gram模型中學習網絡表示。

（2）Node2Vec[12]使用偏置隨機游走結合深度優先搜索和廣度優先搜索來捕捉網絡結構信息生成節點序列，并通過skip-gram模型完成網絡中所有節點的表示學習。

（3）SDNE[13]結合深度自動編碼器和拉普拉斯映射同時學習網絡的一階和二階結構信息。

（4）TriDNR[15]耦合skip-gram和Doc2Vec同時學習網絡結構、節點屬性和節點的標簽信息，可以看作是一個半監督的方法。

（5）VGAE[22]是一個基于圖卷積神經網絡的變分自動編碼器模型，同時學習網絡的結構信息和屬性信息。

（6）ANRL[23]通過輸入和輸出不同的自動編碼器和skip-gram模型學習屬性網絡中的節點表示。這里使用它性能最好的一個方法：ANRL-WAN。

（7）DANE[20]通過兩個自動編碼器分別建模結構和屬性信息，設置約束條件在兩種信息之間保持一致性和互補性。

前三個對比方法是普通網絡的表示學習，后四個是屬性網絡表示學習方法。本文對比方法的代碼都是作者提供，并且參數也是按照作者在報告中所指出的進行設定。為了公平起見，最后學習的網絡表示的維度d都設定為128。對于SANRL，將上下文窗口的大小w設置為10，每個節點隨機游走的次數r設置為10，隨機游走的長度l設置為80，負采樣的數量設置為5。SANRL中自動編碼器的結構如表2所示。

表2 神經網絡結構Table 2 Neural network structures

本文實驗采用Python3.6版本，基于Tensorflow1.15.2實現，在Intel Core i7-7700，16.00 GB內存的操作系統為Windows 10（64位）計算機上運行。

3.2 節點分類任務實驗結果分析

在本節中進行常用的網絡分析任務：節點分類來評價SANRL的性能。具體的，首先使用SANRL以及其他對比方法對所給網絡進行表示學習，然后隨機選取30%的節點的表示向量作為節點特征以及對應的標簽作為訓練集來訓練SVM分類器，剩余節點作為測試集，最后計算Macro-F1和Micro-F1值作為測試結果。此過程重復10次取平均值作為最后節點分類的結果。

所有數據集的節點分類的結果如表3所示，最優值以粗體突出顯示。從表中可以觀察出：本文提出的結構增強的屬性網絡表示學習方法SANRL在Cora、Citeseer和Pubmed數據集上均表現出了最佳的性能。在只考慮鏈接的網絡表示學習方法中，Node2Vec相比較其他兩個同類方法表現出較好的性能，但是融合了屬性信息的SANRL在三個數據集中Macro-F1和Micro-F1相比于Node2Vec高出0.065到0.185不等。這表明節點屬性在網絡表示學習中的重要性，融合屬性信息可以很大程度上提高網絡表示學習方法的性能。

表3 三個數據集的節點分類結果Table 3 Node classification results of three datasets

其中在Cora數據集的實驗中，相比較ANRL，Macro-F1值高出約0.077，Micro-F1值也高出約0.085。這說明SANRL在將自身屬性與鄰居屬性聚合后，相比于ANRL輸入和輸出端不同的自動編碼器更容易捕捉到節點之間復雜的非線性的關系，更完整地保留數據中的信息，對最終表示產生積極影響。

綜合表3的實驗結果和上述分析，表明SANRL在節點分類任務中性能最優，能夠更加準確地預測網絡中未知節點的標簽，從而更加有效地從原始屬性網絡中提取更多信息。

3.3 鏈接預測任務實驗結果分析

鏈接預測也是網絡分析中一項非常重要的任務。本文使用三個數據集的鏈路預測任務來評測SANRL的表示學習的能力。鏈接預測的目的是預測網絡中缺失的鏈接，或者預測在未來可能出現的鏈接，常用于一些推薦任務。具體的，首先從網絡中移除10%已有的鏈接，移除鏈接的節點成為正樣本，然后隨機采樣相同數量沒有鏈接的節點作為負樣本，正樣本和負樣本構成測試集。基于剩余的網絡使用對比方法和SANRL進行網絡表示學習。給定測試集中的節點對，根據學得的網絡表示學習向量計算余弦相似度得分，采用AUC值作為評價預測結果的指標。圖2展示了在三個數據集上鏈接預測任務的表現。

圖2 三個數據集的鏈接預測結果Fig.2 Linkprediction results of three datasets

從柱狀圖可以看出本文提出的SANRL表現出最佳性能，其中在三個數據集中SANRL的AUC值高出前三個普通網絡表示學習0.09~0.15不等。結果再次印證只考慮結構信息的網絡表示學習方法的性能有限，將節點屬性信息考慮其中進行表示學習得到的網絡表示向量質量的提高是可觀的，很大程度上彌補了因鏈接稀疏給網絡表示學習造成的阻礙。

SANRL在三個數據集上的實驗結果也均高于其他屬性網絡表示學習方法方法，其中在Pubmed數據集上SANRL的實驗結果的ACU值高出使用兩個自動編碼器的屬性網絡表示學習方法DANE約0.07。SANRL僅使用一個自動編碼器學習網絡表示結果優于兩個自動編碼器的方法，一個重要原因就是網絡的結構信息和屬性信息在進行表示學習時是密不可分的，若分開建模對最終表示影響很大。SANRL在表示學習前期就將屬性信息進行結構信息的增強，從而融合的特征在經過提取之后更大程度地保留了節點在網絡中的所包含的信息，使得學習得到的表示向量對節點相似度的判斷更加準確。

綜合圖2以及上述分析，使用SANRL進行表示學習，其得到的網絡表示對網絡中丟失或者隱含的鏈接地預測更加精準。

4 結束語

本文提出一種鄰居增強的屬性網絡表示學習方法SANRL，該方法可以有效結合網絡的結構信息和節點的屬性信息學習質量更高的網絡表示。在網絡表示學習初期，SANRL首先通過聚合操作使節點的屬性信息得到結構方面的增強，有效避免因結構信息和屬性信息的異構性給網絡表示學習帶來的阻礙。SANRL使用自動編碼器無監督地對結構增強的屬性信息進行特征提取，然后通過skip-gram模型最大化局部窗口內節點對的似然概率，增強網絡局部的鄰接關系使原網絡中距離相近節點的表示向量更加相似。最后SANRL通過一個聯合損失函數使結構和屬性信息得以在同一向量空間獲得最佳表示。在多個真實的網絡進行大量的實驗，SANRL的表現均優于目前流行的網絡表示學習方法，證明了SANRL學習得到的網絡表示質量更高。

異質信息網絡由多種類型的節點和鏈接構成，在現實生活中也比較常見，而異質信息網絡中節點的異質性給未來網絡表示學習帶來更大挑戰。如何在保持結構增強的屬性信息基礎之上將節點的異質性考慮在內，設計出適合異構信息網絡的表示學習方法將成為下一步的研究目標。