Query2box Reasoning over Knowledge Graphs in Vector Space using Box Embeddings

• 概
• 符号说明
• Query2Box
• 代码

Ren H., Hu W. and Leskovec J. Query2box: Reasoning over knowledge graphs in vector space using box embeddings. ICLR, 2020.

概

Box embedding 用于查询判断, 和我想的那个有很大差别啊. 我对这方面不是很了解, 只能记录个大概.

符号说明

• \(\mathcal{G} = (\mathcal{V}, \mathcal{R})\) , 知识图谱;

• \(v \in \mathcal{V}\), entity;

• \(r \in \mathcal{R}\), 为某种关系, 是一个二元函数:

  \[r: \mathcal{V} \times \mathcal{V} \rightarrow \{\text{True}, \text{False}\}, \]

  满足 \(v \mathop{\rightarrow} \limits^{r} v' \text{ iff } r(v, v') = \text{True}\).

• Conjunctive queries 定义为:
  
  其中 \(v_a\) 是锚点, \(V_1, \ldots, V_k\) 是某些变量, \(V_?\) 是目标变量.

• 举个例子: "Where did Canadian citizens with Turing Award graduate?" 的查询中:

  1. [Truing Award], [Canada] 是锚点, 是起始变量;
  2. 这里只有一个(潜在)变量 [V], 它代表一些具体的人物: Pearl, Hinton, Bengio, Bieber, Trudeau;
  3. 目标变量 [V?] 是满足询问的回答, 即获得图灵奖且受奖于加拿大的大佬的毕业院校:
     1. Hinton: Edinburgh; Cambridge;
     2. Bengio: McGill.

• 我们用 \([\!\!| q |\!\!]\) 来表示答案的集合 (称为 denotation set 或 answer set), 它满足:

  \[v \in [\!\!| q |\!\!] \text{ iff } q[v] = \text{True}. \]

Query2Box

• Box embeddings 定义为二元组 \(\mathbf{p} = (\text{Cen}(\mathbf{p}), \text{Off}(\mathbf{p})) \in \mathbb{R}^{2d}\), 前者表示 box 的中心, 后者为 positive offset. 由此, 它定义了如下的 box:

  \[\text{Box}_{\mathbf{p}} := \{\mathbf{v} \in \mathbb{R}^d: \text{Cen}(\mathbf{p}) - \text{Off}(\mathbf{p}) \preceq \mathbf{v} \preceq \text{Cen}(\mathbf{p}) + \text{Off}(\mathbf{p})\}. \]

• 首先, 我们来看如何使用这个工具来进行 Conjunctive queries.

• Conjunctive queries 中包含 \(\exists, \wedge\) 这两个操作. 实际上等价于需要定义 Projection 和 Intersection 操作.

• 对于输入 \(\mathbf{p} = (\text{Cen}(\mathbf{p}), \text{Off}(\mathbf{p}))\), 和关系 box embedding \(\mathbf{r} = (\text{Cen}(\mathbf{r}), \text{Off}(\mathbf{r}))\), 定义投影为:

  \[\mathbf{p}' = \mathbf{p} + \mathbf{r}. \]

  \(\mathbf{p}'\) 可以看成是 \(\mathbf{p}\) 经过关系 \(\mathbf{r}\) 转换后得到下一阶段的变量 (它应当被理解成为那些和 \(\mathbf{p}\) 有紧密 \(\mathbf{r}\) 关系的向量表示 (当然无法完全一致)).

• 假设我们有了一堆可能的 box embeddings \(\{\mathbf{p}_1, \ldots, \mathbf{p}_n\}\), 我们需要找到一个尽可能满足 (即接近) 所有这些 box embeddings 的中心点

  \[\mathbf{p}_{\text{inter}} = (\text{Cen}(\mathbf{p}_{\text{inter}}), \text{Off}(\mathbf{p}_{\text{inter}})). \]

  具体定义为:
  
  其中

  \[\text{DeepSets}(\{\mathbf{x}_1, \ldots, \mathbf{x}_N\}) =\text{MLP}((1 / N) \cdot \sum_{i=1}^N \text{MLP}(\mathbf{x}_i)). \]

• 现在我们已经定义了 Projection, 他实现了关系转移, Interaction, 它实现了交的操作, 现在还需要实现一个给定 \(\mathbf{q} \in \mathbb{R}^{2d}\) 去找到相匹配的 entity \(\mathbf{v} \in \mathbb{R}^d\) (检索) 的操作:
  

• 如上图 (C) 所示: \(\text{dist}_{\text{outside}} (\mathbf{v}; \mathbf{q})\) 实际上是 \(\mathbf{v}\) 到 \(\text{Box}_{\mathbf{p}}\) 边缘的最短(街区)距离, 当然, 倘若 \(\mathbf{v}\) 在 Box 的内部, 概距离为 \(0\). 类似地, \(\text{dist}_{\text{inside}}(\mathbf{v}; \mathbf{q})\) 刻画的是 \(\text{Cen}(\mathbf{q})\) 到对应边缘的距离, 倘若 \(\mathbf{v}\) 在内部, 实际上就是 \(\text{Cen}(\mathbf{q})\) 到 \(\mathbf{v}\) 的街区距离.

• 当 \(\alpha = 1\) 的时候, 整个距离退化为 \(\|\text{Cen}(\mathbf{q}) - \mathbf{v}\|_1\).

• 训练, 采用如下损失

  \[L = -\log \sigma(\gamma - \text{dist}_{\text{box}}(\mathbf{v}; \mathbf{q})) - \sum_{i=1}^k \frac{1}{k} \log \sigma(\text{dist}_{\text{box}}(\mathbf{v}_i'; \mathbf{q}) - \gamma), \]

  其中 \(\gamma > 0\) 为人为给定的 margin, \(\mathbf{v} \in [\!\!| q |\!\!]\) 为正样本, \(\mathbf{v}' \not\in [\!\!| q |\!\!]\) 为负样本. 该损失是很直接的.

• 上面的操作综合下来看就是这样的:

  1. 给定一些锚点, 初始化为 \((\mathbf{x}, \mathbf{0})\);
  2. 让后锚点通过 Projection 状态转移;
  3. 多个锚点发生 Interaction 操作;
  4. 如有必要重复 2, 3.
  5. 最后得到一个 \(\mathbf{q}\), 然后通过 \(\text{dist}_{\text{box}}\) 来检索相似的.

• 但是我怀疑这种状态转移和 Interaction 的操作是不是会丢失掉太多的信息?

代码

[official]