2023 NIPS A*Net: A Scalable Path-based Reasoning Approachfor Knowledge Graphs 知识图谱、多跳推理、归纳推理、图卷积

标签：嵌入 based Knowledge 迭代路径子图 Scalable 信息节点

文章链接

原文：b9e98316cb72fee82cc1160da5810abc-Paper-Conference.pdf (neurips.cc)

代码：https://github.com/DeepGraphLearning/AStarNet

一、动机与贡献

为了使路径推理方法适用于大规模图上的归纳推理任务，文章改进了路径信息获取的方法。

路径推理方法较好的归纳推理能力。以往获取路径信息是搜索具体路径，耗时长。为降低耗时：1、使用迭代子图信息替代具体路径（具体比抽象多） 2、只考虑重要路径信息，去除不重要信息的干扰。更快获取路径信息的同时提高了预测效果。

两方面降低计算量：

1、将选取具体路径转化为了选取节点，迭代更新子图信息

2、基于A*（A start）考虑了节点重要性，只考虑重要路径，减少计算还能去除噪声

归纳推理：对不在训练集的实体进行预测，归纳能力就是对未训练实体的推理能力

基于嵌入和基于路径的归纳能力：由于预测原理不同，路径方法有更强归纳能力。transE是常见的基于嵌入方法，需要实体和关系嵌入来预测，实体的嵌入来自对训练集中实体，对未见过的实体没有嵌入，因而无法预测。基于路径的方法，只需要关系信息，比如 y是x的母亲： $mother(x,y) \leftarrow father(x,z) \wedge spouse(z,y)$ ，在x上找到对应关系链就可得出。因此归纳能力更强。

文章基于的路径方式：融合两节点间的所有路径信息（简称为子图信息），与查询关系比较，判断关系是否存在。

查询是（a，mother，？），三条路径中红色两条是重要路径，要比黑色路径更合理，因此a-f子图的嵌入只用重要路径嵌入相加，路径的嵌入则由关系的嵌入得出。将mother的嵌入和a-f子图嵌入比较判断f是否是查询答案

二、迭代与重要性

1、子图迭代

搜索具体路径可以被迭代子图信息替代，并且效率更高。子图信息保存在节点上，子图信息只是关系路径的另一种表现，不含特定实体信息。

为什么高效？

简略解释：多跳路径可以整合成单个子图信息，从3行到4行d，3行a储存3条具体路径，e储存1条，到达4行d要更新4条路径再汇总。在三行a、e路径整合成子图，得到对应两个嵌入，第4行就只用更新两个嵌入再汇总。

详细解释：

路径搜索可以看做一个迭代过程。比如寻找源点到目标点的3跳路径，上一次迭代后，拥有从源点到任一节点的二跳路径，并且知道任意两点是否连接。找二跳路径终点与目标节点之间的连接，将其添加到二跳路径上，就得到了三跳路径，可用右图中的a到d的过程来模拟。也就是说对源节点O ，目标节点T ，中间节点M ，找O到T的路径可以通过所有O到M的路径加上M-T的连接获取。直接迭代具体路径需要记录O到M的每一条路径，需要更多的计算和内存，注意到O-M的所有路径就是一个子图，由不同的M对应的O-M得到M-T就是一种子图迭代。之前的路径汇总发生再的到所有具体路径之后，现在将这一步提前，在每个中间节点M上就汇总形成嵌入，下一跳的嵌入就可以直接由各个中间节点M所携带的嵌入汇聚，而不是取得具体路径来汇聚，在a-d的4跳路径种就是通过第三行的a、e两个节点代替了4条具体路径，减少了一半的计算。两种方式的相似性说明了中间M子图嵌入能间接传达路径信息。

具体路径嵌入更新与子图更新的公式

（6）、（7）公式交代路径嵌入的更新。该嵌入只储存关系信息。 $\hat{\mathcal{P}}_{u\leadsto v|q}^{(0)}$ 是由多个路径嵌入构成的集合，上角标是迭代次数，也可看做路径长度， ${u\leadsto v|q}$ 是u到v的对于查询q重要的路径。

（6）初始化，将源节点和其他节点区分开，给源节点赋一个全1张量

（7）x是可以到达目标v的中间点，到达v的新集合是由到达不同x的旧嵌入集合更新而成

$h_{q}^{(t)}$ 是第t次迭代子图嵌入，大的 $\oplus$ 是将多个中间子图更新后的信息聚合，小 $\oplus$ 是将其与初始值聚合。

2、重要性

对给定查询，有的路径重要，有的路径会形成干扰，提前排除掉不重要的路径可以有效减少计算消耗，根据重要度分配权重可以提高准确性。通过A*Net来获取重要度。提前排除在整体流程中讲。

A*net 衡量语义上的路径长短，越短路径上的点越重要。其来源于A*算法， A*算法是一种寻找最短路径的算法，当一个节点的到源点距离+到目标距离最小，该点就更可能是最短路径上的点。A*net ，用嵌入代表距离，前面提到节点上的嵌入是路径的另一种表示，也就代表该点到源点的距离，源点到终点的距离就是查询，根据这两个距离处理后就得到当前点到终点的距离。

$s_{uq}^{(t)}(x)$ 是两距离和的嵌入， $\boldsymbol{h}_q^{(t)}(u,x)$ 是x上的子图嵌入，对应x到源点u的嵌入， $g([\boldsymbol{h}_q^{(t)}(u,x),\boldsymbol{q}])$ ，是问题嵌入和制图嵌入通过神经网络处理，得到的嵌入对应 x 到终点的距离