基于動態投影嵌入的多維異質網絡可視化研究

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

1.中國科學院 空天信息創新研究院，北京100094

2.中國科學院 網絡信息體系技術重點實驗室，北京100190

3.中國科學院大學 電子電氣與通信工程學院，北京100049

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

可視化與可視分析旨在通過視覺手段獲取研究目標的直觀信息并且通過視覺分析方法來挖掘目標數據中的隱藏信息[3]。現代的主流觀點認為數據可視化按照類別分為科學可視化和信息可視化兩個主要分支。本文要研究的網絡可視化就是信息可視化的重要組成部分。信息可視化以抽象的、非結構化數據為主要研究對象，通常在二維空間進行可視化展示。

本文針對異質網絡可視化進行研究，異質網絡可視化通常涉及異質信息的處理以及高維數據的降維處理等技術手段。傳統的網絡可視化技術對于異質網絡可視化來說可視效果并不樂觀。例如節點-鏈接法[3]通過將節點間的關系用線段連接起來重構網絡的結構，主要采用布局算法來對網絡數據進行可視化展示，但是這種方法將包含不同屬性的異質網絡節點布局在一個空間，造成了布局效果混亂、異質信息難以體現的結果。相鄰矩陣法[3]通過構建節點間的關系矩陣來對網絡進行可視化展示，但是當網絡節點眾多且相鄰矩陣稀疏時，每個節點對應一個高維稀疏向量，通常需要采用降維算法來進行降維處理。

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

1 相關工作

網絡可視化的核心是網絡布局算法，因此很多研究者對網絡布局進行了深入的探索。節點鏈接法主要有力引導布局算法（Force-directed Layout）、多維尺度分析布局算法（MDS）以及弧長鏈接圖算法。具體工作有：Eades[5]最早提出力引導布局算法，之后研究者豐富了節點之間的物理模型，提出了能量模型[6]。為了改進力引導布局只能實現局部優化這一缺點，FADE算法利用四叉樹分解來降低時間復雜度[7]。多維尺度布局算法從根本上彌補了力引導布局算法的局限性。但MDS多針對高維數據，所以需要采用降維方法將高維數據映射至低維空間，因此引出另一個重要的研究方向——高維數據可視化。常見的高維數據降維方法有PCA[8]、t-SNE[9-10]、UMAP[11]、LargeVis[12]等等，經過高維數據降維處理后，得到2維或3維向量表示，進而實現高維數據可視化。

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

2 方法介紹

2.1 異質網絡可視化方法整體流程

如圖1 所示，首先提出動態投影嵌入模型，學習異質網絡節點的表示，然后將得到的表示向量通過多維度投影映射至不同空間進行降維處理，進而實現異質網絡的多維度（空間）可視化，最后通過觀察分析手段發掘新信息新知識。

2.2 動態投影嵌入模型

圖1 異質網絡可視化方法整體流程圖

動態投影嵌入（Dynamic Projected Embedding，DPE）模型的核心在于構建投影空間，在投影空間內進行節點相似性度量，設計損失函數，最后進行訓練與更新。投影學習的關鍵在于投影矩陣的設計，投影矩陣的優劣決定了網絡表示學習效果的好壞。PME模型是典型的針對異質網絡的基于投影度量的表示學習方法，該方法為異質網絡的每一種關系映射一個投影矩陣，但是PME的投影矩陣僅和對應關系有關，對于該關系下的所有節點都相同，一種關系對應一個固定的投影矩陣。事實上，投影過程是一個節點和關系的交互過程，該過程不僅與關系有關而且與節點有關，同一種關系下的不同節點應該對應不同的投影矩陣。因此，為每一種關系下的每一個節點分配不同的投影矩陣，這也正是“動態投影”名稱的由來，即投影矩陣隨節點的不同而動態變化。本文提出的DPE模型中投影矩陣的設計兼具靈活性、合理性以及高效性。

如圖2 所示，以DBIS 異質網絡（主要包含作者、文章、機構三種類型節點以及三種關系）中的paper-author關系為例，圖2（a）展示了動態投影矩陣的構建，模型為異質網絡中的每個節點構建兩個向量，一個作為最終的表示向量，另一個是用來構造投影矩陣的投影向量；同時，為每一關系構造一個投影向量，用來構建投影矩陣。對于一個三元組(a,R2,p)，節點a由表示向量iae和投影向量表示，節點p由表示向量和投影向量表示，關系R2 由投影向量rpa表示。DPE 會為每個節點構建一個投影矩陣，節點a、p的投影矩陣如下：

式中，dr(va,vp)代表節點a、p在投影空間的相似性距離，fr(va,vp)代表加權后的相似性距離。事實上，在投影計算過程中，投影計算復雜度相對固定投影模型（PME）也有很大減少。以本文方法DPE和PME分別代表動態投影嵌入方法（Dynamic Projection Embedding，DPE）和固定投影嵌入方法（Fixed Projection Embedding，FPE）來對投影計算復雜度進行分析。以式（5）為例，DPE模型計算投影空間內兩點的相似距離如下：

