基于圖卷積集成的網絡表示學習

常新功，王金玨

（山西財經大學 信息學院，山西 太原 030006）

近年來，基于網絡數據結構的深度學習十分流行，廣泛應用于學術領域和工業領域。網絡包括節點和邊，其中節點表示實體，邊表示節點之間的關系。現實世界中很多數據都可以表示為網絡，例如社交網絡[1-2]、生物-蛋白網絡[3]等。利用網絡分析挖掘有價值的信息備受關注，因為高效的網絡分析不僅處理節點分類[1]、鏈路預測[2]、網絡可視化[4-5]等下游任務時有著很好的效果，而且在金融欺詐、推薦系統等場景下都有實際的應用價值。例如，在社交網絡中通過節點分類可以對不同的用戶推薦不同的物品；在生物網絡中，可以通過分析已知的疾病與基因關系預測潛在的致病基因等。

由于網絡數據的非歐幾里得結構，大多數傳統的網絡分析方法不適合使用機器學習技術解決。網絡表示學習[6-8]很好地解決了上述問題，通過將節點映射到低維空間中，節點用學習生成的低維、稠密的向量重新表示，同時盡可能保留網絡中包含的結構信息。因此，網絡被映射到向量空間中就可以使用經典的機器學習技術處理很多網絡分析問題。現有的網絡表示學習方法主要分為以下3 類：

1)基于矩陣分解的網絡表示學習。Roweis 等[9]提出的局部線性表示算法(locally linear embeding,LLE)假設節點和它的鄰居節點都處于同一流形區域，通過它的鄰居節點表示的線性組合近似得到節點表示；He 等[10]提出的保留局部映射算法(locality preserving projections,LPP)通過對非線性的拉普拉斯特征映射方法進行線性的近似得到節點表示；Tu 等[11]提出的圖形分解算法(max margin deep walk,MMDW)通過對鄰接矩陣分解得到節點表示。Cao 等[12]提出的GraRep 算法通過保留節點的k階鄰近性保留全局網絡結構。

2)基于淺層神經網絡的網絡表示學習。Perozzi等[13]提出的DeepWalk 算法通過隨機游走遍歷網絡中的節點得到有序的節點序列，然后利用Skip-Gram 模型預測節點的前后序列學習得到節點的向量表示；Grover 等[14]提出的Node2Vec 改進了DeepWalk 的隨機游走過程，通過引進兩個參數p和q控制深度優先搜索和廣度優先搜索；Tang等[15]提出的Line 算法能夠處理任意類型的大規模網絡，包括有向和無向、有權重和無權重，該算法保留了網絡中節點的一階鄰近性和二階鄰近性。

3)基于深度學習的網絡表示學習。Wang 等[16]提出的SDNE 算法利用深度神經網絡對網絡表示學習進行建模，將輸入節點映射到高度非線性空間中獲取網絡結構信息。Hamilton 等[17]提出的GraphSAGE 是一種適用于大規模網絡的歸納式學習方法，通過聚集采樣到的鄰居節點表示更新當前節點的特征表示。Wang 等[18]提出的Graph-GAN 引入對抗生成網絡進行網絡表示學習。上述研究方法大多是設計一種有效的模型分別應用不同的數據集學習得到高質量的網絡表示，但是單一模型的泛化能力較弱。為了解決此問題，目前有學者提出使用集成思想學習網絡表示，Zhang等[19]提出的基于集成學習的網絡表示學習，其中stacking 集成分別將GCN 和GAE 作為初級模型，得到兩部分節點嵌入拼接后作為節點特征，其與原始圖數據構成新數據集，最后將三層GCN 作為次級模型處理新數據集，使用部分節點標簽進行半監督訓練。

本文引入了stacking 集成方法學習網絡表示。集成方法是對于同一網絡并行訓練多個較弱的個體學習器，每個個體學習器的輸出都是網絡表示，然后采用某種結合策略集成這些輸出進而得到更好的網絡表示。stacking 集成方法是集成方法的一種，結合策略是學習法，即選用次級學習器集成個體學習器的輸出。次級學習器的選擇是影響結果的重要因素，現有工作證明Kipf 等[20]提出的圖卷積神經網絡[21](graph convolutional network,GCN)在提升網絡分析性能上有著顯著的效果，GCN 通過卷積層聚合網絡中節點及鄰居的信息，根據歸一化拉普拉斯矩陣的性質向鄰居分配權重，中心節點及鄰居信息加權后更新中心節點的特征表示。

