趙 姝，劉夢婷，杜紫維，宋文超，韓光潔

1(計算智能與信號處理教育部重點實驗室，合肥 230601)

2(安徽大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，合肥 230601)

3(安徽省信息材料與智能傳感重點實驗室，合肥 230601)

4(北京智創(chuàng)信安信息科技有限公司，北京 100080)

5(河海大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 常州 213022)

1 引 言

從宏觀的社交網(wǎng)絡(luò)到微觀的蛋白質(zhì)網(wǎng)絡(luò)，網(wǎng)絡(luò)已成為抽象和建模復(fù)雜系統(tǒng)的重要工具，在我們的生活中無處不在.如何挖掘隱藏在網(wǎng)絡(luò)中的信息有著重要價值.近年來，網(wǎng)絡(luò)表示學(xué)習(xí)作為網(wǎng)絡(luò)分析的一種方法，受到極大的關(guān)注.網(wǎng)絡(luò)表示學(xué)習(xí)，又稱網(wǎng)絡(luò)嵌入，旨在將網(wǎng)絡(luò)中的節(jié)點映射成低維稠密的向量，同時保留網(wǎng)絡(luò)的固有特征.學(xué)到的節(jié)點表示可以作為機器學(xué)習(xí)算法的輸入，用于處理社區(qū)發(fā)現(xiàn)、節(jié)點分類、鏈路預(yù)測等下游任務(wù)，對挖掘網(wǎng)絡(luò)的潛在信息有著重要作用.

為獲得有效的節(jié)點表示，研究者們已提出各種網(wǎng)絡(luò)表示學(xué)習(xí)方法.DeepWalk[1]、Node2vec[2]將隨機游走和淺層神經(jīng)網(wǎng)絡(luò)相結(jié)合得到節(jié)點向量.HuGE[3]利用混合屬性啟發(fā)式隨機游走捕獲節(jié)點特征.NetMF[4]、ProNE[5]、eNetMF[6]基于矩陣分解的技術(shù)得到表示向量.隨著圖神經(jīng)網(wǎng)絡(luò)的發(fā)展，GCN[7]、MAGCN[8]等基于深度學(xué)習(xí)的方法被提出，這類方法通過半監(jiān)督的方式學(xué)習(xí)節(jié)點表示，在訓(xùn)練過程中需要利用標(biāo)簽信息.雖然上述方法已經(jīng)取得了不錯的效果，但是它們只考慮了單一粒度下網(wǎng)絡(luò)的結(jié)構(gòu)信息，忽略了網(wǎng)絡(luò)的多粒度特征.然而，現(xiàn)有的復(fù)雜網(wǎng)絡(luò)大多呈現(xiàn)多粒度的結(jié)構(gòu)[9]，如社交網(wǎng)絡(luò)、引文網(wǎng)絡(luò)、蛋白質(zhì)網(wǎng)絡(luò)等.

最近，多粒度網(wǎng)絡(luò)表示學(xué)習(xí)方法因其可以保留網(wǎng)絡(luò)的多粒度特征，從不同粒度上分析網(wǎng)絡(luò)的特性，而受到越來越多的關(guān)注.它們利用一種統(tǒng)一的框架得到節(jié)點表示.具體地，主要經(jīng)過網(wǎng)絡(luò)粗化和網(wǎng)絡(luò)細化兩個階段.網(wǎng)絡(luò)粗化階段，通過設(shè)計節(jié)點合并策略，將網(wǎng)絡(luò)中具有相似特征(一階相似性、二階相似性、社團結(jié)構(gòu))的節(jié)點合并生成超點，構(gòu)成粗粒度網(wǎng)絡(luò).通過粗化階段可以縮小原始網(wǎng)絡(luò)的規(guī)模，同時，由于粗粒度節(jié)點與細粒度節(jié)點之間的對應(yīng)關(guān)系，可以將粗粒度網(wǎng)絡(luò)的表示作為原始網(wǎng)絡(luò)的近似表示.迭代粗化過程還可以獲得網(wǎng)絡(luò)的多粒度結(jié)構(gòu).

