物体和物体之间的联系构成网络，这样的联系无处不在，网络是一种灵活而通用的数据结构. 在现实世界中，许多类型的数据都可以抽象成网络，如社交网络、公路网络、万维网、物联网、生物网络、语言网络等. 对网络进行分析可以提取有价值的信息，其中一个重要的问题就是如何对数据进行表示. 网络表示学习给网络分析任务带来极大的便利，也是网络原始数据和网络应用任务的桥梁^[1].

网络表示学习将原始高维、稀疏的网络投射到一个低维、稠密的空间中，并保留原始网络中的结构特性. 一个好的网络表示学习算法能够保留节点在原网络中的局部特性和全局特性. 现有网络表示学习算法可大致分为基于特征向量的算法^[2-8]（由于高计算复杂度，这一系列算法很难应用于大规模网络）、基于神经网络的算法^[9-11]、基于矩阵分解的算法^[12-13]以及基于社区发现的算法^[14].

现实中的许多网络，如（digital bibliography and library project，DBLP）^[15]、AMiner^[16]等，其中的节点和边包含多种类型，是典型的异构信息网络. 如何对异构信息网络中的节点或者边进行有效的表示学习是一个困难且有挑战性的问题. 与同构网络相比，对异构信息网络进行有效的表示学习更加困难，有研究者已进行相关研究^[17-18]. Dong等^[19]通过元路径的方式来指导随机游走，构造节点的邻居节点集合，然后基于异质的skip-gram模型得到节点的向量表示.

已有研究主要针对同构网络，对异构信息网络的相关研究较少.本文针对异构信息网络中节点和节点间链接关系类型不同的特点，选取典型的异构信息例子，对异构信息网络中节点相似性大小进行建模，利用深度学习提取复杂特征的特点，对传播概率矩阵进行降维，研究基于传播概率矩阵的异构信息网络表示学习算法在分类、聚类、可视化上的效果.

基于传播概率矩阵的异构信息网络表示学习（heterogeneous information network representation learning based on transition probability matrix，HINtpm）的相关定义如下.

定义1　异构信息网络（heterogeneous information network，HIN）：给定一个图 ${{G}} = \left\langle {{{V}},{{E}}} \right\rangle $，用 ${{V}} = \{ {v_1},{v_2}, \cdots ,{v_n}\} $ 表示顶点集合，用 ${{E}} = \left\{ {{e_i}_{,j}} \right\}$ 表示2个顶点的边集合. 用映射函数 ${{\phi }}:{{V}} \to {{L}}$ 表示每个顶点 ${{v}} {}$ 属于顶点类型集合V，即 ${{L}}:{{\phi }} ({{v}}) \in {{L}}$. 用映射函数 ${{\psi }}:{{E}} \to {{R}}$ 表示每条边 ${{e}} {}$ 属于边的类型集合E，即 ${{R}}:{{\psi }}\left( e \right) \in {{R}}$. 其中 $\left| {{L}} \right| > 1$ 或 $\left| {{R}} \right| > 1$，即顶点类型和边类型个数都大于1. 一个典型异构信息网络例子如图1所示. 作者和论文之间的链接关系是“写”与“被写”，论文和术语之间的链接关系是“提及”与“被提及”，论文和论文之间是“引用”与“被引用”，论文和刊物（即会议/期刊）之间是“出版”与“被出版”.

定义2　异构信息网络模式（HIN Schema）：给定一个HIN G=（V，E），映射函数 $\phi :V \to L$ 和 $\psi :E \to R$，则网络模式为 ${T_G} = \left( {L,R} \right)$，L是顶点类型，R是边类型.DBLP数据集元模式如图2所示.

定义3　元路径Meta Path：给定HIN G=（V，E），元路径Path是定义在网络模式T_G=（L，R）上的：

(1) ${{\rm{Path}}} = l_{1}\xrightarrow{{r_1}}l_{2} \to \cdots\to l_{n - 1}\xrightarrow{{r_{n - 1}}}l_n.$

定义4　邻接矩阵W：在图G中，对于一个无权重的无向图而言，仅当顶点V_i和顶点V_j之间存在一条边时W_ij=1，否则W_ij=0.

定义5　度数矩阵D是一个对角矩阵，矩阵每一行对角线上的值均为邻接矩阵W每一行的和，其余值为0.

定义6　一阶相似性：在同构信息网络中，一阶相似性由直接相连的节点决定，权重越大，节点越相似.

