基于動(dòng)態(tài)投影嵌入的多維異質(zhì)網(wǎng)絡(luò)可視化研究

余 磊，許光鑾，王 洋，林道玉，李 峰

1.中國(guó)科學(xué)院 空天信息創(chuàng)新研究院，北京100094

2.中國(guó)科學(xué)院 網(wǎng)絡(luò)信息體系技術(shù)重點(diǎn)實(shí)驗(yàn)室，北京100190

3.中國(guó)科學(xué)院大學(xué) 電子電氣與通信工程學(xué)院，北京100049

隨著信息時(shí)代和大數(shù)據(jù)時(shí)代的快速發(fā)展，網(wǎng)絡(luò)數(shù)據(jù)形式開(kāi)始成為現(xiàn)實(shí)世界中不可或缺的數(shù)據(jù)組織形式，例如，Twitter、Facebook 和新浪微博等構(gòu)成的人與人之間的社交網(wǎng)絡(luò)。在信息社會(huì)中，網(wǎng)絡(luò)形式的數(shù)據(jù)形成了不同的信息網(wǎng)絡(luò)，這些信息網(wǎng)絡(luò)包含豐富的語(yǔ)義信息，對(duì)這類(lèi)網(wǎng)絡(luò)信息進(jìn)行研究和分析具有很高的學(xué)術(shù)價(jià)值和潛在的應(yīng)用價(jià)值[1]。在研究信息網(wǎng)絡(luò)時(shí)，研究者通常將信息網(wǎng)絡(luò)（network）抽象化為圖（graph），把復(fù)雜網(wǎng)絡(luò)表示為由眾多節(jié)點(diǎn)和邊構(gòu)成的圖[2]。根據(jù)節(jié)點(diǎn)和邊的類(lèi)型數(shù)目，將網(wǎng)絡(luò)分類(lèi)為同質(zhì)信息網(wǎng)絡(luò)和異質(zhì)信息網(wǎng)絡(luò)。對(duì)于一個(gè)表示為G=(V,E)的網(wǎng)絡(luò)，其中V是節(jié)點(diǎn)集合，E是邊的集合，設(shè)TV、TE分別表示節(jié)點(diǎn)和邊的類(lèi)型種類(lèi)，若TV+TE ＞1，這樣的網(wǎng)絡(luò)稱(chēng)為異質(zhì)信息網(wǎng)絡(luò)，否則稱(chēng)為同質(zhì)信息網(wǎng)絡(luò)。異質(zhì)信息網(wǎng)絡(luò)包含多種類(lèi)型的節(jié)點(diǎn)和關(guān)系，在現(xiàn)實(shí)世界中無(wú)處不在，因此對(duì)異質(zhì)信息網(wǎng)絡(luò)的研究更具有現(xiàn)實(shí)意義。

可視化與可視分析旨在通過(guò)視覺(jué)手段獲取研究目標(biāo)的直觀信息并且通過(guò)視覺(jué)分析方法來(lái)挖掘目標(biāo)數(shù)據(jù)中的隱藏信息[3]。現(xiàn)代的主流觀點(diǎn)認(rèn)為數(shù)據(jù)可視化按照類(lèi)別分為科學(xué)可視化和信息可視化兩個(gè)主要分支。本文要研究的網(wǎng)絡(luò)可視化就是信息可視化的重要組成部分。信息可視化以抽象的、非結(jié)構(gòu)化數(shù)據(jù)為主要研究對(duì)象，通常在二維空間進(jìn)行可視化展示。

本文針對(duì)異質(zhì)網(wǎng)絡(luò)可視化進(jìn)行研究，異質(zhì)網(wǎng)絡(luò)可視化通常涉及異質(zhì)信息的處理以及高維數(shù)據(jù)的降維處理等技術(shù)手段。傳統(tǒng)的網(wǎng)絡(luò)可視化技術(shù)對(duì)于異質(zhì)網(wǎng)絡(luò)可視化來(lái)說(shuō)可視效果并不樂(lè)觀。例如節(jié)點(diǎn)-鏈接法[3]通過(guò)將節(jié)點(diǎn)間的關(guān)系用線段連接起來(lái)重構(gòu)網(wǎng)絡(luò)的結(jié)構(gòu)，主要采用布局算法來(lái)對(duì)網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行可視化展示，但是這種方法將包含不同屬性的異質(zhì)網(wǎng)絡(luò)節(jié)點(diǎn)布局在一個(gè)空間，造成了布局效果混亂、異質(zhì)信息難以體現(xiàn)的結(jié)果。相鄰矩陣法[3]通過(guò)構(gòu)建節(jié)點(diǎn)間的關(guān)系矩陣來(lái)對(duì)網(wǎng)絡(luò)進(jìn)行可視化展示，但是當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)眾多且相鄰矩陣稀疏時(shí)，每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)高維稀疏向量，通常需要采用降維算法來(lái)進(jìn)行降維處理。

