胡 軍，許正康，劉立，鐘福金

（1.計算智能重慶市重點實驗室（重慶郵電大學），重慶 400065；2.重慶郵電大學計算機科學與技術(shù)學院，重慶 400065）

0 引言

現(xiàn)實生活中存在各種各樣的網(wǎng)絡，如社交網(wǎng)絡、引文網(wǎng)絡、蛋白質(zhì)網(wǎng)絡等。為了挖掘這些網(wǎng)絡中的隱含信息，許多與復雜網(wǎng)絡分析相關(guān)的算法被提出。由于網(wǎng)絡數(shù)據(jù)屬于非歐幾里得類型，無法直接被較為成熟的機器學習算法進行處理，極大地阻礙了網(wǎng)絡分析技術(shù)的發(fā)展。網(wǎng)絡表示學習［1-2］通過將網(wǎng)絡映射到低維特征空間中，從而可直接運用現(xiàn)有的機器學習算法對網(wǎng)絡進行分析處理，是一種有效的對網(wǎng)絡數(shù)據(jù)進行預處理的方法，已被應用到多個領(lǐng)域。近年來，在對網(wǎng)絡表示的研究中，除了神經(jīng)網(wǎng)絡的方法［3-4］和基于矩陣分解的方法［5-6］外，基于Skip-gram 模型的網(wǎng)絡表示方法也取得了較為不錯的效果。它們使用隨機游走（DeepWalk［7］、node2vec［8］）或一階、二階近似（LINE（Large-scale Information Network Embedding）［9］）可以很好地捕獲網(wǎng)絡中的局部結(jié)構(gòu)信息，但忽略了一些隱含的全局信息，比如網(wǎng)絡的社區(qū)信息。

為了將網(wǎng)絡社區(qū)信息融合進節(jié)點表示中，一些學者提出了多種融合社區(qū)信息的網(wǎng)絡表示方法［10-14］。這些方法的基本思想大都利用網(wǎng)絡表示方法得到節(jié)點嵌入，使用聚類算法或社區(qū)發(fā)現(xiàn)算法獲得網(wǎng)絡的社區(qū)結(jié)構(gòu)，再根據(jù)社區(qū)結(jié)構(gòu)來更新節(jié)點嵌入。處理過程如圖1 所示，首先將社區(qū)劃分和節(jié)點嵌入整合得到每個社區(qū)的社區(qū)嵌入（三角和正方形節(jié)點），可視為虛擬社區(qū)中心節(jié)點，類似于節(jié)點嵌入，將社區(qū)嵌入定義為與節(jié)點嵌入有相同維度的向量形式；然后根據(jù)社區(qū)嵌入調(diào)整社區(qū)內(nèi)節(jié)點的嵌入向量，使得原網(wǎng)絡中有相同結(jié)構(gòu)的節(jié)點在嵌入中相似的同時，在同一社區(qū)內(nèi)的節(jié)點嵌入也表現(xiàn)為相似，即使這些節(jié)點沒有直接聯(lián)系。

圖1 融合社區(qū)信息的網(wǎng)絡表示Fig.1 Network representation by fusing community information

對于一個網(wǎng)絡，根據(jù)不同的劃分標準，可以得到不同的網(wǎng)絡社區(qū)結(jié)構(gòu)，并且網(wǎng)絡的社區(qū)劃分具有層次結(jié)構(gòu)，即多粒度特性［15-16］。比如在校園社交網(wǎng)絡中，如果按科系進行劃分，可以形成多個不同的科系社團，但如果按學院來劃分，多個科系就可以合并成一個學院社團，可見，不同的社團劃分蘊含了網(wǎng)絡不同粒度下的社區(qū)結(jié)構(gòu)；然而，現(xiàn)有融合社區(qū)信息的網(wǎng)絡表示方法大都只考慮單個粒度下的社團結(jié)構(gòu)，損失了其他粒度下的社團結(jié)構(gòu)信息。因此，在融合社區(qū)信息時有必要結(jié)合社區(qū)本身具有的多粒度特性，設計新的網(wǎng)絡表示方法，保留更多原始網(wǎng)絡中的信息（如圖2 所示）。