網(wǎng)絡(luò)細化階段旨在保留粗化過程中獲得的多粒度結(jié)構(gòu)，將粗粒度空間的節(jié)點表示細化回原始網(wǎng)絡(luò)，得到原始網(wǎng)絡(luò)的節(jié)點向量.現(xiàn)有的細化方法主要分為3大類：第1類方法，如圖1(a)所示，通過在不同粒度網(wǎng)絡(luò)上運用已有的網(wǎng)絡(luò)表示學(xué)習(xí)方法，并利用拼接操作融合不同粒度的節(jié)點表示以得到最終的嵌入向量.但這類方法需要學(xué)習(xí)每一粒度網(wǎng)絡(luò)的節(jié)點向量，所需的時間復(fù)雜度高，同時采用直接拼接的方法，會造成信息的冗余；第2類方法，如圖1(b)所示，通過繼承粗粒度網(wǎng)絡(luò)的節(jié)點表示，將其作為細粒度網(wǎng)絡(luò)的初始嵌入值，再利用現(xiàn)有的網(wǎng)絡(luò)嵌入方法進一步對細粒度網(wǎng)絡(luò)的節(jié)點表示進行更新.重復(fù)這一過程，直到獲得原始網(wǎng)絡(luò)的節(jié)點表示.本質(zhì)上，與基于拼接的方法類似，該類方法仍需要學(xué)習(xí)每一粒度網(wǎng)絡(luò)的節(jié)點表示，所需的時間開銷大；第3類方法，如圖1(c)所示，與第2類方法類似，采用繼承的思想進行細化操作.但對細粒度網(wǎng)絡(luò)的嵌入向量進行更新時，不再需要學(xué)習(xí)過程，僅使用在最粗粒度上訓(xùn)練過的圖卷積網(wǎng)絡(luò)[7]模型，此時節(jié)點更新過程可簡單的看成幾個矩陣相乘.雖然這種方法減少了學(xué)習(xí)不同粒度網(wǎng)絡(luò)表示的時間，但受到GCN模型的影響，在更新細粒度網(wǎng)絡(luò)節(jié)點表示時，通常只能聚合2-3階的鄰域信息，無法聚合高階鄰域信息.

圖1 多粒度網(wǎng)絡(luò)表示學(xué)習(xí)

因此，本文提出一種基于聚合多階鄰域信息的細化方法的多粒度網(wǎng)絡(luò)表示學(xué)習(xí)方法.具體地，對于粗化后得到的多粒度網(wǎng)絡(luò)，首先利用已有的網(wǎng)絡(luò)表示學(xué)習(xí)方法學(xué)習(xí)最粗粒度網(wǎng)絡(luò)的節(jié)點表示，將其作為偽標(biāo)簽訓(xùn)練細化模型，避免再次學(xué)習(xí)每一粒度網(wǎng)絡(luò)的節(jié)點向量；然后利用繼承的思想，將粗粒度得到的節(jié)點表示投影到細粒度網(wǎng)絡(luò)，使構(gòu)成同一超點的節(jié)點表示相同，并融合細粒度網(wǎng)絡(luò)的結(jié)構(gòu)信息得到細粒度網(wǎng)絡(luò)的初始嵌入；最后，通過聚合節(jié)點的高階鄰域信息以更新每一粒度網(wǎng)絡(luò)的表示，重復(fù)這一過程，直到得到原始網(wǎng)絡(luò)的節(jié)點表示.

本文貢獻總結(jié)如下：

1)基于多粒度網(wǎng)絡(luò)表示學(xué)習(xí)的框架，提出一種新的細化方法，利用譜卷積技術(shù)，在逐層更新細粒度網(wǎng)絡(luò)的節(jié)點表示時，可以聚合多階鄰域信息.

2)利用拉普拉斯矩陣的特征值定義廣義的位置嵌入矩陣，作為輔助信息，在網(wǎng)絡(luò)細化時可以進一步保留細粒度網(wǎng)絡(luò)的結(jié)構(gòu)信息.

3)本文在3個公共數(shù)據(jù)集上進行節(jié)點分類的實驗，證明NRAM(Network Refinement based on Aggregating Multi-neighboring information)方法與其他一系列最先進的方法相比在節(jié)點分類任務(wù)上的優(yōu)越性.

2 相關(guān)工作

本文從單粒度網(wǎng)絡(luò)表示學(xué)習(xí)方法和多粒度網(wǎng)絡(luò)表示學(xué)習(xí)方法兩個角度介紹現(xiàn)有的網(wǎng)絡(luò)表示學(xué)習(xí)方法.

2.1 單粒度網(wǎng)絡(luò)表示學(xué)習(xí)方法

