基于多粒度結(jié)構(gòu)的網(wǎng)絡(luò)表示學(xué)習(xí)

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

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

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

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

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

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

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

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

1 問題定義

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

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

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

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

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

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

圖1 網(wǎng)絡(luò)拓?fù)涞牧；謱邮纠鼺ig.1 An example of hierarchical view of network topology

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

2 網(wǎng)絡(luò)表示學(xué)習(xí)方法Multi-GS

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

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

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

本小節(jié)介紹Multi-GS 的粒化分層操作。主要包含兩個步驟：1)粒的移動與合并：移動和合并的決定取決于局部模塊度增量計(jì)算結(jié)果。2) ?；荷筛至６鹊牧咏Y(jié)構(gòu)。相關(guān)細(xì)節(jié)見算法1。

算法1 網(wǎng)絡(luò)粒化分層(Graphgranular)

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

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

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

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

算法1 的主要步驟如下：

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

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

2.2 基于圖卷積網(wǎng)絡(luò)的粒特征表示學(xué)習(xí)

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

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

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

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

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

解碼器使用式(7)重構(gòu)關(guān)系矩陣A，對于重構(gòu)損失，考慮到A的稀疏性，使用加權(quán)交叉熵?fù)p失函數(shù)Loss 構(gòu)建最終的目標(biāo)函數(shù)，具體公式如下：

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

2.3 算法描述

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

算法2基于多粒度結(jié)構(gòu)的網(wǎng)絡(luò)表示學(xué)習(xí)(Multi-GS)

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

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

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

3 實(shí)驗(yàn)和結(jié)果分析

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

3.1 實(shí)驗(yàn)設(shè)定

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

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

2) 對比算法。

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

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

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

GraRep[9]：通過構(gòu)造k步概率轉(zhuǎn)移矩陣學(xué)習(xí)節(jié)點(diǎn)表示，能夠保留節(jié)點(diǎn)的高階相似性。

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

3) 參數(shù)設(shè)定。

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

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

3.2 節(jié)點(diǎn)分類

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

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

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

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

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

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

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

3.3 鏈接預(yù)測

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

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

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

3.4 可視化

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

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

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

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

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

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

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

4 結(jié)束語

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

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

未來工作方向包括探索其他網(wǎng)絡(luò)?；謱蛹夹g(shù)和繼續(xù)深入研究不同的層和不同粗細(xì)的粒以及不同類型的網(wǎng)絡(luò)結(jié)構(gòu)對Multi-GS 的影響。