張蕾，錢峰，趙姝，陳潔，張燕平，劉峰

（1.安徽大學 計算機科學與技術學院，安徽 合肥 230601; 2.銅陵學院 數(shù)學與計算機學院，安徽 銅陵 244061）

研究人員常用網(wǎng)絡(圖)描述不同學科領域中實體間的交互關系，例如生物學領域中的蛋白質互聯(lián)網(wǎng)絡，社會學領域中的社交網(wǎng)絡，語言學領域中的詞共現(xiàn)網(wǎng)絡。結合不同的分析任務對網(wǎng)絡進行研究、探索，進而挖掘出隱藏在網(wǎng)絡數(shù)據(jù)中的信息，使之服務于人類。不過，真實場景中的網(wǎng)絡數(shù)據(jù)通常具有稀疏、高維等特質，直接利用這樣的數(shù)據(jù)進行分析通常有較高的計算復雜度，使得許多先進的研究成果無法直接應用到現(xiàn)實的網(wǎng)絡環(huán)境中。

網(wǎng)絡表示學習[1](network representation learning，NRL)是解決上述問題的有效方法，旨在保留結構信息的前提下，為網(wǎng)絡中的每個節(jié)點學習一個低維、稠密的向量表示。如此，網(wǎng)絡被映射到一個向量空間中，并可通過許多經(jīng)典的基于向量的機器學習技術處理許多網(wǎng)絡分析任務，如節(jié)點分類[2]、鏈接預測[3]、節(jié)點聚類[4]、可視化[5]、推薦[6]等。

網(wǎng)絡表示學習不僅要解決網(wǎng)絡數(shù)據(jù)的高維和稀疏的問題，還需使學習到的節(jié)點特征表示能夠保留豐富的網(wǎng)絡結構信息。網(wǎng)絡中的節(jié)點結構大致分為三類：1)微觀結構，即局部相似性，例如：一階相似性(相鄰)、二階相似性(有共同的鄰居)。2)中觀結構，例如：角色相似性(承擔相同的功能)、社團相似性(屬于同一社團)。3) 宏觀結構，即全局網(wǎng)絡特性，例如：無標度(度分布符合冪律分布)特性、小世界(高聚類系數(shù))特性。

為獲取有效的節(jié)點表示，結合最先進的機器學習、深度學習等技術，已提出各種各樣的網(wǎng)絡表示學習方法。DeepWalk[7]和Node2Vec[8]通 過隨機游走獲取節(jié)點的局部相似性。GraRep[9]和Walklets[10]通過將鄰接矩陣提升到k次冪獲取節(jié)點的k階相似性。DNGR[11]通過隨機沖浪策略獲取節(jié)點高階相似性。Struc2Vec[12]通過構造層次加權圖，并利用層次加權圖上的隨機游走獲取節(jié)點的結構相似性。M-NMF[13]通過融合模塊度[14](modularity)的非負矩陣分解(nonnegative matrix factor，NMF)方法，將社團結構信息納入網(wǎng)絡表示學習中。GraphWave[15]通過譜圖小波的擴散獲取節(jié)點的角色結構相似性。HARP[16]通過隨機合并網(wǎng)絡中相鄰節(jié)點，迭代地將網(wǎng)絡粗化為一系列簡化的網(wǎng)絡，然后基于這些簡化的網(wǎng)絡遞歸地構建節(jié)點向量，從而捕獲網(wǎng)絡的全局特征。

最近，圖卷積網(wǎng)絡[17](graph convolutional networks，GCN)越來越受到關注，已經(jīng)顯示GCN 對網(wǎng)絡分析任務性能的改進有著顯著的效果。GCN 通過卷積層聚合網(wǎng)絡中每個節(jié)點及其鄰居節(jié)點的特征，輸出聚合結果的加權均值用于該節(jié)點新的特征表示。通過卷積層的不斷疊加，節(jié)點能夠整合k階鄰居信息，從而獲取更高階的節(jié)點特征表示。盡管GCN 的設計目標是利用深層模型更好地學習網(wǎng)絡中節(jié)點的特征表示，但大多數(shù)當前方法依然是淺層結構。例如，GCN[18]實際上只使用兩層結構，更多的卷積層甚至可能會損害方法的性能[19]。而且隨著模型層數(shù)的增加，學習到的節(jié)點特征可能過度平滑，使得不同簇的節(jié)點變得無法區(qū)分。這樣的限制違背使用深層模型的目的，導致利用GCN 模型進行網(wǎng)絡表示學習不利于捕獲節(jié)點的高階和全局特征。