圖2 多粒度網(wǎng)絡表示Fig.2 Multi-granularity network representation

基于這一想法，本文提出了一種融合多粒度社區(qū)信息的網(wǎng)絡表示方法（network Embedding based on Multi-Granularity Community information，EMGC）。本文的主要工作包括：

1）提出了一種社區(qū)嵌入的更新方法，將傳統(tǒng)的社區(qū)發(fā)現(xiàn)算法和網(wǎng)絡嵌入方法融合，得到不同粒度下的社區(qū)嵌入結(jié)果。

2）在不同社區(qū)粒度的網(wǎng)絡中，將節(jié)點嵌入和社區(qū)嵌入進行優(yōu)化，得到了融合相應粒度社區(qū)信息的網(wǎng)絡嵌入結(jié)果。

3）在4 個真實網(wǎng)絡數(shù)據(jù)集上的實驗結(jié)果顯示本文方法較其他對比方法能提升鏈接預測和節(jié)點分類等下游任務的準確率。

1 相關(guān)工作

網(wǎng)絡表示學習近年來受到越來越多的關(guān)注，產(chǎn)生了許多相關(guān)方法。這些方法一般可以分為基于矩陣分解的網(wǎng)絡表示方法［5-6］、基于神經(jīng)網(wǎng)絡的表示方法［17-20］以及基于Skipgram 模型的網(wǎng)絡表示方法三種。在基于Skip-gram 模型的網(wǎng)絡表示方法中，DeepWalk［7］最早將自然語言處理領(lǐng)域的詞嵌入Word2Vec［21-22］中的思想引入到網(wǎng)絡表示中，使用無偏隨機游走得到節(jié)點序列，這些節(jié)點序列保留了網(wǎng)絡的結(jié)構(gòu)信息，通過Skip-gram 模型來訓練這些節(jié)點序列，最終得到網(wǎng)絡的嵌入表示；node2vec［8］在DeepWalk 的基礎上使用深度優(yōu)先和廣度優(yōu)先的搜索策略來控制隨機游走，根據(jù)游走參數(shù)的不同，所得的節(jié)點序列蘊涵了網(wǎng)絡的低階和高階結(jié)構(gòu)信息；LINE［9］可以使得網(wǎng)絡表示結(jié)果的同時保留網(wǎng)絡節(jié)點的一階近似和二階近似信息。但這些方法都只考慮了網(wǎng)絡的局部信息，忽視了全局信息。

由于網(wǎng)絡中社區(qū)的重要性，一些學者開始考慮在網(wǎng)絡表示時對社區(qū)信息進行保留。ComE（Community Embedding）［10］假設社區(qū)內(nèi)的節(jié)點嵌入服從混合高斯分布，可以同時得到保留社區(qū)信息并符合高斯分布的節(jié)點嵌入結(jié)果；GEMSEC（Graph EMbedding with SElf Clustering）［11］能在學習節(jié)點嵌入的同時進行節(jié)點的聚類，最后獲得保留類簇信息的嵌入以及高質(zhì)量的聚類結(jié)果；CARE（Community Aware Random walk for network Embedding）［12］使用自定義隨機游走，將社區(qū)內(nèi)的節(jié)點按照一定概率插入到游走序列中，所得到的游走序列包含網(wǎng)絡的局部結(jié)構(gòu)信息和社區(qū)信息，再使用Skip-gram 模型得到最終的網(wǎng)絡表示；CARA（Community Aware and Relational Attention）［13］在CARE 的基礎上，使用圖卷積網(wǎng)絡（Graph Convolutional Network，GCN）［18］和注意力機制［19］捕獲節(jié)點之間的語義信息；CNRL（Community-enhanced Network Representation Learning）［14］從概率推斷的角度出發(fā)，對節(jié)點嵌入和社區(qū)嵌入聯(lián)合優(yōu)化，得到最終的節(jié)點嵌入、社區(qū)嵌入以及社區(qū)劃分結(jié)果。但上述方法都只關(guān)注網(wǎng)絡在某一個粒度層次的社區(qū)結(jié)構(gòu)，沒有考慮到社區(qū)的多粒度性質(zhì)，損失了其他粒度層次所蘊含的社區(qū)結(jié)構(gòu)信息。為此，有必要研究一種可以融合網(wǎng)絡多粒度社區(qū)信息的表示方法。