鑒于表示學(xué)習(xí)在自然語(yǔ)言處理領(lǐng)域的廣泛應(yīng)用，人們將網(wǎng)絡(luò)類(lèi)比于文本，提出了網(wǎng)絡(luò)表示學(xué)習(xí)[4]（網(wǎng)絡(luò)嵌入）的概念，并對(duì)此進(jìn)行了大量的研究工作。網(wǎng)絡(luò)表示學(xué)習(xí)旨在通過(guò)機(jī)器學(xué)習(xí)等訓(xùn)練方式將網(wǎng)絡(luò)的節(jié)點(diǎn)表示為低維稠密的向量。作為網(wǎng)絡(luò)研究的基礎(chǔ)性任務(wù)，網(wǎng)絡(luò)表示學(xué)習(xí)通常用于鏈接預(yù)測(cè)、節(jié)點(diǎn)分類(lèi)、可視化等后續(xù)任務(wù)。因此衍生出了一種新的基于網(wǎng)絡(luò)表示學(xué)習(xí)的網(wǎng)絡(luò)可視化技術(shù)。為了有效地對(duì)異質(zhì)網(wǎng)絡(luò)中豐富且復(fù)雜的語(yǔ)義信息進(jìn)行可視化，本文提出了一種新的基于投影嵌入的多維度異質(zhì)網(wǎng)絡(luò)可視化方法。首先，本文提出了基于動(dòng)態(tài)投影的異質(zhì)網(wǎng)絡(luò)嵌入方法，得到了包含異質(zhì)網(wǎng)絡(luò)豐富信息的節(jié)點(diǎn)表示向量；其次，本文提出了一種新的多維度異質(zhì)網(wǎng)絡(luò)可視化方法，該方法很好地解決了多屬性多關(guān)系的可視化問(wèn)題；最后，本文進(jìn)行了相應(yīng)的實(shí)驗(yàn)，發(fā)現(xiàn)提出的異質(zhì)網(wǎng)絡(luò)表示學(xué)習(xí)方法和可視化方法確實(shí)達(dá)到了較好的效果。

1 相關(guān)工作

網(wǎng)絡(luò)可視化的核心是網(wǎng)絡(luò)布局算法，因此很多研究者對(duì)網(wǎng)絡(luò)布局進(jìn)行了深入的探索。節(jié)點(diǎn)鏈接法主要有力引導(dǎo)布局算法（Force-directed Layout）、多維尺度分析布局算法（MDS）以及弧長(zhǎng)鏈接圖算法。具體工作有：Eades[5]最早提出力引導(dǎo)布局算法，之后研究者豐富了節(jié)點(diǎn)之間的物理模型，提出了能量模型[6]。為了改進(jìn)力引導(dǎo)布局只能實(shí)現(xiàn)局部?jī)?yōu)化這一缺點(diǎn)，F(xiàn)ADE算法利用四叉樹(shù)分解來(lái)降低時(shí)間復(fù)雜度[7]。多維尺度布局算法從根本上彌補(bǔ)了力引導(dǎo)布局算法的局限性。但MDS多針對(duì)高維數(shù)據(jù)，所以需要采用降維方法將高維數(shù)據(jù)映射至低維空間，因此引出另一個(gè)重要的研究方向——高維數(shù)據(jù)可視化。常見(jiàn)的高維數(shù)據(jù)降維方法有PCA[8]、t-SNE[9-10]、UMAP[11]、LargeVis[12]等等，經(jīng)過(guò)高維數(shù)據(jù)降維處理后，得到2維或3維向量表示，進(jìn)而實(shí)現(xiàn)高維數(shù)據(jù)可視化。

本文提出了一種新的異質(zhì)網(wǎng)絡(luò)可視化方法。即首先通過(guò)異質(zhì)網(wǎng)絡(luò)表示學(xué)習(xí)得到異質(zhì)網(wǎng)絡(luò)節(jié)點(diǎn)的表示向量，然后將表示向量通過(guò)高維數(shù)據(jù)可視化的方法來(lái)實(shí)現(xiàn)異質(zhì)網(wǎng)絡(luò)可視化。研究者們針對(duì)異質(zhì)網(wǎng)絡(luò)的表示學(xué)習(xí)進(jìn)行了大量的研究。早期的網(wǎng)絡(luò)嵌入被認(rèn)為是網(wǎng)絡(luò)特征降維的工具，典型的方法有LLE[13]、IsoMap、HOPE[14]等等。之后研究者們利用隨機(jī)游走算法來(lái)學(xué)習(xí)節(jié)點(diǎn)的嵌入向量，典型方法有DeepWalk[15]和node2vec[16]，以及結(jié)合元路徑用于異質(zhì)網(wǎng)絡(luò)表示學(xué)習(xí)的metapath2vec[17]和Hin2vec[18]。還有一種基于平移機(jī)制和距離度量的方法也取得了很好的效果，如PME[19]和RHINE[20]，本文提出的新的異質(zhì)網(wǎng)絡(luò)表示學(xué)習(xí)方法正是基于平移機(jī)制與距離度量方法，首先提出了動(dòng)態(tài)投影嵌入模型學(xué)習(xí)異質(zhì)網(wǎng)絡(luò)復(fù)雜多樣的語(yǔ)義信息，然后在此基礎(chǔ)上提出了以關(guān)系劃分的多維度（空間）可視化方法。

2 方法介紹

2.1 異質(zhì)網(wǎng)絡(luò)可視化方法整體流程