綜上所述，本文的貢獻有以下幾點：

1)提出了基于stacking 集成學習的網絡表示學習，并行訓練多個較弱的初級學習器，并將它們的網絡表示拼接，選用GCN 作為次級學習器，聚合中心節點及鄰居信息得到最終的網絡表示，這樣可得到更好的網絡表示。

2)利用網絡的一階鄰近性設計了損失函數；

3)設計了評價指標MRR、Hit@1、Hit@3、Hit@10，分別評價初級學習器和集成后的網絡表示，驗證了提出的算法具有較好的網絡表示性能，各評價指標平均提升了1.47～2.97 倍。

1 問題定義

定義1給定網絡G=，其中V表示節點集合，E表示節點之間的邊集合，記vi∈V表示一個節點，ei,j=(vi,vj)∈E表示一條邊，由E構建鄰接矩陣A∈Rn×n表示網絡的拓撲結構，n=|V|，若ei,j∈E，則Ai,j>0，若ei,j?E，則Ai,j=0。

定義2[6]給定網絡G，每個節點的屬性特征是m維，G有n個節點，則網絡G對應的節點特征矩陣H∈Rn×m。網絡表示學習的目標是根據網絡中任意節點vi∈V學習得到低維向量Z∈Rn×d，其中d?n。學習到的低維向量表示可客觀反映節點在原始網絡中的結構特性。例如，相似的節點應相互靠近，不相似的節點應相互遠離。

定義3一階鄰近性[15]。網絡中的一階鄰近性是指兩個節點之間存在邊，若節點vi和vj之間存在邊，這條邊的權重wi,j表示vi和vj之間的一階鄰近性，若節點vi和vj之間沒有邊，則vi和vj之間的一階鄰近性為0。

定義4二階鄰近性[15]。網絡中一對節點vi和vj之間的二階鄰近性是指它們的鄰域網絡結構之間的相似性，令li=(wi,1,wi,2,···,wi,|V|)表示節點vi與其他所有節點的一階鄰近性，vi和vj的二階鄰近性由li和lj的相似性決定。

定義5集成學習[22]。集成學習是構建多個個體學習器 ?1，?2，…，?n，再用某種結合策略將它們的輸出結合起來，結合策略有平均法、投票法和學習法。給定網絡G，定義2 中的網絡表示學習方法可作為個體學習器，其結構如圖1。若個體學習器是同種則是同質集成，否則是異質集成。

圖1 集成學習結構Fig.1 Structure of ensemble learning

定義6stacking 集成學習[22]。stacking 集成學習的結合策略是學習法，對于同一網絡通過k個初級學習器 ?1，?2，…，?k學習得到k部分節點嵌入的特征向量z0，z1，…，zk?1，其嵌入維度均為d維，然后按節點將zi，i∈[0,k?1]對應拼接得到嵌入z，其嵌入維度是k×d維，最后使用次級學習器?得到最終的嵌入z'，為了方便對比設置其嵌入維度也是d維。

2 基于GCN 集成的網絡表示學習方法

本文將stacking 集成思想引入網絡表示學習，對于同一網絡數據基于3 個初級學習器生成3 部分嵌入并將其拼接，然后選取GCN 作為次級學習器得到最終的嵌入，最后使用評價指標進行評價，具體流程如圖2 所示。

圖2 基于GCN 集成的網絡表示學習結構Fig.2 Network representation learning structure based on GCN ensemble method

2.1 初級學習器

