一种基于知识图谱嵌入的链接预测方法

1.一种基于知识图谱嵌入的链接预测方法，其特征在于包括以下步骤：第一步：对知识图谱进行分区；根据需要确定分区数量P和每个分区的子分区数量PP，将所有的实体分为subP个不重叠的子分区，subP＝P×PP，子分区为实体集E的互不重叠的子集，分区为PP个子分区的并集；将所有的三元组根据其头实体和尾实体所在子分区划分为不同的子三元组块；方法是：步骤1.1输入知识图谱数据，得到实体集E，关系集R，三元组集T，实体数量num_entities，E中包含num_entities个实体，num_entities为正整数，T中包含num_triples个三元组，num_triples为正整数；步骤1.2设置超参数嵌入向量维度D、分区数量P、每个分区包含的子分区数量PP，得到总的子分区数量subP＝P×PP，计算实体子分区大小subpart_size，subpart_size＝num_entities/subP；步骤1.3将实体集E随机打乱，然后按照子分区大小subpart_size将实体分割成subP个子分区集subpart，subpart中共有subP个实体子分区，每个实体子分区中含subpart_size个实体；步骤1.4遍历三元组集T所有的三元组，根据三元组头实体和尾实体所属的分区，将三元组划分到对应的子三元组块中，得到subP 2 个子三元组块组成的子三元组块集合subBuckets，subBuckets＝{subBucket(i2，j2)|1＜i2，j2≤subP}，其中(i2，j2)为子三元组块的编号，表示该三元组块中所有三元组的头实体来自第i2实体子分区，尾实体来自第j2实体子分区，subBucket(i2，j2)表示编号为(i2，j2)的子三元组块，将子三元组块集合中所有的三元组块存储至共享文件系统；第二步：构建嵌入模型；方法是先表示实体、关系：嵌入模型采用嵌入向量表示实体和关系，将实体嵌入向量作为实体子分区嵌入矩阵行向量，将关系嵌入向量作为关系嵌入矩阵行向量，嵌入模型的参数由实体嵌入向量和关系嵌入向量构成；再定义得分函数：得分函数定义了如何使用实体和关系嵌入计算三元组得分；由实体子分区嵌入矩阵、关系嵌入矩阵、得分函数共同组成嵌入模型；第三步，构建知识图谱链接预测系统；知识图谱链接预测系统由包含N个服务器的计算集群和共享文件系统组成，N个服务器均包含CPU和GPU，N为正整数；共享文件系统是计算集群的共享磁盘，负责存储实体子分区嵌入矩阵、关系嵌入矩阵θ、以及三元组块；N个服务器与共享文件系统相连，从共享文件系统获取嵌入模型，负责对嵌入模型进行训练，并对用户输入的要预测的实体缺失的三元组即缺失三元组，使用训练后的嵌入模型进行链接预测，得到预测结果；对嵌入模型训练时，每个服务器都是一个训练节点，从训练节点中选择一个作为主节点；主节点也是训练节点，除了运行训练节点的所有进程外，还要运行锁服务器进程，训练节点运行数据加载进程和GPU训练进程；数据加载进程负责从共享文件系统中读取和写入实体子分区嵌入矩阵、关系嵌入矩阵；链接预测时，每个服务器作为一个预测节点，从预测节点选择一个作为查询节点，各预测节点从共享文件系统加载训练后的嵌入模型，从查询节点获取用户输入的缺失三元组，然后使用嵌入模型进行预测；第四步，采用多机并行和CPU、GPU并行对嵌入模型进行分布式训练，将计算集群中的所有N个服务器作为训练节点，训练节点安装有数据加载进程和GPU训练进程，数据加载进程和GPU训练进程配合完成对嵌入模型的训练；从训练节点中任选一个作为主节点，主结点安装有锁服务进程；主节点的锁服务进程按步骤4.1的流程对三元组块进行调度，同时N个训练节点的数据加载进程按步骤4.2的流程进行数据加载，同时N个训练节点的GPU训练进程按步骤4.3的流程进行训练，步骤4.1、步骤4.2、步骤4.3并行进行，完成分布式训练，得到训练后的嵌入模型；方法是：步骤4.1主节点启动锁服务器进程，锁服务器进程调度每个训练节点进行训练所需的三元组块；调度方法如下：步骤4.1.1锁服务器进程初始化活动列表active和完成列表done，active和done初始值都为空，active保存当前正在训练的三元组块编号，done保存已经训练完的三元组块编号；初始化三元组块总数num_buckets＝P 2 ，P为分区数量；步骤4.1.2锁服务器进程接收N个训练节点发送来的信息，按照先到先得的顺序进行处理；如果信息为开始新的训练周期，转步骤4.1.3；如果信息为请求三元组块，转步骤4.1.4；如果信息为释放三元组块，转步骤4.1.5；如果信息为结束训练，结束锁服务器进程；步骤4.1.3新的训练周期开始，清空active和done，生成从分区到子分区的随机映射maps，并将maps发送到N个训练节点；转步骤4.1.2；步骤4.1.4为训练节点生成可训练的三元组块编号，得到可训练三元组编号res_bucket，并更新活动列表active和完成列表done；步骤4.1.5将释放三元组块信息中的三元组编号从active移除；转步骤4.1.2；步骤4.2在N台训练节点上启动数据加载进程，N个训练节点的数据加载进程的流程完全相同，第n个训练节点进行数据加载的方法如下：步骤4.2.1在内存中创建4个PP×subpart_size行D列的矩阵Embs 1 ，Embs 2 ，Embs 3 ，Embs 4 ，矩阵元素值初始化为0，令实体嵌入矩阵列表Embs＝[Embs 1 ，Embs 2 ，Embs 3 ，Embs 4 ]，令空闲矩阵序号列表free_idxs＝[0，1，2，3]；创建2个int类型进程间共享变量lock 1 ＝0，lock 2 ＝0；创建2个三元组编号curB 1 ＝(0，0)，curB 2 ＝(0，0)；创建2个实体嵌入矩阵序号列表EmbsIdx 1 ，EmbsIdx 2 ，分别初始化为长度为P的列表，列表元素均为0；创建2个三元组列表Triples 1 ，Triples 2 ，初始化为空；创建进程间传输管道conm，用于进程间数据传输，其数据类型为Pipe，创建训练标记is_training，初始化为True，类型为bool；创建共享参数列表shared_paras，shared_paras中包含两组共享参数，令shared_paras＝[(lock 1 ，curb 1 ，EmbsIdx 1 ，Triples 1 )，(lock 2 ，curB 2 ，EmbsIdx 2 ，Triples 2 )]；步骤4.2.2从共享文件系统中读取关系嵌入矩阵θ，在第n个训练节点中启动参数服务器，参数服务器负责将关系嵌入矩阵θ在N个训练节点之间进行同步；步骤4.2.3令当前训练周期数epoch＝1，获取用户定义的总训练周期数hum_epoch，num_epoch为正整数；步骤4.2.4如果epoch≤hum_epoch，转步骤4.2.5，否则转步骤4.2.21；步骤4.2.5如果第n个训练节点为主结点，向锁服务器进程发送开始新的训练周期信息，转步骤4.2.6；如果第n个训练节点不是主结点，直接转步骤4.2.6；步骤4.2.6判断是否从锁服务器进程接收到分区到子分区的映射关系maps，若接收到maps，转步骤4.2.7；若未收到maps，转步骤4.2.6继续等待；步骤4.2.7第n个训练节点开始第epoch轮训练周期的训练，初始化第epoch轮训练周期三元组块编号cur_b＝None，next_b＝None，old_b＝None，next_arg_idx＝0；cur_b是第epoch轮正在训练的三元组块编号，next_b是待加载的三元组块编号，old_b是已经训练完成的三元组块编号，next_arg_idx是用于加载的共享参数在shared_paras中的序号；步骤4.2.8从共享参数列表中取出第next_arg_idx+1个元素：令lock，curB，EmbsIdx，Triples＝shared_paras[next_arg_idx]＝shared_paras[next_arg_idx]；使用get_lock()函数对输入为lock时获取临时变量L，使用acquire()函数对输入为L时获取是否成功标记is_success，如果is_success＝True，转步骤4.2.9，否则转步骤4.2.8；步骤4.2.9判断lock的值是否为0，如果是0，转步骤4.2.10；否则，使用get_lock()函数对输入为lock时获取临时变量L，使用release()函数对输入为L时进行进程锁释放，转步骤4.2.8；步骤4.2.10向锁服务器进程发送获取三元组块请求，从主节点得到res_bucket和未训练三元组块数量remaining；如果res_bucket为None且remaining为0，转步骤4.2.17；如果res_bucket为None且remaining不为0，转步骤4.2.10；如果res_bucket不为None，更新old_b＝cur_b，cur_b＝next_b，next_b＝res_bucket，转步骤4.2.11；步骤4.2.11在内存和共享文件系统之间采用嵌入数据交换方法对next_b和old_b进行分区嵌入矩阵数据交换；步骤4.2.12从共享文件系统中加载next_b三元组到内存；Parth，Partt分别为三元组编号next_b的第1个和第2个整数，从maps获取分区Parth和Parth对应的子分区：maps[Parth]＝[sh1，sh2，...shPP]，maps[Partt]＝[st1，st2，...，stPP]；从共享文件系统中加载子分区对应的子三元组块{subBuckets[i3，j3]|i3∈maps[Parth]，j3∈maps[Partt]}，并重组为next_b三元组块Bucket，将Bucket保存至Triples；更新共享参数cur_B＝next_b；步骤4.2.13令lock＝1，令next_arg_idx＝(next_arg_idx+1)％2；步骤4.2.14使用get_lock()函数对输入为lock时获取临时变量L，使用release()函数对输入为L时进行进程锁释放；步骤4.2.15第n个训练节点从conn中接收训练完成信息；步骤4.2.16转步骤4.2.8；步骤4.2.17更新old_b＝cur_b，cur_b＝next_b，next_b＝None，使用步骤4.2.11中的嵌入数据交换方法对更新后next_b，old_b进行嵌入数据交换；步骤4.2.18第n个训练节点从conn中接收训练完成信息，更新old_b＝cur_b，cur_b＝next_b，next_b＝None，使用步骤4.2.11中的嵌入数据交换方法对更新后next_b，old_b进行嵌入数据交换；步骤4.2.19如果第n个训练节点是主结点，将关系嵌入矩阵θ存储至共享文件系统，转步骤4.2.20；如果第n个训练节点不是主结点，直接转步骤4.2.20；步骤4.2.20第epoch轮训练结束，令epoch＝epoch+1，转步骤4.2.4；步骤4.2.21说明第n个训练节点已进行了num_epoch轮训练，得到了训练完成的知识图谱嵌入模型，令训练标记is_training＝False；如果当前节点是主节点，则向锁服务器发送训练结束信息，转第五步，否则直接转第五步；步骤4.3启动GPU训练进程，在数据加载完成的三元组块上进行模型训练，直至数据加载进程完成所有训练周期的数据加载；第n个训练节点的GPU训练进程首先尝试获取内存中数据加载进程完成加载的三元组块以及相应的实体分区嵌入矩阵，然后将训练节点内存中的实体嵌入矩阵列表Embs中的矩阵加载到GPU上进行训练，训练完成后将加载到GPU上的矩阵传回内存，并通知数据加载进程三元组块训练结束，由数据加载进程将训练完成的分区嵌入矩阵存储至共享文件系统；第五步，计算集群加载训练后的嵌入模型，基于训练后的嵌入模型进行知识图谱链接预测；方法是：步骤5.1将N个服务器作为预测节点，选择任意一个服务器作为查询节点；将第四步训练后的嵌入模型即共享文件系统中的实体子分区嵌入矩阵和关系嵌入矩阵加载到服务器中；具体方法如下：步骤5.1.1在查询节点中，根据集群中服务器数量N，从共享文件系统中读取subP个实体子分区嵌入矩阵subEmbs 1 ，subEmbs 2 ，...，subsEmb ip ，...，subEmbs subP ；步骤5.1.2查询结点将子分区集subpart中的subP个集合，按照subpart中的顺序拼接成实体集E，将对应的subP实体子分区嵌入矩阵在行方向上拼接成实体嵌入矩阵Embs_all，Embs_all为一个num_entities行D列的矩阵；步骤5.1.3查询结点将实体集E中的元素按照当前顺序均匀分割为N个实体分区Parts 1 ，...，Parts N ，将实体嵌入矩阵Embs_all在行方向上均匀分割为N个实体分区嵌入矩阵Embs 1 ，Embs 2 ，...，Embs N ；查询节点将第1个分区Parts n1 和第1个分区嵌入矩阵Embs 1 发送给第1个服务器，…，将第n个分区Parts n 和第n个分区嵌入矩阵Embs n 发送给第n个服务器，…，将第N个分区Parts N 和第N个分区嵌入矩阵Embs N 发送给第N个服务器；步骤5.1.4N台服务器从共享文件系统读取关系嵌入矩阵θ，将θ加载到N台服务器的内存中；步骤5.2进行链接预测，方法是：步骤5.2.1查询节点接收用户从终端输入的缺失三元组(e hh ，rr，？)，查询节点从矩阵Embs_all读取e hh 的嵌入向量emb hh ，并发送给N个预测节点；步骤5.2.3N个服务器并行预测，第n台服务器的预测过程是：步骤5.2.3.1第n台服务器从分区Part n 取出所有的实体和实体e hh 组成三元组，得到三元组集{(e hh ，rr，e tt ′)|，e tt ′∈Part n }；步骤5.2.3.2按照嵌入模型中的得分函数，计算三元组集中所有三元组的得分，并按照得分对三元组集{(e hh ，rr，e tt ′)|e tt ′∈Part n }中的元素进行排序，选取{(e hh ，rr，e tt ′)|e tt ′∈Part n }中得分最大的C个三元组作为候选三元组集合CT n ，对应的得分集为Score n ，得分集Score n 中的元素为候选三元组集合CT n 中三元组的得分，C为正整数；步骤5.2.3.3将候选三元组集合CT n 及Score n 发送给查询节点；步骤5.2.4查询节点接受N个预测节点发送的候选三元组集和得分集，得到CT 1 ，CT 2 ，...，CT n ，...，CT N 和Score 1 ，Score 2 ，...，Score n ，...Score N ，将CT 1 ，CT 2 ，...，CT n ，...，CT N 合并为CT，Score 1 ，Score 2 ，...，Score n ，...Score N 合并为Score，CT为C×N个候选三元组，Score为C×N个三元组的得分，按照得分Score对CT进行排序，再次选择出最大的C个候选三元组{(e hh ，rr，e it )|0≤it＜C}，e it 表示得分最大的C个候选三元组中第it个三元组对应的尾实体，C个候选三元组对应的实体集{e it |0≤it＜C}作为链接预测的最终结果，为缺失三元组(e hh ，rr，？)的中缺失实体“？”的候选实体集。 2.如权利要求1所述的一种基于知识图谱嵌入的链接预测方法，其特征在于步骤1.2所述嵌入向量维度D设置为400，P的设置和总实体嵌入大小与GPU显存大小有关，总实体嵌入的大小为num_entities×D×4，P满足：2×总实体嵌入大小/P＜GPU显存大小，PP设置为2。 3.如权利要求1所述的一种基于知识图谱嵌入的链接预测方法，其特征在于步骤1.4所述遍历三元组集T所有的三元组，将三元组划分到对应的子三元组块中的方法是：步骤1.4.1初始化变量k1＝1，初始化子三元组块集合subBuckets，令subBuckets中所有的子三元组块均为空集，即令subBucket(1，1)，...，subBucket(i2，j2)，...，subBucket(subP，subP)均为空集；步骤1.4.2从T中取出第k1个三元组(e h ，r，e t )，0≤h，t≤num_entities-1；根据步骤1.3获得的subpart获取e h 所属子分区序号ih，e t 所属子分区序号it，1≤ih，it≤subP，将三元组(e h ，r，e t )添加到subBucket(ih，it)中，r∈R；步骤1.4.3令k1＝k1+1；如果k1≤num_triples，转步骤1.4.2；如果k1＞num_triples，表示T中所有三元组均被划分到对应的子三元组块中，得到了子三元组块集合subBuckets，结束。 4.如权利要求1所述的一种基于知识图谱嵌入的链接预测方法，其特征在于第三步所述共享文件系统要求具备2TB以上的存储空间，具备10Gb/s以上的读写速度。 5.如权利要求1所述的一种基于知识图谱嵌入的链接预测方法，其特征在于第二步所述构建嵌入模型的方法是：步骤2.1用向量表示实体和关系；方法是：步骤2.1.1将知识图谱中的每个实体表示为一个实体嵌入向量，实体嵌入向量是一个长度为D的向量，向量的值随机初始化为从标准正态分布的随机数；按照子分区集subpart，每个实体子分区包含subpart_size个实体，每个实体有一个实体嵌入向量，subpart_size个实体共有subpart_size个实体嵌入向量，将实体嵌入向量作为实体子分区嵌入矩阵行向量，按照实体子分区内实体顺序组成一个subpart_size行D列的实体子分区嵌入矩阵；subP个实体子分区共组成subP个实体子分区嵌入矩阵即subEmbs 1 ，subEmbs 2 ，...，subEmbs ip ，...，subEmbs subP ，subEmbs ip 为第ip个实体子分区subpart ip 的嵌入矩阵，有subpart_size行D列；将subP个的实体子分区嵌入矩阵存储至共享文件系统；步骤2.1.2将知识图谱中的每个关系表示为一个关系嵌入向量，关系嵌入向量是一个长度为D的向量，向量的值随机初始化为从标准正态分布的随机数，将关系嵌入向量作为关系嵌入矩阵行向量，按照关系集内关系顺序组成关系嵌入矩阵θ，将θ存储至共享文件系统；步骤2.2定义得分函数：f(triple)＝f(e h ，r，e t )＝sim(g(Emb h ，θr)，g(Emb d ，θr))其中sim(a，b)为相似度计算函数，用于计算两个向量a，b之间的相似度：g为关系算子函数，用于计算实体嵌入向量Emb h 经过关系r变换后的向量：g(Emb h ，θr)＝Emb h ⊙θrtriple＝(e h ，r，e t )表示一个三元组，Emb h 为实体e h 的嵌入向量，θr为关系r的嵌入向量，⊙表示哈达玛积， 表示a， 的复数点积， 为b的共轭复数；由实体子分区嵌入矩阵、关系嵌入矩阵、得分函数共同组成了嵌入模型。 6.如权利要求1所述的一种基于知识图谱嵌入的链接预测方法，其特征在于第四步所述maps为python字典类型，记录当前各分区分别由哪些子分区组成。 7.如权利要求1所述的一种基于知识图谱嵌入的链接预测方法，其特征在于步骤4.1.4所述为训练节点生成可训练的三元组块的方法是：步骤4.1.4.1将所有三元组编号添加到三元组块编号列表acquirable_buckets中，具体方法是：初始化三元组块编号列表acquirable_buckets，列表元素为满足1≤m≤subP，1≤n≤subP的所有二元组(m，n)，m和n分别代表三元组头实体和尾实体所在分区序号；步骤4.1.4.2若active为空，转步骤4.1.4.4，若active不为空，转步骤4.1.4.3；步骤4.1.4.3active中所有三元组块编号的分区序号集active_part，对于acquirable_buckets中的二元组，如果二元组中任意元素在active_part中，则将该二元组从acquirable_buckets中去除，转步骤4.1.4.4；步骤4.1.4.4如果done为空，转步骤4.1.4.6；如果done不为空，转步骤4.1.4.5；步骤4.1.4.5将done列表中的三元组块编号从acquirable_buckets中去除；步骤4.1.4.6如果acquirable_buckets不为空，转步骤4.1.4.7，如果acquirable_buckets为空，转步骤4.1.4.8；步骤4.1.4.7随机从acquirable_buckets选择一个三元组块编号，令临时变量res_bucket＝选择的这个三元组块编号，并将res_bucket添加到done和active中；转步骤4.1.4.9；步骤4.1.4.8令临时变量res_bucket＝None；步骤4.1.4.9计算未训练三元组块数量remaining＝num_bucket-num_done，num_done为done中元素个数，num_bucket＝P 2 ；将res_bucket和remaining发送给请求训练结点。 8.如权利要求1所述的一种基于知识图谱嵌入的链接预测方法，其特征在于步骤4.2.3所述总训练周期数num_epoch设为30；第五步所述C根据用户需要的返回结果数量设置为50。 9.如权利要求1所述的一种基于知识图谱嵌入的链接预测方法，其特征在于步骤4.2.11所述在内存和共享文件系统之间采用嵌入数据交换方法对next_b和old_b进行实体分区嵌入矩阵数据交换的方法是：步骤4.2.11.1如果next_b不等于None，更新cur_B＝next_b，转步骤4.2.11.2；否则转步骤4.2.11.3；步骤4.2.11.2加载next_b中分区嵌入向量：next_b的值为(Parth，Partt)，对于二元组(Parth，Partt)中的元素p，从free_idxs弹出idx，idx表示空闲矩阵的序号，EmbsIdx[p]表示实体嵌入矩阵序号列表EmbsIdx的第p个元素，令EmbsIdx[p]＝idx；由映射maps得到maps[p]＝[sp1，sp2，...spPP]，即分区p由子分区sp1，sp2，...spPP组成，从共享文件系统分别读取对应的实体子分区嵌入矩阵subEmbs sp1 ，subEmbs sp2 ，...，subEmbs spPP 拼接并保存至Embs[idx]；步骤4.2.11.3如果old_b不等于None，转步骤4.2.11.4；否则结束；步骤4.2.11.4保存old_b中的分区嵌入向量：old_b的值为(Parth，Partt)，对于分区p∈(Parth，Partt)，令idx＝EmbsIdx[p]，将idx放回free_idxs；由映射maps得到maps[p]＝[sp1，sp2，...spPP]，按照[sp1，sp2，...，spPP]各子分区大小，将分区嵌入矩阵Embs[idx]按行切分为subEmbs sp1 ，subEmbs sp2 ，...，subEmbs spPP ，并将subEmbs sp1 ，subEmbs sp2 ，...，subEmbs spPP 保存到共享文件系统中；向锁服务器进程发送释放old_b信息。 10.如权利要求1所述的一种基于知识图谱嵌入的链接预测方法，其特征在于步骤4.3所述第n个训练节点对分区嵌入向量进行训练的方法是：步骤4.3.1第n个训练节点进行GPU训练进程的初始化：将is_training，关系嵌入矩阵θ，实体嵌入矩阵列表Embs，和共享参数列表share_paras以及进程间传输管道conm，作为参数传入GPU训练进程的初始化函数中，初始化当前参数序号cur_arg_idx＝0，初始化batch_size＝5000；步骤4.3.2定义损失函数：其中，S′ triple 是由triple通过负采样得到的三元组集合，λ是超参数，设置为0.1，f是2.2中的得分函数；步骤4.3.3如果is_training为True，转4.3.4；如果is_training为False，GPU训练进程结束；步骤4.3.4令lock，cur_B，EmbsIdx，Triples＝shared_paras[cur_arg_idx]，输入lock使用get_lock()函数获取临时变量l，对输入l使用acquire()函数获取是否成功标记is_success，如果is_success＝True，转步骤4.3.5，否则转步骤4.3.4；步骤4.3.5判断lock的值是否为1，如果是1，说明数据加载进程已经完成相关数据的加载，可以进行训练，转步骤4.3.6，否则使用get_lock()函数对输入为lock时获取临时变量L，对使用release()函数对输入L进行进程锁释放，转步骤4.3.4；步骤4.3.6令cur_B＝(parth，partt)，idxh＝EmbsIdx[parth]，idxt＝EmbsIdx[partt]，将子三元组列表Triples以及Embs[idxh]，Embs[idxt]加载到GPU，Embs[idxh]，Embs[idxt]分别表示Embs中第idxh、idxt个矩阵；令已训练三元组的数量triple_idx＝0，令num_triples为Triples的长度；步骤4.3.7如果triple_idx＜num_triples，转步骤4.3.8；否则转步骤4.3.9；步骤4.3.8令T_batch＝Triples[triple_idx：triple_idx+batch_size]，T_batch表示三元组列表Triples中从第triple_idx个三元组开始到第triple_idx+batch_size个三元组为止的所有三元组组成的列表；计算loss，采用随机梯度下降方法更新Embs[idxh]，Embs[idxt]；triple_idx＝triple_idx+batch_size；转步骤4.3.7；步骤4.3.9通过conn发送训练完成信息给数据加载进程，通知数据加载进程当前三元组块训练完成，可以进行嵌入矩阵的保存；令lock＝0，令cur_arg_idx＝(cur_arg_idx+1)％2，转步骤4.3.3。