如圖1 所示，首先提出動(dòng)態(tài)投影嵌入模型，學(xué)習(xí)異質(zhì)網(wǎng)絡(luò)節(jié)點(diǎn)的表示，然后將得到的表示向量通過(guò)多維度投影映射至不同空間進(jìn)行降維處理，進(jìn)而實(shí)現(xiàn)異質(zhì)網(wǎng)絡(luò)的多維度（空間）可視化，最后通過(guò)觀察分析手段發(fā)掘新信息新知識(shí)。

2.2 動(dòng)態(tài)投影嵌入模型

圖1 異質(zhì)網(wǎng)絡(luò)可視化方法整體流程圖

動(dòng)態(tài)投影嵌入（Dynamic Projected Embedding，DPE）模型的核心在于構(gòu)建投影空間，在投影空間內(nèi)進(jìn)行節(jié)點(diǎn)相似性度量，設(shè)計(jì)損失函數(shù)，最后進(jìn)行訓(xùn)練與更新。投影學(xué)習(xí)的關(guān)鍵在于投影矩陣的設(shè)計(jì)，投影矩陣的優(yōu)劣決定了網(wǎng)絡(luò)表示學(xué)習(xí)效果的好壞。PME模型是典型的針對(duì)異質(zhì)網(wǎng)絡(luò)的基于投影度量的表示學(xué)習(xí)方法，該方法為異質(zhì)網(wǎng)絡(luò)的每一種關(guān)系映射一個(gè)投影矩陣，但是PME的投影矩陣僅和對(duì)應(yīng)關(guān)系有關(guān)，對(duì)于該關(guān)系下的所有節(jié)點(diǎn)都相同，一種關(guān)系對(duì)應(yīng)一個(gè)固定的投影矩陣。事實(shí)上，投影過(guò)程是一個(gè)節(jié)點(diǎn)和關(guān)系的交互過(guò)程，該過(guò)程不僅與關(guān)系有關(guān)而且與節(jié)點(diǎn)有關(guān)，同一種關(guān)系下的不同節(jié)點(diǎn)應(yīng)該對(duì)應(yīng)不同的投影矩陣。因此，為每一種關(guān)系下的每一個(gè)節(jié)點(diǎn)分配不同的投影矩陣，這也正是“動(dòng)態(tài)投影”名稱(chēng)的由來(lái)，即投影矩陣隨節(jié)點(diǎn)的不同而動(dòng)態(tài)變化。本文提出的DPE模型中投影矩陣的設(shè)計(jì)兼具靈活性、合理性以及高效性。

如圖2 所示，以DBIS 異質(zhì)網(wǎng)絡(luò)（主要包含作者、文章、機(jī)構(gòu)三種類(lèi)型節(jié)點(diǎn)以及三種關(guān)系）中的paper-author關(guān)系為例，圖2（a）展示了動(dòng)態(tài)投影矩陣的構(gòu)建，模型為異質(zhì)網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)構(gòu)建兩個(gè)向量，一個(gè)作為最終的表示向量，另一個(gè)是用來(lái)構(gòu)造投影矩陣的投影向量；同時(shí)，為每一關(guān)系構(gòu)造一個(gè)投影向量，用來(lái)構(gòu)建投影矩陣。對(duì)于一個(gè)三元組(a,R2,p)，節(jié)點(diǎn)a由表示向量iae和投影向量表示，節(jié)點(diǎn)p由表示向量和投影向量表示，關(guān)系R2 由投影向量rpa表示。DPE 會(huì)為每個(gè)節(jié)點(diǎn)構(gòu)建一個(gè)投影矩陣，節(jié)點(diǎn)a、p的投影矩陣如下：

式中，dr(va,vp)代表節(jié)點(diǎn)a、p在投影空間的相似性距離，fr(va,vp)代表加權(quán)后的相似性距離。事實(shí)上，在投影計(jì)算過(guò)程中，投影計(jì)算復(fù)雜度相對(duì)固定投影模型（PME）也有很大減少。以本文方法DPE和PME分別代表動(dòng)態(tài)投影嵌入方法（Dynamic Projection Embedding，DPE）和固定投影嵌入方法（Fixed Projection Embedding，F(xiàn)PE）來(lái)對(duì)投影計(jì)算復(fù)雜度進(jìn)行分析。以式（5）為例，DPE模型計(jì)算投影空間內(nèi)兩點(diǎn)的相似距離如下：

圖2 DPE模型的原理圖

可以看到動(dòng)態(tài)投影嵌入模型相對(duì)以前的投影度量模型計(jì)算復(fù)雜度減少了一個(gè)數(shù)量級(jí)，具有更快的訓(xùn)練學(xué)習(xí)速度，因此本文提出的DPE模型中投影矩陣的設(shè)計(jì)兼具靈活性、合理性以及高效性。

模型希望有聯(lián)系的節(jié)點(diǎn)在投影空間中盡可能地靠近，而沒(méi)有聯(lián)系的節(jié)點(diǎn)盡可能地遠(yuǎn)離，因此，提出了如下?lián)p失函數(shù)：

