基于聚合多階鄰域信息的細(xì)化方法的多粒度網(wǎng)絡(luò)表示學(xué)習(xí)

趙 姝，劉夢(mèng)婷，杜紫維，宋文超，韓光潔

1(計(jì)算智能與信號(hào)處理教育部重點(diǎn)實(shí)驗(yàn)室，合肥 230601)

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

3(安徽省信息材料與智能傳感重點(diǎn)實(shí)驗(yàn)室，合肥 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ú)處不在.如何挖掘隱藏在網(wǎng)絡(luò)中的信息有著重要價(jià)值.近年來(lái)，網(wǎng)絡(luò)表示學(xué)習(xí)作為網(wǎng)絡(luò)分析的一種方法，受到極大的關(guān)注.網(wǎng)絡(luò)表示學(xué)習(xí)，又稱網(wǎng)絡(luò)嵌入，旨在將網(wǎng)絡(luò)中的節(jié)點(diǎn)映射成低維稠密的向量，同時(shí)保留網(wǎng)絡(luò)的固有特征.學(xué)到的節(jié)點(diǎn)表示可以作為機(jī)器學(xué)習(xí)算法的輸入，用于處理社區(qū)發(fā)現(xiàn)、節(jié)點(diǎn)分類、鏈路預(yù)測(cè)等下游任務(wù)，對(duì)挖掘網(wǎng)絡(luò)的潛在信息有著重要作用.

為獲得有效的節(jié)點(diǎn)表示，研究者們已提出各種網(wǎng)絡(luò)表示學(xué)習(xí)方法.DeepWalk[1]、Node2vec[2]將隨機(jī)游走和淺層神經(jīng)網(wǎng)絡(luò)相結(jié)合得到節(jié)點(diǎn)向量.HuGE[3]利用混合屬性啟發(fā)式隨機(jī)游走捕獲節(jié)點(diǎn)特征.NetMF[4]、ProNE[5]、eNetMF[6]基于矩陣分解的技術(shù)得到表示向量.隨著圖神經(jīng)網(wǎng)絡(luò)的發(fā)展，GCN[7]、MAGCN[8]等基于深度學(xué)習(xí)的方法被提出，這類方法通過(guò)半監(jiān)督的方式學(xué)習(xí)節(jié)點(diǎn)表示，在訓(xùn)練過(guò)程中需要利用標(biāo)簽信息.雖然上述方法已經(jīng)取得了不錯(cuò)的效果，但是它們只考慮了單一粒度下網(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ò)的特性，而受到越來(lái)越多的關(guān)注.它們利用一種統(tǒng)一的框架得到節(jié)點(diǎn)表示.具體地，主要經(jīng)過(guò)網(wǎng)絡(luò)粗化和網(wǎng)絡(luò)細(xì)化兩個(gè)階段.網(wǎng)絡(luò)粗化階段，通過(guò)設(shè)計(jì)節(jié)點(diǎn)合并策略，將網(wǎng)絡(luò)中具有相似特征(一階相似性、二階相似性、社團(tuán)結(jié)構(gòu))的節(jié)點(diǎn)合并生成超點(diǎn)，構(gòu)成粗粒度網(wǎng)絡(luò).通過(guò)粗化階段可以縮小原始網(wǎng)絡(luò)的規(guī)模，同時(shí)，由于粗粒度節(jié)點(diǎn)與細(xì)粒度節(jié)點(diǎn)之間的對(duì)應(yīng)關(guān)系，可以將粗粒度網(wǎng)絡(luò)的表示作為原始網(wǎng)絡(luò)的近似表示.迭代粗化過(guò)程還可以獲得網(wǎng)絡(luò)的多粒度結(jié)構(gòu).

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

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

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

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

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

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

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

2 相關(guān)工作

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

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

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

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

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

3 問(wèn)題定義

下面給出本文所提問(wèn)題的定義及使用的符號(hào)定義.

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

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

定義3.網(wǎng)絡(luò)粗化.給定網(wǎng)絡(luò)G=(V，E，A)，令G0=G，通過(guò)定義網(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é)點(diǎn)合并成超點(diǎn)，構(gòu)造出規(guī)模逐漸減小的多粒度網(wǎng)絡(luò)G0，G1，…，Gk.

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

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

4 算法描述

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

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

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

(1)

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

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

(2)

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

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

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

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

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

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

(3)

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

(4)

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

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

(5)

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

(6)

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

(7)

(8)

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

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

Zk=Emd(Gk)

(9)

(10)

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

算法1.NRAM

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

輸出：G的節(jié)點(diǎn)表示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行通過(guò)利用最粗粒度網(wǎng)絡(luò)的表示訓(xùn)練譜卷積模型.第8-10行在繼承粗粒度節(jié)點(diǎn)信息的同時(shí)，進(jìn)一步融合細(xì)粒度網(wǎng)絡(luò)的結(jié)構(gòu)信息得到細(xì)粒度網(wǎng)絡(luò)的初始嵌入.第11行通過(guò)聚合節(jié)點(diǎn)的高階鄰域信息更新細(xì)粒度網(wǎng)絡(luò)的節(jié)點(diǎn)表示.逐層細(xì)化，最終得到原始網(wǎng)絡(luò)的節(jié)點(diǎn)表示.

5 實(shí)驗(yàn)分析

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

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

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

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

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

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

5.2 對(duì)比算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(11)

(12)

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

5.4 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

5.5 消融分析

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

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

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

5.6 靈活性

本節(jié)將通過(guò)實(shí)驗(yàn)展示NRAM方法的靈活性，即在最粗的粒度網(wǎng)絡(luò)上可以使用任何現(xiàn)有的基于結(jié)構(gòu)的網(wǎng)絡(luò)表示學(xué)習(xí)方法學(xué)習(xí)潛在的節(jié)點(diǎn)表示.這里選擇兩種網(wǎng)絡(luò)表示學(xué)習(xí)方法GraRep[12]和ProNE[5]，如圖3總結(jié)了訓(xùn)練率為20%時(shí)，在最粗粒度網(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個(gè)數(shù)據(jù)集的節(jié)點(diǎn)分類任務(wù)上獲得更高的Micro_F1和Macro_F1分?jǐn)?shù)，這表明NARM可以更有效地保留網(wǎng)絡(luò)的結(jié)構(gòu)信息.

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

6 結(jié) 論

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