异质图 $V$ 定义为： $G = \{ V,E,T,\phi ,\psi \} $ 。其中 $V$ 和 $E$ 分别表示异质图中节点和边的集合，任意的节点 $v \in V$ 和边 $e \in E$ 分别有映射函数 $\phi (v):V \to {T_V}$ ， $\psi (v): E \to {T_E}$ ， $ {T_V} $ 和 $ {T_E} $ 分别是节点类型和边类型的集合。根据异质图的定义可知，它允许不同(或相同)类型节点间有不同(或相同)类型的连边，且允许节点和边带有属性。它包含了多种特殊结构的图，如：二部图、三部图、带权图等。图1a给出了异质图的一个实例，图中节点类型包括作者(A)、会议(C)、论文(P)，作者和论文之间的边表示“发表”，会议与论文间的边表示“收录”，论文与论文间的边表示“引用”。图1a展示了从3.2节所述开源数据集的语义中抽取得到的异质图，该数据集不提供作者−作者、会议−会议间的关系，因此图中作者、会议之间没有显示连边。若去掉论文−论文间的连边，该异质图将退化为三部图，许多学者基于三部图这一特殊异质图也进行了深入研究，得到了许多有趣的结论^[26]。

图  1  异质图与元路径实例

异质图上的随机游走不同于同质图，需根据领域知识制定游走规则，这一规则被称为“元路径”^[13]。元路径 ${\rm{Path}}$ 是定义在异质图 $G$ 上的特定序列： ${\rm{Path}} = {v_{{t_1}}}\xrightarrow{{{e_{{t_1}}}}}{v_{{t_2}}} \cdots \xrightarrow{{{e_{{t_{n - 1}}}}}}{v_{{t_n}}}$ ，即节点按照 ${\rm{Path}}$ 给出的序列进行游走： ${t_1}$ 类的节点 ${v_{{t_1}}}$ 沿着边 ${e_{{t_1}}}$ 游走到 ${t_2}$ 类的节点 ${v_{{t_2}}}$ ，以此类推。图1b给出了两种不同的元路径实例，A-P-A规定：从“作者”节点出发，下一步游走必须经过“论文”节点，“论文”节点下一步的游走则必须经过“作者”节点，该元路径可使同一篇论文的共同作者出现在同一个游走序列中；另一个元路径A-P-C-P-A则规定：在同一会议上(相同研究领域)发表的论文及其作者将出现在同一个游走序列^[27]。可见不同元路径的语义不同，A-P-A对共同作者的表达有利于发现作者间的师生关系，而A-P-C-P-A则可以发现某一研究领域内关键性作者。因为领域内关键研究者通常独立带领团队展开研究，他们共同发表论文的可能性较低；相反，这些研究者会选择与自己的学生共同发表论文。基于元路径的随机游走使采样所得节点序列不仅包含异质图的结构信息，还蕴含了丰富的语义。

随机游走构成的节点序列可以被看作“文档”，每个节点可以被看作“单词”，采用自然语言处理的skip-gram模型^[28]可实现节点的嵌入。skip-gram基本思想是采用极大似然估计来计算两个单词共现的概率：

式中， $\sigma $ 是激活函数； $ {{\boldsymbol{w}}_u} $ 和 $ {{\boldsymbol{w}}'_v} $ 分别是目标词 $ u $ 与其邻居 $ v $ 的向量表示；skip-gram模型对邻居的定义是：在一定尺寸窗口内共同出现的词， $ \left\langle {{{\boldsymbol{w}}_u} \cdot {{{\boldsymbol{w}}'}_v}} \right\rangle $ 表示向量的内积，该值越大则两个单词共现的概率就越大，模型通过优化上述概率使其最大，即可获得每个单词的向量表示。为计算方便，在实际应用中通常将上述的最大化问题通过取负对数转换为最小化问题。

需要说明的是，上述模型仅能将节点嵌入到欧式空间，欧式空间在表达具有层次和无标度的网络时将会产生失真，不利于网络结构特征的保持，因此需要对基本skip-gram模型进行修改，使之能够实现双曲空间的嵌入。

1) 双曲空间的性质