其中，Dr表示關(guān)系r下的有鏈接的正樣本集合，表示關(guān)系r下針對(duì)某一節(jié)點(diǎn)對(duì)產(chǎn)生的負(fù)樣本集合。模型采用雙向負(fù)采樣策略，為每一個(gè)節(jié)點(diǎn)對(duì)生成兩種類(lèi)型的負(fù)樣本。由此，得到采用負(fù)采樣策略的損失函數(shù)：

最終，最小化如下目標(biāo)函數(shù)：

多次訓(xùn)練迭代之后，得到網(wǎng)絡(luò)的表示向量，具體包括每一個(gè)節(jié)點(diǎn)的表示向量ie和投影向量ip，以及每一種關(guān)系的投影向量rp。節(jié)點(diǎn)的表示向量ie是最終需要的結(jié)果，但是在特定任務(wù)中節(jié)點(diǎn)和關(guān)系的投影向量也會(huì)起到至關(guān)重要的作用。在多維度異質(zhì)網(wǎng)絡(luò)可視化方法中，就需要結(jié)合DPE模型輸出的這三類(lèi)向量進(jìn)行具體可視化方法的設(shè)計(jì)。

2.3 多維度異質(zhì)網(wǎng)絡(luò)可視化方法

對(duì)異質(zhì)網(wǎng)絡(luò)的可視化，常規(guī)可視化方法在得到表示向量后通過(guò)降維方法，得到節(jié)點(diǎn)的低維表示向量（坐標(biāo)），然后進(jìn)行2D、3D可視化展示。但是這種可視化方法對(duì)于異質(zhì)信息網(wǎng)絡(luò)的展現(xiàn)效果并不理想，因?yàn)樗鼘瑥?fù)雜屬性信息的節(jié)點(diǎn)可視化于同一空間，節(jié)點(diǎn)分布混亂，不能體現(xiàn)節(jié)點(diǎn)的語(yǔ)義信息。為了克服異質(zhì)信息網(wǎng)絡(luò)這種固有可視化方法的弊端，本文提出一種全新的可視化方法，如圖3所示。提出的網(wǎng)絡(luò)可視化方法認(rèn)為異質(zhì)網(wǎng)絡(luò)中的節(jié)點(diǎn)是包含多種屬性的復(fù)雜節(jié)點(diǎn)，節(jié)點(diǎn)的不同屬性導(dǎo)致了節(jié)點(diǎn)間的不同關(guān)系。因此將得到的節(jié)點(diǎn)向量根據(jù)不同關(guān)系，通過(guò)投影計(jì)算分別映射到不同的子空間，從而得到不同關(guān)系空間中的節(jié)點(diǎn)表示，可以認(rèn)為每種關(guān)系空間嵌入了節(jié)點(diǎn)的某種屬性，這樣在每個(gè)關(guān)系空間中就可以針對(duì)某些特性進(jìn)行節(jié)點(diǎn)信息挖掘。

本文通過(guò)DBIS數(shù)據(jù)集來(lái)闡述多維度異質(zhì)網(wǎng)絡(luò)的可視化方案。如圖4所示，可視化方法的具體步驟如下：

（1）如圖4（a）所示，通過(guò)動(dòng)態(tài)投影嵌入模型得到網(wǎng)絡(luò)的表示向量，具體包括節(jié)點(diǎn)投影向量ip和節(jié)點(diǎn)表示向量ie，關(guān)系投影向量rp。其中節(jié)點(diǎn)投影向量ip與關(guān)系投影向量rp用于構(gòu)建投影矩陣。

（2）圖4（b）展示了本文方法如何根據(jù)節(jié)點(diǎn)與關(guān)系進(jìn)行多維度的可視空間劃分。具體如下：對(duì)于每一類(lèi)型的節(jié)點(diǎn)，本文方法都會(huì)根據(jù)包含當(dāng)前類(lèi)型節(jié)點(diǎn)的關(guān)系構(gòu)建對(duì)應(yīng)的投影子空間。例如，對(duì)于作者(a)節(jié)點(diǎn)，作者存在于作者-作者(a-a)，作者-文章(p-a)關(guān)系中，所以作者類(lèi)型的節(jié)點(diǎn)將可視化在對(duì)應(yīng)的兩個(gè)投影空間中。文章(p)與會(huì)議(c)類(lèi)型節(jié)點(diǎn)也采用相同方法。

（3）在構(gòu)建了每一類(lèi)型節(jié)點(diǎn)的投影空間后，利用節(jié)點(diǎn)投影向量ip和節(jié)點(diǎn)表示向量ie，關(guān)系投影向量rp通過(guò)投影計(jì)算得到每個(gè)節(jié)點(diǎn)在不同投影關(guān)系空間下的高維表示向量。投影計(jì)算思想與DPE模型相同，以作者節(jié)點(diǎn)為例的投影計(jì)算具體如下：

圖3 可視化方法對(duì)比圖

圖4 可視化方法流程圖

其中，Mr1a、Mr2a為作者節(jié)點(diǎn)在a-a關(guān)系( )r1 、p-a關(guān)系(r2)下的投影矩陣，分別表示作者節(jié)點(diǎn)在a-a關(guān)系、p-a關(guān)系下投影計(jì)算后的高維向量。在高維投影空間下的其他類(lèi)型節(jié)點(diǎn)（文章、會(huì)議）的表示向量采用同樣投影計(jì)算得到。

