基于社區(qū)優(yōu)化的深度網(wǎng)絡(luò)嵌入方法

李亞芳，梁 燁，馮韋瑋，祖寶開，康玉健

（北京工業(yè)大學(xué)信息學(xué)部，北京 100124）

0 引言

網(wǎng)絡(luò)已成為最常見的信息載體和表示形式，在我們?nèi)粘Ｉ钆c工作中無處不在，如社交網(wǎng)絡(luò)、論文合作者網(wǎng)絡(luò)、通信網(wǎng)絡(luò)以及生物網(wǎng)絡(luò)等。文獻(xiàn)［1］指出在社交網(wǎng)絡(luò)已成為人工智能應(yīng)用焦點的大背景下，對網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行研究與分析，已經(jīng)受到社會各界的廣泛關(guān)注，在用戶畫像、內(nèi)容推薦、輿情監(jiān)測、生物分子功能團(tuán)識別等眾多領(lǐng)域具有潛在應(yīng)用價值。

然而，隨著互聯(lián)網(wǎng)技術(shù)以及大數(shù)據(jù)的蓬勃發(fā)展，以微博、微信、Twitter 和Facebook 為代表的社交網(wǎng)絡(luò)進(jìn)入億級節(jié)點時代，不僅網(wǎng)絡(luò)規(guī)模不斷擴(kuò)大、鏈接關(guān)系更加復(fù)雜，還存在缺失數(shù)據(jù)和噪聲信息，這為大規(guī)模網(wǎng)絡(luò)的相關(guān)研究提出了更新、更大的挑戰(zhàn)。對于這類大規(guī)模稀疏復(fù)雜網(wǎng)絡(luò)，文獻(xiàn)［2］中指出，傳統(tǒng)網(wǎng)絡(luò)分析方法將網(wǎng)絡(luò)表示為高維、稀疏的鄰接矩陣，存在如下問題：計算復(fù)雜度高；節(jié)點通過邊關(guān)聯(lián)，難以并行化；難以直接應(yīng)用機器學(xué)習(xí)方法，對于大規(guī)模網(wǎng)絡(luò)的高維、稀疏向量，已有的統(tǒng)計學(xué)習(xí)方法會花費更多的運行時間和計算空間，使得許多先進(jìn)的研究成果無法直接應(yīng)用到現(xiàn)實的網(wǎng)絡(luò)環(huán)境中。

網(wǎng)絡(luò)嵌入方法是解決傳統(tǒng)方法缺陷的有效方式，在保留結(jié)構(gòu)信息的前提下，為網(wǎng)絡(luò)中的每個節(jié)點學(xué)習(xí)一個低維、稠密的連續(xù)特征向量表示［3-4］。通過將網(wǎng)絡(luò)數(shù)據(jù)表示成一種高效合理的形式，不僅有助于更好理解節(jié)點之間的語義關(guān)聯(lián)，而且能夠有效解決大規(guī)模網(wǎng)絡(luò)中的稀疏性，也可作為經(jīng)典機器學(xué)習(xí)模型的輸入，采用已經(jīng)成熟的模型和方法將其運用于后續(xù)節(jié)點分類、社區(qū)發(fā)現(xiàn)、鏈接預(yù)測以及可視化等網(wǎng)絡(luò)分析任務(wù)中，對解決現(xiàn)實網(wǎng)絡(luò)中的實際應(yīng)用問題具有重要意義，如：通過節(jié)點分類構(gòu)建用戶推薦系統(tǒng)；通過社區(qū)發(fā)現(xiàn)進(jìn)行輿情監(jiān)測；通過鏈路預(yù)測推測蛋白質(zhì)之間可能存在的相互作用關(guān)系以推動疾病的治療。

