相关工作
来源：科技导报
作者：韩忠明、熊峙冰、陈福宇、杨伟杰、张珣
针对大规模网络安全知识图谱表示学习训练速度慢、对头尾实体的关系表达缺乏的问题，提出一种基于随机游走的快速训练模型。该模型首先通过关系路径下的随机游走对整体知识图谱的实体进行初步训练表示；设计了主宾语嵌入，联合关系特定主语嵌入与关系特定宾语嵌入，学习知识图谱中关系的语法含义；再次通过关系路径下的随机游走辅助知识图谱的快速训练。在多个数据集上进行了大量实验，并与多个现有模型进行对比，结果表明，提出的模型能够缩短1/3的训练时间，提升约3%的表示效果，在加快知识图谱表示学习训练速度的同时，有效改善了表示学习的效果。
网络安全情报分析是网络安全的重要基础，知识图谱则为网络安全情报分析提供了强大的手段，学术界和工业界，如Palantir、MITRE等，都对网络安全领域知识图谱进行了深入研究。然而，网络安全领域知识图谱具有规模大、关系复杂多样等特点，这对知识图谱的快速训练提出了很大挑战。
现有的典型知识图谱表示方法中，不使用神经网络的方法，如TransE、ComplEx、DistMult、TransR、RESCAL、RotatE等，都需要大量时间的训练。而基于神经网络的编码模型，在构建方法上从实体和关系的分布式表示出发，利用复杂的神经网络结构，如张量网络、图卷积网络和变换器等，可以学习到更丰富的表示方法。这些深度模型虽然取得了有竞争力的效果，但对算力和空间的要求非常大，无法满足实际应用中大规模知识图谱的快速训练要求。现有的分布式训练方法主要基于数据并行实现，通过增加GPU数量或者提升GPU内存大小的方法加速训练，这些方法都要求使用者提供相应的算力完成训练。而针对单个计算设备，知识图谱嵌入训练加速问题的研究仍处于初步阶段，有部分研究者采用基于多线程的并行优化提升训练速度，但这些方法的加速仍然依赖于机器的基础性能，受算力的限制，并不能从根本上提升表示学习的速度。
另外，知识图谱中的实体表达不仅与其本身语义有关，也与它所在的三元组有关。三元组中的关系可以为三元组的头尾实体附加一层隐藏语义，如对网络安全知识图谱的关系“攻击”而言，其所有尾实体都存在一个隐藏的共同属性“主机”。对于某个关系的所有头实体或尾实体而言，也应当有部分相似的语义，而现有的方法均没有对这种关系隐含的共同特征进行表达，造成实体嵌入信息的缺失，导致下游任务效果降低。有部分研究者基于实体本身的分类特征为实体嵌入增加属性，但这些方法需要知识图谱本身提供实体的分类信息，无法对没有分类信息的知识图谱的自适应进行表达。基于此，提出了一种基于随机游走的知识图谱快速学习方法，通过关系路径下的随机游走加快表示学习收敛速度，同时引入主宾嵌入的关系编码，以解决大规模知识图谱的训练效率问题，同时提升表示学习的效果。
相关工作
根据知识图谱表示学习模型的得分函数的类型，知识图谱嵌入方法被分为以下3类。
基于翻译的模型，认为对于一个三元组（h，r，t），关系r可以当作是从头实体h到尾实体t的一个翻译（translation）操作。TransE是最具代表性的转化距离模型，在TransE中，它将实体和关系都表示为同一空间中的向量，给定一个fact（h，r，t），关系被解释为一个翻译向量r，实体h和t通过r以较低的误差连接起来。TransH在TransE的基础上引入了特定于关系的超平面；TransR引入了特定于关系的空间；TransD和TranSparce为TransR的简化；TransM、ManifoldE、TransF和TransA则放宽了对于h r≈t过分严格的要求。除了TransE及其变体，基于高斯嵌入的方法KG2E将实体和关系表示为从多维高斯分布中抽取的随机向量，TransG用混合高斯来表示关系。另一类基于翻译思想的变种模型将关系建模为头尾实体之间的旋转，代表性的模型为RotatE，HAKE模型也采用了旋转建模的方式，使用同心圆表达实体之间的层级语义信息。
基于语义匹配的模型，利用基于相似度的评分标准，通过匹配实体关系内的潜在语义信息来度量三元组的可信性。其中RESCAL将实体表示为向量，每种关系表示为一个矩阵，用来代表实体之间所有潜在成分之间的相互作用。TATEC建模双向交互，即一个实体与一个关系之间的交互。DistMult通过将关系矩阵限制为对角矩阵来简化RESCAL。Hole结合了RESCAL的表现力和DistMult的效率和简单性，用循环相关操作将实体表示组成h⋆t∈Rd。ComplEx在DistMult的基础上引入了复值嵌入。
基于神经网络的模型，将神经网络方法引入知识图谱嵌入中，挖掘知识图谱中的深层隐藏信息，提升嵌入表达效果。SME使用神经网络架构进行语义匹配。神经张量网络（NTN）将实体投影成输入层的向量嵌入，提出了特定于关系的向量Mr用于组合实体h和t，多层感知机MLP中每个实体和关系都表示为一个单独的向量，参数为所有关系共享。神经关联模型NAM使用“deep”架构进行语义匹配，使用L层线性隐藏层组成深层神经网络。近年来，ConvE使用2D卷积将头实体和关系重塑为2维矩阵，通过多层非线性层来学习语义信息。RGCN则首次将GCN框架引入了知识图谱的表示学习中。SACN在ConvE的基础上引入了GCN，由加权卷积网络WGCN编码器和ConvE-TransE解码器组成。CompGCN将知识图嵌入技术中的实体—关系组合操作与图卷积模型结合，在聚合邻域信息时引入关系信息。考虑到神经网络模型无法解释网络如何捕捉到语义信息的潜在结构，Carl等基于词嵌入的最新理论将知识图谱关系分为3种类型，并将其运用到知识图谱表示学习中。
近年来越来越多中国研究人员投入到知识图谱表示学习的研究中。方阳等在2018年提出了基于TransE的改进模型TransAH，引入面向特定关系的超平面模型，彭敏等在TransE的基础上提出了聚合邻域信息的联合知识表示模型TransE-NA，李鑫超等提出了基于改进向量投影距离的知识表示学习模型SProjE，该模型引入自适应度量方法，降低了噪声信息的影响。为了加强嵌入向量的语义表达，文洋等提出了基于实体相似性的表示学习方法SimE，利用实体的结构邻域度量实体的相似性。陈恒等将关系定义为超复数空间中头实体到尾实体的旋转，用于推理和建模各种关系模式，包括对称/反对称、反转和组合。
总体而言，双线性模型主要基于乘法运算，使得其参数要比基于神经网络方法使用的参数少，但会有很多性能上的局限性。而基于神经网络的编码模型，从实体和关系的分布式表示出发，利用复杂的神经结构来学习更丰富的表示方法，但也存在无法体现网络安全知识图谱中复杂的多重边问题。
基于随机游走的大规模知识图谱快速训练模型
为了对大规模的知识图谱进行快速训练，实现更加高效的知识图谱表示学习，将图表示学习中的随机游走思想引入本研究，提出了一种基于随机游走的大规模知识图谱表示学习快速模型RWRel，整体模型框架如图1所示。模型通过关系路径下的随机游走，融合知识图谱全局结构信息，对知识图谱中实体嵌入进行初步的训练，加速后续表示学习收敛速度。同时，为了使得知识图谱表示学习模型得到的向量能够较好地刻画关系中的主谓语义，模型联合关系特定主语嵌入与关系特定宾语嵌入，学习了知识图谱中关系的语法含义，最后，再次通过关系路径下的随机游走辅助知识图谱的快速训练。另外，模型还能与现有的多种知识图嵌入方法进行结合，如TransE、TransR和RotatE等，具有极强的可扩展性。
1、关系路径下的随机游走
为了在随机游走过程中融入知识图谱中的关系信息，针对知识图谱的多关系特点设计了关系路径下随机游走的方法，目标是使游走时搜索的目标节点在语义上与当前节点更相似。为了实现采样时的语义接近，设计了一种基于关系类型的有偏采样策略，采样时根据之前游走的关系路径在当前节点的邻居节点中选择采样节点。具体来说，对于当前节点v，若该节点为初始节点，下一步游走沿关系r的概率为
Rv代表有节点v参与的关系类型。
通过这种处理，可以确保初始游走方向不会因为大量重复关系类型而忽视节点v周围只出现1次的稀有关系。选择完游走方向后，在该关系下继续确定下一步游走的节点，对于当前初始节点v，若选择的游走路线是r，下一步采样节点是x的概率为
Nvr代表节点v在关系r下的邻居节点。
根据初始节点选择完第一步的游走方向和具体游走节点后，接下来游走的方向与节点上一步游走的关系路径以及上一步的节点相关。即，对当前节点v，若上一步游走是经过（t，rl，v）路径，则下一步游走的采样节点是x的概率为
π（v，rl，x）是节点v和节点x之间的未归一化转移概率，Z是归一化常数。
希望游走方向整体趋向于更相似的节点的同时，保证游走中的节点多样性，因此引入了超参数α，β，γ。通过超参数α控制关系多样性，通过β，γ控制整体游走的深度和广度。节点v和节点x之间的转移概率π（v，rl，x）计算公式如下
通过α控制下一步游走时仍选择与上一步相同的关系路线的概率，当α较大时，游走倾向于选择与上一步不同的关系，当α小时，游走倾向于选择与上一步相同的关系路线。ωrl（t，x）和ω（t，x）通过β，γ控制整体走向，具体计算公式如下
参数β控制反走回访问过节点的概率，当β值较高，则游走进行反走的概率就会降低，反之，反走的概率变高。然后使用参数γ控制游走进行广度搜索或是深度搜索。当γ>1，游走倾向于与上一步游走节点t接近的节点，当γ<1，游走倾向于当前节点v接近的节点。最后，为了减少游走过程中存在度为1的节点而出现的反走，我们考虑采用一种跳跃式的游走策略，使得当游走到度为1的节点时，向一定范围内其他与当前节点类似的节点上跳跃，这时需要依次反向搜索路径上节点的邻居。另外，我们认为其特定关系下的度占总度数比例越大则该节点与当前关系游走到的节点越像，在关系r下游走到的v节点和搜索节点x之间的转移概率π（v，rl，x）计算公式如下
式中，dvx代表节点x和节点v之间的距离。
通过这个参数控制反向搜索的距离，回退的节点数越多，转移概率越小。式（6）中
通过基于关系类型的有偏采样策略对知识图谱进行采样后，本研究使用Word2Vec学习实体的向量，得到知识图谱的初步实体嵌入。
2、引入主宾嵌入的关系编码
实验与结果分析
1 实验设置
为验证提出的模型在训练时间和准确度上的效果，在链接预测任务上将其与多个得分函数组合进行了对比性实验分析，使用Pytorch实现模型，并在1660TiGPU上运行。
首先使用FB15k-237和WN18RR两个数据集进行评估，为验证本模型在大规模数据集上的有效性，选择部分典型的基线模型在FB15k数据集上进行对比实验。数据集的具体统计信息如表1所示。
2 、实验结果
在链路预测实验中使用2个评价指标：平均倒数排名（MRR）和命中率（Hits@k）。
其中，|Q|是三元组集合的个数，ranki是指第i个三元组在链接预测中的排名，该指标越大越好。
Hits@k是指在链接预测中排名小于k的三元组的平均占比。
其中，|Q|是三元组集合的个数，ranki是指第i个三元组在链接预测中的排名，Π（∙）是indicator函数（若条件真则函数值为1，否则为0）。一般的取k等于1、3或者10，该指标越大越好。
分别对比了RWRel框架和各基线模型组合在两个数据集的结果，具体如表2、表3所示。
表2、表3中，第1部分为非神经网络方法，这类方法均可直接与RWRel框架结合；第2部分为神经网络方法，这类方法的耗时普遍比非神经网络方法高，但结果比非神经网络好一些。在FB15k-237数据集上，引入RWRel框架后，各非神经网络模型在各项指标上均优于原始结果，在MRR指标上使用RWRel框架的TransE、DistMult、ComplEx和RotatE平均提升了2%。其中表现最优秀的得分函数为RotatE，和这些方法原本的表现一致。在神经网络的方法上，RWRel方法略弱于最新的神经网络方法CompGCN，但在Hits@1上表现略好于CompGCN。在WN18RR数据集上，引入RWRel框架后各非神经网络模型均有了明显提升，其中表现最好的RotatE得分函数在RWRel框架下能获得比最新的CompGCN在论文上报告的结果高出0.6%。这表明提出的引入主宾嵌入的关系编码方法使原始的非神经网络方法能获得对标神经网络方法的效果。
为验证所提出的方法在训练时间的改善效果，将其与基线模型收敛的时间进行对比，具体结果如图3所示。
可以看到在FB15k-237数据集上，在相同的学习率时，使用RWRel的方法均比不使用时训练时长缩短1/2。其中效果最突出的是在DistMult模型上，时间缩短了近64%，同时在准确率上提升了4%。在WN18RR数据集上表现更为优秀，使用RWRel框架后训练时长缩短接近2/3。基于神经网络的方法在2个数据集上训练普遍耗时在4h以上，其中效果最好的CompGCN在FB15k-237数据集上训练时长达到6.5h，在WN18RR数据集上训练时长接近8h。而效果表现最接近CompGCN模型的RWRel RotatE方法在2个数据集上仅需训练38min和58min，可见本文方法在快速学习方面的有效性。
为了分析RWRel中随机游走方法对于实体嵌入初始化表示的有效性，使用表现最好的RotatE模型，将其本身与结合RWRel框架后的2种模型在开始训练的前600s的MRR指标变化情况进行对比，具体情况如图4所示。
从图4可以看出，在FB15k-237数据集上，使用RotatE作为解码器的RWRel模型在训练开始的10min内就可以获得最终收敛结果约70%的效果。而这时原始的RotatE方法仅达到最终效果的20%左右。在WN18RR数据集上，使用RotatE作为解码器的RWRel模型在10min时表现出的性能要比原始的RotatE模型相对提升25%以上，这证明了RWRel模型中的随机游走能有效提升实体嵌入初始化表达的效果，可以加快训练速度，使模型在较短的时间内获得良好的表示向量。
最后，为验证RWRel模型中引入主宾嵌入的关系编码对表示学习效果的提升，设计了一个消融实验，分别将模型中的随机游走模块和关系编码模块移除，观察剩余模块对实验结果的影响。具体结果如表4所示。其中，RWRel RotatE（1）代表模型中初始化嵌入为随机生成，保留了主宾嵌入，RWRel RotatE（2）代表模型保留了关系路径下的随机游走，移除了主宾嵌入的关系编码。实验中各模型运行时间对比如图5所示。
从表4可以看出，去除引入主宾嵌入的关系编码后，RWRel框架得到的表示结果与原来得分函数RotatE的结果基本一致，证明RWRel框架在提升训练速度的同时能基本保留原始得分函数的性能。同时，仅保留关系编码模块的RWRel框架则比RotatE模型提升了超过3%的性能，证明引入主宾嵌入的关系编码能有效表达知识图谱中关系的语法信息，为RWRel框架提供良好的性能支撑。从图5中各模型的运行时间可以看出，不使用随机游走的RotatE和RWRel RotatE（1）训练时长均超过了80min，而使用了随机游走的RWRel RotatE（2）和RWRel RotatE的训练时长均在40min以下，证明RWRel框架的训练速度提升主要来源于随机游走模块。通过消融实验可以看出，完整的RWRel框架中，关系路径下的随机游走加快表示学习方法的训练速度，引入主宾嵌入的关系编码提升了表示学习的表示性能。
结论
针对现有大规模知识图谱表示学习需要大量时间进行训练的现状，提出了一种基于随机游走的知识图谱快速训练模型RWRel，该模型包含了关系路径下的随机游走策略和针对关系语法含义的主宾嵌入编码，能够缩短大规模知识图谱表示学习时训练所需的时间，并有效改善知识图谱关系中蕴含的语法信息的表达。同时该方法还拥有良好的可扩展性，可直接运用于未来提出的其他得分函数上。但是，计算效率和模型表现力之间权衡，始终是大规模知识图谱的构建需要考虑的问题。随着预训练模型的发展，将预训练模型移植到图谱表示学习上，提前捕捉知识图谱中的实体关系和相关知识，可能会在下游应用中缩短时间、提升用户体验。另外，对于动态知识图谱中的快速表示学习也是未来的重要研究方向。
联系客服
