图解GNN:A Gentle Introduction to Graph Neural Networks

2022年01月16日 阅读数:7
这篇文章主要向大家介绍图解GNN:A Gentle Introduction to Graph Neural Networks,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

1.图是什么?

  本文给出得图的定义为:A graph represents the relations (edges) between a collection of entities (nodes).node

  即:图表示实体(节点)集合之间的关系(边)。算法

    

  其中 $V$  表示顶点,$E$  表示边,$U$  表示全局。能够看到每个定义后面都有一个 attributes,这意味着咱们不能只关注图的一个结构信息,还应该关注属性信息,好比节点的邻居数,边的权重,最长路径等等。网络

  • $V$:节点信息(节点标识、节点邻居数)
  • $E$:节点信息(边标识、边权重)
  • $U$:全局信息(节点数、最长路径)

  为了深刻表示每一个节点、边和整个图,咱们能够用以下的存储方式:dom

    

  把节点信息、边信息和全局信息作  embedding,通俗地说就是把这些信息存储为向量的形式。因此图神经的核心就是,怎么样把咱们想要的信息表示成向量,以及向量是否能经过数据学习到。函数

  图的边分为无向边和有向边。学习

2.数据如何表示成图?

  如下是几种图表示的例子:优化

2.1 图像

  Images as graphs(将图片表示为图)spa

  一般把图片表示为三维  $tensor$,如  $224x224x3$。实际上能够把每一个像素做为一个点,存在邻接关系则造成一条边。设计

  

  每个像素点都和周围八个像素点相连,所以邻接矩阵中这八个位置都为1。3d

  所以对于 $image$ 数据,若是它有  $5 × 5 $  个像素点,那么咱们就可以创建一个拥有  $25$  个节点的图,每一个节点能够跟其周围八个节点相连。

2.2 文本

  文本能够被认为是一个序列,其中每个词做为一个节点,每个词和其下一个词以前有一条有向边:

    

2.3 其余数据

  除了上述图像和文本外,还有一些数据,除了图之外,咱们很难用其余形式来表示他们!

2.3.1 分子

  分子中原子经过做用力连在一块儿,所以每个原子能够表示为一个点,原子间键表示为边。 以下图是一个香料分子:

    

  以及咖啡因分子:

    

2.3.2 社交网络

  在社交网络中,咱们将我的表示为节点,将他们间的关系表示为边。

  好比戏剧中人物关系图:

    

2.3.3 引文图

  将论文抽象为节点,论文  $A$  引用了论文  $B$  ,则有一条有向边  $A->B$  。

3.图中的任务

  图里面的任务主要分为三大类:图级、节点级和边级。

  在图级任务中,咱们预测整个图的属性。对于节点级任务,咱们预测图中每一个节点的一些属性。对于边级任务,咱们但愿预测图中边的属性或者是否存在这条边。

3.1 图级任务

  在图级任务中,咱们的目标是预测整个图的属性。 好比对于某一分子,咱们可能想要预测该分子的气味,或者它是否会和与疾病有关的受体结合。

    

   这里咱们输入的是一张图,输出的是该图的  $label$ ,好比该图是否有两个环?

3.2 节点级任务

  节点级任务主要预测单个节点的属性。

  节点级预测问题的一个经典示例是空手道俱乐部数据集,该数据集是一个社交网络图,每一个节点都具备一个惟一的  $label$。

    

  这里每个节点的标签要么为  Mr. Hi,要么为  Officer。在这种状况下,咱们就能够创建一个模型对某一个节点的  $label$  进行预测。

  所以,节点预测的输入是一个图,输出是节点的标签:

3.3 边级任务

  对于边级任务:给定一些节点,咱们但愿预测这些节点中的哪些共享一条边或该边的权值是什么。

     

   边的预测(链路预测)的例子是经过语义分割把人物、背景拿出来,而后分析实体间的关系(属性)。好比黄衣服的人在踢绿衣服的人,他们都站在地毯上。

    