近年來，針對網(wǎng)絡(luò)結(jié)構(gòu)的網(wǎng)絡(luò)嵌入方法被相繼提出，大致可分為基于因子分解的方法［5-13］與基于神經(jīng)網(wǎng)絡(luò)的表示方法［14-20］?；谝蜃臃纸獾姆椒ㄊ紫葮?gòu)造關(guān)系矩陣，通常為鄰接矩陣、Laplacian 矩陣、節(jié)點轉(zhuǎn)移概率矩陣或其他相似度矩陣，通過對關(guān)系矩陣的分解得到節(jié)點的低維向量表示。該類方法可進(jìn)一步分為：1）特征值分解方法（特征向量表示方法），如局部線性表示（Locally Linear Embedding，LLE）［5］、拉普拉斯特征表示（Laplacian Eigenmaps，LE）［6］、結(jié)構(gòu)保持方法（Structure Preserving Embedding，SPE）［7］。2）矩陣分解方法。主要包括圖分解方法（Graph Factorization，GF）［8］、Graph Representation（GraRep）［9］、高階近鄰保持嵌入方法（High-Order Proximity Preserved Embedding，HOPE）［10］、模塊化非負(fù)矩陣分解方法（Modularized Nonnegative Matrix Factorization，M-NMF）［11］、考慮網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的非負(fù)矩陣分解方法（Network Embedding with Community Structural information，NECS）［12］以及網(wǎng)絡(luò)嵌入更新方法（Network Embedding Update，NEU）［13］。GraRep 通過構(gòu)建k階相似度矩陣，往往能得到較好的效果，但算法的計算復(fù)雜度更高。NEU 則采用相似性方法提高基于高階相似度矩陣進(jìn)行節(jié)點表示的效率。M-NMF 通過融合模塊度進(jìn)行非負(fù)矩陣分解，將社團(tuán)結(jié)構(gòu)信息融入網(wǎng)絡(luò)表示學(xué)習(xí)中。類似地，NECS 基于隨機塊模型，將節(jié)點高階的特征矩陣和社區(qū)結(jié)構(gòu)聯(lián)合分解，得到保持網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的低維表示?；谝蜃臃纸獾姆椒?gòu)建的關(guān)系矩陣包括高階節(jié)點鏈接信息時，能夠顯著提升節(jié)點表示的效果；但計算和存儲效率相對較低，難以擴(kuò)展到大規(guī)模網(wǎng)絡(luò)。而且基于因子分解方法只關(guān)注節(jié)點間線性結(jié)構(gòu)關(guān)系是不夠的，因為網(wǎng)絡(luò)的形成是非常復(fù)雜的過程，節(jié)點間常具有非線性復(fù)雜結(jié)構(gòu)關(guān)系，因此，網(wǎng)絡(luò)研究者利用神經(jīng)網(wǎng)絡(luò)建模節(jié)點表示之間的非線性關(guān)系。

DeepWalk 方法［14］是第一個采用神經(jīng)網(wǎng)絡(luò)進(jìn)行網(wǎng)絡(luò)表示學(xué)習(xí)的方法，通過隨機游走得到網(wǎng)絡(luò)結(jié)構(gòu)的線性序列，進(jìn)一步采用訓(xùn)練詞向量的神經(jīng)網(wǎng)絡(luò)模型SkipGram 進(jìn)行網(wǎng)絡(luò)中節(jié)點的表示學(xué)習(xí)。在DeepWalk 的基礎(chǔ)上，人們相繼提出了node2vec［15］、層次網(wǎng)絡(luò)表示方法（Hierarchical Representation Learning for Networks，HARP）［16］、判別深度隨機游走模型（Discriminative Deep Random Walk，DDRW）［17］以及基于邊采樣的網(wǎng)絡(luò)表示學(xué)習(xí)模型（Network Embedding model based on Edge Sampling，NEES）［18］。DeepWalk 及其擴(kuò)展方法通過某種隨機游走策略自動地抽樣網(wǎng)絡(luò)中節(jié)點的路徑，然后通過神經(jīng)網(wǎng)絡(luò)模型得到節(jié)點的表示，但這類方法屬于淺層神經(jīng)網(wǎng)絡(luò)方法，難以充分捕捉現(xiàn)實世界復(fù)雜網(wǎng)絡(luò)中節(jié)點間的高度非線性關(guān)系。進(jìn)而，Wang 等［19］提出基于深度自編碼節(jié)點表示方法（Structural Deep Network Embedding，SDNE），通過綜合考慮網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的一階和二階相似度，取得了較好的節(jié)點表示性能。深度神經(jīng)網(wǎng)絡(luò)表示方法（Deep Neural Networks for Graph Representation，DNGR）［20］構(gòu)建節(jié)點間PPMI（Positive Pointwise Mutual Information）關(guān)聯(lián)矩陣，通過深層降噪自編碼模型學(xué)習(xí)節(jié)點的低維向量表示。基于深度學(xué)習(xí)的網(wǎng)絡(luò)表示方法具有更強的節(jié)點表示能力，不僅能夠?qū)W習(xí)節(jié)點間復(fù)雜的非線性關(guān)系，而且可通過高效優(yōu)化方法求解模型參數(shù)。