為克服這種限制，受商空間[20]中的分層遞階[21]思想的啟發(fā)，提出一種基于多粒度結構的網(wǎng)絡表示學習方法(network representation learning based on multi-granularity structure，Multi-GS)。Multi-GS 首先基于模塊度[22]和粒計算[23]的思想，利用網(wǎng)絡自身的層次結構，即社團結構，通過使用局部模塊度增量迭代地移動和合并網(wǎng)絡中的節(jié)點，構造網(wǎng)絡的粗粒度結構。利用粗粒度的結構生成更粗粒度的結構，反復多次，最終獲得分層遞階的多粒度網(wǎng)絡結構。在多粒度結構中，不同粗細的粒能夠反映節(jié)點在不同粒度空間上的社團內(nèi)鄰近關系。然后，Multi-GS 使用無監(jiān)督的GCN 模型分別學習不同粒度空間中粒的特征表示向量，學習到的特征能夠反映不同粒度下粒間的鄰近關系，不同粗細粒度中的粒間關系能夠表示不同階的節(jié)點關系，粒度越粗階數(shù)越高。最后，Multi-GS 將不同粒度空間中學習到的粒特征表示按照由粗到細的順序進行逐層細化拼接，輸出最細粒度空間中拼接后的粒特征表示作為初始網(wǎng)絡的節(jié)點特征表示。實驗結果表明，結合多粒度結構能使GCN 有效地捕獲網(wǎng)絡的高階特征，學習的節(jié)點表示可提升諸如節(jié)點分類任務的性能。

1 問題定義

定義1設網(wǎng)絡G=(V,E,A)， 其中，V代表節(jié)點集合，E代表邊集合，A代表鄰接矩陣。記vi∈V代表一個節(jié)點，eij=(vi,vj)∈E代表一條邊，鄰接矩陣A∈Rn×n表示網(wǎng)絡的拓撲結構 ，n=|V|，若eij∈E，則Aij=wij＞0 ；若eij?E，則Ai j=0。記代 表 節(jié) 點vi的 度 ， Γ(vi)={vj|eij∈E} 代表節(jié)點vi的鄰居節(jié)點集合。

定義 2網(wǎng)絡的模塊度[22]Q定義為

式中：m表示網(wǎng)絡中的邊的總數(shù)；lc表示社團c中所有內(nèi)部邊的總數(shù)表示社團c中所有節(jié)點的度的總和；C表示所有社團構成的集合。在社團挖掘任務中，通常使用模塊度評價社團劃分的效果，模塊度Q值越高，表明社團劃分的效果越佳。

基于式(1)，可以推導出兩個社團合并后的局部模塊度增量 ΔQ。設當前劃分中的任意兩個社團p和q， 合并p和q后的社團為k，產(chǎn)生的局部模塊度增量 ΔQpq的計算方法如下：

定義3給定初始網(wǎng)絡G(0)。在粒度世界中，網(wǎng)絡中的每個節(jié)點可視為一個基本粒。同樣用邊描述粒間的關系。通過粒度衡量粒的大小(粗細)?；玖Ｊ侵缸罴毩６鹊牧！Ａ；侵笇⒍鄠€粒合并為一個更粗粒度的粒的操作。

將初始網(wǎng)絡結構視為由基本粒構成的最細粒度的粒層結構。?；謱邮峭ㄟ^聚合和?；僮?，迭代地形成粒度由細到粗的多粒層結構。具體地說，通過不斷聚合不同粒層中的粒和邊，G(0)被遞歸壓縮成一系列粒度由細到粗的粒層，如圖1 所示。

