mem.academic
2 min read

知识图谱

memset0
memset0
Aug 31, 2024

关系图

异质图

异质图(heterogeneous graph) 是一种有向、点和边都有类型的图。其可以被定义为 G(V,E,R,T)G(V, E, R, T)，节点 viv_{i} 的类型为 T(vi)T(v_{i})；每条边记录为 (vi,r,vj)(v_{i},r,v_{j})，这里 r∈Rr\in R 表示这条边的类型。

知识图谱

知识图谱(Knowledge Graph, KG) 是以图形式呈现的知识，是异质图的一种。

  • 关于大型知识图谱，一个事实是：其存在大量的信息缺失——以 FreeBase 15k 为例，其中有 93.8% 的用户没有生日，有 78.5% 的用户没有国籍；此外，还缺少大量可能真实存在的边。

知识图谱中的常见 模式(pattern) 如下。对于后文提到的知识图谱相关算法，我们会考察他们在这些特定模式下的表达能力。

Relational GCN

为了应对边也有类型的问题，Relation GCN 的做法是对每一条类型的边都用一个不同的神经网络训练出一套权重。

hv(l+1)=σ(∑r∈R∑u∈Nvr1cv,rWr(l)hu(l)+Wr(0)hv(l))\mathbf{h}_v^{(l+1)}=\sigma\left(\sum_{r\in R}\sum_{u\in N_v^r}\frac1{c_{v,r}}\mathbf{W}_r^{(l)}\mathbf{h}_u^{(l)}+\mathbf{W}_r^{(0)}\mathbf{h}_v^{(l)}\right)
  • 参数量随关系类数的增长而线性增长，且容易产生过拟合问题。

正则化方法

Block Diagonal Matrices

限制非 0 元素的数量，让权重矩阵变成如图的若干对角块矩阵的形式，从而让参数量从 d(l+1)×d(l)d^{(l+1)} \times d^{(l)} 降低到 B×d(l+1)B×d(l)BB \times \dfrac{d^{(l+1)}}{B} \times \dfrac{d^{(l)}}{B}。但是这样的话——只有相邻的神经元/嵌入维度可以与权重矩阵交互。

Basis Learning

将特定关系的权重矩阵表示为 基变换(basis transformation) 的 线性组合(linear combination)，从而在不同关系之间共享权重参数。

Wr=∑b=1Barb⋅Vb\mathbf{W}_{r} = \sum_{b=1}^{B} a_{rb} \cdot \mathbf{V}_{b}

这里，Vb\mathbf{V}_{b} 是在不同关系之间共享的权重矩阵，对于每类关系我们只需要学习 {arb}b=1B\{a_{rb}\}_{b=1}^{B} 这 BB 个标量即可。

应用

节点分类任务

使用最后一层（prediction head）的输出 hA(L)\mathbf{h}_{A}^{(L)}（可经由 softmax 函数）作为对应节点作为每个类的概率。

边预测任务

将每种类型的边分为 training message edges, training supervision edges, validation edges, test edges 四类。按集合分有助于在保证确保每一类型的边都存在于四个集合中。

知识图谱补全

知识图谱补全(knowledge graph completion) 任务：已知 (head,relation)(\text{head}, \text{relation})，预测 tails\text{tails}。

  • 本节用 shallow encoding 而不是 GNN 的方式来进行图表示学习，即用固定向量表示图数据。

我们用 (h,r,t)(h,r,t) 来表示知识图谱中的一条边，对于真实数据三元组 (h,r,t)(h,r,t)，则 (h,r)(h,r) 的 embedding 应该尽可能地接近 tt 的 embedding。

TransE

设置评分函数为：

fr(h,t)=−∣∣h+r−t∣∣f_{r}(h,t) = - ||\mathbf{h}+\mathbf{r}-\mathbf{t}||