早期的網(wǎng)絡(luò)表示學(xué)習(xí)方法，通過構(gòu)建隨機游走序列得到節(jié)點表示，如DeepWalk、Node2vec受Word2vec的影響，構(gòu)建隨機游走序列并結(jié)合淺層神經(jīng)網(wǎng)絡(luò)以得到節(jié)點表示；CNBE[10]、CARE[11]在設(shè)計隨機游走策略時，進一步考慮社團結(jié)構(gòu)的影響；HuGE[3]基于啟發(fā)式的策略設(shè)計隨機游走序列.還有一些方法利用矩陣分解的技術(shù)得到節(jié)點表示，如ProNE[5]、GraRep[12]、Lemane[13]等.但這些方法都是淺層的，無法捕獲高度非線性的網(wǎng)絡(luò)結(jié)構(gòu).因此，SDNE[14]、 DVNE[15]、NetRA[16]等方法采用深度學(xué)習(xí)的方式獲得網(wǎng)絡(luò)中節(jié)點的潛在表示.同時，隨著圖神經(jīng)網(wǎng)絡(luò)技術(shù)的發(fā)展，GCN[7]、GraphSAGE[17]等基于GNN的方法被提出，然而這些方法都需要利用節(jié)點的標(biāo)簽信息.上述方法都屬于單粒度網(wǎng)絡(luò)表示學(xué)習(xí)方法，在學(xué)習(xí)節(jié)點表示的過程中只利用了單一粒度即原始網(wǎng)絡(luò)的拓撲結(jié)構(gòu)，無法保留網(wǎng)絡(luò)的多粒度特征.

2.2 多粒度網(wǎng)絡(luò)表示學(xué)習(xí)方法

該類方法大多利用統(tǒng)一的框架，通過遞歸的調(diào)用粗化方法來得到原始網(wǎng)絡(luò)的多粒度結(jié)構(gòu)，獲得單粒度網(wǎng)絡(luò)無法得到的多粒度網(wǎng)絡(luò)特征.并利用細化方法以保留該多粒度特征，得到原始網(wǎng)絡(luò)的節(jié)點表示.根據(jù)其細化方法的不同主要可以分為3類：1)HSRL[18]、ACE[19]這類方法通過學(xué)習(xí)每一粒度網(wǎng)絡(luò)的節(jié)點表示，并利用拼接的方式得到最終的節(jié)點表示，所需的時間復(fù)雜度高.LouvainNE[20]也利用了拼接的思想，但是對于每一粒度的表示僅利用隨機嵌入的方法，雖然可以快速得到節(jié)點表示，但犧牲了節(jié)點表示的質(zhì)量；2)HARP[21]、HCNE[22]利用繼承的思想，對于粗化階段得到的多粒度網(wǎng)絡(luò)，從最粗粒度的網(wǎng)絡(luò)開始，通過將粗粒度網(wǎng)絡(luò)的表示繼承下來作為細粒度網(wǎng)絡(luò)的初始嵌入，并利用現(xiàn)有的網(wǎng)絡(luò)表示學(xué)習(xí)的方法重新學(xué)習(xí)細粒度網(wǎng)絡(luò)的節(jié)點表示.與第一類方法類似，該類方法也需要利用現(xiàn)有的網(wǎng)絡(luò)表示學(xué)習(xí)方法重新學(xué)習(xí)每一粒度網(wǎng)絡(luò)的表示，時間開銷大；3)HGNS[23]、MILE[24]通過不同的粗化策略壓縮網(wǎng)絡(luò)的規(guī)模，構(gòu)建多粒度網(wǎng)絡(luò)；細化階段仍利用繼承的思想，但不需要再重新學(xué)習(xí)每一粒度網(wǎng)絡(luò)的節(jié)點表示，僅利用最粗粒度網(wǎng)絡(luò)上訓(xùn)練的圖卷積網(wǎng)絡(luò)逐層細化更新得到節(jié)點的表示.受GCN模型的限制，該類方法在逐層更新細粒度網(wǎng)絡(luò)的節(jié)點表示時，無法利用節(jié)點的高階鄰域信息.

3 問題定義

下面給出本文所提問題的定義及使用的符號定義.

定義1.網(wǎng)絡(luò).G=(V，E，A)表示網(wǎng)絡(luò)，其中V={v1，v2，…，vn}表示構(gòu)成網(wǎng)絡(luò)的n個節(jié)點的集合，E表示網(wǎng)絡(luò)中存在的所有邊的集合，A∈Rn×n表示網(wǎng)絡(luò)的鄰接矩陣，用于定義節(jié)點間的連接關(guān)系.

定義2.網(wǎng)絡(luò)表示學(xué)習(xí).給定網(wǎng)絡(luò)G=(V，E，A)，通過學(xué)習(xí)映射函數(shù)：f：G→Rn×d，其中d?n，可以得到保留網(wǎng)絡(luò)重要特征的節(jié)點向量Z，zi表示節(jié)點vi的低維向量表示.