（4）得到不同關(guān)系空間中節(jié)點(diǎn)的高維表示向量后，此時(shí)仍然是高維空間（var1通常為幾百維），因此需要將高維數(shù)據(jù)降至低維空間，本方法采用t-SNE算法對(duì)高維向量進(jìn)行降維操作，如下式：

（5）在得到可視化結(jié)果后，通過(guò)分析不同關(guān)系空間的可視化結(jié)果，探索節(jié)點(diǎn)在不同空間中的不同特性，當(dāng)然，經(jīng)過(guò)更加深入的分析，更多的新信息和新知識(shí)有待挖掘，在實(shí)驗(yàn)部分將進(jìn)行詳細(xì)分析以及案例介紹。

3 實(shí)驗(yàn)與評(píng)估

3.1 實(shí)驗(yàn)數(shù)據(jù)集

本文采用了三個(gè)異質(zhì)網(wǎng)絡(luò)常用數(shù)據(jù)集，包括You-Tube 數(shù)據(jù)集、DBIS 數(shù)據(jù)集以及領(lǐng)域知識(shí)圖譜（Domain Knowledge Graph，DKG）數(shù)據(jù)集。YouTube數(shù)據(jù)集主要包含YouTube 中的用戶(hù)和分組兩種類(lèi)型節(jié)點(diǎn)以及兩種關(guān)系。DBIS數(shù)據(jù)集主要包含作者、文章、機(jī)構(gòu)三種類(lèi)型節(jié)點(diǎn)以及三種關(guān)系。DKG數(shù)據(jù)集通過(guò)抽取某領(lǐng)域知識(shí)圖譜的部分圖譜數(shù)據(jù)處理后得到，具體包括機(jī)構(gòu)、人物、地點(diǎn)、國(guó)家、裝備5 類(lèi)節(jié)點(diǎn)，以及機(jī)構(gòu)-機(jī)構(gòu)、機(jī)構(gòu)-人物、機(jī)構(gòu)-地點(diǎn)、人物-國(guó)家、機(jī)構(gòu)-國(guó)家等14類(lèi)關(guān)系。數(shù)據(jù)集的具體統(tǒng)計(jì)信息見(jiàn)表1～3。

表1 YouTube數(shù)據(jù)集統(tǒng)計(jì)數(shù)據(jù)

表2 DBIS數(shù)據(jù)集統(tǒng)計(jì)數(shù)據(jù)

表3 所有數(shù)據(jù)集統(tǒng)計(jì)數(shù)據(jù)

3.2 實(shí)驗(yàn)設(shè)計(jì)與對(duì)比方法

對(duì)于異質(zhì)網(wǎng)絡(luò)表示學(xué)習(xí)效果驗(yàn)證了本文設(shè)計(jì)的鏈接預(yù)測(cè)任務(wù)。鏈接預(yù)測(cè)任務(wù)用已有的一些鏈接來(lái)學(xué)習(xí)網(wǎng)絡(luò)表示模型，然后預(yù)測(cè)那些未知的鏈接。在鏈接預(yù)測(cè)實(shí)驗(yàn)中，采用MRR 指標(biāo)來(lái)評(píng)估鏈接預(yù)測(cè)任務(wù)效果。MRR（Mean Reciprocal Rank）稱(chēng)作平均倒數(shù)排名，對(duì)于一個(gè)正樣本，為其生成眾多負(fù)樣本，然后計(jì)算所有樣本的得分并進(jìn)行排名，將正樣本的排名取倒數(shù)然后求平均（MRR不大于1），因此，MRR越大模型表現(xiàn)越好。MRR計(jì)算公式如下：

實(shí)驗(yàn)中將提出的動(dòng)態(tài)投影嵌入模型（DPE）與現(xiàn)有的一些網(wǎng)絡(luò)表示學(xué)習(xí)方法進(jìn)行對(duì)比，相關(guān)算法有：LINE[21]（實(shí)驗(yàn)中采用LINE-2nd）、Node2vec[16]（隨機(jī)游走長(zhǎng)度設(shè)為100，節(jié)點(diǎn)游走數(shù)為10，滑動(dòng)窗口大小設(shè)為2，p=1,q=1）、Hin2vec[18]（隨機(jī)游走的設(shè)置與Node2vec相同）以及PME[19]。

在異質(zhì)網(wǎng)絡(luò)可視化實(shí)驗(yàn)中，分別在YouTube和DKG數(shù)據(jù)集上采用力引導(dǎo)布局算法直接進(jìn)行可視化，具體包括Fast Multipole Embedder 算法、FM3 算法[22]、FR 算法[6]、KK 算法[23]，然后采用網(wǎng)絡(luò)表示學(xué)習(xí)方法與降維方法結(jié)合的方式（例如：LINE+t-SNE、Node2vec+t-SNE、PME+t-SNE以及DPE+t-SNE）進(jìn)行對(duì)比實(shí)驗(yàn)，文中擇優(yōu)選取了DPE+t-SNE（節(jié)點(diǎn)的表示向量只選ie）作為傳統(tǒng)的降維可視化方法與本文提出的多維度可視化方法進(jìn)行對(duì)比。本文從可視化展示的定性分析來(lái)評(píng)估多維異質(zhì)網(wǎng)絡(luò)的可視化方法，包括可視化效果以及案例分析。