根据双曲几何的相关定义可知：双曲空间是一类具有负常曲率的非欧空间，曲率 $k$ 表示曲线的“弯曲”程度，我们熟悉的欧式空间曲率为零( $k = 0$ )，双曲空间的曲率为负( $k < 0$ ，通常取 $k = - 1$ )，球面的曲率则为正( $k > 0$ ，通常取 $k = 1$ )。定性地说，欧式空间是平坦的，而双曲空间有一定程度的“弯曲”，因此，双曲空间比欧式空间更“大”，具有更多“空间”。双曲空间可以利用更少的参数来表达具有在欧式空间中同样容量的模型。为了表达双曲空间，研究者建立了一系列等价模型，如：Lorentz模型、庞加莱模型、克莱因模型等，每个模型强调双曲几何的不同属性。

图2展示了Lorentz模型和庞加莱模型间的关系：双曲面上任意两点发出的射线交于 $Z$ 轴上的(0,0,−1)点，射线与 $Z = 0$ 的庞加莱圆盘相交，此时连接双曲面上两点的一段圆弧被称为Lorentz模型的测地线，这段圆弧投影到庞加莱圆盘上则成为庞加莱模型的测地线。在有度规定义存在时，测地线为空间中两点的局域最短路径^[29]。Lorentz模型和庞加莱圆盘中的测地线都是“弯曲”的，其上的距离度量类似于树形结构上两节点间的最短路径。图3进一步说明：在欧式空间看来离得很近的两个节点在树形结构下实际距离却很远，双曲空间可以认为是一个连续的树形结构。

图  2  双曲空间模型^[20]

图  3  双曲空间中的距离^[30]

Lorentz模型的几何性质^[31]决定了内积、距离等算数运算与欧式空间方法相近，且数值稳定。与此相反，庞加莱模型中计算两个离中心节点很远的节点内积时数值不稳定，难以优化。同时，网络的无标度特性使大部分节点分布在庞加莱圆盘的边界附近，节点的集中分布将导致计算机浮点数精度不足，无法正确表示边缘节点。但庞加莱模型提供了非常直观的可视化方法可用来解释双曲嵌入的结果。在代数上，Lorentz模型和庞加莱模型是同构的，可通过数学变换将双曲面上的点映射到庞加莱模型中。本文综合利用两个模型的优点，在采用Lorentz模型实现异质图嵌入后，将其映射到庞加莱模型进行可视化展示。

2) 洛伦兹(Lorentz)模型

定义Lorentz标量积为：

式中， $x,y \in {\mathbb{R}^{n + 1}}$ ；则 $n$ 维双曲空间的Lorentz模型可定义为黎曼流形 $ {\mathcal{L}^n} = ({\mathcal{H}^n},{g_\ell }) $ ，其中 $ {\mathcal{H}^n} $ 的定义为： $ {\mathcal{H}^n} = \left\{ {x \in {\mathbb{R}^{n + 1}}:{{\left\langle {x,x} \right\rangle }_\mathcal{L}} = - 1,{x_0} > 0} \right\} $ ，它是双曲面 $ - x_0^2 + x_1^2 + \cdot \cdot \cdot + x_n^2 = - 1 $ 的上半叶， $ {g_\ell } = {\rm{diag}}( - 1,1, \cdot \cdot \cdot ,1) $ 为度规张量。双曲面上任意一点 $x \in {\mathcal{H}^n}$ 满足： $ {x_0} = \sqrt {1 + x_1^2 + \cdot \cdot \cdot + x_n^2} $ ，因此 $ \mathcal{L} $ 是 $n$ 维的，在 $ \mathcal{L} $ 上任意两点的测地线距离可表示为： $ {d_\ell }(x,y) = {{\rm{ar}}} \cosh ( - {\left\langle {x,y} \right\rangle _\mathcal{L}}) $ 。

对于给定异质图 $G = \{ V,E,T,\phi ,\psi \} $ ，目标是获得节点的向量表示 ${\boldsymbol{W}} = \{ {w_i}\} _{i = 1}^{|V|}$ ，且 $w \in {\mathcal{H}^d}$ ，节点向量需要保留双曲空间中的结构和语义相关性。异质图 $G$ 上的元路径定义如下： $ {\rm{Path}} = {v_{{t_1}}}\xrightarrow{{{e_{{t_1}}}}}{v_{{t_2}}} \cdots \xrightarrow{{{e_{{t_{n - 1}}}}}}{v_{{t_n}}} $ ，在不同类型的节点间跳转的概率为：