初級學習器選擇DeepWalk[13]、Node2Vec[14]和Line[15]。DeepWalk[13]發現在短的隨機游走中出現的節點分布類似于自然語言中的單詞分布，于是采用廣泛使用的單詞表示學習模型Skip-Gram模型學習節點表示；Node2Vec[14]認為DeepWalk的表達能力不足以捕捉網絡中連接的多樣性，所以設計了一個靈活的網絡鄰域概念，并設計隨機游走策略對鄰域節點采樣，該策略能平滑地在廣度優先采樣(BFS)和深度優先采樣(DFS)之間進行插值；Line[15]是針對大規模的網絡嵌入，可以保持一階和二階鄰近性。圖3 給出了一個說明示例，節點6 和節點7 之間邊的權重較大，即節點6 和節點7 有較高的一階鄰近性，它們在嵌入空間的距離應很近；雖然節點5 和節點6 沒有直接相連的邊，但是它們有很多共同的鄰居，所以它們有較高的二階鄰近性，在嵌入空間中距離也應很近。一階鄰近性和二階鄰近性都很重要，一階鄰近性可以用兩個節點之間的聯合概率分布度量，vi和vj的一階鄰近性如式(1)：

圖3 網絡簡單示例Fig.3 Simple example of network

二階鄰近性通過節點vi的上下文節點vj的概率建模，即

條件分布意味著在上下文中具有相似分布的節點彼此相似，通過最小化兩種分布和經驗分布的KL 散度，可以得到既保持一階鄰近性又保持二階鄰近性的節點表示。

2.2 次級學習器

引入stacking 集成方法學習網絡表示，選擇DeepWalk[13]、Node2Vec[14]和Line[15]作為初級學習器。若初級學習器是同種的則為同質集成，否則為異質集成。3 個初級學習器學習得到的嵌入分別是z1、z2、z3，且維數均設為d，并將z1、z2、z3拼接得到嵌入z'，維數為3×d。這個過程中不使用節點的輔助信息，僅利用網絡的拓撲結構學習節點的特征表示。選用GCN 圖卷積網絡模型[21]作為stacking 的次級學習器，學習得到最終的嵌入z，維數是d。

GCN 模型的輸入有兩部分，若網絡G有N個節點，則一部分是嵌入z'，每個節點有H維，其大小為N×H，另一部分是網絡G的鄰接矩陣A，其大小為N×N。首先，通過計算得到歸一化矩陣∈Rn×n，如式(2)：

圖4 拉普拉斯矩陣示例Fig.4 Example of Laplacian matrix

然后，GCN 的整體結構如圖5 所示，用式(3)、(4)描述：

圖5 圖卷積集成網絡模型結構Fig.5 Structure of GCN ensemble model

2.3 損失函數

利用網絡的一階鄰近性設計損失函數，根據噪聲分布對邊采樣負邊，任意邊的損失函數為

式中：第一項是根據觀測到的邊即正例的loss；第二項是為正例采樣的負例的loss；K是負邊的個數；σ(x)=1/(1+exp(?x))是 sigmoid 函數；設置Pn(v)∝，其在文獻[23]中提出，dv是節點v的出度。

邊采樣根據邊的權重選用alias table[15]方法進行，從alias table 中采樣一條邊的時間復雜度是O(1)，負采樣的時間復雜度是O(d(K+1))，d表示出度，K表示K條負邊，所以每步的時間復雜度是O(dK)，步數的多少取決于邊的數量 |E|，因此計算損失的時間復雜度為O(dK|E|)，與節點數量N無關。此邊采樣策略在不影響準確性的情況下提高了效率。

2.4 評價指標

通過2.3 節損失函數影響模型的訓練學習，得到最終的網絡嵌入表示z，對于網絡表示學習的無監督性，設計評價指標[24]評價網絡表示學習的好壞。對于節點vi和vj之間的邊即一個正例，由一對節點(vi,vj)表示，一個正例對應采樣K條負邊，即采樣K個點(n1,n2,···,nk)，其中i,j?(1,K)，構成負例集合{(vi,n1),(vi,n2),···,(vi,nk)}。

衡量一對節點的相似度可計算它們網絡表示的內積，正例(vi,vj)的相似度s=，負例的相似度sp=，p=(1,2,···,K)，相似值越大越好，所以將sp的值由大到小排序，記錄s插入{sp}的索引ranking，索引是從0 開始的，衡量指標需要的是排名位置，所以令ranking=ranking+1，ranking 越小說明網絡表示學習的嵌入越有效。

上文針對一個正例計算得到了一個ranking，對于整個網絡設計指標如表1 所示。

表1 評價指標Table 1 Evaluating indicator

評價數據邊的數量為 |E’|，時間復雜度為O(K|E’|)。