定義3.網(wǎng)絡(luò)粗化.給定網(wǎng)絡(luò)G=(V，E，A)，令G0=G，通過定義網(wǎng)絡(luò)粗化方法Coarsen：Gi→Gi+1，|Vi+1|<|Vi|，i=0，1，…,k-1，k表示多粒度網(wǎng)絡(luò)的粒度數(shù)，即粗化層數(shù)，Gi+1是比Gi粒度更粗的網(wǎng)絡(luò)，迭代的將不同粒度中結(jié)構(gòu)相似的節(jié)點合并成超點，構(gòu)造出規(guī)模逐漸減小的多粒度網(wǎng)絡(luò)G0，G1，…，Gk.

定義4.網(wǎng)絡(luò)細化.利用網(wǎng)絡(luò)粗化階段得到的多粒度網(wǎng)絡(luò)G0，Gi，…，Gk，網(wǎng)絡(luò)細化旨在通過學(xué)習(xí)每一粒度網(wǎng)絡(luò)的表示Zi←f(Gi)，i=0，…，k，將粗粒度空間的節(jié)點表示細化回原始網(wǎng)絡(luò)，最終得到原始網(wǎng)絡(luò)的節(jié)點向量Z0.

定義5.多粒度網(wǎng)絡(luò)表示學(xué)習(xí).多粒度網(wǎng)絡(luò)表示學(xué)習(xí)包括網(wǎng)絡(luò)粗化和網(wǎng)絡(luò)細化兩個階段.給定網(wǎng)絡(luò)G=(V，E，A)，先利用網(wǎng)絡(luò)粗化方法構(gòu)造多粒度網(wǎng)絡(luò)G0，G1，…，Gk，其中Gk表示最粗粒度的網(wǎng)絡(luò).再利用細化方法，得到保留網(wǎng)絡(luò)多粒度特征的原始網(wǎng)絡(luò)的節(jié)點表示Z0.

4 算法描述

為保留網(wǎng)絡(luò)的多粒度結(jié)構(gòu)，將粗粒度空間的節(jié)點表示細化回原始網(wǎng)絡(luò)，本文提出基于聚合多階鄰域信息的細化方法的多粒度網(wǎng)絡(luò)表示學(xué)習(xí).主要包含兩個模塊，基于社團壓縮的網(wǎng)絡(luò)粗化模塊和基于聚合多階鄰域信息的網(wǎng)絡(luò)細化模塊.通過粗化模塊可以捕獲網(wǎng)絡(luò)的多粒度結(jié)構(gòu)，并利用網(wǎng)絡(luò)細化模塊保留該多粒度結(jié)構(gòu)，得到原始網(wǎng)絡(luò)的節(jié)點表示.

4.1 基于社團壓縮的網(wǎng)絡(luò)粗化

給定原始網(wǎng)絡(luò)G=(V，E，A)，粗化階段的目的是通過粗化方法迭代地構(gòu)造出規(guī)模逐漸減小的網(wǎng)絡(luò)G1，…，Gk，獲得網(wǎng)絡(luò)的多粒度結(jié)構(gòu).具體地，以Gi到Gi+1的粗化過程為例.首先，利用社團劃分算法將Gi劃分成多個不重疊的社團，本文選擇基于模塊度的社團劃分算法Louvain[25]算法；然后，將每個社團的節(jié)點合并構(gòu)成粗粒度網(wǎng)絡(luò)Gi+1中的超節(jié)點.為了保留粗化過程中，粗粒度網(wǎng)絡(luò)和細粒度網(wǎng)絡(luò)中節(jié)點的對應(yīng)關(guān)系，即Gi中的節(jié)點和Gi+1中超節(jié)點的對應(yīng)關(guān)系，定義匹配矩陣M|Vi|×|Vi+1|，其中每個元素Mjk可定義為：

(1)

對于超點間的連邊情況，需要考慮Gi的結(jié)構(gòu).如果構(gòu)成不同超點的社團中的節(jié)點有連邊，則粗粒度網(wǎng)絡(luò)Gi+1中對應(yīng)的超點間也存在一條連邊.如圖2所示，通過社團壓縮的方式，可以將Gi壓縮成3個不重疊的社團，構(gòu)成粗粒度網(wǎng)絡(luò)Gi+1的節(jié)點集{vABC，vDE，vF}.由于構(gòu)成超節(jié)點vDE，vF的節(jié)點vD和vF間存在連邊，則超點vDE，vF間存在連邊.通過構(gòu)建Gi+1的鄰接矩陣Ai+1可以保留該關(guān)系：

圖2 多粒度網(wǎng)絡(luò)細化過程

(2)

重復(fù)這一過程，得到規(guī)模逐漸變小的網(wǎng)絡(luò)G1，…，Gk，其中Gi揭示了原始網(wǎng)絡(luò)不同粒度的拓撲信息.

4.2 基于聚合多階鄰域信息的網(wǎng)絡(luò)細化