4.使用图数据的挑战

  在使用神经网络对图进行处理前,咱们得先将图表示成神经网络可以处理的数据类型。

  图上的信息有四种:节点属性、边属性、全局属性以及链接性。

  图表示的难点在于怎么来表示图的链接性。 最容易想到的就是邻接矩阵:相连为1不然为0。

  不过,使用邻接矩阵来表示链接性的缺点是显而易见的:对于一些大型网络,其节点数可能上百万,而且每一个节点的边数变化可能会很大,好比某些节点链接了几万条边,有些节点只链接了一条边,这样邻接矩阵将会很是稀疏,虽然咱们能够利用压缩的办法来对这些稀疏矩阵进行存储,但稀疏矩阵的计算一直都是一个难题。

  此外,还有一个问题:对于同一个图,咱们将矩阵中任何行或列之间进行交换:
    

  虽然两个邻接矩阵看起来不同,但两者表示的倒是同一个图。

  也就是说,不一样的邻接矩阵,能够表示相同的链接性!这意味着若是我设计了一个神经网络,在上述两个不一样的矩阵输入后我得保证神经网络的输出是同样的。

  对于上面提到的两个问题,一个有效的解决方式是邻接表:

    

  上图有8个顶点,7条边。对于每一个顶点或者每条边的特征咱们用一个标量(通常为向量)来表示,全局特征也用一个标量(通常为向量)来表示。对于链接性,再也不用邻接矩阵来表示,而是用邻接列表来表示。

  使用邻接列表来表示链接性的两个好处:

  • 对于稀疏矩阵来讲,使用邻接列表存储显然更加节省空间。
  • 不存在两个不同的邻接列表表示同一张图。

5.图神经网络

  在经历了将数据转为graph以及将graph进行表示后,咱们就能使用GNN来对图进行处理了。

  一句话归纳GNN:GNN是对图的全部属性(节点、边、全局上下文)进行的可优化的一种变换,它保留了图的对称性(置换不变性)。

  简单来讲就是,咱们初始给定了节点或者边或者全局的属性,GNN将对这些属性进行变换,可是这种变换不会影响节点之间的链接性,变换优化后的图依旧保持着原图的链接结构。

  固然,也只有在变换后依旧保持着原图的链接结构,咱们才能使用这些变换后的属性对图进行预测。 试想在一个社交网络中,原来有朋友关系的节点通过GNN的变换后再也不具备朋友关系,此时再用这些变换后的属性对某一对节点进行预测,结果显而易见!

5.1 最简单的GNN

  以下所示:

    

   首先,对节点向量、边向量、全局向量分别构建一个MLP(多层感知机),MLP的输入输出的大小相同。

  三个MLP组成GNN的一层,一个图通过MLP后仍然是一个图。对于顶点、边、全局向量 分别 找到对应的MLP,做为其更新函数(update function)。能够看到,输出后图的属性变化了,可是图的结构没有改变,符合咱们的需求。MLP对每一个向量独自做用,不会影响的链接性。

5.2 Pooling

  堆叠了多层上述的模型后获得了GNN,如今来到最后一层,对节点进行预测。

  对于一个简单的二分类问题,好比上面3.2节提到的空手道俱乐部网络图,咱们须要对每一个节点进行分类,在咱们获得每一个节点的状态向量后,咱们能够搭建一个输出为2的全链接层,而后再通过一个Softmax,就能进行二分类了。多分类问题相似,只要将全链接层的输出改成n便可。

  以下所示:

   

  将通过最后一层后输出的节点状态向量  $V_n$  与一个全链接层相连,就能进行分类任务了。

  值得一提的是,这里全部节点都是共用一个全链接层,也就是全部节点共享同一个全链接层的参数。

  以上是最简单的一种状况,但咱们不得不考虑另一种状况:若是咱们没有一个节点的向量表示,但咱们仍想对该节点进行预测该怎么办? 答案是Pooling,Pooling在CNN中已经有过接触。

  具体以下所示:
    

  若是咱们没有右上角那个节点的向量表示,此时咱们就能够把与该节点相连的四条边的状态向量以及全局状态向量相加,获得这个节点的状态向量,而后再通过全链接层进行预测。

  相似地,若是没有某条边的状态向量,只有节点的状态向量,以下所示:

    

  此时咱们就能够把这条边上的两个节点的向量相加获得该边的向量,而后再进行预测。

  又好比咱们只有节点信息,没有全局信息,而咱们想对图的全局标签进行预测:

     

  此时一样能够将图中全部顶点的向量加起来,获得一个全局表示,而后再进行预测。

  所以,不管缺乏哪种信息,咱们最终都能经过Pooling操做来汇聚已有的信息,进而获得咱们想要的信息。

  具体来说,上面描述的GNN能够经过下图归纳:

    

  咱们将原始graph经过一个个GNN层(每一层都有三个MLP,分别对三种状态进行转换),而后,不管是顶点、边仍是全局,都经过同一个全链接层进行输出预测。

  上述这种最简单的GNN存在着一个很明显的缺陷:咱们在GNN层对节点或者边进行更新时,每层内全部节点共用一个MLP,全部边共用一个MLP,此时咱们并无考虑链接信息,也就是说咱们在对节点更新时没有考虑与该节点相连的其他节点或者边,更新边时没有考虑与该边相连的节点。

  简单来讲,咱们在更新时没有将图的结构信息考虑进去。