2.5 算法描述

基于圖卷積集成的網絡表示主要包括3 個步驟，首先得到初級學習器的網絡表示，然后用stacking 集成，其中次級學習器選用GCN。對于網絡表示學習的無監督性在GCN 模型中設計了損失函數，也設計了其測試指標，相關算法如算法1所示。

訓練階段進行模型計算和損失計算，所以訓練階段的時間復雜度是O(|E|HTF+dK|E|)，測試階段的時間復雜度是O(K|E′|)，其中H是特征輸入維數384，T為中間層維數256，F為輸出層維數128，數據邊的數量是 |E|，測試數據邊的數量是 |E′|。綜上所述，總體時間復雜度是O(|E|HTF+dK|E|)。

3 實驗和結果分析

在6 個數據集上分別對比DeepWalk、Node 2Vec、Line 這3 個經典的網絡表示學習方法和stacking 集成后的實驗效果，驗證GCN 作為stacking 集成次級學習器的有效性。實驗環境為：Windows10 操作系統，Intel i7-6 700 2.6 GHz CPU，nvidia GeForce GTX 950M GPU，8 GB 內存。編寫Python 和Pytorch 實現。

3.1 實驗設定

1)數據集

實驗使用6 個真實數據集，即Cora、Citeseer、Pubmed、Wiki-Vote、P2P-Gnutella05 和Email-Enron，詳細信息見表2。Cora 是引文網絡，由機器學習論文組成，每個節點代表一篇論文，論文根據論文的主題分為7 類，邊代表論文間的引用關系。Citeseer 也是引文網絡，是從Citeseer 數字論文圖書館中選取的一部分論文，該網絡被分為6 類，邊代表論文間的引用關系。Pubmed 數據集包括來自Pubmed 數據庫的關于糖尿病的科學出版物，被分為3 類。Wiki-Vote 是社交網絡，數據集包含從Wikipedia 創建到2008 年1 月的所有Wikipedia 投票數據。網絡中的節點表示Wikipedia 用戶，從節點i到節點j的定向邊表示用戶i給用戶j的投票。P2P-Gnutella05 是因特網點對點網絡，數據集是從2002 年8 月開始的Gnutella 點對點文件共享網絡的一系列快照，共收集了9 個Gnutella 網絡快照。節點表示Gnutella 網絡拓撲中的主機，邊表示Gnutella 主機之間的連接。Email-Enron 是安然公司管理人員的電子郵件通信網絡，覆蓋了大約50 萬封電子郵件數據集中的所有電子郵件通信，這些數據最初是由聯邦能源管理委員會在調查期間公布在網上的，網絡的節點是電子郵件地址，邊表示電子郵件地址之間的通信。

表2 數據集信息Table 2 Dataset information

2)參數設定

對于stacking 集成方法中的GCN 模型，使用RMSProp 優化器更新訓練參數，學習率設為0.001，訓練次數設為200，卷積層為2 層。對于Deep-Walk 和Node2Vec 共同參數，節點游走次數設為10，窗口大小設為 10，隨機游走的長度設為40。Node2Vec 的超參數p=0.25、q=4。對于Line，負采樣數設為10，學習率設為 0.025。為了方便比較，上述方法的節點表示維度均設為128。

3.2 異質集成實驗結果

實驗選擇4 個領域的數據集，包括Cora、Citeseer、Pubmed、Wiki-Vote、P2P-Gnutella05 和Email-Enron。對于同一數據集，對比各初級學習器、GCN和stacking 異質GCN 集成的特征表示的質量。GCN的參數設定同stacking 集成方法中的GCN 模型參數。GCN 集成過程中僅使用網絡結構，GCN 使用網絡結構和數據集的屬性特征，數據集沒有的使用單位陣代替屬性特征。圖6 展示了各數據集上的評價指標MRR、Hit@1、Hit@3、Hit@10 的比較，各評價指標平均提升了1.47～2.97 倍。

圖6 各數據集異質集成評價指標結果Fig.6 Heterogeneous integration of evaluation index results of all datasets