圖1 網(wǎng)絡拓撲的?；謱邮纠鼺ig.1 An example of hierarchical view of network topology

定義4給定網(wǎng)絡G，網(wǎng)絡表示學習的目標是將網(wǎng)絡中的節(jié)點vi∈V映射到低維向量zi∈Rd，其中，d表示向量的維度，d?n。學習到的向量表示可客觀反映節(jié)點在原始網(wǎng)絡中的結構特性。例如，具有相似結構的節(jié)點在特征向量的歐式距離空間中彼此靠近，不相似的節(jié)點彼此遠離。

2 網(wǎng)絡表示學習方法Multi-GS

Multi-GS 首先基于模塊度構建多粒度的網(wǎng)絡分層結構；接著使用GCN 模型依次學習不同粒層中所有粒的特征向量；然后自底向上逐層對粒的特征向量進行映射、拼接；最后輸出最終的結果作為初始網(wǎng)絡中節(jié)點的特征表示，如圖2 所示。

圖2 Multi-GS 方法的框架Fig.2 Framework of Multi-GS approach

2.1 基于模塊度的網(wǎng)絡?；謱?/h3>

本小節(jié)介紹Multi-GS 的粒化分層操作。主要包含兩個步驟：1)粒的移動與合并：移動和合并的決定取決于局部模塊度增量計算結果。2) 粒化：生成更粗粒度的粒層結構。相關細節(jié)見算法1。

算法1 網(wǎng)絡?；謱?Graphgranular)

輸入網(wǎng)絡G=(V,E)，最大?；瘜訑?shù)k；

輸出由細到粗的粒層 G r(0),Gr(1),···,Gr(k)。

10)將粒vi從自身所在的集合中移出；

12)按式(2)計算粒vi移入集合Cj后的模塊度增量 ΔQ；

算法1 的主要步驟如下：

粒的移動與合并：首先將當前粒層中的每個粒放入不同的集合中(第6 行)。其中，子集合的數(shù)量等于當前粒層中粒的數(shù)量。遍歷所有的粒(第9 行)，將當前粒移出自身所在的集合(第10行)，依次移入一個相鄰粒的集合中，并依據(jù)式(2)計算移入后的局部模塊度增量 ΔQ(第11～13 行)。待與所有相鄰粒集合的 ΔQ計算完成后，選擇與最大(正值)模塊度增量相關聯(lián)的相鄰粒集合，并將粒并入該集合中(第14 行)。遍歷結束后，重新計算模塊度Q(第16 行)。當未達到模塊度的局部極大值時，重復上述步驟(第8～16 行)。

在第2 個步驟中，新粒間的邊權由兩個對應集合中的粒間的邊權和確定。同一集合中粒間的內(nèi)部邊視為新粒的自邊。

2.2 基于圖卷積網(wǎng)絡的粒特征表示學習

本小節(jié)介紹Multi-GS 的GCN 模型結構，包括兩個部分，編碼器和解碼器，如圖3 所示。GCN模型借鑒VGAE[24]的設計，Multi-GS 不使用節(jié)點的輔助信息，僅利用網(wǎng)絡的拓撲結構學習節(jié)點的特征表示，因此，最終的GCN 模型在設計上與VGAE 有所區(qū)別。

圖3 圖卷積神經(jīng)網(wǎng)絡模型結構Fig.3 The structure of GCN model

GCN 模型的輸入是不同分層中的粒關系矩陣A，A∈RN×N表示同一粒層中粒間的連接關系，其中，N表示粒的數(shù)量。給定粒i和粒j，則Ai j=wij，wi j表示粒i和粒j間的連接權重。首先，利用式(3)計算得到歸一化的矩陣

其中，f(?) 表示線性激活函數(shù)，第一層使用RELU函數(shù)，第二層使用sigmoid 函數(shù)；μ 和 σ 分別表示向量矩陣Z的均值向量矩陣和標準差向量矩陣；是需要訓練的權重矩陣；可通過對 μ 和 σ 進行采樣得到特征矩陣Z，Z=μ+ε?exp(σ),ε ～N(0,I) ；“*”符號表示兩個向量的內(nèi)積。