式中， $ v_{{t_{{v_i}}}}^i $ 表示元路径 ${\rm{Path}}$ 中第 $ i $ 步、类型为 $ {t_{{v_i}}} $ 的节点，该节点将以概率 $p$ 跳转到下一个类型为 $ {t_{{v_{i + 1}}}} $ 的节点 $ v_{{t_{{v_{i + 1}}}}}^{i + 1} $ ； $ \left| {{N_{{{\text{t}}_{{v_{i + 1}}}}}}(v_{{t_{{v_i}}}}^i)} \right| $ 表示节点 $ v_{{t_{{v_i}}}}^i $ 类型为 $ {t_{{v_{i + 1}}}} $ 的邻居总数。根据以上元路径 ${\rm{Path}}$ 的定义可知：元路径指导的游走过程使节点的跳转受到元路径定义的约束，因此该游走序列保留了异质图的邻域信息和蕴含的语义信息。为了方便并行计算，采用截断随机游走^[32]，即同时在不同的顶点上进行定长的随机游走，这样做可以减少采样时间。然后，利用极大似然作为目标函数实现二分类：使目标节点与邻居更相似，非邻居节点不相近，由于现实网络非常稀疏，使有连接的正样本和没有连接的负样本偏斜严重，因此对负样本进行采样：在非邻居节点中随机取若干个节点作为负样本参与运算。模型的损失函数为：