節(jié)點低維特征表示的學(xué)習(xí)，為大規(guī)模網(wǎng)絡(luò)的分析和處理提供了一條可行解決思路。但已有方法得到節(jié)點低維特征向量后，需要將其作為其他應(yīng)用（節(jié)點分類、社區(qū)發(fā)現(xiàn)、鏈接預(yù)測、可視化等）的輸入來進(jìn)一步分析，采用的是兩步走策略；缺少針對具體應(yīng)用來設(shè)計模型，因為不同的應(yīng)用場景對學(xué)習(xí)特征的選擇通常有不同的要求。網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)是網(wǎng)絡(luò)分析的主要任務(wù)之一，也是復(fù)雜網(wǎng)絡(luò)的重要結(jié)構(gòu)特性。在網(wǎng)絡(luò)嵌入過程中，將網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)融入節(jié)點嵌入表示過程中，也能夠從全局的角度揭示節(jié)點之間的隱含關(guān)系，有助于提高節(jié)點嵌入表示的質(zhì)量。因此，本文針對網(wǎng)絡(luò)節(jié)點聚類（社區(qū)發(fā)現(xiàn)）的應(yīng)用，基于深度神經(jīng)網(wǎng)絡(luò)的自動編碼器模型SDNE，結(jié)合網(wǎng)絡(luò)的局部和全局拓?fù)浣Y(jié)構(gòu)特性以及深度嵌入聚類（Deep Embedding Clustering，DEC）算法［21］，提出節(jié)點低維表示和社區(qū)結(jié)構(gòu)優(yōu)化的深度網(wǎng)絡(luò)嵌入模型CADNE（Community-Aware Deep Network Embedding）。該模型同時學(xué)習(xí)節(jié)點的低維特征表示和節(jié)點所屬社區(qū)的指示向量，使節(jié)點的低維表示不僅保持原始網(wǎng)絡(luò)結(jié)構(gòu)中的近鄰特性，而且保持原始拓?fù)淇臻g的社區(qū)結(jié)構(gòu)。本文主要工作如下：

1）基于深度自編碼模型提出一種網(wǎng)絡(luò)聚類結(jié)構(gòu)優(yōu)化的深度網(wǎng)絡(luò)嵌入模型CADNE，該方法能夠同時學(xué)習(xí)網(wǎng)絡(luò)節(jié)點拓?fù)滏溄右约肮?jié)點社區(qū)結(jié)構(gòu)的非線性關(guān)系，得到節(jié)點在低維特征空間的向量表示；

2）給出了CADNE模型的框架以及參數(shù)的求解方法；

3）與已有網(wǎng)絡(luò)嵌入方法在經(jīng)典數(shù)據(jù)集進(jìn)行實驗對比，在聚類、分類、鏈接預(yù)測以及可視化等不同應(yīng)用上，驗證了提出CADNE的有效性。

1 深度優(yōu)化的深度網(wǎng)絡(luò)嵌入CADNE

1.1 基本定義

定義1 網(wǎng)絡(luò)（network）。網(wǎng)絡(luò)可描述為G=(V，E)，V={v1，v2，…，vn}表示網(wǎng)絡(luò)中n個節(jié)點組成的集合，E表示節(jié)點間邊的集合。每條邊e∈E是一對包含權(quán)重Aij的有序節(jié)點對e=(vi，vj)，如果節(jié)點vi和vj間不存在鏈接，則Aij=0；若存在鏈接，對于無權(quán)網(wǎng)絡(luò)Aij=1，對于有權(quán)網(wǎng)絡(luò)Aij＞0。

定義2 一階相似性（first-order proximity）。描述任意兩個節(jié)點之間的局部結(jié)構(gòu)相似度，如果兩個節(jié)點間存在鏈接，其一階相似性Aij＞0，否則為0。

一階近鄰描述網(wǎng)絡(luò)中存在直接鏈接的節(jié)點對之間的相似度，只關(guān)注兩個節(jié)點對之間是否存在直接的鏈接。然而，現(xiàn)實網(wǎng)絡(luò)的鏈接關(guān)系往往非常稀疏，而且存在很多非常相似的節(jié)點對之間并沒有直接鏈接關(guān)系，因此，引入二階相似性作為補充以描述全局網(wǎng)絡(luò)結(jié)構(gòu)的相似性。

定義3 二階相似性（second-order proximity）。描述任意兩個節(jié)點近鄰結(jié)構(gòu)的相似性，對于節(jié)點vi和vj，Ai={Ai1，Ai2，…，Ain}和Aj={Aj1，Aj2，…，Ajn}中元素值分別表示兩個節(jié)點與網(wǎng)絡(luò)中其他節(jié)點的一階相似性，則節(jié)點vi和vj的二階相似性為向量Ai和Aj的相似度。

可見，如果兩個節(jié)點共有的鄰居節(jié)點越多，其二階相似性越大，這兩個節(jié)點越相似；若兩個節(jié)點間不存在共同的鄰居鏈接，其二階相似度為0。通過二階相似性可度量網(wǎng)絡(luò)中未存在直接鏈接關(guān)系的節(jié)點對之間的相似度，度量網(wǎng)絡(luò)節(jié)點的全局結(jié)構(gòu)相似度。本文同時考慮節(jié)點間的一階相似性和二階相似性，對網(wǎng)絡(luò)中的節(jié)點進(jìn)行映射表示。

定義4 網(wǎng)絡(luò)嵌入（network embedding）。對網(wǎng)絡(luò)G=(V，E)，學(xué)習(xí)映射函數(shù)f：V→Rd將每個節(jié)點映射為d（d＜n）維特征空間的向量。