基于變分推斷的編碼器，其變分下界的優(yōu)化目標函數(shù)如下：

解碼器使用式(7)重構關系矩陣A，對于重構損失，考慮到A的稀疏性，使用加權交叉熵損失函數(shù)Loss 構建最終的目標函數(shù)，具體公式如下：

結合式(8)和式(12)，GCN 模型最終的目標函數(shù)如下：

2.3 算法描述

本小節(jié)介紹基于多粒度結構的網(wǎng)絡表示學習方法Multi-GS，主要包括3 個步驟：利用局部模塊度增量 ΔQ，由細到粗地構造多粒度的網(wǎng)絡分層結構(已在2.1 小節(jié)詳細介紹)；使用GCN 模型(已在2.2 小節(jié)詳細介紹)學習不同粒層中粒的特征表示；將不同粒層的粒特征表示由粗到細地進行逐層拼接，最終得到最細粒度粒層中粒的特征表示；輸出此結果作為初始網(wǎng)絡的節(jié)點特征表示。相關細節(jié)見算法2。

算法2基于多粒度結構的網(wǎng)絡表示學習(Multi-GS)

輸入網(wǎng)絡G，?；瘜訑?shù)k，節(jié)點表示向量維度d，GCN 參數(shù) Θ；

輸出網(wǎng)絡表示Z。

首先，Multi-GS 算法的輸入包括3 個部分：網(wǎng)絡G；?；瘜訑?shù)k；GCN 模型的參數(shù) Θ，包括，節(jié)點表示向量維度d、訓練次數(shù)和學習率。算法2 的第1 行，使用算法1 構建多粒度的網(wǎng)絡分層結構，其復雜度為O(M+N)，其中M為每輪迭代中粒的數(shù)量，N是粒層中的邊的數(shù)量。第2～第4 行，依次將不同粒層的粒關系矩陣A作為輸入，利用GCN 模型學習粒的特征表示。GCN 模型的復雜度與網(wǎng)絡的邊數(shù)呈線性關系，其復雜度為O(mdh)，其中m是矩陣A中非零元素的數(shù)量，d是特征維數(shù)，h是權重矩陣的特征映射數(shù)量。另外，方法還需重建原始拓撲結構，因此總體復雜度為O(mdH+N2)，其中H是不同層上所有特征映射的總和。第5～第8 行，將學習到的粒特征向量由粗到細地進行拼接。其中，projection 函數(shù)是粒化過程的反向操作。在此過程中，上層的粒特征向量被映射到一個或多個較細粒度粒特征向量，投影結束后，拼接相同粒的兩個不同的粒特征表示。循環(huán)結束后，得到基本粒的拼接后的特征表示，其復雜度為O(M)。第9 行，以基本粒的特征表示作為對應節(jié)點的特征表示進行輸出。

3 實驗和結果分析

本節(jié)通過節(jié)點分類和鏈接預測任務，在真實數(shù)據(jù)集上與4 個具有代表性的網(wǎng)絡表示學習方法進行對比，驗證Multi-GS 的有效性。實驗環(huán)境為：Windows10 操作系統(tǒng)，Intel i7-4790 3.6 GHz CPU，8 GB 內(nèi)存。通過Python 語言和Tensor-Flow 實現(xiàn)Multi-GS。

3.1 實驗設定

1) 數(shù)據(jù)集。

