(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210752653.X (22)申请日 2022.06.29 (71)申请人 支付宝 （杭州） 信息技 术有限公司 地址 310000 浙江省杭州市西湖区西溪路 556号8层B段801-1 1 (72)发明人 胡彬　何建杉　赵培龙　王太峰　 赵登　褚崴　 (74)专利代理 机构 成都七星天知识产权代理有 限公司 5125 3 专利代理师 袁春晓 (51)Int.Cl. G06F 16/36(2019.01) G06F 16/28(2019.01) (54)发明名称 一种知识图谱路径搜索方法和系统 (57)摘要 本说明书实施例提供了一种知识图谱路径 搜索方法和系统， 方法包括： 获取选自所述知识 图谱的至少一个节点对， 每个所述节 点对包括两 个目标节 点； 基于所述至少一个节 点对中的所述 目标节点生成目标节点集合； 基于所述多个三元 组中的节 点生成图谱节点集合； 基于所述多个三 元组， 通过基于所述目标节点集合和所述图谱节 点集合的笛卡尔积运算， 得到相关于所述目标节 点集合的至少一个N跳子图； 基于所述至少一个N 跳子图中的子图路径， 得到所述至少一个节点对 的所述两个目标节点之间K跳以内的路径； 其中K ≥1， 1≤N≤K。 权利要求书3页 说明书19页 附图8页 CN 115080763 A 2022.09.20 CN 115080763 A 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跳子图包 括：权　利　要　求　书 1/3 页 2 CN 115080763 A 2基于所述多个三元组， 通过计算所述首位节点集合和所述头节点集合的N 次笛卡尔积， 得到相关于所述首位节点 集合的至少一个N跳 子图； 将所述多个三元组中的有向边连接的头节点和尾节点的头尾次序倒序， 并将有向边表 示的关系取反， 得到多个处 理后三元组； 以及， 基于所述多个处理后三元组中的头节点生成倒序头节点集合， 并基于所述多个处理后 三元组， 通过计算所述末位节 点集合和所述倒序头节点集合的N次笛卡尔积， 得到相关于所 述末位节点 集合的所述至少一个N跳 子图； 或者， 基于所述多个处理后三元组， 通过计算所述末位节点集合和所述尾节点集合的N次笛 卡尔积， 得到相关于所述末位节点 集合的所述至少一个N跳 子图。 8.如权利要求1所述的方法， 所述基于所述多个三元组， 通过基于所述目标节点集合和 所述图谱节点集合的笛卡尔积运算， 得到相关于所述 目标节点集合的至少一个N跳子图包 括： 基于所述多个三元组， 通过计算所述目标节点集合和所述图谱节点集合的N次笛卡尔 积， 得到相关于所述目标节点 集合的所述至少一个N跳 子图。 9.如权利要求1所述的方法， 所述方法还包括： 设置限定条件， 以基于满足所述 限定条 件的所述多个三元组， 通过基于所述 目标节点集合和所述图谱节点集合的笛卡尔积运算， 得到相关于所述目标节点 集合的所述至少一个N跳 子图； 所述限定条件包括以下中的任意一种或多种： 边属性值、 边类型、 节点类型、 节点属性 值。 10.如权利要求1所述的方法， 所述方法还 包括： 滤除所述至少一个节点对的所述两个目标节点之间K跳以内的路径中的子回路。 11.如权利要求1所述的方法， 所述方法还 包括： 通过目标任务处理方法处理所述至少一个节点对的所述两个目标节点之间K跳以内的 路径， 得到目标 数据处理任务的数据处 理任务结果； 所述数据处理任务结果包括以下中的一种或多种： 所述至少一个节点对中的所述目标 节点的分类结果、 所述至少一个节点对中的所述 目标节点间关系的预测结果、 所述至少一 个节点对的所述两个目标节点之间路径的规则推理结果、 所述至少一个节点对中的多个所 述目标节点所构成的集 合的挖掘结果。 12.一种知识图谱路径搜索系统， 所述知识图谱包括多个三元组， 其中各个三元组包括 一条边以及该边连接的两个节点， 所述系统包括： 获取模块， 用于获取选自所述知识图谱的至少一个节点对， 每个所述节点对包括两个 目标节点； 目标节点集合生成模块， 用于基于所述至少一个节点对中的所述目标节点生成目标节 点集合； 图谱节点 集合生成模块， 用于基于所述多个三元组中的节点 生成图谱节点 集合； 子图生成模块， 用于基于所述多个三元组， 通过基于所述目标节点集合和所述图谱节 点集合的笛卡尔积运 算， 得到相关于所述目标节点 集合的至少一个N跳 子图； 路径确定模块， 用于基于所述至少一个N跳子图中的子图路径， 得到所述至少一个节点 对的所述两个目标节点之间K跳以内的路径； 其中K≥1， 1≤N≤K。权　利　要　求　书 2/3 页 3 CN 115080763 A 3