1.2 CADNE模型框架

給定無向網(wǎng)絡(luò)G=(V，E)，節(jié)點間的鏈接關(guān)系可用鄰接矩陣表示A=[A1，A2，…，An]描述，可見，原始網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)空間中，每個節(jié)點通過n維向量進(jìn)行表示。本文提出基于深度嵌入聚類進(jìn)行社區(qū)優(yōu)化的深度網(wǎng)絡(luò)表示模型，學(xué)習(xí)節(jié)點在d維低維特征空間的表示，同時得到節(jié)點的社區(qū)劃分，整個模型框架如圖1所示。

圖1 CADNE模型框架Fig.1 Framework of CADNE model

該模型主要由兩部分組成：第一部分是深度自編碼模型通過非線性激活函數(shù)進(jìn)行參數(shù)訓(xùn)練，將節(jié)點映射為易于計算的低維、稠密向量表示，以保持原始網(wǎng)絡(luò)結(jié)構(gòu)中節(jié)點間高度非線性關(guān)系，在映射過程中，保持網(wǎng)絡(luò)節(jié)點一階相似性（局部）及二階相似性（全局）的拓?fù)涮匦?；第二部分是基于DEC 模型，利用節(jié)點聚類結(jié)構(gòu)對節(jié)點低維表示進(jìn)一步優(yōu)化，使得節(jié)點低維表示過程中仍保持節(jié)點聚集特性，通過交替迭代更新深度自編碼模型的編碼過程以及節(jié)點聚類，得到社區(qū)結(jié)構(gòu)優(yōu)化的節(jié)點低維表示。

1.3 保持網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

為了使低維表示后的節(jié)點在新的特征空間中仍保持原網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中的近鄰特性，綜合考慮節(jié)點間的一階相似性以及二階相似性，采用深度自動編碼實現(xiàn)節(jié)點稀疏表示的降維。深度自編碼器包括編碼和解碼兩部分，編碼過程通過多層非線性函數(shù)將輸入數(shù)據(jù)映射到低維特征空間；解碼過程也通過多層非線性函數(shù)將低維特征空間映射到重建后的輸出表示。

設(shè)xi表示根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)得到的模型輸入，如果輸入為鄰接矩陣，則xi=Ai，每個元素描述節(jié)點vi與網(wǎng)絡(luò)中其他節(jié)點的鏈接關(guān)系，即節(jié)點的全局鏈接結(jié)構(gòu)特征。通過將鄰居矩陣作為輸入，得到低維表示后，在解碼階段的網(wǎng)絡(luò)重建過程中，使節(jié)點在原始拓?fù)浣Y(jié)構(gòu)中具有相似近鄰結(jié)構(gòu)特征節(jié)點的低維表示也盡可能相似。假設(shè)深度自動編碼網(wǎng)絡(luò)有K層，則每層的隱含表示為：

通過編碼器逐層編碼降維，得到最深層的zi為節(jié)點的低維向量表示，通過逆向解碼得到自動編碼網(wǎng)絡(luò)的輸出：

其中：σ(x)、f(x)為非線性的激活函數(shù)；θenc={W，b}，θdec={M，d}是待學(xué)習(xí)的編碼器和解碼器的模型參數(shù)。目標(biāo)是根據(jù)新的節(jié)點低維表示zi，最小化輸入xi和輸出的重構(gòu)誤差，通過最小化編碼器輸入和解碼器輸出，使得節(jié)點近鄰結(jié)構(gòu)越相近（二階相似度越高）的節(jié)點對，具有相似的低維向量表示，因此保持網(wǎng)絡(luò)二階相似性的目標(biāo)函數(shù)為：

然而，現(xiàn)實網(wǎng)絡(luò)中鏈接非常稀疏，只有極少量的邊被觀測到，因此鄰接矩陣中零元素個數(shù)遠(yuǎn)多于非零元素的數(shù)目。如果直接使用鄰接矩陣作為模型的輸入，過多的零元素將會影響原始網(wǎng)絡(luò)的低維表示以及重建過程，通過最小化重構(gòu)誤差會使得節(jié)點的重建表示傾向于重建很多零元素。因此，在網(wǎng)絡(luò)低維表示和重建過程中，重點關(guān)注鄰接矩陣中的非零元素，定義二階相似性目標(biāo)損失函數(shù)L2nd為：

其中：⊙是哈達(dá)瑪積；Bi=如果鄰接矩陣元素Aij=0，Bij=1，否則Bij=β＞1。通過該二階相似性的目標(biāo)約束，使得原始網(wǎng)絡(luò)拓?fù)淇臻g中具有相似全局鏈接結(jié)構(gòu)關(guān)系的節(jié)點的低維表示也盡可能相似。

