CompGCN: Composition-based Multi-Relational Graph Convolutional Networks


本文前置知识:

Composition-based Multi-Relational Graph Convolutional Networks

本文是论文Composition-based Multi-Relational Graph Convolutional Networks的阅读笔记和个人理解.

Basic Idea

作者观察到, 现在GCN在图建模中存在两个问题:

  1. 现实世界中的图经常是有向图, 但现在图领域的研究常常专注于简单的无向图问题.

  2. GCN的过参数化问题很严重, 并且只学习节点表示限制了模型表达.

作者希望提出一种对节点和关系联合嵌入的GCN模型来应对上述问题.

CompGCN

GCN and R - GCN

对于图$\mathcal{G}=(\mathcal{V}, \mathcal{E}, \mathcal{X})$, $\mathcal{V}, \mathcal{E}, \mathcal{X}$ 分别代表图中存在的顶点, 边, 和节点的初始特征.

让我们先来回顾一下经典的GCN的节点特征更新方程:

$$
\boldsymbol{H}^{k+1}=f\left(\hat{\boldsymbol{A}} \boldsymbol{H}^{k} \boldsymbol{W}^{k}\right)
$$
其中$\hat{\boldsymbol{A}}$ 是由度矩阵和自邻接矩阵归一化得到的.

R - GCN中, 引入了对不同关系$\mathcal{R}$ 的特化处理, 图结构变为了$\mathcal{G}=(\mathcal{V}, \mathcal{R}, \mathcal{E}, \mathcal{X})$:
$$
\boldsymbol{H}^{k+1}=f\left(\hat{\boldsymbol{A}} \boldsymbol{H}^{k} \boldsymbol{W}_{r}^{k}\right)
$$

其中, $\boldsymbol{W}_r$ 为关系特化的变换矩阵.

但和大多数只嵌入节点的常规GCN方法不同, CompGCN同时嵌入节点关系, 图结构信息变为$\mathcal{G}=(\mathcal{V}, \mathcal{R}, \mathcal{E}, \mathcal{X}, \mathcal{Z})$, $\mathcal{Z}$ 代表初始化的关系特征.

边的种类也被作者额外区分, 能对逆边自环边加以区分, 即:
$$
\left.\mathcal{E}^{\prime}=\mathcal{E} \cup\left\{\left(v, u, r^{-1}\right) \mid(u, v, r) \in \mathcal{E}\right\} \cup\{(u, u, \top) \mid u \in \mathcal{V})\right\}
$$

相应的, 关系也被加以区分, 即$\mathcal{R}^{\prime}=\mathcal{R} \cup \mathcal{R}_{i n v} \cup\{\top\}$, 其中$\mathcal{R}_{i n v}=\left\{r^{-1} \mid r \in \mathcal{R}\right\}$.

Relation - Based Composition

引入关系嵌入后, 与KGE方法一样, 作者利用关系嵌入$\mathbf{e}_s$ 和实体嵌入$\mathbf{e}_r$ 的组合操作将节点和关系的信息作为整体共同$\mathbf{e}_o$, 纳入GCN的更新方程:
$$
\boldsymbol{e}_{o}=\phi\left(\boldsymbol{e}_{s}, \boldsymbol{e}_{r}\right)
$$

其中, $\phi: \mathbb{R}^{d} \times \mathbb{R}^{d} \rightarrow \mathbb{R}^{d} $ 是关系和实体嵌入的组合方式.

将关系表示为Embedding减轻了图神经网络中针对关系的过参数化问题.

我个人的理解是, 在R - GCN中, 关系特化以变换矩阵$\boldsymbol{W}_r$ 的形式存在, 而CompGCN中以Embedding的形式存在, 减少了每种关系所对应的参数个数. Embedding是信息的低维表征, 万物皆可Embedding.

作者尝试了三种实体关系组合方式:

  • Subtraction(Sub): $\phi\left(\mathbf{e}_{s}, \mathbf{e}_{r}\right)=\mathbf{e}_{s}-\mathbf{e}_{r}$.
  • Multiplication(Mult): $\phi\left(\boldsymbol{e}_{s}, \boldsymbol{e}_{r}\right)=\boldsymbol{e}_{s} \ast \boldsymbol{e}_{r}$.
  • Circular - correlation(Corr): $\phi\left(\boldsymbol{e}_{s}, \boldsymbol{e}_{r}\right)=\boldsymbol{e}_{s} \star \boldsymbol{e}_{r}$.