圖2 DPE模型的原理圖

可以看到動態投影嵌入模型相對以前的投影度量模型計算復雜度減少了一個數量級，具有更快的訓練學習速度，因此本文提出的DPE模型中投影矩陣的設計兼具靈活性、合理性以及高效性。

模型希望有聯系的節點在投影空間中盡可能地靠近，而沒有聯系的節點盡可能地遠離，因此，提出了如下損失函數：

其中，Dr表示關系r下的有鏈接的正樣本集合，表示關系r下針對某一節點對產生的負樣本集合。模型采用雙向負采樣策略，為每一個節點對生成兩種類型的負樣本。由此，得到采用負采樣策略的損失函數：

最終，最小化如下目標函數：

多次訓練迭代之后，得到網絡的表示向量，具體包括每一個節點的表示向量ie和投影向量ip，以及每一種關系的投影向量rp。節點的表示向量ie是最終需要的結果，但是在特定任務中節點和關系的投影向量也會起到至關重要的作用。在多維度異質網絡可視化方法中，就需要結合DPE模型輸出的這三類向量進行具體可視化方法的設計。

2.3 多維度異質網絡可視化方法

對異質網絡的可視化，常規可視化方法在得到表示向量后通過降維方法，得到節點的低維表示向量（坐標），然后進行2D、3D可視化展示。但是這種可視化方法對于異質信息網絡的展現效果并不理想，因為它將包含復雜屬性信息的節點可視化于同一空間，節點分布混亂，不能體現節點的語義信息。為了克服異質信息網絡這種固有可視化方法的弊端，本文提出一種全新的可視化方法，如圖3所示。提出的網絡可視化方法認為異質網絡中的節點是包含多種屬性的復雜節點，節點的不同屬性導致了節點間的不同關系。因此將得到的節點向量根據不同關系，通過投影計算分別映射到不同的子空間，從而得到不同關系空間中的節點表示，可以認為每種關系空間嵌入了節點的某種屬性，這樣在每個關系空間中就可以針對某些特性進行節點信息挖掘。

本文通過DBIS數據集來闡述多維度異質網絡的可視化方案。如圖4所示，可視化方法的具體步驟如下：

（1）如圖4（a）所示，通過動態投影嵌入模型得到網絡的表示向量，具體包括節點投影向量ip和節點表示向量ie，關系投影向量rp。其中節點投影向量ip與關系投影向量rp用于構建投影矩陣。

（2）圖4（b）展示了本文方法如何根據節點與關系進行多維度的可視空間劃分。具體如下：對于每一類型的節點，本文方法都會根據包含當前類型節點的關系構建對應的投影子空間。例如，對于作者(a)節點，作者存在于作者-作者(a-a)，作者-文章(p-a)關系中，所以作者類型的節點將可視化在對應的兩個投影空間中。文章(p)與會議(c)類型節點也采用相同方法。

（3）在構建了每一類型節點的投影空間后，利用節點投影向量ip和節點表示向量ie，關系投影向量rp通過投影計算得到每個節點在不同投影關系空間下的高維表示向量。投影計算思想與DPE模型相同，以作者節點為例的投影計算具體如下：

圖3 可視化方法對比圖

圖4 可視化方法流程圖

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

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

（5）在得到可視化結果后，通過分析不同關系空間的可視化結果，探索節點在不同空間中的不同特性，當然，經過更加深入的分析，更多的新信息和新知識有待挖掘，在實驗部分將進行詳細分析以及案例介紹。

3 實驗與評估

3.1 實驗數據集

本文采用了三個異質網絡常用數據集，包括You-Tube 數據集、DBIS 數據集以及領域知識圖譜（Domain Knowledge Graph，DKG）數據集。YouTube數據集主要包含YouTube 中的用戶和分組兩種類型節點以及兩種關系。DBIS數據集主要包含作者、文章、機構三種類型節點以及三種關系。DKG數據集通過抽取某領域知識圖譜的部分圖譜數據處理后得到，具體包括機構、人物、地點、國家、裝備5 類節點，以及機構-機構、機構-人物、機構-地點、人物-國家、機構-國家等14類關系。數據集的具體統計信息見表1～3。

表1 YouTube數據集統計數據

表2 DBIS數據集統計數據

表3 所有數據集統計數據

3.2 實驗設計與對比方法

對于異質網絡表示學習效果驗證了本文設計的鏈接預測任務。鏈接預測任務用已有的一些鏈接來學習網絡表示模型，然后預測那些未知的鏈接。在鏈接預測實驗中，采用MRR 指標來評估鏈接預測任務效果。MRR（Mean Reciprocal Rank）稱作平均倒數排名，對于一個正樣本，為其生成眾多負樣本，然后計算所有樣本的得分并進行排名，將正樣本的排名取倒數然后求平均（MRR不大于1），因此，MRR越大模型表現越好。MRR計算公式如下：