3.3 實(shí)驗(yàn)結(jié)果與分析

3.3.1 異質(zhì)網(wǎng)絡(luò)的表示學(xué)習(xí)

首先訓(xùn)練數(shù)據(jù)集得到網(wǎng)絡(luò)的表示向量，本文為所有方法設(shè)置如下參數(shù)：表示向量維度為128，負(fù)采樣數(shù)目為5。在鏈接預(yù)測(cè)任務(wù)中，訓(xùn)練集與測(cè)試集比例為9∶1。表4展示了鏈接預(yù)測(cè)任務(wù)在YouTube數(shù)據(jù)集和DBIS數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果。從表4可以發(fā)現(xiàn)如下結(jié)論：

（1）動(dòng)態(tài)投影嵌入模型相對(duì)現(xiàn)有異質(zhì)網(wǎng)絡(luò)表示學(xué)習(xí)方法取得了最好效果，證明了本文提出的動(dòng)態(tài)投影嵌入模型很好地保持了原有網(wǎng)絡(luò)的信息，也為后續(xù)可視化任務(wù)奠定了良好的基礎(chǔ)。

（2）由于實(shí)驗(yàn)數(shù)據(jù)集具有很強(qiáng)的稀疏性，但是DPE仍然相較已有的方法取得了很好的表現(xiàn)，可以看出模型在稀疏網(wǎng)絡(luò)數(shù)據(jù)上具有較強(qiáng)的魯棒性。

表4 鏈接預(yù)測(cè)任務(wù)的MRR指標(biāo)

3.3.2 異質(zhì)網(wǎng)絡(luò)可視化

在得到網(wǎng)絡(luò)表示向量后，進(jìn)行多維度可視化的評(píng)估實(shí)驗(yàn)。圖5 展示了YouTube 數(shù)據(jù)集上的可視化效果，圖5（a）～（d）為傳統(tǒng)布局算法的可視化結(jié)果，可以看到傳統(tǒng)布局算法注重布局效果，節(jié)點(diǎn)分布均勻，很難體現(xiàn)異質(zhì)信息。圖5（e）展示了常規(guī)表示學(xué)習(xí)與降維算法結(jié)合的方法，同樣節(jié)點(diǎn)分布均勻，效果不佳。相反，本文方法將異質(zhì)網(wǎng)絡(luò)分為兩個(gè)子空間：用戶(hù)-用戶(hù)空間和用戶(hù)-組別空間。從用戶(hù)角度來(lái)看，用戶(hù)具有兩種屬性，分別是交友屬性（friendship）、興趣組屬性（group-ship），將用戶(hù)節(jié)點(diǎn)分別在兩個(gè)維度（空間）進(jìn)行可視化，挖掘節(jié)點(diǎn)的不同的屬性信息。對(duì)用戶(hù)節(jié)點(diǎn)可視化展示如圖5（f）和圖5（g）所示，可以發(fā)現(xiàn)用戶(hù)節(jié)點(diǎn)形成了明顯的大小不同的聚類(lèi)簇。不難理解，在用戶(hù)-用戶(hù)關(guān)系空間內(nèi)，有邊連接的節(jié)點(diǎn)距離更近，因此用戶(hù)節(jié)點(diǎn)根據(jù)交友屬性聚集成不同的簇；在用戶(hù)-組別關(guān)系空間內(nèi)，用戶(hù)的興趣組屬性起到了關(guān)鍵作用，用戶(hù)節(jié)點(diǎn)根據(jù)組別的不同形成了不同的聚類(lèi)簇，由此可以直觀地發(fā)現(xiàn)用戶(hù)的一些共同興趣以及其他隱藏信息。