為保持原始網(wǎng)絡(luò)空間節(jié)點的局部結(jié)構(gòu)，節(jié)點低維表示映射過程中，要使存在直接鏈接的節(jié)點對的低維表示盡可能相似，因此對這類節(jié)點對進(jìn)行約束，如果其低維表示的距離較遠(yuǎn)則引入較大的懲罰。構(gòu)建一階相似性損失函數(shù)L1st，定義dii=，則優(yōu)化目標(biāo)：

為了使網(wǎng)絡(luò)節(jié)點映射為低維特征空間表示的過程中，同時保持網(wǎng)絡(luò)局部及全局拓?fù)浣Y(jié)構(gòu)，將一階相似性與二階相似性綜合得到目標(biāo)函數(shù)：

1.4 保持網(wǎng)絡(luò)潛在聚類結(jié)構(gòu)

在低維表示空間引入聚類損失，使學(xué)到的網(wǎng)絡(luò)嵌入能夠更好地保持網(wǎng)絡(luò)聚類結(jié)構(gòu)，基于深度聚類算法DEC，將節(jié)點聚類融合到節(jié)點低維表示模型，利用節(jié)點聚類結(jié)構(gòu)對低維表示進(jìn)行進(jìn)一步優(yōu)化。將低維表示的節(jié)點向量zi(i=1，2，…，n)進(jìn)行聚類，設(shè)節(jié)點zi屬于類uj的概率為qij(qij∈Q)，表示節(jié)點zi屬于類中心uj的相似度，學(xué) 生t-分 布（Student’s tdistribution）為：

因此，將節(jié)點低維表示的類分布Q與目標(biāo)分布P擬合，采用KL散度衡量，得到目標(biāo)函數(shù)：

1.5 CADNE算法實現(xiàn)

模型的訓(xùn)練主要分成兩部分：第一部分是網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)保持部分（流程步驟1）～8）），即模型預(yù)訓(xùn)練，通過對深度自編碼模型的編碼器encoder 以及解碼器decoder 進(jìn)行訓(xùn)練，采用Adam 優(yōu)化目標(biāo)函數(shù)Lae，使得節(jié)點低維表示過程中同時保持網(wǎng)絡(luò)結(jié)構(gòu)的局部以及全局結(jié)構(gòu)特性；第二部分根據(jù)節(jié)點聚類結(jié)構(gòu)對節(jié)點低維表示進(jìn)行優(yōu)化（流程步驟9）～13）），對編碼器的編碼過程進(jìn)一步訓(xùn)練，使得節(jié)點的低維表示過程保持聚類結(jié)構(gòu)。通過兩部分的模型預(yù)訓(xùn)練以及社區(qū)結(jié)構(gòu)的優(yōu)化訓(xùn)練，得到構(gòu)建深度網(wǎng)絡(luò)模型參數(shù)及最終節(jié)點低維表示Z。本文提出的CADNE模型流程如下：

輸入 網(wǎng)絡(luò)G=(V，E)的鄰接矩陣A；

輸出 節(jié)點低維表示矩陣Z，模型參數(shù)θenc、θdec。

2 實驗設(shè)計與結(jié)果分析

為驗證提出的基于社區(qū)優(yōu)化的深度網(wǎng)絡(luò)嵌入方法CADNE 的有效性，與經(jīng)典的網(wǎng)絡(luò)表示學(xué)習(xí)模型進(jìn)行對比，在數(shù)據(jù)集20NewsGroup、Cora、Citeseer、BlogCatalog 上進(jìn)行測評。各數(shù)據(jù)集的統(tǒng)計信息如表1所示。

表1 數(shù)據(jù)集屬性Tab.1 Datasets attributes

為了更好地評價本文所提出的模型方法，在實驗部分與7個代表方法進(jìn)行對比分析，包括：

1）DeepWalk：該方法通過在圖中進(jìn)行隨機游走得到的節(jié)點序列，將序列輸入使用Skip-Gram模型得到每個節(jié)點的嵌入表示。

2）LINE：該方法通過優(yōu)化保持一階相似度和二階相似度的目標(biāo)函數(shù)來學(xué)習(xí)每個節(jié)點的低維表示向量。

3）SDNE：該方法通過構(gòu)建深層自編碼器保留網(wǎng)絡(luò)一階相似度和二階相似度，學(xué)習(xí)節(jié)點的低維表示。

4）DNGR：構(gòu)建節(jié)點間PPMI 關(guān)聯(lián)矩陣，通過降噪自編碼得到節(jié)點的低維向量表示。

5）M-NMF：基于矩陣分解學(xué)習(xí)節(jié)點低維嵌入表示，模型訓(xùn)練過程中考慮了節(jié)點的社區(qū)結(jié)構(gòu)。

6）NECS：保持網(wǎng)絡(luò)節(jié)點高階近鄰，同時考慮網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的矩陣分解模型，學(xué)習(xí)節(jié)點低維嵌入表示。