實驗中將提出的動態投影嵌入模型（DPE）與現有的一些網絡表示學習方法進行對比，相關算法有：LINE[21]（實驗中采用LINE-2nd）、Node2vec[16]（隨機游走長度設為100，節點游走數為10，滑動窗口大小設為2，p=1,q=1）、Hin2vec[18]（隨機游走的設置與Node2vec相同）以及PME[19]。

在異質網絡可視化實驗中，分別在YouTube和DKG數據集上采用力引導布局算法直接進行可視化，具體包括Fast Multipole Embedder 算法、FM3 算法[22]、FR 算法[6]、KK 算法[23]，然后采用網絡表示學習方法與降維方法結合的方式（例如：LINE+t-SNE、Node2vec+t-SNE、PME+t-SNE以及DPE+t-SNE）進行對比實驗，文中擇優選取了DPE+t-SNE（節點的表示向量只選ie）作為傳統的降維可視化方法與本文提出的多維度可視化方法進行對比。本文從可視化展示的定性分析來評估多維異質網絡的可視化方法，包括可視化效果以及案例分析。

3.3 實驗結果與分析

3.3.1 異質網絡的表示學習

首先訓練數據集得到網絡的表示向量，本文為所有方法設置如下參數：表示向量維度為128，負采樣數目為5。在鏈接預測任務中，訓練集與測試集比例為9∶1。表4展示了鏈接預測任務在YouTube數據集和DBIS數據集上的實驗結果。從表4可以發現如下結論：

（1）動態投影嵌入模型相對現有異質網絡表示學習方法取得了最好效果，證明了本文提出的動態投影嵌入模型很好地保持了原有網絡的信息，也為后續可視化任務奠定了良好的基礎。

（2）由于實驗數據集具有很強的稀疏性，但是DPE仍然相較已有的方法取得了很好的表現，可以看出模型在稀疏網絡數據上具有較強的魯棒性。

表4 鏈接預測任務的MRR指標

3.3.2 異質網絡可視化

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

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

圖5 Youtube數據集可視化圖

圖6 DKG數據集傳統布局算法與降維算法可視化圖

圖7 DKG數據集本文方法可視化圖

表5 可視化方法的時間消耗 s

3.3.3 時間效率分析

本節分析了實驗中可視化方法的時間消耗問題。對比方法包括Fast Multipole Embedder 算法、FM3 算法、FR 算法、KK 算法以及采用網絡表示學習方法與降維方法結合的方法（PME+t-SNE、DPE+t-SNE）。統計了所有可視化方法在YouTube數據集和DKG數據集上的可視化所耗費時間。具體耗時統計如表5所示。

表5 中的時間統計均是取10 次實驗的平均值統計得到，由表可知：

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

表6 t-SNE算法的實驗參數

（2）對比后三種方法，可以看到本文提出的動態投影嵌入模型（DPE）相對傳統的網絡嵌入模型（PME）已經有了很大的效率提升，由于多維度可視化方法需要二次進行投影計算因此時間消耗略高于DPE+t-SNE 方法，但基本持平。因此本文方法在網絡嵌入與降維結合類可視化方法中達到了當前最優水平。

（3）由于結合類方法需要通過訓練迭代來學習網絡中的信息，然后通過降維的方式來進行可視化展示，因此時間消耗將大大增加，但是這類方法通過時間消耗換取了更深層次的信息獲取，因此同樣具有應用價值，在案例分析中將體現這一點。

3.4 案例分析

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

圖8 用戶-組別關系空間信息挖掘

觀察圖7中機構-地點的關系空間，發現所有機構聚集成5 個簇，通過分析每一類節點的具體位置信息時，發現了圖9中的信息：每一類聚集簇的具體地點信息都屬于同一局部區域，多維可視化方法從精細化微觀信息（城市、國家信息）中發掘出了更加宏觀的信息（洲際信息）。由此可見，通過關系子空間的可視化展示，能夠從直觀的角度發現一些潛在的信息，從而幫助人們更好地理解網絡中的信息和挖掘新的知識。

圖9 機構-地點關系空間信息挖掘

4 結束語

本文提出了一種基于動態投影嵌入的多維度異質網絡可視化方法。為了實現對異質網絡更加完整和準確的展示，本文首先提出了動態投影嵌入的異質網絡表示學習方法，此方法很好地學習到了異質網絡中節點的不同屬性和關系信息，通過評估實驗，發現動態投影嵌入模型相對現有異質網絡表示學習方法有較大提升；在動態投影嵌入模型的基礎上，提出了多維度的異質網絡可視化方法，為異質網絡中不同關系分配不同的投影空間，在對異質網絡進行可視化時，根據節點的不同屬性，將節點映射至不同的關系空間，在具體的子空間中進行可視化展示與分析，從而挖掘節點的不同屬性信息。實驗證明，本文提出的方法相對傳統的方法不僅在可視化展示效果上更加清晰完整，而且對于協助人們挖掘異質網絡潛在的信息和知識可以發揮關鍵性作用。