圖6 展示了傳統(tǒng)力引導(dǎo)布局算法和降維算法在DKG 數(shù)據(jù)集的可視化圖，可以發(fā)現(xiàn)力引導(dǎo)布局算法的布局效果有一些聚類(lèi)特征，但是其中包含了所有類(lèi)型的節(jié)點(diǎn)，無(wú)法從中針對(duì)某一類(lèi)型節(jié)點(diǎn)進(jìn)行有效的可視分析與挖掘。而圖6（e）的降維算法雖然只針對(duì)機(jī)構(gòu)節(jié)點(diǎn)進(jìn)行可視化展示，但是這種傳統(tǒng)方法將包含復(fù)雜屬性的節(jié)點(diǎn)映射至同一空間內(nèi)，導(dǎo)致布局分布混亂，難以體現(xiàn)不同的屬性信息。圖7 展示了本文可視化方法選取機(jī)構(gòu)類(lèi)型的節(jié)點(diǎn)進(jìn)行可視化的結(jié)果，機(jī)構(gòu)節(jié)點(diǎn)一共存在于5種關(guān)系中：機(jī)構(gòu)-機(jī)構(gòu)、機(jī)構(gòu)-人物、機(jī)構(gòu)-地點(diǎn)、機(jī)構(gòu)-國(guó)家、機(jī)構(gòu)-裝備。因此多維度可視化方法將關(guān)系空間分成5個(gè)子空間，從屬性-關(guān)系角度分析，機(jī)構(gòu)-機(jī)構(gòu)關(guān)系體現(xiàn)了機(jī)構(gòu)間的關(guān)聯(lián)交互性，機(jī)構(gòu)-地點(diǎn)體現(xiàn)了機(jī)構(gòu)的位置屬性，機(jī)構(gòu)-國(guó)家關(guān)系體現(xiàn)了機(jī)構(gòu)的歸屬屬性。機(jī)構(gòu)-人物與機(jī)構(gòu)-裝備關(guān)系對(duì)于機(jī)構(gòu)類(lèi)型的節(jié)點(diǎn)所能體現(xiàn)的信息較少，所以主要關(guān)注前3種關(guān)系空間。可以發(fā)現(xiàn)不同關(guān)系空間下，可視化的結(jié)果不同。在機(jī)構(gòu)-機(jī)構(gòu)空間下，節(jié)點(diǎn)之間形成了許多規(guī)模較小的聚類(lèi)簇，體現(xiàn)了不同機(jī)構(gòu)間的關(guān)聯(lián)程度；在機(jī)構(gòu)-國(guó)家空間中，可視化效果不明顯，原因是邊數(shù)據(jù)的缺失（網(wǎng)絡(luò)中機(jī)構(gòu)節(jié)點(diǎn)數(shù)584，機(jī)構(gòu)-國(guó)家邊數(shù)89），因此后續(xù)需要增加數(shù)據(jù)量來(lái)更加完美地展示這一關(guān)系空間；在機(jī)構(gòu)-地點(diǎn)關(guān)系中，發(fā)現(xiàn)節(jié)點(diǎn)被清晰地分成了5類(lèi)，體現(xiàn)了機(jī)構(gòu)的位置信息。

圖5 Youtube數(shù)據(jù)集可視化圖

圖6 DKG數(shù)據(jù)集傳統(tǒng)布局算法與降維算法可視化圖

圖7 DKG數(shù)據(jù)集本文方法可視化圖

表5 可視化方法的時(shí)間消耗 s

3.3.3 時(shí)間效率分析

本節(jié)分析了實(shí)驗(yàn)中可視化方法的時(shí)間消耗問(wèn)題。對(duì)比方法包括Fast Multipole Embedder 算法、FM3 算法、FR 算法、KK 算法以及采用網(wǎng)絡(luò)表示學(xué)習(xí)方法與降維方法結(jié)合的方法（PME+t-SNE、DPE+t-SNE）。統(tǒng)計(jì)了所有可視化方法在YouTube數(shù)據(jù)集和DKG數(shù)據(jù)集上的可視化所耗費(fèi)時(shí)間。具體耗時(shí)統(tǒng)計(jì)如表5所示。

表5 中的時(shí)間統(tǒng)計(jì)均是取10 次實(shí)驗(yàn)的平均值統(tǒng)計(jì)得到，由表可知：

（1）FME 算法、FM3 算法、FR 算法、KK 算法時(shí)間消耗處于同一量級(jí)（KK算法由于迭代計(jì)算復(fù)雜度較大，因此相對(duì)耗時(shí)較多），但是它們的可視化效率遠(yuǎn)高于后三種方法。事實(shí)上，前四種可視化算法均是直接布局算法，即根據(jù)網(wǎng)絡(luò)原始數(shù)據(jù)直接進(jìn)行力引導(dǎo)布局，因此時(shí)間消耗很少。相反，后三種方法均采用網(wǎng)絡(luò)表示學(xué)習(xí)方法與降維方法結(jié)合，因此可視化耗時(shí)由網(wǎng)絡(luò)表示學(xué)習(xí)耗時(shí)與降維耗時(shí)相加得到。實(shí)驗(yàn)中t-SNE 算法的實(shí)驗(yàn)參數(shù)設(shè)置如表6所示。

表6 t-SNE算法的實(shí)驗(yàn)參數(shù)

（2）對(duì)比后三種方法，可以看到本文提出的動(dòng)態(tài)投影嵌入模型（DPE）相對(duì)傳統(tǒng)的網(wǎng)絡(luò)嵌入模型（PME）已經(jīng)有了很大的效率提升，由于多維度可視化方法需要二次進(jìn)行投影計(jì)算因此時(shí)間消耗略高于DPE+t-SNE 方法，但基本持平。因此本文方法在網(wǎng)絡(luò)嵌入與降維結(jié)合類(lèi)可視化方法中達(dá)到了當(dāng)前最優(yōu)水平。

（3）由于結(jié)合類(lèi)方法需要通過(guò)訓(xùn)練迭代來(lái)學(xué)習(xí)網(wǎng)絡(luò)中的信息，然后通過(guò)降維的方式來(lái)進(jìn)行可視化展示，因此時(shí)間消耗將大大增加，但是這類(lèi)方法通過(guò)時(shí)間消耗換取了更深層次的信息獲取，因此同樣具有應(yīng)用價(jià)值，在案例分析中將體現(xiàn)這一點(diǎn)。