實驗結果顯示，在各數據集上stacking 集成后的效果明顯優于各初級學習器，僅使用網絡結構的GCN 集成與使用網絡結構和屬性特征的GCN效果相當。這一方面歸功于初級學習器的“好而不同”，即初級學習器有一定的網絡表示學習能力，并且學習器之間具有差異性，會有互補作用；另一方面歸功于GCN 作為stacking 集成次級學習器的有效性，GCN 根據對稱歸一化拉普拉斯矩陣的性質為鄰居分配權重，然后聚合鄰居信息。

3.3 損失函數有效性驗證

本文根據網絡的一階鄰近性設計了損失函數，通過設計使用損失函數和未使用損失函數的實驗來驗證損失函數的有效性。表3 展示了各數據集評價指標的比較，圖中數據集名稱的表示未使用損失函數，數據集名稱中的“-loss”表示使用了損失函數。實驗結果表明，使用損失函數的評價指標與未使用損失函數的相比平均提升了0.44～1.79 倍，驗證了本文損失函數的有效性。

表3 損失函數有效性驗證指標結果Table 3 Results of validation index of loss function

3.4 同質集成實驗對比

本節對比算法分別進行同質stacking，對比設計如表4 所示，第1～3 行是同質集成，第4 行是3.2 節的實驗設定。圖7 展示了Cora、Citeseer和P2P-Gnutella05 數據集同質、異質集成及3 個初級學習器對比的實驗結果。

表4 對比算法設計Table 4 Design of contrast algorithms

圖7 各數據集同質/異質集成對比Fig.7 Comparison of homogeneous/ heterogeneous integration among datasets

實驗結果表明，在不同數據集上不同的同質集成各評價指標的表現不同。但是同質集成效果均明顯優于初級學習器的效果，平均提升了1.46～1.91 倍，所以異質集成的效果平均優于同質集成。在Cora 數據集上，DeepWalk 和Node2Vec 同質集成的效果略差于異質集成，Line 同質集成略好于異質集成；在Citeseer 數據集上，DeepWalk 同質集成效果與異質集成相當，Line 和Node2Vec同質集成略好于異質集成；在P2P-Gnutella05 數據集上，Line 同質集成效果與異質集成相當，Node-2Vec 和DeepWalk 同質集成略好于異質集成。因為數據集網絡結構具有多樣性和復雜性，所以在不同數據集上表現效果不同，有的同質集成效果略優于異質集成。GCN 不僅可以作為集成器，本身也是學習器，有一定的學習能力。

3.5 參數敏感性分析

本節進行參數敏感性實驗，主要分析不同特征維度對性能的影響。實驗選用Cora 數據集，圖8 分別展示了MRR 和Hit@1、Hit@3、Hit@10 的實驗結果。

圖8 參數敏感性分析Fig.8 Parametric sensitivity analysis

實驗結果表明，節點特征向量維度增加到128 時，初級學習器的效果沒有明顯提升；但是GCN 異質集成的效果卻沒有大幅受節點特征向量維度的影響，說明節點特征維度不是實驗結果的重要影響因素。

4 結束語

在網絡表示學習中，如何設計算法學習到高質量的節點表示仍是一個重要的研究課題。本文引入了stacking 集成方法學習網絡表示。首先并行訓練多個簡單的初級學習器，并將它們的嵌入拼接，選用GCN 作為次級學習器，聚合得到最終的網絡表示，然后對網絡表示學習的無監督性，利用網絡的一階鄰近性設計損失函數；最后改進了評價指標MRR、Hit@1、Hit@3、Hit@10，分別測試初級學習器和集成后的節點特征向量表示，驗證了提出算法具有較好的網絡表示性能。

在6 個數據集上進行實驗，在各數據集上stacking 集成后的效果明顯優于各初級學習器，因為GCN 作為stacking 異質集成次級學習器的有效性及初級學習器的“好而不同”。對比算法選擇stacking 同質集成進行比較，實驗結果表明同質集成的效果均明顯優于初級學習器，且異質集成的效果平均優于同質集成，有的數據集同質集成效果由于異質集成是由于GCN 不僅是集成器，更是學習器，有一定的學習能力。對于參數敏感性分析，實驗結果表明節點向量維度不是實驗結果的重要影響因素。

未來研究工作包括探索其他算法作為初級學習器、次級學習器對集成的影響和探索如何提高不同網絡結構的適應性去處理歸納性任務。