分别是相减, 相乘, 循环相关运算. 循环相关运算出自论文Holographic embeddings of knowledge graphs, 即HoLE的论文. 三阶时的计算方法与行列式的主对角线计算中组合方式是相似的:

循环相关运算相比于前两种更为复杂, 考虑了更多向量间的不同组合方式.

通过关系实体组合操作, 关系和实体的嵌入组合特征将在同一特征空间下对节点信息更新.

CompGCN Update Equation

普通GCN的节点表示更新方程如下:

$$
\boldsymbol{h}_{v}=f\left(\sum_{(u, r) \in \mathcal{N}(v)} \boldsymbol{W}_{r} \boldsymbol{h}_{u}\right)
$$

其中, $\mathcal{N}(v)$ 是节点$v$ 的出边邻居, $(u,r)$ 是邻居节点和相对应的和关系. $\boldsymbol{h}_u$ 为节点$u$ 的特征.

而CompGCN引入关系实体嵌入的组合后, 的节点更新方式如下:

$$
\boldsymbol{h}_{v}=f\left(\sum_{(u, r) \in \mathcal{N}(v)} \boldsymbol{W}_{\lambda(r)} \phi\left(\boldsymbol{x}_{u}, \boldsymbol{z}_{r}\right)\right)
$$

其中$\lambda(r)$ 针对边的种类做了特化, 同一种关系在不同的边类型上也许会得到区分. 作者将边分为出边, 入边, 和自环边三种. 在这里$\lambda(r)=\text{dir}(r)$:

$$
\boldsymbol{W}_{\mathrm{dir}(r)}=\left\{\begin{array}{ll}
\boldsymbol{W}_{O}, & r \in \mathcal{R} \\
\boldsymbol{W}_{I}, & r \in \mathcal{R}_{i n v} \\
\boldsymbol{W}_{S}, & r=\top(\text { self-loop })
\end{array}\right.
$$

在该模式下, 一些以前的方法能够被纳入CompGCN的框架之中:

从CompGCN的身上能偶找到这些过去方法的影子.

关系嵌入同节点嵌入的聚合一样, 也需要做类似的更新, 但关系没有邻居之类的概念, 直接用简单的投影即可:
$$
\boldsymbol{h}_{r}=\boldsymbol{W}_{\mathrm{rel}} \boldsymbol{z}_{r}
$$

$\boldsymbol{W_{\text{rel}}}$ 是与关系无关的变换矩阵, 它只是将初始关系嵌入$\boldsymbol{z}_{r}$ 投影到关系嵌入空间而已.

与R - GCN一样, CompGCN也使用基函数分解来减轻GCN的过参数化. 但用途仅为获得初始化的关系嵌入$\boldsymbol{z}_r$:
$$
\boldsymbol{z}_{r}=\sum_{b=1}^{\mathcal{B}} \alpha_{b r} \boldsymbol{v}_{b}
$$
基函数分解并没有在后续更新关系(边)的Embedding中使用到.

上述为CompGCN在只有一层情况下的说明.

CompGCN in Multilayer

对于多层的情况, 只需要将上面的方程改写为含有层数$k$ 的形式:
$$
\boldsymbol{h}_{v}^{k+1}=f\left(\sum_{(u, r) \in \mathcal{N}(v)} \boldsymbol{W}_{\lambda(r)}^{k} \phi\left(\boldsymbol{h}_{u}^{k}, \boldsymbol{h}_{r}^{k}\right)\right)
$$

关系表示$\boldsymbol{h}_r^k$ 的更新也按照多层形式写出:

$$
\boldsymbol{h}_{r}^{k+1}=\boldsymbol{W}_{\mathrm{rel}}^{k} \boldsymbol{h}_{r}^{k}
$$

注意, $\boldsymbol{W}_{\text{rel}}$ 每层参数都是不同的, 多层GCN也对关系嵌入多次迭代更新.

作者对比了CompGCN与普通GCN方法的优势:

$K$ 为GCN的层数, $d$ 为Embedding维度, $\mathcal{B}$ 为基的数量, $\lvert \mathcal{R} \rvert$ 为关系个数.

CompGCN复杂度中的第一项来自于与层数相关的$\boldsymbol{W}_{\text{rel}}, \boldsymbol{W}_{\lambda(r)}$, 第二, 三项分别来自于基函数分解中的基$\boldsymbol{v}_{b}$ 和标量$\alpha_{b r}$.

相较于其他的GCN算法, 尤其是R - GCN, CompGCN保持了相对少的参数量.

Experiments

详细的实验参数设置请参照原论文.

CompGCN在链接预测上的玩法仍然沿用了R - GCN中Encoder - Decoder的架构

R - GCN使用的Decoder是DistMult, 解码时关系嵌入需要额外训练, 并且存在实体嵌入和关系嵌入的方法不匹配问题, 这就割裂了实体嵌入和关系嵌入的关系. 但CompGCN在编码阶段就引入了关系嵌入, 不会存在关系和实体嵌入训练不匹配的问题:

Main Result

作者在FB15k - 237和WN18RR上做了Link Prediction, 结果如下:

无论是比传统的KGE方法, 还是其他基于图的KGE方法, CompGCN的综合表现比较不错, 在WN18RR上的Hits@10比RotatE少了三个点.

Comparison in CompGCN

作者主要比较了不同GCN方法在不同Decoder下的链接预测性能表现, 其形式为$\mathbf{X}+\mathbf{M}(\mathbf{Y})$, $\mathbf{X}$ 代表某种KGE方法的打分函数, $\mathbf{M}$ 代表用来获取实体和关系Embedding的GCN方法名称, $\mathbf{Y}$ 代表组合操作符.

在FB15k - 237上的结果如下:

几乎所有的GCN方法会导致TransE的性能退化, 但CompGCN没有. 可能因为关系和实体的联合学习. 不同的组合操作所擅长的优化指标是不相同的.

Scalability of CompGCN

Effect of Varying Relation Basis Vectors

作者比较了FB15k - 237上不同基向量个数对相对MRR的影响:

当基向量个数为237, 即关系不使用基向量时性能达到最好. 但采用更少的基向量并不会带来非常明显的性能衰减.

Effect of Number of Relations

作者比较了FB15k - 237中, 对于相同的基函数为5的情况下, 不同关系数量上的相对MRR:

即使固定基函数为5, 仍然能比较好的应对繁多的关系.

上述两个实验说明关系之间可能存在着大量线性相关, 少量的基向量完全可以重新组合表示它们.

Comparison with R - GCN

作者对比了R - GCN和CompGCN在FB15k - 237的不同关系数量子集中的表现:

仅仅在5个基函数的情况下, CompGCN全面优于R - GCN.

Node and Graph Classification

在节点和图分类任务中, CompGCN表现如下:

这两个数据集上, 对于简单的节点分类和图分类问题, CompGCN表现良好.

Summary

CompGCN进一步地将Knowledge Embedding中对待关系的方法引入了GCN领域, 在之前的GCN类方法中, 常不将关系嵌入引入, 而在KGE领域中, 将关系和实体嵌入共同使用是非常普遍的.

CompGCN算是集大成者, 作者考虑了很多关于GCN过参数化的内容. 同时兼顾有向, 多关系, 支持关系嵌入三种特性.

作者着重论述了CompGCN的各方面优势, 例如复杂度, 可扩展性, 以及具体任务的性能等.

作者在文中使用的是非参数化的组合方式, 其实也可以尝试参数化的组合, 这样也会引入更高的复杂度.

作者也没有考虑引入Attention来增强边对节点的影响, 而是使用了对边类型的特化来处理, 可能Attention的泛用性更强一些.


文章作者: AnNing
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 AnNing !
评论
 上一篇
KBAT: Learning Attention-based Embeddings for Relation Prediction in KGs KBAT: Learning Attention-based Embeddings for Relation Prediction in KGs
本文前置知识: GAT: 详见图神经网络入门. Learning Attention-based Embeddings for Relation Prediction in Knowledge Graphs本文是论文Learning
2021-04-04
下一篇 
KEQA: Knowledge Graph Embedding Based Question Answering KEQA: Knowledge Graph Embedding Based Question Answering
Knowledge Graph Embedding Based Question Answering本文是论文Knowledge Graph Embedding Based Question Answering的阅读笔记和个人理解. Bas
2021-03-30
  目录