定义7　二阶相似性：在同构信息网络中，二阶相似性由相邻节点共同邻居的个数来决定，共同邻居数量越多，认为相邻的2个节点相似性越高.

同构信息网络上节点的相似性可通过共同邻居个数、传播概率矩阵等来计算，但是该计算方法忽略了对象和链接间类型的细微区别. 因为异构信息网络中节点和链接具有多样性，所以在异构信息网络中不能直接应用同构网络中的相似性规则. 即使是相同的对象，在不同的元路径下语义也不同，而不区分语义地评价相似性是没有意义的，且不是所有节点间的相似性大小都有意义和可解释的.

异构信息网络中节点相似性大小可以通过元路径来计算，因此可以用元路径上节点传播概率矩阵的相似性度量来表示节点相似性大小. 然而，多数应用场景都是寻找网络中相似的对等对象，即对象类型相同，如寻找领域内相似的作者，寻找风格相似的演员，或者寻找功能相同和受欢迎程度相似的产品. 同种类型的对象间的关系是对称的， HINtpm算法限定于对称的元路径.

利用元路径来计算节点相似性的算法还有PathSim^[22]，可以捕捉到对等对象之间的细微之处，为对称路径给定一对称的元路径P. 对于同类型对象x和y之间的PathSim定义如下：

(2) $\begin{split}s\left( {x,y} \right) = \frac{{2\times|\{ p_{x \to x}:p_{x \to y} \in p\} |}}{{|\{ p_{x \to x}:p_{x \to x} \in p\} | + |\{ p_{y \to y}:p_{y \to y} \in p\} |}}.\end{split}$

式中： $p_{x \to x}$、 $p_{x \to y}$、 $p_{y \to y}$ 分别是x与x、x与y、y与y之间的路径实例. 该定义表明给定元路径Path，s（x，y）取决于两部分：1）由x和y之间符合Path的路径数量确定的连通性；2）对象可见性的平衡，对象可见性由对象到自身符合Path的路径实例数量确定. 将路径实例出现的次数作为路径实例的权重，即路径实例中所有链接权重的乘积.

为了计算节点相似性，给定一条如式（1）所示的元路径. 定义W_ij为l_i、l_j的邻接矩阵，则元路径上的可交换矩阵可由邻接矩阵相乘得到：

(3) ${{{M}}_{{\rm{Path}}}} = {{{W}}_{12}}{{{W}}_{23}}\cdots{{{W}}_{\left( {n - 1} \right)n}}{{{W}}_{\left( {n - 1} \right)n}}^{\rm{T}}\cdots{{{W}}_{23}}^{\rm{T}}{{{W}}_{12}}^{\rm{T}}.$

例如DBLP数据集中选取元路径A-P-C-P-A（如图3所示），其中A代表作者，P代表论文，C代表会议. W_AP表示A、P的邻接矩阵，则可交换矩阵：

(4) $ {{{M}}_{\rm APCPA}} = {{{W}}_{\rm AP}}{{{W}}_{\rm PC}}{{{W}}_{\rm PC}}^{\rm{T}}{{{W}}_{\rm AP}}^{\rm{T}}. $

根据定义5，可得度数矩阵：

(5) ${{{D}}_{mn}} = \left\{ \begin{array}{l} \displaystyle\sum\nolimits_n {{{{K}}_{mn}}} ,\;\;\;\;\;{\rm{ }} \; m = n; \\ {\rm{0,}}\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\rm{}} \; m \ne n. \end{array} \right.$

其中，K为同构网络中节点的邻接矩阵，|K|=m=n.

将式（5）改进为适合异构信息网络的度数矩阵：

(6) ${{{D}}_{ij}} = \left\{ \begin{array}{l} \displaystyle\sum\nolimits_j {{{M}}_{ij}} ,\;\;\;\;{\rm{ }} \; i = j;\\ {\rm{0}},\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\rm{}} \; i \ne j. \end{array} \right.$

式中：M为可交换矩阵，例如元路径为A-P-C-P-A. 假设在邻接矩阵W_ij中，从顶点l_i到顶点l_j的传播概率是成比例的，则适合异构信息网络的传播概率矩阵为

(7) ${{S}} = {{{D}}^{ - 1}}M.$

节点间一阶、二阶相似性大小定义如图4所示，关注黑色节点间相似性大小.根据定义6可知，假设图4（a）中的权重比图4（c）中的权重要大，那么图4（a）中的2个节点更相似. 根据定义7可知，图4（b）中的权重比图4（d）中的权重要大，即图4（b）中的2个节点更相似.