實驗使用5 個真實數(shù)據(jù)集，包括引文網(wǎng)絡、生物網(wǎng)絡、詞共現(xiàn)網(wǎng)絡和社交網(wǎng)絡，詳細信息見表1。Cora[25]是引文網(wǎng)絡。其中，節(jié)點代表論文，根據(jù)論文的不同主題分為7 類。邊代表論文間的引用關系。該網(wǎng)絡包含2 708 個節(jié)點和5 278 條邊。Citeseer[25]同樣是引文網(wǎng)絡。該網(wǎng)絡包含6 類的3 312 種出版物。邊代表不同出版物間的引用關系，共有4 660 條邊。PPI[26]是生物網(wǎng)絡。該網(wǎng)絡包含3 890 個節(jié)點和38 739 條邊。其中，節(jié)點代表蛋白質，根據(jù)不同的生物狀態(tài)分為50 類，邊代表蛋白質間的相互作用。WiKi[27]是維基百科數(shù)據(jù)庫中單詞的共現(xiàn)網(wǎng)絡。該網(wǎng)絡包含4 777 個節(jié)點，92 517 條邊，以及40 種不同的詞性標簽。Blog-Catalog[28]是來自BlogCatalog 網(wǎng)站的社交網(wǎng)絡。節(jié)點代表博主，并根據(jù)博主的個人興趣劃分為39類，邊代表博主間的友誼關系。該網(wǎng)絡包含10 312個節(jié)點和333 983 條邊。

2) 對比算法。

實驗選擇4 種具有代表性的網(wǎng)絡表示學習算法作為對比算法，包括DeepWalk、Node2Vec、GraRep、DNGR。關于這些方法的簡要描述如下：

DeepWalk[7]：使用隨機游走獲取節(jié)點序列，通過SkipGram 方法學習節(jié)點表示。

Node2Vec[8]：類似于DeepWalk，但是使用有偏向的隨機游走獲取節(jié)點序列。

GraRep[9]：通過構造k步概率轉移矩陣學習節(jié)點表示，能夠保留節(jié)點的高階相似性。

DNGR[11]：使用隨機沖浪方法獲取節(jié)點的高階相似性，利用深度神經(jīng)網(wǎng)絡學習節(jié)點表示。

3) 參數(shù)設定。

對于Multi-GS 方法中的GCN 模型，使用Adam 優(yōu)化器更新訓練中的參數(shù)，學習率設為0.05。對于DeepWalk 和Node2Vec，節(jié)點游走次數(shù)設為10，窗口大小設為10，隨機游走的長度設為80。Node2Vec 的參數(shù)p=0.25、q=4。對于GraRep，kstep=4。對于DNGR 的隨機沖浪方法，迭代次數(shù)設為4，重啟概率 α =0.98，自編碼器的層數(shù)設為2，使用RMSProp 優(yōu)化器，訓練次數(shù)設為400，學習率設為0.002。為進行公平比較，所以方法學習的節(jié)點表示維度均設為128。

表1 數(shù)據(jù)集信息Table 1 Datasets information

3.2 節(jié)點分類

利用節(jié)點分類任務比較Multi-GS 和對比算法的性能差異。實驗挑選4 種不同領域數(shù)據(jù)集，包括Citeseer、PPI、WiKi 和BlogCatalog。首先各自使用網(wǎng)絡中所有節(jié)點學習節(jié)點的特征表示，對于Multi-GS，為比較不同的?；瘜哟螌Ψ椒ㄐ阅艿挠绊?，針對不同的數(shù)據(jù)集，分別設置5 組實驗，在每組實驗中，將粒化層次從0 設到4(k為0～4)。k=0 表示Multi-GS 不使用多粒度結構進行聯(lián)合學習表示，僅利用原始網(wǎng)絡通過GCN 模型學習節(jié)點的表示。針對節(jié)點分類，使用Logistic 回歸分類器，隨機從不同數(shù)據(jù)集中分別選擇{10%，50%，90%}節(jié)點訓練分類器，在其余節(jié)點上評估分類器的性能。為衡量分類性能，實驗采用Micro-F1

[29]和Macro-F1[29]作為評價指標。兩個指標越大，分類性能越好。所有的分類實驗重復10次，報告平均結果。表2～5 分別展示在Citeseer、PPI、WiKi 和BlogCatalog 數(shù)據(jù)集上的節(jié)點分類Micro-F1和Macro-F1的均值，其中，粗體表示性能最好的結果，下劃線表示對比算法中性能最優(yōu)的結果。

表2 Citeseer 數(shù)據(jù)集上的Micro-F1 和Macro-F1 結果Table 2 Micro-F1 and Macro-F1 results on Citeseer dataset

