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

（北京工業(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)用焦點(diǎn)的大背景下，對(duì)網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行研究與分析，已經(jīng)受到社會(huì)各界的廣泛關(guān)注，在用戶畫像、內(nèi)容推薦、輿情監(jiān)測(cè)、生物分子功能團(tuán)識(shí)別等眾多領(lǐng)域具有潛在應(yīng)用價(jià)值。

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

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

近年來，針對(duì)網(wǎng)絡(luò)結(jié)構(gòu)的網(wǎng)絡(luò)嵌入方法被相繼提出，大致可分為基于因子分解的方法［5-13］與基于神經(jīng)網(wǎng)絡(luò)的表示方法［14-20］。基于因子分解的方法首先構(gòu)造關(guān)系矩陣，通常為鄰接矩陣、Laplacian 矩陣、節(jié)點(diǎn)轉(zhuǎn)移概率矩陣或其他相似度矩陣，通過對(duì)關(guān)系矩陣的分解得到節(jié)點(diǎn)的低維向量表示。該類方法可進(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階相似度矩陣，往往能得到較好的效果，但算法的計(jì)算復(fù)雜度更高。NEU 則采用相似性方法提高基于高階相似度矩陣進(jìn)行節(jié)點(diǎn)表示的效率。M-NMF 通過融合模塊度進(jìn)行非負(fù)矩陣分解，將社團(tuán)結(jié)構(gòu)信息融入網(wǎng)絡(luò)表示學(xué)習(xí)中。類似地，NECS 基于隨機(jī)塊模型，將節(jié)點(diǎn)高階的特征矩陣和社區(qū)結(jié)構(gòu)聯(lián)合分解，得到保持網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的低維表示。基于因子分解的方法構(gòu)建的關(guān)系矩陣包括高階節(jié)點(diǎn)鏈接信息時(shí)，能夠顯著提升節(jié)點(diǎn)表示的效果；但計(jì)算和存儲(chǔ)效率相對(duì)較低，難以擴(kuò)展到大規(guī)模網(wǎng)絡(luò)。而且基于因子分解方法只關(guān)注節(jié)點(diǎn)間線性結(jié)構(gòu)關(guān)系是不夠的，因?yàn)榫W(wǎng)絡(luò)的形成是非常復(fù)雜的過程，節(jié)點(diǎn)間常具有非線性復(fù)雜結(jié)構(gòu)關(guān)系，因此，網(wǎng)絡(luò)研究者利用神經(jīng)網(wǎng)絡(luò)建模節(jié)點(diǎn)表示之間的非線性關(guān)系。

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

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

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

3）與已有網(wǎng)絡(luò)嵌入方法在經(jīng)典數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)對(duì)比，在聚類、分類、鏈接預(yù)測(cè)以及可視化等不同應(yīng)用上，驗(yàn)證了提出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個(gè)節(jié)點(diǎn)組成的集合，E表示節(jié)點(diǎn)間邊的集合。每條邊e∈E是一對(duì)包含權(quán)重Aij的有序節(jié)點(diǎn)對(duì)e=(vi，vj)，如果節(jié)點(diǎn)vi和vj間不存在鏈接，則Aij=0；若存在鏈接，對(duì)于無權(quán)網(wǎng)絡(luò)Aij=1，對(duì)于有權(quán)網(wǎng)絡(luò)Aij＞0。

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

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

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

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

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

1.2 CADNE模型框架

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

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

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

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

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

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

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

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

然而，現(xiàn)實(shí)網(wǎng)絡(luò)中鏈接非常稀疏，只有極少量的邊被觀測(cè)到，因此鄰接矩陣中零元素個(gè)數(shù)遠(yuǎn)多于非零元素的數(shù)目。如果直接使用鄰接矩陣作為模型的輸入，過多的零元素將會(huì)影響原始網(wǎng)絡(luò)的低維表示以及重建過程，通過最小化重構(gòu)誤差會(huì)使得節(jié)點(diǎn)的重建表示傾向于重建很多零元素。因此，在網(wǎng)絡(luò)低維表示和重建過程中，重點(diǎn)關(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é)點(diǎn)的低維表示也盡可能相似。

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

為了使網(wǎng)絡(luò)節(jié)點(diǎn)映射為低維特征空間表示的過程中，同時(shí)保持網(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é)點(diǎn)聚類融合到節(jié)點(diǎn)低維表示模型，利用節(jié)點(diǎn)聚類結(jié)構(gòu)對(duì)低維表示進(jìn)行進(jìn)一步優(yōu)化。將低維表示的節(jié)點(diǎn)向量zi(i=1，2，…，n)進(jìn)行聚類，設(shè)節(jié)點(diǎn)zi屬于類uj的概率為qij(qij∈Q)，表示節(jié)點(diǎn)zi屬于類中心uj的相似度，學(xué) 生t-分 布（Student’s tdistribution）為：

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

1.5 CADNE算法實(shí)現(xiàn)

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

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

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

2 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

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

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

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

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

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

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

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

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

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

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

參數(shù)設(shè)定：為保證對(duì)比公平，各方法的參數(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é)點(diǎn)數(shù)的設(shè)置如表2所示。

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

2.1 聚類實(shí)驗(yàn)分析

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

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

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

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

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

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

2.3 鏈接預(yù)測(cè)實(shí)驗(yàn)分析

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

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

從實(shí)驗(yàn)結(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 通過隨機(jī)塊模型能夠獲取更加可靠的節(jié)點(diǎn)拓?fù)潢P(guān)系，DNGR 通過構(gòu)建PPMI 矩陣能夠更好捕獲節(jié)點(diǎn)間的拓?fù)湎嗨脐P(guān)系，因此取得更好的性能；但在20NewsGroup 上，CADNE 相較于其他基線方法，AUC 提升最多 達(dá)0.451。在其他三個(gè)數(shù)據(jù) 集Cora、Citeseer 以 及BlogCatalog 上，本文方法都取得最優(yōu)結(jié)果，比基線方法提高了約0.111～0.378。以上結(jié)果表明本文通過結(jié)合節(jié)點(diǎn)社團(tuán)結(jié)構(gòu)的深度網(wǎng)絡(luò)嵌入方法，能夠得到更好的節(jié)點(diǎn)低維表示。

2.4 可視化實(shí)驗(yàn)分析

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

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

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

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

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

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

圖3 顯示了γ取值為［0，30］時(shí)所有樣本數(shù)據(jù)集AUC 值的分布情況。從結(jié)果可見，當(dāng)γ為0 時(shí)，CADNE 取得的效果最差。此時(shí)相當(dāng)于CADNE 模型僅利用了網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中的一階近鄰信息，無法完全保留網(wǎng)絡(luò)中高階的相似度；隨著γ增大，CADNE 模型的效果先迅速提升，在γ=10 時(shí)達(dá)到最好之后緩慢下降，在Cora 和Citeseer 數(shù)據(jù)集上結(jié)果比較穩(wěn)定。因此，本實(shí)驗(yà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 時(shí)效果最差，此時(shí)將鄰接矩陣中零元素與非零元素同等對(duì)待進(jìn)行模型訓(xùn)練，因此會(huì)重建更多的零元素，引入的噪聲信息影響了最終節(jié)點(diǎn)嵌入表示的性能。隨著β增加，模型會(huì)傾向于重建更多的非零元素，因此效果有顯著提升；但過大的β使得忽略零元素的重建過程，性能會(huì)降低，因此在實(shí)驗(yàn)過程中β設(shè)置為10。

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

3 結(jié)語

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