2 融合多粒度社區(qū)信息的網(wǎng)絡嵌入方法

2.1 定義

定義1網(wǎng)絡。給定一個網(wǎng)絡G(V，E，WV，WE)，其中V={v1，v2，…，vn}是網(wǎng)絡G的節(jié)點集合，E={eij}是網(wǎng)絡G的邊集，eij代表節(jié)點vi和vj所形成的邊，m=|E|，WV=[wv1，wv2，…，wvn]，WV∈Rn和WE=[weij]，WE∈Rn×n分別代表網(wǎng)絡節(jié)點權(quán)重矩陣和邊權(quán)重矩陣。對于無權(quán)網(wǎng)絡，可將網(wǎng)絡節(jié)點權(quán)重和邊權(quán)重設為1。

根據(jù)不同的社區(qū)劃分標準，網(wǎng)絡中的節(jié)點可以劃分為不同粒度的社區(qū)結(jié)構(gòu)。對于網(wǎng)絡的一個社區(qū)劃分C={c1，c2，…，c|C|}，網(wǎng)絡中的一個節(jié)點vi∈V，有社區(qū)分配函數(shù)z(vi)→C。

定義2多粒度社區(qū)。假設網(wǎng)絡G可以劃分成τ種不同粒度的社區(qū)結(jié)構(gòu)，在t粒度下，網(wǎng)絡的社區(qū)劃分為Ct=，其中為t-1 粒度下的社區(qū)，并且在t粒度下，對于內(nèi)部節(jié)點v都有zt(v)=。

定義3節(jié)點嵌入。在不同社區(qū)粒度下，對于網(wǎng)絡G中任意節(jié)點vi∈V都有相應的節(jié)點嵌入∈Rd，t為當前社區(qū)粒度，d為網(wǎng)絡嵌入的維度。

定義4社區(qū)嵌入。在不同社區(qū)粒度下，對于網(wǎng)絡G中任意社區(qū)∈Ct都有相應的社區(qū)嵌入∈Rd，t為當前社區(qū)粒度，d為網(wǎng)絡嵌入的維度。

2.2 節(jié)點嵌入

為了將網(wǎng)絡結(jié)構(gòu)信息融入節(jié)點嵌入，本文使用DeepWalk［7］來學習節(jié)點嵌入。DeepWalk 使用截斷隨機游走來捕獲網(wǎng)絡結(jié)構(gòu)信息，得到游走路徑集合S={s1，s2，…，sn}，其中si={vi，…}表示以節(jié)點vi為起始節(jié)點的節(jié)點序列。對于節(jié)點序列si中任意節(jié)點，根據(jù)窗口大小生成中心-上下文節(jié)點對，并通過節(jié)點嵌入來刻畫中心節(jié)點和上下文節(jié)點之間的關(guān)系。對于節(jié)點對(vi，vj)，其中心節(jié)點vi預測上下文節(jié)點vj的條件概率為：

其中：vj是vi的上下文節(jié)點，?i、?′j分別代表節(jié)點vi的嵌入以及節(jié)點vj的上下文嵌入。

根據(jù)Skip-gram 模型，DeepWalk 通過最大化中心節(jié)點預測上下文節(jié)點的條件概率，更新中心節(jié)點的嵌入。為了降低計算式（1）的復雜度，可以使用負采樣策略將式（1）修改成如下的目標函數(shù)［21-22］：

其中：σ(x)=1/(1+exp(-x))，K為負采樣的個數(shù)，Pn(v)為負采樣的概率分布，通常Pn(v) ∝，dv為節(jié)點v的度數(shù)。

2.3 社區(qū)嵌入

為了確保網(wǎng)絡嵌入能夠保留網(wǎng)絡的社區(qū)信息，本文根據(jù)所得到的網(wǎng)絡社區(qū)結(jié)構(gòu)來計算相應的網(wǎng)絡社區(qū)嵌入。

2.3.1 社區(qū)發(fā)現(xiàn)