将同构信息网络中一阶相似性、二阶相似性推广到异构信息网络中节点的一阶相似性、二阶相似性. 定义异构信息网络节点一阶相似性大小为异构信息网络中元路径上相邻的同类型的节点间的传播概率大小.定义异构信息网络节点二阶相似性大小为异构信息网络中元路径上间隔一个同类型的节点间的传播概率大小.

深度学习采用非线性的激活函数，使得深度学习算法能提取非线性的复杂特征，正好可以用来提取传播概率矩阵中的非线性的特征，达到降维的目的.

自动编码器能自动提取输入数据中的特征，是一种无监督的学习算法，使用反向传播算法，并让目标值等于输入值. 自动编码器分为2个部分：编码和解码. 在编码阶段，将输入数据通过函数 ${f_{\theta_1} }( \cdot )$ 进行编码，经过激活函数送入下一层；在解码阶段，通过函数 ${g_{\theta_2} }( \cdot )$ 对被编码后的数据进行解码，使解码后的数据等于输入数据. 编码函数和解码函数如下：

(8) ${f_{{\theta _1}}}({{x}}) = \sigma ({w_1}x + {b_1}),$

(9) ${g_{{\theta _2}}}({{y}}) = \sigma ({w_2}y + {b_2}).$

式中： $\sigma ( \cdot )$ 为激活函数，w₁（w₂）和b₁（b₂）分别为编码（解码）期间的权重和偏置. 通过找到合适的 ${\theta _1}$ 和 ${\theta _2}$ 来最小化重构损失函数：

$\sum\limits_{{i}} {L({x^{(i)}},{g_{{\theta _2}}}({f_{{\theta _1}}}({x^{(i)}})))} .$

其中， ${x^{( i)}}$ 为第i个实例.

损失函数采用平方差，即输入层和重构层实例差值的平方：

(10) $L = \frac{1}{a}\sum\limits_{i = 1}^a {|{g_{{\theta _2}}}({y^{(i)}}) - {x^{(i)}}{|^2}} .$

式中：a为实例总数. 模型HINtpm采用的是降噪自动编码，即在输入的数据加上噪声以使训练的数据接近测试数据，增加降噪自动编码器的鲁棒性，防止过拟合.

使用的激活函数为ReLU：

(11) $\varphi ({x^{(i)}}) = \max\; (0,{x^{(i)}}).$

降噪自动编码器模型如图5所示。

综上，完整HINtpm算法的流程如下.

输入　HIN G=（V，E）.

1. 得到邻接矩阵 ${{{W}}_{12}}{{{W}}_{23}}...{{{W}}_{\left( {n - 1} \right)n}}.$

2. 计算可交换矩阵：

${{{M}}_{\rm Path}} = {{{W}}_{12}}{{{W}}_{23}}\cdots{{{W}}_{\left( {n - 1} \right)n}}{{{W}}_{\left( {n - 1} \right)n}}^{\rm{T}}\cdots{{{W}}_{23}}^{\rm{T}}{{{W}}_{12}}^{\rm{T}}.$

3. 计算度数矩阵：

${{{D}}_{ij}} = \left\{ \begin{array}{l} \displaystyle\sum\nolimits_j {{{M}}_{ij}} ,\;\;\;\;{\rm{ }} \; i = j;\\ {\rm{0}},\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\rm{ }} \; i \ne j. \end{array} \right.$

4. 计算概率矩阵 ${{S}} = {{{D}}^{ - 1}}{{M}}.$

5. 一阶相似性：S₁=S；计算二阶相似性：S₂=S₁S₁^T，计算传播概率矩阵S_t=S₁+S₂。

用降噪自动编码器对S_t进行降维。设置降噪自动编码器学习率learningrate=0.001，隐藏层维度为128，每批训练向量大小batchsize=64.

输出　网络节点的向量表示.

（1）DBLP数据集.

从DBLP数据集中抽取一个子网络，子网络中有1 586位作者以及这些作者的10 353篇论文，其中的论文来自18个会议；作者来自4个领域：Data Base数据库、Information Retrieval信息检索、Data Mining数据挖掘、Machine Learning机器学习.

（2）AMiner数据集.

实验时，从AMiner中抽取一个子网络. 子网络包括来自4个不同领域的4 000位作者，75 184篇论文.

（3）HINtpm参数设置.

降噪自动编码器隐藏层的维度为128维，即所得节点表示的维度为128维. 实验中，在2个数据集上选取的元路径都为A-P-C-P-A，由于是对作者进行分类聚类，根据经验认为，在相同领域上发表论文数量越多的作者为同个类别的可能性更大.

