1. Reasoning over Knowledge Graphs
- 回忆：知识图谱补全任务1
- 本章主旨：介绍如何实现知识图谱上的多跳推理任务。
- 回答多跳查询问题，包括path queries和conjunctive queries。在某种程度上也可以说是在做知识图谱预测问题，在对任意predictive queries做预测。
- 介绍query2box方法。
- 知识图谱示例：Biomedicine（以下课程内容都会使用这个知识图谱来作为示例）
- KG上的predictive queries
任务目标：在一个incomplete的大型KG上做多跳推理（如回答复杂查询问题）。
对于某一类查询，我们可以自然语言的形式（绿色字）、formula/logical structure（棕色字）的形式或者graph structure（蓝色节点是查询中出现的实体，绿色节点是查询结果）的形式来表示它。
本节课仅讨论有formula/logical structure或graph structure后如何进行工作，从自然语言转换到对应形式的工作不在本课程讲解。
查询类型及示例：
- one-hop queries
What adverse event is caused by Fulvestrant?
(e:Fulvestrant, (r:Causes))
- path queries
What protein is associated with the adverse event caused by Fulvestrant?
(e:Fulvestrant, (r:Causes, r:Assoc))
- conjunctive queries
What is the drug that treats breast cancer and caused headache?
((e:BreastCancer, (r:TreatedBy)), (e:Migraine, (r:CausedBy))
- predictive one-hop queries
知识图谱补全任务可以formulate成回答one-hop queries问题：
KG补全任务：链接 ( h , r , t ) 在KG中是否存在？
one-hop query：t tt 是否是查询 ( h , ( r ) )的答案？
举例：What side effects are caused by drug Fulvestrant?
图中那个查询应该是少写了一个右括号
- 那么我们应该如何回答KG上的path query问题呢？
如果图是complete的话，那么我们只需要沿query plan直接traverse（遍历）KG就可以。
- 从anchor node（Fulverstrant）开始：
- 从anchor node（Fulverstrant）开始，遍历关系“Causes”，到达实体{“Brain Bleeding”, “Short of Breath”, “Kidney Infection”, “Headache”}
- 从实体{“Brain Bleeding”, “Short of Breath”, “Kidney Infection”, “Headache”}开始，遍历关系“Assoc”，到达实体{“CASP8”, “BIRC2”, “PIM1”}，即所求答案
- 但由于KG是incomplete的，所以如果仅traverse KG，可能会缺失一些关系，从而无法找到全部作为答案的实体。
- 因此我们就需要进行预测任务：predictive queries
目标：在incomplete KG上回答path-based queries
我们希望这一方法能够回答任意查询问题，同时隐式地impute或补全KG，实现对KG中缺失信息和噪音的鲁棒性。
对链接预测任务的泛化：从one-step link prediction task（就以前讲过的那种）到multi-step link prediction task（path queries）
2. Answering Predictive Queries on Knowledge Graphs
path query示例：
可以训练TransE来优化KG补全目标函数。
因为TransE天然可以处理composition relations，所以也能处理path queries，在隐空间通过叠加relation嵌入来表示多跳。
TransR / DistMult / ComplEx无法处理composition relations，因此很难像TransE这样轻易扩展到path queries上。
- conjunctive queries
示例：
What are drugs that cause Short of Breath and treat diseases associated with protein ESR2?
((e:ESR2, (r:Assoc, r:TreatedBy)), (e:Short of Breath, (r:CausedBy))
query plan：
- 同样，如果KG是complete的话，直接traverse KG就行：
- 同样，如果KG有关系缺失了，有些答案就会找不到：
- 我们希望通过嵌入方法来隐式impute KG中缺失的关系 (ESR2, Assoc, Breast Cancer)。
如图所示，ESR2与BRCA1和ESR1都有interact关系，这两个实体都与breast cancer有assoc关系：
- 再回顾一遍query plan，注意图中的中间节点都代表实体，我们也需要学习这些实体的表示方法。此外我们还需要定义在隐空间的intersection操作。
3. Query2box: Reasoning over KGs Using Box Embeddings
- key insight: intersection
- embed with box embedding
- 用box embedding，用projection operator，沿query plan求解：
- 接下来我们的问题就在于：如何定义box上的intersection？
有一种对intersection的定义比较严格，就是定义为数学上的intersection，类似于维恩图。
我们想要更flexible一点的定义，就如下文所介绍：
直觉：
- 输出box的center应该靠近输入boxes的centers
- offset (box size) 应该收缩（因为intersected set应该比所有input set的尺寸都小）
（如图中阴影所示部分）
- intersection operator公式
- offset
- 通过定义intersection operator，现在我们可以完成使用box embedding沿query plan的求解：
- extending to union operation
析取问题示例：What drug can treat breast cancer or lung cancer?
conjunctive queries + disjunction被叫做Existential Positive First-order (EPFO) queries，也叫AND-OR queries。
disjunction或
以下图示中，红点（答案）是我们希望在box中的实体，蓝点（负答案）是我们希望在box外的实体：
对三个点来说，二维是足够的。
- 因为我们无法在低维空间嵌入 AND-OR queries，所以对这类问题，我们的处理思路就是把所有query plan前面的union操作单拎出来，只在最后一步进行union操作。
如图所示：
- 抽样query：从templates生成
- 生成复杂query的流程：从query template开始，通过实例化query template中的变量为KG中实际存在的实体和关系来生成query（如实例化Anchor1为KG节点ESR2，Rel1为KG边Assoc）。
query template可以视作是query的抽象。
如图所示：
- 实例化query template的具体方法：从实例化答案节点开始，迭代实例化其他边和节点，直至到达8所有anchor nodes
- 实例化query template示例：
从query template的根节点开始：从KG中随机选择一个实体作为根节点，例如我们选择了Fulverstrant
然后我们看intersection：实体集的intersection是Fulverstrant，则两个实体集自然都应包含Fulverstrant
我们通过随机抽样一个连接到当前实体Fulverstrant的关系，来实例化对应的projection edge。举例来说，我们选择关系TreatedBy，检查通过TreatedBy关系连接到Fulverstrant的实体：{Breast Cancer}
以此类推，完成一条支路：
类似地，完成另一条支路：
- 在嵌入域可视化查询答案
示例：List male instrumentalists who play string instruments
用t-SNE将嵌入向量降维到2维
可视化节点嵌入和query plan：
anchor node的嵌入：
投影：
投影：
anchor node的嵌入：
投影：
intersection：
4. 本章总结
本章介绍了在大型KG上回答predictive queries。
关键思想在嵌入查询，通过可学习的operator来实现嵌入。在嵌入域中，query的嵌入应该靠近其答案的嵌入。