本文使用Louvain 算法［23］對網(wǎng)絡進行劃分，以此獲得網(wǎng)絡的多粒度社區(qū)結(jié)構(gòu)。Louvain 是一種基于模塊度優(yōu)化的社區(qū)發(fā)現(xiàn)算法，通過最大化模塊度來找到最優(yōu)的社區(qū)結(jié)構(gòu)，模塊度的定義如下：

其中：m為網(wǎng)絡中的總邊數(shù)，weij為節(jié)點vi和vj之間的邊權(quán)重，ki為節(jié)點vi鄰接邊權(quán)重總和，z(vi)為節(jié)點vi所在的社區(qū)，δ為Kronecker delta 函數(shù)。

依據(jù)式（3），將節(jié)點vi劃分到社區(qū)c所產(chǎn)生的模塊度增益如下：

其中：Σin為社區(qū)c內(nèi)部邊權(quán)總和，Σtot為與社區(qū)c有連接的邊權(quán)總和，ki，in為節(jié)點vi與社區(qū)c內(nèi)節(jié)點所連接邊權(quán)總和。Louvain 算法通過遍歷網(wǎng)絡中所有節(jié)點，計算將節(jié)點劃分到其鄰居所在社區(qū)的模塊度增益，并將其劃分到最大正向增益的對應社區(qū)。

對于網(wǎng)絡G(V，E，WV，WE)，根據(jù)Louvain 算法首先得到網(wǎng)絡的一個社區(qū)劃分，其為原網(wǎng)絡最細粒度的社區(qū)結(jié)構(gòu)。根據(jù)得到的社區(qū)結(jié)構(gòu)構(gòu)造一個新的網(wǎng)絡，并對新網(wǎng)絡進行社區(qū)劃分，從而進一步得到更粗粒度的社區(qū)結(jié)構(gòu)。對于t-1 粒度下的網(wǎng)絡，可以根據(jù)其社區(qū)劃分Ct-1構(gòu)建t粒度下的新網(wǎng)絡，即將網(wǎng)絡Gt-1中所有同一社區(qū)內(nèi)的節(jié)點合并得到Gt中的一個節(jié)點，網(wǎng)絡Gt-1中社區(qū)間若存在邊，則在Gt對應節(jié)點間則構(gòu)建一條邊，同時將Gt中節(jié)點內(nèi)部權(quán)重設置為合并節(jié)點集合內(nèi)部權(quán)重的總和，即對于節(jié)點∈Vt，其權(quán)重為：

對于新得到的網(wǎng)絡，按照之前的步驟可以得到新網(wǎng)絡的社區(qū)劃分。依此類推，直到模塊度不再發(fā)生改變，可以得到原網(wǎng)絡多個粒度下的社區(qū)結(jié)構(gòu)。

2.3.2 嵌入更新

對于網(wǎng)絡中的一個社區(qū)ci，將社區(qū)內(nèi)的所有節(jié)點的嵌入進行平均，即得到相應的社區(qū)嵌入ψi，其計算公式如下：

其中：?j是節(jié)點vj的嵌入，|ci|為社區(qū)ci的內(nèi)部節(jié)點數(shù)。

2.4 聯(lián)合優(yōu)化

在得到節(jié)點嵌入和社區(qū)嵌入后，本文利用社區(qū)嵌入來調(diào)整節(jié)點嵌入，使得調(diào)整后的節(jié)點嵌入可以保留網(wǎng)絡的社區(qū)信息?；诠?jié)點與其所屬社區(qū)的關(guān)系，節(jié)點的嵌入與其所屬社區(qū)的嵌入在向量空間中應該相近。因此，可以通過計算節(jié)點與對應的社區(qū)之間的條件概率，將社區(qū)信息融合進節(jié)點嵌入當中：

其中cj是vi所屬的社區(qū)，即z(vi)=cj。

對于采樣網(wǎng)絡中的節(jié)點vi，通過z(?)找到其所屬社區(qū)cj，得到樣本(vi，cj)進行訓練。類似地，可以通過負采樣優(yōu)化策略來降低復雜度，其聯(lián)合優(yōu)化的目標函數(shù)為：

