CompGCN

CompGCN
论文来源:ICLR 2020
论文链接:https://arxiv.org/abs/1911.03082
代码链接:https://github.com/malllabiisc/CompGCN

1、引言

图神经网络已经成为图数据分析领域的经典算法了,各大顶会上相关的论文也层出不穷.但是,这些工作主要关注点都在如何在简单无向图上设计一个更新颖更复杂的模型,而没有从图数据的复杂程度来考虑.实际生活中的图往往更加复杂.比如,知识图谱上的有向多关系图.下面是一个知识图谱的例子,这里有多种节点,如London和United Kingdom;也有多种有向关系,如Born-in和Citizen-of.注意,这里的关系是有方向的,Born-in和Bord-in_inv是同一关系的两个方向.

可以看出,多关系图的建模是更符合实际也具有更高的应用价值.本文作者从实际的图数据特点出发,设计了一种针对多关系有向图的图神经网络CompGCN来同时学习节点和关系的表示.同时,为了降低大量不同类型关系带来的参数,这里作者设计了一种分解操作composition operation,将所有关系都用一组基的加权组合来表示. 这样用于描述关系的参数只和基的个数有关.

下图对比了几种图神经网络的特点,可以看看出:学习关系的表示是CompGCN独有的特点.

总的来说,本文的贡献有3点:

  • 设计了CompGCN模型,一种可以考虑多种关系信息的图神经网络框架,来同时学习节点和关系的表示.
  • 证明了CompGCN与之前的多关系GNN之间的联系.
  • 实验验证了CompGCN的有效性.

2、Related work

GCN:
GCN->切比雪夫多项式近似
都遵循Message Passing Neural Networks (MPNN) 框架,本文也是其特例;但专注于relational graphs。

3、background

CompGCN

\(W_k\): layer-specific ,每一个层k只有一个W。

CompGCN

\(W_r^k\): relation specific,and layer-specific ,每一个层k对每一种关系r有一个W。
但是,由于关系太多,参数也太多了->Marcheggiani只使用了direction-specific的W。

Schlichtkrull提出基和W的块对角化分解(basis、block-diagonal decomposition),解决了over-parameterization。

对比一下:(?为什么参数不乘节点数目n)

CompGCN

4、模型CompGCN

CompGCN

$G = (V; R; E; \mathcal{X} ; \mathcal{Z}) $

扩展双向边

CompGCN

聚合邻居边和节点

初始节点嵌入(只考虑一阶邻居,一层):

CompGCN

N(v)是节点v的出边形成的邻居集合。

CompGCN

  1. \(\phi\)函数定义了三种。composition operation,复合操作。
  2. ??。。这里是只有三种转换矩阵?还是在每种r上,有分类讨论有三种各不一样?(我认为为后者。但数学公式感觉是前者?)

更新完节点的embedding之后,更新关系r的embedding:

CompGCN

\(W_{rel}\)是一个转换矩阵,得到的\(h_r\)可以被后面的layer利用。

\(z_r\)选取基向量的组合:

随着关系数量的增加而扩展

CompGCN

后续层的更新

只在第一层定义关系的基向量,之后使用\(W_{rel}^k\)转换为k+1层的\(h_r\)。

CompGCN

4、实验

这里,作者分别在链路预测,节点分类,图分类上进行了实验.
CompGCN
在链路预测任务上(见Table 3),CompGCN在大部分情况下取得了最优的效果.

作者进一步测试了不同composition operator的影响,见Table 4
CompGCN
当采取CovE+CompGCN(Corr)的时候,模型取得了最佳的效果.

CompGCN的一个特点就是利用基向量来表示各个关系.作者进一步测试了基向量的个数对模型效果的影响.
CompGCN
Figure 3可以看出,在基向量个数设置为100的时候,模型可以保持99.4%的效果.如果进一步降低基向量的个数,模型效果会持续下降.

作者也测试了固定5个基向量的CompGCN与R-GCN的表现,见Figure 4.可以看出,即使只有5个基向量,CompGCN的效果也优于考虑所有关系的R-GCN.

CompGCN
最后,作者也测试了CompGCN在节点分类/图分类上的效果,见Table 5. 在大部分情况下,CompGCN都取得了最好的效果.

CompGCN

5、结论

本文提出了一种针对多关系图的图神经网络CompGCN,可以同时学习到节点和边的表示. 通过一组基向量,CompGCN可以用较少的参数实现对大量关系的描述. 最后,作者通过大量的实验验证了CompGCN的有效性.

上一篇:PDSCH Port 5 UE-Specific Beamforming


下一篇:CVPR2020行人重识别算法论文解读