Graph Neural Networks 综述

2019 年 8 月 13 日 计算机视觉life
Graph Neural Networks 综述

点击上方“计算机视觉life”,选择“星标”

快速获得最新干货


深度学习一直都是被几大经典模型给统治着,如CNN、RNN等等,它们无论再计算机视觉CV还是自然语言处理NLP领域都取得了优异的效果。

针对CV领域,图像是一个二维的结构,于是人们发明了卷积神经网络CNN来提取图像特征。CNN的核心在于它的卷积核kernel,kernel是一个小窗口,在图像上平移滑动,并不断与图像进行卷积来提取窗口内的特征。这种操作的有效性在于二维图像结构的平移不变性:一个小窗口无论移动到图像的哪一个位置,其内部的结构都是一致的,因此CNN可以实现参数共享。这就是CNN的精髓所在。

针对RNN领域,它的对象是自然语言这样的序列信息,是一个一维结构,RNN就是专门针对这些序列结构而设计的,通过各种门的操作,使得序列前后的信息互相影响,从而很好地捕捉序列的特征。

图像和自然语言,都属于欧式空间Euclidean Structure的数据,欧式空间的数据的特点就是结构很规则。但是现实生活中,其实有很多很多不规则的数据结构,典型的就是图Graph结构,或称拓扑结构,如社交网络、化学分子结构、知识图谱等等;即使是语言,实际上其内部也是复杂的树形结构,也是一种图结构;而像图片,在做目标识别的时候,我们关注的实际上只是二维图片上的部分关键点,这些点组成的也是一个图的结构。

图的结构一般来说是十分不规则的,每一个节点的度不尽相同,所以它没有平移不变性,导致传统的CNN、RNN瞬间失效。所以很多学者从上个世纪就开始研究怎么处理这类数据了。这里涌现出了很多方法,例如GNN、DeepWalk、node2vec等等。

图神经网络GNN的根本目标就是学习图中每个节点v的表示 ,可以认为是提取每个节点的最终特征。每个节点的表示是根据当前节点特征和其邻居节点特征进行更新,这和CNN具有相同的本质。最简单的图结构是由节点和无向边构成,而实际上会分为有向图异构图(不同类型的节点)和带边信息的图结构(不同权重或类型的边),如下图所示。综上所述,图神经网络需要解决的难点就是如何根据相邻节点特征和边的信息对当前节点特征进行更新!

最终的节点特征能够让我们可以去对图数据进行节点分类(node classification)、图分类(graph classification)、边预测(link prediction),还可以得到图的嵌入表示(graph embedding),用途非常广泛。

其实,针对Euclidean Structure数据,同样可以使用GNN,广义上来讲任何数据在赋范空间内都可以建立拓扑关联,谱聚类就是应用了这样的思想

GNN根据传播方式也可以分为以下几类:图卷积神经网络GCN(Graph Convolution Networks)、基于注意力更新的图网络GAT(Graph Attention Networks)、基于门控的图网络(Gate Updater)、具有跳边的图网络(skip connection)。下文对这几种图神经网络进行概述。

GCN

GCN的本质目的就是用来提取拓扑图的空间特征,spectral domain就是GCN的理论基础了。这种思路就是希望借助图谱的理论来实现拓扑图上的卷积操作。Spectral graph theory简单的概括就是借助于图的拉普拉斯矩阵的特征值和特征向量来研究图的性质

背景知识

(1) 拉普拉斯矩阵

对于一个图Graph,其拉普拉斯(Laplacian)矩阵的定义如下:

其中,D:Degree matrix 图中节点的度矩阵(对角矩阵,对角线上元素为各节点的度)

A:Adjacency matrix 图的邻接矩阵,反映图中每个节点之间边的特性。可见下图进行理解。

为了避免神经网络反向传播过程中的梯度消失,一般会使用归一化拉普拉斯矩阵(Symmetric normalized Laplacian):

GCN的核心是根据拉普拉斯矩阵的特征值和特征向量来研究图的性质,所以需要进一步对拉普拉斯矩阵进行特征分解。

拉普拉斯矩阵是半正定对称矩阵,具有以下三个属性

(1)对称矩阵一定n个线性无关的特征向量

(2)半正定矩阵的特征值一定非负

(3)对阵矩阵的特征向量相互正交,即所有特征向量构成的矩阵为正交矩阵

对拉普拉斯矩阵进行特征分解:

其中,:由特征向量组成的矩阵

:n个特征值构成的对角阵

由于 是正交矩阵,即 ,所以特征分解又可以写成:

(2)Graph傅里叶(逆)变换

为了生成Graph中的卷积操作,需要把传统的傅里叶变换以及卷积迁移到Graph上来,核心工作其实就是把拉普拉斯算子的特征函数 变为Graph对应的拉普拉斯矩阵的特征向量。

传统傅里叶变换定义如下:

即信号 与基函数 乘积的积分

傅里叶变换的本质是任意一个函数可以表示为若干个正交函数(sin,cos函数)组成的线性组合,如下图所示:

而在图结构中,同理,把Graph中N维向量表示为若干个正交函数的线性组合,自然而然地想到了图拉普拉斯矩阵的特征向量。所以,仿照传统傅里叶变换,在图结构中的离散傅里叶定义如下:

其中,是图Graph中的N维向量, 与Graph的顶点一一对应

表示第 个特征向量的第 个分量。

那么特征值 下的,的Graph傅里叶变换就是与 对应的特征向量进行内积运算。

注:上述的内积运算是在复数空间中定义的,所以采用了 ,也就是特征向量 的共轭。

进一步将Graph傅里叶变换推广为矩阵形式:

而针对傅里叶的逆变换,传统傅里叶逆变换是对频率进行积分:

同理,针对Graph傅里叶逆变换是对特征向量进行积分:

推广到矩阵形式如下:

(3)图的卷积操作

根据傅里叶变换的性质可知函数 两者的卷积是其函数傅立叶变换乘积的逆变换:

同理,针对Graph卷积, 的傅里叶变换为 ,卷积核 的傅里叶变换写成对角矩阵的形式即为 ,即

两者的傅立叶变换乘积即为:

再对其进行逆变换,即左乘一个 ,最终得到Graph中的卷积操作:

到这步,就有了对Graph进行卷积来提取特征的理论基础了。

第一代GCN

类似CNN中的卷积形式,论文Spectral Networks and Locally Connected Networks on Graphs直接将上文中的卷积项 变成了卷积核 再进行非线性运算,那么上文的卷积输出为

其中,

:激活函数

:GCN权重训练参数,通过初始化赋值并利用误差反向传播进行调整

:graph上对应于每个顶点的特征向量(由数据集提取特征构成的向量)

第一代GCN的存在着一些弊端

1)每一次前向传播,都要计算,三者的矩阵乘积,特别是对于大规模的graph,计算代价较高

2)卷积过程需要n个参数,参数数量较多。

第二代GCN

论文Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering把 巧妙地设计成了,也就是:

进一步整理得

并根据以下公式:

从而导出

最终生成

其中 是训练参数,通过初始化赋值然后利用误差反向传播进行调整。

第二代GCN设计的卷积核有如下特点:

1)卷积核只有 个参数,一般 远小于 ,参数的复杂度被大大降低了

2)矩阵变换后,神奇地发现不需要做特征分解了,直接用拉普拉斯矩阵 进行变换。然而由于要计算 ,计算复杂度还是

3)卷积核有很好的空间局部性(图论:通过计算邻接矩阵的K次方得到的矩阵非零位置表示两个节点存在长度为K的路径,K就是卷积核的receptive field,也就是说每次卷积会将节点的路径长度为K的领域节点的特征进行加权求和),可见下图分析:

注:GCN每次卷积过程对所有节点进行上图操作。

Chebyshev多项式递归计算卷积核

在第二代GCN中, 的矩阵,所以 的计算复杂度还是 ,论文Wavelets on graph via special graph theory提出了利用切比雪夫Chebyshev多项式拟合上文卷积核的方法,来降低计算复杂度。卷积核可以利用截断(truncated)的shifted Chebyshev多项式来近似逼近。

其中, (经的最大特征值(即谱半径)缩放后的特征向量矩阵)的Chebyshev多项式,进行这个shift变换的原因是Chebyshev多项式的输入要在 [-1,1]之间

:Chebyshev多项式的系数

从而可得到:

由Chebyshev多项式的性质,已知以下递推公式

阶多项式,且有

其中,

这样,就得到下述的公式:

这个时候不难发现:卷积操作不再有矩阵乘积了,只需要计算矩阵与向量的乘积即可。计算一次 的复杂度是 是图中边的集合,则整个运算的复杂度是 。当graph是稀疏图的时候,计算加速尤为明显,这个时候复杂度远低于

该近似的谱图卷积虽然可以建立起 阶邻居的依赖,然而,却仍然需要在 上进行 阶运算。在实际过程中,这一运算的代价也是非常大的。为了降低运算代价,本文进一步简化了该运算,即限定 。此时,谱图卷积可以近似为 (或 )的线性函数。

当然,这样做的代价是,只能建立起一阶邻居的依赖。对于这一问题,可以通过堆积多层图卷积网络建立 阶邻居的依赖,而且,这样做的另一个优势是,在建立 阶邻居的依赖时,不需要受到切比雪夫多项式的限制。

为了进一步简化运算,在GCN的线性模型中,本文定义 。此时,我们可以得到图谱卷积的一阶线性近似:

可以看到,该式中仅有两个参数。若需建立阶邻居上的依赖,可以通过设置层这样的滤波器来实现。

在实际的过程中,可以通过对参数进行约束来避免过拟合,并进一步简化运算复杂度。例如,可以令 ,从而得到

需要注意的是, 的特征值范围为[0,2],这意味着,当不停地重复该操作时(网络非常深时),可能会引起梯度爆炸或梯度消失。为了减弱这一问题,提出了一种 renormalization trick:

其中,

只使用A的话,由于A的对角线上都是0,所以在对其进行信息提取的收,只会计算当前节点所有邻居的特征加权和,该节点自身的特征却被忽略了。因此,我们可以做一个小小的改动,给A加上一个单位矩阵,这样就让对角线元素变成1了,形成一个自环