國家推行總額預付制的醫(yī)保改革政策，其目的是為了倒逼醫(yī)院規(guī)范醫(yī)療行為，控制醫(yī)療費用。現(xiàn)階段，大部分醫(yī)院在醫(yī)?？刭M方面采用了分科定額控制管理方式，精細化程度不夠。在新的醫(yī)療改革大環(huán)境下，迫切需要醫(yī)院管理人員運用精細化管理的思維進行醫(yī)療費用的管控，在支持國家醫(yī)改政策的同時，謀求醫(yī)院自身的可持續(xù)發(fā)展。醫(yī)院應探索多種醫(yī)保費用管理手段，除了績效考核方法以外，探索單病種質(zhì)量管理及費用管控、臨床路徑管理等考核制度。

與節(jié)點嵌入不同，聯(lián)合優(yōu)化對社區(qū)進行負采樣，以此確保所采樣的社區(qū)不是節(jié)點vi所屬的社區(qū)。

對于一個節(jié)點vi，節(jié)點在粒度層次t的嵌入是?ti，則該節(jié)點嵌入?i為所有社區(qū)粒度下節(jié)點嵌入的拼接，即：

其中符號⊕為拼接運算。

本文方法框架如圖3 所示，首先通過Louvain 算法得到多粒度社區(qū)結(jié)構(gòu)；然后在不同的粒度下學習其社區(qū)嵌入，調(diào)整相應的節(jié)點嵌入，使之保留相應的社區(qū)信息；最后將融合不同粒度社區(qū)信息的節(jié)點嵌入拼接得到最終節(jié)點嵌入，相應的算法如算法1 所示。

圖3 融合多粒度社區(qū)信息網(wǎng)絡嵌入Fig.3 Network embedding based on multi-granularity community information

算法1 融合多粒度社區(qū)信息網(wǎng)絡嵌入方法（EMGC）。

輸入 網(wǎng)絡G(V，E，WV，WE)，嵌入維度d，節(jié)點游走次數(shù)λ，游走長度l，窗口大小w，負采樣個數(shù)nneg；

輸出 節(jié)點嵌入?。

算法的第1）行使用Louvain 算法對網(wǎng)絡進行社區(qū)發(fā)現(xiàn)，得到不同粒度下的社區(qū)結(jié)構(gòu)；2）～3）行對原始網(wǎng)絡進行隨機游走，并根據(jù)式（2）初始化節(jié)點嵌入向量；4）～8）行根據(jù)不同粒度的社區(qū)結(jié)構(gòu)迭代更新社區(qū)嵌入，聯(lián)合優(yōu)化節(jié)點嵌入向量。對于不同社區(qū)粒度下網(wǎng)絡Gt，第5）行根據(jù)Gt中的社區(qū)Ct和?t-1使用式（8）更新Gt的社區(qū)嵌入ψt；第6）行根據(jù)?t-1和ψt使用式（10）來聯(lián)合優(yōu)化當前粒度網(wǎng)絡的節(jié)點嵌入?t；第7）行使用式（11）拼接不同粒度下節(jié)點嵌入，得到最終的節(jié)點嵌入?。

Louvain 算法的時間復雜度接近于O(m+n)。對于節(jié)點嵌入部分，通過隨機游走進行節(jié)點嵌入，則該部分的時間復雜度為O(λ?l?n)。社區(qū)嵌入更新部分的時間復雜度與當前的社區(qū)數(shù)有關(guān)，算法執(zhí)行過程中社區(qū)數(shù)最大為n，也就是原始網(wǎng)絡節(jié)點數(shù)，所以社區(qū)嵌入更新部分的時間復雜度最大為O(n)。對于節(jié)點嵌入和社區(qū)嵌入的聯(lián)合優(yōu)化部分，只需要采樣節(jié)點進行訓練即可，則每次聯(lián)合優(yōu)化部分的復雜度為O(n)。因而算法1 的時間復雜度為O(m+n+λ?l?n+τ×(n+n))，線性接近O(m+n)。

3 實驗分析

