专栏首页NewBeeNLPGraph-Bert:没有我Attention解决不了的

Graph-Bert:没有我Attention解决不了的

作者 | kaiyuan

整理 | NewBeeNLP

最近要做一个图相关的项目,之前没怎么接触过图网络,就从头开始学习了一下,后面有时间也会整理分享。这里顺便推荐一下清华大学唐杰老师的一个分享:「图表示学习和图神经网络的最新理论进展」,主要介绍了图神经网络及其在认知推理方向的一些进展。

ok,今天这篇文章主要是记录下Graph-Bert的阅读笔记,跟我们现在要做的比较像,是关于「图网络的预训练」。这一块还有很多非常棒的资料,后续再慢慢整理分享吧。

  • 论文:https://arxiv.org/abs/2001.05140
  • 代码:https://github.com/jwzhanggy/Graph-Bert

enjoy~

TL;DR

在这篇文章中,作者指出了目前主流GNN完全依赖图链接,存在一些严重影响性能的问题

  • 模型假死(suspended animation):随着训练层数加深,模型不再对输入数据响应;
  • 过度平滑(over-smoothing):随着训练层数加深,所有结点的embedding会越来越相似;
  • 并行化处理(paralelization):在大图上无法并行化处理

针对以上问题,提出了Graph-BERT,同样是非常火的『pretrain+fintune』范式应用于图网络中。中心思想还是attention,首先将原始大图采样为一个个的子图,然后利用attention去学习结点表征。下面来看看具体模型

Model

如上图,Graph-Bert模型主要可以分为四部分:

  • 从原始大图中采样无连接子图(linkless graph)
  • 输入结点embedding处理
  • 基于图的transformer-encoder
  • 基于图的transformer-decoder

子图采样

为了更好地处理大图(并行化),graph-bert选择在采样子图上进行训练。使用了一种基于图亲密度矩阵

\mathbf{S} \in \mathbb{R}^{|\mathcal{V}| \times|\mathcal{V}|}

的采样方案:「top-k intimacy」,其中

S(i, j)

表示节点

v_{i}

和 结点

v_{j}

之间的亲密度,计算公式为:

\mathbf{S}=\alpha \cdot(\mathbf{I}-(1-\alpha) \cdot \overline{\mathbf{A}})^{-1}

其中,

\alpha

是一个[0, 1]之间的超参数(通常取0.15),

\overline{\mathbf{A}}=\mathbf{A} \mathbf{D}^{-1}

表示列规范化邻接矩阵,

A

为图的邻接矩阵,

D

为对应的对角矩阵

\mathbf{D}(i, i)=\sum_{j} \mathbf{A}(i, j)

那么对于一个给定的目标结点,就可以利用上面定义的亲密度来找出其上下文结点,计算公式为:

\Gamma\left(v_{i}\right)=\left\{v_{j} \mid v_{j} \in \mathcal{V} \backslash\left\{v_{i}\right\} \wedge\right. \left.\mathbf{S}(i, j) \geq \theta_{i}\right\}

其实这一步就是把图结构的数据转变成了我们平时常见的NLP序列化输入,把每个结点看成是一个个字或词,然后后面就可以直接套transformer了。记得之前有篇文章说的也是类似的:Transformers are Graph Neural Networks[1]

结点embedding

由于经过采样出来的结点们是无序的,这里按照「与target node的亲密度打分」来对结点集合进行排序。结点emdedding由四部分组成

「1. 原始特征embedding」

就是使用一个映射操作将原始特征表示到新的共享的特征空间,对于不同的输入可以有不同的映射函数,如CNN/LSTM/BERT等

\mathbf{e}_{j}^{(x)}=\operatorname{Embed}\left(\mathbf{x}_{j}\right) \in \mathbb{R}^{d_{h} \times 1}

「2. Weisfeiler-Lehman 绝对角色embedding」

Weisfeiler-Lehman算法是用来确定两个图是否是同构的,其基本思路是通过迭代式地聚合邻居节点的信息来判断当前中心节点的独立性(Identity),从而更新整张图的编码表示。

\begin{aligned} \mathbf{e}_{j}^{(r)} &=\text { Position-Embed }\left(\mathbf{W} \mathbf{L}\left(v_{j}\right)\right) \\ &=\left[\sin \left(\frac{\mathbf{W} \mathbf{L}\left(v_{j}\right)}{10000^{\frac{2 l}{d_{h}}}}\right), \cos \left(\frac{\mathbf{W} \mathbf{L}\left(v_{j}\right)}{10000^{\frac{2 l+1}{d_{h}}}}\right)\right]_{l=0}^{\left\lfloor\frac{d_{h}}{2}\right\rfloor} \end{aligned}

有关更多WL算法的细节可以参考这个slides:Graph Kernel[2]

「3. 基于亲密度的相对位置embedding」

上一节计算的嵌入可以表示全局的信息,而这一步主要是获取局部信息。

\mathbf{e}_{j}^{(p)}=\text { Position-Embed }\left(\mathrm{P}\left(v_{j}\right)\right) \in \mathbb{R}^{d_{h} \times 1}

「4. 基于相对距离embedding」

对两个结点在原始大图中的距离(间隔边的数量)进行embedding表示,主要是为了平衡上述两步的embedding

\mathbf{e}_{j}^{(d)}=\text { Position-Embed }\left(\mathrm{H}\left(v_{j} ; v_{i}\right)\right) \in \mathbb{R}^{d_{h} \times 1}

Transfomer编码器

「输入」

首先是对前面得到的四个embeeding进行聚合,

