526互联

Query2box Reasoning over Knowledge Graphs in Vector Space using Box Embeddings

发布时间 2023-07-14 09:16:43作者: 馒头and花卷

目录

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]