面向复杂网络的异构网络表示学习综述
颜铭江，董一鸿，苏江军，陈华辉，钱江波
（宁波大学信息科学与工程学院，浙江宁波 315211）
摘 要：异构信息网络包含丰富的节点信息和链接信息，具有复杂异质性、高稀疏性、属性高维性等特性，这些特性给网络表示学习任务带来了巨大的挑战。异构网络表示学习通过在嵌入过程中将多样化的异质信息和结构信息进行有效融合，学习得到更有利于下游机器学习任务的低维特征向量。从异构网络表示学习方法的研究粒度出发，对近年的研究现状进行了比较全面的分析和讨论。首先探讨网络表示学习的产生动机，阐述了近年的异构网络表示学习的研究历程；然后对具有代表性的算法模型进行分类讨论，归纳其主要的研究内容和所使用的嵌入技巧。最后给出了未来工作中异构网络表示学习可能的研究方向和比较有价值的研究内容。
关键字：网络表示学习；异构信息网络；图嵌入；图神经网络；异质信息
中图分类号：TP391
文献标识码：A
doi: 10.11959/j.issn.1000−0801.2021013
A survey of heterogeneous network reprentation
learning for complex networks
YAN Mingjiang, DONG Yihong, SU Jiangjun, CHEN Huahui, QIAN Jiangbo
Faculty of Electrical Engineering and Computer Science, Ningbo University, Ningbo 315211, China Abstract: Heterogeneous information networks contain rich information about node and link, and have some charac-teristics, such as complex heterogeneity, high sparsity, high-dimensionality of attributes, etc, which brings huge chal-lenges to network reprentation learning tasks. The heterogeneous network reprentation learning learns low-dimensional feature vectors that are more conducive to downstream machine learning tasks by effectively inte-grating diver heterogeneous information and structural information in the embedding process. It conducts a rela-tively comprehensive analysis and discussion of the rearch status in recent years, starting from the rearch granu-larity of the heterogeneous network reprentation learning method. Firstly, the motivation of network reprentation learning and the rearch history of heterogeneous information network reprentation learning in recent years was discusd. Then some reprentative algorithm models were classified, followed by the summary of their main re-arch contents and embedding skills. Finally, some possible directions and valuable contents of heterogeneous in-
收稿日期：2020−04−26；修回日期：2020−12−10
通信作者：董一鸿，******************
基金项目：浙江省自然科学基金资助项目（No.LY20F020009，No.LZ20F020001）；国家自然科学基金资助项目（No.61572266）；宁波市自然科学基金资助项目（No.202003N4086）
Foundation Items: The Natural Science Foundation of Zhejiang Province (No.LY20F020009, No.LZ20F020001), The National Natural
Science Foundation of China (No.61572266), Ningbo Natural Science Foundation (No.202003N4086)
综述
·2·
formation network reprentation learning rearch in future work were listed.
Key words: network reprentation learning, heterogeneous information network, graph embedding, graph neural network, heterogeneous information
1 引言
互联网基础建设的快速发展使各种线下信息数字化，导致可利用信息呈爆炸式增长。这些庞大数据中多样化实体和实体间关联构成了一系列不同的信息网络，如社交网络[1-2]、生物分子网络[3]等，催生了针对网络数据进行数据挖掘的研究。网络表示学习[4]（network reprentation learning/ network embedding ，NRL ）又称为图嵌入，是为了能有效地进行信息网络数据挖掘任务而产生的研究方法。网络表示学习依据相关优化目标，将具有高维复杂信息的网络中实体节点映射到低维向量空间中，并能保留原始网络中节点信息与网络结构信息，之后将映射后的低维向量应用于各种机器学习任务，比如节点分类[5-6]、可视化[7]、推荐系统[8-9]等。最开始对于网络的研究是从网络的拓扑结构出发的，忽略网络中节点和关系的类型信息，即将网络视为同构网络以矩阵分解[10]的方式利用邻接矩阵实现节点嵌入。
然而，真实网络中包含的节点类型是多样化的，节点之间也存在着不同含义的作用关系，这种复杂的内容单纯依靠传统网络学习方法是无法提取的。另外，这种信息多样化的异构信息网络中还包含描述节点自身特征的属性信息，如文本、图像等，因此需要有效的方式对这些信息进行融合学习。异构网络表示学习通过融合节点属性信
息和网络结构信息，探索各种异质信息之间的潜在作用关系，在网络结构的基础上捕捉节点的微观特性，以获取保留信息量更多的节点嵌入，提高任务性能，其整体学习框架如图1所示。
对真实异构网络进行表示学习主要有3个优点：（1）有效缓解现实世界网络数据的高稀疏性、高维性问题，通过学习将异构信息网络中的节点和边都转化为低维稠密向量，降低了存储空间和节点间度量复杂度；（2）有效解决真实网络中异质信息的融合利用，通过异构信息网络表示学习模型能将不同类型节点映射到统一的低维向量空间中，有效融合节点属性信息和节点间的关系信息，提高了嵌入有效性；（3）有效控制计算复杂度，异构信息网络表示学习模型在设计时同时考虑大规模网络问题，保证信息融合的计算复杂度。这些优点更加符合实际应用中的工作需求，使异构网络表示学习成为目前网络表示学习中的研究热点。
2 异构信息网络表示学习发展
在早期同构网络表示学习的研究过程中，基于矩阵分解的算法由于计算复杂度过高不适用于大规模网络表示学习。后来受自然语言处理的启发，
DeepWalk
[11]开始利用游走和Skip-gram 结合的方式从序列中节点共现的角度学习节点嵌入；Node2vec [12]进一步改进游走方式，同时捕捉局部
图1 异构信息网络表示学习框架
·3·电信科学 2021年第2期
和全局结构信息；LINE[13]则是从节点对间一阶相似性和二阶相似性出发学习节点嵌入；GraphWave[14]通过小波扩散的方式学习节点结构特征，将小波视为图上概率分布。以上这些方式都是从网络结构的相似性出发，不同的是：Node2vec和GraphWave分别通过偏向游走和小波扩散的方式捕捉网络结构，而LINE则是非常直接地保留目标节点对之间的结构相似度。但是，随着同构网络研究的不断发展，研究者们发现单纯拓扑结构已经很难再对网络嵌入性能有更高的提升，而真实网络中随处可见的异质信息（如实体附带的属性、文本信息）以及实体间的语义信息在嵌入过程中并没有得到有效的利用。
异构信息网络表示学习便是从网络中这些复杂的异质信息出发，将网络的拓扑结构信息与多种异质信息进行有效的融合嵌入，并且能有效解决异构信息网络高稀疏性、高异质性等特点。由于异构信息网络中节点类型和关系类型是最基本的异质信息，受DeepWalk在同构网络中随机游走策略的启发，研究者们利用节点类型和关系类型设计元路径来指导随机游走方式，保留节点间具有人工经验的语义信
息，Metapath2vec[15]、HINE[16]等便是利用此种方式实现对节点间特定关系的保留。DDRW[17]等则将截断的随机游走与层级Softmax进行结合，配合分类目标函数捕获节点的相似性。ProxEmbed[18]等利用LSTM具有时间记忆性的特点，意图将随机游走序列模拟为节点间的“时间”演化过程匹配LSTM输入，同时在嵌入过程中考虑节点异质性。HNE[19]、PTE[20]等方法从简化嵌入的角度出发，将原始异构信息网络根据不同内容拆分为多个子图进行独立嵌入。由于神经网络在计算机视觉领域迅速发展，并取得了非常不错的成果，研究者们开始尝试将相关方法应用到网络表示学习过程中，实现端到端学习。比如PinSage[21]借鉴卷积方式探索节点间的消息传递；DKN[22]受迁移学习的启发，利用现有知识图谱模型和CNN实现新闻推荐；HeGAN[23]等利用GAN提高网络嵌入的鲁棒性。
3 相关概念
定义 1 （异构信息网络[24]）异构信息网络本质是一个图，其中V和E分别代表了节点集合和边集合，每个节点的属性特征向量x构成一个属性特征矩阵X，并且G关联一个节点类型映射函数:V A
ϕ→和一个边类型映射函数:E R
φ→，其中A和R分别代表了节点类型集合和边类型集合，且2
A R
+>。
为了学习异构网络中具有异质性的拓扑结构，设计符合异构网络的随机游走策略是十分必要的，因此许多工作中引入了人工经验，提出了元路径的概念。
定义2 （元路径）假设元路径p是定义在异构网络中的一条路径，表示为：
12
121
n
R
R R
n
A A A
+
⎯⎯→⎯⎯→⎯⎯→
"，代表目标节点对11
(,)
n
A A
+
之间的一种复合关系
12n
R R R R
=°°°
"，
其中，°代表关系之间的复合算子，
i
A表示节点
类型，
i
R表示关系类型。
定义 3 （异构网络表示学习）给定异构信息网络作为模型输入，学习一个映射函数()d
f G→R，将原始网络映射到d维空间中，同时尽可能保留原始网络的结构信息和属性信息。其输出可以是整个网络G的表示向量，也可以是网络
中因子的表示向量，如节点v、边e、子图
sub
G等。
机关办公室
4 异构网络表示学习方法
本节从异构信息网络的研究内容出发，根据不同的研究内容和方式将现有异构网络表示学习方法分为4种：基于边采样的方法、基于随机游走的方法、基于子图的方法和基于图神经网络的方法。
4.1 基于边采样的方法
网络中的边代表了两个节点之间存在着某种
综述·4·关系，在网络表示学习的过程中，研究者们常将
边作为衡量两个节点是否相似的直接体现。在同
构网络中，类似LINE[13]的方法在通过边采样学习节点嵌入时只需要考虑节点间拓扑结构关系即可。但是在异构网络中，需要考虑多样化的边类型信息，比如社交网络中用户之间有朋友和敌对关系。如果只考虑节点间有边而不考虑边的类型，则无法区分社交网络中两个实体间具体关系，可能导致最终给目标推荐的用户是目标极为讨厌的对象，造成推荐失败。因此在从边采样角度出发进行节点嵌入时必须考虑不同语义关系带来的差异性，这样才能准确描述和保留节点间语义特性。
南京北京
HIN2vec[25]从语义关系预测出发，以hop
k−
的方式排列组合节点类型构造代表不同语义的元路径集合，然后将元路径看作不同的语义关系r，以三元组(,,)
u v r作为模型输入，将节点u和v以及关系r统一投影到d维空间中，通过预测节点对u和v之间存在关系r的概率优化节点嵌入和关系嵌入。NREP[26]将文献推荐问题转化为边预测问题，在边预测过程中同时融合节点内容信息、结构信息和隐藏的边信息，利用双线性乘积计算推荐的排名成绩，实现推荐任务。
与以上单纯预测节点语义关系的方法不同，Qu等[27]认为不同类型的边在边采样过程中的先后顺序可能会对最终的嵌入效果产生不同的影响。因此模型在采样过程中引入强化学习机制，划分计划模块和学习模块，前者根据LINE的评价结果计算类型采样价值Q p，后者利用查表和神经网络确定价值Q l，两者结合获取最优边采样类型序列。HEER[28]则认为不同语义关系可能会存在不兼容的问题，导致原本比较相近的节点在投影到低维向量空间后变得较为疏远。因此HEER将节点根据语义关系进行分组，然后进行独立嵌入，利用边向量定义节点对的类型接近度，用来度量边与类型的耦合程度：
*
*
T
T T
exp()
,(,)
exp()exp()
(,):
0,(,)
r
r
u
v
r
让气球飞起来
r uv
r uv r uv
r v P
u P
员工流失率r
g
逛夜市u v P
g g
S u v
u v P
μ
μμ
∈∈自给自足的意思
⎧
∈
⎪
+
⎪
=⎨
⎪
⎪∉
⎩
∑∑
（1）
其中，d
r
μ∈R表示边类型向量，
uv
g表示边向量。模型目的在于将节点映射到不同的语义空间中，每种语义空间代表一种度量角度，通过多个度量角度衡量节点之间的相似性，解决原单一度量空间中目标节点对可能由于语义关系不兼容导致相似性不明显的问题。
基于边采样的方法将关注点放在网络的局部结构特征，每次只涉及部分节点，计算复杂度低。另外，异构网络中的边采样以边的类型为主导，考虑节点间语义关系，更有利于完成类似社区内用户推荐等任务。但是边采样涉及的关系类型较为简单，难以推测复杂语义关系。
4.2 基于随机游走的方法
边采样只能感知网络的局部结构特征，无法充分捕获网络的全局结构特征。网络中比较相似的两个节点在拓扑结构中可能实际距离很远，边采样方式无法捕获这样的相似性。受DeepWalk[11]通过随机游走获取网络全局结构特征的启发，越来越多的研究者期望通过随机游走序列与现有自然语言处理模型的结合产生富有价值的节点向量，捕捉远距离情况下节点的相似性。为了能在异构信息网络随机游走过程中保留复杂的语义关系，Metapath2vec[15]引入人工经验的元路径作为随机游走的指导，并设计了异构Skip-gram区分中心节点v
不同类型t的上下文节点
t
c：
()
()()e argmax log|;,|;
工作月报怎么写e
c v
t
u v
V t t
X X
t t X X v V t T c N v
u V
p c v p c v
θ
θθ
∈
=
∑∑∑∑
εεε
（2）虽然这种方法在构造邻居节点时考虑了节点类型，但是在利用Softmax计算共现概率时并没
·5· 电信科学 2021年第2期
有考虑节点类型信息带来的影响。因此在原始模型的基础之上进一步改进异构Skip-gram 模型概率计算，设计考虑节点类型的负采样，使Softmax 计算时只考虑特定类型节点，降低计算复杂度：
e (|;)=e c v
t u v
t t t
X X t X X u V p c v θ⋅⋅∈∑
（3）
类似地，HINE
[16]
引入元路径指导随机游走，
计算目标节点对(,)u v 在元路径中的节点相似度
(,)s u v 和在原始网络中的节点相似度(,)p u v ，通过最小化两种相似度的KL 散度优化节点嵌入。
Yin 等[29]则考虑节点对之间存在多条不同元路径的情况，以节点类型作为分组依据，基于Attention 计算不同元路径中同类型节点权值，然后利用
DeepWalk 的方式优化节点嵌入。HAN [30]借鉴GATs [31]考虑异构信息网络中节点类型影响程度，通过节点级别和语义级别Attention 分别评估节点类型和元路径在嵌入过程中的重要程度，实现对不同任务中网络节点类型贡献度的探索。
CAHNE [32]与前几种方法不同，采用BFS 的方式产生节点上下文序列，将根节点设置为锚点，模仿NF 和IDF 定义节点重要程度概率分布，利用结构信息和节点重要程度的KL 散度优化嵌入。与之类似的UniLPF [33]提出普适链路预测模型用于预测学术网络中相同或不同实体类型间的任意类型关系，利
用BFS 实现自动化元路径查询方法，并在计算基于元路径的节点对相似度时考虑时态信息和内容相关性的影响。D2AGE [34]通过BFS 的方式将节点对(,)u v 之间产生的多条随机游走
路径()1,{,,}l p u v p p ="重新组合成有向无环图
(,)D u v ，利用LSTM 对节点序列进行顺序嵌入，将尾部输出作为节点对(u ,v )的相似度嵌入计算相似度评分。在嵌入过程中，每个LSTM 单元输入前会将当前节点i v 与前驱节点嵌入R i 利用最大池化操作进行初步聚合，同时考虑前驱节点的实际距离dist ：
.dist maxPool({e :})i k R k i h h k R α−×=∈
（4）阴阳师红鬼哪里多
基于随机游走的方法能有效捕获远距离节点的相似度信息，同时也能将节点属性信息和局部结构特征融入嵌入过程中，提高信息保留量。由于随机游走带来的感受野非常大，并且能非常灵活地融入各种辅助信息，因此是当前的研究热点。
4.3 基于子图的方法
随着网络表示学习的深入，越来越多的研究发现随机游走产生的路径结果非常具有局限性，可能会造
成原有关系的截断，导致一些语义信息的丢失，因此，D2AGE 利用BFS 构造有向无环图融合多条游走路径，减缓关系截断问题。IPE [35]在此基础上改进有向无环图的构造方式，以先添边再去环的方式进一步减缓关系截断带来的信息损失。类似工作的SPE [36]则是以用户节点作为研究主体，将用户节点间的多条边进行统计归并形成子图模式(,)m m m C E =。SPE 子图模式i m 如图2所示，最终形成子图增广路径12path:(:1,:1,s m m −
31514:1)(:1,:2)(:1,:1)m m m m m →→，其中m C 代表节点类型集合，m E 代表边集合，path s −
中的
图2 SPE 子图模式m i