為了驗證本文方法的有效性，本章分別在鏈接預測和節(jié)點分類任務上將本文方法與4 種典型的基于Skip-gram 模型的網(wǎng)絡表示方法進行了對比，分別是DeepWalk、node2vec、ComE 和GEMSEC，其中前2 種方法只考慮了網(wǎng)絡的結(jié)構(gòu)信息，后2 種方法同時考慮了網(wǎng)絡的結(jié)構(gòu)信息和社區(qū)信息。實驗中使用了4 個數(shù)據(jù)集，分別是Facebook［24］、Cora［25］、Wiki［26］和DBLP［10］。具體信息如表1 所示，包括網(wǎng)絡的規(guī)模（節(jié)點集|V|、邊集|E|）以及真實社區(qū)數(shù)|C|。

表1 數(shù)據(jù)集信息Tab.1 Dataset information

在實驗中，本文提出的EMGC 的參數(shù)設定為：節(jié)點游走次數(shù)λ=5，游走長度l=80，窗口大小w=10，另外負采樣個數(shù)nneg設置為10，為了避免拼接后嵌入向量維度過大，本文將嵌入維度d設置為16。node2vec 的參數(shù)p、q的取值范圍設定為｛0.25，0.5，1，2，4｝。ComE 和GEMSEC 的社區(qū)數(shù)都設置為相應數(shù)據(jù)集的真實標簽數(shù)。由于Facebook 沒有真實標簽，在這個數(shù)據(jù)集上的社區(qū)數(shù)設置為Louvain 算法發(fā)現(xiàn)的社區(qū)數(shù)。

3.1 鏈接預測結(jié)果分析

實驗中，首先刪除網(wǎng)絡中部分存在的邊，然后通過刪減后的網(wǎng)絡訓練模型得到網(wǎng)絡嵌入的結(jié)果，最后通過分類的方法來預測網(wǎng)絡中丟失的邊。對于每個網(wǎng)絡，從中隨機選擇10%、20%、30%、40%、50%的邊進行刪除，并保證刪除后的網(wǎng)絡仍是連通的。這些被刪除的邊當作正例，同時在選取相同數(shù)量不存在的邊當作負例。由于鏈接預測的預測對象是邊，所以需要得到每條邊對應的特征。通過對邊的兩個端點的嵌入向量求Hadamard 積，將得到結(jié)果當作邊的特征進行預測。實驗使用AUC（Area Under Curve of ROC）作為評價指標。在4 個數(shù)據(jù)集上取得的實驗結(jié)果分別如表2～5 所示。

表2 Facebook上的鏈接預測的AUC結(jié)果 單位：%Tab.2 AUC results for link prediction on Facebook unit：%

表3 Cora上的鏈接預測的AUC結(jié)果 單位：%Tab.3 AUC results for link prediction on Cora unit：%

從實驗結(jié)果可以看出本文提出的EMGC 方法在多數(shù)情況下所取得的結(jié)果相較于其他未考慮的社區(qū)信息的方法（DeepWalk、node2vec）有較大的提升，而對于其他考慮了單一粒度社區(qū)信息的方法（ComE、GEMSEC）也有一定的提升。從結(jié)果中還可以觀察到，同時保留結(jié)構(gòu)信息和社區(qū)信息的方法比只保留了結(jié)構(gòu)信息的方法在結(jié)果上表現(xiàn)更好，另外，EMGC 在稠密網(wǎng)絡（Facebook）中比其他對比方法表現(xiàn)較好，而在較為稀疏的網(wǎng)絡（Cora）中，隨著網(wǎng)絡中邊的刪除比例增加而預測精度有較大程度的下降。在Cora 網(wǎng)絡中刪除50%的邊后，EMGC 所取得的結(jié)果有明顯的下降，原因是在稠密網(wǎng)絡上刪除邊并不會導致網(wǎng)絡的結(jié)構(gòu)發(fā)生大量改變，特別是對于網(wǎng)絡社區(qū)結(jié)構(gòu)，而在稀疏網(wǎng)絡中刪除過多的邊會使得網(wǎng)絡的社區(qū)發(fā)生明顯變化，這使得社區(qū)發(fā)現(xiàn)劃分的社區(qū)與真實社區(qū)有著較大的差異。另外Wiki 網(wǎng)絡中在刪除30%、40%、50%的邊后，本文方法所取得結(jié)果與最好的對比方法相比略低，但相差的幅度不大。Wiki 數(shù)據(jù)集是多標簽數(shù)據(jù)集，本文所使用的Louvain 算法是非重疊社區(qū)發(fā)現(xiàn)算法，所劃分的社區(qū)并不能完全符合真實情況，隨著刪除邊的比例增加，EMGC 社區(qū)發(fā)現(xiàn)結(jié)果的質(zhì)量會隨之降低，使得嵌入的預測精度處于同樣的下降趨勢。社區(qū)信息的大量損失會導致融合社區(qū)信息方法取得相對較低的結(jié)果，但總體上比只考慮局部結(jié)構(gòu)信息的方法仍有著不錯的提升。

