一种知识图谱路径搜索方法和系统.pdf

(19)国家知识产权局(12)发明专利申请(10)申请公布号CN115080763A(43)申请公布日2022.09.20(21)申请号202210752653.X(22)申请日2022.06.29(71)申请人支付宝（杭州）信息技术有限公司地址310000浙江省杭州市西湖区西溪路556号8层B段801-11(72)发明人胡彬何建杉赵培龙王太峰赵登褚崴(74)专利代理机构成都七星天知识产权代理有限公司51253专利代理师袁春晓(51)Int.Cl.G06F16/36(2019.01)G06F16/28(2019.01)权利要求书3页说明书19页附图8页(54)发明名称一种知识图谱路径搜索方法和系统(57)摘要本说明书实施例提供了一种知识图谱路径搜索方法和系统，方法包括：获取选自所述知识图谱的至少一个节点对，每个所述节点对包括两个目标节点；基于所述至少一个节点对中的所述目标节点生成目标节点集合；基于所述多个三元组中的节点生成图谱节点集合；基于所述多个三元组，通过基于所述目标节点集合和所述图谱节点集合的笛卡尔积运算，得到相关于所述目标节点集合的至少一个N跳子图；基于所述至少一个N跳子图中的子图路径，得到所述至少一个节点对的所述两个目标节点之间K跳以内的路径；其中K≥1，1≤N≤K。CN115080763ACN115080763A权利要求书1/3页1.一种知识图谱路径搜索方法，所述知识图谱包括多个三元组，其中各个三元组包括一条边以及该边连接的两个节点，所述方法包括：获取选自所述知识图谱的至少一个节点对，每个所述节点对包括两个目标节点；基于所述至少一个节点对中的所述目标节点生成目标节点集合；基于所述多个三元组中的节点生成图谱节点集合；基于所述多个三元组，通过基于所述目标节点集合和所述图谱节点集合的笛卡尔积运算，得到相关于所述目标节点集合的至少一个N跳子图；基于所述至少一个N跳子图中的子图路径，得到所述至少一个节点对的所述两个目标节点之间K跳以内的路径；其中K≥1，1≤N≤K。2.如权利要求1所述的方法，所述N为K/2向上取整。3.如权利要求1所述的方法，所述基于所述至少一个N跳子图中的子图路径，得到所述至少一个节点对的所述两个目标节点之间K跳以内的路径包括：连接所述至少一个N跳子图中相关于所述至少一个节点对的所述两个目标节点的具有公共外围节点的子图路径，以得到所述至少一个节点对的所述两个目标节点之间K跳以内的路径。4.如权利要求1所述的方法，所述方法还包括：删除所述知识图谱中度大于第一阈值的节点的至少部分边，得到处理后知识图谱；基于所述处理后知识图谱，得到所述多个三元组。5.如权利要求1所述的方法，所述知识图谱为有向图，所述三元组中的边为有向边，所述有向边表示连接的两个节点间的关系，所述有向边连接的两个节点分别为头节点和尾节点；所述基于所述多个三元组，通过基于所述目标节点集合和所述图谱节点集合的笛卡尔积运算，得到相关于所述目标节点集合的至少一个N跳子图包括：将所述多个三元组中的所述有向边连接的头节点和尾节点的头尾次序倒序，并将所述有向边表示的关系取反，得到多个处理后三元组，进而得到包括所述多个三元组和所述多个处理后三元组的新知识图谱；基于所述新知识图谱，通过计算所述目标节点集合和所述图谱节点集合的N次笛卡尔积，得到相关于所述目标节点集合的所述至少一个N跳子图。6.如权利要求1所述的方法，所述知识图谱为有向图，所述多个三元组中的边为有向边，所述有向边连接的两个节点分别为头节点和尾节点，所述图谱节点集合包括基于所述多个三元组中的所述头节点生成的头节点集合和基于所述多个三元组中的所述尾节点生成的尾节点集合；所述至少一个节点对中的各个所述节点对为有序节点对，所述有序节点对中的所述两个目标节点分别为首位节点和末位节点，所述目标节点集合包括基于所述至少一个节点对中的所述首位节点生成的首位节点集合和基于所述至少一个节点对中的所述末位节点生成的末位节点集合。7.如权利要求6所述的方法，所述基于所述多个三元组，通过基于所述目标节点集合和所述图谱节点集合的笛卡尔积运算，得到相关于所述目标节点集合的至少一个N跳子图包括：2CN115080763A权利要求书2/3页基于所述多个三元组，通过计算所述首位节点集合和所述头节点集合的N次笛卡尔积，得到相关于所述首位节点集合的至少一个N跳子图；将所述多个三元组中的有向边连接的头节点和尾节点的头尾次序倒序，并将有向边表示的关系取反，得到多个处理后三元组；以及，基于所述多个处理后三元组中的头节点生成倒序头节点集合，并基于所述多个处理后三元组，通过计算所述末位节点集合和所述倒序头节点集合的N次笛卡尔积，得到相关于所述末位节点集合的所述至少一个N跳子图；或者，基于所述多个处理后三元组，通过计算所述末位节点集合和所述尾节点集合