5.3 消息传递

  那么咱们怎么在更新时考虑结构信息呢?

    $\boldsymbol{x}_{n}(t+1)=f_{\boldsymbol{w}}\left(\boldsymbol{l}_{n}, \boldsymbol{l}_{\mathrm{co}[n]}, \boldsymbol{x}_{\mathrm{ne}[n]}(t), \boldsymbol{l}_{\mathrm{ne}[n]}\right)$

  以下图所示:

    

   咱们在更新每个节点的向量时,并不仅是简单地将该节点的向量经过一个MLP后获得更新后的向量,而是还要考虑与该节点相连节点的向量,也就是在下述更新公式中:

    $\boldsymbol{x}_{n}(t+1)=f_{\boldsymbol{w}}\left(\boldsymbol{l}_{n}, \boldsymbol{l}_{\mathrm{co}[n]}, \boldsymbol{x}_{\mathrm{ne}[n]}(t), \boldsymbol{l}_{\mathrm{ne}[n]}\right)$

  咱们要考虑 $x_{n e[n]}$  这一项了。

  固然上图这种更新方式并无太复杂,只是将该节点的向量与其相连节点的向量相加。

    

  考虑一种更为复杂的状况:

    

  在进行边的更新时,咱们能够将与该边相连的两个顶点的向量加入到该边的向量中(若是维度不一样则须要变换),而后再对该边进行更新。一样,对于某一个节点的更新,咱们也能够将与该节点相连的边的向量加入到该节点中,而后再对该节点进行更新。

  节点和边之间的消息传递存在一个选择:

     

  咱们能够先把边的信息传递给顶点,顶点更新后,再将更新后的顶点信息传递给边,边再更新(上图左),或者相反(上图右)。

  还有一种办法是交替传递:

    

   咱们能够同时进行两种操做:将边的信息给节点,而后节点的信息也给边。此时的节点和边都包含了各自的信息,而后再进行一次传递,将两者的信息互相传递,随后再用两个MLP对节点和边进行更新。

5.4 全局表示

  对一个large graph来说,即便咱们屡次进行消息传递,图中相距较远的两个顶点间也可能没法有效地相互传输信息。

  一种解决办法是加入master node(主节点)或者 context vector(上下文向量)。主节点是一个虚拟的点,咱们假设它与图中全部节点都相连,同时它也跟全部的边都相连。

  所以在进行顶点或者边的更新时,若是咱们加上全局表示 $U$,就能保证全部顶点(边)间都能传递信息。
    

   做者说这个其实能够认为是featurize-wise attention mechanism(特征级的注意力机制),由于将相近的节点汇集了过来。如今咱们就知道了基于消息传递的图神经网络是怎么样工做的。

6.实验

  在这篇文章中,做者很是费心将GNN嵌入到JavaScript中,搭建了这样一个playground,给出分子结构的数据集,经过调节超参数,获得训练效果和结果可视化。分子结构是能够自定义的,很是值得玩一玩。

    

7.相关知识

7.1 其余类型的图

  multigraph和分层图

    

  这里主要介绍了两种其余类型的图:多重图和嵌套图。

  所谓多重图,就是指图中一对节点间能够有多种不一样类型的边。 好比在社交网络中,两个节点(用户)之间的边,能够表示这两人是熟人、家人或者情侣。这种状况下,GNN能够经过为不一样类型的边设置不一样类型的消息传递方式来进行调整。

  所谓嵌套图,就是说图中的某一个节点可能就表示一个图。 好比在一个分子网络中,一个节点表明一个分子,若是一个分子能经过某种反应转换为另外一个分子,则两个分子之间有一条边。在这个网络中,节点(分子)自己也是一个图(原子-原子)。在这种状况下,可让GNN学习分子级别的表示和另外一个反应网络级别的表示,并于训练期间在它们之间进行交替。

  此外,还有超图,超图的一条边能够链接到多个节点,而不只仅是两个。对于这种状况,能够经过识别节点社区并分配链接到社区中全部节点的超边来构建超图。