表4 Wiki上的鏈接預測的AUC結(jié)果 單位：%Tab.4 AUC results for link prediction on Wiki unit：%

表5 DBLP數(shù)據(jù)上的鏈接預測的AUC結(jié)果 單位：%Tab.5 AUC results for link prediction on DBLP unit：%

3.2 節(jié)點分類結(jié)果分析

節(jié)點分類的目標是將網(wǎng)絡中未標記的節(jié)點劃分到單個或多個類別當中。由于Facebook 數(shù)據(jù)集沒有真實標簽，Wiki為多標簽數(shù)據(jù)集，所以本文選擇在稀疏網(wǎng)絡Cora 和稠密網(wǎng)絡DBLP 上進行實驗驗證。在這兩個數(shù)據(jù)集上，隨機選擇10%～90% 標記節(jié)點當作訓練樣本來訓練一對多分類器（OneVsRest）分類器。對于每種分類實驗，都執(zhí)行10 次，計算Macro-F1 和Micro-F1 的平均值來評價網(wǎng)絡嵌入結(jié)果的有效性。

在Cora、DBLP 數(shù)據(jù)集上進行節(jié)點分類所取得結(jié)果分別如表6、7 所示，每列粗體數(shù)字代表取得的最好結(jié)果。在Cora數(shù)據(jù)集上，當訓練比例小于30%時，node2vec 取得最好的結(jié)果，而當訓練比例增大時，EMGC 取得的結(jié)果始終比其他方法好。相同的結(jié)論在DBLP 數(shù)據(jù)集上也有體現(xiàn)，這是由于本文方法的節(jié)點嵌入是進行拼接得到的，其包含的特征維度較大，訓練分類器需要更多的樣本進行訓練以獲得最佳的分類器性能。另外，在DBLP 數(shù)據(jù)集中，當訓練比例為60%或70%時，本文方法取得的Micro-F1 比node2vec 稍低，處于可接受的范圍，同時node2vec 取得的Macro-F1值比本文方法低，但相差不大，即在60%或70%的訓練比例時，node2vec 可以得到與本文方法接近的結(jié)果?？傮w上，與其他對比方法相比，隨著訓練比例的增大，本文提出的EMGC 方法能夠取得較好的分類精度。

表6 Cora數(shù)據(jù)集上的節(jié)點分類結(jié)果 單位：%Tab.6 Node classification results on Cora dataset unit：%

表7 DBLP數(shù)據(jù)集上的節(jié)點分類結(jié)果 單位：%Tab.7 Node classification results on DBLP dataset unit：%

3.3 粒度分析

為了分析不同粒度對結(jié)果的影響，本節(jié)通過拼接不同粒度下的嵌入，分別在鏈接預測和節(jié)點分類實驗的基礎上，研究其對預測結(jié)果的影響。在鏈接預測的實驗中，隨機刪除50%的邊，使用AUC 作為評價指標。在4 個數(shù)據(jù)集中，不同拼接粒度所預測的結(jié)果如圖4 所示。

圖4 4個數(shù)據(jù)集上不同粒度的鏈接預測結(jié)果Fig.4 Link prediction results of different granularities on 4 datasets

在節(jié)點分類的實驗中，使用50%的節(jié)點進行訓練，使用Macro-F1 和Micro-F1 進行評價。不同拼接粒度下的節(jié)點分類結(jié)果如圖5 所示。所有實驗中的每個粒度下的嵌入都是與之前所有粒度下的嵌入進行拼接得到。