式中， $ \mathcal{D} $ 表示节点 $ u $ 的邻居节点集合； $ {v'_j} $ 是随机采样的噪声节点，这样的负样本共取 $ n $ 个； $ {P_\mathcal{L}}(u,v) $ 表示双曲空间中两节点的共现概率：

式(5)与式(1)相似，只是内积 $ {\left\langle {{{\boldsymbol{w}}_u},{{{\boldsymbol{w}}'}_v}} \right\rangle _\mathcal{L}} $ 为满足双曲面模型定义的Lorentz标量积(见式(2))。对 $ {P_\mathcal{L}}(u,v) $ 取负对数使原来概率的最大化转换成对目标函数的最小化以方便实现。

由于模型参数存在于具有黎曼流形的双曲面中，因此反向传播的梯度是黎曼梯度，原来欧式空间下梯度优化方法的参数更新： $ {\boldsymbol{w}}_i^{t + 1} = {\boldsymbol{w}}_i^t + \eta \nabla _w^E\mathcal{L}(W) $ 不再具有实际意义，因此在进行优化时需要采用黎曼梯度下降(Riemannian gradient descent, RGD)^[33]。

Lorentz模型RGD的计算可被分解为以下3个步骤。

1) 计算关于节点嵌入的欧氏梯度：

2) 将欧式梯度转换为在双曲面每一点上定义的切空间黎曼梯度 $ \nabla _{{w_u}}^R\mathcal{L} $ ：

3) 利用指数映射将黎曼梯度转换为双曲面上的测地线后更新节点向量：

式中， $ {{\boldsymbol{h}}_r} = \eta \nabla _{{w_i}}^R\mathcal{L} $ ， $\eta $ 是学习率。采用自适应的黎曼优化算法RAdam^[34]来实现。以上步骤还引入了若干参数用以自适应地调整学习步长，这些参数的更新也需要在黎曼空间实现。

算法1给出了本文所提异质图双曲嵌入算法(heterogeneous graph Lorentz embedding, HGLE)的完整流程。通过执行算法1将得到异质图上各节点的向量表示。

算法1　异质图双曲嵌入

输入：异质图 $G = \{ V,E,T,\phi ,\psi \} $ ，随机游走相关参数：游走长度 $l$ ，每节点游走次数 $m$ ；节点嵌入相关参数：嵌入维度 $d$ ，窗口长度 ${\rm{window}}$ ，负采样数 $n$ ，迭代次数T

输出：节点嵌入向量 ${\boldsymbol{W}} \in {\mathbb{R}^{\left| V \right| \times d}}$

随机初始化 ${\boldsymbol{W}}$ 和 ${\boldsymbol{W}}'$

Walks = { }

// 生成随机游走序列

for i = 1 to m do

　 for all $v \in V$ do

　　 从节点 $v$ 出发，生成基于元路径的长度为 $l$ 的游走序列并添加到Walks

　 end for

end for

// 模型优化

for t=1 to T do

　 for all ${\rm{walk}} \in {\rm{walks}}$ do

　 for all $(u,v)$ within ${\rm{window}}$ in ${\rm{walk}}$ do

　　　 根据式(6)和(7)计算欧式梯度

　　 　for $j = 1$ to $n$ do

　　　 随机采样 $v' \in V$

　　　 根据式(6)和(8)计算欧式梯度

　　 end for

　　 根据式(9)将欧式梯度转换为双曲梯度

　　 根据式(10)用黎曼梯度下降更新 ${\boldsymbol{W}}$ 、 ${\boldsymbol{W}}'$

　 end for

end for

end for

算法复杂度分析：算法1由3个阶段组成：基于元路径约束的随机游走序列生成、节点对采样、梯度下降学习。其中，随机游走阶段为 $\left| V \right|$ 个节点生成 $m$ 条长度为 $l$ 游走序列，时间复杂度为 $O(\left| V \right| \times m \times l)$ ；节点对采样阶段：在游走序列上为每对节点计算共同出现在窗口中的概率，其中，窗口长度为 ${\rm{window}}$ ，时间复杂度为 $O(\left| V \right| \times m \times {\rm{window}} \times l)$ ；采用梯度下降对skip-gram模型进行优化，这一阶段需要对每一个共现节点对进行 $n$ 次负采样，于是，噪声节点对计算次数为 $O(\left| V \right| \times m \times {\rm{window}} \times l \times n)$ ，对每个 $d$ 维向量表达的节点进行欧式梯度更新，其复杂度为 $O(d)$ ，然后需将欧式梯度转换为黎曼梯度，其复杂度为 $O(d)$ ，于是则复杂度总和就是 $O(\left| V \right| \times m \times {\rm{window}} \times l \times (n + 1) \times2d)$ ，其中 $m$ 、 $l$ 、 ${\rm{window}}$ 、 $d$ 、 $n$ 是常数，因此算法1的复杂度与节点总数 $\left| V \right|$ 呈线性关系，可应用于大规模异质图。

本文使用链路预测作为下游任务来验证异质图的双曲嵌入效果，这是因为链路预测的目标是通过学习到的节点属性、拓扑结构等信息推断网络中未连边的两节点之间产生链接的概率，常用于验证图嵌入方法的泛化能力。

算法1得到异质图上各节点的向量表示后，即可利用节点间的双曲距离作为计算连边概率的依据。实验在CPU为corei7，内存4 GB电脑上采用python实现，使用geoopt、gensim、plotly等第三方扩展包用于双曲空间的优化、可视化等操作。下面将详细介绍实验过程并进行结果分析。

1) 数据集描述

使用真实数据集评估所提HGLE方法的效果。数据来源于公开的数据集AMiner、DBLP、ACM，这3个数据集均为引文网，对于AMiner、DBLP，分别提取计算机科学领域学者在重要学术会议发表的相关论文(P)，ACM是国际计算机协会主办会议(C)论文发表情况，该数据集共涉及57个与计算机相关主题(S)。各数据集的统计信息如表1所示。

为证明所提方法对异质图嵌入的有效性，将它与以下基准算法在经典图任务：链路预测上进行比较：

DeepWalk：经典同质图嵌入方法，该方法基于随机游走成功获得了同质图节点的嵌入表达。

metapath2vec：经典异质图嵌入方法，该方法采用元路径指导的随机游走得到蕴含异质图语义信息的游走序列，然后采用skip-gram实现节点的嵌入。

PHomoEmb：同质图在双曲空间的嵌入，该方法将同质图嵌入在双曲面模型的双曲空间中，证明具有层次结构和无标度特征的图在双曲空间获得了更好的嵌入表达。

PHeteroEmb：异质图在双曲空间的嵌入，该方法基于元路径指导的随机游走获得游走序列，然后采用庞加莱模型实现双曲嵌入。

2) 模型参数

随机游走相关参数：游走长度 $l = 80$ ，每节点游走次数 $m = 50$ ；节点嵌入相关参数：嵌入维度 $d$ 分别取2、5、10、30，窗口长度 ${\rm{window}} = 5$ ，节点向量和上下文向量 ${\boldsymbol{W}}$ 和 ${\boldsymbol{W}}'$ 随机初始化，负采样数 $n = 10$ ，元路径使用“APA”“APC(S)PA”。

3) 结果分析