網(wǎng)絡(luò)細化旨在通過將粗粒度空間的節(jié)點表示細化回原始網(wǎng)絡(luò)，以保留粗化階段獲得的多粒度結(jié)構(gòu)G1，…，Gk，得到原始網(wǎng)絡(luò)的節(jié)點表示Z0.

為了解決這一問題，本文首先討論如何從Gi+1細化到Gi.一旦解決這個問題，就可以迭代的將該方法運用到相鄰的不同粒度的網(wǎng)絡(luò)上，最終得到原始網(wǎng)絡(luò)的節(jié)點向量Z0.具體的，給定網(wǎng)絡(luò)Gi，對應(yīng)的粗粒度網(wǎng)絡(luò)Gi+1和粗粒度網(wǎng)絡(luò)的節(jié)點表示Zi+1，如何推斷出Gi的節(jié)點表示Zi.以圖2為例，顯示粗粒度網(wǎng)絡(luò)Gi+1到細粒度網(wǎng)絡(luò)Gi的細化過程.

首先，通過投影的方式，繼承粗粒度網(wǎng)絡(luò)Gi+1的特征，Gi中每個節(jié)點的初始嵌入值等于對應(yīng)的Gi+1中超節(jié)點的嵌入，如圖2所示，Gi中的節(jié)點vA，vB和vC與其構(gòu)成的Gi+1中的超點vABC的表示相同，同理可推導(dǎo)出vD，vE和vF的表示.再融合細粒度網(wǎng)絡(luò)Gi的結(jié)構(gòu)信息，得到細粒度網(wǎng)絡(luò)的初始表示：

Zi=Project(Zi+1，Gi)⊕Xi

(3)

Project(Zi+1，Gi)=Mi，i+1×Zi+1

(4)

其中Project(·)表示投影操作，⊕表示拼接操作，通過該操作可以保留粗粒度網(wǎng)絡(luò)Gi+1的特征.同時為了更好地利用細粒度網(wǎng)絡(luò)的結(jié)構(gòu)信息，對于每一粒度的網(wǎng)絡(luò)，基于結(jié)構(gòu)信息利用網(wǎng)絡(luò)的拉普拉斯矩陣定義廣義位置嵌入矩陣[26]Xi.具體地，先對歸一化的圖拉普拉斯矩陣L進行特征分解：

L=D-A=I-D-1/2AD-1/2=UΛUT

(5)

其中D表示網(wǎng)絡(luò)的度矩陣，Λ是n個特征值構(gòu)成的對角矩陣，U表示對應(yīng)的特征向量，取U中前top-k的特征向量的值定義為廣義的位置嵌入矩陣Xi.

(6)

然后，為了進一步優(yōu)化Zi，引入譜卷積模型[27]來更新節(jié)點的表示.該模型利用改進的馬爾可夫擴散核，通過捕獲每個節(jié)點的局部和全局上下文信息，可以聚合節(jié)點高階鄰域的特征.具體原理如下：

(7)

(8)

基于上述的計算步驟，可以推導(dǎo)出不同粒度的網(wǎng)絡(luò)表示，最終得到保留網(wǎng)絡(luò)多粒度特征的原始網(wǎng)絡(luò)的節(jié)點表示Z0.

為了避免在每一粒度網(wǎng)絡(luò)上重新訓(xùn)練模型，同時更好地得到模型的初始化參數(shù).本文僅利用最粗粒度網(wǎng)絡(luò)Gk的信息來訓(xùn)練譜卷積模型，通過定義均方誤差損失訓(xùn)練模型：

Zk=Emd(Gk)

(9)

(10)

其中Emd(·)的選擇是靈活的，可以選擇現(xiàn)有的基于結(jié)構(gòu)的網(wǎng)絡(luò)表示學(xué)習(xí)方法.由于最粗粒度節(jié)點和最細粒度節(jié)點之間的 關(guān)系，Zk可以作為原始網(wǎng)絡(luò)中節(jié)點的近似表示，并作為細化過程的初始值.因此，在細化過程中將最粗粒度得到的節(jié)點表示作為標(biāo)簽訓(xùn)練譜卷積模型.在不同粒度網(wǎng)絡(luò)的細化過程中，使用參數(shù)共享的思想，僅利用在最粗粒度網(wǎng)絡(luò)上訓(xùn)練好的模型來更新節(jié)點表示，不再單獨訓(xùn)練模型，此時每兩個粒度間信息的轉(zhuǎn)換只需要利用簡單的矩陣相乘就可以實現(xiàn)，減少了模型訓(xùn)練的時間.同時相較于隨機初始化參數(shù)的方法，該方法可以得到更好地初始化參數(shù).NRAM的具體實現(xiàn)過程如算法1所示.