從實驗中可以發(fā)現(xiàn)，Cora、DBLP 被劃分為6 個粒度，F(xiàn)acebook 被劃分為4 個粒度，Wiki 被劃分為5 個粒度。從鏈接預測的結(jié)果（圖4）中可以看到，在所有的數(shù)據(jù)集上，使用2層粒度拼接的嵌入進行預測可以取得最大值，而之后隨著拼接粒度的增加，除了DBLP（圖4（b））上結(jié)果基本穩(wěn)定的情況外，在Cora（圖4（a））、Facebook（圖4（c））、Wiki（圖4（d））上取得鏈接預測結(jié)果處于下降的趨勢。相同的結(jié)果也可以從節(jié)點分類的結(jié)果（圖5）中看到，在Cora（圖5（a））、DBLP（圖5（b））上的Micro-F1 和Macro-F1 在粒度為2 時可以取得最大值。隨著拼接粒度的增加，分類結(jié)果開始波動，總體上呈下降趨勢。因此，2 層粒度的拼接是最優(yōu)選擇，拼接過多的粒度反而會使得實驗結(jié)果的精度下降。

圖5 2個數(shù)據(jù)集上不同粒度的節(jié)點分類結(jié)果Fig.5 Node classification results of different granularities on two datasets

3.4 時間消耗

為了驗證算法在時間復雜度上的優(yōu)勢，本節(jié)將比較所提出的算法與其他對比方法上在4 個數(shù)據(jù)集上進行嵌入所消耗的時間。由于對比方法中DeepWalk、node2vec、ComE 與EMGC 的實現(xiàn)方式不同，這里只與相同實現(xiàn)方式的GEMSEC進行比較。EMGC 和GEMSEC 的運行時間如圖6 所示。

從圖6 中可以發(fā)現(xiàn)，與GEMSEC 相比，在Cora、DBLP 和Wiki 數(shù)據(jù)上，EMGC 的運行時間都低于GEMSEC，而在Facebook 數(shù)據(jù)集上，EMGC 的運行時間略高于GEMSEC，但只有不到1 s 的差距，兩者相差不大。結(jié)合表1 可以看出，EMGC 在不同數(shù)據(jù)集上的運行時間與該數(shù)據(jù)集中的節(jié)點個數(shù)有著很大關(guān)聯(lián)，這與算法復雜度分析結(jié)果相一致。

4 結(jié)語

為了在網(wǎng)絡表示中保留更多原始網(wǎng)絡中的隱含信息，本文提出一種融合多粒度社區(qū)信息的網(wǎng)絡嵌入方法。該方法使用Louvain 算法對網(wǎng)絡中的社區(qū)進行劃分，得到不同粒度下的社區(qū)結(jié)構(gòu)；根據(jù)不同粒度下的社區(qū)結(jié)構(gòu)，在訓練節(jié)點嵌入的同時計算相應的社區(qū)嵌入，利用社區(qū)嵌入更新節(jié)點嵌入，使得節(jié)點的嵌入結(jié)果在保留網(wǎng)絡局部結(jié)構(gòu)信息的同時，保證社區(qū)內(nèi)節(jié)點的嵌入與對應的社區(qū)嵌入結(jié)果相似；將不同粒度下得到節(jié)點嵌入進行拼接，最終得到融合多粒度社區(qū)信息的網(wǎng)絡嵌入結(jié)果。在4 個真實網(wǎng)絡上進行的實驗結(jié)果表明本文提出的方法能夠保留更多的原始網(wǎng)絡的信息，從而提升后續(xù)鏈接預測和節(jié)點分類的準確率。

本文中社區(qū)發(fā)現(xiàn)結(jié)果對最終的嵌入結(jié)果有著重要影響，文中提出的算法所針對的是非重疊社區(qū)，而現(xiàn)實中的社區(qū)有很大一部分為重疊社區(qū)結(jié)構(gòu)，對于未來的工作，將考慮改進嵌入方法，使之能夠應用于重疊社區(qū)的網(wǎng)絡場景中。