并应用 SGD 算法。

  • 在 symmetric relations 上失效：欲使 ∣∣h+r−t∣∣=0||\mathbf{h}+\mathbf{r}-\mathbf{t}||=0 和 ∣∣t+r−h∣∣||\mathbf{t}+\mathbf{r}-\mathbf{h}|| 同时成立，需要 r=0\mathbf{r}=0（没有学习到 r\mathbf{r} 的嵌入）或 h=t\mathbf{h}=\mathbf{t}（两个实体的 embedding 相同），都是不行的。
  • 在 1-to-N relations 上失效：欲使 ∣∣h+r−t1∣∣=0||\mathbf{h}+\mathbf{r}-\mathbf{t}_{1}||=0 和 ∣∣h+r−t2∣∣=0||\mathbf{h}+\mathbf{r}-\mathbf{t}_{2}||=0 同时成立，需要 t1=t2\mathbf{t}_{1} = \mathbf{t}_{2}，而两个实体的 embedding 相同是不行的。

TransR

将实体映射为实体空间 Rd\mathbb{R}^{d} 上的向量，将关系映射为关系空间 Rk\mathbb{R}^{k} 上的向量，对于每个类关系确定一个 投影矩阵(projection matrix) Mr∈Rk×d\mathbf{M}_{r}\in \mathbb{R}^{k \times d}，设 h⊥=Mrh, t⊥=Mrt\mathbf{h}_{\perp} = \mathbf{M}_{r} \mathbf{h},\ \mathbf{t}_{\perp} = \mathbf{M}_{r} \mathbf{t}。取评分函数

fr(h,t)=−∣∣h⊥+r−t⊥∣∣f_{r}(h,t) = - ||\mathbf{h}_{\perp} +\mathbf{r} - \mathbf{t}_{\perp}||
  • 在 composition relations 上失效：每个关系都有独立的空间域，不能自然组合。

DistMult

实体和关系都表示为 Rk\mathbb{R}^{k} 上的向量。取评分函数

fr(h,t)=<h,r,t>=∑i=1khi⋅ri⋅tif_{r}(h,t) = \text{<} \mathbf{h},\mathbf{r},\mathbf{t}\text{>} = \sum_{i=1}^{k} \mathbf{h}_{i} \cdot \mathbf{r}_{i} \cdot \mathbf{t}_{i}

评分函数可以看做是 h⋅r\mathbf{h}\cdot \mathbf{r} 与 t\mathbf{t} 之间的 cosine similarity —— h⋅t\mathbf{h} \cdot \mathbf{t} 与 t\mathbf{t} 同侧且靠近时 score 高。

  • 在 antisymmetric relations 上失效：在 fr(h,t)=<h,r,t>=<t,r,h>=fr(t,h)f_r(h,t)=\text{<} \mathbf{h},\mathbf{r},\mathbf{t} \text{>} = \text{<} \mathbf{t},\mathbf{r},\mathbf{h} \text{>} = f_r(t,h) 永远成立。

  • 在 inverse relations 上失效：欲使 <h,r1,t>=<h,r2,t>\text{<} \mathbf{h},\mathbf{r}_{1},\mathbf{t} \text{>} = \text{<} \mathbf{h}, \mathbf{r}_{2}, \mathbf{t} \text{>} 成立，必须有 r1=r2\mathbf{r}_{1} = \mathbf{r}_{2}，而这显然没有意义。

  • 在 composition relations 上失效：对多跳关系产生的超平面的联合（如 (r1,r2)(\mathbf{r}_{1},\mathbf{r}_{2})）无法用单一超平面（r3\mathbf{r}_{3}）表示。

ComplEx

在 DistMult 的基础上改用复数向量域 Ck\mathbb{C}^{k}（u=a+bi, u‾=a−bi\mathbf{u}=\mathbf{a}+\mathbf{b}i,\ \overline{\mathbf{u}} = \mathbf{a}-\mathbf{b}i）来表示实体和关系，取评分函数

fr(h,t)=Re⁡(∑ihi⋅ri⋅ti‾)f_{r}(h,t) = \operatorname*{Re}\left( \sum_{i} \mathbf{h}_{i} \cdot \mathbf{r}_{i} \cdot \overline{\mathbf{t}_{i}} \right)
  • 在 composition relations 上失效：理由和 DistMult 一致。

小结

TransE 和 TransR 等评分函数都是 L1L_{1} 或 L2L_{2} 距离的相反数；DistMult 和 ComplEx 的评分函数基于 双线性(bilinear) 模型。

四种算法的表示能力对比：

知识图谱推理

TBD

参考资料

Comments