基于动态投影嵌入的多维异质网络可视化研究

余 磊，许光銮，王 洋，林道玉，李 峰

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 结束语

本文提出了一种基于动态投影嵌入的多维度异质网络可视化方法。为了实现对异质网络更加完整和准确的展示，本文首先提出了动态投影嵌入的异质网络表示学习方法，此方法很好地学习到了异质网络中节点的不同属性和关系信息，通过评估实验，发现动态投影嵌入模型相对现有异质网络表示学习方法有较大提升；在动态投影嵌入模型的基础上，提出了多维度的异质网络可视化方法，为异质网络中不同关系分配不同的投影空间，在对异质网络进行可视化时，根据节点的不同属性，将节点映射至不同的关系空间，在具体的子空间中进行可视化展示与分析，从而挖掘节点的不同属性信息。实验证明，本文提出的方法相对传统的方法不仅在可视化展示效果上更加清晰完整，而且对于协助人们挖掘异质网络潜在的信息和知识可以发挥关键性作用。