实验中，同质图算法将所有节点和边都看作是同一种类型，用相同策略实现节点的嵌入，异质图算法则将分别预测“P-A”和“P-C(S)”的连边概率，实验结果取平均值。对每个数据集做8:1:1划分，80%作为训练集，10%为验证集，剩下10%为测试集。在训练集上对模型进行训练，然后用验证集调整模型参数，获得最小损失，然后在测试集上计算节点的连边概率并与原数据集进行比较，使用AUC评价链路预测的性能，表2给出了实验结果。从结果看，论文所提HGLE方法在连边预测上取得了较好的结果。实验结果还显示：面向同质图开发的嵌入算法由于不能捕捉节点、连边性质的差异，因此预测结果不理想；面向异质图开发的嵌入方法，如经典的metapath2vec算法，由于较好地保留了异质图的结构特征和语义信息，获得了比同质图嵌入算法好的预测效果；又由于双曲空间的嵌入算法更好地保留了网络的层次特征，获得了较欧式空间嵌入算法更好的预测精度。在此基础上，本文所提HGLE方法避免了计算边缘节点距离时的数值不稳定问题，使预测性能进一步改善。

图4给出了在数据集ACM上各算法的链路预测精确度结果，双曲嵌入算法在嵌入维度 $d = 10$ 时获得了比欧式空间嵌入维度 $d = 30$ 时更好的结果，这说明基于双曲空间的嵌入能够用较小的嵌入维度保留更多的网络结构和语义信息。

图5则给出了完整的AMiner数据集嵌入在庞加莱圆盘上的投影。数据在圆盘边沿十分密集，圆盘中心则很稀疏。利用gensim提供的庞加莱模型计算各点与原点的距离，并用黑色圆进行了区分。黑色圆内节点与原点的距离在0～2之间，黑色圆之外的距离在2～6之间，这与“树”的特征一致：层次高的节点数量少、层次低的节点呈指数增长。根据图5中给出的数据标签可知：影响因子较高的学者韩家炜、Christos Faloutsos、Philip S. Yug等人均离圆心较近，说明他们是图上的关键节点。经统计发现：双曲距离在0～2之间的作者(A)节点平均发表论文数为4.6篇/人，是双曲距离大于2的作者(图5中黑色圆之外)的2倍。

图  4  数据集ACM上各方法链路预测的AUC值

图  5  AMiner 数据集的可视化

异质图是建模现实世界图数据的有效手段，它蕴含更丰富的语义，对现实世界的描述也更完整自然，因此对异质图的研究在近期受到很多关注。图嵌入是异质图研究的重要手段，因为图嵌入的目标是将图结构和节点属性等映射到稠密、低维向量空间为下游任务提供基础，若嵌入表达不能正确保留图信息则后续挖掘任务无法获得好的结果。如何为图嵌入选择合适的嵌入空间就成为需要认真研究的问题。由于双曲空间中圆的周长随半径呈指数增长的几何性质与图的无标度特征恰好一致，所以可以采用双曲空间作为异质图的嵌入空间，但是，不同的双曲模型具有不同的几何性质，需要更进一步地探讨和研究。另外，目前大部分双曲空间的嵌入使用负常曲率，有一定的局限性，因为数据的复杂性使其各部呈现出不同的几何特性，嵌入空间各处曲率应不同，曲率的选择和学习也是具有挑战的任务。

另外，对异质图自身结构的理解依然没有结束，异质图允许不同类型节点间有连边，也允许相同类型的节点间有连边，同时，节点和边带有属性，它包含了多种特殊结构的图，如二部图(或三部图)，基于元路径的随机游走可以有效保留网络拓扑和节点属性等信息，但是元路径的选择需要领域知识，若元路径由人工确定，有可能为图嵌入引入噪声，当异质图退化为某种特例时，基于异质图建模是否就比基于二部图建模的方法好？这需要认真思考；另外，能否通过自适应的元路径学习方法来避免元路径人工选择也需要深入研究。尽管本文仅介绍了异质图对引文网的嵌入，事实上异质图已被应用至推荐系统、信息安全和基因工程等领域，并提升了挖掘任务的性能，因此，基于异质图的具体应用还需要进一步挖掘。

下一步研究将重点关注双曲空间的几何性质与网络结构之间的关系、元路径的选择与学习以及异质图嵌入在具体领域的应用。