7）DEC：深度嵌入聚類算法，將網(wǎng)絡(luò)鄰接矩陣作為模型輸入進(jìn)行訓(xùn)練，沒有考慮網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)信息。

參數(shù)設(shè)定：為保證對比公平，各方法的參數(shù)設(shè)置為默認(rèn)值，CADNE 參數(shù)設(shè)置為：γ=10，β=10，batch-size=128，ρ=0.000 1，在編碼階段搭建三層神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)，各層神經(jīng)元節(jié)點數(shù)的設(shè)置如表2所示。

表2 神經(jīng)網(wǎng)絡(luò)各層神經(jīng)元節(jié)點數(shù)Tab.2 Neuron nodes in each layer of neural network

2.1 聚類實驗分析

使用CADNE模型得到網(wǎng)絡(luò)節(jié)點的嵌入表示，然后將其運用于節(jié)點聚類任務(wù)，通過聚類的效果評測網(wǎng)絡(luò)表示學(xué)習(xí)的性能。聚類算法采用K-means，評價標(biāo)準(zhǔn)采用標(biāo)準(zhǔn)互信息（Normalized Mutual Information，NMI）以及準(zhǔn)確率（Accuracy，ACC）［22］，這兩個指標(biāo)值越大，說明模型的聚類效果越好，各算法在數(shù)據(jù)集上10次實驗的平均聚類結(jié)果如表3所示。從表中可以看出，CADNE模型在Citeseer和Cora上兩個評測指標(biāo)都取得了最好結(jié)果，在BlogCatalog 上明顯優(yōu)于除DEC 外的其他基準(zhǔn)方法，在20NewsGroup上ACC也取得最優(yōu)，ACC提升最高達(dá)0.525。M-NMF也考慮了網(wǎng)絡(luò)社區(qū)特性，但基于矩陣分解的淺層模型，無法捕獲網(wǎng)絡(luò)更高階復(fù)雜結(jié)構(gòu)特性。NECS方法可以得到類似的結(jié)果，通過引入網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的約束，得到節(jié)點低維表示在BlogCatalog以及Citeseer數(shù)據(jù)集相對于沒有考慮社區(qū)結(jié)構(gòu)的SDNE 以及DNGR 方法，性能得到提升，但由于基于矩陣分解的線性模型，難以捕獲網(wǎng)絡(luò)節(jié)點間復(fù)雜的非線性關(guān)系。DEC通過深度嵌入聚類，在BlogCatalog 數(shù)據(jù)表現(xiàn)較好，但缺乏對網(wǎng)絡(luò)特殊拓?fù)浣Y(jié)構(gòu)特性的保持，在其他數(shù)據(jù)集的性能有待提高。SDNE通過綜合考慮網(wǎng)絡(luò)一階相似度以及二階相似度，聚類效果優(yōu)于采用深度訓(xùn)練模型的DNGR，但CADNE 模型在節(jié)點低維表示過程中，除了考慮網(wǎng)絡(luò)的局部及全局拓?fù)浣Y(jié)構(gòu)，還考慮節(jié)點聚集的社團(tuán)結(jié)構(gòu)進(jìn)行優(yōu)化，表現(xiàn)出更好的聚類結(jié)果，驗證了基于網(wǎng)絡(luò)節(jié)點社區(qū)結(jié)構(gòu)進(jìn)行深度嵌入表示的有效性。

表3 不同網(wǎng)絡(luò)嵌入方法在數(shù)據(jù)集上的NMI和ACC比較Tab.3 NMI and ACC of different network embedding methods on datasets

2.2 分類實驗分析

CADNE 模型得到節(jié)點表示之后，將其運用于節(jié)點的分類任務(wù)，分類結(jié)果的好壞可以有效判斷網(wǎng)絡(luò)表示學(xué)習(xí)模型學(xué)習(xí)到的嵌入表示是否包含了網(wǎng)絡(luò)更多的特性。分類算法采用Liblinear 分類包，和其他網(wǎng)絡(luò)表示學(xué)習(xí)方法［19］類似，采用宏平均（Macro-F1）和微平均（Micro-F1）兩個指標(biāo)作為模型性能的評價標(biāo)準(zhǔn)，這兩個指標(biāo)值越大表明模型的分類性能越好。隨機抽取10%到90%的節(jié)點嵌入表示作為訓(xùn)練樣本，其余作為測試樣本。在20NewsGroup、Cora、Citeseer、BlogCatalog數(shù)據(jù)集的多標(biāo)簽分類結(jié)果如表4～7所示。

表4 訓(xùn)練樣本占比不同時在數(shù)據(jù)集20NewsGroup上的宏平均與微平均結(jié)果對比Tab.4 Comparison of Macro-F1 and Micro-F1 results on 20NewsGroup dataset with different proportions of training samples