表3 PPI 數(shù)據(jù)集上的Micro-F1 和Macro-F1 結果Table 3 Micro-F1 and Macro-F1 results on PPI dataset

表4 WiKi 數(shù)據(jù)集上的Micro-F1 和Macro-F1 結果Table 4 Micro-F1 and Macro-F1 results on WiKi dataset

表5 BlogCatalog 數(shù)據(jù)集上的Micro-F1 和Macro-F1 結果Table 5 Micro-F1 and Macro-F1 results on BlogCatalog dataset

實驗結果顯示，在對比算法中，GreRap 表現(xiàn)出強有力的競爭力，Node2Vec 也表現(xiàn)不俗。因無法獲取節(jié)點的一階相似性，故DNGR 表現(xiàn)較差。針對Multi-GS，可以發(fā)現(xiàn)，相對于不使用聯(lián)合學習(k=0)的情形，使用多粒度結構在多數(shù)情況下可提升方法的性能，說明保留節(jié)點的高階相似性可提升節(jié)點分類任務的性能。對于相同的數(shù)據(jù)集，Multi-GS 在不同的粒化層次下存在差異。具體來說，在Citeseer 數(shù)據(jù)集上，隨著?；瘜訑?shù)的增加，Multi-GS 的Micro-F1 和Macro-F1 值逐漸增大。在PPI 和WiKi 數(shù)據(jù)集上，最佳的結果出現(xiàn)在k=3 時。在BlogCatalog 數(shù)據(jù)集上，當k=2 時方法性能最好。依據(jù)表1 中不同數(shù)據(jù)集平均度的統(tǒng)計結果，可以看出，Citeseer 數(shù)據(jù)集的平均度是3.898 1，說明該網(wǎng)絡是一個弱關系網(wǎng)絡，BlogCata-log 數(shù)據(jù)集的平均度高達64.775 6，是一個強關系網(wǎng)絡。在弱關系網(wǎng)絡中，由于不同社團間的聯(lián)系較弱，使得不同粒層中粒的粒度差異較小，而對于強關系網(wǎng)絡，由于社團內(nèi)部邊的密度與不同社團間的邊密度差異較小，使得小社團快速合并成大社團，導致不同粒層間的粒度差異會非常大。在強關系網(wǎng)絡中，隨著粒化層數(shù)的增加，各粒層中相應粒的特征趨于雷同，若拼接過多類似的特征將導致節(jié)點自身的特征被弱化，導致Multi-GS 的性能會有先提升再降低的情況。因此，針對不同的數(shù)據(jù)集，如何設置一個合理的?；瘜訑?shù)是Multi-GS 需要考慮的問題。

3.3 鏈接預測

鏈接預測任務是預測網(wǎng)絡中給定節(jié)點間是否存在邊。通過鏈接預測可以顯示不同網(wǎng)絡表示方法的鏈接預測能力。對于鏈接預測任務，仍然選擇Citeseer、PPI、WiKi 和BlogCatalog 作為驗證數(shù)據(jù)集，分別從不同數(shù)據(jù)集中隨機移除現(xiàn)有鏈接的50%。使用剩余網(wǎng)絡，利用不同的方法學習節(jié)點表示。另外，將被移除邊中的節(jié)點對作為正樣本，同時隨機采樣相同數(shù)量未連接的節(jié)點對作為負樣本，使正樣本和負樣本構成平衡數(shù)據(jù)集。實驗中，首先基于給定樣本中的節(jié)點對，通過表示向量計算其余弦相似度得分，然后使用Logistic 回歸分類器進行分類，并通過曲線下面積[29](area under curve，AUC)評估標簽間的一致性和樣本的相似性得分。對于Multi-GS，k為0～4。表6顯示鏈接預測任務中，不同算法在Citeseer、PPI、WiKi 和BlogCatalog 數(shù)據(jù)集上的AUC 值，其中，粗體表示性能最好的結果，下劃線表示對比算法中性能最優(yōu)的結果。

表6 鏈接預測任務中不同數(shù)據(jù)集上的AUC 結果Table 6 AUC score on all datasets