算法1.NRAM

輸入：原始網(wǎng)絡(luò)G；?；瘜訑?shù)k；節(jié)點嵌入的維度d；網(wǎng)絡(luò)粗化方法Coarsen(·)；任意的網(wǎng)絡(luò)表示學(xué)習(xí)方法Emd(·)；譜卷積模型H(A，X)

輸出：G的節(jié)點表示Z0∈Rn×d

1.for i=0，…，k-1 do

2.Gi+1←Coarsen(Gi)

3.End

4.Zk=Emd(Gk)

7.for j=k-1，…，0 do

8.Project(Zj+1，Gj)=Mj，j+1×Zj+1

10.Zj=Project(Zj+1，Gj)⊕Xj

11.Zj=H(Aj，Zj)

12.End

13.ReturnZ0

算法1中，第1-3行利用網(wǎng)絡(luò)粗化方法得到多粒度網(wǎng)絡(luò)，第4-6行通過利用最粗粒度網(wǎng)絡(luò)的表示訓(xùn)練譜卷積模型.第8-10行在繼承粗粒度節(jié)點信息的同時，進一步融合細粒度網(wǎng)絡(luò)的結(jié)構(gòu)信息得到細粒度網(wǎng)絡(luò)的初始嵌入.第11行通過聚合節(jié)點的高階鄰域信息更新細粒度網(wǎng)絡(luò)的節(jié)點表示.逐層細化，最終得到原始網(wǎng)絡(luò)的節(jié)點表示.

5 實驗分析

5.1 數(shù)據(jù)集

為了驗證NRAM的有效性，本文在3個公共數(shù)據(jù)集上進行實驗，數(shù)據(jù)集的具體信息如表1所示.

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

Cora[28]是由2708篇與機器學(xué)習(xí)相關(guān)的論文和其之間的引用關(guān)系構(gòu)成的引文網(wǎng)絡(luò)，每篇論文根據(jù)其所屬的研究領(lǐng)域被分為7個類別.

DBLP[29]是由13404篇論文和其引用關(guān)系構(gòu)成的引文網(wǎng)絡(luò)，包含39861條邊，每篇論文根據(jù)其不同的研究領(lǐng)域可以被劃分成4個類別.

Pubmed[28]是醫(yī)學(xué)數(shù)據(jù)庫中一組與糖尿病相關(guān)的文章構(gòu)成的引文網(wǎng)絡(luò)，每篇論文根據(jù)其所屬的糖尿病類型可以被劃分成3個類別.

5.2 對比算法

為驗證NRAM算法的有效性，本文選取了具有代表性的網(wǎng)絡(luò)表示學(xué)習(xí)方法作為基線方法.主要分為以下3類：

1)單粒度網(wǎng)絡(luò)表示學(xué)習(xí)方法

DeepWalk[1]利用隨機游走策略生成節(jié)點序列，并利用Word2vec學(xué)習(xí)節(jié)點的表示向量.

GraRep[12]通過矩陣分解的方法學(xué)習(xí)節(jié)點的k階關(guān)系表示以生成節(jié)點的潛在表示.

ProNE[5]通過稀疏矩陣分解有效地初始化網(wǎng)絡(luò)表示，并在譜空間中傳播表示，以獲得增強的節(jié)點表示.

HuGE[3]是一種熵驅(qū)動的網(wǎng)絡(luò)嵌入方法，利用混合屬性啟發(fā)式隨機游走來捕獲節(jié)點特征.

2)基于拼接的細化方法的多粒度網(wǎng)絡(luò)表示學(xué)習(xí)方法

HSRL[18]采用社團壓縮的方法構(gòu)建網(wǎng)絡(luò)的多粒度結(jié)構(gòu)，學(xué)習(xí)不同粒度網(wǎng)絡(luò)的節(jié)點表示，通過拼接的操作以得到網(wǎng)絡(luò)的潛在節(jié)點表示.

ACE[19]采用基于蟻群算法的粗化方法，構(gòu)建多粒度網(wǎng)絡(luò)，并將不同粒度的網(wǎng)絡(luò)表示拼接起來并降維得到最終的表示向量.

LouvainNE[20]通過構(gòu)建層次樹的方法保留網(wǎng)絡(luò)的多粒度結(jié)構(gòu)，將不同粒度上獲得的單個節(jié)點表示拼接以學(xué)習(xí)最終的嵌入向量.

3)基于繼承的細化方法的多粒度網(wǎng)絡(luò)表示學(xué)習(xí)方法