由實驗結(jié)果可知，CADNE 模型分類效果在BlogCatalog、Citeseer、Cora 數(shù)據(jù)集上兩個評測指標(biāo)都取得最好結(jié)果，除Cora 在90%訓(xùn)練比例時微平均略遜于DEC。結(jié)果表明，與基線方法相比，該方法學(xué)習(xí)到的節(jié)點低維表示能更好地應(yīng)用到分類任務(wù)。其中，CANDE 模型在BlogCatalog 數(shù)據(jù)集上優(yōu)勢最為明顯，在訓(xùn)練比例20%時比基線方法提升最高達(dá)0.512。這在一定程度上表明CADNE 模型結(jié)構(gòu)對網(wǎng)絡(luò)表示學(xué)習(xí)有積極的影響。在表6（BlogCatalog）中，當(dāng)訓(xùn)練百分比從60%下降到10%時，本文方法在基線上的改進(jìn)幅度更加明顯。結(jié)果表明，在標(biāo)記數(shù)據(jù)有限的情況下，該方法比基線方法有更大的改進(jìn)。這種優(yōu)勢對于實際應(yīng)用尤其重要，因為標(biāo)記的數(shù)據(jù)通常是稀缺的。在大多數(shù)情況下，DeepWalk 性能是網(wǎng)絡(luò)嵌入方法中最差的，DeepWalk 沒有明確的目標(biāo)函數(shù)來捕獲網(wǎng)絡(luò)結(jié)構(gòu)，且所采用的隨機游走方式可能引入了噪聲。雖然對于全連接網(wǎng)絡(luò)NewsGroup，CADNE 模型的性能略遜于LINE 方法，主要可能是無法有效通過權(quán)重捕獲網(wǎng)絡(luò)中節(jié)點間的相似性關(guān)系。但在大多數(shù)情況下，CADNE 模型的性能是網(wǎng)絡(luò)嵌入方法中最好的，該方法根據(jù)節(jié)點聚類結(jié)構(gòu)對節(jié)點低維表示進(jìn)行優(yōu)化，對編碼器的編碼過程進(jìn)一步訓(xùn)練，使得節(jié)點的低維表示過程保持聚類結(jié)構(gòu)。因此，該模型學(xué)習(xí)到的網(wǎng)絡(luò)表示能更好地推廣到分類任務(wù)。

表6 訓(xùn)練樣本占比不同時在數(shù)據(jù)集Citeseer上的宏平均與微平均結(jié)果對比Tab.6 Comparison of Macro-F1 and Micro-F1 results on Citeseer dataset with different proportions of training samples

表5 訓(xùn)練樣本占比不同時在數(shù)據(jù)集BlogCatalog上的宏平均與微平均結(jié)果對比Tab.5 Comparison of Macro-F1 and Micro-F1 results on BlogCatalog dataset with different proportions of training samples

2.3 鏈接預(yù)測實驗分析

為了驗證CADNE 模型得到的節(jié)點低維嵌入在鏈接預(yù)測中的有效性，從低維表示后的樣本中隨機選取90%作為訓(xùn)練集，采用邏輯回歸分類器進(jìn)行模型訓(xùn)練，使用受試者工作特性曲 線（Receiver Operating Curve，ROC）下面積AUC（Area Under ROC Curve）衡量預(yù)測的準(zhǔn)確性，較高的AUC 值表示更好的性能。各模型的實驗對比結(jié)果如表8所示。

表8 不同網(wǎng)絡(luò)嵌入方法在數(shù)據(jù)集上的AUC值Tab.8 AUC values of different network embedding methods on datasets

從實驗結(jié)果可見，相比已有的網(wǎng)絡(luò)嵌入方法，本文提出的基于社區(qū)優(yōu)化的深度網(wǎng)絡(luò)嵌入方法CADNE 在各數(shù)據(jù)集上準(zhǔn)確性都取得較大提升。具體來說，在20NewsGroup 上，LINE和DNGR 性能優(yōu)于CADNE 方法，主要原因可能是在全鏈接網(wǎng)絡(luò)20NewsGroup 上，LINE 通過隨機塊模型能夠獲取更加可靠的節(jié)點拓?fù)潢P(guān)系，DNGR 通過構(gòu)建PPMI 矩陣能夠更好捕獲節(jié)點間的拓?fù)湎嗨脐P(guān)系，因此取得更好的性能；但在20NewsGroup 上，CADNE 相較于其他基線方法，AUC 提升最多 達(dá)0.451。在其他三個數(shù)據(jù) 集Cora、Citeseer 以 及BlogCatalog 上，本文方法都取得最優(yōu)結(jié)果，比基線方法提高了約0.111～0.378。以上結(jié)果表明本文通過結(jié)合節(jié)點社團(tuán)結(jié)構(gòu)的深度網(wǎng)絡(luò)嵌入方法，能夠得到更好的節(jié)點低維表示。