表6 的結果顯示，在對比算法中，GraRep 表現(xiàn)依然最好。對于Multi-GS，當不使用聯(lián)合學習框架時，方法的性能是最優(yōu)的。以AUC 為評價標準，相對于對比算法中的最優(yōu)結果，在Citeseer 數(shù)據(jù)集上相對提高45.24%，在WiKi 數(shù)據(jù)集上相對提高15.4%，在PPI 數(shù)據(jù)集上相對提高39.14%，在BlogCatalog 數(shù)據(jù)集上相對提高20.66%。但是，隨著?；瘜訑?shù)的增加，對于鏈接預測任務，方法的性能會越來越差，下降速度會隨著網(wǎng)絡的密度成正比。綜合來看，在鏈接預測任務中，利用多粒度結構聯(lián)合學習到的節(jié)點表示無法提升鏈接預測能力，說明該類任務需要更多節(jié)點自身的特征，節(jié)點低階相似性比高階相似性更重要。雖然融合多粒度結構中節(jié)點的高階特征會導致Multi-GS 性能下降，但可以看出，在較低的k值下，僅利用節(jié)點的拓撲結構信息，Multi-GS 的鏈接預測結果十分理想，說明Multi-GS 中GCN 模型能有效地捕獲節(jié)點的低階相似性。

3.4 可視化

在本小節(jié)中，對Multi-GS 和對比算法學習的節(jié)點表示利用可視化進行比較。由于空間限制，實驗選擇節(jié)點數(shù)較少的Cora 作為可視化數(shù)據(jù)集。其中，每個節(jié)點代表一篇機器學習論文，所有節(jié)點按照論文的主題分為7 類。實驗通過t-SNE[27]工具，將所有方法的節(jié)點表示投影到二維空間中，不同類別的節(jié)點用不同的顏色顯示?？梢暬Y果如圖4 所示。

圖4 Cora 數(shù)據(jù)集的可視化結果Fig.4 The visualization of Cora dataset

在圖4 中，DeepWalk、Node2Vec 的表示結果較差，節(jié)點散布在整個空間中，不同類別的節(jié)點相互混在一起，無法觀察到分組結構，意味著算法無法將相似節(jié)點組合在一起。通過GreRap 的可視化結果，能夠看出節(jié)點間的分組結構。對于Multi-GS，在圖4(e) 中，不同分類的節(jié)點相互混合，這種現(xiàn)象在圖的中心尤其明顯。意味著僅保留低階相似性的節(jié)點表示無法區(qū)分不同分類的節(jié)點。圖4(f)顯示結果與圖4(e)相似。在圖4(g)～圖4(i)中，可以看到節(jié)點逐漸開始呈現(xiàn)緊湊的分組結構，而且不同組之間的距離越來越大，隨著層數(shù)的增加，Multi-GS 可以將相似結構的節(jié)點進行分組并推到一起。因此，在節(jié)點分類任務中，利用多粒度結構使Multi-GS 獲得更好的結果。

3.5 參數(shù)敏感性分析

本節(jié)進行參數(shù)敏感性實驗，主要分析不同的特征維度和粒化層數(shù)對Multi-GS 性能的影響。實驗針對Citeseer 數(shù)據(jù)集，利用Multi-GS 在不同粒化層數(shù)下學習到的不同維度的節(jié)點表示，通過節(jié)點分類、節(jié)點聚類和鏈接預測任務對Multi-GS 進行評估，并報告相關的實驗結果。對于節(jié)點分類任務，隨機選擇50%節(jié)點訓練分類器。采用Micro-F1 和Macro-F1 作為評價指標。對于節(jié)點聚類任務，采用NMI[30]和ARI[30]作為評價指標。對于鏈接預測任務，移除50% 的鏈接，采用AUC 作為評價指標。參數(shù)k表示最終節(jié)點的特征表示融合的?；瘜訑?shù)，若k=0，表示僅選取最細粒度的粒特征表示作為最終的節(jié)點特征表示，k=1，表示用第0 層和第1 層的粒學習到的特征表示進行拼接后的向量作為最終的節(jié)點特征表示，以此類推。其中，0 表示最細粒度，k值越大，表示粒度越粗。對于所有任務，重復實驗10 次并報告平均結果，實驗結果如圖5 所示。