HARP[21]遞歸地使用兩種坍塌方案，邊坍塌和星坍塌，將輸入網(wǎng)絡(luò)粗化成一系列小網(wǎng)絡(luò).從最粗粒度網(wǎng)絡(luò)開始，將粗粒度網(wǎng)絡(luò)學(xué)到的表示作為細粒度網(wǎng)絡(luò)的初始化，迭代的得到原始網(wǎng)絡(luò)的表示.

MILE[24]使用混合匹配技術(shù)反復(fù)地將圖合并成更小的圖，并利用GCN[7]方法將最粗粒度學(xué)到的節(jié)點表示細化回原始網(wǎng)絡(luò).

5.3 參數(shù)設(shè)置與評價標(biāo)準(zhǔn)

本文所涉及實驗方法的嵌入維度統(tǒng)一設(shè)置為128維.同時為了保證實驗的公平性，對于對比算法中的多粒度表示學(xué)習(xí)方法，統(tǒng)一采用DeepWalk[1]方法作為最粗粒度網(wǎng)絡(luò)的基本嵌入方法.對比算法中其它的相關(guān)參數(shù)設(shè)置依據(jù)相應(yīng)論文中設(shè)置的值.為評估學(xué)到的節(jié)點表示的質(zhì)量，本文使用節(jié)點分類作為下游任務(wù)，使用Micro-F1(Mi-F1)，Macro-F1(Ma-F1)作為評價指標(biāo).其定義如下：

(11)

(12)

其中TP、FP、FN分別表示真正例、假正例、假反例.N表示標(biāo)簽的類別數(shù).Micro_F1可看做N個不同類別F1值的加權(quán)平均值，Macro_F1是所有類別F1值的算術(shù)平均值.

5.4 實驗結(jié)果

為驗證NRAM方法的有效性，本文使用節(jié)點分類作為下游任務(wù)評估網(wǎng)絡(luò)表示學(xué)習(xí)質(zhì)量.與之前的研究相似，本文使用Micro_F1和Macro_F1作為衡量節(jié)點分類性能指標(biāo).隨機抽取不同訓(xùn)練率的標(biāo)記樣本用來訓(xùn)練SVM分類器，其余節(jié)點用于測試.每個實驗獨立執(zhí)行10次，實驗結(jié)果如表2-表4所示，其中k表示網(wǎng)絡(luò)粗化的層數(shù)，由于空間限制，對于多粒度網(wǎng)絡(luò)表示學(xué)習(xí)方法僅顯示粗化層數(shù)為1、2、3時的結(jié)果. 同時由于HARP[21]、ACE[19]、LouvainNE[20]等方法直接采用閾值來設(shè)置粗化終點，其粗化層數(shù)不可控制，因此對于該方法，僅顯示最終的表示向量；HSRL[18]是基于拼接的方法，因此為保證嵌入維度相同，僅顯示粗化層數(shù)為1、3時結(jié)果.每列中的最好的結(jié)果用粗體突出顯示.從表2-表4中，可以得到以下結(jié)論：

表2 Cora數(shù)據(jù)集上節(jié)點分類的結(jié)果

表3 DBLP數(shù)據(jù)集上節(jié)點分類的結(jié)果

表4 Pubmed數(shù)據(jù)集上節(jié)點分類的結(jié)果

首先，從表2-表4中可以觀察到相對于HuGE[3]等單粒度的網(wǎng)絡(luò)表示學(xué)習(xí)方法相比，NRAM方法其節(jié)點分類的結(jié)果有明顯的提高，進一步證明了保留網(wǎng)絡(luò)的多粒度信息對于節(jié)點表示的重要性，同時也可以反映出本文的方法可以更好地捕獲網(wǎng)絡(luò)的多粒度結(jié)構(gòu).其次，相較于多粒度網(wǎng)絡(luò)表示的方法，NRAM的效果也有提升.HARP使用邊坍塌和星坍塌的粗化方法，屬于不同社區(qū)的節(jié)點可能會被合并，不利于細化過程中得到的初始嵌入.LouvainNE的方法使用隨機嵌入的方法學(xué)習(xí)節(jié)點表示，在減少學(xué)習(xí)時間的同時損失了節(jié)點表示的質(zhì)量.與MILE[24]相比，NRAM在逐層細化時可以聚合高階鄰域的信息，同時利用了細粒度網(wǎng)絡(luò)的結(jié)構(gòu)信息.雖然與HSRL[21]相比，在測試集比率為70%和90%上Cora數(shù)據(jù)集的結(jié)果差于HSRL的結(jié)果，但相較與HSRL需要學(xué)習(xí)每一粒度的節(jié)點表示相比，NRAM僅在最粗層學(xué)習(xí)節(jié)點的表示向量，所需的時間開銷小.

5.5 消融分析