\mathbf{h}_{j}^{(0)}=\operatorname{Aggregate}\left(\mathbf{e}_{j}^{(x)}, \mathbf{e}_{j}^{(r)}, \mathbf{e}_{j}^{(p)}, \mathbf{e}_{j}^{(d)}\right)

聚合的函数有很多可以选择,文章里作者就使用了最简单的加和操作。聚合之后就可以得到所有结点的输入表示:

H^{(0)} = \left[\mathbf{h}_{i}^{(0)}, \mathbf{h}_{i 1}^{(0)}, \cdots, \mathbf{h}_{i k}^{(0)}\right]^{\top} \in \mathbb{R}^{(k+1) \times d_{h}}

「更新」

然后就是进行N层的transformer encoder的迭代更新,

\begin{aligned} \mathbf{H}^{(l)} &=\text { G-Transformer }\left(\mathbf{H}^{(l-1)}\right) \\ &=\operatorname{softmax}\left(\frac{\mathbf{Q} \mathbf{K}^{\top}}{\sqrt{d_{h}}}\right) \mathbf{V}+\mathbf{G}-\operatorname{Res}\left(\mathbf{H}^{(l-1)}, \mathbf{X}_{i}\right) \end{aligned}

「输出」

经过D层的编码之后,我们就可以得到对应每个结点的表示,

H^{(D)} = \left[\mathbf{h}_{i}^{(D)}, \mathbf{h}_{i 1}^{(D)}, \cdots, \mathbf{h}_{i k}^{(D)}\right]^{\top}

,之后就可以根据具体的下游任务来使用这些向量表示。

预训练

图神经网络的预训练大致分为两部分:对结点的预训练以及对链接关系的预训练。

结点预训练

对于目标结点

v_{i}

,原始特征为

x_{i}

,我们通过GRAPH-BERT编码层可以得到其隐藏表示

z_{i}

, 然后经过一层FC映射后

\hat{\mathbf{x}}_{i}=\mathrm{F} \mathrm{C}\left(\mathbf{z}_{i}\right)

重建原始特征。

\ell_{1}=\frac{1}{|\mathcal{V}|} \sum_{v_{i} \in \mathcal{V}}\left\|\mathbf{x}_{i}-\hat{\mathbf{x}}_{i}\right\|_{2}

链接关系预训练

这一部分其实是考虑了图的结构信息,利用两个节点表示的cos距离与之前提前算好的亲密度打分,来做损失。

\ell_{2}=\frac{1}{|\mathcal{V}|^{2}}\|\mathbf{S}-\hat{\mathbf{S}}\|_{F}^{2}

其中,

\hat{\mathbf{S}}(i, j)=\hat{s}_{i, j}

微调

在文章中介绍了两个微调任务:「节点分类」「图聚类」,效果看着都不错的样子。最后作者还加上了ablation study,分析了一些模型设置的效果,比如采样子图的结点数

k

,初始embedding,是否进行预训练等等。

本文参考资料

[1]

Transformers are Graph Neural Networks: https://graphdeeplearning.github.io/post/transformers-are-gnns/

[2]

Graph Kernel: https://www.slideshare.net/pratikshukla11/graph-kernelpdf

本文分享自微信公众号 - NewBeeNLP(NewBeeNLP),作者:kaiyuan

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-08-17

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Memory Transformer,一种简单明了的Transformer改造方案

    Transformer在广泛的自然语言处理和其他任务中非常成功。由于具有自我注意机制,可以训练Transformer层以使用在整个序列上聚合的信息来更新每个元素...

    NewBeeNLP
  • 关于ELMo,面试官们都怎么问

    以下是关于ELMo的若干问题整理记录,自己在网上找了一些问题,对每个问题收集了一些资料,并做了整理,有些问题还写了一些自己的看法,可能会有纰漏,甚至还有错误,还...

    NewBeeNLP
  • 微软ALUM:当语言模型遇到对抗训练

    本文把对抗训练用到了预训练和微调两个阶段,对抗训练的方法是针对embedding space,通过最大化对抗损失、最小化模型损失的方式进行对抗,在下游任务上取得...

    NewBeeNLP
  • 2-6 链表逆序

    A -> C -> B -> D -> E -> F -> null #将上面 B后的C 插入到A后面

    TeeyoHuang
  • 「经典重温」图表示学习经典算法 node2vec

    node2vec 是斯坦福男神教授 Jure Leskovec 的代表作之一,网上有非常多关于这篇论文的讨论和解析,所以这里我不再累述。

    Houye
  • 数据结构 键树查找法

    键树查找法 又称数字查找树(根节点子树>=2个),键树节点存储的不是某个关键字,而是组成关键字的单个符号。

    Debug客栈
  • 数据结构

    计算机二级中的公告基础部分有关于数据结构的部分,因此保存从百度中找来这些来方便自己的复习。在公共基础部分中,有数据结构,程序设计基础,软件工程基础,数据库设计基...

    sjw1998
  • 算法与数据结构(七) AOV网的拓扑排序(Swift版)

    今天博客的内容依然与图有关,今天博客的主题是关于拓扑排序的。拓扑排序是基于AOV网的,关于AOV网的概念,我想引用下方这句话来介绍: AOV网:在现代化管理中...

    lizelu
  • 线性表的链式存储结构的实现及其应用(C/C++实现)

    存档----------- 1 #include <iostream.h> 2 typedef char ElemType; 3 #include "Li...

    Angel_Kitty
  • 联通率先公布5G品牌标识 三大运营商你追我赶

    4月23日上午,中国联通正式发布全新5G品牌——5G,主题口号为“让未来生长”。此举使中国联通成为三大运营商中首个正式发布5G新品牌的运营商。

    加米谷大数据

扫码关注云+社区

领取腾讯云代金券