7.2 采样和批处理

  图采样介绍了随机采样、随机游走、随机游走+邻居采样、扩散采样Z。

  GNN存在邻居爆炸的问题,即:GNN会不断地聚合图中相邻节点的信息,第L层GNN中的每一个目标节点都须要聚合原图中L层之前的全部节点信息。邻点爆炸式增加,使得GNN的minibatch训练极具挑战性。

  此外,因为彼此相邻的节点和边的数目不一样,咱们也不能使用恒定的批量大小。

  解决该问题的办法是从图中进行采样,获得一个子图,而后对子图进行处理。

  对一张图进行采样的四种方式以下图所示:

    

  • Random node sampling:先随机采样一些点(Sampled nodes),而后再采样它们的邻居。
  • Random walk sampling:作一些随机游走,从当前点的邻居节点中进行采样。
  • Random walk with neighborhood:结合前两种:先随机走必定长度,而后再采样它们的邻居。
  • Diffusion Sampling:取一个根节点,而后对它的一近邻、二近邻一直到K近邻进行采样,相似于一个BFS。

7.3 Inductive biases

  先说一说CNN的平移不变性:即便目标的外观发生了某种变化,可是利用CNN依然能够把它识别出来。即图像中的目标不管是被平移,被旋转,仍是被缩放,均可以被成功地识别出来。

  而在GNN中,也具备图对称性:也就是排列无关性,即便交换了顶点的顺序,GNN对其的做用都保持不变。

7.4 不一样的Pooling方式

  在GNN中,对节点和边的信息进行Pooling是关键操做,选择一个最优的Pooling方式是一个比较好的研究方向。

  常见的Pooling方式有max、mean和sum,做者对三者进行了比较:

    

  左边这幅图中,有2-4和4-4两个网络,若是咱们采用max,两者结果都是4,无法进行区分,而mean和sum能够对两者进行区分;右边这幅图中,max和mean无法区分两种网络,而sum却能够。

  所以,没有一个Pooling方式是明显优于其它Pooling方式的。

7.5 GCN做为子图函数近似

  GCN若是是k层,每一层都往前看一个邻居,那么最后一个节点看到的是一个子图,这个子图大小是k,和节点的距离是k。这里我理解的就是,GCN有多少层,就看到了多少阶的邻居。
  因此,GCN其实是有N个子图,每一个子图都是从原节点出发,往前走k步。

    

7.6 边和图对偶

  点和边作对偶,把边变成点,点变成边,邻接关系保持不变。

7.7 图注意力网络

  在GCN中,将邻居节点汇聚到某个节点上,其实是没有加权的。其实图神经网络中也能够像CNN中的卷积核同样,在3x3窗口中带有基于空间位置的不一样的权重。图上不须要空间位置,只须要经过注意力机制计算两个节点向量的关系强弱,按计算出来的权重来聚合。

    

7.8 图解释

  神经网络到底学到了什么东西,能够抓取子图来看学到了什么。

    

7.9 生成模型

  咱们以前的模型是不改变图结构的,这里经过生成模型能够对图的拓扑结构进行有效建模。

8 对文章和GNN的评论

  • 对于文章

  从头至尾读下来很是流畅!先介绍什么是图,在图中咱们对顶点、边、全局都用向量表示,以及现实中的数据如何表示为图,如何对图作预测,算法用到图上有什么挑战。而后开始介绍图神经网络,首先定义了GNN是对属性作变换而不改变其结构,从最简单的例子开始讲解,用三个MLP作属性向量的变换,用全链接层作输出从而实现预测。若是有缺失向量怎么办,那就作聚合操做,把边、节点、全局属性利用上,也能够完成咱们的预测工做。最后介绍真正意义的GNN,每一层经过汇聚操做把信息传递过来,从每一个顶点看到邻居节点的信息,在每一层能充分汇聚到图中的信息。而后是实验部分,做者搭建了playground供读者玩,跑出了不一样的超参数对模型效果的影响,最后对GNN的相关技术进行了展开。
文章写得是很是精美的,文中存在大量的交互图,文字围绕图展开。这么多的交互图既是缺点也是优势,用JavaScript写如此多的交互图是很是耗时间的事情,做者尽量用图来代替大量的公式和代码,更直观易懂。本文的缺点就是,文章的宽度的展开,不少地方让读者只知其一;不知其二,了解不到其中细节,致使懂GNN的人能感觉到GNN的强大,不懂GNN的人仍然不知道其核心在哪里。

  • 对于GNN

  图是很是强大,几乎全部数据都能表示成图,可是图上作优化很难,涉及到CPU和GPU的训练也是一个挑战,同时图神经网络对超参数很是敏感。近些年图神经网络在学术界迅速发展,实际上工业落地的并很少,GNN的发展还须要时间的沉淀。