一种异质图的Lorentz 嵌入模型

苏晓萍，查英华，曲鸿博

(1. 南京工业职业技术大学计算机与软件学院 南京 210023；2. 南京邮电大学计算机学院 南京 210003)

信息网络普遍存在，如经济贸易网、社交网和计算机网络，这些网络的图模型一般采用邻接矩阵来进行表示与存储，该矩阵具有高维、稀疏的特征，对其分析和计算的成本较高，因此，在网络规模不断增长的情形下，需要找到更好的方法来表示、处理图数据。图嵌入[1-2](也称图表示学习)是解决这一问题的有效方法，它的目标是：将网络节点或边映射到一个方便计算和存储的低维稠密向量空间中，嵌入形成的低维向量可为多种下游数据挖掘任务提供支撑。图嵌入的基本原则是：用较少的数据维度尽可能多地保留原网络的拓扑结构、节点和边属性信息。大部分图嵌入方法仅考虑节点、边类型都相同的同质图。

然而，除同质图外，现实世界中还存在许多需要用异质图建模的复杂系统。异质图模型允许节点和边的类型相异，甚至网络类型也相异，如引文网中，节点包括：作者(A)、会议(C)、论文(P)等不同类型的对象，这些对象之间存在“参加”“发表”等语义不同的边。相较于同质图，异质图的语义更丰富，对现实世界的描述更完整自然，因此，基于异质图建模的研究近期受到了广泛关注[3～6]。由于异质图中节点、边的类型不相同，原来同质图嵌入方法不能直接应用于异质图，需要对这一特定的网络结构设计专门的表示方法。基于异质图的嵌入方法在近几年也获得了快速发展[7-8]，异质图嵌入的主要目标是保留原网络的拓扑结构和语义信息，嵌入的基本原则是：网络中“靠得越近的节点(语义相近或网络可达)，其向量表达越相似”。异质图嵌入方法大致可分为：基于近邻保持的方法[9-14]和基于信息传播[15-17]的方法。

以上异质图嵌入方法都是将异质图中的节点映射到人们熟悉的欧式空间，并用欧式距离来度量节点的相似性，然而，这里忽略了一个重要而根本的问题：用欧式空间表达复杂的图数据是否合适？近期研究表明：欧式空间不能很好地表达网络中的层次结构、无标度特性，在嵌入具有如上特征的网络时将出现较大程度的失真[18]，嵌入失真的主要原因是：欧式空间中球的体积与半径呈多项式增长，不具备表达数据呈指数增长的无标度特性，而在双曲空间中，球的体积与半径呈指数增长，这一特性使得它能很好地表达网络呈指数增长的无标度特征[19～22]，因此将图嵌入到双曲空间能够更多地保留网络的幂率分布、强聚类、小世界等结构特征，从而获得较欧式空间更精确的节点向量表示，为链路预测[23]、节点分类[24]等下游任务提供更好的精确度保证。文献[25]研究了异质图的双曲嵌入问题，采用庞加莱模型实现了异质图的双曲嵌入，并在链路预测任务下证明该方法具有比欧式空间嵌入的基准算法更好的结果。

受以上研究启发，本文提出了一种基于Lorentz模型的异质图嵌入方法。该方法首先采用基于元路径随机游走的方法捕获异质节点的邻域以及语义信息，然后采用Lorentz 模型实现异质图的双曲嵌入并用双曲距离评价节点间的相似度，最后训练模型，使语义相近的节点的向量表达也相似。所提方法解决了以下异质图嵌入的问题：1) 如何有效获取异质图的结构和语义信息；2) 如何将初始在欧式空间表达的节点语义和结构信息映射到双曲空间；3) 如何评价双曲空间中节点对的相似性以及如何实现在双曲空间中目标函数的优化。

1 相关理论

1.1 异质图的定义与实例

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

图1 异质图与元路径实例

1.2 元路径与随机游走

1.3 基于游走序列的嵌入

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

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

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

1.4 双曲空间

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 标量积为：

2 异质图的双曲嵌入

疏，使有连接的正样本和没有连接的负样本偏斜严重，因此对负样本进行采样：在非邻居节点中随机取若干个节点作为负样本参与运算。模型的损失函数为：

式(5)与式(1)相似，只是内积 〈wu,w′v〉L为满足双曲面模型定义的Lorentz 标量积(见式(2))。对PL(u,v)取负对数使原来概率的最大化转换成对目标函数的最小化以方便实现。

由于模型参数存在于具有黎曼流形的双曲面中，因此反向传播的梯度是黎曼梯度，原来欧式空间下梯度优化方法的参数更新：wti+1=wti+η∇EwL(W)不再具有实际意义，因此在进行优化时需要采用黎曼梯度下降(Riemannian gradient descent, RGD)[33]。

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

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

3 算法实现与结果分析

3.1 算法流程

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

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

3.2 实验结果与分析

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

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

1) 数据集描述

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

表1 数据集统计

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

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

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

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

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

2) 模型参数

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

3) 结果分析

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

表2 各算法AUC 结果

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

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

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

图5 AMiner 数据集的可视化

4 结 束 语

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

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

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