当图中每个节点的表示不是单独的标量而是一个大小为 的向量时,可以使用其变体进行处理:

其中,表示参数矩阵,为相应的卷积结果。N为图中节点个数,C为每个节点的特征向量维度,F是变换后每个节点特征向量的维度,此时,每个节点的节点表示被更新成了一个新的 维向量,该 维向量包含了相应的一阶邻居上的信息。

经过以上的推导,本文得到了图卷积神经网络的(单层)最终形式

其中, 第 层网络的输入为(初始输入为

为图中的节点数量,每个节点使用 维的特征向量进行表示

为添加了自连接的邻接矩阵

为度矩阵,

为待训练的参数

为相应的激活函数,例如

训练过程中,输入图结构,经过GCN特征提取,输出每个节点最终表示,计算有标签的节点的训练损失,进行反向传播误差进行梯度下降算法来调整权重参数,可实现半监督分类。

Semi-Supervised Classification with Graph Convolutional Networks

github地址

基于谱的方法需要学习的参数都是与Laplacian矩阵的特征向量和特征值相关的,即取决于图的结构,这样有什么问题呢,如果你在一个大图或者很多同构的小图上进行训练是可以的,这也有很多应用场景。但是如果我们要处理很多不同结构的图,那就不能用同一套参数来学习,不惧泛化性,比如我们对很多树结构的句子进行分类(句子表示为依存句法树或其他),每个句子的表示可能都不同,那就没办法用上面的方法做。

DeepSEA

Convolutional Networks on Graphs for Learning Molecular Fingerprints

github地址

DeepSEA

为了对图中每个节点特征进行更新,DeepSEA使用最简单的算法,即根据邻接矩阵获取当前节点的邻居节点,再把对其邻居节点特征进行直接求和,以实现对当前节点特征的更新,更新公式如下所示:

其中,:邻居节点表示的向量和

第一个公式为收集和整合当前节点的邻居节点特征

第二个公式为对当前节点特征进行更新。

DCNN

Diffusion-Convolutional Neural Networks

github地址

为了对图中每个节点进行分类,需对每个节点特征进行更新,DCNN提出的更新公式如下:

其中,

, P是通过将邻接矩阵中每一行除以该行节点的度计算得到的度归一化邻接矩阵,是一个N×N张量,而是将(K×N×N的张量)经过维度变换生成的张量,N是图中节点个数

X:图中所有节点的特征矩阵,是张量,F为每个节点特征的长度

:是一个维度为K×F的权重参数

:点乘

Z :维度为N×K×F的节点表示

f():一个非线性函数

获取了每个节点表示,为了进一步对节点进行分类,再对Z进行全连接操作,生成N×C的张量,最后使用softmax。公式如下:

针对节点分类,整个算法流程可用下图表示:

注:图中就是上文的N,H就是上文的K,就是上文的Z。

GraphSAGE

Inductive Representation Learning on Large Graphs

github地址

GraphSAGE框架的核心是如何聚合节点邻居特征信息来对当前节点特征进行更新,下文介绍GraphSAGE前向传播过程(生成节点embedding)和不同的聚合函数设定。

1. 前向传播

下图是GraphSAGE 生成目标节点(红色)embededing并供下游任务预测的过程:

(1)先对邻居随机采样,降低计算复杂度(图中一跳邻居采样数=3,二跳邻居采样数=5)

(2)生成目标节点emebedding:先聚合二跳邻居特征,生成一跳邻居embedding,再聚合一跳邻居embedding,生成目标节点embedding,从而间接获得二跳邻居信息。

(3)将embedding作为全连接层的输入,预测目标节点的标签。

前向传播伪代码如下:

2. 聚合函数

每个节点需要获取邻居节点的特征信息,这个过程叫做聚合过程。聚合过程可以使用不同聚合函数,本小节介绍五种满足排序不变量的聚合函数:平均、GCN归纳式、LSTM、pooling聚合器。(因为邻居没有顺序,聚合函数需要满足排序不变量的特性,即输入顺序不会影响函数结果)

a.平均聚合:先对邻居embedding中每个维度取平均,然后与目标节点embedding拼接后进行非线性转换。

其中,:当前节点v的邻居节点上一层的embedding

: 当前节点v的邻居节点

b. 归纳式聚合:直接对目标节点和所有邻居emebdding中每个维度取平均(替换伪代码中第5、6行),后再非线性转换:

c. LSTM聚合:LSTM函数不符合“排序不变量”的性质,需要先对邻居随机排序,然后将随机的邻居序列embedding 作为LSTM输入。

d. Pooling聚合器: 先对每个邻居节点上一层embedding进行非线性转换(等价单个全连接层,每一维度代表在某方面的表示(如信用情况)),再按维度应用 max/mean pooling,捕获邻居集上在某方面的突出的/综合的表现 以此表示目标节点embedding。

对于上述所有的聚合方法,可以使用以下统一公式进行概括:

这里的AGGREGATE可以指上文中不同的聚合函数。

GAT

GRAPH ATTENTION NETWORKS

github地址

图的节点之间的信息传递当然也可以用attention进行控制(NLP中的每个单词、CV中的每个像素当做一个节点,它们的attention都可以当做是在图上的操作),通过当前节点的不同邻居与当前节点的关系计算信息流的权重, Graph Attention Network (GAT) 提出了用注意力机制对邻居节点特征加权求和。邻居节点特征的权重完全取决于节点特征,独立于图结构。

图注意力模型 GAT 用注意力机制替代了GCN中固定的标准化操作。以下公式定义了如何对第 l 层节点特征做更新得到第 l+1 层节点特征:

其中,

第一个等式表示对节点特征表示进行线性变换(为第l层中图第i个节点的特征嵌入)

第二个等式计算了成对节点间的原始注意力分数。它首先拼接了两个节点的 特征嵌入Z( || 在这里表示拼接concatenate);随后对拼接好的嵌入以及一个可学习的权重向量做点积;最后应用了一个 LeakyReLU 激活函数。

第三个等式公式对一个节点所有入边的原始注意力分数应用了一个 softmax 操作,得到了注意力权重

第四个等式形似 GCN 的节点特征更新规则,对所有邻节点的特征做了基于注意力的加权求和

上述节点特征嵌入可用如下示意图进行表示:

GGNN

PPT

GATED GRAPH SEQUENCE NEURAL NETWORKS

github地址

相比于GNN,GGNN的特点在于使用了门控单元来控制信息的传播,比如可以用GRU,LSTM等门控方式来传递图的信息而且,节点表示的更新次数被固定成了 也就是说,GGNN并不能保证图的最终状态会到达不动点。由于更新次数 变成了固定值,因此GGNN可以直接使用BPTT算法来进行梯度的计算。

1.传播过程

这里只介绍一下基于GRU的GGNN,传播过程可以表示为:

其中,表示图中节点与其他节点的连接关系( 可以视作将邻接矩阵的每一个“1”元素替换为的传播矩阵得到),在大多数情况下,是比较稀疏的矩阵,而且,在同一类型的边上,参数是共享的

的一个子矩阵,对应于中与节点有关的列。

|V|是节点个数

D是表示一个节点所需的维度,2D|V|中的2是因为边有两种类型,如下图(c)所示。

第一个等式是一个初始化步骤,用于将节点特征复制到节点状态向量中,其余部分使用0补齐。

第二个等式用于不同节点之间的信息传播,这些信息传播要受到图中边的限制(包括是否有边、边的方向以及边的类型)。包含了每个方向上的激活。

其余等式就是GRU单元。分别表示更新门与重置门,为sigmoid函数,表示逐元素相乘

2.输出过程

根据任务的不同,GGNN可以有多种不同形式的输出。

当GGNN用于node-focused任务时,对于每个节点都需要有一个输出:

若对于图级(graph-level)输出,可以定义一个图的表示向量:

其中,相当于一个soft attention机制,用于决定哪个节点与当前的任务有关。 都是神经网络,其输入是的连接,输出是实值向量。tanh函数也可以被替换为恒等变换。

Skip connection

Semi-supervised User Geolocation via Graph Convolutional Networks

github地址

相比于传统的网络,GNN的深度一般更浅,原因是随着深度的增加,梯度消失很明显,以及GNN的感受野指数增大在信息传递过程中会引入大量噪声。所以在GNN中也有人尝试加入skip connection来缓解这个问题。下面是一个用Highway门控的方法的例子:

其中,

第一个公式计算Highway的权重,用于控制层输入信息对当前层的影响

第二个公式根据Highway权重综合计算层的输入和输出的门控权重和来获取最终节点特征嵌入

参考资料

(1) [Graph Neural Networks (GNN)综述 简介]

(https://zhuanlan.zhihu.com/p/68015756)

(2) [如何理解 Graph Convolutional Network(GCN)?]

(https://www.zhihu.com/question/54504471/answer/332657604)

(3) [图卷积神经网络(GCN)详解:包括了数学基础(傅里叶,拉普拉斯)](https://zhuanlan.zhihu.com/p/67522582)

(4) [Gated Graph Sequence Neural Networks]

(https://arxiv.org/abs/1511.05493)

(5) [Graph Attention Networks](https://arxiv.org/abs/1710.10903)

(6) [深入理解图注意力机制](https://zhuanlan.zhihu.com/p/57180498)

(7)[如何理解 Graph Convolutional Network(GCN)?]

(https://www.zhihu.com/question/54504471/answer/730625049)

交流群

欢迎加入公众号读者群一起和同行交流,目前有SLAM、算法竞赛、图像检测分割、人脸人体、医学影像、自动驾驶、综合等微信群(以后会逐渐细分),请扫描下面微信号加群,备注:”昵称+学校/公司+研究方向“,例如:”张三 + 上海交大 + 视觉SLAM“。请按照格式备注,否则不予通过。添加成功后会根据研究方向邀请进入相关微信群。请勿在群内发送广告,否则会请出群,谢谢理解~


如有AI领域实习、求职、招聘、项目合作、咨询服务等需求,快来加入我们吧,期待和你建立连接,找人找技术不再难!

推荐阅读

目标检测技术二十年综述

最全综述 | 医学图像处理

最全综述 | 图像分割算法

最全综述 | 图像目标检测

综述 | 视频分割在移动端的算法进展

综述 | 语义分割经典网络及轻量化模型盘点

计算机视觉方向简介 | 从全景图恢复三维结构

计算机视觉方向简介 | 阵列相机立体全景拼接

计算机视觉方向简介 | 单目微运动生成深度图

计算机视觉方向简介 | 深度相机室内实时稠密三维重建

计算机视觉方向简介 | 深度图补全

计算机视觉方向简介 | 人体骨骼关键点检测综述

计算机视觉方向简介 | 人脸识别中的活体检测算法综述

计算机视觉方向简介 | 目标检测最新进展总结与展望

计算机视觉方向简介 | 唇语识别技术

计算机视觉方向简介 | 三维深度学习中的目标分类与语义分割

计算机视觉方向简介 | 基于单目视觉的三维重建算法

计算机视觉方向简介 | 用深度学习进行表格提取

计算机视觉方向简介 | 立体匹配技术简介

计算机视觉方向简介 | 人脸表情识别

计算机视觉方向简介 | 人脸颜值打分

计算机视觉方向简介 | 深度学习自动构图

计算机视觉方向简介 | 基于RGB-D的3D目标检测

计算机视觉方向简介 | 人体姿态估计

计算机视觉方向简介 | 三维重建技术概述

计算机视觉方向简介 | 视觉惯性里程计(VIO)

计算机视觉方向简介 | 多目标跟踪算法(附源码)

计算机视觉方向简介 | 基于自然语言的跨模态行人re-id的SOTA方法(上)

计算机视觉方向简介 | 图像拼接


最新AI干货,我在看  


登录查看更多
21

相关内容

图卷积网络(简称GCN),由Thomas Kpif于2017年在论文Semi-supervised classification with graph convolutional networks中提出。它为图(graph)结构数据的处理提供了一个崭新的思路,将深度学习中常用于图像的卷积神经网络应用到图数据上。

知识荟萃

精品入门和进阶教程、论文和代码整理等

更多

查看相关VIP内容、论文、资讯等

题目: Continuous Graph Neural Networks

摘要:

本文建立了图神经网络与传统动力系统之间的联系。我们提出了持续图神经网络(CGNN),它将现有的图神经网络与离散动力学进行了一般化,因为它们可以被视为一种特定的离散化方案。关键思想是如何表征节点表示的连续动力学,即关于时间的节点表示的导数。受现有的基于扩散的图方法(如社交网络上的PageRank和流行模型)的启发,我们将导数定义为当前节点表示、邻节点表示和节点初始值的组合。我们提出并分析了两种可能的动态图,包括节点表示的每个维度(又名特征通道)各自改变或相互作用的理论证明。所提出的连续图神经网络在过度平滑方面具有很强的鲁棒性,因此允许我们构建更深层次的网络,进而能够捕获节点之间的长期依赖关系。在节点分类任务上的实验结果证明了我们提出的方法在和基线对比的有效性。

介绍

图神经网络(GNNs)由于其在节点分类等多种应用中的简单性和有效性而受到越来越多的关注;、链接预测、化学性质预测、自然语言理解。GNN的基本思想是设计多个图传播层,通过聚合邻近节点的节点表示和节点本身的表示,迭代地更新每个节点表示。在实践中,对于大多数任务,几层(两层或三层)通常就足够了,更多的层可能导致较差的性能。

改进GNNs的一个关键途径是能够建立更深层次的网络,以了解数据和输出标签之间更复杂的关系。GCN传播层平滑了节点表示,即图中相邻的节点变得更加相似。当我们堆叠越来越多的层时,这会导致过度平滑,这意味着节点表示收敛到相同的值,从而导致性能下降。因此,重要的是缓解节点过平滑效应,即节点表示收敛到相同的值。

此外,对于提高我们对GNN的理论理解,使我们能够从图结构中描述我们可以学到的信号,这是至关重要的。最近关于理解GCN的工作(Oono和Suzuki, 2020)认为GCN是由离散层定义的离散动力系统。此外,Chen等人(2018)证明了使用离散层并不是构建神经网络的唯一视角。他们指出,带有剩余连接的离散层可以看作是连续ODE的离散化。他们表明,这种方法具有更高的记忆效率,并且能够更平滑地建模隐藏层的动态。

我们利用基于扩散方法的连续视角提出了一种新的传播方案,我们使用来自常微分方程(即连续动力系统)的工具进行分析。事实上,我们能够解释我们的模型学习了什么表示,以及为什么它不会遭受在GNNs中常见的过度平滑问题。允许我们建立更深层次的网络,也就是说我们的模型在时间价值上运行良好。恢复过平滑的关键因素是在连续设置中使用了最初在PageRank中提出的原始分布。直观上,重新开始分布有助于不忘记邻接矩阵的低幂次信息,从而使模型收敛到有意义的平稳分布。

本文的主要贡献是:

  • 基于PageRank和扩散方法,提出了两个连续递增模型容量的ODEs;
  • 我们从理论上分析了我们的层学习的表示,并表明当t → ∞我们的方法接近一个稳定的不动点,它捕获图结构和原始的节点特征。因为我们在t→∞时是稳定的,我们的网络可以有无限多个“层”,并且能够学习远程依赖关系;
  • 我们证明了我们的模型的记忆是高效的,并且对t的选择是具有鲁棒性的。除此之外,我们进一步证明了在节点分类任务上,我们的模型能够比许多现有的最先进的方法表现更好。
成为VIP会员查看完整内容
0
89

题目: Introduction to Graph Neural Networks

简介:

在复杂的实际应用中,图是有用的数据结构,例如对物理系统进行建模,学习分子指纹,控制交通网络以及在社交网络中推荐朋友。但是,这些任务需要处理包含元素之间的丰富关系信息且无法通过传统深度学习模型(例如卷积神经网络(CNN)或递归神经网络(RNN))妥善处理的非欧氏图数据。图中的节点通常包含有用的特征信息,这些信息在大多数无监督的表示学习方法(例如,网络嵌入方法)中无法很好地解决。提出了图神经网络(GNN)来结合特征信息和图结构,以通过特征传播和聚集学习更好的图表示。由于其令人信服的性能和高解释性,GNN最近已成为一种广泛应用的图形分析工具。本书全面介绍了图神经网络的基本概念,模型和应用。首先介绍了香草GNN模型。然后介绍了vanil la模型的几种变体,例如图卷积网络,图递归网络,图注意力网络,图残差网络和一些通用框架。还包括不同图类型的变体和高级训练方法。对于GNN的应用,该书将min分为结构,非结构和其他场景,然后介绍了解决这些任务的几种典型模型。最后,最后几章提供了GNN的开放资源以及一些未来方向的展望。

深度学习在许多领域都取得了可喜的进展,例如计算机视觉和自然语言处理。这些任务中的数据通常以欧几里得表示。但是,许多学习任务需要处理包含元素之间丰富的关系信息的非欧氏图数据,例如建模物理系统,学习分子指纹,预测蛋白质界面等。图神经网络(GNN)是基于深度学习的方法,在图域上运行。由于其令人信服的性能和高解释性,GNN最近已成为一种广泛应用的图形分析方法。本书全面介绍了图神经网络的基本概念,模型和应用。它从数学模型和神经网络的基础开始。在第一章中,它对GNN的基本概念进行了介绍,目的是为读者提供一个概览。然后介绍了GNN的不同变体:图卷积网络,图递归网络,图注意力网络,图残差网络和一些通用框架。这些最差的结果是将通用的深度学习技术转化为图形,例如卷积神经网络,递归神经网络,注意力机制和跳过连接。此外,这本书介绍了GNN在结构场景(物理,化学,知识图谱),非结构场景(图像,文本)和其他场景(生成模型,组合优化)中的不同应用。最后,这本书列出了相关的数据集,开源平台和GNN的实现。本书组织如下。在第1章中进行了概述之后,在第2章中介绍了数学和图论的一些基本知识。在第3章中介绍了神经网络的基础,然后在第4章中简要介绍了香草GNN。四种类型的模型分别在第5、6、7和8章中介绍。在第9章和第10章中介绍了不同图类型和高级训练方法的其他变体。然后在第11章中提出了几种通用的GNN框架。第12、13和14章介绍了GNN在结构场景,非结构场景和其他场景中的应用。最后,我们在第15章提供了一些开放资源,并在第16章总结了这本书。

成为VIP会员查看完整内容
Introduction to Graph Neural Networks.pdf
0
157

题目: Graph Random Neural Networks

摘要:

图神经网络(GNNs)将深度学习方法推广到图结构数据中,在图形挖掘任务中表现良好。然而,现有的GNN常常遇到具有标记节点的复杂图结构,并受到非鲁棒性、过度平滑和过拟合的限制。为了解决这些问题,本文提出了一个简单而有效的GNN框架——图随机神经网络(Grand)。与现有GNNs中的确定性传播不同,Grand采用随机传播策略来增强模型的鲁棒性。这种策略也很自然地使Grand能够将传播从特征转换中分离出来,减少了过度平滑和过度拟合的风险。此外,随机传播是图数据扩充的一种有效方法。在此基础上,利用无标记节点在多个扩展中的分布一致性,提高模型的泛化能力,提出了Grand的一致性正则化方法。在图形基准数据集上的大量实验表明,Grand在半监督的图形学习任务上显著优于最先进的GNN基线。最后,证明了它可以显著减轻过度平滑和过度拟合的问题,并且它的性能与鲁棒性相结合。

成为VIP会员查看完整内容
0
103

近年来,人们对学习图结构数据表示的兴趣大增。基于标记数据的可用性,图表示学习方法一般分为三大类。第一种是网络嵌入(如浅层图嵌入或图自动编码器),它侧重于学习关系结构的无监督表示。第二种是图正则化神经网络,它利用图来增加半监督学习的正则化目标的神经网络损失。第三种是图神经网络,目的是学习具有任意结构的离散拓扑上的可微函数。然而,尽管这些领域很受欢迎,但在统一这三种范式方面的工作却少得惊人。在这里,我们的目标是弥合图神经网络、网络嵌入和图正则化模型之间的差距。我们提出了图结构数据表示学习方法的一个综合分类,旨在统一几个不同的工作主体。具体来说,我们提出了一个图编码解码器模型(GRAPHEDM),它将目前流行的图半监督学习算法(如GraphSage、Graph Convolutional Networks、Graph Attention Networks)和图表示的非监督学习(如DeepWalk、node2vec等)归纳为一个统一的方法。为了说明这种方法的一般性,我们将30多个现有方法放入这个框架中。我们相信,这种统一的观点既为理解这些方法背后的直觉提供了坚实的基础,也使该领域的未来研究成为可能。

概述

学习复杂结构化数据的表示是一项具有挑战性的任务。在过去的十年中,针对特定类型的结构化数据开发了许多成功的模型,包括定义在离散欧几里德域上的数据。例如,序列数据,如文本或视频,可以通过递归神经网络建模,它可以捕捉序列信息,产生高效的表示,如机器翻译和语音识别任务。还有卷积神经网络(convolutional neural networks, CNNs),它根据移位不变性等结构先验参数化神经网络,在图像分类或语音识别等模式识别任务中取得了前所未有的表现。这些主要的成功仅限于具有简单关系结构的特定类型的数据(例如,顺序数据或遵循规则模式的数据)。

在许多设置中,数据几乎不是规则的: 通常会出现复杂的关系结构,从该结构中提取信息是理解对象之间如何交互的关键。图是一种通用的数据结构,它可以表示复杂的关系数据(由节点和边组成),并出现在多个领域,如社交网络、计算化学[41]、生物学[105]、推荐系统[64]、半监督学习[39]等。对于图结构的数据来说,将CNNs泛化为图并非易事,定义具有强结构先验的网络是一项挑战,因为结构可以是任意的,并且可以在不同的图甚至同一图中的不同节点之间发生显著变化。特别是,像卷积这样的操作不能直接应用于不规则的图域。例如,在图像中,每个像素具有相同的邻域结构,允许在图像中的多个位置应用相同的过滤器权重。然而,在图中,我们不能定义节点的顺序,因为每个节点可能具有不同的邻域结构(图1)。此外,欧几里德卷积强烈依赖于几何先验(如移位不变性),这些先验不能推广到非欧几里德域(如平移可能甚至不能在非欧几里德域上定义)。

这些挑战导致了几何深度学习(GDL)研究的发展,旨在将深度学习技术应用于非欧几里德数据。特别是,考虑到图在现实世界应用中的广泛流行,人们对将机器学习方法应用于图结构数据的兴趣激增。其中,图表示学习(GRL)方法旨在学习图结构数据的低维连续向量表示,也称为嵌入。

广义上讲,GRL可以分为两类学习问题,非监督GRL和监督(或半监督)GRL。第一个系列的目标是学习保持输入图结构的低维欧几里德表示。第二系列也学习低维欧几里德表示,但为一个特定的下游预测任务,如节点或图分类。与非监督设置不同,在非监督设置中输入通常是图结构,监督设置中的输入通常由图上定义的不同信号组成,通常称为节点特征。此外,底层的离散图域可以是固定的,这是直推学习设置(例如,预测一个大型社交网络中的用户属性),但也可以在归纳性学习设置中发生变化(例如,预测分子属性,其中每个分子都是一个图)。最后,请注意,虽然大多数有监督和无监督的方法学习欧几里德向量空间中的表示,最近有兴趣的非欧几里德表示学习,其目的是学习非欧几里德嵌入空间,如双曲空间或球面空间。这项工作的主要动机是使用一个连续的嵌入空间,它类似于它试图嵌入的输入数据的底层离散结构(例如,双曲空间是树的连续版本[99])。

鉴于图表示学习领域的发展速度令人印象深刻,我们认为在一个统一的、可理解的框架中总结和描述所有方法是很重要的。本次综述的目的是为图结构数据的表示学习方法提供一个统一的视图,以便更好地理解在深度学习模型中利用图结构的不同方法。

目前已有大量的图表示学习综述。首先,有一些研究覆盖了浅层网络嵌入和自动编码技术,我们参考[18,24,46,51,122]这些方法的详细概述。其次,Bronstein等人的[15]也给出了非欧几里德数据(如图或流形)的深度学习模型的广泛概述。第三,最近的一些研究[8,116,124,126]涵盖了将深度学习应用到图数据的方法,包括图数据神经网络。这些调查大多集中在图形表示学习的一个特定子领域,而没有在每个子领域之间建立联系。

在这项工作中,我们扩展了Hamilton等人提出的编码-解码器框架,并介绍了一个通用的框架,图编码解码器模型(GRAPHEDM),它允许我们将现有的工作分为四大类: (i)浅嵌入方法,(ii)自动编码方法,(iii) 图正则化方法,和(iv) 图神经网络(GNNs)。此外,我们还介绍了一个图卷积框架(GCF),专门用于描述基于卷积的GNN,该框架在广泛的应用中实现了最先进的性能。这使我们能够分析和比较各种GNN,从在Graph Fourier域中操作的方法到将self-attention作为邻域聚合函数的方法[111]。我们希望这种近期工作的统一形式将帮助读者深入了解图的各种学习方法,从而推断出相似性、差异性,并指出潜在的扩展和限制。尽管如此,我们对前几次综述的贡献有三个方面

  • 我们介绍了一个通用的框架,即GRAPHEDM,来描述一系列广泛的有监督和无监督的方法,这些方法对图形结构数据进行操作,即浅层嵌入方法、图形正则化方法、图形自动编码方法和图形神经网络。

  • 我们的综述是第一次尝试从同一角度统一和查看这些不同的工作线,我们提供了一个通用分类(图3)来理解这些方法之间的差异和相似之处。特别是,这种分类封装了30多个现有的GRL方法。在一个全面的分类中描述这些方法,可以让我们了解这些方法究竟有何不同。

  • 我们为GRL发布了一个开源库,其中包括最先进的GRL方法和重要的图形应用程序,包括节点分类和链接预测。我们的实现可以在https://github.com/google/gcnn-survey-paper上找到。

成为VIP会员查看完整内容
0
182

Deep learning has revolutionized many machine learning tasks in recent years, ranging from image classification and video processing to speech recognition and natural language understanding. The data in these tasks are typically represented in the Euclidean space. However, there is an increasing number of applications where data are generated from non-Euclidean domains and are represented as graphs with complex relationships and interdependency between objects. The complexity of graph data has imposed significant challenges on existing machine learning algorithms. Recently, many studies on extending deep learning approaches for graph data have emerged. In this survey, we provide a comprehensive overview of graph neural networks (GNNs) in data mining and machine learning fields. We propose a new taxonomy to divide the state-of-the-art graph neural networks into different categories. With a focus on graph convolutional networks, we review alternative architectures that have recently been developed; these learning paradigms include graph attention networks, graph autoencoders, graph generative networks, and graph spatial-temporal networks. We further discuss the applications of graph neural networks across various domains and summarize the open source codes and benchmarks of the existing algorithms on different learning tasks. Finally, we propose potential research directions in this fast-growing field.

0
9
下载
预览
小贴士
相关资讯
一文读懂图卷积GCN
计算机视觉life
15+阅读 · 2019年12月21日
图神经网络(Graph Neural Networks,GNN)综述
极市平台
60+阅读 · 2019年11月27日
【NeurIPS2019】图变换网络:Graph Transformer Network
跳出公式,看清全局,图神经网络(GCN)原理详解
AI科技评论
64+阅读 · 2019年9月22日
图嵌入(Graph embedding)综述
人工智能前沿讲习班
364+阅读 · 2019年4月30日
图神经网络综述:方法及应用 | Deep Reading
AI100
30+阅读 · 2019年3月17日
论文浅尝 | 图神经网络综述:方法及应用
开放知识图谱
99+阅读 · 2019年2月14日
图神经网络综述:模型与应用
PaperWeekly
159+阅读 · 2018年12月26日
网络表示学习介绍
人工智能前沿讲习班
15+阅读 · 2018年11月26日
深度学习之CNN简介
Python技术博文
14+阅读 · 2018年1月10日
相关论文
Text Level Graph Neural Network for Text Classification
Lianzhe Huang,Dehong Ma,Sujian Li,Xiaodong Zhang,Houfeng WANG
7+阅读 · 2019年10月6日
Geometric Graph Convolutional Neural Networks
Przemysław Spurek,Tomasz Danel,Jacek Tabor,Marek Śmieja,Łukasz Struski,Agnieszka Słowik,Łukasz Maziarka
7+阅读 · 2019年9月11日
A Comprehensive Survey on Graph Neural Networks
Zonghan Wu,Shirui Pan,Fengwen Chen,Guodong Long,Chengqi Zhang,Philip S. Yu
9+阅读 · 2019年3月10日
Graph Neural Networks: A Review of Methods and Applications
Jie Zhou,Ganqu Cui,Zhengyan Zhang,Cheng Yang,Zhiyuan Liu,Lifeng Wang,Changcheng Li,Maosong Sun
9+阅读 · 2019年3月7日
Hao Peng,Jianxin Li,Qiran Gong,Senzhang Wang,Yuanxing Ning,Philip S. Yu
5+阅读 · 2019年2月25日
Graph2Seq: Graph to Sequence Learning with Attention-based Neural Networks
Kun Xu,Lingfei Wu,Zhiguo Wang,Yansong Feng,Michael Witbrock,Vadim Sheinin
6+阅读 · 2018年12月3日
Yao Ma,Ziyi Guo,Zhaochun Ren,Eric Zhao,Jiliang Tang,Dawei Yin
15+阅读 · 2018年10月24日
Keyulu Xu,Weihua Hu,Jure Leskovec,Stefanie Jegelka
18+阅读 · 2018年10月1日
Muhan Zhang,Yixin Chen
23+阅读 · 2018年2月27日
Ruoyu Li,Sheng Wang,Feiyun Zhu,Junzhou Huang
5+阅读 · 2018年1月10日
Top