3.4 案例分析

為了驗(yàn)證多維度可視化方案可以幫助人們挖掘有效的信息，本節(jié)深入分析了關(guān)系空間下的可視化視圖。YouTube 數(shù)據(jù)集包含10 000 個(gè)用戶(hù)節(jié)點(diǎn)和10 000 個(gè)組節(jié)點(diǎn)，導(dǎo)致許多組只包含少量用戶(hù)，因此如果將10 000個(gè)用戶(hù)節(jié)點(diǎn)全部可視化，會(huì)有很多分散的節(jié)點(diǎn)。為了便于可視化展示與分析，選取用戶(hù)數(shù)量大于100 的組別（一共14 組）來(lái)進(jìn)行用戶(hù)節(jié)點(diǎn)的可視化，同時(shí)為不同組別的用戶(hù)節(jié)點(diǎn)分配不同的顏色。案例分別用傳統(tǒng)降維方法和多維度可視化方法進(jìn)行用戶(hù)節(jié)點(diǎn)的可視化展示。如圖8所示，每種顏色代表一種組別，在圖8（a）中，用戶(hù)節(jié)點(diǎn)分布混亂，節(jié)點(diǎn)的組別信息難以體現(xiàn)，而在圖8（b）中可以看到具有相同組別屬性的用戶(hù)節(jié)點(diǎn)形成了聚集簇，尤其是紅、藍(lán)、紫、黑、黃色節(jié)點(diǎn)聚類(lèi)明顯。圖8（b）的可視化展示中，可以挖掘的信息和新知識(shí)：（1）藍(lán)色和紫色簇有部分重疊，經(jīng)過(guò)分析用戶(hù)的實(shí)際組別信息，發(fā)現(xiàn)藍(lán)色和紫色組的信息相似，因此兩類(lèi)節(jié)點(diǎn)距離較近。（2）圖中有幾類(lèi)組別的節(jié)點(diǎn)分布均勻，沒(méi)有形成聚類(lèi)簇（例如綠色、灰色節(jié)點(diǎn)），觀察實(shí)際數(shù)據(jù)，發(fā)現(xiàn)這些節(jié)點(diǎn)不僅僅屬于一個(gè)組別，所以它們很難形成統(tǒng)一的聚集簇。

圖8 用戶(hù)-組別關(guān)系空間信息挖掘

觀察圖7中機(jī)構(gòu)-地點(diǎn)的關(guān)系空間，發(fā)現(xiàn)所有機(jī)構(gòu)聚集成5 個(gè)簇，通過(guò)分析每一類(lèi)節(jié)點(diǎn)的具體位置信息時(shí)，發(fā)現(xiàn)了圖9中的信息：每一類(lèi)聚集簇的具體地點(diǎn)信息都屬于同一局部區(qū)域，多維可視化方法從精細(xì)化微觀信息（城市、國(guó)家信息）中發(fā)掘出了更加宏觀的信息（洲際信息）。由此可見(jiàn)，通過(guò)關(guān)系子空間的可視化展示，能夠從直觀的角度發(fā)現(xiàn)一些潛在的信息，從而幫助人們更好地理解網(wǎng)絡(luò)中的信息和挖掘新的知識(shí)。

圖9 機(jī)構(gòu)-地點(diǎn)關(guān)系空間信息挖掘

4 結(jié)束語(yǔ)

本文提出了一種基于動(dòng)態(tài)投影嵌入的多維度異質(zhì)網(wǎng)絡(luò)可視化方法。為了實(shí)現(xiàn)對(duì)異質(zhì)網(wǎng)絡(luò)更加完整和準(zhǔn)確的展示，本文首先提出了動(dòng)態(tài)投影嵌入的異質(zhì)網(wǎng)絡(luò)表示學(xué)習(xí)方法，此方法很好地學(xué)習(xí)到了異質(zhì)網(wǎng)絡(luò)中節(jié)點(diǎn)的不同屬性和關(guān)系信息，通過(guò)評(píng)估實(shí)驗(yàn)，發(fā)現(xiàn)動(dòng)態(tài)投影嵌入模型相對(duì)現(xiàn)有異質(zhì)網(wǎng)絡(luò)表示學(xué)習(xí)方法有較大提升；在動(dòng)態(tài)投影嵌入模型的基礎(chǔ)上，提出了多維度的異質(zhì)網(wǎng)絡(luò)可視化方法，為異質(zhì)網(wǎng)絡(luò)中不同關(guān)系分配不同的投影空間，在對(duì)異質(zhì)網(wǎng)絡(luò)進(jìn)行可視化時(shí)，根據(jù)節(jié)點(diǎn)的不同屬性，將節(jié)點(diǎn)映射至不同的關(guān)系空間，在具體的子空間中進(jìn)行可視化展示與分析，從而挖掘節(jié)點(diǎn)的不同屬性信息。實(shí)驗(yàn)證明，本文提出的方法相對(duì)傳統(tǒng)的方法不僅在可視化展示效果上更加清晰完整，而且對(duì)于協(xié)助人們挖掘異質(zhì)網(wǎng)絡(luò)潛在的信息和知識(shí)可以發(fā)揮關(guān)鍵性作用。