本節(jié)將進行消融實驗來驗證NRAM的細化方法的有效性.本文設(shè)計了NRAM方法的3種變體方法，僅改變NRAM的細化方法，即NRAM-gcn，NRAM-contate和NRAM-nox.NRAM-gcn方法在細化過程中使用GCN替代譜卷積模型，同時在逐層細化時，不拼接廣義的位置嵌入矩陣.NRAM-contate方法直接使用拼接的方法進行網(wǎng)絡(luò)細化，學(xué)習(xí)每一粒度網(wǎng)絡(luò)的節(jié)點表示并拼接得到最終的表示向量.NRAM-nox在細化過程中去掉每層拼接的廣義位置嵌入矩陣.為了比較的公平性，使用Deepwalk分別學(xué)習(xí)NRAM-nox、NRAM-gcn最粗粒度和NRAM-contate中每一粒度網(wǎng)絡(luò)的節(jié)點表示.表5和表6展現(xiàn)了粗化層數(shù)為3，訓(xùn)練率分別為10%，30%和50%時節(jié)點分類任務(wù)上的性能.從表5和表6中可以看到，相較于NRAM-gcn直接使用GCN模型更新節(jié)點的表示，NRAM細化方法的效果更好，NRAM在細化更新節(jié)點表示時，保留了細粒度網(wǎng)絡(luò)的高階信息，并且相較于傳統(tǒng)的GNN方法，僅在聚合節(jié)點信息時利用網(wǎng)絡(luò)的局部鄰域信息來確定聚合的鄰居節(jié)點.本文利用拉普拉斯矩陣的特征值定義廣義的位置嵌入矩陣進一步考慮了細粒度網(wǎng)絡(luò)的結(jié)構(gòu)信息.同時，相較于NRAM-contate采用直接拼接的方法得到網(wǎng)絡(luò)表示，NRAM的細化方法的效果更好，采用拼接的方法隨著網(wǎng)絡(luò)粗化層數(shù)的增多會造成信息的冗余而降低節(jié)點表示的質(zhì)量.

表5 NRAM和其變體方法的Micro-F1值

表6 NRAM和其變體方法的Macro-F1值

5.6 靈活性

本節(jié)將通過實驗展示NRAM方法的靈活性，即在最粗的粒度網(wǎng)絡(luò)上可以使用任何現(xiàn)有的基于結(jié)構(gòu)的網(wǎng)絡(luò)表示學(xué)習(xí)方法學(xué)習(xí)潛在的節(jié)點表示.這里選擇兩種網(wǎng)絡(luò)表示學(xué)習(xí)方法GraRep[12]和ProNE[5]，如圖3總結(jié)了訓(xùn)練率為20%時，在最粗粒度網(wǎng)絡(luò)上采用不同網(wǎng)絡(luò)表示學(xué)習(xí)方法的NRAM和原始網(wǎng)絡(luò)表示學(xué)習(xí)方法的性能，本文選擇GraRep和ProNE兩種方法.在其他訓(xùn)練比率下，結(jié)果是相似的.從圖3中可以看出，相較于原始的單粒度網(wǎng)絡(luò)表示學(xué)習(xí)方法，NARM在3個數(shù)據(jù)集的節(jié)點分類任務(wù)上獲得更高的Micro_F1和Macro_F1分數(shù)，這表明NARM可以更有效地保留網(wǎng)絡(luò)的結(jié)構(gòu)信息.

圖3 NRAM在最粗粒度網(wǎng)絡(luò)上使用不同網(wǎng)絡(luò)嵌入方法的節(jié)點分類性能

6 結(jié) 論

網(wǎng)絡(luò)表示學(xué)習(xí)對網(wǎng)絡(luò)分析有著重要作用，如何更好地挖掘和保留網(wǎng)絡(luò)的多粒度特征在現(xiàn)實生活中有著重要價值.本文基于聚合多階鄰居信息的細化方法提出一種多粒度網(wǎng)絡(luò)學(xué)習(xí)方法.對于粗化后的多粒度網(wǎng)絡(luò)，從最粗粒度網(wǎng)絡(luò)開始，通過將粗粒度網(wǎng)絡(luò)的表示投影到細粒度網(wǎng)絡(luò)，并融合細粒度網(wǎng)絡(luò)的結(jié)構(gòu)信息得到細粒度網(wǎng)絡(luò)的初始嵌入值；再利用節(jié)點的高階鄰域信息去更新細粒度網(wǎng)絡(luò)的表示，逐層的將粗粒度空間的節(jié)點表示細化回原始網(wǎng)絡(luò)，得到原始網(wǎng)絡(luò)的節(jié)點向量.在3個公共數(shù)據(jù)集上節(jié)點分類的結(jié)果驗證了NARM的有效性.