type
status
date
slug
summary
tags
category
论文链接
代码链接
Huggingface Demo
Notion Tip: Use this template to present new ideas and status updates with your team. The presentation schedule automatically indexes any topic you add. Use the toggles to show and hide content as your presentation progresses.
Table of contents
知识图谱推理（KGR）KGR的挑战KGR的关键问题：Inductive（归纳：从特殊到一般）可选的方式：把KGR规划为Path RepresentationGeneralized Bellman-Ford AlgorithmMath FormulationPath RepresentationGeneralized Bellman-Ford AlgorithmNBFNet对KGR来说，和取什么最优？Design SpaceNBFNet:NBFNet与GNN
知识图谱推理（KGR）
KGR的挑战
- Incompleteness：存在缺失的实体或关系，如果知识图谱里包含所有信息，则无推理的必要，直接查询检索即可；
- Scalability：知识图谱可以为百万级甚至千万级的规模；
- Inductive Setting：应用于其他图谱的泛化能力；
KGR的关键问题：Inductive（归纳：从特殊到一般）
- 从某一特殊知识图谱的推理归纳到具有同质化特征（比如关系相同）的任意知识图谱的推理，e.g. 从英国皇室家族知识图谱归纳到任意家族知识图谱的推理；
- 传统基于embedding的KGE算法不适用于Inductive，在哪个图训练就只能在哪个图测试；
- Inductive对于生产至关重要，比如当图发生变化时，重新训练模型成本过高，更好的方式是通过之前的模型去适应新的图。
可选的方式：把KGR规划为Path Representation
回答某人的儿子的妹妹的女儿是谁的问题
人类推理蓝色节点和黄色节点的关系为孙女时，通过路径来判断，蓝色节点到黄色节点可由“儿子的妹妹的女儿”这条路径连通，而这条路径上的关系组成为孙女，完成了将实体之间的关系表示成实体之间连通路径上所有关系和节点的过程。
由此类比，一种可行的KGR方式是，将两实体之间的关系转换为:对实体间所有path的枚举，学习每条path的representation，再通过某种方式将所有path的representation汇聚起来。
比如，Personalized PageRank算法和Graph Distance算法等其他算法也可以抽象成同样的过程，先枚举两节点之间所有可能的path，对每一条path学习path representation,再通过某种方式将所有的path representation汇聚起来。
进一步泛化推广，可以得到这样一种范式：节点和节点之间的表征可表示为u和v之间所有path表征的泛化和，各path表征可表示成组成该路径的所有边表征的泛化积。[线性空间：乘and加满足四条定律，“群理论”]
Scalabilty的问题
如上所示的计算思路，对于知识图谱来说计算是路径的指数级的。Personalized PageRank采用了power iteration，Graph distance的sacable的方式就是bellman-ford算法，这两种算法的核心思想就是动态规划。
所以在这儿也采用动态规划的思想来解决指数级计算量的Scalability的问题，假定泛化积和泛化和也满足分配律，类似于乘法分配律，提取公共前缀，无需指数级计算泛化积后求和，只需要考虑公共前缀和可选后继的组合方式就可以了。[四元素？][越稠密的图越难建模]
这样的形式就是Generalized Bellman-Ford算法的形式。
Generalized Bellman-Ford Algorithm
Math Formulation
本文在知识图谱（异质图）和同质图的两种视角下定义连接预测任务，对这两类图的定义如下：
- 知识图谱定义为:
- ：节点（实体）；：边（关系）；：关系的类型
- ：节点u的邻居节点；：节点u的邻接边。
- 同质图定义为，可视作知识图谱只有一种关系
Path Representation
知识图谱的视角定义了连接预测：
- 连接预测是预测头实体和尾实体之间是否存在一个可查询的关系；
- 从表示学习的角度来看，就是去学习一个表征，来捕捉对于关系，和之间存在的局部子图的特征。
在这样的设定下：
- 实体对的表征可视作节点u和v之间所有路径表征的泛化和（Generalized Sum），该求和的运算操作符为满足交换律的加和操作符，用表示；
- 各路径的表征可视作路径上各边嵌入的泛化积(Generalized Product)，该运算操作符为符合乘法的操作符，不要求满足交换律（如矩阵乘法）。
上述的数学语言表示如下：
综上，连接预测的路径可以视作一个DFS算法，先搜寻从u到v的所有可能的path，用公式(2)计算各path representation，随后用公式(1)汇聚，来表示节点u和节点v的实体对表征。
本定义与其他方法对路径定义的联系
文章指出有三种连接预测方法和两种图算法是上述路径定义变体：
- Katz index:
- Personalized PageRank:
- Graph distance:
- Widest Path:
- Most reliable path:
Generalized Bellman-Ford Algorithm
由于路径数随路径长度呈指数增长，导致计算成本很高。本工作采用了一种广义贝尔曼福特算法（Generalized Bellman-Ford Algorithm）。
Bellman-Ford算法：对所有的边进行n-1轮propagate操作，因为在一个含有n个顶点的图中，任意两点之间的最短路径最多包含n-1边:
- 第1轮在对所有的边进行propagate后，得到的是源点最多经过一条边到达其他顶点的最短距离；
- 第2轮在对所有的边进行propagate后，得到的是源点最多经过两条边到达其他顶点的最短距离；
- 第3轮在对所有的边进行propagate后，得到的是源点最多经过三条边到达其他顶点的最短距离…
假定操作是使用求和特征和乘积特征,则有如下操作：
其中，是indicator function，当u=v时输出，u≠v时输出。是边的表征，是该边的关系类型。公式（3）是边界条件，公式i（4）为贝尔曼福特迭代。
广义贝尔曼福特算法可以视作单源输入的GNN网络，其核心就是对给定的实体，关系和所有计算实体对表征，并通过乘法大于求和的分配律性质减少总计算量。
由于和在广义Bellman-Ford算法中是固定的，因此在上下文清楚时，可以把简化为。当和时，即为原始的Bellman-Ford算法。
Katz index, personalized PageRank, graph distance, widest path和most reliable path算法可以通过广义贝尔曼-福特算法来派生。
NBFNet
对KGR来说，和取什么最优？
为解决这个问题，本文的方法是使用一个Nerual Network去学习和。用3个神经函数：INDICATOR、MESSAGE和AGGREGATE，对广义Bellman-Ford算法进行参数化。
为建模一个给定的查询，使用：
- INDICATOR：取代了indicator function ，是的学习嵌入。
- MESSAGE：取代了二进制乘法运算符⊗，相当于源点+边的embedding，可从KGE的关系操作符（TransE\DistMult\RotatE,etc.）中选取。
- AGGREGATE：集合上的置换不变函数，它取代了求和运算符⊕，可从(sum\mean\max\PNA,etc)中选取。也可以将AGGREGATE定义为满足交换律的二元算子⊕并将其应用于信息序列,但这会使参数化变得更加复杂。
Design Space
在NBFNet里的神经函数MESSAGE、AGGREGATE和INDICATOR函数的设计上，我们可以从其他GNN方法中借用MESSAGE和AGGREGATE函数。
- MESSAGE：传统方法为对标量的自然求和、自然乘法或最小值。本文使用求和或乘法的向量化版本，直观上，对应于知识图嵌入方法：
- 和的向量和可解释为在向量空间中，通过平移；
- 和的向量乘法可解释为在向量空间中，通过缩放；
- 和的RotatE可解释为在向量空间中，通过在对应的复数空间内旋转；
- AGGREGATE：在传统方法中被实例化为自然求和、最大值或最小值，本文指定 AGGREGATE函数为求和、平均或最大值，后面跟着线性变换和非线性激活，本文还考虑了最近的一项工作中提出的主要邻域聚合（PNA），它共同学习聚合函数的类型和规模。
- INDICATOR：为源节点提供一个非平凡的表示作为边界条件。因此，我们学习一个查询嵌入来表示，并定义INDICATOR函数为。注意，也有可能额外学习一个的嵌入。然而本文发现直接嵌入效果更好。
边的表示在传统方法中被实例化为转移概率或长度。边在执行不同查询关系时可能有不同的贡献。因此，我们将边的表示参数化为查询关系上的线性函数，即。对于同质图或关系很少的知识图，我们简化参数化为 ，以防止过拟合。注意，也可以用可学习的实体嵌入和对 进行参数化，但这种参数化不能解决归纳问题。
NBFNet:
NBFNet把推理视作一个conditional node classification的问题，给定查询(u,q,?)完成以下步骤：
- 关于实体u初始化嵌入q；
- 通过GNN来propagate表征；
- 通过MLP进行node classification；
在本网络中，把简化为，即实体在轮迭代的表征，须注意的是，此处仍为实体对表征而不是单个节点的表征。
将神经函数代入公式3和4，我们就得到了贝尔曼-福德神经网络：
NBFNet与GNN
NBFNet可被视为一种学习实体对表征的新型GNN框架。
- 传统GNN框架通过分别独立计算实体的表征和实体表征来计算实体对表征。
- NBFNet初始化头实体的表征，通过尾实体计算实体对表征。
- 直观上，NBFNet框架可以被看作是一个特定源的信息传递过程，在这个过程中，每个节点学习的表示都是以源节点为条件的。
实验
Inductive relation prediction
GNN-QE
- 作者:Martin Wang
- 链接:https://www.martin1007wang.top//article/Neutal%20Bellam-Ford%20Networks%3A%20A%20General%20Graph%20Neural%20Network%20Framework%20for%20Link%20Prediction
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。