圖5 參數(shù)敏感性分析Fig.5 Parametric sensitivity analysis

圖5 的結果表明，對于節(jié)點分類任務，Micro-F1 和Macro-F1 指標隨著特征維度的上升而上升。因為一個更大的特征維度可以保留網(wǎng)絡中更多的信息。隨著?；瘜訑?shù)的增加，Micro-F1 和Macro-F1 指標也逐漸提升，但是可以看出，這樣的提升效果會隨著?；瘜訑?shù)的增加而越變越小，甚至退化。對于節(jié)點聚類任務，NMI 和ARI 的最優(yōu)結果都出現(xiàn)在k=3 時，繼續(xù)增加層數(shù)，結果會下降。對于鏈接預測任務，AUC 指標隨著特征維度的上升而上升，這是合理的情形。但是當k=4 時，AUC 指標發(fā)生波動，說明疊加更多的層次會導致學習的特征表示發(fā)生信息變化，這是需要避免的情況。通過圖5(f)中顯示的各層中粒的數(shù)量的變化曲線，可以看出，不同層間的粒度差異會隨著層數(shù)的增加而減少。在第3 層和第4 層間，這種粒度差異幾乎很小，意味著節(jié)點在第3 層和第4 層中的特征極為相似，若拼接過多類似的高階特征向量，導致節(jié)點自身的特征被弱化，使得最終Multi-GS 的輸出表示不能在網(wǎng)絡分析任務中發(fā)揮出方法優(yōu)勢。

4 結束語

在網(wǎng)絡表示學習中，如何讓學習到的節(jié)點特征表示能夠保留網(wǎng)絡結構的局部和全局特征，仍是一個開放和重要的研究課題。本文結合分層遞階的思想，提出一種無監(jiān)督網(wǎng)絡表示學習方法Multi-GS，通過構建網(wǎng)絡的深度結構解決GCN 無法有效捕獲節(jié)點高階相似性特征的問題。該方法首先利用模塊度增量逐步構建網(wǎng)絡的多粒度分層結構，然后利用GCN 模型學習不同粒度空間中粒的特征表示，最后將已學習的粒特征向量逐層映射拼接為原始網(wǎng)絡的節(jié)點表示。利用Multi-GS 可捕獲多種網(wǎng)絡結構信息，包括一階和二階相似性、社團內(nèi)相似性(高階結構)和社團間相似性(全局結構)。

為驗證Multi-GS 方法的性能，通過在4 個真實數(shù)據(jù)集上進行節(jié)點分類任務和鏈接預測任務，并與幾個經(jīng)典的網(wǎng)絡表示學習方法進行比較。從實驗結果上看，針對節(jié)點分類任務，使用多粒度結構的Multi-GS 能夠改進節(jié)點的特征表示，提升GCN 模型的節(jié)點分類性能。但是由于網(wǎng)絡結構的多樣性和復雜性，Multi-GS 的?；瘜訑?shù)無法固定，必須根據(jù)不同結構的網(wǎng)絡進行調(diào)整。針對鏈接預測任務，使用多粒度結構M u l t i-G S 對GCN 模型的性能造成損害。說明節(jié)點間的低階鄰近關系對鏈接預測任務是至關重要的。盡管如此，在不使用多粒度結構的情況下，以AUC 為評價指標，相對于對比算法，Multi-GS 的性能優(yōu)勢非常明顯。針對Multi-GS 超參數(shù)敏感性的實驗結果可以看出，面對不同的網(wǎng)絡分析任務，融合不同粒度的粒特征對Multi-GS 的性能有著不同程度的影響。

未來工作方向包括探索其他網(wǎng)絡粒化分層技術和繼續(xù)深入研究不同的層和不同粗細的粒以及不同類型的網(wǎng)絡結構對Multi-GS 的影響。