2.4 可視化實驗分析

為進(jìn)一步評測本文CADNE模型節(jié)點嵌入表示的有效性，在20Newsgroup 數(shù)據(jù)集上與LINE、DNGR 以及SDNE 的可視化結(jié)果進(jìn)行比較。將網(wǎng)絡(luò)嵌入模型輸出得到的節(jié)點低維嵌入表示輸入t-SNE 得到數(shù)據(jù)樣本在2D 空間的可視化圖，其中同顏色的數(shù)據(jù)點表示同一類別。通過可視化，不同顏色樣本點組成的簇間的邊界越清晰，說明模型得到的節(jié)點表示越好。

從圖2（橫軸、縱軸是將數(shù)據(jù)樣本點降維到2維空間后，分別在兩個坐標(biāo)的數(shù)值）結(jié)果可見，LINE 和DNGR 的類邊界不清晰，而且類內(nèi)混淆度比較大，盡管SDNE 能夠得到比較好的可視化結(jié)果，但不同類的邊界也不夠清楚；CADNE 則能夠得到比較清晰的類邊界，三個類間的間距比較大，而且同一個類內(nèi)相同節(jié)點大部分聚集在一起。由此可見，在節(jié)點低維表示過程中，引入節(jié)點的聚類結(jié)構(gòu)對低維表示進(jìn)行優(yōu)化，能夠得到類邊界更加清晰的節(jié)點低維表示。

圖2 20NewsGroup數(shù)據(jù)集可視化圖Fig.2 Visualization Results of 20NewsGroup dataset

表7 訓(xùn)練樣本占比不同時在數(shù)據(jù)集Cora上的宏平均與微平均結(jié)果對比Tab.7 Comparison of Macro-F1 and Micro-F1 results on Cora dataset with different proportions of training samples

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

CADNE 有兩個超參數(shù)：樣本重要度參數(shù)γ和二階相似度系數(shù)β。這里選擇在四個數(shù)據(jù)集上進(jìn)行測試，通過實驗分析超參數(shù)的選擇對CADNE 模型在鏈接預(yù)測上的性能。除了當(dāng)前被測試的參數(shù)，其他參數(shù)均保持默認(rèn)值。

圖3 顯示了γ取值為［0，30］時所有樣本數(shù)據(jù)集AUC 值的分布情況。從結(jié)果可見，當(dāng)γ為0 時，CADNE 取得的效果最差。此時相當(dāng)于CADNE 模型僅利用了網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中的一階近鄰信息，無法完全保留網(wǎng)絡(luò)中高階的相似度；隨著γ增大，CADNE 模型的效果先迅速提升，在γ=10 時達(dá)到最好之后緩慢下降，在Cora 和Citeseer 數(shù)據(jù)集上結(jié)果比較穩(wěn)定。因此，本實驗設(shè)置中該參數(shù)設(shè)置為10。

圖3 不同參數(shù)γ的AUC值Fig.3 AUC values of different γ

圖4 中可以得到類似的結(jié)果，當(dāng)β從1 增至30 過程中，開始CADNE 性能迅速提升，到10 取得最優(yōu)結(jié)果，之后緩慢下降。具體地，在β=1 時效果最差，此時將鄰接矩陣中零元素與非零元素同等對待進(jìn)行模型訓(xùn)練，因此會重建更多的零元素，引入的噪聲信息影響了最終節(jié)點嵌入表示的性能。隨著β增加，模型會傾向于重建更多的非零元素，因此效果有顯著提升；但過大的β使得忽略零元素的重建過程，性能會降低，因此在實驗過程中β設(shè)置為10。

圖4 不同參數(shù)β的AUC值Fig.4 AUC values of different β

3 結(jié)語

本文提出了一種基于社區(qū)結(jié)構(gòu)優(yōu)化的網(wǎng)絡(luò)嵌入方法，在節(jié)點低維表示過程中，不僅保持網(wǎng)絡(luò)的局部和全局拓?fù)浣Y(jié)構(gòu)特性，而且融合節(jié)點潛在的社區(qū)特性對低維表示進(jìn)行優(yōu)化。打破了傳統(tǒng)網(wǎng)絡(luò)表示學(xué)習(xí)方法局限，得到更具有表示能力的低維、稠密特征表示。本文提出的基于社區(qū)結(jié)構(gòu)優(yōu)化進(jìn)行節(jié)點低維特征表示的深度自編碼聚類模型CADNE，能夠同時學(xué)習(xí)節(jié)點的低維表示和節(jié)點所屬社區(qū)的指示向量，在多個數(shù)據(jù)集上與已有經(jīng)典網(wǎng)絡(luò)嵌入方法對比實驗表明：CADNE 模型具有較好的節(jié)點低維表示能力。