（1）DeepWalk.

受到自然语言word2vec的启发，Perozzi等于2014年提出DeepWalk^[20]. DeepWalk在网络中截断随机游走得到很多序列，这些序列相当于自然语言中的句子,然后对序列中的节点对用层级softmax和Skip-gram进行概率建模，使序列似然概率最大，通过随机梯度下降学习参数. 实验中，使用默认参数设置，例如窗口大小w=5，随机游走序列长度t=40，节点表示的维度为128.

（2）Node2vec.

Node2vec^[21]定义了2个参数p和q，使随机游走在BFS和DFS中达到一个平衡，能保留节点局部和宏观的信息，具有很高的适应性. 实验中使用默认参数设置，p=q=1.0，所得节点表示的维度为128.

（3）Metapath2vec.

Metapath2vec通过元路径的方式来指导随机游走，构造节点的邻居节点集合，然后基于异质的skip-gram模型得到节点的向量表示. 节点表示维度为128，邻居节点大小为7，随机游走序列长度为150，负抽样大小为5.

分类算法为GBDT，使用的是sklearn包中默认的GBDT模型. 在数据集DBLP、AMiner上分别使用DeepWalk、Node2vec、metapath2vec、HINtpm算法进行实验，实验结果如表1、2所示. HINtpm0指的是直接对传播概率矩阵进行分类、聚类. 其中，R为数据集中训练集占总的数据集的比例，取10次实验结果的平均值. 标签为作者所属领域.

实验所用DBLP数据集以作者所属领域为标签，将数据集划分为训练集和验证集，训练集的百分比为10%~90%，如训练集为10%，则验证集百分比为90%，以此类推.如表1和2所示为不同训练集比例下GBDT正确分类作者的比例. 从表1、2中可以看出，在使用相同的分类模型、节点表示维度相同的条件下，将算法HINtpm、DeepWalk、Node2vec学习到的节点表示应用到分类任务效果中。结果表明：将算法HINtpm学习到的节点向量的表示用于分类任务效果良好，说明算法HINptm学习到了异构信息网络中节点类型不同的特征.

表1和2中“HINtpm0”表示在不同训练集比例下直接将传播概率矩阵用于分类的准确率。从表中可以看出，将得到的异构信息网络的传播概率矩阵直接应用到分类任务的效果优于用自动编码器进一步处理后的效果.由此可见，尽管降噪自动编码器能自动提取数据中复杂的特征，在对数据降维时仍然损失了部分信息.

聚类所用算法为K-Means，如表3所示为不同算法得到的节点表示的聚类效果，用NMI进行评价.

从表3可知，HINtpm算法得到的节点表示的聚类效果总体而言优于DeepWalk、Node2vec、Metapath2vec得到的节点表示的聚类效果.实验证明，HINtpm算法得到的节点表示可以用于异构信息网络聚类应用任务.

如图6所示为数据集AMiner通过各种算法得到的节点表示的可视化效果，实验所用AMiner数据集中作者领域有4个，图中不同颜色代表不同的领域.从图6（c）可知，DeepWalk算法得到的作者节点表示可视化后不同领域的作者之间的界限不清晰.从图6（b）可知，Node2vecs算法得到的作者节点向量表示可视化后类别与类别之间的界限较DeepWalk清晰.从图6（d）可知，metapath2vec算法得到的作者节点向量表示可视化后界限较为模糊.

DeepWalk和Node2vec算法没有考虑到异构信息网络中节点和边类型的多样性，在异构信息网络上不适用。从前面的实验结果可知，HINtpm算法能学习到异构信息网络中节点和边类型的不同.

本文介绍了一种基于概率传播矩阵的异构信息网络的表示学习算法，利用异构信息网络元路径上节点传播概率来表示节点相似性大小，然后对于得到的传播概率矩阵通过自动编码器的降维得到网络的节点表示. 实验证明：对比DeepWalk、Node2vec、metapath2vec算法，提出的HINtpm算法考虑了异构信息网络中节点的相异性，能很好地学习到异构信息网络中节点的表示，学习到的异构信息网络的节点表示在不同训练集比例下的节点分类准确率上有3%~24%的提升，在聚类NMI上有0~13%的提升. 但是，在本算法的计算过程中，随着节点数量的增加，矩阵维度线性增加；由于矩阵是整个直接存储在计算机内存中，计算机内存以节点数量的平方增加.